Syntactic Decision Tree LMs: Random Selection or Intelligent Design?

Proceedings of the 2011 Conference on Empirical Methods in Natural Language Processing, pages 691–699, Edinburgh, Scotland, UK, July 27–31, 2011. c⃝2011 Association for Computational Linguistics Syntactic Decision Tree LMs: Random Selection or Intelligent Design? Denis Filimonov†‡ ‡Human Language Technology Center of Excellence Johns Hopkins University den@cs.umd.edu Mary Harper† †Department of Computer Science University of Maryland, College Park mharper@umd.edu Abstract Decision trees have been applied to a vari- ety of NLP tasks, including language mod- eling, for their ability to handle a variety of attributes and sparse context space. More- over, forests (collections of decision trees) have been shown to substantially outperform individual decision trees. In this work, we in- vestigate methods for combining trees in a for- est, as well as methods for diversifying trees for the task of syntactic language modeling. We show that our tree interpolation technique outperforms the standard method used in the literature, and that, on this particular task, re- stricting tree contexts in a principled way pro- duces smaller and better forests, with the best achieving an 8% relative reduction in Word Error Rate over an n-gram baseline. 1 Introduction Language Models (LMs) are an essential part of NLP applications that require selection of the most fluent word sequence among multiple hypotheses. The most prominent applications include Automatic Speech Recognition (ASR) and Machine Transla- tion (MT). Statistical LMs formulate the problem as the computation of the model’s probability to gener- ate the word sequence w1, w2, . . . , wm (denoted as wm 1 ), assuming that higher probability corresponds to more fluent hypotheses. LMs are often repre- sented in the following generative form: p(wm 1 ) = m � i=1 p(wi|wi−1 1 ) Note the context space for this function, wi−1 1 is ar- bitrarily long, necessitating some independence as- sumption, which usually consists of reducing the rel- evant context to n−1 immediately preceding tokens: p(wi|wi−1 1 ) ≈ p(wi|wi−1 i−n+1) (1) These distributions are typically estimated from ob- served counts of n-grams wi i−n+1 in the training data. The context space is still far too large1; there- fore, the models are recursively smoothed using lower order distributions. For instance, in a widely used n-gram LM, the probabilities are estimated as follows: ˜p(wi|wi−1 i−n+1) = ρ(wi|wi−1 i−n+1) + (2) γ(wi−1 i−n+1) · ˜p(wi|wi−1 i−n+2) where ρ is a discounted probability2. Note that this type of model is a simple Markov chain lacking any notion of syntax. It is widely accepted that languages do have some structure. Moreover, it has been shown that incorporating syn- tax into a language model can improve its perfor- mance (Bangalore, 1996; Heeman, 1998; Chelba and Jelinek, 2000; Filimonov and Harper, 2009). A straightforward way of incorporating syntax into a language model is by assigning a tag to each word and modeling them jointly; then to obtain the proba- 1O(|V |n−1) in n-gram model with typical order n = 3 . . . 5, and a vocabulary size of |V | = 104 . . . 106. 2We refer …

Content truncated to 500 words