Полуопределенное вложение

Развертка максимальной дисперсии (MVU) , также известная как полуопределенное вложение (SDE), — это алгоритм в информатике , который использует полуопределенное программирование для выполнения нелинейного снижения размерности многомерных векторных входных данных. [1] [2] [3]

Это мотивировано наблюдением, что ядерный компонентный анализ (kPCA) не снижает размерность данных [4] , поскольку он использует прием ядра для нелинейного отображения исходных данных в пространство внутреннего продукта .

Алгоритм

MVU создает отображение из входных векторов высокой размерности в некоторое евклидово векторное пространство низкой размерности за следующие шаги: [5]

  1. Создается граф соседства . Каждый вход соединен с его k-ближайшими входными векторами (согласно евклидовой метрике расстояния), и все k-ближайшие соседи соединены друг с другом. Если данные достаточно хорошо отобраны, то полученный граф является дискретным приближением базового многообразия.
  2. Граф соседства «разворачивается» с помощью полуопределенного программирования. Вместо того, чтобы изучать выходные векторы напрямую, полуопределенное программирование стремится найти матрицу внутреннего произведения, которая максимизирует попарные расстояния между любыми двумя входами, которые не связаны в графе соседства, сохраняя при этом расстояния до ближайших соседей.
  3. Низкоразмерное вложение в конечном итоге получается путем применения многомерного масштабирования к изученной матрице внутреннего произведения.

Шаги применения полуопределенного программирования с последующим шагом линейного снижения размерности для восстановления низкоразмерного вложения в евклидово пространство были впервые предложены Линиалом , Лондоном и Рабиновичем. [6]

Формулировка оптимизации

Пусть будет исходным входом, а будет вложением. Если есть два соседа, то локальное изометрическое ограничение, которое должно быть удовлетворено, равно: [7] [8] [9] Х {\displaystyle X\,\!} И {\displaystyle Y\,\!} я , дж {\displaystyle я,j\,\!}

| Х я − Х дж | 2 = | И я − И дж | 2 {\displaystyle |X_{i}-X_{j}|^{2}=|Y_{i}-Y_{j}|^{2}\,\!}

Пусть будут матрицами Грама и (т.е.: ). Мы можем выразить указанное выше ограничение для каждой соседней точки в терминах : [10] [11] Г , К {\displaystyle Г,К\,\!} Х {\displaystyle X\,\!} И {\displaystyle Y\,\!} Г я дж = Х я ⋅ Х дж , К я дж = И я ⋅ И дж {\displaystyle G_{ij}=X_{i}\cdot X_{j},K_{ij}=Y_{i}\cdot Y_{j}\,\!} я , дж {\displaystyle я,j\,\!} Г , К {\displaystyle Г,К\,\!}

Г я я + Г дж дж − Г я дж − Г дж я = К я я + К дж дж − К я дж − К дж я {\displaystyle G_{ii}+G_{jj}-G_{ij}-G_{ji}=K_{ii}+K_{jj}-K_{ij}-K_{ji}\,\!}

Кроме того, мы также хотим ограничить встраивание центром в начале координат: [12] [13] [14] И {\displaystyle Y\,\!}

0 = | ∑ я И я | 2 ⇔ ( ∑ я И я ) ⋅ ( ∑ я И я ) ⇔ ∑ я , дж И я ⋅ И дж ⇔ ∑ я , дж К я дж {\displaystyle 0=|\sum _{i}Y_{i}|^{2}\Leftrightarrow (\sum _{i}Y_{i})\cdot (\sum _{i}Y_{i})\Leftrightarrow \sum _{i,j}Y_{i}\cdot Y_{j}\Leftrightarrow \sum _{i,j}K_{ij}}

Как описано выше, за исключением того, что расстояния соседних точек сохраняются, алгоритм стремится максимизировать попарное расстояние каждой пары точек. Целевая функция, которая должна быть максимизирована, это: [15] [16] [17]

Т ( И ) = 1 2 Н ∑ я , дж | И я − И дж | 2 {\displaystyle T(Y)={\dfrac {1}{2N}}\sum _{i,j}|Y_{i}-Y_{j}|^{2}}

Интуитивно, максимизация функции выше эквивалентна вытягиванию точек как можно дальше друг от друга и, следовательно, «разворачиванию» многообразия. Ограничение локальной изометрии [18]

