Náhodná projekce - Random projection

V matematice a statistice náhodná projekce je technika zvyklá snížit rozměrnost množiny bodů, které leží v Euklidovský prostor. Metody náhodné projekce jsou známé svou silou, jednoduchostí a nízkou chybovostí ve srovnání s jinými metodami^{[Citace je zapotřebí ]}. Podle experimentálních výsledků náhodná projekce dobře zachovává vzdálenosti, ale empirické výsledky jsou řídké.^[1]Byly použity pod mnoha úkoly v přirozeném jazyce pod tímto názvem náhodné indexování.

Snížení rozměrů

Redukce rozměrů, jak název napovídá, snižuje počet náhodných proměnných pomocí různých matematických metod ze statistik a strojového učení. Snížení rozměrů se často používá ke snížení problému správy a manipulace s velkými soubory dat. Techniky snižování rozměrů obecně používají lineární transformace při určování vnitřní rozměrnosti potrubí a také při extrakci jeho hlavních směrů. Pro tento účel existují různé související techniky, včetně: analýza hlavních komponent, lineární diskriminační analýza, kanonická korelační analýza, diskrétní kosinová transformace, náhodná projekce atd.

Náhodná projekce je jednoduchý a výpočetně efektivní způsob, jak snížit rozměrnost dat obchodováním kontrolovaného množství chyb pro rychlejší časy zpracování a menší velikosti modelu. Rozměry a distribuce matic náhodných projekcí jsou řízeny tak, aby přibližně zachovaly párové vzdálenosti mezi libovolnými dvěma vzorky datové sady.

Metoda

Základní myšlenka náhodné projekce je uvedena v Johnson-Lindenstraussovo lemma,^[2] který uvádí, že pokud jsou body ve vektorovém prostoru dostatečně vysoké dimenze, mohou být promítnuty do vhodného prostoru nižší dimenze způsobem, který přibližně zachovává vzdálenosti mezi body.

V náhodné projekci se původní d-dimenzionální data promítají do k-dimenzionálního (k << d) podprostoru pomocí náhodného promítání ${ displaystyle k times d}$ - rozměrová matice R, jejíž sloupce mají jednotkové délky.^{[Citace je zapotřebí ]} Použití maticového zápisu: If ${ displaystyle X_ {d krát N}}$ je tedy původní sada N d-dimenzionálních pozorování ${ displaystyle X_ {k krát N} ^ {RP} = R_ {k krát d} X_ {d krát N}}$ je projekce dat do nižšího k-dimenzionálního podprostoru. Náhodná projekce je výpočetně jednoduchá: vytvořte náhodnou matici "R" a promítněte ${ displaystyle d krát N}$ datová matice X do K rozměrů objednávky ${ displaystyle O (dkN)}$ . Pokud je datová matice X řídká s přibližně n nenulovými položkami na sloupec, pak je složitost této operace v pořádku ${ displaystyle O (ckN)}$ .^[3]

Gaussova náhodná projekce

Náhodná matice R může být generována pomocí Gaussova rozdělení. První řádek je náhodný jednotkový vektor jednotně vybraný z ${ displaystyle S ^ {d-1}}$ . Druhý řádek je náhodný jednotkový vektor z prostoru kolmého na první řádek, třetí řádek je náhodný jednotkový vektor z prostoru kolmého na první dva řádky atd. Při tomto způsobu výběru R je R ortogonální matice (inverzní k její transpozici) a jsou splněny následující vlastnosti:

Sférická symetrie: Pro jakoukoli ortogonální matici ${ displaystyle A v O (d)}$ , RA a R mají stejnou distribuci.
Ortogonalita: Řady R jsou navzájem kolmé.
Normálnost: Řádky R jsou vektory jednotkové délky.

Výpočtově efektivnější náhodné projekce

Achlioptas^[4] ukázal, že Gaussovo rozdělení lze nahradit mnohem jednodušším rozdělením, jako např

{ displaystyle R_ {i, j} = { sqrt {3}} krát { begin {cases} +1 & { text {s pravděpodobností}} { frac {1} {6}} 0 & { text {s pravděpodobností}} { frac {2} {3}} - 1 & { text {s pravděpodobností}} { frac {1} {6}} end {případy}}}

