A dimenzió átka

A dimenziósság átka (CU) a nagydimenziós terek számos tulajdonságával és kombinatorikai problémákkal kapcsolatos kifejezés . Ez mindenekelőtt a szükséges kísérleti adatok exponenciális növekedését érinti a tér dimenziójától függően a valószínűségi-statisztikai mintafelismerés , a gépi tanulás , az osztályozás és a diszkriminanciaanalízis problémáinak megoldása során . Ez vonatkozik a kombinatorikus feladatokban a kiindulási adatok méretétől függő opciók számának exponenciális növekedésére is, ami a felsorolási algoritmusok bonyolultságának megfelelő növekedéséhez vezet. Az „átok” a folyamatos optimalizálási módszerekre is vonatkozika többdimenziós célfüggvény összetettsége miatt. Tágabb értelemben ezt a kifejezést a nagy dimenziós terek összes "kényelmetlen" vagy szokatlan tulajdonságára és tanulmányozásuk nehézségeire alkalmazzák. A kombinatorikában gyakran nem a tér dimenzióját, hanem a kiindulási adatok méretét jelentik. Különösen a Ramsey-elmélet problémáinál pontosabb lenne a kiindulási adatok '''méretátkáról''' beszélni, még akkor is, ha a problémák minimális méretűek – a problémát meghatározó paraméterek száma. A kifejezést először Richard Bellman vezette be a dinamikus programozás általános problémájával kapcsolatban [1] [2] . Ezt a kifejezést továbbra is használják a technikai kibernetikával, a gépi tanulással és az összetett rendszerek elemzésével foglalkozó munkákban, beleértve a tudományos cikkek címét is [3] .

Tipikus példák

• Tegyük fel, hogy vissza kell állítanunk a legegyszerűbb bináris valószínűségi változó valószínűségi eloszlását , és a céljaink eléréséhez elegendő pontossággal ezt megtehetjük mérések vagy megfigyelések mintájából. Ezután egy vektor valószínűségi eloszlásának helyreállításához bináris valószínűségi változókból ugyanolyan pontossággal mérésekből vett mintára van szükség, ami gyakran elfogadhatatlan anyagköltség vagy idő szempontjából. A bináris mennyiségek A -dimenziós vektorának vannak lehetséges értékei, és a kísérleti mintán belüli eloszlásának egyenes vonalú helyreállítására tett kísérletek kilátástalanok.
• A kombinatorikában a lehetőségek felsorolása sem lehetséges a modern számítógépeken. Emiatt az NP-nehéz és összetettebb problémákra csak abban az esetben lehet pontos megoldást keresni felsorolással, ha a kiindulási adatok nagyságát a gráf több tíz csúcsában, követelményekben, eszközökben stb. számítják. Az a tény, hogy egyes játékok teljes körű információval , mint például a sakk, ma az érdeklődés, van egy következménye a PR.

Felismerési problémákban

A valószínűségi felismerési problémákban két olyan szituáció van, amelyekben a dimenzionalitás átka általános megközelítések segítségével legyőzhető.

1. Olyan helyzet lehetséges, amikor az egymástól függő valószínűségi változók vektorának eloszlása ​​egy kisebb dimenziójú altérben koncentrálódik, vagyis a vektor jól közelíthető egy kisebb számú változó lineáris függvényével. Ebben az esetben a főkomponens módszer lehetővé teszi a méret csökkentését. Továbbá az elismerés (diszkrimináció) kitűzött feladatai már alacsony dimenziójú térben is megoldhatók.
2. Olyan helyzet jöhet létre, amikor a vizsgált vektorok valószínűségi változói függetlenek, vagy reálisabban, gyengén függnek egymástól. Ebben az esetben visszaállíthatjuk a valószínűségi változók egydimenziós eloszlását, és többváltozós eloszlásokat állíthatunk elő ezek szorzataként. Továbbá, ugyanazt a betanítási mintát használva csúszó vizsgamódban, visszaállíthatjuk a differenciálható osztályok valószínűségi függvényeinek arányának egydimenziós eloszlását , ami kiküszöböli a döntési szabályban az egymásra utaltsághoz kapcsolódó torzítást.

Többdimenziós adatok elemzéséhez általában a metrikus legközelebbi szomszéd módszer alkalmazása javasolt [4] [5] . A módszer előnye, hogy formálisan bármilyen méretű mintára alkalmazható, a vektorok méretétől függetlenül. A PR alapvetően alkalmazott problémája azonban az, hogy egy korlátozott adatmintában nincs elegendő információ egy nagyszámú jelentős paraméterrel leírt objektumról. És ha ez a leírás valóban összetett és többdimenziós, és a probléma megoldásához a paraméterek teljes komplexumának elemzése szükséges, akkor a probléma nehéznek bizonyul, és általános módszerekkel nem oldható meg.

Optimalizálási problémák

Az optimalizálási feladatokban vannak olyan módszerek is, amelyek nagy léptékű problémák megoldását segítik elő.

