Analýza topologických dat - Topological data analysis

v aplikovaná matematika, topologická analýza dat (TDA) je přístup k analýze datových souborů pomocí technik z topologie. Extrakce informací z datových souborů, které jsou vysoce dimenzionální, neúplné a hlučné, je obecně náročná. TDA poskytuje obecný rámec pro analýzu takových dat způsobem, který je necitlivý na konkrétní údaje metrický vybrána a poskytuje snížení rozměrů a odolnost vůči hluku. Kromě toho to zdědí funkčnost, základní koncept moderní matematiky, z její topologické podstaty, která jí umožňuje přizpůsobit se novým matematickým nástrojům.

Počáteční motivací je studium tvaru dat. TDA se spojila algebraická topologie a další nástroje z čisté matematiky, které umožňují matematicky důkladné studium „tvaru“. Hlavním nástrojem je trvalá homologie, adaptace homologie na mračno bodů data. Trvalá homologie byla aplikována na mnoho typů dat napříč mnoha poli. Navíc jeho matematický základ má také teoretický význam. Díky jedinečným vlastnostem TDA je slibným mostem mezi topologií a geometrií.

Základní teorie

Intuice

Tento článek je tón nebo styl nemusí odrážet encyklopedický tón použitý na Wikipedii. Viz Wikipedia průvodce psaním lepších článků pro návrhy. (Ledna 2019) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

Základním předpokladem TDA je, že na tvaru záleží. Skutečná data ve vysokých dimenzích jsou téměř vždy řídká a mají tendenci mít relevantní nízko dimenzionální funkce. Jedním z úkolů TDA je poskytnout přesnou charakteristiku této skutečnosti. Ilustrativním příkladem je jednoduchý systém predátor-kořist řízený Rovnice Lotka – Volterra.^[1] Lze snadno pozorovat, že trajektorie systému tvoří uzavřený kruh ve stavovém prostoru. TDA poskytuje nástroje k detekci a kvantifikaci takového opakovaného pohybu.^[2]

Mnoho algoritmů pro analýzu dat, včetně těch, které se používají v TDA, vyžaduje výběr různých parametrů. Bez předchozích znalostí domény je obtížné zvolit správné shromažďování parametrů pro datovou sadu. Hlavní pohled na trvalá homologie je, že můžeme použít informace získané ze všech hodnot parametru. Tento vhled je samozřejmě snadno proveditelný; těžkou součástí je kódování tohoto obrovského množství informací do srozumitelné a snadno reprezentovatelné formy. V případě TDA existuje matematická interpretace, pokud jsou informace homologní skupinou. Obecně se předpokládá, že funkce, které přetrvávají pro širokou škálu parametrů, jsou „skutečné“ funkce. Funkce přetrvávající pouze v úzkém rozsahu parametrů se považují za šum, i když teoretické zdůvodnění je nejasné.^[3]

Raná historie

Předchůdci úplné koncepce trvalé homologie se objevovali postupně v průběhu času.^[4] V roce 1990 představil Patrizio Frosini velikostní funkci, která je ekvivalentní k 0. perzistentní homologii.^[5] Téměř o deset let později Vanessa Robins studoval obrazy homomorfismů vyvolaných inkluzí.^[6] Nakonec krátce nato Edelsbrunner et al. představil koncept trvalé homologie spolu s účinným algoritmem a jeho vizualizací jako perzistenční diagram.^[7] Carlsson a kol. přeformuloval počáteční definici a dal ekvivalentní vizualizační metodu zvanou persistence barcodes,^[8] tlumočení perzistence v jazyce komutativní algebry.^[9]

V algebraické topologii se vytrvalá homologie objevila prací Barannikova na Morseově teorii. Sada kritických hodnot hladké Morseovy funkce byla kanonicky rozdělena do dvojic „narození-smrt“, filtrované komplexy byly klasifikovány a vizualizace jejich invarianty, ekvivalentní perzistenčnímu diagramu a perzistenčnímu čárovému kódu, byla dána v roce 1994 Barannikovovou kanonickou formou.^[10]

Koncepty

Níže jsou uvedeny některé široce používané pojmy. Některé definice se mohou u jednotlivých autorů lišit.

A mračno bodů je často definován jako konečná množina bodů v nějakém euklidovském prostoru, ale může být považován za jakýkoli konečný metrický prostor.

The Čechův komplex mraku bodů je nerv z Pokrýt koulí o pevném poloměru kolem každého bodu v oblaku.

A modul perzistence ${displaystyle mathbb {U}}$ indexováno podle ${displaystyle mathbb {Z}}$ je vektorový prostor ${displaystyle U_ {t}}$ pro každého ${displaystyle tin mathbb {Z}}$a lineární mapa ${displaystyle u_ {t} ^ {s}: U_ {s} o U_ {t}}$ kdykoli ${displaystyle sleq t}$, takový, že ${displaystyle u_ {t} ^ {t} = 1}$ pro všechny ${displaystyle t}$ a ${displaystyle u_ {t} ^ {s} u_ {s} ^ {r} = u_ {t} ^ {r}}$ kdykoli ${displaystyle rleq sleq t.}$^[11] Ekvivalentní definicí je funktor z ${displaystyle mathbb {Z}}$ považována za částečně uspořádanou množinu do kategorie vektorových prostorů.

The skupina trvalé homologie ${displaystyle PH}$ mraku bodů je modul perzistence definovaný jako ${displaystyle PH_ {k} (X) = prod H_ {k} (X_ {r})}$, kde ${displaystyle X_ {r}}$ je Čechův komplex o poloměru ${displaystyle r}$ mraku bodů ${displaystyle X}$ a ${displaystyle H_ {k}}$ je skupina homologie.

