Stroj na podporu vektorů - Support-vector machine

V strojového učení , podpora-vektorové stroje ( SVMs , také podpora-vektorové sítě ), tak učení s modely s spojených učení algoritmy , které analyzují data pro klasifikaci a regresní analýzy . Vyvinutý v AT & T Bell Laboratories podle Vladimír Vapnik s kolegy (Böser et al., 1992, Guyon et al., 1993, Vapnik et al., 1997) SVMs jsou jedním z nejvíce robustních metod predikce, se na základě statistických rámců učení nebo VC teorie navržená Vapnikem (1982, 1995) a Chervonenkisem (1974). Vzhledem k sadě tréninkových příkladů, z nichž každý je označen jako patřící do jedné ze dvou kategorií, tréninkový algoritmus SVM vytvoří model, který přiřadí nové příklady do jedné nebo druhé kategorie, což z něj činí nejpravděpodobnější binární lineární klasifikátor (ačkoli metody jako Platt škálování existují pro použití SVM v nastavení pravděpodobnostní klasifikace). SVM mapuje příklady tréninku na body v prostoru tak, aby byla maximalizována šířka mezery mezi těmito dvěma kategoriemi. Nové příklady jsou pak mapovány do stejného prostoru a předpovídají, že patří do kategorie podle toho, na kterou stranu mezery spadají.

Kromě provádění lineární klasifikace mohou SVM efektivně provádět nelineární klasifikaci pomocí toho, čemu se říká trik jádra , implicitně mapovat jejich vstupy do prostorů vysoce dimenzionálních funkcí.

Když jsou data neoznačená, není možné učení pod dohledem a je vyžadován přístup bez dozoru , který se pokouší najít přirozené seskupování dat do skupin a poté mapovat nová data do těchto vytvořených skupin. Clustering podpora-vector algoritmus, vytvořený Hava Siegelmann a Vladimir Vapnik , platí statistiku podpůrných vektorů, vyvinutých v nosném vektoru stroje algoritmus, kategorizovat neznačených dat, a je jedním z nejrozšířenějších clustering algoritmů v průmyslových aplikacích.

Motivace

H 1 neodděluje třídy. H 2 ano, ale pouze s malým rozpětím. H 3 je odděluje s maximálním okrajem.

Klasifikace dat je běžným úkolem ve strojovém učení . Předpokládejme, že některé dané datové body patří do jedné ze dvou tříd a cílem je rozhodnout, ve které třídě bude nový datový bod . V případě strojů s podpůrnými vektory je datový bod považován za a -rozměrný vektor (a seznam čísel) a chceme vědět, zda můžeme takové body oddělit pomocí -dimenzionální hyperplane . Toto se nazývá lineární klasifikátor . Existuje mnoho hyperplanes, které by mohly klasifikovat data. Jedna rozumná volba jako nejlepší hyperplane je ta, která představuje největší oddělení nebo rozpětí mezi těmito dvěma třídami. Vybereme tedy hyperplane tak, aby vzdálenost od ní k nejbližšímu datovému bodu na každé straně byla maximalizována. Pokud taková hyperplane existuje, je známá jako hyperplane s maximálním rozpětím a lineární klasifikátor, který definuje, je znám jako klasifikátor s maximální marží ; nebo ekvivalentně perceptron optimální stability .

Definice

Formálněji stroj s podpůrnými vektory konstruuje hyperplane nebo sadu hyperplanes ve vysoce nebo nekonečně dimenzionálním prostoru, které lze použít ke klasifikaci , regresi nebo jiným úkolům, jako je detekce odlehlých hodnot. Intuitivně je dobrého oddělení dosaženo hyperplanou, která má největší vzdálenost k nejbližšímu bodu tréninkových dat jakékoli třídy (takzvané funkční rozpětí), protože obecně platí, že čím větší rozpětí, tím nižší generalizační chyba klasifikátoru.

Stroj jádra

