Участник: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.

Схема реализации последовательного алгоритма

Входные параметры и данные: X - матрица высокоразмерных данных размерности n × D

perplexity - целевая перплексия (обычно между 5 и 50)

T - количество итераций

η - скорость обучения

d - размерность выходного пространства (обычно 2 или 3)

# 1. Предобработка данных (нормализация)
X = (X - np.mean(X, axis=0)) / np.std(X, axis=0)
# 2. Инициализация низкоразмерного представления
Y = np.random.normal(0, 1e-4, (n, d))
Y_prev = np.copy(Y)  # для хранения предыдущего состояния (импульс)
# 3. Вычисление попарных квадратов расстояний в высокоразмерном пространстве
D_high = np.zeros((n, n))
for i in range(n):
    for j in range(i+1, n):
        dist_sq = np.sum((X[i] - X[j])**2)
        D_high[i, j] = dist_sq
        D_high[j, i] = dist_sq

Вычисление совместных вероятностей P

def binary_search_perplexity(distances_i, target_perplexity, tol=1e-5, max_iter=50):
   Бинарный поиск для нахождения оптимальной дисперсии
   sigma_min, sigma_max = -np.inf, np.inf
   sigma = 1.0  # начальное предположение
   
   for iter in range(max_iter):
       # Вычисление условных вероятностей с текущей сигмой
       p_cond = np.exp(-distances_i * sigma)
       p_cond = p_cond / np.sum(p_cond)
       
       # Вычисление текущей перплексии
       entropy = -np.sum(p_cond * np.log2(p_cond + 1e-8))
       current_perplexity = 2 ** entropy
       
       # Корректировка границ поиска
       if abs(current_perplexity - target_perplexity) < tol:
           break
           
       if current_perplexity > target_perplexity:
           sigma_min = sigma
           sigma = sigma_max if np.isfinite(sigma_max) else sigma * 2
       else:
           sigma_max = sigma
           sigma = sigma_min if np.isfinite(sigma_min) else sigma / 2
   
   return p_cond
# Основной цикл вычисления P
P = np.zeros((n, n))
for i in range(n):
   p_conditional = binary_search_perplexity(D_high[i], perplexity)
   P[i] = p_conditional
# Симметризация
P = (P + P.T) / (2 * n)

Градиентный спуск

# Инициализация импульса
gain = np.ones((n, d))  # адаптивная скорость обучения
for t in range(T):
   # 1. Вычисление попарных расстояний в низкоразмерном пространстве
   dist_low = np.zeros((n, n))
   for i in range(n):
       for j in range(i+1, n):
           dist_sq = np.sum((Y[i] - Y[j])**2)
           dist_low[i, j] = dist_sq
           dist_low[j, i] = dist_sq  
   # 2. Вычисление матрицы Q (распределение Стьюдента)
   Q = 1.0 / (1.0 + dist_low)
   np.fill_diagonal(Q, 0)  # обнуляем диагональ
   Q = Q / np.sum(Q)
   Q = np.maximum(Q, 1e-12)   
   # 3. Вычисление градиента
   grad = np.zeros((n, d))
   for i in range(n):
       for j in range(n):
           if i != j:
               # Градиент
               factor = 4.0 * (P[i, j] - Q[i, j]) * Q[i, j] * (1.0 + dist_low[i, j])
               grad[i] += factor * (Y[i] - Y[j])    
   # 4. Обновление с импульсом и адаптивной скоростью обучения
   # Простой импульс
   Y_new = Y - eta * grad + momentum * (Y - Y_prev)   
   # 5. Обновление состояний для следующей итерации
   Y_prev = np.copy(Y)
   Y = Y_new

Последовательная сложность алгоритма

Основные операции:

1. Арифметические операции с вещественными числами
2. Вычисления exp и log
3. Операции с памятью
4. Сложность по фазам:

• Матрица расстояний в высокоразмерном пространстве:

Для каждой из O(n²) пар точек выполняется O(D) операций

• Совместные вероятности P: O(n²) с доминирующими exp/log

На каждой итерации:

Вычисление exp для n элементов: O(n)

Суммирование: O(n)

Вычисление энтропии: O(n)

Итого на точку: O(n)

Общая сложность фазы: O(n²) операций + O(n²) вычислений exp

• Градиентный спуск (T итераций): O(T·n²d)

Итеративный градиентный спуск

Детализация на одну итерацию:

Расстояния в низкоразмерном пространстве: O(n²d)

Вычисление Q: O(n²) (включая нормализацию)

Вычисление градиента: O(n²d)

Обновление позиций: O(nd)

Итого на итерацию: O(n²d)

Общая последовательная сложность: O(n²(D + T·d))

Литература

van der Maaten L., Hinton G. Visualizing Data using t-SNE // Journal of Machine Learning Research. 2008. Vol. 9. P. 2579–2605.

Erich Schubert, Michael Gertz. Intrinsic t-Stochastic Neighbor Embedding for Visualization and Outlier Detection // SISAP 2017 – 10th International Conference on Similarity Search and Applications. — 2017.