Лекція 07 · Опорно-векторні машини та ядрові методи

У лекції 05 ми навчилися проводити межу між класами й оцінювати ймовірність. Сьогодні поставимо жорсткіше питання: серед усіх допустимих меж знайти найнадійнішу — і навчимося робити межу нелінійною, не додаючи жодної нової ознаки вручну.

Зміст лекції

Лекція йде від геометрії однієї прямої до методу, який працює в нескінченновимірному просторі ознак.

1. Максимальний відступ. Гіперплощина, ширина коридору між класами, опорні вектори.
2. М'який відступ. Слекові змінні, hinge-втрата, параметр C і компроміс «ширина проти помилок».
3. Двоїста задача. Змінні $\alpha$, розрідженість розв'язку і головне відкриття: дані входять у задачу лише через попарні скалярні добутки.
4. Ядровий трюк. Простір ознак, ядро як міра схожості, умова Мерсера, каталог ядер.
5. Налаштування ядрової SVM. RBF-ядро, спільний підбір C і gamma, наскрізний приклад на медичних даних.
6. Ядрова регресія. Теорема про представлення, kernel ridge regression і SVR.

Кожен блок відкриває наступний: двоїста задача потрібна не сама по собі, а тому, що саме з неї виростає ядровий трюк.

Чого ви навчитеся

Після цієї лекції ви зможете:

• пояснити, чому серед усіх роздільних прямих SVM обирає ту, що максимізує відстань до найближчих точок;
• зв'язати ширину коридору з нормою вектора ваг і записати задачу hard-SVM;
• пояснити роль слекових змінних і показати, що soft-SVM — це мінімізація hinge-втрати з ridge-регуляризацією;
• передбачити, як зміняться відступ, кількість опорних векторів і якість моделі при зміні C;
• пояснити, чому двоїста задача залежить від даних лише через матрицю попарних скалярних добутків;
• обчислити значення ядра двома способами — напряму й через явне відображення ознак — і переконатися, що вони збігаються;
• обрати ядро під форму даних та підібрати C і gamma перехресною перевіркою;
• назвати ситуації, у яких ядрова SVM непридатна, і пояснити чому.

Два сурогати однієї втрати: місток із лекції 05

У лекції 05 ми вже бачили ключову картину: справжня мета класифікації — мінімізувати нуль-одиничну втрату, тобто частку помилок, але вона розривна й неопукла. Тому мінімізують опуклу верхню оцінку — сурогатну втрату (surrogate loss), і вибір цієї оцінки визначає метод.

Перехресна ентропія веде до логістичної регресії: модель віддає ймовірність і карається за кожну недостатньо впевнену відповідь, навіть правильну. Hinge-втрата веде до методу опорних векторів: щойно точка класифікована правильно й із запасом, штраф стає рівно нулем, і модель перестає нею цікавитися.

Саме з цієї байдужості до «легких» точок виростає весь сьогоднішній метод: у розв'язку залишаються тільки ті спостереження, що лежать біля межі.

	Перехресна ентропія	Hinge-втрата
Формула	$\log (1+e^{-yf})$	$max(0,1-yf)$
Штраф за впевнено правильну точку	малий, але ніколи не нуль	рівно нуль
Що дає модель	ймовірність класу	тільки бік межі
Які точки впливають на розв'язок	усі	лише ті, що ближче за відступ
Метод, який із неї виростає	логістична регресія	опорно-векторна машина

Графік обох функцій поруч із нуль-одиничною втратою — у розділі «Функції втрат, придатні для класифікації» лекції 05.

Матеріали до розділу

• ⚙scikit-learn · SGD convex loss functionsдокументація

  Той самий графік сурогатних втрат, що в лекції 05, із кодом для побудови.

• 📄Bartlett P. та ін. Convexity, Classification, and Risk Boundsстаття

  Формальна відповідь на питання, які саме опуклі сурогати ведуть до правильного класифікатора.

Дані лекції: розміри пелюсток трьох сортів ірисів

Геометрію відступу найкраще видно на двох ознаках, тому основний приклад лекції — класичний набір Iris: 150 квіток, по 50 кожного з трьох сортів, для кожної виміряно довжину й ширину чашолистка та пелюстки в сантиметрах. Беремо дві ознаки — довжину й ширину пелюстки — і передбачаємо сорт.

Ліворуч видно, що сорт setosa відділяється від решти з великим запасом, а versicolor і virginica частково перекриваються. Це дві різні задачі: для першої існує ідеальна пряма, для другої — ні. Спершу розв'яжемо легку, потім навчимося жити з важкою.

Джерело даних: UCI Machine Learning Repository · Iris

Роздільних прямих багато, надійна серед них одна

Візьмімо легку задачу: setosa проти versicolor. Між класами лежить порожня смуга, і будь-яка пряма, що проходить крізь неї, розділяє тренувальні дані без жодної помилки. Ліворуч намальовано шість таких прямих — усі мають однакову нульову похибку на навчанні.

Проте вони не рівноцінні. Пряма, що майже торкається квітки, розсипається від найменшого шуму у вимірюванні: трохи інша пелюстка — і точка опиняється не з того боку. Пряма, що йде серединою смуги, витримує таке зміщення.

Метод опорних векторів (support vector machine, SVM) формалізує цю інтуїцію: серед усіх роздільних гіперплощин обираємо ту, навколо якої залишається найширший вільний коридор. На цих даних його ширина — 1,30 см, а тримається він лише на двох квітках.

Опорно-векторні мережі: стаття 1995 року

Метод у сучасному вигляді описали Корінна Кортес і Володимир Вапнік. Їхня стаття вводить одразу дві речі, які ми розберемо сьогодні: нелінійне відображення у високовимірний простір ознак і розширення методу на дані, які не розділяються без помилок.

"The support-vector network is a new learning machine for two-group classification problems. The machine conceptually implements the following idea: input vectors are non-linearly mapped to a very high-dimension feature space. In this feature space a linear decision surface is constructed." — Cortes C., Vapnik V., 1995

Українською: класифікатор нелінійно переносить входи у простір дуже високої розмірності й будує там лінійну розділяльну поверхню. Уся складність ховається у відображенні, сам класифікатор залишається лінійним — і саме тому задача лишається опуклою.

Джерело: Cortes C., Vapnik V. Support-vector networks. Machine Learning, 20, 273–297 (1995)

Гіперплощина і відстань до неї

Мітки в SVM зручно кодувати як $y\in \{-1,+1\}$: тоді добуток мітки на прогноз одразу каже, чи вгадала модель.

Розділяльна поверхня — гіперплощина (hyperplane): у двох вимірах пряма, у трьох площина, у $D$ вимірах — підпростір розмірності $D-1$. Прогноз залежить лише від знака:

$$f(\mathbf{x})=\mathrm{sign}({\mathbf{w}}^{\mathrm{\top }}\mathbf{x}+w_0),\mathrm{dist}({\mathbf{x}}_0)=\frac{|{\mathbf{w}}^{\mathrm{\top }}{\mathbf{x}}_0+w_0|}{\parallel \mathbf{w}\parallel }$$

