Метода потпорних вектора

 

У машинском учењу, метода потпорних вектора је модел учења под надзором са припадајућим алгоритмима учења који анализирају податке за класификацију и регресиону анализу . Развио ју је Владимир Вапник са колегама у AT&T Bell Лабораторијама. Метода потпорних вектора је једна од најпоузданијих метода предвиђања, заснована на статистичким оквирима учења или VC теорији коју су предложили Вапник (1982, 1995) и Червонинкс (1974). Имајући у виду скуп примера за обуку, од којих је сваки означен као да припада једној од две категорије, МПВ алгоритам за обуку гради модел који додељује нове примере једној или другој категорији, чинећи га ненагађајућим бинарним линеарним класификатором . МПВ пресликава примере обуке на тачке у простору како би максимизирао ширину јаза између две категорије. Нови примери се затим мапирају у исти простор и предвиђају да припадају категорији на основу које стране јаза падају.

Поред извођења линеарне класификације, МПВ-ови могу ефикасно да изврше нелинеарну класификацију користећи оно што се назива трик језгра, имплицитно мапирајући своје улазе у просторе карактеристика високе димензије.

Када подаци нису означени, надгледано учење није могуће и потребан је приступ учењу без надзора, који покушава да пронађе природно груписање података у групе, а затим мапира нове податке у ове формиране групе. Алгоритам за груписање потпорних вектора , који су креирали Хава Сигелман и Владимир Вапник, примењује статистику вектора подршке, развијену у алгоритму мотоде поджаних вектора, за категоризацију неозначених података, и један је од најчешће коришћених алгоритама за груписање у инустријској апликацији.

Мотивација

H₁ не раздваја класе. H₂ раздваја, али само са малом маргином. H₃ их раздваја са максималном маргином.

Класификација података је уобичајен задатак у машинском учењу . Претпоставимо да свака дата тачка припада једној од две класе, а циљ је да се одлучи у којој ће класи бити нова тачка података . У случају методе потпорних вектора, тачка података се посматра као $p$ -димензионални вектор (листа $p$ бројева), и желимо да знамо да ли можемо да одвојимо такве тачке са а $(p-1)$ -димензионалном хиперравни . Ово се зове линеарни класификатор . Постоји много хиперравни које могу класификовати податке. Разуман избор као најбоља хиперравна је она који постиже највеће раздвајање, или маргину, између две класе. Зато бирамо хиперраван тако да је растојање од ње до најближе тачке података на свакој страни максимизирано. Ако таква хиперраван постоји, позната је као хиперраван максималне маргине, а линеарни класификатор који он дефинише је познат као класификатор максималне маргине; или еквивалентно, перцептрон оптималне стабилности .

Дефиниција

Модел потпорних векотра конструише хиперраван или скуп хиперравни у високо- или бесконачно-димензионалном простору, који се може користити за класификацију, регресију или друге задатке као што је откривање одступања. Добро раздвајање се постиже хиперравнином која има највећу удаљеност до најближе тачке података за обуку било које класе (функционална маргина), пошто генерално што је већа маргина, то је мања грешка генерализације класификатора.

Кернел машина

