Análise topológica de dados

Em matemática aplicada, a análise topológica de dados (TDA, na abreviatura do nome em inglês, topological data analysis) é uma abordagem para a análise de conjuntos de dados por meio de técnicas da topologia. A extração de informações de conjuntos de dados de dimensão alta, incompletos e com ruídos é um desafio. A TDA fornece uma estrutura geral para analisar esses dados de maneira insensível à métrica específica escolhida e fornece redução de dimensionalidade e robustez ao ruído. Além disso, ela herda funtorialidade, um conceito fundamental da matemática moderna, de sua natureza topológica, o que lhe permite adaptar-se às novas ferramentas matemáticas.

A motivação inicial é estudar a forma dos dados. A TDA combinou a topologia algébrica e outras ferramentas da matemática pura para permitir o estudo matematicamente rigoroso da "forma". A ferramenta principal é a homologia persistente, uma adaptação da homologia para dados de nuvem de pontos. A homologia persistente foi aplicada a muitos tipos de dados em muitas áreas. Além disso, sua base matemática também é de importância teórica. As características exclusivas da TDA fazem dela uma ponte promissora entre topologia e geometria.

Teoria básica

Intuição

A premissa subjacente à TDA é que a forma é importante. Dados reais em altas dimensões quase sempre são esparsos e tendem a ter características de baixa dimensão relevantes. Uma tarefa de TDA é fornecer uma caracterização precisa desse fato. Um exemplo ilustrativo é um sistema predador-presa simples, governado pelas equações de Lotka-Volterra. Pode-se observar facilmente que a trajetória do sistema forma um círculo fechado no espaço de estados. A TDA fornece ferramentas para detectar e quantificar esse movimento recorrente.

Muitos algoritmos para a análise de dados, incluindo aqueles usados na TDA, exigem a escolha de vários parâmetros. Sem conhecimento prévio do domínio, é difícil escolher a coleção correta de parâmetros para um conjunto de dados. A principal percepção da homologia persistente é que podemos usar as informações obtidas de todos os valores de um parâmetro. É claro que apenas essa percepção é fácil de fazer; a parte difícil é codificar essa enorme quantidade de informações em um formato compreensível e fácil de representar. Com a TDA, há uma interpretação matemática quando a informação é um grupo de homologia. Em geral, a suposição é que as características que persistem para uma ampla variedade de parâmetros são "verdadeiras" características. Presume-se que as características que persistem apenas para uma faixa estreita de parâmetros sejam ruídos, embora a justificativa teórica para isso não seja clara.

História antiga

Os precursores do conceito completo de homologia persistente apareceram gradualmente ao longo do tempo. Em 1990, Patrizio Frosini introduziu a função tamanho, que é equivalente à 0ª homologia persistente. Quase uma década depois, Vanessa Robins estudou as imagens de homomorfismos induzidos pela inclusão. Finalmente, logo em seguida, Edelsbrunner et al. introduziram o conceito de homologia persistente juntamente com um algoritmo eficiente e sua visualização como um diagrama de persistência. Carlsson et al. reformularam a definição inicial e deu um método de visualização equivalente chamado códigos de barras de persistência, interpretando a persistência na linguagem da álgebra comutativa.

Em topologia algébrica, a homologia persistente surgiu através do trabalho de Barannikov na teoria de Morse. O conjunto de valores críticos de função Morse suave foi particionado canonicamente em pares "nascimento-morte", complexos filtrados foram classificados e a visualização de seus invariantes, equivalente ao diagrama de persistência e códigos de barras de persistência, foi dada em 1994 pela forma canônica de Barannikov.

Conceitos

Alguns conceitos amplamente usados são apresentados a seguir. Observe que algumas definições podem variar de autor para autor.

Uma nuvem de pontos é frequentemente definida como um conjunto finito de pontos em algum espaço euclidiano, mas pode ser considerada qualquer espaço métrico finito.

O complexo de Čech de uma nuvem de pontos é o nervo da cobertura de bolas com um raio fixo em torno de cada ponto da nuvem.

Um módulo de persistência $\mathbb {U}$ indexado por $\mathbb {Z}$ consiste de um espaço vetorial $U_{t}$, para cada $t\in \mathbb {Z}$, e uma transformação linear $u_{t}^{s}:U_{s}\to U_{t}$ sempre que $s\leq t$, de tal modo que $u_{t}^{t}=1$ para todo $t$ e $u_{t}^{s}u_{s}^{r}=u_{t}^{r}$ sempre que $r\leq s\leq t.$ Uma definição equivalente é um funtor de $\mathbb {Z}$ considerado como um conjunto parcialmente ordenado para a categoria dos espaços vetoriais.

O grupo de homologia persistente $PH$ de uma nuvem de pontos é o módulo de persistência definido como $PH_{k}(X)=\prod H_{k}(X_{r})$, em que $X_{r}$ é o complexo de Čech de raio $r$ da nuvem de pontos $X$ e $H_{k}$ é o grupo de homologia.

Um código de barras de persistência é um multiconjunto de intervalos em $\mathbb {R}$ e um diagrama de persistência é um multiconjunto de pontos em $\Delta$ ( $:=\{(u,v)\in \mathbb {R} ^{2}\mid u,v\geq 0,u\leq v\}$ )

