  


Classification with Guaranteed Probability of Error
Marco C. Campi(marco.campiing.unibs.it) Abstract: We introduce a generalpurpose learning machine that we call the "Guaranteed Error Machine", or GEM, and two learning algorithms, a "real GEM algorithm" and an "ideal GEM algorithm". The real GEM algorithm is for use in real applications, while the ideal GEM algorithm is introduced as a theoretical tool; however, these two algorithms have identical behavior most of the time. Differently from most learning machines, GEM has a ternaryvalued output, that is besides 0 and 1 it can return an "unknown" label, expressing doubt. Our central result is that, under general conditions, the statistics of the generalization error for the ideal GEM algorithm is universal, in the sense that it remains the same, independently of the (unknown) mechanism that generates the data. As a consequence, the user can select a desired level of generalization error and the learning machine is automatically adjusted so as to meet this desired level, and no knowledge of the data generation mechanism is required in this process; the adjustment is achieved by modulating the size of the region where the machine returns the "unknown" label. The keypoint is that no conservatism is present in this process because the statistics of the generalization error is known. We further show that the generalization error of the real algorithm is always no larger than the generalization error of the ideal algorithm. Thus, the generalization error computed for the latter can be rigorously used as a bound for the former, and, moreover, it provably provides tight evaluations in normal cases. Keywords: computational learning theory, guaranteed generalization error, convex optimization, invariant statistics, ternaryvalued classifiers Category 1: Applications  Science and Engineering (DataMining ) Category 2: Linear, Cone and Semidefinite Programming (Semidefinite Programming ) Category 3: Applications  Science and Engineering (Statistics ) Citation: Download: [PDF] Entry Submitted: 03/18/2009 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  