Reducción de dimensionalidad

Pablo Huijse Heise

​

Reducción de dimensionalidad

• Sea una matriz de datos X ϵ ℝ^NxM
• Se denomina característica a cada una de las M columnas de X
• La dimensionalidad M puede ser muy grande

​

​

Reducción de dimensionalidad, github @ phuijse, pablo dot huijse at gmail dot com

Reducción de dimensionalidad

• Sea una matriz de datos X ϵ ℝ^NxM
• Se denomina característica a cada una de las M columnas de X
• La dimensionalidad M puede ser muy grande

​

Maldición de la dimensionalidad

​

Mientras más dimensiones se tengan:

• Más datos de entrenamiento se necesitan para optimizar �nuestros modelos
• Más costoso es el cómputo de distancias y métricas
• Más problemas asociados a generalización y sobre-ajuste

Reducción de dimensionalidad, github @ phuijse, pablo dot huijse at gmail dot com

Reducción de dimensionalidad

• Sea una matriz de datos X ϵ ℝ^NxM
• Se denomina característica a cada una de las M columnas de X
• La dimensionalidad M puede ser muy grande

​

Maldición de la dimensionalidad

​

Reducción de dimensionalidad, github @ phuijse, pablo dot huijse at gmail dot com

Reducción de dimensionalidad

• Sea una matriz de datos X ϵ ℝ^NxM
• Se denomina característica a cada una de las M columnas de X
• La dimensionalidad M puede ser muy grande
• Suponemos que los datos habitan en un sub-espacio (manifold) �de menor dimensión que el espacio de entrada

​

M

ℝ³

Reducción de dimensionalidad, github @ phuijse, pablo dot huijse at gmail dot com

Reducción de dimensionalidad

• Sea una matriz de datos X ϵ ℝ^NxM
• Se denomina característica a cada una de las M columnas de X
• La dimensionalidad M puede ser muy grande
• Suponemos que los datos habitan en un sub-espacio (manifold) �de menor dimensión que el espacio de entrada

​

Deseamos reducir la cantidad de características �sin perder “información relevante“

​

​

Reducción de dimensionalidad, github @ phuijse, pablo dot huijse at gmail dot com

Principal Component Analysis (PCA)

Sean

​

​

​

PCA busca un conjunto de vectores U normalizados que resulten en una proyección de los datos con varianza máxima

Intuición: Los ejes de máxima varianza son los de mayor interés

Reducción de dimensionalidad, github @ phuijse, pablo dot huijse at gmail dot com

Principal Component Analysis (PCA)

Sean

​

​

​

PCA busca un conjunto de vectores U normalizados que resulten en una proyección de los datos con varianza máxima

​

Reducción de dimensionalidad, github @ phuijse, pablo dot huijse at gmail dot com

Principal Component Analysis (PCA)

PCA busca un conjunto de vectores U que resulten en una proyección �de los datos con varianza máxima

Incorporamos la restricción usando multiplicadores de Lagrange

​

​

De la derivada en función de U se tiene que

​

​

​

Reducción de dimensionalidad, github @ phuijse, pablo dot huijse at gmail dot com

Principal Component Analysis (PCA)

La solución

​

​

​

Es equivalente al problema de valores propios

Reconocemos entonces a

• U: vectores propios
• L: valores propios

​

​

Reducción de dimensionalidad, github @ phuijse, pablo dot huijse at gmail dot com

Principal Component Analysis (PCA)

PCA encuentra un base ortogonal rotada con respecto al espacio original �y cuyos ejes maximizan la varianza de los datos

​

​

​

​

Reducción de dimensionalidad, github @ phuijse, pablo dot huijse at gmail dot com

Principal Component Analysis (PCA)

• La Matriz U es de MxM
• ¿Cómo reducimos dimensionalidad con PCA?
• Seleccionamos un subconjunto de los valores propios

Notemos que los valores propios nos indican la varianza proyectada

​

Criterio:

• Ordenamos los valores propios de mayor a menor
• Buscamos el primer D < M tal que:

Reducción de dimensionalidad, github @ phuijse, pablo dot huijse at gmail dot com

Principal Component Analysis (PCA)

​

