Bayesian Gaussian network classifiers for mass spectra classification

Mas e 'in'A i icial'In elligence'(UPC4URV4UB)' ' ' ' ' ' ' Mas e 'o 'Science'Thesis' Bayesian'Gaussian'ne wo k'classi ie s' o 'mass' spec a'classi ica ion' ! ! Víc o !Manuel!Bellón!Molina! ! ! Ad iso :!Jesús!Ce quides!Bueno!! ! ! ! ! 18!Janua y!2013! ! ! ' Con en s 1 In oduc ion 5 1.1 P o eomics............................. 5 1.2 P obabilis ic classi ica ion . . . . . . . . . . . . . . . . . . . . 6 1.3 S uc u e o he hesis . . . . . . . . . . . . . . . . . . . . . . 7 1.4 Con ibu ions ........................... 7 2 P obabilis ic G aphical models 8 2.1 G aph heo y ........................... 8 2.2 Bayesian and Ma ko ne wo ks . . . . . . . . . . . . . . . . . 11 2.2.1 Bayesian ne wo ks . . . . . . . . . . . . . . . . . . . . 11 2.2.2 Ma ko ne wo ks . . . . . . . . . . . . . . . . . . . . . 12 2.2.3 Equi alences be ween Bayesian and Ma ko Ne wo ks . 12 2.2.4 Ma ko dis ibu ions o e decomposable g aphs . . . . 13 2.3 Condi ional Gaussian ne wo ks . . . . . . . . . . . . . . . . . 14 2.4 Gaussian Join ee classi ie s . . . . . . . . . . . . . . . . . . . 15 3 Lea ning PGM 17 3.1 Maximum likelihood . . . . . . . . . . . . . . . . . . . . . . . 17 3.2 Bayesian model a e aging . . . . . . . . . . . . . . . . . . . . 18 3.2.1 Hype Ma ko dis ibu ions o e decomposable g aphs 19 4 Lea ning CGN by ML 20 4.1 The mul inomial dis ibu ion . . . . . . . . . . . . . . . . . . . 20 4.1.1 Pa ame e lea ning . . . . . . . . . . . . . . . . . . . . 20 4.2 The no mal dis ibu ion . . . . . . . . . . . . . . . . . . . . . 21 4.2.1 Pa ame e lea ning . . . . . . . . . . . . . . . . . . . . 21 4.2.2 Cond ional Gaussian dis ibu ion . . . . . . . . . . . . 21 4.3 Lea ning condi ional Gaussian Ne wo ks . . . . . . . . . . . . 22 5 Lea ning GJTc by BMA 23 5.1 Di ichle dis ibu ion . . . . . . . . . . . . . . . . . . . . . . . 23 2 CONTENTS 3 5.1.1 Conjugancy ........................ 24 5.1.2 P edic i e pos e io dis ibu ion . . . . . . . . . . . . . 24 5.2 Hype in e se Wisha dis ibu ion . . . . . . . . . . . . . . . . 24 5.3 Hype no mal in e se Wisha dis ibu ion . . . . . . . . . . . 25 5.3.1 Conjugacy......................... 26 5.3.2 P edic i e dis ibu ion . . . . . . . . . . . . . . . . . . 26 5.4 Gaussian Join T ee Classi ie s . . . . . . . . . . . . . . . . . . 26 5.5 P edic ing............................. 28 6 Empi ical Compa ison 29 6.1 Spec og am da ase s . . . . . . . . . . . . . . . . . . . . . . . 29 6.1.1 O a ian cance da ase . . . . . . . . . . . . . . . . . . 29 6.1.2 Panc ea ic cance da ase . . . . . . . . . . . . . . . . 29 6.2 Dependency s uc u es . . . . . . . . . . . . . . . . . . . . . . 30 6.3 k-BOXs uc u e ......................... 30 6.3.1 k-BANDs uc u e .................... 31 6.4 Thep io ............................. 31 6.5 Theexpe imen .......................... 32 6.5.1 Measu es ......................... 32 6.6 Resul s............................... 33 6.6.1 O a ianda a ....................... 33 6.6.2 Panc ea ic da a . . . . . . . . . . . . . . . . . . . . . . 33 7 Conclusions and Fu u e Wo k 36 A Dis ibu ions 39 A.1 Mul i a ia e -dis ibu ions . . . . . . . . . . . . . . . . . . . . 39 A.1.1 Ma ginals ......................... 39 A.2 No mal In e se Wisha dis ibu ions . . . . . . . . . . . . . . 39 A.2.1 Conjugacy......................... 40 A.2.2 P edic i e dis ibu ion . . . . . . . . . . . . . . . . . . 40 A.2.3 Ma ginals ......................... 41 Lis o Figu es 2.1 Example o a di ec ed g aph. . . . . . . . . . . . . . . . . . . 9 2.2 Example o an undi ec ed g aph. . . . . . . . . . . . . . . . . 9 2.3 Nai e Bayes s uc u e, wi h ou p edic i e a iables. . . . . . 15 6.1 S uc u e o he g aph o k-BOX model . . . . . . . . . . . . 30 6.2 S uc u e o he co a iance ma ix o k-BOX model . . . . . . 30 6.3 S uc u e o he g aph o k-BAND model . . . . . . . . . . . 31 6.4 S uc u e o he co a iance ma ix o k-BAND model . . . . . 31 6.5 P edic ion o o a ian cance . Accu acy e sus numbe o pa- ame e sinmodel. ........................ 34 6.6 P edic ion o o a ian cance . CLL e sus numbe o pa ame- e sinmodel. ........................... 34 6.7 P edic ion o panc ea ic cance . Accu acy e sus numbe o pa ame e s in model. . . . . . . . . . . . . . . . . . . . . . . 35 6.8 P edic ion o panc ea ic cance . CLL e sus numbe o pa- ame e sinmodel. ........................ 35 4 Chap e 1 In oduc ion The ea ly diagnosis o diseases in pa ien s is a key objec i e o biomedical science and one o he mos impo an ac o s in he ea men o diseases such as cance . The ea ly de ec ion o cance can make he di e ence be ween a success ul ea men and he dead o he pa ien . O a ian cance is diagnosed a la e clinical s age in mo e han 80% o pa ien s and he 5-yea su i al a e is a ound 35% o popula ion, while in ea ly diagnosed pa ien s i exceeds 90% [III e al.2002]. The aim o his wo k is o p esen echniques o he ea ly de ec ion o o a ian cance s based in p obabilis ic analysis o p o eomic spec a. 1.1 P o eomics A p o eome is he en i e p o ein complemen o a cell, issue, o o ganism in a pa icula s a e [Elo and Schwikowski2011]. Wi h he ad ances o he la e yea s he ocus o biomedical esea ch has mo ed om p o ein iden i ica ion owa ds he analysis o p o eome. Among all possible echniques, mass spec- ome y has become popula due o i s abili y o deal wi h a wide ange o di e en p o eins in complex p o eomes. Gene exp ession is a complex p ocess whe e in o ma ion om a gene is ansc ibed, by syn hesis, in a gene p oduc . This p oduc s a e o en p o eins, bu hey also could be unc ional RNA. One impo an componen o gene exp ession is p o ein exp ession. P o ein exp ession s a s a e DNA is an- sc ibed in o messenge RNA (mRNA). The p ocess consis in he ansla ion o mRNA o polypep ide chains, which a e ul ima ely olded in o p o eins. The sequencing echnologies o mRNA a e becoming cheape and inc eas- ing hei a ailabili y. Howe e he analysis o mRNA does no gi e any in- o ma ion abou whe he a p o ein is being exp essed o no . E en hough 5 CHAPTER 1. INTRODUCTION 6 he mRNA o ma ion is he i s s ep o he p o ein syn hesis i does no gi e all he in o ma ion abou which p o eins a e going o be exp essed because di e en p o eins can be gene a ed om a single gene. P o eomic s udy is becoming an impo an ool in biomedical esea ch. A key objec i e o he p o eomic analysis is he ea ly de ec ion o diseases, expec ed o lead o a longe su i al a e. Un o una ely p o eomic da a consis s in a la ge se o da a which equi es he use o classi ica ion ools. 1.2 P obabilis ic classi ica ion Supe ised classi ica ion is a basic ask in da a analysis and pa e n ecog- ni ion. I equi es he cons uc ion o a classi ie , ha is, a unc ion ha assigns a class label o ins ances desc ibed by a se o a iables. The e a e nume ous classi ie pa adigms, among which he ones based on p obabilis ic g aphical models (PGMs) [Lau i zen1996], a e e y e ec i e and well-known in domains wi h unce ain y. PGMs can be di ided in h ee main g oups, hose wi h disc e e a iables, hose wi h con inuous a iables and hose wi h bo h ypes o a iables which a e called mixed models. P obabilis ic classi ie s ha e a disc e e a iable co esponding o he class. The e o e he e will be only wo amily models when we alk abou classi ica ion, disc e e models, i all he a iables a e disc e e, and mixed models, when one o mo e a iables a e con inuous. Also, a widely used assump ion is ha da a ollows a mul idimensional Gaussian dis ibu ion[Geige and Hecke man1994]. This is adap ed o classi- ica ion p oblems by assuming ha da a ollows a mul idimensional Gaussian dis ibu ion ha is di e en o each class, encoding he esul ing dis ibu ion as a Condi ional Gaussian Ne wo k (CGN)[Bø che 2004]. In [La a˜naga e al.2006], La a˜naga, P´e ez and Inza in oduce and e alu- a e classi ie s based on CGNs wi h a mo e de ailed desc ip ion in [P´e ez2010]. They analyze di e en me hods o iden i y a Bayesian ne wo k s uc u e and a se o pa ame e s such ha he esul an CGN pe o ms well in he classi- ica ion ask. In [P´e ez2010] he au ho s p opose o es ima e he pa ame e s di ec ly om he sample mean and sample co a iance ma ix in he da a, ha is, using maximum likelihood. I is well known [Bun ine1996] ha ollowing his s a egy can lead o model o e i ing when da a is sca ce. In bioin o ma ics, models a e sough in domains whe e he numbe o da a i ems is small and he numbe o a iables is la ge, such as classi ica ion o mass spec og ams o mic oa ays. To y o a oid o e i ing, we in oduce classi ie s based on Gaussian Join T ees (GJT) ha ins ead o es ima ing by maximum likelihood pe o m exac Bayesian a e aging o e he pa ame e s. CHAPTER 1. INTRODUCTION 7 1.3 S uc u e o he hesis We s a by sho ly e iewing in he heo y o P obabilis ic G aphical Models and condi ional Gaussian ne wo ks and in oducing Gaussian Join ee clas- si ie s in chap e 2. Nex we ge in o he lea ning p oblem. In chap e 3 we e iew he Maximum likelihood and he bayesian model a e aging me hods. Also we e iew he heo y oh Hype Ma ko dis ibu ion o e decomposable g aphs. Chap e 4 is used o explain he lea ning p ocess o e condi ional Gaus- sian Ne wo ks using maximum likelihood. Following, in chap e 5 we explain he p ocess o lea n Gaussian join ee classi ie s using Bayesian model a e - aging and also in oduce he Hype No mal In e se Wisha dis ibu ion. In chap e 6 we pe o m a compa ison be ween models lea ned using max- imum likelihood and Bayesian model A e aging. The compa ison is based in classi ying mass spec ome y da a om cance pa ien s. Finally in chap e 7 we gi e he inal conclusions o he wo k. 1.4 Con ibu ions The con ibu ions o he wo k a e: 1. The p oposal o GJT classi ie s including a p oo ha he HN IW law is s ong hype Ma ko , 2. A p elimina y empi ical compa ison wi h classi ie s adjus ing pa ame- e s by maximum likelihood o he ask o mass spec a classi ica ion and, 3. An open sou ce implemen a ion o he algo i hms, made a ailable o easy ep oducibili y o he esul s. Chap e 2 P obabilis ic G aphical models A p obabilis ic g aphical model is a ep esen a ion o a join p obabili y dis- ibu ion o e a se o a iables. I has wo main pa s, one is he s uc u e, i.e., he se o condi ional dependences be ween he which is ep esen ed by a g aph, and he o he is he condi ional dis ibu ions o e he a iables in which he join dis ibu ion ac o ises. This chap e in oduces basic concep s in p obabilis ic g aphical models. We s a by e iewing some necessa y concep s on g aph heo y. Nex in sec ion 2.2 we ake a look on Bayesian ne wo ks and Ma ko ne wo ks and e iew impo an esul s on he equi alence o Bayesian and Ma ko ne - wo ks.In he same sec ion, we e iew Ma ko dis ibu ions o e decompos- able g aphs heo y. Following, we e iew he concep o condi ional Gaussian ne wo ks in oduced by [Bø che 2004] and see how apply hem o classi i- ca ion. Finally we in oduce Gaussian Join T ee classi ie s, an adap a ion o condi ional Gaussian ne wo ks o Ma ko ne wo ks which ake ad an age o he Ma ko dis ibu ions heo y. 2.1 G aph heo y G aph heo y is an accep ed o malism o ep esen a ion o p obabilis ic g aphical models. In his sec ion we in oduce he basic de ini ions and no a ions ha will be used. Mos o he de ini ions o his sec ion ha e been adap ed om [Kolle and F iedman2009]. We s a by in oducing a gene al de ini ion o g aph. De ini ion 1. Ag aph is a pai G= (X, E) whe e Xis a non-emp y ini e se o e ices and Eis a se o pai s o nodes o Xcalled edges. We call an edge e= (xi, xj)∈E o xi, xj∈Xadi ec ed edge i (xi, xj)6= (xj, xi), o he wise we said ha eis an undi ec ed edge. I all he edges o a g aph 8 CHAPTER 2. PROBABILISTIC GRAPHICAL MODELS 9 x1 x2 x3 x4 Figu e 2.1: Example o a di ec ed g aph. x1 x2 x3 x4 x5 x6 x7 x8 Figu e 2.2: Example o an undi ec ed g aph. Ga e di ec ed, we call Gadi ec ed g aph, on he o he hand i all o he edges o g aph a e undi ec ed we call i an undi ec ed g aph. A g aph is a comple e g aph i o any o de ed pai , xi, xj∈X he e is an edge e= (xi, xj)∈E. The gene al ag eemen is o ep esen a g aph using a ows and lines ha connec nodes ep esen ed by di e en elemen s, usually a ci cle o a poin . A ows ep esen s di ec edges and lines undi ec ed edges. An example o a di ec ed g aph is shown in igu e 2.1, and an example o an undi ec ed g aph is shown in igu e 2.1. An impo an concep when we wo k wi h di ec ed g aphs is he one o pa en and child. De ini ion 2. Gi en a g aph G= (X, E) and an edge e= (xi, xj) we say ha xiand xja e adjacen nodes. I eis di ec ed we say ha xiis a pa en o xjand xjis a child o xi. I eis undi ec ed and xiand xja e connec ed by an edge hen xiand xja e neighbou s. CHAPTER 2. PROBABILISTIC GRAPHICAL MODELS 16 Tiand Tjis he se o a iables Sij =Ti∩Tj. A join ee Tis a clique ee such ha o e e y pai o nodes Ti, Tj,Ti∩Tjis a subse o e e y sepa a o on he unique pa h om Ti o Tj. A Gaussian join ee classi ie is a mixed ne wo k o med by a disc e e a iable co esponding o he class,which is he pa en o all o he a iables. And a se o con inuous a iables ha o med a Ma ko ne wo k wi h a s uc u e o a join ee. The selec ion o he join ee s uc u e o he con inuous a iables allows us o use he decomposi ion explained in sec ion 2.2.4. The ac o iza ion o he p obabili y P(C|X), whe e Cis he class and X he p edic i e a iables is easily done. Then he p obabili y can be calcula ed as in equa ion 2.3, whe e he P(X|C) is ac o ized as in 2.1. Chap e 3 Lea ning P obabilis ic G aphical Models In his chap e we ake a look o he p oblem o lea ning a model om da a. The lea ning p oblem can be di ided in wo pa s, s uc u al lea ning and pa ame e lea ning. S uc u e lea ning consis in in e ing om da a he condi ional dependencies be ween he di e en a iables o he model. Pa ame e lea ning consis in, once gi en a ac o iza ion o he model, lea n he pa ame e s o he di e en dis ibu ions o he ac o iza ion. F om now on, we will ocus on pa ame e lea ning. We can di ide he lea ning algo i hms in wo big amilies, equen is and bayesian lea ning algo i hms. We will conside wo di e en algo i hms: maximum likelihood, which is a equen is app oach and Bayesian model a e aging, which is a Bayesian app oach. In his chap e we will s a by e iewing gene al maximum likelihood in sec ion 3.1. In sec ion 3.2 we e iew Bayesian model a e aging and sho ly e iew he necessa y heo y o pe o m i o e decomposable g aphs. 3.1 Maximum likelihood Maximum likelihood is one o he mos used app oaches o lea n he pa am- e e s o a p obabili y dis ibu ion. E en hough i is one o he mos used s a egies i also p esen s some oubles like model o e i ing. I we conside a model wi h a se o pa ame e s Λ and a da ase Do in- s ances. Maximum likelihood app oach es ima es he alue o he pa ame e s by using hose which maximize he likelihood. P(D|Λ) 17 CHAPTER 3. LEARNING PGM 18 The s a egy o maximizing he likelihood, as we ha e said be o e can o e i he model, specially when he da a is sca ce. Fo example imagine ha we a e modelling he oss o a ai coin, and all ou da a consis in h ee consecu i e lips in which we ha e ob ained h ee heads. Then he maximum likelihood me hod in e s ha he p obabili y o h owing he coin and ob ain head is 1. Which is comple ely alse and he wo s possible app oxima ion o he eal model. In o de o ob ain be e model, and sol e he p oblem o model o e i ing we in oduce in he nex sec ion he Bayesian model a e aging me hod. 3.2 Bayesian model a e aging Bayesian model a e aging ies o o e come he p oblem o model o e i - ing h ough conside ing a p io dis ibu ion o e he space o pa ame e s [Bishop2006]. This p io ep esen s how p obably we hink a ce ain pa am- e e is. The Bayes heo em gi es us a way o lea n a pos e io dis ibu ion o he pa ame e s om da a. Bayes heo em is one o he mos impo an esul s o he p obabili y heo y. The main esul is o calcula e he p obabili y o an e en Agi en he e en Bby u ning a ound he condi ion. P(A|B) = P(A)P(B|A) P(B). I we hink in A as he pa ame e s o he model and B he da a we ha e he nex esul : P(Λ|D)∝P(D|Λ)P(Λ). which means ha he pos e io dis ibu ion is p opo ional o he p oduc o he likelihood o he da a and he p io dis ibu ion. When doing in e ence using a Bayesian model a e aging me hod, we ha e o in eg a e o e he whole space o pa ame e s. This in eg a ion is no always possible and is equi ed o use a sampling me hod such as Ma ko Chain Mon e Ca lo me hods. One usual p oblem wi h his app oach is ha mos o he ime he mos impo an ac o when choosing a p io dis ibu ion is hei ma hema ical con enience a he han he in o ma ion hey ake. CHAPTER 3. LEARNING PGM 19 3.2.1 Hype Ma ko dis ibu ions o e decomposable g aphs We ha e seen in Sec ion 2.2.4 ha a p obabili y dis ibu ion can be easily ac o ized in e m o he cliques and sepa a o s i he associa ed g aph is de- composable. In o de o pe o m Bayesian model a e aging o e his models we need o in oduce hype Ma ko dis ibu ions. In his sec ion we su icien ly e iew he undamen al esul s in [Dawid and Lau i zen1993]. The in e es ed eade can ind some o he missing de ini ions and addi ional de ails in [Dawid and Lau i zen1993]. Le θbe a quan i y pa ame ising a g aphical model M(G). A hype Ma ko law is hen de ined by a p ope y which mimics he global Ma ko p ope y, a he pa ame e le el De ini ion 15. A law on M(G) is called (weak) hype Ma ko o e Gi o any decomposi ion (A, B) o G θA⊥⊥ θB|θA∩B De ini ion 16. A law on M(G) is called s ong hype Ma ko o e Gi o any decomposi ion (A, B) o G θB|A⊥⊥ θA S ong hype Ma ko laws p oduce an especially simple decomposi ion o he Bayesian analysis in o a collec ion o sub-analyses o smalle p oblems. Thus, he pos e io a e obse ing some da a can be assessed locally. The ollowing wo p oposi ions om [Dawid and Lau i zen1993] will be needed la e . They gi e su icien condi ions o p o e ha a gi en p obabili y law is s ong hype Ma ko . P oposi ion 3. Gi en a se o hype consis en laws {MC}o e clique ma ginals, he e is a unique hype Ma ko law o e Gsa is ying hose ma ginals, which is called he hype Ma ko combina ion o {MC}. P oposi ion 4. Le P ⊆ M(G)be a sub amily o he Ma ko models o e G. Assume ha Pis weak me a Ma ko , and o any comple e se Sin G he model PS o m a ull exponen ial amily. Le Lbe a hype Ma ko law such ha , o any clique C, he law o θCis a conjuga e p io dis ibu ion o he model PC. Then Lis s ong hype Ma ko . Chap e 4 Lea ning CGN by ML We ha e al eady alk abou lea ning in Chap e 3, he e we ocus on lea n- ing condi ional Gaussian ne wo ks using maximum likelihood. We s a by e iewing mul inomial and Gaussian dis ibu ion, how o lea n hei pa am- e e s and how o calcula e hei condi ional dis ibu ion. Finally we pu e e y hing oge he and ge in o how o lea n condi ional Gaussian Ne wo ks 4.1 The mul inomial dis ibu ion The mul inomial dis ibu ion is a p obabili y dis ibu ion o e disc e e p ob- abili ies ha can ake wo o mo e di e en alues. I only has an a ay o pa ame e s whe e each pa ame e is he p obabili y ha he a iable ake. The a ay o pa ame e s c= (c1, . . . , cK) ull ill he ollowing p ope ies. ci>0 p(x=k|c=ck= 1 4.1.1 Pa ame e lea ning Pa ame e o he mul inomial dis ibu ion a e easily lea ned by maximum likelihood. The alue o each pa ame e ciis jus p opo ion o imes ha he a iable akes he i- h alue in he da a. In o he wo ds i miis he numbe o imes ha he a iable akes he alue iin he da a, and he da a has nins ances, hen ci=mi n. 20 CHAPTER 4. LEARNING CGN BY ML 21 4.2 The no mal dis ibu ion The no mal dis ibu ion, also known as Gaussian dis ibu ion, is de ined on Rk. I has wo pa ame e s: he mean µwhich is a eal- alued ec o , and he co a iance ma ix Σ wich is a posi i e de ini e k×kma ix. In he li e a u e he co a iance ma ix can be subs i u ed by i s in e se, he p ecission ma ix. The p obabili y densi y unc ion is N(X|µ, Σ) = 1 (2π)k /2|Σ|1 /2exp 1 2(x−µ)TΣ−1(x−µ) 4.2.1 Pa ame e lea ning Pa eme e s o no mal dis ibu ion can be lea ned om da a by di e en ap- p oaches. The mos common one is o use maximum likelihood es ima ions. Gi en a da ase D{xi}n i=1 wi h xi∈Rk he maximum likelihood es ima o o he mean ec o is ¯x=1 n n X i=1 xi.(4.1) The es ima ion o Scan be calcula ed as S="1 n n X l=0 (xi l−¯xi)(xj l−¯xj)#0<i,j≤k ,(4.2) whe e xiis he i h en y o he ec o x. Ins ead o using maximum likelihood s a egies o lea ning pa ame e s we could use maximum a pos e io i lea ning me hods. Fo his we ha e o de ine a p io dis ibu ion o e he space o pa ame e s o he dis ibu ion. In nex sec ion we in oduce No mal In e se Wisha , as a p io o he no mal dis ibu ion. 4.2.2 Cond ional Gaussian dis ibu ion Gi en a mul idimensional a iable z= (z1, . . . , zk) which ollows a no mal dis ibu ion wi h pa ame e s µand Σ we can calcula e he condi ional dis- ibu ion o a subse o his,say x a iables gi en he o he , y. Wi hou loss o gene ali y we can hink ha xa e he i s l a iables, wi h lsmalle han k. We ha e he ollowing decomposi ion o he pa ame e s: µ= (µx, µy) Σ = ΣxΣxy Σyx Σy CHAPTER 4. LEARNING CGN BY ML 22 Then we can calcula e he condi ional dis ibu ion o P(zx|zy) which is also a Gaussian dis ibu ion wi h pa ame e s µx|y=µx+ Σx,yΣ−1 y(zy−µy), Σx|y= Σx−ΣxyΣ−1 yy Σyx. 4.3 Lea ning condi ional Gaussian Ne wo ks Now we ha e seen how can we lea n he di e en dis ibu ions sepa a ely, now we ocus on how o lea n all he pa ame e s o a condi ional Gaussian Ne wo k. Algo i hm 1 explains how o lea n he pa ame e s o he ne wo k om a da ase D. Basically i can be spli in wo pa s, he i s one is o de e mine he p obabili y o each class, he second o lea n, o each class a di e en dis ibu ion o each a iable. Algo i hm 1 Maximum Likelihood lea ning o CGN pa ame e s unc ion Lea nCGNPa ame e s(X,D) o each class cdo Se P(C=c) as he p opo ion o ins ances o class cin D o each node Xi∈ X do Calcula e he mean and he co a iance p obabili y o he join dis ibu ion o Xiand hei p edic o pa en s, acco ding o equa ion 4.1 and 4.2. Calcula e he condi ional Gaussian dis ibu ion o Xgi en hei pa en s as explained in Sec ion 4.2.2. end o end o end unc ion O he possible s a egies o lea n pa ame e s a e possible. We will o- cus in he compa ison be ween Bayesian Model A e aging and Maximum Likelihood. In he ollowing chap e s we will gi e he su icien ools o use Bayesian Model A e aging o e decomposable g aphs. Chap e 5 Lea ning Gaussian Join T ee classi ie s by BMA In he p e ious chap e we ha e ocus on lea ning a condi ional Gaussian ne wo k using a Maximum likelihood. As we ha e commen ed be o e, his model can lead o model o e i ing, specially when da a is sca ce. This p oblem can be sol ed by Bayesian lea ning echniques. In his chap e we ocus on he use o Bayesian Model A e aging o lea n he pa ame e s o a Gaussian Join T ee dis ibu ion. We s a by e iewing he Di ichle p io o he mul inomial and in oducing he Hype In e se Wisha Dis ibu ion. Finally we gi e he algo i hms o lea n he pa ame e s o a Gaussian Join T ee classi ie . 5.1 Di ichle dis ibu ion Di ichle dis ibu ion is a conjuga e p io o he mul inomial dis ibu ion [Bishop2006].The Di ichle dis ibu ion is de ined as ollows. P(c|α) = Γ(K k=1αk) QK k=1 K Y k=1 cαk−1 k Whe e kis he dimension o he dis ibu ion, ck>0, PK k=1 ck= 1, and Γ(x) is he Gamma unc ion. The pa ame e αimus be an in ege , and i ep esen s how many imes he class ihas been saw in he p io . So, i acco ding o ou belie one class is mo e p obable i should ansla e in a la ge alue o i s co esponding αpa ame e s in he p io . 23 CHAPTER 5. LEARNING GJTC BY BMA 24 5.1.1 Conjugancy Since he Di ichle dis ibu ion is conjuga e o he mul inomial dis ibu ion we can lea n he pos e io dis ibu ion by upda ing he pa ame e s o he p io . Gi en a da ase D, he pa ame e s α0o he pos e io dis ibu ion a e upda ed by adding he coun s o each class, i.e., le nibe he numbe o ins ances in Dco esponding o he class i hen α0 i=αi+ni. 5.1.2 P edic i e pos e io dis ibu ion In e ence when using he Di ichle dis ibu ion as a p io o he mul inomial dis ibu ion can be calcula ed exac ly. The pos e io p edic i e dis ibu ion is ob ained by in eg a ing ou he pa ame e ci. P(X|α0)Zc MN(X|c)D(c|α0)∝α0 Then, he p obabili y o a gi en class is he p opo ion o he class in he da a, and in he p io . In o he wo ds, he p edic i e pos e io dis ibu ion is ano he mul inomial dis ibu ion wi h pa ame e s α0 PK i=1 α0 i . 5.2 Hype in e se Wisha dis ibu ion Now we e u n o Hype ma ko heo y, and in oduce he hype in e se Wisha dis ibu ion in o de o in oduce la e he Hype no mal in e se Wisha dis ibu ion, which will be used as a p io o he Gaussian dis i- bu ion o e a decomposable g aph. Le Gbe a decomposable g aph o e a se o con inuous a iables. We a e in e es ed in he sub amily o models which a e in M(G) and which a e assumed o be join ly mul i a ia e no mal wi h mean equal o ze o and unknown posi i e de ini e co a iance ma ix Σ, ha is x∼ N (0,Σ). Fo his pa icula amily, i is possible o de ine a s ong hype Ma ko dis ibu ion. I was in oduced in [Dawid and Lau i zen1993], unde he name o hype in e se Wisha dis ibu ion De ini ion 17. Le ΦC={ΦC, C ∈ C} be a collec ion o posi i e de ini e dispe sion ma ices, whe e ΦCis he dispe sion ma ix o e he a iables in clique C. Assume ha he ma ices a e consis en , ha is, o each B⊆ CHAPTER 5. LEARNING GJTC BY BMA 25 C1∩C2, he sub-ma ices1ΦC1[B, B] and ΦC2[B, B] a e iden ical. Le δbe a posi i e eal numbe . We can de ine a collec ion o hype consis en Ma ko laws by de ining o e each ma ix ΣC he ollowing law: L(ΣC) = IW(δ; ΦC). The law ha esul s om he hype Ma ko combina ion o his collec ion o laws is called hype in e se Wisha and no ed HIW(δ, ΦC). The HIW is p o ed s ong hype Ma ko in [Dawid and Lau i zen1993]. 5.3 Hype no mal in e se Wisha dis ibu- ion HIW laws can only be used when he mul i a ia e mean is known o be 0. We a e in e es ed in he mo e gene al sub amily o models in M(G) wi h any possible mean, ha is x∼ N(µ,Σ). We in oduce he hype no mal in e se Wisha dis ibu ion and p o e ha i is s ong hype Ma ko . De ini ion 18. Le ΦC={ΦC, C ∈ C} be a collec ion o ma ices as in de ini ion 17. Le µC={µC, C ∈ C} be a collec ion o ec o s such ha o each B⊆C1∩C2,µC1[B] = µC2[B]. Le κand δbe non-nega i e eal numbe s. Since he ma ginal o a no mal in e se Wisha depends only on he co esponding sub- ec o and sub-ma ix (see sec ion A.2.3), he collec ion o laws L(ΣC) = NIW(µC, κ, δ, ΦC) is hype consis en . The hype Ma ko combina ion o i s elemen s is called hype no mal in e se Wisha and no ed HNIW(µC, κ, δ, ΦC).By p oposi- ion 3 he HN IW law is hype Ma ko . Theo em 2. The HN IW dis ibu ion is s ong hype Ma ko . P oo . Is a di ec applica ion o p oposi ion 4. Fi s , no e ha in ou case, he se o models is he se o mul idimensional Gaussian models ha ac o ize o e G. Thus, i is weak me a Ma ko and o e a comple e se , i o ms a ull exponen ial amily. Since he HNIW law is hype Ma ko , and o any clique C, i is a conjuga e dis ibu ion o he mul idimensional Gaussian o e C, by p oposi ion 4 i is s ong hype Ma ko . 1Gi en a ma ix Mand se s o indexes I,J, we no e M[I, J] he sub-ma ix ha keeps he ows wi h indexes in Iand he columns wi h indexes in J. Equi alen no a ion is used o ec o s. CHAPTER 6. EMPIRICAL COMPARISON 32 Lea ning Me hod Maximum Likelihood Maximum a Pos e io i S uc u e K-BOX CGN-K-BOX GJT-K-BOX Model K-BAND CGN-K-BAND GJT-K-BOX Table 6.1: Summa y o combina ion o me hods and s uc u es. case o he Gaussian we choose a No mal In e se Wisha p io dis ibu ion which uses he ollowing pa ame e s. η= 0, δ=κ= 1 and Ψ equal o he iden i y ma ix, wha includes a belie on he independence o he a iables. 6.5 The expe imen We ha e pe o med di e en compa isons o each da ase . We ha e used 4 di e en classi ie me hods. Each classi ie me hod is he combina ion o a s uc u e and a lea ning p inciple. The di e en combina ions a e shown in able 6.5. Fo cance da ase s he me hods ha e been un wi h di e en alue o K. Fo o a ian cance da ase K akes alues om 1 o 50, and o panc ea ic cance da ase he me hods ha e been un wi h alues o K om 1 o 30. A 10-c oss old alida ion has been pe o med o each me hod. In o he wo ds, he da ase ha e been di ided in 10 di e en subse s. We ha e clas- si ied each o his subse s while he model has been lea n wi h he o he 9 subse s. 6.5.1 Measu es Two measu es ha e been used o compa e he pe o mance o he classi- ie s. The accu acy is he p opo ion o co ec ed classi ied pa ien s. We can unde s and accu acy as a measu e o how well we classi y. Accu acy = co ec ed classi ied ins ances ins ances We also use condi ional log-likelihood (CLL), which is he log-p obabili y assigned o he co ec class o he ins ances.CLL measu es how accu a ely he p obabili ies o each class a e es ima ed, which is e y ele an o ade- qua e decision making. I ciis he class associa ed o an ins ances xi, he cll is de ined as CHAPTER 6. EMPIRICAL COMPARISON 33 CLL = m X i=0 log(P(C=ci|xi)) 6.6 Resul s We ha e un a sequence o expe imen s on each da ase o compa e he di e en s uc u es (k-BOX and k-BAND) and pa ame e lea ning me hods (CGN and GJT) a ying he kpa ame e . The sou ce code used o pe o m he expe imen s is a ailable a h p: //www.iiia.csic.es/~ce quide/pype ma ko 6.6.1 O a ian da a The o a ian da a has been modelled using k-BOX and k-BAND s uc u es wi h k anging om 1 o 50. In Figu e 6.5 we show he mean accu acy e sus he numbe o pa ame e s in he model and in Figu e 6.6 we show he mean CLL e sus he numbe o pa ame e s in each s uc u e. We see ha in ha da ase , k-BAND models a e mo e accu a e ha k-BOX models. Fo low alues o k, CGN pe o ms be e han GJT, bu GJT has a la ges accu acy and a highes CLL a i s peak, and shows a mo e g ace ul decay as he numbe o pa ame e s g ows beyond ha peak. 6.6.2 Panc ea ic da a The panc ea ic cance da a has been classi ied using k-BOX and k-BAND s uc u es wi h k anging om 1 o 30. Figu e 6.7 and Figu e 6.8 show espec i ely he mean accu acy and mean CLL agains he numbe o pa- ame e s. No e ha he accu acy o his da ase is much lowe and close o he equency o he la ges class, ha is 55.8% in his da ase s. P e ious s udies ha e shown ha he accu acy esul s o his da ase a e much lowe han o he p e ious one. The k-BOX model using GJT appea s o each he highes accu acy and he k-BAND model eaches he highes CLL also o panc ea ic cance . CHAPTER 6. EMPIRICAL COMPARISON 34 Figu e 6.5: P edic ion o o a ian cance . Accu acy e sus numbe o pa am- e e s in model. 0 200000 400000 600000 800000 1000000 1200000 Numbe o pa ame e s in he model 1600 1400 1200 1000 800 600 400 200 Condi ional log likelihood CGN-K-BOX GJT-K-BOX CGN-K-BAND GJT-K-BAND Figu e 6.6: P edic ion o o a ian cance . CLL e sus numbe o pa ame e s in model. CHAPTER 6. EMPIRICAL COMPARISON 35 0 50000 100000 150000 200000 250000 300000 350000 400000 Numbe o pa ame e s in he model 0.48 0.49 0.50 0.51 0.52 0.53 0.54 0.55 0.56 0.57 Accu acy CGN-K-BOX GJT-K-BOX CGN-K-BAND GJT-K-BAND Baseline p obabili y Figu e 6.7: P edic ion o panc ea ic cance . Accu acy e sus numbe o pa ame e s in model. 0 50000 100000 150000 200000 250000 300000 350000 400000 Numbe o a iables in he model 10000 9000 8000 7000 6000 5000 4000 3000 2000 Condi ional log likelihood CGN-K-BOX GJT-K-BOX CGN-K-BAND GJT-K-BAND Figu e 6.8: P edic ion o panc ea ic cance . CLL e sus numbe o pa ame- e s in model. Chap e 7 Conclusions and Fu u e Wo k We ha e in oduced a new amily o classi ie s o con inuous domains, namely Gaussian join T ee classi ie s ha pe o m exac Bayesian a e aging o e he pa ame e s by i ue o he hype no mal in e se Wisha law, ha we ha e in oduced and p o ed o be s ong hype Ma ko . To assess he bene i s we ha e compa ed GJT classi ie s wi h GCN classi ie s which assuming he same se o independences adjus pa ame e s using maximum likelihood. We pe - o med ou compa ison wi h wo high esolu ion mass spec ome y da ase s o o a ian and panc ea ic cance p edic ion. We ha e seen ha , o wo simple dependency s uc u es, ou classi ie s each a be e peak accu acy and a consis en ly be e condi ional log likelihood. We ha e in oduced k-BOX and k-BAND s uc u e, which a e pa o he same amily o join ees s uc u es. Fo example di e en sizes o he sepa a o s de ine di e en models in he amily. The s udy o his amily emains also as u u e wo k. The GJT pa ame e a e aging can be pe o med o e any se o depen- dencies ha can be encoded in o a decomposable g aph. We can adap any algo i hm o lea ning he s uc u e o a CGN classi ie so ha i ou pu s a join ee by mo alizing and iangula ing he DAG ha encodes he s uc u e o he CGN, and hen unning maximum ca dinali y sea ch. A u u e line o wo k is compa ing along he da ase s in [P´e ez2010] using he same s uc u e lea ning algo i hms ha hey sugges , hus es ing i he bene i s ex end o domains wi h a smalle numbe o a ibu es. Finding a s uc u e lea ning me hod o la ge Bayesian ne wo ks emains as u u e wo k. Mo e in o med dependencies s uc u es should imply be e esul s in mass spec a classi ica ion. 36 Bibliog aphy [Bishop2006] C.M. Bishop. 2006. Pa e n ecogni ion and machine lea ning. Sp inge New Yo k. [Bø che 2004] Susanne Gammelgaa d Bø che . 2004. Lea ning Bayesian Ne wo ks wi h Mixed Va iables. Ph.D. hesis, Aalbo g Uni e si y. [Bun ine1996] W ay Bun ine. 1996. A Guide o he Li e a u e on Lea ning P obabilis ic Ne wo ks om Da a. IEEE TRANSACTIONS ON KNOWL- EDGE AND DATA ENGINEERING, 8(2):195–209. [Cowell e al.1999] Robe G. Cowell, A. Philip Dawid, S e en L. Lau i zen, and Da id J. Spiegelhal e . 1999. P obabilis ic Ne wo ks and Expe Sys- ems. Sp inge -Ve lag. [Dawid and Lau i zen1993] A. P. Dawid and S. L. Lau i zen. 1993. Hype Ma ko Laws in he S a is ical Analysis o Decomposable. The Annals o S a is ics, 21(3):1272–1317. [Elo and Schwikowski2011] Lau a L. Elo and Benno Schwikowski. 2011. Min- ing p o eomic da a o biomedical esea ch. Wiley In e disciplina y Re- iews: Da a Mining and Knowledge Disco e y, 2(Feb ua y):n/a–n/a, Au- gus . [Geige and Hecke man1994] Dan Geige and Da id Hecke man. 1994. Lea ning gaussian ne wo ks. In P oceedings o he Ten h Annual Con- e ence on Unce ain y in A i icial In elligence (UAI-94), pages 235–243. [Gelman e al.2004] And ew Gelman, JB Ca lin, HS S e n, and Rubin. 2004. Bayesian da a analysis. [III e al.2002] Emanuel F Pe icoin III, Ali M A dekani, Ben A Hi , Pe e J Le ine, Vincen A Fusa o, Se h M S einbe g, Go don B Mills, Cha les Simone, Da id A Fishman, Elise C Kohn, and Lance A Lio a. 2002. Use o p o eomic pa e ns in se um o iden i y o a ian cance . The Lance , 359(9306):572 – 577. 37 BIBLIOGRAPHY 38 [Kolle and F iedman2009] D. Kolle and N. F iedman. 2009. P obabilis ic g aphical models: p inciples and echniques. The MIT P ess. [Ko z and Nada ajah2004] Samuel Ko z and Sa alees Nada ajah. 2004. Mul- i a ia e T-Dis ibu ions and Thei Applica ions. Camb idge Uni e si y P ess, Camb idge. [La a˜naga e al.2006] Ped o La a˜naga, P, A i z P´e ez, I˜naki Inza, and Pe- d o La a. 2006. Supe ised classi ica ion wi h condi ional Gaussian ne - wo ks : Inc easing he s uc u e complexi y om nai e Bayes. In e na- ional Jou nal o App oxima e Reasoning, 43(Janua y):1–25. [Lau i zen1996] S e en L. Lau i zen. 1996. G aphical models. Ox o d Uni- e si y P ess. [P´e ez2010] A i z P´e ez. 2010. Supe ised classi ica ion in con inuous do- mains wi h Bayesian ne wo ks. Ph.D. hesis, Uni e sidad del Pais Vasco. Appendix A Dis ibu ions A.1 Mul i a ia e -dis ibu ions Ap-dimensional andom ec o xis said o ha e he p- a ia e dis ibu ion wi h deg ees o eedom ν, mean ec o µ, and co ela ion ma ix R( ha is x∼ ν(µ, R)) i i s join pd is gi en by p(x|ν, µ, R) = Γ((ν+p)/2) (πν)p/2Γ(ν/2)|R|1/2· ·[1 + 1 ν(x−µ)R−1(x−µ)]−(ν+p)/2(A.1) A.1.1 Ma ginals Le xbe a p-dimensional andom ec o x∼ ν(µ, R). Fu he mo e le x= (x1,x2) whe e x1is p1dimensional, µ= (µ1,µ2) and R=R11 R12 R21 R22 . We ha e ha x1∼ ν(µ1, R11) (A.2) Fo mo e in o ma ion ega ding mul i a ia e -dis ibu ions see [Ko z and Nada ajah2004]. A.2 No mal In e se Wisha dis ibu ions The in e se Wisha dis ibu ion is de ined on eal- alued posi i e-de ini e p×pma ices. I has wo pa ame e s: a eal numbe δ > 0 and a p×p 39 APPENDIX A. DISTRIBUTIONS 40 posi i e-de ini e ma ix Ψ. The p obabili y densi y unc ion is IW(X|δ, Ψ) = |Ψ|δ+p−1 2|X|−δ+2p 2 2(δ+p−1)p 2Γp(δ+p−1 2) e−1 2 (ΨX−1) The no mal in e se Wisha dis ibu ion is de ined on pai s composed o (i) ec o s o dimension pand (ii) eal- alued posi i e-de ini e p×pma ices. I has ou pa ame e s: a pdimensional ec o η ha encodes he loca ion, a posi i e eal numbe κ ha ac s as scaling ac o , and δand Ψ as in he in e se Wisha . The p obabili y densi y unc ion is NIW(µ,Σ|η, κ, δ, Ψ) = N(µ|η,1 κΣ) · IW(Σ|δ, Ψ) A.2.1 Conjugacy The no mal in e se Wisha dis ibu ion is conjuga e o he mul i a ia e no - mal [Gelman e al.2004]. Thus, i we assume as p io a NIW(µ,Σ|η, κ, δ, Ψ) and we a e gi en a sample X om a mul i a ia e no mal, he pos e io will be a NIW(µ,Σ|η0, κ0, δ0,Ψ0) whe e η0=κη+nx κ+n,(A.3) κ0=κ+n, (A.4) δ0=δ+n, (A.5) Ψ0= Ψ + (n−1)S+κn κ+n(x−η)(x−η)T.(A.6) and Sis he sample co a iance. A.2.2 P edic i e dis ibu ion The p edic i e dis ibu ion is he esul o in eg a e o e he space o pa am- e e he p oduc o he no mal dis ibu ion and he No mal In e se Wisha . This ope a ion, gi e as esul a mul i a ia e dis ibu ion depending on he hype pa ame e s o he model. p(x|η, κ, δ, Ψ) = =Zµ,Σ N(x|µ,Σ)NIW(µ,Σ|η, κ, δ, Ψ) = = δ(η,κ+ 1 κδ Ψ).(A.7) APPENDIX A. DISTRIBUTIONS 41 A.2.3 Ma ginals The nex p oposi ion gi e us he ma ginals o he No mal In e se Wisha . This esul will be necessa y la e , when we alk abou hype Ma ko dis i- bu ions. P oposi ion 5. Le µ=µ1 µ2,Σ = Σ11 Σ12 Σ21 Σ22 ,η=η1 η2and Ψ = Ψ11 Ψ12 Ψ21 Ψ22 . I (µ,Σ) ∼ NIW(η, κ, ν, Ψ), hen (µ1,Σ11)∼ NIW(η1, κ, ν, Ψ11) P oo . The ma ginal can be assessed as ollows P(µ1,Σ11|η, κ, δ, Ψ) = =Zµ2,Σ12,Σ22 NIW(µ,Σ|η, κ, δ, Ψ) = =Zµ2,Σ12,Σ22 N(µ|η,1 κΣ) · IW(Σ|δ, Ψ) = =Zµ2,Σ12,Σ22 N(µ1|η1,1 κΣ11)P(µ2|µ1,η, κ, δ, Ψ)· · IW(Σ11|δ, Ψ11)P(Σ22,Σ21|Σ11, δ, Ψ) = =N(µ1|η1,1 κΣ11)IW(Σ11|δ, Ψ11)· ·Zµ2,Σ12,Σ22 P(µ2|µ1,η, κ, δ, Ψ)P(Σ22,Σ21|Σ11δ, Ψ) = =N(µ1|η1,1 κΣ11)IW(Σ11|δ, Ψ11) (A.8)