Aprendizaje Profundo¶

Introducción al concepto de $q$-dimensión¶

Fuente: Trekky0623 at English Wikipedia ("I made this map myself"), Public domain, via Wikimedia Commons

Autores¶

1. Alvaro Montenegro, PhD, ammontenegrod@unal.edu.co
2. Daniel Montenegro, Msc, dammontenegrore@unal.edu.co

Asesora de Medios y Marketing¶

1. Maria del Pilar Montenegro, pmontenegro88@gmail.com

Referencias¶

1. Christofer. M. Bishop, Pattern Recognition and machine Learning, first edition,Springer, 2006.
2. John A. Lee and Michel Verleysen. Nonlinear dimensionality reduction. Springer, first edition, 2007.
3. Christopher J. C. Burges, Dimension Reduction: A Guided Tour, Foundations and Trends in Machine Learning, Vol. 2, No. 4 (2009) 275–365.

Contenido¶

• Introducción
• Cuatro métodos de reducción de dimensiones aplicados a datos genómicos
• Concentración de las distancias en espacions n-dimensionales
  • Teorema
• Propósitos de la reducción de dimensiones
• Reducción de dimensiones y reconstrucción de errores
• Un ejemplo: Análisis de Componentes Principales (PCA)
• Introducción

Introducción¶

En esta lección revisamos los siguientes conceptos.

1. Curso de la dimensionalidad
2. $q$-dimensión
3. Estimación de la $q$-dimensión

Pero antes vamos con un entremés.

Cuatro métodos de reducción de dimensiones aplicados a datos genómicos¶

Fuente: Alex Diaz-Papkovich,Luke Anderson-Trocmé,Chief Ben-Eghan,Simon Gravel, CC BY 2.5, via Wikimedia Commons

Las imágenes muestran el efecto de reducción de dimensión con un conjunto de datos de tipo genómico.

• A) ACP mapea individuos en un triángulo con vértices correspondientes a la ascendencia continental africana, asiática y europea. Descartar las componentes principales de varianza más baja conduce a la superposición de poblaciones sin afinidad cercana, como las poblaciones de América Central y del Sur con las del sur de Asia.
• B) t-SNE forma grupos correspondientes a los continentes, con cierta superposición entre los pueblos europeos y centro y sudamericanos. Los subgrupos más pequeños son visibles dentro de los grupos continentales. La nube de puntos periféricos resulta de la pobre convergencia del método.
• C) UMAP forma grupos distintos relacionados con el continente con subgrupos claramente definidos. Las poblaciones japonesa, finlandesa, luhya y algunas punjabi y telugu forman grupos separados consistentes con la historia de su población.
• D) UMAP en los primeros 15 componentes principales forma grupos de escala fina para poblaciones individuales. Los grupos estrechamente relacionados por ascendencia o geografía, como las poblaciones afrocaribeña/afroamericana, española/italiana y kinh/dai, se agrupan. Los ejes en UMAP y t-SNE son arbitrarios. Dado que los algoritmos dan prioridad a las distancias locales, las distancias largas entre clústeres no son significativas. ACB, Caribe Africano en Barbados; ASW, ascendencia africana en el suroeste de EE. UU.; BEB, bengalí; CDX, Dai chino; CEU, residentes de Utah con ascendencia del norte/oeste de Europa; CHB, chino Han; CHS, chino Han del Sur; CLM, colombiana en Medellín, Colombia; ESN, Esan en Nigeria; FIN, finlandés; GBR, británicos en Inglaterra y Escocia; GWD, de Gambia; GTH, guyaratí; SII, Ibérico en España; ITU, telugu indio en el Reino Unido; JPT, japonés; KHV, Kinh en Vietnam; LWK, Luhya en Kenia; MSL, Mende en Sierra Leona; MXL, mexicana en Los Ángeles, California; PEL, peruano; PJL, Punjabi en Lahore, Pakistán; PUR, puertorriqueño; STU, tamil de Sri Lanka en el Reino Unido; TSI, Toscani en Italia; YRI, Yoruba en Nigeria.

Concentración de las distancias en espacios n-dimensionales¶

En espacios de alta dimensión las métricas son débiles para discriminar vectores como se muestra en el siguiente resultado.

Teorema ¶

Sea $\boldsymbol{y}$ un vector aleatorio $D$-dimensional. Se supone que todas las componentes de $\boldsymbol{y}$ son independientes e idénticamente distribuidas, con momentos finitos de octavo orden. Entonces la media $\mu_{||\boldsymbol{y}||}$ y la varianza $\sigma^2_{||\boldsymbol{y}||}$ de la norma euclidiana son

