변분베이지안혼합인자분석에의한분포추정을이용하는진화알고리즘 07 변분베이지안혼합인자분석에의한분포추정을이용하는진화알고리즘 (Evolutoary Algorthm wth Dtrbuto Etmato by Varatoal Bayea Mxture of Factor Aalyzer) 조동연 장병탁 (Dog-Yeo Cho) (Byoug-Tak Zhag) 요약최근들어확률분포를개체군으로부터추정하여보다효율적으로최적화를해결하려는연구가진행되고있다. 특히복잡한문제의해결을위해서혼합분포가사용되고있다. 그러나이경우몇개의성분으로혼합분포를나타낼것인가를결정하기어려운문제가있으며, 각분포에의하여표현되는이전세대의우수한부분해들을잘결합하지못하는단점이있다. 본논문에서는변분베이지안혼합인자분석 (varatoal Bayea mxture of factor aalyzer) 기법을사용한개체군의분포추정을통해실수공간에서의최적화문제를해결하는방법을제안한다. 이기법은혼합분포의개수추정을자동화하며, 잠재변수 (latet varable) 를사용하여각분포가표현하는세부개체군내에포함된부분해들의혼합을효율적으로수행할수있다. 잘알려진함수최적화문제들에대해다른분포추정진화알고리즘과비교하여제안하는방법의우수성을검증하였다. 또한시스템생물학에서다루고있는생화학네트워크의동적모델링을위한매개변수추정도성공적으로수행하였다. 키워드 : 변분혼합인자분석, 분포추정진화알고리즘, 최적화 Abtract By etmatg probablty trbuto of the goo oluto the curret populato, ome reearcher try to f the optmal oluto more effcetly. Partcularly, fte mxture of trbuto have a very ueful role ealg wth complex problem. However, t ffcult to chooe the umber of compoet the mxture moel a merge uperor partal oluto repreete by each compoet. I th paper, we propoe a ew cotuou evolutoary optmzato algorthm wth trbuto etmato by varatoal Bayea mxture of factor aalyzer. Th techque ca etmate the umber of mxture automatcally a combe goo ub-oluto by amplg ew vual wth the latet varable. I a comparo wth two probabltc moel-bae evolutoary algorthm, the propoe cheme acheve uperor performace o the tratoal bechmark fucto optmzato. We alo uccefully etmate the parameter of S-ytem for the yamc moelg of bochemcal etwork. Key wor : varatoal Bayea mxture of factor aalyzer, etmato of trbuto algorthm, optmzato. 서론 진화전략 (evoluto trategy) 과같이연속변수를다 본연구는교육인적자원부 BK-IT, 산업자원부차세대신기술개발사업의분자진화컴퓨팅 (MEC) 과제및과학기술부국가지정연구실 (NRL) 사업에의하여일부지원되었다. 또한이연구를위해장비를지원하고공간을제공한서울대학교컴퓨터연구소에도감사드린다. 학생회원 : 서울대학교컴퓨터공학부 ycho@b.u.ac.kr 종신회원 : 서울대학교컴퓨터공학부교수 btzhag@ce.u.ac.kr 논문접수 : 005년 7월 5일심사완료 : 005년 9월 8일 루는진화알고리즘에서는전통적으로확률분포를이용하여새로운개체를생성하는기법을사용하고있다 []. 최근들어이확률분포를개체군으로부터추정하여보다효율적인탐색을수행하려는시도가이루어지고있다. 분포추정알고리즘 (etmato of trbuto algorthm -EDA) 으로불리는이러한기법들은현재개체군중에서적합도가좋은개체들을데이타로사용하여그분포를표현할수있는확률모델을학습하고, 이모델로부터새로운개체들을생성하게된다 []. 즉, 기존의진화알고리즘들과는달리교차나돌연변이연산을이용하지않
07 정보과학회논문지 : 소프트웨어및응용제 3 권제 호 (005.) 고, 학습된확률분포로부터표본추출을통해새로운탐색점을만들어낸다. 여기서우수한개체들의확률분포를추정한다는것은주어진문제에존재하는변수들사이의관계를파악하는것을의미하여, 사용되는확률모델의관계표현능력에따라분포추정진화알고리즘을분류할수있다 [3,4]. 예를들면, 모든변수들이서로독립적이라고가정하는가장단순한모델로부터, 두변수쌍의관계를파악하는모델, 그리고일반적으로임의의관계를나타낼수있는모델을사용하는방법으로구분이가능하다. 히스토그램모델 [5] 을이용하는경우도있기는하지만, 연속변수를다루는문제에대해서는주로정규분포가사용되어왔으며, 이경우각변수들사이의관계는공분산행렬을통해표현된다 [3]. 그러나문제가복잡해지면일반적인공분산행렬을갖는정규분포를사용하더라도변수들사이의관계를정확하게파악하기어렵기때문에, 단하나의정규분포를사용하여최적점을탐색할때지역최적점으로일찍수렴하는현상이발생하게된다. 이러한난점을극복하기위해정규혼합 (ormalmxture) 모델을도입하는연구가이루어졌다 [6-8]. 이는암묵적으로혹은명시적으로여러개의개체군을고려하는진화연산기법 [9-] 과도그맥을같이하며, 전체개체군의분포를다수의세부개체군에대한혼합분포로표현함으로써개체군의다양성을유지하는데기여하게된다. 그러나이러한혼합분포를추정하는경우몇개의분포를사용하여개체군을표현하는것이적합한가를결정하기어려운문제가있으며, 각세부개체군에존재하는우수한부분해들을잘혼합하지못하는결점이있다. 본논문에서는변분베이지안혼합인자분석 (varatoal Bayea mxture of factor aalyzer - vbmfa) [] 을사용한개체군의분포추정을통해실수공간에서의최적화문제를해결하는방법을제안한다. 이기법은변분근사화를통해혼합분포의개수및각세부개체군의분포추정을위해필요한확률모델의복잡도를자동으로결정할수있다. 또한잠재변수 (latet varable) 를이용한독립적표본추출이가능하게되어개체군내에포함된부분해들의결합을효율적으로수행할수있다. 논문의구성은다음과같다. 우선 절에서는 EDA에대하여간략히요약하고, 최근에제안된다중분포를사용하는 EDA에대하여살펴본다. 3절에서는변분베이지안혼합인자분석기법의이론적배경을설명하고, 4 절에서는이기법을사용하여어떻게실수공간에서의최적화문제를효율적으로해결할수있는지를기술한다. 5절에서는잘알려진함수최적화문제와시스템생물학에서다루고있는생화학네트워크의동적모델링을위한매개변수추정문제에대하여기존에제안된 EDA 와그성능을비교하며, 끝으로 6절에서결론을맺는다.. 분포추정알고리즘기존의진화알고리즘에서는임의의교차와돌연변이연산에의하여만들어진새로운탐색점이부모가갖고있는좋은부분해들을결합하거나변형하여그품질을개선시켜줄것을기대한다. 그러나문제가복잡해지면그성능향상을교차나돌연변이연산의무작위성에만의존하는것은한계가있다. 분포추정알고리즘은이러한결점을극복하고자개발되었으며, 주어진개체군에존재하는적합도가좋은개체들로부터확률분포를추정하여보다효율적인탐색을수행한다. 즉, 기존의진화알고리즘들과는달리교차나돌연변이연산을이용하지않고, 학습된확률분포로부터표본추출을통해새로운탐색점을만들어낸다 ( 그림 ). 그림 분포추정알고리즘의흐름도결국 EDA의핵심요소는이확률분포를잘추정하여주어진문제에존재하는변수들사이의관계를파악한후다음탐색을효과적으로이끌어가도록하는것이다. 서론에서언급한바와같이, 최근들어실수공간에서의복잡한문제를해결하기위해서정규혼합 (ormal-mxture) 모델을사용하는연구가활발히진행되고있으며그대표적인예가 MIDEA (mxture vero of terate ety etmato evolutoary algorthm) [7] 이다. 여기서는혼합분포의개수를추정하기위해먼저전체개체군중성능이좋은개체들을선택하여, leaer-follower 군집화 [3] 방법의일종인 BEND (boug box Euclc ormalze tace) leaer 알고리즘으로군집화를수행한다. 그후각군집에대하여가우스망 (Gaua etwork) 을학습한다. 가우스망은베이지안망 (Bayea etwork) 과그구조적특성은같으나, 각변수 x 에대한노드가다음과같은정규분포를나타낸다. x pa St,( µ, b, σ )) N( µ b ( x j St x j pa j µ ), σ ) 여기서 는가우스망의구조 St가주어졌을때 x j
변분베이지안혼합인자분석에의한분포추정을이용하는진화알고리즘 073 의부모를나타내며, 는평균, 는 가주어졌을때의조건부분산이다. 그리고 b j 는 x j 와 x 사이의관계강도를나타내는선형계수이다. 이러한가우스망은다변수정규분포를나타내면서변수들간의관계를명시적으로표현한다. 따라서 MIDEA는개체군의각군집들이가우스망에의하여정규분포로표현되는정규혼합모델을이용하게되는것이다. 그러나이방법은비록온라인군집화방법을사용하여군집의개수를자동적으로추정하기는하지만, 군집화와확률모델의학습이분리되어있으므로군집화가잘못이루어질경우전체개체군의확률분포학습이잘못될가능성이있다. 또한복잡한분포의학습이가능하기는하지만, 각가우스망에의하여표현되는세부개체군내의우수한부분해들을효과적으로결합하지못하는단점이있다. 또다른정규혼합모델을이용하는예로서정규커널확률분포를사용한 IDEA가있다 [4]. 이것은혼합모델의극단적인형태로서모든데이타, 즉선택된개체마다하나의밀도함수가정의되어다음과같은식으로나타내어진다. τn pop / ( (π ) ( x x x) = exp τn pop = σ = σ = ) ) 여기서 N pop 는전체개체군의크기, τ는선택비율 ( 단, 0<τ ), 는주어진문제의차원, 그리고 는 번째데이타의 번째원소를나타낸다. 이분포는일반적인정규분포보다데이타의지역적특성을잘반영하기는하지만, 주어진데이타에과적합하기쉬워정규혼합모델보다는널리사용되지않는다. 이러한결점을극복하고주어진데이타에나타난계층적특성을파악하기위하여 MBOA (mxe Bayea optmzato algorthm) 가제안되었다 [5]. 이것은원래이산변수를다루는문제를위하여개발된베이지안망기반의 hboa (herarchcal Bayea optmzato algorthm)[6] 를연속변수도함께다룰수있도록확장한것이다. 여기서는그림 에보여지는바와같이결정나무를사용하여전체탐색공간을나눈후에각단말노드에대하여정규커널확률분포를학습한다. 이러한결정나무를각변수에대하여순차적으로만들되, 이미만들어진결정나무를고려하여두변수사이의양방향의존성은없도록한다. 또한기존의 EDA에서는새로생성된개체들전체가새로운세대를이루거나, 이전세대에서선택되지못한개체들을전부대체한다. 이에비하여, MBOA에서는토너먼트기법으로부모를선택하여확률모델을학습한후, 이모델로부터추출된자손개체각각에대하여이전세대의전체개체군중일부 ( 그비율은 w로정의 ) 를임의로골라, 그중에서가장비슷한, 즉실수공간에서 그림 MBOA에서결정나무를사용한확률분포학습의예 [7] 는거리가가장가까운개체와의적합도를비교한다. 만약새로운개체가더좋다면그개체를대체하고, 그렇지않으면새로운개체를버린다. 이러한제한된토너먼트대체 (retrcte touramet replacemet RTR) 기법은혼합분포로학습된개체군의다양성을유지하는데더욱도움을준다 [5,6]. 그러나 MBOA는결정나무를사용하므로축에평행하게만탐색공간을나눌수있다. 따라서그림 와는달리축과평행하지않고복잡한모양으로현재개체군이분포하고있을경우에대해서는내재적인특성을파악하기어렵게된다. 본논문에서는위에서설명한기존 EDA들의단점을극복하기위하여변분베이지안혼합인자분석에의한분포추정을사용하는진화알고리즘을제안한다. 다음절에서는 vbmfa의이론적기반이되는잠재변수모델과혼합인자분석및변분근사화를간략히요약하고, 이것이어떻게복잡한개체군의분포추정을효율적으로수행하는지살펴본다. 또한이어지는 4절에서는 vbmfa 에의하여추정된분포와잠재변수를사용하여주어진최적화문제를해결하는방법을설명한다. 3. 변분베이지안혼합인자분석 3. 잠재변수모델과인자분석잠재변수모델 [8] 은 차원의데이타 x에대한분포 x) 를 보다적은 k차원의잠재변수 z를사용하여표현하고자한다. 이모델에서의가장중요한가정은잠재변수가주어졌을때데이타의각변수들은서로조건부독립이라는것이다. 따라서데이타와잠재변수의결합분포는다음과같이정의된다. x, z) = z) x z) = z) z) = 이때, 조건부확률 x z) 는잠재변수로부터데이타로의사상 (mappg) 에의하여표현된다. 즉, x = y(z; Λ) ε가성립하며, 여기서 y(z;λ) 는매개변수 Λ를갖 x ()
074 정보과학회논문지 : 소프트웨어및응용제 3 권제 호 (005.) 는 z 에대한함수이고, ε 는 z 와는무관한오차이다. 만약 ε의원소들이서로독립이라면, x에대한조건부확률은식 () 에서와같이쉽게인수분해가된다. 따라서잠재변수모델은오차에대한분포 ε), 사상 y(z;λ), 그리고잠재변수에대한사전확률분포 z) 를지정함에의하여정의된다. 결국데이타에대한분포 x) 는다음과같이잠재변수에대한주변화 (margalzato) 에의하여얻을수있다. p ( x) = x z) z) z () 그러나이러한적분은 x z) 와 z) 가특별한형태를취하는경우를제외하고일반적으로는쉽게구할수없다. 인자분석 (factor aaly) [9] 은이상에서설명한잠재변수모델중가장단순화된형태로서다음과같은선형사상에기반을두고있다. x = Λz µ ε 여기서 Λ는인자적재행렬 (factor loag matrx) 이며 μ는주어진데이타의평균이다. 또한 z) 의사전확률분포는보통평균이 0이고공분산행렬이항등행렬이되는정규분포 N(0, I) 를지정하는반면, 오차의분포는평균은 0이지만공분산행렬 Ψ은대각행렬이되는정규분포 N(0, Ψ) 로지정한다. 이경우식 () 에의하여, 데이타에대한분포 x) 는평균이 μ이고공분산행렬이 ΛΛ T Ψ으로주어지는정규분포 N(μ, ΛΛ T Ψ) 가된다. 결국인자분석은주어진데이타를가장잘설명할수있는인자적재행렬 Λ과오차의공분산행렬 Ψ을찾는것이된다. 이과정은보통잠재변수값의추정과함께 EM 알고리즘의적용을통해이루어진다 [0]. 이러한인자분석에서자유도 (egree of freeom) 의개수는정규분포에서의일반적인완전공분산행렬의자유도의개수보다작기때문에, 주어진데이타의개수가적다하더라고과적합의위험이적어지며, 따라서더효율적으로주어진데이타의분포를추정할수있게된다. 3. 혼합인자분석하나의인자분석에의하여표현되기어려운복잡한분포의경우, 정규혼합모델과마찬가지로다수의인자분석을사용하게된다. 즉, 혼합인자분석은인자분석의가중합으로주어진데이타의분포를다음과같이표현한다. S = S x) = π x ) = x z, ) z ) ) z = 여기서 S 는혼합모델을이루는인자분석모델의개 수이며, π = ) 는각인자분석모델의혼합비율로서 S = π = 과 π 0의두가지제약조건을만족한다. 또한 x ) 는하나의인자분석모델이나타내는분포이며, 내재변수에대한사전분포는역시표준정규분포, 즉 N(0, I) 를가정하기때문에 p ( z ) = z) 가된다. 결국혼합인자분석은혼합분포를사용하여주어진데이타의군집화를수행함과동시에각분포내에서는정규분포보다더적은수의자유도에의하여주어진데이타에존재하는변수들간의관계를효율적으로표현할수있게된다. 혼합인자분석을표현하기위한매개변수들의집합을 S θ = {( µ, Λ, π ) =, Ψ} 라할때, 이역시 EM 알고리즘에의하여학습이가능하다 []. 그러나일반적으로혼합분포의개수가클수록그리고각분포에서잠재변수의차원이클수록가능도 (lkelhoo) 도역시증가하기때문에, 가능도를최대화하는 EM 알고리즘으로는몇개의분포와어느정도의잠재변수를사용하여주어진데이타를설명하는것이가장적합한지를결정할수없게된다. 3.3 베이지안혼합인자분석과변분근사화이러한단점을극복하기위해학습해야할매개변수들을확률변수로생각하여가능한매개변수에대한평균을취함으로써데이타의로그주변가능도 (log margal lkelhoo) 를계산할수있고, 이것의하한을 Jee의부등식을이용하여다음과같이표현할수있다. l p ( x) = l x, Θ = l x, x, Θ l Θ (3) 여기서 Θ 는잠재변수를포함하여우리가모르는모든매개변수들을의미하며, 는사후분포 Θ x) 에대한다루기쉬운근사화를나타낸다. 변분베이지안 EM 알고리즘은반복적인과정을통해위의하한값을최대화한다. 이과정은결국 와 Θ x) 의 KL 발산량 (Kullback-Lebler vergece) 을최소화하는것과같으며, 복잡한모델에대한확률을낮추어과적합을방지하는효과를가져온다. 또한데이타의로그주변가능도는서로다른복잡도를갖는모델들 ( 예를들면, 혼합분포의개수가다른모델들 ) 에대하여주어진데이타에적합한모델을찾기위한비교기준을제공한다. 실제로이러한변분근사화를수행하기위해그림 3과같은혼합인자분석에대한베이지안확률모델을도입한다 []. 여기서는혼합인자분석을정의하기위한매개변수들에대한확률분포를도입하고, 이분포를위한
변분베이지안혼합인자분석에의한분포추정을이용하는진화알고리즘 075 그림 3 혼합인자분석에대한베이지안확률모델 ([] 에서변형 ) 사전확률분포및초매개변수 (hyper-parameter) 들을정의한다. 이경우그림 3에서주어지는조건부독립성에 의하여다음과같이로그주변가능도를표현할수있다. ( * * * * * * l x) = l π α m ) π ν a, b ) ν Λ ν) Λ µ µ, ν ) µ τn pop S π) z ) x, z, Λ, µ, Ψ) z = = (4) 여기서 ν 는인자적재행렬의각열에대한정밀도 ( 분산의역수 ) 를위한매개변수로서, 인자적재행렬의각열은평균이 0인정규분포를가정하기때문에이러한사전확률분포를고려하면이값이커질수록그열은 0으로수렴하게된다. 따라서해당인자는데이타생성에아무런역할을하지못하게되고, 결국우리는더적은차원으로주어진데이타를표현할수있게된다. 매개변수와우리가모르는변수들에대한다룰수있는분포 π, ν, Λ, μ) 를도입하고, 이것의근사화를 π) ν) Λ, μ) 로인수분해하여나타내면식 (4) 에나타난로그주변가능도의하한은식 (3) 을이용하여다음과같이정의할수있다. l x) * * π α m ) π)l π π) S = τn pop * * ν a, b ) ν ) l ν ) ~ * * ~ Λ ν, µ, ν ) ~ Λ )l ~ Λ ν Λ ) S π) z ) ) π)l π z )l ) z ) ~ Λ ~ ) Λ z )l x, z, Λ ~, Ψ) z = = (5) 여기서 Λ ~ 는 Λ와 μ의연결인 [Λ μ] 를나타낸다. 이하한을최대화하기위하여각 ) 분포에대한함수적미분을구하고이값을 0으로만드는분포를찾는다. 이것을구해보면 ) 에대한최적사후분포는사전확률분포와마찬가지로켤레 (cojugate) 형태가된다. 또한사전확률분포에대한초매개변수도같은방법으로추 ] 정할수있다 ( 최적사후분포들및초매개변수에대한자세한유도는 [] 를참조 ). 변분 EM 알고리즘에서는이렇게구한최적사후분포와초매개변수들을순차적으로갱신하는과정을반복하여로그주변가능도의하한을최대화하게된다. 이러한과정으로학습이진행될때, 혼합분포를구성 하는특정성분 에대하여 ) = 0 이되는경우가있다. 이것은이성분이더이상어떤데이타도설명하지않음을의미한다. 즉, 주어진데이타를생성하는데아무런기여를하지못하는성분임을의미한다. 따라서, 혼합분포에서이성분을제거하여혼합분포의개수를줄일수있다. 혼합분포에서특정성분의삭제는자동적으로수행할수있는반면, 새로운성분을생성은자발적으로일어나지않기때문에이를위한알고리즘이필요하다. 여기서는변분 EM 알고리즘에서하한이어느정도수렴했을때, 이하한값에기여도가적은성분을확률적으로선택한후, 그성분을 개의성분으로분해함으로써혼합분포의개수를늘이는방법을채택한다. 하한값에대한기여도는식 (5) 에서처음항을제외하면뒤쪽은각성분에대한값으로분해가가능하기때문에쉽게계산할수있다. 이렇게증가된개수의혼합분포로변분 EM 알고리즘을추가로수행하여그하한값이원래수렴했던하한값이상으로향상되지못하면, 이증가를기각하고원래의혼합분포로돌아간다. 이과정은가역도약마르코프연쇄몬테칼로 (reverble jump Markov cha Mote Carlo)[3] 방법과유사하게혼합분포의개수추정을자동화한것이다. 4. 변분베이지안혼합인자분석에의한진화알고리즘 4. 변분베이지안혼합인자분석에의한개체군의분포추정연속된공간에서의최적화문제를다루는진화알고리즘에서는최적점을찾기위하여실수벡터들의개체군을유지한다. 이개체군중에서적합도에따라상위 τn pop 개를고른후에, 이것을데이타로하여 3절에서설명한변분베이지안혼합인자분석모델을학습한다. 이방법은비슷한개체들을여러개의그룹으로묶는과정과각그룹에대한분포추정을동시에수행하는것으로볼수있다. 즉, 선택된개체들을자동적으로세부개체군으로나누게되며, 각세부개체군에대하여변분베이지안기법으로잠재변수의차원과그값및매개변수들을추정하여, 주어진최적화문제를해결하기위한변수들간의관계를암시적으로파악하게된다. 선택된개체들의분포추정을위하여본논문에서는
076 정보과학회논문지 : 소프트웨어및응용제 3 권제 호 (005.) MATLAB으로작성된 vbmfa 프로그램 ) 을사용한다. 잠재변수의차원은최대로하여주어진문제의크기보다 이적은 -로설정하였으나, 3.3절에서제시한바와같이주어진데이타를설명하기위해필요한잠재변수의차원은 vbmfa 알고리즘에의하여자동적으로학습된다. 또한변분 EM 알고리즘은로그주변가능도의하한값의변화율이 0.0이하가될때까지반복한다. 4. 새로운개체군의생성베이지안진화알고리즘 [4] 의관점에서보면이전세대의개체군에기반하여학습된확률모델은새로운개체군을생성하기위한사전확률분포를나타내는모델로서사용된다. 변분베이지안혼합인자분석을통하여선택된개체군을표현하기위한매개변수들의집합 θ {(, Λ S = µ, ), Ψ π = } 이구해지면, 각세부개체군은정규분포 N(μ, Λ Λ T Ψ) 로표현되고그혼합비율은 π 가된다. 따라서이혼합분포로부터 (-τ)n pop 개의새로운개체들을추출한후, MBOA에서사용된 RTR 기법과유사하게제한된대체 (retrcte replacemet) 기법으로새로운개체군을생성하게된다. 이와같은일반적인정규분포에서의추출과더불어, 혼합인자분석기법을사용한모델인경우에는식 () 에서와같이잠재변수를이용한각변수의독립적인추출이가능하므로, 이특성을이용하면기존개체군에존재하는우수한부분해들과의결합이가능하다. ( 기본적으로이전세대의최적점 x bet 와의결합을고려하나, 항상최적점과의결합을수행할필요는없다.) 기존개체군에서결합을위해선택된개체를 x r 이라하고, 분포학습에사용된개체들중임의로고른한개의개체를 x m 이라고하면, 변분 EM 알고리즘에의하여학습된혼합인자분석모델및잠재변수값 z m 을사용하여다음과같이새로운개체 x ew 를생성하기위한사전분포를만들수있다. ew m ew r { λ x z, θ) ( λ) ( x x )} ew r m x x, z, θ) = δ = (6) 여기서 ( ew z m m p x, θ) 는정규분포 N( Λ z µ, Ψ ) 로표현되며, 이정규분포를표현하는매개변수들은변분 EM 알고리즘을통해구한최적분포 m ) 에따라, x m 이속한혼합분포의성분 m 을지정하여얻을수있다. 즉, x m 을생성했을확률에의하여 m 을지정한후, 해당성분을나타내는매개변수들을사용한다. 또한 x m 에대한잠재변수값도역시최적분포 z m m ) 으로부터추출할수있다. 이렇게 λ의확률로 번째변수에대 ) [ole] http://www.ce.buffalo.eu/faculty/mbeal/oftware/vbmfa/vbmfa.tar.gz 한새로운값을학습된모델과잠재변수를사용하여생성할수도있고, (-λ) 의확률로기존의개체 x r 로부터 번째변수의값을얻을수도있다. 이것은 [5] 에서이산변수를다루기위해제안된유도돌연변이 (gue mutato) 기법과유사하지만항상변수들의독립관계를가정하는분포를채택할필요가없으며, 변수들사이의상관관계를반영하면서도잠재변수를이용하여각변수들을독립적으로추출함과동시에이미존재하는부분해와의결합을쉽게수행할수있는장점이있다. 이렇게새로생성된 x ew 의적합도가 x r 의적합도보다좋으면 x ew 가 x r 을대체한다. 이과정이 N mx 만큼반복되면 x r 과선택된개체군내의서로다른 x m 사이에존재하는부분해들의결합시도중가장적합도가좋았던새로운개체가현재개체군에남게된다. 이과정을포함하여제안된알고리즘의전체흐름이그림 4에제시되어있다. 5. 실험및결과 5. 함수최적화제안된알고리즘의성능을평가하기위해우선잘알려진함수최적화문제들에대하여기존의분포추정진화알고리즘인 MBOA 및 MIDEA와비교하였다. 또한기본적인비교기준을제시하기위해실수코드유전알고리즘 (real coe geetc algorthm - RCGA) 도적용하였다. RCGA에서는분포추정알고리즘과같이실수벡터들을개체군으로유지하지만, 토너먼트크기가 인선택을통하여부모를고른후에 점교차연산과가우스돌연변이를사용하여새로운개체를생성한다. 여기서가우스돌연변이는각변수에표준정규분포로부터추출된값을더하는것을의미한다. 이때교차확률과돌연변이확률은각각 90% 와 0% 로설정하였다. 다른분포추정알고리즘들의설정은원래의연구에서제안된값을그대로사용하였다. MIDEA에서확률모델을학습하기위해선택되는우수한개체의비율 τ는 30% 이며, BEND 군집화알고리즘을위한분계값은 0.3으로설정하였다. 또한온라인군집화알고리즘에서필요한만큼충분히군집이이루어질수있도록최대군집의개수는 0 까지허용하였다. 그리고각군집을표현하는확률모델인가우스망에서각변수는최대 -개의부모를가질수있다. 이역시확률모델의표현력을최대한허용하는것이다. MBOA에서는토너먼트크기가 인선택을반복하여전체개체군중 50% 의개체를골라확률모델을학습한다. 또한제한된대체기법에서새로운개체와의거리비교를위해임의로선택되는개체군의비율 w 는 5% 로설정하였다. 변분베이지안혼합인자분석에서도잠재변수의차원은최대 -까지허용한다. 적합
변분베이지안혼합인자분석에의한분포추정을이용하는진화알고리즘 077 그림 4 제안된변분혼합인자분석에의한진화알고리즘의개략적흐름 그림 5 f 에대한결과 ( 왼쪽 : 5번실행에서얻은최적해의값과그값을얻기까지필요한적합도평가회수, 오른쪽 : 5번실행중중앙값을나타낸실행에서의적합도변화, 괄호안은최적개체군의크기 ) 도에따라상위 50% 의개체가선택되어확률모델의학습을위한데이타로서사용되며, 제한된대체기법에서임의로고르는개체의비율은역시 5% 이다. 또한부분해들의결합비율 λ는 0% 이며결합을위한반복회수 N mx 는 N pop/로설정하였다. 성능의비교를위해사용된함수들과탐색공간및허용된최대평가회수가표 에 제시되어있다. f 은비록다봉 (multmoal) 함수는아니지만변수들이서로연관되어있고, 적합도공간에서볼때매우좁고긴골짜기안에최적해가존재하기때문에 ( 모든변수값이 일때최소 ) 최적화가어려운문제로알려져있다. 그림 의결과를보면 MIDEA는탐색초기에지역해에
078 정보과학회논문지 : 소프트웨어및응용제 3 권제 호 (005.) 표 사용된평가함수와탐색공간및허용된최대평가회수 ( = 0, 최소값은모두 0) f 함수탐색공간최대평가회수 f = {00( x x ) ( x ) } [-5., 5.] 5.0 0 5 = = 0 e 0exp 0. x exp co(π x [-3, 3].0 0 5 = = ) π = 0 ( y x f 3 = x co [-600, 600].0 0 5 4000 = = 4 ( πy) ( y ) { 0 ( πy = f ) ] = u( x,0,00,4), m k( x a), u( x, a, k, m) = 0, m k( x a), f 5 = 0. (3πx ) ( x = ) { (πx )} y = ( x ) 4 x > a a x a x < a ] = )} ( x ) { (3πx )} u( x,5,00,4) [-50, 50].0 0 5 [-50, 50].0 0 5 빠져전혀해를찾기못하고있는데, 이것은일단골짜기에접근은하지만그골짜기안으로탐색이이루어지지못하고있음을보여준다. RCGA는 MIDEA보다도더일찍지역해에수렴하여전혀답을찾지못한다. MBOA에서는축에평행하게만공간을나누어분포를추정할수있지만실제로이함수의적합도공간이나타내는골짜기는선형이아니기때문에, 가장빨리골짜기로의접근함에도불구하고그후의탐색은더디게진행되어해를찾는데실패하였다. 이에비하여제안된알고리 즘은대부분의수행에서해를찾았으며, 그탐색도훨씬효율적으로이루어짐을확인하였다. f 와 f 3 은대표적인다봉함수로서역시변수들간의분리가불가능하다. 즉, 각변수를독립적으로취급하여최적화할수없다 ( 모든변수값이 0일때최소 ). 또한비록봉우리의분포가규칙적이나, 문제차원이커질수록지역최소점 (local mmum) 의개수가지수적으로증가하여 [] 최소값을찾기어렵게된다. 그림 6에서제시한바와같이 f 의경우에는 RCGA를제외한모든방법이 그림 6 f 에대한결과 ( 왼쪽 : 5 번실행의결과비교, 오른쪽 : 중앙값을기록한실행 )
변분베이지안혼합인자분석에의한분포추정을이용하는진화알고리즘 079 성공적으로최적해를찾지만, 제안된방법이가장적은수의적합도평가회수를필요로한다. 또한 f 3 에서는비록모든방법에서최적해를찾지못하였으나, 제안된방법의성능이가장좋고, 탐색속도도가장빠르다 ( 그림 7). 다봉함수의경우에기존의방법과비교하여제안된방법이월등히탐색속도가빠른것은, 지역최소점에존재하는해들이갖고있는유용한부분해들을학습된혼합분포로부터잠재변수를이용한추출을통해효율적으로결합할수있기때문이다. f 4 와 f 5 도역시다봉함수로서문제차원이커질수록지역최소점의개수가지수적으로증가한다. 또한표 에서주어진바와같이 u함수에의하여적합도공간에단절이존재하는함수이다. f 에서와마찬가지로이함수들에대해서도 RCGA를제외한모든알고리즘이성공적으로해를찾았지만, 역시제안된방법이가장적은수의적합도평가회수를필요로한다 ( 그림 8과 9). 그리고다봉함수에서는제안된방법이기존의방법보다더적 은수의개체군으로도더효율적으로해를찾을수있었다. 이것은변분혼합인자분석기법이잠재변수를사용하여더적은자유도로혼합분포의추정이가능하고효율적으로부분해의결합을수행할수있기때문이다. 기존의방법들을비교해보면, 쉽게해를찾은 f, f 4, f 5 의경우에는 MIDEA가더많은개체군을필요로하지만더빨리탐색을수행한다. 이것은탐색공간에다수의지역최적점이존재한다하더라도전역최적점 (global optmum) 으로의접근이비교적용이하다면, 부분해의결합없이여러개의분포를사용함으로써각분포가탐색공간을분할하여최적화를수행할수있음을보여준다. 그러나 f 3 의결과에서알수있듯이, MIDEA처럼부분해를결합하는방법이없을경우문제가복잡해지면아무리혼합분포를사용한다하더라도지역최적점으로일찍수렴하는현상이발생한다. 반면 MBOA는비교적크기가작은개체군으로도해를찾을수있고부분해들의결합도가능하지만, 분포추정모델의한계로인하여 그림 7 f 3 에대한결과 ( 왼쪽 : 5 번실행의결과비교, 오른쪽 : 중앙값을기록한실행 ) 그림 8 f 4 에대한결과 ( 왼쪽 : 5 번실행의결과비교, 오른쪽 : 중앙값을기록한실행 )
080 정보과학회논문지 : 소프트웨어및응용제 3 권제 호 (005.) 그림 9 f 5 에대한결과 ( 왼쪽 : 5 번실행의결과비교, 오른쪽 : 중앙값을기록한실행 ) 부분해들의혼합이더딘것을확인할수있다. 끝으로식 (6) 에제시된부분해들의결합을위한분포가어느정도효과를발휘하는지살펴보기위하여제시된알고리즘의흐름 ( 그림 4) 에서 5.의과정을생략하고같은함수최적화문제들에적용해보았다. 그림 0 에서보여지는바와같이모든문제에있어서식 (6) 의분포를사용하여부분해들을결합하는과정이존재하는경우가더좋은성능을보였다. 특별히이전의실험결과들에서언급했듯이최적해로의접근이어려운함수 f 과 f 3 에서그효과가더욱분명하게나타난다. 그림 0 부분해들의결합을위한분포의사용유무에따른함수최적화결과비교 (5번실험의중간값 ) 5. 생화학시스템의동적모델링기술의발달로시간이흐름에따라어떤생화학시스템이변화하는것을기록한데이타가축적됨에따라이시스템의상태전이및시스템을구성하는각물질사이의관계를설명해줄수있는수학적모델을자동적으로만들려는연구가진행되고있다. 즉, 이모델은어떠한 방식으로든그시스템을구성하는물질들사이의상호작용관계를나타낼수있는구조와, 시간에따라서로어느정도로영향을주고받는지를나타내는매개변수들을동시에표현하는방법을필요로한다. 이를위한대표적인수학적모델이다음과같은정형화된형태의연립미분방정식으로주어지는 S-ytem이다. X t = α m j= X gj j β m j= 여기서 X 는생화학시스템을구성하는각물질의농도를나타내며, 이중 개는시간에따라그농도가변하는물질이고 m개는항상같은농도를유지하는물질이다. 또한실수값을갖는 g j 와 h j 는 X 에대한 X j 의영향을정량적으로표시한다. 그리고음수가아닌실수값으로나타나는 와 는반응속도상수를의미한다. 위식에서앞쪽은 X 를증가시키는작용을, 반대로뒤쪽은감소시키는작용을표현한다. 이러한 S-ytem은연립미분방정식의형태로서자연스럽게시간에따른시스템의변화를표현할수있으며, g j 와 h j 의값으로물질들간의상호관계도표현할수있는장점을갖고있다. 그러나 S-ytem을사용하여어떤생화학시스템을표현하기위해서는, 농도가변하지않는 m개에대한매개변수가알려져있다고가정하더라로총 () 개의매개변수값들을추정해야한다. 주어진데이타에대한알맞은 S-ytem을찾기위한시도로서진화알고리즘이사용되어왔다. 특히실제생화학시스템은희박한망으로표현된다는사실로부터구조와매개변수를분리하여표현하는진화연산기법이연구되고있다 [6,7]. 여기서시스템의구조는시스템을구성하는물질간의관계유무를나타내며, g j 와 h j 에서 와 j에따라 0의값을갖는것과 0이아닌값을갖는것을구분하여표현한다. 따라서구조가주어지면 와 X hj j
변분베이지안혼합인자분석에의한분포추정을이용하는진화알고리즘 08 뿐만아니라 0이아닌 g j 와 h j 에대해서주어진데이타를설명하기위한매개변수값을추정해야한다. 본실험에서는실제시스템의구조가알려져있다고가정할때, 변분혼합인자분석을사용한진화알고리즘에의한 S-ytem의매개변수값추정을수행함으로써제안된방법의확장성과실제문제에의적용가능성을살펴본다. 그림 (a) 에제시된인공적인유전자조절망은 S-ytem 모델을학습하기위한진화알고리즘의성능평가를위해널리사용되어온것이다 [7]. X 과 X 4 는유전자로부터전사된 mrna의농도를나타내고, X 는 X 의 mrna가번역되어효소로서작용하는단백질의농도이며, X 5 는 X 4 의 mrna가만드는단백질의농도로서다른유전자의발현을조절하는역할을하게된다. X 3 는유도물질의농도로서억제인자와결합을통해억제인자의효과를감소시킴으로써특정유전자의발현을유도할수있다. 관측된데이타를얻기위해본실험에서는그림 (b) 에주어진실제 S-ytem으로부터초기값 X(0) = [0.70 0. 0.4 0.6 0.8] 을사용하여수치적분을통해각각 5개씩총 75개의데이타를생성하였다 ( 그림 ()). 이유전자조절네트워크의구조 ( 그림 (c) 의 g j 와 h j 에서 0 이아닌부분 ) 가주어졌다고가정하고, 와 는 [0.0, 5.0], g j 와 h j 는 [-3.0, 3.0] 의범위에서탐색을수행한다. 즉, 총 3차원의매개변수값을추정해야하는것이다. 실험설정은모두 5.절과동일하며최대적합도평가회수는.0 0 5 이다. 각개체에의하여표현되는 S-ytem은역시같은초기값을사용하여수치적분을통해농도로변환되며, 다음과같이주어진데이타와의상대적인제곱오차 (relatve quare error) 로서적합도가평가된다. T X ( t) X ( t) = t= X ( t) 여기서 X (t) 는각개체에의하여예측된값이고, (t) X 는실제로관측되어데이타로주어진값이다. 또한 T는주어진시계열데이타의개수이다. 일반적으로추정해야하는매개변수의차원에비하여주어진데이타의개수가부족하기때문에, 이오차를최소로하는매개변수의탐색공간은다봉함수가되어다수의지역최소점이존재하는것으로알려져있다 [7]. 그림 (a) 인공유전자조절망 [7] (b) 해당 S-ytem (c) 백터와행렬표기 () 이유전자조절망을위한 S-ytem의매개변수추정을위해사용된시계열데이타 (T = 5)
08 정보과학회논문지 : 소프트웨어및응용제 3 권제 호 (005.) 그림 S-ytem 에대한매개변수추정결과 ( 왼쪽 : 5 번실행의결과비교, 오른쪽 : 중앙값을기록한실행 ) 5.절의비교실험에의하여일반적으로전통적인유전알고리즘보다는분포추정진화알고리즘의성능이더우수함을확인하였기때문에, 여기서는분포추정진화알고리즘들의성능만을비교한다. 각분포추정진화알고리즘을 5번씩수행한결과가그림 에제시되어있다. 적합도, 즉시간에따른각물질의농도변화로주어지는데이타에대한상대적인제곱오차의관점에서보면 MIDEA보다는제안된변분베이지안혼합인자분석을사용한진화알고리즘과 MBOA가더좋은성능을보이지만, 두알고리즘사이에는큰성능차이를보이지않는다. 다만제안된방법의탐색속도가 MBOA보다는약간빠르다. 그러나그림 에제시된실제매개변수의값과분포추정진화알고리즘이추정한해들의거리를비교해보면 ( 그림 ), 제안된방법이찾아낸것들이월등히우수한품질을갖고있음을확인할수있다. 즉, 오차는작지만실제매개변수의값과는거리가먼지역최소점에빠지지않고전역최소점으로의탐색이성공적으로이루진것이다. 이것은주어진시계열데이타를설명하는모델을학습하는관점에서생각할때, 주어진데이타에만과적합되는것이아니라해당시스템의일반적인특성을잘설명할수있는매개변수를추정한것으로볼수있다. 6. 결론본논문에서는변분베이지안혼합인자분석에의한분포추정진화알고리즘을제안하였다. 이방법은개체군에존재하는우수한해들에대한혼합분포를추정함에있어그혼합분포의개수를자동으로설정할수있었고, 주어진데이타의차원보다더적은개수의잠재변수를사용함으로써각세부개체군의분포를효율적으로나타낼수있었다. 또한이와같이추정된혼합분포에의하여표현되는개체군의다양성을유지함과동시 에, 학습된분포로부터잠재변수를이용한추출을통해기존개체군에존재하는유용한부분해들의효과적인결합을수행할수있었다. 잘알려진함수최적화문제에대하여제안된방법은기존의분포추정진화알고리즘보다더좋은성능을보였으며, 비슷한성능을나타낸경우에도그탐색은더빠르게진행됨을확인할수있었다. 또한생화학시스템의동적모델링을위한매개변수추정도성공적으로수행하였으며, 그해의품질또한기존의알고리즘보다우수하였다. 제안된방법은이와같이지역최적점이다수존재하는다른실세계문제에도적용될수있을것으로기대된다. 참고문헌 [ ] Schwefel, H.-P., Evoluto a Optmum Seekg, Joh Wley & So, New York, 995. [ ] Mühlebe, H. a Paaβ, G., "From recombato of gee to the etmato of trbuto I. Bary parameter," Lecture Note Computer Scece, Vol. 4, pp. 78-87, 996. [ 3 ] Larraaga, P., "A revew o etmato of trbuto algorthm," Etmato of Dtrbuto Algorthm: A New Tool for Evolutoary Computato, pp. 57-00, Kluwer Acaemc Publher, 00. [ 4 ] Pelka, M., Golberg, D. E., a Lobo, F. G., "A urvey of optmzato by bulg a ug probabltc moel," Computatoal Optmzato a Applcato, Vol., No., pp. 5-0, 00. [ 5 ] Tutu, S., Pelka, M., a Golberg, D. E., "Evolutoary algorthm ug margal htogram cotuou oma," Proceeg of the GECCO-00 Workhop Program, pp. 30-33, 00. [ 6 ] Gallagher, M., Frea, M., a Dow, T., "Realvalue evolutoary optmzato ug a flexble
변분베이지안혼합인자분석에의한분포추정을이용하는진화알고리즘 083 probablty ety etmator," Proceeg of 999 Geetc a Evolutoary Computato Coferece, Vol., pp. 840-846, 999. [ 7 ] Boma, P. a There, D., "Avacg cotuou IDEA wth mxture trbuto a factorzato electo metrc," Proceeg of the GECCO-00 Workhop Program, pp. 08-, 00. [ 8 ] Cho, D.-Y. a Zhag, B.-T., "Evolutoary optmzato by trbuto etmato wth mxture of factor aalyzer," Proceeg of the 00 Cogre o Evolutoary Computato, Vol., pp. 396-40, 00. [ 9 ] Mahfou, S. W., Nchg Metho for Geetc Algorthm, Ph.D. the, Uverty of Illo at Urbaa-Champag, 995. [0] Deb, K. a Spear, W. M., "Specato metho," Evolutoary Computato : Avace Algorthm a Operator, pp. 93-00, Ittute of Phyc Publhg, 000. [] Mart, W. N., Leg, J., a Cohoo, J. P., "Ila (mgrato) moel: evolutoary algorthm bae o puctuate equlbra," Evolutoary Computato : Avace Algorthm a Operator, pp. 0-4, Ittute of Phyc Publhg, 000. [] Ghahrama, Z. a Beal, M. J., "Varatoal ferece for Bayea mxture of factor aalyer," Avace Neural Iformato Proceg Sytem, pp. 449-455, MIT Pre, 000. [3] Dua, R. O., Hart, P. E., a Stork, D. G., "Uuperve learg a cluterg," Patter Clafcato, pp. 57-599, E., Joh Wley & So, New York, 00. [4] Boma, P. a There, D., "IDEA bae o the ormal kerel probablty ety fucto," Utrecht Uverty, Techcal Report UU-CS- 000-, Mar. 000. [5] Oceaek, J. a Schwarz, J., "Etmato of trbuto algorthm for mxe cotuoucrete optmzato," Proceeg of the Euro-Iteratoal Sympoum o Computatoal Itellgece, pp. 7-3, 00. [6] Pelka, M. a Golberg, D. E., "Ecapg herarchcal trap wth competet geetc algorthm," Proceeg of 00 Geetc a Evolutoary Computato Coferece, pp. 5-58, 00. [7] Ker, S., Müller, S., Hae, N., Büche, D., Oceaek, J., a Koumoutako, P., "Learg probablty trbuto cotuou evolutoary algorthm - a complete revew," Natural Computg, Vol. 3, No., pp. 77-, 004. [8] Bhop, C. M., "Latet varable moel," Learg Graphcal Moel, pp. 37-403, MIT Pre, 999. [9] Bartholomew, D. J. a Kott, M., Latet Varable Moel a Factor Aaly, E., Arol, Loo, 999. [0] Rub, D. B. a Thayer, D. T., "EM algorthm for ML factor aaly," Pychometrka, Vol. 47, No., pp. 69-76, 98. [] Ghahrama, Z. a Hto, G. E., "The EM algorthm for mxture of factor aalyzer," Departmet of Computer Scece, Uverty of Toroto, Techcal Report CGG-TR-96-, Feb. 997. [] Beal, M. J., Varatoal Algorthm for Approxmate Bayea Iferece, Ph.D. the, The Gatby Computatoal Neurocece Ut, Uverty College Loo, 003. [3] Gree, P. J., "Reverble jump Markov cha Mote Carlo computato a Bayea moel etermato," Bometrka, Vol. 8, No. 4, pp. 7-73, 995. [4] Zhag, B.-T., "A ufe Bayea framework for evolutoary learg a optmzato," Avace Evolutoary Computg, pp. 393-4, Sprger, 003. [5] Zhag, Q., Su, J., a Ta, E., "A evolutoary algorthm wth gue mutato for the maxmum clque problem," IEEE Traacto o Evolutoary Computato, Vol. 9, No., pp. 9-00, 005. [6] 조동연, 장병탁, 생화학시스템의동적모델링을위 한 S-tree 기반의진화연산, 정보과학회가을학술 발표논문집 (II), 제30권, 제호, pp. 83-85, 003. [7] Speth, C, Strechert, F., Speer, N., a Zell, A., "Optmzg topology a parameter of gee regulatory etwork moel from tme-ere expermet," Lecture Note Computer Scece, Vol. 30, pp. 46-470, 004. 조동연 998 년서울대학교컴퓨터공학과학사 000 년서울대학교컴퓨터공학과석사 000 년 ~ 현재서울대학교컴퓨터공학부박사과정. 관심분야는 Etmato of Dtrbuto Algorthm, Evolutoary Computato, Probabltc Moel of Learg a Evoluto, Sytem Bology 장병탁정보과학회논문지 : 소프트웨어및응용제 3 권제 8 호참조