SVM a jádrový trik: nejširší hranice a jak ji ohnout

Hranice s největším okrajem a podpůrné vektory, měkký okraj a parametr C, zvednutí dat do většího prostoru, jádrový trik s polynomiálním a gaussovským jádrem a vliv parametru γ na přeučení.

13 minut Matěj Žalmánek 2026-10-16

Série Základy AI Díl 55 z 83

Celá osnova série 83 z 83 témat hotovo

Co si odnesete

Proč SVM hledá nejširší okraj a proč na řešení stačí pár podpůrných vektorů.
Jak parametr C vyvažuje šířku okraje a chyby.
Jak jádrový trik ohne hranici bez sestrojení obřího prostoru příznaků a co dělá parametr γ.

Co se hodí znát předem: Logistická regrese: sigmoida, šance a křížová entropie, Ztrátové funkce: co přesně model minimalizuje

V 90. letech a na začátku tisíciletí byla metoda podpůrných vektorů (SVM) králem strojového učení: rozpoznávala ručně psané číslice, třídila texty, hledala geny. Stojí na dvou elegantních nápadech. První: když jde dvě třídy oddělit mnoha přímkami, vyber tu, která nechá na obou stranách nejvíc místa. Druhý: když je oddělit přímkou nejde, převeď je do prostoru, kde to jde — a celý výpočet přitom proveď, aniž bys ten prostor kdy sestrojil. Tomu druhému se říká jádrový trik a patří k nejkrásnějším myšlenkám celého oboru.

Navazuje na díly Logistická regrese a Ztrátové funkce, kde jsme poznali hinge ztrátu.

1. Nejširší ulice mezi třídami

Čtyřicet bodů dvou tříd, které jdou oddělit přímkou bez chyby. Takových přímek je nekonečně mnoho a všechny mají na trénovacích datech stoprocentní přesnost. Která je nejlepší?

Definice — okraj a SVM s tvrdým okrajem

Nechť d, n ≥ 1 a (x₁, y₁), …, (x_n, y_n) jsou trénovací data, kde x_i ∈ ℝ^d a y_i ∈ {−1, +1} pro i = 1, …, n, a obě třídy jsou zastoupené. Nechť w ∈ ℝ^d, w ≠ 0, a b ∈ ℝ určují hranici — nadrovinu H = {x ∈ ℝ^d : w · x + b = 0} (skalární součin, norma ‖w‖ a vzdálenost od nadroviny jsou zavedené v další definici).

Hranice H data odděluje, právě když y_i(w · x_i + b) > 0 pro všechna i = 1, …, n; data jsou lineárně oddělitelná, právě když taková hranice existuje. Okraj (margin) oddělující hranice je šířka nejširšího pásu kolem H, ve kterém neleží žádný bod x_i, tj. dvojnásobek vzdálenosti nejbližšího bodu od H:

ρ(w, b) = 2 · min_{i = 1, …, n} |w · x_i + b|/‖w‖.

SVM s tvrdým okrajem pro lineárně oddělitelná data je optimalizační úloha

min_{w ∈ ℝ^d, b ∈ ℝ} ½‖w‖² za podmínek y_i(w · x_i + b) ≥ 1 pro i = 1, …, n.

Její řešení (w*, b*) existuje, je jediné a jeho okraj je ρ(w*, b*) = 2/‖w*‖ — největší ze všech oddělujících hranic (odvození v další definici).

Podpůrné vektory jsou body x_i, pro které podmínka platí s rovností, y_i(w* · x_i + b*) = 1. Řešení závisí jen na nich: kdybychom všechny ostatní body z dat vynechali, vyjde stejné (w*, b*).

SVM tedy ze všech přímek (nadrovin), které třídy oddělí, vybere tu, od které má nejbližší bod největší vzdálenost.

Laicky řečeno

Mezi dvěma vesnicemi chceme postavit co nejširší ulici, aby žádný dům nestál na silnici. Osa ulice je hranice. Široká ulice je pojistka: nový dům, postavený trochu vedle těch dosavadních, pořád padne na správnou stranu. Šířku ulice určí jen domy, které stojí přímo u chodníku — ostatní by se mohly přestěhovat kamkoli dál a ulice by zůstala stejná.

Proč je okraj 2/‖`w`‖

