Modelos Estructurados & Gráficos

Cheatsheet Content

Tema 7: Predicción Estructurada y HMMs 1. Predicción Estructurada Observación de entrada ($x$): $x \in \mathcal{X}$, puede ser cualquier clase de objeto. Interpretación de salida ($y$): $y \in \mathcal{Y}$, es un objeto estructurado complejo (secuencia, árbol, grafo). Función de predicción estructurada ($f$): $f: \mathcal{X} \to \mathcal{Y}$, asigna una interpretación $y = f(x)$ a una observación $x$. Solución basada en Teoría de la Decisión Estadística: $\hat{y} = f(x) = \operatorname{argmax}_{y \in \mathcal{Y}(M)} P(y|x; G_\theta)$. 2. Lenguajes Formales y Gramáticas Alfabeto ($\Sigma$): Conjunto finito no vacío de símbolos. Cadena: Secuencia finita de símbolos de un alfabeto. Cadena vacía ($\epsilon$): Cadena sin símbolos, $|\epsilon| = 0$. Lenguaje ($L$): Subconjunto de $\Sigma^*$. Gramática ($G$): Tupla $(N, \Sigma, S, P)$. $N$: Símbolos no-terminales. $\Sigma$: Símbolos terminales, $N \cap \Sigma = \emptyset$. $S$: Símbolo inicial (axioma), $S \in N$. $P$: Producciones o reglas $(\alpha \to \beta)$. Derivaciones: Derivación Elemental ($\Rightarrow$): Si $\alpha \to \beta \in P$, entonces $\gamma \alpha \delta \Rightarrow \gamma \beta \delta$ para cualquier $\gamma, \delta \in (N \cup \Sigma)^*$. Derivación ($\Rightarrow^*$): Una cadena $\omega_0$ deriva a $\omega_n$ (escrito $\omega_0 \Rightarrow^* \omega_n$) si existe una secuencia de $n \ge 0$ derivaciones elementales: $\omega_0 \Rightarrow \omega_1 \Rightarrow \dots \Rightarrow \omega_n$. Forma Sentencial: Cualquier cadena $\omega \in (N \cup \Sigma)^*$ tal que $S \Rightarrow^* \omega$. Lenguaje generado por $G$: $L(G) = \{w \in \Sigma^* | S \Rightarrow^* w\}$. Jerarquía de Chomsky: Tipo 0 (sin restricciones): Las producciones son de la forma $\alpha \to \beta$, donde $\alpha \in (N \cup \Sigma)^*$ y $|\alpha| \ge 1$. Aceptadas por Máquinas de Turing. Tipo 1 (sensibles al contexto): Las producciones son de la forma $\alpha A \beta \to \alpha \gamma \beta$, donde $A \in N$, $\alpha, \beta \in (N \cup \Sigma)^*$, $\gamma \in (N \cup \Sigma)^+$ y $\epsilon \notin P$. Aceptadas por Autómatas Linealmente Acotados. Tipo 2 (incontextuales): Las producciones son de la forma $A \to \gamma$, donde $A \in N$, $\gamma \in (N \cup \Sigma)^*$. Aceptadas por Autómatas de Pila. Tipo 3 (regulares): Las producciones son de la forma $A \to aB$ o $A \to a$, donde $A, B \in N$, $a \in \Sigma$. Aceptadas por Autómatas Finitos. 3. Autómatas Finitos Autómata Finito Determinista (AFD): Tupla $M = (Q, \Sigma, \delta, q_0, F)$. $Q$: Conjunto finito de estados. $\Sigma$: Alfabeto de entrada. $\delta: Q \times \Sigma \to Q$: Función de transición (determinista). $q_0 \in Q$: Estado inicial. $F \subseteq Q$: Conjunto de estados finales (o de aceptación). Autómata Finito No-Determinista (AFND): Tupla $M = (Q, \Sigma, \delta, q_0, F)$. $Q$: Conjunto finito de estados. $\Sigma$: Alfabeto de entrada. $\delta: Q \times (\Sigma \cup \{\epsilon\}) \to \mathcal{P}(Q)$: Función de transición (no-determinista, puede incluir $\epsilon$-movimientos). $q_0 \in Q$: Estado inicial. $F \subseteq Q$: Conjunto de estados finales (o de aceptación). Equivalencia de Modelos: Teorema 1: Para cada AFND $M_{ND}$ que reconoce un lenguaje $L$, existe un AFD $M_D$ que también reconoce $L$. Teorema 2: Un lenguaje $L$ es generado por una Gramática Regular si y sólo si $L$ es reconocido por un Autómata Finito (AFD o AFND). 4. Lenguajes y Gramáticas Probabilísticas Lenguaje probabilístico ($L, P$): Dado un alfabeto $\Sigma$, $P$ es una función de probabilidad sobre $\Sigma^*$ tal que: $P(x) \ge 0$ para toda $x \in \Sigma^*$. $\sum_{x \in L} P(x) = 1$. $P(x) = 0$ si $x \notin L$. Teorema de Wetherell: Un lenguaje es probabilístico si y sólo si es generado por una Gramática Probabilística Incontextual (GPI) y la suma de las probabilidades de todas las cadenas de $L$ es 1. Gramáticas Regulares Probabilísticas (GRP): $G_\theta = (G, P)$, donde $G=(N, \Sigma, S, P_G)$, y $P: P_G \to ]0,1]$ son las probabilidades de las reglas. Condición de normalización: $\forall A \in N, \sum_{A \to \beta \in P_G} P(A \to \beta) = 1$. Probabilidad de un árbol de análisis: $P_\theta(x, t_x) = \prod_{r_j \in t_x} P(r_j)$. Probabilidad de una cadena: $P_\theta(x) = \sum_{t_x \in T_x} P_\theta(x, t_x)$. Probabilidad del mejor árbol: $\hat{P}_\theta(x) = \max_{t_x \in T_x} P_\theta(x, t_x)$. 5. Clasificación Sintáctico-Estadística Regla de clasificación de Bayes: Para clasificar una cadena $x$ en una de $K$ clases $C_1, \dots, C_K$: $$ \text{Clase}(x) = \operatorname{argmax}_{C_i} P(C_i|x) $$ Expandiendo con el Teorema de Bayes: $$ \text{Clase}(x) = \operatorname{argmax}_{C_i} \frac{P(x|C_i)P(C_i)}{P(x)} $$ Como $P(x)$ es constante para todas las clases, se simplifica a: $$ \text{Clase}(x) = \operatorname{argmax}_{C_i} P(x|C_i)P(C_i) $$ Donde $P(x|C_i)$ es la probabilidad de observar la cadena $x$ dado el modelo probabilístico (ej. HMM o GRP) asociado a la clase $C_i$, y $P(C_i)$ es la probabilidad a priori de la clase. 6. Modelos Ocultos de Markov (HMM) Definición: $M = (\Sigma, Q, \pi, A, B)$. $\Sigma$: Alfabeto de símbolos observables. $Q$: Conjunto de estados. $\pi$: Vector de probabilidades iniciales, $\pi_q = P(q_1 = q)$. $A$: Matriz de transición de estados, $A_{q,q'} = P(q_{t+1} = q' | q_t = q)$. $B$: Matriz de emisión de símbolos, $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$. $0 \le A_{q,q'} \le 1$, $\sum_{q' \in Q} A_{q,q'} = 1$. $0 \le B_{q,\sigma} \le 1$, $\sum_{\sigma \in \Sigma} B_{q,\sigma} = 1$. Probabilidad de una cadena: Probabilidad de $x$ y una secuencia de estados $y$ juntos: $$ P(x, y; M) = \pi_{y_1} \prod_{t=2}^T A_{y_{t-1},y_t} \prod_{t=1}^T B_{y_t, x_t} $$ Probabilidad de $x$ (marginando sobre todas las secuencias de estados $y$): $$ P(x; M) = \sum_{y \in Q^T} P(x, y; M) = \sum_{y_1 \dots y_T} \left( \pi_{y_1} \prod_{t=2}^T A_{y_{t-1},y_t} \prod_{t=1}^T B_{y_t, x_t} \right) $$ Algoritmo Forward (Cálculo $P(x;M)$): $\alpha(q, t) = P(x_1 \dots x_t, q_t=q)$. Inicialización: $\alpha(q, 1) = \pi_q B_{q, x_1}$ para $t=1$. Recursión: $\alpha(q, t) = \left( \sum_{q' \in Q} \alpha(q', t-1) A_{q',q} \right) B_{q, x_t}$ para $t > 1$. Terminación: $P(x; M) = \sum_{q \in Q} \alpha(q, T)$. Algoritmo de Viterbi (Decodificación - $\hat{y}$): $\delta(q, t) = \max_{q_1 \dots q_{t-1}} P(x_1 \dots x_t, q_1 \dots q_{t-1}, q_t=q)$. Inicialización: $\delta(q, 1) = \pi_q B_{q, x_1}$ para $t=1$. Recursión: $\delta(q, t) = \left( \max_{q' \in Q} \delta(q', t-1) A_{q',q} \right) B_{q, x_t}$ para $t > 1$. Punteros hacia atrás: $\psi(q, t) = \operatorname{argmax}_{q' \in Q} \delta(q', t-1) A_{q',q}$. Terminación: $\hat{P}(x; M) = \max_{q \in Q} \delta(q, T)$. Secuencia óptima: Se obtiene retrocediendo desde $q_T^* = \operatorname{argmax}_q \delta(q, T)$ usando $\psi$. Estimación de parámetros (Entrenamiento): Objetivo: Encontrar los parámetros $\theta = (\pi, A, B)$ que maximizan la verosimilitud de los datos de entrenamiento $\mathcal{D} = \{x^{(1)}, \dots, x^{(N)}\}$: $$ \theta^* = \operatorname{argmax}_{\theta} L(\theta | \mathcal{D}) = \operatorname{argmax}_{\theta} \sum_{i=1}^N \log P(x^{(i)}; M_\theta) $$ Algoritmo de re-estimación por Viterbi (hard assignment): Inicializar: Escoger valores iniciales para $\pi, A, B$ (aleatorios o heurísticos). Analizar (Viterbi): Para cada secuencia de observación $x^{(j)}$ en el conjunto de entrenamiento, encontrar la secuencia de estados más probable $\hat{y}^{(j)}$ usando el algoritmo de Viterbi. Contabilizar: Contar las ocurrencias de estados iniciales, transiciones y emisiones en las secuencias $\hat{y}^{(j)}$: $C(\text{init}, q)$: Número de veces que el estado $q$ es el primer estado en una secuencia. $C(\text{trans}, q, q')$: Número de veces que hay una transición de $q$ a $q'$. $C(\text{emit}, q, \sigma)$: Número de veces que el símbolo $\sigma$ es emitido desde el estado $q$. Normalizar: Re-estimar los parámetros usando las cuentas normalizadas: $$ \hat{\pi}_q = \frac{C(\text{init}, q)}{\sum_{q'' \in Q} C(\text{init}, q'')} $$ $$ \hat{A}_{q,q'} = \frac{C(\text{trans}, q, q')}{\sum_{q'' \in Q} C(\text{trans}, q, q'')} $$ $$ \hat{B}_{q,\sigma} = \frac{C(\text{emit}, q, \sigma)}{\sum_{\sigma' \in \Sigma} C(\text{emit}, q, \sigma')} $$ Repetir los pasos 2-4 hasta que los parámetros converjan o el cambio sea mínimo. Algoritmo de Baum-Welch (EM - soft assignment): Calcula las probabilidades esperadas de ocurrencias en lugar de conteos duros. Utiliza los algoritmos Forward y Backward para calcular $\gamma(q, t) = P(q_t=q | x, M)$ y $\xi(q, q', t) = P(q_t=q, q_{t+1}=q' | x, M)$. Fórmulas de re-estimación: $$ \hat{\pi}_q = \gamma(q, 1) $$ $$ \hat{A}_{q,q'} = \frac{\sum_{t=1}^{T-1} \xi(q,q',t)}{\sum_{t=1}^{T-1} \gamma(q,t)} $$ $$ \hat{B}_{q,\sigma} = \frac{\sum_{t=1, x_t=\sigma}^T \gamma(q,t)}{\sum_{t=1}^T \gamma(q,t)} $$ Tema 8: Modelos Gráficos 1. Introducción a Modelos Gráficos (MG) Definición: Marco formal que combina probabilidad y lógica estructural (independencias) para representar fenómenos complejos. Nodos: Representan variables aleatorias. Grafo: Representa un conjunto de independencias y factoriza una distribución. Taxonomía: Redes Bayesianas (Grafos Dirigidos). Campos de Markov Aleatorios (Grafos No-Dirigidos). Aspectos Fundamentales: Inferencia: Deducir distribuciones de probabilidad. Aprendizaje: Obtener el modelo probabilístico a partir de observaciones. 2. Redes Bayesianas (RB) Definición: Modelo gráfico que representa un conjunto de variables aleatorias y sus dependencias condicionales a través de un Grafo Dirigido Acíclico (DAG). Factorización de la distribución conjunta: Para $x_1, \dots, x_D$ en una RB: $$ P(x_1, \dots, x_D) = \prod_{i=1}^D P(x_i | \text{padres}(x_i)) $$ donde $\text{padres}(x_i)$ son los nodos que tienen aristas dirigidas hacia $x_i$. 3. Independencia Condicional (d-separación) Independencia incondicional: $a \perp b \iff P(a|b) = P(a) \iff P(a,b) = P(a)P(b)$. Independencia condicional: $a \perp b | c \iff P(a|b,c) = P(a|c) \iff P(a,b|c) = P(a|c)P(b|c)$. d-separación: Dos conjuntos de nodos $A$ y $B$ son d-separados por un conjunto de nodos $C$ si todo camino entre un nodo en $A$ y un nodo en $B$ está "bloqueado" por $C$. Un camino está bloqueado si: 1. Dirección Causal (Cadena): $X \to Z \to Y$. $X \not\perp Y$ (dependientes si Z no se observa). $X \perp Y | Z$ (independientes si Z se observa). 2. Causa Común: $X \leftarrow Z \to Y$. $X \not\perp Y$ (dependientes si Z no se observa). $X \perp Y | Z$ (independientes si Z se observa). 3. Estructura en V (Colisionador): $X \to Z \leftarrow Y$. $X \perp Y$ (independientes si Z no se observa y ningún descendiente de Z se observa). $X \not\perp Y | Z$ (dependientes si Z se observa o si un descendiente de Z se observa). Observar un efecto hace que sus causas sean dependientes. 4. Inferencia en Redes Bayesianas Problema general: Calcular $P(x|e)$ donde $x$ es una variable de interés, $e$ es evidencia (variables observadas), y $f$ son las variables restantes (ocultas). $$ P(x|e) = \frac{P(x,e)}{P(e)} = \frac{\sum_f P(x,e,f)}{\sum_{x,f} P(x,e,f)} $$ Tipos de inferencia: Predicción: ¿$P(\text{síntoma}|\text{enfermedad})$? (Causal) Diagnóstico: ¿$P(\text{enfermedad}|\text{síntoma})$? (Evidencial) 5. Clasificadores Bayesianos Simples Naive Bayes: Asume que las características $x_t$ son condicionalmente independientes dada la clase $Y$. $$ P(x_1, \dots, x_T, Y) = P(Y) \prod_{t=1}^T P(x_t | Y) $$ Modelos Ocultos de Markov (HMM): (Ver Tema 7). Son un tipo de RB para secuencias donde las observaciones son condicionalmente independientes de otras observaciones dadas las variables de estado ocultas. $$ P(x,y) = P(y_1) \prod_{t=2}^{T} P(y_t|y_{t-1}) \prod_{t=1}^{T} P(x_t|y_t) $$ 6. Campos de Markov Aleatorios (CMA) Definición: Modelo gráfico basado en grafos no-dirigidos, asume un modelo simplificado de independencia condicional. Propiedades de independencia condicional: La independencia $A \perp B | C$ se define por la separación de $A$ y $B$ en el grafo no-dirigido cuando $C$ es observado (si $C$ forma una "barrera" entre $A$ y $B$). Cliqué: Subgrafo totalmente conectado. Cliqué maximal: Cliqué que no es subgrafo de ningún otro cliqué. Factorización (Teorema de Hammersley-Clifford): La distribución de probabilidad conjunta $P_G(X_1, \dots, X_D)$ se factoriza sobre los cliqués maximales $C \in \mathcal{Q}$ del grafo $G$. $$ P_G(X_1, \dots, X_D) = \frac{1}{Z} \prod_{C \in \mathcal{Q}} \psi_C(V_C) $$ donde $\psi_C(V_C)$ es una función potencial (factor) para el cliqué $C$, y $Z$ es la constante de normalización. Funciones Potenciales Exponenciales: Si $\psi_C(V_C) = \exp(-E_C(V_C))$, donde $E_C(V_C)$ es la función de energía para el cliqué $C$. $$ P_G(X_1, \dots, X_D) = \frac{1}{Z} \exp \left( - \sum_{C \in \mathcal{Q}} E_C(V_C) \right) $$ Campos Aleatorios Condicionales (CRF): Modelan $P(Y|X)$ directamente, son discriminativos. $$ P(y|x; \theta) = \frac{1}{Z(x)} \exp \left\{ \sum_{k=1}^K \theta_k f_k(x, y) \right\} $$ Para un CRF lineal-cadena: $$ P(y|x; \theta) = \frac{1}{Z(x)} \exp \left\{ \sum_{t=1}^T \sum_{k=1}^K \theta_k f_k(y_{t-1}, y_t, x, t) \right\} $$ donde $Z(x) = \sum_{y' \in \mathcal{Y}^*} \exp \left\{ \sum_{t=1}^T \sum_{k=1}^K \theta_k f_k(y'_{t-1}, y'_t, x, t) \right\}$. CRF: Problemas Básicos: Decodificación: Predecir $\hat{y} = \operatorname{argmax}_y P(y|x; \theta)$ (Algoritmo de Viterbi, adaptado para CRF). Inferencia (marginación): Calcular $P(y_i|x; \theta)$ o $P(y_i, y_j|x; \theta)$. Estimación de parámetros: Aprender $\theta$ a partir de datos de entrenamiento (optimización convexa, ej. L-BFGS, gradiente descendente).