Стохастическое вложение соседей с t-распределением — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Стохастическое вложение соседей)
м (rollbackEdits.php mass rollback)
 
(не показаны 42 промежуточные версии 5 участников)
Строка 1: Строка 1:
{{Определение
 
|definition=
 
 
'''Стохастическое вложение соседей с t-распределением''' (англ. ''t-Distributed Stochastic Neighbor Embedding, t-SNE'') {{---}} метод визуализации данных высокой размерности с помощью представления каждой точки данных в двух или трехмерном пространстве, являющийся модификацией метода стохастического вложения соседей.
 
'''Стохастическое вложение соседей с t-распределением''' (англ. ''t-Distributed Stochastic Neighbor Embedding, t-SNE'') {{---}} метод визуализации данных высокой размерности с помощью представления каждой точки данных в двух или трехмерном пространстве, являющийся модификацией метода стохастического вложения соседей.
}}
 
  
[[Файл:MNIST_compression_methods_comparison.png|300px|thumb|right|Пример работы t-SNE, Isomap, Sammon mapping, LLE на dataset-е MNIST]]
+
[[Файл: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> на наборе данных [[Известные наборы данных|MNIST]]]]
  
 
== Стохастическое вложение соседей ==
 
== Стохастическое вложение соседей ==
Строка 10: Строка 7:
 
Пусть стоит задача вложить множество точек в пространстве высокой размерности <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>\{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>p_{j|i} = \dfrac{\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_{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>q_{j|i} = \dfrac{\exp{(-{\left\Vert y_i - y_j \right\Vert}^2)}}{\sum\limits_{k \neq i}\exp{({-\left\Vert y_i - y_k \right\Vert}^2)}}</tex>.
  
Данные вероятности получаются из тех же самых предложений, что были сделаны для пространства высокой размерности, за исключением того, что все распределения Гаусса имеют стандартное отклонение <tex>\frac{1}{\sqrt{2}}</tex> для всех точек.
+
Данные вероятности получаются из тех же самых предложений, что были сделаны для пространства высокой размерности, за исключением того, что все распределения Гаусса имеют стандартное отклонение <tex>\dfrac{1}{\sqrt{2}}</tex> для всех точек.
  
Если удастся хорошо вложить одно пространство в другое, должны совпасть распределения совместных вероятностей. То есть <tex>p_{i|j}</tex> должны стать похожими на <tex>q_{i|j}</tex>. В связи с этим SNE пытается уменьшить разницу в распределении вероятностей. Стандартной мерой для измерения различия вероятностей служит дивергенция Кульбака-Лейблера<ref>[https://ru.wikipedia.org/wiki/Расстояние_Кульбака_—_Лейблера Расстояние Кульбака—Лейблера]</ref>. Определяется она так:
+
Если удастся хорошо вложить одно пространство в другое, <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>KL(P \Vert Q) = \sum\limits_j p_j \log_2 \dfrac{p_j}{q_j}</tex>.
  
В данном случае имеем <tex>|X|</tex> распределений. Тогда целевую функцию<ref>[https://ru.wikipedia.org/wiki/Целевая_функция Целевая функция]</ref>, который будем оптимизировать, определим как сумму соответствующих дивергенций Кульбака-Лейблера. То есть:
+
В данном случае имеем <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 \frac{p_{j|i}}{q_{j|i}}</tex>.
+
<tex>C = \sum\limits_i KL(p_i \Vert q_i) = \sum\limits_i \sum\limits_j p_{j|i} \log_2 \dfrac{p_{j|i}}{q_{j|i}}</tex>.
  
 
Дивергенция Кульбака-Лейблера не является симметричной мерой, поэтому, например, вложение близких точек в удаленные даёт гораздо большее значение ошибки, чем вложение далеких точек в близкие. Другими словами, целевая функция нацелена на сохранение локальной структуры вокруг точек.
 
Дивергенция Кульбака-Лейблера не является симметричной мерой, поэтому, например, вложение близких точек в удаленные даёт гораздо большее значение ошибки, чем вложение далеких точек в близкие. Другими словами, целевая функция нацелена на сохранение локальной структуры вокруг точек.
  
Параметры <tex>\sigma_i</tex> подбираются следующим образом. Каждое значение параметра порождает свое распределение вероятностей <tex>P_i</tex>. Это распределение имеет энтропию<ref>[https://ru.wikipedia.org/wiki/Информационная_энтропия Информационная энтропия]</ref>
+
Параметры <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} </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> сэмплируют в пространстве низкой размерности в соответствии с распределением Гаусса с маленьким стандартным отклонением с математическим ожиданием в нуле, далее идет оптимизация целевой функции. Она проводится [[Стохастический градиентный спуск|методом градиентного спуска]]. Градиент равен:
 
Изначально точки <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>\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>
  
 
== Физическая интерпретация ==
 
== Физическая интерпретация ==
  
Есть следующая физическая интерпретация модели. Между точками в пространстве низкой размерности натянуты пружины между каждой парой точек <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>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>. Оптимизация функционала в данной интерпретации эквивалентна поиску положения точек, в котором будет наблюдаться равновесие сил.
  
 
== Симметричное стохастическое вложение соседей ==
 
== Симметричное стохастическое вложение соседей ==
Строка 48: Строка 39:
 
Следующая модификация SNE носит название '''симметричное стохастическое вложение соседей''' (англ. ''Symmetric Stochastic Neighbor Embedding, Symmetric SNE''), которая будет использоваться дальше в t-SNE. Симметричный SNE в качестве альтернативы использует совместные вероятности вместо условных. Теперь:
 
Следующая модификация 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 {p_{i j}} {q_{i j}}</tex>.
+
<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>.
  
 
Очевидным образом можно определить <tex>q_{i j}</tex>:
 
Очевидным образом можно определить <tex>q_{i j}</tex>:
  
<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>,
+
<tex>q_{i j} = \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}</tex> привело бы к проблеме, что для [[Выброс|выброса]] <tex>x_i</tex> <tex>p_{i j}</tex> будет очень маленькой для любого <tex>x_j</tex>. Таким образом, будет почти нулевой соответствующая дивергенция Кульбака-Лейблера для любого распределения <tex>q_{i j}</tex>. Это означало бы, что положение точки <tex>y_i</tex> определялось бы очень неточно относительно положения других точек и не было бы особой разницы в том, где она расположена.  
  
<tex>p_{i j} = \frac {p_{i|j} + p_{i|j} } {2|X|}</tex>.
+
Таким образом, в симметричном SNE в качестве <tex>p_{i j}</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>.  
+
<tex>p_{i j} = \dfrac {p_{i|j} + p_{j|i} } {2|X|}</tex>.
 +
 
 +
Очевидный плюс в том, что <tex>\sum\limits_j p_{i j} > \dfrac 1 {2|X|}</tex> для всех точек, что хорошо скажется на выбросах. А также теперь <tex>p_{i j} = p_{j i}</tex>, <tex>q_{i j} = q_{j i}</tex>.  
  
 
Авторы утверждают, что симметричный SNE вкладывает данные в пространство низкой размерности почти так же как и ассиметричный, а иногда даже лучше.  
 
Авторы утверждают, что симметричный SNE вкладывает данные в пространство низкой размерности почти так же как и ассиметричный, а иногда даже лучше.  
  
 
Градиент при таком подходе принимает вид:
 
Градиент при таком подходе принимает вид:
<tex>\frac {\delta C} {\delta y_i} = 2 \sum\limits_j (p_{i j} - q_{i j})(y_i - y_j)</tex>.
+
<tex>\dfrac {\delta C} {\delta y_i} = 2 \sum\limits_j (p_{i j} - q_{i j})(y_i - y_j)</tex>.
  
 
== Проблема скученности ==
 
== Проблема скученности ==
  
При использовании обычного SNE возникает следующая проблема, которая вытекает из разного распределения вероятностей в пространствах высокой и низкой размерностей. Пусть есть некоторое пространство высокой размерности. Пусть в нем точки равномерно распределены вокруг некоторой точки <tex>x_i</tex>. Теперь попытаемся вложить данное пространство в плоскость. Заметим, что область пространства на плоскости, доступная для размещения умеренно-удаленных точек пространства высокой размерности относительно области пространства, доступное для размещения близких точек пространства высокой размерности достаточно мала по сравнению с тем же самым в исходном пространстве (нужно сравнить отношения объемов сфер в этих пространствах). Таким образом, если мы хотим правильно моделировать маленькие расстояния на плоскости и не иметь их между умеренно-удаленными точками пространства высокой размерности, следовало бы поместить умеренно-удаленные точки подальше от точки <tex>x_i</tex>, чем в исходном. В таком случае на слишком эти далекие точки на плоскости будет действовать небольшая сила притяжения от точки <tex>x_i</tex>. Но, принимая во внимание остальные точки, таких сил будет достаточно много, что сожмет все точки и будет мешать образованию кластеров.
+
Необходимо понимать, что невозможно абсолютно точно моделировать расстояния между точками пространства высокой размерности в низком. Например, в десятимерном пространстве существует <tex>11</tex> равноудаленных друг от друга точек, в то время как на плоскости может быть максимум <tex>3</tex> равноудаленные точки.
 +
 
 +
При использовании обычного SNE возникает проблема, которая вытекает из разного распределения вероятностей в пространствах высокой и низкой размерностей. Пусть есть некоторое пространство высокой размерности. Пусть точки <tex>x_i</tex> равномерно распределены в нем вокруг точки <tex>x_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>y_0</tex>. Принимая во внимание, что точек наподобие <tex>x_0</tex> в реальной выборке данных будет достаточно много, их пружины вместе образуют силу, что сожмет все точки в нуле и будет мешать образованию кластеров.
  
 
== Стохастическое вложение соседей с t-распределением ==
 
== Стохастическое вложение соседей с t-распределением ==
  
Чтобы избежать проблемы скученности было решено использовать в пространстве низкой размерности t-распределение Стьюдента с одной степенью свободы<ref>[https://ru.wikipedia.org/wiki/Распределение_Стьюдента Распределение Стьюдента]</ref> вместо распределения Гаусса. Данное распределение очень похоже на распределение Гаусса, но имеет большую вероятностную массу на участках, отдаленных от нуля, что решает описанную выше проблему, т.к. теперь удаленные точки лучше отталкиваются.
+
Чтобы избежать проблемы скученности, было решено использовать в пространстве низкой размерности t-распределение Стьюдента с одной степенью свободы<ref>[https://ru.wikipedia.org/wiki/Распределение_Стьюдента Распределение Стьюдента]</ref> вместо распределения Гаусса. Данное распределение очень похоже на распределение Гаусса, но имеет большую вероятностную массу на участках, отдаленных от нуля (Рис. 2.), что решает описанную выше проблему, т.к. теперь удаленные точки лучше отталкиваются.
 +
 
 +
[[Файл:Normal t-distribution comparison.png|300px|right|thumb|Рис. 2. Сравнение плотностей нормального распределения (синий цвет) и t-распределения с одной степенью свободы (красный цвет)]]
  
 
В связи с заменой распределения <tex>q_{i j}</tex> определяется следующим образом:
 
В связи с заменой распределения <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>q_{i j} = \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>(1 + {\left\Vert y_i - y_j \right\Vert}^2)^{-1}</tex> описывает закон обратных квадратов<ref>[https://ru.wikipedia.org/wiki/Закон_обратных_квадратов Закон обратных квадратов]</ref> для далеких точек в пространстве низкой размерности, что позволяет думать не об отдельных точках, а о кластерах, которые будут взаимодействовать между собой как отдельные точки.
Строка 81: Строка 78:
 
После замены распределения изменился градиент целевой функции, теперь он равен:
 
После замены распределения изменился градиент целевой функции, теперь он равен:
  
<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>.
+
<tex>\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-распределением ==
+
== Оптимизации t-SNE ==
  
 
В t-SNE используется 2 основные оптимизации:
 
В t-SNE используется 2 основные оптимизации:
Строка 89: Строка 86:
 
# Первая оптимизация называется "раннее сжатие". В данной оптимизации на ранних итерациях оптимизации к целевой функции добавляется [[Регуляризация|<tex>L_2</tex>-штраф]] на расстояния в пространстве низкой размерности, что влечет за собой сжатие всех точек в нуле. В связи с этим кластерам будет легче переходить друг через друга, чтобы правильно расположиться в пространстве.
 
# Первая оптимизация называется "раннее сжатие". В данной оптимизации на ранних итерациях оптимизации к целевой функции добавляется [[Регуляризация|<tex>L_2</tex>-штраф]] на расстояния в пространстве низкой размерности, что влечет за собой сжатие всех точек в нуле. В связи с этим кластерам будет легче переходить друг через друга, чтобы правильно расположиться в пространстве.
 
# Вторая оптимизация называется "раннее преувеличение". В данной оптимизации на ранних итерациях <tex>p_{i j}</tex> умножаются на некоторое положительное число, например на <tex>4</tex>. Так как <tex>q_{i j}</tex> остаются теми же самыми, они слишком маленькие, чтобы моделировать соответствующие <tex>p_{i j}</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, на которой видны эффекты от применения приведенных выше оптимизаций.
  
 
== См. также ==
 
== См. также ==
  
 
*[[Уменьшение размерности]]
 
*[[Уменьшение размерности]]
 +
*[[Метод главных компонент (PCA)]]
 +
*[[Стохастический градиентный спуск]]
  
 
== Примечания ==
 
== Примечания ==
Строка 99: Строка 102:
 
== Источники информации ==
 
== Источники информации ==
  
# [http://www.jmlr.org/papers/volume9/vandermaaten08a/vandermaaten08a.pdf Visualizing Data using 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]
 +
 
 +
[[Категория: Машинное обучение]]
 +
[[Категория: Уменьшение размерности]]

Текущая версия на 19:43, 4 сентября 2022

Стохастическое вложение соседей с t-распределением (англ. t-Distributed Stochastic Neighbor Embedding, t-SNE) — метод визуализации данных высокой размерности с помощью представления каждой точки данных в двух или трехмерном пространстве, являющийся модификацией метода стохастического вложения соседей.

Пример работы методов t-SNE, Isomap[1], Sammon mapping[2], LLE[3] на наборе данных MNIST

Стохастическое вложение соседей

Пусть стоит задача вложить множество точек в пространстве высокой размерности [math]\{x_i \mid x_i \in X\}[/math] в пространство низкой размерности. Обозначим множество точек в пространстве низкой размерности, которые получаются после вложения через [math]\{y_i \mid y_i \in Y\}[/math]. Стохастическое вложение соседей (англ. Stochastic Neighbor Embedding, SNE) конвертирует расстояния в Евклидовом пространстве высокой размерности между точками в условные вероятности [math]p_{j|i}[/math]. [math]p_{j|i}[/math] — вероятность, что точка [math]x_i[/math] выберет в качестве своего соседа точку [math]x_j[/math] среди остальных точек данных. Будем считать, что вероятность для точки [math]x_i[/math] найти соседа падает с увеличением расстояния от точки [math]x_i[/math] в соответствии с распределением Гаусса[4] с нулевым математическим ожиданием и стандартным отклонением [math]\sigma_i[/math]. В соответствии с этим [math]p_{j|i}[/math] выражается как

[math]p_{j|i} = \dfrac{\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})}}[/math].

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

[math]q_{j|i} = \dfrac{\exp{(-{\left\Vert y_i - y_j \right\Vert}^2)}}{\sum\limits_{k \neq i}\exp{({-\left\Vert y_i - y_k \right\Vert}^2)}}[/math].

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

Если удастся хорошо вложить одно пространство в другое, [math]p_{i|j}[/math] должны стать похожими на [math]q_{i|j}[/math]. В связи с этим SNE пытается уменьшить разницу в распределении вероятностей. Стандартной мерой для измерения различия вероятностей служит дивергенция Кульбака-Лейблера[5]:

[math]KL(P \Vert Q) = \sum\limits_j p_j \log_2 \dfrac{p_j}{q_j}[/math].

В данном случае имеем [math]|X|[/math] распределений. Тогда целевую функцию[6], которую будем оптимизировать, определим как сумму соответствующих дивергенций Кульбака-Лейблера. То есть:

[math]C = \sum\limits_i KL(p_i \Vert q_i) = \sum\limits_i \sum\limits_j p_{j|i} \log_2 \dfrac{p_{j|i}}{q_{j|i}}[/math].

Дивергенция Кульбака-Лейблера не является симметричной мерой, поэтому, например, вложение близких точек в удаленные даёт гораздо большее значение ошибки, чем вложение далеких точек в близкие. Другими словами, целевая функция нацелена на сохранение локальной структуры вокруг точек.

Параметры [math]\sigma_i[/math] подбираются следующим образом. Каждое значение параметра порождает свое распределение вероятностей [math]P_i[/math]. Это распределение имеет энтропию[7] [math]H(P_i) = \sum\limits_j p_{j|i}\log_2 p_{j|i} [/math], которая возрастает с ростом [math]\sigma_i[/math]. В самом алгоритме [math]\sigma_i[/math] вычисляются с помощью вещественного двоичного поиска по заранее заданной пользователем величине, называемой перплексией[8]: [math]Perp(P_i) = 2 ^ {H(P_i)}[/math].

Изначально точки [math]y_i[/math] сэмплируют в пространстве низкой размерности в соответствии с распределением Гаусса с маленьким стандартным отклонением с математическим ожиданием в нуле, далее идет оптимизация целевой функции. Она проводится методом градиентного спуска. Градиент равен:

[math]\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)[/math]

Физическая интерпретация

Есть следующая физическая интерпретация модели. В пространстве низкой размерности натянуты пружины между каждой парой точек [math]y_i[/math] и [math]y_j[/math], действующие в направлении [math]y_i - y_j[/math]. Пружины могут притягивать или отталкивать точки в зависимости от расстояния между ними. Сила, прикладываемая пружиной, пропорциональна её длине [math]\left\Vert y_i - y_j \right\Vert[/math] и жесткости[9] [math]p_{j|i} - q_{j|i} + p_{i|j} - q_{i|j}[/math]. Оптимизация функционала в данной интерпретации эквивалентна поиску положения точек, в котором будет наблюдаться равновесие сил.

Симметричное стохастическое вложение соседей

Следующая модификация SNE носит название симметричное стохастическое вложение соседей (англ. Symmetric Stochastic Neighbor Embedding, Symmetric SNE), которая будет использоваться дальше в t-SNE. Симметричный SNE в качестве альтернативы использует совместные вероятности вместо условных. Теперь:

[math]C = KL(P \Vert Q) = \sum\limits_i \sum\limits_j p_{i j} \log_2 \dfrac {p_{i j}} {q_{i j}}[/math].

Очевидным образом можно определить [math]q_{i j}[/math]:

[math]q_{i j} = \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) } }[/math],

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

