Topologisk dataanalys

Inom tillämpad matematik är topologisk baserad dataanalys ( TDA ) ett tillvägagångssätt för analys av datamängder med hjälp av tekniker från topologi . Utvinning av information från datauppsättningar som är högdimensionella, ofullständiga och bullriga är generellt sett utmanande. TDA tillhandahåller ett allmänt ramverk för att analysera sådana data på ett sätt som är okänsligt för det speciella mått som valts och ger dimensionsreduktion och robusthet mot brus. Utöver detta ärver den funktionalitet , ett grundläggande koncept för modern matematik, från dess topologiska natur, vilket gör att den kan anpassa sig till nya matematiska verktyg. ^{[ citat behövs ]}

Den initiala motivationen är att studera formen på data. TDA har kombinerat algebraisk topologi och andra verktyg från ren matematik för att möjliggöra matematiskt rigorösa studier av "form". Huvudverktyget är persistent homology , en anpassning av homologi till punktmolndata . Ihållande homologi har applicerats på många typer av data inom många områden. Dessutom är dess matematiska grund också av teoretisk betydelse. De unika egenskaperna hos TDA gör det till en lovande bro mellan topologi och geometri. ^{[ citat behövs ]}

Grundläggande teori

Intuition

TDA bygger på idén att formen på datamängder innehåller relevant information. Verkliga högdimensionella data är vanligtvis sparsamma och tenderar att ha relevanta lågdimensionella egenskaper. En uppgift för TDA är att ge en exakt karaktärisering av detta faktum. Till exempel bildar banan för ett enkelt rovdjur-byte-system som styrs av Lotka–Volterra-ekvationerna en sluten cirkel i tillståndsrummet. TDA tillhandahåller verktyg för att upptäcka och kvantifiera sådana återkommande rörelser.

Många algoritmer för dataanalys, inklusive de som används i TDA, kräver att olika parametrar ställs in. Utan förkunskaper om domänen är den korrekta insamlingen av parametrar för en datamängd svår att välja. Den huvudsakliga insikten i persistent homologi är att använda informationen som erhålls från alla parametervärden genom att koda denna enorma mängd information till en begriplig och lätt att representera form. Med TDA finns det en matematisk tolkning när informationen är en homologigrupp . Generellt sett är antagandet att egenskaper som kvarstår för ett brett spektrum av parametrar är "sanna" egenskaper. Funktioner som kvarstår för endast ett snävt område av parametrar antas vara brus, även om den teoretiska motiveringen för detta är oklar.

Tidig historia

Föregångare till hela konceptet med ihållande homologi dök upp gradvis över tiden. 1990 introducerade Patrizio Frosini storleksfunktionen, som motsvarar den 0:e persistenta homologin. Nästan ett decennium senare Vanessa Robins bilderna av homomorfismer som inducerades av inkludering. Slutligen, kort därefter, Edelsbrunner et al. introducerade konceptet persistent homologi tillsammans med en effektiv algoritm och dess visualisering som ett persistensdiagram. Carlsson et al. omformulerade den ursprungliga definitionen och gav en likvärdig visualiseringsmetod som kallas persistensstreckkoder, som tolkar persistens på språket för kommutativ algebra.

Inom algebraisk topologi har den ihållande homologin uppstått genom Sergey Barannikovs arbete med Morse-teorin. Uppsättningen av kritiska värden för jämn morsefunktion delades kanoniskt upp i par "födelse-död", filtrerade komplex klassificerades, deras invarianter, motsvarande persistensdiagram och persistensstreckkoder, tillsammans med den effektiva algoritmen för deras beräkning, beskrevs under namnet av kanoniska former 1994 av Barannikov.

Begrepp

Några allmänt använda begrepp presenteras nedan. Observera att vissa definitioner kan variera från författare till författare.

Ett punktmoln definieras ofta som en ändlig uppsättning punkter i något euklidiskt utrymme, men kan anses vara vilket ändligt metriskt utrymme som helst.

Čech -komplexet av ett punktmoln är nerven för täcket av bollar med en fast radie runt varje punkt i molnet.

En beständighetsmodul $\mathbb {U}$ indexerad av $\mathbb {Z}$ är ett vektorrum $U_{t}$ för varje $t\in \mathbb {Z}$ , och en linjär karta $u_{t}^{s}:U_{s}\to U_{t}$ närhelst $s\leq t$ , så att $u_{t}^{t}=1$ för alla $t$ och $u_ {t}^{s}u_{s}^{r}=u_{t}^{r}$ närhelst $r\leq s\leq t.$ En ekvivalent definition är en funktor från $\mathbb {Z}$ betraktad som en delvis ordnad uppsättning till kategorin vektorrum.

Den persistenta homologigruppen $PH$ i ett punktmoln är persistensmodulen definierad som $X)=\prod H_{ k}(X_{r})}$ , där $X_{r}$ är Čech-komplexet av radien $r$ för punktmolnet $X$ och $H_ {k}$ är homologigruppen.

En persistensstreckkod är en multiuppsättning av intervall i $\mathbb {R}$ , och ett persistensdiagram är en multiuppsättning av punkter i $\Delta$ ( ${\displaystyle :=\{(u,v)\in \mathbb {R} ^{2}\mid u,v\geq 0,u\leq v\}} )$ .