Definice — nadrovina, norma a vzdálenost bodu od ní

Nechť d ≥ 1. Pro u, v ∈ ℝ^d je skalární součin u · v = ∑_j=1^d u_jv_j a (eukleidovská) norma vektoru w ∈ ℝ^d je jeho délka

‖w‖ = √w · w = √w₁² + … + w_d².

Nechť w ∈ ℝ^d, w ≠ 0, a b ∈ ℝ. Nadrovina s normálovým vektorem w a posunem b je množina

H = {x ∈ ℝ^d : w · x + b = 0}.

Vektor w je na ni kolmý: pro všechna x, x′ ∈ H je w · (x − x′) = 0. V rovině (d = 2) je nadrovina přímka, v prostoru (d = 3) rovina. Vzdálenost bodu x ∈ ℝ^d od H je dist(x, H) = min_{x′ ∈ H} ‖x − x′‖.

Věta. Nechť w ∈ ℝ^d, w ≠ 0, b ∈ ℝ, H je nadrovina jako výše a x ∈ ℝ^d. Pak

dist(x, H) = |w · x + b|/‖w‖.

Důkaz. Nejbližší bod H k bodu x je jeho kolmý průmět, tedy bod tvaru x₀ = x − t · w/‖w‖, kde t ∈ ℝ je (znaménková) vzdálenost a |t| = ‖x − x₀‖. Bod x₀ leží na nadrovině: 0 = w · x − t (w · w)/‖w‖ + b = w · x + b − t‖w‖, takže t = w · x + b/‖w‖. ∎

Podmínky SVM chtějí y_i(w · x_i + b) ≥ 1, a protože |y_i| = 1, je |w · x_i + b| ≥ 1: každý bod je od hranice aspoň 1/‖w‖ daleko a podpůrné vektory přesně tolik. Ulice má dva chodníky, takže šířka je 2/‖w‖.

min_{w, b} ½‖w‖² za podmínek y_i (w · x_i + b) ≥ 1 pro všechna i

½‖w‖²: šířka ulice je 2/‖w‖, takže nejširší ulice = nejkratší w. Místo ‖w‖ se minimalizuje jeho čtverec (má stejné minimum, ale je hladký a kvadratický — úloha je konvexní) a ½ jen zjednoduší derivaci na w
y_i: štítek ±1 otočí znaménko u třídy −1, takže jedna nerovnost platí pro obě třídy: kladné body musí být na kladné straně, záporné na záporné
w · x_i + b: skóre bodu: znaménko říká, na které straně hranice leží, velikost (dělená ‖w‖) jak daleko
≥ 1: každý bod musí stát aspoň na chodníku. Jednička je jen volba měřítka: w a b lze vynásobit libovolným kladným číslem a hranice se nezmění, tak je škálujeme tak, aby nejbližší body měly skóre přesně ±1

Ze všech hranic, které oddělí data s rezervou, vyber tu s nejkratším w — tedy s nejširší ulicí.

SVM s tvrdým okrajem; čárkovaně okraje, žlutě podpůrné vektory, fialově hranice logistické regrese

Hranici SVM určují jen 3 podpůrné vektory ze 40 bodů a ulice je široká 1,90. Logistická regrese oddělí body také bez chyby, ale její hranice nechá kolem sebe volný pás široký jen 1,74 — nesnaží se o širokou ulici, ale o pravděpodobnosti, a na to ji ovlivňují všechny body.

Příklad — přepočítejte si hranici z obrázku

Naučené SVM má w = (0,914; 0,526) a b = −0,049. Tři podpůrné vektory:

bod	`x`₁	`x`₂	`y`	`w` · `x` + `b`	`α`
A	−1,013	−0,048	−1	−1,00	0,556
B	1,291	−0,248	+1	+1,00	0,129
C	0,431	1,246	+1	+1,00	0,427

bod A: 0,914 · (−1,013) + 0,526 · (−0,048) − 0,049 = −0,925 − 0,025 − 0,049 = −1,00, (−1) · (−1,00) = 1 ≥ 1 (přesně na chodníku; barvy podle vzorce výše)

‖w‖ = √0,914² + 0,526² = √0,835 + 0,277 = √1,112 = 1,054

