Метод главных компонент

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

Версия от 13:43, 25 июля 2026; Georgii Kvaratsкheliia (Обсуждение | вклад)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Метод Главных Компонент (англ. Principal Components Analysis, PCA) — один из основных способов уменьшить размерность данных, потеряв наименьшее количество информации. Изобретен К. Пирсоном (англ.Karl Pearson) в 1901 г. Применяется во многих областях, таких как распознавание образов, компьютерное зрение, сжатие данных и т. п. Вычисление главных компонент сводится к вычислению собственных векторов и собственных значений ковариационной матрицы исходных данных или к сингулярному разложению матрицы данных. Иногда метод главных компонент называют преобразованием Кархунена-Лоэва (англ. Karhunen-Loeve)[1] или преобразованием Хотеллинга (англ. Hotelling transform). Другие способы уменьшения размерности данных — это метод независимых компонент, многомерное шкалирование, а также многочисленные нелинейные обобщения: метод главных кривых и многообразий, поиск наилучшей проекции (англ. Projection Pursuit), нейросетевые методы «узкого горла», самоорганизующиеся карты Кохонена и др.

Содержание

Формальная постановка задачи

Задача анализа главных компонент, имеет, как минимум, четыре базовых версии:

  • аппроксимировать данные линейными многообразиями меньшей размерности;
  • найти подпространства меньшей размерности, в ортогональной проекции на которые разброс данных (т.е. среднеквадратичное уклонение от среднего значения) максимален;
  • найти подпространства меньшей размерности, в ортогональной проекции на которые среднеквадратичное расстояние между точками максимально;
  • для данной многомерной случайной величины построить такое ортогональное преобразование координат, что в результате корреляции между отдельными координатами обратятся в ноль.

Первые три версии оперируют конечными множествами данных. Они эквивалентны и не используют никакой гипотезы о статистическом порождении данных. Четвёртая версия оперирует случайными величинами. Конечные множества появляются здесь как выборки из данного распределения, а решение трёх первых задач — как приближение к «истинному» преобразованию Кархунена-Лоэва. При этом возникает дополнительный и не вполне тривиальный вопрос о точности этого приближения.

Аппроксимация данных линейными многообразиями

Иллюстрация к знаменитой работе К. Пирсона (1901): даны точки на плоскости, — расстояние от до прямой . Ищется прямая , минимизирующая сумму
Иллюстрация к знаменитой работе К. Пирсона (1901): даны точки P_i на плоскости, p_i — расстояние от P_i до прямой AB. Ищется прямая AB, минимизирующая сумму \sum_i p_i^2

Метод главных компонент начинался с задачи наилучшей аппроксимации конечного множества точек прямыми и плоскостями (К. Пирсон, 1901). Дано конечное множество векторов x_1,x_2,...x_m \in\mathbb{R}^n . Для каждого k = 0,1,..., n-1 среди всех k-мерных линейных многообразий в \mathbb{R}^n найти такое L_k \subset \mathbb{R}^n , что сумма квадратов уклонений x_i от L_k минимальна:

\sum_{i=1}^m \operatorname{dist}^2(x_i, L_k) \to \min,

где \operatorname{dist}(x_i, L_k) — евклидово расстояние от точки до линейного многообразия. Всякое k -мерное линейное многообразие в \mathbb{R}^n может быть задано как множество линейных комбинаций L_k = \{ a_0 +\beta_1 a_1 +...+ \beta_k a_k | \beta_i \in \mathbb{R} \} , где параметры \beta_i пробегают вещественную прямую \mathbb{R}, a_0 \in \mathbb{R}^n а \left\{a_1,..., a_k \right\} \subset \mathbb{R}^n — ортонормированный набор векторов

\operatorname{dist}^2(x_i, L_k) = \| x_i - a_0 - \sum_{j=1}^k a_j (a_j, x_i - a_0) \| ^2,

где \|^\ \cdot \ \|^\ евклидова норма, \left(a_j, x_i\right) — евклидово скалярное произведение, или в координатной форме:

\operatorname{dist}^2(x_i, L_k) = \sum_{l=1}^n \left(x_{il} - a_{0l}- \sum_{j=1}^k a_{jl} \sum_{q=1}^n a_{jq}(x_{iq} - a_{0q}) \right)^2 .

Решение задачи аппроксимации для k = 0,1,..., n-1 даётся набором вложенных линейных многообразий L_0 \subset L_1 \subset ... L_{n-1} , L_k = \{ a_0 +\beta_1 a_1 +...+ \beta_k a_k | \beta_i \in \mathbb{R} \} . Эти линейные многообразия определяются ортонормированным набором векторов \left\{a_1,..., a_{n-1} \right\} (векторами главных компонент) и вектором a_0 . Вектор a_0 ищется, как решение задачи минимизации для L_0 :

a_0 = \underset{a_0\in\mathbb{R}^n}{\operatorname{argmin}} \left(\sum_{i=1}^m \operatorname{dist}^2(x_i, L_0)\right),

то есть

a_0 = \underset{a_0\in\mathbb{R}^n}{\operatorname{argmin}} \left (\sum_{i=1}^m \| x_i - a_0\| ^2\right) .

Это — выборочное среднее: a_0 = \frac{1}{m} \sum_{i=1}^m x_i = \overline{X}. Фреше в 1948 году обратил внимание, что вариационное определение среднего (как точки, минимизирующей сумму квадратов расстояний до точек данных) очень удобно для построения статистики в произвольном метрическом пространстве, и построил обобщение классической статистики для общих пространств (обобщённый метод наименьших квадратов).

Векторы главных компонент могут быть найдены как решения однотипных задач оптимизации:

1) централизуем данные (вычитаем среднее): x_i:= x_i - \overline{X_i}. Теперь \sum_{i=1}^m x_i =0 ;
2) находим первую главную компоненту как решение задачи;
a_1 = \underset{\| a_1 \| =1}{\operatorname{argmin}} \left( \sum_{i=1}^m \| x_i - a_1 (a_1,x_i)\| ^2\right).
Если решение не единственно, то выбираем одно из них.
3) Вычитаем из данных проекцию на первую главную компоненту:
x_i:= x_i - a_1 \left(a_1,x_i\right) ;
4) находим вторую главную компоненту как решение задачи
a_2 = \underset{\| a_2 \| =1}{\operatorname{argmin}} \left( \sum_{i=1}^m \| x_i - a_2 (a_2,x_i)\| ^2\right) .
Если решение не единственно, то выбираем одно из них.
…
2k-1) Вычитаем проекцию на (k-1)-ю главную компоненту (напомним, что проекции на предшествующие (k-2) главные компоненты уже вычтены):
x_i:= x_i - a_{k-1} \left(a_{k-1},x_i\right) ;
2k) находим k-ю главную компоненту как решение задачи:
a_k = \underset{\| a_k \| =1}{\operatorname{argmin}} \left( \sum_{i=1}^m \| x_i - a_k (a_k,x_i)\| ^2\right) .
Если решение не единственно, то выбираем одно из них.
…

На каждом подготовительном шаге (2k-1) вычитаем проекцию на предшествующую главную компоненту. Найденные векторы \left\{a_1,..., a_{ n -1} \right\} ортонормированы просто в результате решения описанной задачи оптимизации, однако чтобы не дать ошибкам вычисления нарушить взаимную ортогональность векторов главных компонент, можно включать a_k \bot \{a_1,..., a_{k -1} \} в условия задачи оптимизации.

Неединственность в определении a_k помимо тривиального произвола в выборе знака ( a_k и -a_k решают ту же задачу) может быть более существенной и происходить, например, из условий симметрии данных.

Поиск ортогональных проекций с наибольшим рассеянием

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


Пусть нам дан центрированный набор векторов данных x_i\in\mathbb{R}^n \; (i=1,...,m) (среднее арифметическое значение x_i равно нулю). Задача — найти такое ортогональное преобразование в новую систему координат, для которого были бы верны следующие условия:

  • Выборочная дисперсия данных вдоль первой координаты максимальна (эту координату называют первой главной компонентой);
  • Выборочная дисперсия данных вдоль второй координаты максимальна при условии ортогональности первой координате (вторая главная компонента);
  • …
  • Выборочная дисперсия данных вдоль значений k-ой координаты максимальна при условии ортогональности первым k-1 координатам;
  • …

Выборочная дисперсия данных вдоль направления, заданного нормированным вектором a_k, это

S^2_m \left[ (X, a_k) \right ] = \frac{1}{m} \sum\limits_{i=1}^m \left(\sum\limits_{j=1}^n x_{ij}a_{kj} \right)^2

(поскольку данные центрированы, выборочная дисперсия здесь совпадает со средним квадратом уклонения от нуля).

Формально, если A=\left \{a_1,...,a_n \right \}^T\in\mathbb{R}^{n \times n}, a_k\in\mathbb{R}^n — искомое преобразование, то для векторов a_k должны выполняться следующие условия:

  • a_1 = \underset{\| a_1 \| =1}{\operatorname{argmax}}\,S^2_m \left [(X, a_1) \right ];
Если решение не единственно, то выбираем одно из них.
  • Вычитаем из данных проекцию на первую главную компоненту:
x_i:= x_i-a_1 \left(a_1,x_i\right) ; в результате x_i \bot a_1;
  • находим вторую главную компоненту как решение задачи
a_2 = \underset{\| a_2 \| =1}{\operatorname{argmax}}\,S^2_m \left [ (X, a_2) \right ];
Если решение не единственно, то выбираем одно из них.
  • …
  • Вычитаем проекцию на (k-1)-ю главную компоненту (напомним, что проекции на предшествующие k-2 главные компоненты уже вычтены):
x_i:= x_i-a_{k-1} \left(a_{k-1},x_i\right) ; в результате x_i \bot a_l, (l = 1,\dots k-1);
  • находим k-ю главную компоненту как решение задачи
a_n = \underset{\| a_k\| = 1}{\operatorname{argmax}}\,S^2_m \left [ (X, a_k) \right ];
Если решение не единственно, то выбираем одно из них.
  • ...

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

Решение задачи о наилучшей аппроксимации даёт то же множество решений \left\{a_i\right\}, что и поиск ортогональных проекций с наибольшим рассеянием, по очень простой причине: \| x_i-a_k (a_k, x_i)\|^2 \stackrel{\|a_k\|=1}{=} \| x_i\|^2-(a_k, x_i)^2, и первое слагаемое не зависит от a_k. Только одно дополнение к задаче об аппроксимации: появляется последняя главная компонента a_n.

Поиск ортогональных проекций с наибольшим среднеквадратичным расстоянием между точками

Ещё одна эквивалентная формулировка следует из очевидного тождества, верного для любых m векторов x_i:

\frac{1}{m(m-1)}\sum_{i,j=1}^m (x_i-x_j)^2 =\frac{2m^2}{m(m-1)}\left[\frac{1}{m}\sum_{i=1}^m x_i^2 - \left(\frac{1}{m}\sum_{i}^m x_i \right)^2\right].

В левой части этого тождества стоит среднеквадратичное расстояние между точками, а в квадратных скобках справа — выборочная дисперсия. Таким образом, в методе главных компонент ищутся подпространства, в проекции на которые среднеквадратичное расстояние между точками максимально (или, что то же самое, его искажение в результате проекции минимально)[1]. Такая переформулировка позволяет строить обобщения с взвешиванием различных парных расстояний (а не только точек).

Аннулирование корреляций между координатами

Для заданной n-мерной случайной величины X найти такой ортонормированный базис, \left\{a_1,..., a_n \right\}, в котором коэффициент ковариации между различными координатами равен нулю. После преобразования к этому базису

\operatorname{cov}(X_i,X_j)=0 для i \neq j .

