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
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
depending on the parameters
. Let
be the latent or
missing data, so that
is the complete data with
loglikelihood
. The algorithm for solving the
problem in its general form is the following EM algorithm
([Dempster77],
[Hastie2009]): Choose initial values of the parameters .
 Expectation step: in thejth step, compute as a function of the dummy argument .
 Maximization step: in thejth step, calculate the new estimate by maximizing over .
 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
and
.
The
is the probability density function with
parameters
, where
the vector of means, and
is the
variancecovariance matrix. The probability density function for a
p
dimensional multivariate Gaussian distribution is defined as
follows:Let
be
the indicator function and
.
Computation
The EM algorithm for GMM includes the following steps:
Define the weights as follows:
for
i = 1, …, n
and
. Choose initial values of the parameters:
 Expectation step: in thejth step, compute the matrix with the weights
 Maximization step: in thejth step, for all compute:
 The mixture weights , where is the “amount” of the feature vectors that are assigned to therth mixture component
 Mean estimates
 Covariance estimate of size with
 Repeat steps 2 and 3 until any of these conditions is met:
 , where the likelihood function is:
 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 kdifferent random observations from the input data set
 Initial weights  the values of
 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
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 

algorithmFPType  float  The floatingpoint type that the algorithm uses for intermediate computations. Can be float or double . 
method  defaultDense  Performanceoriented computation method, the only method supported by the algorithm. 
nComponents  Not applicable  The number of components in the Gaussian Mixture Model, a required parameter. 
nTrials  20  The number of starts of the EM algorithm. 
nIterations  10  The maximal number of iterations in each start of the EM algorithm. 
accuracyThreshold  1.0e04  The threshold for termination of the algorithm. 
covarianceStorage  full  Covariance matrix storage scheme in the Gaussian Mixture Model:

engine  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 

weights  Pointer to the
numeric table with mixture weights. By default, this result is an object of the HomogenNumericTable class,
but you can define the result as an object of any class derived from NumericTable
except PackedTriangularMatrix , PackedSymmetricMatrix , and CSRNumericTable . 
means  Pointer to the
numeric table with each row containing the estimate
of the means for the i th mixture component, where
.By default, this result is an object of the HomogenNumericTable class,
but you can define the result as an object of any class derived from NumericTable
except PackedTriangularMatrix , PackedSymmetricMatrix , and CSRNumericTable . 
covariances  Pointer to the DataCollection object that contains k numeric tables,
each with the
variancecovariance matrix for the i th mixture
component of size:
By default, the collection contains objects of the HomogenNumericTable class,
but you can define them as objects of any class derived from NumericTable
except PackedTriangularMatrix and CSRNumericTable . 
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 

data  Pointer to the
numeric table with the data to which the EM
algorithm is applied. The input can be an object of any class derived
from NumericTable . 
inputWeights  Pointer to the
numeric table with initial mixture weights. This input can be an object of any class derived from NumericTable. 
inputMeans  Pointer to a
numeric table. Each row in this table contains the
initial value of the means for the i th mixture component, where
.
This input can be an object of any class derived from NumericTable . 
inputCovariances  Pointer to the DataCollection object that contains k numeric tables,
each with the
variancecovariance matrix for the i th mixture component of size:
The collection can contain objects of any class derived from NumericTable. 
inputValues  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 

algorithmFPType  float  The floatingpoint type that the algorithm uses for intermediate computations. Can be float or double . 
method  defaultDense  Performanceoriented computation method, the only method supported by the algorithm. 
nComponents  Not applicable  The number of components in the Gaussian Mixture Model, a required parameter. 
maxIterations  10  The maximal number of iterations in the algorithm. 
accuracyThreshold  1.0e04  The threshold for termination of the algorithm. 
covariance  Pointer to an object of the BatchIface class  Pointer to the algorithm that computes the covariance matrix. By default, the respective oneDAL algorithm is used,
implemented in the class derived from BatchIface . 
regularizationFactor  0.01  Factor for covariance regularization in the case of illconditional data. 
covarianceStorage  full  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 

weights  Pointer to the
numeric table with mixture weights. By default, this result is an object of the HomogenNumericTable class,
but you can define the result as an object of any class derived from NumericTable
except PackedTriangularMatrix , PackedSymmetricMatrix , and CSRNumericTable . 
means  Pointer to the
numeric table with each row containing the estimate
of the means for the i th mixture component, where
.By default, this result is an object of the HomogenNumericTable class,
but you can define the result as an object of any class derived from NumericTable
except PackedTriangularMatrix , PackedSymmetricMatrix , and CSRNumericTable . 
covariances  Pointer to the DataCollection object that contains k numeric tables,
each with the
variancecovariance matrix for the i th mixture component of size:
By default, the collection contains objects of the HomogenNumericTable class,
but you can define them as objects of any class derived from NumericTable
except PackedTriangularMatrix and CSRNumericTable . 
goalFunction  Pointer to the
numeric table with the value of the logarithm of
the likelihood function after the last iteration. By default, this result is an object of the HomogenNumericTable class. 
nIterations  Pointer to the
numeric table with the number of iterations
computed after completion of the algorithm. By default, this result is an object of the HomogenNumericTable class. 
Examples
C++ (CPU)
Batch Processing:
Java*
Python*
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 