A dimenziók átka - Curse of dimensionality

A dimenzionalitás átka különféle jelenségekre utal, amelyek akkor merülnek fel, amikor nagy dimenziós terekben elemezzük és rendezzük az adatokat, és amelyek nem fordulnak elő alacsony dimenziós beállításokban, például a mindennapi tapasztalatok háromdimenziós fizikai terében . A kifejezést Richard E. Bellman találta ki, amikor a dinamikus programozás problémáit mérlegelte .

Méretileg átkozott jelenségek fordulnak elő olyan területeken, mint a numerikus elemzés , a mintavétel , a kombinatorika , a gépi tanulás , az adatbányászat és az adatbázisok . Ezeknek a problémáknak az a közös témája, hogy amikor a dimenzionalitás növekszik, a tér térfogata olyan gyorsan növekszik, hogy a rendelkezésre álló adatok ritkák lesznek. Ez a ritkaság problematikus minden olyan módszer esetében, amely statisztikai szignifikanciát igényel . A statisztikailag megbízható és megbízható eredmény elérése érdekében az eredmény alátámasztásához szükséges adatok mennyisége a méretarányosság mellett gyakran exponenciálisan növekszik. Az adatok rendezése és keresése gyakran azon területek felismerésén alapul, ahol az objektumok hasonló tulajdonságú csoportokat alkotnak; nagydimenziós adatokban azonban minden objektum ritka és sok szempontból különbözik egymástól, ami megakadályozza a közös adatszervezési stratégiák hatékonyságát.

Domainek

Kombinatorika

Bizonyos problémák esetén mindegyik változó több diszkrét érték egyikét veheti fel, vagy a lehetséges értékek tartománya fel van osztva, hogy véges számú lehetőséget adjon. A változókat együttvéve rengeteg értékkombinációt kell figyelembe venni. Ezt a hatást kombinatorikus robbanásnak is nevezik . A bináris változók legegyszerűbb esetben is a lehetséges kombinációk száma már exponenciális a dimenzióban. Naivan minden további dimenzió megduplázza az összes kombináció kipróbálásához szükséges erőfeszítést. ${\ displaystyle d}$ ${\ displaystyle 2 ^ {d}}$

Mintavétel

A matematikai térhez további dimenziók hozzáadásával exponenciálisan növekszik a térfogat . Például 10 ² = 100 egyenletesen elosztott mintapont elegendő egységnyi intervallum ("1-dimenziós kocka") mintavételéhez, ahol a pontok közötti távolság legfeljebb 10 ⁻² = 0,01; Egy 10 dimenziós egység hiperkocka ekvivalens mintavételezéséhez egy rács, amelynek a szomszédos pontok közötti távolság 10 ⁻² = 0,01, 10 ²⁰ = [(10 ² ) ¹⁰ ] mintapontra lenne szükség . Általánosságban elmondható, hogy 10 ^{- n} távolságtartomány mellett a 10 dimenziós hiperkocka 10 ^{n (10−1)} = [(10 ⁿ ) ¹⁰ / (10 ⁿ )] tényező "nagyobb", mint az 1 dimenziós hiperkocka. hiperkocka, amely az egység intervalluma. A fenti példában n = 2: 0,01 mintavételi távolság használatakor a 10 dimenziós hiperkocka 10 ¹⁸ "nagyobb", mint az egység intervalluma. Ez a hatás a fenti kombinatorikai problémák és az alábbiakban kifejtett távolságfüggvény-problémák kombinációja.

Optimalizálás

A dinamikus optimalizálási problémák numerikus visszafelé indukcióval történő megoldása során az értékek minden kombinációjára ki kell számítani a célfüggvényt. Ez jelentős akadályt jelent, ha az "állapotváltozó" dimenziója nagy.

Gépi tanulás

A gépi tanulás a problémákat, amelyek magukban foglalják a tanulás egy „state-of-természet” egy véges számú adat minták magas dimenziós jellemző térben minden funkció, amelynek számos lehetséges értékek jellemzően óriási mennyiségű képzés adatokra van szükség annak biztosítása érdekében, hogy az értékek minden kombinációjával több minta van.

Tipikus ökölszabály, hogy az ábrázolás minden dimenziójához legalább 5 képzési példa legyen. A gépi tanulásban és a prediktív teljesítmény tekintetében a dimenzió átkát felcserélve használják a csúcsjelenséggel , amelyet Hughes-jelenségnek is neveznek . Ez a jelenség azt állítja, hogy rögzített számú képzési minta esetén az osztályozó vagy a regresszor átlagos (várható) előrejelző ereje először növekszik, mivel a használt dimenziók vagy jellemzők száma növekszik, de egy bizonyos dimenziósságon túl romlani kezd, ahelyett, hogy folyamatosan javulna.

Mindazonáltal egy egyszerű osztályozóval összefüggésben ( lineáris diszkrimináns elemzés a többváltozós Gauss-modellben egy közös ismert kovariancia-mátrix feltételezése mellett) Zollanvari és mtsai. analitikusan és empirikusan is megmutatta, hogy amíg egy kiegészítő jellemzőkészlet relatív kumulatív hatékonysága (a már az osztályozóba tartozó jellemzők tekintetében) nagyobb (vagy kevesebb), mint e kiegészítő jellemzőkészlet mérete, addig a az ezen kiegészítő jellemzők alapján elkészített osztályozó kisebb (vagy nagyobb) lesz, mint a nélkülük elkészített osztályozó várható hibája. Más szavakkal, mind a kiegészítő jellemzők mérete, mind azok (relatív) kumulatív diszkriminatív hatása fontos az átlagos prediktív erő csökkenésének vagy növekedésének megfigyelésében.

Távolságfüggvények

Ha egy olyan mértéket, mint egy euklideszi távolság , sok koordináta segítségével határozunk meg, a különböző mintapárok közötti távolságokban alig van különbség.

Az egyik módja annak, hogy bemutassa a „végtelen” a nagy dimenziós tér összehasonlítani aránya egy feliratos hipergömb sugarú és dimenzió ebben a hiperkockák élei hosszának A kötet egy ilyen gömb , ahol a gamma-függvény , míg a kocka térfogata . A tér méretének növekedésével a hiperszféra jelentéktelen térfogattá válik a hiperkocka méretéhez képest. Ez jól látható az arányok összehasonlításával, mivel a dimenzió a végtelenbe megy: ${\ displaystyle r}$ ${\ displaystyle d}$ ${\ displaystyle 2r.}$ ${\ displaystyle {\ frac {2r ^ {d} \ pi ^ {d / 2}} {d \; \ Gamma (d / 2)}}}$ ${\ displaystyle \ Gamma}$ ${\ displaystyle (2r) ^ {d}}$ ${\ displaystyle d}$ ${\ displaystyle d}$

{\ displaystyle {\ frac {V _ {\ mathrm {hypersphere}}} {V _ {\ mathrm {hypercube}}}}} = {\ frac {\ pi ^ {d / 2}} {d2 ^ {d-1} \ Gamma (d / 2)}} \ jobbra nyíl 0}

mint .

{\ displaystyle d \ rightarrow \ infty}

Ezenkívül a középpont és a sarkok közötti távolság megnövekszik anélkül, hogy fix r-hez kötődne. Ebben az értelemben a nagydimenziós tér csaknem minden része "messze van" a központtól. Nagy dimenziókban a d- dimenziós egység hiperkocka térfogata (a csúcsok koordinátáival ) a d nagy dimenziós sugarú gömb közelében koncentrálódik . Valójában az egyes koordináták esetében a kocka átlagos értéke ${\ displaystyle r {\ sqrt {d}}}$ ${\ displaystyle \ pm 1}$ ${\ displaystyle {\ sqrt {d}} / {\ sqrt {3}}}$ ${\ displaystyle x_ {i}}$ ${\ displaystyle x_ {i} ^ {2}}$

{\ displaystyle \ langle x_ {i} ^ {2} \ rangle = {\ frac {1} {2}} \ int _ {- 1} ^ {1} x ^ {2} dx = {\ frac {1} {3}}}

.

A kocka egyenletes eloszlásának szórása ${\ displaystyle x_ {i} ^ {2}}$

{\ displaystyle {\ frac {1} {2}} \ int _ {- 1} ^ {1} x ^ {4} dx- \ langle x_ {i} ^ {2} \ rangle ^ {2} = {\ frac {4} {45}}}

