Menu

Topologická analýza dat jako cesta k přesnějším výsledkům

11. března 2019/Andrea Rozhoňová, Zuzana Maruniaková

Přečtěte si, jak bychom díky topologické analýze dat mohli dospět k přesnějším výsledkům oproti klasickým metodám datové vědy. V článku se zaměříme na nové topologické přístupy pro učení bez učitele u redukce dimenze, vnořování slov a shlukování.

Inspirováno přednáškou Topological Approaches for Unsupervised Learning od Lelanda McInnese na Machine Learning Prague 2019.

Hlavní výhody topologického přístupu

Topologická analýza dat se řadí mezi relativně nové oblasti výzkumu. Snaží se aplikovat silné nástroje algebraické topologie a zaobírat se praktickými problémy z oblasti data science. Těmito oblastmi je redukce dimenzevnořování slov a shlukování.

Začněme krátkým vysvětlením, co topologie vlastně znamená. Vycházejme z myšlenky, že u hodně geometrických úloh nezáleží ani tak na tvaru objektu, ale naopak na vztazích mezi jednotlivými objekty. Topologický prostor se tak vyskytuje v mnoha matematických odvětvích a lze ho nazvat sjednocující disciplínou matematiky. Obecná topologie studuje některé vlastnosti prostorů a algebraická topologie využívá algebru, zejména grupy určené ke zkoumání topologických prostorů a zobrazení mezi nimi.

Ukazuje se totiž, že topologický přístup přináší podobné výsledky jako tradiční metody strojového učení. Za hlavní výhodu se považuje fakt, že při vytváření výsledků zůstanou zachovány vnitřní struktury systémů – ty nám poskytují další důležité informace, které můžeme využít při optimalizaci algoritmu.

Téměř všechny zmíněné oblasti využití topologického přístupu v Gauss Algorithmic často používáme. Ne vždy ale nastanou ideální podmínky, kdy máme k dispozici dostatek dat a kdy jsou data řádně anotovaná. Kvůli tomu bohužel klasické metody, jako například t-SNE, PCA, FastText nebo K-means, neumožňují dosáhnout tak přesných výsledků, jak bychom potřebovali. Nový pohled na celou problematiku, který topologie nabízí, by to mohl zlepšit.

Teoretický úvod

Na úvod je důležité ujasnit si pár základních pojmů, které se v oblasti topologických struktur vyskytují. První z nich je simplex, který se dá interpretovat jako n-rozměrné zovšeobecnění trojúhelníku. Pro potřeby našeho článku postačí intuitivní představa o tom, co simplex představuje.

Příklady simplexů
Obrázek č.1: Příklady simplexů (převzato z prezentace Lelanda McInnese, https://slideslive.com/38913519)

0-simplex představuje bod, 1-simplex pak úsečku, na obrázku vidíte 2-simplex neboli trojúhelník, 3-simplex jako čtyřstěn atd. Simplexy je možné spojovat do tzv. simpliciálních komplexů a toto propojování má určitá pravidla. Opět by nám měla stačit intuitivní představa o propojování, kterou můžeme popsat následujícím obrázkem.

Simpliciální komplex
Obrázek č. 2: Simpliciální komplex (převzato z prezentace Lelanda McInnese, https://slideslive.com/38913519)

Přemýšlejme nyní o okolí bodů popisujících křivku. Pokud mezi otevřenými okolími existuje průnik, pak spojíme tyto body tak, aby tvořily simplex (Nerve theorem).

Ukázka topologické struktury
Obrázek č. 3: Ukázka topologické struktury (převzato z prezentace Lelanda McInnese, https://slideslive.com/38913519)

Na obrázku si můžeme všimnout, že mezi jednotlivými otevřenými okolími, které nemají společný průnik, vznikají nepropojené části vlivem jejich nerovnoměrného rozložení. Podobné situace řeší topologie složitými topologickými strukturami, teorií kategorií a fuzzy přístupem.

Topologický přístup pro učení bez učitele nachází uplatnění v následujích třech oblastech: redukce dimenze, vnořování slov a shlukování – ty si nyní blíže rozebereme. Nejdříve u nich popíšeme klasické metody, poté představíme nové pohledy založené na topologii, která respektuje vnitřní vztahy struktur.

Redukce dimenze

Redukce dimenze se využívá za účelem snížení rozměru dat pro jednodušší interpretaci, vizualizaci a případně pro přípravu k jejich dalšímu zpracování. Z klasických metod se zpravidla používá například analýza hlavních komponent nebo t-SNE.

Při metodě PCA (Principal Component Analysis) je cílem najít množinu lineárních kombinací z množiny pozorování tak, abychom zachovali co nejvíce vlastností a zároveň došlo k redukci dimenze. Díky tomu můžeme daný problém zkoumat v podprostoru s menší dimenzí.

Metoda t-SNE se řadí mezi nelineární. V porovnání s PCA není založená na hledání největšího rozptylu. Metoda využívá matici podobnosti, která reprezentuje podobnost dvou bodů v prostoru, z něhož vycházíme. Dále se dobře optimalizuje, protože redukuje hromadění bodů ve středu grafu.

Nová metoda UMAP

Nový pohled, představující alternativu ke klasickým postupům, přináší metoda UMAP. Ta využívá Riemannovu (Riemannovskou) geometrii společně s již zmiňovanou algebraickou topologií. Algoritmus UMAP je schopný konkurovat metodě t-SNE, hlavně z hlediska vizualizace, a s vyšší pravděpodobností zachovává větší část vlastností vnitřní struktury s vynikající výpočetní dobou. Více si o metodě můžete přečíst v této studii.

Vizualizace dat při použití metody UMAP
Obrázek č. 4: Vizualizace dat při použití metody UMAP
(převzato z prezentace Lelanda McInnese, https://slideslive.com/38913519)

Proces redukce dimenze
Obrázek č. 5: Proces redukce dimenze (převzato z prezentace Lelanda McInnese, https://slideslive.com/38913519)

Obrázek č. 5 popisuje proces redukce dimenze, konkrétně minimalizace vzájemné entropie. První člen vzorce optimalizuje shluky v prostoru s redukovanou dimenzí. Druhý člen se snaží optimalizovat prostor mezi jednotlivými shluky. Podrobněji si o celé problematice přečtete v tomto článku.

Vnořování slov (Words Embeddings)

Pro vnořování slov, neboli words embedding, v současné době v Gauss Algorithmic využíváme knihovnu FastText, která je rozšířením nástroje Word2vec. Ten představuje neuronovou síť o dvou vrstvách, která převede slova v původním textu do vektorů čísel. Nástroj FastText už do neuronové sítě neposílá jednotlivá slova, ale n-gramy z nich vytvořené. Výstupní vektor, charakterizující jednotlivá slova, je potom tvořený součtem ze všech n-gramů daného slova. Vzájemná podobnost a vztah mezi konkrétními slovy jsou následně stanoveny na základě výpočtu kosinové vzdálenosti mezi jejich vektory.

Geometrické propojení slov

Topologické přístupy při zpracování přirozeného jazyka zatím nejsou tak hojně využívány. Vzájemný vztah mezi slovy je zde zprostředkován na základě vytvoření geometrického propojení slov, kdy jednotlivé hrany nesou informaci o podobnosti mezi propojenými slovy v lokálním, ale i globálním kontextu.

Metoda je detailně popsána například v článku, kde se pomocí geometrického propojení slov v kombinaci s nástrojem Word2vec porovnává podobnost dokumentů. Nejprve se z dokumentu vytvoří vektorová reprezentace slov a na základě těchto vektorů se geometricky zobrazí slova v prostoru podle jejich podobnosti. Mezi těmito sadami vektorů, kdy je každá sada z jednoho dokumentu, se hledá Gromov-Haussdorffova vzdálenost. Když je tato vzdálenost rovná nule, jsou slova z obou dokumentů ve stejné geometrii. Čím nižší je vzdálenost, tím jsou si dokumenty podobnější.

 Ukázka geometrického propojení slov z dat společnosti Yelp
Obrázek č. 6: Ukázka geometrického propojení slov z dat společnosti Yelp (převzato z prezentace Lelanda McInnese, https://slideslive.com/38913519)

Shlukování

Metody shlukování používáme k roztřídění dat do několika skupin na základě jejich vzájemného vztahu. Jednou z námi nejčastěji využívaných je nehierarchická shlukovací metoda K-means. Předpokladem této metody je znalost požadovaného výstupního počtu shluků, kdy jsou data postupně přiřazována do shluků na základě jejich vzdálenosti od centrálních bodů těchto shluků (centroidů), které jsou v každé iteraci přepočítávány.

Spectral Clustering

Z topologických metod můžeme použít metodu Spectral Clustering (spektrální shlukování) a metodu vycházející z výše zmíněné metody UMAP. Bližší popis a vysvětlení spektrálního shlukování najdete v článku od Antonia Riesera.

Vizualizace dat podle metody Spectral Clustering
Obrázek č. 7: Vizualizace dat podle metody Spectral Clustering (převzato z prezentace Lelanda McInnese, https://slideslive.com/38913519)

Shrnutí

Topologická analýza dat má jednu nespornou výhodu, zachovává vnitřní vztahy systémů, které následně můžeme použít pro optimalizaci algoritmu. Všechny zmíněné nové postupy ale narážejí na několik úskalí: Prvním z nich je skutečnost, že využívají matematicky složité struktury a práce s nimi vyžaduje pokročilé matematické znalosti. Díky tomu, že se jedná o poměrně nové metody, chybí zavedené pracovní postupy i jejich automatizace. Nejsou například vytvořené knihovny, nastavená pravidla apod., proto práce vyžaduje více času. Pro některé projekty zcela dostačují klasické metody datové vědy. Topologickou analýzu dat doporučujeme využít v případě, kdy kladete důraz především na přesnost dosažených výsledků a zachování vnitřních vztahů.

Použitá literatura

McInnes, Leland. UMAP: Uniform Manifold Approximation and Projection for Dimension Reduction. arXiv® Cornell University. December 7, 2018 [cit. 6. 3. 2019]. Dostupné z: https://arxiv.org/pdf/1802.03426.pdf.

Rieser, Antonio. A Topological Approach to Spectral Clustering. arXiv® Cornell University. June 8, 2015. [cit. 7. 3. 2019]. Dostupné z: https://arxiv.org/pdf/1506.02633.pdf.

Govc, Dejan – Skraba, Primoz. AN APPROXIMATE NERVE THEOREM. arXiv® Cornell University. April 18, 2017. [cit. 7. 3. 2019]. Dostupné z: https://arxiv.org/pdf/1608.06956.pdf.

Michel, Paul – Ravichander, Abhilasha –  Rijhwani, Shruti. Does the Geometry of Word Embeddings Help Document Classification? A Case Study on Persistent Homology Based Representations. arXiv® Cornell University. May 31, 2017. [cit. 11. 3. 2019]. Dostupné z: https://arxiv.org/pdf/1705.10900.pdf.

Líbí se vám článek? Sdílejte jej.

K tématu by vás mohlo zajímat

Případová studie použití datové analýzy na predikci platební kázně
Případová studie použití datové analýzy na predikci platební kázně26. ledna 2015

Cílem studie je ohodnocení (rating) nových zákazníků na základě předchozího chování podobných subjektů. K tomuto úče...

Více informací o Případová studie použití datové analýzy na predikci platební kázně

Máte zájem o naše služby?

Kontaktujte nás

Sbíráme anonymní data a měříme, abychom náš web mohli dále vylepšovat. Souhlasíte se sběrem cookies?

AnoNe, více informací