Zatímco původní problém může být uveden v prostoru s konečnou dimenzí, často se stává, že sady pro rozlišení nejsou v tomto prostoru lineárně oddělitelné . Z tohoto důvodu bylo navrženo, aby byl původní prostor konečných rozměrů mapován do prostoru mnohem vyšší dimenze, což pravděpodobně v tomto prostoru usnadnilo oddělení. Aby byla výpočetní zátěž přiměřená, jsou mapování používaná schématy SVM navržena tak, aby zajistily, že bodové produkty dvojic vektorů vstupních dat lze snadno vypočítat z hlediska proměnných v původním prostoru, a to tak, že je definujeme pomocí vybrané funkce jádra. aby vyhovoval problému. Hyperplany ve vyšším dimenzionálním prostoru jsou definovány jako množina bodů, jejichž součin bodů s vektorem v tomto prostoru je konstantní, kde taková sada vektorů je ortogonální (a tedy minimální) sada vektorů, která definuje hyperplane. Vektory definující hyperplany mohou být vybrány jako lineární kombinace s parametry obrazů charakteristických vektorů, které se vyskytují v databázi. Při této volbě hyperplany jsou body v prostoru funkcí, které jsou mapovány do hyperplany, definovány vztahem Všimněte si, že pokud se stane malým, jak se od něj dále vzdaluje , každý člen v součtu měří stupeň blízkosti testovacího bodu k odpovídající bod databáze . Tímto způsobem lze součet výše uvedených jader použít k měření relativní blízkosti každého testovacího bodu k datovým bodům pocházejícím z jedné nebo druhé ze sad, které mají být diskriminovány. Všimněte si skutečnosti, že množina bodů namapovaných do jakékoli hyperplany může být ve výsledku dost spletitá, což umožňuje mnohem komplexnější rozlišení mezi množinami, které v původním prostoru nejsou vůbec konvexní.

Aplikace

SVM lze použít k řešení různých problémů reálného světa:

  • SVM jsou užitečné při kategorizaci textu a hypertextu , protože jejich aplikace může výrazně snížit potřebu označených tréninkových instancí ve standardním induktivním i transduktivním nastavení. Některé metody pro mělkou sémantickou analýzu jsou založeny na podpůrných vektorových počítačích.
  • Klasifikaci obrázků lze provádět také pomocí SVM. Experimentální výsledky ukazují, že SVM dosahují podstatně vyšší přesnosti vyhledávání než tradiční schémata zpřesňování dotazů po pouhých třech až čtyřech kolech relevantní zpětné vazby. To platí také pro systémy segmentace obrazu , včetně systémů využívajících upravenou verzi SVM, která využívá privilegovaný přístup, jak navrhuje Vapnik.
  • Klasifikace satelitních dat, jako jsou data SAR, pomocí kontrolovaného SVM.
  • Ručně psané znaky lze rozpoznat pomocí SVM.
  • Algoritmus SVM byl široce používán v biologických a jiných vědách. Byly použity ke klasifikaci proteinů, přičemž až 90% sloučenin bylo klasifikováno správně. Permutační testy založené na hmotnostech SVM byly navrženy jako mechanismus pro interpretaci modelů SVM. V minulosti byly k interpretaci modelů SVM také použity strojní váhy podpůrných vektorů. Posthoc interpretace modelů strojových podpůrných vektorů za účelem identifikace vlastností použitých modelem k predikci je relativně nová oblast výzkumu se zvláštním významem v biologických vědách.

Dějiny

Původní algoritmus SVM vynalezli Vladimir N.Vapnik a Alexey Ya. Chervonenkis v roce 1963. V roce 1992 Bernhard Boser, Isabelle Guyon a Vladimir Vapnik navrhli způsob, jak vytvořit nelineární klasifikátory použitím triku jádra na hyperplany s maximálním okrajem. Vtělení „měkkého okraje“, jak se běžně používají softwarové balíky, navrhly Corinna Cortes a Vapnik v roce 1993 a publikovaly v roce 1995.

Lineární SVM

Hyperplane s maximálním rozpětím a okraje pro SVM trénované se vzorky ze dvou tříd. Vzorky na okraji se nazývají podpůrné vektory.

Dostáváme tréninkový datový soubor bodů formuláře

kde jsou buď 1 nebo −1, přičemž každá označuje třídu, do které daný bod patří. Každý z nich je -dimenzionální skutečný vektor. Chceme najít „hyperplanu s maximálním okrajem“, která rozděluje skupinu bodů, pro které, ze skupiny bodů, pro které je definována tak, aby vzdálenost mezi hyperplanou a nejbližším bodem z každé skupiny byla maximalizována.

Libovolnou nadrovinu lze zapsat jako množinu bodů, které uspokojí