A distância de Wasserstein entre dois diagramas de persistência $X$ e $Y$ é definida como

$$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}$$

em que $1\leq p,q\leq \infty$ e $\varphi$ varia sobre as bijeções entre $X$ e $Y$ . Para uma ilustração, pode consultar a figura 3.1 em Munch. A distância de gargalo entre $X$ e $Y$ é

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

Este é um caso especial da distância de Wasserstein, obtido ao considerar $p=\infty$ .

Propriedade básica

Teorema da estrutura

O primeiro teorema de classificação para a homologia persistente apareceu em 1994 através das formas canônicas de Barannikov. O teorema da classificação que interpreta a persistência na linguagem da álgebra comutativa apareceu em 2005: para um módulo de persistência finitamente gerado $C$ com coeficientes em um corpo $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).$$

Intuitivamente, as partes livres correspondem aos geradores da homologia que aparecem no nível da filtração $t_{i}$ e nunca desaparecem, enquanto as partes de torção correspondem às que aparecem no nível da filtração $r_{j}$ e duram por $s_{j}$ etapas da filtração (ou equivalentemente, desaparecem no nível $s_{j}+r_{j}$ da filtração).

A homologia persistente é visualizada através de um código de barras ou diagrama de persistência. O código de barras originou-se na matemática abstrata. Especificamente, a categoria dos complexos filtrados finitos sobre um corpo é semissimples. Qualquer complexo filtrado é isomorfo à sua forma canônica, uma soma direta de complexos filtrados simples uni e bidimensionais.

Estabilidade

A estabilidade é desejável por fornecer robustez contra ruídos. Se $X$ é qualquer espaço homeomorfo a um complexo simplicial, e $f,g:X\to \mathbb {R}$ são funções tame contínuas, então os espaços vetoriais de persistência $\{H_{k}(f^{-1}([0,r]))\}$ e $\{H_{k}(g^{-1}([0,r]))\}$ são apresentados finitamente e $W_{\infty }(D(f),D(g))\leq \lVert f-g\rVert _{\infty }$, onde $W_{\infty }$ refere-se à distância de gargalo e $D$ é a aplicação que leva uma função tame contínua no diagrama de persistência de sua $k$-ésima homologia.

Fluxo de trabalho

O fluxo de trabalho básico na TDA é:

Nuvem de pontos

$\to$

complexos aninhados

$\to$

módulo de persistência

$\to$

código de barras ou diagrama

1. Se $X$ é uma nuvem de pontos, substitua $X$ por uma família aninhada de complexos simpliciais $X_{r}$ (como o complexo de Čech ou Vietoris-Rips). Esse processo converte a nuvem de pontos para uma filtragem de complexos simpliciais. Tomando-se a homologia de cada complexo nessa filtração obtém-se um módulo de persistência
   $$H_{i}(X_{r_{0}})\to H_{i}(X_{r_{1}})\to H_{i}(X_{r_{2}})\to \cdots$$
2. Aplique o teorema da estrutura para fornecer uma versão parametrizada do número de Betti, diagrama de persistência ou, equivalentemente, código de barras.

Graficamente,

Um uso comum de persistência na TDA

Cálculo

O primeiro algoritmo sobre todos os corpos para homologia persistente no contexto da topologia algébrica foi descrito por Barannikov através da redução à forma canônica por matrizes triangulares superiores. O primeiro algoritmo para homologia persistente sobre $F_{2}$ foi dado por Edelsbrunner et al. Zomorodian e Carlsson deram o primeiro algoritmo prático para calcular a homologia persistente em todos os corpos. O livro de Edelsbrunner e Harer fornece orientação geral sobre topologia computacional.

Uma questão que surge na computação é a escolha do complexo. O complexo de Čech e o complexo de Vietoris – Rips são mais naturais à primeira vista; no entanto, seu tamanho aumenta rapidamente com o número de pontos de dados. O complexo de Vietoris – Rips é preferível ao complexo de Čech porque sua definição é mais simples e o complexo de Čech requer um esforço extra para definir em um espaço métrico finito geral. Foram estudadas formas eficientes de reduzir o custo computacional da homologia. Por exemplo, o complexo α e o complexo testemunha são usados para reduzir a dimensão e o tamanho dos complexos.

Recentemente, a teoria de Morse discreta mostrou-se promissora para a homologia computacional, pois pode reduzir um complexo simplicial dado a um complexo celular muito menor que é homotópico ao original. Essa redução pode de fato ser realizada à medida em que o complexo é construído usando a teoria matroide, levando a maiores aumentos de desempenho. Outro algoritmo recente economiza tempo ignorando as classes de homologia com baixa persistência.

