Anàlisis de senyes topològiques

En matemàtiques aplicades, el anàlisis topològic de les senyes (en anglés: topological data analysis) (TDA) és un enfocament l'anàlisis de conjunts de senyes que utilisa tècniques de topología. l'extracció d'informació de conjunts de senyes d'alta dimensió, incomplets i sorollosos sol ser un desafiu, no obstant, l'anàlisis topològic de les senyes proporciona un marc general per a analisar dits senyes d'una manera que no és sensible a la mètrica particular elegida i proporciona reducció de dimensionalidad i robustea al soroll. Més allà d'açò, hereta la funtorialidad, un concepte fonamental de les matemàtiques modernes, de la seua naturalea topològica, lo que li permet adaptar-se a noves ferramentes matemàtiques.

La motivació inicial de l'anàlisis topològic de les senyes és estudiar la forma de les senyes és combinar la topología algebraica i atres ferramentes de les matemàtiques pures per a permetre un estudi matemàticament rigorós de la "forma". La ferramenta principal és la homologia persistent, una adaptació de la homologia a les senyes de la núvol de punts. L'homologia persistent s'ha aplicat a molts tipos de senyes en molts camps. Ademés, el seu fonament matemàtic també té importància teòrica. Les característiques úniques de l'anàlisis topològic de les senyes ho convertixen en un pont prometedor entre la topología i la geometria.

Teoria bàsica

Intuïció

TDA es basa en l'idea de que la forma dels conjunts de senyes conté informació rellevant. Les senyes reals d'alta dimensió solen ser escassos i tendixen a tindre característiques rellevants de baixa dimensió. Una tasca de el TDA és proporcionar una caracterisació precisa d'este fet. Per eixemple, la trayectòria d'un sistema simple depredador-presa regit per les equacions de Lotka-Volterra forma un círcul tancat en l'espai d'estats. TDA proporciona ferramentes per a detectar i quantificar dit moviment recurrent.

Molts algoritmes per a l'anàlisis de senyes, inclosos els utilisats en TDA, requerixen la configuració de varis paràmetros. Sense un coneiximent previ del domini, és difícil elegir la recopilació correcta de paràmetros per a un conjunt de senyes. L'idea principal de la homologia persistent és utilisar l'informació obtinguda de tots els valors dels paràmetros codificant esta enorme cantitat d'informació en una forma comprensible i fàcil de representar. En TDA, existix una interpretació matemàtica quan l'informació és un grup d'homologia. En general, se supon que les característiques que persistixen per a una àmplia gama de paràmetros són característiques "verdaderes". Se supon que les característiques que persistixen solament per a un ranc estret de paràmetros són soroll, encara que la justificació teòrica para açò no està clara.

Història primerenca

Els precursors del concepte complet d'homologia persistent varen aparéixer gradualment en el temps. En 1990, Patrizio Frosini va introduir una pseudodistancia entre subvariedades, i posteriorment la funció de tamany, que en curves 1-dim és equivalent a l'homologia persistent 0. Casi una década despuix, Vanessa Robins va estudiar les imàgens d'homomorfismes induïts per inclusió. Finalment, poc despuix, Herbert Edelsbrunner et al. varen introduir el concepte d'homologia persistent junt en un algoritme eficient i la seua visualisació com un diagrama de persistència. Gunnar Carlsson et al. varen reformular la definició inicial i varen donar un método de visualisació equivalent cridat còdics de barres de persistència, interpretant la persistència en el llenguage de l'àlgebra conmutativa.

En topología algebraica, l'homologia persistent va sorgir a través del treball de Sergey Barannikov sobre la teoria de Morse. El conjunt de valors crítics de la funció Morse suau es va dividir canónicamente en parells "naiximent-mort", els complexos filtrats es varen classificar, els seus invariantes, equivalents al diagrama de persistència i els còdics de barres de persistència, junt en l'algoritme eficient per al seu càlcul, varen ser descrits baix el nom de formes canòniques en 1994 per Barannikov.

Conceptes

