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

Новые признаки как проекции

В машинном обучении мы привыкли работать с исходными признаками объекта $\boldsymbol{x} = (x^1, x^2, \dots, x^D)^T$. Однако часто гораздо полезнее рассматривать не сами значения признаков, а их линейные комбинации. Любую такую комбинацию можно представить как скалярное произведение вектора объекта $\boldsymbol{x}$ на некоторый вектор весов $\boldsymbol{v}$:

$$z = \sum_{i=1}^D v^i x^i = \langle \boldsymbol{x}, \boldsymbol{v} \rangle = \boldsymbol{v}^T \boldsymbol{x}$$

Рассмотрим примеры того, как линейные комбинации позволяют извлекать смысл из данных:

1. Средняя оценка: Если $\boldsymbol{x} = [5, 4, 3, 5, 4]$ - оценки студента по 5 предметам, а $\boldsymbol{v} = [1/5, 1/5, 1/5, 1/5, 1/5]^T$, то $z=\boldsymbol{v}^T \boldsymbol{x}$ равен его среднему баллу.

2. Разница стоимостей: Если $\boldsymbol{x} = [p_{today}, p_{yesterday}]$ - цены акции, а $\boldsymbol{v} = [1, -1]^T$, то $z$ характеризует суточное изменение цены.

3. Суммарная активность: Если $\boldsymbol{x}$ - количество действий пользователя в разные часы суток, скалярное произведение его на $\boldsymbol{v} = [1,1,...1]$ покажет общее количество действий за сутки.

4. Цветовой баланс: В обработке изображений проекция RGB-вектора на $[0.299, 0.587, 0.114]^T$ позволяет перевести цветной пиксель в яркость (оттенки серого).

Если мы ограничим вектор $\boldsymbol{v}$ условием единичной нормы ($\|\boldsymbol{v}\|=1$), то значение проекции $\boldsymbol{x}$ на $\boldsymbol{v}$ можно находить как скалярное произведение:

$$z = \boldsymbol{x}^T \boldsymbol{v} = \langle \boldsymbol{x}, \boldsymbol{v}\rangle$$

Почему так?

Скалярное произведение двух векторов $\boldsymbol{x}$ и $\boldsymbol{v}$ можно выразить через их длины и косинус угла $\theta$ между ними:

$$z = \langle \boldsymbol{x}, \boldsymbol{v} \rangle = \|\boldsymbol{x}\| \cdot \|\boldsymbol{v}\| \cdot \cos \theta$$

Если мы наложим условие единичной нормы $\|\boldsymbol{v}\| = 1$, формула упрощается:

$$z = \|\boldsymbol{x}\| \cdot \cos \theta$$

Последнее выражение как раз и равно длине проекции (со знаком, в зависимости от сонаправленности векторов).

Возникает вопрос: какие именно вектора $\boldsymbol{v}$ обеспечивают максимальное сохранение информации об исходных данных?

Метод главных компонент (principal component analysis, PCA [1]) решает эту задачу, предлагая последовательно находить направления, вдоль которых данные сохраняют наибольшую изменчивость.

Определение и свойства

Индивидуально каждая $k$-я главная компонента (principal component) определяется как направление $\boldsymbol{v}_k$, которое обеспечивает максимальную дисперсию проекций данных на него при условии, что этот вектор ортогонален всем ранее найденным компонентам $\boldsymbol{v}_1, \dots, \boldsymbol{v}_{k-1}$.

Линейная оболочка первых $K$ главных компонент образует $K$-мерное подпространство наилучшей аппроксимации. Оно является оптимальным в глобальном смысле: среди всех возможных подпространств размерности $K$ именно это подпространство лучше всего описывает структуру исходных данных:

• максимизируя средний квадрат длин проекций объектов $\boldsymbol{x}_1,...\boldsymbol{x}_N$ на это подпространство;

• минимизируя средний квадрат длин ошибок аппроксимации исходных объектов их проекциями.

