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

Карты диффузии — это алгоритм снижения размерности или извлечения признаков, представленный Койфманом и Лафоном ^{[1] [2] [3] [4],} который вычисляет семейство вложений набора данных в евклидово пространство (часто низкоразмерное), координаты которого могут быть вычислены из собственных векторов и собственных значений оператора диффузии данных. Евклидово расстояние между точками во вложенном пространстве равно «расстоянию диффузии» между распределениями вероятностей, центрированными в этих точках. В отличие от линейных методов снижения размерности, таких как анализ главных компонент (PCA), карты диффузии являются частью семейства нелинейных методов снижения размерности , которые фокусируются на обнаружении базового многообразия , из которого были отобраны данные. Интегрируя локальные сходства в разных масштабах, карты диффузии дают глобальное описание набора данных. По сравнению с другими методами алгоритм карты диффузии устойчив к шумовым возмущениям и не требует больших вычислительных затрат.

Следуя ^[3] и ^[5] , карты диффузии можно определить в четыре этапа.

Карты диффузии используют взаимосвязь между диффузией тепла и случайным блужданием цепи Маркова . Основное наблюдение заключается в том, что если мы совершаем случайное блуждание по данным, то переход к ближайшей точке данных более вероятен, чем переход к другой, которая находится далеко. Пусть будет пространством мер , где — набор данных и представляет собой распределение точек на .${\displaystyle (X,{\mathcal {A}},\mu )}$${\displaystyle X}$${\displaystyle \мю}$${\displaystyle X}$

Исходя из этого, связность между двумя точками данных, и , может быть определена как вероятность перехода от к за один шаг случайного блуждания. Обычно эта вероятность указывается в терминах функции ядра двух точек: . Например, популярное ядро ​​Гаусса:${\displaystyle к}$${\displaystyle x}$${\displaystyle у}$${\displaystyle x}$${\displaystyle у}$${\displaystyle k:X\times X\rightarrow \mathbb {R} }$

${\displaystyle k(x,y)=\exp \left(-{\frac {||xy||^{2}}{\epsilon }}\right)}$

В более общем смысле функция ядра имеет следующие свойства:

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

( симметрично)${\displaystyle к}$

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

( сохраняет положительность).${\displaystyle к}$

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

Учитывая , мы можем построить обратимую дискретную цепь Маркова на (процесс, известный как построение Лапласа нормализованного графа):${\displaystyle (X,k)}$${\displaystyle X}$

${\displaystyle d(x)=\int _{X}k(x,y)d\mu (y)}$

и определить:

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

Хотя новое нормализованное ядро ​​не наследует свойство симметричности, оно наследует свойство сохранения положительности и приобретает свойство сохранения:

${\displaystyle \int _{X}p(x,y)d\mu (y)=1}$

Из мы можем построить матрицу перехода цепи Маркова ( ) на . Другими словами, представляет собой вероятность одношагового перехода из в , и дает матрицу перехода t-шага.${\displaystyle p(x,y)}$${\displaystyle М}$${\displaystyle X}$${\displaystyle p(x,y)}$${\displaystyle x}$${\displaystyle у}$${\displaystyle М^{т}}$

Определим матрицу диффузии (она также является версией графовой матрицы Лапласа )${\displaystyle L}$

${\displaystyle L_{i,j}=k(x_{i},x_{j})\,}$

Затем мы определяем новое ядро

${\displaystyle L_{i,j}^{(\alpha )}=k^{(\alpha )}(x_{i},x_{j})={\frac {L_{i,j}}{(d(x_{i})d(x_{j}))^{\alpha }}}\,}$

или эквивалентно,

${\displaystyle L^{(\alpha)}=D^{-\alpha }LD^{-\alpha }\,}$

где D — диагональная матрица и${\displaystyle D_{i,i}=\sum _{j}L_{i,j}.}$

Применим графовую лапласовскую нормализацию к этому новому ядру:

${\displaystyle M=({D}^{(\alpha )})^{- 1}L^{(\alpha )},\,}$

где - диагональная матрица и${\displaystyle D^{(\альфа)}}$${\displaystyle {D}_{i,i}^{(\alpha )}=\sum _{j}L_{i,j}^{(\alpha )}.}$

${\displaystyle p(x_{j},t|x_{i})=M_{i,j}^{t}\,}$

Одна из основных идей диффузионной структуры заключается в том, что запуск цепи вперед во времени (взятие все больших и больших степеней ) раскрывает геометрическую структуру во все больших и больших масштабах (процесс диффузии). В частности, понятие кластера в наборе данных количественно определяется как область, в которой вероятность выхода из этой области низкая (в течение определенного времени t). Таким образом, t не только служит временным параметром, но и играет двойную роль параметра масштаба.${\displaystyle M}$${\displaystyle X}$

Собственное разложение матрицы дает${\displaystyle M^{t}}$

${\displaystyle M_{i,j}^{t}=\sum _{l}\lambda _{l}^{t}\psi _{l}(x_{i})\phi _{l}(x_{j})\,}$

где — последовательность собственных значений и и — биортогональные правые и левые собственные векторы соответственно. Из-за распада спектра собственных значений для достижения заданной относительной точности в этой сумме необходимо всего несколько членов.${\displaystyle \{\lambda _{l}\}}$${\displaystyle M}$${\displaystyle \{\psi _{l}\}}$${\displaystyle \{\phi _{l}\}}$

