Méthode des poids multiplicatifs

La méthode des poids multiplicatifs 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.

Principe

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.

Contexte

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éthode

Le principe de la méthode des poids multiplicatifs est le suivant. À 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 technique

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) (m_i(t) est le coût de la décision de l'expert i). On note $w_{i}(t)$ le poids de l'expert i à la ronde t. La méthode est la suivante.

Initialisation: Choisir un réel $\eta \leq 1/2$. Associer à chaque expert un poids $w_{i}(1):=1$.

Pour t allant de 1 à T :

• Choisir une décision, selon la distribution de probabilité $p(t)=\{w_{1}(t)/\Phi (t),...,w_{n}(t)/\Phi (t)\}$ où $\Phi (t)=\sum _{i}w_{i}(t)$.
• Observer le vecteur de coûts $m(t)$.
• Mettre à jour les poids de la façon suivante: pour tout expert i, $w_{i}(t+1)=w_{i}(t)(1-\eta m_{i}(t))$.

Propriétés

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 $\eta \leq 1/2$ et $m_{i}(t)\in [-1,1]$ pour tout i et t :

$\sum _{t=1}^{T}m(t)p(t)\leq \sum _{t=1}^{T}m_{i}(t)+\eta \sum _{t=1}^{T}|m_{i}(t)|+{\frac {\log n}{\eta }}.$

Applications et différentes formes

On compte de nombreuses applications, spécialisations et algorithmes proches.

• L'algorithme fictitious play (en) en théorie des jeux. Dans ce cadre, les experts représente des stratégies pour l'adversaire.
• En apprentissage, l'algorithme de boosting Adaboost, mais aussi l'algorithme winnow (en).
• La résolution rapide de certains problème d'optimisation linéaire, notamment le problème de flot multi-commodités.
• Des algorithmes d'approximation de ratio log(n) pour de nombreux problèmes algorithmiques NP-difficiles.
• Des algorithmes pour l'optimisation convexe en ligne.
• Une méthode de dérandomisation pour la géométrie algorithmique.