Rmd/10-pgms/10-pgms.html

<!DOCTYPE html>
<html xmlns="http://www.w3.org/1999/xhtml" lang="" xml:lang="">
  <head>
    <title>Modelos Gráficos Probabilísticos (PGMs)</title>
    <meta charset="utf-8" />
    <meta name="author" content="Víctor Gallego y Roi Naveiro" />
    <meta name="date" content="2019-05-26" />
    <link href="libs/remark-css-0.0.1/default.css" rel="stylesheet" />
    <link rel="stylesheet" href="custom.css" type="text/css" />
  </head>
  <body>
    <textarea id="source">
class: center, middle, inverse, title-slide

# Modelos Gráficos Probabilísticos (PGMs)
## Curso de aprendizaje automático para el INE
### Víctor Gallego y Roi Naveiro
### 2019-05-26

---


class: middle, center, inverse

# Introducción

---

## Representar gráficamente distribuciones de probabilidad. Ventajas

* Forma simple de visualizar la estructura de modelos probabilísticos.

* Diseño y motivación de nuevos modelos.

* Facilita comprender propiedades de los modelos, como la independencia condicional.

* Cálculos complejos pueden ser expresados en términos de manipulaciones gráficas sencillas.


---

class: middle, center, inverse

# Redes Bayesianas

---
## Introducción

* Podemos representar cualquier distribución de probabilidad utilizando un **grafo acíclico dirigido** (DAG).

* Cada nodo es una variable aleatoria de la distribución.

* Arcos entre nodos representan dependencias condicionales.

* Dado un DAG, la distribución de probabilidad conjunta es

`\begin{equation}
p(x) = \prod_{k=1}^K p(x_k \vert \text{pa}_k)
\end{equation}`

---

## Introducción

* **Ejercicio**: Factoriza y representa gráficamente la distribución `\(p(a,b,c)\)`.

* **Ejercicio**: ¿A qué distribución corresponde este DAG?

&lt;center&gt;
![:scale 50%](./img/pgm1.png)
&lt;/center&gt;


---

## Notación

* Para expresar multiplicidad de variables aleatorias se utiliza la siguiente notación


&lt;center&gt;
![:scale 50%](./img/plate1.png)
![:scale 50%](./img/plate2.png)
&lt;/center&gt;

---

## Notación

* Los parámetros deterministas se representan usando círculos sólidos.

* Las variables observadas se colorean.

&lt;center&gt;
![:scale 50%](./img/full1.png)
&lt;/center&gt;

* **Ejercicio**: ¿Qué modelo representa esta Red Bayesiana?

---

## Independencia Condicional

* Decimos que `\(a\)` y `\(b\)` son condicionalmente independientes dado `\(c\)` si `\(p(a \vert b,c) = p(a \vert c)\)` o `\(p(a,b \vert c) = p(a \vert c) p(b \vert c)\)`.

* Los PGMs permiten identificar las propiedades de independencia condicional de la distribución conjunto de forma automática.

---

## Ejemplo 1

* Nodo *tail-to-tail*
* Si se condiciona en `\(c\)` este nodo bloquea el camino entre `\(a\)` y `\(b\)`, y se cumple independencia condicional.
&lt;center&gt;
![:scale 40%](./img/ci1.png)
&lt;/center&gt;

&lt;center&gt;
![:scale 40%](./img/ci2.png)
&lt;/center&gt;

---

## Ejemplo 2

* Nodo *head-to-tail*
* Si se condiciona en `\(c\)` este nodo bloquea el camino entre `\(a\)` y `\(b\)`, y se cumple independencia condicional.
&lt;center&gt;
![:scale 40%](./img/ci3.png)
&lt;/center&gt;

&lt;center&gt;
![:scale 40%](./img/ci4.png)
&lt;/center&gt;


---

## Ejemplo 3

* Nodo *head-to-head*
* Si se `\(c\)` **no se observa** bloquea el camino entre `\(a\)` y `\(b\)` y estas son independientes.
* Si se `\(c\)` **se observa** el camino se desbloquea: `\(a\)` y `\(b\)` y son dependientes.
&lt;center&gt;
![:scale 35%](./img/ci5.png)
&lt;/center&gt;

&lt;center&gt;
![:scale 35%](./img/ci6.png)
&lt;/center&gt;

---
## D-separación

