Tato odpověď vysvětluje následující:

1. Proč je vždy možné dokonalé oddělení s odlišnými body a Gaussovým jádrem (dostatečně malé šířky pásma)
2. Jak může být toto oddělení interpretováno jako lineární, ale pouze v abstraktním prostoru funkcí odlišném od prostoru, kde žijí data
3. Jak je „nalezeno“ mapování z datového prostoru do prostoru funkcí. Spoiler: není nalezen SVM, je implicitně definován zvoleným jádrem.
4. Proč je prostor funkcí nekonečně rozměrný.

1. Dosažení dokonalého oddělení

Dokonalé oddělení je u gaussovského jádra vždy možné (za předpokladu, že žádné dva body z různých tříd nejsou vždy úplně stejné) kvůli vlastnostem jádra, které vedou k libovolně flexibilní hranici rozhodování. Pro dostatečně malou šířku pásma jádra bude hranice rozhodování vypadat, jako byste právě nakreslili malé kruhy kolem bodů, kdykoli jsou potřeba k oddělení pozitivních a negativních příkladů:

(Uznání: Online kurz strojového učení Andrewa Nga).

Proč k tomu tedy dochází z matematické perspektivy?

Zvažte standardní nastavení: máte gaussovské jádro $ K (\ mathbf {x}, \ mathbf {z}) = \ exp (- || \ mathbf {x} - \ mathbf {z} || ^ 2 / \ sigma ^ 2) $ a tréninková data $ (\ mathbf {x} ^ {(1)}, y ^ {(1)}), (\ mathbf {x} ^ {(2)}, y ^ {(2)}), \ ldots, (\ mathbf {x} ^ {(n)}, y ^ {(n)}) $ kde hodnoty $ y ^ {(i)} $ jsou $ \ pm 1 $. Chceme se naučit funkci klasifikátoru

$$ \ hat {y} (\ mathbf {x}) = \ sum_i w_i y ^ {(i)} K (\ mathbf {x} ^ {(i )}, \ mathbf {x}) $$

Jak teď budeme přiřadit váhy $ w_i $? Potřebujeme nekonečné dimenzionální prostory a kvadratický programovací algoritmus? Ne, protože chci jen ukázat, že umím dokonale oddělit body. Takže $ \ sigma $ miliardkrát menší než nejmenší oddělování $ || \ mathbf {x} ^ {(i)} - \ mathbf {x} ^ {(j)} || $ mezi libovolnými dvěma příklady tréninku, a právě jsem nastavil $ w_i = 1 $. To znamená, že pokud jde o jádro, všechny tréninkové body jsou od sebe vzdáleny miliardu sigmat a každý bod zcela ovládá znaménko $ \ hat {y} $ v jeho sousedství. Formálně máme

$$ \ hat {y} (\ mathbf {x} ^ {(k)}) = \ sum_ {i = 1} ^ ny ^ {(k)} K (\ mathbf {x} ^ {(i)}, \ mathbf {x} ^ {(k)}) = y ^ {(k)} K (\ mathbf {x} ^ {(k)}, \ mathbf {x} ^ {(k)}) + \ sum_ {i \ neq k} y ^ {(i)} K (\ mathbf {x} ^ {(i)}, \ mathbf {x} ^ {(k)}) = y ^ {(k)} + \ epsilon $$

kde $ \ epsilon $ je libovolně malá hodnota. Víme, že $ \ epsilon $ je malý, protože $ \ mathbf {x} ^ {(k)} $ je miliarda sigmat od jakéhokoli jiného bodu, takže pro všechny $ i \ neq k $ máme

$$ K (\ mathbf {x} ^ {(i)}, \ mathbf {x} ^ {(k)}) = \ exp (- || \ mathbf {x} ^ {(i)} - \ mathbf { x} ^ {(k)} || ^ 2 / \ sigma ^ 2) \ přibližně 0. $$

Protože $ \ epsilon $ je tak malý, $ \ hat {y} (\ mathbf { x} ^ {(k)}) $ má určitě stejné znaménko jako $ y ^ {(k)} $ a klasifikátor dosahuje dokonalé přesnosti tréninkových dat.

2. Učení jádra SVM jako lineární separace

Skutečnost, že to lze interpretovat jako „dokonalé lineární oddělení v nekonečném prostoru dimenzionálních funkcí“, pochází z triku jádra, který umožňuje interpretovat jádro jako vnitřní produkt v a (potenciálně nekonečně-dimenzionální) prostor funkcí:

$$ K (\ mathbf {x} ^ {(i)}, \ mathbf {x} ^ {(j)}) = \ langle \ Phi (\ mathbf {x} ^ {(i)}), \ Phi (\ mathbf {x} ^ {(j)}) \ rangle $$

kde $ \ Phi (\ mathbf {x} ) $ je mapování z datového prostoru do prostoru funkcí. Z toho okamžitě vyplývá, že funkce $ \ hat {y} (\ mathbf {x}) $ funguje jako lineární funkce v prostoru funkcí:

$$ \ hat {y} (\ mathbf {x}) = \ sum_i w_i y ^ {(i)} \ langle \ Phi (\ mathbf {x} ^ {(i)}), \ Phi (\ mathbf {x}) \ rangle = L (\ Phi (\ mathbf {x})) $$

kde lineární funkce $ L (\ mathbf {v}) $ je definována na vektorech prostorového prostoru $ \ mathbf {v} $ as

$$ L (\ mathbf {v}) = \ sum_i w_i y ^ {(i)} \ langle \ Phi (\ mathbf {x} ^ {(i) }), \ mathbf {v} \ rangle $$

Tato funkce je lineární v $ \ mathbf {v} $, protože je to jen lineární kombinace vnitřních produktů s pevnými vektory. V prostoru funkcí je hranice rozhodnutí $ \ hat {y} (\ mathbf {x}) = 0 $ pouze $ L (\ mathbf {v}) = 0 $, sada úrovní lineární funkce. Toto je samotná definice nadroviny v prostoru funkcí.

3. Porozumění mapování a prostoru funkcí

Poznámka: V této části se odkazuje na $ \ mathbf {x} ^ {(i)} $ libovolná sada $ n $ bodů a ne tréninková data. To je čistá matematika; tréninková data do této sekce vůbec nefigurují!

Metody jádra nikdy ve skutečnosti „nenaleznou“ nebo „nevypočítají“ prostor funkcí nebo mapování $ \ Phi $ explicitně. Metody učení jádra, jako je SVM, nepotřebují, aby fungovaly; potřebují pouze funkci jádra $ K $.

To znamená, že je možné zapsat vzorec pro $ \ Phi $. Prostor funkcí, na který $ \ Phi $ mapuje, je jaksi abstraktní (a potenciálně nekonečně dimenzionální), ale v zásadě mapování používá pouze jádro k provádění jednoduchého inženýrství funkcí. Pokud jde o konečný výsledek, model, který se nakonec naučíte používat jádra, se nijak neliší od tradičního inženýrství funkcí, které se běžně používá v lineární regrese a modelování GLM, jako je převzetí protokolu pozitivní proměnné prediktoru před jeho vložením do regresního vzorce. Matematika je většinou právě tam, aby se ujistil, že jádro dobře hraje s algoritmem SVM, který má své vychvalované výhody sparsity a škálování na velké datové sady.

Pokud máte stále zájem, funguje to takto. V podstatě vezmeme identitu, kterou chceme držet, $ \ langle \ Phi (\ mathbf {x}), \ Phi (\ mathbf {y}) \ rangle = K (\ mathbf {x}, \ mathbf {y}) $ , a zkonstruovat prostor a vnitřní produkt tak, že drží podle definice. Za tímto účelem definujeme abstraktní vektorový prostor $ V $, kde každý vektor je funkcí z prostoru, ve kterém data žijí, $ \ mathcal {X} $, na reálná čísla $ \ mathbb {R} $. Vektor $ f $ v $ V $ je funkce vytvořená z konečné lineární kombinace řezů jádra: $$ f (\ mathbf {x}) = \ sum_ {i = 1} ^ n \ alpha_i K (\ mathbf {x } ^ {(i)}, \ mathbf {x}) $$ Je vhodné psát $ f $ kompaktněji jako $$ f = \ sum_ {i = 1} ^ n \ alpha_i K _ {\ mathbf {x} ^ {(i)}} $$ kde $ K_ \ mathbf {x} (\ mathbf {y}) = K (\ mathbf {x}, \ mathbf {y}) $ je funkce poskytující "řez" jádra at $ \ mathbf {x} $.

Vnitřní produkt v prostoru není obyčejný bodový produkt, ale abstraktní vnitřní produkt založený na jádře:

