Bayesian Treatment of Incomplete Discrete Data Applied to Mutual Information and Feature Selection

Marcus Hutter, Marco Zaffalon

Abstract

This paper presents a unified Bayesian framework for estimating Mutual Information (MI) from incomplete discrete datasets. By proving the unimodality of the posterior distribution under Dirichlet priors, the authors guarantee the global convergence of the Expectation-Maximization (EM) algorithm. Furthermore, they derive efficient analytical approximations for the posterior distribution of MI, enabling the development of robust feature selection filters—the Forward and Backward Filters—that adaptively handle data scarcity and uncertainty more effectively than traditional empirical methods.

Introduction

In machine learning, practitioners frequently encounter "incomplete" data where features or class labels are missing. Traditionally, this challenge is addressed through two distinct lenses: Bayesian treatments, which use prior distributions to account for uncertainty, and the Expectation-Maximization (EM) algorithm, which iteratively finds maximum likelihood estimates.

A significant gap exists when calculating Mutual Information (MI), a standard measure for feature selection. Empirical MI calculations often ignore the reliability of the estimate; for instance, a feature might appear highly informative due to chance in a small or sparse dataset. This research bridges the gap by providing a Bayesian approach to estimate the distribution of MI, offering credible intervals and a measure of confidence even when data is missing.

Theoretical Framework: Unimodality and EM

The authors model the joint probabilities of discrete variables using Dirichlet priors. A core technical contribution of this work is the proof that the log-likelihood function for this problem is concave. This result is significant because it guarantees that the EM algorithm will always converge to the global maximum within this framework, rather than becoming trapped in local optima. This mathematical certainty simplifies the optimization process and ensures the reliability of the resulting estimates.

Analytical Approximations

To maintain computational efficiency, the authors move away from expensive Markov Chain Monte Carlo (MCMC) simulations. Instead, they derive closed-form, leading-order approximations ($O(1/N)$) for the mean, mode, and variance of the chances and the resulting MI. With a complexity of $O(rs)$—where $r$ and $s$ represent the number of states for the variables—these calculations are fast enough for incremental, real-time learning tasks.

Robust Feature Selection Filters

Using the posterior distribution, the paper introduces two new filtering mechanisms for feature selection:

  1. Backward Filter (BF): This filter only discards a feature if there is strong evidence that its MI is below a predefined threshold.
  2. Forward Filter (FF): This filter only includes a feature if there is strong evidence that its MI is above a threshold.

The Forward Filter is particularly innovative because it is self-adapting. Early in the learning process, when data is scarce and variance is high, the filter is cautious. As more data is processed and the variance of the MI estimate decreases, the "effective threshold" for inclusion automatically lowers, allowing the system to become more confident in its selections.

Experimental Evaluation

The researchers evaluated their approach using five incomplete datasets from the UCI Repository: Audiology, Crx (Credit Approval), Horse-colic, Hypothyroidloss, and Soybean-large. These datasets featured varying degrees of missing values, ranging from 67 to over 2,300 missing entries.

Key Results

  • Feature Efficiency: The Forward Filter (FF) consistently selected fewer features than traditional empirical filters. In the Hypothyroidloss dataset, the FF used an average of 4.3 features, whereas the traditional filter required 8.3.
  • Predictive Accuracy: On the Hypothyroidloss set, the FF significantly outperformed the traditional filter, achieving an accuracy of 0.986 compared to 0.930 at a peak observation point.
  • Robustness: Across the remaining datasets, the FF achieved accuracy comparable to traditional methods while utilizing a smaller, more reliable subset of features.

Conclusion and Future Directions

This research demonstrates that a Bayesian treatment of incomplete data provides a more robust foundation for feature selection than empirical methods. By proving unimodality and deriving efficient approximations, the authors have created a framework that is both mathematically sound and computationally practical.

While the current study assumes the missing-data mechanism is "ignorable" (Missing At Random), future work could extend this framework to non-random missing data scenarios. Additionally, the authors suggest applying these Bayesian principles to more complex structures, such as the robust inference of Bayesian networks or classification trees from incomplete data.

Summary updated

BibTeX
@inproceedings{hutter2003bayesian,
  author = {Marcus Hutter and Marco Zaffalon},
  title = {{Bayesian Treatment of Incomplete Discrete Data Applied to Mutual Information and Feature Selection}},
  booktitle = {KI},
  year = {2003},
  doi = {10.1007/978-3-540-39451-8\_29},
}
Figure