Language modeling has found useful applications in speech and natural language tasks such as phonetic decoding, parsing, machine translation and text generation. With the increasing availability of large corpora, statistical language models for natural language have been attracting more and more attention for their ability to score language strings in addition to simply testing strings for language membership....[ Read more ]

Language modeling has found useful applications in speech and natural language tasks such as phonetic decoding, parsing, machine translation and text generation. With the increasing availability of large corpora, statistical language models for natural language have been attracting more and more attention for their ability to score language strings in addition to simply testing strings for language membership.

Although finite-state language models such as N-grams and Hidden Markov Models have achieved'impressive measures of predictive power among probabilistic language models, we believe that a context-free grammar formalism, with its enhanced ability to model center embeddings and long-distance dependencies, has the potential of outperforming these linguistically simplistic models, provided sufficiently constrained learning techniques can be found for estimating the parameters reliably. To this end, we studied the use of probabilistic link grammars, a relatively new context-free grammar formalism with the desirable properties of being highly constrained and lexical, in modeling natural language sources.

The aim of this work is to induce the grammar rules (which are in the form of disjuncts in link grammar) in addition to estimating their probabilities. We have made a number of simplifications to the original probabilistic link grammar model proposed by Lafferty et al. to suit our purpose. We have also developed a revised model formulation to better capture word associations and resolve the sparse data problem.

Our grammar learning approach employs maximum-likelihood estimation from incomplete data. The training algorithm we used is in the spirit of the Inside- Outside algorithm, which falls under the EM (Expectation-Maximization) framework. We have also investigated issues such as appropriate parameter initialization, use of a suitable bias, and limguistic constraints to guide generalization.

We have run preliminary experiments for our probabilistic models using an English corpus of limited vocabulary and sentence length. The results are evaluated using the criteria of parsing correctness and perplexity measures.