Projecció aleatòria

En matemàtiques i estadística, la projecció aleatòria és una tècnica utilitzada per reduir la dimensionalitat d'un conjunt de punts que es troben a l'espai euclidià. Els mètodes de projecció aleatòria són coneguts per la seva potència, simplicitat i baixes taxes d'error en comparació amb altres mètodes. Segons els resultats experimentals, la projecció aleatòria conserva bé les distàncies, però els resultats empírics són escassos. S'han aplicat a moltes tasques de llenguatge natural sota el nom d'indexació aleatòria.

Reducció de la dimensionalitat

La reducció de la dimensionalitat, com el seu nom indica, és reduir el nombre de variables aleatòries utilitzant diversos mètodes matemàtics d'estadístiques i aprenentatge automàtic. La reducció de la dimensionalitat s'utilitza sovint per reduir el problema de la gestió i manipulació de grans conjunts de dades. Les tècniques de reducció de la dimensionalitat utilitzen generalment transformacions lineals per determinar la dimensionalitat intrínseca de la varietat, així com per extreure les seves direccions principals. Amb aquesta finalitat hi ha diverses tècniques relacionades, incloent: anàlisi de components principals, anàlisi discriminant lineal, anàlisi de correlació canònica, transformada cosinus discreta, projecció aleatòria, etc.

La projecció aleatòria és una manera senzilla i computacionalment eficient de reduir la dimensionalitat de les dades mitjançant el comerç d'una quantitat controlada d'errors per a temps de processament més ràpids i mides de model més petites. Les dimensions i la distribució de les matrius de projecció aleatòries es controlen per preservar aproximadament les distàncies per parelles entre dues mostres qualsevol del conjunt de dades.

Mètode

La idea bàsica darrere de la projecció aleatòria es dóna en el lema de Johnson-Lindenstrauss, que afirma que si els punts d'un espai vectorial tenen una dimensió prou alta, llavors es poden projectar en un espai de dimensions inferiors adequat d'una manera que aproximadament conserva les distàncies entre els punts.

En la projecció aleatòria, les dades d-dimensionals originals es projecten a un subespai k-dimensional (k << d), utilitzant un $k\times d$ - matriu dimensional R les columnes de la qual tenen longituds unitats. Ús de la notació matricial: If $X_{d\times N}$ és el conjunt original d'observacions N d-dimensionals, doncs $X_{k\times N}^{RP}=R_{k\times d}X_{d\times N}$ és la projecció de les dades en un subespai k-dimensional inferior. La projecció aleatòria és computacionalment senzilla: formeu la matriu aleatòria "R" i projecteu el $d\times N$ matriu de dades X a K dimensions d'ordre $O(dkN)$. Si la matriu de dades X és escassa amb aproximadament c entrades diferents de zero per columna, aleshores la complexitat d'aquesta operació és d'ordre $O(ckN)$.