Нелинейное уменьшение размерности

Проекция данных на многообразия меньшей размерности

Вверху слева: 3D-набор данных из 1000 точек в спиральной полосе (также известной как швейцарский рулет ) с прямоугольным отверстием посередине. Вверху справа: исходное 2D-многообразие, использованное для генерации 3D-набора данных. Внизу слева и справа: 2D-восстановления многообразия соответственно с использованием алгоритмов LLE и Hessian LLE, реализованных с помощью инструментария Modular Data Processing.

Нелинейное снижение размерности , также известное как обучение многообразиям , представляет собой любой из различных родственных методов, направленных на проекцию многомерных данных, потенциально существующих в нелинейных многообразиях, которые не могут быть адекватно охвачены методами линейной декомпозиции, на скрытые многообразия меньшей размерности с целью либо визуализации данных в пространстве меньшей размерности, либо изучения самого отображения (либо из пространства большей размерности в вложение меньшей размерности, либо наоборот). ^{[1] [2]} Методы, описанные ниже, можно понимать как обобщения методов линейной декомпозиции, используемых для снижения размерности , таких как разложение по сингулярным значениям и анализ главных компонент .

Применение NLDR

Машинам может быть сложно работать с данными высокой размерности, требуя значительного времени и пространства для анализа. Это также представляет собой проблему для людей, поскольку трудно визуализировать или понимать данные в более чем трех измерениях. Уменьшение размерности набора данных, при сохранении его основных характеристик относительно нетронутыми, может сделать алгоритмы более эффективными и позволить аналитикам визуализировать тенденции и закономерности.

График двумерных точек, полученный в результате использования алгоритма NLDR. В этом случае Manifold Sculpting используется для сведения данных всего к двум измерениям (вращение и масштаб).

Представления данных с уменьшенной размерностью часто называют «внутренними переменными». Это описание подразумевает, что это значения, из которых были получены данные. Например, рассмотрим набор данных, содержащий изображения буквы «А», которая была масштабирована и повернута на различные величины. Каждое изображение имеет размер 32×32 пикселя. Каждое изображение может быть представлено как вектор из 1024 значений пикселей. Каждая строка является образцом на двумерном многообразии в 1024-мерном пространстве ( пространство Хэмминга ). Внутренняя размерность равна двум, поскольку для получения данных были изменены две переменные (вращение и масштаб). Информация о форме или виде буквы «А» не является частью внутренних переменных, поскольку она одинакова в каждом случае. Нелинейное уменьшение размерности отбросит коррелированную информацию (букву «А») и восстановит только изменяющуюся информацию (вращение и масштаб). На изображении справа показаны примеры изображений из этого набора данных (в целях экономии места показаны не все входные изображения) и график двумерных точек, полученный в результате использования алгоритма NLDR (в данном случае использовался Manifold Sculpting) для сведения данных всего к двум измерениям.

PCA (алгоритм линейного уменьшения размерности) используется для сокращения этого же набора данных до двух измерений, но полученные значения не так хорошо организованы.

Для сравнения, если использовать анализ главных компонент , который является линейным алгоритмом уменьшения размерности, для уменьшения этого же набора данных до двух измерений, то полученные значения не будут так хорошо организованы. Это показывает, что многомерные векторы (каждый из которых представляет букву «A»), которые выбирают это многообразие, изменяются нелинейно.

Таким образом, должно быть очевидно, что NLDR имеет несколько приложений в области компьютерного зрения. Например, рассмотрим робота, который использует камеру для навигации в закрытой статической среде. Изображения, полученные этой камерой, можно считать образцами на многообразии в многомерном пространстве, а внутренние переменные этого многообразия будут представлять положение и ориентацию робота.

Инвариантные многообразия представляют общий интерес для редукции порядка модели в динамических системах . В частности, если в фазовом пространстве есть притягивающее инвариантное многообразие, близлежащие траектории будут сходиться к нему и оставаться на нем неопределенно долго, что делает его кандидатом на редукцию размерности динамической системы. Хотя существование таких многообразий в общем случае не гарантируется, теория спектральных подмногообразий (SSM) дает условия для существования уникальных притягивающих инвариантных объектов в широком классе динамических систем. ^[3] Активные исследования в области NLDR стремятся развернуть многообразия наблюдений, связанные с динамическими системами, для разработки методов моделирования. ^[4]

Ниже перечислены некоторые из наиболее известных методов нелинейного снижения размерности .

Важные концепции

Картографирование Сэммона

Картирование Сэммона — один из первых и самых популярных методов NLDR.

Аппроксимация основной кривой одномерным SOM ​​( ломаная линия с красными квадратами, 20 узлов). Первый главный компонент представлен синей прямой линией. Точки данных — маленькие серые кружки. Для PCA доля необъясненной дисперсии в этом примере составляет 23,23%, для SOM — 6,86%. ^[5]

Самоорганизующаяся карта

Самоорганизующаяся карта ( SOM, также называемая картой Кохонена ) и ее вероятностный вариант — генеративное топографическое картирование (GTM) — используют точечное представление во встроенном пространстве для формирования модели скрытой переменной на основе нелинейного отображения встроенного пространства в многомерное пространство. ^[6] Эти методы связаны с работой над сетями плотности, которые также основаны на той же вероятностной модели.

Анализ главных компонент ядра

Возможно, наиболее широко используемый алгоритм для размерной редукции — это ядерный PCA . ^[7] PCA начинается с вычисления ковариационной матрицы матрицы ${\displaystyle m\times n}$ ${\displaystyle \mathbf {X} }$

