\documentclass[12pt, fullpage]{amsart}
\usepackage[T1]{fontenc}
\usepackage{geometry}
\geometry{verbose,margin=13mm}

\makeatletter

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Textclass specific LaTeX commands.
\theoremstyle{plain}    
\newtheorem{thm}{Theorem} 
\theoremstyle{plain}    
\newtheorem{cor}{Corollary} 
\theoremstyle{plain}    
\newtheorem{lem}{Lemma} 

\makeatother

\begin{document}

\begin{abstract}
There are many examples of machine learning problems which consist of
hierarchically related subproblems.  Given that this extra labeling
information is available, how can we take advantage of it?  The Staged
Learning model allows learning on hierarchies of related tasks of
arbitrary depth which can be understood as a generalization of Jon
Baxter's \cite{Baxter} Learning to Learn model.  Upper bounds on the
number of examples, tasks, etc... are presented and proved.  In the
process, a new, more flexible bound is given for the Learning to Learn
model.  All of these bounds are accomplished by a new technique of
mapping metalearning problems down onto learning problems.  This is
made possible by moving from consideration of the hypothesis space to
consideration of the hypothesis loss space.
\end{abstract}

\title{Staged Learning}

\author{John Langford}
\email{jcl+@cs.cmu.edu}
\maketitle

\newpage
\section{Introduction}

The basic PAC model lays out a theoretical framework for machine
learning which has been qualitatively useful. Unfortunately, there are
many forms of a priori information about a particular problem which
cannot be inserted easily into the PAC framework. In the PAC
framework, every learning problem is approached \emph{tabula rasa} -
without incorporating information from prior learning problems into
the learning of new learning problems. By removing the \emph{tabula
rasa} aspect of PAC learning and allowing information from other tasks
to aid in the learning of the current task, empirical performance
improvement has been shown \cite{Caruana}\cite{Thrun}. The improved
empirical performance can be understood as stemming from a refined,
stronger, bias for learning implying fewer needed examples per task.
Jon Baxter worked through the details of a proof that fewer
examples per task are needed when the tasks are ``related''\cite{Baxter}.

Several people have encountered hierarchical learning problems such as
http or usenet posting\cite{7} classification in which a hierarchy of
related tasks exists naturally.  Baxter's work can't use all of the
information contained in a hierarchy of related tasks with a depth
greater than 2.  This paper provides a generalization of Baxter's work
to arbitrary depth hierarchies, allowing a theoretical analysis of
hierarchies of related tasks.  In the process, we give a more flexible
proof of Baxter's Learning to Learn results.

The Staged Learning model will be defined formally later.  Informally,
the model consists of examples, tasks, groups of tasks, etc... with
each element drawn according to some unknown distribution.  

\subsection{An example: Character recognition}

The character recognition problem naturally falls into a relatively deep hierarchy
which can be understood by considering the set of subproblems or the set of
invariants which each level of the hierarchy introduces.

\begin{itemize}
\item all character recognition problems
\item all English character recognition problems
\item all handwritten English character recognition problems
\item Recognizing handwritten English letters by John Langford
\item Recognizing the letter 'a' handwritten by John Langford
\end{itemize}
At each of these level certain invariants would hopefully be picked out. 

\begin{itemize}
\item scale invariance, location invariance, curve detection
\item No more than 3 vertical or horizontal lines. No more than 2 curves.
\item Start and stop point for each curve.
\item difficult to state. I suspect invariants exist because different characters
in my handwriting seem 'similar'. 
\item Exact task
\end{itemize}
The Staged Learning model suggests the use of chained function
approximators, one for each level in the hierarchy providing some
theoretical motivation for neural networks of a depth greater than
2. Some current character recognition efforts \cite{Le Cun} use a deep
neural net as suggested by this model.

\subsection{Main results}

The contributions of this paper are:

\begin{enumerate}
\item A bound relevant to the Multitask Learning \cite{Caruana} setting
\item A technique for mapping metalearning problems onto learning
problems using the associated loss space.
\item Improvements in the flexibility of bounds in Baxter's Learning to Learn model
\item A model for Staged Learning
\item Upper bounds for the sample complexity (in number of examples,
tasks, etc...) of learning in the Staged Learning model
\end{enumerate}
The Multitask Learning bound provides a more flexible bound then could
previously be applied to the Multitask Learning setting.  The
technique for mapping metalearning problems onto learning problems
simplifies the proof of Learning to Learn and Staged Learning bounds.  

The improved flexibility of bounds for the Learning to Learn model
simply allow a tighter application of the Learning to Learn model by
trading off the number of task and number of examples/task.

The Staged Learning model is applicable to several real world learning
problems involve hierarchies of related tasks. A model for such
situations leads to an improved understanding of when learning can
occur. In addition, the Staged Learning model provides some
theoretical justification for the use of deep (depth greater than 2)
neural nets which have sometimes been found useful experimentally for
learning multiple tasks.

The upper bounds for the Staged Learning model are significant for
research in learning on hierarchies. Like most distribution
independent statistical bounds, the results are not tight enough for
quantitative use. However, the bounds do provide a useful qualitative
understanding of what is necessary for learning to occur within the
model.

\subsection{Paper organization}

The results will be introduced incrementally. In section 2, I will
introduce a generalized version of a theorem from Baxter \cite{Baxter}
which will be used in all the results. In section 3, I will reprove
Baxter's Learning to Learn results with a more flexible bound.  Since
the Staged Learning with a depth of 2 is Learning to Learn, I will
next introduce the full Staged Learning model and prove a convergence
theorem in the model. In section 5, I will apply the bound to a
hierarchical learning problem and discuss other settings in which the
bound is applicable. Section 6 will discuss open work and future
directions of research. Appendix A contains a reference table for all
of the notation used. Appendix B contains the details for the proof of
the theorem introduced in section 2.

\section{Preliminaries}

\subsection{PAC framework}

The notation used is slightly different from standard PAC notation.
This is necessary because there is no easy generalization of the
standard notation to a hierarchical model. After introducing the
notation, a generalization of Haussler's\cite{Haussler} sample
complexity bounds will be proved.  This generalized theorem will be
used as a building block in proving a more flexible bound for Baxter's
Learning to Learn setting and in the convergence bound for the Staged
Learning model.

The initial framework will follow the setup of Haussler\cite{Haussler}
with notation revised for easy extension into the Staged Learning
model. The basic PAC model is characterized by a hypothesis space, \(
H_{F} \), composed of hypotheses, \( H_{f}:x\rightarrow y \) which
take an input \( x\in X \), and produce an output, \( y\in Y \). Let
\( z=(x,y) \) denote a labeled example and let \(Z=X \times Y\).  The
loss function, \( l \), describes the penalty for predicting some
output \(y_1\) when the correct answer is \( y_2 \).  Instead of
viewing \( l \) as a function from \( Y \times Y \rightarrow [0,1] \),
we will find it more convenient to think of \( l \) as a function from
\( (X\rightarrow Y)\times Z \rightarrow [0,1] \) where \( l(H_f,(x,y))
\) gives the loss of predicting \( H_f(x) \) when the correct answer
is \( y \).  Let us create a loss space, \(H^{l}_{F}=\{l(H_{f},\cdot
):H_{f}\in H_{F}\} \) by partially applying the loss function to each
hypothesis.  Individual elements, \( H_{f}^{l}:Z\rightarrow [0,1] \),
of the loss space \( H_{F}^{l} \), are functions from a labeled
example to some loss in \( [0,1] \). Some number, \( N \), of labeled
examples, \( z^{N}\in Z^{N} \), is generated according to an unknown
distribution, \( P \), on the example space, \( Z \). Let \( z_{n} \)
denote the \( n \)th labeled example in \( z^{N} \). A learning
algorithm, \( L(H_{F},z^{N},l) \), in the PAC setting can be thought
of as taking a hypothesis space, \( H_{F} \), a set of examples, \(
z^{N} \), and a loss function, \( l:(X\rightarrow Y)\times Z
\rightarrow [0,1] \) to produce a hypothesis, \( H_{f} \). We will
think of the empirical minimization algorithm: \footnote{Other choice
algorithms can be used.  For example the empirical risk maximization
algorithm or the algorithm which chooses the hypothesis with error
nearest to \( 1/2 \). } evaluate every hypothesis and pick the one
with the lowest average loss.  An upper bound which applies to the
empirical risk minimization algorithm will apply to any other
algorithm which outputs a hypothesis in a subset of \( H_{F} \) in the
same model.