Док се оригинални проблем може навести у коначнодимензионалном простору, често се дешава да скупови дискриминанти нису линеарно одвојиви у том простору. Из тог разлога, предложено је да се оригинални коначно-димензионални простор преслика у простор много веће димензије, што вероватно олакшава раздвајање у том простору. Да би рачунарско оптерећење било разумно, мапирања које користе МПВ шеме су дизајниране да обезбеде да се тачкасти производи парова вектора улазних података могу лако израчунати у смислу променљивих у оригиналном простору, дефинисањем у смислу функције језгра $k(x,y)$ одабрано да одговара проблему. Хиперравне у вишедимензионалном простору су дефинисане као скуп тачака чији је тачкасти производ са вектором у том простору константан, при чему је такав скуп вектора ортогоналан (а тиме и минималан скуп вектора који дефинише хиперраван. Вектори који дефинишу хиперравне могу се изабрати да буду линеарне комбинације са параметрима $\alpha _{i}$ слике вектора обележја $x_{i}$ који се јављају у бази података. Са овим избором хиперравнине, тачке $x$ у простору обележја који су пресликани у хиперравнину дефинисани су релацијом $\textstyle \sum _{i}\alpha _{i}k(x_{i},x)={\text{constant}}.$ Имајте на уму да ако $k(x,y)$ постаје мали као $y$ расте даље од $x$, сваки члан у збиру мери степен блискости испитане тачке $x$ до одговарајуће тачке базе података $x_{i}$ . На овај начин, збир горњих језгара може да се користи за мерење релативне близине сваке испитне тачке тачкама података које потичу из једног или другог скупа који се дискриминише. Обратите пажњу на чињеницу да је скуп тачака $x$ пресликан у било коју хиперравнину може бити прилично замршен као резултат, омогућавајући много сложенију дискриминацију између скупова који уопште нису конвексни у оригиналном простору.

Апликације

Методе потпорних векотра се могу користити за решавање различитих проблема из стварног света:

• Методе потпорних векотра су корисне у категоризацији текста и хипертекста, јер њихова примена може значајно смањити потребу за означеним инстанцама обуке и у стандардним индуктивним и трансдуктивним поставкама. Неке методе за плитко семантичко рашчлањивање засноване су на методама потпорних векотра.
• Класификација слика се такође може извршити помоћу МПВ-а. Експериментални резултати показују да МПВ постижу знатно већу тачност претраге од традиционалних шема за прецизирање упита након само три до четири круга повратних информација о релевантности. Ово важи и за системе за сегментацију слика, укључујући и оне који користе модификовану верзију МПВ-а која користи привилеговани приступ како је предложио Вапник.
• Класификација сателитских података као што су SAR подаци коришћењем надгледаног МПВ.
• Руком писани знакови се могу препознати помоћу МПВ.
• Алгоритам МПВ има широку примену у биологијо и другим наукама. Коришћени су за класификацију протеина са до 90% исправно класификованих једињења. Пермутациони тестови засновани на МПВ тежинама су предложени као механизам за интерпретацију МПВ модела. Методе потпорних векотра су такође коришћене за тумачење МПВ модела у прошлости. Постхок интерпретација модела потпорних вектора у циљу идентификације карактеристика које модел користи за предвиђање је релативно нова област истраживања од посебног значаја у биолошким наукама.

Историја

Оригинални МПВ алгоритам су измислили Владимир Н. Вапник и Алексеј Ја. Червонинкс 1963. године. Године 1992. Бернхард Босер, Изабела Гујон и Владимир Вапник су предложили начин да се створе нелинеарни класификатори применом трика језгра да би се добиле максималне маргине хиперравни. Инкарнацију „меке маргине“, као што се уобичајено користе софтверски пакети, предложили су Корина Кортес и Вапник 1993. године и објављени 1995. године

Линеарна МПВ

Хиперраван максималне маргине и маргине за МПВ обучен са узорцима из две класе. Узорци на маргини називају се вектори подршке.

Имамо скуп података за обуку од $n$ тачке форме

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

где $y_{i}$ су или 1 или −1, од којих сваки указује на класу до које је тачка $\mathbf {x} _{i}$ припада. Сваки $\mathbf {x} _{i}$ је $p$-димензионални реални вектор. Желимо да пронађемо "хиперраван максималне маргине" која дели групу тачака $\mathbf {x} _{i}$ за које $y_{i}=1$ из групе бодова за које $y_{i}=-1$, који је дефинисан тако да растојање између хиперравни и најближе тачке $\mathbf {x} _{i}$ из било које групе буде максимизиран.

Било која хиперраван се може написати као скуп тачака $\mathbf {x}$ уколико испуњава:

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

где је $\mathbf {w}$ (не нужно нормализован) вектор нормале на хиперраван. Ово је слично Хесеновом нормалном облику, осим тога $\mathbf {w}$ није нужно јединични вектор. Параметар ${\tfrac {b}{\|\mathbf {w} \|}}$ одређује помак хиперравни од почетка дуж вектора нормале $\mathbf {w}$ .

Тврда маргина

Ако су тренинг подаци линеарно раздвојиви, можемо изабрати две паралелне хиперравне које раздвајају две класе података, тако да је растојање између њих што је могуће веће. Подручје ограничено са ове две хиперравне назива се „маргина“, а хиперраван максималне маргине је хиперраван која се налази на пола пута између њих. Са нормализованим или стандардизованим скупом података, ове хиперравне се могу описати слдећим једначинама:

$\mathbf {w} ^{T}\mathbf {x} -b=1$ (све на или изнад ове границе припрада једној класи, са ознаком 1)

и

$\mathbf {w} ^{T}\mathbf {x} -b=-1$ (све на или испод ове границе припада другој класи, са ознаком −1).

Геометријски, растојање између ове две хиперравне је ${\tfrac {2}{\|\mathbf {w} \|}}$, тако да би максимизовали растојање између равни које желимо да минимизирамо $\|\mathbf {w} \|$ . Растојање се израчунава коришћењем једначине удаљености тачке од равни . Такође морамо да спречимо да тачке података падну на маргину, додајемо следеће ограничење: за сваку $i$ било

$\mathbf {w} ^{T}\mathbf {x} _{i}-b\geq 1$, ако је $y_{i}=1$,

или

$\mathbf {w} ^{T}\mathbf {x} _{i}-b\leq -1$, ако је $y_{i}=-1$ .

Ови услови наводе да свака тачка података мора лежати на исправној страни маргине.

Ово се може написати и као:

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

Можемо да саставимо све ово и добијемо проблем оптимизације:

„Минимизуј $\|\mathbf {w} \|$ на $y_{i}(\mathbf {w} ^{T}\mathbf {x} _{i}-b)\geq 1$ за $i=1,\ldots ,n$ ."

$\mathbf {w}$ и $b$ који решавају овај проблем одређују наш класификатор, $\mathbf {x} \mapsto \operatorname {sgn}(\mathbf {w} ^{T}\mathbf {x} -b)$ где је $\operatorname {sgn}(\cdot )$ функција знака .

Важна последица овог геометријског описа је да је хиперраван максималне маргине потпуно одређена векотром ${\vec {x}}_{i}$ који му је најближи. Ови $\mathbf {x} _{i}$ називају се вектори подршке .

Мека маргина

За проширење МПВ на случајеве у којима подаци нису линеарно одвојиви, функција губитка зглоба је од помоћи

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

Напоменути да је $y_{i}$ i-ти циљ (то јест, у овом случају је 1 или −1), и $\mathbf {w} ^{T}\mathbf {x} _{i}-b$ је i-ти излаз.

Ова функција је нула ако је услов из (1) задовољен, другим речима, ако $\mathbf {x} _{i}$ лежи на исправној страни маргине. За податке на погрешној страни маргине, вредност функције је пропорционална удаљености од тачке од маргине.

Циљ оптимизације је да се минимизује

$\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],$

