Для чего нужно понижение размерности

Уменьшение размерности

Под уменьшением размерности (англ. dimensionality reduction) в машинном обучении подразумевается уменьшение числа признаков набора данных. Наличие в нем признаков избыточных, неинформативных или слабо информативных может понизить эффективность модели, а после такого преобразования она упрощается, и соответственно уменьшается размер набора данных в памяти и ускоряется работа алгоритмов ML на нем. Уменьшение размерности может быть осуществлено методами выбора признаков (англ. feature selection) или выделения признаков (англ. feature extraction).

Содержание

Выбор признаков [ править ]

Методы выбора признаков оставляют некоторое подмножество исходного набора признаков, избавляясь от признаков избыточных и слабо информативных. Основные преимущества этого класса алгоритмов:

Все методы выбора признаков можно разделить на 5 типов, которые отличаются алгоритмами выбора лишних признаков.

Фильтры [ править ]

Фильтры могут быть:

Преимуществом группы фильтров является простота вычисления релевантности признаков в наборе данных, но недостатком в таком подходе является игнорирование возможных зависимостей между признаками.

Оберточные методы [ править ]

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

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

Встроенные методы [ править ]

Группа встроенных методов (англ. embedded methods) очень похожа на оберточные методы, но для выбора признаков используется непосредственно структуру некоторого классификатора. В оберточных методах классификатор служит только для оценки работы на данном множестве признаков, тогда как встроенные методы используют какую-то информацию о признаках, которую классификаторы присваивают во время обучения.

Одним из примеров встроенного метода является реализация на случайном лесе: каждому дереву на вход подаются случайное подмножество данных из датасета с каким-то случайным набор признаков, в процессе обучения каждое из деревьев решений производит «голосование» за релевантность его признаков, эти данные агрегируются, и на выходе получаются значения важности каждого признака набора данных. Дальнейший выбор нужных нам признаков уже зависит от выбранного критерия отбора.

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

Другие методы [ править ]

Есть и другие методы выбора признаков: гибридные (англ. hybrid methods) и ансамблевые (англ. ensemble methods). Гибридные методы комбинируют несколько разных методов выбора признаков, например, некоторое множество фильтров, а потом запускают оберточный или встроенный метод. Таким образом, гибридные методы сочетают в себе преимущества сразу нескольких методов, и на практике повышают эффективность выбора признаков.

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

Примеры кода scikit-learn [ править ]

Пример кода, реализующего функцию оценки фильтра на основе коэффициента ранговой корреляции:

Пример кода, реализующего SVM-RFE wrapper:

Выделение признаков [ править ]

Другим способом уменьшить размерность входных данных является выделение признаков. Эти методы каким-то образом составляют из уже исходных признаков новые, все также полностью описывающие пространство набора данных, но уменьшая его размерность и теряя в репрезентативности данных, т.к. становится непонятно, за что отвечают новые признаки. Все методы feature extraction можно разделить на линейные и нелинейные.

Одним из самых известных методов линейного выделения признаков является PCA [на 28.01.19 не создан] (Principal Component Analysis, рус. метод главных компонент). Основной идеей этого метода является поиск такой гиперплоскости, на которую при ортогональной проекции всех признаков максимизируется дисперсия. Данное преобразование может быть произведено с помощью сингулярного разложения матриц и создает проекцию только на линейные многомерные плоскости, поэтому и метод находится в категории линейных.

Пример кода scikit-learn [ править ]

Пример выделения признаков с помощью PCA в scikit-learn:

Источник

Обзор нового алгоритма уменьшения размерности UMAP. Действительно ли он лучше и быстрее, чем t-SNE?

Привет, Хабр! Задача снижения размерности является одной из важнейших в анализе данных и может возникнуть в двух следующих случаях. Во-первых, в целях визуализации: перед тем, как работать с многомерными данными, исследователю может быть полезно посмотреть на их структуру, уменьшив размерность и спроецировав их на двумерную или трехмерную плоскость. Во-вторых, понижение размерности полезно для предобработки признаков в моделях машинного обучения, поскольку зачастую неудобно обучать алгоритмы на сотне признаков, среди которых может быть множество зашумленных и/или линейно зависимых, от них нам, конечно, хотелось бы избавиться. Наконец, уменьшение размерности пространства значительно ускоряет обучение моделей, а все мы знаем, что время — это наш самый ценный ресурс.

