Изменения
Нет описания правки
[[Файл:MNIST_compression_methods_comparison.png|300px|thumb|250pxright|Пример работы t-SNE, Isomap, Sammon mapping, LLE на dataset-е MNIST]]
<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>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> <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>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>
== Физическая интерпретация ==
Есть следующая физическая интерпретация модели. Между точками в низкоразмерном пространстве натянуты пружины между каждой парой точек <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>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 вкладывает данные в низкоразмерное пространство почти также так же как и ассимитричныйассиметричный, а иногда даже лучше.
Градиент при таком подходе принимает вид:
== Проблема скученности ==
При использовании обычного SNE возникает следующая проблема, которая вытекает из разного распределения вероятностей в высокоразмерном и низкоразмерном пространствах. Пусть есть некоторое высокоразмерное пространство. Пусть в нем точки равномерно распределены вокруг некоторой точки <tex>x_i</tex>. Теперь попытаемся вложить высокоразмерное пространство в низкоразмерное. Заметим, что область пространства, доступная для размещения умеренно-удаленных точек высокоразмерного пространства относительно области пространства, доступное для размещения близких точек высокоразмерного пространства достаточно мала по сравнению с тем же самым в исходном пространстве (нужно сравнить отношения объемов сфер в низкоразмерном и высокоразмерном пространствах). Таким образом, если мы хотим правильно моделировать близкие маленькие расстояния и не иметь лишних маленьких расстояний, возникающих их в низкоразмерном пространстве между умеренно-удаленными между собой точкамивысокоразмерного пространства, следовало бы поместить умеренно-удаленные точки подальше от точки <tex>x_i</tex>, чем в исходном. В таком случае на слишком эти далекие точки в низкоразмерном пространстве будет действовать небольшая сила притяжения от точки <tex>x_i</tex>. Но, принимая во внимание остальные точки, таких сил будет достаточно много, что схлопнет точки и будет мешать образованию кластеров.
== Стохастическое вложение соседей с t-SNE распределением ==
Чтобы избежать проблемы скученности было решено использовать в низкоразмерном пространстве t-распределение Стьюдента с одной степенью свободы <ref>[https://ru.wikipedia.org/wiki/Распределение_Стьюдента Распределение Стьюдента]</ref> вместо распределения Гаусса. Данное распределение очень похоже на распределение Гаусса, но имеет большую вероятностную массу на участках, отдаленных от нуля, что решает описанную выше проблему, т.к. теперь удаленные точки лучше отталкиваются. В связи с заменой распределения <tex>q_{i j}</tex> определяется следующим образом:
<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> описывает закон обратных квадратов <ref>[https://ru.wikipedia.org/wiki/Закон_обратных_квадратов Закон обратных квадратов]</ref> для далеких точек в низкоразмерном пространстве, что позволяет думать не об отдельных точках, а о кластерах, которые будут взаимодействовать между собой как отдельные точки. После замены распределения изменился градиент целевой функции, теперь он равен:
<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>.
== Оптимизации в стохастическом вложении соседей с t-SNE распределением == В t-SNE используется 2 основных оптимизации:
== См. также ==
*[[Уменьшение размерности]]
== Примечания ==
<references/>
== Источники информации ==
# [http://www.jmlr.org/papers/volume9/vandermaaten08a/vandermaaten08a.pdf Visualizing Data using t-SNE]