Maximum Likelihood Estimation of Mixture Densities for Binned and Truncated Multivariate Data

Igor V. Cadez, Padhraic Smyth, Geoffrey J. McLachlan, Christine E. McLarenMachine Learning 2002 · DOI · OpenReview

Introduction

In many empirical fields, researchers often lack access to raw, individual data points. Instead, data is frequently encountered in binned formats, such as histograms or cytograms, where only the frequency counts within specific intervals are known. Furthermore, this data is often truncated, meaning observations outside a certain sensor range are lost entirely. While methods for fitting mixture models to univariate binned data are well-established, extending these to multivariate spaces presents a significant computational challenge known as the "curse of dimensionality."

This paper introduces a generalized Expectation-Maximization (EM) algorithm designed to recover underlying probability densities from coarse, truncated multivariate histograms. By optimizing numerical integration and initialization strategies, the authors demonstrate that high-fidelity density estimation is possible even with limited data resolution.

Overcoming the Computational Hurdle

The primary difficulty in fitting mixture models to multivariate binned data lies in the E-step of the EM algorithm. To update model parameters, one must calculate multidimensional integrals over every single bin in the grid. For a standard $100 \times 100$ grid, this requires 10,000 integrals per iteration, leading to prohibitive processing times.

To address this, the authors propose a three-pronged approach:

  1. Multivariate EM Framework: They treat the exact locations of points within bins and the counts in truncated regions as "missing data," deriving the necessary E-step and M-step equations for the multivariate case.
  2. Optimized Numerical Integration: The algorithm utilizes Romberg integration. To accelerate the process, a "fast integration" heuristic is introduced: bins with a probability mass below a threshold $\epsilon$ are processed using a single-iteration integrator, significantly reducing computation with negligible accuracy loss.
  3. Strategic Initialization: To avoid the high cost of running the binned EM from scratch, the model is initialized by drawing a small, jittered random sample from the bins and running a standard, "cheap" EM. This places the parameters near the global maximum before the more intensive binned algorithm begins.

Real-World Application: Red Blood Cell Analysis

The practical utility of this approach is demonstrated using a Red Blood Cell (RBC) dataset. This dataset consists of blood samples from 172 subjects—90 healthy controls and 82 patients with iron deficiency anemia. Each sample contains approximately 40,000 RBC measurements of volume and hemoglobin concentration.

A 3D cytogram representing binned red blood cell data, showing the relationship between volume and hemoglobin concentration.

As shown in the figure above, the data is provided as $100 \times 100$ binned "cytograms." The proposed algorithm allows for the precise estimation of the mixture density underlying these histograms, accounting for the truncation at the edges of the sensor range.

Key Insights and Results

The authors' experiments yielded several critical insights into the nature of binned data:

  • The "Plateau" Effect: Accuracy in density estimation does not increase indefinitely with bin resolution. The authors found that once a grid reaches approximately 10–20 bins per dimension, the performance plateaus, suggesting that relatively coarse histograms are sufficient for complex modeling.
  • Truncation Sensitivity: Results indicate that truncation (losing data at the tails) is significantly more detrimental to model accuracy than binning (losing precision within the grid). The algorithm's ability to explicitly model these missing regions is a key advantage.
  • Diagnostic Performance: When the parameters derived from the binned mixture model were used as features for classification, a hierarchical mixture model achieved a cross-validated error rate of 1.65% in diagnosing anemia. This significantly outperformed traditional decision tree classifiers like C5.0 (3.62%) and CART (4.65%).

Conclusion

By leveraging the sparsity of multivariate histograms and employing efficient numerical techniques, this research makes multivariate density estimation from binned data computationally feasible. While the approach is currently best suited for low-dimensional spaces (2D to 5D), it provides a robust framework for medical diagnostics and other fields where raw data is inaccessible.

Summary updated

Abstract

Binning and truncation of data are common in data analysis and machine learning. This paper addresses the problem of fitting mixture densities to multivariate binned and truncated data. The EM approach proposed by McLachlan and Jones (Biometrics, 44: 2, 571–578, 1988) for the univariate case is generalized to multivariate measurements. The multivariate solution requires the evaluation of multidimensional integrals over each bin at each iteration of the EM procedure. Naive implementation of the procedure can lead to computationally inefficient results. To reduce the computational cost a number of straightforward numerical techniques are proposed. Results on simulated data indicate that the proposed methods can achieve significant computational gains with no loss in the accuracy of the final parameter estimates. Furthermore, experimental results suggest that with a sufficient number of bins and data points it is possible to estimate the true underlying density almost as well as if the data were not binned. The paper concludes with a brief description of an application of this approach to diagnosis of iron deficiency anemia, in the context of binned and truncated bivariate measurements of volume and hemoglobin concentration from an individual's red blood cells.
BibTeX
@article{cadez2002maximum,
  author = {Igor V. Cadez and Padhraic Smyth and Geoffrey J. McLachlan and Christine E. McLaren},
  title = {{Maximum Likelihood Estimation of Mixture Densities for Binned and Truncated Multivariate Data}},
  journal = {Machine Learning},
  year = {2002},
  doi = {10.1023/a:1013679611503},
}
Figure