A persistence barcode je multiset intervalů v ${displaystyle mathbb {R}}$a diagram perzistence je multiset bodů v ${displaystyle Delta}$(${displaystyle: = {(u, v) in mathbb {R} ^ {2} mid u, vgeq 0, uleq v}}$).

The Wassersteinova vzdálenost mezi dvěma diagramy perzistence ${displaystyle X}$ a ${displaystyle Y}$ je definován jako

$${displaystyle W_ {p} [L_ {q}] (X, Y): = inf _ {varphi: X o Y} vlevo [součet _ {xin X} Vert x-varphi (x) Vert _ {q} vpravo] ^ {1 / p}}$$

${displaystyle 1leq p, qleq infty}$

${displaystyle varphi}$

${displaystyle X}$

${displaystyle Y}$

The vzdálenost úzkého hrdla mezi ${displaystyle X}$ a ${displaystyle Y}$ je

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

${displaystyle p = infty}$

Základní vlastnost

Věta o struktuře

První klasifikační věta pro perzistentní homologii se objevila v roce 1994^[10] prostřednictvím Barannikovových kanonických forem. Klasifikační věta interpretující perzistenci v jazyce komutativní algebry se objevila v roce 2005:^[9] pro konečně vygenerovaný modul perzistence ${displaystyle C}$ s polem ${displaystyle F}$ koeficienty,

$${displaystyle H (C; F) simeq igoplus _ {i} x ^ {t_ {i}} cdot F [x] oplus vlevo (igoplus _ {j} x ^ {r_ {j}} cdot (F [x] / (x ^ {s_ {j}} cdot F [x])) ight).}$$

${displaystyle t_ {i}}$

${displaystyle r_ {j}}$

${displaystyle s_ {j}}$

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

Trvalá homologie je vizualizována čárovým kódem nebo diagramem stálosti. Čárový kód má kořeny v abstraktní matematice. Jmenovitě je kategorie konečných filtrovaných komplexů přes pole částečně jednoduchá. Libovolný filtrovaný komplex je izomorfní se svou kanonickou formou, přímým součtem jednorozměrných a dvourozměrných jednoduchých filtrovaných komplexů.

Stabilita

Stabilita je žádoucí, protože poskytuje odolnost proti hluku. Li ${displaystyle X}$ je jakýkoli prostor, který je homeomorfní se zjednodušeným komplexem, a ${displaystyle f, g: X o mathbb {R}}$ jsou neustále krotké^[13] funkce, pak vektorové prostory persistence ${displaystyle {H_ {k} (f ^ {- 1} ([0, r]))}}$ a ${displaystyle {H_ {k} (g ^ {- 1} ([0, r]))}}$ jsou definitivně prezentovány a ${displaystyle W_ {infty} (D (f), D (g)) leq lVert f-gVert _ {infty}}$, kde ${displaystyle W_ {infty}}$ odkazuje na úzkou vzdálenost^[14] a ${displaystyle D}$ je mapa, která využívá průběžnou krotkou funkci k perzistenčnímu diagramu ${displaystyle k}$-th homologie.

Pracovní postup

Základní pracovní postup v TDA je:^[15]

mračno bodů

${displaystyle o}$

vnořené komplexy

${displaystyle o}$

modul perzistence

${displaystyle o}$

čárový kód nebo diagram

1. Li ${displaystyle X}$ je mračno bodů, vyměňte ${displaystyle X}$ s vnořenou rodinou zjednodušené komplexy ${displaystyle X_ {r}}$ (například komplex Čech nebo Vietoris-Rips). Tento proces převádí mračno bodů na filtraci zjednodušených komplexů. Vezmeme-li homologii každého komplexu v této filtraci, získáme modul perzistence
   $${displaystyle H_ {i} (X_ {r_ {0}}) o H_ {i} (X_ {r_ {1}}) o H_ {i} (X_ {r_ {2}}) o cdots}$$

   
2. Aplikujte větu o struktuře a poskytněte parametrizovanou verzi Betti číslo, diagram vytrvalosti, nebo ekvivalentně čárový kód.

Graficky vzato,

Obvyklé použití perzistence v TDA ^[16]

Výpočet

První algoritmus pro všechna pole pro trvalou homologii v nastavení algebraické topologie popsal Barannikov^[10] prostřednictvím redukce do kanonické podoby maticemi s horními trojúhelníky. První algoritmus pro trvalou homologii ${displaystyle F_ {2}}$ byl dán Edelsbrunnerem a kol.^[7] Zomorodian a Carlsson poskytli první praktický algoritmus pro výpočet trvalé homologie ve všech oblastech.^[9] Kniha Edelsbrunnera a Harera poskytuje obecné vodítko pro výpočetní topologii.^[17]

Jednou z otázek, která vyvstává při výpočtu, je volba komplexu. The Čechův komplex a Vietoris – Rips komplex jsou na první pohled nejpřirozenější; jejich velikost však rychle roste s počtem datových bodů. Komplex Vietoris – Rips je upřednostňován před Čechovým komplexem, protože jeho definice je jednodušší a Čechův komplex vyžaduje další úsilí k definování v obecném konečném metrickém prostoru. Byly studovány účinné způsoby, jak snížit výpočetní náklady na homologii. Například komplex α a komplex svědků se používají ke zmenšení rozměru a velikosti komplexů.^[18]

Nedávno, Diskrétní Morseova teorie prokázal slib pro výpočetní homologii, protože může redukovat daný zjednodušující komplex na mnohem menší celulární komplex, který je homotopický k původnímu.^[19] Tuto redukci lze ve skutečnosti provést, protože komplex je konstruován pomocí teorie matroidů, což vede k dalšímu zvýšení výkonu.^[20] Další nedávný algoritmus šetří čas ignorováním tříd homologie s nízkou perzistencí.^[21]