Здесь \operatorname{cov}(X_i,X_j)= \operatorname{E}[(X_i-\overline{X_i})(X_j-\overline{X_j})] — коэффициент ковариации.

Диагонализация ковариационной матрицы

Все задачи о главных компонентах приводят к задаче диагонализации ковариационной матрицы или выборочной ковариационной матрицы. Эмпирическая или выборочная ковариационная матрица, это

C = [c_{ij}],\ c_{ij} = \frac{1}{m-1} \sum_{l=1}^m (x_{li}-\overline{X_{i}})(x_{lj}-\overline{X_{j}}).

Ковариационная матрица многомерной случайной величины X, это

\Sigma = [\sigma_{ij}],\ \sigma_{ij} = \operatorname{cov}(X_i,X_j)=E[(X_i-\overline{X_i})(X_j-\overline{X_j})].

Векторы главных компонент для задач о наилучшей аппроксимации и о поиске ортогональных проекций с наибольшим рассеянием — это ортонормированный набор \left\{a_1,..., a_n \right\} собственных векторов эмпирической ковариационной матрицы C, расположенных в порядке убывания собственных значений \lambda: \lambda_1 \ge \lambda_2 \ge ... \ge \lambda_n \ge 0. Эти векторы служат оценкой для собственных векторов ковариационной матрицы \operatorname{cov}(X_i,X_j) . В базисе из собственных векторов ковариационной матрицы она, естественно, диагональна, и в этом базисе коэффициент ковариации между различными координатами равен нулю.

Если спектр ковариационной матрицы вырожден, то выбирают произвольный ортонормированный базис собственных векторов. Он существует всегда, а собственные числа ковариационной матрицы всегда вещественны и неотрицательны.

Сингулярное разложение матрицы данных

Основная статья: Простой итерационный алгоритм сингулярного разложения

Математическое содержание метода главных компонент — это спектральное разложение ковариационной матрицы C , то есть представление пространства данных в виде суммы взаимно ортогональных собственных подпространств C , а самой матрицы C — в виде линейной комбинации ортогональных проекторов на эти подпространства с коэффициентами \lambda_i . Если \operatorname{X}=\left\{x_1,..., x_m \right\}^T — матрица, составленная из векторов-строк центрированных данных, то C = \frac{1}{m-1}\operatorname{X}^T\operatorname{X} и задача о спектральном разложении ковариационной матрицы C превращается в задачу о сингулярном разложении (англ. Singular value decomposition) матрицы данных \operatorname{X}.

Хотя формально задачи сингулярного разложения матрицы данных и спектрального разложения ковариационной матрицы совпадают, алгоритмы вычисления сингулярного разложения напрямую, без вычисления ковариационной матрицы и её спектра, более эффективны и устойчивы [1].

Теория сингулярного разложения была создана Дж. Дж. Сильвестром (англ. J. J. Sylvester) в 1889 г. и изложена во всех подробных руководствах по теории матриц [1].

Вычисление для больших и потоковых данных

Рандомизированные алгоритмы

Для матриц данных с очень большим числом строк и/или столбцов точное вычисление сингулярного разложения может быть неприемлемо дорогим. Халко, Мартинссон и Тропп[1] показали, что случайная проекция матрицы данных на низкоразмерное подпространство с последующим точным разложением уже существенно меньшей матрицы даёт приближённое сингулярное разложение (а значит, и приближённые главные компоненты) с контролируемой точностью и на порядки меньшей вычислительной стоимостью, чем прямое вычисление. Этот подход стал стандартом практического вычисления метода главных компонент на данных с миллионами наблюдений и признаков.

Онлайн-вычисление: правило Ойя

Если данные поступают последовательно (потоком) и не помещаются в памяти целиком, применяют онлайн-обновление вида

a_{t+1} = a_t + \eta_t\, y_t\,(x_t - y_t a_t), \qquad y_t = a_t^\top x_t,

предложенное Ойя[1] — простое правило хеббовского обучения одного линейного нейрона, сходящееся к первой главной компоненте по мере поступления новых наблюдений x_t без необходимости хранить или повторно обрабатывать уже увиденные данные. Это правило стало одним из первых примеров биологически правдоподобного алгоритма обучения представлений и одной из точек соприкосновения метода главных компонент с теорией искусственных нейронных сетей.

Матрица преобразования к главным компонентам

Матрица A преобразования данных к главным компонентам строится из векторов главных компонент: A=\left \{a_1,...,a_n \right \}^T. Здесь a_i — ортонормированные векторы-столбцы главных компонент, расположенные в порядке убывания собственных значений, верхний индекс T означает транспонирование. Матрица A является ортогональной: A A^T=1.

После преобразования большая часть вариации данных будет сосредоточена в первых координатах, что даёт возможность отбросить оставшиеся и рассмотреть пространство уменьшенной размерности.

Остаточная дисперсия

Пусть данные центрированы, \overline{ X}=0. При замене векторов данных x_i на их проекцию на первые k главных компонент x_i \mapsto \sum_{j=1}^k a_j (a_j, x_i) вносится средний квадрат ошибки в расчете на один вектор данных:

\frac{1}{m} \sum_{i=1}^m \left\| x_i - \sum_{j=1}^k a_j (a_j, x_i) \right \| ^2=\sum_{l=k+1}^n \lambda_l,

где \lambda_1 \ge \lambda_2 \ge ... \ge \lambda_n \ge 0 собственные значения эмпирической ковариационной матрицы C, расположенные в порядке убывания, с учетом кратности.

Эта величина называется остаточной дисперсией. Величина

\frac{1}{m} \sum_{i=1}^m \left\| \sum_{j=1}^k a_j (a_j, x_i) \right\| ^2=\frac{1}{m} \sum_{i=1}^m \sum_{j=1}^k (a_j, x_i)^2=\sum_{l=1}^k \lambda_l

называется объяснённой дисперсией. Их сумма равна выборочной дисперсии. Соответствующий квадрат относительной ошибки — это отношение остаточной дисперсии к выборочной дисперсии (то есть доля необъяснённой дисперсии):

\delta^2_k=\frac{\lambda_{k+1}+\lambda_{k+2}+...+\lambda_{n}}{\lambda_{1}+\lambda_{2}+...+\lambda_{n}}.

По относительной ошибке \delta_k оценивается применимость метода главных компонент с проецированием на первые k компонент.

Замечание: в большинстве вычислительных алгоритмов собственные числа \lambda_i с соответствуюшими собственными векторами — главными компонентами a_i вычисляются в порядке «от больших \lambda_i — к меньшим». Для вычисления \delta_k достаточно вычислить первые k собственных чисел и след эмпирической ковариационной матрицы C, \operatorname{tr} C (сумму диагональных элементов C, то есть дисперсий по осям). Тогда

\delta^2_k=\frac{1}{\operatorname{tr} C}\left(\operatorname{tr} C -\sum_{i=1}^k \lambda_{i}\right).

Оценка числа главных компонент по правилу сломанной трости

Пример: оценка числа главных компонент по правилу сломанной трости в размерности 5.
Пример: оценка числа главных компонент по правилу сломанной трости в размерности 5.

Целевой подход к оценке числа главных компонент по необходимой доле объяснённой дисперсии формально применим всегда, однако неявно он предполагает, что нет разделения на "сигнал" и "шум", и любая заранее заданная точность имеет смысл. Поэтому часто более продуктивна иная эвристика, основывающаяся на гипотезе о наличии "сигнала" (сравнительно малая размерность, относительно большая амплитуда) и "шума" (большая размерность, относительно малая амплитуда). С этой точки зрения метод главных компонент работает как фильтр: сигнал содержится, в основном, в проекции на первые главные компоненты, а в остальных компонентах пропорция шума намного выше.

Вопрос, как оценить число необходимых главных компонент, если отношение "сигнал/шум" заранее неизвестно? Одним из наиболее популярных эвристических подходов является правило сломанной трости (англ. Broken stick model)[1]. Набор нормированных собственных чисел (\lambda_i / \tr C, i=1,...,n) сравнивается с распределением длин обломков трости единичной длины, сломанной в n-1-й случайно выбранной точке (точки разлома выбираются независимо и равнораспределены по длине трости). Пусть L_i (i=1,...,n) - длины полученных кусков трости, занумерованные в порядке убывания длины: L_1 \geq L_2 \geq \ldots \geq L_n. Нетрудно найти математическое ожидание L_i:

l_i=\operatorname{E}(L_i)=\frac{1}{n}\sum_{j=i}^{n} \frac{1}{j}.

По правилу сломанной трости k-й собственный вектор (в порядке убывания собственных чисел \lambda_i) сохраняется в списке главных компонент, если

\frac{\lambda_1}{\tr C}>l_1 \& \frac{\lambda_2}{\tr C}>l_2 \& \ldots \& \frac{\lambda_k}{\tr C}>l_k.

На Рис. приведён пример для 5-мерного случая:

l_1=(1+1/2+1/3+1/4+1/5)/5; l_2=(1/2+1/3+1/4+1/5)/5; l_3=(1/3+1/4+1/5)/5; l_4=(1/4+1/5)/5; l_5=(1/5)/5.

Для примера выбрано

\frac{\lambda_1}{\tr C}=0.5; \frac{\lambda_2}{\tr C}=0.3; \frac{\lambda_3}{\tr C}=0.1; \frac{\lambda_4}{\tr C}=0.06; \frac{\lambda_5}{\tr C}=0.04.

По правилу сломанной трости в этом примере следует оставлять 2 главных компоненты:

\frac{\lambda_1}{\tr C}>l_1 \;; \; \frac{\lambda_2}{\tr C}>l_2 \;; \;\frac{\lambda_3}{\tr C}<l_3\;.

Нормировка

Нормировка после приведения к главным компонентам

После проецирования на первые k главных компонент с \lambda_1 \ge \lambda_2 \ge ... \ge \lambda_k > 0 удобно произвести нормировку на единичную (выборочную) дисперсию по осям. Дисперсия вдоль iй главной компоненты равна \lambda_i > 0 \; (1 \le i \le k), поэтому для нормировки надо разделить соответствующую координату на \sqrt{ \lambda_i}. Это преобразование не является ортогональным и не сохраняет скалярного произведения. Ковариационная матрица проекции данных после нормировки становится единичной, проекции на любые два ортогональных направления становятся независимыми величинами, а любой ортонормированный базис становится базисом главных компонент (напомним, что нормировка меняет отношение ортогональности векторов). Отображение из пространства исходных данных на первые k главных компонент вместе с нормировкой задается матрицей

K=\left \{\frac{a_1}{\sqrt{ \lambda_1}},\frac{a_2}{\sqrt{ \lambda_2}},...,\frac{a_k}{\sqrt{ \lambda_k}} \right \}^T.

Именно это преобразование чаще всего называется преобразованием Кархунена-Лоэва. Здесь a_i — векторы-столбцы, а верхний индекс T означает транспонирование.

Нормировка до вычисления главных компонент

Предупреждение: не следует путать нормировку, проводимую после преобразования к главным компонентам, с нормировкой и «обезразмериванием» при предобработке данных, проводимой до вычисления главных компонент. Предварительная нормировка нужна для обоснованного выбора метрики, в которой будет вычисляться наилучшая аппроксимация денных, или будут искаться направления наибольшего разброса (что эквивалентно). Например, если данные представляют собой трёхмерные векторы из «метров, литров и килограмм», то при использовании стандартного евклидового расстояния разница в 1 метр по первой координате будет вносить тот же вклад, что разница в 1 литр по второй, или в 1 кг по третьей. Обычно системы единиц, в которых представлены исходные данные, недостаточно точно отображают наши представления о естественных масштабах по осям, и проводится «обезразмеривание»: каждая координата делится на некоторый масштаб, определяемый данными, целями их обработки и процессами измерения и сбора данных.

