Ulottuvuuden kirous - Curse of dimensionality

Kirous dimensionality viittaa erilaisia ilmiöitä, jotka syntyvät kun analysointi ja järjestää datan korkean avaruuksissa , jotka eivät esiinny matalan ulotteinen-asetukset, kuten kolmiulotteista fyysisestä tilasta jokapäiväistä kokemusta. Lausekkeen keksi Richard E. Bellman harkitessaan dynaamisen ohjelmoinnin ongelmia .

Dimensioittain kirottuja ilmiöitä esiintyy sellaisilla aloilla kuin numeerinen analyysi , otanta , kombinatorika , koneoppiminen , tiedonlouhinta ja tietokannat . Näiden ongelmien yhteinen teema on, että kun ulottuvuus kasvaa, avaruuden tilavuus kasvaa niin nopeasti, että käytettävissä oleva data harvenee. Tämä harvinaisuus on ongelmallinen kaikille tilastollista merkitsevyyttä vaativille menetelmille . Tilastollisesti vakaan ja luotettavan tuloksen saamiseksi tuloksen tukemiseen tarvittavien tietojen määrä kasvaa usein eksponentiaalisesti ulottuvuuden mukana. Tietojen järjestäminen ja etsiminen perustuu usein alueiden havaitsemiseen, joissa objektit muodostavat ryhmiä, joilla on samanlaiset ominaisuudet; korkean ulottuvuuden tiedoissa kaikki objektit näyttävät kuitenkin olevan harvinaisia ja monin tavoin erilaisia, mikä estää yhteisten dataorganisaatiostrategioiden tehokkuuden.

Verkkotunnukset

Kombinaattorit

Joissakin ongelmissa kukin muuttuja voi ottaa yhden useista erillisistä arvoista tai mahdollisten arvojen alue on jaettu, jotta saadaan rajallinen määrä mahdollisuuksia. Muuttujien yhteenlaskemisen yhteydessä on otettava huomioon valtava määrä arvoyhdistelmiä. Tämä vaikutus tunnetaan myös yhdistelmäräjähdyksenä . Jopa yksinkertaisimmassa binäärimuuttujien tapauksessa mahdollisten yhdistelmien määrä on jo eksponentiaalinen ulottuvuuksissa. Jokainen ylimääräinen ulottuvuus kaksinkertaistaa kaikkien yhdistelmien kokeilemisen. ${\ displaystyle d}$ ${\ displaystyle 2 ^ {d}}$

Näytteenotto

Lisämittojen lisäämiseen matemaattiseen tilaan liittyy eksponentiaalinen äänenvoimakkuuden kasvu . Esimerkiksi 10 ² = 100 tasaisesti sijoitettua näytekohtaa riittää näytteenottoon yksikköintervallin ("1-ulotteinen kuutio") siten, että pisteiden välinen etäisyys on enintään 10 - ² = 0,01; 10-ulotteisen yksikön hyperkuution vastaava näytteenotto ristikolla , jonka vierekkäisten pisteiden väli on 10 - ² = 0,01, vaatisi 10 ²⁰ = [(10 ² ) ¹⁰ ] näytepistettä. Yleensä, kun etäisyys on 10 ^{- n} , 10-ulotteinen hyperkuutio näyttää olevan tekijä 10 ^{n (10−1)} = [(10 ⁿ ) ¹⁰ / (10 ⁿ )] "suurempi" kuin 1-ulotteinen hyperkuutio, joka on yksikköintervalli. Yllä olevassa esimerkissä n = 2: kun käytetään näytteenottoetäisyyttä 0,01, 10-ulotteinen hyperkuutio näyttää olevan 10 ¹⁸ "suurempi" kuin yksikön väli. Tämä vaikutus on yhdistelmä edellä mainituista kombinaattoriongelmista ja alla selitetyistä etäisyysfunktio-ongelmista.

Optimointi

Kun dynaamisen optimoinnin ongelmia ratkaistaan numeerisella taaksepäin induktiolla , tavoitefunktio on laskettava jokaiselle arvoyhdistelmälle. Tämä on merkittävä este, kun "tilamuuttujan" ulottuvuus on suuri.

Koneoppiminen

