A multiplikatív súlyok vagy a multiplikatív súlyfrissítési módszer angolul algoritmikus módszer. Ez egy meta-algoritmus valószínűsége , hogy úgy tűnik, sok területen különböző formákban és különböző nevek, mint például az algoritmus fiktív lejátszás (a) a játékelmélet és az algoritmus Adaboost a gépi tanulás . Az elméleti számítástechnika számos területén alkalmazzák , például a számítási geometriában , az online algoritmusokban , a derandomizálásban és a lineáris optimalizálásban .
Mivel az algoritmus általános, annak leírása és felhasználási környezete homályos, és minden alkalmazáshoz meg kell adni.
A kontextus a következőképpen írható le. Sorra kell választani, egymás után. Minden döntés után megadják az egyes lehetőségek költségeit, és ezért meg lehet tudni, hogy a választás mennyire jó vagy sem. E döntések meghozatalához n szakértő van, akik véleményt mondanak az egyes választásokról. A cél egy stratégia megszerzése a jó választáshoz. Ehhez szakértői értékelésre, választás utáni választásra van szükség.
A multiplikatív súly módszer alapelve a következő. Minden szakértőhöz hozzárendelik a szakértő súlyának nevezett együtthatót. Eleinte ezek az együtthatók megegyeznek 1. Minden fordulóban az egyik szakértő döntését véletlenszerűen választják meg egy valószínűségi eloszlás szerint, amely arányos a szakértők együtthatóival. Ezután hozzáférünk az összes költséghez, és frissítjük az egyes szakértők együtthatóját, megszorozva azt egy számmal, amely figyelembe veszi a döntésének költségeit. Minél inkább egy szakértő adott jó tanácsot, vagyis olyan választást, amelynek alacsony költségei voltak, annál inkább nő az együtthatója, és fordítva, a rossz tanácsok megbüntetik a szakértőt, aki adta.
A folyamat T fordulóban zajlik , n szakértővel. A t körmérkőzéses döntések költségét m (t) vektor írja le ( m i (t) az i szakértő döntésének költsége ). Jelöljük az i szakértő súlyát a t körben . A módszer a következő.
Inicializálás: Válasszon egy valós értéket . Rendeljen súlyt minden szakértőhöz .
1-től T-ig terjedő t:
Bármely i szakértő választása esetén az algoritmus által fizetett teljes költséget megnöveli a fizetett költség függvénye, ha az i szakértőt kezdettől fogva választják. Ez a függvény affin, 2-nél kisebb szorzótényezővel és n logaritmus nagyságrendű additív faktorral . Pontosabban, az előző jelölésekkel, minden i-re , ha és mindenre i és t :
Sok hasonló alkalmazás, specializáció és algoritmus létezik.