* Consideremos un DAG general y sean `\(A\)`, `\(B\)` y `\(C\)` conjuntos de nodos diferentes.

* Queremos determinar si `\(A\)` y `\(B\)` son condicionalmente independientes dado `\(C\)`.

* Consideremos todas las trayectorias entre `\(A\)` y `\(B\)`. Diremos que alguna de estas está bloqueada si:
  * Las flechas del camino encuentran un nodo *head-to-tail* o *tail-to-tail* y este está en `\(C\)`.
  
  * Las flechas del camino encuentran un nodo *head-to-head* y ni el nodo ni sus descendientes están en `\(C\)`.

* Si todos los caminos entre `\(A\)` y `\(B\)` están bloqueados, entonces `\(A\)` y `\(B\)` están `\(d\)`-separados por `\(C\)` y son condicionalmente independientes dado `\(C\)`.

---
## D-separación
* Determinar si `\(a\)` y `\(b\)` son condicionalmente independientes dados los nodos observados en cada caso.

&lt;center&gt;
![:scale 100%](./img/ejci.png)
&lt;/center&gt;

---
## D-separación
* Dibuja la red bayesiana de un modelo de Naive-Bayes

* Estudia la independencia condicional entre `\(t_n\)` y `\(\hat{t}\)`.

&lt;center&gt;
![:scale 50%](./img/ci_ex.png)
&lt;/center&gt;

---
## D-separación

* A efectos de `\(D\)`-separación, los parámetros se comportan como variables aleatorias observadas.

* Como nunca tienen padres son siempre nodos *tail-to-tail* y bloquean todas las trayectorias en las que intervienen.

* El conjunto de distribuciones que pueden ser expresadas en términos de la factorización implicada por un DAG, se denomina `\(\mathcal{DF}\)`.

* `\(\mathcal{DF}\)` coincide con todas las distribuciones que cumplen las propiedades de independencia condicional del DAG.

* Se denomina *Markov Blanket* de una variable `\(x_i\)` al conjunto de padres, hijos y co-padres de `\(x_i\)`.

* Demostrar que para una distribución arbitraria `\(p(x_1, \dots, x_D)\)`, `\(p(x_i \vert x_{\lbrace j \neq i \rbrace})\)` depende únicamente de las variables del *Markov Blanket* de `\(x_i\)`.

---
class: middle, center, inverse

# Markov Random Fields

---

## Modelos gráficos no dirigidos

* También conocidos como **redes de Markov**.

* Los enlaces ahora **no son dirigidos**.

--

* **Ventaja**: la propiedad de independencia se puede verificar mucho más fácilmente:

  * **d-separación**: `\(A  \perp B | C\)` sii todos los caminos entre `\(A\)` y `\(B\)` están bloqueados por nodos de `\(C\)`. 
  
  * Corolario: no hay fenómeno de **explaining away**.
  
* Markov blanket: todos los nodos adyacentes.
  

&lt;center&gt;
![:scale 70%](./img/mrf1.png)
&lt;/center&gt;

---

## Propiedades de factorización

* Consideremos dos nodos `\(x_i\)` y `\(x_j\)` que no estén conectados por arco. 

* Como no hay camino directo, dado el resto de nodos, todos los caminos están bloqueados.

* Por tanto, `\(p(x_i, x_j| x_{\setminus \lbrace i,j \rbrace}) = p(x_i| x_{\setminus  \lbrace i,j \rbrace})p(x_j| x_{\setminus  \lbrace i,j \rbrace})\)`.


--

Es conveniente introducir el concepto de **clique**:

* **Clique**: subgrafo donde cada par de nodos está conectado por **un** enlace.

* **Clique maximal**: clique al cual no es posible añadir más nodos sin que pierda la propiedad de ser clique.

&lt;center&gt;
![:scale 30%](./img/clique.png)
&lt;/center&gt;

---

## Distribución conjunta

* Para un clique `\(C\)` y conjunto de variables contenidas en él, `\(x_C\)`, tenemos que

`\begin{equation}
p(x) = \frac{1}{Z} \prod_{C}  \Psi_C(x_C),\qquad Z = \sum_x \prod_{C}  \Psi_C(x_C)
\end{equation}`

* Hay que tomar

`\begin{equation}
\Psi_C(x_C) = \exp \lbrace - E(x_C) \rbrace
\end{equation}`

