Ядро

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

Ядро (англ. kernel) в контексте машинного обучения — это функция, позволяющая выполнять вычисления в неявном высокоразмерном пространстве признаков без явного отображения исходных данных в это пространство. Это фундаментальная концепция, лежащая в основе метода опорных векторов (SVM) и других ядерных методов, позволяющая эффективно моделировать нелинейные зависимости с помощью линейных алгоритмов.

Содержание 1 Неформальное введение и проблема линейной разделимости 2 Определение 3 Трюк с ядром (Kernel Trick) 4 Функция Мерсера и свойства 5 Основные семейства ядер 5.1 Стационарные ядра 5.2 Нестационарные ядра 5.3 Ядра для специфических структур данных 6 Применение в классических алгоритмах 7 Связь с гауссовскими процессами 8 Практические аспекты и выбор ядра 9 См. также 10 Литература

Неформальное введение и проблема линейной разделимости

Многие классические алгоритмы обучения (например, логистическая регрессия или перцептрон) являются линейными. Они строят разделяющую гиперплоскость в пространстве признаков. Однако реальные данные редко бывают линейно разделимы в исходном пространстве <math>\mathcal{X}</math> (например, задача XOR).

Стандартный подход к решению этой проблемы — обогащение данных: исходный вектор <math>\mathbf{x} \in \mathcal{X}</math> явно отображается в пространство более высокой размерности <math>\mathcal{H}</math> с помощью функции <math>\phi: \mathcal{X} \to \mathcal{H}</math>. Если размерность <math>\mathcal{H}</math> достаточно велика, данные с высокой вероятностью станут линейно разделимыми. Проблема этого подхода (проклятие размерности и вычислительная сложность) снимается с помощью «трюка с ядром» (kernel trick).

Определение

Пусть <math>\mathcal{X}</math> — непустое множество исходных объектов. Функция <math>K: \mathcal{X} \times \mathcal{X} \to \mathbb{R}</math> называется ядром, если существует гильбертово пространство <math>\mathcal{H}</math> (называемое пространством признаков) и отображение <math>\phi: \mathcal{X} \to \mathcal{H}</math>, такие что для любых <math>\mathbf{x}, \mathbf{x}' \in \mathcal{X}</math>:

<math>K(\mathbf{x}, \mathbf{x}') = \langle \phi(\mathbf{x}), \phi(\mathbf{x}') \rangle_{\mathcal{H}}</math>

где <math>\langle \cdot, \cdot \rangle_{\mathcal{H}}</math> — скалярное произведение в пространстве <math>\mathcal{H}</math>.

Трюк с ядром (Kernel Trick)

Ключевая идея использования ядер заключается в том, что во многих алгоритмах машинного обучения векторы признаков входят только в виде операций скалярного произведения <math>\langle \mathbf{x}_i, \mathbf{x}_j \rangle</math>.

• Линейная модель: <math>f(\mathbf{x}) = \mathbf{w}^T\mathbf{x} + b</math>. После оптимизации веса представляются как <math>\mathbf{w} = \sum_i \alpha_i \mathbf{x}_i</math>, и решающее правило примет вид <math>f(\mathbf{x}) = \sum_i \alpha_i \langle \mathbf{x}_i, \mathbf{x} \rangle + b</math>.
• Нелинейное обобщение: Заменим исходные векторы на их образы: <math>f(\mathbf{x}) = \sum_i \alpha_i \langle \phi(\mathbf{x}_i), \phi(\mathbf{x}) \rangle + b</math>.

Трюк с ядром позволяет вычислить это выражение напрямую как <math>f(\mathbf{x}) = \sum_i \alpha_i K(\mathbf{x}_i, \mathbf{x}) + b</math>, никогда не вычисляя координаты векторов <math>\phi(\mathbf{x})</math> в явном виде. Это дает возможность работать с пространствами признаков бесконечной размерности (например, используя RBF-ядро).

Функция Мерсера и свойства

Не любая функция двух переменных является ядром. Для того чтобы функция <math>K</math> была корректным ядром в рамках теории статистического обучения, она должна удовлетворять условиям теоремы Мерсера (для пространств со скалярным произведением), что эквивалентно положительной полуопределенности. Для любого конечного набора точек <math>\{\mathbf{x}_1, \dots, \mathbf{x}_n\} \subset \mathcal{X}</math> матрица Грама <math>\mathbf{K}</math>, определенная как <math>K_{ij} = K(\mathbf{x}_i, \mathbf{x}_j)</math>, должна быть симметричной и неотрицательно определенной.

Из этого свойства вытекают правила построения новых ядер из существующих (исчисление ядер):

• Сумма ядер: <math>K = K_1 + K_2</math> — ядро.
• Произведение ядер: <math>K = K_1 \cdot K_2</math> — ядро.
• Умножение на константу: <math>K = c \cdot K_1, c > 0</math> — ядро.

Основные семейства ядер

Стационарные ядра

Ядра этой группы зависят только от разности аргументов: <math>K(\mathbf{x}, \mathbf{x}') = K(\mathbf{x} - \mathbf{x}')</math>. Часто рассматриваются как функции от расстояния (ядра радиального базиса).

