Глобальная оптимальность главных компонент

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

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

$$\mathbb{D}_{total} = \mathbb{D}(z^1) + \mathbb{D}(z^2) + \dots + \mathbb{D}(z^K)$$

Для того, чтобы это показать, докажем вначале вспомогательное утверждение.

Утверждение: связь дисперсии и квадрата нормы

Для центрированных данных ($\boldsymbol{\mu} = \boldsymbol{0}$) суммарная дисперсия (total variance) вектора новых признаков $\boldsymbol{z} \in \mathbb{R}^K$ совпадает с математическим ожиданием квадрата его евклидовой нормы:

$$\mathbb{D}_{total} = \mathbb{E}[\|\boldsymbol{z}\|^2]$$

Доказательство:

Пусть $\boldsymbol{z} = (z^1, z^2, \dots, z^K)^T$ — вектор проекций объекта на первые $K$ главных компонент. По определению, суммарная дисперсия набора признаков равна сумме их индивидуальных дисперсий. Применим формулу дисперсии $\mathbb{D}(X) = \mathbb{E}[X^2] - (\mathbb{E}[X])^2$ для каждой компоненты:

$$\mathbb{D}_{total} = \sum_{i=1}^K \mathbb{D}(z^i) = \sum_{i=1}^K \left( \mathbb{E}[(z^i)^2] - (\mathbb{E}[z^i])^2 \right)$$

Поскольку ранее было доказано, что для центрированных исходных данных математическое ожидание каждой проекции $\mathbb{E}[z^i] = 0$, то второе слагаемое в каждой скобке обращается в ноль. Тогда выражение упрощается, и, воспользовавшись линейностью математического ожидания, получим:

$$\mathbb{D}_{total} = \sum_{i=1}^K \mathbb{E}[(z^i)^2] = \mathbb{E}\left[ \sum_{i=1}^K (z^i)^2 \right] = \mathbb{E}[\|\boldsymbol{z}\|^2]$$

$\square$

Геометрический смысл

Это равенство означает, что суммарный разброс данных в методе PCA совпадает со средним квадратом расстояний от спроецированных точек до начала координат в подпространстве $V_K$, являющимся линейной оболочкой первых $K$ главных компонент.

Утверждение: оптимальность подпространства

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

$$\mathbb{D}_{total} = \mathbb{E}[\|\boldsymbol{z}\|^2] = \sum_{i=1}^K \lambda_i$$

Доказательство:

Пусть $\{\boldsymbol{u}_i\}_{i=1}^K$ — произвольный ортонормированный базис некоторого $K$-мерного подпространства $U$. Как мы выше показывали, дисперсия проекций на отдельный вектор $\boldsymbol{u}_i$ равна $\boldsymbol{u}_i^T \Sigma \boldsymbol{u}_i$, следовательно суммарная дисперсия проекций на это подпространство равна:

$$\mathbb{D}_{total}(U) = \sum_{i=1}^K \boldsymbol{u}_i^T \Sigma \boldsymbol{u}_i$$

Воспользуемся спектральным разложением ковариационной матрицы $\Sigma = \sum_{j=1}^D \lambda_j \boldsymbol{v}_j \boldsymbol{v}_j^T$, где $\boldsymbol{v}_j$ — её собственные векторы, а $\lambda_1 \ge \lambda_2 \ge \dots \ge \lambda_D$ — упорядоченные собственные числа. Подставим это разложение в формулу дисперсии:

$$\mathbb{D}_{total}(U) = \sum_{i=1}^K \boldsymbol{u}_i^T \left( \sum_{j=1}^D \lambda_j \boldsymbol{v}_j \boldsymbol{v}_j^T \right) \boldsymbol{u}_i$$ $$= \sum_{i=1}^K \sum_{j=1}^D \lambda_j (\boldsymbol{u}_i^T \boldsymbol{v}_j)^2 = \sum_{j=1}^D \lambda_j \left( \sum_{i=1}^K (\boldsymbol{u}_i^T \boldsymbol{v}_j)^2 \right) = \sum_{j=1}^D \lambda_jc_j,$$

где мы использовали обозначение $c_j = \sum_{i=1}^K (\boldsymbol{u}_i^T \boldsymbol{v}_j)^2$.

