Uvolněný algoritmus naplněný okrajem - Margin-infused relaxed algorithm - Wikipedia

Uvolněný algoritmus s infuzí marží (MIRA)^[1] je strojové učení algoritmus, an online algoritmus pro klasifikace více tříd problémy. Je navržen tak, aby se naučil sadu parametrů (vektor nebo matice) zpracováním všech uvedených příkladů tréninku jeden po druhém a aktualizací parametrů podle každého příkladu tréninku, aby byl aktuální příklad tréninku správně klasifikován pomocí okraj proti nesprávné klasifikaci, která je alespoň tak velká jako jejich ztráta.^[2] Změna parametrů je udržována co nejmenší.

Volala verze pro dvě třídy binární MIRA^[1] zjednodušuje algoritmus tím, že nevyžaduje řešení a kvadratické programování problém (viz níže). Při použití v jeden proti všem konfigurace, binární MIRA může být rozšířen na studenta více tříd, který se blíží plné MIRA, ale může být rychlejší trénovat.

Tok algoritmu^[3]^[4] vypadá takto:

Algoritmus MIRA Vstup: Příklady školení  ${ displaystyle T = {x_ {i}, y_ {i} }}$   Výstup: Sada parametrů  ${ displaystyle w}$

   ${ displaystyle i}$  ← 0,  ${ displaystyle w ^ {(0)}}$  ← 0  pro  ${ displaystyle n}$  ← 1 na  ${ displaystyle N}$     pro  ${ displaystyle t}$  ← 1 na  ${ displaystyle | T |}$        ${ displaystyle w ^ {(i + 1)}}$  ← aktualizace  ${ displaystyle w ^ {(i)}}$  podle  ${ displaystyle {x_ {t}, y_ {t} }}$        ${ displaystyle i}$  ←  ${ displaystyle i + 1}$     konec pro  konec pro  vrátit se  ${ displaystyle { frac { sum _ {j = 1} ^ {N krát | T |} w ^ {(j)}} {N krát | T |}}}$

„←“ označuje úkol. Například, "největší ← položka"znamená, že hodnota největší změny hodnoty položka.
"vrátit se"ukončí algoritmus a odešle následující hodnotu.

Krok aktualizace je poté formován jako a kvadratické programování^[2] problém: Najít ${ displaystyle min | w ^ {(i + 1)} - w ^ {(i)} |}$ , aby ${ displaystyle skóre (x_ {t}, y_ {t}) - skóre (x_ {t}, y ') geq L (y_ {t}, y') za všechny y '}$ , tj. skóre aktuálního správného tréninku ${ displaystyle y}$ musí být větší než skóre jakéhokoli jiného možného ${ displaystyle '$ alespoň o jeho ztrátu (počet chyb) ${ displaystyle '$ ve srovnání s ${ displaystyle y}$ .

Reference

^ ^A ^b Crammer, Koby; Singer, Yoram (2003). „Ultrakonzervativní online algoritmy pro řešení problémů s více třídami“. Journal of Machine Learning Research. 3: 951–991.
^ ^A ^b McDonald, Ryan; Crammer, Koby; Pereira, Fernando (2005). „Online školení s velkou rezervou analyzátorů závislostí“ (PDF). Sborník 43. výročního zasedání ACL. Sdružení pro výpočetní lingvistiku. str. 91–98.
^ Watanabe, T. et al (2007): „Online Large Margin Training pro statistický strojový překlad“. V: Sborník příspěvků ze společné konference 2007 o empirických metodách ve zpracování přirozeného jazyka a výpočetním učení přirozeného jazyka, 764–773.
^ Bohnet, B. (2009): Efektivní analýza syntaktických a sémantických závislostních struktur. Sborník z konference o studiu přirozeného jazyka (CoNLL), Boulder, 67–72.

externí odkazy

obdivuhodný - Implementace MIRA v C ++
Miralium - Implementace MIRA v Javě
Implementace MIRA pro Mahout v Hadoop

[crammer-singer2003-1] A ^b Crammer, Koby; Singer, Yoram (2003). „Ultrakonzervativní online algoritmy pro řešení problémů s více třídami“. Journal of Machine Learning Research. 3: 951–991.

[mcdonald-etal2005-2] A ^b McDonald, Ryan; Crammer, Koby; Pereira, Fernando (2005). „Online školení s velkou rezervou analyzátorů závislostí“ (PDF). Sborník 43. výročního zasedání ACL. Sdružení pro výpočetní lingvistiku. str. 91–98.

[3] Watanabe, T. et al (2007): „Online Large Margin Training pro statistický strojový překlad“. V: Sborník příspěvků ze společné konference 2007 o empirických metodách ve zpracování přirozeného jazyka a výpočetním učení přirozeného jazyka, 764–773.

[4] Bohnet, B. (2009): Efektivní analýza syntaktických a sémantických závislostních struktur. Sborník z konference o studiu přirozeného jazyka (CoNLL), Boulder, 67–72.

[1]

[2]

[3]

[4]