Dimensionens förbannelse

The Curse of Dimensionality (CU) är en term som används i relation till ett antal egenskaper hos högdimensionella utrymmen och kombinatoriska problem . Först och främst handlar detta om den exponentiella tillväxten av nödvändiga experimentella data beroende på rummets dimension vid lösning av problem med probabilistisk-statistisk mönsterigenkänning , maskininlärning , klassificering och diskriminantanalys . Detta gäller även den exponentiella ökningen av antalet alternativ i kombinatoriska problem beroende på storleken på initialdata, vilket leder till en motsvarande ökning av komplexiteten i uppräkningsalgoritmer. "Förbannelsen" påverkar också kontinuerliga optimeringsmetoder på grund av komplexiteten i den flerdimensionella objektivfunktionen. I en vidare mening tillämpas termen på alla "obekväma" eller ovanliga egenskaper hos högdimensionella utrymmen och på svårigheterna med deras studier. I kombinatorik menar de ofta inte dimensionen av rymden, utan storleken på de initiala data. Speciellt i problem med Ramsey-teorin skulle det vara mer korrekt att tala om "förbannelsen av storlek" för de initiala data även i fallet med problem med minimal dimension - antalet parametrar som definierar problemet. Termen introducerades först av Richard Bellman i relation till det allmänna problemet med dynamisk programmering [1] [2] . Detta uttryck fortsätter att användas i arbeten om teknisk kybernetik, maskininlärning och analys av komplexa system, inklusive i titlarna på vetenskapliga artiklar [3] .

Typiska exempel

• Anta att vi behöver återställa sannolikhetsfördelningen för den enklaste binära slumpvariabeln , och med en noggrannhet som är tillräcklig för våra mål, kan detta göras från ett urval av mätningar eller observationer. För att sedan återställa sannolikhetsfördelningen för en vektor från binära slumpvariabler med samma noggrannhet krävs ett urval från mätningar, vilket ofta visar sig vara oacceptabelt vad gäller materialkostnader eller tid. Den A -dimensionella vektorn av binära kvantiteter har möjliga värden, och försök att återställa dess fördelning rätlinjigt över det experimentella provet är föga lovande.
• Inom kombinatorik är uppräkning av alternativ på moderna datorer också omöjligt. Därför kan exakta lösningar för NP-hårda och mer komplexa problem sökas genom uppräkning endast i det fall då storleken på initialdata beräknas i flera tiotals hörn av grafen, krav, enheter etc. Det faktum att vissa spel med fullständig information , såsom schack, idag är av intresse, det finns en konsekvens av PR.

I igenkänningsproblem

I probabilistiska igenkänningsproblem finns det två situationer där dimensionalitetens förbannelse kan övervinnas med hjälp av allmänna tillvägagångssätt.

1. En situation är möjlig när fördelningen av en vektor av inbördes beroende slumpvariabler är koncentrerad i ett delrum med lägre dimension, det vill säga vektorn kan väl approximeras av en linjär funktion av ett mindre antal variabler. I det här fallet tillåter huvudkomponentmetoden en att minska dimensionen. Vidare kan de uppsatta uppgifterna om erkännande (diskriminering) lösas redan i ett rum av låg dimension.
2. En situation är möjlig när de slumpmässiga variablerna för de studerade vektorerna är oberoende eller, mer realistiskt, svagt beroende av varandra. I detta fall kan man återställa endimensionella fördelningar av slumpvariabler och konstruera multivariata distributioner som deras produkter. Vidare, genom att använda samma träningsprov i glidundersökningsläget, kan man återställa den endimensionella fördelningen av förhållandet mellan sannolikhetsfunktionerna för differentierbara klasser, vilket eliminerar biasen som är förknippad med ömsesidigt beroende i beslutsregeln.

Vanligtvis, för analys av flerdimensionell data, föreslås det att använda den metriska närmaste grannemetoden [4] [5] . Fördelen med metoden är att den formellt sett kan tillämpas på prover av vilken storlek som helst, oavsett dimensionen på vektorerna. Men det fundamentalt tillämpade problemet med PR är att det i ett begränsat urval av data inte finns tillräckligt med information om ett objekt som beskrivs av ett stort antal signifikanta parametrar. Och om denna beskrivning verkligen är komplex och flerdimensionell, och lösningen av problemet kräver en analys av hela komplexet av parametrar, så visar sig problemet vara svårt och kan inte lösas med allmänna metoder.

Optimeringsproblem

I optimeringsproblem finns det även metoder som underlättar lösningen av storskaliga problem.

• I diskreta uppräkningsoptimeringsproblem kan körtiden för algoritmer reduceras med hjälp av förgrenings- och bindningsmetoden och approximativa heuristiska algoritmer (se Ungefärligt polynomtidsschema ).
• I optimeringsmetoden för gradientnedstigning för vissa objektiva funktioner av många variabler, ökar ravinmetoden effektiviteten avsevärt. [6]