где је параметар $\lambda >0$ одређује компромис између повећања величине маргине и обезбеђивања да $\mathbf {x} _{i}$ леже на исправној страни маргине. Дакле, за довољно мале вредности од $\lambda$, понашаће се слично МПВ-а са тврдом маргином, ако се улазни подаци линеарно класификују, али ће и даље научити да ли је правило класификације одрживо или не. (Овај параметар $\lambda$ се такође назива Ц, нпр. у <a href="https://en.wikipedia.org/wiki/LIBSVM" rel="mw:ExtLink" title="LIBSVM" class="cx-link" data-linkid="534">LIBSVM</a> . )

Нелинеарна класификација

Кернел машина

Оригинални алгоритам максималне маргине хиперавни који је предложио Вапник 1963. године конструисао је линеарни класификатор . Међутим, 1992. године, Бернхард Босер, Изабел Гујон и Владимир Вапник су предложили начин за креирање нелинеарних класификатора применом трика језгра (првобитно предложен од Аизермана ) за максималне маргине хиперравни. Добијени алгоритам је формално сличан, осим што је сваки тачкасти производ замењен нелинеарном функцијом језгра. Ово омогућава алгоритму да уклопи хиперраван максималне маргине у трансформисани простор обележја. Трансформација може бити нелинеарна, а трансформисани простор вишедимензионалан; иако је класификатор хиперравна у трансформисаном простору обележја, он може бити нелинеаран у оригиналном улазном простору.

Важно је напоменути да рад у вишедимензионалном простору карактеристика повећава грешку генерализације методе потпорних вектора, уколико има довољно тренинг узорака алгоритам ће и даље ради добро.

Нека уобичајена језгра укључују:

• Полином (хомоген) : $k({\vec {x_{i}}},{\vec {x_{j}}})=({\vec {x_{i}}}\cdot {\vec {x_{j}}})^{d}$ .
• Полином (нехомоген): $k({\vec {x_{i}}},{\vec {x_{j}}})=({\vec {x_{i}}}\cdot {\vec {x_{j}}}+1)^{d}$ .
• Гаусова радијална базна функција : $k({\vec {x_{i}}},{\vec {x_{j}}})=\exp(-\gamma \|{\vec {x_{i}}}-{\vec {x_{j}}}\|^{2})$ за $\gamma >0$ . Понекад се параметризују коришћењем $\gamma =1/(2\sigma ^{2})$ .
• Хиперболички тангент : $k({\vec {x_{i}}},{\vec {x_{j}}})=\tanh(\kappa {\vec {x_{i}}}\cdot {\vec {x_{j}}}+c)$ за неке (не за све) $\kappa >0$ и $c<0$ .

Језгро је повезано са трансформацијом $\varphi ({\vec {x_{i}}})$ по једначини $k({\vec {x_{i}}},{\vec {x_{j}}})=\varphi ({\vec {x_{i}}})\cdot \varphi ({\vec {x_{j}}})$ . Вредност W је такође у трансформисаном простору, са $\textstyle {\vec {w}}=\sum _{i}\alpha _{i}y_{i}\varphi ({\vec {x}}_{i})$ . Тачкасти производи са w за класификацију се поново могу израчунати помоћу трика језгра, тј $\textstyle {\vec {w}}\cdot \varphi ({\vec {x}})=\sum _{i}\alpha _{i}y_{i}k({\vec {x}}_{i},{\vec {x}})$ .

Израчунавање класификатора МПВ

Израчунавање (меке маргине) класификатора МПВ доводи до минимизирања израза форме

$\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)$

Фокусирамо се на класификатор меке маргине пошто, као што је горе наведено, одабир довољно мале вредности за $\lambda$ даје класификатор тврде маргине за линеарно класификујуће улазне податке. Класични приступ, који укључује свођење (2) на проблем квадратног програмирања, детаљно је описан у наставку. Затим ће се расправљати о новијим приступима као што су суб-градијентални спуст и координатни спуст.

Примал

Минимизовање израза (2) се може написати као проблем ограничене оптимизације са диференцијабилном циљном функцијом овако:

За сваки $i\in \{1,\,\ldots ,\,n\}$ уводимо променљиву $\zeta _{i}=\max \left(0,1-y_{i}(\mathbf {w} ^{T}\mathbf {x} _{i}-b)\right)$ . Напоменути да је $\zeta _{i}$ најмањи ненегативни број који задовољава(испуњава) $y_{i}(\mathbf {w} ^{T}\mathbf {x} _{i}-b)\geq 1-\zeta _{i}.$

Стога можемо преписати проблем оптимизације на следећи начин

${\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.$

Ово се зове примарни проблем.

Дуал

Решавањем Лагранжовог дуала горњег проблема добија се упрошћени проблем

${\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.$

Ово се зове дуални проблем. Пошто је проблем двоструке максимизације квадратна функција од $c_{i}$ а подлеже линеарним ограничењима, ефикасно се решава помоћу алгоритама квадратног програмирања.

Овде, променљиве $c_{i}$ дефинисане су тако да

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

Штавише, $c_{i}=0$ тачно када $\mathbf {x} _{i}$ лежи на исправној страни маргине, и $0<c_{i}<(2n\lambda )^{-1}$ када $\mathbf {x} _{i}$ лежи на граници маргине. Следи да се $\mathbf {w}$ може написати као линеарна комбинација потпорних векотра.

Офсет, $b$, може се повратити проналажењем $\mathbf {x} _{i}$ на граници маргине и решавањем:

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

(Напоменути да је $y_{i}^{-1}=y_{i}$ јер је $y_{i}=\pm 1$ . )

Трик језгра

Тренинг пример МПВ са језгром датим са φふぁい(( a, b )) = ( a, b, a ² + b ² )

Претпоставимо сада да бисмо желели да научимо правило нелинеарне класификације које одговара правилу линеарне класификације за трансформисане тачке података $\varphi (\mathbf {x} _{i}).$ Штавише, дата нам је функција језгра $k$ која задовољава $k(\mathbf {x} _{i},\mathbf {x} _{j})=\varphi (\mathbf {x} _{i})\cdot \varphi (\mathbf {x} _{j})$ .

Познато нам је да вектор класификације $\mathbf {w}$ у трансформисаном простору задовољава

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

где се $c_{i}$ добија се решавањем задатка оптимизације

${\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.$

Коефицијенти $c_{i}$ се могу решити коришћењем квадратног програмирања, као и раније. Опет, можемо пронаћи неки индекс $i$ тако да $0<c_{i}<(2n\lambda )^{-1}$, тако да $\varphi (\mathbf {x} _{i})$ лежи на граници маргине у трансформисаном простору, а затим можемо решити

${\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}}$

коначно,

$\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).$

Савремене методе

Најновији алгоритми за проналажење класификатора МПВ укључују суб-градијентни спус и координатни спуст. Обе технике показале су се да нуде значајне предности у односу на традиционални приступ када се ради са великим, ретким скуповима података — методе суб-градијента су посебно ефикасне када постоји много примера за обуку и координисани спуст када је димензија простора обележја велика.

Суб-градијенти спуст

Суб-градијентни спуст алгоритам за МПВ ради директно са изразом

$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}.$

