Dimensionens forbandelse

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 28. april 2021; checks kræver 4 redigeringer .

Dimensionalitetens forbandelse (CU) er et udtryk, der bruges i relation til en række egenskaber ved højdimensionelle rum og kombinatoriske problemer . Først og fremmest vedrører dette den eksponentielle vækst af de nødvendige eksperimentelle data afhængigt af rummets dimension ved løsning af problemer med probabilistisk-statistisk mønstergenkendelse , maskinlæring , klassificering og diskriminantanalyse . Dette gælder også for den eksponentielle vækst i antallet af muligheder i kombinatoriske problemer afhængigt af størrelsen af de indledende data, hvilket fører til en tilsvarende stigning i kompleksiteten af opregningsalgoritmer. "Forbandelsen" påvirker også kontinuerlige optimeringsmetoder på grund af kompleksiteten af den multidimensionelle objektivfunktion. I en bredere forstand anvendes udtrykket på alle de "ubehagelige" eller usædvanlige egenskaber ved højdimensionelle rum og på vanskelighederne ved deres undersøgelse. I kombinatorik betyder de ofte ikke rummets dimension, men størrelsen af de oprindelige data. Især i problemer med Ramsey-teori ville det være mere præcist at tale om '''størrelsesforbandelsen''' af de indledende data, selv i tilfælde af problemer med minimal dimension - antallet af parametre, der definerer problemet. Udtrykket blev først introduceret af Richard Bellman i relation til det generelle problem med dynamisk programmering [1] [2] . Dette udtryk bliver fortsat brugt i værker om teknisk kybernetik, maskinlæring og analyse af komplekse systemer, herunder i titlerne på videnskabelige artikler [3] .

Typiske eksempler

Antag, at vi skal genoprette sandsynlighedsfordelingen af den enkleste binære tilfældige variabel , og med en nøjagtighed, der er tilstrækkelig til vores mål, kan dette gøres ud fra en stikprøve af målinger eller observationer. Derefter, for at genoprette sandsynlighedsfordelingen af en vektor fra binære tilfældige variabler med samme nøjagtighed, kræves en prøve fra målinger, hvilket ofte viser sig at være uacceptabelt med hensyn til materialeomkostninger eller tid. Den A -dimensionelle vektor af binære mængder har mulige værdier, og forsøg på at genoprette dens fordeling retlinet over den eksperimentelle prøve er ikke lovende. $200=2\cdot 100$ $ti$ $2^{{10}}\cdot 100>10^{5}$ $100$ $2^{{100}}>10^{{30}}$
I kombinatorik er opremsning af muligheder på moderne computere også umulig. Derfor kan nøjagtige løsninger til NP-hårde og mere komplekse problemer kun søges ved opregning i tilfælde, hvor størrelsen af de indledende data beregnes i flere titus af hjørner af grafen, krav, enheder osv. Det faktum, at nogle spil med fuldstændig information , såsom skak, i dag er af interesse, er der en konsekvens af PR. $2^{{100}}$

Problemer med genkendelse

I probabilistiske genkendelsesproblemer er der to situationer, hvor dimensionalitetens forbandelse kan overvindes ved hjælp af generelle tilgange.

En situation er mulig, når fordelingen af en vektor af indbyrdes afhængige stokastiske variable er koncentreret i et underrum med lavere dimension, det vil sige, at vektoren godt kan tilnærmes ved en lineær funktion af et mindre antal variable. I dette tilfælde tillader hovedkomponentmetoden at reducere dimensionen. Yderligere kan de opstillede opgaver med anerkendelse (diskrimination) løses allerede i et rum af lav dimension.
En situation er mulig, når de tilfældige variable for de undersøgte vektorer er uafhængige eller mere realistisk svagt indbyrdes afhængige. I dette tilfælde kan man genoprette endimensionelle fordelinger af stokastiske variable og konstruere multivariate fordelinger som deres produkter. Yderligere kan man ved at bruge den samme træningsprøve i glidende eksamenstilstand genoprette den endimensionelle fordeling af forholdet mellem sandsynlighedsfunktionerne i differentiable klasser, hvilket eliminerer skævheden forbundet med indbyrdes afhængighed i beslutningsreglen.

