Home > Articles

  • Print
  • + Share This
This chapter is from the book

3.2 Traditional Derivation of EM

Each EM iteration is composed of two steps—Estimation (E) and Maximization (M). The M-step maximizes a likelihood function that is further refined in each iteration by the E-step. This section derives the traditional EM and establishes its convergence property.

3.2.1 General Analysis

The following notations are adopted.

  • X = {xt ∊ ℜD; t = 1, . . , T} is the observation sequence, where T is the number of observations and D is the dimensionality of xt.

  • C = {C(1), . . , C(J)} is the set of cluster mixture labels, where J is the number of mixture components.

  • Z = {zt ∊ C; t = 1, . . , T} is the set of missing data (specifying the hidden-state information).

  • θ = {θ(j); j = 1, . . , J} is the set of unknown parameters that define the density function for approximating the true probability density of X.

  • θ(j)= {π(j), φ(j)}, where π(j) denotes the prior probability of the j-th component density and φ(j) defines the j-th component density.

Note that the combination of observations X and the "hidden-states" Z constitute the complete-data. The likelihood of the complete-data is instrumental in accordance with the EM formulation.

To facilitate the derivation, define

Equation 3.2.1

03equ06.gif


as the log-likelihood of the incomplete-data given the current estimate θn, where n represents the iteration index; also, define p(Z, X|θn) as the completed data likelihood. According to probability theory, [1] p(X|θn) can be expressed as

Equation 3.2.2

03equ07.gif


Using Eq. 3.2.1 and Eq. 3.2.2, one can write the incomplete-data log-likelihood as follows:

Equation 3.2.3

03equ08.gif


where EZ{} denotes expectation with respect to Z. Thus, denote

Equation 3.2.4

03equ09.gif


and

Equation 3.2.5

03equ10.gif


where R(θ|θn) is an entropy term representing the difference between the incomplete-data likelihood and the expectation of the completed-data likelihood. Interpretation of R(θ|θn) and its role in the EM algorithm is discussed further in Section 3.3.

3.2.2 Convergence Property of EM

The following demonstrates why the EM algorithm has a general convergence property. The basic idea is via Jensen's inequality. More precisely, it can be shown that if the Q-function in Eq. 3.2.4 is improved in each iteration (in the M-step), then so will be the likelihood function L.

The proof of convergence begins with the observation of the following relationship:

Equation 3.2.6

03equ11.gif


Using Eq. 3.2.6 and Jensen's inequality, this is obtained:

Equation 3.2.7

03equ12.gif


In the M-step of the n-th iteration, 0* is selected according to

Equation 3.2.8

03equ13.gif


This means one can always choose a θ* at iteration n such that

Equation 3.2.9

03equ14.gif


Note that this equation constitutes a sufficient condition to ensure the convergence property of the EM algorithm because, according to Eqs. 3.2.3, 3.2.7, and 3.2.9

03equ15.gif


Instead of directly maximizing L(X|θ), the EM algorithm divides the optimization problem into two subproblems: Expectation and Maximization.

In each EM iteration, the E-step computes Q(θ|θn) using a set of presumed model parameters θn. The M-step determines the value of 0 (say θ*) that maximizes Q(θ|θn); that is,

Equation 3.2.10

03equ16.gif


This results in (see Problem 8)

Equation 3.2.11

03equ17.gif


Dividing the optimization into two interdependent steps is most useful if optimizing Q(θ|θn) is simpler than that of L(X|θn). Figure 3.4 illustrates how the E-and M-steps interplay to obtain a maximum-likelihood solution. The next section explains how to compute Q(θ|θn) in the E-step and how to maximize Q(θ|θn) in the M-step.

03fig04.gifFigure 3.4 The flow of the EM algorithm.

Generalized EM

In case θ* in Eq. 3.2.8 is difficult to attain, the EM approach is still applicable if one can improve Q(θ|θn) in each M-step (e.g., by gradient ascent). The algorithm is known as generalized EM. Although convergence of generalized EM is slower than that of the standard EM, it offers a more general and flexible framework for dividing the optimization process into the EM steps.

