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

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

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

Основная теория

Интуиция

TDA основан на идее, что форма наборов данных содержит соответствующую информацию. Реальные многомерные данные обычно разрежены и имеют тенденцию иметь соответствующие низкоразмерные функции. Одна из задач ТДА — дать точную характеристику этого факта. Например, траектория простой системы хищник-жертва, описываемая уравнениями Лотки – Вольтерра образует замкнутый круг в пространстве состояний. TDA предоставляет инструменты для обнаружения и количественной оценки такого повторяющегося движения.

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

Ранняя история

Предшественники полной концепции стойкой гомологии появлялись постепенно с течением времени. В 1990 году Патрицио Фрозини ввел псевдорасстояние между подмногообразиями, а затем и функцию размера, которая на 1-мерных кривых эквивалентна 0-й постоянной гомологии. Почти десять лет спустя Ванесса Робинс изучила образы гомоморфизмов, вызванных включением. Наконец, вскоре после этого Эдельсбруннер и др. представил концепцию устойчивой гомологии вместе с эффективным алгоритмом и его визуализацией в виде диаграммы постоянства. Карлссон и др. переформулировал первоначальное определение и предложил эквивалентный метод визуализации, называемый персистентными штрих-кодами . интерпретация персистентности на языке коммутативной алгебры.

В алгебраической топологии устойчивая гомология возникла благодаря работам Сергея Баранникова по теории Морса. Множество критических значений гладкой функции Морса было канонически разбито на пары «рождение-смерть», классифицированы фильтруемые комплексы, их инварианты, эквивалентные диаграмме инерционности и штрих-кодам инерционности, вместе с эффективным алгоритмом их расчета описаны под названием канонических форм в 1994 году Баранникова.

Концепции

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

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

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

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

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

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

между Расстояние Вассерштейна двумя диаграммами постоянства $X$ и $Y$ определяется как $$W_{p}[L_{q}](X,Y):=\inf _{\varphi :X\to Y}\left[\sum _{x\in X}(\Vert x-\varphi (x)\Vert _{q})^{p}\right]^{1/p}$$где $1\leq p,q\leq \infty$ и $\varphi$ пробегает по биекциям между $X$ и $Y$. Пожалуйста, обратитесь к рисунку 3.1 в книге Мунка. для иллюстрации.

Расстояние «узкого места» между $X$ и $Y$ является $$W_{\infty }[L_{q}](X,Y):=\inf _{\varphi :X\to Y}\sup _{x\in X}\Vert x-\varphi (x)\Vert _{q}.$$ Это частный случай расстояния Вассерштейна, позволяющий $p=\infty$.

Основное свойство

Структурная теорема

Первая теорема классификации стойких гомологии появилась в 1994 году. через канонические формы Баранникова. Классификационная теорема, интерпретирующая персистентность на языке коммутативной алгебры, появилась в 2005 году: для конечно сгенерированного модуля персистентности $C$ с полем $F$ коэффициенты, $$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).$$Интуитивно понятно, что свободные части соответствуют генераторам гомологии, возникающим на уровне фильтрации. $t_{i}$ и никогда не исчезают, а торсионные части соответствуют тем, которые появляются на уровне фильтрации. $r_{j}$ и продлится $s_{j}$ ступени фильтрации (или, что то же самое, исчезают на уровне фильтрации $s_{j}+r_{j}$).

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

Стабильность

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

Рабочий процесс

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

облако точек

$\to$

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

$\to$

модуль персистентности

$\to$

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

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

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

Обычное использование персистентности в TDA

Вычисление

Первый алгоритм по всем полям для постоянной гомологии в условиях алгебраической топологии был описан Баранниковым. путем приведения к каноническому виду верхнетреугольными матрицами. Алгоритм постоянной гомологии $F_{2}$ было дано Эдельсбруннером и др. Зомородян и Карлссон предложили практический алгоритм для вычисления устойчивой гомологии во всех полях. Книга Эдельсбруннера и Харера дает общие рекомендации по вычислительной топологии.

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

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

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

Визуализация

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

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

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

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

С математической точки зрения MAPPER — это разновидность графа Риба . Если ${\textstyle M(\mathbb {U} ,f)}$ не более чем одномерен, то для каждого $i\geq 0$, $$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. Комментарий Дж. Карри к приложениям в этой статье заключается в том, что «общей особенностью приложений, представляющих интерес, является наличие бликов или усиков».

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

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