Есть три cущественно различных стандартных подхода к такой нормировке: на единичную дисперсию по осям (масштабы по осям равны средним квадратичным уклонениям — после этого преобразования ковариационная матрица совпадает с матрицей коэффициентов корреляции), на равную точность измерения (масштаб по оси пропорционален точности измерения данной величины) и на равные требования в задаче (масштаб по оси определяется требуемой точностью прогноза данной величины или допустимым её искажением — уровнем толерантности). На выбор предобработки влияют содержательная постановка задачи, а также условия сбора данных (например, если коллекция данных принципиально не завершена и данные будут ещё поступать, то нерационально выбирать нормировку строго на единичную дисперсию, даже если это соответствует смыслу задачи, поскольку это предполагает перенормировку всех данных после получения новой порции; разумнее выбрать некоторый масштаб, грубо оценивающий стандартное отклонение, и далее его не менять).

Предварительная нормировка на единичную дисперсию по осям разрушается поворотом системы координат, если оси не являются главными компонентами, и нормировка при предобработке данных не заменяет нормировку после приведения к главным компонентам.

Механическая аналогия и метод главных компонент для взвешенных данных

Если сопоставить каждому вектору данных единичную массу, то эмпирическая ковариационная матрица C совпадёт с тензором инерции этой системы точечных масс (делённым на полную массу m), а задача о главных компонентых — с задачей приведения тензора инерции к главным осям. Можно использовать дополнительную свободу в выборе значений масс для учета важности точек данных или надежности их значений (важным данным или данным из более надежных источников приписываются бо́льшие массы). Если вектору данных x_l придаётся масса w_l, то вместо эмпирической ковариационной матрицы C получим

C^w = [c^w_{ij}],\ c^w_{ij} = \frac{1}{\sum_{l} w_l} \sum_{l=1}^m w_l(x_{li}-\overline{X_{i}})(x_{lj}-\overline{X_{j}}).

Все дальнейшие операции по приведению к главным компонентам производятся так же, как и в основной версии метода: ищем ортонормированный собственный базис C^w, упорядочиваем его по убыванию собственных значений, оцениваем средневзвешенную ошибку аппроксимации данных первыми k компонентами (по суммам собственных чисел C^w), нормируем и т. п.

Более общий способ взвешивания даёт максимизация взвешенной суммы попарных расстояний[1] между проекциями. Для каждых двух точек данных, x_l , \ x_q вводится вес d_{lq}; d_{lq}=d_{ql} и d_{l}=\sum_{q=1}^m d_{lq}. Вместо эмпирической ковариационной матрицы C используется

C^d = [c^d_{ij}],\ c^d_{ij} =\sum_{l=1}^m d_l (x_{li}-\overline{X_{i}})(x_{lj}-\overline{X_{j}}) -\sum_{l \neq q, \ l,q=1}^m d_{lq}(x_{li} - \overline{X_{i}})(x_{qj}- \overline{X_{j}}).

При d_{lq}>0 симметричная матрица C^d положительно определена, поскольку положительна квадратичная форма:

\sum_{ij} c^d_{ij}a_i a_j = \frac{1}{2}\sum_{lq}d_{lq}\left(\sum_ia_i(x_{li}-x_{qi})\right)^2.

Далее ищем ортонормированный собственный базис C^d, упорядочиваем его по убыванию собственных значений, оцениваем средневзвешенную ошибку аппроксимации данных первыми k компонентами и т. д. — в точности так же, как и в основном алгоритме.

Этот способ применяется при наличии классов: для x_l , \ x_q из разных классов вес d_{lq} вес выбирается бо́льшим, чем для точек одного класса. В результате, в проекции на взвешенные главные компоненты различные классы «раздвигаются» на большее расстояние.

Другое применение — снижение влияния больших уклонений (оутлайеров, англ.Outlier), которые могут искажать картину из-за использования среднеквадратичного расстояния: если выбрать d_{lq}=1/ \| x_l -x_q \|, то влияние больших уклонений будет уменьшено. Таким образом, описанная модификация метода главных компонент является более робастной, чем классическая.

Устойчивость главных компонент

Найденные из выборки главные компоненты — это оценки собственных векторов истинной (генеральной) ковариационной матрицы \Sigma, и как всякие статистические оценки, они подвержены случайным колебаниям от выборки к выборке. Вопрос об устойчивости — это вопрос о том, насколько сильно малое возмущение ковариационной матрицы (за счёт конечности выборки, шума измерений или удаления/добавления небольшого числа наблюдений) может изменить найденные направления a_k.

Чувствительность к близким собственным значениям. Если истинная эмпирическая матрица C возмущена на E (\hat C = C+E), то по классической теореме о возмущении собственных векторов[1] угол между истинным и возмущённым k-м собственным вектором ограничен, с точностью до постоянного множителя, отношением нормы возмущения к зазору между соседними собственными значениями:

\sin\theta(a_k,\hat a_k) \le \frac{\|E\|}{\min(\lambda_{k-1}-\lambda_k,\ \lambda_k-\lambda_{k+1})}.

Отсюда — практически важный вывод: направления, отвечающие хорошо разделённым (далеко отстоящим друг от друга) собственным значениям, устойчивы к малым возмущениям данных; направления же, отвечающие близким или совпадающим собственным значениям, определены плохо, и небольшое изменение выборки может произвольно «перемешать» соответствующие компоненты между собой — в согласии с замечанием о неединственности a_k при вырожденном спектре в разделе «Диагонализация ковариационной матрицы».

Классическая асимптотическая теория. Андерсон[1] показал, что при фиксированной размерности n и растущем объёме выборки m\to\infty, если собственные значения генеральной ковариационной матрицы попарно различны, выборочные собственные значения и собственные векторы — состоятельные и асимптотически нормальные оценки истинных, с дисперсией оценки a_k, обратно пропорциональной квадрату зазора (\lambda_k-\lambda_j)^{-2} до соседних собственных значений — количественное уточнение качественного вывода предыдущего пункта.

