[ЗАСТАВКА] В
этой лекции мы поговорим о нелинейных методах понижения размерности,
которые ещё называют методами обучения многообразий.
Но прежде чем перейти к методам,
давайте рассмотрим для примера набор изображений рукописных цифр MNIST.
Каждый объект из набора — это изображение 28 на 28 пикселей.
В каждом пикселе известна интенсивность цвета, то есть частное число от 0 до 1.
Матрицу интенсивности можно развернуть в вектор признаков длины 784.
Что можно сказать про расположение объектов в признаковом пространстве?
Для того чтобы ответить на этот вопрос, давайте возьмём случайный вектор из
пространства признаков и посмотрим, какие изображения будут ему соответствовать.
Если мы сделаем так много раз, то мы обнаружим,
что вектор признаков с вероятностью, равной единице не будет
соответствовать рукописной цифре, а будет выглядеть, как какой‐то шум.
Это означает, что изображение рукописных цифр в их признаковом описании занимает
лишь незначительную часть всего пространства признаков.
Если мы возьмём линейную комбинацию признаков двух рукописных цифр,
то мы можем увидеть, что она может не соответствовать рукописной цифре,
а соответствовать какому‐то непонятному изображению.
Это говорит о том, что пространство, в котором лежат рукописные цифры — оно,
вообще говоря, не является линейным.
Но было бы удобно работать в признаковом пространстве,
которое содержит только рукописные цифры.
Для того чтобы было проще понять, что значит «работать в пространстве,
содержащем только рукописные цифры», рассмотрим более простую модель например.
В трёхмерном пространстве имеется S‐образная поверхность, на которой лежат
объекты выборки, которые можно отобразить на двухмерную координатную плоскость,
сохранив при этом всю информацию об объектах.
При этом вся плоскость будет равномерно заполнена объектами нашей выборки.
Теперь мы можем формально поставить задачу нелинейного понижения размерности.
Имеется выборка x1, ..., xl.
И наша задача — отобразить все объекты выборки в пространство малой размерности.
При этом мы требуем, чтобы малоразмерное представление хорошо отражало структуру
данных в исходном пространстве и сохраняло интересующие нас закономерности в данных.
Наиболее популярное приложение методов нелинейного понижения размерности —
визуализация данных.
Человек живет в трёхмерном мире, и посмотреть глазами на данные с
более чем тремя вещественными признаками достаточно трудно.
Визуализировать объекты, представленные векторами большой размерности — значит
расположить их на прямой,
плоскости или в виде трёхмерного облака точек таким образом, чтобы их расположение
хорошо отражало внутреннюю структуру данных в исходном пространстве.
Возьмём для примера рукописные цифры от 0 до 5 и отобразим их в
двухмерное пространство при помощи метода главных компонент,
рассмотренном на предыдущих лекциях.
На этом изображении координатные оси соответствуют компонентам проекции,
различные цифры выделены цветом.
Видно, что классы перемешаны между собой,
хотя человек по изображению отличает цифры достаточно точно.
Это следствие нелинейности пространства рукописных цифр,
заданных числовыми векторами.
А теперь мы рассмотрим несколько простых методов, используемых на практике.
И начнём мы с многомерного шкалирования, или сокращённо MDS.
Этот метод основан на гипотезе о том, что хорошее малоразмерное представление
сохраняет попарные расстояния между объектами выборки.
И наша задача — найти такое малоразмерное представление,
евклидово расстояние между объектами в котором аппроксимировало бы достаточно
хорошо расстояние между объектами в исходном признаковом пространстве dᵢⱼ.
Мы записываем это в виде оптимизационной задачи,
алгоритм решения которой разбирать не будем, но перейдём к примеру.
Применим многомерное шкалирование к выборке рукописных цифр и уменьшим
размерность признакового пространства до двух.
Расположим эти объекты на плоскости.
Видно, что классы цифр расположились каждая в своей области.
И они уже не так сильно перемешаны, как это было в случае,
когда мы просто спроецировали на главные компоненты.
Следующий метод, который мы рассмотрим — SNE (Stochastic Neighbor Embedding).
Основан на идее о том, что при отображении объектов в пространство малой размерности
сохранить расстояние в исходном признаковом пространстве достаточно
сложно, но при этом достаточно сохранения пропорций этих расстояний.
Для построения такого представления каждый объект выборки описывается нормированными
расстояниями до всех остальных объектов.
В исходном признаковом пространстве мы обозначим это описание за p,
а в пространстве малой размерности обозначим его за q.
Мы хотим выбрать такое малоразмерное представление,
чтобы описания p и q всех объектов были максимально похожи.
Набор нормированных распределений p и q будем сравнивать при помощи
дивергенции Кульбака‐Лейблера.
Таким образом, задача сводится к минимизации суммы дивергенции Кульбака —
Лейблера между всеми соответствующими представлениями p и q.
Эту оптимизационную задачу можно решать при помощи метода стохастического
градиентного спуска.
Метод SNE можно улучшить.
Вспомним, что чем выше размерность пространства,
тем меньше расстояния между парами точек отличаются друг от друга.
Это так называемое «проклятие размерности».
Иными словами, в пространстве малой размерности, например на плоскости,
нельзя расположить достаточно большое число точек так,
чтобы расстояния между ними были примерно равны.
Значит, нужно меньше штрафовать за сильное увеличение пропорций
в малоразмерном пространстве, поскольку оно в любом случае будет иметь место.
Чтобы меньше штрафовать, в описании объекта в виде нормированных расстояний
заменим экспоненту от расстояния на выражение вида «1 / 1 + расстояние».
Применим метод t-SNE к набору рукописных цифр.
Отобразим все объекты в двухмерное пространство и расположим на плоскости.
На получившейся визуализации цифры расположились в виде чётко выраженных
кластеров.
Невооружённым глазом видно, что к такому представлению цифр в виде всего 2
признаков можно применять методы классификации, не проигрывая в точности.
Имея такую визуализацию,
мы можем посмотреть глазами на внутреннюю структуру данных.
Например, мы можем наблюдать,
что объекты из класса единичек разбиты на 3 характерных кластера.
Единички, написанные с нижней засечкой-подставкой, единички без засечек,
похожие на палочку, и единички с выраженной верхней засечкой,
которая сильнее всего похожа на цифру 4.
Собственно, и расположены они ближе всего к облаку четверок.
В этой лекции мы разобрали методы нелинейного понижения размерности MDS и
t-SNE.
Они восстанавливают информацию о внутренней структуре данных в признаковом
пространстве.
За счёт этого понижают размерность эффективнее линейных методов,
таких, как метод главных компонент.
Рассмотренные методы хорошо применять для визуализации данных.
На примере набора рукописных цифр MNIST нам удалось эффективно снизить размерность
описания объектов с нескольких сот до всего двух признаков.
[ЗАСТАВКА]