Изменения
Нет описания правки
== SNE ==
Пусть стоит задача вложить высокоразмерные точки <tex>x_i \in X</tex> в низкоразмерное пространство. Обозначим точки, которые получаются после вложения через <tex>y_i \in Y</tex>. '''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> выражается как <br />
<tex>p_{j|i} = \frac{\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> для низкоразмерного пространства, куда вкладываются высокоразмерные точки. <br \>
<tex>q_{j|i} = \frac{\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>\frac{1}{\sqrt{2}}</tex> для всех точек.
Если удастся хорошо вложить высокоразмерное пространство в низкоразмерное, должны совпасть распределения совместных вероятностей. То есть <tex>p_{i|j}</tex> должны стать похожими на <tex>q_{i|j}</tex>. В связи с этим SNE пытается уменьшить разницу в распределении вероятностей. Стандартной мерой для измерения различия вероятностей служит дивергенция Кульбака-Лейблера<ref>[https://ru.wikipedia.org/wiki/Расстояние_Кульбака_—_Лейблера Расстояние Кульбака—Лейблера]</ref>. Определяется она так: <br />
<tex>KL(P \Vert Q) = \sum\limits_j p_j \log_2 \frac{p_j}{q_j}</tex>.
В данном случае имеем <tex>|X|</tex> распределений. Тогда целевую функцию<ref>[https://ru.wikipedia.org/wiki/Целевая_функция Целевая функция]</ref>, который будем оптимизировать, определим как сумму соответствующих дивергенций Кульбака-Лейблера. То есть: <br />
<tex>C = \sum\limits_i KL(p_i \Vert q_i) = \sum\limits_i \sum\limits_j p_{j|i} \log_2 \frac{p_{j|i}}{q_{j|i}}</tex>.
Дивергенция Кульбака-Лейблера не является симметричной мерой, поэтому, например, вложение близких точек в удаленные даёт гораздо большее значение ошибки, чем вложение далеких точек в близкие. Другими словами, целевая функция нацелена на сохранение локальной структуры вокруг точек.
Параметры <tex>\sigma_i</tex> подбираются следующим образом. Каждое значение параметра порождает свое распределение вероятностей <tex>P_i</tex>. Это распределение имеет энтропию<ref>[https://ru.wikipedia.org/wiki/Информационная_энтропия Информационная энтропия]</ref> <br /> <tex>H(P_i) = \sum\limits_j p_{j|i}\log_2 p_{j|i} </tex>, <br /> которая возрастает с ростом <tex>\sigma_i</tex>. В самом алгоритме <tex>\sigma_i</tex> вычисляются с помощью бинарного поиска по заранее заданной пользователем величине, называемой перплексией<ref>[https://en.wikipedia.org/wiki/Perplexity Perplexity]</ref>, которая определяется как <br />
<tex>Perp(P_i) = 2 ^ {H(P_i)}</tex>.
Изначально точки <tex>y_i</tex> сэмплируют в низкоразмерном пространстве в соответствии с Гауссовским распределением с маленьким стандартным отклонением с математическим ожиданием в нуле, далее идет оптимизация целевой функции. Она проводится [[Стохастический градиентный спуск|методом градиентного спуска]]. Градиент равен: <br />
<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 ==
Следующая модификация SNE носит название '''симметричный SNE'''. Было странно, что в классическом SNE <tex>p_{j|i} \neq p_{i|j}</tex> и <tex>q_{j|i} \neq q_{i|j}</tex>. Симметричный SNE {{---}} попытка исправить эту ситуацию путем определения совместных вероятностей вместо условных. Теперь: <br />
<tex>C = KL(P \Vert Q) = \sum\limits_i \sum\limits_j p_{i j} \log_2 \frac {p_{i j}} {q_{i j}}</tex>.
Очевидным образом определяется <tex>q_{i j}</tex>: <br /> <tex>q_{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>, <br /> но то же решение для <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> определили как: <br /> <tex>p_{i j} = \frac {p_{i|j} + p_{i|j} } {2|X|}</tex>. <br />
Очевидный плюс такого определения в том, что <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 вкладывает данные в низкоразмерное пространство почти также как и ассиметричный, а иногда даже лучше.
Чтобы избежать проблемы скученности было решено использовать в низкоразмерном пространстве t-распределение Стьюдента с одной степенью свободы<ref>[https://ru.wikipedia.org/wiki/Распределение_Стьюдента Распределение Стьюдента]</ref> вместо распределения Гаусса. Данное распределение очень похоже на распределение Гаусса, но имеет большую вероятностную массу на участках, отдаленных от нуля, что решает описанную выше проблему, т.к. теперь удаленные точки лучше отталкиваются.
В связи с заменой распределения <tex>q_{i j}</tex> определяется следующим образом: <br />
<tex>q_{i j} = \frac {(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> описывает закон обратных квадратов для далеких точек в низкоразмерном пространстве, что позволяет думать не об отдельных точках, а о кластерах, которые будут взаимодействовать между собой как отдельные точки.
После замены распределения изменился градиент целевой функции, теперь он равен: <br />
<tex>\frac {\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>.
