\documentclass{beamer}%
%\usepackage{pgf}%
\usepackage[latin1]{inputenc}%
\usepackage[spanish]{babel}%
\usepackage{graphicx}
\usepackage{beamerthemesplit}
\spanishdecimal{.}
%\usepackage{shortvrb}%
\newcommand{\fuentePie}{\fontsize{5pt}{4pt}\selectfont}%
 
\newcommand{\subtitulo}{\colorbox{white}{\parbox{60mm}{\centering \textcolor{red}{Grado en Matemáticas}}}}
 
\title{Máquinas de Vector Soporte}
%\subtitle{\textcolor{red}{Grado en Física y Grado en Matemáticas}}
%\subtitle[]{\colorbox{white}{\parbox{60mm}{\centering \textcolor{red}{Grado en Matemáticas}}}}
%\author{}
\pgfdeclareimage[width=1.0cm]{escudo}{/home/norberto/charlasInstitutos/escudoAC}
\titlegraphic{\pgfuseimage{escudo}}
\institute{.\\[0pt]\vspace*{-10mm}%
%  \includegraphics[width=65mm]{/home/norberto/charlasInstitutos/fcPanoramica1.jpg}\\
 \parbox[b][14mm][b]{40mm}{Facultad de Ciencias\\ C/ Federico García Lorca, 18\\33007\, -\, OVIEDO \\ \textcolor{blue}{\url{http://ciencias.uniovi.es }}}\\[-3mm]}
\date{\footnotesize Junio de 2017\\[-3mm]}
%\hypersetup{
%    bookmarks=false,         % show bookmarks bar?
%    pdfauthor={Norberto Corral y Tomás Aranda}%,    % author
%}

\begin{document}


\begin{frame} {Máquinas de Vector Soporte}

 \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 = \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} | f(\vec{x}) =0\, \}$$
 
  \vspace{0.4cm}
  
Cualquier hiperplano de $ \mathbb{R}^2$  define una recta
\end{frame}



\begin{frame} {Máquinas de Vector Soporte}


El vector $\vec{w}$ es ortogonal a todos los puntos del hiperplano

\vspace{0.3cm}
La distancia entre un hiperplano $\pi$ y un punto $\vec{x} \in \mathbb{R}^p$ viene dada por la expresión:

$$ dist(\pi, \vec{x} )= \frac{f(\vec{x})} {||\vec{w}||} \qquad \mbox{con}\qquad ||\vec{w}||= \sqrt{\sum_{j=1}^{p} w_j^2 }$$  

\begin{center}
% \includegraphics[width=4cm] {/home/norberto/carleos/mvs/distancia.pdf}
 \includegraphics[width=4cm] {/home/norberto/norberto/Maquinas_Vector_Soporte/distancia.pdf}
\end{center}

\end{frame}



\begin{frame} {Máquinas de Vector Soporte}

\begin{Large} { \textcolor{red}  {Conjunto linealmente separable} }\end{Large}

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} {Máquinas de Vector Soporte}
\begin{center}
% \includegraphics[width=5cm] {/home/norberto/carleos/mvs/hiperplanos.pdf}
 \includegraphics[width=4cm] {/home/norberto/norberto/Maquinas_Vector_Soporte/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}) = signo (f(\vec{x}))$$
\end{frame}


\begin{frame} {Máquinas de Vector Soporte}

\begin{Large} { \textcolor{red}  {Margen de un hiperplano de sepación} }\end{Large}

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 \vec w ' \cdot\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) $$

\vspace{0.1cm}
\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]{/home/norberto/carleos/mvs/hiperplano-optimo.pdf}
     \includegraphics[width=4cm] {/home/norberto/norberto/Maquinas_Vector_Soporte/hiperplano-optimo.pdf}
     \end{center}
\end{column}
\end{columns}

\end{frame}



\begin{frame}{Máquinas de Vector Soporte}
\begin{Large} { \textcolor{red}  {Hiperplano óptimo} }\end{Large}

Es el hiperplano de separación con margen máximo.

El problema se puede plantear como la búsqueda del hiperplano óptimo deseparación, es decir, :
$$ \text{Maximizar } M  $$
%$$ \text{sujeto a} $$
$$ y_i\cdot \frac{\langle\vec w,\vec x\rangle+b} { ||\vec{w}||} \geq M $$

Imponiendo 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}
$$
 
\end{frame}


