대화형에이전트의주제추론을위한계층적베이지안네트워크의자동생성 877 대화형에이전트의주제추론을위한계층적베이지안네트워크의자동생성 (Automatic Construction of Hierarchical Bayesian Networks for Topic Inference of Conversational Agent) 임성수 조성배 (Sungsoo Lim) (Sung-Bae Cho) 요약최근에대화형에이전트에서사용자질의의주제추론을위하여베이지안네트워크가효과적임이발표되었다. 하지만베이지안네트워크는설계에있어서많은시간이소요되며, 스크립트 ( 대화를위한데이타베이스 ) 의추가 변경시에는베이지안네트워크도같이수정해야하는번거로움이있어대화형에이전트의확장성을저해하고있다. 본논문에서는스크립트로부터베이지안네트워크를자동으로생성함으로써베이지안네트워크를이용한대화형에이전트의확장성을높이는방법을제안한다. 제안한방법은베이지안네트워크의구성노드를계층적으로설계하고, Noisy-OR gate 를사용하여베이지안네트워크의조건부확률테이블을구성한다. 피험자 10 명이대화형에이전트를위한베이지안네트워크를수동설계한것과비교한결과제안하는방법이효과적임을알수있었다. 키워드 : 대화형에이전트, 베이지안네트워크, 스크립트 Abstract Recently it is proposed that the Bayesian networks used as conversational agent for topic inference is useful but the Bayesian networks require much time to model, and the Bayesian networks also have to be modified when the scripts, the database for conversation, are added or modified and this hinders the scalability of the agent. This paper presents a method to improve the scalability of the agent by constructing the Bayesian network from scripts automatically. The proposed method is to model the structure of Bayesian networks hierarchically and to utilize Noisy-OR gate to form the conditional probability distribution table (CPT). Experimental results with ten subjects confirm the usefulness of the proposed method. Key words :conversational agent, Bayesian network, script 1. 서론 인터넷사용이보편화됨에따라서인터넷을통하여많은정보가쏟아져나오고있다. 이러한정보의홍수속에서사용자와정보를주고받을수있는효과적인방법의필요성이크게늘고있다. 이에따라서사용자가원하는정보를제공해주기위한검색엔진들이많이개발되었으나, 주로키워드에기반한검색을통하여사이트내의정보를제공하므로사용자의의도와는달리불 본연구는정보통신부및정보통신연구진흥원의대학 IT연구센터지원사업의연구결과로수행되었음. IITA-2005-(C1090-0501-0019). 학생회원 : 연세대학교컴퓨터과학과 lss@sclab.yonsei.ac.kr 종신회원 : 연세대학교컴퓨터과학과교수 sbcho@cs.yonsei.ac.kr 논문접수 : 2005년 3월 10일심사완료 : 2006년 9월 4일 필요한정보를찾아주는경우가많다. 그리고사용자와의상호작용을위해서메뉴, 사용자프로그래밍등의사용자입력과그림, 도표등의출력이많이사용되었지만이들은포함하는정보의양이정적이고사용자가친숙하지않은경우가많아부가적인교육이필요하며, 한쪽방향으로만정보를전달하기때문에사람과의상호작용을위한매체로사용되기에는많은한계가있다. 이러한문제를해결하기위한대안으로서자연어로정보를주고받으며사용자에게필요한정보를제공하는대화형에이전트에관한연구가진행중이다. 여러연구에서정보를교환하고사용자의도를파악하는데에, 대화가매우효과적인방법임이밝혀졌으며 [1], 대화를통한처리는좀더친숙한사용자인터페이스를제공한다 [2]. 전통적인대화형에이전트는패턴매칭기술을통해사용자의질의에대응하는답변을제공한다. 그러나미
878 정보과학회논문지 : 소프트웨어및응용제 33 권제 10 호 (2006.10) 리설계된질의패턴과사용자질의패턴이일치하는경우에만답변을제공하기때문에대화유형이단순하며, 사용자의의도를잘못파악하여잘못된답변을하는경우가종종발생한다. 이에따라서최근에대화형에이전트에서사용자질의의주제를확률적으로추론하기위하여베이지안네트워크가적용되어에이전트의성능을높였으나 [3] 베이지안네트워크설계는초보자들이쉽게접근하지못하며전문가들도설계에많은시간이소요된다. 그리고대화형에이전트에서의베이지안네트워크는대화의주제에의존적이므로시스템의도메인이변경되면네트워크를수정해야하는번거로움이있다. 이러한설계의어려움은대화형에이전트의확장성을저하시키고있다. 본논문에서는베이지안네트워크를질의-답변데이타베이스인스크립트로부터자동으로생성함으로써베이지안네트워크이용한대화형에이저트의확장성을높이는방법을제안한다. 베이지안네트워크가자동으로생성되면대화형에이전트설계에드는시간비용이감소되며, 스크립트만설계하면되므로초보자들도쉽게대화형에이전트를설계할수있다. 2. 배경 2.1 대화형에이전트에이전트시스템이란인간이처리해야할일련의작업들을컴퓨터가대신하여처리하는시스템을포괄적으로일컫는다. 이시스템은어떤환경에서보다적극적, 지적으로작업을수행하는응용프로그램이다. 에이전트들은일반적으로사용자의특별한지시가없어도스스로판단하여행동하는자율성, 에이전트가스스로문제에대한솔루션을파악하여자신의능력을강화하는학습성, 사용자의요구를요구한호스트에서수행하지않고해당호스트로이동하여직접수행하는이동성, 다른에이전트들과서로메시지를주고받는사교성, 이런 4가지특성을갖는다 [4]. 대화형에이전트는자연어로해당분야의전문지식을알려주는메신저기반의대화형전문가시스템이다 [5]. 인간이서로의사소통수단으로사용하는자연어를인간 -컴퓨터간의통신에사용한다면, 기존의컴퓨터제약적이거나사용자제약적인시스템에서제공하는메뉴와같은정보전달방식과는달리, 상호작용을풍부하게하고단순히하나의단어나사용자입력을통해서전달하는정보에비해훨씬복잡한정보를포함할수있다 [1]. 최초의대화형로봇으로는 1966년 MIT대학의 Weizenbaum 교수가만든 ELIZA가있다 [6]. ELIZA는사람과기계사이의자연어의사소통을연구하기위해만들어진프로그램으로사용자가던진문장을분석하여대답에필요한키워드를추출한후이미프로그램되어 있는문장에키워드를치환하여대답한다. ALICE(Artificial Linguistic Internet Computer Entity) 라는대화형로봇은자연스러운대화를이끌어내기위하여패턴매칭기법을사용하였다 [7]. 대화에사용되는지식, 즉패턴은 AIML(Artificial Intelligence Markup Language) 이라는 XML형태의파일로저장되어있다. ALICE는 AIML파일에사용자가물어볼만한질문과그에해당하는대답을기술하고사용자가물어보는문장과 AIML파일에패턴으로기술된문장을비교하여하나의와일드카드 (*) 를허용하는범위내에서정확하게매칭되는것만을선택하여답을해주는시스템이다. 그러나이러한시스템은질문을답변에매칭시킬때키워드에기반하여단순한패턴매칭을사용하기때문에사용자의의도를반영한답변을정확히제시하지못하는단점이있다, 또한이러한점을개선하기위해서는답변데이타베이스구축시많은노력이들어가야한다 [8]. 이러한단점들을보완하기위해서본논문의대화형에이전트에서는질의문형분석을통한사용자의도파악, 베이지안네트워크를통한주제추론등의기법을사용한다 [3,8]. 2.2 베이지안네트워크실세계의응용애플리케이션에서환경은매우불확실하며, 에이전트는불완전하고노이즈가많은정보를가지고불확실한환경에서행동을결정해야만한다. 그런에이전트의설계자는이런상황에서어떤행동을할것인지를결정하는에이전트를갖기위한방법이필요하다. 베이지안확률추론은지능형에이전트나시스템이불확실한상황에서정보를표현하거나추론하는대표적인방법이다 [9]. 베이지안네트워크에서노드는실제환경변수를나타내고, 아크는각변수간의의존성을나타낸다. 네트워크를구축하기위해서는구조를설계하고, 각노드에맞는확률분포를정해주어야하는데, 보통구조는전문가에의해설계되고, 확률분포는전문가가계산하거나혹은주어진데이타를통해계산된다. 네트워크를학습한후어떤상황에대한증거가관찰되면그증거를바탕으로각노드의조건부확률테이블과독립조건을이용, 베이지안추론알고리즘을통해각노드의상태에대한확률이계산된다. 위수식은베이지안네트워크를나타낸것이다. 는베이지안네트워크의구조 와확률변수 를나타내고, 는네트워크의모든변수간의결합확률분포를나타낸다. 방향성비순환그래프인베이지안네트워크구조 라고하면, 는실제문제의환경변수인노드를의미하고, 는아
대화형에이전트의주제추론을위한계층적베이지안네트워크의자동생성 879 크의집합으로각변수간의의존관계를나타낸다. 각변수 에대해서, 조건부확률분포는 로나타낼수있고, 여기서 는변수의부모집합이다. 2.3 베이지안네트워크학습베이지안네트워크를학습하는문제는주어진평가척도에따라데이타의훈련집합 (training set) Ξ에가장잘부합되는네트워크를구하는것이며, 여기서 Ξ는모든 ( 또는적어도몇몇 ) 변수에대한값의사례집합이다. 네트워크를구한다는것은 DAG 구조와 DAG의각노드에연관된조건부확률테이블 (conditional probability table, CPT) 을함께구하는것을의미한다 [10]. 만일네트워크의구조가알려져있다면 CPT만을구하면된다. 하지만 CPT를구하는문제는난해하여전문가들도문제영역에알맞은구조만구하고 CPT는얻지못하는경우가종종있다. 네트워크의구조가알려진경우, 만일문제영역에해당하는표본통계자료가준비되어있다면, 조건부확률을이용하여 CPT의값을구할수있다. 하지만일부표본통계는매우작은수의예제에만의존하게되며, 이경우해당되는확률은잘못추측할수도있다. 또한표본통계자료가완전하게제공되지않고몇몇레코드에는대응값이없는변수가존재할수있다. 이러한경우에는 Monte-Caro Methods, Gaussian Approximation, EM Algorithm 등의기법을이용하여 CPT값을얻어낼수있다 [10]. 베이지안네트워크의 DAG 구조가알려져있지않은경우에는네트워크구조를평가하는평가척도를도입하여네트워크구조를탐색하며가장적합한네트워크를얻어야한다. 그러나네트워크의크기가작으면간단하게구할수있지만, 네트워크의크기가커지게되면탐색해야할네트워크구조의양이기하급수적으로증가하게되므로상당한시간이필요하다. 이러한문제는 NP-hard라는것은이미증명되었다 [11]. 따라서모든네트워크를탐색하는것은불가능하므로유전자알고리즘과같은휴리스틱한방법을사용한다 [12]. 3. 대화주제추론을위한베이지안네트워크자동생성 3.1 대화형에이전트대화형에이전트는그림 1과같이사용자질의를분석하여적절한답변을출력한다. 먼저전처리단계에서는사용자입력질의분석을통해필요한정보를추출한다. 도메인에사용되는키워드를정의하고, 사용자질의에포함된키워드를추출하여질의분석에사용한다. 대화는자연어를기반으로이루어지기때문에동일질의에대한사용자들의표현이다양하다. 같은의미의키워드에대해서도사용자마다다른키워드를입력할수있기때문에이런경우를모두고려한설계는쉽지않다. 따라서동의어사전을이용한키워드데이타베이스를구축함으로써키워드간전환이용이해지도록한다. 사용되는동의어사전은특정주제나도메인에관련된키워드의의미적구조와관계를규칙기반방식으로정의한것으로같은의미로표현될수있는다른단어들의여러키워드들을모아대표키워드로제시한다. 이로써사용자에따른단어표현의차이를극복하여동의어및중의어의문제를처리하고좀더융통성있는답변수행이가능하게된다. 그림 1 대화형에이전트구조도 표 1은대상도메인지식과관련된용어와개념의다양성을처리하기위한동의어사전의예이다. 시스템실행시질의문장이입력되면전처리과정에서키워드추출과동시에동의어사전파일을불러들여개별키워드에대한변환작업이수행되며, 최종적으로변환된대표키워드로질의를분석한다. Attribute ( 대표키워드 ) 표 1 동의어사전의예 Value 1 ( 관련동의어 ) Value 2 Value 3 Value n 무엇 무어 뭐 머 언제 며칠 날짜 어느때 색상 색조 색깔 빛깔 무게 중량 근량 하중 이렇게분석된사용자질의는미리구축된지식구조의패턴- 답변쌍과비교하여동일한패턴을갖는패턴- 답변쌍의답변을선택하여사용자에게제공한다. 패턴- 답변쌍은 XML 형식을가진스크립트파일로저장된다. 표 2는스크립트의형식을 BNF로나타내고있다.
880 정보과학회논문지 : 소프트웨어및응용제 33 권제 10 호 (2006.10) 표 2 스크립트의형식 [letter] := 영어 한글 [word] := [letter] + [topic] := "<topic>" [word] + "</topic>" [keyword] := "<keyword>" [word] + "</keyword>" [answer] := "<answer>" [word] + "</answer>" [class] := "<class>" [ 문형 ]+ "</class>" [script] := "<script>" [topic] [class] [keyword] + [answer] + "</script>" [script_file] := [script]* 스크립트는 AIML의형식을빌어간단하면서도다양한질의와답변입력이가능한형식을가지므로접근이용이하다 [13]. [topic] 은스크립트의주제를나타내는것으로베이지안네트워크를통하여추론할주제를말한다. 그리고 [class] 는질문문장의문형을규정하고, [keyword] 는질의의핵심어들을의미하는것으로순차패턴매칭에서사용된다. 스크립트는동일질문에대하여비슷한여러개의답변을할수있도록설계되었으며또한, 같은것을묻는질문이나질문의형식이다른경우를하나의 [script] 로처리하기위해서여러개의문형과핵심어리스트를입력할수있도록설계되었다. 스크립트의평가는그림 1에서보여주는바와같이 BN 주제추론과순차패턴매칭, 그리고문형분석을통해서이루어진다. 일반적인대화는사용자의도를표현하는데있어서그의도와관련된모든정보를한문장에포함하지는않는다. 보통이전대화에서사용된정보를이용하기도하고, 생략과우회등의기법을이용하여최소한의정보만을포함한문장을사용한다. 또한앞에서지칭된내용을가리키는대명사등을사용하며일반적인상식에대한내용은생략한다. 이러한대화를처리하기위해서는대화의문맥을잘유지하는것이필요하다 [14]. 사용자와유연한대화를유지하기위해서는현재지속되는문맥을파악하는것 [15] 과문맥이변하는것을잘처리해야한다 [16]. 이두가지를처리하는데에는대화의방향성을파악하는것이중요하며, 이전단계에서의대화에대한분석이필요하다. 본논문에서는대화흐름을파악하며주제추론을할수있도록베이지안네트워크를적용한다. 베이지안주제추론에서사용자질의로부터주제추론의결과가나타나지않으면, 이전질의문의정보를함께활용하여한번더추론함으로써사용자의의도를보다명확하게파악할수있다. 표 3은 BN 주제추론과정을보여주고있다. 주제가선택되면해당주제를갖는스크립트와질의문에서추출한키워드간의순차패턴매칭을수행한다. 순차패턴매칭의평가점수는문서분류에서많이사용되는성능평가기준인 F-measure 를적용한다. F-measure 표 3 BN 주제추론과정 대상영역키워드노드 K = {k 1,..., k n} 주제노드 T = {t 1,..., t n} 내부노드 I = {i 1,..., i n} 추론알고리즘단계 1: 사용자질의에포함된키워드노드의확률값을 1 로, 포함되지않은것을 0 으로설정단계 2: 베이지안추론알고리즘실행, 각노드의확률값계산단계 3: 임계값을넘는가장높은주제노드선택 & 종료, 임계값을넘는주제노드가없다면단계 4 로이동단계 4: 베이지안노드초기화 & 현재질의와이전질의에대해서단계 1 수행단계 5: 임계값을넘는가장높은주제노드선택 & 종료, 임계값을넘는주제노드가없다면주제선택포기 는정확률과재현율을함께고려하여성능을측정하는 도구로다음과같이평가값을얻는다. 본논문에서는 정확률과제현율을동등하게고려하려 F-measure의 α 값을 1로설정하였다., 입력질의패턴- 답변쌍 포함 미포함 포함 A B 미포함 C D A, B, C, D : 빈도수 문형분석은오토메타를사용하여사용자입력을표 4 와같이질의문형 19개, 서술문형 11개의총 30개문형으로분류하여사용자의도를파악한다. 이러한문형분석을통하여사용자의질의의도를대략적으로추측할수있다. 1차질문형이나평서문형은하나의부류로만분류될수있으며, 2차인경우에는하나이상으로분류될수있다. 그림 2는 1차질문형인 Who 에대한오토메타 질의대분류 1 차질문형 2 차질문형 1 차평서문형 표 4 문형분류 문형 Can, Who, WhatIf, Method, Location, Reason, Should, Time, Description, Fact, miscellaneous Compare, Confirm, Cost, Direction, DoHave, Example, More, Obtain Message, Act, Is, Have, Want, Fact, Miscellaneous 2 차평서문형 Cause, Feeling, Time, Conditiona
대화형에이전트의주제추론을위한계층적베이지안네트워크의자동생성 881 그림 2 Who 질문형분류오토메타를나타낸다. 그림에서보듯이오토메타의상태 (state) 는사용자질의의단어를입력심볼 (input symbol) 로하여상태이동 (transition) 을한다. 오토메타는대화문장의구조적정보를표현할수있어유용하지만, 정해진경로를따라서면상태가변화하므로유연성이떨어지는단점이있다. 본논문에서는스크립트선택에있어서주제추론과는달리보조적인자료로사용한다. 즉, 주제추론은스크립트평가시선택된주제에대해서만패턴매칭을수행하는반면에문형분석은질의문과스크립트의문형이일치하지않을경우, 패턴매칭점수에 p (0<p<1) 를곱하여패널티를준다. 본논문에서는 p의값으로 0.7을선택하였다. 3.2 계층적베이지안네트워크의자동생성 3.1절에서알아본바와같이본논문의대화형에이전트는사용자의도추론을위해베이지안네트워크를사용한다. 베이지안확률추론은불충분한정보를가진환경을표현하고추론하는대표적인기법들중하나로, 여러분야에서현실세계의불확실성을극복하기위해적용되어왔다. 하지만베이지안네트워크는설계가복잡하고사용하기어려워초보자가접근하기힘들다. 본논문에서는베이지안네트워크의이러한한계점을극복할수있도록대화형에이전트의주제추론을위한베이지안네트워크의자동생성을제안한다. 3.2.1 베이지안네트워크구조생성대화형에이전트에서베이지안네트워크는그림 3과같이계층적으로설계한다. 대상영역을크게분류하여상위계층을큰주제로구성하고, 각주제에대한세부주제로중간계층을구성한다. 그리고사용자의입력에서뽑은키워드를하위계층의증거노드들로사용한다 [3]. 이렇게대상영역의주제를계층적으로분류하여모델링하면사용자의도를상세하게몇단계로분석하여사용자의도에부합하는세부적내용을파악하도록대화를유도할수있다 [17]. 대화형에이전트에서사용되는베이지안네트워크는비교적인과관계가명확하므로그구조를규칙에의해 그림 3 대화형에이전트에서의계층적베이지안네트워크설계 서생성할수있다. 본논문에서제안하는방법은대화형에이전트를위한베이지안네트워크구조를계층적으로규칙에의해서생성하는것이다. 우선, 네트워크계층을네가지로구분한다. 그림 3에서보여주는것과같이상위레벨에는주제노드가들어가며, 중간레벨에는중간주제노드와소주제노드가들어간다. 그리고하위레벨에는키워드노드가들어간다. 여기서말하는주제노드는스크립트에서 [topic] 을의미하며, 베이지안네트워크추론을통해서알고자하는확률변수이다. 그리고키워드노드는 [keyword] 에서의하나의 [word] 를의미하며, 베이지안네트워크의증거노드가된다. 그리고 [script] 에서 [keyword] 하나는하나의소주제노드를구성하게되며, 중간주제노드는네트워크의크기가커짐에따라서생성된다. 표 5의스크립트는그림 4와같은베이지안네트워크구조로표현된다. 즉, 스크립트의주제인 Agent Age 표 5 스크립트의예 <SCRIPT> <TOPIC> Agent Age </TOPIC> <CLASS>?otherquestion </CLASS> <KEYWORD> 너나이 </KEYWORD> <KEYWORD> 너몇살 </KEYWORD> <ANSWER> 한살인데요. </ANSWER> <ANSWER> 태어난지몇일안됐어요. </ANSWER> </SCRIPT> 그림 4 베이지안네트워크구조
882 정보과학회논문지 : 소프트웨어및응용제 33 권제 10 호 (2006.10) 가상위노드로나타나며, 키워드인 너, 나이, 몇살 은하위노드로나타난다. 그리고스크립트에는두개의 [keyword] 가있으므로두개의소주제노드가생성된다. 그림 4에서보듯이하위레벨의노드는중간레벨의노드와아크로연결이되며, 중간레벨의노드는상위레벨의노드와아크로연결된다. 그런데위와같은방식으로만들다보면주제인상위노드아래에있는소주제의개수가많아질수있다. 그러면상위노드에서결정해주어야할확률변수의개수가많아지므로 ( 한주제아래에있는소주제의개수가 개이면각주제및소주제들은 Yes/No의값을가지므 이되고, 각노드의하위노드개수가 개가되므로, 총연산량은 이된다. 즉, 노드의분화를 통해서연산량이 에서 로바뀌게된다. 로주제노드에서결정해야할확률변수들은 개가된다.) 확률변수를저장해야하는메모리의양도커지게되며, 계산해야할데이타의양도많아지게된다. 따라서주제아래의소주제의개수가어느정도이상되면 B트리와유사한방식으로소주제노드들을분화하여중간주제노드를만든다. 표 6은제안하는시스템에서의베이지안네트워크구조생성과정을보여주고있으며표 7 은베이지안네트워크생성과정중의불변조건을나타낸다. 표 6 대화형에이전트를위한베이지안네트워크구조생성 make_topic_nodes; make_keyword_nodes; make_little_topic_nodes; for(all little_topic_node n) { insert_node n in n's topic_node } // 주제노드를만든다. // 키워드노드를만든다. // 소주제노드를만든다. // 소주제노드를해당주제노드에넣는다. 표 7 베이지안네트워크의불변조건 1. 주제노드와중간주제노드는 개이상의하위노드를갖지못한다. 2. 중간주제노드는최소 개의하위노드를갖는다. 3. 주제노드는상위노드가없으며, 중간주제노드와소주제노드는하나의상위노드를갖는다. 그리고키워드노드는하나이상의상위노드를갖는다. 네트워크에서하의노드의개수를제한하는것은확률추론할때, 계산량을줄이기위해서이다. 한노드의확률값을계산하기위해서는그노드의하위노드의개수의지수승에비례하는계산량이필요하다. 즉, 하위노드의개수가개인노드의경우 의연산량이필요하게된다. 만일노드를분화하지않고주제노드밑에개의소주제노드를추가하면, 의계산량이필요하다. 그러나노드들을분화한다면네트워크의높이가이고각노드의하위노드의개수는 그림 5 베이지안네트워크구조생성 (a) 초기상태, (b) 소주제추가 (c) 노드분화그림 5는 n =4일때의베이지안네트워크구조생성과정을간략히보여주고있다. 그림 5(a) 는초기상태를나타내며, 그림 5(b) 는소주제가하나추가된상태를나타낸다. 그리고그림 5(c) 는노드가분화된상태를보여주고있다. 분화전후의주제노드의확률값계산을위한연산량을구해보면그림 5(b) 는주제아래에소주제가 4개가있으므로 2 4 =16이되고그림 5(c) 는주제노드에서는중간주제노드의개수가 2개이므로 2 2 =4개, 그리고중간주제 1, 2번노드에서는각각소주제가 2개씩있으므로두노드가 2 2 =4개로총연산량은 12가된다.
대화형에이전트의주제추론을위한계층적베이지안네트워크의자동생성 883 3.2.2 조건부확률테이블 (CPT) 생성베이지안네트워크를학습하기위해서는먼저학습에필요한충분한양의데이타가필요하다. 그러나대화형에이전트를구축하는시점에서는통계자료가준비되어있지않으므로앞에서소개한학습방법을통해서 CPT 매개변수값을얻을수없다. 본논문에서는베이지안네트워크에서널리사용되고있는 Noisy-OR gate를사용하여확률변수값을결정한다 [18]. Noisy-OR gate에서는 : 원인 ( 하위노드 ), : 결과 ( 상위노드 ) 라 고하고, 를 만나타나고나머지원인은나타나지않았을때, 결과가나타날확률이라고하면, 가나타났을때결과가나타날확률을다음과같이정의한다. 여기서 는원인이되는노드들의부분집합이다. 그 런데 가모두나타나지않았을때, 저절로 y가나타날확률을 라고하면 에대한 의조건부확률은다음과같이구해진다. 따라서 CPT의확률변수값으로는 만을결정하면된다. 여기서는 의값으로 0.001을주었으며, 주제노드와중간노드에서의확률변수값은다음과같이정의한다. 은하위노드의개수이고 는가중치를의미한다. 그리고소주제노드에서의확률변수값은다음과같이정의한다. 은하위노드 의상위노드의개수이다. 위의식에서보면 n 으로나누어주는부분이있는데, 이는각하위노드가상위노드에미치는영향이같다는가정하에서각하위노드가상위노드에미치는영향을고르게분배하는역할을한다. 또한소주제노드의경우에는 뿐만아니라 으로도나누어주는데, 이는키워드가여러개의상위노드를갖는다면다른노드에도함께영향을주므로상대적으로그비중을줄여줄필요가있기때문이다. 그리고 a 값은상위노드가주제노드에가까울수록하위노드들이주제노드에미치는영향이커지므로높고, 그렇지않을수록낮은값이주어진다. 본 논문에서는 a 값을소주제노드에서는 0.5, 주제노드에서는 0.999로설정하였다. 4. 실험및결과 본논문에서는제안한시스템의성능을평가하기위하여표 8과같은평가척도를사용하였다. 베이지안네트워크를통한확률추론은사용자질의가어느주제에속하는지를찾는것이다. 따라서추론결과로사용되는것은각주제에대한확률값이되며, 해당주제노드 ( ) 에서의확률값이가장커야올바로동작한다고볼수있다. 그리고다른주제노드 (T k) 와확률값차이가클수록, 즉사용자가의도한주제에서의확률값이다른주제노드에서의확률값보다확연한차이가나타나면좋은성능을가졌다고할수있다. 따라서베이지안네트워크의평가척도는우선적으로해당주제노드에서의확률값을그대로사용하며, 다른주제노드에서의확률값과해당주제노드에서의확률값과의차이가임계치이하가되는경우 (T 0 - T k < 0.1) 에는그거리에따라서적절히적합도를낮춰준다. 표 8 적합도평가방법 := 사용자질의가의도한주제의확률값 := 각주제의확률값 ( ) := 주제의개수 - 1 적합도 (%) 제안한시스템의성능평가를위해서컴퓨터전공의대학생 10명을대상으로실험을하였다. 실험에서사용된스크립트는베이지안네트워크설계에드는시간이많이소모된다는점을감안하여 11개의주제를갖는스크립트만을사용하였다. 실험은각피험자에게베이지안네트워크에대한설명과, 베이지안네트워크설계툴인 GENIE의사용법을설명하고베이지안네트워크를설계하는데걸리는시간과베이지안네트워크의적합도를측정하고, 제안하는시스템과비교하였다. 표 9는수동설계와자동설계간의적합도와설계시간을비교한결과를나타내고있다. 실험결과초보자들은평균 74.4% 의적합도를가지는베이지안네트워크를평균 97.1분에설계하는것으로나
884 정보과학회논문지 : 소프트웨어및응용제 33 권제 10 호 (2006.10) 적합도 (%) 설계시간 ( 분 ) 피험자 1 94.45 98 피험자 2 88.27 99 피험자 3 88.18 81 피험자 4 83.36 103 피험자 5 81.14 101 피험자 6 74.05 101 피험자 7 63.14 89 피험자 8 60.81 97 피험자 9 57.09 108 피험자 10 53.59 94 자동설계 90.00 0.01 그림 9 수동설계와자동설계비교타났다. 반면에제안하는시스템은 90% 의적합도를나타냈으며설계시간은수밀리초에불과하였다. 수동설계의경우, 피험자에따라설계한네트워크의적합도가 53.59%~94.45% 의큰편차를보였다. 이는피험자들의베이지안네트워크에대한수학적이해정도에차이가있기때문이다. 5. 결론및향후연구베이지안네트워크를사용하는대화형에이전트의설계에있어서베이지안네트워크의설계는필수적이다. 그러나베이지안네트워크는초보자들이쉽게접근하기어려우며, 전문가들도대상영역에대한분석과설계가선행되야하므로네트워크설계에많은시간이든다. 본논문에서는대화형에이전트에서의베이지안네트워크를자동생성하는시스템을제안하고그성능을수동설계와비교 평가해본결과제안한시스템은초보자들에비하여더좋은성능의베이지안네트워크를짧은시간에자동으로생성함을확인할수있었다. 이러한시스템을사용하면대화형에이전트의설계에드는시간과비용을크게줄일수있을뿐만아니라초보자도대화형에이전트에쉽게접근할수있을것이다. 향후에는베이지안네트워크의자동설계뿐만아니라베이지안네트워크에학습기능을넣어서보다정확한주제추론을가능하도록하는기능이요구된다. Monte- Caro Methods, Gaussian Approximation, EM Algorithm 등과같은오프라인학습방법은학습을위한충분한데이타가미리준비되어야하므로, 데이타준비에많은시간과노력이필요하다는단점이있다. 따라서향후연구로이러한단점을해결할수있는온라인베이지안네트워크학습이요구된다. 참고문헌 [1] J. Allen, D. Byron, M. Dzikovska, G. Ferguson, L. Galescu and A. Stent, "Towards conversational human-computer interaction," AI Magazine, vol. 22, no. 4, pp. 27-38, 2001. [2] M. Budzikowska, J. Chai,, S. Govindappa, V. Horvath, N. Kambhatla, N. Nicolov and W. Zadrozny, "A conversational interface for online shopping," Human Language Technology Confererence, 2001. [3] 홍진혁, 조성배, 계층적베이지안네트워크를이용한 대화형에이전트의문맥유지, 추계정보과학회학회 지, vol. 29, no. 2, pp. 259-261, 2002. [4] 이말례, 배금표, 정보추출을이용한학습기반의웹 인터페이스에이전트, 정보관리학회지, vol. 19, no. 1, pp. 5-22, pp. 1013-0799, 2002. [5] 김혜숙, 한국어기본문형설정에대하여 : 효과적인 국어교육을위하여, 국어국문학회, 국어국문학 122, 1998. [6] J. Weizenbaun, "ELIZA - A computer program for the study of natural language communication between man and machine," Communications of the ACM, vol. 9, no. 1, pp. 36-45, 1965. [7] The A.L.I.C.E. AI Foundation, In http://alicebot.org [8] S.-I. Lee, S.-B. Cho, "An intelligent agent with structured pattern matching for a virtual representative," Proc. of Asia-Pacific Conf. on Intelligent Agent Technology, pp. 409-411, 2001. [9] E. Charniak, "Bayesian networks without tears," AI Magazine, vol. 12, no. 4, pp. 50-63, 1991. [10] D. Heckerman, "A tutorial on learning with Bayesian networks," Microsoft Research, Technical Report MSR-TR-95-06, 1995. [11] D. Chickering, D. Geiger and D. Heckerman, "Learning Bayesian networks is NP-hard," Proc. 5th Conf. on Artificial Intelligence and Statistics, pp. 112-128, 1995. [12] R. Etxeberria, P. Larranaga and J.M. Picaza, "Analysis of the behaviour of genetic algorithms when learning Bayesian network structure from data," Pattern Recognition Letters, vol. 18, Issues 11-13, pp. 1269-1273, 1997. [13] 김경민, 임성수, 조성배, 인공지능기법을이용한 User Interface 기반대화형에이전트, 한글및한국 어정보처리학술대회, 15회, pp. 201-207, 2003. [14] J. Allen, G. Ferguson, A. Stent, "An architecture for more realistic conversational systems," Proceedings of Intelligent User Interfaces 2001, 2001. [15] B. Lin, H. Wang, L. Lee, "Consistent dialogue across concurrent topics based on an expert system model," Proceedings of European Conference on Speech Communication and Technology (EUROSPEECH'99), pp. 1427-1430, 1999. [16] C. Sammut, "Managing context in a conversational agent," Electronic Transactions on Artificial Intelligence, 2001. [17] E. Horvitz and T. Paek, "A computational architecture for conversation," Proc. 7th Int. Conf. on
대화형에이전트의주제추론을위한계층적베이지안네트워크의자동생성 885 User Modeling, Banff, Canada, pp. 201-210. Springer Wien, 1999. [18] A, Onisko, M. J. Druzdzel and H. Wasyluk, "Learning Bayesian network parameters from small data sets: Application of Noisy-OR gates," Int. Journal of Approximate Reasoning, vol. 27, Issue 2, pp 165-182, 2001. 임성수 2004년 2월연세대학교컴퓨터과학과 ( 학사 ). 2006년 2월연세대학교컴퓨터과학과 ( 석사 ). 2006년 3월 ~ 현재연세대학교컴퓨터과학과박사과정. 관심분야는인공지능, 지능형에이전트, 베이지안네트워크 조성배정보과학회논문지 : 소프트웨어및응용제 33 권제 3 호참조