Stroj na podporu vektoru podpory nejmenších čtverců - Least-squares support-vector machine

Nejmenší čtverce podpůrných vektorových strojů (LS-SVM) jsou verze nejmenších čtverců podpůrných vektorových strojů (SVM), které jsou sadou souvisejících dohlížených metod učení, které analyzují data a rozpoznávají vzory a které se používají pro klasifikaci a regresi analýza . V této verzi najdeme řešení řešením řady lineárních rovnic místo problému konvexního kvadratického programování (QP) pro klasické SVM. Klasifikátory SVM nejmenších čtverců navrhli Suykens a Vandewalle. LS-SVM jsou třídou výukových metod založených na jádře .

Od stroje vektoru podpory po stroj vektoru podpory s nejmenšími čtverci

Vzhledem k tomu, trénovací množinu s vstupních dat a odpovídající etikety binární třídy , v SVM klasifikátor, podle Vapnik ‚s původní formulaci, splňuje následující podmínky: ${\ displaystyle \ {x_ {i}, y_ {i} \} _ {i = 1} ^ {N}}$${\ displaystyle x_ {i} \ in \ mathbb {R} ^ {n}}$${\ displaystyle y_ {i} \ in \ {- 1, + 1 \}}$

${\ displaystyle {\ begin {cases} w ^ {T} \ phi (x_ {i}) + b \ geq 1, & {\ text {if}} \ quad y_ {i} = + 1, \\ w ^ {T} \ phi (x_ {i}) + b \ leq -1, & {\ text {if}} \ quad y_ {i} = - 1, \ end {případů}}}$

což odpovídá

${\ Displaystyle y_ {i} \ vlevo [{w ^ {T} \ phi (x_ {i}) + b} \ vpravo] \ geq 1, \ quad i = 1, \ ldots, N,}$

kde je nelineární mapa z původního prostoru do prostoru vysoké nebo nekonečné dimenze. ${\ displaystyle \ phi (x)}$

Neoddělitelná data

V případě, že taková oddělovací nadrovina neexistuje, zavedeme tzv. Slack proměnné takové, že ${\ displaystyle \ xi _ {i}}$

${\ displaystyle {\ begin {cases} y_ {i} \ left [{w ^ {T} \ phi (x_ {i}) + b} \ right] \ geq 1- \ xi _ {i}, & i = 1 , \ ldots, N, \\\ xi _ {i} \ geq 0, & i = 1, \ ldots, N. \ end {případy}}}$

Podle principu minimalizace strukturálních rizik je riziko omezeno následujícím problémem minimalizace:

${\ displaystyle \ min J_ {1} (w, \ xi) = {\ frac {1} {2}} w ^ {T} w + c \ součet \ limity _ {i = 1} ^ {N} \ xi _ {i},}$

${\ displaystyle {\ text {Subject}} {\ begin {cases} y_ {i} \ left [{w ^ {T} \ phi (x_ {i}) + b} \ right] \ geq 1- \ xi _ {i}, & i = 1, \ ldots, N, \\\ xi _ {i} \ geq 0, & i = 1, \ ldots, N, \ end {případy}}}$

Abychom tento problém vyřešili, mohli bychom postavit Lagrangeovu funkci :

${\ displaystyle L_ {1} (w, b, \ xi, \ alfa, \ beta) = {\ frac {1} {2}} w ^ {T} w + c \ suma \ limity _ {i = 1} ^ {N} {\ xi _ {i}} - \ sum \ limity _ {i = 1} ^ {N} \ alpha _ {i} \ left \ {y_ {i} \ left [{w ^ {T} \ phi (x_ {i}) + b} \ right] -1+ \ xi _ {i} \ right \} - \ sum \ limity _ {i = 1} ^ {N} \ beta _ {i} \ xi _ {i},}$

kde jsou Lagrangeovy multiplikátory . Optimální bod bude v sedlovém bodě Lagrangeovy funkce a pak získáme ${\ displaystyle \ alpha _ {i} \ geq 0, \ \ beta _ {i} \ geq 0 \ (i = 1, \ ldots, N)}$