kde je (ne nutně normalizovaný) normální vektor hyperplany. Je to podobné jako v Hesensku normální forma , kromě toho, že to nemusí být jednotkový vektor. Parametr určuje posun hyperplany od počátku podél normálního vektoru .

Hard-margin

Pokud jsou tréninková data lineárně oddělitelná , můžeme vybrat dvě paralelní hyperplany, které oddělují dvě třídy dat, takže vzdálenost mezi nimi je co největší. Oblast ohraničená těmito dvěma hyperplanesami se nazývá „okraj“ a hyperplane s maximálním okrajem je hyperplane, která leží na půli cesty mezi nimi. S normalizovanou nebo standardizovanou datovou sadou lze tyto hyperplochy popsat pomocí rovnic

(cokoli na nebo nad touto hranicí je jedné třídy, s popiskem 1)

a

(cokoli na nebo pod touto hranicí je jiné třídy, se štítkem −1).

Geometricky je vzdálenost mezi těmito dvěma hyperplany taková, abychom maximalizovali vzdálenost mezi rovinami, které chceme minimalizovat . Vzdálenost se vypočítá pomocí vzdálenosti od bodu k rovině roviny . Musíme také zabránit propadu datových bodů na okraj, přidáme následující omezení: pro každé z nich

, pokud ,

nebo

, pokud .

Tato omezení uvádějí, že každý datový bod musí ležet na správné straně okraje.

Toto lze přepsat jako

Můžeme to dát dohromady, abychom získali problém s optimalizací:

„Minimalizovat s výhradou pro .“

A že vyřešit tento problém určit naše třídiče, kde je funkce znamení .

Důležitým důsledkem tohoto geometrického popisu je, že hyperplana s maximálním okrajem je zcela určena těmi, které leží nejblíže k ní. Nazývají se podpůrné vektory .

Soft-margin

Chcete -li rozšířit SVM na případy, ve kterých data nelze lineárně oddělit, je užitečná funkce ztráty závěsu

Všimněte si, že je to i -tý cíl (tj. V tomto případě 1 nebo -1), a je i -tý výstup.

Tato funkce je nulová, pokud je splněno omezení v (1), jinými slovy, pokud leží na správné straně okraje. U dat na špatné straně okraje je hodnota funkce úměrná vzdálenosti od okraje.

Cílem optimalizace je pak minimalizace

kde parametr určuje kompromis mezi zvýšením velikosti marže a zajištěním, že leží na správné straně marže. Pro dostatečně velké hodnoty se tedy bude chovat podobně jako SVM s pevným okrajem, pokud jsou vstupní data lineárně klasifikovatelná, ale přesto se naučí, zda je klasifikační pravidlo životaschopné nebo ne. (Tento parametr se také nazývá C, např. V LIBSVM .)

Nelineární klasifikace

Stroj jádra

Původní algoritmus hyperplane s maximálním rozpětím navržený Vapnikem v roce 1963 sestrojil lineární klasifikátor . V roce 1992 však Bernhard Boser , Isabelle Guyon a Vladimir Vapnik navrhli způsob, jak vytvořit nelineární klasifikátory použitím triku jádra (původně navrhovaného Aizermanem a kol.) Na hyperplany s maximálním rozpětím. Výsledný algoritmus je formálně podobný, kromě toho, že každý bodový produkt je nahrazen nelineární funkcí jádra . To umožňuje algoritmu přizpůsobit hyperplanu s maximálním okrajem v transformovaném prostoru funkcí . Transformace může být nelineární a transformovaný prostor vysoce dimenzionální; přestože je klasifikátor v rovině transformovaných prvků hyperplane, v původním vstupním prostoru může být nelineární.

Je pozoruhodné, že práce v prostoru s vyšší dimenzí funkcí zvyšuje chybu generalizace strojů s podpůrnými vektory, přestože vzhledem k dostatku vzorků algoritmus stále funguje dobře.

Mezi některá běžná jádra patří:

  • Polynom (homogenní) : .
  • Polynom (nehomogenní) .
  • Gaussova radiální základová funkce : pro . Někdy parametrizováno pomocí .
  • Hyperbolický tangens : pro některé (ne pro každého) a .

Jádro souvisí s transformací podle rovnice . Hodnota w je také v transformovaném prostoru, s . Tečkové produkty s w pro klasifikaci lze opět vypočítat pomocí triku jádra, tzn .

