Introduction au Data Mining
CoursOutils transverses

Séparateurs à Vaste Marge Linéaire

Séparation linéaire

On s'intéresse dans un premier temps au cas de deux classes linéairement séparables, c'est-à-dire qu'il existe au moins une droite (en général, une infinité) expliquant la totalité des données. Dans ce contexte, on se pose la question de trouver la meilleure droite, qui sera définie comme celle qui aura le meilleur pouvoir de généralisation.

Le principe des vastes marges permet d'ajouter des contraintes sur la définition de la droite de telle façon que la solution du problème devient unique. Intuitivement, cela consiste à dire que la meilleure droite parmi toutes celles qui séparent les deux classes est celle qui se trouve le plus loin possible de tous les exemples d'apprentissage (ou encore "au milieu").

DéfinitionVaste marge
Différentes solutions linéaires
Différentes solutions linéaires

Dans les méthodes à vaste marge, on recherche parmi tous les hyperplans discriminants celui qui maximise la marge, c'est-à-dire celui qui se trouve à égale distance des deux classes à séparer. Cette marge se calcule par rapport au points les plus proches de l'hyper plan, ils sont appelés points supports.

SVM Linéaire et marge
SVM Linéaire et marge

L'hyperplan recherché est alors défini par une fonction telle que et telle que les points support répondent à la contrainte (donc ou en fonction de leur classe). Ainsi, on demande à ce que tous les points d'apprentissage se trouve à une distance minimum de de la frontière. Plus formellement, on pose le système à résoudre (problème quadratique donc la solution est unique si elle existe) :

Dans le cas dit non séparable, on introduit une variable de relâchement des contraintes qui permet de tolérer les écarts. En pratique, cela revient à admettre que certains points se trouvent du mauvais côté de leur marge, mais au prix d'une constante qui pénalise la minimisation (cette constante devient un paramètre de la méthode). Le système quadratique à résoudre devient alors :

Les réseaux de neurones (page suivante)Le perceptron (page Précédente)
AccueilImprimerRéalisé avec SCENARI