${\ displaystyle {\ begin {cases} {\ frac {\ částečné L_ {1}} {\ částečné w}} = 0 \ quad \ to \ quad w = \ sum \ limity _ {i = 1} ^ {N} \ alpha _ {i} y_ {i} \ phi (x_ {i}), \\ {\ frac {\ částečný L_ {1}} {\ částečný b}} = 0 \ quad \ to \ quad \ sum \ limity _ {i = 1} ^ {N} \ alpha _ {i} y_ {i} = 0, \\ {\ frac {\ částečné L_ {1}} {\ částečné \ xi _ {i}}} = 0 \ quad \ to \ quad 0 \ leq \ alpha _ {i} \ leq c, \; i = 1, \ ldots, N. \ end {případy}}}$

Nahrazením jeho výrazem v Lagrangeově tvaru vytvořeném z příslušného cíle a omezení získáme následující kvadratický programovací problém: ${\ displaystyle w}$

${\ displaystyle \ max Q_ {1} (\ alfa) = - {\ frac {1} {2}} \ součet \ limity _ {i, j = 1} ^ {N} {\ alfa _ {i} \ alfa _ {j} y_ {i} y_ {j} K (x_ {i}, x_ {j})} + \ sum \ limity _ {i = 1} ^ {N} \ alpha _ {i},}$

kde se nazývá funkce jádra . Při řešení tohoto problému QP podléhajícím omezením v bodě (8) získáme nadrovinu ve vysokodimenzionálním prostoru, a tedy klasifikátor v původním prostoru. ${\ displaystyle K (x_ {i}, x_ {j}) = \ left \ langle \ phi (x_ {i}), \ phi (x_ {j}) \ right \ rangle}$

Formulace SVM nejmenších čtverců

Verze nejmenších čtverců klasifikátoru SVM se získá přeformulováním problému minimalizace na

${\ displaystyle \ min J_ {2} (w, b, e) = {\ frac {\ mu} {2}} w ^ {T} w + {\ frac {\ zeta} {2}} \ součet \ limity _ {i = 1} ^ {N} e_ {i} ^ {2},}$

s výhradou omezení rovnosti

${\ displaystyle y_ {i} \ left [{w ^ {T} \ phi (x_ {i}) + b} \ right] = 1-e_ {i}, \ quad i = 1, \ ldots, N.}$

Výše uvedená formulace klasifikátoru SVM (LS-SVM) s nejmenšími čtverci implicitně odpovídá regresní interpretaci s binárními cíli . ${\ displaystyle y_ {i} = \ pm 1}$

Pomocí máme ${\ displaystyle y_ {i} ^ {2} = 1}$

${\ displaystyle \ sum \ limity _ {i = 1} ^ {N} e_ {i} ^ {2} = \ součet \ limity _ {i = 1} ^ {N} (y_ {i} e_ {i}) ^ {2} = \ sum \ limity _ {i = 1} ^ {N} e_ {i} ^ {2} = \ sum \ limity _ {i = 1} ^ {N} \ vlevo (y_ {i} - (w ^ {T} \ phi (x_ {i}) + b) \ vpravo) ^ {2},}$

s Všimněte si, že tato chyba by také měla smysl pro přizpůsobení dat nejmenších čtverců, takže pro případ regrese platí stejné konečné výsledky. ${\ displaystyle e_ {i} = y_ {i} - (w ^ {T} \ phi (x_ {i}) + b).}$

Proto je formulace klasifikátoru LS-SVM ekvivalentní

${\ displaystyle J_ {2} (w, b, e) = \ mu E_ {W} + \ zeta E_ {D}}$

