Ядро

Материал из MachineLearning.

Версия от 16:41, 17 июля 2026; Alfina Iamaeva (Обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)

Содержание

1 Ядра в машинном обучении
2 См. также
3 Литература

Ядра в машинном обучении

Определение

Ядро (kernel) — это функция, которая измеряет сходство между двумя объектами. С точки зрения математики, ядро $\kappa(x, x')$ для любой пары объектов $x$ и $x'$ неявно вычисляет их скалярное произведение в некотором «расширенном» пространстве признаков $\mathcal{H}$ , но делает это, оставаясь в исходном пространстве.

Простая формальная запись выглядит так: $\kappa(x, x') = \langle \phi(x), \phi(x') \rangle_{\mathcal{H}}$

Здесь $\phi$ — это некоторое гипотетическое преобразование (например, возведение координат в квадрат или расчет расстояния до центров кластеров). Ключевая идея состоит в том, что само преобразование $\phi$ мы никогда не вычисляем и можем даже не знать его явного вида. Вся магия работает благодаря функции $\kappa$ , которую мы вычисляем напрямую.

Ядерный трюк: что это и как работает

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

Аналогия. Представьте, что вы оцениваете дружбу между людьми не по списку их характеристик в резюме, а по тому, насколько совпадают их любимые книги, фильмы и привычки. Ядро — это и есть инструмент такой оценки сходства, только математически строгий.

Техническая суть. Многие алгоритмы машинного обучения (например, SVM, гребневая регрессия) можно переписать так, что на каждом шагу они будут использовать только попарные скалярные произведения объектов: $\langle x_i, x_j \rangle$ . Если мы заменим в этих алгоритмах $\langle x_i, x_j \rangle$ на вызов ядра $\kappa(x_i, x_j)$ , то без изменения кода алгоритм обучится в новом, более мощном пространстве $\mathcal{H}$ .

Пример «на пальцах». Допустим, точки двух классов на плоскости расположены в виде «мишени»: круг внутри, кольцо снаружи. Никакой прямой линией мы их не разделим. Но если мы добавим новый признак $z = x^2 + y^2$ (квадрат расстояния от центра), точки выстроятся вдоль оси $z$ , и их станет легко разделить горизонтальной линией. Ядро RBF делает именно это, но автоматически и без явного расчета тысяч новых координат. Функция $\kappa(x, x') = \exp(-\gamma \|x - x'\|^2)$ просто считает что-то вроде «экспоненты от минус расстояния», но математически доказано, что это соответствует скалярному произведению в пространстве бесконечного числа признаков.

Какие бывают ядра и как их выбирать

Выбор ядра — это выбор того, как модель будет понимать «похожесть» объектов. Это главная инженерная задача при использовании ядерных методов.

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

$\kappa(x, x') = \langle x, x' \rangle$ Самый простой случай. Никакого трюка не происходит, мы работаем в исходном пространстве. Когда использовать:

Признаков очень много (например, десятки тысяч слов в TF-IDF для анализа текстов).
Данные и так почти линейно разделимы.
Нужна очень быстрая и хорошо интерпретируемая модель (можно посмотреть веса признаков).

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

$\kappa(x, x') = (\gamma \langle x, x' \rangle + r)^d$ Моделирует взаимодействия признаков вплоть до степени $d$ . Если $d=2$ , ядро неявно учитывает не только исходные признаки, но и все их попарные произведения. Когда использовать:

Есть понимание, что важны конкретные нелинейные комбинации (например, «цена * площадь» в задаче оценки недвижимости).
Данные нормированы, и нам не нужна супер-гибкая граница. Будьте осторожны: при больших $d$ значения ядра могут становиться очень большими или очень маленькими.

RBF (гауссовское ядро, Radial Basis Function)

$\kappa(x, x') = \exp\left(-\gamma \|x - x'\|^2\right)$ Король нелинейных задач и самый популярный выбор. Измеряет близость как экспоненту от квадрата расстояния между объектами. Имеет бесконечную размерность, то есть может подстроиться под границу практически любой формы. Когда использовать:

Вы не знаете, какая структура у данных, но предполагаете, что она сложная.
У вас не слишком много данных (до десятков тысяч объектов), и нормально работает кросс-валидация.
Это ядро по умолчанию для SVM.

Важнейшие параметры C и gamma

Для практического применения RBF критически важны два гиперпараметра (обычно в SVM):

C (штраф за ошибку): Баланс между шириной разделяющей полосы и количеством ошибок на обучении. Большое C заставляет модель правильно классифицировать все точки, что ведет к сложным, изрезанным границам и риску переобучения. Маленькое C позволяет больше ошибок, делает границу более гладкой и обобщающей.
gamma ( $\gamma$ ): Определяет «радиус влияния» одной точки. Большое gamma означает, что точка влияет только на очень близких соседей — граница становится рваной, модель переобучается. Маленькое gamma размывает влияние, делает границу слишком простой (вплоть до почти линейной).

Стандартный протокол настройки: перебор $C$ и $\gamma$ на логарифмической сетке (например, $C \in \{10^{-3}, 10^{-2}, ..., 10^3\}$ , $\gamma \in \{10^{-4}, 10^{-3}, ..., 10^1\}$ ) с использованием кросс-валидации.

Основные алгоритмы, использующие ядра

Метод опорных векторов (SVM)

Самый известный потребитель ядер. Изначально SVM ищет линейную разделяющую полосу максимальной ширины. Применение ядерного трюка превращает его в мощный нелинейный классификатор. На этапе предсказания модель опирается только на опорные векторы — объекты обучающей выборки, ближайшие к границе. Формула предсказания: $f(x) = \text{sign}\left(\sum_{i} \alpha_i y_i \kappa(x_i, x) + b\right)$ Здесь $\alpha_i$ — ненулевые коэффициенты только для опорных векторов, что делает предсказание эффективным.

Ядерный PCA

Классический PCA ищет направления максимальной дисперсии в исходных данных. Ядерный PCA делает то же самое, но в пространстве $\mathcal{H}}$ . Это позволяет ему, например, выделить «главную компоненту» для данных в форме кольца или спирали — задача, с которой обычный PCA не справится. Технически это требует вычисления матрицы Грама (об этом ниже) и ее разложения.

Ядерная гребневая регрессия (Kernel Ridge Regression)

Это альтернатива линейной регрессии, которую можно «изогнуть». Вместо прямой линии модель строит гладкую функцию, проходящую через точки. Решение в ядерной форме имеет элегантный вид: $f(x) = Y^\top (K + \lambda I)^{-1} \mathbf{k}(x)$ где:

$K$ — матрица Грама (или ядерная матрица). Это таблица $N \times N$ , в ячейке $K_{ij}$ которой хранится значение ядра $\kappa(x_i, x_j)$ для каждой пары обучающих объектов. По сути, это вся информация, которую модель знает о данных.
$\mathbf{k}(x)$ — столбец сходства нового объекта $x$ со всей обучающей выборкой.
$\lambda$ — коэффициент регуляризации.

Практические аспекты и проблема масштабируемости

Главная ахиллесова пята ядерных методов — цена работы с матрицей Грама.

Память: Хранение матрицы требует $O(N^2)$ ячеек. Для 100 000 объектов матрица из 10 миллиардов чисел уже не поместится в оперативную память стандартного компьютера.
Время: Обращение матрицы (как в Kernel Ridge Regression или Гауссовских процессах) стоит $O(N^3)$ операций. Утроение данных увеличивает время счета в 27 раз.

Это делает классическую ядерную машину идеальным инструментом для малых и средних данных (примерно до 20–50 тысяч объектов), но создает сложности на больших данных.

Методы ускорения

Инженеры придумали способы «обмануть» кубическую сложность:

Разложение Нюстрёма (Nyström method). Интуиция: вся матрица Грама имеет большой избыток информации. Мы берем случайные $m \ll N$ строк и столбцов и по ним приближенно восстанавливаем остальную часть матрицы. Сложность падает до $O(N m^2)$ .
Случайные признаки (Random Fourier Features). Вместо того чтобы работать с ядром, мы генерируем случайные $D$ -мерные векторы $z(x)$ так, что $\kappa(x, x') \approx z(x)^\top z(x')$ . После этого применяем обычный быстрый линейный метод. Это превращает ядерный метод в линейный и снижает сложность до $O(N D)$ .

Важные математические детали (для углубленного понимания)

Матрица Грама (K) должна быть положительно полуопределенной. Это означает, что функция-кандидат в ядра должна давать такую матрицу сходств, у которой нет отрицательных собственных значений. Это гарантирует, что найдется неявное пространство $\mathcal{H}$ , где эта матрица будет матрицей скалярных произведений.
RKHS (Воспроизводящее ядро гильбертова пространства). Это математическая конструкция, которая стоит за каждым ядром. Если ядро удовлетворяет условиям, то существует уникальное гильбертово пространство функций, где $f(x) = \langle f, \kappa(\cdot, x) \rangle$ . Для практика это означает, что поиск сложной нелинейной функции в этом пространстве сводится к поиску комбинации участков ядра, привязанных к точкам данных.

Современное состояние: ядра и нейронные сети

Ядерные методы и глубокие нейросети не конкуренты, а взаимодополняющие инструменты.

Гауссовские процессы — это байесовские ядерные методы, незаменимые в задачах оптимизации гиперпараметров (Bayesian Optimization) и всюду, где нужна оценка неопределенности прогноза.
Neural Tangent Kernel (NTK). Современная теория показала, что бесконечно широкая нейронная сеть со случайной инициализацией в процессе градиентного спуска ведет себя в точности как ядерный метод с ядром NTK. Это дало строгий математический мост между двумя мирами и помогает теоретически объяснять успех глубокого обучения.

См. также

Литература

Schölkopf, B., & Smola, A. J. (2002). Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond. MIT Press. (Настольная книга по теории).
Bishop, C. M. (2006). Pattern Recognition and Machine Learning. Springer. (Глава 6: Kernel Methods, отличное введение).
Murphy, K. P. (2012). Machine Learning: A Probabilistic Perspective. MIT Press. (Глава 14: Kernels, с упором на практику и связь с байесовскими методами).
Rahimi, A., & Recht, B. (2007). Random Features for Large-Scale Kernel Machines. Advances in Neural Information Processing Systems (NIPS). (Революционная статья об аппроксимации ядер).
Jacot, A., Gabriel, F., & Hongler, C. (2018). Neural Tangent Kernel: Convergence and Generalization in Neural Networks. Advances in Neural Information Processing Systems (NeurIPS). (Теория, связывающая ядра и нейросети).

Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%AF%D0%B4%D1%80%D0%BE»