UMAP (Uniform Manifold Approximation and Projection) — это новый алгоритм уменьшения размерности, библиотека с реализацией которого вышла совсем недавно. Авторы алгоритма считают, что UMAP способен бросить вызов современным моделям снижения размерности, в частности, t-SNE, который на сегодняшний день является наиболее популярным. По результатам их исследований, у UMAP нет ограничений на размерность исходного пространства признаков, которое необходимо уменьшить, он намного быстрее и более вычислительно эффективен, чем t-SNE, а также лучше справляется с задачей переноса глобальной структуры данных в новое, уменьшенное пространство.

В данной статье мы постараемся разобрать, что из себя представляет UMAP, как настраивать алгоритм, и, наконец, проверим, действительно ли он имеет преимущества перед t-SNE.

Немного теории

Алгоритмы понижения размерности можно разделить на 2 основные группы: они пытаются сохранить либо глобальную структуру данных, либо локальные расстояния между точками. К первым относятся такие алгоритмы как Метод главных компонент (PCA) и MDS (Multidimensional Scaling), а ко вторым — t-SNE, ISOMAP, LargeVis и другие. UMAP относится именно к последним и показывает схожие с t-SNE результаты.

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

Результаты применения

Итак, теперь попробуем применить UMAP к какому-нибудь набору данных и сравним его качество визуализации с t-SNE. Наш выбор пал на датасет Fashion MNIST, который включает в себя 70000 черно-белых изображений различной одежды по 10 классам: футболки, брюки, свитеры, платья, кроссовки и т.д. Каждая картинка имеет размер 28×28 пикселей или 784 пикселя всего. Они и будут являться фичами в нашей модели.

Итак, попробуем использовать библиотеку UMAP на Python для того, чтобы представить наши предметы одежды на двумерной плоскости. Зададим количество соседей, равное 5, а остальные параметры оставим по умолчанию. Их мы обсудим чуть позже.

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

Как видно, алгоритм справляется вполне хорошо и «не растерял» большинство ценной информации, которая отличает один вид одежды от другого. Также о качестве алгоритма говорит и тот факт, что UMAP отделил обувь, одежду для туловища и брюки друг от друга, понимая, что это совершенно разные вещи. Конечно, есть и ошибки. К примеру, модель решила, что рубашка и свитер — это одно и то же.

Теперь посмотрим, как с этим же набором данных управится t-SNE. Для этого будем использовать Multicore TSNE — самую быструю (даже в режиме одного ядра) среди всех реализаций алгоритма:

T-SNE показывает схожие с UMAP результаты и допускает те же ошибки. Однако, в отличии от UMAP, t-SNE не так очевидно объединяет виды одежды в отдельные группы: брюки, вещи для туловища и для ног находятся близко друг к другу. Однако в целом можно сказать, что оба алгоритма одинаково хорошо справились с задачей и исследователь волен на свой вкус делать выбор в пользу одного или другого. Можно было, если бы не одно «но».

Это «но» заключается в скорости обучения. На сервере с 4 ядрами Intel Xeon E5- 2690v3, 2,6 Гц и 16 Гб оперативной памяти на наборе данных размера 70000х784 UMAP обучился за 4 минуты и 21 секунду, в то время как t-SNE потребовалось на это почти в 5 раз больше времени: 20 минут, 14 секунд. То есть UMAP значительно более вычислительно эффективен, что дает ему огромное преимущество перед другими алгоритмами, в том числе и перед t-SNE.

Параметры алгоритма

Число соседей — n_neighbors. Варьируя этот параметр, можно выбирать, что важнее сохранить в новом пространственном представлении данных: глобальную или локальную структуру данных. Маленькие значения параметра означают, что, пытаясь оценить пространство, в котором распределены данные, алгоритм ограничивается малой окрестностью вокруг каждой точки, то есть пытается уловить локальную структуру данных (возможно в ущерб общей картине). С другой стороны большие значения n_neighbors заставляют UMAP учитывать точки в большей окрестности, сохраняя глобальную структуру данных, но упуская детали.

