Blestemul dimensionalității - Curse of dimensionality

Blestemul dimensionalitatii se referă la diferite fenomene care apar atunci când analiza și organizarea datelor în spațiile dimensiuni mari , care nu apar în setările-dimensionale mici , cum ar fi tri-dimensională spațiul fizic al experienței de zi cu zi. Expresia a fost inventată de Richard E. Bellman când a luat în considerare problemele din programarea dinamică .

Fenomenele blestemate dimensional apar în domenii precum analiza numerică , eșantionare , combinatorică , învățare automată , extragere de date și baze de date . Tema obișnuită a acestor probleme este că atunci când dimensionalitatea crește, volumul spațiului crește atât de repede încât datele disponibile devin rare. Această raritate este problematică pentru orice metodă care necesită semnificație statistică . Pentru a obține un rezultat statistic solid și fiabil, cantitatea de date necesară pentru a susține rezultatul crește adesea exponențial odată cu dimensionalitatea. De asemenea, organizarea și căutarea datelor se bazează adesea pe detectarea zonelor în care obiectele formează grupuri cu proprietăți similare; totuși, în datele cu dimensiuni ridicate, toate obiectele par să fie rare și diferite în multe feluri, ceea ce împiedică strategiile comune de organizare a datelor să fie eficiente.

Domenii

Combinatorie

În unele probleme, fiecare variabilă poate lua una din mai multe valori discrete, sau gama de valori posibile este împărțită pentru a da un număr finit de posibilități. Luând variabilele împreună, trebuie luat în considerare un număr mare de combinații de valori. Acest efect este, de asemenea, cunoscut sub numele de explozie combinatorie . Chiar și în cel mai simplu caz de variabile binare, numărul combinațiilor posibile este deja , exponențial în dimensionalitate. Naiv, fiecare dimensiune suplimentară dublează efortul necesar pentru a încerca toate combinațiile. ${\ displaystyle d}$ ${\ displaystyle 2 ^ {d}}$

Prelevarea de probe

Există o creștere exponențială a volumului asociată cu adăugarea unor dimensiuni suplimentare unui spațiu matematic . De exemplu, 10 ² = 100 de puncte de eșantionare distanțate uniform sunt suficiente pentru a preleva un interval de unitate (un "cub 1-dimensional") cu o distanță mai mare de 10 ⁻² = 0,01 între puncte; o eșantionare echivalentă a unui hipercub unitar cu 10 dimensiuni cu o rețea care are o distanță de 10 ^-2 = 0,01 între punctele adiacente ar necesita 10 ²⁰ = [(10 ² ) ¹⁰ ] puncte de eșantionare. În general, cu o distanță de spațiere de 10 ^{- n} hipercubul 10-dimensional pare a fi un factor de 10 ^{n (10−1)} = [(10 ⁿ ) ¹⁰ / (10 ⁿ )] „mai mare” decât 1-dimensional hipercub, care este intervalul unitar. În exemplul de mai sus n = 2: când se utilizează o distanță de eșantionare de 0,01, hipercubul cu 10 dimensiuni pare a fi 10 ¹⁸ "mai mare" decât intervalul unitar. Acest efect este o combinație a problemelor combinatorii de mai sus și a problemelor funcției la distanță explicate mai jos.

Optimizare

La rezolvarea problemelor de optimizare dinamică prin inducție numerică înapoi , funcția obiectivă trebuie calculată pentru fiecare combinație de valori. Acesta este un obstacol semnificativ atunci când dimensiunea „variabilei de stare” este mare.

Învățare automată

În problemele de învățare automată care implică învățarea unei „stări de natură” dintr-un număr finit de eșantioane de date într-un spațiu de dimensiuni ridicate , fiecare caracteristică având o gamă de valori posibile, de obicei este necesară o cantitate enormă de date de instruire pentru a asigura că există mai multe eșantioane cu fiecare combinație de valori.

O regulă tipică este că ar trebui să existe cel puțin 5 exemple de instruire pentru fiecare dimensiune din reprezentare. În învățarea automată și în ceea ce privește performanța predictivă, blestemul dimensionalității este utilizat în mod interschimbabil cu fenomenul de vârf , care este, de asemenea, cunoscut sub numele de fenomen Hughes . Acest fenomen afirmă că, cu un număr fix de probe de antrenament, puterea predictivă medie (așteptată) a unui clasificator sau regresor crește mai întâi pe măsură ce numărul dimensiunilor sau caracteristicilor utilizate este crescut, dar dincolo de o anumită dimensionalitate începe să se deterioreze în loc să se îmbunătățească constant.