Há vários pacotes de software disponíveis, como por exemplo javaPlex, Dionysus, Perseus, PHAT, DIPHA, Gudhi, Ripser e TDAstats. Uma comparação entre essas ferramentas é feita por Otter et al. Giotto-tda é um pacote Python dedicado à integração de TDA no fluxo de trabalho de aprendizagem de máquina por meio de uma API scikit-learn. Um pacote R chamado TDA é capaz de calcular conceitos inventados recentemente, como paisagem e o estimador de distância do núcleo. O pacote Topology ToolKit é especializado em dados contínuos, definidos em variedades de baixa dimensão (1, 2 ou 3), como os que normalmente são encontrados em visualização científica. Outro pacote R, o TDAstats, implementa a biblioteca rápida C++ Ripser para calcular a homologia persistente. Ele também usa o onipresente pacote ggplot2 para gerar visualizações de homologia persistente reproduzíveis, personalizáveis e com qualidade de publicação, especificamente códigos de barras topológicos e diagramas de persistência. O código de exemplo abaixo mostra como a linguagem de programação R pode ser usada para calcular a homologia persistente.

# instalar pacote a partir do CRAN e carregar conjuntos de dados
install.packages("TDAstats")
library("TDAstats")
data("unif2d")
data("circle2d")

# calcular a homologia persistente para ambos os conjuntos de dados
unif.phom <- calculate_homology(unif2d)
circ.phom <- calculate_homology(circle2d)

# plotar nuvem de pontos distribuídos uniformemente como um diagrama de persistência
plot_persist(unif.phom)

# plotar nuvem circular de pontos como um código de barras
# nota-se uma única barra persistente, como seria de se esperar para uma circunferência (único 1-ciclo/laço)
plot_barcode(circ.phom)

Diagrama de persistência criado pelo código de exemplo (conjunto de dados unif.2d) para um conjunto de 100 pontos distribuídos uniformemente dentro de um quadrado bidimensional unitário. Nenhum dos 0-ciclos ou 1-ciclos é considerado um sinal verdadeiro (nenhum existe realmente dentro de uma nuvem de pontos quadrada unitária). Embora algumas características pareçam persistir, as marcas nos eixos mostram que a característica mais persistente persiste por menos de 0,20 unidades, o que é relativamente pequeno para uma nuvem de pontos em um quadrado unitário.

Código de barras topológico criado pelo código de exemplo (conjunto de dados circ.2d) para um conjunto de 100 pontos distribuídos uniformemente em torno da circunferência de um círculo. A única e longa característica unidimensional na parte superior do código de barras representa o único 1-ciclo presente em um círculo.

Visualização

É impossível visualizar diretamente dados de dimensão alta. Muitos métodos foram inventados para extrair uma estrutura de baixa dimensão do conjunto de dados, como análise de componentes principais e dimensionamento multidimensional. No entanto, é importante observar que o próprio problema é mal posto, pois muitas características topológicas diferentes podem ser encontradas no mesmo conjunto de dados. Assim, o estudo da visualização de espaços de alta dimensão é de importância central para a TDA, embora ele não envolva necessariamente o uso de homologia persistente. No entanto, houve tentativas recentes de usar homologia persistente na visualização de dados.

Carlsson et al. propuseram um método geral chamado MAPPER. Ele herda a ideia de Serre de que uma cobertura preserva a homotopia. Uma formulação generalizada de MAPPER é a seguinte:

Sejam $X$ e $Z$ espaços topológicos e $f:X\to Z$ uma função contínua. Seja $\mathbb {U} =\{U_{\alpha }\}_{\alpha \in A}$ uma cobertura aberta finita de $Z$. A saída do MAPPER é o nervo da cobertura pullback ${\textstyle M(\mathbb {U} ,f):=N(f^{-1}(\mathbb {U} ))}$, em que cada pré-imagem é dividida em suas componentes conexas. Este é um conceito muito geral, do qual o gráfico Reeb e as árvores de mesclagem são casos especiais.

Esta não é exatamente a definição original. Carlsson et al. tomaram $Z$ como $\mathbb {R}$ ou $\mathbb {R} ^{2}$ e o cobriram com conjuntos abertos, tais que no máximo dois se intersectassem. Essa restrição significa que a saída está na forma de uma rede complexa. Como a topologia de uma nuvem de pontos finitos é trivial, métodos de agrupamento (como ligação única) são usados para produzir o análogo de conjuntos conexos na pré-imagem $f^{-1}(U)$ quando se aplica MAPPER a dados reais.

Em termos matemáticos, o MAPPER é uma variação do gráfico de Reeb. Se o ${\textstyle M(\mathbb {U} ,f)}$ é no máximo unidimensional, então para cada $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}).$$

A flexibilidade adicional também tem desvantagens. Um problema é a instabilidade, na medida em que alguma mudança na escolha da cobertura pode levar a grandes mudanças na saída do algoritmo. Houve trabalho no sentido de superar esse problema.

Três aplicações bem-sucedidas do MAPPER podem ser encontradas em Carlsson et al. Um comentário de J. Curry sobre as aplicações neste artigo é que "uma característica de interesse comum em aplicações é a presença de flares ou tendrils".

Está disponível online uma implementação gratuita do MAPPER, escrita por Daniel Müllner e Aravindakshan Babu. O MAPPER também serve como base para a plataforma de IA da Ayasdi.

Persistência multidimensional

A persistência multidimensional é importante para a TDA. O conceito surge tanto na teoria quanto na prática. A primeira investigação da persistência multidimensional foi no início do desenvolvimento da TDA, e é um dos artigos fundadores da TDA. A primeira aplicação a aparecer na literatura é um método para comparação de formas, semelhante à invenção da TDA.

A definição de um módulo de persistência n- dimensional em $\mathbb {R} ^{n}$ é

• um espaço vetorial $V_{s}$ é associado a cada ponto em $s=(s_{1},...,s_{n})$
• uma aplicação $\rho _{s}^{t}:V_{s}\to V_{t}$ é associada se $s\leq t$ ( $s_{i}\leq t_{i},i=1,...,n)$
• as aplicações satisfazem $\rho _{r}^{t}=\rho _{s}^{t}\circ \rho _{r}^{s}$ para quaisquer $r\leq s\leq t$

Pode ser interessante notar que existem controvérsias sobre a definição de persistência multidimensional.

Uma das vantagens da persistência unidimensional é sua representabilidade por um diagrama ou código de barras. No entanto, não existem invariantes completos discretos de módulos de persistência multidimensionais. A principal razão para isso é que a estrutura da coleção de indecomponíveis é extremamente complicada pelo teorema de Gabriel na teoria das representações de quiver, embora um módulo de persistência finitamente n-dim possa ser decomposto unicamente em uma soma direta de indecomponíveis devido ao teorema de Krull-Schmidt.