šířka ulice 2/‖w‖ = 2/1,054 = 1,90

w = ∑ α_iy_ix_i: 0,556 · (−1) · (−1,013; −0,048) + 0,129 · (1,291; −0,248) + 0,427 · (0,431; 1,246) = (0,914; 0,526)

Zbylých 37 bodů má skóre (se správným znaménkem) větší než 1 a váhu α = 0 — v posledním řádku nefigurují vůbec. Proto by se mohly „přestěhovat“, kam chtějí, a hranice by se nepohnula. Váhy α vysvětlí oddíl o jádrovém triku.

2. Měkký okraj: když se třídy překrývají

Skutečná data skoro nikdy nejdou oddělit bez chyby. SVM proto dovolí některým bodům stát na chodníku nebo i na špatné straně — za poplatek.

Definice — SVM s měkkým okrajem

Nechť (x₁, y₁), …, (x_n, y_n) jsou trénovací data, x_i ∈ ℝ^d, y_i ∈ {−1, +1} (nemusí být lineárně oddělitelná), a nechť C > 0 je parametr. SVM s měkkým okrajem je optimalizační úloha

min_{w ∈ ℝ^d, b ∈ ℝ} ½‖w‖² + C ∑_i=1ⁿ max(0, 1 − y_i(w · x_i + b)).

Člen max(0, 1 − y_i(w · x_i + b)) je hinge ztráta bodu i (viz Ztrátové funkce). Pro řešení (w*, b*) jsou podpůrné vektory body x_i, pro které y_i(w* · x_i + b*) ≤ 1, tj. leží na okraji, uvnitř pásu, nebo na špatné straně hranice. Ostatní body mají nulovou ztrátu a jejich vynechání řešení nezmění.

Parametr C tedy určuje, kolik stojí porušení okraje proti šířce ulice.

Laicky řečeno

C je pokuta za každý dům na silnici. Malé C: ať si tam pár domů stojí, hlavně ať je ulice široká. Velké C: ulice smí být úzká, ale domy na ní nestrpíme. Je to stejná hinge ztráta z dílu o ztrátových funkcích, jen s regularizací v jiném převleku.

min_{w, b} ½‖w‖² + C ∑_i max(0, 1 − y_i(w · x_i + b))

½‖w‖²: stejně jako u tvrdého okraje: táhne k široké ulici. Z pohledu ztrátových funkcí je to L2 regularizace
C: kurz, kterým se přepočítávají porušení na šířku ulice. Bez něj by šlo jen o jeden z extrémů: buď nejširší ulici bez ohledu na chyby, nebo žádné chyby bez ohledu na šířku
y_i(w · x_i + b): skóre bodu se znaménkem podle jeho třídy: kladné = správná strana, záporné = špatná
1: poloha chodníku. Pokutuje se už bod, který je na správné straně, ale uvnitř ulice — jinak by SVM nemělo důvod okraj vůbec držet
max(0, …): hinge ztráta: bod za chodníkem neplatí nic, a proto řešení neovlivní. Kdo je uvnitř, platí lineárně podle toho, jak hluboko — jeden špatný bod tak nepřebije všechny ostatní, jako by to udělal čtverec

Šířka ulice proti součtu pokut; C rozhoduje, kolik pokuty vyváží jednotku šířky.

Definice — skluzové proměnné

Nechť data (x_i, y_i), i = 1, …, n, a parametr C > 0 jsou jako v definici měkkého okraje. Formulace se skluzovými proměnnými (slack) ξ = (ξ₁, …, ξ_n) ∈ ℝⁿ je úloha

min_{w ∈ ℝ^d, b ∈ ℝ, ξ ∈ ℝⁿ} ½‖w‖² + C ∑_i=1ⁿ ξ_i za podmínek

y_i(w · x_i + b) ≥ 1 − ξ_i pro i = 1, …, n,
ξ_i ≥ 0 pro i = 1, …, n.

Pro pevná w, b je nejmenší přípustné ξ_i = max(0, 1 − y_i(w · x_i + b)) a cíl s ξ_i roste, takže v optimu platí právě tahle rovnost a úloha má stejná optimální w, b jako úloha s hinge ztrátou.

