Modelos Descriptivos y Predictivos II

Cheatsheet Content

5. Árboles de Decisión y Clasificación (ADC) Definición y utilidad Los Modelos Gráficos (MG) probabilísticos combinan la gestión de la incertidumbre (probabilidad) con la lógica estructural (restricciones de independencia) para representar fenómenos complejos del mundo real. Los árboles de clasificación (también llamados de decisión o de identificación) se enmarcan en la aproximación no paramétrica al Reconocimiento de Formas. Un árbol de clasificación es la estructura resultante de la partición recursiva del espacio de representación a partir de una muestra de aprendizaje. Cada nodo interno contiene una pregunta sobre un atributo concreto (con un hijo por cada posible respuesta) y cada nodo hoja o terminal contine una etiqueta de clase y corresponde a una decisión final (clasificación). Un dato de test se clasifica mediante una serie de preguntas sobre los valores de sus atributos, empezado por el nodo raiz y siguiendo el camino determinado por las respuestas a las preguntas de los nodos internos, hasta llegar a un nodo hoja. Notación Espacio de representación: $E = \mathbb{R}^D$; $\mathbf{y} = (y_1, y_2, ..., y_D)^t \in E$ Muestra de aprendizaje: $N$ vectores, con su correcta clasificación: $(\mathbf{y}_1, c_1), ..., (\mathbf{y}_N, c_N)$, $\mathbf{y}_i \in E, c_i \in \mathcal{C} = \{1, 2, ..., C\}$, $1 \le i \le N$ Un árbol se denota por $T$ ("Tree"), un nodo por $t$, sus hijos izquierdo y derecho por $t_L, t_R$, respectivamente y el conjunto de nodos-hoja o terminales por $\tilde{T}$ Una partición binaria (“split") se denota por $s$ y el conjunto de particiones admisibles por $\mathcal{S}$ Estimación de probabilidades asociadas a nodos $N$: número total de datos en la muestra. $N_c$: número de datos de la clase $c$. $N(t)$: número de datos representados en el nodo $t$. $N_c(t)$: número de datos de la clase $c$ en el nodo $t$. Probabilidad a priori de la clase $c$: $\hat{P}(c) = \frac{N_c}{N}$ Probabilidad a posteriori de clase $c$ en el nodo $t$: $\hat{P}(c|t) = \frac{N_c(t)}{N(t)}$ Probabilidad de un nodo terminal $t \in \tilde{T}$: $\hat{P}(t) = \frac{N(t)}{N}$ Probabilidad de decisión por el hijo izquierdo de $t$: $\hat{P}_t(L) = \frac{N(t_L)}{N(t)}$ Probabilidad de decisión por el hijo derecho de $t$: $\hat{P}_t(R) = \frac{N(t_R)}{N(t)}$ Construcción de un ADC Elementos necesarios: Método para hacer particiones y seleccionar la mejor: Condiciones o "preguntas" ("splits") admisibles: ¿$y_j \in B$?, $B \subset E$. Evaluación y optimización de la calidad de una partición (Decremento de impureza). Criterio para considerar un nodo "puro" (terminal). Criterio para asignar una etiqueta a un nodo terminal. Conjunto de preguntas admisibles (splits) Cada partición involucra a una única componente $j$ de $E$, $1 \le j \le D$. Las preguntas: ¿$y_j \le r$?. Un "split" es un par $s = (j,r)$. Los "splits" definen hiperplanos paralelos a los ejes de $E$, formando bloques (rectangulares en $E = \mathbb{R}^2$). Para un nodo $t$ con $N(t)$ elementos, se exploran $O(D N(t))$ "splits". Evaluación de la calidad de una partición La impureza de un nodo $t$, $I(t)$, se mide en función de las probabilidades estimadas de las clases en $t$. Entropía: $I(t) = - \sum_{c=1}^C \hat{P}(c|t) \log_2 \hat{P}(c|t) = - \sum_{c=1}^C \frac{N_c(t)}{N(t)} \log_2 \frac{N_c(t)}{N(t)}$ Decremento de impureza: $\Delta I(j,r,t) \stackrel{def}{=} I(t) - \hat{P}_t(L)I(t_L) - \hat{P}_t(R)I(t_R)$ La mejor partición $(j^*,r^*)$ maximiza el decremento de impureza: $(j^*,r^*) = \arg\max_{1 \le j \le D, -\infty Criterios de pureza en nodos terminales Un nodo $t$ es terminal si el máximo decremento de impureza posible es demasiado pequeño: $\max \Delta I(j,r,t) \le \epsilon$. Asignación de etiquetas a nodos terminales: $c^*(t) = \arg\max_{1 \le c \le C} \hat{P}(c|t)$ (clase mayoritaria). Complejidad del algoritmo ADC Temporal: $O(D N (\log N)^2)$. $D$: número de atributos (dimensiones del espacio). $N$: número de muestras en el conjunto de entrenamiento. $(\log N)^2$: proviene de la ordenación de las muestras para encontrar los mejores puntos de corte en cada atributo, y el número de niveles del árbol. En cada nodo, se itera sobre los $D$ atributos. Para cada atributo, se ordenan hasta $N$ valores para encontrar los puntos de corte, lo que lleva $O(N \log N)$. Si el árbol tiene profundidad $O(\log N)$ (balanceado), la complejidad total se acumula. Espacial: $O(N)$. El espacio requerido es proporcional al número de muestras $N$, ya que el algoritmo necesita almacenar la muestra de entrenamiento en cada nodo para realizar las particiones. En el peor caso, si el árbol no está balanceado o si cada nodo solo contiene una muestra, el espacio puede ser considerable. Estimación del error de clasificación (resustitución) Probabilidad de error de un nodo terminal $t$: $\hat{P}_t(\text{error}) = 1 - \max_{1 \le c \le C} \hat{P}(c|t)$ Para un árbol $T$: $P_T(\text{error}) = \sum_{t \in \tilde{T}} \hat{P}(t) \hat{P}_t(\text{error})$ El sobreaprendizaje ocurre si se hace crecer el árbol hasta que los nodos terminales sean totalmente puros, resultando en un error estimado nulo pero sin capacidad de generalización. 6. Máquinas de Vectores Soporte (SVM) y Núcleos Clasificación en dos clases con Funciones Discriminantes Lineales (FDL) Dado un conjunto de muestras linealmente separables (2-clases): $\mathcal{S} = \{(\mathbf{x}_1, c_1), ..., (\mathbf{x}_N, c_N)\}$, $\mathbf{x}_n \in \mathbb{R}^d$, $c_n \in \{+1, -1\}$, $1 \le n \le N$. FDL: $\phi(\mathbf{x}; \mathbf{\Theta}) = \mathbf{\theta}^t \mathbf{x} + \theta_0 = \sum_{i=1}^d \theta_i x_i + \theta_0$. $\mathbf{\Theta} = (\mathbf{\theta}, \theta_0)$ donde $\mathbf{\theta} \in \mathbb{R}^d$ es un vector de pesos y $\theta_0 \in \mathbb{R}$ es el umbral . Restricción FDL: $c_n (\mathbf{\theta}^t \mathbf{x}_n + \theta_0) \ge 0$, $1 \le n \le N$. Propiedades de las FDL Una FDL, $\phi(\mathbf{x}; \mathbf{\Theta})$, define un hiperplano de separación $\mathcal{H} = \{\mathbf{x} | \phi(\mathbf{x}; \mathbf{\Theta}) = 0\}$. $\mathcal{H}$ divide a $\mathbb{R}^d$ en dos semiespacios: $\phi(\mathbf{x}; \mathbf{\Theta}) > 0, c = +1$ y $\phi(\mathbf{x}; \mathbf{\Theta}) El vector de pesos, $\mathbf{\theta}$, es ortogonal a $\mathcal{H}$. Su vector unitario es $\frac{\mathbf{\theta}}{\|\mathbf{\theta}\|}$. La distancia de cualquier $\mathbf{x}_s$ a $\mathcal{H}$ es: $r_{\mathbf{x}_s} = \frac{|\phi(\mathbf{x}_s; \mathbf{\Theta})|}{\|\mathbf{\theta}\|}$. Hiperplano y margen de un Hiperplano separador El margen $\tau$ de un hiperplano $\mathcal{H}$ es la mínima distancia entre $\mathcal{H}$ y la muestra más cercana de cualquiera de las clases. Un hiperplano $\mathcal{H}$ es óptimo si su margen es máximo. Forma canónica respecto a un conjunto de puntos La distancia entre un Hiperplano $\mathcal{H}$ y una muestra $\mathbf{x}_n \in \mathcal{S}$ se define como: $\frac{|\phi(\mathbf{x}_n; \mathbf{\Theta})|}{\|\mathbf{\theta}\|} = \frac{|\mathbf{\theta}^t \mathbf{x}_n + \theta_0|}{\|\mathbf{\theta}\|}$. En forma canónica, se cumple: $c_n (\mathbf{\theta}^t \mathbf{x}_n + \theta_0) \ge 1$. Los vectores soporte $\mathcal{V}$ son las muestras de la frontera que delimitan el margen, y cumplen: $\frac{|\phi(\mathbf{x}_i; \mathbf{\Theta})|}{\|\mathbf{\theta}\|} = \tau = \frac{1}{\|\mathbf{\theta}\|}$. El margen respecto a $\mathcal{H}$ es: $2\tau = \frac{2}{\|\mathbf{\theta}\|}$. Clasificadores de margen máximo (muestras separables: SVM) Objetivo: obtener el hiperplano $\mathcal{H}$ óptimo, definido por $\mathbf{\theta} \in \mathbb{R}^d$ y $\theta_0 \in \mathbb{R}$, que maximice el margen $\frac{2}{\|\mathbf{\theta}\|}$. Problema de optimización: Maximizar $\frac{2}{\|\mathbf{\theta}\|}$ (o minimizar $\frac{1}{2}\mathbf{\theta}^t \mathbf{\theta}$). Sujeto a: $c_n (\mathbf{\theta}^t \mathbf{x}_n + \theta_0) \ge 1$, $1 \le n \le N$. Aplicación de la técnica de los multiplicadores de Lagrange Lagrangiana: $\Lambda(\mathbf{\theta}, \theta_0, \mathbf{\alpha}) = \frac{1}{2}\mathbf{\theta}^t \mathbf{\theta} - \sum_{n=1}^N \alpha_n [c_n (\mathbf{\theta}^t \mathbf{x}_n + \theta_0) - 1]$. $\alpha_n \ge 0$ son los multiplicadores de Lagrange . Minimizar $\Lambda(\mathbf{\theta}, \theta_0, \mathbf{\alpha})$ para $\mathbf{\theta}, \theta_0$. Dual: Maximizar $A_D(\mathbf{\alpha}) = \sum_{n=1}^N \alpha_n - \frac{1}{2} \sum_{n=1}^N \sum_{m=1}^N c_n c_m \alpha_n \alpha_m \mathbf{x}_n^t \mathbf{x}_m$. Sujeto a: $\sum_{n=1}^N \alpha_n c_n = 0$, $\alpha_n \ge 0$, $1 \le n \le N$. Resumen de propiedades de los clasificadores de margen máximo Las soluciones $\mathbf{\theta}^*, \theta_0^*, \mathbf{\alpha}^*$ verifican: $\mathbf{\theta}^* = \sum_{n=1}^N c_n \alpha_n^* \mathbf{x}_n$. $\sum_{n=1}^N \alpha_n^* c_n = 0$. $\alpha_n^* \ge 0$, $1 \le n \le N$. Condición KKT: $\alpha_n^* [c_n (\mathbf{\theta}^{*t} \mathbf{x}_n + \theta_0^*) - 1] = 0$, $1 \le n \le N$. Esto implica: $\alpha_n^* = 0$ o bien $\alpha_n^* \ne 0, c_n (\mathbf{\theta}^{*t} \mathbf{x}_n + \theta_0^*) = 1$. Vectores soporte Los vectores soporte son las muestras de entrenamiento $\mathbf{x}_n$ para las que $\alpha_n^* \ne 0$. Todos los vectores soporte equidistan del hiperplano separador: $r_{\mathbf{x}_n} = \frac{|\mathbf{\theta}^{*t} \mathbf{x}_n + \theta_0^*|}{\|\mathbf{\theta}^*\|} = \frac{1}{\|\mathbf{\theta}^*\|}$. Las propiedades implican que hay al menos un vector soporte de cada clase. La función discriminante lineal que maximiza el margen es: $\phi_{SVM}(\mathbf{x}; \mathbf{\alpha}^*, \mathcal{S}) = \sum_{n \in \mathcal{V}} c_n \alpha_n^* \mathbf{x}_n^t \mathbf{x} + \theta_0^*$. Clasificadores de margen máximo (muestras no-separables: "márgenes blandos") Una muestra $\mathcal{S}$ es no-separable linealmente si no cumple: $c_n (\mathbf{\theta}^t \mathbf{x}_n + \theta_0) \ge 1$. Se introducen variables de holgura $\xi_n \in \mathbb{R}^+$, que cuantifican la desviación del caso separable. Problema de optimización: Minimizar $\frac{1}{2}\mathbf{\theta}^t \mathbf{\theta} + C \sum_{n=1}^N \xi_n$. ($C$ es parámetro de regularización). Sujeto a: $c_n (\mathbf{\theta}^t \mathbf{x}_n + \theta_0) \ge 1 - \xi_n$, $\xi_n \ge 0$, $1 \le n \le N$. Lagrangiana dual: Maximizar $A_D(\mathbf{\alpha}, \mathbf{\beta}) = \sum_{n=1}^N \alpha_n - \frac{1}{2} \sum_{n=1}^N \sum_{m=1}^N c_n c_m \alpha_n \alpha_m \mathbf{x}_n^t \mathbf{x}_m$. Sujeto a: $\sum_{n=1}^N \alpha_n c_n = 0$, $0 \le \alpha_n \le C$, $1 \le n \le N$. Condición KKT: $\alpha_n^* [c_n (\mathbf{\theta}^{*t} \mathbf{x}_n + \theta_0^*) - 1 + \xi_n^*] = 0$ y $\beta_n^* \xi_n^* = 0$. Vectores soporte "erróneos": Si $\xi_n^* = 0$: no hay error de margen. Si $\alpha_n^* = 0$: muestra separable y bien clasificada. Si $\alpha_n^* \ne 0$: $\mathbf{x}_n$ son vectores soporte. Si $\xi_n^* > 0$: hay error de margen. $\xi_n^* > 1$: mal clasificadas. $0 Cuando $\alpha_n^* = C$, $\mathbf{x}_n$ se denominan vectores soporte ligados . Métodos de optimización para SVM Solución analítica: para $N$ pequeños (generalmente $N \le 3$). Ascenso por gradiente: en general. Algoritmos de descomposición: para $N \le 5000$. Optimización minimal secuencial (SMO): para $N \gg 5000$. Generalización de SVM: Núcleos Se aprovecha que una SVM se puede expresar en base a productos escalares. Se introduce una función de transformación no lineal $\psi: \mathbb{R}^d \to \mathbb{R}^{d'}$ (típicamente $d' \gg d$). Se obtiene un hiperplano separador lineal en este nuevo espacio. Función de transformación: $\phi_\psi(\mathbf{x}) = \sum_{n=1}^N \alpha_n c_n \psi(\mathbf{x}_n)^t \psi(\mathbf{x}) + \theta_0$. Kernel: $\phi_K(\mathbf{x}) = \sum_{n=1}^N \alpha_n c_n K(\mathbf{x}_n, \mathbf{x}) + \theta_0$. Un núcleo $K: \mathbb{R}^d \times \mathbb{R}^d \to \mathbb{R}$ es una función si $\exists \psi: \mathbb{R}^d \to \mathbb{R}^{d'}$ tal que $K(\mathbf{x}, \mathbf{x}') = \psi(\mathbf{x})^t \psi(\mathbf{x}')$. $\mathbb{R}^{d'}$ se llama espacio de características . Construcción de núcleos No es necesario construir $\psi(\mathbf{x})$, basta con definir una función $K$ que sea: Simétrica: $K(\mathbf{x}, \mathbf{x}') = K(\mathbf{x}', \mathbf{x})$. Semidefinida positiva (Condición de Mercer): $\sum_{n=1}^N \sum_{m=1}^N c_n c_m K(\mathbf{x}_n, \mathbf{x}_m) \ge 0$. Ejemplos de funciones kernel Kernel Lineal: $K_L(\mathbf{x}, \mathbf{x}') = \mathbf{x}^t \mathbf{x}'$. Kernel polinómico de grado $p$: $K_P(\mathbf{x}, \mathbf{x}') = [\gamma \mathbf{x}^t \mathbf{x}' + \tau]^p$. Kernel gaussiano: $K_G(\mathbf{x}, \mathbf{x}') = \exp(-\gamma \|\mathbf{x} - \mathbf{x}'\|^2)$. Kernel de base radial (RBK): $K_{RBK}(\mathbf{x}, \mathbf{x}') = f(r)$; $r = \|\mathbf{x} - \mathbf{x}'\|$. SVM para problemas de $C$ clases Las SVM no generalizan bien de forma natural para más de dos clases. Estrategias: Uno-contra-uno (one-versus-one): Clasificación por votación: $f(\mathbf{x}) = \arg\max_{c} \sum_{c' \ne c} f_{cc'}(\mathbf{x})$. Clasificación utilizando DAG (Directed Acyclic Graphs). Uno-contra-resto (one-versus-all): Se entrenan $C$ clasificadores binarios, uno para cada clase contra el resto. $\phi_{c\#}(\mathbf{x}) = \sum_{\mathbf{x}_n \in \mathcal{V}_{c\#}} \alpha_{nc\#}^* c_{nc\#} K(\mathbf{x}_n, \mathbf{x}) + \theta_{c\#}^*$. Otras técnicas multiclase para SVM: $SVM^{multiC}$: Optimización directa de márgenes. Construcción de Kesler: Transformación de un problema de $C$ clases en otro de 2. 7. Predicción Estructurada: Modelos Ocultos de Markov (HMM) Predicción no-estructurada Observación de entrada: $\mathbf{x} \in \mathcal{X}$ (cualquier clase de objeto). Interpretación de salida: $y \in \mathcal{Y}$ (escalar, $\{1,...,K\}$, o $\mathbb{R}$). Función de predicción (no-estructurada): $f: \mathcal{X} \to \mathbb{R}$, asigna $y = f(\mathbf{x})$ a $\mathbf{x}$. Predicción estructurada Observación de entrada: $\mathbf{x} \in \mathcal{X}$ (cualquier clase de objeto). Interpretación de salida: $y \in \mathcal{Y}$ (objeto estructurado complejo: secuencia, árbol, grafo). Función de predicción estructurada: $f: \mathcal{X} \to \mathcal{Y}$, asigna $y = f(\mathbf{x})$ a $\mathbf{x}$. Si $\mathcal{Y}$ es potencialmente infinito, $f(\mathbf{x}) = y \in \mathcal{Y}$ será intratable. Predicción estructurada: incertidumbre Fragilidad: falta de robustez por representación imperfecta de objetos (incertidumbre en la entrada). Ambigüedad: varias interpretaciones posibles (incertidumbre en la salida). Incompletitud: modelos inadecuados por conocimientos incompletos. Solución: Basada en la Teoría de la decisión estadística. Se busca $f: \mathcal{X} \to L(G)$. $\hat{y} = f(\mathbf{x}) = \arg\max_{y \in L(G)} P(y|\mathbf{x}; G_\theta)$, donde $G_\theta$ es el modelo probabilístico. Lenguaje Probabilístico Un Lenguaje $L \subseteq \Sigma^*$. Un Lenguaje generado por una gramática $L(G) = \{\mathbf{x} | \mathbf{x} \in \Sigma^*: S \stackrel{*}{\Rightarrow} \mathbf{x}\}$. Un Lenguaje probabilístico $(L, \phi)$ con alfabeto $\Sigma$ y función probabilística computable $\phi: \Sigma^* \to [0,1]$ tal que: Si $\mathbf{x} \notin L$, entonces $\phi(\mathbf{x}) = 0$. Si $\mathbf{x} \in L$, entonces $0 $\sum_{\mathbf{x} \in L} \phi(\mathbf{x}) = 1$. Gramáticas regulares probabilísticas Una Gramática Regular Probabilística $G_p = (G, P)$, donde $G = (N, \Sigma, \mathcal{P}, S)$ es una gramática regular, y $P: \mathcal{P} \to ]0,1]$ asigna probabilidades a las reglas. Las probabilidades de las reglas para un no-terminal $A \in N$ deben sumar 1: $\sum_{i=1}^{n_A} P(A \to \alpha_i) = 1$. Derivación probabilística: La probabilidad de que $\mathbf{x}$ sea generada por $G_\theta$ a partir de la secuencia de reglas $t_\mathbf{x} = r_1 ... r_m$ es: $P_\theta(\mathbf{x}, t_\mathbf{x}) = P_\theta(r_1) \cdot P_\theta(r_2|r_1) \cdot ... \cdot P_\theta(r_m|r_1...r_{m-1})$. Restricción: $P_\theta(r_i|r_1...r_{i-1}) = P_\theta(r_i)$. Probabilidad de un árbol de análisis: $P_\theta(\mathbf{x}, t_\mathbf{x}) = \prod_{j=1...m} P(r_j)$. Probabilidad de una cadena: $P_\theta(\mathbf{x}) = \sum_{t_\mathbf{x} \in T_\mathbf{x}} P_\theta(\mathbf{x}, t_\mathbf{x})$. Probabilidad del mejor árbol de análisis: $\hat{P}_\theta(\mathbf{x}) = \max_{t_\mathbf{x} \in T_\mathbf{x}} P_\theta(\mathbf{x}, t_\mathbf{x})$. Lenguaje generado: $L(G_\theta) = \{\mathbf{x} \in L(G) | P_\theta(\mathbf{x}) > 0\}$. Modelo Oculto de Markov (HMM) Un HMM es una quíntupla $M = (\Sigma, Q, F, \mathbf{\pi}, A, B)$ donde: $\Sigma$: alfabeto (símbolos "observables"). $Q$: conjunto de estados. $F \subseteq Q$: conjunto de estados finales. $\mathbf{\pi}$: vector de probabilidades iniciales. $\pi_q = P(q_1 = q)$. $A$: matriz de probabilidades de transición. $A_{q,q'} = P(q_{t+1} = q' | q_t = q)$. $B$: matriz de probabilidades de emisión. $B_{q,\sigma} = P(x_t = \sigma | q_t = q)$. Condiciones de normalización: $0 \le \pi_q \le 1$, $\sum_{q \in Q} \pi_q = 1$, $\pi_F = 0$. $0 \le A_{q,q'} \le 1$, $\sum_{q' \in Q} A_{q,q'} = 1$, $A_{F,q} = 0$. $0 \le B_{q,\sigma} \le 1$, $\sum_{\sigma \in \Sigma} B_{q,\sigma} = 1$, $B_{F,\sigma} = 0$. HMM: probabilidad de una cadena La probabilidad de que $M$ produzca $\mathbf{x}$ mediante $\mathbf{y}$ es: $P(\mathbf{x}, \mathbf{y}) = P(q_1) P(x_1|q_1) ... P(q_T|q_{T-1}) P(x_T|q_T) P(q_f|q_T)$. La probabilidad de que $M$ genere la cadena $\mathbf{x} = x_1...x_T \in \Sigma^+$ es: $P(\mathbf{x}; M) = \sum_{\mathbf{y} \in Q^+} P(\mathbf{x}, \mathbf{y})$. Se cumple: $0 \le P(\mathbf{x}; M) \le 1$, $\sum_{\mathbf{x} \in \Sigma^+} P(\mathbf{x}; M) = 1$. Algoritmo Forward $\alpha(q, t)$: probabilidad de que $M$ genere el prefijo $x_1...x_t$ y alcance el estado $q$ en el instante $t$. Inicialización: $\alpha(q, 1) = \pi_q B_{q,x_1}$ para $t=1$. Recursión: $\alpha(q, t) = \sum_{q' \in Q} \alpha(q', t-1) A_{q',q} B_{q,x_t}$ para $t > 1$. La probabilidad de la cadena es: $P(\mathbf{x}; M) = \sum_{q \in Q} \alpha(q, T) A_{q,F}$. La función $\alpha()$ puede representarse como una matriz $\alpha_{q,t} = \alpha(q,t)$. Esta matriz define un grafo multi-etapa llamado trellis . Complejidad temporal: $O(T b)$, donde $T$ es la longitud de la cadena y $b$ es el número de transiciones entre estados. Algoritmo de Viterbi $\gamma(q, t)$: probabilidad máxima de que $M$ genere el prefijo $x_1...x_t$ y alcance el estado $q$ en el instante $t$. Inicialización: $\gamma(q, 1) = \pi_q B_{q,x_1}$ para $t=1$. Recursión: $\gamma(q, t) = \max_{q' \in Q} \{\gamma(q', t-1) A_{q',q} B_{q,x_t}\}$ para $t > 1$. La probabilidad de la mejor interpretación de la cadena es: $\hat{P}(\mathbf{x}; M) = \max_{q \in Q} \gamma(q, T) A_{q,F}$. La secuencia óptima de estados, $\hat{\mathbf{y}}$, se obtiene recorriendo el trellis hacia atrás. Complejidad temporal: $O(T b)$. Estimación de modelos de Markov Dado un corpus de entrenamiento $\Omega = \{\mathbf{x}_1, ..., \mathbf{x}_N\}$, la función objetivo es: $P(\Omega; M_\theta) = \prod_{k=1}^N P(\mathbf{x}_k; M_\theta)$. El problema de aprender $\theta$ se formula mediante un estimador de máxima probabilidad : $\hat{\theta} = \arg\max_{\theta} P(\Omega; M_\theta)$. $P(\Omega; M_\theta)$ es continua y derivable, y para su optimización se usa el Algoritmo de Baum-Welch (o Forward-Backward) . Si $P(\Omega; M_\theta)$ no es derivable, se define una nueva función objetivo: $P(\Omega, \hat{Y}_\Omega; M_\theta) = \prod_{k=1}^N P(\mathbf{x}_k, \hat{\mathbf{y}}_{\mathbf{x}_k}; M_\theta)$, donde $\hat{\mathbf{y}}$ es la secuencia óptima de estados para $\mathbf{x}$. Para esta optimización se emplea el Algoritmo de estimación por Viterbi . Estimación mediante el algoritmo de Viterbi Analizar todas las cadenas de $\Omega$, contabilizando estados iniciales, frecuencias de transiciones y generación de símbolos. Normalizar. Inicializar las probabilidades "adecuadamente". Analizar cada cadena de $\Omega$ con el algoritmo de Viterbi para obtener la secuencia de estados. Contabilizar las frecuencias requeridas. Normalizar las frecuencias para obtener nuevas probabilidades. Repetir pasos 2-4 hasta convergencia. Algoritmo de reestimación por Viterbi: $\hat{\pi}_q = P(q|\#) = \frac{N(\hat{\pi}_q, \hat{\mathbf{y}})}{N(\hat{\mathbf{\pi}}, \hat{\mathbf{y}})}$. $\hat{A}_{q,q'} = P(q'|q) = \frac{N(\hat{A}_{q,q'}, \hat{\mathbf{y}})}{N(\hat{A}_q, \hat{\mathbf{y}})}$. $\hat{B}_{q,\sigma} = P(\sigma|q) = \frac{N(\hat{B}_{q,\sigma}, \hat{\mathbf{y}})}{N(\hat{B}_q, \hat{\mathbf{y}})}$. 8. Modelos Gráficos Modelos Gráficos: Introducción Los Modelos Gráficos (MG) probabilísticos son un marco formal que combina la gestión de la incertidumbre (probabilidad) con la lógica estructural (restricciones de independencia) para representar fenómenos complejos. Utilidad: Base formal para aproximación probabilística a Sistemas Inteligentes. Representación compacta de distribuciones de probabilidad conjunta mediante grafos. Permiten abstraer relaciones de independencia condicional. Generalización de Redes Neuronales y Modelos Ocultos de Markov. Nodos: representan variables aleatorias. Grafo: representa un conjunto de independencias y factoriza una distribución. Taxonomía Redes Bayesianas (Bayesian Networks): Grafos Dirigidos. Campos de Markov Aleatorios (Markov Random Fields): Grafos No-Dirigidos. Aspectos fundamentales Inferencia: deducir distribuciones de probabilidad a partir de otras dadas. Aprendizaje: obtener el modelo probabilístico a partir de observaciones. Redes Bayesianas Una Red Bayesiana es un modelo gráfico que representa un conjunto de variables aleatorias y sus dependencias condicionales a través de un Grafo Dirigido Acíclico (DAG) . Nodos: representan variables aleatorias (discretas o continuas). Edges: representan dependencias estadísticas entre las variables. Redes Bayesianas: dependencias condicionales Una RB con nodos $x_1, ..., x_D$ define una distribución de probabilidad conjunta: $P(x_1, ..., x_D) = \prod_{i=1}^D P(x_i | a(x_i))$, donde $a(x_i)$ representa las dependencias asociadas al nodo $x_i$. Reglas de independencia condicional e incondicional Independencia incondicional (a $\perp\hspace{-0.7em}\perp$ b): $p(a|b) = p(a)$ o $p(a,b) = p(a)p(b)$. Independencia condicional (a $\perp\hspace{-0.7em}\perp$ b | c): $p(a|b,c) = p(a|c)$ o $p(a,b|c) = p(a|c)p(b|c)$. Dirección causal (a $\to$ c $\to$ b): $a \perp\hspace{-0.7em}\perp b | c$ $a \not\perp\hspace{-0.7em}\perp b$ Causa común (a $\leftarrow$ c $\to$ b): $a \perp\hspace{-0.7em}\perp b | c$ $a \not\perp\hspace{-0.7em}\perp b$ Estructura en V (a $\to$ c $\leftarrow$ b): $a \not\perp\hspace{-0.7em}\perp b | c$ $a \perp\hspace{-0.7em}\perp b$ Inferencia en Redes Bayesianas Calcular la probabilidad a posteriori de una variable $x$ a partir de distribuciones conjuntas, dada evidencia $e$: $P(x|e) = \frac{P(x,e)}{P(e)}$. $P(x,e) = \sum_f P(x,e,f)$; $P(e) = \sum_{x,f} P(x,e,f)$. Predicción: ¿$P(\text{síntoma}|\text{enfermedad})$? Diagnóstico: ¿$P(\text{enfermedad}|\text{síntomas})$? Algunas Redes Bayesianas simples Clasificadores Naive Bayes: Predecir una clase $y$ dado un vector de características $\mathbf{x} = \{x_1, ..., x_T\}$. Asunción: una vez que se conoce la etiqueta de la clase, todas las características son independientes. $p(x_1, ..., x_T, y) = p(y) \prod_{t=1}^T p(x_t|y)$. Tree-Augmented Naive Bayes (TAN): Se añaden dependencias entre características. Etiquetado de secuencias: (Bigram) Hidden Markov Model: $P(\mathbf{x}, \mathbf{y}) = \prod_{t=1}^T q(y_t|y_{t-1}) e(x_t|y_t)$. (Trigram) Hidden Markov Model: $P(\mathbf{x}, \mathbf{y}) = \prod_{t=1}^T q(y_t|y_{t-2}, y_{t-1}) e(x_t|y_t)$. Campos de Markov Aleatorios (CMA) Un campo de Markov aleatorio es un modelo gráfico, basado en grafos no-dirigidos, que asume un modelo simplificado de independencia condicional. Nodos: representan variables aleatorias. Arcos: representan interacción probabilística entre nodos vecinos. Propiedades de independencia condicional: Los CMA definen las relaciones de independencia condicional a través de una simple separación de grafos: $A \perp\hspace{-0.7em}\perp B | C$ si $C$ separa $A$ de $B$ en el grafo. Un cliqué de un grafo no-dirigido es un subgrafo totalmente conectado. Un cliqué maximal es un cliqué que no es subgrafo de ningún otro cliqué. Una probabilidad $P_G$ define una factorización sobre $G$ si está asociada con: $P_G(X_1,...,X_D) = \frac{1}{Z} \prod_{C \in Q} \psi_C(V_C)$. $V = \{X_1,...,X_D\}$: conjunto de variables aleatorias. $Q$: conjunto de todos los cliqués maximales de $G$. $V_C$: subconjunto de variables del cliqué $C$. $\psi_C: Q \to \mathbb{R}^{>0}$: función potencial para el cliqué $C$. $Z$: factor de normalización. $Z = \sum_{X_1,...,X_D} \prod_{C \in Q} \psi_C(V_C)$. Los CMA son más potentes que las RB, pero tienen un coste computacional mayor. Funciones potenciales en familia exponencial Si las funciones potenciales son de la familia exponencial: $P_G(X_1,...,X_D) = \frac{1}{Z} \prod_{C \in Q} \exp(-E_C(V_C)) = \frac{1}{Z} \exp(-\sum_{C \in Q} E_C(V_C))$. $E_C: Q \to \mathbb{R}$ es una función de energía . Las funciones de energía lineales generalizadas: $E_C(V_C) = - \sum_k \theta_{C,k} f_{C,k}(V_C)$. Los Campos Aleatorios Condicionales (CRF) son un ejemplo de CMA para modelos discriminativos: $p(y|\mathbf{x}; \theta) = \frac{\exp\{\sum_{t=1}^T \sum_{k=1}^K \theta_k f_k(y_{t-1}, y_t, x_t)\}}{Z(\mathbf{x}; \theta)}$. $Z(\mathbf{x}; \theta) = \sum_{y' \in \mathcal{Y}^*} \exp\{\sum_{t=1}^T \sum_{k=1}^K \theta_k f_k(y'_{t-1}, y'_t, x_t)\}$. CRF: tres problemas básicos Decodificación: Predecir la mejor interpretación para la entrada $\mathbf{x}$. $\hat{y} = \arg\max_y p(y|\mathbf{x}; \theta) = \arg\max_y \prod_{t=1}^T \exp\{\sum_{k=1}^K \theta_k f_k(y_{t-1}, y_t, x_t)\}$. Inferencia: Probabilidad a posteriori de la interpretación $y$ dado la entrada $\mathbf{x}$. $p(y|\mathbf{x}; \theta) = \frac{1}{Z(\mathbf{x}; \theta)} \prod_{t=1}^T \exp\{\sum_{k=1}^K \theta_k f_k(y_{t-1}, y_t, x_t)\}$. Estimación de los parámetros: Aprender los parámetros $\theta$ a partir de un conjunto de datos de entrenamiento $\Omega = \{(\mathbf{x}^{(1)}, y^{(1)}), ..., (\mathbf{x}^{(N)}, y^{(N)})\}$. CRF como grafos de factores Un factor (transición): $\Psi_t(y_{t-1}, y_t, x_t) \stackrel{def}{=} \exp\{\sum_{k=1}^K \theta_k f_k(y_{t-1}, y_t, x_t)\}$. Un CRF se puede definir como: $p(y|\mathbf{x}; \theta) = \frac{1}{Z(\mathbf{x}; \theta)} \prod_{t=1}^T \Psi_t(y_{t-1}, y_t, x_t)$. Para $Z(\mathbf{x}; \theta)$: $Z(\mathbf{x}; \theta) = \sum_{y' \in \mathcal{Y}^*} \prod_{t=1}^T \Psi_t(y'_{t-1}, y'_t, x_t)$. Decodificación de CRF: algoritmo de Viterbi Definición: Puntuación de la secuencia óptima de $\mathbf{x}_1^T$ que termina en $y_t = s \in \mathcal{Y}$. $\gamma_t(s) \stackrel{def}{=} \max_{y_1...y_{t-1}} \prod_{i=1}^t \Psi_i(y_{i-1}, y_i, x_i)$. Inicialización: $\gamma_1(s) = \Psi_1(y_0=\text{null}, y_1=s, x_1)$. Recursión: $\gamma_t(s) = \max_{s' \in \mathcal{Y}} \{\gamma_{t-1}(s') \Psi_t(y_{t-1}=s', y_t=s, x_t)\}$. Resultado final: $\max_s \gamma_T(s)$. La secuencia óptima $\hat{y}$ se obtiene empleando punteros (hacia atrás).