* donde `\(E(x)\)` es la llamada **función de energía**.

* Con `\(M\)` variables que tomen `\(K\)` valores, la complejidad puede ser `\(\mathcal{O}(K^M)\)`.

---

## De dirigido a no dirigido

* Para pasar de un grafo dirigido a uno no dirigido, basta añadir nuevos enlaces entre todos los pares de parientes de cualquier nodo.

* Este proceso se conoce como **moralización**, y el grafo resultante, **grafo moral**.

&lt;center&gt;
![:scale 70%](./img/moral.png)
&lt;/center&gt;

* Ir de una representación en grafo dirigido a uno no dirigido descarta algunas propiedades de independencia condicional del grafo.


---

class: middle, center, inverse

# Inferencia Exacta en Modelos Gráficos

---

## Resumen

* **Inferencia**: algunos de los nodos del modelo estarán fijados a ciertos valores conocidos (observados), y deseamos calcular la distribución posterior sobre (subconjuntos de) el resto de nodos (no observados).

* Aprovecharemos la estructura gráfica del modelo para desarrollar algoritmos que eviten la explosión exponencial del número de configuraciones posibles del modelo.

* Caso más sencillo: supongamos que `\(p(x, y) = p(y|x)p(x)\)`, con el Teorema de Bayes

`\begin{equation}
p(x|y) = \frac{p(y|x)p(x)}{p(y)}
\end{equation}`

* Ahora el modelo se interpreta como `\(p(y)p(x|y)\)`. Ejemplo: MoG.

&lt;center&gt;
![:scale 50%](./img/inf1.png)
&lt;/center&gt;


---

## Inferencia en una cadena

* Consideremos una cadena de nodos


`\begin{equation}
p(x) = \frac{1}{Z} \psi_{1,2}(x_1, x_2)  \psi_{2,3}(x_2, x_3) \cdots \psi_{N-1,N}(x_{N-1}, x_N)
\end{equation}`

* Echemos cuentas: supongamos que cada nodo es una VA discreta ($K$ clases), y cada potencial viene especificado como una tabla de tamaño `\(K \times K\)`: la conjunta tiene `\((N-1)K^2\)` parámetros.

* Queremos obtener la **distribución marginal sobre `\(x_n\)`** (sumando todos los demás nodos):

`\begin{equation}
p(x_n) = \sum_{x_1} \sum_{x_2} \cdots \sum_{x_{n-1}}  \sum_{x_{n+1}} \cdots  \sum_{x_{N}} p(x)
\end{equation}`

* La complejidad es `\(\mathcal{O}(K^N)\)` !! Es **intratable** para `\(N\)` moderados.


---

## Inferencia en una cadena (2)

* ¿Podemos hacerlo mejor? La clave consiste en utilizar la propiedad distributiva

`\begin{equation}
ab + ac = a(b+c)
\end{equation}`

* Podemos obtener ecuaciones recursivas para **transmitir mensajes**

`\begin{align}
p(x_n) &amp;= \frac{1}{Z} \left[  \sum_{x_{n-1}} \psi_{n-1,n}(x_{n-1}, x_n) \cdots \left[ \sum_{x_1} \psi_{x_1, x_2} (x_1, x_2) \right] \cdots \right] \\
&amp;\left[  \sum_{x_{n+1}} \psi_{n,n+1}(x_{n}, x_{n+1}) \cdots \left[  \sum_{x_{N}} \psi_{N-1,N}(x_{N-1}, x_N) \right] \cdots \right]
\end{align}`

* Esto es,

`\begin{align}
p(x_n) = \frac{1}{Z} \mu_{\alpha}(x_n) \mu_{\beta}(x_n)
\end{align}`

&lt;center&gt;
![:scale 70%](./img/chain.png)
&lt;/center&gt;

---

## Inferencia en una cadena (3)


`\begin{align}
p(x) &amp;= \left[  \frac{1}{Z} \sum_{x_{n-1}} \psi_{n-1,n}(x_{n-1}, x_n) \cdots \left[ \sum_{x_1} \psi_{x_1, x_2} (x_1, x_2) \right] \cdots \right] \\
&amp;\left[  \sum_{x_{n+1}} \psi_{n,n+1}(x_{n}, x_{n+1}) \cdots \left[  \sum_{x_{N}} \psi_{N-1,N}(x_{N-1}, x_N) \right] \cdots \right]
\end{align}`