A continuació es presenten alguns conceptes àmpliament utilisats. Tinga en conte que algunes definicions poden variar d'un autor a un atre.

Una núvol de punts a sovint es definix com un conjunt finito de punts en algun espai euclidiano, pero pot considerar-se qualsevol espai mètric finito.

El complex de Čech d'un núvol de punts és el nervi de la coberta de boles d'un radi fix al voltant de cada punt del núvol.

Un mòdul de persistència $𝕌$ indexat per $\mathbb{Z}$ és un espai vectorial $U_t$ Per a cada u $t\in \mathbb{Z}$, i un mapa llineal $u_t^s:U_s\to U_t$ quan siga $s\le t$, de tal manera que $u_t^t=1$ a pesar de $t$ i $u_t^s{u}_s^r=u_t^r$ quan siga $r\le s\le t.$ Una definició equivalent és un funtor de $\mathbb{Z}$ considerat com un conjunt parcialment ordenat en la categoria d'espais vectorials.

El grup d'homologia persistent $PH$ d'un núvol de punts és el mòdul de persistència definit com $P{H}_k(X)=\prod H_k(X_r)$, on $X_r$ és el complex de Čech de radi $r$ del núvol de punts $X$ i $H_k$ és el grup d'homologia.

Un còdic de barres de persistència és un conjunt múltiple d'intervals en $ℝ$, i un diagrama de persistència és un conjunt múltiple de punts en $\Delta$ ($:=\{(u,v)\in {ℝ}^2\mid u,v\ge 0,u\le v\}$).

La distància de Wasserstein entre dos diagrames de persistència $X$ i $Y$ es definix com $$W_p[L_q](X,Y):=\underset{\phi :X\to Y}{\inf }{[\sum _{x\in X}(\Vert x-\phi (x){\Vert }_q{)}^p]}^{1/p}$$ on $1\le p,q\le \mathrm{\infty }$ i $\phi$ rancs sobre biyecciones entre $X$ i $Y$. Consulte la figura 3.1 en Munch per a obtindre una ilustració.

La distància de coll de botella entre $X$ i $Y$ és $$W_{\mathrm{\infty }}[L_q](X,Y):=\underset{\phi :X\to Y}{\inf }\underset{x\in X}{\sup }\Vert x-\phi (x){\Vert }_q.$$ Est és un cas especial de la distància de Wasserstein, sent $p=\mathrm{\infty }$.

Propietat bàsica

Teorema d'estructura

La primera teorema de classificació per a homologia persistent va aparéixer en 1994 a través de les formes canòniques de Barannikov. El teorema de classificació que interpreta la persistència en el llenguage de l'àlgebra conmutativa va aparéixer en 2005: per a un mòdul de persistència generat finitamente $C$ en camp $F$ coeficients, $$H(C;F)\simeq \underset{i}{⨁}{x}^{t_i}\cdot F[x]\oplus (\underset{j}{⨁}{x}^{r_j}\cdot (F[x]/(x^{s_j}\cdot F[x]))).$$ Intuitivamente, les parts lliures corresponen als generadors d'homologia que apareixen a nivell de filtració. $t_i$ i mai desapareixen, mentres que les parts de torsió corresponen a les que apareixen a nivell de filtració. $r_j$ i per últim $s_j$ passos de la filtració (o equivalentemente, desapareixen en el nivell de filtració) $s_j+r_j$).

L'homologia persistent es visualisa a través d'un còdic de barres o un diagrama de persistència. El còdic de barres té la seua raïl en les matemàtiques abstractes. És dir, la categoria de complexos filtrats finitos sobre un camp és semi-simple. Qualsevol complex filtrat és isomorfo a la seua forma canònica, una suma directa de complexos filtrats simples unidimensionals i bidimensionales.

Estabilitat

