Ядерное обобщение методов

Вычислительная проблема

В прошлой главе вы изучили важность работы не с исходными признаками $\mathbf{x}$, а с их нелинейно преобразованными версиями посредством спрямляющего преобразования $\phi(\mathbf{x})$. Однако в реальных задачах размерность $\phi(\mathbf{x})$ может быть очень большой, иногда даже бесконечной. Явное вычисление всех новых признаков становится вычислительно дорогим и часто невозможным. Например, при использовании полиномиальных признаков степени $K$ для вектора размерности $D$ количество новых признаков будет $\binom{D+K}{D}$, что даже при небольших $D$ и $K$ становится непрактичным.

Доказательство для любознательных

Пусть у нас есть вектор признаков размерности $D$:

$$\mathbf{x} = (x_1, x_2, \dots, x_D)$$

и мы хотим построить все мономы степени $K$:

$$x_1^{k_1} x_2^{k_2} \cdots x_D^{k_D}, \quad k_1 + k_2 + \dots + k_D = K, \quad k_i \ge 0.$$

Каждое целое число $k_i$ можно интерпретировать как количество звёздочек ★, присвоенных признаку $x_i$.

• Всего звёздочек: $K$
• Нужно распределить их между $D$ признаками.

Пример для $D=3$, $K=4$:

$x_1^4 x_2^0 x_3^0 \to$ ★★★★|| $x_1^3 x_2^1 x_3^0 \to$ ★★★|★| $x_1^1 x_2^1 x_3^2 \to$ ★|★|★★ ...

Здесь каждая перегородка | отделяет группы звёздочек для разных признаков, а число звёздочек между перегородками определяет степень соответствующего признака.

Для распределения $K$ звёздочек между $D$ признаками требуется $D-1$ перегородка.

По комбинаторике, количество способов выбрать $D-1$ позиций из $K+D-1$ равно числу сочетаний из $K+D-1$ по $D$, т.е. $\binom{K+D-1}{D-1}$.

Задание: посчитайте теперь множество мономов из $D$ признаков степени не выше $D$.

Идея

Можно ли обойтись без явного построения $\phi(\mathbf{x})$, но при этом позволить алгоритму учитывать все эти сложные признаки? Оказывается, это можно сделать, если формула построения прогноза метода вместе с настроенными параметрами можно выразить так, чтобы она зависела не от самих объектов $\mathbf{x}$ и $\mathbf{x}_1,\mathbf{x}_2,\cdots\mathbf{x}_N$ напрямую, а зависела от них опосредованно через скалярные произведения $\langle \mathbf{x},\mathbf{x}_i\rangle$ и $\langle \mathbf{x}_i,\mathbf{x}_j\rangle$.

В таком виде можно выразить прогнозы, например, для гребневой регрессии, метода опорных векторов и метода главных компонент.

В этом случае формула построения прогнозов в пространстве исходных признаков будет

$$\widehat{y}\left(\mathbf{x}\right)=F\left(\left\{ \left<\mathbf{x},\mathbf{x}_{i}\right>\right\} _{i}\left\{ \left<\mathbf{x}_{i},\mathbf{x}_{j}\right>\right\} _{i,j}\right)$$

После перехода в спрямляющее пространство $\mathbf{x}\to\phi\left(\mathbf{x}\right)$ она станет

$$\widehat{y}\left(\mathbf{x}\right)=F\left(\left\{ \left<\phi\left(\mathbf{x}\right),\phi\left(\mathbf{x}_{i}\right)\right>\right\} _{i}\left\{ \left<\phi\left(\mathbf{x}_{i}\right),\phi\left(\mathbf{x}_{j}\right)\right>\right\} _{i,j}\right),$$

что, используя функцию ядра (kenrel function) $k\left(\mathbf{x},\mathbf{z}\right)=\left<\phi\left(\mathbf{x}\right),\phi\left(\mathbf{z}\right)\right>$ можно записать в виде

