{"id":712,"date":"2019-01-09T05:05:55","date_gmt":"2019-01-09T05:05:55","guid":{"rendered":"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/?post_type=chapter&p=712"},"modified":"2019-01-09T06:08:37","modified_gmt":"2019-01-09T06:08:37","slug":"expectation-and-maximization","status":"publish","type":"chapter","link":"https:\/\/ebooks.inflibnet.ac.in\/csp15\/chapter\/expectation-and-maximization\/","title":{"rendered":"Expectation and Maximization"},"content":{"raw":"
\"epgp<\/a>\r\n<\/span><\/div>\r\n
\r\n\r\n \r\n\r\n \r\n\r\nLearning Objectives:<\/strong>\r\n\r\n \r\n\r\nThe learning objectives of this module are as follows:\r\n\r\n \r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 To understand the concept of Expectation Maximization (EM)\r\n\r\n \r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 To explain EM using a Coin Toss Example\r\n\r\n \r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 To understand the use of EM in K-means Algorithm\r\n\r\n \r\n\r\n33.1\u00a0 Introduction<\/strong>\r\n\r\n \r\n

The Expectation Maximization methodology was first presented in a general way by Dempster, Laird and Rubin in 1977. They define EM algorithm as an iterative estimation algorithm that can derive the maximum likelihood (ML) estimates in the presence of missing\/hidden data (\u201cincomplete data\u201d). As an example we have theclassical case of the Gaussian mixture, where we have a set of unknown Gaussian distributions.The goal of the EM algorithm is to facilitate maximum likelihood parameter estimation by introducing so-called hidden random variables which are not observed and therefore define the unobserved data.<\/p>\r\n \r\n

There are two main approaches to the applications of the EM algorithm. The first is when the data indeed has missing values, due to problems with or limitations of the observation process. The second approachis the optimization of the likelihood function is complex but however likelihood function can be simplified by assuming the existence of additional but missing (or hidden) parameters. The second type of application is more common in the pattern recognition. Now let us understand the concept of hidden and observed variables. Observed variables are directly measurable from the data, e.g. waveform values of a speech recording, Is it raining today? Did the smoke\u00a0alarm go off?. On the other hand hidden variablesinfluence the data, but are not trivial to measure e.g includethe phonemes that produce a given speech recording, the probability P (rain today | rain yesterday) and is the smoke alarm malfunctioning?<\/span><\/p>\r\n\r\n<\/div>\r\n

\r\n\r\n\"\"\r\n

Figure 33.1 Many to One Mapping<\/strong><\/p>\r\n \r\n

In Figure 33.1 X can be considered as the underlying space, x is the complete data (required for ML), Y<\/em> is the observation space, y is the actual observation and x is observed only by means of y(x) and X<\/em>(y) is a subset of X determined by y. The term y=(x) indicates that y is observed as some mapping of x.<\/p>\r\n \r\n

The EM approach has found usage in filling in missing data in a sample, discovering the value of latent variables, estimating parameters of HMMs, estimating parameters of finite mixtures, unsupervised learning of clusters and finding parameters of Mixtures of Gaussians (MoG).<\/p>\r\n \r\n\r\n33.2 The EM algorithm<\/strong>\r\n\r\n \r\n\r\nThe steps of the EM algorithm are as follows:\r\n

    \r\n \t
  1. We first consider a set of starting parameters given a set of incomplete (observed) data and we assume that observed data come from a specific model<\/li>\r\n \t
  2. We then use the model to \u201cestimate\u201d the missing data . In other words after formulating some parameters from observed data to build a model, we use this model to guess the missing value\/data. This step is called the expectation step.<\/li>\r\n \t
  3. Now we use the \u201ccomplete\u201d data that we have estimated to update parameters whereusing the missing data and observed data, we find the most likely modified parameters to build the modified model. This is called the maximization step .<\/li>\r\n \t
  4. We repeat steps 2 & 3 until convergence that is there is no change in the parameters of the model and the estimated model fits the observed data.<\/li>\r\n<\/ol>\r\n<\/div>\r\n \r\n

    The general idea of the algorithm is that we start by devising a noisy channel that is we use any model that predicts the corpus observations via some hidden structure and we Initially guess the parameters of the model. It is best to make an educated guess but random assumptions can also work. Then we repeat until convergence the Expectation and Maximization steps. In the<\/span>Expectation<\/strong> step <\/strong>we use current parameters (and observations) to reconstruct hidden structure while in the <\/span>Maximization step<\/strong> weuse that hidden structure (and observations) to re-estimate parameters.<\/span><\/p>\r\n\r\n

    \r\n\r\n\"\"\r\n

    Figure 33.2 General Idea of the EM algorithm<\/strong><\/p>\r\n \r\n

    In the example shown in Figure 33.2, we initially guess the probabilities of unknown parameters using which we guess the hidden structure such as tags, parses, weather (E step) and use it along with the observed structure such as words, eating ice cream to again re-estimate the probabilities (M step).<\/p>\r\n \r\n\r\n33.3\u00a0 EM and Maximum Likelihood Estimates<\/strong>\r\n\r\n \r\n

    As discussed above parameters describe the characteristics of a population. Their values are estimated from samples collected from that population.A maximum likelihood (ML) estimate is a parameter estimate that is most consistent with the sampled data since it attempts to maximize the likelihood function.<\/p>\r\n \r\n\r\nThe basic setting of EM which is essentially based on maximum likelihood estimates is outlined below:\r\n\r\n \r\n

    Let X be a set of data points considered asobserved<\/strong> data and \u0398bethe parameter vector. Now EM is a method to find \u03b8ML<\/sub>where L<\/em>(Q) is likelihood function<\/p>\r\n\r\n<\/div>\r\n

    \r\n\r\n\"\"\r\n

    In essence we need to determine the probability of the observed data given the parameter vector. Now calculating P(X | \u03b8) directly is hard. However calculating P(X,Y|\u03b8) is much simpler, where Y is \u201chidden\u201d data (or \u201cmissing\u201d data) associated with the observed data.<\/p>\r\n \r\n

    Let us first define Z = (X, Y) where Z is considered as the complete data that is \u201caugmented data\u201d, X is the observed data (\u201cincomplete\u201d data) and Y is the hidden data (\u201cmissing\u201d data). EM is an iterative method to perform Maximum Likelihood estimation which starts with an initial estimate for \u03b8andrefines the current estimate iteratively to increase the likelihood of the observed data:<\/p>\r\n \r\n

    p(Z\/<\/em>\u03b8)<\/em><\/p>\r\n \r\n\r\n33.4 EM \u2013 Coin Toss Example<\/strong>\r\n\r\n \r\n

    The EM strategy can be explained with a coin toss example. This is the example we will be using in subsequent iterations to explain the complete flow of the EM algorithm. In this example we assume that we are tossing a number of coins sequentially to obtain a sequence of Head or Tails. The context of the coin toss example is given in Table 33.1. Here the problem is defined as X, the sequence of Heads and Tails that is observed, Y as the identifier of the coin that is tossed in the sequence, which is hidden and finally \u03b8which is the parameter vector which is associated with the probabilities ofthe observed and hidden data. Here if we assume three coins are tossed \u03bb is the probability of coin 0 showing H (so 1 \u2212 \u03bb is the probability of it showing T), p1 is the probability of coin 1 showing H, and p2 is the probability of coin 2 showing H.<\/p>\r\n \r\n\r\n\r\n\r\n\r\n\r\n\r\n
    Problem<\/td>\r\nCoin toss<\/td>\r\n<\/tr>\r\n
    X(observed)<\/td>\r\nHead-tail sequences<\/td>\r\n<\/tr>\r\n
    Y (hidden)<\/td>\r\nCoin id sequences<\/td>\r\n<\/tr>\r\n
    \u0398<\/td>\r\np1, p2, \u03bb<\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n

    Table 33.1 Parameters of EM<\/strong><\/p>\r\n\r\n<\/div>\r\n\u00a0<\/strong>\r\n

    We can also modify the problem to figure out the probability of heads for two coins. Normally the ML estimate can be directly calculated from the results if we know the identity of which of the coins was tossed.<\/span><\/p>\r\n\r\n

    \r\n\r\n \r\n

    We have two coins indicated as coinsA<\/strong> and B<\/strong>and let us assume that the probabilities for heads are q<\/strong>A<\/em><\/strong>&q<\/strong> B<\/em><\/strong>respectively. We are given 5 measurements sets including 10 coin tosses in each set. Now we know which coin has been tossed in each measurement. The example sets of experiments are given in Table 33.2. In this table A coin has been indicated as red and B coin as blue. The first column in the table indicates the coin type for each of the 5 measurements since here we assume we know the identity of the coin. The second column indicates the sequence of 10 Heads and Tails observed for each measurement. Columns 3 and 4 indicate the number of Heads and Tails obtained in each coin toss for each measurement of each coin type. The final row shows the total number of Heads and Tails obtained for the measurements for each of the A and B coin types.<\/p>\r\n \r\n\r\n\"\"\r\n

    Table 33.2 Coin Toss Example of 5 measurements of 10 coin Tosses<\/strong><\/p>\r\n \r\n\r\nNow we calculate the ML probabilitiesq<\/strong>A<\/em><\/strong>&q<\/strong> B<\/em><\/strong>, the probabilities for heads of coins A and B respectively.\r\n\r\n \r\n

    Maximum Likelihood<\/strong>of theprobabilities q<\/strong>A<\/em><\/strong>&q <\/strong>B<\/em><\/strong>arecalculated by dividing the total number of Heads obtained by the total number of Head and Tails observed for each type of coin. Thus we get<\/p>\r\n \r\n\r\nq<\/strong>A<\/em><\/strong><\/sub> = 24\/24+6 = 24\/30 = 0.8\r\n\r\n \r\n\r\nq<\/strong>B<\/em><\/strong><\/sub> = 9\/9+11=9\/20=0.45\r\n\r\n<\/div>\r\n

    \r\n\r\n \r\n

    The above calculation is a basic probability calculation based on observations knowing whether coin A or B has been tossed.<\/p>\r\n \r\n

    We will now make the problem more interesting and assume that we do not even know which one of the coins is used for the sample set . Now we need to estimate the coin probabilities without knowing which one of the coins is being tossed.<\/p>\r\n \r\n\r\n33.5 EM Flow Explained with Coin Toss Example<\/strong>\r\n\r\n \r\n

    Note that when we do not know which of the coins is tossed in each set we cannot calculate ML directly and hence we use EM strategy to find the probabilities of which one of the coins is likely to be tossed. Figure 33.3 shows the complete flow of the EM algorithm. Remember we do not know which of the coins is tossed. Hence we start the process by assuming that for each of the coins A (red) and B (blue), the initial probabilities for heads are q<\/strong>A<\/em><\/strong>&q\u00a0<\/strong>B<\/em><\/strong>respectivelywhich are assumed to have random values. Hence as seen from Figure 33.3 we have randomly fixed q<\/strong>A<\/em><\/strong>to be 0.6 and q<\/strong> B<\/em><\/strong>to be 0.5. Now we observe the number of Heads and Tails for each of the 5 measurements.<\/p>\r\n \r\n\r\nE Step:<\/strong>\r\n\r\n \r\n

    The first stage is the Expectation<\/strong>stage for which we initially use the randomly assumed probabilities of q<\/strong>A<\/em><\/strong>&q<\/strong> B<\/em><\/strong> and the set of coin tosses observed for each measurement. Now we need to calculate the probabilities for Heads and Tails for both A and B coins for each measurement since we do not know which coin is tossed. We have shown the calculation for the first set .of measurements in Figure 33.3.<\/p>\r\n \r\n\r\nStep E-C1<\/strong>\r\n\r\n \r\n

    In the first step of the Expectation stage<\/strong> we assume that the coin toss sequence follows a binomial distribution, where n is total number of coin tosses, k is number of Heads (Tails) observed and p is the probability of observing heads for each coin.<\/p>\r\n\r\n<\/div>\r\n

    \r\n\r\n\"\"\r\n\r\n\"\"\r\n\r\n \r\n

    Figure 33.3 Flow of EM - Coin Toss Example<\/strong><\/p>\r\n \r\n

    Usingthe distribution we can calculate the probability of observing Heads and Tails for coins A and B for the first set as shown in Figure 33.4. Here<\/p>\r\n \r\n\r\nn - the total number of coins tossed in the first measurement = 10,<\/strong> k -the total number of heads observed =5<\/strong>\r\n\r\n \r\n

    Now we need to calculate the probability of observing Heads(Tails) for both coins A and B since we do not know which of the coins was tossed and hence p \u2013 (qA<\/em>)- the probability of heads for A (red) coin is initially assumed to be = 0.6<\/strong> & (qb<\/em>)- the probability of heads for B (blue) coin is initially assumed to be = 0.5<\/strong><\/p>\r\n \r\n\r\n\"\"\r\n

    Figure 33.4 Use of Binomial Distribution<\/strong><\/p>\r\n \r\n\r\nStep E-C2<\/strong>\r\n\r\n \r\n

    In the second step of the Expectation stage we calculate the probabilities of using coin A or B as follows:<\/p>\r\n0.201\/ (0.201+0.246)=0.45<\/strong>\r\n\r\n \r\n\r\n0.246\/ (0.201+0.246)=0.55<\/strong>\r\n\r\n \r\n\r\nWe calculate in a similar manner for all the experiments and the values obtained are shown in Figure 33.3.\r\n\r\n \r\n\r\nStep E-C3<\/strong>\r\n\r\n \r\n

    In the third step of the Expectation stage using the probability values obtained in step E-C2, we calculate the possible number of Heads and Tails that is likely\u00a0to be observed in each experiment if the coin tossed was A and if the coin tossed was B<\/span><\/p>\r\n\r\n<\/div>\r\n

    \r\n\r\nFirst Experiment \u2013 values corresponding to first row:<\/strong>\r\n\r\n \r\n\r\n(i)\u00a0 5(number of heads in First experiment)\r\n\r\n \r\n\r\n*0.45(probability of tossing coin A)=2.2H,\r\n\r\n \r\n\r\n(ii)\u00a0 5(number of Tails in First experiment)\r\n\r\n \r\n\r\n*0.45(probability of tossing coin A)=2.2H,\r\n\r\n \r\n\r\n(iii)\u00a0\u00a0 5(number of heads in First experiment) *0.55(probability of tossing coin B)=2.8H, (\r\n\r\n \r\n\r\niv)5(number of Tails in First experiment) *0.55(probability of tossing coin B)=2.8H.\r\n\r\n \r\n\r\nWe will also explain the calculations for second experiment .\r\n\r\n \r\n\r\nSecond Experiment \u2013 values corresponding to second row:<\/strong>\r\n\r\n \r\n\r\n(i)\u00a0 9(number of heads in Second experiment)\r\n\r\n \r\n\r\n*0.80(probability of tossing coin A)=7.2H,\r\n\r\n \r\n\r\n(ii)\u00a0 1(number of Tails in Second experiment)\r\n\r\n \r\n\r\n*0.8(probability of tossing coin A)=0.8H,\r\n\r\n \r\n\r\n(iii)\u00a0 9(number of heads in Second experiment) *0.20(probability of tossing coin B)=1.8H, (iv)1(number of Tails in Second experiment)\r\n\r\n \r\n\r\n*0.20(probability of tossing coin B)=0.2H.\r\n\r\n \r\n

    Similarly we can do the calculations for all 5 experiments. Using these calculated values for number of Head and Tails for each experiment, we can calculate the total number of Heads and Tails for both Coins A and B.<\/p>\r\n \r\n\r\nM Step<\/strong>\r\n\r\n \r\n

    Now we have the Maximization stage where we calculate the new values (after 1st\u00a0 iteration) of q<\/strong>A<\/em>\u00a0B<\/em><\/strong>(1)<\/em><\/strong>that is the maximum likelihood estimates of the probability of heads when coin A and probability of heads when coin B are tossed respectively using the values total number of Heads and Tails for both Coins A and B. This calculation is shown below:<\/p>\r\n \r\n

    q<\/strong>A<\/em><\/strong>(1)<\/em><\/strong>= 21.3(total number of Heads when coin A is tossed)\/(21.3+8.6)(total number of Heads and Tails when coin A is tossed)= 0.71<\/strong><\/p>\r\n \r\n

    q <\/strong>B<\/em><\/strong>(1)<\/em><\/strong>= 11.7(total number of Heads when coin B is tossed)\/(11.7+8.4)(total number of Heads and Tails when coin B is tossed)=0.58<\/strong><\/p>\r\n \r\n\r\nContinuing and Completing the EM algorithm<\/strong>\r\n\r\n \r\n

    Now we have completed one iteration of the EM algorithm. We now continue the second iteration of the algorithm using the above new values of q<\/strong>A<\/em><\/strong>&q<\/strong> B<\/em><\/strong>. We continue the iterations until the values of q<\/strong>A<\/em><\/strong>&q<\/strong> B<\/em><\/strong> do not change from one iteration to the next. This happens in the 10th iteration for our example (shown in Figure 33.3) when the values q<\/strong>A<\/em><\/strong>&q<\/strong> B<\/em><\/strong> converge to values 0.80<\/strong> and 0.52<\/strong> respectively.<\/p>\r\n\r\n<\/div>\r\n

    \r\n\r\n \r\n\r\n33.6 Kmeans and EM algorithm<\/strong>\r\n\r\n \r\n

    We can explain K means as an EM algorithm. First we initialize the k means (mk) of the Kmeans algorithm. In the E Step weassign each point to a Cluster and during the M Step given the Clusters we refine mean mkof each cluster k. This process is repeated until the change in means is small.<\/p>\r\n \r\n\r\n33.6.1 Generating Data from Mixture of Gaussians<\/strong>\r\n\r\n \r\n

    Now we can replace the \u2018hard\u2019 clustering of K-means described above with \u2018soft\u2019 probabilistic assignments . Here we assume that each instance x is generated<\/p>\r\n\"\"\r\n

    Figure 33.5 The Gaussian Distributions used to Generate Data<\/strong><\/p>\r\n\"\"\r\n

    Figure 33.6 The Use of a Mixture of Gaussians for Generating Data<\/strong><\/p>\r\n \r\n

    by choosing one of the k Gaussians at random and generating an instance according to that Gaussian(Figure 33.5). This requires more parameters to be determined that would fit the data. Figure 33.6 shows the probability of generating data p(X). This probability is based on the Gaussian distributions used, the mean and the variance of the Gaussian distributions and the mixing coefficients used. The sum of the mixing coefficients of all the Gaussian distributions use must be 1.<\/p>\r\n \r\n

    33.6.2 K-means and Mixture of Gaussians<\/strong><\/p>\r\n\r\n<\/div>\r\n

    \r\n\r\n \r\n

    Now we know that in a general K-means which is essentially a classifier and we need to find the parameterto fit data \u2013 that is we need to find the mean - \u00b5k<\/em> as already discussed above. However when we use mixture of Gaussians which is a probability model where we are defining a \u201csoft\u201d classifier. Now the parameters that are to be determined to fit to data are the means \u00b5k<\/em>and c<\/em>ovariance \u03a3k<\/em>which define the Gaussians distributions and the mixing coefficient \u03c0k<\/em>.<\/em> Now given the data set, find the mixing coefficients, means and covariance. If we knew which component generated each data point, the maximum likelihood solution would involve fitting each component to the corresponding cluster . However our problem is that the data set is unlabelled or are hidden (Figure 33.7).<\/p>\r\n\"\"\r\n

    Figure 33.7 K Means Scenario<\/strong><\/p>\r\n\"\"\r\n\r\nFigure 33.8 K means with Initial Guess of Cluster Points 33.6.3 EM for Estimating k Means<\/strong>\r\n\r\n \r\n

    Figure 33.8 shows the scenario of K means the instances from X are generated by a mixture of k Gaussians with unknown means <m1,\u2026,mk> of the k Gaussians.Remember we do not know which instance xi was generated by\u00a0which Gaussian. Now we need to determine the maximum likelihood estimates of <m1,\u2026,mk>. Now let us define the full description of each instance as yi=<xi,zi1,zi2> where zij is 1 if xi generated by j-th Gaussian. In this case xiis observable but however zijis unobservable.<\/span><\/p>\r\n\r\n<\/div>\r\n

    \r\n\r\n \r\n\r\n33.6.4 EM for Gaussian Mixtures<\/strong>\r\n\r\n \r\n\r\nHere we initialize the Gaussian parameters mean mk, co-variance \u00e5 k and mixing coefficient pk.\r\n\r\n \r\n\r\nE Step:<\/strong>\r\n\r\n \r\n

    In the E Step we assign each point xn an assignment score g(znk) for each cluster or Gaussian kwhich essentially indicates how much this Gaussian k is responsible for point Xn<\/p>\r\n \r\n\r\n\"\"\r\n

    Figure 33.9 Calculation of Assignment Score<\/strong><\/p>\r\n \r\n

    Here g(znk) is calculated as the mean and covariance of the Gaussian distribution corresponding to the kth mean multiplied by mixture coefficient of kth distribution divided by the summation of mean and covariance of all the Gaussian distributions multiplied by their corresponding mixture coefficient.<\/p>\r\n \r\n\r\nM step<\/strong>\r\n

    During the M Step, given scores, adjust mk, \u00e5 k, pk for each cluster kor Gaussian K. We update parameters using new g(znk) that is find the parameters that fit the new assignment score g(znk) the best. The new values of each of the parameters mknew , \u00e5 knew and pknew are determined as shown in Figure 33.10.<\/p>\r\n\r\n<\/div>\r\n\"\"\r\n

    Figure 33.10 Calculating new Values of Parameters during M Step<\/strong><\/p>\r\n \r\n

    Now we evaluate log likelihood as shown in Figure 33.11 . If likelihood or parameters converge we stop else we iterate with the E and M steps.<\/p>\r\n\"\"\r\n

    Figure 33.11 Evaluation of Log Likelihood<\/strong><\/p>\r\n \r\n\r\n33.7 Strengths of EM<\/strong>\r\n\r\n \r\n

    The major strength of the EM algorithm is its numerical stability where in every iteration of the EM algorithm, the likelihood of the observed data increases that is we are heading towards a solution. In addition, the EM handles parameter constraints gracefully.<\/p>\r\n \r\n\r\n33.8 Problems with EM<\/strong>\r\n\r\n \r\n

    In the case of EM algorithms can converge very slowly on some problems and this convergence is intimately related to the amount of missing information.It guarantees to improve the probability of the training corpus, which is different from reducing the errors directly. The EM algorithm cannot guarantee to reach global maximum and sometimes could get struck at the local maxima, saddle points, etc. Essentially the guess we make of the initial parameter values is very important and can decide on the time to converge.<\/p>\r\n \r\n\r\nSummary<\/strong>\r\n