* Ahora, el coste computacional es el de `\(N-1\)` sumas, sobre variables con `\(K\)` categorías.

* Cada suma local es la de una tabla de tamaño `\(K \times K\)`.

* Por tanto, la nueva complejidad es `\(\mathcal{O}(NK^2)\)`, esto es, lineal en `\(N\)` !!

--

* Si el grafo fuera completo (todos los nodos tienen arcos a todos los restantes) no hubiéramos podido hacer lo anterior: volvemos al coste exponencial.


---

## Paso de mensajes (1)

&lt;center&gt;
![:scale 70%](./img/chain.png)
&lt;/center&gt;

* Intepretación más común: paso de mensajes entre los nodos del grafo.

* La marginal se descompone en un producto de dos factores y la constante de normalización:

`\begin{equation}
p(x_n) = \frac{1}{Z} \mu_{\alpha}(x_n) \mu_{\beta}(x_n)\qquad Z = \sum_{x_n}  \mu_{\alpha}(x_n) \mu_{\beta}(x_n)
\end{equation}`

* `\(\mu_\alpha(x_n)\)` es un mensaje propagado hacia adelante en la cadena desde `\(x_{n-1}\)` hasta `\(x_n\)`.

* `\(\mu_\beta(x_n)\)` es un mensaje propagado hacia atrás en la cadena desde `\(x_{n+1}\)` hasta `\(x_n\)`.

* Cada mensaje contiene un conjunto de `\(K\)` valores (uno para cada elección de `\(x_n\)`), por lo que el producto de dos mensajes representa una multiplicación componente a componente de los correspondientes elementos.

---

## Paso de mensajes (2)

* El mensaje hacia adelante puede ser evaluado recursivamente

`\begin{equation}
\mu_\alpha(x_n) = \sum_{x_{n-1}} \psi_{x_{n-1}, x_n} (x_{n-1}, x_n) \left[ \sum_{x_{n-2}} \ldots \right] =\sum_{x_{n-1}} \psi_{x_{n-1}, x_n} (x_{n-1}, x_n)  \mu_\alpha(x_{n-1}) 
\end{equation}`

* Por tanto, primero evaluamos

`\begin{equation}
\mu_\alpha(x_2) = \sum_{x_1} \psi_{1,2}(x_1, x_2)
\end{equation}`

* El mensaje saliente se obtiene multiplicando el mensaje entrante por el potencial local y sumando en la variable del nodo.

* Los mensajes hacia atrás también tienen la misma estructura recursiva.

* Este tipo de grafos se denominan **cadenas de Markov** y las ecuaciones de paso de mensajes correspondientes son un ejemplo de las **ecuaciones de Chapman-Kolmogorov** para procesos de Markov.

---

## Inferencia en una cadena

* Para calcular distribuciones marginales:

  * Calcular y guardar todos los mensajes hacia adelante `\(\mu_\alpha(x_n)\)`.
  * Calcular y guardar todos los mensajes hacia atrás `\(\mu_\beta(x_n)\)`.
  * Calcular la constante de normalización `\(Z\)`.
  * Calcular `\(p(x_n) = \frac{1}{Z} \mu_{\alpha}(x_n) \mu_{\beta}(x_n)\)`.
  
* **Ejercicio**: la marginal para pares de nodos adyacentes es

`\begin{equation}
p(x_{n-1}, x_n) = \frac{1}{Z} \mu_{\alpha}(x_{n-1}) \psi_{n-1,n}(x_{n-1},x_n) \mu_{\beta}(x_n)
\end{equation}`

* Componentes básicas para hacer inferencia en sistemas dinámicos lineales y modelos ocultos de Markov (HMM).


---

## Inferencia en árboles

* El esquema propuesto de paso de mensajes generaliza fácilmente a cualquier grafo **individualmente conectado** (singly connected): a lo sumo un único camino entre cualquier par de nodos.

* Cada nodo envía por cada enlace el producto de los mensajes que ha recibido desde los otros enlaces.

* Ejemplo: árbol no dirigido, árbol dirigido y poliárbol.

&lt;center&gt;
![:scale 100%](./img/trees.png)
&lt;/center&gt;

---

## Grafos de factores

* También representamos los **factores como nodos especiales**.

