LPBoost

Linear Programming Boosting ( LPBoost ) är en övervakad klassificerare från boostningsfamiljen av klassificerare. LPBoost maximerar en marginal mellan träningsprover av olika klasser och tillhör därför också klassen av marginalmaximerande övervakade klassificeringsalgoritmer. Överväg en klassificeringsfunktion

$f:{\mathcal {X}}\to \{-1,1\},$

som klassificerar sampel från ett mellanslag ${\mathcal {X}}$ i en av två klasser, märkta 1 respektive -1. LPBoost är en algoritm för att lära sig en sådan klassificeringsfunktion givet en uppsättning träningsexempel med kända klassetiketter. LPBoost är en maskininlärningsteknik och speciellt lämpad för tillämpningar av gemensam klassificering och funktionsval i strukturerade domäner.

LPBoost översikt

Som i alla förstärkande klassificerare är den slutliga klassificeringsfunktionen av formen

$f({\boldsymbol {x}})=\summa _{j=1}^{J}\alpha _{j} h_{j}({\boldsymbol {x}}),$

där $\alpha _{j}$ är icke-negativa viktningar för svaga klassificerare $h_{j}:{\mathcal {X}}\to \ {-1,1\}$ . Varje enskild svag klassificerare $h_{j}$ kan vara lite bättre än slumpmässig, men den resulterande linjära kombinationen av många svaga klassificerare kan fungera mycket bra.

LPBoost konstruerar $f$ genom att börja med en tom uppsättning svaga klassificerare. Iterativt väljs, läggs till en enda svag klassificerare att lägga till i uppsättningen av betraktade svaga klassificerare och alla vikter ${\boldsymbol {\alpha }}$ för den aktuella uppsättningen av svaga klassificerare justeras. Detta upprepas tills det inte finns några svaga klassificerare att lägga till.

Egenskapen att alla klassificerares vikter justeras i varje iteration är känd som totalkorrigerande egenskap. Tidiga boostingmetoder, som AdaBoost, har inte denna egenskap och konvergerar långsammare.

Linjärt program

Mer allmänt, låt ${\displaystyle {\mathcal {H}}=\{h(\cdot ;\omega )|\omega \in \Omega \}} vara$ den möjligen oändliga uppsättningen svaga klassificerare, även kallade hypoteser . Ett sätt att skriva ner problemet LPBoost löser är som ett linjärt program med oändligt många variabler.

Det primära linjära programmet för LPBoost, optimerar över den icke-negativa viktvektorn ${\displaystyle {\boldsymbol {\alpha }}} ,$ den icke-negativa vektorn ${\boldsymbol {\xi }}$ för slackvariabler och marginalen $\rho$ är följande.

