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

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

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

Текущая версия

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

Содержание

1 Формальная постановка задачи
- 1.1 Аппроксимация данных линейными многообразиями
- 1.2 Поиск ортогональных проекций с наибольшим рассеянием
- 1.3 Поиск ортогональных проекций с наибольшим среднеквадратичным расстоянием между точками
- 1.4 Аннулирование корреляций между координатами
2 Диагонализация ковариационной матрицы
3 Сингулярное разложение матрицы данных
4 Вычисление для больших и потоковых данных
- 4.1 Рандомизированные алгоритмы
- 4.2 Онлайн-вычисление: правило Ойя
5 Матрица преобразования к главным компонентам
6 Остаточная дисперсия
7 Оценка числа главных компонент по правилу сломанной трости
8 Нормировка
- 8.1 Нормировка после приведения к главным компонентам
- 8.2 Нормировка до вычисления главных компонент
9 Механическая аналогия и метод главных компонент для взвешенных данных
10 Устойчивость главных компонент
11 Анализ соответствий
12 Специальная терминология
13 Вероятностная трактовка и связь с обучением представлений
- 13.1 Вероятностный PCA
- 13.2 PCA как линейный автокодировщик
14 Пределы применимости и ограничения эффективности метода
15 Ядерный, разреженный и робастный PCA
- 15.1 Ядерный PCA
- 15.2 Разреженный PCA
- 15.3 Робастный PCA
16 Примеры использования
17 Литература
- 17.1 Классические работы
- 17.2 Основные руководства (стандарт де-факто)
- 17.3 Сборник современных обзоров
- 17.4 Современные работы по машинному обучению
18 Ссылки
19 Учебное програмное обеспечение
20 Примечания

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

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

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

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

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

