DBPIA-NURIMEDIA

Size: px

Start display at page:

Download "DBPIA-NURIMEDIA"

미주 궁
5 years ago
Views:

1 복합레이블을적용한한국어구문규칙235 복합레이블을적용한한국어구문규칙 (Korean Syntactic Rules using Composite Labels) 김성용 이공주 최기선 (Seongyong Kim) (Kong Joo Lee) (Key-Sun Choi) 요약본논문에서는한국어구문분석및구문트리표현을위한복합레이블생성방법을제안한다. 기존의구문트리표현에서는미리정의된구문트리레이블을사용하여구문정보를표현하였다. 본논문에서는이진규칙하에서품사태그정보만을이용하여구문레이블을자동으로생성하는방법을제시한다. 제안된구문레이블은두개의하위구성체의품사정보를적절히구성하여형성되며, 동시에현구성체의상태및역할정보를표현할수있도록고안되었다. 이와같이함으로써품사태그정보가가지고있는정보를그대로구문트리에반영시킬수있었다. 또한, 품사정보와이진규칙만을이용하여구문트리를표현하기때문에, 다양한구문규칙을채택하고있는서로다른구문분석기의결과를정규화하는데적용할수있을것이며, 일본어와같은다른언어에도쉽게적용가능하다. 약 31,080 문장에대한구문분석의결과, 79.30% 의정확도를얻을수있었으며, 이는제안된구문트리표현방법이구문분석기의효율에도좋은영향을미침을보이는것이다. 키워드 : 한국어구문분석, 이진규칙, 복합레이블링, 레이블링알고리즘 Abstract We propose a format of a binary phrase structure grammar with composite labels. The grammar adopts binary rules so that the dependency between two sub-trees can be represented in the label of the tree. The label of a tree is composed of two attributes, each of which is extracted from each sub-tree so that it can represent the compositional information of the tree. The composite label is generated from part-of-speech tags using an automatic labeling algorithm. Since the proposed rule description scheme is binary and uses only part-of-speech information, it can readily be used in dependency grammar and be applied to other languages as well. In the best-1 context-free cross validation on 31,080 tree-tagged corpus, the labeled precision is 79.30%, which outperforms phrase structure grammar and dependency grammar by 5% and by 4%, respectively. It shows that the proposed rule description scheme is effective for parsing Korean. Key words :syntactic analysis, Korean, agglutination, binary rules, composite label, automatic labeling algorithm 1. 서론 한국어는첨가어로서, 문장은띄어쓰기에의해구분되는어절로이루어지고어절은여러개의형태소로이루어지는데, 하나이상의실질형태소 (lexical morpheme) 에 0개이상의형식형태소 (grammatical morpheme) 가결합하여구성된다. 그러므로, 한국어구문분석을위한규칙을기술하기위해서는어절과형태소중어느것을 비회원 : 국방과학연구소연구원 sykim@csone.kaist.ac.kr 정회원 : 이화여자대학교컴퓨터학과 kjlee007@ewha.ac.kr 종신회원 : 한국과학기술원전산학과 kschoi@cs.kaist.ac.kr 논문접수 : 2003년 8월 4일심사완료 : 2004년 11월 5일 규칙기술의단위로할것인지를먼저선택하여야한다. (1) 시간 /ncn+ 이 /jcs 귀중 /ncps+ 하 /xsm+ ㄴ /etm 것 /nbn+ 이 /jp+ 다 /ef+./sf 문장 (1) 은문장부호를포함하여 3개의어절과 9개의형태소로구성되어있다. 형태소간의결합은 + 로표시되었으며, 어절간의띄어쓰기는공백으로표현되었다. 문장에서밑줄친서술격조사 이 /jp 는명사구 귀중한것 과결합하는데, 이는 것 /nbn 과 이 /jp 가단순하게결합하는것이아니라관형어 귀중한 과명사 것 /nbn 이구문적으로하나의명사구를생성한이후에그명사구와결합하는것이다. 한국어는지배소후위의언어이기때문에명사구구성체 (construct) 와결합한서술격조사는지배소역할을하며, 결과로생성된구성체는문장에서술어의역할을한다. 이러한현상, 소위후통사적