Метод порождает новое признаковое описание объектов в виде длин проекций объекта на первые $K$ главных компонент, компактно и информативно описывающих исходные данные:

$$\boldsymbol{x}=[x^1,...x^D]\to [z^1,...z^K]$$ $$\boldsymbol{x}=\sum_{k=1}^K z^k \boldsymbol{v}_k$$

Как будет доказано далее, новые признаки обладают удобными свойствами:

• они являются нескоррелированными;
• вектора значений каждого признака линейно независимы, если ранг матрицы признаков не ниже $K$: $\text{rg} X\ge K$.

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

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

Как будет показано в следующей главе, главные компоненты представляют собой собственные векторы $\boldsymbol{v}_1, \dots, \boldsymbol{v}_D$ ковариационной матрицы признаков $\Sigma$, где признаки предварительно центрируются относительно их средних значений. При этом каждое соответствующее собственное значение (eigenvalue) $\lambda_k$ характеризует величину дисперсии (информативности), сосредоточенной вдоль соответствующей компоненты $\boldsymbol{v}_k$.

Алгоритм применения

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

1. Центрирование данных:

$$\boldsymbol{x}_n \leftarrow \boldsymbol{x}_n - \boldsymbol{\mu}$$ $$\boldsymbol{\mu} = \frac{1}{N} \sum_{n=1}^N \boldsymbol{x}_n$$

2. Вычисление ковариационной матрицы $\Sigma$ (которая будет вещественной и симметричной) и её спектральное разложение [2]:

$$\Sigma = \frac{1}{N} \sum_{n=1}^N \boldsymbol{x}_n \boldsymbol{x}_n^T = V \Lambda V^T$$ $$\Lambda = \text{Diag}\{\lambda_1,...\lambda_D\}$$

3. Переход к новым признакам:

$$\boldsymbol{z}_n = V_K^T \boldsymbol{x}_n$$

где $V_K=[\boldsymbol{v}_1,...\boldsymbol{v}_K]\in\mathbb{R}^{D\times K}$ - матрица, составленная из первых $K$ столбцов матрицы собственных векторов $V=[\boldsymbol{v}_1,...\boldsymbol{v}_D]\in\mathbb{R}^{D\times D}$, отвечающих максимальным собственным значениям $\lambda_1\ge\lambda_2\ge...\lambda_K$. Вектора $\boldsymbol{v}_1,...\boldsymbol{v}_K$ и будут первыми $K$ главными компонентами.

При этом собственные значения $\lambda_1,\lambda_2,...\lambda_K$ описывают количество информации, которое соответствующие компоненты $\boldsymbol{v}_1,\boldsymbol{v}_2,...\boldsymbol{v}_K$ по отдельности описывают в исходных данных.

Аппроксимации в исходном признаковом пространстве

Если требуется получить вектор аппроксимации $\hat{\boldsymbol{x}}_n$, извлекаемый по первым $K$ главным компонентам исходного вектора $\boldsymbol{x}_n$, это можно сделать, вернувшись из базиса главных компонент в исходное признаковое пространство по следующей формуле:

$$\hat{\boldsymbol{x}}_n = \boldsymbol{\mu} + V_K \boldsymbol{z}_n = \boldsymbol{\mu} + \sum_{i=1}^K z_n^i \boldsymbol{v}_i$$

Это может быть полезным, например, для в задачах фильтрации данных от шума:

1. данные представляются в компактном маломерном пространстве

2. данные восстанавливаются по этому сжатому представлению

Очевидно, при таком преобразовании будут восстановлены лишь самые основные зависимости, а шум - отфильтрован.

Применение метода на практике

Метод главных компонент (principal component analysis, PCA) находит широкое применение в анализе данных, когда необходимо упростить структуру признакового пространства, максимально сохранив при этом исходную информацию.

Рассмотрим основные способы его использования:

1. Визуализация данных: При $K=2$ или $K=3$ многомерные объекты можно отобразить на плоскости или в пространстве. Это позволяет визуализировать многомерные данные, увидеть на них кластерную структуру, аномалии и общие закономерности.

   При решении задачи классификации информативно отображать полученные точки разными цветами, отвечающими разным классам.