Пусть где τ = м а х { η я дж | И я − И дж | 2 } {\displaystyle \tau =max\{\eta _{ij}|Y_{i}-Y_{j}|^{2}\}\,\!} η я дж := { 1 если   я  является соседом  дж 0 в противном случае . {\displaystyle \eta _{ij}:={\begin{cases}1&{\mbox{if}}\ i{\mbox{ является соседом }}j\\0&{\mbox{internally}}.\end{cases}}}

предотвращает расхождение целевой функции (стремление к бесконечности).

Поскольку график имеет N точек, расстояние между любыми двумя точками . Тогда мы можем ограничить целевую функцию следующим образом: [19] [20] | И я − И дж | 2 ≤ Н τ {\displaystyle |Y_{i}-Y_{j}|^{2}\leq N\tau \,\!}

Т ( И ) = 1 2 Н ∑ я , дж | И я − И дж | 2 ≤ 1 2 Н ∑ я , дж ( Н τ ) 2 = Н 3 τ 2 2 {\displaystyle T(Y)={\dfrac {1}{2N}}\sum _{i,j}|Y_{i}-Y_{j}|^{2}\leq {\dfrac {1}{ 2N}}\sum _{i,j}(N\tau )^{2}={\dfrac {N^{3}\tau ^{2}}{2}}\,\!}

Целевую функцию можно переписать исключительно в виде матрицы Грама: [21] [22] [23]

Т ( И ) = 1 2 Н ∑ я , дж | И я − И дж | 2 = 1 2 Н ∑ я , дж ( И я 2 + И дж 2 − И я ⋅ И дж − И дж ⋅ И я ) = 1 2 Н ( ∑ я , дж И я 2 + ∑ я , дж И дж 2 − ∑ я , дж И я ⋅ И дж − ∑ я , дж И дж ⋅ И я ) = 1 2 Н ( ∑ я , дж И я 2 + ∑ я , дж И дж 2 − 0 − 0 ) = 1 Н ( ∑ я И я 2 ) = 1 Н ( Т г ( К ) ) {\displaystyle {\begin{aligned}T(Y)&{}={\dfrac {1}{2N}}\sum _{i,j}|Y_{i}-Y_{j}|^{2}\\&{}={\dfrac {1}{2N}}\sum _{i,j}(Y_{i}^{2}+Y_{j}^{2}-Y_{i}\cdot Y_{j}-Y_{j}\cdot Y_{i})\\&{}={\dfrac {1}{2N}}(\sum _{i,j}Y_{i}^{2}+\sum _{i,j}Y_{j}^{2}-\sum _{i,j}Y_{i}\cdot Y_{j}-\sum _{i,j}Y_{j}\cdot Y_{i})\\&{}={\dfrac {1}{2N}}(\sum _{i,j}Y_{i}^{2}+\sum _{i,j}Y_{j}^{2}-0-0)\\&{}={\dfrac {1}{N}}(\sum _{i}Y_{i}^{2})={\dfrac {1}{N}}(Tr(K))\\\end{aligned}}\,\!}

Наконец, оптимизацию можно сформулировать следующим образом: [24] [25] [26]

Увеличить Т г ( К ) при условии К ⪰ 0 , ∑ я дж К я дж = 0 и Г я я + Г дж дж − Г я дж − Г дж я = К я я + К дж дж − К я дж − К дж я , ∀ я , дж  где  η я дж = 1 , {\displaystyle {\begin{aligned}&{\text{Maximize}}&&Tr(\mathbf {K} )\\&{\text{subject to}}&&\mathbf {K} \succeq 0,\sum _{ij}\mathbf {K} _{ij}=0\\&{\text{and}}&&G_{ii}+G_{jj}-G_{ij}-G_{ji}=K_{ii}+K_{jj}-K_{ij}-K_{ji},\forall i,j{\mbox{ where }}\eta _{ij}=1,\end{aligned}}}

После того, как матрица Грама изучена с помощью полуопределенного программирования, выходные данные можно получить с помощью разложения Холецкого . K {\displaystyle K\,\!} Y {\displaystyle Y\,\!}

В частности, матрицу Грама можно записать как , где — i-й элемент собственного вектора собственного значения . [27] [28] K i j = ∑ α = 1 N ( λ α V α i V α j ) {\displaystyle K_{ij}=\sum _{\alpha =1}^{N}(\lambda _{\alpha }V_{\alpha i}V_{\alpha j})\,\!} V α i {\displaystyle V_{\alpha i}\,\!} V α {\displaystyle V_{\alpha }\,\!} λ α {\displaystyle \lambda _{\alpha }\,\!}

Из этого следует, что -й элемент вывода равен . [29] [30] α {\displaystyle \alpha \,\!} Y i {\displaystyle Y_{i}\,\!} λ α V α i {\displaystyle {\sqrt {\lambda _{\alpha }}}V_{\alpha i}\,\!}

Смотрите также

Примечания

  1. ^ Вайнбергер, Ша и Саул 2004a
  2. ^ Вайнбергер и Сол 2004b
  3. ^ Вайнбергер и Сол 2006
  4. ^ Лоуренс 2012, стр. 1612
  5. ^ Вайнбергер, Ша и Саул 2004a, стр. 7.
  6. ^ Линиал, Лондон и Рабинович 1995
  7. ^ Вайнбергер, Ша и Саул 2004a, стр. 3, уравнение 8
  8. ^ Вайнбергер и Саул 2004b, стр. 3, уравнение 2
  9. ^ Вайнбергер и Саул 2006, стр. 4, уравнение 2
  10. ^ Вайнбергер, Ша и Саул 2004a, стр. 3, уравнение 9
  11. ^ Вайнбергер и Саул 2004b, стр. 3, уравнение 3
  12. ^ Вайнбергер, Ша и Саул 2004a, стр. 3, уравнение 6
  13. ^ Вайнбергер и Саул 2004b, стр. 3, уравнение 5
  14. ^ Вайнбергер и Саул 2006, стр. 5, уравнение 8
  15. ^ Вайнбергер, Ша и Саул 2004a, стр. 4, уравнение 10
  16. ^ Вайнбергер и Саул 2004b, стр. 4, уравнение 6
  17. ^ Вайнбергер и Саул 2006, стр. 5, уравнение 4
  18. ^ Вайнбергер и Саул 2004b, стр. 4, уравнение 7
  19. ^ Вайнбергер и Саул 2004b, стр. 4, уравнение 8
  20. ^ Вайнбергер и Саул 2006, стр. 5, уравнение 6
  21. ^ Вайнбергер, Ша и Саул 2004a, стр. 4, уравнение 11
  22. ^ Вайнбергер и Саул 2004b, стр. 4, уравнение 9
  23. ^ Вайнбергер и Саул 2006, стр. 6, уравнения 10–13
  24. ^ Вайнбергер, Ша и Саул 2004a, стр. 4, раздел 3.3
  25. ^ Вайнбергер и Саул 2004b, стр. 4, уравнение 9
  26. ^ Вайнбергер и Саул 2006, стр. 6, уравнения 10–13
  27. ^ Вайнбергер и Саул 2004b, стр. 4, уравнение 10
  28. ^ Вайнбергер и Саул 2006, стр. 7, уравнения 14
  29. ^ Вайнбергер и Саул 2004b, стр. 4, уравнение 11
  30. ^ Вайнбергер и Саул 2006, стр. 7, уравнения 15

Ссылки

  • Линиал, Лондон и Рабинович, Натан, Эран и Юрий (1995). «Геометрия графов и некоторые ее алгоритмические приложения». Combinatorica . 15 (2): 215– 245. doi :10.1007/BF01200757. S2CID  5071936.{{cite journal}}: CS1 maint: multiple names: authors list (link)
  • Вайнбергер, Ша и Саул, Килиан К., Фей и Лоуренс К. (4 июля 2004a). Изучение матрицы ядра для нелинейного снижения размерности. Труды Двадцать первой международной конференции по машинному обучению (ICML 2004). Банф, Альберта , Канада.{{cite conference}}: CS1 maint: multiple names: authors list (link)
  • Вайнбергер и Сол, Килиан К. и Лоуренс К. (27 июня 2004 г.). Неконтролируемое обучение многообразий изображений с помощью полуопределенного программирования. Конференция компьютерного общества IEEE 2004 года по компьютерному зрению и распознаванию образов. Том 2.
  • Вайнбергер и Сол, Килиан К. и Лоуренс К. (1 мая 2006 г.). "Неконтролируемое обучение многообразий изображений с помощью полуопределенного программирования" (PDF) . International Journal of Computer Vision . 70 : 77–90 . doi :10.1007/s11263-005-4939-z. S2CID  291166.
  • Лоуренс, Нил Д. (2012). «Унифицированная вероятностная перспектива снижения спектральной размерности: идеи и новые модели». Журнал исследований машинного обучения . 13 (май): 1612. arXiv : 1010.4830 . Bibcode : 2010arXiv1010.4830L.

Дополнительный материал

  • Код MVU Matlab Килиана К. Вайнбергера
Retrieved from "https://en.wikipedia.org/w/index.php?title=Semidefinite_embedding&oldid=1180093242"