Forbannelse av dimensjonalitet - Curse of dimensionality

Den bann av dimensjonalitet refererer til forskjellige fenomener som oppstår ved å analysere og organisere data i høy-dimensjonale rom som ikke forekommer i lav-dimensjonale innstillinger, slik som den tredimensjonale fysisk plass av hverdag. Uttrykket ble laget av Richard E. Bellman når man vurderte problemer i dynamisk programmering .

Dimensjonalt forbannede fenomener forekommer i domener som numerisk analyse , prøvetaking , kombinatorikk , maskinlæring , datautvinning og databaser . Det vanlige temaet for disse problemene er at når dimensjonaliteten øker, øker volumet på rommet så raskt at tilgjengelige data blir sparsomme. Denne sparsomheten er problematisk for enhver metode som krever statistisk signifikans . For å oppnå et statistisk forsvarlig og pålitelig resultat, vokser datamengden som trengs for å støtte resultatet ofte eksponensielt med dimensjonaliteten. Organisering og søking av data er ofte avhengig av å oppdage områder der objekter danner grupper med lignende egenskaper; i høydimensjonale data ser det imidlertid ut til at alle objekter er sparsomme og forskjellige på mange måter, noe som forhindrer at vanlige dataorganisasjonsstrategier er effektive.

Domener

Kombinatorikk

I noen problemer kan hver variabel ta en av flere diskrete verdier, eller rekkevidden av mulige verdier er delt for å gi et endelig antall muligheter. Tar vi variablene sammen, må et stort antall kombinasjoner av verdier vurderes. Denne effekten er også kjent som den kombinatoriske eksplosjonen . Selv i det enkleste tilfellet av binære variabler, er antallet mulige kombinasjoner allerede eksponentiell i dimensjonaliteten. Naivt dobler hver ekstra dimensjon innsatsen som trengs for å prøve alle kombinasjoner.

Prøvetaking

Det er en eksponentiell økning i volum forbundet med å legge til ekstra dimensjoner til et matematisk rom . For eksempel er 10 2  = 100 jevnt fordelt prøvepunkter tilstrekkelig til å prøve et enhetsintervall (en "1-dimensjonal kube") med ikke mer enn 10 −2 = 0,01 avstand mellom punkter; en ekvivalent prøvetaking av en 10-dimensjonal hyperkube med et gitter som har en avstand på 10 −2 = 0,01 mellom tilstøtende punkter, vil kreve 10 20 = [(10 2 ) 10 ] prøvepunkter. Generelt, med en avstand på 10 - n, ser den 10-dimensjonale hyperkubben ut til å være en faktor på 10 n (10−1) = [(10 n ) 10 / (10 n )] "større" enn den 1-dimensjonale hypercube, som er enhetsintervallet. I eksemplet ovenfor n = 2: Når du bruker en samplingsavstand på 0,01, ser den 10-dimensjonale hyperkubben ut til å være 10 18 "større" enn enhetsintervallet. Denne effekten er en kombinasjon av kombinatoriske problemer ovenfor og avstandsfunksjonsproblemene forklart nedenfor.

Optimalisering

Når du løser dynamiske optimaliseringsproblemer ved numerisk bakoverinduksjon , må objektivfunksjonen beregnes for hver kombinasjon av verdier. Dette er en betydelig hindring når dimensjonen til "tilstandsvariabelen" er stor.

Maskinlæring

I maskinlæringsproblemer som involverer læring av en "state-of-nature" fra et endelig antall datasampler i et høydimensjonalt funksjonsrom med hver funksjon som har en rekke mulige verdier, kreves det typisk en enorm mengde treningsdata for å sikre at det er flere prøver med hver kombinasjon av verdier.

En typisk tommelfingerregel er at det skal være minst 5 treningseksempler for hver dimensjon i representasjonen. I maskinlæring og i den grad prediktiv ytelse er bekymret, brukes forbannelsen av dimensjonalitet om hverandre med toppfenomenet , som også er kjent som Hughes-fenomenet . Dette fenomenet sier at med et fast antall treningsprøver øker den gjennomsnittlige (forventede) prediktive effekten til en klassifiseringsanordning eller regressor først etter hvert som antall dimensjoner eller funksjoner som brukes økes, men utover en viss dimensjonalitet begynner det å forverres i stedet for å forbedre seg jevnt.