Неустойчивость в режиме больших размерностей. Классическая теория Андерсона предполагает, что размерность n фиксирована, а растёт только объём выборки m. Для многих задач машинного обучения — с сотнями и тысячами признаков при ограниченном числе наблюдений — более реалистичен режим, когда n и m растут одновременно, n/m\to\gamma>0. В этом режиме поведение метода главных компонент меняется качественно: Джонстон[1] показал (методами теории случайных матриц), что даже для данных без какой-либо реальной структуры («шум») наибольшее выборочное собственное значение систематически завышает истинное и флуктуирует по универсальному закону Трейси — Видома, а Джонстон и Лу[1] установили, что в этом же режиме выборочные главные компоненты могут быть несостоятельными оценками истинных направлений — то есть не сходиться к ним даже при неограниченном росте m и n одновременно, — если соответствующее истинное собственное значение недостаточно велико по сравнению с «шумовым фоном» остальных направлений. Это явление — одна из главных причин практического интереса к регуляризованным вариантам метода, в частности к разреженному PCA (см. раздел «Ядерный, разреженный и робастный PCA»), который восстанавливает состоятельность оценки за счёт дополнительного предположения о разреженности истинных нагрузок.

Практическая оценка устойчивости. На практике устойчивость конкретного разложения (не полагаясь на асимптотические формулы) часто оценивают эмпирически, методом бутстрепа: по многократно передискретизированным версиям выборки заново вычисляют главные компоненты и смотрят на разброс получаемых направлений или объяснённой ими дисперсии; большой разброс свидетельствует о неустойчивости выбранного числа компонент или о близости соответствующих собственных значений.

Анализ соответствий

Анализ соответствий (франц. analyse des correspondances, англ. correspondence analysis) — аналог метода главных компонент для категориальных данных, представленных в виде таблицы сопряжённости (contingency table), а не в виде количественных признаков.

Пусть N=[n_{ij}] — таблица сопряжённости размера I\times J (например, число совместных наблюдений категории i одной номинальной переменной с категорией j другой), n=\sum_{ij}n_{ij} — общее число наблюдений, P=N/n=[p_{ij}] — матрица соответствия. Обозначим через r_i=\sum_j p_{ij} и c_j=\sum_i p_{ij} «массы» строк и столбцов (их маргинальные частоты). При независимости строковой и столбцовой переменных ожидаемая частота в ячейке (i,j) равнялась бы r_i c_j; анализ соответствий ищет главные направления отклонения наблюдаемых частот от этой гипотезы независимости, для чего строится матрица стандартизованных остатков

s_{ij} = \frac{p_{ij} - r_i c_j}{\sqrt{r_i c_j}},

— в точности те слагаемые, сумма квадратов которых образует статистику \chi^2 критерия независимости для данной таблицы сопряжённости. Сингулярное разложение этой матрицы, S=[s_{ij}]=U\Sigma V^\top, даёт «главные оси» анализа соответствий — координаты строк и столбцов таблицы в общем низкоразмерном пространстве, которые наносятся на одну диаграмму («карту соответствий»): категории строк и столбцов, часто встречающиеся друг с другом, оказываются на карте ближе, а редко встречающиеся вместе — дальше.

По математической структуре анализ соответствий эквивалентен методу главных компонент, применённому не к евклидовой, а к \chi^2-метрике между профилями строк (или столбцов) таблицы, взвешенными обратно пропорционально соответствующим массам r_i (c_j), — то есть той же задаче диагонализации, что обсуждалась выше, но для взвешенной и метрически преобразованной версии данных, а не для исходной ковариационной матрицы.

Метод восходит к работам по анализу таблиц сопряжённости 1930—1940-х годов; в частности, базовое уравнение метода связывают с работой Р. Фишера 1940 года по дискриминантному анализу категориальных признаков. Как самостоятельный, систематически развитый метод анализ соответствий был предложен и подробно разработан Ж.-П. Бензекри и французской школой анализа данных в 1960—1970-е годы[1]; наиболее полное изложение теории и приложений метода на английском языке дал впоследствии Гринакр[1].

Метод особенно популярен в социальных науках, лингвистике (лексикометрия, анализ частотных таблиц «слово × документ») и маркетинговых исследованиях, где данные по своей природе категориальны, а не количественны, и где совместная визуализация категорий строк и столбцов на общей карте даёт содержательно интерпретируемую картину структуры данных — в этом смысле анализ соответствий для категориальных таблиц играет ту же роль, что метод главных компонент для количественных.

Специальная терминология

В статистике при использовании метода главных компонент используют несколько специальных терминов.

Матрица данных \mathbf{X}=\{x_1,... x_m\}^T; каждая строка — вектор предобработанных данных (центрированных и правильно нормированных), число строк — m (количество векторов данных), число столбцов — n (размерность пространства данных);

Матрица нагрузок (Loadings) \mathbf{P}=\{a_1,... a_k\}; каждый столбец — вектор главных компонент, число строк — n (размерность пространства данных), число столбцов — k (количество векторов главных компонент, выбранных для проецирования);

Матрица счетов (Scores) \mathbf{T}=[t_{ij}]; \; t_{ij}=(x_i,a_j); каждая строка — проекция вектора данных на k главных компонент; число строк — m (количество векторов данных), число столбцов — k (количество векторов главных компонент, выбранных для проецирования);

Матрица Z-счетов (Z-scores) \mathbf{Z}=[z_{ij}]; \; z_{ij}=\frac{(x_i,a_j)}{\sqrt{ \lambda_j}}; каждая строка — проекция вектора данных на k главных компонент, нормированная на единичную выборочную дисперсию; число строк — m (количество векторов данных), число столбцов — k (количество векторов главных компонент, выбранных для проецирования);

