Conventional parsers try to identify syntactic information completely. These parsers encounter difficulties when processing unrestricted texts, because of ungrammatical 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 syntactic information efficiently and reliably from unrestricted texts by sacrificing completeness and depth of analysis, and relying on local information to resolve ambiguities.
Rule-based methods, used in partial parsing techniques via finite state machines, have several advantages over statistical counterparts in that the resulting knowledge is more compact and comprehensible to human developers and results are more easily integrated into existing hand-built symbolic systems. As would be expected, manually building underlying knowledge is both a labor-intensive task and prone to have inconsistencies. Recently, there have been several studies on automatically extracting rules from large-scale corpora by using several machine learning techniques. But their work was restricted to the chunking task, especially finding non-recursive and non-overlapping noun phrases.
In this dissertation, we present a method of automatically extracting partial parsing rules from a tree-annotated corpus using the decision tree method. Our goal is to extract rules with higher accuracy and broader coverage. We define the partial parsing rules as those that can establish the structure of a substring in an input sentence deterministically. This decision can be considered as a classification that, 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 with features of contextual and lexical information. In addition, we use negative evidence, as well as positive evidence, to gain higher accuracy. For general recursive phrases, all possible substrings in a parse tree are taken into account by extracting evidence recursively from a parse tree in a training corpus. We induce partial parsing rules from the decision tree, and, to retain only those rules that are accurate, verify each rule through cross-validation.
In many cases, several different structures are assigned to the same substring in a tree-annotated corpus. Substrings for coordination and compound nouns are typical examples of such ambiguous cases in Korean. These ambiguities can prevent us from extracting partial parsing rules that cover the substrings with more than one substructure and, consequently, can cause the result of partial parsing to be limited to a relatively shallow depth. In this work, we address this problem by merging substructures with ambiguity using an underspecified representation. This underspecification Ieads to broader coverage without deteriorating either the determinism or the precision of partial parsing.
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. It is easy to understand; it can be easily modified; and it can be selectively added to or deleted from the grammar. Partial parsing with this grammar processes an input sentence deterministically using longest-match heuristics. The partial parsing rules we acquire are then recursively applied to an input sentence. To verify the effectiveness of the proposed partial parser, we applied the parser to text chunking of Korean. Our experiments showed that the proposed partial parser using the automatically extracted rules is not only accurate and efficient, but also achieves reasonable coverage for Korean.
구문 분석은 자연 언어 처리 응용 시스템의 주요 요소 중 하나로, 입력 문장의 구문 구조를 밝혀내는 작업을 의미한다. 자연 언어는 정해진 구문 형식과 의미가 있는 인공 언어와 달리 매우 다양하게 표현되며, 사용되는 어휘도 제한되어 있지 않고, 비정형화된 문장도 쓰인다. 자연적으로 발생 가능한 모든 문장에 대한 문법을 기술하는 것은 매우 어려우며, 길이가 긴 문장이나 비문법적인 문장 역시 구문 분석이 용이하지 않다. 이러한 문제점을 해결하기 위한 한 방법으로 구조적 중의성이 적은 부분에 대한 분석만을 수행하는 부분 구문 분석에 대한 연구가 활발히 진행되고 있다. 부분 구문 분석은 영어의 전치사구의 부착 문제와 같이 구조적 중의성을 급증시키는 부분에 대한 처리를 배제하고, 다소 명확한 구조만을 빠르고 정확하게 인식하는 것을 목적으로 한다. 유한 상태 변환기를 이용한 부분 구문 분석 기법에서 주로 사용된 규칙 기반 방식은 얻어진 지식이 좀더 간결하고 사람이 이해하기 쉬우며 수정이 용이하다는 장점이 있다. 또한 기존에 구축된 심볼릭 시스템에 쉽게 적용이 가능하며 확장이 용이하고 보다 효율적으로 시스템을 구축할 수 있다. 그러나 대부분 필요한 지식을 수동으로 구축하고 있다. 따라서 지식 구축에 많은 시간과 비용이 필요하고, 대량의 지식을 일관성 있게 작성하기 어렵다. 최근에는 기존에 구축된 대량의 코퍼스로부터 규칙을 추출하려는 연구들이 진행되고 있다. 하지만 이러한 연구들은 부분 구조들의 경계, 특히 주요한 구절의 핵심 부분인 기반구(base phrase, chunk)의 경계를 인식하는 데에 집중해 있으며, 그 범위도 기반 명사구나 기반 동사구, 주어, 목적어 등으로 한정되어 있다. 본 논문에서는 구문 구조 부착 코퍼스로부터 부분 구문 분석 규칙을 자동으로 추출하는 방법을 제안한다. 본 논문에서 부분 구문 분석은 부분 트리들의 경계만이 아니라 그 내부 구조까지 찾고자 하며, 기존의 전체 구문 분석기(full parsing)에 가능한 한 근접하도록 분석하는 것을 목적으로 한다. 본 논문에서는 부분 구문 분석 규칙을 입력 문장에서 부분 태그열의 구조를 결정적으로(deterministically) 분석하기 위한 것으로 정의한다. 이는 입력 문장의 부분 태그열에 대해 구문 구조 부착 코퍼스에서 발생한 가능한 모든 부분 구조 중 하나로 분류(classification)하는 과정으로 간주할 수 있다. 이러한 분류를 위하여 문맥 정보와 어휘 정보를 자질로 하여 결정 트리 기법을 이용한다. 또한 긍정적 증거뿐만 아니라 부분 태그열에 대해 적용된 부분 구조가 없는 부정적 증거(negative evidence)도 고려하여 보다 정확한 규칙을 추출하고자 한다. 일반적인 재귀적 구절을 인식하기 위하여 학습 코퍼스의 구문 구조에 대해 재귀적으로 증거를 추출함으로써 구문 구조에 대해 가능한 모든 부분 태그열을 고려한다. 이렇게 구성된 결정 트리로부터 부분 구문 분석 규칙을 추출하며, 정확성이 떨어지는 규칙을 여과하기 위하여 학습 코퍼스에 대한 교차 검증 기법(cross-validation)을 통하여 추출된 규칙을 검증하였다. 구문 분석 구조 부착 코퍼스에서 같은 부분 태그열에 대해 서로 다른 부분 구조가 적용된 경우가 많이 발생한다. 한국어에서 병렬 구조나 복합 명사의 경우가 이러한 중의성을 지닌 예이다. 이러한 중의성은 둘 이상의 서로 다른 구조가 적용된 부분 태그열에 대한 규칙 추출을 어렵게 하며, 따라서 부분 구문 분석의 결과를 얕은 깊이로 한정시킨다. 본 논문에서는 이러한 문제를 해결하기 위하여 중의성을 지닌 부분 구조를 비명확화(underspecification)를 통하여 병합하고자 한다. 이를 통해 부분 구문 분석의 효율성을 해치지 않고 정확성을 떨어뜨리지 않으면서 적용 범위를 향상시킬 수 있다. 추출된 규칙은 문맥 정보와 어휘 정보를 지닌 구구조 문법과 유사한 형태를 지니지만 깊이 1 이상의 구조를 형성할 수 있다. 또한 이해하기 쉽고 수정 및 추가, 삭제가 용이하다. 추출된 규칙을 이용한 부분 구문 분석에서는 입력 문장을 최장 일치 기법을 이용하여 결정적으로 처리한다. 또한 입력 문장에 대해 재귀적으로 동작함으로써 그 결과가 전체 구문 분석과 유사하게 된다. 본 논문의 부분 구문 분석기를 검증하기 위하여 최근 많은 연구가 되고 있는 기반구 인식에 응용하였다. 자동 추출된 규칙을 이용한 부분 구문 분석기의 성능을 살펴보기 위한 실험을 통해 추출된 규칙이 한국어에 대해 정확하고 효율적으로 동작하며, 적절한 적용 범위를 지님을 확인할 수 있었다.
