\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^*<C  \Longleftrightarrow \beta_i^* \neq 0 \Longleftrightarrow \xi_i^*= 0$.
  Por lo tanto 
 \[ y_i(\langle\vec w^*,\vec x_i\rangle+b^*) =1 \]
 es decir, $\vec{x}_i$ es un vector soporte y permite estimar $b^*$  
 \[ b^* = \frac{1}{N_{\text{vs}}} \sum_{k=1}^{N_{\text{vs}}} (y_k - \langle\vec w^*,\vec x_k \rangle) \]
 \end{itemize}

\end{frame}



\begin{frame}{\mvs}
  \begin{itemize}\item
  Cuando las clases no son separables se plantea ``pasar'' los datos a
  un espacio de dimensión mayor en el que se cumpla la condición de
  separabilidad.

$$
\begin{array}{rcl}
  \Phi:  \mathbb{X} & \to &  F\\
  \vec{x} & \mapsto & \Phi(\vec{x}) = \bigl(\phi_1(\vec{x}), \ldots, \phi_m(\vec{x})\bigr)
\end{array}
$$
donde alguna de las funciones $\phi_j$ no es lineal.

\item
El espacio transformado se denomina \emph{espacio de características}.

\item
El objetivo es buscar el hiperplano óptimo, en el espacio de
características, que produce una frontera no lineal en el espacio
inicial.
\end{itemize}
\end{frame}
\begin{frame}{\mvs}
\begin{center}
 \includegraphics[width=\textwidth]{nucleo-paraboloide.png}
 
 Transformación (núcleo): \((a, b) \rightarrow (a,b,a^2+b^2)  \)
\end{center}
\end{frame}

\begin{frame}{\mvs}
\sub{Funciones Núcleo}

Sea $K$ una función $ K: \mathbb{X} \times \mathbb{X} \rightarrow  \mathbb{R}$\\
que verifica las condiciones 

\begin{enumerate}
 \item $K(\vec{x}_1, \vec{x}_2)=  K(\vec{x}_2, \vec{x}_1)$ (simétrica)
 \item $K(\vec{x}, \vec{x}) \ge 0$ (semidefinida positiva)
\end{enumerate}

Algunos ejemplos de funciones núcleo ($\lambda>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}
