.. _chap-coursAlgosNoyaux: Les informations pratiques concernant le déroulement de l'unité d'enseignement RCP209 « Apprentissage, réseaux de neurones et modèles graphiques » au Cnam se trouvent dans `ce préambule `_. ############################################ Cours - Algorithmes à noyaux et applications ############################################ « *Statistics is the grammar of science.* » (Karl Pearson) [`Diapositives du cours `_] (cette page sera complétée avec les explications détaillées de la séance introductive du cours) Objectifs et contenu de cette séance ************************************ Nous avons vu dans la séance précédente que « l'astuce à noyaux » permettait de *non-linéariser* tout algorithme linéaire qui utilise des produits scalaires. L'idée est de transposer les données dans un autre espace de dimension plus grande et ensuite appliquer l’algorithme linéaire sur les données projetées. Par la théorème de Mercer, si :math:`K` est un noyau défini positif :math:`K: \mathbb{R}^d \times \mathbb{R}^d \rightarrow \mathbb{R}` alors : .. math:: K(x,y) = \langle\phi(x), \phi(y)\rangle où :math:`\phi:\mathbb{R}^d\rightarrow \mathcal{H}, x\rightarrow \phi(x)` est une transformation de :math:`\mathbb{R}^d` vers un espace de Hilbert :math:`\mathcal{H}` qu'on n'as pas besoin d'expliciter : tout algorithme qui utilise seulement des produits scalaires entres les échantillons de données peut toute suite s'appliquer dans l’espace :math:`\mathcal{H}` via le produit scalaire :math:`\langle\phi(x), \phi(y)\rangle = K(x,y)`. Basés sur cet outil, dans cette séance nous présentons deux extensions de l'algorithme standard SVM : les SVM pour l'estimation du support d'une densité et les SVM pour la régression. Nous finissons par la présentation de quelques applications des SVM de façon générale et, pour illustrer les difficultés rencontrés dans leur utilisation pratique, nous détaillerons la recherche d'images par retour de pertinence. Estimation du support d’une densité *********************************** On considère les données d’apprentissage :math:`D = \{x_1, x_2, \dots, x_n \in \mathcal{X}\}`, issues de variables i.i.d. suivant la densité de probabilité :math:`p(x)` inconnue. Comme il ne s'agit pas d'un problème de classification, il n'y a pas d’étiquettes de classe :math:`y_i`. Le problème consiste à décider si une nouvelle observation :math:`x` est proche ou non de cet ensemble :math:`D`, c'est à dire s’il est tiré de la même distribution. On cherche donc à estimer le support de cette densité : :math:`\{x|p(x)>0\}`. Il y a donc moins de difficultés que pour une estimation de densité : pour un point :math:`x` il faut juste déterminer si :math:`p(x)>0` et non prédire la valeur de :math:`p(x)`. .. figure:: _images/algnoyaux00.png :width: 60% :align: center :name: algnoyaux00 Exemple issu de SVM-toy avec un noyau gaussien : il faut determiner le support de la densité (région blanche). L'intensité de la couleur est proportionnelle à l’éloignement de la frontière. Selon la modélisation géometrique du problème, on distingue deux approches pour le resoudre : SVDD (*Support Vector Data Description*) et OCSVM (*One Class SVM*). *Support Vector Data Description* (SVDD) **************************************** Dans cette approche proposée dans [TD04]_ on cherche dans l'espace d'arrivée :math:`\mathcal{H}` l'hypersphère la plus petite qui englobe les données : .. figure:: _images/algnoyaux01.png :width: 40% :align: center :name: algnoyaux01 SVDD cherche la sphère englobante minimale. La pré-image de l'intérieur de la sphère (dans l'espace de départ) donne le support de la densité. Cette formulation conduit au problème d'optimisation suivant (voir [TD04]_) : .. math:: \left\{ \begin{array}{lll} \underset{R,g}{\min}\; R^2 + C \sum_{i=1}^n\xi_i\\ \textrm{avec :}\\ ||x_i-g||^2 \leq R^2 + \xi_i, i = 1, \dots, n\\ \xi_i \geq 0, i = 1, \dots, n \end{array} \right. où :math:`g` est le centre, :math:`R` est le rayon et la constante :math:`C = \frac{1}{\nu n}` permet de régler la proportion :math:`\nu` de points que l’on désire maintenir en dehors de la boule (*outliers*). Le problème dual est : .. math:: \left\{ \begin{array}{lll} \underset{\alpha}{\min}\; \frac{1}{2}\alpha^T K \alpha - \frac{1}{2} \alpha^T \textrm{diag}(K)\\ \textrm{avec} :\\ e^t \alpha = 1\\ 0 \leq \alpha_i <= C, i = 1, \dots, n \end{array} \right. où :math:`K` est la matrice de Gramm :math:`K_{ij} = k(x_i, x_j)` et :math:`e=(1, 1, \dots 1)^T`. Le centre est obtenu par :math:`g = \sum_{i=1}^{n}\alpha_i \phi(x_i)`. Un nouveau point :math:`x` appartient au support si :math:`||\phi(x) - g|| \leq R^2`, ou : .. math:: K(x, x) - 2 \sum_{i=1}^{n} \alpha_i K(x_i, x) + \sum_{i,j=1}^{n}\alpha_i \alpha_j K(x_i, x_j) \leq R^2 .. figure:: _images/algnoyaux03.png :width: 100% :align: center :name: algnoyaux03 Exemple SVDD : linéaire (à gauche) et noyau gaussien (à droite). A droite, le calcul a été fait pour deux valeurs de :math:`C`. Le point en haut à droite est un *outlier* (il est placé en dehors de l’enveloppe calculée). *One Class* SVM (OCSVM) *********************** Dans l'approche One Class SVM (OCSVM) de [SS01]_ il faut trouver, dans l’espace d’arrivée :math:`\mathcal{H}`, l’hyperplan le plus éloigné de l’origine qui sépare les données de l’origine. .. figure:: _images/algnoyaux02.png :width: 60% :align: center :name: algnoyaux02 L'approche *One Class* SVM (OCSVM) : chercher l'hyperplan le plus éloigné de l'origine qui sépare tous les points d'apprentissage (moins éventuellement les quelques *ouliers*). Cela conduit au problème primal suivant (voir [SS01]_) : .. math:: \left\{ \begin{array}{lll} \underset{w,\xi_i, \rho}{\min}\; \frac{1}{2} ||w||^2 + C \sum_{i=1}^n\xi_i -\rho \\ \textrm{avec :}\\ w\cdot x_i \geq \rho - \xi_i, i = 1, \dots, n\\ \xi_i \geq 0, i = 1, \dots, n \end{array} \right. où : - la fonction de décision est donnée par : :math:`f(x) = \mathrm{sign}\left(\langle w, \phi(x)\rangle - \rho\right)`, - :math:`\rho` est la distance à l’origine, - :math:`C = \frac{1}{\nu n}` est un paramètre de régularisation qui permet de contrôler le nombre de *outliers*. Le problème dual est le même que celui des SVDD avec le terme linéaire de la fonction coût en moins : .. math:: \left\{ \begin{array}{lll} \underset{\alpha}{\min}\; \frac{1}{2}\alpha^T K \alpha\\ \textrm{avec :}\\ e^t \alpha = 1\\ 0 \leq \alpha_i <= C, i = 1, \dots, n \end{array} \right. où : - :math:`K` est la matrice de Gramm :math:`K_{ij} = k(x_i, x_j)` et :math:`e=(1, 1, \dots 1)^T` - la fonction de décision est donnée par : .. math:: f(x) = \mathrm{sign}\left(\langle w, \phi(x)\rangle - \rho\right) = \mathrm{sign}(\sum_{i=1}^{n}\alpha_i K(x_i, x) - \rho) avec :math:`\rho = \langle w, \phi(x_s)\rangle = \sum_{i=1}^{n}\alpha_i K(x_i, x_s)` - :math:`C = \frac{1}{\nu n}` est le paramètre de régularisation qui permet de contrôler le nombre de outliers. Dans les deux formulations :math:`\nu \in (0, 1]` et :math:`\nu n = 1/C` peut être interprété comme : - une borne supérieure pour la fraction de *outliers*, - une borne inférieure pour la fraction de vecteurs de support. Concernant la capacité de généralisation : la probabilité pour que de nouveaux exemples (tirages i.i.d. suivant la densité :math:`p(x)`) soient en dehors d’une région un peu plus grande que le support déterminé ne sera pas supérieure de beaucoup à la fraction de *outliers* dans les données d’apprentissage. .. figure:: _images/algnoyauxoneclass01.png :width: 60% :align: center :name: algnoyauxoneclass01 Effet du paramètre :math:`\nu` dans le OCSVM. .. figure:: _images/algnoyauxoneclass02.png :width: 60% :align: center :name: algnoyauxoneclass02 Effet du paramètre :math:`\nu` dans le OCSVM. Pour comparaison : le paramètre d'échelle du noyau :math:`\gamma` a une valeur bien plus grande par rapport à la :numref:`algnoyauxoneclass01`. SVM pour la régression (SVR) **************************** Les données d’apprentissage sont :math:`\mathcal{D} = \{(x_i, y_i); i = 1,\dots, n\}`, où :math:`x_i \in \mathcal{X}, y_i \in \mathbb{R}`. A la différence du problème de classification, ou les :math:`y_i` étaient des étiquettes de classe (valeurs -1 ou 1), ici les :math:`y_i` ont des valeurs réelles. Le but est donc, étant donné une novelle observation :math:`x` de prédire la valeur du :math:`y` associé. C'est un problème plus difficile car il faut apprendre à prédire les valeurs d'une fonction à partir d'un nombre fini d'échantillons. .. figure:: _images/algnoyaux04.png :width: 80% :align: center :name: algnoyaux04 SVM pour la régression : on cherche une solution aussi « plate » que possible sans s’éloigner trop des points d'apprentissage (en vert). En régression :math:`\epsilon`-SV on cherche donc une fonction :math:`f:\mathcal{X} \rightarrow R` aussi « plate » que possible tel que :math:`|f(x_i) - y_i| < \epsilon` pour tous les :math:`i`. Pour cela on considère les projections des points d'apprentissage dans l'espace d'arrivée :math:`\mathcal{H}` et on cherche des solutions de la forme .. math:: f(x) = \langle w, \phi(x)\rangle + b La condition d’aplatissement se traduit par la minimisation de :math:`||w||^2 = \langle w, w \rangle`. La régression :math:`\epsilon`-SV correspond à l’utilisation de la fonction de coût :math:`\epsilon`-insensible : .. math:: |\xi|_\epsilon = \left\{ \begin{array}{ll} 0 \mathrm{\;si\;} |\xi| < \epsilon\\ |\xi| - \epsilon \mathrm{\;sinon\;}\\ \end{array} \right. Comme en discrimination, on accepte quelques erreurs au-delà de :math:`\epsilon` et on introduit les « variables d'assouplissement » :math:`\xi_t` et :math:`\xi_t^*` : .. figure:: _images/algnoyaux05.png :width: 100% :align: center :name: algnoyaux05 Le problème d’optimisation sera : .. math:: \left\{ \begin{array}{llll} \underset{w, b}{\min}\; \frac{1}{2} ||w||^2 + C \sum_{i=1}^n(\xi_i + \xi_i^*)\\ \textrm{avec :}\\ y_i - \langle w, \phi(x_i)\rangle - b \leq \epsilon + \xi_i, i = 1, \dots, n\\ \langle w, \phi(x_i)\rangle +b - y_i \leq \epsilon + \xi_i^*, i = 1, \dots, n\\ \xi_i, \xi_i^* \geq 0, i = 1, \dots, n \end{array} \right. La constante :math:`C > 0` permet de choisir le point d’équilibre entre l'aplatissement de la solution et l’acceptation d’erreurs au-delà de :math:`\epsilon`-SVM pour la régression. Avec les multiplicateurs de Lagrange on obtient le problème dual : .. math:: \left\{ \begin{array}{llll} \underset{\alpha, \alpha^*}{\min}\; \frac{1}{2}\sum_{i,j=1}^{n} (\alpha_i - \alpha_i^*)(\alpha_j - \alpha_j^*)K(x_i, x_j) + \epsilon\sum_{1=1}^{n} (\alpha_i + \alpha_i^*) - \sum_{1=1}^{n} y_i (\alpha_i - \alpha_i^*) \\ \textrm{avec :}\\ 0 \leq \alpha_i, \alpha_j \leq C,\; i,j = 1, \dots, n\\ \sum_{1=1}^n (\alpha_i - \alpha_i^*) = 0 \end{array} \right. Tous les points d’apprentissage à l’intérieur du :math:`\epsilon`-tube ont :math:`\alpha_i = \alpha_i^* = 0`. Les points qui ont :math:`\alpha_i, \alpha_i^* \neq 0` sont appelés vecteurs de support. Comme :math:`w = \sum_{1=1}^n (\alpha_i - \alpha_i^*)\phi(x_i)`, la fonction recherchée sera : .. math:: f(x) = \sum_{1=1}^n (\alpha_i - \alpha_i^*)K(x_i, x) + b .. figure:: _images/algnoyauxsvr2.png :width: 70% :align: center :name: algnoyauxsvr2 Le choix du paramètre :math:`\epsilon` est d'une grande importance pour éviter les phénomènes de sur- et sous-apprentissage. .. figure:: _images/algnoyauxsvr1.png :width: 70% :align: center :name: algnoyauxsvr1 Des valeurs trop petites du paramètre :math:`\epsilon` forcent la fonction approximée de suivre les détails (bruit) de l’échantillon. Ceci conduit au problème de sur-apprentissage. .. figure:: _images/algnoyauxsvr3.png :width: 70% :align: center :name: algnoyauxsvr3 Des valeurs trop grandes du paramètre :math:`\epsilon` mènent à une fonction trop lissée (problème de sous-apprentissage). .. figure:: _images/algnoyauxsvr4.png :width: 100% :align: center :name: algnoyauxsvr4 L'impact des paramètres :math:`\nu` et :math:`\epsilon` sur un problème de régression (exemple produit avec l'outil SVM-Toy). Autres algorithmes à noyaux *************************** Pratiquement, tout algorithme qui utilise des produits scalaires entre les échantillons peut être « non-linéarisé » par le « truc des noyaux ». Quelques exemples notables : - *Kernel PCA* (*Principal Component Analysis*), voir [SS01]_ ; - *Kernel CCA* (*Canonical Correlation Analysis*), voir [HSS03]_ ; - *Kernel FDA* (*Factorial Discriminant Analysis*), voir [RS00]_. Applications des SVM ******************** Les machines à vecteurs de supports ont l’avantage de ne pas nécessiter le réglage de beaucoup de paramètres et ont été appliquées avec grand succès dans de nombreux domaines : - Finance (évolution des prix, valeurs en bourse, etc.) - Structure des protéines (*protein folding*) - Génomique (*microarray gene expression data*) - Reconnaissance de visages - Détections des catastrophes, forecasting - Images satellite et surveillance - Diagnostic médical (cancer du sein) - En physique, par ex. *Particle and Quark-Flavour Identification*, *High Energy Physics* (*Classifying LEP Data with Support Vector Algorithms* by Schölkopf et al. AIHENP’99). Références : livres, articles, web ********************************** .. [SC08] Steinwart, Christmann, *Support Vector Machines*, Springer 2008. .. [SS01] Scholkopf, Smola, *Learning with Kernels*, The MIT Press, 2001. .. [HTF06] Hastie, Tibshirani, Friedman, *The elements of statistical learning: data mining, inference, and prediction*, New York, Springer Verlag, 2006. .. [WikiStat] Machines à vecteurs supports (WikiStat), http://wikistat.fr .. [TD04] Tax and Duin, *Support Vector Data Description*, Machine Learning, 54(1), 2004. .. [HSS03] Hardoon, Szedmak, Shawe-Taylor, *Canonical correlation analysis; an overview with application to learning methods*, Technical Report, University of London, 2003. .. [RS00] Roth, Steinhage, *Nonlinear discriminant analysis using kernel functions*, Advances in Neural Information Processing Systems, 2000.