Apprentissage autonome et endurant
L'apprentissage par SVM est une méthode de discrimination supervisée binaire. J'ai abordé diverses approches pour résoudre le problème d'optimisation posé par les SVM. Mon étude a eu a pour objectif de répondre à un certain nombre de questions posées par l'apprentissage autonome. En particulier, est-il possible d'apprendre en temps réel? Est-il possible d'apprendre sur un très grand nombre d'exemples? En d'autres termes, existe-t-il des moyens d'apprendre efficacement?
Ces questions sont complexes. Pour y apporter des éléments de réponses, l'étude a porté en premier lieu sur les méthodes classiques de résolution, bien connues dans le domaine de l'optimisation, comme la méthode du point intérieur. Ensuite je me suis intéressée aux méthodes dédiées aux SVM (SMO, SimpleSVM) qui tiennent compte des spécificités du problème, la principale étant la parcimonie de la solution (en général, une faible proportion d'exemples constitue la solution).
La méthode du point intérieur se sert de tous les exemples pour construire la solution, même si certains ont une influence très proche de zéro car le fait de faire face à un problème avec une solution parcimonieuse n'est pas utilisé au cours de la résolution. En revanche, SMO ou SimpleSVM se servent de cette connaissance pour éviter des calculs inutiles. En effet, les SVM font appel à une fonction noyau qui fournit une notion de distance entre les points. Une approche naïve consiste à pré-calculer l'ensemble des valeurs correspondant à tous les couples d'exemples et à les enregistrer dans une matrice (« noyau » ou « de Gram »). Cette approche est maladroite si peu de points sont vecteurs supports car un grand nombre de valeurs sont calculées inutilement, ce qui est une perte de temps et de mémoire. D'ailleurs, pour des problèmes de grandes dimensions, cette matrice ne peut être gardée complètement en mémoire. Les méthodes modernes dédiées aux SVM évitent ce travers.
Les problèmes de grandes dimensions, en plus de l'aspect temps de calcul, posent d'importantes questions de gestion de la mémoire. Même en utilisant des techniques habiles de gestion de la matrice noyau, la mémoire devient insuffisante quand la solution contient plusieurs dizaines de milliers d'exemples (ce qui peut arriver lorsque l'ensemble d'apprentissage contient lui-même plusieurs millions d'exemples). Lorsque la mémoire est insuffisante, il faut alors recalculer les valeurs non stockées à chaque fois qu'elle sont utilisées. Dans ce cas il est utile de mettre en œuvre des méthodes qui permettent de limiter le nombre de calculs à effectuer.
Les méthodes d'apprentissage en ligne sont dans ce cadre très indiquées car les exemples ne sont considérés qu'une seule fois (contrairement aux méthodes hors ligne, qui peuvent tout à fait considérer chaque exemple un grand nombre de fois tant que la solution exacte au problème posé n'est pas atteinte). Le revers de l'approche en ligne est que la solution obtenue n'est pas la solution optimale. J'ai donc étudié des approches non exactes de résolution des SVM. L'une est une approche pour l'apprentissage en ligne (LASVM) et l'autre une approche hors ligne mais conçue pour les grandes bases de données (CVM). L'apprentissage en ligne, qui est un pré-requis indispensable à l'apprentissage en temps réel, peut être détourné pour traiter les très grandes bases de données.