Natural Language Processing 1st Edition by Jacob Eisenstein ISBN 0262042843 9780262042840

1. Introduction
   1.1 Natural language processing and its neighbors . . . . . . . . . . . . . . . . . . 1
   1.2 Three themes in natural language processing . . . . . . . . . . . . . . . . . . 6
   1.2.1 Learning and knowledge . . . . . . . . . . . . . . . . . . . . . . . . . 6
   1.2.2 Search and learning . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
   1.2.3 Relational, compositional, and distributional perspectives . . . . . . . 9

I. Learning 11
2. Linear text classification 13
2.1 The bag of words . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.2 Naïve Bayes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.2.1 Types and tokens . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.2.2 Prediction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.2.3 Estimation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.2.4 Smoothing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.2.5 Setting hyperparameters . . . . . . . . . . . . . . . . . . . . . . 23
2.3 Discriminative learning . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.3.1 Perceptron . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.3.2 Averaged perceptron . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.4 Loss functions and large-margin classification . . . . . . . . . . . . . . 27
2.4.1 Online large margin classification . . . . . . . . . . . . . . . . . 30
2.4.2 Derivation of the online support vector machine . . . . . . . . . . . 32
2.5 Logistic regression . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
2.5.1 Regularization . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
2.5.2 Gradients . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
2.6 Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
2.6.1 Batch optimization . . . . . . . . . . . . . . . . . . . . . . . . . 38
2.6.2 Online optimization . . . . . . . . . . . . . . . . . . . . . . . . . 39
2.7 Additional topics in classification . . . . . . . . . . . . . . . . . . . . . 41
2.7.1 Feature selection by regularization . . . . . . . . . . . . . . . . . 41
2.7.2 Other views of logistic regression . . . . . . . . . . . . . . . . . . . 41
2.8 Summary of learning algorithms . . . . . . . . . . . . . . . . . . . . . . . 43

3. Nonlinear classification 47
   3.1 Feedforward neural networks . . . . . . . . . . . . . . . . . . . . . . . . . 48
   3.2 Designing neural networks

1. Introduction
   1.1 Natural language processing and its neighbors
   1.2 Three themes in natural language processing
   1.2.1 Learning and knowledge
   1.2.2 Search and learning
   1.2.3 Relational, compositional, and distributional perspectives

I. Learning
2. Linear text classification
2.1 The bag of words
2.2 Naïve Bayes
2.2.1 Types and tokens
2.2.2 Prediction
2.2.3 Estimation
2.2.4 Smoothing
2.2.5 Setting hyperparameters
2.3 Discriminative learning
2.3.1 Perceptron
2.3.2 Averaged perceptron
2.4 Loss functions and large-margin classification
2.4.1 Online large margin classification
2.4.2 Derivation of the online support vector machine
2.5 Logistic regression
2.5.1 Regularization
2.5.2 Gradients
2.6 Optimization
2.6.1 Batch optimization
2.6.2 Online optimization
2.7 Additional topics in classification
2.7.1 Feature selection by regularization
2.7.2 Other views of logistic regression
2.8 Summary of learning algorithms

3. Nonlinear classification
   3.1 Feedforward neural networks
   3.2 Designing neural networks
   3.2.1 Activation functions
   3.2.2 Network structure
   3.2.3 Outputs and loss functions
   3.2.4 Inputs and lookup layers
   3.3 Learning neural networks
   3.3.1 Backpropagation
   3.3.2 Regularization and dropout
   3.3.3 Learning theory
   3.3.4 Tricks
   3.4 Convolutional neural networks

4. Linguistic applications of classification
   4.1 Sentiment and opinion analysis
   4.1.1 Related problems
   4.1.2 Alternative approaches to sentiment analysis
   4.2 Word sense disambiguation
   4.2.1 How many word senses?
   4.2.2 Word sense disambiguation as classification
   4.3 Design decisions for text classification
   4.3.1 What is a word?
   4.3.2 How many words?
   4.3.3 Count or binary?
   4.4 Evaluating classifiers
   4.4.1 Precision, recall, and F-MEASURE
   4.4.2 Threshold-free metrics
   4.4.3 Classifier comparison and statistical significance
   4.4.4 Multiple comparisons
   4.5 Building datasets
   4.5.1 Metadata as labels
   4.5.2 Labeling data

5. Learning without supervision
   5.1 Unsupervised learning
   5.1.1 K-means clustering
   5.1.2 Expectation-Maximization (EM)
   5.1.3 EM as an optimization algorithm
   5.1.4 How many clusters?
   5.2 Applications of expectation-maximization
   5.2.1 Word sense induction
   5.2.2 Semi-supervised learning
   5.2.3 Multi-component modeling
   5.3 Semi-supervised learning
   5.3.1 Multi-view learning
   5.3.2 Graph-based algorithms
   5.4 Domain adaptation
   5.4.1 Supervised domain adaptation
   5.4.2 Unsupervised domain adaptation
   5.5 Other approaches to learning with latent variables
   5.5.1 Sampling
   5.5.2 Spectral learning

II. Sequences and Trees
6. Language models
6.1 N-gram language models
6.2 Smoothing and discounting
6.2.1 Smoothing
6.2.2 Discounting and backoff
6.2.3 Interpolation
6.2.4 Kneser-Ney smoothing
6.3 Recurrent neural network language models
6.3.1 Backpropagation through time
6.3.2 Hyperparameters
6.3.3 Gated recurrent neural networks
6.4 Evaluating language models
6.4.1 Held-out likelihood
6.4.2 Perplexity
6.5 Out-of-vocabulary words