ξ_i = 0: bod je na chodníku nebo za ním. 0 < ξ_i ≤ 1: uvnitř ulice, ale na správné straně (nebo přímo na hranici). ξ_i > 1: na špatné straně hranice. Každý chybně zařazený bod tedy přispěje do ∑ ξ_i aspoň jedničkou a součet je horní mez počtu chyb na tréninkových datech.

Příklad — co zaplatí model s C = 1

Na 100 překrývajících se bodech vyjde pro C = 1 hranice w = (2,068; 1,480), b = 0,314.

‖w‖² = 2,068² + 1,480² = 4,278 + 2,191 = 6,469, šířka ulice 2/√6,469 = 2/2,543 = 0,79

bodů s ξ > 0 (uvnitř ulice nebo za hranicí): 21, z toho na špatné straně (ξ > 1): 5 (přesnost na tréninku 95 %)

součet pokut ∑ ξ_i = ∑ max(0, …) = 15,47

hodnota cíle: ½ · 6,469 + 1 · 15,47 = 3,23 + 15,47 = 18,70 (barvy podle vzorce měkkého okraje výše)

Pokuty tu převažují nad šířkou zhruba pětkrát. S C = 0,01 je to naopak: ∑ ξ = 41,8, ale v cíli se to počítá jen jako 0,01 · 41,8 = 0,42 — a tak se vyplatí ulici rozšířit na 3,47, i když do ní spadne 74 bodů.

Měkký okraj pro tři hodnoty C (100 bodů, třídy se překrývají)

`C`	0,01	0,1	1	100
šířka okraje 2/‖`w`‖	3,47	1,61	0,79	0,57
podpůrných vektorů (ze 100)	76	40	23	18
přesnost na 4 000 nových bodech	91,0 %	90,7 %	90,6 %	90,8 %

S rostoucím C se ulice zužuje a podpůrných vektorů ubývá. Přesnost se na těchto datech skoro nemění — když jsou třídy dvě oblaka bodů, je správná přímka skoro stejná, ať je ulice úzká, nebo široká. Na C začne záležet u složitějších hranic, kde příliš velké C vede k přeučení; tam se volí křížovou validací.

3. Když přímka nestačí: zvedni data

Na přímce leží body dvou tříd: zelené uprostřed, červené po stranách. Žádný jeden práh je neoddělí. Stačí ale ke každému bodu x přidat druhou souřadnici x² — a body se zvednou na parabolu, kde je oddělí obyčejná vodorovná přímka:

Zobrazení x ↦ (x, x²) udělá z neoddělitelných dat oddělitelná

To je stejný trik jako kvadratické příznaky v dílu o logistické regresi. Má jeden háček: příznaků je rychle moc. Všech součinů nejvýš třetího stupně ze 100 příznaků je 176 851; z obrázku 28 × 28 pixelů (784 příznaků) přes 80 milionů. Spočítat je pro každý bod a naučit na nich model je nepraktické.

Definice — zobrazení do prostoru příznaků a počet monomů

Nechť p, D ≥ 1. Zobrazení příznaků je libovolná funkce φ : ℝ^p → ℝ^D, která ze vstupu x ∈ ℝ^p udělá nový, obvykle delší vektor φ(x) ∈ ℝ^D. Lineární model v prostoru příznaků je funkce

f(x) = w · φ(x) + b, w ∈ ℝ^D, b ∈ ℝ;

učí se tedy na φ(x) místo na x. Na obrázku je p = 1, D = 2, φ(x) = (x, x²) a hranice x² = 1 je v novém prostoru přímka s w = (0, 1), b = −1 — v původním prostoru jsou to dva prahy x = ±1.

Nechť x = (x₁, …, x_p) ∈ ℝ^p a k = (k₁, …, k_p) ∈ ℕ₀^p. Monom s exponenty k je číslo x₁^k₁ ⋯ x_p^k_p; jeho stupeň je k₁ + … + k_p. Pro d ≥ 1 je polynomiální zobrazení stupně d zobrazení φ_d : ℝ^p → ℝ^D, jehož složky jsou všechny monomy stupně nejvýš d, každý právě jednou (včetně konstanty 1 pro k = (0, …, 0)). Jejich počet je

D = |{k ∈ ℕ₀^p : k₁ + … + k_p ≤ d}| = (p + d)!/p! d!,

protože každý monom odpovídá právě jednomu rozdělení d „jednotek stupně“ mezi p proměnných a jednu „nevyužitou“ přihrádku.

p = 2, d = 2: 4!/2! · 2! = 6 (1, x₁, x₂, x₁², x₂², x₁x₂)

p = 100, d = 3: 103!/100! · 3! = 103 · 102 · 101/6 = 176 851

p = 784, d = 3: 787!/784! · 3! = 787 · 786 · 785/6 = 80 931 145

Počet roste jako p^d/d! — pro pevný stupeň polynomiálně, ale s velkou mocninou.

4. Jádrový trik

Definice — jádro a jádrový trik

Nechť p, D ≥ 1 a φ : ℝ^p → ℝ^D je zobrazení příznaků. Jádro příslušné k φ je funkce K : ℝ^p × ℝ^p → ℝ,

K(x, z) = φ(x) · φ(z) pro všechna x, z ∈ ℝ^p,

tj. skalární součin obrazů v prostoru příznaků. Obecněji se jádrem nazývá každá funkce K, ke které nějaké takové φ existuje, i do nekonečně rozměrného prostoru se skalárním součinem (kdy to nastane, říká Mercerova podmínka níže).

Nechť (x_i, y_i), i = 1, …, n, jsou trénovací data. SVM v prostoru příznaků se dá zapsat tak, že data potřebuje jen ve skalárních součinech φ(x_i) · φ(x): rozhodovací funkce je

f(x) = ∑_i=1ⁿ α_iy_iK(x_i, x) + b,

kde α₁, …, α_n ≥ 0 jsou váhy z duální úlohy (níže), b ∈ ℝ, a α_i > 0 jen pro podpůrné vektory; bod x zařadíme do třídy sign f(x). Jádrový trik je postup: všude, kde data vystupují jen ve skalárních součinech φ(x) · φ(z), dosadit hodnotu K(x, z) spočítanou přímo z x a z, a vektory φ(x) nikdy nepočítat.

Častá jádra (pro x, z ∈ ℝ^p):

polynomiální stupně d ≥ 1: K(x, z) = (x · z + 1)^d — odpovídá φ, jehož složky jsou (vhodně vynásobené) monomy stupně nejvýš d;
gaussovské (RBF) s parametrem γ > 0: K(x, z) = exp(−γ‖x − z‖²) — odpovídá nekonečně rozměrnému prostoru příznaků.

Laicky řečeno

Pro dva body v rovině je (x · z + 1)² jedno násobení a jedno umocnění — a přitom dá přesně skalární součin vektorů se šesti kvadratickými příznaky, které jsme nikde nesestrojili. Pro RBF jádro by ten prostor měl nekonečně rozměrů; jádro se přesto spočítá na jeden řádek. Intuitivně je RBF jádro míra podobnosti: 1 pro stejné body, skoro 0 pro vzdálené. Výsledný model pak říká: „nový bod patří ke třídě podpůrných vektorů, kterým je nejpodobnější“ — vážené hlasování sousedů, podobně jako kNN.

Duální úloha: kde se vzaly skalární součiny

Proč smí SVM data „vidět“ jen přes skalární součiny? Z Lagrangeových podmínek optimality pro měkký okraj vyjde, že optimální w je vždy kombinací trénovacích bodů, w = ∑_i α_iy_ix_i (u tvrdého okraje jsme to přepočítali výše). Když to dosadíme zpátky, zmizí w i b a zbude úloha jen pro váhy α — duální úloha:

max_α ∑_i α_i − ½ ∑_i∑_j α_iα_j y_iy_j K(x_i, x_j) za podmínek 0 ≤ α_i ≤ C, ∑_i α_iy_i = 0

∑ α_i: α_i je „síla“, kterou bod i tlačí na hranici. Tenhle člen odměňuje každý bod, který se zapojí — sám by poslal všechny váhy nahoru
y_iy_j: +1 pro dvojici ze stejné třídy, −1 pro dvojici z různých. Podobné body téže třídy se tak navzájem brzdí (stačí, když tlačí jeden z nich), podobné body různých tříd naopak váhu dostanou — jsou to ty u hranice
K(x_i, x_j): jediné místo, kde do úlohy vstupují data — a jen jako podobnost dvojic. Proto stačí umět spočítat K, ne φ
0 ≤ α_i ≤ C: strop C je měkký okraj v duálním převleku: jeden bod nesmí tlačit libovolně silně, takže ani bod na špatné straně nepřetáhne hranici k sobě. Bez stropu (C → ∞) je to tvrdý okraj
∑ α_iy_i = 0: vznikne z derivace podle posunu b: síly obou tříd musí být v rovnováze, jinak by se hranice dala posunout a cíl zlepšit