K dispozici jsou různé softwarové balíčky, například javaPlex, Dionýsos, Perseus, PHAT, DIPHA, GUDHI, Ripser, a TDAstats. Srovnání mezi těmito nástroji provádí Otter et al.^[22] Giotto-tda je balíček Pythonu věnovaný integraci TDA do pracovního toku strojového učení pomocí a scikit-učit se API. Balíček R. TDA je schopen vypočítat nedávno vynalezené koncepty jako krajina a odhad vzdálenosti jádra.^[23] The Topologie ToolKit se specializuje na spojitá data definovaná na varietách nízké dimenze (1, 2 nebo 3), jak se obvykle nacházejí v vědecká vizualizace. Další balíček R, TDAstats, implementuje rychlou knihovnu C ++ Ripser pro výpočet trvalé homologie.^[24] Používá také všudypřítomné ggplot2 balíček pro generování reprodukovatelných, přizpůsobitelných vizualizací trvalé kvality v publikační kvalitě, konkrétně topologických čárových kódů a diagramů perzistence. Níže uvedený ukázkový kód uvádí příklad toho, jak Programovací jazyk R. lze použít k výpočtu trvalé homologie.

# nainstalujte balíček z CRANu a načtěte datové sadyinstall.packages(„TDAstats“)knihovna(„TDAstats“)data("unif2d")data(„circle2d“)# vypočítat trvalou homologii pro oba soubory datunif.phom <- vypočítat_homologii(unif2d)circ.phom <- vypočítat_homologii(circle2d)# vykreslete rovnoměrně distribuovaný mrak bodů jako diagram perzistenceplot_persist(unif.phom)# vykreslit mračno kruhových bodů jako topologický čárový kód# vidíme jednu trvalou lištu podle očekávání pro kruh (jeden 1 cyklus / smyčka)plot_barcode(circ.phom)

Diagram vytrvalosti vytvořený ukázkovým kódem (unif. 2D datová sada) pro sadu 100 bodů rovnoměrně rozložených v 2-rozměrném jednotkovém čtverci. Žádný z 0 cyklů ani 1 cyklů se nepovažuje za skutečný signál (žádný skutečně neexistuje v mračnu jednotkových čtvercových bodů). I když se zdá, že některé funkce přetrvávají, zaškrtnutí osy ukazují, že nejtrvalejší funkce přetrvává pro méně než 0,20 jednotek, což je relativně málo pro mračno bodů na čtverci jednotek.

Topologický čárový kód vytvořený vzorovým kódem (datová sada cir. 2D) pro sadu 100 bodů rovnoměrně rozložených po obvodu kruhu. Jediný dlouhý 1-rozměrný prvek v horní části čárového kódu představuje jediný 1-cyklus přítomný v kruhu.

Vizualizace

Přímo vizualizovat vysoce dimenzionální data není možné. Bylo vyvinuto mnoho metod pro extrakci nízkodimenzionální struktury ze souboru dat, jako je například analýza hlavních komponent a vícerozměrné škálování.^[25] Je však důležité si uvědomit, že samotný problém je nepředstavitelný, protože ve stejné datové sadě lze nalézt mnoho různých topologických rysů. Studie vizualizace prostorů vysokých rozměrů má tedy pro TDA zásadní význam, i když nutně nezahrnuje použití trvalé homologie. Byly však provedeny nedávné pokusy o použití trvalé homologie při vizualizaci dat.^[26]

Carlsson a kol. navrhli obecnou metodu nazvanou MAPPER.^[27] Zdědil myšlenku Serre, že krytina zachovává homotopii.^[28] Zobecněná formulace MAPPER je následující:

Nechat ${displaystyle X}$ a ${displaystyle Z}$ být topologické prostory a nechat ${displaystyle f: X o Z}$ být spojitá mapa. Nechat ${displaystyle mathbb {U} = {U_ {alpha}} _ {alfa v A}}$ být konečnou otevřenou pokrývkou ${displaystyle Z}$. Výstup MAPPERU je nervem stahovacího krytu ${extstyle M (mathbb {U}, f): = N (f ^ {- 1} (mathbb {U}))}$, kde je každá preimage rozdělena na připojené komponenty.^[26] Jedná se o velmi obecný koncept, jehož grafem je Reeb ^[29] a sloučení stromů jsou zvláštní případy.

To není zcela původní definice.^[27] Carlsson a kol. Vybrat ${displaystyle Z}$ být ${displaystyle mathbb {R}}$ nebo ${displaystyle mathbb {R} ^ {2}}$a zakryjte jej otevřenými množinami tak, aby se protínaly maximálně dvě.^[3] Toto omezení znamená, že výstup je ve formě a komplexní síť. Protože topologie mračna konečných bodů je triviální, shlukovací metody (například jednoduché propojení ) se používají k výrobě analogu připojených sad v preimage ${displaystyle f ^ {- 1} (U)}$ když je MAPPER aplikován na skutečná data.

Matematicky vzato je MAPPER variantou Reebový graf. Pokud ${extstyle M (mathbb {U}, f)}$ je nanejvýš jednorozměrný, pak pro každý ${displaystyle igeq 0}$,

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

Tři úspěšné aplikace MAPPER lze nalézt v Carlsson et al.^[32] Komentář k aplikacím v tomto článku od J. Curryho je, že „společným rysem zájmu o aplikace je přítomnost světlic nebo úponků“.^[33]

