Förbannelse av dimensionalitet - Curse of dimensionality

Den förbannelse dimension avser olika fenomen som uppstår när analysera och organisera data i hög-dimensionell utrymmen som inte förekommer i låga dimensionella inställningar såsom tredimensionella fysiskt utrymme i det dagliga erfarenhet. Uttrycket myntades av Richard E. Bellman när man övervägde problem med dynamisk programmering .

Dimensionellt förbannade fenomen förekommer i domäner som numerisk analys , provtagning , kombinatorik , maskininlärning , datautvinning och databaser . Det vanliga temat för dessa problem är att när dimensionaliteten ökar, ökar volymen i utrymmet så snabbt att de tillgängliga data blir glesa. Denna gleshet är problematisk för alla metoder som kräver statistisk signifikans . För att få ett statistiskt sundt och tillförlitligt resultat växer mängden data som behövs för att stödja resultatet ofta exponentiellt med dimensionaliteten. Organisering och sökning av data förlitar sig ofta på att detektera områden där objekt bildar grupper med liknande egenskaper; i högdimensionell data verkar emellertid alla objekt vara glesa och olika på många sätt, vilket förhindrar att vanliga dataorganisationsstrategier blir effektiva.

Domäner

Kombinatorik

I vissa problem kan varje variabel ta ett av flera diskreta värden, eller så kan antalet värden delas för att ge ett begränsat antal möjligheter. Om man tar variablerna ihop måste ett stort antal kombinationer av värden beaktas. Denna effekt är också känd som den kombinatoriska explosionen . Även i det enklaste fallet med binära variabler är antalet möjliga kombinationer redan exponentiellt i dimensionaliteten. Naivt fördubblar varje ytterligare dimension den ansträngning som krävs för att prova alla kombinationer. ${\ displaystyle d}$ ${\ displaystyle 2 ^ {d}}$

Provtagning

Det finns en exponentiell volymökning i samband med att lägga till extra dimensioner i ett matematiskt utrymme . Exempelvis räcker 10 ² = 100 jämnt fördelade samplingspunkter för att sampla ett enhetsintervall (en "1-dimensionell kub") med högst 10 ^-2 = 0,01 avstånd mellan punkterna; en ekvivalent provtagning av en 10-dimensionell enhetshyperkub med ett galler som har ett avstånd på 10 ⁻² = 0,01 mellan intilliggande punkter skulle kräva 10 ²⁰ = [(10 ² ) ¹⁰ ] provpunkter. I allmänhet, med ett avståndsavstånd på 10 ^{- n} verkar den 10-dimensionella hyperkuben vara en faktor 10 ^{n (10−1)} = [(10 ⁿ ) ¹⁰ / (10 ⁿ )] "större" än den 1-dimensionella hypercube, vilket är enhetsintervallet. I exemplet ovan n = 2: vid användning av ett samplingsavstånd på 0,01 verkar det 10-dimensionella hyperkuben vara 10 ¹⁸ "större" än enhetsintervallet. Denna effekt är en kombination av kombinationsproblemen ovan och distansfunktionsproblemen som förklaras nedan.

Optimering

När man löser dynamiska optimeringsproblem genom numerisk bakåtinduktion måste objektivfunktionen beräknas för varje kombination av värden. Detta är ett betydande hinder när dimensionen hos "tillståndsvariabeln" är stor.

Maskininlärning

I maskininlärningsproblem som involverar inlärning av ett "naturligt tillstånd" från ett begränsat antal dataprover i ett högdimensionellt funktionsutrymme, varvid varje funktion har ett antal möjliga värden, vanligtvis krävs en enorm mängd träningsdata för att säkerställa att det finns flera prover med varje kombination av värden.

En typisk tumregel är att det ska finnas minst 5 träningsexempel för varje dimension i representationen. I maskininlärning och i den mån det gäller prediktiv prestanda används dimensionens förbannelse utbytbart med toppfenomenet , som också kallas Hughes-fenomenet . Detta fenomen säger att med ett fast antal träningsprover ökar den genomsnittliga (förväntade) prediktiva effekten hos en klassificerare eller regressor först när antalet dimensioner eller funktioner som används ökas men bortom en viss dimensionalitet börjar det försämras istället för att förbättras stadigt.

