Reducing Parsing Complexity by Intra-Sentence Segmentation based on Maximum Entropy Model

Reducing Parsing Complexity by Intra-Sentence Segmentation based on Maximum Entropy Model Sung Dong Kim, ByoungoTak Zhang, Yung Taek Kim School of Computer Science and Engineering, Seoul National University, Korea {sdkim,btzhang}@scai. snu. ac. kr, ytkim@cse, snu. ac. kr Abstract Long sentence analysis has been a critical problem because of high complexity. This pa- per addresses the reduction of parsing com- plexity by intra-sentence segmentation, and presents maximum entropy model for deter- mining segmentation positions. The model features lexical contexts of segmentation posi- tions, giving a probability to each potential position. Segmentation coverage and accu- racy of the proposed method are 96% and 88% respectively. The parsing efficiency is im- proved by 77% in time and 71% in space. 1 Introduction Long sentence analysis has been a critical problem in machine translation because of high complexity. In EBMT (example-based machine translation), the longer a sentence is, the less possible it is that the sentence has an exact match in the translation archive, and the less flexible an EBMT system will be (Cranias et al., 1994). In idiom-based ma- chine translation (Lee, 1993), long sentence parsing is difficult because more resources are spent during idiom recognition phase as sen- tence length increases. A parser is often un- able to analyze long sentences owing to their complexity, though they have no grammatical errors (Nasukawa, 1995). In English-Korean machine translation, idiom-based approach is adopted to overcome the structural differences between two lan- guages and to get more accurate translation. The parser is a chart parser with a capabil- ity of idiom recognition and translation, which is adapted to English-Korean machine trana- lation. Idioms are recognized prior to syn- tactic analysis and the part of a sentence for an idiom takes an edge in a chart (Winograd, 1983). When parsing long sentences, an am- biguity of an idiom's range may cause more edges than the number of words included in the idiom (Yoon, 1994), which increases pars- ing complexity much. A parser of practical machine translation system should be able to analyze long sentences in a reasonable time. Most context-free parsing algorithms have O(n 3) parsing complexities in terms of time and space, where n is the length of a sen- tence (Tomita, 1986). Our work is moti- vated by the fact that parsing becomes more efficient, if n becomes shorter. This paper deals with the problem of parsing complex- ity by way of reducing the length of sentence to be analyzed. This reduction is achieved by intra-sentence segmentation, which is distinguished from inter--sentence segmen- tation that is used for text categorization (Beeferman et al., 1997) or sentence boundary identification (Palmer and Hearst, 1997) (Rey- nar and Ratnaparkhi, 1997). Intra-sentence segmentation plays a role as a preliminary step to a chart-based, context-free parser in English-Korean machine translation. There have been several methods for reducing parsing complexities by intra- sentence segmentation. In (Lyon and Frank, 1995)(Lyon and Dickerson, 1997), they took advantage of the fact that the declarative sentences almost always consist of three seg- ments: [pre-subject …

Content truncated to 500 words