\documentclass[11pt,a4paper,fleqn]{jsarticle}
\usepackage{amsmath,amssymb,amscd}
\usepackage{bm}
\usepackage{graphicx}
\usepackage{ascmac}
\usepackage{cases}
\setlength{\textwidth}{\fullwidth}
\setlength{\textheight}{40\baselineskip}
\addtolength{\textheight}{\topskip}
\setlength{\voffset}{-0.2in}
\setlength{\topmargin}{0pt}
\setlength{\headheight}{0pt}
\setlength{\headsep}{0pt}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 数式と図の連番
\makeatletter
\renewcommand{\theequation}{ \thesection.\arabic{equation} }
\@addtoreset{equation}{section}
\renewcommand{\thefigure}{ \thesection.\arabic{figure} }
\@addtoreset{figure}{section}
\makeatother
\DeclareMathOperator*{\maximize}{\mathrm{max}}
\newcommand{\xx}{\mathbf{x}}
\newcommand{\yy}{\mathbf{y}}
\newcommand{\zz}{\mathbf{z}}
\newcommand{\tht}{\mathbf{\theta}}
\newcommand{\ps}{\mathbf{\psi}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 属性
\title{Pattern Recognition and Machine Learning 6.2.}
\author{1G06Q117-5 園田 翔\thanks{早稲田大学理工学部電気・情報生命工学科 村田研究室４年}}
\date{2009/6/8}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% ここから本文
\begin{document}
\maketitle
\section{Constructing Kernels}
\begin{itembox}[l]{Kernel function}
$ \begin{array}{c c c c c c c c c}
k & : & \mathcal{X} \times \mathcal{X} & \to & \mathbb{R}^N \times \mathbb{R}^N & \to & \mathbb{R} && \\
& & \rotatebox[origin=c]{90}{$\in$} & & \rotatebox[origin=c]{90}{$\in$} & & \rotatebox[origin=c]{90}{$\in$} &&\\
& & (\xx,\xx') & \mapsto & (\mathbf{\phi(x)}, \mathbf{\phi(x')}) & \mapsto & \sum_{i=1}^N \phi_i(\xx) \phi_i(\xx') &=:& \langle \mathbf{\phi(x)},\mathbf{\phi(x')}\rangle_f
\end{array} $
\end{itembox}
\subsection{how to construct valid kernel functions}
\begin{itembox}[l]{to construct valid kernel functions}
\begin{enumerate}
\item to choose a feature space mapping $ \phi(\xx) $.
\item to construct $k(\xx,\yy)$ and find certain $\phi(\xx)$
\item to see if the Gram Matrices $\mathbf{K}_{ij} := k(\xx_i, \xx_j)$ for all possible $ \{ \xx_n \} $ are positive semidefinite. (necessary and sufficient condition, Shawe-Taylor and Cristianini, 2004)
\item to build a kernel out of simpler ones.
\end{enumerate}
\end{itembox}
Rem. We require that a kernel $k(\xx,\xx')$
\begin{itemize}
\item be symmetric and positive semidefinite
\item expresses the appropriate form of similarity between $\xx$ and $\xx'$
\end{itemize}
\begin{figure}[h]
\begin{minipage}{0.3\hsize}
\begin{center}
\includegraphics{Figure6_1a.eps}
\end{center}
\caption{Figure6.1a}
\end{minipage}
\begin{minipage}{0.3\hsize}
\begin{center}
\includegraphics{Figure6_1b.eps}
\end{center}
\caption{Figure6.1b}
\end{minipage}
\begin{minipage}{0.3\hsize}
\begin{center}
\includegraphics{Figure6_1c.eps}
\end{center}
\caption{Figure6.1c}
\end{minipage}
\end{figure}
\begin{figure}[h]
\begin{minipage}{0.3\hsize}
\begin{center}
\includegraphics{Figure6_1d.eps}
\end{center}
\caption{Figure6.1d}
\end{minipage}
\begin{minipage}{0.3\hsize}
\begin{center}
\includegraphics{Figure6_1e.eps}
\end{center}
\caption{Figure6.1e}
\end{minipage}
\begin{minipage}{0.3\hsize}
\begin{center}
\includegraphics{Figure6_1f.eps}
\end{center}
\caption{Figure6.1f}
\end{minipage}
\end{figure}
\begin{figure}[h]
\begin{minipage}{0.31\hsize}
\begin{center}
\includegraphics[width=5cm, trim=60 60 60 60]{kpoly.eps}
\end{center}
\caption{monomial kernel}
\end{minipage}
\begin{minipage}{0.31\hsize}
\begin{center}
\includegraphics[width=5cm, trim=60 60 50 60]{kgauss.eps}
\end{center}
\caption{gaussiann kernel}
\end{minipage}
\begin{minipage}{0.31\hsize}
\begin{center}
\includegraphics[width=5cm, trim=60 60 60 60]{ksig.eps}
\end{center}
\caption{logistic sigmoid kernel}
\end{minipage}
\end{figure}
\begin{itembox}[l]{ the followings are valid kernels.}
Given $k_1(\xx,\xx'),k_2(\xx,\xx')$ to be valid,
\begin{align}
k(\xx,\xx') & := f(\xx) k_1(\xx,\xx') f(\xx') \quad \mbox{( $f$ : function )} \label{eq:ff} \\
k(\xx,\xx') & := c k_1(\xx,\xx') \quad \mbox{( c : positive constant )} \\
k(\xx,\xx') & := k_1(\xx,\xx') + k_2(\xx,\xx') \\
k(\xx,\xx') & := k_1(\xx,\xx') k_2(\xx,\xx') \\
k(\xx,\xx') & := q(k_1(\xx,\xx')) \quad \mbox{( q : polynomial with nonnegatibe coefficients )} \\
k(\xx,\xx') & := \exp(k_1(\xx,\xx')) \label{eq:exp} \\
k(\xx,\xx') & := k_3(\mathbf{\phi}(\xx),\mathbf{\phi}(\xx')) \quad \mbox{( $\mathbf{\phi}(\xx) \in \mathbb{R}^N$, $k_3(\xx,\xx')$ is a valid kernel in $\mathbb{R}^N$)} \\
k(\xx,\xx') & := \xx^\mathrm{T} \mathbf{A} \xx' \quad \mbox{( } \xx \in \mathbb{R}^M, \mathbf{A} \mbox{ : sym. pos. semidef. )} \\
k(\xx,\xx') & := k_a(\xx_a,\xx_a') + k_b(\xx_b,\xx_b') \quad \mbox{( } \xx = (\xx_a,\xx_b) \mbox{ )} \\
k(\xx,\xx') & := k_a(\xx_a,\xx_a') k_b(\xx_b,\xx_b') \label{eq:fl}
\end{align}
\end{itembox}
\subsection*{Proofs}
%ここに証明を書く(特にexp(k))
\begin{itemize}
\item[\ref{eq:exp}]
\end{itemize}
%%% polynomial %%%
\subsection*{Ex1. Polynomial kernel}
\begin{itembox}[l]{Polynomial kernel}
$\xx,\xx' \in \mathbb{R}^N$, $c>0$
\begin{eqnarray}
k(\xx,\xx')&:=&(\xx^\mathrm{T} \xx')^M \label{eq:hom} \\ % homogeneous polynomial
k(\xx,\xx')&:=&(\xx^\mathrm{T} \xx'+c)^M \label{eq:all}
\end{eqnarray}
\end{itembox}
\begin{itemize}
\item (\ref{eq:hom}) contains all monomials order M.
\item Whereas (\ref{eq:all}) contains all terms up to degree M.
\item If $\xx$ and $\xx'$ are two images, it represents a particular weighted sum of products of M pixels in the $\xx$ with M pixels in the $\xx'$.
\end{itemize}
%（それぞれ同次式，多項式になっていることを確認）
%（画像の例が本当に類似度を表しているのか確認）
%%% Gaussian %%%
\subsection*{Ex2. Gaussian kernel}
\begin{itembox}[l]{Gaussian kernel}
$\xx,\xx' \in \mathbb{R}^N$
\begin{eqnarray}
k(\xx,\xx') &:=& \exp \left( -\frac{\| \xx - \xx' \|^2}{2 \sigma^2} \right) \\
&=& \exp \left( -\frac{\xx^\mathrm{T} \xx + (\xx')^\mathrm{T} \xx' - 2 \xx^\mathrm{T} \xx'}{2 \sigma^2} \right)
\end{eqnarray}
$\kappa(\xx,\xx')$ : nonlinear kernel
\begin{equation}
k(\xx,\xx') := \exp \left( -\frac{\kappa(\xx,\xx) + \kappa(\xx',\xx')-2\kappa(\xx,\xx')}{2 \sigma^2} \right)
\end{equation}
\end{itembox}
%演習問題（R^n上のガウスカーネルを無限次元の内積として表現する。）
%（それでなんの類似度を表しているのか）
%%% over sets %%%
\subsection*{Ex3. Kernels over graphs, sets, strings and text documents.}
\begin{itembox}[l]{The kernel defined over sets}
$D$ : fixed set \\
$A_1, A_2 \subset D$
\begin{equation}
k(A_1,A_2) := 2^{|A_1 \cap A_2|}
\end{equation}
where $|A|$ denotes the number of elements in $A$
\end{itembox}
\begin{itemize}
\item Kernels can be defined over graphs, sets, strings and text documents.
\end{itemize}
%演習問題（カーネルの確認）
%%% generative and discriminative %%%
\subsection*{Ex4. Kernels from probabilistic generative models}
\begin{itemize}
\item Generative models can deal naturally with missing data, \par and in the case of HMMs it can handle sequences of varying length.
\item Whereas Discriminative models generally give BETTER performance.
\item In order to combine two approaches, we define a kernel using a generatibe model, and apply the kernel in a discriminative approach.
\end{itemize}
\begin{itembox}[l]{The kernel defined over sets}
$p(\xx)$ : generative model
\begin{equation}
k(\xx,\xx') := p(\xx)p(\xx') \label{eq:pg1}
\end{equation}
$p(i)$ : positive weighting coefficients, or 'latent' variable (\S 9.2) \\
$p(\mathbf{z})$ : weighting coefficients for continuous latent variable
\begin{eqnarray}
k(\xx,\xx') &:=& \sum_i p(\xx|i)p(\xx'|i)p(i) \label{eq:pg2} \\
& \xrightarrow[i\to\infty]{} & \int p(\xx|\mathbf{z})p(\xx'|\mathbf{z})p(\mathbf{z}) d \mathbf{z} \label{eq:pg3}
\end{eqnarray}
HMM (\S 13.2) \\
$\mathbf{X}=\{ \xx_1,\cdots,\xx_L \}$ : input data consists of ordered sequences. \\
$\mathbf{Z}=\{\zz_1,\cdots,\zz_L \}$ : corresponding sequence of hidden states.
\begin{equation}
k(\mathbf{X},\mathbf{X}') := \sum_\mathbf{Z} p(\mathbf{X}|\mathbf{Z})p(\mathbf{X}'|\mathbf{Z})p(\mathbf{Z}) \label{eq:pg4}
\end{equation}
\end{itembox}
\begin{itemize}
\item (\ref{eq:pg1}) represents that $\xx$ and $\xx'$ are similar if they have high probabilities.
\item (\ref{eq:pg2}) is equivalent, if normalized, to a mixture distribution.
\item A popular generative model for sequences is the HMM, which expresses the distribution $p(\mathbf{X})$ as a marginalization over $\mathbf{Z}$.
\item (\ref{eq:pg4}) measures the similarity of two sequences.
\end{itemize}
%%% Fisher %%%
\subsection*{Ex5. Fisher kernel}
\begin{itembox}[l]{Fisher kernel}
$p(\xx|\mathbf{\theta})$ : $\mathbf{\theta}$-parametrized generative model \\
Fisher score :
\begin{equation}
\mathbf{g(\theta,x)} := \nabla_\mathbf{\theta} \ln p(\xx|\mathbf{\theta})
\end{equation}
Fisher information matrix :
\begin{eqnarray}
\mathbf{F} &:=& \mathbb{E}_\xx \left[ \mathbf{g(\theta,x)} \mathbf{g(\theta,x)}^\mathrm{T} \right] \\
&=& \int \begin{pmatrix} \frac{\partial \ln p(\xx|\mathbf{\theta})}{\partial \theta_1}\frac{\partial \ln p(\xx|\mathbf{\theta})}{\partial \theta_1} & \cdots & \frac{\partial \ln p(\xx|\mathbf{\theta})}{\partial \theta_1}\frac{\partial \ln p(\xx|\mathbf{\theta})}{\partial \theta_P} \\ \vdots & \ddots & \vdots \\ \frac{\partial \ln p(\xx|\mathbf{\theta})}{\partial \theta_P}\frac{\partial \ln p(\xx|\mathbf{\theta})}{\partial \theta_1} & \cdots & \frac{\partial \ln p(\xx|\mathbf{\theta})}{\partial \theta_P}\frac{\partial \ln p(\xx|\mathbf{\theta})}{\partial \theta_P} \end{pmatrix} p(\xx|\mathbf{\theta}) d \xx
\end{eqnarray}
Fisher kernel :
\begin{equation}
k(\xx,\xx') := \mathbf{g(\theta,x)}^\mathrm{T} \mathbf{F}^{-1} \mathbf{g(\theta,x')}
\end{equation}
\end{itembox}
\begin{itemize}
\item It measures the similarity between $\xx$ and $\xx'$ induced by the generative model $p(\xx|\mathbf{\theta})$.
\item It can be motivated from the perspective of information geometry.(Amari, 1998)
\item form-invariant under a nonlinear re-parametrization : $\mathbf{\theta} \to \mathbf{\psi(\theta)}$
%演習問題（変換不変を導く）
[Proof.] \\
Let $f(\tht):= \ln p(\xx|\tht)$, $ \widetilde{f}(\ps(\tht)):=f(\tht) $
\begin{equation}
\mathbf{g}(\tht,\xx) = \frac{\partial f(\tht)}{\partial \tht} = \frac{\partial \widetilde{f}(\ps(\tht))}{\partial \tht} = \mathcal{J} \mathbf{h}(\ps,\xx) \quad \left( \mathcal{J} := \left( \frac{\partial \ps }{\partial \tht} \right)^\mathrm{T}, \mathbf{h}(\ps,\xx):=\frac{\partial \widetilde{f}(\ps)}{\partial \ps}\right)
\end{equation}
Therefore,
\begin{eqnarray}
\mathbf{F} &=& \mathbb{E}_\xx [ \mathbf{g}(\tht,\xx) \mathbf{g}(\tht,\xx')^\mathrm{T} ] \\
&=& \mathbb{E}_\xx [\mathcal{J} \mathbf{h}(\ps,\xx) \mathbf{h}(\ps,\xx')^\mathrm{T}\mathcal{J}^\mathrm{T}] \\
&=& \mathcal{J} \mathbb{E}_\xx [ \mathbf{h}(\ps,\xx) \mathbf{h}(\ps,\xx')^\mathrm{T}]\mathcal{J}^\mathrm{T}
\end{eqnarray}
Then,
\begin{eqnarray}
\mathbf{g}(\tht,\xx)^\mathrm{T} \mathbf{F}^{-1} \mathbf{g}(\tht,\xx') &=& \mathbf{h}(\ps,\xx)^\mathrm{T} \mathcal{J}^\mathrm{T} \left( \mathcal{J}^\mathrm{T} \right)^\mathrm{-1} \left( \mathbb{E}_\xx [ \mathbf{h}(\ps,\xx) \mathbf{h}(\ps,\xx')^\mathrm{T}] \right)^\mathrm{-1} \mathcal{J}^\mathrm{-1} \mathcal{J} \mathbf{h}(\ps,\xx') \\
&=& \mathbf{h}(\ps,\xx)^\mathrm{T} \left( \mathbb{E}_\xx [ \mathbf{h}(\ps,\xx) \mathbf{h}(\ps,\xx')^\mathrm{T}] \right)^\mathrm{-1} \mathbf{h}(\ps,\xx')
\end{eqnarray}
Q.E.D.
\item In practice, we substitute the sample average for the proper $\mathbf{F}$.
\begin{equation}
\mathbf{F} \simeq \frac{1}{N} \sum_{n=1}^N \mathbf{g(\theta,x_n)} \mathbf{g(\theta,x_n)}^\mathrm{T}
\end{equation}
This is the covariance matrix of the Fisher scores.
Thus the kernel corresponds to a whitening of these scores.
% この近似はどうして成り立つのか
\item or, more simply replace $\mathbf{F} \to \mathbf{I}$. This is NO MORE form-invariant.
\item Fisher kernels applied to document retrieval.(Hofmann, 2000)
\end{itemize}
%%% Sigmoidal %%%
\subsection*{Ex6. Sigmoidal kernel}
\begin{itembox}[l]{Sigmoidal kernel}
\vspace{-\baselineskip} % 数式だけのitemboxは一行下がってしまうので上げる
\begin{equation}
k(\xx,\xx') := \tanh(a \xx^\mathrm{T} \xx' + b)
\end{equation}
\end{itembox}
\begin{itemize}
\item This is NOT positive semidefinite in general.
\item superficial resemblances between SVMs and NNs.
\item some Baysian NNs have deeper links to kernel methods. (\S 6.4.7)
\end{itemize}
\end{document}
最終更新：2009年06月08日 03:27