${\displaystyle C={\frac {1}{m}}\sum _{i=1}^{m}{\mathbf {x} _{i}\mathbf {x} _{i}^{\mathsf {T}}}.}$

Затем он проецирует данные на первые k собственных векторов этой матрицы. Для сравнения, KPCA начинает с вычисления ковариационной матрицы данных после преобразования в более многомерное пространство,

${\displaystyle C={\frac {1}{m}}\sum _{i=1}^{m}{\Phi (\mathbf {x} _{i})\Phi (\mathbf {x} _{i})^{\mathsf {T}}}.}$

Затем он проецирует преобразованные данные на первые k собственных векторов этой матрицы, как и PCA. Он использует трюк с ядром , чтобы разложить большую часть вычислений, так что весь процесс может быть выполнен без фактического вычисления . Конечно, должен быть выбран таким образом, чтобы у него было известное соответствующее ядро. К сожалению, нетривиально найти хорошее ядро ​​для данной проблемы, поэтому KPCA не дает хороших результатов с некоторыми проблемами при использовании стандартных ядер. Например, известно, что он плохо работает с этими ядрами на многообразии швейцарского рулета . Однако можно рассматривать некоторые другие методы, которые хорошо работают в таких условиях (например, собственные карты Лапласа, LLE), как особые случаи ядра PCA путем построения матрицы ядра, зависящей от данных. ^[8] ${\displaystyle \Phi (\mathbf {x} )}$ ${\displaystyle \Phi }$

KPCA имеет внутреннюю модель, поэтому ее можно использовать для отображения точек на ее внедрении, которые не были доступны во время обучения.

Главные кривые и многообразия

Применение основных кривых: Нелинейный индекс качества жизни. ^[9] Точки представляют данные 171 страны ООН в 4-мерном пространстве, образованном значениями 4 показателей: валовой продукт на душу населения , ожидаемая продолжительность жизни , детская смертность , заболеваемость туберкулезом . Различные формы и цвета соответствуют различным географическим местоположениям. Красная жирная линия представляет основную кривую , аппроксимирующую набор данных. Эта основная кривая была получена методом эластичной карты . ^[10]

Главные кривые и многообразия дают естественную геометрическую основу для нелинейного снижения размерности и расширяют геометрическую интерпретацию PCA путем явного построения вложенного многообразия и кодирования с использованием стандартной геометрической проекции на многообразие. Этот подход был первоначально предложен Тревором Хасти в его диссертации 1984 года ^[11] , которую он официально представил в 1989 году. ^[12] Эта идея была далее исследована многими авторами. ^[13] Как определить «простоту» многообразия, зависит от проблемы, однако, она обычно измеряется внутренней размерностью и/или гладкостью многообразия. Обычно главное многообразие определяется как решение задачи оптимизации. Целевая функция включает качество аппроксимации данных и некоторые штрафные члены за изгиб многообразия. Популярные начальные приближения генерируются линейным PCA и SOM Кохонена.

Собственные карты Лапласа

Собственные карты Лапласа используют спектральные методы для выполнения снижения размерности. ^[14] Этот метод основан на базовом предположении, что данные лежат в многообразии низкой размерности в пространстве высокой размерности. ^[15] Этот алгоритм не может встраивать точки вне выборки, но существуют методы, основанные на регуляризации гильбертова пространства воспроизводящего ядра, для добавления этой возможности. ^[16] Такие методы можно применять и к другим нелинейным алгоритмам снижения размерности.

Традиционные методы, такие как анализ главных компонент, не учитывают внутреннюю геометрию данных. Собственные карты Лапласа строят граф из информации о соседстве набора данных. Каждая точка данных служит узлом на графе, а связность между узлами регулируется близостью соседних точек (например, с использованием алгоритма k-ближайших соседей ). Граф, сгенерированный таким образом, можно рассматривать как дискретную аппроксимацию низкоразмерного многообразия в высокоразмерном пространстве. Минимизация функции стоимости на основе графика гарантирует, что точки, близкие друг к другу на многообразии, отображаются близко друг к другу в низкоразмерном пространстве, сохраняя локальные расстояния. Собственные функции оператора Лапласа–Бельтрами на многообразии служат в качестве измерений вложения, поскольку при мягких условиях этот оператор имеет счетный спектр, который является базисом для квадратично интегрируемых функций на многообразии (сравните с рядами Фурье на многообразии единичной окружности). Попытки поместить собственные карты Лапласа на прочную теоретическую основу увенчались определенным успехом, поскольку при определенных не ограничивающих предположениях было показано, что графическая матрица Лапласа сходится к оператору Лапласа–Бельтрами, когда число точек стремится к бесконечности. ^[15]

Изомап

Isomap ^[17] представляет собой комбинацию алгоритма Флойда–Уоршелла с классическим многомерным шкалированием (MDS). Классический MDS берет матрицу парных расстояний между всеми точками и вычисляет положение для каждой точки. Isomap предполагает, что парные расстояния известны только между соседними точками, и использует алгоритм Флойда–Уоршелла для вычисления парных расстояний между всеми остальными точками. Это эффективно оценивает полную матрицу парных геодезических расстояний между всеми точками. Затем Isomap использует классический MDS для вычисления сокращенных размерных положений всех точек. Landmark-Isomap является вариантом этого алгоритма, который использует ориентиры для увеличения скорости за счет некоторой потери точности.

В обучении многообразиям предполагается, что входные данные выбираются из многообразия низкой размерности , которое встроено в векторное пространство более высокой размерности. Основная интуиция MVU заключается в использовании локальной линейности многообразий и создании отображения, которое сохраняет локальные окрестности в каждой точке базового многообразия.