${\begin{array}{cl}{\underset {{\boldsymbol {\alpha }},{\boldsymbol {\xi }},\rho }{\min }}&-\rho +D\summa _{n=1}^{\ell }\xi _{n}\\{\textrm {sb.t.}}&\summa _{\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{array}}$

Notera effekterna av slackvariabler ${\boldsymbol {\xi }}\geq 0$ : deras ennorm bestraffas i objektivfunktionen med en konstant faktor ${\displaystyle D} ,$ som – om tillräckligt liten — leder alltid till ett primärt genomförbart linjärt program.

Här använde vi notationen av ett parameterutrymme $\Omega$ , så att för ett val $\omega \in \Omega$ den svaga klassificeraren $h(\cdot ;\omega ):{\mathcal {X}}\to \{-1,1\}$ är unikt definierad.

När ovanstående linjära program först skrevs ned i tidiga publikationer om förstärkningsmetoder ignorerades det som svårhanterligt på grund av det stora antalet variabler ${\boldsymbol {\alpha }}$ . Först senare upptäcktes det att sådana linjära program verkligen kan lösas effektivt med den klassiska tekniken för kolumngenerering .

Kolumngenerering för LPBoost

I ett linjärt program motsvarar en kolumn en primalvariabel. Kolumngenerering är en teknik för att lösa stora linjära program. Det fungerar vanligtvis i ett begränsat problem, som endast hanterar en delmängd av variabler. Genom att generera primala variabler iterativt och på begäran, återställs så småningom det ursprungliga obegränsade problemet med alla variabler. Genom att smart välja kolumnerna för att generera kan problemet lösas så att samtidigt som man garanterar att den erhållna lösningen är optimal för det ursprungliga hela problemet, behöver bara en liten bråkdel av kolumner skapas.

LPBoost dubbelt problem

Kolumner i det primära linjära programmet motsvarar rader i det dubbla linjära programmet . Det motsvarande dubbla linjära programmet för LPBoost är följande linjära program.

${\begin{array}{cl}{\underset {{\boldsymbol {\lambda }},\gamma }{\max }}&\gamma \\{\textrm {sb.t.}}&\ summa _{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{array}}$

För linjära program är det optimala värdet av det primära och det dubbla problemet lika. För ovanstående primära och dubbla problem är det optimala värdet lika med den negativa "mjuka marginalen". Den mjuka marginalen är storleken på marginalen som skiljer positiva från negativa träningstillfällen minus positiva slackvariabler som medför straff för marginalöverträdande prover. Således kan den mjuka marginalen vara positiv även om inte alla prover är linjärt separerade av klassificeringsfunktionen. Den senare kallas för "hård marginal" eller "realiserad marginal".

Konvergenskriterium

Betrakta en delmängd av de uppfyllda begränsningarna i det dubbla problemet. För vilken finit delmängd som helst kan vi lösa det linjära programmet och därmed uppfylla alla begränsningar. Om vi ​​kunde bevisa att av alla de restriktioner som vi inte lagt till det dubbla problemet inte någon enskild restriktion överträds, skulle vi ha bevisat att att lösa vårt begränsade problem är likvärdigt med att lösa det ursprungliga problemet. Mer formellt, låt $\gamma ^{*}$ vara det optimala objektivfunktionsvärdet för en begränsad instans. Sedan kan vi formulera ett sökproblem för den 'mest överträdda begränsningen' i det ursprungliga problemutrymmet, nämligen att hitta $\omega ^{*}\in \Omega$ som

$\omega ^{*}={\underset {\omega \in \Omega }{\textrm {argmax}}}\summa _{n=1}^{\ell }y_{n}h({\ fetstil {x}}_{n};\omega )\lambda _{n}.$

Det vill säga, vi söker i utrymmet ${\mathcal {H}}$ efter en enda beslutsstubb ${\displaystyle h(\cdot ;\omega ^{*})} och$ maximerar den vänstra sidan av den dubbla begränsningen. Om begränsningen inte kan överträdas av något val av beslutsstubb, kan ingen av motsvarande begränsningar vara aktiv i det ursprungliga problemet och det begränsade problemet är likvärdigt.

Straffkonstant $D$

Det positiva värdet av straffkonstanten $D$ måste hittas med hjälp av modellvalstekniker . Men om vi väljer $D={\frac {1}{\ell \nu }}$ , där $\ell$ är antalet träningsprov och ${ \displaystyle 0<\nu <1}$ , då har den nya parametern $\nu$ följande egenskaper.

• $\nu$ är en övre gräns för bråkdelen av träningsfel; det vill säga om $k$ anger antalet felklassificerade träningsprov, då ${\frac {k}{\ell }}\leq \nu$ .
• $\nu$ är en nedre gräns för andelen träningsprov utanför eller på marginalen.

Algoritm

• Inmatning:
  • Träningsuppsättning $X=\{{\boldsymbol {x}}_{1},\dots ,{\boldsymbol {x}}_{\ell }\}$ , ${\boldsymbol {x}}_{i}\in {\mathcal {X}}$
  • Träningsetiketter $Y=\{y_{1},\dots ,y_{\ell }\}$ , $y_ {i}\in \{-1,1\}$
  • Konvergenströskel $\theta \geq 0$
• Utdata:
  • Klassificeringsfunktion $f:{\mathcal {X}}\to \{-1,1\}$

1. Initialisering
   1. Vikter, enhetlig $\lambda _{n}\vänsterpil {\frac {1}{\ell }},\quad n=1,\dots ,\ell$
   2. Kant $\gamma \leftarrow 0$
   3. Hypotesantal $J\leftarrow 1$
2. Iterera
   1. ${\hat {h}}\vänsterpil {\underset {\omega \in \Omega }{\textrm { argmax}}}\sum _{n=1}^{\ell }y_{n}h({\boldsymbol {x}}_{n};\omega )\lambda _{n}$
   2. om $\sum _{n=1}^{\ell }y_{n}{\hat {h}}({\ fetstil {x}}_{n})\lambda _{n}+\gamma \leq \theta$
      1. bryt
      sedan
   3. $h_{J}\leftarrow {\hat {h}}$
   4. $J\leftarrow J+1$
   5. $({\boldsymbol {\lambda }},\gamma )\leftarrow$ lösning av LPBoost-dual
   6. ${\boldsymbol {\alpha }}\leftarrow$ Lagrangemultiplikatorer för lösning av LPBoost-dubbelproblem
3. $f({\boldsymbol {x}}):={\textrm {tecken}}\left(\sum _{ j=1}^{J}\alpha _{j}h_{j}({\boldsymbol {x}})\right)$

Observera att om konvergenströskeln är satt till $\theta =0$ är den erhållna lösningen den globala optimala lösningen för ovanstående linjära program. I praktiken sätts ${\displaystyle \theta } till ett litet positivt värde för att snabbt få en bra lösning.$

Realiserad marginal

Den faktiska marginalen som separerar träningsproverna kallas den realiserade marginalen och definieras som

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

Den realiserade marginalen kan och kommer vanligtvis att vara negativ i de första iterationerna. För ett hypotesutrymme som tillåter att särskilja varje enskilt prov, vilket är vanligt fallet, kommer den realiserade marginalen så småningom att konvergera till något positivt värde.

Konvergensgaranti

Även om ovanstående algoritm har visat sig konvergera, i motsats till andra förstärkande formuleringar, såsom AdaBoost och TotalBoost, finns det inga kända konvergensgränser för LPBoost. I praktiken är det dock känt att LPBoost konvergerar snabbt, ofta snabbare än andra formuleringar.

Basera elever

LPBoost är en ensembleinlärningsmetod och dikterar således inte valet av basinlärare, hypotesutrymmet ${\mathcal {H}}$ . Demiriz et al. visade att under milda antaganden kan vilken basinlärare som helst användas. Om basinlärarna är särskilt enkla kallas de ofta för beslutsstubbar .

Antalet basinlärare som vanligtvis används med Boosting i litteraturen är stort. Till exempel, om ${\mathcal {X}}\subseteq {\mathbb {R} }^{n}$ , kan en basinlärare vara en linjär mjuk marginalstödvektormaskin . Eller ännu enklare, en enkel stump av formen

$h({\boldsymbol {x}};\omega \in \{1,-1\},p\in \{1,\dots ,n\},t\in {\mathbb {R} } ):=\left\{{\begin{array}{cl}\omega &{\textrm {if~}}{\boldsymbol {x}}_{p}\leq t\\-\omega &{\textrm {annat}}\end{array}}\right..$

Ovanstående beslutsstubbar tittar bara längs en enstaka dimension $p$ av inmatningsutrymmet och trösklar helt enkelt respektive kolumn i provet med hjälp av en konstant tröskel $t$ . Sedan kan den bestämma i båda riktningarna, beroende på $\omega$ för en positiv eller negativ klass.

Givet vikter för träningsproverna innebär att konstruera den optimala beslutsstumpen i ovanstående form helt enkelt att söka längs alla provkolumner och bestämma ${\displaystyle p} ,$$\displaystyle t}$$\omega$ och ω för att optimera förstärkningsfunktionen.

• Linjär programmering Boosting via Column Generation , A. Demiriz och KP Bennett och J. Shawe-Taylor. Publicerad 2002 i Kluwer Machine Learning 46, sidorna 225–254.