Incremental p-margin algorithm for classification with arbitrary norm. (July 2016) - Villela, Saulo Moraes; Leite, Saul de Castro; Fonseca Neto, Raul
Abstract: This paper presents a new algorithm to approximate large margin solutions in binary classification problems with arbitrary q -norm or p -margin, where p and q are Holder conjugates. We begin by presenting the online fixed p -margin perceptron algorithm (FMP p ) that solves linearly separable classification problems in primal variables and consists of a generalization of the fixed margin perceptron algorithm (FMP). This algorithm is combined with an incremental margin strategy called IMA p, which computes an approximation of the maximal p -margin. To achieve this goal, IMA p executes FMP p several times with increasing p -margin values. One of the main advantages of this approach is its flexibility, which allows the use of different p -norms in the same primal formulation. For non-linearly separable problems, FMP p can be used with a soft margin in primal variables. The incremental learning strategy always guarantees a good approximation of the optimal p -margin and avoids the use of linear or higher order programming methods. IMA p was tested in different datasets obtaining similar results when compared to classical L 1 and L ∞ linear programming formulations. Also, the algorithm was compared to ALMA p and presents superior results. Abstract : Highlights: We propose a novel algorithm for large p -margin classification problems, for 1 ≤ p ≤ ∞ . The approach is based on an unified perceptron-based formulation. Soft-margin in primal variables is introduced for non-linearly separable problems. An efficient incremental strategy is used to construct the large p -margin solution.