2 236 정보과학회논문지 : 소프트웨어및응용제 31 권제 2 호 (2004.2) 형태소결합 (post-syntactic morpheme concatenation: PSMC) 현상은앞선두개의구성체가하나의명사구구성체로생성된다음에서술격조사가첨용되기때문에발생하게된다. 한국어의 PSMC 현상은어절을분석단위로하는규칙으로는처리하기어렵다. 따라서, 어절단위의규칙을사용하는연구들에서는 PSMC현상을처리하기위한방편으로기본코퍼스 (source corpus) 와입력문장상의어절중해당현상이발생하는어절에대하여이현상을처리할수있도록어절분리등의재구성을하게되는데 [1,2], 이는기본코퍼스를왜곡하는, 바람직하지못한현상이다. 이러한제한점으로인해한국어구문분석을위해서는형태소를구문분석의단위로하는형태소기반규칙을사용하는것이필요하다. 한국어형태소는명사, 동사어간과같이문장에서상태 (state) 를나타내는실질형태소와조사및어미와같이문장에서구성체의문법적역할 (role) 을담당하는형식형태소로나누어진다. 이두가지의형태소는문장을구성하는데있어서로구분되는쓰임새를가지므로, 한국어구문규칙을다룰때에도이두가지에대한구분이있어야한다. 이논문에서는형태소단위의규칙을사용하며, 품사태그를이용하여구문레이블을자동으로생성하는알고리즘을제시한다. 형태소단위의규칙을사용함으로써 PSMC 현상을다룰수있고, 품사태그정보로부터구문레이블을직접생성함으로써품사태그가가지고있는정보를그대로활용가능하다. 각구문레이블은 Det- Noun Det Noun 에서 DetNoun이두개의하위구성체인정관사 (Det) 와명사 (Noun) 의레이블로부터생성되는형태와같이구성한다. 각레이블은문장에서그구성체가가지는상태및역할을가능한한동시에나타낼수있도록구성한다. 이렇게함으로써구성체의레이블이하위구성체의정보뿐만아니라자신의상태 / 역할정보도나타낼수있게된다. 이러한형태의규칙형식은한국어구문분석을위해자주사용되는의존문법 (dependency grammar, DG) 과매우유사하므로, 의존문법의형태로도적용가능하다. 또한, 제안된규칙형식은이진규칙이라는최소화된형태로서, 이를적용하면다양한규칙표현들을정규화 (normalization) 할수있다. 이를통하여임의의코퍼스로부터정규화된코퍼스를만들수있고, 서로다른문법형식에따른상이한트리구조들을상호비교할수있다. 2. 기존연구한국어는부분자유어순인첨가어로서구문분석을위하여다양한문법이사용되고있다. 그중의존문법 [1,2] 과구구조문법 [3,4] 이주로적용되며 [5], 최근에는결합범주문법 (CCG)[6, 7] 도주목을받고있다. 2.1 의존문법한국어분석에사용되는의존문법에서는분석의효율성을위해지배소후위원칙및투영성 (projectivity) 원리를제약사항으로적용한다. 한국어는문장에서의존소뒤에지배소가온다는원칙을가정하는것이일반적이다 [1]. 형태소단위의품사태그기반의존문법은한국어의 PSMC 현상을다룰수있는반면, 구성체의상태를표현하는실질형태소와문장내에서의구문적역할을나타내는형식형태소를구별하지않는다. 또한, 기존의존문법에서는첨용에의해발생하는의존관계와어절간에일어나는구문적인의존관계를상호구분하지않는다. 한편, 어절단위의품사태그기반의존문법에서는어절이구문분석을위한기본단위가되는데, 한어절은다른어절로부터수식을받거나또는다른어절을수식할수있기때문에, 각어절의레이블은 (ltag, rtag) 형태를취하게된다. 한국어의지배소후위원칙에의하면, ltag는앞에선행하는의존소 ( 어절 ) 에대하여본어절이가지는지배소로서의품사태그를나타내며, rtag는후위지배소 ( 어절 ) 에대해본어절이가지는의존소로서의품사태그를나타내게된다. 문장 (1) 을어절품사태그기반의존문법에맞게작성한코퍼스는표 1과같다. 어절번호 표 1 어절품사태그기반의존문법의표현 지배소어절 어절내용 어절레이블 1 4 시간 /ncn+ 이 /jcs (ncn, jcs) 2 3 귀중 /ncps+ 하 /xsm+ ㄴ /etm (paa, etm) 3 4 것 /nbn (nbn, nbn) 4 0 이 /jp+ 다 /ef+./sf (jp, sf) 여기에서 것 + 이 + 다 +. 는인위적인방법에의해두어절로분리되어있다. 이와같이 것 + 이 + 다 +. 의어절을 2개의다른어절로분리하여처리한이유는 것 + 이 + 다 +. 가하나의어절상태로는 시간이 와 귀중한 의두어절의수식관계를동시에만족시킬수없기때문이다. 2.2 구구조문법구구조문법은규칙의오른편 (right hand side: RHS) 에나오는단말기호및비단말기호의개수에대한제한이없고체계적인구절생성방법을제공하지않으므로, 이러한특성은곧문법규칙의작성시정형성의미흡이라는현상으로나타나게된다 [8]. 또한, 확률구구조문법에서는 RHS 길이의변이로인해문장에대한트리구성참여규칙수가가변적이되며, 작은트리가큰트리