No entanto, muitos resultados foram estabelecidos. Carlsson e Zomorodian introduziram o invariante de classificação $\rho _{M}(u,v)$, definido como o $\rho _{M}(u,v)=\mathrm {rank} (x^{u-v}:M_{u}\to M_{v})$, no qual $M$ é um módulo n-graduado finamente gerado. Em uma dimensão, é equivalente ao código de barras. Na literatura, o invariante de classificação é freqüentemente referido como os números de Betti persistentes (PBNs, na sigla em inglês). Em muitos trabalhos teóricos, os autores usaram uma definição mais restrita, um análogo da persistência de conjunto subnível. Especificamente, os números de Betti de persistência de uma função $f:X\to \mathrm {R} ^{k}$ são dados pela função $\beta _{f}:\Delta ^{+}\to \mathrm {N}$, que leva cada $(u,v)\in \Delta ^{+}$ em $\beta _{f}(u,v):=\mathrm {rank} (H(X(f\leq u)\to H(X(f\leq v)))$, em que $\Delta ^{+}:=\{(u,v)\in \mathbb {R} \times \mathbb {R} :u\leq v\}$ e $X(f\leq u):=\{x\in X:f(x)\leq u\}$ .

Entre as propriedades básicas estão a monotonicidade e o salto diagonal. Números de Betti persistentes serão finitos se $X$ é um subespaço compacto e localmente contrátil de $\mathbb {R} ^{n}$.

Usando um método de foliação, os PBNs k-dim podem ser decompostos em uma família de PBNs 1-dim por dedução de dimensionalidade. Este método também levou a uma prova de que os PBNs multi-dim são estáveis. As descontinuidades dos PBNs ocorrem apenas em pontos $(u,v)(u\leq v)$ em que ou $u$ é um ponto descontínuo de $\rho _{M}(\star ,v)$ ou $v$ é um ponto descontínuo de $\rho (u,\star )$ sob a suposição de que $f\in C^{0}(X,\mathrm {R} ^{k})$ e $X$ é um espaço topológico compacto e triangulável.

O espaço persistente, uma generalização do diagrama persistente, é definido como o multiconjunto de todos os pontos com multiplicidade maior que 0 e a diagonal. Ele fornece uma representação estável e completa dos PBNs. Em um trabalho em andamento, Carlsson et al. tentam dar uma interpretação geométrica da homologia persistente, o que pode fornecer insights sobre como combinar a teoria do aprendizado de máquina com a análise topológica de dados.

O primeiro algoritmo prático para calcular a persistência multidimensional foi inventado muito cedo. Posteriormente, muitos outros algoritmos foram propostos, baseados em conceitos como a teoria de Morse discreta e estimativa de amostras finitas.

Outras persistências

O paradigma padrão em TDA é frequentemente referido como persistência de subnível. Além da persistência multidimensional, muitos trabalhos foram feitos para estender este caso especial.

Persistência em zigue-zague

As aplicações não nulas no módulo de persistência são restritas pela relação de pré-ordem na categoria. No entanto, os matemáticos descobriram que a unanimidade de direção não é essencial para muitos resultados. “O ponto filosófico é que a teoria de decomposição das representações de grafos é um tanto independente da orientação das arestas dos grafos”. A persistência em zigue-zague é importante do ponto de vista teórico. Os exemplos dados no artigo de revisão de Carlsson para ilustrar a importância da funcionalidade, todos compartilham algumas de suas características.

Persistência estendida e persistência de conjuntos de nível

Algumas tentativas é perder a restrição mais estrita da função. Por favor, consulte as seções sobre categorização e cofeixes e impacto na matemática para mais informações.

É natural estender a homologia de persistência a outros conceitos básicos da topologia algébrica, como a coomologia e a homologia/coomologia relativa. Uma aplicação interessante é o cálculo de coordenadas circulares para um conjunto de dados por meio do primeiro grupo de coomologia persistente.

Persistência circular

A homologia de persistência normal estuda funções a valores reais. Funções a valores no círculo podem ser úteis, "a teoria da persistência para aplicações a valores no círculo promete desempenhar para alguns campos vetoriais o papel que a teoria de persistência padrão desempenha para campos escalares", como comentado em D. Burghelea et al. A principal diferença é que as células de Jordan (muito semelhantes em formato aos blocos de Jordan na álgebra linear) não são triviais em funções a valores no círculo, que seriam zero no caso a valores reais, e combinando com códigos de barras fornecem as invariantes de uma aplicação tame, sob condições moderadas.

Duas técnicas que eles usam são a teoria de Morse-Novikov e a teoria de representação de grafos. Resultados mais recentes podem ser encontrados em D. Burghelea et al. Por exemplo, o requisito de tame pode ser substituído por uma condição muito mais fraca, a continuidade.

Persistência com torção

A prova do teorema da estrutura depende do domínio de base ser corpo, portanto, não foram feitas muitas tentativas de homologia de persistência com torção. Frosini definiu uma pseudométrica neste módulo específico e comprovou sua estabilidade. Uma de suas novidades é não depender de uma teoria de classificação para definir a métrica.

Categorificação e cofeixes

Uma vantagem da teoria das categorias é a sua capacidade de elevar resultados concretos a um nível superior, mostrando relações entre objetos aparentemente desconectados. Bubenik et al. oferecem uma breve introdução da teoria das categorias ajustada para a TDA.

A teoria das categorias é a linguagem da álgebra moderna e tem sido amplamente utilizada no estudo da geometria algébrica e da topologia. Foi notado que "a observação chave de é que o diagrama de persistência produzido por depende apenas da estrutura algébrica carregada por este diagrama." O uso da teoria das categorias na TDA provou ser frutífero.

Seguindo as notações feitas em Bubenik et al., a categoria de indexação ${\textstyle P}$ é qualquer conjunto pré-ordenado (não necessariamente $\mathbb {N}$ ou $\mathbb {R}$), a categoria de destino $D$ é qualquer categoria (em vez do comumente usado ${\textstyle \mathrm {Vect} _{\mathbb {F} }}$ ), e funtores ${\textstyle P\to D}$ são chamados de módulos de persistência generalizados em $D$, sobre ${\textstyle P}$.

Uma vantagem de se usar a teoria das categorias na TDA é uma compreensão mais clara dos conceitos e a descoberta de novas relações entre as provas. Considere dois exemplos para ilustração. O entendimento da correspondência entre intercalação e correspondência é de grande importância, uma vez que a correspondência foi o método usado no início (modificado da teoria de Morse). Um resumo dos trabalhos pode ser encontrado em Vin de Silva et al. Muitos teoremas podem ser provados com muito mais facilidade em um ambiente mais intuitivo. Outro exemplo é a relação entre a construção de diferentes complexos a partir de nuvens de pontos. Há muito tempo foi notado que os complexos de Čech e de Vietoris-Rips estão relacionados. Especificamente, $V_{r}(X)\subset C_{{\sqrt {2}}r}(X)\subset V_{2r}(X)$. A relação essencial entre os complexos Cech e Rips pode ser vista muito mais claramente na linguagem categórica.

A linguagem da teoria das categorias também ajuda a expor os resultados em termos reconhecíveis pela comunidade matemática mais ampla. A distância de gargalo é amplamente usada na TDA por causa dos resultados sobre a estabilidade em relação à distância de gargalo. Na verdade, a distância de intercalação é o objeto terminal em uma categoria poset de métricas estáveis em módulos de persistência multidimensionais em um corpo primo.☃☃☃☃

Feixes, um conceito central em geometria algébrica moderna, estão intrinsecamente relacionados à teoria das categorias. Em linhas gerais, os feixes são a ferramenta matemática para entender como as informações locais determinam as informações globais. Justin Curry considera a persistência do conjunto de níveis como o estudo de fibras de funções contínuas. Os objetos que ele estuda são muito semelhantes aos do MAPPER, mas com a teoria dos feixes como fundamento teórico. Embora nenhuma grande descoberta na teoria de TDA tenha usado a teoria dos feixes, ela é promissora, uma vez que existem muitos teoremas em geometria algébrica relacionados à teoria dos feixes. Por exemplo, uma questão teórica natural é se diferentes métodos de filtragem resultam na mesma saída.

Estabilidade

A estabilidade é de importância central para a análise de dados, uma vez que dados reais têm ruídos. Com o uso da teoria das categorias, Bubenik et al. distinguiram entre teoremas de estabilidade soft e hard e provaram que os casos flexíveis são formais. Especificamente, o fluxo de trabalho geral da TDA é

dados

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

módulo de persistência topológica

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

módulo de persistência algébrica

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

invariante discreto

O teorema de estabilidade soft afirma que $HF$ é Lipschitz contínuo, e o teorema da estabilidade hard afirma que $J$ é Lipschitz contínuo.

A distância do gargalo é amplamente usada na TDA. O teorema de isometria afirma que a distância de intercalação $d_{I}$ é igual à distância do gargalo. Bubenik et al. abstrairam a definição àquela entre functores $F,G:P\to D$ quando ${\textstyle P}$ está equipado com uma projeção sublinear ou família superlinear, na qual ainda permanece uma pseudométrica. Considerando os caracteres magníficos da distância de intercalação, aqui é apresentada a definição geral de distância de intercalação (em vez da primeira introduzida): $\Gamma ,K\in \mathrm {Trans_{P}}$ (uma função de ${\textstyle P}$ para ${\textstyle P}$ que é monótona e satisfaz $x\leq \Gamma (x)$ para todo ${\textstyle x\in P}$ ) Uma $(\Gamma ,K)$-intercalação entre F e G consiste em transformações naturais $\varphi :F\Rightarrow G\Gamma$ e $\psi :G\Rightarrow FK$, tais que $(\psi \Gamma )=\varphi F\eta _{K\Gamma }$ e $(\varphi \Gamma )=\psi G\eta _{\Gamma K}$.

Os dois resultados principais são

• Seja ${\textstyle P}$ um conjunto pré-ordenado com uma projeção sublinear ou família superlinear. Seja ${\textstyle H:D\to E}$ um funtor entre categorias arbitrárias ${\textstyle D,E}$. Então, para quaisquer dois funtores ${\textstyle F,G:P\to D}$, tem-se ${\textstyle d_{I}(HF,HG)\leq d_{I}(F,G)}$.
• Seja ${\textstyle P}$ um conjunto parcialmente ordenado de um espaço métrico ${\textstyle Y}$, e seja ${\textstyle X}$ um espaço topológico. Sejam também ${\textstyle f,g:X\to Y}$ funções (não necessariamente contínuas), e ${\textstyle F,G}$ os diagramas de persistência correspondentes. Então $d_{I}(F,G)\leq d_{\infty }(f,g):=\sup _{x\in X}d_{Y}(f(x),g(x))$ .

Esses dois resultados resumem muitos resultados sobre a estabilidade de diferentes modelos de persistência.

Para o teorema de estabilidade da persistência multidimensional, consulte a subseção de persistência.

Teorema de estrutura

O teorema de estrutura é de importância central para a TDA; como comentado por G. Carlsson, "o que torna a homologia útil como discriminador entre espaços topológicos é o fato de que existe um teorema de classificação para grupos abelianos finitamente gerados". (veja o teorema fundamental dos grupos abelianos finitamente gerados).

O principal argumento usado na prova do teorema de estrutura original é o clássico teorema de estrutura para módulos finitamente gerados sobre um domínio de ideais principais. No entanto, este argumento falha se o conjunto de índices for $(\mathbb {R} ,\leq )$ .

Em geral, nem todo módulo de persistência pode ser decomposto em intervalos. Muitas tentativas foram feitas para relaxar as hipóteses do teorema de estrutura original. O caso dos módulos de persistência pontualmente de dimensão finita indexados por um subconjunto localmente finito de $\mathbb {R}$ é resolvido com base no trabalho de Webb. O resultado mais notável é feito por Crawley-Boevey, que resolveu o caso de $\mathbb {R}$. O teorema de Crawley-Boevey afirma que qualquer módulo de persistência pontualmente de dimensão finita é uma soma direta de módulos de intervalo.

Para entender o que diz o teorema, alguns conceitos precisam ser introduzidos. Um intervalo em $(\mathbb {R} ,\leq )$ é definido como um subconjunto $I\subset \mathbb {R}$ com a propriedade de que se $r,t\in I$ e se houver um $s\in \mathbb {R}$ de tal modo que $r\leq s\leq t$, então também é tem-se $s\in I$. Um módulo de intervalo $k_{I}$ atribui a cada elemento $s\in I$ o espaço vetorial $k$ e atribui o espaço vetorial nulo aos elementos de $\mathbb {R} \setminus I$. Todas as aplicações $\rho _{s}^{t}$ são nulas, a não ser que $s,t\in I$ e $s\leq t$, nesse caso $\rho _{s}^{t}$ é a aplicação identidade. Módulos de intervalo são indecomponíveis.

Embora o resultado de Crawley-Boevey seja um teorema muito poderoso, ele ainda não se estende ao caso q-tame. Um módulo de persistência é q-tame se o posto de ☃☃ é finito sempre que ☃☃. Existem exemplos de módulos de persistência q-tame não são pontualmente finitos. ☃ No entanto, verifica-se que um teorema de estrutura semelhante ainda é válido sforem removides a as características que existem apenas em um valor de índias. Isso é válido porque as partes de dimensão inifinita em cada valor de índice não persistem, devido à condição de posto finito. Formalmente, a categoria observável $\mathrm {Ob}$ é definida como $\mathrm {Pers} /\mathrm {Eph}$, em que $\mathrm {Eph}$ denota a subcategoria completa de $\mathrm {Pers}$ cujos objetos são os módulos efêmeros ($\rho _{s}^{t}=0$ sempre que $s<t$ )

Observe que os resultados estendidos listados aqui não se aplicam à persistência em ziguezague, uma vez que o análogo de um módulo de persistência em ziguezague sobre $\mathbb {R}$ não é imediatamente óbvio.

Estatísticas

Os dados reais são sempre finitos, consequentemente seu estudo exige que levemos em consideração a estocasticidade. A análise estatística nos dá a habilidade de separar características verdadeiras dos dados de artefatos introduzidos por ruído aleatório. Não há um mecanismo inerente à homologia persistente para distinguir entre características de baixa probabilidade e características de alta probabilidade.

Uma maneira de aplicar estatística à análise topológica de dados é estudar as propriedades estatísticas das características topológicas das nuvens de pontos. O estudo de complexos simpliciais aleatórios oferece alguns insights sobre a topologia estatística. K. Turner et al. oferecem um resumo dos trabalhos nessa linha.

Uma segunda maneira é estudar as distribuições de probabilidade no espaço de persistência. O espaço de persistência $B_{\infty }$ é $\coprod _{n}B_{n}/{\backsim }$, Onde $B_{n}$ é o espaço de todos os códigos de barras contendo exatamente $n$ intervalos e as equivalências são $\{[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}]\}$ se $x_{n}=y_{n}$. Este espaço é bastante complicado; por exemplo, ele não é completo na métrica de gargalo. A primeira tentativa de estudá-lo foi feita por Y. Mileyko et al. O espaço dos diagramas de persistência $D_{p}$ é definido em seu artigo como

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

em que $\Delta$ é a reta diagonal em $\mathbb {R} ^{2}$. Uma boa propriedade é que $D_{p}$ é completo e separável na métrica de Wasserstein$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}$ . A esperança, a variância e a probabilidade condicional podem ser definidas no sentido de Fréchet. Isso permite que muitas ferramentas estatísticas sejam transferidas para a TDA. Trabalhos em teste de significância de hipótese nula, intervalos de confiança e estimativas robustas são etapas notáveis.

Uma terceira forma é considerar a coomologia do espaço probabilístico ou sistemas estatísticos diretamente, chamadas de estruturas de informação e consistindo basicamente nas triplas ( $\Omega ,\Pi ,P$ ), espaço amostral, variáveis aleatórias e leis de probabilidade. Variáveis aleatórias são consideradas como partições das n probabilidades atômicas (vistas como um (n-1)-simplex de probabilidade, $|\Omega |=n$ ) no reticulado de partições ($\Pi _{n}$). As variáveis aleatórias ou módulos de funções mensuráveis fornecem os complexos de cocadeia enquanto o cobordo é considerado como a álgebra homológica geral descoberta pela primeira vez por Hochschild com uma ação à esquerda implementando a ação de condicionamento. A primeira condição de cociclo corresponde à regra da cadeia de entropia, permitindo derivar unicamente a menos da constante multiplicativa, a entropia de Shannon como a primeira classe de coomologia. A consideração de uma ação deformada à esquerda generaliza o quadro para entropias de Tsallis. A coomologia da informação é um exemplo de topos anelados. k-informações mútuas multivariadas aparecem em expressões cobordos, e o seu desaparecimento, relacionado à condição de cociclo, fornece condições equivalentes para a independência estatística. Mínimos de informações mútuas, também chamados de sinergia, dão origem a configurações de independência interessantes análogas a links homotópicos. Devido à sua complexidade combinatória, apenas o subcaso simplicial da coomologia e da estrutura de informação foi investigado nos dados. Aplicadas a dados, essas ferramentas coomológicas quantificam dependências e independências estatísticas, incluindo cadeias de Markov e independência condicional, no caso multivariado. Notavelmente, as informações mútuas generalizam o coeficiente de correlação e a covariância para dependências estatísticas não lineares. Essas abordagens foram desenvolvidas de forma independente e apenas indiretamente relacionadas aos métodos de persistência, mas podem ser aproximadamente compreendidas no caso simplicial usando o Teorema de Hu Kuo Tin que estabelece correspondência um a um entre funções de informações mútuas e função mensurável finita de um conjunto com operador de interseção, para construir o esqueleto do complexo de Čech . A coomologia de informações oferece alguma interpretação e aplicação direta em termos de neurociência (teoria da montagem neural e cognição qualitativa), física estatística e rede neural profunda para a qual a estrutura e o algoritmo de aprendizagem são impostos pelo complexo de variáveis aleatórias e pela regra da cadeia de informações.

