Linguistic Structure Prediction (Synthesis Lectures on Human Language Technologies)

✍ Scribed by Noah A. Smith

• Publisher: Morgan & Claypool Publishers
• Year: 2011
• Tongue: English
• Leaves: 270
• Series: Synthesis Lectures on Human Language Technologies
• Edition: 1
• Category: Library

✦ Synopsis

A major part of natural language processing now depends on the use of text data to build linguistic analyzers. We consider statistical, computational approaches to modeling linguistic structure. We seek to unify across many approaches and many kinds of linguistic structures. Assuming a basic understanding of natural language processing and/or machine learning, we seek to bridge the gap between the two fields. Approaches to decoding (i.e., carrying out linguistic structure prediction) and supervised and unsupervised learning of models that predict discrete structures as outputs are the focus. We also survey natural language processing problems to which these methods are being applied, and we address related topics in probabilistic inference, optimization, and experimental methodology. Table of Contents: Representations and Linguistic Data / Decoding: Making Predictions / Learning Structure from Annotated Data / Learning Structure from Incomplete Data / Beyond Decoding: Inference

✦ Table of Contents

Preface......Page 15
Acknowledgments......Page 21
Representations and Linguistic Data......Page 23
Sequential Prediction......Page 24
Sequence Segmentation......Page 26
Word Classes and Sequence Labeling......Page 27
Morphological Disambiguation......Page 28
Chunking......Page 29
Syntax......Page 31
Semantics......Page 33
Coreference Resolution......Page 36
Discourse......Page 38
Alignment......Page 39
Types......Page 40
Why Linguistic Structure is a Moving Target......Page 41
Conclusion......Page 42
Definitions......Page 45
Five Views of Decoding......Page 46
Probabilistic Graphical Models......Page 49
Polytopes......Page 53
Parsing with Grammars......Page 59
Graphs and Hypergraphs......Page 61
Weighted Logic Programs......Page 63
Dynamic Programming......Page 66
Shortest or Minimum-Cost Path......Page 67
Semirings......Page 70
DP as Logical Deduction......Page 72
Solving DPs......Page 77
Approximate Search......Page 83
Specialized Graph Algorithms......Page 86
Spanning Trees......Page 87
Maximum Flow and Minimum Cut......Page 88
Conclusion......Page 89
Annotated Data......Page 91
Generic Formulation of Learning......Page 92
Generative Models......Page 93
Multinomial-Based Models......Page 95
Hidden Markov Models......Page 96
Other Generative Multinomial-Based Models......Page 100
Maximum Likelihood Estimation By Counting......Page 101
Maximum A Posteriori Estimation......Page 103
Alternative Parameterization: Log-Linear Models......Page 105
Comments......Page 107
Conditional Models......Page 108
Logistic Regression......Page 110
Conditional Random Fields......Page 111
Feature Choice......Page 113
Maximum Likelihood Estimation......Page 114
Maximum A Posteriori Estimation......Page 116
Pseudolikelihood......Page 119
Toward Discriminative Learning......Page 120
Binary Classification......Page 121
Perceptron......Page 123
Multi-class Support Vector Machines......Page 125
Structural SVM......Page 126
Optimization......Page 127
Conclusion......Page 128
Learning Structure from Incomplete Data......Page 131
Unsupervised Generative Models......Page 132
Expectation Maximization......Page 133
Word Clustering......Page 134
Hard and Soft K-Means......Page 137
The Structured Case......Page 139
Hidden Markov Models......Page 141
EM Iterations Improve Likelihood......Page 142
Extensions and Improvements......Page 144
Log-Linear EM......Page 145
Contrastive Estimation......Page 146
Bayesian Unsupervised Learning......Page 147
Latent Dirichlet Allocation......Page 149
Inference......Page 151
Nonparametric Bayesian Methods......Page 156
Discussion......Page 161
Hidden Variable Learning......Page 162
Generative Models with Hidden Variables......Page 163
Conditional Log-Linear Models with Hidden Variables......Page 164
Large Margin Methods with Hidden Variables......Page 165
Conclusion......Page 167
Beyond Decoding: Inference......Page 169
Summing by Dynamic Programming......Page 170
Feature Expectations......Page 172
Reverse DPs......Page 174
Another Interpretation of Reverse Values......Page 177
From Reverse Values to Expectations......Page 179
Deriving the Reverse DP......Page 181
Non-DP Expectations......Page 182
Minimum Bayes Risk Decoding......Page 185
Decoding with Hidden Variables......Page 187
Conclusion......Page 189
Numerical Optimization......Page 191
The Hill-Climbing Analogy......Page 192
Coordinate Ascent......Page 193
Gradient Ascent......Page 194
Subgradient Methods......Page 196
Conjugate Gradient and Quasi-Newton Methods......Page 197
Limited Memory BFGS......Page 198
``Aggressive'' Online Learners......Page 199
Improved Iterative Scaling......Page 200
Methodology......Page 203
Training, Development, and Testing......Page 204
Comparison without Replication......Page 205
Hypothesis Testing and Related Topics......Page 206
Terminology......Page 207
Standard Error......Page 208
Beyond Standard Error for Sample Means......Page 209
Confidence Intervals......Page 210
Hypothesis Tests......Page 211
Closing Notes......Page 219
Maximum Entropy......Page 221
Probabilistic Finite-State Automata......Page 225
Maximum Entropy Markov Models......Page 226
Directional Effects......Page 227
Comparison to Globally Normalized Models......Page 228
Decoding......Page 229
Theory vs. Practice......Page 230
Bibliography......Page 231
Author's Biography......Page 263
Index......Page 0