3 복합레이블을적용한한국어구문규칙237 에비해선호도를가지게된다. 제한된구구조문법 (RPSG) 은한국어의자유어순특성을다루기위해제안된문법이다 [3]. 제한된구구조문법에서는규칙을세가지형태로제한한다. 형태 1 규칙 ( A B+ τ) 은파생현상을기술하기위한것이고, 형태 2 규칙 ( A B+ γ C) 은구문요소 (constituent) 사이의관계를표현하기위한규칙이며, 형태 3 규칙 ( A A1 + γ A2+γ... An) 은병렬을기술하기위한규칙이다. 문장 (1) 을 Penn Korean Treebank[4] 의구구조문법형식과 KAIST 코퍼스 [9] 에서사용한제한된구구조문법형식으로나타내면그림 1에서보는바와같다. 구구조문법과제한된구구조문법은품사태그와관계없이인위적으로정의한소수개의구문레이블 - 한국어의경우 [3] 에서는 8개레이블, [4] 에서는 11개레이블 - 을사용한다. 그러나품사태그자체는구문정보뿐만아니라형태결합정보와의미정보등도같이담고있기때문에 [10], 이렇게인위적이고한정된구문레이블을사용함으로써품사태그에내재되어있는정보를잃어버리는현상을초래하게된다. 명사구 귀중 + 하 + ㄴ것 에서구구조문법은 PSMC 현상을제대로다루지못하고있는반면, 제한된구구조문법에서는형태 2 규칙 NP ADJP+etm NP 를사용하여처리하고있다. 또한, 구구조문법은 귀중 + 하 + ㄴ것 + 이 구성체를표현하는데있어명사구가동사구로변환되는과정을보여주지못하는반면, 제한된구구조문법에서는형태 1 규칙 VP NP+jp 를이용하여이를처리한다. 한편, 구구조문법이주격명사구 시간 + 이 를 NP- SBJ 로표현하는반면에제한된구구조문법에는이에상응하는레이블이없다. 제한된구구조문법은형식형태소를실질형태소사이의연결점으로만취급하기때문에, 어순교차의단위 (unit of scrambling) 를표현하지못할뿐만아니라그것이문장내에서가져야할주제적역할도부여할방법이없다. 이는구성적언어 (configurational language) 에서정한구문레이블들을그대로사용하다보니, 그자체가문장성분이되는해당언어에 서와는달리한국어에서는첨용및활용접미사가붙어문장성분이되는특성을무시한데기인한다. 그결과 S VP+ef+sf 와같은경우를제외한다른구문레이블들은항상실질형태소로끝나는현상이나타나는것이다. 3. 한국어구문분석을위한복합레이블링일반적으로규칙에서 RHS의길이가가변적이면해당 RHS를포괄하는규칙의개수를명확하게결정하기어렵다. 다시말해구구조문법에서규칙1 ( NP ADJP NP ), 규칙2 ( NP NP NP ), 규칙3 ( NP ADJ NP NP ) 이라는세가지규칙이있을때입력이 아름다운정원의꽃 이라면, { 규칙1 규칙2} 또는 { 규칙2 규칙1} 또는 { 규칙3} 의적용이가능하다. 여기에서규칙3은구성요소간의존관계가명시적으로드러나지않으며, 규칙1 및규칙2를포함하는잉여규칙이된다. 또한가변길이의 RHS를가지게되면동일한입력문에대해적용되는규칙의수가가변적이된다. 이는확률파싱에서각규칙의확률에큰변이가없을경우적은규칙으로이루어지는구문트리결과를선호하게되는, 확률적용의문제를유발할수있다. 따라서 left-factoring[11] 에의한이진화방법 (binarization) 을적용한구구조문법들 [12,13] 이제시되어있다. 그럼에도불구하고구구조문법은비단말기호들을 RHS 에배열하기때문에동일입력문에대하여이진화된규칙이라고하더라도적용규칙의수가가변적이될수있다. 따라서확률적용상의편향성 (bias) 이완전히해결되지는않는다. 이에비해의존문법등이진규칙을적용하는문법은동일입력문에대하여적용되는규칙의수가일정하기때문에확률적용상의편향성이사라지는장점이있다. 복합레이블이라는용어는 C L R 형태의이진분기규칙에서의노드레이블 C가하위구성체의레이블인 L과 R로부터뽑은정보로구성되기때문에붙여진것이다. 여기에서는이진분기규칙의형식과복합레이블을자동적으로생성하는방법에대하여기술한다. 3.1 이진규칙 그림 1 문장 (1) 에대한구구조문법과제한된구구조문법표현

