Hispanopedia Wiki
Articulo de referencia

Proyección aleatoria

En matemáticas y estadística, la proyección aleatoria es una técnica utilizada para reducir la dimensionalidad de un conjunto de puntos que se encuentran en el espacio euclidian...

Hispanopedia WikiContenido en espanolLectura gratuita

En matemáticas y estadística, la proyección aleatoria es una técnica utilizada para reducir la dimensionalidad de un conjunto de puntos que se encuentran en el espacio euclidiano . Según los resultados teóricos, la proyección aleatoria conserva bien las distancias, pero los resultados empíricos son escasos. [ 1 ] Se han aplicado a muchas tareas de lenguaje natural bajo el nombre de indexación aleatoria .

Reducción de dimensionalidad

La reducción de dimensionalidad, como su nombre indica, consiste en reducir el número de variables aleatorias mediante diversos métodos matemáticos de la estadística y el aprendizaje automático. Se utiliza frecuentemente para simplificar la gestión y manipulación de grandes conjuntos de datos. Las técnicas de reducción de dimensionalidad suelen emplear transformaciones lineales para determinar la dimensionalidad intrínseca de la variedad y extraer sus direcciones principales. Para ello, existen diversas técnicas relacionadas, como el análisis de componentes principales , el análisis discriminante lineal , el análisis de correlación canónica , la transformada discreta del coseno y la proyección aleatoria, entre otras.

La proyección aleatoria es una forma sencilla y computacionalmente eficiente de reducir la dimensionalidad de los datos, intercambiando una cantidad controlada de error por tiempos de procesamiento más rápidos y modelos más pequeños. Las dimensiones y la distribución de las matrices de proyección aleatoria se controlan para preservar aproximadamente las distancias entre pares cualesquiera de muestras del conjunto de datos.

Método

La idea central detrás de la proyección aleatoria se da en el lema de Johnson-Lindenstrauss , [ 2 ] que establece que si los puntos en un espacio vectorial tienen una dimensión suficientemente alta, entonces pueden proyectarse en un espacio de menor dimensión adecuado de manera que se preserven aproximadamente las distancias por pares entre los puntos con alta probabilidad.

En proyección aleatoria, el originald{\displaystyle d}Los datos dimensionales se proyectan a unk{\displaystyle k}subespacio de dimensión , multiplicando por la izquierda por una matriz aleatoriaR∈Rk×d{\displaystyle R\in \mathbb {R} ^{k\times d}}. Usando notación matricial: Siincógnitad×norte{\displaystyle X_{d\times N}}es el conjunto original de observaciones N d-dimensionales, entoncesincógnitak×norteRPAG=Rk×dincógnitad×norte{\displaystyle X_{k\times N}^{RP}=R_{k\times d}X_{d\times N}}es la proyección de los datos sobre un subespacio k-dimensional inferior. La proyección aleatoria es computacionalmente simple: forme la matriz aleatoria "R" y proyecte los datos sobre un subespacio k-dimensional inferior.d×norte{\displaystyle d\times N}matriz de datos X en K dimensiones de ordenO(dknorte){\displaystyle O(dkN)}Si la matriz de datos X es dispersa con aproximadamente c entradas distintas de cero por columna, entonces la complejidad de esta operación es de ordenO(doknorte){\displaystyle O(ckN)}. [ 3 ]

Proyección aleatoria ortogonal

Un vector unitario puede proyectarse ortogonalmente sobre un subespacio aleatorio.tú{\displaystyle u}Sea el vector unitario original y seav{\displaystyle v}sea ​​su proyección. La norma al cuadrado‖v‖22{\displaystyle \|v\|_{2}^{2}}tiene la misma distribución que proyectar un punto aleatorio, muestreado uniformemente en la esfera unitaria , a su primerak{\displaystyle k}coordenadas. Esto equivale a muestrear un punto aleatorio en la distribución gaussiana multivariada.incógnita∼norte(0,Id×d){\displaystyle x\sim {\mathcal {N}}(0,I_{d\times d})}y luego normalizándolo.

