模式识别与人工智能之十

1、Pattern Recognition if it is gender, then Bernoulli distribution,20,EM estimation,Basic setting in EM,21,EM estimation,X is a set of data points: observed data is a parameter vector. EM is a method to find ML where Calculating P(X | ) directly is hard. Calculating P(X,Y|) is much simpler, where Y is

2、 “hidden” data (or “missing” data).,Recall: maximum likelihood,22,EM estimation,Latent variables or missing data,23,EM estimation,Incomplete Data,Complete Data,Missing data,Complete Data Likelihood,EM estimation,Complete Data Likelihood,EM estimation,Log likelihood,In many cases, we cannot find the

3、solution directly. An alternative is to find a sequence:,s.t.,Complete Data Likelihood,EM estimation,Define: : the probability of y : function of y, namely g(y),0,Ln(x) is strictly concave on (0, ),Complete Data Likelihood,EM estimation,We need to choose the maximum lower bound,How to choose Q(y)?,I

4、f is given, Q(y) and P(xi, y) will determine the value of l(),Step1: find Q(y) (Expectation) Step2: according to Q(y), maximize l() by adjusting (Maximization),EM estimation,Expectation Step: how to choose Q(y),According to the Jensen inequality, when g(y) is a constant, the lower bound is maximum.,

5、We know that ( is the probability of y, so,It is easily obtained:,EM estimation,Expectation Step: how to choose Q(y),EM estimation,Maximization Step: maximize l() by adjusting ,EM algorithm is an iterative procedure for maximizing . Assume that after the Iteration the current estimation for is given

6、 by . Since the objective is to maximize , we wish to compute an update estimate such that： Equivalently, we want to maximize the difference,EM estimation,How to guarantee the likelihood function L() is increased at each step?,Denote the hidden random vector by , the total probability is,EM estimati

7、on,How to guarantee the likelihood function L() is increased at each step?,EM estimation,How to guarantee the likelihood function L() is increased at each step?,EM estimation,Our objective is to choose a value of so that is maximized.,Gaussian Mixture Model,35,Single Gaussian,Solution: MLE by maximi

8、zing,Gaussian Mixture Model,36,Multiple Gaussians,Which component does each point belong to? Solution: ?,EM for GMM,37,The aim is to estimate the unknown parameters representing between the Gaussians and the means and covariances of each:,let x=(x1,x2,xn) be a sample of n independent observations fr

9、om a mixture of multiple normal distributions of dimension d, and let z=(z1,z2,zn) be the latent variables that determine the component from which the observation originates.,where,with,EM for GMM,38,The incomplete-data likelihood function is:,The complete-data likelihood function is:,where is an in

10、dicator function and f is the probability density function of a multivariate normal.,EM for GMM,39,This may be rewritten in log likelihood function form:,E-step:,EM for GMM,40,M-step:,Using MLE to find solution of,EM for GMM,41,M-step:,Eg:,SMM:,GMM:,EM for GMM,42,M-step:,Eg:,SMM,GMM,EM for GMM,43,M-

11、step:,Eg:,S.t.,Difference between K-means and EM,44,K-means,Classifier (K-Means),Classification Results x1C(x1) x2C(x2) xiC(xi) ,Cluster Parameters m1 for C1 m2 for C2 mk for Ck,Difference between K-means and EM,45,K-means,x1=r1, g1, b1 x2=r2, g2, b2 xi=ri, gi, bi ,Classification Results (1) C(x1),

12、C(x2), , C(xi),Initial Guess of Cluster Parameters m1 , m2 , , mk,Input (Known),Output (Unknown),Cluster Parameters(1) m1 , m2 , , mk,Classification Results (2) C(x1), C(x2), , C(xi),Cluster Parameters(2) m1 , m2 , , mk,Classification Results (ic) C(x1), C(x2), , C(xi),Cluster Parameters(ic) m1 , m2

13、 , , mk,Difference between K-means and EM,46,K-means,Boot Step: Initialize K clusters: C1, , CK Each Cluster is represented by its mean mj Iteration Step: Estimate the cluster of each data Re-estimate the cluster parameters,Difference between K-means and EM,47,Kmeans -EM,Boot Step: Initialize K clus

14、ters: C1, , CK Iteration Step: Estimate the cluster of each data Re-estimate the cluster parameters,(j, j) and P(Cj) for each cluster j.,For each cluster j,Expectation,Maximization,Difference between K-means and EM,48,Classifier (EM),Classification Results p(C1|x1) p(Cj|x2) p(Cj|xi) ,Cluster Paramet

15、ers (1,1),p(C1) for C1 (2,2),p(C2) for C2 (k,k),p(Ck) for Ck,EM,Difference between K-means and EM,49,EM,x1=r1, g1, b1 x2=r2, g2, b2 xi=ri, gi, bi ,Cluster Parameters (1,1), p(C1) for C1 (2,2), p(C2) for C2 (k,k), p(Ck) for Ck,Input (Known),Output (Unknown),Classification Results p(C1|x1) p(Cj|x2) p(

16、Cj|xi) ,Difference between K-means and EM,50,EM(E-step),x1=r1, g1, b1 x2=r2, g2, b2 xi=ri, gi, bi ,Cluster Parameters (1,1), p(C1) for C1 (2,2), p(C2) for C2 (k,k), p(Ck) for Ck,Input (Known),Output,Classification Results p(C1|x1) p(Cj|x2) p(Cj|xi) ,Estimation,+,Difference between K-means and EM,51,

17、EM (M-step),x1=r1, g1, b1 x2=r2, g2, b2 xi=ri, gi, bi ,Cluster Parameters (1,1), p(C1) for C1 (2,2), p(C2) for C2 (k,k), p(Ck) for Ck,Input (Known),Input (Estimation),Output,+,Classification Results p(C1|x1) p(Cj|x2) p(Cj|xi) ,Difference between K-means and EM,52,EM,Boot Step: Initialize K clusters:

18、 C1, , CK Iteration Step: Expectation Step Maximization Step,(j, j) and P(Cj) for each cluster j.,53,Case Study (1),We have a data set with 1000 2-D data points (three clusters, k=3), how can we cluster it?,54,Case Study (2),Step 1: Initialize the partition Randomly select 3 points as initial class

19、centers; Partition the data with the 3 mean points Step 2: E step Step 3: EM algorithm do M Step E Step until convergence,55,Step 1: Initialize the partition,56,57,58,Image Segmentation using EM,Step 1: Feature Extraction Step 2: Image Segmentation using EM,Symbols,The feature vector for pixel i is called xi. There are going to be K seg