Ядро

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

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

Текущая версия

Содержание

1 Ядра в машинном обучении
2 Интуитивное введение
3 Формальное определение
- 3.1 Общий принцип кирнелизации алгоритма
4 Теорема Мерсера и положительная определенность
- 4.1 Интуитивное объяснение роли Теоремы Мерсера
5 Основные свойства ядер и конструирование
6 Примеры стандартных ядер
7 Ядерный трюк в действии: пример ядерной гребневой регрессии
8 Практические примеры применения ядер
- 8.1 Классификация текстов: SVM с ядром RBF для анализа тональности
- 8.2 Классификация изображений: ядерный SVM в эпоху до глубокого обучения
9 Практические аспекты и выбор ядра
10 Заключение
11 См. также
12 Литература

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

Ядро (англ. 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}$ .

Общий принцип кирнелизации алгоритма

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

Идентификация двойственной формы: Необходимо вывести формулировку алгоритма, где все обучающие примеры $\mathbf{x}_i$ входят только в операциях скалярного произведения $\langle \mathbf{x}_i, \mathbf{x}_j \rangle$ . Часто это возможно благодаря переходу от прямой (параметрической) формы к двойственной (основанной на данных). Классический пример — двойственная задача SVM, где матрица $\mathbf{X}\mathbf{X}^T$ в целевой функции содержит именно попарные скалярные произведения.
Подстановка ядра: Как только алгоритм представлен в терминах $\langle \mathbf{x}_i, \mathbf{x}_j \rangle$ , производится замена $\langle \mathbf{x}_i, \mathbf{x}_j \rangle \to \kappa(\mathbf{x}_i, \mathbf{x}_j)$ как в процессе обучения, так и при предсказании. Для нового объекта $\mathbf{x}_{\text{new}}$ предсказание также будет зависеть от ядерных вычислений $\kappa(\mathbf{x}_i, \mathbf{x}_{\text{new}})$ между ним и опорными (или всеми обучающими) векторами.

Таким образом, алгоритм неявно работает в пространстве $\mathcal{H}$ , но не требует ни вычисления отображения $\varphi$ , ни знания размерности этого пространства. Это позволяет, например, использовать RBF-ядро, соответствующее бесконечномерному $\varphi$ , без каких-либо дополнительных вычислительных затрат по сравнению с конечномерным случаем.

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

Критерием того, что функция $\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$ . Это условие гарантирует, что функция ядра неявно соответствует скалярному произведению в некотором, возможно, бесконечномерном, пространстве.

Интуитивное объяснение роли Теоремы Мерсера

На интуитивном уровне теорема Мерсера и условие положительной определенности решают фундаментальную проблему: гарантируют, что наша "подмена" скалярного произведения ядром математически корректна. Ключевая идея в следующем:

Существование пространства: Мы заменяем $\langle \mathbf{x}_i, \mathbf{x}_j \rangle$ на $\kappa(\mathbf{x}_i, \mathbf{x}_j)$ , подразумевая, что где-то "есть" признаки $\varphi(\mathbf{x})$ , для которых ядро дает скалярное произведение. Теорема Мерсера гарантирует, что для любой симметричной и положительно определенной функции такое пространство и такое отображение действительно существуют, даже если мы никогда не будем их строить. Без этой гарантии мы не могли бы полагаться на корректность операций, основанных на аксиомах скалярного произведения.
**Оптимизационная интерпретация**: Условие $\mathbf{c}^T \mathbf{K} \mathbf{c} \ge 0$ означает, что функция потерь, записанная в терминах ядра, остается выпуклой. Например, двойственная задача SVM остается задачей выпуклого квадратичного программирования, что гарантирует существование единственного глобального оптимума и эффективную сходимость алгоритмов оптимизации. Если бы матрица $\mathbf{K}$ не была положительно полуопределенной, задача оптимизации могла бы стать невыпуклой с множеством локальных минимумов.
**Геометрическая согласованность**: Условие положительной определенности гарантирует, что ядро порождает геометрию, согласованную с понятиями расстояния и угла в некотором евклидовом пространстве. Расстояние между образами, индуцированное ядром, $\|\varphi(\mathbf{x}) - \varphi(\mathbf{x}')\|^2 = \kappa(\mathbf{x}, \mathbf{x}) + \kappa(\mathbf{x}', \mathbf{x}') - 2\kappa(\mathbf{x}, \mathbf{x}')$ , будет удовлетворять всем аксиомам метрики, что необходимо для осмысленных геометрических выводов.

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

Множество допустимых ядер замкнуто относительно ряда операций, что позволяет конструировать сложные ядра из простых "вручную", учитывая специфику данных. Если $\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}})$ . Замена всех скалярных произведений на функцию ядра дает нелинейную ядерную гребневую регрессию, способную аппроксимировать сложные нелинейные функции.

Практические примеры применения ядер

Ядерные методы демонстрируют высокую эффективность в ситуациях, где данные не являются линейно разделимыми, а размерность признакового пространства высока. Ниже приведены два характерных примера из реальной практики.