s a ${\ displaystyle E_ {W} = {\ frac {1} {2}} w ^ {T} w}$${\ displaystyle E_ {D} = {\ frac {1} {2}} \ sum \ limity _ {i = 1} ^ {N} e_ {i} ^ {2} = {\ frac {1} {2} } \ sum \ limits _ {i = 1} ^ {N} \ left (y_ {i} - (w ^ {T} \ phi (x_ {i}) + b) \ right) ^ {2}.}$

Oba a měly by být považovány za hyperparametry pro vyladění množství regularizace versus součet čtvercových chyb. Řešení závisí pouze na poměru , proto původní formulace používá pouze jako parametr ladění. Používáme oba parametry a jako parametry, abychom poskytli Bayesovu interpretaci LS-SVM. ${\ displaystyle \ mu}$${\ displaystyle \ zeta}$${\ displaystyle \ gamma = \ zeta / \ mu}$${\ displaystyle \ gamma}$${\ displaystyle \ mu}$${\ displaystyle \ zeta}$

Řešení regresoru LS-SVM získáme po konstrukci Lagrangeovy funkce :

${\ displaystyle {\ begin {cases} L_ {2} (w, b, e, \ alpha) \; = J_ {2} (w, e) - \ součet \ limity _ {i = 1} ^ {N} \ alpha _ {i} \ left \ {{\ left [{w ^ {T} \ phi (x_ {i}) + b} \ right] + e_ {i} -y_ {i}} \ right \}, \\\ quad \ quad \ quad \ quad \ quad \; = {\ frac {1} {2}} w ^ {T} w + {\ frac {\ gamma} {2}} \ sum \ limity _ {i = 1} ^ {N} e_ {i} ^ {2} - \ sum \ limity _ {i = 1} ^ {N} \ alpha _ {i} \ left \ {\ left [w ^ {T} \ phi ( x_ {i}) + b \ vpravo] + e_ {i} -y_ {i} \ vpravo \}, \ end {případů}}}$

kde jsou Lagrangeovy multiplikátory. Podmínky pro optimálnost jsou ${\ displaystyle \ alpha _ {i} \ v \ mathbb {R}}$

${\ displaystyle {\ begin {cases} {\ frac {\ částečné L_ {2}} {\ částečné w}} = 0 \ quad \ to \ quad w = \ sum \ limity _ {i = 1} ^ {N} \ alpha _ {i} \ phi (x_ {i}), \\ {\ frac {\ částečné L_ {2}} {\ částečné b}} = 0 \ quad \ to \ quad \ sum \ limity _ {i = 1} ^ {N} \ alpha _ {i} = 0, \\ {\ frac {\ částečné L_ {2}} {\ částečné e_ {i}}} = 0 \ quad \ to \ quad \ alpha _ {i } = \ gamma e_ {i}, \; i = 1, \ ldots, N, \\ {\ frac {\ parciální L_ {2}} {\ parciální \ alfa _ {i}}} = 0 \ quad \ to \ quad y_ {i} = w ^ {T} \ phi (x_ {i}) + b + e_ {i}, \, i = 1, \ ldots, N. \ end {cases}}}$

Eliminace a přinese lineární systém namísto kvadratického programovacího problému: ${\ displaystyle w}$${\ displaystyle e}$

${\ displaystyle \ left [{\ begin {matrix} 0 & 1_ {N} ^ {T} \\ 1_ {N} & \ Omega + \ gamma ^ {- 1} I_ {N} \ end {matrix}} \ right] \ left [{\ begin {matrix} b \\\ alpha \ end {matrix}} \ right] = \ left [{\ begin {matrix} 0 \\ Y \ end {matrix}} \ right],}$

s , a . Odtud je jednotková matice a je matrix jádra definováno . ${\ displaystyle Y = [y_ {1}, \ ldots, y_ {N}] ^ {T}}$${\ displaystyle 1_ {N} = [1, \ ldots, 1] ^ {T}}$${\ displaystyle \ alpha = [\ alpha _ {1}, \ ldots, \ alpha _ {N}] ^ {T}}$${\ displaystyle I_ {N}}$${\ displaystyle N \ krát N}$ ${\ displaystyle \ Omega \ in \ mathbb {R} ^ {N \ krát N}}$${\ displaystyle \ Omega _ {ij} = \ phi (x_ {i}) ^ {T} \ phi (x_ {j}) = K (x_ {i}, x_ {j})}$

