Ядра

Заметка о методе опорных векторов закончилась двумя наблюдениями. Двойственная задача и полученный из неё классификатор используют обучающие точки только через скалярные произведения $\langle x_i, x_j\rangle$, а оценка через зазор не зависит от размерности. Линейный классификатор на исходных признаках по-прежнему проводит гиперплоскость, и два концентрических кольца ему не по силам. В этой заметке исходные признаки заменяются более богатым представлением $\phi(x)$, а скалярное произведение — ядром (kernel) $k(x, z) = \langle \phi(x), \phi(z)\rangle$, которое можно вычислить, ни разу не построив $\phi(x)$. Та же задача квадратичного программирования тогда проводит криволинейные границы, а та же идея превращает гребневую регрессию в гибкий непараметрический регрессор. Платить приходится числом обучающих точек вместо числа признаков, и в конце заметки показано, как платить меньше.

Обозначения. Обучающие точки $x_1, \dots, x_n \in \mathbb R^d$ с целевыми значениями $y_i$. Отображение признаков (feature map) $\phi: \mathbb R^d \to \mathcal H$ переводит точку в вектор пространства $\mathcal H$ со скалярным произведением, возможно бесконечномерного. Ядро — функция $k(x, z)$; матрица Грама (Gram matrix) $K$ — матрица $n \times n$ с элементами $K_{ij} = k(x_i, x_j)$, а $k(x) = (k(x_1, x), \dots, k(x_n, x))^\top$ собирает значения ядра между новой точкой и обучающими. $\sigma$ — ширина RBF-ядра, $\lambda$ — коэффициент гребневого штрафа.

Отображения признаков#

Линейная модель становится нелинейной по $x$, когда она линейна по нелинейным признакам $x$. Точки на прямой, у которых один класс в середине, нельзя разделить одним порогом, но после $\phi(x) = (x, x^2)$ они лежат на параболе, где их разделяет прямая:

Рисунок

Отображение признаков делает классы линейно разделимыми

Прямая $w_1 x + w_2 x^2 + b = 0$ на поднятой плоскости — это квадратное неравенство по $x$, которое выполняется между двумя порогами. В общем случае добавляют все произведения признаков до некоторой степени $p$. Число одночленов степени не выше $p$ от $d$ переменных равно $\binom{d + p}{p}$: при $d = 100$ и $p = 3$ это $176\,851$. Выписать эти признаки для каждой обучающей точки и подобрать вес для каждого быстро становится узким местом.

Ядерный трюк в двойственной задаче#

Самим признакам SVM не нужен. Его двойственная задача с $\phi(x_i)$ вместо $x_i$ выглядит так:

$$\begin{aligned} &\max_{\alpha}\ \sum_i \alpha_i - \tfrac12 \sum_{i,j} \alpha_i \alpha_j y_i y_j\, k(x_i, x_j)\\ &\text{subject to}\ \ 0 \le \alpha_i \le C,\quad \sum_i \alpha_i y_i = 0, \end{aligned}$$

а классификатор равен $f(x) = \sum_i \alpha_i y_i\, k(x_i, x) + b$, где $b = y_i - \sum_j \alpha_j y_j k(x_j, x_i)$ для любого опорного вектора на краю полосы. И то и другое требует только $k(x, z) = \langle \phi(x), \phi(z)\rangle$. Замена каждого скалярного произведения в линейном методе ядром называется ядерным трюком (kernel trick; Boser, Guyon and Vapnik, 1992); он работает для любого метода, который можно записать через скалярные произведения, от SVM и гребневой регрессии до PCA и $k$-средних.

Выигрыш дают ядра, которые дёшево вычислять, хотя $\phi$ велико. Для $x \in \mathbb R^2$ и $\phi(x) = (x_1^2,\ \sqrt2\, x_1 x_2,\ x_2^2)$

$$\langle \phi(x), \phi(z)\rangle = x_1^2 z_1^2 + 2 x_1 x_2 z_1 z_2 + x_2^2 z_2^2 = (x_1 z_1 + x_2 z_2)^2 = \langle x, z\rangle^2 .$$

Разобранный пример. Для $x = (1, 2)$ и $z = (3, 1)$: $\phi(x) = (1, 2\sqrt2, 4)$, $\phi(z) = (9, 3\sqrt2, 1)$ и $\langle\phi(x), \phi(z)\rangle = 9 + 12 + 4 = 25 = (1 \cdot 3 + 2 \cdot 1)^2$. Ядро стоит одного скалярного произведения в $\mathbb R^2$ и возведения в квадрат; в $d$ измерениях $\langle x, z\rangle^2$ стоит $d$ умножений против $d^2$ для явных признаков. У отображения признаков с рисунка, $\phi(x) = (x, x^2)$, ядро равно $k(x, z) = xz + x^2 z^2$.