Классификация текстов: SVM с ядром RBF для анализа тональности

В задаче анализа тональности отзывов требуется определить, является ли текст положительным или отрицательным.

Векторизация: Каждый документ преобразуется в вектор $\mathbf{x} \in \mathbb{R}^d$ с помощью TF-IDF-взвешивания, где $d$ — размер словаря (обычно десятки тысяч слов). В таком пространстве документы разных классов часто перекрываются и не разделяются линейно из-за синонимии, многозначности слов и сложных контекстных взаимосвязей.
Выбор ядра: Линейное ядро (по сути, линейный классификатор) является хорошим baseline, но для улавливания нелинейных взаимодействий между термами применяется RBF-ядро. Оно позволяет неявно моделировать ситуации вида "наличие слова A вблизи слова B меняет смысл на противоположный", что недоступно чисто линейной модели.
Результат: SVM с RBF-ядром на представлении TF-IDF долгое время была стандартом де-факто для задач классификации текстов до появления Word2Vec и трансформеров, показывая точность, превосходящую наивный байесовский классификатор и линейные модели.

Классификация изображений: ядерный SVM в эпоху до глубокого обучения

До повсеместного распространения свёрточных нейронных сетей одним из лучших подходов к классификации рукописных цифр (MNIST) и распознаванию объектов в небольших датасетах был следующий пайплайн:

Извлечение признаков: Из изображений извлекались высокоуровневые признаки, инвариантные к сдвигу и повороту, например, HOG (Histogram of Oriented Gradients) или признаки на основе банка фильтров Габора.
Классификация: Полученные векторы признаков классифицировались с помощью SVM с RBF-ядром или полиномиальным ядром степени 2 или 3. Ядро неявно моделировало сложные взаимодействия между выходами различных фильтров, соответствующие определенным формам и текстурам.
Преимущество: Такой подход был вычислительно эффективнее и требовал меньше данных для обучения, чем полносвязные нейронные сети того времени, и служил стандартным, очень сильным бейзлайном в компьютерном зрении.

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

Выбор ядра и его гиперпараметров — центральная задача при использовании ядерных методов. Решения здесь принимаются на основе анализа данных, размера выборки и требуемой сложности модели.

Стратегия выбора типа ядра

Рекомендуется следовать иерархическому подходу, начиная с простого и двигаясь к сложному, используя кросс-валидацию для объективного сравнения.

1. Линейное ядро (Baseline): Всегда следует начинать с него. Термин baseline (базовая модель) означает простую, хорошо интерпретируемую и быстро обучаемую модель, которая служит точкой отсчета. Если линейное ядро дает приемлемое качество, его, как правило, и выбирают. Линейная модель:
- Предпочтительна, когда размерность признакового пространства $d$ очень велика (например, $d \approx 10^5$ в задачах анализа текстов с TF-IDF). В таких данных высокая размерность часто уже обеспечивает хорошую линейную разделимость, а введение нелинейности чревато переобучением.
- Интерпретируема: веса признаков $\mathbf{w}$ могут быть проанализированы, что важно в биоинформатике или финансах.
- Вычислительно эффективна: обучение может быть выполнено за линейное время от $d$ , минуя построение полной ядерной матрицы $O(n^2)$ .

2. Радиально-базисное ядро (RBF): Это следующий шаг, если линейное ядро показало неудовлетворительный результат. RBF-ядро является выбором "по умолчанию" для нелинейных задач по ряду причин:
- Универсальность: Теоретически, при правильном подборе $\gamma$ и $C$ способно аппроксимировать любую непрерывную границу решений.
- Численная стабильность: Значения ядра лежат в диапазоне $(0, 1]$ , что обеспечивает хорошую обусловленность матрицы Грама, в отличие от полиномиального ядра высокой степени, значения которого могут расходиться.
- Малое число гиперпараметров: Всего два ( $C$ и $\gamma$ ), что упрощает настройку по сравнению с полиномиальным ядром.

3. Полиномиальное ядро: Используется реже RBF, но целесообразно в случаях, когда предметная область подразумевает полиномиальный характер взаимодействий (например, в некоторых задачах физики или при кодировании взаимодействий генов). Основная трудность — настройка сразу трех гиперпараметров: $d, \gamma, c$ .

Детальная настройка гиперпараметров

Гиперпараметры ядерных методов управляют компромиссом между переобучением и недообучением. Их подбор всегда осуществляется на отложенной валидационной выборке через решетчатый поиск (Grid Search) с кросс-валидацией.

