Ядро

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

(Различия между версиями)

Версия 16:41, 17 июля 2026

Содержание

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»

@@ Строка 1: / Строка 1: @@
 == Ядра в машинном обучении ==
-'''Ядро''' (в контексте [[Машинное обучение|машинного обучения]], не путать с ядрами [[Сверточная нейронная сеть|сверточных нейронных сетей]]) — это функция, которая позволяет применять линейные алгоритмы в неявно заданном нелинейном пространстве признаков, не вычисляя координаты точек в этом пространстве напрямую. Этот подход, известный как '''ядерный трюк''', лежит в основе широкого класса алгоритмов, называемых [[Ядерные методы|ядерными методами]].
+=== Определение ===
-Формально, ядром называется функция <tex>\kappa: \mathcal{X} \times \mathcal{X} \to \mathbb{R}</tex>, которая для любых двух объектов <tex>x, x' \in \mathcal{X}</tex> эквивалентна скалярному произведению их образов в некотором гильбертовом пространстве признаков <tex>\mathcal{H}</tex>:
+'''Ядро''' (kernel) — это функция, которая измеряет сходство между двумя объектами. С точки зрения математики, ядро <tex>\kappa(x, x')</tex> для любой пары объектов <tex>x</tex> и <tex>x'</tex> неявно вычисляет их скалярное произведение в некотором «расширенном» пространстве признаков <tex>\mathcal{H}</tex>, но делает это, оставаясь в исходном пространстве.
-<tex>\kappa(x, x') = \langle \phi(x), \phi(x') \rangle_{\mathcal{H}}</tex>,
+Простая формальная запись выглядит так:
+<tex>\kappa(x, x') = \langle \phi(x), \phi(x') \rangle_{\mathcal{H}}</tex>
-где <tex>\phi: \mathcal{X} \to \mathcal{H}</tex> — неявное отображение из исходного пространства в пространство признаков.
+Здесь <tex>\phi</tex> — это некоторое гипотетическое преобразование (например, возведение координат в квадрат или расчет расстояния до центров кластеров). '''Ключевая идея состоит в том, что само преобразование <tex>\phi</tex> мы никогда не вычисляем и можем даже не знать его явного вида'''. Вся магия работает благодаря функции <tex>\kappa</tex>, которую мы вычисляем напрямую.
-=== Исторический контекст и мотивация ===
+=== Ядерный трюк: что это и как работает ===
-Классические линейные методы, такие как [[Метод опорных векторов|SVM]] или [[Регрессия (математическая статистика)|линейная регрессия]], просты в обучении и интерпретации, но неспособны улавливать сложные нелинейные зависимости в данных. Ручное конструирование нелинейных признаков (например, полиномиальных) может привести к комбинаторному взрыву размерности. Ядра решают эту дилемму, позволяя эффективно работать в пространствах очень высокой или даже бесконечной размерности, избегая ''проклятия размерности'' за счет того, что все вычисления сводятся к операциям с ядровой функцией в исходном пространстве.
+'''Ядерный трюк''' (kernel trick) — это вычислительный прием, позволяющий незаметно перевести данные в сложное нелинейное пространство, где они становятся линейно разделимыми, без ресурсоемкой операции настоящего преобразования координат.
-=== Необходимые математические условия ===
+'''Аналогия.''' Представьте, что вы оцениваете дружбу между людьми не по списку их характеристик в резюме, а по тому, насколько совпадают их любимые книги, фильмы и привычки. Ядро — это и есть инструмент такой оценки сходства, только математически строгий.
-Чтобы функция <tex>\kappa</tex> могла быть ядром, она должна удовлетворять определенным условиям. Важнейшим из них является теорема Мерсера, а также симметричность и положительная полуопределенность.
+'''Техническая суть.''' Многие алгоритмы машинного обучения (например, [[Метод опорных векторов|SVM]], [[Гребневая регрессия|гребневая регрессия]]) можно переписать так, что на каждом шагу они будут использовать только попарные скалярные произведения объектов: <tex>\langle x_i, x_j \rangle</tex>. Если мы заменим в этих алгоритмах <tex>\langle x_i, x_j \rangle</tex> на вызов ядра <tex>\kappa(x_i, x_j)</tex>, то без изменения кода алгоритм обучится в новом, более мощном пространстве <tex>\mathcal{H}</tex>.
-'''Ядро Мерсера.''' Функция <tex>\kappa</tex> является ядром Мерсера тогда и только тогда, когда для любого конечного набора точек <tex>\{x_1, \dots, x_n\} \subset \mathcal{X}</tex> [[Матрица Грама|матрица Грама]] <tex>K</tex>, элементы которой <tex>K_{ij} = \kappa(x_i, x_j)</tex>, является симметричной и положительно полуопределенной (т.е. все ее собственные значения неотрицательны).
+'''Пример «на пальцах».''' Допустим, точки двух классов на плоскости расположены в виде «мишени»: круг внутри, кольцо снаружи. Никакой прямой линией мы их не разделим. Но если мы добавим новый признак <tex>z = x^2 + y^2</tex> (квадрат расстояния от центра), точки выстроятся вдоль оси <tex>z</tex>, и их станет легко разделить горизонтальной линией. Ядро RBF делает именно это, но автоматически и без явного расчета тысяч новых координат. Функция <tex>\kappa(x, x') = \exp(-\gamma \|x - x'\|^2)</tex> просто считает что-то вроде «экспоненты от минус расстояния», но математически доказано, что это соответствует скалярному произведению в пространстве бесконечного числа признаков.
-'''Воспроизводящее ядро гильбертова пространства (RKHS).''' Для каждого ядра Мерсера существует уникальное [[Воспроизводящее ядро гильбертова пространства|воспроизводящее ядро гильбертова пространства]] (Reproducing Kernel Hilbert Space, RKHS) <tex>\mathcal{H}_\kappa</tex>. Ключевое свойство RKHS — ''воспроизводящее свойство'': для любой функции <tex>f \in \mathcal{H}_\kappa</tex> и любого <tex>x \in \mathcal{X}</tex> выполняется <tex>f(x) = \langle f, \kappa(\cdot, x) \rangle_{\mathcal{H}_\kappa}</tex>. Это свойство связывает представление функции в гильбертовом пространстве с вычислением ядра.
+=== Какие бывают ядра и как их выбирать ===
-=== Распространенные ядра и конструирование ===
+Выбор ядра — это выбор того, как модель будет понимать «похожесть» объектов. Это главная инженерная задача при использовании ядерных методов.
-Выбор ядра критичен для успеха модели. Наиболее распространены следующие семейства:
+==== Линейное ядро ====
+<tex>\kappa(x, x') = \langle x, x' \rangle</tex>
+Самый простой случай. Никакого трюка не происходит, мы работаем в исходном пространстве.
+'''Когда использовать:'''
+* Признаков очень много (например, десятки тысяч слов в [[TF-IDF]] для анализа текстов).
+* Данные и так почти линейно разделимы.
+* Нужна очень быстрая и хорошо интерпретируемая модель (можно посмотреть веса признаков).
-* '''Линейное ядро:''' <tex>\kappa(x, x') = \langle x, x' \rangle</tex>. Соответствует отсутствию преобразования, используется как базовый случай.
+==== Полиномиальное ядро ====
-* '''Полиномиальное ядро:''' <tex>\kappa(x, x') = (\gamma \langle x, x' \rangle + r)^d</tex>. Позволяет строить разделяющие поверхности в виде полиномов степени <tex>d</tex>. Параметр <tex>\gamma</tex> масштабирует данные, <tex>r</tex> управляет влиянием старших степеней.
+<tex>\kappa(x, x') = (\gamma \langle x, x' \rangle + r)^d</tex>
-* '''Ядро радиальной базисной функции (RBF):''' <tex>\kappa(x, x') = \exp\left(-\gamma \|x - x'\|^2\right)</tex>. Самое популярное нелинейное ядро, соответствующее признаковому пространству бесконечной размерности. Оно основано на расстоянии между объектами и является универсальным аппроксиматором. Параметр <tex>\gamma</tex> определяет радиус влияния одной точки.
+Моделирует взаимодействия признаков вплоть до степени <tex>d</tex>. Если <tex>d=2</tex>, ядро неявно учитывает не только исходные признаки, но и все их попарные произведения.
-* '''Сигмоидное ядро:''' <tex>\kappa(x, x') = \tanh(\gamma \langle x, x' \rangle + r)</tex>. Исторически связано с нейронными сетями, но его матрица Грама не всегда положительно полуопределена, что ограничивает применение.
+'''Когда использовать:'''
-* '''Ядра для специальных структур данных:''' Существуют ядра, определенные на строках (string kernels), графах (graph kernels), изображениях (например, ядро пересечения гистограмм) и вероятностных распределениях, которые позволяют применять ядерные методы в этих доменах.
+* Есть понимание, что важны конкретные нелинейные комбинации (например, «цена * площадь» в задаче оценки недвижимости).
+* Данные нормированы, и нам не нужна супер-гибкая граница. Будьте осторожны: при больших <tex>d</tex> значения ядра могут становиться очень большими или очень маленькими.
-Ядра можно комбинировать для создания новых:
+==== RBF (гауссовское ядро, Radial Basis Function) ====
-* '''Сумма:''' <tex>\kappa(x, x') = \kappa_1(x, x') + \kappa_2(x, x')</tex>.
+<tex>\kappa(x, x') = \exp\left(-\gamma \|x - x'\|^2\right)</tex>
-* '''Произведение:''' <tex>\kappa(x, x') = \kappa_1(x, x') \cdot \kappa_2(x, x')</tex>.
+'''Король нелинейных задач и самый популярный выбор.''' Измеряет близость как экспоненту от квадрата расстояния между объектами. Имеет бесконечную размерность, то есть может подстроиться под границу практически любой формы.
-Эти операции сохраняют свойства положительной полуопределенности.
+'''Когда использовать:'''
+* Вы не знаете, какая структура у данных, но предполагаете, что она сложная.
+* У вас не слишком много данных (до десятков тысяч объектов), и нормально работает кросс-валидация.
+* Это ядро по умолчанию для [[Метод опорных векторов|SVM]].
-=== Ядерный трюк в алгоритмах ===
+===== Важнейшие параметры C и gamma =====
+Для практического применения RBF критически важны два гиперпараметра (обычно в [[SVM]]):
+* '''C''' (штраф за ошибку): Баланс между шириной разделяющей полосы и количеством ошибок на обучении. Большое '''C''' заставляет модель правильно классифицировать все точки, что ведет к сложным, изрезанным границам и риску переобучения. Маленькое '''C''' позволяет больше ошибок, делает границу более гладкой и обобщающей.
+* '''gamma''' (<tex>\gamma</tex>): Определяет «радиус влияния» одной точки. Большое '''gamma''' означает, что точка влияет только на очень близких соседей — граница становится рваной, модель переобучается. Маленькое '''gamma''' размывает влияние, делает границу слишком простой (вплоть до почти линейной).
-Основная идея заключается в том, что многие линейные алгоритмы можно сформулировать так, чтобы они зависели только от попарных скалярных произведений объектов <tex>\langle x_i, x_j \rangle</tex>. Замена этих произведений на вызов ядра <tex>\kappa(x_i, x_j)</tex> неявно выполняет обучение в пространстве <tex>\mathcal{H}</tex>.
+'''Стандартный протокол настройки:''' перебор <tex>C</tex> и <tex>\gamma</tex> на логарифмической сетке (например, <tex>C \in \{10^{-3}, 10^{-2}, ..., 10^3\}</tex>, <tex>\gamma \in \{10^{-4}, 10^{-3}, ..., 10^1\}</tex>) с использованием [[Кросс-валидация|кросс-валидации]].
-* '''В Методе опорных векторов (SVM):''' Двойственная задача [[SVM]] зависит от скалярных произведений. Применение ядра позволяет строить нелинейные разделяющие поверхности. Решающее правило принимает вид <tex>f(x) = \text{sign}\left(\sum_{i} \alpha_i y_i \kappa(x_i, x) + b\right)</tex>, где <tex>x_i</tex> — опорные векторы. Это классический пример непараметрической ядерной машины.
+=== Основные алгоритмы, использующие ядра ===
-* '''В Гребневой регрессии:''' Решение [[Гребневая регрессия|гребневой регрессии]] через ядерный трюк приводит к форме <tex>f(x) = Y^\top (K + \lambda I)^{-1} \mathbf{k}(x)</tex>, где <tex>\mathbf{k}(x)</tex> — вектор ядерых близостей объекта <tex>x</tex> ко всем объектам обучающей выборки.
-* '''В Анализе главных компонент (PCA):''' [[Ядерный анализ главных компонент|Ядерный PCA]] выполняет поиск главных компонент в пространстве <tex>\mathcal{H}</tex>, решая задачу на собственные векторы центрированной матрицы Грама.
-=== Практические аспекты: масштабируемость и аппроксимации ===
+==== Метод опорных векторов (SVM) ====
+Самый известный потребитель ядер. Изначально [[SVM]] ищет линейную разделяющую полосу максимальной ширины. Применение ядерного трюка превращает его в мощный нелинейный классификатор. На этапе предсказания модель опирается только на ''опорные векторы'' — объекты обучающей выборки, ближайшие к границе. Формула предсказания:
+<tex>f(x) = \text{sign}\left(\sum_{i} \alpha_i y_i \kappa(x_i, x) + b\right)</tex>
+Здесь <tex>\alpha_i</tex> — ненулевые коэффициенты только для опорных векторов, что делает предсказание эффективным.
-Главный недостаток ядерных методов — их вычислительная сложность. Для построения и хранения матрицы Грама размером <tex>N \times N</tex> требуется <tex>O(N^2)</tex> памяти и до <tex>O(N^3)</tex> операций для ее обращения (как в случае [[Гауссовский процесс|Гауссовских процессов]]), что делает их неприменимыми для больших наборов данных.
+==== Ядерный PCA ====
+Классический [[Метод главных компонент|PCA]] ищет направления максимальной дисперсии в исходных данных. [[Ядерный анализ главных компонент|Ядерный PCA]] делает то же самое, но в пространстве <tex>\mathcal{H}}</tex>. Это позволяет ему, например, выделить «главную компоненту» для данных в форме кольца или спирали — задача, с которой обычный PCA не справится. Технически это требует вычисления матрицы Грама (об этом ниже) и ее разложения.
-Для решения этой проблемы разработаны методы аппроксимации:
+==== Ядерная гребневая регрессия (Kernel Ridge Regression) ====
-* '''Случайные признаки (Random Fourier Features):''' Позволяют явно аппроксимировать ядро RBF конечномерным отображением, сводя задачу к линейной со сложностью <tex>O(N)</tex>.
+Это альтернатива линейной регрессии, которую можно «изогнуть». Вместо прямой линии модель строит гладкую функцию, проходящую через точки. Решение в ядерной форме имеет элегантный вид:
-* '''Разложение Нюстрёма (Nyström method):''' Аппроксимирует полную матрицу Грама с помощью низкорангового разложения на основе небольшого подмножества опорных точек.
+<tex>f(x) = Y^\top (K + \lambda I)^{-1} \mathbf{k}(x)</tex>
+где:
+* <tex>K</tex> — '''матрица Грама''' (или ядерная матрица). Это таблица <tex>N \times N</tex>, в ячейке <tex>K_{ij}</tex> которой хранится значение ядра <tex>\kappa(x_i, x_j)</tex> для каждой пары обучающих объектов. По сути, это вся информация, которую модель знает о данных.
+* <tex>\mathbf{k}(x)</tex> — столбец сходства нового объекта <tex>x</tex> со всей обучающей выборкой.
+* <tex>\lambda</tex> — коэффициент регуляризации.
-=== Современное состояние и связь с глубоким обучением ===
+=== Практические аспекты и проблема масштабируемости ===
-Хотя пик популярности ядерных методов пришелся на начало 2000-х, они сохраняют важное теоретическое и прикладное значение. Связь с глубинным обучением проявляется в нескольких аспектах:
+Главная ахиллесова пята ядерных методов — цена работы с матрицей Грама.
+* '''Память:''' Хранение матрицы требует <tex>O(N^2)</tex> ячеек. Для 100 000 объектов матрица из 10 миллиардов чисел уже не поместится в оперативную память стандартного компьютера.
+* '''Время:''' Обращение матрицы (как в Kernel Ridge Regression или [[Гауссовский процесс|Гауссовских процессах]]) стоит <tex>O(N^3)</tex> операций. Утроение данных увеличивает время счета в 27 раз.
-* '''Ядерные методы с множественным ядром (Multiple Kernel Learning, MKL):''' Изучают оптимальные комбинации ядер, что можно рассматривать как предшественника современных архитектур, автоматически настраивающих представления.
+Это делает классическую ядерную машину идеальным инструментом для ''малых и средних данных'' (примерно до 20–50 тысяч объектов), но создает сложности на больших данных.
-* '''Гауссовские процессы:''' Используются в Bayesian Optimization и предоставляют хорошо откалиброванную оценку неопределенности, чего лишены многие нейронные сети.
-* '''Нейронные тангенциальные ядра (Neural Tangent Kernel, NTK):''' Теория, связывающая бесконечно широкие нейронные сети с ядерными методами. NTK описывает динамику обучения таких сетей в функциональном пространстве, давая строгое теоретическое обоснование их сходимости.
-Ядерные методы остаются мощным инструментом, когда интерпретируемость и работа с малыми и средними выборками важнее масштабирования на миллиарды примеров.
+==== Методы ускорения ====
+Инженеры придумали способы «обмануть» кубическую сложность:
+* '''Разложение Нюстрёма (Nyström method).''' Интуиция: вся матрица Грама имеет большой избыток информации. Мы берем случайные <tex>m \ll N</tex> строк и столбцов и по ним приближенно восстанавливаем остальную часть матрицы. Сложность падает до <tex>O(N m^2)</tex>.
+* '''Случайные признаки (Random Fourier Features).''' Вместо того чтобы работать с ядром, мы генерируем случайные <tex>D</tex>-мерные векторы <tex>z(x)</tex> так, что <tex>\kappa(x, x') \approx z(x)^\top z(x')</tex>. После этого применяем обычный быстрый линейный метод. Это превращает ядерный метод в линейный и снижает сложность до <tex>O(N D)</tex>.
+=== Важные математические детали (для углубленного понимания) ===
+* '''Матрица Грама (K) должна быть положительно полуопределенной.''' Это означает, что функция-кандидат в ядра должна давать такую матрицу сходств, у которой нет отрицательных собственных значений. Это гарантирует, что найдется неявное пространство <tex>\mathcal{H}</tex>, где эта матрица будет матрицей скалярных произведений.
+* '''RKHS (Воспроизводящее ядро гильбертова пространства).''' Это математическая конструкция, которая стоит за каждым ядром. Если ядро удовлетворяет условиям, то существует уникальное гильбертово пространство функций, где <tex>f(x) = \langle f, \kappa(\cdot, x) \rangle</tex>. Для практика это означает, что поиск сложной нелинейной функции в этом пространстве сводится к поиску комбинации участков ядра, привязанных к точкам данных.
+=== Современное состояние: ядра и нейронные сети ===
+Ядерные методы и [[Глубокое обучение|глубокие нейросети]] не конкуренты, а взаимодополняющие инструменты.
+* '''Гауссовские процессы''' — это байесовские ядерные методы, незаменимые в задачах оптимизации гиперпараметров (Bayesian Optimization) и всюду, где нужна оценка неопределенности прогноза.
+* '''Neural Tangent Kernel (NTK).''' Современная теория показала, что бесконечно широкая нейронная сеть со случайной инициализацией в процессе градиентного спуска ведет себя в точности как ядерный метод с ядром NTK. Это дало строгий математический мост между двумя мирами и помогает теоретически объяснять успех глубокого обучения.
 == См. также ==
@@ Строка 66: / Строка 100: @@
 * [[Метод опорных векторов]]
 * [[Гауссовский процесс]]
-* [[Воспроизводящее ядро гильбертова пространства]]
 * [[Ядерный анализ главных компонент]]
-* [[Методы аппроксимации ядер]]
+* [[Гребневая регрессия]]
+* [[Проблема проклятия размерности]]
 == Литература ==
-# Schölkopf, B., & Smola, A. J. (2002). ''Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond''. MIT Press.
+# 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).
+# 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).
+# Murphy, K. P. (2012). ''Machine Learning: A Probabilistic Perspective''. MIT Press. (Глава 14: Kernels, с упором на практику и связь с байесовскими методами).
-# Hofmann, T., Schölkopf, B., & Smola, A. J. (2008). Kernel methods in machine learning. ''The Annals of Statistics'', 36(3), 1171–1220.
+# Rahimi, A., & Recht, B. (2007). Random Features for Large-Scale Kernel Machines. ''Advances in Neural Information Processing Systems (NIPS)''. (Революционная статья об аппроксимации ядер).
-# 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)''. (Теория, связывающая ядра и нейросети).
-# Jacot, A., Gabriel, F., & Hongler, C. (2018). Neural Tangent Kernel: Convergence and Generalization in Neural Networks. ''Advances in Neural Information Processing Systems (NeurIPS)''.