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

[djuuj]

Согласно Википедии, метод главных компонент находит $k$-мерное линейное многообразие $L_k$ $n$-мерного пространства, для которого сумма квадратов расстояний от данных точек $x_i$ до $L_k$ минимальна: $\sum\limits_{i=1}^m \textrm{dist}(x_i,L_k)^2\to\min$. Далее говорится, что $L_0\subset L_1\subset\ldots\subset L_{n-1}$ и описывается процедура последовательного построения $L_k$, добавляя по одному вектору в базис: в качестве $L_0$ берём среднее арифметическое $a_0$, отнимаем его от всех $x_i$, выбираем единичный вектор $a_1$, который минимизирует $\sum\limits_{i=1}^m \|x_i-(x_i,a_1)a_1\|^2$, отнимаем от всех $x_i$ проекции на $a_1$, выбираем единичный $a_2$ который минимизирует $\sum\limits_{i=1}^m \|x_i-(x_i,a_2)a_2\|^2$, и т.д.. Векторы $a_1,\ldots ,a_k$ образуют базис $L_k$ (соответствующего подпространства).
Фактически в описанном алгоритме $L_k$ строятся "жадно", выбирая на каждом шаге вектор $a_k$, фиксируя остальные. Почему полученные многообразия оптимальны в смысле минимизации $\sum\limits_{i=1}^m \textrm{dist}(x_i,L_k)^2$? Если доказать, что оптимальные $L_k$ вложены, то вроде понятно. Может это доказано в какой-то статье или книге?

[iifat]

(Оффтоп)

Вырисовывается какая-то странная картина. Вбиваем в гугла «метод главных компонент», берём первую из 384000 ссылок, попадаем по ней на русскую Википедию, читаем и бежим сюда с вопросами. Ну, если вас заинтересовал этот вопрос, поднимите пару ссылок из той же Википедии, добавьте парочку из гугла.

[Евгений Машеров]

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

[djuuj]

(Оффтоп)

Цитата:

Вырисовывается какая-то странная картина. Вбиваем в гугла «метод главных компонент», берём первую из 384000 ссылок, попадаем по ней на русскую Википедию, читаем и бежим сюда с вопросами. Ну, если вас заинтересовал этот вопрос, поднимите пару ссылок из той же Википедии, добавьте парочку из гугла.

Естественно, я почитал несколько источников, но ответа на вопрос не нашёл. Такое определение главных компонент видел только в русской википедии, в других источниках описанный алгоритм даёт главные компоненты по определению, либо определяются как собственные векторы ковариационной матрицы. В оригинальной статье результат получен для $k=1$ и $k=n-1$. Самому доказать тоже не получилось, тогда я задал вопрос здесь.

[djuuj]

Евгений Машеров в сообщении #1038285 писал(а):

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

Ну допустим уже вычли среднее $a_0$ и векторы $a_1,\ldots ,a_k$ ортонормированы, тогда $\sum\limits_{i=1}^m\textrm{dist}(x_i,L_k)^2=\sum\limits_{i=1}^m\|x_i-\sum\limits_{j=1}^k(x_i,a_j)a_j\|^2=\sum\limits_{i=1}^m\left(\|x_i\|^2-\sum\limits_{j=1}^k(x_i,a_j)^2\right)$. Тогда исходная задача эквивалентна максимизации $\sum\limits_{i=1}^m\sum\limits_{j=1}^k(x_i,a_j)^2$. Если обозначить $X$ матрицу со строками $x_i$ и $A$ матрицу со столбцами $a_j$, то требуется максимизировать $\|XA\|_F^2$ при условии ортогональности и размерности $n\times k$ матрицы $A$. Это то, что даёт Пифагор. Непонятно как дальше рассуждать.

[Евгений Машеров]

Возможно, я недооцениваю сложность и философскую глубину задачи. Но мне представляется, что в силу двух названных причин тут достаточно просто.
Мы представляем исходные переменные линейной комбинацией искомых компонент, которые принимаются ортогональными. При этом критерий квадратичен, а сумма квадратов равна сумме квадратов проекций на компоненты. То есть если мы включим m компонент, для которых проекции максимальные, мы получим самую большую сумму квадратов проекций на подпространство, натянутое на m компонент, а сумма квадратов проекций на ортогональное ему подпространство размерности (n-m) будет минимальна (поскольку сумма этих двух сумм квадратов постоянна).
Приведенный в Википедии алгоритм, с его постепенным пополнением множества компонент, не является единственным способом определения метода главных компонент. Возможно, он отражает раннюю практику применения метода, поскольку для матрицы не очень большого размера (скажем, 10х10) найти вручную собственный вектор, соответствующий максимальному собственному значению, трудоёмко, но возможно (степенным методом, скажем), затем могли "выметя" из матрицы этот с.в., найти следующий, также вручную (ну, или на арифмометре, я даже представляю себе, какие упрощающие приёмы счёта могли бы быть в инструкции для вычислителя), а больше двух компонент уже не искали.