ISSN 2383-630X(Print) / ISSN 2383-6296(Online) Journal of KIISE, Vol. 42, No. 3, pp. 367-378, 2015. 3 http://dx.doi.org/10.5626/jok.2015.42.3.367 기계학습 및 필터링 방법을 결합한 경쟁관계 인식 (Competition Relation Extraction based on Combining Machine Learning and Filtering) 이충희 서 영 훈 김 현 기 (ChungHee Lee) (YoungHoon Seo) (HyunKi Kim) 요 약 본 논문은 기계학습 방법과 필터링 방법을 결합해서 경쟁관계를 인식하는 방법에 대한 연구이 다. 기존 연구들은 기계학습 방법에만 의존해서 관계유형을 인식하는 연구들이 대부분이며. 사용되는 자질 도 일반적인 관계유형에 적합한 자질을 사용하고 특히 구문분석 정보가 매우 중요한 자질로 사용된다. 본 논문에서는 구문분석 등의 언어분석 결과를 이용하지 않고, 단순한 자질들(어휘, 거리, 위치, 단서단어)만을 사용해도 경쟁관계 인식에 효과적임을 확인하였다. 또한, 경쟁관계인식 긍정 정확도를 향상시킬 수 있는 문장별 경쟁유무 분류방법, 스팸분류 방법, 거리제약 기반 자질필터링 방법을 기계학습 방법과 결합한 방 법론을 제안한다. 방법론 검증을 위해서 뉴스분야 2,565개 문장을 평가셋으로 구축하였고, 비교 평가를 위 해서 규칙기반 경쟁관계 인식기와 기존연구의 관계추출 방법론에 기반한 일반 관계추출기를 적용해서 비 교하였다. 성능평가 결과로 규칙기반 엔진이 긍정정확도와 전체정확도(accuracy)가 81.2%와 56.8% 성능 을 보였고, 일반 관계추출기는 61.2%와 56.3%를 보였다. 그에 비해서 본 논문에서 제안하는 방법은 긍정 정확도 92.2%와 전체정확도 71.3% 성능을 보여서 경쟁관계 인식에 효과적임을 확인하였다. 키워드: 관계추출, 경쟁관계인식, 기계학습, 지지벡터기계 Abstract This study was directed at the design of a hybrid algorithm for competition relation extraction. Previous works on relation extraction have relied on various lexical and deep parsing indicators and mostly utilize only the machine learning method. We present a new algorithm integrating machine learning with various filtering methods. Some simple but useful features for competition relation extraction are also introduced, and an optimum feature set is proposed. The goal of this paper was to increase the precision of competition relation extraction by combining supervised learning with various filtering methods. Filtering methods were employed for classifying compete relation occurrence, using distance restriction for the filtering of feature pairs, and classifying whether or not the candidate entity pair is spam. For evaluation, a test set consisting of 2,565 sentences was examined. The proposed method was compared with the rule-based method and general relation extraction method. As a result, the rule-based method achieved positive precision of 0.812 and accuracy 본 연구는 미래창조과학부 및 정보통신기술진흥센터의 산업융합원천기술개발 사업(정보통신)의 일환으로 수행하였음. [10044577, (1세부) 휴먼 지식증강 서비스를 위한 지능진화형 WiseQA 플랫폼 기술 개발] 비 회 원 : 한국전자통신연구원 지식마이닝연구실 forever@etri.re.kr hkk@etri.re.kr 종신회원 : 충북대학교 컴퓨터공학과 교수 (Chungbuk National Univ.) yhseo@chungbuk.ac.kr (Corresponding author임) 논문접수 : 2014년 10월 16일 (Received 16 October 2014) 논문수정 : 2015년 1월 7일 (Revised 7 January 2015) 심사완료 : 2015년 1월 20일 (Accepted 20 January 2015) CopyrightC2015 한국정보과학회ː개인 목적이나 교육 목적인 경우, 이 저작물 의 전체 또는 일부에 대한 복사본 혹은 디지털 사본의 제작을 허가합니다. 이 때, 사본은 상업적 수단으로 사용할 수 없으며 첫 페이지에 본 문구와 출처를 반드시 명시해야 합니다. 이 외의 목적으로 복제, 배포, 출판, 전송 등 모든 유형의 사용행위 를 하는 경우에 대하여는 사전에 허가를 얻고 비용을 지불해야 합니다. 정보과학회논문지 제42권 제3호(2015. 3)
368 정보과학회논문지 제42권 제3호(2015. 3) of 0.568, while the general relation extraction method achieved 0.612 and 0.563, respectively. The proposed system obtained positive precision of 0.922 and accuracy of 0.713. These results demonstrate that the developed method is effective for competition relation extraction. Keywords: relation extraction, competition relation, machine learning, support vector machines 1. 서 론 정보추출(Information Extraction)은 텍스트 마이닝 분야에서 가장 중요한 기술이며, 구체적으로는 개체명 인식(예: 인물, 기관, 지역, 날짜), 관계 추출(예: 인물_X 가 기관_Y에 근무하고 있다), 이벤트 추출(예: 인물_X 가 기관_Y에 날짜_Z 입사하였다) 등이 해당된다. 그 중 에서 관계추출 기술은 정보추출 기술 중 가장 상위 기 술이고 난이도가 높은 분야로 여겨지고 있다[1]. 저자가 조사한 바로는 국내외 관계추출 연구들은 PLO(Person, Location, Organization) 개체 간의 관계 유형으로 located_in, work_for, live_in, kill, orgbased_in 등은 다루고 있지만 경쟁관계인 compete_with 관계 유형을 다루는 연구들은 아직 발표되지 않고 있다. 경쟁관계는 뉴스를 포함해서 최근 활발하게 작성되고 있는 소셜미디어 상의 문서들에서 많이 언급되는 중요 한 관계이다. 또한 최근 빅데이터 시대를 맞이하여 소셜 미디어가 중요한 정보의 소통수단으로 급부상함에 따라 이슈 탐지 및 예측분석 기술이 큰 주목을 받고 있고, 이 러한 이슈 탐지 및 예측 분석에서 경쟁관계 자동 인식 기술의 필요성과 중요성은 점점 커지고 있는 상황이다. 이처럼 실제 사회에서 경쟁관계 인식이 중요한 역할을 하지만 관계추출 연구 분야에서는 관계유형으로 경쟁관 계를 거의 다루지 않고 있다. 경쟁관계는 다양한 관계유형 중의 한 가지이며, 일반 적인 정의로는 어떤 것들(things) 간의 연관성 중에서 도 경쟁이나 대립 측면에서의 연관성을 인식하는 것이 다. 라고 설명할 수 있다. 컴퓨터 인지과학 측면에서는 경쟁관계는 개체명(Named entities) 간의 경쟁이나 대 립 구도의 연관성을 인식하는 것이다 로 정의할 수 있 다. 경쟁관계 인식의 목적은 n개 논항과 관계 서술을 인식하는 것인데, 논항은 개체명을 의미하고 관계 서술 은 경쟁관계를 의미한다. 경쟁관계에 대한 구체적인 정 의는 다음과 같다. 정의 1. 경쟁관계(Competition Relation) 경쟁관계 는 2개의 논항인 개체명 와 의 경쟁관계 여부를 나타내며, 긍정(positive)과 부정(negative)의 2개 값을 가진다. 경쟁관계는 직접경쟁관계와 경쟁가능관계로 구분할 수 있으며, 각각에 대한 구체적인 정의는 다음과 같다. 정의 2. 직접경쟁관계 직접경쟁관계는 문장의 원문에 명확한 증거가 제시되는 경쟁관계를 의미한다. 명확한 증거가 제시된다는 의미는 문장을 읽는 독자의 문맥적 추론을 필요로 하는 것과 구별된다. 즉, 문맥 적 추론이 필요 없이 문장 원문만으로 경쟁관계임을 알 수 있다는 것을 말한다. 직접경쟁관계는 2개 개체명과 관계 표현 간의 관계라고 할 수 있다. 즉, 2개 개체명 정보 외에도 관계 표현이 문장에 나타나야 한다. 직접경쟁관계의 2개 개체명과 관계 표현의 출현 범위 는 1개 문장으로 제약한다. 1개 문장 안에 2개 개체 명과 관계 표현이 모두 나타나야 하며, 대상 문장만 을 읽고도 독자가 2개 개체명이 경쟁관계임을 알 수 있어야 한다. 정의 3. 경쟁가능관계 경쟁가능관계는 문장의 원문에 명확한 증거가 없는 경쟁관계를 의미한다. 명확한 증거가 없다는 의미는 문장을 읽는 독자의 문 맥적 추론이나 상식을 필요로 한다는 것을 말한다. 즉, 2개 개체명 간에 경쟁관계가 있다는 것을 이전 문장이나 다른 문서로부터의 문맥적 추론을 통해서 알 수 있거나, 독자의 상식을 통해서 유추해야 하는 경우를 말한다. 경쟁가능관계는 문맥적 추론이나 독자의 상식을 필요 로 하므로 독자에 따라서 경쟁관계로 볼 수도 있고 경쟁관계가 아니라고 할 수도 있는 애매한 경쟁관계 이다. 경쟁가능관계는 2개 개체명 간의 관계라고 할 수 있 다. 즉, 문장에 2개 개체명만 나타나고 경쟁관계에 대 한 표현이 없는 경우를 말한다. (예제1) 지난해에는 GS칼텍스가 SK네트웍스와 경합 을 벌인 끝에 최종 사업자로 선정됐다. (예제2) 그 동안 나이키 아디다스 등 스포츠 전문기업 은 전문적인 스포츠 용품이나 의류 판매에 주력해왔다. 예제1은 직접경쟁관계에 대한 예제이다. 문장 안에 있 는 경합을 벌이다 라는 명확한 증거를 통해 GS칼텍스 와 SK네트웍스 가 경쟁관계임을 명확히 알 수 있다. 반 면에 예제2는 경쟁가능관계에 대한 예제로써 문장 안에 나이키 와 아디다스 가 명확히 경쟁관계임을 나타내는 표현이 없지만 2개 업체가 동종 제품을 다루는 스포츠 기업이므로 언제든 경쟁이 가능한 기업임을 상식적으로
기계학습 및 필터링 방법을 결합한 경쟁관계 인식 369 인지할 수 있다. 하지만, 동종 제품을 다루는 기업들도 상황에 따라서는 기술 협력 등을 통해 우호 관계를 맺 을 수도 있으므로 예제2 문장만으로는 나이키 와 아디 다스 가 경쟁관계라고 모든 독자가 동의할 수 없다. 본 논문에서는 한 문장 안에 2개 개체명이 모두 나오 고 경쟁관계 표현도 출현하기 때문에 대상 문장만으로 경쟁여부를 명확히 알 수 있는 직접경쟁관계만을 연구 대상으로 다룬다. 지금부터 논문에서 표현되는 경쟁관계 는 직접경쟁관계를 가리킨다. (예제3) 에펠탑은 1889년 파리 마르스 광장에 지어 진 탑이다. (예제4) 애플이 아이폰5S를 출시하면서 동시에 아이 폰5 생산을 전면 중단한다고 협력사에 통보했다. 경쟁관계는 개체 간의 연관관계 중 1가지인데, 개체 간의 연관관계로는 예제3으로부터 추출되는 located_in (에펠탑, 파리 마르스 광장) 관계, 또는 예제4로부터 추 출되는 product_release (애플, 아이폰5S) 관계 등이 있다. 예제3과 예제4에서 보듯이 일반적인 관계유형은 대부분 용언을 중심으로 이진 관계를 형성한다. 예제3에 서는 <지어지다, 에펠탑, 파리 마르스 광장>과 같이 지 어지다 동사를 중심으로 관계를 형성하고, 예제4에서는 <출시하다, 애플, 아이폰5S>와 같이 출시하다 를 중심 으로 관계가 형성된다. 또한 일반적인 관계유형에서는 대상 개체 2개가 동일한 개체유형일 필요는 없다. 그에 반해서 경쟁관계는 2개 개체 간의 이진관계인 것은 동일하지만 2개 개체가 동일한 개체유형인 경우가 대부분이고, 용언보다는 명사가 경쟁관계의 중심 표현인 경우가 많다. 예를 들어 아래의 예제5에서는 vs 명사 가 경쟁관계의 중심 표현이고, 예제6에서는 설전 명사 가 경쟁관계를 나타내는 중심 단어가 된다. (예제5) 애플 vs 삼성, 특허전쟁이 국가적으로 번지다. (예제6) 박지원 박승춘 법사위서 한판 설전 이렇듯 경쟁관계는 다른 관계유형과는 다른 양상을 보인다. 최근에 발표된 관계추출 연구로는 Choi 등[2]이 이벤트 추출을 위해서 130개의 세부적인 관계유형을 인 식하는 관계추출기를 개발하였다. 개발된 관계추출기는 세부적인 관계유형을 인식하기 위해서 뉴스, 블로그, 트 위터로 세분화된 학습셋을 사용하였다. 하지만, 관계추 출기에 적용된 알고리즘 및 자질은 이전 관계추출 연구 들과 유사한 방법을 사용하였다. 세분화된 관계추출기를 평가한 결과에 의하면 130개 관계유형의 평균 정확도가 70%를 넘어서 기존 관계추출 연구와 비슷한 성능을 보 였다. 하지만, 130개 관계유형 중 1개인 경쟁관계 유형 에 대해서는 57.7%의 매우 낮은 성능을 보였는데, 이러 한 결과를 통해서 경쟁관계 인식에 특화된 심층적인 연 구가 필요함을 알 수 있다. 본 논문에서는 경쟁관계 인 식의 필요성과 경쟁관계 인식의 어려움을 인지함에 따 라 경쟁관계에 최적화된 알고리즘을 찾기 위해서 다양 한 접근방법을 연구하고 실험하였다. 본 논문의 구성은 다음과 같다. 2장에서는 관계추출에 대한 기존 연구들에 대해서 설명하고, 3장에서는 본 논 문에서 제안하는 기계학습 및 필터링에 기반한 경쟁관 계인식 방법에 대해서 설명한다. 4장에서는 제안한 방법 으로 구현된 경쟁관계 인식기의 성능을 평가하고 결과 를 분석한다. 마지막 5장에서는 결론을 도출한다. 2. 관련 연구 Message Understanding Conference(MUC)는 미국 DARPA(Defense Advanced Research Projects Agency) 에서 주관하는 학술대회로 정보 추출 연구의 평가 및 활성화를 위해 1987년부터 1998년까지 개최되었다. MUC 참가자들은 미리 정해진 주제에 대해 정보 추출 시스템 을 구축하여 결과를 제출하면, 주관기관에서 공식 평가 프로그램으로 각 참가자의 결과를 평가하였다. MUC에 서 평가된 태스크 중에서 관계추출은 마지막 대회인 MUC-7에서 처음 도입되었는데, 관계유형은 3가지 관계 (LOCATION_OF, EMPLOYEE_OF, PRODUCT_OF) 에 대해서 평가하였다. 학습셋과 평가셋으로 참가자들에 게 각각 100개의 뉴스 문서가 제공되었고, 관계추출 평 가척도는 F-score를 사용하였는데 5개 참가 기관 중 최 고 성능은 SRA[3]가 75.63%의 성능을 보였다. Park 등[4]은 특정 이슈에 대해서 논쟁하는 뉴스 기 사를 2개의 그룹으로 구분하는 방법을 제안하였다. 기사 를 2개의 그룹으로 구분하기 위해서 세부적으로는 논쟁 자를 2개 그룹으로 구분하였고, 논쟁자 후보는 부정 어 휘가 출현한 인용문에 나타나는 인물/지역/기관 개체명 을 대상으로 선정하였다. 논쟁자들을 2개의 그룹으로 구 분하는 방법으로는 HITS 알고리즘을 변형해서 각 그룹 을 대표하는 핵심 논쟁자를 1명씩 선정하고, 나머지 논 쟁자를 2개의 핵심 논쟁자와의 유사도를 계산해서 2개 의 그룹으로 분류하였다. 평가셋은 네이버 뉴스 기사에 서 14개 이슈에 대해서 250개 기사를 선정해서 논쟁자 그룹을 수작업으로 구축하였고, 논쟁자를 2개의 그룹으 로 구분한 성능은 재현율과 정확률 성능이 각각 69%와 56.5%를 보였다. Park 등[4]은 경쟁관계를 인식한 것이 아니라 이슈에 따라 2개의 경쟁 그룹으로 나누는 방법 을 연구하였으므로 본 논문에서 다루는 경쟁관계 추출 과는 직접적인 비교가 힘들다. Choi 등[2]은 2개 개체 사이의 이진 관계 인식 결과 를 기반으로 이벤트를 추출하는 방법을 연구하였다. 130 가지 관계유형을 인식하는 관계추출기에 기반해서 31개 이벤트 유형을 최종적으로 인식하였으며, 130가지 관계
370 정보과학회논문지 제42권 제3호(2015. 3) 유형 중 1개로 경쟁관계가 포함되어 있다. 관계인식은 Structural Support Vector Machines(SSVMs) 알고리 즘을 사용한 분류기를 기반으로 130개 관계유형 중 1개 로 분류하는 방법을 사용하였고, 관계유형 분류기에 사 용된 자질은 다음과 같다. 2개 개체명 주변의 형태소와 품사 2개 개체명 사이의 거리 2개 개체명 사이의 단어 개수 2개 개체명의 개체유형 구문분석 정보: 2개 개체명과 관련된 구문트리의 최하위 용언 학습데이터는 뉴스 15,295문장, 블로그 6,776문장, 트 윗 5,713문장을 사용하였고, 평가셋으로 뉴스 1,376문장, 블로그 745문장, 트윗 543문장을 구축하였다. 130개 관 계유형에 대한 관계인식 성능은 F1 성능으로 뉴스 71.2%, 블로그 65.0%, 트윗 71.9%를 보였다. MUC-7 등의 관계추출에 대한 기존 연구들에서는 PLO와 관련된 매우 일반적인 관계유형들만을 대상으로 인식하였다. 하지만, 최근 이슈화되는 내용을 기반으로 관계 및 이벤트를 분석한 Choi 등[2]의 연구 결과에 의 하면 최근 이슈화되는 이벤트를 다양한 미디어 문서를 분석해서 31개를 정의하였는데 행사개최, 증시상승/하락, 경쟁관계 등에 대한 것으로 실제 사용 측면에서는 경쟁 관계 등의 매우 세부적인 관계 인식이 필요함을 알 수 있다. Choi 등[2]의 실험에 사용된 관계인식 평가셋 중 에는 경쟁관계 대상 문장이 54개가 존재하였고, 유형별 성능 평가에서 경쟁관계 유형은 57.73%의 F1 성능을 보였다. 130개 관계유형 전체에 대한 평균 성능이 70% 정도를 보이는 것에 비해서 경쟁관계 유형이 57.73%의 훨씬 낮은 성능을 보이므로 경쟁관계 인식이 다른 유형 에 비해서 어렵다는 것을 알 수 있다. 이에 본 연구에서 는 경쟁관계 인식에 대한 심층적인 연구의 필요성을 인 지하고, 경쟁관계 인식에 효과적인 자질 및 분류 알고리 즘 등을 분석해서 경쟁관계 인식에 최적화된 알고리즘 을 연구하고자 한다. 에 필터링 방법을 결합해서 성능을 향상시킨 것이 주요 기여점으로 볼 수 있다. 본 논문에서 제안한 방법이 효과적임을 증명하기 위 해서 기준선 엔진으로 단순한 규칙에 기반한 규칙 기반 경쟁관계인식기를 구현해서 비교하였다. 3.1 규칙 기반 경쟁관계 인식 규칙 기반 경쟁관계 인식기는 경쟁 단서 단어에 기반 해서 단순하게 분류하는 방법을 사용하였는데, 경쟁관계 인 2개의 개체가 나타나는 문장에는 경쟁관계 여부를 판단할 수 있는 결정적인 단서단어가 1개 이상 존재한 다는 가정에서 구현되었다. 예를 들면, 삼성전자가 애 플을 상대로 대대적 반격에 돌입하였다. 라는 문장에서 삼성전자 와 애플 은 경쟁관계에 있는 개체이며, 2개 개 체가 경쟁관계임을 나타내는 단서단어로 반격 이 존재 한다. 그림 1은 경쟁관계가 출현한 문장과 경쟁 단서단 어에 대한 예제를 보여준다. 그림에서 단서단어는 빨간 색으로 표시하였다. 그림 1 경쟁관계 출현 문장 및 단서단어 예제 Fig. 1 Example of sentences and clue words of competition relation type 단순 규칙 기반 경쟁관계 인식기의 세부 구성도는 그림 2 와 같다. 3. 기계학습 및 필터링 기반 경쟁관계 인식 경쟁관계 인식방법에는 규칙기반 방법과 기계학습 기 반으로 크게 구분될 수 있다. 규칙 기반 방법은 문맥정 보를 수작업으로 패턴화해서 규칙을 만들어서 인식하는 방법이고, 기계학습 방법은 경쟁관계를 수작업으로 태깅 한 학습데이터로부터 문맥정보를 자질로 추출해서 학습 모델을 학습시켜서 인식하는 방법이다. 본 논문에서는 기계학습 기반 경쟁관계 분류기와 필 터링 방법을 결합한 경쟁관계인식기를 개발하였는데, 경 쟁관계 인식에 적합한 자질을 발굴하고 기계학습 방법 그림 2 규칙 기반 경쟁관계 인식 구성도 Fig. 2 Architecture of rule-based system for competition relation extraction 3.1.1 경쟁 단서단어 추출 단계 경쟁관계 문장은 주요 포털사이트의 실시간 검색어를
기계학습 및 필터링 방법을 결합한 경쟁관계 인식 371 그림 3 경쟁관계 단서단어 예제 Fig. 3 Example of clue words 대상으로 인물/기업/제품에 대한 핫키워드를 1개월 동안 수집하였고, 수집된 핫키워드를 대상으로 1개월간의 뉴 스기사를 검색해서 경쟁 관계 출현 문장만을 따로 수집 하였다. 경쟁관계 단서단어는 수집된 경쟁관계 출현 문장들에 대한 형태소분석 결과를 기반으로 명사, 용언, 부사, 동 사구를 자동으로 추출해서 단서단어 후보를 자동으로 추출하고, 4명의 인원이 수작업으로 검증해서 단서단어 사전을 구축하였다. 최종적으로 620개의 경쟁관계 단서 단어가 수집되었고, 그림 3은 추출된 단서단어의 일부 예를 보여준다. 3.1.2 규칙 기반 경쟁관계 인식 단계 경쟁관계 후보 개체는 한 문장에 출현한 동일 유형의 개체명들이 대상이 된다. 한 문장에 2개 이상의 개체가 나오는 경우에는 2개 쌍의 조합을 각각 경쟁관계 후보 개체로 선정한다. 예를 들어, LTE 가입자가 증가함에 따라 주파수 할당 경매에서 SK텔레콤, KT, LG유플러 스가 경쟁 입찰하게 되었다. 라는 문장에는 기관(OGG_ BUSINESS) 개체유형으로 SK텔레콤, KT, LG유플 러스 3개가 있으므로 SK텔레콤 KT, SK텔레콤 LG 유플러스, KT LG유플러스 의 3개 쌍이 경쟁관계 후 보 개체로 선정된다. 규칙 기반 경쟁관계 분류 과정에서는 주변 문맥을 고 려하지 않고 경쟁관계 단서 단어가 있으면 무조건 2개 의 후보 개체를 경쟁관계로 인식한다. 3.2 기계학습 기반 경쟁관계 인식 본 논문에서는 경쟁관계 인식을 2개 개체의 경쟁관계 여부에 대한 이진 분류 문제로 접근하였고, 지도학습 기 반 분류 모델을 사용해서 경쟁관계를 인식하였다. 그림 4는 지도학습 기반 경쟁관계 인식기의 세부 구 성도를 보여준다. 3.2.1 학습데이터 학습데이터는 3.1절에서 설명된 경쟁관계 수집 문장을 사용해서 수작업으로 경쟁관계를 태깅하였다. 학습데이 터는 4차에 걸쳐서 구축되었고, 각 차수별 구축량은 표 1과 같다. 학습데이터는 경쟁관계인 경우(긍정)와 경쟁관계가 아 닌 경우(부정)가 모두 태깅되었고, 표 1에서 긍정(positive) 그림 4 지도학습 기반 경쟁관계인식 구성도 Fig. 4 Architecture of supervised learning 표 1 경쟁관계 학습데이터 구축결과(단위: 문장) Table 1 Training corpus size Positive Negative Neg. ratio Total 1 970 1,211 1.2 2,181 2 4,124 14,910 3.6 19,034 3 5,698 23,122 4.1 28,820 4 19,347 35,173 1.8 54,520 칼럼이 2개 개체가 경쟁관계인 경우를 나타내고 부정 (negative) 칼럼이 경쟁관계가 아닌 경우를 나타낸다. 경쟁관계의 경우에 실제 문서에서 부정이 긍정보다 훨 씬 많이 출현하는 불균형 데이터이므로 부정이 긍정보 다 많도록 태깅데이터를 구축하였고, 차수 별로 부정의 양을 조절하였다. 표 1에서 부정 비율(neg. ratio)은 부 정이 긍정의 몇 배인지를 나타내며, 부정 개수를 긍정 개수로 나눈 값이다. 3.2.2 경쟁관계 인식을 위한 자질 본 연구에서 경쟁관계 인식을 위해서 사용한 자질은 표 2와 같다. 형태소 자질( )은 문장에 나타난 형태소와 품사 정보를 같이 표현하였고(예: 금액/nc ), 개체명 자질( )은 개체 명 태그 값을 그대로 사용하였다. 토큰 자질( )은 한 어절에 나타난 동일 유형의 토큰을 1개의 자질로 추출 표 2 기계학습을 위한 경쟁관계 자질 Table 2 Features for supervised learning Feature Feature tag Explanation f 1 M Morpheme f 2 NE Named Entity f 3 T Token f 4 L,M,R Location f 5 - Distance (byte) f 6 Clue Clue words occurrence f 7 ClueWord Clue words
372 정보과학회논문지 제42권 제3호(2015. 3) 하였으며, 토큰 유형은 숫자, 심벌, 한국어, 영어, 중국 어, 기타로 구분된다. 토큰 자질에 형태소 정보가 이미 포함되어 있지만 형태소 자질을 추가적으로 사용한 이 유는 복합명사와 같은 경우는 1개의 토큰으로도 사용 가능하지만 2개 이상의 형태소로 분리돼서 독립적으로 도 사용될 수 있으므로 형태소 정보도 독립적인 자질로 사용하였다. 위치정보 자질( )은 문장에 나타난 경쟁관 계 개체 2개를 중심으로 3개의 구역으로 구분하였다. L은 첫 번째 개체의 왼쪽 구역을 나타내고, M은 2개 개체 의 중간 구역을 나타내고, R은 2번째 개체의 오른쪽 구 역을 나타낸다. 거리 자질( )은 각 자질의 경쟁관계 개 체 후보로부터의 바이트 단위 거리를 나타내는데, L구 역에 나타나는 자질은 첫 번째 개체로부터의 왼쪽으로 의 거리로 계산되고, M구역에 나타나는 자질은 첫 번째 개체로부터의 오른쪽으로의 거리로 계산되고, R구역에 나타나는 자질은 2 번째 개체로부터의 오른쪽으로의 거 리로 계산된다. 거리 자질은 경쟁관계 후보 개체와 가까 울수록 중요한 정보라는 가정 하에 사용되었다. 한국어 가 문맥자유 문법이라서 거리정보가 중요하지 않은 경 우도 있지만 일반적으로는 관련 있는 정보를 가까운 문 맥에 사용하게 되므로 자질로서 가치가 있다. 단서단어 자질은 3.1.1절에서 구축된 단서단어를 자질로 사용한 것으로 문장에 단서단어가 있는지 여부( )와 단서단어 어휘 정보( )가 자질로 사용되었다. 3.2.3 분류 알고리즘 지도학습 기 반 관계추출 방법에는 자질 기반 방법과 커널 기반 방법이 있는데, 본 연구에서는 자질 기반 방 법을 사용하였다. 분류 알고리즘은 분류 문제에 많이 사 용되는 Maximum Entropy(ME), Conditional Random Fields(CRFs), SSVMs(Structural Support Vector Machines)을 경쟁관계 인식에 적용해서 비교하였다. SSVMs의 경우에는 학습속도 향상을 위해서 Pegasos 알고리즘을 적용하였다[5,6]. 3.3 오류 필터링 지도학습에 기반해서 경쟁관계를 인식하는 경우에 학 습데이터 오류 또는 학습데이터 부족에 의해서 부정이 지만 긍정으로 잘못 분류되거나 긍정이지만 부정으로 잘못 분류되는 경우들이 발생한다. 경쟁관계 인식 결과 를 사용하는 응용 분야에서는 긍정을 제대로 분류하는 긍정 정확도가 중요하므로 본 연구에서는 부정이지만 긍정으로 잘못 분류되는 오류에 대한 필터링 엔진을 다 양한 방법으로 구현하였다. 그림 5는 본 논문에서 제안 하는 지도학습 분류 방법과 필터링 방법을 결합한 경쟁 관계 인식기의 전체 구성도를 보여준다. 이번 절에서는 경쟁관계 인식기에 적용된 3가지 필터링 방법에 대해서 자세히 설명한다. 그림 5 지도학습 분류방법과 필터링방법을 결합한 경쟁 관계 인식기의 구성도 Fig. 5 Architecture of combination system of classification and filtering 3.3.1 문장별 경쟁유무 분류 기반 필터링 경쟁관계 분류기는 기본적으로 2개 개체가 경쟁관계 후보로 선정된 상태에서 2개 개체를 중심으로 자질을 추출해서 경쟁관계 여부를 분류하게 된다. 문장별 경쟁 유무 분류기는 2개 개체를 중심으로 경쟁관계 여부를 분류하는 방법을 단순화시켜서 해당 문장 자체의 경쟁 관계 포함 여부만을 분류한다. 문장별 경쟁유무 분류기의 학습데이터는 표 1에서 설 명한 학습데이터를 그대로 사용하였다. 사용된 자질은 표 2에서 설명된 자질 중에서 형태소 자질( ), 개체명 자질( ), 토큰 자질( ), 거리자질( )의 기본 자질 4개 만을 사용하였다. 문장별 경쟁유무 분류기의 분류 알고리즘은 SSVMs 을 사용하였다. 문장별 경쟁유무 분류 기반 필터링 절차는 입력된 문 장에 대해서 4개 유형의 자질을 추출해서 문장별 경쟁 유무 분류 모델을 이용해서 경쟁관계 포함여부를 분류 하였고, 경쟁유무 분류 결과가 부정인 경우에는 해당 문 장을 필터링시켰고, 경쟁유무 분류결과가 긍정인 문장에 대해서만 경쟁관계 인식기의 다음 단계로 진행하였다. 3.3.2 스팸 분류 기반 필터링 동일 개체유형의 개체 2개 중에는 절대로 경쟁관계가 될 수 없는 것들이 있다. 예를 들면, 류현진-클라라, 이 순신-세종대왕, 삼성그룹-삼성전자와 같은 것들이다. 이 러한 경쟁관계가 성립될 수 없는 2개 개체를 블랙리스
기계학습 및 필터링 방법을 결합한 경쟁관계 인식 373 트로 수작업으로 구축하였고, 수집된 블랙리스트에 기반 해서 스팸(Spam) 분류기를 만들어서 필터링 엔진으로 적용하였다. 여기서 스팸이라는 용어는 경쟁관계가 성립 될 수 없는 문장을 스팸 문장이라고 본 논문에서 임의 로 정의하였고, 블랙리스트가 출현한 문장을 무조건 스 팸 문장으로 구분하였다. 스팸 분류기는 경쟁관계가 없는 문장, 즉 스팸문장을 긍정(스팸 클래스)으로 인식하고 경쟁관계가 포함된 문 장을 부정(논-스팸 클래스)으로 인식한다. 스팸 분류기 는 학습데이터를 수작업으로 태깅하는 절차를 생략한 비지도 방법에 의해서 만들어졌다. 학습데이터는 블랙리 스트에 기반해서 자동으로 수집하였고, 수집된 문장들은 긍정 클래스로 자동 태깅하였다. 긍정 학습데이터는 자 동으로 많이 구축할 수 있는 반면, 경쟁관계를 포함하는 논-스팸 클래스 문장은 수작업으로 구축해야 하므로 스 팸 분류기는 학습데이터로 긍정 클래스만을 사용하는 원클래스(one class) SVMs 알고리즘을 사용해서 분류 모델을 학습하고 생성하였다. 원클래스 SVMs 알고리즘은 데이터 불균형 문제를 해결하기 위해서 최근에 많이 연구되고 있는 원클래스 분류 알고리즘 중 한 가지이며, 관심 대상인 범주 1개에 대한 학습데이터만을 가지고 학습을 수행해서 대상 범 주를 잘 설명할 수 있는 분류 경계를 설정하는 문제로 접근한다. 본 논문에서는 스팸 분류가 원클래스 분류 문 제로 접근이 가능할 것으로 생각해서 원클래스 SVMs 알고리즘을 적용하였다. 스팸 분류 기반 필터링 절차는 다음과 같다. 1단계) 스팸 분류기 학습 단계 블랙리스트 수집(수작업 구축) 블랙리스트 기반 학습데이터 자동 구축 학습데이터 기반 스팸 분류기 학습 2단계) 스팸 분류 기반 필터링 단계 입력된 문장에 대한 스팸 분류 스팸 분류: 긍정인 문장 -> 필터링 스팸 분류: 부정인 문장 -> 경쟁관계 인식 1단계에서 블랙리스트 수집 과정은 인물, 기업, 제품 의 3개 개체유형에 대해서만 수작업으로 구축하였고, 1 개월의 뉴스 기사를 대상으로 수집한 결과로 2,408개가 구축되었다. 블랙리스트 기반 학습데이터 자동 구축 과 정은 수집된 블랙리스트가 1개 문장에 동시에 나타난 문장을 무조건 수집해서 긍정 클래스로 자동 태깅하였 다. 스팸 분류기 학습 과정은 자동으로 수집된 학습데이 터에 대해서 one class SVMs 모델을 학습시켰으며, 사 용된 자질은 표 1의 자질 중에서 형태소 자질( ), 개체 명 자질( ), 토큰 자질( ), 거리자질( )의 기본 자질 4개만을 사용하였다. 원클래스 SVMs 모델의 파라미터 는 실험을 통해서 최적 값을 구하였고, 학습 속도 향상 을 위해서 Stochastic gradient descent (SGD) 알고리 즘[7]이 적용되었다. 2단계 스팸 분류 기반 필터링 단계에서는 경쟁관계 추출을 위해서 입력되는 문장들에 대해서 스팸 분류 과 정을 먼저 거쳐서 스팸 분류 결과가 긍정인 문장들은 필터링 시키고, 스팸 분류 결과가 부정인 문장들에 대해 서는 경쟁관계 인식의 다음 단계로 진행한다. 3.3.3 거리 제약 기반 자질 필터링 3.2절에서 설명한 기본적인 지도학습 기반 경쟁관계 인식기에서는 경쟁관계 후보 개체와의 거리와 상관없이 문장에 있는 모든 자질을 사용하였다. 하지만, 경쟁관계 후보 개체로부터 너무 먼 거리에 있는 자질의 경우에는 후보 개체와의 연관도가 떨어지면서 노이즈로 작용할 가능성도 높다. 그러므로 거리 제약 기반 자질 필터링에 서는 거리 자질을 단순히 형태소, 토큰, 개체명 자질과 결합해서 사용하는 것이 아니라, 제약 조건으로도 사용 해서 정해진 거리 안에 있는 경우에만 자질로 추출하도 록 제약을 주었다. 거리 자질의 제약 조건은 바이트 단 위로 계산되었고, 거리 제약에 사용할 거리를 n값으로 외부에서 설정할 수 있도록 하였다. 거리 제약 기반 자질 필터링은 학습데이터로부터 자 질을 추출하는 학습단계와 새로운 문장을 대상으로 경 쟁관계를 인식하는 단계에서 모두 적용되었다. 4. 실험 및 결과 이번 장에서는 본 논문에서 제안하는 경쟁관계 인식 방법론의 효과를 입증하기 위한 실험 내용 및 평가 결 과를 설명한다. 4.1 실험 환경 실험은 경쟁관계 분류 성능을 측정하고 비교하였다. 평가셋은 표 1에서 설명된 4차 학습데이터 중 3차 데이 터를제외한 나머지의 10%를 무작위로 추출해서 사용하 였고, 평가셋으로 추출된 데이터는 학습 시에는 사용되 지 않았다. 평가셋 데이터는 2,565개 문장으로 긍정 1,362개, 부정 1,203개 문장으로 구성되었다. 전통적인 분류 연구에서 성능 측정에 대부분 정확도(accuracy)를 사용하므로, 본 논문에서도 경쟁관계 분류 성능 측정에 수식 (1)과 같은 정확도를 사용하였으며 표 3에서 수식 에 사용된 빈도정보를 설명한다. (1) 세부적인 성능 측정을 위해서 정확도 외에도 긍정정 확도(POS)와 부정정확도(NEG) 성능도 측정하였다. POS 는 긍정 클래스에 대한 정확도로써 시스템이 긍정으로 분류한 문장들 중에서 올바르게 분류한 문장 비율을 측
374 정보과학회논문지 제42권 제3호(2015. 3) 표 3 경쟁관계 분류 성능 측정을 위한 2 2 분할표 System Table 3 2 2 contingency table Positive Negative Answer Positive Negative TP (true positive) FN (false negative) FP (false positive) TN (true negative) 정한 것이고, NEG는 부정 클래스에 대한 정확도로써 시스템이 부정으로 분류한 문장들에 대한 정확도를 측 정한 결과이다. 4.2 기준선 엔진 성능 제안한 방법론과 비교 평가를 위한 기준선 엔진으로는 규칙 기반 경쟁관계 인식기와 기존연구의 일반관계추출 기를 구현해서 비교하였다. 기존연구의 일반관계추출기 로는 최근에 Choi 등[2]이 발표한 이벤트 추출을 위한 130개 세부 관계유형 인식기를 저자로부터 직접 받아서 사용하였다. Choi 등[2]의 관계추출기는 이전 관계추출 연구들과 유사한 알고리즘 및 자질을 사용하였고, 이벤 트 추출을 위한 130개 관계유형의 평균 정확도가 70%를 넘어서 기존 관계추출 연구와 비슷한 성능을 보였다. 표 4 기준선 엔진 성능 Table 4 Result of baseline systems POS NEG Accuracy baseline(rule) 0.780 0.547 0.603 baseline(choi) 0.812 0.522 0.568 4.2.1 규칙 기반 경쟁관계 인식 성능 규칙 기반 경쟁관계 인식기는 수작업으로 구축된 620 개의 경쟁단서 단어를 기반으로 단순하게 경쟁관계를 인식하는 방법으로 평가셋에 대해서 실험한 결과는 표 4 의 baseline(rule)과 같다. 규칙 기반 경쟁관계 인식기는 POS 성능이 78.0%이고 NEG 성능이 54.7%이므로 경 쟁관계인데 경쟁관계가 아닌 것으로 인식한 경우가 많 은 것을 알 수 있다. NEG 오류인 45.3%는 경쟁관계이지만 경쟁관계로 인 식하지 못하는 경우이며, 경쟁 단서단어를 수작업으로 수집하면서 미처 수집되지 못한 단서단어가 존재하기 때문으로 수작업 구축의 한계를 보여준다. POS 오류인 22.0%는 부정인데 긍정으로 인식한 경우이며, 문장에 경쟁 단서단어가 출현했지만 경쟁관계 후보인 2개 개체 에 대한 경쟁 표현이 아닌 경우를 나타낸다. 이번 실험 을 통해 경쟁관계 단서단어가 매우 강력한 정보이지만 문맥을 고려하지 않으면 오류가 많고, 모든 단서단어를 수집하는 것의 한계를 확인할 수 있다. 4.2.2 일반 관계추출기 성능 구문분석 정보가 가장 중요한 자질로 사용되는 일반 관계추출 방법론이 적용된 Choi 등[2]이 구현한 관계추 출기를 저자로부터 직접 받아서 본 논문에서 구축한 4 차 학습데이터를 이용해서 학습을 시키고, 4.1절에서 설 명한 평가셋에 대해서 평가하였다. 평가결과는 표 4의 baseline(choi)와 같다. Choi 등[2]의 관계추출기가 130 개 일반 관계유형에 대해서 뉴스분야에서 71.2% 정확도 를 보이는 것에 비해서 경쟁관계 유형에 대해서는 56.8%의 낮은 성능을 보이는 것을 확인하였다. 경쟁관 계 학습데이터에 대해서 모델 파라메터 튜닝을 하지 않 아서 최적의 성능이 아닌 것을 감안하더라도 기존연구 의 자질이 경쟁관계 인식에는 부적합하다는 것을 유추 할 수 있다. 4.3 지도학습 기반 경쟁관계 인식 이번 절에서는 지도학습 기반 경쟁관계 인식기에 대 한 다양한 실험결과를 설명한다. 4.3.1 분류 알고리즘 실험 이번 실험에서는 3개의 대표적인 분류 알고리즘을 사 용해서 경쟁관계 인식기를 구현하고 실험하였다. 대상으 로 선정한 분류 알고리즘은 ME, CRFs, SSVMs의 3가 지 알고리즘이다. 세부 실험 환경은 다음과 같다. 학습데이터: 표 1의 학습데이터 중 1차 버전(2,181 개 문장) 사용자질: 표 2의 모든 자질( ) 표 5는 3가지 분류 알고리즘을 각각 사용해서 경쟁관계 를 인식한 성능을 나타낸다. 3개 알고리즘들 중 SSVMs 알고리즘이 가장 높은 성능을 보였다. 이번 실험으로 경 쟁관계 분류 문제에서는 분류 알고리즘에 따른 성능 차 이가 크지 않음을 알 수 있다. 근소한 차이지만 SSVMs 분류 알고리즘이 가장 좋은 성능을 보였으므로 최종적 으로 SSVMs을 지도학습 기반 경쟁관계 인식기의 분류 알고리즘으로 선정하였으며, 이후 실험부터는 SSVMs 알고리즘을 사용해서 모든 실험이 이루어진다. 표 5 분류 알고리즘 비교 평가: 경쟁관계 인식성능 Table 5 Result of algorithm comparison Algorithm Accuracy ME 0.560 CRFs 0.553 SSVMs 0.569 4.3.2 자질 선택 3.2.2절에서 경쟁관계 인식을 위해 7가지 유형의 자질 을 정의하였는데, 이번 실험에서는 7개 자질을 모두 사 용한 경우와 자질을 개별적으로 제외한 경우의 성능저하
기계학습 및 필터링 방법을 결합한 경쟁관계 인식 375 표 6 경쟁관계 인식에서의 자질 기여도 측정 Table 6 Feature contribution test Feature Accuracy Contribution Baseline: All 0.569 - Removed: f 1 0.593-0.024 Removed: f 2 0.593-0.024 Removed: f 3 0.554 0.015 Removed: f 4 0.554 0.015 Removed: f 5 0.554 0.015 Removed: f 6 0.483 0.086 Removed: f 7 0.556 0.013 Optimum: f 3 +f 4 +f 5 +f 6 +f 7 0.606 - 를 측정해서 각 자질의 기여도를 측정하였다. 표 6은 각 자질을 제외한 경우의 정확도 및 각 자질의 기여도를 보 여준다. 기여도는 모든 자질을 사용한 정확도에서 각 자 질을 제외한 정확도를 빼서 계산하였다. 즉, 기여도가 + 인 경우에 해당 자질의 기여도가 높다고 볼 수 있다. 자질 기여도 평가 결과, (형태소자질)과 (개체유 형)는 제거한 경우에 도리어 성능이 올라간 경우로써 부정적 기여를 한 것으로 나타났다. 나머지 5개 자질은 제거한 경우에 성능 저하가 발생하였는데, 단서단어 유 무 자질인 의 기여도가 가장 높았고 단서단어 어휘 자질인 의 기여도가 가장 낮았다. 자질 기여도 측정에 서 긍정적으로 기여한 5개 자질인 만을 사 용한 경우에 0.606의 정확도 성능을 보였는데, 7개 모든 자질을 사용한 것에 비해서 3.7%의 성능 향상을 보였 다. 지도학습 기반 경쟁관계인식기는 7개 자질을 모두 사용한 경우에는 규칙 기반 엔진의 성능(0.603)에 비해 서 낮은 성능(0.569)을 보이지만, 자질 선택을 통해 최 적 자질을 사용한 경우에는 정확도 0.606으로 규칙 기반 경쟁관계인식기보다 0.6% 높은 성능을 보였다. 4.3.3 학습데이터 구축량에 따른 성능 비교 지도학습 기반 분류기는 학습데이터가 분류 성능에 미치는 영향이 매우 크다. 이번 실험에서는 표 1에서 설 명한 4가지 학습데이터를 기반으로 경쟁관계 분류기를 각각 학습하고, 학습된 분류모델을 경쟁관계 인식에 사 용한 결과를 비교하였다. 이번 실험의 세부 실험 환경은 다음과 같고, 그림 6은 실험결과를 보여준다. 분류 알고리즘: SSVMs 사용 자질: 이번 실험을 통해서 학습데이터의 구축량이 증가하면 서 2만개 정도까지는 성능향상이 크지 않지만, 5만개 이 상 구축하면서 대폭적인 성능향상이 이루어짐을 확인하 였다. 이번 실험에서 가장 성능이 높았던 4차 학습셋을 그림 6 학습데이터 구축량에 따른 경쟁관계 인식 성능 Fig. 6 Effect of training corpus size on classifier performance 최종 학습셋으로 결정해서 지도학습 기반 경쟁관계 인식 기에 적용하였다. 4.3.4 지도학습 기반 경쟁관계 인식 기본엔진 4.3.3절까지 실험된 내용들을 기반으로 경쟁관계인식 에 최적화된 지도학습 기반 경쟁관계 인식기를 기본엔 진(proposed-base)이라고 나타낸다. 기본 엔진의 엔진 구현 환경은 다음과 같고, 표 7은 기본엔진의 세부 성능 을 나타낸다. 분류 알고리즘: SSVMs 사용 자질: 학습데이터: 표 2의 학습데이터 중 4차 버전 (54,520 개 문장) 표 7 지도학습 기반 기본 엔진 성능 Table 7 Performance of base engine POS NEG Accuracy proposed-base 0.863 0.595 0.669 4.4 오류 필터링 이번 실험에서는 긍정 클래스의 인식 정확도를 높이기 위 한 필터링 방법들을 경쟁관계 인식에 적용하고 실험하였다. 4.4.1 문장별 경쟁유무 분류 기반 필터링 이번 실험에서는 문장별 경쟁유무 분류기를 필터링 엔진으로 적용해서 기본 엔진과 결합하였다. 실험 과정은 경쟁관계 인식을 2단계로 진행하였다. 1단 계는 문장별 경쟁유무 분류를 하고, 2단계는 1단계 결과가 긍정인 문장들만을 대상으로 경쟁관계 인식을 수행하였다. 실험은 문장별 경쟁유무 분류기의 학습데이터로 1차, 2차, 3차, 4차를 각각 사용해서 성능을 평가하였다(그림 7). 필터링 단계로 사용된 4가지 문장별 경쟁유무 분류기 중에서 4차 학습셋을 사용한 분류기가 긍정 정확도 및 전체정확도를 각각 5.2%와 1.3%씩 개선시켰다.
376 정보과학회논문지 제42권 제3호(2015. 3) 그림 7 기본엔진 & 문장별 경쟁유무 분류 기반 필터링 Fig. 7 Performance when filtering by classifying competition relation occurrence 4.4.2 스팸 분류 기반 필터링 이번 실험은 스팸 분류기를 경쟁관계 분류의 전처리 단계로 이용해서 경쟁관계 인식을 2단계로 적용하였다. 1단계는 각 문장별로 스팸 분류기를 적용하고, 2단계는 스팸 분류 결과가 부정인 문장, 즉 논-스팸인 문장만을 대상으로 경쟁관계 인식을 적용하였다. 스팸 분류기의 구현환경은 다음과 같다. 분류 알고리즘: 원클래스 SVMs 블랙리스트: 2,408개 개체 쌍 학습데이터: 뉴스기사 91,929문장 그림 8은 스팸 분류기를 필터링 엔진으로 적용한 경 우와 기본엔진의 성능을 비교한 결과를 보여준다. 논-스팸 문장에 대해서 각각 측정하였다. 실험 결과, 스 팸 인식률 45.4%와 논-스팸 인식률 73.6%의 성능을 보 였는데, 스팸 문장의 인식 성능이 떨어지는 것을 확인하 였다. 그 원인은 원클래스 SVMs의 경우에 학습데이터 가 많이 필요한데, 필요한 만큼의 학습데이터를 수집하 지 못한 것이 원인으로 보인다. 하지만, 스팸분류기 성 능이 낮음에도 불구하고 경쟁관계 인식기의 전처리 필 터링 엔진으로 사용한 경우에 경쟁관계 인식 성능 향상 에 도움이 된다는 결과를 얻었는데, 스팸분류기 성능이 많이 개선되면 경쟁관계 인식 성능도 더욱 개선될 것으 로 예상된다. 4.4.3 거리 제약 기반 자질 필터링 기본 엔진에서 사용한 거리 자질은 거리 제약이 없이 거리정보를 무조건 자질로 사용하였다. 이번 실험에서는 거리 자질을 단순히 형태소, 토큰, 개체명 자질과 결합 해서 사용하는 것이 아니라, 제약 조건으로도 사용해서 정해진 거리 안에 있는 경우에만 자질로 추출하도록 제 약을 주었다. 거리 자질의 제약 조건은 바이트 단위로 계산되었고, 2부터 거리를 늘리면서 실험하였다. 그림 9 는 거리제약을 하지 않은 기본 엔진과 거리를 2부터 6 까지 제약한 경우의 성능 비교 결과를 보여준다. 그림 9 기본엔진 & 거리 제약 기반 필터링 Fig. 9 Performance when filtering by distance restriction 그림 8 기본엔진 & 스팸 분류 기반 필터링 Fig. 8 Performance when filtering by classifying spam 실험결과에 의하면 스팸 분류기를 필터링 단계로 사용 한 경우에 긍정, 부정, 전체정확도가 각각 1.9%, 0.2%, 0.2% 개선되었다. 10묶음 교차검증(10 fold cross validation) 방법으로 스팸 분류기 자체의 성능을 평가하였는데, 스팸 문장과 실험에 의하면 거리 제약을 주는 경우에 전반적으로 긍정 정확도가 높아지는 것을 확인하였다. 거리 제약을 2로 하는 경우에 긍정정확도가 가장 높았고 기본 엔진 보다 1.1% 향상되었다. 4.5 지도학습 분류 방법과 오류 필터링 3가지 방법의 결합 이번 실험에서는 본 논문에서 최종적으로 제안하는 경쟁관계 인식 방법론을 실험한 것으로, 지도학습 기반 분류 방법과 오류 필터링 3가지 방법을 모두 결합한 경 쟁관계 인식기의 성능을 측정하였다. 그림 10은 비교대 상인 기준선엔진 baseline(rule)과 baseline(choi)를 본 논문에서 제안하는 지도학습 기반 경쟁관계 인식 엔진 (proposed-base)과 지도학습 방법과 필터링 3가지 방법
기계학습 및 필터링 방법을 결합한 경쟁관계 인식 377 그림 10 지도학습 분류방법과 필터링 3가지 방법 결합 모델 성능 Fig. 10 Performance of the proposed system 을 결합한 엔진(proposed-hybrid)과 비교한 그래프이다. 실험 결과에 의하면 본 논문에서 최종적으로 제안하 는 지도학습방법과 3가지 필터링방법을 결합한 엔진이 긍정정확도와 전체정확도에서 가장 우수한 성능을 보였 다. 일반 관계추출방법에 비해서 긍정 정확도는 11.0% 의 성능향상이 있었고, 전체정확도는 14.5%의 성능이 개선되었다. 그러므로 본 논문에서 제안하는 모델이 경 쟁관계 인식에 상당히 효과적이라는 것을 알 수 있다. 4.6 오류 분석 본 논문에서는 경쟁관계 인식 성능 평가를 위해서 뉴 스 문서를 대상으로 학습셋과 평가셋을 구축하였다. 뉴 스 문서를 선택한 이유는 경쟁관계 표현이 뉴스 문서에 많이 나타나기 때문이다. 경쟁관계 표현이 나타나는 뉴 스 문서는 유시민-전여옥 논쟁, 100분 토론 최고 시청 률 과 같이 타이틀에 압축된 표현으로 많이 나타나는 것이 특징이다. 하지만, 평가셋이나 학습셋은 타이틀과 본문에 대해서 따로 비율을 정해서 수집하지는 않았다. 일반 관계추출기(baseline(choi))의 경우에 용언과 2개 개체간의 관계가 매우 중요한 자질로 사용된다. 그러므 로 용언에 대한 구문분석 정보가 중요한 자질로 작용하 는 경우에는 경쟁관계 인식을 잘 하는 편이지만, 용언이 중요한 자질로 사용되지 않는 경우에는 미인식되는 경 우가 많았다. 일반 관계추출기에서 잘 인식하는 경우와 미인식되는 경우의 예는 다음과 같다. 일반 관계추출기: 경쟁관계 인식 성공 100분토론' 구로다 "한국은 일본 앞에만 서면 작아져" 2G종료 제동에 KT 내리고 SKTㆍLGU + 올라 삼성ㆍLG 2G폰도 양보없다 일반 관계추출기: 경쟁관계 인식 실패 나경원ㆍ박원순 100분토론 가시돋친 설전 유시민 홍준표 빅뱅 100분토론 400회 특집서 입 심대결 4대강 비리 수사 놓고 야당-검찰 날선 공방 제안하는 경쟁관계 인식기(proposed-hybrid)의 경우 에는 경쟁관계 단서단어가 매우 중요한 자질로 사용되 었다. 그러므로 단서단어가 중요한 역할을 하는 문장의 경쟁관계는 잘 인식하는 반면에 단서단어가 없거나 구 문분석과 같은 구조 정보가 중요한 역할을 하는 문장의 경우에는 미인식되는 경우가 많았다. 위의 일반 관계추 출기에서 실패한 3개의 문장에 대해서는 제안하는 경쟁 관계 인식기는 제대로 인식하였다. 본 논문에 제안한 관 계추출기의 성공과 실패한 예제는 다음과 같다. proposed-hybrid: 경쟁관계 인식 성공 오세훈 따라잡은 한명숙 개표 내내 초박빙 우세 김두관 내 라이벌은 박근혜 비박 경선 고심 MS, 구글-모토로라 인수 견제 proposed-hybrid: 경쟁관계 인식 실패 6 2개표방송 시청률, KBS 웃고 SBS 울었다 아이패드 미 판매량, 갤럭시탭의 24배 갤럭시S3 가 아이폰5 를 이기는 방법 5. 결 론 기존의 일반적인 관계추출 방법론을 사용하는 경우에 는 경쟁관계 유형과 같이 특별한 유형에 대해서 낮은 성능을 보이므로 본 논문에서는 경쟁관계 인식에 특화 된 경쟁관계 인식기를 제안하였다. 다양한 실험을 통해 경쟁관계 인식에 알맞은 분류 알고리즘, 자질, 학습데이 터를 선정하였고, 오류필터링 방법을 지도학습 분류기와 결합해서 경쟁관계 중 긍정관계에 대한 인식 정확도를 높이는 방법론을 제안하였다. 본 연구에서 제안한 방법론을 기존의 일반 관계추출 방법론을 적용한 관계추출기와 비교하였고, 일반 관계추 출방법에 비해서 긍정 정확도는 11.0%의 성능향상이 있 었고, 전체정확도는 14.5%의 성능이 개선되었다. 경쟁관 계 인식기를 사용하는 응용분야에서 긍정 정확도가 매 우 중요한데, 제안한 방법론이 92.2%의 매우 높은 정확 도를 보인다는 것은 실제 필드에서도 기여할 수 있음을 보여준다. 제안한 방법론이 긍정 정확도는 높지만 부정 정확도 는 60.1%로 아직 낮고, 그렇기 때문에 전체정확도도 71.3%로 기존 연구와 비슷한 수준이다. 향후 연구로는 부정 정확도도 개선시킬 수 있는 필터링 방법을 같이 적용해서 긍정과 부정 정확도를 모두 개선시킬 수 있는 방법을 연구할 필요가 있고, 기존 연구에서 사용한 구문 분석 정보와 같은 구조 정보를 같이 사용할 수 있는 방 법을 연구할 필요가 있다.
378 정보과학회논문지 제42권 제3호(2015. 3) References [1] N. Bach, and S. Badaskar, "A review of relation extraction," Literature Review for Language and Statistics II, Carnegie Mellon University, 2007. [2] Y. Choi, P.M. Ryu, H. Kim, and C.K. Lee, "Extracting Events from Web Documents for Social Media Monitoring using Structured SVM," IEICE TRANSACTIONS on Information and Systems, Vol. 96, No. 6, pp. 1410-1414, 2013. [3] C. Aone, L. Halverson, T. Hampton, and M. Ramos-Santacruz, "SRA: Description of the IE2 System Used for MUC-7," Proc. of the Seventh Message Understanding Conference (MUC-7), 1998. [4] S. Park, K.S. Lee, and J. Song, "Contrasting Opposing Views of News Articles on Contentious Issues," Proc. of the 49th Annual Meeting of the Association for Computational Linguistics (ACL'11), pp. 340-349, 2011. [5] S. Shalev-Shwartz, Y. Singer, and N. Srebro, "Pegasos: Primal Estimated sub-gradient SOlver for SVM," Proc. of the 24th international conference on Machine learning(icml 07), pp. 807-814, 2007. [6] C.K. Lee and M.G. Jang, "Named Entity Recognition with Structural SVMs and Pegasos algorithm," Journal of Cognitive Science, Vol. 21, No. 4, pp. 655-667, 2010. (in Korean) [7] L. Bottou, and O. Bousquet, "The Tradeoffs of Large Scale learning," Proc. of 21st Annual Conference on Neural Information Processing Systems (NIPS 20), pp. 161-168, 2007. 김 현 기 정보과학회논문지 제 42 권 제 2 호 참조 이 충 희 1996년 한양대학교 전자계산학과(학사) 2001년 연세대학교 컴퓨터과학과(석사) 2014년 충북대학교 컴퓨터공학과(박사) 2001년~현재 한국전자통신연구원 선임 연구원. 관심분야는 자연어처리, 기계학 습, 정보검색, 질의응답 등 서 영 훈 1983년 서울대학교 컴퓨터공학과(학사) 1985년 서울대학교 컴퓨터공학과(석사) 1991년 서울대학교 컴퓨터공학과(박사) 1994년~1995년 미국 Carnegie Mellon 대학 기계번역센터 객원교수. 1988년~ 현재 충북대학교 전자정보대학 컴퓨터공 학과(교수). 관심분야는 자연언어처리, 한영기계번역, 정보검 색, 질의응답시스템