Blestemul dimensiunii

Blestemul dimensionalității (CU) este un termen folosit în relație cu o serie de proprietăți ale spațiilor de dimensiuni mari și probleme combinatorii . În primul rând, aceasta se referă la creșterea exponențială a datelor experimentale necesare în funcție de dimensiunea spațiului atunci când se rezolvă probleme de recunoaștere probabilistic-statistică a modelelor , învățarea automată , clasificarea și analiza discriminantă . Acest lucru se aplică și creșterii exponențiale a numărului de opțiuni în problemele combinatorii în funcție de dimensiunea datelor inițiale, ceea ce duce la o creștere corespunzătoare a complexității algoritmilor de enumerare. „Blestemul” afectează și metodele de optimizare continuă datorită complexității funcției obiectiv multidimensionale. Într-un sens mai larg, termenul se aplică tuturor proprietăților „incomode” sau neobișnuite ale spațiilor cu dimensiuni mari și dificultăților studiului lor. În combinatorică, ele înseamnă adesea nu dimensiunea spațiului, ci dimensiunea datelor inițiale. În special, în problemele teoriei Ramsey ar fi mai corect să vorbim despre „blestemul mărimii” a datelor inițiale chiar și în cazul problemelor de dimensiune minimă – numărul de parametri care definesc problema. Termenul a fost introdus pentru prima dată de Richard Bellman în legătură cu problema generală a programării dinamice [1] [2] . Această expresie continuă să fie folosită în lucrările de cibernetică tehnică, învățarea automată și analiza sistemelor complexe, inclusiv în titlurile articolelor științifice [3] .

Exemple tipice

• Să presupunem că trebuie să restabilim distribuția de probabilitate a celei mai simple variabile aleatoare binare și, cu o precizie suficientă pentru obiectivele noastre, acest lucru se poate face dintr-un eșantion de măsurători sau observații. Apoi, pentru a restabili distribuția de probabilitate a unui vector din variabile aleatoare binare cu aceeași acuratețe, este necesar un eșantion din măsurători, care de multe ori se dovedește a fi inacceptabil din punct de vedere al costurilor materiale sau al timpului. Vectorul A - dimensional al mărimilor binare are valori posibile, iar încercările de a-și restabili distribuția rectiliniu pe eșantionul experimental sunt nepromițătoare.
• În combinatorică, enumerarea opțiunilor pe computerele moderne este, de asemenea, imposibilă. Prin urmare, soluțiile exacte pentru probleme NP-hard și mai complexe pot fi căutate prin enumerare numai în cazul în care dimensiunea datelor inițiale este calculată în câteva zeci de vârfuri ale graficului, cerințe, dispozitive etc. Faptul că unele jocuri cu informații complete , cum ar fi șahul, astăzi sunt de interes, există o consecință a PR.

În probleme de recunoaștere

În problemele de recunoaștere probabilistică, există două situații în care blestemul dimensionalității poate fi depășit cu ajutorul abordărilor generale.

1. Este posibilă o situație când distribuția unui vector de variabile aleatoare interdependente este concentrată într-un subspațiu de dimensiune inferioară, adică vectorul poate fi bine aproximat printr-o funcție liniară a unui număr mai mic de variabile. În acest caz, metoda componentelor principale permite reducerea dimensiunii. Mai mult, sarcinile stabilite de recunoaștere (discriminare) pot fi rezolvate deja într-un spațiu de dimensiuni reduse.
2. Este posibilă o situație când variabilele aleatoare ale vectorilor studiați sunt independente sau, mai realist, slab interdependente. În acest caz, se pot restaura distribuțiile unidimensionale ale variabilelor aleatoare și se pot construi distribuții multivariate ca produse ale acestora. În plus, folosind același eșantion de antrenament în modul de examinare glisante, se poate restabili distribuția unidimensională a raportului funcțiilor de probabilitate ale claselor diferențiabile, ceea ce elimină părtinirea asociată cu interdependența în regula de decizie.

De obicei, pentru analiza datelor multidimensionale, se propune utilizarea metodei metrice a celui mai apropiat vecin [4] [5] . Avantajul metodei este că în mod formal poate fi aplicată probelor de orice dimensiune, indiferent de dimensiunea vectorilor. Dar problema aplicată fundamental a PR este că într-un eșantion limitat de date nu există suficiente informații despre un obiect descris de un număr mare de parametri semnificativi. Și dacă această descriere este cu adevărat complexă și multidimensională, iar rezolvarea problemei necesită o analiză a întregului complex de parametri, atunci problema se dovedește a fi dificilă și nu poate fi rezolvată prin metode generale.

Probleme de optimizare

În problemele de optimizare, există și metode care facilitează rezolvarea problemelor la scară largă.

• În problemele de optimizare a enumerației discrete, timpul de rulare al algoritmilor poate fi redus folosind metoda ramurilor și legate și algoritmi euristici aproximativi (vezi Schema de timp polinomială aproximativă ).
• În metoda de optimizare a coborârii în gradient pentru unele funcții obiective ale multor variabile, metoda râpei crește semnificativ eficiența. [6]

