In this case, the sum of squared errors is minimized by the sample mean in Software

Generation QR Code in Software In this case, the sum of squared errors is minimized by the sample mean

Our problem here, however, involves a mixture of k different Normal distributions, and we cannot observe which instances were generated by which distribution Thus, we have a prototypical example of a problem involving hidden variables In the example of Figure 64, we can think of the full description of each instance as the triple (xi, , ziz),where xi is the observed value of the ith zil instance and where zil and zi2 indicate which of the two Normal distributions was i used to generate the value xi In particular, zijhas the value 1 if x was created by the jth Normal distribution and 0 otherwise Here xi is the observed variable in the description of the instance, and zil and zi2are hidden variables If the values of zil and zi2 were observed, we could use Equation (627) to solve for the means p1 and p2 Because they are not, we will instead use the EM algorithm Applied to our k-means problem the EM algorithm searches for a maximum likelihood hypothesis by repeatedly re-estimating the expected values of the hidden variables zij given its current hypothesis ( p I pk), then recalculating the

maximum likelihood hypothesis using these expected values for the hidden variables We will first describe this instance of the EM algorithm, and later state the EM algorithm in its general form Applied to the problem of estimating the two means for Figure 64, the EM algorithm first initializes the hypothesis to h = (PI, p2),where p1 and p are 2 arbitrary initial values It then iteratively re-estimates h by repeating the following two steps until the procedure converges to a stationary value for h

Step 1: Calculate the expected value E[zij] of each hidden variable zi,, assuming the current hypothesis h = (p1,p2) holds Step 2: Calculate a new maximum likelihood hypothesis h' = (pi, p;), assuming the value taken on by each hidden variable zij is its expected value E [ z i j ] calculated in Step 1 Then replace the hypothesis h = (pl, p2) by the new hypothesis h' = (pi,pi) and iterate

Let us examine how both of these steps can be implemented in practice Step 1 must calculate the expected value of each zi, This E [ 4 ] is just the probability that instance xi was generated by the jth Normal distribution

Thus the first step is implemented by substituting the current values (pl, p2)and the observed xi into the above expression In the second step we use the E[zij] calculated during Step 1 to derive a new maximum likelihood hypothesis h' = (pi,pi) AS we will discuss later, the maximum likelihood hypothesis in this case is given by

Note this expression is similar to the sample mean from Equation (628) that is used to estimate p for a single Normal distribution Our new expression is just the weighted sample mean for p j , with each instance weighted by the expectation E[z,j] that it was generated by the jth Normal distribution The above algorithm for estimating the means of a mixture of k Normal distributions illustrates the essence of the EM approach: The current hypothesis is used to estimate the unobserved variables, and the expected values of these variables are then used to calculate an improved hypothesis It can be proved that on each iteration through this loop, the EM algorithm increases the likelihood P ( D l h ) unless it is at a local maximum The algorithm thus converges to a local maximum likelihood hypothesis for (pl, w2)

Above we described an EM algorithm for the problem of estimating means of a mixture of Normal distributions More generally, the EM algorithm can be applied in many settings where we wish to estimate some set of parameters 8 that describe an underlying probability distribution, given only the observed portion of the full data produced by this distribution In the above two-means example the parameters of interest were 8 = (PI,p2), and the full data were the triples (xi,zil,zi2) of which only the xi were observed In general let X = {xl, ,x} denote the , observed data in a set of m independently drawn instances, let Z = {zl, , z} , denote the unobserved data in these same instances, and let Y = X U Z denote the full data Note the unobserved Z can be treated as a random variable whose probability distribution depends on the unknown parameters 8 and on the observed data X Similarly, Y is a random variable because it is defined in terms of the random variable Z In the remainder of this section we describe the general form of the EM algorithm We use h to denote the current hypothesized values of the parameters 8, and h' to denote the revised hypothesis that is estimated on each iteration of the EM algorithm The EM algorithm searches for the maximum likelihood hypothesis h' by seeking the h' that maximizes E[ln P(Y (h')]This expected value is taken over the probability distribution governing Y , which is determined by the unknown parameters 8 Let us consider exactly what this expression signifies First, P(Ylhl) is the likelihood of the full data Y given hypothesis h' It is reasonable that we wish to find a h' that maximizes some function of this quantity Second, maximizing the logarithm of this quantity In P(Ylhl) also maximizes P(Ylhl), as we have discussed on several occasions already Third, we introduce the expected value E[ln P(Ylhl)] because the full data Y is itself a random variable Given that the full data Y is a combination of the observed data X and unobserved data Z, we must average over the possible values of the unobserved Z, weighting each according to its probability In other words we take the expected value E[ln P ( Y lh')] over the probability distribution governing the random variable Y The distribution governing Y is determined by the completely known values for X, plus the distribution governing Z What is the probability distribution governing Y In general we will not know this distribution because it is determined by the parameters 0 that we are trying to estimate Therefore, the EM algorithm uses its current hypothesis h in place of the actual parameters 8 to estimate the distribution governing Y Let us define a function Q(hllh) that gives E[ln P(Y lh')] as a function of h', under the assumption that 8 = h and given the observed portion X of the full data Y

We write this function Q in the form Q(hllh) to indicate that it is defined in part by the assumption that the current hypothesis h is equal to 8 In its general form, the EM algorithm repeats the following two steps until convergence: