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

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

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

Алгоритм

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

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

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

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

Позволять $X\,\!$ быть исходным входом и $Y\,\!$ быть вложением. Если $i,j\,\!$ являются двумя соседями, то ограничение локальной изометрии, которое должно быть удовлетворено, следующее: ^[7]^[8]^[9]

|X_{i}-X_{j}|^{2}=|Y_{i}-Y_{j}|^{2}\,\!

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

G_{ii}+G_{jj}-G_{ij}-G_{ji}=K_{ii}+K_{jj}-K_{ij}-K_{ji}\,\!

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

$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]

$T(Y)={\dfrac {1}{2N}}\sum _{i,j}|Y_{i}-Y_{j}|^{2}$

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

Позволять $\tau =max\{\eta _{ij}|Y_{i}-Y_{j}|^{2}\}\,\!$ где $\eta _{ij}:={\begin{cases}1&{\mbox{if}}\ i{\mbox{ is a neighbour of }}j\\0&{\mbox{otherwise}}.\end{cases}}$

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

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

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]

{\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]

${\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\,\!$ изучается с помощью полуопределенного программирования, результат $Y\,\!$ можно получить с помощью разложения Холецкого .

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

Отсюда следует, что $\alpha \,\!$ -й элемент вывода $Y_{i}\,\!$ является ${\sqrt {\lambda _{\alpha }}}V_{\alpha i}\,\!$ . ^[29]^[30]

См. также

Примечания

^ Вайнбергер, Ша и Саул, 2004a.
^ Вайнбергер и Сол 2004b
^ Вайнбергер и Сол 2006 г.
^ Лоуренс 2012 , стр. 1612.
^ Вайнбергер, Ша и Саул 2004a , стр. 7.
^ Linial, London and Rabinovich 1995
^ Вайнбергер, Ша и Саул, 2004a , стр. 3, уравнение 8.
^ Вайнбергер и Саул 2004b , стр. 3, уравнение 2.
^ Вайнбергер и Саул, 2006 , стр. 4, уравнение 2.
^ Вайнбергер, Ша и Саул 2004a , стр. 3, уравнение 9
^ Вайнбергер и Саул 2004b , стр. 3, уравнение 3.
^ Вайнбергер, Ша и Саул 2004a , стр. 3, уравнение 6
^ Вайнбергер и Саул, 2004b , стр. 3, уравнение 5.
^ Вайнбергер и Саул, 2006 , стр. 5, уравнение 8.
^ Вайнбергер, Ша и Саул, 2004a , стр. 4, уравнение 10.
^ Вайнбергер и Саул, 2004b , стр. 4, уравнение 6.
^ Вайнбергер и Саул, 2006 , стр. 5, уравнение 4.
^ Вайнбергер и Саул 2004b , стр. 4, уравнение 7.
^ Вайнбергер и Саул 2004b , стр. 4, уравнение 8
^ Вайнбергер и Саул, 2006 , стр. 5, уравнение 6.
^ Вайнбергер, Ша и Саул, 2004a , стр. 4, уравнение 11.
^ Вайнбергер и Саул 2004b , стр. 4, уравнение 9
^ Вайнбергер и Саул, 2006 , стр. 6, уравнения с 10 по 13.
^ Вайнбергер, Ша и Саул 2004a , стр. 4, раздел 3.3.
^ Вайнбергер и Саул 2004b , стр. 4, уравнение 9
^ Вайнбергер и Саул, 2006 , стр. 6, уравнения с 10 по 13.
^ Вайнбергер и Саул 2004b , стр. 4, уравнение 10.
^ Вайнбергер и Саул, 2006 , стр. 7, уравнения 14.
^ Вайнбергер и Саул 2004b , стр. 4, уравнение 11.
^ Вайнбергер и Саул, 2006 , стр. 7, уравнения 15.

Ссылки

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

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

Код MVU Matlab Килиана К. Вайнбергера

[1] Вайнбергер, Ша и Саул, 2004a.

[2] Вайнбергер и Сол 2004b

[3] Вайнбергер и Сол 2006 г.

[4] Лоуренс 2012 , стр. 1612.

[5] Вайнбергер, Ша и Саул 2004a , стр. 7.

[6] Linial, London and Rabinovich 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.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]