Wasserstein -avståndet mellan två persistensdiagram $X$ och $Y$ definieras som

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

där

1\leq p,q\leq \infty

och

\varphi

sträcker sig över bijektioner mellan

X

och

Y

. Se figur 3.1 i Munch för illustration.

Flaskhalsavståndet mellan $X$ och $\displaystyle Y}$ { är

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

Detta är ett specialfall av Wasserstein-avstånd, som låter

p=\infty

.

Grundläggande egendom

Struktursats

Det första klassificeringsteoremet för ihållande homologi dök upp 1994 via Barannikovs kanoniska former. Klassificeringssatsen som tolkar persistens i språket för kommutativ algebra dök upp 2005: för en ändligt genererad persistensmodul $C$ med fält $F$ -koefficienter,

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]))\höger).

Intuitivt motsvarar de fria delarna homologigeneratorerna som uppträder på filtreringsnivån

t_{i}

och aldrig försvinner, medan torsionsdelarna motsvarar de som uppträder på filtreringsnivån

r_{j}

och varar i

s_{j}

steg av filtreringen (eller motsvarande, försvinner vid filtreringsnivån

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

.

Persistent homologi visualiseras genom en streckkod eller persistensdiagram. Streckkoden har sin rot i abstrakt matematik. Kategorin av finita filtrerade komplex över ett fält är nämligen halvenkel. Varje filtrerat komplex är isomorft till sin kanoniska form, en direkt summa av en- och tvådimensionella enkla filtrerade komplex.

Stabilitet

Stabilitet är önskvärt eftersom det ger robusthet mot buller. Om $X$ är ett utrymme som är homeomorft till ett förenklat komplex, och $f,g:X\to \mathbb {R}$ är kontinuerliga tama funktioner, då är persistensen vektorrum $\{H_{k}(f^{-1}([0,r]))\}$ och $\{H_{k}(g^{-1}([0,r]))\}$ presenteras ändligt, och ${\displaystyle W_{\infty }(D(f),D(g))\leq \lVert fg\rVert _{\infty }} , där$ W $\ displaystyle W_{\infty }}$ hänvisar till flaskhalsavståndet och $D$ är kartan som tar en kontinuerlig tam funktion till persistensdiagrammet för dess $k$ -te homologi.

Arbetsflöde

Det grundläggande arbetsflödet i TDA är:

punktmoln	$\to$	kapslade komplex	$\to$	uthållighetsmodul	$\to$	streckkod eller diagram

Om $X$ är ett punktmoln, ersätt $X$ med en kapslad familj av enkla komplex $X_{r}$ (som Čech eller Vietoris-Rips-komplexet). Denna process omvandlar punktmolnet till en filtrering av enkla komplex. Att ta homologin för varje komplex i denna filtrering ger en persistensmodul $H_{i}(X_{r_{0}})\till H_{i}(X_{r_ {1}})\to H_{i}(X_{r_{2}})\to \cdots$
Tillämpa struktursatsen för att tillhandahålla en parametriserad version av Betti-nummer , persistensdiagram eller motsvarande streckkod.

Grafiskt sett,

En vanlig användning av persistens i TDA

Beräkning

Den första algoritmen över alla fält för ihållande homologi i algebraisk topologimiljö beskrevs av Barannikov genom reduktion till den kanoniska formen med övre triangulära matriser. Den första algoritmen för ihållande homologi över $F_{2}$ gavs av Edelsbrunner et al. Zomorodian och Carlsson gav den första praktiska algoritmen för att beräkna persistent homologi över alla fält. Edelsbrunner och Harers bok ger allmän vägledning om beräkningstopologi.

En fråga som uppstår vid beräkning är valet av komplex. Čech -komplexet och Vietoris–Rips-komplexet är mest naturliga vid första anblicken; deras storlek växer dock snabbt med antalet datapunkter. Vietoris-Rips-komplexet föredras framför Čech-komplexet eftersom dess definition är enklare och Čech-komplexet kräver extra ansträngning för att definiera i ett allmänt ändligt metriskt utrymme. Effektiva sätt att sänka beräkningskostnaden för homologi har studerats. Till exempel används a-komplexet och vittneskomplexet för att minska dimensionen och storleken på komplex.

Nyligen har diskret Morse-teorin visat lovande för beräkningshomologi eftersom den kan reducera ett givet förenklat komplex till ett mycket mindre cellulärt komplex som är homotopiskt till det ursprungliga. Denna minskning kan faktiskt utföras när komplexet konstrueras med hjälp av matroidteori , vilket leder till ytterligare prestationshöjningar. En annan ny algoritm sparar tid genom att ignorera homologiklasserna med låg uthållighet.

