SVM : Formule dual

Cet article sera court car il n’entrera pas dans le détail de l’obtention de l'équation dual mais juste dans l’explication de comment y parvenir en partant de la fonction de décision (où le modèle de régression. L’idée n’est pas d’entrer trop dans les détails mathématiques que d’une part je ne maîtrise pas forcement mais d’intègrer cet article dans la continuité des sujet sur SVM et finalement aboutir aux modèles SVM non linéaire. Pour plus de détails la littérature sur le sujet est vaste, en dehors de ressources de type cours de math de master, vous trouverez les articles suivant qui m’ont permis de mieux appréhender cette problématique [1,2,3].

Pour rappel cette fonction solution à notre problème est [6]:
TODO Dans ce cadre, le but est de maximiser la marge qui dans le cas de la SVM est inversement proportionnel à la norme de W par deux
TODO Pour faire plus simple, alors on propose de plutôt minimiser directement la norme de W. Que l’on préférera choisir sous la forme de (½)W^^2
TODO

Formule primal

Ainsi, la SVM devient un problème d’optimisation quadratique avec contrainte dans laquelle, on cherche:
TODO sous la contrainte
TODO A noter que cette contrainte dépend du type de modèle : régression ou classification

Ce problème est alors ce que l’on appelle le problème primal.

Ce qu’il faut savoir est que la solution à ce “facile” à la condition que le nombre de données soit conséquent par rapport au nombre de variable (rang(X)). Par contre lorsque le nombre de données devient equivalent au nombre de variable voir est inferieur, cette solution n’est plus efficace et il faut alors se tourner vers la solution duale.

Formule dual

Cette solution duale qui est le propos de cet article s’obtient à l’aide du multiplicateur de agrange [4,5] qui nous permettre de la reformuler la solution primale sous la forme suivante.
TODO avec
TODO et
TODO A noter que ce dernier element étant associée à la contrainte de la formule primale, il faut l’ajuster selon le type de modèle : classification ou régression. On obtient donc:
TODO L’utilisation des conditions Kuhn-Tucker à cette étape vont alors nous permettre en calculant de gradient de L de nous fournir la formule duale (au coef prés du type de modèle) qu’il faudra maximiser selon le paramètre alpha.
TODO L’intéret de cette approche est de fournir à l’inverse de la solution primale une solution adapté au calcule des W dans le cas ou le nombre de données est faible face au nombre de variable. Pour plus d’informations afin d’approfondir, je vous invite à consulter la formation [1] qui explique le rôle de alpha qui selon sa valeur permet d’identifier le rôle des vecteurs du support à la marge du SVM.

Enfin dernier intérêt de la formule duale sur la formule primale, comme nous le verrons dans les articles suivant, est que celui ci fait intervenir un produit scalaire…. mais nous verrons cela plus tard.

Références

[1] https://openclassrooms.com/fr/courses/4444646-entrainez-un-modele-predictif-lineaire/4507841-maximisez-la-marge-de-separation-entre-vos-classes
[2] https://zestedesavoir.com/tutoriels/1760/un-peu-de-machine-learning-avec-les-svm/#5-systemes-non-lineaires--astuce-du-noyau
[3] https://fr.wikipedia.org/wiki/Machine_%C3%A0_vecteurs_de_support
[4] https://fr.wikipedia.org/wiki/Multiplicateur_de_Lagrange
[5] https://fr.wikipedia.org/wiki/Optimisation_quadratique
[6] https://medium.com/coinmonks/support-vector-regression-or-svr-8eb3acf6d0ff