$$ \ langle \ sum_ {i = 1} ^ n \ alpha_i K _ {\ mathbf {x} ^ {(i)}}, \ sum_ {j = 1} ^ n \ beta_j K _ {\ mathbf {x} ^ {(j)} } \ rangle = \ sum_ {i, j} \ alpha_i \ beta_j K (\ mathbf {x} ^ {(i)}, \ mathbf {x} ^ {(j)}) $$

S takto definovaným prostorem funkcí je $ \ Phi $ mapování $ \ mathcal {X} \ rightarrow V $, přičemž každý bod $ \ mathbf {x} $ je v tomto bodě převeden na "řez jádra":

$$ \ Phi (\ mathbf {x}) = K_ \ mathbf {x}, \ quad \ text {kde} \ quad K_ \ mathbf {x} (\ mathbf {y}) = K (\ mathbf {x}, \ mathbf {y}). $$

Můžete dokázat, že $ V $ je vnitřní produktový prostor, když $ K $ je pozitivní definitivní jádro. Podrobnosti najdete v tomto příspěvku. (Kudos až f coppens, že na to upozornili!)

4. Proč je prostor funkcí nekonečně rozměrný?

Tato odpověď poskytuje pěkné vysvětlení lineární algebry, ale zde je geometrická perspektiva s intuicí i důkazem.

Intuice

Pro jakýkoli pevný bod $ \ mathbf {z} $ máme funkci řezu jádra $ K_ \ mathbf {z} (\ mathbf {x}) = K (\ mathbf {z}, \ mathbf {x}) $. Graf $ K_ \ mathbf {z} $ je pouze Gaussův hrbolek soustředěný na $ \ mathbf {z} $. Pokud by byl prostor funkcí pouze konečný rozměr, znamenalo by to, že bychom mohli vzít konečnou množinu hrbolek na pevnou množinu bodů a vytvořit jakýkoli Gaussův hrbolek kdekoli jinde. Ale zjevně neexistuje způsob, jak to udělat; ze starých hrbolů nemůžete udělat nový hrbolek, protože nový hrb může být opravdu daleko od těch starých. Takže bez ohledu na to, kolik máme vektorů rysů (hrboly), můžeme vždy přidat nové hrboly a v prostoru rysů jsou to nové nezávislé vektory. Takže prostor funkcí nemůže být konečný rozměrný; musí to být nekonečné.

Důkaz

Používáme indukci. Předpokládejme, že máte libovolnou množinu bodů $ \ mathbf {x} ^ {(1)}, \ mathbf {x} ^ {(2)}, \ ldots, \ mathbf {x} ^ {(n)} $ takové, že vektory $ \ Phi (\ mathbf {x} ^ {(i)}) $ jsou v prostoru funkcí lineárně nezávislé. Nyní najděte bod $ \ mathbf {x} ^ {(n + 1)} $ odlišný od těchto $ n $ bodů, ve skutečnosti od nich všech miliard sigmat. Tvrdíme, že $ \ Phi (\ mathbf {x} ^ {(n + 1)}) $ je lineárně nezávislé na prvních $ n $ vektorech funkcí $ \ Phi (\ mathbf {x} ^ {(i)}) $ .

Důkaz rozporem. Předpokládejme naopak, že

$$ \ Phi (\ mathbf {x} ^ {(n + 1)}) = \ sum_ {i = 1} ^ n \ alpha_i \ Phi (\ mathbf {x} ^ {(i)}) $$

Nyní vezměte vnitřní produkt na obě strany s libovolným $ \ mathbf {x} $. Identitou $ \ langle \ Phi (\ mathbf {z}), \ Phi (\ mathbf {x}) \ rangle = K (\ mathbf {z}, \ mathbf {x}) $ získáme

$$ K (\ mathbf {x} ^ {(n + 1)}, \ mathbf {x}) = \ sum_ {i = 1} ^ n \ alpha_i K (\ mathbf {x} ^ {(i )}, \ mathbf {x}) $$

Zde je $ \ mathbf {x} $ volná proměnná, takže tato rovnice je identita, která uvádí, že dvě funkce jsou stejné. Zejména říká, že Gaussian se středem na $ \ mathbf {x} ^ {(n + 1)} $ může být reprezentován jako lineární kombinace Gaussianů v jiných bodech $ \ mathbf {x} ^ {(i)} $ . Je geometricky zřejmé, že nelze vytvořit Gaussův hrbolek soustředěný v jednom bodě z konečné kombinace Gaussianských hrbolek soustředěných v jiných bodech, zvláště když jsou všechny ostatní Gaussovy hrboly vzdálené miliardu sigmat. Náš předpoklad lineární závislosti tedy vedl k rozporu, jak jsme se rozhodli ukázat.

