Ядро

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

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

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

Содержание

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

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

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

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

Определение и мотивация

Многие классические алгоритмы обучения, такие как метод опорных векторов (SVM) или метод главных компонент (PCA), являются линейными. Они хорошо работают, когда данные линейно разделимы, но терпят неудачу в реальных задачах со сложными зависимостями. Классический подход к решению — явное преобразование входных данных $\mathbf{x} \in \mathcal{X}$ в новое признаковое пространство $\mathcal{H}$ с помощью отображения $\varphi: \mathcal{X} \rightarrow \mathcal{H}$ , где данные становятся линейно разделимыми.

Прямое вычисление $\varphi(\mathbf{x})$ может быть вычислительно невозможным, если пространство $\mathcal{H}$ имеет огромную или даже бесконечную размерность. Однако многие алгоритмы зависят от данных только через скалярные произведения векторов вида $\langle \varphi(\mathbf{x}), \varphi(\mathbf{x}') \rangle$ . Ядро $K$ позволяет вычислить это произведение напрямую, не вычисляя сами отображения:

$K(\mathbf{x}, \mathbf{x}') = \langle \varphi(\mathbf{x}), \varphi(\mathbf{x}') \rangle_{\mathcal{H}}$

Такой прием называется ядерной уловкой (kernel trick).

Формальные свойства

С математической точки зрения, функция $K: \mathcal{X} \times \mathcal{X} \rightarrow \mathbb{R}$ является допустимой для использования в методах, основанных на гильбертовых пространствах с воспроизводящим ядром (RKHS), тогда и только тогда, когда она является симметричной и положительно полуопределенной.

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

Для того чтобы функция $K(\mathbf{x}, \mathbf{y})$ была ядром, необходимо и достаточно, чтобы для любой конечной выборки $\{\mathbf{x}_1, \dots, \mathbf{x}_n\}$ матрица Грама (матрица попарных близостей) $\mathbf{K}$ , определяемая как $K_{ij} = K(\mathbf{x}_i, \mathbf{x}_j)$ , была положительно полуопределенной. Это условие гарантирует существование отображения $\varphi$ и пространства со скалярным произведением, для которых ядро является скалярным произведением.

Основные виды ядер

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

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

Самое простое ядро, соответствующее отсутствию преобразования. $K(\mathbf{x}, \mathbf{x}') = \langle \mathbf{x}, \mathbf{x}' \rangle$ Используется, когда данные и так почти линейно разделимы, или при очень высокой размерности исходного пространства (например, в задачах классификации текстов).

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

Представляет скалярные произведения в пространстве всех мономов степени до $d$ . $K(\mathbf{x}, \mathbf{x}') = (\gamma \langle \mathbf{x}, \mathbf{x}' \rangle + c_0)^d$

Параметры: $d$ — степень полинома, $c_0$ — свободный член (trade-off между влиянием старших и младших степеней), $\gamma$ — коэффициент масштабирования.
Хорошо подходит для данных, где зависимости имеют полиномиальный характер, но склонно к переобучению при больших $d$ .

Гауссово ядро (Radial Basis Function, RBF)

Наиболее популярное универсальное ядро, соответствующее бесконечномерному пространству признаков. $K(\mathbf{x}, \mathbf{x}') = \exp\left( -\gamma \|\mathbf{x} - \mathbf{x}'\|^2 \right)$

Параметр: $\gamma > 0$ (часто задается как $\gamma = \frac{1}{2\sigma^2}$ ). Определяет «радиус влияния» одного примера на другой. При малом $\gamma$ граница решения получается гладкой (недообучение), при большом — сложной, подстраивающейся под каждый выброс (переобучение).
Является универсальным аппроксиматором.

Сигмоидное ядро

$K(\mathbf{x}, \mathbf{x}') = \tanh(\gamma \langle \mathbf{x}, \mathbf{x}' \rangle + c_0)$ Происходит из теории нейронных сетей. Является допустимым (положительно определенным) только при определенных значениях параметров, что ограничивает его применение на практике по сравнению с RBF.

Ядра для специфических структур данных

Мощь ядерного подхода проявляется в возможности задавать сходство для невекторных объектов.

Строковые ядра (String kernels): Измеряют сходство текстов через количество общих подстрок (спектральное ядро) или расстояние Левенштейна.
Ядра на графах (Graph kernels): Вычисляют сходство графов через случайные блуждания (Random Walk kernel) или сравнение подграфов (Weisfeiler-Lehman kernel).
Ядра на вероятностных распределениях: Например, ядро Фишера (Fisher kernel), использующее градиенты логарифмического правдоподобия порождающей модели.

Конструирование ядер

Новые ядра могут быть построены из существующих с помощью набора алгебраических операций, замкнутых относительно свойства положительной определенности:

Сумма: $K(\mathbf{x}, \mathbf{y}) = K_1(\mathbf{x}, \mathbf{y}) + K_2(\mathbf{x}, \mathbf{y})$
Произведение: $K(\mathbf{x}, \mathbf{y}) = K_1(\mathbf{x}, \mathbf{y}) \cdot K_2(\mathbf{x}, \mathbf{y})$
Прямое произведение признаков: $K(\mathbf{x}, \mathbf{y}) = f(\mathbf{x}) f(\mathbf{y})$ для любой вещественной функции $f$ .
Предельный переход: Предел сходящейся последовательности ядер также является ядром.

Применение в алгоритмах

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

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

Классическая задача бинарной классификации. Двойственная задача Лагранжа для поиска разделяющей гиперплоскости формулируется исключительно через скалярные произведения. Замена скалярного произведения на ядро $K$ дает нелинейный классификатор. Решающее правило приобретает вид: $f(\mathbf{x}) = \text{sign}\left( \sum_{i \in \mathcal{S}} \alpha_i y_i K(\mathbf{x}_i, \mathbf{x}) + b \right)$ , где $\mathcal{S}$ — множество опорных векторов.

Ядерный метод главных компонент (Kernel PCA)

Позволяет находить нелинейные многообразия в данных. Вместо анализа ковариационной матрицы исходных данных анализируется матрица Грама $\mathbf{K}$ . Решение сводится к нахождению собственных векторов центрированной матрицы $\mathbf{K}$ , что эквивалентно PCA в пространстве RKHS.

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

Эквивалентна построению линейной регрессии в пространстве признаков с L2-регуляризацией. Решение в замкнутой форме: $\boldsymbol{\alpha} = (\mathbf{K} + \lambda \mathbf{I})^{-1} \mathbf{y}$ , где $\lambda$ — параметр регуляризации. Позволяет строить гладкие нелинейные регрессионные модели.

Гауссовские процессы

В гауссовских процессах ядро (часто называемое ковариационной функцией) определяет гладкость и свойства априорного распределения над функциями. Выбор ядра критичен: RBF-ядро порождает бесконечно дифференцируемые функции, а ядро Матерна позволяет контролировать степень гладкости явно.

Ограничения и практические аспекты

Несмотря на элегантность, ядерные методы обладают недостатками:

Вычислительная сложность: Прямые методы требуют обращения матрицы Грама размером $n \times n$ , что приводит к сложности $O(n^3)$ и памяти $O(n^2)$ . Это делает их неприменимыми к миллионам объектов без аппроксимаций (например, Nyström method, Random Fourier Features).
Выбор ядра и гиперпараметров: Критически важен и обычно осуществляется через кросс-валидацию (grid search). Неудачный выбор $\gamma$ в RBF легко ведет к переобучению.
Интерпретируемость: Модель в неявном пространстве RKHS трудно интерпретировать, в отличие от разреженных линейных моделей на исходных признаках.

Литература

Schölkopf, B., Smola, A. J. Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond. — MIT Press, 2002. (Классический фундаментальный труд).
Bishop, C. M. Pattern Recognition and Machine Learning. — Springer, 2006. — Глава 6: Kernel Methods.
Hofmann, T., Schölkopf, B., Smola, A. J. Kernel methods in machine learning // The Annals of Statistics. — 2008. — Т. 36, № 3. — С. 1171–1220.
Rasmussen, C. E., Williams, C. K. I. Gaussian Processes for Machine Learning. — MIT Press, 2006.
Вьюгин, В. В. Математические основы теории машинного обучения и прогнозирования. — МЦНМО, 2013.

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

@@ Строка 1: / Строка 1: @@
-'''Ядро''' (англ. kernel) в контексте [[Машинное обучение|машинного обучения]] — это функция, позволяющая выполнять вычисления в неявном высокоразмерном пространстве признаков без явного отображения исходных данных в это пространство. Это фундаментальная концепция, лежащая в основе [[Метод опорных векторов|метода опорных векторов]] (SVM) и других [[Ядерные методы|ядерных методов]], позволяющая эффективно моделировать нелинейные зависимости с помощью линейных алгоритмов.
+== Ядра в машинном обучении ==
-== Неформальное введение и проблема линейной разделимости ==
+'''Ядро''' (kernel) в контексте машинного обучения — это функция, задающая меру сходства или скалярное произведение между двумя объектами в некотором, часто неявном, спрямляющем пространстве признаков. Это фундаментальная концепция, позволяющая применять линейные алгоритмы к решению существенно нелинейных задач, избегая прямых вычислений в пространствах высокой размерности (так называемый ''kernel trick'').
-Многие классические алгоритмы обучения (например, [[Логистическая регрессия|логистическая регрессия]] или [[Перцептрон|перцептрон]]) являются линейными. Они строят разделяющую гиперплоскость в пространстве признаков. Однако реальные данные редко бывают линейно разделимы в исходном пространстве <math>\mathcal{X}</math> (например, задача [[Исключающее ИЛИ|XOR]]).
-Стандартный подход к решению этой проблемы — обогащение данных: исходный вектор <math>\mathbf{x} \in \mathcal{X}</math> явно отображается в пространство более высокой размерности <math>\mathcal{H}</math> с помощью функции <math>\phi: \mathcal{X} \to \mathcal{H}</math>. Если размерность <math>\mathcal{H}</math> достаточно велика, данные с высокой вероятностью станут линейно разделимыми. Проблема этого подхода (проклятие размерности и вычислительная сложность) снимается с помощью «трюка с ядром» (kernel trick).
+Не следует путать данное понятие с [[Свёртка (машинное обучение)|ядрами свёртки]] в [[Свёрточная нейронная сеть|свёрточных нейронных сетях]], где термин обозначает матрицу весов фильтра.
-== Определение ==
+=== Определение и мотивация ===
-Пусть <math>\mathcal{X}</math> — непустое множество исходных объектов. Функция <math>K: \mathcal{X} \times \mathcal{X} \to \mathbb{R}</math> называется '''ядром''', если существует [[Гильбертово пространство|гильбертово пространство]] <math>\mathcal{H}</math> (называемое пространством признаков) и отображение <math>\phi: \mathcal{X} \to \mathcal{H}</math>, такие что для любых <math>\mathbf{x}, \mathbf{x}' \in \mathcal{X}</math>:
-<center><math>K(\mathbf{x}, \mathbf{x}') = \langle \phi(\mathbf{x}), \phi(\mathbf{x}') \rangle_{\mathcal{H}}</math></center>
-где <math>\langle \cdot, \cdot \rangle_{\mathcal{H}}</math> — скалярное произведение в пространстве <math>\mathcal{H}</math>.
-== Трюк с ядром (Kernel Trick) ==
+Многие классические алгоритмы обучения, такие как [[метод опорных векторов]] (SVM) или [[метод главных компонент]] (PCA), являются линейными. Они хорошо работают, когда данные [[Линейная разделимость|линейно разделимы]], но терпят неудачу в реальных задачах со сложными зависимостями. Классический подход к решению — явное преобразование входных данных <tex>\mathbf{x} \in \mathcal{X}</tex> в новое признаковое пространство <tex>\mathcal{H}</tex> с помощью отображения <tex>\varphi: \mathcal{X} \rightarrow \mathcal{H}</tex>, где данные становятся линейно разделимыми.
-Ключевая идея использования ядер заключается в том, что во многих алгоритмах машинного обучения векторы признаков входят только в виде операций скалярного произведения <math>\langle \mathbf{x}_i, \mathbf{x}_j \rangle</math>.
-*   '''Линейная модель:''' <math>f(\mathbf{x}) = \mathbf{w}^T\mathbf{x} + b</math>. После оптимизации веса представляются как <math>\mathbf{w} = \sum_i \alpha_i \mathbf{x}_i</math>, и решающее правило примет вид <math>f(\mathbf{x}) = \sum_i \alpha_i \langle \mathbf{x}_i, \mathbf{x} \rangle + b</math>.
-*   '''Нелинейное обобщение:''' Заменим исходные векторы на их образы: <math>f(\mathbf{x}) = \sum_i \alpha_i \langle \phi(\mathbf{x}_i), \phi(\mathbf{x}) \rangle + b</math>.
-Трюк с ядром позволяет вычислить это выражение напрямую как <math>f(\mathbf{x}) = \sum_i \alpha_i K(\mathbf{x}_i, \mathbf{x}) + b</math>, '''никогда не вычисляя''' координаты векторов <math>\phi(\mathbf{x})</math> в явном виде. Это дает возможность работать с пространствами признаков бесконечной размерности (например, используя [[Гауссовское ядро|RBF-ядро]]).
-== Функция Мерсера и свойства ==
+Прямое вычисление <tex>\varphi(\mathbf{x})</tex> может быть вычислительно невозможным, если пространство <tex>\mathcal{H}</tex> имеет огромную или даже бесконечную размерность. Однако многие алгоритмы зависят от данных только через скалярные произведения векторов вида <tex>\langle \varphi(\mathbf{x}), \varphi(\mathbf{x}') \rangle</tex>. Ядро <tex>K</tex> позволяет вычислить это произведение напрямую, не вычисляя сами отображения:
-Не любая функция двух переменных является ядром. Для того чтобы функция <math>K</math> была корректным ядром в рамках [[Теория статистического обучения|теории статистического обучения]], она должна удовлетворять условиям '''теоремы Мерсера''' (для пространств со скалярным произведением), что эквивалентно положительной полуопределенности.
-Для любого конечного набора точек <math>\{\mathbf{x}_1, \dots, \mathbf{x}_n\} \subset \mathcal{X}</math> '''матрица Грама''' <math>\mathbf{K}</math>, определенная как <math>K_{ij} = K(\mathbf{x}_i, \mathbf{x}_j)</math>, должна быть симметричной и неотрицательно определенной.
-Из этого свойства вытекают правила построения новых ядер из существующих (исчисление ядер):
+<tex>K(\mathbf{x}, \mathbf{x}') = \langle \varphi(\mathbf{x}), \varphi(\mathbf{x}') \rangle_{\mathcal{H}}</tex>
-*   Сумма ядер: <math>K = K_1 + K_2</math> — ядро.
-*   Произведение ядер: <math>K = K_1 \cdot K_2</math> — ядро.
-*   Умножение на константу: <math>K = c \cdot K_1, c > 0</math> — ядро.
-== Основные семейства ядер ==
+Такой прием называется '''ядерной уловкой''' (kernel trick).
-=== Стационарные ядра ===
+=== Формальные свойства ===
-Ядра этой группы зависят только от разности аргументов: <math>K(\mathbf{x}, \mathbf{x}') = K(\mathbf{x} - \mathbf{x}')</math>. Часто рассматриваются как функции от расстояния (ядра радиального базиса).
-*   '''Гауссовское ядро (RBF):''' <math>K(\mathbf{x}, \mathbf{x}') = \exp\left(-\frac{\|\mathbf{x} - \mathbf{x}'\|^2}{2\sigma^2}\right)</math>. Самое популярное ядро, соответствующее бесконечномерному пространству признаков. Параметр <math>\sigma</math> (ширина окна) управляет гладкостью границы решений.
+С математической точки зрения, функция <tex>K: \mathcal{X} \times \mathcal{X} \rightarrow \mathbb{R}</tex> является допустимой для использования в методах, основанных на [[Воспроизводящее ядро гильбертова пространства|гильбертовых пространствах с воспроизводящим ядром]] (RKHS), тогда и только тогда, когда она является симметричной и положительно полуопределенной.
-*   '''Ядро Лапласа:''' <math>K(\mathbf{x}, \mathbf{x}') = \exp\left(-\frac{\|\mathbf{x} - \mathbf{x}'\|}{\sigma}\right)</math>. Менее чувствительно к выбросам по сравнению с гауссовским.
-*   '''Рациональное квадратичное ядро:''' <math>K(\mathbf{x}, \mathbf{x}') = 1 - \frac{\|\mathbf{x} - \mathbf{x}'\|^2}{\|\mathbf{x} - \mathbf{x}'\|^2 + c}</math>. Представляет собой смесь RBF-ядер с разными масштабами.
-=== Нестационарные ядра ===
+==== Теорема Мерсера ====
-*   '''Полиномиальное ядро:''' <math>K(\mathbf{x}, \mathbf{x}') = (\langle \mathbf{x}, \mathbf{x}' \rangle + c)^d</math>. Позволяет строить полиномиальные разделяющие поверхности степени <math>d</math>. Параметр <math>c \ge 0</math> регулирует вес старших и младших степеней.
+Для того чтобы функция <tex>K(\mathbf{x}, \mathbf{y})</tex> была ядром, необходимо и достаточно, чтобы для любой конечной выборки <tex>\{\mathbf{x}_1, \dots, \mathbf{x}_n\}</tex> матрица Грама (матрица попарных близостей) <tex>\mathbf{K}</tex>, определяемая как <tex>K_{ij} = K(\mathbf{x}_i, \mathbf{x}_j)</tex>, была положительно полуопределенной. Это условие гарантирует существование отображения <tex>\varphi</tex> и пространства со скалярным произведением, для которых ядро является скалярным произведением.
-*   '''Сигмоидное ядро:''' <math>K(\mathbf{x}, \mathbf{x}') = \tanh(\kappa \langle \mathbf{x}, \mathbf{x}' \rangle + \theta)</math>. Исторически связано с нейронными сетями, однако матрица Грама для него положительно определена лишь при определенных значениях параметров.
-=== Ядра для специфических структур данных ===
+=== Основные виды ядер ===
-Метод ядер не ограничивается векторными пространствами, что является его огромным преимуществом. Ядро можно определить на любом типе объектов, если удалось задать подходящую меру сходства.
-*   '''Строковые ядра (String Kernels):''' Измеряют сходство строк через количество общих подстрок (спектральное ядро, ядро с пропусками). Используются в [[Биоинформатика|биоинформатике]] и [[Обработка естественного языка|NLP]].
-*   '''Ядра на графах:''' Например, Random Walk Kernel подсчитывает количество общих маршрутов в двух графах. Применяются в [[Хемоинформатика|хемоинформатике]] для предсказания свойств молекул.
-*   '''Ядра Фишера:''' Строятся на основе вероятностных порождающих моделей, позволяя применять SVM к данным, хорошо описываемым скрытыми марковскими моделями.
-== Применение в классических алгоритмах ==
+Выбор ядра определяет геометрию пространства признаков и гипотезы о данных. Наиболее распространены следующие семейства.
-Хотя термин «kernel trick» ассоциируется в первую очередь с [[Метод опорных векторов|SVM]], он применим к любому алгоритму, который можно выразить через скалярные произведения. Это утверждение носит название '''теоремы о представимости''' (Representer Theorem).
-*   '''SVM с мягким зазором (C-SVM):''' Классический пример, где замена скалярного произведения на ядро <math>K</math> превращает линейный классификатор в нелинейный.
-*   '''Гребневая регрессия (Kernel Ridge Regression):''' Нелинейный вариант [[Гребневая регрессия|регуляризованной линейной регрессии]], полезный для восстановления регрессионных зависимостей малой размерности выборки.
-*   '''Метод главных компонент (Kernel PCA):''' Выполняет анализ главных компонент в пространстве <math>\mathcal{H}</math>, что позволяет выявлять нелинейные структуры в данных ([[Многообразие|многообразия]]).
-*   '''Kernel K-Means:''' Кластеризация данных, разделимых нелинейными границами, путем переноса центроидов в пространство признаков.
-== Связь с гауссовскими процессами ==
+==== Линейное ядро ====
-В [[Гауссовские процессы|гауссовских процессах]] (GP) ядро играет роль ковариационной функции и определяет априорные предположения о свойствах моделируемой функции (гладкость, периодичность, стационарность). В этом контексте выбор ядра — это способ кодирования знаний о предметной области в модель. Часто используемые в GP ядра (Матерна, экспоненциальное, периодическое) имеют прямые аналоги в ядерных методах, таких как SVM, но интерпретируются с вероятностной точки зрения.
+Самое простое ядро, соответствующее отсутствию преобразования.
+<tex>K(\mathbf{x}, \mathbf{x}') = \langle \mathbf{x}, \mathbf{x}' \rangle</tex>
+Используется, когда данные и так почти линейно разделимы, или при очень высокой размерности исходного пространства (например, в задачах классификации текстов).
-== Практические аспекты и выбор ядра ==
+==== Полиномиальное ядро ====
-Выбор ядра и его гиперпараметров критически важен:
+Представляет скалярные произведения в пространстве всех мономов степени до <tex>d</tex>.
-*   '''Переобучение:''' Слишком маленькая <math>\sigma</math> в RBF-ядре ведет к обобщению по принципу «один ближайший сосед» (переобучение), а слишком большая — к вырождению в линейную границу.
+<tex>K(\mathbf{x}, \mathbf{x}') = (\gamma \langle \mathbf{x}, \mathbf{x}' \rangle + c_0)^d</tex>
-*   '''Масштабируемость:''' Вычисление матрицы Грама размера <math>n \times n</math> требует <math>O(n^2)</math> памяти и <math>O(n^3)</math> времени для обращения (или <math>O(n^2)</math> для SVM). Это делает наивные ядерные методы неприменимыми к «большим данным». Проблема решается с помощью аппроксимаций:
+* '''Параметры:''' <tex>d</tex> — степень полинома, <tex>c_0</tex> — свободный член (trade-off между влиянием старших и младших степеней), <tex>\gamma</tex> — коэффициент масштабирования.
-**   '''Случайные признаки (Random Fourier Features):''' Аппроксимация стационарных ядер через прямое преобразование Фурье.
+* Хорошо подходит для данных, где зависимости имеют полиномиальный характер, но склонно к переобучению при больших <tex>d</tex>.
-**   '''Метод Найстрома (Nyström Method):''' Низкоранговая аппроксимация матрицы Грама на основе подвыборки столбцов.
-== См. также ==
+==== Гауссово ядро (Radial Basis Function, RBF) ====
-*   [[Метод опорных векторов]] (SVM)
+Наиболее популярное универсальное ядро, соответствующее бесконечномерному пространству признаков.
-*   [[Гауссовские процессы]]
+<tex>K(\mathbf{x}, \mathbf{x}') = \exp\left( -\gamma \|\mathbf{x} - \mathbf{x}'\|^2 \right)</tex>
-*   [[Проблема "проклятия размерности"]]
+* '''Параметр:''' <tex>\gamma > 0</tex> (часто задается как <tex>\gamma = \frac{1}{2\sigma^2}</tex>). Определяет «радиус влияния» одного примера на другой. При малом <tex>\gamma</tex> граница решения получается гладкой (недообучение), при большом — сложной, подстраивающейся под каждый выброс (переобучение).
-*   [[Воспроизводящее ядро гильбертова пространства]] (RKHS)
+* Является универсальным аппроксиматором.
-== Литература ==
+==== Сигмоидное ядро ====
-# Schölkopf, B., & Smola, A. J. (2002). ''Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond''. MIT Press.
+<tex>K(\mathbf{x}, \mathbf{x}') = \tanh(\gamma \langle \mathbf{x}, \mathbf{x}' \rangle + c_0)</tex>
-# Bishop, C. M. (2006). ''Pattern Recognition and Machine Learning''. Chapter 6: Kernel Methods. Springer.
+Происходит из теории нейронных сетей. Является допустимым (положительно определенным) только при определенных значениях параметров, что ограничивает его применение на практике по сравнению с RBF.
-# Murphy, K. P. (2012). ''Machine Learning: A Probabilistic Perspective''. Chapter 14: Kernels. MIT Press.
-# Rasmussen, C. E., & Williams, C. K. I. (2006). ''Gaussian Processes for Machine Learning''. Chapter 4: Covariance Functions. MIT Press.
+==== Ядра для специфических структур данных ====
-# Mercer, J. (1909). "Functions of positive and negative type, and their connection with the theory of integral equations". ''Philosophical Transactions of the Royal Society A'', 209, pp. 415–446.
+Мощь ядерного подхода проявляется в возможности задавать сходство для невекторных объектов.
+* '''Строковые ядра (String kernels):''' Измеряют сходство текстов через количество общих подстрок (спектральное ядро) или расстояние Левенштейна.
+* '''Ядра на графах (Graph kernels):''' Вычисляют сходство графов через случайные блуждания (Random Walk kernel) или сравнение подграфов (Weisfeiler-Lehman kernel).
+* '''Ядра на вероятностных распределениях:''' Например, ядро Фишера (Fisher kernel), использующее градиенты логарифмического правдоподобия порождающей модели.
+=== Конструирование ядер ===
+Новые ядра могут быть построены из существующих с помощью набора алгебраических операций, замкнутых относительно свойства положительной определенности:
+# '''Сумма:''' <tex>K(\mathbf{x}, \mathbf{y}) = K_1(\mathbf{x}, \mathbf{y}) + K_2(\mathbf{x}, \mathbf{y})</tex>
+# '''Произведение:''' <tex>K(\mathbf{x}, \mathbf{y}) = K_1(\mathbf{x}, \mathbf{y}) \cdot K_2(\mathbf{x}, \mathbf{y})</tex>
+# '''Прямое произведение признаков:''' <tex>K(\mathbf{x}, \mathbf{y}) = f(\mathbf{x}) f(\mathbf{y})</tex> для любой вещественной функции <tex>f</tex>.
+# '''Предельный переход:''' Предел сходящейся последовательности ядер также является ядром.
+=== Применение в алгоритмах ===
+Хотя ядерный трюк наиболее известен по SVM, он пронизывает все области машинного обучения.
+==== Метод опорных векторов (SVM) ====
+Классическая задача бинарной классификации. Двойственная задача Лагранжа для поиска разделяющей гиперплоскости формулируется исключительно через скалярные произведения. Замена скалярного произведения на ядро <tex>K</tex> дает нелинейный классификатор. Решающее правило приобретает вид:
+<tex>f(\mathbf{x}) = \text{sign}\left( \sum_{i \in \mathcal{S}} \alpha_i y_i K(\mathbf{x}_i, \mathbf{x}) + b \right)</tex>,
+где <tex>\mathcal{S}</tex> — множество опорных векторов.
+==== Ядерный метод главных компонент (Kernel PCA) ====
+Позволяет находить нелинейные многообразия в данных. Вместо анализа ковариационной матрицы исходных данных анализируется матрица Грама <tex>\mathbf{K}</tex>. Решение сводится к нахождению собственных векторов центрированной матрицы <tex>\mathbf{K}</tex>, что эквивалентно PCA в пространстве RKHS.
+==== Ядерная регрессия (Kernel Ridge Regression) ====
+Эквивалентна построению линейной регрессии в пространстве признаков с L2-регуляризацией. Решение в замкнутой форме:
+<tex>\boldsymbol{\alpha} = (\mathbf{K} + \lambda \mathbf{I})^{-1} \mathbf{y}</tex>,
+где <tex>\lambda</tex> — параметр регуляризации. Позволяет строить гладкие нелинейные регрессионные модели.
+==== Гауссовские процессы ====
+В [[Гауссовский процесс|гауссовских процессах]] ядро (часто называемое ковариационной функцией) определяет гладкость и свойства априорного распределения над функциями. Выбор ядра критичен: RBF-ядро порождает бесконечно дифференцируемые функции, а ядро Матерна позволяет контролировать степень гладкости явно.
+=== Ограничения и практические аспекты ===
+Несмотря на элегантность, ядерные методы обладают недостатками:
+* '''Вычислительная сложность:''' Прямые методы требуют обращения матрицы Грама размером <tex>n \times n</tex>, что приводит к сложности <tex>O(n^3)</tex> и памяти <tex>O(n^2)</tex>. Это делает их неприменимыми к миллионам объектов без аппроксимаций (например, Nyström method, Random Fourier Features).
+* '''Выбор ядра и гиперпараметров:''' Критически важен и обычно осуществляется через [[кросс-валидация|кросс-валидацию]] (grid search). Неудачный выбор <tex>\gamma</tex> в RBF легко ведет к переобучению.
+* '''Интерпретируемость:''' Модель в неявном пространстве RKHS трудно интерпретировать, в отличие от разреженных линейных моделей на исходных признаках.
+=== Литература ===
+# Schölkopf, B., Smola, A. J. ''Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond''. — MIT Press, 2002. (Классический фундаментальный труд).
+# Bishop, C. M. ''Pattern Recognition and Machine Learning''. — Springer, 2006. — Глава 6: Kernel Methods.
+# Hofmann, T., Schölkopf, B., Smola, A. J. ''Kernel methods in machine learning'' // The Annals of Statistics. — 2008. — Т. 36, № 3. — С. 1171–1220.
+# Rasmussen, C. E., Williams, C. K. I. ''Gaussian Processes for Machine Learning''. — MIT Press, 2006.
+# Вьюгин, В. В. ''Математические основы теории машинного обучения и прогнозирования''. — МЦНМО, 2013.