Toate aceste metode de luptă nu rezolvă problema PR-ului în mod radical și sunt eficiente doar în cazuri speciale.

În teoria lui Ramsey

Deși problemele teoriei Ramsey permit de obicei generalizări multidimensionale, ele sunt dificile chiar și cu dimensiuni minime și dimensiuni mici ale datelor de intrare.

• În special, numărul Ramsey R(5,5) nu este cunoscut - dimensiunea minimă a unui grup de oameni în care există un grup de 5 persoane care fie se cunosc în perechi, fie nu se cunosc în perechi. Pal Erdős a remarcat că, în caz de urgență, umanitatea ar putea rezolva această problemă concentrând cele mai bune minți și puterea de calcul asupra ei. Dar definiția numărului R(6,6) este dincolo de puterea omenirii moderne [7] .
• Conjectura poligonului lui Szekeres-Erdő , care este atât o problemă în geometria combinatorie, cât și o problemă în teoria Ramsey, nici nu a fost dovedită până astăzi, chiar și în formularea bidimensională originală a problemei.

În geometria combinatorie

În geometria combinatorie, există câteva probleme dificile strict matematice legate direct de dimensiunea spațiului.

• Cel mai frapant exemplu este problema Nelson-Erdős-Hadwiger asupra numărului cromatic de spații metrice. Astăzi (2013) acest număr nu este cunoscut nici măcar pentru spațiul euclidian de dimensiunea 2. Se știe doar că numărul cromatic al planului este în intervalul [5,7] [8] . Pe de altă parte, pentru această problemă, a fost posibilă demonstrarea ordinii exponențiale de creștere a numărului cromatic pentru dimensiuni spațiale mari.
• O altă problemă dificilă este problema Borsuk . Conjectura lui Borsuk a fost acum dovedită pentru spații cu dimensiunea de cel mult 3 și infirmată pentru spații cu dimensiunea de cel puțin 65. Astfel, întrebarea rămâne nerezolvată pentru un segment mare de dimensiuni spațiale. În această problemă, nici măcar presupusa creștere exponențială a numărului necesar de părți ale partiției nu a fost dovedită.

Câteva proprietăți „neobișnuite” ale spațiilor multidimensionale

• Este ușor de observat că, dacă stabilim orice , atunci fracțiunea de volum a unui cub sau a unei bile multidimensionale din vecinătatea limitei tinde spre 1 cu o creștere nelimitată a dimensiunii. Astfel, în corpurile multidimensionale, cea mai mare parte a volumului este „aproape” de graniță. Prin urmare, punctele chiar și ale eșantioanelor experimentale mari, de regulă, sunt de frontieră - se află fie pe carcasa convexă a setului, fie aproape de aceasta.
• Conform CLT , probabilitatea ca doi vectori aleatori să fie normali, în cadrul oricărei erori pozitive predeterminate, tinde spre 1 pe măsură ce dimensiunea spațiului crește.

Note

1. ↑ Richard Ernest Bellman; corporația rand. Programare dinamică  (nedefinită) . - Princeton University Press , 1957. - ISBN 978-0-691-07951-6 . ,
   Republicat: Richard Ernest Bellman. Programare dinamică  (nedefinită) . — Courier Dover Publications , 2003. — ISBN 978-0-486-42809-3 .
2. ↑ Richard Ernest Bellman. Procese de control adaptiv : un tur ghidat  . — Princeton University Press , 1961.
3. ^ Powell, Warren B. 2007. Approximate Dynamic Programming: Solving the Curses of Dimensionality. Wiley, ISBN 0-470-17155-3 .
4. ↑ Marimont, R. B.; Shapiro, MB Căutările celor mai apropiati vecini și blestemul dimensionalității  // IMA J Appl  Math : jurnal. - 1979. - Vol. 24 , nr. 1 . - P. 59-70 . - doi : 10.1093/imamat/24.1.59 .
5. ↑ Radovanovic, Miloš; Nanopoulos, Alexandros; Ivanovic, Mirjana. Hub-uri în spațiu: cei mai apropiați vecini populari în date cu dimensiuni mari  //  Journal of Machine Learning Research  : jurnal. - 2010. - Vol. 11 . - P. 2487-2531 .
6. ↑ CUNOAȘTE INTUIT | Prelegere | Cea mai abruptă metodă de coborâre. Metoda Davidon-Fletcher-Powell. Problema râpei. Problema multi-extremității . Preluat la 26 aprilie 2022. Arhivat din original la 27 decembrie 2016. (nedefinit)
7. ↑ Joel H. Spencer (1994), Zece Lectures on the Probabilistic Method , SIAM , p. 4, ISBN 978-0-89871-325-1 
8. ↑ Aubrey D.N.J. D.E. Grey. Numărul cromatic al planului este de cel puțin 5  // math.CO. — 2018. Arhivat la 12 iulie 2018.