$$\widehat{y}\left(\mathbf{x}\right)=F\left(\left\{ k\left(\mathbf{x},\mathbf{x}_{i}\right)\right\} _{i},\left\{ k\left(\mathbf{x}_{i},\mathbf{x}_{j}\right)\right\} _{i,j}\right)$$

Таким образом, если заменить все скалярные произведения в формуле построения прогнозов функциями ядра, то алгоритм будет работать в высокомерном пространстве признаков без его явного создания, что будет очень быстро, поскольку к сложности вычисления исходной версии алгоритма добавится только сложность вычисления ядра, которое по сложности вычислений обычно не отличается от обычного скалярного произведения!

Популярные ядра

При обработке табличных данных чаще всего используются следующие ядра (kernels):

Название	Формула	Гиперпараметры
линейное	$k(\mathbf{x}, \mathbf{x'}) = \langle \mathbf{x}, \mathbf{x'}\rangle$	—
полиномиальное	$k(\mathbf{x}, \mathbf{x'}) = (\langle \mathbf{x}, \mathbf{x'}\rangle + r)^d$	$r \ge 0$ — сдвиг, $d \in \mathbb{N}$ — степень
RBF (Гауссово)	$k(\mathbf{x}, \mathbf{x'}) = \exp(-\gamma \|\mathbf{x} - \mathbf{x'}\|^2)$	$\gamma > 0$ — ширина ядра

Гауссово ядро также часто записывается в виде

$$K(x, x') = \exp\Big(-\frac{\|x - x'\|^2}{2\sigma^2}\Big),$$

где $1/(2\sigma^2)=\gamma$ из первого определения, а $\sigma^2$ называется дисперсией Гауссова ядра.

Разберём описание спрямляющего пространства и применения каждого из этих ядер.

Линейное ядро

Спрямляющее пространство соответствует исходным признакам, $\phi(\mathbf{x}) = \mathbf{x}$, точки не меняют своих координат.

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

Полиномиальное ядро

В полиномальном ядре каждая точка $\mathbf{x}=(x^1,x^2,...x^D)$ отображается во всевозможные полиномиальные комбинации исходных признаков степень которых не превосходит $d$ при $r>0$:

$$\phi(\mathbf{x}) = \{(\sqrt{r})^{i_0} \cdot (x^1)^{i_1} \cdot (x^2)^{i_2} \cdot (x^D)^{i_D} \}_{i_0,i_1,i_2,...i_D},$$ $$i_0+i_1+\cdots+i_D\le d$$

В частном случае $r=0$ используются всевозможные полиномиальные комбинации признаков степени ровно $d$:

$$\phi(\mathbf{x}) = \{((x^1)^{i_1} \cdot (x^2)^{i_2} \cdot (x^D)^{i_D} \}_{i_0,i_1,i_2,...i_D},$$ $$i_1+\cdots+i_D= d$$

Это ядро применяется для нелинейных данных, когда целевая функция хорошо аппроксимируется полиномиальной зависимостью.

Вычислительная эффективность

Вместо явного перехода в пространство размерности $\binom{K+D}{D}$ при $r>0$ или $\binom{K+D-1}{D-1}$ при $r=0$ мы используем обычный прогноз в исходном пространстве признаков, но в котором скалярные произведения $\langle \mathbf{x}, \mathbf{x'}\rangle$ заменяются на $(\langle \mathbf{x}, \mathbf{x'}\rangle + r)^d$, что имеет тот же порядок сложности!

Увеличение $d$ приводит к переходу в более высокоразмерное пространство (сохраняя при этом сложность исходного метода!), что позволяет моделировать более сложные виды зависимостей, но при этом и более склонно к переобучению.

Увеличение $r$ приводит к увеличению множителей при признаках, соответствующих мономам более низких степеней, увеличивая их масштаб и значимость подобных признаков в итоговом прогнозе.

RBF (Гауссово) ядро

Это ядро является самым популярным в машинном обучении. При этом спрямляющее пространство этого ядра бесконечномерно, поэтому мы бы не смогли перейти в него явно. Однако при использовании ядерного обобщения мы сохраняем возможность в нём работать, причём это имеет тот же порядок вычислительной сложности, что и работа в исходном признаковом пространстве!

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

