LPBoost - LPBoost - Wikipedia

Posílení lineárního programování (LPBoost) je klasifikovaný pod dohledem z posílení rodina klasifikátorů. LPBoost maximalizuje a okraj mezi tréninkovými vzorky různých tříd a tudíž také patří do třídy supervizních klasifikačních algoritmů s maximalizací marže. Zvažte klasifikační funkci

${ displaystyle f: { mathcal {X}} do {- 1,1 },}$

který klasifikuje vzorky z prostoru ${ displaystyle { mathcal {X}}}$ do jedné ze dvou tříd s označením 1 a -1. LPBoost je algoritmus Učit se taková klasifikační funkce dostala sadu příkladů školení se známými štítky tříd. LPBoost je a strojové učení Tato technika je zvláště vhodná pro aplikace společné klasifikace a výběru funkcí ve strukturovaných doménách.

Přehled LPBoost

Stejně jako ve všech posilovacích klasifikátorech má funkce konečné klasifikace tvar

${ displaystyle f ({ boldsymbol {x}}) = součet _ {j = 1} ^ {J} alpha _ {j} h_ {j} ({ boldsymbol {x}}),}$

kde ${ displaystyle alpha _ {j}}$ jsou záporné váhy pro slabý klasifikátory ${ displaystyle h_ {j}: { mathcal {X}} do {- 1,1 }}$. Každý jednotlivý slabý klasifikátor ${ displaystyle h_ {j}}$ může být o něco lepší než náhodné, ale výsledná lineární kombinace mnoha slabých klasifikátorů může fungovat velmi dobře.

Konstrukce LPBoost ${ displaystyle f}$ počínaje prázdnou sadou slabých klasifikátorů. Iterativně je vybrán, přidán a všechny váhy jeden slabý klasifikátor, který se přidá do sady zvažovaných slabých klasifikátorů. ${ displaystyle { boldsymbol { alpha}}}$ pro aktuální sadu slabých klasifikátorů jsou upraveny. To se opakuje, dokud nezůstanou žádné slabé klasifikátory, které chcete přidat.

Vlastnost, že jsou upraveny všechny váhy klasifikátoru v každé iteraci, je známá jako zcela korektivní vlastnictví. Metody včasného posílení, jako je AdaBoost nemají tuto vlastnost a konvergují pomaleji.

Lineární program

Obecněji řečeno ${ displaystyle { mathcal {H}} = {h ( cdot; omega) | omega v Omega }}$ být možná nekonečnou sadou slabých klasifikátorů, nazývaných také hypotézy. Jeden způsob, jak si zapsat problém, který LPBoost řeší, je jako lineární program s nekonečně mnoha proměnnými.

Prvotní lineární program LPBoost optimalizující vektor záporné hmotnosti ${ displaystyle { boldsymbol { alpha}}}$, nezáporný vektor ${ displaystyle { boldsymbol { xi}}}$ ochablých proměnných a okraj ${ displaystyle rho}$ je následující.

${ displaystyle { begin {array} {cl} { podmnožina {{ boldsymbol { alpha}}, { boldsymbol { xi}}, rho} { min}} & - rho + D sum _ {n = 1} ^ { ell} xi _ {n} { textrm {sb.t.}} & sum _ { omega in Omega} y_ {n} alpha _ { omega} h ({ boldsymbol {x}} _ {n}; omega) + xi _ {n} geq rho, qquad n = 1, dots, ell, & sum _ { omega in Omega} alpha _ { omega} = 1, & xi _ {n} geq 0, qquad n = 1, dots, ell, & alpha _ { omega} geq 0, qquad omega in Omega, & rho in { mathbb {R}}. end {pole}}}$

Všimněte si účinků uvolněných proměnných ${ displaystyle { boldsymbol { xi}} geq 0}$: jejich jedna norma je v objektivní funkci penalizována konstantním faktorem ${ displaystyle D}$, což - je-li dostatečně malé - vždy vede k prvotnímu proveditelnému lineárnímu programu.

Zde jsme převzali notaci prostoru parametrů ${ displaystyle Omega}$, tak, že na výběr ${ displaystyle omega v Omega}$ slabý klasifikátor ${ displaystyle h ( cdot; omega): { mathcal {X}} do {- 1,1 }}$ je jednoznačně definována.

Když byl výše uvedený lineární program poprvé zapsán v raných publikacích o posilovacích metodách, byl ignorován jako neřešitelný kvůli velkému počtu proměnných ${ displaystyle { boldsymbol { alpha}}}$. Teprve později bylo zjištěno, že takové lineární programy lze skutečně efektivně vyřešit klasickou technikou generování sloupců.

Generování sloupců pro LPBoost

