Human languages and derive algorithms with which the language understanding may be automated through machines. The task of searching for such computational methods is a process of identifying constructive accounts of linguistic phenomena. Languages are more than what qualitative linguistic descriptions can provide.
This thesis investigates a quantitative methodology to compute natural language phenomena. The particular line that this thesis represents is commonly known as probabilistic or empirical approaches The basic tenet is that natural language expressions are ambiguous due to the lack of information. Language processing is roughly equivalent to discovering the missing information that is usually presumed by the speaker and listener of natural language expressions. The presumed information may soon deplete making an exact interpretation of the received expression by a listener impossible. When this happens, the expression becomes ambiguous. For the most language understanding systems the problem of information deficiency is even worse because the representation and construction of knowledge are not provided with realistic algorithms. Probabilistic approaches have been motivated to overcome the uncertainty caused by missing information through weighted decisions.
In particular, this thesis addresses the two types of ambiguities in natural language sentences. One is syntactic ambiguity in which syntactic relations are not certain. The other is lexical ambiguity of polysemous words in which the meaning of words is not certain. For the syntactic ambiguity problem, probabilistic Recursive Transition Network (PRTN) as a probabilistic grammar representation is developed by supplying an algorithm to estimate parameters and an algorithm to identify best scored syntactic results. The establishment of probabilistic Recursive Transition Network is the second effort following Kupiec's work (1992) to extend the probabilistic CFG that used to work only on Chomsky Normal Form to the CFGs in general representation.
The thesis also suggests a chart based reestimation algorithm for the PRTN. Inside algorithm and Earley's algorithm are compared as best parse parsing methods. Inside algorithm was turned out to be better than Earley's for sufficiently short sentences and sufficiently large grammars.
For the second problem of lexical ambiguity, Collocation map is defined and its underlying utilities are developed. Collocation map is an application model of sigmoid Bayesian network where each node of the network corresponds to a word and edges represent the dependency between words. Well known methods to approximate the cooccurrence dependency among words are Markov and n-gram models. The methods suffer data sparseness problem that addresses the situation where the approximation is not possible or is overestimated, which is largely due to the insufficient training data.
The nice feature of Bayesian networks is that we can compute any conditional distribution among the nodes (words). The conditional distribution can be used in measuring the cooccurrence similarity of the words. In this thesis an algorithm to acquire word sense from Collocation map is defined and the use of Collocation map to overcome data sparseness problem is also illustrated.
The core of the thesis regarding Collocation map is the development of an efficient algorithm to compute the conditional densities for sigmoid Bayesian networks. This is important because the time complexity of computing on Bayesian networks is too high to be practical in large applications. The efficient algorithm is a mixture of two well known algorithms: node reduction and Gibbs sampling methods.
The thesis is the result of formal derivation of two frameworks for computing syntactic and lexical relations with probabilistic scores. Along with the introduction of the algorithms constituting the frameworks, extensive experimental arguments are also provided to support the validity of the methods.
자연언어처리는 인간의 언어에 대한 기본적인 이해를 하기위한 혹은 기계적인 처리를 위한 계산적 방법을 지칭한다. 그러한 계산적 방법을 찾는 것은 언어현상에 대한 구현가능한 모델을 찾아내는 작업이다. 자연언어의 현상을 정성적 설명만으로 충분히 설명하기는 쉽지 않다.
본 논문은 자연언어를 처리하는데 수량적인 접근방법에 관한 결과이다. 논문의 내용은 최근 관심이 모아지고 있는 확률적 혹은 실험적 접근 방법에 속한다. 확률적 접근의 기본 동기는 자연언어 표현의 모호성에 기초하고 있다. 자연언어 표현의 모호성은 정보의 부족에서 발생한다. 자연언어처리의 내용은 가용한 정보를 이용해서 모호성을 줄여가는 과정으로 되어있다. 모호성을 줄이기 위한 정보는 자연언어 개별 표현에 있다기 보다 표현을 주고 받는 사람간에 가정되어 있다. 이러한 정보도 불완전하기 마련이고 이럴경우 표현의 모호성이 해결되지 않은체 이해될 수 밖에 없다. 모호한 표현에 대한 이해는 확률적 판단에 의해서 일차적으로 이루어 질 수 있다.
본 논문은 자연언어 표현의 모호성중에서도 구문의 모호성과 단어의미의 모호성을 해결하기 위한 수학적 모델을 개발하였다. 구문의 모호성이란 자연언어 문장을 구문적으로 분석하는 과정에서 구문적 요소간의 관계가 불확실한 경우를 말한다. 단어의미의 모호성이란 단어의 의미가 여러가지일 경우를 말한다. 구문의 모호성을 해결하기 위해서 확률재귀천이망을 개발하였다. 재귀천이망을 학습시키는 알고리듬과 최적의 구문결과를 찾는 탐색알고리듬을 정의하였다.
확률재귀천이망의 탐색을 위한 인사이드알고리듬과 Earley의 알고리듬을 비교한 결과 인사이드 알고리듬이 짧은 문장 혹은 커다란 문법에 대해서 Earley보다 우수하다는 결과를 얻었다.
단어의미의 모호성은 문장에서 일아나는 주변단어에 의해서 어느 정도 해결될 수 있다. 단어간의 공기의존관계를 계산하는 방법으로 마코프모델이나 n-그램과 같은 것이 있으나 통계자료의 부족으로 계산이 불가능하거나 계산값이 불안전한 문제점이 있다. 이러한 문제점을 극복하기 위하여 베이지언넷에 기반한 공기지도를 개발하였다. 베이지언넷은 노드들 간의 어떠한 조건확률도 계산을 가능하게 하는 강력한 기능을 제공하고 있으며, 공기지도의 경우 임의의 단어들간의 공기관계의 계산을 가능하게 한다. 공기지도를 이용한 응용으로서, 단어의 의미자동추출 알고리듬을 정의하였고 공기지도가 자료부족의 문제를 해결할 수 있음을 실험을 통해서 보였다.
공기지도에서 확률값을 계산하는 것은 많은 계산을 요구한다. 이 계산양을 줄이기 위해서 효율적인 계산방법을 제안하였다. 넷워크의 노드를 줄임으로써 계산하는 방법과 샘플링을 해서 계산하는 방법을 결합한 것으로 실험을 통해서 250개이상의 노드를 가진 넷워크에서 그 효율성을 검증하였다.
본 논문은 자연언어처리에서 구문간 그리고 단어간의 확률적 관계를 계산하는 두개의 수학적 방법을 개발한 결과에 관한 것이다. 여러개의 알고리듬과 함께 각각의 특성을 규명하기 위한 실험적 논증을 제시하였다.