Body s α_i > 0 jsou podpůrné vektory; rozhodovací funkce f(x) = ∑_i α_iy_iK(x_i, x) + b sčítá jen přes ně.

Na oddělitelných datech z prvního obrázku to sedí: kladné váhy mají jen tři podpůrné vektory, a jejich součet se znaménky je 0,556 · (−1) + 0,129 · (+1) + 0,427 · (+1) = 0 (barvy podle vzorce výše). Podmínce ∑ α_iy_i = 0 odpovídá i to, že síla jediného záporného podpůrného vektoru vyvažuje dva kladné.

Věta — polynomiální jádro je skalární součin šesti příznaků

Nechť φ : ℝ² → ℝ⁶ je zobrazení

φ(x) = (1, √2 x₁, √2 x₂, x₁², x₂², √2 x₁x₂) pro x = (x₁, x₂) ∈ ℝ².

Pak pro všechna x, z ∈ ℝ² platí (x · z + 1)² = φ(x) · φ(z).

Důkaz. (x₁z₁ + x₂z₂ + 1)² = 1 + 2x₁z₁ + 2x₂z₂ + x₁²z₁² + x₂²z₂² + 2x₁z₁x₂z₂, a to je člen po členu součin složek φ(x) a φ(z). Odmocniny ze dvou jsou tam proto, aby součin dvou složek dal právě koeficient 2. ∎

Příklad: x = (1, 2), z = (3, −1).

jádrem: x · z = 3 − 2 = 1, (1 + 1)² = 4 (dvě násobení, sčítání a umocnění)

φ(x) = (1, √2, 2√2, 1, 4, 2√2), φ(z) = (1, 3√2, −√2, 9, 1, −3√2)

skalární součin: 1 + 6 − 4 + 9 + 4 − 12 = 4

Stejné číslo, ale bez šestisložkových vektorů. Pro stupeň 3 a 784 pixelů je to necelých 800 násobení místo sestrojení dvou vektorů s 80 miliony složek.

Definice — kdy je funkce jádrem (Mercerova podmínka)

Ne každá funkce podobnosti je skalárním součinem v nějakém prostoru. Nechť X ⊆ ℝ^p je množina vstupů a K : X × X → ℝ funkce.

K je symetrická, právě když K(x, z) = K(z, x) pro všechna x, z ∈ X.
Pro n ≥ 1 a body x₁, …, x_n ∈ X je Gramova matice G ∈ ℝ^n×n dána předpisem G_ij = K(x_i, x_j) pro i, j = 1, …, n.
Symetrická matice G ∈ ℝ^n×n je pozitivně semidefinitní, právě když ∑_i=1ⁿ ∑_j=1ⁿ c_ic_jG_ij ≥ 0 pro všechna c = (c₁, …, c_n) ∈ ℝⁿ.

Věta (Mercerova podmínka). Nechť K : X × X → ℝ je symetrická. Pak existuje prostor se skalárním součinem ⟨·, ·⟩ (případně nekonečně rozměrný) a zobrazení φ do něj takové, že K(x, z) = ⟨φ(x), φ(z)⟩ pro všechna x, z ∈ X, právě když pro každé n ≥ 1 a každé body x₁, …, x_n ∈ X je Gramova matice pozitivně semidefinitní.

Právě tahle vlastnost dělá z duální úlohy konvexní úlohu (hledá se maximum konkávní funkce), takže má jediné optimum a algoritmus nezávisí na startu. Polynomiální i gaussovské jádro ji splňují.

Jak se to učí: SMO

Duální úlohu řeší algoritmus SMO (Sequential Minimal Optimization, John Platt, 1998). Nejmenší krok, který neporuší podmínku ∑ α_iy_i = 0, je změnit dvě váhy naráz — a pro dvě proměnné se optimum spočítá vzorcem. Naše obrázky počítá jeho zjednodušená verze:

def smo(X, y, K, C, tol=1e-3):
    a = [0] * n;  b = 0
    f = lambda x: sum(a[j] * y[j] * K(X[j], x) for j in range(n)) + b
    while ještě nebylo 50 průchodů po sobě beze změny:
        for i in range(n):
            Ei = f(X[i]) - y[i]                       # chyba na bodu i
            if (y[i]*Ei < -tol and a[i] < C) or (y[i]*Ei > tol and a[i] > 0):
                j = náhodný index různý od i;  Ej = f(X[j]) - y[j]
                L, H = meze pro a[j], aby 0 ≤ a ≤ C a ∑ a·y zůstal stejný
                eta = 2*K(X[i],X[j]) - K(X[i],X[i]) - K(X[j],X[j])   # zakřivení, < 0
                aj_nove = ořízni(a[j] - y[j] * (Ei - Ej) / eta, L, H)
                a[i] += y[i] * y[j] * (a[j] - aj_nove)  # aby ∑ a·y zůstal 0
                a[j] = aj_nove
                b = přepočti z bodu, jehož nová váha leží mezi 0 a C
    return a, b                                   # podpůrné vektory: a > 0

Podmínka v if hledá body, které porušují podmínky optimality: bod uvnitř ulice, který ještě nemá plnou váhu C, nebo bod daleko za chodníkem, který přitom váhu má. Když už žádný takový není, je dosaženo optima.

Zkusme to na kruhu: 200 bodů ve čtverci, třída „uvnitř“ v kruhu, a 8 % štítků náhodně prohozených. Model, který by znal skutečný kruh, by měl na nových bodech přesnost 92,2 %.

Jádrové SVM na kruhových datech; čárkovaně skutečný kruh, žlutě podpůrné vektory

Lineární SVM nemá šanci: přesnost 69,0 %, tedy jen tolik, kolik dá „vždycky venku“. Polynomiální jádro 2. stupně najde elipsu a dosáhne 87,5 % (s C = 100; s C = 1 je okraj tak měkký, že elipsu zploští a má jen 84,2 %). RBF jádro s γ = 1 má 88,3 %.

5. Parametr γ: jak daleko sahá podobnost

K(x, z) = exp(−γ ‖x − z‖²)

K(x, z): podobnost dvou bodů mezi 0 a 1; v rozhodovací funkci určuje, jak silně podpůrný vektor x_i „hlasuje“ o novém bodu
‖x − z‖²: čtverec vzdálenosti: podobnost má záviset jen na tom, jak daleko body jsou, ne kde leží nebo kterým směrem od sebe. Čtverec místo vzdálenosti dělá z jádra hladký zvon bez špičky uprostřed
γ: měřítko: převádí vzdálenost v jednotkách dat na „vzdálenost v jednotkách podobnosti“. Podobnost klesne na 1/e ≈ 0,37 ve vzdálenosti 1/√γ — to je dosah jednoho bodu
exp(−…): udělá z nezáporného čísla podobnost: pro stejné body exp(0) = 1, se vzdáleností klesá k 0, nikdy záporná. Exponenciála čtverce vzdálenosti navíc zaručí, že Gramova matice je vždy pozitivně semidefinitní — funkce je opravdu jádro, a to s nekonečně rozměrným φ (Taylorova řada exponenciály má nekonečně mnoho členů)

Gaussovský zvon o šířce 1/√γ kolem každého bodu.

Příklad — jak rychle podobnost klesá

Data leží ve čtverci [−1, 1]², kruh má poloměr 0,6 a nejbližší soused je od bodu v průměru 0,072 daleko.

`γ`	dosah 1/√`γ`	`K` ve vzdálenosti 0,1	0,5	1
0,1	3,16	0,999	0,975	0,905
1	1	0,990	0,779	0,368
10	0,32	0,905	0,082	0,000 05
100	0,1	0,368	1 · 10⁻¹¹	≈ 0
1 000	0,032	0,000 05	≈ 0	≈ 0

γ = 1, vzdálenost 0,5: K = exp(−1 · 0,5²) = exp(−0,25) = 0,779 (barvy podle vzorce výše)