$$ \begin{align} \mu_{||\boldsymbol{y}}||&= \sqrt{aD-b} + \mathcal{O}(D^{-1})\\ \sigma^2_{||\boldsymbol{y}||}&= b + \mathcal{O}(D^{-1/2}), \end{align} $$

donde $a$ y $b$ son parámetros que dependen únicamente de los momentos centrales de orden $1,2,3$ y 4.

Por lo tanto, la norma de los vectores aleatorios crece proporcionalmente a $\sqrt{D}$, como se esperaba, pero las varianzas permanecen más o menos constantes para un $D$ suficientemente grande.

En otras palabras, la distribución de las normas tiende a estar muy concentrada alrededor de su media.

Propósitos de la reducción de dimensión¶

Casi siempre se puede reducir la alta dimensionalidad de los datos. La subsección anterior motiva a reducir la dimensión de los datos para superar algunas de las dificultades causadas por el problema de la maldición de la dimensionalidad. Las principales propiedades que caracterizan a un método de análisis de datos de alta dimensionalidad son:

1. Estimar la dimensión intrínseca de los datos. Informalmente esto quiere decir, estimar el número de variables latentes necesarias para representar los datos con un error bajo.
2. Incrustar datos en espacios de dimensión baja para reducir su dimensionalidad.
3. Incrustar datos para recuperar las variables latentes.

Reducción de dimensión y reconstrucción de errores¶

Por lo general, un método de reducción de dimensiones se guía por un criterio que debe optimizarse. Por ejemplo, en el conocido análisis de componentes principales (PCA), el principio desde un punto de vista geométrico es minimizar la distancia desde los puntos de datos hasta el primer componente, luego hasta el segundo, y así sucesivamente. Equivalente, desde un punto de vista estadístico, PCA maximiza la varianza de los datos representados por el primer componente y así sucesivamente.

Para evaluar un método de reducción, primero se reduce la dimensionalidad y luego se vuelve a expandir, siempre que el preceso pueda ser revertido, al menos parcialmente. Matemáticamente, este error de reconstrucción se puede escribir como

$$ \begin{equation} E_{\text{cod}} = E_{y}[|| y-\text{dec}(\text{cod}(y))||_2^2], \end{equation} $$

donde $E[]$ es el operador de esperanza. La reducción de la dimensionalidad y la expansión hacia atrás se denotan respectivamente como

$$ \begin{align*} cod: \mathcal{R}^D \to \mathcal{R}^P, \hspace{2mm} &x = cod(y),\\ dec: \mathcal{R}^P \to \mathcal{R}^D, \hspace{2mm} &y' = dec(x). \end{align*} $$

Fuente: Alvaro Montenegro. Basado en Michael Gashler, Dan Ventura, Tony Martinez, CC BY-SA 4.0, via Wikimedia Commons

Un ejemplo: Análisis de Componentes Principales (ACP)¶

Una hipótesis esencial en el modelo ACP es que se tiene una matriz $\mathbf{A}$ de tamaño $N\times D$, en donde cada fila es de la forma $\mathbf{y}= [y_1,\ldots,y_D]^T$ con las $D$ variables observadas, proviene de una transformación lineal $\mathbf{W}$ de $P$ variables latentes desconocidas, digamos, $\mathbf{x} = [x_1,\ldots,x_P]^T$, de tal manera que

$$ \begin{equation} \mathbf{y = Wx}. \end{equation} $$

En el ACP convencional no hay una distribución de probabilidad pre-definida de antemano. Sin embargo, Tipping y Bishop (1997) mostraron cómo el ACP puede reformularse como la solución de máxima verosimilitud de un modelo de variable latente específico. En este caso, se supone que el vector latente $\mathbf{x}$ tiene una distribución gaussiana $\mathfrak{N}(\boldsymbol{0},\boldsymbol{I}_P)$, y el vector observado $\mathbf{y}$ viene dado por $\mathbf{y= Wx } + \boldsymbol{\mu } + \boldsymbol{\epsilon }$, donde $\epsilon$ es un vector gaussiano de media cero con matriz de covarianza $\sigma^2\mathbf{I}_{D}$, y $\boldsymbol{\mu}$ es el vector de parámetros de la media. Supondremos que $\boldsymbol{\mu}= \boldsymbol{0}$, y que las variables latentes tienen una distribución gaussiana.

Se supone que las columnas de $\mathbf{W}$ son ortogonales, de forma que $\mathbf{W}^T\mathbf{W}= \mathbf{I}_P$, y que las variables observadas y las latentes están centradas.

