Technical Report CIS9627

Title: Consistent Classification, Firm and Soft
Authors: Yoram Baram
PDFNot Available
Abstract: A classifier is called {\em consistent} with respect to a given set of class-labeled points if it correctly classifies the set. We consider classifiers defined by unions of local separators (e.g., polytopes) 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 reduction of the nearest neighbor classifier, resolving unanswered questions raised by Hart [19] with respect to the complexity of the condensed nearest neighbor method. Our analysis shows that an objection to the utility of Occam's razor in classification, recently raised by Webb [30] on experimental grounds, is theoretically justified. The nearest neighbor classifier and its consistent derivatives perform ``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. We define a {\em benefit" function, which translates into profit in an economic context, as the difference between the probability of a correct decision and that of an incorrect one, and show that, under a certain condition on the indecision rate, a soft classifier can produce a higher benefit than a firm classifier. Spherical local separators are shown to offer certain advantages in soft classification over multi-linear local separators. The performances of the proposed classifiers in predicting stock behavior are compared to that achieved by the nearest neighbor method and the utility of soft classification is demonstrated.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CIS technical reports of 1996
To the main CS technical reports page

Computer science department, Technion