K-Version-Space Multi-Class Classification Based on K-Consistency Tests

Abstract

k -Version spaces were introduced in [6] to handle noisy data. They were defined as sets of k -consistent hypotheses; i.e., hypotheses consistent with all but k instances. Although k -version spaces were applied, their implementation was intractable due to the boundary-set representation. This paper argues that to classify with k -version spaces we do not need an explicit representation. Instead we need to solve a general k -consistency problem and a general k 0-consistency problem. The general k -consistency problem is to test the hypothesis space for classifier that is k -consistent with the data. The general k 0-consistency problem is to test the hypothesis space for classifier that is k -consistent with the data and 0-consistent with a labeled test instance. Hence, our main result is that the k -version-space classification can be (tractably) implemented if we have (tractable) k -consistency-test algorithms and (tractable) k 0-consistency-test algorithms. We show how to design these algorithms for any learning algorithm in multi-class classification setting.