Olika mjukvarupaket är tillgängliga, såsom javaPlex , Dionysus , Perseus , PHAT , DIPHA , GUDHI , Ripser och TDAstats . En jämförelse mellan dessa verktyg görs av Otter et al. Giotto-tda är ett Python-paket dedikerat till att integrera TDA i arbetsflödet för maskininlärning med hjälp av ett scikit-learn [1] API. Ett R-paket TDA kan beräkna nyligen uppfunna begrepp som landskap och kärnavståndsberäknaren. Topology ToolKit är specialiserat för kontinuerliga data definierade på grenrör med låg dimension (1, 2 eller 3), som vanligtvis finns i vetenskaplig visualisering . Ett annat R-paket, TDAstats , implementerar Ripser-biblioteket för att beräkna persistent homologi.

Visualisering

Högdimensionell data är omöjlig att visualisera direkt. Många metoder har uppfunnits för att extrahera en lågdimensionell struktur från datamängden, såsom huvudkomponentanalys och flerdimensionell skalning . Det är dock viktigt att notera att själva problemet är illa ställt, eftersom många olika topologiska egenskaper kan hittas i samma datamängd. Således är studiet av visualisering av högdimensionella utrymmen av central betydelse för TDA, även om det inte nödvändigtvis involverar användningen av ihållande homologi. Emellertid har nya försök gjorts att använda ihållande homologi vid datavisualisering.

Carlsson et al. har föreslagit en allmän metod som kallas MAPPER . Det ärver Serres idé att en täckning bevarar homotopin. En generaliserad formulering av MAPPER är följande:

Låt $X$ och $Z$ vara topologiska rum och låt $f:X\to Z$ vara en kontinuerlig karta. Låt ${\displaystyle \mathbb {U} =\{U_{\alpha }\}_{\alpha \in A}} vara$ en finit öppen täckning av $Z$ . Utgången från MAPPER är nerven för det tillbakadragna locket ${\textstyle M(\mathbb {U} ,f):=N(f^{-1 }(\mathbb {U} ))}$ , där varje förbild delas upp i sina anslutna komponenter. Detta är ett mycket allmänt koncept, där Reeb-grafen och sammanslagna träd är specialfall.

Detta är inte riktigt den ursprungliga definitionen. Carlsson et al. välj $Z$ för att vara $\mathbb {R}$ eller ${\displaystyle \mathbb {R} ^{2}} ,$ och täck den med öppna mängder så att högst två skär varandra. Denna begränsning innebär att utgången är i form av ett komplext nätverk . Eftersom topologin för ett ändligt punktmoln är trivial, används klustringsmetoder (såsom enkel länkning ) för att producera analogen av anslutna uppsättningar i förbilden $f^{-1}(U)$ när MAPPER tillämpas på faktiska data.

Matematiskt sett är MAPPER en variant av Reeb-grafen . Om ${\textstyle M(\mathbb {U} ,f)}$ är högst endimensionell, då för varje $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}).

Den ökade flexibiliteten har också nackdelar. Ett problem är instabilitet, eftersom en viss förändring av valet av locket kan leda till stora förändringar av utdata från algoritmen. Arbete har gjorts för att lösa detta problem.

Tre framgångsrika tillämpningar av MAPPER finns i Carlsson et al. En kommentar om tillämpningarna i detta dokument av J. Curry är att "ett vanligt drag av intresse för tillämpningar är närvaron av utbrott eller rankor."

En gratis implementering av MAPPER finns tillgänglig online skriven av Daniel Müllner och Aravindakshan Babu. MAPPER utgör också grunden för Ayasdis AI-plattform.

Flerdimensionell uthållighet

Flerdimensionell uthållighet är viktig för TDA. Begreppet uppstår i både teori och praktik. Den första undersökningen av multidimensionell uthållighet var tidigt i utvecklingen av TDA. Carlsson-Zomorodian introducerade teorin om multidimensionell persistens i och i samarbete med Singh introducerade användningen av verktyg från symbolisk algebra (Grobner-basmetoder) för att beräkna MPH-moduler. Deras definition presenterar flerdimensionell beständighet med n parametrar som en $\mathbb {Z} ^{n}$ graderad modul över en polynomring i n variabler. Verktyg från kommutativ och homologisk algebra används för att studera flerdimensionell uthållighet i arbetet av Harrington-Otter-Schenck-Tillman. Den första applikationen som dyker upp i litteraturen är en metod för formjämförelse, liknande uppfinningen av TDA.

Definitionen av en n -dimensionell beständighetsmodul i $\mathbb {R} ^{n}$ är

vektorutrymme $V_{s}$ tilldelas varje punkt i $s=(s_{1},...,s_{n} )$
map $\rho _{s}^{t}:V_{s}\to V_{t}$ tilldelas om $s\leq t$ ( $s_{i}\leq t_{i},i=1,...,n)$
kartor uppfyller $\rho _{r}^{t}=\rho _{s}^{t}\circ \rho _{r}^{s}$ för alla $r\leq s\leq t$

Det kan vara värt att notera att det finns kontroverser om definitionen av multidimensionell persistens.

En av fördelarna med endimensionell uthållighet är dess representation med ett diagram eller streckkod. Emellertid existerar inte diskreta fullständiga invarianter av flerdimensionella beständighetsmoduler. Den främsta anledningen till detta är att strukturen av samlingen av oupplösbara är extremt komplicerad av Gabriels teorem i teorin om kogerrepresentationer, även om en ändligt genererad n-dim persistensmodul unikt kan dekomponeras till en direkt summa av oupplösbara på grund av Krull -Schmidts sats.

