Classification supervisée et optimisation convexe

Les succès récents des méthodes d’optimisation stochastiques telles que les techniques de des- cente de gradient moyenné (stochastic average gradient) ont renouvelé l’interêt des approches par descente de gradient pour résoudre les problèmes convexes de grande taille [184, 208]. Ce- pendant, lorsque le nombre de paramètres dépasse le million et que l’ensemble d’entraînement approche du Téra-octet, la resolution d’un problème convexe reste computationnellement très couteuse, même lorsque l’expression du gradient est très simple. Ainsi, les progrès considérables réalisés par les méthodes d’approximation stochastiques ne suffisent pas à contrer l’explosion de la quantité de données à manipuler.Par ailleurs, la nature stochastique de ces approches favorise la formulation d’équivalents parallèlisés voire distribués à ces algorithmes. Toutefois, nous mettons en évidence dans ce cha- pitre qu’il n’est pas trivial d’en proposer une extension décentralisée et asynchrone qui conserve de bonne propriétés de stabilité. L’hypothèse de convexité assure que tout minimum local de f en est également un minimum glo- bal. Notons que f n’est pas nécessairement dérivable. En tout point où f est dérivable, rf (w) désigne le gradient de f en w. Pour les points où f n’est pas lisse, rf (w) 2 @f (w) désigne alors un sous-gradient de f en w. Parmi les problèmes convexes, une sous-classe importante est constituée des problèmes fortement convexes, pour lesquels

contrôle le niveau de régularisation souhaité. Ce type de reformulation a l’avantage d’assurer la convexité forte (on a ici ) et ainsi de privilégier, parmi les solutions offrant une risque empirique identique, celle qui minimise également un certain risque structurel [242]. Le pouvoir de généralisation s’en trouve généralement accru, limitant ainsi les risques de sur- apprentissage sur les données d’entraînement.Ce chapitre est organisé comme suit. La section 1 présente un exemple emblématique d’op- timisation convexe : la classification supervisée par Machines à Vecteurs Support (SVM). Dans la section 2, nous détaillons quelques méthodes de résolution primales basées sur la descente de gradient stochastique (SGD). La section 3 définit l’optimisation convexe en environnement distribué. Dans la section 4, nous présentons un algorithme de résolution primal qui s’appuie sur le moyennage à court terme des gradients (Short Term Average Gradient, STAG). La section 5 est consacrée à son extension décentralisée et asynchrone (Asynchronous Gossip Short Term Average Gradient, AGSTAG). Son evaluation expérimentale est présentée en section 6, avant de conclure le chapitre.! f0; : : : ; C 1g appelée classificateur qui prédit pour tout vecteur d’entrée son appartenance à une des C classes iden- tifiées par un label entier entre 0 et C 1. La classe réelle correspondant à un vecteur donné est supposée inconnue, le but de la tâche étant d’estimer cette classe à partir d’un ensemble de couples d’apprentissage f(xjouant alors le rôle de b. Dans la suite de ce chapitre, nous ignorerons donc le paramètre b. L’objectif (4.6) est convexe mais pas fortement convexe, dans la mesure où il existe généralement une infinité d’hyperplans distincts qui offrent une erreur minimale. Par ailleurs, la valeur minimale de f n’est nulle que lorsque les échantillons sont linéairement séparables [179].

 L’hyperplan optimal est donc défini par un petit nombre d’échantillons appelés vecteurs supports. Ces échantillons sont justement ceux qui se situent sur la frontière de décision ou l’enfreignent. Par ailleurs, le théorème de Mercer [176] révèle que toute fonction noyau, semi-définie positive, est équivalente à un produit scalaire dans un certain espace de Hilbert (de dimension potentiellement infinie). On peut donc substituer au produit scalaire initial x 2. Généralement, on ne cherche pas la solution exacte au problème (4.10), dans la mesure où l’erreur empirique est seulement évaluée sur l’ensemble d’apprentissage tandis que l’objectif final est de minimiser l’erreur en phase de test, c’est à dire sur des données in- observables durant l’entraînement. Ainsi, on observe en pratique que lorsqu’une précision suffisante est atteinte sur l’ensemble d’entraînement, il est inutile de raffiner le modèle car l’erreur en utilisation ne progresse plus [32]. Comme nous le verrons dans la section sui- vante, les méthodes primales convergent bien plus rapidement pendant les premières ité- rations, puis ralentissent significativement à l’approche de l’optimum. Puisqu’une conver- gence approximative est suffisante, les méthodes primales produisent ainsi en pratique une solution acceptable beaucoup plus rapidement que leurs homologues duales.3. Pour les problèmes de classification linéaires, un solveur primal est généralement plus ra- pide qu’un solveur dual [55]. Par ailleurs, de nouveaux noyaux explicites, où l’image d’un vecteur d’entrée dans l’espace de redescription peut être effectivement calculée et stockée efficacement ont récemment montré des performances de classification par SVM linéaire égales voire supérieures aux méthodes à noyaux implicites non-linéaires (par exemple en classification d’images : [137, 182, 197, 200]). La combinaison de ces deux facteurs conduit à une utilisation croissante d’encodeurs de caractéristiques explicites suivis d’une SVM linéaire lorsque la quantité d’échantillons d’apprentissage devient très grande.