Relation Extraction based on Composite Kernel combining Pattern Similarity of Predicate-Argument Structure 정창후 * 최성필 ** 최윤수 *** 송사광 **** 전홍우 ***** Chang-Hoo Jeong Sung-Pil Choi Yun-Soo Choi Sa-Kwang Song Hong-Woo Chun 요 약 문헌에존재하는핵심개체간의관계를자동으로추출할때다양한형태의문서분석결과를활용할수있다. 본논문에서는기존에개발되어비교적높은성능을보여준합성곱구문트리커널의구절구조유사성정보와두개체사이의유의미한연관관계를표현해주는술어 - 논항구조패턴의유사성정보를동시에활용하는혼합커널을제안한다. 구문적구조를이용하는기존의합성곱구문트리커널에술어와논항간의의미적구조를활용하는술어 - 논항구조패턴유사도커널을결합하여상호보완적인혼합커널을구성하였고, 다양한테스트컬렉션기반의실험을통하여개발된커널의성능을측정하였다. 실험결과구절구조정보를이용하는합성곱구문트리커널만을단독으로사용했을때보다술어 - 논항구조의패턴정보를결합한혼합커널을사용했을때에더좋은성능을보이는것을확인할수있었다. 또한기존의시스템보다우수한성능을보이는것도함께확인할수있었다. ABSTRACT Lots of valuable textual information is used to extract relations between named entities from literature. Composite kernel approach is proposed in this paper. The composite kernel approach calculates similarities based on the following information: (1) Phrase structure in convolution parse tree kernel that has shown encouraging results. (2) Predicate-argument structure patterns. In other words, the approach deals with syntactic structure as well as semantic structure using a reciprocal method. The proposed approach was evaluated using various types of test collections and it showed the better performance compared with those of previous approach using only information from syntactic structures. In addition, it showed the better performance than those of the state of the art approach. keyword : 합성곱구문트리커널 (Convolution Parse Tree Kernel), 술어 - 논항구조패턴 (Predicate-Argument Structure Pattern), 관계추출 (Relation Extraction), 혼합커널 (Composite Kernel) 1. 서론 * 정회원 : 한국과학기술정보연구원선임연구원 chjeong@kisti.re.kr ** 정회원 : 한국과학기술정보연구원선임연구원 spchoi@kisti.re.kr *** 정회원 : 한국과학기술정보연구원선임연구원 armian@kisti.re.kr **** 정회원 : 한국과학기술정보연구원선임연구원 esmallj@kisti.re.kr ***** 정회원 : 한국과학기술정보연구원선임연구원 hw.chun@kisti.re.kr( 교신저자 ) [2011/07/01 투고 - 2011/07/05 심사 - 2011/08/08 심사완료 ] 비정형적인텍스트내에서중요하고연관성있는정보를식별하는정보추출은자연어처리및텍스트마이닝분야에서핵심적인영역으로인식되고있다. 이러한정보추출기술을구성하는요소기술로서 (1) 개체명인식 (Named-Entity Recognition), (2) 관계추출 (Relation Extraction), (3) 대용어참조해소 (Co-reference Resolution) 등이있는데 [1], 이중에서문서내에존재하는중요한개체간의관계를자동으로추출하는관계추출은정보추출중에서핵심적인작업으로꼽히면서도가장어려운작업으로알려져있다 [1-3]. 한국인터넷정보학회 (12 권 5 호 ) 73
관계추출문제를해결하기위한방법론으로관계추출에특화된커널함수를새롭게구성하여이를기반으로지지벡터기계 (Support Vector Machines) 에적용하는커널기반방법의효과가주목을받고있다. 관계추출분야에서의커널기반방법의특징은한문장에존재하는두개체간의관계를가장잘표현하는특징을선별해서유사도를가장효과적으로계산하는커널을구성하면성능이매우높게나타난다는것이다. 개체간의관계를추출할때문서내에존재하는다양한특징을활용할수있는데, 본논문에서는두개체간의관계를핵심적으로표현하고있는술어-논항구조패턴을추출하여이를기존의합성곱구문트리커널 (Convolution Parse Tree Kernel) 기법과결합한혼합커널기반의관계추출방법을제안한다. 본논문의구성은다음과같다. 우선 2장에서관계추출과관련한선행연구에대해서살펴본다. 이어서 3장에서는혼합커널기반관계추출기법에대해서살펴보고, 이를구성하는합성곱구문트리커널과술어- 논항구조패턴유사도커널에대해서좀더상세히설명한다. 4장에서는본논문에서제시한시스템의성능을평가하고, 평가결과에대한분석을제시한다. 마지막으로 5장에서결론과향후연구방향을논의한다. 2. 관련연구 지도학습기반관계추출 (Supervised Relation Extraction) 은 1997년도에개최된 MUC-7(Message Understanding Conference 7) 에서처음으로도입된 템플릿기반관계추출 (Template Relation Extraction) 태스크에서본격적으로기계학습기반의관계추출을위한학습집합을제공함으로써이분야연구의단초를제공하였다. 그이후로많은관계추출기법들이개발되었으며, 이를처리기법에따라분류하면크게 (1) 규칙기반방법 (rule-based methods), (2) 자질기반방법 (feature-based methods), 그리고 (3) 커널기반방법 (kernel-based methods) 으로구분된다. 자질기반방법으로서 Kambhatla (2004) 는최초로최대엔트로피모델 (Maximum Entropy Model) 을기반으로다양한형태의어휘적, 구문적, 의미적자질들을이용하여관계추출을시도하였다 [4]. 이를기반으로 GuoDong et al. (2005) 는지지벡터기계를활용하여더확장되고세분화된자질정보를관계추출에적용하였다 [5]. 이와유사하게 Zhao et al. (2005) 는모든세부자질을종류별로구분하고이를개별적인선형커널로구성하여최종적으로혼합커널로결합하는기법을제안하였다 [6]. 이방법은커널함수를직접고안하여적용하였다는점에서커널기반기법으로분류될수도있으나, 커널의구조가단순하고대부분자질벡터로변환될수있는점에근거하여자질기반방법으로분류하였다. 기본적으로위의논문들모두관계추출을위한자질선정이나구성방법에준거하여자질공학적시도에국한하여접근하였으며, 관계인스턴스의구문구조에대한적용은매우제한적으로이루어졌다. 커널기반기법의단초는 Zelenko (2003) 에서제시하였다. 최초로두개의구문분석트리에대한유사도를재귀적으로측정하는연속부분트리커널 (contiguous subtree kernel) 과희소부분트리커널 (sparse subtree kernel) 의두가지구문트리커널을고안하고, 이를두가지이진관계에적용하여매우높은성능을보였다 [7]. 이연구를기반으로 Culotta et al. (2004) 는의존구문트리 (dependency parse tree) 의유사도를측정할수있는커널을개발하였으며, 최초로 ACE 컬렉션을대상으로실험하였으나그성능은비교적낮았다 [2]. 또한 Bunescu et al. (2005) 는 [2] 의결과를확장하여의존구문트리를부분트리로분할하고, 문장내의의존관계경로를대상으로커널함수를구성하여 [2] 에서보다더나은결과를얻었다 [1]. 한편 Zhang et al. (2006) 은 Collins and Duffy (2001) 에서새롭게고안한합성곱구문트리커널을기반으로다양한구조적자질정보와기존의개체자질정보를결합한혼합커널 (composite kernel) 을개발하였다 [8]. 또한 GuoDong et al. (2007) 은 [8] 74 2011. 10
에서제안한구문트리커널의가지치기기법및커널계산기법을확장하여개체쌍주변문맥까지도포괄하는새로운트리커널을개발하였다 [9]. 본논문에서는기존에연구되어비교적높은성능을나타낸합성곱구문트리커널에술어-논항구조패턴유사도커널을결합한혼합커널을제안한다. 구절구조의유사도를측정하는합성곱구문트리커널과술어와논항간의의미적연결고리를활용하는술어-논항구조패턴유사도커널을결합하여보다성능좋은혼합커널을구성할수있음을보인다. ( 그림 1) 전체구문트리에서가지치기된문맥구문트리 3. 혼합커널기반관계추출 3.1 합성곱구문트리커널합성곱구문트리커널 (Convolution Parse Tree Kernel, 이하트리커널 ) 의기본적인개념은구문트리를요소하부트리로분리하고이들하부트리를벡터공간의개별축으로전사시킴으로써 M개의하부트리에대해서 M차원의벡터공간을구성하는것이다. 이때개별구문트리는벡터공간의특정벡터로전사된다. 벡터공간으로전사된구문트리집합쌍은그들간의내적을계산함으로써유사도를측정할수있으며, 이내적값을이용하여관계추출을수행할수있다. 이때관계추출을위한커널함수의유사도측정성능을향상시키기위해서불필요한문맥정보들을제외시키는트리가지치기작업을수행해야하는데, 다양한트리가지치기방법들중에서 PT(Path-enclosed Tree) 방법이가장우수하다고알려져있다 [10]. 따라서본논문에서도 PT 방법을사용하여두개체를연결하는최소경로내에포함된부분트리를사용하도록한다. 문장의전체구문트리에서두개체간의관계추정을위한자질로활용하기위해서가지치기된문맥구문트리의예는 ( 그림 1) 과같다. 트리커널은하부트리분리방법에따라 Vishwanathan and Smola (2003) 이 [11] 에서제안한부분트리커널 (SubTree Kernel) 과 Collins and Duffy (2001) 가 [12] 에서고안한부분집합트리커널 (SubSet Tree Kernel) 로나뉜다. 부분트리기법은트리내에서특정노드의모든자식노드로구성된부분트리를구성하는것이다. 따라서모든부분트리는말단자식노드로서전체트리의잎노드를가져야하며, 구문생성규칙에위배되지말아야한다. 이에반해서부분집합트리기법은부분트리기법보다더일반화된방법으로서, 특정부분트리가반드시전체트리의잎노드를가질필요는없다. 다시말해서, 구문생성규칙에위배되지만않는다면, 특정노드에서출발하여그노드의자식노드중일부분을포함할수있으며, 부분트리커널기법보다훨씬많은부분트리를생성한다. Moschitti (2006) 는 [13] 에서이들두가지커널을빠르게계산할수있는알고리즘을개발하고, 이를 의미역결정 (Semantic Role Labeling) 에활용하여괄목할만한성능을보여주었다. 또한 Moschitti (2006) 에의하면, 부분트리커널은부분집합트리커널에비해서성능이매우저조하게나타났다 [13]. 따라서본논문에서도구문트리분리방법은부분집합트리를이용하였다. 구문트리의유사도를측정하기위해서입력구문트리 는다음과같이함수 에의해서새로운자질공간 로전사된다. 식 (1) 한국인터넷정보학회 (12 권 5 호 ) 75
( 그림 2) HPSG 파서의문장분석결과 식 (1) 에서사상된자질공간은 N- 차원의유클리드공간이며, 자질공간내에서의 은다음과 같이구성요소트리의출현빈도벡터로표현된다. 식 (2) = the number of subtree i S, appearing in T S = a set of all the unique subtrees of the entire tree set. 식 (2) 에서함수 는구문트리 T 내에존재 하는 i 번째구성요소트리의출현빈도를계산한다. 따라서 는그내부구조에따라 N- 차원의 희소벡터 (sparse vector) 로표현될수있으며, 이들간의유사도, 즉커널값은다음과같이내적을통해서계산할수있다. 식 (3) 그러나특정입력구문트리집합내에존재하는모든구성요소트리를추출하고, 이를이용하여개별입력구문트리에대해서벡터를구성하는작업은상당히비효율적이다. 따라서 [12] 에서는 를직접계산하는재귀적방법을고안 해냄으로써처리속도를향상시켰다. 3.2 술어 - 논항구조패턴유사도커널 술어-논항구조는술어와논항관계를이용하여문장내에존재하는각단어간의유의미한연관관계를표현하는구조이다. 그리고술어-논항구조패턴은문장을구성하는모든단어에대한술어-논항관계그래프에서중요하게지정된두개체를연결하는최소집합의술어-논항으로구성된순서열을의미한다. 이러한특성때문에술어-논항구조패턴은문장내에서상호작용하는두개체간의연관관계를표현해주는중요한단서정보가된다. 따라서한개체로부터시작해서다른개체로까지의의미적연결고리를제공해주는술어- 논항구조패턴을이용하여관계추출을수행할수있다. 본논문에서는술어-논항구조패턴을추출하기위해서 HPSG * 파서를이용하였다. CFG ** 를사용하는전통적인파서와달리 HPSG를사용하는파서는효과적으로문장의구문적 / 의미적구조를분석하여술어-논항관계를제공한다. 따라서사용자는파싱결과로부터직접적으로문장에있는단어들사이의의미적연관관계를파악할수있다. HPSG 파서를이용한문장분석결과의예는 ( 그림 2) 와같다. * Head-driven Phrase Structure Grammar, http://en.wikipedia.org/wiki/hpsg ** Context Free Grammar, http://en.wikipedia.org/wiki/context-free_grammar 76 2011. 10
( 그림 3) 술어 - 논항관계그래프 ( 표 1) HPSG 파서분석결과의각열에대한설명열번호상세설명 1 술어 2 술어의기본형 3 술어의품사 4 술어의기본형의품사 5 문장에서술어의위치 6 술어의종류 7 술어와논항사이의관계레이블 8 논항 9 논항의기본형 10 논항의품사 11 논항의기본형의품사 12 문장에서논항의위치 ( 그림 2) 에서보는바와같이 HPSG 파서는문장을입력으로받아서문장을구성하는각단어의술어-논항관계를분석하여제공한다. 행으로나열된술어-논항분석결과의각필드에대한설명은 ( 표 1) 과같다. ( 표 1) 에서설명한내용을바탕으로 Radon_ exposure is the second leading cause of lung_cancer in the general population. 문장에대한분석결과인 ( 그림 2) 의 2번째행과 3번째행을설명하면, 우선단어 is 는동사로서논항 1과 2를갖는데그중논항 1은명사인단어 radon_exposure 를지칭하고논 항 2는또다른명사인단어 cause 를지칭한다는사실을나타낸다. 분석결과의 1번째행은단순히문장의기본술어 (root predicate) 를표현하는것이고, 4번째행부터는 2번째와 3번째행을해석한것과같은방식으로해석하면된다. HPSG 파서에서제공된결과를이용하여각단어의술어-논항관계그래프를그리면 ( 그림 3) 과같이표현된다. ( 그림 3) 에서실제적으로문장내에존재하는두개체간의유의미한관계를표현하는술어-논항구조만을추출하여패턴을구성하면 ( 그림 4) 와같다. 화살표의연결은한개체로부터상호작용하는다른개체로까지의술어- 논항관계를추적할수있다는것을의미한다. 따라서 radon_exposure 와 lung_ cancer 사이의관계를추적해보면 is cause of 와같은중요한패턴을기반으로관계가형성되어있음을알수있다. 다시한번말하지만, 이러한패턴은두개체간의상호작용을식별하는데중요한자질로사용될수있다. 결과적으로개체 1과개체 2의관계는두개체를유의미한관계로연결해주는술어-논항구조패턴에의하여식별될수있다. 술어-논항구조패턴을자질로활용하기위해서술어-논항구조, 즉 ( 그림 4) 에서화살표로연결되는술어와논항, 술어의종류, 그리고술어와논항사이의관계레이블을이용하여벡터값을생성하였다. 그리고이벡터값을 SVM의내장커널중하나인 RBF(Radial Basis 한국인터넷정보학회 (12 권 5 호 ) 77
( 그림 4) 술어 - 논항구조패턴 다. ( 그림 5) 의예문들은구절구조를이용하는트리커널에서는상이한유사도를나타내지만술어- 논항구조패턴을이용할경우에는모두동일한유사도를나타낸다. 그렇기때문에이두가지방법을결합하면기존의트리커널기반의방법보다더나은성능을얻을수있다. 1) ENTITY1 recognizes and activates ENTITY2. 2) ENTITY2 activated by ENTITY1 are not well characterized. 3) The herpesvirus encodes a functional ENTITY1 that activates human ENTITY2. 4) ENTITY1 can functionally cooperate to synergistically activate ENTITY2. 5) The ENTITY1 plays key roles by activating ENTITY2. ( 그림 5) Entity1 activate Entity2 를표현하는서로다른문장구조 Function) 커널을이용하여술어-논항구조패턴의유사도를측정하였다. 3.3 혼합커널 문장내에존재하는두개체간의구절구조정보를이용하여유사도를계산하는트리커널과두개체사이의유의미한연관관계를표현하는술어- 논항구조패턴을기반으로유사도를계산하는커널을선형관계로결합하여혼합커널을구성하였다. 트리커널은그자체만으로도좋은성능을발휘하기때문에이전의많은연구에서활용되어왔지만, 동일한의미를반영하는문장의다양한변형에대해서는유사도측정에잡음이발생할수밖에없다. 하지만술어-논항구조패턴의경우에는능동형, 수동형, to 부정사, that 절과같은다양한변형이발생하더라도두개체간의연관관계를표현해주는패턴을정규화해서일관된형태로기술할수있다. ( 그림 5) 는 Entity1 이 Entity2 를 activate 시킨다는의미를서로다른문장구조로표현한예이 ( 수식 1) 혼합커널구성 ( 수식 1) 에서 K tree(i 1,I 2) 는인스턴스 I 1 과 I 2 간의구절구조유사도를계산하는트리커널이고, K pas (I 1, I 2 ) 는인스턴스 I 1 과 I 2 간의술어-논항구조패턴유사도를계산하는커널함수이다. τ는두커널사이의가중치조절역할을수행한다. 본논문에서는트리커널을빠르게계산하기위하여 [13] 에서개발한트리커널도구를활용하였고, 지지벡터기계학습을위해서는 LIBSVM * 을활용하였다. 그리고구절구조트리생성을위해서 Charniak parser ** 를이용하였고, 술어-논항구조분석을위해서 Enju parser *** 를이용하였다. 4. 실험및분석 본장에서는논문에서제안한술어-논항구조의패턴유사도를결합한혼합커널의성능을파악하기위해서다양한테스트컬렉션기반의실험을수행하고결과를분석한다. 먼저기존의트리커널만을사용한방법과술어-논항구조의패턴유사도를결합한혼합커널을사용한방법의성능에대해서비교실험을수행한다. 첫번째실험을통해서술어-논항구조의패턴유사도정보를결합하여혼합커널을구성하는것이관계추출에유용한작업임을보인다. 다음으로최근에발표된시스템들과의 * http://www.csie.ntu.edu.tw/~cjlin/libsvm/ ** http://www.cs.brown.edu/~ec/#software *** http://www-tsujii.is.s.u-tokyo.ac.jp/enju/ 78 2011. 10
성능비교실험을수행한다. 두번째실험을통해서본논문에서제안한방법론과기존시스템과의객관적인성능비교평가를수행할수있다. 실험에사용된테스트컬렉션에대해서살펴보면, 첫번째실험에서는녹색기술문헌에존재하는 PLOT 간의구체적인상호작용의종류를판별하는성능평가에사용되는 KREC 2010 테스트컬렉션을이용하였다. 그리고두번째실험에서는바이오분야의단백질간상호작용식별실험에대표적으로사용되는 Five PPI Corpora라고불리는테스트컬렉션을이용하였다. 본논문에서사용한성능측정기준은거시평균기반 F-점수 (macro-averaged F-score) 와미시평균기반 F-점수 (micro-averaged F-score) 이다. 우선거시평균기반방법은 m개의클래스에대해서개별적으로정확율과재현율이합산된 F-점수를계산하고, 이를 m으로나눈평균을계산하는방법이다. 이에반해미시평균기반방법은전체검증데이터를기반으로옳게분류된데이터와그르게분류된데이터를누산하고이를기반으로 F-점수를계산하는방법이다. 전자는학습모델의모든클래스에대한분류능력을전체적으로살펴볼수있는장점이있으나, 학습집합의클래스별분포가고르지않을경우상대적으로낮은성능측정결과를가져온다. 미시평균기반방법은학습모델의특정클래스에대한분류능력이상대적으로낮을경우, 이를제대로반영하지못한다는단점이있다. 학습집합의클래스별분포가차이가나는경우나, 학습모델의특정클래스예측성능이낮게나타날경우에는두평가방법의수치차이가상당한경우도있다. 본논문에서는 10겹교차평가 (10-fold cross validation) 를수행하여각성능을측정하였다. 4.1 녹색기술문헌에존재하는 PLOT 간의상호작용추출실험본절에서는술어- 논항구조의패턴유사도를활용하는방법이기존의트리커널방법과결합됐을때얼마만큼의성능향상효과를발휘하는지를알 아보기위한실험을수행한다. 4.1.1 실험대상테스트컬렉션 과학기술문헌에존재하는 PLOT 간연관관계추출성능평가를위해서자체적으로구축한관계추출테스트컬렉션 KREC 2010을활용하였다. PLOT간연관관계추출대상은과학기술문헌중에서도최근들어활발히언급되고있는녹색기술관련분야로한정하였다. 그리고실제문헌은과학기술뉴스 * 와 NDSL ** 에서보유하고있는해외학술지에서선정하였다. KREC 2010 구축과정에대해서좀더구체적으로살펴보면, 우선과학기술뉴스데이터는녹색기술분야중에서도 2000년도이후의문서를대상으로문서크기가상위 80% 이상에해당되는것들만을연도별로임의로선정하여전체 11,185건을수집하였다. 그리고해외학술지데이터는 SCI급, 인용지수, 초록크기등여러가지요소들을고려하여수집하였다. 그기준으로는첫째, 해외학술지중에서인용지수 (impact factor) 를기준으로상위 50종을우선선별하였다. 둘째, 동일한종에서개별초록의크기가평균초록크기의 90% 이상인문서를선정하였다. 셋째, 발행연도가 2000년이후인최신문서를선정하였다. 넷째, 선정된종에서종별로각 25% 의문서를선정하여최종적으로 10,310건의문서를수집하였다. 선정된문서는미리정의된연관관계집합을참조하여관계태깅작업을수행하였다. 실제테스트컬렉션에존재하는연관관계의수는 39개이지만, 본실험에서는비슷한성질의연관관계를통합하여 ( 표 2) 와같이총 7개의연관관계로재구성하여실험을진행하였다. 테스트컬렉션구축은전문가 2인에의해수행되었고, 서로교차검토하여오류를최소화하였다. 테스트컬렉션구축시발생되는철자오류및태깅오류등을방지하고작업속도를높이기위하여, ( 그림 6) 과같은테스트컬렉션구축도구를자체적으로개발하여사용하였다. * http://www.eurekalert.org/ ** http://www.ndsl.kr/index.do 한국인터넷정보학회 (12 권 5 호 ) 79
( 표 2) 실험대상관계종류관계종류 relate change produce own connect analyze cause 의미관계있다변경하다생산하다소유하다연결하다분석하다야기하다 ( 그림 7) τ 값에따른성능변화그래프 ( 그림 6) 테스트컬렉션구축도구 ( 표 3) KREC 2010 통계문서문장핵심개체연관관계 1,090 14,341 22,125 2,441 테스트컬렉션구축도구는문장분리및합병, 핵심개체지정및취소, 핵심개체추천, 연관관계태깅, 분류코드지정, 오류검증등의기능을제공하고, 완성된문서를테스트컬렉션의 DTD에맞는 XML문서로저장한다. ( 표 3) 은본연구에서 1차적으로구축한테스트컬렉션의통계정보이다. 4.1.2 실험결과및분석본절에서는앞의 4.1.1에서소개한 KREC 2010 테스트컬렉션을기반으로수행한 PLOT 간연관관 계자동분류에대한성능평가결과를보인다. 혼합커널의보다정확한성능비교를위해서우선일반구문트리커널과술어-논항구조의패턴유사도커널을각각단독으로사용한경우에대해서살펴본다. 그리고나서최종적으로두방법을결합한상태로사용한경우의성능측정결과를비교해본다. 우선본실험에서는두커널사이의가중치변수 τ 값에따라성능평가결과가달라지는데, ( 그림 7) 에서와같이최적의 τ 값은 0.4로측정되었다. τ 값이증가함에따라전체적인성능이좋아지다가 0.4를넘어서면서전체성능이나빠지는것을확인할수있다. 따라서술어-논항구조의유사도를활용한방법론의기여도는 40% 정도로제한하도록한다. ( 표 4) 는 PLOT 간연관관계추출실험에대한성능평가결과를보여준다. ( 표 4) 에서보이는것처럼트리커널과술어-논항구조패턴유사도커널을단독으로수행했을때는트리커널의성능이술어-논항구조패턴유사도커널보다더좋은것을확인할수있다. 하지만트리커널단독으로사용하는것보다는술어-논항구조패턴유사도커널을결합하여혼합커널을구성하였을때에더나은성능을보이는것을확인할수있다. 따라서기존의트리커널은술어-논항구조패턴유사도커널과결합하여더나은성능을발휘한다는사실을알수있다. ( 표 4) 에서미시평균기반 F-점수 (mi-f1) 보다거 80 2011. 10
( 표 4) PLOT 간연관관계추출성능 커널종류 mi-f1(%) * ma-f1(%) ** 술어-논항구조패턴유사도커널 64.60 33.69 구문트리커널 68.78 38.09 혼합커널 74.72 42.33 시평균기반 F-점수 (ma-f1) 의성능이낮게나타나는이유는테스트컬렉션에사용된 7가지관계의인스턴스의분포때문이다. 7개의연관관계중에서인스턴스의개수가 100개미만인연관관계가 3개존재하는데, 이 3개의연관관계는전체학습인스턴스의단지 6.3%(2,441 중에서 152개 ) 만을차지하고있다. 다시말해서나머지 4개의관계가학습집합의 93.7% 를차지한다는사실로그편중현상이매우심함을알수있다. 따라서관계추출의정답과오답만을검사하는미시평균기반 F-점수와는달리거시평균기반 F-점수는각관계별정답과오답을따로검사한후에그것의평균값을성능으로취하기때문에관계별인스턴스개수의분포가고르지못한경우에는성능이낮게나오는경향이있다. 이는관계인스턴스가적은연관관계의경우에학습집합의부족현상이발생하기때문이다. 4.2 단백질간상호작용식별실험 본절에서는술어- 논항구조의패턴유사도를활용하는혼합커널의보다객관적인성능비교를위해서비교적선행연구가많이수행되어진바이오 분야의단백질간상호작용식별실험을수행하여기존시스템과비교를수행한다. 본논문에서제안하는방법론은분야에의존적이지않기때문에테스트컬렉션만존재하면다양한분야에적용해볼수있는장점이있다. 4.2.1 실험대상테스트컬렉션단백질상호작용식별실험은 [14] 에서구성한 5 가지의 PPI(Protein-Protein Interaction) 관련테스트컬렉션을대상으로수행하였다. 통상적으로 Five PPI Corpora *** 라고불리는이테스트컬렉션집합은 AIMed[15], BioInfer[16], HPRD50[17], IEPA[18] 그리고 LLL[19] 을단일화된 XML 형식으로변환해놓은컬렉션으로서, 현재단백질간상호작용추출기법의준거평가컬렉션으로활용되고있다. ( 표 5) 는 [14] 에서구성한 Five PPI Corpora에포함된개별컬렉션의규모와상호작용포함문장및불포함문장에대한통계정보이다. 특정문장에 2개이상의단백질이름이출현하고그것들간의상호작용관계가설정되어있으면, 단일문장에대해서도여러개의상호작용포함문장이구성된다. 또한문장내에단백질이름이존재하더라도상호작용관계가설정되어있지않다면상호작용포함문장도불포함문장으로동시에설정될수있다. 이를기반으로단백질간상호작용추출은개별인스턴스 ( 상호작용포함 / 불포함문장 ) 에대한이진분류작업으로규정할수있다. ( 그림 8) 은 Five PPI Corpora 에포함된 BioInfer 테 ( 표 5) Five PPI Corpora 규모및내용 테스트컬렉션 AIMed BioInfer HPRD50 IEPA LLL 문장개수 1,955 1,100 145 486 77 단백질간상호작용포함문장 (Positive instance) 1,000 2,534 163 335 164 단백질간상호작용불포함문장 (Negative instance) 4,834 7,132 270 482 166 * micro-averaged F-score ** macro-averaged F-score *** http://mars.cs.utu.fi/ppicorpora/eval-standard.html 한국인터넷정보학회 (12 권 5 호 ) 81
<sentence id="bioinfer.d0.s0" origid="2" text=" inhibits signaling by preventing formation of a * *DNA complex."> <entity charoffset="88-100" id="bioinfer.d0.s0.e0" origid="e.2.2" type="individual_protein" /> <entity charoffset="0-12" id="bioinfer.d0.s0.e1" origid="e.2.3" type="individual_protein" /> <entity charoffset="23-34" id="bioinfer.d0.s0.e2" origid="e.2.4" type="individual_protein" /> <entity charoffset="75-86" id="bioinfer.d0.s0.e3" origid="e.2.5" type="individual_protein" /> <pair e1="bioinfer.d0.s0.e0" e2="bioinfer.d0.s0.e1" id="bioinfer.d0.s0.p0" interaction="true" /> <pair e1="bioinfer.d0.s0.e0" e2="bioinfer.d0.s0.e2" id="bioinfer.d0.s0.p1" interaction="true" /> <pair e1="bioinfer.d0.s0.e0" e2="bioinfer.d0.s0.e3" id="bioinfer.d0.s0.p2" interaction="true" /> <pair e1="bioinfer.d0.s0.e1" e2="bioinfer.d0.s0.e2" id="bioinfer.d0.s0.p3" interaction="true" /> <pair e1="bioinfer.d0.s0.e1" e2="bioinfer.d0.s0.e3" id="bioinfer.d0.s0.p4" interaction="true" /> <pair e1="bioinfer.d0.s0.e2" e2="bioinfer.d0.s0.e3" id="bioinfer.d0.s0.p5" interaction="true" /> </sentence> ( 그림 8) Five PPI Corpora 내에서의 BioInfer 테스트컬렉션첫번째문장 스트컬렉션내에존재하는첫번째인스턴스를보여준다. 단백질간의알려진상호작용의비정상적적용을방지하기위해서문장내의모든단백질이름은블라인드처리가되어있음을알수있다. 또한총 4개의단백질명이존재하며, 이들간의상호작용쌍은총 6가지이다. 결론적으로위의문장에서는총 6개의단백질간상호작용포함문장이구성될수있으며, 이들각각은동일한문장을공유하게된다. 4.2.2. 실험결과및분석 ( 표 6) 은각테스트컬렉션별로가장높은성능을나타내는단백질간상호작용식별실험결과와매개변수값을보여준다. 실험에필요한학습매개변수 C는 SVM 정규화인자를나타내고, λ는비교대상이되는구문트리들의깊이 (tree depth) 가서로상이함에따라발생하는커널값의불일치성을해결하기위해서사용되는트리커널소멸인자를나타낸다. 실험결과, 대체적으로 80% 중 후반대의높은성능을보여주고있다. 다음으로본논문에서구현한접근방법과 [20, 21] 에서의접근방법에대한성능비교를표 7에나타내었다. ( 표 6) 각테스트컬렉션별최고성능 Corpus λ C micro-f1(%) macro-f1(%) AIMed 0.6 6.0 89.5125 81.239 BioInfer 0.5 7.0 88.9233 85.9112 HPRD50 0.7 6.0 84.5266 83.3478 IEPA 0.3 4.0 78.799 77.8944 LLL 0.3 7.0 86.9697 86.9992 ( 표 7) 거시평균기반 F- 점수기준성능비교 AIMed BioInfer HPRD50 IEPA LLL 평균 Airola et al. (2008) [20] 56.4 61.3 63.4 75.1 76.8 66.60 Miwa et al. (2009) [21] 60.8 68.1 70.9 71.7 80.1 70.32 Our system 77.1 82.0 79.0 76.3 85.6 80.00 학습매개변수중의하나인 SVM 정규화인자는 [21] 과의객관적인비교를위해서 1.0으로일치시켰고, 트리커널소멸인자는모두 0.5로동일하게적용하였다. 실험결과, 모든테스트컬렉션에대해서본논문에서제안한시스템이우수한성능을보이고있다. 특히학습집합의규모가큰 AIMed 와 BioInfer 테스트컬렉션에서의성능향상이두드러진다. 82 2011. 10
5. 결론및향후연구본연구에서는문장내에존재하는두개체간의구절구조정보를이용하여유사도를계산하는합성곱구문트리커널과두개체사이의유의미한연관관계를표현해주는술어-논항구조패턴을기반으로유사도를계산하는커널을선형관계로결합하는혼합커널을제안하였다. 그리고이것을과학기술문헌의 PLOT 간연관관계추출및바이오분야의단백질간상호작용식별문제에적용하여성능향상을입증하였다. 결과적으로문장내에존재하는술어와논항간의의미적구조를활용하는술어-논항구조패턴유사도커널은기존의합성곱구문트리커널과결합됨으로써관계추출의성능을향상시킬수있음을보여주었다. 향후연구로는본논문에서제안한아이디어를또다른형태로적용하는방법을생각해볼수있다. 본논문에서는술어- 논항구조의패턴유사도정보를트리커널에혼합커널형태로적용하였지만, 또다른방법으로트리커널의가지치기수행시에본아이디어를적용해볼수있을것이다. 기존에제안된다양한형태의트리가지치기방법이있지만, 술어-논항구조의패턴정보에근거하여정말중요한노드들을인식하고그정보에기반하여가지치기를수행한다면혼합커널기법이아닌트리커널단독으로도충분히성능을향상시킬수있을것으로예상한다. 이경우트리커널은또다른종류의커널과결합하여더욱정교한혼합커널을구성할수있을것이다. 참고문헌 [1] Bunescu, R. C. and Mooney, R. J., A Shortest Path Dependency Kernel for Relation Extraction, Proceedings of the Human Language Technology Conference and Conference on Empirical Methods in Natural Language Processing, pp.724-731, Vancouver, B.C., 2005. [2] Culotta, A. and Sorensen, J., Dependency Tree Kernels for Relation Extraction, Proceedings of the 42nd Annual Meeting on Association for Computational Linguistics, 2004. [3] Bunescu, R. C. and Mooney, R. J., Subsequence Kernels for Relation Extraction, Advances in Neural Information Processing Systems, 2006. [4] Kambhatla N., Combining lexical, syntactic and semantic features with Maximum Entropy models for extracting relations, ACL 2004 (Poster), pp.178-181, 21-26 July, Barcelona, Spain, 2004. [5] GuoDong Z., Su J. Zhang J. and Zhang M., Exploring various knowledge in relation extraction, ACL 2005, pp.427-434, 25-30 June, Ann Arbor, Michigan, USA, 2005. [6] Zhao, S. B. and Grishman, R., Extracting Relations with Integrated Information Using Kernel Methods, ACL-2005, 2005. [7] Zelenko, D., Aone, C. and Richardella, A., Kernel Methods for Relation Extraction, Journal of Machine Learning Research 3, pp.1083-1106, 2003. [8] Zhang, M., Zhang, J., Su, J. and Zhou, G., A Composite Kernel to Extract Relations between Entities with both Flat and Structured Features, 21st International Conference on Computational Linguistics and 44th Annual Meeting of the ACL, pp.825-832, 2006. [9] GuoDong Z., Min Z., Dong H. J. and QiaoMing Z., Tree Kernel-based Relation Extraction with Context-Sensitive Structured Parse Tree Information, Proceedings of the 2007 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning, 한국인터넷정보학회 (12 권 5 호 ) 83
pp.728-736, Prague, June 2007. [10] Zhang, M., GuoDong, Z. and Aiti, A., Exploring syntactic structured features over parse trees for relation extraction using kernel methods, Information Processing and Management, v.44, pp.687-701, 2008. [11] Vishwanathan S. V. N. and Smola A. J., Fast Kernels for String and Tree Matching, Advances in Neural Information Processing Systems, MIT Press, vol.15, pp.569-576, 2003. [12] Collins M. and Duffy N., Convolution Kernels for Natural Language, NIPS-2001, 2001. [13] Moschitti A., Making tree kernels practical for natural language learning, Proceedings of EACL 06, Trento, Italy, 2006. [14] Pyysalo S., Airola A., Heimonen J., Bjorne J., Ginter F. and Salakoski T., Comparative analysis of five protein-protein interaction corpora, BMC Bioinformatics, vol.9, no.s6, 2008. [15] Bunescu R., Ge R., Kate R., Marcotte E., Mooney R., Ramani, A. and Wong, Y., Comparative Experiments on Learning Information Extractors for Proteins and their Interactions, Artif. Intell. Med., Summarization and Information Extraction from Medical Documents, vol.33, pp.139-155, 2005. [16] Pyysalo S., Ginter F., Heimonen J., Bjorne J., Boberg J., Jarvinen J. and Salakoski T., BioInfer: a corpus for information extraction in the biomedical domain, BMC Bioinformatics, vol.8, no.50, 2007. [17] Fundel K., Kuffner R. and Zimmer R., RelEx - Relation extraction using dependency parse trees, Bioinformatics, vol.23, pp.365-371, 2007. [18] Ding J., Berleant D., Nettleton D. and Wurtele E., Mining MEDLINE: abstracts, sentences, or phrases?, Proceedings of PSB'02, pp. 326-337, 2002. [19] Nedellec C., Learning language in logic - genic interaction extraction challenge, Proceedings of LLL'05, pp.31-37, 2005. [20] Airola A., Pyysalo S., Bjorne J., Pahikkala T., Ginter F. and Salakoski T., All-paths graph kernel for protein-protein interaction extraction with evaluation of cross-corpus learning, BMC Bioinformatics, vol.9, no.s2, 2008. [21] Miwa M., Sætre R., Miyao Y. and Tsujii J., Protein-protein interaction extraction by leveraging multiple kernels and parsers, International Journal of Medical Informatics, 2009. 저자소개 정창후 (Chang-Hoo Jeong) 1999 년충남대학교컴퓨터과학과졸업 ( 학사 ) 2002 년충남대학교대학원컴퓨터과학과졸업 ( 석사 ) 2003 년 ~ 현재한국과학기술정보연구원선임연구원관심분야 : 정보검색및추출, 텍스트마이닝 E-mail : chjeong@kisti.re.kr 84 2011. 10
저자소개 최성필 (Sung-Pil Choi) 1996 년부산대학교전자계산학과졸업 ( 학사 ) 1998 년부산대학교대학원전자계산학과졸업 ( 석사 ) 2009 년한국과학기술원대학원정보통신공학과 ( 박사수료 ) 1998 년 ~ 현재한국과학기술정보연구원선임연구원관심분야 : 기계학습, 정보검색, 자연어처리, 정보추출, 텍스트마이닝 E-mail : spchoi@kisti.re.kr 최윤수 (Yun-Soo Choi) 1993 년충남대학교컴퓨터공학과졸업 ( 학사 ) 1995 년충남대학교대학원컴퓨터공학과졸업 ( 석사 ) 1995 년 ~ 현재한국과학기술정보연구원선임연구원관심분야 : 정보검색, 텍스트마이닝 E-mail : armian@kisti.re.kr 송사광 (Sa-Kwang Song) 1997 년충남대학교통계학과졸업 ( 학사 ) 1999 년충남대학교대학원컴퓨터과학과졸업 ( 석사 ) 2011 년한국과학기술원대학원전산학과졸업 ( 박사 ) 2005 년 ~2010 년한국전자통신연구원바이오인포매틱스팀연구원 2010 년 ~ 현재과학기술정보연구원선임연구원관심분야 : 텍스트마이닝, 자연어처리, 정보검색, 시맨틱웹 E-mail : esmallj@kisti.re.kr 전홍우 (Hong-Woo Chun) 2002 년고려대학교컴퓨터학과졸업 ( 학사 ) 2004 년고려대학교대학원컴퓨터학과졸업 ( 석사 ) 2007 년일본동경대학대학원컴퓨터과학전공졸업 ( 박사 ) 2009 년 ~ 현재한국과학기술정보연구원선임연구원 2008 년 ~2009 년 Japan Research Organization of Information Systems, Database Center for Life Science, Project researcher 2007 년 ~2008 년 Japan National Institute of Advanced Industrial Science and Technology (AIST), Japan Biological Information Research Center (JBIRC), 박사후과정관심분야 : 자연어처리, 기계학습 E-mail : hw.chun@kisti.re.kr 한국인터넷정보학회 (12 권 5 호 ) 85