Ändå har många resultat fastställts. Carlsson och Zomorodian introducerade ranginvarianten ρ $\displaystyle \rho _{M}(u,v)}$ , definierad som ${\displaystyle \rho _{M}(u,v)=\mathrm {rank} (x^{uv}:M_{u}\to M_{v})} ,$ där $M$ är en ändligt genererad n-graderad modul. I en dimension motsvarar det streckkoden. I litteraturen hänvisas ofta till rankinvarianten som persistent Betti-tal (PBNs). I många teoretiska verk har författare använt en mer begränsad definition, en analog från sublevel set persistence. Specifikt ges beständighetstalen för en funktion $f:X\to \mathbb {R} ^{k}$ av funktionen $\beta _{f}:\Delta ^{+}\to \mathrm {N}$ , vilket tar varje $(u,v)\in \Delta ^{+}$ till ${\displaystyle \beta _{f}(u,v):=\mathrm { rank} (H(X(f\leq u)\till H(X(f\leq v)))} ,$ där $\Delta ^{+}:=\{(u,v)\in \mathbb {R} ^{k}\times \mathbb {R} ^{k}:u\leq v\}$ och $X(f\leq u):=\{x\in X:f(x)\leq u\}$ .

Några grundläggande egenskaper inkluderar monotoni och diagonalhopp. Beständiga Betti-tal kommer att vara ändliga om $X$ är ett kompakt och lokalt sammandragbart delrum av $\mathbb {R} ^{n}$ .

Med hjälp av en foliationsmetod kan k-dim PBNs sönderdelas till en familj av 1-dim PBNs genom dimensionsavdrag. Denna metod har också lett till ett bevis på att multi-dim PBN är stabila. Diskontinuiteterna för PBN förekommer endast vid punkter $(u,v)(u\leq v)$ där antingen $u$ är en diskontinuerlig punkt på $\rho _{M}(\star ,v)$ eller $v$ är en diskontinuerlig punkt av $\rho (u,\star )$ under antagandet att $f\in C^{0}(X,\mathbb {R} ^{k})$ och $X$ är en kompakt, triangulerbar topologisk Plats.

Persistent utrymme, en generalisering av beständigt diagram, definieras som multiuppsättningen av alla punkter med multiplicitet större än 0 och diagonalen. Det ger en stabil och komplett representation av PBN. Ett pågående arbete av Carlsson et al. försöker ge geometrisk tolkning av ihållande homologi, vilket kan ge insikter om hur man kombinerar maskininlärningsteori med topologisk dataanalys.

Den första praktiska algoritmen för att beräkna flerdimensionell persistens uppfanns mycket tidigt. Därefter har många andra algoritmer föreslagits, baserade på sådana koncept som diskret morse-teori och ändlig provuppskattning.

Andra persistenser

Standardparadigmet i TDA kallas ofta sublevel persistens . Förutom multidimensionell uthållighet har många arbeten gjorts för att utvidga detta specialfall.

Sicksack uthållighet

Kartorna som inte är noll i beständighetsmodulen är begränsade av förbeställningsrelationen i kategorin. Emellertid har matematiker funnit att enhällighet i riktningen inte är avgörande för många resultat. "Den filosofiska poängen är att nedbrytningsteorin för grafrepresentationer är något oberoende av orienteringen av grafkanterna". Sicksack-uthållighet är viktigt för den teoretiska sidan. Exemplen som ges i Carlssons recensionsartikel för att illustrera vikten av funktionalitet delar alla några av dess egenskaper.

Utökad uthållighet och uthållighet på nivåer

Vissa försök är att förlora den strängare begränsningen av funktionen. Se Kategorisering och cosheaves och Inverkan på matematik för mer information.

Det är naturligt att utvidga persistenshomologi till andra grundläggande begrepp inom algebraisk topologi, såsom kohomologi och relativ homologi/kohomologi. En intressant tillämpning är beräkningen av cirkulära koordinater för en datamängd via den första persistenta kohomologigruppen.

Cirkulär uthållighet

Normal persistenshomologi studerar verkligt värderade funktioner. Den cirkelvärderade kartan kan vara användbar, "beständighetsteorin för cirkelvärdade kartor lovar att spela rollen för vissa vektorfält liksom standardbeständighetsteorin för skalära fält", som kommenterat i Dan Burghelea et al . Den största skillnaden är att Jordan-celler (mycket lika i format som Jordan-blocken i linjär algebra) är icke-triviala i cirkelvärdade funktioner, vilket skulle vara noll i verkligt värde, och kombination med streckkoder ger invarianterna för en tam karta, under måttliga förhållanden.

Två tekniker som de använder är Morse-Novikov-teori och grafrepresentationsteori. Nyare resultat kan hittas i D. Burghelea et al. Till exempel kan tamhetskravet ersättas av det mycket svagare tillståndet, kontinuerligt.

Uthållighet med vridning

Beviset för struktursatsen bygger på att basdomänen är fält, så inte många försök har gjorts på persistenshomologi med torsion. Frosini definierade en pseudometrisk på denna specifika modul och bevisade dess stabilitet. En av dess nyheter är att det inte är beroende av någon klassificeringsteori för att definiera måttet.

Kategorisering och coheaves

En fördel med kategoriteorin är dess förmåga att lyfta konkreta resultat till en högre nivå, som visar samband mellan till synes osammanhängande objekt. Bubenik et al. erbjuder en kort introduktion av kategoriteori anpassad för TDA.

Kategoriteori är språket i modern algebra, och har använts i stor utsträckning i studiet av algebraisk geometri och topologi. Det har noterats att "nyckelobservationen av är att persistensdiagrammet som produceras av endast beror på den algebraiska strukturen som bärs av detta diagram." Användningen av kategoriteori i TDA har visat sig vara fruktbar.

Efter notationerna i Bubenik et al., är indexeringskategorin ${\textstyle P} vilken som helst$ förbeställd uppsättning (inte nödvändigtvis $\mathbb {N}$ eller ${\displaystyle \mathbb {R} } )$ , målkategori $D$ är vilken kategori som helst (istället för den vanligaste ${\textstyle \mathrm {Vect} _{\mathbb {F} }} ),$ och funktorer ${\textstyle P \to D}$ kallas generaliserade persistensmoduler i $D$ , över ${\textstyle P}$ .

En fördel med att använda kategoriteori i TDA är en tydligare förståelse av begrepp och upptäckten av nya samband mellan bevis. Ta två exempel för illustration. Förståelsen av överensstämmelsen mellan interfoliering och matchning är av enorm betydelse, eftersom matchning har varit den metod som användes i början (modifierad från Morse-teorin). En sammanfattning av verk finns i Vin de Silva et al. Många teorem kan bevisas mycket lättare i en mer intuitiv miljö. Ett annat exempel är förhållandet mellan konstruktionen av olika komplex från punktmoln. Det har länge märkts att Čech och Vietoris-Rips-komplex är relaterade. Specifikt $V_{r}(X)\subset C_{{\sqrt {2}}r}(X)\subset V_ {2r}(X)$ . Det väsentliga förhållandet mellan Cech- och Rips-komplex kan ses mycket tydligare i kategoriskt språk.

Språket i kategoriteorin hjälper också till att skapa resultat i termer som känns igen för den bredare matematiska gemenskapen. Flaskhalsavstånd används ofta i TDA på grund av resultaten på stabilitet med avseende på flaskhalsavståndet. Faktum är att interfolieringsavståndet är terminalobjektet i en poset-kategori av stabila mått på flerdimensionella beständighetsmoduler i ett primfält .

Skivor , ett centralt begrepp i modern algebraisk geometri , är i sig släkt med kategoriteori. Grovt sett skivor det matematiska verktyget för att förstå hur lokal information avgör global information. Justin Curry betraktar nivåbeständighet som studiet av fibrer med kontinuerliga funktioner. Objekten som han studerar är mycket lika de av MAPPER, men med kärveteori som teoretisk grund. Även om inget genombrott i teorin om TDA ännu har använt kärveteori, är det lovande eftersom det finns många vackra teorem inom algebraisk geometri som rör kärveteori. Till exempel är en naturlig teoretisk fråga om olika filtreringsmetoder ger samma uteffekt.

Stabilitet

Stabilitet är av central betydelse för dataanalys, eftersom riktiga data bär på ljud. Genom användning av kategoriteori, Bubenik et al. har skiljt mellan mjuka och hårda stabilitetsteorem, och bevisat att mjuka fall är formella. Specifikt är det allmänna arbetsflödet för TDA

data	${\stackrel {F}{\longrightarrow }}$	topologisk persistensmodul	${\stackrel {H}{\longrightarrow }}$	algebraisk beständighetsmodul	${\stackrel {J}{\longrightarrow }}$	diskret invariant

Den mjuka stabilitetssatsen hävdar att $HF$ är Lipschitz kontinuerlig , och den hårda stabilitetssatsen hävdar att $J$ är Lipschitz kontinuerlig.

Flaskhalsavstånd används ofta i TDA. Isometrisatsen hävdar att interfolieringsavståndet $d_{I}$ är lika med flaskhalsavståndet. Bubenik et al. har abstraherat definitionen till den mellan funktorerna $F,G:P\to D$ när ${\textstyle P}$ är utrustad med en sublinjär projektion eller superlinjär familj, i vilken fortfarande är en pseudometrisk . Med tanke på de magnifika karaktärerna av interfolieringsavstånd, introducerar vi här den allmänna definitionen av interfolieringsavstånd (istället för den först introducerade): Låt $\Gamma ,K\in \mathrm {Trans_ {P}}$ (en funktion från ${\textstyle P}$ till ${\textstyle P}$ som är monoton och uppfyller $x\leq \Gamma (x)$ för alla ${\textstyle x\in P}$ ). A $(\Gamma ,K)$ -interfoliering mellan F och G består av naturliga transformationer $\varphi \colon F\Rightarrow G\Gamma$ och $\psi :G\Rightarrow FK$ , så att $(\psi \Gamma )=\varphi F\eta _{K\Gamma }$ och $(\varphi \Gamma )=\psi G\eta _{\Gamma K}$ .

De två huvudsakliga resultaten är

Låt ${\textstyle P}$ vara en förbeställd mängd med en sublinjär projektion eller superlinjär familj. Låt ${\textstyle H:D\to E}$ vara en funktion mellan godtyckliga kategorier ${\textstyle D,E}$ . För två valfria funktioner ${\textstyle F,G:P\to D}$ , har vi ${\textstyle d_{I }(HF,HG)\leq d_{I}(F,G)}$ .
Låt ${\textstyle P}$ vara en poset av ett metriskt utrymme ${\textstyle Y}$ , ${\textstyle X}$ vara ett topologiskt utrymme. Och låt ${\textstyle f,g:X\to Y}$ (inte nödvändigtvis kontinuerliga) vara funktioner, och ${\textstyle F,G}$ vara det motsvarande beständighetsdiagrammet. Sedan $d_{I}(F,G)\leq d_ {\infty }(f,g):=\sup _{x\in X}d_{Y}(f(x),g(x))$ .

Dessa två resultat sammanfattar många resultat om stabiliteten hos olika modeller av persistens.

För stabilitetsteoremet för flerdimensionell uthållighet, se underavsnittet om uthållighet.

Struktursats

Struktursatsen är av central betydelse för TDA; som kommenterat av G. Carlsson, "det som gör homologi användbar som en diskriminator mellan topologiska rum är det faktum att det finns en klassificeringssats för ändligt genererade abelska grupper." (se grundsatsen för ändligt genererade abelska grupper) .

Huvudargumentet som används i beviset för den ursprungliga struktursatsen är standardstruktursatsen för ändligt genererade moduler över en principiell idealdomän . Detta argument misslyckas dock om indexeringsuppsättningen är $(\mathbb {R} ,\leq )$ .

I allmänhet kan inte alla beständighetsmoduler delas upp i intervaller. Många försök har gjorts för att mildra restriktionerna för den ursprungliga struktursatsen. ^{[ förtydligande behövs ]} Fallet för punktvis ändligdimensionella beständighetsmoduler indexerade av en lokalt ändlig delmängd av $\mathbb {R}$ löses baserat på Webbs arbete. Det mest anmärkningsvärda resultatet görs av Crawley-Boevey, som löste fallet med $\mathbb {R}$ . Crawley-Boeveys teorem säger att varje punktvis änddimensionell beständighetsmodul är en direkt summa av intervallmoduler.

För att förstå definitionen av hans teorem behöver vissa begrepp introduceras. Ett intervall i $(\mathbb {R} ,\leq )$ definieras som en delmängd $I\subset \mathbb {R}$ med egenskapen att om $r,t\in I$ och om det finns ett $s\in \mathbb {R}$ så att $r\leq s\leq t$ , sedan $s\in I$ också. En intervallmodul $k_{I}$ tilldelar varje element $s\in I$ vektorutrymmet $k$ och tilldelar nollvektorutrymmet till element i $\mathbb {R} \setminus I$ . Alla kartor $\rho _{s}^{t}$ är nollkartan, om inte $s,t\in I$ och $s\leq t$ , i vilket fall $\rho _{s}^{t}$ är identitetskartan. Intervallmoduler är oupplösliga.

Även om resultatet av Crawley-Boevey är ett mycket kraftfullt teorem, sträcker det sig fortfarande inte till q-tame-fallet. En persistensmodul är q-tam om rangordningen för $\rho _{s}^{t}$ är ändlig för alla $s<t$ . Det finns exempel på q-tame persistensmoduler som inte kan vara punktvis ändliga. Det visar sig dock att en liknande struktursats fortfarande gäller om de egenskaper som bara finns vid ett indexvärde tas bort. Detta gäller eftersom de oändliga dimensionella delarna vid varje indexvärde inte kvarstår, på grund av tillståndet med ändlig rangordning. definieras den observerbara kategorin ${\displaystyle \mathrm {Ob} } som$ $\mathrm {Pers} /\mathrm {Eph}$ , där ${\ displaystyle \mathrm {Eph} }$ betecknar hela underkategorin av $\mathrm {Pers}$ vars objekt är de efemära modulerna ( $\rho _{s}^{t}= 0$ närhelst $s<t$ ).

Observera att de utökade resultaten som listas här inte gäller för sicksackbeständighet, eftersom analogen av en sicksackbeständighetsmodul över $\mathbb {R}$ inte är omedelbart uppenbar.

Statistik

Verkliga data är alltid ändliga, så dess studie kräver att vi tar hänsyn till stokasticitet. Statistisk analys ger oss möjligheten att separera sanna egenskaper hos data från artefakter som introduceras av slumpmässigt brus. Persistent homologi har ingen inneboende mekanism för att skilja mellan egenskaper med låg sannolikhet och egenskaper med hög sannolikhet.

Ett sätt att tillämpa statistik på topologisk dataanalys är att studera de statistiska egenskaperna hos topologiska egenskaper hos punktmoln. Studiet av slumpmässiga förenklade komplex ger viss insikt i statistisk topologi. K. Turner et al. ger en sammanfattning av arbetet i denna anda.

Ett andra sätt är att studera sannolikhetsfördelningar på persistensutrymmet. Persistensutrymmet $B_{\infty }$ är ${\displaystyle \coprod _{n}B_{n}/{\backsim }} ,$ där $B_{n }$ är utrymmet för alla streckkoder som innehåller exakt $n$ intervall och ekvivalenserna är $\{[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}]\}$ om $x_{n}=y_{n}$ . Detta utrymme är ganska komplicerat; till exempel är den inte komplett under flaskhalsmåttet. Det första försöket att studera det är av Y. Mileyko et al. Utrymmet av persistensdiagram $D_{p}$ i deras papper definieras som

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