Какие функции являются ядрами#

Не всякая функция сходства — скалярное произведение в каком-то пространстве. Если $k(x, z) = \langle\phi(x), \phi(z)\rangle$, то для любых точек $x_1, \dots, x_m$ и любых вещественных чисел $c_1, \dots, c_m$

$$\sum_{i,j} c_i c_j\, k(x_i, x_j) = \Big\lVert \sum_i c_i \phi(x_i)\Big\rVert^2 \ge 0 .$$

Значит, матрица Грама ядра на любом конечном множестве точек симметрична и положительно полуопределена. Верно и обратное: симметричная функция, все матрицы Грама которой положительно полуопределены, — это скалярное произведение после некоторого отображения признаков в гильбертово пространство, гильбертово пространство с воспроизводящим ядром (reproducing kernel Hilbert space, RKHS) функции $k$ (Aronszajn, 1950; Shalev-Shwartz and Ben-David, 2014, лемма 16.2). Такие функции называются положительно полуопределёнными ядрами (positive semidefinite kernels), и именно их может использовать ядерный трюк. Теорема Мерсера (Mercer’s theorem) явно даёт отображение признаков для непрерывного ядра на компактной области: $k(x, z) = \sum_j \lambda_j e_j(x) e_j(z)$ с собственными значениями $\lambda_j \ge 0$ и ортонормированными собственными функциями $e_j$, так что $\phi(x) = (\sqrt{\lambda_j}\, e_j(x))_j$ (Rasmussen and Williams, 2006, §4.3).

Это условие знакомо по теории вероятностей. Матрица положительно полуопределена ровно тогда, когда она является ковариационной матрицей некоторого случайного вектора, потому что $\sum_{i,j} c_i c_j \operatorname{Cov}(Z_i, Z_j) = \operatorname{Var}(\sum_i c_i Z_i) \ge 0$ (см. ковариацию). Точно так же $k$ — положительно полуопределённое ядро ровно тогда, когда оно является ковариационной функцией случайной функции: $k(x, z) = \operatorname{Cov}(F(x), F(z))$ для гауссовского процесса $F$. Ядро говорит, насколько сильно коррелированы значения неизвестной функции в двух входах; это прочтение вернётся в ядерной гребневой регрессии.

Проверять определение напрямую часто трудно, поэтому ядра обычно строят из более простых по правилам, сохраняющим положительную полуопределённость. Если $k_1$ и $k_2$ — ядра, то ядрами являются и:

• $k_1 + k_2$ и $c\, k_1$ при $c \gt 0$: суммы и положительные кратные положительно полуопределённых матриц положительно полуопределены;
• $k_1 k_2$: поэлементное произведение положительно полуопределённых матриц положительно полуопределено (теорема Шура о произведении), или, в терминах признаков, $\phi_1 \otimes \phi_2$;
• $g(x) g(z)$ для любой вещественной функции $g$: матрица Грама ранга один $gg^\top$;
• $k_1(\psi(x), \psi(z))$ для любого отображения $\psi$;
• поточечный предел ядер, потому что каждое неравенство $\sum c_i c_j k(x_i, x_j) \ge 0$ сохраняется в пределе.

Поэтому многочлены от ядра с неотрицательными коэффициентами и его экспонента (предел таких многочленов) тоже являются ядрами (Bishop, 2006, §6.2).

Некоторые естественные меры сходства этому не удовлетворяют. У расстояния $k(x, z) = \lVert x - z\rVert$ на диагонали матрицы Грама стоят нули, поэтому сумма собственных значений равна следу, 0, и если не все точки совпадают, одно из них отрицательно. Для двух точек 0 и 1 матрица Грама равна $\begin{pmatrix} 0 & 1 \\ 1 & 0\end{pmatrix}$ с собственными значениями $\pm 1$. На 50 случайных точках плоскости её наименьшее собственное значение равно $-27.5$; «сигмоидное ядро» $\tanh(\langle x, z\rangle + 1)$ даёт $-6.26$, а у RBF-ядра оно остаётся равным $0$ с точностью до округления. С такой функцией двойственная задача SVM перестаёт быть вогнутой, и её решение теряет смысл.

Распространённые ядра: полиномиальное и RBF#

