An Unsupervised Parameter Estimation Algorithm for a Generative Dependency N-gram Language Model

International Joint Conference on Natural Language Processing, pages 516–524, Nagoya, Japan, 14-18 October 2013. An Unsupervised Parameter Estimation Algorithm for a Generative Dependency N-gram Language Model Chenchen Ding and Mikio Yamamoto Department of Computer Science University of Tsukuba 1-1-1 Tennodai, Tsukuba, 305-8573, Japan {tei@mibel.,myama@}cs.tsukuba.ac.jp Abstract We design a language model based on a generative dependency structure for sen- tences. The parameter of the model is the probability of a dependency N-gram, which is composed of lexical words with four kinds of extra tags used to model the dependency relation and valence. We fur- ther propose an unsupervised expectation- maximization algorithm for parameter es- timation, in which all possible dependency structures of a sentence are considered. As the algorithm is language-independent, it can be used on a raw corpus from any lan- guage, without any part-of-speech annota- tion, tree-bank or trained parser. We con- ducted experiments using four languages: English, German, Spanish and Japanese. The results illustrate the applicability and the properties of the proposed approach. 1 Introduction Statistical language models are a fundamental component of speech recognition systems, ma- chine translation systems, and so forth. Presently, the N-gram language model is the most widely used approach. This model focuses on sequences of neighboring lexical words (Fig. 1), and uses the probabilities of these sequences as model parame- ters. Due to the full lexicalization of the N-gram language model, local features of word sequences can be well modeled. However, an N-gram lan- guage model cannot capture relatively long-range features, because it regards a sentence as a flat string and ignores its structure. Figure 1: The N-gram language model treats the English sentence “all things pass” composed of (all, things) and (things, pass), for N = 2. Figure 2: The constituency-based parsing (A) and the dependency-based parsing (B)1 for the English sentence “all things pass”. On the other hand, revealing the structure of a sentence is the task of parsing, which is based on linguistically oriented formulations and focuses on generating the likeliest structure for a given sen- tence. For this purpose, there are constituency- based and dependency-based formulations (Fig. 2). The former organizes continuous word se- quences in a hierarchy of small range to large range groups with linguistically oriented labels; the latter links words with dependency relations2. Figure 3: All possible dependency structures for the English sentence “all things pass”. (I) is the linguistically correct structure while the original N-gram language model handles the sentence as if it has the structure labeled (II). We consider all these structures in our unsupervised estimation algorithm. In this paper, we focus on introducing sentence structure into language modeling. We propose a generative dependency N-gram language model that integrates a generative dependency structure of a sentence into the original N-gram language model. We prefer the dependency-based formula- 1For the illustrations in this paper, we use the follow- ing representation to show the dependency structure. If two aligned words are on different levels, the upper one is the head of the lower one; if they …

Content truncated to 500 words