CMU高级机器学习非参数贝叶斯模型

1、Advanced Machine Learning Nonparametric Bayesian Models 一Learning/Reasoning in Open Possible Worlds Learning/Reasoning Eric Xing Lecture 17, August 14, 2009 Reading: Eric Xing © Eric Xing CMU, 2006-2009 1 Clustering Eric Xing © Eric Xing CMU, 2006-2009 2 1Image Segmentation How to segment

2、images? Manual segmentation (very expensive Algorithm segmentation K-means Statistical mixture models Spectral clustering Problems with most existing algorithms Ignore 什w spatial information Perform the segmentation one image at a time Need to specify the number of segments a priori Eric Xing ©

3、 Eric Xing CMU, 2006-2009 3 Object Recognition and Tracking (1.9, 9.0, 2.1 (1.& 7.4, 2.3 (1.9, 6.1, 2.2 (0.7, 5.1, 3.2 (0.9, 5.& 3(0.6, 5.9, 3.2 t=l Eric Xing t=2 © Eric Xing CMU, 2006-2009 t=3 4 2Modeling The Mind Latent brain processes: View picture Read sentence Decide whether consis

4、tent fMRI scan:Eric Xing . t=l © Eric Xing CMU, 20062009 t=T 5 The Evolution of Science Research circles Phy Research topics Bio CS PNAS papers 1900 Eric Xing © Eric Xing CMU, 2006-2009 2000 6?3A Classical Approach Clustering as Mixture Modeling Then Mmodel selection" Eric Xing ©

5、 Eric Xing CMU, 2006-2009 7 Partially Observed, Open and Evolving Possible Worlds Unbounded # of objects/trajectories Changing attributes Birth/death, merge/split Relational ambiguity Tlie parametric paradigm: p cpkO ( or p(p 1:T k Evunt model p (pkt +1 motion model t k ( cp E*+l|t+l t Finite Entity

6、 space Stinctxirally unambiguous E*|t t Sensor model p(x | cpk obsen*ation space How to open it up? © Eric Xing CMU, 2006-2009 8 Eric Xing 4Model Selection vs. Posterior Inference Model selection HintelligentH guess: ? cross validation: data-hungry information theoretic: AIC TIC MDL : " ar

7、g min KL f ( I g ( | 6 ML , K Parsimony, Ockam's Razor need to compute data likeliliood ( Bayes factor: Posterior inference: we want to handle uncertainty of model complexity explicitly p (M I D 00 p (D I M p (M we favor a distribution that does not constrain M in a "closed" space! M =

8、 0 , K Eric Xing © Eric Xing CMU, 2006-2009 9 Two "Recent" Developments First order probabilistic languages (FOPLs Examples: PRM. BLOG Lift giaphical models to MopenM world relation, index, lifespan Focus on complete, consistent, and operating rules to instantiate possible worlds, and

9、 formal language of expressing such rules Operational way of defining distributions over possible worlds, via sampling methods Bayesian Nonparametrics Examples: Dirichlet processes, stick-breaking processes From finite, to infinite mixture, to more complex constnictions (hierarchies, spatial/tempora

10、l sequences, Focus on the laws and behaviors of both the generative formalisms and resulting distributions Often offer explicit expression of distributions, and expose the stnjcture of the distributions motivate various approximate schemes Eric Xing © Eric Xing CMU, 2006-2009 10 5Clustering How

11、 to label them ? How many clusters ? Eric Xing © Eric Xing CMU, 2006-2009 11 Random Partition of Probability Space <p4 , tt 4 cp6，兀 6 <p5 , 7i 5 (p3 , it 3 (pl 1 (event，pe*ent centroid :=(p linage ele. :=(xQ 述 q>2，兀 2 Eric Xing © Eric Xing CMU, 2006-2009 12 6Stick-breaking Process

12、 兀 G =k 6 (0k 0k - GO k =1 k =1 co cc 0 0.6 0.4 0.5 0.8 0.4 0.3 0.24 兀k =1 k 1 Location 0.3 nk = pk H(1 - pk j =1 3k Beta(l, a Eric Xing Mass © Eric Xing CMU, 2006-2009 GO 13 Cliinese Restaurant Process 01 02 P(ci = k | c -i =11 1+a 1 2 +a 1 3+a ml i + a -1 a 1+a 1 2 +a 2 3 +a m2 i + a -1 000a2

13、+aa3 +a . ai + a-1 CRP defines an exchangeable distribution on partitions over an (infinite sequence of samples, such a distribution is formally known as 什Dirichlet Process (DP Eric Xing © Eric Xing CMU, 2006-2009 14 7Diriclilet Process(p4 <p6 <p3 <p5 (p(pl 2 a distribution A CDF, G, o

14、n possible worlds of random partitions follows a Dirichlet Process if for any measurable finite partition (cpl,<p2,(pm: (G(pl, G(cp2, G(pm Dii'iclilet( aG0(pl, , aG0(pm another distribution where GO is the base measure and a is the scale parameter Thus a DirichletProcess G defines a distribut

15、ion of distribution Eric Xing © Eric Xing CMU, 2006- 2009 15 Gi'apliical Model Representations of DP GO GO a G 0i xi N a k oo 0 yi xi N The Stick-breaking construction The CRP constmction Eric Xing © Eric Xing CMU, 2006-2009 16 8Ancestral Inference ? Ak 0k Hnl Gn Hii2 N Essentially a c

16、lustering problem, but Better recovery of the ancestors leads to better haplotyping results (because of more accurate grouping of common haplotypes True haplotypes are obtainable with high cost, but they can validate model more subjectively (as opposed to examining saliency of clustering Eric Xing M

17、any other biological/scientific utilities © Eric Xing CMU, 2006-2009 17 Example: DP-haplotypei' Clustering human populations a G K Xing et al, 2004 GO DP A 0 Hii2 Gn N infinite mixture components (for population haplotypes haplotypes Hnl Likelihood model (for individual haplotypes and genot

18、ypes genotypes Inference: Markov Chain Monte Carlo (MCMC Gibbs sampling Metropolis Hasting Eric Xing © Eric Xing CMU, 2006-2009 18 9The DP Mixture of Ancestral Haplotypes The customers around a table in CRP form a cluster associate a mixture component (i.e., a population haplotype with a table

19、sample a, 0 at each table from a base measure GO to obtain the population haplotype and nucleotide substitution frequency for that component 1 4 8 9 A.0 3 2 A50 5 A,0 6 A,0 7 A,0 A,6 . Withp(h|A, 0 andp(g|hl,h2, the CRP yields a posterior distribution on the number of population haplotypes (and on t

20、he haplotype configurations and the nucleotide substitution frequencies Eric Xing © Eric Xing CMU, 2006-2009 19 Inheritance and Observation Models Single-locus mutation model ACi > H ie e Cil C i2 for ht = a t ( 0 I PH ( ht | a t, 0 = I 1-0 I B | - 1 for ht a t lht = at with prob 0 Al A2 A3

21、Ancestral pool H il H i2 Haplotypes Noisy observation model H il,Hi2->GiPG(g|hl,h2:gt = hl,t h2,t with prob. X Gi © Eric Xing CMU, 2006-2009 Genotype Eric Xing 20 10Con vargence -of Ancwstrai InferenceDP vs. Finite Mixture via EMEHIMCMC 1ar Haplotype Inference t Odco unpng»x<«QXtin;Lta（mtMDr-eM）tafuiLnM bcpoailnsiM冷trtw&.xq u » h: *MCMC ior Haplotype inferencea StnRi*. ton Octo anting uftitoc n not «ttoo« moih k>nte(jitoIMKAMI RitHm TnniaM«nofeTrtkn am ： tonwMsd nh«ul rt4*at x