Топологический анализ данных

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

Первоначальная мотивация - изучить форму данных. TDA объединила алгебраическую топологию и другие инструменты чистой математики, чтобы обеспечить математически строгое изучение «формы». Главный инструмент - постоянная гомология , адаптация гомологии к данным облака точек . Устойчивая гомология применяется ко многим типам данных во многих областях. Более того, ее математическая основа имеет еще и теоретическое значение. Уникальные особенности TDA делают его многообещающим мостом между топологией и геометрией.

Основная теория [ править ]

Интуиция [ править ]

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

Предпосылка, лежащая в основе TDA, заключается в том, что форма имеет значение. Реальные данные в больших размерах почти всегда разрежены и, как правило, имеют релевантные особенности малых размеров. Одна из задач TDA - дать точную характеристику этого факта. Наглядным примером является простая система хищник-жертва, управляемая уравнениями Лотки – Вольтерра . ^[1] Легко заметить, что траектория системы образует замкнутый круг в пространстве состояний. TDA предоставляет инструменты для обнаружения и количественной оценки такого повторяющегося движения. ^[2]

Многие алгоритмы анализа данных, в том числе используемые в TDA, требуют выбора различных параметров. Без предварительного знания предметной области трудно выбрать правильный набор параметров для набора данных. Основная идея стойкой гомологиив том, что мы можем использовать информацию, полученную из всех значений параметра. Конечно, одно только это понимание сделать легко; сложная часть - это кодирование этого огромного количества информации в понятной и простой для представления форме. С TDA есть математическая интерпретация, когда информация является группой гомологии. В общем, предполагается, что функции, которые сохраняются для широкого диапазона параметров, являются «истинными» функциями. Предполагается, что особенности, сохраняющиеся только для узкого диапазона параметров, являются шумом, хотя теоретическое обоснование этого неясно. ^[3]

Ранняя история [ править ]

Предшественники полной концепции стойкой гомологии со временем появлялись постепенно. ^[4] В 1990 году Патрицио Фрозини ввел функцию размера, которая эквивалентна 0-й постоянной гомологии. ^[5] Спустя почти десять лет Ванесса Робинс изучала образы гомоморфизмов, индуцированных включением. ^[6] Наконец, вскоре после этого Edelsbrunner et al. представил концепцию устойчивой гомологии вместе с эффективным алгоритмом и его визуализацией в виде диаграммы устойчивости. ^[7] Карлссон и др. переформулировал первоначальное определение и дал эквивалентный метод визуализации, называемый штрих-кодами персистентности ^[8], интерпретирующий персистентность на языке коммутативной алгебры. ^[9]Инвариант штрих-кода эквивалентен канонической форме, введенной Баранниковым в 1996 году для изучения теории Морса. ^[10]

Концепции [ править ]

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

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

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

Модуль персистентности, индексированный с помощью, является векторным пространством для каждого и линейной картой всякий раз , так что для всех и всякий раз ^[11] Эквивалентное определение - это функтор, рассматриваемый как частично упорядоченное множество, в категорию векторных пространств.${\ Displaystyle \ mathbb {U}}$${\ Displaystyle \ mathbb {Z}}$${\ displaystyle U_ {t}}$${\ Displaystyle т \ в \ mathbb {Z}}$${\ displaystyle u_ {t} ^ {s}: U_ {s} \ to U_ {t}}$${\ displaystyle s \ leq t}$${\ Displaystyle и_ {т} ^ {т} = 1}$${\ displaystyle t}$${\ displaystyle u_ {t} ^ {s} u_ {s} ^ {r} = u_ {t} ^ {r}}$${\ displaystyle r \ leq s \ leq t.}$${\ Displaystyle \ mathbb {Z}}$

Постоянная группа гомологии точечного облака модуль устойчивости определяется как , где это Чех комплекс радиуса облака точек и является группой гомологии.${\ displaystyle PH}$${\ Displaystyle PH_ {k} (X) = \ prod H_ {k} (X_ {r})}$${\ displaystyle X_ {r}}$${\ displaystyle r}$${\ displaystyle X}$${\ displaystyle H_ {k}}$

Сохранение штрих - кода является мультимножеством интервалов в , а диаграмма , устойчивость является мультимножеством точек ( ).${\ Displaystyle \ mathbb {R}}$${\ displaystyle \ Delta}$${\ displaystyle: = \ {(u, v) \ in \ mathbb {R} ^ {2} \ mid u, v \ geq 0, u \ leq v \}}$

Вассерстин расстояние между двумя персистенции диаграмм и определяется как${\ displaystyle X}$${\ displaystyle Y}$

$${\ Displaystyle W_ {p} [L_ {q}] (X, Y): = \ inf _ {\ varphi: X \ to Y} \ left [\ sum _ {x \ in X} \ Vert x- \ varphi (x) \ Vert _ {q} \ right] ^ {1 / p}}$$

${\ displaystyle 1 \ leq p, q \ leq \ infty}$

${\ displaystyle \ varphi}$

${\ displaystyle X}$

${\ displaystyle Y}$