Funkce jádra K

U funkce jádra K (•, •) má člověk obvykle následující možnosti:

• Lineární jádro: ${\ displaystyle K (x, x_ {i}) = x_ {i} ^ {T} x,}$
• Polynomiální jádro stupně : ${\ displaystyle d}$${\ displaystyle K (x, x_ {i}) = \ left ({1 + x_ {i} ^ {T} x / c} \ right) ^ {d},}$
• Radiální základní funkce RBF jádro: ${\ displaystyle K (x, x_ {i}) = \ exp \ left ({- \ left \ | {x-x_ {i}} \ right \ | ^ {2} / \ sigma ^ {2}} \ right ),}$
• MLP jádro: ${\ displaystyle K (x, x_ {i}) = \ tanh \ vlevo ({k \, x_ {i} ^ {T} x + \ theta} \ vpravo),}$

kde , , , a jsou konstanty. Všimněte si, že podmínka Mercer platí pro všechny a hodnoty v případě polynomu a RBF, ale ne pro všechny možné volby a v případě MLP. Parametry stupnice , a určují škálování vstupů do polynomu, RBF a MLP funkce jádra . Toto měřítko souvisí se šířkou pásma jádra ve statistikách , kde se ukazuje, že šířka pásma je důležitým parametrem chování generalizace metody jádra. ${\ displaystyle d}$${\ displaystyle c}$${\ displaystyle \ sigma}$${\ displaystyle k}$${\ displaystyle \ theta}$${\ displaystyle c, \ sigma \ in \ mathbb {R} ^ {+}}$${\ displaystyle d \ v N}$${\ displaystyle k}$${\ displaystyle \ theta}$${\ displaystyle c}$${\ displaystyle \ sigma}$${\ displaystyle k}$

Bayesovská interpretace pro LS-SVM

Bayesian výklad SVM bylo navrženo Smola et al. Ukázali, že použití různých jader v SVM lze považovat za definování různých předchozích distribucí pravděpodobnosti ve funkčním prostoru, jako . Zde je konstanta a je to regularizační operátor odpovídající vybranému jádru. ${\ displaystyle P [f] \ propto \ exp \ left ({- \ beta \ left \ | {{\ hat {P}} f} \ right \ | ^ {2}} \ right)}$${\ displaystyle \ beta> 0}$${\ displaystyle {\ hat {P}}}$

Obecný Bayesiánský důkazní rámec byl vyvinut společností MacKay a MacKay ji použil k řešení problému regrese, dopředné neuronové sítě a klasifikační sítě. Za předpokladu datové sady , modelu s vektorem parametrů a takzvaného hyperparametru nebo regularizačního parametru je Bayesianova inference konstruována se 3 úrovněmi inference: ${\ displaystyle D}$${\ displaystyle \ mathbb {M}}$${\ displaystyle w}$${\ displaystyle \ lambda}$

• Na úrovni 1, pro danou hodnotu , odvozuje první úroveň inference zadní rozdělení podle Bayesovské vlády ${\ displaystyle \ lambda}$${\ displaystyle w}$

${\ displaystyle p (w | D, \ lambda, \ mathbb {M}) \ propto p (D | w, \ mathbb {M}) p (w | \ lambda, \ mathbb {M}).}$

• Druhá úroveň závěru určuje hodnotu maximalizací ${\ displaystyle \ lambda}$

${\ displaystyle p (\ lambda | D, \ mathbb {M}) \ propto p (D | \ lambda, \ mathbb {M}) p (\ lambda | \ mathbb {M}).}$

• Třetí úroveň závěru v rámci důkazů řadí různé modely zkoumáním jejich zadních pravděpodobností