We now recap the setup of Haussler's agnostic sample complexity bounds
\cite{Haussler}.  The goal is to prove that for all hypotheses, \( H_{f} \), the empirical error, 
\( \hat{E}(H^{l}_{f},z^{N})=\frac{1}{N}\sum _{n=1}^{N}H_{f}^{l}(z_{n}) \), 
is close (in a way defined later) to the expected error, 
\( E(H^{l}_{f},P)=\int _{Z}H^{l}_{f}(z)dP(z) \), on a random example
drawn according to the distribution, \( P \), over examples. In order
to achieve this goal, it is necessary to have some measure of the size
of the hypothesis space. We first use the example distribution, \( P
\), to induce a metric, \( d_{P} \) on the hypothesis space:

\[
d_{P}(H^{l}_{f},H^{l}_{g})=\int _{X}\sup _{y\in Y}|H^{l}_{f}((x,y))-H^{l}_{g}((x,y))|dP_{|X}(x)\]


Here, \( P_{|X}(x) = \int _{Y}P(x,y)dy \) is the marginal distribution on X.

With this metric, we can define the size, \( N(\epsilon ,H_{F}^{l},d_{P}) \), of the loss space, \( H_{F}^{l} \), as the minimum
size of a subset of the elements such that all portions of the space are \( \epsilon  \) close
to some element in the subset as measured by \( d_{P} \). Formally, \( N(\epsilon ,H_{F}^{l},d_{P})=\inf _{S\subseteq H_{F}^{l}:\forall H^{l}_{f}\in H_{F}^{l}\exists s\in S:d_{P}(H_{f}^{l},s)\leq \epsilon }|S| \). Since we do not
know the distribution, we further define a capacity, \( C(\epsilon ,H_{F}^{l}) \), of the loss space as
the worst value of \( N(\epsilon ,H_{F}^{l},d_{P}) \) for all \( P \). Formally, \( C(\epsilon ,H_{F}^{l})=\sup _{P}N(\epsilon ,H_{F}^{l},d_{P}) \).

We measure the distance between the empirical and expected error using
 the \( d_{\nu } \) metric defined by, \( d_{\nu }(a,\textrm{
 }b)=\frac{|a-b|}{\nu +a+b} \).


\subsection{Extension of PAC framework to multiple tasks}

There is a simple extension of the PAC framework to multiple tasks
which centers around the observation that Hoeffding's inequality holds
for independent random variables with \emph{different} means \cite{8}.
Similar results have been derived by Baxter \cite{Baxter}.  This
variant allows for tasks with different numbers of examples and
requires less notational machinery.

The learning function can return a chain of hypotheses 
\( H_{f_{1}},...,H_{f_{j}} \), each of which is applied to some
(predetermined) portion of the examples. Let \( H_f^M \) denote a
chain of \( M \) hypothesis. The standard PAC bound will hold except
that the size of the hypothesis space drawn from will increase to 
\( H=H_{F_{1}}\times ...\times H_{F_{j}} \). With this bound, we will be
able to measure how well a hypothesis space learns a group of tasks
(by a ``task'', we mean the agnostic version of a target concept)
without needing enough examples to make \emph{each} task's empirical
error converge to it's true error for all hypothesis. As a side effect
we will also remove a requirement for the same number of
examples/task.

Let:

\begin{itemize}
\item \( M \) = the number of tasks
\item \( N_{m} \) = the number of examples for task \( m \)
\item \( N_{total}=\sum _{m=1}^{M}N_{m} \) = the total number of examples for all tasks. 
\item \( \hat{E}(H^{lM}_{f},z^{N_{total}})=\frac{1}{N_{total}}\sum _{m=1}^{M}\sum _{n=1}^{N_{m}}l(H_{f_{m}},z_{nm}) \) = empirical loss on the given sample.
\item \( E(H^{lM}_{f},P^{M})=\frac{1}{N_{total}}\sum _{m=1}^{M}N_{m}\int _{Z}l(H_{f_{m}},z_{m})dP_{m}(z_{m}) \) = expected loss when the \( m \)th hypothesis is weighted in proportion to \( N_m\).
\end{itemize}
With this notation in hand, we are ready to state the first theorem.

\subsection{Multitask Learning Theorem}

The Multitask Learning Theorem essentially states that we can
guarantee convergence between the average empirical error and average
true error with fewer examples then would be necessary to guarantee
convergence between empirical and true error on all tasks
individually.

\begin{thm}
Let \( H^{l}\subseteq H^{l}_{F_{1}}\times ...\times H^{l}_{F_{M}} \)
be a permissible set of chains of \( M \) functions each mapping \(
Z\rightarrow [0,1] \). Let each set of examples \( z_{1m}...z_{N_{m}m}
\) be generated according to a probability distribution, \( P_{m} \)
with \( N_{total}>\frac{2}{\alpha ^{2}\nu } \). \( \forall \nu
>0,0<\alpha <1 \),
\end{thm}