Локально-линейное вложение

Локально-линейное встраивание (LLE) было представлено примерно в то же время, что и Isomap. ^[18] Оно имеет несколько преимуществ перед Isomap, включая более быструю оптимизацию при реализации для использования преимуществ алгоритмов разреженной матрицы и лучшие результаты при решении многих задач. LLE также начинается с поиска набора ближайших соседей каждой точки. Затем он вычисляет набор весов для каждой точки, который наилучшим образом описывает точку как линейную комбинацию ее соседей. Наконец, он использует метод оптимизации на основе собственных векторов для поиска низкоразмерного встраивания точек, так что каждая точка по-прежнему описывается той же линейной комбинацией своих соседей. LLE имеет тенденцию плохо обрабатывать неравномерные плотности выборок, поскольку нет фиксированной единицы, которая бы предотвращала дрейф весов, поскольку различные регионы различаются по плотности выборок. LLE не имеет внутренней модели.

LLE вычисляет барицентрические координаты точки X _i на основе ее соседей X _j . Исходная точка реконструируется линейной комбинацией, заданной весовой матрицей W _ij , ее соседей. Ошибка реконструкции задается функцией стоимости E ( W ).

${\displaystyle E(W)=\sum _{i}\left|\mathbf {X} _{i}-\sum _{j}{\mathbf {W} _{ij}\mathbf {X} _{j}}\right|^{2}}$

Веса W _ij относятся к величине вклада точки X _j при реконструкции точки X _i . Функция стоимости минимизируется при двух ограничениях: (a) Каждая точка данных X _i реконструируется только из своих соседей, тем самым заставляя W _ij быть равным нулю, если точка X _j не является соседом точки X _i и (b) Сумма каждой строки матрицы весов равна 1.

${\displaystyle \sum _{j}{\mathbf {W} _{ij}}=1}$

Исходные точки данных собираются в пространстве размерности D , и цель алгоритма — уменьшить размерность до d таким образом, чтобы D >> d . Те же веса W _ij , которые реконструируют i- ю точку данных в пространстве размерности D , будут использоваться для реконструкции той же точки в пространстве размерности d . На основе этой идеи создается карта сохранения соседства. Каждая точка X _i в пространстве размерности D отображается на точку Y _i в пространстве размерности d путем минимизации функции стоимости

${\displaystyle C(Y)=\sum _{i}\left|\mathbf {Y} _{i}-\sum _{j}{\mathbf {W} _{ij}\mathbf {Y} _{j}}\right|^{2}}$

В этой функции стоимости, в отличие от предыдущей, веса W _ij сохраняются фиксированными, а минимизация выполняется в точках Y _i для оптимизации координат. Эту задачу минимизации можно решить, решив разреженную задачу собственных значений N X N ( где N — число точек данных), нижние d ненулевых собственных векторов которой обеспечивают ортогональный набор координат. Обычно точки данных восстанавливаются из K ближайших соседей, измеряемых с помощью евклидова расстояния . Для такой реализации алгоритм имеет только один свободный параметр K, который можно выбрать с помощью перекрестной проверки.

Гессеновское локально-линейное вложение (Гессианское локально-линейное вложение)

Как и LLE, Hessian LLE также основан на методах разреженных матриц. ^[19] Он имеет тенденцию давать результаты гораздо более высокого качества, чем LLE. К сожалению, он имеет очень дорогостоящую вычислительную сложность, поэтому он не очень подходит для многообразий с большой выборкой. Он не имеет внутренней модели.

Модифицированное локально-линейное вложение (MLLE)

Модифицированный LLE (MLLE) ^[20] — это еще один вариант LLE, который использует несколько весов в каждой окрестности для решения проблемы обусловленности локальной матрицы весов, которая приводит к искажениям в картах LLE. Грубо говоря, несколько весов являются локальной ортогональной проекцией исходных весов, созданных LLE. Создатели этого регуляризованного варианта также являются авторами локального выравнивания касательного пространства (LTSA), которое подразумевается в формулировке MLLE при понимании того, что глобальная оптимизация ортогональных проекций каждого вектора весов, по сути, выравнивает локальные касательные пространства каждой точки данных. Теоретические и эмпирические выводы из правильного применения этого алгоритма имеют далеко идущие последствия. ^[21]

Локальное выравнивание касательного пространства

LTSA ^[22] основан на интуиции, что при правильном развертывании многообразия все касательные гиперплоскости к многообразию станут выровненными. Он начинается с вычисления k -ближайших соседей каждой точки. Он вычисляет касательное пространство в каждой точке, вычисляя d -первые главные компоненты в каждой локальной окрестности. Затем он оптимизируется для поиска вложения, которое выровняет касательные пространства.

Максимальное разворачивание дисперсии

Развертка максимальной дисперсии , Isomap и локально-линейное вложение разделяют общую интуицию, основанную на представлении о том, что если многообразие развернуто должным образом, то дисперсия по точкам максимизируется. Его начальный шаг, как и Isomap и локально-линейное вложение, заключается в поиске k -ближайших соседей каждой точки. Затем он стремится решить задачу максимизации расстояния между всеми несоседними точками, ограниченными таким образом, чтобы расстояния между соседними точками сохранялись. Основной вклад этого алгоритма - это метод приведения этой задачи к задаче полуопределенного программирования. К сожалению, решатели полуопределенного программирования имеют высокую вычислительную стоимость. Как и локально-линейное вложение, он не имеет внутренней модели.

Автоэнкодеры

