%% This LaTeX-file was created by <jl> Sun Mar  1 15:07:15 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}


\section{general proof}

I'm going to try to work out bounds for the kernel \( K(Ax,Ay) \) first. Hopefully, this
will transfer to other kernel parameterizations.


\subsection{definitions}

First, some definitions.

\begin{itemize}
\item \( X= \) input space = a bounded subset of \( R^{n} \)
\item \( x\in X \)
\item \( m=length(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 \)
\item let \( =\{H\circ f:f\in F\} \) 
\item let \( H_{l}=\{l\circ h:h\in H\} \) = \( H \) with the loss function absorbed.
\item \( d_{L^{1}}(f,g)=\int _{X}sup_{y\in Y}|l(y,f(x))-l(y,g(x))|dP(x) \)
\end{itemize}

\section{Capacity values}


\subsection{Support Vector machines}

Theorem: let \( h\in H \) with \( h:X\rightarrow A=[0,1] \) with \( VCdim(H)\leq d \) for some \( 1\leq d<\infty  \):


\[
C(\epsilon ,H,d_{L^{1}})<2\left( \frac{2e}{\epsilon }\ln \frac{2e}{\epsilon }\right) ^{d}\]


proof: This is a specialization of Haussler's theorem 10.

In particular, this approximately bounds the capacity of SVM's.


\subsection{linear spaces}

Theorem: Let \( F \) be a \( d \)-dimensional vector space of functions from a set \( Z \) into
\( R \), then \( VCdim(F)=d \).

Proof: due to Dudley, 1978

In particular, letting \( F=sgn(Ax) \), we get \( VCdim(F)=m^{2} \) where \( x \) has \( m \) dimensions.


\section{relating capacities}


\subsection{\protect\( d_{L^{1}}\protect \) to \protect\( d_{P}\protect \)}

Haussler's theorems are independent of y while Baxter's metric is dependent
on y. We must relate the two metrics.

\( d_{p}(g,f) \)\( =\int _{X\times Y}|(g(x)-y)^{2}-(f(x)-y)^{2}|dP(x,y) \) 

\( =\int _{X\times Y}|((g(x)-f(x))(g(x)+f(x))+2y(f(x)-g(x))|dP(x,y) \) 

\( \leq \int _{X\times Y}|((g(x)-f(x))(g(x)+f(x))|+|2y(f(x)-g(x))|dP(x,y) \) 

\( \leq 4\int _{X}|((g(x)-f(x))|dP(x) \) 

Which implies: \( C(\frac{\epsilon }{4},H,d_{L^{1}})\geq C(\epsilon ,H,d_{P}) \)

I can 'sort of' relate the capacities of \( C(\epsilon ,F,d_{L^{1}}) \) to \( C(\epsilon ,F,d_{P}) \). If, instead of taking a sign,
you use the function: \( softsign(x)=\begin{array}{ccc}
sign(x) & if & |x|\geq \frac{1}{A}\\
\frac{A}{2}(x+\frac{1}{A}) & if & |x|<\frac{1}{A}
\end{array} \) then the output of SVM's will satisfy a lipschitz condition: \( ||f(x)-f(x')||\leq \frac{A}{2}||x-x'|| \). Note that this
'sort of' is as valid as \( VCdim(SVM)\leq R^{2}A^{2}+1 \).

Satisfying a lipschitz condition allows you to relate \( d_{L^{1}} \) to \( d_{p} \) for functions on
\( F \) through a pullback. 

\( d_{p}(g,f) \)\( =\int _{X\times Y}|(h\circ g(x)-y)^{2}-(h\circ f(x)-y)^{2}|dP(x,y) \) 

\( \leq \frac{A}{2}\int _{X\times Y}|(g(x)-y)^{2}-(f(x)-y)^{2}|dP(x,y) \) 

\( \leq 4\frac{A}{2}\int _{X}|((g(x)-f(x))|dP(x) \) 

which implies: \( C(\frac{\epsilon }{2A},F,d_{L^{1}})\geq C(\epsilon ,F,d_{P}) \)


\subsection{capacities}


\paragraph{Theorem: With \protect\( \protect \) as above, then for all \protect\( \epsilon ,\epsilon _{1},\epsilon _{2}>0\protect \) with \protect\( \epsilon =\epsilon _{1}+\epsilon _{2}\protect \), }


\[
C(\epsilon ,_{l}^{n})\leq C(\epsilon _{1},H_{l})^{n}C_{H_{l}}(\epsilon _{2},F)\]



\[
C(\epsilon ,^{*})\leq C_{H_{l}}(\epsilon ,F)\]


proof: One of Baxters theorems.

Putting this together, we get: 

\( C(\epsilon ,_{l}^{n})\leq  \)\( 2^{n}\left( \frac{8e}{\epsilon }\ln \frac{8e}{\epsilon }\right) ^{(R^{2}A^{2}+1)n} \)\( 2\left( \frac{4Ae}{\epsilon }\ln \frac{4Ae}{\epsilon }\right) ^{m^{2}} \) 

\( C(\epsilon ,^{*})\leq  \)\( 2\left( \frac{4Ae}{\epsilon }\ln \frac{4Ae}{\epsilon }\right) ^{m^{2}} \)


\section{The bound}

Now we just plug in the capacities above into Baxter's theory.


\paragraph{Theorem: For \protect\( n=\protect \)number of tasks and \protect\( o=\protect \)number of examples/task, if \protect\( n\geq max\{\frac{288}{\epsilon ^{2}}\ln \protect \)\protect\( \frac{8}{\delta }2\left( \frac{48*4Ae}{\epsilon }\ln \frac{48*4Ae}{\epsilon }\right) ^{m^{2}}\protect \)\protect\( ,\frac{72}{\epsilon ^{2}}\}\protect \) and \protect\( o\geq max\{\frac{288}{n\epsilon ^{2}}\ln \protect \)\protect\( \frac{8}{\delta }2^{n}\left( \frac{48*8e}{\epsilon }\ln \frac{48*8e}{\epsilon }\right) ^{(R^{2}A^{2}+1)n}\protect \)\protect\( 2\left( \frac{48*4Ae}{\epsilon }\ln \frac{48*4Ae}{\epsilon }\right) ^{m^{2}}\protect \)
then with \protect\( p\geq 1-\delta \protect \), }


\[
er_{Q}(H)\leq er_{Z}(H)+\epsilon \]


Proof: application of one of Baxter's theorem 2.

Note that this bound isn't very tight. It can also be simplified into the functional
form:

\( n\geq O(\frac{1}{\epsilon ^{2}}(m^{2}+\ln \frac{1}{\delta })) \) and \( o\geq O(\frac{1}{\epsilon ^{2}}[R^{2}A^{2}+1+\frac{1}{n}(m^{2}+ln\frac{1}{\delta })]) \)

This theorem essentially talks about learning the bias rather than learning
a particular task. To learn a particular task, a different theorem can be used.


\paragraph{Theorem: For \protect\( o=\protect \)number of examples, if \protect\( o\geq \frac{72}{\epsilon ^{2}}\ln \frac{4}{\delta }\protect \)\protect\( 2\left( \frac{24*8e}{\epsilon }\ln \frac{24*8e}{\epsilon }\right) ^{(R^{2}A^{2}+1)}\protect \) then with \protect\( p\geq 1-\delta \protect \), \protect\( er_{P}(h)\leq er_{z}(h)+\epsilon \protect \)}

proof: application of Baxter's theorem 3.

In functional form, this bound is: \( o\geq O(\frac{1}{\epsilon ^{2}}[R^{2}A^{2}+1+\ln \frac{1}{\delta }]) \)

\end{document}
