A FAST METHOD FOR CALCULATING THE PERCEPTRON WITH MAXIMAL STABILITY

For the class of linearly separable two class (boolean) functions the Perceptron with maximal stability defines in the space of all possible input configurations the direction along which the gap between the two classes is maximal. This solution has several advantages: it is unique, it is robust, and has the best generalization probability among all known linear discriminants. I present here an active set approach to the dual problem, finding the minimal connector between two disjoint convex hulls. If N is the number of the input units and M is the number of examples, this algorithm runs in average O (M N2) steps and requires the storage of a symmetric (N + 3) x (N + 3) matrix.