\documentclass[10pt]{beamer} \usepackage[latin1]{inputenc} \usepackage[spanish]{babel} \usepackage{lxfonts} %\usepackage{beamerthemesplit} \renewcommand{\t}[1]{#1^{\top}} \renewcommand{\v}[1]{\vec{#1}} \newcommand{\mvs}{Máquinas de Vectores Soporte (SVM)} \newcommand{\sub}[1]{\textbf{#1}\\[2ex]} \title{\mvs} \author{Norberto Corral, Carlos Carleos} \begin{document} \frame{\titlepage} \begin{frame} {\mvs} \vspace{0.4cm} Dados $\vec{w} \in \mathbb{R}^p$ y $ b \in \mathbb{R}$, fijos, se define una aplicación lineal $f:\mathbb{R}^p \rightarrow \mathbb{R}$ como: $$f(\vec{x}) = \langle \vec{w}, \vec{x}\rangle + b = \t{\vec{w}} \, \vec{x} + b = \sum_{j=1}^p w_j \, x_j + b$$ \vspace{0.4cm} Se llama hiperplano, $\pi$, al subconjunto de puntos $\mathbb{R}^p$ que verifican: $$\pi = \{\vec{x} \mid f(\vec{x}) =0\, \}$$ \vspace{0.4cm} Cualquier hiperplano de $ \mathbb{R}^2$ define una recta. \end{frame} \begin{frame} {\mvs} El vector $\vec{w}$ es ortogonal a todos los puntos del hiperplano. La distancia entre un hiperplano $\pi$ y un punto $\vec{x} \in \mathbb{R}^p$ es: $$ \text{dist}(\pi, \vec{x} )= \frac{f(\vec{x})} {\|\vec{w}\|} \qquad \mbox{con}\qquad \|\vec{w}\|= \sqrt{\sum_{j=1}^{p} w_j^2 }$$ \vspace{-1cm} \begin{center} \includegraphics[width=6cm]{distancia.pdf} \end{center} \end{frame} \begin{frame} {\mvs} %\begin{Large} { \textcolor{red} {Conjunto linealmente separable} }\end{Large}\\[2ex] \sub{Conjunto linealmente separable} Un conjunto de puntos $(\vec{x}_i, y_i)_{i=1}^n$ con $\vec{x}_i \in \mathbb{R}^p$ , $y_i \in \{-1, +1\}$, es linealmente separable si existe un hiperplano $\pi$ tal que: \vspace{0.2cm} \begin {itemize} \item $ f(\vec{x}_i) = \langle \vec{w}, \vec{x}_i\rangle + b \ge 0 \quad \mbox{si } y_i=+1$ \item $ f(\vec{x}_i) = \langle \vec{w}, \vec{x}_i\rangle + b \le 0 \quad \mbox{si } y_i=-1$ \end {itemize} \vspace{0.3cm} Esas dos condiciones son equivalentes a: $$y_i \,f (\vec{x}_i) = y_i ( \langle \vec{w}, \vec{x} \rangle + b) \ge 0 \quad i= 1, \ldots, n$$ \end{frame} \begin{frame} {\mvs} \begin{center} \includegraphics[width=5cm] {hiperplanos.pdf} \end{center} %\vspace{0.2cm} Cuando existe un hiperplano de separación un criterio razonable para clasificar un punto $\vec{x}$ es: $$G(\vec{x}) = \text{signo} \bigl(f(\vec{x})\bigr)$$ \end{frame} \begin{frame} {\mvs} %\begin{Large} { \textcolor{red} {Margen de un hiperplano de separación} }\end{Large} \sub{Margen de un hiperplano de separación} Dado un conjunto de puntos $(\vec{x}_i)_{i=1}^n$ con $\vec{x}_i \in \mathbb{R}^p$ , y un hiperplano de separación $\pi = \{ \vec x \mid \t{\vec w} \vec x+b=0 \}$ se define su margen como el valor $M$ tal que $$ M=\min_{i=1,\dots,n} \text{dist}(\vec x_i,\pi) $$ \begin{columns} \begin{column}{0.5\textwidth} \begin{itemize} \item $\pi_1$ no es hiperplano de separación \item $\pi_2$ es hiperplano de separación con margen pequeño \item $\pi_3$ es el hiperplano de separación con margen máximo \end{itemize} \end{column} \begin{column}{0.5\textwidth} \begin{center} \includegraphics[width=.9\textwidth]{hiperplano-optimo.pdf} \end{center} \end{column} \end{columns} \end{frame} \begin{frame}{\mvs} %\begin{Large} { \textcolor{red} {Hiperplano óptimo} }\end{Large}\\[2ex] \sub{Hiperplano óptimo} Es el hiperplano de separación con margen máximo. El problema se puede plantear como la búsqueda del hiperplano óptimo de separación, es decir, $$ \text{Maximizar } M $$ %$$ \text{sujeto a} $$ $$ y_i\cdot \frac{\langle\vec w,\vec x_i\rangle+b} { \|\vec{w}\|} \geq M \qquad\forall i=1,...,n$$ Si $$y_j\cdot \frac{\langle\vec w,\vec x_j\rangle+b} { \|\vec{w}\|} = M$$ entonces $\vec x_j$ es un \textbf{vector soporte}. \end{frame} \begin{frame}{\mvs} %\begin{Large} { \textcolor{red} {Hiperplano óptimo} }\end{Large}\\[2ex] Como solamente interviene la dirección de $\vec w$ y no su norma, se puede imponer la condición $$M \cdot \Vert \vec w\Vert=1 \Longleftrightarrow M=\frac1{\Vert\vec w\Vert}$$ $$ \begin{array}{c} \text{Maximizar } \frac1{\Vert\vec w\Vert} \\[1ex] y_i \left[ \langle \vec{w},\vec{x} \rangle +b \right] \geq 1 \end{array} \Longleftrightarrow \begin{array}{c} \text{Minimizar } \Vert\vec w\Vert \\ y_i\left[\langle\vec w,\vec x\rangle+b\right]-1\geq 0 \end{array} $$ $$ \Longleftrightarrow \begin{array}{c} \text{Minimizar } \dfrac12\Vert\vec w\Vert^2 \\[2ex] y_i\left[\langle\vec w,\vec x\rangle+b\right]-1\geq 0 \end{array} $$ \end{frame} \begin{frame}{\mvs} \begin{itemize} \item Problema de optimización cuadrática con restricciones lineales. \item Se aplican las condiciones de Karush--Kuhn--Tucker (KKT) a un \emph{problema cuadrático convexo} con restricciones lineales. \begin{itemize} \item formulación general \item función lagrangiana \item condiciones KKT y su interpretación \end{itemize} \end{itemize} \end{frame} % --------------------------------------------------- \begin{frame}{\mvs} \sub{Problema cuadrático convexo \\con restricciones lineales (general)} Sea el problema \[ \begin{aligned} \text{minimizar } & f(\v{x})=\tfrac12\,\v{x}^\top Q \v{x} + \v{c}^\top\v{x},\\[4pt] \text{sujeto a } & A\v{x} \ge \v{b}, \end{aligned} \] con $Q$ simétrica y semidefinida positiva (convexo), $A\in\mathbb{R}^{m\times n}$. \medskip \textbf{Objetivo:} encontrar $\v{x}^*$ que minimice $f$ cumpliendo las restricciones. \end{frame} % --------------------------------------------------- \begin{frame}{\mvs}\sub{Función lagrangiana} Introducimos multiplicadores $\v{\lambda}\in\mathbb{R}^m$ (uno por restricción), con $\lambda_i\ge 0$. La lagrangiana es \[ L(\v{x},\v{\lambda})=\tfrac12\,\v{x}^\top Q\v{x} + \v{c}^\top\v{x} -\v{\lambda}^\top(A\v{x}-\v{b}). \] Interpretación: se incorporan las restricciones al objetivo con pesos $\lambda_i$. \end{frame} % --------------------------------------------------- \begin{frame}{\mvs}\sub{Condiciones KKT} Un par $(\v{x}^*,\v{\lambda}^*)$ que satisfaga las siguientes condiciones es óptimo (en problemas convexos estas condiciones son necesarias y suficientes): \begin{itemize} \item {Estacionariedad:} \quad $\nabla_{\v{x}} L(\v{x}^*,\v{\lambda}^*) = 0$. \item {Factibilidad primal:} \quad $A\v{x}^* \ge \v{b}$. \item {Factibilidad dual:} \quad $\v{\lambda}^* \ge 0$. \item {Complementariedad:} \quad $\lambda_i^* (A_i\v{x}^* - b_i)=0,\quad \forall i$. \end{itemize} \medskip Aquí $A_i$ denota la $i$-ésima fila de $A$. \end{frame} % --------------------------------------------------- \begin{frame}{\mvs}\sub{Interpretación de la estacionariedad} La derivada de $L$ respecto a $\v{x}$: \[ \nabla_{\v{x}} L = Q\v{x} + \v{c} - A^\top\v{\lambda}. \] La estacionariedad exige \[ Q\v{x}^* + \v{c} - A^\top\v{\lambda}^* = \v{0}. \] Esta ecuación relaciona la solución primal $\v{x}^*$ con los multiplicadores duales. \end{frame} % --------------------------------------------------- \begin{frame}{\mvs}\sub{Interpretación de la complementariedad} La condición $\lambda_i^* (A_i\v{x}^* - b_i)=0$ implica: \begin{itemize} \item Si $\lambda_i^*>0$ entonces \(A_i\v{x}^* = b_i\) \\(la restricción está {activa}). \item Si \(A_i\v{x}^* > b_i\) entonces $\lambda_i^* = 0$ \\(la restricción tiene holgura). \end{itemize} \medskip Por tanto los $\lambda_i^*$ son ``precios sombra'': cuánto cambiaría el objetivo al relajar $b_i$ en una unidad. \end{frame} % --------------------------------------------------- \begin{frame}{\mvs}\sub {Dualidad fuerte} Definimos el problema dual como \[ \max_{\v{\lambda}\ge0}\; \inf_{\v{x}} L(\v{x},\v{\lambda}). \] Para problemas convexos con condiciones de regularidad (p. ej. Slater), existe \emph{dualidad fuerte}: el valor óptimo primal coincide con el valor óptimo dual. Esto permite resolver el problema a través del dual cuando convenga. \end{frame} % --------------------------------------------------- \begin{frame}{\mvs}\sub{Formulación primal en SVM (separable)} \[ \begin{aligned} \text{minimizar}\ & \tfrac12 \|\vec w\|^2\\[2pt] \text{sujeto a } & y_i(\langle\vec w,\vec x_i\rangle + b) \ge 1,\quad i=1,\dots,n \end{aligned} \] Es un problema cuadrático convexo con restricciones lineales en $(\vec w,b)$. \end{frame} % --------------------------------------------------- \begin{frame}{\mvs}\sub{Función lagrangiana} Multiplicadores: $\alpha_i\ge0$ (uno por punto) \[ L(\vec w,b,\v{\alpha})=\frac12\|\vec w\|^2 - \sum_{i=1}^n \alpha_i\bigl[y_i(\langle\vec w,\vec x_i\rangle + b)-1\bigr]. \] \end{frame} % --------------------------------------------------- \begin{frame}{\mvs}\sub{KKT: condiciones explícitas} {Estacionariedad:} \[ \frac{\partial L}{\partial \vec w}=0 \ \Rightarrow\ \vec w^*=\sum_{i=1}^n \alpha_i^* y_i \vec x_i \] \[ \frac{\partial L}{\partial b}=0 \ \Rightarrow\ \sum_{i=1}^n \alpha_i^* y_i = 0 \] {Factibilidad primal:} \[ y_i(\langle \vec w^*,\vec x_i\rangle + b^*) \ge 1 \] {Factibilidad dual:} \(\alpha_i^*\ge0\) {Complementariedad:} \[ \alpha_i^*\bigl[\,y_i(\langle \vec w^*,\vec x_i\rangle + b^*) - 1\,\bigr]=0,\quad \forall i \] \end{frame} % --------------------------------------------------- \begin{frame}{\mvs} % \sub {Consecuencias prácticas (SVM)} De las KKT se deduce: \begin{itemize} \item Si $y_i(\langle \vec w^*,\vec x_i\rangle + b^*)>1$ entonces $\alpha_i^*=0$ (punto estrictamente dentro del margen). \item Si $y_i(\langle \vec w^*,\vec x_i\rangle + b^*)=1$ entonces $\alpha_i^*>0$ (punto en el margen: vector soporte). % \item En el caso de margen blando (holguras), aparece el límite superior $\alpha_i\le C$ y % los puntos con $\alpha_i=C$ suelen ser mal clasificados o violan el margen. \end{itemize} \medskip Por tanto la solución se expresa como combinación lineal de \emph{pocos} vectores. \end{frame} \begin{frame}{\mvs} En la mayor parte de los problemas reales no existen hiperplanos de separación y se plantea la búsqueda de hiperplanos que verifiquen unas condiciones más suaves: $$ y_i\cdot(\langle\vec w,\vec x_i\rangle+b) \geq 1-\xi_i \quad \mbox{con }\xi_i\ge 0 \; i=1,\ldots, n $$ \begin{columns} \begin{column}{0.5\textwidth} \begin{itemize} \item Las variables $\xi_i$ se denominan de holgura y permiten la existencia de puntos mal clasificados. \item Cuando $\xi_i= 0$, es el problema anterior. \end{itemize} \end{column} \begin{column}{0.5\textwidth} \begin{center} \includegraphics[width=0.99\textwidth] {noseparables.pdf} \end{center} \end{column} \end{columns} % Gráfica conjuntos cuasi separables \end{frame} \begin{frame}{\mvs} El nuevo problema de optimización viene dado por: \[ L(\vec w,\vec{\xi}) = \frac12 \langle\vec w,\vec w\rangle + C \,\sum_{i=1}^n \xi_i \] sujeto a las restricciones \[ y_i\cdot(\langle\vec w,\vec x_i\rangle+b) + \xi_i - 1 \geq 0 ;\quad \xi_i\geq 0;\quad i=1,\ldots, n \] $C$ representa la penalización de los puntos mal clasificados. \vspace{0.3cm} Estos hiperplanos se denominan de margen blando. \end{frame} \begin{frame}{\mvs} \begin{itemize} \item La función lagrangiana del hiperplano de margen blando es: \[ L(\vec w,b,\vec{\xi},\vec\alpha, \vec{\beta}) = \] \[= \frac12 \langle\vec w,\vec w\rangle + C \sum_{i=1}^{n} \xi_i - \sum_{i=1}^n\alpha_i\left[y_i(\langle\vec w,\vec x_i\rangle+b) + \xi_i-1\right] - \sum_{i=1}^n \beta_i \xi_i \] \item Aplicando las condiciones KKT se obtiene \begin{eqnarray*} \forall\;i=1,\dots,n:\qquad\qquad \frac{\partial L}{\partial \vec w} = 0 &\Longleftrightarrow& \vec w^* = \sum_{i=1}^n\alpha_i^*\cdot y_i\cdot \vec x_i\\ \frac{\partial L}{\partial b} = 0 &\Longleftrightarrow& \sum_{i=1}^n\alpha_i^*\cdot y_i=0\\ \frac{\partial L}{\partial \xi_i} = 0 &\Longleftrightarrow& C= \alpha_i^* + \beta_i^* \\ \alpha_i^*[1-y_i(\langle\vec w^*,\vec x_i\rangle+b^*) - \xi_i^*] &=&0\\ \beta_i^* \, \xi_i^* &=&0 \end{eqnarray*} \end{itemize} \end{frame} % \begin{frame}{Máquinas de Vector Soporte} % \[ L(\vec\alpha) = \sum_{i=1}^n \alpha_i - \frac{1}{2} \sum_{i=1}^n \sum_{j=1}^n % \alpha_i \alpha_j y_i y_j \langle\vec x_i,\vec x_j\rangle \] % \vspace{0.2cm} % Se puede plantear el problema inicial en su forma dual: % \[\text{Maximizar } L(\alpha) \] % \[\sum_{i=1}^n\alpha_i\cdot y_i=0 \] % \[ 0 \le \alpha_i \leq C \qquad i=1,\dots,n\] % \vspace{0.3cm} % Una vez calculado $\alpha^*$, se obtiene % \[f(\vec x)=\sum_{i=1}^n\alpha_i^*\cdot y_i\cdot\langle\vec x, \vec x_i\rangle+b^*\] % \end{frame} \begin{frame}{\mvs} Teniendo en cuenta las condiciones que debe cumplir la solución \[ C= \alpha_i^* + \beta_i^*; \quad \beta_i^* \, \xi_i^* = 0, \quad i=1,\ldots, n \] \[\alpha_i^*[1-y_i(\langle\vec w^*,\vec x_i\rangle+b^*) - \xi_i^*]=0, \quad i=1,\ldots, n\] se pueden caracterizar los puntos $\vec{x}_i$: \begin{itemize} \item $\vec{x}_i \mbox{ no es separable } \Longleftrightarrow \xi_i^*>0 $. Por tanto $\beta_i^*=0$, $\alpha_i^* = C$ y \[ y_i(\langle\vec w^*,\vec x_i\rangle+b^*) = 1+\xi_i^* \] \item $\alpha_i^*=0$ $\Longrightarrow$ $\beta_i^*=C$, $\xi_i^*=0$ y el punto$\vec{x}_i$ es separable \item $0<\alpha_i^*0$, $\gamma>0$): \begin{itemize} \item $K(\vec{x}_1, \vec{x}_2)= \langle\vec{x}_1, \vec{x}_2\rangle$ \item $K(\vec{x}_1, \vec{x}_2)= (\lambda \langle \vec{x}_1, \vec{x}_2\rangle + \gamma)^p $ \item $K(\vec{x}_1, \vec{x}_2) = \exp(-\lambda \langle\vec{x}_1-\vec{x}_2,\vec{x}_1-\vec{x}_2\rangle) = \exp(-\lambda \|\vec{x}_1-\vec{x}_2 \|^2)$ \end{itemize} \end{frame} \begin{frame}{Máquinas de Vector Soporte} \textcolor{red}{Teorema de Moore-Aronszajn}\\ Para cualquier función $ K: \mathbb{X} \times \mathbb{X} \rightarrow \mathbb{R}$ simétrica y semidefinida positiva, existe un espacio de Hilbert (normado y completo) y una función $ \Phi: \mathbb{X} \rightarrow F$ tal que $$ K(\vec{x}, \vec{x}') = \langle \Phi(\vec{x}), \Phi(\vec{x}')\rangle$$ Este resultado permite calcular el producto escalar $ \langle \Phi(\vec{x}), \Phi(\vec{x}')\rangle$ sin necesidad de conocer la función $\Phi$. \end{frame} \begin{frame}{\mvs}\sub{Derivación del problema dual} Recordando primera condición KKT (estacionariedad): \[ \frac{\partial L}{\partial \vec w}=0 \ \Rightarrow\ \vec w^*=\sum_{i=1}^n \alpha_i^* y_i \vec x_i \] Sustituyendo $\vec w=\sum_j\alpha_j y_j\vec x_j$ en la lagrangiana \\y simplificando: \[ L(\v{\alpha})=\sum_{i=1}^n \alpha_i - \tfrac12\sum_{i,j}\alpha_i\alpha_j y_i y_j \langle\vec x_i,\vec x_j\rangle. \] Problema dual:\quad maximizar $L(\v{\alpha})$ sujeto a \[ \sum_i \alpha_i y_i = 0,\qquad \alpha_i \ge 0%\ (\text{y } \alpha_i\le C\ \text{en margen blando}). \] \end{frame} % --------------------------------------------------- \begin{frame}{\mvs} \[ L(\v{\alpha})=\sum_{i=1}^n \alpha_i - \tfrac12\sum_{i,j}\alpha_i\alpha_j y_i y_j \langle\vec x_i,\vec x_j\rangle. \] Problema dual:\quad maximizar $L(\v{\alpha})$ sujeto a \[ \sum_i \alpha_i y_i = 0,\qquad \alpha_i \ge 0%\ (\text{y } \alpha_i\le C\ \text{en margen blando}). \]{Interpretación geométrica y algorítmica}: \begin{itemize} \item El dual depende únicamente de productos escalares $\langle\vec x_i,\vec x_j\rangle$. \item Esto permite introducir un \emph{kernel} $K(\vec x_i,\vec x_j)$ y trabajar en espacios de características sin calcular $\Phi$. % \item Algoritmos (p. ej. SMO) actualizan localmente pares de $\alpha$ y explotan la estructura del dual. % \item Limitación: la matriz de Gram $K$ es $n\times n$; si $n$ es enorme se plantean aproximaciones o métodos primales. \end{itemize} \end{frame} \begin{frame}{\mvs} En el espacio de características se busca la función: \[ f(\vec{x}) = \langle \vec{w}, \Phi(\vec{x}) \rangle + b \] que en su forma dual se expresa como: \vspace{-0.2cm} \[ f(\vec{x}) = \sum_{i=1}^n \alpha_i^* \cdot y_i \cdot K(\vec{x}, \vec{x}_i) \] \vspace{0.2cm} Se resuelve mediante el siguiente problema de optimización \[ Max \sum_{i=1}^n \alpha_i - \frac{1}{2} \sum_{i=1}^n \sum_{j=1}^n \alpha_i \alpha_j y_i y_j \langle\vec x_i,\vec x_j\rangle \] \[\sum_{i=1}^n\alpha_i\cdot y_i=0 \] \[ 0 \le \alpha_i \leq C \qquad i=1,\dots,n\] \end{frame} \begin{frame}{\mvs} \sub{El problema XOR} \begin{center} \begin{tabular}{c|c|c} Caso& $(X_1, X_2)$ & Y\\ \hline 1 & $(+1, +1)$ & $-1$\\ 2 & $(-1, -1)$ & $-1$\\ 3 & $(+1, -1)$ & $+1$\\ 4 & $(-1, +1)$ & $+1$\ \end{tabular} \end{center} Para representar el producto escalar en el espacio de las características se usa el siguiente kernel polinómico: $$K(\vec{x}, \vec{x}')= (\langle \vec{x}, \vec{x}' \rangle+1)^2 $$ \end{frame} \begin{frame}{\mvs} El problema dual por resolver es: \[ \text{Maximizar}\quad \sum_{i=1}^n \alpha_i - \frac{1}{2} \sum_{i=1}^n \sum_{j=1}^n \alpha_i \cdot\alpha_j \cdot y_i \cdot y_j \cdot K(\vec{x}, \vec{x}') \] \[\sum_{i=1}^n\alpha_i\cdot y_i=0 \] \[ 0 \le \alpha_i \leq C \qquad i=1,\dots,n\] La solución de $\alpha$ es: $$\alpha^* = 0.125\quad i=1,\ldots, 4$$ La función de clasificación que se obtiene es: $$f(\vec{x})= 0.125\cdot\sum_{i=1}^{4} y_i \cdot K(\vec{x}, \vec{x}') $$ \end{frame} \begin{frame}{\mvs} En este caso se pueden obtener las funciones de transformación. \[ \langle \Phi(\vec{x}), \Phi(\vec{x}') \rangle = K(\vec{x}, \vec{x}') = (\langle \vec{x}, \vec{x}' \rangle +1)^2 = \] \[ 1+ x_1^2 (x'_1)^2 + x_2^2 (x'_2)^2 + 2 x_1 x_2 x'_1 x'_2 + 2 x_1 x'_1 + 2 x_2 x'_2 \] con \[ \Phi = (\phi_1, \phi_2, \phi_3, \phi_4, \phi_5, \phi_6) \] $$f(\vec{x})= \frac{1}{\sqrt{2}} \phi_4(\vec{x}) = x_1 x_2 $$ \end{frame} \begin{frame}{\mvs} Puntos débiles de las Máquinas de Vector Soporte\\ \begin{itemize} \item Las MVS son muy sensibles a los parámetros que intervienen en su cáculo. Es aconsejable probar con diferentes valores y analizar los resultados y su estabilidad. \item En los problemas de clasificación es preferible usar un núcleo gausiano y la función objetivo basada en el coste $C$. En este caso sólo son necesarios los parámetros $\lambda$ y $C$. Estrategias posibles de búsqueda: \begin{itemize} \item Buscar un $C$ adecuado probando con valores entre 1 y 1000, usando validación cruzada. Con el $C$ seleccionado buscar el $\lambda$ adecuado. \item Buscar simultáneamente sobre $\lambda$ y $C$, usando una malla. \end{itemize} \item Las MVS son sensibles a las unidades de las variables y es conveniente realizar una tipificación previa. \end{itemize} \end{frame} \begin{frame}[fragile] \frametitle{\mvs} La librería \verb+e1071+ de R puede usarse para aplicar las máquinas de vector soporte. \begin{verbatim} library (e1071) mvs_salida <- svm (y ~ x, datos.entrena) mvs_pred <- predict (mvs_salida, datos.prueba) ## para optimizar parámetros en una malla: tune (svm, y ~ x, data = datos.entrena, ranges = list (cost=10^(-1:3), gamma=10^(-3:0))) \end{verbatim} Por omisión, usa núcleo gausiano (radial) \\donde $\lambda$ = \verb+gamma+. \end{frame} \end{document} % --------------------------------------------------- \begin{frame}{\mvs}\sub{Derivación del problema dual} Sustituyendo $\vec w=\sum_j\alpha_j y_j\vec x_j$ en la lagrangiana \\y simplificando: \[ L(\v{\alpha})=\sum_{i=1}^n \alpha_i - \tfrac12\sum_{i,j}\alpha_i\alpha_j y_i y_j \langle\vec x_i,\vec x_j\rangle. \] Problema dual:\quad maximizar $L(\v{\alpha})$ sujeto a \[ \sum_i \alpha_i y_i = 0,\qquad \alpha_i \ge 0%\ (\text{y } \alpha_i\le C\ \text{en margen blando}). \] \end{frame} % --------------------------------------------------- \begin{frame}{Interpretación geométrica y algorítmica} \begin{itemize} \item El dual depende únicamente de productos escalares $\langle\vec x_i,\vec x_j\rangle$. \item Esto permite introducir un \emph{kernel} $K(\vec x_i,\vec x_j)$ y trabajar en espacios de características sin calcular $\Phi$. \item Algoritmos (p. ej. SMO) actualizan localmente pares de $\alpha$ y explotan la estructura del dual. \item Limitación: la matriz de Gram $K$ es $n\times n$; si $n$ es enorme se plantean aproximaciones o métodos primales. \end{itemize} \end{frame} % --------------------------------------------------- \begin{frame}{Ejemplo esquemático (pasos para resolver)} \begin{enumerate} \item Formule primal y Lagrangiana. \item Obtenga condiciones de estación: exprese $\vec w$ y demás variables primales con $\alpha$. \item Sustituya en $L$ y obtenga $L(\alpha)$ (forma dual). \item Resuelva el problema cuadrático convexo dual (restricciones lineales simples). \item Recupere $\vec w^*$ y $b^*$ usando KKT (promedio sobre vectores soporte suele usarse para $b^*$). \end{enumerate} \end{frame} % --------------------------------------------------- \begin{frame}{Observaciones y buenas prácticas} \begin{itemize} \item Verifique condiciones de regularidad (p. ej. Slater) para garantizar dualidad fuerte. \item Use KKT para identificar vectores soporte y entender sensibilidad respecto.\ a $C$. \item En implementaciones numéricas, cuide tolerancias: por ejemplo, considere $\alpha_i> \varepsilon$ en vez de $>0$. \item Para problemas grandes, compare resolver primal (métodos de primer orden) vs. dual (SMO, QP). \end{itemize} \end{frame} % --------------------------------------------------- \begin{frame}{Resumen rápido} \begin{itemize} \item KKT = estacionariedad + factibilidad primal + factibilidad dual + complementariedad. \item En SVM permiten pasar del problema primal (en $\vec w$) a un dual en $\alpha_i$, facilitar el uso de kernels y mostrar que la frontera depende solo de los vectores soporte. \item Matemáticamente, en problemas convexos KKT caracterizan la solución óptima. \end{itemize} \end{frame} % --------------------------------------------------- % \begin{frame}{¿Quieres un ejemplo numérico resuelto?} % Si quieres, puedo añadir una transparencia con un ejemplo numérico concreto (p.\,ej. 3 puntos en 2D) % y resolverlo paso a paso aplicando KKT y obteniendo $\vec w$, $b$ y $\alpha_i$. % ¿Te interesa ese ejemplo? % \end{frame} %\end{document} %%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}{\mvs} \begin{itemize} \item Problema de optimización cuadrática con restricciones lineales. \item La función lagrangiana es \[ L(\vec w,b,\vec\alpha) = \frac12 \langle\vec w,\vec w\rangle-\sum_{i=1}^n\alpha_i\left[y_i(\langle\vec w,\vec x_i\rangle+b)-1\right] \] \item Aplicando las condiciones de Karush-Kuhn-Tucker se obtiene \[\frac{\partial L}{\partial \vec w} = 0 \Longleftrightarrow \vec w^* = \sum_{i=1}^n\alpha_i^*\cdot y_i\cdot \vec x_i\qquad i=1,\dots,n \] \[\frac{\partial L}{\partial b} = 0 \Longleftrightarrow \sum_{i=1}^n\alpha_i^*\cdot y_i=0\qquad i=1,\dots,n \] \[\alpha_i^*[1-y_i(\langle\vec w^*,\vec x_i\rangle+b^*)]=0\] \end{itemize} \end{frame} \begin{frame}{\mvs} Se puede plantear el problema inicial en su forma dual: \[ L(\vec\alpha) = \sum_{i=1}^n \alpha_i - \frac{1}{2} \sum_{i=1}^n \sum_{j=1}^n \alpha_i \alpha_j y_i y_j \langle\vec x_i,\vec x_j\rangle \] \vspace{0.2cm} \[\text{Maximizar } L(\alpha) \] \[\sum_{i=1}^n\alpha_i\cdot y_i=0 \] \[\alpha_i\geq0\qquad i=1,\dots,n\] Una vez calculado $\alpha^*$, se obtiene \[f(\vec x)=\sum_{i=1}^n\alpha_i^*\cdot y_i\cdot\langle\vec x, \vec x_i\rangle+b^*\] \end{frame} \begin{frame}{\mvs} Analizando la condición \[{\alpha_i^*}\cdot (1- y_i\cdot \langle\vec w^*,\vec x_i\rangle+b^*) =0\] \begin{itemize} \item $\alpha_i^*>0 \Longleftrightarrow 1=y_i\cdot(\langle\vec w^*,\vec x_i\rangle+b^*)$ \\ que corresponde a los vectores soporte $\vec x_{\text{vs}} $ $$b^*=y_{\text{vs}}-\langle\vec w^*,\vec x_{\text{vs}} \rangle$$ \item $\alpha_i^*=0$ : el punto $\vec x_i$ no interviene en el hiperplano óptimo \end{itemize} \vspace{0.4cm} En la práctica, $b^*$ se estima con todos los vectores soporte: $$ b^* = \frac{1}{N_{\text{vs}}} \sum_{k=1}^{N_{\text{vs}}} (y_{\text{vs}}-\langle\vec w^*,\vec x_{\text{vs}} \rangle)$$ \end{frame}