* Ejemplo: `\(p(x) = f_a(x_1, x_2) f_b(x_1, x_2) f_c(x_2, x_3) f_d(x_3)\)`


&lt;center&gt;
![:scale 50%](./img/fg.png)
&lt;/center&gt;

* En general, `\(p(x) = \prod_s f_s (X_s)\)`.

* Cada potencial tiene su propio nodo de factor, conectado a todos los términos del potencial.

* Los grafos de factores son **bipartitos**: podemos dividir entre nodos de variables y nodos de factores `\(\rightarrow\)` estructura para implementar paso de mensajes genérico.

---

## Grafos de factores para modelos no dirigidos

* Un grafo no dirigido puede ser convertido a un grafo de factores.

* Además, factorizaciones adicionales son posibles de representar(los **grafos de factores son más expresivos**)

&lt;center&gt;
![:scale 90%](./img/fg_undir.png)
&lt;/center&gt;


---

## Grafos de factores para modelos dirigidos

* Los grafos dirigidos son un caso especial en que los factores representan **distribuciones locales condicionadas**.

* Un modelo individualmente conectado generará un grafo de factores individualmente conectado: preserva la sencillez de la inferencia en estos casos (esto no ocurre si pasamos de dirigidos a no dirigidos).

&lt;center&gt;
![:scale 90%](./img/fg_dir.png)
&lt;/center&gt;


---

class: middle, center, inverse

# Algoritmo suma-producto

---

## Introducción

* Usando el marco de grafos de factores, derivaremos un algoritmo eficiente de **inferencia exacta** aplicable a grafos con estructura de árbol.

* Nos centraremos en evaluar marginales locales sobre nodos o conjuntos de nodos.

* Por sencillez, supondremos que todas las variables son discretas (la extensión a caso contínuo es trivial).

* Asumiremos que el grafo original es un **árbol no dirigido**, un **árbol dirigido** o un **poli-árbol**.

* En estos casos, el grafo de factores tiene estructura de árbol.

---
## Objetivos

* Primero de todo convertimos el grafo original en un grafo de factores.

* El objetivo es explotar la estructura del grafo para:

  1. Obtener un algoritmo eficiente de inferencia exacta para encontrar las marginales.
  
  2. En el caso de computar muchas marrginales, *compartir* los cálculos de manera eficiente.
  
---
## Algoritmo suma-producto (1)

* Empezamos por encontrar `\(p(x)\)` para un nodo en concreto.

`\begin{equation}
p(x) = \sum_{\textbf{x} / x} p(\textbf{x} ) = \sum_{\textbf{x} / x} \prod_{s} f_s(x_s)
\end{equation}`

* La estructura de árbol permite dividir los factores en la distribución conjunta en grupos, cada uno asociado con un factor vecino de `\(x\)`.

---
## Algoritmo suma-producto (2)

* Llamamos a `\(\text{ne}(x)\)` al conjunto de nodos factor vecinos de `\(x\)`.

* `\(X_s\)`: todas las variables **en el subárbol** conectado a `\(x\)` via un nodo factor `\(f_s\)`.

* `\(F_s(x, X_s)\)` el producto de **todos los factores** del grupo asociado a `\(f_s\)`.

* Entonces:

`\begin{equation}
p(\textbf{x} ) = \prod_{s \in \text{ne}(x) } F_s(x, X_s)
\end{equation}`

&lt;center&gt;
![:scale 40%](./img/sp1.png)
&lt;/center&gt;

---
## Algoritmo suma-producto (3)

* Sustituyendo, cambiando orden suma producto y definiendo **mensajes** entre `\(f_s\)` y x

`\begin{equation}
p(x) = \prod_{s \in \text{ne}(x) } \left[ \sum_{X_s} F_s(x, X_s) \right] := \prod_{s \in \text{ne}(x) } \mu_{f_s \rightarrow x} (x)
\end{equation}`

* Necesitamos evaluar los mensajes. Vemos que cada factor `\(F_s(x, X_s)\)` es a su vez un grafo de factores y puede ser factorizado.

---
## Algoritmo suma-producto (4)

* Denotamos las variables asociadas a `\(f_s\)` (a parte de `\(x\)`) como `\(x_1, \dots, x_M\)`.