Заметим, что $c_j$ представляет собой квадрат длины проекции единичного вектора $\boldsymbol{v}_j$ на подпространство $U$, следовательно, $0 \le c_j \le 1$. Кроме того, сумма всех $c_j$ (по всем главным компонентам) равна:

$$\sum_{j=1}^D c_j = \sum_{j=1}^D\sum_{i=1}^K (\boldsymbol{u}_i^T \boldsymbol{v}_j)^2 = \sum_{i=1}^K \sum_{j=1}^D (\boldsymbol{u}_i^T \boldsymbol{v}_j)^2 = \sum_{i=1}^K \|\boldsymbol{u}_i\|^2 = K$$

Задача максимизации $\sum_{j=1}^D \lambda_j c_j$ при условиях $0 \le c_j \le 1$ и $\sum c_j = K$ решается выбором максимально возможных весов для самых больших коэффициентов $\lambda_j$. Поскольку собственные числа упорядочены:

$$\lambda_1\ge\lambda_2\ge...\lambda_D \ge 0,$$

необходимо положить $c_1 = c_2 = \dots = c_K = 1$ и $c_{K+1} = \dots = c_D = 0$.

Это достигается тогда и только тогда, когда подпространство $U$ совпадает с подпространством, натянутым на собственные векторы $\boldsymbol{v}_1, \dots, \boldsymbol{v}_K$. В этом случае суммарная дисперсия принимает значение $\sum_{i=1}^K \lambda_i$.

Ранее было доказано, что для центрированных данных дисперсия каждой компоненты совпадает с математическим ожиданием квадрата её значения, $\mathbb{D}(z^i) = \mathbb{E}[(z^i)^2]$, откуда:

$$\mathbb{D}_{total} = \sum_{i=1}^K \mathbb{E}[(z^i)^2] = \mathbb{E}\left[ \sum_{i=1}^K (z^i)^2 \right] = \mathbb{E}[\|\boldsymbol{z}\|^2]$$

$\square$

Пусть подпространство $V$ задано ортонормированным базисом $\{\boldsymbol{v}_i\}_{i=1}^K$, а вектор $\hat{\boldsymbol{x}} = \sum_{i=1}^K z^i \boldsymbol{v}_i$ является проекцией вектора $\boldsymbol{x}$ на это подпространство. Как мы выяснили $K$-мерное подпространство, образованное первыми $K$ главными компонентами, оптимально в терминах максимизации нормы координат $\boldsymbol{z}$:

$$\boldsymbol{v}_{1}, \dots, \boldsymbol{v}_{K} = \arg \max_{\{\boldsymbol{v}_i\}_{i=1}^K : \boldsymbol{v}_i^T \boldsymbol{v}_j = \mathbb{I}\{i=j\}} \mathbb{E}[\|\boldsymbol{z}\|^2]$$

Оказывается, оно оптимально и в терминах максимизации нормы самих проекций $\hat{\boldsymbol{x}}$ на подпространство $V$:

$$\boldsymbol{v}_{1}, \dots, \boldsymbol{v}_{K} = \arg \max_{\{\boldsymbol{v}_i\}_{i=1}^K : \boldsymbol{v}_i^T \boldsymbol{v}_j = \mathbb{I}\{i=j\}} \mathbb{E}[\|\hat{\boldsymbol{x}}\|^2]$$

Это следует из следующего утверждения:

Утверждение: сохранение нормы при проектировании

$$\|\hat{\boldsymbol{x}}\|^2 = \|\boldsymbol{z}\|^2$$

Доказательство:

Распишем квадрат евклидовой нормы вектора $\hat{\boldsymbol{x}}$ через скалярное произведение вектора самого на себя:

$$\|\hat{\boldsymbol{x}}\|^2 = \hat{\boldsymbol{x}}^T \hat{\boldsymbol{x}} = \left( \sum_{i=1}^K z^i \boldsymbol{v}_i \right)^T \left( \sum_{j=1}^K z^j \boldsymbol{v}_j \right)$$

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

$$\|\hat{\boldsymbol{x}}\|^2 = \sum_{i=1}^K \sum_{j=1}^K z^i z^j (\boldsymbol{v}_i^T \boldsymbol{v}_j)$$