Расстояние узкого места между и является${\ displaystyle X}$${\ displaystyle Y}$

$${\ displaystyle W _ {\ infty} [L_ {q}] (X, Y): = \ inf _ {\ varphi: X \ to Y} \ sup _ {x \ in X} \ Vert x- \ varphi (x ) \ Vert _ {q}.}$$

${\ displaystyle p = \ infty}$

Базовое свойство [ править ]

Структурная теорема [ править ]

Первая классификационная теорема для стойких гомологий появилась в 1994 г. ^[10] через канонические формы Баранникова. Классификационная теорема, интерпретирующая настойчивость на языке коммутативной алгебры, появилась в 2005 г .: ^[9] для конечно порожденного модуля персистентности с полевыми коэффициентами, ${\ displaystyle C}$${\ displaystyle F}$

$${\ displaystyle H (C; F) \ simeq \ bigoplus _ {i} x ^ {t_ {i}} \ cdot F [x] \ oplus \ left (\ bigoplus _ {j} x ^ {r_ {j}} \ cdot (F [x] / (x ^ {s_ {j}} \ cdot F [x])) \ right).}$$

${\ displaystyle t_ {i}}$

${\ displaystyle r_ {j}}$

${\ displaystyle s_ {j}}$

${\ displaystyle s_ {j} + r_ {j}}$

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

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

Стабильность желательна, поскольку она обеспечивает устойчивость к шуму. Если - любое пространство, гомеоморфное симплициальному комплексу и являющееся непрерывными ручными ^[13] функциями, то векторные пространства персистентности и конечно представлены, и , где относится к расстоянию узкого места ^[14] и является отображением, принимающим непрерывное ручное к диаграмме персистентности ее -й гомологии.${\ displaystyle X}$${\displaystyle f,g:X\to \mathbb {R} }$${\displaystyle \{H_{k}(f^{-1}([0,r]))\}}$${\displaystyle \{H_{k}(g^{-1}([0,r]))\}}$${\displaystyle W_{\infty }(D(f),D(g))\leq \lVert f-g\rVert _{\infty }}$${\displaystyle W_{\infty }}$${\displaystyle D}$${\displaystyle k}$

Рабочий процесс [ править ]

Основной рабочий процесс в TDA: ^[15]

облако точек

${\displaystyle \to }$

вложенные комплексы

${\displaystyle \to }$

модуль постоянства

${\displaystyle \to }$

штрих-код или диаграмма

1. Если это облако точек, замените его вложенным семейством симплициальных комплексов (например, комплекс Чеха или Виеториса-Рипса). Этот процесс превращает облако точек в фильтрацию симплициальных комплексов. Взятие гомологии каждого комплекса в этой фильтрации дает модуль персистентности${\displaystyle X}$${\displaystyle X}$ ${\displaystyle X_{r}}$
   $${\displaystyle H_{i}(X_{r_{0}})\to H_{i}(X_{r_{1}})\to H_{i}(X_{r_{2}})\to \cdots }$$

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

Графически говоря,

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

Первый алгоритм по всем полям для устойчивых гомологий в алгебраической топологии был описан Баранниковым ^[10] путем приведения к канонической форме верхнетреугольными матрицами. Первый алгоритм устойчивой гомологии был предложен Edelsbrunner et al. ^[7] Зомородиан и Карлссон дали первый практический алгоритм для вычисления устойчивых гомологий по всем полям. ^[9] Книга Эдельсбруннера и Харера дает общее руководство по вычислительной топологии. ^[17]${\displaystyle F_{2}}$

Одна из проблем, возникающих при вычислениях, - это выбор комплекса. Чех комплекс и Виторис-рипы комплекс являются наиболее естественным на первый взгляд; однако их размер быстро растет с увеличением количества точек данных. Комплекс Виеториса – Рипса предпочтительнее комплекса Чеха, потому что его определение проще, а комплекс Чеха требует дополнительных усилий для определения в общем конечном метрическом пространстве. Были изучены эффективные способы снизить вычислительные затраты на гомологию. Например, α-комплекс и комплекс-свидетель используются для уменьшения размера и размера комплексов. ^[18]

Недавно дискретная теория Морса показала многообещающие возможности для вычислительной гомологии, поскольку она может свести данный симплициальный комплекс к гораздо меньшему клеточному комплексу, который гомотопен исходному. ^[19] Это сокращение фактически может быть выполнено, поскольку комплекс построен с использованием теории матроидов , что приведет к дальнейшему увеличению производительности. ^[20] Другой недавний алгоритм экономит время, игнорируя классы гомологии с низкой персистентностью. ^[21]