`\begin{equation}
F_s(x, X_s) = f_s(x, x_1, \dots, x_M) G_1(x_1, X_{s1}) \dots G_M(x_M, X_{sM})
\end{equation}`

&lt;center&gt;
![:scale 40%](./img/sp2.png)
&lt;/center&gt;

---
## Algoritmo suma-producto (5)

* Substituyendo y llamando `\(\text{ne}(f_s)\)` al conjunto de nodos variable vecinos de `\(f_s\)`.

`\begin{eqnarray}
\mu_{f_s \rightarrow x} (x) &amp;=&amp; \sum_{X_s} F_s(x, X_s) \\
&amp;=&amp; \sum_{x1,\dots,x_M} f_s(x, x_1, \dots, x_M) \prod_{m \in \text{ne}(f_s) / x} \left[ \sum_{X_{sm}} G_{m} (x_m, X_{sm})\right] \\
&amp;=&amp; \sum_{x1,\dots,x_M} f_s(x, x_1, \dots, x_M) \prod_{m \in \text{ne}(f_s) / x} \left[\mu_{x_m \rightarrow f_s} (x_m) \right]
\end{eqnarray}`
 
* Existen dos tipos de mensajes: variable-factor y factor-variable.

* Evaluar mensaje de nodo factor a nodo variable requiere evaluar el **producto de mensajes recibidos** por el nodo factor, **multiplicar factor asociado** a este nodo y **marginalizar en variables asociadas a mensajes recibidos**.

---
## Algoritmo suma-producto (6)

* Para cerrar círculo, evaluamos los mensajes variable-factor.

&lt;center&gt;
![:scale 40%](./img/sp3.png)
&lt;/center&gt;

* Vemos que `\(G_m(x_m, X_{sm})\)` admite la factorización

`\begin{equation}
\prod_{l \in \text{ne}(x_m)/f_s } F_l(x_m, X_{ml}) 
\end{equation}`

---
## Algoritmo suma-producto (6)

* Con esto

`\begin{eqnarray}
\mu_{x_m \rightarrow f_s} (x_m) &amp;=&amp; \prod_{l \in \text{ne}(x_m)/f_s } \left[ \sum_{X_{ml}} F_l (x_m, X_{ml})\right] \\
&amp;=&amp; \prod_{l \in \text{ne}(x_m)/f_s } \mu_{f_l \rightarrow x_m} (x_m)
\end{eqnarray}`

* Para evaluar mensajes mandados por variable nodo a variable factor, calcular producto de todos los mensajes que llegan a la variable nodo.

---
## Algoritmo suma-producto (7)

* Cada mensaje puede ser calculado recursivamente en términos de otros mensajes.

* ¿Cómo empezar la recursión?

* Vemos `\(x\)` como el nodo raíz, y nos vamos a loas nodos hoja.


&lt;center&gt;
![:scale 70%](./img/sp4.png)
&lt;/center&gt;


---
## Algoritmo suma-producto (8)

* Para calcular todas las marginales de forma eficiente:
  
  1. Escoger nodo arbitrario como raíz.
  
  2. Calcular y propagar mensajes de las hojas hasta la raíz, guardando todos los mensajes recibidos en cada nodo.
  
  3. Calcular y propagar mensajes de la raíz hasta las hojas, guardando todos los mensajes recibidos en cada nodo.
  
  4. Calcular el producto de mensajes recibidos en cada nodo y normalizar si es necesario.
  
---
## Algoritmo suma-producto (9)

* **Ejercicio** :  Demostrar que las marginales sobre variables asociadas a un factor se pueden escribir como

`\begin{equation}
p(\boldsymbol{x_s}) = f_s(\boldsymbol{x_s}) \prod_{m \in \text{ne}(f_s)} \mu_{x_m \rightarrow f_s} (x_m)
\end{equation}`

---
## Algoritmo suma-producto (10)

* Cuando hay variables observadas, particionamos `\(\textbf{x}\)` en variables observadas `\(\textbf{v}\)` y ocultas `\(\textbf{h}\)`.

* Sean `\(\boldsymbol{\hat{v}}\)` los valores observados. Redefinimos la conjunta como

`\begin{equation}
p(\boldsymbol{x}) \prod_i I(v_i, \hat{v}_i)
\end{equation}`

* Que no es más que la versión sin normalizar de `\(p(\boldsymbol{h} \vert \boldsymbol{v} = \boldsymbol{\hat{v}})\)`.

