Optimisation des SVMs par l'algorithme SMO

Résumé du document

Algorithme de décomposition

Osuna a proposé une autre stratégie pour résoudre le problème de programmation quadratique des SVMs. On part du même principe qui consiste à partager le problème de PQ en une série de sous-problèmes. A chaque étape, tant qu'il y a au moins un exemple qui viole les conditions KKT il sera rajouté aux exemples du sous-problème précédent. Dans cette méthode la taille de la matrice est inchangée pour tous les sous-problèmes PQ en impliquant d'ajouter et d'éliminer le même nombre d'exemples à chaque étape. Théoriquement, l'algorithme propose de rajouter et d'éliminer un exemple mais en pratique, les chercheurs rajoutent et éliminent plusieurs exemples en utilisant différentes techniques. A chaque événement, une résolution numérique du problème PQ doit être utilisée (...)

Extraits

[...] où est la sortie fournit par la SVM à l'exemple . Similairement, Au point maximal de l'équation est nulle. Ainsi : En substituant et dans nous obtenons : Une fois est trouvée, il correspond au maximum sans contraintes. Comme il doit être limité par les points limites de la diagonale on utilise : Pour calculer nous utilisons l'équation suivante : qui conduit à : Remarques : Quand on évalue η, la dérivée seconde de utilisant l'équation on trouve qu'elle est nulle quand plus qu'un exemple dans les exemples de la base d'apprentissage ont le même vecteur d'entrée x. [...]

[...] Comment fonctionne l'algorithme SMO ? Rappelons que le problème de programmation quadratique pour entraîner une SVM est décrit par les équations et (54). Ce problème est reformulé en utilisant un Lagrangien tel que : On a deux cas d'optimisation selon que y1 et y2 ont le même signe ou pas. Figure 13 : deux cas d'optimisations Premier cas Deuxième cas S = y1y2 Quand alors et À chaque fois les conditions KKT sont évaluées pour un exemple et quand tous les obéissent à ces conditions alors W atteint son maximum. [...]

[...] SMO décompose le problème de PQ en plusieurs sous-problèmes aussi mais contrairement aux autres méthodes, à chaque étape SMO optimise le plus petit problème possible. Ainsi à chaque étape il optimise deux multiplieurs de Lagrangien (on ne peut pas utiliser un seul multiplieur car on a une contrainte d'égalité linéaire). A chaque étape d'optimisation SMO cherche les valeurs optimales des deux multiplieurs et effectue une mise à jour de la SVM pour donner le reflet des nouvelles valeurs optimisées. Figure 12 : trois méthodes alternatives pour entraîner les SVMs : Chunking, algorithme de Osuna et le SMO. [...]

[...] Soit u1 la réponse de SVM avec les anciennes valeurs de et . (101) Si la nouvelle valeur de est différente de alors la sortie de SVM après l'optimisation sera y1. Donc : (102) Nous déduisons ainsi : (103) De la même manière nous obtenons le seuil b2. (104) Les deux seuils doivent avoir la même valeur comme le montre la figure ci- dessous. Figure 16 : le seuil b quand les deux multiplieurs sont égaux à la bande C : les vecteurs de support λ et β donnent le même seuil b. [...]

[...] Cette heuristique est basée sur la maximisation du pas qui peut être pris lors de l'optimisation. Dans cette étape l'équation est utilisée. On choisit le multiplieur qui permet de donner la plus grande valeur de dans l'équation (83). Rappelons qu'une valeur d'erreur E est déjà calculée pour chaque exemple dont le multiplieur est différent des limites 0 et car c'est à partir de ces exemples que le multiplieur est choisi. Si E1 est positive, l'exemple qui possède la plus petite valeur de E2 est choisi. [...]