Ядро

Материал из 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) в контексте [[Машинное обучение|машинного обучения]] — это функция, позволяющая выполнять вычисления в неявном высокоразмерном пространстве признаков без явного отображения исходных данных в это пространство. Это фундаментальная концепция, лежащая в основе [[Метод опорных векторов|метода опорных векторов]] (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).
+== Интуитивное введение ==
+Многие классические алгоритмы машинного обучения, такие как [[Логистическая регрессия]] или базовый [[Метод опорных векторов|SVM]], являются линейными. Они способны строить лишь линейные разделяющие поверхности или линейные зависимости, что часто недостаточно для реальных данных. Традиционный подход к решению этой проблемы заключается в ручном конструировании новых, нелинейных признаков (например, полиномиальных признаков <tex>x_1^2, x_1 x_2, x_2^2</tex>) и последующем применении линейного алгоритма. Однако такой подход быстро становится вычислительно нереализуемым из-за "проклятия размерности", особенно если требуется отображение в пространство очень высокой или бесконечной размерности. Ядерный трюк предлагает элегантный обходной путь, заменяя все операции с координатами в расширенном пространстве вычислением специальной функции от исходных векторов.
-== Определение ==
+== Формальное определение ==
-Пусть <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>:
+Функция двух переменных <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> выполняется:
-<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) ==
+<tex>\kappa(\mathbf{x}, \mathbf{x}') = \langle \varphi(\mathbf{x}), \varphi(\mathbf{x}') \rangle_{\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>\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>.
-Не любая функция двух переменных является ядром. Для того чтобы функция <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>, должна быть симметричной и неотрицательно определенной.
-Из этого свойства вытекают правила построения новых ядер из существующих (исчисление ядер):
+== Теорема Мерсера и положительная определенность ==
-*   Сумма ядер: <math>K = K_1 + K_2</math> — ядро.
+Критерием того, что функция <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>. Это условие гарантирует, что функция ядра неявно соответствует скалярному произведению в некотором, возможно, бесконечномерном, пространстве.
-*   Произведение ядер: <math>K = K_1 \cdot K_2</math> — ядро.
-*   Умножение на константу: <math>K = c \cdot K_1, c > 0</math> — ядро.
-== Основные семейства ядер ==
+== Основные свойства ядер и конструирование ==
+Множество допустимых ядер замкнуто относительно ряда операций, что позволяет конструировать сложные ядра из простых "вручную", учитывая специфику данных. Если <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> (ядро с учетом линейного преобразования признаков)
-=== Стационарные ядра ===
+== Примеры стандартных ядер ==
-Ядра этой группы зависят только от разности аргументов: <math>K(\mathbf{x}, \mathbf{x}') = K(\mathbf{x} - \mathbf{x}')</math>. Часто рассматриваются как функции от расстояния (ядра радиального базиса).
+Рассмотрим наиболее распространенные семейства ядер, используемые на практике для данных в виде векторов <tex>\mathbf{x}, \mathbf{x}' \in \mathbb{R}^d</tex>.
-*   '''Гауссовское ядро (RBF):''' <math>K(\mathbf{x}, \mathbf{x}') = \exp\left(-\frac{\|\mathbf{x} - \mathbf{x}'\|^2}{2\sigma^2}\right)</math>. Самое популярное ядро, соответствующее бесконечномерному пространству признаков. Параметр <math>\sigma</math> (ширина окна) управляет гладкостью границы решений.
+=== Линейное ядро ===
-*   '''Ядро Лапласа:''' <math>K(\mathbf{x}, \mathbf{x}') = \exp\left(-\frac{\|\mathbf{x} - \mathbf{x}'\|}{\sigma}\right)</math>. Менее чувствительно к выбросам по сравнению с гауссовским.
+<tex>\kappa(\mathbf{x}, \mathbf{x}') = \langle \mathbf{x}, \mathbf{x}' \rangle = \mathbf{x}^T \mathbf{x}'</tex>
-*   '''Рациональное квадратичное ядро:''' <math>K(\mathbf{x}, \mathbf{x}') = 1 - \frac{\|\mathbf{x} - \mathbf{x}'\|^2}{\|\mathbf{x} - \mathbf{x}'\|^2 + c}</math>. Представляет собой смесь RBF-ядер с разными масштабами.
+Простейшее ядро, соответствующее тождественному отображению <tex>\varphi(\mathbf{x}) = \mathbf{x}</tex>. Приводит к обычному линейному алгоритму. Полезно как базовый случай и для задач с высокой размерностью, где линейная разделимость уже достигнута.
-=== Нестационарные ядра ===
+=== Полиномиальное ядро ===
-*   '''Полиномиальное ядро:''' <math>K(\mathbf{x}, \mathbf{x}') = (\langle \mathbf{x}, \mathbf{x}' \rangle + c)^d</math>. Позволяет строить полиномиальные разделяющие поверхности степени <math>d</math>. Параметр <math>c \ge 0</math> регулирует вес старших и младших степеней.
+<tex>\kappa(\mathbf{x}, \mathbf{x}') = (\gamma \langle \mathbf{x}, \mathbf{x}' \rangle + c)^d</tex>
-*   '''Сигмоидное ядро:''' <math>K(\mathbf{x}, \mathbf{x}') = \tanh(\kappa \langle \mathbf{x}, \mathbf{x}' \rangle + \theta)</math>. Исторически связано с нейронными сетями, однако матрица Грама для него положительно определена лишь при определенных значениях параметров.
+где <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>
-*   '''Строковые ядра (String Kernels):''' Измеряют сходство строк через количество общих подстрок (спектральное ядро, ядро с пропусками). Используются в [[Биоинформатика|биоинформатике]] и [[Обработка естественного языка|NLP]].
+где <tex>\gamma > 0</tex> — параметр ширины ядра. Это одно из самых популярных ядер. Оно соответствует бесконечномерному признаковому пространству и может моделировать чрезвычайно сложные, локальные зависимости. Параметр <tex>\gamma</tex> контролирует "радиус влияния" одного примера: большое значение приводит к переобучению (гибкая, изрезанная граница), маленькое — к недообучению (почти линейная граница).
-*   '''Ядра на графах:''' Например, Random Walk Kernel подсчитывает количество общих маршрутов в двух графах. Применяются в [[Хемоинформатика|хемоинформатике]] для предсказания свойств молекул.
-*   '''Ядра Фишера:''' Строятся на основе вероятностных порождающих моделей, позволяя применять SVM к данным, хорошо описываемым скрытыми марковскими моделями.
-== Применение в классических алгоритмах ==
+=== Сигмоидное ядро ===
-Хотя термин «kernel trick» ассоциируется в первую очередь с [[Метод опорных векторов|SVM]], он применим к любому алгоритму, который можно выразить через скалярные произведения. Это утверждение носит название '''теоремы о представимости''' (Representer Theorem).
+<tex>\kappa(\mathbf{x}, \mathbf{x}') = \tanh(\gamma \langle \mathbf{x}, \mathbf{x}' \rangle + c)</tex>
-*   '''SVM с мягким зазором (C-SVM):''' Классический пример, где замена скалярного произведения на ядро <math>K</math> превращает линейный классификатор в нелинейный.
+Данное ядро происходит из области [[Нейронная сеть|нейронных сетей]]. Однако оно является допустимым (положительно определенным) только для некоторых значений параметров <tex>\gamma, c</tex>, что ограничивает его прямое использование в строгой ядерной теории, хотя на практике оно иногда применяется.
-*   '''Гребневая регрессия (Kernel Ridge Regression):''' Нелинейный вариант [[Гребневая регрессия|регуляризованной линейной регрессии]], полезный для восстановления регрессионных зависимостей малой размерности выборки.
-*   '''Метод главных компонент (Kernel PCA):''' Выполняет анализ главных компонент в пространстве <math>\mathcal{H}</math>, что позволяет выявлять нелинейные структуры в данных ([[Многообразие|многообразия]]).
-*   '''Kernel K-Means:''' Кластеризация данных, разделимых нелинейными границами, путем переноса центроидов в пространство признаков.
-== Связь с гауссовскими процессами ==
+=== Ядра для специфических структур данных ===
-В [[Гауссовские процессы|гауссовских процессах]] (GP) ядро играет роль ковариационной функции и определяет априорные предположения о свойствах моделируемой функции (гладкость, периодичность, стационарность). В этом контексте выбор ядра — это способ кодирования знаний о предметной области в модель. Часто используемые в GP ядра (Матерна, экспоненциальное, периодическое) имеют прямые аналоги в ядерных методах, таких как SVM, но интерпретируются с вероятностной точки зрения.
+Ядерный подход не ограничивается векторами из <tex>\mathbb{R}^d</tex>. Существуют ядра, определенные на строках (на основе [[Расстояние Левенштейна|расстояния редактирования]]), графах (ядро случайных блужданий, ''random walk kernel''), множествах, деревьях и других сложных объектах. Это позволяет применять весь арсенал ядерных методов к задачам [[Биоинформатика|биоинформатики]], [[Компьютерная лингвистика|обработки текстов]] и хемоинформатики.
+== Ядерный трюк в действии: пример ядерной гребневой регрессии ==
+Рассмотрим задачу [[Линейная регрессия|линейной регрессии]] с квадратичной функцией потерь и 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>\mathbf{y}_{\text{pred}}(\mathbf{x}_{\text{new}}) = \mathbf{y}^T (\mathbf{K} + \lambda \mathbf{I})^{-1} \mathbf{k}</tex>,
+где <tex>\mathbf{K}</tex> — матрица Грама на обучающей выборке, а вектор <tex>\mathbf{k}</tex> состоит из ядерных оценок <tex>\kappa(\mathbf{x}_i, \mathbf{x}_{\text{new}})</tex>. Замена всех скалярных произведений на функцию ядра дает нелинейную '''ядерную гребневую регрессию''', способную аппроксимировать сложные нелинейные функции.
 == Практические аспекты и выбор ядра ==
-Выбор ядра и его гиперпараметров критически важен:
+Выбор ядра и его параметров — центральная задача при использовании ядерных методов.
-*   '''Переобучение:''' Слишком маленькая <math>\sigma</math> в RBF-ядре ведет к обобщению по принципу «один ближайший сосед» (переобучение), а слишком большая — к вырождению в линейную границу.
+* '''Выбор типа ядра''': Обычно начинают с линейного ядра как с интерпретируемого baseline. Если оно не дает нужного качества, переходят к RBF-ядру, которое является универсальным аппроксиматором и хорошим выбором "по умолчанию" для нелинейных задач средней размерности. Специфические ядра (например, для графов) выбирают, исходя из природы данных.
-*   '''Масштабируемость:''' Вычисление матрицы Грама размера <math>n \times n</math> требует <math>O(n^2)</math> памяти и <math>O(n^3)</math> времени для обращения (или <math>O(n^2)</math> для SVM). Это делает наивные ядерные методы неприменимыми к «большим данным». Проблема решается с помощью аппроксимаций:
+* '''Настройка гиперпараметров''': Критически важна. Осуществляется через [[Перекрестная проверка|кросс-валидацию]]. Для RBF-ядра настраивают <tex>\gamma</tex> (и параметр регуляризации <tex>C</tex> в SVM). Распространенная эвристика для <tex>\gamma</tex> в RBF — установка обратно пропорционально медиане попарных евклидовых расстояний между объектами.
-**   '''Случайные признаки (Random Fourier Features):''' Аппроксимация стационарных ядер через прямое преобразование Фурье.
+* '''Нормализация данных''': Перед применением ядер, чувствительных к масштабу признаков (особенно RBF и полиномиального), необходимо проводить стандартизацию признаков (вычитание среднего, деление на стандартное отклонение).
-**   '''Метод Найстрома (Nyström Method):''' Низкоранговая аппроксимация матрицы Грама на основе подвыборки столбцов.
+* '''Вычислительная сложность''': Основной недостаток ядерных методов — необходимость вычисления и хранения матрицы Грама <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>). Для преодоления этого ограничения разработаны различные методы аппроксимации (например, метод случайных признаков, аппроксимация Найстрома).
+== Заключение ==
+Ядра — это мощная и математически строгая концепция, позволяющая неявно строить нелинейные модели без необходимости работы с координатами в многомерных пространствах. Понимание принципов ядерного трюка не только дает в руки инженера эффективный инструмент (SVM, ядерная регрессия), но и формирует полезный взгляд на модели машинного обучения через призму функций сходства, что находит отклик и в более современных подходах.
 == См. также ==
-*   [[Метод опорных векторов]] (SVM)
+* [[Метод опорных векторов]]
-*   [[Гауссовские процессы]]
+* [[Воспроизводящее ядро гильбертова пространства]]
-*   [[Проблема "проклятия размерности"]]
+* [[Проклятие размерности]]
-*   [[Воспроизводящее ядро гильбертова пространства]] (RKHS)
+* [[Теорема Мерсера]]
+* [[Гауссовский процесс]]
 == Литература ==
-# Schölkopf, B., & Smola, A. J. (2002). ''Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond''. MIT Press.
+# Шлезингер М., Главач В. Десять лекций по статистическому и структурному распознаванию. — Киев: Наукова думка, 2004. — Глава о ядерных методах.
-# Bishop, C. M. (2006). ''Pattern Recognition and Machine Learning''. Chapter 6: Kernel Methods. Springer.
+# Schölkopf B., Smola A. J. Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond. — MIT Press, 2002. — Фундаментальный труд по теории ядер.
-# Murphy, K. P. (2012). ''Machine Learning: A Probabilistic Perspective''. Chapter 14: Kernels. MIT Press.
+# Bishop C. M. Pattern Recognition and Machine Learning. — Springer, 2006. — Глава 6: Kernel Methods.
-# Rasmussen, C. E., & Williams, C. K. I. (2006). ''Gaussian Processes for Machine Learning''. Chapter 4: Covariance Functions. MIT Press.
+# Shawe-Taylor J., Cristianini N. Kernel Methods for Pattern Analysis. — Cambridge University Press, 2004. — Всеобъемлющее введение в ядерные методы анализа закономерностей.
-# 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.
+# Murphy K. P. Machine Learning: A Probabilistic Perspective. — MIT Press, 2012. — Глава 14: Kernels.