Матрица ошибок (или остатков) (Errors or residuals) \mathbf{E}=\mathbf{X}-\mathbf{T}\mathbf{P}^T.

Основная формула: \mathbf{X}=\mathbf{T}\mathbf{P}^T+\mathbf{E}.

Вероятностная трактовка и связь с обучением представлений

Вероятностный PCA

Помимо четырёх классических постановок задачи (см. раздел «Формальная постановка задачи»), у метода главных компонент есть вероятностная переформулировка. Вероятностный PCA (Probabilistic PCA, PPCA) задаёт порождающую модель

x = W z + \mu + \varepsilon, \qquad z\sim\mathcal N(0,I_k),\ \ \varepsilon\sim\mathcal N(0,\sigma^2 I_n),

где z — ненаблюдаемые (скрытые) переменные меньшей размерности k<n. Маргинальное распределение наблюдаемых данных при этом гауссово: x\sim\mathcal N(\mu,\,WW^\top+\sigma^2 I_n), а параметры W и \sigma^2 оцениваются максимизацией правдоподобия[1]. При \sigma^2\to0 максимально правдоподобное решение W совпадает (с точностью до вращения и масштаба столбцов) с классическими главными компонентами, полученными из диагонализации ковариационной матрицы. Оценка параметров W,\sigma^2 естественно проводится EM-алгоритмом, попеременно уточняющим апостериорное распределение скрытых переменных z и параметры модели — то есть частным случаем альтернированной минимизации. Вероятностная формулировка даёт, в частности, естественный способ работы с пропущенными значениями в данных и байесовские критерии выбора числа компонент k, дополняющие эвристику «сломанной трости» из соответствующего раздела.

PCA как линейный автокодировщик

Пусть x пропускается через линейный автокодировщик с k-мерным узким слоем: x \mapsto W_2 W_1 x, где W_1\in\mathbb{R}^{k\times n}, W_2\in\mathbb{R}^{n\times k}, а параметры подбираются минимизацией среднеквадратичной ошибки восстановления \sum_i \|x_i - W_2 W_1 x_i\|^2. Болди и Хорник[1] строго показали, что при такой (линейной, без нелинейностей активации) архитектуре целевая функция не имеет плохих локальных минимумов, а любое её глобально оптимальное решение натягивает то же самое k-мерное подпространство, что и первые k главных компонент, хотя сам автокодировщик обучается градиентными методами, а не диагонализацией ковариационной матрицы. Этот результат объясняет, почему PCA часто используют как быстрый и надёжный ориентир при оценке качества более сложных (нелинейных) автокодировщиков и как способ инициализации весов линейных слоёв нейронных сетей.

Пределы применимости и ограничения эффективности метода

Построение ветвящихся главных компонент методом топологических грамматик. Крестики — точки данных, красное дерево с желтыми узлами — аппроксимирующий дендрит.
Построение ветвящихся главных компонент методом топологических грамматик. Крестики — точки данных, красное дерево с желтыми узлами — аппроксимирующий дендрит[1].

Метод главных компонент применим всегда. Распространённое утверждение о том, что он применим только к нормально распределённым данным (или для распределений, близких к нормальным) неверно: в исходной формулировке К. Пирсона ставится задача об аппроксимации конечного множества данных и отсутствует даже гипотеза о их статистическом порождении, не говоря уж о распределении.

Однако метод не всегда эффективно снижает размерность при заданных ограничениях на точность \delta_k. Прямые и плоскости не всегда обеспечивают хорошую аппроксимацию. Например, данные могут с хорошей точностью следовать какой-нибудь кривой, а эта кривая может быть сложно расположена в пространстве данных. В этом случае метод главных компонент для приемлемой точности потребует нескольких компонент (вместо одной), или вообще не даст снижения размерности при приемлемой точности. Для работы с такими «кривыми» главными компонентами изобретен метод главных многообразий[1] и различные версии нелинейного метода главных компонент[1][1]. Больше неприятностей могут доставить данные сложной топологии. Для их аппроксимации также изобретены различные методы, например самоорганизующиеся карты Кохонена, нейронный газ[1] или топологические грамматики[1]. Если данные статистически порождены с распределением, сильно отличающимся от нормального, то для аппроксимации распределения полезно перейти от главных компонент к независимым компонентам[1], которые уже не ортогональны в исходном скалярном произведении. Наконец, для изотропного распределения (даже нормального) вместо эллипсоида рассеяния получаем шар, и уменьшить размерность методами аппроксимации невозможно.

Ядерный, разреженный и робастный PCA

Ядерный PCA

Заменяя евклидово скалярное произведение (x_i,x_j) на значение некоторой ядерной функции k(x_i,x_j)=(\phi(x_i),\phi(x_j)) для нелинейного отображения \phi в пространство более высокой (возможно, бесконечной) размерности, можно вычислить главные компоненты в этом пространстве признаков, не вычисляя \phi явно, — эквивалентная задача сводится к собственному разложению центрированной матрицы Грама K_{ij}=k(x_i,x_j)[1]. В отличие от рассмотренных выше главных многообразий и топологических грамматик, ядерный PCA сохраняет линейно-алгебраическую структуру исходной задачи (собственное разложение), перенося нелинейность целиком в выбор ядра.

Разреженный PCA

Векторы главных компонент a_k в классической постановке, как правило, являются плотными линейными комбинациями всех n исходных координат, что затрудняет их содержательную интерпретацию при большом n. Цзоу, Хасти и Тибширани[1] предложили переформулировать задачу как регрессию с эластичной сетью (\ell_1+\ell_2-регуляризация), дающую компоненты с малым числом ненулевых координат при сохранении большей части объяснённой дисперсии — такой подход называется разреженным PCA (Sparse PCA).

Робастный PCA