Позначення	Значення
$\mathbf{w}$	нормаль до гіперплощини, задає її нахил
$w_0$	зсув: наскільки площина відсунута від початку координат
$y_n\in \{-1,+1\}$	мітка $n$-го спостереження
$|\mathbf{w}|$	довжина вектора ваг, нормує відстань

Формула відстані — це теорема Піфагора: беремо проєкцію точки на напрям $\mathbf{w}$. Слайди EPFL записують її коротше, $|{\mathbf{w}}^{\mathrm{\top }}{\mathbf{x}}_0|$, бо там гіперплощина проходить через початок координат і $\parallel \mathbf{w}\parallel =1$; ми залишаємо зсув, як це роблять усі бібліотеки.

Відступ — це відстань до найближчої точки

Відступ (margin) гіперплощини — найменша відстань від неї до тренувальної точки. Не середня і не типова, а саме найменша: одна квітка, що підійшла впритул, визначає весь відступ, хай би як далеко лежала решта.

На рисунку суцільна лінія — межа рішення, дві штрихові — межі коридору, а обведені точки лежать точно на них. Пересунути суцільну лінію хоч трохи вгору або вниз означає звузити коридор.

$$M(\mathbf{w},w_0)=\underset{n\le N}{min}\frac{|{\mathbf{w}}^{\mathrm{\top }}{\mathbf{x}}_n+w_0|}{\parallel \mathbf{w}\parallel }$$

Правило hard-SVM обирає таку гіперплощину, для якої це мінімальне значення найбільше з можливих. Звідси й назва — класифікатор із максимальним відступом.

Джерело: scikit-learn · SVM: Maximum margin separating hyperplane

Максимізація відступу — це мінімізація норми ваг

Максимізувати мінімум відстаней незручно. Але задача має приховану симетрію: якщо помножити $\mathbf{w}$ і $w_0$ на будь-яке додатне число, гіперплощина не зміниться. Скористаємося цією свободою й зафіксуємо масштаб так, щоб найближчі точки давали рівно одиницю. Тоді задача стає простою й опуклою:

$$\underset{\mathbf{w},w_0}{min}\frac{1}{2}\parallel \mathbf{w}{\parallel }^2\text{за умови }{y}_n({\mathbf{w}}^{\mathrm{\top }}{\mathbf{x}}_n+w_0)\ge 1\text{для всіх }n$$

За такої нормалізації відступ дорівнює $M=1/\parallel \mathbf{w}\parallel$, а ширина всього коридору — $2/\parallel \mathbf{w}\parallel$. Чим коротший вектор ваг, тим ширший коридор: «максимізувати відступ» і «мінімізувати норму» — це буквально одна задача.

Числовий приклад із попереднього рисунка: для setosa проти versicolor оптимальний $\parallel \mathbf{w}\parallel =1,53$, звідси коридор $2/1,53=1,30$ см. Задача опукла й має єдиний розв'язок — на відміну від нейронних мереж, тут не буває невдалої ініціалізації.

Матеріали до розділу

• 📄Cortes C., Vapnik V. Support-Vector Networks (1995)PDF

  Оригінальна стаття, з якої почалися SVM.

• ▶MIT 6.034 · Learning: Support Vector Machinesвідео

  Лекція Патріка Вінстона з повним виведенням двоїстої задачі на дошці.

Розв'язок тримається лише на опорних векторах

Опорні вектори (support vectors) — це точки, що лежать на межах коридору або порушують їх. Решта спостережень у розв'язок не входять зовсім, і це легко перевірити експериментом.

Ліворуч SVM навчено на всіх 100 квітках, праворуч — лише на двох опорних векторах, які знайшла перша модель. Межа збіглася: максимальна різниця коефіцієнтів становить $7,3\cdot {10}^{-9}$, зсуву — $2,1\cdot {10}^{-8}$, тобто на рівні похибки округлення. Дев'яносто вісім викинутих квіток не змінили нічого.

Практичний наслідок подвійний. З одного боку, модель компактна: щоб робити прогнози, достатньо зберігати опорні вектори. З іншого — вона вразлива: помилка у вимірюванні однієї прикордонної точки зсуває всю межу, тоді як груба помилка в далекій точці не робить нічого.

Реальні класи перекриваються: м'який відступ

Друга пара сортів, versicolor проти virginica, ідеальної прямої не має: у зоні перекриття лежать квітки обох класів. Жорстка вимога $y_n({\mathbf{w}}^{\mathrm{\top }}{\mathbf{x}}_n+w_0)\ge 1$ для всіх точок тут просто не має розв'язку — задача несумісна.

Soft-SVM послаблює вимогу: кожній точці дозволено порушити межу коридору, але за плату. На рисунку обведено 23 квітки, які залізли в коридор або перейшли на чужий бік; п'ять із них класифіковано неправильно. Решта 77 лежать за коридором і на межу не впливають.

Зверніть увагу: порушників 23, а помилок лише 5. Більшість «порушників» класифіковано правильно — вони просто підійшли до межі ближче, ніж на одиницю відступу. Це і є ціна ширшого коридору.

Слекові змінні вимірюють глибину порушення

Формально до кожного обмеження додається власна слекова змінна (slack variable) ${\xi }_n\ge 0$ — наскільки саме точка порушила вимогу. Сума порушень входить у цільову функцію зі штрафом:

$$\underset{\mathbf{w},w_0,\mathit{\xi }}{min}\frac{\lambda }{2}\parallel \mathbf{w}{\parallel }^2+\frac{1}{N}\sum _{n=1}^N{\xi }_n\text{за умови }{y}_n({\mathbf{w}}^{\mathrm{\top }}{\mathbf{x}}_n+w_0)\ge 1-{\xi }_n,{\xi }_n\ge 0$$

Значення ${\xi }_n$ читається геометрично: ${\xi }_n=0$ — точка чесно за коридором; $0<{\xi }_n\le 1$ — точка всередині коридору, але з правильного боку; ${\xi }_n>1$ — точка перейшла межу рішення, тобто класифікована помилково. У сантиметрах глибина порушення дорівнює ${\xi }_n/\parallel \mathbf{w}\parallel$.

Для рисунка вище сума всіх слеків становить 13,6 при ста спостереженнях. Параметр $\lambda$ визначає, наскільки дорого обходиться ця сума; до нього ми ще повернемося.

Hinge-втрата обнуляється, щойно точка впевнено правильна

Слекові змінні можна виключити з задачі. При фіксованих вагах оптимальне значення ${\xi }_n$ обчислюється явно: це $[1-{\eta }_n{]}_{+}$, де ${\eta }_n=y_n({\mathbf{w}}^{\mathrm{\top }}{\mathbf{x}}_n+w_0)$ — функційний відступ (functional margin) точки. Підставивши це назад, отримуємо задачу без обмежень.