4 238 정보과학회논문지 : 소프트웨어및응용제 31 권제 2 호 (2004.2) 표 2 각규칙형태별예시 형태 예 규칙 1 시간 /ncn 0Ncn ncn 2a 실 /xp+(0ncn 시간 /ncn) 1Ncn xp + 0Ncn 2b (0Ncn 시간 /ncn)+ 들 /xsn 1Ncn 0Ncn + xsn (0Ncn 시간 /ncn)+ 이 /jcs jcsncn 0Ncn + jcs 2c (0Ncpa 근무 /ncpa)+(0ncn 시간 /ncn) NcpaNcn 0Ncpa + 0Ncn 3 (etmpaa 귀중한 ) (0Nbn 것 /nbu) EtmNbn etmpaa 0Nbn 문맥자유문법은 (T, N, G, S) 의 4개항으로이루어지며, T와 N은각각단말기호 ( 즉, 품사태그 ) 집합과비단말기호 ( 즉, 구문레이블 ) 집합이고, S N는시작기호, G는유한개의규칙을가진집합을표시한다. 여기에서 T는 55개의품사태그로이루어진 KAIST 품사태그집합이다 [10]. 각규칙은 C L R의이진형태로서, 왼편 (left hand side: LHS) 레이블인 C는의존관계정보와구문특성을동시에표현토록한다. 기본적으로한국어의경우 RHS에서 L은의존소이며 R은지배소이다. 또한, 실질형태소 ( 문장부호포함 ) 에는최초레이블을부여하는반면형식형태소자체에는레이블을부여하지않는다. 1) 노드레이블 C가 RHS의지배소정보, 현구성체의상태정보 ( 구구조문법에서의 NP, VP 등 ), 그리고현구성체의역할정보 ( 주격, 목적격등 ) 를동시에가지기위해서는 C LC R 형태의복합레이블을가져야할필요가있다. 결과적으로, 규칙 C L R 은 C LC R L LL R R LR R 과같이변환된다. 여기에한국어에서가지고있는형태결합표시 ( + ) 및띄어쓰기표시 ( ) 를고려하면, 다음과같은세가지형태의규칙을정의할수있다. Type 1 ( 단일원소규칙 ): C LC R f, C LC R N, f T, f는실질형태소 Type 2 ( 어절내부규칙 ): 이형태에는어절내부에서일어나는모든형태의규칙이포함된다. 다음과같은세가지하부규칙으로분류된다. Type 2a: C LC R e+r LR R Type 2b: C LC R L LL R+e Type 2c: C LC R L LL R+R LR R C LC R, L LL R, R LR R N 표 2는각형태의규칙에대한예를보여주고있다. 3.2 복합레이블의자동생성이절에서는이진규칙을위한복합레이블생성방법을기술한다. 적절한복합레이블을생성하기위해필요한제약사항은다음과같다. 복합레이블의어떠한하위구성체의레이블도 null이아니어야하고, C L 및 C R 은중복을피하기위하여동일한정보를가지지않도록해야하며, 하위구성체의레이블로부터현구성체의레이블을만드는방법에는일관성이있어야한다. 또한, C L 및 C R 은품사태그정보를적용하여야한다. 설명을위해서먼저 L을왼편의하위구성체, R을오른편하위구성체라고하자. 아래첨자 State 는구성체의상태태그를의미하며, Role은해당문법기능을가진하위구성체가의존소로결합되어현구성체를이루고있다는의미이고, role은해당문법기능을가진하위구성체가지배소로서현구성체를이루고있다는의미이다. 다시말하여, role은현구성체의형식형태소가가지는역할을나타내는데, 이형식형태소는다른구성체와결합하여상위구성체를만들게된다. 이와달리 Role 은그렇게결합하여상위구성체가형성되었을때상위구성체의복합레이블의한구성레이블을나타내게되는것이다. 예를들어, 귀중하 + ㄴ것 에대한트리를형성하는과정을표현하면그림 2에서보는바와같다. ㄴ /etm 은관형형어미로먼저서술어 귀중하 에결합하여관형어를만들게되는데, 이를표현하는구문레이블은 etmpaa 로서 etm* 은서술어의구문상에서의역할이관형어임을의미하며, 관형어의수식기능이아직적용되지않은상태임을의미한다. 이와달리, C LC R, L LL R, R LR R N, e T, e 는형식형태소 Type 3 ( 어절사이규칙 ): C LC R L LL R, R LR R, 1) 실질형태소는그자체로독립적인구문요소가될수있는반면, 형식형태소는실질어와결합하지않고는구문요소로존재하지못한다. 문장부호는형태소수준이아니라문장수준의기능을가지므로, 독립된단위로구별하여문장차원에서다루어야한다. 그림 2 상태 / 역할정보를적용한레이블

5 복합레이블을적용한한국어구문규칙239 Etm* 은관형어 etmpaa 가불완전명사 것 /nbn 과결합하였음을, 즉관형어가한번의존관계를적용시킨결과임을나타내는표현이다. 결과적으로 귀중한것 은관형어 귀중한 의수식을받은명사구 것 임을 Etm- Nbn 이라는복합레이블을통하여표현하게된다. 한국어의경우이러한상태와역할은품사태그에따라비교적쉽게구분된다. 각형태소마다표현하는상태또는역할은표 3에서보는바와같다. 상태를나타내는것들은실질형태소와동일하며, 단지 Jp 가이에속한다. 상태의표현은대문자로시작하도록하였다. 역할은소문자로표현하였다. 예를들어, jcs* 는역할을나타내지만 Jcs* 의경우에는그렇지않다. 상태 역할 표 3 상태및역할표시자 표시자 Ncpa, Ncps, Ncn, Nq, Nbu, Nbn, Npp, Npd, Nnc, Nno, F, Ii, Pvd, Pvg, Pad, Paa, Px, Mmd, Mma, Mad, Maj, Mag, Jp jcs, jco, jcc, jcm, jcv, jca, jcj, jct, jcr, jxc, jxt, jxf, ep, ecc, ecs, ecx, etn, etm, ef 구성체의복합레이블을표현하기위해서역할에는소문자를, 상태에는대문자를시작문자로표현하므로, jcsncn 의경우상태는 *Ncn, 역할은 jcs* 가된다. 그러나 EtmNbn 의경우에는상태로서 *Nbn 을나타내고있으나역할에대한정보는없다. 이는대문자로 시작하는 Etm* 은현구성체의역할을나타내는것이아니고구성체의구성이력을나타내기때문이다. 다시말해, 이구성체의복합레이블은관형구 etm* 에의해의존명사 ( 구 ) *Nbn 이수식을받음으로써전체적으로관형어의수식을받는의존명사구임을나타낸다. 이러한방식을적용하여각형태의규칙마다복합레이블을생성하는방법은다음과같다. Case 0 ( 하위구성체가한개의상태만을가지는경우 ): type 1, 접두사를가지는 type 2a, 파생접미사를가지는 type 2b 규칙들이속한다. Type 1 규칙에는 0 을, type 2 규칙에는 1 을사용한다. Case 1 (L이상태만을가지고 R이역할만을가지는경우 ): type 2b (e가 jp 인경우는제외 ) 가여기에속한다. 복합레이블은 R rolel State 으로서, 결과적으로생성된구성체의역할은 R role 이고상태는 L State 가된다. Case 2 (L과 R 모두상태만을가지는경우 ): type 2b (e가 jp 인경우 ) 와 type 2c 규칙이이에속한다. 복합레이블 L StateR State 는결과적으로생성되는구성체가역할정보를가지지않고상태로서 R State 를가지고있음을나타낸다. Case 3 (L은상태와역할을가지고있으나 R은상태만을가지는경우 ): type 3 규칙들이이에속한다. 결과적으로생성된구성체는역할을가지지않는다. Case 4 (L과 R 모두상태및역할을가지는경우 ): type 3 규칙의예외적인현상 Case 0 예 상태 역할 LHS 레이블 Type 1 L x x 0R State R 시간 /ncn O(Ncn) x (0Ncn) rule 0Ncn ncn Type 2a L 실 /xp x x 1R State R +(0Ncn 시간 /ncn) O(Ncn) x (1Ncn) rule 1Ncn xp + 0Ncn Type 2b L (0Ncn 시간 /ncn) O(Ncn) x 1L State R + 들 /xsn x x (1Ncn) rule 1Ncn 0Ncn+ xsn Case 1 예 상태 역할 LHS 레이블 Type 2b L (0Ncn 시간 /ncn) O(Ncn) x R rolel State R 이 /jcs x O(jcs) (jcsncn) rule jcsncn 0Ncn + jcs Case 2 예 상태 역할 LHS 레이블 Type 2b L (EtmNbn 귀중 + 하 + ㄴ것 ) O(Nbn) x L StateR State R + 이 /jp O(Jp) x (NbnJp) rule NbnJp EtmNbn + jp Type 2c L (0Ncpa 근무 /ncpa) O(Ncpa) x L StateR State R +(0Ncn 시간 /ncn) O(Ncn) x (NcpaNcn) rule NcpaNcn 0Ncpa + 0Ncn

