Algorithme d'apprentissage incrémental

En informatique, un algorithme d'apprentissage incrémental ou incrémentiel^[1] est un algorithme d'apprentissage qui a la particularité d'être online, c'est-à-dire qui apprend à partir de données reçues au fur et à mesure du temps. À chaque incrément il reçoit 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.

Principe

Analyse compétitive

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).

Problème du voyageur de commerce canadien

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.

Liste d'algorithmes online

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.

Voir aussi

• algorithme glouton
• Apprentissage par renforcement
• Adversary Model
• Job shop scheduling
• List update problem
• Metrical task systems
• Odds algorithm
• Paging Problem
• Real-time computing
• Secretary problem
• Ski rental problem
• Linear search problem
• Search games
• Algorithms for calculating variance
• Bandit problem
• algorithme d'Ukkonen

Bibliographie

• (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)

Notes et références

Liens externes

• Bibliographie sur les algorithmes en ligne

• Portail de l'informatique théorique