Metoda potpornih vektora

 

U mašinskom učenju, metoda potpornih vektora je model učenja pod nadzorom sa pripadajućim algoritmima učenja koji analiziraju podatke za klasifikaciju i regresionu analizu . Razvio ju je Vladimir Vapnik sa kolegama u AT&T Bell Laboratorijama. Metoda potpornih vektora je jedna od najpouzdanijih metoda predviđanja, zasnovana na statističkim okvirima učenja ili VC teoriji koju su predložili Vapnik (1982, 1995) i Červoninks (1974). Imajući u vidu skup primera za obuku, od kojih je svaki označen kao da pripada jednoj od dve kategorije, MPV algoritam za obuku gradi model koji dodeljuje nove primere jednoj ili drugoj kategoriji, čineći ga nenagađajućim binarnim linearnim klasifikatorom . MPV preslikava primere obuke na tačke u prostoru kako bi maksimizirao širinu jaza između dve kategorije. Novi primeri se zatim mapiraju u isti prostor i predviđaju da pripadaju kategoriji na osnovu koje strane jaza padaju.

Pored izvođenja linearne klasifikacije, MPV-ovi mogu efikasno da izvrše nelinearnu klasifikaciju koristeći ono što se naziva trik jezgra, implicitno mapirajući svoje ulaze u prostore karakteristika visoke dimenzije.

Kada podaci nisu označeni, nadgledano učenje nije moguće i potreban je pristup učenju bez nadzora, koji pokušava da pronađe prirodno grupisanje podataka u grupe, a zatim mapira nove podatke u ove formirane grupe. Algoritam za grupisanje potpornih vektora , koji su kreirali Hava Sigelman i Vladimir Vapnik, primenjuje statistiku vektora podrške, razvijenu u algoritmu motode podžanih vektora, za kategorizaciju neoznačenih podataka, i jedan je od najčešće korišćenih algoritama za grupisanje u inustrijskoj aplikaciji.

Motivacija

H₁ ne razdvaja klase. H₂ razdvaja, ali samo sa malom marginom. H₃ ih razdvaja sa maksimalnom marginom.

Klasifikacija podataka je uobičajen zadatak u mašinskom učenju . Pretpostavimo da svaka data tačka pripada jednoj od dve klase, a cilj je da se odluči u kojoj će klasi biti nova tačka podataka . U slučaju metode potpornih vektora, tačka podataka se posmatra kao $p$ -dimenzionalni vektor (lista $p$ brojeva), i želimo da znamo da li možemo da odvojimo takve tačke sa a $(p-1)$ -dimenzionalnom hiperravni . Ovo se zove linearni klasifikator . Postoji mnogo hiperravni koje mogu klasifikovati podatke. Razuman izbor kao najbolja hiperravna je ona koji postiže najveće razdvajanje, ili marginu, između dve klase. Zato biramo hiperravan tako da je rastojanje od nje do najbliže tačke podataka na svakoj strani maksimizirano. Ako takva hiperravan postoji, poznata je kao hiperravan maksimalne margine, a linearni klasifikator koji on definiše je poznat kao klasifikator maksimalne margine; ili ekvivalentno, perceptron optimalne stabilnosti .

Definicija

Model potpornih vekotra konstruiše hiperravan ili skup hiperravni u visoko- ili beskonačno-dimenzionalnom prostoru, koji se može koristiti za klasifikaciju, regresiju ili druge zadatke kao što je otkrivanje odstupanja. Dobro razdvajanje se postiže hiperravninom koja ima najveću udaljenost do najbliže tačke podataka za obuku bilo koje klase (funkcionalna margina), pošto generalno što je veća margina, to je manja greška generalizacije klasifikatora.

Kernel mašina