V lineární program A sloupec odpovídá primární proměnné. Generování sloupců je technika řešení velkých lineárních programů. Obvykle funguje v omezeném problému, který se zabývá pouze podmnožinou proměnných. Generováním iterativních proměnných iterativně a na vyžádání se nakonec obnoví původní neomezený problém se všemi proměnnými. Chytrým výběrem sloupců pro generování problému lze vyřešit tak, že zatímco stále zaručuje, že získané řešení bude optimální pro původní úplný problém, musí být vytvořen pouze malý zlomek sloupců.

LPBoost duální problém

Sloupce v primárním lineárním programu odpovídají řádkům v duální lineární program. Ekvivalentní duální lineární program LPBoost je následující lineární program.

${ displaystyle { begin {array} {cl} { podmnožina {{ boldsymbol { lambda}}, gamma} { max}} & gamma { textrm {sb.t.}} & součet _ {n = 1} ^ { ell} y_ {n} h ({ boldsymbol {x}} _ {n}; omega) lambda _ {n} + gamma leq 0, qquad omega in Omega, & 0 leq lambda _ {n} leq D, qquad n = 1, dots, ell, & sum _ {n = 1} ^ { ell} lambda _ {n} = 1, & gamma in mathbb {R}. end {pole}}}$

Pro lineární programy optimální hodnota primátů a dvojí problém jsou rovny. U výše uvedených prvotních a duálních problémů se optimální hodnota rovná záporné „měkké rezervě“. Měkká marže je velikost marže oddělující pozitivní od negativních tréninkových instancí minus pozitivní ochablé proměnné, které jsou penalizovány za vzorky porušující marži. Měkká rezerva tedy může být pozitivní, i když ne všechny vzorky jsou klasifikační funkcí lineárně odděleny. Ta se nazývá „tvrdá marže“ nebo „realizovaná marže“.

Kritérium konvergence

Zvažte podmnožinu uspokojených omezení v duálním problému. Pro jakoukoli konečnou podmnožinu můžeme vyřešit lineární program a uspokojit tak všechna omezení. Pokud bychom dokázali, že ze všech omezení, která jsme nepřidali k dvojímu problému, není porušeno jediné omezení, dokázali bychom, že řešení našeho omezeného problému je ekvivalentní řešení původního problému. Více formálně, pojďme ${ displaystyle gamma ^ {*}}$ být optimální hodnotou objektivní funkce pro jakoukoli omezenou instanci. Poté můžeme formulovat problém s hledáním „nejvíce porušeného omezení“ v původním prostoru problému, konkrétně s hledáním ${ displaystyle omega ^ {*} v Omega}$ tak jako

${ displaystyle omega ^ {*} = { podmnožina { omega v Omega} { textrm {argmax}}} sum _ {n = 1} ^ { ell} y_ {n} h ({ boldsymbol {x}} _ {n}; omega) lambda _ {n}.}$

To znamená, že prohledáváme prostor ${ displaystyle { mathcal {H}}}$ pro jednoho rozhodnutí pařez ${ displaystyle h ( cdot; omega ^ {*})}$ maximalizovat levou stranu dvojího omezení. Pokud omezení nemůže být porušeno žádným výběrem rozhodovacího pařezu, žádné z odpovídajících omezení nemůže být aktivní v původním problému a omezený problém je ekvivalentní.

Konstanta penalizace ${ displaystyle D}$

Kladná hodnota penalizační konstanty ${ displaystyle D}$ je třeba najít pomocí výběr modelu techniky. Pokud se však rozhodneme ${ displaystyle D = { frac {1} { ell nu}}}$, kde ${ displaystyle ell}$ je počet vzorků školení a ${ displaystyle 0 < nu <1}$, pak nový parametr ${ displaystyle nu}$ má následující vlastnosti.

• ${ displaystyle nu}$ je horní hranice zlomku tréninkových chyb; to je, pokud ${ displaystyle k}$ označuje počet nesprávně klasifikovaných tréninkových vzorků ${ displaystyle { frac {k} { ell}} leq nu}$.
• ${ displaystyle nu}$ je dolní mez na zlomku tréninkových vzorků venku nebo na okraji.

Algoritmus

• Vstup:
  • Tréninková sada ${ displaystyle X = {{ boldsymbol {x}} _ {1}, tečky, { boldsymbol {x}} _ { ell} }}$, ${ displaystyle { boldsymbol {x}} _ {i} v { mathcal {X}}}$
  • Školicí štítky ${ displaystyle Y = {y_ {1}, tečky, y _ { ell} }}$, ${ displaystyle y_ {i} in {- 1,1 }}$
  • Konvergenční práh ${ displaystyle theta geq 0}$
• Výstup:
  • Klasifikační funkce ${ displaystyle f: { mathcal {X}} do {- 1,1 }}$