Автоэнкодер — это нейронная сеть прямого распространения , которая обучена аппроксимировать функцию идентичности. То есть она обучена отображать вектор значений в тот же вектор. При использовании для целей снижения размерности один из скрытых слоев сети ограничен содержанием только небольшого количества сетевых единиц. Таким образом, сеть должна научиться кодировать вектор в небольшое количество измерений, а затем декодировать его обратно в исходное пространство. Таким образом, первая половина сети представляет собой модель, которая отображает из высокоразмерного в низкоразмерное пространство, а вторая половина отображает из низкоразмерного в высокоразмерное пространство. Хотя идея автоэнкодеров довольно стара, ^[23] обучение глубоких автоэнкодеров только недавно стало возможным благодаря использованию ограниченных машин Больцмана и автоэнкодеров со стекированным шумоподавлением. С автоэнкодерами связан алгоритм NeuroScale, который использует функции напряжения, вдохновленные многомерным масштабированием и отображениями Сэммона (см. выше), чтобы изучить нелинейное отображение из высокоразмерного во встроенное пространство. Отображения в NeuroScale основаны на сетях радиальных базисных функций .

Модели гауссовского процесса со скрытыми переменными

Модели скрытых переменных гауссовского процесса (GPLVM) ^[24] являются вероятностными методами снижения размерности, которые используют гауссовские процессы (GP) для поиска нелинейного вложения малой размерности для многомерных данных. Они являются расширением вероятностной формулировки PCA. Модель определяется вероятностно, а затем скрытые переменные маргинализуются, а параметры получаются путем максимизации правдоподобия. Как и в ядерном PCA, они используют функцию ядра для формирования нелинейного отображения (в форме гауссовского процесса ). Однако в GPLVM отображение происходит из встроенного (скрытого) пространства в пространство данных (например, в сетях плотности и GTM), тогда как в ядерном PCA оно происходит в противоположном направлении. Первоначально он был предложен для визуализации многомерных данных, но был расширен для построения общей модели многообразия между двумя пространствами наблюдения. GPLVM и его многочисленные варианты были предложены специально для моделирования движения человека, например, ограниченная сзади GPLVM, динамическая модель GP (GPDM), сбалансированная GPDM (B-GPDM) и топологически ограниченная GPDM. Чтобы захватить эффект связи многообразий позы и походки в анализе походки, было предложено многослойное совместное многообразие походка-поза. ^[25]

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

Широко используется t-распределенное стохастическое соседнее встраивание (t-SNE) ^[26] . Это один из методов семейства стохастических соседских встраиваний. Алгоритм вычисляет вероятность того, что пары точек данных в пространстве высокой размерности связаны, а затем выбирает низкоразмерные встраивания, которые производят похожее распределение.

Другие алгоритмы

Карта реляционной перспективы

Карта реляционной перспективы — это алгоритм многомерного масштабирования . Алгоритм находит конфигурацию точек данных на многообразии, моделируя многочастичную динамическую систему на замкнутом многообразии, где точки данных отображаются на частицы, а расстояния (или различия) между точками данных представляют собой отталкивающую силу. По мере того, как многообразие постепенно увеличивается в размерах, многочастичная система постепенно остывает и сходится к конфигурации, которая отражает информацию о расстоянии точек данных.

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

Карта реляционной перспективы была введена в ^[27] . Сначала алгоритм использовал плоский тор в качестве многообразия изображений, затем он был расширен (в программном обеспечении VisuMap для использования других типов замкнутых многообразий, таких как сфера , проективное пространство и бутылка Клейна , в качестве многообразий изображений).

Карты заражения

Карты заражения используют множественные заражения в сети для отображения узлов в виде облака точек. ^[28] В случае модели глобальных каскадов скорость распространения можно регулировать с помощью порогового параметра . Для карты заражения это эквивалентно алгоритму Isomap . ${\displaystyle t\in [0,1]}$ ${\displaystyle t=0}$

Анализ криволинейных компонентов

Анализ криволинейных компонентов (CCA) ищет конфигурацию точек в выходном пространстве, которая сохраняет исходные расстояния настолько, насколько это возможно, при этом фокусируясь на малых расстояниях в выходном пространстве (в отличие от отображения Сэммона , которое фокусируется на малых расстояниях в исходном пространстве). ^[29]

Следует отметить, что CCA, как итеративный алгоритм обучения, на самом деле начинает с фокусировки на больших расстояниях (как алгоритм Сэммона), а затем постепенно меняет фокус на малые расстояния. Информация о малых расстояниях перезапишет информацию о больших расстояниях, если придется идти на компромиссы между ними.

Функция напряжения CCA связана с суммой правых дивергенций Брегмана. ^[30]

Анализ криволинейного расстояния

CDA ^[29] обучает самоорганизующуюся нейронную сеть подгонять многообразие и стремится сохранить геодезические расстояния в его внедрении. Он основан на анализе криволинейных компонентов (который расширил отображение Сэммона), но вместо этого использует геодезические расстояния.

Диффеоморфное уменьшение размерности

Диффеоморфное уменьшение размерности или Diffeomap ^[31] изучает гладкое диффеоморфное отображение, которое переносит данные в линейное подпространство меньшей размерности. Методы решают для гладкого индексированного по времени векторного поля, так что потоки вдоль поля, которые начинаются в точках данных, заканчиваются в линейном подпространстве меньшей размерности, тем самым пытаясь сохранить попарные различия как при прямом, так и при обратном отображении.

Выравнивание коллектора