Посмотрим на примере нашего датасета, как параметр n_neighbors влияет на качество и скорость обучения:

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

Вернемся к нашему датасету и оценим влияние параметра min_dist. Значение n_neighbors будет фиксированным и равным 5:

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

Метрика расстояния — metric. Параметр metric определяет, каким образом будут рассчитаны расстояния в пространстве исходных данных. По умолчанию UMAP поддерживает всевозможные расстояния, от Минковского до Хэмминга. Выбор метрики зависит от того, как мы интерпретируем эти данные и их типа. К примеру, работая с текстовой информацией, предпочтительно использовать косинусное расстояние (metric=’cosine’).

Продолжим играть с нашим датасетом и попробуем различные метрики:

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

Размерность конечного пространства — n_components. Тут все очевидно: параметр определяет размерность итогового пространства. Если вам нужно визуализировать данные, то следует выбирать 2 или 3. Если же использовать преобразованные вектора в качестве фич моделей машинного обучения, то можно и больше.

Заключение

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

Напоследок, посмотрите, как UMAP смог визуализировать набор данных Google News, состоящий из 3 миллионов векторов-слов. Время обучения составило 200 минут, тогда как t-SNE на это потребовалось несколько дней:

Кстати, рисунок был построен с помощью библиотеки для визуализации больших данных datashader, о которой мы расскажем вам в одной из следующих статей!

Среди алгоритмов снижения размерности есть SVD, которому мы уделяем внимание в контексте построения рекомендаций на нашей программе “Специалист по большим данным 8.0”, которая стартует уже 22 марта.

Источник

Как уменьшить количество измерений и извлечь из этого пользу

Сначала я хотел честно и подробно написать о методах снижения размерности данных — PCA, ICA, NMF, вывалить кучу формул и сказать, какую же важную роль играет SVD во всем этом зоопарке. Потом понял, что получится текст, похожий на вырезки из опусов от Mathgen, поэтому количество формул свел к минимуму, но самое любимое — код и картинки — оставил в полном объеме.

Еще думал написать об автоэнкодерах. В R же, как известно, беда с нейросетевыми библиотеками: либо медленные, либо глючные, либо примитивные. Это и понятно, ведь без полноценной поддержки GPU (и в этом огромный минус R по сравнению с Python) работа со сколь-нибудь сложными нейронными сетями — и в особенности с Deep Learning — практически бессмысленна (хотя есть подающий надежды развивающийся проект MXNet ). Интересен также относительно свежий фреймворк h2o, авторов которого консультирует небезызвестный Trevor Hastie, а Cisco, eBay и PayPal даже используют его для создания своих планов по порабощению человечества. Фреймворк написан на Java (да-да, и очень любит оперативную память). К сожалению, он тоже не поддерживает работу с GPU, т.к. имеет несколько иную целевую аудиторию, но зато отлично масштабируется и предоставляет интерфейс к R и Python (хотя любители мазохизма могут воспользоваться и висящем по дефолту на localhost:54321 web-интерфейсом).

Так вот, если уж возник вопрос о количестве измерений в наборе данных, то это значит, что их, ну, скажем так, довольно много, из-за чего применение алгоритмов машинного обучения становится не совсем удобным. А иногда часть данных — всего лишь информационный шум, бесполезный мусор. Поэтому лишние измерения желательно убрать, вытащив из них по возможности все самое ценное. Кстати, может возникнуть и обратная задача — добавить еще измерений, а попросту — больше интересных и полезных фич. Выделенные компоненты могут быть полезны и для целей визуализации (t-SNE на это, например, и ориентирован). Алгоритмы декомпозиции интересны и сами по себе в качестве машинных методов обучения без учителя, что, согласитесь, иногда может и вовсе привести к решению первичной задачи.

Матричные разложения

