Return to site

Vive les hyperplans

Algorithmes machine learning : SVM

Billet posté initialement sur la plateforme Medium où vous pourrez partager ou commenter.

Don't panic !

Ce billet traite d'apprentissage automatique, de la théorie de Vapnik-Chervonenkis, de classes de fonctions infinies, et de machines à vecteurs de support.

On est donc sur une forme assez claire d'agression mathématique caractérisée. J'aurais pu faire bien pire, vous êtes donc chanceux. Quelque part.

Contexte

Les machines à vecteurs de support, a.k.a. support vector machines [wp] ou encore séparateurs à vastes marges, sont des outils classiques de l'apprentissage automatique (machine learning). Domaine très tendance, puisque les "analystes" de Gartner l'ont à nouveau placé au sommet de leur "hype-cycle for emerging technologies" de 2016, cf figure ci-dessous, et ici. C'est dire la pertinence de mon positionnement.

Hype Cycle for Emerging Technologies, Gartner, 2016.

Pourquoi est-ce un outil classique ? Car le SVM marche bien sur des jeux de données de grande taille, avec une grande variabilité dans les données, beaucoup de paramètres, du bruit ou des erreurs dans les données etc. Bref, des datasets du monde réel.

Le cas traité ici est le problème classique de la classification de jeux de données, qui peuvent être plus ou moins ce qu'elles veulent (historiques de ventes, profils de clients, logs etc). Il se résume ainsi : si je sais répartir n points dans p classes, puis-je utiliser cette connaissance pour répartir des points similaires dans des classes similaires. Les points peuvent être des points sur une ligne, une carte ou un espace (dimension 1,2,3) mais aussi des éléments d'espaces beaucoup plus grands, contenant des nombres, des mots, des images etc. Tout ce que vous pouvez vouloir classer, en somme. On parle de points k-dimensionnels, k quelconque.

Apprentissage

