Statistical Parsing - probabilistic models and stochastic grammars

Mark Johnson, Brown University, USA

ABSTRACT:

This course unites two different approaches to computational linguistics and natural language processing. On the one hand, there is considerable linguistic evidence that natural language possesses a rich hierarchical structure that is only indirectly reflected in the sequence of words or sounds that make up sentences. On the other hand, there are also reliable statistical regularities in the selection and ordering of words and phrases in natural languages. Stochastic grammars are capable of describing both aspects of natural languages, and are a key component of state-of-the-art technology in many areas of computational linguistics.

This course will cover the following topics:

• An introduction to language modeling and the noisy channel model.
• Applications of language modeling and parsing, including speech recognition, machine translation and information extraction and retrieval.
• Finite-state machines and hidden Markov models.
• Probabilistic context-free grammars (PCFGs).
• Estimation of PCFGs from visible and hidden data (maximum likelihood estimation, expectation maximization).
• Chart parsing and dynamic programming algorithms.
• Stochastic Unification-based Grammars and discriminative training.

The course does not have any specific prerequisites, but mathematical and computer science background will be helpful. The ability to take derivatives and manipulate mathematical expressions at a first-year undergraduate level will enable students to follow the derivation of the formulas, and computer science experience in algorithms with enable students to understand, analyze and implement the various algorithms described in the course.

BIO :

Mark Johnson is Professor of Cognitive & Linguistic Sciences and Computer Science at Brown University, and current president of the Association for Computational Linguistics. He has made significant contributions to research into computational processes involved in human language understanding, and is at the forefront of research in statistical natural language processing. [http://www.cog.brown.edu/~mj/]

RESOURCES:

• Probability and Statistics in Computational Linguistics: a brief review. (S. German and M. Johnson) [German-Johnson.pdf]
• Estimators for Stochastic "Unification-Based" Grammars. (M. Johnson, S. German, S. Canon, Z. Chi and S. Riezler) [Johnson-German-Canon-etal.pdf]
• Edge-Based Best-First Chart Parsing. (E.Charniak, S.Goldwater and M.Johnson). [Charniak-Goldwater-Johnson.pdf]
• PCFG Models of Linguistic Tree Representations. (M.Johnson) [Johnson.pdf]

• Index
• Preface
• Table of Contents
• Acknowledgements