t-распределенное стохастическое вложение соседей - t-distributed stochastic neighbor embedding

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

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

t-SNE использовался для визуализации в широком спектре приложений, включая геномику , исследования компьютерной безопасности , обработку естественного языка, анализ музыки , исследования рака , биоинформатику , интерпретацию геологической области и обработку биомедицинских сигналов.

В то время как графики t-SNE часто кажутся отображающими кластеры , на визуальные кластеры может сильно влиять выбранная параметризация, и поэтому необходимо хорошее понимание параметров для t-SNE. Такие «кластеры» могут появляться даже в некластеризованных данных и, следовательно, могут быть ложными выводами. Таким образом, для выбора параметров и проверки результатов может потребоваться интерактивное исследование. Было продемонстрировано, что t-SNE часто может восстанавливать хорошо разделенные кластеры и при специальном выборе параметров приближается к простой форме спектральной кластеризации .

Подробности

Учитывая набор многомерных объектов , t-SNE сначала вычисляет вероятности , которые пропорциональны сходству объектов и , как показано ниже. ${\ displaystyle N}$${\ displaystyle \ mathbf {x} _ {1}, \ dots, \ mathbf {x} _ {N}}$${\ 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}}$

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

${\ 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}}$

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 }}}}$

и поставил . Здесь t-распределение Стьюдента с тяжелым хвостом (с одной степенью свободы, которое совпадает с распределением Коши ) используется для измерения сходства между точками низкой размерности, чтобы позволить разнородным объектам моделироваться далеко друг от друга на карте. . ${\ 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}}$

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

• В R пакет Rtsne реализует т-SnE в R .
• ELKI содержит tSNE, также с приближением Барнса-Хата
• Scikit-learn , популярный набор инструментов для машинного обучения на Python, реализует t-SNE как с точными решениями, так и с приближением Барнса-Хата.
• Tensorboard, набор для визуализации, связанный с TensorFlow , также реализует t-SNE ( онлайн-версия )

использованная литература

внешние ссылки

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