\documentstyle[psbox,ps,11pt,fullpage]{article}

\title{Clustering in High-Dimensional Feature Spaces}
\author{Matthew Gray}
\begin{document}
\maketitle

\begin{equation}
{\bf m_\nu} = \sum_{j=1}^{M} \gamma_{\nu j}\Phi({\bf x}_j).
\end{equation}


Now, the distance between a mean ${\bf m}_\nu$ and a mapped vector
$\Phi({\bf x})$ can be expressed in terms of dot products:

\begin{equation}
||\Phi({\bf y}) - \sum_{j=1}^M\gamma_{\nu j} \Phi({\bf x}_j)||^2\\
= k({\bf y}, {\bf y}) - 2\sum^{M}_{j=1} \gamma_{\nu j} k({\bf y}, {\bf x}_j) + \sum^{M}_{i,j=1} \gamma_{\nu i}\gamma_{\nu j} k({\bf x}_i, {\bf x}_j)
\label{dist}
\end{equation}

This allows us to determine which cluster is nearest for any given
point.  For training points, the means should be updated according to:

\begin{equation}
{\bf m}_\alpha^{new} = {\bf m}^{old}_\alpha + \zeta(\Phi({\bf x}_{new}) - {\bf m}_\alpha^{old})
\end{equation}

where $\zeta$ is 1 over the number of points closest to ${\bf m}_\alpha$.
\par
Therefore, to update $\gamma$, we do:

\begin{equation}
\gamma^{new}_{\alpha j} = \left\{  
\begin{tabular}{ll}
$\gamma^{old}_{\alpha j}(1 - \zeta)$& for all $j$ other than the current training point\\
&\\
$\zeta + \gamma^{old}_{\alpha j}(1 - \zeta)$& for $j = $ the current training point\\
\end{tabular}
\right.
\end{equation}

Modifying this for fixed variance gaussian clusters is easy, in that
calculating the centroid in our basis space, given the responsibilities $h_\nu^{(i)}$ is trivial:

\begin{equation}
\gamma_{\nu i} = h_\nu^{(i)} = \frac{e^{-\|{\bf y}-{\bf m}_{\nu}\|^2}}{\sum_{i=1}^{N}e^{\|{\bf y} - {\bf m}_i\|}}
\end{equation}

\newpage
\begin{equation}
\Phi\left(
\begin{tabular}{ll}
${\bf x}_1$\\
${\bf x}_2$\\
\end{tabular}
\right) = \left(
\begin{tabular}{c}
$1$\\
${\bf x}_1$\\
${\bf x}_2$\\
${\bf x}_1^2$\\
${\bf x}_2^2$\\
${\bf x}_1{\bf x}_2$\\
\end{tabular}
\right)
\end{equation}

In this case, 
\begin{equation}
k(x,y) = \Phi({\bf x}) \cdot \Phi({\bf y}) = ({\bf x} \cdot {\bf y} + 1)^2
\end{equation}

The RBF kernel I used:

\begin{equation}
k(x,y) = e^{-\frac{\|{\bf x} - {\bf y}\|^2}{\sigma^2}}
\end{equation}


\end{document}