Причина введения шага нормализации, включающего настройку влияния плотности точек данных на бесконечно малый переход диффузии. В некоторых приложениях выборка данных, как правило, не связана с геометрией многообразия, описание которого нам интересно. В этом случае мы можем установить и оператор диффузии аппроксимирует оператор Лапласа–Бельтрами. Затем мы восстанавливаем риманову геометрию набора данных независимо от распределения точек. Для описания долгосрочного поведения распределения точек системы стохастических дифференциальных уравнений мы можем использовать и полученная цепь Маркова аппроксимирует диффузию Фоккера–Планка . С помощью это сводится к классической нормализации Лапласа графа.${\displaystyle \alpha }$${\displaystyle \alpha =1}$${\displaystyle \alpha =0.5}$${\displaystyle \alpha =0}$

Расстояние диффузии во времени между двумя точками можно измерить как сходство двух точек в пространстве наблюдения со связностью между ними. Оно определяется как${\displaystyle t}$

${\displaystyle D_{t}(x_{i},x_{j})^{2}=\sum _{y}{\frac {(p(y,t|x_{i})-p(y,t|x_{j}))^{2}}{\phi _{0}(y)}}}$

где — стационарное распределение цепи Маркова, заданное первым левым собственным вектором . Явно:${\displaystyle \phi _{0}(y)}$${\displaystyle M}$

${\displaystyle \phi _{0}(y)={\frac {d(y)}{\sum _{z\in X}d(z)}}}$

Интуитивно, мало, если существует большое количество коротких путей, соединяющих и . Есть несколько интересных особенностей, связанных с расстоянием диффузии, основанных на нашем предыдущем обсуждении, которое также служит параметром масштаба:${\displaystyle D_{t}(x_{i},x_{j})}$${\displaystyle x_{i}}$${\displaystyle x_{j}}$${\displaystyle t}$

1. Точки расположены ближе в заданном масштабе (как указано ), если они тесно связаны на графике, тем самым подчеркивая концепцию кластера.${\displaystyle D_{t}(x_{i},x_{j})}$
2. Это расстояние устойчиво к шуму, поскольку расстояние между двумя точками зависит от всех возможных длин путей между точками.${\displaystyle t}$
3. С точки зрения машинного обучения расстояние учитывает все свидетельства, связанные с , что позволяет нам сделать вывод о том, что это расстояние подходит для разработки алгоритмов вывода, основанных на большинстве перевесов. ^[3]${\displaystyle x_{i}}$${\displaystyle x_{j}}$

Расстояние диффузии можно рассчитать с помощью собственных векторов:

${\displaystyle D_{t}(x_{i},x_{j})^{2}=\sum _{l}\lambda _{l}^{2t}(\psi _{l}(x_{i})-\psi _{l}(x_{j}))^{2}\,}$

Таким образом, собственные векторы могут быть использованы как новый набор координат для данных. Карта диффузии определяется как:

${\displaystyle \Psi _{t}(x)=(\lambda _{1}^{t}\psi _{1}(x),\lambda _{2}^{t}\psi _{2}(x),\ldots ,\lambda _{k}^{t}\psi _{k}(x))}$

Из-за распада спектра достаточно использовать только первые k собственных векторов и собственных значений. Таким образом, мы получаем карту диффузии из исходных данных в k -мерное пространство, которое вложено в исходное пространство.

В ^[6] доказано, что

${\displaystyle D_{t}(x_{i},x_{j})^{2}\approx ||\Psi _{t}(x_{i})-\Psi _{t}(x_{j})||^{2}\,}$

поэтому евклидово расстояние в координатах диффузии приблизительно равно расстоянию диффузии.

Базовая структура алгоритма карты диффузии выглядит следующим образом:

Шаг 1. Дана матрица подобия L.

Шаг 2. Нормализуем матрицу по параметру : .${\displaystyle \alpha }$${\displaystyle L^{(\alpha )}=D^{-\alpha }LD^{-\alpha }}$

Шаг 3. Формируем нормализованную матрицу .${\displaystyle M=({D}^{(\alpha )})^{-1}L^{(\alpha )}}$

Шаг 4. Вычислить k наибольших собственных значений и соответствующие им собственные векторы.${\displaystyle M^{t}}$

Шаг 5. Используйте карту диффузии, чтобы получить вложение .${\displaystyle \Psi _{t}}$

В статье ^[6] Надлер и др. показали, как спроектировать ядро, которое воспроизводит диффузию, вызванную уравнением Фоккера–Планка . Они также объяснили, что когда данные аппроксимируют многообразие, можно восстановить геометрию этого многообразия, вычислив аппроксимацию оператора Лапласа–Бельтрами . Это вычисление совершенно нечувствительно к распределению точек и, следовательно, обеспечивает разделение статистики и геометрии данных. Поскольку карты диффузии дают глобальное описание набора данных, они могут измерять расстояния между парами точек выборки в многообразии, в которое встроены данные. Приложения, основанные на картах диффузии, включают распознавание лиц , ^[7] спектральную кластеризацию , низкоразмерное представление изображений, сегментацию изображений, ^[8] сегментацию 3D-моделей, ^[9] проверку говорящего ^[10] и идентификацию, ^[11] выборку на многообразиях, обнаружение аномалий, ^{[12] [13]} закрашивание изображений, ^[14] выявление организации сетей состояния покоя мозга ^[15] и т. д.

Более того, структура диффузионных карт была продуктивно распространена на сложные сети ^[16] , раскрывая функциональную организацию сетей, которая отличается от чисто топологической или структурной.

• Нелинейное уменьшение размерности
• Спектральная кластеризация