Участник:USKoroleva/t-sne

Свойства и структура алгоритмов

Общее описание алгоритма

T-распределенное стохастическое вложение соседей (t-Distributed Stochastic Neighbor Embedding) — это алгоритм, предназначенный для визуализации высокоразмерных данных. Он относится к классу алгоритмов нелинейного снижения размерности (non-linear dimensionality reduction). Основная задача t-SNE — преобразование многомерных данных в пространство более низкой размерности (обычно 2D или 3D) таким образом, чтобы сохранить структуру локальных соседств. Другими словами, алгоритм предназначен для того, чтобы точки данных, которые были близки друг к другу в исходном высокоразмерном пространстве, оставались близкими в новом пространстве, а далекие точки оставались далекими.

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

В отличие от линейных методов, таких как PCA (Principal Component Analysis), t-SNE способен улавливать сложные, нелинейные зависимости между данными.

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

В основе t-SNE лежит вероятностный подход. Он не вычисляет прямое расстояние между точками, а вместо этого моделирует распределения вероятностей, которые отражают схожести между точками.

Математическое описание алгоритма

Алгоритм работает в два этапа:

Построение распределения вероятностей в высокоразмерном пространстве.

Если дан набор из n объектов высокой размерности $$\mathbf{x}_1, \mathbf{x}_2, ..., \mathbf{x}_n,$$ то для каждой пары точек данных исходного пространства вычисляются вероятности $$p_{j|i}$$ вероятность того, что объект i выберет объект j в качестве соседа. Эта вероятность пропорциональна гауссовскому распределению, центрированному вокруг точки i. $$ p_{j|i} = \frac{\exp\left(-||\mathbf{x}_i - \mathbf{x}_j||^2 / 2\sigma_i^2\right)}{\sum_{k \neq i} \exp\left(-||\mathbf{x}_i - \mathbf{x}_k||^2 / 2\sigma_i^2\right)} $$ $$\sigma_i \text{— дисперсия гауссова распределения для объекта i}$$ Дисперсия подбирается для каждого объекта так, чтобы энтропия распределения достигла заданного значения (параметр перплексии), оно определяет количество ближайших соседей, которые точка будет учитывать при построении распределения.

Затем условные вероятности симметризуются, чтобы получить совместное распределение p в высокоразмерном пространстве: $$ p_{ij} = \frac{p_{j|i} + p_{i|j}}{2n} $$ Чем больше полученное значение, тем более похожи объекты в исходном пространстве.

Построение распределения вероятностей и оптимизация в пространстве низкой размерности.

Алгоритм t-SNE стремится получить отображение $$\mathbf{y}_{1},\dots,\mathbf{y}_{N}$$ в D-мерное пространство $$\mathbf{y}_{i}\in \mathbb{R}^{d}$$ которое отражает похожести, насколько это возможно.

В низкоразмерном пространстве для объектов определяется аналогичное распределение схожести. Однако вместо гауссова распределения используется t-распределение Стьюдента с одной степенью свободы(распределение Коши). Это ключевое отличие, которое решает проблему "скукоживания". $$ q_{ij} = \frac{(1 + \|\mathbf{y}_i - \mathbf{y}_j\|^2)^{-1}}{\sum_{k \neq l} (1 + \|\mathbf{y}_k - \mathbf{y}_l\|^2)^{-1}} $$ t-распределение имеет более тяжелые "хвосты", что позволяет точкам в низкоразмерном пространстве "разбегаться" и более эффективно моделировать умеренные расстояния.

Алгоритм итеративно обновляет положения точек в низкоразмерном пространстве, минимизируя расхождение Кульбака-Лейблера между двумя распределениями P и Q $$ KL(P \mid \mid Q) = \sum_{i \neq j} p_{ij} \log\frac{p_{ij}}{q_{ij}} $$ Минимизация осуществляется с помощью метода градиентного спуска.

Результатом оптимизации является отображение, которое отражает похожесть между объектами пространства высокой размерности.