Кернел-трюк

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

Версия от 16:51, 18 июля 2026; Aleksandr Pochtarev (Обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)

Перейти к: навигация, поиск

Статья написана с использованием LLM ChatGPT 5.6 Terra и проверена участником А.Ю.Почтарев 18 июля 2026

Промпт приводится полностью в Обсуждение:Кернел-трюк

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

Ядерный трюк не является отдельным алгоритмом. Он применим, когда алгоритм можно выразить через попарные скалярные произведения объектов. В такой формуле каждое скалярное произведение заменяют значением ядра. Это делает линейный алгоритм в новом признаковом пространстве нелинейным по исходным данным.

Основная идея

Пусть объект $x$ отображается в признаковое пространство функцией

$\varphi(x)$

Линейный алгоритм в этом пространстве использует скалярные произведения

$\varphi(x)^T\varphi(z)$

Ядро — это функция двух исходных объектов

$K(x,z)=\varphi(x)^T\varphi(z)$

Если значение $K(x,z)$ удаётся вычислить непосредственно по $x$ и $z$ , функцию $\varphi$ строить не нужно. Именно эту замену и называют ядерным трюком.

Например, полиномиальное ядро

$K(x,z)=(x^Tz+1)^2$

равно скалярному произведению в пространстве, содержащем исходные признаки, их квадраты и попарные произведения. Явное число таких признаков быстро растёт с размерностью и степенью полинома; вычисление одного значения ядра позволяет получить тот же результат без выписывания всех компонент отображения.^[1]

Признаковое пространство и ядро

В обычной линейной модели граница решения имеет вид

$f(x)=w^T x+b$

После преобразования признаков она становится линейной в $\varphi(x)$ :

$f(x)=w^T\varphi(x)+b$

но может быть нелинейной как функция исходного $x$ . Для многих регуляризованных методов решение представляется через обучающие объекты. Например, SVM-классификатор после подстановки ядра имеет форму

$f(x)=\sum_{i=1}^{n}\alpha_i y_i K(x_i,x)+b$

где $x_i$ — обучающие объекты, $y_i$ — их метки, а $\alpha_i$ — найденные коэффициенты. Класс определяется знаком $f(x)$ . В этой записи не требуется хранить вектор $w$ в признаковом пространстве.^[1]

Набор значений ядра на обучающей выборке образует матрицу Грама:

$K_{ij}=K(x_i,x_j)$

Она позволяет выполнять обучение, если алгоритму достаточно попарных сходств объектов. При предсказании для нового объекта нужны значения $K(x_i,x)$ .

Какие функции являются ядрами

Не всякая мера сходства является допустимым ядром. Для стандартных ядерных методов функция $K$ должна быть симметричной, а её матрица Грама — положительно полуопределённой. Это означает, что для любых чисел $c_i$ и любых объектов $x_i$ выполняется

$\sum_{i=1}^{n}\sum_{j=1}^{n}c_i c_j K(x_i,x_j) \geq 0$

Это условие гарантирует существование пространства, в котором $K$ действительно является скалярным произведением. Связь между положительно полуопределёнными ядрами и гильбертовыми пространствами с воспроизводящим ядром (англ. reproducing kernel Hilbert space, RKHS) составляет математическую основу ядерных методов.^[1]

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

Распространённые ядра

Линейное ядро: $K(x,z)=x^Tz$ . Оно не меняет пространство признаков и удобно для очень разреженных или высокоразмерных данных.
Полиномиальное ядро: $K(x,z)=(\gamma x^Tz+r)^d$ . Учитывает взаимодействия признаков до степени $d$ . Параметры $\gamma$ , $r$ и $d$ задают масштаб и сложность преобразования.
Гауссово радиально-базисное ядро (RBF, англ. radial basis function): $K(x,z)=\exp(-\gamma ||x-z||^2)$ . Сходные объекты получают близкое к единице значение, далёкие — близкое к нулю. Это ядро соответствует бесконечномерному признаковому пространству, но его значение вычисляется конечным числом операций.
Ядра для структурированных объектов: функции могут сравнивать строки, деревья, графы, множества или последовательности. Их ценность состоит в том, что в модель вводится предметно-обусловленное понятие сходства, а не только числовой вектор признаков.^[1]