${\ displaystyle p (\ mathbb {M} | D) \ propto p (D | \ mathbb {M}) p (\ mathbb {M}).}$

Vidíme, že Bayesiánský důkazní rámec je jednotná teorie pro učení modelu a výběru modelu. Kwok použil Bayesianský důkazní rámec k interpretaci formulace SVM a výběru modelu. A také použil Bayesianský důkazní rámec na podporu vektorové regrese.

Nyní, vzhledem k datovým bodům a hyperparametrům a modelu , jsou parametry modelu a jsou odhadovány maximalizací zadní . Použitím Bayesova pravidla získáme ${\ displaystyle \ {x_ {i}, y_ {i} \} _ {i = 1} ^ {N}}$${\ displaystyle \ mu}$${\ displaystyle \ zeta}$${\ displaystyle \ mathbb {M}}$${\ displaystyle w}$${\ displaystyle b}$${\ displaystyle p (w, b | D, \ log \ mu, \ log \ zeta, \ mathbb {M})}$

${\ Displaystyle p (w, b | D, \ log \ mu, \ log \ zeta, \ mathbb {M}) = {\ frac {p (D | w, b, \ log \ mu, \ log \ zeta, \ mathbb {M}) p (w, b | \ log \ mu, \ log \ zeta, \ mathbb {M})} {p (D | \ log \ mu, \ log \ zeta, \ mathbb {M}) }},}$

kde je normalizační konstanta takového integrálu přes všechno možné a rovná se 1. Předpokládáme a jsme nezávislí na hyperparametru a jsou podmíněné nezávislé, tj. předpokládáme ${\ displaystyle p (D | \ log \ mu, \ log \ zeta, \ mathbb {M})}$${\ displaystyle w}$${\ displaystyle b}$${\ displaystyle w}$${\ displaystyle b}$${\ displaystyle \ zeta}$

${\ Displaystyle p (w, b | \ log \ mu, \ log \ zeta, \ mathbb {M}) = p (w | \ log \ mu, \ mathbb {M}) p (b | \ log \ sigma _ {b}, \ mathbb {M}).}$

Kdy bude distribuce přibližně stejná distribuce. Dále předpokládáme a jsme Gaussovo rozdělení, takže získáme apriorní rozdělení a s být ${\ displaystyle \ sigma _ {b} \ do \ infty}$${\ displaystyle b}$${\ displaystyle w}$${\ displaystyle b}$${\ displaystyle w}$${\ displaystyle b}$${\ displaystyle \ sigma _ {b} \ do \ infty}$

${\ displaystyle {\ begin {pole} {l} p (w, b | \ log \ mu,) = \ left ({\ frac {\ mu} {2 \ pi}} \ right) ^ {\ frac {n_ {f}} {2}} \ exp \ left ({- {\ frac {\ mu} {2}} w ^ {T} w} \ right) {\ frac {1} {\ sqrt {2 \ pi \ sigma _ {b}}}} \ exp \ left ({- {\ frac {b ^ {2}} {2 \ sigma _ {b}}}} \ right) \\\ quad \ quad \ quad \ quad \ quad \ quad \ quad \ propto \ left ({\ frac {\ mu} {2 \ pi}} \ right) ^ {\ frac {n_ {f}} {2}} \ exp \ left ({- {\ frac {\ mu} {2}} w ^ {T} w} \ right) \ end {array}}.}$

Tady je rozměrnost prostoru funkcí, stejně jako rozměrnost prostoru . ${\ displaystyle n_ {f}}$${\ displaystyle w}$

Předpokládá se, že pravděpodobnost závisí pouze na a . Předpokládáme, že datové body jsou nezávisle identicky distribuovány (iid), takže: ${\ displaystyle p (D | w, b, \ log \ mu, \ log \ zeta, \ mathbb {M})}$${\ displaystyle w, b, \ zeta}$${\ displaystyle \ mathbb {M}}$