2. Сжатие данных: Метод позволяет хранить основную информацию о многомерных объектах, используя небольшое число признаков.

   Например, в методе Eigenfaces [3] изображения человеческих лиц компактно представляются в виде линейной комбинации небольшого числа "эталонных" лиц наподобие того, как детальный фоторобот лица составляется всего по нескольким характеристикам.

3. Фильтрация шума (noise filtering): Если предположить, что компоненты с очень малыми собственными числами $\lambda_i$ описывают лишь случайные флуктуации в данных, то представляя объекты как комбинацию только первых самых значимых главных компонент мы получим версии объектов, очищенные от шума.

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

5. Компактное информативное описание: Вместо исходного многомерного описания данных, которое часто бывает избыточным, метод генерирует компактное информативное описание данных, которое легче обрабатывать последующими алгоритмами. При этом, настраивая число используемых компонент $K$, можно эффективно управлять степенью переобучения модели: уменьшение $K$ снижает эффективную сложность модели, ограничивая её способность "подстраиваться" под шум в данных.

Предварительная подготовка признаков

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

Это важно по следующим причинам:

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

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

Вычислительная сложность

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

Сложность нахождения всех собственных векторов и собственных чисел матрицы размера $D \times D$ равна $O(D^3)$.

Главные компоненты можно также найти из сингулярного разложения (singular value decomposition, SVD [4]) матрицы данных $X$.

На практике нас чаще всего интересует не полное разложение, а нахождение только первых $K$ главных компонент. В этом случае их можно вычислить существенно быстрее с использованием степенного метода (power method) .

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

Для оценки информативности выбранных направлений (компонент) и определения их оптимального количества $K$ используют два ключевых показателя: индивидуальную и накопленную доли объяснённой дисперсии.

Доля объяснённой дисперсии

Доля объяснённой дисперсии (Explained Variance Ratio, EVR) для $k$-й компоненты показывает, какую часть суммарного разброса (изменчивости) данных описывает именно это направление:

$$EVR_k = \frac{\lambda_k}{\sum_{j=1}^D \lambda_j}$$

На практике строят график зависимости доли объяснённой дисперсии от номера компоненты, по которому подбирают, какое число главных компонент использовать. Для этого отбрасываются все компоненты, у которых доля объяснённой дисперсии оказалась ниже порога.

Накопленная доля объяснённой дисперсии

Накопленная доля объяснённой дисперсии (Cumulative Explained Variance Ratio, CEVR) характеризует суммарную информативность первых $K$ выбранных главных компонент:

$$CEVR_K = \frac{\sum_{i=1}^K \lambda_i}{\sum_{j=1}^D \lambda_j}$$

Данная величина монотонно возрастает с увеличением $K$ и достигает 1, когда число компонент становится равным исходной размерности признакового пространства $D$.

Эта величина также используется для подбора числа главных компонент: задают порог (обычно 0.9, 0.95 или 0.99), а далее выбирают минимальное число первых $K$ главных компонент, которые сохраняют заданную долю объяснённой дисперсии.

В последующих главах будут

• аналитически выведены главные компоненты;

• доказаны свойства проекций на главные компоненты;

• показана глобальная оптимальность первых $K$ главных компонент.

Поскольку данные описываются конечной выборкой объектов $\boldsymbol{x}_1,\boldsymbol{x}_2,...\boldsymbol{x}_N$, то операции математического ожидания и дисперсии в этих главах следует понимать в конечном пространстве исходов этой выборки, т.е. как выборочное среднее и выборочную дисперсию.

Литература

1. Pearson K. LIII. On lines and planes of closest fit to systems of points in space //The London, Edinburgh, and Dublin philosophical magazine and journal of science. – 1901. – Т. 2. – №. 11. – С. 559-572.
2. Википедия: спектральное разложение матрицы.
3. Wikipedia: Eigenface.
4. Wikipedia: Singular value decomposition.