Vuonna koneoppimisen liittyviin ongelmiin oppiminen "state-of-luonteeltaan" alkaen rajallinen määrä tietoa näytteiden suuriulotteinen piirreavaruudessa kunkin ominaisuuden, jonka mahdollisten arvojen, tyypillisesti valtavasti harjoitusarvot on varmistettava että jokaisella arvoyhdistelmällä on useita näytteitä.

Tyypillinen nyrkkisääntö on, että jokaisessa edustuksen ulottuvuudessa tulisi olla vähintään 5 harjoitteluesimerkkiä. In koneen oppiminen ja sikäli kuin ennustava suorituskyky on kyseessä, kirouksen dimensionality käytetään vaihtokelpoisesti korkeimmillaan ilmiö , joka tunnetaan myös nimellä Hughes ilmiö . Tämä ilmiö kertoo, että kiinteällä määrällä harjoittelunäytteitä luokittelijan tai regresorin keskimääräinen (odotettu) ennakointiteho kasvaa ensin, kun käytettyjen ulottuvuuksien tai ominaisuuksien määrä kasvaa, mutta tietyn ulottuvuuden ulkopuolella se alkaa heikentyä sen sijaan, että se paranisi tasaisesti.

Kuitenkin yksinkertaisen luokittelijan yhteydessä ( lineaarinen diskriminanttianalyysi monimuuttujaisessa Gaussin mallissa olettaen yleinen tunnettu kovarianssimatriisi) Zollanvari et ai. osoitti sekä analyyttisesti että empiirisesti, että niin kauan kuin lisäominaisuusjoukon suhteellinen kumulatiivinen tehokkuus (suhteessa jo luokittelijaan kuuluviin ominaisuuksiin) on suurempi (tai vähemmän) kuin tämän lisäominaisuusjoukon koko, odotettu virhe näitä lisäominaisuuksia käyttäen rakennettu luokittelija on pienempi (tai suurempi) kuin ilman niitä rakennetun luokittelijan odotettu virhe. Toisin sanoen sekä lisäominaisuuksien koko että niiden (suhteellinen) kumulatiivinen syrjivä vaikutus ovat tärkeitä keskimääräisen ennustekyvyn laskun tai kasvun havaitsemisessa.

Etäisyystoiminnot

Kun mitta, kuten euklidinen etäisyys, määritetään käyttämällä monia koordinaatteja, eri näyteparien välillä on vähän eroja.

Yksi tapa havainnollistaa korkean ulottuvuuden euklidisen avaruuden "valtavuutta" on verrata kirjoitetun hyperpallon osuutta, jonka säde ja ulottuvuus on hyperkuution kanssa, jonka reunat ovat pitkiä . Tällaisen pallon tilavuus on , missä on gammafunktio , kun kuution tilavuus on . Avaruuden ulottuvuuden kasvaessa hyperpallosta tulee merkityksetön tilavuus suhteessa hyperkuution tilavuuteen. Tämä voidaan selvästi havaita vertaamalla suhteessa kuin ulottuvuus ääretön: ${\ 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)}} \ oikeanpuoleinen nuoli 0}

kuten .

{\ displaystyle d \ rightarrow \ infty}

Lisäksi keskipisteen ja kulmien välinen etäisyys on , mikä kasvaa sitoutumatta kiinteään r: ään. Tässä mielessä melkein koko korkeaulotteinen tila on "kaukana" keskustasta. Korkean mitat, tilavuus d ulotteinen laite hyperkuutio (koordinaatit pisteiden ) konsentroidaan lähellä pallo, jonka säde on suuri ulottuvuus d . Jokaisen koordinaatin keskimääräinen arvo kuutiossa on ${\ 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}}}

.

Kuution tasaisen jakautumisen varianssi on ${\ displaystyle x_ {i} ^ {2}}$

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

Siksi neliön etäisyydellä alkuperästä on keskiarvo d / 3 ja varianssi 4 d / 45. Suurten d , jakelu on lähellä normaalijakaumaa keskiarvon kanssa 1/3 ja keskihajonta mukaan keskeinen raja lause . Siten suurissa mittasuhteissa sekä hyperkuution "keskiosa" että kulmat ovat tyhjät, ja koko tilavuus on keskittynyt lähellä "keskisäteen" palloa . ${\ displaystyle r ^ {2} = \ summa _ {i} x_ {i} ^ {2}}$ ${\ displaystyle r ^ {2} / d}$ ${\ displaystyle {\ frac {2} {\ sqrt {45d}}}}$ ${\ displaystyle {\ sqrt {d / 3}}}$