Напоменути да $f$ је конвексна функција од $\mathbf {w}$ и $b$ . Као такав, традиционални градијенти спуст (или СГС) се може прилагодити, где уместо узимања корака у правцу функције градијента, корак се узима у правцу вектора изабраног из функције суб-градијента . Овај приступ има предност у томе што се, за одређене имплементације, број итерација не повећава са $n$, број тачака података.

Координатни спуст

Алгоритми координатног спуста за МПВ раде из дуалног проблема

${\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.$

За свако $i\in \{1,\,\ldots ,\,n\}$, итеративно, коефицијент $c_{i}$ је подешен у правцу $\partial f/\partial c_{i}$ . Затим, резултујући вектор коефицијената $(c_{1}',\,\ldots ,\,c_{n}')$ пројектује се на најближи вектор коефицијената који задовољава дате услове. (Обично се користе еуклидске удаљености. ) Процес се затим понавља све док се не добије скоро оптималан вектор коефицијената. Добијени алгоритам је изузетно брз у пракси, иако је мало гаранција перформанси доказано.

Емпиријска минимизација ризика

Горе описана мотода потпорних векотра меке маргине је пример емпиријског алгоритма за смањење ризика (ЕРМ) за губитак зглоба . Гледано на овај начин, метода потпорних векотра припадају природној класи алгоритама за статистичко закључивање, а многе од његових јединствених карактеристика су последица понашања губитка зглоба. Ова перспектива може пружити даљи увид у то како и зашто МПВ функционишу и омогућити нам да боље анализирамо њихова статистичка својства.

Минимизација ризика

У надгледаном учењу, даје се тренинг скуп примера $X_{1}\ldots X_{n}$ са лабелама $y_{1}\ldots y_{n}$, и желимо да предвидимо $y_{n+1}$ за дато $X_{n+1}$ . Да би се то урадило, формира се хипотеза, $f$, тако да је $f(X_{n+1})$ "добра" апроксимација за $y_{n+1}$ . "Добра" апроксимација се обично дефинише уз помоћ функције губитка, $\ell (y,z)$, што карактерише колико је лоше $z$ као предвиђање за $y$ . Затим бисмо желели да изаберемо хипотезу која минимизира очекивани ризик :

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

У већини случајева не знамо заједничку расподелу $X_{n+1},\,y_{n+1}$ директно. У овим случајевима, уобичајена стратегија је да се изабере хипотеза која минимизује емпиријски ризик:

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

Под одређеним претпоставкама о редоследу случајних променљивих $X_{k},\,y_{k}$ (на пример, да су генерисани коначним Марковљевим процесом), ако је скуп хипотеза које се разматрају довољно мали, минимизатор емпиријског ризика ће се блиско приближити минимизатору очекиваног ризика како $n$ постаје велико. Овај приступ се назива емпиријска минимизација ризика или ЕРМ.

Регуларизација и стабилност

Да би проблем минимизације имао добро дефинисано решење, морамо да поставимо нека ограничења на скуп ${\mathcal {H}}$ хипотеза које се разматрају. Ако је ${\mathcal {H}}$ нормирани простор (као што је случај са МПВ), посебно ефикасна техника је разматрање само тих хипотеза $f$ за које $\lVert f\rVert _{\mathcal {H}}<k$ . Ово је једнако изрицању казне регуларизације ${\mathcal {R}}(f)=\lambda _{k}\lVert f\rVert _{\mathcal {H}}$, и решавање новог проблема оптимизације

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

Овај приступ се назива Тихоновска регуларизација .

${\mathcal {R}}(f)$ може бити нека мера сложености хипотезе $f$, тако да предност добијају једноставније хипотезе.

МПВ и губитак зглоба

Подсетимо се да је МПВ класификатор (меке маргине)${\hat {\mathbf {w} }},b:\mathbf {x} \mapsto \operatorname {sgn}({\hat {\mathbf {w} }}^{T}\mathbf {x} -b)$ изабран да минимизује следећи израз:

$\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}.$

