Robust classification with feature selection using an application of the Douglas-Rachford splitting algorithm

¹ I3S, Univ. Côte d’Azur & CNRS, F-06900 Sophia Antipolis.
² I3S, Univ. Côte d’Azur & CNRS, F-06900 Sophia Antipolis.

Abstract

This paper deals with supervised classification and feature selection with application in the context of high dimensional features. A classical approach leads to an optimization problem minimizing the within sum of squares in the clusters (I₂ norm) with an I₁ penalty in order to promote sparsity. It has been known for decades that I₁ norm is more robust than I₂ norm to outliers. In this paper, we deal with this issue using a new proximal splitting method for the minimization of a criterion using I₂ norm both for the constraint and the loss function. Since the I₁ criterion is only convex and not gradient Lipschitz, we advocate the use of a Douglas-Rachford minimization solution. We take advantage of the particular form of the cost and, using a change of variable, we provide a new efficient tailored primal Douglas-Rachford splitting algorithm which is very effective on high dimensional dataset. We also provide an efficient classifier in the projected space based on medoid modeling. Experiments on two biological datasets and a computer vision dataset show that our method significantly improves the results compared to those obtained using a quadratic loss function.

Résumé

Ce document traite de la classification supervisée et de la sélection des descripteurs avec application dans le contexte des descripteurs de haute dimension. Une approche classique conduit à un problème d’optimisation minimisant la norme quadratique (norme I₂) avec une pénalite de norme I₁ afin de promouvoir la parcimonie. Il est bien connu que la norme I₁ est plus robuste que la norme I₂ aux valeurs aberrantes. Dans cet article, nous abordons cette question avec une nouvelle méthode proximale pour la minimisation d’un critère utilisant la norme I₁ à la fois pour la contrainte et la fonction de perte. Comme le critèreI₁ n’est que convexe et non gradient de Lipschitz, nous proposons l’utilisation d’une solution de minimisation de type Douglas-Rachford. Nous tirons parti de la forme du critère et, en utilisant un changement de variable, nous fournissons un nouvel algorithme de type Douglas- Rachford dans le primal qui est très efficace dans le contexte des descripteurs de haute dimension. Nous fournissons également un classifieur efficace dans l’espace projeté basé sur la modélisation de medoïds. Des expériences sur des données biologiques et de vision par ordinateur montrent que notre méthode améliore les résultats par rapport à ceux obtenus avec une fonction de perte quadratique.