Introduction
This paper introduces a Bayesian approach to feature selection that goes beyond ranking individual variables to calculate the probability of entire input subsets. By utilizing Reversible Jump Markov Chain Monte Carlo (RJMCMC) sampling, the proposed classifier can "jump" between different combinations of features. This provides a nuanced, probabilistic view of which groups of variables best explain the underlying data.
The Challenge of Input Selection
In machine learning, input (or feature) selection is the critical process of identifying which variables are genuinely useful for making predictions. Traditional methods typically fall into two categories:
- Search Algorithms: These attempt to find the single "best" subset of features but often ignore other subsets that might be nearly as effective.
- Automatic Relevance Determination (ARD): A Bayesian technique that uses hierarchical priors to shrink the weights of irrelevant features toward zero. While powerful, ARD evaluates features individually rather than assessing the synergistic effects of subsets.
The primary challenge is combinatorial explosion: as the number of possible inputs grows, the number of potential subsets increases exponentially, making exhaustive testing impossible. This paper addresses the need for a method that efficiently explores this "subset space" to find a probability distribution over all plausible explanations, rather than just a single point estimate.
A Bayesian RJMCMC Approach
The author constructs a classifier based on Radial Basis Functions (RBF), specifically modeling class-conditional densities as a mixture of Gaussians. To perform inference, a hybrid MCMC sampler is employed, consisting of two main components:
- Gibbs Sampling: Used for "fixed-dimension" updates. When the set of inputs is held constant, the sampler updates the model's internal coefficients (means, variances, and mixing weights) using standard conjugate priors.
- Reversible Jump MCMC (RJMCMC): This mechanism allows the model to dynamically change its own dimensionality. It employs three types of moves:
- Birth: Randomly adding a new input feature to the model.
- Death: Randomly removing an existing input feature.
- Exchange: Swapping one active feature for an inactive one, helping the sampler "tunnel" through low-probability regions.
To prevent overfitting, the model uses a truncated Poisson prior on the number of inputs, penalizing overly complex models and ensuring the sampler favors parsimonious explanations.
Key Insights: Subsets Over Individuals
A major takeaway from this research is that feature relevance is highly contextual. A feature might appear useless on its own but become highly informative when paired with another. By sampling entire subsets, this method successfully captures these inter-variable dependencies.
Instead of relying on a standard neural network architecture, the author treats classification as a density estimation problem. By modeling the distribution of the data itself, calculating the Bayesian evidence for different input subsets becomes more tractable. Furthermore, the method provides a quantifiable measure of uncertainty. Unlike "black box" selectors, it generates a histogram of visited subsets. For instance, on the Ionosphere data, the sampler visited about 500 different subsets within 10,000 samples, revealing exactly which combinations (e.g., features [7, 14] at 9.1% probability) were most likely.
Experimental Results
The method was evaluated using three classic datasets: Ionosphere (33 inputs), Wine Recognition (13 inputs), and Pima Indians Diabetes (8 inputs).
- Parsimony by Design: The results for the high-dimensional Ionosphere dataset were particularly striking. Despite having 33 available inputs, the model found that, on average, only 4.3 inputs were necessary to achieve high accuracy. This strongly suggests that many real-world datasets are significantly over-determined.
- Competitive Accuracy: The RJMCMC-RBF method achieved classification accuracy comparable to the then-state-of-the-art MLP-ARD (Multi-Layer Perceptron with Automatic Relevance Determination). It reached 91.5% accuracy on the Ionosphere dataset and 100% on the Wine dataset.
- Automated Dimensionality Reduction: The model successfully ignored the vast majority of irrelevant inputs, effectively performing automated feature engineering during the training process.
Limitations and Future Directions
While powerful for interpretation, the author notes that the approach did not significantly outperform MLP-ARD in terms of raw classification error; its primary value lies in subset analysis and interpretability. Additionally, MCMC methods—especially Reversible Jump variants—are computationally expensive and require careful tuning of proposal distributions. Finally, while effective on datasets with up to 33 inputs, scaling this sampler to modern problems with thousands of features remains a daunting challenge due to the exponentially larger subset space.
Summary updated