Una vez que encontramos un valor para D creamos podemos crear nuestra matriz de proyección de menor dimensión a partir de las columnas de U que acumulan la mayor varianza

​

​

Finalmente nuestros datos proyectados

​

​

​

​

Donde X - X barra son los datos centrados (media cero)

​

​

Reducción de dimensionalidad, github @ phuijse, pablo dot huijse at gmail dot com

Principal Component Analysis (PCA)

​

También es de interés estudiar la información perdida al reconstruir cuando se usan distintos valores de D

Una reconstrucción se obtiene reproyectando al espacio original luego de haber reducido dimensionalidad

En el siguiente ejemplo se aprecian reconstrucciones de un dígito manuscrito (MNIST, M=748) usando distinta cantidad de vectores propios

​

​

​

Reducción de dimensionalidad, github @ phuijse, pablo dot huijse at gmail dot com

Principal Component Analysis (PCA)

​

Consideraciones adicionales

• Los datos deben estar centrados (media cero) antes de ser proyectados
• No olvidar restar la media cuando se calcula la covarianza de lo contrario la media de los datos dominará la proyección
• Si las características no están en la misma escala (unidades) es conveniente estandarizar (dividir columnas por su desviación estándar)
• PCA se puede usar para obtener una proyección esférica (blanqueada)

​

• Donde L es una matriz diagonal con los valores propios asociados a W. Se dice proyección esférica pues ahora Z tiene covarianza identidad

​

​

Reducción de dimensionalidad, github @ phuijse, pablo dot huijse at gmail dot com

PCA probabilístico

Podemos expresar PCA como la solución de máxima verosimilitud para un modelo probabilístico de variables latentes continuas

Sea X ϵ ℝ^NxM nuestros datos y Z ϵ ℝ^NxD la variable latente

Definimos un prior Gaussiano isotrópico para los componentes principales

​

​

Y para la probabilidad condicional x|z

​

​

Donde W ϵ ℝ^MxD y μ ϵ ℝ^D

​

​

Reducción de dimensionalidad, github @ phuijse, pablo dot huijse at gmail dot com

PCA probabilístico

Escribimos la verosimilitud como

​

​

p(x) es Gaussiana pues es una convolución �de dos gaussianas

Para encontrar sus parámetros reparametrizamos x

​

​

​

​

​

​

​

Reducción de dimensionalidad, github @ phuijse, pablo dot huijse at gmail dot com

PCA probabilístico

Escribimos la verosimilitud como

​

​

p(x) es Gaussiana pues es una convolución �de dos gaussianas

Luego

​

​

​

​

​

​

​

Reducción de dimensionalidad, github @ phuijse, pablo dot huijse at gmail dot com

PCA probabilístico

Escribimos la verosimilitud como

​

​

p(x) es Gaussiana pues es una convolución �de dos gaussianas

Finalmente

​

​

​

​

​

​

​

Reducción de dimensionalidad, github @ phuijse, pablo dot huijse at gmail dot com

PCA probabilístico

Haciendo un proceso similar para el posterior obtenemos que

​

​

Donde

​

​

Es decir sólo la media de z depende de X

​

​

​

​

Reducción de dimensionalidad, github @ phuijse, pablo dot huijse at gmail dot com

PCA probabilístico

Para la solución de máxima verosimilitud resolvemos

​

​

​

• De las derivadas se obtienen formas cerradas para μ, W y σ
• Si los datos están centrados se puede omitir μ
• Otra opción es asignar priors para los parámetros y usar un tratamiento Bayesiano completo
• Es particularmente interesante asignar un prior para W. Así es posible aprender el número óptimo de dimensiones para Z

​

​

​

​

Reducción de dimensionalidad, github @ phuijse, pablo dot huijse at gmail dot com

Linear Discriminant Analysis (LDA)

• La proyección de máxima varianza puede no ser la de mayor interés

​

Reducción de dimensionalidad, github @ phuijse, pablo dot huijse at gmail dot com

Linear Discriminant Analysis (LDA)

• La proyección de máxima varianza puede no ser la de mayor interés
• Técnica de reducción de dimensionalidad supervisada
• También se conoce como Discriminante Lineal de Fisher (FLD)
• La proyección encontrada es lineal (como en PCA)
• Busca una rotación de los ejes de características que maximice la dispersión entre-clases y minimice la dispersión intra-clase

