\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{Bosques Aleatorios}
%\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.

La búsqueda de un hiperplano óptimo se puede plantear de la siguiente forma:
$$ \text{Maximizar } M  $$
%$$ \text{sujeto a} $$
$$ y_i\cdot(\langle\vec w,\vec x\rangle+b) \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]\geq1
\end{array}
\Longleftrightarrow
\begin{array}{c}
\text{Minimizar } \Vert\vec w\Vert \\
y_i\left[\langle\vec w,\vec x\rangle+b\right]-1\geq10
\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}
 Se puede plantear el problema inicial en su forma dual:
 \[\text{Maximizar } L(\vec\alpha)\]
 \[\sum_{i=1}^n\alpha_i\cdot y_i=0\qquad\alpha_i\geq0\qquad i=1,\dots,n\]
 \[\not\!\!{\alpha_i} - \alpha_i\cdot y_i\cdot\langle\vec w^*,\vec x_i\rangle+b^*=0\]
 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}
 Si $\alpha_i>0$, 
 \[1=y_i\cdot(\langle\vec w^*,\vec x_i\rangle+b^*)\]
 que corresponde con los vectores soporte
 \[y_i={}\Longleftrightarrowy_i=\langle\vec w^*,\vec x_i\rangle+b^*\Longleftrightarrow b^*=y-\langle\vec w^*,\vec x_i\rangle\]
\end{frame}


\end{document}

