지배소 후보 집합을 이용한 한국어 의존 구문 분석 알고리즘 (A Korean Dependency Parsing Algorithm using Sets of Head Candidates)

서지정보

· 발행기관 : 한국정보과학회
· 수록지 정보 : 정보과학회논문지 : 소프트웨어 및 응용 / 41권 / 1호 / 88 ~ 95페이지
· 저자명 : 안광모, 서영훈

초록

본 논문에서는 ‘지배소 후보 집합(sets of head candidates)’을 이용한 한국어 의존 구문 분석(dependency parsing) 알고리즘을 제안한다. 본 논문에서 제안하는 알고리즘은 모든 의존소와 지배소의 관계를 전역적으로 탐색하는 일반적인 비결정적 의존 구문 분석과는 다르게 각 의존소에 대하여 문법적 관계를 가질 수 있는 지배소 후보들을 제한하여 분석의 복잡도를 감소시켰다. 그리고 한국어 구문 분석 시 일반적으로 고려되는 교착어적 특징, 지배소 후위 및 투사성(projectivity) 원칙을 반영한다. 학습데이터 및 평가데이터로는 세종 구문 분석 말뭉치를 의존 구문 분석 말뭉치의 형태로 변환하여 사용하였으며, 실험결과는 아크단위 87.52%의 정확도(accuracy)와 문장단위 34.43%의 정확도를 보였다. 또한 본 논문에서 제안하는 알고리즘은 문장의 길이에 따라서 CYK 파싱 알고리즘보다 약 3배에서 11배 정도 빠른 구문 분석 속도를 보였다.

영어초록

This paper presents Korean dependency parsing algorithm using sets of head candidates. In this algorithm, the characteristics of Korean language has been used, which are agglutinative, head-final, and projective. Our approach differs from the general non-deterministic dependency parsing that searches whole dependents and heads globally. Instead of considering whole dependents and heads, we restrict to only heads which could be related in grammar for each dependent. Such an approach can reduce the parsing complexity. In addition, we have modified the structure of Sejong tree-tagged to dependency structures, which was originally composed of phrase structures. Such a tagged corpus has been used for training and test data. Our experiments show 87.52% arc accuracy and 34.43% sentence accuracy, respectively. Furthermore, the proposed algorithm shows 3 to 11 times faster than CYK parsing algorithm depending on the lengths of sentences.

참고자료

· 없음