Conceptos generales de aprendizaje no supervisado

# Conceptos generales de aprendizaje no supervisado
## Curso de aprendizaje automático para el INE
### Víctor Gallego y Roi Naveiro
### 2019-04-01

---

# Introducción

---

## Aprendizaje Supervisado

* Espacio de las muestras de entrada: `$\mathcal{X}$`

* Espacio de las salidas: `$\mathcal{Y}$`

**Dados**:

* Conjunto de **entrenamiento**: `$S = \{x_i,\, y_i\}_{i=1}^N$`, con `$x_i, y_i \in \mathcal{X} \times \mathcal{Y}$`

* Visión probabilística: `$x_i, y_i \sim P(X,Y)$`

**Objetivo**:

* Aprender una regla de predicción (hipótesis), `$h: \mathcal{X} \rightarrow \mathcal{Y}$`
  
  * Visión probabilística: estimar `$P(Y|X)$`
  
---

## Aprendizaje Supervisado
**Estrategia básica**:

* MLE de algún modelo paramétrico
  
  `$$\arg\max_{w} \prod_{i=1}^N P(y_i|x_i, w)$$`
  
**Facilidades**:

* `$\mathcal{Y}$` es tiene dimensión baja
  
  * Es sencillo cuantificar el error: natural definir función de coste. Error = valor esperado de coste bajo `$P(X,Y)$`.

---

## Aprendizaje No Supervisado

**Dados**:

* No hay salidas: `$S = \{x_i\}_{i=1}^N$`, con `$x_i \in \mathcal{X}$`

* Visión probabilística: `$x_i \sim P(X)$`

**Objetivo**:

* Estimar `$P(X)$`
  
  * Inferir alguna propiedad de `$P(X)$`
  
  * Muestrear de `$P(X)$`

---

## Retos del Aprendizaje No Supervisado