γ = 1 000, nejbližší soused (0,072): K = exp(−1 000 · 0,072²) = exp(−5,2) = 0,006

S γ = 0,1 je dosah větší než celý čtverec (úhlopříčka 2,83) — všechny body jsou si skoro stejně podobné a hranice nemá jak se ohnout kolem kruhu. S γ = 1 000 nevidí bod ani svého nejbližšího souseda; každý je ostrůvek sám pro sebe. Nový bod daleko od všech dostane f(x) ≈ b = −0,30, tedy „venku“.

RBF, `C` = 1, `γ` =	0,1	1	10	100	1 000
podpůrných vektorů (z 200)	166	103	99	175	198
přesnost na tréninku	59,0 %	88,5 %	90,0 %	95,0 %	98,5 %
přesnost na 4 000 nových	69,0 %	88,3 %	87,2 %	86,0 %	73,3 %

γ říká, jak rychle podobnost se vzdáleností klesá. Malé γ = každý bod je podobný skoro všem, hranice je moc hladká a model neudělá nic lepšího než „vždycky venku“. Velké γ = každý bod je podobný jen sám sobě: s γ = 1 000 jsou podpůrnými vektory skoro všechny body (198 z 200), model kolem každého nakreslí malý ostrůvek, na tréninku má 98,5 % a na nových datech 73,3 %. Je to stejné přeučení jako u kNN s jedním sousedem. γ a C se proto volí spolu, obvykle mřížkou hodnot a křížovou validací. Nejlepší nalezené SVM má 88,3 % při stropu 92,2 % — rozdíl padá hlavně na to, že 200 bodů s 8 % chybných štítků kruh přesně neurčí.

6. SVM dnes

Historie. Myšlenka maximálního okraje pochází od Vladimira Vapnika a Alexeje Červoněnkise z 60. let; jádrový trik k ní v roce 1992 přidali Bernhard Boser, Isabelle Guyonová a Vapnik, měkký okraj v roce 1995 Corinna Cortesová a Vapnik.
Síla. Funguje dobře s málo daty a mnoha příznaky (texty, geny), má jasnou geometrickou interpretaci a úloha je konvexní — žádná lokální minima, žádné závislosti na startu.
Slabina. Jádrové SVM potřebuje matici jader n × n: pro milion příkladů bilion čísel. Pro velká data se proto používá lineární SVM, nebo jádro aproximuje.
Proč ho vystřídaly sítě. Jádro je pevně dané předem — člověk musí vybrat, jaká podobnost dává smysl. Neuronové sítě se zobrazení φ učí z dat samy, a s velkým množstvím dat to vychází lépe.

7. Shrnutí

SVM hledá hranici s nejširším okrajem; na oddělitelných datech ji určily 3 podpůrné vektory ze 40 a okraj byl 1,90 (logistická regrese 1,74).
Měkký okraj dovolí porušení za cenu C; s rostoucím C se okraj zúžil z 3,47 na 0,57 a podpůrných vektorů ubylo ze 76 na 18.
Nelineární hranici lze získat zobrazením do většího prostoru příznaků — jen příznaků je rychle moc (ze 784 přes 80 milionů).
Jádrový trik počítá skalární součiny v tom prostoru přímo; na kruhu dalo RBF jádro 88,3 %, lineární 69,0 %.
Parametr γ řídí dosah podobnosti: příliš velké γ (1 000) udělalo ze skoro všech bodů podpůrné vektory a přesnost spadla na 73,3 %.

Chcete si to osahat? Nechte AI agenta pustit SVM s RBF jádrem na kruhových nebo měsícových datech a projít mřížku hodnot C a γ — kde leží nejlepší kombinace?

Máte na to jiný názor? Napište na support@coden-app.com.

SVM a jádrový trik: nejširší hranice a jak ji ohnout

1. Nejširší ulice mezi třídami

Proč je okraj 2/‖w‖

2. Měkký okraj: když se třídy překrývají

3. Když přímka nestačí: zvedni data

4. Jádrový trik

Duální úloha: kde se vzaly skalární součiny

Jak se to učí: SMO

5. Parametr γ: jak daleko sahá podobnost

6. SVM dnes

7. Shrnutí

Agent na vašem počítači, ovládaný z telefonu

Proč je okraj 2/‖`w`‖