Metoda multiplikativní hmotnosti

Způsob multiplikativních závaží nebo způsobu aktualizace multiplikativní hmotnosti v angličtině, je algoritmický metoda. Jedná se o pravděpodobnost meta-algoritmu, která se objevuje v mnoha oblastech v různých formách a různých jménech, jako je algoritmus fiktivní hry (ne) v teorii her a algoritmus Adaboost ve strojovém učení . Používá se v mnoha oblastech teoretické informatiky , jako je výpočetní geometrie , online algoritmy , derandomizace a lineární optimalizace .

Zásada

Protože je algoritmus obecný, jeho popis a kontext použití jsou vágní a musí být specifikovány pro každou aplikaci.

Kontext

Kontext lze popsat následovně. Je třeba učinit řadu možností, jeden po druhém. Po každém rozhodnutí jsou uvedeny náklady na každou možnost, a proto je možné vědět, jak dobrá je volba nebo ne. Aby bylo možné učinit tato rozhodnutí, existuje n odborníků, kteří ke každé volbě vyjadřují názor. Cílem je nakonec získat strategii pro dobrou volbu. To vyžaduje odborné posouzení, výběr za výběrem.

Princip metody

Princip metody multiplikativní hmotnosti je následující. Každému odborníkovi je přidělen koeficient nazývaný jeho váha. Na začátku jsou tyto koeficienty rovny 1. V každém kole je rozhodnutí jednoho z odborníků zvoleno náhodně podle rozdělení pravděpodobnosti, které je úměrné koeficientům odborníků. Poté máme přístup ke všem nákladům a aktualizujeme koeficient každého odborníka vynásobením číslem, které zohledňuje náklady na jeho rozhodnutí. Čím více expert dává dobrou radu, to znamená volbu, která má nízkou cenu, tím více se zvyšuje jeho koeficient a naopak špatná rada penalizuje experta, který ji dal.

Technický popis

Proces probíhá v T kolech s n experty. Náklady na kruhových rozhodnutí robin t je popsán vektor m (t) ( m i (t), jsou náklady na rozhodnutí odborníka i ). Označíme váhu experta i v kole t . Metoda je následující. ${\ displaystyle w_ {i} (t)}$

Inicializace: Vyberte skutečný . Přiřaďte každému odborníkovi váhu . ${\ displaystyle \ eta \ leq 1/2}$ ${\ displaystyle w_ {i} (1): = 1}$

Pro t v rozmezí od 1 do T:

Vyberte rozhodnutí podle rozdělení pravděpodobnosti kde . ${\ displaystyle p (t) = \ {w_ {1} (t) / \ Phi (t), ..., w_ {n} (t) / \ Phi (t) \}}$ ${\ displaystyle \ Phi (t) = \ součet _ {i} w_ {i} (t)}$
Sledujte nákladový vektor . ${\ displaystyle m (t)}$
Aktualizace hmotnost takto: pro každou odborníka i , . ${\ displaystyle w_ {i} (t + 1) = w_ {i} (t) (1- \ eta m_ {i} (t))}$

Vlastnosti

U jakékoli volby experta i se celkové náklady zaplacené algoritmem zvýší o funkci zaplacených nákladů, pokud je volba experta i provedena od začátku. Tato funkce je afinní, s multiplikativním faktorem menším než 2 a aditivním faktorem řádu logaritmu n . Přesněji, s předchozími notacemi, pro všechny i , if a pro všechny i a t : ${\ displaystyle \ eta \ leq 1/2}$ ${\ displaystyle m_ {i} (t) \ v [-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}}.}$

Aplikace a různé formy

Existuje mnoho podobných aplikací, specializací a algoritmů.

Algoritmus fiktivní hru (v) v teorii her . V tomto rámci představují odborníci strategie pro protivníka.
V tréninku se Adaboost posílení algoritmus , ale také oddělit zrno od plev algoritmus (en) .
Rychlé řešení určitých problémů lineární optimalizace , včetně problému s multikomoditním tokem (in) .
Aproximačních algoritmů je poměr log (n) pro mnoho algoritmických problémů NP-hard .
Algoritmy pro online konvexní optimalizaci .
Metoda derandomizace pro výpočetní geometrii .

Poznámky a odkazy

Odkaz na francouzský překlad: Richard Lassaigne, „ Metoda multiplikativních vah: aproximační meta-algoritmus pro učení a optimalizaci “ .
Na Collège de France také najdeme „techniku multiplikativních vah“: Bernard Chazelle , „ Algorithmique et les sciences “ .
Jeremy Kun, „ Přiměřená účinnost algoritmu aktualizace multiplikativní váhy “ ,27. února 2017
Sanjeev Arora , Elad Hazan a Satyen Kale, „ Metoda aktualizace multiplikativní váhy: meta-algoritmus a aplikace “, Theory of Computing , sv. 8, n o 1, 2012, str. 121-164 ( číst online ).