У машинском учењу, метода потпорних вектора је модел учења под надзором са припадајућим алгоритмима учења који анализирају податке за класификацију и регресиону анализу . Развио ју је Владимир Вапник са колегама у AT&T Bell Лабораторијама. Метода потпорних вектора је једна од најпоузданијих метода предвиђања, заснована на статистичким оквирима учења или VC теорији коју су предложили Вапник (1982, 1995) и Червонинкс (1974). Имајући у виду скуп примера за обуку, од којих је сваки означен као да припада једној од две категорије, МПВ алгоритам за обуку гради модел који додељује нове примере једној или другој категорији, чинећи га ненагађајућим бинарним линеарним класификатором . МПВ пресликава примере обуке на тачке у простору како би максимизирао ширину јаза између две категорије. Нови примери се затим мапирају у исти простор и предвиђају да припадају категорији на основу које стране јаза падају.
Поред извођења линеарне класификације, МПВ-ови могу ефикасно да изврше нелинеарну класификацију користећи оно што се назива трик језгра, имплицитно мапирајући своје улазе у просторе карактеристика високе димензије.
Када подаци нису означени, надгледано учење није могуће и потребан је приступ учењу без надзора, који покушава да пронађе природно груписање података у групе, а затим мапира нове податке у ове формиране групе. Алгоритам за груписање потпорних вектора , који су креирали Хава Сигелман и Владимир Вапник, примењује статистику вектора подршке, развијену у алгоритму мотоде поджаних вектора, за категоризацију неозначених података, и један је од најчешће коришћених алгоритама за груписање у инустријској апликацији.
Мотивација десно|мини| H1 не раздваја класе. H2 раздваја, али само са малом маргином. H3 их раздваја са максималном маргином. Класификација података је уобичајен задатак у машинском учењу . Претпоставимо да свака дата тачка припада једној од две класе, а циљ је да се одлучи у којој ће класи бити нова тачка података . У случају методе потпорних вектора, тачка података се посматра као -димензионални вектор (листа бројева), и желимо да знамо да ли можемо да одвојимо такве тачке са а -димензионалном хиперравни . Ово се зове линеарни класификатор . Постоји много хиперравни које могу класификовати податке. Разуман избор као најбоља хиперравна је она који постиже највеће раздвајање, или маргину, између две класе. Зато бирамо хиперраван тако да је растојање од ње до најближе тачке података на свакој страни максимизирано. Ако таква хиперраван постоји, позната је као хиперраван максималне маргине, а линеарни класификатор који он дефинише је познат као класификатор максималне маргине; или еквивалентно, перцептрон оптималне стабилности .
Дефиниција Модел потпорних векотра конструише хиперраван или скуп хиперравни у високо- или бесконачно-димензионалном простору, који се може користити за класификацију, регресију или друге задатке као што је откривање одступања. Добро раздвајање се постиже хиперравнином која има највећу удаљеност до најближе тачке података за обуку било које класе (функционална маргина), пошто генерално што је већа маргина, то је мања грешка генерализације класификатора. мини| Кернел машина Док се оригинални проблем може навести у коначнодимензионалном простору, често се дешава да скупови дискриминанти нису линеарно одвојиви у том простору. Из тог разлога, предложено је да се оригинални коначно-димензионални простор преслика у простор много веће димензије, што вероватно олакшава раздвајање у том простору. Да би рачунарско оптерећење било разумно, мапирања које користе МПВ шеме су дизајниране да обезбеде да се тачкасти производи парова вектора улазних података могу лако израчунати у смислу променљивих у оригиналном простору, дефинисањем у смислу функције језгра одабрано да одговара проблему. Хиперравне у вишедимензионалном простору су дефинисане као скуп тачака чији је тачкасти производ са вектором у том простору константан, при чему је такав скуп вектора ортогоналан (а тиме и минималан скуп вектора који дефинише хиперраван. Вектори који дефинишу хиперравне могу се изабрати да буду линеарне комбинације са параметрима слике вектора обележја који се јављају у бази података. Са овим избором хиперравнине, тачке у простору обележја који су пресликани у хиперравнину дефинисани су релацијом Имајте на уму да ако постаје мали као расте даље од , сваки члан у збиру мери степен блискости испитане тачке до одговарајуће тачке базе података . На овај начин, збир горњих језгара може да се користи за мерење релативне близине сваке испитне тачке тачкама података које потичу из једног или другог скупа који се дискриминише. Обратите пажњу на чињеницу да је скуп тачака пресликан у било коју хиперравнину може бити прилично замршен као резултат, омогућавајући много сложенију дискриминацију између скупова који уопште нису конвексни у оригиналном простору.
Апликације Методе потпорних векотра се могу користити за решавање различитих проблема из стварног света:
Методе потпорних векотра су корисне у категоризацији текста и хипертекста, јер њихова примена може значајно смањити потребу за означеним инстанцама обуке и у стандардним индуктивним и трансдуктивним поставкама. Неке методе за плитко семантичко рашчлањивање засноване су на методама потпорних векотра. Pradhan, Sameer S., et al. "Shallow semantic parsing using support vector machines." Proceedings of the Human Language Technology Conference of the North American Chapter of the Association for Computational Linguistics: HLT-NAACL 2004. 2004. Класификација слика се такође може извршити помоћу МПВ-а. Експериментални резултати показују да МПВ постижу знатно већу тачност претраге од традиционалних шема за прецизирање упита након само три до четири круга повратних информација о релевантности. Ово важи и за системе за сегментацију слика, укључујући и оне који користе модификовану верзију МПВ-а која користи привилеговани приступ како је предложио Вапник. Vapnik, Vladimir N.: Invited Speaker. IPMU Information Processing and Management 2014). . Granular Computing and Decision-Making. Springer International Publishing, 2015. 285–318. Класификација сателитских података као што су SAR подаци коришћењем надгледаног МПВ. Руком писани знакови се могу препознати помоћу МПВ. Алгоритам МПВ има широку примену у биологијо и другим наукама. Коришћени су за класификацију протеина са до 90% исправно класификованих једињења. Пермутациони тестови засновани на МПВ тежинама су предложени као механизам за интерпретацију МПВ модела. Gaonkar, Bilwaj; Davatzikos, Christos; . Cuingnet, Rémi; Rosso, Charlotte; Chupin, Marie; Lehéricy, Stéphane; Dormont, Didier; Benali, Habib; Samson, Yves; and Colliot, Olivier; , . Методе потпорних векотра су такође коришћене за тумачење МПВ модела у прошлости. Statnikov, Alexander; Hardin, Douglas; & Aliferis, Constantin; (2006); "Using SVM weight-based methods to identify causally relevant and non-causally relevant variables", Sign, 1, 4. Постхок интерпретација модела потпорних вектора у циљу идентификације карактеристика које модел користи за предвиђање је релативно нова област истраживања од посебног значаја у биолошким наукама.
Историја Оригинални МПВ алгоритам су измислили Владимир Н. Вапник и Алексеј Ја. Червонинкс 1963. године. Године 1992. Бернхард Босер, Изабела Гујон и Владимир Вапник су предложили начин да се створе нелинеарни класификатори применом трика језгра да би се добиле максималне маргине хиперравни. Инкарнацију „меке маргине“, као што се уобичајено користе софтверски пакети, предложили су Корина Кортес и Вапник 1993. године и објављени 1995. године
Линеарна МПВ мини|300x300пиксел| Хиперраван максималне маргине и маргине за МПВ обучен са узорцима из две класе. Узорци на маргини називају се вектори подршке. Имамо скуп података за обуку од тачке форме
где су или 1 или −1, од којих сваки указује на класу до које је тачка припада. Сваки је -димензионални реални вектор. Желимо да пронађемо "хиперраван максималне маргине" која дели групу тачака за које из групе бодова за које , који је дефинисан тако да растојање између хиперравни и најближе тачке из било које групе буде максимизиран.
Било која хиперраван се може написати као скуп тачака уколико испуњава:
где је (не нужно нормализован) вектор нормале на хиперраван. Ово је слично Хесеновом нормалном облику, осим тога није нужно јединични вектор. Параметар одређује помак хиперравни од почетка дуж вектора нормале .
Тврда маргина Ако су тренинг подаци линеарно раздвојиви, можемо изабрати две паралелне хиперравне које раздвајају две класе података, тако да је растојање између њих што је могуће веће. Подручје ограничено са ове две хиперравне назива се „маргина“, а хиперраван максималне маргине је хиперраван која се налази на пола пута између њих. Са нормализованим или стандардизованим скупом података, ове хиперравне се могу описати слдећим једначинама:
(све на или изнад ове границе припрада једној класи, са ознаком 1)
и
(све на или испод ове границе припада другој класи, са ознаком −1).
Геометријски, растојање између ове две хиперравне је , тако да би максимизовали растојање између равни које желимо да минимизирамо . Растојање се израчунава коришћењем једначине удаљености тачке од равни . Такође морамо да спречимо да тачке података падну на маргину, додајемо следеће ограничење: за сваку било
, ако је ,
или
, ако је .
Ови услови наводе да свака тачка података мора лежати на исправној страни маргине.
Ово се може написати и као:
Можемо да саставимо све ово и добијемо проблем оптимизације:
„Минимизуј на за ."
и који решавају овај проблем одређују наш класификатор, где је функција знака .
Важна последица овог геометријског описа је да је хиперраван максималне маргине потпуно одређена векотром који му је најближи. Ови називају се вектори подршке .
Мека маргина За проширење МПВ на случајеве у којима подаци нису линеарно одвојиви, функција губитка зглоба је од помоћи
Напоменути да је i-ти циљ (то јест, у овом случају је 1 или −1), и је i-ти излаз.
Ова функција је нула ако је услов из (1) задовољен, другим речима, ако лежи на исправној страни маргине. За податке на погрешној страни маргине, вредност функције је пропорционална удаљености од тачке од маргине.
Циљ оптимизације је да се минимизује
где је параметар одређује компромис између повећања величине маргине и обезбеђивања да леже на исправној страни маргине. Дакле, за довољно мале вредности од , понашаће се слично МПВ-а са тврдом маргином, ако се улазни подаци линеарно класификују, али ће и даље научити да ли је правило класификације одрживо или не. (Овај параметар се такође назива Ц, нпр. у -{LIBSVM}- .)
Нелинеарна класификација мини| Кернел машина Оригинални алгоритам максималне маргине хиперавни који је предложио Вапник 1963. године конструисао је линеарни класификатор . Међутим, 1992. године, Бернхард Босер, Изабел Гујон и Владимир Вапник су предложили начин за креирање нелинеарних класификатора применом трика језгра (првобитно предложен од Аизермана ) за максималне маргине хиперравни. Добијени алгоритам је формално сличан, осим што је сваки тачкасти производ замењен нелинеарном функцијом језгра. Ово омогућава алгоритму да уклопи хиперраван максималне маргине у трансформисани простор обележја. Трансформација може бити нелинеарна, а трансформисани простор вишедимензионалан; иако је класификатор хиперравна у трансформисаном простору обележја, он може бити нелинеаран у оригиналном улазном простору.
Важно је напоменути да рад у вишедимензионалном простору карактеристика повећава грешку генерализације методе потпорних вектора, уколико има довољно тренинг узорака алгоритам ће и даље ради добро.
Нека уобичајена језгра укључују:
Полином (хомоген) : . Полином (нехомоген): . Гаусова радијална базна функција : за . Понекад се параметризују коришћењем . Хиперболички тангент : за неке (не за све) и .