En el paso de procesamiento previo, las variables observadas se centran y escalan para tener variables estandarizadas. Es importante evitar estandarizar variables con una desviación estándar muy baja, porque en este caso el ruido puede ser proporcionalmente grande.

Solución ACP ¶

En esta sección se utilizan dos criterios para llegar al mismo método:

• error de reconstrucción mínimo
• varianza conservada máxima.

Otro criterio que conduce a la misma solución es la preservación de la distancia (escalamiento multidimensional).

Error de reconstrucción minimal¶

Las funciones de codificación y codificación se pueden reescribir como

$$ \begin{align} cod:& \mathcal{R}^D \to \mathcal{R}^P, y \mapsto x = cod(y) = W^+y,\\ dec:& \mathcal{R}^P \to \mathcal{R}^D, x \mapsto y = dec(y)= Wx, \end{align} $$

donde $W^+ = (W^T W)^{-1}W^T = W^T$ es la pseudo-inversa izquierda de $W$. Recuerde que asumimos $\mathbf{W}^T\mathbf{W}= \mathbf{I}_P$. Por lo tanto, el error cuadrático medio de la reconstrucción se convierte en

$$ \begin{equation} E_{\text{cod}} = E_{y}[||y- W W^Ty ||_2^2] = E_y[y^Ty] - E_{y}[y^T WW^T y]. \end{equation} $$

Por lo tanto, minimizar $E_{\text{cod}}$ es equivalente a maximizar el término $E_{y}[y^T WW^T y]$. Para la muestra observada $y_1,\ldots,y_N$, la experanza se aproxima mediante la media muestral

$$ \begin{equation} E_{y}[y^T WW^T y] \approx \frac{1}{N} \sum_{i=1}^{N} y_i^T WW^T y_i = \frac{1}{N} tr(Y^T WW^T Y), \end{equation} $$

donde $tr(M)$ denota la traza de la matriz $M$ y en donde $Y$ es la matriz de tamaño $D\times N$ cuyas columnas son los vectores $y_i$.

Consideremos la descomposición en valor único (SVD) de la matriz $Y$ dada por

$$ \begin{equation} Y= V\boldsymbol{\Sigma}U^T, \end{equation} $$

donde $V$ y $U$ son matrices unitarias y donde $\boldsymbol{\Sigma}$ es una matriz del mismo tamaño que $Y$, con $D$ como máximo entradas cero, $\sigma_d$ llamados valores singulares ubicados en la primera diagonal de $\boldsymbol{\Sigma}$, ordenados en orden descendente. Es fácil ver que $$ \begin{equation} \arg \max\limits_{W} \frac{1}{N} tr(Y^T WW^T Y) = V I_{D\times P}, \end{equation} $$

para un $P$ dado. $I_{D\times P}$ es tal que las primeras columnas $P$ corresponden a la identidad $I_P$.

Las variables latentes $P$-dimensionales están dadas por $$ \begin{equation} \widehat{x} = I_{P\times D} V^T Y. \end{equation} $$

Estimación de la dimensión intrínseca¶

Si el modelo se mantiene razonablemente bien, los valores propios grandes corresponden a la varianza de las variables latentes y los más pequeños se deben al ruido y otras imperfecciones. Idealmente, una brecha visible en el trazado de los valores propios separa los dos tipos de valores propios. Si la brecha no es visible, trazar los valores propios normalizados puede ayudar:

$$ \begin{equation} 0 \le -\log \frac{\lambda_d}{\lambda_1}. \end{equation} $$

Otros criterios, por ejemplo preservar los $95\%$ de la varianza, pueden ser útiles:

$$ \begin{equation} 0.95 \le \frac{\sum_{d=1}^{P} \lambda_d}{\sum_{d=1}^{D} \lambda_d}. \end{equation} $$

Se han desarrollado otros procedimientos más complejos, véase, por ejemplo, el artículo de Bishop (1998), para un procedimiento bayesiano para la detección automática de la dimensión intrínseca.

Una caracterización de los métodos de reducción de dimensión¶

1. Reducción de dimensionalidad dura vs. blanda.
2. Modelo tradicional vs generativo.
3. Modelo lineal frente a no lineal.
4. Modelo continuo vs. discreto.
5. Mapeo implícito versus explícito.
6. Estimación integrada vs externa de la dimensionalidad.
7. Incrustaciones en capas frente a independientes.
8. Sistemas de coordenadas simples versus múltiples.
9. Cuantificación vectorial opcional frente a obligatoria.
10. Algoritmo por lotes vs. en línea.
11. Optimización exacta vs. aproximada.
12. El tipo de criterio a optimizar