Tämä auttaa myös ymmärtämään khi-neliön jakaumaa . Itse asiassa satunnaispisteeseen liittyvä (ei-keskitetty) khi-neliöjakauma aikavälillä [-1, 1] on sama kuin satunnaispisteen pituuden neliön jakauma d- kuutiossa. Suurten lukujen lain mukaan tämä jakauma keskittyy kapeaan kaistaan d- kertaiseksi alkuperäisen johdannaisen keskihajonnan neliön (σ ² ) ympärille. Tämä valaisee khi-neliöjakauman ja kuvaa myös, että suurin osa d- kuution tilavuudesta keskittyy lähelle säteen pallon pintaa . ${\ displaystyle \ sigma {\ sqrt {d}}}$

Tämän ilmiön jatkokehitys on seuraava. Mikä tahansa kiinteä jakauma reaaliluvuilla aiheuttaa tuotteen jakauman pisteissä ℝ ^d . Kaikki kiinteitä n , käy ilmi, että minimi ja maksimi etäisyys on satunnainen vertailupisteen Q ja listan n satunnaisten tietojen pistettä P ₁ , ..., P _n tulla huomaamaton verrattuna minimietäisyys:

{\ displaystyle \ lim _ {d \ to \ infty} E \ vasen ({\ frac {\ operaattorin nimi {dist} _ {\ max} (d) - \ operaattorin nimi {dist} _ {\ min} (d)} { \ operaattorin nimi {dist} _ {\ min} (d)}} \ oikea) \ to 0}

.

Tähän viitataan usein etäisyysfunktioiden menettäminä hyödyllisyytensä (esimerkiksi lähimmän naapurin kriteerille ominaisuusvertailualgoritmeissa) suurissa mitoissa. Viimeaikaiset tutkimukset ovat kuitenkin osoittaneet, että tämä pätee vain keinotekoiseen skenaarioon, kun yksiulotteiset jakaumat ℝ ovat riippumattomia ja identtisesti jakautuneita . Kun attribuutit korreloivat, datasta voi tulla helpompaa ja antaa suuremman etäisyyden kontrastin ja signaali-kohinasuhteen havaittiin olevan tärkeä rooli, joten ominaisuuden valintaa tulisi käyttää.

Lähin naapurihaku

Vaikutus vaikeuttaa lähimmän naapurin etsintää korkean ulottuvuuden tilassa. Ehdokkaita ei voida nopeasti hylätä käyttämällä yhden koordinaatin eroa etäisyyden alarajana kaikkien ulottuvuuksien perusteella.

Äskettäin on kuitenkin havaittu, että pelkkä ulottuvuuksien määrä ei välttämättä aiheuta vaikeuksia, koska asiaankuuluvat lisäulottuvuudet voivat myös lisätä kontrastia. Lisäksi tuloksena olevan rankingin kannalta on edelleen hyödyllistä erottaa läheiset ja kaukaiset naapurit. Epäasialliset ("kohina") mitat vähentävät kuitenkin kontrastia yllä kuvatulla tavalla. In aikasarja-analyysin , jossa tiedot ovat luonnostaan korkea-ulotteinen, etäisyys toimii myös toimittava luotettavasti niin kauan kuin signaali-kohina-suhde on riittävän suuri.

k - lähin naapuriluokittelu

Toinen suuren ulottuvuuden vaikutus etäisyystoimintoihin koskee k- lähimmän naapurin ( k -NN) kuvaajia, jotka on rakennettu etäisyysfunktiota käyttävästä datajoukosta . Kuten ulottuvuus kasvaa, indegree jakautuminen k -NN suunnatun graafin tulee vinossa kanssa huipun oikealla koska syntyminen suhteettoman paljon solmukohdat , että on, data-pisteitä, jotka näkyvät paljon enemmän k -NN luetteloita muista datapisteitä kuin keskimäärin. Tällä ilmiöllä voi olla huomattava vaikutus erilaisiin luokittelutekniikoihin (mukaan lukien k -NN-luokittelija ), osittain valvottuun oppimiseen ja klustereihin , ja se vaikuttaa myös tiedonhakuun .

Poikkeavuuksien havaitseminen

