Multi-Class Least Squares Classification at Binary-Classification Complexity
- Creators
- Noumir, Zineb
- Honeine, Paul
- Richard, Cédric
- Others:
- Laboratoire Modélisation et Sûreté des Systèmes (LM2S) ; Institut Charles Delaunay (ICD) ; Université de Technologie de Troyes (UTT)-Centre National de la Recherche Scientifique (CNRS)-Université de Technologie de Troyes (UTT)-Centre National de la Recherche Scientifique (CNRS)
- Laboratoire Hippolyte Fizeau (FIZEAU) ; Université Nice Sophia Antipolis (1965 - 2019) (UNS) ; COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Institut national des sciences de l'Univers (INSU - CNRS)-Observatoire de la Côte d'Azur ; COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Université Côte d'Azur (UCA)-Université Côte d'Azur (UCA)-Centre National de la Recherche Scientifique (CNRS)
- ANR-08-SECU-0013,VIGIRES'EAU,Surveillance en temps réel de la qualité de l'eau potable d'un réseau de distribution en vue de la détection d'intrusions(2008)
Description
This paper deals with multi-class classification problems. Many methods extend binary classifiers to operate a multi-class task, with strategies such as the one-vs-one and the one-vs-all schemes. However, the computational cost of such techniques is highly dependent on the number of available classes. We present a method for multi-class classification, with a computational complexity essentially independent of the number of classes. To this end, we exploit recent developments in multifunctional optimization in machine learning. We show that in the proposed algorithm, labels only appear in terms of inner products, in the same way as input data emerge as inner products in kernel machines via the so-called the kernel trick. Experimental results on real data show that the proposed method reduces efficiently the computational time of the classification task without sacrificing its generalization ability.
Abstract
International audience
Additional details
- URL
- https://hal.archives-ouvertes.fr/hal-01966033
- URN
- urn:oai:HAL:hal-01966033v1
- Origin repository
- UNICA