Unsupervised Learning of Dependency Structure for Language Modeling

Unsupervised Learning of Dependency Structure for Language Modeling Jianfeng Gao Microsoft Research, Asia 49 Zhichun Road, Haidian District Beijing 100080 China jfgao@microsoft.com Hisami Suzuki Microsoft Research One Microsoft Way Redmond WA 98052 USA hisamis@microsoft.com Abstract This paper presents a dependency language model (DLM) that captures linguistic con- straints via a dependency structure, i.e., a set of probabilistic dependencies that express the relations between headwords of each phrase in a sentence by an acyclic, planar, undirected graph. Our contributions are three-fold. First, we incorporate the de- pendency structure into an n-gram language model to capture long distance word de- pendency. Second, we present an unsuper- vised learning method that discovers the dependency structure of a sentence using a bootstrapping procedure. Finally, we evaluate the proposed models on a realistic application (Japanese Kana-Kanji conver- sion). Experiments show that the best DLM achieves an 11.3% error rate reduction over the word trigram model. 1 Introduction In recent years, many efforts have been made to utilize linguistic structure in language modeling, which for practical reasons is still dominated by trigram-based language models. There are two major obstacles to successfully incorporating lin- guistic structure into a language model: (1) captur- ing longer distance word dependencies leads to higher-order n-gram models, where the number of parameters is usually too large to estimate; (2) capturing deeper linguistic relations in a language model requires a large annotated training corpus and a decoder that assigns linguistic structure, which are not always available. This paper presents a new dependency language model (DLM) that captures long distance linguistic constraints between words via a dependency structure, i.e., a set of probabilistic dependencies that capture linguistic relations between headwords of each phrase in a sentence. To deal with the first obstacle mentioned above, we approximate long-distance linguistic dependency by a model that is similar to a skipping bigram model in which the prediction of a word is conditioned on exactly one other linguistically related word that lies arbitrarily far in the past. This dependency model is then in- terpolated with a headword bigram model and a word trigram model, keeping the number of pa- rameters of the combined model manageable. To overcome the second obstacle, we used an unsu- pervised learning method that discovers the de- pendency structure of a given sentence using an Expectation-Maximization (EM)-like procedure. In this method, no manual syntactic annotation is required, thereby opening up the possibility for building a language model that performs well on a wide variety of data and languages. The proposed model is evaluated using Japanese Kana-Kanji conversion, achieving significant error rate reduc- tion over the word trigram model. 2 Motivation A trigram language model predicts the next word based only on two preceding words, blindly dis- carding any other relevant word that may lie three or more positions to the left. Such a model is likely to be linguistically implausible: consider the Eng- lish sentence in Figure 1(a), where a trigram model would predict cried from next seat, which does not agree with our …

Content truncated to 500 words