L'estabilitat és desijable perque proporciona robustea front al soroll. Si $X$ és qualsevol espai que és homeomorfo a un complex simplicial, i $f,g:X\to ℝ$ són funcions contínues domesticades, llavors els espais vectorials de persistència $\{H_k(f^{-1}([0,r]))\}$ i $\{H_k(g^{-1}([0,r]))\}$ es presenten de forma finita i $W_{\mathrm{\infty }}(D(f),D(g))\le \Vert f-g{\Vert }_{\mathrm{\infty }}$, on $W_{\mathrm{\infty }}$ es referix a la distància del coll de botella i $D$ ¿El mapa du una funció domesticada contínua al diagrama de persistència de la seua $k$ -ésima homologia.

Fluix de treball

El fluix de treball bàsic en TDA és:

núvol de punts

$\to$

complexos anidados

$\to$

mòdul de persistència

$\to$

còdic de barres o diagrama

1. Si $X$ és un núvol de punts, reemplace $X$ en una família anidada de complexos simpliciales $X_r$ (com el complex Čech o Vietoris-Rips). Este procés convertix el núvol de punts en una filtració de complexos simples. Prenent l'homologia de cada complex en esta filtració s'obté un mòdul de persistència. $$H_i(X_{r_0})\to H_i(X_{r_1})\to H_i(X_{r_2})\to \cdots$$
2. Aplicar la teorema d'estructura per a obtindre els números de Betti persistents, diagrama de persistència o, equivalentemente, còdic de barres.

Gràficament parlant,

Archiu:Illustration of Typical Workflow in TDA.jpeg

Un us habitual de la persistència en TDA

Càlcul

El primer algoritme sobre tots els camps per a homologia persistent en un entorn d'topología algebraica va ser descrit per Barannikov a través de la reducció a la forma canònica per mig de matrius triangulars superiors. L'algoritme per a l'homologia persistent sobre $F_2$ Va ser proporcionat per Edelsbrunner et al. Afra Zomorodian i Carlsson varen proporcionar l'algoritme pràctic per a calcular l'homologia persistent en tots els camps. El llibre de Edelsbrunner i Harer oferix una guia general sobre topología computacional.

Un problema que sorgix en la computació és l'elecció de lo complex. El complex Čech i el complex Vietoris–Rips són els més naturals a primera vista; no obstant, el seu tamany creix ràpidament en el número de punts de senyes. Es preferix el complex de Vietoris-Rips al complex de Čech perque la seua definició és més simple i el complex de Čech requerix un esforç adicional per a definir-ho en un espai mètric finito general. S'han estudiat formes eficients de reduir el cost computacional de l'homologia. Per eixemple, el complex α i el complex testic s'utilisen per a reduir la dimensió i el tamany dels complexos.

Recentment, la teoria de Morse discreta ha demostrat ser prometedora per a l'homologia computacional perque pot reduir un complex simplicial dau a un complex celular molt més chicotet que és homotópico a l'original. De fet, esta reducció es pot realisar a mida que es construïx el complex utilisant la teoria de matroides, lo que conduïx a majors auments del rendiment. Un atre algoritme recent aforra temps en ignorar les classes d'homologia en baixa persistència.

Hi ha varis paquets de software disponibles, com javaPlex, Dionysus, Perseus, PHAT, DIPHA, GUDHI, Ripser i TDAstats. Otter et al. realisen una comparació entre estes ferramentes. Giotto-tda és un paquet de Python dedicat a integrar TDA en el fluix de treball d'aprenentage automàtic per mig d'una API scikit-learn [1]. Un paquet R TDA és capaç de calcular conceptes recentment inventats com el paisage i l'estimador de distància del núcleu. El Topology ToolKit està especialisat en senyes contínues definides en varietats de baixa dimensió (1, 2 o 3), com els que normalment es troben en la visualisació científica. Cubicle està optimisat per a senyes d'imàgens en escala de grises grans (escala de gigaoctets) en dimensió 1, 2 o 3 utilisant complexos cúbics i teoria de Morse discreta. Un atre paquet R, TDAstats, utilisa la biblioteca Ripser per a calcular l'homologia persistent.

Vore també

• Reducció de dimensionalidad
• Mineria de senyes
• Visió per computadora
• Topología computacional
• Teoria de Morse discreta
• Anàlisis de formes (geometria digital)
• Topología algebraica