2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему
 
 Метод главных компонент
Сообщение17.07.2015, 23:25 


06/01/10
56
Согласно Википедии, метод главных компонент находит $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$ вложены, то вроде понятно. Может это доказано в какой-то статье или книге?

 Профиль  
                  
 
 Re: Метод главных компонент
Сообщение18.07.2015, 06:35 
Заслуженный участник


16/02/13
4105
Владивосток

(Оффтоп)

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

 Профиль  
                  
 
 Re: Метод главных компонент
Сообщение18.07.2015, 10:48 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Метод главных компонент
Сообщение18.07.2015, 14:23 


06/01/10
56

(Оффтоп)

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

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

 Профиль  
                  
 
 Re: Метод главных компонент
Сообщение18.07.2015, 18:54 


06/01/10
56
Евгений Машеров в сообщении #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$. Это то, что даёт Пифагор. Непонятно как дальше рассуждать.

 Профиль  
                  
 
 Re: Метод главных компонент
Сообщение23.07.2015, 13:27 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 6 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group