Algorithme d'apprentissage incrémental

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En informatique, un algorithme d'apprentissage incrémental (anglais : online algorithm) est un algorithme 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 predire le resultat à partir des données d'entrées.

Principe[modifier | modifier le code]

Un algorithme d'apprentissage incrémental commence donc son travail sans avoir une vision globale sur la totalité des données qu'il va recevoir. À l'inverse, un algorithme hors ligne (offline), connait lui toutes les données avant de commencer à traiter le problème correspondant. Par exemple, le tri par sélection requiert que l'intégralité de la liste à trier soit fournie avant qu'il puisse commencer à la trier, tandis que le tri par insertion a plus de souplesse. Il peut recevoir la liste à trier au compte-gouttes et néanmoins commencer à trier. Un autre exemple est celui du calcul de la moyenne arithmétique d'un ensemble de valeur. En possession de l'intégralité des valeurs on effectuera le calcul: moyenne =\frac{x_1+x_2+\ldots+x_n}n. Tandis que dans la version incrémentale on effetuera le calcul (incrément i) moyenne_i =\frac{moyenne_{i-1} * (i-1) + x_i}i à chaque découverte d'une nouvelle valeur.

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 au final 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çu dans le passées), dynamic algorithm (centré sur la complexité en temps pour manipuler les solutions à des problèmes à inputs online) et apprentissage en ligne.

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[modifier | modifier le code]

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[modifier | modifier le code]

Références[modifier | modifier le code]

Lien externe[modifier | modifier le code]