Méthode des poids multiplicatifsLa méthode des poids multiplicatifs[1],[2] ou multiplicative weight update method en anglais, est une méthode algorithmique. C'est un méta-algorithme probabiliste qui apparaît dans de nombreux domaines sous diverses formes et divers noms, par exemple l'algorithme fictitious play (en) en théorie des jeux et l'algorithme Adaboost en apprentissage automatique. Elle est utilisée dans de nombreux domaines de l'informatique théorique, comme la géométrie algorithmique, les algorithmes en ligne, la dérandomisation et l'optimisation linéaire. PrincipeComme l'algorithme est générique, sa description et son contexte d'utilisation sont vagues et doivent être précisés pour chaque application. ContexteLe contexte peut être décrit de la manière suivante. Il y a une série de choix à faire, les uns après les autres. Après chaque décision, le coût de chaque option est donné, et il est donc possible de savoir à quel point le choix fait est bon ou non. Pour prendre ces décisions, il y a n experts, donnant un avis pour chaque choix. Le but est d'obtenir à terme une stratégie permettant de faire un bon choix. Cela passe par une évaluation des experts choix après choix. Principe de la méthodeLe principe de la méthode des poids multiplicatifs est le suivant[3],[4]. À chaque expert on attribue un coefficient appelé le poids de l'expert. Au départ ces coefficient sont égaux à 1. À chaque ronde, on choisit la décision d'un des experts aléatoirement selon une distribution de probabilité qui est proportionnelle aux coefficients des experts. On a ensuite accès à tous les coûts et l'on met à jour le coefficient de chaque expert en le multipliant par un nombre qui prend en compte le coût de sa décision. Plus un expert a donné un bon conseil, c'est-à-dire un choix qui s'est révélé avoir un petit coût, plus sont coefficient augmente et inversement, un mauvais conseil pénalise l'expert qui l'a donné. Description techniqueLe processus a lieu en T rondes, avec n experts. Le coût des décisions à la ronde t est décrit par un vecteur m(t) (mi(t) est le coût de la décision de l'expert i). On note le poids de l'expert i à la ronde t. La méthode est la suivante[4]. Initialisation: Choisir un réel . Associer à chaque expert un poids . Pour t allant de 1 à T :
PropriétésPour tout choix d'expert i, le coût total payé par l'algorithme est majoré par une fonction du coût payé si l'on fait le choix de l'expert i dès le départ. Cette fonction est affine, avec un facteur multiplicatif inférieur à 2 et un facteur additif de l'ordre du logarithme de n. Plus précisément, avec les notations précédentes, pour tout i, si et pour tout i et t :
Applications et différentes formesOn compte de nombreuses applications, spécialisations et algorithmes proches[4],[3].
Notes et références
|