Por lo tanto,‖v‖22{\displaystyle \|v\|_{2}^{2}}tiene la misma distribución que∑i=1kincógnitai2∑i=1kincógnitai2+∑i=k+1dincógnitai2{\displaystyle {\frac {\sum _{i=1}^{k}x_{i}^{2}}{\sum _{i=1}^{k}x_{i}^{2}+\sum _{i=k+1}^{d}x_{i}^{2}}}}, que por la construcción chi-cuadrado de la distribución Beta , tiene distribuciónBeta⁡(k/2,(d−k)/2){\displaystyle \operatorname {Beta} (k/2,(dk)/2)}, con mediak/d{\displaystyle k/d}.

Tenemos una desigualdad de concentraciónPAGr[|‖v‖2−kd|≥ϵkd]≤3exp⁡(−kϵ2/64){\displaystyle Pr\left[\left|\|v\|_{2}-{\frac {k}{d}}\right|\geq \epsilon {\sqrt {\frac {k}{d}}}\right]\leq 3\exp \left(-k\epsilon ^{2}/64\right)}para cualquierϵ∈(0,1){\displaystyle \épsilon \en (0,1)}. [ 4 ] : 50

proyección aleatoria gaussiana

La matriz aleatoria R se puede generar utilizando una distribución gaussiana. La primera fila es un vector unitario aleatorio elegido uniformemente deSd−1{\displaystyle S^{d-1}}La segunda fila es un vector unitario aleatorio del espacio ortogonal a la primera fila, la tercera fila es un vector unitario aleatorio del espacio ortogonal a las dos primeras filas, y así sucesivamente. De esta forma de elegir R, se satisfacen las siguientes propiedades:

  • Simetría esférica: Para cualquier matriz ortogonalA∈O(d){\displaystyle A\in O(d)}RA y R tienen la misma distribución.
  • Ortogonalidad: Las filas de R son ortogonales entre sí.
  • Normalidad: Las filas de R son vectores de longitud unitaria.

Proyecciones aleatorias computacionalmente más eficientes

Achlioptas [ 5 ] ha demostrado que la matriz aleatoria puede muestrearse de manera más eficiente. La matriz completa puede muestrearse de forma independiente e idénticamente distribuida (IID) según