7. Sequence labeling
   7.1 Sequence labeling as classification
   7.2 Sequence labeling as structure prediction
   7.3 The Viterbi algorithm
   7.3.1 Example
   7.3.2 Higher-order features
   7.4 Hidden Markov Models
   7.4.1 Estimation
   7.4.2 Inference
   7.5 Discriminative sequence labeling with features
   7.5.1 Structured perceptron
   7.5.2 Structured support vector machines
   7.5.3 Conditional random fields
   7.6 Neural sequence labeling
   7.6.1 Recurrent neural networks
   7.6.2 Character-level models
   7.6.3 Convolutional Neural Networks for Sequence Labeling
   7.7 Unsupervised sequence labeling
   7.7.1 Linear dynamical systems
   7.7.2 Alternative unsupervised learning methods
   7.7.3 Semiring notation and the generalized Viterbi algorithm

8. Applications of sequence labeling
   8.1 Part-of-speech tagging
   8.1.1 Parts-of-Speech
   8.1.2 Accurate part-of-speech tagging
   8.2 Morphosyntactic Attributes
   8.3 Named Entity Recognition
   8.4 Tokenization
   8.5 Code switching
   8.6 Dialogue acts

9. Formal language theory
   9.1 Regular languages
   9.1.1 Finite state acceptors
   9.1.2 Morphology as a regular language
   9.1.3 Weighted finite state acceptors
   9.1.4 Finite state transducers
   9.1.5 Learning weighted finite state automata
   9.2 Context-free languages
   9.2.1 Context-free grammars
   9.2.2 Natural language syntax as a context-free language
   9.2.3 A phrase-structure grammar for English
   9.2.4 Grammatical ambiguity
   9.3 Mildly context-sensitive languages
   9.3.1 Context-sensitive phenomena in natural language
   9.3.2 Combinatory categorial grammar

10. Context-free Parsing
10.1 Deterministic bottom-up parsing
10.1.1 Recovering the parse tree
10.1.2 Non-binary productions
10.1.3 Complexity
10.2 Ambiguity
10.2.1 Parser evaluation
10.2.2 Local solutions
10.3 Weighted Context-Free Grammars
10.3.1 Parsing with weighted context-free grammars
10.3.2 Probabilistic context-free grammars
10.3.3 Semiring weighted context-free grammars
10.4 Learning weighted context-free grammars
10.4.1 Probabilistic context-free grammars
10.4.2 Feature-based parsing
10.4.3 Conditional random field parsing
10.4.4 Neural context-free grammars
10.5 Grammar refinement
10.5.1 Parent annotations and other tree transformations
10.5.2 Lexicalized context-free grammars
10.5.3 Refinement grammars
10.6 Beyond context-free parsing
10.6.1 Reranking
10.6.2 Transition-based parsing

11. Dependency Parsing
11.1 Dependency grammar
11.1.1 Heads and dependents
11.1.2 Labeled dependencies
11.1.3 Dependency subtrees and constituents
11.2 Graph-based dependency parsing
11.2.1 Graph-based parsing algorithms
11.2.2 Computing scores for dependency arcs
11.2.3 Learning
11.3 Transition-based dependency parsing
11.3.1 Transition systems for dependency parsing
11.3.2 Scoring functions for transition-based parsers
11.3.3 Learning to parse
11.4 Applications

III. Meaning
12. Logical semantics
12.1 Meaning and denotation
12.2 Logical representations of meaning
12.2.1 Propositional logic
12.2.2 First-order logic
12.3 Semantic parsing and the lambda calculus
12.3.1 The lambda calculus
12.3.2 Quantification
12.4 Learning semantic parsers
12.4.1 Learning from derivations
12.4.2 Learning from logical forms
12.4.3 Learning from denotations

13. Predicate-argument semantics
    13.1 Semantic roles
    13.1.1 VerbNet
    13.1.2 Proto-roles and PropBank
    13.1.3 FrameNet
    13.2 Semantic role labeling
    13.2.1 Semantic role labeling as classification
    13.2.2 Semantic role labeling as constrained optimization
    13.2.3 Neural semantic role labeling
    13.3 Abstract Meaning Representation
    13.3.1 AMR Parsing

14. Distributional and Distributed Semantics
    14.1 The distributional hypothesis
    14.2 Design decisions for word representations
    14.2.1 Representation
    14.2.2 Context
    14.2.3 Estimation
    14.3 Latent semantic analysis
    14.4 Brown clusters
    14.5 Neural word embeddings
    14.5.1 Continuous bag-of-words (CBOW)
    14.5.2 Skipgrams
    14.5.3 Computational complexity
    14.5.4 Word embeddings as matrix factorization
    14.6 Evaluating word embeddings
    14.6.1 Intrinsic evaluations
    14.6.2 Extrinsic evaluations
    14.6.3 Fairness and bias
    14.7 Distributed representations beyond distributional statistics
    14.7.1 Word-internal structure
    14.7.2 Lexical semantic resources
    14.8 Distributed representations of multiword units
    14.8.1 Purely distributional methods
    14.8.2 Distributional-compositional hybrids
    14.8.3 Supervised compositional methods
    14.8.4 Hybrid distributed-symbolic representations