Иллюстрация к знаменитой работе К. Пирсона (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.

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

Вопрос, как оценить число необходимых главных компонент, если отношение "сигнал/шум" заранее неизвестно? Одним из наиболее популярных эвристических подходов является правило сломанной трости (англ. 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

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

Gorban A. N., Kegl B., Wunsch D., Zinovyev A. Y. (Eds.), Principal Manifolds for Data Visualisation and Dimension Reduction, Series: Lecture Notes in Computational Science and Engineering 58, Springer, Berlin — Heidelberg — New York, 2008, XXIV, 340 p. 82 illus. ISBN 978-3-540-73749-0 (а также онлайн).

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

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.

Ссылки

A tutorial on Principal Components Analysis, Jonathon Shlens, 22, 2009; Version 3.01.
Нелинейный метод главных компонент (сайт-библиотека)
Метод главных компонент на wikipedia.org

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

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

Примечания

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

Источник — «http://www.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»

@@ Строка 62: / Строка 62: @@
-Пусть нам дан центрированный набор векторов данных <tex>x_i\in\mathbb{R}^n \; (i=1,...,m)</tex> (среднее арифметическое значение <tex> x_i </tex> равно нулю). Задача — найти такое ортогональное преобразование в новую систему координат, для которого были бы верны следующие условия:
+Пусть нам дан центрированный набор векторов данных <tex>x_i\in\mathbb{R}^n \; (i=1,...,m)</tex> (среднее арифметическое значение <tex> x_i </tex> равно нулю). Задача — найти такое ортогональное преобразование в новую систему координат, для которого были бы верны следующие условия:
 * [[Выборочная дисперсия]] данных вдоль первой координаты максимальна (эту координату называют первой ''главной компонентой'');
 * Выборочная дисперсия данных вдоль второй координаты максимальна при условии ортогональности первой координате (вторая главная компонента);
@@ Строка 73: / Строка 73: @@
 (поскольку данные центрированы, выборочная дисперсия здесь совпадает со средним квадратом уклонения от нуля).
-Формально, если <tex>A=\left \{a_1,...,a_n \right \}^T\in\mathbb{R}^{n \times n}</tex>, <tex>a_k\in\mathbb{R}^n</tex> — искомое преобразование, то для векторов <tex>a_k</tex> должны выполняться следующие условия:
+Формально, если <tex>A=\left \{a_1,...,a_n \right \}^T\in\mathbb{R}^{n \times n}</tex>, <tex>a_k\in\mathbb{R}^n</tex> — искомое преобразование, то для векторов <tex>a_k</tex> должны выполняться следующие условия:
 * <tex>a_1 = \underset{\| a_1 \| =1}{\operatorname{argmax}}\,S^2_m \left [(X, a_1) \right ];</tex>
 : Если решение не единственно, то выбираем одно из них.
@@ Строка 126: / Строка 126: @@
 Теория сингулярного разложения была создана Дж. Дж. Сильвестром (англ. [http://en.wikipedia.org/wiki/James_Joseph_Sylvester J. J. Sylvester]) в 1889 г. и изложена во всех подробных руководствах по теории матриц <ref>''Гантмахер Ф. Р.'', Теория матриц. — М.: Наука, 1966. — 576 стр.</ref>.
+== Вычисление для больших и потоковых данных ==
+=== Рандомизированные алгоритмы ===
+Для матриц данных с очень большим числом строк и/или столбцов точное вычисление сингулярного разложения может быть неприемлемо дорогим. Халко, Мартинссон и Тропп<ref>''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.</ref> показали, что случайная проекция матрицы данных на низкоразмерное подпространство с последующим точным разложением уже существенно меньшей матрицы даёт приближённое сингулярное разложение (а значит, и приближённые главные компоненты) с контролируемой точностью и на порядки меньшей вычислительной стоимостью, чем прямое вычисление. Этот подход стал стандартом практического вычисления метода главных компонент на данных с миллионами наблюдений и признаков.
+=== Онлайн-вычисление: правило Ойя ===
+Если данные поступают последовательно (потоком) и не помещаются в памяти целиком, применяют онлайн-обновление вида
+: <tex>a_{t+1} = a_t + \eta_t\, y_t\,(x_t - y_t a_t), \qquad y_t = a_t^\top x_t,</tex>
+предложенное Ойя<ref>''Oja E.'', A simplified neuron model as a principal component analyzer, Journal of Mathematical Biology, 15 (1982) 3, 267—273.</ref> — простое правило хеббовского обучения одного линейного нейрона, сходящееся к первой главной компоненте по мере поступления новых наблюдений <tex>x_t</tex> без необходимости хранить или повторно обрабатывать уже увиденные данные. Это правило стало одним из первых примеров биологически правдоподобного алгоритма обучения представлений и одной из точек соприкосновения метода главных компонент с теорией искусственных нейронных сетей.
 == Матрица преобразования к главным компонентам ==
@@ Строка 201: / Строка 215: @@
 == Устойчивость главных компонент ==
+Найденные из выборки главные компоненты — это оценки собственных векторов истинной (генеральной) ковариационной матрицы <tex>\Sigma</tex>, и как всякие статистические оценки, они подвержены случайным колебаниям от выборки к выборке. Вопрос об устойчивости — это вопрос о том, насколько сильно малое возмущение ковариационной матрицы (за счёт конечности выборки, шума измерений или удаления/добавления небольшого числа наблюдений) может изменить найденные направления <tex>a_k</tex>.
+'''Чувствительность к близким собственным значениям.''' Если истинная эмпирическая матрица <tex>C</tex> возмущена на <tex>E</tex> (<tex>\hat C = C+E</tex>), то по классической теореме о возмущении собственных векторов<ref>''Davis C., Kahan W. M.'', The rotation of eigenvectors by a perturbation. III, SIAM Journal on Numerical Analysis, 7 (1970) 1, 1—46.</ref> угол между истинным и возмущённым <tex>k</tex>-м собственным вектором ограничен, с точностью до постоянного множителя, отношением нормы возмущения к '''зазору между соседними собственными значениями''':
+: <tex>\sin\theta(a_k,\hat a_k) \le \frac{\|E\|}{\min(\lambda_{k-1}-\lambda_k,\ \lambda_k-\lambda_{k+1})}.</tex>
+Отсюда — практически важный вывод: направления, отвечающие хорошо разделённым (далеко отстоящим друг от друга) собственным значениям, устойчивы к малым возмущениям данных; направления же, отвечающие близким или совпадающим собственным значениям, определены плохо, и небольшое изменение выборки может произвольно «перемешать» соответствующие компоненты между собой — в согласии с замечанием о неединственности <tex>a_k</tex> при вырожденном спектре в разделе «Диагонализация ковариационной матрицы».
+'''Классическая асимптотическая теория.''' Андерсон<ref>''Anderson T. W.'', Asymptotic theory for principal component analysis, The Annals of Mathematical Statistics, 34 (1963) 1, 122—148.</ref> показал, что при фиксированной размерности <tex>n</tex> и растущем объёме выборки <tex>m\to\infty</tex>, если собственные значения генеральной ковариационной матрицы попарно различны, выборочные собственные значения и собственные векторы — состоятельные и асимптотически нормальные оценки истинных, с дисперсией оценки <tex>a_k</tex>, обратно пропорциональной квадрату зазора <tex>(\lambda_k-\lambda_j)^{-2}</tex> до соседних собственных значений — количественное уточнение качественного вывода предыдущего пункта.
+'''Неустойчивость в режиме больших размерностей.''' Классическая теория Андерсона предполагает, что размерность <tex>n</tex> фиксирована, а растёт только объём выборки <tex>m</tex>. Для многих задач машинного обучения — с сотнями и тысячами признаков при ограниченном числе наблюдений — более реалистичен режим, когда <tex>n</tex> и <tex>m</tex> растут одновременно, <tex>n/m\to\gamma>0</tex>. В этом режиме поведение метода главных компонент меняется качественно: Джонстон<ref>''Johnstone I. M.'', On the distribution of the largest eigenvalue in principal components analysis, The Annals of Statistics, 29 (2001) 2, 295—327.</ref> показал (методами теории случайных матриц), что даже для данных без какой-либо реальной структуры («шум») наибольшее выборочное собственное значение систематически завышает истинное и флуктуирует по универсальному закону Трейси — Видома, а Джонстон и Лу<ref>''Johnstone I. M., Lu A. Y.'', On Consistency and Sparsity for Principal Components Analysis in High Dimensions, Journal of the American Statistical Association, 104 (2009) 486, 682—693.</ref> установили, что в этом же режиме выборочные главные компоненты могут быть '''несостоятельными''' оценками истинных направлений — то есть не сходиться к ним даже при неограниченном росте <tex>m</tex> и <tex>n</tex> одновременно, — если соответствующее истинное собственное значение недостаточно велико по сравнению с «шумовым фоном» остальных направлений. Это явление — одна из главных причин практического интереса к регуляризованным вариантам метода, в частности к разреженному PCA (см. раздел «Ядерный, разреженный и робастный PCA»), который восстанавливает состоятельность оценки за счёт дополнительного предположения о разреженности истинных нагрузок.
+'''Практическая оценка устойчивости.''' На практике устойчивость конкретного разложения (не полагаясь на асимптотические формулы) часто оценивают эмпирически, методом бутстрепа: по многократно передискретизированным версиям выборки заново вычисляют главные компоненты и смотрят на разброс получаемых направлений или объяснённой ими дисперсии; большой разброс свидетельствует о неустойчивости выбранного числа компонент или о близости соответствующих собственных значений.
 == Анализ соответствий ==
-[[анализ соответствий|Анализ соответствий]] (англ. [http://www.statsoft.com/textbook/stcoran.html Correspondence analysis])...
+'''Анализ соответствий''' (франц. analyse des correspondances, англ. correspondence analysis) — аналог метода главных компонент для категориальных данных, представленных в виде таблицы сопряжённости (contingency table), а не в виде количественных признаков.
+Пусть <tex>N=[n_{ij}]</tex> — таблица сопряжённости размера <tex>I\times J</tex> (например, число совместных наблюдений категории <tex>i</tex> одной номинальной переменной с категорией <tex>j</tex> другой), <tex>n=\sum_{ij}n_{ij}</tex> — общее число наблюдений, <tex>P=N/n=[p_{ij}]</tex> — матрица соответствия. Обозначим через <tex>r_i=\sum_j p_{ij}</tex> и <tex>c_j=\sum_i p_{ij}</tex> «массы» строк и столбцов (их маргинальные частоты). При независимости строковой и столбцовой переменных ожидаемая частота в ячейке <tex>(i,j)</tex> равнялась бы <tex>r_i c_j</tex>; анализ соответствий ищет главные направления отклонения наблюдаемых частот от этой гипотезы независимости, для чего строится матрица стандартизованных остатков
+: <tex>s_{ij} = \frac{p_{ij} - r_i c_j}{\sqrt{r_i c_j}},</tex>
+— в точности те слагаемые, сумма квадратов которых образует статистику <tex>\chi^2</tex> критерия независимости для данной таблицы сопряжённости. Сингулярное разложение этой матрицы, <tex>S=[s_{ij}]=U\Sigma V^\top</tex>, даёт «главные оси» анализа соответствий — координаты строк и столбцов таблицы в общем низкоразмерном пространстве, которые наносятся на одну диаграмму («карту соответствий»): категории строк и столбцов, часто встречающиеся друг с другом, оказываются на карте ближе, а редко встречающиеся вместе — дальше.
+По математической структуре анализ соответствий эквивалентен методу главных компонент, применённому не к евклидовой, а к <tex>\chi^2</tex>-метрике между профилями строк (или столбцов) таблицы, взвешенными обратно пропорционально соответствующим массам <tex>r_i</tex> (<tex>c_j</tex>), — то есть той же задаче диагонализации, что обсуждалась выше, но для взвешенной и метрически преобразованной версии данных, а не для исходной ковариационной матрицы.
+Метод восходит к работам по анализу таблиц сопряжённости 1930—1940-х годов; в частности, базовое уравнение метода связывают с работой Р. Фишера 1940 года по дискриминантному анализу категориальных признаков. Как самостоятельный, систематически развитый метод анализ соответствий был предложен и подробно разработан Ж.-П. Бензекри и французской школой анализа данных в 1960—1970-е годы<ref>''Benzécri J.-P. et coll.'', L'Analyse des Données. Tome 2: L'Analyse des Correspondances, Paris, Dunod, 1973 (2-е изд. 1976).</ref>; наиболее полное изложение теории и приложений метода на английском языке дал впоследствии Гринакр<ref>''Greenacre M. J.'', Theory and Applications of Correspondence Analysis, London, Academic Press, 1984. XI+364 pp. ISBN 0-12-299050-1.</ref>.
+Метод особенно популярен в социальных науках, лингвистике (лексикометрия, анализ частотных таблиц «слово × документ») и маркетинговых исследованиях, где данные по своей природе категориальны, а не количественны, и где совместная визуализация категорий строк и столбцов на общей карте даёт содержательно интерпретируемую картину структуры данных — в этом смысле анализ соответствий для категориальных таблиц играет ту же роль, что метод главных компонент для количественных.
 == Специальная терминология ==
@@ Строка 221: / Строка 261: @@
 Основная формула: <tex>\mathbf{X}=\mathbf{T}\mathbf{P}^T+\mathbf{E}.</tex>
+== Вероятностная трактовка и связь с обучением представлений ==
+=== Вероятностный PCA ===
+Помимо четырёх классических постановок задачи (см. раздел «Формальная постановка задачи»), у метода главных компонент есть вероятностная переформулировка. '''Вероятностный PCA''' (Probabilistic PCA, PPCA) задаёт порождающую модель
+: <tex>x = W z + \mu + \varepsilon, \qquad z\sim\mathcal N(0,I_k),\ \ \varepsilon\sim\mathcal N(0,\sigma^2 I_n),</tex>
+где <tex>z</tex> — ненаблюдаемые (скрытые) переменные меньшей размерности <tex>k<n</tex>. Маргинальное распределение наблюдаемых данных при этом гауссово: <tex>x\sim\mathcal N(\mu,\,WW^\top+\sigma^2 I_n)</tex>, а параметры <tex>W</tex> и <tex>\sigma^2</tex> оцениваются максимизацией правдоподобия<ref>''Tipping M. E., Bishop C. M.'', Probabilistic Principal Component Analysis, Journal of the Royal Statistical Society: Series B, 61 (1999) 3, 611—622.</ref>. При <tex>\sigma^2\to0</tex> максимально правдоподобное решение <tex>W</tex> совпадает (с точностью до вращения и масштаба столбцов) с классическими главными компонентами, полученными из диагонализации ковариационной матрицы. Оценка параметров <tex>W,\sigma^2</tex> естественно проводится [[EM-алгоритм]]ом, попеременно уточняющим апостериорное распределение скрытых переменных <tex>z</tex> и параметры модели — то есть частным случаем [[альтернированная минимизация|альтернированной минимизации]]. Вероятностная формулировка даёт, в частности, естественный способ работы с пропущенными значениями в данных и байесовские критерии выбора числа компонент <tex>k</tex>, дополняющие эвристику «сломанной трости» из соответствующего раздела.
+=== PCA как линейный автокодировщик ===
+Пусть <tex>x</tex> пропускается через линейный [[автокодировщик]] с <tex>k</tex>-мерным узким слоем: <tex>x \mapsto W_2 W_1 x</tex>, где <tex>W_1\in\mathbb{R}^{k\times n}</tex>, <tex>W_2\in\mathbb{R}^{n\times k}</tex>, а параметры подбираются минимизацией среднеквадратичной ошибки восстановления <tex>\sum_i \|x_i - W_2 W_1 x_i\|^2</tex>. Болди и Хорник<ref>''Baldi P., Hornik K.'', Neural networks and principal component analysis: Learning from examples without local minima, Neural Networks, 2 (1989) 1, 53—58.</ref> строго показали, что при такой (линейной, без нелинейностей активации) архитектуре целевая функция не имеет плохих локальных минимумов, а любое её глобально оптимальное решение натягивает то же самое <tex>k</tex>-мерное подпространство, что и первые <tex>k</tex> главных компонент, хотя сам автокодировщик обучается градиентными методами, а не диагонализацией ковариационной матрицы. Этот результат объясняет, почему PCA часто используют как быстрый и надёжный ориентир при оценке качества более сложных (нелинейных) автокодировщиков и как способ инициализации весов линейных слоёв нейронных сетей.
 == Пределы применимости и ограничения эффективности метода ==
@@ Строка 230: / Строка 284: @@
 Однако метод не всегда эффективно снижает размерность при заданных ограничениях на точность <tex> \delta_k</tex>. Прямые и плоскости не всегда обеспечивают хорошую аппроксимацию. Например, данные могут с хорошей точностью следовать какой-нибудь кривой, а эта кривая может быть сложно расположена в пространстве данных. В этом случае метод главных компонент для приемлемой точности потребует нескольких компонент (вместо одной), или вообще не даст снижения размерности при приемлемой точности. Для работы с такими «кривыми» главными компонентами изобретен метод главных многообразий<ref>С этой работы началось изучение главных многообразий. Диссертация ''T. Хасти'': ''Hastie T.'', [http://www.slac.stanford.edu/pubs/slacreports/slac-r-276.html Principal Curves and Surfaces], Ph.D Dissertation, Stanford Linear Accelerator Center, Stanford University, Stanford, California, US, November 1984. [http://pca.narod.ru/HastieThesis.htm А также на сайте PCA]</ref> и различные версии нелинейного метода главных компонент<ref>''Scholz M., Fraunholz M., Selbig J.'', [http://pca.narod.ru/contentsgkwz.htm Nonlinear Principal Component Analysis: Neural Network Models and Applications], In: Gorban A. N. et al (Eds.), LNCSE 58, Springer, 2007 ISBN 978-3-540-73749-0</ref><ref>''Yin H.'' [http://pca.narod.ru/contentsgkwz.htm Learning Nonlinear Principal Manifolds by Self-Organising Maps], In: Gorban A. N. et al (Eds.), LNCSE 58, Springer, 2007 ISBN 978-3-540-73749-0</ref>. Больше неприятностей могут доставить данные сложной топологии. Для их аппроксимации также изобретены различные методы, например [[Самоорганизующаяся карта Кохонена|самоорганизующиеся карты Кохонена]], [[нейронный газ]]<ref>''Martinetz, T.M., Berkovich, S.G., and Schulten K.J.'', [http://pca.narod.ru/MartinesShultenNeuralGas1993.pdf Neural-gas network for vector quantization and its application to time-series prediction.] IEEE Transactions on Neural Networks, 4 (1993) #4, 558—569. На сайте [http://pca.narod.ru/ PCA]</ref> или топологические грамматики<ref name="TopGram"/>. Если данные статистически порождены с распределением, сильно отличающимся от нормального, то для аппроксимации распределения полезно перейти от главных компонент к ''независимым компонентам''<ref>''Hyvdrinen A, Karhunen J., and Oja E.'', Independent Component Analysis, A Volume in the Wiley Series on Adaptive and Learning Systems for Signal Processing, Communications, and Control. — John Wiley & Sons, Inc., 2001. — XVI+481 pp. ISBN 0-471-40540-X</ref>, которые уже не ортогональны в исходном скалярном произведении. Наконец, для изотропного распределения (даже нормального) вместо эллипсоида рассеяния получаем шар, и уменьшить размерность методами аппроксимации невозможно.
+== Ядерный, разреженный и робастный PCA ==
+=== Ядерный PCA ===
+Заменяя евклидово скалярное произведение <tex>(x_i,x_j)</tex> на значение некоторой ядерной функции <tex>k(x_i,x_j)=(\phi(x_i),\phi(x_j))</tex> для нелинейного отображения <tex>\phi</tex> в пространство более высокой (возможно, бесконечной) размерности, можно вычислить главные компоненты в этом пространстве признаков, не вычисляя <tex>\phi</tex> явно, — эквивалентная задача сводится к собственному разложению центрированной матрицы Грама <tex>K_{ij}=k(x_i,x_j)</tex><ref>''Schölkopf B., Smola A., Müller K.-R.'', Nonlinear component analysis as a kernel eigenvalue problem, Neural Computation, 10 (1998) 5, 1299—1319.</ref>. В отличие от рассмотренных выше главных многообразий и топологических грамматик, ядерный PCA сохраняет линейно-алгебраическую структуру исходной задачи (собственное разложение), перенося нелинейность целиком в выбор ядра.
+=== Разреженный PCA ===
+Векторы главных компонент <tex>a_k</tex> в классической постановке, как правило, являются плотными линейными комбинациями всех <tex>n</tex> исходных координат, что затрудняет их содержательную интерпретацию при большом <tex>n</tex>. Цзоу, Хасти и Тибширани<ref>''Zou H., Hastie T., Tibshirani R.'', Sparse principal component analysis, Journal of Computational and Graphical Statistics, 15 (2006) 2, 265—286.</ref> предложили переформулировать задачу как регрессию с эластичной сетью (<tex>\ell_1+\ell_2</tex>-регуляризация), дающую компоненты с малым числом ненулевых координат при сохранении большей части объяснённой дисперсии — такой подход называется '''разреженным PCA''' (Sparse PCA).
+=== Робастный PCA ===
+Классический метод главных компонент чувствителен к грубым выбросам в данных: как видно из формулы остаточной дисперсии, даже одно сильно искажённое наблюдение способно заметно исказить найденные собственные векторы, поскольку выборочная ковариация — квадратичная функция уклонений. Устойчивость к выбросам через взвешивание попарных расстояний уже обсуждалась выше (см. раздел «Механическая аналогия и метод главных компонент для взвешенных данных»); отдельный, более поздний подход дали Кандес, Ли, Ма и Райт<ref>''Candès E. J., Li X., Ma Y., Wright J.'', Robust principal component analysis?, Journal of the ACM, 58 (2011) 3, статья 11.</ref>, показавшие, что при определённых условиях можно точно восстановить низкоранговую составляющую матрицы данных <tex>X</tex>, даже если неизвестная, но разреженная доля её элементов повреждена сколь угодно сильно, решая выпуклую задачу '''Principal Component Pursuit''':
+: <tex>\min_{L,S}\ \|L\|_* + \lambda\|S\|_1</tex> при <tex>X=L+S,</tex>
+где <tex>\|L\|_*</tex> — ядерная норма (сумма сингулярных чисел <tex>L</tex>), выпуклая релаксация ранга, а <tex>\|S\|_1</tex> поощряет разреженность матрицы выбросов <tex>S</tex>. В отличие от взвешивания попарных расстояний, этот метод не требует заранее знать, какие именно наблюдения — выбросы, и восстанавливает их положение как часть решения задачи оптимизации.
 == Примеры использования ==
@@ Строка 235: / Строка 307: @@
 {{main|Применение метода главных компонент}}
-Метод главных компонент — наиболее популярный метод сокращения размерности во многих приложениях, в том числе в следующих областях:
+Метод главных компонент — наиболее популярный метод сокращения размерности во многих приложениях, в том числе в следующих областях:
 * Визуализация данных;
 * Компрессия изображений и видео;
@@ Строка 244: / Строка 316: @@
 * Психодиагностика;
 * Общественные науки (включая политологию);
-* Сокращение размерности динамических моделей (в том числе — в вычислительной гидродинамике).
+* Сокращение размерности динамических моделей (в том числе — в вычислительной гидродинамике).
+Два примера подробнее иллюстрируют применение метода в задачах машинного обучения и искусственного интеллекта:
+* '''Собственные лица (Eigenfaces).''' Тёрк и Пентланд<ref>''Turk M., Pentland A.'', Eigenfaces for recognition, Journal of Cognitive Neuroscience, 3 (1991) 1, 71—86.</ref> представили каждое изображение лица как точку в низкоразмерном подпространстве, натянутом на главные компоненты обучающего набора лиц («собственные лица»), а распознавание свели к сравнению координат в этом подпространстве — одна из первых успешных систем автоматического распознавания лиц и по сей день учебный эталон применения PCA в компьютерном зрении.
+* '''Матричная факторизация в рекомендательных системах.''' Метод главных компонент — частный случай факторизации матрицы данных с ограничением ортогональности факторов; более общие билинейные модели матричной факторизации, включая факторизацию методом чередующихся наименьших квадратов (ALS) для рекомендательных систем<ref>''Koren Y., Bell R., Volinsky C.'', Matrix factorization techniques for recommender systems, Computer, 42 (2009) 8, 30—37.</ref>, оптимизируются методом [[альтернированная минимизация|альтернированной минимизации]], тогда как сам PCA через сингулярное разложение можно рассматривать как точное — не итеративное — решение соответствующей билинейной задачи при дополнительном ограничении ортогональности факторов.
 == Литература ==
@@ Строка 263: / Строка 340: @@
 * ''Gorban A. N., Kegl B., Wunsch D., Zinovyev A. Y.'' (Eds.), [http://www.springer.com/west/home/math/cse?SGWID=4-10045-22-173750210-0 Principal Manifolds for Data Visualisation and Dimension Reduction], [http://www.springer.com/west/home/math/cse?SGWID=4-10045-69-173622682-0 Series: Lecture Notes in Computational Science and Engineering] 58, Springer, Berlin — Heidelberg — New York, 2008, XXIV, 340 p. 82 illus. ISBN 978-3-540-73749-0 (а также [http://pca.narod.ru/ онлайн]).
+=== Современные работы по машинному обучению ===
+* ''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.
 == Ссылки ==

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

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

Текущая версия

Содержание

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

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

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

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

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

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

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

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

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

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

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

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

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

Нормировка

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

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

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

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

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

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

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

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

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

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

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

Ядерный PCA

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

Робастный PCA

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

Литература

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

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

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

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

Ссылки

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

Примечания

Просмотры

Личные инструменты

Навигация

Поиск

Инструменты