Incremental p -margin algorithm for classification with arbitrary norm

Autor: Saul C. Leite, Raul Fonseca Neto, Saulo Moraes Villela
Rok vydání: 2016
Předmět:
Zdroj: Pattern Recognition. 55:261-272
ISSN: 0031-3203
DOI: 10.1016/j.patcog.2016.01.016
Popis: 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 (FMPp) 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 IMAp, which computes an approximation of the maximal p-margin. To achieve this goal, IMAp executes FMPp 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, FMPp 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. IMAp was tested in different datasets obtaining similar results when compared to classical L1 and L ∞ linear programming formulations. Also, the algorithm was compared to ALMAp and presents superior results. HighlightsWe 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.
Databáze: OpenAIRE
Externí odkaz: