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

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

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

Применение НЛДР

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

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

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

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

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

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

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

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

Важные понятия

Картирование Саммона

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

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

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

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

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

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

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

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

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

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

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

Основные кривые и многообразия

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

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

Собственные отображения Лапласа

См. Также: Регуляризация многообразия

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

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

Изомап

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Основная статья: Выравнивание локального касательного пространства

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

Максимальная дисперсия

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

Автоматические кодировщики

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Криволинейный дистанционный анализ

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

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

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

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

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

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

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

$k(x,y)=k(y,x),$

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

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

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

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

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

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

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

Чтобы точно представить марковскую матрицу, $K$ должен быть нормализован соответствующей матрицей степеней $D$:

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

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

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

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

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

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

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

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

Нелинейный PCA

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

Многомерное масштабирование на основе данных

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

Скульптура многообразия

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

РейтингВсе

РейтингВсе разработан для сохранения ранга соседства, а не расстояния. RankVisu особенно полезен при выполнении сложных задач (когда сохранение дистанции не может быть удовлетворительным). Действительно, ранг соседства менее информативен, чем расстояние (ранги можно вывести из расстояний, но расстояния нельзя вывести из рангов), и поэтому его легче сохранить.

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

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

Приближение и проекция равномерного многообразия

Приближение и проекция равномерного многообразия (UMAP) - это метод нелинейного уменьшения размерности. Визуально он похож на t-SNE , но предполагает, что данные равномерно распределены на локально связном римановом многообразии и что риманова метрика локально постоянна или приблизительно локально постоянна.

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

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

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

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

См. также

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

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

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

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

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