DEPARTMENT OF COMPUTER SCIENCE
DOCTORAL DISSERTATION DEFENSE


Candidate: Mark Epstein
Advisor: Ralph Grishman

Maximum-Likelihood Estimation for Natural Language Understanding

10:00 a.m., Monday, July 22, 1996
12th floor conference room, 719 Broadway




Abstract

The problem of Natural Language Understanding (NLU) has intrigued researchers since the 1960's. Most researchers working in computational linguistics focus on linguistic solutions to their problems. They develop grammars and parsers to process the input natural language into a meaning representation. In this thesis, a new approach is utilized. Borrowing from the field of communication theory, an information theoretic approach to natural language understanding is applied. This is based on the source-channel model of communication.

The source-channel model of NLU assumes that the user has a meaning in the domain of the application that he wishes to convey. This meaning is sent through a noisy channel. The observer receives the English sentence as output from the noisy channel. The observer then submits the English sentence to a decoder, which determines the meaning most likely to have generated the English. The decoder uses mathematical models of the channel and the meanings to process the English sentence. Thus, the following problems must be addressed in a source-channel model for NLU:

1.
A mathematical model of the noisy-channel must be developed.
2.
The parameters of the model must be set, either manually or by an automatic training procedure.
3.
A decoder must be built to search through the meaning space for the most likely meaning to have generated the observed English.

This dissertation focuses on the first two of these problems. Several mathematical models of the noisy channel are developed. They are trained from a corpus of context independent sentence pairs consisting of both English and the corresponding meaning. The parameters of the models are trained to maximize the likelihood of the model's prediction of the observed training data using Dempster and Laird's Expectation-Maximization algorithm. Results are presented for the Air Travel Information Service (ATIS) domain.