La dimensión intrínsica¶

La dimensión intrínseca de un vector aleatorio $\boldsymbol{y}$ generalmente se define como el número mínimo de parámetros o variables latentes necesarios para describir $\boldsymbol{y}$. Esta es una definición informal y ambigua, aunque parece clara en la práctica. La dimensión $q$ formaliza y unifica el concepto.

La $q$-dimensión¶

Fuente: Alvaro Montenegro.

La definición que adoptaremos proviene de la física. Supongamos que $\mu$ representa la medida que usamos para medir los objetos que estamos observando. Para $\epsilon > 0$, el soporte de $\mu$ se cubre con una cuadrícula multidimensional de cubos con longitud de arista $\epsilon$. Sea $N(\epsilon)$ el número de cubos que cortan el soporte de $\mu$, y sea $p_1,\ldots, p_{N(\epsilon)}$ la medida natural de esos cubos. Las medidas se normalizan tal que

$$ \begin{equation*} \sum_{i=1}^{N(\epsilon)} p_i =1. \end{equation*} $$

Entonces definimos la q-dimensión como

$$ \begin{align} D_q(\mu) &= \lim\limits_{\epsilon \to 0} \frac{\log \sum_{i=1}^{N(\epsilon)} p_i^q}{(q-1)\log \epsilon}\\ \end{align} $$

Aproximación intuitiva al concepto de $q$-dimensión¶

Suponga que la muestra de datos que tenemos se ve en la siguiente imagen.

Fuente: Alvaro Montenegro.

• El volumen de cada caja es $\epsilon^2$ en la rejilla. Por otro lado, definimos como medida $\mu$ de los datos en cada bola abierta al número de de elementos dentro de la bola.
• Si cada caja en la rejilla es un bola cerrada, entonces las medidas $\mu$ de las cajas no vacías son 3,1,2,1,2,3,4,1,2 respectivamente.
• Si hacemos $\epsilon$ cada vez más pequeño, al final resulta que quedarán cajas solamente con un elemento o con ninguno.

Entonces el volumen total ocupado por las cajas $C_q(\mu,\epsilon)$ en el límite es la suma de todas las medidas, que en el ejemplo coincide con el número de cajas ocupadas. por lo que

$$ C_q(\mu,\epsilon) = \propto K(\epsilon^{q-1})^2, $$

en donde K es el número de cajas ocupadas.

Esta instiución se generaliza al espacio p-dimensional como

$$ C_q(\mu,\epsilon) \propto (\epsilon^{q-1})^p, $$

Si se toma logaritmo a ambos lados se tiene

$$ p \propto\frac{\log C_q(\mu,\epsilon) }{(q-1) \log \epsilon} $$

Dimensión de capacidad: Capacity dimension¶

En la segunda definición sea $q=0$, y obtenemos la dimensión de capacidad (capacity dimension):

$$ \begin{equation} d_{cap} = D_0(\mu) = -\lim\limits_{\epsilon \to 0} \frac{\log N(\epsilon)}{\log \epsilon}. \end{equation} $$

Tenga en cuenta que $d_{cap}$ no depende de las medidas naturales $p_i$. $d_{cap}$ también se llama la dimensión recuento de cajas. Para una muestra, un algoritmo para calcular $d_{cap}$ es el siguiente.

1. Determine el hipercubo que circunscribe todos los puntos de datos.
2. Descomponga el hipercubo obtenido en una cuadrícula de hipercubos más pequeños con

longitud del borde $\epsilon$ (estos cuadros explican el nombre del método).

1. Determine $N(\epsilon)$, el número de hipercubos que están ocupados por uno o varios puntos de datos.
2. Calcule $\log (N(\epsilon))$ y divida por $\log \epsilon$.
3. Calcular el límite cuando $\epsilon$ tiende a cero; esto es $d_{cap}$.

Desafortunadamente, el límite a calcular en el último paso parece ser el único obstáculo para la simplicidad general de la técnica. Abajo se dan algunos consejos para sortear este obstáculo.

Para una intuición sobre $d_{cap}$ imagine un conjunto de puntos en el espacio tridimensional. Así, para un objeto unidimensional, el número de cajas ocupadas crece proporcionalmente a la longitud del objeto. Para un objeto bidimensional, el número de casillas ocupadas crece proporcionalmente a la superficie del objeto, y así sucesivamente. Por lo tanto, para una variedad $P-$dimensional incrustada en $\mathcal{R}^D$ se obtiene