Alla dessa kampmetoder löser inte problemet med PR radikalt och är endast effektiva i speciella fall.

I Ramseys teori

Även om Ramsey-teoriproblem vanligtvis tillåter flerdimensionella generaliseringar, är de svåra även med minimala dimensioner och små indatastorlekar.

• Framför allt är Ramsey-talet R(5,5) inte känt - minimistorleken för en grupp människor där det finns en grupp på 5 personer som antingen känner varandra i par eller inte känner varandra i par. Pal Erdős noterade att i nödfall kan mänskligheten lösa detta problem genom att koncentrera de bästa sinnena och datorkraften på det. Men definitionen av talet R(6,6) ligger bortom den moderna mänsklighetens makt [7] .
• Szekeres-Erdős polygonförmodan , som är både ett problem i kombinatorisk geometri och ett problem i Ramsey-teorin, har inte heller bevisats till denna dag, ens i den ursprungliga tvådimensionella formuleringen av problemet.

I kombinatorisk geometri

Inom kombinatorisk geometri finns det flera svåra strikt matematiska problem som är direkt relaterade till rummets dimension.

• Det mest slående exemplet är Nelson-Erdős-Hadwiger-problemet om det kromatiska antalet metriska utrymmen. Idag (2013) är detta nummer inte känt ens för det euklidiska rummet av dimension 2. Det är bara känt att planets kromatiska tal ligger i intervallet [5,7] [8] . Å andra sidan, för detta problem, var det möjligt att bevisa den exponentiella tillväxtordningen för det kromatiska talet för stora rymddimensioner.
• Ett annat svårt problem är Borsuk-problemet . Borsuks gissning har nu bevisats för utrymmen med dimensionen högst 3 och motbevisats för utrymmen med dimensionen minst 65. Frågan förblir således olöst för ett stort segment av utrymmesdimensionerna. I detta problem har inte ens den förmodade exponentiella tillväxten av det erforderliga antalet delar av partitionen bevisats.

Några "ovanliga" egenskaper hos flerdimensionella utrymmen

• Det är lätt att se att om vi sätter någon positiv , så tenderar bråkdelen av volymen av en flerdimensionell kub eller boll i -grannskapet av gränsen till 1 med en obegränsad ökning av dimensionen. Således, i flerdimensionella kroppar, är det mesta av volymen "nära" gränsen. Därför är punkterna för även stora experimentella prover som regel gräns - de ligger antingen på uppsättningens konvexa skrov eller nära den.
• Enligt CLT tenderar sannolikheten att två slumpmässiga vektorer kommer att vara normala, inom varje förutbestämt positivt fel, till 1 när dimensionen av utrymmet ökar.

Anteckningar

1. ↑ Richard Ernest Bellman; rand bolag. Dynamisk programmering  (obestämd tid) . - Princeton University Press , 1957. - ISBN 978-0-691-07951-6 . ,
   Återpublicerad: Richard Ernest Bellman. Dynamisk programmering  (obestämd tid) . — Courier Dover Publications , 2003. — ISBN 978-0-486-42809-3 .
2. ↑ Richard Ernest Bellman. Adaptiva kontrollprocesser : en guidad tur  . — Princeton University Press , 1961.
3. ↑ Powell, Warren B. 2007. Ungefärlig dynamisk programmering: Lösning av dimensionalitetens förbannelser. Wiley, ISBN 0-470-17155-3 .
4. ↑ Marimont, R. B.; Shapiro, MB Nearest Neighbor Searches and the Curse of Dimensionality  // IMA J Appl  Math : journal. - 1979. - Vol. 24 , nr. 1 . - S. 59-70 . - doi : 10.1093/imamat/24.1.59 .
5. ↑ Radovanovic, Miloš; Nanopoulos, Alexandros; Ivanovic, Mirjana. Nav i rymden: Populära närmaste grannar i högdimensionell data  //  Journal of Machine Learning Research  : tidskrift. - 2010. - Vol. 11 . - P. 2487-2531 .
6. ↑ KÄNNA INTUIT | Föreläsning | Den brantaste nedstigningsmetoden. Davidon-Fletcher-Powell-metoden. Ravinproblemet. Problemet med multi-extremalitet . Hämtad 26 april 2022. Arkiverad från originalet 27 december 2016. (obestämd)
7. ↑ Joel H. Spencer (1994), Tio föreläsningar om den probabilistiska metoden , SIAM , sid. 4, ISBN 978-0-89871-325-1 
8. ↑ Aubrey D.N.J. D.E. Grey. Planets kromatiska nummer är minst 5  // math.CO. — 2018. Arkiverad 12 juli 2018.