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

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

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

Например, при использовании полиномиальных признаков степени не выше $K$ в $D$-мерном пространстве признаков количество новых признаков будет равно числу сочетаний из $D+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-1$, т.е. $\binom{K+D-1}{D-1}$.

Чтобы посчитать число всех мономов степени не выше $K$ необходимо в число признаков включить тождественную единицу и посчитать число мономов степени в точности равной $K$, что по формуле выше (учитывая появление $D+1$ признака) будет $\binom{K+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$.

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

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

$$\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),$$

что, используя обозначение $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),$$

где $k\left(\mathbf{x},\mathbf{z}\right)$ называется функцией ядра (kenrel function).

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

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

При обработке табличных данных чаще всего используются следующие ядра (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$:

$$\phi(\mathbf{x}) = \{\sqrt{\frac{d!}{i_0!i_1!...i_D!}}(\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} \text{ при } r>0$$ $$i_0+i_1+\cdots+i_D = d$$

Это можно проверить непосредственным расчётом $\langle \phi(\mathbf{x}), \phi(\mathbf{x}) \rangle$ и применением мультиномиальной теоремы [1].

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

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

$$\phi(\mathbf{x}) = \{\sqrt{\frac{d!}{i_1!...i_D!}}(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 \to 0$ Гауссово ядро стремится к константе.

При увеличении $\gamma$ ядро порождает более выраженные нелинейные зависимости, делая метод, опирающийся на такое ядро, более гибким, но и более склонным к переобучению.

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

По свойствам скалярного произведения для любых векторов $\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 \to 1$,

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

подсказка

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

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

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

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

Литература

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