Выравнивание многообразий использует предположение, что разрозненные наборы данных, созданные схожими процессами генерации, будут совместно использовать схожее базовое представление многообразия. Изучая проекции из каждого исходного пространства в общее многообразие, восстанавливаются соответствия, и знания из одной области могут быть перенесены в другую. Большинство методов выравнивания многообразий рассматривают только два набора данных, но эта концепция распространяется на произвольное количество начальных наборов данных. ^[32]

Карты диффузии

Диффузионные карты используют связь между диффузией тепла и случайным блужданием ( цепь Маркова ); проводится аналогия между оператором диффузии на многообразии и матрицей перехода Маркова, работающей с функциями, определенными на графике, узлы которого были выбраны из многообразия. ^[33] В частности, пусть набор данных представлен как . Основное предположение диффузионной карты заключается в том, что высокоразмерные данные лежат на низкоразмерном многообразии размерности . Пусть X представляет набор данных и представляет распределение точек данных на X . Далее, определим ядро , которое представляет некоторое понятие сродства точек в X . Ядро обладает следующими свойствами ^[34] ${\displaystyle \mathbf {X} =[x_{1},x_{2},\ldots ,x_{n}]\in \Omega \subset \mathbf {R^{D}} }$ ${\displaystyle \mathbf {d} }$ ${\displaystyle \mu }$ ${\displaystyle {\mathit {k}}}$

${\displaystyle k(x,y)=k(y,x),}$

k симметричен

${\displaystyle k(x,y)\geq 0\qquad \forall x,y,k}$

k сохраняет положительность

Таким образом, можно рассматривать отдельные точки данных как узлы графа, а ядро ​​k — как определение некоторого рода сродства на этом графе. Граф симметричен по построению, поскольку ядро ​​симметрично. Здесь легко увидеть, что из кортежа ( X , k ) можно построить обратимую цепь Маркова . Этот метод является общим для множества полей и известен как граф Лапласиан.

Например, график K = ( X , E ) можно построить с использованием гауссовского ядра.

${\displaystyle K_{ij}={\begin{cases}e^{-\|x_{i}-x_{j}\|_{2}^{2}/\sigma ^{2}}&{\text{if }}x_{i}\sim x_{j}\\0&{\text{otherwise}}\end{cases}}}$

В приведенном выше уравнении обозначает, что является ближайшим соседом . Соответственно, геодезическое расстояние должно использоваться для фактического измерения расстояний на многообразии . Поскольку точная структура многообразия недоступна, для ближайших соседей геодезическое расстояние аппроксимируется евклидовым расстоянием. Выбор модулирует наше понятие близости в том смысле, что если то и если то . Первое означает, что произошла очень незначительная диффузия, в то время как последнее подразумевает, что процесс диффузии почти завершен. Различные стратегии выбора можно найти в. ^[35] ${\displaystyle x_{i}\sim x_{j}}$ ${\displaystyle x_{i}}$ ${\displaystyle x_{j}}$ ${\displaystyle \sigma }$ ${\displaystyle \|x_{i}-x_{j}\|_{2}\gg \sigma }$ ${\displaystyle K_{ij}=0}$ ${\displaystyle \|x_{i}-x_{j}\|_{2}\ll \sigma }$ ${\displaystyle K_{ij}=1}$ ${\displaystyle \sigma }$

Для точного представления марковской матрицы ее необходимо нормализовать с помощью соответствующей матрицы степеней : ${\displaystyle K}$ ${\displaystyle D}$

${\displaystyle P=D^{-1}K.}$

${\displaystyle P}$теперь представляет собой цепь Маркова. - вероятность перехода из в за один временной шаг. Аналогично вероятность перехода из в за t временных шагов определяется как . Здесь матрица умножена сама на себя t раз. ${\displaystyle P(x_{i},x_{j})}$ ${\displaystyle x_{i}}$ ${\displaystyle x_{j}}$ ${\displaystyle x_{i}}$ ${\displaystyle x_{j}}$ ${\displaystyle P^{t}(x_{i},x_{j})}$ ${\displaystyle P^{t}}$ ${\displaystyle P}$

Матрица Маркова представляет собой некоторое понятие локальной геометрии набора данных X. Основное различие между картами диффузии и анализом главных компонент заключается в том, что в картах диффузии рассматриваются только локальные особенности данных, а не рассматриваются корреляции всего набора данных. ${\displaystyle P}$

${\displaystyle K}$определяет случайное блуждание по набору данных, что означает, что ядро ​​захватывает некоторую локальную геометрию набора данных. Цепь Маркова определяет быстрые и медленные направления распространения через значения ядра. По мере того, как блуждание распространяется вперед во времени, информация о локальной геометрии агрегируется таким же образом, как локальные переходы (определяемые дифференциальными уравнениями) динамической системы. ^[34] Метафора диффузии возникает из определения расстояния диффузии семейства ${\displaystyle \{D_{t}\}_{t\in N}}$

${\displaystyle D_{t}^{2}(x,y)=\|p_{t}(x,\cdot )-p_{t}(y,\cdot )\|^{2}}$

Для фиксированного t определяет расстояние между любыми двумя точками набора данных на основе связности путей: значение будет тем меньше, чем больше путей соединяют x с y и наоборот. Поскольку величина включает сумму по всем путям длины t, гораздо более устойчива к шуму в данных, чем геодезическое расстояние. учитывает все отношения между точками x и y при вычислении расстояния и служит лучшим понятием близости, чем просто евклидово расстояние или даже геодезическое расстояние. ${\displaystyle D_{t}}$ ${\displaystyle D_{t}(x,y)}$ ${\displaystyle D_{t}(x,y)}$ ${\displaystyle D_{t}}$ ${\displaystyle D_{t}}$

