Ядерный метод главных компонент (Kernel PCA)

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

Статья написана с использованием LLM Qwen3.7-Plus и проверена участником Mariia Shubina 10:22, 19 июля 2026 (MSD)

Содержание

1 Постановка задачи и интуиция
2 Связь с классическим PCA и ядерный трюк
- 2.1 Центрирование данных в признаковом пространстве
3 Алгоритм и вычислительная сложность
- 3.1 Псевдокод
- 3.2 Анализ вычислительной сложности
4 Выбор ядерной функции
5 Проблема прообраза (Pre-image problem)
6 Сравнение с другими методами
7 Ограничения метода
8 Варианты и расширения
9 Литература

Ядерный метод главных компонент (Kernel Principal Component Analysis, Kernel PCA) — это нелинейное расширение классического метода главных компонент (PCA), предназначенное для снижения размерности данных. Метод основан на отображении исходных данных в пространство более высокой (возможно, бесконечной) размерности с помощью ядерной функции, где нелинейные зависимости в исходном пространстве становятся линейными, после чего к преобразованным данным применяется стандартный линейный PCA. Метод был впервые строго сформулирован в фундаментальной работе Шёлькопфа, Смолы и Мюллера в 1998 году^[1].

Постановка задачи и интуиция

Задача нелинейного снижения размерности заключается в поиске такого низкоразмерного представления данных, которое сохраняет максимальное количество дисперсии (информации) исходных данных, учитывая при этом их нелинейную структуру. Классический PCA находит линейные комбинации исходных признаков, максимизирующие дисперсию. Если данные лежат на нелинейном многообразии (например, концентрические окружности или спираль швейцарского рулона), линейный PCA не способен выделить значимые направления. Интуиция Kernel PCA состоит в применении отображения $\phi: \mathcal{X} \to \mathcal{F}$ , где $\mathcal{X}$ — исходное пространство, а $\mathcal{F}$ — гильбертово пространство признаков (feature space) высокой или бесконечной размерности. В пространстве $\mathcal{F}$ нелинейные структуры исходных данных могут стать линейно разделимыми или линейно коррелированными, что позволяет стандартному PCA успешно выделить главные компоненты.

Связь с классическим PCA и ядерный трюк

Пусть дана выборка ${x_1, x_2, \dots, x_N} \subset \mathcal{X}$ . Предположим, что данные в пространстве признаков уже центрированы, то есть $\sum_{i=1}^N \phi(x_i) = 0$ . Ковариационная матрица в пространстве $\mathcal{F}$ имеет вид:

$C = \frac{1}{N} \sum_{i=1}^N \phi(x_i) \phi(x_i)^T$

Задача PCA сводится к решению задачи на собственные значения и собственные векторы:

$C v = \lambda v$

Любой собственный вектор $v$ , соответствующий ненулевому собственному значению, лежит в линейной оболочке отображённых данных ${\phi(x_1), \dots, \phi(x_N)}$ . Следовательно, $v$ можно представить как:

$v = \sum_{j=1}^N \alpha_j \phi(x_j)$

Подставив это выражение в уравнение на собственные значения и умножив слева на $\phi(x_k)^T$ для всех $k = 1, \dots, N$ , получаем:

$\frac{1}{N} \sum_{i=1}^N \langle \phi(x_k), \phi(x_i) \rangle \sum_{j=1}^N \alpha_j \langle \phi(x_i), \phi(x_j) \rangle = \lambda \sum_{j=1}^N \alpha_j \langle \phi(x_k), \phi(x_j) \rangle$

Вводя матрицу Грама $K$ с элементами $K_{ij} = \langle \phi(x_i), \phi(x_j) \rangle = k(x_i, x_j)$ , где $k$ — ядерная функция, уравнение переписывается в матричном виде:

$\frac{1}{N} K^2 \alpha = \lambda K \alpha$

Поскольку мы ищем решения с $\lambda > 0$ , это уравнение эквивалентно:

$K \alpha = N \lambda \alpha$

Таким образом, задача сводится к нахождению собственных значений и собственных векторов матрицы Грама $K$ . Это и есть суть «ядерного трюка» (Kernel Trick): нам никогда не требуется явно вычислять отображение $\phi(x)$ , достаточно знать функцию $k(x, y)$ . Согласно теореме Мерсера, функция $k(x, y)$ является допустимым ядром (то есть соответствует скалярному произведению в некотором гильбертовом пространстве) тогда и только тогда, когда матрица Грама $K$ является положительно полуопределённой для любой конечной выборки.

Центрирование данных в признаковом пространстве

На практике данные в пространстве $\mathcal{F}$ редко бывают центрированы. Пусть $\bar{\phi} = \frac{1}{N} \sum_{i=1}^N \phi(x_i)$ . Центрированное отображение имеет вид $\tilde{\phi}(x) = \phi(x) - \bar{\phi}$ . Центрированная матрица Грама $\tilde{K}$ вычисляется без явного знания $\phi$ по формуле:

$\tilde{K} = K - 1_N K - K 1_N + 1_N K 1_N$

где $1_N$ — это $N \times N$ матрица, все элементы которой равны $1/N$ . Далее решается задача на собственные значения для центрированной матрицы:

$\tilde{K} \alpha = N \lambda \alpha$

Для того чтобы собственные векторы $v$ в пространстве $\mathcal{F}$ были нормированы ( $\langle v, v \rangle = 1$ ), коэффициенты $\alpha$ должны удовлетворять условию нормировки:

$\alpha^T \tilde{K} \alpha = 1 \Rightarrow N \lambda \alpha^T \alpha = 1 \Rightarrow \alpha^T \alpha = \frac{1}{N \lambda}$

Проекция новой точки $x$ на $k$ -ю главную компоненту вычисляется как:

$y_k(x) = \langle v_k, \tilde{\phi}(x) \rangle = \sum_{i=1}^N \alpha_{k,i} \left( k(x, x_i) - \frac{1}{N} \sum_{j=1}^N k(x, x_j) - \frac{1}{N} \sum_{j=1}^N k(x_i, x_j) + \frac{1}{N^2} \sum_{m,j=1}^N k(x_m, x_j) \right)$

Алгоритм и вычислительная сложность

Псевдокод

Вычислить матрицу ядра $K$ размера $N \times N$ , где $K_{ij} = k(x_i, x_j)$ . Центрировать матрицу ядра: $\tilde{K} = (I - 1_N) K (I - 1_N)$ . Найти собственные значения $\lambda_1 \ge \lambda_2 \ge \dots \ge \lambda_N$ и соответствующие им собственные векторы $\alpha_1, \alpha_2, \dots, \alpha_N$ матрицы $\tilde{K}$ . Отсортировать собственные векторы по убыванию собственных значений. Нормировать каждый собственный вектор $\alpha_k$ так, чтобы $|\alpha_k|^2 = \frac{1}{N \lambda_k}$ . Для проецирования новой точки $x$ вычислить вектор проекций $y(x)$ по формуле скалярного произведения с центрированным ядром.

Анализ вычислительной сложности

Время: Вычисление матрицы Грама требует $O(N^2 d)$ операций, где $d$ — размерность исходного пространства. Нахождение собственных значений и векторов плотной симметричной матрицы размера $N \times N$ требует $O(N^3)$ операций. Это делает метод вычислительно затратным для больших выборок. Память: Требуется хранение матрицы Грама размера $N \times N$ , что составляет $O(N^2)$ элементов памяти. При $N > 10^4$ это становится узким местом даже для современных вычислительных систем.

Выбор ядерной функции

Результат работы Kernel PCA критически зависит от выбора ядра, которое определяет геометрию пространства признаков. RBF ядро (Radial Basis Function): $k(x, y) = \exp(-\gamma |x - y|^2)$ . Гиперпараметр $\gamma$ контролирует ширину гауссиана. Малые значения $\gamma$ приводят к гладким, глобальным компонентам, большие значения $\gamma$ фокусируются на локальной структуре и могут привести к переобучению (выделению шума как значимой компоненты). Полиномиальное ядро: $k(x, y) = (\langle x, y \rangle + c)^d$ . Позволяет выявлять полиномиальные взаимодействия признаков. Параметры $c$ и $d$ управляют смещением и степенью полинома. Сигмоидальное ядро: $k(x, y) = \tanh(\kappa \langle x, y \rangle + \theta)$ . Исторически связано с многослойными перцептронами, но не всегда является положительно полуопределённым (требует аккуратного подбора $\kappa$ и $\theta$ для выполнения условий теоремы Мерсера). Подбор гиперпараметров обычно осуществляется с помощью кросс-валидации по качеству решения конечной задачи (например, точности классификации после снижения размерности) или путём минимизации ошибки реконструкции в исходном пространстве (что напрямую упирается в проблему прообраза).

Проблема прообраза (Pre-image problem)

Одной из фундаментальных трудностей Kernel PCA является «проблема прообраза». После проецирования данных в пространство главных компонент и выполнения там определённых операций (например, шумоподавления или кластеризации), часто возникает необходимость восстановить соответствующую точку в исходном пространстве $\mathcal{X}$ . Поскольку отображение $\phi$ нелинейно и часто переводит данные в пространство бесконечной размерности, оно не имеет обратного отображения в явном виде. Более того, точка в пространстве признаков, полученная в результате линейной комбинации $y = \sum_{i=1}^N \alpha_i \phi(x_i)$ , может не лежать на многообразии $\phi(\mathcal{X})$ . Для решения этой задачи применяются эвристические методы: Метод фиксированной точки (Mika et al., 1999)^[1]. Для RBF-ядра задача минимизации расстояния $|\phi(z) - y|^2$ сводится к максимизации $\sum_{i=1}^N \alpha_i k(z, x_i)$ . Итерационный процесс обновления:

$z_{t+1} = \frac{\sum_{i=1}^N \alpha_i k(z_t, x_i) x_i}{\sum_{i=1}^N \alpha_i k(z_t, x_i)}$