Ri,j=3/k×{+1con probabilidad 160con probabilidad 23−1con probabilidad 16{\displaystyle R_{i,j}={\sqrt {3/k}}\times {\begin{cases}+1&{\text{con probabilidad }}{\frac {1}{6}}\\0&{\text{con probabilidad }}{\frac {2}{3}}\\-1&{\text{con probabilidad }}{\frac {1}{6}}\end{cases}}}

o la matriz completa puede ser muestreada IID segúnRi,j=1/k×{+1con probabilidad 12−1con probabilidad 12{\displaystyle R_{i,j}={\sqrt {1/k}}\times {\begin{cases}+1&{\text{con probabilidad }}{\frac {1}{2}}\\-1&{\text{con probabilidad }}{\frac {1}{2}}\end{cases}}}Ambos son eficientes para aplicaciones de bases de datos porque los cálculos se pueden realizar utilizando aritmética de enteros. Se realiza un estudio más relacionado en [ 6 ] .

Posteriormente se demostró cómo utilizar la aritmética de enteros para lograr una distribución aún más dispersa, con muy pocos valores distintos de cero por columna, en el trabajo sobre la Transformación JL dispersa. [ 7 ] Esto resulta ventajoso, ya que una matriz de incrustación dispersa permite proyectar los datos a una dimensión inferior con mayor rapidez.

Proyección aleatoria con cuantización

La proyección aleatoria puede condensarse aún más mediante cuantización (discretización), con 1 bit (proyección aleatoria de signo) o multibits. Es el componente básico de SimHash, [ 8 ] el árbol RP, [ 9 ] y otros métodos de estimación y aprendizaje eficientes en memoria. [ 10 ] [ 11 ]

Grandes bases cuasiortogonales

El lema de Johnson-Lindenstrauss establece que grandes conjuntos de vectores en un espacio de alta dimensión pueden mapearse linealmente en un espacio de dimensión n mucho menor (pero aún alta) con una conservación aproximada de las distancias. Una de las explicaciones de este efecto es la dimensión cuasiortogonal exponencialmente alta del espacio euclidiano n -dimensional . [ 12 ] Existen conjuntos exponencialmente grandes (en dimensión n ) de vectores casi ortogonales (con un valor pequeño de productos internos ) en el espacio euclidiano n- dimensional. Esta observación es útil en la indexación de datos de alta dimensión. [ 13 ]

La cuasiortogonalidad de grandes conjuntos aleatorios es importante para los métodos de aproximación aleatoria en el aprendizaje automático . En dimensiones altas, un número exponencialmente grande de vectores elegidos aleatoriamente e independientemente de una equidistribución en una esfera (y de muchas otras distribuciones) son casi ortogonales con una probabilidad cercana a uno. [ 14 ] Esto implica que, para representar un elemento de un espacio de tan alta dimensión mediante combinaciones lineales de vectores elegidos aleatoriamente e independientemente, a menudo puede ser necesario generar muestras de longitud exponencialmente grande si usamos coeficientes acotados en las combinaciones lineales. Por otro lado, si se permiten coeficientes con valores arbitrariamente grandes, el número de elementos generados aleatoriamente que son suficientes para la aproximación es incluso menor que la dimensión del espacio de datos.

Implementaciones

  • RandPro - Un paquete de R para proyección aleatoria [ 15 ] [ 16 ]
  • sklearn.random_projection : un módulo para proyección aleatoria de la biblioteca de Python scikit-learn.
  • Implementación de Weka

Véase también

Referencias

  1. ↑ Ella, Bingham; Heikki, Mannila (2001). "Proyección aleatoria en la reducción de dimensionalidad: aplicaciones a datos de imagen y texto". KDD-2001: Actas de la Séptima Conferencia Internacional ACM SIGKDD sobre Descubrimiento de Conocimiento y Minería de Datos . Nueva York: Association for Computing Machinery. pp. 245–250 . CiteSeerX 10.1.1.24.5135 . doi : 10.1145/502512.502546 .  
  2. ↑ Johnson, William B .; Lindenstrauss, Joram (1984). «Extensiones de aplicaciones de Lipschitz en un espacio de Hilbert». Conferencia sobre Análisis Moderno y Probabilidad (New Haven, Connecticut, 1982) . Matemáticas Contemporáneas. Vol. 26. Providence, Rhode Island: Sociedad Matemática Americana. págs. 189-206 . doi : 10.1090/conm/026/737400 . ISBN   978-0-8218-5030-5. MR 0737400 . S2CID 117819162 .  .
  3. ↑ Bingham, Ella; Mannila, Heikki (6 de mayo de 2014). "Proyección aleatoria en la reducción de dimensionalidad: aplicaciones a datos de imagen y texto" (PDF) .
  4. ↑ Mahoney, Michael W. (16 de agosto de 2016), Notas de clase sobre álgebra lineal aleatorizada , arXiv : 1608.04481
  5. ↑ Achlioptas, Dimitris (2001). "Proyecciones aleatorias compatibles con bases de datos". Actas del vigésimo simposio ACM SIGMOD-SIGACT-SIGART sobre Principios de los sistemas de bases de datos - PODS '01 . págs. 274–281 . CiteSeerX 10.1.1.28.6652 . doi : 10.1145/375551.375608 . ISBN   978-1-58113-361-5. S2CID 2640788 . 
  6. ↑ Li, Ping; Hastie, Trevor; Church, Kenneth (2006). «Proyecciones aleatorias muy dispersas». Actas de la 12.ª conferencia internacional ACM SIGKDD sobre descubrimiento de conocimiento y minería de datos . págs. 287–296 . doi : 10.1145/1150402.1150436 . ISBN  1-59593-339-5. S2CID 7995734 . 
  7. ↑ Kane, Daniel M.; Nelson, Jelani (2014). "Transformadas de Johnson-Lindenstrauss más dispersas". Journal of the ACM . 61 (1): 1– 23. arXiv : 1012.1577 . doi : 10.1145/2559902 . MR 3167920 . S2CID 7821848 .  
  8. ↑ Charikar, Moses (2002). «Técnicas de estimación de similitud a partir de algoritmos de redondeo». Actas del trigésimo cuarto simposio anual de la ACM sobre Teoría de la Computación . Vol. 1. págs. 380–388 . doi : 10.1145/509907.509965 . ISBN   1-58113-495-9. S2CID 4229473 . 
  9. ↑ Freund, Yoav; Dasgupta, Sanjoy; Kabra, Mayank; Verma, Nakul (2007). "Aprendizaje de la estructura de variedades mediante proyecciones aleatorias". XX Conferencia Internacional sobre Sistemas de Procesamiento de Información Neuronal . 1 (1): 473– 480.
  10. ↑ Boufounos, Petros; Baraniuk, Richard (2008). "Detección compresiva de 1 bit". 42.ª Conferencia Anual sobre Ciencias y Sistemas de la Información de 2008. Vol. 1. págs. 16–21 . doi : 10.1109/CISS.2008.4558487 . ISBN   978-1-4244-2246-3. S2CID 206563812 . 
  11. ↑ Li, Xiaoyun; Li, Ping (2019). "Análisis del error de generalización del aprendizaje compresivo cuantificado". 33.ª Conferencia Internacional sobre Sistemas de Procesamiento de Información Neuronal . 1 : 15150–15160 .
  12. ↑ Kainen, Paul C. ; Kůrková, Věra (1993), "Dimensión cuasiorthogonal de espacios euclidianos", Applied Mathematics Letters , 6 (3): 7– 10, doi : 10.1016/0893-9659(93)90023-G , MR 1347278 
  13. ↑ Hecht-Nielsen, R. (1994). «Vectores de contexto: Representaciones aproximadas de significado de propósito general autoorganizadas a partir de datos brutos». En Zurada, Jacek M.; Marks, Robert Jackson; Robinson, Charles J. (eds.). Inteligencia computacional: Imitando la vida . IEEE. pp. 43–56 . ISBN  978-0-7803-1104-6.
  14. ↑ Gorban, Alexander N. ; Tyukin, Ivan Y.; Prokhorov, Danil V.; Sofeikov, Konstantin I. (2016). "Aproximación con bases aleatorias: Pro y Contra". Information Sciences . 364– 365: 129– 145. arXiv : 1506.04631 . doi : 10.1016/j.ins.2015.09.021 . S2CID 2239376 . 
  15. ↑ Ravindran, Siddharth (2020). "Una técnica de proyección reutilizable independiente de datos (DIRP) para la reducción de dimensión en la clasificación de grandes datos utilizando el algoritmo k-vecinos más cercanos (k-NN)". National Academy Science Letters . 43 : 13–21 . doi : 10.1007/s40009-018-0771-6 . S2CID 91946077 . 
  16. ↑ Siddharth, R.; Aghila, G. (julio de 2020). "RandPro: una implementación práctica de la extracción de características basada en proyección aleatoria para el análisis de datos multivariados de alta dimensión en R" . SoftwareX . 12 100629. Bibcode : 2020SoftX..1200629S . doi : 10.1016/j.softx.2020.100629 .

Lecturas adicionales

  • Fodor, Imola K (2002). Un estudio de técnicas de reducción de dimensionalidad (Informe). CiteSeerX 10.1.1.8.5098 . 
  • Menon, Aditya Krishna (2007). Proyecciones aleatorias y aplicaciones a la reducción de dimensionalidad (Tesis). CiteSeerX 10.1.1.164.640 . 
  • Ramdas, Aditya. Una introducción aleatoria a las proyecciones aleatorias (Informe). CiteSeerX 10.1.1.377.2593 .