[ЗАСТАВКА] В этом видео мы поговорим про многомерное шкалирование — один из довольно простых методов нелинейного понижения размерности. Мы уже обсуждали линейные методы понижения размерности, например, метод случайных проекций, в котором каждый новый признак линейно выражается через исходные признаки, и при этом веса этой линейной комбинации выбираются случайно. Например, из нормального распределения с нулевым средним и какой-то дисперсией. Также мы обсуждали метод главных компонент, который более грамотно выбирает эти веса. Он выражает их через сингулярные векторы матрицы «объекты-признаки», но при этом он все еще является линейным. Оба этих метода не могут поймать нелинейные зависимости в данных. Поймать эти зависимости может, например, метод многомерного шкалирования, или сокращенно MDS. Гипотеза этого метода состоит в том, что попарные расстояния между объектами в новом признаковом пространстве должны быть как можно ближе к попарным расстояниям в исходном пространстве признаков. То есть, например, если есть два объекта, и расстояние в исходном пространстве между ними было равно 10, то в новом пространстве будем пытаться разместить их так, что расстояние между ними будет как можно ближе к этой десятке. Давайте введем несколько формальных обозначений. Объекты в исходном высокомерном пространстве будем обозначать как x1, ..., xl. Всего их l-штук. Объекты после проецирования, объекты в новом маломерном пространстве, будем обозначать как x1 с волной, ..., xl с волной. Расстояния между объектами в исходном пространстве — это dij. Они измеряются по какой-то метрике ρ, это необязательно евклидова метрика, может быть какая угодно метрика. Расстояния между объектами в новом маломерном пространстве — это dij с волной, и их мы уже будем измерять с помощью евклидовой метрики. Обратите внимание, что здесь нам необязательно знать признаковые описания объектов в исходном пространстве. Достаточно знать лишь попарные расстояния между ними. То есть этот метод можно использовать в задачах, где признаки мы не знаем, а вот расстояния между объектами измерять умеем. В задаче многомерного шкалирования будет следующая постановка: мы для каждой пары из i-того и j-того объекта будем пытаться сделать как можно ближе расстояние между объектами в новом маломерном пространстве (то есть расстояния между xi с волной и xj с волной) и расстояние между объектами в исходном пространстве, то есть dij. Отклонения между этими расстояниями будем измерять с помощью квадратичного отклонения, то есть считаем их разность и возводим в квадрат. Мы уже хорошо знакомы с этим подходом. И вот этот функционал, который для всех пар объектов измеряет такое отклонение, мы будем минимизировать. Обратите внимание, что эта задача довольно сложная. Раньше мы обычно вели суммирование просто по всем объектам. Здесь же суммирование ведется по всем парам объектов. Также здесь используются не какие-то веса или параметры модели, а в оптимизации участвуют непосредственно сами признаковые описания в новом пространстве. Поэтому задача сложная, и метод оптимизации будет тоже довольно сложным. Мы не будем его обсуждать, скажу лишь, что это метод SMACOF, который обычно используется. Он состоит в том, что на каждой итерации данный функционал оценивается сверху другим функционалом, который оптимизировать уже гораздо проще. Давайте посмотрим, как работает метод MDS — метод многомерного шкалирования — на задаче MNIST. Видно, что он довольно неплохо разделяет цифры. То есть действительно, каждый класс оказывается хорошо отделимым от остальных классов. Но при этом как объекты внутри классов, так и сами классы оказываются довольно близки друг к другу. Это следствие того, что мы пытаемся отобразить довольно многомерное (почти тысячемерное) пространство в двумерное. А в пространствах высокой размерности есть такая штука как проклятие размерности, которое состоит в том, что чем выше размерность пространства, тем более похожи друг на друга расстояния между различными парами объектов. Итак, мы обсудили метод многомерного шкалирования, который пытается найти такое отображение объектов в маломерное пространство, что при этом как можно лучше сохраняются попарные расстояния между объектами. В следующем видео мы поговорим про метод TSNE, который является развитием метода многомерного шкалирования и устраняет довольно много его проблем.