Statistics 580 The EM Algorithm Introduction The EM algorithm is a very general iterative algorithm for parameter estimation by maximum likelihood when some of the random variables involved are not observed i.e.,con- sidered missing or incomplete.The EM algorithm formalizes an intuitive idea for obtaining parameter estimates when some of the data are missing: i.replace missing values by estimated values, ii.estimate parameters. iii.Repeat step (i)using estimated parameter values as true values,and step (ii)using estimated values as "observed"values,iterating until convergence. This idea has been in use for many years before Orchard and Woodbury (1972)in their missing information principle provided the theoretical foundation of the underlying idea. The term EM was introduced in Dempster,Laird,and Rubin(1977)where proof of general results about the behavior of the algorithm was first given as well as a large number of applications. For this discussion,let us suppose that we have a random vector y whose joint density f(y;0)is indexed by a p-dimensional parameter 0RP.If the complete-data vector y were observed,it is of interest to compute the maximum likelihood estimate of a based on the distribution of y.The log-likelihood function of y log L(0;y)=(0;y)=log f(y;0). is then required to be maximized. In the presence of missing data,however,only a function of the complete-data vector y,is observed.We will denote this by expressing y as(yobs,ymis),where yobs denotes the observed but“incomplete”data and ymis denotes the unobserved or“missing”data.For simplicity of description,assume that the missing data are missing at random (Rubin,1976),so that f(y;0)=f(yobs,ymis;0) =f1(yobsi0)f2(ymislyobsi 0), where fi is the joint density of yobs and f2 is the joint density of ymis given the observed data yobs,respectively.Thus it follows that lobs(;yobs)=e(0;y)-log f2(ymislyobsi0), where lobs(0;yobs)is the observed-data log-likelihood. 1Statistics 580 The EM Algorithm Introduction The EM algorithm is a very general iterative algorithm for parameter estimation by maximum likelihood when some of the random variables involved are not observed i.e., con￾sidered missing or incomplete. The EM algorithm formalizes an intuitive idea for obtaining parameter estimates when some of the data are missing: i. replace missing values by estimated values, ii. estimate parameters. iii. Repeat • step (i) using estimated parameter values as true values, and • step (ii) using estimated values as “observed” values, iterating until convergence. This idea has been in use for many years before Orchard and Woodbury (1972) in their missing information principle provided the theoretical foundation of the underlying idea. The term EM was introduced in Dempster, Laird, and Rubin (1977) where proof of general results about the behavior of the algorithm was first given as well as a large number of applications. For this discussion, let us suppose that we have a random vector y whose joint density f(y; θ) is indexed by a p-dimensional parameter θ ∈ Θ ⊆ Rp . If the complete-data vector y were observed, it is of interest to compute the maximum likelihood estimate of θ based on the distribution of y. The log-likelihood function of y log L(θ; y) = `(θ; y) = log f(y; θ), is then required to be maximized. In the presence of missing data, however, only a function of the complete-data vector y, is observed. We will denote this by expressing y as (yobs, ymis), where yobs denotes the observed but “incomplete” data and ymis denotes the unobserved or “missing” data. For simplicity of description, assume that the missing data are missing at random (Rubin, 1976), so that f(y; θ) = f(yobs, ymis; θ) = f1(yobs; θ) · f2(ymis|yobs; θ), where f1 is the joint density of yobs and f2 is the joint density of ymis given the observed data yobs, respectively. Thus it follows that `obs(θ; yobs) = `(θ; y) − log f2(ymis|yobs; θ), where `obs(θ; yobs) is the observed-data log-likelihood. 1