K dispozici je bezplatná implementace MAPPER online napsal Daniel Müllner a Aravindakshan Babu. MAPPER také tvoří základ Ayasdi AI platforma.

Vícerozměrná vytrvalost

Multidimenzionální vytrvalost je pro TDA důležitá. Koncept vzniká jak v teorii, tak v praxi. První vyšetřování vícerozměrné perzistence bylo počátkem vývoje TDA,^[34] a je jedním ze zakládajících dokumentů TDA.^[9] První aplikací, která se objevila v literatuře, je metoda pro srovnání tvarů, podobná vynálezu TDA.^[35]

Definice n-dimenzionální modul perzistence v ${displaystyle mathbb {R} ^ {n}}$ je^[33]

• vektorový prostor ${displaystyle V_ {s}}$ je přiřazen ke každému bodu v ${displaystyle s = (s_ {1}, ..., s_ {n})}$
• mapa ${displaystyle ho _ {s} ^ {t}: V_ {s} o V_ {t}}$ je přiřazeno, pokud ${displaystyle sleq t}$(${displaystyle s_ {i} leq t_ {i}, i = 1, ..., n)}$
• mapy uspokojí ${displaystyle ho _ {r} ^ {t} = ho _ {s} ^ {t} circ ho _ {r} ^ {s}}$ pro všechny ${displaystyle rleq sleq t}$

Za zmínku stojí, že o definici vícerozměrné perzistence se vedou spory.^[33]

Jednou z výhod jednorozměrné perzistence je její reprezentovatelnost pomocí diagramu nebo čárového kódu. Diskrétní úplné invarianty modulů vícerozměrné perzistence však neexistují.^[36] Hlavním důvodem je to, že struktura sběru nerozložitelných položek je extrémně komplikována Gabrielova věta v teorii toulcových reprezentací,^[37] i když konečně n-dimenzionální modul perzistence lze jednoznačně rozložit na přímý součet nerozložitelných kvůli Krull-Schmidtově teorému.^[38]