Видимо да је техника МПВ еквивалентна емпиријској минимизацији ризика са Тихоновом регуларизацијом, где је у овом случају функција губитка губитак зглоба.

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

Из ове перспективе, МПВ је уско повезана са другим основним класификационим алгоритмима као што су регуларизовани најмањи квадрати и логистичка регресија . Разлика између ова три алгоритма лежи у избору функције губитка: регуларизовани најмањи квадрати представљају емпиријску минимизацију ризика са квадратним губитком, $\ell _{sq}(y,z)=(y-z)^{2}$ ; логистичка регресија користи лог-губитак,

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

Циљне функције

Разлика између губитка зглоба и ових других функција губитка најбоље се може изразити у смислу циљних функција – функција која минимизира очекивани ризик за дати пар случајних прмонељивих $X,\,y$ .

Конкретно, нека $y_{x}$ означава $y$ условљено догађајем који даје $X=x$ . У поставци класификације имамо:

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

Дакле, оптимални класификатор је:

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

За квадратни губитак, циљна функција је функција условног очекивања, $f_{sq}(x)=\mathbb {E} \left[y_{x}\right]$ ; За логистички губитак, то је logit функција, $f_{\log }(x)=\ln \left(p_{x}/({1-p_{x}})\right)$ . Док обе ове циљне функције дају исправан класификатор, као $\operatorname {sgn}(f_{sq})=\operatorname {sgn}(f_{\log })=f^{*}$, оне нам дају више информација него што нам је потребно. У ствари, оне нам дају довољно информација да у потпуности опишемо расподелу по $y_{x}$ .

С друге стране, може се проверити да ли је циљна функција за губитак зглоба тачна $f^{*}$ . Дакле, у довољно богатом простору хипотеза — или еквивалентно, за одговарајуће одабрано језгро — МПВ класификатор ће конвергирати најједноставнијој функцији (у смислу ${\mathcal {R}}$ ) који исправно класификује податке. Ово проширује геометријску интерпретацију МПВ-а – за линеарну класификацију, емпиријски ризик је минимизиран било којом функцијом чије маргине леже између вектора подршке, а најједноставнији од њих је класификатор максималне маргине.

Својства

МПВ припадају породици генерализованих линеарних класификатора и могу се тумачити као проширење перцептрона . Они се такође могу сматрати посебним случајем Тихоновске регуларизације . Посебно својство је да они истовремено минимизирају грешку емпиријске класификације и максимизирају геометријску маргину ; стога су познати и као класификатори максималне маргине.

Поређење МПВ-а са другим класификаторима су направили Меиер, Леисцх и Хорник.

Избор параметара

Ефикасност МПВ-а зависи од избора језгра, параметара језгра и параметра меке маргине $\lambda$ . Уобичајени избор је Гаусово језгро, које има један параметар $\gamma$ . Најбоља комбинација од $\lambda$ и $\gamma$ се често бира претрагом мреже са експоненцијално растућим секвенцама од $\lambda$ и $\gamma$, на пример, $\lambda \in \{2^{-5},2^{-3},\dots ,2^{13},2^{15}\}$ ; $\gamma \in \{2^{-15},2^{-13},\dots ,2^{1},2^{3}\}$ . Обично се свака комбинација избора параметара проверава коришћењем унакрсне валидације и бирају се параметри са најбољом тачношћу унакрсне провере. Алтернативно, недавни рад у Бајесовој оптимизацији се може користити за одабир $\lambda$ и $\gamma$, што често захтева процену много мањег броја комбинација параметара од претраживања мреже. Коначни модел, који се користи за тестирање и класификацију нових података, се затим обучава на целом скупу за обуку користећи изабране параметре.

Проблеми