Vuonna 2012 tehdyssä tutkimuksessa Zimek et ai. havaitsi seuraavat ongelmat etsiessään poikkeavuuksia korkeaulotteisissa tiedoissa:

Pisteiden ja etäisyyksien keskittyminen: johdetut arvot, kuten etäisyydet, tulevat numeerisesti samanlaisiksi
Epäolennaiset määritteet: korkean ulottuvuuden tiedoissa merkittävä määrä attribuutteja voi olla merkityksetön
Viitejoukkojen määrittely: Paikallisille menetelmille vertailujoukot perustuvat usein lähimpään naapuriin
Vertailemattomat pisteet eri ulottuvuuksille: eri alatilat tuottavat vertaansa vailla olevia pisteitä
Pisteiden tulkittavuus: pisteet eivät usein enää välitä semanttista merkitystä
Eksponentiaalinen hakutila: hakutilaa ei voida enää skannata järjestelmällisesti
Tietojen nuuskaaminen : koska suuri hakutila on, jokaiselle halutulle merkitykselle voidaan löytää hypoteesi
Hubness: tiettyjä objekteja esiintyy naapuriluetteloissa useammin kuin toisia.

Monet analysoiduista erikoistuneista menetelmistä käsittelevät yhtä tai toista näistä ongelmista, mutta avoimia tutkimuskysymyksiä on edelleen paljon.

Ulottuvuuden siunaus

Yllättäen ja odotetuista "dimensioiden kirouksen" vaikeuksista huolimatta kaikkein suorimpiin menetelmiin perustuva terveen järjen heuristiikka "voi tuottaa tuloksia, jotka ovat melkein varmasti optimaalisia" suurille ulottuvuuksille. Termi "ulottuvuuden siunaus" otettiin käyttöön 1990-luvun lopulla. Donoho Millennium-manifestissaan selitti selvästi, miksi "ulottuvuuden siunaus" muodostaa perustan tulevalle tiedonlouhinnalle. Ulottuvuuden siunauksen vaikutukset löydettiin monista sovelluksista, ja ne löysivät perustan mittausilmiöiden keskittymiseen . Yksi esimerkki ulottuvuusilmiön siunauksesta on satunnaispisteen lineaarinen erotettavuus suuresta äärellisestä satunnaisjoukosta suurella todennäköisyydellä, vaikka tämä joukko on eksponentiaalisesti suuri: Tämän satunnaisjoukon elementtien määrä voi kasvaa eksponentiaalisesti ulottuvuuden mukana. Lisäksi tämä lineaarinen funktionaalisuus voidaan valita yksinkertaisimman lineaarisen Fisher-erottelijan muodossa . Tämä erotettavuuslauseke todistettiin laajalle todennäköisyysjakaumaluokalle: yleisesti tasaisesti log-koverat jakaumat, tuotejakaumat kuutiossa ja monet muut perheet (tarkistettu äskettäin vuonna).

"Ulottuvuuden siunaus ja ulottuvuuden kirous ovat saman kolikon kaksi puolta." Esimerkiksi olennaisesti korkean ulottuvuuden todennäköisyysjakaumien tyypillinen ominaisuus suurdimensionaalisessa tilassa on: satunnaispisteiden neliöetäisyys valittuun pisteeseen on suurella todennäköisyydellä lähellä keskimääräistä (tai mediaania) neliöetäisyyttä. Tämä ominaisuus yksinkertaistaa merkittävästi datan odotettua geometriaa ja suurdimensionaalisen datan indeksointia (siunaus), mutta samalla tekee samankaltaisuuden etsinnän suurissa ulottuvuuksissa vaikeaksi ja jopa hyödyttömäksi (kirous).

Zimek et ai. huomautti, että vaikka ulottuvuuden kirouksen tyypilliset muotoilut vaikuttavat iid- tietoihin, kussakin attribuutissa erotetun datan saaminen on helpompaa myös suurissa mitoissa, ja väitti, että signaali-kohinasuhde on merkitystä: data helpottuu jokaisen attribuutin kanssa, joka lisää signaalin ja vaikeampaa ominaisuuksilla, jotka lisäävät vain melua (merkityksetön virhe) dataan. Erityisesti valvomaton data-analyysi tämä vaikutus tunnetaan suolla.

Languages

In other projects