Локальное многомерное масштабирование

Локальное многомерное масштабирование выполняет многомерное масштабирование в локальных регионах, а затем использует выпуклую оптимизацию для объединения всех частей. ^[36]

Нелинейный PCA

Нелинейный PCA (NLPCA) использует обратное распространение для обучения многослойного персептрона (MLP) для подгонки к многообразию. ^[37] В отличие от типичного обучения MLP, которое обновляет только веса, NLPCA обновляет как веса, так и входы. То есть, и веса, и входы рассматриваются как скрытые значения. После обучения скрытые входы являются низкоразмерным представлением наблюдаемых векторов, и MLP отображает это низкоразмерное представление в высокоразмерное пространство наблюдения.

Высокоразмерное масштабирование на основе данных

Масштабирование на основе данных высокой размерности (DD-HDS) ^[38] тесно связано с картографированием Сэммона и анализом криволинейных компонентов, за исключением того, что (1) оно одновременно штрафует ложные соседства и разрывы, фокусируясь на малых расстояниях как в исходном, так и в выходном пространстве, и что (2) оно учитывает явление концентрации меры , адаптируя весовую функцию к распределению расстояний.

Многообразная скульптура

Manifold Sculpting ^[39] использует градуированную оптимизацию для поиска вложения. Как и другие алгоритмы, он вычисляет k -ближайших соседей и пытается найти вложение, которое сохраняет отношения в локальных окрестностях. Он медленно масштабирует дисперсию из более высоких измерений, одновременно корректируя точки в более низких измерениях, чтобы сохранить эти отношения. Если скорость масштабирования мала, он может найти очень точные вложения. Он может похвастаться более высокой эмпирической точностью, чем другие алгоритмы с несколькими проблемами. Его также можно использовать для уточнения результатов других алгоритмов обучения многообразий. Однако он с трудом разворачивает некоторые многообразия, если только не используется очень низкая скорость масштабирования. У него нет модели.

РангVisu

RankVisu ^[40] предназначен для сохранения ранга соседства, а не расстояния. RankVisu особенно полезен для сложных задач (когда сохранение расстояния не может быть достигнуто удовлетворительным образом). Действительно, ранг соседства менее информативен, чем расстояние (ранги могут быть выведены из расстояний, но расстояния не могут быть выведены из рангов), и его сохранение, таким образом, проще.

Топологически ограниченное изометрическое вложение

Топологически ограниченное изометрическое вложение (TCIE) ^[41] — это алгоритм, основанный на аппроксимации геодезических расстояний после фильтрации геодезических, несовместимых с евклидовой метрикой. Нацеленный на исправление искажений, вызванных использованием Isomap для отображения внутренне невыпуклых данных, TCIE использует весовой метод наименьших квадратов MDS для получения более точного отображения. Алгоритм TCIE сначала обнаруживает возможные граничные точки в данных, а во время вычисления геодезической длины отмечает несовместимые геодезические, чтобы им был дан небольшой вес в последующей взвешенной мажорации напряжений .

Равномерное многообразие аппроксимации и проекции

Равномерная аппроксимация и проекция многообразия (UMAP) — это нелинейный метод снижения размерности. ^[42] Он похож на t-SNE. ^[43]

Методы, основанные на матрицах близости

Метод, основанный на матрицах близости, — это метод, в котором данные представляются алгоритму в виде матрицы подобия или матрицы расстояний . Все эти методы попадают в более широкий класс метрического многомерного масштабирования . Различия, как правило, заключаются в различиях в том, как вычисляются данные близости; например, isomap , локально линейные вложения , развертка максимальной дисперсии и отображение Сэммона (которое на самом деле не является отображением) являются примерами методов метрического многомерного масштабирования.

Программное обеспечение

• Waffles — это библиотека C++ с открытым исходным кодом, содержащая реализации LLE, Manifold Sculpting и некоторых других алгоритмов обучения многообразий.
• UMAP.jl реализует метод для языка программирования Julia .
• Метод также был реализован на Python (код доступен на GitHub ).

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

• Гипотеза многообразия
• Спектральное подмногообразие
• Теорема Такена
• Теорема вложения Уитни
• Дискриминантный анализ
• Эластичная карта
• Особенности обучения
• Растущая самоорганизующаяся карта (GSOM)
• Самоорганизующаяся карта (SOM)

Ссылки