Likevel, i sammenheng med en enkel klassifikator ( lineær diskriminantanalyse i den multivariate Gauss-modellen under antagelse om en vanlig kjent kovariansmatrise) Zollanvari et al. viste både analytisk og empirisk at så lenge den relative kumulative effekten av et tilleggsfunksjonssett (med hensyn til funksjoner som allerede er en del av klassifisereren) er større (eller mindre) enn størrelsen på dette tilleggsfunksjonssettet, er den forventede feilen av klassifisereren konstruert ved hjelp av disse tilleggsfunksjonene vil være mindre (eller større) enn den forventede feilen til klassifisereren som er konstruert uten dem. Med andre ord er både størrelsen på tilleggsfunksjoner og deres (relative) kumulative diskriminerende effekt viktig for å observere en reduksjon eller økning i gjennomsnittlig prediktiv kraft.

Avstandsfunksjoner

Når et mål som en euklidisk avstand defineres ved hjelp av mange koordinater, er det liten forskjell i avstandene mellom forskjellige par av prøver.

En måte å illustrere "det enorme" av det høydimensjonale euklidiske rommet er å sammenligne andelen av en innskrevet hypersfære med radius og dimensjon , til andelen av en hypercube med lengdekanter . Volumet til en slik sfære er , hvor er gammafunksjonen , mens kubens volum er . Når dimensjonen til rommet øker, blir hypersfæren et ubetydelig volum i forhold til det til hyperkuben. Dette kan tydelig sees ved å sammenligne proporsjonene når dimensjonen går til uendelig:

som .

Videre er avstanden mellom sentrum og hjørnene , som øker uten å være bundet til fast r. I denne forstand er nesten hele det høydimensjonale rommet "langt borte" fra sentrum. I høye dimensjoner er volumet av d- dimensjoneringsenhetens hyperkube (med koordinater for toppunktene ) konsentrert nær en kule med radien for stor dimensjon d . Faktisk, for hver koordinat er gjennomsnittsverdien av i kuben

.

Avviket for jevn fordeling i kuben er

Derfor har den kvadratiske avstanden fra opprinnelsen gjennomsnittsverdien d / 3 og variansen 4 d / 45. For stor d er fordeling av nær normalfordelingen med gjennomsnittet 1/3 og standardavviket i henhold til sentralgrenseteoremet . Dermed, i høye dimensjoner, er både "midten" av hyperkuben og hjørnene tomme, og alt volumet er konsentrert nær en sfære av "mellom" -radien .

Dette hjelper også til å forstå chi-kvadratfordelingen . Faktisk er den (ikke-sentrale) chi-kvadratiske fordelingen assosiert med et tilfeldig punkt i intervallet [-1, 1] den samme som fordelingen av lengden i kvadrat av et tilfeldig punkt i d- kuben. Etter loven om store tall konsentrerer denne fordelingen seg i et smalt bånd rundt d ganger standardavviket i kvadrat (σ 2 ) til den opprinnelige avledningen. Dette belyser den ki-kvadratiske fordelingen og illustrerer også at det meste av volumet av d- kuben konsentrerer seg nær overflaten av en radiuskule .

En videre utvikling av dette fenomenet er som følger. Enhver fast fordeling på reelle tall induserer en produktfordeling på punkter i ℝ d . For en hvilken som helst fast n viser det seg at minimum og maksimum avstand mellom et tilfeldig referansepunkt Q og en liste over n tilfeldige datapunkter P 1 , ..., P n blir umulig å sammenligne med minimum avstand:

.

Dette blir ofte sitert som avstandsfunksjoner som mister sin nytte (for eksempel nærmeste nabo-kriterium i funksjonssammenligningsalgoritmer) i høye dimensjoner. Nyere forskning har imidlertid vist at dette bare holder i det kunstige scenariet når de endimensjonale distribusjonene ℝ er uavhengige og identisk fordelt . Når attributter er korrelert, kan data bli enklere og gi høyere avstandskontrast, og signal-støy-forholdet ble funnet å spille en viktig rolle, og funksjonsvalg bør derfor brukes.

Nærmeste nabo-søk

Effekten kompliserer nærmeste nabo-søk i høyt dimensjonalt rom. Det er ikke mulig å raskt avvise kandidater ved å bruke forskjellen i en koordinat som en nedre grense for en avstand basert på alle dimensjonene.

Imidlertid har det nylig blitt observert at det bare antall dimensjoner ikke nødvendigvis resulterer i vanskeligheter, siden relevante tilleggsdimensjoner også kan øke kontrasten. I tillegg, for den resulterende rangeringen, er det fortsatt nyttig å se nære og fjerne naboer. Irrelevante ("støy") dimensjoner reduserer imidlertid kontrasten på den måten som er beskrevet ovenfor. I tidsserieanalyser , hvor dataene i seg selv er høydimensjonale, fungerer avstandsfunksjoner også pålitelig så lenge signal-støy-forholdet er høyt nok.

