Méthode des poids multiplicatifs

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

PrincipeModifier

Comme l'algorithme est générique, sa description et son contexte d'utilisation sont vagues et doivent être précisés pour chaque application.

ContexteModifier

Le 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éthodeModifier

Le 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 techniqueModifier

Le 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 :

  • Choisir une décision, selon la distribution de probabilité   .
  • Observer le vecteur de coûts  .
  • Mettre à jour les poids de la façon suivante: pour tout expert i,  .

PropriétésModifier

Pour 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 formesModifier

On compte de nombreuses applications, spécialisations et algorithmes proches[4],[3].

Notes et référencesModifier

  1. Référence de la traduction en français : Richard Lassaigne, « La méthode des poids multiplicatifs : un méta-algorithme d’approximation pour l’apprentissage et l’optimisation ».
  2. On trouve aussi « technique des poids multiplicatifs » : Bernard Chazelle, « L'algorithmique et les sciences », sur Collège de France.
  3. a b et c Jeremy Kun, « The Reasonable Effectiveness of the Multiplicative Weights Update Algorithm »,
  4. a b et c Sanjeev Arora, Elad Hazan et Satyen Kale, « The Multiplicative Weights Update Method: a Meta-Algorithm and Applications », Theory of Computing, vol. 8, no 1,‎ , p. 121-164 (lire en ligne).