${\ displaystyle p (D | w, b, \ log \ zeta, \ mathbb {M}) = \ prod \ limity _ {i = 1} ^ {N} {p (x_ {i}, y_ {i} | w, b, \ log \ zeta, \ mathbb {M})}.}$

Za účelem získání funkce nejmenších čtvercových nákladů se předpokládá, že pravděpodobnost datového bodu je úměrná:

${\ Displaystyle p (x_ {i}, y_ {i} | w, b, \ log \ zeta, \ mathbb {M}) \ propto p (e_ {i} | w, b, \ log \ zeta, \ mathbb {M}).}$

Gaussova distribuce je považována za chyby jako: ${\ displaystyle e_ {i} = y_ {i} - (w ^ {T} \ phi (x_ {i}) + b)}$

${\ displaystyle p (e_ {i} | w, b, \ log \ zeta, \ mathbb {M}) = {\ sqrt {\ frac {\ zeta} {2 \ pi}}} \ exp \ left ({- {\ frac {\ zeta e_ {i} ^ {2}} {2}}} \ vpravo).}$

Předpokládá se, že a a jsou určeny takovým způsobem, že se třída vycentruje a mapuje na cíl -1, respektive +1. Projekce prvků třídy sledují mnohorozměrné Gaussovo rozdělení, které mají rozptyl . ${\ displaystyle w}$${\ displaystyle b}$${\ displaystyle {\ hat {m}} _ {-}}$${\ displaystyle {\ hat {m}} _ {+}}$${\ displaystyle w ^ {T} \ phi (x) + b}$${\ displaystyle \ phi (x)}$${\ displaystyle 1 / \ zeta}$

Zkombinováním předchozích výrazů a zanedbáním všech konstant se stane Bayesovo pravidlo

${\ displaystyle p (w, b | D, \ log \ mu, \ log \ zeta, \ mathbb {M}) \ propto \ exp (- {\ frac {\ mu} {2}} w ^ {T} w - {\ frac {\ zeta} {2}} \ sum \ limits _ {i = 1} ^ {N} {e_ {i} ^ {2}}) = \ exp (-J_ {2} (w, b )).}$

Maximální hustota zadní odhady a se získají tím, že minimalizuje negativní logaritmus (26), takže dostaneme (10). ${\ displaystyle w_ {MP}}$${\ displaystyle b_ {MP}}$

Reference

Bibliografie

• JAK Suykens, T. Van Gestel, J. De Brabanter, B. De Moor, J. Vandewalle, Least Squares Support Vector Machines, World Scientific Pub. Co., Singapore, 2002. ISBN   981-238-151-1
• Suykens J. A. K., Vandewalle J., Nejmenší čtverce podporují klasifikátory vektorových strojů, Neural Processing Letters , sv. 9, č. 3, červen 1999, str. 293–300.
• Vladimir Vapnik. Podstata teorie statistického učení . Springer-Verlag, 1995. ISBN   0-387-98780-0
• MacKay, DJC, Pravděpodobné sítě a věrohodné předpovědi - přehled praktických Bayesiánských metod pro neuronové sítě pod dohledem. Network: Computation in Neural Systems , sv. 6, 1995, s. 469–505.

externí odkazy

• www.esat.kuleuven.be/sista/lssvmlab/ „ Sada nejmenších čtverců podporuje sadu vektorových strojů Lab (LS-SVMlab) obsahuje implementace Matlab / C pro řadu algoritmů LS-SVM“.
• www.kernel-machines.org „Podpora vektorových strojů a metod založených na jádře (Smola & Schölkopf)“.
• www.gaussianprocess.org „Gaussovské procesy: Modelování dat pomocí Gaussova procesu upřednostňuje funkce pro regresi a klasifikaci (MacKay, Williams)“.
• www.support-vector.net „Podpora vektorových strojů a metod založených na jádře (Cristianini)“.
• dlib : Obsahuje implementaci SVM nejmenších čtverců pro rozsáhlé datové sady.