Параметр регуляризации $C$ (для SVM): Общий для ядерных SVM. Это параметр, определяющий штраф за неправильную классификацию обучающих примеров. Контролирует баланс между шириной разделяющей полосы и количеством ошибок на обучении.
- Малое $C$ ( $10^{-3} \dots 10^{-1}$ ): Увеличивает ширину полосы, разрешая множественные нарушения границы. Приводит к более гладкой, простой границе решений. Используется при сильном переобучении или зашумленных данных. Эквивалентно сильной регуляризации.
- Большое $C$ ( $10^2 \dots 10^4$ ): Штрафует ошибки на обучающей выборке очень сильно, стремясь классифицировать все примеры верно. Полоса сужается, граница становится изрезанной и подстраивается под индивидуальные выбросы. Ведет к переобучению. Эквивалентно слабой регуляризации.
- Рекомендуемый диапазон поиска: Экспоненциальная сетка, например, $[10^{-3}, 10^{-2}, ..., 10^3, 10^4]$ .

Параметр ширины ядра $\gamma$ (для RBF, полиномиального и сигмоидного ядер): Определяет "радиус влияния" одного примера или масштаб скалярного произведения.
- Малое $\gamma$ ( $10^{-4} \dots 10^{-2}$ ): Модель "видит" примеры как далеко рассеянные; даже далекие точки считаются похожими ( $\kappa(\mathbf{x}, \mathbf{x}') \to 1$ ). Граница решений получается очень гладкой, почти линейной, что ведет к сильному недообучению.
- Большое $\gamma$ ( $10 \dots 10^3$ ): Влияние каждого примера становится чрезвычайно локальным; уже небольшие расстояния приводят к почти нулевому сходству ( $\kappa(\mathbf{x}, \mathbf{x}') \to 0$ ). Граница решений формирует маленькие "островки" вокруг опорных векторов, идеально разделяя обучающие данные, но теряя способность к обобщению — классическое переобучение.
- Эвристика для начального приближения: Установите $\gamma \approx 1 / d$ , где $d$ — количество признаков, или используйте $\gamma \approx 1 / \text{медиана}(\|\mathbf{x}_i - \mathbf{x}_j\|^2)$ , что масштабирует параметр, делая его инвариантным к дисперсии данных.
- Рекомендуемый диапазон поиска: Экспоненциальная сетка, например, $[10^{-5}, 10^{-4}, ..., 10^2, 10^3]$ . Решетчатый поиск по паре $(C, \gamma)$ критичен для достижения высокой точности.

Параметры полиномиального ядра $d, \gamma, c$ :
- Степень $d$ : Определяет максимальную сложность взаимодействия признаков. Обычно ограничивается значениями $d = 2$ или $3$ . Большие степени ( $d > 5$ ) почти гарантированно приводят к переобучению и численной нестабильности, поэтому на практике используются редко.
- Свободный член $c$ : Обычно фиксируется как $c=0$ (однородный полином) или $c=1$ (неоднородный, учитывающий взаимодействия всех степеней вплоть до $d$ ). Настройка $c$ как непрерывного гиперпараметра используется редко.
- Рекомендация: Если линейное и RBF ядра не дали результата, попробуйте комбинации $d \in \{2, 3\}$ , $c \in \{0, 1\}$ , а $\gamma$ ищите по сетке, аналогичной RBF.

Нормализация данных

Перед применением ядер, чувствительных к масштабу признаков (особенно RBF и полиномиального), строго необходима предварительная стандартизация признаков. Процедура заключается в вычитании среднего значения признака и делении на его стандартное отклонение. Без этого признаки с большим численным диапазоном будут доминировать в евклидовой метрике $\|\mathbf{x} - \mathbf{x}'\|^2$ , полностью подавляя вклад других, не менее информативных признаков. Для данных с неизвестной природой рекомендуется применять RobustScaler (использующий медиану и квартили), устойчивый к выбросам.

Вычислительная сложность

Основной недостаток точных ядерных методов — необходимость вычисления и хранения матрицы Грама $\mathbf{K}$ размера $n \times n$ , где $n$ — число объектов в обучающей выборке. Это требует $O(n^2)$ памяти и, как правило, $O(n^3)$ времени для обращения матрицы или решения задачи квадратичного программирования, что делает методы непрактичными для больших наборов данных ( $n > 10^5$ ). В таких случаях вместо точных методов прибегают к линейным аппроксимациям ядер, например:

Метод случайных признаков (Random Fourier Features): Строится конечномерная аппроксимация $\tilde{\varphi}(\mathbf{x})$ пространства RBF-ядра, после чего применяется быстрый линейный метод.
Аппроксимация Найстрома (Nyström method): Выбирается подмножество из $m \ll n$ примеров, и полная ядерная матрица аппроксимируется низкоранговой матрицей $\mathbf{K} \approx \tilde{\mathbf{K}}_{nm} \tilde{\mathbf{K}}_{mm}^{-1} \tilde{\mathbf{K}}_{mn}$ , что снижает сложность до $O(n m^2)$ .

Заключение

Ядра — это мощная и математически строгая концепция, позволяющая неявно строить нелинейные модели без необходимости работы с координатами в многомерных пространствах. Для практика они являются незаменимым инструментом, обеспечивающим высокое качество на малых и средних выборках сложной структуры. Ключом к успешному применению является системный подход: начиная с простого линейного baseline, обоснованно переходя к RBF-ядру, и всегда настраивая гиперпараметры $(C, \gamma)$ через кросс-валидацию. Понимание ядерного трюка не только обогащает арсенал инженера алгоритмами (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.
Hsu C.-W., Chang C.-C., Lin C.-J. A Practical Guide to Support Vector Classification. — National Taiwan University, 2003 (последнее обновление: 2016). — Практическое руководство по выбору ядер и настройке гиперпараметров.

Источник — «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>\mathbf{x}_i</tex> входят только в операциях скалярного произведения <tex>\langle \mathbf{x}_i, \mathbf{x}_j \rangle</tex>. Часто это возможно благодаря переходу от прямой (параметрической) формы к двойственной (основанной на данных). Классический пример — двойственная задача [[Метод опорных векторов|SVM]], где матрица <tex>\mathbf{X}\mathbf{X}^T</tex> в целевой функции содержит именно попарные скалярные произведения.
+# '''Подстановка ядра''': Как только алгоритм представлен в терминах <tex>\langle \mathbf{x}_i, \mathbf{x}_j \rangle</tex>, производится замена <tex>\langle \mathbf{x}_i, \mathbf{x}_j \rangle \to \kappa(\mathbf{x}_i, \mathbf{x}_j)</tex> как в процессе обучения, так и при предсказании. Для нового объекта <tex>\mathbf{x}_{\text{new}}</tex> предсказание также будет зависеть от ядерных вычислений <tex>\kappa(\mathbf{x}_i, \mathbf{x}_{\text{new}})</tex> между ним и опорными (или всеми обучающими) векторами.
-Такой прием называется '''ядерной уловкой''' (kernel trick).
+Таким образом, алгоритм неявно работает в пространстве <tex>\mathcal{H}</tex>, но не требует ни вычисления отображения <tex>\varphi</tex>, ни знания размерности этого пространства. Это позволяет, например, использовать RBF-ядро, соответствующее бесконечномерному <tex>\varphi</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>. Это условие гарантирует, что функция ядра неявно соответствует скалярному произведению в некотором, возможно, бесконечномерном, пространстве.
-С математической точки зрения, функция <tex>K: \mathcal{X} \times \mathcal{X} \rightarrow \mathbb{R}</tex> является допустимой для использования в методах, основанных на [[Воспроизводящее ядро гильбертова пространства|гильбертовых пространствах с воспроизводящим ядром]] (RKHS), тогда и только тогда, когда она является симметричной и положительно полуопределенной.
+=== Интуитивное объяснение роли Теоремы Мерсера ===
+На интуитивном уровне теорема Мерсера и условие положительной определенности решают фундаментальную проблему: гарантируют, что наша "подмена" скалярного произведения ядром математически корректна. Ключевая идея в следующем:
+# '''Существование пространства''': Мы заменяем <tex>\langle \mathbf{x}_i, \mathbf{x}_j \rangle</tex> на <tex>\kappa(\mathbf{x}_i, \mathbf{x}_j)</tex>, подразумевая, что где-то "есть" признаки <tex>\varphi(\mathbf{x})</tex>, для которых ядро дает скалярное произведение. Теорема Мерсера гарантирует, что для любой симметричной и положительно определенной функции такое пространство и такое отображение действительно ''существуют'', даже если мы никогда не будем их строить. Без этой гарантии мы не могли бы полагаться на корректность операций, основанных на аксиомах скалярного произведения.
+# **Оптимизационная интерпретация**: Условие <tex>\mathbf{c}^T \mathbf{K} \mathbf{c} \ge 0</tex> означает, что функция потерь, записанная в терминах ядра, остается выпуклой. Например, двойственная задача SVM остается задачей выпуклого квадратичного программирования, что гарантирует существование единственного глобального оптимума и эффективную сходимость алгоритмов оптимизации. Если бы матрица <tex>\mathbf{K}</tex> не была положительно полуопределенной, задача оптимизации могла бы стать невыпуклой с множеством локальных минимумов.
+# **Геометрическая согласованность**: Условие положительной определенности гарантирует, что ядро порождает геометрию, согласованную с понятиями расстояния и угла в некотором евклидовом пространстве. Расстояние между образами, индуцированное ядром, <tex>\|\varphi(\mathbf{x}) - \varphi(\mathbf{x}')\|^2 = \kappa(\mathbf{x}, \mathbf{x}) + \kappa(\mathbf{x}', \mathbf{x}') - 2\kappa(\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_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>\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>K(\mathbf{x}, \mathbf{x}') = \langle \mathbf{x}, \mathbf{x}' \rangle</tex>
+где <tex>d \in \mathbb{N}</tex> — степень полинома, <tex>\gamma > 0</tex> — коэффициент масштабирования, <tex>c \ge 0</tex> — свободный член. Это ядро соответствует пространству всех мономиальных признаков степени вплоть до <tex>d</tex>. Оно позволяет улавливать полиномиальные взаимодействия между исходными признаками.
-Используется, когда данные и так почти линейно разделимы, или при очень высокой размерности исходного пространства (например, в задачах классификации текстов).
-==== Полиномиальное ядро ====
+=== Радиально-базисное ядро (Гауссово, RBF) ===
-Представляет скалярные произведения в пространстве всех мономов степени до <tex>d</tex>.
+<tex>\kappa(\mathbf{x}, \mathbf{x}') = \exp\left( -\gamma \|\mathbf{x} - \mathbf{x}'\|^2 \right)</tex>
-<tex>K(\mathbf{x}, \mathbf{x}') = (\gamma \langle \mathbf{x}, \mathbf{x}' \rangle + c_0)^d</tex>
+где <tex>\gamma > 0</tex> — параметр ширины ядра. Это одно из самых популярных ядер. Оно соответствует бесконечномерному признаковому пространству и может моделировать чрезвычайно сложные, локальные зависимости. Параметр <tex>\gamma</tex> контролирует "радиус влияния" одного примера: большое значение приводит к переобучению (гибкая, изрезанная граница), маленькое — к недообучению (почти линейная граница).
-* '''Параметры:''' <tex>d</tex> — степень полинома, <tex>c_0</tex> — свободный член (trade-off между влиянием старших и младших степеней), <tex>\gamma</tex> — коэффициент масштабирования.
-* Хорошо подходит для данных, где зависимости имеют полиномиальный характер, но склонно к переобучению при больших <tex>d</tex>.
-==== Гауссово ядро (Radial Basis Function, RBF) ====
+=== Сигмоидное ядро ===
-Наиболее популярное универсальное ядро, соответствующее бесконечномерному пространству признаков.
+<tex>\kappa(\mathbf{x}, \mathbf{x}') = \tanh(\gamma \langle \mathbf{x}, \mathbf{x}' \rangle + c)</tex>
-<tex>K(\mathbf{x}, \mathbf{x}') = \exp\left( -\gamma \|\mathbf{x} - \mathbf{x}'\|^2 \right)</tex>
+Данное ядро происходит из области [[Нейронная сеть|нейронных сетей]]. Однако оно является допустимым (положительно определенным) только для некоторых значений параметров <tex>\gamma, c</tex>, что ограничивает его прямое использование в строгой ядерной теории, хотя на практике оно иногда применяется.
-* '''Параметр:''' <tex>\gamma > 0</tex> (часто задается как <tex>\gamma = \frac{1}{2\sigma^2}</tex>). Определяет «радиус влияния» одного примера на другой. При малом <tex>\gamma</tex> граница решения получается гладкой (недообучение), при большом — сложной, подстраивающейся под каждый выброс (переобучение).
-* Является универсальным аппроксиматором.
-==== Сигмоидное ядро ====
+=== Ядра для специфических структур данных ===
-<tex>K(\mathbf{x}, \mathbf{x}') = \tanh(\gamma \langle \mathbf{x}, \mathbf{x}' \rangle + c_0)</tex>
+Ядерный подход не ограничивается векторами из <tex>\mathbb{R}^d</tex>. Существуют ядра, определенные на строках (на основе [[Расстояние Левенштейна|расстояния редактирования]]), графах (ядро случайных блужданий, ''random walk kernel''), множествах, деревьях и других сложных объектах. Это позволяет применять весь арсенал ядерных методов к задачам [[Биоинформатика|биоинформатики]], [[Компьютерная лингвистика|обработки текстов]] и хемоинформатики.
-Происходит из теории нейронных сетей. Является допустимым (положительно определенным) только при определенных значениях параметров, что ограничивает его применение на практике по сравнению с RBF.
-==== Ядра для специфических структур данных ====
+== Ядерный трюк в действии: пример ядерной гребневой регрессии ==
-Мощь ядерного подхода проявляется в возможности задавать сходство для невекторных объектов.
+Рассмотрим задачу [[Линейная регрессия|линейной регрессии]] с квадратичной функцией потерь и 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>:
-* '''Строковые ядра (String kernels):''' Измеряют сходство текстов через количество общих подстрок (спектральное ядро) или расстояние Левенштейна.
+<tex>\mathbf{y}_{\text{pred}}(\mathbf{x}_{\text{new}}) = \mathbf{y}^T (\mathbf{K} + \lambda \mathbf{I})^{-1} \mathbf{k}</tex>,
-* '''Ядра на графах (Graph kernels):''' Вычисляют сходство графов через случайные блуждания (Random Walk kernel) или сравнение подграфов (Weisfeiler-Lehman kernel).
+где <tex>\mathbf{K}</tex> — матрица Грама на обучающей выборке, а вектор <tex>\mathbf{k}</tex> состоит из ядерных оценок <tex>\kappa(\mathbf{x}_i, \mathbf{x}_{\text{new}})</tex>. Замена всех скалярных произведений на функцию ядра дает нелинейную '''ядерную гребневую регрессию''', способную аппроксимировать сложные нелинейные функции.
-* '''Ядра на вероятностных распределениях:''' Например, ядро Фишера (Fisher kernel), использующее градиенты логарифмического правдоподобия порождающей модели.
-=== Конструирование ядер ===
+== Практические примеры применения ядер ==
+Ядерные методы демонстрируют высокую эффективность в ситуациях, где данные не являются линейно разделимыми, а размерность признакового пространства высока. Ниже приведены два характерных примера из реальной практики.
-Новые ядра могут быть построены из существующих с помощью набора алгебраических операций, замкнутых относительно свойства положительной определенности:
+=== Классификация текстов: SVM с ядром RBF для анализа тональности ===
-# '''Сумма:''' <tex>K(\mathbf{x}, \mathbf{y}) = K_1(\mathbf{x}, \mathbf{y}) + K_2(\mathbf{x}, \mathbf{y})</tex>
+В задаче анализа тональности отзывов требуется определить, является ли текст положительным или отрицательным.
-# '''Произведение:''' <tex>K(\mathbf{x}, \mathbf{y}) = K_1(\mathbf{x}, \mathbf{y}) \cdot K_2(\mathbf{x}, \mathbf{y})</tex>
+# '''Векторизация''': Каждый документ преобразуется в вектор <tex>\mathbf{x} \in \mathbb{R}^d</tex> с помощью [[TF-IDF]]-взвешивания, где <tex>d</tex> — размер словаря (обычно десятки тысяч слов). В таком пространстве документы разных классов часто перекрываются и не разделяются линейно из-за синонимии, многозначности слов и сложных контекстных взаимосвязей.
-# '''Прямое произведение признаков:''' <tex>K(\mathbf{x}, \mathbf{y}) = f(\mathbf{x}) f(\mathbf{y})</tex> для любой вещественной функции <tex>f</tex>.
+# '''Выбор ядра''': Линейное ядро (по сути, линейный классификатор) является хорошим baseline, но для улавливания нелинейных взаимодействий между термами применяется '''RBF-ядро'''. Оно позволяет неявно моделировать ситуации вида "наличие слова A вблизи слова B меняет смысл на противоположный", что недоступно чисто линейной модели.
-# '''Предельный переход:''' Предел сходящейся последовательности ядер также является ядром.
+# '''Результат''': SVM с RBF-ядром на представлении TF-IDF долгое время была стандартом де-факто для задач классификации текстов до появления [[Word2Vec]] и [[Трансформер (архитектура)|трансформеров]], показывая точность, превосходящую наивный байесовский классификатор и линейные модели.
-=== Применение в алгоритмах ===
+=== Классификация изображений: ядерный SVM в эпоху до глубокого обучения ===
+До повсеместного распространения [[Свёрточная нейронная сеть|свёрточных нейронных сетей]] одним из лучших подходов к классификации рукописных цифр ([[MNIST]]) и распознаванию объектов в небольших датасетах был следующий пайплайн:
+# '''Извлечение признаков''': Из изображений извлекались высокоуровневые признаки, инвариантные к сдвигу и повороту, например, [[Гистограмма направленных градиентов|HOG]] (Histogram of Oriented Gradients) или признаки на основе банка фильтров Габора.
+# '''Классификация''': Полученные векторы признаков классифицировались с помощью '''SVM с RBF-ядром''' или '''полиномиальным ядром''' степени 2 или 3. Ядро неявно моделировало сложные взаимодействия между выходами различных фильтров, соответствующие определенным формам и текстурам.
+# '''Преимущество''': Такой подход был вычислительно эффективнее и требовал меньше данных для обучения, чем полносвязные нейронные сети того времени, и служил стандартным, очень сильным бейзлайном в компьютерном зрении.
-Хотя ядерный трюк наиболее известен по 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) ====
+* '''1. Линейное ядро (Baseline)''': Всегда следует начинать с него. Термин ''baseline'' (базовая модель) означает простую, хорошо интерпретируемую и быстро обучаемую модель, которая служит точкой отсчета. Если линейное ядро дает приемлемое качество, его, как правило, и выбирают. Линейная модель:
-Позволяет находить нелинейные многообразия в данных. Вместо анализа ковариационной матрицы исходных данных анализируется матрица Грама <tex>\mathbf{K}</tex>. Решение сводится к нахождению собственных векторов центрированной матрицы <tex>\mathbf{K}</tex>, что эквивалентно PCA в пространстве RKHS.
+** ''Предпочтительна'', когда размерность признакового пространства <tex>d</tex> очень велика (например, <tex>d \approx 10^5</tex> в задачах анализа текстов с TF-IDF). В таких данных высокая размерность часто уже обеспечивает хорошую линейную разделимость, а введение нелинейности чревато переобучением.
+** ''Интерпретируема'': веса признаков <tex>\mathbf{w}</tex> могут быть проанализированы, что важно в биоинформатике или финансах.
+** ''Вычислительно эффективна'': обучение может быть выполнено за линейное время от <tex>d</tex>, минуя построение полной ядерной матрицы <tex>O(n^2)</tex>.
-==== Ядерная регрессия (Kernel Ridge Regression) ====
+* '''2. Радиально-базисное ядро (RBF)''': Это следующий шаг, если линейное ядро показало неудовлетворительный результат. RBF-ядро является выбором "по умолчанию" для нелинейных задач по ряду причин:
-Эквивалентна построению линейной регрессии в пространстве признаков с L2-регуляризацией. Решение в замкнутой форме:
+** ''Универсальность'': Теоретически, при правильном подборе <tex>\gamma</tex> и <tex>C</tex> способно аппроксимировать любую непрерывную границу решений.
-<tex>\boldsymbol{\alpha} = (\mathbf{K} + \lambda \mathbf{I})^{-1} \mathbf{y}</tex>,
+** ''Численная стабильность'': Значения ядра лежат в диапазоне <tex>(0, 1]</tex>, что обеспечивает хорошую обусловленность матрицы Грама, в отличие от полиномиального ядра высокой степени, значения которого могут расходиться.
-где <tex>\lambda</tex> — параметр регуляризации. Позволяет строить гладкие нелинейные регрессионные модели.
+** ''Малое число гиперпараметров'': Всего два (<tex>C</tex> и <tex>\gamma</tex>), что упрощает настройку по сравнению с полиномиальным ядром.
-==== Гауссовские процессы ====
+* '''3. Полиномиальное ядро''': Используется реже RBF, но целесообразно в случаях, когда предметная область подразумевает полиномиальный характер взаимодействий (например, в некоторых задачах физики или при кодировании взаимодействий генов). Основная трудность — настройка сразу трех гиперпараметров: <tex>d, \gamma, c</tex>.
-В [[Гауссовский процесс|гауссовских процессах]] ядро (часто называемое ковариационной функцией) определяет гладкость и свойства априорного распределения над функциями. Выбор ядра критичен: RBF-ядро порождает бесконечно дифференцируемые функции, а ядро Матерна позволяет контролировать степень гладкости явно.
-=== Ограничения и практические аспекты ===
+=== Детальная настройка гиперпараметров ===
+Гиперпараметры ядерных методов управляют компромиссом между переобучением и недообучением. Их подбор всегда осуществляется на отложенной валидационной выборке через решетчатый поиск (''Grid Search'') с кросс-валидацией.
-Несмотря на элегантность, ядерные методы обладают недостатками:
+* '''Параметр регуляризации <tex>C</tex> (для SVM)''': Общий для ядерных SVM. Это параметр, определяющий штраф за неправильную классификацию обучающих примеров. Контролирует баланс между шириной разделяющей полосы и количеством ошибок на обучении.
-* '''Вычислительная сложность:''' Прямые методы требуют обращения матрицы Грама размером <tex>n \times n</tex>, что приводит к сложности <tex>O(n^3)</tex> и памяти <tex>O(n^2)</tex>. Это делает их неприменимыми к миллионам объектов без аппроксимаций (например, Nyström method, Random Fourier Features).
+** ''Малое <tex>C</tex> (<tex>10^{-3} \dots 10^{-1}</tex>)'': Увеличивает ширину полосы, разрешая множественные нарушения границы. Приводит к более гладкой, простой границе решений. Используется при сильном переобучении или зашумленных данных. Эквивалентно сильной регуляризации.
-* '''Выбор ядра и гиперпараметров:''' Критически важен и обычно осуществляется через [[кросс-валидация|кросс-валидацию]] (grid search). Неудачный выбор <tex>\gamma</tex> в RBF легко ведет к переобучению.
+** ''Большое <tex>C</tex> (<tex>10^2 \dots 10^4</tex>)'': Штрафует ошибки на обучающей выборке очень сильно, стремясь классифицировать все примеры верно. Полоса сужается, граница становится изрезанной и подстраивается под индивидуальные выбросы. Ведет к переобучению. Эквивалентно слабой регуляризации.
-* '''Интерпретируемость:''' Модель в неявном пространстве RKHS трудно интерпретировать, в отличие от разреженных линейных моделей на исходных признаках.
+** ''Рекомендуемый диапазон поиска'': Экспоненциальная сетка, например, <tex>[10^{-3}, 10^{-2}, ..., 10^3, 10^4]</tex>.
-=== Литература ===
+* '''Параметр ширины ядра <tex>\gamma</tex> (для RBF, полиномиального и сигмоидного ядер)''': Определяет "радиус влияния" одного примера или масштаб скалярного произведения.
-# Schölkopf, B., Smola, A. J. ''Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond''. — MIT Press, 2002. (Классический фундаментальный труд).
+** ''Малое <tex>\gamma</tex> (<tex>10^{-4} \dots 10^{-2}</tex>)'': Модель "видит" примеры как далеко рассеянные; даже далекие точки считаются похожими (<tex>\kappa(\mathbf{x}, \mathbf{x}') \to 1</tex>). Граница решений получается очень гладкой, почти линейной, что ведет к сильному недообучению.
-# Bishop, C. M. ''Pattern Recognition and Machine Learning''. — Springer, 2006. — Глава 6: Kernel Methods.
+** ''Большое <tex>\gamma</tex> (<tex>10 \dots 10^3</tex>)'': Влияние каждого примера становится чрезвычайно локальным; уже небольшие расстояния приводят к почти нулевому сходству (<tex>\kappa(\mathbf{x}, \mathbf{x}') \to 0</tex>). Граница решений формирует маленькие "островки" вокруг опорных векторов, идеально разделяя обучающие данные, но теряя способность к обобщению — классическое переобучение.
-# Hofmann, T., Schölkopf, B., Smola, A. J. ''Kernel methods in machine learning'' // The Annals of Statistics. — 2008. — Т. 36, № 3. — С. 1171–1220.
+** ''Эвристика для начального приближения'': Установите <tex>\gamma \approx 1 / d</tex>, где <tex>d</tex> — количество признаков, или используйте <tex>\gamma \approx 1 / \text{медиана}(\|\mathbf{x}_i - \mathbf{x}_j\|^2)</tex>, что масштабирует параметр, делая его инвариантным к дисперсии данных.
-# Rasmussen, C. E., Williams, C. K. I. ''Gaussian Processes for Machine Learning''. — MIT Press, 2006.
+** ''Рекомендуемый диапазон поиска'': Экспоненциальная сетка, например, <tex>[10^{-5}, 10^{-4}, ..., 10^2, 10^3]</tex>. Решетчатый поиск по паре <tex>(C, \gamma)</tex> критичен для достижения высокой точности.
-# Вьюгин, В. В. ''Математические основы теории машинного обучения и прогнозирования''. — МЦНМО, 2013.
+* '''Параметры полиномиального ядра <tex>d, \gamma, c</tex>''':
+** ''Степень <tex>d</tex>'': Определяет максимальную сложность взаимодействия признаков. Обычно ограничивается значениями <tex>d = 2</tex> или <tex>3</tex>. Большие степени (<tex>d > 5</tex>) почти гарантированно приводят к переобучению и численной нестабильности, поэтому на практике используются редко.
+** ''Свободный член <tex>c</tex>'': Обычно фиксируется как <tex>c=0</tex> (однородный полином) или <tex>c=1</tex> (неоднородный, учитывающий взаимодействия всех степеней вплоть до <tex>d</tex>). Настройка <tex>c</tex> как непрерывного гиперпараметра используется редко.
+** ''Рекомендация'': Если линейное и RBF ядра не дали результата, попробуйте комбинации <tex>d \in \{2, 3\}</tex>, <tex>c \in \{0, 1\}</tex>, а <tex>\gamma</tex> ищите по сетке, аналогичной RBF.
+=== Нормализация данных ===
+Перед применением ядер, чувствительных к масштабу признаков (особенно RBF и полиномиального), '''строго необходима''' предварительная стандартизация признаков. Процедура заключается в вычитании среднего значения признака и делении на его стандартное отклонение. Без этого признаки с большим численным диапазоном будут доминировать в евклидовой метрике <tex>\|\mathbf{x} - \mathbf{x}'\|^2</tex>, полностью подавляя вклад других, не менее информативных признаков. Для данных с неизвестной природой рекомендуется применять [[Масштабирование признаков|RobustScaler]] (использующий медиану и квартили), устойчивый к выбросам.
+=== Вычислительная сложность ===
+Основной недостаток точных ядерных методов — необходимость вычисления и хранения матрицы Грама <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>). В таких случаях вместо точных методов прибегают к линейным аппроксимациям ядер, например:
+* '''Метод случайных признаков''' (''Random Fourier Features''): Строится конечномерная аппроксимация <tex>\tilde{\varphi}(\mathbf{x})</tex> пространства RBF-ядра, после чего применяется быстрый линейный метод.
+* '''Аппроксимация Найстрома''' (''Nyström method''): Выбирается подмножество из <tex>m \ll n</tex> примеров, и полная ядерная матрица аппроксимируется низкоранговой матрицей <tex>\mathbf{K} \approx \tilde{\mathbf{K}}_{nm} \tilde{\mathbf{K}}_{mm}^{-1} \tilde{\mathbf{K}}_{mn}</tex>, что снижает сложность до <tex>O(n m^2)</tex>.
+== Заключение ==
+Ядра — это мощная и математически строгая концепция, позволяющая неявно строить нелинейные модели без необходимости работы с координатами в многомерных пространствах. Для практика они являются незаменимым инструментом, обеспечивающим высокое качество на малых и средних выборках сложной структуры. Ключом к успешному применению является системный подход: начиная с простого линейного baseline, обоснованно переходя к RBF-ядру, и всегда настраивая гиперпараметры <tex>(C, \gamma)</tex> через кросс-валидацию. Понимание ядерного трюка не только обогащает арсенал инженера алгоритмами (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.
+# Hsu C.-W., Chang C.-C., Lin C.-J. A Practical Guide to Support Vector Classification. — National Taiwan University, 2003 (последнее обновление: 2016). — Практическое руководство по выбору ядер и настройке гиперпараметров.