В принципе, для сокращения размерности данных с той или иной эффективностью можно приспособить большинство методов машинного обучения — этим, собственно, они и занимаются, отображая одни многомерные пространства в другие. Например, результаты работы PCA и K-means в некотором смысле эквивалентны. Но обычно хочется сокращать размерность данных без особой возни с поиском параметров модели. Самым важным среди таких методов, конечно же, является SVD. «Почему SVD, а не PCA?» — спросите вы. Потому что SVD, во-первых, само по себе является отдельной важной методикой при анализе данных, а полученные в результате разложения матрицы имеют вполне осмысленную интерпретацию с точки зрения машинного обучения; во-вторых, его можно использовать для PCA и с некоторыми оговорками для NMF (как и других методов факторизации матриц); в-третьих, SVD можно приспособить для улучшения результатов работы ICA. Кроме того, у SVD нет таких неудобных свойств, как, например, применимость только к квадратным (разложения LU, Schur) или квадратным симметричным положительно определенным матрицам (Cholesky), или только к матрицам, элементы которых неотрицательны (NMF). Естественно, за универсальность приходится платить — сингулярное разложение довольно медленное; поэтому, когда матрицы слишком большие, применяют рандомизированные алгоритмы.

Что будет, если из исходного изображения вычесть средние значения каждого столбца, разделить полученную матрицу на корень квадратный из количества столбцов в исходной матрице, а потом выполнить сингулярное разложение? Оказывается, что столбцы матрицы V в полученном разложении в точности будут соответствовать главным компонентам, которые получаются при PCA (к слову, в R для PCA можно использовать функцию prcomp() )

Вернемся к вопросу выбора количества главных компонент. Капитанское правило такое: чем больше компонент, тем больше дисперсии они описывают. Andrew Ng, например, советует ориентироваться на >90% дисперсии. Другие исследователи утверждают, что это число может быть и 50%. Даже придуман так называемый параллельный анализ Хорна, который основывается на симуляции Монте-Карло. В R для этого и пакет есть. Совсем простой подход — использовать scree plot: на графике надо искать «локоть» и отбрасывать все компоненты, которые формируют пологую часть этого «локтя». На рисунке ниже, я бы сказал, надо учитывать 6 компонент:

В общем, как вы видите. вопрос неплохо проработан. Также бытует мнение, что PCA применим только для нормально распределенных данных, но Wiki с этим не согласна, и SVD/PCA можно использовать с данными любого распределения, но, конечно, не всегда результативно (что выясняется эмпирически).

Еще одно интересное разложение — это факторизация неотрицательных матриц, которая, как следует из названия, применяется для разложения неотрицательных матриц на неотрицательные матрицы:
X=WH.
В целом, такая задача не имеет точного решения (в отличие от SVD), и для ёё вычисления используют численные алгоритмы. Задачу можно сформулировать в терминах квадратичного программирования — и в этом смысле она будет близка к SVM. В проблеме же сокращения размерности пространства важным является вот что: если матрица Х имеет размерность m x n, то соответственно матрицы W и H имеют размерности m x k и k x n, и, выбирая k намного меньше самих m и n, можно значительно урезать эту самую исходную размерность. NMF любят применят для анализа текстовых данных, там, где неотрицательные матрицы хорошо согласуются с самой природой данных, но в целом спектр применения методики не уступает PCA. Разложение первой картинки в R дает такой результат:

Если требуется что-то более экзотичное

Какое отношение имеет ICA к задаче уменьшения размерности данных? Попробуем представить данные — вне зависимости от их природы — как смесь компонент, тогда можно будет разделить эту смесь на то количество «сигналов», которое нам подходит. Особого критерия, как в случае с PCA, по выбору количества компонент нет — оно подбирается экспериментально.

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

Вышеозначенный автоэнкодер несложно превратить в denoising autoencoder. Так как такому автокодировщику на вход надо подавать искаженные образы, перед первым скрытым слоем достаточно разместить dropout слой. Благодаря ему с некоторой вероятностью нейроны будут находиться в «выключенном» состоянии, что а) будет вносить искажения в обрабатываемый образ; б) будет служить своеобразной регуляризацией при обучении.
Еще одно интересное применение автоэнкодера — определение аномалий в данных по ошибке реконструкции образов. В целом, если подавать на вход автоэнкодера данные не из обучающей выборки, то, понятно, ошибка реконструкции каждого образа из новой выборки будет выше таковой из тренировочной выборки, но более-менее одного порядка. При наличии аномалий эта ошибка будет в десятки, а то и сотни раз больше.