Классический метод главных компонент чувствителен к грубым выбросам в данных: как видно из формулы остаточной дисперсии, даже одно сильно искажённое наблюдение способно заметно исказить найденные собственные векторы, поскольку выборочная ковариация — квадратичная функция уклонений. Устойчивость к выбросам через взвешивание попарных расстояний уже обсуждалась выше (см. раздел «Механическая аналогия и метод главных компонент для взвешенных данных»); отдельный, более поздний подход дали Кандес, Ли, Ма и Райт[1], показавшие, что при определённых условиях можно точно восстановить низкоранговую составляющую матрицы данных X, даже если неизвестная, но разреженная доля её элементов повреждена сколь угодно сильно, решая выпуклую задачу Principal Component Pursuit:

\min_{L,S}\ \|L\|_* + \lambda\|S\|_1 при X=L+S,

где \|L\|_* — ядерная норма (сумма сингулярных чисел L), выпуклая релаксация ранга, а \|S\|_1 поощряет разреженность матрицы выбросов S. В отличие от взвешивания попарных расстояний, этот метод не требует заранее знать, какие именно наблюдения — выбросы, и восстанавливает их положение как часть решения задачи оптимизации.

Примеры использования

Основная статья: Применение метода главных компонент

Метод главных компонент — наиболее популярный метод сокращения размерности во многих приложениях, в том числе в следующих областях:

  • Визуализация данных;
  • Компрессия изображений и видео;
  • Подавление шума на изображениях;
  • Индексация видео;
  • Биоинформатика;
  • Хемометрика;
  • Психодиагностика;
  • Общественные науки (включая политологию);
  • Сокращение размерности динамических моделей (в том числе — в вычислительной гидродинамике).

Два примера подробнее иллюстрируют применение метода в задачах машинного обучения и искусственного интеллекта:

  • Собственные лица (Eigenfaces). Тёрк и Пентланд[1] представили каждое изображение лица как точку в низкоразмерном подпространстве, натянутом на главные компоненты обучающего набора лиц («собственные лица»), а распознавание свели к сравнению координат в этом подпространстве — одна из первых успешных систем автоматического распознавания лиц и по сей день учебный эталон применения PCA в компьютерном зрении.
  • Матричная факторизация в рекомендательных системах. Метод главных компонент — частный случай факторизации матрицы данных с ограничением ортогональности факторов; более общие билинейные модели матричной факторизации, включая факторизацию методом чередующихся наименьших квадратов (ALS) для рекомендательных систем[1], оптимизируются методом альтернированной минимизации, тогда как сам PCA через сингулярное разложение можно рассматривать как точное — не итеративное — решение соответствующей билинейной задачи при дополнительном ограничении ортогональности факторов.

Литература

Классические работы

  • Pearson K., On lines and planes of closest fit to systems of points in space, Philosophical Magazine, (1901) 2, 559—572; а также на сайте PCA.
  • Sylvester J.J., On the reduction of a bilinear quantic of the nth order to the form of a sum of n products by a double orthogonal substitution, Messenger of Mathematics, 19 (1889), 42—46; а также на сайте PCA.
  • Frećhet M. Les élements aléatoires de nature quelconque dans un espace distancié. Ann. Inst. H. Poincaré, 10 (1948), 215—310.

Основные руководства (стандарт де-факто)

  • Айвазян С. А., Бухштабер В. М., Енюков И. С., Мешалкин Л. Д. Прикладная статистика. Классификация и снижение размерности.— М.: Финансы и статистика, 1989.— 607 с.
  • Рао С. Р., Линейные статистические методы и их применения.— М.: Наука (Физматлит), 1968.— 548 с.
  • Jolliffe I.T. Principal Component Analysis, Series: Springer Series in Statistics, 2nd ed., Springer, NY, 2002, XXIX, 487 p. 28 illus. ISBN 978-0-387-95442-4

Сборник современных обзоров

Современные работы по машинному обучению

  • Oja E., A simplified neuron model as a principal component analyzer, Journal of Mathematical Biology, 15 (1982) 3, 267—273.
  • Turk M., Pentland A., Eigenfaces for recognition, Journal of Cognitive Neuroscience, 3 (1991) 1, 71—86.
  • Baldi P., Hornik K., Neural networks and principal component analysis: Learning from examples without local minima, Neural Networks, 2 (1989) 1, 53—58.
  • Schölkopf B., Smola A., Müller K.-R., Nonlinear component analysis as a kernel eigenvalue problem, Neural Computation, 10 (1998) 5, 1299—1319.
  • Tipping M. E., Bishop C. M., Probabilistic Principal Component Analysis, Journal of the Royal Statistical Society: Series B, 61 (1999) 3, 611—622.
  • Zou H., Hastie T., Tibshirani R., Sparse principal component analysis, Journal of Computational and Graphical Statistics, 15 (2006) 2, 265—286.
  • Candès E. J., Li X., Ma Y., Wright J., Robust principal component analysis?, Journal of the ACM, 58 (2011) 3, статья 11.
  • Halko N., Martinsson P. G., Tropp J. A., Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions, SIAM Review, 53 (2011) 2, 217—288.
  • Koren Y., Bell R., Volinsky C., Matrix factorization techniques for recommender systems, Computer, 42 (2009) 8, 30—37.

Ссылки

Учебное програмное обеспечение

Java-апплет «Метод главных компонент и самоорганизующиеся карты» (E.M. Mirkes, Principal Component Analysis and Self-Organizing Maps: applet. University of Leicester, 2011). Свободно распространяемая программа с моделями метода главных компонент, самоорганизуюшихся карт (SOM) и растущих самоорганизующихся карт (Growing Self-Organized Maps, GSOM). Дано описание алгоритмов (англ.), приведены тьюториалы и некоторые публикации. Используется для выполнения небольших студенческих исследовательских работ по сравнению различных алгоритмов аппроксимации данных.

Примечания


Незарегистрированные пользователи не видят примечаний и основных литературных ссылок (дефект системы). Зарегистрироваться безопасно и просто.

Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%9C%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»
Личные инструменты