​

Reducción de dimensionalidad, github @ phuijse, pablo dot huijse at gmail dot com

Linear Discriminant Analysis (LDA)

• Sea un conjunto de datos M dimensionales con etiqueta categórica separados en dos clases

​

​

• Podemos definir las medias de los conjuntos como

​

​

​

• Lo que buscamos es un vector de proyección w tal que

Reducción de dimensionalidad, github @ phuijse, pablo dot huijse at gmail dot com

Linear Discriminant Analysis (LDA)

• Sea la matriz de dispersión entre-clases

​

​

• Sea la matriz de dispersión intra-clases

​

​

• La función de costo que buscamos maximizar es

Reducción de dimensionalidad, github @ phuijse, pablo dot huijse at gmail dot com

Linear Discriminant Analysis (LDA)

• Derivando en función de w e igualando a cero se llega a

​

​

• Que corresponde al problema de autovalores
• Dado que S_Bw está en la dirección (m1 - m2)

​

​

• Función discriminante: Si <w, x> supera un cierto umbral decimos que x pertenece a C1
• Esta regla de decisión es óptima si (a) las densidades condicionales son Gaussianas multivariadas y (b) las covarianzas son iguales.

​

​

Reducción de dimensionalidad, github @ phuijse, pablo dot huijse at gmail dot com

Linear Discriminant Analysis (LDA)

Sección 4.1.4, Bishop

Reducción de dimensionalidad, github @ phuijse, pablo dot huijse at gmail dot com

Multiple Discriminant Analysis (MDA)

• Se hacen una proyección a C-1 dimensiones de C es el número de clases
• Sólo funciona para datos con dimensionalidad M > C
• Se tiene ahora una matriz de proyección de M x (C-1)

​

​

• La matriz de dispersión entre-clases con m la media total es

​

​

​

• La matriz de dispersión intra-clases suma una covarianza por clases
• El vector óptimo de proyección se resuelve mediante autovalores

Reducción de dimensionalidad, github @ phuijse, pablo dot huijse at gmail dot com

Independent Component Analysis (ICA)

Pendiente

Reducción de dimensionalidad, github @ phuijse, pablo dot huijse at gmail dot com

Non-negative matrix factorization (NMF)

Pendiente

Reducción de dimensionalidad, github @ phuijse, pablo dot huijse at gmail dot com

Mapas auto-organizativos

• Los mapas auto-organizativos o mapas de Kohonen son un tipo de red neuronal no-supervisada para hacer proyección y visualización de datos

​

​

​

M

ℝ³

Reducción de dimensionalidad, github @ phuijse, pablo dot huijse at gmail dot com

Mapas auto-organizativos

• Los mapas auto-organizativos o mapas de Kohonen son un tipo de red neuronal no-supervisada para hacer proyección y visualización de datos
• Los datos son representados por un conjunto de vectores prototipo

​

​

M

ℝ³

Reducción de dimensionalidad, github @ phuijse, pablo dot huijse at gmail dot com

Mapas auto-organizativos

• Los mapas auto-organizativos o mapas de Kohonen son un tipo de red neuronal no-supervisada para hacer proyección y visualización de datos
• Los datos son representados por un conjunto de vectores prototipo
• Los prototipos se ordenan topológicamente en una grilla (bidimensional)

​

M

ℝ³

Reducción de dimensionalidad, github @ phuijse, pablo dot huijse at gmail dot com

Mapas auto-organizativos

• Los mapas auto-organizativos o mapas de Kohonen son un tipo de red neuronal no-supervisada para hacer proyección y visualización de datos
• Los datos son representados por un conjunto de vectores prototipo
• Los prototipos se ordenan topológicamente en una grilla (bidimensional)
• Los prototipos viven en el espacio de entrada y en la grilla

​

M

ℝ³

Reducción de dimensionalidad, github @ phuijse, pablo dot huijse at gmail dot com

Cuantización vectorial (VQ)

• Es una técnica para hacer compresión de datos
• VQ encuentro un conjunto de vectores prototipo (codebook) que representa a los datos
• Sea un conjunto de N datos D-dimensionales

​

​

