Prokletí Dimenze

Prokletí dimenzionality (CU) je termín používaný v souvislosti s řadou vlastností vysokorozměrných prostorů a kombinatorických problémů . Především se jedná o exponenciální růst potřebných experimentálních dat v závislosti na dimenzi prostoru při řešení problémů pravděpodobnostně-statistického rozpoznávání vzorů , strojového učení , klasifikace a diskriminační analýzy . To platí i pro exponenciální růst počtu možností v kombinatorických úlohách v závislosti na velikosti počátečních dat, což vede k odpovídajícímu zvýšení složitosti výčtových algoritmů. „Prokletí“ také ovlivňuje kontinuální optimalizační metody kvůli složitosti vícerozměrné účelové funkce. V širším slova smyslu se tento termín vztahuje na všechny „nepohodlné“ nebo neobvyklé vlastnosti vysokorozměrných prostorů a na obtíže jejich studia. V kombinatorice často neznamenají rozměr prostoru, ale velikost výchozích dat. Zejména v problémech Ramseyho teorie by bylo přesnější hovořit o '''prokletí velikosti''' počátečních dat i v případě problémů minimálního rozměru - počtu parametrů, které definují problém. Termín poprvé představil Richard Bellman ve vztahu k obecnému problému dynamického programování [1] [2] . Tento výraz se nadále používá v pracích o technické kybernetice, strojovém učení a analýze složitých systémů, včetně názvů vědeckých článků [3] .

Typické příklady

• Předpokládejme, že potřebujeme obnovit rozdělení pravděpodobnosti nejjednodušší binární náhodné veličiny a s přesností dostatečnou pro naše cíle to lze provést ze vzorku měření nebo pozorování. Pak, aby se se stejnou přesností obnovilo rozdělení pravděpodobnosti vektoru z binárních náhodných veličin, je potřeba vzorek z měření, což se často ukazuje jako nepřijatelné z hlediska materiálových nákladů nebo času. A -rozměrný vektor binárních veličin má možné hodnoty a pokusy obnovit jeho distribuci přímočarě na experimentálním vzorku jsou neperspektivní.
• V kombinatorice je výčet možností na moderních počítačích také nemožný. Přesná řešení pro NP-těžké a složitější problémy lze tedy hledat výčtem pouze v případě, kdy je velikost počátečních dat počítána v několika desítkách vrcholů grafu, požadavky, zařízení atd. Skutečnost, že některé hry s úplnými informacemi , jako jsou šachy, dnes jsou zajímavé, je důsledkem PR.

V problémech s rozpoznáváním

V problémech pravděpodobnostního rozpoznávání existují dvě situace, ve kterých lze prokletí dimenzionality překonat pomocí obecných přístupů.

1. Nastává situace, kdy je rozložení vektoru vzájemně závislých náhodných veličin soustředěno do podprostoru nižší dimenze, to znamená, že vektor lze dobře aproximovat lineární funkcí menšího počtu proměnných. V tomto případě metoda hlavní součásti umožňuje zmenšit rozměr. Dále, stanovené úlohy rozpoznávání (diskriminace) lze řešit již v prostoru nízké dimenze.
2. Je možná situace, kdy jsou náhodné veličiny studovaných vektorů nezávislé nebo reálněji na sobě slabě závislé. V tomto případě lze obnovit jednorozměrná rozdělení náhodných proměnných a konstruovat vícerozměrná rozdělení jako jejich produkty. Dále, použitím stejného cvičného vzorku v režimu klouzavé zkoušky je možné obnovit jednorozměrné rozložení poměru pravděpodobnostních funkcí diferencovatelných tříd, což eliminuje zkreslení spojené se vzájemnou závislostí v rozhodovacím pravidle.

Obvykle se pro analýzu vícerozměrných dat navrhuje použít metodu metrického nejbližšího souseda [4] [5] . Výhodou metody je, že ji lze formálně aplikovat na vzorky libovolné velikosti, bez ohledu na rozměr vektorů. Zásadně uplatňovaným problémem PR je ale to, že v omezeném vzorku dat není dostatek informací o objektu popsaném velkým množstvím významných parametrů. A pokud je tento popis skutečně komplexní a vícerozměrný a řešení problému vyžaduje analýzu celého komplexu parametrů, pak se problém ukazuje jako obtížný a nelze jej řešit obecnými metodami.

Problémy s optimalizací

V optimalizačních úlohách existují i ​​metody, které usnadňují řešení rozsáhlých problémů.

• V problémech optimalizace diskrétního výčtu lze zkrátit dobu běhu algoritmů pomocí metody větvení a vazby a přibližných heuristických algoritmů (viz Přibližné polynomiální časové schéma ).
• V optimalizační metodě gradientního klesání pro některé objektivní funkce mnoha proměnných výrazně zvyšuje účinnost roklinová metoda. [6]

