Разбираемся в ML без воды: от базы до Attention. Часть 12: Понижение размерности и PCA

В предыдущей части ^[1] мы разобрали градиентный бустинг — финального босса в классическом обучении ^[2] с учителем. Мы научились строить мощные ансамбли, которые выжимают максимум из табличных данных. Кажется, что на этом можно ставить точку и прыгать в современный мир нейросетей и Deep Learning.

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

В этой части мы закроем очередную проблему в классическом ML — столкнемся лицом к лицу с проклятием размерности (curse of dimensionality). Поймем, как сжимать многомерные пространства, не теряя важный смысл, и как заставить машину самостоятельно группировать объекты в кластеры, вообще не имея готовых классов.

Проклятие размерности

Хорошо ли иметь много столбцов в датасете? На первый взгляд, кажется, да. Чем больше признаков, тем больше потенциально полезной информации может содержаться в данных. Закономерностей найдется больше, модель (хоть дерево, хоть линейная регрессия) получит больше информации для поиска закономерностей. Одним словом — профит. И это, в целом, истина.

Но у монетки есть и обратная сторона, по имени проклятием размерности (Curse of Dimensionality). Этот термин придумал математик Ричард Беллман для динамического программирования, но он идеально вписался и в мире машинного обучения. Разберем в чем его суть:

При увеличении количества признаков возникают несколько неприятных моментов.

Первое и, пожалуй, самое очевидное — вычисления становятся дороже: чем больше матрица признаков, тем больше памяти ^[3] нужно для её хранения. Кроме того, нужно выполнить больше вычислений при работе с этой матрицей.

Если учесть, что для скорости обучения выгоднее хранить данные на дорогой VRAM, ещё и делать сложные операции (та же кубическая сложность для обращения матрицы в линейной регрессии, если не говорить о хитрых алгоритмах), процесс обучения может пережить инженера, запустившего его.

Во-вторых, данные становятся “редкими”: представьте квадрат со стороной 1.

• В 1D это отрезок длины 1.

• В 2D — квадрат площадью 1.

• В 10D — гиперкуб объёма 1.

Теперь возьмём маленькую область со стороной 0.1.

• В 1D её “объём” равен 0.1, или 10% от всего пространства;

• В 2D: 0.01, или же 1%;

• В 10D: 10, то есть 0….01%.

Получается, общее пространство вокруг разрастается до гигантских масштабов, а область с нашими данными превращается в микроскопическую точку. Вокруг остается один пустой “воздух”. Чтобы заполнить этот 10-мерный куб данными с той же плотностью, что и обычный отрезок, нам понадобится экспоненциально больше строк в датасете. Откуда найти столько данных? — непонятно.

Из этого вытекает третья проблема: расстояния теряют свой смысл.

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

Самая дальняя точка оказывается почти на таком же расстоянии, как и самая близкая. То есть понятие “сосед” становится менее информативным.

Также, есть и четвертая проблема: возможность переобучения:

Если признаков много, модель получает огромную свободу.

Например у нас 100 объектов и 100500 признаков. Модель может найти гиперплоскость, которая идеально разделит обучающую выборку, но на новых данных всё развалится.

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

Понижение размерности

Как мы увидели, проблем у высокой размерности достаточно много. И один из классических способов борьбы с ними звучит почти гениально: раз высокая размерность создаёт проблемы, давайте её понизим.

Однако делать это нужно со вкусом ^[4]. Самый грубый подход иногда действительно работает: мы можем без сожалений удалить столбец с группой крови предыдущих владельцев из датасета, который используем для предсказания цен на дома. Иными словами, можно и нужно избавляться от признаков, которые вообще не связаны с поставленной задачей.

И да, формально это тоже является понижением размерности, активно используется на практике и называется отбором признаков (feature selection). Минус такого подхода заключается в том, что в конечном счёте мы своими руками избавляемся от части информации.

Но есть и другой подход — можно составить новые признаки, используя старые. Простым примером является создание столбца “площадь” из столбцов “длина” и “ширина”. Этот метод тоже имеет свое название — извлечение признаков (feauture extraction).

Посмотрим как это работает, на примере ветерана машинного обучения — метода PCA.

Principal component analysis (PCA)

Итак, Метод главных компонент (Principal component analysis, PCA) — это способ преобразовать исходные признаки так, чтобы получить новое пространство, в котором информация “упакована” более компактно.

Возьмем датасет с автомобилями. Если у всех машин пробег равен ровно 100500 км, этот признак, очевидно, бесполезен. Но если пробег варьируется от 5000 до 100000 км, разброс огромен, и этот признак уже может быть информативным. PCA ищет такие направления в данных, вдоль которых этот разброс максимален, и объявляет их новыми осями — главными компонентами.

PCA фактически вращает старые оси координат (признаки). Он находит такое направление, вдоль которого данные вытянуты сильнее всего, и делает его первой, самой важной осью — первой главной компонентой.

Посмотрим как это работает с математической точки зрения ^[5].

Возьмем датасет (матрицу) размерности , где n — количество объектов (строк), а — количество признаков (столбцов).

Как мы уже поняли, речь будет пойти о дисперсии. Потому, изначально хочется центрировать данные (вычесть из каждого признака его среднее значение по выборке). Делается это крайне просто: для каждого признака вычисляем среднее

И отнимаем её от всех значений . Тем самым центр превращается в начало координат. Теперь надо думать на какую прямую лучше всего спроецировать наши точки. Чтобы не путаться в обозначениях, напишем полученное как , где — центрированное.

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