• Se busca un codebook con K prototipos

​

​

• Donde una muestra cualquiera es aproximada como

Reducción de dimensionalidad, github @ phuijse, pablo dot huijse at gmail dot com

Cuantización vectorial (VQ)

• Es una técnica para hacer compresión de datos
• VQ encuentro un conjunto de vectores prototipo (codebook) que representa a los datos
• ¿Cómo se seleccionan los prototipos?
• Se usa la siguiente función de error

​

​

​

• Si optimizamos esta función estamos aproximando p(x)^N/(N+2)

​

​

Reducción de dimensionalidad, github @ phuijse, pablo dot huijse at gmail dot com

Cuantización vectorial (VQ)

• ¿Cómo se seleccionan los prototipos?
• Se usa la siguiente función de error

​

​

​

​

​

Reducción de dimensionalidad, github @ phuijse, pablo dot huijse at gmail dot com

Cuantización vectorial (VQ)

• ¿Cómo se seleccionan los prototipos?
• Se usa la siguiente función de error

​

​

​

​

​

Reducción de dimensionalidad, github @ phuijse, pablo dot huijse at gmail dot com

Cuantización vectorial (VQ)

• ¿Cómo se seleccionan los prototipos?
• Se usa la siguiente función de error

​

​

​

​

​

Al aplicar el limite:

Reducción de dimensionalidad, github @ phuijse, pablo dot huijse at gmail dot com

Cuantización vectorial (VQ)

• ¿Cómo se seleccionan los prototipos?
• Se usa el siguiente algoritmo de aprendizaje secuencial

​

Para una nueva muestra x(t)

​

​

​

​

​

Reducción de dimensionalidad, github @ phuijse, pablo dot huijse at gmail dot com

Mapas auto-organizativos (SOM)

• El mapa auto-organizativo conecta topológicamente los prototipos de VQ en una grilla bidimensional
• Noción de vecindad. Una muestra modifica el prototipo más cercano y sus vecinos topológicos

Algoritmo SOM

​

1. Encontrar BMU

​

Reducción de dimensionalidad, github @ phuijse, pablo dot huijse at gmail dot com

Mapas auto-organizativos (SOM)

• El mapa auto-organizativo conecta topológicamente los prototipos de VQ en una grilla bidimensional
• Noción de vecindad. Una muestra modifica el prototipo más cercano y sus vecinos topológicos

Algoritmo SOM

​

• Encontrar BMU
• Actualizar prototipos según BMU y vecindad

Reducción de dimensionalidad, github @ phuijse, pablo dot huijse at gmail dot com

Mapas auto-organizativos (SOM)

• El mapa auto-organizativo conecta topológicamente los prototipos de VQ en una grilla bidimensional
• Noción de vecindad. Una muestra modifica el prototipo más cercano y sus vecinos topológicos

Algoritmo SOM

​

• Encontrar BMU
• Actualizar prototipos según BMU y vecindad
• Disminuir la vecindad y la tasa de aprendizaje

​

Reducción de dimensionalidad, github @ phuijse, pablo dot huijse at gmail dot com

Mapas auto-organizativos (SOM)

• El mapa auto-organizativo conecta topológicamente los prototipos de VQ en una grilla bidimensional
• Noción de vecindad. Una muestra modifica el prototipo más cercano y sus vecinos topológicos

Algoritmo SOM

​

• Encontrar BMU
• Actualizar prototipos según BMU y vecindad
• Disminuir la vecindad y la tasa de aprendizaje
• Si no hay cambios, terminar

Reducción de dimensionalidad, github @ phuijse, pablo dot huijse at gmail dot com

Mapas auto-organizativos (SOM)

• El mapa auto-organizativo conecta topológicamente los prototipos de VQ en una grilla bidimensional
• Noción de vecindad. Una muestra modifica el prototipo más cercano y sus vecinos topológicos

Algoritmo SOM

• Vecindad

Reducción de dimensionalidad, github @ phuijse, pablo dot huijse at gmail dot com

Mapas auto-organizativos (SOM)

• El mapa auto-organizativo conecta topológicamente los prototipos de VQ en una grilla bidimensional
• Noción de vecindad. Una muestra modifica el prototipo más cercano y sus vecinos topológicos

