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

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

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

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

Связанные методы линейной декомпозиции [ править ]

• Независимый компонентный анализ (ICA).
• Анализ главных компонент (PCA) (также называемый теоремой Карунена – Лоэва  - KLT).
• Разложение по сингулярным числам (SVD).
• Факторный анализ .

Приложения NLDR [ править ]

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

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

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

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

Таким образом, должно быть очевидно, что NLDR имеет несколько приложений в области компьютерного зрения. Например, рассмотрим робота, который использует камеру для навигации в замкнутой статической среде. Изображения, полученные с помощью этой камеры, можно рассматривать как образцы на многообразии в многомерном пространстве, и внутренние переменные этого многообразия будут представлять положение и ориентацию робота. Эта утилита не ограничивается роботами. Динамические системы , более общий класс систем, который включает роботов, определяются в терминах многообразия. Активные исследования в области NLDR направлены на раскрытие многообразия наблюдений, связанных с динамическими системами, для разработки методов моделирования таких систем и обеспечения их автономной работы. ^[3]

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

Важные понятия [ править ]

Карта Саммона [ править ]

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

Самоорганизующаяся карта [ править ]

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

Анализ основных компонентов ядра [ править ]

Возможно, наиболее широко используемым алгоритмом уменьшения размерности является ядерный PCA . ^[6] 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, создавая зависимую от данных матрицу ядра. ^[7]${\displaystyle \Phi (\mathbf {x} )}$${\displaystyle \Phi }$

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

Основные кривые и многообразия [ править ]

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

Собственные карты лапласа [ править ]

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

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

В приложениях классификации низкоразмерные коллекторы могут использоваться для моделирования классов данных, которые могут быть определены из наборов наблюдаемых экземпляров. Каждый наблюдаемый экземпляр может быть описан двумя независимыми факторами, называемыми «контент» и «стиль», где «контент» - это инвариантный фактор, связанный с сущностью класса, а «стиль» выражает вариации в этом классе между экземплярами. ^[16] К сожалению, лапласовские собственные карты могут не дать связного представления интересующего класса, когда обучающие данные состоят из экземпляров, значительно различающихся по стилю. ^[17]В случае классов, которые представлены многомерными последовательностями, были предложены структурные лапласианские собственные карты для преодоления этой проблемы путем добавления дополнительных ограничений в граф информации о соседстве лапласовских собственных карт, чтобы лучше отражать внутреннюю структуру класса. ^[18] Более конкретно, граф используется для кодирования как последовательной структуры многомерных последовательностей, так и, чтобы минимизировать стилистические вариации, близости между точками данных различных последовательностей или даже внутри последовательности, если она содержит повторы. Используя динамическое преобразование времени , близость обнаруживается путем нахождения соответствий между и внутри участков многомерных последовательностей, которые демонстрируют высокое сходство. Эксперименты по распознаванию активности по зрению, приложения классификации ориентации объектов и восстановления трехмерных поз человека продемонстрировали дополнительную ценность структурных лапласовских собственных карт при работе с многомерными данными последовательности. ^[18] Расширение структурных лапласовских собственных карт, обобщенных лапласовских собственных карт привело к созданию многообразий, в которых одно из измерений конкретно представляет вариации стиля. Это оказалось особенно полезным в таких приложениях, как отслеживание шарнирного тела человека и извлечение силуэта. ^[19]

Isomap [ править ]

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

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

Локально-линейное встраивание [ править ]

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

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

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

Веса W _ij относятся к сумме вклада, которую имеет точка X _j при восстановлении точки X _i . Функция стоимости минимизируется при двух ограничениях: (a) Каждая точка данных X _i восстанавливается только по своим соседям, таким образом, принудительно устанавливая W _ij равным нулю, если точка X _j не является соседом точки X _i, и каждой строки весовой матрицы равно 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}|{\mathbf {Y} _{i}-\sum _{j}{\mathbf {W} _{ij}\mathbf {Y} _{j}}|}^{\mathsf {2}}}$

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

Гессенское локально-линейное вложение (Hessian LLE) [ править ]

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

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

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

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

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

Развертывание максимальной дисперсии [ править ]

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

Автоэнкодеры [ править ]

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

Гауссовские модели скрытых переменных процесса [ править ]

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

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

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

Другие алгоритмы [ править ]

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

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

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

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

Карты заражения [ править ]

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

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

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

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

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

Анализ криволинейных расстояний [ править ]

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

Диффеоморфное уменьшение размерности [ править ]

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

Выравнивание коллектора [ править ]

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

Карты диффузии [ править ]

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

В приведенном выше уравнении означает, что это ближайший сосед . Правильно, геодезическое расстояние должно использоваться для фактического измерения расстояний на коллекторе . Поскольку точная структура многообразия недоступна, для ближайших соседей геодезическое расстояние аппроксимируется евклидовым расстоянием. Выбор модулирует наше представление о близости в том смысле, что если, то и если, то . Первое означает, что произошла очень небольшая диффузия, а второе подразумевает, что процесс диффузии почти завершен. Различные стратегии выбора можно найти в ^[38]${\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}$определяет случайное блуждание по набору данных, что означает, что ядро ​​фиксирует некоторую локальную геометрию набора данных. Цепь Маркова определяет быстрое и медленное направления распространения значений ядра. По мере того, как блуждание распространяется вперед во времени, информация о локальной геометрии накапливается так же, как локальные переходы (определяемые дифференциальными уравнениями) динамической системы. ^[37] Метафора диффузии возникает из определения расстояния распространения в семье { }${\displaystyle D_{t}}$${\displaystyle _{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}}$

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

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

Нелинейный PCA [ править ]

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

Управляемое данными многомерное масштабирование [ править ]

Data-Driven High Dimensional Scaling (DD-HDS) ^[41] тесно связано с картированием Sammon и анализом криволинейных компонентов, за исключением того, что (1) оно одновременно наказывает ложные окрестности и разрывы, фокусируясь на малых расстояниях как в исходном, так и в выходном пространстве, и (2) он учитывает явление концентрации меры , адаптируя весовую функцию к распределению расстояний.

Моделирование коллекторов [ править ]

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

RankVisu [ править ]

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

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

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

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

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

Методы на основе матриц близости [ править ]

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

См. Также [ править ]

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

Ссылки [ править ]

Внешние ссылки [ править ]

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