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

Шаблон:Машинне навчання Шаблон:Унаочнення даних T-розподілене вкладення стохастичної близькості (Шаблон:Lang-en, t-SNE) — це метод машинного навчання візуалізації даних, розроблений Лоренсом ван дер Маатеном і Джефрі Гінтоном. Це зручний Шаблон:Нп шляхом вкладення багатовимірних даних у дво- або тривимірний простір для подальшої візуалізації. Зокрема, він відображає кожну точку багатовимірного простору в дво- або тривимірну точку евклідового простору так, що подібні об'єкти розташовуються поруч, а несхожі об'єкти відповідають віддаленим точкам з високою ймовірністю.

Алгоритм t-SNE складається з двох основних етапів. Спочатку, t-SNE створює розподіл імовірностей по парах багатовимірних об'єктів таким чином, що подібні об'єкти мають високу ймовірність бути вибраними, у той час як несхожі точки мають надзвичайно малу ймовірність бути вибраними разом. Далі, t-SNE визначає подібний розподіл ймовірностей для точок у карті низьковимірного простору та мінімізує розбіжності за відстанню Кульбака–Лейблера між двома розподілами за місцем розташування точок на карті. Зверніть увагу, що хоч оригінальний алгоритм і використовує евклідову відстань між об'єктами, як основну метрику подібності об'єктів, проте, вона може бути змінена при необхідності.

t-SNE використовується для візуалізації в різноманітних застосунках, таких як дослідження по комп'ютерній безпеці, аналізу музики, Шаблон:Нп, біоінформатики, та біомедичній обробці сигналів. Він часто використовується для візуалізації високорівневих представлень, отриманих за допомогою штучної нейронної мережі.

Хоча візуалізації отримані за допомогою t-SNE часто використовуються для відображення кластерів, отримане зображення може суттєво залежати від обраної параметризації і тому потрібне глибоке розуміння параметрів, які використовуються для t-SNE. Навіть для некластеризованих даних можуть з'явитись «кластери», що може привести до помилкових висновків. Тим самим, для правильного підбору параметрів і перевірки результатів може бути потрібне інтерактивне дослідження даних. Було продемонстровано, що t-SNE часто здатний відновлювати добре розділені кластери, та зі спеціальним вибором параметрів, він наближається до простої форми спектральної кластеризації.

Деталі

Для даного набору $N$ багатовимірних об'єктів ${𝐱}_1,\dots ,{𝐱}_N$ t-SNE спочатку обчислює ймовірності $p_{ij}$ пропорційні схожості ${𝐱}_i$ і ${𝐱}_j$ наступним чином:

$p_{j\mid i}=\frac{\exp (-\Vert {𝐱}_i-{𝐱}_j{\Vert }^2/2{\sigma }_i^2)}{\sum _{k\ne i}\exp (-\Vert {𝐱}_i-{𝐱}_k{\Vert }^2/2{\sigma }_i^2)},$

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

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

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

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

Через те що Гаусове ядро використовує евклідову відстань $\Vert x_i-x_j\Vert$, то, у випадку дуже високої розмірності даних, слід мати на увазі ефект прокляття розмірності, коли відстані втрачають здатність до розділення і $p_{ij}$ стають дуже схожими (асимптотично, вони збігаються до константи). Для пом'якшення цього ефекту запропоновано регулювати відстані степеневим перетворенням, спираючись на Шаблон:Нп кожної точки.

t-SNE намагається дізнатись $d$-вимірне відображення ${𝐲}_1,\dots ,{𝐲}_N$ (де ${𝐲}_i\in {ℝ}^d$), яке відображає подібність $p_{ij}$ наскільки це можливо. З цією метою він вимірює схожість $q_{ij}$ між двома точками відображення ${𝐲}_i$ та ${𝐲}_j$ за допомогою аналогічного підходу. Зокрема, $q_{ij}$ визначається як:

$q_{ij}=\frac{(1+\Vert {𝐲}_i-{𝐲}_j{\Vert }^2{)}^{-1}}{\sum _{k\ne l}(1+\Vert {𝐲}_k-{𝐲}_l{\Vert }^2{)}^{-1}}$

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

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

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

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

Програмне забезпечення

• t-SNE від Лоренса ван дер Маатена https://lvdmaaten.github.io/tsne/ Шаблон:Webarchive
• Шаблон:Нп містить t-SNE. Див. https://github.com/elki-project/elki/blob/master/elki/src/main/java/de/lmu/ifi/dbs/elki/algorithm/projection/TSNE.javaШаблон:Недоступне посилання

Посилання

• Візуалізація даних за допомогою t-SNE Шаблон:Webarchive, Google Tech Talk про t-SNE
• Реалізація t-SNE різними мовами програмування Шаблон:Webarchive, список посилань підтримує Лоренс ван дер Маатен
• Шаблон:Cite news