Warning: main(/home/gurugail/header.php) [function.main]: failed to open stream: No such file or directory in /home/gurugail/NLP/page.html on line 23
Warning: main(/home/gurugail/header.php) [function.main]: failed to open stream: No such file or directory in /home/gurugail/NLP/page.html on line 23
Warning: main() [function.include]: Failed opening '/home/gurugail/header.php' for inclusion (include_path='.:/usr/local/lib/php') in /home/gurugail/NLP/page.html on line 23
|
커뮤니티 게시판 |
|
A.I Section
자연어 처리 |
|
GGOP
GGOP 소개
|
| 구문 해석(Syntactic analysis) | |
|
작성 |
정현철 (lifegear@hanmail.net) |
|
작성 날짜 |
2001.09.03 |
|
개요 |
... |
|
|
|
자연언어의 문장은 발화 또는 표기된 시점에서는 단어의 나열로 1차원적이다. 구문해석이란 바로 자연언어의 구조를 문법규칙에 기초하여 복원하는 처리를 말하는 것이다. 자연어처리의 최초의 시도가 영어권 나라이며, 영어는 구조가 중요한 역할을 하기 때문에 자연어처리 단계의 하나로 구문 해석이 언어에 따라서는 가장 중요한 역할을 하기도 한다. 하지만 한국어나 일본어의 경우 구조가 미약하다. 아마도 자연어처리가 일본어나 한국어같은 교착어를 가진 나라에서 최초 시도되었다면, 구문해석의 단계가 중요한 역할을 하지는 못했을 것이라 생각된다. 우야튼!(^^;) 구문해석은 자연어의 구조를 알아내는 단계이다. 의미를 파악하기 위해, 먼저 구조를 파악해야 되지 않을까? 라는 자연스런 질문에 해당하는 단계로 생각할 수 있다.
구문 해석이란?
구문 해석이란, 문법 규칙 및 여러 종류의 규칙에 의해 입력 문장을 해석하고 그 구조를 명백히 하는 것이다. 예를 들면 "I saw a girl"이란 구조는 다음과 같이 생각할 수 있다.
그림.
구문 해석의 결과 : I saw a girl.
결국, 구문 해석이라 함은 하나의 탐색(search) 과정이라 할 수 있는 데, 형태소 해석으로부터 다음과 입력이 주어지고
I/N saw/V a/DET girl/N.
문맥자유문법(CFG)의 생성 규칙이 아래와 같이 주어질 때,
|
[1] S → NP VP |
[4] VP → V |
[7] PP → PREP NP |
|
[2] NP → N |
[5] VP → V NP |
|
|
[3] NP → DET N |
[6] VP → V NP PP |
|
어떻게 위와 같은 트리(tree) 형태의 구조를 찾을 것인가의 문제가 바로 구문 해석이기 때문이다. 그럼 구문 해석은 어떤 식으로 할까? 크게 Top-Down 알고리즘과 Bottom-Up 알고리즘으로 나눌 수 있다.
Top-Down 알고리즘은 개시기호(S)부터 시작하여 차례로 규칙을 적용해서 주어진 그링 얻어질 때까지 반복하는 방법이다. 우선 처음에 개시기호 S를 위의 표에서 규칙 [1]으로 바꿔보자
S ⇒ NP VP
이 시점에서 두 가지 선택이 있다.
(1) 다음에 NP를 바꿀 것인가, VP를 바꿀 것인가?
(2)
NP를 바꾼다면 어떤 규칙과 바꿀 것인가?(규칙 [2], [3]) VP의 경우도 그렇다.(규칙
[4], [5], [6])
(1)의 문제는 왼쪽의 기호부터 바꿔 써 간다고 하는 방법( 최좌 도출, Mostleft derivation )을 이용하면 되고, (2)의 문제는 단순히 위의 규칙에 따라 적용해 가는 것으로 한다.
S ⇒ NP VP (∵ 규칙 [1])
⇒ N VP
(∵ 규칙 [2])
⇒ I VP (∵ 입력 문장의 첫 단어 I의 품사
N과 동일)
⇒ I V (∵ 규칙 [4])
⇒
I saw(∵ 입력 문장의 두 번째 단어 saw의 품사 V과 동일)
앗! 입력문과 비교하면 입력문의 후반이 남아 있음에도 불구하고 바뀔 기호열이 더 이상 존재하지 않는다! 이와 같이, 어떤 시점에서 해석이 실패했음을 알면, 마치 트리(tree)탐색와 같이 해를 못 찾을 때, 거슬러 올라가 찾는 것처럼, 다른 규칙의 적용이 가능한 시점까지 되돌아가 다시 바꿔쓰기 규칙을 적용한다. 이와 같은 과정을 백트랙(backtrack)이라 한다.
⇒ I saw
⇒ I V NP
⇒
I V N (∵ 규칙 [2])
⇒ ...
⇒ I saw a girl(탐색
완료 시점)
규칙을 적용하여 입력 문장을 찾으면, 경로를 따라가면 쉽게 위와 같은 구조를 알아낼 수가 있는 것이고, 그것으로써 구문해석은 완료된 것이다.
Top-Down은 S에서 출발하여 입력문을 만들어 내지만, Bottom-Up은 입력문(bottom)에서 S를 만들어 가는 방향으로 해석된다. 여러 가지 알고리즘이 있지만 가장 기본적인 Bottom-Up 알고리즘인 CKY(Cocke-Kasami-Younger)법에 대해 알아보자.
Top-Down 알고리즘의 역순이라 생각하면 쉽다. 단지 순조로운
역순 탐색을 위해 CKY법에는 삼각행력을 써서 해석한다. 그리고 삼각행렬을 이용하기
위하여 문맥자유문법(CFG)를 아래와 같이 조금은
다르게 표현한 촘스키 표준형을 이용한다.
|
촘스키 표준형 |
|
|
구구조 규칙(생성 규칙) |
사전 규칙 |
|
S → NP VP |
N → I | girl |
|
NP → DET N |
NP → I | girl |
|
NP → NP PP |
V → saw |
|
VP → V NP |
VP → saw |
|
VP → VP PP |
DET → a |
|
PP → PREP NP |
PREP → NULL |
표. 촘스키 표준형의 문맥자유문법
아래 그림과 같이, 우선, 사전 규칙을 참조하여 입력문의 i번째 단어에 맞는 기호를 설정한다. 다음에는 aij(1 ≤ i, j ≤ n, n은 입력문의 단어수)에 i번째 단어부터 j번째 단어까지의 품사열을 생성하는 것이 가능한 기호를 준다. 예를 들어 a34의 NP는 a33의 DET와 a44의 N로부터 두 번째의 구구조규칙에 의해 만들어진다. 최종적으로 a1n에 S가 주어지면 입력문의 해석은 성공한 것이되며, S에서부터 반대로 찾아가면 문의 구조를 얻을 수 있다.
그림. CKY법에 의한 구문해석
CKY법이 Top-Down과는 해석 방향만 반대이고 비슷한 개념같지만, Top-Down 알고리즘은 해석 시간이 지수차 (O(Kn))인데 반해, CKY법의 해석 시간은 O(n3)이다.
|
Reference |
|
|
||
|
|
||
|