• Гауссовское ядро (RBF): <math>K(\mathbf{x}, \mathbf{x}') = \exp\left(-\frac{\|\mathbf{x} - \mathbf{x}'\|^2}{2\sigma^2}\right)</math>. Самое популярное ядро, соответствующее бесконечномерному пространству признаков. Параметр <math>\sigma</math> (ширина окна) управляет гладкостью границы решений.
• Ядро Лапласа: <math>K(\mathbf{x}, \mathbf{x}') = \exp\left(-\frac{\|\mathbf{x} - \mathbf{x}'\|}{\sigma}\right)</math>. Менее чувствительно к выбросам по сравнению с гауссовским.
• Рациональное квадратичное ядро: <math>K(\mathbf{x}, \mathbf{x}') = 1 - \frac{\|\mathbf{x} - \mathbf{x}'\|^2}{\|\mathbf{x} - \mathbf{x}'\|^2 + c}</math>. Представляет собой смесь RBF-ядер с разными масштабами.

Нестационарные ядра

• Полиномиальное ядро: <math>K(\mathbf{x}, \mathbf{x}') = (\langle \mathbf{x}, \mathbf{x}' \rangle + c)^d</math>. Позволяет строить полиномиальные разделяющие поверхности степени <math>d</math>. Параметр <math>c \ge 0</math> регулирует вес старших и младших степеней.
• Сигмоидное ядро: <math>K(\mathbf{x}, \mathbf{x}') = \tanh(\kappa \langle \mathbf{x}, \mathbf{x}' \rangle + \theta)</math>. Исторически связано с нейронными сетями, однако матрица Грама для него положительно определена лишь при определенных значениях параметров.

Ядра для специфических структур данных

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

• Строковые ядра (String Kernels): Измеряют сходство строк через количество общих подстрок (спектральное ядро, ядро с пропусками). Используются в биоинформатике и NLP.
• Ядра на графах: Например, Random Walk Kernel подсчитывает количество общих маршрутов в двух графах. Применяются в хемоинформатике для предсказания свойств молекул.
• Ядра Фишера: Строятся на основе вероятностных порождающих моделей, позволяя применять SVM к данным, хорошо описываемым скрытыми марковскими моделями.

Применение в классических алгоритмах

Хотя термин «kernel trick» ассоциируется в первую очередь с SVM, он применим к любому алгоритму, который можно выразить через скалярные произведения. Это утверждение носит название теоремы о представимости (Representer Theorem).

• SVM с мягким зазором (C-SVM): Классический пример, где замена скалярного произведения на ядро <math>K</math> превращает линейный классификатор в нелинейный.
• Гребневая регрессия (Kernel Ridge Regression): Нелинейный вариант регуляризованной линейной регрессии, полезный для восстановления регрессионных зависимостей малой размерности выборки.
• Метод главных компонент (Kernel PCA): Выполняет анализ главных компонент в пространстве <math>\mathcal{H}</math>, что позволяет выявлять нелинейные структуры в данных (многообразия).
• Kernel K-Means: Кластеризация данных, разделимых нелинейными границами, путем переноса центроидов в пространство признаков.

Связь с гауссовскими процессами

В гауссовских процессах (GP) ядро играет роль ковариационной функции и определяет априорные предположения о свойствах моделируемой функции (гладкость, периодичность, стационарность). В этом контексте выбор ядра — это способ кодирования знаний о предметной области в модель. Часто используемые в GP ядра (Матерна, экспоненциальное, периодическое) имеют прямые аналоги в ядерных методах, таких как SVM, но интерпретируются с вероятностной точки зрения.

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

Выбор ядра и его гиперпараметров критически важен:

• Переобучение: Слишком маленькая <math>\sigma</math> в RBF-ядре ведет к обобщению по принципу «один ближайший сосед» (переобучение), а слишком большая — к вырождению в линейную границу.
• Масштабируемость: Вычисление матрицы Грама размера <math>n \times n</math> требует <math>O(n^2)</math> памяти и <math>O(n^3)</math> времени для обращения (или <math>O(n^2)</math> для SVM). Это делает наивные ядерные методы неприменимыми к «большим данным». Проблема решается с помощью аппроксимаций:
  • Случайные признаки (Random Fourier Features): Аппроксимация стационарных ядер через прямое преобразование Фурье.
  • Метод Найстрома (Nyström Method): Низкоранговая аппроксимация матрицы Грама на основе подвыборки столбцов.

См. также

• Метод опорных векторов (SVM)
• Гауссовские процессы
• Проблема "проклятия размерности"
• Воспроизводящее ядро гильбертова пространства (RKHS)

Литература

1. Schölkopf, B., & Smola, A. J. (2002). Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond. MIT Press.
2. Bishop, C. M. (2006). Pattern Recognition and Machine Learning. Chapter 6: Kernel Methods. Springer.
3. Murphy, K. P. (2012). Machine Learning: A Probabilistic Perspective. Chapter 14: Kernels. MIT Press.
4. Rasmussen, C. E., & Williams, C. K. I. (2006). Gaussian Processes for Machine Learning. Chapter 4: Covariance Functions. MIT Press.
5. Mercer, J. (1909). "Functions of positive and negative type, and their connection with the theory of integral equations". Philosophical Transactions of the Royal Society A, 209, pp. 415–446.