Algoritmo SOM

• Vecindad: También se puede definir como

​

​

​

​

Nota: r es la posición del prototipo en la grilla

Reducción de dimensionalidad, github @ phuijse, pablo dot huijse at gmail dot com

Mapas auto-organizativos (SOM)

• El mapa auto-organizativo conecta topológicamente los prototipos de VQ en una grilla bidimensional
• Noción de vecindad. Una muestra modifica el prototipo más cercano y sus vecinos topológicos

​

Relación con k-means: En el caso de fijar la vecindad Nc = c, es decir sólo actualizar el BMU, se recupera una versión on-line de k-means

​

​

​

Reducción de dimensionalidad, github @ phuijse, pablo dot huijse at gmail dot com

Mapas auto-organizativos (SOM)

• Es posible usar SOM para hacer clustering
• Se pueden visualizar las distancias en la grilla usando técnicas de post-procesamiento
• Un ejemplo es la U-matrix (Unified-distance matrix)

Reducción de dimensionalidad, github @ phuijse, pablo dot huijse at gmail dot com

Mapas auto-organizativos (SOM)

• Es posible usar SOM para hacer clustering
• Se pueden visualizar las distancias en la grilla usando técnicas de post-procesamiento
• U-matrix: Suma de distancias a sus vecinos más cercanos. A cada prototipo se le asigna un color correspondiente a su lejanía relativa

Reducción de dimensionalidad, github @ phuijse, pablo dot huijse at gmail dot com

Mapas auto-organizativos (SOM)

• Es posible usar SOM para hacer clustering
• Se pueden visualizar las distancias en la grilla usando técnicas de post-procesamiento
• U-matrix: Suma de distancias a sus vecinos más cercanos. A cada prototipo se le asigna un color correspondiente a su lejanía relativa
• ¿Cuáles ejemplos son similares?

X

Y

B

A

Z

C

Reducción de dimensionalidad, github @ phuijse, pablo dot huijse at gmail dot com

Mapas auto-organizativos (SOM)

​

Recomendaciones de Teuvo Kohonen

• Condiciones de convergencia: Decaer la tasa de aprendizaje y la �vecindad exponencialmente
• Las vecindades hexagonales son preferibles a las rectangulares por ser visualmente más ilustrativas y precisas
• Nx > Ny o viceversa para darle orientación al mapa y facilitar la convergencia
• El número de neuronas es la resolución del mapa. Más neuronas revelarán estructuras más finas pero incrementan el tiempo de cómputo. Se escoge mediante prueba-y-error
• Para evitar efectos de bordes se puede usar una grilla toroidal (cíclica)
• Para una convergencia más estable conviene separar el entrenamiento en etapa de ajuste grueso y etapa de ajuste fino

​

Reducción de dimensionalidad, github @ phuijse, pablo dot huijse at gmail dot com

Mapas auto-organizativos (SOM)

Implementaciones

• Python: github.com/peterwittek/somoclu
• Matlab: http://www.cis.hut.fi/somtoolbox

​

​

Libro de Teuvo Kohonen con implementaciones en MATLAB disponible libremente en

​

docs.unigrafia.fi/publications/kohonen_teuvo/

Reducción de dimensionalidad, github @ phuijse, pablo dot huijse at gmail dot com

Neural Gas (NG)

• Es una variante de SOM que no usa grilla
• NG es máx flexible ya que no está restringido por la forma de la grilla

​

Algoritmo NG

​

• Encontrar BMU

​

Reducción de dimensionalidad, github @ phuijse, pablo dot huijse at gmail dot com

Neural Gas (NG)

• Es una variante de SOM que no usa grilla
• NG es máx flexible ya que no está restringido por la forma de la grilla

​

Algoritmo NG

​

• Encontrar BMU
• Actualizar prototipos según BMU y ranking

​

Reducción de dimensionalidad, github @ phuijse, pablo dot huijse at gmail dot com

Neural Gas (NG)

• Es una variante de SOM que no usa grilla
• NG es máx flexible ya que no está restringido por la forma de la grilla

​

Algoritmo NG

​

• Encontrar BMU
• Actualizar prototipos según BMU y ranking
• Disminuir la vecindad y la tasa de aprendizaje

