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

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

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

Определение карт диффузии

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

Связность

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

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

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

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

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

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

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

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

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

Учитывая , мы можем построить обратимую дискретную цепь Маркова на (процесс, известный как построение Лапласа нормализованного графа): ${\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 M}$ ${\displaystyle X}$ ${\displaystyle p(x,y)}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle M^{t}}$

Определим матрицу диффузии (она также является версией графовой матрицы Лапласа ) ${\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^{(\alpha )}}$ ${\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] , раскрывая функциональную организацию сетей, которая отличается от чисто топологической или структурной.

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

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

Ссылки

1. Coifman, RR; Lafon, S; Lee, AB; Maggioni, M; Nadler, B; Warner, F; Zucker, SW (2005). «Геометрические диффузии как инструмент для гармонического анализа и определения структуры данных: карты диффузии». PNAS . 102 (21): 7426–7431. Bibcode :2005PNAS..102.7426C. doi : 10.1073/pnas.0500334102 . PMC  1140422 . PMID  15899970.
2. Coifman, RR; Lafon, S; Lee, AB; Maggioni, M; Nadler, B; Warner, F; Zucker, SW (2005). «Геометрические диффузии как инструмент для гармонического анализа и определения структуры данных: многомасштабные методы». PNAS . 102 (21): 7432–7437. Bibcode :2005PNAS..102.7432C. doi : 10.1073/pnas.0500896102 . PMC 1140426 . PMID  15899969. 
3. Coifman, RR; S. Lafon. (2006). «Карты диффузии». Прикладной и вычислительный гармонический анализ . 21 : 5–30. doi :10.1016/j.acha.2006.04.006. S2CID  17160669.
4. Лафон, СС (2004). Диффузионные карты и геометрические гармоники (PDF) (PhD). Йельский университет.
5. De la Porte, J.; Herbst, BM; Hereman, W; Van der Walt, SJ (2008). "Введение в диффузионные карты". Труды девятнадцатого ежегодного симпозиума Ассоциации распознавания образов Южной Африки (PRASA) . CiteSeerX 10.1.1.309.674 . 
6. Nadler, Boaz; Stéphane Lafon; Ronald R. Coifman; Ioannis G. Kevrekidis (2005). "Diffusion Maps, Spectral Clustering and Eigenfunctions of Fokker–Planck Operators" (PDF) . Advances in Neural Information Processing Systems . 18 . arXiv : math/0506090 . Bibcode :2005math......6090N.
7. Баркан, Орен; Вайль, Джонатан; Вольф, Лиор; Ароновиц, Хагай. «Быстрое распознавание лиц с помощью многомерного векторного умножения» (PDF) . Труды Международной конференции IEEE по компьютерному зрению 2013 : 1960–1967.
8. Зеев, Фарбман; Фаттал Раанан; Лишински Дани (2010). «Карты диффузии для редактирования изображений с учетом краев». ACM Trans. Graph . 29 (6): 145:1–145:10. doi :10.1145/1882261.1866171.
9. Оана, Сиди; ван Кайк, Оливер; Клейман, Янир; Чжан, Хао; Коэн-Ор, Дэниел (2011). Неконтролируемая ко-сегментация набора фигур с помощью спектральной кластеризации в пространстве дескрипторов (PDF) . Труды ACM по графике .
10. Баркан, Орен; Ароновиц, Хагай (2013). «Карты диффузии для проверки диктора на основе PLDA» (PDF) . Труды Международной конференции IEEE по акустике, речи и обработке сигналов : 7639–7643.
11. Михалевски, Ян; Тальмон, Ронен; Коэн, Израиль (2011). Идентификация говорящего с использованием карт диффузии (PDF) . Европейская конференция по обработке сигналов 2011.
12. Мишне, Гал; Коэн, Израиль (2013). «Обнаружение многомасштабных аномалий с использованием карт диффузии». Избранные темы IEEE по обработке сигналов . 7 (1): 111–123. Bibcode : 2013ISTSP...7..111M. doi : 10.1109/jstsp.2012.2232279. S2CID  1954466.
13. Шабат, Гил; Сегев, Дэвид; Авербух, Амир (2018-01-07). «Раскрытие неизвестных неизвестных в больших данных финансовых услуг с помощью неконтролируемых методологий: текущие и будущие тенденции». Семинар KDD 2017 по обнаружению аномалий в финансах . 71 : 8–19.
14. Гепштейн, Шай; Келлер, Йоси (2013). «Завершение изображения с помощью диффузионных карт и спектральной релаксации». Труды IEEE по обработке изображений . 22 (8): 2983–2994. Bibcode : 2013ITIP...22.2983G. doi : 10.1109/tip.2013.2237916. PMID  23322762. S2CID  14375333.
15. Маргулис, Дэниел С.; Гош, Сатраджит С.; Гулас, Александрос; Фалькевич, Марсель; Хантенбург, Джулия М.; Лангс, Георг; Безгин, Глеб; Эйкхофф, Саймон Б.; Кастелланос, Ф. Ксавье; Петридес, Майкл; Джефферис, Элизабет; Смоллвуд, Джонатан (2016). «Расположение сети режима по умолчанию вдоль главного градиента макромасштабной корковой организации». Труды Национальной академии наук . 113 (44): 12574–12579. Bibcode : 2016PNAS..11312574M. doi : 10.1073/pnas.1608282113 . PMC 5098630. PMID  27791099 . 
16. Де Доменико, Манлио (2017). «Геометрия диффузии раскрывает возникновение функциональных кластеров в коллективных явлениях». Physical Review Letters . 118 (16): 168301. arXiv : 1704.07068 . Bibcode :2017PhRvL.118p8301D. doi :10.1103/PhysRevLett.118.168301. PMID  28474920. S2CID  2638868.