Probabilistic Grammars and Data-Oriented Parsing 

References

Bod and Kaplan (to appear). A Data-Oriented Parsing Model for Lexical-Functional Grammar.

Eugene Charniak (1993). Statistical Language Learning.

Eugene Charniak (1996). Treebank Grammars.

Chi and Geman (1998). Estimation of Probabilistic Context-Free Grammars.

Joshua Goodman (1999). Semiring Parsing.

Mark Johnson (1999). PCFG models of linguistic tree representations.

Jurafsky and Martin (2000). Speech and Language Processing.

Klein and Manning (2003). Accurate Unlexicalized Parsing.

Mike de Kreek (2003). Language Acquisition and Virtual Grammars. On the Continuity of Cognition.

Manning and Schütze (1999). Foundations of Statistical Natural Language Processing.

Bernard Merialdo (1994). Tagging English Text with a Probabilistic Model.

Shinsuke Mori and Makoto Nagao (1995). Parsing Without Grammar.

Detlef Prescher (2003). A Tutorial on the Expectation-Maximization Algorithm Including Maximum-Likelihood Estimation and EM Training of Probabilistic Context-Free Grammars.

Sanchez and Benedi (1997). Consistency of Stochastic Context-Free Grammars from Probabilistic Estimation based on Growth Transformations.

Sabine Schulte im Walde (2000). The German Statistical Grammar Model: Development, Training and Linguistic Exploitation.

Tylman Ule (2003). Directed Treebank Refinement for PCFG Parsing.

Syllabus

• Lecture 1 (February 3): Formal definition of a context-free grammar (CFG); Chomsky's very first context-free syntax tree; CFGs can be used as parsers and generators; sentence generation with a CFG is a non-deterministic process; This leads to a formal definition of PCFGs that is based on rule, tree and sentence probabilities.
  Reading: The sub-section "Background: Probabilistic Modeling of CFGs" of Section 5 of Prescher (2003).
  Recommended: Chapter 9 of the book of Jurafsky and Martin.

• Lecture 2 (February 10): Non-standard PCFGs; Resolving ambiguities with PCFGs; Two examples: PP attachment and conjunctions; PCFGs can deal with these, but a transformation of the underlying CFG should be done beforehand; The parent-encoding technique; Definition of treebank grammars.
  Reading: The sub-section "Background: Resolving Ambiguities with PCFGs" of Section 5 of Prescher (2003).
  Highly recommended: Charniak (1996), Mark Johnson (1999), and Klein and Manning (2003).
  For freaks: Sanchez and Benedi (1997), and Chi and Geman (1998).

• Lecture 3 (February 17): General Estimation Theory: Definition of a corpus and the relative-frequency estimate and (restricted or unrestricted) probability models; Definition of corpus probabilities and the maximum-likelihood estimation; Problems for MLE: existence, uniqueness, and efficiency; MLE and relative-frequency estimation: The relative-frequency estimate is a ML estimate for a (restricted or unrestricted) probability model, if and only if the relative-frequency estimate is a model instance; The information inequality of information theory; MLE and relative-entropy estimation: Maximizing the corpus probability is equivalent to minimizing the relative entropy with respect to the relative-frequency estimate.
  Reading: Section 2 of Prescher (2003).

• Lecture 4 (February 24): Review of the general estimation theory; Estimation of PCFGs: Definition of a CFG's probability model; A CFG's probability model is restricted if the CFG is read off from a treebank and if it generates a full parse-tree outside the treebank: The relative-frequency estimate on the treebank is NOT an instance of this CFG's probability model! On the one hand, this is good as ML estimates for unrestricted models necessarily overfit their training corpus; On the other hand, this is bad: Is there a ML estimate for a CFG's probability model on a given treebank?! Is it unique?! Can it be efficiently calculated?!
  Reading: The beginning of sub-section "Maximum-Likelihood Estimation of PCFGs" of Section 5 of Prescher (2003).

• Lecture 5 (March 2): Estimation of PCFGs: The ML estimate for a CFG's probability model on a given treebank is the treebank grammar!
  Reading: The end of sub-section "Maximum-Likelihood Estimation of PCFGs" of Section 5 of Prescher (2003).

• Lecture 6 (March 9): Definition of the input of the EM algorithm (a symbolic analyzer, an incomplete-data corpus, a complete-data model, and a randomly generated starting instance); Definition of the procedure of the EM algorithm (a loop over E- and M-steps: an E-step generates a complete-data corpus expected by the current model instance, and a M-step looks for a maximum-likelihood estimate for the complete-data model on the expected complete-data corpus); Theorem about the output of the EM algorithm (a sequence of instances of the complete-data model, so-called EM re-estimates, such that the sequence of probabilities allocated to the incomplete-data corpus is monotonic increasing); So the EM algorithm aims at doing MLE on incomplete-data by performing a series of MLE steps on complete-data. Typically, the EM algorithm will be applied in settings, where incomplete-data MLE is difficult but complete-data MLE is easy! Example: The EM algorithm for PCFGs.
  Reading: Section 3 and the sub-section "EM-Training of PCFGs" of Section 5 of Prescher (2003).

• Lecture 7 (March 16): The semiring-parsing algorithm (comprising many standard parsing algorithms like the parse-forest, the CKY, the count, the inside, and the Viterbi algorithm).
  Reading: Goodman (1999).

• Lecture 8 (March 30): Data-Oriented Parsing I (ppt)
  

• Lecture 9 (April 6): Data-Oriented Parsing II (ppt)
  

• Lecture 10 (April 13): Data-Oriented Parsing and Estimation Theory
  

• Lecture 11 (April 20): Presentation (Klein and Manning, 2003).
  

• Lecture 12 (April 27): Presentation (Sabine Schulte im Walde, 2000)
  

• Lecture 13 (May 4): Presentation (Bod and Kaplan, to appear)
  

• Lecture 14 (May 11): Presentation (Mike de Kreek, 2003)