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

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

(Различия между версиями)

Версия 16:38, 12 июля 2026

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

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

Содержание

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

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

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

Поскольку значение функции во всех точках выборки определяется только компонентой $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)$ в гильбертовом пространстве гипотез, что физически выражается в следующем:

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

См. также

Литература

Schölkopf B., Smola A. J. Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond. — MIT Press, 2002.
Shawe-Taylor J., Cristianini N. Kernel Methods for Pattern Analysis. — Cambridge University Press, 2004.
Расмуссен К. В., Уильямс К. И. Гауссовские процессы в машинном обучении. — Физматлит, 2014.
Мерсер Дж. 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»

@@ Строка 1: / Строка 1: @@
-{{well|Статья написана с использованием LLM '''Gemini Flash 3.5''' и проверена участником [[Участник:Nikita Zinovich|Nikita Zinovich]] [[Участник:Nikita Zinoviсh|Nikita Zinoviсh]] 20:23, 12 июля 2026 (MSD)}}
+{{well|Статья написана с использованием LLM '''Gemini Flash 3.5''' и проверена участником [[Участник:Nikita Zinoviсh|Nikita Zinoviсh]] 20:38, 12 июля 2026 (MSD)}}
 {{Статья
-| название = Ядерные методы в статистике
+| название = Математические основы ядерных методов
+| автор =
-}}
+| структура =
-{{well|Статья написана с использованием LLM '''Gemini Flash 3.5''' и проверена участником [[Участник:Nikita Zinoviсh|Nikita Zinoviсh]] 20:29, 12 июля 2026 (MSD)}}
-{{Статья
-| название = Ядерные методы в статистике
 }}
@@ Строка 16: / Строка 10: @@
 Стандартный статистический подход для расширения класса гипотез — введение нелинейного отображения признаков:
-<tex>\Phi: \mathcal{X} \to \mathcal{H}</tex>
+:<tex>\Phi: \mathcal{X} \to \mathcal{H}</tex>
 где <tex>\mathcal{H}</tex> — новое [[Гильбертово пространство|гильбертово пространство]] большей размерности <tex>\dim(\mathcal{H}) = D \gg d</tex>. Линейная модель в этом пространстве имеет вид <tex>f(x) = \langle w, \Phi(x) \rangle_{\mathcal{H}}</tex>, где <tex>w \in \mathcal{H}</tex>.
@@ Строка 27: / Строка 21: @@
 '''Определение 1.''' Функция двух переменных <tex>K: \mathcal{X} \times \mathcal{X} \to \mathbb{R}</tex> называется [[Положительно определенная функция|положительно определенным ядром]], если она симметрична (<tex>K(x, x') = K(x', x)</tex>) и для любого конечного набора объектов <tex>\{x_i\}_{i=1}^n</tex> матрица Грама <tex>\mathbf{K} \in \mathbb{R}^{n \times n}</tex> с элементами <tex>\mathbf{K}_{ij} = K(x_i, x_j)</tex> является полуположительно определенной:
-<tex>\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</tex>
+:<tex>\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</tex>
-Связь между абстрактным положительно определенным ядром <tex>K</tex> и геометрическим пространством <tex>\mathcal{H}</tex> устанавливает '''Теорема Мерсера''': если ядро <tex>K</tex> непрерывно и положительно определено на компакте, то существует пространство <tex>\mathcal{H}</mrow> и отображение <tex>\Phi: \mathcal{X} \to \mathcal{H}</tex>, такие что:
+Связь между абстрактным положительно определенным ядром <tex>K</tex> и геометрическим пространством <tex>\mathcal{H}</tex> устанавливает '''Теорема Мерсера''': если ядро <tex>K</tex> непрерывно и положительно определено на компакте, то существует пространство <tex>\mathcal{H}</tex> и отображение <tex>\Phi: \mathcal{X} \to \mathcal{H}</tex>, такие что:
-<tex>K(x, x') = \langle \Phi(x), \Phi(x') \rangle_{\mathcal{H}}</tex>
+:<tex>K(x, x') = \langle \Phi(x), \Phi(x') \rangle_{\mathcal{H}}</tex>
 Для характеризации класса функций, который порождает такое ядро, вводится понятие '''воспроизводящего ядерного гильбертова пространства (RKHS)''' <tex>\mathcal{H}_K</tex>. Это пространство функций <tex>f: \mathcal{X} \to \mathbb{R}</tex>, конструируемое как замыкание линейной оболочки элементов вида <tex>\{K(x, \cdot) \mid x \in \mathcal{X}\}</tex>. Оно уникально для каждого ядра и обладает '''воспроизводящим свойством''':
 # Функция <tex>K(x, \cdot)</tex> сама является элементом пространства <tex>\mathcal{H}_K</tex> для любого <tex>x</tex>.
 # Скалярное произведение любой функции <tex>f \in \mathcal{H}_K</tex> с «сечением» ядра вычисляет значение этой функции в точке <tex>x</tex>:
-<tex>\langle f, K(x, \cdot) \rangle_{\mathcal{H}_K} = f(x)</tex>
+:<tex>\langle f, K(x, \cdot) \rangle_{\mathcal{H}_K} = f(x)</tex>
 Из этого свойства напрямую следует, что скалярное произведение самих ядерных функций возвращает значение ядра: <tex>\langle K(x, \cdot), K(x', \cdot) \rangle_{\mathcal{H}_K} = K(x, x')</tex>. Норма функции в этом пространстве <tex>\|f\|_{\mathcal{H}_K}^2</tex> служит строгой мерой её гладкости: чем сильнее функция осциллирует между точками, тем выше её норма.
@@ Строка 43: / Строка 37: @@
 '''Полиномиальное ядро:'''
-<tex>K(x, x') = (x^T x' + 1)^d, \quad d \in \mathbb{N}</tex>
+:<tex>K(x, x') = (x^T x' + 1)^d, \quad d \in \mathbb{N}</tex>
 При раскрытии скобок по формуле бинома Ньютона ядро распадается на сумму скалярных произведений мономов всех степеней до <tex>d</tex>. Количество таких мономов конечно, следовательно, <tex>\dim(\mathcal{H}_K)</tex> конечно.
 '''Гауссово ядро (RBF):'''
-<tex>K(x, x') = \exp\left(-\frac{1}{2} \|x - x'\|^2\right)</tex>
+:<tex>K(x, x') = \exp\left(-\frac{1}{2} \|x - x'\|^2\right)</tex>
 Покажем, что это ядро порождает бесконечномерное пространство. Для простоты рассмотрим одномерный случай <tex>x, x' \in \mathbb{R}</tex>. Используя свойства экспоненты, перепишем ядро:
-<tex>K(x, x') = e^{-\frac{1}{2}x^2} e^{-\frac{1}{2}(x')^2} e^{xx'}</tex>
+:<tex>K(x, x') = e^{-\frac{1}{2}x^2} e^{-\frac{1}{2}(x')^2} e^{xx'}</tex>
 Разложим сомножитель <tex>e^{xx'}</tex> в бесконечный ряд Тейлора:
-<tex>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)</tex>
+:<tex>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)</tex>
 Полученное выражение эквивалентно стандартному определению скалярного произведения в пространстве последовательностей <tex>\ell_2</tex> для неявного отображения вида:
-<tex>\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</tex>
+:<tex>\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</tex>
 Так как функции <tex>\{e^{-\frac{1}{2}x^2}x^m\}</tex> линейно независимы при разных <tex>m</tex>, базис пространства бесконечен. Соответственно, <tex>\dim(\mathcal{H}_K) = \infty</tex>.
@@ Строка 64: / Строка 58: @@
 '''Формулировка:''' Пусть задана произвольная [[Функция потерь|функция потерь]] <tex>\mathcal{L}(f(x_1), \dots, f(x_n), y_1, \dots, y_n)</tex> и строго возрастающая функция штрафа за сложность (регуляризатор) <tex>\Omega(\|f\|_{\mathcal{H}_K})</tex>. Тогда любая функция <tex>f^*</tex>, минимизирующая полный регуляризованный риск:
-<tex>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)</tex>
+:<tex>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)</tex>
 строго представима в виде конечной линейной комбинации ядер, центрированных на элементах обучающей выборки:
-<tex>f^*(x) = \sum_{i=1}^n \alpha_i K(x, x_i), \quad \alpha_i \in \mathbb{R}</tex>
+:<tex>f^*(x) = \sum_{i=1}^n \alpha_i K(x, x_i), \quad \alpha_i \in \mathbb{R}</tex>
 '''Доказательство:''' Выделим конечномерное подпространство <tex>\mathcal{V} = \text{span}\left(\{K(x_i, \cdot)\}_{i=1}^n\right)</tex>. По теореме о проекции в гильбертовых пространствах, любую функцию <tex>f \in \mathcal{H}_K</tex> можно разложить на параллельную и ортогональную составляющие: <tex>f = f_{\mathcal{V}} + v</tex>, где <tex>f_{\mathcal{V}} \in \mathcal{V}</tex>, а <tex>v \in \mathcal{V}^{\perp}</tex> (то есть <tex>\langle v, K(x_i, \cdot) \rangle_{\mathcal{H}_K} = 0</tex> для всех <tex>i=1,\dots,n</tex>).
 Вычислим значение функции <tex>f</tex> в точке обучения <tex>x_j</tex>, используя воспроизводящее свойство и линейность скалярного произведения:
-<tex>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(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</tex>
 Поскольку значение функции во всех точках выборки определяется только компонентой <tex>f_{\mathcal{V}}</tex>, слагаемое эмпирического риска <tex>\mathcal{L}</tex> инвариантно к ортогональному сдвигу <tex>v</tex>.
 Теперь оценим норму функции <tex>f</tex> по теореме Пифагора для ортогональных векторов:
-<tex>\|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</tex>
+:<tex>\|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</tex>
-Так как функция <tex>\Omega</tex> строго возрастает, добавление любой компоненты <tex>v \neq 0</tex> строго увеличивает штрафную часть функционала, не изменяя при этом значение эмпирических потерь. Следовательно, точка минимума <tex>f^*</tex> обязана иметь ортогональную компоненту <tex>\|v\| = 0 \implies v = 0</text>. Значит, <tex>f^* \in \mathcal{V}</tex>, то есть является линейной комбинацией <tex>\sum_{i=1}^n \alpha_i K(x_i, \cdot)</tex>. Теорема доказана.
+Так как функция <tex>\Omega</tex> строго возрастает, добавление любой компоненты <tex>v \neq 0</tex> строго увеличивает штрафную часть функционала, не изменяя при этом значение эмпирических потерь. Следовательно, точка минимума <tex>f^*</tex> обязана иметь ортогональную компоненту <tex>\|v\| = 0 \implies v = 0</tex>. Значит, <tex>f^* \in \mathcal{V}</tex>, то есть является линейной комбинацией <tex>\sum_{i=1}^n \alpha_i K(x_i, \cdot)</tex>. Теорема доказана.
 == Ядерная гребневая регрессия (Kernel Ridge Regression) ==
 Продемонстрируем, как сквозной математический аппарат решает конкретную задачу непараметрической регрессии с квадратичным функционалом потерь и [[Регуляризация Тихонова|тихоновским регуляризатором]]:
-<tex>\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</tex>
+:<tex>\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</tex>
-По доказанной теореме о представлении, оптимум гарантированно ищется в виде <tex>f(x) = \sum_{i=1}^n \alpha_i K(x, x_i)</tex>. Подставим это выражение в функционал оптимизации, переходя к матричной форме. Вектор предсказаний модели на обучающей выборке равен <tex>\mathbf{K}\alpha</tex>, где <tex>\mathbf{K}</text> — матрица Грама, а <tex>\alpha = [\alpha_1, \dots, \alpha_n]^T</text>. Квадрат нормы функции раскрывается через скалярное произведение в RKHS:
+По доказанной теореме о представлении, оптимум гарантированно ищется в виде <tex>f(x) = \sum_{i=1}^n \alpha_i K(x, x_i)</tex>. Подставим это выражение в функционал оптимизации, переходя к матричной форме. Вектор предсказаний модели на обучающей выборке равен <tex>\mathbf{K}\alpha</tex>, где <tex>\mathbf{K}</tex> — матрица Грама, а <tex>\alpha = [\alpha_1, \dots, \alpha_n]^T</tex>. Квадрат нормы функции раскрывается через скалярное произведение в 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>\|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</tex>
 Задача минимизации полностью сводится к конечномерной квадратичной форме относительно вектора весов <tex>\alpha \in \mathbb{R}^n</tex>:
-<tex>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</tex>
+:<tex>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</tex>
-<tex>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>Q(\alpha) = \alpha^T \mathbf{K}^2 \alpha - 2 \alpha^T \mathbf{K} y + y^T y + \lambda \alpha^T \mathbf{K} \alpha</tex>
 Для нахождения глобального экстремума вычислим [[Градиент|градиент]] по вектору <tex>\alpha</tex> и приравняем его к нулю:
-<tex>\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>
+:<tex>\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}</tex>
-Поскольку матрица Грама <tex>\mathbf{K}</text> полуположительно определена, а параметр регуляризации <tex>\lambda > 0</text>, матрица в скобках <tex>(\mathbf{K} + \lambda \mathbf{I})</text> строго положительно определена и гарантированно обратима. Следовательно, уравнение имеет единственное аналитическое решение:
+Поскольку матрица Грама <tex>\mathbf{K}</tex> полуположительно определена, а параметр регуляризации <tex>\lambda > 0</tex>, матрица в скобках <tex>(\mathbf{K} + \lambda \mathbf{I})</tex> строго положительно определена и гарантированно обратима. Следовательно, уравнение имеет единственное аналитическое решение:
-<tex>\alpha^* = (\mathbf{K} + \lambda \mathbf{I})^{-1} y</text>
+:<tex>\alpha^* = (\mathbf{K} + \lambda \mathbf{I})^{-1} y</tex>
-Для предсказания значения в новой произвольной точке <tex>x</text> используется вектор значений ядра между новым объектом и обучающей выборкой <tex>\mathbf{k}(x) = [K(x, x_1), \dots, K(x, x_n)]^T</text>:
+Для предсказания значения в новой произвольной точке <tex>x</tex> используется вектор значений ядра между новым объектом и обучающей выборкой <tex>\mathbf{k}(x) = [K(x, x_1), \dots, K(x, x_n)]^T</tex>:
-<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>
+:<tex>f^*(x) = \sum_{i=1}^n \alpha_i^* K(x, x_i) = \mathbf{k}(x)^T (\mathbf{K} + \lambda \mathbf{I})^{-1} y</tex>
 == Резюме: класс решаемых задач и смысл решения ==
