ExpectationMaximization¶
ExpectationMaximization (EM) algorithm is an iterative method for finding the maximum likelihood and maximum a posteriori estimates of parameters in models that typically depend on hidden variables.
While serving as a clustering technique, EM is also used in nonlinear dimensionality reduction, missing value problems, and other areas.
Details¶
Given a set \(X\) of \(n\) feature vectors \(x_1 = (x_{11}, \ldots, x_{1p}), \ldots, x_n = (x_{n1}, \ldots, x_{np})\) of dimension \(p\), the problem is to find a maximumlikelihood estimate of the parameters of the underlying distribution when the data is incomplete or has missing values.
ExpectationMaximization (EM) Algorithm in the General Form¶
Let \(X\) be the observed data which has loglikelihood \(l(\theta; X)\) depending on the parameters \(\theta\). Let \(X^m\) be the latent or missing data, so that \(T=(X, X^m)\) is the complete data with loglikelihood \(l_0(\theta; X)\). The algorithm for solving the problem in its general form is the following EM algorithm ([Dempster77], [Hastie2009]):
Choose initial values of the parameters \(\theta^{(0)}\).
Expectation step: in the \(j\)th step, compute \(Q(\theta', \theta^{(j)}) = E (l_0(\theta'; T)  X, \theta^{(j)})\) as a function of the dummy argument \(\theta'\).
Maximization step: in the \(j\)th step, calculate the new estimate \(\theta^{(j+1)}\) by maximizing \(Q(\theta', \theta^{(j)})\) over \(\theta'\).
Repeat steps 2 and 3 until convergence.
EM algorithm for the Gaussian Mixture Model¶
Gaussian Mixture Model (GMM) is a mixture of k pdimensional multivariate Gaussian distributions represented as
where \(\sum _{i=1}^{k}{\alpha_i} = 1\) and \(\alpha_i \geq 0\).
The \(pd(x\theta_i)\) is the probability density function with parameters \(\theta_i = (m_i, \Sigma_i)\), where \(m_i\) the vector of means, and \(\Sigma_i\) is the variancecovariance matrix. The probability density function for a \(p\)dimensional multivariate Gaussian distribution is defined as follows:
Let \(x_{ij} = I\{x_i \text{belongs to j mixture component}\}\) be the indicator function and \(\theta = (\alpha_1, \ldots, \alpha_k; \theta_1, \ldots, \theta_k)\).
Computation¶
The EM algorithm for GMM includes the following steps:
Define the weights as follows:
for \(i = 1, \ldots, n\) and \(j=1, \ldots, k\).
Choose initial values of the parameters: \({\theta }^{\left(0\right)}=\left({\alpha }_{1}^{\left(0\right)},...,{\alpha }_{k}^{\left(0\right)};{\theta }_{1}^{\left(0\right)},...,{\theta }_{k}^{\left(0\right)}\right)\)
Expectation step: in the \(j\)th step, compute the matrix \(W = {(w_{ij})}_{nxk}\) with the weights \(w_{ij}\)
Maximization step: in the \(j\)th step, for all \(r=1, \ldots, k\) compute:
The mixture weights \({\alpha }_{r}^{\left(j+1\right)}=\frac{{n}_{r}}{n}\), where \({n}_{r}=\sum _{i=1}^{n}{w}_{ir}\) is the “amount” of the feature vectors that are assigned to the \(r\)th mixture component
Mean estimates \({m}_{r}^{\left(j+1\right)}=\frac{1}{{n}_{r}}\sum _{i=1}^{n}{w}_{ir}{x}_{i}\)
Covariance estimate \(\sum _{r}^{(j+1)}=({\sigma }_{r,hg}^{(j+1)})\) of size \(p \times p\) with \(\sigma_{r,hg}^{(j+1)}=\frac{1}{n_r}\sum_{l=1}^{n}{w}_{lr}(x_{lh}m_{r,h}^{(j+1)})(x_{lg}m_{r,g}^{(j+1)})\)
Repeat steps 2 and 3 until any of these conditions is met:
\(\log({\theta }^{(j+1)}{\theta }^{(j)})<\epsilon\), where the likelihood function is:
\(\log(\theta)=\sum_{i=1}^{n}\log(\sum _{j=1}^{k}{pd(x}_{i}{z}_{j},{\theta }_{j}){\alpha }_{j})\)
The number of iterations exceeds the predefined level.
Initialization¶
The EM algorithm for GMM requires initialized vector of weights, vectors of means, and variancecovariance [Biernacki2003, Maitra2009].
The EM initialization algorithm for GMM includes the following steps:
Perform nTrials starts of the EM algorithm with nIterations iterations and start values:
Initial means  \(k\) different random observations from the input data set
Initial weights  the values of \(1/k\)
Initial covariance matrices  the covariance of the input data
Regard the result of the best EM algorithm in terms of the likelihood function values as the result of initialization
Initialization¶
The EM algorithm for GMM requires initialized vector of weights, vectors of means, and variancecovariance. Skip the initialization step if you already calculated initial weights, means, and covariance matrices.
Batch Processing¶
Algorithm Input¶
The EM for GMM initialization algorithm accepts the input
described below. Pass the Input ID
as a parameter to the methods
that provide input for your algorithm.
Input ID 
Input 

data 
Pointer to the \(n \times p\) numeric table with the data to which the EM initialization algorithm is applied. The input can be an object of any class derived from NumericTable. 
Algorithm Parameters¶
The EM for GMM initialization algorithm has the following parameters:
Parameter 
Default Value 
Description 



The floatingpoint type that the algorithm uses for intermediate computations. Can be 


Performanceoriented computation method, the only method supported by the algorithm. 

Not applicable 
The number of components in the Gaussian Mixture Model, a required parameter. 

\(20\) 
The number of starts of the EM algorithm. 

\(10\) 
The maximal number of iterations in each start of the EM algorithm. 

1.0e04 
The threshold for termination of the algorithm. 


Covariance matrix storage scheme in the Gaussian Mixture Model:


SharePtr< engines:: mt19937:: Batch>() 
Pointer to the random number generator engine that is used internally to get the initial means in each EM start. 
Algorithm Output¶
The EM for GMM initialization algorithm calculates the results described below.
Pass the Result ID
as a parameter to the methods that access the results of your algorithm.
Result ID 
Result 


Pointer to the \(1 \times k\) numeric table with mixture weights. Note By default, this result is an object of the 

Pointer to the \(k \times p\) numeric table with each row containing the estimate of the means for the \(i\)th mixture component, where \(i=0, 1, \ldots, k1\). Note By default, this result is an object of the 

Pointer to the
Note By default, the collection contains objects of the 
Computation¶
Batch Processing¶
Algorithm Input¶
The EM for GMM algorithm accepts the input described below.
Pass the Input ID
as a parameter to the methods that provide input for your algorithm.
Input ID 
Input 


Pointer to the \(n \times p\) numeric table with the data to which the EM
algorithm is applied. The input can be an object of any class derived
from 

Pointer to the \(1 \times k\) numeric table with initial mixture weights. This input can be an object of any class derived from NumericTable. 

Pointer to a \(k \times p\) numeric table. Each row in this table contains the
initial value of the means for the \(i\)th mixture component, where \(i = 0, 1, \ldots, k1\).
This input can be an object of any class derived from 

Pointer to the
The collection can contain objects of any class derived from NumericTable. 

Pointer to the result of the EM for GMM initialization algorithm. The result of initialization contains weights, means, and a collection of covariances. You can use this input to set the initial values for the EM for GMM algorithm instead of explicitly specifying the weights, means, and covariance collection. 
Algorithm Parameters¶
The EM for GMM algorithm has the following parameters:
Parameter 
Default Value 
Description 



The floatingpoint type that the algorithm uses for intermediate computations. Can be 


Performanceoriented computation method, the only method supported by the algorithm. 

Not applicable 
The number of components in the Gaussian Mixture Model, a required parameter. 

\(10\) 
The maximal number of iterations in the algorithm. 

1.0e04 
The threshold for termination of the algorithm. 

Pointer to an object of the BatchIface class 
Pointer to the algorithm that computes the covariance matrix. Note By default, the respective oneDAL algorithm is used,
implemented in the class derived from 

\(0.01\) 
Factor for covariance regularization in the case of illconditional data. 


Covariance matrix storage scheme in the Gaussian Mixture Model:

Algorithm Output¶
The EM for GMM algorithm calculates the results described below. Pass
the Result ID
as a parameter to the methods that access the results
of your algorithm.
Result ID 
Result 


Pointer to the \(1 \times k\) numeric table with mixture weights. Note By default, this result is an object of the 

Pointer to the \(k \times p\) numeric table with each row containing the estimate of the means for the \(i\)th mixture component, where \(i=0, 1, \ldots, k1\). Note By default, this result is an object of the 

Pointer to the DataCollection object that contains \(k\) numeric tables, each with the \(p \times p\) variancecovariance matrix for the \(i\)th mixture component of size:
Note By default, the collection contains objects of the 

Pointer to the \(1 \times 1\) numeric table with the value of the logarithm of the likelihood function after the last iteration. Note By default, this result is an object of the 

Pointer to the \(1 \times 1\) numeric table with the number of iterations computed after completion of the algorithm. Note By default, this result is an object of the 
Examples¶
Batch Processing:
Batch Processing:
Performance Considerations¶
To get the best overall performance of the expectationmaximization algorithm at the initialization and computation stages:
If input data is homogeneous, provide the input data and store results in homogeneous numeric tables of the same type as specified in the algorithmFPType class template parameter.
If input data is nonhomogeneous, use AOS layout rather than SOA layout.
Optimization Notice 

Intel’s compilers may or may not optimize to the same degree for nonIntel microprocessors for optimizations that are not unique to Intel microprocessors. These optimizations include SSE2, SSE3, and SSSE3 instruction sets and other optimizations. Intel does not guarantee the availability, functionality, or effectiveness of any optimization on microprocessors not manufactured by Intel. Microprocessordependent optimizations in this product are intended for use with Intel microprocessors. Certain optimizations not specific to Intel microarchitecture are reserved for Intel microprocessors. Please refer to the applicable product User and Reference Guides for more information regarding the specific instruction sets covered by this notice. Notice revision #20110804 