Многомерная устойчивость важна для TDA. Это понятие возникает как в теории, так и на практике. Первое исследование многомерной персистентности было на ранней стадии разработки TDA. Карлссон-Зомородян представил теорию многомерной персистентности в и в сотрудничестве с Сингхом представил использование инструментов символической алгебры (методы базиса Гробнера) для вычисления модулей MPH. Их определение представляет многомерную устойчивость с n параметрами как $\mathbb {Z} ^{n}$ градуированный модуль над кольцом полиномов от n переменных. Инструменты коммутативной и гомологической алгебры применяются для изучения многомерной персистентности в работах Харрингтона-Оттера-Шенка-Тиллмана. Первое применение, появившееся в литературе, — это метод сравнения форм, аналогичный изобретению TDA.

Определение n -мерного модуля персистентности в $\mathbb {R} ^{n}$ является

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

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

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

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

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

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

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

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

Другие настойчивости

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

Зигзагообразная настойчивость

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

Расширенное сохранение и сохранение набора уровней

Есть некоторые попытки ослабить более строгое ограничение функции. Для получения дополнительной информации обратитесь к разделам «Категоризация и коспуки» и «Влияние на математику» .

Естественно распространить гомологию персистентности на другие основные понятия алгебраической топологии, такие как когомологии и относительные гомологии/когомологии. Интересным применением является вычисление круговых координат набора данных с помощью первой постоянной группы когомологий.

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

Нормальная гомология персистентности изучает вещественнозначные функции. Карта с круговыми значениями может быть полезна: «Теория персистентности для карт с круговыми значениями обещает сыграть роль для некоторых векторных полей, как и стандартная теория персистентности для скалярных полей», как прокомментировано Дэном Бургелеа и др. Основное отличие состоит в том, что жордановые ячейки (очень похожие по формату на жордановые блоки в линейной алгебре) нетривиальны в функциях с круговыми значениями, которые в вещественном случае были бы равны нулю, а в сочетании со штрих-кодами дают инварианты ручной карты, в умеренных условиях.

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

Стойкость с кручением

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

Категорификация и ко-пучки

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

Теория категорий — это язык современной алгебры, который широко используется при изучении алгебраической геометрии и топологии. Было отмечено, что «ключевое наблюдение заключается в том, что диаграмма персистентности, созданная зависит только от алгебраической структуры, которую несет эта диаграмма». Использование теории категорий в TDA оказалось плодотворным.

Следуя обозначениям, сделанным Бубеником и др., категория индексации ${\textstyle P}$ — это любой заранее упорядоченный набор (не обязательно $\mathbb {N}$ или $\mathbb {R}$), целевая категория $D$ любая категория (вместо обычно используемого ${\textstyle \mathrm {Vect} _{\mathbb {F} }}$) и функторы ${\textstyle P\to D}$ называются обобщенными модулями персистентности в $D$, над ${\textstyle P}$.

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

Язык теории категорий также помогает выражать результаты в терминах, понятных более широкому математическому сообществу. Расстояние «узкого места» широко используется в TDA из-за результатов по стабильности относительно расстояния «узкого места». Фактически, расстояние чередования является конечным объектом в категории ЧУМ стабильных метрик на многомерных модулях персистентности в простом поле .

Пучки , центральное понятие современной алгебраической геометрии , неразрывно связаны с теорией категорий. Грубо говоря, пучки — это математический инструмент для понимания того, как локальная информация определяет глобальную информацию. Джастин Карри рассматривает сохранение множества уровней как исследование слоев непрерывных функций. Объекты, которые он изучает, очень похожи на объекты МАППЕРА, но в качестве теоретической основы используется теория снопов. Хотя ни один прорыв в теории ТДА еще не связан с использованием теории пучков, это многообещающе, поскольку в алгебраической геометрии существует множество красивых теорем, связанных с теорией пучков. Например, естественный теоретический вопрос заключается в том, приводят ли разные методы фильтрации к одному и тому же результату.

Стабильность

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

данные

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

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

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

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

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

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

Теорема мягкой устойчивости утверждает, что $HF$ является липшицевым непрерывным , и жесткая теорема устойчивости утверждает, что $J$ является липшицевым непрерывным.

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

Двумя основными результатами являются

• Позволять ${\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}$ быть соответствующей диаграммой персистентности. Затем $d_{I}(F,G)\leq d_{\infty }(f,g):=\sup _{x\in X}d_{Y}(f(x),g(x))$.

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

