Изменения
Нет описания правки
{{Определение
|definition=
'''Стохастическое вложение соседей с t-распределением''' (англ. ''t-Distributed Stochastic Neighbor Embedding, t-SNE'') {{---}} метод визуализации высокоразмерных данных высокой размерности с помощью представления каждой точки данных в двух или трехмерном пространстве, являющийся модификацией метода стохастического вложения соседей.
}}
== Стохастическое вложение соседей ==
Пусть стоит задача вложить множество высокоразмерных точек в пространстве высокой размерности <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} = \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> для низкоразмерного пространстванизкой размерности, куда вкладываются высокоразмерные точкипространства высокой размерности.
<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>. Определяется она так:
<tex>KL(P \Vert Q) = \sum\limits_j p_j \log_2 \frac{p_j}{q_j}</tex>.
<tex>Perp(P_i) = 2 ^ {H(P_i)}</tex>.
Изначально точки <tex>y_i</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>
== Физическая интерпретация ==
Есть следующая физическая интерпретация модели. Между точками в низкоразмерном пространстве низкой размерности натянуты пружины между каждой парой точек <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>p_{i j} = \frac {p_{i|j} + p_{i|j} } {2|X|}</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 вкладывает данные в низкоразмерное пространство низкой размерности почти так же как и ассиметричный, а иногда даже лучше.
Градиент при таком подходе принимает вид:
== Проблема скученности ==
При использовании обычного SNE возникает следующая проблема, которая вытекает из разного распределения вероятностей в высокоразмерном пространствах высокой и низкоразмерном пространствахнизкой размерностей. Пусть есть некоторое высокоразмерное пространствовысокой размерности. Пусть в нем точки равномерно распределены вокруг некоторой точки <tex>x_i</tex>. Теперь попытаемся вложить высокоразмерное данное пространство в низкоразмерноеплоскость. Заметим, что область пространствана плоскости, доступная для размещения умеренно-удаленных точек высокоразмерного пространства высокой размерности относительно области пространства, доступное для размещения близких точек высокоразмерного пространства высокой размерности достаточно мала по сравнению с тем же самым в исходном пространстве (нужно сравнить отношения объемов сфер в низкоразмерном и высокоразмерном этих пространствах). Таким образом, если мы хотим правильно моделировать маленькие расстояния на плоскости и не иметь их в низкоразмерном пространстве между умеренно-удаленными точками высокоразмерного пространствавысокой размерности, следовало бы поместить умеренно-удаленные точки подальше от точки <tex>x_i</tex>, чем в исходном. В таком случае на слишком эти далекие точки в низкоразмерном пространстве на плоскости будет действовать небольшая сила притяжения от точки <tex>x_i</tex>. Но, принимая во внимание остальные точки, таких сил будет достаточно много, что схлопнет сожмет все точки и будет мешать образованию кластеров.
== Стохастическое вложение соседей с t-распределением ==
Чтобы избежать проблемы скученности было решено использовать в низкоразмерном пространстве низкой размерности 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> для далеких точек в низкоразмерном пространственизкой размерности, что позволяет думать не об отдельных точках, а о кластерах, которые будут взаимодействовать между собой как отдельные точки.
После замены распределения изменился градиент целевой функции, теперь он равен:
В t-SNE используется 2 основные оптимизации:
# Первая оптимизация называется "раннее сжатие". В данной оптимизации на ранних итерациях оптимизации к целевой функции добавляется [[Регуляризация|<tex>L_2</tex>-штраф]] на расстояния в низкоразмерном пространственизкой размерности, что влечет за собой сжатие всех точек в нуле. В связи с этим кластерам будет легче переходить друг через друга, чтобы правильно расположиться в пространстве.# Вторая оптимизация называется "раннее преувеличение". В данной оптимизации на ранних итерациях <tex>p_{i j}</tex> умножаются на некоторое положительное число, например на <tex>4</tex>. Так как <tex>q_{i j}</tex> остаются теми же самыми, они слишком маленькие, чтобы моделировать соответствующие <tex>p_{i j}</tex>. Как следствие, образуются очень плотные кластера, которые широко раскиданы в низкоразмерном пространственизкой размерности. Это создает много пустого пространства, которое используется кластерами, чтобы легко менять и находить наилучшее взаимное расположение.
== См. также ==
