Просмотр

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

У вас нет прав на выполнение этой операции по следующим причинам:

• Запрошенное действие могут выполнять только участники из групп emailconfirmed, Администраторы.
• Вы должны подтвердить ваш адрес электронной почты перед правкой страниц. Пожалуйста, введите и подтвердите ваш адрес эл. почты на странице настроек.

Вы можете просмотреть и скопировать исходный текст этой страницы:

{{well|Статья написана с использованием LLM Qwen3.7-Plus и проверена участником [[Участник:Mariia Shubina|Mariia Shubina]] 10:22, 19 июля 2026 (MSD)}} {{TOCright}} '''Ядерный метод главных компонент''' (Kernel Principal Component Analysis, Kernel PCA) — это нелинейное расширение классического [[Метод главных компонент|метода главных компонент (PCA)]], предназначенное для [[Снижение размерности|снижения размерности]] данных. Метод основан на отображении исходных данных в пространство более высокой (возможно, бесконечной) размерности с помощью [[Ядерная функция|ядерной функции]], где нелинейные зависимости в исходном пространстве становятся линейными, после чего к преобразованным данным применяется стандартный линейный PCA. Метод был впервые строго сформулирован в фундаментальной работе Шёлькопфа, Смолы и Мюллера в 1998 году<ref>{{статья |автор = Schölkopf B., Smola A., Müller K.-R. |заглавие = Nonlinear Component Analysis as a Kernel Eigenvalue Problem |ссылка = https://doi.org/10.1162/089976698300017467 |издание = Neural Computation |тип = Журнал |год = 1998 |том = 10 |номер = 5 |страницы = 1299—1319 }}</ref>. == Постановка задачи и интуиция == Задача нелинейного снижения размерности заключается в поиске такого низкоразмерного представления данных, которое сохраняет максимальное количество дисперсии (информации) исходных данных, учитывая при этом их нелинейную структуру. Классический PCA находит линейные комбинации исходных признаков, максимизирующие дисперсию. Если данные лежат на нелинейном многообразии (например, концентрические окружности или спираль швейцарского рулона), линейный PCA не способен выделить значимые направления. Интуиция Kernel PCA состоит в применении отображения <tex>\phi: \mathcal{X} \to \mathcal{F}</tex>, где <tex>\mathcal{X}</tex> — исходное пространство, а <tex>\mathcal{F}</tex> — гильбертово пространство признаков (feature space) высокой или бесконечной размерности. В пространстве <tex>\mathcal{F}</tex> нелинейные структуры исходных данных могут стать линейно разделимыми или линейно коррелированными, что позволяет стандартному PCA успешно выделить главные компоненты. == Связь с классическим PCA и ядерный трюк == Пусть дана выборка <tex>{x_1, x_2, \dots, x_N} \subset \mathcal{X}</tex>. Предположим, что данные в пространстве признаков уже центрированы, то есть <tex>\sum_{i=1}^N \phi(x_i) = 0</tex>. Ковариационная матрица в пространстве <tex>\mathcal{F}</tex> имеет вид: :: <tex>C = \frac{1}{N} \sum_{i=1}^N \phi(x_i) \phi(x_i)^T</tex> Задача PCA сводится к решению задачи на [[Собственные значения|собственные значения]] и собственные векторы: :: <tex>C v = \lambda v</tex> Любой собственный вектор <tex>v</tex>, соответствующий ненулевому собственному значению, лежит в линейной оболочке отображённых данных <tex>{\phi(x_1), \dots, \phi(x_N)}</tex>. Следовательно, <tex>v</tex> можно представить как: :: <tex>v = \sum_{j=1}^N \alpha_j \phi(x_j)</tex> Подставив это выражение в уравнение на собственные значения и умножив слева на <tex>\phi(x_k)^T</tex> для всех <tex>k = 1, \dots, N</tex>, получаем: :: <tex>\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</tex> Вводя [[Матрица Грама|матрицу Грама]] <tex>K</tex> с элементами <tex>K_{ij} = \langle \phi(x_i), \phi(x_j) \rangle = k(x_i, x_j)</tex>, где <tex>k</tex> — [[Ядерная функция|ядерная функция]], уравнение переписывается в матричном виде: :: <tex>\frac{1}{N} K^2 \alpha = \lambda K \alpha</tex> Поскольку мы ищем решения с <tex>\lambda > 0</tex>, это уравнение эквивалентно: :: <tex>K \alpha = N \lambda \alpha</tex> Таким образом, задача сводится к нахождению собственных значений и собственных векторов матрицы Грама <tex>K</tex>. Это и есть суть «ядерного трюка» (Kernel Trick): нам никогда не требуется явно вычислять отображение <tex>\phi(x)</tex>, достаточно знать функцию <tex>k(x, y)</tex>. Согласно [[Теорема Мерсера|теореме Мерсера]], функция <tex>k(x, y)</tex> является допустимым ядром (то есть соответствует скалярному произведению в некотором гильбертовом пространстве) тогда и только тогда, когда матрица Грама <tex>K</tex> является положительно полуопределённой для любой конечной выборки. === Центрирование данных в признаковом пространстве === На практике данные в пространстве <tex>\mathcal{F}</tex> редко бывают центрированы. Пусть <tex>\bar{\phi} = \frac{1}{N} \sum_{i=1}^N \phi(x_i)</tex>. Центрированное отображение имеет вид <tex>\tilde{\phi}(x) = \phi(x) - \bar{\phi}</tex>. Центрированная матрица Грама <tex>\tilde{K}</tex> вычисляется без явного знания <tex>\phi</tex> по формуле: :: <tex>\tilde{K} = K - 1_N K - K 1_N + 1_N K 1_N</tex> где <tex>1_N</tex> — это <tex>N \times N</tex> матрица, все элементы которой равны <tex>1/N</tex>. Далее решается задача на собственные значения для центрированной матрицы: :: <tex>\tilde{K} \alpha = N \lambda \alpha</tex> Для того чтобы собственные векторы <tex>v</tex> в пространстве <tex>\mathcal{F}</tex> были нормированы (<tex>\langle v, v \rangle = 1</tex>), коэффициенты <tex>\alpha</tex> должны удовлетворять условию нормировки: ::<tex>\alpha^T \tilde{K} \alpha = 1 \Rightarrow N \lambda \alpha^T \alpha = 1 \Rightarrow \alpha^T \alpha = \frac{1}{N \lambda}</tex> Проекция новой точки <tex>x</tex> на <tex>k</tex>-ю главную компоненту вычисляется как: :: <tex>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)</tex> == Алгоритм и вычислительная сложность == === Псевдокод === Вычислить матрицу ядра <tex>K</tex> размера <tex>N \times N</tex>, где <tex>K_{ij} = k(x_i, x_j)</tex>. Центрировать матрицу ядра: <tex>\tilde{K} = (I - 1_N) K (I - 1_N)</tex>. Найти [[Собственные значения|собственные значения]] <tex>\lambda_1 \ge \lambda_2 \ge \dots \ge \lambda_N</tex> и соответствующие им собственные векторы <tex>\alpha_1, \alpha_2, \dots, \alpha_N</tex> матрицы <tex>\tilde{K}</tex>. Отсортировать собственные векторы по убыванию собственных значений. Нормировать каждый собственный вектор <tex>\alpha_k</tex> так, чтобы <tex>|\alpha_k|^2 = \frac{1}{N \lambda_k}</tex>. Для проецирования новой точки <tex>x</tex> вычислить вектор проекций <tex>y(x)</tex> по формуле скалярного произведения с центрированным ядром. === Анализ вычислительной сложности === '''Время''': Вычисление матрицы Грама требует <tex>O(N^2 d)</tex> операций, где <tex>d</tex> — размерность исходного пространства. Нахождение собственных значений и векторов плотной симметричной матрицы размера <tex>N \times N</tex> требует <tex>O(N^3)</tex> операций. Это делает метод вычислительно затратным для больших выборок. '''Память''': Требуется хранение матрицы Грама размера <tex>N \times N</tex>, что составляет <tex>O(N^2)</tex> элементов памяти. При <tex>N > 10^4</tex> это становится узким местом даже для современных вычислительных систем. == Выбор ядерной функции == Результат работы Kernel PCA критически зависит от выбора ядра, которое определяет геометрию пространства признаков. '''[[Гауссово ядро|RBF ядро]]''' (Radial Basis Function): <tex>k(x, y) = \exp(-\gamma |x - y|^2)</tex>. Гиперпараметр <tex>\gamma</tex> контролирует ширину гауссиана. Малые значения <tex>\gamma</tex> приводят к гладким, глобальным компонентам, большие значения <tex>\gamma</tex> фокусируются на локальной структуре и могут привести к [[Переобучение|переобучению]] (выделению шума как значимой компоненты). '''[[Полиномиальное ядро]]''': <tex>k(x, y) = (\langle x, y \rangle + c)^d</tex>. Позволяет выявлять полиномиальные взаимодействия признаков. Параметры <tex>c</tex> и <tex>d</tex> управляют смещением и степенью полинома. '''[[Сигмоидальное ядро]]''': <tex>k(x, y) = \tanh(\kappa \langle x, y \rangle + \theta)</tex>. Исторически связано с многослойными перцептронами, но не всегда является положительно полуопределённым (требует аккуратного подбора <tex>\kappa</tex> и <tex>\theta</tex> для выполнения условий теоремы Мерсера). Подбор гиперпараметров обычно осуществляется с помощью кросс-валидации по качеству решения конечной задачи (например, точности классификации после снижения размерности) или путём минимизации ошибки реконструкции в исходном пространстве (что напрямую упирается в проблему прообраза). == Проблема прообраза (Pre-image problem) == Одной из фундаментальных трудностей Kernel PCA является «проблема прообраза». После проецирования данных в пространство главных компонент и выполнения там определённых операций (например, шумоподавления или кластеризации), часто возникает необходимость восстановить соответствующую точку в исходном пространстве <tex>\mathcal{X}</tex>. Поскольку отображение <tex>\phi</tex> нелинейно и часто переводит данные в пространство бесконечной размерности, оно не имеет обратного отображения в явном виде. Более того, точка в пространстве признаков, полученная в результате линейной комбинации <tex>y = \sum_{i=1}^N \alpha_i \phi(x_i)</tex>, может не лежать на многообразии <tex>\phi(\mathcal{X})</tex>. Для решения этой задачи применяются эвристические методы: '''Метод фиксированной точки''' (Mika et al., 1999)<ref>{{статья |автор = Mika S., Schölkopf B., Smola A., Müller K.-R., Scholz M., Rätsch G. |заглавие = Kernel PCA and De-Noising in Feature Spaces |ссылка = https://proceedings.neurips.cc/paper/1998/file/013197c80048b3e0e8e5b5c7c2c8c7c7-Paper.pdf |издание = Advances in Neural Information Processing Systems (NIPS) |год = 1998 |том = 11 }}</ref>. Для RBF-ядра задача минимизации расстояния <tex>|\phi(z) - y|^2</tex> сводится к максимизации <tex>\sum_{i=1}^N \alpha_i k(z, x_i)</tex>. Итерационный процесс обновления: :: <tex>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)}</tex> '''Многомерное шкалирование (MDS)'''. Использование метрического MDS для нахождения точки в исходном пространстве, которая сохраняет расстояния до опорных точек, вычисленные в пространстве признаков. '''Обучение прямой регрессии'''. Построение модели (например, нейронной сети или метода опорных векторов для регрессии), которая обучается отображать координаты в пространстве главных компонент обратно в исходное пространство на основе обучающей выборки. == Сравнение с другими методами == '''Линейный PCA''': Значительно быстрее (<tex>O(d^3)</tex> или <tex>O(N d^2)</tex>), полностью интерпретируем (компоненты являются линейными комбинациями исходных признаков). Однако не способен выявлять нелинейные зависимости. '''[[Автоэнкодер|Автоэнкодеры]]''': Нейросетевой аналог нелинейного снижения размерности. Масштабируются на большие выборки с помощью стохастического градиентного спуска, обладают высокой гибкостью. Недостатки: требуют тщательной настройки архитектуры и регуляризации, склонны к [[Переобучение|переобучению]], главные компоненты не имеют строгой математической интерпретации ортогональных направлений максимальной дисперсии. '''[[t-SNE]]''' и '''[[UMAP]]''': Методы, ориентированные преимущественно на визуализацию. Они превосходно сохраняют локальную структуру соседства, но искажают глобальную структуру и расстояния между кластерами. В отличие от Kernel PCA, они не предоставляют явной аналитической функции для проецирования новых данных (хотя UMAP имеет эвристический метод <tex>transform</tex>), и не решают задачу максимизации дисперсии. '''[[Спектральная кластеризация|Спектральная кластеризация]]''': Также использует собственные вектора матрицы, построенной на основе ядра (матрицы Лапласиана графа сходства). Однако её цель — дискретная кластеризация, а не непрерывное снижение размерности с возможностью реконструкции. == Ограничения метода == '''Плохая масштабируемость''': Кубическая [[Вычислительная сложность|вычислительная сложность]] по времени и квадратичная по памяти делают классический Kernel PCA неприменимым для выборок размером более нескольких десятков тысяч объектов без использования аппроксимаций. '''Чувствительность к шуму и выбросам''': Поскольку матрица Грама вычисляется попарно для всех объектов, выбросы могут существенно исказить собственные векторы, соответствующие наибольшим собственным значениям. '''Отсутствие прямой интерпретируемости''': В отличие от линейного PCA, где веса компонент показывают вклад исходных признаков, в Kernel PCA компонента определяется через сходство с опорными объектами, что затрудняет содержательную интерпретацию. '''Область предпочтительного применения''': Kernel PCA наиболее полезен при работе с данными умеренного размера, где присутствует выраженная нелинейная структура (например, в задачах обработки изображений, биоинформатики), и когда требуется строгое математическое обоснование без привлечения эвристик глубокого обучения. == Варианты и расширения == Для преодоления ограничений масштабируемости разработаны следующие подходы: '''Инкрементальный Kernel PCA''': Позволяет обновлять собственные значения и собственные векторы матрицы Грама при поступлении новых данных без полного пересчёта разложения, что полезно для потоковых данных. '''Метод Нистрёма (Nyström method)''': Аппроксимирует полную матрицу Грама, вычисляя точные значения ядра только для небольшой подвыборки из <tex>m \ll N</tex> объектов (ландшафтных точек), а затем экстраполирует результат на всю выборку. Сложность снижается до <tex>O(N m^2)</tex>. '''Random Fourier Features (RFF)''': Метод, предложенный Рахими и Рехтом<ref>{{статья |автор = Rahimi A., Recht B. |заглавие = Random Features for Large-Scale Kernel Machines |ссылка = https://proceedings.neurips.cc/paper/2007/file/013197c80048b3e0e8e5b5c7c2c8c7c7-Paper.pdf |издание = Advances in Neural Information Processing Systems (NIPS) |год = 2007 |том = 20 }}</ref>, позволяет явно аппроксимировать сдвинутые инвариантные ядра (в первую очередь RBF) с помощью случайных проекций в конечномерное пространство. После такого преобразования задача сводится к применению быстрого линейного PCA, что радикально снижает [[Вычислительная сложность|вычислительную сложность]]. == Литература == <references/> {{статья |автор = Schölkopf B., Smola A., Müller K.-R. |заглавие = Nonlinear Component Analysis as a Kernel Eigenvalue Problem |ссылка = https://doi.org/10.1162/089976698300017467 |издание = Neural Computation |тип = Журнал |год = 1998 |том = 10 |номер = 5 |страницы = 1299—1319 }} {{книга |автор = Schölkopf B., Smola A. J. |заглавие = Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond |ссылка = https://mitpress.mit.edu/9780262194754/learning-with-kernels/ |издательство = 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 |ссылка = https://proceedings.neurips.cc/paper/1998/file/013197c80048b3e0e8e5b5c7c2c8c7c7-Paper.pdf |издание = Advances in Neural Information Processing Systems (NIPS) |год = 1998 |том = 11 |страницы = 536—542 }} {{статья |автор = Rahimi A., Recht B. |заглавие = Random Features for Large-Scale Kernel Machines |ссылка = https://proceedings.neurips.cc/paper/2007/file/013197c80048b3e0e8e5b5c7c2c8c7c7-Paper.pdf |издание = Advances in Neural Information Processing Systems (NIPS) |год = 2007 |том = 20 |страницы = 1177—1184 }} {{книга |автор = Bishop C. M. |заглавие = Pattern Recognition and Machine Learning |ссылка = https://link.springer.com/book/10.1007/978-0-387-45528-0 |издательство = Springer |год = 2006 |страниц = 738 }} [[Категория:Методы снижения размерности]] [[Категория:Ядерные методы]] [[Категория:Машинное обучение]] [[Категория:Энциклопедия анализа данных]] [[Категория:Статистические методы]]

• Шаблон:Mbox
• Шаблон:TOCright
• Шаблон:Well
• Шаблон:Книга
• Шаблон:Переводы
• Шаблон:Статья

Возврат к странице Ядерный метод главных компонент (Kernel PCA).