Bylo však zjištěno mnoho výsledků. Carlsson a Zomorodian představili hodnost neměnná ${displaystyle ho _ {M} (u, v)}$, definovaný jako ${displaystyle ho _ {M} (u, v) = mathrm {rank} (x ^ {u-v}: M_ {u} o M_ {v})}$, ve kterém ${displaystyle M}$ je konečně generovaný modul třídy n. V jedné dimenzi je to ekvivalent čárového kódu. V literatuře je invariant hodnosti často označován jako perzistentní čísla Betti (PBN).^[17] V mnoha teoretických pracích autoři použili omezenější definici, analogii z perlevence množiny podúrovní. Konkrétně persistence Bettiho čísla funkce ${displaystyle f: X o mathrm {R} ^ {k}}$ jsou dány funkcí ${displaystyle eta _ {f}: Delta ^ {+} o mathrm {N}}$, přičemž každý ${displaystyle (u, v) v Delta ^ {+}}$ na ${displaystyle eta _ {f} (u, v): = mathrm {rank} (H (X (fleq u) o H (X (fleq v)))}$, kde ${displaystyle Delta ^ {+}: = {(u, v) in mathbb {R} imes mathbb {R}: uleq v}}$ a ${displaystyle X (fleq u): = {xin X: f (x) leq u}}$.

Některé základní vlastnosti zahrnují monotónnost a diagonální skok.^[39] Trvalá čísla Betti budou konečná, pokud ${displaystyle X}$ je kompaktní a lokálně stahovatelný podprostor o ${displaystyle mathbb {R} ^ {n}}$.^[40]

Použitím foliační metody lze k-dim PBN rozložit na rodinu 1-dim PBN pomocí dedukce rozměrů.^[41] Tato metoda také vedla k důkazu, že vícedimenzionální PBN jsou stabilní.^[42] K diskontinuitám PBN dochází pouze v bodech ${displaystyle (u, v) (uleq v)}$ kde buď ${displaystyle u}$ je nesouvislý bod ${displaystyle ho _ {M} (hvězda, v)}$ nebo ${displaystyle v}$ je nesouvislý bod ${displaystyle ho (u, star)}$ za předpokladu, že ${displaystyle fin C ^ {0} (X, mathrm {R} ^ {k})}$ a ${displaystyle X}$ je kompaktní, triangulovatelný topologický prostor.^[43]

Persistentní prostor, zobecnění perzistentního diagramu, je definován jako multiset všech bodů s multiplicitou větší než 0 a úhlopříčkou.^[44] Poskytuje stabilní a úplné zastoupení PBN. Probíhající práce Carlssona a kol. se pokouší poskytnout geometrickou interpretaci perzistentní homologie, která by mohla poskytnout poznatky o tom, jak kombinovat teorii strojového učení s analýzou topologických dat.^[45]

První praktický algoritmus pro výpočet vícerozměrné stálosti byl vynalezen velmi brzy.^[46] Poté bylo navrženo mnoho dalších algoritmů založených na takových koncepcích, jako je diskrétní morseova teorie^[47] a konečný odhad vzorku.^[48]

Další perzistence

Standardní paradigma v TDA se často označuje jako dílčí vytrvalost. Kromě vícerozměrné vytrvalosti bylo pro rozšíření tohoto zvláštního případu provedeno mnoho prací.

Cikcak vytrvalost

Nenulové mapy v modulu perzistence jsou omezeny vztahem předobjednávky v kategorii. Matematici však zjistili, že jednomyslnost směru není pro mnoho výsledků nezbytná. „Filozofickým bodem je, že teorie rozkladu grafových reprezentací je poněkud nezávislá na orientaci okrajů grafu“.^[49] Cikcaková vytrvalost je důležitá z teoretické stránky. Příklady uvedené v recenzním článku Carlssona pro ilustraci důležitosti funkcionality sdílejí některé z jejích funkcí.^[3]

Rozšířená perzistence a perzistence sady úrovní

Některé pokusy spočívají ve ztrátě přísnějšího omezení funkce.^[50] Přečtěte si prosím Kategorizace a cosheaves a Dopad na matematiku sekce pro více informací.

Je přirozené rozšířit perzistenční homologii na další základní pojmy v algebraické topologii, jako je kohomologie a relativní homologie / kohomologie.^[51] Zajímavou aplikací je výpočet kruhových souřadnic pro soubor dat prostřednictvím první perzistentní kohomologické skupiny.^[52]

Kruhová perzistence

Normální perzistenční homologie studuje funkce se skutečnou hodnotou. Kruhová mapa může být užitečná, „slibuje teorie perzistence pro mapy s kruhovou hodnotou, že bude hrát roli u některých vektorových polí, stejně jako standardní teorie perzistence pro skalární pole“, jak uvedl D. Burghelea et al.^[53] Hlavní rozdíl spočívá v tom, že buňky Jordan (formátem velmi podobné formátu Jordan bloky v lineární algebře) jsou netriviální ve funkcích s kruhovou hodnotou, které by byly v reálném případě nulové, a kombinace s čárovými kódy dává invarianty krotké mapy za mírných podmínek.^[53]

Dvě techniky, které používají, jsou Morse-Novikovova teorie^[54] a teorie reprezentace grafů.^[55] Novější výsledky lze nalézt v D. Burghelea et al.^[56] Například požadavek na krotkost lze nahradit mnohem slabším stavem, kontinuálním.

Perzistence s kroucením

Důkaz o konstrukční větě se opírá o pole základní domény, takže nebylo provedeno mnoho pokusů o perzistenční homologii s torzí. Frosini na tomto konkrétním modulu definoval pseudometrii a prokázal jeho stabilitu.^[57] Jednou z jeho novinek je, že definování metriky nezávisí na nějaké teorii klasifikace.^[58]

Kategorizace a cosheaves

Jedna výhoda teorie kategorií je jeho schopnost pozvednout konkrétní výsledky na vyšší úroveň a ukázat vztahy mezi zdánlivě nespojenými objekty. Bubenik a kol.^[59] nabízí krátké představení teorie kategorií přizpůsobené pro TDA.

Teorie kategorií je jazykem moderní algebry a byla široce používána při studiu algebraické geometrie a topologie. Bylo poznamenáno, že „klíčové pozorování ^[9] je to, že perzistenční diagram produkovaný ^[7] záleží pouze na algebraické struktuře nesené tímto diagramem. “^[60] Ukázalo se, že použití teorie kategorií v TDA je plodné.^[59][60]

V návaznosti na poznámky učiněné v Bubenik et al.,^[60] the kategorie indexování ${extstyle P}$ je jakýkoli předobjednaná sada (ne nutně ${displaystyle mathbb {N}}$ nebo ${displaystyle mathbb {R}}$), cílová kategorie ${displaystyle D}$ je libovolná kategorie (místo běžně používaných ${extstyle mathrm {Vect} _ {mathbb {F}}}$), a funktory ${extstyle P o D}$ se nazývají generalizované moduly perzistence v ${displaystyle D}$, přes ${extstyle P}$.

Jednou z výhod používání teorie kategorií v TDA je jasnější pochopení konceptů a objevení nových vztahů mezi důkazy. Pro ilustraci si vezměte dva příklady. Pochopení korespondence mezi prokládáním a párováním má obrovský význam, protože párování bylo metodou používanou na začátku (modifikovanou z Morseovy teorie). Souhrn prací lze nalézt ve Vin de Silva et al.^[61] Mnoho vět lze dokázat mnohem snadněji v intuitivnějším prostředí.^[58] Dalším příkladem je vztah mezi konstrukcí různých komplexů z mračen bodů. Již dlouho si všimli, že komplexy Čech a Vietoris-Rips jsou příbuzné. Konkrétně ${displaystyle V_ {r} (X) podmnožina C _ {{sqrt {2}} r} (X) podmnožina V_ {2r} (X)}$.^[62] Základní vztah mezi Cechovými a Ripsovými komplexy lze mnohem jasněji vidět v kategorickém jazyce.^[61]

Jazyk teorie kategorií také pomáhá sesílat výsledky v termínech rozpoznatelných širší matematické komunitě. Vzdálenost úzkého hrdla je v TDA široce používána kvůli výsledkům stability s ohledem na vzdálenost úzkého hrdla.^[11][14] Ve skutečnosti je prokládací vzdálenost koncový objekt v kategorii poset stabilních metrik na vícerozměrných modulech perzistence v a hlavní pole.^[58][63]

Snopy, ústřední pojem v moderní algebraická geometrie, jsou skutečně spojené s teorií kategorií. Zhruba řečeno, snopy jsou matematickým nástrojem pro pochopení toho, jak místní informace určují globální informace. Justin Curry považuje perzistenci na úrovni úrovní za studium vlákna spojitých funkcí. Objekty, které studuje, jsou velmi podobné těm od MAPPERA, ale s teorií svazků jako teoretickým základem.^[33] Ačkoli žádný průlom v teorii TDA dosud nepoužil teorii svazků, je slibný, protože v algebraické geometrii existuje mnoho krásných vět o teorii svazků. Například přirozenou teoretickou otázkou je, zda různé metody filtrace vedou ke stejnému výstupu.^[64]

Stabilita

Stabilita má pro analýzu dat zásadní význam, protože skutečná data nesou zvuky. Použitím teorie kategorií Bubenik et al. rozlišovali mezi měkkými a tvrdými větami o stabilitě a dokázali, že měkké případy jsou formální.^[60] Obecně platí, že obecný pracovní postup TDA je

data

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

modul topologické perzistence

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

modul algebraické perzistence

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

diskrétní invariant

Věta o měkké stabilitě to potvrzuje ${displaystyle HF}$ je Lipschitz kontinuální, a tvrdá věta o stabilitě to tvrdí ${displaystyle J}$ je Lipschitz kontinuální.

Vzdálenost úzkého hrdla je v TDA široce používána. Věta o izometrii tvrdí, že prokládací vzdálenost ${displaystyle d_ {I}}$ se rovná vzdálenosti úzkého místa.^[58] Bubenik a kol. abstrahovali definici na definici mezi funktory ${displaystyle F, G: P o D}$ když ${extstyle P}$ je vybaven sublineární projekcí nebo superlineární rodinou, ve které stále zůstává pseudometrická.^[60] Vzhledem k velkolepým postavám prokládané vzdálenosti,^[65] zde uvádíme obecnou definici vzdálenosti prokládání (namísto první zavedené):^[11] Nechat ${displaystyle Gamma, Kin mathrm {Trans_ {P}}}$ (funkce z ${extstyle P}$ na ${extstyle P}$ který je monotónní a vyhovuje ${displaystyle xleq Gamma (x)}$ pro všechny ${extstyle xin P}$). A ${displaystyle (Gamma, K)}$- prokládání mezi F a G sestává z přirozených transformací ${displaystyle varphi: FRightarrow GGamma}$ a ${displaystyle psi: GRightarrow FK}$, takový, že ${displaystyle (psi Gamma) = varphi Feta _ {KGamma}}$ a ${displaystyle (varphi Gamma) = psi Geta _ {Gamma K}}$.

Dva hlavní výsledky jsou^[60]

• Nechat ${extstyle P}$ být předobjednaná množina s sublineární projekcí nebo superlineární rodinou. Nechat ${extstyle H: D o E}$ být funktorem mezi libovolnými kategoriemi ${extstyle D, E}$. Pak pro kterékoli dva funktory ${extstyle F, G: P o D}$, my máme ${extstyle d_ {I} (HF, HG) leq d_ {I} (F, G)}$.
• Nechat ${extstyle P}$ být poset metrického prostoru ${extstyle Y}$ , ${extstyle X}$ být topologickým prostorem. A nechte${extstyle f, g: X o Y}$ (nemusí být nutně spojité) být funkcemi a ${extstyle F, G}$ být odpovídajícím diagramem perzistence. Pak ${displaystyle d_ {I} (F, G) leq d_ {infty} (f, g): = sup _ {xin X} d_ {Y} (f (x), g (x))}$.

Tyto dva výsledky shrnují mnoho výsledků týkajících se stability různých modelů perzistence.

Teorém o stabilitě vícerozměrné perzistence najdete v podsekci perzistence.

Věta o struktuře

Věta o struktuře má pro TDA zásadní význam; jak poznamenal G. Carlsson, „to, co činí homologii užitečnou jako diskriminátor mezi topologickými prostory, je skutečnost, že existuje klasifikační věta pro konečně generované abelianské skupiny.“^[3] (viz základní věta o konečně generovaných abelianských skupinách ).

Hlavním argumentem použitým v důkazu věty o původní struktuře je standard věta o struktuře pro konečně generované moduly nad hlavní ideální doménou.^[9] Tento argument však selže, pokud je sada indexování ${displaystyle (mathbb {R}, leq)}$.^[3]

Obecně platí, že ne každý modul perzistence lze rozložit na intervaly.^[66] Bylo učiněno mnoho pokusů o uvolnění omezení věty o původní struktuře.^{[je zapotřebí objasnění ]} Případ bodových modulů konečně-dimenzionální perzistence indexovaných lokálně konečnou podmnožinou ${displaystyle mathbb {R}}$ je řešen na základě práce Webba.^[67] Nejpozoruhodnější výsledek je Crawley-Boevey, který vyřešil případ ${displaystyle mathbb {R}}$. Crawley-Boeveyova věta uvádí, že jakýkoli bodově konečný rozměrný modul perzistence je přímým součtem intervalových modulů.^[68]

Abychom porozuměli definici jeho věty, je třeba zavést některé koncepty. An interval v ${displaystyle (mathbb {R}, leq)}$ je definována jako podmnožina ${displaystyle Isubset mathbb {R}}$ mít vlastnost, že pokud ${displaystyle r, tin I}$ a pokud existuje ${displaystyle sin mathbb {R}}$ takhle ${displaystyle rleq sleq t}$, pak ${displaystyle sin I}$ také. An intervalový modul ${displaystyle k_ {I}}$ přiřadí každému prvku ${displaystyle sin I}$ vektorový prostor ${displaystyle k}$ a přiřadí nulový vektorový prostor prvkům v ${displaystyle mathbb {R} setminus I}$. Všechny mapy ${displaystyle ho _ {s} ^ {t}}$ jsou nulová mapa, pokud ${displaystyle s, tin I}$ a ${displaystyle sleq t}$, v jakém případě ${displaystyle ho _ {s} ^ {t}}$ je mapa identity.^[33] Intervalové moduly jsou nerozložitelné.^[69]

Přestože je výsledek Crawley-Boevey velmi silné věty, stále se nevztahuje na případ q-tame.^[66] Modul perzistence je q-krotit pokud je hodnost ${displaystyle ho _ {s} ^ {t}}$ je konečný pro všechny ${displaystyle sleq t}$. Existují příklady modulů persistence q-tame, které nejsou bodově konečné.^[70] Ukázalo se však, že věta o podobné struktuře stále platí, pokud jsou odstraněny funkce, které existují pouze při jedné hodnotě indexu.^[69] To platí, protože nekonečné dimenzionální části při každé hodnotě indexu nepřetrvávají kvůli podmínce konečné pozice.^[71] Formálně pozorovatelná kategorie ${displaystyle mathrm {Ob}}$ je definován jako ${displaystyle mathrm {Pers} / mathrm {Eph}}$, ve kterém ${displaystyle mathrm {Eph}}$ označuje celou podkategorii ${displaystyle mathrm {Pers}}$ jejichž objekty jsou pomíjivé moduly (${displaystyle ho _ {s} ^ {t} = 0}$ kdykoli ${displaystyle s$).^[69]

Všimněte si, že zde uvedené rozšířené výsledky se nevztahují na perzistenci cikcaku, protože analoga modulu perzistence cikcaku přes ${displaystyle mathbb {R}}$ není okamžitě zřejmé.

Statistika

Reálná data jsou vždy konečná, a proto jejich studie vyžaduje, abychom vzali v úvahu stochasticitu. Statistická analýza nám dává možnost oddělit skutečné vlastnosti dat od artefaktů zavedených náhodným šumem. Trvalá homologie nemá žádný vlastní mechanismus k rozlišení mezi prvky s nízkou pravděpodobností a vlastnostmi s vysokou pravděpodobností.

Jedním ze způsobů, jak aplikovat statistiku na analýzu topologických dat, je studium statistických vlastností topologických vlastností mračen bodů. Studium náhodných zjednodušených komplexů nabízí určitý pohled na statistickou topologii. K. Turner a kol.^[72] nabízí shrnutí práce v tomto duchu.

Druhým způsobem je studium rozdělení pravděpodobnosti v prostoru perzistence. Prostor vytrvalosti ${displaystyle B_ {infty}}$ je ${displaystyle coprod _ {n} B_ {n} / {acksim}}$, kde ${displaystyle B_ {n}}$ je prostor všech čárových kódů obsahujících přesně ${displaystyle n}$ intervaly a ekvivalence jsou ${displaystyle {[x_ {1}, y_ {1}], [x_ {2}, y_ {2}], ldots, [x_ {n}, y_ {n}]} acksim {[x_ {1}, y_ {1}], [x_ {2}, y_ {2}], ldots, [x_ {n-1}, y_ {n-1}]}}$ -li ${displaystyle x_ {n} = y_ {n}}$.^[73] Tento prostor je poměrně komplikovaný; například není pod metrikou úzkého místa úplná. První pokus o jeho studium provedli Y. Mileyko a kol.^[74] Prostor perzistence diagramů ${displaystyle D_ {p}}$ v jejich příspěvku je definován jako

$${displaystyle D_ {p}: = left {dmid sum _ {xin d} left (2inf _ {yin Delta} lVert x-yVert ight) ^ {p}$$

${displaystyle Delta}$

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

${displaystyle D_ {p}}$

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

Třetím způsobem je uvažovat přímo o kohomologii pravděpodobnostního prostoru nebo statistických systémů, která se nazývá informační struktury a která v zásadě spočívá v trojici (${displaystyle Omega, Pi, P}$), ukázkový prostor, náhodné proměnné a zákony pravděpodobnosti ^{[78] [79]}. Náhodné proměnné jsou považovány za oddíly n atomových pravděpodobností (vnímáno jako pravděpodobnost (n-1) -simplex, ${displaystyle | Omega | = n}$) na mřížce oddílů (${displaystyle Pi _ {n}}$). Náhodné proměnné nebo moduly měřitelných funkcí poskytují komplexy řetězců, zatímco hranice je považována za obecnou homologickou algebru, kterou poprvé objevil Hochschild s levou akcí provádějící akci kondicionování. První podmínka cyklu odpovídá pravidlu řetězení entropie, což umožňuje jednoznačně odvodit až do multiplikativní konstanty, Shannonova entropie jako první třída cohomologie. Úvaha o deformované levé akci zobecňuje rámec na Tsallisovy entropie. Informační kohomologie je příkladem prstencových toposů. Vícerozměrný k-Vzájemné informace objevují se ve výrazech coboundaries a jejich mizení, související s podmínkou cyklu, poskytuje rovnocenné podmínky pro statistickou nezávislost ^[80]. Minima vzájemných informací, nazývaná také synergie, vede k zajímavým konfiguracím nezávislosti analogickým s homotopickými vazbami. Vzhledem ke své kombinatorické složitosti byl na datech zkoumán pouze zjednodušený podskupina kohomologie a informační struktury. Tyto cohomologické nástroje aplikované na data kvantifikují statistické závislosti a nezávislosti, včetně Markovovy řetězy a podmíněná nezávislost, v případě více proměnných ^[81]. Zejména se vzájemné informace zobecňují korelační koeficient a kovariance k nelineárním statistickým závislostem. Tyto přístupy byly vyvinuty nezávisle a pouze nepřímo související s metodami perzistence, ale lze je zhruba pochopit v jednoduchém případě pomocí věty Hu Kuo Tin, která stanoví vzájemnou korespondenci mezi funkcemi vzájemných informací a konečnou měřitelnou funkcí množiny s operátorem průniku , postavit Čechův komplex kostra. Informační kohomologie nabízí určitou přímou interpretaci a aplikaci z hlediska neurovědy (teorie neurální sestavy a kvalitativní poznání ^[82]), statistická fyzika a hluboká neuronová síť, pro které je struktura a algoritmus učení uložen komplexem náhodných proměnných a pravidlem informačního řetězce ^[83].

Persistence landscapes, introduced by Peter Bubenik, are a different way to represent barcodes, more amenable to statistical analysis.^[84] The persistence landscape of a persistent module ${displaystyle M}$ is defined as a function ${displaystyle lambda :mathbb {N} imes mathbb {R} o { ar {mathbb {R} }}}$, ${displaystyle lambda (k,t):=sup(mgeq 0mid eta ^{t-m,t-m}geq k)}$, kde ${displaystyle { ar {mathbb {R} }}}$ označuje prodloužená skutečná čára a ${displaystyle eta ^{a,b}=mathrm {dim} (mathrm {im} (M(aleq b)))}$. The space of persistence landscapes is very nice: it inherits all good properties of barcode representation (stability, easy representation, etc.), but statistical quantities can be readily defined, and some problems in Y. Mileyko et al.'s work, such as the non-uniqueness of expectations,^[74] can be overcome. Effective algorithms for computation with persistence landscapes are available.^[85] Another approach is to use revised persistence, which is image, kernel and cokernel persistence.^[86]

Aplikace

Classification of applications

More than one way exists to classify the applications of TDA. Perhaps the most natural way is by field. A very incomplete list of successful applications includes ^[87] data skeletonization,^[88] shape study,^[89] graph reconstruction,^{[90][91][92] [93][94]}image analysis,^[95][96] materiál,^[97] progression analysis of disease,^[98][99] sensor network,^[62] signal analysis,^[100] cosmic web,^[101] complex network,^{[102][103][104][105]} fractal geometry,^[106] viral evolution,^[107] propagation of contagions on networks,^[108] bacteria classification using molecular spectroscopy,^[109] hyperspectral imaging in physical-chemistry ^[110] and remote sensing.^[111]

Another way is by distinguishing the techniques by G. Carlsson,^[73]

one being the study of homological invariants of data one individual data sets, and the other is the use of homological invariants in the study of databases where the data points themselves have geometric structure.

Characteristics of TDA in applications

There are several notable interesting features of the recent applications of TDA:

1. Combining tools from several branches of mathematics. Besides the obvious need for algebra and topology, partial differential equations,^[112] algebraic geometry,^[36] representation theory,^[49] statistics, combinatorics, and Riemannian geometry^[71] have all found use in TDA.
2. Kvantitativní analýza. Topology is considered to be very soft since many concepts are invariant under homotopy. However, persistent topology is able to record the birth (appearance) and death (disappearance) of topological features, thus extra geometric information is embedded in it. One evidence in theory is a partially positive result on the uniqueness of reconstruction of curves;^[113] two in application are on the quantitative analysis of Fullerene stability and quantitative analysis of sebepodobnost, separately.^[106][114]
3. The role of short persistence. Short persistence has also been found to be useful, despite the common belief that noise is the cause of the phenomena.^[115] This is interesting to the mathematical theory.

One of the main fields of data analysis today is strojové učení. Some examples of machine learning in TDA can be found in Adcock et al.^[116] A konference is dedicated to the link between TDA and machine learning. In order to apply tools from machine learning, the information obtained from TDA should be represented in vector form. An ongoing and promising attempt is the persistence landscape discussed above. Another attempt uses the concept of persistence images.^[117] However, one problem of this method is the loss of stability, since the hard stability theorem depends on the barcode representation.

Impact on mathematics

Topological data analysis and persistent homology have had impacts on Morseova teorie. Morse theory has played a very important role in the theory of TDA, including on computation. Some work in persistent homology has extended results about Morse functions to tame functions or, even to continuous functions. A forgotten result of R. Deheuvels long before the invention of persistent homology extends Morse theory to all continuous functions.^[118]

One recent result is that the category of Reeb graphs is equivalent to a particular class of cosheaf.^[119] This is motivated by theoretical work in TDA, since the Reeb graph is related to Morse theory and MAPPER is derived from it. The proof of this theorem relies on the interleaving distance.

Persistent homology is closely related to spektrální sekvence.^{[120] [121]} In particular the algorithm bringing a filtered complex to its canonical form^[10] permits much faster calculation of spectral sequences than the standard procedure of calculating ${displaystyle E_{p,q}^{r}}$ groups page by page. Zigzag persistence may turn out to be of theoretical importance to spectral sequences.

Viz také

• Snížení rozměrů
• Dolování dat
• Počítačové vidění
• Výpočetní topologie
• Diskrétní Morseova teorie
• Analýza tvaru (digitální geometrie)
• Size theory
• Algebraická topologie

Reference

Další čtení

Stručný úvod

• Studium tvaru dat pomocí topologie od Michaela Lesnicka
• Zdrojový materiál pro analýzu topologických dat Mikael Vejdemo-Johansson

Monografie

• Teorie vytrvalosti: Od reprezentace toulce po analýzu dat Steve Oudot

Video přednáška

• Úvod do persistentní homologie a Topologie pro analýzu dat, Matthew Wright
• Tvar dat Gunnar Carlsson

Učebnice topologie

• Algebraická topologie, Allen Hatcher
• Výpočetní topologie: Úvod, Herbert Edelsbrunner a John L. Harer
• Elementární aplikovaná topologie autor: Robert Ghrist

Další zdroje TDA

• Aplikovaná topologie, Stanford
• Síť pro výzkum aplikované algebraické topologie , Ústavem pro matematiku a jeho aplikace
• Topologické učení jádra: Diskrétní Morseova teorie se používá k propojení strojového učení jádra s analýzou topologických dat. https://www.researchgate.net/publication/327427685_Topological_Kernel_Learning