На графіку добре видно, чим hinge відрізняється від сусідів. Квадратична втрата має мінімум у точці $\eta =1$ і знову зростає праворуч від неї — карає навіть «надто правильні» точки. Логістична спадає, але ніколи не досягає нуля, тому кожне спостереження назавжди залишається в розв'язку. Hinge при $\eta \ge 1$ дорівнює точно нулю: при $\eta =2$ логістична втрата ще становить 0,127, квадратична — 1,0, а hinge — рівно 0.

Soft-SVM — це hinge-втрата плюс ridge-регуляризація

Після підстановки слеків задача набуває форми, знайомої з лекції 03: середня втрата плюс штраф за довжину вектора ваг.

$$\underset{\mathbf{w},w_0}{min}\frac{1}{N}\sum _{n=1}^N[1-y_n({\mathbf{w}}^{\mathrm{\top }}{\mathbf{x}}_n+w_0){]}_{+}+\frac{\lambda }{2}\parallel \mathbf{w}{\parallel }^2,[z{]}_{+}=max\{0,z\}$$

Тобто SVM — це не окремий алгоритм із власною філософією, а звичайна мінімізація емпіричного ризику, у якій обрано конкретну функцію втрат. Регуляризатор тут виконує подвійну роботу: він і стримує ваги від розбігання, і, оскільки $M=1/\parallel \mathbf{w}\parallel$, безпосередньо розширює коридор.

Одна практична незручність: hinge має злам у точці $\eta =1$ і в ній не диференційовна. Тому первинну задачу розв'язують субградієнтним методом, а не звичайним градієнтним спуском.

Параметр C — та сама задача в іншій параметризації

Бібліотеки записують soft-SVM інакше: штраф ставлять не перед нормою ваг, а перед сумою порушень.

$$\underset{\mathbf{w},w_0,\mathit{\xi }}{min}\frac{1}{2}\parallel \mathbf{w}{\parallel }^2+C\sum _{n=1}^N{\xi }_n$$

Це та сама задача: домноживши форму з попереднього розділу на $1/\lambda$, отримуємо $C=1/(\lambda N)$. Саме таке означення дає Bishop у PRML, §7.1. Отже, велике C — слабка регуляризація, вузький коридор і мало порушень; мале C — сильна регуляризація, широкий коридор і багато порушників.

На рисунку — той самий набір даних при C=1 і C=100. Праворуч коридор помітно вужчий, а обведених опорних векторів менше: модель майже не дозволяє порушень і притискає межу до найближчих точок.

Джерело: scikit-learn · Plot the support vectors in LinearSVC

Вплив C на реальних даних: діагностика пухлин

Перевіримо це на другому наборі лекції. Breast Cancer Wisconsin (Diagnostic): 569 пункційних біопсій, 30 числових ознак, обчислених із зображення (радіус, текстура, периметр, площа ядер клітин та інші), передбачаємо діагноз — доброякісна пухлина чи злоякісна. Навчальна частина — 398 спостережень, ознаки стандартизовано, ядро лінійне.

Ліва панель показує обіцяну залежність без винятків: при C=0,001 у розв'язку 195 опорних векторів із 398, при C=1000 — лише 24. Права панель додає те, чого не видно з геометрії: точність на навчальній вибірці зростає до одиниці, а на перехресній перевірці спершу піднімається до 0,985 при C≈0,32, а потім падає до 0,937. Це класичне перенавчання — надто вузький коридор запам'ятовує шум.

Джерело даних: UCI · Breast Cancer Wisconsin (Diagnostic)

Дисбаланс класів зсуває межу до меншого класу

Ще одна пастка, помітна саме в геометрії відступу. Якщо один клас представлено сотнями точок, а другий — десятками, сумарний штраф $C\sum {\xi }_n$ автоматично більший з боку великого класу. Оптимізатору вигідно посунути межу вбік меншого класу: так він порушить обмеження кількох рідкісних точок замість багатьох частих.

На рисунку близько тисячі точок великого класу і сотня — рідкісного. Чорна лінія — звичайна SVM: вона проходить крізь рідкісний клас і віддає більшу його частину сусідові. Червона — та сама модель із class_weight="balanced", яка множить C для кожного класу на величину, обернену до його частоти. Її межа зсунута вглиб великого класу, і рідкісні точки нарешті опиняються на своєму боці.

Це та сама проблема, що й у лекції 05 при виборі порога, тільки розв'язується вона не після навчання, а всередині цільової функції.

Джерело: scikit-learn · SVM: Separating hyperplane for unbalanced classes

Код: лінійна SVM з нуля на субградієнтному спуску

Двадцять п'ять рядків numpy, щоб було видно: всередині немає нічого, крім формули з попередніх розділів.

import numpy as np
from sklearn.datasets import load_iris

iris = load_iris()
X = iris.data[iris.target < 2][:, [2, 3]]  # довжина і ширина пелюстки
y = np.where(iris.target[iris.target < 2] == 1, 1.0, -1.0)
X = np.c_[X, np.ones(len(X))]  # стовпець для зсуву w0
lam = 0.01


def objective(w):  # hinge + ridge
    eta = y * (X @ w)
    return np.mean(np.maximum(0.0, 1.0 - eta)) + lam / 2 * w[:2] @ w[:2]


def subgradient(w):  # злам у точці eta = 1
    active = (y * (X @ w) < 1).astype(float)
    g = -(X * (active * y)[:, None]).mean(axis=0)
    g[:2] += lam * w[:2]
    return g


w = np.zeros(3)
for step in range(2001):
    if step % 500 == 0:
        print(f"крок {step:4d}   цільова функція {objective(w):.4f}")
    w -= 0.05 * subgradient(w)

Вивід код запущено, вивід не редагувався

крок    0   цільова функція 1.0000
крок  500   цільова функція 0.0193
крок 1000   цільова функція 0.0132
крок 1500   цільова функція 0.0117
крок 2000   цільова функція 0.0117

На що дивитися: цільова функція падає з 1,0 до 0,0117 і після 1500 кроків уже не змінюється — спуск зійшовся.

Знайдений напрям $\mathbf{w}=(\mathrm{0,994};\mathrm{0,839})$. Якщо окремо навчити SVC(kernel="linear", C=1/(lam*len(y))) і порівняти напрями, косинус між ними дорівнює 0,991 — тобто наші двадцять п'ять рядків знайшли практично ту саму гіперплощину, що й бібліотека.

Двоїста задача: ті самі ваги через змінні альфа

Первинну задачу можна переписати відносно нових змінних ${\alpha }_n\in [0,1]$ — по одній на кожне спостереження. Ключ до перетворення простий: $[z{]}_{+}=\underset{\alpha \in [0,1]}{max}\alpha z$, після чого мінімум і максимум міняються місцями (це законно, бо функція опукла по $\mathbf{w}$ й угнута по $\mathit{\alpha }$).

$$\underset{\mathit{\alpha }\in [0,1{]}^N}{max}\frac{1}{N}{\mathit{\alpha }}^{\mathrm{\top }}\mathbf{1}-\frac{1}{2\lambda N^2}{\mathit{\alpha }}^{\mathrm{\top }}\mathbf{Y}\underset{\mathbf{K}}{\underbrace{\mathbf{X}{\mathbf{X}}^{\mathrm{\top }}}}\mathbf{Y}\mathit{\alpha },\mathbf{w}(\mathit{\alpha })=\frac{1}{\lambda N}\sum _{n=1}^N{\alpha }_n{y}_n{\mathbf{x}}_n$$