där

\Delta

är den diagonala linjen i

\mathbb {R} ^{2}

. En trevlig egenskap är att

D_{p}

är komplett och separerbar i Wasserstein-metriken

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}

. Förväntning, varians och betingad sannolikhet kan definieras i Fréchet-bemärkelsen . Detta gör att många statistiska verktyg kan portas till TDA. Arbeten med nollhypotes signifikanstest , konfidensintervall och robusta uppskattningar är anmärkningsvärda steg.

Ett tredje sätt är att betrakta kohomologin av probabilistiskt utrymme eller statistiska system direkt, kallat informationsstrukturer och i grunden bestående av trippeln ( $\Omega ,\Pi ,P$ ), urvalsutrymme, slumpvariabler och sannolikhetslagar. Slumpvariabler betraktas som partitioner av de n atomsannolikheterna (sedda som en sannolikhet (n-1)-simplex, $|\Omega |=n$ ) på partitionernas gitter ( ${\ displaystyle \Pi _{n}}$ ). De slumpmässiga variablerna eller modulerna av mätbara funktioner tillhandahåller cochain-komplexen medan coboundary betraktas som den allmänna homologiska algebra som först upptäcktes av Hochschild med en vänsteråtgärd som implementerar verkan av konditionering. Det första samcykelvillkoret motsvarar kedjeregeln för entropi, vilket gör det möjligt att härleda unikt upp till den multiplikativa konstanten, Shannon-entropin som den första kohomologiklassen. Övervägandet av en deformerad vänsteraktion generaliserar ramverket till Tsallis-entropier. Informationskohomologin är ett exempel på ringmärkt topos. Multivariat k- Ömsesidig information förekommer i coboundaries uttryck, och deras försvinnande, relaterat till samcykeltillstånd, ger likvärdiga förutsättningar för statistiskt oberoende. Minima av ömsesidig information, även kallad synergi, ger upphov till intressanta oberoende konfigurationer analogt med homotopiska länkar. På grund av dess kombinatoriska komplexitet har endast det enkla delfallet av kohomologin och informationsstrukturen undersökts på data. Tillämpade på data kvantifierar dessa kohomologiska verktyg statistiska beroenden och oberoende, inklusive Markov-kedjor och villkorligt oberoende, i det multivariata fallet. I synnerhet generaliserar ömsesidig information korrelationskoefficient och kovarians till icke-linjära statistiska beroenden. Dessa tillvägagångssätt utvecklades oberoende och endast indirekt relaterade till beständighetsmetoder, men kan i det enkla fallet förstås grovt med hjälp av Hu Kuo Tin-satsen som etablerar en-till-en-överensstämmelse mellan ömsesidiga informationsfunktioner och ändlig mätbar funktion hos en uppsättning med korsningsoperator , för att konstruera Čech-komplex -skelettet. Informationskohomologi erbjuder en viss direkt tolkning och tillämpning i termer av neurovetenskap (neural sammansättningsteori och kvalitativ kognition), statistisk fysik och djupa neurala nätverk för vilka strukturen och inlärningsalgoritmen påtvingas av komplexet av slumpvariabler och informationskedjeregeln.

