Развертывание максимальной дисперсии (MVU) , также известное как полуопределенное встраивание (SDE), представляет собой алгоритм в компьютерных науках, который использует полуопределенное программирование для выполнения нелинейного уменьшения размерности многомерных векторных входных данных. [1] [2] [3]
Это мотивировано наблюдением, что анализ главных компонентов ядра (kPCA) не снижает размерность данных [4], поскольку он использует трюк ядра для нелинейного отображения исходных данных во внутреннее пространство продукта .
Алгоритм
MVU создает отображение из входных векторов большой размерности в некоторое евклидово векторное пространство низкой размерности в следующих шагах: [5]
- Создается граф соседства . Каждый вход связан со своими k-ближайшими входными векторами (согласно метрике евклидова расстояния), а все k-ближайшие соседи связаны друг с другом. Если данные отобраны достаточно хорошо, результирующий график является дискретной аппроксимацией лежащего в основе многообразия.
- Граф окрестности «разворачивается» с помощью полуопределенного программирования. Вместо того, чтобы изучать выходные векторы напрямую, полуопределенное программирование направлено на поиск внутренней матрицы произведения, которая максимизирует попарные расстояния между любыми двумя входами, которые не связаны в графе соседства, сохраняя при этом расстояния до ближайших соседей.
- В конечном итоге низкоразмерное вложение достигается путем применения многомерного масштабирования к выученной матрице внутреннего продукта.
Шаги применения полуопределенного программирования с последующим шагом уменьшения линейной размерности для восстановления низкоразмерного вложения в евклидово пространство были впервые предложены Линиалом , Лондоном и Рабиновичем. [6]
Формулировка оптимизации
Позволять быть исходным вводом и быть вложением. Еслиявляются двумя соседями, то необходимо выполнить ограничение локальной изометрии: [7] [8] [9]
Позволять быть матрицы Грама из а также (например: ). Мы можем выразить указанное выше ограничение для каждой соседней точки с точки зрения : [10] [11]
Кроме того, мы также хотим ограничить вложение центрировать в начале координат: [12] [13] [14]
Как описано выше, за исключением того, что расстояния между соседними точками сохраняются, алгоритм стремится максимизировать попарное расстояние каждой пары точек. Максимизируемая целевая функция: [15] [16] [17]
Интуитивно максимизация функции, описанной выше, эквивалентна оттягиванию точек как можно дальше друг от друга и, следовательно, «развертыванию» многообразия. Ограничение локальной изометрии [18]
Позволять где
предотвращает расхождение целевой функции (уход в бесконечность).
Поскольку на графике N точек, расстояние между любыми двумя точками . Затем мы можем оценить целевую функцию следующим образом: [19] [20]
Целевая функция может быть переписана чисто в виде матрицы Грама: [21] [22] [23]
Наконец, оптимизацию можно сформулировать так: [24] [25] [26]
После матрицы Грама изучается полуопределенным программированием, вывод можно получить с помощью разложения Холецкого .
В частности, матрицу Грама можно записать как где это i-й элемент собственного вектора собственного значения . [27] [28]
Смотрите также
Заметки
- ^ Вайнбергер, Ша и Саул 2004a
- ^ Вайнбергер и Сол 2004b
- ^ Вайнбергер и Сол 2006
- ^ Лоуренс 2012 , стр. 1612
- Перейти ↑ Weinberger, Sha and Saul 2004a , page 7.
- ^ Linial, Лондон и Рабинович 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
- ^ Weinberger and Saul 2004b , страница 4, уравнение 9
- ^ Вайнбергер и Саул 2006 , стр. 6, уравнения с 10 по 13
- ↑ Weinberger, Sha and Saul 2004a , страница 4, раздел 3.3
- ^ Weinberger and Saul 2004b , страница 4, уравнение 9
- ^ Вайнбергер и Саул 2006 , стр. 6, уравнения с 10 по 13
- ^ Вайнбергер и Сол 2004b , страница 4, уравнение 10
- ^ Вайнбергер и Сол 2006 , стр.7, уравнения 14
- ^ Вайнбергер и Сол 2004b , страница 4, уравнение 11
- ^ Вайнбергер и Сол 2006 , стр.7, уравнения 15
Рекомендации
- Линиал, Лондон и Рабинович, Натан, Эран и Юрий (1995). «Геометрия графов и некоторые ее алгоритмические приложения» . Combinatorica . 15 (2): 215–245. DOI : 10.1007 / BF01200757 . S2CID 5071936 .
- Вайнбергер, Ша и Саул, Килиан К., Фей и Лоуренс К. (4 июля 2004 г.). Изучение матрицы ядра для нелинейного уменьшения размерности . Труды Двадцать первой международной конференции по машинному обучению (ICML 2004). Банф, Альберта , Канада.
- Вайнбергер и Сол, Килиан К. и Лоуренс К. (27 июня 2004b). Неконтролируемое обучение многообразий изображений с помощью полуопределенного программирования . Конференция компьютерного общества IEEE 2004 года по компьютерному зрению и распознаванию образов. 2 .
- Вайнбергер и Сол, Килиан К. и Лоуренс К. (1 мая 2006 г.). «Неконтролируемое обучение многообразий изображений с помощью полуопределенного программирования» (PDF) . Международный журнал компьютерного зрения . 70 : 77–90. DOI : 10.1007 / s11263-005-4939-Z . S2CID 291166 .
- Лоуренс, Нил Д. (2012). «Единая вероятностная перспектива для уменьшения спектральной размерности: идеи и новые модели» . Журнал исследований в области машинного обучения . 13 (май): 1612. arXiv : 1010.4830 . Bibcode : 2010arXiv1010.4830L .
Дополнительный материал
- Код Килиана К. Вайнбергера MVU Matlab