Cu toate acestea, în contextul unui clasificator simplu ( analiză liniară discriminantă în modelul Gaussian multivariat sub presupunerea unei matrici comune de covarianță cunoscute) Zollanvari și colab. a arătat atât din punct de vedere analitic, cât și empiric, atât timp cât eficacitatea relativă cumulativă a unui set de caracteristici suplimentare (în ceea ce privește caracteristicile care fac deja parte din clasificator) este mai mare (sau mai mică) decât dimensiunea acestui set de caracteristici suplimentare, eroarea așteptată de clasificatorul construit folosind aceste caracteristici suplimentare va fi mai mic (sau mai mare) decât eroarea așteptată a clasificatorului construit fără ele. Cu alte cuvinte, atât dimensiunea caracteristicilor suplimentare, cât și efectul discriminator cumulativ (relativ) al acestora sunt importante în observarea unei scăderi sau creșteri a puterii predictive medii.

Funcții la distanță

Când o măsură, cum ar fi o distanță euclidiană, este definită folosind multe coordonate, există o diferență mică între distanțele dintre diferite perechi de probe.

O modalitate de a ilustra „vastitatea” spațiului euclidian de înaltă dimensiune este de a compara proporția unei hipersfere inscripționate cu raza și dimensiunea , cu cea a unui hipercub cu margini de lungime . Volumul unei astfel de sfere este , unde este funcția gamma , în timp ce volumul cubului este . Pe măsură ce dimensiunea spațiului crește, hipersfera devine un volum nesemnificativ față de cel al hipercubului. Acest lucru poate fi văzut clar comparând proporțiile pe măsură ce dimensiunea merge la infinit: ${\ 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}

ca .

{\ displaystyle d \ rightarrow \ infty}

Mai mult, distanța dintre centru și colțuri este , care crește fără a fi fixată pentru r fix. În acest sens, aproape tot spațiul de înaltă dimensiune este „departe” de centru. În dimensiuni mari, volumul hipercubului d -dimensional (cu coordonatele vârfurilor ) este concentrat lângă o sferă cu raza pentru dimensiunea mare d . Într-adevăr, pentru fiecare coordonată valoarea medie a în cub este ${\ 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}}}

.

Varianța pentru o distribuție uniformă în cub este ${\ displaystyle x_ {i} ^ {2}}$

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

Prin urmare, distanța pătrată de la origine are valoarea medie d / 3 și varianța 4 d / 45. Pentru d mare , distribuția lui este apropiată de distribuția normală cu media 1/3 și deviația standard în conformitate cu teorema limită centrală . Astfel, în dimensiuni ridicate, atât „mijlocul” hipercubului, cât și colțurile sunt goale, iar tot volumul este concentrat lângă o sferă cu raza „intermediară” . ${\ displaystyle r ^ {2} = \ sum _ {i} x_ {i} ^ {2}}$ ${\ displaystyle r ^ {2} / d}$ ${\ displaystyle {\ frac {2} {\ sqrt {45d}}}}$ ${\ displaystyle {\ sqrt {d / 3}}}$

Acest lucru ajută și la înțelegerea distribuției chi-pătrate . Într-adevăr, distribuția chi-pătrată (non-centrală) asociată unui punct aleatoriu în intervalul [-1, 1] este aceeași cu distribuția pătratului de lungime al unui punct aleatoriu în cubul d . Conform legii numărului mare, această distribuție se concentrează într-o bandă îngustă de aproximativ d ori deviația standard pătrată (σ ² ) a derivării originale. Acest lucru luminează distribuția chi-pătrat și ilustrează, de asemenea, că cea mai mare parte a volumului cubului d se concentrează în apropierea suprafeței unei sfere de rază . ${\ displaystyle \ sigma {\ sqrt {d}}}$

O dezvoltare ulterioară a acestui fenomen este următoarea. Orice distribuție fixă pe numerele reale induce o distribuție a produsului pe puncte în ℝ ^d . Pentru orice n fix , se dovedește că distanța minimă și maximă dintre un punct de referință aleatoriu Q și o listă de n puncte de date aleatoare P ₁ , ..., P _n devin indiscernibile în comparație cu distanța minimă:

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

.

Acest lucru este adesea citat ca funcțiile la distanță își pierd utilitatea (pentru criteriul cel mai apropiat vecin în algoritmi de comparație a caracteristicilor, de exemplu) în dimensiuni ridicate. Cu toate acestea, cercetările recente au arătat că acest lucru este valabil doar în scenariul artificial atunci când distribuțiile unidimensionale ℝ sunt independente și distribuite identic . Atunci când atributele sunt corelate, datele pot deveni mai ușoare și pot oferi un contrast mai mare la distanță, iar raportul semnal-zgomot a jucat un rol important, astfel ar trebui folosită selectarea caracteristicilor .

Cea mai apropiată căutare a vecinilor

Efectul complică căutarea celui mai apropiat vecin în spațiul cu dimensiuni mari. Nu este posibil să respingeți rapid candidații utilizând diferența într-o coordonată ca limită inferioară pentru o distanță bazată pe toate dimensiunile.

