Sélection du noyau

Illustration sur des données artificielles

Nous allons montrer l’importance de l’affinage des hyper-paramètres à travers une courte étude sur des données artificielles à deux dimensions. Cette étude portera sur le paramètre σ du noyau RBF gaussien, parce que les noyaux sigmoïdes sont très instables (le noyau n’est pas positif pour toutes les valeurs de ses paramètres), et les noyaux polynomiaux ont intérêt limité sur deux dimensions. On s’intéressera donc à des problèmes définis sur des variables bi-dimensionnelles x = [x1, x2]. Dans le cas de données artificielles séparables, on pourra définir une fonction de décision idéale fI (x) telle que y = fI (x) ∀x, où y est la classe associée à l’exemple x. 4.1.1 Surface de décision Le problème de l’échiquier constitue un très bon exemple de données artificielles linéairement inséparables. Si l’on fixe à NC le nombre de case par côté, la fonction de décision idéale fI : R 2 → [0; 1] × [0; 1] est définie comme suit : fI (x1, x2) = sign(mod(bNC (x1 + x2)c, 2)), où mod(a, b) est le reste de la division entière de a par b, et l’opérateur bxc désigne l’arrondi par défaut. La figure 4.1 montre la fonction de décision idéale pour un échiquier à NC = 3 cases de largeur, ainsi que 250 exemples générés aléatoirement. Les croix claires désignent les exemples de la classe 1, symbolisée par les régions noires pour la fonction de décision, tandis que les cercles foncés désignent les exemples de la classe 2, symbolisée par les régions blanches pour la fonction de décision. Les figures 4.2(a), (b) et (c) illustrent le résultat de l’apprentissage par SVM avec noyau gaussien RBF pour différentes valeurs de σ. La ligne pleine blanche représente la surface de séparation et les pointillés gris représentent les surfaces de marge pour chaque classe. Les Vecteurs de Support sont donc les exemples situés sur ces lignes grises. Si l’on rappelle l’expression du noyau gaussien RBF, k(x, y) = exp Å − ||x − y||2 d σ2 ã , celui-ci traduit bien une mesure de similarité basée sur la distance entre les exemples. Lorsque σ augmente, le terme sur lequel s’applique l’exponentielle inverse tend vers 0, ce qui accroît la similarité entre les exemples. À l’inverse, lorsque l’on réduit le terme σ, la distance entre les exemples se trouve amplifiée. Ce phénomène apparaît clairement dans l’exemple présent. Lorsque σ est trop bas (figure 4.2(a)), les exemples sont plus distants entre eux et la fonction de décision doit donc inclure plus de Vecteurs de Support pour pouvoir couvrir tout l’espace. On voit en effet sur la figure que de 48 4.1. ILLUSTRATION SUR DES DONNÉES ARTIFICIELLES −1 −0.8 −0.6 −0.4 −0.2 0 0.2 0.4 0.6 0.8 1 −1 −0.8 −0.6 −0.4 −0.2 0 0.2 0.4 0.6 0.8 1 Dim 1 Dim 2 Figure 4.1 – Fonction de décision idéale de la distribution Echiquier et répartition des 100 exemples d’apprentissage. (a) σ = 0.2, C = 100 (b) σ = 1, C = 100 (c) σ = 3, C = 100 Figure 4.2 – Surfaces de décision obtenues par apprentissage SVM à noyau gaussien RBF pour différentes valeurs de σ sur la distribution Echiquier. nombreux exemples figurent sur la surface de marge, qui se trouve ainsi trop adaptée à l’ensemble d’apprentissage, au détriment de la capacité de généralisation du classificateur. On parle alors de sur-apprentissage (ou d’overfitting). Lorsque, par contre, σ est trop élevé (figure 4.2(c)), la mesure de similarité ne permet plus de distinguer les exemples de classes opposées. Ainsi l’algorithme est incapable de déduire une surface de décision traduisant la frontière entre les classes. La figure centrale (4.2(b)) présente dans ce cas un bon compromis entre généralisation et erreur de classification. 4.1.2 Tolérance aux outliers On utilise ici une distribution plus simple, nommée Courbe et représentée figure 4.3, pour illustrer l’influence du paramètre C par rapport à la présence d’outliers. 100 exemples sont générés aléatoirement, dont 8 outliers sont assignés à la classe erronée. La figure 4.4 montre les résultats de l’apprentissage par SVM avec noyau gaussien RBF pour différentes combinaisons de valeurs pour σ et C. On peut ainsi constater qu’une valeur trop basse du facteur d’erreur C (figures (a) à gauche) induit une trop grande tolérance aux erreurs de classification. Ainsi le classificateur peine à établir une surface de décision qui réponde au problème posé puisque les exemples peuvent se situer indifféremment d’un côté ou de l’autre de la surface de décision. A l’inverse, une valeur trop élevée de C (figures (c) à droite) pousse le classificateur à prendre en compte le moindre exemple erroné (dans la mesure où le paramètre σ lui permet de complexifier la surface de décision, ce qui n’est pas le cas par exemple pour la figure (c,3) où σ = 6). La comparaison des figures (c,1) et (c,2) illustre clairement la tendance à « encercler » chaque outlier 49 CHAPITRE 4. SÉLECTION DU NOYAU −1 −0.8 −0.6 −0.4 −0.2 0 0.2 0.4 0.6 0.8 1 −1 −0.8 −0.6 −0.4 −0.2 0 0.2 0.4 0.6 0.8 1 Dim 1 Dim 2 Figure 4.3 – Fonction de décision idéale de la distribution Courbe et répartition des 100 exemples d’apprentissage. pour C trop élevé. Dans le cas étudié, C = 2 (figures (b) au centre) constitue un bon compromis. Néanmoins, on voit que cette valeur n’a de sens que pour un σ adéquat. Les paramètres sont donc fortement liés entre eux, ce qui explique la complexité de l’affinage des noyaux puisque les paramètres ne peuvent être affinés indépendamment. Nous présentons dans la section suivante les stratégies possibles pour l’affinage des paramètres, ainsi que les critères employés. On reviendra plus précisément dans la section 4.5 sur la question du facteur d’erreur C, et sa relation au paramètre σ. 4.2 Stratégies d’affinage On aborde ici le problème de l’affinage des hyper-paramètres indépendamment de leur nature et de leur nombre. On considère donc qu’un noyau kΘ est paramétré par P valeurs Θ = [θ1, . . . , θP ]. 4.2.1 Recherche par maillage La recherche par maillage (grid-search) est la méthode la plus généralement employée. Elle consiste à évaluer les performances du classifieur SVM appris sur un ensemble fini de V valeurs V = {Θi , i ∈ [1, . . . , V ]}. Soit P(kΘ) la mesure de performances du noyau kΘ, l’algorithme consiste donc à retenir la valeur Θˆ telle que Θˆ = arg max Θ∈V P(kΘ). Concernant le choix des valeurs de l’ensemble V, on utilise généralement pour chaque paramètre un ensemble de valeurs également réparties dans un intervalle donné. V est alors le produit cartésien de ces ensembles et constitue un maillage de l’espace des paramètres sur un intervalle donné. Il est également courant d’utiliser des valeurs logarithmiquement réparties. Nous détaillerons par la suite (section 4.3) la plupart des critères permettant d’évaluer la mesure de performance d’un classifieur SVM. La solution la plus basique et la plus généralement employée consiste à mesurer le taux d’erreur sur un ensemble dit de validation. La recherche par maillage souffre ainsi de deux défauts majeurs : • La complexité algorithmique est polynomiale, en O(n P ). On fait donc face à une explosion combinatoire dès que le nombre de paramètres dépasse 1 ou 2..

