Ядро

Материал из 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) — это функция, которая измеряет сходство между двумя объектами. С точки зрения математики, ядро <tex>\kappa(x, x')</tex> для любой пары объектов <tex>x</tex> и <tex>x'</tex> неявно вычисляет их скалярное произведение в некотором «расширенном» пространстве признаков <tex>\mathcal{H}</tex>, но делает это, оставаясь в исходном пространстве.
+== Интуитивное введение ==
+Многие классические алгоритмы машинного обучения, такие как [[Логистическая регрессия]] или базовый [[Метод опорных векторов|SVM]], являются линейными. Они способны строить лишь линейные разделяющие поверхности или линейные зависимости, что часто недостаточно для реальных данных. Традиционный подход к решению этой проблемы заключается в ручном конструировании новых, нелинейных признаков (например, полиномиальных признаков <tex>x_1^2, x_1 x_2, x_2^2</tex>) и последующем применении линейного алгоритма. Однако такой подход быстро становится вычислительно нереализуемым из-за "проклятия размерности", особенно если требуется отображение в пространство очень высокой или бесконечной размерности. Ядерный трюк предлагает элегантный обходной путь, заменяя все операции с координатами в расширенном пространстве вычислением специальной функции от исходных векторов.
-Простая формальная запись выглядит так:
+== Формальное определение ==
-<tex>\kappa(x, x') = \langle \phi(x), \phi(x') \rangle_{\mathcal{H}}</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> выполняется:
-Здесь <tex>\phi</tex> — это некоторое гипотетическое преобразование (например, возведение координат в квадрат или расчет расстояния до центров кластеров). '''Ключевая идея состоит в том, что само преобразование <tex>\phi</tex> мы никогда не вычисляем и можем даже не знать его явного вида'''. Вся магия работает благодаря функции <tex>\kappa</tex>, которую мы вычисляем напрямую.
+<tex>\kappa(\mathbf{x}, \mathbf{x}') = \langle \varphi(\mathbf{x}), \varphi(\mathbf{x}') \rangle_{\mathcal{H}}</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>.
-'''Ядерный трюк''' (kernel trick) — это вычислительный прием, позволяющий незаметно перевести данные в сложное нелинейное пространство, где они становятся линейно разделимыми, без ресурсоемкой операции настоящего преобразования координат.
+== Теорема Мерсера и положительная определенность ==
+Критерием того, что функция <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>. Это условие гарантирует, что функция ядра неявно соответствует скалярному произведению в некотором, возможно, бесконечномерном, пространстве.
-'''Аналогия.''' Представьте, что вы оцениваете дружбу между людьми не по списку их характеристик в резюме, а по тому, насколько совпадают их любимые книги, фильмы и привычки. Ядро — это и есть инструмент такой оценки сходства, только математически строгий.
+== Основные свойства ядер и конструирование ==
+Множество допустимых ядер замкнуто относительно ряда операций, что позволяет конструировать сложные ядра из простых "вручную", учитывая специфику данных. Если <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> (ядро с учетом линейного преобразования признаков)
-'''Техническая суть.''' Многие алгоритмы машинного обучения (например, [[Метод опорных векторов|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>\mathbf{x}, \mathbf{x}' \in \mathbb{R}^d</tex>.
-'''Пример «на пальцах».''' Допустим, точки двух классов на плоскости расположены в виде «мишени»: круг внутри, кольцо снаружи. Никакой прямой линией мы их не разделим. Но если мы добавим новый признак <tex>z = x^2 + y^2</tex> (квадрат расстояния от центра), точки выстроятся вдоль оси <tex>z</tex>, и их станет легко разделить горизонтальной линией. Ядро RBF делает именно это, но автоматически и без явного расчета тысяч новых координат. Функция <tex>\kappa(x, x') = \exp(-\gamma \|x - x'\|^2)</tex> просто считает что-то вроде «экспоненты от минус расстояния», но математически доказано, что это соответствует скалярному произведению в пространстве бесконечного числа признаков.
+=== Линейное ядро ===
+<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>\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(x, x') = \langle x, x' \rangle</tex>
+<tex>\kappa(\mathbf{x}, \mathbf{x}') = \tanh(\gamma \langle \mathbf{x}, \mathbf{x}' \rangle + c)</tex>
-Самый простой случай. Никакого трюка не происходит, мы работаем в исходном пространстве.
+Данное ядро происходит из области [[Нейронная сеть|нейронных сетей]]. Однако оно является допустимым (положительно определенным) только для некоторых значений параметров <tex>\gamma, c</tex>, что ограничивает его прямое использование в строгой ядерной теории, хотя на практике оно иногда применяется.
-'''Когда использовать:'''
-* Признаков очень много (например, десятки тысяч слов в [[TF-IDF]] для анализа текстов).
-* Данные и так почти линейно разделимы.
-* Нужна очень быстрая и хорошо интерпретируемая модель (можно посмотреть веса признаков).
-==== Полиномиальное ядро ====
+=== Ядра для специфических структур данных ===
-<tex>\kappa(x, x') = (\gamma \langle x, x' \rangle + r)^d</tex>
+Ядерный подход не ограничивается векторами из <tex>\mathbb{R}^d</tex>. Существуют ядра, определенные на строках (на основе [[Расстояние Левенштейна|расстояния редактирования]]), графах (ядро случайных блужданий, ''random walk kernel''), множествах, деревьях и других сложных объектах. Это позволяет применять весь арсенал ядерных методов к задачам [[Биоинформатика|биоинформатики]], [[Компьютерная лингвистика|обработки текстов]] и хемоинформатики.
-Моделирует взаимодействия признаков вплоть до степени <tex>d</tex>. Если <tex>d=2</tex>, ядро неявно учитывает не только исходные признаки, но и все их попарные произведения.
-'''Когда использовать:'''
-* Есть понимание, что важны конкретные нелинейные комбинации (например, «цена * площадь» в задаче оценки недвижимости).
-* Данные нормированы, и нам не нужна супер-гибкая граница. Будьте осторожны: при больших <tex>d</tex> значения ядра могут становиться очень большими или очень маленькими.
-==== RBF (гауссовское ядро, Radial Basis Function) ====
+== Ядерный трюк в действии: пример ядерной гребневой регрессии ==
-<tex>\kappa(x, x') = \exp\left(-\gamma \|x - x'\|^2\right)</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>\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>. Замена всех скалярных произведений на функцию ядра дает нелинейную '''ядерную гребневую регрессию''', способную аппроксимировать сложные нелинейные функции.
-* Вы не знаете, какая структура у данных, но предполагаете, что она сложная.
-* У вас не слишком много данных (до десятков тысяч объектов), и нормально работает кросс-валидация.
-* Это ядро по умолчанию для [[Метод опорных векторов|SVM]].
-===== Важнейшие параметры C и gamma =====
+== Практические аспекты и выбор ядра ==
-Для практического применения RBF критически важны два гиперпараметра (обычно в [[SVM]]):
+Выбор ядра и его параметров — центральная задача при использовании ядерных методов.
-* '''C''' (штраф за ошибку): Баланс между шириной разделяющей полосы и количеством ошибок на обучении. Большое '''C''' заставляет модель правильно классифицировать все точки, что ведет к сложным, изрезанным границам и риску переобучения. Маленькое '''C''' позволяет больше ошибок, делает границу более гладкой и обобщающей.
+* '''Выбор типа ядра''': Обычно начинают с линейного ядра как с интерпретируемого baseline. Если оно не дает нужного качества, переходят к RBF-ядру, которое является универсальным аппроксиматором и хорошим выбором "по умолчанию" для нелинейных задач средней размерности. Специфические ядра (например, для графов) выбирают, исходя из природы данных.
-* '''gamma''' (<tex>\gamma</tex>): Определяет «радиус влияния» одной точки. Большое '''gamma''' означает, что точка влияет только на очень близких соседей — граница становится рваной, модель переобучается. Маленькое '''gamma''' размывает влияние, делает границу слишком простой (вплоть до почти линейной).
+* '''Настройка гиперпараметров''': Критически важна. Осуществляется через [[Перекрестная проверка|кросс-валидацию]]. Для 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>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) ====
-Самый известный потребитель ядер. Изначально [[SVM]] ищет линейную разделяющую полосу максимальной ширины. Применение ядерного трюка превращает его в мощный нелинейный классификатор. На этапе предсказания модель опирается только на ''опорные векторы'' — объекты обучающей выборки, ближайшие к границе. Формула предсказания:
-<tex>f(x) = \text{sign}\left(\sum_{i} \alpha_i y_i \kappa(x_i, x) + b\right)</tex>
-Здесь <tex>\alpha_i</tex> — ненулевые коэффициенты только для опорных векторов, что делает предсказание эффективным.
-==== Ядерный PCA ====
-Классический [[Метод главных компонент|PCA]] ищет направления максимальной дисперсии в исходных данных. [[Ядерный анализ главных компонент|Ядерный PCA]] делает то же самое, но в пространстве <tex>\mathcal{H}}</tex>. Это позволяет ему, например, выделить «главную компоненту» для данных в форме кольца или спирали — задача, с которой обычный PCA не справится. Технически это требует вычисления матрицы Грама (об этом ниже) и ее разложения.
-==== Ядерная гребневая регрессия (Kernel Ridge Regression) ====
-Это альтернатива линейной регрессии, которую можно «изогнуть». Вместо прямой линии модель строит гладкую функцию, проходящую через точки. Решение в ядерной форме имеет элегантный вид:
-<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> — коэффициент регуляризации.
-=== Практические аспекты и проблема масштабируемости ===
-Главная ахиллесова пята ядерных методов — цена работы с матрицей Грама.
-* '''Память:''' Хранение матрицы требует <tex>O(N^2)</tex> ячеек. Для 100 000 объектов матрица из 10 миллиардов чисел уже не поместится в оперативную память стандартного компьютера.
-* '''Время:''' Обращение матрицы (как в Kernel Ridge Regression или [[Гауссовский процесс|Гауссовских процессах]]) стоит <tex>O(N^3)</tex> операций. Утроение данных увеличивает время счета в 27 раз.
-Это делает классическую ядерную машину идеальным инструментом для ''малых и средних данных'' (примерно до 20–50 тысяч объектов), но создает сложности на больших данных.
-==== Методы ускорения ====
-Инженеры придумали способы «обмануть» кубическую сложность:
-* '''Разложение Нюстрёма (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. Это дало строгий математический мост между двумя мирами и помогает теоретически объяснять успех глубокого обучения.
 == См. также ==
 * [[Метод опорных векторов]]
+* [[Воспроизводящее ядро гильбертова пространства]]
+* [[Проклятие размерности]]
+* [[Теорема Мерсера]]
 * [[Гауссовский процесс]]
-* [[Ядерный анализ главных компонент]]
-* [[Гребневая регрессия]]
-* [[Проблема проклятия размерности]]
 == Литература ==
+# Шлезингер М., Главач В. Десять лекций по статистическому и структурному распознаванию. — Киев: Наукова думка, 2004. — Глава о ядерных методах.
-# 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. Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond. — MIT Press, 2002. — Фундаментальный труд по теории ядер.
-# Bishop, C. M. (2006). ''Pattern Recognition and Machine Learning''. Springer. (Глава 6: Kernel Methods, отличное введение).
+# Bishop C. M. Pattern Recognition and Machine Learning. — Springer, 2006. — Глава 6: Kernel Methods.
-# Murphy, K. P. (2012). ''Machine Learning: A Probabilistic Perspective''. MIT Press. (Глава 14: Kernels, с упором на практику и связь с байесовскими методами).
+# Shawe-Taylor J., Cristianini N. Kernel Methods for Pattern Analysis. — Cambridge University Press, 2004. — Всеобъемлющее введение в ядерные методы анализа закономерностей.
-# Rahimi, A., & Recht, B. (2007). Random Features for Large-Scale Kernel Machines. ''Advances in Neural Information Processing Systems (NIPS)''. (Революционная статья об аппроксимации ядер).
+# Murphy K. P. Machine Learning: A Probabilistic Perspective. — MIT Press, 2012. — Глава 14: Kernels.
-# Jacot, A., Gabriel, F., & Hongler, C. (2018). Neural Tangent Kernel: Convergence and Generalization in Neural Networks. ''Advances in Neural Information Processing Systems (NeurIPS)''. (Теория, связывающая ядра и нейросети).