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

Рассмотрим конечную выборку наблюдений $\boldsymbol{x}_1,\boldsymbol{x}_2,...\boldsymbol{x}_N$ и произвольную ортонормированную систему векторов $\{\boldsymbol{u}_i\}_{i=1}^K$.

Проекцию объекта $\boldsymbol{x}$ на $i$-й вектор будем обозначать как $z^i$:

$$z^i = \boldsymbol{u}_i^T \boldsymbol{x}$$

Проекцию $n$-го объекта $\boldsymbol{x}_n$ на $i$-й вектор будем обозначать как $z^i_n$:

$$z^i_n = \boldsymbol{u}_i^T \boldsymbol{x}_n$$

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

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

Поскольку данные и проекции центрированы в нуле, то для $i=1,2,...K$:

$$\mathbb{D}\{z^i\} = \mathbb{E}\{(z^i)^2\} - \left(\mathbb{E}\{(z^i)^2\}\right)^2=\mathbb{E}\{(z^i)^2\}$$

Пусть подпространство $U=\mathcal{L}(\boldsymbol{u}_1,\boldsymbol{u}_2,...\boldsymbol{u}_K)$ задано ортонормированным базисом $\{\boldsymbol{u}_i\}_{i=1}^K$. Для любого центрированного вектора объекта $\boldsymbol{x}$ его можно представить в виде суммы двух составляющих:

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

где

• $\hat{\boldsymbol{x}} = \sum_{i=1}^K (\boldsymbol{u}_i^T \boldsymbol{x}) \boldsymbol{u}_i = \sum_{i=1}^K z^i \boldsymbol{u}_i$ — векторная проекция $\boldsymbol{x}$ на подпространство $U$ (по смыслу - аппроксимация $\boldsymbol{x}$ в $K$-мерном подпространстве $U$)

• $\boldsymbol{h}$ — ортогональное дополнение к проекции (ошибка аппроксимации).

Введём понятие суммарной дисперсии проекций.

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

Утверждение 1:

Cуммарная дисперсия будет совпадать со средним квадратом длин векторов-апроксимаций.

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

$$\begin{align*} \mathbb{D}_{total} &= \mathbb{D}\{z^1\} + \mathbb{D}\{z^2\} + \dots + \mathbb{D}\{z^K\} \\ &= \mathbb{E}\{(z^1)^2\} + \mathbb{E}\{(z^2)^2\} + \dots + \mathbb{E}\{(z^K)^2\} \\ &=\frac{1}{N}\sum_{n=1}^N (z^1_n)^2 + \frac{1}{N}\sum_{n=1}^N (z^2_n)^2 + \dots \frac{1}{N}\sum_{n=1}^N (z^K_n)^2 \\ &=\frac{1}{N}\sum_{n=1}^N \left( (z^1_n)^2 + (z^2_n)^2 + \dots (z^K_n)^2 \right) =\frac{1}{N}\sum_{n=1}^N \|\boldsymbol{z}_n\|^2 \\ &=\frac{1}{N}\sum_{n=1}^N \|\hat{\boldsymbol{x}}_n\|^2 = \mathbb{E}\{\|\hat{\boldsymbol{x}}\|^2\} \end{align*}$$

$\square$

В процессе доказательства мы воспользовались следующим свойством:

Утверждение 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{u}_i \right)^T \left( \sum_{j=1}^K z^j \boldsymbol{u}_j \right)$$

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

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

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

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

$\square$

Геометрический смысл утверждения 1.

Равенство в утверждении 1 означает, что суммарный разброс проекций совпадает со средним квадратом расстояний от спроецированных точек до начала координат в подпространстве $U$, являющимся линейной оболочкой $\{\boldsymbol{u}_i\}_{i=1}^K$.

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

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

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

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

$$\mathbb{D}_{total} = \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_j c_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$.

Это достигается, когда

$$\begin{align*} \boldsymbol{u}_1 &= \boldsymbol{v}_1\\ \boldsymbol{u}_2 &= \boldsymbol{v}_2\\ &\cdots \\ \boldsymbol{u}_K &= \boldsymbol{v}_K\\ \end{align*}$$

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

$$\mathbb{D}_{total}(U) = \sum_{j=1}^D \lambda_j c_j=\sum_{i=1}^K \lambda_i$$

$\square$

Из утверждения 3 следует, что подпространство $V=\mathcal{L}(\boldsymbol{v}_1,\boldsymbol{v}_2,...\boldsymbol{v}_K)$ (линейная оболочка первых $K$ главных компонент) является оптимальным в том смысле, что суммарный квадрат аппроксимаций исходных данных максимизируется при проецировании именно на такое $K$-мерное подпространство.

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

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

Оказывается, что подпространство $V$ будет оптимальным и в том смысле, что именно оно минимизирует средний квадрат ошибок аппроксимации. Это следует из следующего утверждения:

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

Среди всех линейных проекций в $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}[\|\hat{\boldsymbol{x}}\|^2]$ максимизируется при проецировании именно на $K$ первых главных компонент.

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

$\square$