1. Inicializace
   1. Váhy, uniforma ${ displaystyle lambda _ {n} leftarrow { frac {1} { ell}}, quad n = 1, dots, ell}$
   2. Okraj ${ displaystyle gamma leftarrow 0}$
   3. Počet hypotéz ${ displaystyle J leftarrow 1}$
2. Opakovat
   1. ${ displaystyle { hat {h}} leftarrow { underset { omega in Omega} { textrm {argmax}}} sum _ {n = 1} ^ { ell} y_ {n} h ( { boldsymbol {x}} _ {n}; omega) lambda _ {n}}$
   2. -li ${ displaystyle sum _ {n = 1} ^ { ell} y_ {n} { hat {h}} ({ boldsymbol {x}} _ {n}) lambda _ {n} + gamma leq theta}$ pak
      1. přestávka
   3. ${ displaystyle h_ {J} leftarrow { hat {h}}}$
   4. ${ displaystyle J leftarrow J + 1}$
   5. ${ displaystyle ({ boldsymbol { lambda}}, gamma) leftarrow}$ řešení duální LPBoost
   6. ${ displaystyle { boldsymbol { alpha}} leftarrow}$ Lagrangeovští multiplikátoři řešení dvojitého problému LPBoost
3. ${ displaystyle f ({ boldsymbol {x}}): = { textrm {sign}} left ( sum _ {j = 1} ^ {J} alpha _ {j} h_ {j} ({ tučný symbol {x}}) vpravo)}$

Všimněte si, že pokud je práh konvergence nastaven na ${ displaystyle theta = 0}$ získaným řešením je globální optimální řešení výše uvedeného lineárního programu. V praxi, ${ displaystyle theta}$ je nastavena na malou kladnou hodnotu, aby bylo možné rychle získat dobré řešení.

Realizovaná marže

Skutečná rezerva oddělující tréninkové vzorky se nazývá realizovaná marže a je definován jako

${ displaystyle rho ({ boldsymbol { alpha}}): = min _ {n = 1, dots, ell} y_ {n} sum _ { alpha _ { omega} v Omega } alpha _ { omega} h ({ boldsymbol {x}} _ {n}; omega).}$

Realizovaná marže může a bude obvykle záporná v prvních iteracích. Pro prostor hypotézy, který umožňuje vyčlenění jakéhokoli jednotlivého vzorku, jak je tomu obvykle, bude realizovaná marže nakonec konvergovat k nějaké pozitivní hodnotě.

Záruka konvergence

I když je prokázáno, že výše uvedený algoritmus konverguje, na rozdíl od jiných posilovacích formulací, jako je AdaBoost a TotalBoost, pro LPBoost nejsou známy žádné hranice konvergence. V praxi je však známo, že LPBoost konverguje rychle, často rychleji než jiné formulace.

Základní studenti

LPBoost je souborové učení metodou a tudíž nediktuje výběr základních žáků, prostor hypotéz ${ displaystyle { mathcal {H}}}$. Demiriz a kol. ukázal, že za mírných předpokladů lze použít jakéhokoli základního studenta. Pokud jsou základní žáci obzvláště jednoduchí, jsou často označováni jako rozhodovací pařezy.

Počet základních studentů, kteří se v rámci Boostingu běžně používají v literatuře, je velký. Například pokud ${ displaystyle { mathcal {X}} subseteq { mathbb {R}} ^ {n}}$, základní student může být lineární měkká marže podporovat vektorový stroj. Nebo ještě jednodušší, jednoduchý pahýl formuláře

${ displaystyle h ({ boldsymbol {x}}; omega v {1, -1 }, p v {1, tečky, n }, t v { mathbb {R}} ): = left {{ begin {array} {cl} omega & { textrm {if ~}} { boldsymbol {x}} _ {p} leq t - omega & { textrm {jinak}} end {pole}} vpravo ..}$

Výše uvedené pařezy vypadají pouze v jedné dimenzi ${ displaystyle p}$ vstupního prostoru a jednoduše prahuje příslušný sloupec vzorku pomocí konstantní prahové hodnoty ${ displaystyle t}$. Poté se může rozhodnout v obou směrech, v závislosti na ${ displaystyle omega}$ pro kladnou nebo zápornou třídu.

Vzhledem k vahám pro tréninkové vzorky sestrojení optimálního rozhodovacího pahýlu výše uvedeného formuláře jednoduše zahrnuje prohledávání všech sloupců vzorků a určení ${ displaystyle p}$, ${ displaystyle t}$ a ${ displaystyle omega}$ za účelem optimalizace funkce zesílení.

Reference

• Posílení lineárního programování pomocí generování sloupců, A. Demiriz a K.P. Bennett a J. Shawe-Taylor. Publikováno 2002 v Kluwer Machine Learning 46, strany 225–254.