Таким образом, в симметричном SNE в качестве [math]p_{i j}[/math] рассматривается следующая величина:

[math]p_{i j} = \dfrac {p_{i|j} + p_{j|i} } {2|X|}[/math].

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

Авторы утверждают, что симметричный SNE вкладывает данные в пространство низкой размерности почти так же как и ассиметричный, а иногда даже лучше.

Градиент при таком подходе принимает вид: [math]\dfrac {\delta C} {\delta y_i} = 2 \sum\limits_j (p_{i j} - q_{i j})(y_i - y_j)[/math].

Проблема скученности

Необходимо понимать, что невозможно абсолютно точно моделировать расстояния между точками пространства высокой размерности в низком. Например, в десятимерном пространстве существует [math]11[/math] равноудаленных друг от друга точек, в то время как на плоскости может быть максимум [math]3[/math] равноудаленные точки.

При использовании обычного SNE возникает проблема, которая вытекает из разного распределения вероятностей в пространствах высокой и низкой размерностей. Пусть есть некоторое пространство высокой размерности. Пусть точки [math]x_i[/math] равномерно распределены в нем вокруг точки [math]x_0[/math] в некотором шаре с радиусом [math]R[/math]. Заметим, что, чем больше размерность пространства, тем больше точек попадет рядом с границей шара, поэтому количество близких к [math]x_0[/math] точек с ростом размерности будет убывать. Теперь попытаемся вложить данное пространство в плоскость. Пусть точки [math]x_i[/math] перешли в точки [math]y_i[/math] на плоскости. Заметим, что если попытаться вложить точки [math]x_i[/math] в круг радиуса [math]R[/math] с центром в точке [math]y_0[/math] образуется большое количество маленьких расстояний между точками [math]y_i[/math], т.к. объем сферы в высокомерном пространстве несопоставим с площадью круга на плоскости. Таким образом, если мы хотим правильно моделировать маленькие расстояния на плоскости, следовало бы поместить удаленные от [math]x_0[/math] точки [math]x_i[/math] ещё дальше, чем в исходном пространстве. Но в таком случае, вспоминая физическую интерпретацию, на соответствующие им точки [math]y_i[/math] будет действовать небольшая сила притяжения к точке [math]y_0[/math]. Принимая во внимание, что точек наподобие [math]x_0[/math] в реальной выборке данных будет достаточно много, их пружины вместе образуют силу, что сожмет все точки в нуле и будет мешать образованию кластеров.

