Apprentissage incrémental

En informatique, l'apprentissage incrémental ou incrémentiel^[1] désigne les algorithmes d'apprentissages qui ont la particularité d'apprendre à partir de données reçues au fur et à mesure du temps. À chaque incrément il reçoivent des données d'entrées et un résultat, l'algorithme calcule alors une amélioration du calcul fait pour prédire le résultat à partir des données d'entrées.

Puisqu'il ne connait pas l'intégralité des données, un algorithme d'apprentissage incrémental est forcé de faire des choix qui peuvent s'avérer finalement non optimaux ; l'étude des algorithmes d'apprentissage incrémental a ainsi mis l'accent sur la qualité des choix possibles dans une telle configuration. L'analyse compétitive formalise cette idée en comparant la performance, sur les mêmes données, de l'algorithme d'apprentissage incrémental et de l'équivalent ayant à disposition l'intégralité des données. Pour d'autres points de vue sur les algorithmes où les données deviennent disponibles au fur et à mesure du temps, voir les articles algorithme de fouille de flots de données (centré sur la quantité de mémoire nécessaire à représenter les données reçues dans le passé), dynamic algorithm (centré sur la complexité en temps pour manipuler les solutions à des problèmes à inputs online).

Un problème illustrant le concept d'algorithme d'apprentissage incrémental est celui du voyageur de commerce canadien. Le but de ce problème est de minimiser le coût d'atteinte d'un sommet dans un graphe pondéré où certaines des arêtes sont peu « fiables » car elles peuvent à tout moment être retirées du graphe. Cependant, si une arête devient inutilisable, cela n'est révélé au "voyageur" uniquement lorsqu'il atteint l'un des sommets de cette arête. Le pire cas de ce problème a lieu lorsque toutes les arêtes peu fiables s'avèrent être inutilisables et le problème se réduit alors au problème du plus court chemin. Une analyse alternative du problème peut être effectuée à l'aide de l'analyse compétitive. Pour cette méthode d'analyse, l'algorithme offline connait par avance les arêtes qui vont être inutilisables et le but est de minimiser le rapport entre la performance de l'algorithme en ligne et celle de l'algorithme hors ligne. Ce problème est PSPACE-complet.

Voici quelques noms d'algorithmes online : K server, Balance2, Balance-Slack, Double Coverage, Equipoise, Handicap, Harmonic, Random-Slack, Tight Span Algorithm, Tree Algorithm, Work Function Algorithm.

• Algorithme glouton
• Apprentissage par renforcement
• Séquençage de tâches
• Problème du secrétaire
• Algorithme de calcul de la variance
• algorithme d'Ukkonen

• (en) A. Borodin et R. El-Yaniv, Online Computation and Competitive Analysis, Cambridge University Press, 1998, 414 p. (ISBN 978-0-521-56392-5, BNF 37558537, lire en ligne)

• Bibliographie sur les algorithmes en ligne

• Portail de l'informatique théorique