1. Лоуренс, Нил Д. (2012). «Унифицированная вероятностная перспектива для снижения спектральной размерности: идеи и новые модели». Журнал исследований машинного обучения . 13 (май): 1609–38. arXiv : 1010.4830 . Bibcode : 2010arXiv1010.4830L.
2. Ли, Джон А.; Верлейсен, Мишель (2007). Нелинейное снижение размерности . Springer. ISBN 978-0-387-39350-6.
3. Халлер, Джордж; Понсиоен, Стен (2016). «Нелинейные нормальные моды и спектральные подмногообразия: существование, уникальность и использование в редукции модели». Нелинейная динамика . 86 (3): 1493–1534. arXiv : 1602.00560 . doi : 10.1007/s11071-016-2974-z. S2CID  44074026.
4. Гашлер, М.; Мартинес, Т. (2011). Временное нелинейное снижение размерности (PDF) . Труды Международной объединенной конференции по нейронным сетям IJCNN'11. стр. 1959–66.
5. Иллюстрация подготовлена ​​с использованием бесплатного программного обеспечения: Mirkes, EM (2011). «Анализ главных компонент и самоорганизующиеся карты: апплет». Университет Лестера.
6. Yin, Hujun (2007). "3. Learning Nonlinear Principal Manifolds by Self-Organising Maps". В Gorban, AN; Kégl, B.; Wunsch, DC; Zinovyev, A. (ред.). Principal Manifolds for Data Visualization and Dimension Reduction . Lecture Notes in Computer Science and Engineering. Vol. 58. Springer. pp. 68–95. ISBN 978-3-540-73749-0.
7. Шёлкопф, Б.; Смола, А.; Мюллер, К.-Р. (1998). «Анализ нелинейных компонентов как проблема собственных значений ядра». Нейронные вычисления . 10 (5). Массачусетский технологический институт Пресс : 1299–1319. дои : 10.1162/089976698300017467. S2CID  6674407.
8. Хэм, Джихун; Ли, Дэниел Д.; Мика, Себастьян; Шёлькопф, Бернхард. «Ядро взгляда на уменьшение размерности многообразий». Труды 21-й Международной конференции по машинному обучению, Банф, Канада, 2004 г. doi : 10.1145/1015330.1015417.
9. Горбань, АН; Зиновьев, А. (2010). «Главные многообразия и графы на практике: от молекулярной биологии до динамических систем». International Journal of Neural Systems . 20 (3): 219–232. arXiv : 1001.1122 . doi : 10.1142/S0129065710002383. PMID  20556849. S2CID  2170982.
10. А. Зиновьев, ViDaExpert — инструмент визуализации многомерных данных Института Кюри , Париж.
11. Hastie, T. (ноябрь 1984 г.). Principal Curves and Surfaces (PDF) (PhD). Stanford Linear Accelerator Center, Stanford University. Архивировано (PDF) из оригинала 2 августа 2019 г.
12. Hastie, T. ; Stuetzle, W. (июнь 1989). "Главные кривые" (PDF) . Журнал Американской статистической ассоциации . 84 (406): 502–6. doi :10.1080/01621459.1989.10478797.
13. Горбань, AN ; Кегль, B.; Вунш, DC; Зиновьев, A., ред. (2007). Главные многообразия для визуализации данных и уменьшения размерности. Конспект лекций по информатике и инжинирингу (LNCSE). Том 58. Springer. ISBN 978-3-540-73749-0.
14. Белкин, Михаил; Ниёги, Партха (2001). «Лапласовские собственные карты и спектральные методы для встраивания и кластеризации» (PDF) . Достижения в области нейронных систем обработки информации . 14. MIT Press: 586–691. ISBN 0-262-27173-7. OCLC  52710683.
15. Белкин, Михаил (август 2003 г.). Проблемы обучения на многообразиях (PhD). Кафедра математики, Чикагский университет.Код Matlab для собственных карт Лапласа можно найти в алгоритмах на Ohio-state.edu
16. Бенжио, Йошуа; Пайеман, Жан-Франсуа; Винсент, Паскаль; Делальо, Оливье; Ле Ру, Николя; Уиме, Мари (2004). "Расширения вне выборки для LLE, Isomap, MDS, Eigenmaps и спектральной кластеризации" (PDF) . Достижения в области нейронных систем обработки информации . Том 16. MIT Press. ISBN 0-262-20152-6.
17. Тененбаум, Дж. Б.; де Сильва, В.; Лэнгфорд, Дж. К. (2000). «Глобальная геометрическая структура для нелинейного снижения размерности» (PDF) . Science . 290 (5500): 2319–23. Bibcode :2000Sci...290.2319T. doi :10.1126/science.290.5500.2319. PMID  11125149. S2CID  221338160.
18. Роуайс, СТ; Саул, ЛК (2000). «Нелинейное снижение размерности путем локально-линейного вложения». Science . 290 (5500): 2323–6. Bibcode :2000Sci...290.2323R. doi :10.1126/science.290.5500.2323. PMID  11125150. S2CID  5987139.
19. Донохо, Д.; Граймс, К. (2003). «Собственные карты Гессе: методы локального линейного встраивания для многомерных данных». Proc Natl Acad Sci USA . 100 (10): 5591–6. Bibcode : 2003PNAS..100.5591D. doi : 10.1073/pnas.1031596100 . PMC 156245. PMID  16576753 . 
20. Чжан, З.; Ван, Дж. (2006). «MLLE: Модифицированное локально-линейное вложение с использованием нескольких весов». NIPS'06: Труды 19-й Международной конференции по нейронным системам обработки информации : 1593–1600.
21. Сидху, Гаган (2019). «Локально-линейное встраивание и выбор признаков фМРТ в психиатрической классификации». IEEE Journal of Translational Engineering in Health and Medicine . 7 : 1–11. arXiv : 1908.06319 . doi : 10.1109/JTEHM.2019.2936348. PMC 6726465. PMID 31497410.  S2CID 201832756  . 
22. Чжан, Чжэньюэ; Хунъюань Чжа (2005). «Главные многообразия и нелинейное уменьшение размерности с помощью локального выравнивания касательного пространства». Журнал SIAM по научным вычислениям . 26 (1): 313–338. CiteSeerX 10.1.1.211.9957 . doi :10.1137/s1064827502419154. 
23. DeMers, D.; Cottrell, GW (1993). "Нелинейное снижение размерности". Достижения в области нейронных систем обработки информации . Том 5. С. 580–7. ISBN 1558600159. OCLC  928936290.
24. Лоуренс, Н. (2005). «Вероятностный нелинейный главный компонентный анализ с моделями гауссовского процесса со скрытыми переменными». Журнал исследований машинного обучения . 6 : 1783–1816.
25. Дин, М.; Фань, Г. (2015). «Многослойные совместные многообразия походки и позы для моделирования движения походки человека». Труды IEEE по кибернетике . 45 (11): 2413–24. doi :10.1109/TCYB.2014.2373393. PMID  25532201. S2CID  15591304.
26. Ван дер Маатен, LJP; Хинтон, GE (2008). «Визуализация многомерных данных с использованием t-SNE» (PDF) . Журнал исследований машинного обучения . 9 : 2579–2605.
27. Ли, Джеймс X. (2004). «Визуализация многомерных данных с помощью реляционной перспективной карты» (PDF) . Визуализация информации . 3 : 49–59. doi :10.1057/palgrave.ivs.9500051. S2CID  7566939.
28. Тейлор, Д.; Климм, Ф.; Харрингтон, HA; Крамар, М.; Мишайков, К.; Портер, MA; Муха, П. Дж. (2015). «Топологический анализ данных карт заражения для изучения процессов распространения в сетях». Nature Communications . 6 : 7723. arXiv : 1408.1168 . Bibcode :2015NatCo...6.7723T. doi :10.1038/ncomms8723. PMC 4566922 . PMID  26194875. 
29. Demartines, P.; Hérault, J. (1997). "Анализ криволинейных компонентов: самоорганизующаяся нейронная сеть для нелинейного отображения наборов данных" (PDF) . IEEE Transactions on Neural Networks . 8 (1): 148–154. doi :10.1109/72.554199. PMID  18255618.
30. Сан, Джиган; Кроу, Малкольм; Файф, Колин (2010). «Анализ криволинейных компонентов и расхождения Брегмана» (PDF) . Европейский симпозиум по искусственным нейронным сетям (Esann) . Публикации d-side. С. 81–86.
31. Вальдер, Кристиан; Шёлькопф, Бернхард (2009). «Диффеоморфное снижение размерности» (PDF) . Достижения в области нейронных систем обработки информации . Том 22. MIT Press. С. 1713–20.
32. Ван, Чанг; Махадеван, Шридхар (июль 2008 г.). Выравнивание многообразий с использованием анализа Прокруста (PDF) . 25-я Международная конференция по машинному обучению. С. 1120–7.
33. Лафон, Стефан (май 2004 г.). Диффузионные карты и геометрические гармонии (PhD). Йельский университет .
34. Coifman, Ronald R.; Lafon, Stephane (июль 2006 г.). "Diffusion Maps" (PDF) . Applied and Computational Harmonic Analysis . 21 (1): 5–30. doi :10.1016/j.acha.2006.04.006. S2CID  17160669.
35. Бах, Б. (2008). Карты диффузии: приложения и анализ (магистратура). Оксфордский университет.
36. Venna, J.; Kaski, S. (2006). «Локальное многомерное масштабирование». Neural Networks . 19 (6–7): 889–899. doi :10.1016/j.neunet.2006.05.014. PMID  16787737.
37. Шольц, М.; Каплан, Ф.; Гай, КЛ; Копка, Дж.; Селбиг, Дж. (2005). «Нелинейный PCA: подход с отсутствующими данными». Биоинформатика . 21 (20). Oxford University Press: 3887–95. doi : 10.1093/bioinformatics/bti634 . hdl : 11858/00-001M-0000-0014-2B1F-2 . PMID  16109748.
38. S. Lespinats, M. Verleysen, A. Giron, B. Fertil, DD-HDS: инструмент для визуализации и исследования многомерных данных, IEEE Transactions on Neural Networks 18 (5) (2007) 1265–1279.
39. Гашлер, М. и Вентура, Д. и Мартинес, Т., Итеративное нелинейное снижение размерности с помощью скульптурирования многообразий , в Platt, JC и Koller, D. и Singer, Y. и Roweis, S., редактор, Advances in Neural Information Processing Systems 20, стр. 513–520, MIT Press, Кембридж, Массачусетс, 2008
40. Леспинатс С., Фертиль Б., Вильмен П. и Эро Ж., Рангвизу: Картографирование из соседней сети, Нейрокомпьютинг, т. 72 (13–15), стр. 2964–2978, 2009.
41. Росман, Г.; Бронштейн, М.М.; Бронштейн, А.М.; Киммел, Р. (2010). «Нелинейное снижение размерности с помощью топологически ограниченного изометрического вложения» (PDF) . International Journal of Computer Vision . 89 (1): 56–68. doi :10.1007/s11263-010-0322-1. S2CID  1365750.
42. Макиннес, Леланд; Хили, Джон; Мелвилл, Джеймс (2018-12-07). «Аппроксимация и проекция равномерного многообразия для уменьшения размерности». arXiv : 1802.03426 .
43. "UMAP: Аппроксимация и проекция однородного многообразия для уменьшения размерности — документация umap 0.3". umap-learn.readthedocs.io . Получено 04.05.2019 .

Дальнейшее чтение

• Мерфи, Кевин П. (2022). «Обучение многообразий». Вероятностное машинное обучение . MIT Press. стр. 682–699. ISBN 978-0-262-04682-4.

Внешние ссылки

• Изомап
• Генеративное топографическое картографирование
• Диссертация Майка Типпинга
• Модель латентной переменной гауссовского процесса
• Локально линейное вложение
• Карта реляционной перспективы
• Домашняя страница DD-HDS
• Домашняя страница RankVisu
• Краткий обзор Diffusion Maps
• Нелинейный PCA с помощью нейронных сетей автоэнкодера