Изменения

[[Файл:MNIST_compression_methods_comparison.png|300px|thumb|right|Пример работы методов [[Стохастическое вложение соседей с t-распределением|t-SNE]], Isomap<ref>[https://en.wikipedia.org/wiki/Isomap Isomap]</ref>, Sammon mapping<ref>[https://en.wikipedia.org/wiki/Sammon_mapping Sammon mapping]</ref>, LLE <ref>[https://en.wikipedia.org/wiki/Nonlinear_dimensionality_reduction#Manifold_learning_algorithms Manifold learning algorithms]</ref> на dataset-е наборе данных [[Известные наборы данных|MNIST]] '''Стохастическое вложение соседей с t-распределением''' (англ. ''t-Distributed Stochastic Neighbor Embedding, t-SNE'') {{---}} алгоритм визуализации высокоразмерных данных с помощью представления каждой точки данных в двух или трехмерном пространстве. Данный алгоритм является модификацией cтохастического вложения соседей, который будет описан далее.]]

Пусть стоит задача вложить высокоразмерные точки множество точек в пространстве высокой размерности <tex>\{x_i \mid x_i \in X\}</tex> в низкоразмерное пространствонизкой размерности. Обозначим точкимножество точек в пространстве низкой размерности, которые получаются после вложения через <tex>\{y_i \mid y_i \in Y\}</tex>. '''Стохастическое вложение соседей''' (англ. ''Stochastic Neighbor Embedding, SNE'') конвертирует расстояния в высокоразмерном Евклидовом пространстве высокой размерности между точками в условные вероятности <tex>p_{j|i}</tex>. <tex>p_{j|i}</tex> {{- --}} вероятность, что точка <tex>x_i</tex> выберет в качестве своего соседа точку <tex>x_j</tex> среди остальных точек данных. Будем считать, что вероятность для точки <tex>x_i</tex> найти соседа падает с увеличением расстояния от точки <tex>x_i</tex> в соответствии с распределением Гаусса<ref>[https://ru.wikipedia.org/wiki/Нормальное_распределение Нормальное распределение]</ref> с нулевым [[Математическое ожидание случайной величины|математическим ожиданием]] и [[Дисперсия случайной величины|стандартным отклонением]] <tex>\sigma_i</tex>. В соответствии с этим <tex>p_{j|i}</tex> выражается как

<tex>p_{j|i} = \fracdfrac{\exp{(-\dfrac{{\left\Vert x_i - x_j \right\Vert}^2/}{2\sigma_i^2})}}{\sum\limits_{k \neq i}\exp{(\dfrac{{-\left\Vert x_i - x_k \right\Vert}^2/}{2\sigma_i^2})}}</tex>.

Теперь определим похожие вероятности <tex>q_{i|j}</tex> для низкоразмерного пространстванизкой размерности, куда вкладываются высокоразмерные точкипространства высокой размерности.

<tex>q_{j|i} = \fracdfrac{\exp{(-{\left\Vert y_i - y_j \right\Vert}^2)}}{\sum\limits_{k \neq i}\exp{({-\left\Vert x_i y_i - x_k y_k \right\Vert}^2)}}</tex>.

Заметим, что данное распределение получается Данные вероятности получаются из тех же самых предложений, что были сделаны для высокоразмерного пространствавысокой размерности, за исключением того, что все распределения Гаусса имеют стандартное отклонение <tex>\fracdfrac{1}{\sqrt{2}}</tex> для всех точек.

Если удастся хорошо вложить высокоразмерное одно пространство в низкоразмерноедругое, должны совпасть распределения совместных вероятностей. То есть <tex>p_{i|j}</tex> должны стать похожими на <tex>q_{i|j}</tex>. В связи с этим SNE пытается уменьшить разницу в распределении вероятностей. Стандартной мерой для измерения различия вероятностей служит дивергенция Кульбака-Лейблера<ref>[https://ru.wikipedia.org/wiki/Расстояние_Кульбака_—_Лейблера Расстояние Кульбака—Лейблера]</ref>. Определяется она так:

<tex>KL(P \Vert Q) = \sum\limits_j p_j \log_2 \fracdfrac{p_j}{q_j}</tex>.

В данном случае имеем <tex>|X|</tex> распределений. Тогда целевую функцию<ref>[https://ru.wikipedia.org/wiki/Целевая_функция Целевая функция]</ref>, который которую будем оптимизировать, определим как сумму соответствующих дивергенций Кульбака-Лейблера. То есть:

<tex>C = \sum\limits_i KL(p_i \Vert q_i) = \sum\limits_i \sum\limits_j p_{j|i} \log_2 \fracdfrac{p_{j|i}}{q_{j|i}}</tex>.

Параметры <tex>\sigma_i</tex> подбираются следующим образом. Каждое значение параметра порождает свое распределение вероятностей <tex>P_i</tex>. Это распределение имеет энтропию<ref>[https://ru.wikipedia.org/wiki/Информационная_энтропия Информационная энтропия]</ref><tex>H(P_i) = \sum\limits_j p_{j|i}\log_2 p_{j|i} </tex>, которая возрастает с ростом <tex>\sigma_i</tex>. В самом алгоритме <tex>\sigma_i</tex> вычисляются с помощью [[Вещественный двоичный поиск|вещественного двоичного поиска]] по заранее заданной пользователем величине, называемой перплексией<ref>[https://en.wikipedia.org/wiki/Perplexity Perplexity]</ref>: <tex>Perp(P_i) = 2 ^ {H(P_i)}</tex>.

Изначально точки <tex>H(P_i) = \sum\limits_j p_{j|i}\log_2 p_{j|i} y_i</tex>сэмплируют в пространстве низкой размерности в соответствии с распределением Гаусса с маленьким стандартным отклонением с математическим ожиданием в нуле,далее идет оптимизация целевой функции. Она проводится [[Стохастический градиентный спуск|методом градиентного спуска]]. Градиент равен:

которая возрастает с ростом <tex>\sigma_i</tex>. В самом алгоритме <tex>dfrac {\delta C} {\delta y_i} = 2 \sum\sigma_ilimits_j (p_{j|i} - q_{j|i} + p_{i|j} - q_{i|j})(y_i - y_j)</tex> вычисляются с помощью бинарного поиска по заранее заданной пользователем величине, называемой перплексией<ref>[https://en.wikipedia.org/wiki/Perplexity Perplexity]</ref>, которая определяется как

<tex>Perp(P_i) = 2 ^ {H(P_i)}</tex>.= Физическая интерпретация ==

Изначально точки Есть следующая физическая интерпретация модели. В пространстве низкой размерности натянуты пружины между каждой парой точек <tex>y_i</tex> сэмплируют и <tex>y_j</tex>, действующие в низкоразмерном пространстве направлении <tex>y_i - y_j</tex>. Пружины могут притягивать или отталкивать точки в соответствии с Гауссовским распределением с маленьким стандартным отклонением с математическим ожиданием в нулезависимости от расстояния между ними. Сила, прикладываемая пружиной, далее идет оптимизация целевой функциипропорциональна её длине <tex>\left\Vert y_i - y_j \right\Vert</tex> и жесткости<ref>[https://ru.wikipedia. Она проводится [[Стохастический градиентный спускorg/wiki/Жёсткость Жесткость]</ref> <tex>p_{j|i} - q_{j|i} + p_{i|j} - q_{i|методом градиентного спуска]]j}</tex>. Оптимизация функционала в данной интерпретации эквивалентна поиску положения точек, в котором будет наблюдаться равновесие сил. Градиент равен:

<tex>\frac {\delta C} {\delta y_i} = 2 \sum\limits_j (p_{j|i} - q_{j|i} + p_{i|j} - q_{i|j})(y_i - y_j)</tex> == Физическая интерпретация Симметричное стохастическое вложение соседей ==

Есть следующая физическая интерпретация моделиСледующая модификация SNE носит название '''симметричное стохастическое вложение соседей''' (англ. Между точками в низкоразмерном пространстве натянуты пружины между каждой парой точек <tex>y_i</tex> и <tex>y_j</tex>. действующие в направлении <tex>y_i - y_j</tex>. Пружины могут притягивать или отталкивать точки в зависимости от расстояния между ними. Сила''Symmetric Stochastic Neighbor Embedding, прикладываемая пружинойSymmetric SNE''), пропорциональна её длине <tex>\left\Vert y_i - y_j \right\Vert</tex> и жесткости <tex>p_{j|i} которая будет использоваться дальше в t- q_{j|i} + p_{i|j} - q_{i|j}</tex>SNE. Оптимизация функционала Симметричный SNE в данном случае эквивалентна поиску положения точек, в котором будет наблюдаться равновесие силкачестве альтернативы использует совместные вероятности вместо условных.Теперь:

<tex>C =KL(P \Vert Q) = Симметричное стохастическое вложение соседей ==\sum\limits_i \sum\limits_j p_{i j} \log_2 \dfrac {p_{i j}} {q_{i j}}</tex>.

Следующая модификация SNE носит название '''симметричное стохастическое вложение соседей''' (англ. ''Symmetric Stochastic Neighbor Embedding, Symmetric SNE''). Было странно, что в классическом SNE Очевидным образом можно определить <tex>p_{j|i} \neq p_{i|j}</tex> и <tex>q_{j|i} \neq q_{i|j}</tex>. Симметричный SNE {{---}} попытка исправить эту ситуацию путем определения совместных вероятностей вместо условных. Теперь:

<tex>C q_{i j} = KL\dfrac {\exp (P { -{\left\Vert Q) = y_i - y_j \sumright\limits_i Vert}^2 }) } {\sum\limits_j p_limits_{i jk \neq l} \log_2 \frac exp ({p_-{i j\left\Vert y_k - y_l \right\Vert}} {q_{i j^2) }}</tex>.,

Очевидным но то же решение для <tex>p_{i j}</tex> привело бы к проблеме, что для [[Выброс|выброса]] <tex>x_i</tex> <tex>p_{i j}</tex> будет очень маленькой для любого <tex>x_j</tex>. Таким образом определяется , будет почти нулевой соответствующая дивергенция Кульбака-Лейблера для любого распределения <tex>q_{i j}</tex>:. Это означало бы, что положение точки <tex>y_i</tex> определялось бы очень неточно относительно положения других точек и не было бы особой разницы в том, где она расположена.

Таким образом, в симметричном SNE в качестве <tex>q_p_{i j} = \frac {\exp { -{\left\Vert y_i - y_j \right\Vert}^2 } } {\sum\limits_{k \neq l} \exp { -{\left\Vert y_k - y_l \right\Vert}^2 } }</tex>,рассматривается следующая величина:

но то же решение для <tex>p_{i j}</tex> привело бы к проблеме, что для [[Выброс|выброса]] <tex>x_i</tex> <tex>= \dfrac {p_{i |j}</tex> будет очень маленькой для любого <tex>x_j</tex>, таким образом будет почти нулевой соответствующая дивергенция Кульбака-Лейблера для любого распределения <tex>q_+ p_{j|i j}</tex>. Это означало бы, что положение точки <tex>y_i</tex> определялось бы очень неточно относительно положения других точек. Поэтому в t-SNE <tex>p_} {i j2|X|}</tex> определили как:.

Очевидный плюс в том, что <tex>\sum\limits_j p_{i j} = > \frac dfrac 1 {2|X|}</tex> для всех точек, что хорошо скажется на выбросах. А также теперь <tex>p_{i|j} + = p_{j i}</tex>, <tex>q_{i|j} } = q_{2|X|j i}</tex>.

Очевидный плюс такого определения в том, что <tex>\sum\limits_j p_{i j} > \frac 1 {2|X|}</tex> для всех точек, что хорошо скажется на выбросах. А также теперь <tex>p_{i j} = p_{j i}</tex>, <tex>q_{i j} = q_{j i}</tex>. Авторами утверждаетсяАвторы утверждают, что симметричный SNE вкладывает данные в низкоразмерное пространство низкой размерности почти также так же как и ассиметричный, а иногда даже лучше.

<tex>\frac dfrac {\delta C} {\delta y_i} = 2 \sum\limits_j (p_{i j} - q_{i j})(y_i - y_j)</tex>.

Необходимо понимать, что невозможно абсолютно точно моделировать расстояния между точками пространства высокой размерности в низком. Например, в десятимерном пространстве существует <tex>11</tex> равноудаленных друг от друга точек, в то время как на плоскости может быть максимум <tex>3</tex> равноудаленные точки. При использовании обычного SNE возникает следующая проблема, которая вытекает из разного распределения вероятностей в высокоразмерном пространствах высокой и низкоразмерном пространствахнизкой размерностей. Пусть есть некоторое высокоразмерное пространствовысокой размерности. Пусть в нем точки <tex>x_i</tex> равномерно распределены в нем вокруг некоторой точки <tex>x_ix_0</tex>. Теперь попытаемся вложить высокоразмерное пространство в низкоразмерноенекотором шаре с радиусом <tex>R</tex>. Заметим, что область , чем больше размерность пространства, доступная для размещения умеренно-удаленных тем больше точек высокоразмерного пространства относительно области пространствапопадет рядом с границей шара, доступное для размещения поэтому количество близких к <tex>x_0</tex> точек высокоразмерного пространства достаточно мала по сравнению с тем же самым ростом размерности будет убывать. Теперь попытаемся вложить данное пространство в плоскость. Пусть точки <tex>x_i</tex> перешли в точки <tex>y_i</tex> на плоскости. Заметим, что если попытаться вложить точки <tex>x_i</tex> в круг радиуса <tex>R</tex> с центром в точке <tex>y_0</tex> образуется большое количество маленьких расстояний между точками <tex>y_i</tex>, т.к. объем сферы в исходном высокомерном пространстве (нужно сравнить отношения объемов сфер в низкоразмерном и высокоразмерном пространствах)несопоставим с площадью круга на плоскости. Таким образом, если мы хотим правильно моделировать маленькие расстояния и не иметь их в низкоразмерном пространстве между умеренно-удаленными точками высокоразмерного пространствана плоскости, следовало бы поместить умеренно-удаленные точки подальше от <tex>x_0</tex> точки <tex>x_i</tex>ещё дальше, чем в исходномпространстве. В Но в таком случае , вспоминая физическую интерпретацию, на слишком эти далекие соответствующие им точки в низкоразмерном пространстве <tex>y_i</tex> будет действовать небольшая сила притяжения от точки к точке <tex>x_iy_0</tex>. Но, принимая Принимая во внимание остальные точки, таких сил что точек наподобие <tex>x_0</tex> в реальной выборке данных будет достаточно много, их пружины вместе образуют силу, что схлопнет сожмет все точки в нуле и будет мешать образованию кластеров.

Чтобы избежать проблемы скученности , было решено использовать в низкоразмерном пространстве низкой размерности t-распределение Стьюдента с одной степенью свободы<ref>[https://ru.wikipedia.org/wiki/Распределение_Стьюдента Распределение Стьюдента]</ref> вместо распределения Гаусса. Данное распределение очень похоже на распределение Гаусса, но имеет большую вероятностную массу на участках, отдаленных от нуля(Рис. 2.), что решает описанную выше проблему, т.к. теперь удаленные точки лучше отталкиваются. [[Файл:Normal t-distribution comparison.png|300px|right|thumb|Рис. 2. Сравнение плотностей нормального распределения (синий цвет) и t-распределения с одной степенью свободы (красный цвет)]]

<tex>q_{i j} = \frac dfrac {(1 + {\left\Vert y_i - y_j \right\Vert}^2)^{-1}} {\sum\limits_{k \neq l} (1 + {\left\Vert y_k - y_l \right\Vert}^2)^{-1}}</tex>.

Еще одно свойство данного распределения состоит в том, что <tex>(1 + {\left\Vert y_i - y_j \right\Vert}^2)^{-1}</tex> описывает закон обратных квадратов <ref>[https://ru.wikipedia.org/wiki/Закон_обратных_квадратов Закон обратных квадратов]</ref> для далеких точек в низкоразмерном пространственизкой размерности, что позволяет думать не об отдельных точках, а о кластерах, которые будут взаимодействовать между собой как отдельные точки.

<tex>\frac dfrac {\delta C} {\delta y_i} = 4 \sum\limits_j (p_{i j} - q_{i j})(y_i - y_j)(1 + {\left\Vert y_i - y_j \right\Vert}^2)^{-1}</tex>.

== Оптимизации в cтохастическом вложении соседей с t-распределением SNE ==

# Первая оптимизация называется "раннее сжатие". В данной оптимизации на ранних итерациях оптимизации к целевой функции добавляется [[Регуляризация|<tex>L_2</tex>-штраф ]] на расстояния в низкоразмерном пространственизкой размерности, что влечет за собой сжатие всех точек в нуле. В связи с этим кластерам будет легче переходить друг через друга, чтобы правильно расположиться в пространстве.# Вторая оптимизация называется "раннее преувеличение". В данной оптимизации на ранних итерациях <tex>p_{i j}</tex> умножаются на некоторое положительное число, например на <tex>4</tex>. Так как <tex>q_{i j}</tex> остаются теми же самыми, они слишком маленькие, чтобы моделировать соответствующие <tex>p_{i j}</tex>. Как следствие, образуются очень плотные кластера, которые широко раскиданы в низкоразмерном пространственизкой размерности. Это создает много пустого пространства, которое используется кластерами, чтобы легко менять и находить наилучшее взаимное расположение. [[Файл:T-SNE iterations visualization.gif||200px|thumb|right|Рис. 3. Визуализация работы t-SNE]] На Рис. 3 представлена визуализация работы t-SNE, на которой видны эффекты от применения приведенных выше оптимизаций.

# [http://www.jmlr.org/papers/volume9/vandermaaten08a/vandermaaten08a.pdf Laurens van der Maaten and Geoffrey Hinton {{---}} Visualizing Data using t-SNE]# [http://datareview.info/article/algoritm-t-sne-illyustrirovannyiy-vvodnyiy-kurs datareview.info {{---}} Алгоритм t-SNE. Иллюстрированный вводный курс]# [https://en.wikipedia.org/wiki/Multivariate_t-distribution Wikipedia {{---}} Multivariate t-distribution] [[Категория: Машинное обучение]][[Категория: Уменьшение размерности]]