Algorithme d'apprentissage incrémental

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.