​

Reducción de dimensionalidad, github @ phuijse, pablo dot huijse at gmail dot com

Neural Gas (NG)

• Es una variante de SOM que no usa grilla
• NG es máx flexible ya que no está restringido por la forma de la grilla

​

Algoritmo NG

​

• Encontrar BMU
• Actualizar prototipos según BMU y ranking
• Disminuir la vecindad y la tasa de aprendizaje
• Si no hay cambios, terminar

​

Reducción de dimensionalidad, github @ phuijse, pablo dot huijse at gmail dot com

Transformación no lineal

• Es posible transformar nuestros datos a un nuevo �espacio de mayor dimensionalidad
• Los algoritmo lineales se pueden usar en el espacio transformado
• Generalmente es más fácil encontrar hiperplanos separadores o proyecciones en el espacio aumentado los cuales equivalen a fronteras o proyecciones no-lineales en el espacio de entrada

​

Reducción de dimensionalidad, github @ phuijse, pablo dot huijse at gmail dot com

Kernel

• Un kernel es:
• Un producto punto generalizado
• Una generalización de una matriz/función definida positiva
• Un operador de mapeo que tiene la propiedad de reproducción
• Truco del kernel

​

• Para un cierto conjunto de datos definimos la matriz Gram como

​

​

​

​

​

​

Sección 5.8.1, Hastie, Tibshirani, Friedman

Reducción de dimensionalidad, github @ phuijse, pablo dot huijse at gmail dot com

Kernel

• Sea un kernel

​

• ¿Qué transformación no-lineal induce en los datos?

​

Reducción de dimensionalidad, github @ phuijse, pablo dot huijse at gmail dot com

Kernel

• Sea un kernel

​

​

Reducción de dimensionalidad, github @ phuijse, pablo dot huijse at gmail dot com

Ejemplos de kernels

Kernel polinomial inhomogeneo

​

​

Kernel Gaussiano o Radial Basis Function (RBF)

​

​

Kernel tangente hiperbólica

Reducción de dimensionalidad, github @ phuijse, pablo dot huijse at gmail dot com

Kernel PCA

• Es una versión “kernelizada” de PCA
• Kernel es un producto interno en un espacio de alta dimensión �que induce una transformación no lineal
• Usando kernels podemos generalizar PCA al caso no-lineal
• No necesitamos conocer la transformación no lineal

​

​

​

​

​

​

1. B. Sholkopf, A. Smola, KR Muller, “Kernel Principal Component Analysis”, Springer, 1997
2. Sección 12.3, Bishop, Pattern Recognition and Machine Learning

​

Reducción de dimensionalidad, github @ phuijse, pablo dot huijse at gmail dot com

Kernel PCA

Recordemos, PCA es una proyección de máxima varianza que resulta de resolver el problema de valores propios para la matriz de covarianza

​

​

Sea ahora una transformación no lineal que aumenta la dimensionalidad de los datos, definimos una covarianza generalizada (matriz gram)

​

​

​

Donde asumimos que los datos transformados están centrados

​

Reducción de dimensionalidad, github @ phuijse, pablo dot huijse at gmail dot com

Kernel PCA

Luego el objetivo es resolver el problema de autovalores para K

​

​

Los valores propios tienen la forma

​

​

Son una combinación lineal que usa la transformación no lineal como base

​

​

​

Reducción de dimensionalidad, github @ phuijse, pablo dot huijse at gmail dot com

Kernel PCA

Reemplazando arriba se tiene y multiplicando por φ^T

​

​

Se encuentra autovalores equivalentes resolviendo

​

​

Usamos el truco del kernel para formar la matriz Gram

Reducción de dimensionalidad, github @ phuijse, pablo dot huijse at gmail dot com

Kernel PCA

Se restringe que los componentes de V estén normalizados

​

​

​

Para proyectar una nueva muestra al espacio de los �componentes principales kernelizados

Reducción de dimensionalidad, github @ phuijse, pablo dot huijse at gmail dot com

Kernel PCA

Algoritmo

1. Computar matriz gram
2. Normalizar matriz gram
3. Resolver el problema de v.p.
4. Normalizar los coeficientes
5. Proyectar los datos

