\documentclass[11pt]{article}
\usepackage{latexsym}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{bm}
\usepackage{epsfig}
\usepackage[tight]{subfigure}

\newcommand{\handout}[5]{
  \noindent
  \begin{center}
  \framebox{
    \vbox{
      \hbox to 5.78in { {#1} \hfill #2 }
      \vspace{4mm}
      \hbox to 5.78in { {\Large \hfill #5  \hfill} }
      \vspace{2mm}
      \hbox to 5.78in { {\em #3 \hfill #4} }
    }
  }
  \end{center}
  \vspace*{4mm}
}

\newcommand{\lecture}[5]{\handout{#1}{#2}{#3}{#4}{#5}}

\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{assumption}[theorem]{Assumption}

% 1-inch margins, from fullpage.sty by H.Partl, Version 2, Dec. 15, 1988.
\topmargin 0pt
\advance \topmargin by -\headheight
\advance \topmargin by -\headsep
\textheight 8.9in
\oddsidemargin 0pt
\evensidemargin \oddsidemargin
\marginparwidth 0.5in
\textwidth 6.5in

\parindent 0in
\parskip 1.5ex
%\renewcommand{\baselinestretch}{1.25}

\begin{document}
\newcommand{\defeq}[0]{\ensuremath{\stackrel{\triangle}{=}}}
\def\x{\mathbf{x}}
\def\w{\mathbf{w}}
\def\K{\mathbf{K}}
\lecture{Statistical Techniques in Robotics (16-831, F11)}{Lecture \#22 (Nov 30, 2011)}{Lecturer: Drew Bagnell}{Scribe: Abhinav Shrivastava$^1$}{Kernel Machines Review / Functional Gradient Descent}
\let\thefootnote\relax\footnotetext{$^1$Based on the scribe work of Varun Ramakrishna, Dave Rollinson, Daniel Munoz, Tomas Simon, Jack Singleton and Sergio Valcarcel}


\section{The Big Picture}
We have seen how to use online convex programming to learn linear functions by optimizing costs of the following form:
\begin{equation}
	L(\w) = \sum_i\underbrace{(y_i - \w^T \x_i)^2}_{loss} + \underbrace{\lambda ||\w||^2}_{regularization / prior} \nonumber
\end{equation}

We want to generalize this to learn over a space of more general functions $f: \mathbb{R}^n \rightarrow \mathbb{R}$. The high-level idea is to learn non-linear models using the same gradient-based approach used to learn linear models.

\begin{equation}
	L(f) = \sum_i(y_i - f(\x_i))^2 + \lambda ||f||^2 \nonumber
\end{equation}

Up till now we have only considered functions of the form $f(\x)=\w^T \x$, but we will now extend this to a more general space of functions.

\section{Review of Kernels}
\begin{itemize}
\item
Ultimately, we wish to learn a function $f: \mathbb{R}^n \rightarrow \mathbb{R}$ that assigns
a meaningful score given a data point.  For example, in binary classification, we would like an $f(\cdot)$ 
to return positive and negative values, given positive and negative samples, respectively.

\item
A kernel $K: \mathbb{R}^n \times \mathbb{R}^n \rightarrow \mathbb{R}$ 
intuitively measures the \textit{correlation} between $f(\mathbf{x_i})$ and $f(\mathbf{x_j})$.  Considering
a matrix $\mathbf{K}$ with entries $K_{ij} = K(\mathbf{x_i}, \mathbf{x_j})$, then matrix 
$\mathbf{K}$ must satisfy the properties:
\begin{itemize}
	\item
	$\mathbf{K}$ is symmetric ($K_{ij} = K_{ji}$)
	\item
	$\mathbf{K}$ is positive-definite 
		($\forall \mathbf{x} \in \mathbb{R}^n : \mathbf{x} \neq \mathbf{0}, \mathbf{x^T K x} > 0$)
\end{itemize}
Hence, a valid kernel is the inner product: $K_{ij} = \langle\mathbf{x_i, x_j}\rangle$.  

\item
A function can be considered that is a weighted composition of many kernels 
centered at various locations $\mathbf{x_i}$:
\begin{equation}
  \label{eq:rkhs-function}
	f(\cdot) = \sum_{i=1}^Q \alpha_i K(\mathbf{x_i}, \cdot),
\end{equation}
where $Q$ is the number of kernels that compose $f(\cdot)$ and $\alpha_i \in \mathbb{R}$ is
each kernel's associated weight.  All functions $f(\cdot)$ with kernel $K$ that satisfy the above properties and can be written in the form of Equation \ref{eq:rkhs-function} are said to lie in a \textit{Reproducing Kernel Hilbert Space} (RKHS) $\mathcal{H}_K$: $f \in \mathcal{H}_K$
\end{itemize}

However to do gradient descent on the space of such functions, we need the notion of a distance, norm and an inner product. We formalize this by introducing the Reproducing Kernel Hilbert Space.

\section{Reproducing Kernel Hilbert Space}

The Reproducing Kernel Hilbert Space (RKHS), denoted by $\mathcal{H}_k$, is the space of functions $f(\cdot)$ that can be written as $\sum_i \alpha_i k(\x_i,\cdot)$, where $k(\x_i,\x_j)$ satisfies certain properties described below.

To be able to manipulate objects in this space of functions, we will look at some key properties:
\begin{itemize}
\item
The \emph{{\bf inner product}} of $f, g \in \mathcal{H}_k$ is defined as
$$\langle f,g \rangle \defeq \sum_i \sum_j \alpha_i \beta_j k(\x_i, \x_j) = \bm{\alpha}^{\top} \mathbf{K} \bm{\beta}$$
where $f(\cdot) = \sum_i \alpha_i k(\x_i,\cdot)$, $g(\cdot) = \sum_j \beta_j k(\x_j,\cdot)$, $\bm{\alpha}$ and $\bm{\beta}$ are vectors comprising, respectively, $\alpha_i$ and $\beta_i$ components, and $\mathbf{K}$ is $n$ by $m$ (where $n$ is the number of $\x_i$ in $f$, and $m$ those in $g$) with $K_{ij}=k(\x_i, \x_j)$.

Note that this will satisfy linearity (in both arguments):
\begin{itemize}
	\item
	   $\langle \lambda f, g\rangle = \lambda \langle f,g\rangle$
	\item
	   $\langle f_1+f_2, g \rangle = \langle f_1,g\rangle + \langle f_2,g\rangle$
\end{itemize}

With this inner product, the \emph{norm} will be: $|| f ||^2 = \langle f,f \rangle = \bm{\alpha}^{\top} \mathbf{K} \bm{\alpha}$.

\item
The \emph{{\bf reproducing property}} is observed by taking the inner-product of a function with a kernel $\langle f, K(\mathbf{x^*}, \cdot)\rangle$ and functional $E$:
\begin{eqnarray*}
  E_{x^*}[f] &=& \langle f, K(\mathbf{x^*}, \cdot)\rangle \\
& = & \langle \sum_{i=1}^Q \alpha_i K(\mathbf{x_i},\cdot) , K(\cdot, \mathbf{x^*})\rangle = \sum_{i=1}^Q \alpha_i \langle K(\mathbf{x_i}, \cdot), K(\cdot, \mathbf{x^*})\rangle = \sum_{i=1}^Q \alpha_i  K(\mathbf{x_i}, \mathbf{x^*})  \\
& = & \underbrace{f(\mathbf{x^*})}_{\mbox{eval @ $x^*$}}
\end{eqnarray*}
\end{itemize}

An example of a valid kernel for $\x \in \mathbb{R}^n$ is the inner product: $k(\x_i,\x_j) = \x_i^T \x_j$. Intuitively, the kernel measures the \textit{correlation} between $\x_i$ and $\x_j$. 

A very commonly used kernel is the RBF or Radial Basis Function kernel, which takes the form $k(\x_i, \x_j)= e^{-\frac{1}{\gamma}||\x_i - \x_j||^2}$.
With this kernel in mind, a function can be considered as a weighted (by $\alpha_i$) composition of bumps (the kernels) centered at the $Q$ locations $\mathbf{x_i}$: \begin{equation}
%  \label{eq:rkhs-function}
	f(\cdot) = \sum_{i=1}^Q \alpha_i K(\x_i, \cdot), \nonumber
\end{equation}

%%%%%%%%%%%%%%%%%
\section{Loss Minimization}
Again, let us consider our cost function defined over all functions $f$ in our RKHS, as before our loss is:
\begin{equation}
	L(f) = \sum_i(y_i - f(\x_i))^2 + \lambda ||f||^2 \nonumber
\end{equation}

The purpose of $\langle f, f \rangle$ is to penalize the complexity of the solution $f$. Here it acts like the log of a gaussian prior over functions. Intuitively, the probability can be thought of as being distributed according to $P(f)=\frac{1}{Z} e^{-\frac{1}{2} \langle f,f \rangle}$ (in practice this expression doesn't work because $Z$ becomes infinite).

We want to find the best function $f$ in our RKHS so as to minimize this cost, and we will do this by moving in the direction of the negative gradient: $f - \alpha \nabla L$. To do this, we will first have to be able to express the gradient of a function of functions (ie. a \emph{functional} such as $L[f]$).

%%%%%%%%%%%%
\subsection{Functional gradient}
A gradient can be thought of as:
	\begin{itemize}
		\item
            Vector of partial derivatives
		\item
			Direction of steepest ascent
		\item
			Linear approximation of the function (or functional), ie. $f(x_0 + \epsilon) = f(x_0) + \epsilon \cdot \underbrace{\nabla f(x_0)}_{gradient}  + O(\epsilon^2)$.
	\end{itemize}
We will use the third definition. 
A \textit{functional} $E : f \rightarrow \mathbb{R}$ is a function of functions $f \in \mathcal{H}_K$.
As an example let us write the terms of our loss function from above as functionals:
	\begin{itemize}
		\item
			$E_{1}[f] = ||f||^2$
		\item
			$E_{2}[f] = (y - f(\x))^2$
		\item
			$E[f] =  \sum_i (y_i - f(\x_i))^2 + \lambda||f||^2 $
	\end{itemize}
A functional gradient $\nabla E[f]$ is defined implictly as the linear term of the change in a function due to a small perturbation $\epsilon$ in its input: $E[f + \epsilon g] = E[f] + \epsilon \langle \nabla E[f], g \rangle + O(\epsilon^2)$.

Before computing the gradients for these functionals, let us look at a few tools that will help us derive the gradient of the loss functional

\subsection {Chain rule for functional gradients}
Consider \textit{differentiable} functions $C : \mathbb{R} \rightarrow \mathbb{R}$ that are functions
of functionals $G$, $C(G[f])$.  Our cost function $L[f]$ from before was such a function, these are precisely the functions that we are interested in minimizing.


The derivative of these functions follows the chain rule:
 \begin{equation}
\nabla C(G[f]) = \frac{\partial C(G[f])}{\partial \lambda}\vert_{G(f)} \nabla G[f]
\end{equation}
	%\item
	Example: If $C = (||f||^2)^3$, then $\nabla C = 3(||f||^2)^2(2f)$

\subsection{Another useful functional gradient}

Another useful functio nthat we come across often  is the evaluation functional.
The \emph{evaluation functional} evaluates $f$ at the specified $x$: $E_x[f] = f(x)$
	\begin{itemize}
		\item
		Gradient is $\nabla E_x = K(x, \cdot)$
		\begin{eqnarray*}
			E_x[f + \epsilon g] &=& f(x) + \epsilon g(x) + 0 \\
			& = & f(x) + \epsilon \langle K(x, \cdot) , g \rangle + 0 \\
			& = & E_x[f] + \epsilon \langle \nabla E_x , g \rangle + O(\epsilon^2)
		\end{eqnarray*}
		\item It is called a \textit{linear functional} due to the lack of a multiplier on perturbation $\epsilon$.
	\end{itemize}



%%%%%%%%%%%%%
\subsection{Functional gradient of the regularized least squares loss function}

	\begin{itemize}
		\item Let's look at the functional gradient of the second term of the loss function:
		 \begin{equation}
		\nabla E[f] = \nabla ||f||^2 \\
		\end{equation}
		Expanding it out using a Taylor's series type expansion
		\begin{eqnarray*}
			E[f + \epsilon g] & = &\langle f + \epsilon g, f + \epsilon g\rangle \\
			& = & ||f|| + 2 \langle f, \epsilon g \rangle + \epsilon^ 2	||g|| \\
			& = & ||f|| + \epsilon \langle 2f , g \rangle + O(\epsilon^2)
		\end{eqnarray*}
		We observe that
		 \begin{equation}
		\nabla E[f] = \nabla ||f||^2  = 2f
		\end{equation}

	\item Now for the first term of the loss function
		 \begin{equation}
		E[f] = \sum_i (y_i - f(\x_i))^2 \\
		\end{equation}
		Using the chain rule we have
 		\begin{equation}
		\nabla E[f] = -2(y_i - f(\x_i)) \nabla(f(x_i))\\
		\end{equation}
		We observe that $\nabla(f(x_i)) $ is the functional gradient of the evaluation functional. Substituting in the gradient of the evaluaton functional as computed in the previous section we have :
		 \begin{equation}
		\nabla E[f] = -2(y_i - f(\x_i))K(\x_i, \cdot)\\
		\end{equation}
	\end{itemize}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Functional gradient descent}
\begin{itemize}
\item
Regularized least squares loss function $L[f]$
\begin{eqnarray*}
L[f] &=& (y_i - f(\x_i))^2 + \lambda ||f||^2 \\
L[f] &=& (y_i - E_{\x_i}[f])^2 + \lambda ||f||^2 \\
\nabla L[f] &=& -2(y_i - f(\x_i))K(\x_i, \cdot) + 2 \lambda f
\end{eqnarray*}

Update rule for the regularized least squares loss function:
\begin{eqnarray*}
f_{t+1} & \leftarrow & f_t - \eta_t \nabla L \\
& \leftarrow & f_t - \eta_t ( -2(y_t - f_t(\x_t))K(\x_t, \cdot) + 2 \lambda f_t) \\
& \leftarrow & f_t(1 - 2 \eta_t \lambda) + 2\eta_t (y_t - f_t(\x_t))K(\x_t, \cdot)
\end{eqnarray*}
where $\eta_t$ is the learning rate at time step $t$.

The update rule is equivalent to:
\begin{itemize}
\item Adding a kernel $K(\x_t, \cdot)$ weighted by $2\eta_t (y_t - f_t(\x_t))$.
\item Shrinking all other weights by $(1-2\eta_t \lambda)$ multiplier.
\end{itemize}
\vspace{0.1in}
\item
SVM loss function $L(f)$
\begin{equation} 
L(f(\x_t),y_t) = \max(0, 1- y_tf(\x_t)) + \lambda ||f||^2
\end{equation}
The sub-gradient $\nabla L$ has two cases.  One where the prediction is correct by margin = 1, and the other where is not correct by margin = 1 (margin error).
\begin{equation}
\nabla L((x_t),y_t) = 
\begin{cases}
    0 &$if $ (1 - y_i f(\x_i)) \leq 0 \\
    L'(f(\x_t),y_t) f'(\x_t) = -y_t K(\x_t, \cdot) & \text{else margin error}
\end{cases}
\end{equation}

The update rule is equivalent to:
\begin{itemize}
\item Adding a kernel $K(\x_t, \cdot)$ weighted by $\eta_t y_t$ in case of margin error.
\item Shrinking all other weights by $(1-2\eta_t \lambda)$ multiplier.
\end{itemize}
\end{itemize}

\section{Online Kernel Machine}

\begin{itemize}
\item Initialize the function $f=0$.

\item For t = 1 to T:

\begin{enumerate}

\item Observe some measurement over some set of features $x_t$
\item Predict the class using $f(x_t) = \sum_{i=1}^n \alpha_i K(x_i, x_t)$
\item Receive loss based on the prediction from $f(x_t)$ and the true class $y_t$ 
    \[L(f(x_t),y_t)\]
\item Update $f$ based on the gradient of the loss function $L$ and learning rate $\eta_t$ depending on the chosen algorithm (examples in previous section).
\end{enumerate}
\end{itemize}

\subsection{Discussion}

\begin{itemize}
\item
\textbf{Representer Theorem} (informally): Given a loss function and regularizer objective
with many data points $\{x_i\}$, the minimizing solution $f^*$ can be represented as
\begin{equation}
f^*(\cdot) = \sum_i \alpha_i K(x_i, \cdot)
\end{equation}


\item This algorithm qualitatively corresponds to adding weighted 'bumps' that predicts some value based on the kernel function in each new observation's neighborhood of the feature space in $x$. For example: Figure \ref{fig:kernel_update} shows an update over 3 points $\{(x_1,+), (x_2,-) , (x_3,+)\}$. The individual kernels centered at the points are \textbf{independently} drawn with colored lines.  After 3 updates, the function $f$ looks like the solid black line.

\begin{figure}[ht]
\centering
\includegraphics[width=0.85\linewidth]{images/kernel_update}
\caption{Illustration of function after 3 updates}
\label{fig:kernel_update}
\end{figure}

\item Need to perform $O(T)$ work at each time step. As time progresses and the data set grows, the prediction step will take longer and longer to compute.  To shorten this computation time you may want to throw out old data points by weight or age.  If interested, there are some papers on that use tricks to find sparse solutions to large-scale problems:
\begin{itemize}
	\item Rahimi and Recht - \textit{Random Features for Large-Scale Kernel Machines} 2007
	\item Dekel, Shalev-Shwartz and Singer \textit{The Forgetron: A Kernel-Based Perceptron on a Budget} 2007
\end{itemize}


\item The regret is computed as: \[Regret = \sum_t (C_t(f_t(x_t)) - C_t(f^*(x_t))) \mbox{     } | \mbox{     } f^* \in H_k\]
The regret bound:\[Regret = ||\nabla C_t(f)||_k \cdot ||f^*||_k \sqrt T \]
$||f^*||$ is the size of the function.  $||\nabla C_t(f)||$ can get as big as $\alpha^TK\alpha$.

	
\item The choice and tuning of the kernel and their corresponding bandwidth parameters are what affect the bias-variance tradeoff.  These are parameters that need to be tuned in addition to the learning rate $\eta$ and decay rate $\lambda$ from the update equations.
\begin{itemize}
		\item Often simple kernels work quite well.  When approaching a new problem it is usually a good idea start with linear or polynomial kernels.  Radial basis functions are another good kernel to try early on.  Note that any kernels $K_1$ and $K_2$ that satisfy the conditions mentioned in Section 2 can be summed to form a new valid kernel.
\end{itemize}
\end{itemize}
\end{document}