Persistenslandskap, introducerade av Peter Bubenik, är ett annorlunda sätt att representera streckkoder, mer mottagliga för statistisk analys. Persistenslandskapet beständig modul $M$ definieras som en funktion $\lambda :\mathbb {N} \times \mathbb {R} \to {\bar { \mathbb {R} }}$ , $\lambda (k,t):=\sup(m\ geq 0\mid \beta ^{tm,tm}\geq k)$ , där ${\bar {\mathbb {R} }}$ anger den förlängda reella linjen och $\beta ^{a,b}=\mathrm {dim} (\mathrm {im} (M(a\leq b)))$ . Utrymmet av beständighetslandskap är mycket trevligt: det ärver alla goda egenskaper för streckkodsrepresentation (stabilitet, enkel representation, etc.), men statistiska storheter kan lätt definieras, och några problem i Y. Mileyko et al.s arbete, t.ex. eftersom förväntningarnas icke-unikhet kan övervinnas. Effektiva algoritmer för beräkning med beständighetslandskap är tillgängliga. Ett annat tillvägagångssätt är att använda reviderad beständighet, vilket är bild-, kärn- och kokkärnbeständighet.

Ansökningar

Klassificering av applikationer

Det finns mer än ett sätt att klassificera tillämpningarna av TDA. Det kanske mest naturliga sättet är efter fält. En mycket ofullständig lista över framgångsrika applikationer inkluderar dataskelettisering, formstudie, grafrekonstruktion, bildanalys, material, progressionsanalys av sjukdomar, sensornätverk, signalanalys, kosmisk nät, komplext nätverk, fraktal geometri, viral evolution, spridning av smittor på nätverk , bakterieklassificering med hjälp av molekylär spektroskopi, hyperspektral avbildning i fysikalisk kemi, fjärranalys, funktionsval och tidiga varningstecken på finansiella krascher.