Стохастическое вложение соседей с t-распределением

Чтобы избежать проблемы скученности, было решено использовать в пространстве низкой размерности t-распределение Стьюдента с одной степенью свободы[10] вместо распределения Гаусса. Данное распределение очень похоже на распределение Гаусса, но имеет большую вероятностную массу на участках, отдаленных от нуля (Рис. 2.), что решает описанную выше проблему, т.к. теперь удаленные точки лучше отталкиваются.

Рис. 2. Сравнение плотностей нормального распределения (синий цвет) и t-распределения с одной степенью свободы (красный цвет)

В связи с заменой распределения [math]q_{i j}[/math] определяется следующим образом:

[math]q_{i j} = \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}}[/math].

Еще одно свойство данного распределения состоит в том, что [math](1 + {\left\Vert y_i - y_j \right\Vert}^2)^{-1}[/math] описывает закон обратных квадратов[11] для далеких точек в пространстве низкой размерности, что позволяет думать не об отдельных точках, а о кластерах, которые будут взаимодействовать между собой как отдельные точки.

После замены распределения изменился градиент целевой функции, теперь он равен:

[math]\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}[/math].

Оптимизации t-SNE

В t-SNE используется 2 основные оптимизации:

  1. Первая оптимизация называется "раннее сжатие". В данной оптимизации на ранних итерациях оптимизации к целевой функции добавляется [math]L_2[/math]-штраф на расстояния в пространстве низкой размерности, что влечет за собой сжатие всех точек в нуле. В связи с этим кластерам будет легче переходить друг через друга, чтобы правильно расположиться в пространстве.
  2. Вторая оптимизация называется "раннее преувеличение". В данной оптимизации на ранних итерациях [math]p_{i j}[/math] умножаются на некоторое положительное число, например на [math]4[/math]. Так как [math]q_{i j}[/math] остаются теми же самыми, они слишком маленькие, чтобы моделировать соответствующие [math]p_{i j}[/math]. Как следствие, образуются очень плотные кластера, которые широко раскиданы в пространстве низкой размерности. Это создает много пустого пространства, которое используется кластерами, чтобы легко менять и находить наилучшее взаимное расположение.
Рис. 3. Визуализация работы t-SNE

На Рис. 3 представлена визуализация работы t-SNE, на которой видны эффекты от применения приведенных выше оптимизаций.

См. также

Примечания

Источники информации

  1. Laurens van der Maaten and Geoffrey Hinton — Visualizing Data using t-SNE
  2. datareview.info — Алгоритм t-SNE. Иллюстрированный вводный курс
  3. Wikipedia — Multivariate t-distribution