UMAP

Versiunea actuală a paginii nu a fost încă revizuită de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 8 septembrie 2019; verificările necesită 2 modificări .

Uniform Manifold Aproximation and Projection (UMAP) este un algoritm de învățare automată care efectuează reducerea neliniară a dimensionalității [1] .

Istoria creației și descrierea

UMAP a fost creat de Leland McInnes împreună cu colegii săi de la Institutul Tutt . Scopul a fost de a avea un algoritm similar cu t-SNE [2] dar cu o bază matematică mai puternică [3] .

Când reduceți dimensiunea, UMAP efectuează mai întâi o construcție grafică ponderată , conectând marginile numai la acele obiecte care sunt cele mai apropiate. Mulțimea muchiilor unui graf este o mulțime neclară cu o funcție de membru , este definită ca probabilitatea existenței unei muchii între două vârfuri. Apoi algoritmul creează un grafic în spațiul de dimensiuni reduse și îl aproximează cu cel original, minimizând suma divergențelor Kullback-Leibler [a] pentru fiecare muchie din mulțimile [4] [5] .

Algoritmul UMAP este utilizat în diverse domenii ale științei: bioinformatică , știința materialelor , învățarea automată [6] .

Cum funcționează algoritmul

Algoritmul primește o selecție de obiecte pentru procesare: . UMAP calculează distanța dintre obiecte în funcție de o metrică dată și pentru fiecare obiect determină o listă cu cei mai apropiați vecini ai săi: . $n$ ${\displaystyle X=\{x_{1},\;\ldots,\;x_{n}\))$ $x_{i}$ $k$ $T=\{t_{1},\;\ldots ,\;t_{k}\}$

În plus, pentru fiecare obiect se calculează distanța până la cel mai apropiat vecin: . Precum și valoarea dată de ecuație: $\rho _{i}=\min _{t\,\in \,T}d(x_{i},t)$ $\sigma_i$

\sum _{t\,\in \,T}\exp \left(-{\frac {d(x_{i},t)-\rho _{i)}{\sigma _{i} }}\right)=\log _{2}k

Apoi, algoritmul construiește un grafic direcționat ponderat în care muchiile conectează fiecare obiect cu vecinii săi. Greutatea unei margini de la un obiect la vecinul său se calculează după cum urmează: $x_{i}$ $t_{j}$

w(x_{i}\rightarrow t_{j})=\exp \left(-{\frac {d(x_{i},t_{j})-\rho _{i)}{\sigma _{i}}}\dreapta)

Cel obținut mai devreme normalizează suma greutăților pentru fiecare obiect la un număr dat . $\sigma_i$ $\log _{2}k$

Deoarece UMAP construiește un grafic direcționat ponderat, între vârfuri pot exista două muchii cu greutăți diferite. Greutatea unei muchii este interpretată ca probabilitatea existenței unei muchii date de la un obiect la altul. Pe baza acesteia, muchiile dintre două vârfuri sunt combinate într-unul singur cu o pondere egală cu probabilitatea existenței a cel puțin unei muchii:

w(x_{i},x_{j})=w(x_{i}\rightarrow x_{j})+w(x_{j}\rightarrow x_{i}) -w(x_{i} \rightarrow x_{j})\cdot w(x_{j}\rightarrow x_{i})

Astfel, algoritmul obține un graf nedirecționat ponderat [7] .

Mulțimea muchiilor unui astfel de grafic este un set neclar de variabile aleatoare Bernoulli . Algoritmul creează un nou grafic într-un spațiu cu dimensiuni reduse și aproximează setul marginilor sale de cel original. Pentru a face acest lucru, minimizează suma divergențelor Kullback-Leibler pentru fiecare muchie din seturile fuzzy originale și noi: $E$ $e$

\sum _{e\in E}w_{h}(e)\log {\frac {w_{h}(e)}{w_{l}(e)))+(1-w_{h }(e))\log \left({\frac {1-w_{h}(e)}{1-w_{l}(e)}}\right)\rightarrow \min _{w_{l}}

[8] ,

w_{h}(e)

este funcția de apartenență a unui set neclar de muchii într-un spațiu de dimensiuni mari,

w_{l}(e)

este funcția de membru a unui set neclar de muchii într-un spațiu cu dimensiuni reduse.

UMAP rezolvă problema minimizării utilizând coborârea gradientului stocastic . Setul de margini rezultat determină noua locație a obiectelor și, în consecință, maparea cu dimensiuni reduse a spațiului original.

Software

Ghid de instalare a bibliotecii
Aplicație în limbaj R

Literatură

Duoduo Wu, Joe Yeong Poh Sheng, Grace Tan Su-En, Marion Chevrier, Josh Loh Jie Hua, Tony Lim Kiat Hon, Jinmiao Chen. Comparație între UMAP și t-SNE pentru date cu o singură celulă derivate prin imunofluorescență multiple din secțiuni de țesut // bioRxiv . – 2019. – 15 feb. - doi : 10.1101/549659 .
Etienne Becht, Charles-Antoine Dutertre, Immanuel W. H. Kwok, Lai Guan Ng, Florent Ginhoux, Evan W. Newell. Evaluarea UMAP ca alternativă la t-SNE pentru date unicelulare // bioRxiv . - 2018. - 28 iunie. - doi : 10.1101/298430 .
Leland McInnes, John Healy, James Melville. UMAP: Uniform Manifold Aproximation and Projection for Dimension Reduction // arXiv . - 2018. - 7 decembrie.

Note

↑ Etienne Becht, 2018 , p. unu.
↑ Duoduo Wu, 2019 .
↑ PyData Ann Arbor Meetup. PyData Ann Arbor: Leland McInnes, PCA, t-SNE și UMAP: Modern Approaches to Dimension Reduction ( 12 iunie 2018). Preluat la 28 iunie 2019. Arhivat din original la 9 noiembrie 2020.
↑ Leland McInnes, 2018 , p. 11-12.
↑ Jacob Hansen. UMAP (engleză) (link indisponibil) . Plog personal (4 mai 2018). Preluat la 28 iunie 2019. Arhivat din original la 26 august 2019.
↑ Ceshine Lee. UMAP pe RAPIDS (15x Speedup) (engleză) (PDF). Medie (30 martie 2019). Preluat la 28 iunie 2019. Arhivat din original la 26 august 2019.
↑ Leland McInnes, 2018 , p. 13.
↑ Leland McInnes, 2018 , p. 16-17.

↑ Autorii numesc această valoare entropia încrucișată a mulțimilor fuzzy, entropia încrucișată a mulțimii fuzzy

Link -uri

Prezentarea autorului a algoritmului
Tutorialul autorului și beneficiile UMAP
Exemple de lucru în UMAP: 1 și 2
Prezentare generală a algoritmului
Cum funcționează algoritmul și exemple