Полиномиальное ядро (polynomial kernel) $k(x, z) = (\langle x, z\rangle + c)^p$ с $c \ge 0$ раскладывается по формуле бинома в $\sum_{j=0}^p \binom{p}{j} c^{p-j} \langle x, z\rangle^j$ — неотрицательную комбинацию ядер $\langle x, z\rangle^j$. Его признаки — все одночлены степени не выше $p$, причём одночлен $x_1^{a_1} \cdots x_d^{a_d}$ степени $j = a_1 + \dots + a_d$ взят с весом $\sqrt{\binom{p}{j} \binom{j}{a_1, \dots, a_d} c^{p - j}}$, где мультиномиальный коэффициент возникает при раскрытии $\langle x, z\rangle^j$; $c$ управляет тем, насколько низкие степени весят по сравнению с высокими.

RBF-ядро (гауссовское, radial basis function kernel) равно

$$k(x, z) = \exp\Big(-\frac{\lVert x - z\rVert^2}{2\sigma^2}\Big) = e^{-\lVert x\rVert^2/(2\sigma^2)}\, e^{-\lVert z\rVert^2/(2\sigma^2)}\, e^{\langle x, z\rangle/\sigma^2} .$$

Первые два множителя имеют вид $g(x) g(z)$, а последний — экспонента ядра, так что по правилам выше это ядро. Его ряд Тейлора содержит $\langle x, z\rangle^j$ для каждого $j$, поэтому пространство признаков бесконечномерно: никакое явное $\phi$ не удалось бы сохранить, а $k$ стоит одного расстояния. У каждой точки $\lVert\phi(x)\rVert^2 = k(x, x) = 1$, а квадрат расстояния между двумя точками в пространстве признаков равен $k(x, x) + k(z, z) - 2k(x, z) = 2 - 2k(x, z)$: RBF-ядро — это мера сходства, убывающая с расстоянием на масштабе $\sigma$. Классификатор $f(x) = \sum_i \alpha_i y_i\, k(x_i, x) + b$ с этим ядром — взвешенное голосование опорных векторов, в котором ближние весят больше всего, гладкий родственник метода ближайших соседей с весами, подобранными максимизацией зазора.

Ширина ядра как смещение и разброс. При большом $\sigma$ каждая обучающая точка влияет на всё пространство, и решающая функция почти линейна; при малом $\sigma$ каждая точка влияет лишь на ближайшую окрестность, и функция может обогнуть каждую обучающую точку. На двух зашумлённых полумесяцах (600 точек, шум 0.3, половина для теста, $C = 1$; scikit-learn записывает ядро как $e^{-\gamma\lVert x - z\rVert^2}$, так что $\gamma = 1/(2\sigma^2)$):

$\gamma$	$\sigma$	доля правильных на обучении	доля правильных на тесте	опорных векторов
0.01	7.07	0.843	0.827	198
0.1	2.24	0.883	0.850	125
1	0.71	0.937	0.880	79
10	0.22	0.940	0.883	126
100	0.07	0.990	0.857	256
1000	0.02	1.000	0.653	299

Линейный SVM достигает $0.853$. С очень широким ядром RBF-SVM не лучше прямой; при $\sigma \approx 0.2$–$0.7$ он выигрывает три пункта; с очень узким ядром он запоминает обучающую выборку (доля правильных ответов (accuracy) 1, опорными векторами становятся 299 из 300 точек) и падает до $0.653$ на тесте. Число опорных векторов минимально там, где доля правильных ответов на тесте максимальна. $\sigma$ и $C$ подбирают вместе кросс-валидацией по логарифмическим сеткам, предварительно стандартизовав признаки, чтобы одно $\sigma$ подходило им всем.

Теорема о представителе#

Почему решение SVM имеет вид $\sum_i \alpha_i y_i \phi(x_i)$, с одним коэффициентом на обучающую точку, даже когда $\phi$ бесконечномерно? Причина не связана именно с кусочно-линейной функцией потерь. Рассмотрим любую регуляризованную задачу

$$\min_{w}\ \sum_{i=1}^n L\big(y_i,\ \langle w, \phi(x_i)\rangle\big) + \lambda \lVert w\rVert^2 ,\qquad \lambda \gt 0 .$$

Разложим $w = w_\parallel + w_\perp$, где $w_\parallel$ лежит в линейной оболочке $\phi(x_1), \dots, \phi(x_n)$, а $w_\perp$ ортогонален им всем. Предсказания на обучающих точках зависят только от $w_\parallel$, потому что $\langle w_\perp, \phi(x_i)\rangle = 0$, а $\lVert w\rVert^2 = \lVert w_\parallel\rVert^2 + \lVert w_\perp\rVert^2$. Отбрасывание $w_\perp$ сохраняет функцию потерь и строго уменьшает штраф, если $w_\perp \ne 0$, поэтому у любого минимума $w_\perp = 0$:

$$w = \sum_{i=1}^n \alpha_i \phi(x_i), \qquad f(x) = \langle w, \phi(x)\rangle = \sum_{i=1}^n \alpha_i\, k(x_i, x) .$$

Это теорема о представителе (representer theorem; Kimeldorf and Wahba, 1971; Schölkopf, Herbrich and Smola, 2001, которые допускают в качестве штрафа любую строго возрастающую функцию от $\lVert w\rVert$; Shalev-Shwartz and Ben-David, 2014, теорема 16.1). Она превращает поиск в бесконечномерном пространстве в поиск $n$ коэффициентов и выполняется для любой функции потерь: квадратичной, логистической, кусочно-линейной. После подстановки этого представления $\lVert w\rVert^2 = \sum_{i,j} \alpha_i \alpha_j k(x_i, x_j) = \alpha^\top K \alpha$, а вектор предсказаний на обучающей выборке равен $K\alpha$.

Ядерная гребневая регрессия#

С квадратичной функцией потерь задача становится гребневой регрессией в пространстве признаков, $\min_w \lVert y - \Phi w\rVert^2 + \lambda\lVert w\rVert^2$, где строки $\Phi$ — это $\phi(x_i)^\top$. Её решение из заметки о регуляризации можно переписать с помощью тождества $\Phi^\top(\Phi\Phi^\top + \lambda I) = (\Phi^\top\Phi + \lambda I)\Phi^\top$: умножив его слева на $(\Phi^\top\Phi + \lambda I)^{-1}$ и справа на $(\Phi\Phi^\top + \lambda I)^{-1}$ (обе матрицы обратимы при $\lambda \gt 0$), получаем

$$w = (\Phi^\top \Phi + \lambda I)^{-1}\Phi^\top y = \Phi^\top (\Phi\Phi^\top + \lambda I)^{-1} y .$$

Левая форма обращает матрицу размера пространства признаков, правая — матрицу размера $n \times n$, причём $\Phi\Phi^\top = K$. Значит, $w = \sum_i \alpha_i \phi(x_i)$ с

$$\alpha = (K + \lambda I)^{-1} y, \qquad f(x) = k(x)^\top (K + \lambda I)^{-1} y ,$$

— это предсказание ядерной гребневой регрессии (kernel ridge regression), в точности в той форме, которую обещала теорема о представителе (Bishop, 2006, §6.1).

Разобранный пример. Две обучающие точки $x = 0$ и $x = 1$ с целевыми значениями $1$ и $2$, RBF-ядро с $\sigma = 1$ и $\lambda = 0.1$. Ядро между точками равно $e^{-1/2} = 0.6065$, поэтому

$$K + \lambda I = \begin{pmatrix} 1.1 & 0.6065 \\ 0.6065 & 1.1 \end{pmatrix}, \qquad \alpha = (K + \lambda I)^{-1}\begin{pmatrix} 1 \\ 2\end{pmatrix} = \begin{pmatrix} -0.134 \\ 1.892\end{pmatrix} .$$

В точке $x = 0.5$ оба значения ядра равны $e^{-1/8} = 0.8825$ и $f(0.5) = 0.8825 \cdot (-0.134 + 1.892) = 1.551$. В точке $x = 3$ значения ядра равны $e^{-4.5} = 0.011$ и $e^{-2} = 0.135$, и $f(3) = 0.255$: вдали от данных RBF-регрессор возвращается к 0, своему априорному среднему, каким бы ни был тренд. В самих обучающих точках подгонка равна $f(0) = 1.013$ и $f(1) = 1.811$, а не целевым значениям $1$ и $2$: при $\lambda \gt 0$ подгонка сглаживает, а не интерполирует. Точная интерполяция требует $\lambda = 0$ и обратимой $K$. В любом случае экстраполяции нет.

Рисунок

Ширина RBF-ядра как сложность модели

Ширина ядра и здесь обменивает смещение на разброс. Эффективное число параметров гребневой подгонки, $\mathrm{df} = \operatorname{tr}\big(K(K + \lambda I)^{-1}\big)$, показывает, сколько направлений использует подгонка (Hastie, Tibshirani and Friedman, 2009, §3.4.1); оно близко к $n$, когда подгонка интерполирует, и мало, когда она жёсткая. Для 30 точек рисунка:

$\sigma$	1	0.5	0.3	0.2	0.1	0.05	0.02	0.01
df	2.36	3.31	4.43	5.77	9.25	14.69	21.61	24.26
ошибка на обучении	0.231	0.098	0.039	0.031	0.024	0.019	0.006	0.004
средний квадрат расстояния до истинной кривой	0.181	0.051	0.007	0.015	0.031	0.060	0.116	0.197

Ошибка на обучении монотонно падает по мере сужения ядра; средний квадрат расстояния до истинной кривой имеет U-образную форму разложения на смещение и разброс с минимумом около $\sigma = 0.3$.

Байесовское прочтение. Для конечномерного отображения признаков зададим на весах гауссовское априорное распределение $w \sim N(0, \tau^2 I)$, а на целевых значениях — гауссовский шум с дисперсией $s^2$. Тогда $F(x) = \langle w, \phi(x)\rangle$ — гауссовский процесс с ковариацией $\tau^2 k(x, z)$. У RBF-ядра пространство признаков бесконечномерно, и изотропное гауссовское априорное распределение на бесконечном числе весов — лишь формальный предел этой картины; тогда модель задают напрямую: $F$ — гауссовский процесс с ковариацией $\tau^2 k(x, z)$. В обоих случаях апостериорное среднее $F(x)$ при данных следует из формулы условного распределения многомерной гауссианы: $\tau^2 k(x)^\top(\tau^2 K + s^2 I)^{-1} y = k(x)^\top (K + \lambda I)^{-1} y$ с $\lambda = s^2/\tau^2$. Ядерная гребневая регрессия — это апостериорное среднее регрессии на гауссовских процессах, так же как гребневая регрессия — MAP-оценка при гауссовском априорном распределении (Rasmussen and Williams, 2006, §2.2 и §6.2). Гауссовский процесс добавляет то, чего не хватает гребневому взгляду: апостериорную дисперсию, планку погрешности в каждой точке $x$.

Стоимость и случайные признаки Фурье#

Ядерные методы обменивают размерность признаков на число примеров. Вычисление матрицы Грама стоит $O(n^2 d)$ времени и $O(n^2)$ памяти, решение $(K + \lambda I)\alpha = y$ стоит $O(n^3)$, а солверы SVM на практике масштабируются между $O(n^2)$ и $O(n^3)$. Каждое предсказание стоит одного вычисления ядра на опорный вектор или обучающую точку. При $n = 100\,000$ одна матрица Грама содержит $10^{10}$ элементов, 80 ГБ в двойной точности. Поэтому ядерные методы господствуют на малых и средних данных и проигрывают линейным моделям, деревьям и нейросетям на больших.

Средство Rahimi and Recht (2007) — вернуться к явным признакам, но немногочисленным и случайным. Оно опирается на теорему Бохнера (Bochner’s theorem): непрерывное инвариантное к сдвигу ядро $k(x, z) = k(x - z)$ с $k(0) = 1$ положительно полуопределено тогда и только тогда, когда оно является характеристической функцией некоторого распределения вероятностей $p$,

$$k(x - z) = \mathbb E_{\omega \sim p}\, e^{i\langle \omega, x - z\rangle} = \mathbb E_{\omega \sim p} \cos\langle \omega, x - z\rangle$$

(Rahimi and Recht, §3, теорема 1; вторая форма верна, потому что $k$ вещественно, так что мнимая часть в среднем равна нулю). Характеристические функции встречались в заметке о математическом ожидании. Для RBF-ядра $p$ — гауссиана $N(0, \sigma^{-2} I)$, характеристическая функция которой равна $e^{-\lVert t\rVert^2/(2\sigma^2)}$. Теперь сгенерируем $\omega_1, \dots, \omega_D$ из $p$ и $b_1, \dots, b_D$ равномерно из $[0, 2\pi]$ и положим

$$z(x) = \sqrt{2/D}\,\big(\cos(\langle\omega_1, x\rangle + b_1), \dots, \cos(\langle\omega_D, x\rangle + b_D)\big) .$$

