Adaptive Margin Machines for Classification Learning

In this paper we propose a new learning algorithm for kernel classifiers. Former approaches like Quadratic Programming Machines (SVMs) [11], and Linear Programming Machines [1, 12] were based on minimization of a regularized margin loss where the margin was treated equivalently for each training pattern. We propose a reformulation of the minimization problem such that adaptive margins (AMM) for each training pattern are utilized. Furthermore, we give bounds on the generalization error of AMMs which justify their robustness against outliers. We show experimentally that the generalization error of AMMs is comparable to QP-- and LP--Machines on benchmark datasets from the UCI repository. 1 Introduction Recently, the study of classification learning has shown that algorithms which learn a real--valued function for classification can control their generalization error by making use of a quantity known as the margin. Based on these results, learning machines (SVMs, LP--Machines) which dir..