Источник

Препарируем t-SNE

Работая над статьей «Глубокое обучение на R. », я несколько раз встречал упоминание t-SNE — загадочной техники нелинейного снижения размерности и визуализации многомерных переменных (например, здесь), был заинтригован и решил разобраться во всем в деталях. t-SNE это t-distributed stochastic neighbor embedding. Русский вариант с «внедрением соседей» в некоторой мере звучит нелепо, поэтому дальше буду использовать английский акроним.

Алгоритм t-SNE, который также относят к методам множественного обучения признаков, был опубликован в 2008 году (ссылка 1 в конце статьи) голландским исследователем Лоуренсом ван дер Маатеном (сейчас работает в Facebook AI Research) и чародеем нейронных сетей Джеффри Хинтоном. Классический SNE был предложен Хинтоном и Ровейсом в 2002 (ссылка 2). В статье 2008 года описывается несколько «трюков», которые позволили упростить процесс поиска глобальных минимумов, и повысить качество визуализации. Одним из них стала замена нормального распределения на распределение Стьюдента для данных низкой размерности. Кроме того, была сделана удачная реализация алгоритма (в статье есть ссылка на MatLab), которая потом портировалась в другие популярные среды.

Немного математики

Начнем с «классического» SNE и сформулируем задачу. У нас есть набор данных с точками, описываемыми многомерной переменной с размерностью пространства существенно больше трех. Необходимо получить новую переменную, существующую в двумерном или трехмерном пространстве, которая бы в максимальной степени сохраняла структуру и закономерности в исходных данных. SNE начинается с преобразования многомерной евклидовой дистанции между точками в условные вероятности, отражающие сходство точек. Математически это выглядит следующим образом (формула 1):

Эта формула показывает, насколько точка X_j близка к точке X_i при гауссовом распределении вокруг X_i с заданным отклонением σ. Сигма будет различной для каждой точки. Она выбирается так, чтобы точки в областях с большей плотностью имели меньшую дисперсию. Для этого используется оценка перплексии:

Где H(Pi) – энтропия Шеннона в битах (формула 2):

В данном случае перплексия может быть интерпретирована как сглаженная оценка эффективного количества «соседей» для точки X_i. Она задается в качестве параметра метода. Авторы рекомендуют использовать значение в интервале от 5 до 50. Сигма определяется для каждой пары X_i и X_j при помощи алгоритма бинарного поиска.

Для двумерных или трехмерных «коллег» пары X_i и X_j, назовем их для ясности Y_i и Y_j, не представляет труда оценить условную вероятность, используя ту же формулу 1. Стандартное отклонение предлагается установить в 1/√2:

Если точки отображения Y_i и Y_j корректно моделируют сходство между исходными точками высокой размерности X_i и X_j, то соответствующие условные вероятности p_j|i и q_j|i будут эквивалентны. В качестве очевидной оценки качества, с которым q_j|i отражает p_j|i, используется дивергенция или расстояние Кульбака-Лейблера. SNE минимизирует сумму таких расстояний для всех точек отображения при помощи градиентного спуска. Функция потерь для данного метода будет определяться формулой 3:

При этом градиент выглядит на удивление просто:

Авторы предлагают следующую физическую аналогию для процесса оптимизации: Все точки отображения соединены пружинами. Жесткость пружины, соединяющей точки i и j зависит от разности между сходством двух точек в многомерном пространстве и двух точек в пространстве отображения. В этой аналогии, градиент — это результирующая сила, действующая на точку в пространстве отображения. Если систему «отпустить», через какое-то время она придет в равновесие, это и будет искомое распределение. Алгоритмически, поиск равновесия предлагается делать с учетом моментов:

