단어의 통사분석을 위한 계산모형

Abstract

과거의 구조주의와 유사하게 한국어 형태론에 관한 기존의 전산 모형은 선형적인 것들로 단어 내부구조 형성보다 형태소의 분리 문제나 연쇄에만 관심을 두고 있다. 이러한 선형적 전산모형을 구문 분석 과정과 통합적으로 고려할 경우, 구문 단위 요소의 형성을 위해 형태소 분석 결과를 묶어야만 하는 추가적인 과정이 필요할 뿐만 아니라 의미적 직관성을 얻기도 어려웠다. 본 논문에서는 형태소 분리와 구문 요소 형성뿐만 아니라 단어의 구조 분석까지도 통합적으로 다룰 수 있는 단어통사론적 시각에 따른 전산 모형을 제안한다. 본 논문에서 제안하고 있는 전산 모형은 중재부와 같은 비효율의 원인이 되는 추가적인 부문이 필요 없다. 또한 문장 통사 분석기에 비가시적이거나 부분 가시적이다. 즉, 문장 통사 분석기는 개개의 형태소들은 참조할 필요가 없고 자질 제약이나 자질 연산에 의해 형태소들을 묶어 형성한 최대 단위(문장 통사부 입장에서는 최소 단위, 문법 단위, 혹은 원자 단위)만을 참조하면 된다. 본 논문의 궁극적인 목표는 자연언어처리 응용에 적용할 수 있을 정도의 계산론적으로 충분히 효율적이고, 언어학 분야에서 모의실험 도구로 사용할 수 있는 알고리즘을 설계하고 개발하는 것이다. 제안하는 단어의 계층적 구조 분석 알고리즘이 근간으로 하고 있는 형태부의 모습은 자질을 갖춘 형태소 목록과 형태론적 변형을 다루기 위한 규칙, 그리고 형태소 목록을 이용한 단어의 형성을 위한 규칙을 갖는 모습이다. 형태소 목록은 TRIE 자료구조의 사전에 음절 단위로 저장되고, 사전은 언어정보의 제공과 함께 형태소 분리 역할을 담당한다. 형태소 분리와 형태론적 변형을 동시에 다루기 위한 철자규칙은 2단계 형태론의 형식화를 사용하고 있으며, 초기 2단계 형태론과는 달리 형태소 결합의 합법성 여부에는 관여하지 않고 단지 변형이 발생한 표층형 단어를 어휘형으로 환원하는 일만을 수행한다. 추가적으로 형태론적 변형에 따른 범주 문맥을 반영하기 위해 기능성 구분문자를 제안하고, 2단계 규칙의 저수준의 표현인 유한상태 변환기에서 2단계규칙들 간의 의존성을 반영하기 위해 두 종류의 상관성 제약을 제안한다. 제한하는 전산 모형은 형태소들과 어휘구들간의 계층관계를 파악하기 위해 단어 형성 규칙으로 문맥자유문법 규칙을 사용하고 있으며, 파싱 알고리즘으로는 GLR 알고리즘에 기반한 방법을 사용한다. GLR 알고리즘은 통상적으로 단위(단어)의 경계가 분명한 문장의 통사 구조 분석에 사용되는 알고리즘이므로 이를 단위(형태소)의 경계에 대해 다중의 해석을 갖는 단어의 내부 구조 분석에 적용하기 위해서는 알고리즘을 변경해야만 한다. 이를 위해 본 논문에서는 음절 단위로 TRIE 노드를 전이함과 동시에 유한상태 정점을 통과하여 해석된 결과를 입력으로 받아 그래프 구조화 스택을 완성해나가는, 넓이-우선 탐색이면서 서로 교호적으로 동작하는 알고리즘을 제시한다. 본 논문에서 전체에 걸쳐 유지되고 있는 형태론적 관점은 생성문법의 변형은 파생 형태론에서 사용될 수 없다고 주장하는 약어휘론적 가설이다. 약어휘론적 가설은 파생만이 형태부에서 발생하는 것이고 파생과 반대 현상인 굴절은 문장 통사부에서 발생한다는 입장이다. 그러나 약어휘론적 입장이든, 강어휘론적 입장이든, 심지어 선형적 입장일지라도 제안하는 모형은 사용자가 정의한 단어 형성 규칙에 따라 동작한다. 따라서 제안하는 모형은 단어 형성 규칙을 위한 규칙 분석기를 내장하고 있다. 제안하는 모형은 자질 구조와 자질구조에 관한 논리적 연산 장치를 가지고 있지 않다. 그러나 약간의 알고리즘의 수정만으로도 자질 기반 접근 방법으로 변환이 가능하다는 것을 보이기 위해, 본 논문에서는 알고리즘을 변경하는 방법과 구구조 기반 접근법, 자질 기반 접근법에 관한 두 종류의 사례를 제시한다. 마지막으로 제안하는 모형의 효율성을 입증하기 위해 약 96만 어절을 분석하는데 소요된 시간에 관한 평가 결과를 제시한다.; Similarly to the past structuralism, up to now computational models for Korean morphology have been linear in that it deals with only segmentation or concatenation of morphemes rather than formation of the internal structure of a word. When integrating these linear models with syntax analysis, it requires an additional interface component between the morphological component and the syntactic component to bind morphemes into sentence constituents. Furthermore, the linear model is not semantically intuitive. Based on the word-syntactical point of view, this thesis proposes an integrated computational model that deals with morpheme segmentation, formation of syntactic element (sentence constituent), and even internal structure of word. The computational model presented in this thesis need not be equipped with additional components (e.g., interface component) caused to be inefficient. Moreover, it is invisible or partially visible to sentence-syntactic parser. In other words, the sentence-syntactic parser need not access to individual morphemes, accesses only maximal units (i.e., in a sentence-syntactic point of view, minimal, grammatical, or atomic units) formed through combining morphemes together by feature constraints and operations. The final goal of this thesis is to design and develop an algorithm that is computationally efficient enough to apply it to natural language applications, and is able to be utilized as a simulation tool in the area of linguistics. The morphological component that the proposed algorithm for the syntactic structure analysis of word is based on consists of three elementary features, the list of morphemes permitting feature structures, the rules to deal with morphological alternation, and the rules for word formation. The list of morphemes is conserved by the syllable in a single dictionary organized as the TRIE data structure, and the dictionary provides with some linguistic information and plays the role of segmentation of morphemes. Spelling rules to deal with morpheme segmentation and morphological alternation problems are based on the two-level formalism. Differently from early two-level formalism, they are not concerned with the estimation of the legitimacy of connection between morphemes, but carry out only restoration of morphologically alternated surface form to lexical form. In addition, functional diacritics are proposed to incorporate categorial context into the two-level formalism, and two sorts of reciprocity constraints are proposed to catch the dependency between two-level rules at finite-state transducer, which is the low-level representation to implement its rules. The proposed computational model uses context-free grammar as word formation rules to investigate hierarchical relations between morphemes and lexical phrases, and uses the method based on GLR algorithm as its parsing algorithm. Since the GLR parsing algorithm has typically been used for syntactic analysis of sentence having explicit boundary of units (words), it must be revised to be applied to the analysis of internal structure for word having multiple interpretations for boundary of units (morphemes). To achieve this purpose, this thesis presents the algorithm executed interleavingly, where at each step, by a breath-first search, a syllable fully traverses the nodes in multiple paths of TRIE dictionary and passes through the all vertices connected by matched edge paths in finite-state transducer, and then makes up its own graph-structured stack from their found interpretations. The morphological point of view throughout this thesis is the weak lexicalist hypothesis which says that lexical transformations in generative grammar cannot be used in derivational morphology, conversely, only derivation takes place in morphological component, and inflection, as opposed to derivation, takes place in sentence-syntax. However, whether the weak lexicalist, the strong lexicalist, or even linear one, the proposed model is executed according to the word formation rules that user defines, and therefore the proposed model has a rule-parser for word formation rules. The proposed model does not have mechanism for feature structures and logical operations on feature structures. However, to show that it is able to be migrated toward the feature-based approach by only simple modification of algorithm, this thesis presents how to modify it and two sorts of samples about phrase-structured approach and feature-based approach. Finally, in order to prove the efficiency of the proposed model, this thesis presents the evaluation results of elapsed time in analysis for about 966,000 words.