Ядерные методы в статистике

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

Перейти к: навигация, поиск
Статья написана с использованием LLM Gemini Flash 3.5 и проверена участником Nikita Zinoviсh 20:38, 12 июля 2026 (MSD)


Математические основы ядерных методов.

Содержание

Мотивация: неявное погружение в гильбертовы пространства

Пусть задана обучающая выборка объектов \{(x_i, y_i)\}_{i=1}^n, где x_i \in \mathcal{X} \subset \mathbb{R}^d, а y_i \in \mathbb{R}. Задача линейной регрессии состоит в поиске вектора весов w \in \mathbb{R}^d, минимизирующего некоторый эмпирический риск. Однако если истинная зависимость y от x нелинейна, класс линейных функций обладает высоким смещением.

Стандартный статистический подход для расширения класса гипотез — введение нелинейного отображения признаков:

\Phi: \mathcal{X} \to \mathcal{H}

где \mathcal{H} — новое гильбертово пространство большей размерности \dim(\mathcal{H}) = D \gg d. Линейная модель в этом пространстве имеет вид f(x) = \langle w, \Phi(x) \rangle_{\mathcal{H}}, где w \in \mathcal{H}.

Попытка явного вычисления и оптимизации такой модели сталкивается со следующими ограничениями:

  1. Вычислительная сложность: если D велико (например, при полиномиальном расширении высокой степени), вычисление вектора \Phi(x) требует высоких временных и аппаратных затрат O(D).
  2. Теоретическое ограничение: если D = \infty (пространство бесконечномерно), явное представление вектора \Phi(x) в памяти и покоординатное вычисление скалярного произведения \langle \Phi(x), \Phi(x') \rangle_{\mathcal{H}} физически невозможны.

Математический фундамент: Ядра и пространства RKHS

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

Определение 1. Функция двух переменных K: \mathcal{X} \times \mathcal{X} \to \mathbb{R} называется положительно определенным ядром, если она симметрична (K(x, x') = K(x', x)) и для любого конечного набора объектов \{x_i\}_{i=1}^n матрица Грама \mathbf{K} \in \mathbb{R}^{n \times n} с элементами \mathbf{K}_{ij} = K(x_i, x_j) является полуположительно определенной:

\forall c \in \mathbb{R}^n, \quad c^T \mathbf{K} c = \sum_{i=1}^n \sum_{j=1}^n c_i c_j K(x_i, x_j) \ge 0

Связь между абстрактным положительно определенным ядром K и геометрическим пространством \mathcal{H} устанавливает Теорема Мерсера: если ядро K непрерывно и положительно определено на компакте, то существует пространство \mathcal{H} и отображение \Phi: \mathcal{X} \to \mathcal{H}, такие что:

K(x, x') = \langle \Phi(x), \Phi(x') \rangle_{\mathcal{H}}

Для характеризации класса функций, который порождает такое ядро, вводится понятие воспроизводящего ядерного гильбертова пространства (RKHS) \mathcal{H}_K. Это пространство функций f: \mathcal{X} \to \mathbb{R}, конструируемое как замыкание линейной оболочки элементов вида \{K(x, \cdot) \mid x \in \mathcal{X}\}. Оно уникально для каждого ядра и обладает воспроизводящим свойством:

  1. Функция K(x, \cdot) сама является элементом пространства \mathcal{H}_K для любого x.
  2. Скалярное произведение любой функции f \in \mathcal{H}_K с «сечением» ядра вычисляет значение этой функции в точке x:
\langle f, K(x, \cdot) \rangle_{\mathcal{H}_K} = f(x)

Из этого свойства напрямую следует, что скалярное произведение самих ядерных функций возвращает значение ядра: \langle K(x, \cdot), K(x', \cdot) \rangle_{\mathcal{H}_K} = K(x, x'). Норма функции в этом пространстве \|f\|_{\mathcal{H}_K}^2 служит строгой мерой её гладкости: чем сильнее функция осциллирует между точками, тем выше её норма.

Канонические ядра: анализ размерности признакового пространства

Рассмотрим, как конкретная аналитическая форма ядра определяет размерность пространства \mathcal{H}_K.

Полиномиальное ядро:

K(x, x') = (x^T x' + 1)^d, \quad d \in \mathbb{N}

При раскрытии скобок по формуле бинома Ньютона ядро распадается на сумму скалярных произведений мономов всех степеней до d. Количество таких мономов конечно, следовательно, \dim(\mathcal{H}_K) конечно.

Гауссово ядро (RBF):

K(x, x') = \exp\left(-\frac{1}{2} \|x - x'\|^2\right)

Покажем, что это ядро порождает бесконечномерное пространство. Для простоты рассмотрим одномерный случай x, x' \in \mathbb{R}. Используя свойства экспоненты, перепишем ядро:

K(x, x') = e^{-\frac{1}{2}x^2} e^{-\frac{1}{2}(x')^2} e^{xx'}

Разложим сомножитель e^{xx'} в бесконечный ряд Тейлора:

K(x, x') = e^{-\frac{1}{2}x^2} e^{-\frac{1}{2}(x')^2} \sum_{m=0}^{\infty} \frac{(xx')^m}{m!} = \sum_{m=0}^{\infty} \left( \frac{e^{-\frac{1}{2}x^2} x^m}{\sqrt{m!}} \right) \left( \frac{e^{-\frac{1}{2}(x')^2} (x')^m}{\sqrt{m!}} \right)

Полученное выражение эквивалентно стандартному определению скалярного произведения в пространстве последовательностей \ell_2 для неявного отображения вида:

\Phi(x) = \left[ e^{-\frac{1}{2}x^2}, \ e^{-\frac{1}{2}x^2}x, \ \frac{1}{\sqrt{2!}}e^{-\frac{1}{2}x^2}x^2, \ \dots, \ \frac{1}{\sqrt{m!}}e^{-\frac{1}{2}x^2}x^m, \ \dots \right]^T

Так как функции \{e^{-\frac{1}{2}x^2}x^m\} линейно независимы при разных m, базис пространства бесконечен. Соответственно, \dim(\mathcal{H}_K) = \infty.

Ядерный трюк и Теорема о представлении

Ядерный трюк (Kernel Trick) — это методология, позволяющая выполнять линейные операции в бесконечномерном пространстве \mathcal{H}_K без явного вычисления координат \Phi(x), заменяя любые скалярные произведения на функцию ядра: \langle \Phi(x), \Phi(x') \rangle = K(x, x').

Главное теоретическое обоснование применимости ядер к задачам оптимизации дает Теорема о представлении (Representer Theorem).

Формулировка: Пусть задана произвольная функция потерь \mathcal{L}(f(x_1), \dots, f(x_n), y_1, \dots, y_n) и строго возрастающая функция штрафа за сложность (регуляризатор) \Omega(\|f\|_{\mathcal{H}_K}). Тогда любая функция f^*, минимизирующая полный регуляризованный риск:

f^* = \arg\min_{f \in \mathcal{H}_K} \left( \mathcal{L}(f(x_1), \dots, f(x_n), y_1, \dots, y_n) + \Omega(\|f\|_{\mathcal{H}_K}) \right)

строго представима в виде конечной линейной комбинации ядер, центрированных на элементах обучающей выборки:

f^*(x) = \sum_{i=1}^n \alpha_i K(x, x_i), \quad \alpha_i \in \mathbb{R}

Доказательство: Выделим конечномерное подпространство \mathcal{V} = \text{span}\left(\{K(x_i, \cdot)\}_{i=1}^n\right). По теореме о проекции в гильбертовых пространствах, любую функцию f \in \mathcal{H}_K можно разложить на параллельную и ортогональную составляющие: f = f_{\mathcal{V}} + v, где f_{\mathcal{V}} \in \mathcal{V}, а v \in \mathcal{V}^{\perp} (то есть \langle v, K(x_i, \cdot) \rangle_{\mathcal{H}_K} = 0 для всех i=1,\dots,n).

Вычислим значение функции f в точке обучения x_j, используя воспроизводящее свойство и линейность скалярного произведения:

f(x_j) = \langle f, K(x_j, \cdot) \rangle_{\mathcal{H}_K} = \langle f_{\mathcal{V}} + v, K(x_j, \cdot) \rangle_{\mathcal{H}_K} = \langle f_{\mathcal{V}}, K(x_j, \cdot) \rangle_{\mathcal{H}_K} + \langle v, K(x_j, \cdot) \rangle_{\mathcal{H}_K} = f_{\mathcal{V}}(x_j) + 0

Поскольку значение функции во всех точках выборки определяется только компонентой f_{\mathcal{V}}, слагаемое эмпирического риска \mathcal{L} инвариантно к ортогональному сдвигу v.

Теперь оценим норму функции f по теореме Пифагора для ортогональных векторов:

\|f\|_{\mathcal{H}_K}^2 = \|f_{\mathcal{V}} + v\|_{\mathcal{H}_K}^2 = \|f_{\mathcal{V}}\|_{\mathcal{H}_K}^2 + \|v\|_{\mathcal{H}_K}^2 \ge \|f_{\mathcal{V}}\|_{\mathcal{H}_K}^2

Так как функция \Omega строго возрастает, добавление любой компоненты v \neq 0 строго увеличивает штрафную часть функционала, не изменяя при этом значение эмпирических потерь. Следовательно, точка минимума f^* обязана иметь ортогональную компоненту \|v\| = 0 \implies v = 0. Значит, f^* \in \mathcal{V}, то есть является линейной комбинацией \sum_{i=1}^n \alpha_i K(x_i, \cdot). Теорема доказана.

Ядерная гребневая регрессия (Kernel Ridge Regression)

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

\min_{f \in \mathcal{H}_K} \left( \sum_{i=1}^n (f(x_i) - y_i)^2 + \lambda \|f\|_{\mathcal{H}_K}^2 \right), \quad \lambda > 0

По доказанной теореме о представлении, оптимум гарантированно ищется в виде f(x) = \sum_{i=1}^n \alpha_i K(x, x_i). Подставим это выражение в функционал оптимизации, переходя к матричной форме. Вектор предсказаний модели на обучающей выборке равен \mathbf{K}\alpha, где \mathbf{K} — матрица Грама, а \alpha = [\alpha_1, \dots, \alpha_n]^T. Квадрат нормы функции раскрывается через скалярное произведение в RKHS:

\|f\|_{\mathcal{H}_K}^2 = \langle \sum_{i=1}^n \alpha_i K(x_i, \cdot), \sum_{j=1}^n \alpha_j K(x_j, \cdot) \rangle_{\mathcal{H}_K} = \sum_{i=1}^n \sum_{j=1}^n \alpha_i \alpha_j K(x_i, x_j) = \alpha^T \mathbf{K} \alpha

Задача минимизации полностью сводится к конечномерной квадратичной форме относительно вектора весов \alpha \in \mathbb{R}^n:

Q(\alpha) = \|\mathbf{K}\alpha - y\|_2^2 + \lambda \alpha^T \mathbf{K} \alpha = (\mathbf{K}\alpha - y)^T(\mathbf{K}\alpha - y) + \lambda \alpha^T \mathbf{K} \alpha
Q(\alpha) = \alpha^T \mathbf{K}^2 \alpha - 2 \alpha^T \mathbf{K} y + y^T y + \lambda \alpha^T \mathbf{K} \alpha

Для нахождения глобального экстремума вычислим градиент по вектору \alpha и приравняем его к нулю:

\nabla_{\alpha} Q(\alpha) = 2 \mathbf{K}^2 \alpha - 2 \mathbf{K} y + 2 \lambda \mathbf{K} \alpha = 2 \mathbf{K} \left( (\mathbf{K} + \lambda \mathbf{I})\alpha - y \right) = \mathbf{0}

Поскольку матрица Грама \mathbf{K} полуположительно определена, а параметр регуляризации \lambda > 0, матрица в скобках (\mathbf{K} + \lambda \mathbf{I}) строго положительно определена и гарантированно обратима. Следовательно, уравнение имеет единственное аналитическое решение:

\alpha^* = (\mathbf{K} + \lambda \mathbf{I})^{-1} y

Для предсказания значения в новой произвольной точке x используется вектор значений ядра между новым объектом и обучающей выборкой \mathbf{k}(x) = [K(x, x_1), \dots, K(x, x_n)]^T:

f^*(x) = \sum_{i=1}^n \alpha_i^* K(x, x_i) = \mathbf{k}(x)^T (\mathbf{K} + \lambda \mathbf{I})^{-1} y

Резюме: класс решаемых задач и смысл решения

Построенный математический аппарат позволяет строго очертить класс задач и физический смысл их решения в ядерной форме.

Класс решаемых задач: Это задачи непараметрического восстановления функций (регрессии, интерполяции и аппроксимации) по конечной зашумленной выборке в условиях, когда:

  • Истинная зависимость существенно нелинейна, а её аналитический вид априори неизвестен.
  • Объекты выборки x имеют сложную нелинейную структуру или являются нечисловыми (последовательности, графы), но для них можно задать симметричную функцию близости, удовлетворяющую критерию положительной определенности Мерсера.

Что значит «решить задачу» в данном случае: Решить задачу ядерным методом означает найти глобально оптимальную функцию f^*(x) в гильбертовом пространстве гипотез, что физически выражается в следующем:

  1. Геометрически: Найти такую разделяющую или аппроксимирующую гиперплоскость в бесконечномерном пространстве \mathcal{H}_K, которая в исходном пространстве \mathcal{X} разворачивается в сложную нелинейную поверхность, идеально проходящую через точки данных с учетом заданного уровня шума.
  2. Алгебраически: Свести бесконечномерную вариационную задачу к конечномерной системе линейных уравнений размерности n \times n (где n — размер выборки). Решением является единственный вектор коэффициентов \alpha^*, который определяет вклад каждого обучающего объекта в предсказание для новой точки.
  3. Статистически: Найти компромисс между точностью приближения выборки (эмпирическим риском) и гладкостью итоговой функции. Штраф за норму в RKHS \|f\|_{\mathcal{H}_K}^2 гарантирует, что решение не будет хаотично осциллировать между точками обучения, подавляя переобучение.

См. также

Литература

  1. Schölkopf B., Smola A. J. Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond. — MIT Press, 2002.
  2. Shawe-Taylor J., Cristianini N. Kernel Methods for Pattern Analysis. — Cambridge University Press, 2004.
  3. Расмуссен К. В., Уильямс К. И. Гауссовские процессы в машинном обучении. — Физматлит, 2014.
  4. Мерсер Дж. Functions of positive and negative type, and their connection with the theory of integral equations. — Philosophical Transactions of the Royal Society A, 1909.
Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%AF%D0%B4%D0%B5%D1%80%D0%BD%D1%8B%D0%B5_%D0%BC%D0%B5%D1%82%D0%BE%D0%B4%D1%8B_%D0%B2_%D1%81%D1%82%D0%B0%D1%82%D0%B8%D1%81%D1%82%D0%B8%D0%BA%D0%B5»
Личные инструменты