To je efektivní pro databázové aplikace, protože výpočty lze provádět pomocí celočíselné aritmetiky.

Později se ukázalo, jak při práci na Sparse JL Transform používat celočíselnou aritmetiku, zatímco distribuce je ještě řídší a má velmi málo nenulových hodnot na sloupec.^[5] To je výhodné, protože řídká matice vkládání znamená možnost promítat data do nižší dimenze ještě rychleji.

Velké kvaziortogonální základny

The Johnson-Lindenstraussovo lemma uvádí, že velké sady vektorů ve vysokodimenzionálním prostoru lze lineárně mapovat v prostoru mnohem nižší (ale stále vysoké) dimenze n s přibližným zachováním vzdáleností. Jedním z vysvětlení tohoto jevu je exponenciálně vysoká kvaziortogonální dimenze n-dimenzionální Euklidovský prostor.^[6] Existují exponenciálně velké (v dimenzi n) sady téměř ortogonální vektory (s malou hodnotou vnitřní výrobky ) v n–Dimenzionální euklidovský prostor. Toto pozorování je užitečné v indexování vysoce dimenzionálních dat.^[7]

Kvasiortogonalita velkých náhodných množin je důležitá pro metody náhodné aproximace v strojové učení. Ve vysokých dimenzích jsou exponenciálně velké počty náhodně a nezávisle zvolených vektorů z ekvidistribuce na kouli (a z mnoha dalších distribucí) téměř kolmé s pravděpodobností blízkou jedné.^[8] To znamená, že aby bylo možné reprezentovat prvek takového trojrozměrného prostoru lineárními kombinacemi náhodně a nezávisle zvolených vektorů, může být často nutné generovat vzorky exponenciálně velké délky, pokud použijeme omezené koeficienty v lineárních kombinacích. Na druhou stranu, pokud jsou povoleny koeficienty s libovolně velkými hodnotami, počet náhodně vygenerovaných prvků, které jsou dostatečné pro aproximaci, je dokonce menší než rozměr datového prostoru.

Implementace

RandPro - Balíček R pro náhodnou projekci ^[9]
sklearn.random_projection - Pythonový modul pro náhodnou projekci
Implementace Weka [1]

Viz také

Reference

^ Ella, Bingham; Heikki, Mannila (2001). "Náhodná projekce při redukci rozměrů: Aplikace na obrazová a textová data". KDD-2001: Sborník ze sedmé mezinárodní konference ACM SIGKDD o získávání znalostí a dolování dat. New York: Sdružení pro výpočetní techniku. str. 245–250. CiteSeerX 10.1.1.24.5135. doi:10.1145/502512.502546.
^ Johnson, William B.; Lindenstrauss, Joram (1984). "Rozšíření mapování Lipschitze do Hilbertova prostoru". Konference o moderní analýze a pravděpodobnosti (New Haven, Conn., 1982). Současná matematika. 26. Providence, RI: American Mathematical Society. str.189–206. doi:10.1090 / conm / 026/737400. ISBN 9780821850305. PAN 0737400..
^ Bingham, Ella; Mannila, Heikki (6. května 2014). „Náhodná projekce při redukci rozměrů: Aplikace na obrazová a textová data“ (PDF).
^ Achlioptas, Dimitris (2001). "Náhodné projekce vhodné pro databázi". Sborník dvacátého sympozia ACM SIGMOD-SIGACT-SIGART o zásadách databázových systémů - PODS '01. str. 274–281. CiteSeerX 10.1.1.28.6652. doi:10.1145/375551.375608. ISBN 978-1581133615.
^ Kane, Daniel M .; Nelson, Jelani (2014). „Sparser Johnson-Lindenstrauss Transforms“. Deník ACM. 61 (1): 1–23. arXiv:1012.1577. doi:10.1145/2559902. PAN 3167920.
^ Kainen, Paul C.; Kůrková, Věra (1993), „Kvaziortogonální rozměr euklidovských prostorů“, Aplikovaná matematická písmena, 6 (3): 7–10, doi:10.1016 / 0893-9659 (93) 90023-G, PAN 1347278
^ R. Hecht-Nielsen, Context vectors: General-Purpose Aproximate Mean Reprezentations Self-Organized from Raw Data, in: J. Zurada, R. Marks, C. Robinson (Eds.), Computational Intelligence: Imitating Life, IEEE Press, 1994 , str. 43–56.
^ Gorban, Alexander N.; Tyukin, Ivan Y .; Prochorov, Danil V .; Sofeikov, Konstantin I. (2016). "Aproximace s náhodnými bázemi: Pro et Contra". Informační vědy. 364-365: 129–145. arXiv:1506.04631. doi:10.1016 / j.ins.2015.09.021.
^ Ravindran, Siddharth (2020). „Technika DIRP (Data Independent Reusable Projection) pro zmenšení dimenze v klasifikaci velkých dat pomocí k-Nearest Neighbor (k-NN).“ Vědecké dopisy Národní akademie. 43: 13–21. doi:10.1007 / s40009-018-0771-6.

Fodor, I. (2002) „Přehled technik redukce rozměrů“. Centrum pro aplikované vědecké výpočty, Lawrence Livermore National, technická zpráva UCRL-ID-148494
ADITYA KRISHNA MENON (2007) „Náhodné projekce a aplikace ke snížení rozměrů“. School of Information Technologies, The University of Sydney, Australia
ADITYA Ramdas „Náhodný úvod do náhodných projekcí“. Univerzita Carnegie Mellon

[1] Ella, Bingham; Heikki, Mannila (2001). "Náhodná projekce při redukci rozměrů: Aplikace na obrazová a textová data". KDD-2001: Sborník ze sedmé mezinárodní konference ACM SIGKDD o získávání znalostí a dolování dat. New York: Sdružení pro výpočetní techniku. str. 245–250. CiteSeerX 10.1.1.24.5135. doi:10.1145/502512.502546.

[2] Johnson, William B.; Lindenstrauss, Joram (1984). "Rozšíření mapování Lipschitze do Hilbertova prostoru". Konference o moderní analýze a pravděpodobnosti (New Haven, Conn., 1982). Současná matematika. 26. Providence, RI: American Mathematical Society. str.189–206. doi:10.1090 / conm / 026/737400. ISBN 9780821850305. PAN 0737400..

[3] Bingham, Ella; Mannila, Heikki (6. května 2014). „Náhodná projekce při redukci rozměrů: Aplikace na obrazová a textová data“ (PDF).

[4] Achlioptas, Dimitris (2001). "Náhodné projekce vhodné pro databázi". Sborník dvacátého sympozia ACM SIGMOD-SIGACT-SIGART o zásadách databázových systémů - PODS '01. str. 274–281. CiteSeerX 10.1.1.28.6652. doi:10.1145/375551.375608. ISBN 978-1581133615.

[5] Kane, Daniel M .; Nelson, Jelani (2014). „Sparser Johnson-Lindenstrauss Transforms“. Deník ACM. 61 (1): 1–23. arXiv:1012.1577. doi:10.1145/2559902. PAN 3167920.

[6] Kainen, Paul C.; Kůrková, Věra (1993), „Kvaziortogonální rozměr euklidovských prostorů“, Aplikovaná matematická písmena, 6 (3): 7–10, doi:10.1016 / 0893-9659 (93) 90023-G, PAN 1347278

[7] R. Hecht-Nielsen, Context vectors: General-Purpose Aproximate Mean Reprezentations Self-Organized from Raw Data, in: J. Zurada, R. Marks, C. Robinson (Eds.), Computational Intelligence: Imitating Life, IEEE Press, 1994 , str. 43–56.

[GorbanTyukin2016-8] Gorban, Alexander N.; Tyukin, Ivan Y .; Prochorov, Danil V .; Sofeikov, Konstantin I. (2016). "Aproximace s náhodnými bázemi: Pro et Contra". Informační vědy. 364-365: 129–145. arXiv:1506.04631. doi:10.1016 / j.ins.2015.09.021.

[9] Ravindran, Siddharth (2020). „Technika DIRP (Data Independent Reusable Projection) pro zmenšení dimenze v klasifikaci velkých dat pomocí k-Nearest Neighbor (k-NN).“ Vědecké dopisy Národní akademie. 43: 13–21. doi:10.1007 / s40009-018-0771-6.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]