Участник: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}} $$ Минимизация осуществляется с помощью метода градиентного спуска.
Результатом оптимизации является отображение, которое отражает похожесть между объектами пространства высокой размерности.
Вычислительное ядро алгоритма
Вычислительное ядро №1: Построение матрицы схожестей в высокоразмерном пространстве
Вычисление попарных расстояний между всеми точками: O(N²)
Бинарный поиск дисперсий σᵢ для каждой точки для достижения заданной перплексии
Расчет и симметризация условных вероятностей
Вычислительное ядро №2: Минимизация расхождения Кульбака-Лейблера
Расчет попарных расстояний в низкоразмерном пространстве: O(N²)
Вычисление градиента
Обновление координат точек
Оба этапа имеют квадратичную сложность O(N²) относительно числа точек. Основные операции — вычисление попарных расстояний и вероятностных распределений.
Макроструктура алгоритма
Построение графа сходств в высокоразмерном пространстве
1. Расстояния: Рассчитать матрицу попарных расстояний для исходных данных.
2. Вероятности: На основе расстояний и заданной перплексии построить матрицу совместных вероятностей P, которая представляет собой взвешенный и симметризованный граф сходств.
Оптимизация низкоразмерного представления
1. Инициализация: Случайно разместить точки в целевом пространстве.
2. Цикл оптимизации (повторять T раз):
- Рассчитать сходства Q: По текущим позициям точек в низкоразмерном пространстве рассчитать новую матрицу сходств Q с помощью тяжелых хвостов распределения Стьюдента.
- Рассчитать градиент: Оценить направление улучшения, вычислив градиент между P и Q.
- Обновить позиции: Сдвинуть точки в направлении, минимизирующем расхождение между P и Q.