Потенцијални недостаци МПВ-а укључују следеће аспекте:

• Захтева потпуно означавање улазних података
• Некалибриране вероватноће чланства у класама — МПВ произилази из Вапникове теорије која избегава процену вероватноће на коначним подацима
• МПВ је директно применљива само за двокласне задатке. Стога се морају применити алгоритми који своде задатак више класа на неколико бинарних проблема.
• Параметре решеног модела је тешко интерпретирати.

Надоградње

Метода груписања потпорних вектора

Метода груписања потпорних вектора је сличана метода која се такође заснива на функцијама језгра, али је прикладаан за учење без надзора. Сматра се фундаменталном методом у науци о подацима .

Метода потпорних векотра са више класа

Мултикласна МПВ има за циљ да додели ознаке инстанцама коришћењем методе потпорних векотра, где су ознаке извучене из коначног скупа неколико елемената.

Доминантан приступ за то је свођење једног проблема више класа на вишеструке проблеме бинарне класификације. Уобичајене методе за такву оптимизацију укључују:

• Прављење бинарних класификатора који праве разлику између једне од ознака и остатка ( један против свих ) или између сваког пара класа ( један против једаног ). Класификација нових инстанци за случај један наспрам свих врши се стратегијом победник узима све, у којој класификатор са највећом излазном функцијом додељује класу (важно је да излазне функције буду калибрисане да би произвеле упоредиве резултате ). За приступ један против један, класификација се врши стратегијом гласања са максималним бројем победа, у којој сваки класификатор додељује инстанцу једној од две класе, затим се глас за додељену класу повећава за један глас, и на крају класа са највише гласова одређује класификацију инстанце.
• Усмерени ациклични граф МПВ (DAGSVM)
• Исправљање излазних кодова

Крамер и Сингер су предложили вишекласну МПВ који баца проблем вишекласне класификације у један проблем оптимизације, уместо да га декомпонује на вишеструке проблеме бинарне класификације. Види такође Ли, Лин и Ваба и Ван ден Бург и Гроенен.

Трансдуктивна метода потпорних векотра

Трансдуктивна метода потпорних векотра прошире МПВ тако што могу да третирају и делимично обележене податке у полунадгледаном учењу пратећи принципе трансдукције . Овде, поред комплета за обуку ${\mathcal {D}}$, ученику се такође даје сет

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

тест примера које треба класификовати. Формално, трансдуктивна метода потпорних вектора је дефинисана следећим примарним проблемом оптимизације:

Минимизовати (у ${{\vec {w}},b,{\vec {y^{\star }}}}$ )

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

