Метод главных компонент (Principal component analysis)

Это незавершённая статья Автор, вероятно, переобучился и отправился спать. Вы можете помочь, экстраполировав местную информацию.

Рассматриваем выборку $x_{i},~i=1,\dots ,N$в пространстве признаков размерности $K$ (далее везде $k\leqslant K$).

Пусть $L$ - некоторое подпространство пространства признаков. Для объекта $x_{i}$ введем разложение $x_{i}=p_{i}+h_{i}$, где $p_{i}\in L$, а $h_{i}$ ортогонально $L$.

По теореме Пифагора, $||x_{i}||^{2}=||p_{i}||^{2}+||h_{i}||^{2}$

Определение

Опр. Главными компонентами в пространстве признаков называются $k$ векторов, задающих ортонормированный базис $e_{1},e_{2},\dots ,e_{k}$, $k$-мерного подпространства $L$, такого что в нем $\sum _{i=1}^{N}||h_{i}||^{2}\rightarrow min$ (или $\sum _{i=1}^{N}||p_{i}||^{2}\rightarrow max$). Такое подпространство L называется наилучшим.

Опр. Метод главных компонент (principal component analysis, PCA) - способ уменьшения количества признаков с минимальной потерей информации. В данном методе вместо изначального пространства признаков берутся признаки в наилучшем пространстве (т.е. происходит замена $x_{i}\leftrightarrow x_{i}',~x_{i}'=(x_{1}^{i},x_{2}^{i},\dots ,x_{k}^{i}),~x_{j}^{i}=(x_{i},e_{j}),~j=1,\dots ,k,~i=1,\dots ,N$, $e_{j}$ — главные компоненты)

Свойства

• Не инвариантно к сдвигу на вектор.
• Не инвариантно к масштабированию.

DANGER! Это место вызывает сомнения или непонимание! Объяснить подробнее, добавить примеры

Как следствие перед поиском главных компонент необходимо выполнить нормировку (вычесть матожидание, разделить на дисперсию) объектов.

Липкина Аня: Вынести нормировку в отдельную статью

• Является наилучшим линейным приближением при фиксированной размерности (теряется минимум информации). ^{(но это не точно.)}

см. также Сингулярное разложение.

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

Китов (слайд 15): какая связь PCA с регрессией с минимизацией квадратов?

Построение

DANGER! Это место вызывает сомнения или непонимание! Неочевидна связь $||Xe_{1}||$ и максимизации квадратов длин проекций

Итеративно строится система ортонормированных векторов, построение происходит с помощью метода множителей Лагранжа. Пусть $X$ — выборка, а $e_{1},...e_{k}$ — искомая система.

• $e_{1}$ берётся таким, чтобы $||Xe_{1}||\rightarrow max~s.t.~\langle e_{1},e_{1}\rangle =1$.
• $e_{2}$ берётся таким, чтобы $||Xe_{2}||\rightarrow max~s.t.~\langle e_{2},e_{2}\rangle =1,~\langle e_{1},e_{2}\rangle =0$.
• $e_{3}$ берётся таким, чтобы $||Xe_{3}||\rightarrow max~s.t.~\langle e_{3},e_{3}\rangle =1,~\langle e_{1},e_{3}\rangle =0,~\langle e_{2},e_{3}\rangle =0$

Построим их:

Первая компонента

${\begin{cases}||Xe_{1}||^{2}\rightarrow {\underset {e_{1}}{\max }}\\||e_{1}||^{2}=1\end{cases}}$

Лагранжиан:

${\mathcal {L}}(e_{1},\mu )=e_{1}^{T}X^{T}Xe_{1}-\mu (e_{1}^{T}e_{1}-1)\rightarrow {\underset {e_{1},\mu }{\max }}$

Получим производные: ${\frac {\partial {\mathcal {L}}}{\partial e_{1}}}=2X^{T}Xe_{1}-2\mu e_{1}=0;{\frac {\partial {\mathcal {L}}}{\partial \mu }}=1-e_{1}^{T}e_{1}=0$

Второе ограничение тривиально. Из первого следует, что $e_{1}$ — некоторый собственный вектор матрицы $X^{T}X$.

Воспользуемся нормализованностью вектора и тем, что это собственный вектор: $||Xe_{1}||^{2}=e_{1}^{T}X^{T}Xe_{1}=e_{1}^{T}(X^{T}X)e_{1}=e_{1}^{T}\lambda e_{1}=\lambda \times 1=\lambda$, а мы и максимизируем эту величину. То есть получаем, что $e_{1}$ надо взять одним из собственных векторов, соответствующих максимальному собственному значению матрицы $X^{T}X$. Вектор должен соответствовать ограничению на норму: $||e_{1}||^{2}=1$.

Вторая компонента

${\begin{cases}||Xe_{2}||^{2}\rightarrow {\underset {e_{2}}{\max }}\\||e_{2}||^{2}=1\\\langle e_{2},e_{1}\rangle =0\end{cases}}$

Лагранжиан:

${\mathcal {L}}(e_{2},\mu ,\alpha )=e_{2}^{T}X^{T}Xe_{2}-\mu (e_{2}^{T}e_{2}-1)-\alpha e_{2}^{T}e_{1}\rightarrow {\underset {e_{2},\mu ,\alpha }{\max }}$

