Version Space Reduction Based on Ensembles of Dissimilar Balanced Perceptrons

Abstract

A classifier able to minimize the generalization error of a particular problem for any set of unseen samples is named Bayes-optimal classifier. The hypothesis induced by such classifier is equivalent to the optimal Bayes point, which is approximately equivalent to the center of mass of the version space. However, there are only a few methods for estimating the center of mass and most of them are computationally expensive or impractical, especially for large datasets. In this paper we present the Version Space Reduction Machine (VSRM), a new method that obtains an approximation of the center of mass. The method works by means of successive reductions of the version space which are consistent with an oracle's decision. This oracle is represented by the majority voting of an ensemble, whose components must contain a reasonable diversity level to ensure an effective approximation. We conduct an experimental study on microarray datasets and assess the performance of the proposed method compared to Support Vector Machine and Bayes Point Machine. Our method consistently outperforms the others. Such result indicates that the proposed method provides a better approximation of the center of mass.