%% This LaTeX-file was created by <jl> Mon Feb 23 20:34:36 1998
%% LyX 0.12 (C) 1995-1998 by Matthias Ettrich and the LyX Team

%% Do not edit this file unless you know what you are doing.
\documentclass{article}
\usepackage[T1]{fontenc}

\makeatletter


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% LyX specific LaTeX commands.
\newcommand{\LyX}{L\kern-.1667em\lower.25em\hbox{Y}\kern-.125emX\spacefactor1000}

\makeatother

\begin{document}

First, some definitions.

\begin{itemize}
\item \( X= \) input space = a bounded subset of \( R^{n} \)
\item \( x\in X \)
\item \( Y= \) output space = \( \{0,1\} \)
\item \( y\in Y \)
\item \( Z=X\times Y \) 
\item \( z\in Z \)
\item \( P \) = probability distribution on \( Z \)
\item \( R \) = radius of smallest hyper-sphere in \( R^{n} \) containing \( X \).
\item \( w_{i} \) = lagrange multipliers in a support vector machine.
\item \( A=max(||w_{i}||) \) = maximum allowed magnitude of support vector lagrange multipliers in an SVM.
\item \( H_{RA}= \) space of hypothesis with a distribution bounded by \( R \) and a lagrange multiplier
magnitude bounded by \( A \).
\item \( h\in H_{RA} \)
\item \( VCDim(H_{RA})=d\leq R^{2}A^{2}+1 \) Actually, this is not quite true. See http://svm.research.bell-labs.com/SVMdoc.html
for a good discussion of why. It is close to true in some sense though.
\item \( l:\{0,1\}\times \{0,1\}\rightarrow \{0,1\} \)= a loss function. \( l(0,0)=0, \) \( l(1,1)=0 \) otherwise \( l(y_{1},y_{2})=1 \)
\item \( h_{l}(z)=l(h(x),y) \)
\item \( d_{P}(h,h^{'})=\int _{Z}|h_{l}(z)-h_{l}^{'}(z)|dP(z) \) = a (pseudo) metric between hypothesis based on how different their loss signature
is.
\item \( N(\epsilon ,H_{RA},d_{P}) \) = minimum number, \( N, \) of points s.t. every \( h\in H_{RA} \) satisfies \( d_{P}(h,h^{'})<\epsilon  \) where \( h'\in S_{N} \) the set of
\( N \) points.
\item \( C(\epsilon ,H_{RA})=sup_{P}N(\epsilon ,H_{RA},d_{P}) \) = \( N \) under the worst \( P \)
\end{itemize}
Now, I need to define or bound \( C(\epsilon ,H_{RA}) \) in order to apply Baxter's bounds. In general,
it should be of the form: \( C(\epsilon ,H_{RA})=k(\frac{c}{\epsilon })^{d} \) where \( k,c \) are some constants.

If you assume a discrete probability distribution over a set of maximally seperated
points on the sphere, you get \( C(\frac{1}{d},H_{RA})\leq M(d) \) where \( M(d) \) is the growth function defined by Sauer's
lemma. Proof: every hypothesis \( h \) which shaters the \( X \) in a different way will
be a distance of at least \( \frac{1}{d} \) from every other shattering under \( d_{P} \). Hypothesis
which do shatter \( X \) in the same way will have distance 0 under \( d_{P} \). \( M(d) \) is a bound
on the number of shatterings, so it must be a bound on the covering number.

\begin{enumerate}
\item Can you think of a more direct proof?
\item Can you think of a good way to extend the covering to arbitrary \( \epsilon  \) and \( P \)?
\end{enumerate}
\end{document}