При увеличении $\gamma$ ядро изменяется резче и становится более локальным: точки, находящиеся далеко друг от друга, дают значение ядра близкое к 0. Таким образом при больших $\gamma$ метод становится более гибким, но и более склонным к переобучению.

При $\gamma \to 0$ Гауссово ядро стремится к линейному.

Обоснование для любознательных

Для любых векторов $\mathbf{x}$ и $\mathbf{x'}$:

$$\|\mathbf{x} - \mathbf{x}'\|^2 = \|\mathbf{x}\|^2 + \|\mathbf{x}'\|^2 - 2 \langle \mathbf{x}, \mathbf{x}' \rangle$$

Вспомним разложение Тейлора для экспоненты:

$$e^z = 1 + z + \frac{z^2}{2!} + \frac{z^3}{3!} + \dots$$

RBF-ядро можно выразить следующим образом:

$$K(\mathbf{x}, \mathbf{x}') = \exp(-\gamma \|\mathbf{x} - \mathbf{x}'\|^2) = \exp\Big(-\gamma (\|\mathbf{x}\|^2 + \|\mathbf{x}'\|^2 - 2 \langle \mathbf{x}, \mathbf{x}' \rangle)\Big)$$

Выделяем зависимость от скалярного произведения:

$$K(\mathbf{x}, \mathbf{x}') = \exp(-\gamma \|\mathbf{x}\|^2) \, \exp(-\gamma \|\mathbf{x}'\|^2) \, \exp(2 \gamma \langle \mathbf{x}, \mathbf{x}' \rangle)$$

Применяем разложение Тейлора к экспоненте с $\langle \mathbf{x}, \mathbf{x}' \rangle$:

$$\exp(2 \gamma \langle \mathbf{x}, \mathbf{x}' \rangle) = 1 + 2 \gamma \langle \mathbf{x}, \mathbf{x}' \rangle + \frac{(2 \gamma \langle \mathbf{x}, \mathbf{x}' \rangle)^2}{2!} + \frac{(2 \gamma \langle \mathbf{x}, \mathbf{x}' \rangle)^3}{3!} + \dots$$

Отсюда видно, что RBF-ядро зависит от бесконечной суммы полиномиальный ядер всех степеней, следовательно спрямляющее пространство включает бесконечное количество всевозможных мономов от исходных признаков.

При этом за счёт множителя $1/n!$ существенное влияние оказывают только первые члены разложения. Число значимых слагаемых разложения тем больше, чем выше $\gamma$, поэтому с ростом $\gamma$ эффективная размерность используемого признакового пространства растёт, и метод становится способным моделировать более сложные зависимости.

При $\gamma\to 0$:

• $\exp(-\gamma \|\mathbf{x}\|^2)\to 1$,

• $\exp(-\gamma \|\mathbf{x'}\|^2)\to 1$,

• $\exp(2 \gamma \langle \mathbf{x}, \mathbf{x}' \rangle) \to 1 + 2 \gamma \langle \mathbf{x}, \mathbf{x}' \rangle$,

откуда следует, что ядро стремится к линейному.

Всякая ли функция $k(\mathbf{x},\mathbf{x'})$ годится как функция ядра?

Нет, не каждая. Поскольку функции ядра соответствует скалярное произведение

$\left<\phi\left(\mathbf{x}\right),\phi\left(\mathbf{x}'\right)\right>$, то эта функция должна быть симметричной и неотрицательно определённой, что более формально сформулировано в теореме Мерсера [1].

Помимо представленных, существуют и другие типы ядер. В частности, существуют специализированные ядра для строковых [2] и графовых данных [3], использование которых позволяет работать со строками/графами напрямую без приведения их к векторному представлению (что приводило бы к потере информации и снижению качества обработки).

Литература

1. Wikipedia: Mercer's theorem.
2. Wikipedia: String kernel.
3. Wikipedia: Graph kernel.