Поскольку базис $\{\boldsymbol{v}_i\}$ является ортонормированным, $\boldsymbol{v}_i^T \boldsymbol{v}_j = \mathbb{I}\{i=j\}$, следовательно

$$\|\hat{\boldsymbol{x}}\|^2 = \sum_{i=1}^K (z^i)^2 = \|\boldsymbol{z}\|^2$$

$\square$

Интерпретация

Таким образом, метод главных компонент находит наилучшее сжатие данных: среди всех способов линейно спроецировать объекты в $K$-мерное подпространство, именно PCA сохраняет наибольший объем «информации», выраженной через суммарный разброс точек.

Оптимальность ожидаемого квадрата ошибки аппроксимации

Пусть подпространство $V$ задано ортонормированным базисом $\{\boldsymbol{v}_i\}_{i=1}^K$. Для любого центрированного вектора объекта $\boldsymbol{x}$ его можно представить в виде суммы двух составляющих:

$$\boldsymbol{x} = \hat{\boldsymbol{x}} + \boldsymbol{h}$$

Здесь $\hat{\boldsymbol{x}} = \sum_{i=1}^K (\boldsymbol{v}_i^T \boldsymbol{x}) \boldsymbol{v}_i$ — ортогональная проекция вектора на подпространство $V$, а $\boldsymbol{h}$ — ошибка аппроксимации (approximation error), которая является ортогональным дополнением к проекции.

Утверждение: минимизация ошибки реконструкции

Среди всех линейных проекций в $K$-мерное подпространство именно PCA минимизирует математическое ожидание квадрата ошибки аппроксимации $\mathbb{E}[\|\boldsymbol{h}\|^2]$.

Доказательство:

Распишем квадрат евклидовой нормы вектора $\boldsymbol{x}$ через скалярное произведение вектора на самого себя:

$$\|\boldsymbol{x}\|^2 = (\hat{\boldsymbol{x}} + \boldsymbol{h})^T (\hat{\boldsymbol{x}} + \boldsymbol{h})$$

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

$$\|\boldsymbol{x}\|^2 = \hat{\boldsymbol{x}}^T \hat{\boldsymbol{x}} + \hat{\boldsymbol{x}}^T \boldsymbol{h} + \boldsymbol{h}^T \hat{\boldsymbol{x}} + \boldsymbol{h}^T \boldsymbol{h}$$

По определению ортогональной проекции вектор ошибки $\boldsymbol{h}$ перпендикулярен подпространству $V$, а значит, он перпендикулярен любому вектору из этого подпространства, включая саму проекцию $\hat{\boldsymbol{x}}$. Следовательно, скалярное произведение $\hat{\boldsymbol{x}}^T \boldsymbol{h} = 0$:

$$\|\boldsymbol{x}\|^2 = \|\hat{\boldsymbol{x}}\|^2 + 0 + 0 + \|\boldsymbol{h}\|^2 = \|\hat{\boldsymbol{x}}\|^2 + \|\boldsymbol{h}\|^2$$

Применим оператор математического ожидания к обеим частям равенства:

$$\mathbb{E}[\|\boldsymbol{x}\|^2] = \mathbb{E}[\|\hat{\boldsymbol{x}}\|^2] + \mathbb{E}[\|\boldsymbol{h}\|^2]$$

Выразим математическое ожидание квадрата ошибки:

$$\mathbb{E}[\|\boldsymbol{h}\|^2] = \mathbb{E}[\|\boldsymbol{x}\|^2] - \mathbb{E}[\|\hat{\boldsymbol{x}}\|^2]$$

Величина $\mathbb{E}[\|\boldsymbol{x}\|^2]$ (полная дисперсия данных) не зависит от выбора подпространства и является постоянной для данной выборки. Таким образом, достижение минимума ошибки $\mathbb{E}[\|\boldsymbol{h}\|^2]$ эквивалентно достижению максимальной дисперсии проекций $\mathbb{E}[\|\hat{\boldsymbol{x}}\|^2]$. Как было доказано ранее, эта величина достигает максимума, когда базис подпространства образован первыми $K$ главными компонентами.

$\square$