Prokletí Dimenze
Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od
verze recenzované 28. dubna 2021; kontroly vyžadují
4 úpravy .
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ů.
- 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.
- 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š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
- ↑ 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 .
- ↑ Richard Ernest Bellman. Procesy adaptivního řízení : prohlídka s průvodcem . — Princeton University Press , 1961.
- ↑ Powell, Warren B. 2007. Přibližné dynamické programování: Řešení kleteb dimenzionality. Wiley, ISBN 0-470-17155-3 .
- ↑ 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 .
- ↑ 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 .
- ↑ 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ý)
- ↑ Joel H. Spencer (1994), Ten Lectures on the Probabilistic Method , SIAM , str. 4, ISBN 978-0-89871-325-1
- ↑ Aubrey D.N.J. D.E. Grey. Chromatické číslo roviny je alespoň 5 // math.CO. — 2018. Archivováno 12. července 2018.