По формуле $2\cos A \cos B = \cos(A - B) + \cos(A + B)$ каждое слагаемое $\langle z(x), z(x')\rangle$ равно $\tfrac1D\big(\cos\langle\omega_j, x - x'\rangle + \cos(\langle\omega_j, x + x'\rangle + 2b_j)\big)$, а второй косинус в среднем по равномерному $b_j$ равен нулю. Значит, $\langle z(x), z(x')\rangle$ — среднее $D$ независимых слагаемых со средним $k(x - x')$: оценка методом Монте-Карло ядра. Каждое слагаемое лежит в $[-2, 2]$, и неравенство Хёфдинга даёт $P(\lvert\langle z(x), z(x')\rangle - k(x, x')\rvert \ge \varepsilon) \le 2e^{-D\varepsilon^2/8}$ для каждой пары; Rahimi and Recht (утверждение 1) распространяют оценку сразу на все пары из ограниченного множества ценой множителя, растущего с $d$.

Ошибка убывает как $1/\sqrt D$. На 300 точках в $\mathbb R^5$ наибольшая ошибка по всей матрице Грама $300 \times 300$ равна $1.12$, $0.34$, $0.10$ и $0.035$ при $D = 10$, $100$, $1\,000$ и $10\,000$ — примерно в $\sqrt{10}$ раз на каждом шаге. Любой линейный метод, обученный на $z(x)$, тогда приближает ядерный метод, а стоит это $O(nDd)$ на признаки и $O(nD^2)$ на гребневую подгонку — линейно по $n$. На полумесяцах линейный SVM на $D = 10$ случайных признаках уже достигает доли правильных ответов на тесте точного RBF-SVM с тем же $\gamma = 1$, $0.88$.

Ядра сравнивают распределения#

Дополнительный материал: ядерные вложения средних и максимальное расхождение средних, которыми пользуется курс генеративных моделей. Остальная часть заметки на него не опирается.

Среднее признаков распределения, $\mu_P = \mathbb E_{X \sim P}\phi(X)$, сводит $P$ к одной точке пространства признаков, а расстояние между двумя такими точками снова вычисляется одним ядром:

$$\lVert \mu_P - \mu_Q\rVert^2 = \mathbb E\, k(X, X') + \mathbb E\, k(Y, Y') - 2\,\mathbb E\, k(X, Y), \qquad X, X' \sim P,\ Y, Y' \sim Q .$$

Это квадрат максимального среднего расхождения (maximum mean discrepancy, MMD). С полиномиальным ядром оно сравнивает моменты до степени ядра; с RBF-ядром оно равно нулю, только когда $P = Q$ (Gretton et al., 2012). Курс генеративных моделей использует его, чтобы сравнивать сгенерированные изображения с настоящими: Kernel Inception Distance — это та же величина с кубическим полиномиальным ядром на признаках сети.

Что изменилось#

	Линейный SVM и гребневая регрессия	Ядерные методы
Решающая функция	$\langle w, x\rangle + b$, гиперплоскость	$\sum_i \alpha_i k(x_i, x) + b$, криволинейная по $x$
Параметры	$d$ весов	$n$ коэффициентов, по одному на обучающую точку (теорема о представителе)
Как входят данные	векторы признаков	матрица Грама $K_{ij} = k(x_i, x_j)$
Пространство признаков	$\mathbb R^d$	любое пространство со скалярным произведением, для RBF-ядра бесконечномерное
Ручка сложности	$C$ или $\lambda$	$C$ или $\lambda$ плюс ядро и его ширина
Стоимость обучения	линейная по $n$	$O(n^2)$ памяти, $O(n^2)$–$O(n^3)$ времени; случайные признаки возвращают её к линейной

Ограничения#

• Квадратичная память, кубическое время. Точные ядерные методы не масштабируются дальше нескольких десятков тысяч примеров; приближения (случайные признаки, метод Нистрёма) жертвуют точностью ради скорости.
• Ядро — это выбор модели. Оно задаёт, какие входы считаются похожими. RBF-ядро после стандартизации обращается со всеми направлениями одинаково; при многих нерелевантных признаках в расстояниях доминирует шум, как в проклятии размерности из заметки о методе ближайших соседей.
• Гиперпараметры. Ширина ядра и $C$ или $\lambda$ взаимодействуют, и их нужно подбирать совместно; таблица для полумесяцев показывает долю правильных ответов на тесте от $0.65$ до $0.88$ в зависимости от одного только $\sigma$.
• Нет экстраполяции с локальными ядрами. RBF-подгонка вдали от данных возвращается к нулю, как показал разобранный пример.
• Фиксированные признаки. Отображение признаков выбирают до того, как увидеть данные. Нейросети вместо этого выучивают признаки, что и позволяет им масштабироваться на изображения и тексты.

Что нужно запомнить#

• Ядро — это скалярное произведение после отображения признаков, $k(x, z) = \langle\phi(x), \phi(z)\rangle$. Любой метод, записанный через скалярные произведения, например двойственная задача SVM, работает с $k$ вместо $\langle x, z\rangle$ без построения $\phi$.
• $k$ — допустимое ядро тогда и только тогда, когда все его матрицы Грама симметричны и положительно полуопределены; равносильно, $k$ — ковариационная функция. Суммы, положительные кратные, произведения, пределы и $g(x)g(z)$ сохраняют это свойство; у расстояний и $\tanh$ его нет.
• Полиномиальное ядро: все одночлены до степени $p$. RBF-ядро: бесконечномерные признаки, сходство на масштабе $\sigma$; большое $\sigma$ ведёт к недообучению, малое $\sigma$ — к переобучению.
• Теорема о представителе: для любой функции потерь плюс $\lambda\lVert w\rVert^2$ минимум имеет вид $\sum_i \alpha_i \phi(x_i)$. Ядерная гребневая регрессия: $\alpha = (K + \lambda I)^{-1}y$, $f(x) = k(x)^\top \alpha$ — апостериорное среднее гауссовского процесса.
• Точные ядерные методы стоят $O(n^2)$ памяти и до $O(n^3)$ времени. Случайные признаки Фурье оценивают инвариантное к сдвигу ядро методом Монте-Карло с ошибкой $O(1/\sqrt D)$ и делают обучение линейным по $n$.

Код#

Полиномиальное ядро как скалярное произведение, матрицы Грама, которые положительно полуопределены и которые нет, ядерная гребневая регрессия вручную, ширина RBF-ядра на полумесяцах и случайные признаки Фурье:

import numpy as np, math
from sklearn.datasets import make_moons
from sklearn.model_selection import train_test_split
from sklearn.svm import SVC, LinearSVC
from sklearn.kernel_ridge import KernelRidge
from sklearn.kernel_approximation import RBFSampler

# ядро — это скалярное произведение после отображения признаков: (x.z)^2 при phi(x) = (x1^2, sqrt(2) x1 x2, x2^2)
x, z = np.array([1.0, 2.0]), np.array([3.0, 1.0])
phi = lambda v: np.array([v[0]**2, math.sqrt(2) * v[0] * v[1], v[1]**2])
print((x @ z)**2, phi(x) @ phi(z), math.comb(100 + 3, 3))   # 25.0 25.0 176851: одночлены степени <= 3 от 100 признаков

# какие функции являются ядрами: наименьшее собственное значение матрицы Грама на 50 случайных точках
rng = np.random.default_rng(0)
P = rng.normal(size=(50, 2)); D2 = ((P[:, None] - P[None]) ** 2).sum(-1)
for name, G in (('rbf', np.exp(-D2 / 2)), ('distance', np.sqrt(D2)), ('tanh', np.tanh(P @ P.T + 1))):
    print(name, f'{np.linalg.eigvalsh(G).min():.3g}')
# rbf 4.24e-10 | distance -27.5 | tanh -6.26: положительно полуопределена только матрица Грама RBF-ядра

# ядерная гребневая регрессия вручную: x = (0, 1), y = (1, 2), RBF с sigma = 1, lambda = 0.1
X = np.array([[0.0], [1.0]]); y = np.array([1.0, 2.0])
k = lambda A, B: np.exp(-(A - B.T) ** 2 / 2)
alpha = np.linalg.solve(k(X, X) + 0.1 * np.eye(2), y)
Xn = np.array([[0.5], [3.0]])
print(alpha.round(4), (k(Xn, X) @ alpha).round(4))     # [-0.1343  1.8922] [1.5514 0.2546]
print((k(X, X) @ alpha).round(3))                      # [1.013 1.811]: подгонка в обучающих точках, а не (1, 2)
print(KernelRidge(alpha=0.1, kernel='rbf', gamma=0.5).fit(X, y).predict(Xn).round(4))   # [1.5514 0.2546]

# ширина RBF-ядра как смещение и разброс: SVM на двух зашумлённых полумесяцах, gamma = 1/(2 sigma^2)
Xm, ym = make_moons(n_samples=600, noise=0.3, random_state=0)
Xtr, Xte, ytr, yte = train_test_split(Xm, ym, test_size=0.5, random_state=0)
print('linear', round(SVC(kernel='linear').fit(Xtr, ytr).score(Xte, yte), 3))   # linear 0.853
for g in (0.01, 0.1, 1, 10, 100, 1000):
    m = SVC(kernel='rbf', gamma=g, C=1).fit(Xtr, ytr)
    print(g, round(1 / math.sqrt(2 * g), 3), round(m.score(Xtr, ytr), 3), round(m.score(Xte, yte), 3), len(m.support_))
# gamma, sigma, доля правильных на обучении и на тесте, опорные векторы
# 0.01 7.071 0.843 0.827 198 | 0.1 2.236 0.883 0.85 125 | 1 0.707 0.937 0.88 79
# 10 0.224 0.94 0.883 126    | 100 0.071 0.99 0.857 256 | 1000 0.022 1.0 0.653 299

# случайные признаки Фурье: наибольшая ошибка по матрице Грама 300 x 300 (5 признаков, gamma = 0.1), среднее по 5 генерациям
Q = rng.normal(size=(300, 5)); K = np.exp(-0.1 * ((Q[:, None] - Q[None]) ** 2).sum(-1))
for D in (10, 100, 1000, 10000):
    err = [np.abs((Z := RBFSampler(gamma=0.1, n_components=D, random_state=s).fit_transform(Q)) @ Z.T - K).max() for s in range(5)]
    print(D, round(float(np.mean(err)), 3))
# 10 1.118 | 100 0.343 | 1000 0.101 | 10000 0.035: примерно 1/sqrt(D)

# линейный SVM на D случайных признаках приближается к RBF-SVM (gamma = 1: доля правильных на тесте 0.88)
for D in (2, 10, 100, 1000):
    f = RBFSampler(gamma=1, n_components=D, random_state=0).fit(Xtr)
    print(D, round(LinearSVC(C=1).fit(f.transform(Xtr), ytr).score(f.transform(Xte), yte), 3))
# 2 0.663 | 10 0.883 | 100 0.88 | 1000 0.877

Дальше#

SVM и его ядра разделяют два класса. Во многих задачах их больше: десять цифр, тысячи тем, словарь из десятков тысяч слов или несколько меток сразу у одного объекта. Следующая заметка сводит такие задачи к бинарным, обобщает логистическую регрессию на много классов с помощью softmax и приспосабливает метрики из заметки о метриках классификации к нескольким классам и к нескольким меткам на пример.

Литература#

• B. E. Boser, I. M. Guyon, V. N. Vapnik. A Training Algorithm for Optimal Margin Classifiers. COLT, 1992, pp. 144–152. Ядерный трюк в классификаторе с максимальным зазором.
• N. Aronszajn. Theory of Reproducing Kernels. Transactions of the American Mathematical Society, 68(3), pp. 337–404, 1950.
• G. Kimeldorf, G. Wahba. Some Results on Tchebycheffian Spline Functions. Journal of Mathematical Analysis and Applications, 33(1), pp. 82–95, 1971. Теорема о представителе для квадратичной функции потерь.
• B. Schölkopf, R. Herbrich, A. J. Smola. A Generalized Representer Theorem. COLT, LNCS 2111, pp. 416–426, 2001.
• A. Rahimi, B. Recht. Random Features for Large-Scale Kernel Machines. NIPS, 2007. §3: теорема Бохнера (теорема 1), случайные признаки Фурье (алгоритм 1), равномерная сходимость (утверждение 1).
• A. Gretton, K. M. Borgwardt, M. J. Rasch, B. Schölkopf, A. Smola. A kernel two-sample test. JMLR, 13, pp. 723–773, 2012. Максимальное среднее расхождение.
• C. E. Rasmussen, C. K. I. Williams. Gaussian Processes for Machine Learning. MIT Press, 2006. §2.1–2.2 (регрессия в пространстве весов и в пространстве функций), §4.3 (анализ ядер через собственные функции, теорема Мерсера), §6.1–6.2 (гильбертовы пространства с воспроизводящим ядром, регуляризация).
• S. Shalev-Shwartz, S. Ben-David. Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, 2014. Глава 16: вложения в пространства признаков, ядерный трюк, теорема 16.1 (теорема о представителе), лемма 16.2 (положительно полуопределённые ядра).
• C. M. Bishop. Pattern Recognition and Machine Learning. Springer, 2006. §6.1 (двойственные представления), §6.2 (построение ядер), §6.4 (гауссовские процессы).
• T. Hastie, R. Tibshirani, J. Friedman. The Elements of Statistical Learning, 2nd ed. Springer, 2009. §3.4.1 (гребневая регрессия и её эффективное число степеней свободы), §5.8 (регуляризация и гильбертовы пространства с воспроизводящим ядром), §12.3 (SVM и ядра).
• E. Sokolov et al. Машинное обучение (HSE), конспекты лекций: лекция 13 (ядерные методы, построение ядер, полиномиальное и гауссовское ядра), лекция 14 (ядерный SVM, случайные признаки Фурье).