У RBF-ядра параметр $\gamma$ определяет масштаб сходства: при большом значении ядро становится локальным, при малом — более глобальным. Его нельзя выбирать вне контекста масштаба признаков, поэтому числовые признаки обычно стандартизируют до обучения, а параметры ядра настраивают по перекрёстной проверке или отложенной выборке.

Применения

Наиболее известное применение ядерного трюка — SVM: алгоритм максимизации зазора использует ядро вместо явного нелинейного преобразования. В ядерном методе главных компонент (kernel PCA) тот же приём позволяет выполнять метод главных компонент в неявном признаковом пространстве и тем самым выявлять нелинейную структуру данных.^[1]

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

Преимущества и ограничения

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

Ограничения не менее важны:

ядерная матрица для $n$ обучающих объектов имеет $n^2$ элементов. Её хранение и обработка становятся дорогими на больших наборах данных;
предсказание часто требует сравнить новый объект со многими обучающими объектами или опорными векторами;
выбор ядра и его параметров задаёт индуктивное смещение модели. RBF-ядро не является универсально лучшим выбором;
большая гибкость может вызвать переобучение, если параметры ядра и регуляризации настраивать по той же части данных, на которой измеряется итоговое качество;
ядерный трюк применим только к алгоритмам, зависящим от данных через скалярные произведения. Он не превращает любой алгоритм в ядерный.

Для крупных наборов данных вместо полной матрицы ядра используют линейные модели, явные признаковые преобразования или приближения ядра, например случайные признаки (англ. random features) и метод Нистрёма (англ. Nyström method). Такие подходы обменивают точность ядрового вычисления на время и память.

История

Математическая теория воспроизводящих ядер была систематически изложена Нахманом Ароншайном в 1950 году.^[1] В 1992 году Бернхард Бозер, Изабель Гийон и Владимир Вапник описали алгоритм классификации с максимальным зазором, допускающий широкий класс преобразований входных данных, включая полиномиальные и радиально-базисные.^[1] В конце 1990-х ядерный подход вышел за пределы классификации: работа Шёлькопфа, Смолы и Мюллера 1998 года показала его применение к нелинейному методу главных компонент.^[1] Термин «ядерный трюк» закрепился в литературе как краткое название вычислительной подстановки ядра вместо явного отображения, а не как обозначение единственного самостоятельного изобретения.

См. также

Примечания

Литература

Ароншайн Н. Theory of Reproducing Kernels // Transactions of the American Mathematical Society. — 1950. — Vol. 68, no. 3. — P. 337–404.
Бозер Б. Э., Гийон И. М., Вапник В. Н. A Training Algorithm for Optimal Margin Classifiers // Proceedings of the Fifth Annual Workshop on Computational Learning Theory. — ACM, 1992. — P. 144–152.
Шёлькопф Б., Смола А. Дж., Мюллер К.-Р. Nonlinear Component Analysis as a Kernel Eigenvalue Problem // Neural Computation. — 1998. — Vol. 10, no. 5. — P. 1299–1319.
Шёлькопф Б., Смола А. Дж. Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond. — MIT Press, 2002. — 626 p. — ISBN 978-0-262-19475-4.
Хофман Т., Шёлькопф Б., Смола А. Дж. Kernel Methods in Machine Learning // The Annals of Statistics. — 2008. — Vol. 36, no. 3. — P. 1171–1220.

Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%9A%D0%B5%D1%80%D0%BD%D0%B5%D0%BB-%D1%82%D1%80%D1%8E%D0%BA»

Категории: Машинное обучение | Ядровые методы