T-розподілене вкладення стохастичної близькості

Для даного набору ${\displaystyle N}$ багатовимірних об'єктів ${\displaystyle \mathbf {x} _{1},\dots ,\mathbf {x} _{N}}$ t-SNE спочатку обчислює ймовірності ${\displaystyle p_{ij}}$ пропорційні схожості ${\displaystyle \mathbf {x} _{i}}$ і ${\displaystyle \mathbf {x} _{j}}$ наступним чином:

${\displaystyle p_{j\mid i}={\frac {\exp(-\lVert \mathbf {x} _{i}-\mathbf {x} _{j}\rVert ^{2}/2\sigma _{i}^{2})}{\sum _{k\neq i}\exp(-\lVert \mathbf {x} _{i}-\mathbf {x} _{k}\rVert ^{2}/2\sigma _{i}^{2})}},}$

Ван дер Маатен та Гінтон пояснюють такий вибір відстані наступним чином: «подібність точки даних ${\displaystyle x_{j}}$ до точки даних ${\displaystyle x_{i}}$ — це умовна ймовірність, ${\displaystyle p_{j|i}}$, що ${\displaystyle x_{i}}$ вибрав би ${\displaystyle x_{j}}$ як свого сусіда, якби сусіди були обрані пропорційно їх гаусовій густині ймовірності з центром в ${\displaystyle x_{i}}$.»[1]

${\displaystyle p_{ij}={\frac {p_{j\mid i}+p_{i\mid j}}{2N}}}$

Більш того, коли ${\displaystyle i=j}$, ймовірності дорівнюють нулю: ${\displaystyle p_{ij}=0}$

Пропускна здатність Гаусового ядра ${\displaystyle \sigma _{i}}$встановлюється за допомогою методу бісекції так, що перплексивність умовного розподілу дорівнює попередньо визначеній перплексивності. У результаті пропускна здатність адаптується до густини даних: менші значення ${\displaystyle \sigma _{i}}$ використовуються у більш густих частинах даних.

Через те що Гаусове ядро використовує евклідову відстань ${\displaystyle \lVert x_{i}-x_{j}\rVert }$, то, у випадку дуже високої розмірності даних, слід мати на увазі ефект прокляття розмірності, коли відстані втрачають здатність до розділення і ${\displaystyle p_{ij}}$ стають дуже схожими (асимптотично, вони збігаються до константи). Для пом'якшення цього ефекту запропоновано[12] регулювати відстані степеневим перетворенням, спираючись на внутрішню розмірність кожної точки.

t-SNE намагається дізнатись ${\displaystyle d}$-вимірне відображення ${\displaystyle \mathbf {y} _{1},\dots ,\mathbf {y} _{N}}$ (де ${\displaystyle \mathbf {y} _{i}\in \mathbb {R} ^{d}}$), яке відображає подібність ${\displaystyle p_{ij}}$ наскільки це можливо. З цією метою він вимірює схожість ${\displaystyle q_{ij}}$ між двома точками відображення ${\displaystyle \mathbf {y} _{i}}$ та ${\displaystyle \mathbf {y} _{j}}$ за допомогою аналогічного підходу. Зокрема, ${\displaystyle q_{ij}}$ визначається як:

${\displaystyle q_{ij}={\frac {(1+\lVert \mathbf {y} _{i}-\mathbf {y} _{j}\rVert ^{2})^{-1}}{\sum _{k\neq l}(1+\lVert \mathbf {y} _{k}-\mathbf {y} _{l}\rVert ^{2})^{-1}}}}$

Тут використовується T-розподіл Стьюдента з обважнілим кінцем (з одним ступенем свободи, який є по суті розподілом Коші) для вимірювання подібностей між точками у низьковимірному просторі для того, щоб різнорідні об'єкти були змодельовані далеко один від одного при відображенні. Зверніть увагу, що в даному випадку ми прирівнюємо ${\displaystyle q_{ii}=0.}$

Координати точок ${\displaystyle \mathbf {y} _{i}}$ при відображенні визначаються шляхом мінімізації (несиметричної) відмінності по мірі Кульбака–Лейблера розподілу ${\displaystyle Q}$ від розподілу ${\displaystyle P}$, тобто:

${\displaystyle KL(P||Q)=\sum _{i\neq j}p_{ij}\log {\frac {p_{ij}}{q_{ij}}}}$

Мінімізація розбіжностей Кульбака–Лейблера по точкам ${\displaystyle \mathbf {y} _{i}}$ здійснюється за допомогою градієнтного спуску. Результатом такої оптимізації є відображення, яке добре зберігає подібність між входовими даними високої розмірності.

• t-SNE від Лоренса ван дер Маатена https://lvdmaaten.github.io/tsne/
• ELKI містить t-SNE. Див. https://github.com/elki-project/elki/blob/master/elki/src/main/java/de/lmu/ifi/dbs/elki/algorithm/projection/TSNE.java%5Bнедоступне+посилання+з+жовтня+2019%5D

• Візуалізація даних за допомогою t-SNE, Google Tech Talk про t-SNE
• Реалізація t-SNE різними мовами програмування, список посилань підтримує Лоренс ван дер Маатен
• Wattenberg, Martin; Viégas, Fernanda; Johnson, Ian (13 жовтня 2016). How to Use t-SNE Effectively. Distill (англ.) 1 (10). с. e2. ISSN 2476-0757. doi:10.23915/distill.00002. Процитовано 4 січня 2021.