WikiDer > T-распределенное стохастическое вложение соседей

t-распределенное стохастическое вложение соседей (t-SNE) это машинное обучение алгоритм для визуализация основан на стохастическом соседнем встраивании, первоначально разработанном Сэмом Роуисом и Джеффри Хинтон,^[1] куда Лоренс ван дер Маатен предложил т-распределенный вариант.^[2] Это уменьшение нелинейной размерности Техника хорошо подходит для встраивания данных большой размерности для визуализации в двух- или трехмерном пространстве низкой размерности. В частности, он моделирует каждый многомерный объект двух- или трехмерной точкой таким образом, что аналогичные объекты моделируются ближайшими точками, а разные объекты с высокой вероятностью моделируются удаленными точками.

Алгоритм t-SNE состоит из двух основных этапов. Сначала t-SNE конструирует распределение вероятностей над парами объектов большой размерности таким образом, что похожим объектам присваивается более высокая вероятность, а разным точкам - более низкая вероятность. Во-вторых, t-SNE определяет аналогичное распределение вероятностей по точкам на карте малой размерности и минимизирует Дивергенция Кульбака – Лейблера (Расхождение KL) между двумя распределениями относительно расположения точек на карте. В то время как исходный алгоритм использует Евклидово расстояние между объектами в качестве основы его метрики подобия, это можно изменить при необходимости.

t-SNE использовался для визуализации в широком спектре приложений, включая компьютерная безопасность исследование,^[3] музыкальный анализ,^[4] исследования рака,^[5] биоинформатика,^[6] и обработка биомедицинских сигналов.^[7] Он часто используется для визуализации высокоуровневых представлений, изученных искусственная нейронная сеть.^[8]

Хотя графики t-SNE часто кажутся кластеры, выбранная параметризация может сильно влиять на визуальные кластеры, поэтому необходимо хорошее понимание параметров t-SNE. Такие «кластеры» могут появляться даже в некластеризованных данных,^[9] а значит, могут быть ложные выводы. Таким образом, для выбора параметров и проверки результатов может потребоваться интерактивное исследование.^[10][11] Было продемонстрировано, что t-SNE часто может восстанавливать хорошо разделенные кластеры и при специальном выборе параметров приближается к простой форме спектральная кластеризация.^[12]

Подробности

Учитывая набор ${ displaystyle N}$ многомерные объекты ${ displaystyle mathbf {x} _ {1}, dots, mathbf {x} _ {N}}$, t-SNE сначала вычисляет вероятности ${ displaystyle p_ {ij}}$ которые пропорциональны подобию предметов ${ Displaystyle mathbf {х} _ {я}}$ и ${ displaystyle mathbf {x} _ {j}}$, следующее.

За ${ displaystyle i neq 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 p_ {i mid i} = 0}$. Обратите внимание, что ${ displaystyle sum _ {j} p_ {j mid i} = 1}$ для всех ${ displaystyle i}$.

Как объяснили Ван дер Маатен и Хинтон: «Сходство точки данных ${ displaystyle x_ {j}}$ датировать ${ displaystyle x_ {i}}$ - условная вероятность, ${ displaystyle p_ {j | i}}$, который ${ displaystyle x_ {i}}$ выбрал бы ${ displaystyle x_ {j}}$ в качестве своего соседа, если бы соседи были выбраны пропорционально их плотности вероятности при гауссиане с центром в ${ displaystyle x_ {i}}$."^[2]

Теперь определим

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

и обратите внимание, что ${ displaystyle p_ {ij} = p_ {ji}}$, ${ displaystyle p_ {ii} = 0}$, и ${ Displaystyle сумма _ {я, j} p_ {ij} = 1}$.

Пропускная способность Гауссовы ядра ${ displaystyle sigma _ {я}}$ устанавливается таким образом, что недоумение условного распределения равняется заранее заданной сложности с использованием метод деления пополам. В результате полоса пропускания адаптируется к плотность данных: меньшие значения ${ displaystyle sigma _ {я}}$ используются в более плотных частях пространства данных.

Поскольку ядро ​​Гаусса использует евклидово расстояние ${ displaystyle lVert x_ {i} -x_ {j} rVert}$, на него влияет проклятие размерности, а в данных большой размерности, когда расстояния теряют способность различать, ${ displaystyle p_ {ij}}$ становятся слишком похожими (асимптотически они сходятся к константе). Было предложено регулировать расстояния с помощью степенного преобразования на основе внутреннее измерение каждой точки, чтобы облегчить это.^[13]

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 i neq j}$, определять ${ displaystyle q_ {ij}}$ в качестве

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

и установить ${ displaystyle q_ {ii} = 0}$. Здесь хвостатый Распределение Стьюдента (с одной степенью свободы, что аналогично Распределение Коши) используется для измерения сходства между точками низкой размерности, чтобы можно было смоделировать разнородные объекты далеко друг от друга на карте.

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

${ displaystyle mathrm {KL} left (P parallel Q right) = sum _ {i neq j} p_ {ij} log { frac {p_ {ij}} {q_ {ij}}} }$

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

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

• ELKI содержит tSNE, также с приближением Барнса-Хата
• Scikit-Learn, популярный инструментарий машинного обучения на Python реализует t-SNE как с точными решениями, так и с приближением Барнса-Хата.

Рекомендации

внешняя ссылка

• Визуализация данных с помощью t-SNE, Google Tech Talk о t-SNE
• Реализации t-SNE на разных языках, Коллекция ссылок, которую поддерживает Лоренс ван дер Маатен