Получим производные:

${\frac {\partial {\mathcal {L}}}{\partial e_{2}}}=2X^{T}Xe_{2}-2\mu e_{2}-\alpha e_{1}=0;{\frac {\partial {\mathcal {L}}}{\partial \mu }}=1-e_{2}^{T}e_{2}=0;{\frac {\partial {\mathcal {L}}}{\partial \alpha }}=-e_{1}^{T}e_{2}=0$

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

Мы бы хотели упростить первое уравнение, чтобы как-нибудь хорошо учесть $e_{1}$. Для этого домножим это выражение на $e_{1}^{T}$ слева:

$e_{1}^{T}{\frac {\partial {\mathcal {L}}}{\partial e_{2}}}=2e_{1}^{T}X^{T}Xe_{2}-2\mu e_{1}^{T}e_{2}-\alpha e_{1}^{T}e_{1}=0$

Получаем:

$\alpha e_{1}^{T}e_{1}=\alpha$ и $2\mu e_{1}^{T}e_{2}=0$

Можно убедиться по размерностям, что $e_{1}^{T}X^{T}Xe_{2}$ — скаляр. Мы можем его транспонировать и воспользоваться тем, что это собственный вектор, а также условием ортогональности:

$(e_{1}^{T}X^{T}Xe_{2})^{T}=e_{2}^{T}X^{T}Xe_{1}=e_{2}^{T}\lambda e_{1}=\lambda e_{2}^{T}e_{1}=0$

Таким образом, мы получили, что $e_{1}^{T}{\frac {\partial {\mathcal {L}}}{\partial e_{2}}}=0+0-\alpha =0$.

Следовательно, ограничение упрощается:

${\frac {\partial {\mathcal {L}}}{\partial e_{2}}}=2X^{T}Xe_{2}-2\mu e_{2}=0$

Применив такие же рассуждения, как в для первой компоненты, мы получим, что $e_{2}$ — собственный вектор, соответствующий второму по величине собственному значению матрицы $X^{T}X$.

k-я компонента

Для неё мы поступаем точно так же — записываем лагранжиан и избавляемся от неудобных членов в производной.

Для этого мы каждый раз домножаем на уже имеющиеся вектора $e_{i},i=\{1,\dots ,k-1\}$, все члены, кроме члена вида $\alpha _{i}e_{i}^{T}e_{i}=\alpha _{i}$ занулятся (за счёт ортогональности и того, что всё это собственные вектора, смотри построение второй компоненты). И мы получим, что $\alpha _{i}=0$ для всех лишних компонент. Проделав рассуждения, как для 1-ой компоненты, мы получим, что $e_{k}$ – собственный вектор, соответствующий $\lambda _{k}$.

Доказательство корректности построения

Теорема

Пусть ${\mathcal {L}}_{k}$ – линейная оболочка векторов $e_{1},...e_{k}$. Тогда $\forall k\in \{1,\dots ,D\}:$(*откуда D? что это за D?) ${\mathcal {L}}_{k}$ – наилучшее подпространство размерности $k$ для $X$.

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

Доказательство по индукции.

Для $k=1$ утверждение верно, так как максимизация проекции эквивалентна минимизации расстояния (если проекция ортогональная).

Пусть для $k-1$ утверждение доказано, то есть ${\mathcal {L}}_{k-1}$ – наилучшее подпространство.

Пусть ${\mathcal {L}}_{k}$ – наилучшее подпространство размерности $k$ (из определения наилучшего подпространства всегда следует его существование).

Выберем (всегда возможно) для него ортонормированный базис $b_{1},\dots ,b_{k}$ таким образом, что ${\begin{cases}||b_{k}||=1\\\langle b_{k},e_{i}\rangle =0~\forall i\in \{1,\dots ,k-1\}\end{cases}}$

Мы можем это сделать, потому что мы можем сначала выбрать $b_{k}$ ортогональным к проекциям $e_{1},\dots ,e_{k-1}$ на ${\mathcal {L}}_{k}$. Дальше мы строим оставшиеся вектора. Эти условия нужны для того, чтобы $b_{k}$ удовлетворял ограничениям, под которыми мы оптимизируем.

DANGER! Это место вызывает сомнения или непонимание! Ничё не понятно

Мне не очень нравится это ограничение на b.

Запишем сумму квадратов норм проекций: $||Xb_{1}||^{2}+...+||Xb_{k}||^{2}$. По предположению индукции, ${\mathcal {L}}_{k-1}$ – наилучшее подпространство размерности $k-1$, так что $||Xb_{1}||^{2}+...+||Xb_{k-1}||^{2}\leq ||Xe_{1}||^{2}+...+||Xe_{k-1}||^{2}$.

Посмотрим на то, как мы строим $e_{k}$. Мы максимизируем норму проекции, а выше мы потребовали, что $b_{1},\dots ,b_{k-1}$удовлетворяют таким ограничениям. Так что $||Xb_{k}||^{2}\leq ||Xe_{k}||^{2}$.

Таким образом, утверждение доказано, а это и есть корректность построения.

Источники

http://www.machinelearning.ru/wiki/images/1/1a/Kitov-ML-eng-03-PCA.pdf (слайды 12 – 14)