As paisagens de persistência, introduzidas por Peter Bubenik, são uma forma diferente de representar códigos de barras, mais passíveis de análise estatística. A paisagem de persistência de um módulo persistente $M$ é definida como uma função $\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)$, Onde ${\bar {\mathbb {R} }}$ denota a reta real estendida e $\beta ^{a,b}=\mathrm {dim} (\mathrm {im} (M(a\leq b)))$. O espaço de paisagens de persistência é muito bom: ele herda todas as boas propriedades de representação de código de barras (estabilidade, fácil representação, etc.), mas as quantidades estatísticas podem ser prontamente definidas, e alguns problemas no trabalho de Y. Mileyko et al., como a não unicidade das expectativas, podem ser superados. Estão disponíveis algoritmos eficazes para computação com paisagens de persistência. Outra abordagem é usar a persistência revisada, que é a persistência de imagem, núcleo e conúcleo.

Aplicações

Classificação das aplicações

Existe mais de uma maneira de classificar as aplicações da TDA. Talvez a forma mais natural seja pela área. Uma lista muito incompleta de aplicações bem-sucedidas inclui esqueletização de dados, estudo da forma, reconstrução de gráfico, análise de imagem, material, análise de progressão de doenças, rede de sensores, análise de sinais, teia cósmica, rede complexa, geometria fractal, evolução viral, propagação de contágios em redes, classificação de bactérias usando espectroscopia molecular, imageamento hiperespectral em físico-química e sensoriamento remoto. Outra forma é distinguindo as técnicas de G. Carlsson,

