A Method of Incorporating Bigram Constraints into an LR Table and Its Effectiveness in Natural Language Processing

II II II II II II II II II II A Method of Incorporating Bigram Constraints into an LR Table and Its Effectiveness in Natural Language Processing i Hiroki Imai and Hozumi Tanaka Graduate School of Information Science and Technology Tokyo Institute of Technology 2-12-10-okayama, Meguro, Tokyo 152 Japan {imai, tanaka}@cs, t itech, ac. jp Abstract In this paper, we propose a method for con- structing bigram LR tables by way of incor- porating bigram constraints into an LR table. Using a bigram LR table, it is possible for a GLR parser to make use of both big'ram and CFG constraints in natural language process- ing. Applying bigram LR tables to our GLR method has the following advantages: (1) Language models utilizing bigzam LR ta- bles have lower perplexity than simple bigram language models, since local constraints (hi- gram) and global constraints (CFG) are com- bined in a single bigram LR table. (2) Bigram constraints are easily acquired from a given corpus. Therefore data sparseness is not likely to arise. (3) Separation of local and global constraints keeps down the number of CFG rules. The first advantage leads to a reduction in complexity, and as the result, better perfor- mance in GLR parsing. Our experiments demonstrate the effectiveness of our method. 1 Introduction In natural language processing, stochastic language models are commonly used for lexical and syntactic disambiguation (Fujisaki et al., 1991; Franz, 1996). Stochastic language models are also helpful in re- ducing the complexity of speech and language pro- cessing by way of providing probabilistic linguistic constraints (Lee, 1989). N-gram language models (Jelinek, 1990), includ- ing bigram and trigram models, are the most com- monly used method of applying local probabilis- tic constraints. However, context-free grammars (CFGs) produce more global linguistic constraints than N-gram models. It seems better to combine both local and global constraints and use them both concurrently in natural language processing. The reason why N-gram models are preferred over CFGs is that N-gram constraints are easily acquired from a given corpus. However, the larger N is, the more serious the problem of data sparseness becomes. CFGs are commonly employed in syntactic pars- ing as global linguistic constraints, since many eifi- cient parsing algorithms are available. GLR (Gen- eralized LR) is one such parsing algorithm that uses an LR table, into which CFG constraints are pre- compiled in advance (Knuth, 1965; Tomita, 1986). Therefore if we can incorporate N-gram constraints into an LR table, we can make concurrent use of both local and global linguistic constraints in GLR parsing. In the following section, we will propose a method that incorporates bigram constraints into an LR ta- ble. The advantages of the method are summarized as follows: First, it is expected that this method produces a lower perplexity than that for a simple bigram lan- guage model, since it is possible to utilize both local (bigram) and global (CFG) constraints in the LR table. We will evidence this reduction in perplexity by considering states in an LR table …

Content truncated to 500 words