* Con el agoritmo suma-producto podemos calcular las versiones sin normalizar de

`\begin{equation}
p(h_i \vert \boldsymbol{v} = \boldsymbol{\hat{v}})
\end{equation}`

* Que es barato de normalizar.
---

class: middle, center, inverse

# Algoritmo max-suma

---

## Algoritmo max-suma (1)

* El algoritmo suma-producto nos permitía calcular marginales de forma eficiente.

* En muchas ocasiones, también nos interesará calcular una **configuración de variables `\(x\)` que maximice la probabilidad del modelo**.

* Solución: usaremos el algoritmo **max-suma**.

* Objetivo: encontrar un algoritmo eficiente para
  
  1. Calcular `\(x_{max}\)` tal que maximize `\(p(x)\)`.
  
  2. Calcular `\(p(x_{max})\)`.
  
--
  
* En general, **maximizar marginales `\(\neq\)` máximo conjunto**:

&lt;center&gt;
![:scale 50%](./img/max_sum1.png)
&lt;/center&gt;


---


## Algoritmo max-suma. Inferencia en cadena

Volvamos al caso de inferencia en una cadena...

* La clave vuelve a ser **intercambiar las operaciones**.

`\begin{align}
p(x_{max}) &amp;= \max_x p(x) = \max_{x_1} \ldots \max_{x_N} p(x) = \\
&amp;= \frac{1}{Z} \max_{x_1} \ldots \max_{x_N} \left[  \psi_{1,2} (x_1, x_2) \cdots \psi_{N-1,N} (x_{N-1}, x_N)  \right] = \\
&amp;= \frac{1}{Z} \max_{x_1} \left[  \max_{x_1} \left[  \psi_{1,2} (x_1, x_2) \left[ \cdots \max_{x_N} \psi_{N-1,N} (x_{N-1}, x_N)  \right] \right] \right]
\end{align}`

* Al igual que con las marginales, intercambiar los operadores max y producto resulta en un algoritmo mucho más eficiente, dejando de tener coste exponencial.

* Puede ser interpretado en términos de un **paso de mensajes** desde `\(x_N\)` hasta `\(x_1\)`.

---


## Algoritmo max-suma. Generalización a árboles

* Al igual que suma-producto, puede aplicarse en grafos de factores con estructura de árbol

`\begin{equation}
\max_x p(x) = \max_{x_n} \prod_{f_s \in ne(x_n)} \max_{X_s} f_s(x_n, X_s)
\end{equation}`

* Frente al original:


`\begin{equation}
p(x) =  \prod_{f_s \in ne(x)} \left[ \sum_{X_s} F_s(x, X_s)   \right]
\end{equation}`

* max-producto `\(\rightarrow\)` max-suma

  1. Por razones numéricas, es más estable trabajar en espacio logarítmico:
    \begin{equation}
    \log (\max_x p(x)) = \max_x \log p(x)
    \end{equation}
  2. Y usamos la propiedad distributiva para los intercambios de operadores:
  
    \begin{equation}
    \max \lbrace a+b, a+c \rbrace = a + \max \lbrace b, c \rbrace
    \end{equation}
---

## Algoritmo max-suma

* Ya es directo pasar del algoritmo suma-producto al max-suma: basta cambiar los operadores:

  * `\(+ \rightarrow \max\)`,
  * `\(\times \rightarrow +\)` (de logaritmos)
  
* **Inicialización** (los elementos neutros para ambos operadores):

  * `\(\mu_{f\rightarrow x}(x) = 0\)`
  * `\(\mu_{x\rightarrow f}(x) = \log f(x)\)`
  
* **Caso recursivo**:

`\begin{equation}
\mu_{f \rightarrow x} = \max_{x_1, \ldots, x_M} \left[ \log f(x, x_1, \ldots, x_M) + \sum_{m \in ne(f_s)\ x} \mu_{x_m \rightarrow f} (x_m) \right]
\end{equation}`

`\begin{equation}
\mu_{x\rightarrow f} (x) = \sum_{l \in ne(x) \ f} \mu_{f_l \rightarrow x} (x)
\end{equation}`


---

## Generalizaciones de suma-producto