Normalt, til analyse af multidimensionelle data, foreslås det at bruge den metriske nærmeste nabo-metode [4] [5] . Fordelen ved metoden er, at den formelt kan anvendes på prøver af enhver størrelse, uanset dimensionen af vektorerne. Men det grundlæggende anvendte problem med PR er, at der i et begrænset udsnit af data ikke er nok information om et objekt beskrevet af et stort antal væsentlige parametre. Og hvis denne beskrivelse er virkelig kompleks og multidimensionel, og løsningen af problemet kræver en analyse af hele komplekset af parametre, så viser problemet sig at være vanskeligt og kan ikke løses med generelle metoder.

Optimeringsproblemer

I optimeringsproblemer findes der også metoder, der letter løsningen af store problemer.

I diskrete optællingsoptimeringsproblemer kan køretiden for algoritmer reduceres ved hjælp af branch and bound- metoden og tilnærmede heuristiske algoritmer (se Approximate polynomial time scheme ).
I optimeringsmetoden for gradientnedstigning for nogle objektive funktioner af mange variabler øger ravinemetoden effektiviteten betydeligt. [6]

Alle disse kampmetoder løser ikke problemet med PR radikalt og er kun effektive i særlige tilfælde.

I Ramseys teori

Selvom Ramsey-teoriproblemer normalt tillader multidimensionelle generaliseringer, er de vanskelige selv med minimale dimensioner og små inputdatastørrelser.

Især Ramsey-tallet R(5,5) kendes ikke - minimumsstørrelsen af en gruppe mennesker, hvor der er en gruppe på 5 personer, som enten kender hinanden i par eller ikke kender hinanden i par. Pal Erdős bemærkede, at i nødstilfælde kunne menneskeheden løse dette problem ved at koncentrere de bedste sind og computerkraft om det. Men definitionen af tallet R(6,6) ligger uden for det moderne menneskes magt [7] .
Szekeres-Erdős polygonformodning , som både er et problem i kombinatorisk geometri og et problem i Ramsey-teorien, er heller ikke blevet bevist den dag i dag, selv i den oprindelige todimensionelle formulering af problemet.

I kombinatorisk geometri

I kombinatorisk geometri er der flere vanskelige strengt matematiske problemer direkte relateret til rummets dimension.

Det mest slående eksempel er Nelson-Erdős-Hadwiger-problemet om det kromatiske antal metriske rum. I dag (2013) kendes dette tal ikke engang for det euklidiske rum med dimension 2. Det vides kun, at planets kromatiske tal er i intervallet [5,7] [8] . På den anden side, for dette problem, var det muligt at bevise den eksponentielle rækkefølge for vækst af det kromatiske tal for store rumdimensioner.
Et andet vanskeligt problem er Borsuk-problemet . Borsuks formodning er nu blevet bevist for rum med dimension højst 3 og tilbagevist for rum med dimension mindst 65. Spørgsmålet forbliver således uløst for et stort segment af rumdimensioner. I dette problem er selv den formodede eksponentielle vækst af det nødvendige antal dele af partitionen ikke blevet bevist.

Nogle "usædvanlige" egenskaber ved multidimensionelle rum

Det er let at se, at hvis vi sætter nogen positiv , så har brøkdelen af volumen af en flerdimensionel terning eller kugle i -kvarteret af grænsen en tendens til 1 med en ubegrænset stigning i dimension. I multidimensionelle legemer er det meste af volumen således "nær" grænsen. Derfor er punkterne på selv store eksperimentelle prøver som regel grænse - de ligger enten på sættets konvekse skrog eller tæt på det. $\varepsilon$ $\varepsilon$
Ifølge CLT er sandsynligheden for, at to tilfældige vektorer vil være normale, inden for enhver forudbestemt positiv fejl, tilbøjelig til 1, når rummets dimension øges.