Многомерное шкалирование (MDS). Использование метрического MDS для нахождения точки в исходном пространстве, которая сохраняет расстояния до опорных точек, вычисленные в пространстве признаков. Обучение прямой регрессии. Построение модели (например, нейронной сети или метода опорных векторов для регрессии), которая обучается отображать координаты в пространстве главных компонент обратно в исходное пространство на основе обучающей выборки.

Сравнение с другими методами

Линейный PCA: Значительно быстрее ( $O(d^3)$ или $O(N d^2)$ ), полностью интерпретируем (компоненты являются линейными комбинациями исходных признаков). Однако не способен выявлять нелинейные зависимости. Автоэнкодеры: Нейросетевой аналог нелинейного снижения размерности. Масштабируются на большие выборки с помощью стохастического градиентного спуска, обладают высокой гибкостью. Недостатки: требуют тщательной настройки архитектуры и регуляризации, склонны к переобучению, главные компоненты не имеют строгой математической интерпретации ортогональных направлений максимальной дисперсии. t-SNE и UMAP: Методы, ориентированные преимущественно на визуализацию. Они превосходно сохраняют локальную структуру соседства, но искажают глобальную структуру и расстояния между кластерами. В отличие от Kernel PCA, они не предоставляют явной аналитической функции для проецирования новых данных (хотя UMAP имеет эвристический метод $transform$ ), и не решают задачу максимизации дисперсии. Спектральная кластеризация: Также использует собственные вектора матрицы, построенной на основе ядра (матрицы Лапласиана графа сходства). Однако её цель — дискретная кластеризация, а не непрерывное снижение размерности с возможностью реконструкции.

Ограничения метода

Плохая масштабируемость: Кубическая вычислительная сложность по времени и квадратичная по памяти делают классический Kernel PCA неприменимым для выборок размером более нескольких десятков тысяч объектов без использования аппроксимаций. Чувствительность к шуму и выбросам: Поскольку матрица Грама вычисляется попарно для всех объектов, выбросы могут существенно исказить собственные векторы, соответствующие наибольшим собственным значениям. Отсутствие прямой интерпретируемости: В отличие от линейного PCA, где веса компонент показывают вклад исходных признаков, в Kernel PCA компонента определяется через сходство с опорными объектами, что затрудняет содержательную интерпретацию. Область предпочтительного применения: Kernel PCA наиболее полезен при работе с данными умеренного размера, где присутствует выраженная нелинейная структура (например, в задачах обработки изображений, биоинформатики), и когда требуется строгое математическое обоснование без привлечения эвристик глубокого обучения.

Варианты и расширения

Для преодоления ограничений масштабируемости разработаны следующие подходы: Инкрементальный Kernel PCA: Позволяет обновлять собственные значения и собственные векторы матрицы Грама при поступлении новых данных без полного пересчёта разложения, что полезно для потоковых данных. Метод Нистрёма (Nyström method): Аппроксимирует полную матрицу Грама, вычисляя точные значения ядра только для небольшой подвыборки из $m \ll N$ объектов (ландшафтных точек), а затем экстраполирует результат на всю выборку. Сложность снижается до $O(N m^2)$ . Random Fourier Features (RFF): Метод, предложенный Рахими и Рехтом^[1], позволяет явно аппроксимировать сдвинутые инвариантные ядра (в первую очередь RBF) с помощью случайных проекций в конечномерное пространство. После такого преобразования задача сводится к применению быстрого линейного PCA, что радикально снижает вычислительную сложность.

Литература

Schölkopf B., Smola A., Müller K.-R. Nonlinear Component Analysis as a Kernel Eigenvalue Problem // Neural Computation: Журнал. — 1998. — Т. 10. — № 5. — С. 1299—1319. Schölkopf B., Smola A. J. Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond. — MIT Press, 2002. — 644 с. Mika S., Schölkopf B., Smola A., Müller K.-R., Scholz M., Rätsch G. Kernel PCA and De-Noising in Feature Spaces // Advances in Neural Information Processing Systems (NIPS). — 1998. — Т. 11. — С. 536—542. Rahimi A., Recht B. Random Features for Large-Scale Kernel Machines // Advances in Neural Information Processing Systems (NIPS). — 2007. — Т. 20. — С. 1177—1184. Bishop C. M. Pattern Recognition and Machine Learning. — Springer, 2006. — 738 с.

Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%AF%D0%B4%D0%B5%D1%80%D0%BD%D1%8B%D0%B9_%D0%BC%D0%B5%D1%82%D0%BE%D0%B4_%D0%B3%D0%BB%D0%B0%D0%B2%D0%BD%D1%8B%D1%85_%D0%BA%D0%BE%D0%BC%D0%BF%D0%BE%D0%BD%D0%B5%D0%BD%D1%82_%28Kernel_PCA%29»

Категории: Методы снижения размерности | Ядерные методы | Машинное обучение | Энциклопедия анализа данных | Статистические методы