Теорему устойчивости многомерного постоянства можно найти в подразделе постоянства.

Структурная теорема

Структурная теорема имеет центральное значение для ТДА; как прокомментировал Г. Карлссон, «что делает гомологии полезными в качестве дискриминатора между топологическими пространствами, так это тот факт, что существует классификационная теорема для конечно порожденных абелевых групп». (см. основную теорему о конечно порожденных абелевых группах ).

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

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

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

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

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

Статистика

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

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

Второй способ — изучить распределения вероятностей в пространстве персистентности. Пространство персистентности $B_{\infty }$ является $\coprod _{n}B_{n}/{\backsim }$, где $B_{n}$ пространство всех штрих-кодов, содержащее ровно $n$ интервалы и эквивалентности $\{[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}]\}$ если $x_{n}=y_{n}$. Это пространство довольно сложное; например, он не является полным по показателю узкого места. Первая попытка его изучения предпринята Ю. Милейко с соавт. Пространство диаграмм персистентности $D_{p}$ в их статье определяется как $$D_{p}:=\left\{d\mid \sum _{x\in d}\left(2\inf _{y\in \Delta }\lVert x-y\rVert \right)^{p}<\infty \right\}$$где $\Delta$ это диагональная линия в $\mathbb {R} ^{2}$. Хорошее свойство это то, что $D_{p}$ полно и отделимо в метрике Вассерштейна $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}$. Ожидание, дисперсия и условная вероятность могут быть определены в смысле Фреше . Это позволяет портировать многие статистические инструменты на TDA. Работает над проверкой значимости нулевой гипотезы , доверительные интервалы , и надежные оценки являются заметными шагами.

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

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

Приложения

Классификация приложений

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

Другой путь – выделить приемы Г. Карлссона,

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

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

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

1. Объединение средств из нескольких разделов математики . Помимо очевидной необходимости в алгебре и топологии, уравнениях в частных производных, алгебраическая геометрия, теория представлений, статистика, комбинаторика и риманова геометрия все нашли применение в TDA.
2. Количественный анализ . Топология считается очень мягкой, поскольку многие понятия инвариантны относительно гомотопии. Однако постоянная топология способна фиксировать рождение (появление) и смерть (исчезновение) топологических признаков, поэтому в нее заложена дополнительная геометрическая информация. Одним из теоретических доказательств является частично положительный результат однозначности восстановления кривых; два приложения посвящены количественному анализу стабильности фуллеренов и количественному анализу самоподобия отдельно .
3. Роль кратковременного упорства . Недолгое постоянство также оказалось полезным, несмотря на распространенное мнение, что причиной явлений является шум. Это представляет интерес для математической теории.

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

Влияние на математику

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

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

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

DONUT: база данных приложений TDA

База данных оригинального и нетеоретического использования топологии (DONUT) — это база данных научных статей, посвященных практическому применению анализа топологических данных в различных областях науки. Компания DONUT была основана в 2017 году Барбарой Джунти, Янисом Лазовскисом и Бастианом Риком. и по состоянию на октябрь 2023 г. содержит 447 статей. ПОНЧИК был упомянут в выпуске « Уведомлений Американского математического общества» за ноябрь 2023 года .

См. также

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

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

Краткое введение

• Лесник, Майкл (2013). «Изучение формы данных с помощью топологии» . Институт перспективных исследований.
• Исходный материал для топологического анализа данных Микаэля Вейдемо-Йоханссона.

Монография

• Удо, Стив Ю. (2015). Теория персистентности: от представлений Quiver к анализу данных . Американское математическое общество. ISBN  978-1-4704-2545-6 .

Учебники по топологии

• Хэтчер, Аллен (2002). Алгебраическая топология . Издательство Кембриджского университета. ISBN  0-521-79540-0 . Доступно для скачивания
• Эдельсбруннер, Герберт; Харер, Джон (2010). Вычислительная топология: Введение . Американское математическое общество. ISBN  9780821849255 .
• «Элементарная прикладная топология» , Роберт Грист.

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

• База данных оригинального и нетеоретического использования топологии (DONUT)

Видео Лекции

• Введение в устойчивую гомологию и топологию для анализа данных , Мэтью Райт
• Форма данных , Гуннар Карлссон

Другие ресурсы TDA

• Прикладная топология , Стэнфорд
• Сеть исследований прикладной алгебраической топологии. Архивировано 31 января 2016 г. в Wayback Machine Институтом математики и ее приложений.