Reducción de dimensionalidad, github @ phuijse, pablo dot huijse at gmail dot com

Kernel PCA

Algoritmo

• Computar matriz gram
• Normalizar matriz gram
• Resolver el problema de v.p.
• Normalizar los coeficientes
• Proyectar los datos

Reducción de dimensionalidad, github @ phuijse, pablo dot huijse at gmail dot com

Kernel PCA

Algoritmo

• Computar matriz gram
• Normalizar matriz gram
• Resolver el problema de v.p.
• Normalizar los coeficientes
• Proyectar los datos

Reducción de dimensionalidad, github @ phuijse, pablo dot huijse at gmail dot com

Kernel PCA

Algoritmo

• Computar matriz gram
• Normalizar matriz gram
• Resolver el problema de v.p.
• Normalizar los coeficientes
• Proyectar los datos

Reducción de dimensionalidad, github @ phuijse, pablo dot huijse at gmail dot com

Kernel PCA

Algoritmo

• Computar matriz gram
• Normalizar matriz gram
• Resolver el problema de v.p.
• Normalizar los coeficientes
• Proyectar los datos

Reducción de dimensionalidad, github @ phuijse, pablo dot huijse at gmail dot com

Kernel PCA

Proyección lineal en el espacio de alta dimensionalidad equivale a una proyección no-lineal en el espacio de entrada

Reducción de dimensionalidad, github @ phuijse, pablo dot huijse at gmail dot com

Kernel PCA

• No necesitamos conocer la transformación no lineal (truco del kernel)
• Lo complejidad computacional no aumenta con la dimensión de la transformación no lineal
• Si se limita el número de componentes principales en la proyección se reduce la dimensionalidad de los datos
• Proyectar de vuelta al espacio original no es trivial
• Dos estrategias:
• Características no lineales + clasificador lineal
• Características lineales + clasificador no lineal

Reducción de dimensionalidad, github @ phuijse, pablo dot huijse at gmail dot com

Autoencoder

• Redes neuronales no-supervisadas
• Arquitectura diabolo

​

​

...

...

...

...

...

...

Reducción de dimensionalidad, github @ phuijse, pablo dot huijse at gmail dot com

Autoencoder

• Redes neuronales no-supervisadas
• Arquitectura diabolo
• Paradigma self-taught learning (auto-aprendizaje)
• El objetivo es reproducir la entrada

​

​

...

...

...

...

...

...

Reducción de dimensionalidad, github @ phuijse, pablo dot huijse at gmail dot com

Autoencoder

• Redes neuronales no-supervisadas
• Arquitectura diabolo
• Paradigma self-taught learning (auto-aprendizaje)
• El objetivo es reproducir la entrada
• Cuello de botella: variable latente

​

​

​

...

...

...

...

...

...

Reducción de dimensionalidad, github @ phuijse, pablo dot huijse at gmail dot com

Autoencoder

• Redes neuronales no-supervisadas
• Arquitectura diabolo
• Paradigma self-taught learning (auto-aprendizaje)
• El objetivo es reproducir la entrada
• Cuello de botella: variable latente
• Se usa para aprender representaciones latentes comprimidas específicas al conjunto de datos

​

​

...

...

...

...

...

...

-1.2

5.4

Reducción de dimensionalidad, github @ phuijse, pablo dot huijse at gmail dot com

Autoencoder

Ejemplo de arquitectura de autoencoder

​

​

...

...

...

...

...

...

-1.2

5.4

Capa fully-connected

Capa fully-connected

Capa latente

Reducción de dimensionalidad, github @ phuijse, pablo dot huijse at gmail dot com

Autoencoder

Ejemplo de arquitectura de autoencoder

• Pueden concatenarse varias capas densas
• Si se usa activación lineal se recupera una solución similar a PCA
• Se entrena usando MSE para variables continuas o cross-entropy para variables categóricas (imágenes)
• Los autoencoders profundos son difíciles �de entrenar

​

​

...

...

...

...

...

...

-1.2

5.4

Capa fully-connected

Capa fully-connected

Capa latente

Reducción de dimensionalidad, github @ phuijse, pablo dot huijse at gmail dot com

Autoencoder

• Stacked autoencoder: Autoencoders conectados en serie

​

