Details

Given a set of feature vectors of dimension , 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.

Let be the observed data which has log-likelihood depending on the parameters . Let be the latent or missing data, so that is the complete data with log-likelihood . 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 the -th step, compute as a function of the dummy argument .
Maximization step
: in the -th step, calculate the new estimate by maximizing over .
Repeat steps 2 and 3 until convergence.

where and .

The is the probability density function with parameters , where the vector of means, and is the variance-covariance matrix. The probability density function for a -dimensional multivariate Gaussian distribution is defined as follows:

Let be the indicator function and .

for and .

Choose initial values of the parameters:
Expectation step
: in the -th step, compute the matrix with the weights
Maximization step: in the -th step, for all compute:
The mixture weights , where is the “amount” of the feature vectors that are assigned to the -th 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.

Perform nTrials starts of the EM algorithm with nIterations iterations and start values:
Initial means - different 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

Algorithm Input for Expectation-Maximization Initialization (Batch Processing)

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 for Expectation-Maximization Initialization (Batch Processing)

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		The number of starts of the EM algorithm.
nIterations		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 . All elements of the matrix are updated during the processing. diagonal - covariance matrices are stored as numeric tables of size . 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 for Expectation-Maximization Initialization (Batch Processing)

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 -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 numeric tables, each with the variance-covariance matrix for the -th mixture component of size: - for the full covariance matrix storage scheme - 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

Algorithm Input for Expectation-Maximization Computaion (Batch Processing)

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 -th mixture component, where . This input can be an object of any class derived from NumericTable .
inputCovariances	Pointer to the DataCollection object that contains numeric tables, each with the variance-covariance matrix for the -th mixture component of size: - for the full covariance matrix storage scheme - 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 for Expectation-Maximization Computaion (Batch Processing)

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		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		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 . All elements of the matrix are updated during the processing. diagonal - covariance matrices are stored as numeric tables of size . Only diagonal elements of the matrix are updated during the processing, and the rest are assumed to be zero.

Algorithm Output for Expectation-Maximization Computaion (Batch Processing)

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 -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 numeric tables, each with the variance-covariance matrix for the -th mixture component of size: - for the full covariance matrix storage scheme - 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 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.

em_gmm_dense_batch.cpp

EmGmmDenseBatch.java

em_gmm_batch.py

Performance Considerations

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.