@@ Строка 106: / Строка 100: @@
 Это задачи '''непараметрического восстановления функций''' (регрессии, интерполяции и аппроксимации) по конечной зашумленной выборке в условиях, когда:
 * Истинная зависимость существенно нелинейна, а её аналитический вид априори неизвестен.
-* Объекты выборки <tex>x</text> имеют сложную нелинейную структуру или являются нечисловыми (последовательности, графы), но для них можно задать симметричную функцию близости, удовлетворяющую критерию положительной определенности Мерсера.
+* Объекты выборки <tex>x</tex> имеют сложную нелинейную структуру или являются нечисловыми (последовательности, графы), но для них можно задать симметричную функцию близости, удовлетворяющую критерию положительной определенности Мерсера.
 '''Что значит «решить задачу» в данном случае:'''
-Решить задачу ядерным методом означает найти глобально оптимальную функцию <tex>f^*(x)</text> в [[Гильбертово пространство|гильбертовом пространстве]] гипотез, что физически выражается в следующем:
+Решить задачу ядерным методом означает найти глобально оптимальную функцию <tex>f^*(x)</tex> в [[Гильбертово пространство|гильбертовом пространстве]] гипотез, что физически выражается в следующем:
-# '''Геометрически:''' Найти такую разделяющую или аппроксимирующую гиперплоскость в бесконечномерном пространстве <tex>\mathcal{H}_K</text>, которая в исходном пространстве <tex>\mathcal{X}</text> разворачивается в сложную нелинейную поверхность, идеально проходящую через точки данных с учетом заданного уровня шума.
+# '''Геометрически:''' Найти такую разделяющую или аппроксимирующую гиперплоскость в бесконечномерном пространстве <tex>\mathcal{H}_K</tex>, которая в исходном пространстве <tex>\mathcal{X}</tex> разворачивается в сложную нелинейную поверхность, идеально проходящую через точки данных с учетом заданного уровня шума.
-# '''Алгебраически:''' Свести бесконечномерную вариационную задачу к конечномерной системе линейных уравнений размерности <tex>n \times n</text> (где <tex>n</text> — размер выборки). Решением является единственный вектор коэффициентов <tex>\alpha^*</text>, который определяет вклад каждого обучающего объекта в предсказание для новой точки.
+# '''Алгебраически:''' Свести бесконечномерную вариационную задачу к конечномерной системе линейных уравнений размерности <tex>n \times n</tex> (где <tex>n</tex> — размер выборки). Решением является единственный вектор коэффициентов <tex>\alpha^*</tex>, который определяет вклад каждого обучающего объекта в предсказание для новой точки.
-# '''Статистически:''' Найти компромисс между точностью приближения выборки ([[Эмпирический риск|эмпирическим риском]]) и гладкостью итоговой функции. Штраф за норму в RKHS <tex>\|f\|_{\mathcal{H}_K}^2</text> гарантирует, что решение не будет хаотично осциллировать между точками обучения, подавляя [[Переобучение|переобучение]].
+# '''Статистически:''' Найти компромисс между точностью приближения выборки ([[Эмпирический риск|эмпирическим риском]]) и гладкостью итоговой функции. Штраф за норму в RKHS <tex>\|f\|_{\mathcal{H}_K}^2</tex> гарантирует, что решение не будет хаотично осциллировать между точками обучения, подавляя [[Переобучение|переобучение]].
 == См. также ==