\relax 
\@writefile{toc}{\contentsline {section}{\numberline {1}The Fundamental Idea: Similarity}{1}{}\protected@file@percent }
\newlabel{sec:simil}{{1}{1}{}{section.1}{}}
\newlabel{eq:rbf}{{1}{1}{}{equation.1}{}}
\@writefile{toc}{\contentsline {section}{\numberline {2}Dot Products, Feature Maps, and the Kernel Matrix}{2}{}\protected@file@percent }
\newlabel{sec:featuremap}{{2}{2}{}{section.2}{}}
\@writefile{toc}{\contentsline {subsection}{\numberline {2.1}The Linear Kernel}{2}{}\protected@file@percent }
\@writefile{toc}{\contentsline {subsection}{\numberline {2.2}Mapping to a New Space}{2}{}\protected@file@percent }
\@writefile{toc}{\contentsline {section}{\numberline {3}Which Similarities Are Valid Kernels?}{3}{}\protected@file@percent }
\newlabel{sec:valid}{{3}{3}{}{section.3}{}}
\@writefile{toc}{\contentsline {section}{\numberline {4}A Gallery of Kernels: What Each One Considers Similar}{3}{}\protected@file@percent }
\newlabel{sec:examples}{{4}{3}{}{section.4}{}}
\@writefile{lof}{\contentsline {figure}{\numberline {1}{\ignorespaces Similarity landscapes $K(\mathbf  {x},\mathbf  {z})$ for a fixed $\mathbf  {z}=(1,0.5)$ (star). Linear and polynomial similarity are \emph  {global} (they keep growing in the direction of $\mathbf  {z}$, even far past it); Gaussian and Laplacian similarity are \emph  {local} (a bump centered at $\mathbf  {z}$, close to $0$ elsewhere).}}{4}{}\protected@file@percent }
\newlabel{fig:landscape}{{1}{4}{}{figure.1}{}}
\@writefile{toc}{\contentsline {subsection}{\numberline {4.1}Linear Kernel $K(\mathbf  {x},\mathbf  {z})=\mathbf  {x}\mathbf  {z}^T$}{4}{}\protected@file@percent }
\@writefile{toc}{\contentsline {subsection}{\numberline {4.2}Polynomial Kernel $K(\mathbf  {x},\mathbf  {z})=(\mathbf  {x}\mathbf  {z}^T+c)^p$}{4}{}\protected@file@percent }
\@writefile{lof}{\contentsline {figure}{\numberline {2}{\ignorespaces Decision boundaries of kernel ridge regression (labels $\pm 1$, predict the sign) with three kernels, on three datasets. Rows: linearly separable blobs; concentric circles; XOR. Columns: linear, polynomial of degree 2 $(\mathbf  {x}\mathbf  {z}^T+1)^2$, Gaussian.}}{5}{}\protected@file@percent }
\newlabel{fig:boundaries}{{2}{5}{}{figure.2}{}}
\@writefile{toc}{\contentsline {subsection}{\numberline {4.3}Gaussian (RBF) Kernel $K(\mathbf  {x},\mathbf  {z})=\exp \big  (-\|\mathbf  {x}-\mathbf  {z}\|^2/\sigma ^2\big  )$}{6}{}\protected@file@percent }
\@writefile{toc}{\contentsline {subsection}{\numberline {4.4}Laplacian Kernel $K(\mathbf  {x},\mathbf  {z})=\exp \big  (-\|\mathbf  {x}-\mathbf  {z}\|/\sigma \big  )$}{6}{}\protected@file@percent }
\@writefile{toc}{\contentsline {subsection}{\numberline {4.5}Histogram Kernels (Images, Bag-of-Features)}{7}{}\protected@file@percent }
\@writefile{toc}{\contentsline {subsection}{\numberline {4.6}A Kernel That Is Not Valid: Sigmoid}{7}{}\protected@file@percent }
\@writefile{toc}{\contentsline {section}{\numberline {5}Kernels for Non-Vector Data}{7}{}\protected@file@percent }
\newlabel{sec:nonvector}{{5}{7}{}{section.5}{}}
\@writefile{toc}{\contentsline {section}{\numberline {6}The Kernel Trick}{8}{}\protected@file@percent }
\newlabel{sec:trick}{{6}{8}{}{section.6}{}}
\@writefile{toc}{\contentsline {section}{\numberline {7}The Pattern}{8}{}\protected@file@percent }
\newlabel{sec:partB}{{7}{8}{}{section.7}{}}
\newlabel{eq:dualpred}{{6}{8}{}{equation.6}{}}
\@writefile{lof}{\contentsline {figure}{\numberline {3}{\ignorespaces What a trained kernel model computes (Eq.~\ref {eq:dualpred}). Training only chooses the weights $\alpha _i$; the ``features'' of $\mathbf  {z}$ are its similarities to the training points.}}{8}{}\protected@file@percent }
\newlabel{fig:kernelmachine}{{3}{8}{}{figure.3}{}}
\@writefile{toc}{\contentsline {section}{\numberline {8}Kernel Ridge Regression}{9}{}\protected@file@percent }
\newlabel{sec:krr}{{8}{9}{}{section.8}{}}
\@writefile{toc}{\contentsline {section}{\numberline {9}The Dual Perceptron}{10}{}\protected@file@percent }
\newlabel{sec:dualperc}{{9}{10}{}{section.9}{}}
\@writefile{toc}{\contentsline {section}{\numberline {10}$k$-NN and Kernel Smoothing}{11}{}\protected@file@percent }
\newlabel{sec:knn}{{10}{11}{}{section.10}{}}
\@writefile{toc}{\contentsline {section}{\numberline {11}Kernel PCA}{11}{}\protected@file@percent }
\newlabel{sec:kpca}{{11}{11}{}{section.11}{}}
\@writefile{toc}{\contentsline {subsection}{\numberline {11.1}Recap: PCA}{11}{}\protected@file@percent }
\@writefile{toc}{\contentsline {subsection}{\numberline {11.2}PCA Written with Dot Products Only}{12}{}\protected@file@percent }
\@writefile{toc}{\contentsline {subsection}{\numberline {11.3}The Kernel Trick: Kernel PCA}{12}{}\protected@file@percent }
\@writefile{lof}{\contentsline {figure}{\numberline {4}{\ignorespaces Top: PCA on a 2-D cloud. Dashed lines are points with equal $z_1=(\mathbf  {x}-\mu )\mathbf  {e}_1$; rotating makes them vertical, and keeping $t=1$ drops $z_2$. Bottom: Gaussian Kernel PCA ($\sigma =1$) on two rings. The same steps, done in the feature space: the level lines of $z_1$ are circles in the input space (d) and vertical lines in the new coordinates (e), and $z_1$ alone already separates the rings (f).}}{13}{}\protected@file@percent }
\newlabel{fig:kpcarotate}{{4}{13}{}{figure.4}{}}
\@writefile{toc}{\contentsline {subsection}{\numberline {11.4}Centering Inside $K$}{13}{}\protected@file@percent }
\@writefile{toc}{\contentsline {section}{\numberline {12}Why This Always Works: The Representer Theorem}{14}{}\protected@file@percent }
\newlabel{sec:representer}{{12}{14}{}{section.12}{}}
\@writefile{toc}{\contentsline {section}{\numberline {13}Implementation Notes (HW3)}{15}{}\protected@file@percent }
\newlabel{sec:implementation}{{13}{15}{}{section.13}{}}
\@writefile{toc}{\contentsline {section}{\numberline {14}Optional Material}{15}{}\protected@file@percent }
\newlabel{sec:optional}{{14}{15}{}{section.14}{}}
\@writefile{toc}{\contentsline {subsection}{\numberline {14.1}Kernel Logistic Regression}{15}{}\protected@file@percent }
\@writefile{toc}{\contentsline {subsection}{\numberline {14.2}Mercer's Theorem}{15}{}\protected@file@percent }
\@writefile{toc}{\contentsline {subsection}{\numberline {14.3}Scaling Up: Random Fourier Features and Nystr\"om}{15}{}\protected@file@percent }
\newlabel{sec:opt_scaling}{{14.3}{15}{}{subsection.14.3}{}}
\gdef \@abspage@last{16}