Multiplikativ vægtmetode

Den fremgangsmåde til multiplikative vægte eller multiplikativ vægt opdateringsmetode på engelsk, er en algoritmisk metode. Dette er en meta-algoritme sandsynlighed , der vises i mange områder i forskellige former og forskellige navne, såsom algoritmen fiktiv play (i) i spilteori og algoritme Adaboost i machine learning . Det bruges i mange områder af teoretisk datalogi , såsom beregningsgeometri , online algoritmer , derandomisering og lineær optimering .

Princip

Da algoritmen er generisk, er dens beskrivelse og anvendelseskontekst uklar og skal specificeres for hver applikation.

Sammenhæng

Konteksten kan beskrives som følger. Der er en række valg, der skal tages, den ene efter den anden. Efter hver beslutning gives omkostningerne ved hver mulighed, og det er derfor muligt at vide, hvor godt det valgte valg er eller ej. For at træffe disse beslutninger er der n eksperter, der giver en udtalelse for hvert valg. Målet er til sidst at opnå en strategi til at træffe et godt valg. Dette kræver en ekspertvurdering, valg efter valg.

Princip for metoden

Princippet for metoden med multiplikativ vægt er som følger. Hver ekspert tildeles en koefficient kaldet ekspertens vægt. I starten er disse koefficienter lig med 1. I hver runde vælges beslutningen fra en af eksperterne tilfældigt efter en sandsynlighedsfordeling, der er proportional med koefficienterne for eksperterne. Vi har derefter adgang til alle omkostninger, og vi opdaterer koefficienten for hver ekspert ved at gange det med et tal, der tager højde for omkostningerne ved hans beslutning. Jo mere en ekspert har givet gode råd, det vil sige et valg, der viste sig at have en lav pris, jo mere stiger dens koefficient, og omvendt straffer dårlig rådgivning den ekspert, der gav den.

Teknisk beskrivelse

Processen finder sted i T- runder med n eksperter. Omkostningerne ved round robin-beslutninger t er beskrevet af en vektor m (t) ( m i (t) er omkostningen ved beslutningen fra ekspert i ). Vi angiver vægten af eksperten i i runde t . Metoden er som følger. ${\ displaystyle w_ {i} (t)}$

Initialisering: Vælg en reel . Tildel en vægt til hver ekspert . ${\ displaystyle \ eta \ leq 1/2}$ ${\ displaystyle w_ {i} (1): = 1}$

For t fra 1 til T:

Vælg en beslutning i henhold til sandsynlighedsfordelingen hvor . ${\ displaystyle p (t) = \ {w_ {1} (t) / \ Phi (t), ..., w_ {n} (t) / \ Phi (t) \}}$ ${\ displaystyle \ Phi (t) = \ sum _ {i} w_ {i} (t)}$
Overhold omkostningsvektoren . ${\ displaystyle m (t)}$
Opdater vægt på følgende måde: for enhver ekspert i , . ${\ displaystyle w_ {i} (t + 1) = w_ {i} (t) (1- \ eta m_ {i} (t))}$

Ejendomme

For ethvert valg af ekspert i øges de samlede omkostninger, der betales af algoritmen, med en funktion af de betalte omkostninger, hvis valget af ekspert i foretages fra starten. Denne funktion er affin, med en multiplikationsfaktor mindre end 2 og en additiv faktor i rækkefølgen af logaritmen af n . Mere præcist, med de foregående notationer, for alle i , hvis og for alle i og t : ${\ displaystyle \ eta \ leq 1/2}$ ${\ displaystyle m_ {i} (t) \ in [-1,1]}$

${\ displaystyle \ 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}}.}$

Ansøgninger og forskellige former

Der er mange lignende applikationer, specialiseringer og algoritmer.

Algoritmen fiktive spil (in) i spilteori . I denne ramme repræsenterer eksperterne strategier for modstanderen.
Under træning, Adaboost boosting algoritme , men også winnow algoritme (en) .
Den hurtige opløsning af visse problemer med lineær optimering , herunder multi-råvareproblem (in) .
Af tilnærmelsesalgoritmer forholdslog (n) for mange algoritmiske problemer NP-hårdt .
Algoritmer til online konveks optimering .
En derandomiseringsmetode til beregningsgeometri .

Noter og referencer

Fransk oversættelsesreference: Richard Lassaigne, “ Metoden til multiplikative vægte: en tilnærmelsesmeta-algoritme til læring og optimering ” .
Vi finder også "multiplikativ vægtteknik": Bernard Chazelle , " Algorithmique et les sciences " , på Collège de France .
Jeremy Kun, " Den rimelige effektivitet af de multiplikative vægte opdaterer algoritmen " ,27. februar 2017
Sanjeev Arora , Elad Hazan og Satyen Kale, “ The Multiplicative Weights Update Method: a Meta-Algorithm and Applications ”, Theory of Computing , vol. 8, nr . 1, 2012, s. 121-164 ( læs online ).