Доступны различные программные пакеты, такие как javaPlex , Dionysus , Perseus , PHAT , DIPHA , GUDHI , Ripser и TDAstats . Сравнение этих инструментов выполнено Otter et al. ^[22] Giotto-tda - это пакет Python, предназначенный для интеграции TDA в рабочий процесс машинного обучения с помощью API scikit-learn . TDA пакета R может рассчитывать недавно изобретенные концепции, такие как ландшафт и оценка расстояния между ядрами. ^[23] Набор инструментов топологииспециализируется на непрерывных данных, определенных на множествах низкой размерности (1, 2 или 3), что обычно встречается в научной визуализации . Другой пакет R, TDAstats , реализует быструю библиотеку C ++ Ripser для вычисления постоянной гомологии. ^[24] Он также использует вездесущий пакет ggplot2 для создания воспроизводимых, настраиваемых, качественных для публикации визуализаций постоянной гомологии, в частности топологических штрих-кодов и диаграмм устойчивости. В приведенном ниже примере кода дается пример того, как можно использовать язык программирования R для вычисления постоянной гомологии.

# установить пакет из CRAN и загрузить наборы данных install.packages ( "TDAstats" ) library ( "TDAstats" ) data ( "unif2d" ) data ( "circle2d" )# вычислить постоянную гомологию для обоих наборов данных unif.phom  <-  calculate_homology ( unif2d ) circ.phom  <-  calculate_homology ( circle2d )# построить равномерно распределенное облако точек как диаграмму устойчивости plot_persist ( unif.phom )# построить облако точек круга как топологический штрих-код # мы видим одну постоянную полосу, как и ожидалось для круга (один цикл / цикл) plot_barcode ( circ.phom )

Визуализация [ править ]

Данные большого размера невозможно визуализировать напрямую. Было изобретено множество методов для извлечения низкоразмерной структуры из набора данных, таких как анализ главных компонентов и многомерное масштабирование . ^[25] Однако важно отметить, что сама проблема некорректна, поскольку в одном и том же наборе данных можно найти множество различных топологических характеристик. Таким образом, изучение визуализации многомерных пространств имеет центральное значение для TDA, хотя оно не обязательно предполагает использование устойчивых гомологий. Однако в последнее время были предприняты попытки использовать постоянную гомологию при визуализации данных. ^[26]

Карлссон и др. предложили общий метод под названием MAPPER . ^[27] Он наследует идею Серра о том, что покрытие сохраняет гомотопию. ^[28] Обобщенная формулировка MAPPER выглядит следующим образом:

Позвольте и быть топологическими пространствами и позвольте быть непрерывным отображением. Позвольте быть конечным открытым покрытием . Выход MAPPER - это нерв откатной крышки , где каждый прообраз разделяется на связанные компоненты. ^[26] Это очень общая концепция, частными случаями которой являются граф Риба ^[29] и деревья слияния.${\displaystyle X}$${\displaystyle Z}$${\displaystyle f:X\to Z}$${\displaystyle \mathbb {U} =\{U_{\alpha }\}_{\alpha \in A}}$${\displaystyle Z}$${\textstyle M(\mathbb {U} ,f):=N(f^{-1}(\mathbb {U} ))}$

Это не совсем исходное определение. ^[27] Карлссон и др. выберите быть или и накройте его открытыми множествами, пересекающимися не более чем двумя. ^[3] Это ограничение означает, что выходные данные имеют форму сложной сети . Поскольку топология конечного облака точек тривиальна, методы кластеризации (например, одиночная связь ) используются для создания аналога связанных наборов в прообразе, когда MAPPER применяется к фактическим данным.${\displaystyle Z}$${\displaystyle \mathbb {R} }$${\displaystyle \mathbb {R} ^{2}}$${\displaystyle f^{-1}(U)}$

С математической точки зрения MAPPER - это разновидность графа Риба . Если самое большее одномерно, то для каждого ,${\textstyle M(\mathbb {U} ,f)}$${\displaystyle i\geq 0}$

$${\displaystyle H_{i}(X)\simeq H_{0}(N(\mathbb {U} );{\hat {F}}_{i})\oplus H_{1}(N(\mathbb {U} );{\hat {F}}_{i-1}).}$$

Три успешных применения MAPPER можно найти в Carlsson et al. ^[32] Комментарий Дж. Карри к приложениям в этой статье состоит в том, что «общая черта, представляющая интерес в приложениях, - это наличие бликов или усиков». ^[33]

Бесплатная реализация MAPPER доступна в Интернете, написанная Даниэлем Мюлнером и Аравиндакшаном Бабу. MAPPER также составляет основу платформы AI Ayasdi .

Многомерная настойчивость [ править ]

Для TDA важна многомерная настойчивость. Эта концепция возникает как в теории, так и на практике. Первое исследование многомерной устойчивости было проведено на ранней стадии разработки TDA ^[34] и является одной из основополагающих документов TDA. ^[9] Первое приложение, появившееся в литературе, - это метод сравнения форм, аналогичный изобретению TDA. ^[35]

Определение п - мерного модуля сохранения состояния в это ^[33]${\displaystyle \mathbb {R} ^{n}}$

• векторное пространство назначается каждой точке в${\displaystyle V_{s}}$${\displaystyle s=(s_{1},...,s_{n})}$
• карта присваивается, если (${\displaystyle \rho _{s}^{t}:V_{s}\to V_{t}}$${\displaystyle s\leq t}$${\displaystyle s_{i}\leq t_{i},i=1,...,n)}$
• карты удовлетворяют для всех${\displaystyle \rho _{r}^{t}=\rho _{s}^{t}\circ \rho _{r}^{s}}$${\displaystyle r\leq s\leq t}$