* `$X$` generalmente es de alta dimensión (piensa en imágenes: `$128 \times 128 \times 3 = 49152)$`

* Propiedades de interés que queremos inferir son más complejas que simples parámetros

* No hay una medida directa de cuantificar el error

* Métodos heurísticos no solo para motivar los algoritmos sino también para medir la calidad de los resultados

**Buen proxy de la dificultad de cada área !!**
---

## Una taxonomía de algoritmos de aprendizaje no supervisado según su objetivo

* Métodos de estimación de densidades

* Manifold learning: PCA, PCA no lineal, self-organizing maps, modelos de variables latentes, ...

* Encontrar regiones convexas del espacio que contengan modas de `$P(X)$`: análisis de cluster, modelos de mixturas,
...

* Muestrear de `$P(X)$`: GAN, autoencoders, autoencoders variacionales, ...

---

# Repaso Álgebra Lineal

---

## Aplicaciones lineales

* Dado `$\boldsymbol{x} \in \mathbb{R}^N$`, una **aplicación (función) lineal**  `$f : \mathbb{R}^N \rightarrow \mathbb{R}^M$` se expresa como
$$
f(\boldsymbol{x}) = W \boldsymbol{x}
$$
donde `$W$` es una matriz de tamaño `$M \times N$`.

* Para el caso `$M = N$`, los **autovalores** `$\lambda \in \mathbb{R}$` y los **autovectores** `$\boldsymbol{v} \in \mathbb{R}^M$` son los elementos que cumplen

$$
W \boldsymbol{v} = \lambda \boldsymbol{v}
$$

* Si los vectores columna de `$W = \left[ w_1, \ldots, w_M \right]$` son ortonormales (esto es, `$w_i^{\intercal} w_j = 0, w_i^{\intercal} w_i = 1$`), se dice que `$W$` es una proyección ortonormal. En este caso, los vectores `$\left[ w_1, \ldots, w_M \right]$` forman una base ortonormal.

---

## Derivadas matriciales

* Será necesario considerar derivadas de vectores respecto a escalares. En este caso,

$$
\left( \frac{\partial \boldsymbol{a}}{\partial x}  \right)_i = \frac{\partial \boldsymbol{a}_i}{\partial x}
$$

* También podemos derivar respecto a vectores o matrices:

`\begin{equation}
\left( \frac{\partial x}{\partial \boldsymbol{a}}  \right)_i = \frac{\partial x}{\partial \boldsymbol{a}_i}, \left( \frac{\partial \boldsymbol{a}}{\partial \boldsymbol{b}}  \right)_{i,j} = \frac{\partial \boldsymbol{a}_i}{\partial \boldsymbol{b}_j} 
\end{equation}`

* *Ejercicio*. Probar que

$$
\frac{\partial \boldsymbol{x}^{\intercal} \boldsymbol{a}}{\partial \boldsymbol{x}} = \frac{\partial \boldsymbol{a}^{\intercal} \boldsymbol{x}}{\partial \boldsymbol{x}} = \boldsymbol{a}
$$
y que
$$
\frac{\partial \boldsymbol{A} \boldsymbol{B}}{\partial x} = \frac{\partial \boldsymbol{A}}{\partial x}\boldsymbol{B} + \frac{\partial \boldsymbol{B}}{\partial x}\boldsymbol{A}.
$$

---

## Optimización

* Queremos optimizar una función diferenciable `$f(\boldsymbol{x})$` tal que `$f : \mathbb{R}^N \rightarrow \mathbb{R}$`. Los **óptimos locales** verifican

$$
\frac{\partial f(\boldsymbol{x})}{\partial \boldsymbol{x}} = 0
$$

* En el caso de querer optimizar `$f(\boldsymbol{x})$` sujeto a demás a una restricción `$g(\boldsymbol{x}) = 0$`, podemos utilizar el **Teorema de los multiplicadores de Lagrange** y optimizar la siguiente función objetivo (ya sin restricciones):

$$
f(\boldsymbol{x}) + \lambda g(\boldsymbol{x})
$$

---

# Métodos Lineales reducción de dimensionalidad
# Análisis de Componentes Principales

---

## Dos definiciones alternativas

* Proyección ortogonal de datos a subespacio de dimensión inferior tal que varianza de proyecciones es máxima

* Proyección lineal que minimiza el *coste medio de proyección* = distancia media cuadrática entre datos y sus proyecciones

* Ambos dan lugar al mismo algoritmo!

* Diferentes aplicaciones: reducción de dimensionalidad, compresión, visualización de datos, extracción de variables predictoras...

---

# Formulación por Máxima Varianza
---

## PCA: Formulación por Máxima Varianza (1)

* Dados: `$x_n \in \mathbb{R}^D,\quad n = 1, \ldots, N$`

* Objetivo: encontrar proyección lineal `$\pi: \mathbb{R}^D \rightarrow \mathbb{R}^M$` tal que `$M < D$` y se maximize la varianza de los datos proyectados.

* Ejemplo `$\mathbb{R}^2 \rightarrow \mathbb{R}^1$`:

![:scale 100%](./img/pca_anim.gif)
---

## PCA: Formulación por Máxima Varianza (2)

* Empezamos considerando proyección a `$\mathbb{R}$` ( `$M = 1$` ).

* Una proyección viene representada por su dirección, esto es, un vector `$\boldsymbol{u}_1 \in \mathbb{R}^D$`. Como sólo nos interesa la dirección, imponemos `$\boldsymbol{u}_1^\intercal \boldsymbol{u}_1 = 1$`.

* `$\boldsymbol{u}_1^\intercal x_n$` es la proyección del n-ésimo punto.

* También nos interesa calcular:
  
  * La media de los datos proyectados
    $$ \frac{1}{N} \sum_{n=1}^N \boldsymbol{u}_1^\intercal x_n = \boldsymbol{u}_1^\intercal \bar{x}  $$
    
  * La varianza de los datos proyectados
  
    $$  \frac{1}{N} \sum_{n=1}^N (\boldsymbol{u}_1^\intercal x_n - \boldsymbol{u}_1^\intercal \bar{x})^2 = \boldsymbol{u}_1^\intercal \boldsymbol{S} \boldsymbol{u}_1 $$

---

## PCA: Formulación por Máxima Varianza (3)

* Ahora ya podemos plantear un problema de optimización, con objetivo:

$$
\max_{\boldsymbol{u}_1} \boldsymbol{u}_1^\intercal \boldsymbol{S} \boldsymbol{u}_1
$$

* con la restricción:

$$
\boldsymbol{u}_1^\intercal \boldsymbol{u}_1 = 1
$$

* Para resolverlo, utilizamos la formulación Lagrangiana, con lo que lo convertimos al siguiente problema de optimización sin restricciones:

$$
\max_{\boldsymbol{u}_1} \boldsymbol{u}_1^\intercal \boldsymbol{S} \boldsymbol{u}_1 + \lambda_1 (\boldsymbol{u}_1^\intercal \boldsymbol{u}_1 - 1)
$$

* Derivamos...

---

## PCA: Formulación por Máxima Varianza (4)

* Queda que

$$
\boldsymbol{S} \boldsymbol{u}_1 = \lambda_1 \boldsymbol{u}_1
$$
es decir, `$\boldsymbol{u}_1$` es *autovector de la matriz de covarianzas* `$\boldsymbol{S}$`.

* Más aún,

$$
\boldsymbol{u}_1^\intercal \boldsymbol{S} \boldsymbol{u}_1 = \lambda_1
$$
la *varianza es precisamente el mayor autovalor*

* El autovector `$\boldsymbol{u}_1$` asociado al mayor autovalor, `$\lambda_1$` es conocido como *primera componente principal*.

---

# Minimización de Error de Proyección

---

## PCA: Minimización de Error de Proyección (1)

* Considérese  el conjunto de observaciones `$\lbrace x_n \rbrace_{n=1}^{N}$`, donde `$x_n \in \mathbb{R}^D$`

* `$\lbrace u_i \rbrace_{i=1}^{D}$`: base ortonormal completa de dimension `$D$`

`\begin{equation}
x_n = \sum_{i=1}^D \alpha_{ni} u_i
\end{equation}`

* Sin pérdida de generalidad

`\begin{equation}
x_n = \sum_{i=1}^D (x_n^\top u_i) u_i
\end{equation}`

* Interés: aproximar dato usando representación que requiera `$M<D$` parámetros.

---

## PCA: Minimización de Error de Proyección (2)

* Representamos el subespacio de dimensión `$M$` con los primeros `$M$` vectores de la base

`\begin{equation}
\tilde{x}_n = \sum_{i=1}^M (z_{ni} u_i)  + \sum_{i=M+1}^D b_i u_i
\end{equation}`

* Escogemos `$\{z_{in}\}$`, `$\{b_{i}\}$` y `$\{u_{i}\}$` para distorsión introducida por reducción de dimensión

`\begin{equation}
J = \frac{1}{N}\sum_{n=1}^N \Vert x_n - \tilde{x}_n \Vert^2
\end{equation}`

* Minimizando respecto `$\{z_{in}\}$`

`\begin{equation}
z_{nj} = x_n^\top u_j
\end{equation}`

* Minimizando respecto `$\{b_{i}\}$`

`\begin{equation}
b_{j} = \left( \frac{1}{N} \sum_{n=1}^N x_n^\top \right)^\top u_j = \bar{x}^\top u_j
\end{equation}`

---

## PCA: Minimización de Error de Proyección (3)

* Substituyendo en la expresión de `$\tilde{x}_n$`

`\begin{equation}
x_n - \tilde{x}_n = \sum_{i=M+1}^D \left \lbrace (x_n - \bar{x})^\top u_i  \right \rbrace u_i
\end{equation}`

* Vector desplazamiento ortogonal al *subespacio principal*. Substituendo en `$J$`

`\begin{equation}
J = \frac{1}{N} \sum_{n=1}^N \sum_{i=M+1}^D \left( x_n^\top u_i - \bar{x}^\top u_i \right)^2 = \sum_{i=M+1}^D u^\top_i S u_i
\end{equation}`

Donde `$S = \frac{1}{N} \sum_{i=1}^N (x_n - \bar{x})(x_n - \bar{x})^\top$`.

* Falta minimizar respecto de `$\{u_{i}\}$`, sujeto a `$u_i^\top u_i = 1$`

---

## PCA: Minimización de Error de Proyección (4)

* Intuición: `$D=2$` y `$M=1$`: encontra `$u_2$` que minimice `$J = u^\top_2 S u_2$`, sujeto a `$u_2^Tu_2 = 1$`.

`\begin{equation}
\tilde{J} = u_2^\top S u_2 + \lambda_2(1-u_2^\top u_2)
\end{equation}`

* Derivando e igualando a 0: `$S u_2 = \lambda_2 u_2$` `$\Rightarrow$` todo autovector define un punto estacionario.

* En el mínimio `$J=\lambda_2$`: escogemos `$u_2$` con autovalor mínimo. Luego **subespacio principal** definido por autovectores de autovalor máximo.

---

## PCA: Minimización de Error de Proyección (5)

* Solución general: escoger como `$\{u_{i}\}$` los autovectores de la matriz de covarianza

`\begin{equation}
S u_i = \lambda_i u_i
\end{equation}`

* El valor de distorsión es entonces `$J = \sum_{i= M+1}^D \lambda_i$`.

* `$J$` será mínimo si escogemos los `$D-M$` autovectores de menor autovalor.

* Los autovectores definiendo el subespacio principal, serán los de mayor autovalor.

---

# Aplicaciones de PCA

---