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

Math: Analyse des données

L’analyse des données consiste à extraire des informations supplémentaires à celles-ci. Elle peut mener à découvrir des choses aussi bien spécifique en faisant apparaître des cas particulier mais aussi des choses générales et transverses.  Bien sur, on ne peut demander le même genre d’informations selon le type de données que l’on observe mais on peut dégager des tendances.

Analyse de données quantitatives

Les données quantitatives sont les plus évidente à analyser car celles ci se prêtent bien aux analyses statistiques. On utilisera donc naturellement des outils comme la moyenne [1], la variance [2], l'écart-type [2] ou encore la médiane [3].

Math: La nature des données

Jusqu'à maintenant nous nous somme intéressé comment construire un outil capable de soit prédire des données futurs (avec des modèles de régression) soit prédire l’association de celle ci avec des ensembles divers (classification)

Ces deux types de modèles sont en fait typique de la nature des données manipulées ou de la nature des données de sorties souhaitées, ici respectivement des données quantitatives et qualitatives [1,2].

Python : Les Coroutines

Je vous avais promis des aspects technologiques sur python et l’utilisation de quelques librairies intéressantes, et bien c’est loupé, initialement je voulais voir les coroutines en même temps que le décorateurs [decorateur] , mais finalement je les aies séparés. Donc nous revoilà avec un autre article sur cette petite spécificité du langage [pep-342].

Vous vous souvenez du mots clefs yield? C’est celui la que nous utilisions dans les générateurs pour produire des résultats sans interrompre le déroulement du contexte d'exécution… c'était assez magique… à bien sachez qu’il est aussi possible de lui envoyer des données en contre partie…. dur à imaginer…. effectivement…Prenons un exemple:

Python : Les décorateurs

Bien nous voilà maintenant encore un nouveau sujet Python, les décorateurs ! Alors promis c’est le dernier! (ou presque) parce qu'après on s'intéressera à des aspects plutôt technologique de python plutôt que des subtilités du langages…

On va donc tâcher de faire court afin de ne pas lasser!

Les décorateurs

Vous connaissez le pattern décorateur ? et bien c’est un peu la même idée sauf que dans notre cas le but est de faire plutôt comme le pattern Proxy…

Quoi? Vous comprenez pas? Ok faisons un parallèle avec Java… Dans Java lorsque l’on dispose d’une classe comportant certains comportement mais que ces derniers ne suffisent pas, on peut employer ce que l’on appelle un proxy [pattern-prox].

Dans le principe le proxy va prendre en paramètre l’objet que l’on souhaite décorer et s’enregistrer auprès de ce dernier afin de déclencher l’une de ses méthodes en lieu et place de l’objet en lui même. Alors bien sûr, souvent on joue quand même la méthode de l'objet mais celui ci on ajoute quelques comportement supplémentaire, on dit que l’on va décorer…

Bien en python c’est un peu la même idée mais avec des fonctions.

Ainsi un décorateur est une fonction prenant en paramètre une autre fonction (celle ci est dite décorée). Le déclarant est exécuté sur la fonction dès sa déclaration et permet donc d’agir sur celle ci.

Python : Les classes et méta-classes

Un article, court celui ci pour explorer le concept de class dans python. ici rien de compliqué, l’approche est classique comme dans tout autre langage. On déclare un mot clef spécifique un nom, et on par sur une surcharge éventuelle des méthodes de base de la classe Object dont on dérive par défaut.

La classe

Ainsi sera par  exemple amener à surcharger une où plusieurs méthodes __init__ dont le rôle est l’initialisation de votre instance. A noter que cette instance est créée par la méthode __new__ qui elle n’est pas à surcharger (enfin on peut mais c’est pas bien) et qui est en fait le vrai constructeur de notre classe.

On notera au passage que l’on pourra distinguer deux types de méthodes, celles de classe comme __new__ au quelle la classe elle même est passé en paramètre et celle d’instance auxquelles c’est le nouvel objet fraîchement qui est créé qui va etre passé en paramètre.

Python : Listes et générateurs

Aujourd'hui nous allons mettre Java un peu de coté et revenir pour ces prochaines semaine aux technologies et connaissances nécessaires au Machine Learning.

Nous avions déjà fait quelques articles, sur les réseaux de neurones avec du Java, du python etc... Du coup comme nous avons déjà bien traité de Java durant ces derniers mois, je vous propose de revenir maintenant sur le langage python.

Alors bien sur ce n'est pas en un article que l'on fera le tour de ce langage qui est tout aussi complexe que Java et de tout son eco-système. Mais on peut malgré tout tenter d'en survoler les mécanismes essentiels afin de pouvoir l'exploiter au mieux. Alors on ne va pas refaire non plus ici un cours de syntaxe mais regarder comment l'utiliser: voir un peu les listes en compréhension, l’intérêt des décorateurs, faire un petit tour du coté des générateurs et bien sur jouer avec les classes et méta-classes etc...

OSGI : Les annotations

Nous avons vu comment déclarer un Activator/Factory/Tracker [ex-karaf], [uttu-felix] pour construire des bundles OSGI, ensuite nous avons vu comment tirer parti de la philosophie Spring pour alléger la définition des beans, des services  et leur utilisations avec SpringDM et Blueprint [bp-karaf], [uttu-bp]; dans ce dernier article (où presque sur OSGI), je vous propose de nous intéresser à une dernière façon de faire des bundles : en utilisant des annotations [scr-annot].

Bon la question ici n’est pas de faire un laïus sur les annotations, j’en ai déjà parlé dans un article [uttu-annot], donc on va aller directement dans le vif du sujet parce que l’on se doute bien que pour remplacer nos Activator and coe et/ou les description xml, il va nous falloir quelques concepts de base.

Les annotations

Alors en fait si vous ne l’aviez pas encore vraiment compris, avec OSGI, finalement il n’y à pas forcément beaucoup de concepts à mettre en oeuvre…. en effet finalement, on à des beans qui implémentent des services et qui vont être injecté dans d’autres beans…

Du coup dans notre contexte, on va rencontrer les annotations suivantes:

• @Component: permet de déclarer un bean
• @Activate/@Deactivate: permet de spécifier une méthode gérant une initialisation spécifique (où inversement pour l’annotation @Deactivate)
• @Référence: permet de spécifier une donnée membre dans laquelle devra être injectée un autre bean (spécifié par @Component)

OSGI : SpringDM et BluePrint

Nous revoilà avec OSGI. Nous parlions à la fin de l’article sur Karaf et Service-mix de SpringDM et BluePrint… mais qu’est ce que c’est?

SpringDM et Blueprint [gemini] sont des frameworks Java et XML permettant la simplification de la description et la gestion des services OSGI de nos Bundles.

SpringDM a été le précurseur et a été suivi par Blueprint grâce à une normalisation (plus une adhésion) au sein de la norme OSGI.

Le principe est d’utiliser les mécanismes de Spring pour réaliser la déclaration de Beans au sein des bundles qui seront chargé par un bundle context dédiés. Cela ne va pas nous empêcher de devoir déclarer nos services sous la forme d’interfaces et d’en réaliser des implémentation mais cela va nous permet de ne plus avoir à implémenter toute la partie Activator, Factory et Tracker que nous avions vu dans les précédents articles sur le sujet…

Quoi ? mais du coup il n’y à plus rien dans le Bundle?