Изменения
Нет описания правки
Пусть стоит задача вложить множество точек в пространстве высокой размерности <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{(-{\left\Vert x_i - x_j \right\Vert}^2/2\sigma_i^2)}}{\sum\limits_{k \neq i}\exp{({-\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 - x_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>y_i</tex> сэмплируют в пространстве низкой размерности в соответствии с распределением Гаусса с маленьким стандартным отклонением с математическим ожиданием в нуле, далее идет оптимизация целевой функции. Она проводится [[Стохастический градиентный спуск|методом градиентного спуска]]. Градиент равен:
<tex>\frac dfrac {\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 носит название '''симметричное стохастическое вложение соседей''' (англ. ''Symmetric Stochastic Neighbor Embedding, Symmetric SNE''), которая будет использоваться дальше в t-SNE. Симметричный SNE в качестве альтернативы использует совместные вероятности вместо условных. Теперь:
<tex>C = KL(P \Vert Q) = \sum\limits_i \sum\limits_j p_{i j} \log_2 \frac dfrac {p_{i j}} {q_{i j}}</tex>.
Очевидным образом можно определить <tex>q_{i j}</tex>:
<tex>q_{i j} = \frac dfrac {\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>p_{i j}</tex> будет очень маленькой для любого <tex>x_j</tex>, таким образом будет почти нулевой соответствующая дивергенция Кульбака-Лейблера для любого распределения <tex>q_{i j}</tex>. Это означало бы, что положение точки <tex>y_i</tex> определялось бы очень неточно относительно положения других точек и не было бы особой разницы в том, где она расположена. Поэтому в t-SNE <tex>p_{i j}</tex> определили как:
<tex>p_{i j} = \frac {p_{i|j} + p_{i|j} } {2|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_{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>q_{i j}</tex> определяется следующим образом:
<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>.
== Оптимизации в стохастическом вложении соседей с t-распределением ==
