Parameter Estimation for Constrained Context-Free Language Models

PARAMETER ESTIMATION FOR CONSTRAINED CONTEXT-FREE LANGUAGE MODELS Kevin Mark, Michael Miller, Ulf Grenander~ Steve Abney t Electronic Systems and Signals Research Laboratory Washington University St. Louis, Missouri 63130 ABSTRACT A new language model incorporating both N-gram and context-free ideas is proposed. This constrained context-free model is specified by a stochastic context-free prior distribu- tion with N-gram frequency constraints. The resulting dis- tribution is a Markov random field. Algorithms for sampling from this distribution and estimating the parameters of the model are presented. 1. INTRODUCTION This paper introduces the idea of N-gram constrained context-free language models. This class of language models merges two prevalent ideas in language modeling: N-grams and context-free grammars. In N-gram lan- guage models, the underlying probability distributions are Markov chains on the word string. N-gram mod- els have advantages in their simplicity. Both parameter estimation and sampling from the distribution are sim- ple tasks. A disadvantage of these models is their weak modeling of linguistic structure. Context-free language models are instances of random branching processes. The major advantage of this class of models is its ability to capture linguistic structure. In the following section, notation for stochastic context- free language models and the probability of a word string under this model are presented. Section 3 reviews a pa- rameter estimation algorithm for SCF language models. Section 4 introduces the bigram-constrained context-free language model. This language model is seen to be a Markov random field. In Section 5, a random sampling algorithm is stated. In Section 6, the problem of param- eter estimation in the constrained context-free language model is addressed. *Division of Applied Mathematics, Brown University, Provi- dence, Rhode Island 02904 tBell Communications Research, Morristown, New Jersey 07962 2. STOCHASTIC CONTEXT-FREE GRAMMARS A stochastic context-free grammar G is specified by the quintuple < VN, VT, R, S, P > where VN is a finite set of non-terminal symbols, VT is a finite set of terminal symbols, R is a set of rewrite rules, S is a start symbol in VN, and P is a parameter vector. If r 6 R, then Pr is the probability of using the rewrite rule r. For our experiments, we are using a 411 rule grammar which we will refer to as the Abney-2 grammar. The grammar has 158 syntactic variables, i.e., IVNI = 158. The rules of the Abney-2 grammar are of the form H -+ G1,G2 .... Gk where H, Gi 6 VN and k = 1,2 ..... Hence, this grammar is not expressed in Chomsky Nor- mal Form. We maintain this more general form for the purposes of linguistic analysis. An important measure is the probability of a deriva- tion tree T. Using ideas from the random branching process literature [2, 4], we specify a derivation tree T by its depth L and the counting statistics zt(i,k),l = 1 .... ,n,i = 1 .... ,IVNI, and k = 1 ..... IRI. The count- ing statistic zz(i, k) is the number of non-terminals at 6 VN rewritten at level I …

Content truncated to 500 words