Maledicció de la dimensionalitat
La maledicció de la dimensionalitat es refereix a diversos fenòmens que sorgeixen en analitzar i organitzar dades en espais d'alta dimensió que no es produeixen en entorns de dimensions baixes com l'espai físic tridimensional de l'experiència quotidiana. L'expressió va ser encunyada per Richard E. Bellman en considerar problemes en la programació dinàmica.[1]
Els fenòmens maleïts dimensionalment es produeixen en dominis com ara l'anàlisi numèrica, el mostreig, la combinatòria, l'aprenentatge automàtic, la mineria de dades i les bases de dades. El tema comú d'aquests problemes és que quan la dimensionalitat augmenta, el volum de l'espai augmenta tan ràpidament que les dades disponibles es tornen escasses. Per obtenir un resultat fiable, la quantitat de dades necessàries sovint creix exponencialment amb la dimensionalitat. A més, l'organització i la cerca de dades sovint es basa en detectar àrees on els objectes formen grups amb propietats similars; en dades d'alta dimensió, però, tots els objectes semblen ser escassos i diferents en molts aspectes, cosa que impedeix que les estratègies comunes d'organització de dades siguin eficients.
Dominis
[modifica]Combinatòria
[modifica]En alguns problemes, cada variable pot prendre un dels diversos valors discrets, o el rang de valors possibles es divideix per donar un nombre finit de possibilitats. Prenent les variables juntes, s'ha de considerar un gran nombre de combinacions de valors. Aquest efecte també es coneix com a explosió combinatòria. Fins i tot en el cas més simple de variables binàries, el nombre de combinacions possibles ja és , exponencial en la dimensionalitat. Ingènuament, cada dimensió addicional duplica l'esforç necessari per provar totes les combinacions.
Mostreig
[modifica]Hi ha un augment exponencial de volum associat amb l'addició de dimensions addicionals a un espai matemàtic. Per exemple, 10 2 = 100 punts de mostra espaiats uniformement són suficients per mostrar un interval d'unitat (intenta visualitzar un cub "1-dimensional") amb no més de 10 −2 = 0,01 distància entre punts; un mostreig equivalent d'un hipercub unitat de 10 dimensions amb una gelosia que tingui un espai de 10 −2 = 0,01 entre punts adjacents requeriria 10 20 = [(10 2 ) 10 ] punts de mostra. En general, amb una distància d'espai de 10 − n, l'hipercub de 10 dimensions sembla ser un factor de 10 n (10−1) = [(10 n ) 10 /(10 n )] "més gran" que l'unidimensional hipercub, que és l'interval unitari. A l'exemple anterior n = 2: quan s'utilitza una distància de mostreig de 0,01, l'hipercub de 10 dimensions sembla ser 10 18 "més gran" que l'interval unitari. Aquest efecte és una combinació dels problemes de combinatòria anteriors i dels problemes de funció de distància explicats a continuació.
Optimització
[modifica]Quan es resolen problemes d'optimització dinàmica per inducció numèrica cap enrere, s'ha de calcular la funció objectiu per a cada combinació de valors. Aquest és un obstacle important quan la dimensió de la "variable d'estat" és gran.[2]
Aprenentatge automàtic
[modifica]En els problemes d'aprenentatge automàtic que impliquen aprendre un "estat de la naturalesa" a partir d'un nombre finit de mostres de dades en un espai de característiques d'alta dimensió amb cada característica amb un rang de valors possibles, normalment es requereix una quantitat enorme de dades d'entrenament per garantir que hi ha diverses mostres amb cada combinació de valors. En un sentit abstracte, a mesura que el nombre de característiques o dimensions creix, la quantitat de dades que necessitem per generalitzar amb precisió creix de manera exponencial.
Una regla general típica és que hi hauria d'haver almenys 5 exemples d'entrenament per a cada dimensió de la representació.[3] En l'aprenentatge automàtic i pel que fa al rendiment predictiu, la maledicció de la dimensionalitat s'utilitza indistintament amb el fenomen del pic,[3] que també es coneix com a fenomen Hughes.[4] Aquest fenomen afirma que amb un nombre fix de mostres d'entrenament, el poder predictiu mitjà (esperat) d'un classificador o regressor augmenta primer a mesura que augmenta el nombre de dimensions o característiques utilitzades, però més enllà d'una certa dimensionalitat comença a deteriorar-se en lloc de millorar constantment.[5][6][7]
Mineria de dades
[modifica]A la mineria de dades, la maledicció de la dimensionalitat es refereix a un conjunt de dades amb massa característiques.
Referències
[modifica]- ↑ Bellman, Richard Ernest. Adaptive control processes: a guided tour (en anglès). Princeton University Press, 1961. ISBN 9780691079011.
- ↑ Taylor, C. Robert. «Dynamic Programming and the Curses of Dimensionality». A: Applications Of Dynamic Programming To Agricultural Decision Problems (en anglès). Westview Press, 1993, p. 1–10. ISBN 0-8133-8641-1.
- ↑ 3,0 3,1 Koutroumbas, Konstantinos. Pattern Recognition (en anglès). 4th, 2008. ISBN 978-1-59749-272-0.
- ↑ Hughes, G.F. IEEE Transactions on Information Theory, 14, 1, 1-1968, pàg. 55–63. DOI: 10.1109/TIT.1968.1054102.
- ↑ Trunk, G. V. IEEE Transactions on Pattern Analysis and Machine Intelligence, PAMI-1, 3, 7-1979, pàg. 306–307. DOI: 10.1109/TPAMI.1979.4766926. PMID: 21868861.
- ↑ B. Chandrasekaran; A. K. Jain IEEE Transactions on Computers, 23, 8, 1974, pàg. 102–106. DOI: 10.1109/T-C.1974.223789.
- ↑ McLachlan, G. J.. Discriminant Analysis and Statistical Pattern Recognition (en anglès). Wiley Interscience, 2004. ISBN 978-0-471-69115-0.