Cu toate acestea, sa observat recent că simplul număr de dimensiuni nu duce neapărat la dificultăți, deoarece dimensiunile suplimentare relevante pot crește și contrastul. În plus, pentru clasamentul rezultat rămâne util să discerneți vecinii apropiați și îndepărtați. Dimensiunile irelevante („zgomot”) reduc totuși contrastul în modul descris mai sus. În analiza seriilor temporale , în care datele sunt inerent de înaltă dimensiune, funcțiile de distanță funcționează și în mod fiabil, atât timp cât raportul semnal-zgomot este suficient de mare.

k -cea mai apropiată clasificare a vecinilor

Un alt efect al dimensionalitatii de mare distanță asupra funcțiilor se referă la k -nearest vecin ( k -NN) grafice construite dintr - un set de date folosind o funcție de distanță. Pe măsură ce dimensiunea crește, distribuția neclasificată a digrafului k -NN devine înclinată cu un vârf în dreapta datorită apariției unui număr disproporționat de hub-uri , adică puncte de date care apar în multe alte liste k -NN ale altor puncte de date decât media. Acest fenomen poate avea un impact considerabil asupra diferitelor tehnici de clasificare (inclusiv clasificatorul k- NN ), învățarea semi-supravegheată și gruparea și afectează și recuperarea informațiilor .

Detectarea anomaliilor

Într-un sondaj din 2012, Zimek și colab. a identificat următoarele probleme la căutarea anomaliilor în date de înaltă dimensiune:

Concentrarea scorurilor și distanțelor: valorile derivate, cum ar fi distanțele, devin similare numeric
Atribute irelevante: în datele cu dimensiuni ridicate, un număr semnificativ de atribute pot fi irelevante
Definiția seturilor de referință: pentru metodele locale, seturile de referință sunt adesea bazate pe cel mai apropiat vecin
Scoruri incomparabile pentru diferite dimensiuni: subspatii diferite produc scoruri incomparabile
Interpretabilitatea scorurilor: scorurile adesea nu mai transmit un sens semantic
Spațiu de căutare exponențial: spațiul de căutare nu mai poate fi scanat sistematic
Tendința de snooping a datelor : având în vedere spațiul mare de căutare, pentru fiecare semnificație dorită poate fi găsită o ipoteză
Hubness: anumite obiecte apar mai frecvent în listele de vecini decât altele.

Multe dintre metodele specializate analizate abordează una sau alta dintre aceste probleme, dar rămân multe întrebări deschise de cercetare.

Binecuvântarea dimensionalității

În mod surprinzător și în ciuda dificultăților „blestemului dimensionalității” așteptate, euristicile de bun simț bazate pe cele mai simple metode „pot produce rezultate care sunt aproape sigur optime” pentru problemele cu dimensiuni ridicate. Termenul „binecuvântare a dimensionalității” a fost introdus la sfârșitul anilor '90. Donoho în „Manifestul Millennium” a explicat în mod clar de ce „binecuvântarea dimensionalității” va forma baza viitoarei exploatări de date. Efectele binecuvântării dimensionalității au fost descoperite în multe aplicații și și-au găsit fundamentul în concentrarea fenomenelor de măsură . Un exemplu al fenomenului de binecuvântare a dimensionalității este separabilitatea liniară a unui punct aleatoriu de un set mare aleator finit cu probabilitate mare chiar dacă acest set este exponențial mare: numărul de elemente din acest set aleator poate crește exponențial cu dimensiunea. Mai mult, această funcționalitate liniară poate fi selectată sub forma celui mai simplu discriminant liniar Fisher . Această teoremă a separabilității a fost dovedită pentru o clasă largă de distribuții de probabilitate: distribuții generale log-concav, distribuții de produse într-un cub și multe alte familii (revizuite recent în).

„Binecuvântarea dimensionalității și blestemul dimensionalității sunt două fețe ale aceleiași monede.” De exemplu, proprietatea tipică a distribuțiilor de probabilitate esențial de înaltă dimensiune într-un spațiu de înaltă dimensiune este: distanța pătrată a punctelor aleatorii la un punct selectat este, cu probabilitate mare, apropiată de distanța pătrată medie (sau mediană). Această proprietate simplifică semnificativ geometria așteptată a datelor și indexarea datelor de înaltă dimensiune (binecuvântare), dar, în același timp, face căutarea similarității în dimensiuni ridicate dificilă și chiar inutilă (blestem).

Zimek și colab. a remarcat faptul că, în timp ce formalizările tipice ale blestemului dimensionalității afectează datele iid , având date care sunt separate în fiecare atribut devine mai ușor chiar și în dimensiunile ridicate și a susținut că raportul semnal-zgomot contează: datele devin mai ușoare cu fiecare atribut care adaugă semnal și mai greu cu atribute care adaugă doar zgomot (eroare irelevantă) la date. În special pentru analiza datelor nesupravegheate, acest efect este cunoscut sub numele de swamping.

Languages

In other projects