Hierarchical Non-Emitting Markov Models

Hierarchical Non-Emitting Markov Models Eric Sven Ristad and Robert G. Thomas Department of Computer Science Princeton University Princeton, NJ 08544-2087 {ristad, rgt )©cs. princeton, edu Abstract We describe a simple variant of the inter- polated Markov model with non-emitting state transitions and prove that it is strictly more powerful than any Markov model. Empirical results demonstrate that the non-emitting model outperforms the inter- polated model on the Brown corpus and on the Wall Street Journal under a wide range of experimental conditions. The non- emitting model is also much less prone to overtraining. 1 Introduction The Markov model has long been the core technol- ogy of statistical language modeling. Many other models have been proposed, but none has offered a better combination of predictive performance, com- putational efficiency, and ease of implementation. Here we add hierarchical non-emitting state tran- sitions to the Markov model. Although the states in our model remain Markovian, the model itself is no longer Markovian because it can represent unbounded dependencies in the state distribution. Consequently, the non-emitting Markov model is strictly more powerful than any Markov model, in- cluding the context model (Rissanen, 1983; Rissa- nen, 1986), the backoff model (Cleary and Witten, 1984; Katz, 1987), and the interpolated Markov model (Jelinek and Mercer, 1980; MacKay and Peto, 1994). More importantly, the non-emitting model consis- tently outperforms the interpolated Markov model on natural language texts, under a wide range of experimental conditions. We believe that the su- perior performance of the non-emitting model is due to its ability to better model conditional inde- pendence. Thus, the non-emitting model is better able to represent both conditional independence and long-distance dependence, ie., it is simply a better statistical model. The non-emitting model is also nearly as computationally effÉcient and easy to im- plement as the interpolated model. The remainder of our article consists of four sec- tions. In section 2, we review the interpolated Markov model and briefly demonstrate that all inter- polated models are equivalent to some basic Markov model of the same model order. Next, we introduce the hierarchical non-emitting Markov model in sec- tion 3, and prove that even a lowly second order non-emitting model is strictly more powerful than any basic Markov model, of any model order. In section 4, we report empirical results for the inter- polated model and the non-emitting model on the Brown corpus and Wall Street Journal. Finally, in section 5 we conjecture that the empirical success of the non-emitting model is due to its ability to bet- ter model a point of apparent independence, such as may occur at a sentence boundary. Our notation is as follows. Let A be a finite alpha- bet of distinct symbols, [A[ = k, and let z T 6 A T denote an arbitrary string of length T over the al- phabet A. Then z~ denotes the substring of z T that begins at position i and ends at position j. For con- venience, we abbreviate the unit length substring z~ as …

Content truncated to 500 words