Developer Guide and Reference

  • 2021.2
  • 03/26/2021
  • Public Content
Contents

Expectation-Maximization

Expectation-Maximization (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 non-linear dimensionality reduction, missing value problems, and other areas.

Details

Given a set
X
of
n
feature vectors LaTex Math image. of dimension
p
, the problem is to find a maximum-likelihood estimate of the parameters of the underlying distribution when the data is incomplete or has missing values.
Expectation-Maximization (EM) Algorithm in the General Form
Let
X
be the observed data which has log-likelihood LaTex Math image. depending on the parameters LaTex Math image.. Let LaTex Math image. be the latent or missing data, so that LaTex Math image. is the complete data with log-likelihood LaTex Math image.. The algorithm for solving the problem in its general form is the following EM algorithm ([Dempster77], [Hastie2009]):
  1. Choose initial values of the parameters LaTex Math image..
  2. Expectation step
    : in the
    j
    -th step, compute LaTex Math image. as a function of the dummy argument LaTex Math image..
  3. Maximization step
    : in the
    j
    -th step, calculate the new estimate LaTex Math image. by maximizing LaTex Math image. over LaTex Math image..
  4. Repeat steps 2 and 3 until convergence.
EM algorithm for the Gaussian Mixture Model
Gaussian Mixture Model (GMM) is a mixture of k p-dimensional multivariate Gaussian distributions represented as
LaTex Math image.
where LaTex Math image. and LaTex Math image..
The LaTex Math image. is the probability density function with parameters LaTex Math image., where LaTex Math image. the vector of means, and LaTex Math image. is the variance-covariance matrix. The probability density function for a
p
-dimensional multivariate Gaussian distribution is defined as follows:
LaTex Math image.
Let LaTex Math image. be the indicator function and LaTex Math image..
Computation
The EM algorithm for GMM includes the following steps:
Define the weights as follows:
LaTex Math image.
for
i = 1, …, n
and LaTex Math image..
  1. Choose initial values of the parameters: LaTex Math image.
  2. Expectation step
    : in the
    j
    -th step, compute the matrix LaTex Math image. with the weights LaTex Math image.
  3. Maximization step: in the
    j
    -th step, for all LaTex Math image. compute:
    1. The mixture weights LaTex Math image., where LaTex Math image. is the “amount” of the feature vectors that are assigned to the
      r
      -th mixture component
    2. Mean estimates LaTex Math image.
    3. Covariance estimate LaTex Math image. of size LaTex Math image. with LaTex Math image.
  4. Repeat steps 2 and 3 until any of these conditions is met:
    • LaTex Math image., where the likelihood function is:
      LaTex Math image.
    • The number of iterations exceeds the predefined level.
Initialization
The EM algorithm for GMM requires initialized vector of weights, vectors of means, and variance-covariance [Biernacki2003, Maitra2009].
The EM initialization algorithm for GMM includes the following steps:
  1. 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 LaTex Math image.
    • Initial covariance matrices - the covariance of the input data
  2. 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 variance-covariance. 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 LaTex Math image. 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 floating-point type that the algorithm uses for intermediate computations. Can be
float
or
double
.
method
defaultDense
Performance-oriented 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.0e-04
The threshold for termination of the algorithm.
covarianceStorage
full
Covariance matrix storage scheme in the Gaussian Mixture Model:
  • full
    - covariance matrices are stored as numeric tables of size LaTex Math image.. All elements of the matrix are updated during the processing.
  • diagonal
    - covariance matrices are stored as numeric tables of size LaTex Math image.. Only diagonal elements of the matrix are updated during the processing, and the rest are assumed to be zero.
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 LaTex Math image. 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 LaTex Math image. numeric table with each row containing the estimate of the means for the
i
-th mixture component, where LaTex Math image..
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 LaTex Math image. variance-covariance matrix for the
i
-th mixture component of size:
  • LaTex Math image. - for the full covariance matrix storage scheme
  • LaTex Math image. - for the diagonal covariance matrix storage scheme
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 LaTex Math image. 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 LaTex Math image. numeric table with initial mixture weights. This input can be an object of any class derived from NumericTable.
inputMeans
Pointer to a LaTex Math image. numeric table. Each row in this table contains the initial value of the means for the
i
-th mixture component, where LaTex Math image.. 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 LaTex Math image. variance-covariance matrix for the
i
-th mixture component of size:
  • LaTex Math image. - for the full covariance matrix storage scheme
  • LaTex Math image. - for the diagonal covariance matrix storage scheme
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 floating-point type that the algorithm uses for intermediate computations. Can be
float
or
double
.
method
defaultDense
Performance-oriented 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.0e-04
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 ill-conditional data.
covarianceStorage
full
Covariance matrix storage scheme in the Gaussian Mixture Model:
  • full
    - covariance matrices are stored as numeric tables of size LaTex Math image.. All elements of the matrix are updated during the processing.
  • diagonal
    - covariance matrices are stored as numeric tables of size LaTex Math image.. Only diagonal elements of the matrix are updated during the processing, and the rest are assumed to be zero.
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 LaTex Math image. 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 LaTex Math image. numeric table with each row containing the estimate of the means for the
i
-th mixture component, where LaTex Math image..
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 LaTex Math image. variance-covariance matrix for the
i
-th mixture component of size:
  • LaTex Math image. - for the full covariance matrix storage scheme
  • LaTex Math image. - for the diagonal covariance matrix storage scheme
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 LaTex Math image. 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 LaTex Math image. 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*
There is no support for Java on GPU.
Batch Processing:
Python*
Batch Processing:

Performance Considerations

To get the best overall performance of the expectation-maximization 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 non-homogeneous, use AOS layout rather than SOA layout.
Product and Performance Information
Performance varies by use, configuration and other factors. Learn more at www.Intel.com/PerformanceIndex​.
Notice revision #20201201

Product and Performance Information

1

Performance varies by use, configuration and other factors. Learn more at www.Intel.com/PerformanceIndex.