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

Проклятие размерности
Ричард Эрнест Бе́ллман (26 августа 1920, Нью-Йорк, США — 19 марта 1984, Лос-Анджелес, США) — американский математик, один из ведущих специалистов в области математики и вычислительной техники. Ввел термин «проклятие размерности» в 1961 году.

Пример проклятия размерности
Рассмотрим единичный интервал [0,1]. 100 равномерно разбросанных точек будет достаточно, чтобы покрыть этот интервал с частотой не менее 0,01.
Теперь рассмотрим 10-мерный куб. Для достижения той же степени покрытия потребуется уже 1020 точек. То есть, по сравнению с одномерным пространством, требуется в 1018 раз больше точек.
Поэтому, например, использование переборных алгоритмов становится неэффективным при возрастании размерности системы.

Сферы возникновения
Машинное обучение
Задачи распознавания
Задачи оптимизации
Комбинаторная геометрия
Работа со сложными системами

Трудности при работе со сложными системами
Трудоемкость вычислений
Необходимость хранения огромного количества данных
Увеличение доли шумов

Способ решения
Основная идея при решении проблемы — понизить размерность пространства, а именно спроецировать данные на подпространство меньшей размерности. На этой идее и основан метод главных компонент.

Пример проецирования данных на подпространство меньшей размерности

История появления
Гарольд Хотеллинг (29 сентября 1895, Фулда, Миннесота — 26 декабря 1973, Чапел-Хилл, Северная Каролина) — американский экономист и статистик. Детально разработал метод главных компонент, предложенный Карлом Пирсоном.
Карл Пи́рсон (27 марта 1857, Лондон — 27 апреля 1936, Лондон) — английский математик, статистик, биолог и философ; основатель математической статистики, один из основоположников биометрики. Предложил идею метода главных компонент в 1901. В русскоязычных источниках его иногда называют Чарлз Пирсон.

Эквивалентные постановки метода главных компонент
1. Аппроксимировать данные линейными многообразиями меньшей
размерности
2. Найти подпространства меньшей размерности, в ортогональной проекции на
которые разброс данных максимален
3. Найти подпространства меньшей размерности, в ортогональной проекции на
которые среднеквадратичное расстояние между точками максимально
4. Для данной многомерной случайной величины построить такое
ортогональное преобразование координат, что в результате корреляции между
отдельными координатами обратятся в ноль.

Пример “Школьные оценки”
Пусть у нас имеются результаты теста для школьников по двум предметам — например, по русскому языку и математике.
Тогда мы можем построить по этим результатам график.
Предположим, что нам надо уменьшить размерность — вместо двух чисел на каждого школьника хранить только одно число.

Пример “Школьные оценки”
Мы можем отбросить одну из переменных и оставить другую. Например, можно записывать в аттестат только оценку по русскому языку, а оценку по математике игнорировать. Но в таком случае мы потеряем слишком много информации.

Пример “Школьные оценки”
Нам необходимо выбрать такую систему координат, в которой мы сможем избавиться от зависимостей между переменными. Именно благодаря этому новая система координат будет «экономнее» старой и мы можем выделить в ней переменную PC1, содержащую большую часть информации.

Основные понятия
Линейное многообразие
M = {v + x | x ∈ L}
Линейная комбинация
Ортонормированная система
Ортогональное преобразование
Ковариационная матрица
Cov(Xi,Xj)= E[(Xi - E(Xi)) * (Xj - E(Xj))]

Аппроксимация данных линейными многообразиями
Дано: ?1, ?2, … , ?m ∈ ?n, ? = 1, 2, … , ? – 1
Найти: ?k ⊂ ?n :
∀?k = {?0 + ?1?1 + ⋯ + ?k?k, ?i ∈ R}, где параметры ?i пробегают вещественную прямую ?, ?0 ∈ ?n, {?1, ?2, … , ?k} ⊂ ?n – ортонормированный набор векторов.

Аппроксимация данных линейными многообразиями
Решение задачи аппроксимации для ? = 1, 2, … , ? – 1 дается набором вложенных линейных многообразий ?0 ⊂ ?1 ⊂ … ?n-1, ?k = {?0 + ?1?1 + ⋯ + ?k?k, ?i ∈ R}. Эти линейные многообразия определяются ортонормированным набором векторов {?1, … , ?n-1} – векторами главных компонент и вектором ?0. Вектор ?0 ищется как решение задачи минимизации для ?0:

Аппроксимация данных линейными многообразиями
Ищем такой вектор, при котором максимизировалась бы дисперсия проекции нашей выборки на него.

Диагонализация ковариационной матрицы
Векторы главных компонент для задач о наилучшей аппроксимации и о поиске ортогональных проекций с наибольшим рассеянием — это ортонормированный набор {?1, …, ?n} собственных векторов эмпирической ковариационной матрицы C, расположенных в порядке убывания собственных значений ?: ?1 ≥ ?2 ≥ … ≥ ?n ≥ 0. Данные векторы служат оценкой для собственных векторов ковариационной матрицы cov(?i, ?j). В базисе из собственных векторов ковариационной матрицы она, естественно, диагональна, и в этом базисе коэффициент ковариации между различными координатами равен нулю.

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

Подавление шума на изображениях

Примеры
Биоинформатика
Хемометрика
Индексация видео
Общественные науки

Применение для визуализации
Проекция ДНК-блуждания на первые 2 главные компоненты для генома бактерии «Streptomyces coelicolor».