불확실한장면의효과적인인식을위한베이지안네트워크의온톨로지기반제한학습방법 549 불확실한장면의효과적인인식을위한베이지안네트워크의온톨로지기반제한학습방법 (A Constrained Learning Method based on Ontology of Bayesian Networks for Effective Recognition of Uncertain Scenes) 황금성 조성배 (Keum-Sung Hwang) (Sung-Bae Cho) 요약영상을분석하여얻은증거를바탕으로장면의의미를추론하고해석하는것을시각기반장면이해라고하며, 최근인과적인판단및추론과정을모델링하기에유리한베이지안네트워크 (BN) 를이용한확률적인접근방법이활발히연구되고있다. 하지만실제환경은변화가많고불확실하기때문에의미있는증거를충분히확보하기어려울뿐만아니라전문가에의한설계로유지하기어렵다. 본논문에서는증거및학습데이타가부족한장면인식문제에서효율적인 BN 구조로계산복잡도가줄어들고정확도는향상될수있는 BN 학습방법을제안한다. 이방법은추론대상환경의도메인지식을온톨로지로표현하고이를제한적으로사용하여효율적인계층구조의 BN 을구성한다. 제안하는방법의평가를위하여 9 종류의환경에서 90 장의영상을수집하고레이블링하여실험하였다. 실험결과, 제안하는방법은증거의수가적은불확실한환경에서도좋은성능을내고학습의복잡도가줄어듦을확인할수있었다. 키워드 : 베이지안네트워크구조, 제한학습, 장면이해, 불확실한환경 Abstract Vision-based scene understanding is to infer and interpret the context of a scene based on the evidences by analyzing the images. A probabilistic approach using Bayesian networks is actively researched, which is favorable for modeling and inferencing cause-and-effects. However, it is difficult to gather meaningful evidences sufficiently and design the model by human because the real situations are dynamic and uncertain. In this paper, we propose a learning method of Bayesian network that reduces the computational complexity and enhances the accuracy by searching an efficient BN structure in spite of insufficient evidences and training data. This method represents the domain knowledge as ontology and builds an efficient hierarchical BN structure under constraint rules that come from the ontology. To evaluate the proposed method, we have collected 90 images in nine types of circumstances. The result of experiments indicates that the proposed method shows good performance in the uncertain environment in spite of few evidences and it takes less time to learn. Key words :Bayesian network structure, constrained learning, scene understanding, uncertain environment. 서론 베이지안접근방법은확률적인모델을효과적으로 구성하고효율적인추론및학습이가능한방법으로서 인간의인과적인판단및추론과정을모델링하기에유 본연구는정보통신부및정보통신연구진흥원의대학 IT연구센터지원 사업의연구결과로수행되었음. IITA-2006-(C090-0603-0046). 정회원 : 연세대학교컴퓨터과학과 yellowg@sclab.yonsei.ac.kr 종신회원 : 연세대학교컴퓨터과학과교수 sbcho@sclab.yonsei.ac.kr 논문접수 : 2005년 9월 22일 심사완료 : 2007년 4월 3일 리한도구이다. 복잡한세계에존재하는모든정보의확률적인과관계를모델로표현하는것은거의불가능할뿐만아니라효율적이지않다. 따라서인과성이높은관계만을네트워크구조로표현하고, 표현되지않은관계에대해서는상호독립성을가정하며, 직접적인인과관계에서의조건부확률만을정의하여확률분포를표현하는베이지안네트워크구조를이용하는것이효율적이다 []. 베이지안네트워크는직관적인그래픽모델, 효율적인추론알고리즘및학습알고리즘을가지고있어서여러문제에서널리사용되고있다. 장면에어떤물체가존재하는지, 어떤장소에있는지,
550 정보과학회논문지 : 소프트웨어및응용제 34 권제 6 호 (2007.6) 그리고어떤상황인지를알기위해, 시각정보로부터물체및물체특징을인식하고장면에대해설명하는컨텍스트를추출하는것을시각기반장면이해라고한다. 그리고장면인식은일상사건을인식하는것을의미하며이를이해하고해석하면장면설명을할수있다. 장면에서인식의대상은장소, 부분, 활동, 의도및공간적시간적관계가있다 [2]. 장면을이해하면사용자의의도를인지하거나작업중심의서비스제공, 과거의경험발견및신뢰성있는작업이가능하기때문에중요한연구과제로여겨지고있으며, 시각정보는사용자및환경과상호작용이요구되는실세계문제에서중요한판단의근거가되기때문에많은관심을받고있다. 장면이해를잘하기위해서는장면관련정보를컨텍스트로정의하는과정과컨텍스트의관계를정확하게모델링하는과정, 그리고신뢰성있는추론과정이요구되는데, 특히잘구성된모델링을통한정확한컨텍스트의추론은어렵지만중요한이슈이다. 장면인식은물체에대한정보를바탕으로여러단계의컨텍스트추출이수행되고시간과공간에대한인과관계를가지고있기때문에확률적접근방법이좋다 [2]. 이는장면이해과정에서시각적인행동정보는시공간적컨텍스트의확률적추론에의해예측이가능하고 [3], 센서의종류, 알려지지않은물체, 모델이가진고유의불확실성등다양한소스로부터생기는실세계에서의불확실성에대해잘다룰수있기때문이다 [4]. 본논문에서는환경의불확실성에의한성능저하를최소화하고효율적인계산을수행하기위해계층적이면서도간결한베이지안네트워크를자동으로학습하는방법을제안한다. 자주바뀌는실세계환경을대상으로하고가려짐에의한정보부족이나센서노이즈의간섭이빈번한불확실한환경을극복하기위해서는환경에서직접수집한데이타를이용하여효과적인모델링을수행해야한다. 이를위해도메인지식을활용한제한된구조학습방법을제안한다. 즉, 추론대상컨텍스트의 관계를온톨로지로구성하고모델의레벨및클래스정보를베이지안네트워크학습파라미터로정의하여자동학습하는방법이다. 이런방법으로학습하면베이지안네트워크구조가계층화되고추론의방향이계층에서다른계층으로흐르도록제한되기때문에증거가부족하더라도추론결과오류가제한되어신뢰성있는결과를낼수있다. 본논문에서는평가를위해실제영상데이타를수집하여직접레이블링한뒤실험하였다. 2. 관련연구장면인식에대한연구는 955년지각인식컨텍스트연구에서부터시작되어최근까지계속발전하였다. 특히영상처리기술이발전하고영상기반정보인식이요구되는에이전트연구가진행되면서그필요성이증대하였다. 최근에는확률모델기반장면인식방법이주로연구되고있다 ( 표 ). 장면이해를위해이용되는확률모델의하나인베이지안네트워크를설계하는방법은크게두가지가있다. 전문가의도움을얻는방법과학습을이용한방법이다. 직관적이고인과적인설명이가능한베이지안네트워크특성상전문가에의한설계방법이많이이용되고있다. 하지만복잡하고변화가많은환경에서전문가에의한모델링을유지하기위해서는많은비용이요구되기때문에자동학습방법이많이연구되고있다. 학습데이타로부터베이지안네트워크를자동학습하는방법은크게두가지가있다. 먼저변수들의연관성기반학습방법이있다. 이방법은주어진데이타에서변수들의조건부독립성을테스트하면서네트워크구조를형성해나가는방법이나변수들의관계를테스트하는것이쉽지않기때문에널리쓰이지는않는다 [5]. 다른방법으로네트워크구조학습문제를최적화문제로두고해결하고자하는접근방법이있다 [6]. 이방법은네트워크의구조가학습데이타에얼마나일치하는지를점수로환산하고, 가장높은점수를가진구조를 장면인식을위한추론모델구성방법연구 표 확률적모델기반장면인식관련연구 의미저자내용 영상필터를이용한실세계데이타학습 계층적 BN 을이용한단계적인컨텍스트추론모델설계 독일 Hamburg 대학프로젝트 Neumann03 [2] MIT 연구실 Torralba03 [0] 미국 Massachusetts 대학 THE ASCENDER II SYSTEM 개발프로젝트 Marengoni03 [] 개체의존재, 특성, 그룹및클래스정보를계층적으로구성하고확률적으로정의, Bayes' Rule 을기초로확률연산, 시간적인연관성과공간적인연관성을상향식 (Bottom-Up) 으로설계 PCA 영상특징추출필터를이용해서장소및물체인식모델구성, Bayes' Rule 과 Markov 가정이용, 장소이동관련성은전문가가설계, 물체의장소별존재확률추정 BN 을이용한컨텍스트모델링, 항공영상에서정보를추출하여건물특징및건물종류를추론, 상위수준추론결과가하위수준추론수행여부를결정하는계층적 BN 을제안하여연산효율성높임, BN 구조는전문가설계, 파라미터는학습, 결정네트워크와유틸리티활용
불확실한장면의효과적인인식을위한베이지안네트워크의온톨로지기반제한학습방법 55 탐색하는방법이다. 탐색공간이네트워크를구성하는변수에대해지수적인복잡도를가지고있고최적의구조를찾는문제가 NP-hard 문제라고알려져있기때문에 [7], 탐욕적인탐색휴리스틱방법이주로사용되고있다 [8]. 하지만이러한방법들은지역최적해에빠지는문제를가지고있어, 최근에는진화연산을이용해이를해결하려는노력이이뤄졌다 [9]. 확률파라미터학습과정에서도설계된네트워크의구조에따라많은수의데이타가요구된다. 장면이해문제는불확실한실세계를도메인으로하고있는데, 불확실한환경에서부딪히는문제상황은예상치못한데이타가입력된경우, 환경이바뀐경우, 입력된데이타에잡음이포함된경우와입력데이타의양이부족한경우가있다. 이중에서앞의두경우는실시간업데이트및지속적인추론모델의적응을통해극복가능하며, 뒤의두경우는오류에강인한확률추론모델설계를통해극복이가능하다. 본논문에서접근하는방법은입력데이타의양이부족하거나잡음이포함된경우를극복하기위한방법이다. 불확실한환경에서좋은성능을얻기위한베이지안네트워크학습방법은해당환경에서직접수집한불확실성이고려된데이타에가장일치하는정확한모델을찾는것이었다. 이미오래전부터베이지안통계및정보이론, MDL(Minimal description length) 원리 [2] 를이용한 BN 탐색방법이고안되었고, 이러한방법들을발전시키고분석하는노력이있었다 [3]. 하지만이러한방법들은학습데이타가부족한환경에서는좋은성능을보장할수없으며, 이를해결하기위한연구로표 2 와같은방법들이연구되었다. 하지만학습을통해서네트워크구조를설계할경우불필요한연결관계가생기거나잘못구성될가능성이높기때문에전문가의개입에의한네트워크구조수정및설계방법이여전히많이사용되고있다. 3. 장면인식을위한베이지안네트워크장면이해란, 영상에서여러컨텍스트정보를추출하 고이를바탕으로장면인식컨텍스트를추론한다음이를바탕으로장면을이해하는과정이다. 이과정에서얼마나많은증거를얼마나정확하게수집하느냐, 수집된증거를이용하여얼마나정확하게추론하느냐가장면이해성능을좌우하게된다. 본논문에서사용된장면인식컨텍스트추론과정은그림 과같다. 환경에서수집된센서정보및기호적으로해석된컨텍스트정보와온톨로지등으로주어진도메인지식을함께고려하여상대적으로레벨이높은상황이나상태컨텍스트를추론하는과정을거친다. 이때, 온톨로지란 어떤개념들이도메인내에서어떻게존재하고, 서로관련되는가에대한지식을나타내는것 을말하며, 환경의지식을포함하고있다 [9]. 그림 영상정보에서여러레벨의컨텍스트를추출하는과정여러레벨의컨텍스트를얻기위한추론과정에는확률적인접근방법이많이사용된다. 하지만복잡한실세계의모든확률관계를표현하거나설계하는것은매우어렵기때문에, 확률적인과성이강한정보의확률만정의하는베이지안네트워크모델을이용하기도한다. 또한베이지안네트워크를이용하면분석적추론 (Diagnostic Reasoning) 을이용해결과에서원인을분석할수있을뿐만아니라, 구성하고있는변수의종류에상관없이유연하게입출력이가능하기때문에실세계처럼복잡한환경에서하나의증거라도더활용할수 방법 Noisy-OR 기법 : Buchanan84 [4], Pearl88 [5] Learning with Boosting: Choudhury02 [6] Restricted BN: Schneiderman04 [7] Restricted BN: Lucas02 [8] 표 2 부족한 BN 학습데이타를극복하기위한연구 적은수의학습데이타를극복하기위해부모조건의독립성을가정하고파라미터를학습 학습데이타의오류를집중적으로극복하기위해학습단계에서 Boosting 기법을사용하여오류를최소화하는방법 내용 지역별로오류를최소화하는변수의부분집합을선택한후 BN 을탐색하는전역오류최소화과정을이용 도메인의특성에따라 Naive Bayesian network 와 TAN (Tree augmented Bayesian network) 의모델지향특성을조절하여좋은성능을가지는 BN 을탐색
552 정보과학회논문지 : 소프트웨어및응용제 34 권제 6 호 (2007.6) 있다. 또한불확실성을확률적으로다룰수있는데, 정보나증거에대한신뢰도를확률적으로정의하면더정확한추론결과를얻을수있다. 장면이해대상인장소의종류와특성을인식하기위한베이지안네트워크를가장단순한베이지안분류기형태인 Naïve BN으로설계하면그림 2와같다. 그림 2 는계산복잡도를줄이기위해인과성의역방향으로설계 ( 장소 물체 ) 하고, 장소및장소특성변수 0개와물체변수 33개를대상으로설계한 BN이다. 장소변수는장면정보 ( 장소의종류 ) 를나타내는결과노드이고, 물체노드는장면인식을위한증거가입력되는노드이다. 그림 2의 BN은모든장소와물체노드가연결되기때문에상당히많은연결관계가관찰된다. 따라서많은확률파라미터의정의가요구되고, 확률추론의계산복잡도가크며, 학습을할경우많은확률파라미터에대응하여많은데이타가요구된다. 베이지안네트워크구조에따라요구되는확률파라미터의개수는수식 () 과 같다. 이때, N은변수의수, r i 는변수 X i 의상태의수, U i 는변수 X i 의부모집합을의미한다. () 그림 3은도메인지식을이용하여추론의단계를 발견된물체종류 장소종류추론 장소특성추론 으로나누고계층적 BN 구조를설계한경우이다. 계층이증가하면서구조가단순해지고복잡도가줄어들었다. 본논문에서는이렇게계층성이부여된 BN 구조의설계를기반으로학습데이타에서연관성이강한변수관계를탐색하여자동으로구성하는학습방법을제안한다. 4. 베이지안네트워크의제한된학습방법 4. 베이지안네트워크의학습베이지안네트워크는노드의연결관계를표현하는방향성비순환그래프 (DAG: directed acyclic graph) 형태를가지고있으며, 이구조에따라정의된조건부 그림 2 물체정보에서장소를인식하는 Naïve BN : 43개의변수와, 330개의연결관계, 67,604개의확률파라미터를가진다. 그림 3 장소인식을위한계층적인 Naïve BN : 추론과정이 물체 장소종류 장소클래스 이다. 43개의변수와, 306개의연결관계, 33,830개의확률파라미터를가진다.
불확실한장면의효과적인인식을위한베이지안네트워크의온톨로지기반제한학습방법 553 확률테이블 (CPT: conditional probability table) 에의해적은비용으로많은확률관계를효율적으로표현한다. 베이지안네트워크모델은네트워크구조를나타내는 B s 와파라미터집합을나타내는 θ를이용해 (B s,θ) 쌍으로정의할수있다. 여기서 θ={b Φ, B p} 는조건부확률테이블 B Φ 와초기확률분포 B p 로구성된다. 본논문에서는 B s 를제안하는구조학습을통해구성하고, 파라미터 θ는학습데이타집합 D로부터수식 (2) 와같은방법으로계산한다. * θ = arg max P( D θ ) P( θ ) θ 여기서 P(θ) 는초기확률을의미한다. 기본적인학습과정은다음과같다. 만약 Z T={z, z 2,, z T} 가 T개의상태변수를나타내고, Y T 가실제로측정된 T개의변수라면수식 (3) 과같은관계를가지게된다. P ( ZT P (2), YT, θ ) = P( YT ZT, Bφ ) P( ZT B ) (3) 여기서조건부확률테이블 B Φ 는측정값과상태변수의조합이얼마나있었는지의빈도를조사하여정의가가능하다. 즉, 학습데이타의분포에대한히스토그램을분석하여빈도를확률로계산하고베이지안네트워크의파라미터를학습한다. 학습으로구성된베이지안네트워크에서주어진증거집합 E의추론결과 h에대한확률 Bel(h) 는 Bayes' rule에의해수식 (4) 와같이계산된다 []. P( E h) P( h) P( h E) Bel( h) = P( h E) = = P( E) P( E) (4) 이때조건부확률은 Chain Rule에의해수식 (5) 와같이계산된다. P( x, x..., x ) = P( x, x..., x 2, n ) P( x x, x = P( x ) P( x x ) P( x x, x )... P( x,..., x ) x = P( x ) P( x π ) P( x π )... P( x π ) 2, 2 2 n 2 3 3 n 2 n 3 n 2 n n n n, x n 2,..., x ) (5) 여기에서 x i 는 i번째노드를 π i 는 x i 의부모를의미한다. 4.2 베이지안네트워크구조의제한학습기존연구에서전문가에의해설계된장면인식을위한베이지안네트워크구조들을살펴보면계층성이많이나타난다 [2,0,]. 본논문은이러한계층적인베이지안네트워크를자동으로설계하기위한한가지방법을제안한다. 제안하는방법은그림 4와같으며도메인지식과학습데이타를이용하여계층적인 BN을생성하는과정이다. 그림 4에서사용되는도메인지식은베이지안네트워크소속변수의인과성과레벨에관련된정보이고그림 5와같은온톨로지로정의하였다. 이와같은온톨로지정의를통해개체및속성의연관관계와클래스계층구조를고려하여베이지안네트워크학습을위한파라미터를정의할수있다. 이때온톨로지를정의하기위해수집하고분석한정보는다음과같다. 여기서 Category와 Association은더많은데이타가수집될수도있으나문제의복잡도를줄이기위해제안하는정도로만한정시켰다. 그림 4 제안하는 BN 제한학습방법의개요 그림 5 물체및장소의계층성과관계를나타낸온톨로지구조
554 정보과학회논문지 : 소프트웨어및응용제 34 권제 6 호 (2007.6) Domain: 사무실및주변환경에서물체를식별하여장소의종류를인식하는문제 Entity: 사용되는데이타의종류를구분지음 예 : { 물체의특징, 물체, 장소의특징, 장소 } Class: 그룹을형성하거나포함하는개념 예 : 물체 ({ 책상, 의자 }) 물체클래스 ( 사무용가구 ) Individual: 발견되거나인식된각각의정보변수 예 : { 책상, 의자 } 물체 Association: Class 및 individual 사이의연관성을표시 예 : is_a, is_in, is_a_feature_of 온톨로지로표현된도메인지식을바탕으로수행되는제한된베이지안네트워크학습방법은그림 6과같다. 온톨로지를통해얻은도메인정보를바탕으로 level, predefined link와같은파라미터를정의하고, BN 학습에필요한추가파라미터 ( 예 : topological order) 를생성하거나초기 BN을구성하고제한된 BN 구조학습및수정하는과정을거쳐서목표 BN을탐색한다. 이같은과정은학습데이타와 BN 구조의일치성을평가하는함수를정의하고가장만족스러운네트워크구조를탐색하는 BN 구조탐색알고리즘에도메인정보로제한을가한것이다. 본논문에서는 level 수준을정의하기위해서그림 5 의좌측을고레벨로, 우측을저레벨로정의하였다. 제안하는학습알고리즘이인접레벨사이의연결만허용하기때문에가능한한많은인접연결 (association) 을허용할수있도록 { place's class place place's feature object's class object object's feature } 순서로 배열한다음에 level을정의한것이다. 이때연결에의해구분되는계층의경계가불확실한경우같은 level을정의하는것도가능하다. 실제로본논문의실험에서는 object 와 object's feature 를같은 level로정의하였다. predefined link는온톨로지에서정의된 is_a, is_in, is_a_feature_of 연결을그대로채택하였다. 온톨로지에서정의된클래스에속하는서브클래스나인스턴스사이에알려져있는연결관계는이미인과관계를가지고있다고가정하는것이다. 이러한연결관계는설계자가인과관계가있다고확신하는경우에만해당된다. 제안하는알고리즘에서베이지안네트워크는 predefined link가연결된상태에서학습을시작한다. topological order는 4.3절에서다루는베이지안네트워크학습방법에적용되는파라미터로서부모가될가능성이높은노드에대한순서를정의한다. 본논문에서는 topological order를정의하기위해같은 level의노드사이에서는순서를임의로생성하고 level 사이에는높은레벨이우선순위가높도록하였다. topological order를어떻게정의하느냐에따라알고리즘의성능이차이가날수있으나본논문에서는 topological order의최적화방법에대해서는다루지않고반복실험에의한성능검증까지만수행하였다. 일반적으로베이지안네트워크구조를학습하기위해사용되는방법은각노드별로부모를정의했을때주어진데이타의존재확률값을최대로하는부모집단을찾는방법으로수식 (6) 과같다. 여기서 π i 는 X i 의부모집단을의미하고, θ i 는 X i 에대한조건부확률테이블을의미한다. * i π = arg max P( D θ ) P( θ π ) P( π ) π i 본논문에서는레벨파라미터 (L) 를이용하기때문에 X i 의부모탐색복잡도가줄어드는효과를가진다. 기존에는탐색후보집합이 X i 를제외한모든변수였지만, 제안하는방법에서는레벨파라미터 (L) 값이높은변수중에서 X i 를제외한변수가후보집합이다. 계층적인 BN 구조를학습하기위해서제한되는사항은다음과같다. 이때 order는숫자가작을수록우선순위가높음을나타내고, level은숫자가클수록상위수준을의미하며, level이높을수록 order는작다. 기호정의 X i = i th variable that is included in the set X level(x i) = an integer which is the level of i i i i (6) variable X i order(x i) = an integer which is the topological 그림 6 베이지안네트워크의제한학습과정 order of variable X i parents(x i) = {X j X j = the parent of variable X i}
불확실한장면의효과적인인식을위한베이지안네트워크의온톨로지기반제한학습방법 555 parents_level_area(x i) = {k k = available level as parent of variable X i} 제한규칙. 위상순위초기화 : On the initialization process, set: order(x i) order(x j), order(x j) order(x i) if level(x i)<level(x j) order(x i)<order(x j) where: X i X, X j X i j, 제한규칙 2. 알려진연결관계반영 : On the initialization process, set: parents(x j) parents(x j) {X i} where: X i X, X j X X i causes X j 제한규칙 3. 부모탐색도메인의제한 : On the learning process, set: parents-candidate-set(x i) = {X k level(x k) parents_level_area(x i), X k X, i k} 제한규칙 4. 동수준연결관계의수정 : After the learning process, set: parents(x i) (parents(x i) {X j}) {X k} if X k parents(x j) level(x j)<level(x k) where: X i X, X j X i j X j parents(x i) level(x i)=level(x j) 4.3 알고리즘제안하는베이지안네트워크학습방법은 Cooper가제안한 K2 학습알고리즘 [8] 에레벨파라미터 (L) 와연결관계파라미터 (R) 에의한제한을적용한방법이다 ( 그림 7). 그림 7 제한된베이지안네트워크학습알고리즘
556 정보과학회논문지 : 소프트웨어및응용제 34 권제 6 호 (2007.6) 제안하는알고리즘은베이지안네트워크의최적구조를판단하기위해 Cooper가제안한 K2 metric인 g( ) 함수를사용하였으며, 최대부모수파라미터 (μ) 와변수순서파라미터 (O) 를같이사용하였다. μ 는 K2 학습알고리즘의파라미터로서너무복잡한구조의베이지안네트워크구조가되지않도록부모의수를제한하는역할을하며, α는부모로정의가가능한레벨차이의범위를나타낸다. 예를들어, α가 2이면 level 인노드는 level ~3인노드를부모로가질수있다. K2 알고리즘은상대적으로위상순위가높은변수만부모가될수있도록제한하고있기때문에이를제한규칙 에적용하였다. 그리고초기화과정에서제한규칙 2가적용되었으며, K2 학습과정에서제한규칙 3이적용된부모변수탐색이수행되고, 수정하는단계에서제한규칙 4 가사용되었다. 이때학습에사용되는 K2 점수계산함수는수식 (7) 와같으며, 여기서, (v i,, v iri) 은변수 X i 에배정가능한값배열을, r i 는그배열의수를, π i 는변수 X i 의부모집합을, w ij 는부모집합 π i 의 j번째상태를, q i 는부모집합 π i 의상태수를, N ijk 는변수 X i 가값 v ik 를가지고부모집합 π i 가 w ij 로초기화된경우의수를의미한다 [8]. g'(i) = qi r i i j= ( Nij + ri )! k = ( r )! 5. 실험및결과본장에서는제안하는베이지안네트워크학습방법이컨텍스트추론기능에서어떤특성을보이는지알아보기위해비교실험을수행하였다. 특히제안하는방법의경우계층적으로수행되는분류특성으로인해부족하거나잘못된증거의오류가줄어들수있기때문에증거가부족한상황을가정하여비교실험을수행하였다. 실험을위해 9종류의장소별로 0장의다른영 N ijk! (7) 상데이타를수집하고, 영상에서관찰되는물체, 장소, 장소의클래스에대한컨텍스트를레이블링하였다 ( 그림 8). 이때레이블링항목은장소의종류를인식하는데에도움이되는것을위주로채택하였으며, 주로물체존재여부가장소의증거로사용되는것으로가정하였다. 5. 실험환경그림 9는영상데이타로부터장면을인식하기위해사용될수있는물체와장소관련도메인지식을온톨로지로표현한것이다. 영상데이타를분석하여레이블링한항목은그림 9에서와같이장소클래스, 장소, 물체, 물체특성이다. 그림에서 place 와 place's class 의사이에는연결관계가명확하게드러나있지만 object 와 place 사이에는어떤노드사이에연결을가지고있는지알수없는경우이다. 해당연결관계는제안하는베이지안네트워크의학습과정에서찾게될것이다. 표 3은베이지안네트워크의학습에사용된데이타를나타낸다. 물체노드는관찰의빈도수에따라 3개의상태 {none, a little, a lot} 로구분하였다. 물체특징노드는장면에대해중요한증거가될수있다고판단되는 바닥의밝기 (brightness) 와 바닥의크기 (area size) 에대해서만정의하였는데, brightness 는 { normal, dark, bright } 로정의하였고, area size 는 { small, normal, wide, long } 로정의하였다. 각장소노드는 { Yes, No } 로정의하였으며, 장소의클래스노드는 { indoor, outdoor } 를상태로가지는 AreaType 노드하나만사용하였다. 이때속성을선택하기위한기준은레이블링에참여한전문가의의견을그대로반영하였다. door 나 tap_water 와같이빈도수가작은물체의경우 2개이상이면 a lot 으로정의하였고, chair 와같이원래어느정도많이존재하는물체의경우에는 5개이상이면 a lot 으로레이블링하였다. 그림 8 인터넷에서수집한영상데이타의예
불확실한장면의효과적인인식을위한베이지안네트워크의온톨로지기반제한학습방법 557 그림 9 온톨로지로설계된도메인지식모델 표 3 실험에사용된데이타일부 번호 종류 이름 속성구분 레벨 부모 places's class AreaType indoor / outdoor 2 없음 2 place plaza Yes / No AreaType 3 place lobby Yes / No AreaType 0 place street Yes / No AreaType object tap_water none / a_little / a_lot 0 없음 4 object cupboard none / a_little / a_lot 0 없음 42 object's feature brightness normal / dark / bright 0 없음 43 object's feature areasize small / normal / wide / long 0 없음 컨텍스트의 level은그림 9의온톨로지를바탕으로정의하였다. 이때, 모든장소에서 floor 는항상존재하고 floor 의속성을다양하게정의하는것보다특징 brightness, AreaSize 에의한직접적인장소증거활용이더효율적이라판단하여 brightness 와 AreaSize 를물체와같은레벨로정의하였다. 정의된레벨속성은 {level of object's feature = 0, level of object = 0, level of place =, level of place's class = 2} 과같다. 표 4는베이지안네트워크학습실험에사용된환경 변수및주어진파라미터를나타낸다. 5.2 자동설계된베이지안네트워크구조제한된 BN 학습알고리즘은 Naïve BN 구조의많은연결관계에의한복잡도문제를해결하고전문가에의한 BN 설계어려움을덜기위해제안된것이다. 그림 0과 은실험결과얻은 BN을레벨이가장높은 AreaType 노드를기준으로최소경로거리에따라중심에서동심원모양으로배열한그림이다. 그림 0은기존의 K2 알고리즘을이용하여설계된 BN을나타낸다. 환경변수 학습데이타관련 학습파라미터관련 표 4 실험환경변수 내용 물체및물체특성컨텍스트 33개 장소컨텍스트 9개 장소클래스컨텍스트 개 데이타수 (M) 90 BN 노드수 (N) 43 최대부모수 (μ) 0 초기변수우선순위 (O) 무작위 (Random) 레벨 (L) 장소클래스 =2, 장소 =, 물체 =0, 물체특성 =0 연결관계 (R) 모든 place 노드 AreaType 노드 Coverage of level (α)
558 정보과학회논문지 : 소프트웨어및응용제 34 권제 6 호 (2007.6) 그림 0 K2 알고리즘에의해얻은 BN : 계층성이약하고노드가흩어져있다. AreaType 변수를중심으로경로거리에따라동심원으로배열하였다. 그림 K2R 알고리즘에의해얻은 BN : AreaType 변수를중심으로경로거리에따라동심원으로배열하였으며, 노드레벨간계층성이뚜렷하다.
불확실한장면의효과적인인식을위한베이지안네트워크의온톨로지기반제한학습방법 559 43개의노드와 87개의연결관계,,925개의파라미터를가지고있으며, 인과성이강한경우에만연결관계가생성되기때문에 Naïve BN( 그림 2, 그림 3) 에비해네트워크의복잡도가크게줄어들었다. 하지만실제노드의레벨과상관없이불규칙한 8개의층을형성하고있어서이해하기어려운구조를가지고있다. 즉, 그림 0의 BN은노드의계층적특성이반영되지않았기때문에, 결과노드 ( 변수 ) 의판단근거가되는변수가적게연결되어있어서증거가부족한경우정확도가감소할가능성이높다. 또한독립성이요구되는증거노드사이에생긴불필요한인과관계로인해 D-separation 되어증거의효과가차단될수있다 [5]. 그림 은본논문에서제안한방법을이용해설계된베이지안네트워크이다. 43개의노드, 0개의연결관계, 5,859개의파라미터를가지고있다. 그림 0에비해구조가복잡하지만 Naïve BN에비해복잡도가크게줄어들었고, 계층적으로구성되어있어서증거가 개가들어오더라도관련된결과노드에정보를전달할수있다. 또한같은증거노드사이의연결이배제되어있기때문에추론의단절을방지할수있다. 5.3 컨텍스트추론성능비교제안하는방법 (K2R) 과기존의학습방법 (K2) 의일반화성능을평가하기위해주어지는증거의개수를다르게하면서장소에대한분류성능을평가해보았다. 그림 3은주어지는증거의수를 3개에서 33개 ( 물체의수 ) 로바꿔가면서각각의경우에대해 20번씩의분류성능평가를한다음평균및표준편차를계산하여표현한결과를나타낸다. 주어지는증거는 33개의물체중에서임의의것을선택하도록하였으며 9개의장소에대해가장높은확률을나타낸노드가정답장소와일치하는지여부를평가하였다. 이실험에서학습데이타와평가데이타는동일한것을사용하였다. 실험결과를살펴보면모든경우에대해서 K2R 방법이더좋은성능을보이고있으며, 특히증거의수가적을수록그성능차이가크게나타나는것을알수있다. 이와같은결과는계층적인정보가잘반영된베이지안네트워크에서는주어진물체의증거가장소존재확률에미치는 그림 2 증거의수에따른베이지안네트워크분류성능및표준편차영향이잘학습이되어있는데비해, 기존의 K2 학습방법에서는물체와장소가릴것없이존재확률이비슷한노드에만영향을많이끼치기때문으로분석된다. 학습데이타와평가데이타가다른경우의성능평가를위해교차검증 (cross validation) 을통한성능평가를하였다. 그림 3은증거 4개 ( Chair, AreaSize, Brightness, AreaType ) 를준경우 ( 왼쪽 ) 와장소노드 9개를제외한 34개의증거를준경우 ( 오른쪽 ) 에교차검증을통해장소분류성능을비교한그래프를나타낸다. 증거에 AreaType 을포함시켜서 장소특성 장소 의추론성능도함께평가하였다. 증거가적은경우에는 K2R 방법이더좋은성능을보이고있으며, 증거가많은경우에는 K2R 방법과 K2방법이유사한성능을보이고있다. 적은수의증거가주어진경우장소컨텍스트의변화를살펴보기위해모든장소컨텍스트확률의변화를농도가다른회색으로표현하였다. 그림 4는교차검증을하지않고 4개의증거 ( Chair, AreaSize, Brightness, AreaType ) 만을사용하여학습과평가를한경우의결과를나타낸다. 실험에서같은종류의장소더라도전혀다른장면형태를가지고있는불연속적인이미지를사용하였으며, 장소의변화를 주방 로비 사무실 복도 엘리베이터 강의실 거리 공터 광장 으로정의하였다. 따라서실험결과가색깔이진한장소가올라가는계단형이될수록더좋은성능을나타낸다. 그림 그림 3 실험에의해얻은분류기의성능비교그래프 : 좌측은증거 4개 ( Chair, AreaSize, Brightness, AreaType ) 를준경우, 우측은증거 34개 (9개의장소노드를제외한나머지 ) 를준경우의결과이다.
560 정보과학회논문지 : 소프트웨어및응용제 34 권제 6 호 (2007.6) 그림 4 장소이동에따른컨텍스트추론결과비교그래프 : 레이블링하면서수집된실제장면영상분류실험결과를나타낸다. 을살펴보면 K2R 방법이더좋은분류결과를나타내고있다. 특히, 복도 (corridor) 와회의실 (conference room) 의성능향상이두드러진다. 그리고증거로실내 / 실외특성 (AreaType) 을주었기때문에실내일경우에는광장 (Plaza) 과공터 (Open space), 거리 (Street) 의확률값이 0% 이고, 실외인경우에는나머지장소의확률이 0% 인것이관찰된다. 이는주어진장소클래스정보에의해각장소컨텍스트가잘구분되고있다는증거를나타낸다. 실험에서 공터 와 거리 는비슷한물체를가지고있는장소이기때문에상대적으로성능이좋지않게나왔다. 6. 결론및토의본논문에서는장면인식을수행하기위한베이지안네트워크를설계할때기존의자동설계기법으로는전문가와같은계층적인설계가어렵다는문제를해결하기위해도메인지식을이용한제한된 BN 구조학습방법 [20] 을체계적으로제안하고실험으로검증하였다. 이를위해, 도메인지식을클래스와카테고리, 연결관계로구성된온톨로지로표현한뒤, level과 predefined link 학습파라미터로정의하여제한학습을수행하였다. 계층적으로잘설계된 BN의경우각층별로분류가이뤄지기때문에오류의확산이적어서, 증거가부족한불확실한환경에서더좋은분류성능을보일수있으며, 제한된부모도메인속에서학습방법을사용하기때문에계산복잡도가줄어든다. 하지만제안하는방법에서는레벨의제한에의해학습과정에서무시되는부모자식관계가있어성능저하가능성이남아있다. 따라서정보이론에의한분석 과연관관계가강인한변수쌍에대해은닉노드 (Hidden Node) 를추가시키는방법이함께사용된다면더좋은 BN 설계가가능할것이다. 또한좀더복잡한도메인지식을고려한학습기법의연구가필요할것이다. 참고문헌 [] K. B. Korb and A. E. Nicholson, Bayesian Artificial Intelligence, Chapman & Hall/CRC, 2003. [2] B. Neumann, A Conceptual Framework for High- Level Vision, Bericht, FB Informatik, FBI-HH- B245/03, 2003. [3] J. Fernyhough et al., "Building qualitative event models automatically from visual input," In Proc. ICCV-98, IEEE Computer Society, pp.350-355, 998. [4] L. R. Biswas, et al., "A probabilistic approach to inference with limited information in sensor networks," In Proc. of the 3rd Int. Symposium on Information Processing in Sensor Networks, pp.269-276, 2004. [5] P. Spirtes, et al., Causation, Prediction, and Search (2nd edition), MIT Press, Cambridge, 2000. [6] N. Friedman and M. Goldszmidt, "Learning Bayesian networks with local structure," M.I. Jordan (eds.), Learning in Graphical Models, MIT Press, Cambridge, pp. 42-459, 999. [7] D.M. Chickering, "Learning Bayesian networks is NP-complete," D. Fisher, H.-J. Lenz (eds.), Learning from Data: Artificial Intelligence and Statistics V, Springer-Verlag, Berlin Heidelberg New York, pp. 2-30, 996. [8] G. F. Cooper and E. Herskovits, "A Bayesian
불확실한장면의효과적인인식을위한베이지안네트워크의온톨로지기반제한학습방법 56 method for the induction of probabilistic networks from data," Machine Learning, vol. 9, pp. 309-347, 992. [9] M. L. Wong and K. S. Leung, "An efficient data mining method for learning Bayesian networks using an evolutionary algorithm-based hybrid approach," IEEE Transactions on Evolutionary Computation, vol. 8, no. 6, pp. 532-545, Aug. 2004. [0] A. Torralba, et al., "Context-based vision system for place and object recognition," In Proc. of Int. Conf. Computer Vision, pp.273-280, 2003. [] M. Marengoni, et al., "Decision making and uncertainty management in a 3D reconstruction system," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 25, no.7, pp.852-858, July 2003. [2] J. Rissanen, "Modeling by shortest data description," Automatica, vol. 4, pp. 465-47, 978. [3] R. R. Bouckaert, "Bayesian belief networks: From inference to construction," Ph.D.Dissertation, Utrecht Univ., Utrecht, The Netherlands, 995. [4] B. G. Buchanan and E. H. Shortliffe, Rule-based Expert Systems: The MYCIN Experiments of The Stanford Heuristic Programming Project, Addison-Wesley, Reading, MA, 984. [5] J. Pearl, Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference, Morgan Kaufmann, San Mateo, CA, 988. [6] T. Choudhury et al., "Boosting and structure learning in dynamic Bayesian networks for audiovisual speaker detection," Proc. of Int. Conf. on Pattern Recognition, vol. 3, pp. 789-794, Aug. 2002. [7] H. Schneiderman, "Learning a restricted Bayesian network for object detection," In Proc. of IEEE Conf. on Computer Vision and Pattern Recognition, pp. 639-646, June 2004. [8] P. Lucas, "Restricted Bayesian network structure learning," In Proc. of 4th Belgian-Dutch Conf. on Artificial Intelligence, pp. 2-28, 2002. [9] B. Smith, Basic concepts of formal ontology, Formal Ontology in Information Systems, IOS Press, pp. 9-28, 998. [20] 황금성, 조성배, 효율적인컨텍스트분류를위한베이지안네트워크구조의제한학습, 한국정보과학회가을학술발표논문집, vol. 3, no. 2, pp. 2-4, 2004. 조성배정보과학회논문지 : 소프트웨어및응용제 34 권제 5 호참조 황금성 200 년 2 월연세대학교컴퓨터과학과졸업 ( 학사 ). 2003 년 2 월연세대학교컴퓨터과학과졸업 ( 석사 ). 2004 년 3 월 ~ 현재연세대학교컴퓨터과학과박사과정재학중. 관심분야는진화알고리즘, 지능형에이전트, 베이지안네트워크