3.2.3 Complete-Data Likelihood

EM begins with an optimization of a likelihood function, which may be considerably simplified if a set of "missing" or "hidden" data is assumed to be known. The following demonstrates that computing the expectation of the complete-data likelihood in the E-step can be accomplished by finding the expectation of the missing or hidden data.

If X = {xt; t = 1,..., T} contains T statistically independent vectors and Z = {ztC; t = 1,..., T}, where zt = C(j) means that the j-th mixture generates xt, then one can write p(Z, X|θ) as

03equ18.gif


Now, a set of indicator variables is introduced to indicate the status of the hidden-states: [2]

03equ19.gif


where

03equ20.gif


Since for each t only one of the terms in 03inl04.gif is equal to one and all of the others are equal to 0, one can express p(Z, X|θ) as follows:

03equ21.gif


03equ22.gif


Hence, the completed-data likelihood is given by

Equation 3.2.12

03equ23.gif


where π(j) is the mixing coefficient of the j-th mixture. Eq. 3.2.12 uses the fact that 03inl64.gif and 03inl65.gif. Moreover, because there is only one non-zero term inside the summation 03inl05.gif, one can extract sigmatj.gif from the log function without affecting the result.

E-Step

Taking the expectations of Eq. 3.2.12 and using the defintions in Eq. 3.2.4, one obtains

Equation 3.2.13

03equ24.gif


Then, define

03equ25.gif


and denote 03inl06.gif as the j-th mixture coefficient at iteration n. Using the Bayes theorem, one can express 03inl07.gif as

03equ26.gif


Equation 3.2.14

03equ27.gif


The E-step determines the best guess of the membership function 03inl07.gif. Once the probability 03inl07.gif are computed for each t and j, Q(θ|θn) can be considered as a function of θ. In the M-step of each iteration, this function is maximized to obtain the best value of θ (denoted as θ*). In most cases, the M-step is substantially simplified if 03inl07.gif are known. Therefore, the E-step can be viewed as a preparation step for the M-step.

3.2.4 EM for GMMs

To better illustrate the EM steps, a simple example applying EM to Gaussian mixture models (GMMs) is presented next. The most common forms for the mixture density are the radial basis functions (RBFs) or the more general elliptical basis functions (EBFs). In the latter case, the component density 03inl66.gif is a Gaussian distribution, with the model parameter of the j-th cluster φ(j) = {μ(j), Σ(j)}I consisting of a mean vector and a full-rank covariance matrix.

Assume a Gaussian mixture model:

03equ28.gif


where π(j), μ(j) and Σ(j) denote, respectively, the mixture coefficient, mean vector, covariance matrix of the j-th component density. The GMM's output is given by

Equation 3.2.15

03equ29.gif


where

Equation 3.2.16

03equ30.gif


is the j-th Gaussian density of the GMM. A closer look at Eqs. 3.2.15 and 3.2.16 reveals that the GMM parameters θ can be divided into two groups: one containing π(j)s and another containing μ(j)s and ∑(j)s. The former indicates the importance of individual mixture densities via the prior probabilities π(j)s, whereas the latter is commonly regarded as the kernel parameter defining the form of the mixture density. Unlike other optimization techniques (e.g., gradient descent) in which unknown parameters can be arranged in any order, the EM approach effectively makes use of the structural relationship among the unknown parameters to simplify the optimization process.

After the initialization of θ0, the EM iteration is as follows:

  • E-step. In the n-th iteration, compute 03inl07.gif (xt) for each j and t using Eqs. 3.2.14 and 3.2.16. This is followed by the M-step described next.

  • M-step. Maximize Q(θ|θn) with respect to θ to find θ*. Replace θn by θ*. Then, increment n by 1 and repeat the E-step until convergence.

To determine μ(k)*, set 03inl10.gif, which gives