Matice jádra gaussovského jádra má vždy úplnou hodnost pro odlišné $ \ mathbf x_1, ..., \ mathbf x_m $. To znamená, že pokaždé, když přidáte nový příklad, pořadí se zvýší o $ 1 $. Nejjednodušší způsob, jak to zjistit, pokud nastavíte $ \ sigma $ na velmi malou. Pak je matice jádra téměř diagonální.

Skutečnost, že se pořadí vždy zvyšuje o jednu, znamená, že všechny projekce $ \ Phi (\ mathbf x) $ v prostoru funkcí jsou lineárně nezávislé (ne ortogonální, ale nezávislé). Proto každý příklad přidává novou dimenzi do rozsahu projekcí $ \ Phi (\ mathbf x_1), ..., \ Phi (\ mathbf x_m) $. Jelikož můžete přidat nespočet nekonečně mnoho příkladů, musí mít prostor prvků nekonečnou dimenzi. Zajímavé je, že všechny projekce vstupního prostoru do prostorového prostoru leží na kouli, protože $ || \ Phi (\ mathbf x) || _ {\ mathcal H} ^ ² = k (\ mathbf x, \ mathbf x) = 1 $. Geometrie koule je nicméně plochá. Více se o tom můžete dočíst v

Burges, C. J. C. (1999). Geometrie a invariance v metodách založených na jádře. In B. Schölkopf, C. J. C. Burges, & A. J. Smola (Eds.), Advances in Kernel Methods Support Vector Learning (str. 89–116). MIT Press.

Pokud jde o pozadí a notace, odkazuji na odpověď Jak vypočítat hranici rozhodnutí z vektorů podpory?.

Takže funkcemi v „původním“ prostoru jsou vektory $ x_i $, binární výsledek $ y_i \ in \ {- 1, +1 \} $ a Lagrangeovy multiplikátory jsou $ \ alpha_i $.

Je známo, že jádro lze zapsat jako $ K (x, y) = \ Phi (x) \ cdot \ Phi (y) $ ('$ \ cdot $' představuje vnitřní produkt. ) Kde $ \ Phi $ je (implicitní a neznámá) transformace do prostoru nových funkcí.

Pokusím se dát nějaké „intuitivní“ vysvětlení toho, jak tento $ \ Phi $ vypadá, takže tato odpověď není žádným formálním důkazem, chce jen dát nějaký pocit, jak si myslím, že to funguje. Pokud se mýlím, neváhejte mě opravit. Základem mého vysvětlení je část 2.2.1 tohoto pdf

Musím ‚transformovat 'svůj prostor funkcí (tedy můj $ x_i $) na nějaký‚ nový' prostor funkcí ve kterém bude řešena lineární separace.

Pro každé pozorování $ x_i $ definuji funkce $ \ phi_i (x) = K (x_i, x) $, takže mám funkci $ \ phi_i $ pro každý prvek mého tréninkového vzorku. Tyto funkce $ \ phi_i $ překlenují vektorový prostor. Vektorový prostor překlenutý $ \ phi_i $, všimněte si to $ V = span (\ phi_ {i, i = 1,2, \ dots N}) $. ($ N $ je velikost cvičného vzorku).

Pokusím se tvrdit, že tento vektorový prostor $ V $ je vektorový prostor, ve kterém bude možná lineární separace. Podle definice rozpětí každý vektor ve vektorovém prostoru $ V $ lze psát jako lineární kombinaci $ \ phi_i $, tj .: $ \ sum_ {i = 1} ^ N \ gamma_i \ phi_i $, kde $ \ gamma_i $ jsou reálná čísla. Ve skutečnosti tedy $ V = \ {v = \ sum_ {i = 1} ^ N \ gamma_i \ phi_i | (\ gamma_1, \ gamma_2, \ dots \ gamma_N) \ in \ mathbb {R} ^ N \} $

Všimněte si, že $ (\ gamma_1, \ gamma_2, \ dots \ gamma_N) $ jsou souřadnice vektoru $ v $ ve vektorovém prostoru $ V $.

$ N $ je velikost cvičného vzorku, a proto může dimenze vektorového prostoru $ V $ dosáhnout až $ N $, v závislosti na tom, zda jsou $ \ phi_i $ lineárně nezávislé. Protože $ \ phi_i (x) = K (x_i, x) $ (viz výše, definovali jsme $ \ phi $ tímto způsobem), to znamená, že dimenze $ V $ závisí na použitém jádře a může jít až do velikosti cvičného vzorku.

