\documentclass[12pt]{article}
%\usepackage{a4}
%\usepackage[czech]{babel}
%\usepackage{html}
%\usepackage{graphicx}
\usepackage{amssymb}
\usepackage{amsfonts}

\def\beq{\begin{equation}}
\def\eeq{\end{equation}}
\def\beqn{\begin{eqnarray}}
\def\eeqn{\end{eqnarray}}
\def\beqns{\begin{eqnarray*}}
\def\eeqns{\end{eqnarray*}}
\def\argmax{\mathop{\rm argmax}}
\def\argmin{\mathop{\rm argmin}}
\def\Re{{\mathbb R}}
\def\SX{{\cal X}}
\def\SZ{{\cal Z}}
\def\lz{\langle}
\def\pz{\rangle}
\def\equ#1{(\ref{#1})}

\author{Vojt{\v e}ch Franc, translated by Petr Doubek\\
{\em Center for Machine Perception, FEE CTU Prague}}
\title{Recognition Labs -- Nonlinear Perceptron}

\date{November 5 2009}

\begin{document}

\maketitle

\section{Introduction}
The goal of this exercise is to extend the perceptron learning algorithm
to nonlinear classifier, i.e. classifier with nonlinear discriminative function.
We will demonstrate it on learning a quadratic discriminative function in
a two-dimensional feature space.

\section{Lifting the Feature Space}

The perceptron algorithm optimises parameters of a linear classifier,
so that the classifier has zero error on given training data
$\{(\vec{x}_1,y_1),\ldots,(\vec{x}_m,y_m)\}$. The linear classifier decides
based on the sign of linear discriminative function
\begin{equation}
  \label{equ:LinDscr}
  f(\vec{x}) = \lz \vec{w},\vec{x}\pz +b = \sum_{i=1}^n w_i x_i + b\:,
\end{equation}
%
where vector $\vec{w}\in\Re^n$ and scalar $b\in\Re$ are parameters and $\vec{x}\in\Re^n$
is a feature vector of the object to be classified. Note that the discriminative
function~\equ{equ:LinDscr} is linear in both parameters $(\vec{w},b)$ as well as
in the feature vector $\vec{x}$. By nonlinear classifier we mean nonlinear with respect
to the feature vector $\vec{x}$. For optimising the parameters of nonlinear classifier
by perceptron, we will use {\em lifting of feature space}.
The idea of lifting is as follows: (i) project training samples from input feature
space $\SX\subseteq\Re^n$ into new (lifted) space $\SZ\subseteq\Re^N$, where nonlinear
functions project as linear; (ii) use perceptron algorithm in lifted space $\SZ$.
Found parameters determine a linear classifier in the space $\SZ$ and a nonlinear
classifier in the input space $\SX$.  The function which maps the input feature space
to the new lifted space is denoted as $\phi\colon\SX\rightarrow\SZ$.
Let us focus on one specific case of learning a quadratic discriminative function:
the input feature space $\SX\subseteq\Re^n$ is two-dimensional ($n=2$) and the quadratic
discriminative function has form
\begin{equation}
 \label{equ:KvadrDscr}
 q(\vec{x}) = w_1 \cdot x_1 + w_2\cdot x_2 + w_3\cdot  x_1^2 + w_4\cdot x_1\cdot x_2 +
 w_5 \cdot x_2^2 + b = \sum_{i=1}^5 w_i \phi_i(\vec{x}) + b\:.
\end{equation}
%
By comparing the linear~\equ{equ:LinDscr} and the quadratic discriminative
function~\equ{equ:KvadrDscr}, we can derive mapping function $\phi$
\begin{equation}
  \label{equ:Transform}
  \vec{z} = \phi(\vec{x}) \quad\mbox{as}\quad
  \left [ \begin{array}{c}z_1\\z_2\\z_3\\z_4\\z_5\end{array}\right ] 
   = 
  \left
    [\begin{array}{c}\phi_1(\vec{x})\\\phi_2(\vec{x})\\\phi_3(\vec{x})\\\phi_4(\vec{x})\\
      \phi_5(\vec{x})\end{array}\right ] =    
  \left [ \begin{array}{c}x_1\\x_2\\x_1^2\\x_1\cdot x_2\\x_2^2\end{array}\right
  ] \:.  
\end{equation}
%
The lifted feature space $\SZ$ is 5-dimensional. Entire extension of the
linear perceptron algorithm to algorithm searching quadratic discriminative
function is done as follows:
\begin{enumerate}
\item Transform the training data $\{(\vec{x}_1,y_1),\ldots,(\vec{x}_m,y_m)\}$ into
		lifted feature space as $\{(\vec{z}_1,y_1),\ldots,(\vec{z}_m,y_m)\}$
		using the mapping function~\equ{equ:Transform}. 
  \item Use perceptron algorithm to learn a linear classifier on the lifted training
	  set $\{(\vec{z}_1,y_1),\ldots,(\vec{z}_m,y_m)\}$.
  \item Substitute the found parameters $(\vec{w},b)$ into the quadratic discriminative
	  function~\equ{equ:KvadrDscr}.
\end{enumerate}

\end{document}