I sammanhanget med en enkel klassificering ( linjär diskriminantanalys i den multivariata Gaussiska modellen under antagande av en gemensam känd kovariansmatris) Zollanvari et al. visade både analytiskt och empiriskt att så länge den relativa kumulativa effekten av en ytterligare funktionsuppsättning (med avseende på funktioner som redan ingår i klassificeraren) är större (eller mindre) än storleken på denna ytterligare funktionsuppsättning, är det förväntade klassificeraren konstruerad med hjälp av dessa ytterligare funktioner kommer att vara mindre (eller större) än det förväntade felet för klassificeraren konstruerad utan dem. Med andra ord är både storleken på ytterligare funktioner och deras (relativa) kumulativa diskriminerande effekt viktiga för att observera en minskning eller ökning av den genomsnittliga prediktiva effekten.

Avståndsfunktioner

När ett mått som ett euklidiskt avstånd definieras med hjälp av många koordinater är det liten skillnad i avstånden mellan olika par av prover.

Ett sätt att illustrera "storheten" i det högdimensionella euklidiska utrymmet är att jämföra andelen av en inskriven hypersfär med radie och dimension , till en hyperkub med längdkanter. Volymen på en sådan sfär är , var är gammafunktionen , medan kubens volym är . När rymdens dimension ökar blir hypersfären en obetydlig volym i förhållande till hyperkubens. Detta kan tydligt ses genom att jämföra proportionerna när dimensionen går till oändligheten: ${\ 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)}} \ rightarrow 0}

som .

{\ displaystyle d \ rightarrow \ infty}

Vidare är avståndet mellan centrum och hörnen , vilket ökar utan begränsning för fast r. I den meningen är nästan hela det högdimensionella utrymmet "långt borta" från centrum. I höga dimensioner koncentreras volymen för hypercube d -dimensionell enhet (med koordinater för hörnpunkterna ) nära en sfär med radien för stor dimension d . Faktum är att för varje koordinat är medelvärdet i kuben ${\ 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}}}

.

Variansen för enhetlig fördelning i kuben är ${\ displaystyle x_ {i} ^ {2}}$

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

Därför har kvadratavståndet från ursprunget medelvärdet d / 3 och variansen 4 d / 45. För stora d är fördelningen av nära normalfördelningen med medelvärdet 1/3 och standardavvikelsen enligt den centrala gränssatsen . Således, i höga dimensioner, är både "mitten" av hyperkuben och hörnen tomma, och hela volymen koncentreras nära en sfär med "mellanliggande" radie . ${\ displaystyle r ^ {2} = \ sum _ {i} x_ {i} ^ {2}}$ ${\ displaystyle r ^ {2} / d}$ ${\ displaystyle {\ frac {2} {\ sqrt {45d}}}}$ ${\ displaystyle {\ sqrt {d / 3}}}$

Detta hjälper också till att förstå chi-kvadratfördelningen . Faktum är att den (icke-centrala) chi-kvadratiska fördelningen associerad med en slumpmässig punkt i intervallet [-1, 1] är densamma som fördelningen av längden i kvadrat för en slumpmässig punkt i d- kuben. Enligt lagen om stora tal koncentrerar sig denna fördelning i ett smalt band runt d gånger standardavvikelsen i kvadrat (σ ² ) för den ursprungliga härledningen. Detta belyser den chi-kvadratiska fördelningen och illustrerar också att det mesta av volymen på d- kuben koncentreras nära ytan av en radiesfär . ${\ displaystyle \ sigma {\ sqrt {d}}}$

En vidareutveckling av detta fenomen är som följer. Varje fast fördelning på de verkliga siffrorna inducerar en produktfördelning på punkter i ℝ ^d . För varje fast n , visar det sig att den minsta och det största avståndet mellan en slumpmässig referenspunkt Q och en lista med n slumpvis datapunkter P ₁ , ..., P _n bli urskiljbara jämfört med det minsta avståndet:

{\ displaystyle \ lim _ {d \ to \ infty} E \ left ({\ frac {\ operatorname {dist} _ {\ max} (d) - \ operatorname {dist} _ {\ min} (d)} { \ operatorname {dist} _ {\ min} (d)}} \ right) \ to 0}

.

Detta citeras ofta som avståndsfunktioner som förlorar sin användbarhet (för närmaste grannskriteriet i exempelvis funktionsjämförelsealgoritmer) i höga dimensioner. Ny forskning har dock visat att detta bara gäller i det artificiella scenariot när de endimensionella fördelningarna ℝ är oberoende och identiskt fördelade . När attribut är korrelerade kan data bli enklare och ge högre avståndskontrast och signal-brusförhållandet visade sig spela en viktig roll, så funktionsval bör användas.

Närmaste grannsökning

Effekten komplicerar närmaste grannsökning i högdimensionellt utrymme. Det är inte möjligt att snabbt avvisa kandidater genom att använda skillnaden i en koordinat som en nedre gräns för ett avstånd baserat på alla dimensioner.

