개최장소추출을위한 LGG 의구축 김경렬 O, 최동현, 김은경, 최기선한국과학기술원, 시맨틱웹첨단연구센터 {barnabas, cdh4696, kekeeo, kschoi}@world.kaist.ac.kr Construction of LGG for Extracting Meeting Location Kyoung-Ryol Kim O, Dong-Hyun Choi, Eun-Kyung Kim, Key-Sun Choi Semantic Web Research Center, KAIST 요약본논문에서는회의공지이메일을대상으로하는개최장소추출시스템에대하여소개한다. 개최장소추출시스템은두단계로구성되는데, 첫번째단계는본문에포함된개최장소의추출이고, 두번째단계는추출된개최장소의 Geocoding이다. 개최장소의추출을위하여문맥패턴을분석하여개최장소가포함된문장주변의패턴을반영하는 Local-Grammar Graph를구축하며, 개최장소의 Geocoding을위하여는 Addr2Geocode API를사용한다. 본논문은일정공지메일의개최장소를추출하기위한 LGG 방법론기반의어휘-통사적언어정보를기술하는것을목적으로한다. 주제어 : Information Extraction, Geocode, Local-Grammar Graph 1. 서론 최근애플의 iphone OS, 구글의 Android 와같은스마트폰운영체제에서는일정관리를효과적으로할수있도록여러가지정보인식및추출기술을제공하기시작했다. 예를들어, iphone 에서는이메일에간단한시간표현이발견되면자동으로이벤트를생성하여캘린더에추가할수있는링크를생성해주며, 간단한주소에대하여서도자동으로인식하여지도와연결되는링크를생성해주고있다 [1]. 본논문에서는회의공지이메일을대상으로, 본문에포함되어있는회의정보를추출하여캘린더에자동으로추가하는회의정보추출시스템의모듈인개최장소추출시스템에대하여소개한다. 개최장소추출시스템은두단계로구성되는데, 첫번째는본문에포함된개최장소를추출하는단계이고, 두번째단계는추출된개최장소의 Geocoding 이다. 본논문은 LGG(Local-Grammar Graph) 방법론에기초하여어휘 - 통사적언어정보를기술하고, 이로부터유한상태변환기 (Finite-State Transducer) 를구축하여본문에포함된개최장소를추출한다. 회의공지를대상으로회의정보를추출하는연구는영어권에서활발히진행되었는데 CMU 에서제작된 Seminar Announcement Corpus[2] 가대표적이다. 규칙을기반으로추출하는연구가꾸준히연구되어왔고 [3][4][5][6], 최근에는통계모델의학습을통하여일정정보를추출하는연구가주류를이루게되었다. Hidden Markov Models 을이용한연구 [7][8][9], Maximum Entropy Models 기반연구 [10][11][12], Conditional Random Fields 를이용한연구들이 [13][14][15] 대표적이다. 각방법론은데이터가가지 는특성에따라다른성능을얻을수있어, 주어진문제에적절한방법론을이용하는것이필요하다. 영어권의다양한연구결과에비하여한국어를대상으로일정정보를추출하는연구는상대적으로많이부족하다. 공개된일정공지말뭉치가존재하지않아연구자들이직접말뭉치를수집하여연구해왔으며, 연구의수도많지않다. 본논문에서는개최장소의추출문제에적절한방법론을찾기위하여, 회의공지이메일에포함된개최장소주변의어휘 - 통사적언어정보를분석및기술하여 LGG 를구축한다. LGG 로부터유한상태변환기를얻을수있는데, 이를이용하여개최장소를추출하는방법을설명한다. 추출된개최장소정보로부터 Geocode 를얻는과정도간략히소개한다. 본논문은다음과같이구성된다. 2 장에서는 LGG 방법론과이를작성하는도구인 UNITEX 에대하여소개하고, 3 장에서는개최장소추출방법에대하여설명하고, 4 장에서는추출된개최장소의 Geocoding 방법을설명한다. 5 장에서는실험및결과에대하여논의하고, 6 장에서결론및추후연구과제에관하여논한다. 2. LGG 와 UNITEX 2.1. Local-Grammar Graph Local-Grammar Graph 는프랑스의전산언어학자인모리스그로스에의해제안된언어기술모델로써, 특정영역별로부분적인언어정보를유한상태오토마타 (Finite-State Automata) 문법의형태로구현하고이를이용하여자연언어텍스트에대한자동분석및생성, 정보추출등을수행하는것을목적으로한다. 언어지식을형식화하는문법을최대한어휘화함으로써시스템
의효율성과정확성을향상시키며문법을방향성비순환그래프 (Directed Acyclic Graph) 방식으로구성함으로써문법구성의용이성과문법에대한가독성을극대화한점이특징이다 [16]. 2.2. UNITEX UNITEX 프로그램은그래프형식으로표상되는 LGG 문법에기반하여텍스트의자동분석및생성, 정보추출등을수행하는파서 (Parser) 이다. 현재마른느 - 라 - 발레대학의 IGM 연구소에서개발된 UNITEX 프로그램은, Gross 교수에의해주도된 Paris 7 대학의 LADL 연구소에서구현되었던 INTEX 프로그램의후속버전이다. UNITEX 프로그램은언어자원을효율적으로구출할수있도록도와주는그래픽툴이자, 텍스트처리를가능하게하는분석시스템으로써의역할을한다. UNITEX 로작성된 Local-Grammar Graph 는유한상태변환기로변환될수있으며, 이를통하여입력텍스트를대상으로텍스트분석및정보추출을수행할수있다. 특별히이프로그램은 Java 로작성되었기때문에 Windows/Mac OS/Linux 등의다양한환경에서쉽게구동할수있는특징을가지고, 유니코드를사용하기때문에영어및한국어를포함한다양한언어를지원한다 [16]. 3. 개최장소추출을위한 LGG 구축 3.1. 개최장소정보의속성 본논문에서사용된 개최장소 는회의공지이메일에서공지하는회의가열리는장소를의미하며, 장소에대한정의는 BNF 로표기된표 1 의내용과같다. 1. < > ::= < > < > < > < > < > < > ::= < ( )> < ( )> < ( )> ::= < > < > < > < > < > < > < > < > < > < > < > < > < > < > < ( )> ::= < > < > < > < > < > < > < > < > < > < > < > < > < > ::= < > < > < > < > < > ::= < > ::= 1 2 3 4 5 6 7 8 9 을위하여장소, 시간, 주제, 행위주체, 레이블, 이음문자열, 기타정보 7 가지정보타입의대분류아래에새로운정보타입이발견되면추가하는방식으로작성되었다. 예를들어, 장소 : 는 ' 레이블 ' 분류에해당되며, 장소레이블을의미하는 'loclbl' 이라는타입을가진다. 이러한방식으로총 110 개의세부타입들이작성되었다. 정보타입의세부내용은부록에첨부하였다. LGG 를구성하는패턴은그림 1 의예와같이정보타입의열로이루어지며, 표 2 와같은어휘 - 통사적구조를가지는이메일로부터개최장소를추출할수있도록작성되었다. 그림 1 에빨간색괄호로둘러싸인부분은추출될개최장소 (locmtg) 를의미하며, 개최장소의내부패턴은그림 2 와같은패턴을가진다. 그림 2 에서 <NB> 는정수, <PNC> 는특수문자, <MOT> 는토큰을의미한다. 2. : 2010 1 13 ( ) 2 ~ 4 : 2. : 2003 5 17 ( ) 10:30 ~ 16:30 3. : 4. 1. : 04 11 17 9:30-12:30 2. : 3 3. : 1 -, 2-1. LGG 3.2. 개최장소추출을위한 LGG 구축 본연구에서구축하고자하는개최장소추출을위한 LGG 는수집된회의공지이메일말뭉치에나타난개최장소주변정보의패턴을귀납적으로검토하여어휘 - 통사적으로기술되었으며, 패턴이작성된범위는개최장소가포함된문장과앞, 뒤문장까지로하였다. 각패턴작성 2. (locmtg) LGG 작성된 LGG 는개최장소의종류와개수에따라크게
3 가지로분류되는데, 첫번째는 1 개의개최장소를포함하는패턴, 두번째는 N(>1) 개의개최장소를포함하는패턴, 세번째는집결장소, 예상장소, 장소미정과같이개최장소이지만속성이개최장소와차이가있는장소를포함하는패턴이다. 각분류아래에는해당패턴으로추출가능한장소의타입별로구분된목록을가진다. 표 4 는 LGG 의분류를나타낸다. 개최장소 1_1, 개최장소 1_2 과같이표현된형태는 1 개의개최장소의일부장소정보가 2 개로분리되어작성된경우를표현한다. 예를들어, 표 3 과같이, 무역협회중회의실 과 삼성동트레이드타워 51 층 은같은장소를나타내고있지만, 예문에서는굳이괄호로구분을하고있다. 3. 2 1. 일시및장소 : 2010. 5. 12( 수 ) 14:00~16:00, 무역협회중회의실 ( 삼성동트레이드타워 51 층 ) 4. LGG 1. 1 1.1. ( ) 1.1.1. 1.1.2. 1_1 1_2 1.2. ( ) + 1.2.1. 1.2.2. 1_1 1_2 1.3. ( ) + 1.3.1. 1.3.2. 1_1 1_2 1.3.3. 1 2 1.3.4. 1.4. (, ) 1.4.1. ( ) 1.4.2. 1_1 ( ) 1_2 1.4.3. 1_1 ( ) 1_2 2. N (N>1) 2.1. 2 2.2. 3 2.3. 4 3. 3.1. 3.1.1. 3.1.2. ( ) 3.2. 3.2.1. 3.2.2. 1 2 3.3. 특별히표 4 의분류 1.2, 1.3.4 를이용하여개최장소 와주소를함께추출할수가있다. 예를들어, 표 5 의개최장소는 울산광역시울주군상북면등억리 27 번지 라는주소에위치한 먹고쉬었다가 라는음식점이며, 표 4 의분류 1.2.1 에해당하는예이다. 이처럼개최장소의주소를함께추출할수있는경우는 4 장에서소개할 Addr2Geocode API 를통하여바로 Geocode 를얻을수있다. 5. 3. 장소 : 울산광역시울주군상북면등억리 27 번지먹고쉬었다가 (052-263-1206) 4. 개최장소의 Geocoding Geocoding 이란, 토지내중심점의지리적좌표로서토지를구분하는방법으로특정지도투영법에의해지표상의위치를 X, Y 좌표로나타내는방법이다 [17]. 이를표현하는좌표계의종류와제정된표준의수는상당히다양하지만, WGS84, TM128 등몇가지가사실상표준으로채택되어 Google Maps, Naver 지도뿐아니라 OpenStreetMap 등의웹기반지도서비스에서사용되고있다. 본논문에서는최근가장많이사용되고있는 WGS84 를사용한다. 개최장소를 Geocoding 하는방법은크게 2 가지로나뉜다. 첫째는주소정보가포함되어있는경우로 Addr2Geocode API 를사용하며, 둘째는주소정보가포함되지않은경우로외부지리정보자원에장소명으로검색하는방법이다. 본논문에서는첫번째방법중에서도번지수까지포함하는주소를가지는경우를다룬다. 주소정보의일부만포함하는경우와두번째방법은본논문에서다루지않는다. 주소의 Geocoding 을위하여 Daum 에서제공하는 Addr2Geocode API 를사용하였다. API 의입력은번지를포함하는주소문자열이며, 출력으로해당주소의 WGS84 경위도좌표를 RSS/XML/JSON 형태로반환한다. 5. 실험및결과 본논문에서사용한회의공지이메일말뭉치는인터넷을통하여 ' 공지 ' 라는검색어로 1,011 개의이메일을수집하였다. 3 명의서로다른어노테이터가어노테이션작업을수행하였으며, 어노테이션간충돌이발생하였을때에는또다른컨쥬게이터가충돌해소작업을진행하였다. 그중에서순서대로선택된 555 개의문서에대하여 LGG 를구축하여실험을진행하였다. 39 개의 LGG 가작성되었으며, 그중 7 개는개최장소와주소를함께추출
할수있는형태이고나머지 32 개는개최장소만을대상으로추출하는형태이다. 표 6 은작성된 LGG 를적용하여추출된결과이다. 'Exact' 는어노테이션된개최장소와시스템이추출한개최장소가완전히일치한결과이고, 'Contain' 은시스템이추출한결과가어노테이션된개최장소를포함하는경우의결과이다. Exact, Contain 에대하여각각 93.41%, 99.41% 의높은 Recall 을보였으나 Precision 에대하여는 82.11%, 87.39% 로상대적으로낮은수치를보였다. Precision 이낮은원인으로는 LGG 가지나치게일반화된경우, 조사가개최장소뒤에붙어있는경우등을찾을수있었다. 특별히, 조사가분리된명사를분석하기위하여필요한한국어사전이 UNITEX 에서요구하는방식으로구현되어야한다. 하지만, 라이센스의문제로인하여사용이어렵기때문에조사가개최장소뒤에붙어있는경우는후처리를통하여조사를제거해주는방법이추가되어야한다. 또한, 표 7 은개최장소 - 주소를함께추출가능한경우의패턴을적용하여추출된결과를보여준다. 번지수를포함한주소를대상으로하였기때문에그수가많지않다. 19 개중 10 개만이개최장소와주소가함께인식되었는데에러를분석하여보면, 주소와개최장소의문서내위치가상당히떨어져있어 Local-Grammar 만으로는처리가어려운경우들이었다. 6. 39 Path LGG 555 Exact Contain Relevant 683 Retrieved 777 Ret. & Rel. 638 679 Recall 93.41% 99.41% Precision 82.11% 87.39% F-measure 87.40% 93.01% 7. - 7 Path LGG 555 Exact Relevant 19 Retrieved 10 Ret. & Rel. 10 Recall 47.62% Precision 100.00% F-measure 64.52% 6. 결론 본논문에서는회의공지이메일을대상으로개최장소를추출하는문제를해결하기위하여 LGG 를구축하는방법을소개하였다. 555 개의이메일에포함된개최장소를추출하기위하여 39 개의패턴만이사용되어 Exact, Contain 일치에대하여각각 F-measure 87.40%, 93.01% 의높은추출성능을보였다. 세밀한일반화및후처리작업등을통하여 Precision 이더상승할수있을것으로기대한다. 또한, 이러한어휘 - 통사론적분석결과는추후다른방법론을적용하기위한근거자료로써활용도가능할것으로예상한다. 추후연구할과제는, 충분히분석된 LGG 결과를바탕으로개최장소온톨로지를구축하여정보타입간의온톨로지추론을통하여개최장소추출및주소매핑을수행하는연구이다. 이에앞서, 수집된이메일의 50% 정도를대상으로실험하였기때문에나머지데이터에대한 LGG 구축과일반화작업이필요하다. 뿐만아니라, 본연구는한국어개최장소만을대상으로실험을수행하였지만, 특정언어에의존적인방법론이아니기때문에추후영어등의다른언어에대하여도같은방법으로실험하여언어에독립적인방법론으로일반화해볼수있다. 감사의글 본 논문은 지식경제부 산업원천기술개발사업 (10035348, 모바일플랫폼기반계획및학습인지모 델프레임워크기술개발 ) 의지원으로수행되었음 참고문헌 [1] Mail Data Detection, Apple Inc., 2008, http://itunes.apple.com/podcast/mac-quick-tips/id2 57243321 [2] Seminar Announcements Dataset, CMU, http://www.cs.cmu.edu/~dayne/seminarannouncem ents/ [3] Muggleton, S., Buntine, W., "Machine invention of first-order predicates by inverting resolution", Proceedings of the 5th International Conference on Machine Learning, 1988 [4] Riloff, E., "Automatically constructing a dictionary for information extraction tasks", Proceedings of the 11th National Conference on Artificial Intelligence (AAAI), 811-816, 1993 [5] Kim, J., Moldovan, D., "Acquisition of linguistic patterns for konwledge-based information extraction", IEEE Transaction Knowledge Data Engineering, 1995 [6] Chai, J., Biermann, A., Guinn, C.,Two dimensional generalization in information extraction, Proceedings of the 16th AAAI National
Conference on Artificial Intelligence (AAAI), 1999 [7] Seymore, K., Mccallum, A., Rosenfeld, R., "Learning hidden Markov model structure for information extraction", Proceedings of the 16th AAAI National Conference on Artificial Intelligence (AAAI), 1999 [8] Freitag, D., Kushmerick, N., "Boosted wrapper induction", Proceedings of the ECAI Workshop on Machine Learning for Information Extraction, 2000 [9] Ray, S., Craven, M., "Representing sentence structure in hidden Markov models for information extraction", Proceedings of the 17th International Joint Conference on Artificial Intelligence (IJCAI01), 2001 [10] Chieu, H. L., Ng, H. T, "A maximum entropy approach to information extraction from semistructured and free text", Proceedings of the 18th National Conference on Artificial Intelligence (AAAI), 2002 [11] Kambhatla, N., "Combining lexical, syntactic, and semantic features with maximum entropy models for extracting relations", Proceedings of the 42nd Annual Meeting of the Association for Computational Linguistics (ACL), 2004 [12] Turmo, J., Ageno, A., Catala, N., "Adaptive information extraction", Journal of ACM Computing Surveys (CSUR), Vol.38-2, 2006 [13] Lafferty, J., Mccallum, A., Pereira, F., "Conditional random fields: probabilistic models for segmenting and labeling sequence data", Proceedings of the 18th International Conference on Machine Learning (ICML), 2001 [14] Cox, C., Nicolson, J., Finkel, J., Manning, C., Langley, P., "Template sampling for leveraging domain knowledge in information extraction", First PASCAL Challenges Workshop, 2005 [1] Lee, C. K., Hwang, Y. G., Oh, H. J., Lim, S. J., Heo, J., Lee, C. H., Kim, H. J., Wang, J. H., Jang, M. G., Fine-Grained Named Entity Recognition Using Conditional Random Fields for Question Answering, Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, 2007 [15] 남지순, " 웹문서의미지식추출을위한 LGG 의구축 ", 프랑스어문교육제 25 집, 105-112, 2007 [16] 강영옥, 이동연, " 위치정보제고를위한주소표시제도개선방안 ", 국토계획제 31 권제 6 호, 5-314, 1996 [17] Google Maps, http://maps.google.com/ [18] Naver 지도, http://map.naver.com/ [19] OpenStreetMap, http://www.openstreetmap.org/ [20] Daum 주소좌표변환 API, http://dna.daum.net/apis/maps/reference 부록 1. 분류별정보타입 분류정보타입설명 장소 시간 주제 행위주체 locdst 장소 : 개최예정장소 locare 장소 : 지역 ( 장소 +dirwrd 를포함하는지역 ) locadr locgtr locgnr loclmk locmtg locold locswy locslt locunk locway loccnf locdstcnf loceqv 장소 : 주소 장소 : 집결장소 장소 : 일반장소 장소 : 랜드마크 장소 : 개최장소 장소 : 장소의이전이름 장소 : 지하철역 장소 : 여러장소중하나로개최장소선택예정 장소 : 장소미정 장소 : 거리 (way) 장소확정지시어 예정장소지시어 동일한장소표현접속사및기호 loctyp 장소의타입 ( 업종 ) swysta dirwrd diswrd timdur timend timgnr timstr titmtg tpcmtg perlst pernam pertit orgnam 지하철역명 방향성을나타내는단어 거리 (distance) 를나타내는단어 시간 : 기간 시간 : 종료시간 시간 : 일반시간 ( 시작, 종료시간이아닌시간표현 ) 시간 : 시작시간 모임제목 모임주제 사람목록 사람이름 사람직책 기관이름
레이블 이음문자열 adrlbl agdlbl anclbl applbl brglbl chglbl dirlbl feelbl gtrlbl hstlbl inqlbl lcalbl lctlbl loclbl noplbl mtglbl phnlbl prslbl reflbl scllbl symemp spnlbl tgtlbl timlbl tlclbl tprlbl tpclbl weblbl decprd loclmk2loclmk locgnr2locare locgnr2titmtg locgnraft locmtg2locgnr locmtg2locmtg locmtg2pernam 주소레이블안건레이블진행자레이블신청레이블준비물레이블변경정보레이블오는길레이블참가비레이블모임집결레이블주최레이블문의레이블지역 ( 지역 : 의형태 ) 레이블개최장소및시간레이블개최장소레이블인원레이블모임레이블전화번호레이블발표자레이블참고자료레이블규모레이블강조심볼후원레이블대상레이블시간레이블시간및개최장소레이블교통편레이블주제레이블홈페이지레이블서술성종결사랜드마크사이의문자열일반장소와지역사이의문자열일반장소와제목사이의문자열일반장소뒷쪽에나오는문자열개최장소와일반장소사이의문자열개최장소사이의문자열개최장소와사람이름사이의문자열 locadr2locmtg locadr2timstr locway2locmtg orgnam2orgnam orgnam2locgnr orgnam2timgnr orgnam2tpcmtg diswrd2locway locswy2locare locswy2locswy locway2dirwrd pernam2locare pernam2locmtg pernam2titmtg pernam2tpcmtg pernamaft pernambef phnnbr2adrlbl timstr2loclbl timstr2locmtg timstr2timend timstr2titmtg timstraft titmtg2locadr titmtg2locmtg titmtg2pernbr titmtg2timstr titmtgbef tpcmtg2locmtg tpcmtg2titmtg tpcmtg2perlst tpcmtgaft timend2locmtg locadr2locadr locare2pernam 주소와개최장소사이의문자열 주소와시작시간사이의문자열 거리 (way) 와개최장소사이의문자열 기관이름과기관이름사이의문자열 기관이름과일반장소사이의문자열 기관이름과일반시간사이의문자열 기관이름과모임주제사이의문자열 거리를나타내는단어와거리사이의문자열 지하철역과랜드마크장소사이의문자열 지하철역사이의문자열 거리 (way) 와방향을나타내는단어사이의문자열 사람이름과지역사이의문자열 사람이름과개최장소사이의문자열 사람이름과모임제목사이의문자열 사람이름과모임주제사이의문자열 사람이름뒤쪽에나오는문자열 사람이름앞쪽에나오는문자열 전화번호와주소레이블사이의문자열 시작시간과개최장소레이블사이의문자열 시작시간과개최장소사이의문자열 시작시간과종료시간사이의문자열 시작시간과제목사이의문자열 시작시간뒤쪽에나오는문자열 모임제목과주소사이의문자열 모임제목과개최장소사이의문자열 모임제목과사람이름사이의문자열 모임제목과시작시간사이의문자열 모임제목앞쪽에나오는문자열 모임주제와개최장소사이의문자열 모임주제와모임제목사이의문자열 모임주제와사람목록사이의문자열 모임주제뒤쪽에나오는문자열 종료시간과개최장소사이의문자열 주소사이의문자열 장소 ( 지역 ) 과사람이름사이의문자열 locmtg2phnlbl locmtg2timstr locmtg2titmtg locmtg2tpcmtg locmtgaft locmtgbef 개최장소와전화레이블사이의문자열개최장소와시작시간사이의문자열개최장소와모임제목사이의문자열개최장소와모임주제사이의문자열개최장소뒷쪽에나오는문자열개최장소앞쪽에나오는문자열 기타정보 webadr phnnbr phnnbraft addinf 홈페이지주소 전화번호 전화번호뒤쪽에나오는문자열 추가정보 LF <Enter>, line feed