Version Space Reduction Based on Ensembles of Dissimilar Balanced Perceptrons

Karen Braga Enes, Saulo Moraes Villela, Raul Fonseca NetoIJCAI 2016

Introduction

A fundamental objective in Bayesian machine learning is identifying the "Bayes-optimal" classifier. Theoretically, this classifier corresponds to the center of mass of the version space—the set of all possible hypotheses that correctly classify the training data. Selecting the center of mass minimizes the expected generalization error on unseen data. However, calculating this center in high-dimensional polytopes is computationally intensive and often intractable for large-scale problems.

The Version Space Reduction Machine (VSRM)

To address these challenges, we introduce the Version Space Reduction Machine (VSRM). Unlike Support Vector Machines (SVMs), which approximate the center by finding the largest inscribed sphere, or Bayes Point Machines (BPMs), which rely on complex sampling, VSRM employs an iterative geometric pruning strategy.

Core Components

  1. Variable Margin Perceptron (VMP): Traditional perceptrons stop once any separating hyperplane is found. VMP utilizes dual margin constraints—a lower (inf) and upper (sup) bound—to push the solution away from the version space boundaries and toward its interior.
  2. Iterative Reduction: VSRM uses an ensemble of diverse "Balanced Perceptrons" (EBPd) to act as a decision oracle. The algorithm generates a cutting plane through a feasible point and uses the oracle's majority vote to determine which side likely contains the true center of mass. The less likely half is discarded, effectively "shrinking" the version space toward the optimal point.
Geometric representation of version space reduction using lower (inf) and upper (sup) margin constraints to isolate the center of mass.

The Importance of Ensemble Diversity

The efficacy of VSRM relies heavily on the diversity of its oracle. If ensemble members are too similar, the cutting planes fail to prune the space accurately. By incorporating a dissimilarity measure, the algorithm ensures that the EBPd covers the version space broadly, making the majority vote a robust proxy for the center of mass. This is particularly critical in high-dimensional "small $n$, large $p$" scenarios, such as genomic data, where many valid separating hyperplanes exist.

Comparison of point distributions: clustered data (left) vs. spread data (right). Diverse ensembles are required to robustly navigate the resulting version spaces.

Experimental Evaluation

The VSRM was evaluated against SVM and BPM using six DNA microarray datasets (e.g., Prostate, Leukemia, Breast). These datasets are characterized by a low number of samples (24–102) and a massive number of features (up to 12,600).

  • Performance: VSRM outperformed both BPM and SVM in 5 out of 6 datasets. For instance, on the Breast dataset, VSRM achieved a mean error of 19.83%, compared to 20.67% for SVM.
  • Statistical Significance: A Friedman Rank Sum test yielded a p-value of approximately 0.042, confirming the performance gains are statistically significant at the 5% level.
  • Efficiency: Unlike methods that stack constraints, VSRM updates margin constraints, maintaining computational efficiency even as the search narrows.

Conclusion and Future Work

VSRM provides a computationally efficient geometric approach to approximating the Bayes-optimal classifier. By iteratively reducing the version space through a diverse ensemble oracle, it achieves superior generalization on difficult high-dimensional datasets. Future research will focus on extending VSRM to non-linear classification via kernel methods and exploring alternative ensemble configurations to further refine the center-of-mass approximation.

Summary updated

BibTeX
@inproceedings{enes2016version,
  author = {Karen Braga Enes and Saulo Moraes Villela and Raul Fonseca Neto},
  title = {{Version Space Reduction Based on Ensembles of Dissimilar Balanced Perceptrons}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
}
Figure