Math: Linéarité or not linéarité

Un petit aparté avant de traiter l’astuce du noyau et son utilisation dans les SVM pour parler de la linéarité et de la non linéarité.

Principe de la linéarité

Des données sont dites linéaires lorsqu'il est possible de construire un modèle de ces données en s’appuyant sur une équation linéaire. Pour rappel, une équation linéaire est une équation du type:
TODO Généralisable en dimension n sous la forme:
TODO Que l’on peut réécrire sous forme matricielle:
TODO Souvent c’est à partir de la que l’on va appliquer les algorithmes de machine learning afin de rechercher les paramètres W optimaux à partir d’un jeu de données (mais cela on l’a vu dans les articles précédents en minimisant la distance des points à la moyenne par exemple où avec l'équation normale).

Pourtant, si les SVM sont une approche de machine learning efficace pour la classification ou la régression sur des ensembles de données linéaires (ou linéairement séparable) cet outil n’est pas adapté à une utilisation sur des ensembles de données non linéaire ou du moins pas directement.

Mais qu’est ce que l’on appel des données non-linéaires ?

La non linéarité

La non linéarité du coup c’est le reste! Ok merci au revoir….

Non, bon ok, ça parait un peu facile dit comme ça mais en fait ça se limite vraiment à ça! Donc ca signifie que toute construction à base d’exponentielle, de logarithme, de passage à la puissance ou faisant intervenir une quelconque dérivée est non linéaire. il en existe bien d’autre forme, les pire étant les systèmes chaotique (mais nous n’irons pas ici jusqu'à la).

Mais cela parait assez vite logique lorsque l’on observe un peu ces fonctions car elles ont un profil typiquement non linéaire. Par exemple les fonctions exp, log et x à différents niveau de puissances



Mais du coup on en fait quoi de la non linéarité? Et bien c’est un sujet difficile qu’il faut appréhender un peu cas par cas car chaque non linéarité peut être issue de mécanisme varié.

Cependant en machine learning, il existe une approche efficace qui permet de ramener un problème non linéaire (pas chaotique) en un problème linéaire, c’est l’utilisation du kernel-trick! Rien que ça…. mais on en parlera dans le prochain article.

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

IA : Obtention de l'equation normale

En machine learning, nous cherchons un modèle. Dans le cas d’un nuage de point pour lequel nous avons que son profil est linéaire, nous allons rechercher un modèle de la forme
TODO Ce modèle une fois obtenu, va nous permet de fournir des prédictions. Seulement, encore faut il en déterminer le paramétrage.

Pour cela on peut utiliser l'équation normale que nous avions vu dans l’article [1]:
TODO Du coup comme il importe d’en comprendre l’origine, explorons son origine: la méthode des résidus.

En fait l’idée est simple l'équation du modèle linéaire que nous avons vu précédemment nous fourni un modèle linéaire mais qui forcément ne sera pas parfait. Ainsi, si l'équation normale nous donne un résultat optimal en terme de régression (par exemple), si l’on compare les valeurs prédites avec les valeurs initiales, on va faire apparaître ce que l’on pourrait apparaître comme un résidu:
TODO À partir de ce constat, il faut que nous cherchions donc une solution permettant de minimiser les résidus. Pour cela, on va en calculer le produit scalaire c’est à dire: TODO Ensuite on décompose:

TODO Or on peut trouver l'équivalence suivante:
TODO Du coup en réintroduisant ce résultat dans l'équation on obtient:
TODO Il s’agit d’une forme quadrative avec du type avec la solution associé (l’équation du modèle linéaire)
TODO Donc notre calcule des residus nous amene à l’equation normale
TODO Voila en allant chercher la valeur minimale c’est à dire la solution l’équation quadrative, alors on retrouve l’équation normale.

Réferences

[1] https://un-est-tout-et-tout-est-un.blogspot.com/2018/09/ia-equation-normale.html

IA : Chemin vers le kernel trick

Quand tu fais face a Dunning, Kruger.... tu prends conscience de ton ignorance et du travail qu'il te reste a accomplir....

Cette semaine ça a été mon quotidien. J'ai du temps et je me suis dit, et bien pourquoi ne pas s’intéresser plus précisément aux modèles de machines learning permettant de réaliser des classification ou des régressions non linéaire? En toute logique, forcement je me suis pencher sur les SVM....

Alors bien sur ce sujet avait été traité de façon technique avec scikit-learn [2] sans se préoccuper des fondamentaux mathématiques qui se cachaient derrières... et conscient des explications faisaient défaut.

J'ai donc voulu remplir le vide.... seulement en m'intéressant aux SVM dans le cadre des problèmes de la non linéarité, on se rend vite compte qu'il s'agit d'un faux problème car il existe un outil mathématique magique (mathemagique?) qui permet de passer d'un espace de description  non linéaire a un espace linéaire : le kernel trick! et en plus cerise sur le gâteau, il permet de ne pas avoir a se poser de question sur la fonction permettant cette transformation, celle ci étant dans le noyau et que ce dernier s'applique directement! Du coup un bon choix de noyau et op, on est capable d'appliquer un SVM (qui est très efficace sur les problèmes linéaires).

Mais du coup forcement outil aussi cool que le kernel trick devait aussi etre compris et surtout pourquoi il marche!

Alors le kernel trick fonctionne car dans les équations solutions (équation dual de la forme quadratique de minimisation de la norme du vecteur de poids) du SVM, existe un produit scalaire des données d'entrées d'entrainement. Ce produit scalaire est justement l'astuce du noyaux car il autorise sa substitution avec le noyau choisi (grâce au théorème de Mercer).

A ce stade, on se rend compte qu'il y a encore des choses a expliquer.... que fait réellement le kernel trick (ou du moins qu'est ce qu'il permet de cacher?) Pourquoi avons nous une solution de minimisation des poids du modèle sous une forme quadratique?

Voila donc tout ceci pour expliquer la complexité d'un sujet que même si compris implicitement dans le survol,  il est souvent nécessaire en réalité de fournir un travail plus en profondeur pour en maîtriser réellement les tenant et aboutissant (comprenant les concepts mathématiques dans l'ombre).

Donc ce que nous allons faire c'est:

• Expliquer comment on obtient l’équation normale
• Comment a partir de l’équation normale, on obtient la forme duale
• Identifier le kernel trick et son fonctionnement
• Application de kernel trick a autre chose que SVM

Bon ok c'est probablement pas l'article que vous attendiez mais... au plus je me suis intéressé au sujet et au plus il m'a semblé nécessaire d'en écrire plusieurs.... il me fallait éclaircir la démarche, d'ou cet article...

Références

[1] https://fr.wikipedia.org/wiki/Effet_Dunning-Kruger
[2] https://un-est-tout-et-tout-est-un.blogspot.com/2018/12/ia-classification-svc-avec-scikit-learn.html