\[
P(z^{N}:\sup _{H^{l}}d_{\nu }(\hat{E}(H_{f}^{lM},z^{N_{total}}),E(H_{f}^{lM},P^{M})>\alpha )\]

\[
\leq 4C(\frac{\alpha \nu }{8},H^l)e^{\frac{-\alpha ^{2}\nu N_{total}}{8}}\]

\begin{proof}
See appendix B.
\end{proof}
This bound is quite useful in it's own right. The bound does not require a minimum
number of examples/task or a minimum number of tasks - the only constraint concerns
the total number of examples. The bound is useful when trying to prove the aggregate
convergence of the empirical error across multiple tasks to the true error across
multiple tasks. The bound is tighter (by a constant factor) than requiring each
task's empirical error converge to the true error.

\section{Learning to Learn}

The Staged Learning model is a generalization of the Learning to Learn
model. I will first introduce the Learning to Learn model and prove a
bound related to this model.  The proof is simplified version of
Baxter's proof which relies upon the Multitask Learning theorem with a
parameterization which allows trading off between the number of examples
per task and number of tasks.

In order to perform the analysis, we want to define mappings between
the Learning to Learn model and the Multitask Learning Theorem.

\subsection{Model}

The Learning to Learn model as introduced by Baxter\cite{Baxter} is a
two level hierarchy.  The model covered here is the same, although the
notation differs for the ease of the later description of the Staged
Learning model.  

At the top level, there is a space of hypothesis spaces, \( H_{FG} \), composed of hypothesis
spaces, \( H_{Fg} \), which contain individual hypotheses, \( H_{fg}:X\rightarrow Y \). In the Learning to Learn model, there is a probability distribution,
\( Q \), over all possible tasks (a task is a target function and data distribution). Drawing \( M \) times from \( Q \) 
produces a set of probability distributions, \( P^{M} \), which represent \( M \) unknown tasks.
From each task, \( P_{m} \), \( N \) labeled examples ( \(N_m = \) N in the previous theorem ), \( z^{N} \) are drawn. The input to a learning
to learn algorithm, \( L_{2}(H_{FG},z^{NM},L,l) \), is a space of hypothesis spaces, \( H_{FG} \), a set of sets of
labeled examples, \( z^{NM} \), a learning algorithm, \( L(H_{Fg},z_{m}^{N},l) \), and a loss function, \( l:(X\rightarrow Y)\times (X\times Y)\rightarrow [0,1] \), for a
hypothesis on an example. Output is a hypothesis space, \( H_{Fg} \), on which future tasks
will have an expected low loss. 

The loss function for the higher level learning problem is defined in terms
of the lower level loss function and the learning algorithm. \[ l_{2}(L,l,H_{Fg},z_{m}^{N})= \]
\[ \hat{E}(l(L(H_{Fg},z^{N},l),z_{nm})= \frac{1}{N}\sum _{n=1}^{N}l(L(H_{Fg},z_{m}^{N},l),z_{nm}) \] 
The higher level loss function allows us to compare hypothesis spaces based on their empirical
loss on a particular task. With this loss function, we can define the empirical
minimization algorithm at the higher level as: evaluate each hypothesis space
on each task and pick the hypothesis space with the lowest average error across
all tasks.

Now, we can define loss spaces at both the lower, \( H^{l}_{Fg}=\{l(H_{fg},\cdot ):H_{fg}\in H_{Fg}\} \), and upper, \( H_{FG}^{l_{2}}=\{l_{2}(L,l,H_{Fg},\cdot ):H_{Fg}\in H_{FG}\} \), levels in
the Learning to Learn model by partially evaluating the loss functions. Proving
a bound for the Learning to Learn model will involve two mappings onto the Multitask Learning
theorem, once for the choice of hypothesis space, and once for the \( M \) hypothesis
choices within a hypothesis space.


\subsection{Mapping}

This table gives the mappings of Learning to Learn problem down onto the PAC
problem, which is included for comparison. 

\( \begin{array}{cccc}
 & \textrm{PAC} & \textrm{L. to L.},\textrm{ level }1 & \textrm{L. to L.},\textrm{ level }2\\
\textrm{hypothesis space} & (H_{F})^{M} & \cup _{g}(H_{Fg})^{M} & H_{FG}\\
\textrm{loss function} & l & l & l_{2}\\
\textrm{loss space} & (H_{F}^{l})^{M} & \cup _{g}(H_{Fg}^{l})^{M} & H_{FG}^{l_{2}}\\
\textrm{example space} & Z^{N_{total}} & Z^{NM} & (Z^{N})^{M}\\
\textrm{training example} & z_{n} & z_{nm} & z_{m}^{N}\\
\textrm{example quantity} & N_{total} & NM & M\\
\textrm{probability distribution} & P^{M} & P^{M} & Q
\end{array} \)

These mappings will be explained in more detail below.


\subsection{Learning to Learn}

Let's recover Baxter's Learning to Learn results. The Learning to Learn algorithm
is: for each task, learn on each hypothesis space. Choose the hypothesis space
which produces the lowest empirical error across all tasks learned on it.

We want to know that the two Learning to Learn mappings (level 1 and level 2) satisfy
the assumptions of the Multitask Learning theorem.

\begin{lem}
The mapping for Learning to Learn, level 1: \( H^l = \cup _{g}(H_{Fg}^{l})^{M} \), \( Z = Z \), \( N_m = N \), \( M = M \), \( P_m = P_m \), and \( N_{total} = NM \)
is applicable to the Multitask Learning theorem.
\end{lem}
\begin{proof} The proof is by assertion. We require the Learning to Learn model to
be such that \( \forall g:H_{Fg}^{l} \) is permissible. \( Z \) is unchanged from the Multitask Learning model, and each \( P_{m} \)
is a probability distribution on \( Z \). Let \( H^{l}=\cup _{j}(H_{Fg})^{M}\subset (\cup _{j}H_{Fg})^{M} \). \( N_{total}=NM \). All of the preconditions of the
Multitask Learning theorem have been met.
\end{proof}

Now, we want to prove that we can learn an average empirical error which is a good estimate of the average true error.
We require the extra constraint that \( \forall m:\textrm{ }N_{m}=\frac{N_{total}}{M} \) because the learning function at the
next level will be using each \emph{task} as an example and we need each example
to have equal weight in the sum.  

\begin{cor}
\( \forall a_{1},b_{1}\in (0,1) \) if \( NM\geq \frac{8}{\alpha ^{2}a_{1}^{2}\nu }\ln \frac{4C(\frac{a_{1}\alpha \nu }{8},\cup _{j}(H^{l}_{Fg})^{M})}{b_{1}\delta } \) then with probability at least \( 1-\delta b_{1} \), the difference between the empirical
and true error of any hypothesis chain, \( (H_{fg}^{l})^{M} \) in the loss space, \( \cup _{j}(H^{l}_{Fg})^{M} \), will satisfy
\[ d_{\nu }(\hat{E}((H^{l}_{fg})^{M},P^{M}),E((H^{l}_{fg})^{M},z^{NM})\leq \alpha a_{1} \]
\end{cor}
\begin{proof} Application of the Multitask Learning theorem to the mappings in the lemma
\end{proof}

We need another constraint because it is possible to overfit our choice of hypothesis
space. The necessary constraint can be found by reducing the metalearning procedure
to a learning procedure which uses the base level learning procedure as a subroutine.
For the moment, let's assume the learning subroutine has no error, \( E(H_{fg}^{l},P_{m})=\hat{E}(H_{fg}^{l},z^{N}_{m}) \). The choice
of the ``best'' hypothesis space is governed by the learning problem indicated
by the 'Learning to Learn' mapping above. The second mapping views each draw
from \( Q \) as giving an example, \( z^{N} \), on which some loss in \( [0,1] \) is suffered. Each draw
from \( Q \) is independent, so we can apply the generalized Multitask Learning theorem
to each example.

\begin{lem}
The mapping for Learning to Learn, level 2: \( H^l = H_{FG}^{l_{2}} \), \( Z = Z^N \), \( N_1 = M \), \( M = 1 \), \( P_1 = Q \), and \( N_{total} = M \)
 is applicable to the Multitask Learning theorem.
\end{lem}
\begin{proof} Again, this is a proof by assertion. We require that \( H_{FG}^{l_{2}} \) be permissible.
\( Q \) induces a probability for each example, \( z^{N} \). \( H^{l}=H_{FG}^{l_{2}}\subset H_{FG}^{l_{2}} \).
\end{proof}

\begin{cor}
\( \forall a_{2},b_{2}\in (0,1) \) if 
\[
M\geq \frac{8}{a_{2}^{2}\alpha ^{2}\nu }\ln \frac{4C(\frac{a_{2}\alpha \nu }{8},H^{l_{2}}_{FG})}{\delta b_{2}}\]
 then with probability at least \( 1-\delta b_{2} \), the difference between the empirical and
true error of any hypothesis space on the hypothesis space space, \( H_{FG} \), will satisfy:
\[ d_{v}(E(H^{l_{2}}_{Fg},P),\hat{E}(H^{l_{2}}_{Fg},(z^{N})^{M}))\leq \alpha a_{2} \]
\end{cor}
\begin{proof} Application of the Multitask Learning theorem to the mappings in the lemma
\end{proof}

\begin{thm}
Assume that \( H_{Fg} \) and the loss function, \( l \), are such that \( H_{Fg}^{l} \) is permissible for all
\( H_{Fg}\in H_{FG} \). Also assume that \( H_{FG} \) and the loss function, \( l_{2} \), are such that \( H_{FG}^{l_{2}} \) is permissible.
Let \( Q \) be any probability distribution over probability distributions on \( Z \). Let
\( \nu >0, \) \( 0<\delta ,a_{1},b_{1},a_{2},b_{2}<1 \), \( a_{1}+a_{2}\leq 1 \), \( b_{1}+b_{2}\leq 1 \), and \( 0<\alpha <1 \). Also let \( (z^{N})^{M} \) be generated by \( M \) independent draws according to
\( Q \) each draw of which is used to draw \( N \) examples. If \( N\geq \frac{1}{M}\frac{8}{a_{1}^{2}\alpha ^{2}\nu }\ln \frac{4C(\frac{a_{1}\alpha \nu }{8},\cup _{g}(H^{l}_{Fg})^{M})}{\delta b_{1}} \) and \( M\geq \frac{8}{a_{2}^{2}\alpha ^{2}\nu }\ln \frac{4C(\frac{a_{2}\alpha \nu }{8},H^{l_{2}}_{FG})}{\delta b_{2}} \) then 
\[ P(\exists H_{Fg}\in H_{FG}:d_{\nu }(E(H^{l_{2}}_{Fg},P),\hat{E}(H^{l_{2}}_{Fg},z^{N}))>\alpha )\leq \delta  \] 
\end{thm}
\begin{proof} Just apply the two lemmas above with the triangle inequality.
\end{proof}

\subsection{Comparison}

Learning to Learn can be a big win in some situations, but there is a
constant overhead (in number of examples required) when it is applied
to degenerate cases where a PAC bound could be applied.

\subsubsection{Comparison with previous work}

It's worth comparing this result with Baxter's work. If we set \( a_{1}=a_{2}=b_{1}=b_{2}=\frac{1}{2} \), we recover
exactly Baxter's Learning to Learn bound. The extra parameters allow us to trade
off between the number of tasks and the number of examples/task for any particular
application.


\subsubsection{Comparison with extremes}

Several interesting extreme cases arise in Learning to Learn. 

One interesting case is where each \( H_{Fg} \) contains just one hypothesis. Then the
total number of examples required is \( N_{total}=NM\geq \frac{8}{a_{1}^{2}\alpha ^{2}\nu }\ln \frac{4C(\frac{\alpha a_{1}\nu }{8},H^{l_{2}}_{FG})}{\delta b_{1}} \). The same problem can be analyzed in
the PAC framework which requires only \( N_{total}\geq \frac{8}{\alpha ^{2}\nu }\ln \frac{4C(\frac{\alpha \nu }{8},H^{l}_{G})}{\delta } \) examples, a savings by a factor of approximately
\( \frac{\ln \frac{1}{b_{1}}}{a_{1}^{2}} \) neglecting changes in capacity. There is some cost to misusing the learning
to learn model. 

On the other hand, consider a case in which there exist many tasks known to
come from a large space, \( \cup _{g}H_{Fg} \), and also known to be 'related' (which in this case
means all the tasks can be learned well on a small subset of the hypothesis
space). If one carves up the large space, \( \cup _{g}H_{Fg} \), into many equal size smaller spaces, \( H_{Fg} \),
and apply the Learning to Learn theorem. In this case, with \( N_{total}=NM\geq \frac{8}{\alpha ^{2}a_{1}^{2}\nu }\ln \frac{4C(\frac{\alpha a_{1}\nu }{8},\cup _{g}(H^{l}_{Fg})^{M})}{\delta b_{1}} \) we can be confident
that the next task will be easily learnable with \( N \sim \frac{\ln C(\epsilon ,\cup _{g}(H^{l}_{Fg})^{M})}{\ln C(\epsilon ,H^{l}_{FG}) } \) examples. In the PAC case,
we will always have to use the capacity of the larger space, \( N_{total}\geq \frac{8}{\alpha ^{2}\nu }\ln \frac{4C(\frac{\alpha \nu }{8},\cup _{g}H^{l}_{Fg})}{\delta } \) to learn. Ignoring
constant factors, the number of examples required per task can be much larger
in the PAC setting then in the Learning to Learn setting.

\section{Staged Learning}

\subsection{Model}

Staged Learning is the natural extension to Learning to Learn to Learn
... to Learn.  In the Staged Learning setting, one is given a set of set
of ... sets of hypotheses, \( H_{FG...HI} \), and wish to guarantee
that any set of ... sets of hypotheses, \( H_{FG...Hi} \), will have an
empirical error close, \( (\alpha ,\textrm{ }\delta ) \), to the true
expected error on future sets of ... sets of examples, \(
x^{NML....}_{k} \). Labeled examples, \( z^{NML...K} \), are drawn
from a distribution, \( R \) over distributions over ... distributions
over examples, which is used to draw a set, \( S^{L} \), over sets of
... sets of examples.  The \( S_{l} \) are each used to draw a \(
T^{K} \), and the process is repeated inductively until examples are
drawn at the base level. 'Staged Learning' was chosen as a name
because the learning is done in stages where the entropy of the choice
of a hypothesis function is gradually reduced to 0. In the Staged
Learning setup, the learning algorithm at the highest level, \(
L_{D}(H_{FG...I},z^{NML...K},l,L,...) \), takes a set of set of
... sets of hypotheses, a set of set of ... sets of examples, a loss
function of a hypothesis applied to a labeled example, and learning
algorithms for each level in the hierarchy below the top.

The loss function at the lowest level, \( 1 \), and the next level, \( 2 \), are the same
as in the Learning to Learn case, \[ l_{2}(L,l,H_{Fg...i},z^{N}_{ml...k})= \hat{E}(l(L(H_{Fg...i},z^{N}_{ml...k},l),z_{nml....k}) \] At the next level up in the hierarchy,
the loss function, \[ l_{3}(L_{2},L,l,H_{FG...i},z^{NM}_{l...k})=\hat{E}(l_{2}(L,l,L_{2}(H_{FG...i},z^{NM}_{l...k},l,L),z^{N}_{ml...k})) \] is the average empirical loss across a set of set of tasks.
The loss functions for the higher functions are defined recursively in this
manner until the \( d \)th loss function, \[ l_{D}(L_{D-1},...,L,l,H_{FG....i},z^{NML...}_{k})\] 
\[ =\hat{E}(l_{D-1}(L_{D-2},...,L,l,L_{D-1}(H_{FG...i},z^{NML...}_{k},l,L,...,L_{D-2}),z^{NML...}_{k})) \] is reached. For the purposes of the
proof, we will once again partially apply the loss function to the hypothesis
space in order to get a loss space at level \( 1 \), \[ H^{l}_{Fg...i}=\{l(H_{fg...i},\cdot ):H_{fg...i}\in H_{Fg...i}\} \] level \( 2 \), \[ H_{FG...i}^{l_{2}}=\{l_{2}(L,l,H_{Fg...i},\cdot ):H_{Fg...i}\in H_{FG...i}\} \] ..., and level
\( d \), \[ H_{FG...I}^{l_{D}}=\{l_{D}(l,L_{2},...,H_{FG...i},\cdot ):H_{FG...i}\in H_{FG...I}\} \]

\subsection{Mapping}

The mappings are straightforward now. 

\[ \begin{array}{cccc}
 & \textrm{Staged},\textrm{ level }1 & \textrm{Staged},\textrm{ level }d & \textrm{ level }D\\
\textrm{hyp. space} & \cup _{i} (...\cup _{h}(\cup _{g}(H_{Fg...i})^{M})^{L}...)^{K} & \cup _{i}(...\cup _{h}(H_{F...Gh...i})^{L}...)^{K} & H_{FG...I}\\
\textrm{loss fun.} & l & l_{d} & l_{D}\\
\textrm{loss space} & \cup _{i} (...\cup _{h}(\cup _{g}(H_{Fg...i}^{l})^{M})^{L}...)^{K} & \cup _{i}(...\cup _{h}(H_{F...Gh...i}^{l_{d}})^{L}...)^{K} & H_{FG...I}^{l_{D}}\\
\textrm{ex. space} & Z^{N}_{ml...k} & Z_{l...k}^{N...M} & Z^{NML...K}\\
\textrm{example} & z_{nml...k} & z^{N...}_{ml...k} & z^{NML...}_{k}\\
\textrm{\# ex.} & NML...K & ML...K & K\\
\textrm{dist.} & P^{M...K} & Q^{L...K} & R
\end{array} \]


\subsection{Distribution convergence theorem}

\begin{lem}
Each of the mappings defined above: \( H^l = \cup _{i}(...\cup _{h}(H_{F...Gh...i}^{l_{d}})^{L}...)^{K} \), \( Z = Z^{N...M}_{l...k} \), \( N_m = M \), \( M = L...K \), \( P_m = Q_{l...k} \), and \( N_{total} = ML...K \)
 can be applied to the Multitask Learning theorem.
\end{lem}
\begin{proof} Again, by assertion. We will require that all hypothesis loss spaces
be such that they are permissible. \( N_{total} \) will be the example quantity given. In
all cases \( H^{l} \) is the loss space given in the map. Notice that the loss space is
always a subset of \( (\cup _{g...i}H_{Fg...i})^{M...K} \).
\end{proof}
\begin{thm}
With a hierarchical nesting of hypothesis spaces, \( H_{FG...I} \), a loss function, \( l \), and
algorithms for learning at lower levels, \( L \), \( L_{2} \), ..., \( L_{D-1} \) such that all loss spaces,
\( H^{l_{D}}_{F..Gh...i} \) are permissible, \( R \) a probability distribution over distributions over ...
over the space of labeled examples, \( Z \), \( \forall  \) \( \nu >0, \) \( 0<\delta <1, \) \( 0<\alpha <1, \) \( a_{i},b_{i}\in [0,1]:\sum _{i=1}^{D}a_{i}\leq 1,\sum _{i=1}^{D}b_{i}\leq 1 \) and \( z^{NML...K} \) generated according to
the Staged Learning model, if 
\[ N\geq \frac{1}{ML...K}\frac{8}{\alpha ^{2}a_{1}^{2}\nu }\ln \frac{4C(\frac{\alpha a_{1}\nu }{8},\cup _{i}(...\cup _{h}(\cup _{g}(H^{l}_{Fgh...i})^{M})^{L}...)^{K})}{\delta b_{1}} \] 
\[ M\geq \frac{1}{L...K}\frac{8}{\alpha ^{2}a_{2}^{2}\nu }\ln \frac{4C(\frac{\alpha a_{2}\nu }{8},\cup _{i}(...\cup _{h}(H^{l_{2}}_{FGh...i})^{L}...)^{K})}{\delta b_{2}} \] ..., and 
\[ K\geq \frac{8}{\alpha ^{2}a_{D}^{2}\nu }\ln \frac{4C(\frac{\alpha a_{D}\nu }{8},H^{l_{D}}_{FG...I})}{\delta b_{D}} \] then 
\[ P(\exists H_{F...Gi}\in H_{F...GI}:b_{\nu }(E(H^{l_{D}}_{F...Gi},P),\hat{E}(H^{l_{D}}_{F...Gi},z^{NML...K}))>\alpha )\leq \delta  \] 
\end{thm}
\begin{proof}
A chain of \( D-1 \) applications of the triangle inequality for \( d_{\nu } \).
\end{proof}

\subsection{Generalizations}

All of the bounds here apply to the agnostic case: there is no need to guarantee
that there exists a 'perfect' (zero loss) choice. If such a guarantee can be
made, then all of the arguments above can be made with a Multitask Learning theorem
for the realizable case which allowing tighter bounds.


\section{Examples}

Examples of situations where Learning to Learn can be useful are fairly common
- any time there is a group of tasks which exploit some common substructure
Learning to Learn may be useful. Many other people\cite{Thrun} have covered these examples. 
When is the full Staged Learning model necessary?

\subsection{Species recognition}

Given the hierarchy present from kingdom to species in nature, it
wouldn't be unreasonable to hope that starting with an 'ape family'
biased hypothesis space significantly better generalization on the
task of 'recognizing a chimpanzee' could be achieved.  In this
application, the tradeoff between the number of examples/task, tasks,
... would be very useful because typically the number of members of a
species is much greater than the number of species in a family.

\subsection{Information hierarchies}

One of the more practical uses of Staged Learning may lie in the direction of
using information hierarchies (indices) which are already existent on the Internet.
Many indices are organized in a hierarchical fashion. Constructing a recognizer
for each leaf of the hierarchy would be useful because it is rather expensive
to build human made hierarchies of information. One approach to this is the
use of a naive Bayes model by McCallum\cite{7} and others. Essentially, one starts with
some hierarchically organized documents. At each node in the hierarchy, the
word frequency in all children is calculated. Then a set of mixture weights,
\( \lambda _{1},\textrm{ }...,\textrm{ }\lambda _{root},\textrm{ }\lambda _{uniform} \) s.t. \( \sum _{i}\lambda _{i}=1 \) is calculated using an EM method giving a final probability of a word
in a document which is:


\[
P(word|class)=\]
 
\[
\lambda _{1}P(word|N_{1})+\lambda _{2}P(word|N_{2})+...+\lambda _{root}P(word|root)+\lambda _{uniform}\frac{1}{|dict|}\]


Here \( N_{i} \) = the node at level \( i \) on a path from the class to the root.

A classification is made by multiplying all probabilities of all occurring words
in each document and choosing the class with the highest probability. If we
assume that \( \lambda _{i}>\epsilon >0 \) for some \( \epsilon >0 \) (in practice none of the \( \lambda _{i}=0 \)) then this method fits into
the Staged Learning model. To see this, start at the root of the hierarchy. The classifier
can have \( P(word|class)\in [\lambda _{uniform}P_{uniform}(word),(1-\lambda _{uniform})(1-P_{uniform}(word))] \). At the next level down, the range of possible classifiers becomes
further constrained, and so on until the final class is reached. We can then
view the learning problem as choosing between a hierarchy of classes where each
level of the hierarchy is parameterized by the relative frequency of words in
the child classes. \( H_{F...Gh...i} \) will range over all the possible word frequencies of children
of a node at level \( k \). 


\subsection{Boolean variables}

Restricting to the discrete case on boolean variables a simple
complete analysis can be done. Assume we have a depth of \( 3 \) and
the input is \( n \) variables. We know that each task (target
concept) depends on only \( 3 \) variables.  The tasks are grouped
into families where the tasks of each family depend on \( 10 \)
variables associated with that family.  There are several families of
tasks.  How many families of examples/task, tasks/family, and families
do we need to learn which set of \( 10 \) variables the families
depend on?  We will find that the number of tasks per task family
needed to learn a hypothesis space will be noticeably smaller when
using the staged learning model then when using the Learning to Learn
model on each task family.

There are \( 2^{2^{n}} \) functions on \( n \) variables, \( 2^{2^{10}} \) functions on \( 10 \) variables, and \( 2^{2^{3}}=256 \) functions
on \( 3 \) variables. There are \( n\textrm{ choose }10\leq (\frac{ne}{10})^{10} \) possible sets of \( 10 \) variables in \( n \) and \( 10\textrm{ choose }3=120 \) possible sets
of \( 3 \) variables in \( 10 \). 

\begin{itemize}
\item Let \( H_{Fgh} \) = all \( 256 \) functions over a set of \( 3 \) variables determined by \( g \) and \( h \). 
\item Let \( H_{FGh} \) = a set composed of the possible settings of \( 3 \) variables in \( 10 \) determined
by \( h \). 
\item Let \( H_{FGH} \) = a set composed of all choices of \( 10 \) variables. 
\end{itemize}
Then we have:
\begin{itemize}
\item \( |H_{Fgh}|\leq 2^{8} \)
\item \( |\cup _{g}(H_{Fgh})^{M}|\leq 3*5*2^{8M+3} \)
\item \( |\cup _{h}(\cup _{g}(H_{Fgh})^{M})^{K}|\leq 3^{K}*5^{K}*2^{8MK+3K}(\frac{ne}{10})^{10} \)
\item \( |\cup _{h}(H_{FGh})^{K}|\leq 3^{K}*5^{K}*2^{3K}(\frac{ne}{10})^{10} \)
\item \( |H_{FGH}|\leq (\frac{ne}{10})^{10} \)
\end{itemize}

With the capacities defined, we only need to set the
values of \( a_{1}=a_{2}=a_{3}=b_{1}=b_{2}=b_{3}=\frac{1}{3} \) to apply the bound.

If \[ N\geq \frac{1}{MK}\frac{9*8}{\alpha ^{2}\nu }\ln \frac{3^{K+1}5^{K}2^{8MK+3K+2}(\frac{ne}{10})^{10}}{\delta } \] 
\[ M\geq \frac{1}{K}\frac{9*8}{\alpha ^{2}\nu }\ln \frac{3^{K+1}5^{K}2^{3K+2}(\frac{ne}{10})^{10}}{\delta } \] 
and \[ K\geq \frac{9*8}{\alpha ^{2}\nu }\ln \frac{2^{2}3(\frac{ne}{10})^{10}}{\delta } \] then 
\[ P(\exists H_{FGh}\in H_{FGH}:b_{\nu }(E(H^{l_{D}}_{FGh},P),\hat{E}(H^{l_{D}}_{FGh},z^{NMK}))>\alpha )\leq 1-\delta  \] 
Working the numbers out more explicitly we need \( K\geq \frac{3^{2}2^{3}}{\alpha ^{2}\nu }(\ln \frac{2^{2}3}{\delta }+10\ln \frac{ne}{10}) \), \( M\geq \frac{1}{K}\frac{9*8}{\alpha ^{2}\nu }(\ln \frac{2^{2}3}{\delta }+K\ln 3*5*2^{3}+10\ln \frac{ne}{10}) \),
and \( N\geq \frac{1}{MK}\frac{9*8}{\alpha ^{2}\nu }(\ln \frac{2^{2}3}{\delta }+10\ln \frac{ne}{10}+K\ln 3*5+K(8M+3)\ln 2) \). 

How does this compare with the PAC bound? The most straightforward
application of the PAC bound will require making a choice from a very large space of size \( 2^{2^n} \).  The log capacity of this space is \( 2^n \).
A smarter application of the PAC bound would note that only \(
\left( \begin{array}{c} n\\ 3
\end{array}\right)  \)\( 2^{2^{3}} \) \( \leq 2^{8}n^{3} \) hypothesis are possible with a log capacity bounded by \( 8\ln 2+3\ln n \).

Learning to Learn can do much better.  The Learning to Learn algorithm must choose between  \(
\left( \begin{array}{c} n\\ 3
\end{array}\right)  \) \( \leq n^{3} \) hypothesis spaces with a log capacity bounded by \( 3\ln n \).  
After this choice is made, individual hypothesis are chosen from a set
of \( 2^8 \) choices with a log capacity of \( 8\ln 2 \), much lower
then the results of the PAC bound.

Depth 3 staged learning lowers the number of tasks required to learn
which 3 variables are important.  We must make a choice between a set
of hypothesis sets of size \( \left( \begin{array}{c} n\\ 10
\end{array}\right)  \) \( \leq n^{10} \) with a log capacity of \( 10 \ln n \).
After this choice is made, Learning to Learn can be applied to \(
O(10^{3}) \) hypothesis spaces with log capacity of \( 3\ln {10} \), a
noticeably improvement over the pure Learning to Learn case.  

Learning to Learn reduces the number of examples required per task and
Staged Learning reduces the number of tasks required in Learning to
Learn.

\subsection{Deep neural nets}

As mentioned in the introduction, the Staged Learning model suggests
the use of deep feed forward neural nets or, more generically, chained
nonlinear feature detectors. Assume that a neural net implements a
staged learning model by freezing weights to restrict the available
hypothesis space as you move from the root to a leaf. The choice of
which weights to freeze is arbitrary and the analysis can work for
unnatural choices of weights. However, the natural choice of which
weights to freeze corresponds to freezing weights a level or two at a
time starting at the first hidden layer and proceeding towards the
output as you move through the hierarchy from the root to a particular
task.

In light of this, it is interesting to notice that top efforts in
character recognition \cite{Le Cun} employ a deep feed forward
net. The first couple layers of this feed forward net can be useful
in recognizing a new language \cite{CDM}.

\section{Conclusion and Discussion}

Hierarchies of related tasks arise naturally in many domains, but
previous bounds were unable to take the information contained in the
hierarchy fully into account.  We have defined and proved a bound for
the Staged Learning model.  Along the way, we also proved a more
flexible bound for the Learning to Learn model and proved a theorem
relevant to Multitask learning.  All of these proofs were made eaiser
by working explicitly in the loss space.

There is another problem suggested by Staged Learning, that of
automatically deducing hierarchies. The extra information contained in
an a. priori hierarchy can be rather expensive to produce. It would be
nice to create hierarchies automatically by unsupervised learning
techniques and a theoretical understanding of this process would be
very useful. An EM analysis between these two techniques could prove
fruitful.

The analysis in this paper is entirely theoretical. One nice aspect of
the theoretical analysis is no particular learning algorithm is
required at any level in the hierarchy (in fact, a different learning
algorithm could be used at every level in the
hierarchy). Unfortunately, the theoretical analysis is only an upper
bound. I believe that a lower bound on the number of tasks required
can not be proved without some definition of 'relatedness'.  Consider
the single task distribution which draws the same task every time.
Clearly, only one task need be drawn, although many examples from the
one task may be required.  On the other hand, A distribution over many
tasks could require many samples in order to find a confident estimate
of the learnability of the task distribution by a particular
hypothesis space.  A lower bound on the number of examples required
has been proved \cite{Baxter}.

It would be nice to remove the requirement that each task have the
same minimum number of examples and get a bound which is more
adaptive.  I'm convinced that this is possible using variables with
nonidentical ranges in the Hoeffding bounds.

{\bf Acknowledgements}: I would like to thank Jon Baxter, Avrim Blum,
and Sebastian Thrun whose comments where indispensable in making this
paper coherent.

\newpage

\section*{Notation Appendix}

In general, superscripts denote cross products and subscripts denote
``modifier'' or ``member of''. Capitols denote a full range and
lower case denotes a member of a range.

Here are some examples:

\begin{itemize}
\item \( x^{N} \), a set (of input examples)
\item \( x_{n} \), a member of a set (of input examples)
\item \( H_{F} \), a set (of hypothesis)
\item \( H_{f} \), a member (hypothesis) of a set (of hypothesis)
\end{itemize}
To get nested sets, I add extra indices:

\begin{itemize}
\item \( x^{N_{total}} \), a set (of input examples possibly drawn from multiple tasks)
\item \( x_{m}^{N} \), a set (of input examples for the \( m \)th task) 
\item \( x^{NM} \) a set of sets of input examples.
\item \( P^{M} \), a set (of probability distributions over examples)
\item \( H_{FG} \), a set (of hypothesis sets) of sets (of hypothesis)
\item \( H_{Fg} \), a member (hypothesis space) of a set of sets (of hypothesis)
\end{itemize}
An arbitrary nesting looks like:

\begin{itemize}
\item \( H_{FG...I} \), a set of sets of ... of sets (of hypothesis)
\item \( H_{FG...Hi} \), a member of a set of sets of ... of sets (of hypothesis)
\end{itemize}
I associate a particular level in the hierarchy of nested sets with a particular
position in the indices. The first index corresponds to the deepest level.
Thus:

\begin{itemize}
\item \( x_{nm...lk} \), the \( n \)th element of the ... of the \( m \)th element of the \( l \)th set of sets of ...
of sets (of input examples)
\item \( H_{Fg...i} \), a member of ... a member of a set of sets of ... of sets (of hypothesis)
= a set (of hypothesis).
\end{itemize}
It is often useful to get the size of a particular finite set. To indicate the
size of a set, I use the index. Thus, \( N=|x^{N}| \) and \( M=|(x^{N})^{M}| \) denote the number of examples
and example sets respectively.

The notation for multiple tasks:

\begin{itemize}
\item \( N_{m} \) = number of examples for task \( m \)
\item \( N_{total}=\sum _{m=1}^{M}N_{m} \) = total number of examples for all tasks. 't' for ``total''
\item \( \hat{E}(H^{M}_{f},z^{N})=\frac{1}{N}\sum _{m=1}^{M}\sum _{n=1}^{N_{m}}l(H_{f_{m}},z_{nm}) \)
\item \( E(H^{M}_{f},P^{M})=\frac{1}{N}\sum _{m=1}^{M}N_{m}\int _{Z}l(H_{f_{m}},z_{m})dP_{m}(z_{m}) \)
\end{itemize}

\subsection{Learning depth}

The proofs often involve learning bias at some depth, \( d \).

\subsection{Learning algorithms.}

The lower order learning algorithms are arguments to the higher order learning
algorithms. It does not matter what the lower order learning algorithms are
as long as they are deterministic. 

\begin{itemize}
\item \( L \), a learning algorithm
\item \( L_{2} \), a Learning to Learn algorithm
\item \( L_{D} \), a Staged Learning algorithm at depth \( d \)
\end{itemize}

\subsection{Loss function}

Loss functions at various depths are necessary to measure the convergence of
distributions.

\begin{itemize}
\item \( l(H_{f},z_{n})=l(H_{f},(x_{n},y_{n}))=l(H_{f}(x_{n}),y_{n}) \) PAC model loss function
\item \( l_{2}(L,l,H_{Fg},z_{m}^{N})= \) \( \hat{E}(l(L(H_{Fg},z_{m}^{N},l),z_{nm})= \) \( \frac{1}{N}\sum _{n=1}^{N}l(L(H_{Fg},z^{N}_{m},l),z_{nm}) \) Learning to Learn top level loss function
\item \( l_{D}(L_{D-1},...,L,l,H_{FG...Hi},z^{NM...L}_{k}) \) 
\[ =\hat{E}(l_{D-1}(L_{D-2},...,L,l,L_{D-1}(H_{FG...Hi},z^{NM...L}_{k},l,L,...,L^{d-2}),z^{NM...L}_{k})) \] Staged Learning loss function at the highest level
\end{itemize}

\subsection{Loss spaces}

With a loss function and hypothesis space, we can define loss spaces.

\begin{itemize}
\item \( H^{l}_{F}=\{l(H_{f},\cdot ):H_{f}\in H_{F}\} \) loss hypothesis space for PAC model.
\item \( H_{FG}^{l_{2}}=\{l_{2}(L,l,H_{Fg},\cdot ):H_{Fg}\in H_{FG}\} \) loss hypothesis space for top level Learning to Learn model.
\item \( H_{FG...I}^{l_{D}}=\{l_{D}(l,L_{2},...,H_{FG...Hi},\cdot ):H_{FG...Hi}\in H_{FG...HI}\} \) loss hypothesis space for the highest level in a Staged Learning model.
\end{itemize}

\subsection{Error}

There are two kinds of error at each level in the hierarchy.

\begin{itemize}
\item \( \hat{E}(H^{l_{D}}_{F...Gh...i},z^{N...M}_{l...k})=\frac{1}{M}\sum _{m=1}^{M}H^{l_{D}}_{F...Gh...i}(z^{N...}_{ml...k}) \) empirical error
\item \( E(H^{l_{D}}_{F...Gh...i},P)=\int _{Z}H^{l_{D}}_{F...Gh...i}dP(z^{N...}_{ml...k}) \) expected error
\end{itemize}

\section*{Proof of Multitask Learning Theorem}

The proof of the Multitask Learning theorem is broken up into 3 lemmas similar to Haussler\cite{Haussler} and Baxter\cite{Baxter}.

Make two identical draws of \( z^{N_{total}} \), labeled as \( z^{N_{total}}_{1} \) and \( z^{N_{total}}_{2} \).

\begin{lem}
Let \( H^{l} \) be a permissible set of chains of \( M \) functions. Let \( P^{M} \) be \( M \) probability
measures on \( Z \). \( \forall \nu >0,\textrm{ }0<\alpha <1 \) with \( N_{total}\geq \frac{2}{\alpha ^{2}v} \), 
\[
P(z^{N_{total}}:d_{\nu }(\hat{E}(H_{f}^{lM},z^{N_{total}}),E(H_{f}^{lM},P^{M}))>\alpha )\]
 
\[
\leq 2P(z_{1}^{N_{total}},z_{2}^{N_{total}}:d_{\nu }(\hat{E}(H_{f}^{lM},z_{1}^{N_{total}}),\hat{E}(H_{f}^{lM},z_{2}^{N_{total}}))>\frac{\alpha }{2})\]
 
\end{lem}
\begin{proof}
permissibility implies measurability of \( H^l \) guarantees the measurability of suprema
over \( H^l \). The triangle inequality for \( d_{\nu } \) implies
\[
P(z_{1}^{N_{total}},z_{2}^{N_{total}}:d_{\nu }(\hat{E}(H_{f}^{lM},z_{1}^{N_{total}}),\hat{E}(H_{f}^{lM},z_{2}^{N_{total}}))>\frac{\alpha }{2})\]
 
\[
\geq P(z_{1}^{N_{total}},z_{2}^{N_{total}}:d_{\nu }(\hat{E}(H_{f}^{lM},z_{1}^{N_{total}}),E(H_{f}^{lM},P^{M}))>\alpha \textrm{ and }\]
\[ d_{\nu }(\hat{E}(H_{f}^{lM},z_{2}^{N_{total}}),E(H_{F}^{lM},P^{M}))<\frac{\alpha }{2})\]
 

By Chebyshev's inequality, for a fixed \( H_{f}^{lM} \),
\[
P(z^{N_{total}}:d_{\nu }(\hat{E}(H_{f}^{lM},z^{N_{total}}),E(H_{f}^{lM},P^{M}))<\frac{\alpha }{2})\]
 
\[
\geq P(z^{N_{total}}:\frac{|\hat{E}(H^{lM}_{f},z^{N_{total}})-E(H_{f}^{lM},P^{M})|}{\nu }<\frac{\alpha }{2})\]
 
\[
\geq 1-\frac{\sum _{m=1}^{M}N_{m}E(H^l_{f_{m}},P_{m})(1-E(H^l_{f_{m}},P_{m}))}{N_{total}^{2}\nu \frac{\alpha ^{2}}{4}}\]
 
\[
\geq 1-\frac{1}{N_{total}\nu \alpha ^{2}}\]
 
\[
\geq \frac{1}{2}\]
 

if \( N_{total}\geq \frac{2}{\alpha ^{2}\nu } \)
\end{proof}
Next we need to define a permutation group between the elements of \( z^{N_{total}}_{1} \) and \( z_{2}^{N_{total}} \) so
that we can bound the distance between the loss of these two samples under the
permutation group. We will first define the permutation group between the examples
of each task and then define the permutation group on all tasks, \( \Gamma _{2N_{total}} \), as the direct
product of each of the permutation groups of each task.

For each task with \( N_{m} \) examples, define \( \Gamma _{2N_{m}} \) as the permutation group between each
task. \( \Gamma _{2N_{m}} \) is in turn defined as the \( N_{m} \) way direct product of \( \Gamma _{2} \), the permutation
group on 2 elements. \( \Gamma _{2} \) has 2 elements, \( \sigma _{0}:\{0,1\}\rightarrow \{0,1\} \) and \( \sigma _{1}:\{0,1\}\rightarrow \{0,1\} \) defined by \( \sigma _{1}(i)=1-i \) and \( \sigma _{0}(i)=i \). Now, we define
\( \Gamma _{2N_{m}} \) \( =\prod _{n=1}^{N_{m}}\Gamma _{2} \) as the direct product of \( N_{m} \) \( \Gamma _{2} \) groups and then we define \( \Gamma _{2N_{total}}=\prod _{m=1}^{M}\Gamma _{2N_{m}} \) as the direct product
between all of the \( N_{m} \)'s.

Let \( \sigma \in \Gamma _{2N_{total}} \) denote an element from the permutation group and 
\( z_{\sigma (1)}^{N_{total}},z_{\sigma (2)}^{N_{total}} \) a permutation applied
between the elements of \( z^{N_{total}}_{1},\textrm{ }z^{N_{total}}_{2} \).

{\bf Define}: \( H_{f}^{lM} \) as a set of \( M \) functions, one drawn from each \( H^l_{F_{m}} \).

Define: \( d_{z^{2N_{total}}}(H_{f}^{lM},H_{g}^{lM}) \)
\[ =\frac{1}{2N_{total}}\sum _{m=1}^{M}\sum _{n=1}^{N_{m}}|H^{l}_{f_{m}}(z_{1nm})-H^{l}_{g_{m}}(z_{1nm})| + |H^{l}_{f_{m}}(z_{2nm})-H^{l}_{g_{m}}(z_{2nm})| \]

\begin{lem}
Let \( H^l \subset H^l_{F_{1}}\times ...\times H^l_{F_{M}} \) be a permissible set of chains of functions as in the Multitask Learning
Theorem. Fix \( z_{1}^{N_{total}},z_{2}^{N_{total}} \) and let \( C=\{g^l_{1},...,g^l_{K}\} \) be an \( \frac{\alpha \nu }{8} \) cover for \( (H^l,d_{z^{2N_{total}}}) \) then 

\[ P(\sigma :\sup _{H}d_{\nu }[\hat{E}(H_{f}^{lM},z_{1}^{N_{total}}),\hat{E}(H_{f}^{lM},z_{2}^{N_{total}})]>\frac{\alpha }{2}) \]


\[ \leq \sum _{k=1}^{K}P(\sigma :d_{\nu }[\hat{E}(g_{f}^{lM},z_{1}^{N_{total}}),\hat{E}(g_{f}^{lM},z_{2}^{N_{total}})]>\frac{\alpha }{4}) \]

with each \( \sigma  \) chosen uniformly from \( \Gamma _{2N_{total}} \).
\end{lem}
\begin{proof}
Fix \( \sigma  \) and let \( H_{f}^{lM} \) be such that \( d_{\nu }[\hat{E}(H_{f}^{lM},z_{1}^{N_{total}}),\hat{E}(H_{f}^{lM},z_{2}^{N_{total}})]>\frac{\alpha }{2} \). Choose \( f_{k}=g_{f}^{lM}\in C \) such that \( d_{z^{2N_{total}}}(H_{f}^{lM},g_{f}^{lM})\leq \frac{\alpha \nu }{8} \). In this case:


\[
\frac{2}{\nu }d_{z^{2N_{total}}}(H_{f}^{lM},\textrm{ }g_{f}^{lM})\]



\[
=\frac{\sum _{m=1}^{M}\sum _{n=1}^{N_{m}}|H^{l}_{f_{m}}(z_{1nm})-g^{l}_{f_{m}}(z_{1nm})|+|H^{l}_{f_{m}}(z_{2nm})-g^{l}_{f_{m}}(z_{2nm})|}{\nu N_{total}}\]



\[
=\frac{\sum _{m=1}^{M}\sum _{n=1}^{N_{m}}|H^{l}_{f_{m}}(z_{\sigma (nm)})-g^{l}_{f_{m}}(z_{\sigma (nm)})|+|H^{l}_{f_{m}}(z_{\sigma (nm)})-g^{l}_{f_{m}}(z_{\sigma (nm)})|}{\nu N_{total}}\]



\[
=\frac{\sum _{m=1}^{M}\sum _{n=1}^{N_{m}}|H^{l}_{f_{m}}(z_{\sigma (nm)})-g^{l}_{f_{m}}(z_{\sigma (nm)})|+\sum _{m=1}^{M}\sum _{n=1}^{N_{m}}|H^{l}_{f_{m}}(z_{\sigma (nm)})-g^{l}_{f_{m}}(z_{\sigma (nm)})|}{\nu N_{total}}\]


\[
\geq \frac{\sum _{m=1}^{M}\sum _{n=1}^{N_{m}}|H^{l}_{f_{m}}(z_{\sigma (nm)})-g^{l}_{f_{m}}(z_{\sigma (nm)})|}{\nu N_{total}+\sum _{m=1}^{M}\sum _{n=1}^{N_{m}}|H_{f_{m}}^{l}(z_{\sigma (nm)})-g_{f_{m}}^{l}(z_{\sigma (nm)})|}\]

\[
+\frac{\sum _{m=1}^{M}\sum _{n=1}^{N_{m}}|H^{l}_{_{f_{m}}}(z_{\sigma (nm)})-g^{l}_{f_{m}}(z_{\sigma (nm)})|}{\nu N_{total}+\sum _{m=1}^{M}\sum _{n=1}^{N_{m}}|H_{_{f_{m}}}^{l}(z_{\sigma (nm)})-g_{f_{m}}^{l}(z_{\sigma (nm)})|}\]



\[
=d_{\nu }(\hat{E}(H_{f}^{lM},z_{\sigma (1)}^{N_{total}}),\hat{E}(g_{f}^{lM},z_{\sigma (1)}^{N_{total}}))+d_{\nu }(\hat{E}(H_{f}^{lM},z_{\sigma (2)}^{N_{total}}),\hat{E}(g_{f}^{lM},z_{\sigma (2)}^{N_{total}})\]


By the triangle inequality for \( d_{\nu } \),


\[
\frac{2}{\nu }d_{z^{2N_{total}}}(H_{f}^{lM},g_{f}^{lM})+d_{\nu }(\hat{E}(g_{f}^{lM},z^{N_{total}}_{\sigma (1)}),\hat{E}(g_{f}^{lM},z^{N_{total}}_{\sigma (2)}))\]



\[
\geq d_{\nu }(\hat{E}(H_{f}^{lM},z^{N_{total}}_{\sigma (1)}),\hat{E}(g_{f}^{lM},z^{N_{total}}_{\sigma (1)}))\]

\[
+d_{\nu }(\hat{E}(H_{f}^{lM},z^{N_{total}}_{\sigma (2)}),\hat{E}(g_{f}^{lM},z^{N_{total}}_{\sigma (2)}))\]

\[
+d_{\nu }(\hat{E}(g_{f}^{lM},z^{N_{total}}_{\sigma (1)}),\hat{E}(g_{f}^{lM},z^{N_{total}}_{\sigma (2)}))\]

\[
\geq d_{\nu }(\hat{E}(H_{f}^{lM},z^{N_{total}}_{\sigma (1)}),\hat{E}(H_{f}^{lM},z^{N_{total}}_{\sigma (2)}))\]


Since \( \frac{2}{\nu }d_{z^{2N_{total}}}(H_{f}^{lM},g_{f}^{lM})
\leq \frac{\alpha }{4} \) and \( b_{\nu
}(\hat{E}(H_{f}^{lM},z^{N_{total}}_{\sigma
(1)}),\hat{E}(H_{f}^{lM},z^{N_{total}}_{\sigma (2)}))>\frac{\alpha }{2}
\) we must have \( d_{\nu }(\hat{E}(g_{f}^{lM},z^{N_{total}}_{\sigma
(1)}),\hat{E}(g_{f}^{lM},z^{N_{total}}_{\sigma (2)}))>\frac{\alpha }{4}
\) implying that if a ``bad'' \( H_{f}^{lM} \) exists 
there must exist a ``bad'' \( g_{f}^{lM} \).
\end{proof}

The next lemma is essentially a statement that Hoeffding bounds apply to the
second equation in the lemma above. 

\begin{lem}
Let \( f \) be any chain of functions. \( \forall z_1^{N_{total}},z_2^{N_{total}} \), 
\[
P(\sigma :d_{\nu }[\hat{E}(g_{f}^{lM},z_{1}^{N_{total}}),\hat{E}(g_{f}^{lM},z_{2}^{N_{total}})]>\frac{\alpha }{4})\leq 2e^{-\frac{\alpha ^{2}\nu N_{total}}{8}}\label{}
\]


where each \( \sigma  \) is chosen uniformly at random
\end{lem}
\begin{proof}
For any \( \sigma  \),

\[
d_{\nu }[\hat{E}(g_{f}^{lM},z_{1}^{N_{total}}),\hat{E}(g_{f}^{lM},z_{2}^{N_{total}})]
= \frac{\sum _{m=1}^{M}\sum _{n=1}^{N_{m}}[g^l_{f_{m}}(z_{1\sigma (nm)})-g^l_{f_{m}}(z_{2\sigma (nm)})]}{\nu N_{total}+\sum _{m=1}^{M}\sum _{n=1}^{N_{m}}[g^l_{f_{m}}(z_{1nm})+g^l_{f_{m}}(z_{2nm})]}
\]

Each pair, \( g_{f_{m}}(z_{1\sigma (nm)})-g_{f_{m}}(z_{2\sigma (nm)}) \) is
a \( 0 \) mean random variable over the choice of \( \sigma  \). Hoeffding's
bound for \( 0 \) mean independent random variables, \( X_{1},...,X_{K} \)
with ranges \( a_{k}\leq X_{k}\leq b_{k} \) is: 


\[
P(|\sum ^{K}_{k=1}X_{k}|\geq \epsilon )\leq 2e^{\frac{-2\epsilon ^{2}}{\sum _{k=
1}^{K}(b_{k}-a_{k})^{2}}}\]

Which, when applied to our \( N_{total} \) random variables gives 
\[
P(\sigma :d_{\nu }[\hat{E}(g_{f}^{lM},z_{1}^{N_{total}}),\hat{E}(g_{f}^{lM},z_{2}^{N_{total}})] 
   > \frac{\alpha }{4})
\]
\[
\leq 2e^{-\frac{\alpha ^{2}(\nu N_{total}+\sum _{m=1}^{M}\sum ^{N_{m}}_{n=1}[g^l_{f_{m}}(z_{1nm})+g^l_{f_{m}}(z_{2mn})])^{2}}
               {32\sum _{m=1}^{M}\sum _{n=1}^{N_{m}}[g^l_{f_{m}}(z_{1\sigma (nm)})+g^l_{f_{m}}(z_{2\sigma (nm)})]^{2}}}
\]
%%Fixme why is this true?

Letting \( \gamma =\sum _{m=1}^{M}\sum _{n=1}^{N_{m}}[g^l_{f_{m}}(z_{1nm})+g^l_{f_{m}}(z_{2nm})] \),
this becomes:
\[
P(\sigma :d_{\nu }[\hat{E}(g_{f}^{lM},z_{1}^{N_{total}}),\hat{E}(g_{f}^{lM},z_{2}^{N_{total}})]
  > \frac{\alpha }{4})
\leq 2e^{-\frac{\alpha ^{2}(\nu N_{total}+\gamma )^{2}}{32\gamma }}
\]


Which is worst for \( \gamma =\nu N_{total} \), implying the lemma.
\end{proof}
The three lemmas above give a proof for the Multitask Learning Theorem.

\begin{thebibliography}{}
\bibitem{Baxter}Jon Baxter. A Model of Inductive Bias
Learning. 1998. http://syseng.anu.edu.au/~jon/papers/bias.ps.gz

\bibitem{CDM}Jon Baxter and Peter Bartlett. The Canonical Distortion
Measure in Feature Space and 1-NN
Classification. NIPS97. http://syseng.anu.edu.au/~jon/papers/NIPS97.ps.gz

\bibitem{Le Cun}Y. Bengio, Y. LeCun, C. Nohl, and C. Burges. Lerec: A nn/hmm hybrid for on-line
handwriting recognition. Neural Computation, 7(6):1289-1303, November 1995

\bibitem{Caruana}Rich Caruana, \char`\"{}Multitask Learning,\char`\"{}
MACHINE LEARNING, 1997.

\bibitem{Haussler}David Haussler. ``Decision Theoretic Generalizations
of the PAC Model for Neural Net and Other Learning Applications'',
Information and Computation 100, 78-150 (1992)

\bibitem{4}Thorsten Joachims, Tom Mitchell, Dayne Freitag, and Robert Armstrong, ``WebWatcher:
Machine Learning and Hypertext'', 1995

\bibitem{7}Andrew McCallum, Ronald Rosenfeld, Tom Mitchell, and Andrew
Ng, ``Improving Text Classification by Shrinkage in a Hierarchy of
Classes'', ICML98, 359-367, 1998 

\bibitem{8}Rajeev Motwani and Prabhakar Raghavan, ``Randomized
Algorithms'', Cambridge University Press, p. 70, 1995

\bibitem{Thrun}S. Thrun and L.Y. Pratt (eds), 1997. Learning To
Learn. Kluwer Academic Publishers.

\end{thebibliography} 
\end{document}