6 240 정보과학회논문지 : 소프트웨어및응용제 31 권제 2 호 (2004.2) Case 3 예 상태 역할 LHS 레이블 Type 3 L (etmpaa 귀중 + 하 + ㄴ ) O(Paa) O(etm) L RoleR State R (0Nbn 것 /nbn) O(Nbn) x (EtmNbn) rule EtmNbn etmpaa 0Nbn Case 4 예 상태 역할 LHS 레이블 Type 3 L (jcanbn 9+ 시 + 부터 ) O(Nbn) O(jca) R roler State R (jcanbn 6+ 시 + 까지 ) O(Nbn) O(jca) (jcanbn) rule jcanbn jcanbn jcanbn 그림 3 제안한규칙기술방법에따른문장 (1) 의표현 이진규칙레이블을위한상태및역할의가능한조합은 36가지 ({L State, L Role, L role} {R State, R Role, R role} {LL, LR, RL, RR}) 가된다. 하지만, 위에서나타나는것처럼유효한조합은 5가지뿐인데, 그이유는다음과같다. 1. LL 및 RR 조합은발생하지않는다. 단, case 4는예외. 2. L RoleR Role 과같이상태정보없이역할과역할만의조합을이루는것은무의미하다. 3. 레이블구성시역할정보를나타내는부분이항상상태정보를나타내는부분보다먼저오도록표현함으로써표현의일관성을가지도록한다. 4. L roler State 와 R RoleL State 는구성체를표현할수없다. 시간 /ncn+ 이 /jcs 에대한 case 1 규칙 jcsncn 0Ncn+jcs 에대한설명은다음과같다. 먼저, 시간 /ncn 은실질형태소이므로단일원소규칙인 0Ncn ncn 이적용된다. 이후뒤에나오는 이 /jcs 에대해의존소로서결합한다. 이 /jcs 는구성체에서주격역할인 jcs* 를취하며, 복합레이블은주격명사구라는표현의 jcsncn 이된다. 여기에서소문자 jcs* 는주격조사가어순상명사 ( 구 ) 뒤에나온다는표현이다. 그림 3 은문장 (1) 을이러한복합레이블을이용하여트리구조로표현한것이다. JcsJp jcsncn NbnJp 는주격명사구 jcsncn 이의존소로서지배소인서술어구 NbnJp 와결합하여, 결과적으로주어의수식을받는서술어구성체 JcsJp 가됨을의미한다. 4. 실험 이절에서는제안한규칙기술방법이그자체로한국어구문분석에적합한지를판단하기위한실험결과를기술한다. KAIST 구문트리코퍼스는 55개의 KAIST 품사태그와제한된구구조문법을적용한 31,080 문장으로구성되어있다 [9]. 문장당평균어절수및형태소수는각각 및 25.62이다. 실험을위해서 KAIST 코퍼스를제안한규칙기술방법에맞게변환하는작업후, 교차시험 (cross validation: CV) 2) 을실시하였다. 실험은 PC상의 Hancom Linux 2.2 환경에서 MSLR 파서 [14] 를이용하여수행하였으며, 결과측정을위해 PARSEVAL 평가기준 3) [15] 2) 교차시험이란코퍼스를일정비율로균등분할하여한주기가될때까지각부분을돌아가면서시험하는것으로, 본논문에서는전체코퍼스를 10등분하여각부분에대한 held-out test- 학습에사용되지않은문장들에대하여시험하는것으로 9개부분을학습시켜나머지 1개부분을시험- 를실시하였다. 3) 정확율 (precision) 은분석결과에포함된올바른구문요소 (constituent) 개수의비율, 재현율 (recall) 은올바른구문분석에포함된구문요소개수중분석결과에포함된개수의비율이다. 유표지정확율 (labelled precision:lp) 및유표지재현율 (labelled recall: LR) 은구문요소의맞고틀림을그구문요소의대상범위와레이블의일치여부까지판단하여결정하는것이며, 무표지정확율 (unlabelled precision)

