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

«ЦНЕ» перенаправляет сюда. Для организации из Бостона см. Третий сектор Новой Англии.

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 {x} _{i}}$ и ${\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 \sum _{i,j}p_{ij}=1}$.

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

Поскольку ядро ​​Гаусса использует евклидово расстояние ${\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 как с точными решениями, так и с приближением Барнса-Хата.

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

1. Роуис, Сэм; Хинтон, Джеффри (январь 2002 г.). Стохастическое вложение соседа (PDF). Системы обработки нейронной информации.
2. van der Maaten, L.J.P .; Хинтон, Г. (Ноябрь 2008 г.). «Визуализация данных с помощью t-SNE» (PDF). Журнал исследований в области машинного обучения. 9: 2579–2605.
3. Гаши, I .; Станкович, В .; Leita, C .; Тоннард, О. (2009). «Экспериментальное исследование разнообразия с помощью готовых антивирусных механизмов». Материалы Международного симпозиума IEEE по сетевым вычислениям и приложениям: 4–11.
4. Hamel, P .; Экк, Д. (2010). «Возможности обучения из музыкального аудио в сетях глубокого убеждения». Материалы конференции Международного общества поиска информации о музыке: 339–344.
5. Jamieson, A.R .; Giger, M.L .; Drukker, K .; Луи, H .; Yuan, Y .; Бхошан, Н. (2010). «Изучение уменьшения размерности пространства нелинейных признаков и представления данных в CADx груди с помощью лапласовских собственных карт и t-SNE». Медицинская физика. 37 (1): 339–351. Дои:10.1118/1.3267037. ЧВК  2807447. PMID  20175497.
6. Wallach, I .; Лилиан, Р. (2009). «База данных« белок-малые молекулы », неизбыточный структурный ресурс для анализа связывания белок-лиганд». Биоинформатика. 25 (5): 615–620. Дои:10.1093 / биоинформатика / btp035. PMID  19153135.
7. Birjandtalab, J .; Pouyan, M. B .; Нурани, М. (01.02.2016). Нелинейное уменьшение размеров для обнаружения эпилептических припадков на основе ЭЭГ. Международная конференция IEEE-EMBS по биомедицинской и медицинской информатике (BHI), 2016 г.. С. 595–598. Дои:10.1109 / BHI.2016.7455968. ISBN  978-1-5090-2455-1. S2CID  8074617.
8. Визуализация репрезентаций: глубокое обучение и человеческие существа Блог Кристофера Олаха, 2015 г.
9. «К-означает кластеризацию на выходе t-SNE». Перекрестная проверка. Получено 2018-04-16.
10. Пеццотти, Никола; Lelieveldt, Boudewijn P. F .; Маатен, Лоуренс ван дер; Холлт, Томас; Эйсеманн, Эльмар; Виланова, Анна (01.07.2017). «Приблизительный и управляемый пользователем tSNE для прогрессивной визуальной аналитики». IEEE Transactions по визуализации и компьютерной графике. 23 (7): 1739–1752. arXiv:1512.01655. Дои:10.1109 / tvcg.2016.2570755. ISSN  1077-2626. PMID  28113434. S2CID  353336.
11. Ваттенберг, Мартин; Вьегас, Фернанда; Джонсон, Ян (2016-10-13). «Как эффективно использовать t-SNE». Дистиллировать. Получено 4 декабря 2017.
12. Линдерман, Джордж С .; Штайнербергер, Стефан (8 июня 2017 г.). «Кластеризация с t-SNE, доказуемо». arXiv:1706.02582 [cs.LG ].
13. Шуберт, Эрих; Герц, Майкл (2017-10-04). Внутреннее t-стохастическое вложение соседей для визуализации и обнаружения выбросов. SISAP 2017 - 10-я Международная конференция по поиску и применению подобия. С. 188–203. Дои:10.1007/978-3-319-68474-1_13.

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

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