Advanced Natural Language Processing 2013
General Topics
These are topics and issues that are relevant to more than one part
the course. You should be able to briefly discuss each, with respect
to what it is relevant to.
- Zipf's Law
- Ambiguity (Lexical, Syntactic, Semantic, Discourse-functional)
- Open-class Words, Closed-class Words
- Part-of-Speech and PoS-tagging
- Sparse Data
Lexical Processing
1. Concepts
You should be able to explain each of these concepts, give
one or two examples where appropriate, and its pros and cons (again
where appropriate).
- Tokenization
- Morphology: Stems, Affixes, Root, Lemma
- Inflectional Morphology
- Derivational Morphology
- Lexical compound
- Finite State Machine
- Regular Language and Regular Expression
- N-Gram Language Model
- Markov Model
- Hidden Markov Model
- Add-One / Add-Alpha Smoothing
- Good-Turing Smoothing (not required: derivation of Good Turing Smoothing)
- Witten-Bell Smoothing
- Kneser-Ney Smoothing
- Backoff
- Interpolation
- Interpolated Back-Off
- Trie Structure for Backoff Language Models
- Bayes Rule
- Spelling Correction
- Features in Machine Learning
- Feature Selection
2. Types of methods
For types of methods, you should be able to describe their essential elements.
- Automatic Learning of Morphology
- Expectation-Maximization Algorithm (EM)
- Maximum Entropy Models - Improved Iterative Scaling
- N-Best List Reranking
- Perceptron Algorithm
3. Specific methods
For specific methods, you should be able to hand simulate each one.
- Maximum Likelihood Estimation
- Viterbi Algorithm for Hidden Markov Models
- Finding minimum string edit distance
Grammars and Parsing
1. Concepts
You should be able to explain each concept, give
one or two examples where appropriate, and its pros and cons (again
where appropriate).
- Context-Free Grammar
- Bounded and unbounded dependencies
- Nested vs. crossing dependencies
- Mildly Context-sensitive Grammar
- Phrase-structure grammar vs. Lexicalized grammar
- Tree Adjoining Grammar
- Dependency grammar
- Dependency structures: Projective vs. Non-projective
- Dependency parsing: Maximal spanning trees
- Search space: What is one searching for in parsing and what is
one searching through?
- Breadth-first search, depth-first search, and differences
between them
- Parsing as dynamic programming: What problems is one solving and
how does this differ from breadth-first and depth-first search?
- Prediction in parsing (as in Earley parser with Dotted Rules)
- Difference between recognition and parsing
- Push-Down Automaton
- Probabilistic Context-Free Grammar
- Head Words (in Syntax)
- Competence vs Performance
- PARSEVAL: precision, recall
- Complexity of CKY Parsing
- Coarse-to-Fine Parsing
- Outside Cost Estimation
- Oracle Performance
2. Types of Methods
For types of methods, you should be able to describe their essential elements.
- Top-Down parsing
- Bottom-Up parsing
- Chart Parsing
3. Specific Methods
For specific methods, you should be able to hand simulate each one.
- CKY Parsing
- Earley Parsing
Discourse Processing
1. Concepts
You should be able to explain each of these concepts, give
one or two examples where appropriate, and its pros and cons (again
where appropriate).
- Reference
- Coreference
- Anaphora
- Constraints on anaphor binding
- Preferences in anaphor resolution
- Cohesion in Discourse
- Coherence
- Coherence relations
- Rhetorical Structure Theory
- Discourse connectives
2. Types of methods
For types of methods, you should be able to describe their essential elements.
3. Specific methods
For specific methods, you should be able to hand simulate each one.
Semantic Processing
1. Concepts
You should be able to explain each of these concepts, give
one or two examples where appropriate, and its pros and cons (again
where appropriate).
- Meaning representations (MR)
- Canonical Form
- First Order Logic as a MR
- Compositionality
- Expressivity
- Lambda expression
- Word Senses
- Relations between word senses
- WordNet
- Thematic Roles
- Selectional Restrictions
- Question Answering
- Similarity Metric
2. Types of methods
For types of methods, you should be able to describe their essential elements.
- Syntax Driven Semantic Analysis
- Constraint satisfaction for Word Sense Disambiguation (WSD)
- Supervised Learning for WSD (Naive Bayes Classifier, Decision List Classifier)
- Unsupervised methods for WSD (Agglomerative Clustering)
- Cosine Similarity Metric
3. Specific methods
For specific methods, you should be able to hand simulate each one.
- Lambda reduction
- Compositional Semantics: parsing with semantic attachments