В этом видео мы начнем
говорить о задаче понижения размерности.
О том, зачем она нужна, чем отличается от отбора признаков,
и обсудим один простой подход к ее решению.
Для начала давайте рассмотрим пару примеров.
Вот есть такая выборка, у нее три размерности.
При этом видно, что если просто убрать из нее признак,
который отложен по оси Z, то мы получим двумерную выборку,
в которой классы будут все еще отлично разделяться между собой.
Синий, зеленый и красный будут разделимы даже линейными методами.
А вот более сложный случай.
Здесь кажется, что оба признака — значимые.
Но при этом можно заметить, что можно спроецировать эти данные на прямую,
сделав их одномерными, не потеряв при этом практически никакой информации.
То есть да, оба признака значимые, но при этом они линейно зависимые.
И этим можно воспользоваться, чтобы устранить некоторую избыточность в данных.
Но при этом отбора признаков здесь не хватит.
Нужно сформировать новый признак на основе двух исходных.
Бывают и еще более сложные случаи, как, например, здесь.
Здесь тоже видно, что можно спроецировать выборку на некоторую кривую, но при этом
кривая очень нелинейная, и скорее всего, найти ее будет довольно сложно.
Так мы приходим к задаче понижения размерности,
которая состоит в формировании новых признаков на основе исходных.
При этом новых признаков должно быть меньше, чем исходных,
но они должны сохранять в себе как можно больше информации,
которая содержалась в исходных признаках.
Один из основных подходов к понижению размерности — это
линейный подход, в котором каждый новый
признак представляет собой линейную комбинацию исходных признаков.
Если говорить более формально, то будем считать,
что исходных признаков у нас D штук, при этом значение j-того исходного
признака на i-том объекте выборки будем обозначать, как xᵢⱼ.
А новых признаков при этом d штук,
и значение j-того нового признака на i-том объекте выборки обозначаем, как zᵢⱼ.
И будем считать, что раз у нас подход линейный,
то признак zᵢⱼ — новый j-тый признак на i-том объекте — линейно
выражается через исходные признаки на этом же i-том объекте, xᵢⱼ.
И при этом они складываются с весами wⱼk-тое,
где вес wⱼk-тое показывает, какой именно вклад k-тый
исходный признак делает в j-тый новый признак на каждом объекте.
Один из простейших подходов к такому понижению
размерности — это метод случайных проекций, в котором мы просто случайно
генерируем все эти веса wⱼk-тое, например, из нормального распределения.
То есть wⱼk-тое мы просто выбираем из нормального распределения с центром в 0 и
дисперсией, например, 1/d, где d — это количество новых признаков,
которое мы хотим сделать.
Этот подход не такой уж необоснованный,
у него есть некоторое обоснование в виде леммы Джонсона-Линденштраусса,
которая говорит следующее: если у нас есть выборка, в которой объектов меньше,
чем признаков, то есть это выборка в очень многомерном признаковом пространстве,
то ее можно спроецировать в пространство меньшей размерности так,
что при этом расстояния между объектами практически не изменятся.
То есть мы сохраним топологию в этом признаковом пространстве.
При этом, если мы хотим, чтобы расстояния изменились не больше, чем на ε,
то нужно брать размерность нового признакового пространства (количество
новых признаков d) не меньше, чем вот такая дробь: 8 * ln
количества объектов в выборке / ε².
Да, эта лемма лишь говорит о том, что существует такая проекция,
что она будет сохранять расстояния между парами признаков.
Но при этом на практике оказывается, что если взять d, соответствующее вот такой
формуле, то даже метод случайных проекций строит такое преобразование признаков,
так понижает размерность выборки, что расстояния сохраняются неплохо,
и это понижение оказывается довольно качественным.
Такой подход оказывается хорошо работающим для текстов,
где размерности всегда оказываются большими.
Мы кодируем каждый текст с помощью признаков,
с помощью мешка слов, и при этом признаков у нас столько,
сколько слов в словаре, и поэтому признаков оказывается очень много.
И даже метод случайных подпространств работает очень хорошо на таких выборках,
хотя, конечно, есть и более интеллектуальные подходы.
Итак: мы начали разговор о методах понижения размерности, поговорили,
зачем это нужно, и что это гораздо более общий подход, чем отбор признаков,
и обсудили один очень простой подход — метод случайных подпространств.
А в следующем видео мы поговорим о более продвинутом подходе
к понижению размерности — методе главных компонент.