7 복합레이블을적용한한국어구문규칙241 표 4KAIST 코퍼스에대한문법규칙기술방법의실험결과 실험 문법 실험문장 레이블 학습 애매성 LP LR 집단 LP&LR 1 PSG 1, , E RPSG-1 1, , E RPSG-2 31,080CV 8 2, E 태그 31,080CV , E 태그 31,080CV 343 5, E MP-based DG 31,080CV 55 1, E 을적용한 EVALB 프로그램 [16] 을이용하였다. 표 4는이러한환경에서실행된실험결과를보여주고있다. 실험 1과 2는 [3] 에서제시된것이며, 실험 3은같은실험환경에서교차시험한결과이다. 구구조문법과제한된구구조문법에서의구문레이블의개수는 8개이다. 위세가지실험결과를종합해보면한국어에대해서약 75% 정확도를보이고있는데, 이는영어의경우문맥자유문법에의한확률파싱이 75% 전후의정확도를낸다 [17] 는사실과유사한결과이다. 나머지실험들은 PC상에서 HanCom Linux 2.2와 MSLR 파서를사용하여수행되었다. 실험 4는제안한규칙기술방법에의한실험으로서, 55 개의품사태그를적용하였으며, 코퍼스로부터추출된구문레이블의개수는 726개이다. 구문레이블은 C LC R 로나타낼수있으며 C R 은항상상태를표현하므로, C R 로가능한것은 31개품사태그들이다 4). 동일한방법으로 C L 로쓰일수있는개수는 68개가된다. 따라서, 2,108개의구문레이블이가능한데, 형태소간결합제약및구문적인결합제약으로인하여코퍼스에서 726개의레이블만이발견된것이다. 또한, 그중잘못된구문레이블이 105개발견되었지만, 실험에서는잘못된오류레이블이라고하더라도코퍼스에서자동으로추출된경우에는그대로포함하여수행하였다. 실험 4의결과를보면 LP 및 LR 측정지표를적용한정확율이 75.58% 로서, 기존방법들과비교할때구문분석규칙의기술방법으로서문제가없음을알수있다. 실험 5는실험 4와비교하여간략화된태그집합이미치는영향을평가하기위해 35개의품사태그를적용한결과이다. 실험 4에사용된 55개품사태그를수준 2 에서묶어 ( 예 : pvg, pvd를 pv로 ) 35개품사태그로만들어실험한것으로서, 55개품사태그를그대로이용한실험에비해 2.53% 의성능저하를나타냈다. 그이유는 및무표지재현율 (unlabelled recall) 은레이블의일치여부를고려하지않은것이다. 4) KAIST-POS 의문장부호 (symbol), 체언 (nominal), 외국어 (foreign), 감탄사 (interjection), 서술어 (predicate), 수식어 (modifier), 서술격조사 (copula) 가이에포함된다. 품사태그개수를줄이면서품사태그에포함된정보의변별력이저하되었기때문으로풀이된다. 실험 6은형태소품사태그기반의존문법의경우이다. 형태소품사태그기반의존문법은각구성체가지배소의품사태그에의해표현되기때문에 55개의레이블을가지는데, 정확율및재현율을보면 75% 보다약간상회하는것으로나타나있다. 실험 4와 5의결과중, 집단 LP&LR 은유표지정확율과유표지재현율을평가하는데있어서, 726개의구문레이블을각각 55개와 35개로집단화시켜평가해본것이다. 이와같이구문레이블을집단화시켜평가해본이유는다음과같다. 그림 4는문장 아름다운정원의꽃 에대한구문트리표현들이다. (a1) 과 (b1) 트리가정답트리이고, (a2) 와 (b2) 가구문분석기의결과트리이다. 그림에서보는바와같이, (a1) 과 (b1) 은동일한구문수식정보를표현하고있으며, 마찬가지로 (a2) 와 (b2) 또한동일한구문수식정보를나타내고있다. 그런데, 표 5에서보는바와같이유표지정확률과재현율을고려할때, 트리 (a) 의경우에는 NP[2,5] 만이틀린구조로평가받는데비해, 트리 (b) 의경우에는모두틀린구조로간주된다. 구구조문법및제한된구구조문법에서는 8개의비단말기호를사용하므로, 정확율및재현율은 8개의레이블에대해서만측정된다. 이러한측면에서제안된규칙기술방법을좀더공정하게평가하기위한집단정확율 (clustered LP) 및집단재현율 (clustered LR) 을제시할수있는데, 예를들어구문레이블 EtmNcn 은비복합적인 (non-composite) 비단말기호 Ncn 으로사상될수있다. 이렇게하면 726개의복합레이블은실험 4 의경우 55개또는실험 5의경우 35개의비단말기호 ( 품사태그의개수와같음 ) 로사상될수있다. 이러한사상을통한평가방법에서는출력트리상의 EtmNcn [0,5] 과정답트리 JcmNcn[0,5] 모두동일한 Ncn [0,5] 으로판정된다. 실험 4에서집단 LP & LR의방법으로평가했을경우, 제안한규칙기술방법이 79.3% 의정확률로기존의다른방법에비해 4% 이상의향상된결과를보였다.