• A diszkrét felsorolás optimalizálási feladatokban az algoritmusok futási ideje csökkenthető az elágazó és kötött módszerrel , valamint a közelítő heurisztikus algoritmusokkal (lásd: Hozzávetőleges polinomiális időséma ).
• A gradiens süllyedés optimalizálási módszerében számos változó egyes célfüggvényeire a szakadékos módszer jelentősen növeli a hatékonyságot. [6]

Mindezek a harci módszerek nem oldják meg radikálisan a PR problémáját, és csak speciális esetekben hatékonyak.

Ramsey elméletében

Bár a Ramsey-elméleti problémák általában többdimenziós általánosításokat tesznek lehetővé, még minimális méretek és kis bemeneti adatok esetén is nehézkesek.

• Különösen az R(5,5) Ramsey-szám nem ismert - egy olyan embercsoport minimális mérete, amelyben van egy 5 fős csoport, akik vagy párban ismerik egymást, vagy párban nem ismerik egymást. Erdős Pál megjegyezte, hogy vészhelyzet esetén az emberiség úgy tudja megoldani ezt a problémát, hogy a legjobb elméket és számítási teljesítményt rákoncentrálja. De az R(6,6) szám meghatározása meghaladja a modern emberiség erejét [7] .
• A Szekeres-Erdős poligon sejtés , amely egyszerre probléma a kombinatorikus geometriában és a Ramsey-elméletben, szintén a mai napig nem bizonyított, még a probléma eredeti, kétdimenziós megfogalmazásában sem.

A kombinatorikus geometriában

A kombinatorikus geometriában számos nehéz, szigorúan matematikai probléma van, amely közvetlenül kapcsolódik a tér dimenziójához.

• A legszembetűnőbb példa a Nelson-Erdős-Hadwiger probléma a metrikus terek kromatikus számával kapcsolatban. Ma (2013) ez a szám még a 2-es dimenziójú euklideszi térre sem ismert. Csak azt tudjuk, hogy a sík kromatikus száma az [5,7] [8] intervallumban van . Másrészt ennél a feladatnál sikerült igazolni a kromatikus szám exponenciális növekedési sorrendjét nagy térméreteknél.
• Egy másik nehéz probléma a Borsuk probléma . Borsuk sejtése mostanra a legfeljebb 3-as dimenziójú terekre bebizonyosodott, és a legalább 65-ös dimenziójú terekre megcáfolva. Így a kérdés a térdimenziók nagy szegmensére nézve megoldatlan marad. Ebben a feladatban még a partíció szükséges számú részeinek feltételezett exponenciális növekedése sem bizonyított.

A többdimenziós terek néhány "szokatlan" tulajdonsága

• Könnyen belátható, hogy ha tetszőleges pozitívat állítunk be , akkor egy többdimenziós kocka vagy golyó térfogatának a határ -környezetében lévő hányada 1-re hajlik, korlátlan méretnövekedéssel. Így a többdimenziós testekben a térfogat nagy része "közel" van a határhoz. Ezért még a nagy kísérleti minták pontjai is általában határvonalak - vagy a halmaz domború testén , vagy annak közelében fekszenek.
• A CLT szerint annak a valószínűsége, hogy két véletlen vektor normális lesz, bármely előre meghatározott pozitív hibán belül, 1-re hajlik, ahogy a tér dimenziója nő.

Jegyzetek

1. ↑ Richard Ernest Bellman; rand vállalat. Dinamikus programozás  (határozatlan idejű) . - Princeton University Press , 1957. - ISBN 978-0-691-07951-6 . ,
   Újra kiadva: Richard Ernest Bellman. Dinamikus programozás  (határozatlan idejű) . — Courier Dover Publications , 2003. — ISBN 978-0-486-42809-3 .
2. ↑ Richard Ernest Bellman. Adaptív szabályozási folyamatok : tárlatvezetés  . – Princeton University Press , 1961.
3. ↑ Powell, Warren B. 2007. Hozzávetőleges dinamikus programozás: A dimenziós átkok megoldása. Wiley, ISBN 0-470-17155-3 .
4. ↑ Marimont, R. B.; Shapiro, MB Legközelebbi szomszéd keresések és a dimenzionalitás átka  // IMA J Appl  Math : folyóirat. - 1979. - 1. évf. 24 , sz. 1 . - P. 59-70 . - doi : 10.1093/imamat/24.1.59 .
5. ↑ Radovanovic, Miloš; Nanopulosz, Alexandrosz; Ivanovics, Mirjana. Hubok az űrben: Népszerű legközelebbi szomszédok a nagydimenziós adatokban  //  Journal of Machine Learning Research  : Journal. - 2010. - 20. évf. 11 . - P. 2487-2531 .
6. ↑ KNOW INTUIT | Előadás | A legmeredekebb ereszkedési módszer. Davidon-Fletcher-Powell módszer. A szakadék probléma. A multi-extremalitás problémája . Letöltve: 2022. április 26. Az eredetiből archiválva : 2016. december 27. (határozatlan)
7. ↑ Joel H. Spencer (1994), Tíz előadás a valószínűségi módszerről , SIAM , p. 4, ISBN 978-0-89871-325-1 
8. ↑ Aubrey D.N.J. D.E. Grey. A sík kromatikus száma legalább 5  // math.CO. — 2018. Archiválva : 2018. július 12.