Pokud je jádro dostatečně složité, pak bude $ \ phi_i (x) = K (x_i, x) $ nezávislé a poté rozměr $ V $ bude $ N $, což je velikost cvičného vzorku.

Transformace, která mapuje můj původní prostor funkcí na $ V $, je definována jako

$ \ Phi: x_i \ to \ phi_i (x) = K (x_i, x) $ .

Tato mapa $ \ Phi $ mapuje můj původní prostor funkcí na vektorový prostor, který může mít dimenzi, která jde až do velikosti mého tréninkového vzorku. Takže $ \ Phi $ mapuje každé pozorování v mém tréninkovém vzorku do vektorového prostoru, kde jsou vektory funkcí. Vektor $ x_i $ z mého tréninkového vzorku je 'mapován' na vektor v $ V $, jmenovitě vektor $ \ phi_i $ se všemi souřadnicemi rovnými nule, kromě souřadnice $ i $ -th je 1.

Je zřejmé, že tato transformace (a) závisí na jádře, (b) závisí na hodnotách $ x_i $ ve cvičném vzorku a (c) může, v závislosti na mém jádře, mít dimenzi, která jde až do velikosti můj tréninkový vzorek a (d) vektory $ V $ vypadají jako $ \ sum_ {i = 1} ^ N \ gamma_i \ phi_i $, kde $ \ gamma_i $ jsou reálná čísla.

Při pohledu na funkci $ f (x) $ v Jak vypočítat hranici rozhodnutí z vektorů podpory? je vidět, že $ f (x) = \ sum_i y_i \ alpha_i \ phi_i (x) + b $. Hranice rozhodnutí nalezená SVM je $ f (x) = 0 $.

Jinými slovy, $ f (x) $ je lineární kombinace $ \ phi_i $ a $ f (x) = 0 $ je lineární oddělující nadrovina v $ V $ - mezerník : jedná se o zvláštní volbu $ \ gamma_i $, konkrétně $ \ gamma_i = \ alpha_i y_i $!

$ y_i $ jsou známy z našich pozorování, $ \ alpha_i $ jsou Lagrangeovy multiplikátory, které SVM našel. Jinými slovy SVM najde pomocí jádra a vyřešením kvadratického programovacího problému lineární oddělení v $ V $ -spave.

Toto je moje intuitivní chápání toho, jak „jádrový trik“ umožňuje „implicitně“ transformovat původní prostor funkcí na prostor nových funkcí $ V $ s jinou dimenzí. Tato dimenze závisí na použitém jádře a pro jádro RBF může tato dimenze dosáhnout až velikosti cvičného vzorku. Jelikož ukázky tréninku mohou mít jakoukoli velikost, mohlo by se to dostat až k „nekonečnu“ . Je zřejmé, že ve velmi dimenzionálních prostorech se riziko nadměrného vybavení zvýší.

Takže jádra jsou technikou, která umožňuje SVM transformovat váš prostor funkcí, viz také Co dělá gaussovské jádro tak magickým pro PCA a také obecně?

Vysvětlení fcopu je bohužel docela nesprávné. Nejprve říká: „Je známo, že jádro lze zapsat jako ... kde ... je (implicitní a neznámá) transformace do prostoru nových funkcí.“ Není to neznámé. Toto je ve skutečnosti prostor, na který jsou objekty mapovány, a toto je prostor, který může být nekonečně dimenzionální, jako v případě RBF. Jediné, co jádro dělá, je vzít vnitřní produkt tohoto transformovaného vektoru funkcí s vektorem transformovaných funkcí z příkladu tréninku a použít nějakou funkci na výsledek. Implicitně tedy představuje tento vyšší dimenzionální rysový vektor. Myslete například na psaní (x + y) ^ 2 místo x ^ 2 + 2xy + y ^ 2. Nyní si představte, jakou nekonečnou řadu implicitně reprezentuje exponenciální funkce ... a máte nekonečný prostor funkcí. To nemá absolutně nic společného se skutečností, že vaše tréninková sada může být nekonečně velká.

Správným způsobem, jak přemýšlet o SVM, je to, že své prvky mapujete do možná nekonečného dimenzionálního prostoru funkcí, který je implicitně reprezentovatelný v ještě dalším konečném dimenzionálním prostoru funkcí „jádra“, jehož rozměr může být stejně velký jako velikost tréninkové sady.