Кернел-трюк

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

Перейти к: навигация, поиск
Статья написана с использованием 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] Термин «ядерный трюк» закрепился в литературе как краткое название вычислительной подстановки ядра вместо явного отображения, а не как обозначение единственного самостоятельного изобретения.

См. также

Примечания

Литература

Источник — «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»
Личные инструменты