Výpočet klasifikátoru SVM

Výpočet klasifikátoru SVM (soft-margin) odpovídá minimalizaci výrazu ve formuláři

Zaměřujeme se na klasifikátor s měkkým okrajem, protože, jak bylo uvedeno výše, výběrem dostatečně malé hodnoty pro klasifikátor s pevným okrajem pro lineárně klasifikovatelná vstupní data. Níže je popsán klasický přístup, který zahrnuje redukci (2) na problém kvadratického programování . Poté budou probrány novější přístupy, jako je sestup pod gradientem a sestup souřadnic.

Původní

Minimalizaci (2) lze přepsat jako omezený optimalizační problém s funkcí diferencovatelného cíle následujícím způsobem.

U každého zavedeme proměnnou . Všimněte si, že je to nejmenší vyhovující číslo, které není záporné

Můžeme tedy přepsat problém optimalizace následujícím způsobem

Tomu se říká prvotní problém.

Dvojí

Řešením Lagrangeova duálu výše uvedeného problému získáme zjednodušený problém

Tomu se říká duální problém. Protože problém duální maximalizace je kvadratickou funkcí subjektu podle lineárních omezení, je efektivně řešitelný kvadratickými programovacími algoritmy.

Zde jsou proměnné definovány tak, že

.

Navíc přesně tehdy, když leží na správné straně okraje a kdy leží na hranici okraje. Z toho vyplývá, že může být zapsán jako lineární kombinace podpůrných vektorů.

Offset,, lze obnovit nalezením na hranici marže a řešením

(Všimněte si, že od .)

Trik jádra

Tréninkový příklad SVM s jádrem daným φ (( a , b )) = ( a , b , a 2 + b 2 )

Předpokládejme nyní, že bychom se chtěli naučit nelineární klasifikační pravidlo, které odpovídá lineárnímu klasifikačnímu pravidlu pro transformované datové body Navíc máme k dispozici funkci jádra, která splňuje .

Víme, že klasifikační vektor v transformovaném prostoru vyhovuje

kde jsou získány řešením problému s optimalizací

Koeficienty lze vyřešit pomocí kvadratického programování, jako dříve. Opět můžeme najít nějaký takový index , který leží na hranici okraje v transformovaném prostoru, a poté vyřešit

Konečně,

Moderní metody

Nedávné algoritmy pro nalezení klasifikátoru SVM zahrnují sestup pod gradientem a sestup souřadnic. Obě techniky se ukázaly jako významné výhody oproti tradičnímu přístupu při práci s velkými, řídkými datovými soubory-metody sub-gradientu jsou zvláště účinné, když existuje mnoho tréninkových příkladů, a koordinují sestup, když je dimenze prostoru funkcí vysoká.

Sub-gradient sestup

Algoritmy klesání pod gradientem pro SVM pracují přímo s výrazem

Všimněte si, že je funkce konvexní z a . Lze tak upravit tradiční metody gradientového klesání (neboli SGD ), kde místo kroku ve směru gradientu funkce se udělá krok ve směru vektoru vybraného z dílčího gradientu funkce . Tento přístup má tu výhodu, že u určitých implementací se počet iterací nemění s počtem datových bodů.

Souřadnicový sestup

Algoritmy sestupu souřadnic pro SVM pracují z duálního problému

U každého se iterativně koeficient upraví ve směru . Potom se výsledný vektor koeficientů promítne na nejbližší vektor koeficientů, který splňuje daná omezení. (Obvykle se používají euklidovské vzdálenosti.) Proces se poté opakuje, dokud se nezíská téměř optimální vektor koeficientů. Výsledný algoritmus je v praxi extrémně rychlý, i když bylo prokázáno jen málo záruk výkonu.

Empirická minimalizace rizik

Výše popsaný vektorový stroj na podporu měkkých marží je příkladem algoritmu empirické minimalizace rizik (ERM) pro ztrátu závěsu . Viděno tímto způsobem, podpůrné vektorové stroje patří do přirozené třídy algoritmů pro statistické odvozování a mnoho z jeho jedinečných vlastností je dáno chováním ztráty závěsu. Tato perspektiva může poskytnout další pohled na to, jak a proč SVM fungují, a umožnit nám lépe analyzovat jejich statistické vlastnosti.