* Consideramos un (semi-)anillo con dos operaciones:

  * `\(+,\times\)`: marginalización.
  * `\(\max, +\)`: MAP.
  * `\(\sim, +\)`: forward-filter, backward-sample (para obtener muestras del posterior).
  * ...
  
* Es lo que recientemente se ha denominado como **semiring dynamic programming**.

* Permite encontrar de forma natural algoritmos eficientes en más contextos aparte de PGMs.

* Por ejemplo: Belle, de Raedt, *Semiring Programming: A Framework for Search, Inference and Learning* (2016).

---


## Inferencia en grafos generales

* El algoritmo *junction tree* generaliza el marco visto a grafos arbitrarios (con ciclos), pero no es eficiente en general.

* Otra alternativa es usar métodos aproximados.

* *Loopy belief propagation* propone usar el algoritmo suma producto aunque haya ciclos.

* La información fluye indefinidamente por los ciclos. En algunos casos se converge (no garantizado!).
    </textarea>
<style data-target="print-only">@media screen {.remark-slide-container{display:block;}.remark-slide-scaler{box-shadow:none;}}</style>
<script src="https://remarkjs.com/downloads/remark-latest.min.js"></script>
<script src="macros.js"></script>
<script>var slideshow = remark.create({
"highlightStyle": "github",
"highlightLines": true,
"countIncrementalSlides": false
});
if (window.HTMLWidgets) slideshow.on('afterShowSlide', function (slide) {
  window.dispatchEvent(new Event('resize'));
});
(function(d) {
  var s = d.createElement("style"), r = d.querySelector(".remark-slide-scaler");
  if (!r) return;
  s.type = "text/css"; s.innerHTML = "@page {size: " + r.style.width + " " + r.style.height +"; }";
  d.head.appendChild(s);
})(document);

(function(d) {
  var el = d.getElementsByClassName("remark-slides-area");
  if (!el) return;
  var slide, slides = slideshow.getSlides(), els = el[0].children;
  for (var i = 1; i < slides.length; i++) {
    slide = slides[i];
    if (slide.properties.continued === "true" || slide.properties.count === "false") {
      els[i - 1].className += ' has-continuation';
    }
  }
  var s = d.createElement("style");
  s.type = "text/css"; s.innerHTML = "@media print { .has-continuation { display: none; } }";
  d.head.appendChild(s);
})(document);
// delete the temporary CSS (for displaying all slides initially) when the user
// starts to view slides
(function() {
  var deleted = false;
  slideshow.on('beforeShowSlide', function(slide) {
    if (deleted) return;
    var sheets = document.styleSheets, node;
    for (var i = 0; i < sheets.length; i++) {
      node = sheets[i].ownerNode;
      if (node.dataset["target"] !== "print-only") continue;
      node.parentNode.removeChild(node);
    }
    deleted = true;
  });
})();</script>

<script>
(function() {
  var links = document.getElementsByTagName('a');
  for (var i = 0; i < links.length; i++) {
    if (/^(https?:)?\/\//.test(links[i].getAttribute('href'))) {
      links[i].target = '_blank';
    }
  }
})();
</script>

<script>
slideshow._releaseMath = function(el) {
  var i, text, code, codes = el.getElementsByTagName('code');
  for (i = 0; i < codes.length;) {
    code = codes[i];
    if (code.parentNode.tagName !== 'PRE' && code.childElementCount === 0) {
      text = code.textContent;
      if (/^\\\((.|\s)+\\\)$/.test(text) || /^\\\[(.|\s)+\\\]$/.test(text) ||
          /^\$\$(.|\s)+\$\$$/.test(text) ||
          /^\\begin\{([^}]+)\}(.|\s)+\\end\{[^}]+\}$/.test(text)) {
        code.outerHTML = code.innerHTML;  // remove <code></code>
        continue;
      }
    }
    i++;
  }
};
slideshow._releaseMath(document);
</script>
<!-- dynamically load mathjax for compatibility with self-contained -->
<script>
(function () {
  var script = document.createElement('script');
  script.type = 'text/javascript';
  script.src  = 'https://mathjax.rstudio.com/latest/MathJax.js?config=TeX-MML-AM_CHTML';
  if (location.protocol !== 'file:' && /^https?:/.test(script.src))
    script.src  = script.src.replace(/^https?:/, '');
  document.getElementsByTagName('head')[0].appendChild(script);
})();
</script>
  </body>
</html>