Equation 3.2.17

03equ31.gif


To determine Σ(k)*, set 03inl10.gif, which gives

Equation 3.2.18

03equ32.gif


To determine π(k)*, maximize Q(θ|θn) with respect to π(k) subject to the constraint 03inl14.gif, which gives

Equation 3.2.19

03equ33.gif


The detailed derivations of Eq. 3.2.17 to Eq. 3.2.19 are as follows:

03equ34.gif


Equation 3.2.20

03equ35.gif


To determine Σ(k)*, k = 1,..., J, let Λ(k)) = (Σ(k))−1 and set 03inl10.gif, that is,

Equation 3.2.21

03equ36.gif


Equation 3.2.22

03equ37.gif


Note that Eq. 3.2.21 makes use of the identity 03inl18.gif, where A is a symmetric matrix. Note also that one can replace μ(k) by μ(k)* in Eq. 3.2.20 to obtain Eq. 3.2.18.

To determine π(r), r = 1,..., J, maximize Q(θ|θn) with respect to π(r) subject to the constraint 03inl20.gif. More specifically, maximize the function f(λ, π(j)) = 03inl21.gif where A is the Lagrange multiplier. Setting 03inl22.gif results in

Equation 3.2.23

03equ38.gif


Equation 3.2.24

03equ39.gif


Summing both size of Eq. 3.2.24 from r = 1 to J, one has

Equation 3.2.25

03equ40.gif


Equation 3.2.26

03equ41.gif


Substituting Eq. 3.2.26 into Eq. 3.2.24 results in

Equation 3.2.27

03equ42.gif


Complexity of EM

Let T denote the number of patterns, J the number of mixtures, and D the feature dimension, then the following is a rough estimation of the computation complexity of using EM to train a GMM:

  • E-step. o.gif(TJD + TJ) for each epoch.

  • M-step. o.gif(2TJD) for each epoch.

Numerical Example 1

This example uses the data in Figure 3.3(a) as the observed data. Assume that when EM begins, n = 0 and

03equ43.gif


Therefore, one has

Equation 3.2.28

03equ44.gif


and

Equation 3.2.29

03equ45.gif


Substituting X = {1, 2, 3, 4, 6, 7, 8} into Eqs. 3.2.28 and 3.2.29, Table 3.1 is obtained. Substituting 03inl23.gif in Table 3.1 into Eqs. 3.2.17 through 3.2.19 results in

Table 3.1. Values of 03inl23.gif in Example 1

Pattern Index (t)

Pattern (xt)

03inl24.gif

03inl24.gif

1

1

1

0

2

2

1

0

3

3

1

0

4

4

1

0

5

6

0

1

6

7

0

1

7

8

0

1

03equ46.gif


Then, continue the algorithm by computing Q(θ|θn) -that is, 03inl32.gif —which are then substituted into Eqs. 3.2.17 through 3.2.19 to obtain θ2. Figure 3.5 depicts the movement of the component density functions specified by μ(j) and σ(j) during the EM iterations, and Table 3.2 lists the numerical values of Q(θ|θn) and θn for the first five iterations. It is obvious that the algorithm converges quickly in this example.

03fig05.gifFigure 3.5 Movement of the component density function specified by μ(j) and (σ(j))2 for the first two EM iterations.

Table 3.2. Values of Q(θ|θn), μ(j) and (σ(j))2 in the course of EM iterations. Data shown in Figure 3.3(a) were used as the observed data.

Iteration (n)

Q(θ|θn)

03inl27.gif

03inl28.gif

03inl29.gif

03inl30.gif

0

-∞

0

1

9

1

1

-43.71

2.50

1.25

6.99

0.70

2

-25.11

2.51

1.29

7.00

0.68

3

-25.11

2.51

1.30

7.00

0.67

4

-25.10

2.52

1.30

7.00

0.67

5

-25.10

2.52

1.30

7.00

0.67

  • + Share This
  • 🔖 Save To Your Account