Ezért az origótól számított négyzet távolságnak átlagos értéke d / 3 és szórása 4 d / 45. Nagy d esetén a (z) eloszlása közel van a normál eloszláshoz az átlag 1/3-mal és a szórással a központi határtétel szerint . Így nagy méretekben mind a hiperkocka "közepe", mind a sarkai üresek, és az összes térfogat a "köztes" sugarú gömb közelében koncentrálódik . ${\ displaystyle r ^ {2} = \ sum _ {i} x_ {i} ^ {2}}$ ${\ displaystyle r ^ {2} / d}$ ${\ displaystyle {\ frac {2} {\ sqrt {45d}}}}$ ${\ displaystyle {\ sqrt {d / 3}}}$

Ez a khi-négyzet eloszlás megértését is segíti . Valójában a [-1, 1] intervallumban egy véletlenszerű ponthoz társított (nem központi) chi-négyzet eloszlás megegyezik a d- kocka véletlenszerű pontjának hosszúság-négyzet eloszlásával . A nagy számok törvénye szerint ez az eloszlás keskeny sávban koncentrálódik az eredeti levezetés szórásának négyzetének (σ ² ) d- szeresére . Ez megvilágítja a khi-négyzet eloszlást, és azt is szemlélteti, hogy a d- kocka térfogatának legnagyobb része egy sugarú gömb felszíne közelében koncentrálódik . ${\ displaystyle \ sigma {\ sqrt {d}}}$

A jelenség további fejlődése a következő. A valós számok bármely fix eloszlása szorzatot indukál ℝ ^d pontjain . Bármely fix n esetén kiderül, hogy a Q véletlen referenciapont és az n P ₁ , ..., P _n véletlen adatpont listája közötti minimális és maximális távolság felismerhetetlenné válik a minimális távolsághoz képest:

{\ displaystyle \ lim _ {d \ to \ infty} E \ balra ({\ frac {\ operátornév {dist} _ {\ max} (d) - \ operátornév {dist} _ {\ min} (d)} { \ üzemeltető neve {dist} _ {\ min} (d)}} \ jobbra \ \ 0}

.

Erre gyakran hivatkoznak, mivel a távolságfüggvények nagy dimenziókban elvesztik hasznosságukat (például a vonás-összehasonlító algoritmusokban a legközelebbi szomszéd kritérium szempontjából). A legújabb kutatások azonban azt mutatják, hogy ez csak akkor áll fenn a mesterséges forgatókönyvben, ha az-egydimenziós eloszlások függetlenek és azonos eloszlásúak . Ha az attribútumok korrelálnak egymással, az adatok könnyebbé válhatnak és nagyobb kontrasztot nyújthatnak, és a jel / zaj arány fontos szerepet játszik, ezért a jellemzők kiválasztását kell használni.

Legközelebbi szomszéd keresés

A hatás megnehezíti a legközelebbi szomszéd keresését nagy dimenziós térben. Nem lehet gyorsan elutasítani a jelölteket, ha egy koordináta különbségét használjuk alsó határként egy távolságra az összes dimenzió alapján.

Nemrégiben azonban megfigyelték, hogy a dimenziók puszta száma nem feltétlenül okoz nehézségeket, mivel a releváns további dimenziók is növelhetik a kontrasztot. Ezen túlmenően az így kapott rangsor szempontjából továbbra is hasznos megkülönböztetni a közeli és távoli szomszédokat. A lényegtelen ("zaj") méretek azonban csökkentik a kontrasztot a fent leírt módon. Az idősor-elemzés során , ahol az adatok eredendően nagydimenziósak, a távolságfüggvények is megbízhatóan működnek mindaddig, amíg a jel-zaj arány elég magas.

k - a legközelebbi szomszéd osztályozás

A másik hatás, magas dimenzionalitás a távolság funkciók aggodalmak k -nearest szomszéd ( k -NN) diagramjánál épített egy adathalmaz segítségével távolságban funkciót. Mivel a méret növekedésével a -foka eloszlása k -NN digráf válik ferde a csúcs a jobb, mert a megjelenése aránytalan számú csomópontok , azaz adat-pontok jelennek meg több k -NN listákat más adatpontok, mint az átlag. Ez a jelenség jelentős hatással lehet a különböző osztályozási technikákra (beleértve a k -NN osztályozót ), a félig felügyelt tanulásra és a klaszterezésre , és hatással van az információ visszakeresésére is .

Anomáliák felderítése

Egy 2012-es felmérésben Zimek et al. A nagydimenziós adatok anomáliáinak keresésekor a következő problémákat azonosította :

Pontszámok és távolságok koncentrációja: a származtatott értékek, például a távolságok, számszerűen hasonlóvá válnak
Irreleváns attribútumok: nagy dimenziójú adatokban az attribútumok jelentős része nem releváns
Referenciakészletek meghatározása: a helyi módszerek esetében a referenciakészletek gyakran a legközelebbi szomszéd alapúak
Összehasonlíthatatlan pontszámok a különböző dimenziókhoz: a különböző alterületek összehasonlíthatatlan pontszámokat eredményeznek
A pontszámok értelmezhetősége: a pontszámok gyakran már nem jelentenek szemantikai jelentést
Exponenciális keresési hely: a keresési terület már nem szisztematikusan szkennelhető
Adatok szaggatása torzítás: tekintettel a nagy keresési helyre, minden kívánt jelentőségre vonatkozóan megtalálható egy hipotézis
Hubness: bizonyos objektumok gyakrabban fordulnak elő a szomszédlistákban, mint mások.

Az elemzett speciális módszerek közül sok megoldja ezeket a problémákat, de sok nyitott kutatási kérdés marad.

A dimenziósság áldása

Meglepő módon és a várható "dimenziós átok" nehézségek ellenére a legegyszerűbb módszereken alapuló józan ész heurisztikája "olyan eredményeket hozhat, amelyek szinte biztosan optimálisak" a nagydimenziós problémákra. A "dimenzió megáldása" kifejezést az 1990-es évek végén vezették be. Donoho "Millenniumi kiáltványában" világosan elmagyarázta, hogy a "dimenzió áldása" miért képezi a jövőbeni adatbányászat alapját. A dimenziósság megáldásának hatásait számos alkalmazásban fedezték fel, és a mérési jelenségek koncentrációjában találták meg alapjaikat . A dimenziós jelenség megáldásának egyik példája a véletlen pont lineáris elválaszthatósága egy nagy véges véletlen halmaztól nagy valószínűséggel, még akkor is, ha ez a halmaz exponenciálisan nagy: ebben a véletlen halmazban az elemek száma a dimenzióval exponenciálisan nőhet. Ezenkívül ez a lineáris funkció a legegyszerűbb lineáris Fisher-diszkrimináns formájában választható ki . Ezt az elválaszthatósági tételt a valószínűségeloszlások széles osztályánál bizonyították: általános egységesen log-konkáv eloszlások, egy kocka termékeloszlása és sok más család (a közelmúltban áttekintve).

"A dimenziósság áldása és a dimenzió átka ugyanazon érem két oldala." Például a nagydimenziós térben a lényegében nagy dimenziójú valószínűségi eloszlások jellemző tulajdonsága: a véletlenszerű pontok négyzetes távolsága egy kiválasztott ponthoz nagy valószínűséggel közel van az átlagos (vagy medián) négyzet távolsághoz. Ez a tulajdonság jelentősen leegyszerűsíti az adatok várható geometriáját és a nagydimenziós adatok indexelését (áldás), ugyanakkor megnehezíti, sőt haszontalanná teszi a hasonlóság keresését nagy dimenziókban (átok).

Zimek és mtsai. megjegyezte, hogy míg a dimenziós átok tipikus formalizálása befolyásolja az iid adatokat, az egyes attribútumokban elválasztott adatok birtoklása még nagy dimenziókban is könnyebbé válik, és azzal érvelt, hogy a jel / zaj arány számít: az adatok minden egyes attribútummal könnyebbé válnak, amely hozzáadódik jel, és nehezebb olyan attribútumokkal, amelyek csak zajt (irreleváns hibát) adnak az adatokhoz. Különösen a felügyelet nélküli adatelemzésnél ismerik el ezt a hatást.

Languages

In other projects