Minimalizace rizik

V učení s učitelem, jeden dostane sadu příkladů tréninkových etiketami a přání předvídat daný . K tomu jeden, tvoří hypotéz , tak, že je „dobrý“ aproximace . A „dobrý“ přiblížení je obvykle definována pomocí jednoho ztrátové funkce , , který charakterizuje jak špatná je predikce . Poté bychom chtěli zvolit hypotézu, která minimalizuje očekávané riziko :

Ve většině případů neznáme společné rozdělení přímých. V těchto případech je běžnou strategií zvolit hypotézu, která minimalizuje empirické riziko:

Za určitých předpokladů o posloupnosti náhodných proměnných (například že jsou generovány konečným Markovovým procesem), je -li uvažovaný soubor hypotéz dostatečně malý, bude se minimalizátor empirického rizika velmi blížit minimalizátoru očekávaného rizika. jak roste velký. Tento přístup se nazývá empirická minimalizace rizik nebo ERM.

Regularizace a stabilita

Aby měl problém minimalizace přesně definované řešení, musíme na uvažovaný soubor hypotéz klást omezení . Pokud je to normovaný prostor (jako je tomu v případě SVM), zvláště efektivní technikou je zvážit pouze ty hypotézy, pro které . To je ekvivalentní uložení sankce za regularizaci a vyřešení nového problému s optimalizací

Tento přístup se nazývá Tichonovova regularizace .

Obecněji může být určitým měřítkem složitosti hypotézy , takže jsou preferovány jednodušší hypotézy.

SVM a ztráta závěsu

Připomeňme, že klasifikátor SVM (soft-margin) je zvolen tak, aby minimalizoval následující výraz:

Ve světle výše uvedené diskuse vidíme, že technika SVM je ekvivalentní empirické minimalizaci rizika s Tichonovovou regularizací, kde v tomto případě je ztrátová funkce závěsová ztráta

Z tohoto pohledu je SVM úzce spjat s dalšími základními klasifikačními algoritmy, jako jsou regulované nejmenší čtverce a logistická regrese . Rozdíl mezi třemi spočívá ve volbě ztrátové funkce: legalizovány nejmenších čtverců činí empirické minimalizaci rizika s čtvercovým-ztráta , ; logistická regrese využívá ztrátu protokolu ,

Cílové funkce

Rozdíl mezi ztrátou závěsu a těmito dalšími ztrátovými funkcemi je nejlépe vyjádřit z hlediska cílových funkcí - funkce, která minimalizuje očekávané riziko pro daný pár náhodných proměnných .

Zejména označme podmíněné případem, že . V nastavení klasifikace máme:

Optimálním klasifikátorem je tedy:

Pro druhou mocninu je cílová funkce funkcí podmíněného očekávání ; Pro logistické ztráty, je to funkce logit, . Zatímco obě tyto cílové funkce poskytují správný klasifikátor, as , poskytují nám více informací, než potřebujeme. Ve skutečnosti nám poskytují dostatek informací k úplnému popisu distribuce .

Na druhou stranu je možné zkontrolovat, zda je cílová funkce pro ztrátu závěsu přesně . V dostatečně bohatém prostoru hypotéz - nebo ekvivalentně pro vhodně zvolené jádro - bude klasifikátor SVM konvergovat k nejjednodušší funkci (pokud jde o ), která správně klasifikuje data. To rozšiřuje geometrickou interpretaci SVM-u lineární klasifikace je empirické riziko minimalizováno jakoukoli funkcí, jejíž okraje leží mezi nosnými vektory, a nejjednodušší z nich je klasifikátor max. Marže.

Vlastnosti

SVM patří do rodiny generalizovaných lineárních klasifikátorů a lze je interpretovat jako rozšíření perceptronu . Lze je také považovat za zvláštní případ Tichonovovy regularizace . Zvláštní vlastností je, že současně minimalizují empirickou klasifikační chybu a maximalizují geometrický okraj ; proto jsou také známí jako klasifikátory maximální marže .

Srovnání SVM s jinými klasifikátory provedli Meyer, Leisch a Hornik.

Výběr parametrů

