Classifieur linéaire
En apprentissage automatique, les classifieurs linéaires sont une famille d'algorithmes de classement statistique. Le rôle d'un classifieur est de classer dans des groupes (des classes) les échantillons qui ont des propriétés similaires, mesurées sur des observations. Un classifieur linéaire est un type particulier de classifieur, qui calcule la décision par combinaison linéaire des échantillons.
Terminologie
modifier« Classifieur linéaire » est une traduction de l'anglais linear classifier. En français, selon les pays, les communautés et les personnes, ce terme peut être remplacé par discrimination linéaire, ou apprentissage de surface séparatrice linéaire. Pour les statisticiens, ces méthodes sont parfois classées en tant que méthodes d'analyse discriminante.
Définition
modifierPour un vecteur d'observation x, à valeur dans , la sortie du classifieur est donnée par :
où est un vecteur de poids, est le biais, et f est une fonction qui convertit le produit scalaire des deux vecteurs dans la sortie désirée. Le vecteur de poids w est appris à partir d'un ensemble d'apprentissage étiqueté. La fonction f est souvent une simple fonction de seuillage, par exemple la fonction signe, la fonction de Heaviside, ou des fonctions plus complexes comme la tangente hyperbolique, ou la fonction sigmoïde. Une fonction de décision plus complexe pourrait donner la probabilité qu'un certain échantillon appartienne à une certaine classe.
Pour un problème de discrimination à deux classes, l'opération réalisée par un classifieur linéaire peut se voir comme la séparation d'un espace de grande dimension par un hyperplan : tous les points d'un côté de l'hyperplan sont classés en tant que 1, les autres sont classés en tant que -1. Cet hyperplan est appelé hyperplan séparateur, ou séparatrice.
Les classifieurs linéaires sont souvent employés dans les situations où une faible complexité est souhaitée, car ce sont les classifieurs les plus simples et donc les plus rapides, surtout lorsque le vecteur d'observation x est creux. Toutefois, les méthodes d'arbre de décision peuvent s'avérer plus rapides encore.
Les classifieurs linéaires obtiennent souvent de bons résultats lorsque N, le nombre de dimension de l'espace des observations, est grand comme dans la fouille de textes, où chaque élément de x est le nombre de mots dans un document.
Modèle génératif vs. modèle discriminant
modifierIl existe deux grandes familles de méthodes pour estimer les paramètres du vecteur d'un classifieur linéaire[1],[2].
La première consiste à modéliser les probabilités conditionnelles soit . On parle de modèles génératifs. Des exemples d'algorithmes de ce type sont :
- Analyse discriminante linéaire (ou discriminant linéaire de Fisher, LDA) : implique l'existence d'un modèle discriminant basé sur une distribution de probabilité de type Gaussienne.
- Classifieur bayesien naïf : implique une distribution de probabilité conditionnelle de type binomiale.
La seconde famille d'approche qui regroupe les analyses par modèle discriminant, cherche d'abord à maximiser la qualité de la classification sur un jeu de test. Dans un second temps, une fonction de coût va réaliser l'adaptation du modèle de classification final (en minimisant les erreurs). Quelques exemples d'entrainement de classifieurs linéaires par méthode discriminante :
- Régression logistique : un estimateur de maximum de vraisemblance est évalué d'après , en considérant que le jeu d'entrainement a été généré par un modèle binomial.
- Perceptron : un algorithme qui cherche à corriger toutes les erreurs rencontrées dans le jeu d'entrainement (et ainsi améliorer l'apprentissage et le modèle créé d'après ce jeu d'entrainement).
- Machine à vecteurs de support (SVM) : un algorithme qui maximise la marge des hyperplans séparateurs du classifieur en utilisant le jeu d'entrainement pour son apprentissage.
On considère généralement que les modèles entraînés par une méthode discriminante (SVM, Régression logistique) sont plus précis que ceux de type génératifs entraînés avec des probabilités conditionnelles (classifieur bayésiens naïfs ou linéaires). On considère que les classifieurs génératifs sont plus adaptés pour les processus de classification avec nombreuses données manquantes (par exemple la classification de texte avec peu de données d'apprentissage)[réf. nécessaire].
Tous les classifieurs linéaires cités peuvent opérer sur des données non linéairement séparables en opérant sur un espace de représentation transformé avec l'astuce du noyau. Cette technique consiste à appliquer une transformation aux données d'entrées pour trouver un hyperplan séparateur optimal dans un nouvel espace de grande dimension dans lequel elles sont projetées.
Notes et références
modifierVoir aussi
modifierArticles connexes
modifierBibliographie
modifier- (en) Richard O. Duda, Peter E. Hart, David G. Stork, Pattern Classification, Wiley-interscience, (ISBN 0-471-05669-3) [détail des éditions]
- (en) Tom M. Mitchell, Machine Learning, [détail des éditions]