1 Introduction
In the last ten years machine-learning classifiers have b een applied to various
classification problems [5]. Nevertheless, almost no classifiers have b een employed
in real applications, esp ecially in critical domains. The main reason is that it is
difficult to determine whether a classification assigned to a particular instance is
reliable or not.
There are several approaches to classification reliability. They first estimate
some parameter(s) that are related to classification reliability. Then, the approaches learn a threshold on that parameter(s) to decide whether an instance
classification is reliable. The oldest approach used the p osterior probability of the
predicted class as a reliability parameter [3]. Unfortunately, this rather simple approach assumes an underlying distribution of the data, which is generally unknown
[6]. Newer approaches are based on the theory of randomness (cf. [5, 8, 10]). The
key idea is to classify a new instance so that when the instance is added to the
training data, the data show a level of randomness that is close to the level of randomness of the same data b efore the instance was added. The reliability parameter
is inversely prop ortional to the difference b etween the two levels of randomness.
In this pap er we prop ose a new approach to classification reliability. In contrast
to the previous approaches, ours is not based on classification-reliability parameter(s) and thus do es not require learning any thresholds.
The approach is applicable for binary classifiers. The key idea assumes that
we can maintain version spaces [7, 11] containing (close approximations of ) the
target classifiers. If the assumption is correct for the training data under consideration, the classification rule of unanimous voting applied on these version spaces
guarantees that the classification assigned to each instance is reliable.