Функция ядра¶
Функция ядра — математическая функция, определённая на пространстве признаков и используемая в методах машинного обучения, в первую очередь в опорных векторных машинах (SVM) и ядерных методах, для неявного отображения данных в пространство более высокой размерности, где данные становятся линейно разделимыми. Ключевое свойство ядерной функции — возможность вычислять скалярное произведение в пространстве признаков, не выполняя самого отображения явно («безъядерный трюк», kernel trick).
¶Математическая постановка
Пусть дано отображение $\varphi: \mathbb{R}^n \to \mathbb{R}^m$, $m \gg n$. Ядерная функция $K(x, y)$ называется корректной (соответствующей скалярному произведению), если для любых векторов $x, y$ и любых коэффициентов $c_i$ выполняется
$$\sum_{i,j} c_i c_j K(x_i, x_j) \ge 0$$
(положительная полуопределённость) и $K(x, y) = \langle \varphi(x), \varphi(y) \rangle$. Второе условие позволяет заменить скалярное произведение в пространстве признаков на вычисление ядра в исходном пространстве, что и составляет суть «безъядерного трюка».
¶Основные виды ядерных функций
| Ядро | Формула | Особенности | ||
|---|---|---|---|---|
| Линейное | $K(x,y) = x^\top y$ | Отображение тождественно, вырождается в обычный линейный классификатор | ||
| Полиномиальное | $K(x,y) = (\gamma x^\top y + r)^d$ | Моделирует взаимодействия признаков до степени $d$ | ||
| Гауссово (RBF) | $K(x,y) = \exp(-\gamma \ | x-y\ | ^2)$ | Бесконечномерное пространство признаков, самый распространённый выбор |
| Сигмоидный | $K(x,y) = \tanh(\gamma x^\top y + r)$ | Не всегда является корректным ядром | ||
| Степенное | $K(x,y) = (x^\top y)^d$ | Частный случай полиномиального при $r=0$ |
Гауссово ядро соответствует отображению в бесконечномерное пространство (разложение в ряд Тейлора показывает бесконечное число мономиальных признаков). Сигмоидное ядро корректно лишь при определённых значениях параметров $\gamma$ и $r$.
¶Теорема Мерсера
Теорема Мерсера (1909) даёт необходимое и достаточное условие корректности ядра: непрерывная симметричная функция $K(x,y)$ является ядром тогда и только тогда, когда она положительно полуопределена на компакте. Теорема Мура — Арона защищает более общие случаи. На практике проверка положительной полуопределённости выполняется численно — построением матрицы Грама $G_{ij} = K(x_i, x_j)$ и проверкой неотрицательности собственных чисел.
¶Применение
¶Опорные векторные машины
В SVM задача двоичной классификации сводится к максимизации функции Лагранжа, в которой данные входят только через попарные скалярные произведения. Замена их на $K(x_i, x_j)$ позволяет строить нелинейные границы разделения классов без явного вычисления $\varphi(x)$. Гиперпараметры ядра ($\gamma$, $d$, $r$) подбираются кросс-валидацией.
¶Регрессия с опорными векторами
SVR (Support Vector Regression) использует ту же ядерную замену для задач регрессии, допуская отступ $\varepsilon$, в пределах которого ошибки не штрафуются.
¶Ядерные методы в статистике
Ядерная оценка плотности (KDE) использует ядерную функцию $K_h(x) = \frac{1}{h}K(x/h)$ для непараметрического оценивания распределения случайной величины. Ядерное сглаживание применяется в оценке регрессионных функций и плотностей.
¶Другие области
Ядерные представления используются в анализе текстов (TF-IDF с ядерными моделями), компьютерном зрении (SIFT-дескрипторы), биоинформатике (классификация белковых последовательностей), обработке сигналов. В глубоком обучении ядерные идеи проявляются в attention-механизмах трансформеров, где скалярное произведение запроса и ключа выполняет роль линейного ядра.
¶Выбор и настройка ядра
На практике выбор ядра определяется задачей и объёмом данных. Гауссово ядро — дефолтный вариант для большинства задач благодаря универсальности. Полиномиальное ядро полезно, когда известна природная полиномиальная структура данных. Линейное ядро предпочтительно при $m \gg n$ (например, классификация текстов), где нелинейность не требуется. Сложность вычислений ядерной матрицы — $O(N^2 d)$ по памяти и времени, что ограничивает применение SVM на выборках свыше $10^4$–$10^5$ объектов; для больших данных используются приближённые методы (random features, Nystrom-приближение).
¶История
Идея «безъядерного трюка» восходит к работам Айзенберга и Айзенберга (1964), а также к методу потенциальных функций Вапника и Лернера (1963). Систематическую разработку ядерных методов для SVM выполнили Владимир Вапник и его сотрудники в 1990-х годах; термин «kernel trick» закрепился в публикациях Михаила Джордана и Тревора Хасти (1998). Теорема Мерсера была сформулирована Джеймсом Мерсером в 1909 году в контексте теории интегральных уравнений.
¶Источники
- Вапник В. Н. «Статистические теории обучения»
- Шлейхер Д. «Kernel Methods in Machine Learning»
- Мюллер К., Николау С. «Kernel Methods in Computational Biology»
- Hastie T., Tibshirani R., Friedman J. «The Elements of Statistical Learning»
- Bishop C. M. «Pattern Recognition and Machine Learning»