[ЗАСТАВКА] В этом видео мы поговорим про метод t-SNE,
один их наиболее современных подходов к визуализации данных.
В прошлый раз мы говорили про задачу многомерного шкалирования,
где производится попытка найти новое признаковое описание объектов (маломерное
признаковое описание объектов),
что расстояние между парами объектов в новом пространстве как можно ближе
к расстоянию между объектами в исходном многомерном признаковом пространстве.
При этом задача, которая получается, она довольно сложная, потому что понятно,
что очень непросто сохранить расстояние при радикальном уменьшении
размерности пространства.
Скорее всего, решение задачи будет получаться не очень качественным.
Метод SNE пытается решить эту проблему следующим образом: он больше не
требует близости попарных расстояний,
он требует лишь, чтобы сохранялись пропорции расстояний между объектами.
А именно: допустим у нас есть тройка объектов — xi, xj и xk, и мы знаем,
что расстояние между i-тым и j-тым объектом в α раз больше,
чем расстояние между i-тым и k-тым объектом.
Тогда в методе SNE будет требоваться, чтобы и в новом пространстве,
маломерном пространстве, это свойство сохранялось,
то есть чтобы расстояние между проекциями объектов xi и xj было в α раз больше,
чем расстояние между проекциями объектов xi и xk.
Чтобы это формализовать, воспользуемся следующим подходом.
Введем следующие распределения на объектах при условии i-го объекта.
Вероятность j-го объекта при условии i-го объекта будет вычисляться как
нормированное расстояние между i-тым и j-тым объектом, где расстояние считается
как экспонента в степени евклидова расстояния между этими объектами.
Тут еще присутствует параметр σ, который является гиперпараметром метода.
В каждом пакете есть рекомендации по выбору этого параметра,
которые работают довольно хорошо.
Итак, вероятность вычисляется как расстояние между этими объектами,
деленное на сумму расстояний от i-го объекта до всех остальных объектов.
Получаем такое распределение, оно как раз нужно для того, чтобы учитывать только
пропорции, то есть этому распределению неважны абсолютные значения, например,
евклидовой метрики в исходном пространстве.
Ему важны лишь соотношения: расстояние до какого объекта во сколько раз
было больше расстояния до другого объекта.
Также мы вводим такие же распределения в новом маломерном пространстве,
которое обозначается как q от xj при условии xi с волной, и вычисляются таким
же образом: это экспонента в степени расстояния между парой объектов делить на
сумму экспонент для всех пар между i-тым и другими объектами.
Чтобы как-то сравнить эти два распределения, нам нужно выписать
функционал, который находит различия между двумя вероятностными распределениями.
Известно, что для этого очень хорошо подходит дивергенция Кульбака-Лейблера.
Она вычисляется вот таким образом: там стоит суммирование,
и под знаками суммы находится вероятность xj при условии xi, умноженная
на логарифм отношения этого расстояния в исходном признаковом пространстве и
расстояния в новом признаковом пространстве, q от xj при условии xi.
Мы минимизируем этот функционал и пытаемся найти описание объектов
в новом маломерном пространстве.
Минимизировать его можно, например,
с помощью стохастического градиентного спуска.
У этого подхода есть одна проблема, которая решается в методе t-SNE.
Дело в том, что в пространствах высокой размерности, как мы уже упоминали,
имеет место проклятье размерности, которое состоит в том, что, во-первых,
чем больше размерность пространства, тем более близки друг к другу расстояния между
парами объектов, а во-вторых, вообще, чем больше размерность пространства,
тем проще нам разместить объекты ближе друг к другу, тогда как
ту же самую близость в двухмерном пространстве сохранить очень сложно.
Собственно, тот способ, с помощью которого мы штрафуем за несохранение пропорций,
а именно: экспонента в степени евклидова расстояния, и потом это еще подставляется
в дивергенцию Кульбака-Лейблера, на самом деле очень сильно штрафует,
если мы увеличиваем расстояние в новом пространстве.
Нужно с этим как-то бороться.
Оказывается, проблему можно устранить, если использовать немного другой
способ вычисления распределений в новом пространстве.
В исходном пространстве признаков мы используем точно
такой же подход с экспонентой и евклидовым расстоянием,
а в маломерном пространстве вероятности вычисляются по вот такой формуле.
Здесь уже не экспонента,
а единица делить на один плюс расстояние между парой объектов.
Действительно, можно проверить,
что при таком подходе в методе t-SNE объекты в новом пространстве — двумерном
или трехмерном — оказываются гораздо более сильно разнесенными между собой.
Разделение гораздо более четкое.
Собственно, если посмотреть на результат применения метода t-SNE к набору данных
MNIST, мы увидим вот такую картину.
Видно, что классы разделяются очень хорошо.
Те классы цифр, которые похожи по начертанию,
оказываются близко друг к другу; те классы цифр, которые очень непохожи по начертанию
на остальные, сильно отделены от общего облака.
При этом некоторые классы разбиваются еще на подкластеры, как, например, единичка.
У нее выделяется три подкластера, и они зависят от того,
как именно единица рисуется: есть ли у нее верхняя засечка или нет;
рисуем ли мы внизу палочку или нет.
Собственно, это все характеризует эти кластеры.
Визуализация получается очень хорошая,
и она реально отображает структуру объектов в исходном пространстве.
Если же вспомним, как этот набор данных был визуализирован методом MDS (методом
многомерного шкалирования), видно, что ситуация не такая хорошая.
Да, объекты разделимы, но при этом классы довольно близки друг к другу,
и нет никакой кластеризации внутри отдельных классов,
то есть визуализация получается довольно хаотичной.
Итак, мы поговорили про метод t-SNE, один из наиболее качественных методов
визуализации данных, который, во-первых, требует лишь сохранения пропорций
расстояния между объектами и не сильно штрафует за то,
что расстояния увеличиваются в новом маломерном пространстве.
Evgeniy Riabenko
Evgeny Sokolov
Victor Kantor
Emeli Dral
Константин Воронцовдоктор физико-математических наук, профессор