И вот здесь нам как раз пригодится центрирование, ибо дисперсия раскроется просто как

Подставляя , получим

Вспоминаем ковариационную матрицу: . Получаем итоговую задачу PCA:

Дальше все достаточно естественно — люди мы простые, видим условную задачу, вводим Лагранжиан (подробнее об этом было в части 8 ^[6]).

По стандартному методу, берем производную по , приравниваем к нулю:

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

Теперь мы получили главную идею: , если — собственный вектор. А значит для задачи максимизации мы просто берем собственный вектор с наибольшим собственным значением.

То есть, весь PCA это:

• Вычислить ковариационную матрицу для центрированных данных;

• Найти собственные векторы ковариационной матрицы;

• Отсортировать их по собственным значениям;

• Взять первые (число компонент);

• Умножать данные на эти векторы и получить сжатый датасет размера .

Казалось бы, всё отлично, но раз мы занимаемся понижением размерности, то фич у нас многовато. А из этого следует, что ковариационная матрица будет огромной. Именно поэтому, на практике почти всегда обходятся без вычисления ковариационной матрицы, а используют метод под названием SVD ^[7].

Singular Value Decomposition / Сингулярное разложение

Суть SVD заключается в том, что мы можем разложить матрицу на вращение, сжатие и на ещё одно вращение.

Где

• — ортогональная матрица размера . Её столбцы — это собственные векторы матрицы .

• — ортогональная матрица размера . Её столбцы — это собственные векторы матрицы

• — прямоугольная диагональная матрица размера . На её главной диагонали стоят неотрицательные числа, упорядоченные по убыванию . Это сингулярные числа, которые равны корням из собственных значений .

Если подставить такое разложение в ковариационную матрицу , получим

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

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

Остается финальный шаг: умножим обе части этого равенства на матрицу справа:

Так как матрица V ортогональна, то и , а значит

Фактически, это то же самое уравнение , к которому мы пришли через Лагранжиан.

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

Посмотрим на разницу:

Как говорится, хрен редьки не слаще. Однако, всё это время мы брали все собственные вектора, а затем оставили из них первые . Для решения этой проблемы существует метод Ланцоша.

Метод Ланцоша

В чем суть? Раз мы не обязаны найти все собственные векторы огромной матрицы, мы можем спроецировать её на подпространство гораздо меньшей размерности k, где и найдем нужное нам количество.

Пусть у нас есть ковариационная матрица размера . Мы физически не можем её вычислить и хранить в памяти. Наша цель — найти её первый собственный вектор (главную компоненту).

Возьмем случайный единичный вектор размера и умножим его на ковариационную матрицу справа. Назовем результат как.

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

Теперь измерим, какая часть от вектора сонаправлена с нашим исходным вектором ․ Для этого найдем их скалярное произведение и обозначим полученное число как :

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

Посмотрим на следующее произведение:

Так как единичный (), а , то получаем:

Как и ожидалось, вектор перпендикулярен .

Обозначим длину вектора как (). Отнормируем его, чтобы получить второй единичный вектор:

Подставим это обратно в наше уравнение:

Теперь у нас есть два взаимно перпендикулярных вектора и . Умножим матрицу на наш новый вектор :

Аналогично предыдущему шагу, этот вектор будет как-то проецироваться на уже имеющиеся у нас направления и . Найдем эти проекции:

• Проекция на :

• Проекция на :

По свойствам транспонирования . Подставим сюда найденное нами выражение для :

Итак, и перпендикулярны, длина равна 1. Нетрудно заметить, что наше выражение превращается просто в число .

Красота симметрии ^[8]: проекция нового вектора на самый первый вектор оказалась в точности равна числу , которое мы посчитали на прошлом шаге!

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

Измеряем длину остатка и находим следующий единичный вектор :

Отсюда получим

Аналогично для :

То есть вектор зависит только от и .

Запишем систему уравнений в общем виде для векторов. Соберем векторы в прямоугольную матрицу размера .

Тогда всю эту цепочку уравнений можно записать как одно матричное равенство:

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

Умножим уравнение на слева. Так как все векторы строго перпендикулярны друг другу, то (единичная матрица размера ). Получаем:

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

Теперь компьютеру не составит труда собственные векторы этой матрицы :

Но давайте поймем куда делись наши “омеги и лямбды”.

Подставим вместо выражение :

Умножим на слева:

Поскольку вектор по определению метода Ланцоша целиком лежит внутри нашего подпространства , операция проекции оставляет его неизменным и полностью исчезает. Получим:

Сравниваем это с нашим Лагранжианом :

• Наши искомые омеги (собственные векторы) — это просто .

• Наши лямбды (собственные значения) — это .

Заключение

Напоследок, добавим этот метод в нашу таблицу для сравнения.

Думаю, комментарии излишни.

На если запустить алгоритм в таком виде, то через 3–4 шага из-за микроскопических погрешностей в вычислениях свойство ортогональности векторов начинает теряться (в численных методах это называют loss of orthogonality). Новые векторы перестают быть перпендикулярными самым первым, и алгоритм ломается.

Именно поэтому на практике (включая тот же scikit-learn и с его ARPACK) никто не запускает метод Ланцоша “в лоб”. К нему обязательно прикручивают так называемую процедуру переортогонализации.

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

И да, за точность приходится платить: в формулу времени добавляется дополнительный хвост операций, зависящий от количества компонент. Но поскольку мы обычно ищем всего несколько компонент ( обычно маленькое), эта надбавка ничтожна.

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