Incremental p-margin algorithm for classification with arbitrary norm. (July 2016)

• Record Type: Journal Article
• Authors: Villela, Saulo Moraes; Leite, Saul de Castro; Fonseca Neto, Raul
• Is Part Of: Pattern recognition. Volume 55(2016:Jul.)
• Page Start: 261
• Page End: 272
• Publication Date: 2016-07
• Subjects: Large margin classifiers -- p-Norm -- Perceptron algorithms -- Binary classification; Pattern perception -- Periodicals; Perception des structures -- Périodiques; Patroonherkenning; 006.4
• DOI: 10.1016/j.patcog.2016.01.016
• Languages: English
• ISSNs: 0031-3203

Abstract

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.