Reducción de dimensionalidad, github @ phuijse, pablo dot huijse at gmail dot com

Autoencoder

• Stacked autoencoder: Autoencoders conectados en serie
• Convolutional autoencoder: Se usan capas convoluciones y de-convolucionales para aprovechar las invarianzas y características locales que se aprenden con estas arquitecturas

​

Reducción de dimensionalidad, github @ phuijse, pablo dot huijse at gmail dot com

Autoencoder

• Stacked autoencoder: Autoencoders conectados en serie
• Convolutional autoencoder: Se usan capas convoluciones y de-convolucionales para aprovechar las invarianzas y características locales que se aprenden con estas arquitecturas
• Sparse autoencoder: Se penaliza con norma L1 la capa latente
• Denoising autoencoder: Se agrega ruido a la entrada antes de entrenar
• Variational autoencoder: Utiliza un modelo generativo en la capa latente

Reducción de dimensionalidad, github @ phuijse, pablo dot huijse at gmail dot com

Autoencoder Variacional

GIFs: http://blog.fastforwardlabs.com

Reducción de dimensionalidad, github @ phuijse, pablo dot huijse at gmail dot com

t-distributed Stochastic Neighbor Embedding

• Es una técnica de reducción de dimensionalidad no lineal
• Enfocado a 2 (3) dimensiones (visualización)
• Usa métricas de teoría de la información
• Generalización de Stochastic Neighbor Embedding (SNE)

​

​

​

​

​

​

L.J.P. van der Maaten, G.E. Hinton, "Visualizing High-Dimensional Data Using t-SNE", Journal of Machine Learning Research, vol. 9, pp. 2579–2605, 2008

​

Reducción de dimensionalidad, github @ phuijse, pablo dot huijse at gmail dot com

t-distributed Stochastic Neighbor Embedding

Generalización de Stochastic Neighbor Embedding (SNE)

Sea

​

Se generan probabilidades condicionales

​

​

​

​

Se interpreta como la pbb de que xi sea vecino de xj dentro de una vecindad de tamaño si

Reducción de dimensionalidad, github @ phuijse, pablo dot huijse at gmail dot com

t-distributed Stochastic Neighbor Embedding

Generalización de Stochastic Neighbor Embedding (SNE)

El objetivo es preservar las similitudes, que se traduce a igualar las pbb condicionales, para esto se minimiza

​

​

La divergencia KL no es simétrica. Para seleccionar el tamaño de vecindad:

​

​

La “perplejidad” se interpreta como el Nº efectivo de vecinos

Reducción de dimensionalidad, github @ phuijse, pablo dot huijse at gmail dot com

t-distributed Stochastic Neighbor Embedding

En t-SNE se generaliza SNE

• Versión simétrica de la función de costo
• Distribución t-Student en vez de Gaussiana

​

Esto facilita la optimización del funcional y alivia el “problema de crowding”

Reducción de dimensionalidad, github @ phuijse, pablo dot huijse at gmail dot com

t-distributed Stochastic Neighbor Embedding

Se reemplazan las probabilidades condicionales por conjuntas

Reducción de dimensionalidad, github @ phuijse, pablo dot huijse at gmail dot com

t-distributed Stochastic Neighbor Embedding

Para el espacio de baja dimensionalidad se reemplaza la distribución Gaussiana por una distribución t-Student de colas anchas

Reducción de dimensionalidad, github @ phuijse, pablo dot huijse at gmail dot com

t-distributed Stochastic Neighbor Embedding

Reducción de dimensionalidad, github @ phuijse, pablo dot huijse at gmail dot com

t-distributed Stochastic Neighbor Embedding

http://distill.pub/2016/misread-tsne/

​

t-SNE

Sammon

Isomap

Reducción de dimensionalidad, github @ phuijse, pablo dot huijse at gmail dot com

t-distributed Stochastic Neighbor Embedding

• Revela clusters y retiene estructuras locales de los datos
• Mejor desempeño que otros algoritmos de embedding
• No funciona bien si la dimensionalidad intrínseca del manifold es grande
• Función de costo no convexa y complejidad cuadrática (barnes-hut)
• No es inductivo

Reducción de dimensionalidad, github @ phuijse, pablo dot huijse at gmail dot com