k -næreste naboklassifisering

En annen effekt av høy dimensjonalitet på avstandsfunksjoner gjelder k -næreste nabo ( k -NN) grafer konstruert fra et datasett ved hjelp av en avstandsfunksjon. Som dimensjon øker, indegree fordelingen av k -NN digraph blir forskjøvet med en topp på høyre side på grunn av fremveksten av et uforholdsmessig stort antall knutepunkter , det vil si datapunkter som forekommer i mange flere k -NN lister av annen datapunkter enn gjennomsnittet. Dette fenomenet kan ha en betydelig innvirkning på ulike teknikker for klassifisering (inkludert k -NN klassifiserende ), semi-overvåket læring og klynging , og det påvirker også innhenting av informasjon .

Avviksdeteksjon

I en undersøkelse fra 2012, Zimek et al. identifiserte følgende problemer når vi søkte etter avvik i høydimensjonale data:

  1. Konsentrasjon av poeng og avstander: avledede verdier som avstander blir numerisk like
  2. Irrelevante attributter: i høydimensjonale data kan et betydelig antall attributter være irrelevante
  3. Definisjon av referansesett: for lokale metoder er referansesett ofte nærmeste nabo
  4. Enestående poengsum for forskjellige dimensjoner: forskjellige underområder gir uforlignelige poeng
  5. Tolkning av poeng: poengene gir ofte ikke lenger en semantisk betydning
  6. Eksponensielt søkeområde: søkeområdet kan ikke lenger skannes systematisk
  7. Data snooping bias: gitt det store søkeområdet, kan man finne en hypotese for hver ønsket betydning
  8. Hubness: visse objekter forekommer oftere i nabolister enn andre.

Mange av de analyserte spesialiserte metodene takler en eller annen av disse problemene, men det er fortsatt mange åpne forskningsspørsmål.

Velsignelse av dimensjonalitet

Overraskende og til tross for forventede vanskeligheter med "forbannelse av dimensjonalitet", kan sunn fornuft heuristikk basert på de mest enkle metodene "gi resultater som nesten helt sikkert er optimale" for høydimensjonale problemer. Begrepet "velsignelse av dimensjonalitet" ble introdusert på slutten av 1990-tallet. Donoho forklarte i sitt "Millennium-manifest" tydelig hvorfor "velsignelse av dimensjonalitet" vil danne et grunnlag for fremtidig datautvinning. Effektene av dimensjonalitetens velsignelse ble oppdaget i mange bruksområder og fant grunnlaget i konsentrasjonen av målefenomener . Et eksempel på velsignelsen av dimensjonalitetsfenomenet er lineær separerbarhet av et tilfeldig punkt fra et stort endelig tilfeldig sett med stor sannsynlighet, selv om dette settet er eksponentielt stort: ​​antall elementer i dette tilfeldige settet kan vokse eksponentielt med dimensjonen. Dessuten kan denne lineære funksjonen velges i form av den enkleste lineære Fisher-diskriminanten . Denne skillbarhetssetningen ble bevist for en bred klasse av sannsynlighetsfordelinger: generelle jevnt logg-konkave fordelinger, produktfordelinger i en kube og mange andre familier (nylig omtalt i).

"Velsignelsen av dimensjonalitet og dimensjonalitetens forbannelse er to sider av samme mynt." For eksempel er den typiske egenskapen til i det vesentlige høydimensjonale sannsynlighetsfordelinger i et høyt dimensjonalt rom: den kvadratiske avstanden til tilfeldige punkter til et valgt punkt er, med stor sannsynlighet, nær gjennomsnittlig (eller median) kvadratdistanse. Denne egenskapen forenkler betydelig den forventede geometrien til data og indeksering av høydimensjonale data (velsignelse), men samtidig gjør det likhetssøket i høye dimensjoner vanskelig og til og med ubrukelig (forbannelse).

Zimek et al. bemerkes at mens de typiske formalizations av bann av dimensionality påvirke IId data, har data som er atskilt i hver attributt blir lettere, selv i kraftig dimensjoner, og hevdet at signal-til-støyforholdet forhold: data blir enklere med hvert attributt som legger signal, og vanskeligere med attributter som bare tilfører støy (irrelevant feil) til dataene. Spesielt for uten tilsyn dataanalyse er denne effekten kjent som sumping.

Se også

Referanser