Optimisation

Une autre stratégie consiste, plutôt que de tenter de couvrir l’espace de recherche, à évaluer itérativement la valeur optimale par mises à jour successives en fonction d’un critère de performance. Cette approche sollicite donc des méthodes d’optimisation, domaine très large couvrant le problème de la recherche d’extrema. Les méthodes de programmation mathématique (linéaire, quadratique, etc…) ne peuvent être utilisées ici puisque le problème n’est pas exprimé analytiquement, tandis que les algorithmes dérivés de la descente de gradient sont applicables. De nombreuses approches de ce type existent dans la littérature [26], parmi lesquelles la Méthode de Newton, la descente de gradient stochastique ou le gradient conjugué. Néanmoins, une étude des méthodes d’optimisation sort du domaine de cette thèse et nous nous restreindrons à l’usage de la plus simple, la descente (ou montée) de gradient. On peut résumer celle-ci par l’algorithme 1 présenté ci-dessous. La condition d’arrêt peut également s’appliquer à la différence de performance entre deux itérations. La descente de gradient implique de pouvoir calculer le gradient de la mesure de performance par rapport aux paramètres du noyau. C’est là la principale restriction liée à cette méthode.

Recherche par voisinage

Momma et Bennett proposent pour l’affinage de paramètres une recherche par pas successifs qui constitue un compromis intéressant entre optimisation et recherche par maillage pour le cas de critères non dérivables. A chaque itération k le critère est évalué sur des points voisins de la valeur actuelle, dont la disposition forme ce que les auteurs appellent un pattern, et le point actuel est déplacé au point voisin minimisant le critère, jusqu’à convergence. Le pattern le plus simple consiste à sélectionner les points à une distance ∆k, décroissante, pour chacune des directions axiales de l’espace. Ce critère permet de s’affranchir de la contrainte de dérivabilité et restreint fortement l’espace de recherche par rapport à la recherche par maillage. Toutefois, il reste très coûteux lorsque l’espace est de dimension élevée, et n’offre aucune garantie quant à la globalité du maximum trouvé. En pratique on préférera se limiter ici à des critères dérivables permettant l’usage de la descente de gradient.