8 242 정보과학회논문지 : 소프트웨어및응용제 31 권제 2 호 (2004.2) 그림 4 아름다운정원의꽃 에대한구문트리표현들 표 5 각구문규칙기술방법에따른 LP 평가 ( 규칙적용범위를 [] 안에표현 ) (a1): 정답트리 (a2): 결과트리 평가 NP[0,3] ADJP[0,1]+etm NP[2,3] NP[2,5] NP[2,3]+jcm NP[4,5] X NP[0,5] NP[0,3]+jcm NP[4,5] NP[0,5] ADJP[0,1]+etm NP[2.5] O (b1): 정답트리 (b2): 결과트리 평가 EtmNcn[0,3] etmpaa[0,2] 0Ncn[2,3] jcmncn[2,4] 0Ncn[2,3]+jcm[3,4] X jcmncn[0,4] EtmNcn[0,3]+jcm[3,4] JcmNcn[2,5] jcmncn[2,4] 0Ncn[4,5] X JcmNcn[0,5] jcmncn[0,4] 0Ncn[4,5] EtmNcn[0,5] etmpaa[0,2] JcmNcn[2,5] X KAIST 품사태그집합 실질형태소 형식형태소 morpheme Symbol Nominal Foreign Intj Predicate Modifier Josa Ending Affix tag sp(pause), sf(full stop), sl(left quotation & parenthesis mark), sr(right quotation & parenthesis mark), sd(dash), se(ellipsis), su(unit), sy(other symbols) ncpa(active-predicative common noun), ncps(stative-predicative common noun), ncn(nonpredicative common noun), nq(proper noun), nbu(unit bound noun), nbn(non-unit bound noun), npp(personal pronoun), npd(demonstrative pronoun), nnc(cardinal numerals), nno(ordinal numerals) f(foreign word) ii(interjection) pvd(demonstrative verb), pvg(general verb), pad(demonstrative adjective), paa(attributetive adjective), px(auxiliary verb) mmd(demonstrative adnoun), mma(attributive adnoun), mad(demonstrative adverb), maj(conjunctive adverb), mag(general adverb) jcs(subjective), jco(objective), jcc(complemental), jcm(adnominal), jcv(vocative), jca(adverbial), jcj(conjunctive), jct(comitative), jcr(quotative), jxc(common auxiliary), jxt(topical auxiliary), jxf(final auxiliary), jp(predicative case) ep(prefinal), ecc(coordinate), ecs(subordinate), ecx(auxiliary conjunctive), etn(nominalizing), etm (adnominalizing), ef(final) xp(prefix), xsn(noun-derivational), xsv(verb-derivational), xsm(adjective-derivational), xsa(adverbderivational)