Тут $\mathbf{Y}=\mathrm{diag}(\mathbf{y})$, а $\mathbf{K}=\mathbf{X}{\mathbf{X}}^{\mathrm{\top }}$ — матриця розміру $N\times N$, у якій на перетині рядка $i$ та стовпця $j$ стоїть скалярний добуток ${\mathbf{x}}_i^{\mathrm{\top }}{\mathbf{x}}_j$. Запис вище відповідає моделі без окремого нерегуляризованого зсуву; щойно такий зсув з'являється, мінімізація по ньому додає до задачі рівність $\sum _n{\alpha }_n{y}_n=0$.

Прочитайте останню формулу уважно: дані входять у задачу тільки через $\mathbf{K}$. Кількість ознак $D$ у ній не з'являється взагалі. Це і є двері, крізь які за кілька розділів увійде ядровий трюк.

Значення альфа розказує, де лежить точка

Оптимальне ${\alpha }_n$ повністю визначається положенням точки відносно коридору, і навпаки.

Положення точки ${\mathbf{x}}_n$	$1-y_n({\mathbf{w}}^{\mathrm{\top }}{\mathbf{x}}_n+w_0)$	${\alpha }_n$
правильний бік, за коридором	$<0$	$0$
точно на межі коридору	$=0$	будь-яке з $[0,1]$
усередині коридору або на чужому боці	$>0$	$1$

Опорні вектори — це рівно точки з ${\alpha }_n>0$. Оскільки $\mathbf{w}$ є їхньою зваженою сумою, точки з ${\alpha }_n=0$ у формулі просто зникають — саме це ми й побачили в експерименті з двома квітками.

Двоїста форма зручна ще й обчислювально: вона гладка й угнута, тому її розв'язують квадратичними солверами або координатним підйомом, без проблем зі зламом hinge. А розрідженість $\mathit{\alpha }$ означає, що готова модель зберігає лише невелику частку навчальних даних.

Ознаки, яких немає в даних, можна дорахувати

Поки що межа завжди була прямою. Але прямою вона є лише в тому просторі, де ми працюємо, — а простір можна змінити.

Ліворуч — одновимірні дані, розмічені за правилом «близько до нуля — один клас, далеко — інший». Жоден поріг на прямій їх не розділить: обидва боки нуля змішані. Праворуч до кожної точки дописано другу координату $x^2$. Точки лягли на параболу, і тепер їх ідеально розділяє горизонтальна пряма $x^2=16$.

$$\varphi (x)=(x,x^2):\mathbb{R}\to {\mathbb{R}}^2$$

Функцію $\varphi$ називають відображенням у простір ознак (feature map). Головне: задача не стала складнішою — вона залишилася лінійною, просто в іншому просторі. Нелінійна межа у вихідному просторі — це лінійна межа у просторі ознак.

Той самий прийом у двох вимірах: підйом угору

Той самий трюк працює й на реальніших формах. Ліворуч — 220 точок, згенерованих як два концентричні кільця (make_circles). Класи розділені ідеально, але не прямою: лінійна SVM дає 59 % правильних відповідей, тобто ледве краще за монетку.

Праворуч до кожної точки дописано третю координату ${\varphi }_3=x_1^2+x_2^2$, тобто квадрат відстані до центра. Внутрішнє ядро опустилося вниз, зовнішнє кільце піднялося вгору, і між ними тепер проходить звичайна горизонтальна площина ${\varphi }_3=0,54$. Класифікатор у просторі ознак лінійний; коли ми проєктуємо його межу назад у площину, вона перетворюється на коло.

Проблема лише одна, і вона обчислювальна: у справжніх задачах потрібне відображення набагато більшої розмірності, і будувати його явно надто дорого.

Ядровий трюк: скалярний добуток без побудови ознак

Тут і спрацьовує головна ідея. Двоїста задача потребує не самих векторів ознак, а лише їхніх попарних скалярних добутків. Отже, якщо вміти рахувати добуток $\varphi (\mathbf{x}{)}^{\mathrm{\top }}\varphi ({\mathbf{x}}^{\prime })$ безпосередньо, саме $\varphi$ будувати не треба.

Ядро (kernel) — це функція двох аргументів, що повертає таке саме число, як скалярний добуток у просторі ознак: $\kappa (\mathbf{x},{\mathbf{x}}^{\prime })=\varphi (\mathbf{x}{)}^{\mathrm{\top }}\varphi ({\mathbf{x}}^{\prime })$. Перевіримо на прикладі $\mathbf{x}=(1,2)$, ${\mathbf{x}}^{\prime }=(3,1)$ і квадратичному ядрі.

import numpy as np

x, xp = np.array([1, 2]), np.array([3, 1])
k_direct = (x @ xp) ** 2  # одна дія у вихідному просторі


def phi(v):  # явне відображення в R^3
    return np.array([v[0] ** 2, np.sqrt(2) * v[0] * v[1], v[1] ** 2])


k_explicit = phi(x) @ phi(xp)  # через явне відображення в R^3

print("ядро напряму      :", k_direct)
print("phi(x), phi(x')   :", np.round(phi(x), 3), np.round(phi(xp), 3))
print("скалярний добуток :", k_explicit)

Вивід код запущено, вивід не редагувався

