Ulottuvuuden kirous

Ulottuvuuden kirous (CU) on termi, jota käytetään liittyen useisiin korkeadimensionaalisten tilojen ominaisuuksiin ja kombinatorisiin ongelmiin . Ensinnäkin tämä koskee tarvittavan kokeellisen datan eksponentiaalista kasvua avaruuden ulottuvuudesta riippuen, kun ratkaistaan ​​todennäköisyys-tilastollisen kuviontunnistuksen , koneoppimisen , luokituksen ja erotteluanalyysin ongelmia . Tämä koskee myös kombinatoristen ongelmien vaihtoehtojen lukumäärän eksponentiaalista kasvua lähtötietojen koosta riippuen, mikä johtaa vastaavaan laskenta-algoritmien monimutkaisuuden lisääntymiseen. "Kirous" vaikuttaa myös jatkuviin optimointimenetelmiin moniulotteisen tavoitefunktion monimutkaisuuden vuoksi. Laajemmassa merkityksessä termiä sovelletaan kaikkiin korkeaulotteisten tilojen "epämukaviin" tai epätavallisiin ominaisuuksiin ja niiden tutkimuksen vaikeuksiin. Kombinatoriikassa ne eivät usein tarkoita tilan ulottuvuutta, vaan lähtötiedon kokoa. Erityisesti Ramseyn teorian ongelmissa olisi tarkempaa puhua lähtötiedon '''koon kirouksesta''' myös silloin, kun kyseessä ovat minimaaliset ongelmat - ongelman määrittelevien parametrien lukumäärä. Terminin esitteli ensimmäisenä Richard Bellman liittyen dynaamisen ohjelmoinnin yleiseen ongelmaan [1] [2] . Tätä ilmaisua käytetään edelleen teknistä kybernetiikkaa, koneoppimista ja monimutkaisten järjestelmien analysointia koskevissa teoksissa, myös tieteellisten artikkeleiden otsikoissa [3] .

Tyypillisiä esimerkkejä

• Oletetaan, että meidän on palautettava yksinkertaisimman binaarisen satunnaismuuttujan todennäköisyysjakauma , ja tavoitteemme riittävällä tarkkuudella tämä voidaan tehdä mittausten tai havaintojen otoksesta. Sitten vektorin todennäköisyysjakauman palauttamiseksi binäärisatunnaismuuttujista samalla tarkkuudella tarvitaan näyte mittauksista, mikä usein osoittautuu materiaalikustannusten tai ajan suhteen mahdottomaksi. Binäärisuureiden A- ulotteisella vektorilla on mahdollisia arvoja, ja yritykset palauttaa sen jakautuminen suoraviivaisesti koenäytteen yli ovat lupaamattomia.
• Kombinatoriikassa vaihtoehtojen luetteleminen nykyaikaisissa tietokoneissa on myös mahdotonta. Siksi tarkkoja ratkaisuja NP-vakavimpiin ja monimutkaisempiin ongelmiin voidaan etsiä luetteloimalla vain siinä tapauksessa, että lähtötietojen koko lasketaan useissa kymmenissä graafin pisteissä, vaatimuksissa, laitteissa jne. Se, että jotkut pelit täydelliset tiedot , kuten shakki, tänään kiinnostavat, on seurausta PR.

Tunnistusongelmissa

Todennäköisyystunnistusongelmissa on kaksi tilannetta, joissa ulottuvuuden kirous voidaan voittaa yleisten lähestymistapojen avulla.

1. Tilanne on mahdollinen, kun toisistaan ​​riippuvaisten satunnaismuuttujien vektorin jakauma on keskittynyt pienemmän ulottuvuuden aliavaruuteen, eli vektori voidaan hyvin approksimoida pienemmän muuttujamäärän lineaarifunktiolla. Tässä tapauksessa pääkomponenttimenetelmä mahdollistaa mittasuhteen pienentämisen. Lisäksi tunnistuksen (syrjinnän) asetetut tehtävät voidaan ratkaista jo matalan ulottuvuuden tilassa.
2. Tilanne on mahdollinen, kun tutkittujen vektorien satunnaismuuttujat ovat riippumattomia tai realistisemmin heikosti riippuvaisia ​​toisistaan. Tässä tapauksessa voidaan palauttaa satunnaismuuttujien yksiulotteiset jakaumat ja rakentaa monimuuttujajakaumia niiden tuotteiksi. Edelleen käyttämällä samaa harjoitusnäytettä liukuvassa koemoodissa voidaan palauttaa differentioituvien luokkien todennäköisyysfunktioiden suhteen yksiulotteinen jakauma , mikä eliminoi keskinäiseen riippuvuuteen liittyvän harhan päätöksentekosäännössä.

Yleensä moniulotteisen datan analysointiin ehdotetaan metrisen lähin naapurin menetelmää [4] [5] . Menetelmän etuna on, että muodollisesti sitä voidaan soveltaa minkä kokoisiin näytteisiin riippumatta vektorien dimensiosta. Mutta PR:n pohjimmiltaan sovellettu ongelma on, että rajoitetussa datanäytteessä ei ole tarpeeksi tietoa objektista, jota kuvataan suurella määrällä merkittäviä parametreja. Ja jos tämä kuvaus on todella monimutkainen ja moniulotteinen, ja ongelman ratkaisu vaatii koko parametrikompleksin analyysin, niin ongelma osoittautuu vaikeaksi eikä sitä voida ratkaista yleisillä menetelmillä.

Optimointiongelmat

Optimointitehtävissä on myös menetelmiä, jotka helpottavat suurten ongelmien ratkaisemista.

