Part of Advances in Neural Information Processing Systems 9 (NIPS 1996)
Yoram Baram
A classifier is called consistent with respect to a given set of class(cid:173) labeled points if it correctly classifies the set. We consider classi(cid:173) fiers defined by unions of local separators and propose algorithms for consistent classifier reduction. The expected complexities of the proposed algorithms are derived along with the expected classifier sizes. In particular, the proposed approach yields a consistent re(cid:173) duction of the nearest neighbor classifier, which performs "firm" classification, assigning each new object to a class, regardless of the data structure. The proposed reduction method suggests a notion of "soft" classification, allowing for indecision with respect to objects which are insufficiently or ambiguously supported by the data. The performances of the proposed classifiers in predict(cid:173) ing stock behavior are compared to that achieved by the nearest neighbor method.