где η – параметр, определяющий скорость обучения (длину шага), а α – коэффициент инерции. Использование классического SNE позволяет получить неплохие результаты, но может быть связано с трудностями в оптимизации функции потерь и проблемой скученности (в оригинале – crowding problem). t-SNE если и не решает эти проблемы совсем, то существенно облегчает. Функция потерь t-SNE имеет два принципиальных отличая. Во-первых, у t-SNE симметричная форма сходства в многомерном пространстве и более простой вариант градиента. Во-вторых, вместо гауссова распределения для точек из пространства отображения используется t-распределение (Стьюдента), «тяжелые» хвосты которого облегчают оптимизацию и решают проблему скученности.

В качестве альтернативы минимизации суммы дивергенций Кульбака-Лейблера между условными вероятностями p_i|j и q_i|j предлагается минимизировать одиночную дивергенцию между совместной вероятностью P в многомерном пространстве и совместной вероятностью Q в пространстве отображения:

где p_ii и q_ii = 0, p_ij = p_ji, q_ij = q_ji для любых i и j, а p_ij определяется по формуле:

где n — количество точек в наборе данных. Градиент для симметричного SNE получается существенно проще, чем для классического:

Проблема скученности заключается в том, что расстояние между двумя точками в пространстве отображения, соответствующими двум среднеудаленным точкам в многомерном пространстве, должно быть существенно больше, нежели расстояние, которое позволяет получить гауссово распределение. Проблему решают хвосты Стьюдента. В t-SNE используется t-распределение с одной степенью свободы. Совместная вероятность для пространства отображения в этом случае будет определяться формулой 4:

А соответствующий градиент – выражением 5:

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

Алгоритм

Алгоритм t-SNE в упрощенном виде можно представить следующим псевдокодом:

Чтобы улучшить результат предлагается использовать два трюка. Первый авторы назвали «ранней компрессией». Его задача – заставить точки в пространстве отображения в начале оптимизации быть как можно ближе друг к другу. Когда дистанция между точками отображения невелика, перемещать один кластер через другой существенно легче. Так гораздо проще исследовать пространство оптимизации и «нацелиться» на глобальные минимумы. Ранняя компрессия создается за счет добавочного L2-штрафа в функции потерь, который пропорционален сумме квадратов дистанций точек отображения от начала координат (в исходном коде этого не нашел).

Второй трюк менее очевидный — «раннее гиперусиление» (в оригинале – «early exaggeration»). Заключается он в умножении в начале оптимизации всех p_ij на некоторое целое число, например на 4. Смысл в том, чтобы для больших p_ij получить бόльшие q_ij. Это позволит для кластеров в исходных данных получить плотные и широко разнесенные кластеры в пространстве отображения.

Реализация на R

В качестве исходного кода я взял оригинальную MatLab реализацию ван дер Маатена. Однако академическая лицензия на MatLab у меня давно закончилась, поэтому весь код я портировал на R. Код доступен в репозитарии. Также в моем распоряжении был код из архива R-пакета tsne, взял оттуда пару идей.

Для экспериментов предлагается использовать следующие параметры:
Количество итераций: 1000;
Перплексия: 40;
Раннее гиперусиление: х4 для первых 50 итераций;
Момент α: 0.5 для первых 250 итераций, 0.8 для оставшихся 750;
Скорость обучения η: первоначально 100 (в оригинальном коде — 500) и изменяется после каждой итерации в соответствие со схемой, описанной Робертом Джекобсом в 1988 (ссылка 3).

Проиллюстрирую только самые важные конструкции. Прежде всего, необходимо рассчитать матрицу квадратов евклидовой дистанции для исходного набора данных. Для этого лучше использовать функцию rdist() из пакета fields. Она работает в разы быстрее, чем популярная dist() из базового пакета stats. Возможно, это по тому, что она оптимизирована именно для евклидовой дистанции. Далее нужно инициализировать пространство отображения. Это можно сделать при помощи rnorm() с нулевым мат. ожиданием и стандартным отклонением 1е-4.

Расчет логарифма перплексии и гауссового ядра выглядит следующим образом:

Последнее выражение получается, если формулу (1) для p_j|i подставить формулу (2) для перплексии. Пусть n будет количеством точек в исходных данных. Di – вектор длины n-1, с квадратами попарных дистанций для строки исходного данных. Получается он при помощи конструкции Di

Источник