• Diskreetissä numeroinnin optimointiongelmissa algoritmien ajoaikaa voidaan lyhentää käyttämällä haara- ja sidomenetelmää ja likimääräisiä heuristisia algoritmeja (katso Approksimaalinen polynomiaikakaavio ).
• Gradientin laskeutumisen optimointimenetelmässä useiden muuttujien joidenkin tavoitefunktioiden osalta rotkomenetelmä lisää merkittävästi tehokkuutta. [6]

Kaikki nämä taistelumenetelmät eivät ratkaise PR-ongelmaa radikaalisti ja ovat tehokkaita vain erityistapauksissa.

Ramseyn teoriassa

Vaikka Ramseyn teoriaongelmat yleensä sallivat moniulotteiset yleistykset, ne ovat vaikeita jopa pienillä mitoilla ja pienillä syötetietokooilla.

• Erityisesti Ramsey-lukua R(5,5) ei tunneta - vähimmäiskoko ihmisryhmälle, jossa on 5 hengen ryhmä, jotka joko tuntevat toisensa pareittain tai eivät tunne toisiaan pareittain. Pal Erdős huomautti, että hätätilanteessa ihmiskunta voisi ratkaista tämän ongelman keskittämällä siihen parhaat mielet ja laskentatehoa. Mutta luvun R(6,6) määritelmä on nyky-ihmiskunnan voimien ulkopuolella [7] .
• Szekeres-Erdősin monikulmio-oletus , joka on sekä kombinatorisen geometrian että Ramseyn teorian ongelma, ei ole myöskään todistettu tähän päivään mennessä, edes alkuperäisessä kaksiulotteisessa muotoilussa.

Kombinatorisessa geometriassa

Kombinatorisessa geometriassa on useita vaikeita tiukasti matemaattisia ongelmia, jotka liittyvät suoraan tilan ulottuvuuteen.

• Silmiinpistävin esimerkki on Nelson-Erdős-Hadwigerin ongelma metristen avaruuksien kromaattisesta lukumäärästä. Nykyään (2013) tätä lukua ei tunneta edes dimensiolla 2 olevalle euklidiselle avaruudelle. Tiedetään vain, että tason kromaattinen luku on välillä [5,7] [8] . Toisaalta tälle ongelmalle oli mahdollista todistaa kromaattisen luvun eksponentiaalinen kasvujärjestys suurilla tilamitoilla.
• Toinen vaikea ongelma on Borsukin ongelma . Borsukin arvelu on nyt todistettu korkeintaan 3 mitta-avaruuksille ja kumottu vähintään 65 mitta-avaruuksille. Näin ollen kysymys jää ratkaisematta suurelle avaruusulottuvuuden segmentille. Tässä ongelmassa edes oletettua osion tarvittavan määrän eksponentiaalista kasvua ei ole todistettu.

Jotkut moniulotteisten tilojen "epätavalliset" ominaisuudet

• On helppo nähdä, että jos asetamme minkä tahansa positiivisen , niin moniulotteisen kuution tai pallon tilavuuden murto- osalla rajan -naapurustossa on taipumus olla 1 mittasuhteen rajoittamattomalla lisäyksellä. Siten moniulotteisissa kappaleissa suurin osa tilavuudesta on "lähellä" rajaa. Siksi jopa suurten kokeellisten näytteiden pisteet ovat pääsääntöisesti rajallisia - ne sijaitsevat joko joukon kuperalla rungolla tai lähellä sitä.
• CLT :n mukaan todennäköisyys, että kaksi satunnaisvektoria on normaaleja missä tahansa ennalta määrätyssä positiivisessa virheessä, pyrkii olemaan 1, kun avaruuden ulottuvuus kasvaa.

Muistiinpanot

1. ↑ Richard Ernest Bellman; rand yhtiö. Dynaaminen ohjelmointi  (rajoittamaton) . - Princeton University Press , 1957. - ISBN 978-0-691-07951-6 . ,
   Julkaistu uudelleen: Richard Ernest Bellman. Dynaaminen ohjelmointi  (rajoittamaton) . — Courier Dover Publications , 2003. — ISBN 978-0-486-42809-3 .
2. ↑ Richard Ernest Bellman. Mukautuvat ohjausprosessit : opastettu kierros  . - 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 Lähin naapurihaut ja ulottuvuuden kirous  // IMA J Appl  Math : päiväkirja. - 1979. - Voi. 24 , ei. 1 . - s. 59-70 . - doi : 10.1093/imamat/24.1.59 .
5. ↑ Radovanovic, Miloš; Nanopoulos, Alexandros; Ivanovic, Mirjana. Keskittimet avaruudessa: Suositut lähinaapurit korkeaulotteisessa datassa  //  Journal of Machine Learning Research  : Journal. - 2010. - Vol. 11 . - P. 2487-2531 .
6. ↑ TIEDÄ INTUITTI | Luento | Jyrkin laskeutumismenetelmä. Davidon-Fletcher-Powell menetelmä. Rokon ongelma. Multi-extremaalisuuden ongelma . Haettu 26. huhtikuuta 2022. Arkistoitu alkuperäisestä 27. joulukuuta 2016. (määrätön)
7. ↑ Joel H. Spencer (1994), Ten Lectures on the Probabilistic Method , SIAM , p. 4, ISBN 978-0-89871-325-1 
8. ↑ Aubrey D.N.J. D.E. Grey. Tason kromaattinen luku on vähintään 5  // math.CO. — 2018. Arkistoitu 12. heinäkuuta 2018.