uma sendo o estudo de invariantes homológicos de dados em conjuntos de dados individuais, e a outra é o uso dos invariantes homológicos no estudo de bancos de dados em que os próprios pontos de dados têm estrutura geométrica.

Características da TDA em aplicações

Existem várias características interessantes notáveis das aplicações recentes do TDA:

1. Combinação de ferramentas de vários ramos da matemática. Além da necessidade óbvia de álgebra e topologia, a TDA também fez uso a equações diferenciais parciais, geometria algébrica, teoria da representação, estatística, combinatória e geometria Riemanniana.
2. Análise quantitativa. A topologia é considerada muito suave, pois muitos conceitos são invariantes sob homotopia. No entanto, a topologia persistente é capaz de registrar o nascimento (aparecimento) e morte (desaparecimento) de características topológicas, portanto, informações geométricas extras estão incorporadas nela. Uma evidência em teoria é um resultado parcialmente positivo na unicidade da reconstrução de curvas; dois em aplicações se referem à análise quantitativa da estabilidade do fulereno e a análise quantitativa da autossimilaridade, separadamente.
3. O papel da persistência curta. A persistência curta também se mostrou útil, apesar da crença comum de que o fenômeno seja causado por ruído. Isso é interessante para a teoria matemática.

Um dos principais campos da análise de dados hoje é o aprendizado de máquina. Alguns exemplos de aprendizado de máquina em TDA podem ser encontrados em Adcock et al. Uma conferência é dedicada à ligação entre a TDA e o aprendizado de máquina. Para aplicar ferramentas de aprendizado de máquina, as informações obtidas na TDA devem ser representadas na forma vetorial. Uma tentativa contínua e promissora é o cenário de persistência discutido acima. Outra tentativa usa o conceito de imagens de persistência. Porém, um problema desse método é a perda de estabilidade, uma vez que o teorema da estabilidade rígida depende da representação em código de barras.

Impacto na matemática

A análise topológica de dados e a homologia persistente tiveram impactos na teoria de Morse. A teoria de Morse desempenhou um papel muito importante na teoria de TDA, inclusive na computação. Alguns trabalhos em homologia persistente estenderam resultados sobre funções de Morse para funções tame ou mesmo para funções contínuas. Um resultado esquecido de R. Deheuvels de muito antes da invenção da homologia persistente estende a teoria de Morse a todas as funções contínuas.

Um resultado recente é que a categoria de grafos Reeb é equivalente a uma classe particular de cofeixe. Isso é motivado por trabalhos teóricos em TDA, uma vez que o grafo de Reeb está relacionado à teoria de Morse e o MAPPER é derivado dela. A prova desse teorema se baseia na distância de intercalação.

A homologia persistente está intimamente relacionada às sequências espectrais. Em particular, o algoritmo que leva um complexo filtrado à sua forma canônica permite um cálculo muito mais rápido de sequências espectrais do que o procedimento padrão de cálcular os grupos $E_{p,q}^{r}$ página por página. A persistência em ziguezague pode acabar sendo de importância teórica para as sequências espectrais.

Ver também

• Redução de dimensionalidade
• Mineração de dados
• Visão computacional
• Topologia computacional
• Teoria de Morse discreta
• Análise da forma (geometria digital)
• Teoria do tamanho
• Topologia algébrica

Leitura complementar

Breve introdução

• Estudando a forma dos dados usando topologia, por Michael Lesnick
• Material de referência para análise topológica de dados por Mikael Vejdemo-Johansson

Monografia

• Teoria da persistência: das representações de aljavas à análise de dados, por Steve Oudot

Palestra em vídeo

• Introdução à Homologia Persistente e Topologia para Análise de Dados, por Matthew Wright
• A forma dos dados, de Gunnar Carlsson

Livros didáticos sobre topologia

• Topologia Algébrica, de Allen Hatcher
• Topologia Computacional: Uma Introdução, por Herbert Edelsbrunner e John L. Harer
• Topologia aplicada elementar, por Robert Ghrist

Outros recursos sobre TDA

• Topologia Aplicada, de Stanford
• Rede de pesquisa de topologia algébrica aplicada, do Institute for Mathematics and its Applications
• Aprendizagem Topológica de Kernel: A Teoria Morse Discreta é usada para conectar aprendizado de máquina de kernel à análise de dados topológicos. https://www.researchgate.net/publication/327427685_Topological_Kernel_Learning