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

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

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

Nikita Zinoviсh (Обсуждение | вклад)
(Новая: {{well|Статья написана с использованием LLM '''Gemini Flash 3.5''' и проверена участником [[Участник:Nikita Zinovich|Nikita Zinov...)
К следующему изменению →

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

Статья написана с использованием LLM Gemini Flash 3.5 и проверена участником Nikita Zinovich Nikita Zinoviсh 20:23, 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</term> от <tex>x</term> нелинейна, класс линейных функций обладает высоким [[Смещение и дисперсия|смещением (bias)]]. Стандартный статистический подход для расширения класса гипотез — введение нелинейного отображения признаков: <tex>\Phi: \mathcal{X} \to \mathcal{H}$ где $\mathcal{H}</text> — новое [[Гильбертово пространство|гильбертово пространство]] большей размерности <tex>\dim(\mathcal{H}) = D \gg d</text>. Линейная модель в этом пространстве имеет вид <tex>f(x) = \langle w, \Phi(x) \rangle_{\mathcal{H}}</text>, где <tex>w \in \mathcal{H}</text>. Попытка явного вычисления и оптимизации такой модели сталкивается со следующими ограничениями: <ol><li> Вычислительная сложность: если <tex>D</text> велико (например, при полиномиальном расширении высокой степени), вычисление вектора <tex>\Phi(x)</text> требует высоких временных и аппаратных затрат <tex>O(D)</text>. </li><li> Теоретическое ограничение: если <text>D = \infty</text> (пространство бесконечномерно), явное представление вектора <tex>\Phi(x)</text> в памяти и покоординатное вычисление [[Скалярное произведение|скалярного произведения]] <tex>\langle \Phi(x), \Phi(x') \rangle_{\mathcal{H}}</text> физически невозможны. </li></ol> == Математический фундамент: Ядра и пространства RKHS == Вычислительный тупик разрешается, если алгоритм обучения можно переписать так, чтобы объекты <tex>x</text> участвовали в нем исключительно в виде скалярных произведений. Это мотивирует введение функции ядра. '''Определение 1.''' Функция двух переменных <tex>K: \mathcal{X} \times \mathcal{X} \to \mathbb{R}$ называется положительно определенным ядром, если она симметрична ( $K(x, x') = K(x', x)</text>) и для любого конечного набора объектов <tex>\{x_i\}_{i=1}^n</text> матрица Грама <tex>\mathbf{K} \in \mathbb{R}^{n \times n}</text> с элементами <tex>\mathbf{K}_{ij} = K(x_i, x_j)</text> является полуположительно определенной: </li></ol> <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</text> Связь между абстрактным положительно определенным ядром <tex>K</text> и геометрическим пространством <tex>\mathcal{H}</text> устанавливает '''Теорема Мерсера''': если ядро <tex>K</text> непрерывно и положительно определено на компакте, то существует пространство <tex>\mathcal{H}</text> и отображение <tex>\Phi: \mathcal{X} \to \mathcal{H}</text>, такие что: <tex>K(x, x') = \langle \Phi(x), \Phi(x') \rangle_{\mathcal{H}}</text> Для характеризации класса функций, который порождает такое ядро, вводится понятие '''воспроизводящего ядерного гильбертова пространства (RKHS)''' <tex>\mathcal{H}_K</text>. Это пространство функций <tex>f: \mathcal{X} \to \mathbb{R}</text>, конструируемое как замыкание линейной оболочки элементов вида <tex>\{K(x, \cdot) \mid x \in \mathcal{X}\}</text>. Оно уникально для каждого ядра и обладает '''воспроизводящим свойством''': <ol><li> Функция <tex>K(x, \cdot)</text> сама является элементом пространства <tex>\mathcal{H}_K</text> для любого <tex>x</text>. </li><li> Скалярное произведение любой функции <tex>f \in \mathcal{H}_K</text> с «сечением» ядра вычисляет значение этой функции в точке <tex>x</text>: </li></ol> <tex>\langle f, K(x, \cdot) \rangle_{\mathcal{H}_K} = f(x)</text> Из этого свойства напрямую следует, что скалярное произведение самих ядерных функций возвращает значение ядра: <tex>\langle K(x, \cdot), K(x', \cdot) \rangle_{\mathcal{H}_K} = K(x, x')</text>. Норма функции в этом пространстве <tex>\%\|f\|_{\mathcal{H}_K}^2\%</text> служит строгой мерой её гладкости: чем сильнее функция осциллирует между точками, тем выше её норма. == Канонические ядра: анализ размерности признакового пространства == Рассмотрим, как конкретная аналитическая форма ядра определяет размерность пространства <tex>\mathcal{H}_K</text>. '''Полиномиальное ядро:''' <tex>K(x, x') = (x^T x' + 1)^d, \quad d \in \mathbb{N}</text> При раскрытии скобок по формуле бинома Ньютона ядро распадается на сумму скалярных произведений мономов всех степеней до <tex>d</text>. Количество таких мономов конечно, следовательно, <tex>\dim(\mathcal{H}_K)</text> конечно. '''Гауссово ядро (RBF):''' <tex>K(x, x') = \exp\left(-\frac{1}{2} \|x - x'\|^2\right)</text> Покажем, что это ядро порождает бесконечномерное пространство. Для простоты рассмотрим одномерный случай <tex>x, x' \in \mathbb{R}</text>. Используя свойства экспоненты, перепишем ядро: <tex>K(x, x') = e^{-\frac{1}{2}x^2} e^{-\frac{1}{2}(x')^2} e^{xx'}</text> Разложим сомножитель <tex>e^{xx'}</sc> в бесконечный ряд Тейлора (Маклорена): <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)</text> Полученное выражение эквивалентно стандартному определению скалярного произведения в пространстве последовательностей <tex>\ell_2</text> для неявного отображения вида: <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</text> Так как функции <tex>\{e^{-\frac{1}{2}x^2}x^m\}</text> линейно независимы при разных <tex>m</text> (полином не может быть тождественным нулем), базис пространства бесконечен. Соответственно, <tex>\dim(\mathcal{H}_K) = \infty</text>. == Ядерный трюк и Теорема о представлении == '''Ядерный трюк (Kernel Trick)''' — это методология, позволяющая выполнять линейные операции в бесконечномерном пространстве <tex>\mathcal{H}_K</text> без явного вычисления координат <tex>\Phi(x)</text>, заменяя любые скалярные произведения на функцию ядра: <tex>\langle \Phi(x), \Phi(x') \rangle = K(x, x')</text>. Главное теоретическое обоснование применимости ядер к задачам оптимизации дает '''Теорема о представлении (Representer Theorem)'''. Она объясняет, почему бесконечномерная задача минимизации функционала качества не приводит к расходящимся вычислениям. '''Формулировка:''' Пусть задана произвольная функция потерь <tex>\mathcal{L}(f(x_1), \dots, f(x_n), y_1, \dots, y_n)</text> и строго возрастающая функция штрафа за сложность (регуляризатор) <tex>\Omega(\|f\|_{\mathcal{H}_K})</text>. Тогда любая функция <tex>f^*</text>, минимизирующая полный регуляризованный риск: <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)</text> строго представима в виде конечной линейной комбинации ядер, центрированных на элементах обучающей выборки: <tex>f^*(x) = \sum_{i=1}^n \alpha_i K(x, x_i), \quad \alpha_i \in \mathbb{R}</text> '''Доказательство:''' Выделим конечномерное подпространство <tex>\mathcal{V} = \text{span}\left(\{K(x_i, \cdot)\}_{i=1}^n\right)</text>. По теореме о проекции в гильбертовых пространствах, любую функцию <tex>f \in \mathcal{H}_K</text> можно разложить на параллельную и ортогональную составляющие: <tex>f = f_{\mathcal{V}} + v</text>, где <tex>f_{\mathcal{V}} \in \mathcal{V}</text>, а <tex>v \in \mathcal{V}^{\perp}</text> (то есть <tex>\langle v, K(x_i, \cdot) \rangle_{\mathcal{H}_K} = 0</text> для всех <tex>i=1,\dots,n</text>). Вычислим значение функции <tex>f</text> в точке обучения <tex>x_j</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</text> Поскольку значение функции во всех точках выборки определяется только компонентой <tex>f_{\mathcal{V}}</text>, слагаемое эмпирического риска <tex>\mathcal{L}</text> инвариантно к ортогональному сдвигу <tex>v</text>. Теперь оценим норму функции <tex>f</text> по теореме Пифагора для ортогональных векторов: <tex>\mathbf{\|}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</text> Так как функция <tex>\Omega</sc> строго возрастает, добавление любой компоненты <tex>v \neq 0</text> строго увеличивает штрафную часть функционала, не изменяя при этом значение эмпирических потерь. Следовательно, точка минимума <tex>f^*</text> обязана иметь ортогональную компоненту <tex>\|v\| = 0 \implies v = 0</text>. Значит, <tex>f^* \in \mathcal{V}</text>, то есть является линейной комбинацией <tex>\sum_{i=1}^n \alpha_i K(x_i, \cdot)</text>. Теорема доказана. == Ядерная гребневая регрессия (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</text> По доказанной теореме о представлении, оптимум гарантированно ищется в виде <tex>f(x) = \sum_{i=1}^n \alpha_i K(x, x_i)</text>. Подставим это выражение в функционал оптимизации, переходя к матричной форме. Вектор предсказаний модели на обучающей выборке равен <tex>\mathbf{K}\alpha</text>, где <tex>\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</text>: <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</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</text> Для нахождения глобального экстремума вычислим [[Градиент|градиент]] по вектору <tex>\alpha</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}</text> Поскольку матрица Грама <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.$