$$ \begin{equation} N(\epsilon) \propto \epsilon^P, \end{equation} $$

así que, $$ \begin{equation} P \propto \frac{\log N(\epsilon)}{\log \epsilon}. \end{equation} $$

Exercicio¶

Verificar que la dimensión de capacidad se pueda calcular analíticamente para la costa de la isla de Koch y es

$$ \begin{equation} d_{cap} = \frac{\log 4}{\log 3} = 1.261859507. \end{equation} $$

Dimensión de la información: Information dimension¶

La dimensión de información ($d_{inf}$) corresponde al caso donde $q=1$. Se puede demostrar que $d_{inf}$ está dado por

$$ \begin{equation} d_{inf} = \lim\limits_{\epsilon \to 0} \frac{\log \sum_{i=1}^{N(\epsilon)} p_i \log p_i}{\log \epsilon} \end{equation} $$

Esta expresión sigue siendo difícil porque, en general, los $p_i$ rara vez se conocen, excepto en el caso en que se supone que todos los $p_i$ son iguales. En tal caso $d_{inf} = d_{cap}$.

Dimensión correlación ¶

La dimensión de correlación corresponde al caso de $q=2$. Cuando los datos son un conjunto de puntos $\boldsymbol{y}= \{y_1,\ldots,y_N\}$. En este caso $C_2(\mu,\epsilon)$ se puede escribir como

$$ \begin{equation} C_2(\epsilon) = Pr(||\boldsymbol{y}_i-\boldsymbol{y}_j ||_2 \le \epsilon). \end{equation} $$

Entonces, la dimensión de correlación $d_{cor}$ se puede escribir como

$$ \begin{equation} d_{cor} = \lim\limits_{\epsilon \to 0} \frac{\log C_2(\epsilon)}{\log \epsilon}. \end{equation} $$

Dado un conjunto de puntos $\boldsymbol{y}$, la dimensión de correlación se estima fácilmente mediante el siguiente procedimiento:

1. Calcula las distancias entre todos los puntos posibles $\boldsymbol{y}_i, \boldsymbol{y}_j$.
2. Determina la proporción de distancias que son menores o iguales a $\epsilon$.
3. Calcule $\log C_2(\epsilon)$ y divida por $\log \epsilon$.
4. Calcular el límite cuando $\epsilon$ tiende a cero.

El segundo paso da como resultado una estimación $\widehat{C}_2(\epsilon)$ de ${C}_2(\epsilon)$. La interpretación intuitiva es muy similar a la asociada con la dimensión de capacidad. El problema vuelve a ser el último paso.

Estimación práctica de la $q$-dimensión¶

Para superar el problema del límite hacia cero en la dimensión de capacidad y la dimensión de correlación, podemos calcular los valores de $N(\epsilon)$ o $\hat{C}(\epsilon)$ para $\epsilon$ que oscilan entre las distancias más pequeña y más grande en el conjunto de datos. Un truco para sortear el problema consiste en aplicar la regla de l'Hopital. La regla se puede aplicar porque el numerador y el denominador tienden a $-\infty$. En el caso de la dimensión de correlación tenemos

$$ \begin{align*} d_{cor} &= \lim\limits_{\epsilon \to 0} \frac{\log \widehat{C}_2(\epsilon)}{\log \epsilon}\\ &= \lim\limits_{\epsilon \to 0} \frac{\partial\log \widehat{C}_2(\epsilon)}{\partial \epsilon} \Biggl{/} \frac{\partial \log \epsilon}{\partial \epsilon}\\ &= \lim\limits_{\epsilon \to 0} \frac{\partial\log \widehat{C}_2(\epsilon)}{\partial \log \epsilon}\\ &= \lim\limits_{\epsilon_1,\epsilon_2 \to 0} \frac{\log \widehat{C}_2(\epsilon_2)-\log \widehat{C}_1(\epsilon_1)}{\log \epsilon_2-\log \epsilon_1} \end{align*} $$

Alternativamente, la dimensión de correlación se puede estimar calculando la derivada numérica de $\log \widehat{C}_2(\exp \nu)$, con $\nu = \log \epsilon$:

$$ \begin{equation} \widehat{d}_{cor} = \frac{d}{d\nu} \log \widehat{C}_2(\exp \nu). \end{equation} $$

Entonces, el $d_{cor}$ se puede estimar como la pendiente de $\log \widehat{C}_2(\epsilon)$ en el gráfico log-log.

Por ejemplo, el parámetro de regresión de la regresión de $\log \widehat{C}_2(\epsilon) = \beta \log \epsilon + error$.