Perceptron-like large margin classifiers

We consider perceptron-like algorithms with margin in which the standard classification condition is modified to require a specific value of the margin in the augmented space. The new algorithms are shown to converge in a finite number of steps and used to approximately locate the optimal weight vector in the augmented space following a procedure analogous to Bolzano’s bisection method. We demonstrate that as the data are embedded in the augmented space at a larger distance from the origin the maximum margin in that space approaches the maximum geometric one in the original space. Thus, our algorithmic procedure could be regarded as an approximate maximal margin classifier. An important property of our method is that the computational cost for its implementation scales only linearly with the number of training patterns.