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

Рассматриваем выборку в пространстве признаков размерности (далее везде ).

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

По теореме Пифагора,

Определение

Опр. Главными компонентами в пространстве признаков называются векторов, задающих ортонормированный базис , -мерного подпространства , такого что в нем . Такое подпространство L называется наилучшим.

Опр. Метод главных компонент (principal component analysis, PCA) - способ уменьшения количества признаков с минимальной потерей информации. В данном методе вместо изначального пространства признаков берутся признаки в наилучшем пространстве (т.е. происходит замена , — главные компоненты)

Свойства

  • Не инвариантно к сдвигу на вектор.
  • Не инвариантно к масштабированию.
DANGER! Это место вызывает
сомнения или непонимание!

Объяснить подробнее, добавить примеры

Hard

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

Липкина Аня: Вынести нормировку в отдельную статью
  • Является наилучшим линейным приближением при фиксированной размерности (теряется минимум информации). (но это не точно.)

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

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


Todo

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

Построение

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

  • берётся таким, чтобы .
  • берётся таким, чтобы .
  • берётся таким, чтобы

Построим их:

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

Лагранжиан:

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

Второе ограничение тривиально. Из первого следует, что — некоторый собственный вектор матрицы .

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

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

Лагранжиан:

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

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

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

Получаем:

и

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

Таким образом, мы получили, что .

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

Применив такие же рассуждения, как в для первой компоненты, мы получим, что — собственный вектор, соответствующий второму по величине собственному значению матрицы .

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

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

Для этого мы каждый раз домножаем на уже имеющиеся вектора , все члены, кроме члена вида занулятся (за счёт ортогональности и того, что всё это собственные вектора, смотри построение второй компоненты). И мы получим, что для всех лишних компонент. Проделав рассуждения, как для 1-ой компоненты, мы получим, что – собственный вектор, соответствующий .

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

Теорема

Пусть – линейная оболочка векторов . Тогда – наилучшее подпространство размерности для .

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

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

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

Пусть для утверждение доказано, то есть – наилучшее подпространство.

Пусть – наилучшее подпространство размерности (из определения наилучшего подпространства всегда следует его существование).

Выберем (всегда возможно) для него ортонормированный базис таким образом, что Мы можем это сделать, потому что мы можем сначала выбрать ортогональным к проекциям на . Дальше мы строим оставшиеся вектора. Эти условия нужны для того, чтобы удовлетворял ограничениям, под которыми мы оптимизируем.

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

Ничё не понятно

Hard

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

Запишем сумму квадратов норм проекций: . По предположению индукции, – наилучшее подпространство размерности , так что .

Посмотрим на то, как мы строим . Мы максимизируем норму проекции, а выше мы потребовали, что удовлетворяют таким ограничениям. Так что .

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

Источники

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

Advertisement