Les Séparateurs à Vaste Marge
Les noyaux permettent aux méthodes linéaires de proposer des solutions non linéaires. Dans le cas des SVM, l'introduction des noyaux conduit au problème d'optimisation quadratique suivant :
où
est une combinaison linéaire de noyaux
dans l'espace de Hilbert à noyaux reproduisants construit à partir de la fonction noyau choisie.
L'algorithme de résolution de ce problème passe classiquement par la résolution du problème dual (obtenu par le Lagrangien), dans lequel on ne cherche plus une fonction mais un vecteur de multiplicateur de Lagrange de taille
.
Les conditions d'optimalité de ce système, appelée conditions KKT (Kuhn Karuch et Tucker) sont les suivantes :
La résolution de ce problème ce fait en général par une méthode de décomposition appelée SMO. Les méthode d'active set sont aussi particulièrement adaptées. Il faut remarquer que selon les conditions d'optimalité, seuls les points se trouvant sur la marge ou mal classés ont un multiplicateur de Lagrange associé non nul. Parmi les points actifs dans la solution, seuls ceux se trouvant exactement sur la marge nécéssitent le calcul de leur
. Ainsi, l'algorithme peut se résumer à la recherche des trois groupes de points (
,
et
) et on ne résoud le problème quadratique pour pour le groupe
(appelé aussi working set)
La figure ci-après illustre les effets des paramètres sur la forme de la solution d'un SVM. On fait varier ici la largeur de bande (paramètre du noyau gaussien) et la constante de pénalisation des erreurs
.