Ett annat sätt är att särskilja teknikerna av G. Carlsson,

den ena är studiet av homologiska invarianter av data en individuell datauppsättning, och den andra är användningen av homologiska invarianter i studien av databaser där själva datapunkterna har geometrisk struktur.

Egenskaper för TDA i applikationer

Det finns flera anmärkningsvärda intressanta egenskaper hos de senaste tillämpningarna av TDA:

Kombinera verktyg från flera grenar av matematiken . Förutom det uppenbara behovet av algebra och topologi har partiella differentialekvationer, algebraisk geometri, representationsteori, statistik, kombinatorik och Riemannsk geometri alla funnit användning i TDA.
Kvantitativ analys . Topologi anses vara mycket mjuk eftersom många begrepp är invarianta under homotopi. Men persistent topologi kan registrera födelsen (utseendet) och döden (försvinnandet) av topologiska egenskaper, så extra geometrisk information är inbäddad i den. Ett bevis i teorin är ett delvis positivt resultat på det unika med rekonstruktion av kurvor; två i tillämpningen är på den kvantitativa analysen av Fulleren-stabilitet och kvantitativ analys av självlikhet, separat.
Kort uthållighets roll . Kort uthållighet har också visat sig vara användbart, trots den vanliga uppfattningen att buller är orsaken till fenomenen. Detta är intressant för den matematiska teorin.

