Automatic Partial Parsing Rule Acquisition Using Decision Tree Induction

Automatic Partial Parsing Rule Acquisition Using Decision Tree Induction⋆ Myung-Seok Choi, Chul Su Lim, and Key-Sun Choi Korea Advanced Institute of Science and Technology, 373-1 Guseong-dong, Yuseong-gu, Daejeon 305-701, Republic of Korea {mschoi, cslim}@kaist.ac.kr kschoi@cs.kaist.ac.kr Abstract. Partial parsing techniques try to recover syntactic informa- tion efficiently and reliably by sacrificing completeness and depth of anal- ysis. One of the difficulties of partial parsing is finding a means to extract the grammar involved automatically. In this paper, we present a method for automatically extracting partial parsing rules from a tree-annotated corpus using decision tree induction. We define the partial parsing rules as those that can decide the structure of a substring in an input sentence deterministically. This decision can be considered as a classification; as such, for a substring in an input sentence, a proper structure is chosen among the structures occurred in the corpus. For the classification, we use decision tree induction, and induce partial parsing rules from the decision tree. The acquired grammar is similar to a phrase structure grammar, with contextual and lexical information, but it allows building structures of depth one or more. Our experiments showed that the pro- posed partial parser using the automatically extracted rules is not only accurate and efficient, but also achieves reasonable coverage for Korean. 1 Introduction Conventional parsers try to identify syntactic information completely. These parsers encounter difficulties when processing unrestricted texts, because of un- grammatical sentences, the unavoidable incompleteness of lexicon and grammar, and other reasons like long sentences. Partial parsing is an alternative technique developed in response to these problems. This technique aims to recover syn- tactic information efficiently and reliably from unrestricted texts by sacrificing completeness and depth of analysis, and relying on local information to resolve ambiguities [1]. Partial parsing techniques can be roughly classified into two groups. The first group of techniques involves partial parsing via finite state machines [2,3,9,10]. These approaches apply the sequential regular expression recognizer to an in- put sentence. When multiple rules match an input string at a given position, ⋆ This research was supported in part by the Ministry of Science and Technology, the Ministry of Culture and Tourism, and the Korea Science and Engineering Foundation in Korea. R. Dale et al. (Eds.): IJCNLP 2005, LNAI 3651, pp. 143–154, 2005. c ⃝ Springer-Verlag Berlin Heidelberg 2005 144 M.-S. Choi, C.S. Lim, and K.-S. Choi the longest-matching rule is selected. Therefore, these parsers always produce a single best analysis and operate very fast. In general, these approaches use a hand-written regular grammar. As would be expected, manually writing a grammar is both very time consuming and prone to have inconsistencies. The other group of partial parsing techniques is text chunking, that is, recog- nition of non-overlapping and non-recursive cores of major phrases (chunks), by using machine learning techniques [4,7,8,13,15,17]. Since Ramshaw and Mar- cus [15] first proposed formulating the chunking task as a tagging task, most chunking methods have followed this word-tagging approach. In base noun phrase chunking, for instance, each word …

Content truncated to 500 words