подлеже (за било које $i=1,\dots ,n$ и било које $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,$

и

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

Трансдуктивне методе потпорних вектора је представио Владимир Н. Вапник 1998. године.

Структурирана МПВ

МПВ су генерализоване на структуриране МПВ, где је простор за ознаке структуриран и вероватно бесконачне величине.

Регресија

Регресија вектора подршке (предвиђање) са различитим праговима εいぷしろん . Како се εいぷしろん повећава, предвиђање постаје мање осетљиво на грешке.

Верзију МПВ за регресију предложили су 1996. Владимир Н. Вапник, Харис Дракер, Кристофер Џеј Си Берџес, Линда Кауфман и Александар Ј. Смола. Овај метод се назива регресија вектора потпора. Модел произведен класификацијом вектора подршке (као што је горе описано) зависи само од подскупа података о обуци, јер функција трошкова за изградњу модела не брине о тачкама обуке које се налазе изван маргине. Аналогно томе, модел који производи СВР(support-vector regression) зависи само од подскупа података о обуци, јер функција грешке за изградњу модела игнорише све податке о обуци који су блиски предвиђању модела. Другу МПВ верзију познату као метода потпорних вектора најмањих квадрата (LS-SVM) су предложили Суикенс и Вандевалле.

Обука оригиналног СВР-а значи решавање

минимизирати ${\frac {1}{2}}\|w\|^{2}$

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

где је $x_{i}$ узорак за обуку са циљном вредношћу $y_{i}$ . Унутрашњи производ плус пресретање $\langle w,x_{i}\rangle +b$ је предвиђање за тај узорак, и $\varepsilon$ је слободан параметар који служи као праг: сва предвиђања морају бити унутар $\varepsilon$ распона истинитих предвиђања. "Лабаве" променљиве се обично додају у горе наведеном да би се омогућиле грешке и омогућила апроксимација у случају да је горњи проблем неизводљив.

Бајесова МПВ

Полсон и Скот су 2011. показали да МПВ прихвата Бајесову интерпретацију кроз технику повећања података . У овом приступу МПВ се посматра као графички модел (где су параметри повезани преко расподеле вероватноће). Овај детаљни преглед омогућава примену Бајесове технике на МПВ, као што је флексибилана функција моделирања, аутоматско хиперпараметерско подешавање, и предвидљиву несигурну квантификацију . „Недавно је Флоријан”. arXiv:search/stat?searchtype=author&query=Wenzel%2C+F  .  Венцел развио скалабилну верзију Бајесовое МПВ, омогућавајући примену Бајесовое МПВ на велике податке . Флориан Вензел је развио две различите верзије, шему варијационог закључивања (VI) за Бајесов модел потпорних вектора са језгром (SVM) и стохастичку верзију (SVI) за линеарни Бајесов МПВ.

Имплементација

Параметри хиперравни максималне маргине су изведени решавањем оптимизације. Постоји неколико специјализованих алгоритама за брзо решавање проблема квадратног програмирања (КП) који произилази из МПВ, углавном се ослањајући на хеуристику за разбијање проблема на мање делове којима је лакше управљати.

Други приступ је коришћење методе унутрашње тачке која користи итерације сличне Њутновој методи да би се пронашло решење Каруш–Кун–Такерових услова примарног и дуалног проблема. Уместо решавања низа рашчлањених проблема, овај приступ директно решава проблем у целини. Да би се избегло решавање линеарног система који укључује велику матрицу језгра, апроксимација ниског ранга матрици се често користи у трику језгра.

Уобичајени метод је и Платоов алгоритам секвенцијалне минималне оптимизације, који разлаже проблем на 2-димензионалне подпроблеме који се решавају аналитички, елиминишући потребу за нумеричким алгоритмом оптимизације и складиштењем матрице. Овај алгоритам је концептуално једноставан, лак за имплементацију, генерално бржи и има боља својства скалирања за тешке МПВ проблеме.

Посебан случај линераних МПВ може се ефикасније решити истом врстом алгоритама који се користе за оптимизацију његовог блиског рођака, логистичке регресије ; ова класа алгоритама укључује суб-градијенти спуст (нпр. PEGASOS) и координатни спуст (нпр. LIBLINEAR ). LIBLINEAR има импресивна времена обуке. Свака итерација конвергенције траје линеарно у времену потребном за читање тренинг података, а итерације такође имају својство Q-линеарне конвергенције, што алгоритам чини изузетно брзим.

Општа МПВ језгра се такође могу ефикасније решити коришћењем суб-градијентног спуста (нпр P-packSVM ), посебно када је паралелизација дозвољена.

МПВ језгра су доступна у многим комплетима алата за машинско учење, укључујући <a href="https://en.wikipedia.org/wiki/LIBSVM" rel="mw:ExtLink" title="LIBSVM" class="cx-link" data-linkid="815">LIBSVM</a>, MATLAB, SAS, СВМлигхт, 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 и друге.

Препоручује се претходна обрада података (стандардизација) да би се побољшала тачност класификације. Постоји неколико метода стандардизације, као што су мин-макс, нормализација децималним скалирањем, Z-score. Одузимање средње вредности и дељење варијансом сваке карактеристике се обично користи за М.

 

Додатна литература

• 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). Ур.: Abello, J.; Carmode, G. Discrete Methods in Epidemiology. DIMACS Series in Discrete Mathematics and Theoretical Computer Science. 70. стр. 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. стр. 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 изд.). Academic Press. ISBN 978-1-59749-272-0. 

Спољашње везе

• libsvm, <a href="https://en.wikipedia.org/wiki/LIBSVM" rel="mw:ExtLink" title="LIBSVM" class="cx-link" data-linkid="924">LIBSVM</a> је популарна библиотека за ученике MПВ-а
• liblinear је библиотека за велику линеарну класификацију укључујући неке МПВ
• [1]SVM light је колекција софтверских алата за учење и класификацију користећи МПВ
• [2] Архивирано на сајту Wayback Machine (5. мај 2013)SVMJS live demo је Графички кориснички интерфејс демо за JavaScript имплементацију МПВ-а