ядро напряму      : 25
phi(x), phi(x')   : [1.    2.828 4.   ] [9.    4.243 1.   ]
скалярний добуток : 25.0

На що дивитися: обидва шляхи дають 25: ядро обчислює той самий скалярний добуток, не будуючи тривимірних векторів.

Ліворуч — один скалярний добуток і піднесення до квадрата; праворуч — побудова двох тривимірних векторів. Для степеня $p$ і $D$ ознак різниця стає катастрофічною: $O(D)$ проти $O(D^p)$.

Матеріали до розділу

• 🎓Cornell CS4780 · Kernelsкурс

  Конспект із доведенням, чому ядро можна обчислити, не будуючи простір ознак.

Матриця ядра — це таблиця схожості всіх з усіма

Ядро зручно уявляти як міру схожості. Матриця $\mathbf{K}$ розміру $N\times N$ збирає значення $\kappa ({\mathbf{x}}_i,{\mathbf{x}}_j)$ для всіх пар спостережень — це і є єдине, що алгоритм знає про дані.

На рисунку обидві матриці побудовані на всіх 150 квітках Iris за чотирма стандартизованими ознаками; спостереження впорядковано за сортом, тому блоки на діагоналі — це «свої зі своїми». Ліворуч лінійне ядро: значення можуть бути від'ємними, і зчитати структуру важче. Праворуч RBF-ядро: значення лежать у $[0,1]$, три блоки видно неозброєним оком. Середня схожість усередині сорту становить 0,66, а між setosa і virginica — лише 0,02.

Саме така блокова структура й дозволяє класифікатору працювати, ніколи не бачачи самих координат: достатньо знати, хто на кого схожий.

Не будь-яка функція схожості є ядром

Ядром може бути не всяка симетрична функція. Критерій дає умова Мерсера (Mercer's condition): функція $\kappa$ є ядром тоді й лише тоді, коли вона симетрична й будь-яка складена з неї матриця $\mathbf{K}$ додатно напіввизначена.

Контрприклад корисно тримати в голові. Візьмімо «схожість» $\kappa (\mathbf{x},{\mathbf{x}}^{\prime })=\parallel \mathbf{x}-{\mathbf{x}}^{\prime }\parallel$. Для двох точок на відстані $d$ матриця має вигляд $(\begin{array}{cc}0& d\\ d& 0\end{array})$, її власні значення дорівнюють $+d$ і $-d$, тобто вона не є додатно напіввизначеною. Ядром ця функція не є, і жодного $\varphi$ для неї не існує.

Нові ядра будують із наявних: якщо ${\kappa }_1$ і ${\kappa }_2$ — ядра, то ядрами будуть і $\alpha {\kappa }_1+\beta {\kappa }_2$ при $\alpha ,\beta \ge 0$, і добуток ${\kappa }_1\cdot {\kappa }_2$. Відображення для суми — конкатенація $[\sqrt{\alpha }{\varphi }_1;\sqrt{\beta }{\varphi }_2]$, для добутку — усі попарні добутки координат.

Каталог ядер і простори, які вони задають

Три ядра покривають переважну більшість практичних задач.

Ядро	Формула	Простір ознак
лінійне	${\mathbf{x}}^{\mathrm{\top }}{\mathbf{x}}^{\prime }$	вихідний, розмірність $D$
поліноміальне степеня $p$	$(1+{\mathbf{x}}^{\mathrm{\top }}{\mathbf{x}}^{\prime }{)}^p$	усі одночлени до степеня $p$, розмірність $(\genfrac{}{}{0ex}{}{D+p}{p})$
RBF (гаусове)	$\exp (-{\displaystyle \frac{|\mathbf{x}-{\mathbf{x}}^{\prime }{|}^2}{2{\sigma }^2}})$	нескінченновимірний

Поліноміальне ядро при $D=10$ і $p=3$ відповідає простору з 286 ознак, при $p=5$ — з 3003; рахувати їх явно не потрібно жодного разу. RBF відповідає нескінченновимірному відображенню, яке отримують розкладом експоненти в ряд Тейлора, — і його одне обчислення все одно коштує $O(D)$.

Ядра існують і для нечислових даних: string kernel вимірює схожість рядків за спільними підпослідовностями, і SVM працює з текстом, не перетворюючи його на вектор.

RBF-ядро: параметр gamma задає радіус впливу

RBF — ядро за замовчуванням у більшості бібліотек, тому його параметр варто розуміти точно. У scikit-learn замість ${\sigma }^2$ пишуть gamma, і зв'язок такий: $\gamma =1/(2{\sigma }^2)$, тобто $\kappa (\mathbf{x},{\mathbf{x}}^{\prime })=\exp (-\gamma \parallel \mathbf{x}-{\mathbf{x}}^{\prime }{\parallel }^2)$.

Графік показує, як швидко спадає схожість із відстанню. При $\gamma =0,1$ дві точки на відстані 1,0 усе ще схожі на 0,90 — кожне спостереження впливає далеко навколо себе, і межа виходить гладкою. При $\gamma =10$ та сама схожість дорівнює $4,5\cdot {10}^{-5}$ — точка «бачить» лише найближчих сусідів, і межа розпадається на острівці навколо окремих спостережень.

Звідси правило: завелике gamma — це перенавчання, замале — недонавчання. Значення gamma="scale" у scikit-learn обчислюється як $1/(D\cdot \mathrm{Var}[X])$ і є розумною відправною точкою, а не оптимумом.

Матеріали до розділу

• ⚙scikit-learn · RBF SVM parametersдокументація

  Той самий експеримент на сітці C × gamma з поясненням, як читати теплову карту.

• 📄Hofmann T., Schölkopf B., Smola A. Kernel Methods in Machine Learningстаття

  Оглядова стаття про ядрові методи: від теореми Мерсера до практичних рецептів.

Що робить gamma — і що з цього виходить

Ліворуч саме ядро: як швидко спадає схожість двох точок із відстанню. Посередині — карта якості по всій сітці C × gamma, клітинки клікабельні. Праворуч — межа рішень на тих самих двох півмісяцях, що в коді лекції.

схожість κ(r) = exp(−γ r²)

карта якості на сітці C × gamma

межа рішень на двох півмісяцях

gamma = 5C = 1

0,007схожість на відстані 1,0

90опорних векторів із 195

0,938точність на навчальних

0,905точність на відкладених

Поставте C = 1 і γ = 0,1: схожість на відстані 1,0 дорівнює 0,90 — кожна точка впливає далеко навколо себе, межа виходить майже прямою, і модель недонавчається: 0,877 на навчальних і 0,848 на відкладених. Тепер γ = 50: схожість падає практично до нуля, межа розпадається на острівці навколо окремих спостережень, навчальна точність злітає до 0,990, а відкладена лишається 0,886 — перенавчання видно просто в цих двох числах. Далі зафіксуйте γ = 0,5 і посуньте C: він керує не радіусом, а ціною порушення відступу, тому змінює межу інакше — і кількість опорних векторів разом із нею, від 116 при C = 0,1 до 38 при C = 100. Саме тому ці два параметри підбирають спільно, сіткою, а не по черзі.

Карта посередині показує це відразу для всіх двадцяти чотирьох пар. Світлі клітинки не збираються в одну точку, а лягають діагоналлю: C = 100 з gamma = 0,1 дає 0,933, C = 10 з gamma = 0,5 — найкращі 0,943, C = 1 з gamma = 0,5 — знову 0,933. Уздовж цієї смуги добуток C·gamma тримається приблизно сталим: більший радіус впливу компенсується суворішим штрафом. Клітинка C = 1, gamma = 0,5 — це рівно той рядок, який друкує код розділу про порівняння ядер: gamma="scale" на стандартизованих даних дорівнює 1/(2·1), тобто 0,5, і віджет дає ті самі 0,933 при 66 опорних векторах із 195. Зелений кружок стоїть на 0,943, але дві сусідні клітинки дають 0,933, а цілий стовпчик при gamma = 1 — по 0,924, і різниця між ними менша за розкид між фолдами. Практичний висновок той самий, що в тексті розділу: сітку беруть логарифмічну, а всередині світлої смуги за третій знак не воюють. Клацніть по кутах карти: лівий верхній (мале gamma, велике C) дає майже пряму межу з 53 опорними векторами, правий нижній (велике gamma, мале C) — 0,495, тобто чисте вгадування, і всі 195 навчальних точок стають опорними: модель запам'ятала кожну й не навчилася нічого.

Ядро задає форму межі, алгоритм не змінюється

У двоїстій задачі досить замінити ${\mathbf{x}}_i^{\mathrm{\top }}{\mathbf{x}}_j$ на $\kappa ({\mathbf{x}}_i,{\mathbf{x}}_j)$ — і той самий солвер починає будувати нелінійну межу. Прогноз теж записується лише через ядро:

$$f(\mathbf{x})=\mathrm{sign}(\frac{1}{\lambda N}\sum _{n=1}^N{\alpha }_n{y}_n\kappa (\mathbf{x},{\mathbf{x}}_n)+w_0)$$

Сума йде тільки по опорних векторах, бо в решти ${\alpha }_n=0$. Формула лінійна у просторі ознак і нелінійна у вихідному — це той самий об'єкт, побачений із двох боків.

Рисунок показує чотири ядра на одних і тих самих даних. Лінійне дає пряму, поліноміальне — криву відповідного порядку, RBF — гладку межу довільної форми, сигмоїдне — химерну ламану, яка ілюструє, що не всяке ядро підходить будь-яким даним.

Джерело: scikit-learn · Plot classification boundaries with different SVM Kernels

Код: лінійне ядро проти RBF на двох півмісяцях

Порівняємо ядра там, де правильна відповідь відома заздалегідь: make_moons генерує два переплетені півмісяці, які прямою не розділити принципово.

from sklearn.datasets import make_moons
from sklearn.model_selection import train_test_split
from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import StandardScaler
from sklearn.svm import SVC

X, y = make_moons(n_samples=300, noise=0.22, random_state=3)
X_tr, X_te, y_tr, y_te = train_test_split(
    X, y, test_size=0.35, stratify=y, random_state=3
)

for kernel in ("linear", "rbf"):
    model = make_pipeline(StandardScaler(), SVC(kernel=kernel, C=1.0, gamma="scale"))
    model.fit(X_tr, y_tr)
    print(
        f"{kernel:>6}: точність на тесті {model.score(X_te, y_te):.3f}, "
        f"опорних векторів {model[-1].n_support_.sum():3d} із {len(y_tr)}"
    )

Вивід код запущено, вивід не редагувався

linear: точність на тесті 0.829, опорних векторів  71 із 195
   rbf: точність на тесті 0.933, опорних векторів  66 із 195

На що дивитися: RBF-ядро піднімає точність з 0,829 до 0,933, і опорних векторів йому знадобилося навіть менше — 66 проти 71.

Зміна одного рядка дала плюс десять відсоткових пунктів.

Джерело: scikit-learn · SVC

Результат на півмісяцях: пряма проти гладкої межі

Тепер подивимося на те саме очима. Ліворуч лінійне ядро чесно робить усе, що може: одна пряма, 82,9 % правильних відповідей і систематична помилка на «хвостах» обох півмісяців. Праворуч RBF-ядро огинає форму даних і дає 93,3 % на тих самих 105 тестових точках.

Помилки, що залишилися, зосереджені у вузькій зоні перетину півмісяців, де шум noise=0.22 фізично змішав класи. Це важливий орієнтир: ядро прибирає обмеження методу, але не прибирає шум у даних. Модель, яка розділила б і цю зону, просто запам'ятала б окремі точки.

Чотири варіанти SVM на одному наборі ірисів

Повернімося до Iris, тепер уже з трьома класами (SVM робить це схемою «один проти одного», навчаючи класифікатор на кожну пару класів). Чотири панелі показують той самий набір і той самий алгоритм із різними налаштуваннями.

SVC(kernel="linear") і LinearSVC дають схожі, але не тотожні межі: перший розв'язує двоїсту задачу зі стандартною hinge-втратою, другий — первинну з квадратичною hinge і регуляризує ще й зсув. RBF-ядро дає плавно вигнуті межі, поліноміальне третього степеня — жорсткіші, майже кутові.

Практичний висновок: «SVM» — це не одна модель, а сімейство, і різниця між його членами буває більшою, ніж різниця між SVM і логістичною регресією.

Джерело: scikit-learn · Plot different SVM classifiers in the iris dataset

C і gamma працюють у парі, а не поодинці

Два параметри ядрової SVM не можна підбирати незалежно, бо вони частково компенсують один одного: жорсткіше ядро можна пригасити сильнішою регуляризацією.

Сітка показує це наочно. У верхньому ряду C замале — регуляризація давить модель незалежно від gamma, і межа майже плоска. У правому стовпці gamma завелике — модель обгортає кожну точку окремим острівцем, і це вже перенавчання, яке жодне C не рятує.

Робочі моделі зосереджені в середині діапазону, і жоден із двох параметрів не має «правильного» значення сам по собі: важлива тільки їхня комбінація. Саме тому підбирають їх разом, сіткою, а не по черзі.

Джерело: scikit-learn · RBF SVM parameters

Карта якості показує діагональ, а не єдину точку

Той самий перебір, але замість меж рішення — точність перехресної перевірки для кожної пари значень. По горизонталі відкладено gamma, по вертикалі C, обидві шкали логарифмічні.

Світлі клітинки утворюються не в одній точці, а витягуються в діагональ: мале gamma з великим C дає приблизно ту саму якість, що велике gamma з малим C. Два праві стовпці — суцільно темні: при gamma порядку сотні модель обгортає кожну точку окремим острівцем і не узагальнює взагалі, і жодне C цього не виправляє.

Звідси два практичні правила. По-перше, шукати параметри слід логарифмічною сіткою — крок «×10», а не «+1». По-друге, всередині світлої смуги немає сенсу боротися за третій знак після коми: різниця між сусідніми клітинками менша за розкид між фолдами перехресної перевірки.

Джерело: scikit-learn · RBF SVM parameters, карта якості

Код: підбір C і gamma на медичних даних

Повний робочий приклад на Breast Cancer: стандартизація всередині конвеєра, сітка по двох параметрах, п'ятикратна перехресна перевірка.

from sklearn.datasets import load_breast_cancer
from sklearn.model_selection import GridSearchCV, train_test_split
from sklearn.pipeline import Pipeline
from sklearn.preprocessing import StandardScaler
from sklearn.svm import SVC

data = load_breast_cancer()
X_tr, X_te, y_tr, y_te = train_test_split(
    data.data, data.target, test_size=0.3, stratify=data.target, random_state=0
)

pipe = Pipeline([("scaler", StandardScaler()), ("svc", SVC(kernel="rbf"))])
grid = {"svc__C": [0.1, 1, 10, 100], "svc__gamma": [0.001, 0.01, 0.1, "scale"]}

search = GridSearchCV(pipe, grid, cv=5, scoring="accuracy", n_jobs=-1)
search.fit(X_tr, y_tr)

best = search.best_params_
print(f"найкращі параметри: C = {best['svc__C']}, gamma = {best['svc__gamma']}")
print("перехресна перевірка:", round(search.best_score_, 3))
print("на тесті:", round(search.score(X_te, y_te), 3))
print("опорних векторів:", search.best_estimator_["svc"].n_support_.sum())

Вивід код запущено, вивід не редагувався

найкращі параметри: C = 100, gamma = 0.001
перехресна перевірка: 0.985
на тесті: 0.953
опорних векторів: 40

На що дивитися: крос-валідація дає 0,985, тест — 0,953, а все рішення тримається на 40 опорних векторах із 398 навчальних зразків.

Стандартизація стоїть усередині Pipeline не для краси: обчислена на всій вибірці, вона пропустила б інформацію про тест у навчання.

Результат на медичних даних і межі можливого

Ліва панель порівнює чотири конфігурації на тих самих 171 тестовій пухлині. Головний висновок несподіваний для тих, хто чекав чудес від ядра: стандартизація дала більше, ніж вибір ядра. Без неї RBF провалюється до 0,906, бо площа ядра клітини вимірюється сотнями, а гладкість контуру — сотими, і в евклідовій відстані чути лише першу ознаку.

Права панель показує розподіл значень розв'язувальної функції на тесті. Дві вертикальні штрихові лінії — межі коридору; всередині нього лежать саме ті пухлини, які стали опорними векторами. Розділення чисте: більшість спостережень далеко від нуля, і лише кілька потрапили в зону сумніву.

Підбір гіперпараметрів підняв перехресну перевірку до 0,985, але на тесті дав ті самі 0,953, що й налаштування за замовчуванням. На цих даних модель уже близька до стелі, і чесно це визнати корисніше, ніж полірувати сітку.

Теорема про представлення відкриває ядра для регресії

Ядровий трюк не є винаходом саме для SVM: він працює для будь-якої моделі з ridge-регуляризацією.

"For any loss function ℓ, and any minimizer w* of the regularized empirical risk, there exists α* ∈ ℝᴺ such that w* = Xᵀα*." — теорема про представлення (representer theorem), EPFL CS-433, лекція 07a

Українською: оптимальні ваги завжди є лінійною комбінацією навчальних точок, бо ортогональна до них компонента лише збільшує норму, не змінюючи прогнозів. Отже, будь-яку таку модель можна переписати через $\mathit{\alpha }$ й підставити ядро — так з'являються kernel ridge regression, kernel PCA і kernel SVM. Розв'язок гребеневої регресії з лекції 03 має два еквівалентні записи:

$${\mathbf{w}}^{\ast }=\frac{1}{N}(\frac{1}{N}{\mathbf{X}}^{\mathrm{\top }}\mathbf{X}+\lambda {\mathbf{I}}_D{)}^{-1}{\mathbf{X}}^{\mathrm{\top }}\mathbf{y}=\frac{1}{N}{\mathbf{X}}^{\mathrm{\top }}(\frac{1}{N}\mathbf{X}{\mathbf{X}}^{\mathrm{\top }}+\lambda {\mathbf{I}}_N{)}^{-1}\mathbf{y}$$

Перша коштує $O(D^3+N{D}^2)$, друга — $O(N^3+D{N}^2)$, і саме друга цінна: дані входять у неї через $\mathbf{X}{\mathbf{X}}^{\mathrm{\top }}$, тож добуток можна замінити ядром, а прогноз стає зваженою сумою схожостей $\hat{y}(\mathbf{x})=\sum _n{\alpha }_n^{\ast }\kappa (\mathbf{x},{\mathbf{x}}_n)$.

KRR і SVR: одна крива, різна ціна

Той самий прийом дає два різні методи регресії. Kernel ridge regression мінімізує квадратичну втрату й тому використовує всі точки. Support vector regression (SVR) замінює її на $\epsilon$-нечутливу втрату: похибки, менші за $\epsilon$, не караються зовсім, і розв'язок виходить розрідженим.

На рисунку обидві моделі навчено на зашумленій синусоїді: криві практично збігаються, але червоні кружки — опорні вектори SVR, і їх помітно менше, ніж точок. На нашому запуску з 400 точок KRR дала MSE 0,171 за 0,24 с, SVR — 0,177 за 0,35 с, використавши 95 точок. Обмін чіткий: KRR навчається швидше, SVR дає компактнішу модель, бо вартість її прогнозу зростає з кількістю опорних векторів, а не всієї вибірки.

Джерело: scikit-learn · Comparison of kernel ridge regression and SVR

Наближення ядра рятує на великих вибірках

Матриця ядра має розмір $N\times N$, і це головна межа масштабування: для ста тисяч спостережень вона займе близько 80 ГБ пам'яті, а розв'язання задачі коштує приблизно $O(N^3)$.

Вихід парадоксальний: побудувати відображення $\varphi$ явно, але наближено, і після цього застосувати звичайну лінійну SVM, яка масштабується лінійно за $N$. Метод Нюстрема відбирає підмножину точок і будує на ній низькорангове наближення матриці ядра; метод випадкових ознак Фур'є використовує ймовірнісне подання RBF-ядра.

На рисунку три моделі на наборі рукописних цифр у проєкції на дві головні компоненти: точне RBF-ядро та два наближення зі ста компонентами. Межі рішень майже не відрізняються.

Джерело: scikit-learn · Explicit feature map approximation for RBF kernels

HAR: на семи тисячах спостережень наближення ще не потрібне

Перш ніж заміняти ядро наближенням, варто перевірити, чи вже треба. Візьмімо Human Activity Recognition — набір із лабораторної: 10 299 записів з акселерометра смартфона, 561 ознака, шість дій.

# продовження: спирається на попередні блоки лекції
import time

from sklearn.datasets import fetch_openml
from sklearn.kernel_approximation import Nystroem
from sklearn.svm import LinearSVC

har = fetch_openml(data_id=1478, as_frame=True, parser="auto")
Xh, yh = har.data.to_numpy(float), har.target.to_numpy()
Xh_tr, Xh_te, yh_tr, yh_te = train_test_split(
    Xh, yh, test_size=0.3, stratify=yh, random_state=0
)
sc_h = StandardScaler().fit(Xh_tr)
Zh_tr, Zh_te = sc_h.transform(Xh_tr), sc_h.transform(Xh_te)


def seconds_to_fit(model, X, y, repeats=3):
    """Найкращий із кількох замірів: так фонове навантаження менше спотворює час."""
    times = []
    for _ in range(repeats):
        t0 = time.perf_counter()
        model.fit(X, y)
        times.append(time.perf_counter() - t0)
    return min(times)


print(f"{'модель':16s} {'навчання, с':>11} {'точність':>9}")
for tag, model in [
    ("точне RBF-ядро", SVC(kernel="rbf", C=10)),
    (
        "Нюстрем 300",
        make_pipeline(
            Nystroem(n_components=300, random_state=0), LinearSVC(C=1, max_iter=5000)
        ),
    ),
    (
        "Нюстрем 2000",
        make_pipeline(
            Nystroem(n_components=2000, random_state=0), LinearSVC(C=1, max_iter=5000)
        ),
    ),
]:
    sec = seconds_to_fit(model, Zh_tr, yh_tr)
    print(f"{tag:16s} {sec:11.1f} {model.score(Zh_te, yh_te):9.4f}")

Вивід код запущено, вивід не редагувався

модель           навчання, с  точність
точне RBF-ядро           1.9    0.9848
Нюстрем 300              0.8    0.9618
Нюстрем 2000             6.5    0.9767

На що дивитися: на семи тисячах записів точне ядро найточніше, а наближення виграє в часі лише зі 300 компонентами — і платить за це точністю.

Результат несподіваний для тих, хто чув правило «ядро не масштабується»: на 7209 навчальних записах точне ядро навчається за неповні дві секунди й дає найкращу точність, 0,985. Наближення зі 300 компонентами вдвічі швидше, але втрачає два відсоткові пункти; із 2000 компонентами воно вже повільніше за точне ядро й усе одно поступається йому.

Висновок практичний: наближення — не «краща версія» ядра, а обмін точності на час, і братися за нього має сенс лише тоді, коли час справді став проблемою. Сім тисяч спостережень — ще не той випадок.

Квадратична стіна: де саме ламається точне ядро

Щоб побачити межу, потрібен набір, на якому вона настає: MiniBooNE, 130 064 події детектора нейтрино, 50 ознак. Навчаємо на підвибірках зростаючого розміру.

# продовження: спирається на попередні блоки лекції
import time

import numpy as np

mb = fetch_openml(data_id=41150, as_frame=False, parser="auto")
Xm, ym = np.asarray(mb.data, float), np.asarray(mb.target)
Xm_tr, Xm_te, ym_tr, ym_te = train_test_split(
    Xm, ym, test_size=20000, stratify=ym, random_state=0
)
sc_m = StandardScaler().fit(Xm_tr[:20000])
Zm_te = sc_m.transform(Xm_te)
rng = np.random.default_rng(0)

print(
    f"{'N':>6} {'ядро, с':>8} {'точність ядра':>14} {'Нюстрем':>8} {'матриця, ГБ':>12}"
)
for N in (2000, 5000, 10000, 20000):
    idx = rng.choice(len(Xm_tr), N, replace=False)
    Z, yy = sc_m.transform(Xm_tr[idx]), ym_tr[idx]
    exact = SVC(kernel="rbf", C=1)
    t_exact = seconds_to_fit(exact, Z, yy)
    appr = make_pipeline(
        Nystroem(n_components=500, random_state=0), LinearSVC(C=1, max_iter=3000)
    ).fit(Z, yy)
    print(
        f"{N:6d} {t_exact:8.1f} {exact.score(Zm_te, ym_te):14.4f} "
        f"{appr.score(Zm_te, ym_te):8.4f} {N * N * 8 / 1e9:12.1f}"
    )

Вивід код запущено, вивід не редагувався

     N  ядро, с  точність ядра  Нюстрем  матриця, ГБ
  2000      0.1         0.7194   0.8766          0.0
  5000      0.2         0.8619   0.8813          0.2
 10000      0.9         0.8793   0.8877          0.8
 20000      3.6         0.8824   0.8913          3.2

На що дивитися: дивіться на стовпці часу й пам'яті: вибірка зросла вдесятеро, час ядра — у десятки разів, а матриця ядра на 20 000 зразках займає вже 3,2 ГБ.

Час точного ядра росте так: 0,1 с при двох тисячах, 0,2 при п'яти, 0,9 при десяти, 3,6 при двадцяти. Вибірка зросла вдесятеро — час у тридцять шість разів. На рисунку той самий вимір продовжено до 40 000 і показано в подвійному логарифмічному масштабі: нахил дорівнює 1,89, тобто обіцяна квадратична залежність не процитована, а виміряна. Наближення на тому ж відрізку дорожчає помітно повільніше й при цьому не програє в точності: 0,895 проти 0,887 на найбільшій вибірці.

Абсолютні секунди залежать від машини, тож порівнювати варто нахили. Що від машини не залежить — пам'ять: матриця ядра при 40 000 спостережень зайняла б 12,8 ГБ, при 130 000 — 135 ГБ. Бібліотека не тримає її цілком, а перераховує через кеш, і саме тому час росте квадратично, а не впирається в пам'ять одразу.

Обмеження методу опорних векторів

Метод має чіткі межі застосовності, і краще знати їх заздалегідь.

Вартість зростає як куб від кількості спостережень. Матриця ядра $N\times N$ робить ядрову SVM непридатною для сотень тисяч рядків. Виходи: лінійне ядро, наближення ядра або зовсім інший клас моделей.

Обов'язкова стандартизація. Відступ вимірюється евклідовою відстанню, тому ознака з більшим числовим розмахом заглушує решту. Ми бачили це на медичних даних: 0,906 проти 0,953 на тих самих ознаках.

Два гіперпараметри без замовчувань. C і gamma треба підбирати перехресною перевіркою на кожному новому наборі даних; універсально правильних значень не існує.

Немає ймовірностей. SVM віддає відстань до межі, а не ймовірність класу. Перетворення (калібрування Платта) можливе, але потребує додаткової перехресної перевірки й помітно уповільнює навчання.

Втрачається інтерпретованість. У лінійному ядрі коефіцієнти ще можна прочитати; у RBF модель — це набір опорних векторів і схожостей, і пояснити конкретне рішення стає важко.

Підсумок лекції

Максимальний відступ — це вибір найнадійнішої з нескінченної кількості роздільних гіперплощин. Задача «максимізувати відступ» тотожна задачі «мінімізувати $\parallel \mathbf{w}{\parallel }^2$ за обмежень $y_n({\mathbf{w}}^{\mathrm{\top }}{\mathbf{x}}_n+w_0)\ge 1$», а ширина коридору дорівнює $2/\parallel \mathbf{w}\parallel$.

Soft-SVM — це ERM з hinge-втратою і ridge-регуляризацією. Слекові змінні вимірюють глибину порушення, а параметр C = 1/(λN) керує компромісом між шириною коридору й кількістю допущених помилок.

Розв'язок розріджений. Модель зберігає лише опорні вектори; викидання решти даних не змінює межі — ми перевірили це з точністю до ${10}^{-8}$.

Двоїста задача залежить від даних лише через матрицю попарних скалярних добутків — і саме ця властивість відкриває ядровий трюк.

Ядро дає нелінійність задарма. Заміна ${\mathbf{x}}^{\mathrm{\top }}{\mathbf{x}}^{\prime }$ на $\kappa (\mathbf{x},{\mathbf{x}}^{\prime })$ переносить лінійний класифікатор у високовимірний простір ознак, ніколи його не будуючи; той самий прийом працює для регресії, PCA та інших моделей із ridge-регуляризацією.

Джерела й додаткові матеріали

Курси

• EPFL CS-433 — лекції 06a (SVM) і 07a (ядра)
• UBC CPSC 340 — лекція 21
• Stanford CS229 — розділ 5

Статті та підручники

• Cortes C., Vapnik V. Support-vector networks (1995)
• Schölkopf B., Herbrich R., Smola A. A generalized representer theorem. COLT, 2001
• Bishop C. Pattern Recognition and Machine Learning — розділи 6–7
• Hastie T. та ін. The Elements of Statistical Learning — розділ 12

Документація й дані

• scikit-learn · Support Vector Machines
• Iris, UCI · Breast Cancer, UCI