Reconocimiento de Formas

Cheatsheet Content

Tema 5: Árboles de Clasificación Árboles de Decisión y Clasificación (ADC) 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. Notación Espacio de representación: $E \equiv \mathbb{R}^D;\; y=(y_1,y_2,\ldots,y_D)$ Muestra de aprendizaje: $(y_1,c_1),\ldots,(y_N,c_N),\quad y_i\in E,\quad c_i\in C=\{1,2,\ldots,C\},\quad 1\le i\le N$ Árbol $T$, nodo $t$, hijos $t_L,t_R$, nodos terminales $\tilde{T}$. Partición binaria (“split”) $s$, conjunto de particiones $S$. Construcción / Aprendizaje de un ADC Método para hacer particiones y seleccionar la mejor. Criterio para considerar un nodo suficientemente “puro” (homogéneo) como terminal. Criterio para asignar una etiqueta a un nodo terminal. Conjunto de preguntas admisibles para particiones Preguntas: ¿$y_j\le r$?, donde $s=(j,r)$. Número de "splits" a explorar: $O(D\,N(t))$. Estimación de probabilidades asociadas a los nodos Probabilidad a priori de la clase $c$: $\hat{P}(c)=\frac{N_c}{N}$ Probabilidad a posteriori de clase en el nodo $t$: $\hat{P}(c\mid 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)}$ Evaluación de la calidad de una partición (impureza) Impureza de un nodo $t$ mediante entropía: $$ I(t)=-\sum_{c=1}^{C}\hat{P}(c\mid t)\log_2\hat{P}(c\mid t) $$ Decremento de impureza al particionar $t$ con $s=(j,r)$: $$ \Delta I(j,r,t)\overset{\text{def}}{=}I(t)-\hat{P}_t(L)\,I(t_L)-\hat{P}_t(R)\,I(t_R) $$ Mejor partición (maximiza el decremento): $$ (j^\star,r^\star)=\arg\max_{1\le j\le D,\;-\infty Entropía Fórmula: $H=-\sum_{i=1}^{k}P_i\log_2 P_i \quad (0\log 0\ \text{def}=0)$ Ejemplos: $P_1=P_2=1/2$, $H=1$ bit $P_1=1, P_2=0$, $H=0$ bits $P_i=1/k$, $H=\log_2 k$ Criterios de suficiente “pureza” en nodos terminales $t$ es terminal si: $\max_{1\le j\le D,\;-\infty Asignación de etiqueta a nodos terminales Clase de la mayoría: $c^\star(t)=\arg\max_{1\le c\le C}\hat{P}(c\mid t),\ \forall t\in\tilde{T}$ Complejidad Temporal: $O(D N (\log N)^2)$ Espacial: $O(N)$ Estimación por resustitución del error de clasificación Error en nodo terminal $t$: $\hat{P}_t(\text{error}) = 1 - \max_{1 \le c \le C} \hat{P}(c \mid t)$ Error para el árbol $T$: $\hat{P}_T(\text{error}) = \sum_{t \in \tilde{T}} \hat{P}(t)\hat{P}_t(\text{error})$ Otras medidas de impureza Índice Gini y probabilidad de error. Tema 6: Máquinas de Vectores Soporte y Núcleos Funciones Discriminantes Lineales (FDL) Definición: $\varphi(x;\Theta)=\theta^t x+\theta_0=\sum_{i=1}^{d}\theta_i x_i+\theta_0$ Condición para clasificación: $c_n (\theta^t x_n + \theta_0) \ge 0,\quad 1 \le n \le N$ Propiedades de las FDL Hiperplano: $H=\{x\mid \varphi(x;\Theta)=0\}$ Vector de pesos $\theta$ es ortogonal a $H$. Distancia de $x_s$ a $H$: $r_{x_s}=\frac{|\theta^t x_s+\theta_0|}{\|\theta\|}$ Clasificadores de margen máximo (SVM), muestras separables Objetivo: minimizar $\frac12\,\theta^t\theta$ Sujeto a: $c_n(\theta^t x_n+\theta_0)\ge 1,\quad 1\le n\le N$ Multiplicadores de Lagrange (separable) Lagrangiana: $\Lambda(\theta,\theta_0,\alpha)=\frac12\theta^t\theta-\sum_{n=1}^{N}\alpha_n\big[c_n(\theta^t x_n+\theta_0)-1\big]$ Condiciones: $\frac{\partial \Lambda}{\partial \theta_0}=0\ \Rightarrow\ \sum_{n=1}^{N}\alpha_n c_n=0$ $\frac{\partial \Lambda}{\partial \theta}=0\ \Rightarrow\ \theta^* = \sum_{n=1}^{N}\alpha_n c_n x_n$ Dual: $\Lambda_D(\alpha)=\sum_{n=1}^{N}\alpha_n-\frac12\sum_{n=1}^{N}\sum_{m=1}^{N}c_n c_m\,\alpha_n\alpha_m\,x_n^t x_m$ Optimización: Maximizar $\Lambda_D(\alpha)$ sujeto a $\sum_{n=1}^{N}\alpha_n c_n=0,\quad \alpha_n\ge 0,\quad 1\le n\le N$ Propiedades de las soluciones SVM $\theta_0^* = c_m - \theta^{*t} x_m$ para cualquier $m$ con $\alpha_m^* \ne 0$. Condición KKT: $\alpha_n^* [c_n (\theta^{*t} x_n + \theta_0^*) - 1] = 0,\; 1 \le n \le N$ Vectores soporte Muestras $x_n$ para las que $\alpha_n^* \ne 0$. Distancia al hiperplano: $\frac{1}{\|\theta^*\|}$ FDL que maximiza el margen: $\varphi_{svm}(x; \alpha^*, S) = \sum_{n \in \mathcal{V}}c_n \alpha_n^* x_n^t x + \left(c_m - \sum_{n \in \mathcal{V}}c_n \alpha_n^* x_n^t x_m\right)$ Muestras no separables: "márgenes blandos" Variables de holgura: $c_n (\theta^t x_n + \theta_0) \ge 1 - \zeta_n;\; \zeta_n \ge 0$ Objetivo: $\min \frac{1}{2}\theta^t\theta + C \sum_{n=1}^{N}\zeta_n$ Sujeto a: $c_n (\theta^t x_n + \theta_0) + \zeta_n - 1 \ge 0$, $\zeta_n \ge 0$ SVM en el caso de no separabilidad lineal Lagrangiana dual: $\Lambda_D(\alpha, \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 x_n^t x_m$ Sujeto a: $\sum_{n=1}^{N}\alpha_n c_n = 0,\; 0 \le \alpha_n \le C,\; 1 \le n \le N$ Generalización de SVM: Núcleos Función discriminante con núcleo: $\varphi_K(x) = \sum_{n=1}^{N}\alpha_n c_n K(x_n, x) + \theta_0$ Función núcleo $K(x,x') = \psi(x)^t \psi(x')$, donde $\psi$ es la transformación al espacio de características. Construcción de núcleos $K(x,x')$ debe ser simétrica y semidefinida positiva (Condición de Mercer): $\sum_{n=1}^{N}\sum_{m=1}^{N}c_n c_m K(x_n, x_m) \ge 0$ Ejemplos de funciones kernel Kernel Lineal: $K_L(x,x') = x^t x'$ Kernel polinómico de grado $p$: $K_P(x,x') = [\gamma x^t x' + \tau]^p$ Kernel gaussiano: $K_G(x,x') = \exp (\gamma \|x - x'\|^2)$ Kernel de base radial (RBK): $K_{RBK}(x,x') = f(r);\; r = \|x - x'\|$ Máquinas de vectores soporte y núcleos Lagrangiana dual: $\Lambda_D(\alpha) = \sum \alpha_n - \frac{1}{2} \sum \sum c_n c_m \alpha_n \alpha_m K(x_n, x_m)$ FDLG con núcleos: $\varphi_K(x) = \sum_{n \in \mathcal{V}}c_n \alpha_n^* K(x_n, x) + \left(c_m - \sum_{m \in \mathcal{V}}c_m \alpha_m^* K(x_m, x_n)\right)$ SVM para problemas de C clases Estrategias: Uno-contra-uno, Uno-contra-resto. Tema 7: Teoría de Lenguajes Formales y Modelos Ocultos de Markov Predicción Estructurada Interpretación de salida: $y \in \mathcal{Y}$ es un objeto estructurado. Solución basada en Teoría de la decisión estadística: $$ P(x;G_\theta)\equiv P(x;\theta) $$ $$ \hat{y}=f(x)=\arg\max_{y\in L(G_\theta)} P(y\mid x;G_\theta) $$ Lenguaje Probabilístico $L \subseteq \Sigma^*$ lenguaje característico. $\phi:\Sigma^\ast\to [0,1]$ función probabilística computable: $x\notin L\Rightarrow \phi(x)=0$ $x\in L\Rightarrow 0 $\sum_{x\in L}\phi(x)=1$ Gramáticas regulares probabilísticas Probabilidad de un árbol de análisis: $P_\theta(x,t_x)=\prod_{j=1\cdots m} 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 de análisis: $P_\theta^c(x)=\max_{t_x\in T_x} P_\theta(x,t_x)$ Lenguaje generado por una gramática probabilística: $L(G_\theta)=\{x\in L(G)\mid P_\theta(x)>0\}$ Modelo Oculto de Markov (HMM) Un HMM es una quíntupla $M=(\Sigma,Q,F,\pi,A,B)$ donde: $\Sigma$: alfabeto (observables). $Q$: conjunto de estados. $q_f\in F\subseteq Q$: estado final especial. $\pi:(Q-\{q_f\})\to\mathbb{R}$ probabilidades iniciales: $\pi_q=P(q_1=q)$ $A:(Q-\{q_f\})\times Q\to\mathbb{R}$ transiciones: $A_{q,q'}=P(q_{t+1}=q'\mid q_t=q)$ $B:(Q-\{q_f\})\times \Sigma\to\mathbb{R}$ emisiones: $B_{q,\sigma}=P(x_t=\sigma\mid q_t=q)$ Condiciones de normalización para $\pi,A,B$ Estado inicial: $0\le \pi_q\le 1,\qquad \sum_{q\in Q}\pi_q=1,\qquad \pi_F=0$ Transiciones: $0\le A_{q,q'}\le 1,\qquad \sum_{q'\in Q}A_{q,q'}=1,\qquad A_{F,q}=0$ Emisiones: $0\le B_{q,\sigma}\le 1,\qquad \sum_{\sigma\in\Sigma}B_{q,\sigma}=1,\qquad B_{F,\sigma}=0$ Probabilidad conjunta y de cadena en HMM Probabilidad de que $M$ produzca $x$ mediante $y$: $$ P(x,y)=P(q_1)\cdot\Big(\prod_{t=2}^{T}P(q_t\mid q_{t-1})\Big)\cdot P(q_f\mid q_T)\cdot \Big(\prod_{t=1}^{T}P(x_t\mid q_t)\Big) $$ Probabilidad de que $M$ genere la cadena $x$: $P(x;M)=\sum_{y\in Q^+}P(x,y)$ Algoritmo Forward Definición: $\alpha(q,t)\overset{\text{def}}{=}\sum_{q_1,\ldots,q_t:\ q_t=q} P(x_1\cdots x_t,q_1,\ldots,q_t)$ Recursión: $$ \alpha(q,t)= \begin{cases} \pi_q\,B_{q,x_1} & \text{si } t=1\\[2mm] \sum_{q'\in Q}\alpha(q',t-1)\,A_{q',q}\,B_{q,x_t} & \text{si } t>1 \end{cases} $$ Probabilidad de la cadena: $P(x;M)=\sum_{q\in Q}\alpha(q,T)\,A_{q,F}$ Complejidad temporal: $O(T\,b)$ Algoritmo de Viterbi Definición: $\gamma(q,t)\overset{\text{def}}{=}\max_{q_1,\ldots,q_t:\ q_t=q} P^b(x_1\cdots x_t,q_1,\ldots,q_t)$ Recursión: $$ \gamma(q,t)= \begin{cases} \pi_q\,B_{q,x_1} & \text{si } t=1\\[2mm] \max_{q'\in Q}\gamma(q',t-1)\,A_{q',q}\,B_{q,x_t} & \text{si } t>1 \end{cases} $$ Probabilidad de la mejor interpretación: $P^b(x;M)=\max_{q\in Q}\gamma(q,T)\,A_{q,F}$ Complejidad temporal: $O(T\,b)$ Estimación de modelos de Markov Corpus: $\Omega=\{x_1,\ldots,x_N\}$ Función objetivo: $P(\Omega;M_\theta)=\prod_{k=1}^{N} P(x_k;M_\theta)$ Estimador de máxima probabilidad: $\hat{\theta}=\arg\max_{\theta}\sum_{k=1}^{N}\log P(x_k;M_\theta)$ Función objetivo alternativa (Viterbi): $P(\Omega,\hat{Y}_\Omega;M_\theta)=\prod_{k=1}^{N} P(x_k,\hat{y}_{x_k};M_\theta)$ Estimador Viterbi: $\hat{\theta}=\arg\max_{\theta}\sum_{k=1}^{N}\log P(x_k,\hat{y}_{x_k};M_\theta)$ Algoritmo de reestimación por Viterbi Probabilidad conjunta: $P(x, \hat{y}) = P(q_1) \prod_{t=2}^{T} P(q_t \mid q_{t-1}) P(\# \mid q_T) \prod_{t=1}^{T} P(x_t \mid q_t)$ Probabilidad inicial: $\hat{\pi}_q = P(q \mid \#) = \frac{N(\pi_q, \hat{y})}{N(\pi, \hat{y})}$ Probabilidad de transición: $\hat{A}_{q,q'} = P(q' \mid q) = \frac{N(A_{q,q'}, \hat{y})}{N(A_q, \hat{y})}$ Probabilidad de emisión: $\hat{B}_{q,\sigma} = P(\sigma \mid q) = \frac{N(B_{q,\sigma}, \hat{y})}{N(B_q, \hat{y})}$ Clasificación sintáctico-estadística Probabilidad a posteriori: $P(c \mid x; M_c) = \frac{P(x \mid c; M_c) P(c)}{P(x)}$ Regla de clasificación: $\hat{c}(x) = \arg\max_{1 \le c \le C} P(c \mid x; M_c)$ Tema 8: Redes Bayesianas y Modelos Gráficos Probabilísticos Redes Bayesianas Distribución de probabilidad conjunta: $P(x_1, \ldots, x_D) = \prod_{i=1}^{D} P(x_i \mid a(x_i))$ Independencia condicional $a \perp \! \! \! \perp b \mid \emptyset \iff P(a \mid b) = P(a)$ $a \perp \! \! \! \perp b \mid c \iff P(a \mid b, c) = P(a \mid c)$ Reglas de independencia condicional e incondicional Dirección causal: $P(a, b \mid c) = P(a \mid c)P(b \mid c)$ Causa común: $P(a, b \mid c) = P(a \mid c)P(b \mid c)$ Estructura en V: $P(a, b) = P(a)P(b)$ Inferencia en Redes Bayesianas Probabilidad a posteriori: $P(x \mid 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)$ Algunas Redes Bayesianas simples Naive Bayes: $p(x_1, \ldots, x_T, y) = p(y) \prod_{t=1}^{T} p(x_t \mid y)$ Tree-Augmented Naive Bayes: $p(x_1, \ldots, x_4, y) = p(y) \cdot p(x_1 \mid y) \cdot p(x_2 \mid y, x_1) \cdot p(x_3 \mid y, x_1) \cdot p(x_4 \mid y, x_3)$ (Bigram) HMM: $P(x_t^T, y_t^T) = \prod_{t=1}^T q(y_t \mid y_{t-1}) e(x_t \mid y_t)$ (Trigram) HMM: $P(x_t^T, y_t^T) = \prod_{t=1}^T q(y_t \mid y_{t-2}, y_{t-1}) e(x_t \mid y_t)$ Campos de Markov aleatorios (CMA / CAM) Factorización: $P_G(X_1,\ldots,X_D)=\frac{1}{Z}\prod_{C\in Q}\psi_C(V_C)$ Factor de normalización: $Z=\sum_{X_1,\ldots,X_D}\ \prod_{C\in Q}\psi_C(V_C)$ Funciones potenciales exponenciales: $P_G(X_1,\ldots,X_D)=\frac{1}{Z}\exp\Big(-\sum_{C\in Q}E_C(V_C)\Big)$ Energía lineal generalizada: $E_C(V_C)=-\sum_{k}\theta_{C,k}\,f_{C,k}(V_C)$ CRF (Conditional Random Fields) Probabilidad condicional: $p(y\mid x;\theta)=\frac{\exp\left\{\sum_{t=1}^{T}\sum_{k=1}^{K}\theta_k\,f_k(y_{t-1},y_t,x_t)\right\}}{Z(x;\theta)}$ Función de partición: $Z(x;\theta)=\sum_{y'\in Y^\ast}\exp\left(\sum_{t=1}^{T}\sum_{k=1}^{K}\theta_k\,f_k(y'_{t-1},y'_t,x_t)\right)$ CRF: tres problemas básicos Decodificación: $\hat{y}=\arg\max_{y}\prod_{t=1}^{T}\exp\left\{\sum_{k=1}^{K}\theta_k f_k(y_{t-1},y_t,x_t)\right\}$ Inferencia: $p(y\mid x;\theta)=\frac{1}{Z(x;\theta)}\prod_{t=1}^{T}\exp\left\{\sum_{k=1}^{K}\theta_k f_k(y_{t-1},y_t,x_t)\right\}$ Estimación de parámetros: Aprender $\theta$ de $\Omega=\{(x^{(1)},y^{(1)}),\ldots,(x^{(N)},y^{(N)})\}$ CRF como grafos de factores Factor (transición): $\Psi_t(y_{t-1},y_t,x_t)\overset{\text{def}}{=}\exp\left\{\sum_{k=1}^{K}\theta_k\,f_k(y_{t-1},y_t,x_t)\right\}$ CRF con factores: $p(y\mid x;\theta)=\frac{1}{Z(x;\theta)}\prod_{t=1}^{T}\Psi_t(y_{t-1},y_t,x_t)$ $Z(x;\theta)=\sum_{y'\in Y^\ast}\prod_{t=1}^{T}\Psi_t(y'_{t-1},y'_t,x_t)$ Decodificación de CRF: algoritmo de Viterbi Definición: $\gamma_t(s)\overset{\text{def}}{=}\max_{y_1^t;\ y_t=s}\ \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),\quad \forall s\in Y$ Recursión: $\gamma_t(s)=\max_{s'\in Y}\left\{\gamma_{t-1}(s')\cdot \Psi_t(y_{t-1}=s',y_t=s,x_t)\right\}$ Resultado final: $\max_{s}\gamma_T(s)$ Conceptos de probabilidad Probabilidad $P(x)$: $\sum_x P(x)=1$ Probabilidad conjunta $P(x,y)$: $\sum_x\sum_y P(x,y)=1$ Probabilidad condicional $P(x\mid y)$: $\sum_x P(x\mid y)=1\ \ \forall y$ Marginales: $P(x)=\sum_y P(x,y),\qquad P(y)=\sum_x P(x,y)$ Regla de la probabilidad conjunta: $P(x,y)=P(x)\,P(y\mid x)$ Regla de la cadena: $P(x_1,\ldots,x_N)=P(x_1)\prod_{i=2}^{N}P(x_i\mid x_1,\ldots,x_{i-1})$ Regla de Bayes: $P(y\mid x)=\frac{P(y)P(x\mid y)}{\sum_{y'}P(y')P(x\mid y')}$