Aprendizaje No Supervisado

# Aprendizaje No Supervisado
## Curso JAE ICMAT 2021
### Roi Naveiro y David Ríos Insua
### 2021-06-22

---

# 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**:

* 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}$` 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

**Datos**:

* 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

**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 (reducción de la dimensionalidad): PCA, PCA no lineal, self-organizing maps, modelos de variables latentes, autoencoders, ...

* 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, ...

---

# 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)

* `$S = \frac{1}{N} \sum_{i=1}^N (x_n - \bar{x})(x_n - \bar{x})^T$`, matriz de covarianza.

* 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_{ni}\}$`

`\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

---