Účinnost SVM závisí na výběru jádra, parametrech jádra a parametru soft margin . Běžnou volbou je gaussovské jádro, které má jediný parametr . Nejlepší kombinace a je často vybrána vyhledáváním v mřížce s exponenciálně rostoucími sekvencemi a například ; . Obvykle je každá kombinace voleb parametrů zkontrolována pomocí křížové validace a jsou vybrány parametry s nejlepší přesností křížové validace. Alternativně lze k výběru použít nedávnou práci v Bayesovské optimalizaci a často vyžaduje vyhodnocení mnohem méně kombinací parametrů než vyhledávání v mřížce. Výsledný model, který se používá pro testování a pro klasifikaci nových dat, se poté trénuje na celé tréninkové sadě pomocí vybraných parametrů.

Problémy

Potenciální nevýhody SVM zahrnují následující aspekty:

  • Vyžaduje úplné označení vstupních dat
  • Nekalibrované pravděpodobnosti členství ve třídě - SVM vychází z Vapnikovy teorie, která se vyhýbá odhadování pravděpodobností na konečných datech
  • SVM je přímo použitelný pouze pro úkoly se dvěma třídami. Proto musí být použity algoritmy, které redukují úlohu více tříd na několik binárních problémů; viz sekce SVM s více třídami .
  • Parametry řešeného modelu jsou obtížně interpretovatelné.

Rozšíření

Klastrování vektorů podpory (SVC)

SVC je podobná metoda, která také staví na funkcích jádra, ale je vhodná pro učení bez dozoru. To je považováno za základní metodu v datové vědě .

Více tříd SVM

Multiclass SVM si klade za cíl přiřadit popisky k instancím pomocí strojů podpůrných vektorů, kde jsou popisky čerpány z konečné sady několika prvků.

Dominantním přístupem k tomu je redukovat problém s více třídami na více problémů s binární klasifikací . Mezi běžné metody takové redukce patří:

  • Vytváření binárních klasifikátorů, které rozlišují mezi jedním ze štítků a zbytkem ( jeden proti všem ) nebo mezi každou dvojicí tříd ( jeden proti jednomu ). Klasifikace nových instancí pro případ jeden proti všem se provádí strategií vítěz bere vše, kde třídu přiřazuje klasifikátor s funkcí nejvyššího výkonu (je důležité, aby výstupní funkce byly kalibrovány tak, aby poskytovaly srovnatelné skóre ). Pro přístup jeden proti jednomu se klasifikace provádí pomocí strategie hlasování max-wins, ve které každý klasifikátor přiřadí instanci jedné ze dvou tříd, poté se hlas pro přiřazenou třídu zvýší o jeden hlas a nakonec třída s největším počtem hlasů určuje klasifikaci instance.
  • Řízený acyklický graf SVM (DAGSVM)
  • Výstupní kódy opravující chyby

Crammer a Singer navrhli metodu SVM s více třídami, která vrhá problém klasifikace více tříd do jednoho problému optimalizace, místo aby jej rozložila na více problémů s binární klasifikací. Viz také Lee, Lin a Wahba a Van den Burg a Groenen.

Stroje s vektorovou transdukční podporou

Stroje s transduktivní podporou vektorů rozšiřují SVM v tom, že by také mohly zpracovávat částečně označená data v semi-supervizovaném učení podle principů transdukce . Zde kromě vzdělávací sady dostane žák také sadu

testovacích příkladů, které mají být klasifikovány. Formálně je transduktivní stroj s vektorem podpory definován následujícím problémem primární optimalizace:

Minimalizovat (v )

podléhá (pro jakékoli a jakékoli )

a

Stroje s vektorovou transdukční podporou představil Vladimir N.Vapnik v roce 1998.

Strukturovaný SVM

SVM byly zobecněny na strukturované SVM , kde je prostor štítků strukturovaný a může mít neomezenou velikost.

Regrese

Regrese vektoru podpory (predikce) s různými prahy ε . Jak se ε zvyšuje, předpověď se stává méně citlivou na chyby.

Verzi SVM pro regresi navrhli v roce 1996 Vladimir N.Vapnik , Harris Drucker, Christopher JC Burges, Linda Kaufman a Alexander J. Smola. Tato metoda se nazývá regrese podpory vektorů (SVR). Model vytvořený klasifikací podpůrných vektorů (jak je popsáno výše) závisí pouze na podmnožině tréninkových dat, protože nákladová funkce pro sestavení modelu se nestará o tréninkové body, které leží za okrajem. Analogicky model vytvořený SVR závisí pouze na podmnožině tréninkových dat, protože nákladová funkce pro stavbu modelu ignoruje všechna tréninková data blízká predikci modelu. Suykens a Vandewalle navrhli jinou verzi SVM známou jako podpůrný vektorový stroj nejmenších čtverců (LS-SVM).

