UMAP

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 8. september 2019; checks kræver 2 redigeringer .

Uniform Manifold Approximation and Projection (UMAP) er en maskinlæringsalgoritme , der udfører ikke-lineær dimensionalitetsreduktion [1] .

Tilblivelseshistorie og beskrivelse

UMAP blev skabt af Leland McInnes sammen med sine kolleger på Tutt Institute . Målet var at have en algoritme svarende til t-SNE [2] men med et stærkere matematisk fundament [3] .

Når dimensionen reduceres, udfører UMAP først en vægtet grafkonstruktion , der kun forbinder kanter med de objekter, der er nærmeste naboer. Sættet af kanter af en graf er et fuzzy sæt med en medlemskabsfunktion , det er defineret som sandsynligheden for eksistensen af en kant mellem to toppunkter. Derefter opretter algoritmen en graf i lavdimensionelt rum og tilnærmer den til den oprindelige, og minimerer summen af Kullback-Leibler divergenser [a] for hver kant fra mængderne [4] [5] .

UMAP-algoritmen bruges inden for forskellige videnskabsområder: bioinformatik , materialevidenskab , maskinlæring [6] .

Sådan fungerer algoritmen

Algoritmen modtager et udvalg af objekter til behandling: . UMAP beregner afstanden mellem objekter i henhold til en given metrik og bestemmer for hvert objekt en liste over dets nærmeste naboer: . $n$ ${\displaystyle X=\{x_{1},\;\ldots ,\;x_{n}\))$ $x_{i}$ $k$ $T=\{t_{1},\;\ldots ,\;t_{k}\}$

Derudover beregnes for hvert objekt afstanden til dens nærmeste nabo: . Samt værdien givet af ligningen: $\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

Dernæst bygger algoritmen en vægtet rettet graf , hvor kanter forbinder hvert objekt med dets naboer. Vægten af en kant fra en genstand til dens nabo beregnes som følger: $x_{i}$ $t_{j}$

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

Den tidligere opnåede normaliserer summen af vægtene for hvert objekt til et givet tal . $\sigma_i$ $\log _{2}k$

Da UMAP bygger en vægtet rettet graf, kan der eksistere to kanter med forskellig vægt mellem hjørner. Vægten af en kant fortolkes som sandsynligheden for eksistensen af en given kant fra et objekt til et andet. Baseret på dette kombineres kanterne mellem to hjørner til én med en vægt svarende til sandsynligheden for eksistensen af mindst én kant:

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

Algoritmen opnår således en vægtet urettet graf [7] .

Sættet af kanter af en sådan graf er et fuzzy sæt af Bernoulli tilfældige variabler . Algoritmen opretter en ny graf i et lavdimensionelt rum og tilnærmer sættet af dens kanter til den oprindelige. For at gøre dette minimerer den summen af Kullback-Leibler afvigelser for hver kant fra de originale og nye fuzzy sæt: $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)

er medlemskabsfunktionen af et fuzzy sæt kanter i et højdimensionelt rum,

w_{l}(e)

er medlemskabsfunktionen af et fuzzy sæt kanter i et lavdimensionelt rum.

UMAP løser minimeringsproblemet ved hjælp af stokastisk gradientnedstigning . Det resulterende sæt kanter bestemmer den nye placering af objekter og følgelig den lavdimensionelle kortlægning af det oprindelige rum.

Software

Bibliotek installationsvejledning
Ansøgning i R-sprog

Litteratur

Duoduo Wu, Joe Yeong Poh Sheng, Grace Tan Su-En, Marion Chevrier, Josh Loh Jie Hua, Tony Lim Kiat Hon, Jinmiao Chen. Sammenligning mellem UMAP og t-SNE for multipleks-immunofluorescens-afledte enkeltcelledata fra vævssektioner // 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. Evaluering af UMAP som et alternativ til t-SNE for enkeltcelledata // bioRxiv . - 2018. - 28. juni. - doi : 10.1101/298430 .
Leland McInnes, John Healy, James Melville. UMAP: Uniform Manifold Approximation and Projection for Dimension Reduction // arXiv . - 2018. - 7. december.

Noter

↑ Etienne Becht, 2018 , s. en.
↑ Duoduo Wu, 2019 .
↑ PyData Ann Arbor Meetup. PyData Ann Arbor: Leland McInnes, PCA, t-SNE og UMAP: Modern Approaches to Dimension Reduction ( 12. juni 2018). Hentet 28. juni 2019. Arkiveret fra originalen 9. november 2020.
↑ Leland McInnes, 2018 , s. 11-12.
↑ Jacob Hansen. UMAP (engelsk) (utilgængeligt link) . Personlig plog (4. maj 2018). Hentet 28. juni 2019. Arkiveret fra originalen 26. august 2019.
↑ Ceshine Lee. UMAP på RAPIDS (15x Speedup) (engelsk) (PDF). Medium (30. marts 2019). Hentet 28. juni 2019. Arkiveret fra originalen 26. august 2019.
↑ Leland McInnes, 2018 , s. 13.
↑ Leland McInnes, 2018 , s. 16-17.

↑ Forfatterne kalder denne værdi for krydsentropien af fuzzy sæt, fuzzy sæt krydsentropi