9 복합레이블을적용한한국어구문규칙243 구문레이블링의사례 0Ncn ncn [ 시간 ] NcnNbn etnpvg [ 먹 + 기 ] 0Nbn [ 때문 ] 1Ncn xp [ 신 ] + 0Ncn [ 기술 ] NbnJp EtmNbn [ 귀중한것 ] + jp [ 이 ] 1Ncn 0Ncn [ 시간 ] + xsn [ 들 ] JxtJp jxtnpp [ 그는 ] NcnJp [ 학생이 ] 1Pvg 0Ncpa [ 생각 ] + xsm [ 하 ] NcpaNcn spncpa [ 정치,] 0Ncn [ 경제 ] 1Mag 0Ncps [ 영원 ] + xsa [ 히 ] MagPaa jxcmag [ 너무나 ] 0Paa [ 길 ] jconcn etnpvg [ 오 + 기 ] + jco [ 를 ] EccPaa spjp [ 좋고,] 0Paa [ 부지런하 ] jcsncn 0Ncn [ 시간 ] + jcs [ 이 ] eccjp eccjp[ 역동적이면서 ] + jxc [ 도 ] JcjNcn jcjncn [ 복수 + 나 ] etnpvg [ 붓 + 기 ] spncpa 0Ncpa [ 정치 ] + 0Sp [,] JcmNcn jcmncn [ 정원의 ] 0Ncn [ 꽃 ] 5. 결론 이논문에서는한국어의구문적특성과한국어구문분석을위한기존문법들을살펴보고, 새로운규칙기술방법및레이블생성방법으로이진분기규칙과품사태그를이용한복합레이블자동생성방법을제시하였다. 제안된규칙에서는구문레이블이구성체의상태및역할을자연스럽게표현할수있으며, 동시에의존관계및구문적정보를표현한다. 또한, 표현된구문레이블을통해서해당구문트리의적절성을쉽게판별할수있다. 형태소기반의이진규칙을적용함으로써한국어의특성인 PSMC 현상을다룰수있으며, 확률적구문분석에서확률적용의편향성 (bias) 을방지한다. 제안된규칙기술방법은하위구성체들의노드레이블을활용하고품사태그를사용함으로써규칙에코퍼스의구문트리확률을보다적절하게반영한다. 이진규칙을이용한, 정규화된규칙표현방법을통하여다양한트리표현방법에의해생성된트리들을쉽게상호비교할수있다. 실험결과 75.58% 의 LP 및 LR, 79.30% 의집단정확율및재현율을보이며, 이는기존방법에비해 4% 이상향상된결과이다. 또한, 제시된규칙기술방법은품사태그를바탕으로한범용적레이블링알고리즘을이용하여복합레이블을생성하므로, 일본어와같은교착어뿐만아니라영어와같은굴절어에도적용가능할것이다. 참고문헌 [1] C. H. Kim, J. H. Kim, J. Y. Seo, and G. C. Kim A right-to-left chart parsing with headable paths for Korean dependency grammar. Computer Processing of Chinese and Oriental Languages 8 (Supplement), 105~118. [2] K. J. Seo, K. C. Nam, and K. S. Choi A probabilistic model for dependency parsing considering ascending dependencies. Literary and Linguistic Computing 13(2), 59~63. [3] K. J. Lee, J. H. Kim, and G. C. Kim An efficient parsing of Korean sentences using restricted phrase structure grammar. Computer Processing of Oriental Languages 11(1), 49~62. [4] C. H. Han, N. R. Han, and E. S. Ko Bracketing Guidelines for Penn Korean TreeBank. IRCS Report 01-10, University of Pennsylvania. [5] 나동렬 한국어파싱에대한고찰. 정보과학회지 12(8), 33~46. [6] J. Cha and Geunbae Lee. Structural disambiguation of morpho-syntactic categorial parsing for Korean, Proceedings of 18th Conference on Computational Linguistics, pp 1002~ [7] Jeongwon Cha, Geunbae Lee, Jong-Hyeok Lee. Korean Combinatory Categorial Grammar and statistical parsing, Computers and the Humanities, Vol 36(4): 431~453, Nov [8] C. D. Manning and H. Schutze Foundations of Statistical Language Processing. The MIT Press. [9] 한국과학기술원 문화체육부와과학기술부의연구과제국어정보처리기구축과 STEP2000에서구축된 KAIST 코퍼스, 1996~1997. 한국과학기술원. [10] 최기선, 남영준, 김진규, 한영균, 박석문, 김진수, 이춘택, 김덕봉, 김재훈, 최병진 한국어정보베이스를위한형태 통사태그표준에관한연구. 인지과학 7(4), 43~61. [11] J. E. Hopcraft and J. D. Ullman Introduction to Automata Theory, Languages and Computation. Addison-Wesley. [12] E. Charniak, S. Goldwater, and M. Johnson Edge-based best-first chart parsing. Proc. of the Fourteenth Nat'l Conf. on AI, 127~133. [13] C. D. Manning, and R. Carpenter Probabilistic parsing using left corner language models. cmp-lg/ [14] H. Tanaka, T. Tokunaga, and M. Aizawa Integration of morphological and syntactic analysis based on LR parsing algorithm. Journal of Natural Language Processing 2(2), 59~74. [15] E.Black, S. Abney, D. Flickinger, C. Gdaniec, R. Grishman, P.Harrison, D. Hindle, R. Ingria, F. Jelinek, J. Klavans, M.Liberman, M. Marcus, S. Roukos, B. Santorini, and T. Strzalkowski A procedure for quantitatively comparing the syn-

244 정보과학회논문지 : 소프트웨어및응용제 31 권제 2 호 (2004.2) tactic coverage of English grammars.

M. White. 2000. Rapid Grammar Development and Parsing Constraint Dependency Grammars with Abstract Role Values. Ph.D. Thesis, Purdue University.

10 244 정보과학회논문지 : 소프트웨어및응용제 31 권제 2 호 (2004.2) tactic coverage of English grammars. Proceedings of Speech and Natural Language Workshop, DARPA, Pacific Grove, 306~311. [16] S. Sekine and M. Collins Evalb. ftp://cs. nyu.edu/. [17] C. M. White Rapid Grammar Development and Parsing Constraint Dependency Grammars with Abstract Role Values. Ph.D. Thesis, Purdue University. 김성용 1985년서울대학교계산통계학과 ( 학사 ) 1987년한국과학기술원전산학과 ( 공학석사 ). 2003년한국과학기술원전자전산학과전산학전공 ( 공학박사 ). 1987년~현재국방과학연구소연구원. 관심분야는자연언어처리, 정보검색, 지능형에이전트 이공주 1992 년서강대학교전자계산학과 ( 학사 ) 1994 년한국과학기술원전산학과 ( 공학석사 ) 년한국과학기술원전산학과 ( 공학박사 ) 년 ~2003 년 ( 주 ) 한국마이크로소프트연구원 년 ~ 현재이화여자대학교컴퓨터학과대우전임강사. 관심분야는자연언어처리, 자연어인터페이스, 기계번역, 정보검색 최기선 1978년서울대학교수학과 ( 학사 ). 1980년한국과학기술원전산학과 ( 석사 ). 1986년한국과학기술원전산학과 ( 박사 ). 1985년 ~1986년한국외국어대학교교수 년~1988년일본 NEC C&C 초빙연구원 1997년~1998년미국스탠포드 CSLI 객원교수. 1988년~현재한국과학기술원교수. 1998년~현재 KORTERM 소장. 관심분야는자연언어처리, 기계번역, 정보검색, 전문용어

자연언어처리

자연언어처리 제 7 장파싱 파싱의개요 파싱 (Parsing) 입력문장의구조를분석하는과정 문법 (grammar) 언어에서허용되는문장의구조를정의하는체계 파싱기법 (parsing techniques) 문장의구조를문법에따라분석하는과정 차트파싱 (Chart Parsing) 2 문장의구조와트리 문장 : John ate the apple. Tree Representation List