Возможно, стоит отметить, что существуют разногласия по поводу определения многомерной устойчивости. ^[33]

Одним из преимуществ одномерного постоянства является его представление в виде диаграммы или штрих-кода. Однако дискретных полных инвариантов многомерных модулей персистентности не существует. ^[36] Основная причина этого заключается в том, что структура набора неразложимых чрезвычайно усложняется теоремой Габриэля в теории колчановых представлений ^[37], хотя конечно n-мерный модуль сохранения может быть однозначно разложен в прямую сумму неразложимы по теореме Крулля-Шмидта. ^[38]

Тем не менее, многие результаты были получены. Карлссон и Зомородиан ввели ранговый инвариант , определенный как , в котором есть конечно порожденный n-градуированный модуль. В одном измерении он эквивалентен штрих-коду. В литературе ранговый инвариант часто называют постоянными числами Бетти (PBN). ^[17] Во многих теоретических работах авторы использовали более ограниченное определение, аналог персистентности подуровневого множества. В частности, сохранение числа Бетти функции задаются с помощью функции , принимая каждый к , где и .${\displaystyle \rho _{M}(u,v)}$${\displaystyle \rho _{M}(u,v)=\mathrm {rank} (x^{u-v}:M_{u}\to M_{v})}$${\displaystyle M}$${\displaystyle f:X\to \mathrm {R} ^{k}}$${\displaystyle \beta _{f}:\Delta ^{+}\to \mathrm {N} }$${\displaystyle (u,v)\in \Delta ^{+}}$${\displaystyle \beta _{f}(u,v):=\mathrm {rank} (H(X(f\leq u)\to H(X(f\leq v)))}$${\displaystyle \Delta ^{+}:=\{(u,v)\in \mathbb {R} \times \mathbb {R} :u\leq v\}}$${\displaystyle X(f\leq u):=\{x\in X:f(x)\leq u\}}$

Некоторые основные свойства включают монотонность и диагональный скачок. ^[39] Стойкие числа Бетти будут конечными, если является компактным и локально стягиваемым подпространством . ^[40]${\displaystyle X}$${\displaystyle \mathbb {R} ^{n}}$

Используя метод слоения, k-тусклые PBN можно разложить на семейство одномерных PBN с помощью вывода размерности. ^[41] Этот метод также привел к доказательству устойчивости многомерных PBN. ^[42] Разрывы PBN возникают только в точках, где либо является точкой разрыва, либо точкой разрыва в предположении, что и является компактным триангулируемым топологическим пространством. ^[43]${\displaystyle (u,v)(u\leq v)}$${\displaystyle u}$${\displaystyle \rho _{M}(\star ,v)}$${\displaystyle v}$${\displaystyle \rho (u,\star )}$${\displaystyle f\in C^{0}(X,\mathrm {R} ^{k})}$${\displaystyle X}$

Постоянное пространство, обобщение устойчивой диаграммы, определяется как мультимножество всех точек с кратностью больше 0 и диагональю. ^[44] Он обеспечивает стабильное и полное представление PBN. Текущая работа Carlsson et al. пытается дать геометрическую интерпретацию устойчивой гомологии, которая может дать представление о том, как объединить теорию машинного обучения с топологическим анализом данных. ^[45]

Первый практический алгоритм вычисления многомерной персистентности был изобретен очень рано. ^[46] После этого было предложено множество других алгоритмов, основанных на таких концепциях, как дискретная теория Морса ^[47] и оценка по конечной выборке. ^[48]

Прочие настойчивости [ править ]

Стандартная парадигма в TDA часто называется настойчивостью на подуровне . Помимо многомерной персистентности, было сделано много работ, чтобы расширить этот частный случай.

Зигзагообразное упорство [ править ]

Ненулевые отображения в модуле сохраняемости ограничиваются отношением предварительного порядка в категории. Однако математики пришли к выводу, что единодушие направления не является существенным для многих результатов. «Философский момент состоит в том, что теория декомпозиции представлений графов в некоторой степени не зависит от ориентации ребер графа». ^[49] Настойчивость зигзага важна с теоретической стороны. Все примеры, приведенные в обзорной статье Карлссона, чтобы проиллюстрировать важность функциональности, имеют некоторые общие черты. ^[3]

Расширенная настойчивость и настойчивость уровней [ править ]

Некоторые попытки - это потерять более строгое ограничение функции. ^[50] Дополнительную информацию см. В разделах « Категоризация, связки и влияние на математику» .

Естественно распространить гомологию персистентности на другие базовые понятия алгебраической топологии, такие как когомологии и относительные гомологии / когомологии. ^[51] Интересным приложением является вычисление круговых координат для набора данных через первую постоянную группу когомологий. ^[52]

Круговая настойчивость [ править ]

Гомология нормальной персистентности изучает функции с действительными значениями. Кругозначная карта может быть полезной, «теория постоянства для кругозначных карт обещает сыграть роль для некоторых векторных полей, как и стандартная теория стойкости для скалярных полей», как прокомментировали D. Burghelea et al. ^[53] Основное отличие состоит в том, что жордановы клетки (очень похожие по формату на жордановы блоки в линейной алгебре) нетривиальны для кругозначных функций, которые были бы равны нулю в вещественном случае, а комбинация со штрих-кодами дает инварианты ручная карта в умеренных условиях. ^[53]

Они используют два метода: теория Морса-Новикова ^[54] и теория представлений графов. ^[55] Более свежие результаты можно найти у D. Burghelea et al. ^[56] Например, требование приручения может быть заменено более слабым условием - непрерывным.

Стойкость при кручении [ править ]

Доказательство структурной теоремы основывается на том, что базовая область является полем, поэтому было сделано не так много попыток гомологии персистентности с кручением. Фрозини определил псевдометрию на этом конкретном модуле и доказал ее устойчивость. ^[57] Одно из новшеств в том, что определение метрики не зависит от какой-либо теории классификации. ^[58]

Категоризация и связки [ править ]

Одним из преимуществ теории категорий является ее способность поднимать конкретные результаты на более высокий уровень, показывая отношения между кажущимися несвязанными объектами. Бубеник и др. ^[59] предлагает краткое введение в теорию категорий, подходящую для TDA.

Теория категорий - это язык современной алгебры, который широко используется при изучении алгебраической геометрии и топологии. Было отмечено, что «ключевое наблюдение ^[9] состоит в том, что диаграмма устойчивости, созданная в ^[7], зависит только от алгебраической структуры, которую несет эта диаграмма». ^[60] Использование теории категорий в TDA оказалось плодотворным. ^{[59] [60]}

После обозначения , сделанное в Bubenik и др., ^[60] категория индексации является любым предупорядоченным множеством (не обязательно или ), целевая категорией является любой категорией (вместо обычно используется ), и функторы называются обобщены устойчивостью модулей в , над .${\textstyle P}$${\displaystyle \mathbb {N} }$${\displaystyle \mathbb {R} }$${\displaystyle D}$${\textstyle \mathrm {Vect} _{\mathbb {F} }}$ ${\textstyle P\to D}$${\displaystyle D}$${\textstyle P}$

Одним из преимуществ использования теории категорий в TDA является более четкое понимание концепций и открытие новых отношений между доказательствами. Для иллюстрации возьмем два примера. Понимание соответствия между перемежением и сопоставлением имеет огромное значение, поскольку сопоставление было методом, используемым вначале (измененным из теории Морса). Краткое изложение работ можно найти в Vin de Silva et al. ^[61] Многие теоремы гораздо легче доказать в более интуитивной обстановке. ^[58] Другой пример - взаимосвязь между построением различных комплексов из облаков точек. Давно замечено родство комплексов Чеха и Виеториса-Рипса. В частности, . ^[62]${\displaystyle V_{r}(X)\subset C_{{\sqrt {2}}r}(X)\subset V_{2r}(X)}$Существенную взаимосвязь между комплексами Чеха и Рипса можно гораздо яснее увидеть на категориальном языке. ^[61]

Язык теории категорий также помогает формулировать результаты в терминах, понятных более широкому математическому сообществу. Расстояние до узкого места широко используется в TDA из-за результатов стабильности по отношению к расстоянию до узкого места. ^{[11] [14]} Фактически, расстояние перемежения - это конечный объект в ч.у. категории стабильных метрик на многомерных модулях персистентности в простом поле . ^{[58] [63]}

Пучки , центральное понятие в современной алгебраической геометрии , неразрывно связаны с теорией категорий. Грубо говоря, связки - это математический инструмент для понимания того, как локальная информация определяет глобальную информацию. Джастин Карри рассматривает постоянство набора уровней как исследование волокон непрерывных функций. Объекты, которые он изучает, очень похожи на объекты MAPPER, но с теорией пучков в качестве теоретической основы. ^[33] Хотя в теории пучков еще не было прорыва в теории TDA, это многообещающе, поскольку в алгебраической геометрии есть много красивых теорем, относящихся к теории пучков. Например, естественный теоретический вопрос заключается в том, приводят ли разные методы фильтрации к одному и тому же результату.^[64]

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

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

данные

${\displaystyle {\stackrel {F}{\longrightarrow }}}$

модуль топологического сохранения

${\displaystyle {\stackrel {H}{\longrightarrow }}}$

модуль алгебраической персистентности

${\displaystyle {\stackrel {J}{\longrightarrow }}}$

дискретный инвариант

Теорема о мягкой устойчивости утверждает, что это липшицево , а теорема о жесткой устойчивости утверждает, что это липшицево.${\displaystyle HF}$${\displaystyle J}$

Расстояние узкого места широко используется в TDA. Теорема изометрии утверждает, что расстояние чередования равно расстоянию до узкого места. ^[58] Бубеник и др. абстрагировали определение до определения между функторами, когда оно оснащено сублинейной проекцией, или надлинейным семейством, в котором все еще остается псевдометрическим. ^[60] Рассматривая великолепные символы расстояния перемежения, ^[65] здесь мы вводим общее определение расстояния перемежения (вместо первого введенного): ^[11] Пусть (функция от до, которая является монотонной и удовлетворяет всем ). А${\displaystyle d_{I}}$${\displaystyle F,G:P\to D}$${\textstyle P}$${\displaystyle \Gamma ,K\in \mathrm {Trans_{P}} }$${\textstyle P}$${\textstyle P}$${\displaystyle x\leq \Gamma (x)}$${\textstyle x\in P}$${\displaystyle (\Gamma ,K)}$-перемежение между F и G состоит из естественных преобразований и , таких что и .${\displaystyle \varphi :F\Rightarrow G\Gamma }$${\displaystyle \psi :G\Rightarrow FK}$${\displaystyle (\psi \Gamma )=\varphi F\eta _{K\Gamma }}$${\displaystyle (\varphi \Gamma )=\psi G\eta _{\Gamma K}}$

Два основных результата: ^[60]

• Позвольте быть предварительно упорядоченным набором с сублинейной проекцией или суперлинейным семейством. Позвольте быть функтором между произвольными категориями . Тогда для любых двух функторов имеем .${\textstyle P}$${\textstyle H:D\to E}$${\textstyle D,E}$${\textstyle F,G:P\to D}$${\textstyle d_{I}(HF,HG)\leq d_{I}(F,G)}$
• Позвольте быть ч.у. метрического пространства , быть топологическим пространством. И пусть (не обязательно непрерывными) будут функции, и будет соответствующая диаграмма устойчивости. Тогда .${\textstyle P}$${\textstyle Y}$${\textstyle X}$${\textstyle f,g:X\to Y}$${\textstyle F,G}$${\displaystyle d_{I}(F,G)\leq d_{\infty }(f,g):=\sup _{x\in X}d_{Y}(f(x),g(x))}$

Эти два результата суммируют многие результаты по стабильности различных моделей персистентности.

Для получения информации о теореме устойчивости многомерной персистентности обратитесь к подразделу о настойчивости.

Структурная теорема [ править ]

Структурная теорема имеет центральное значение для TDA; как прокомментировал Дж. Карлссон, «то, что делает гомологии полезными в качестве дискриминатора между топологическими пространствами, - это факт наличия классификационной теоремы для конечно порожденных абелевых групп». ^[3] (см. Основную теорему о конечно порожденных абелевых группах ).

Основным аргументом, используемым при доказательстве исходной структурной теоремы, является стандартная структурная теорема для конечно порожденных модулей над областью главных идеалов . ^[9] Однако этот аргумент не работает, если установлен индексный набор . ^[3]${\displaystyle (\mathbb {R} ,\leq )}$

В общем, не каждый модуль сохраняемости можно разложить на интервалы. ^[66] Было сделано много попыток ослабить ограничения исходной структурной теоремы. ^{[ требуется пояснение ]} Случай для поточечных конечномерных модулей персистентности, индексированных локально конечным подмножеством, решен на основе работы Уэбба. ^[67] Наиболее заметный результат получен Кроули-Бови, который решил случай . Теорема Кроули-Бови утверждает, что любой поточечно конечномерный модуль персистентности является прямой суммой интервальных модулей. ^[68]${\displaystyle \mathbb {R} }$${\displaystyle \mathbb {R} }$

Чтобы понять определение его теоремы, необходимо ввести некоторые понятия. Интервал в определяется как подмножество , обладающего свойством , что если и , если есть такие , что , то , как хорошо. Модуль интервалов назначает каждому элементу векторное пространство и присваивает нулевое векторное пространство элементам в нем . Все карты являются нулевыми, если только и , в этом случае, не являются тождественными. ^[33] Интервальные модули неразложимы. ^[69]${\displaystyle (\mathbb {R} ,\leq )}$${\displaystyle I\subset \mathbb {R} }$${\displaystyle r,t\in I}$${\displaystyle s\in \mathbb {R} }$${\displaystyle r\leq s\leq t}$${\displaystyle s\in I}$ ${\displaystyle k_{I}}$${\displaystyle s\in I}$${\displaystyle k}$${\displaystyle \mathbb {R} \setminus I}$${\displaystyle \rho _{s}^{t}}$${\displaystyle s,t\in I}$${\displaystyle s\leq t}$${\displaystyle \rho _{s}^{t}}$

Хотя результат Кроули-Бови является очень сильной теоремой, он все же не распространяется на случай q-tame. ^[66] Модуль персистентности q-ручной, если ранг модуля конечен для всех . Есть примеры q-ручных модулей персистентности, которые не могут быть поточечно конечными. ^[70] Однако оказывается, что аналогичная структурная теорема все еще остается в силе, если признаки, существующие только для одного значения индекса, удалены. ^[69] Это верно, потому что бесконечномерные части при каждом значении индекса не сохраняются из-за условия конечного ранга. ^[71] Формально наблюдаемая категория определяется как , в котором обозначает полную подкатегорию${\displaystyle \rho _{s}^{t}}$${\displaystyle s<t}$${\displaystyle \mathrm {Ob} }$${\displaystyle \mathrm {Pers} /\mathrm {Eph} }$${\displaystyle \mathrm {Eph} }$${\displaystyle \mathrm {Pers} }$чьи объекты являются эфемерными модулями ( когда бы то ни было ). ^[69]${\displaystyle \rho _{s}^{t}=0}$${\displaystyle s<t}$

Обратите внимание, что расширенные результаты, перечисленные здесь, не применимы к зигзагообразной персистентности, поскольку аналог модуля зигзагообразной стойкости не сразу очевиден.${\displaystyle \mathbb {R} }$

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

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

Один из способов применения статистики к анализу топологических данных - изучение статистических свойств топологических характеристик облаков точек. Изучение случайных симплициальных комплексов дает некоторое представление о статистической топологии. K. Turner et al. ^[72] предлагает резюме работы в этом ключе.

Второй способ - изучить распределения вероятностей в постоянном пространстве. Пространство сохранения есть , где - пространство всех штрих-кодов, содержащих ровно интервалы, а эквивалентности - если . ^[73] Это пространство довольно сложно; например, он не является полным по метрике «узкое место». Первая попытка его изучения сделана Ю. Милейко и соавт. ^[74] Пространство диаграмм устойчивости в их статье определяется как${\displaystyle B_{\infty }}$${\displaystyle \coprod _{n}B_{n}/{\backsim }}$${\displaystyle B_{n}}$${\displaystyle n}$${\displaystyle \{[x_{1},y_{1}],[x_{2},y_{2}],\ldots ,[x_{n},y_{n}]\}\backsim \{[x_{1},y_{1}],[x_{2},y_{2}],\ldots ,[x_{n-1},y_{n-1}]\}}$${\displaystyle x_{n}=y_{n}}$${\displaystyle D_{p}}$

$${\displaystyle D_{p}:=\left\{d\mid \sum _{x\in d}\left(2\inf _{y\in \Delta }\lVert x-y\rVert \right)^{p}<\infty \right\}}$$

${\displaystyle \Delta }$

${\displaystyle \mathbb {R} ^{2}}$

${\displaystyle D_{p}}$

${\displaystyle W_{p}(u,v)=\left(\inf _{\gamma \in \Gamma (u,v)}\int _{\mathbb {X} \times \mathbb {X} }\rho ^{p}(x,y)\,\mathrm {d} \gamma (x,y)\right)^{1/p}}$

Третий способ - это непосредственно рассматривать когомологии вероятностного пространства или статистических систем, которые называются информационными структурами и в основном состоят из тройки ( ), пространства выборки, случайных величин и вероятностных законов. ^{[78] [79]} Случайные величины рассматриваются как разбиения n атомных вероятностей (рассматриваемых как вероятностный (n-1) -симплекс ) на решетке разбиений (${\displaystyle \Omega ,\Pi ,P}$${\displaystyle |\Omega |=n}$${\displaystyle \Pi _{n}}$). Случайные величины или модули измеримых функций обеспечивают коцепные комплексы, в то время как кограница рассматривается как общая гомологическая алгебра, впервые обнаруженная Хохшильдом с левым действием, реализующим действие обусловливания. Первое условие коцикла соответствует цепному правилу энтропии, позволяющему однозначно с точностью до мультипликативной константы получить энтропию Шеннона как первый класс когомологий. Рассмотрение деформированного левого действия обобщает структуру энтропии Тсаллиса. Информационные когомологии - это пример окольцованных топосов. Многомерный k - Взаимная информация появляется в выражениях кограниц, и их обращение в нуль, связанное с условием коцикла, дает эквивалентные условия для статистической независимости. ^[80]Минимумы взаимной информации, также называемые синергизмом, порождают интересные конфигурации независимости, аналогичные гомотопическим связям. Из-за его комбинаторной сложности на данных был исследован только симплициальный подслучай когомологий и информационной структуры. Применительно к данным эти когомологические инструменты количественно определяют статистические зависимости и независимость, включая цепи Маркова и условную независимость , в многомерном случае. ^[81] Примечательно, что взаимная информация обобщает коэффициент корреляции и ковариациюнелинейным статистическим зависимостям. Эти подходы были разработаны независимо и лишь косвенно связаны с методами персистентности, но могут быть примерно поняты в симплициальном случае с помощью теоремы Ху Куо Тина, которая устанавливает взаимно однозначное соответствие между функциями взаимной информации и конечной измеримой функцией множества с оператором пересечения. , чтобы построить сложный каркас Чеха . Информационная когомология предлагает некоторую прямую интерпретацию и применение с точки зрения нейробиологии (теория нейронной сборки и качественное познание ^[82] ), статистической физики и глубокой нейронной сети, для которых структура и алгоритм обучения определяются комплексом случайных величин и информационной цепочкой. правило. ^[83]

Пейзажи персистентности, представленные Питером Бубеником, представляют собой другой способ представления штрих-кодов, более поддающийся статистическому анализу. ^[84] сохранение ландшафта из стойкого модуля определяется как функция , , где обозначает расширенную реальную линию и . Пространство ландшафтов персистентности очень хорошее: оно наследует все хорошие свойства представления штрих-кода (стабильность, простота представления и т. Д.), Но статистические величины могут быть легко определены, и некоторые проблемы в работе Ю. Милейко и др., Такие как как неединственность ожиданий, ^[74] можно преодолеть. Доступны эффективные алгоритмы вычислений с персистентными ландшафтами. ^[85]${\displaystyle M}$${\displaystyle \lambda :\mathbb {N} \times \mathbb {R} \to {\bar {\mathbb {R} }}}$${\displaystyle \lambda (k,t):=\sup(m\geq 0\mid \beta ^{t-m,t-m}\geq k)}$${\displaystyle {\bar {\mathbb {R} }}}$${\displaystyle \beta ^{a,b}=\mathrm {dim} (\mathrm {im} (M(a\leq b)))}$Другой подход заключается в использовании измененной персистентности, то есть сохраняемости образа, ядра и коядра. ^[86]

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

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

Существует несколько способов классификации приложений TDA. Пожалуй, самый естественный способ - по полю. Очень неполный список успешных приложений включает ^[87] скелетирование данных, ^[88] изучение формы, ^[89] реконструкцию графа, ^{[90] [91] [92] [93] [94]} анализ изображений, ^{[95] [96]} материал, ^[97] анализ развития болезни, ^{[98] [99]} сенсорная сеть, ^[62] анализ сигналов, ^[100] космическая паутина, ^[101] сложная сеть, ^{[102] [103] [104] [105]}фрактальная геометрия, ^[106] вирусная эволюция, ^[107] распространение инфекций в сетях, ^[108] классификация бактерий с использованием молекулярной спектроскопии, ^[109] гиперспектральная визуализация в физической химии ^[110] и дистанционное зондирование. ^[111]

Другой способ - выделить методы Дж. Карлссона ^[73]

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

Характеристики ТДА в приложениях [ править ]

В последних приложениях TDA есть несколько примечательных интересных особенностей:

1. Объединение инструментов из нескольких разделов математики . Помимо очевидной потребности в алгебре и топологии, в TDA нашли применение уравнения в частных производных, ^[112] алгебраическая геометрия, ^[36] теория представлений, ^[49] статистика, комбинаторика и риманова геометрия ^[71] .
2. Количественный анализ . Топология считается очень мягкой, поскольку многие понятия инвариантны относительно гомотопии. Тем не менее, постоянная топология способна регистрировать рождение (появление) и смерть (исчезновение) топологических объектов, поэтому в нее встраивается дополнительная геометрическая информация. Одним из теоретических доказательств является частично положительный результат об уникальности восстановления кривых; ^[113] два из них касаются количественного анализа стабильности фуллерена и количественного анализа самоподобия отдельно. ^{[106] [114]}
3. Роль непродолжительной настойчивости . Кратковременная настойчивость также оказалась полезной, несмотря на распространенное мнение, что причиной этого явления является шум. ^[115] Это интересно с математической теорией.

Одна из основных областей анализа данных сегодня - машинное обучение . Некоторые примеры машинного обучения в TDA можно найти в Adcock et al. ^[116] конференция посвящена связи между TDA и машинного обучения. Чтобы применить инструменты машинного обучения, информация, полученная из TDA, должна быть представлена ​​в векторной форме. Постоянная и многообещающая попытка - это описанный выше ландшафт настойчивости. Другая попытка использует концепцию постоянства изображений. ^[117] Однако одной из проблем этого метода является потеря устойчивости, поскольку теорема о жесткой устойчивости зависит от представления штрих-кода.

Влияние на математику [ править ]

Топологический анализ данных и стойкая гомология оказали влияние на теорию Морса . Теория Морса сыграла очень важную роль в теории ТДА, в том числе в области вычислений. Некоторые работы в области устойчивых гомологий расширили результаты о функциях Морса для приручения функций или даже для непрерывных функций. Забытый результат Р. Деёвеля задолго до изобретения стойких гомологий распространяет теорию Морса на все непрерывные функции. ^[118]

Один из недавних результатов состоит в том, что категория графов Риба эквивалентна определенному классу пучков. ^[119] Это мотивировано теоретической работой в TDA, поскольку граф Риба связан с теорией Морса, а MAPPER является производным от нее. Доказательство этой теоремы опирается на расстояние перемежения.

Стойкая гомология тесно связана со спектральными последовательностями . ^{[120] [121]} В частности, алгоритм, приводящий отфильтрованный комплекс к его канонической форме ^[10], позволяет гораздо быстрее вычислять спектральные последовательности, чем стандартная процедура вычисления групп постранично. Сохранение зигзага может иметь теоретическое значение для спектральных последовательностей.${\displaystyle E_{p,q}^{r}}$

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

• Снижение размерности
• Сбор данных
• Компьютерное зрение
• Вычислительная топология
• Дискретная теория Морса
• Анализ формы (цифровая геометрия)
• Теория размеров
• Алгебраическая топология

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