%\documentclass[portrait,semhelv,semrot,8pt,epsf,side,psfig]{seminar}
%\usepackage{amsmath,amsthm,amssymb,epsfig}
%\usepackage{geometry}
%\slideframe{none}
%\rotateheaderstrue
%\begin{document}

\documentclass[semhelv,semcolor,11pt,slidesonly,amsmath,theorem,amssymb]{seminar}
\renewcommand{\ttdefault}{cmtt}
\slideframe{none}
\usepackage{amsbsy}
\usepackage{alltt}
\usepackage{amsmath}
\usepackage{epsf}
\usepackage{graphicx}
\special{papersize=11in,8.5in}
\graphicspath{{figs/}}
\DeclareGraphicsExtensions{.eps,.ps}
\DeclareGraphicsRule{*}{eps}{*}{}
\setkeys{Gin}{width=\textwidth}
\newenvironment{Example}%
{\begin{list}{}{\setlength{\leftmargin}{.5\parindent}}%
  \scriptsize%
  \item\begin{alltt}}%
    {\end{alltt}\end{list}}
\newcommand{\Ti}[1]{\centerline{\textbf{\large\blue #1}}}
\newcommand{\mg}[1]{{\magenta #1}}
\newcommand{\splus}{\emph{S-PLUS}}
\newcommand{\code}[1]{\texttt{\small #1}}
\newcommand{\abs}{\operatorname{abs}}
\newcommand{\E}{\mbox{\rm E}}
\newcommand{\HO}{{\rm H_0\!\!:\:}}
\newcommand{\Ha}{{\rm H_1\!\!:\:}}
\newcommand{\HA}{{\rm H_A\!\!:\:}}
\newcommand{\var}{\mbox{\rm Var}}
\newcommand{\se}{\mbox{\rm se}}
\newcommand{\bzero}{{\boldsymbol 0}}
\newcommand{\bb}{{\boldsymbol b}}
\newcommand{\bc}{{\boldsymbol c}}
\newcommand{\beps}{{\boldsymbol\epsilon}}
\newcommand{\bdelta}{{\boldsymbol\delta}}
\newcommand{\bDelta}{{\boldsymbol\Delta}}
\newcommand{\bbeta}{{\boldsymbol\beta}}
\newcommand{\btheta}{{\boldsymbol\theta}}
\newcommand{\bu}{{\boldsymbol u}}
\newcommand{\bw}{{\boldsymbol w}}
\newcommand{\bx}{{\boldsymbol x}}
\newcommand{\by}{{\boldsymbol y}}
\newcommand{\bA}{{\boldsymbol A}}
\newcommand{\bD}{{\boldsymbol D}}
\newcommand{\bI}{{\boldsymbol I}}
\newcommand{\bQ}{{\boldsymbol Q}}
\newcommand{\bR}{{\boldsymbol R}}
\newcommand{\bSigma}{{\boldsymbol\Sigma}}
\newcommand{\bX}{{\boldsymbol X}}
\newcommand{\bY}{{\boldsymbol Y}}
\newcommand{\bzer}{{\boldsymbol 0}}
\newcommand{\bZ}{{\boldsymbol Z}}
\newcommand{\bm}[1]{{\boldsymbol {#1}}}
\newcommand{\gaus}{\mathcal{N}}
\newcommand{\trans}{^T}
\newcommand{\hb}{\hat{\bm{\beta}}}

\newpagestyle{verbose}%
{\sl GACV for SVMs \hfil 06/29/2000}
{\hfil\thepage\hfil}
\pagestyle{verbose}
\def\beqr{\begin{eqnarray}}             %\bqr
\def\eeqr{\end{eqnarray}}               %\eqr
\def\bc{\begin{center}}                 %\bc
\def\ec{\end{center}}                   %\ec

\def\mb{\mbox}                          %\mb
\def\smn{\sum_{i=1}^n}                  %\s1n
\def\bfs{\mathcal S}
\def\bfh{\mathcal H}
\def\bfk{\mathcal K}
\def\bft{\mathcal T}
\def\bfhk{\mathcal{H}_K}

\begin{document}

% 1 ==================================================================
\begin{slide}{}
\begin{center}
{\Huge\blue Generalized Approximate Cross Validation for Support Vector Machines}\\[4ex]
\emph{\Large\mg{Hao Zhang}}\\[1.5ex]
\end{center}
\end{slide}
% 2 ==================================================================
\begin{slide}
\Ti{Outlines}
\begin{enumerate}
\item Introduction
\item Support Vector Machines
\begin{itemize}
\item Linear Support Vector Machines
\item Nonlinear Support Vector Machines
\item Formulation of SVMs in the Regularization Theory
\end{itemize}
\item GACV for SVMs
\item Simulations
\item Current and Future Study
\begin{itemize}
\item Variable Selection via Basis Pursuit with $L_1$ penalty
\item Examples
\end{itemize}  
\end{enumerate}
\end{slide}
% 3 ==================================================================
\begin{slide}
\begin{center}
\Ti{Introduction}
\end{center}

\begin{itemize}
\item Classification Problem:

Given a training set of $n$ examples $(x_1,y_1), \dots, (x_n, y_n)$,
where the explanatory vector $x_i \in R^d, y_i \in \{ +1, -1 \}$ for 
each $i$. The examples are i.i.d from the same distribution $P(x,y)$
as the target population. Need to decide a classification rule 
$\phi: R^d \rightarrow \{ \pm 1 \}$,  such that $\phi$ will correctly 
classify unseen examples from the same $P(x,y)$. Or the expected 
misclassification rate (EMR) is minimized: 
\begin{center}
$\mb{EMR} [\phi] = \frac{1}{2} E |\phi(X)-Y| = \int \frac{1}{2} |\phi(x)-y| dP(x,y)$  
\end{center}

\item Task:

$P(x,y)$ is usually unknown. Need to `` learn'' classification rules from the data. 
\end{itemize}
\end{slide}
% 4 ==================================================================
\begin{slide}
\begin{center}
\Ti{Linear Support Vector Machines}
\end{center}
\begin{itemize}
\item{Linear Separable Case}

Need to find a hyperplane $f(x) \equiv \omega \cdot x + b = 0$, which 
separates the positive from the negative examples correctly, with the 
largest margin. This results in the hard margin linear SVMs: 
\beqr
\underset{\omega,b}{\mb{minimize}}  & &  ||\omega||^2 \nonumber  \\
\mb{subject} & \mb{to} &  \omega \cdot x_i + b \ge +1 
~~ \mb{for} ~~ y_i = +1 \label{lsvm1} \\
&&  \omega \cdot x_i + b \le -1
~~ \mb{for} ~~ y_i = -1. \label{lsvm2}
\eeqr
Classification rule: 
\begin{center}
$\mb{sign} ~ (\omega \cdot x + b )$
\end{center}
\end{itemize}
\end{slide}
% 5 ==================================================================
\begin{slide}
\begin{itemize}
\item{Non-Separable Case}

Relax the constraints ($\ref{lsvm1}$) and ($\ref{lsvm2}$) by introducing 
positive slack variables $\xi_i, i = 1, \dots, n$.  This amounts to the 
soft margin linear SVMs:
\beqr
\underset{\omega, b, \xi}{\mb{minimize}} &&  \frac{1}{n} ~ (\smn \xi_i) ~  + ~ 
\lambda ~ ||\omega||^2  \nonumber \\
\mb{subject} & \mb{to} & \omega \cdot x_i  + b \ge + 1 - \xi_i 
~~ \mb{for} ~~ y_i = +1 \label{lsvm3}\\
&&  \omega \cdot  x_i + b \le - 1 + \xi_i  
~~ \mb{for} ~~ y_i = -1 \label{lsvm4}\\
&&  \xi_i \ge 0 ~~ \forall i. \label{xi1}
\eeqr
\begin{itemize}
\item If an error occurs, the corresponding $\xi_i$ must exceed unity. 
$\sum_{i=1}^n \xi_i$ is an upper bound on the number of training 
errors.
\item $\lambda$ is a regularization parameter, controlling a trade-off 
between the largest margin and the lowest number of errors. A small 
$\lambda$ corresponds to assigning a high penalty to errors.  
\end{itemize}
\end{itemize}
\end{slide}
% 6 ==================================================================
\begin{slide}
\begin{center}
\Ti{Nonlinear Support Vector Machines}
\end{center}
\begin{itemize}
\item Nonlinear separating is realized by mapping the input points into a 
high dimensional (often infinite dimensional) {\em feature space} $\bfh$ 
using a map $\Phi : R^d \rightarrow \bfh $, and applying the linear SVMs 
in $\bfh$.

\item Training procedure would only depend on the data through 
dot products $\Phi(x_i) \cdot \Phi(x_j)$ in $\bfh$. Constructing $\Phi$ and 
evaluating the inner product can be very time consuming. If there is a 
``kernel function'' $K$ such that $K(x_i, x_j) = \Phi(x_i) \cdot \Phi(x_j)$, 
then full knowledge of $\Phi$ is not necessary.

\item Examples:\\
Gaussian Kernel:
$ ~~~~~ K(\mathbf{x_i}, \mathbf{x_j}) =
 e^{-||\mathbf{x}_i-\mathbf{x}_j||^2/{2\sigma^2}}$\\
Polynomial Kernel:
$ ~~~ K(\mathbf{x_i}, \mathbf{x_j}) =
(1 + \mathbf{x}_i\cdot \mathbf{x}_j)^d$

\end{itemize}
\end{slide}
% 7 ==================================================================
\begin{slide}
\begin{center}
\Ti{Equivalent Variational Problem}
\end{center}

A nonlinear support vector machine with kernel $K$ is equivalent
to a variational problem in the reproducing kernel Hilbert space (RKHS)
$\bfhk$. By defining $f_i = \Phi(x_i) \cdot \omega + b $, the 
combination of ($\ref{lsvm3}$), ($\ref{lsvm4}$) and ($\ref{xi1}$) is
\beqr
\xi_i &\ge & \mb{max} ~ \{ ~  0,  ~~ 1 - y_i (\Phi(x_i) \cdot \omega + b) ~ \} \nonumber\\
    & \ge & ( ~ 1 - y_i ~ (\Phi(x_i) \cdot \omega + b) ~ )_+ \nonumber\\
    & \ge & ( ~ 1 - y_i f_i ~ )_+ ~ . 
\eeqr
Thus the classical SVMs paradigm is equivalent to: Find $f_\lambda(x)$ 
of the form $h(x) + b$, where $h(x) \in \bfhk, b \in R$,  to minimize
\begin{equation}
\frac{1}{n} ~ \smn ~ (1 - y_i f_i)_+ ~ + ~ \lambda ~ ||h||^2_{\bfhk} ~.
\label{reg}
\end{equation}
\end{slide}
% 8 ==================================================================
\begin{slide}
\begin{itemize}
\item The {\em Representer theorem (Kimeldorf and Wahba 1971)} guarantees 
that $h(\cdot) = \smn c_i K(x_i, \cdot)$, thus
$f(x) = b + \smn c_i K(x_i, x)$. In other words, the minimizer of 
($\ref{reg}$) lies in a finite dimensional space, even when the minimization
is carried out in an infinite dimensional RKHS. 

\item The well-known ``reproducing property'' gives the inner product in 
$\bfhk$ of two representers as 
$< ~ K(x_i, \cdot), K(x_j, \cdot) ~ >_{\bfhk} = K(x_i, x_j)$. 
Thus $||h||^2_{\bfhk} = \sum_{i,j=1}^n ~ c_i c_j K(x_i, x_j)$. 

\item Using notations $e = (1, \dots, 1)'$, $ c = (c_1, \dots, c_n)'$ and 
$f = (f_1, \dots, f_n)'$, we have $f = K ~ c + e ~ b$.  The variational 
problem ($\ref{reg}$) becomes finding $(c,b)$ to minimize
\begin{equation}
\frac{1}{n} ~ \smn ~ (1 - y_i f_i)_+ ~ + ~ \lambda ~ c'Kc.
\label{quar}
\end{equation}
\end{itemize}
\end{slide}
% 9 ==================================================================
\begin{slide}
\begin{center}
\Ti{Lagrangian Formulation and Dual Problem}
\end{center}
\begin{itemize}
\item Introducing a new vector $z = (z_1, \dots, z_n)$, $(\ref{quar})$ becomes (QP):
\beqr
\underset{c,b,z}{\mb{minimize}} &&  n \lambda ~ c'Kc + e'z \nonumber\\
\mb{subject} & \mb{to} ~~ & z ~ \ge ~  0 \label{con1}\\
&& z ~ \ge ~ e - Y K c - Y ~ e ~ b. \label{con2} 
\label{qp}
\eeqr

\item Using positive Lagrange multipliers $\{ ~ r_i, \alpha_i ~ \}, i = 1, \dots, n$, 
one for each of the inequality constraints, we get the Lagrangian:
\begin{equation}
L_P(c, b, z, r, \alpha) \equiv  n \lambda c'Kc + e'z -  
\smn r_i z_i + \smn \alpha_i ( 1 - y_i f_i - z_i ).  
\end{equation}
\end{itemize}
\end{slide}
%10 =================================================================
\begin{slide}
\begin{itemize}

\item $L_P$ must be minimized with respect to the primal variables 
$c,b,z$ and simultaneously maximized with respect to the dual 
variables $r$ and  $\alpha$ (i.e. a saddle point has to be 
found), subject to $r > 0, \alpha> 0$. Let $H = \frac{1}{2 n \lambda} ~ Y K Y$. 
This finally leads to Wolfe dual problem: 
\beqr
\underset{\alpha}{\mb{maximize}} && 
 - \frac{1}{2} ~ \alpha' H \alpha + e'\alpha \nonumber \\
\mb{subject} & \mb{to} ~~ & 0 ~ \le ~ 
 \alpha ~ \le ~ 1 \nonumber \\
&& e' Y  \alpha = y' \alpha = 0. \label{dual} 
\eeqr

\item Once ($\ref{dual}$) is solved, $c$ is obtained from the equation 
$c = \frac{1}{2 n \lambda} ~ Y \alpha$.  The constant $b$ is implicitly 
determined and can be easily found using the Karush-Kuhn-Tucker (KKT) conditions:
\begin{equation}
b = \displaystyle{\frac{\smn ~ \alpha_i ~ (1-\alpha_i) ~
(y_i - \sum_{j=1}^n ~ c_j K(x_i, x_j))}
{\smn ~ \alpha_i ~ (1-\alpha_i)}} ~ .
\end{equation}
\end{itemize}
\end{slide}
% 11 ==================================================================
\begin{slide}
\begin{center}
\Ti{Bayes' Rule}
\end{center}
For any classification rule $\phi: ~ R^d \rightarrow \{ \pm 1\}$, its EMR 
is reexpressed as:
\beqr
\mb{EMR} [\phi] & = & \frac{1}{2} ~ E |Y - \phi(X)| ~ = ~ \frac{1}{2} ~ E [ 1 - Y \phi(X) ]_+  
\label{emr} \\
& = & E [ (1 - p(X)) I_{\phi(x) = 1} + p(X) I_{\phi(x) = -1} ].
\label{expec}
\eeqr
If we knew the true probability $p(x)$, we would be able to identify the 
optimal rule which minimizes ($\ref{expec}$). It is Bayes' rule:
\beqr
\phi_B (x)  & = & +1, ~~ \mb{if} ~ \frac{p(x)}{1-p(x)} > 1 \nonumber \\
& = & -1, ~~ \mb{otherwise}. \nonumber
\eeqr
Lin (1999) shows that SVMs with appropriately chosen smoothing parameter 
$\lambda$ approximately implement Bayes' rule.
\end{slide}
% 12 ==================================================================
\begin{slide}
\begin{center}
\Ti{Generalized Comparative Kullback-Liebler Distance}
\end{center}
\begin{itemize}
\item 
For a general function $f: ~ R^d \rightarrow R$, its expected 
misclassification rate is naturally defined as
\beqr
E  ~ [ ~ (1 - p(X)) ~ I_{f(x) > 0} ~ + ~  p(X) ~ I_{f(x) < 0} ~ ].
\label{gemr1}
\eeqr
It can be reexpressed as
\begin{equation}
E[|Y-\mb{sign}(f(X))|/2] =  E[1-Y \mb{sign}(f(X))]_+ /2
\end{equation}
We call $\mb{E}~[ 1 - Y f(X) ]_+$ the generalized comparative 
Kullback Leibler (GCKL) distance. Since the GCKL is continuous and 
convex in $f$, it usually has unique minimum; However the EMR is 
discontinuous and not convex in $f$, thus it has several local 
minima. That is why we aim to minimize the GCKL rather than the 
EMR in practice.
\end{itemize}
\end{slide}
% 13 ============================================================
\begin{slide}
\begin{itemize}
\item The sampling version for GCKL is 
\begin{equation}
\mb{GCKL}(p_{true}, f_\lambda) \doteq GCKL(\lambda) = 
E_{true} \frac{1}{n} \smn ~ (1 - y_i f_{\lambda i})_+ .\nonumber
\end{equation}
\item Actually GCKL is an {\em upper bound} for the EMR, since
\beqr
E_{true} (1 - y_i f_{\lambda i})_+ & = &
 p_{[true]i} (1 - f_{\lambda i}), ~~~~~~~~ \mb{if} ~ 
 f_{\lambda i} < -1 \nonumber \\
& = & 1 + (1 - 2 p_{[true]i}) f_{\lambda i}, ~~~ \mb{if} ~ 
 -1 \le f_{\lambda i} \le 1 \nonumber \\
& = & (1 -  p_{[true]i}) (1 + f_{\lambda i}), ~~ \mb{if} ~ 
 f_{\lambda i} > 1. \nonumber
\eeqr
\item Wahba, Lin and Zhang (1999) proposed to find the value $\lambda$ so 
that the solution $f_\lambda$ of ($\ref{reg}$) minimizes GCKL. 
Heuristically, as $f_\lambda$ tends to $\mb{sign}(p(x)  - \frac{1}{2})$, 
the GCKL tends to two times EMR. Thus, when $f_\lambda$ is close
to $\mb{sign}(p(x)  - \frac{1}{2})$, minimizing the GCKL is equivalent to 
minimizing the EMR.
\end{itemize}
\end{slide}
% 14 =================================================================
\begin{slide}
\begin{center}
\Ti{Generalized Approximate Cross-Validation Function}
\end{center}
Without knowledge of $p(x)$, there is no way to compute GCKL. The
proposed GACV is a calculable proxy of $GCKL$.
\begin{itemize}
\item Ordinary Cross Validation Function (CV)
\begin{equation}
CV(\lambda) = \frac{1}{n} \smn ~ ( 1 - y_i f_{\lambda i}^{[-i]} ~ )_+  
\end{equation}
Since $f_{\lambda i}^{[-i]}$
does not depend on $y_i$ but is presumably on average close to
$f_{\lambda i}$, we may consider $CV(\lambda)$ as a proxy for
$GCKL(\lambda)$. For any fixed $\lambda$, in order to evaluate 
$CV(\lambda)$, we have to get $n$ leaving-out-one estimates 
${f_{\lambda i}}^{[-i]}$ for $i = 1, \dots, n$, which in general
is very expensive to compute.
\end{itemize}
\end{slide}
% 15 ================================================================
\begin{slide}
\beqr
D(\lambda) & = & \frac{1}{n} \smn ~ [ ~ 
( 1 ~ - y_i f_{\lambda i}^{[-i]})_+ - 
(1 - y_i f_{\lambda i})_+ ~ ] \\
OBS(\lambda) & = & \frac{1}{n} \smn ~ (1 - y_i f_{\lambda i})_+ .
\eeqr
The approximation of CV is GACV,  which is a reasonable proxy for $GCKL(\lambda)$:
\begin{equation}
GACV(\lambda) = \frac{1}{n} \smn ~ (1 - y_i f_{\lambda i})_+ ~ 
+ ~ \hat{D}(\lambda),
\end{equation}
where
\begin{equation}
\hat{D}(\lambda)=\frac{1}{n}[2\sum_{y_i f_{\lambda_i} < -1} 
\frac{\alpha_{\lambda_i}}{2n\lambda}||K(x_i,\cdot)||^2_{\bfhk} + 
\sum_{y_if_{\lambda_i}\in [-1,1]} 
\frac{\alpha_{\lambda_i}}{2n\lambda}||K(x_i,\cdot)||^2_{\bfhk}]
\end{equation}
\end{slide}
% 16 ================================================================

\end{document}







