Compound noun decomposition using a Markov model

MT Summit VII Sept.1999 Compound Noun Decomposition Using a Markov Model Jongwoo Lee Department of Computer Engineering Seoul National University. Korea jongwoo@nova.snu.ac.kr Byoung-Tak Zhang Department of Computer Engineering Seoul National University, Korea btzhang@comp.snu.ac.kr Yung Taek Kim Department of Computer Engineering Seoul National University, Korea ytkim@comp.snu.ac.kr Abstract A statistical method for compound noun decompo- sition is presented. Previous studies on this prob- lem showed some statistical information are helpful. But applying statistical information was not so sys- temic that performance depends heavily on the algo- rithm and some algorithms usually have many sep- arated steps. In our work statistical information is collected from manually decomposed compound noun corpus to build a Markov model for composition. Two Markov chains representing statistical information are assumed independent: one for the sequence of partic- ipants' lengths and another for the sequence of par- ticipants ' features. Besides Markov assumptions, least participants preference assumption also is used. These two assumptions enable the decomposition algorithm to be a kind of conditional dynamic programming so that efficient and systemic computation can be per- formed. When applied to test data of size 5027, we obtained a precision of 98.4%. 1 Introduction Generally, compound noun takes the form of succes- sive appearance of elementary nouns. Decomposition of compound nouns is an important problem in nat- ural language processing (NLP), especially in oriental languages such as Korean, Chinese, Japanese in that there can be no intervening blank between participant nouns. It is more complicated in Korean case, since most Korean words are represented by phonetic alpha- bets. To analyze the meaning of a Korean compound noun, its decomposition is necessary. Only with dictionary lookup, several compositions of a compound noun are possible. Finding all possi- ble candidate compositions [3] is of high cost since the number of compositions increases exponentially in proportion to the length of the compound noun. Although the length of many compound noun is usu- ally manageable, some heuristic search is required in order to avoid full search, for search involves dictio- nary lookup. Even after all the candidates possible are found, semantically correct one must be selected by some semantic resolver. If heuristics are adopted, selection choices can be made before complete partic- ipants of a candidate are searched. Some heuristics on this problem have been studied be- fore. One of the simplest heuristics is longest match first heuristics. With this method, decomposition points are searched from left to right and the next decom- position point is the end point of longest elementary noun starting at the previous decomposition point. On the other hand, there is a different method in which the most probable decomposition point is found in the whole string, and then this decomposition is performed on the substrings recursively [2]. If algo- rithms like these did not have a backtracking mecha- nism they would frequently fall in local maxima, re- sulting in low accuracy. Some flexible heuristics that reduces the number of search paths and partially al- lows backtracking are studied [5, 2, 9]. …

Content truncated to 500 words