Det har emellertid nyligen observerats att endast antalet dimensioner inte nödvändigtvis leder till svårigheter, eftersom relevanta ytterligare dimensioner också kan öka kontrasten. Dessutom för den resulterande rankningen är det fortfarande användbart att urskilja nära och långt grannar. Irrelevanta ("brus") dimensioner minskar emellertid kontrasten på det sätt som beskrivs ovan. Vid tidsserieanalys , där data i sig är högdimensionella, fungerar avståndsfunktioner också tillförlitligt så länge signal-brusförhållandet är tillräckligt högt.

k- närmaste grannklassificering

En annan effekt av högdimensionalitet på avståndsfunktioner gäller k -närsta grann- ( k -NN) -diagram konstruerade från en datamängd med hjälp av en avståndsfunktion. Som dimensionen ökar, indegree fördelningen av k -NN digraph blir skev med en topp till höger på grund av uppkomsten av ett oproportionerligt stort antal knutpunkter , dvs data-punkter som visas i många fler k -NN listor över andra datapunkter än genomsnittet. Detta fenomen kan ha en avsevärd inverkan på olika tekniker för klassificering (inklusive k -NN-klassificeraren ), halvövervakad inlärning och kluster , och det påverkar också informationshämtningen .

Avvikelse upptäckt

I en undersökning från 2012, Zimek et al. identifierade följande problem vid sökning efter avvikelser i högdimensionell data:

Koncentration av poäng och avstånd: härledda värden som avstånd blir numeriskt lika
Irrelevanta attribut: i högdimensionella data kan ett betydande antal attribut vara irrelevanta
Definition av referensuppsättningar: för lokala metoder är referensuppsättningar ofta närmaste grannbaserade
Ojämförliga poäng för olika dimensioner: olika delområden ger ojämförliga poäng
Tolkning av poäng: poängen förmedlar ofta inte längre en semantisk betydelse
Exponentiellt sökutrymme: sökutrymmet kan inte längre systematiskt skannas
Data snooping bias: med tanke på det stora sökutrymmet kan en hypotes hittas för varje önskad betydelse
Hubness: vissa objekt förekommer oftare i grannlistor än andra.

Många av de analyserade specialiserade metoderna hanterar ett eller annat av dessa problem, men det finns fortfarande många öppna forskningsfrågor.

Välsignelse av dimensionalitet

Överraskande och trots de förväntade svårigheterna med "förbannelse av dimensionalitet" kan sunt förnuft heuristik baserat på de mest enkla metoderna "ge resultat som nästan säkert är optimala" för högdimensionella problem. Uttrycket "dimensionalitetens välsignelse" introducerades i slutet av 1990-talet. Donoho förklarade i sitt "Millenniummanifest" tydligt varför "dimensionens välsignelse" kommer att utgöra en grund för framtida datautvinning. Effekterna av dimensioneringens välsignelse upptäcktes i många applikationer och fann sin grund i koncentrationen av måttfenomen . Ett exempel på dimensioneringens välsignelse är linjär separering av en slumpmässig punkt från en stor slutlig slumpmässig uppsättning med hög sannolikhet även om denna uppsättning är exponentiellt stort: antalet element i denna slumpmässiga uppsättning kan växa exponentiellt med dimension. Dessutom kan denna linjära funktion väljas i form av den enklaste linjära Fisher-diskriminanten . Denna separationssats bevisades för en bred klass av sannolikhetsfördelningar: allmänna enhetligt log-konkava fördelningar, produktfördelningar i en kub och många andra familjer (granskades nyligen i).

"Välsignelsen av dimensionalitet och dimensionens förbannelse är två sidor av samma mynt." Till exempel är den typiska egenskapen för väsentligen högdimensionell sannolikhetsfördelning i ett högdimensionellt utrymme: det kvadratiska avståndet av slumpmässiga punkter till en vald punkt är med hög sannolikhet nära det genomsnittliga (eller median) kvadratavståndet. Den här egenskapen förenklar avsevärt den förväntade geometrin för data och indexering av högdimensionella data (välsignelse), men samtidigt gör det likhetssökningen i höga dimensioner svår och till och med värdelös (förbannelse).

Zimek et al. noterade att även om de typiska formaliseringarna av dimensionens förbannelse påverkar iid- data, blir det lättare att ha data som är separerade i varje attribut även i höga dimensioner, och hävdade att signal-brus-förhållandet betyder något: data blir lättare för varje attribut som lägger till signal och hårdare med attribut som bara lägger till brus (irrelevant fel) till data. I synnerhet för icke-övervakad dataanalys kallas denna effekt som swamping.

Languages

In other projects