Trénovat původní SVR znamená řešit

minimalizovat
podléhá

kde je tréninkový vzorek s cílovou hodnotou . Intercept product intercept je předpověď pro tento vzorek a je volným parametrem, který slouží jako prahová hodnota: všechny předpovědi musí být v rozsahu skutečných předpovědí. Proměnné prověšení se obvykle přidávají do výše uvedeného, ​​aby se umožnily chyby a umožnila aproximace v případě, že je výše uvedený problém neproveditelný.

Bayesian SVM

V roce 2011 Polson a Scott ukázali, že SVM připouští Bayesovskou interpretaci technikou augmentace dat . V tomto přístupu je SVM vnímán jako grafický model (kde jsou parametry spojeny prostřednictvím rozdělení pravděpodobnosti). Tento rozšířený pohled umožňuje aplikaci bayesovských technik na SVM, jako je flexibilní modelování funkcí, automatické ladění hyperparametrů a kvantifikace prediktivní nejistoty . Florian Wenzel nedávno vyvinul škálovatelnou verzi Bayesian SVM , která umožňuje aplikaci Bayesian SVM na velká data . Florian Wenzel vyvinul dvě různé verze, schéma variačního inference (VI) pro Bayesian kernel support vector machine (SVM) a stochastickou verzi (SVI) pro lineární Bayesian SVM.

Implementace

Parametry hyperplany s maximálním rozpětím jsou odvozeny řešením optimalizace. Existuje několik specializovaných algoritmů pro rychlé řešení problému s kvadratickým programováním (QP), které vyplývá ze SVM, přičemž při rozdělování problému na menší, lépe zvládnutelné bloky se většinou spoléhají na heuristiku.

Dalším přístupem je použít metodu vnitřního bodu, která používá Newtonovy iterace k nalezení řešení Karush -Kuhn -Tuckerových podmínek primárních a duálních problémů. Tento přístup namísto řešení sekvence rozdělených problémů tento problém přímo zcela řeší. Abychom se vyhnuli řešení lineárního systému zahrnujícího velkou matici jádra, v triku jádra se často používá aproximace matice na nízké úrovni.

Další běžnou metodou je Plattův algoritmus sekvenční minimální optimalizace (SMO), který rozděluje problém na 2-dimenzionální dílčí problémy, které jsou řešeny analyticky, což eliminuje potřebu algoritmu numerické optimalizace a maticového úložiště. Tento algoritmus je koncepčně jednoduchý, snadno implementovatelný, obecně rychlejší a má lepší vlastnosti škálování pro obtížné problémy SVM.

Zvláštní případ lineárních strojů s podporou vektorů lze efektivněji vyřešit stejným druhem algoritmů, které se používají k optimalizaci jeho blízkého bratrance, logistické regrese ; tato třída algoritmů zahrnuje klesání pod gradientem (např. PEGASOS) a sestup souřadnic (např. LIBLINEAR). LIBLINEAR má několik atraktivních vlastností během tréninku. Každá konvergenční iterace potřebuje čas lineární v čase potřebném ke čtení dat vlaku a iterace mají také vlastnost Q-lineární konvergence , díky čemuž je algoritmus extrémně rychlý.

Obecné SVM jádra lze také řešit efektivněji pomocí sestupu pod gradientem (např. P-packSVM), zvláště když je povolena paralelizace .

Jádra SVM jsou k dispozici v mnoha sadách nástrojů pro strojové učení, včetně LIBSVM , MATLAB , SAS , SVMlight, kernlab , scikit-learn , Shogun , Weka , Shark , JKernelMachines , OpenCV a dalších.

Pro zvýšení přesnosti klasifikace se důrazně doporučuje předběžné zpracování dat (standardizace). Existuje několik metod standardizace, jako je min-max, normalizace podle desetinného měřítka, Z-skóre. Pro SVM se obvykle používá odčítání průměru a dělení rozptylem každé funkce.

Viz také

Reference

Další čtení

externí odkazy