\begin{frame}{Máquinas de Vector Soporte}
 \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}{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 \] 
  \[\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}{Máquinas de Vector Soporte}
 Analizando la condición 
  \[\!{\alpha_i} - \alpha_i\cdot 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
  $$b^*=y_{vs}-\langle\vec w^*,\vec x_{vs} \rangle$$
  
 \item $\alpha_i=0$ el punto `$x_i$' no interviene en el hiperplano óptimo
 \end{itemize}
 
 \vspace{0.4cm}
 
 La estimación de $b^*$ se hace con todos los vectores soporte:
 $$ b^* = \frac{1}{N_{vs}} \sum_{k=1}^{N_{vs}} (y_{vs}-\langle\vec w^*,\vec x_{vs} \rangle)$$
\end{frame}


\begin{frame}{Máquinas de Vector Soporte}
 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}{Máquinas de Vector Soporte}

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}{Máquinas de Vector Soporte}
 \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 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 \]
  \[\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, \quad  i=1\ldots, n\]
  \[ \beta_i \, \xi_i = 0, \quad  i=1\ldots, n \]
 \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}{Máquinas de Vector Soporte}
Teniendo en cuenta las condiciones que debe cumplir la solución 
\[ 1) \; C= \alpha_i - \beta_i; \quad 2)\; \beta_i \, \xi_i = 0, \quad  i=1\ldots, n \]
\[ 3)\; \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 Si $\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 Si $\alpha_i =0$ entonces $\beta_i=C$, $\xi_i=0 \Longleftrightarrow  \vec{x}_i$ es separable
 \item Cuando $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 permiten estimar $b^*$  
 \[ b^* = \frac{1}{N_{vs}} \sum_{k=1}^{N_{vs}} (y_k - \langle\vec w^*,\vec x_k \rangle) \]
 \end{itemize}

\end{frame}



\begin{frame}{Máquinas de Vector Soporte}
 Cuando las clases no son separables se plantea ``pasar'' los datos a un espacio de dimensión
 mayor en los que se cumpla la condición de separabilidad.
 
El espacio transformado se denomina espacio de características.\\

$$ \Phi:  \mathbb{X} \rightarrow  F$$
$$ \vec{x} \rightarrow \Phi(\vec{x})= ( \phi_1(\vec{x}), \ldots, \phi_m(\vec{x}))$$
donde alguna de las funciones $\phi_j$ no es lineal.
\vspace{0.2cm}

El objetivo es buscar el hiperplano óptimo en el espacio de características, que produce una frontera no lineal en el espacio inicial.

\end{frame}
\begin{frame}{Máquinas de Vector Soporte}
\begin{center}
 \includegraphics[width=\textwidth]{nucleo-paraboloide.png}
 
 Transformación : \((a, b) \rightarrow (a,b,a^2+b^2)  \)
\end{center}

\end{frame}

\begin{frame}{Máquinas de Vector Soporte}
\textcolor{red}{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}, \vec{x}')=  K(\vec{x}', \vec{x})$ (simétrica)
 \item $K(\vec{x}, \vec{x}) \ge 0$ (semidefinida positiva)
\end{enumerate}

Algunos ejemplos de funciones núcleo:
\begin{itemize}
 \item $K(\vec{x}, \vec{x}')= \langle\vec{x}, \vec{x}'\rangle$
 \item $K(\vec{x}, \vec{x}')= (\lambda  \langle \vec{x}, \vec{x}'\rangle + \gamma)^p $
 \item $K(\vec{x}, \vec{x}')= exp(\lambda  \langle\vec{x}-\vec{x}' \rangle); \quad \lambda>0$
\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}{Máquinas de Vector Soporte}
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^* y_i 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}[fragile]
\frametitle {Máquinas de Vector Soporte}

La librería e1071 de R puede usarse para aplicar las máquinas de vector soporte.

\begin{verbatim}
mvs_salida <- svm (y ~ x, datos.entrena) 
mvs_pred   <- predict (mvs_salida, datos.prueba)
tune.svm (svm, y~x, data=datos.entrena, 
          ranges=list(cost=10^(-1:3),gamma=10^(-3:0))
\end{verbatim}
\end{frame}

\begin{frame}{Máquinad de Vector Soporte}
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 gaussiano y la función objetivo basada en el coste C; en este 
 caso sólo son necesarios los parámetors $\lambda$ y C.
 \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 SVM es sensible a las unidades de las variables y es conviente realizar una tipificación. 
\end{itemize}

 \end{frame}
\end{document}