Un problème de classification est, pour un ordinateur, un problème d'apprentissage. On lui fournit des informations sur les données à classer (données d'entrée, x) et les résultats correspondants (données d'apprentissage, y). On parle d'apprentissage supervisé, en opposition au cas de l'apprentissage non-supervisé où on laisse l'ordinateur classer les données seul. L'idée est donc de trouver une méthode (fonction de classement, f) qui saura, pour chaque x, donner le résultat y=f(x). De manière très schématique [*] cette fonction f a des paramètres internes/externes qu'il va falloir adapter pour reproduire le classement voulu.

Le bon point, c'est que le problème de l'apprentissage est un problème qu'on sait résoudre ... pour peu qu'on utilise des fonctions de classement assez complexes (cf figure ci-dessous). Au prix toutefois d'une erreur de généralisation phénoménale, ce qui est, en pratique, absolument rédhibitoire.

Différents cas de modélisation : robuste (à gauche), trop ajusté (à droite), correct (en bas)

Généralisation ?

C'est le fait de prédire les valeurs f(x) en dehors de l'ensemble d'apprentissage. Point important, puisque c'est justement sur cette capacité de prédiction qu'on attend la fonction de classification : prédire des résultats cohérents en dehors de son ensemble d'apprentissage.

Ce problème se pose souvent. Si une société connaît le comportement de deux catégories de clients, ceux qui ont un panier moyen de 50€ et 70€, on s'attend à ce que le comportement des clients avec un panier moyen à 60€ soit quelque part entre les deux ; pas à l'opposé complet. Exit, donc, les fonctions qui gigotent trop. C'est le coté rédhibitoire dont je parlais plus haut.

Généralisation !

Les gens qui théorisent aiment bien reformuler.

On peut ramener le problème de l'apprentissage (supervisé) au problème de la généralisation de la fonction de classement. Un pré-requis fort est de savoir s'il possible de pouvoir prédire des résultats en dehors du jeu de données d'entrée. Le cas échéant, il est raisonnable de considérer que plus on ajoute de points, plus la prédiction est bonne [**].

Ce qui soulève les questions suivantes :

  • Converge-t-on vers une fonction de classement optimale ?
  • Si oui, à quelle vitesse s'effectue cette convergence ?
  • Y a-t-il une stratégie pour construire des algorithmes qui garantissent, mesurent et contrôlent la capacité de généralisation de modèles d’apprentissage ?

Une réponse est donnée par un principe de minimisation du risque (structural risk minimization, Vapnik et Chervonenkis, 1974), qui part de l'idée que pour construire le meilleur modèle à partir de données, il faut tenter d’optimiser à la fois sa performance sur l’ensemble d’apprentissage, et sa performance de généralisation ; le modèle se construit en parcourant une famille de fonctions.

Le but est donc de trouver des (familles de) fonctions sympathiques qui réalisent un compromis : bon apprentissage et bonne généralisation. On parle de familles de fonctions car, afin de pouvoir maîtriser la généralisation du modèle, il faut pouvoir caractériser les fonctions qu'on veut utiliser. On ne va évidemment pas les choisir au hasard ...

Dimension

Une question se pose souvent, pour les grands jeux de données : comment ne pas se noyer dans la dimensionnalité des données (ex: vous avez 10 millions de points, et pour chaque point, 17 paramètres possibles) ? Question à laquelle il faut maintenant ajouter celle du choix de la fonction de classement. Je traduis : il faut travailler avec des familles de fonctions, assez génériques pour pouvoir être adaptables aux données. Ce qui permet d'introduire un premier infini, ou presque, qui vient s'ajouter à l'infini, ou presque, des données d'entrée. Il faut donc quantifier et contrôler ces infinis pour rester dans un apprentissage consistant.

Toute la question est donc de proposer une méthode de classification générale satisfaisante, ie garder la variabilité a priori infinie de tous les datasets réels et utiliser des familles de fonctions suffisamment générales pour ne pas avoir à repartir de zéro à chaque fois ?

Exemples de fonctions de classification. Issu de scikit-learn.org.

Et le SVM, dans tout ca ?

Les machines à vecteurs de support entrent maintenant en jeu, du coté de la famille de fonctions, vous l'aurez deviné.

La tentation est grande d'écrire des équations, mais on sortirait du cadre joyeux et bon enfant de ce billet. Et je ne suis pas assez matheux pour ne pas être certain de finir par raconter n'importe quoi. Je vais donc essayer de vous faire sentir l'intérêt de cette méthode, en vous décrivant les trois idées principales.

Revenons au problème : il faut pouvoir contrôler l'erreur de généralisation. Dans le cadre d'une famille de fonctions de classement de taille finie, on sait faire. Enfin, ils savent faire. Mais on perd en généralité. Il faut donc utiliser des familles infinies, auquel cas on perd le contrôle.

La première idée est de quantifier la complexité de cette classe de fonctions, en estimant la taille maximale d'un jeu de données qu'elle peut totalement résoudre (=classer).

Comment ? En se basant sur la séparabilité de points dans un espace n-dimensionnel, dans le cadre d'une théorie générale de l'apprentissage et plus précisément de la dimension de Vapnik-Chervonenkis (avec de bonnes pages Wikipedia ici et ici ... bon courage, ça pique). On retrouve ainsi un moyen de contrôler l'erreur de généralisation. Cette dimension (de familles de fonctions d'une taille infinie !) permet de se ramener à une situation sympathique de contrôle de l'apprentissage, i.e. l'erreur de généralisation reste bornée par l'erreur d'apprentissage et une quantité faisant intervenir la mesure de la complexité de l'espace des solutions.
   
La seconde idée est de pouvoir trouver des familles de fonctions sympathiques qui ont un grand pouvoir prédictif et qui ont une faible complexité. C'est tout l'intérêt d'un théorème toujours du même Vapnik, ouzbek semble-t-il, qui exhibe une condition dite de "larges marges" sur des ensembles de fonctions de classification générales, dans des espaces de tailles quelconques, mais finies. En pratique, on se sert d'hyperplans, qui sont des fonctions très simples qui séparent les espaces en deux parties, comme des murs. Ou des plans en 3D. D'où le nom.

La troisième idée, qui paraîtra, au premier abord, passablement bizarre aux gens qui n'ont pas un doctorat de mathématiques théoriques, consiste à dire que si un problème ne peut pas être résolu à grands coups d'hyperplans, on va le plonger dans un espace plus grand où il le sera. Quite à adapter un peu la métrique. Prendre de la hauteur, changer de point de vue, mais comme le ferait un mathématicien. En l'état, et moyennant quelques astuces de calculs (kernel trick), ça marche plutôt bien.

Et sinon

en pratique, on finit par obtenir des hyperplans un peu contraints (=la classe de fonctions sympathiques), des règles du jeu puissantes pour observer les jeux de données (=l'utilisation d'espaces de dimensions supérieures) et l'assurance qu'on saura contenir les erreurs de généralisation et d'apprentissage. Ce qui permet d'adresser sereinement et efficacement les cas réels, au moins dans un premier temps.

OceanData se sert d'ailleurs souvent des algorithmes de type SVM dans ses analyses.

[*] : et donc presque totalement, mais pas tout à fait, fausse.

[**]: j'oublie volontairement les problématiques de sur-apprentissage

All Posts
×

Almost done…

We just sent you an email. Please click the link in the email to confirm your subscription!

OKSubscriptions powered by Strikingly