Ядро

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

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

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

Содержание

1 Ядра в машинном обучении
2 Интуитивное введение
3 Формальное определение
4 Теорема Мерсера и положительная определенность
5 Основные свойства ядер и конструирование
6 Примеры стандартных ядер
7 Ядерный трюк в действии: пример ядерной гребневой регрессии
8 Практические аспекты и выбор ядра
9 Заключение
10 См. также
11 Литература

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

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

Интуитивное введение

Многие классические алгоритмы машинного обучения, такие как Логистическая регрессия или базовый SVM, являются линейными. Они способны строить лишь линейные разделяющие поверхности или линейные зависимости, что часто недостаточно для реальных данных. Традиционный подход к решению этой проблемы заключается в ручном конструировании новых, нелинейных признаков (например, полиномиальных признаков $x_1^2, x_1 x_2, x_2^2$ ) и последующем применении линейного алгоритма. Однако такой подход быстро становится вычислительно нереализуемым из-за "проклятия размерности", особенно если требуется отображение в пространство очень высокой или бесконечной размерности. Ядерный трюк предлагает элегантный обходной путь, заменяя все операции с координатами в расширенном пространстве вычислением специальной функции от исходных векторов.

Формальное определение

Функция двух переменных $\kappa: \mathcal{X} \times \mathcal{X} \to \mathbb{R}$ , где $\mathcal{X}$ — некоторое исходное пространство объектов, называется ядром, если существует гильбертово пространство $\mathcal{H}$ (называемое воспроизводящим ядром гильбертовым пространством, RKHS) и отображение $\varphi: \mathcal{X} \to \mathcal{H}$ , такие что для любых $\mathbf{x}, \mathbf{x}' \in \mathcal{X}$ выполняется:

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

Ключевой момент здесь в том, что алгоритм, выраженный исключительно через скалярные произведения векторов, может быть "кирнелизован" простой заменой всех вхождений $\langle \mathbf{x}_i, \mathbf{x}_j \rangle$ на $\kappa(\mathbf{x}_i, \mathbf{x}_j)$ . Это эквивалентно неявному применению алгоритма в пространстве $\mathcal{H}$ , но все вычисления остаются в исходном пространстве $\mathcal{X}$ , завися только от размера выборки, а не от размерности $\mathcal{H}$ .

Теорема Мерсера и положительная определенность

Критерием того, что функция $\kappa$ является допустимым ядром в некотором гильбертовом пространстве, служит теорема Мерсера (для компактных пространств). На практике используется более общее и конструктивное определение: функция $\kappa$ является ядром тогда и только тогда, когда она симметрична ( $\kappa(\mathbf{x}, \mathbf{x}') = \kappa(\mathbf{x}', \mathbf{x})$ ) и порождаемая ею матрица Грама $\mathbf{K}$ является неотрицательно определенной (положительно полуопределенной) для любого конечного набора точек $\{\mathbf{x}_1, \dots, \mathbf{n}\}$ . Матрица $\mathbf{K}$ имеет элементы $K_{ij} = \kappa(\mathbf{x}_i, \mathbf{x}_j)$ , и условие неотрицательной определенности означает, что для любого вектора $\mathbf{c} \in \mathbb{R}^n$ выполняется $\mathbf{c}^T \mathbf{K} \mathbf{c} \ge 0$ . Это условие гарантирует, что функция ядра неявно соответствует скалярному произведению в некотором, возможно, бесконечномерном, пространстве.

Основные свойства ядер и конструирование

Множество допустимых ядер замкнуто относительно ряда операций, что позволяет конструировать сложные ядра из простых "вручную", учитывая специфику данных. Если $\kappa_1, \kappa_2$ — ядра на $\mathcal{X}$ , $a > 0$ , $f: \mathcal{X} \to \mathbb{R}$ , $\mathbf{A}$ — положительно определенная матрица, то следующие функции также являются ядрами:

$\kappa(\mathbf{x}, \mathbf{x}') = \kappa_1(\mathbf{x}, \mathbf{x}') + \kappa_2(\mathbf{x}, \mathbf{x}')$ (сумма ядер)
$\kappa(\mathbf{x}, \mathbf{x}') = a \cdot \kappa_1(\mathbf{x}, \mathbf{x}')$ (умножение на положительную константу)
$\kappa(\mathbf{x}, \mathbf{x}') = \kappa_1(\mathbf{x}, \mathbf{x}') \cdot \kappa_2(\mathbf{x}, \mathbf{x}')$ (произведение ядер)
$\kappa(\mathbf{x}, \mathbf{x}') = f(\mathbf{x}) \kappa_1(\mathbf{x}, \mathbf{x}') f(\mathbf{x}')$ (нормализация)
$\kappa(\mathbf{x}, \mathbf{x}') = \mathbf{x}^T \mathbf{A} \mathbf{x}'$ (ядро с учетом линейного преобразования признаков)

Примеры стандартных ядер

Рассмотрим наиболее распространенные семейства ядер, используемые на практике для данных в виде векторов $\mathbf{x}, \mathbf{x}' \in \mathbb{R}^d$ .

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

$\kappa(\mathbf{x}, \mathbf{x}') = \langle \mathbf{x}, \mathbf{x}' \rangle = \mathbf{x}^T \mathbf{x}'$ Простейшее ядро, соответствующее тождественному отображению $\varphi(\mathbf{x}) = \mathbf{x}$ . Приводит к обычному линейному алгоритму. Полезно как базовый случай и для задач с высокой размерностью, где линейная разделимость уже достигнута.

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

$\kappa(\mathbf{x}, \mathbf{x}') = (\gamma \langle \mathbf{x}, \mathbf{x}' \rangle + c)^d$ где $d \in \mathbb{N}$ — степень полинома, $\gamma > 0$ — коэффициент масштабирования, $c \ge 0$ — свободный член. Это ядро соответствует пространству всех мономиальных признаков степени вплоть до $d$ . Оно позволяет улавливать полиномиальные взаимодействия между исходными признаками.

Радиально-базисное ядро (Гауссово, RBF)

$\kappa(\mathbf{x}, \mathbf{x}') = \exp\left( -\gamma \|\mathbf{x} - \mathbf{x}'\|^2 \right)$ где $\gamma > 0$ — параметр ширины ядра. Это одно из самых популярных ядер. Оно соответствует бесконечномерному признаковому пространству и может моделировать чрезвычайно сложные, локальные зависимости. Параметр $\gamma$ контролирует "радиус влияния" одного примера: большое значение приводит к переобучению (гибкая, изрезанная граница), маленькое — к недообучению (почти линейная граница).

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

$\kappa(\mathbf{x}, \mathbf{x}') = \tanh(\gamma \langle \mathbf{x}, \mathbf{x}' \rangle + c)$ Данное ядро происходит из области нейронных сетей. Однако оно является допустимым (положительно определенным) только для некоторых значений параметров $\gamma, c$ , что ограничивает его прямое использование в строгой ядерной теории, хотя на практике оно иногда применяется.

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

Ядерный подход не ограничивается векторами из $\mathbb{R}^d$ . Существуют ядра, определенные на строках (на основе расстояния редактирования), графах (ядро случайных блужданий, random walk kernel), множествах, деревьях и других сложных объектах. Это позволяет применять весь арсенал ядерных методов к задачам биоинформатики, обработки текстов и хемоинформатики.

Ядерный трюк в действии: пример ядерной гребневой регрессии

Рассмотрим задачу линейной регрессии с квадратичной функцией потерь и L2-регуляризацией (гребневая регрессия). Решение в терминах исходных признаков дается формулой $\mathbf{w} = (\mathbf{X}^T\mathbf{X} + \lambda \mathbf{I})^{-1}\mathbf{X}^T\mathbf{y}$ . Используя матричное тождество, его можно переписать в "дуальную форму", зависящую только от скалярных произведений $\mathbf{X}\mathbf{X}^T$ : $\mathbf{y}_{\text{pred}}(\mathbf{x}_{\text{new}}) = \mathbf{y}^T (\mathbf{K} + \lambda \mathbf{I})^{-1} \mathbf{k}$ , где $\mathbf{K}$ — матрица Грама на обучающей выборке, а вектор $\mathbf{k}$ состоит из ядерных оценок $\kappa(\mathbf{x}_i, \mathbf{x}_{\text{new}})$ . Замена всех скалярных произведений на функцию ядра дает нелинейную ядерную гребневую регрессию, способную аппроксимировать сложные нелинейные функции.

Практические аспекты и выбор ядра

Выбор ядра и его параметров — центральная задача при использовании ядерных методов.

Выбор типа ядра: Обычно начинают с линейного ядра как с интерпретируемого baseline. Если оно не дает нужного качества, переходят к RBF-ядру, которое является универсальным аппроксиматором и хорошим выбором "по умолчанию" для нелинейных задач средней размерности. Специфические ядра (например, для графов) выбирают, исходя из природы данных.
Настройка гиперпараметров: Критически важна. Осуществляется через кросс-валидацию. Для RBF-ядра настраивают $\gamma$ (и параметр регуляризации $C$ в SVM). Распространенная эвристика для $\gamma$ в RBF — установка обратно пропорционально медиане попарных евклидовых расстояний между объектами.
Нормализация данных: Перед применением ядер, чувствительных к масштабу признаков (особенно RBF и полиномиального), необходимо проводить стандартизацию признаков (вычитание среднего, деление на стандартное отклонение).
Вычислительная сложность: Основной недостаток ядерных методов — необходимость вычисления и хранения матрицы Грама $\mathbf{K}$ размера $n \times n$ , где $n$ — число объектов в обучающей выборке. Это требует $O(n^2)$ памяти и, как правило, $O(n^3)$ времени для обращения матрицы, что делает методы непрактичными для больших наборов данных ( $n > 10^5$ ). Для преодоления этого ограничения разработаны различные методы аппроксимации (например, метод случайных признаков, аппроксимация Найстрома).

Заключение

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

См. также

Литература

Шлезингер М., Главач В. Десять лекций по статистическому и структурному распознаванию. — Киев: Наукова думка, 2004. — Глава о ядерных методах.
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.
Shawe-Taylor J., Cristianini N. Kernel Methods for Pattern Analysis. — Cambridge University Press, 2004. — Всеобъемлющее введение в ядерные методы анализа закономерностей.
Murphy K. P. Machine Learning: A Probabilistic Perspective. — MIT Press, 2012. — Глава 14: Kernels.

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

@@ Строка 1: / Строка 1: @@
 == Ядра в машинном обучении ==
-'''Ядро''' (kernel) в контексте машинного обучения — это функция, задающая меру сходства или скалярное произведение между двумя объектами в некотором, часто неявном, спрямляющем пространстве признаков. Это фундаментальная концепция, позволяющая применять линейные алгоритмы к решению существенно нелинейных задач, избегая прямых вычислений в пространствах высокой размерности (так называемый ''kernel trick'').
+'''Ядро''' (англ. ''kernel'') в контексте [[Машинное обучение|машинного обучения]] — это функция, позволяющая вычислять скалярное произведение образов двух объектов в некотором, возможно, бесконечномерном, [[Признаковое пространство|признаковом пространстве]] без явного отображения объектов в это пространство. Этот приём, известный как '''kernel trick''' (ядерный трюк), лежит в основе множества алгоритмов, позволяя им эффективно выявлять нелинейные закономерности в данных, оставаясь при этом вычислительно реализуемыми. Ядра являются фундаментальным инструментом в таких методах, как [[Метод опорных векторов]], [[Гребневая регрессия|ядерная гребневая регрессия]] и [[Анализ главных компонент|ядерный метод главных компонент]].
-Не следует путать данное понятие с [[Свёртка (машинное обучение)|ядрами свёртки]] в [[Свёрточная нейронная сеть|свёрточных нейронных сетях]], где термин обозначает матрицу весов фильтра.
+== Интуитивное введение ==
+Многие классические алгоритмы машинного обучения, такие как [[Логистическая регрессия]] или базовый [[Метод опорных векторов|SVM]], являются линейными. Они способны строить лишь линейные разделяющие поверхности или линейные зависимости, что часто недостаточно для реальных данных. Традиционный подход к решению этой проблемы заключается в ручном конструировании новых, нелинейных признаков (например, полиномиальных признаков <tex>x_1^2, x_1 x_2, x_2^2</tex>) и последующем применении линейного алгоритма. Однако такой подход быстро становится вычислительно нереализуемым из-за "проклятия размерности", особенно если требуется отображение в пространство очень высокой или бесконечной размерности. Ядерный трюк предлагает элегантный обходной путь, заменяя все операции с координатами в расширенном пространстве вычислением специальной функции от исходных векторов.
-=== Определение и мотивация ===
+== Формальное определение ==
+Функция двух переменных <tex>\kappa: \mathcal{X} \times \mathcal{X} \to \mathbb{R}</tex>, где <tex>\mathcal{X}</tex> — некоторое исходное пространство объектов, называется '''ядром''', если существует [[Гильбертово пространство|гильбертово пространство]] <tex>\mathcal{H}</tex> (называемое [[Воспроизводящее ядро гильбертова пространства|воспроизводящим ядром гильбертовым пространством]], RKHS) и отображение <tex>\varphi: \mathcal{X} \to \mathcal{H}</tex>, такие что для любых <tex>\mathbf{x}, \mathbf{x}' \in \mathcal{X}</tex> выполняется:
-Многие классические алгоритмы обучения, такие как [[метод опорных векторов]] (SVM) или [[метод главных компонент]] (PCA), являются линейными. Они хорошо работают, когда данные [[Линейная разделимость|линейно разделимы]], но терпят неудачу в реальных задачах со сложными зависимостями. Классический подход к решению — явное преобразование входных данных <tex>\mathbf{x} \in \mathcal{X}</tex> в новое признаковое пространство <tex>\mathcal{H}</tex> с помощью отображения <tex>\varphi: \mathcal{X} \rightarrow \mathcal{H}</tex>, где данные становятся линейно разделимыми.
+<tex>\kappa(\mathbf{x}, \mathbf{x}') = \langle \varphi(\mathbf{x}), \varphi(\mathbf{x}') \rangle_{\mathcal{H}}</tex>
-Прямое вычисление <tex>\varphi(\mathbf{x})</tex> может быть вычислительно невозможным, если пространство <tex>\mathcal{H}</tex> имеет огромную или даже бесконечную размерность. Однако многие алгоритмы зависят от данных только через скалярные произведения векторов вида <tex>\langle \varphi(\mathbf{x}), \varphi(\mathbf{x}') \rangle</tex>. Ядро <tex>K</tex> позволяет вычислить это произведение напрямую, не вычисляя сами отображения:
+Ключевой момент здесь в том, что алгоритм, выраженный исключительно через скалярные произведения векторов, может быть "кирнелизован" простой заменой всех вхождений <tex>\langle \mathbf{x}_i, \mathbf{x}_j \rangle</tex> на <tex>\kappa(\mathbf{x}_i, \mathbf{x}_j)</tex>. Это эквивалентно неявному применению алгоритма в пространстве <tex>\mathcal{H}</tex>, но все вычисления остаются в исходном пространстве <tex>\mathcal{X}</tex>, завися только от размера выборки, а не от размерности <tex>\mathcal{H}</tex>.
-<tex>K(\mathbf{x}, \mathbf{x}') = \langle \varphi(\mathbf{x}), \varphi(\mathbf{x}') \rangle_{\mathcal{H}}</tex>
+== Теорема Мерсера и положительная определенность ==
+Критерием того, что функция <tex>\kappa</tex> является допустимым ядром в некотором гильбертовом пространстве, служит '''теорема Мерсера''' (для компактных пространств). На практике используется более общее и конструктивное определение: функция <tex>\kappa</tex> является ядром тогда и только тогда, когда она '''симметрична''' (<tex>\kappa(\mathbf{x}, \mathbf{x}') = \kappa(\mathbf{x}', \mathbf{x})</tex>) и порождаемая ею '''[[Матрица Грама|матрица Грама]]''' <tex>\mathbf{K}</tex> является неотрицательно определенной (положительно полуопределенной) для любого конечного набора точек <tex>\{\mathbf{x}_1, \dots, \mathbf{n}\}</tex>. Матрица <tex>\mathbf{K}</tex> имеет элементы <tex>K_{ij} = \kappa(\mathbf{x}_i, \mathbf{x}_j)</tex>, и условие неотрицательной определенности означает, что для любого вектора <tex>\mathbf{c} \in \mathbb{R}^n</tex> выполняется <tex>\mathbf{c}^T \mathbf{K} \mathbf{c} \ge 0</tex>. Это условие гарантирует, что функция ядра неявно соответствует скалярному произведению в некотором, возможно, бесконечномерном, пространстве.
-Такой прием называется '''ядерной уловкой''' (kernel trick).
+== Основные свойства ядер и конструирование ==
+Множество допустимых ядер замкнуто относительно ряда операций, что позволяет конструировать сложные ядра из простых "вручную", учитывая специфику данных. Если <tex>\kappa_1, \kappa_2</tex> — ядра на <tex>\mathcal{X}</tex>, <tex>a > 0</tex>, <tex>f: \mathcal{X} \to \mathbb{R}</tex>, <tex>\mathbf{A}</tex> — положительно определенная матрица, то следующие функции также являются ядрами:
+* <tex>\kappa(\mathbf{x}, \mathbf{x}') = \kappa_1(\mathbf{x}, \mathbf{x}') + \kappa_2(\mathbf{x}, \mathbf{x}')</tex> (сумма ядер)
+* <tex>\kappa(\mathbf{x}, \mathbf{x}') = a \cdot \kappa_1(\mathbf{x}, \mathbf{x}')</tex> (умножение на положительную константу)
+* <tex>\kappa(\mathbf{x}, \mathbf{x}') = \kappa_1(\mathbf{x}, \mathbf{x}') \cdot \kappa_2(\mathbf{x}, \mathbf{x}')</tex> (произведение ядер)
+* <tex>\kappa(\mathbf{x}, \mathbf{x}') = f(\mathbf{x}) \kappa_1(\mathbf{x}, \mathbf{x}') f(\mathbf{x}')</tex> (нормализация)
+* <tex>\kappa(\mathbf{x}, \mathbf{x}') = \mathbf{x}^T \mathbf{A} \mathbf{x}'</tex> (ядро с учетом линейного преобразования признаков)
-=== Формальные свойства ===
+== Примеры стандартных ядер ==
+Рассмотрим наиболее распространенные семейства ядер, используемые на практике для данных в виде векторов <tex>\mathbf{x}, \mathbf{x}' \in \mathbb{R}^d</tex>.
-С математической точки зрения, функция <tex>K: \mathcal{X} \times \mathcal{X} \rightarrow \mathbb{R}</tex> является допустимой для использования в методах, основанных на [[Воспроизводящее ядро гильбертова пространства|гильбертовых пространствах с воспроизводящим ядром]] (RKHS), тогда и только тогда, когда она является симметричной и положительно полуопределенной.
+=== Линейное ядро ===
+<tex>\kappa(\mathbf{x}, \mathbf{x}') = \langle \mathbf{x}, \mathbf{x}' \rangle = \mathbf{x}^T \mathbf{x}'</tex>
+Простейшее ядро, соответствующее тождественному отображению <tex>\varphi(\mathbf{x}) = \mathbf{x}</tex>. Приводит к обычному линейному алгоритму. Полезно как базовый случай и для задач с высокой размерностью, где линейная разделимость уже достигнута.
-==== Теорема Мерсера ====
+=== Полиномиальное ядро ===
-Для того чтобы функция <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> и пространства со скалярным произведением, для которых ядро является скалярным произведением.
+<tex>\kappa(\mathbf{x}, \mathbf{x}') = (\gamma \langle \mathbf{x}, \mathbf{x}' \rangle + c)^d</tex>
+где <tex>d \in \mathbb{N}</tex> — степень полинома, <tex>\gamma > 0</tex> — коэффициент масштабирования, <tex>c \ge 0</tex> — свободный член. Это ядро соответствует пространству всех мономиальных признаков степени вплоть до <tex>d</tex>. Оно позволяет улавливать полиномиальные взаимодействия между исходными признаками.
-=== Основные виды ядер ===
+=== Радиально-базисное ядро (Гауссово, RBF) ===
+<tex>\kappa(\mathbf{x}, \mathbf{x}') = \exp\left( -\gamma \|\mathbf{x} - \mathbf{x}'\|^2 \right)</tex>
+где <tex>\gamma > 0</tex> — параметр ширины ядра. Это одно из самых популярных ядер. Оно соответствует бесконечномерному признаковому пространству и может моделировать чрезвычайно сложные, локальные зависимости. Параметр <tex>\gamma</tex> контролирует "радиус влияния" одного примера: большое значение приводит к переобучению (гибкая, изрезанная граница), маленькое — к недообучению (почти линейная граница).
-Выбор ядра определяет геометрию пространства признаков и гипотезы о данных. Наиболее распространены следующие семейства.
+=== Сигмоидное ядро ===
+<tex>\kappa(\mathbf{x}, \mathbf{x}') = \tanh(\gamma \langle \mathbf{x}, \mathbf{x}' \rangle + c)</tex>
+Данное ядро происходит из области [[Нейронная сеть|нейронных сетей]]. Однако оно является допустимым (положительно определенным) только для некоторых значений параметров <tex>\gamma, c</tex>, что ограничивает его прямое использование в строгой ядерной теории, хотя на практике оно иногда применяется.
-==== Линейное ядро ====
+=== Ядра для специфических структур данных ===
-Самое простое ядро, соответствующее отсутствию преобразования.
+Ядерный подход не ограничивается векторами из <tex>\mathbb{R}^d</tex>. Существуют ядра, определенные на строках (на основе [[Расстояние Левенштейна|расстояния редактирования]]), графах (ядро случайных блужданий, ''random walk kernel''), множествах, деревьях и других сложных объектах. Это позволяет применять весь арсенал ядерных методов к задачам [[Биоинформатика|биоинформатики]], [[Компьютерная лингвистика|обработки текстов]] и хемоинформатики.
-<tex>K(\mathbf{x}, \mathbf{x}') = \langle \mathbf{x}, \mathbf{x}' \rangle</tex>
-Используется, когда данные и так почти линейно разделимы, или при очень высокой размерности исходного пространства (например, в задачах классификации текстов).
-==== Полиномиальное ядро ====
+== Ядерный трюк в действии: пример ядерной гребневой регрессии ==
-Представляет скалярные произведения в пространстве всех мономов степени до <tex>d</tex>.
+Рассмотрим задачу [[Линейная регрессия|линейной регрессии]] с квадратичной функцией потерь и L2-регуляризацией ([[Гребневая регрессия|гребневая регрессия]]). Решение в терминах исходных признаков дается формулой <tex>\mathbf{w} = (\mathbf{X}^T\mathbf{X} + \lambda \mathbf{I})^{-1}\mathbf{X}^T\mathbf{y}</tex>. Используя матричное тождество, его можно переписать в "дуальную форму", зависящую только от скалярных произведений <tex>\mathbf{X}\mathbf{X}^T</tex>:
-<tex>K(\mathbf{x}, \mathbf{x}') = (\gamma \langle \mathbf{x}, \mathbf{x}' \rangle + c_0)^d</tex>
+<tex>\mathbf{y}_{\text{pred}}(\mathbf{x}_{\text{new}}) = \mathbf{y}^T (\mathbf{K} + \lambda \mathbf{I})^{-1} \mathbf{k}</tex>,
-* '''Параметры:''' <tex>d</tex> — степень полинома, <tex>c_0</tex> — свободный член (trade-off между влиянием старших и младших степеней), <tex>\gamma</tex> — коэффициент масштабирования.
+где <tex>\mathbf{K}</tex> — матрица Грама на обучающей выборке, а вектор <tex>\mathbf{k}</tex> состоит из ядерных оценок <tex>\kappa(\mathbf{x}_i, \mathbf{x}_{\text{new}})</tex>. Замена всех скалярных произведений на функцию ядра дает нелинейную '''ядерную гребневую регрессию''', способную аппроксимировать сложные нелинейные функции.
-* Хорошо подходит для данных, где зависимости имеют полиномиальный характер, но склонно к переобучению при больших <tex>d</tex>.
-==== Гауссово ядро (Radial Basis Function, RBF) ====
+== Практические аспекты и выбор ядра ==
-Наиболее популярное универсальное ядро, соответствующее бесконечномерному пространству признаков.
+Выбор ядра и его параметров — центральная задача при использовании ядерных методов.
-<tex>K(\mathbf{x}, \mathbf{x}') = \exp\left( -\gamma \|\mathbf{x} - \mathbf{x}'\|^2 \right)</tex>
+* '''Выбор типа ядра''': Обычно начинают с линейного ядра как с интерпретируемого baseline. Если оно не дает нужного качества, переходят к RBF-ядру, которое является универсальным аппроксиматором и хорошим выбором "по умолчанию" для нелинейных задач средней размерности. Специфические ядра (например, для графов) выбирают, исходя из природы данных.
-* '''Параметр:''' <tex>\gamma > 0</tex> (часто задается как <tex>\gamma = \frac{1}{2\sigma^2}</tex>). Определяет «радиус влияния» одного примера на другой. При малом <tex>\gamma</tex> граница решения получается гладкой (недообучение), при большом — сложной, подстраивающейся под каждый выброс (переобучение).
+* '''Настройка гиперпараметров''': Критически важна. Осуществляется через [[Перекрестная проверка|кросс-валидацию]]. Для RBF-ядра настраивают <tex>\gamma</tex> (и параметр регуляризации <tex>C</tex> в SVM). Распространенная эвристика для <tex>\gamma</tex> в RBF — установка обратно пропорционально медиане попарных евклидовых расстояний между объектами.
-* Является универсальным аппроксиматором.
+* '''Нормализация данных''': Перед применением ядер, чувствительных к масштабу признаков (особенно RBF и полиномиального), необходимо проводить стандартизацию признаков (вычитание среднего, деление на стандартное отклонение).
+* '''Вычислительная сложность''': Основной недостаток ядерных методов — необходимость вычисления и хранения матрицы Грама <tex>\mathbf{K}</tex> размера <tex>n \times n</tex>, где <tex>n</tex> — число объектов в обучающей выборке. Это требует <tex>O(n^2)</tex> памяти и, как правило, <tex>O(n^3)</tex> времени для обращения матрицы, что делает методы непрактичными для больших наборов данных (<tex>n > 10^5</tex>). Для преодоления этого ограничения разработаны различные методы аппроксимации (например, метод случайных признаков, аппроксимация Найстрома).
-==== Сигмоидное ядро ====
+== Заключение ==
-<tex>K(\mathbf{x}, \mathbf{x}') = \tanh(\gamma \langle \mathbf{x}, \mathbf{x}' \rangle + c_0)</tex>
+Ядра — это мощная и математически строгая концепция, позволяющая неявно строить нелинейные модели без необходимости работы с координатами в многомерных пространствах. Понимание принципов ядерного трюка не только дает в руки инженера эффективный инструмент (SVM, ядерная регрессия), но и формирует полезный взгляд на модели машинного обучения через призму функций сходства, что находит отклик и в более современных подходах.
-Происходит из теории нейронных сетей. Является допустимым (положительно определенным) только при определенных значениях параметров, что ограничивает его применение на практике по сравнению с RBF.
-==== Ядра для специфических структур данных ====
+== См. также ==
-Мощь ядерного подхода проявляется в возможности задавать сходство для невекторных объектов.
+* [[Метод опорных векторов]]
-* '''Строковые ядра (String kernels):''' Измеряют сходство текстов через количество общих подстрок (спектральное ядро) или расстояние Левенштейна.
+* [[Воспроизводящее ядро гильбертова пространства]]
-* '''Ядра на графах (Graph kernels):''' Вычисляют сходство графов через случайные блуждания (Random Walk kernel) или сравнение подграфов (Weisfeiler-Lehman kernel).
+* [[Проклятие размерности]]
-* '''Ядра на вероятностных распределениях:''' Например, ядро Фишера (Fisher kernel), использующее градиенты логарифмического правдоподобия порождающей модели.
+* [[Теорема Мерсера]]
+* [[Гауссовский процесс]]
-=== Конструирование ядер ===
+== Литература ==
+# Шлезингер М., Главач В. Десять лекций по статистическому и структурному распознаванию. — Киев: Наукова думка, 2004. — Глава о ядерных методах.
-Новые ядра могут быть построены из существующих с помощью набора алгебраических операций, замкнутых относительно свойства положительной определенности:
+# Schölkopf B., Smola A. J. Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond. — MIT Press, 2002. — Фундаментальный труд по теории ядер.
-# '''Сумма:''' <tex>K(\mathbf{x}, \mathbf{y}) = K_1(\mathbf{x}, \mathbf{y}) + K_2(\mathbf{x}, \mathbf{y})</tex>
+# Bishop C. M. Pattern Recognition and Machine Learning. — Springer, 2006. — Глава 6: Kernel Methods.
-# '''Произведение:''' <tex>K(\mathbf{x}, \mathbf{y}) = K_1(\mathbf{x}, \mathbf{y}) \cdot K_2(\mathbf{x}, \mathbf{y})</tex>
+# Shawe-Taylor J., Cristianini N. Kernel Methods for Pattern Analysis. — Cambridge University Press, 2004. — Всеобъемлющее введение в ядерные методы анализа закономерностей.
-# '''Прямое произведение признаков:''' <tex>K(\mathbf{x}, \mathbf{y}) = f(\mathbf{x}) f(\mathbf{y})</tex> для любой вещественной функции <tex>f</tex>.
+# Murphy K. P. Machine Learning: A Probabilistic Perspective. — MIT Press, 2012. — Глава 14: Kernels.
-# '''Предельный переход:''' Предел сходящейся последовательности ядер также является ядром.
-=== Применение в алгоритмах ===
-Хотя ядерный трюк наиболее известен по 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.