Dok se originalni problem može navesti u konačnodimenzionalnom prostoru, često se dešava da skupovi diskriminanti nisu linearno odvojivi u tom prostoru. Iz tog razloga, predloženo je da se originalni konačno-dimenzionalni prostor preslika u prostor mnogo veće dimenzije, što verovatno olakšava razdvajanje u tom prostoru. Da bi računarsko opterećenje bilo razumno, mapiranja koje koriste MPV šeme su dizajnirane da obezbede da se tačkasti proizvodi parova vektora ulaznih podataka mogu lako izračunati u smislu promenljivih u originalnom prostoru, definisanjem u smislu funkcije jezgra $k(x,y)$ odabrano da odgovara problemu. Hiperravne u višedimenzionalnom prostoru su definisane kao skup tačaka čiji je tačkasti proizvod sa vektorom u tom prostoru konstantan, pri čemu je takav skup vektora ortogonalan (a time i minimalan skup vektora koji definiše hiperravan. Vektori koji definišu hiperravne mogu se izabrati da budu linearne kombinacije sa parametrima $\alpha _{i}$ slike vektora obeležja $x_{i}$ koji se javljaju u bazi podataka. Sa ovim izborom hiperravnine, tačke $x$ u prostoru obeležja koji su preslikani u hiperravninu definisani su relacijom $\textstyle \sum _{i}\alpha _{i}k(x_{i},x)={\text{constant}}.$ Imajte na umu da ako $k(x,y)$ postaje mali kao $y$ raste dalje od $x$, svaki član u zbiru meri stepen bliskosti ispitane tačke $x$ do odgovarajuće tačke baze podataka $x_{i}$ . Na ovaj način, zbir gornjih jezgara može da se koristi za merenje relativne blizine svake ispitne tačke tačkama podataka koje potiču iz jednog ili drugog skupa koji se diskriminiše. Obratite pažnju na činjenicu da je skup tačaka $x$ preslikan u bilo koju hiperravninu može biti prilično zamršen kao rezultat, omogućavajući mnogo složeniju diskriminaciju između skupova koji uopšte nisu konveksni u originalnom prostoru.

Aplikacije

Metode potpornih vekotra se mogu koristiti za rešavanje različitih problema iz stvarnog sveta:

• Metode potpornih vekotra su korisne u kategorizaciji teksta i hiperteksta, jer njihova primena može značajno smanjiti potrebu za označenim instancama obuke i u standardnim induktivnim i transduktivnim postavkama. Neke metode za plitko semantičko raščlanjivanje zasnovane su na metodama potpornih vekotra.
• Klasifikacija slika se takođe može izvršiti pomoću MPV-a. Eksperimentalni rezultati pokazuju da MPV postižu znatno veću tačnost pretrage od tradicionalnih šema za preciziranje upita nakon samo tri do četiri kruga povratnih informacija o relevantnosti. Ovo važi i za sisteme za segmentaciju slika, uključujući i one koji koriste modifikovanu verziju MPV-a koja koristi privilegovani pristup kako je predložio Vapnik.
• Klasifikacija satelitskih podataka kao što su SAR podaci korišćenjem nadgledanog MPV.
• Rukom pisani znakovi se mogu prepoznati pomoću MPV.
• Algoritam MPV ima široku primenu u biologijo i drugim naukama. Korišćeni su za klasifikaciju proteina sa do 90% ispravno klasifikovanih jedinjenja. Permutacioni testovi zasnovani na MPV težinama su predloženi kao mehanizam za interpretaciju MPV modela. Metode potpornih vekotra su takođe korišćene za tumačenje MPV modela u prošlosti. Posthok interpretacija modela potpornih vektora u cilju identifikacije karakteristika koje model koristi za predviđanje je relativno nova oblast istraživanja od posebnog značaja u biološkim naukama.

Istorija

Originalni MPV algoritam su izmislili Vladimir N. Vapnik i Aleksej Ja. Červoninks 1963. godine. Godine 1992. Bernhard Boser, Izabela Gujon i Vladimir Vapnik su predložili način da se stvore nelinearni klasifikatori primenom trika jezgra da bi se dobile maksimalne margine hiperravni. Inkarnaciju „meke margine“, kao što se uobičajeno koriste softverski paketi, predložili su Korina Kortes i Vapnik 1993. godine i objavljeni 1995. godine

Linearna MPV

Hiperravan maksimalne margine i margine za MPV obučen sa uzorcima iz dve klase. Uzorci na margini nazivaju se vektori podrške.

Imamo skup podataka za obuku od $n$ tačke forme

$(\mathbf {x} _{1},y_{1}),\ldots ,(\mathbf {x} _{n},y_{n}),$

gde $y_{i}$ su ili 1 ili −1, od kojih svaki ukazuje na klasu do koje je tačka $\mathbf {x} _{i}$ pripada. Svaki $\mathbf {x} _{i}$ je $p$-dimenzionalni realni vektor. Želimo da pronađemo "hiperravan maksimalne margine" koja deli grupu tačaka $\mathbf {x} _{i}$ za koje $y_{i}=1$ iz grupe bodova za koje $y_{i}=-1$, koji je definisan tako da rastojanje između hiperravni i najbliže tačke $\mathbf {x} _{i}$ iz bilo koje grupe bude maksimiziran.

Bilo koja hiperravan se može napisati kao skup tačaka $\mathbf {x}$ ukoliko ispunjava:

$\mathbf {w} ^{T}\mathbf {x} -b=0,$

gde je $\mathbf {w}$ (ne nužno normalizovan) vektor normale na hiperravan. Ovo je slično Hesenovom normalnom obliku, osim toga $\mathbf {w}$ nije nužno jedinični vektor. Parametar ${\tfrac {b}{\|\mathbf {w} \|}}$ određuje pomak hiperravni od početka duž vektora normale $\mathbf {w}$ .

Tvrda margina

Ako su trening podaci linearno razdvojivi, možemo izabrati dve paralelne hiperravne koje razdvajaju dve klase podataka, tako da je rastojanje između njih što je moguće veće. Područje ograničeno sa ove dve hiperravne naziva se „margina“, a hiperravan maksimalne margine je hiperravan koja se nalazi na pola puta između njih. Sa normalizovanim ili standardizovanim skupom podataka, ove hiperravne se mogu opisati sldećim jednačinama:

$\mathbf {w} ^{T}\mathbf {x} -b=1$ (sve na ili iznad ove granice priprada jednoj klasi, sa oznakom 1)

i

$\mathbf {w} ^{T}\mathbf {x} -b=-1$ (sve na ili ispod ove granice pripada drugoj klasi, sa oznakom −1).

Geometrijski, rastojanje između ove dve hiperravne je ${\tfrac {2}{\|\mathbf {w} \|}}$, tako da bi maksimizovali rastojanje između ravni koje želimo da minimiziramo $\|\mathbf {w} \|$ . Rastojanje se izračunava korišćenjem jednačine udaljenosti tačke od ravni . Takođe moramo da sprečimo da tačke podataka padnu na marginu, dodajemo sledeće ograničenje: za svaku $i$ bilo

$\mathbf {w} ^{T}\mathbf {x} _{i}-b\geq 1$, ako je $y_{i}=1$,

ili

$\mathbf {w} ^{T}\mathbf {x} _{i}-b\leq -1$, ako je $y_{i}=-1$ .

Ovi uslovi navode da svaka tačka podataka mora ležati na ispravnoj strani margine.

Ovo se može napisati i kao:

$y_{i}(\mathbf {w} ^{T}\mathbf {x} _{i}-b)\geq 1,\quad {\text{ за све }}1\leq i\leq n.\qquad \qquad (1)$

Možemo da sastavimo sve ovo i dobijemo problem optimizacije:

„Minimizuj $\|\mathbf {w} \|$ na $y_{i}(\mathbf {w} ^{T}\mathbf {x} _{i}-b)\geq 1$ za $i=1,\ldots ,n$ ."

$\mathbf {w}$ i $b$ koji rešavaju ovaj problem određuju naš klasifikator, $\mathbf {x} \mapsto \operatorname {sgn}(\mathbf {w} ^{T}\mathbf {x} -b)$ gde je $\operatorname {sgn}(\cdot )$ funkcija znaka .

Važna posledica ovog geometrijskog opisa je da je hiperravan maksimalne margine potpuno određena vekotrom ${\vec {x}}_{i}$ koji mu je najbliži. Ovi $\mathbf {x} _{i}$ nazivaju se vektori podrške .

Meka margina

Za proširenje MPV na slučajeve u kojima podaci nisu linearno odvojivi, funkcija gubitka zgloba je od pomoći

$\max \left(0,1-y_{i}(\mathbf {w} ^{T}\mathbf {x} _{i}-b)\right).$

Napomenuti da je $y_{i}$ i-ti cilj (to jest, u ovom slučaju je 1 ili −1), i $\mathbf {w} ^{T}\mathbf {x} _{i}-b$ je i-ti izlaz.

Ova funkcija je nula ako je uslov iz (1) zadovoljen, drugim rečima, ako $\mathbf {x} _{i}$ leži na ispravnoj strani margine. Za podatke na pogrešnoj strani margine, vrednost funkcije je proporcionalna udaljenosti od tačke od margine.

Cilj optimizacije je da se minimizuje

$\lambda \lVert \mathbf {w} \rVert ^{2}+\left[{\frac {1}{n}}\sum _{i=1}^{n}\max \left(0,1-y_{i}(\mathbf {w} ^{T}\mathbf {x} _{i}-b)\right)\right],$

gde je parametar $\lambda >0$ određuje kompromis između povećanja veličine margine i obezbeđivanja da $\mathbf {x} _{i}$ leže na ispravnoj strani margine. Dakle, za dovoljno male vrednosti od $\lambda$, ponašaće se slično MPV-a sa tvrdom marginom, ako se ulazni podaci linearno klasifikuju, ali će i dalje naučiti da li je pravilo klasifikacije održivo ili ne. (Ovaj parametar $\lambda$ se takođe naziva C, npr. u <a href="https://en.wikipedia.org/wiki/LIBSVM" rel="mw:ExtLink" title="LIBSVM" class="cx-link" data-linkid="534">LIBSVM</a> . )

Nelinearna klasifikacija

Kernel mašina

Originalni algoritam maksimalne margine hiperavni koji je predložio Vapnik 1963. godine konstruisao je linearni klasifikator . Međutim, 1992. godine, Bernhard Boser, Izabel Gujon i Vladimir Vapnik su predložili način za kreiranje nelinearnih klasifikatora primenom trika jezgra (prvobitno predložen od Aizermana ) za maksimalne margine hiperravni. Dobijeni algoritam je formalno sličan, osim što je svaki tačkasti proizvod zamenjen nelinearnom funkcijom jezgra. Ovo omogućava algoritmu da uklopi hiperravan maksimalne margine u transformisani prostor obeležja. Transformacija može biti nelinearna, a transformisani prostor višedimenzionalan; iako je klasifikator hiperravna u transformisanom prostoru obeležja, on može biti nelinearan u originalnom ulaznom prostoru.

Važno je napomenuti da rad u višedimenzionalnom prostoru karakteristika povećava grešku generalizacije metode potpornih vektora, ukoliko ima dovoljno trening uzoraka algoritam će i dalje radi dobro.

Neka uobičajena jezgra uključuju:

• Polinom (homogen) : $k({\vec {x_{i}}},{\vec {x_{j}}})=({\vec {x_{i}}}\cdot {\vec {x_{j}}})^{d}$ .
• Polinom (nehomogen): $k({\vec {x_{i}}},{\vec {x_{j}}})=({\vec {x_{i}}}\cdot {\vec {x_{j}}}+1)^{d}$ .
• Gausova radijalna bazna funkcija : $k({\vec {x_{i}}},{\vec {x_{j}}})=\exp(-\gamma \|{\vec {x_{i}}}-{\vec {x_{j}}}\|^{2})$ za $\gamma >0$ . Ponekad se parametrizuju korišćenjem $\gamma =1/(2\sigma ^{2})$ .
• Hiperbolički tangent : $k({\vec {x_{i}}},{\vec {x_{j}}})=\tanh(\kappa {\vec {x_{i}}}\cdot {\vec {x_{j}}}+c)$ za neke (ne za sve) $\kappa >0$ i $c<0$ .

Jezgro je povezano sa transformacijom $\varphi ({\vec {x_{i}}})$ po jednačini $k({\vec {x_{i}}},{\vec {x_{j}}})=\varphi ({\vec {x_{i}}})\cdot \varphi ({\vec {x_{j}}})$ . Vrednost W je takođe u transformisanom prostoru, sa $\textstyle {\vec {w}}=\sum _{i}\alpha _{i}y_{i}\varphi ({\vec {x}}_{i})$ . Tačkasti proizvodi sa w za klasifikaciju se ponovo mogu izračunati pomoću trika jezgra, tj $\textstyle {\vec {w}}\cdot \varphi ({\vec {x}})=\sum _{i}\alpha _{i}y_{i}k({\vec {x}}_{i},{\vec {x}})$ .

Izračunavanje klasifikatora MPV

Izračunavanje (meke margine) klasifikatora MPV dovodi do minimiziranja izraza forme

$\left[{\frac {1}{n}}\sum _{i=1}^{n}\max \left(0,1-y_{i}(\mathbf {w} ^{T}\mathbf {x} _{i}-b)\right)\right]+\lambda \|\mathbf {w} \|^{2}.\qquad (2)$

Fokusiramo se na klasifikator meke margine pošto, kao što je gore navedeno, odabir dovoljno male vrednosti za $\lambda$ daje klasifikator tvrde margine za linearno klasifikujuće ulazne podatke. Klasični pristup, koji uključuje svođenje (2) na problem kvadratnog programiranja, detaljno je opisan u nastavku. Zatim će se raspravljati o novijim pristupima kao što su sub-gradijentalni spust i koordinatni spust.

Primal

Minimizovanje izraza (2) se može napisati kao problem ograničene optimizacije sa diferencijabilnom ciljnom funkcijom ovako:

Za svaki $i\in \{1,\,\ldots ,\,n\}$ uvodimo promenljivu $\zeta _{i}=\max \left(0,1-y_{i}(\mathbf {w} ^{T}\mathbf {x} _{i}-b)\right)$ . Napomenuti da je $\zeta _{i}$ najmanji nenegativni broj koji zadovoljava(ispunjava) $y_{i}(\mathbf {w} ^{T}\mathbf {x} _{i}-b)\geq 1-\zeta _{i}.$

Stoga možemo prepisati problem optimizacije na sledeći način

${\text{минимизуј}}{\frac {1}{n}}\sum _{i=1}^{n}\zeta _{i}+\lambda \|\mathbf {w} \|^{2}$

${\text{за }}y_{i}(\mathbf {w} ^{T}\mathbf {x} _{i}-b)\geq 1-\zeta _{i}\,{\text{ and }}\,\zeta _{i}\geq 0,\,{\text{за свако }}i.$

Ovo se zove primarni problem.

Dual

Rešavanjem Lagranžovog duala gornjeg problema dobija se uprošćeni problem

${\text{максимизуј}}\,\,f(c_{1}\ldots c_{n})=\sum _{i=1}^{n}c_{i}-{\frac {1}{2}}\sum _{i=1}^{n}\sum _{j=1}^{n}y_{i}c_{i}(\mathbf {x} _{i}^{T}\mathbf {x} _{j})y_{j}c_{j},$

${\text{за }}\sum _{i=1}^{n}c_{i}y_{i}=0,\,{\text{and }}0\leq c_{i}\leq {\frac {1}{2n\lambda }}\;{\text{за свако }}i.$

Ovo se zove dualni problem. Pošto je problem dvostruke maksimizacije kvadratna funkcija od $c_{i}$ a podleže linearnim ograničenjima, efikasno se rešava pomoću algoritama kvadratnog programiranja.

Ovde, promenljive $c_{i}$ definisane su tako da

$\mathbf {w} =\sum _{i=1}^{n}c_{i}y_{i}\mathbf {x} _{i}$ .

Štaviše, $c_{i}=0$ tačno kada $\mathbf {x} _{i}$ leži na ispravnoj strani margine, i $0<c_{i}<(2n\lambda )^{-1}$ kada $\mathbf {x} _{i}$ leži na granici margine. Sledi da se $\mathbf {w}$ može napisati kao linearna kombinacija potpornih vekotra.

Ofset, $b$, može se povratiti pronalaženjem $\mathbf {x} _{i}$ na granici margine i rešavanjem:

$y_{i}(\mathbf {w} ^{T}\mathbf {x} _{i}-b)=1\iff b=\mathbf {w} ^{T}\mathbf {x} _{i}-y_{i}.$

(Napomenuti da je $y_{i}^{-1}=y_{i}$ jer je $y_{i}=\pm 1$ . )

Trik jezgra

Trening primer MPV sa jezgrom datim sa φ(( a, b )) = ( a, b, a ² + b ² )

Pretpostavimo sada da bismo želeli da naučimo pravilo nelinearne klasifikacije koje odgovara pravilu linearne klasifikacije za transformisane tačke podataka $\varphi (\mathbf {x} _{i}).$ Štaviše, data nam je funkcija jezgra $k$ koja zadovoljava $k(\mathbf {x} _{i},\mathbf {x} _{j})=\varphi (\mathbf {x} _{i})\cdot \varphi (\mathbf {x} _{j})$ .

Poznato nam je da vektor klasifikacije $\mathbf {w}$ u transformisanom prostoru zadovoljava

$\mathbf {w} =\sum _{i=1}^{n}c_{i}y_{i}\varphi (\mathbf {x} _{i}),$

gde se $c_{i}$ dobija se rešavanjem zadatka optimizacije

${\begin{aligned}{\text{maximize}}\,\,f(c_{1}\ldots c_{n})&=\sum _{i=1}^{n}c_{i}-{\frac {1}{2}}\sum _{i=1}^{n}\sum _{j=1}^{n}y_{i}c_{i}(\varphi (\mathbf {x} _{i})\cdot \varphi (\mathbf {x} _{j}))y_{j}c_{j}\\&=\sum _{i=1}^{n}c_{i}-{\frac {1}{2}}\sum _{i=1}^{n}\sum _{j=1}^{n}y_{i}c_{i}k(\mathbf {x} _{i},\mathbf {x} _{j})y_{j}c_{j}\\\end{aligned}}$

${\text{за }}\sum _{i=1}^{n}c_{i}y_{i}=0,\,{\text{and }}0\leq c_{i}\leq {\frac {1}{2n\lambda }}\;{\text{за свако }}i.$

Koeficijenti $c_{i}$ se mogu rešiti korišćenjem kvadratnog programiranja, kao i ranije. Opet, možemo pronaći neki indeks $i$ tako da $0<c_{i}<(2n\lambda )^{-1}$, tako da $\varphi (\mathbf {x} _{i})$ leži na granici margine u transformisanom prostoru, a zatim možemo rešiti

${\begin{aligned}b=\mathbf {w} ^{T}\varphi (\mathbf {x} _{i})-y_{i}&=\left[\sum _{j=1}^{n}c_{j}y_{j}\varphi (\mathbf {x} _{j})\cdot \varphi (\mathbf {x} _{i})\right]-y_{i}\\&=\left[\sum _{j=1}^{n}c_{j}y_{j}k(\mathbf {x} _{j},\mathbf {x} _{i})\right]-y_{i}.\end{aligned}}$

konačno,

$\mathbf {z} \mapsto \operatorname {sgn}(\mathbf {w} ^{T}\varphi (\mathbf {z} )-b)=\operatorname {sgn} \left(\left[\sum _{i=1}^{n}c_{i}y_{i}k(\mathbf {x} _{i},\mathbf {z} )\right]-b\right).$

Savremene metode

Najnoviji algoritmi za pronalaženje klasifikatora MPV uključuju sub-gradijentni spus i koordinatni spust. Obe tehnike pokazale su se da nude značajne prednosti u odnosu na tradicionalni pristup kada se radi sa velikim, retkim skupovima podataka — metode sub-gradijenta su posebno efikasne kada postoji mnogo primera za obuku i koordinisani spust kada je dimenzija prostora obeležja velika.

Sub-gradijenti spust

Sub-gradijentni spust algoritam za MPV radi direktno sa izrazom

$f(\mathbf {w} ,b)=\left[{\frac {1}{n}}\sum _{i=1}^{n}\max \left(0,1-y_{i}(\mathbf {w} ^{T}\mathbf {x} _{i}-b)\right)\right]+\lambda \|\mathbf {w} \|^{2}.$

Napomenuti da $f$ je konveksna funkcija od $\mathbf {w}$ i $b$ . Kao takav, tradicionalni gradijenti spust (ili SGS) se može prilagoditi, gde umesto uzimanja koraka u pravcu funkcije gradijenta, korak se uzima u pravcu vektora izabranog iz funkcije sub-gradijenta . Ovaj pristup ima prednost u tome što se, za određene implementacije, broj iteracija ne povećava sa $n$, broj tačaka podataka.

Koordinatni spust

Algoritmi koordinatnog spusta za MPV rade iz dualnog problema

${\text{максимизуј}}\,\,f(c_{1}\ldots c_{n})=\sum _{i=1}^{n}c_{i}-{\frac {1}{2}}\sum _{i=1}^{n}\sum _{j=1}^{n}y_{i}c_{i}(x_{i}\cdot x_{j})y_{j}c_{j},$

${\text{за }}\sum _{i=1}^{n}c_{i}y_{i}=0,\,{\text{and }}0\leq c_{i}\leq {\frac {1}{2n\lambda }}\;{\text{за свако }}i.$

Za svako $i\in \{1,\,\ldots ,\,n\}$, iterativno, koeficijent $c_{i}$ je podešen u pravcu $\partial f/\partial c_{i}$ . Zatim, rezultujući vektor koeficijenata $(c_{1}',\,\ldots ,\,c_{n}')$ projektuje se na najbliži vektor koeficijenata koji zadovoljava date uslove. (Obično se koriste euklidske udaljenosti. ) Proces se zatim ponavlja sve dok se ne dobije skoro optimalan vektor koeficijenata. Dobijeni algoritam je izuzetno brz u praksi, iako je malo garancija performansi dokazano.

Empirijska minimizacija rizika

Gore opisana motoda potpornih vekotra meke margine je primer empirijskog algoritma za smanjenje rizika (ERM) za gubitak zgloba . Gledano na ovaj način, metoda potpornih vekotra pripadaju prirodnoj klasi algoritama za statističko zaključivanje, a mnoge od njegovih jedinstvenih karakteristika su posledica ponašanja gubitka zgloba. Ova perspektiva može pružiti dalji uvid u to kako i zašto MPV funkcionišu i omogućiti nam da bolje analiziramo njihova statistička svojstva.

Minimizacija rizika

U nadgledanom učenju, daje se trening skup primera $X_{1}\ldots X_{n}$ sa labelama $y_{1}\ldots y_{n}$, i želimo da predvidimo $y_{n+1}$ za dato $X_{n+1}$ . Da bi se to uradilo, formira se hipoteza, $f$, tako da je $f(X_{n+1})$ "dobra" aproksimacija za $y_{n+1}$ . "Dobra" aproksimacija se obično definiše uz pomoć funkcije gubitka, $\ell (y,z)$, što karakteriše koliko je loše $z$ kao predviđanje za $y$ . Zatim bismo želeli da izaberemo hipotezu koja minimizira očekivani rizik :

$\varepsilon (f)=\mathbb {E} \left[\ell (y_{n+1},f(X_{n+1}))\right].$

U većini slučajeva ne znamo zajedničku raspodelu $X_{n+1},\,y_{n+1}$ direktno. U ovim slučajevima, uobičajena strategija je da se izabere hipoteza koja minimizuje empirijski rizik:

${\hat {\varepsilon }}(f)={\frac {1}{n}}\sum _{k=1}^{n}\ell (y_{k},f(X_{k})).$

Pod određenim pretpostavkama o redosledu slučajnih promenljivih $X_{k},\,y_{k}$ (na primer, da su generisani konačnim Markovljevim procesom), ako je skup hipoteza koje se razmatraju dovoljno mali, minimizator empirijskog rizika će se blisko približiti minimizatoru očekivanog rizika kako $n$ postaje veliko. Ovaj pristup se naziva empirijska minimizacija rizika ili ERM.

Regularizacija i stabilnost

Da bi problem minimizacije imao dobro definisano rešenje, moramo da postavimo neka ograničenja na skup ${\mathcal {H}}$ hipoteza koje se razmatraju. Ako je ${\mathcal {H}}$ normirani prostor (kao što je slučaj sa MPV), posebno efikasna tehnika je razmatranje samo tih hipoteza $f$ za koje $\lVert f\rVert _{\mathcal {H}}<k$ . Ovo je jednako izricanju kazne regularizacije ${\mathcal {R}}(f)=\lambda _{k}\lVert f\rVert _{\mathcal {H}}$, i rešavanje novog problema optimizacije

${\hat {f}}=\mathrm {arg} \min _{f\in {\mathcal {H}}}{\hat {\varepsilon }}(f)+{\mathcal {R}}(f).$

Ovaj pristup se naziva Tihonovska regularizacija .

${\mathcal {R}}(f)$ može biti neka mera složenosti hipoteze $f$, tako da prednost dobijaju jednostavnije hipoteze.

MPV i gubitak zgloba

Podsetimo se da je MPV klasifikator (meke margine)${\hat {\mathbf {w} }},b:\mathbf {x} \mapsto \operatorname {sgn}({\hat {\mathbf {w} }}^{T}\mathbf {x} -b)$ izabran da minimizuje sledeći izraz:

$\left[{\frac {1}{n}}\sum _{i=1}^{n}\max \left(0,1-y_{i}(\mathbf {w} ^{T}\mathbf {x} -b)\right)\right]+\lambda \|\mathbf {w} \|^{2}.$

Vidimo da je tehnika MPV ekvivalentna empirijskoj minimizaciji rizika sa Tihonovom regularizacijom, gde je u ovom slučaju funkcija gubitka gubitak zgloba.

$\ell (y,z)=\max \left(0,1-yz\right).$

Iz ove perspektive, MPV je usko povezana sa drugim osnovnim klasifikacionim algoritmima kao što su regularizovani najmanji kvadrati i logistička regresija . Razlika između ova tri algoritma leži u izboru funkcije gubitka: regularizovani najmanji kvadrati predstavljaju empirijsku minimizaciju rizika sa kvadratnim gubitkom, $\ell _{sq}(y,z)=(y-z)^{2}$ ; logistička regresija koristi log-gubitak,

$\ell _{\log }(y,z)=\ln(1+e^{-yz}).$

Ciljne funkcije

Razlika između gubitka zgloba i ovih drugih funkcija gubitka najbolje se može izraziti u smislu ciljnih funkcija – funkcija koja minimizira očekivani rizik za dati par slučajnih prmoneljivih $X,\,y$ .

Konkretno, neka $y_{x}$ označava $y$ uslovljeno događajem koji daje $X=x$ . U postavci klasifikacije imamo:

$y_{x}={\begin{cases}1&{\text{са вероватноћом }}p_{x}\\-1&{\text{са вероватноћом }}1-p_{x}\end{cases}}$

Dakle, optimalni klasifikator je:

$f^{*}(x)={\begin{cases}1&{\text{ако је }}p_{x}\geq 1/2\\-1&{\text{иначе}}\end{cases}}$

Za kvadratni gubitak, ciljna funkcija je funkcija uslovnog očekivanja, $f_{sq}(x)=\mathbb {E} \left[y_{x}\right]$ ; Za logistički gubitak, to je logit funkcija, $f_{\log }(x)=\ln \left(p_{x}/({1-p_{x}})\right)$ . Dok obe ove ciljne funkcije daju ispravan klasifikator, kao $\operatorname {sgn}(f_{sq})=\operatorname {sgn}(f_{\log })=f^{*}$, one nam daju više informacija nego što nam je potrebno. U stvari, one nam daju dovoljno informacija da u potpunosti opišemo raspodelu po $y_{x}$ .

S druge strane, može se proveriti da li je ciljna funkcija za gubitak zgloba tačna $f^{*}$ . Dakle, u dovoljno bogatom prostoru hipoteza — ili ekvivalentno, za odgovarajuće odabrano jezgro — MPV klasifikator će konvergirati najjednostavnijoj funkciji (u smislu ${\mathcal {R}}$ ) koji ispravno klasifikuje podatke. Ovo proširuje geometrijsku interpretaciju MPV-a – za linearnu klasifikaciju, empirijski rizik je minimiziran bilo kojom funkcijom čije margine leže između vektora podrške, a najjednostavniji od njih je klasifikator maksimalne margine.

Svojstva

MPV pripadaju porodici generalizovanih linearnih klasifikatora i mogu se tumačiti kao proširenje perceptrona . Oni se takođe mogu smatrati posebnim slučajem Tihonovske regularizacije . Posebno svojstvo je da oni istovremeno minimiziraju grešku empirijske klasifikacije i maksimiziraju geometrijsku marginu ; stoga su poznati i kao klasifikatori maksimalne margine.

Poređenje MPV-a sa drugim klasifikatorima su napravili Meier, Leisch i Hornik.

Izbor parametara

Efikasnost MPV-a zavisi od izbora jezgra, parametara jezgra i parametra meke margine $\lambda$ . Uobičajeni izbor je Gausovo jezgro, koje ima jedan parametar $\gamma$ . Najbolja kombinacija od $\lambda$ i $\gamma$ se često bira pretragom mreže sa eksponencijalno rastućim sekvencama od $\lambda$ i $\gamma$, na primer, $\lambda \in \{2^{-5},2^{-3},\dots ,2^{13},2^{15}\}$ ; $\gamma \in \{2^{-15},2^{-13},\dots ,2^{1},2^{3}\}$ . Obično se svaka kombinacija izbora parametara proverava korišćenjem unakrsne validacije i biraju se parametri sa najboljom tačnošću unakrsne provere. Alternativno, nedavni rad u Bajesovoj optimizaciji se može koristiti za odabir $\lambda$ i $\gamma$, što često zahteva procenu mnogo manjeg broja kombinacija parametara od pretraživanja mreže. Konačni model, koji se koristi za testiranje i klasifikaciju novih podataka, se zatim obučava na celom skupu za obuku koristeći izabrane parametre.

Problemi

Potencijalni nedostaci MPV-a uključuju sledeće aspekte:

• Zahteva potpuno označavanje ulaznih podataka
• Nekalibrirane verovatnoće članstva u klasama — MPV proizilazi iz Vapnikove teorije koja izbegava procenu verovatnoće na konačnim podacima
• MPV je direktno primenljiva samo za dvoklasne zadatke. Stoga se moraju primeniti algoritmi koji svode zadatak više klasa na nekoliko binarnih problema.
• Parametre rešenog modela je teško interpretirati.

Nadogradnje

Metoda grupisanja potpornih vektora

Metoda grupisanja potpornih vektora je sličana metoda koja se takođe zasniva na funkcijama jezgra, ali je prikladaan za učenje bez nadzora. Smatra se fundamentalnom metodom u nauci o podacima .

Metoda potpornih vekotra sa više klasa

Multiklasna MPV ima za cilj da dodeli oznake instancama korišćenjem metode potpornih vekotra, gde su oznake izvučene iz konačnog skupa nekoliko elemenata.

Dominantan pristup za to je svođenje jednog problema više klasa na višestruke probleme binarne klasifikacije. Uobičajene metode za takvu optimizaciju uključuju:

• Pravljenje binarnih klasifikatora koji prave razliku između jedne od oznaka i ostatka ( jedan protiv svih ) ili između svakog para klasa ( jedan protiv jedanog ). Klasifikacija novih instanci za slučaj jedan naspram svih vrši se strategijom pobednik uzima sve, u kojoj klasifikator sa najvećom izlaznom funkcijom dodeljuje klasu (važno je da izlazne funkcije budu kalibrisane da bi proizvele uporedive rezultate ). Za pristup jedan protiv jedan, klasifikacija se vrši strategijom glasanja sa maksimalnim brojem pobeda, u kojoj svaki klasifikator dodeljuje instancu jednoj od dve klase, zatim se glas za dodeljenu klasu povećava za jedan glas, i na kraju klasa sa najviše glasova određuje klasifikaciju instance.
• Usmereni aciklični graf MPV (DAGSVM)
• Ispravljanje izlaznih kodova

Kramer i Singer su predložili višeklasnu MPV koji baca problem višeklasne klasifikacije u jedan problem optimizacije, umesto da ga dekomponuje na višestruke probleme binarne klasifikacije. Vidi takođe Li, Lin i Vaba i Van den Burg i Groenen.

Transduktivna metoda potpornih vekotra

Transduktivna metoda potpornih vekotra prošire MPV tako što mogu da tretiraju i delimično obeležene podatke u polunadgledanom učenju prateći principe transdukcije . Ovde, pored kompleta za obuku ${\mathcal {D}}$, učeniku se takođe daje set

${\mathcal {D}}^{\star }=\{{\vec {x}}_{i}^{\star }\mid {\vec {x}}_{i}^{\star }\in \mathbb {R} ^{p}\}_{i=1}^{k}$

test primera koje treba klasifikovati. Formalno, transduktivna metoda potpornih vektora je definisana sledećim primarnim problemom optimizacije:

Minimizovati (u ${{\vec {w}},b,{\vec {y^{\star }}}}$ )

${\frac {1}{2}}\|{\vec {w}}\|^{2}$

podleže (za bilo koje $i=1,\dots ,n$ i bilo koje $j=1,\dots ,k$ )

$y_{i}({\vec {w}}\cdot {\vec {x_{i}}}-b)\geq 1,$

$y_{j}^{\star }({\vec {w}}\cdot {\vec {x_{j}^{\star }}}-b)\geq 1,$

i

$y_{j}^{\star }\in \{-1,1\}.$

Transduktivne metode potpornih vektora je predstavio Vladimir N. Vapnik 1998. godine.

Strukturirana MPV

MPV su generalizovane na strukturirane MPV, gde je prostor za oznake strukturiran i verovatno beskonačne veličine.

Regresija

Regresija vektora podrške (predviđanje) sa različitim pragovima ε . Kako se ε povećava, predviđanje postaje manje osetljivo na greške.

Verziju MPV za regresiju predložili su 1996. Vladimir N. Vapnik, Haris Draker, Kristofer Džej Si Berdžes, Linda Kaufman i Aleksandar J. Smola. Ovaj metod se naziva regresija vektora potpora. Model proizveden klasifikacijom vektora podrške (kao što je gore opisano) zavisi samo od podskupa podataka o obuci, jer funkcija troškova za izgradnju modela ne brine o tačkama obuke koje se nalaze izvan margine. Analogno tome, model koji proizvodi SVR(support-vector regression) zavisi samo od podskupa podataka o obuci, jer funkcija greške za izgradnju modela ignoriše sve podatke o obuci koji su bliski predviđanju modela. Drugu MPV verziju poznatu kao metoda potpornih vektora najmanjih kvadrata (LS-SVM) su predložili Suikens i Vandevalle.

Obuka originalnog SVR-a znači rešavanje

minimizirati ${\frac {1}{2}}\|w\|^{2}$

za $|y_{i}-\langle w,x_{i}\rangle -b|\leq \varepsilon$

gde je $x_{i}$ uzorak za obuku sa ciljnom vrednošću $y_{i}$ . Unutrašnji proizvod plus presretanje $\langle w,x_{i}\rangle +b$ je predviđanje za taj uzorak, i $\varepsilon$ je slobodan parametar koji služi kao prag: sva predviđanja moraju biti unutar $\varepsilon$ raspona istinitih predviđanja. "Labave" promenljive se obično dodaju u gore navedenom da bi se omogućile greške i omogućila aproksimacija u slučaju da je gornji problem neizvodljiv.

Bajesova MPV

Polson i Skot su 2011. pokazali da MPV prihvata Bajesovu interpretaciju kroz tehniku povećanja podataka . U ovom pristupu MPV se posmatra kao grafički model (gde su parametri povezani preko raspodele verovatnoće). Ovaj detaljni pregled omogućava primenu Bajesove tehnike na MPV, kao što je fleksibilana funkcija modeliranja, automatsko hiperparametersko podešavanje, i predvidljivu nesigurnu kvantifikaciju . „Nedavno je Florijan”. arXiv:search/stat?searchtype=author&query=Wenzel%2C+F  .  Vencel razvio skalabilnu verziju Bajesovoe MPV, omogućavajući primenu Bajesovoe MPV na velike podatke . Florian Venzel je razvio dve različite verzije, šemu varijacionog zaključivanja (VI) za Bajesov model potpornih vektora sa jezgrom (SVM) i stohastičku verziju (SVI) za linearni Bajesov MPV.

Implementacija

Parametri hiperravni maksimalne margine su izvedeni rešavanjem optimizacije. Postoji nekoliko specijalizovanih algoritama za brzo rešavanje problema kvadratnog programiranja (KP) koji proizilazi iz MPV, uglavnom se oslanjajući na heuristiku za razbijanje problema na manje delove kojima je lakše upravljati.

Drugi pristup je korišćenje metode unutrašnje tačke koja koristi iteracije slične Njutnovoj metodi da bi se pronašlo rešenje Karuš–Kun–Takerovih uslova primarnog i dualnog problema. Umesto rešavanja niza raščlanjenih problema, ovaj pristup direktno rešava problem u celini. Da bi se izbeglo rešavanje linearnog sistema koji uključuje veliku matricu jezgra, aproksimacija niskog ranga matrici se često koristi u triku jezgra.

Uobičajeni metod je i Platoov algoritam sekvencijalne minimalne optimizacije, koji razlaže problem na 2-dimenzionalne podprobleme koji se rešavaju analitički, eliminišući potrebu za numeričkim algoritmom optimizacije i skladištenjem matrice. Ovaj algoritam je konceptualno jednostavan, lak za implementaciju, generalno brži i ima bolja svojstva skaliranja za teške MPV probleme.

Poseban slučaj lineranih MPV može se efikasnije rešiti istom vrstom algoritama koji se koriste za optimizaciju njegovog bliskog rođaka, logističke regresije ; ova klasa algoritama uključuje sub-gradijenti spust (npr. PEGASOS) i koordinatni spust (npr. LIBLINEAR ). LIBLINEAR ima impresivna vremena obuke. Svaka iteracija konvergencije traje linearno u vremenu potrebnom za čitanje trening podataka, a iteracije takođe imaju svojstvo Q-linearne konvergencije, što algoritam čini izuzetno brzim.

Opšta MPV jezgra se takođe mogu efikasnije rešiti korišćenjem sub-gradijentnog spusta (npr P-packSVM ), posebno kada je paralelizacija dozvoljena.

MPV jezgra su dostupna u mnogim kompletima alata za mašinsko učenje, uključujući <a href="https://en.wikipedia.org/wiki/LIBSVM" rel="mw:ExtLink" title="LIBSVM" class="cx-link" data-linkid="815">LIBSVM</a>, MATLAB, SAS, SVMlight, kernlab, <a href="https://en.wikipedia.org/wiki/Scikit-learn" rel="mw:ExtLink" title="Scikit-learn" class="cx-link" data-linkid="817">scikit-learn</a>-, <a href="https://en.wikipedia.org/wiki/Shogun_(toolbox)" rel="mw:ExtLink" title="Shogun (toolbox)" class="cx-link" data-linkid="818">Shogun</a>, <a href="https://en.wikipedia.org/wiki/Weka_(machine_learning)" rel="mw:ExtLink" title="Weka (machine learning)" class="cx-link" data-linkid="819">Weka</a>, Shark, JKernelMachines, OpenCV i druge.

Preporučuje se prethodna obrada podataka (standardizacija) da bi se poboljšala tačnost klasifikacije. Postoji nekoliko metoda standardizacije, kao što su min-maks, normalizacija decimalnim skaliranjem, Z-score. Oduzimanje srednje vrednosti i deljenje varijansom svake karakteristike se obično koristi za M.

 

Dodatna literatura

• Bennett, Kristin P.; Campbell, Colin (2000). „Support Vector Machines: Hype or Hallelujah?” (PDF). SIGKDD Explorations. 2 (2): 1—13. doi:10.1145/380995.380999. 
• Cristianini, Nello; Shawe-Taylor, John (2000). An Introduction to Support Vector Machines and other kernel-based learning methods. Cambridge University Press. ISBN 0-521-78019-5. 
• Fradkin, Dmitriy; Muchnik, Ilya (2006). „Support Vector Machines for Classification” (PDF). Ur.: Abello, J.; Carmode, G. Discrete Methods in Epidemiology. DIMACS Series in Discrete Mathematics and Theoretical Computer Science. 70. str. 13—20. 
• Ivanciuc, Ovidiu (2007). „Applications of Support Vector Machines in Chemistry” (PDF). Reviews in Computational Chemistry. 23: 291—400. ISBN 9780470116449. doi:10.1002/9780470116449.ch6. 
• James, Gareth; Witten, Daniela; Hastie, Trevor; Tibshirani, Robert (2013). „Support Vector Machines” (PDF). An Introduction to Statistical Learning : with Applications in R. New York: Springer. str. 337—372. ISBN 978-1-4614-7137-0. 
• Schölkopf, Bernhard; Smola, Alexander J. (2002). Learning with Kernels. Cambridge, MA: MIT Press. ISBN 0-262-19475-9. 
• Steinwart, Ingo; Christmann, Andreas (2008). Support Vector Machines. New York: Springer. ISBN 978-0-387-77241-7. 
• Theodoridis, Sergios; Koutroumbas, Konstantinos (2009). Pattern Recognition (4th izd.). Academic Press. ISBN 978-1-59749-272-0. 

Spoljašnje veze

• libsvm, <a href="https://en.wikipedia.org/wiki/LIBSVM" rel="mw:ExtLink" title="LIBSVM" class="cx-link" data-linkid="924">LIBSVM</a> je popularna biblioteka za učenike MPV-a
• liblinear je biblioteka za veliku linearnu klasifikaciju uključujući neke MPV
• [1]SVM light je kolekcija softverskih alata za učenje i klasifikaciju koristeći MPV
• [2] Arhivirano na sajtu Wayback Machine (5. maj 2013)SVMJS live demo je Grafički korisnički interfejs demo za JavaScript implementaciju MPV-a