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

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

Версия от 16:29, 12 июля 2026; Nikita Zinoviсh (Обсуждение | вклад)

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

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

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

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

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

Содержание

1 Мотивация: неявное погружение в гильбертовы пространства
2 Математический фундамент: Ядра и пространства RKHS
3 Канонические ядра: анализ размерности признакового пространства
4 Ядерный трюк и Теорема о представлении
5 Ядерная гребневая регрессия (Kernel Ridge Regression)

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

Пусть задана обучающая выборка объектов $\{(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}$ .

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

Вычислительная сложность: если $D$ велико (например, при полиномиальном расширении высокой степени), вычисление вектора $\Phi(x)$ требует высоких временных и аппаратных затрат $O(D)$ .
Теоретическое ограничение: если $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}</mrow> и отображение <tex>\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}\}$ . Оно уникально для каждого ядра и обладает воспроизводящим свойством:

Функция $K(x, \cdot)$ сама является элементом пространства $\mathcal{H}_K$ для любого $x$ .
Скалярное произведение любой функции $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</text> Поскольку значение функции во всех точках выборки определяется только компонентой <tex>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</text>. Значит, <tex>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}</text> — матрица Грама, а <tex>\alpha = [\alpha_1, \dots, \alpha_n]^T</text>. Квадрат нормы функции раскрывается через скалярное произведение в RKHS: <tex>\|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</text> Задача минимизации полностью сводится к конечномерной квадратичной форме относительно вектора весов <tex>\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</text> Для нахождения глобального экстремума вычислим [[Градиент|градиент]] по вектору <tex>\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}</text> </li></ol> Поскольку матрица Грама <tex>\mathbf{K}</text> полуположительно определена, а параметр регуляризации <tex>\lambda > 0</text>, матрица в скобках <tex>(\mathbf{K} + \lambda \mathbf{I})</text> строго положительно определена и гарантированно обратима. Следовательно, уравнение имеет единственное аналитическое решение: <tex>\alpha^* = (\mathbf{K} + \lambda \mathbf{I})^{-1} y</text> Для предсказания значения в новой произвольной точке <tex>x</text> используется вектор значений ядра между новым объектом и обучающей выборкой <tex>\mathbf{k}(x) = [K(x, x_1), \dots, K(x, x_n)]^T</text>: <tex>f^*(x) = \sum_{i=1}^n \alpha_i^* K(x, x_i) = \mathbf{k}(x)^T (\mathbf{K} + \lambda \mathbf{I})^{-1} y</text> == Резюме: класс решаемых задач и смысл решения == Построенный математический аппарат позволяет строго очертить класс задач и физический смысл их решения в ядерной форме. '''Класс решаемых задач:''' Это задачи '''непараметрического восстановления функций''' (регрессии, интерполяции и аппроксимации) по конечной зашумленной выборке в условиях, когда: <ul><li> Истинная зависимость существенно нелинейна, а её аналитический вид априори неизвестен. </li><li> Объекты выборки <tex>x</text> имеют сложную нелинейную структуру или являются нечисловыми (последовательности, графы), но для них можно задать симметричную функцию близости, удовлетворяющую критерию положительной определенности Мерсера. </li></ul> '''Что значит «решить задачу» в данном случае:''' Решить задачу ядерным методом означает найти глобально оптимальную функцию <tex>f^*(x)</text> в [[Гильбертово пространство|гильбертовом пространстве]] гипотез, что физически выражается в следующем: <ol><li> '''Геометрически:''' Найти такую разделяющую или аппроксимирующую гиперплоскость в бесконечномерном пространстве <tex>\mathcal{H}_K</text>, которая в исходном пространстве <tex>\mathcal{X}</text> разворачивается в сложную нелинейную поверхность, идеально проходящую через точки данных с учетом заданного уровня шума. </li><li> '''Алгебраически:''' Свести бесконечномерную вариационную задачу к конечномерной системе линейных уравнений размерности <tex>n \times n</text> (где <tex>n</text> — размер выборки). Решением является единственный вектор коэффициентов <tex>\alpha^*</text>, который определяет вклад каждого обучающего объекта в предсказание для новой точки. </li><li> '''Статистически:''' Найти компромисс между точностью приближения выборки ([[Эмпирический риск|эмпирическим риском]]) и гладкостью итоговой функции. Штраф за норму в RKHS <tex>\|f\|_{\mathcal{H}_K}^2</text> гарантирует, что решение не будет хаотично осциллировать между точками обучения, подавляя [[Переобучение|переобучение]]. </li></ol> == См. также == <ul><li> [[Метод опорных векторов]] </li><li> [[Метод главных компонент]] </li><li> [[Регуляризация Тихонова]] </li><li> [[Непараметрическая регрессия]] </li></ul> == Литература == <ol><li> '' Schölkopf B., Smola A. J.'' Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond. — MIT Press, 2002. </li><li> '' Shawe-Taylor J., Cristianini N.'' Kernel Methods for Pattern Analysis. — Cambridge University Press, 2004. </li><li> '' Расмуссен К. В., Уильямс К. И.'' Гауссовские процессы в машинном обучении. — Физматлит, 2014. </li><li> '' Мерсер Дж.'' Functions of positive and negative type, and their connection with the theory of integral equations. — Philosophical Transactions of the Royal Society A, 1909.$