Ett av huvudområdena för dataanalys idag är maskininlärning . Några exempel på maskininlärning i TDA finns i Adcock et al. En konferens ägnas åt kopplingen mellan TDA och maskininlärning. För att kunna tillämpa verktyg från maskininlärning bör informationen som erhålls från TDA representeras i vektorform. Ett pågående och lovande försök är det uthållighetslandskap som diskuterats ovan. Ett annat försök använder begreppet persistensbilder. Ett problem med denna metod är dock förlusten av stabilitet, eftersom hårdstabilitetsteoremet beror på streckkodens representation.

Inverkan på matematik

Topologisk dataanalys och ihållande homologi har haft effekter på Morse-teorin ^{[ citat behövs ]} . Morseteorin har spelat en mycket viktig roll i teorin om TDA, inklusive beräkning. En del arbete i persistent homologi har utökat resultat om Morse-funktioner till att tämja funktioner eller till och med kontinuerliga funktioner [ ^{citat behövs ]} . Ett glömt resultat av R. Deheuvels långt innan uppfinningen av persistent homologi utökar Morse-teorin till alla kontinuerliga funktioner.

Ett färskt resultat är att kategorin Reeb-grafer motsvarar en viss klass av cosheaf. Detta motiveras av teoretiskt arbete i TDA, eftersom Reeb-grafen är relaterad till Morse-teorin och MAPPER är härledd från den. Beviset för detta teorem förlitar sig på interfolieringsavståndet.

Ihållande homologi är nära besläktad med spektralsekvenser . Speciellt tillåter algoritmen som bringar ett filtrerat komplex till dess $E_{p,q}^{r}$ form mycket snabbare beräkning av spektralsekvenser än standardproceduren för att beräkna grupper sida för sida. Sicksackbeständighet kan visa sig vara av teoretisk betydelse för spektrala sekvenser.

Se även

Vidare läsning

Kort introduktion

Lesnick, Michael (2013). "Studera formen på data med topologi" . Institutet för avancerade studier.
Källmaterial för topologisk dataanalys av Mikael Vejdemo-Johansson

Monografi

Oudot, Steve Y. (2015). Persistensteori: Från kogerrepresentationer till dataanalys . American Mathematical Society. ISBN 978-1-4704-2545-6 .

Videoföreläsning

Introduktion till beständig homologi och topologi för dataanalys , av Matthew Wright
The Shape of Data , av Gunnar Carlsson

Lärobok i topologi

Hatcher, Allen (2002). Algebraisk topologi . Cambridge University Press. ISBN 0-521-79540-0 . Tillgänglig för nedladdning
Edelsbrunner, Herbert; Harer, John (2010). Computational Topology: An Introduction . American Mathematical Society. ISBN 9780821849255 .
Elementary Applied Topology , av Robert Ghrist

Andra resurser för TDA

Applied Topology , av Stanford
Forskningsnätverk för tillämpad algebraisk topologi Arkiverad 2016-01-31 på Wayback Machine , av Institutet för matematik och dess tillämpningar
Topologisk kärninlärning: Diskret Morse-teori används för att koppla samman kärnmaskininlärning med topologisk dataanalys. https://www.researchgate.net/publication/327427685_Topological_Kernel_Learning