Ядро

Пример использования ядерного трюка

Ядерный трюк(анг. kernel function) метод в машинном обучении, позволяющий перевести элементы для случая линейной неразделимости в новое линейно разделимое пространство пространство. Такое пространство называют спрямляющим. Поскольку для любой непротиворечивой выборки соответствующее пространство большей размерности существует, главной проблемой становится его найти.

Определение

Функция $K(x,x'):X×X\rightarrow \mathbb{R}$ называется ядром, если она может быть представлена в виде $K(x,x')=\langle \varphi(x),\varphi(x')\rangle_H$ при некотором отображении $\varphi(x):X\rightarrow H$,где H — пространство со скалярным произведением.

Поскольку для задачи линейного разделения объектов не требуется их признаковое описание, а достаточно скаляров, то можно заменить скалярное произведение $\langle x,x'\rangle$ на ядро $K(x,x')$ Более того, можно вообще не строить спрямляющее пространствоHв явномвиде, и вместо подбора отображения $\varphi$ заниматься непосредственно подбором ядра.

Можно пойти ещё дальше, и вовсе отказаться от признаковых описаний объек-тов. Во многих практических задачах объекты изначально задаются информациейоб их попарном взаимоотношении, например, отношении сходства. Если эта инфор-мация допускает представление в виде двуместной функции $K(x,x')$, удовлетворяю-щей аксиомам скалярного произведения, то задача может решаться методом SVM .

Теорема Мерсера

Функция K(x,y) является ядром тогда и только тогда, когда:

Она симметрична: $K(x,y)=K(y,x)$

Она неотрицательно определена, то есть $\forall g: X \rightarrow \mathbb{R}, \int_X \int_X K(x, x')g(x)g(x')dxdx' \geqslant 0$

Конструктивные способы построения ядер

1.Произвольное скалярное произведение $ K(x,x') =\langle x,x'\rangle $ является ядром.

2. Константа $K(x,x') = 1$ является ядром.

3. Произведение ядер $K(x,x')=K_1(x,x')K_2(x,x')$является ядром.

4. Для любой функции $\psi :X\rightarrow R$ произведение [math]K(x,x′) =\psi(x)\psi(x′)[/math]— ядро.

5. Линейная комбинация ядер с неотрицательными коэффициентами K(x,x′) ==\alpha_1K_1(x,x') +\alpha_2K_2(x,x')является ядром.

6. Композиция произвольной функции $\varphi:X \rightarrow X$ и произвольного ядраK0является ядром: $K(x,x') =K_0(\varphi(x),\varphi(x'))$.

7. Еслиs:$X×X\rightarrow R$ произвольная симметричная интегрируемая функция, то $K(x,x′) =\int Xs(x,z)s(x',z)$dzявляется ядром.//TODO

8. Функция вида K(x,x') = k(x−x)является ядром тогда и только тогда, когдаФурье-образ F[k](\omega) = (2\Pi)n_2∫Xe−i〈\owmega,x〉k(x)dx неотрицателен.

9. Предел локально-равномерно сходящейся последовательности ядер — ядро.

10. Композиция произвольного ядраK0и произвольной функции f:R\rightarrow R, представимой в виде сходящегося степенного ряда с неотрицательными коэффициентами $K(x,x') = f(K_0(x,x'))$, является ядром. В частности, функции $f(z) =e^z$ и f(z) =1/{1−z} от ядра являются ядрами.

Ядерный трюк

Поскольку для обучения зачастую необходима уже функция "расстояния" между элементами в новом пространстве, то вместо явного нахождения ядра — его можно зашить внутрь соответсвующей функции k(x, x'). Такую функцию k называют ядерной функцией

Некоторые часто используемые функции

0.Линейное $K(x, x')= \langle x, x'\rangle$

1.Полиномиальное ядро $K(x, x') = (\langle x, x' \rangle + R)^d$

2.Гаусово ядро RBF K(x, x') = exp(-\gamma ||x - x'||^2)

Источники информации

1. Ядра и спрямляющие пространства p.73-75 — К. В. Воронцов Математические методы обучения по прецедентам