Noter

↑ Richard Ernest Bellman; rand selskab. Dynamisk programmering (ubestemt) . - Princeton University Press , 1957. - ISBN 978-0-691-07951-6 . ,
Genudgivet: Richard Ernest Bellman. Dynamisk programmering (ubestemt) . — Courier Dover Publications , 2003. — ISBN 978-0-486-42809-3 .
↑ Richard Ernest Bellman. Adaptive kontrolprocesser : en guidet tur . — Princeton University Press , 1961.
↑ Powell, Warren B. 2007. Approximate Dynamic Programming: Solving the Curses of Dimensionality. Wiley, ISBN 0-470-17155-3 .
↑ Marimont, R. B.; Shapiro, MB Nearest Neighbor Searches and the Curse of Dimensionality // IMA J Appl Math : journal. - 1979. - Bd. 24 , nr. 1 . - S. 59-70 . - doi : 10.1093/imamat/24.1.59 .
↑ Radovanovic, Miloš; Nanopoulos, Alexandros; Ivanovic, Mirjana. Hubs i rummet: Populære nærmeste naboer i højdimensionelle data // Journal of Machine Learning Research : tidsskrift. - 2010. - Bd. 11 . - P. 2487-2531 .
↑ KEND INTUIT | Foredrag | Den stejleste nedstigningsmetode. Davidon-Fletcher-Powell metode. Kløften problem. Problemet med multi-ekstremalitet . Hentet 26. april 2022. Arkiveret fra originalen 27. december 2016. (ubestemt)
↑ Joel H. Spencer (1994), Ten Lectures on the Probabilistic Method , SIAM , s. 4, ISBN 978-0-89871-325-1
↑ Aubrey D.N.J. D.E. Grey. Flyets kromatiske tal er mindst 5 // math.CO. — 2018. Arkiveret den 12. juli 2018.

Machine learning og data mining
Opgaver	Klassificeringsproblem Læring uden lærer Lærerassisteret læring Regressions analyse AutoML Foreningens regler Feature Extraction Træning af træk Ranking træning Grammatisk afledning Online læring
At lære med en lærer	k-nærmeste nabo metode Naiv Bayes Classifier beslutningstræ Support vektor maskine Lineær regression Logistisk regression perceptron Ensembler af modeller Bagning boostning tilfældig skov Relevant vektormetode
klyngeanalyse	k-betyder metode Fuzzy klyngemetode Hierarkisk klyngedannelse EM algoritme BIRKE HELBREDE DBSCAN OPTIK Middel-forskydning
Dimensionalitetsreduktion	Faktoranalyse Hovedkomponentmetode CCA ICA LDA Ikke-negativ matrixudvidelse t-SNE
Strukturel prognose	Graf probabilistisk model Bayesiansk netværk Skjult Markov-model CRF
Anomali detektion	k-nærmeste nabo metode Lokalt emissionsniveau
Grafer sandsynlighedsmodeller	Bayesiansk netværk Markov netværk Skjult Markov-model
Neurale netværk	Begrænset Boltzmann-maskine selvorganiserende kort Aktiveringsfunktion Sigmoid softmax Radial basisfunktion Rygformeringsmetode Dyb læring Flerlagsperceptron Tilbagevendende neurale netværk lang korttidshukommelse Kontrolleret tilbagevendende blokering Konvolutionelt neuralt netværk U-Net Autoencoder
Forstærkende læring	Markov proces Bellmans ligning Grådig algoritme Q-læring SARSA Temporal forskel (TD)
Teori	Vapnik-Chervonenkis teori Bias-Dispersion Dilemma Beregningsmæssig læringsteori Empirisk risikominimering Occams læring PAC læring Statistisk læringsteori
Tidsskrifter og konferencer	NeurIPS ICML ML JMLR ArXiv:cs.LG