Všechny tyto metody boje neřeší problém PR radikálně a jsou účinné pouze ve zvláštních případech.

V Ramseyho teorii

Ačkoli problémy Ramseyovy teorie obvykle umožňují vícerozměrná zobecnění, jsou obtížné i při minimálních rozměrech a malých velikostech vstupních dat.

• Zejména není známo Ramseyho číslo R(5,5) - minimální velikost skupiny lidí, ve které je skupina 5 lidí, kteří se buď znají ve dvojicích, nebo se neznají ve dvojicích. Pal Erdős poznamenal, že v případě nouze by lidstvo mohlo tento problém vyřešit tím, že na něj soustředí nejlepší mozky a výpočetní výkon. Ale definice čísla R(6,6) je nad síly moderního lidstva [7] .
• Szekeres-Erdős polygon dohad , který je jak problém v kombinatorické geometrii a problém v Ramsey teorii, také nebyl dokázaný k tomuto dni, dokonce v originální dvourozměrné formulaci problému.

V kombinatorické geometrii

V kombinatorické geometrii existuje několik obtížných přísně matematických problémů přímo souvisejících s rozměrem prostoru.

• Nejvýraznějším příkladem je Nelson-Erdős-Hadwigerův problém o chromatickém počtu metrických prostorů. Dnes (2013) toto číslo není známo ani pro euklidovský prostor dimenze 2. Ví se pouze, že chromatické číslo roviny je v intervalu [5,7] [8] . Na druhou stranu pro tento problém bylo možné dokázat exponenciální pořadí růstu chromatického čísla pro velké prostorové rozměry.
• Dalším obtížným problémem je problém Borsuk . Borsukova domněnka byla nyní prokázána pro prostory dimenze nejvýše 3 a vyvrácena pro prostory dimenze nejméně 65. Otázka tedy zůstává nevyřešena pro velký segment prostorových dimenzí. V tomto problému se neprokázal ani předpokládaný exponenciální růst potřebného počtu dílů přepážky.

Některé "neobvyklé" vlastnosti vícerozměrných prostorů

• Je snadné vidět, že pokud nastavíme nějaké kladné , pak podíl objemu vícerozměrné krychle nebo koule v sousedství hranice má tendenci k 1 s neomezeným nárůstem rozměru. Ve vícerozměrných tělesech je tedy většina objemu „blízko“ hranice. Proto jsou body i velkých experimentálních vzorků zpravidla hraniční - leží buď na konvexním trupu souboru, nebo blízko něj.
• Podle CLT se pravděpodobnost, že dva náhodné vektory budou normální, v rámci jakékoli předem určené kladné chyby, blíží 1, jak se zvětšuje rozměr prostoru.

Poznámky

1. ↑ Richard Ernest Bellman; rand korporace. Dynamické programování  (neurčité) . - Princeton University Press , 1957. - ISBN 978-0-691-07951-6 . ,
   Znovu publikováno: Richard Ernest Bellman. Dynamické programování  (neurčité) . — Courier Dover Publications , 2003. — ISBN 978-0-486-42809-3 .
2. ↑ Richard Ernest Bellman. Procesy adaptivního řízení : prohlídka s průvodcem  . — Princeton University Press , 1961.
3. ↑ Powell, Warren B. 2007. Přibližné dynamické programování: Řešení kleteb dimenzionality. Wiley, ISBN 0-470-17155-3 .
4. ↑ Marimont, R. B.; Shapiro, MB Hledání nejbližšího souseda a prokletí dimenzionality  // IMA J Appl  Math : deník. - 1979. - Sv. 24 , č. 1 . - str. 59-70 . - doi : 10.1093/imamat/24.1.59 .
5. ↑ Radovanovic, Miloš; Nanopoulos, Alexandros; Ivanovič, Mirjana. Huby ve vesmíru: Populární nejbližší sousedé ve vysokorozměrných datech  //  Journal of Machine Learning Research  : journal. - 2010. - Sv. 11 . - str. 2487-2531 .
6. ↑ POZNEJ INTUIT | Přednáška | Nejstrmější způsob sestupu. Davidon-Fletcher-Powell metoda. Problém rokle. Problém multiextremality . Získáno 26. dubna 2022. Archivováno z originálu dne 27. prosince 2016. (neurčitý)
7. ↑ Joel H. Spencer (1994), Ten Lectures on the Probabilistic Method , SIAM , str. 4, ISBN 978-0-89871-325-1 
8. ↑ Aubrey D.N.J. D.E. Grey. Chromatické číslo roviny je alespoň 5  // math.CO. — 2018. Archivováno 12. července 2018.