\documentclass[twoside,11pt]{article}
\usepackage{times}
\usepackage{theapa}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amssymb}
\usepackage{epsf}
\usepackage{glossary}
\usepackage{jair}
%\renewcommand{\floatpagefraction}{20} 
\jairheading{12}{2000}{149--198}{11/99}{3/00}
\firstpageno{149}
\ShortHeadings{A Model of Inductive Bias Learning}{Baxter}
\newcommand{\supp}{{\mbox{supp}}}
\newcommand{\bb}{\mathbb}
\renewcommand{\Box}{\qed}
\newcommand{\mathbold}[1]{\mathbf{#1}}
\newcommand{\glossaryentry}[3]{\item[#1] #2 \hfill #3}
\renewcommand{\glossary}[2]{}
%\def\addcontentsline#1#2#3{} 
\renewcommand{\thickapprox}{\doteq}
\newtheorem{thm}{Theorem}
\newtheorem{exmp}{Example}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{corr}[thm]{Corollary}
\newtheorem{defn}{Definition}
\newcommand{\D}{{\cal D}}
\DeclareMathOperator{\er}{er}
\DeclareMathOperator{\VCdim}{VCdim}
\DeclareMathOperator{\opt}{opt}
\newcommand{\Hhat}{{\hat{\H}}}
\newcommand{\erh}{{\hat{\er}}}
\newcommand{\ie}{{i.e.,\ }}
\newcommand{\etal}{{\em et.\ al.\ }}
\newcommand{\iid}{{i.i.d.\ }}
\newcommand{\norm}{{\|\cdot\|}}
\newcommand{\eg}{{\em e.g.\ }}
\newcommand{\cf}{{\em c.f.\ }}
\newcommand{\etc}{{\em etc\ }}
\newcommand{\comp}[2]{{#1\circ#2}}
\newcommand{\epspic}[2]{{\parbox{#1}{\epsfxsize=#1\epsfbox{#2}}}}
\renewcommand{\d}[2]{d_\nu\left[#1,#2\right]}
\newcommand{\pt}{p(z|\theta)}
\newcommand{\ptt}{p(z|\thetat)}
\newcommand{\rangel}[1]{\rangle_{#1}}
\newcommand{\E}{\bb E}
\newcommand{\HH}{{\hspace{0.2mm}\bb H}\hspace{0.2mm}}
\newcommand{\Phihat}{{\hat{\Phi}}}
\newcommand{\Hs}{{\HH_\sigma}}
\newcommand{\dun}{{\underline{d}}}
\renewcommand{\H}{{\cal H}}
\newcommand{\XY}{{X\times Y}}
\newcommand{\VY}{{V\times Y}}
\newcommand{\de}{=}%%{{\,\,\,\,\overset{\text{def}}{=}\,\,\,\,}}
\renewcommand{\P}{{\cal P}}
\newcommand{\Zm}{{\(X\times Y\)^m}}
\newcommand{\Zn}{{\(X\times Y\)^n}}
\newcommand{\Zmn}{{\(X\times Y\)^{(m,n)}}}
\newcommand{\Znm}{{\(X\times Y\)^{(n,m)}}}
\newcommand{\Xnm}{{X^{(n,m)}}}
\newcommand{\Ztmn}{{\(X\times Y\)^{(2m,n)}}}
\newcommand{\Gtmn}{{\Gamma_{(2m,n)}}}
\newcommand{\zmn}{{z^{(m,n)}}}
\newcommand{\znm}{{z^{(n,m)}}}
\newcommand{\znmm}{{z^{(n,m-1)}}}
\newcommand{\z}{{\mathbold{z}}}
\newcommand{\m}{{\mathbold{m}}}
\newcommand{\f}{{\bf f}}
\newcommand{\g}{{\bf g}}
\newcommand{\w}{{\bf w}}
\newcommand{\x}{{\mathbold{x}}}
\newcommand{\y}{{\bf y}}
\newcommand{\B}{{\cal B}}
\newcommand{\h}{{\mathbold{h}}}
\newcommand{\Pm}{{P^m}}
\newcommand{\zb}{{\bold{z}}}
\newcommand{\zbh}{{\hat{\zb}}}
\newcommand{\zbv}{{\smash[b]{\vec{\zb}}}}
\newcommand{\zbvh}{\zbv} %%{\smash[b]{\hat{\vec{\zb}}}}}
\newcommand{\zh}{{\hat z}}
\newcommand{\xh}{{\hat x}}
\newcommand{\sh}{{\hat s}}
\newcommand{\Xhat}{{\hat X}}
\newcommand{\Shat}{{\hat S}}
\newcommand{\Ehat}{{\hat E}}
\newcommand{\qhat}{{\hat q}}
\newcommand{\yh}{{\hat y}}
\newcommand{\Phat}{{\hat \P}}
\newcommand{\Ph}{{\hat P}}
\newcommand{\zs}{{\z_\sigma}}
\newcommand{\zsw}{{\z_\sigma(1)}}
\newcommand{\zst}{{\z_\sigma(2)}}
\newcommand{\zsij}{{z_{\sigma(i,j)}}}
\newcommand{\fhat}{{\hat f}}
\newcommand{\ghat}{{\hat g}}
\newcommand{\Fhat}{{\hat \F}}
\newcommand{\rhat}{{\hat \rho}}
\newcommand{\Eh}{{\hat E}}
\newcommand{\bw}{{\bold{w}}}
\newcommand{\be}{\begin{equation*}}
\newcommand{\ee}{$$}
\newcommand{\ep}{{\varepsilon}}
\newcommand{\Z}{{\cal Z}}
\newcommand{\A}{{\cal A}}
\newcommand{\C}{{\cal C}}
\newcommand{\N}{{\cal N}}
\newcommand{\Nco}{{\N_\co}}
\newcommand{\M}{{\cal M}}
\newcommand{\F}{{\cal F}}
\newcommand{\G}{{\cal G}}
\newcommand{\T}{{\bb T}}
\newcommand{\U}{{\cal U}}
\newcommand{\V}{{\cal V}}
\renewcommand{\S}{{\cal S}}
\newcommand{\Ch}{{\hat \C}}
\newcommand{\rhol}{\rho_{\!_l}}
\renewcommand{\(}{\left(}
\renewcommand{\)}{\right)}
\renewcommand{\[}{\left[}
\renewcommand{\]}{\right]}
\newcommand{\Pv}{{\Pb}}
\newcommand{\xb}{{\bold{x}}}
\newcommand{\yb}{{\bold{y}}}
\newcommand{\wb}{{\bold{w}}}
\newcommand{\Fbar}{{\overline\F}}
\newcommand{\Rbar}{{\overline R}}
\newcommand{\Cbar}{{\overline C}}
\newcommand{\Lbar}{{\overline L}}
\newcommand{\Gbar}{{\overline\G}}
\newcommand{\Pbar}{{\bar{P}}}
\newcommand{\Pb}{{\mathbold{P}}}
\newcommand{\scPb}{{\mathbold{\scriptstyle P}}}
\renewcommand{\hbar}{{\overline h}}
\newcommand{\dbar}{{d^*}}
\newcommand{\co}{{\text{\rm co}}}
\newcommand{\jon}{{\text{\rm jon}}}
\newcommand{\cdm}{{d_{\text{\rm CDM}}}}
\newcommand{\cdmhat}{{\hat{d}_{\text{\rm CDM}}}}
\newcommand{\thetahat}{{\hat{\theta}}}
\newcommand{\pihat}{{\hat{\pi}}}
\newcommand{\thetat}{{\tilde{\theta}}}
\newcommand{\cdmhathat}{{\tilde{d}_{\text{\rm CDM}}}}
\newcommand{\lin}{{\text{\rm lin}}}
\newcommand{\sign}{{\text{\rm sign}}}
\newcommand{\IID}{{\text{\rm IID}}}
\newcommand{\OTS}{{\text{\rm OTS}}}
\newcommand{\CDM}{{\text{\rm CDM}}}
\newcommand{\VC}{{\text{\rm VC}}}
\newcommand{\LDR}{{\text{\rm LDR}}}
\newcommand{\OUT}{{\text{\rm OUT}}}
\newcommand{\cobar}[1]{{\overline{\text{\rm co}\(#1\)}}}
\newcommand{\linbar}[1]{{\overline{\text{\rm lin}\(#1\)}}}
\newcommand{\fbar}{{\bar f}}
\newcommand{\lbar}{{\bar l}}
\newcommand{\pibar}{{\bar \pi}}
\newcommand{\zv}{{\vec{z}}}
\newcommand{\gv}{{\vec{g}}}
\newcommand{\fv}{{\mathbold{f}}}
\newcommand{\lv}{{\vec l}}
\newcommand{\hv}{{\mathbold{h}}}
\newcommand{\xv}{{\vec x}}
\newcommand{\yv}{{\vec y}}
\newcommand{\wv}{{\vec w}}
\newcommand{\vv}{{\vec v}}
\newcommand{\av}{{\vec a}}
\newcommand{\Xv}{{\vec X}}
\newcommand{\pr}[3]{{{#1}_1#2\dots#2{#1}_{#3}}}
\newcommand{\iton}{{1\leq i\leq n}}
\newcommand{\prd}[4]{{{#1}_{#2}#3\dots#3{#1}_{#4}}}
\newcommand{\R}{{\mathbb R}}
\newcommand{\Q}{{\mathbb Q}}
\newcommand{\Rn}{{\R^n}}
\newcommand{\Rpm}{{(\bb R^+)^{2m}}}
\newcommand{\Rptm}{{(\bb R^+)^{(2m,n)}}}
\newcommand{\dl}{{\mbox{\boldmath$d_{L^1}$}}}
\newcommand{\dimp}{{\mbox{dimp}}}
\newcommand{\argmin}{{\mbox{argmin}}}
\newcommand{\plus}{{\mbox{plus}}}
\newcommand{\minus}{{\mbox{minus}}}
\newcommand{\DKL}{{\mbox{DKL}}}
\newcommand{\WKS}{{\mbox{WKS}}}
\newcommand{\PKS}{{\mbox{PKS}}}
\newcommand{\ch}{{\large \chi}}
\newcommand{\SZ}{{\cal S}_Z}
\newcommand{\SP}{{\cal S}_\P}
\newcommand{\Tbar}{{\overline T}}
\newcommand{\Sbar}{{\overline S}}
\newcommand{\Xbar}{{\overline X}}
\newcommand{\Hbar}{{\overline \H}}
\newcommand{\bool}{{\{\pm 1\}}}
\newcommand{\zm}{{z^m}}
\newcommand{\Hns}{{\HH^n_l}}
\newcommand{\Hsn}{{\[\HH_\sigma\]^n}}
\newcommand{\XVA}{X\stackrel{\F}{\rightarrow}V\stackrel{\G}{\rightarrow}A}
\newcommand{\XfVGY}{X\stackrel{f}{\rightarrow}V\stackrel{\G}{\rightarrow}Y}
\renewcommand{\ln}{\log}
\newcommand{\dov}{{\overline{d}}}
\makeglossary
\begin{document}
\title{A Model of Inductive Bias Learning} 
\author{\name Jonathan Baxter \email Jonathan.Baxter@anu.edu.au \\
\addr Research School of Information Sciences and Engineering \\
Australian National University, Canberra 0200, Australia}
\date{12 January, 1996\\
Revised: \today}
\maketitle
\begin{abstract} A major problem in machine learning is that of
inductive bias: how to choose a learner's hypothesis space so that it
is large enough to contain a solution to the problem being learnt, yet
small enough to ensure reliable generalization from reasonably-sized
training sets.  Typically such bias is supplied by hand through the
skill and insights of experts. In this paper a model for {\em
automatically learning} bias is investigated. The central assumption
of the model is that the learner is embedded within an {\em
environment} of related learning tasks. Within such an environment the
learner can sample from multiple tasks, and hence it can search for a
hypothesis space that contains good solutions to many of the problems
in the environment. Under certain restrictions on the set of all
hypothesis spaces available to the learner, we show that a
hypothesis space that performs well on a sufficiently large number of
training tasks will also perform well when learning novel tasks in the
same environment.  Explicit bounds are also derived demonstrating that
learning multiple tasks within an environment of related tasks can
potentially give much better generalization than learning a single
task.
\end{abstract}
\section{Introduction} 
Often the hardest problem in any machine learning task is 
the initial choice of hypothesis space; it has to be large enough to
contain a solution to the problem at hand, yet small enough to
ensure good generalization from a small number of examples
\cite{mitchell91}. Once a suitable bias has been
found, the actual learning task is often straightforward. Existing
methods of bias generally require the input of a human expert in the
form of heuristics and domain knowledge (for example, through the
selection of an appropriate set of features). Despite their successes,
such methods are clearly limited by the accuracy and reliability of
the expert's knowledge and also by the extent to which that knowledge
can be transferred to the learner. Thus it is natural to search for
methods for {\em automatically learning} the bias.

\sloppy
In this paper we introduce and analyze a formal model of {\em bias
learning} that builds upon the PAC model of machine learning and its
variants \cite{vapnik82a,valiant84,blumer89a,haussler92a}. These
models typically take the following general form: the learner is
supplied with a hypothesis space $\H$ and training data $z =
\{(x_1,y_1),\dots,(x_m,y_m)\}$ drawn independently according to some
underlying distribution $P$ on $X\times Y$. Based on the information
contained in $z$, the learner's goal is to select a hypothesis
$h\colon X\to Y$ from $\H$ minimizing some measure $\er_P(h)$ of
expected loss with respect to $P$ (for example, in the case of squared
loss $\er_P(h) := \E_{(x,y)\sim P} \(h(x) - y\)^2$).  In such models the
learner's bias is represented by the choice of $\H$; if $\H$ does not
contain a good solution to the problem, then, regardless of how much
data the learner receives, it cannot learn.

Of course, the best way to bias the learner is to supply it with an
$\H$ containing just a single optimal hypothesis. But finding such a
hypothesis is precisely the original learning problem, so in the PAC
model there is no distinction between bias learning and ordinary
learning. Or put differently, the PAC model does not model the process
of inductive bias, it simply takes the hypothesis space $\H$ as given
and proceeds from there. To overcome this problem, in this paper we
assume that instead of being faced with just a single learning task,
the learner is embedded within an {\em environment} of related
learning tasks. The learner is supplied with a {\em family} of
hypothesis spaces $\HH=\{\H\}$, and its goal is to find a bias
(i.e. hypothesis space $\H\in \HH$) that is appropriate for the entire
environment. A simple example is the problem of handwritten character
recognition. A preprocessing stage that identifies and removes any
(small) rotations, dilations and translations of an image of a
character will be advantageous for recognizing all characters. If the
set of all individual character recognition problems is viewed as an
environment of learning problems (that is, the set of all problems of
the form ``distinguish `A' from all other characters'', ``distinguish
`B' from all other characters'', and so on), this preprocessor represents a bias
that is appropriate for all problems in the environment. It is likely
that there are many other currently unknown biases that are also
appropriate for this environment. We would like to be able to learn
these automatically.

There are many other examples of learning problems that can be
viewed as belonging to environments of related problems. For example,
each individual face recognition problem belongs to an (essentially
infinite) set of related learning problems (all the other individual
face recognition problems); the set of all individual spoken word
recognition problems forms another large environment, as does the set
of all fingerprint recognition problems, printed Chinese and Japanese
character recognition problems, stock price prediction problems and so
on.  Even medical diagnostic and prognostic problems, where a multitude
of diseases are predicted from the same pathology tests, constitute an
environment of related learning problems.

In many cases these ``environments'' are not normally modeled as
such; instead they are treated as single, multiple category learning
problems. For example, recognizing a group of faces would normally be
viewed as a single learning problem with multiple class labels (one
for each face in the group), not as multiple individual learning
problems. However, if a reliable classifier for each individual face
in the group can be constructed then they can easily be combined to
produce a classifier for the whole group. Furthermore, by viewing the
faces as an environment of related learning problems, the results
presented here show that bias can be learnt that will be good for
learning novel faces, a claim that cannot be made for the traditional
approach.

This point goes to the heart of our model: we are not
not concerned with adjusting a learner's bias so it performs better on 
some {\em fixed} set of learning problems. Such a process is in fact
just ordinary learning but with a richer hypothesis space in which
some components labelled ``bias'' are also able to be varied. Instead, 
we suppose the learner is faced with a (potentially infinite) stream of 
tasks, and that by adjusting its bias on some subset of the tasks it
improves its learning performance on future, as yet unseen tasks. 

Bias that is appropriate for all problems in an environment must be
learnt by sampling from many tasks. If only a single task is learnt
then the bias extracted is likely to be specific to that task.  In the
rest of this paper, a general theory of bias learning is developed
based upon the idea of learning multiple related tasks. Loosely
speaking (formal results are stated in Section \ref{modelsec}),
there are two main conclusions of the theory presented here:
\begin{itemize}
\item Learning multiple related tasks reduces the sampling burden
required for good generalization, at least on a
number-of-examples-required-per-task basis.
\item Bias that is learnt on sufficiently many training tasks is
likely to be good for learning novel tasks drawn from the same
environment.
\end{itemize}

The second point shows that a form of {\em meta-generalization} is
possible in bias learning. Ordinarily, we say a learner generalizes
well if, after seeing sufficiently many training examples, it
produces a hypothesis that with high probability will perform well on
future examples of the same task. However, a bias learner generalizes well
if, after seeing sufficiently many training {\em tasks} it produces a
{\em hypothesis space} that with high probability contains good
solutions to novel tasks. Another term that has been used for this process is 
{\em Learning to Learn} \cite{thrun97a}. 

Our main theorems are stated in an agnostic setting (that is, $\HH$
does not necessarily contain a hypothesis space with solutions to all
the problems in the environment), but we also give improved bounds in
the realizable case.  The sample complexity bounds appearing in these
results are stated in terms of combinatorial parameters related to the
complexity of the set of all hypothesis spaces $\HH$ available to the
bias learner. For Boolean learning problems (pattern classification)
these parameters are the bias learning analogue of the {\em
Vapnik-Chervonenkis dimension}
\cite{vapnik82a,blumer89a}.

As an application of the general theory, the problem of learning an
appropriate set of neural-network features for an environment of
related tasks is formulated as a bias learning problem. In the case of
continuous neural-network features we are able to prove upper bounds
on the number of training tasks and number of examples of each
training task required to ensure a set of features that works well for
the training tasks will, with high probability, work well on novel
tasks drawn from the same environment. The upper bound on the number
of tasks scales as $O(b)$ where $b$ is a measure of the complexity of
the possible feature sets available to the learner, while the upper
bound on the number of examples of each task scales as $O(a + b/n)$
where $O(a)$ is the number of examples required to learn a task if the
``true'' set of features (that is, the correct bias) is already known,
and $n$ is the number of tasks. Thus, in this case we see that as the
number of related tasks learnt increases, the number of examples
required of each task for good generalization decays to the minimum
possible. For Boolean neural-network feature maps we are able to show a matching
lower bound on the number of examples required per task of the same
form.

\subsection{Related Work} 
There is a large body of previous algorithmic and experimental work in
the machine learning and statistics literature addressing the problems
of inductive bias learning and improving generalization through
multiple task learning. Some of these approaches can be seen as
special cases of, or at least closely aligned with, the model
described here, while others are more orthogonal. Without being
completely exhaustive, in this section we present an overview
of the main contributions. See \citeA[chapter 1]{thrun97a} for a more
comprehensive treatment.
\begin{description}
\item[$\bullet$ Hierarchical Bayes.] The earliest approaches to bias
learning come from Hierarchical Bayesian methods
in statistics \cite{Berger85,Good80,Gelman95}. In contrast to 
the Bayesian methodology, the present paper takes an essentially
empirical process approach to modeling the problem of bias
learning. However, a model using a mixture of hierarchical Bayesian
and information-theoretic ideas was presented in
\citeA{97b}, with similar conclusions to those found here. An empirical 
study showing the utility of the hierarchical Bayes approach in a
domain containing a large number of related tasks was given 
in \citeA{heskes98}. 
\item[$\bullet$ Early machine learning work.] 
In \citeA{Rendell87} ``VBMS'' or {\em Variable Bias
Management System} was introduced as a mechanism for selecting amongst
different learning algorithms when tackling a new learning
problem. ``STABB'' or {\em Shift To a Better Bias} \cite{utgoff86}
was another early scheme for adjusting bias, but unlike VBMS, STABB
was not primarily focussed on searching for bias applicable to large
problem domains. Our use of an ``environment of related tasks'' in
this paper may also be interpreted as an ``environment of analogous
tasks'' in the sense that conclusions about one task can be arrived at
by analogy with (sufficiently many of) the other tasks. For an early
discussion of analogy in this context, see \citeA[\S4.3]{russell86},
in particular the observation that for analogous problems the sampling 
burden {\em per task} can be reduced. 
\item[$\bullet$ Metric-based approaches.]
The metric used in nearest-neighbour classification, and in vector
quantization to determine the nearest code-book vector, represents a
form of inductive bias. Using the model of the present paper, and
under some extra assumptions on the tasks in the environment
(specifically, that their marginal input-space distributions are
identical and they only differ in the conditional probabilities they
assign to class labels), it can be shown that there is an {\em
optimal} metric or distance measure to use for vector quantization and
one-nearest-neighbour classification
\cite{thesis,icml_97,nips_97}. This metric can be learnt by sampling from a subset of
tasks from the environment, and then used as a distance measure when
learning novel tasks drawn from the same environment. Bounds on the
number of tasks and examples of each task required to ensure good
performance on novel tasks were given in
\citeA{nips_97}, along with an experiment in which a metric was
successfully trained on examples of a subset of 400 Japanese characters and then
used as a fixed distance measure when learning 2600 as yet unseen characters.

A similar approach is described in \citeA{thrun95b,thrun96a}, in which 
a neural network's output was trained to match labels on a novel
task, while simultaneously being forced to match its gradient to {\em 
derivative} information generated from a distance metric trained on
previous, related tasks. Performance on the novel tasks improved
substantially with the use of the derivative information. 

Note that there are many other adaptive metric techniques used in
machine learning, but these all focus exclusively on adjusting the
metric for a fixed set of problems rather than learning a metric
suitable for learning novel, related tasks (bias learning). 
\item[$\bullet$ Feature learning or learning internal representations.]
As with adaptive metric techniques, there are many approaches to
feature learning that focus on adapting features for a fixed task
rather than learning features to be used in novel tasks. One of the
few cases where features have been learnt on a subset of tasks with
the explicit aim of using them on novel tasks was \citeA{edelman96a} in
which a low-dimensional representation was learnt for a set of
multiple related image-recognition tasks and then used to successfully
learn novel tasks of the same kind. The experiments reported in \citeA[chapter
4]{thesis} and \citeA{95a,nips_97} are also of this nature.
\item[$\bullet$ Bias learning in Inductive Logic Programming (ILP).]
Predicate invention refers to the process in ILP whereby new
predicates thought to be useful for the classification task at hand
are added to the learner's domain knowledge. By using the new
predicates as background domain knowledge when learning novel tasks,
predicate invention may be viewed as a form of inductive bias
learning. Preliminary results with this approach on a chess domain are 
reported in \citeA{khan98}. 
\item[$\bullet$ Improving performance on a fixed reference task.]
``Multi-task learning'' \cite{caruana97a} trains extra neural
network outputs to match related tasks in order to improve
generalization performance on a fixed reference task. Although this
approach does not explicitly identify the extra bias generated by the
related tasks in a way that can be used to learn novel tasks, it is an
example of exploiting the bias provided by a set of related tasks to
improve generalization performance. Other similar approaches include
\citeA{Suddarth90,Suddarth91,mostafa93a}. 
\sloppy
\item[$\bullet$ Bias as computational complexity.] In this paper we
consider inductive bias from a sample-complexity perspective: how does 
the learnt bias decrease the number of examples required of novel
tasks for good generalization? A natural alternative line of enquiry
is how the running-time or computational complexity of a learning
algorithm may be improved by training on related tasks. Some early
algorithms for neural networks in this vein are contained in
\citeA{sharkey93,pratt}. 
\item[$\bullet$ Reinforcement Learning.] Many control tasks can appropriately be
viewed as elements of sets of related tasks, such as learning to
navigate to different goal states, or learning a set of complex motor
control tasks. A number of papers in the reinforcement learning
literature have proposed algorithms for both sharing the information
in related tasks to improve average generalization performance across
those tasks \citeA{singh92,ring95}, or learning bias from a set
of tasks to improve performance on future tasks
\citeA{sutton92,thrun95c}.
\end{description}

\subsection{Overview of the Paper}

In Section \ref{modelsec} the bias learning model is formally defined,
and the main sample complexity results are given showing the utility
of learning multiple related tasks and the feasibility of bias
learning. These results show that the sample complexity is controlled
by the size of certain covering numbers associated with the set of all
hypothesis spaces available to the bias learner, in much the same way
as the sample complexity in learning Boolean functions is controlled
by the {\em Vapnik-Chervonenkis} dimension
\cite{vapnik82a,blumer89a}. The results of Section \ref{modelsec} are
upper bounds on the sample complexity required for good generalization
when learning multiple tasks and learning inductive bias. 

The general results of Section \ref{modelsec} are specialized to the
case of feature learning with neural networks in Section
\ref{featuresec}, where an algorithm for training features by gradient
descent is also presented. For this special case we are able to show
matching lower bounds for the sample complexity of multiple task
learning.  In Section \ref{conclusion} we present some concluding
remarks and directions for future research. Many of the proofs are
quite lengthy and have been moved to the appendices so as not to
interrupt the flow of the main text.

The following tables contain a glossary of the
mathematical symbols used in the paper.

\renewcommand{\glossaryentry}[3]{#1 & #2 & #3 \\}    
\begin{tabular}{|l|l|c|}
\hline
Symbol & Description & First Referenced \\ \hline
\glossaryentry{$X$}{Input Space}{155}
\glossaryentry{$Y$}{Output Space}{155}
\glossaryentry{$P$}{Distribution on $X\times Y$ (learning task)}{155}
\glossaryentry{$l$}{Loss function}{155}
\glossaryentry{$\H$}{Hypothesis Space}{155}
\glossaryentry{$h$}{Hypothesis}{155}
\glossaryentry{$\er_P(h)$}{Error of hypothesis $h$ on distribution $P$}{156}
\glossaryentry{$z$}{Training set}{156}
\glossaryentry{$\A$}{Learning Algorithm}{156}
\glossaryentry{$\erh_z(h)$}{Empirical error of $h$ on training set $z$}{156}
\glossaryentry{$\P$}{Set of all learning tasks $P$}{157}
\glossaryentry{$Q$}{Distribution over learning tasks}{157}
\glossaryentry{$\HH$}{Family of hypothesis spaces}{157}
\glossaryentry{$\er_Q(\H)$}{Loss of hypothesis space $\H$ on environment $Q$}{158}
\glossaryentry{$\z$}{$(n,m)$-sample}{158}
\glossaryentry{$\erh_\z(\H)$}{Empirical loss of $\H$ on $\z$}{158}
\glossaryentry{$\A$}{Bias learning algorithm}{159}
\glossaryentry{$h_l$}{Function induced by $h$ and $l$}{159}
\glossaryentry{$\H_l$}{Set of $h_l$}{159}
\glossaryentry{$(h_1,\dots,h_n)_l$}{Average of $h_{1,l}, \dots,h_{n,l}$}{159}
\glossaryentry{$\h_l$}{Same as$(h_1,\dots,h_n)_l$}{159}
\glossaryentry{$\H^n_l$}{Set of $(h_1,\dots,h_n)_l$}{159}
\glossaryentry{$\HH^n_l$}{Set of $\H^n_l$}{159}
\glossaryentry{$\H^*$}{Function on probability distributions}{160}
\glossaryentry{$\HH^*$}{Set of $\H^*$}{160}
\glossaryentry{$d_\scPb$}{Pseudo-metric on $\H^n_l$}{160}
\glossaryentry{$d_Q$}{Pseudo-metric on $\HH^*$}{160}
\glossaryentry{$\N(\ep,\HH^*,d_Q)$}{Covering number of $\HH^*$}{160}
\glossaryentry{$\C(\ep,\HH^*)$}{Capacity of $\HH^*$}{160}
\glossaryentry{$\N(\ep,\HH^n_l,d_\scPb)$}{Covering number of $\HH^n_l$}{160}
\glossaryentry{$C(\ep,\HH^n_l)$}{Capacity of $\HH^n_l$}{160}
\glossaryentry{$\h$}{Sequence of $n$ hypotheses $(h_1,\dots,h_n)$}{163}
\glossaryentry{$\Pb$}{Sequence of $n$ distributions $(P_1,\dots,P_n)$}{163}
\glossaryentry{$\er_\scPb(\h)$}{Average loss of $\h$ on $\Pb$}{164}
\glossaryentry{$\erh_\z(\h)$}{Average loss of $\h$ on $\z$}{164}
\glossaryentry{$\F$}{Set of feature maps}{166}
\glossaryentry{$\G$}{Output class composed with feature maps $f$}{166}
\glossaryentry{$\comp{\G}{f}$}{Hypothesis space associated with $f$}{166}
\glossaryentry{$\G_l$}{Loss function class associated with $\G$}{166}
\glossaryentry{$\N\(\ep, \G_l, d_P\)$}{Covering number of $\G_l$}{166}
\glossaryentry{$\C\(\ep, \G_l\)$}{Capacity of $\G_l$}{166}
\glossaryentry{$d_{[P,\G_l]}(f,f')$}{Pseudo-metric on feature maps $f,f'$}{166}
\glossaryentry{$\N(\ep,\F,d_{[P,{\G_l}]})$}{Covering number of $\F$}{166}
\hline
\end{tabular}

\renewcommand{\glossaryentry}[3]{#1 & #2 & #3 \\}    
\begin{tabular}{|l|l|c|}
\hline
Symbol & Description & First Referenced \\ \hline
\glossaryentry{$\N(\ep,\F,d_{[P,{\G_l}]})$}{Covering number of $\F$}{166}
\glossaryentry{$\C_{\G_l}(\ep,\F)$}{Capacity of $\F$}{166}
\glossaryentry{$\H_w$}{Neural network hypothesis space}{167}
\glossaryentry{$\H_{|x}$}{$\H$ restricted to vector $x$}{172}
\glossaryentry{$\Pi_\H(m)$}{Growth function of $\H$}{172}
\glossaryentry{$\VCdim(\H)$}{Vapnik-Chervonenkis dimension of $\H$}{172}
\glossaryentry{$\H_{|\x}$}{$\H$ restricted to matrix $\x$}{173}
\glossaryentry{$\HH_{|\x}$}{$\HH$ restricted to matrix $\x$}{173}
\glossaryentry{$\Pi_\HH(n,m)$}{Growth function of $\HH$}{173}
\glossaryentry{$d_\HH(n)$}{Dimension function of $\HH$}{173}
\glossaryentry{$\dov(\HH)$}{Upper dimension function of $\HH$}{173}
\glossaryentry{$\dun(\HH)$}{Lower dimension function of $\HH$}{173}
\glossaryentry{$\opt_\scPb(\HH^n)$}{Optimal performance of $\HH^n$ on $\Pb$}{175}
\glossaryentry{$d_\nu$}{Metric on $\R^+$}{179}
\glossaryentry{$h_1\oplus\dots\oplus h_n$}{Average of $h_1$, \dots, $h_n$}{179}
\glossaryentry{$\H_1\oplus\dots\oplus\H_n$}{Set of $h_1\oplus\dots\oplus h_n$}{180}
\glossaryentry{$\Gtmn$}{Permutations on integer pairs}{182}
\glossaryentry{$\z_\sigma$}{Permuted $\z$}{182}
\glossaryentry{$d_\z(\hv,\hv')$}{Empirical $l_1$ metric on functions $\hv$}{182}
\glossaryentry{$\erh_\scPb(\H)$}{Optimal average error of $\H$ on $\Pb$}{185}
\hline
\end{tabular}
\section{The Bias Learning Model}
\label{modelsec}
In this section the bias learning model is formally introduced. To
motivate the definitions, we first describe the main features of
ordinary (single-task) supervised learning models.

\subsection{Single-Task Learning}
Computational learning theory models of supervised learning usually
include the following ingredients:
\begin{itemize}
\item An {\em input space} $X$\glossary{$X$}{Input Space} and an {\em
output space} $Y$\glossary{$Y$}{Output Space},
\item a {\em probability distribution} $P$\glossary{$P$}{Distribution
on $X\times Y$ (learning task)} on $X\times Y$,
\item a {\em loss function} $l\colon Y\times Y\to
\R$\glossary{$l$}{Loss function}, and
\item a {\em hypothesis space} $\H$\glossary{$\H$}{Hypothesis Space} which is a set of {\em hypotheses}
or functions $h\colon X\to Y$\glossary{$h$}{Hypothesis}.
\end{itemize}
As an example, if the problem is to learn to recognize images of
Mary's face using a neural network, 
then $X$ would be the set of all images (typically
represented as a subset of $\R^d$ where each component is a pixel
intensity), $Y$ would be the set $\{0,1\}$, and the distribution $P$
would be peaked over images of different faces and the correct class
labels. The learner's hypothesis space $\H$ would be a class of neural
networks mapping the input space $\R^d$ to $\{0,1\}$. The loss in
this case would be discrete loss: 
\begin{equation}
l(y,y') := \left\{ \begin{array}{ll}
			1& \mbox{if $y\neq y'$} \\
			0& \mbox{if $y = y'$}
			\end{array} \right.	
\end{equation}
Using the loss function allows us to present a unified treatment of both
pattern recognition ($Y = \{0,1\}$, $l$ as above), and real-valued
function learning (\eg regression) in which $Y=\R$ and usually $l(y,y') =
(y-y')^2$. 

The goal of the learner is to select a hypothesis $h\in \H$ with
minimum {\em expected loss}: 
\begin{equation}
\label{expordloss}
\er_P(h) := \int_{X\times Y} l(h(x),y)\, dP(x,y).\glossary{$\er_P(h)$}{Error of hypothesis $h$ on
distribution $P$}
\end{equation}
Of course, the learner does not know $P$ and so it cannot search
through $\H$ for an $h$ minimizing $\er_P(h)$. In practice, the
learner samples repeatedly from $X\times Y$ according to the
distribution $P$ to generate a {\em training set}
\begin{equation}
z:= \{(x_1,y_1),\dots,(x_m,y_m)\}.\glossary{$z$}{Training set}
\end{equation}
Based on the information contained in $z$ the learner produces a
hypothesis $h\in\H$. Hence, in general a learner is simply a map $\A$
from the set of all training samples to the hypothesis space $\H$:
$$
\A\colon \bigcup_{m>0} (X\times Y)^m \to \H\glossary{$\A$}{Learning Algorithm}
$$
(stochastic learner's can be treated by assuming a distribution-valued $\A$.)

Many algorithms seek to minimize the {\em
empirical} loss of $h$ on $z$, where this is defined by:
\begin{equation}
\label{empordloss}
\erh_z(h) := \frac1m\sum_{i=1}^m l(h(x_i),y_i).\glossary{$\erh_z(h)$}{Empirical error of $h$ on training set $z$}
\end{equation}
Of course, there are more intelligent things to do with the data than
simply minimizing empirical error---for example one can add
regularisation terms to avoid over-fitting. 

However the learner chooses its hypothesis $h$, if we have a {\em
uniform} bound (over all $h\in\H$) on the probability of large
deviation between $\erh_z(h)$ and $\er_P(h)$, then we can bound the
learner's generalization error $\er_P(h)$ as a function of its
empirical loss on the training set $\erh_z(h)$. Whether such a bound
holds depends upon the ``richness'' of $\H$.  The conditions ensuring
convergence between $\erh_z(h)$ and $\er_P(h)$ are by now well
understood; for Boolean function learning ($Y= \{0,1\}$, discrete loss), convergence
is controlled by the {\em VC-dimension}\footnote{The VC
dimension of a class of Boolean functions $\H$ is the largest integer
$d$ such that there exists a subset $S:= \{x_1,\dots,x_d\} \subset X$
such that the restriction of $\H$ to $S$ contains all $2^d$ Boolean
functions on $S$.} of $\H$:
\begin{thm}
\label{vcthm}
Let $P$ be any probability distribution on $X\times \{0,1\}$ and
suppose $z= \{(x_1,y_1),\dots,(x_m,y_m)\}$ is generated by sampling
$m$ times from $X\times \{0,1\}$ according to $P$. Let $d :=
\VCdim(\H)$.  Then with probability at least $1-\delta$ (over the
choice of the training set $z$), {\bf all} $h\in \H$ will satisfy
\begin{equation}
\label{vceq}
\er_P(h) \leq \erh_z(h) + \[\frac{32}m\(d\ln\frac{2 e m}{d} +
\ln\frac4\delta\)\]^{1/2}
\end{equation}
\end{thm}
Proofs of this result may be found in \citeA{vapnik82a,blumer89a}, and
will not be reproduced here. 

Theorem \ref{vcthm} only provides conditions under which the deviation
between $\er_P(h)$ and $\erh_z(h)$ is likely to be small, it does not
guarantee that the true error $\er_P(h)$ will actually be small. This
is governed by the choice of $\H$. If $\H$ contains a solution with
small error and the learner minimizes error on the training set, then
with high probability $\er_P(h)$ will be small. However, a bad choice
of $\H$ will mean there is no hope of achieving small error. Thus, the
{\em bias} of the learner in this model\footnote{The bias is also governed by how the
learner uses the hypothesis space. For example, under some
circumstances the learner may choose not to use the full power of $\H$ (a neural
network example is early-stopping). For simplicity in this paper we
abstract away from such features of the algorithm $\A$ and assume that
it uses the entire hypothesis space $\H$.} is represented by the choice
of hypothesis space $\H$.

\subsection{The Bias Learning Model}
\label{EPsec}
The main extra assumption of the bias learning model introduced here
is that the learner is embedded in an {\em environment} of related
tasks, and can sample from the environment to generate multiple
training sets belonging to multiple different tasks. In the above
model of ordinary (single-task) learning, a learning task is
represented by a distribution $P$ on $X\times Y$. So in the bias
learning model, an environment of learning problems is represented by
a pair $(\P,Q)$ where $\P$\glossary{$\P$}{Set of all learning tasks $P$} is the set of all probability distributions
on $X\times Y$ (\ie $\P$ is the set of all possible learning
problems), and $Q$\glossary{$Q$}{Distribution over learning tasks} is a distribution on $\P$. $Q$ controls which
learning problems the learner is likely to see\footnote{$Q$'s domain
is a $\sigma$-algebra of subsets of $\P$. A suitable one for our
purposes is the Borel $\sigma$-algebra $\B(\P)$ generated by the
topology of weak convergence on $\P$. If we assume that $X$ and $Y$
are separable metric spaces, then $\P$ is also a separable metric
space in the Prohorov metric (which metrizes the topology of weak
convergence) \cite{parthasarathy67}, so there is no problem with the existence of
measures on $\B(\P)$. See Appendix \ref{permsec} for further
discussion, particularly the proof of part \ref{4} in Lemma
\ref{permlem}.}. For example, if the learner is in a face recognition
environment, $Q$ will be highly peaked over face-recognition-type
problems, whereas if the learner is in a character recognition
environment $Q$ will be peaked over character-recognition-type
problems (here, as in the introduction, we view these environments as
sets of individual classification problems, rather than single,
multiple class classification problems).

Recall from the last paragraph of the previous section that the
learner's bias is represented by its choice of hypothesis space
$\H$. So to enable the learner to learn the bias, we supply it with a
{\em family} or set of hypothesis spaces $\HH :=
\{\H\}$\glossary{$\HH$}{Family of hypothesis spaces}. 

Putting all this together, formally a {\em learning to learn} or {\em bias
learning} problem consists of:
\begin{itemize} 
\item an {\em input space} $X$ and an {\em output space} $Y$ (both of
which are separable metric spaces),
\item a {\em loss function} $l\colon Y\times Y\to \R$,
\item an {\em environment} $(\P,Q)$ where $\P$ is the set of all
probability distributions on $X\times Y$ and $Q$ is a distribution on
$\P$,
\item a {\em hypothesis space family} $\HH = \{\H\}$ where each $\H\in\HH$
is a set of functions $h\colon X\to Y$. 
\end{itemize}

>From now on we will assume the loss function $l$ has range
$[0,1]$, or equivalently, with rescaling, we assume that $l$ is bounded.

We define the goal of a bias learner to be to find a hypothesis space
$\H\in\HH$ minimizing the following loss:
\begin{align}
\label{exploss}
\er_Q(\H) &:= \int_\P\inf_{h\in \H} \er_P(h)\,dQ(P) \\
&=\int_\P\inf_{h\in \H} \int_{X\times Y} l(h(x), y)\, dP(x,y)
\,dQ(P). \nonumber\glossary{$\er_Q(\H)$}{Loss of hypothesis space $\H$ on environment $Q$}
\end{align}
The only way $\er_Q(\H)$ can be small is if, with high
$Q$-probability, $\H$ contains a good solution $h$ to any problem $P$
drawn at random according to $Q$. In this sense $\er_Q(\H)$ measures how
appropriate the bias embodied by $\H$ is for the environment $(\P,Q)$.

In general the learner will not know $Q$, so it will not be able to
find an $\H$ minimizing $\er_Q(\H)$ directly. However, the learner can
sample from the environment in the following way:
\begin{itemize}
\item Sample $n$ times from $\P$ according to $Q$ to yield:\\
$P_1,\dots,P_n$.
\item Sample $m$ times from $X\times Y$ according to each $P_i$ to yield:\\
$z_i = \{(x_{i1},y_{i1})\dots,(x_{im},y_{im})\}$.
\item The resulting $n$ training sets---henceforth called an {\em
$(n,m)$-sample} if they are generated by the above process---are
supplied to the learner. In the sequel, an $(n,m)$-sample will be
denoted by $\z$\glossary{$\z$}{$(n,m)$-sample} and written as a matrix:
\begin{equation}
\begin{array}{ccccc}
& (x_{11},y_{11}) & \cdots & (x_{1m}, y_{1m}) & = z_1 \\
\z:= &  \vdots & \ddots & \vdots & \vdots\\ 
& (x_{n1},y_{n1}) & \cdots & (x_{nm}, y_{nm}) & = z_n
\end{array}
\end{equation}
\end{itemize}
An $(n,m)$-sample is simply $n$ training sets
$z_1,\dots,z_n$ sampled from $n$ different learning tasks
$P_1,\dots,P_n$, where each task is selected according to the
environmental probability distribution $Q$. The size of each training
set is kept the same primarily  to facilitate the analysis. 

Based on the information contained in $\z$, the learner must choose a
hypothesis space $\H\in\HH$. One way to do this would be for
the learner to find an $\H$ minimizing  the {\em empirical loss} on $\z$,
where this is defined by:
\begin{equation}
\label{emploss}
\erh_\z(\H) :=\frac1n\sum_{i=1}^n
\inf_{h\in \H}\erh_{z_i}(h) \glossary{$\erh_\z(\H)$}{Empirical loss of $\H$ on $\z$}
\end{equation}
Note that $\erh_\z(\H)$ is simply the average of the best possible
empirical error achievable on each training set $z_i$, using a
function from $\H$. It is a biased estimate of $\er_Q(\H)$. An
unbiased estimate of $\er_Q(\H)$ would require choosing an $\H$
with minimal average error over the $n$ distributions $P_1,\dots,P_n$, 
where this is defined by $\frac1n\sum_{i=1}^n \inf_{h\in \H}\er_{P_i}(h)$. 


As with ordinary learning, it is likely there are more intelligent
things to do with the training data $\z$ than minimizing
\eqref{emploss}. Denoting the set of all $(n,m)$-samples by $\Znm$, a
general ``bias learner'' is a map $\A$ that takes $(n,m)$-samples as
input and produces hypothesis spaces $\H\in\HH$ as output:
\begin{equation}
\label{Aeqn}
\A\colon\bigcup_{\substack{n>0\\m > 0}} \Znm \rightarrow \HH.\glossary{$\A$}{Bias learning algorithm}
\end{equation}
(as stated, $\A$ is a deterministic bias learner, however it is
trivial to extend our results to stochastic learners). 

Note that in this paper we are concerned only with the sample
complexity properties of a bias learner $\A$; we do not discuss issues
of the computability of $\A$.

Since $\A$ is searching for entire hypothesis spaces $\H$ within a
family of such hypothesis spaces $\HH$, there is an extra
representational question in our model of bias learning that is not
present in ordinary learning, and that is how the family $\HH$ is
represented and searched by $\A$. We defer this discussion until
Section \ref{sec:biasrep}, after the main sample complexity results
for this model of bias learning have been introduced. For the specific 
case of learning a set of features suitable for an environment of
related learning problems, see Section \ref{featuresec}. 

Regardless of how the learner chooses its hypothesis space $\H$, if we
have a uniform bound (over all $\H\in\HH$) on the probability of large
deviation between $\erh_\z(\H)$ and $\er_Q(\H)$, and we can compute an
upper bound on $\erh_\z(\H)$, then we can bound the bias learner's
``generalization error'' $\er_Q(\H)$.  With this view, the question of
generalization within our bias learning model becomes: how many tasks ($n$)
and how many examples of each task ($m$) are required to ensure that
$\erh_\z(\H)$ and $\er_Q(\H)$ are close with high probability,
uniformly over all $\H\in\HH$?
Or, informally, how many tasks and how many examples of each task are
required to ensure that a hypothesis space with good solutions to all
the training tasks will contain good solutions to novel tasks drawn
from the same environment?

It turns out that this kind of uniform convergence for bias learning
is controlled by the ``size'' of certain function classes derived from
the hypothesis space family $\HH$, in much the same way as the
VC-dimension of a hypothesis space $\H$ controls uniform convergence
in the case of Boolean function learning (Theorem \ref{vcthm}). 
These ``size'' measures and other auxiliary definitions needed to
state the main theorem are introduced in the following subsection.

\subsection{Covering Numbers}
\begin{defn}
\label{spacedef}
For any hypothesis $h\colon X\to Y$, define 
$h_l\colon X\times Y\to [0,1]$\glossary{$h_l$}{Function induced by $h$ and $l$}
by 
\begin{equation}
h_l(x,y) := l(h(x),y)
\end{equation}
For any hypothesis space $\H$ in the hypothesis space family $\HH$, 
define 
\begin{equation}
\H_l:= \{h_l\colon h\in \H\}.\glossary{$\H_l$}{Set of $h_l$}
\end{equation}
For any sequence of $n$ hypotheses $(h_1,\dots,h_n)$, define 
$(h_1,\dots,h_n)_l\colon (X\times Y)^n\to [0,1]$ by 
\begin{equation}
(h_1,\dots,h_n)_l(x_1,y_1,\dots,x_n,y_n) := \frac1n\sum_{i=1}^n l(h_i(x_i),y_i).
\end{equation}
We will also use $\h_l$ to denote $(h_1,\dots,h_n)_l$\glossary{$(h_1,\dots,h_n)_l$}{Average 
of $h_{1,l}, \dots,h_{n,l}$}\glossary{$\h_l$}{Same as$(h_1,\dots,h_n)_l$}.
For any $\H$ in the hypothesis space family $\HH$, define 
\begin{equation}
\H^n_l  := \{(h_1,\dots,h_n)_l\colon h_1,\dots,h_n\in \H\}.\glossary{$\H^n_l$}{Set of $(h_1,\dots,h_n)_l$}
\end{equation}
Define
\begin{equation} 
\HH^n_l := \bigcup_{\H\in\HH} \H^n_l.\glossary{$\HH^n_l$}{Set of $\H^n_l$}
\end{equation}
\end{defn}
In the first part of the definition above, hypotheses $h\colon X\to Y$
are turned into functions $h_l$ mapping $X\times Y\to [0,1]$ by
composition with the loss function. $\H_l$ is then just the collection
of all such functions where the original hypotheses come from
$\H$. $\H_l$ is often called a {\em loss-function class}. In our case
we are interested in the average loss across $n$ tasks, where each of
the $n$ hypotheses is chosen from a fixed hypothesis space $\H$. This
motivates the definition of $\h_l$ and $\H^n_l$. Finally, $\HH^n_l$ is
the collection of all $(h_1,\dots,h_n)_l$, with the restriction that
all $h_1,\dots,h_n$ belong to a single hypothesis space $\H\in\HH$.
\begin{defn}
\label{stardef}
For each $\H\in \HH$, define $\H^*\colon \P\to
[0,1]$\glossary{$\H^*$}{Function on probability distributions} by 
\begin{equation}
\H^*(P) := \inf_{h\in \H} \er_P(h).
\end{equation}
For the hypothesis space family $\HH$, define 
\begin{equation}
\HH^* := \{\H^*\colon \H\in \HH\}.\glossary{$\HH^*$}{Set of $\H^*$}
\end{equation}
\end{defn} 
It is the ``size'' of $\HH^n_l$ and $\HH^*$ that controls how large 
the $(n,m)$-sample $\z$ must be to ensure $\erh_\z(\H)$ and $\er_Q(\H)$ are
close uniformly over all $\H\in\HH$. Their size will be defined in
terms of certain covering numbers, and for this
we need to define how to measure the distance between
elements of $\HH^n_l$ and also between elements of $\HH^*$.
\begin{defn}
\label{metricdef}
Let $\Pb = (P_1,\dots,P_n)$ be any sequence of $n$ probability
distributions on $X\times Y$.
For any $\h_l,\h'_l\in \HH^n_l$, define
\begin{equation}
\label{dp}
\begin{split}
d_\scPb(\h_l,\h'_l) := \int_{(X\times Y)^n}
|\h_l(x_1,y_1,\dots,x_n,y_n) &-
\h'_l(x_1,y_1,\dots,x_n,y_n)| \\
\,
dP_1(x_1,y_1) \dots dP_n(x_n,y_n)\glossary{$d_\scPb$}{Pseudo-metric on $\H^n_l$}
\end{split}
\end{equation}
\noindent Similarly, for any distribution $Q$ on $\P$ and any
$\H_1^*,\H_2^*\in \HH^*$, define
\begin{equation}
\label{dq}
d_Q(\H_1^*,\H_2^*) := \int_\P \left|\H_1^*(P) - \H_2^*(P)\right | \,dQ(P)\glossary{$d_Q$}{Pseudo-metric on $\HH^*$}
\end{equation}
\end{defn}
It is easily verified that $d_\scPb$ and $d_Q$ are
pseudo-metrics\footnote{A pseudo-metric $d$ is a metric without
the condition that $d(x,y) = 0 \Rightarrow x = y$.} on $\HH^n_l$ and
$\HH^*$ respectively.

\begin{defn}
\label{covdef}
An $\ep$-cover of $(\HH^*,d_Q)$ is a set $\{\H^*_1,\dots,\H^*_N\}$
such that for all $\H^*\in\HH^*$, $d_Q(\H^*,\H^*_i) \leq \ep$ for some
$i=1\dots N$. Note that we do not require the $\H^*_i$ to be contained
in $\HH^*$, just that they be measurable functions on $\P$. Let
$\N(\ep,\HH^*,d_Q)$ denote the size of the smallest such cover. Define
the {\em capacity} of $\HH^*$ by 
\begin{equation}
\label{bub}
\C(\ep,\HH^*) := \sup_{Q} \N(\ep,\HH^*,d_Q)\glossary{$\N(\ep,\HH^*,d_Q)$}{Covering number of $\HH^*$}\glossary{$\C(\ep,\HH^*)$}{Capacity of $\HH^*$}
\end{equation}
where the supremum is over all probability measures on $\P$. 
$\N(\ep,\HH^n_l,d_\scPb)$ is defined in a similar way, using
$d_\scPb$ in place of $d_Q$. Define the {\em capacity} of $\HH^n_l$ by:
\begin{equation}
\label{bib}
\C(\ep,\HH^n_l) := \sup_{\scPb} \N(\ep,\HH^n_l,d_\scPb)\glossary{$\N(\ep,\HH^n_l,d_\scPb)$}{Covering number of
$\HH^n_l$}\glossary{$C(\ep,\HH^n_l)$}{Capacity of $\HH^n_l$}
\end{equation}
where now the supremum is over all sequences of $n$ probability
measures on $X\times Y$. 
\end{defn}

\subsection{Uniform Convergence for Bias Learners}
Now we have enough machinery to state the main theorem.  In the
theorem the hypothesis space family is required to be {\em
permissible}. Permissibility is discussed in detail in Appendix
\ref{permsec}, but note that it is a weak measure-theoretic condition
satisfied by almost all ``real-world'' hypothesis space families. All
logarithms are to base $e$. 
\begin{thm}
\label{biaslearnthm}
Suppose $X$ and $Y$ are separable metric spaces and let $Q$ be any
probability distribution on $\P$, the set of all distributions on
$X\times Y$. Suppose $\z$ is an $(n,m)$-sample generated by sampling
$n$ times from $\P$ according to $Q$ to give $P_1,\dots,P_n$, and then
sampling $m$ times from each $P_i$ to generate $z_i =
\{(x_{i1},y_{i1}),\dots,(x_{im},y_{im})\}$, $i=1,\dots,n$.  Let
$\HH=\{\H\}$ be any permissible hypothesis space family.  If the
number of tasks $n$ satisfies
\begin{align}
\label{nbound}
n &\geq
\max\left\{\frac{256}{\ep^2}\ln\frac{8\C\(\frac{\ep}{32},\HH^*\)}\delta,
\frac{64}{\ep^2}\right\}, \\ 
\intertext{and the number of examples $m$
of each task satisfies}
\label{mbound}
m &\geq
\max\left\{\frac{256}{n\ep^2}\ln\frac{8\C(\frac{\ep}{32},\HH^n_l)}\delta,
\frac{64}{\ep^2}\right\},
\end{align}
then with probability at least $1-\delta$ (over the $(n,m)$-sample
$\z$), all $\H\in\HH$ will satisfy
\begin{equation}
\label{blip}
\er_Q(\H) \leq \erh_\z(\H) + \ep
\end{equation}
\end{thm}
\begin{proof}
See Appendix \ref{biaslearnproofsec}.
\end{proof}

\noindent There are several important points to note about Theorem
\ref{biaslearnthm}:
\begin{enumerate}
\item Provided the capacities $\C\(\ep,\HH^*\)$ and
$\C(\ep,\HH^n_l)$ are finite, the theorem shows that {\em
any} bias learner that selects hypothesis spaces from $\HH$ can bound
its generalisation error $\er_Q(\H)$ in terms of $\erh_\z(\H)$ for
sufficiently large $(n,m)$-samples $\z$. Most bias learner's will not
find the exact value of $\erh_\z(\H)$ because it involves finding the
smallest error of any hypothesis $h\in\H$ on each of the $n$ training
sets in $\z$. But any upper bound on $\erh_\z(\H)$ (found, for example
by gradient descent on some error function) will still give an upper
bound on $\er_Q(\H)$. See Section \ref{sec:featalg} for a brief
discussion on how this can be achieved in a feature learning setting. 

\item In order to learn bias (in the sense that $\er_Q(\H)$ and 
$\erh_\z(\H)$ are close uniformly over all $\H\in\HH$), both the
number of tasks $n$ and the number of examples of each task $m$ must
be sufficiently large. This is intuitively reasonable because the bias
learner must see both sufficiently many tasks to be confident of the
nature of the environment, and sufficiently many examples of each task
to be confident of the nature of each task. 
\item Once the learner has found an $\H\in\HH$ with a small value of
$\erh_\z(\H)$, it can then use $\H$ to learn novel tasks $P$ drawn
according to $Q$. One then has the following theorem bounding the
sample complexity required for good generalisation when learning with
$\H$ (the proof is very similar to the proof of the bound on $m$ in Theorem
\ref{biaslearnthm}).
\begin{thm}
\label{ordthm}
Let $z=\{(x_1,y_1),\dots,(x_m,y_m)\}$ be a training set generated by
sampling from $X\times Y$ according to some distribution $P$. Let $\H$
be a permissible hypothesis space. For all $\ep, \delta$ with
$0<\ep,\delta <1$, if the number of training examples
$m$ satisfies 
\begin{equation}
\label{ordmeqn}
m \geq \max\left\{\frac{64}{\ep^2} 
\ln \frac{4\C\(\frac{\ep}{16},\H_l\)}{\delta}, \frac{16}{\ep^2}\right\}
\end{equation}
then with probability at least $1-\delta$, all $h\in\H$ will satisfy 
$$
\er_P(h) \leq \erh_z(h) + \ep.
$$
\end{thm}
The capacity $\C\(\ep,\H\)$ appearing in equation \eqref{ordmeqn} is
defined in an analogous fashion to the capacities in Definition
\ref{covdef} (we just use the pseudo-metric $d_P(h_l,h_l') :=
\int_{X\times Y} |h_l(x,y) - h'_l(x,y)| \,dP(x,y)$). The important
thing to note about Theorem \ref{ordthm} is that the number of
examples required for good generalisation when learning novel tasks is
proportional to the logarithm of the capacity of the learnt hypothesis
space $\H$. In contrast, if the learner does not do any bias learning,
it will have no reason to select one hypothesis space $\H\in \HH$ over
any other and consequently it would have to view as a candidate
solution any hypothesis in any of the hypothesis spaces
$\H\in\HH$. Thus, its sample complexity will be proportional to the
capacity of $\cup_{\H\in\HH}\{\H_l\} = \HH^1_l$, which in general will be
considerably larger than the capacity of any individual $\H\in\HH$. So
by learning $\H$ the learner has {\em learnt to learn} in the
environment $(\P,Q)$ in the sense that it needs far smaller training
sets to learn novel tasks.

\item Having learnt a hypothesis space $\H$ with a small value of
$\erh_\z(\H)$, Theorem \ref{biaslearnthm} tells us that with probability at
least $1-\delta$, the expected value of $\inf_{h\in\H}\er_P(h)$ on a
novel task $P$ will be less than $\erh_\z(\H) + \ep$. Of course, this
does not rule out really bad performance on some tasks $P$. However,
the probability of generating such ``bad'' tasks can be bounded. In
particular, note that $\er_Q(\H)$ is just the expected value of the
function $\H^*$ over $\P$, and so by Markov's inequality, for $\gamma
> 0$,
\begin{align*}
\Pr\left\{P\colon \inf_{h\in\H} \er_P(h) \geq \gamma\right\} &=
\Pr\left\{P\colon \H^*(P) \geq \gamma\right\} \\ 
&\leq \frac{E_Q \H^*}{\gamma} \\ 
&=\frac{\er_Q(\H)}{\gamma} \\ 
&\leq \frac{\erh_\z(\H) + \ep}{\gamma}\quad \text{(with probability
$1-\delta$).} 
\end{align*}
\item \label{last}
Keeping the accuracy and confidence parameters $\ep,\delta$
fixed, note that the number of examples required of each task for good
generalisation obeys
\begin{equation}
m = O\(\frac1n\ln \C\(\ep,\HH^n_l\)\).
\end{equation}
So provided $\ln \C\(\ep,\HH^n_l\)$ increases sublinearly with $n$, the
upper bound on the number of examples required of each task will {\em
decrease} as the number of tasks increases. This shows that for
suitably constructed hypothesis space families it is possible to {\em
share} information between tasks. This is discussed further
after Theorem \ref{ntaskthm} below.
\end{enumerate}

\subsection{Choosing the Hypothesis Space Family $\mathbold{\HH}$.}
\label{sec:biasrep}
Theorem \ref{biaslearnthm} only provides conditions under which
$\erh_\z(\H)$ and $\er_Q(\H)$ are close, it does not guarantee that
$\er_Q(\H)$ is actually small. This is governed by the choice of
$\HH$. If $\HH$ contains a hypothesis space $\H$ with a small value of
$\er_Q(\H)$ and the learner is able to find an $\H\in\HH$ minimizing
error on the $(n,m)$ sample $\z$ (\ie minimizing $\erh_\z(\H)$), then, 
for sufficiently large $n$ and $m$, Theorem \ref{biaslearnthm} ensures 
that with high probability $\er_Q(\H)$ will be small. However, a bad choice
of $\HH$ will mean there is no hope of finding an $\H$ with small
error. In this sense the choice of $\HH$ represents the {\em
hyper-bias} of the learner.

Note that from a sample complexity point of view, the {\em optimal}
hypothesis space family to choose is one containing a single, minimal
hypothesis space $\H$ that contains good
solutions to all of the problems in the environment (or at least a set
of problems with high $Q$-probability), and no more. For then there
is no bias learning to do (because there is no choice to be made
between hypothesis spaces), the output of the bias
learning algorithm is guaranteed to be a good hypothesis space for the 
environment, and since the hypothesis space is minimal, learning any
problem within the environment using $\H$ will require the smallest possible
number of examples. However, this
scenario is analagous to the trivial scenario in ordinary learning in
which the learning algorithm contains a single, optimal hypothesis for 
the problem being learnt. In that case there is no learning to be
done, just as there is no bias learning to be done if the correct
hypothesis space is already known. 

At the other extreme, if $\HH$ contains a single hypothesis space
$\H$ consisting of all possible functions from $X\to Y$ then bias learning
is impossible because the bias learner cannot produce a restricted
hypothesis space as output, and hence cannot produce a hypothesis
space with improved sample complexity requirements on as yet unseen
tasks. 

Focussing on these two extremes highlights the minimal requirements on
$\HH$ for successful bias learning to occur: the hypothesis spaces
$\H\in \HH$ must be strictly smaller than the space of all functions
$X\to Y$, but not so small or so ``skewed'' that none of them
contain good solutions to a large majority of the problems in the
environment.

It may seem that we have simply replaced the problem of selecting the
right bias (\ie selecting the right hypothesis space $\H$) with the
equally difficult problem of selecting the right hyper-bias (\ie the
right hypothesis space family $\HH$). However, in many cases selecting
the right hyper-bias is far easier than selecting the right bias. For
example, in Section \ref{featuresec} we will see how the feature
selection problem may be viewed as a bias selection problem. Selecting
the right features can be extremely difficult if one knows little
about the environment, with intelligent trial-and-error typically the
best one can do. However, in a bias learning scenario, one only has to
specify that a set of features should exist, find a loosely
parameterised set of features (for example neural networks), and then
learn the features by sampling from multiple related tasks. 





\subsection{Learning Multiple Tasks}
\label{ntasksec}
It may be that the learner is not interested in learning to learn, but
just wants to learn a fixed set of $n$ tasks from the environment
$(\P,Q)$.  As in the previous section, we assume the learner starts
out with a hypothesis space family $\HH$, and also that it receives an
$(n,m)$-sample $\z$ generated from the $n$ distributions
$P_1,\dots,P_n$. This time, however, the learner is simply looking for
$n$ hypotheses $(h_1,\dots,h_n)$, all contained in the same hypothesis
space $\H$, such that the average generalization error of the $n$
hypotheses is minimal. Denoting $(h_1,\dots,h_n)$ by
$\h$\glossary{$\h$}{Sequence of $n$ hypotheses $(h_1,\dots,h_n)$} and writing
$\Pb = (P_1,\dots,P_n)$\glossary{$\Pb$}{Sequence of $n$ distributions
$(P_1,\dots,P_n)$}, 
this error is given by:
\begin{align}
\label{expnerr}
\er_\scPb(\h) &:=\frac1n\sum_{i=1}^n \er_{P_i}(h_i) \\
	     &= \frac1n\sum_{i=1}^n \int_{X\times Y} l(h_i(x),y)\,
	     dP_i(x,y), \nonumber\glossary{$\er_\scPb(\h)$}{Average loss of $\h$ on $\Pb$}
\end{align}
and the empirical loss of $\h$ on $\z$ is 
\begin{align}
\label{empnerr}
\erh_\z(\h) &:=\frac1n\sum_{i=1}^n\erh_{z_i}(h_i) \\
             &=\frac1n\sum_{i=1}^n\frac1m\sum_{j=1}^m l(h_i(x_{ij}),
             y_{ij}).\nonumber\glossary{$\erh_\z(\h)$}{Average loss of $\h$ on $\z$}
\end{align}
As before, regardless of how the learner chooses $(h_1,\dots,h_n)$, if
we can prove a uniform bound on the probability of large deviation
between $\erh_\z(\h)$ and $\er_\scPb(\h)$ then any $(h_1,\dots,h_n)$
that perform well on the training sets $\z$ will with high probability
perform well on future examples of the same tasks.  
\begin{thm}
\label{ntaskthm}
Let $\Pb = (P_1,\dots,P_n)$ be $n$ probability distributions on
$X\times Y$ and let $\z$ be an $(n,m)$-sample generated by sampling
$m$ times from $X\times Y$ according to each $P_i$. 
Let $\HH=\{\H\}$ be any permissible hypothesis space family. 
If the number of examples $m$ of each task satisfies
\begin{equation}
\label{nmbound}
m \geq
\max\left\{\frac{64}{n\ep^2}\ln\frac{4\C(\frac{\ep}{16},\HH^n_l)}\delta,
\frac{16}{\ep^2}\right\}
\end{equation}
then with probability at least $1-\delta$ (over the choice of 
$\z$), any $\h\in\HH^n$ will satisfy
\begin{equation}
\label{blipp}
\er_\scPb(\h) \leq \erh_\z(\h) + \ep
\end{equation}
(recall Definition \ref{covdef} for the meaning of $\C(\ep,\HH^n_l)$).
\end{thm}
\begin{proof} Omitted (follow the proof of the bound on $m$ in Theorem
\ref{biaslearnthm}).
\end{proof}
The bound on $m$ in Theorem \ref{ntaskthm} is virtually identical to
the bound on $m$ in Theorem \ref{biaslearnthm}, and note again that it
depends {\em inversely} on the number of tasks $n$ (assuming that the
first part of the ``max'' expression is the dominate one). Whether
this helps depends on the rate of growth of
$\C(\frac{\ep}{16},\HH^n_l)$ as a function of $n$. The following
Lemma shows that this growth is always small enough to ensure that we
never do worse by learning multiple tasks (at least in terms of the
upper bound on the number of examples required per task).
\begin{lem}
For any hypothesis space family $\HH$, 
\label{nboundlem}
\begin{equation}
\C\(\ep,\HH^1_l\) \leq \C\(\ep,\HH^n_l\) \leq \C\(\ep,\HH^1_l\)^n.
\end{equation}
\end{lem}
\begin{proof}
Let $K$  denote the set of all functions $(h_1,\dots,h_n)_l$ where each
$h_i$ can be a member of any hypothesis space $\H\in \HH$ (recall
Definition \ref{spacedef}). Then $\HH^n_l \subseteq K$ and so
$\C\(\ep,\HH^n_l\) \leq \C\(\ep,K\)$. By Lemma \ref{prodlem} in
Appendix \ref{capproof}, $\C\(\ep,K\) \leq \C\(\ep, \HH^1_l\)^n$ and
so the right hand inequality follows.

\sloppy
For the first inequality, let $P$ be any probability measure on
$X\times Y$ and let $\Pb$ be the measure on $(X\times Y)^n$ obtained
by using $P$ on the first copy of $X\times Y$ in the product, and
ignoring all other elements of the product. Let $N$ be an
$\ep$-cover for $(\HH^n_l, d_\scPb)$. Pick any $h_l\in\HH^1_l$ and let
$(g_1,\dots, g_n)_l\in N$ be such that $d_\scPb\((h,h,\dots,h)_l, 
(g_1,\dots,g_n)_l\)\leq \ep$. But by construction, $d_\scPb\((h,h,\dots,h)_l, 
(g_1,\dots,g_n)_l\) = d_P(h,(g_1)_l)$, which establishes the first
inequality.
\end{proof}
By Lemma \ref{nboundlem}
\begin{equation}
\label{fart}
\ln \C\(\ep,\HH^1_l\) \leq \ln \C\(\ep,\HH^n_l\) \leq n\ln
\C\(\ep,\HH^1_l\).
\end{equation}
So keeping the accuracy parameters $\ep$ and $\delta$ fixed, and
plugging \eqref{fart} into \eqref{nmbound}, we see that the upper
bound on the number of examples required of each task never {\em
increases} with the number of tasks, and at best decreases as
$O(1/n)$. Although only an upper bound, this provides a strong
hint that learning multiple related tasks should be advantageous on a
``number of examples required per task'' basis.  In Section
\ref{featuresec} it will be shown that for feature learning all types of
behavior are possible, from no advantage at all to $O(1/n)$ decrease.

\subsection{Dependence on $\mathbold{\ep}$}
In Theorems \ref{biaslearnthm}, \ref{ordthm} and \ref{ntaskthm} the
bounds on sample complexity all scale as $1/\ep^2$. This behavior can
be improved to $1/\ep$ if the empirical loss is always guaranteed to
be zero (\ie we are in the realizable case). The same behavior
results if we are interested in relative deviation between empirical
and true loss, rather than absolute deviation. Formal theorems along
these lines are stated in Appendix \ref{realisable}. 

\section{Feature Learning}
\label{featuresec}
The use of restricted feature sets is nearly ubiquitous as a method of 
encoding bias in many areas of machine learning and statistics,
including classification, regression and density estimation. 

In this section we show how the problem of choosing a set of features
for an environment of related tasks can be recast as a bias learning
problem. Explicit bounds on $\C(\HH^*, \ep)$ and $\C(\HH^n_l, \ep)$ are
calculated for general feature classes in Section \ref{genfeatsec}.
These bounds are applied to the problem of learning a neural network
feature set in Section \ref{nnetsec}.

\subsection{The Feature Learning Model}
\label{sec:featlearn}
Consider the following quote from \citeA{vapnik96a}:  
\begin{quote}
The classical approach to estimating multidimensional functional
dependencies is based on the following belief:

Real-life problems are such that there exists a small number of
``strong features,'' simple functions of which (say linear
combinations) approximate well the unknown function. Therefore, it
is necessary to carefully choose a low-dimensional feature space and
then to use regular statistical techniques to construct an
approximation.
\end{quote}

In general a set of ``strong features'' may be viewed as a function
$f\colon X\to V$ mapping the input space $X$ into some (typically
lower) dimensional space $V$.  Let
$\F=\{f\}$\glossary{$\F$}{Set of feature maps} be a set of such feature
maps (each $f$ may be viewed as a set of features $(f_1,\dots,f_k)$ if
$V=\R^k$). It is the $f$ that must be ``carefully chosen'' in the
above quote. In general, the ``simple functions of the features'' may
be represented as a class of functions $\G$\glossary{$\G$}{Output
class composed with feature maps $f$} mapping $V$ to $Y$.  If
for each $f\in\F$ we define the hypothesis space
$\comp{\G}{f}:=\{\comp{g}{f}\colon
g\in\G\}$\glossary{$\comp{\G}{f}$}{Hypothesis space associated with
$f$}, then we have the
hypothesis space family $\HH$
\begin{equation}
\label{hhdef}
\HH:= \{\comp{\G}{f}\colon f\in\F\}.
\end{equation}
Now the problem of ``carefully choosing'' the right features $f$ is
equivalent to the bias learning problem ``find the right hypothesis
space $\H\in\HH$''. Hence, provided the learner is embedded within an
environment of related tasks, and the capacities $\C(\HH^*,\ep)$ and
$\C(\HH^n_l,\ep)$ are finite, Theorem \ref{biaslearnthm} tells us that
the feature set $f$ can be {\em learnt} rather than carefully chosen.
This represents an important simplification, as choosing a set of
features is often the most difficult part of any machine learning
problem. 

In Section \ref{genfeatsec} we give a theorem bounding
$\C(\HH^*,\ep)$ and $\C(\HH^n_l,\ep)$ for general feature classes. The
theorem is specialized to neural network classes in Section \ref{nnetsec}.

Note that we have forced the function class $\G$ to be the same for
all feature maps $f$, although this is not necessary. Indeed variants
of the results to follow can be obtained if $\G$ is allowed to vary
with $f$.

\subsection{Capacity Bounds for General Feature Classes}
\label{genfeatsec}
Notationally it is easier to view the feature maps $f$ as mapping from
$X\times Y$ to $V\times Y$ by $(x,y) \mapsto (f(x),y)$, and also to
absorb the loss function $l$ into the definition of $\G$ by viewing 
each $g\in\G$ as a map from $V\times Y$ into $[0,1]$ via $(v,y)\mapsto
l(g(v),y)$. Previously this latter function would have been denoted
$g_l$ but in what follows we
will drop the subscript $l$ where this does not cause confusion. The
class to which $g_l$ belongs will still be denoted by
$\G_l$\glossary{$\G_l$}{Loss function class associated with $\G$}. 

With the above definitions let $\comp{\G_l}{\F}:= \{\comp{g}{f}\colon
g\in\G_l, f\in\F\}$. Define the capacity of $\G_l$ in the usual way,
$$
\C\(\ep,\G_l\) := \sup_P \N\(\ep, \G_l, d_P\) \glossary{$\N\(\ep, \G_l, d_P\)$}{Covering number of $\G_l$}\glossary{$\C\(\ep, \G_l\)$}{Capacity of $\G_l$}
$$
where the supremum is over all probability measures on $V\times Y$,
and $d_P(g,g') := \int_{V\times Y} |g(v,y) - g'(v,y)|\, dP(v,y)$. To
define the capacity of $\F$ we first define a pseudo-metric
$d_{[P,\G_l]}$ on $\F$ by ``pulling back'' the $L^1$ metric on $\R$
through $\G_l$ as follows:
\begin{equation}
\label{fmetricdef}
d_{[P,\G_l]}(f,f') := \int_{X\times Y} \sup_{g\in\G_l} |\comp{g}{f}(x,y) - 
\comp{g}{f'}(x,y)|\, dP(x,y).\glossary{$d_{[P,\G_l]}(f,f')$}{Pseudo-metric on feature maps $f,f'$}
\end{equation}
It is easily verified that $d_{[P,\G_l]}$ is a pseudo-metric.  Note that
for $d_{[P,\G_l]}$ to be well defined the supremum over $\G_l$ in the
integrand must be measurable. This is guaranteed if the hypothesis
space family $\HH=\{\comp{\G_l}{f}\colon f\in\F\}$ is permissible
(Lemma \ref{permlem}, part \ref{3}).  Now define $\N(\ep,\F,
d_{[P,\G_l]})$ to be the smallest $\ep$-cover of the pseudo-metric space
$(\F,d_{[P,\G_l]})$ and the $\ep$-capacity of $\F$ (with respect to
$\G_l$) as
$$
\C_{\G_l}(\ep,\F) := \sup_P \N(\ep,\F,d_{[P,{\G_l}]})\glossary{$\N(\ep,\F,d_{[P,{\G_l}]})$}{Covering number of $\F$}
\glossary{$\C_{\G_l}(\ep,\F)$}{Capacity of $\F$}
$$
where the supremum is over all probability measures on $X\times Y$.
Now we can state the main theorem of this section.
\begin{thm}
\label{gencompthm}
Let $\HH$ be a hypothesis space family as in equation
\eqref{hhdef}. Then for all $\ep,\ep_1,\ep_2>0$ with
$\ep=\ep_1+\ep_2$, 
\begin{align}
\label{hhnlineq}
\C\(\ep, \HH^n_l\) &\leq \C\(\ep_1,{\G_l}\)^n \, \C_{\G_l}\(\ep_2,\F\) \\
\label{hhstarineq}
\C\(\ep,\HH^*\) &\leq \C_{\G_l}\(\ep,\F\)
\end{align}
\end{thm}
\begin{proof}
See Appendix \ref{capproof}.
\end{proof}
\subsection{Learning Neural Network Features}
\label{nnetsec}
In general, a set of features may be viewed as a map from the
(typically high-dimensional) input space $\R^d$ to a much smaller
dimensional space $\R^k$ ($k\ll d$). In this section we consider
approximating such a feature map by a one-hidden-layer neural network
with $d$ input nodes and $k$ output nodes (Figure \ref{nnet}).  We
denote the set of all such feature maps by $\{\Phi_w = (\phi_{w,1},
\dots, \phi_{w,k})\colon w\in D\}$ where $D$ is a bounded subset of
$\R^W$ ($W$ is the number of weights (parameters) in the first two
layers). This set is the $\F$ of the previous section.

Each feature $\phi_{w,i}\colon \R^d\to [0,1]$, $i=1,\dots, k$ is
defined by
\begin{equation}
\label{featurenode}
\phi_{w,i}(x) := \sigma\(\sum_{j=1}^l v_{ij} h_j(x) + v_{il+1}\) 
\end{equation}
where $h_j(x)$ is the output of the $jth$ node in the first hidden
layer, $(v_{i1}, \dots, v_{il+1})$ are the output node parameters for
the $i$th feature and $\sigma$ is a ``sigmoid'' squashing function
$\sigma\colon \R\to [0,1]$.  
Each first layer hidden node $h_i\colon \R^d
\to \R$, $i=1,\dots, l$, computes
\begin{equation}
\label{hiddennode}
h_i(x) := \sigma\(\sum_{j=1}^d u_{ij}x_j + u_{id+1}\)
\end{equation}
where $(u_{i1},\dots, u_{id+1})$ are the hidden node's parameters.  
We assume $\sigma$ is Lipschitz.\footnote{$\sigma$ is
Lipschitz if there exists a constant $K$ such that $|\sigma(x) -
\sigma(x')| \leq K|x-x'|$ for all $x,x'\in\R$.} The weight vector for the entire
feature map is thus
$$
w = (u_{11},\dots, u_{1d+1},\dots, u_{l1}, \dots, u_{ld+1}, v_{11},
\dots, v_{1l+1}, \dots, v_{k1}, \dots, v_{kl+1})
$$ 
and the total number of feature parameters $W = l(d+1) + k(l+1)$. 

\begin{figure}
\begin{center}
\leavevmode
\epsfysize=3in\epsfbox{unnamed.eps}
\caption{\label{nnet} Neural network for feature learning. The feature
map is implemented by the first two hidden layers. The $n$ output
nodes correspond to the $n$ different tasks in the $(n,m)$-sample
$\z$. Each node in the network computes a squashed linear function of
the nodes in the previous layer.}
\end{center}
\end{figure}

\sloppy
For argument's sake, assume the ``simple functions'' of the features
(the class $\G$ of the previous section) are squashed affine maps
using the same sigmoid function $\sigma$ above (in keeping with the
``neural network'' flavor of the features). Thus, each setting of the
feature weights $w$ generates a hypothesis space:
\begin{equation}
\label{hysp}
\H_w:= \left\{\sigma\(\sum_{i=1}^k \alpha_i \phi_{w,i} + \alpha_{k+1}\)\colon
(\alpha_1,\dots,\alpha_{k+1}) \in D'\right\},\glossary{$\H_w$}{Neural network hypothesis space}
\end{equation}
where $D'$ is a bounded subset of $\R^{k+1}$.
The set of all such hypothesis spaces,
\begin{equation}
\label{nnetfamily}
\HH := \{\H_w\colon w\in D\}
\end{equation}
is a hypothesis space family. The restrictions on the output layer
weights $(\alpha_1,\dots, \alpha_{k+1})$ and feature weights $w$, and the
restriction to a Lipschitz squashing function are needed to obtain
finite upper bounds on the covering numbers in Theorem
\ref{biaslearnthm}.

Finding a good set of features for the environment $(\P,Q)$ is
equivalent to finding a good hypothesis space $\H_w\in \HH$, which in
turn means finding a good set of feature map parameters $w$.

As in Theorem \ref{biaslearnthm}, the correct set of features may be learnt
by finding a hypothesis space with small error on a sufficiently large
$(n,m)$-sample $\z$. Specializing to squared loss, in the present framework the
empirical loss of $\H_w$ on $\z$ (equation \eqref{emploss}) is given by
\begin{equation}
\label{featemploss}
\erh_\z(\H_w) = \frac1n\sum_{i=1}^n \inf_{(\alpha_0,\alpha_1,\dots,\alpha_k)\in
D'}
\frac1m\sum_{j=1}^m \[\sigma\(\sum_{l=1}^k \alpha_l
\phi_{w,l}(x_{ij}) + \alpha_0\) - y_{ij}\]^2 
\end{equation}
Since our sigmoid function $\sigma$ only has range $[0,1]$, we also 
restrict the outputs $Y$ to this range. 

\subsubsection{Algorithms for Finding a Good Set of Features}
\label{sec:featalg}
Provided the squashing function $\sigma$ is differentiable, gradient
descent (with a small variation on backpropagation to compute the
derivatives) can be used to find feature weights $w$ minimizing
\eqref{featemploss} (or at least a local minimum of
\eqref{featemploss}). The only extra difficulty over and above
ordinary gradient descent is the appearance of ``$\inf$'' in the
definition of $\erh_\z(\H_w)$. The solution is to perform gradient
descent over both the output parameters $(\alpha_0, \dots, \alpha_k)$
for each node and the feature weights $w$. For more details see
\citeA{95a} and \citeA[chapter 4]{thesis}, where empirical results
supporting the theoretical results presented here are also given. 

\subsubsection{Sample Complexity Bounds for Neural-Network Feature
Learning}

The size of $\z$ ensuring that the resulting features will be good for
learning novel tasks from the same environment is given by Theorem
\ref{biaslearnthm}. All we have to do is compute the logarithm of the
covering numbers $\C(\ep,\HH^n_l)$ and $\C(\ep,\HH^*)$.  
\begin{thm}
\label{capthm}
Let $\HH = \left\{\H_w\colon w\in\R^W\right\}$ be a hypothesis
space family where each $\H_w$ is of the form 
$$
\H_w:= \left\{\sigma\(\sum_{i=1}^k \alpha_i \phi_{w,i}(\cdot) + \alpha_0\)\colon
(\alpha_1,\dots,\alpha_k) \in \R^k\right\},
$$
where $\Phi_w=(\phi_{w,1},\dots,\phi_{w,k})$ is a neural network with $W$
weights mapping from $\R^d$ to $\R^k$.
If the feature weights $w$ and the output weights
$\alpha_0,\alpha_1,\dots,\alpha_k$ are bounded, the squashing function
$\sigma$ is Lipschitz, $l$ is squared loss, and the output space
$Y=[0,1]$ (any bounded subset of $\R$ will do), then there exist constants $\kappa,\kappa'$
(independent of $\ep,W$ and $k$) such that for all $\ep > 0$,
\begin{align}
\label{one}
\ln\C(\ep,\HH^n_l) &\leq 2\((k+1)n + W\)\ln\frac{\kappa}{\ep} \\
\label{two}
\ln\C(\ep,\HH^*) &\leq 2 W\ln\frac{\kappa'}{\ep}
\end{align}
(recall that we have specialized to squared loss here). 
\end{thm}
\begin{proof}
See Appendix \ref{capproof}.
\end{proof}
Noting that our neural network hypothesis space family $\HH$ is
permissible, plugging \eqref{one} and \eqref{two} into
Theorem \ref{biaslearnthm} gives the following theorem.
\begin{thm}
\label{featthm}
Let $\HH = \{\H_w\}$ be a hypothesis space family where each hypothesis
space $\H_w$ is a set of squashed linear maps composed with a neural
network feature map, as above. Suppose the number of features is
$k$, and the total number of feature weights is W. Assume
all feature weights and output weights are bounded, and the squashing
function $\sigma$ is Lipschitz. Let $\z$ be an $(n,m)$-sample
generated from the environment $(\P,Q)$.  If
\begin{equation}
n \geq O\(\frac1{\ep^2}\[W\log\frac1{\ep} + \log\frac1\delta\]\),
\end{equation}
and
\begin{equation}
m \geq O\(\frac1{\ep^2}\[\(k + 1 +
\frac{W}{n} \)\log\frac1\ep + \frac1n\log\frac1\delta\]\)
\end{equation}
then with probability at least $1 - \delta$ any 
$\H_w\in\HH$ will satisfy
\begin{equation}
\er_Q(\H_w) \leq \erh_\z(\H_w) + \ep.
\end{equation}
\end{thm}

\subsubsection{Discussion}
\label{sec:discussion}
\begin{enumerate}
\item \label{noteone} Keeping the accuracy and confidence parameters
$\ep$ and $\delta$ fixed, the upper bound on the number of examples
required of each task behaves like $O(k + W/n)$. If the learner is
simply learning $n$ fixed tasks (rather than learning to learn), then
the same upper bound also applies (recall Theorem \ref{ntaskthm}).
\item Note that if we do away with the feature map altogether then
$W=0$ and the upper bound on $m$ becomes $O(k)$, independent of $n$
(apart from the less important $\delta$ term).  So in terms of the upper bound,
learning $n$ tasks becomes just as hard as learning one task. At the
other extreme, if we fix the output weights then effectively $k=0$ and
the number of examples required of each task decreases as
$O(W/n)$. Thus a range of behavior in the number of examples required
of each task is possible: from no improvement at all to an $O(1/n)$
decrease as the number of tasks $n$ increases (recall the discussion
at the end of Section
\ref{ntasksec}).
\item Once the feature map is learnt \cite<which can be achieved using the
techniques outlined in>[chapter 4]{95a,nips_97,thesis}, only the output weights have to be estimated to learn a
novel task. Again keeping the accuracy parameters fixed, this requires
no more that $O(k)$ examples.  Thus, as the number of tasks learnt
increases, the upper bound on the number of examples required of each
task decays to the minimum possible, $O(k)$.
\item 
\label{note4}
If the ``small number of strong features'' assumption is
correct, then $k$ will be small. However, typically we will have very
little idea of what the features are, so to be confident that the
neural network is capable of implementing a good feature set it will
need to be very large, implying $W\gg k$. $O(k + W/n)$ decreases most
rapidly with increasing $n$ when $W\gg k$, so at least in terms of the
upper bound on the number of examples required per task, learning
small feature sets is an ideal application for bias 
learning. However, the upper bound on the number of tasks does not fare
so well as it scales as $O(W)$. 
\end{enumerate}

\subsubsection{Comparison with Traditional Multiple-Class
Classification} 
A special case of this multi-task framework is one in which the
marginal distribution on the input space $P_{i|X}$ is the same for
each task $i=1,\dots,n$, and all that varies between tasks is the
conditional distribution over the output space $Y$. An example would
be a multi-class problem such as face recognition, in which
$Y=\{1,\dots, n\}$ where $n$ is the number of faces to be recognized
and the marginal distribution on $X$ is simply the ``natural''
distribution over images of those faces. In that case, if for every
example $x_{ij}$ we have---in addition to the sample $y_{ij}$ from the
$i$th task's conditional distribution on $Y$---samples from the
remaining $n-1$ conditional distributions on $Y$, then we can view the
$n$ training sets containing $m$ examples each as one large training
set for the multi-class problem with $mn$ examples altogether. The
bound on $m$ in Theorem \ref{featthm} states that $mn$ should be $O(nk
+ W)$, or proportional to the total number of parameters in the
network, a result we would expect from\footnote{If each example can be
classified with a ``large margin'' then naive parameter counting can
be improved upon \cite{Bar98}.} \cite{haussler92a}.

So when specialized to the traditional multiple-class, single task
framework, Theorem \ref{featthm} is consistent with the bounds already
known. However, as we have already argued, problems such as face
recognition are not really single-task, multiple-class problems. They
are more appropriately viewed as a (potentially infinite) collection
of distinct binary classification problems. In that case, the goal of
bias learning is not to find a single $n$-output network that can
classify some subset of $n$ faces well. It is to learn a set of
features that can reliably be used as a fixed preprocessing for
distinguishing any single face from other faces. This is the new thing
provided by Theorem \ref{featthm}: it tells us that provided we have
trained our $n$-output neural network on sufficiently many examples of
{\em sufficiently many tasks}, we can be confident that the common
feature map learnt for those $n$ tasks will be good for learning {\em
any} new, as yet unseen task, provided the new task is drawn from the
same distribution that generated the training tasks. In addition,
learning the new task only requires estimating the $k$ output node
parameters for that task, a vastly easier problem than estimating the
parameters of the entire network, from both a sample and computational
complexity perspective. Also, since we have high confidence that the
learnt features will be good for learning novel tasks drawn from the
same environment, those features are themselves a candidate for
further study to learn more about the nature of the environment. The
same claim could not be made if the features had been learnt on too
small a set of tasks to guarantee generalization to novel tasks, for
then it is likely that the features would implement idiosyncrasies
specific to those tasks, rather than ``invariances'' that apply across
all tasks.

When viewed from a bias (or feature) learning perspective,
rather than a traditional $n$-class classification perspective, the
bound $m$ on the number of examples required of each task takes on a
somewhat different meaning. It tells us that provided $n$ is large
(\ie we are collecting examples of a large number tasks), then we
really only need to collect a few more examples than we would
otherwise have to collect if the feature map was already known
($k + W/n$ examples vs. $k$ examples). So it tells us that the burden
imposed by feature learning can be made negligibly small, at least
when viewed from the perspective of the sampling burden required of
each task. 

\subsection{Learning Multiple Tasks with Boolean Feature Maps}
\label{lowersec}
Ignoring the accuracy and confidence parameters $\ep$ and $\delta$,
Theorem \ref{featthm} shows that the number of
examples required of each task when learning $n$ tasks with a common
neural-network feature map is bounded above by $O(k + W/n)$, where $k$
is the number of features and $W$ is the number of adjustable
parameters in the feature map. Since $O(k)$ examples are required to
learn a single task once the true features are known, this shows that
the upper bound on the number of examples required of each task decays
(in order) to the minimum possible as the number of tasks $n$
increases. This suggests that learning multiple tasks is advantageous,
but to be truly convincing we need to prove a lower bound of the same
form. Proving lower bounds in a real-valued setting ($Y= \R$) is
complicated by the fact that a single example can convey an infinite
amount of information, so one typically has to make extra assumptions,
such as that the targets $y\in Y$ are corrupted by a noise process. Rather
than concern ourselves with such complications, in this section we
restrict our attention to Boolean hypothesis space families (meaning
each hypothesis $h\in \HH^1$ maps to $Y= \{\pm1\}$ and we measure
error by discrete loss $l(h(x), y) = 1$ if $h(x) \neq y$ and $l(h(x),
y) = 0$ otherwise).

We show that the sample complexity for learning $n$ tasks with a
Boolean hypothesis space family $\HH$ is controlled by a ``VC
dimension'' type parameter $d_\HH(n)$ (that is, we give nearly
matching upper and lower bounds involving $d_\HH(n)$). We then derive
bounds on $d_\HH(n)$ for the hypothesis space family considered in the
previous section with the Lipschitz sigmoid function $\sigma$ replaced
by a hard threshold (linear threshold networks). 

As well as the bound on the number of examples required per task for
good generalization across those tasks, Theorem \ref{featthm} also
shows that features performing well on $O(W)$ {\em tasks} will
generalize well to novel tasks, where $W$ is the number of parameters
in the feature map.  Given that for many feature learning problems $W$
is likely to be quite large (recall Note \ref{note4} in Section
\ref{sec:discussion}), it would be useful to know that $O(W)$ tasks
are in fact {\em necessary} without further restrictions on the
environmental distributions $Q$ generating the tasks. Unfortunately,
we have not yet been able to show such a lower bound. 

There is some empirical evidence suggesting that in practice the upper
bound on the number of tasks may be very weak. For example, in \citeA{nips_97} we reported
experiments in which a set of neural network features learnt on a
subset of only 400 Japanese characters turned out to be good enough
for classifying some 2600 unseen characters, even though the features
contained several hundred thousand parameters. Similar results may be
found in \citeA{edelman96a} and in the experiments reported in
\citeA{thrun96a} and \citeA[chapter 8]{thrun97a}. While this gap between
experiment and theory may be just another example of the looseness
inherent in general bounds, it may also be that the analysis can be
tightened. In particular, the bound on the number of tasks is insensitive to
the size of the class of output functions (the class $\G$ in Section
\ref{sec:featlearn}),  which may be where the looseness has arisen. 

\subsubsection{Upper and Lower Bounds for Learning $\mathbold{n}$
Tasks with Boolean Hypothesis Space Families}

First we recall some concepts from the theory of Boolean function
learning.  Let $\H$ be a class of Boolean functions on $X$ and
$x=(x_1,\dots, x_m)\in X^m$. $\H_{|x}$\glossary{$\H_{|x}$}{$\H$
restricted to vector $x$} is the set
of all binary vectors obtainable by applying functions in $\H$ to $x$:
$$
\H_{|x} := \{(h(x_1), \dots, h(x_m))\colon h\in \H\}. 
$$
Clearly $|\H_{|x}| \leq 2^m$. If $|\H_{|x}| = 2^m$ we say $\H$ {\em
shatters} $x$.  The {\em growth function} of $\H$ is defined by
$$
\Pi_\H(m) := \max_{x\in X^m} \left|\H_{|x}\right|.\glossary{$\Pi_\H(m)$}{Growth function of $\H$}
$$
The {\em Vapnik-Chervonenkis dimension} $\VCdim(\H)$ is the size of
the largest set shattered by $\H$:
$$
\VCdim(\H) := \max \{m:\Pi_\H(m) = 2^m\}. \glossary{$\VCdim(\H)$}{Vapnik-Chervonenkis dimension of $\H$}
$$
An important result in the theory of learning Boolean functions is
Sauer's Lemma \cite{sauer72}, of which we will also make use. 
\begin{lem}[Sauer's Lemma]
\label{lem:sauer}
For a Boolean function class $\H$ with
$\VCdim(\H) = d$, 
$$
\Pi_\H(m) \leq \sum_{i=0}^d \binom{m}{i} \leq \(\frac{em}{d}\)^d,
$$
for all positive integers $m$. 
\end{lem}

We now generalize these concepts to learning $n$ tasks with a Boolean
hypothesis space family. 

\begin{defn}
Let $\HH$ be a Boolean hypothesis space family. Denote the $n\times
m$ matrices over the input space $X$ by $\Xnm$. For each $\x\in\Xnm$
and $\H\in\HH$, define $\H_{|\x}$ to be the set of (binary) matrices,
$$
\H_{|\x} := \left\{
\[\begin{array}{ccc}
h_1(x_{11}) & \cdots & h_1(x_{1m}) \\
\vdots & \ddots & \vdots\\ 
h_n(x_{n1}) & \cdots & h_n(x_{nm})
\end{array}\]\colon h_1,\dots,h_n\in\H
\right\}.\glossary{$\H_{|\x}$}{$\H$ restricted to matrix $\x$}
$$
Define 
$$
\HH_{|\x} := \bigcup_{\H\in\HH}\H_{|\x}.\glossary{$\HH_{|\x}$}{$\HH$ restricted to matrix $\x$}
$$
Now for each $n>0,m>0$, define $\Pi_\HH(n,m)$  by 
$$
\Pi_\HH(n,m) := \max_{\x\in\Xnm} \left|\HH_{|\x}\right|.\glossary{$\Pi_\HH(n,m)$}{Growth function of $\HH$}
$$
Note that $\Pi_\HH(n,m) \leq 2^{nm}$. If $\left|\HH_{|\x}\right| =
2^{nm}$ we say $\HH$ {\bf shatters} the matrix $\x$.  For
each $n>0$ let
$$
d_\HH(n) := \max\{m\colon \Pi_\HH(n,m) = 2^{nm}\}.\glossary{$d_\HH(n)$}{Dimension function of $\HH$}
$$
Define
\begin{align*} 
\dov(\HH) :&= \VCdim(\HH^1) \quad \text{and} \\
\dun(\HH) :&= \max_{\H\in\HH} \VCdim(\H).\glossary{$\dov(\HH)$}{Upper dimension function of $\HH$}
\glossary{$\dun(\HH)$}{Lower dimension function of $\HH$}
\end{align*}
\end{defn}

\begin{lem}
\label{buggeroff}
\begin{align*} 
\dov(\HH) &\geq \dun(\HH) \\
d_\HH(n) &\geq \max\left\{\left\lfloor\frac{\dov(\HH)}{n}\right\rfloor, \dun(\HH)\right\} \geq
\frac12\(\left\lfloor\frac{\dov(\HH)}{n}\right\rfloor + \dun(\HH)\)
\end{align*}
\end{lem} 
\begin{proof} 
The first inequality is trivial from the definitions. To get the
second term in the maximum in the second inequality, choose an
$\H\in\HH$ with $\VCdim(\H) = \dun(\HH)$ and construct a matrix
$\x\in\Xnm$ whose rows are of length $\dun(\HH)$ and are shattered by
$\H$. Then clearly $\HH$ shatters $\x$. For the first term in the
maximum take a sequence $x= (x_1,\dots, x_{\dov(\HH)})$ shattered by
$\HH^1$ (the hypothesis space consisting of the union over all
hypothesis spaces from $\HH$), and distribute its elements equally
among the rows of $\x$ (throw away any leftovers). The set of matrices
$$
\left\{
\[\begin{array}{ccc}
h(x_{11}) & \cdots & h(x_{1m}) \\
\vdots & \ddots & \vdots\\ 
h(x_{n1}) & \cdots & h(x_{nm})
\end{array}\]\colon h\in \HH^1
\right\}.
$$
where $m = \lfloor \dov(\HH)/n \rfloor$
is a subset of $\HH_{|\x}$ and has size $2^{nm}$. 
\end{proof}

\begin{lem}
\label{Sauer}
$$
\Pi_\HH(n,m) \leq \[\frac{em}{d_\HH(n)}\]^{nd_\HH(n)}
$$
\end{lem}
\begin{proof}
Observe that for each $n$, $\Pi_\HH(n,m) = \Pi_\H(nm)$ where $\H$ is the collection
of all Boolean functions on sequences $x_1,\dots,x_{nm}$  obtained by first choosing $n$ 
functions $h_1,\dots,h_n$ from some $\H\in\HH$, and then applying
$h_1$ to the first $m$ examples, $h_2$ to the second $m$ examples and
so on. By the definition of $d_\HH(n)$, $\VCdim(\H) = n d_\HH(n)$, 
hence the result follows from Lemma \ref{lem:sauer} applied to $\H$. 
\end{proof}

If one follows the proof of Theorem \ref{ntaskthm} (in particular the
proof of Theorem \ref{fundthm} in Appendix \ref{biaslearnproofsec})
then it is clear that for all $\epsilon > 0$, $\C(\HH^n_l, \ep)$ may be replaced by
$\Pi_\HH(n,2m)$ in the Boolean case. Making this replacement in
Theorem \ref{fundthm}, and using the choices of $\alpha, \nu$ from the 
discussion following Theorem \ref{genthm}, we obtain the following bound on the
probability of large deviation between empirical and true performance
in this Boolean setting. 

\begin{thm}
\label{newboolntaskthm}
Let $\Pb = (P_1,\dots,P_n)$ be $n$ probability distributions on
$X\times \{\pm1\}$ and let $\z$ be an $(n,m)$-sample generated by sampling
$m$ times from $X\times \{\pm1\}$ according to each $P_i$. 
Let $\HH=\{\H\}$ be any permissible Boolean hypothesis space family. 
For all $0<\epsilon\leq 1$, 
\begin{equation}
\label{boolfundeqn}
\Pr\left\{\z\colon \exists \h\in\HH^n \colon 
\er_\scPb(\h) \geq  \erh_\z(\h) + \ep \right\} 
\leq 4 \Pi_\HH(n,2m) \exp(-\epsilon^2 n m/64).
\end{equation}
\end{thm}

\begin{corr}
\label{boolntaskthm}
Under the conditions of Theorem \ref{newboolntaskthm}, 
if the number of examples $m$ of each task satisfies
\begin{equation}
\label{newnmbound}
m \geq \frac{88}{\ep^2}\[2d_\HH(n) \log\frac{22}{\ep} + \frac1n\log\frac4\delta\]
\end{equation}
then with probability at least $1-\delta$ (over the choice of 
$\z$), any $\h\in\HH^n$ will satisfy
\begin{equation}
\label{blipp1}
\er_\scPb(\h) \leq \erh_\z(\h) + \ep
\end{equation}
\end{corr}

\begin{proof}
Applying Theorem \ref{newboolntaskthm}, we require
$$
4 \Pi_\HH(n,2m) \exp(-\epsilon^2 n m/64) \leq \delta,
$$
which is satisfied if 
\begin{equation}
\label{eq:bb}
m \geq \frac{64}{\epsilon^2}\[d_\HH(n) \log\frac{2em}{d_\HH(n)} + 
	\frac1n\log \frac{4}{\delta}\], 
\end{equation}
where we have used Lemma \ref{Sauer}. Now, for all $a\geq 1$, if 
$$
m = \(1 + \frac1e\) a \log \(1 + \frac1e\) a, 
$$
then $m \geq a \log m$. So setting $a = 64 d_\HH(n)/\ep^2$,
\eqref{eq:bb} is satisfied if  
$$
m \geq \frac{88}{\ep^2}\[2 d_\HH(n) \log \frac{22}{\ep} +
\frac1n\log\frac4\delta\].
$$
\end{proof}


Corollary \ref{boolntaskthm} shows that any algorithm learning $n$ tasks
using the hypothesis space family $\HH$ requires no more than
\begin{equation}
\label{boolmbound}
m = O\(\frac1{\ep^2}\[d_\HH(n)\log\frac1\ep + \frac1n\log\frac1\delta\]\)
\end{equation}
examples of each task to ensure that with high probability the average
true error of any $n$ hypotheses it selects from $\HH^n$ is within
$\ep$ of their average empirical error on the sample $\z$. We now give
a theorem showing that if the learning algorithm is required to
produce $n$ hypotheses whose average true error is within $\ep$ of the
{\em best possible error} (achievable using $\HH^n$) for an arbitrary
sequence of distributions $P_1,\dots, P_n$, then within a
$\log\frac1\ep$ factor the number of examples in equation
\eqref{boolmbound} is also necessary.

For any sequence $\Pb = (P_1,\dots,P_n)$ of $n$ probability
distributions on $X\times\{\pm1\}$, define
$\opt_\scPb(\HH^n)$\glossary{$\opt_\scPb(\HH^n)$}{Optimal performance
of $\HH^n$ on $\Pb$} by
$$
\opt_\scPb(\HH^n) := \inf_{\h\in\HH^n} \er_\scPb(\h).
$$

\begin{thm}
\label{boollowerbound}
Let $\HH$ be a Boolean hypothesis space family such that $\HH^1$
contains at least two functions. For each
$n=1,2,\dots,$ let $\A_n$ be any learning algorithm taking as input
$(n,m)$-samples $\z\in (X\times\{\pm1\})^{(n,m)}$ and producing as
output $n$ hypotheses $\h=(h_1,\dots,h_n)\in\HH^n$. For all
$0<\ep<1/64$ and $0<\delta<1/64$, if
$$
m < \frac1{\ep^2} \[\frac{d_\HH(n)}{616} + 
(1-\ep^2)\frac1n\log\(\frac1{8\delta(1-2\delta)}\)\right]
$$
then there exist distributions $\Pb=(P_1,\dots, P_n)$ such that
with probability at least $\delta$ (over the random choice of $\z$), 
$$
\er_\scPb(\A_n(\z)) > \opt_\scPb(\HH^n) + \ep
$$
\end{thm}
\begin{proof}
See Appendix \ref{lowerproof}
\end{proof}

\subsubsection{Linear Threshold Networks}
Theorems \ref{boolntaskthm} and \ref{boollowerbound} show that within
constants and a $\log(1/\ep)$ factor, the sample complexity of
learning $n$ tasks using the Boolean hypothesis space family $\HH$ is
controlled by the complexity parameter $d_\HH(n)$. In this section we
derive bounds on $d_\HH(n)$ for hypothesis space families constructed
as thresholded linear combinations of Boolean feature
maps. Specifically, we assume $\HH$ is of the form given by
\eqref{nnetfamily}, \eqref{hysp}, \eqref{hiddennode} and
\eqref{featurenode}, where now the squashing function $\sigma$ is
replaced with a hard threshold:
$$
\sigma(x) := \begin{cases} 1 \quad \text{if $x \geq 0$}, \\
			  -1 \quad \text{otherwise},
	    \end{cases}
$$ 
and we don't restrict the range of the feature and output layer
weights. Note that in this case the proof of Theorem \ref{featthm}
does not carry through because the constants $\kappa, \kappa'$ in
Theorem \ref{capthm} depend on the Lipschitz bound on $\sigma$. 

\begin{thm}
\label{upperlinthresh}
Let $\HH$ be a hypothesis space family of the form given in
\eqref{nnetfamily}, \eqref{hysp}, \eqref{hiddennode} and
\eqref{featurenode}, with a hard threshold sigmoid function
$\sigma$. Recall that the parameters $d$, $l$ and $k$ are the input
dimension, number of hidden nodes in the feature map and number of
features (output nodes in the feature map) respectively. Let $W :=
l(d+1) + k(l+1)$ (the number of adjustable parameters in the feature
map). Then,
$$
d_\HH(n) \leq 2\(\frac{W}{n} + k + 1\)\log_2\(2e(k+l+1)\).
$$
\end{thm}
\begin{proof}
\sloppy
Recall that for each $w\in\R^W$, $\Phi_w\colon \R^d\to \R^k$ denotes the
feature map with parameters $w$. 
For each $\x\in\Xnm$, let $\Phi_{w|\x}$ denote the matrix
$$
\[\begin{array}{ccc}
\Phi_w(x_{11}) & \cdots & \Phi_w(x_{1m}) \\
\vdots & \ddots & \vdots\\ 
\Phi_w(x_{n1}) & \cdots & \Phi_w(x_{nm})
\end{array}\].
$$
Note that $\HH_{|\x}$ is the set of all binary $n\times m$ matrices obtainable by
composing thresholded linear functions with the elements of
$\Phi_{w|\x}$, with the restriction that the same function must be
applied to each element in a row (but the functions may differ
between rows). With a slight abuse of notation, define
$$
\Pi_\Phi(n,m) := \max_{\x\in\Xnm} \left|\left\{\Phi_{w|\x}\colon
w\in\R^W\right\}\right|.
$$
Fix $\x\in\Xnm$. By Sauer's Lemma, each node in the first hidden layer
of the feature map computes at most $\(emn/(d+1)\)^{d+1}$ functions on
the $nm$ input vectors in $\x$. Thus, there can be at most
$\(emn/(d+1)\)^{l(d+1)}$ distinct functions from the input to the
output of the first hidden layer on the $nm$ points in $\x$. Fixing
the first hidden layer parameters, each node in the second layer of
the feature map computes at most $\(emn/(l+1)\)^{l+1}$ functions on
the image of $\x$ produced at the output of the first hidden layer. 
Thus the second hidden layer computes no more than
$\(emn/(l+1)\)^{k(l+1)}$ functions on the output of the first hidden
layer on the $nm$ points in $\x$. So, in total, 
$$
\Pi_\Phi(n,m) \leq \(\frac{emn}{d+1}\)^{l(d+1)}
\(\frac{emn}{l+1}\)^{k(l+1)}. 
$$
Now, for each possible matrix $\Phi_{w|\x}$, the number of functions
computable on each row of $\Phi_{w|\x}$ by a thresholded linear
combination of the output of the feature map is at most
$\(em/(k+1)\)^{k+1}$. Hence, the number of binary sign assignments
obtainable by applying  linear threshold functions to all the rows
is at most $\(em/(k+1)\)^{n(k+1)}$. Thus, 
$$
\Pi_\HH(n,m) \leq \(\frac{emn}{d+1}\)^{l(d+1)}
\(\frac{emn}{l+1}\)^{k(l+1)} \(\frac{emn}{n(k+1)}\)^{n(k+1)}.
$$
$f(x) := x\log x$ is a convex function, hence 
for all $a,b,c>0$, 
\begin{align*}
f\(\frac{ka + lb + c}{k + l + 1}\) &\leq \frac1{k+l+1}\(kf(a) + lf(b) +
f(c)\) \\
\Rightarrow\quad \(\frac{k+l+1}{ka + lb + c}\)^{ka + lb + c} &\geq
\(\frac1a\)^{ka} \(\frac1b\)^{lb}\(\frac1c\)^c. 
\end{align*} 
Substituting $a = l+1$, $b = d+1$ and $c = n(k+1)$ shows that 
\begin{equation}
\label{growth}
\Pi_\HH(n,m) \leq \(\frac{emn(k+l+1)}{W + n(k+1)}\)^{W + n(k+1)}.
\end{equation}
Hence, if
\begin{equation}
\label{t}
m > \(\frac{W}{n} + k + 1\) \log_2 \(\frac{emn(k+l+1)}{W + n(k+1)}\) 
\end{equation}
then $\Pi_\HH(n,m) < 2^{nm}$ and so by definition $d_\HH(n) \leq m$. 
For all $a>1$, observe that $x > a\log_2 x$ if $x = 2a\log_2
2a$. Setting $x = emn(k+l+1)/(W + n(k+1))$ and $a = e(k+l+1)$ shows
that \eqref{t} is satisfied if $m = 2(W/n + k + 1)\log_2(2e(k+l+1))$. 
\end{proof}

\begin{thm}
\label{lowerlinthresh}
Let $\HH$ be as in Theorem \ref{upperlinthresh} with the following
extra restrictions: $d \geq 3$, $l \geq k$ and $k\leq d$. Then 
$$
d_\HH(n) \geq \frac12\(\left\lfloor\frac{W}{2n}\right\rfloor + k + 1\) 
$$
\end{thm}
\begin{proof} 
We bound $\dov(\HH)$ and $\dun(\HH)$ and then apply Lemma
\ref{buggeroff}. In the present setting $\HH^1$ contains all
three-layer linear-threshold networks with $d$ input nodes, $l$ hidden
nodes in the first hidden layer, $k$ hidden nodes in the second hidden
layer and one output node. From Theorem 13 in \citeA{bartlett93}, we
have 
$$
\VCdim(\HH^1) \geq dl + \frac{l(k-1)}{2} + 1,
$$
which under the restrictions stated above is greater than
$W/2$. Hence $\dov(\HH) \geq W/2$. 

As $k\leq d$ and $l\geq k$ we can choose a feature weight assignment
so that the feature map is the identity on $k$ components of the input
vector and insensitive to the setting of the reminaing $d-k$
components. Hence we can generate $k+1$ points in $X$
whose image under the feature map is shattered by the linear threshold
output node, and so $\dun(\HH) = k+1$. 
\end{proof}

Combining Theorem \ref{upperlinthresh} with Corrolary \ref{boolntaskthm}
shows that 
$$
m \geq O\(\frac1{\ep^2} \[\(\frac{W}{n} + k + 1\)\log\frac1\ep + \frac1n\log\frac1\delta\]\) 
$$
examples of each task suffice when learning $n$ tasks using a linear
threshold hypothesis space family, while combining Theorem
\ref{lowerlinthresh} with Theorem \ref{boollowerbound} shows that if 
$$
m \leq \Omega\(\frac1{\ep^2} \[\(\frac{W}{n} + k + 1\) + \frac1n\log\frac1\delta\]\)
$$
then any learning algorithm will fail on some set of $n$ tasks. 

\section{Conclusion}
\label{conclusion}
The problem of inductive bias is one that has broad significance in
machine learning. In this paper we have introduced a formal model of
inductive bias learning that applies when the learner is able to
sample from multiple related tasks.  We proved that provided certain
covering numbers computed from the set of all hypothesis spaces
available to the bias learner are finite, any hypothesis space that
contains good solutions to sufficiently many training tasks is likely
to contain good solutions to novel tasks drawn from the same
environment. 

In the specific case of learning a set of features, we showed that the
number of examples $m$ required of each task in an $n$-task training
set obeys $m = O(k + W/n)$, where $k$ is the number of features and
$W$ is a measure of the complexity of the feature class. We showed
that this bound is essentially tight for Boolean feature maps
constructed from linear threshold networks. In addition, we proved
that the number of tasks required to ensure good performance from the
features on novel tasks is no more than $O(W)$. We also showed how a
good set of features may be found by gradient descent. 

The model of this paper represents a first step towards a formal model
of hierarchical approaches to learning. By modelling a learner's
uncertainty concerning its environment in probabilistic terms, we have
shown how learning can occur simultaneously at both the base
level---learn the tasks at hand---and at the meta-level---learn bias
that can be transferred to novel tasks. From a technical perspective,
it is the assumption that tasks are distributed probabilstically that
allows the performance guarantees to be proved. From a practical
perspective, there are many problem domains that can be viewed as
probabilistically distributed sets of related tasks. For example,
speech recognition may be decomposed along many different axes: words,
speakers, accents, etc. Face recognition represents a potentially
infinite domain of related tasks. Medical diagnosis and prognosis
problems using the same pathology tests are yet another example. All
of these domains should benefit from being tackled with a bias
learning approach.

Natural avenues for further enquiry include: 
\begin{description}
\item[$\bullet$ Alternative constructions for $\mathbold{\HH}$.] Although widely
applicable, the specific example on feature learning via gradient
descent represents just one possible way of generating and searching
the hypothesis space family $\HH$. It would be interesting to
investigate alternative methods, including decision tree approaches,
approaches from Inductive Logic Programming \cite{khan98}, and whether 
more general learning techniques such as boosting can be applied in a
bias learning setting. 
\item[$\bullet$ Algorithms for automatically determining the hypothesis space
family $\mathbold{\HH}$.] In our model the structure of $\HH$ is fixed {\em
apriori} and represents the {\em hyper-bias} of the bias learner. It
would be interesting to see to what extent this structure can also be
learnt.
\item[$\bullet$ Algorithms for automatically determining task
relatedness.] In ordinary learning there is usually little doubt
whether an individual {\em example} belongs to the same learning task
or not. The analogous question in bias learning is whether an
individual learning task belongs to a given set of related tasks, which 
in contrast to ordinary learning, does not always have such a
clear-cut answer. For most of the examples we have discussed here, such 
as speech and face recognition, the task-relatedness is not in
question, but in other cases such as medical problems it is not so
clear. Grouping too large a subset of tasks together as related tasks
could clearly have a detrimental impact on bias-learning or multi-task 
learning, and there is emprical evidence to support this
\cite{caruana97a}. Thus, algorithms for automatically determining
task-relatedness are a potentially useful avenue for further
research. In this context, see \citeA{silver96,thrun96b}. Note that the 
question of task relatedness is clearly only meaningful {\em relative} 
to a particular hypothesis space family $\HH$ (for example, all
possible collections of tasks are related if $\HH$ contains every
possible hypothesis space). 
\item[$\bullet$ Extended hierarchies.] For an extension of our two-level
approach to arbitrarily deep hierarchies, see \citeA{langford99}. An
interesting further question is to what extent the hierarchy can be
inferred from data. This is somewhat related to the question of automatic
induction of structure in graphical models.
\end{description}

\subsection*{Acknowledgements} This work was supported at various
times by an Australian Postgraduate Award, a Shell Australia
Postgraduate Fellowship, U.K Engineering and Physical Sciences
Research Council grants K70366 and K70373, and an Australian
Postdoctoral Fellowship. Along the way, many people have contributed
helpful comments and suggestions for improvement including Martin
Anthony, Peter Bartlett, Rich Caruana, John Langford, Stuart Russell,
John Shawe-Taylor, Sebastian Thrun and several anonymous referees.

\appendix
\section{Uniform Convergence Results}
\label{biaslearnproofsec}
Theorem \ref{biaslearnthm} provides a bound (uniform over all
$\H\in\HH$) on the probability of large deviation between $\er_Q(\H)$
and $\erh_\z(\H)$. To obtain a more general result, we follow
\citeA{haussler92a} and introduce the following parameterized class of
metrics on $\R^+$:
$$
\d{x}{y} := \frac{|x - y|}{x + y + \nu},\glossary{$d_\nu$}{Metric on $\R^+$}
$$
where $\nu > 0$. Our main theorem will be a uniform bound on the
probability of large values of $\d{\er_Q(\H)}{\er_\z(\H)}$, rather
than $|\er_Q(\H) - \erh_\z(\H)|$. Theorem \ref{biaslearnthm} will
then follow as a corollary, as will better bounds for the realizable
case $\erh_\z(\H) = 0$ (Appendix \ref{realisable}).
\begin{lem}
The following three properties of $d_\nu$ are easily established:
\begin{enumerate}
\item For all $r,s \geq 0$, $0\leq\d{r}{s} \leq 1$
\item For all $0\leq r\leq s \leq t$, $\d{r}{s}\leq \d{r}{t}$ and 
$\d{s}{t}\leq \d{r}{t}$. 
\item For $0\leq r,s\leq 1$, $\frac{|r-s|}{\nu + 2} \leq \d{r}{s} 
\leq \frac{|r-s|}{\nu}$
\end{enumerate}
\end{lem}

For ease of exposition we have up until now been dealing explicitly
with hypothesis spaces $\H$ containing functions $h\colon X\to Y$, and
then constructing loss functions $h_l$ mapping $X\times Y\to[0,1]$ by
$h_l(x,y) := l(h(x),y)$ for some loss function $l\colon Y\times Y\to
[0,1]$. However, in general we can view $h_l$ just as a function from
an abstract set $Z$ ($X\times Y$) to $[0,1]$ and ignore its particular
construction in terms of the loss function $l$. So for the remainder
of this section, unless otherwise stated, all hypothesis spaces $\H$
will be sets of functions mapping $Z$ to $[0,1]$. 
It will also be considerably more convenient to transpose our notation
for $(n,m)$-samples, writing the $n$ training sets as columns instead
of rows: 
$$
\z = 
\begin{matrix}
z_{11} & \hdots & z_{1n} \\
\vdots & \ddots & \vdots \\
z_{m1} & \hdots & z_{mn} 
\end{matrix}
$$
where each $z_{ij}\in Z$. Recalling the definition of $\Znm$ (Equation
\ref{Aeqn} and prior discussion), with this transposition $\z$ lives
in $\Zmn$.  The following definition now generalizes quantities like
$\erh_\z(\H)$, $\er_\scPb(\H)$ and so on to this new setting.
\begin{defn}
\label{yuck}
\em Let $\H_1,\dots,\H_n$ be $n$ sets of functions mapping $Z$ into $[0,1]$.
For any $h_1\in\H_1,\dots,h_n\in\H_n$, let 
$h_1\oplus\dots\oplus h_n$\glossary{$h_1\oplus\dots\oplus h_n$}{Average of $h_1$, \dots, $h_n$} or simply $\hv$ denote the map 
$$
\hv(\zv) = 1/n\sum_{i=1}^n h_i(z_i)
$$ 
for all $\zv=(z_1,\dots,z_n)\in Z^n$. Let
$\H_1\oplus\dots\oplus\H_n$\glossary{$\H_1\oplus\dots\oplus\H_n$}{Set
of $h_1\oplus\dots\oplus h_n$}
denote the set of all such functions.  Given
$\hv\in\H_1\oplus\dots\oplus\H_n$ and $m$ elements of $\Zn$,
$(\zv_1,\dots,\zv_m)$ (or equivalently an element $\z$ of $\Zmn$ by
writing the $\zv_i$ as rows), define 
$$
\erh_\z(\hv) := \frac1m\sum_{i=1}^m\hv(\zv_i)
$$
(recall equation \eqref{emploss}).
Similarly, for any product probability measure $\Pb =
P_1\times\dots\times P_n$ on $\Zn$, define 
$$
\er_\scPb(\hv) := \int_{Z^n} \hv(\zv)\, d\Pb(\zv)
$$
(recall equation \eqref{expnerr}). For {\em any} $\hv,\hv'\colon \Zn\to
[0,1]$ (not necessarily of the form $h_1\oplus\dots\oplus h_n$), define
$$
d_\scPb(\h,\h') := \int_{Z^n}
|\h(\zv) - \h'(\zv)| \, d\Pb(\zv)
$$
(recall equation \eqref{dp}). For any class of functions $\H$ mapping $\Zn$
to $[0,1]$, define 
$$
\C\(\ep,\H\) := \sup_{\scPb}\N\(\ep, \H, d_\scPb\)
$$
where the supremum is over all product probability measures on $\Zn$
and $\N\(\ep, \H, d_\scPb\)$ is the size of the smallest $\ep$-cover
of $\H$ under $d_\scPb$ (recall Definition \ref{covdef}).
\end{defn}

\sloppy
The following theorem is the main result from which the rest of the
uniform convergence results in this paper are derived. 
\begin{thm}
\label{fundthm}
Let $\H\subseteq\H_1\oplus\dots\oplus\H_n$ be a permissible class of functions
mapping $\Zn$ into $[0,1]$. Let $\z\in\Zmn$ be generated by
$m\geq 2/(\alpha^2\nu)$ independent trials
from $\Zn$ according to some product probability measure
$\Pb=P_1\times\dots\times P_n$. For all $\nu > 0$,
$0<\alpha<1$, 
\begin{multline}
\label{fundeqn}
\Pr\left\{\z\in\Zmn\colon \sup_\H 
\d{\erh_\z(\hv)}{\er_\scPb(\hv)} > \alpha \right\} \\ \leq
4 \C(\alpha\nu/8,\H) \exp(-\alpha^2 \nu n m/8).
\end{multline}
\end{thm}
\noindent The following immediate corollary will also be of use later.
\begin{cor}
\label{fundcor}
Under the same conditions as Theorem \ref{fundthm}, if 
\begin{equation}
\label{fundmeq}
m \geq \max\left\{\frac{8}{\alpha^2\nu n}
\log\frac{4\C\(\frac{\alpha\nu}{8},\H\)}{\delta},
\frac2{\alpha^2\nu}\right\},
\end{equation}
then 
\begin{equation}
\label{corprob}
\Pr\left\{\z\in\Zmn\colon \sup_\H 
\d{\erh_\z(\hv)}{\er_\scPb(\hv)} > \alpha \right\} \leq \delta
\end{equation}
\end{cor}

\subsection{Proof of Theorem \ref{fundthm}}
The proof is via a double symmetrization argument of the kind 
given in chapter 2 of \citeA{pollard84a}. I have also borrowed some 
ideas from the proof of Theorem 3 in \citeA{haussler92a}.

\subsubsection{First Symmetrization}
An extra piece of notation: for all $\z\in \Ztmn$, let $\z(1)$ be the
top half of $\z$ and $\z(2)$ be the bottom half, viz:
$$
\z(1) = 
\begin{matrix}
z_{11} & \hdots & z_{1n} \\
\vdots & \ddots & \vdots \\
z_{m1} & \hdots & z_{mn} 
\end{matrix}
\qquad \z(2) =
\begin{matrix}
z_{m+1,1} & \hdots & z_{m+1,n} \\
\vdots & \ddots & \vdots \\
z_{2m,1} & \hdots & z_{2m,n}
\end{matrix}
$$
The following lemma is the first ``symmetrization trick.'' We relate
the probability of large deviation between an empirical estimate of
the loss and the true loss to the probability of large deviation
between two independent empirical estimates of the loss. 
\begin{lem}
\label{empdev}
Let $\H$ be a permissible set of functions from $\Zn$ into $[0,1]$ and
let $P$ be a probability measure on $\Zn$. For all 
$\nu>0, 0<\alpha<1$ and $m\geq\frac{2}{\alpha^2 \nu}$,
\begin{multline}
\label{firstsym}
\Pr\left\{\z\in \Zmn\colon \sup_\H\d{\erh_\z(h)}{\er_P(h)} 
> \alpha\right\} \\
\leq 2 \Pr\left\{\z\in Z^{(2m,n)}\colon  \sup_\H
\d{\erh_{\z(1)}(h)}{\erh_{\z(2)}(h)} > \frac{\alpha}{2}\right\}.
\end{multline}
\end{lem}
\begin{proof}
Note first that permissibility of $\H$
guarantees the measurability of suprema over $\H$ (Lemma \ref{permlem} part
\ref{4}). By the triangle inequality for $d_\nu$, if
$\d{\erh_{\z(1)}(h)}{\er_P(h)} > \alpha$ and 
$\d{\erh_{\z(2)}(h)}{\er_P(h)} < \alpha/2$, then
$\d{\erh_{\z(1)}(h)}{\erh_{\z(2)}(h)} > \alpha/2$. Thus,
\begin{multline}
\label{chebyshev}
\Pr\Bigl\{\z\in\Ztmn\colon\exists h\in\H\colon\d{\erh_{\z(1)}(h)}{\erh_{\z(2)}(h)} > 
\frac{\alpha}{2}\Bigr\} \\
\begin{split}
\geq\Pr\Bigl\{\z\in\Ztmn\colon\exists h\in\H:\d{\erh_{\z(1)}(h)}{\er_P(h)} &>
\alpha\,\,\text{and} \\ 
\d{\erh_{\z(2)}(h)}{\er_P(h)} &< \alpha/2\Bigr\}.
\end{split}
\end{multline}
By Chebyshev's inequality, for any fixed $h$,
\begin{align*}
\Pr\Bigl\{\z\in\Zmn\colon \d{\erh_\z(h)}{\er_P(h)} &< \frac{\alpha}{2}\Bigr\}\\
&\geq \Pr\left\{\z\in\Zmn\colon 
\frac{\left|\erh_\z(h) - \er_P(h)\right|}{\nu} <
\frac\alpha 2\right\} \\
&\geq 1 - \frac{\er_P(h)(1-\er_P(h))}{m\nu\alpha^2/4} \\
& \geq\frac12
\end{align*}
as $m\geq 2/(\alpha^2\nu)$ and $\er_P(h)\leq 1$. Substituting this
last expression into the right hand side of \eqref{chebyshev} gives
the result. 
\end{proof}

\subsubsection{Second Symmetrization}
The second symmetrization trick bounds the probability of large
deviation between two empirical estimates of the loss (i.e. the right
hand side of \eqref{firstsym}) by computing the probability of large
deviation when elements are randomly permuted between the first and
second sample. The following definition introduces the appropriate
permutation group for this purpose.
\begin{defn}
\label{dmusig}
\em For all integers $m,n\geq 1$, let $\Gtmn$\glossary{$\Gtmn$}{Permutations on integer pairs} denote the set of all
permutations $\sigma$ of the sequence of pairs of integers
$\left\{(1,1),\dots,(1,n),\dots,(2m,1),\dots,(2m,n)\right\}$ such that
for all $i$, $1\leq i\leq m$, either $\sigma(i,j) = (m+i,j)$ and
$\sigma(m+i,j) = (i,j)$ or $\sigma(i,j) = (i,j)$ and
$\sigma(m+i,j) = (m+i,j)$.
\end{defn}
For any $\z\in\Ztmn$ and any $\sigma\in\Gtmn$, let 
$$
\z_\sigma :=
\begin{matrix}
z_{\sigma(1,1)} & \hdots & z_{\sigma(1,n)} \\
\vdots & \ddots & \vdots \\
z_{\sigma(2m,1)} & \hdots & z_{\sigma(2m,n)}.
\end{matrix}\glossary{$\z_\sigma$}{Permuted $\z$}
$$
\begin{lem}
\label{intlem}
Let $\H = \H_1\oplus\dots\oplus\H_n$ be a permissible set of functions
mapping $\Zn$ into $[0,1]$ (as in the statement of Theorem
\ref{fundthm}).  Fix $\z\in\Ztmn$ and let
$\Hhat:= \{\fv^1,\dots,\fv^M\}$ be an $\alpha\nu/8$-cover for
$\(\H,d_\z\)$, where $d_\z(\hv,\hv') := \frac1{2m}\sum_{i=1}^{2m}
|\hv(\zv_i) - \hv'(\zv_i)|$\glossary{$d_\z(\hv,\hv')$}{Empirical $l_1$ metric on functions $\hv$} where the $\zv_i$ are the rows of $\z$. Then,
\begin{multline}
\label{lb1}
\Pr\left\{\sigma\in \Gtmn\colon  \sup_\H
\d{\erh_\zsw(\hv)}{\erh_\zst(\hv)} > \frac{\alpha}{2}\right\} \\
\leq \sum_{i=1}^M \Pr\left\{\sigma\in \Gtmn\colon
\d{\erh_\zsw(\fv^i)}{\erh_\zst(\fv^i)} > \frac{\alpha}{4}\right\},
\end{multline}
where each $\sigma\in\Gtmn$ is chosen uniformly at random.
\end{lem}
\begin{proof}
Fix $\sigma\in\Gtmn$ and let $\hv\in\H$ be such that
$\d{\erh_\zsw(\hv)}{\erh_\zst(\hv)} > \alpha/2$ (if there is no such
$\hv$ for any $\sigma$ we are already done). Choose $\fv\in \Hhat$ such that
$d_\z(\hv,\fv) \leq \alpha\nu/8$. Without loss of generality we
can assume $\fv$ is of the form $\fv=f_1\oplus\dots\oplus f_n$. Now,
\begin{align*}
\frac2\nu d_\z(\hv,\fv) &= \frac{\sum_{i=1}^{2m}
	\left|\sum_{j=1}^n h_j(z_{ij}) - f_j(z_{ij})\right|}{\nu m n} \\
&= 	\frac{\sum_{i=1}^{2m}
	\left|\sum_{j=1}^n h_j(\zsij) - f_j(\zsij)\right|}{\nu m n} \\
&\geq
\frac{\left|\sum_{i=1}^m\sum_{j=1}^n\[h_j(\zsij) - f_j(\zsij)\]\right|}
	{\nu m n + \sum_{i=1}^m \sum_{j=1}^n \[h_j(\zsij) + f_j(\zsij)\]} \\
&\qquad
+\frac{\left|\sum_{i=m+1}^{2m}\sum_{j=1}^n\[h_j(\zsij) - f_j(\zsij)\] \right|}
	{\nu m n + \sum_{i=m+1}^{2m}\sum_{j=1}^n \[h_j(\zsij) + f_j(\zsij)\]} \\
&= \d{\erh_\zsw(\hv)}{\erh_\zsw(\fv)} + \d{\erh_\zst(\hv)}{\erh_\zst(\fv)}.
\end{align*}
Hence, by the triangle inequality for $d_\nu$,
\begin{equation}
\label{dnineq}
\begin{split}
\frac2\nu d_\z(\hv,\fv) + &\d{\erh_\zsw(\fv)}{\erh_\zst(\fv)}
\geq \d{\erh_\zsw(\hv)}{\erh_\zsw(\fv)} \\ &+
\d{\erh_\zst(\hv)}{\erh_\zst(\fv)} +
\d{\erh_\zsw(\fv)}{\erh_\zst(\fv)}\\
&\geq \d{\erh_\zsw(\hv)}{\erh_\zst(\hv)}.
\end{split}
\end{equation}
But $\frac{2}{\nu} d_\z(\hv,\fv) \leq \alpha/4$ by construction 
and $\d{\erh_\zsw(\hv)}{\erh_\zst(\hv)} > \alpha/2$ by assumption, so 
\eqref{dnineq} implies 
$\d{\erh_\zsw(\fv)}{\erh_\zst(\fv)} > \alpha/4$. 
Thus, 
\begin{multline*}
\left\{\sigma\in \Gtmn\colon\exists\hv\in\H\colon
\d{\erh_\zsw(\hv)}{\erh_\zst(\hv)} > \frac{\alpha}{2}\right\} \\
\subseteq \left\{\sigma\in \Gtmn\colon \exists\fv\in\Hhat \colon
\d{\erh_\zsw(\fv)}{\erh_\zst(\fv)}) > \frac{\alpha}{4}\right\},
\end{multline*}
which gives \eqref{lb1}.
\end{proof}

Now we bound the probability of each term in the right hand side of
\eqref{lb1}.  
\begin{lem}
\label{lastlem}
Let $\fv:\Zn\to[0,1]$ be any function that can be written in the form 
$\fv = f_1\oplus\dots\oplus f_n$. For any $\z\in\Ztmn$, 
\begin{equation}
\label{uniform}
\Pr\left\{\sigma\in \Gtmn\colon
\d{\erh_\zsw(\fv)}{\erh_\zst(\fv)} > \frac{\alpha}{4}\right\} \leq 
2\exp\(\frac{-\alpha^2\nu m n}{8}\),
\end{equation}
where each $\sigma\in\Gtmn$ is chosen uniformly at random.
\end{lem}
\begin{proof}
For any $\sigma\in\Gtmn$,
\begin{equation}
\label{blippy}
\d{\erh_{\zs(1)}(\fv)}{\erh_{\zs(2)}(\fv)} =
\frac{\left|\sum_{i=1}^m\sum_{j=1}^n \[f_j(\zsij) - f_j(z_{\sigma(m+i,j)})\]\right|}
{\nu m n + \sum_{i=1}^{2m}\sum_{j=1}^n f_j(z_{ij})}.
\end{equation}
To simplify the notation denote $f_j(z_{ij})$ by $\beta_{ij}$.
For each pair $ij$, $1\leq i\leq m$, $1\leq j\leq n$, let 
$Y_{ij}$ be an independent random variable such that 
$Y_{ij} = \beta_{ij} - \beta_{m+i,j}$ with 
probability $1/2$ and $Y_{ij} = \beta_{m+i,j} - \beta_{ij}$ with probability 
$1/2$. From \eqref{blippy},
\begin{align*}
\Pr&\left\{\sigma\in \Gtmn\colon
\d{\erh_\zsw(\fv)}{\erh_\zst(\fv)} > \frac{\alpha}{4}\right\} \\
&= \Pr\left\{\sigma\in \Gtmn\colon
\left|\sum_{i=1}^m\sum_{j=1}^n \[f_j(\zsij) - f_j(z_{\sigma(m+i,j)})\]\right| 
> \frac\alpha{4} \(\nu m n + \sum_{i=1}^{2m}\sum_{j=1}^n \beta_{ij}\)\right\} \\
&= \Pr\left\{
\left|\sum_{i=1}^m\sum_{j=1}^n Y_{ij} \right|
\frac\alpha{4} \(\nu m n + \sum_{i=1}^{2m}\sum_{j=1}^n \beta_{ij}\)\right\}
\end{align*}
For zero-mean independent random variables $Y_1,\dots,Y_k$ with bounded
ranges $a_i\leq Y_i\leq b_i$, Hoeffding's inequality \cite{gabor97a}
is
$$
\Pr\left\{\left|\sum_{i=1}^k Y_i\right| \geq \eta\right\} 
\leq 2\exp\(-\frac{2 \eta^2}{\sum_{i=1}^k
(b_i-a_i)^2}\).  
$$ 
Noting that the range of each $Y_{ij}$ is
$[-|\beta_{ij} - \beta_{i+m,j})|, |\beta_{ij} - \beta_{i+m,j})|]$, we
have
$$
\Pr\left\{
\left|\sum_{i=1}^m\sum_{j=1}^n Y_{ij} \right|
> \frac\alpha{4} \(\nu m n + \sum_{i=1}^{2m}\sum_{j=1}^n \beta_{ij}\)\right\} 
\leq 
2\exp\(
-\frac{\alpha^2 \[\nu m n + \sum_{i=1}^{2m} \sum_{j=1}^n \beta_{ij}\]^2}
{32 \sum_{i=1}^m\sum_{j=1}^n (\beta_{ij} - \beta_{i+m,j})^2}\)
$$
Let $\gamma = \sum_{i=1}^{2m}\sum_{j=1}^n \beta_{ij}$.
As $0\leq \beta_{ij} \leq 1$, $\sum_{i=1}^m
\sum_{j=1}^n (\beta_{ij} - \beta_{m+i j})^2 \leq \gamma$. Hence,
$$
2\exp\(
-\frac{\alpha^2 \[\nu m n + \sum_{i=1}^{2m} \sum_{j=1}^n \beta_{ij}\]^2}
{32 \sum_{i=1}^m\sum_{j=1}^n (\beta_{ij} - \beta_{i+m,j})^2}\)
\leq 2\exp\(-\frac{\alpha^2 (\nu m n + \gamma)^2}{32 \gamma}\).
$$
$(\nu m n + \gamma)^2/\gamma$ is minimized by setting $\gamma = \nu m n$ giving 
a value of $4\nu m n $. Hence
$$
\Pr\left\{\sigma\in \Gtmn\colon
\d{\erh_\zsw(\fv)}{\erh_\zst(\fv)} > \frac{\alpha}{4}\right\} \leq 
2\exp\(\frac{-\alpha^2\nu m n}{8}\),
$$
as required.
\end{proof}
\subsubsection{Putting it Together}
For fixed $\z\in \Ztmn$, Lemmas \ref{intlem} and \ref{lastlem}
give:
\begin{multline*}
\Pr\left\{\sigma\in \Gtmn\colon  \sup_\H
\d{\erh_\zsw(\hv)}{\erh_\zst(\hv)} > \frac{\alpha}{2}\right\}\\
\leq 
2\N\(\alpha\nu/8,\H, d_\z)\) \exp\(-\frac{\alpha^2\nu m n}{8}\).
\end{multline*}
Note that $d_\z$ is simply $d_\scPb$ where $\Pb = (P_1,\dots,P_n)$ and each
$P_i$ is the empirical distribution 
that puts point mass $1/m$ on each $z_{ji}, j=1,\dots,2m$ (recall
Definition \ref{metricdef}). Hence,
\begin{multline*}
\Pr\left\{\sigma\in \Gtmn, \z\in\Ztmn\colon  \sup_\H
\d{\erh_\zsw(\hv)}{\erh_\zst(\hv)} > \frac{\alpha}{2}\right\} \\
\leq 
2\C\(\alpha\nu/8,\H\) \exp\(-\frac{\alpha^2\nu m n}{8}\).
\end{multline*}
Now, for a random choice of $\z$, each $z_{ij}$ in $\z$ is independently
(but not identically) distributed and $\sigma$ only ever swaps
$z_{ij}$ and $z_{i+m,j}$ (so that $\sigma$ swaps a $z_{ij}$ drawn
according to $P_j$ with another component drawn according to the same
distribution). Thus we can integrate out with respect to the choice of
$\sigma$ and write
\begin{multline*}
\Pr\left\{\z\in\Ztmn\colon  \sup_\H
\d{\erh_{\z(1)}(\hv)}{\erh_{\z(2)}(\hv)} > \frac{\alpha}{2}\right\} \\
\leq 2\C\(\alpha\nu/8,\H\) \exp\(-\frac{\alpha^2\nu m n}{8}\).
\end{multline*}
Applying Lemma \ref{empdev} to this expression gives Theorem
\ref{fundthm}. \qed

\subsection{Proof of Theorem \ref{biaslearnthm}}
Another piece of notation is required for the proof. 
For any hypothesis space $\H$ and any probability measures
$\Pb=(P_1,\dots,P_n)$ on $Z$, let
$$
\erh_\scPb(\H) := \frac1n\sum_{i=1}^n \inf_{h\in\H} \er_{P_i}(h).\glossary{$\erh_\scPb(\H)$}{Optimal average error of $\H$ on $\Pb$}
$$
Note that we have used $\erh_\scPb(\H)$ rather than $\er_\scPb(\H)$ to
indicate that $\erh_\scPb(\H)$ is another empirical estimate of
$\er_Q(\H)$. 

With the $(n,m)$-sampling process, in addition to the sample $\z$
there is also generated a sequence of probability measures,
$\Pb=\(\pr{P}{,}{n}\)$ although these are not supplied to the learner.
This notion is used in the following Lemma, where
$\Pr\{(\z,\Pb)\in\Znm\times\P^n\colon A\}$ means ``the probability of
generating a sequence of measures $\Pv$ from the environment $(\P,Q)$
and then an $(n,m)$-sample $\z$ according to $\Pv$ such that A
holds''.
\begin{lem}
\label{firstlem}
If
\begin{equation}
\label{ineq1}
\Pr\left\{(\z,\Pv)\in\Znm\times\P^n\colon \sup_\HH \d{\erh_\z(\H)}{\erh_\scPb(\H)} > 
\frac\alpha2 \right\} \leq \frac\delta2,
\end{equation}
and
\begin{equation}
\label{ineq2}
\Pr\left\{\Pv\in\P^n\colon \sup_\HH \d{\erh_\scPb(\H)}{\er_Q(\H)} 
> \frac\alpha2 \right\} \leq \frac\delta2,
\end{equation}
then
$$
\Pr\left\{\z\in\Znm\colon \sup_\HH 
\d{\erh_\z(\H)}{\er_Q(\H)} > \alpha \right\} \leq \delta.
$$
\end{lem}
\begin{proof}
Follows directly from the triangle inequality for $d_\nu$.
\end{proof}

\noindent We treat the two inequalities in Lemma \ref{firstlem} separately. \\

\subsubsection{Inequality \eqref{ineq1}}
In the following Lemma we replace the supremum over $\H\in\HH$ in
inequality \eqref {ineq1} with a supremum over $\hv \in \HH^n$.
\begin{lem}
\label{firstineq}
\begin{multline}
\label{dunno}
\Pr\left\{(\z,\Pv)\in \Znm\times\P^n\colon\sup_\HH
\d{\erh_\z(\H)}{\erh_\scPb(\H)} > \alpha \right\} \\
\leq
\Pr\left\{(\z,\Pv)\in \Znm\times\P^n\colon\sup_\Hns 
\d{\erh_\z(\hv)}{\er_\scPb(\hv)} >\alpha\right\}
\end{multline}
\end{lem}
\begin{proof}
Suppose that $(\z,\Pv)$ are such that $\sup_\HH \d{\erh_\z(\H)}{\erh_\scPb(\H)} > \alpha$. 
Let $\H$ satisfy this inequality.
Suppose first that $\erh_\z(\H) \leq \erh_\scPb(\H)$.
By the definition of $\erh_\z(\H)$, for all $\ep>0$  there exists $\hv\in\H^n:=\H\oplus\dots\oplus\H$ such
that $\erh_\z(\hv) < \erh_\z(\H) + \ep$.
Hence by property (3) of the $d_\nu$ metric, 
for all $\ep>0$, there exists $\hv\in\H^n$ such that
$\d{\erh_\z(\hv)}{\erh_\z(\H)} < \ep$.
Pick an arbitrary $\hv$ satisfying this inequality. By definition,
$\erh_\scPb(\H) \leq \er_\scPb(\hv)$, and so $\erh_\z(\H) \leq \erh_\scPb(\H) \leq \er_\scPb(\hv)$.
As $\d{\erh_\z(\H)}{\erh_\scPb(\H)} > \alpha$ (by assumption), 
by the compatibility of $d_\nu$ with the ordering on the reals,
$\d{\erh_\z(\H)}{\er_\scPb(\hv)} > \alpha = \alpha+\delta$, say.
By the triangle inequality for $d_\nu$,
$$
\d{\erh_\z(\hv)}{\er_\scPb(\hv)} + 
\d{\erh_\z(\hv)}{\erh_\z(\H)} \geq \d{\erh_\z(\H)}{\er_\scPb(\hv)} = \alpha + \delta.
$$
Thus $\d{\erh_\z(\hv)}{\er_\scPb(\hv)} > \alpha+\delta-\ep$
and for any $\ep>0$ an $\hv$ satisfying this inequality can be found.
Choosing $\ep=\delta$ shows that there exists $\hv\in\H^n$ such that 
$\d{\erh_\z(\hv)}{\er_\scPb(\hv)} > \alpha$.

If instead,  $\erh_\scPb(\H) < \erh_\z(\H)$, then an identical 
argument can be run with the role of $\z$ and $\Pv$ interchanged.
Thus in both cases,
$$
\sup_\HH \d{\erh_\z(\H)}{\erh_\scPb(\H)} > \alpha \\
\Rightarrow
\exists \hv\in \Hns\colon 
\d{\erh_\z(\hv)}{\er_\scPb(\hv)} > \alpha,
$$
which completes the proof of the Lemma.
\end{proof}

By the nature of the $(n,m)$ sampling process,
\begin{multline}
\label{intprob}
\Pr\left\{(\z,\Pv)\in \Znm\times\P^n
\sup_\Hns\colon \d{\erh_\z(\hv)}{\er_\scPb(\hv)} >\alpha\right\} \\
= \int\limits_{\scPb\in\P^n}\!\! 
\Pr\left\{\z\in \Znm\colon \sup_\Hns \d{\erh_\z(\hv)}{\er_\scPb(\hv)}
>\alpha\right\}\,dQ^n(\Pv).
\end{multline} 
Now $\HH^n_l\subseteq K\oplus\dots\oplus K$ where $K:= \{h_l\colon
h\in\H\colon \H\in\HH\}$ and $\HH^n_l$ is permissible by the assumed
permissibility of $\HH$ (Lemma \ref{permlem}, Appendix \ref{permsec}). Hence
$\HH^n_l$ satisfies the conditions of Corollary \ref{fundcor} and so
combining Lemma \ref{firstineq}, Equation \eqref{intprob} and 
substituting $\alpha/2$ for $\alpha$ and $\delta/2$ for $\delta$ in Corollary 
\ref{fundcor} gives the following Lemma on the sample size required
to ensure \eqref{ineq1} holds.
\begin{lem}
\label{ineq1lem}
If
$$
m \geq 
\max\left\{\frac{32}{\alpha^2\nu n} \ln \frac{8\C(\alpha\nu/16,\Hns)}{\delta},
	\frac8{\alpha^2\nu}\right\}
$$
then
$$
\Pr\left\{(\z,\Pv)\in\Znm\times\P^n\colon \sup_\HH \d{\erh_\z(\H)}{\erh_\scPb(\H)} > 
\frac\alpha2 \right\} \leq \frac\delta2.
$$
\end{lem}

\subsubsection{Inequality \eqref{ineq2}}
Note that $\er_\scPb(\H) = \frac1n\sum_{i=1}^n \H^*(P_i)$ and
$\er_Q(\H) = \E_{P\sim Q}\H^*(P)$, i.e the expectation of $\H^*(P)$
where $P$ is distributed according to $Q$. So to bound the left-hand-side of
\eqref{ineq2} we can apply Corollary \ref{fundcor} with $n=1$, $m$
replaced by $n$, $\H$ replaced by $\HH^*$, $\alpha$ and $\delta$
replaced by $\alpha/2$ and $\delta/2$ respectively, $P$ replaced by
$Q$ and $Z$ replaced by $\P$.  Note that $\HH^*$ is permissible
whenever $\HH$ is (Lemma \ref{permlem}). Thus, if
\begin{equation}
\label{ineq2eq}
n \geq \max\left\{\frac{32}{\alpha^2\nu} 
\ln \frac{8\C(\alpha\nu/16,\HH^*)}{\delta}, \frac{8}{\alpha^2\nu}\right\}
\end{equation}
then inequality \eqref{ineq2} is satisfied.

Now, putting together Lemma \ref{firstlem}, Lemma \ref{ineq1lem} and 
Equation \ref{ineq2eq}, we have proved the following more general
version of Theorem \ref{biaslearnthm}.
\begin{thm}
\label{genthm}
Let $\HH$ be a permissible hypothesis space family and let $\z$ be an
$(n,m)$-sample generated from the environment $\(\P,Q\)$. For all
$0<\alpha,\delta<1$ and $\nu>0$, if 
\begin{align*}
n &\geq \max\left\{\frac{32}{\alpha^2\nu} 
\ln \frac{8\C(\alpha\nu/16,\HH^*)}{\delta},
\frac{8}{\alpha^2\nu}\right\} \\
\text{and}\qquad 
m &\geq 
\max\left\{\frac{32}{\alpha^2\nu n} \ln \frac{8\C(\alpha\nu/16,\Hns)}{\delta},
	\frac8{\alpha^2\nu}\right\},
\end{align*}
then 
$$
\Pr\left\{\z\in\Znm\colon\sup_{\HH} \d{\erh_\z(\H)}{\er_Q(\H)} >
\alpha\right\}
\leq \delta
$$
\end{thm}
To get Theorem \ref{biaslearnthm}, observe that $\er_Q(\H) >
\erh_\z(\H) + \ep \Rightarrow \d{\erh_\z(\H)}{\er_Q(\H)} >
\ep/(2+\nu)$. Setting $\alpha = \ep/(2+\nu)$ and maximizing
$\alpha^2\nu$ gives $\nu=2$. Substituting $\alpha=\ep/4$ and $\nu = 2$
into Theorem \ref{genthm} gives Theorem \ref{biaslearnthm}.

\subsection{The Realizable Case}
\label{realisable}
In Theorem \ref{biaslearnthm} the sample complexity for both $m$ and
$n$ scales as $1/\ep^2$. This can be improved to $1/\ep$ if
instead of requiring $\er_Q(\H) \leq \erh_\z(\H) + \ep$, we require only that
$\er_Q(\H) \leq \kappa \erh_\z(\H) + \ep$ for some $\kappa > 1$. 
To see this, observe that $\er_Q(\H) >
\erh_\z(\H)(1+\alpha)/(1-\alpha) + \alpha\nu/(1-\alpha) \Rightarrow
\d{\erh_\z(\H)}{\er_Q(\H)} > \alpha$, so setting 
$\alpha\nu/(1-\alpha) = \ep$ in Theorem \ref{genthm} and treating $\alpha$ as a
constant gives:
\begin{cor}
\label{realcor}
Under the same conditions as Theorem \ref{genthm},
for all $\ep > 0$ and $0<\alpha, \delta < 1$, if
\begin{align*}
n &\geq \max\left\{\frac{32}{\alpha(1-\alpha)\ep} 
\ln \frac{8\C((1-\alpha)\ep/16,\HH^*)}{\delta},
\frac{8}{\alpha(1-\alpha)\ep}\right\} \\
\text{and}\qquad 
m &\geq 
\max\left\{\frac{32}{\alpha(1-\alpha)\ep n} \ln \frac{8\C((1-\alpha)\ep/16,\Hns)}{\delta},
	\frac8{\alpha(1-\alpha)\ep}\right\},
\end{align*}
then 
$$
\Pr\left\{\z\in\Znm\colon\sup_{\HH} \er_Q(\H) \geq \frac{1+\alpha}{1-\alpha}\erh_\z(\H) 
+ \ep\right\}
\leq \delta.
$$
\end{cor}
These bounds are particularly useful if we know that $\erh_\z(\H)=0$,
for then we can set $\alpha=1/2$ (which maximizes $\alpha(1-\alpha)$). 

\section{Proof of Theorem \ref{gencompthm}}
\label{capproof}
Recalling Definition \ref{yuck}, for $\HH$ of the form given in
\eqref{hhdef}, $\HH^n_l$ can be written 
$$
\HH^n_l = \left\{\comp{g_1}{f}\oplus\dots\oplus\comp{g_n}{f}\colon
g_1,\dots,g_n\in{\G_l}\,\text{and}\, f\in\F\right\}.
$$
To write $\HH^n_l$ as a composition of two function classes note
that if for each 
$f\colon X\to V$ we define $\fbar\colon (\XY)^n \to (\VY)^n$ by 
$$
\fbar(x_1,y_1,\dots,x_n,y_n) := (f(x_1),y_1, \dots,f(x_n),y_n)
$$ 
then 
$\comp{g_1}{f}\oplus\dots\oplus\comp{g_n}{f} = 
\comp{g_1\oplus\dots\oplus g_n}{\fbar}$. Thus, setting 
$\G_l^n:= {\G_l}\oplus\dots\oplus {\G_l}$ and $\Fbar:= \{\fbar\colon f\in\F\}$,
\begin{equation}
\label{hhnl}
\HH^n_l = \comp{\G_l^n}{\Fbar}.
\end{equation}
The following two Lemmas will enable us to bound $\C\(\ep,\HH^n_l\)$.
\begin{lem}
\label{litcomplem}
Let $\H\colon \XY \to [0,1]$ be of the form $\H = \comp{{\G_l}}{\F}$ where 
$\XY\xrightarrow{\F}\VY\xrightarrow{{\G_l}}[0,1]$. For all $\ep_1,\ep_2 > 0$,
$$
\C(\ep_1+\ep_2,\H) \leq \C_{{\G_l}}(\ep_1,\F)\,\C(\ep_2,{\G_l}).
$$
\end{lem}
\begin{proof}
Fix a measure $P$ on $\XY$ 
and let $F$ be a minimum size $\ep_1$-cover
for $(\F,d_{[P,{\G_l}]})$. By definition $|F| \leq \C_{{\G_l}}(\ep_1,\F)$. 
For each $f\in F$ let $P_f$ be the measure on $\VY$
defined by $P_f(S) = P(f^{-1}(S))$ for any set $S$ in the $\sigma$-algebra
on $V\times Y$ ($f$ is measurable so $f^{-1}(S)$ is measurable). 
Let $G_f$ be a minimum size
$\ep_2$-cover for $({\G_l},d_{P_f})$. By definition again, $|G_f| \leq
\C(\ep_2,{\G_l})$. 
Let $N:=\{\comp{g}{f}\colon  
f\in F \,{\text{and}}\,
g\in G_f\}$. Note that $|N| \leq
\C_{{\G_l}}(\ep_1,\F) \C(\ep_2,{\G_l})$ so the Lemma will be proved if
$N$ can be shown to be an $\ep_1+\ep_2$-cover for $(\H,d_P)$. So, given any
$\comp{g}{f}\in \H$ choose $f'\in F$ such that $d_{[P,{\G_l}]}(f,f') \leq
\ep_1$ and $g'\in G_{f'}$ such that $d_{P_{f'}}(g,g')\leq \ep_2$. 
Now,
\begin{align*}
d_P(\comp{g}{f},\comp{g'}{f'}) 
&\leq d_P(\comp{g}{f},\comp{g}{f'}) + d_P(\comp{g}{f'},\comp{g'}{f'})\\
&\leq d_{[P,{\G_l}]}(f,f') + d_{P_{f'}}(g,g') \\
&\leq \ep_1 + \ep_2.
\end{align*}
where the first line follows from the triangle inequality for $d_P$
and the second line follows from 
the facts: $d_P(\comp{g}{f'},\comp{g'}{f'}) = d_{P_f}(g,g')$ and 
$d_P(\comp{g}{f},\comp{g}{f'}) \leq d_{[P,\G_l]}(f,f')$. 
Thus $N$ is an $\ep_1+\ep_2$-cover for $(\H,d_P)$ and so the result follows.
\end{proof}
Recalling the definition of $\H_1\oplus\dots\oplus\H_n$ (Definition
\ref{yuck}), we have the following Lemma.
\begin{lem}
\label{prodlem}
$$
\C(\ep,\H_1\oplus\dots\oplus\H_n) \leq 
\prod_{i=1}^n \C(\ep,\H_i)
$$
\end{lem}
\begin{proof}
Fix a product probability measure $\Pb=P_1\times\dots\times P_n$ on 
$\Zn$. Let $N_1,\dots,N_n$ be
$\ep$-covers of $(\H_1,d_{P_1})\dots,(\H_n,d_{P_n})$. 
and let $N = N_1\oplus\dots\oplus N_n$. Given
$h=h_1\oplus\dots\oplus h_n\in
\H_1\oplus\dots\oplus\H_n$, choose $g_1\oplus\dots\oplus g_n\in N$ such that
$d_{P_i}(h_i,g_i) \leq \ep$ for each $i=1,\dots,n$. 
Now,
\begin{align*}
d_{\scPb}(h_1\oplus\dots\oplus h_n, g_1\oplus\dots\oplus g_n) 
&= \frac1n\int_{Z^n} \left|\sum_{i=1}^n h_i(z_i) - 
\sum_{i=1}^n g_i(z_i)\right|\,d\Pb(z_1,\dots,z_n) \\ 
&\leq \frac1n\sum_{i=1}^n d_{P_i}(h_i, g_i) \\
&\leq \ep.
\end{align*}
Thus $N$ is an $\ep$-cover for $\H_1\oplus\dots\oplus\H_n$  and as 
$|N| = \prod_{i=1}^n |N_i|$ the result follows.
\end{proof}

\subsection{Bounding $\mathbold{\C\(\ep,\HH^n_l\)}$}
>From Lemma \ref{litcomplem}, 
\begin{equation}
\label{pone}
\C\(\ep_1 + \ep_2,\comp{{\G_l}^n}{\Fbar}\) \leq \C\(\ep_1,{\G_l}^n\)\, \C_{{\G_l}^n}\(\ep_2,\Fbar\)
\end{equation}
and from Lemma \ref{prodlem},
\begin{equation}
\label{ptwo}
\C\(\ep_1,{\G_l}^n\) \leq \C\(\ep_1,{\G_l}\)^n.
\end{equation}
Using similar techniques to those used to prove Lemmas
\ref{litcomplem} and \ref{prodlem}, $\C_{{\G_l}^n}(\ep,\Fbar)$ can be shown
to satisfy 
\begin{equation}
\label{pthree}
\C_{{\G_l}^n}(\ep_2,\Fbar) \leq \C_{{\G_l}}\(\ep_2,\F\).
\end{equation}
Equations \eqref{hhnl}, \eqref{pone}, \eqref{ptwo} and \eqref{pthree} together imply
inequality  \eqref{hhnlineq}. \\

\subsection{Bounding \boldmath{$\C\(\ep,\HH^*\)$}}
We wish to prove that $\C\(\ep,\HH^*\) \leq
\C_{{\G_l}}\(\ep,\F\)$ when $\HH$ is a hypothesis space family of the form
$\HH = \{\comp{{\G_l}}{f}\colon f\in\F\}$. Note that each $\H^*\in\HH^*$
corresponds to some $\comp{{\G_l}}{f}$, and that 
$$
\H^*(P) = \inf_{g\in{\G_l}} \er_P(\comp{g}{f}).
$$
Any probability measure $Q$ on $\P$ induces a probability measure $Q_\XY$ on
$\XY$, defined by
$$
Q_\XY(S) = \int_\P P(S)\, dQ(P)
$$
for any $S$ in the $\sigma$-algebra on $\XY$.  Note also that if
$h,h'$ are bounded, positive functions on an arbitrary set $A$, then
\begin{equation}
\label{infeq}
\left|\inf_{a\in A} h(a) - \inf_{a\in A} h'(a)\right| \leq 
\sup_{a\in A} \left|h(a) - h'(a)\right|.
\end{equation}
Let $Q$ be any probability measure on the space 
$\P$ of probability measures on $\XY$.
Let $\H_1^*,\H_2^*$ be two elements of $\HH^*$ with corresponding 
hypothesis spaces $\comp{{\G_l}}{f_1}, \comp{{\G_l}}{f_2}$. Then,
\begin{align*}
d_Q(\H_1^*,\H_2^*) 
	&= \int_\P \left|\inf_{g\in{\G_l}} \er_P(\comp{g}{f_1}) - 
	\inf_{g\in{\G_l}} \er_P(\comp{g}{f_2})\right|\,dQ(P) \\
	&\leq \int_\P\sup_{g\in{\G_l}} \left| \er_P(\comp{g}{f_1}) -
	\er_P(\comp{g}{f_2})\right|\,dQ(P) 
	\qquad\text{(by \eqref{infeq} above)} \\
	&\leq \int_\P \int_\XY\sup_{g\in{\G_l}}\left|\comp{g}{f_1}(x,y) -
	\comp{g}{f_2}(x,y)\right|\,dP(x,y)\,dQ(P) \\
	&= d_{[Q_\XY,{\G_l}]}(f_1,f_2).
\end{align*}
The measurability of $\sup_{\G_l} \comp{g}{f}$ is guaranteed by the
permissibility of $\HH$ (Lemma \ref{permlem} part \ref{3}, Appendix
\ref{permsec}).  From $d_Q(\H_1^*, \H_2^*) \leq
d_{[Q_\XY,{\G_l}]}(f_1,f_2)$ we have,
\begin{equation}
\label{beep}
\N\(\ep,\HH^*,d_Q\) \leq \N\(\ep,\F,d_{[Q_\XY,{\G_l}]}\),
\end{equation}
which gives inequality \eqref{hhstarineq}.

\subsection{Proof of Theorem \ref{capthm}}
\label{nnetapp}
In order to prove the bounds in Theorem \ref{capthm} we have to apply
Theorem \ref{gencompthm} to the neural network hypothesis space family
of equation \eqref{nnetfamily}. In this case the structure 
is 
$$
\R^d \xrightarrow{\F}\R^k\xrightarrow{\G}[0,1]
$$
where ${\G} = \{(x_1,\dots,x_k) \mapsto \sigma\(\sum_{i=1}^k \alpha_i
x_i + \alpha_0\)\colon (\alpha_0, \alpha_1,\dots,\alpha_k) \in U\}$
for some bounded subset $U$ of $\R^{k+1}$ and some Lipschitz squashing
function $\sigma$. The feature class $\F\colon \R^d\to \R^k$ is the
set of all one hidden layer neural networks with $d$ inputs, 
$l$ hidden nodes, $k$ outputs, $\sigma$ as the squashing
function and weights $w\in T$ where $T$ is a bounded subset of
$\R^W$. The Lipschitz restriction on $\sigma$ and the bounded
restrictions on the weights ensure that $\F$ and $\G$ are Lipschitz
classes. Hence there exists $b < \infty$ such that for all $f\in \F$
and $x,x'\in \R^d$, $\|f(x) - f(x')\| < b\|x-x'\|$ and for all $g\in
\G$ and $x,x'\in\R^k$, $|g(x) - g(x')| < b\|x-x'\|$ where $\|\cdot\|$
is the $L_1$ norm in each case.  The loss function is squared loss.

Now, $g_l(x,y) = l(g(x),y) = (g(x) - y)^2$, hence
for all $g,g'\in\G$ and all probability measures $P$ on
$\R^{k}\times[0,1]$ (recall that we assumed the output space $Y$ was $[0,1]$),
\begin{align}
d_P(g_l, g'_l) &= \int_{\R^{k}\times[0,1]} \left|(g(v) - y)^2 - (g'(v) -
y)^2\right|\,dP(v,y) \notag\\\label{biff} 
&\leq 2 \int_{\R^k} \left|g(v) - g'(v)\right|\,dP_{\R^k}(v),
\end{align} 
where $P_{\R^k}$ is the marginal distribution on $\R^k$ derived from $P$.
Similarly, for all $f,f'\in \F$ and probability measures $P$ on
$\R^d\times [0,1]$, 
\begin{equation}
\label{boff}
d_{[P,\G_l]}(f,f') \leq 2b \int_{\R^d} \|f(x) - f'(x)\|\,dP_{\R^d}(x).
\end{equation}
Define
$$
\C\(\ep, \G,L^1\) := \sup_P \N\(\ep, \G, L^1(P)\),
$$
where the supremum is over all probability measures on (the Borel
subsets of) $\R^k$, and $\N\(\ep, \G, L^1(P)\)$ is the size of the
smallest $\ep$-cover of $\G$ under the $L^1(P)$ metric. 
Similarly set, 
$$
\C\(\ep, \F,L^1\) := \sup_P \N\(\ep, \F, L^1(P)\),
$$
where now the supremum is over all probability measures on $\R^d$. 
Equations \eqref{biff} and \eqref{boff} imply
\begin{align}
\label{biffy}
\C(\ep, \G_l) &\leq \C\(\frac{\ep}{2},\G, L^1\) \\
\label{boffy}
\C_{\G_l}\(\ep,\F\) &\leq \C\(\frac{\ep}{2b}, \F, L^1\)
\end{align} 
Applying Theorem 11 from \citeA{haussler92a}, we find
\begin{align*}
\C\(\frac{\ep}{2},\G_l, L^1\) &\leq \[\frac{2eb}{\ep}\]^{2k+2} \\
\C\(\frac{\ep}{2b}, \F, L^1\) &\leq \[\frac{2eb^2}{\ep}\]^{2W}.
\end{align*}
Substituting these two expressions into \eqref{biffy} and
\eqref{boffy} and applying Theorem \ref{gencompthm} yields Theorem
\ref{capthm}. \qed

\section{Proof of Theorem \ref{boollowerbound}}
\label{lowerproof}
This proof follows a similar argument to the one presented in
\citeA{bartlett99a} for ordinary Boolean function learning. 

First we need a technical Lemma.
\begin{lem}
\label{techlem}
Let $\alpha$ be a random variable uniformly distributed on 
$\{1/2+\beta/2, 1/2-\beta/2\}$, with $0<\beta<1$. Let $\xi_1,\dots,\xi_m$ be \iid
$\{1,-1\}$-valued random variables with $\Pr(\xi_i=1) = \alpha$ for
all $i$. For any function $f$ mapping $\{1,-1\}^n \to
\{1/2+\beta/2,1/2-\beta/2\}$,
$$
\Pr\left\{\xi_1,\dots,\xi_m\colon f(\xi_1,\dots,\xi_m) \neq \alpha\right\} >
\frac14\[1 - \sqrt{1 - e^{-\frac{m\beta^2}{1-\beta^2}}}\].
$$
\end{lem}
\begin{proof}
Let $N(\xi)$ denote the number of occurences of $+1$ in the random
sequence $\xi=(\xi_1,\dots, \xi_m)$.  The function $f$ can be viewed
as a decision rule, i.e. based on the observations $\xi$, $f$ tries to
guess whether the probability of $+1$ is $1/2+\beta/2$ or
$1/2-\beta/2$. The optimal decision rule is the Bayes estimator:
$f(\xi_1,\dots, \xi_m) = 1/2+\beta/2$ if $N(\xi) \geq m/2$, and
$f(\xi_1,\dots, \xi_m) = 1/2-\beta/2$ otherwise. Hence,
\begin{align*}
\Pr\(f(\xi) \neq \alpha\) &\geq 
\frac12\Pr\(N(\xi) \geq \frac{m}{2}\right.\left|
\alpha = \frac12 - \frac\beta{2}\) \\
&\qquad+ \frac12\Pr\(N(\xi) < \frac{m}{2}\right.\left|
\alpha = \frac12+\frac\beta2\) \\
&> \frac12\Pr\(N(\xi) \geq \frac{m}{2}\right.\left|
\alpha = \frac12 - \frac\beta{2}\)
\end{align*}
which is half the probability that a binomial $(m,1/2-\beta/2)$ random
variable is at least $m/2$. By Slud's inequality \cite{slud77},
$$
\Pr\(f(\xi) \neq \alpha\) > \frac12\Pr\(Z\geq \sqrt{\frac{m\beta^2}{1-\beta^2}}\)
$$
where $Z$ is normal $(0,1)$. Tate's inequality
\cite{tate53} states that for all $x \geq 0$, 
$$
\Pr\(Z\geq x\) \geq \frac12\[1 - \sqrt{1- e^{-x^2}}\].
$$ 
Combining the last two inequalities completes the proof. 
\end{proof}


Let $\x\in\Xnm$ be shattered by $\HH$, with $m=d_\HH(n)$. For each
row $i$ in $\x$ let $\P_i$ be the set of all $2^{d}$
distributions $P$ on $X\times \{\pm1\}$ such that $P(x,1) = P(x,0) =
0$ if $x$ is not contained in the $i$th row of $\x$, and for each
$j=1,\dots, d_\HH(n)$, $P(x_{ij},1) = (1\pm\beta)/(2d_\HH(n))$ and
$P(x_{ij}, -1) = (1\mp\beta)/(2d_\HH(n))$. Let $\P := \P_1\times\dots\times\P_n$.

Note that for $\Pb = (P_1,\dots, P_n) \in \P$, 
the optimal error $\opt_\scPb(\HH^n)$ is achieved by any sequence
$\h^* = (h_1^*,\dots, h_n^*)$ such that $h^*_i(x_{ij}) = 1$ if and only if
$P_i(x_{ij}, 1) = (1+\beta)/(2d_\HH(n))$, and $\HH^n$ always contains
such a sequence because $\HH$ shatters $\x$. The optimal error is then 
$$
\opt_\scPb(\HH^n) = \er_\scPb(\h^*) = \frac1n\sum_{i=1}^n P_i\{h_i^*(x)
\neq y\} = \frac1n\sum_{i=1}^n\sum_{j=1}^{d_\HH(n)}
\frac{1-\beta}{2d_\HH(n)} = \frac{1-\beta}{2},
$$
and for any $\h = (h_1,\dots, h_n)\in\HH^n$, 
\begin{equation}
\label{keep}
\er_\scPb(\h) = \opt_\scPb(\HH^n) + \frac{\beta}{n d_\HH(n)}
\left|\left\{(i,j)\colon h_i(x_{ij}) \neq h^*_i(x_{ij})\right\}\right|.
\end{equation}
For any $(n,m)$-sample $\z$, let each element $m_{ij}$ in the array 
$$
\m(\z):= 
\begin{array}{ccc}
m_{11} & \cdots & m_{1d_\HH(n)} \\
\vdots & \ddots & \vdots\\ 
m_{n1} & \cdots & m_{nd_\HH(n)}
\end{array}
$$
equal the number of occurrences of $x_{ij}$ in $\z$. 

Now, if we select $\Pb= (P_1,\dots, P_n)$ uniformly at random from
$\P$, and generate an $(n,m)$-sample $\z$ using $\Pb$, then for
$\h = \A_n(\z)$ (the output of the learning algorithm) we have:
\begin{align*}
\E\(\left|\left\{(i,j)\colon h_i(x_{ij}) \neq
h^*_i(x_{ij})\right\}\right|\) 
&= \sum_{\m} P(\m) \E\(\left|\left\{(i,j)\colon h_i(x_{ij}) \neq
h^*_i(x_{ij})\right\}\right|\right. \left|\m\) \\
&= \sum_{\m} P(\m) \sum_{i=1}^n\sum_{j=1}^{d_\HH(n)} P\(h(x_{ij}) \neq
h^*(x_{ij}) | m_{ij}\)
\end{align*}
where $P(\m)$ is the probability of generating a configuration $\m$ of
the $x_{ij}$ under the $(n,m)$-sampling process and the sum is over all possible 
configurations. From Lemma \ref{techlem}, 
$$
P\(h(x_{ij}) \neq
h^*(x_{ij}) | m_{ij}\) > 
\frac14\[1 - \sqrt{1 - e^{-\frac{m_{ij}\beta^2}{1-\beta^2}}}\],
$$
hence
\begin{align}
\label{keep2}
\E\[\frac1{nd_\HH(n)}\left|\left\{(i,j) \colon h_i(x_{ij}) 
\neq h^*_i(x_{ij})\right\}\right|\]
&> \frac1{nd_\HH(n)}\sum_{\m} P(\m) \sum_{i=1}^n\sum_{j=1}^{d_\HH(n)} \frac14\[1 - \sqrt{1 -
e^{-\frac{m_{ij}\beta^2}{1-\beta^2}}}\] \notag\\
&\geq \frac{1}{4}\[1 - \sqrt{1 -
e^{-\frac{m\beta^2}{d_\HH(n)(1-\beta^2)}}}\]
\end{align}
by Jensen's inequality. Since for any $[0,1]$-valued random variable $Z$, $\Pr(Z> x) \geq
\E Z - x$, \eqref{keep2} implies:
$$
\Pr\(\frac1{nd_\HH(n)}\left|\left\{(i,j)\colon h_i(x_{ij}) \neq
h^*_i(x_{ij})\right\}\right| > \gamma\alpha\) >
(1-\gamma)\alpha 
$$
where 
\begin{equation}
\label{eq:alpha}
\alpha :=  \frac14\[1 - \sqrt{1 -
e^{-\frac{m\beta^2}{d_\HH(n)(1-\beta^2)}}}\]
\end{equation}
and $\gamma \in[0,1]$. 
Plugging this into \eqref{keep} shows that 
$$
\Pr\left\{(\Pb, \z)\colon \er_\scPb(\A_n(\z)) 
> \opt_{\scPb}(\HH^n) + \gamma\alpha\beta\right\} > (1-\gamma)\alpha. 
$$
Since the inequality holds over the random choice of $\Pb$, it must
also hold for some specific choice of $\Pb$. Hence for any learning
algorithm $\A_n$ there is some sequence of distributions $\Pb$ such
that
$$
\Pr\left\{\z\colon \er_\scPb(\A_n(\z)) 
> \opt_{\scPb}(\HH^n) +\gamma\alpha\beta\right\} > (1-\gamma)\alpha.
$$
Setting 
\begin{equation}
\label{eq:sat}
(1-\gamma)\alpha \geq \delta, \quad\text{and} \quad\gamma\alpha\beta \geq \ep, 
\end{equation}
ensures
\begin{equation}
\label{eq:probm}
\Pr\left\{\z\colon \er_\scPb(\A_n(\z)) 
> \opt_{\scPb}(\HH^n) + \ep\right\} > \delta.
\end{equation}
Assuming equality in \eqref{eq:sat}, we get
$$
\alpha = \frac{\delta}{1-\gamma}, \qquad\beta = \frac\ep\delta\frac{1-\gamma}{\gamma}.
$$
Solving \eqref{eq:alpha} for $m$, and substituting the above
expressions for $\alpha$ and $\beta$ shows that \eqref{eq:probm} is
satisfied provided 
\begin{equation}
\label{eq:bigm}
m \leq d_\HH(n) \[\(\frac\delta\ep\)^2\(\frac{\gamma}{1 - \gamma}\)^2 - 1\]
\log\frac{\(1-\gamma\)^2}{8\delta\(1-\gamma - 2 \delta\)}
\end{equation}
Setting $\gamma = 1 - a\delta$ for some $a > 4$ ($a > 4$ since $\alpha 
< 1/4$ and $\alpha = \delta /(1-\gamma)$), and assuming $\ep, \delta
\leq 1/(k a)$ for some $k > 2$, \eqref{eq:bigm} becomes 
\begin{equation}
\label{eq:biggm}
m \leq \frac{d_\HH(n)}{a^2}\[1 - \frac{2}{k} \] \log\frac{a^2}{8(a -
2)}.
\end{equation}
Subject to the constraint $a>4$, the right hand side of
\eqref{eq:biggm} is approximately maximized at $a = 8.7966$, at which
point the value exceeds $d_\HH(n)(1 - 2/k) / (220 \ep^2)$. Thus, for
all $k\geq 1$, if $\ep,\delta \leq 1 / 9k$ and 
\begin{equation}
\label{firstm}
m \leq \frac{d_\HH(n)\(1 - \frac2k\)}{220 \ep^2},
\end{equation}
then 
$$
\Pr\left\{\z\colon \er_\scPb(\A_n(\z)) 
> \opt_{\scPb}(\HH^n) + \ep\right\} > \delta.
$$

To obtain the $\delta$-dependence in Theorem \ref{boollowerbound}
observe that by assumption $\HH^1$ contains at least two functions
$h_1, h_2$, hence there exists an $x\in X$ such that $h_1(x) \neq
h_2(x)$. Let $P^\pm$ be two distributions concentrated on $(x,1)$ and
$(x, -1)$ such that $P^\pm\(x, h_1(x)\) = (1\pm\ep)/2$  and $P^\pm\(x,
h_2(x)\) = (1\mp\ep)/2$. Let $\Pb^+ := P^+\times\dots\times P^+$ and 
$\Pb^- := P^-\times\dots\times P^-$ be the product distributions
on $\(X\times\{\pm1\}\)^n$ generated by $P^\pm$, and $\h_1 :=
(h_1,\dots, h_1), \h_2:= (h_2, \dots, h_2)$. Note that $\h_1$ and
$\h_2$ are both in $\HH^n$. If $\Pb$ is one of $\Pb^\pm$ and the
learning algorithm $\A_n$ chooses the wrong hypothesis $\h$, then 
$$
\er_\scPb(\h) - \opt_\scPb(\HH^n) = \ep.
$$
Now, if we choose $\Pb$ uniformly at random from $\{\Pb^+, \Pb^-\}$
and generate an $(n,m)$-sample $\z$ according to $\Pb$, Lemma
\ref{techlem} shows that 
$$
\Pr\{(\Pb, \z)\colon \er_\scPb(\A_n(\z)) \geq \opt_\scPb(\HH^n) + \ep\}
> \frac14\[1 - \sqrt{1-e^{\frac{nm\ep^2}{1-\ep^2}}}\],
$$
which is at least $\delta$ if
\begin{equation}
\label{secondm}
m < \frac{1-\ep^2}{\ep^2}\frac1n\log\frac1{8\delta(1-2\delta)}
\end{equation}
provided $0<\delta < 1/4$. Combining the two constraints on $m$:
\eqref{firstm} (with $k=7$) and 
\eqref{secondm}, and using $\max\{x_1,x_2\} \geq \frac12(x_1+x_2)$ finishes
the proof. $\Box$

\section{Measurability}
\label{permsec}
In order for Theorems \ref{biaslearnthm} and \ref{fundthm} to hold in
full generality we had to impose a constraint called
``permissibility'' on the hypothesis space family $\HH$.
Permissibility was introduced by \citeA{pollard84a} for ordinary
hypothesis classes $\H$.  His definition is very similar to
Dudley's ``image admissible Suslin'' \cite{Dudley}. We will be
extending this definition to cover hypothesis space families. 

Throughout this section we assume all functions $h$ map from (the
complete separable metric space) $Z$ into $[0,1]$. Let $\B(T)$ denote
the Borel $\sigma$-algebra of any topological space $T$. As in Section
\ref{EPsec}, we view $\P$, the set of all probability measures on $Z$,
as a topological space by equipping it with the topology of weak
convergence. $\B(\P)$ is then the $\sigma$-algebra generated by this
topology.  The following two definitions are taken (with minor
modifications) from \citeA{pollard84a}.
\begin{defn}
\label{index}
A set $\H$ of $[0,1]$-valued functions on $Z$ is {\em indexed} by the
set $T$ if there exists a function $f\colon Z\times T\to [0,1]$ such
that
$$
\H = \left\{f(\,\cdot\,,t)\colon t\in T\right\}.
$$ 
\end{defn}
\begin{defn}
\label{permissible}
The set $\H$ is {\em permissible} if it can be indexed by a set $T$ 
such that
\begin{enumerate}
\item $T$ is an analytic subset of a Polish\footnote{A topological
space is called {\em Polish} if it is metrizable such that it is a
complete separable metric space.} space $\Tbar$, and
\item the function $f\colon Z\times T\to [0,1]$ indexing $\H$ by $T$
is measurable with respect to the product $\sigma$-algebra $\B(Z)\otimes
\B(T)$.
\end{enumerate}
\end{defn}
An analytic subset $T$ of a Polish space $\Tbar$ is 
simply the continuous image of a Borel subset $X$ of another Polish
space $\Xbar$.  The analytic subsets of a Polish space include the
Borel sets. They are important because projections of analytic sets
are analytic, and can be measured in a complete measure space whereas
projections of Borel sets are not necessarily Borel, and hence cannot
be measured with a Borel measure. For more details see 
\citeA{Dud}, section 13.2. 
\begin{lem}
\label{htimespermiss}
$\H_1\oplus\dots\oplus\H_n\colon \Zn\to [0,1]$ is permissible if
$\H_1,\dots,\H_n$ are all permissible.
\end{lem}
\begin{proof}
Omitted.
\end{proof}

We now define permissibility of hypothesis space families.
\begin{defn}
A hypothesis space family $\HH= \{\H\}$ is {\em permissible} if there exist
sets $S$ and $T$ that are analytic subsets of Polish spaces $\Sbar$
and $\Tbar$ respectively, and a function $f\colon Z\times T\times S\to
[0,1]$, measurable with respect to $\S\otimes\B(T)\otimes\B(S)$, such
that
$$
\HH = \bigl\{\{f(\,\cdot\,,t,s)\colon  t\in T\}\colon  s\in S\bigr\}.
$$
\end{defn}

Let $\(X,\Sigma,\mu\)$ be a measure space and $T$ be an analytic
subset of a Polish space. Let $\A(X)$ denote the analytic subsets of
$X$.  The following three facts about analytic sets are taken
from \citeA{pollard84a}\label{PE3}, appendix C.  \newcounter{bean}
\setcounter{bean}{1}
\begin{list}{(\alph{bean})}{\usecounter{bean}}
\item If $(X,\Sigma,\mu)$ is complete then $\A(X) \subseteq \Sigma$.
\item $\A(X\times T)$ contains the product $\sigma$-algebra
$\Sigma\otimes\B(T)$.
\item For any set $Y$ in $\A(X \times T)$, the projection $\pi_X Y$ of $Y$
onto $X$ is in $\A(X)$.
\end{list}

Recall Definition \ref{stardef} for the definition of $\HH^*$.
In the following Lemma we assume that
$(Z,\B(Z))$ has been completed with respect to any probability measure $P$,
and also that $(\P,\B(\P))$ is complete with respect to the environmental
measure $Q$.

\begin{lem}
\label{permlem}
For any permissible hypothesis space family $\HH$, 
\begin{enumerate}
\item\label{0} $\HH^n_l$ is permissible.
\item\label{1} $\{h\in\H\colon \H\in\HH\}$ is permissible.
\item\label{2} $\H$ is permissible for all $\H\in \HH$.
\item\label{3} $\sup_\H$ and $\inf_\H$ are measurable for all $\H\in\HH$.
\item\label{4} $\H^*$ is measurable for all $\H\in \HH$.
\item\label{5} $\HH^*$ is permissible.
\end{enumerate}
\end{lem}
\begin{proof}
As we have absorbed the loss function into the hypotheses $h$, $\HH^n_l$
is simply the set of all $n$-fold products $\H\oplus\dots\oplus\H$
such that $\H\in\HH$. Thus (\ref{0}) follows from Lemma
\ref{htimespermiss}. (\ref{1}) and (\ref{2}) are immediate from the
definitions.  As $\H$ is permissible for all $\H\in\HH$, (\ref{3})
can be proved by an identical argument to that used in the
``Measurable Suprema'' section of \citeA{pollard84a}, appendix C. 

For (\ref{4}), note that for any Borel-measurable $h\colon Z\to
[0,1]$, the function $\hbar\colon \P\to [0,1]$ defined by $\hbar(P) :=
\int_Z h(z)\, dP(z)$ is Borel measurable \citeA[chapter 17]{kechris95}.  
Now, permissibility of $\H$ automatically implies
permissibility of $\Hbar := \{\hbar\colon h\in\H\}$, and $\H^* =
\inf_{\Hbar}$ so $\H^*$ is measurable by (\ref{3}).

Now let $\HH$ be indexed by $f\colon Z\times T\times S\to [0,1]$ in
the appropriate way. To prove (\ref{5}), define $g\colon\P\times
T\times S\to [0,1]$ by $g(P,t,s) := \int_Z f(z,t,s)\, dP(z)$.  By
Fubini's theorem $g$ is a $\B(\P)\otimes\B(T)\otimes\B(S)$-measurable
function. Let $G\colon \P\times S\to [0,1]$ be defined by $G(P,s) :=
\inf_{t\in T} g(P,t,s)$. $G$ indexes $\HH^*$ in the appropriate way
for $\HH^*$ to be permissible, provided it can be shown that $G$ is
$\B(\P)\otimes \B(S)$-measurable. This is where analyticity becomes
important.  Let $g_\alpha := \{(P,t,s)\colon g(P,t,s) > \alpha\}$. By
property (b) of analytic sets, $\A\(\P\times T\times S\)$ contains
$g_\alpha$. The set $G_\alpha := \{(P,s)\colon G(P,s) > \alpha\}$ is
the projection of $g_\alpha$ onto $\P\times S$, which by property (c)
is also analytic. As $(\P,\B(\P),Q)$ is assumed complete, $G_\alpha$ is
measurable, by property (a).  Thus $G$ is a measurable function and
the permissibility of $\HH^*$ follows.
\end{proof}
\bibliographystyle{theapa}
\begin{thebibliography}{}

\bibitem[\protect\BCAY{Abu-Mostafa}{Abu-Mostafa}{1993}]{mostafa93a}
Abu-Mostafa, Y. \BBOP1993\BBCP.
\newblock \BBOQ A method for learning from hints\BBCQ\
\newblock In Hanson, S.~J., Cowan, J.~D., \BBA\ Giles, C.~L.\BEDS, {\Bem
  Advances in Neural Information Processing Systems 5}, \BPGS\ 73--80\ San
  Mateo, CA. Morgan Kaufmann.

\bibitem[\protect\BCAY{Anthony \BBA\ Bartlett}{Anthony \BBA\
  Bartlett}{1999}]{bartlett99a}
Anthony, M.\BBACOMMA\  \BBA\ Bartlett, P.~L. \BBOP1999\BBCP.
\newblock {\Bem Neural Network Learning: Theoretical Foundations}.
\newblock Cambridge University Press, Cambridge, UK.

\bibitem[\protect\BCAY{Bartlett}{Bartlett}{1993}]{bartlett93}
Bartlett, P.~L. \BBOP1993\BBCP.
\newblock \BBOQ Lower bounds on the {VC}-dimension of multi-layer threshold
  networks\BBCQ\
\newblock In {\Bem Proccedings of the Sixth ACM Conference on Computational
  Learning Theory}, \BPGS\ 44--150\ New York. ACM Press.
\newblock Summary appeared in Neural Computation, 5, no. 3.

\bibitem[\protect\BCAY{Bartlett}{Bartlett}{1998}]{Bar98}
Bartlett, P.~L. \BBOP1998\BBCP.
\newblock \BBOQ The sample complexity of pattern classification with neural
  networks: the size of the weights is more important than the size of the
  network\BBCQ\
\newblock {\Bem IEEE Transactions on Information Theory}, {\Bem 44\/}(2),
  525--536.

\bibitem[\protect\BCAY{Baxter}{Baxter}{1995a}]{thesis}
Baxter, J. \BBOP1995a\BBCP.
\newblock {\Bem Learning Internal Representations}.
\newblock Ph.D.\ thesis, Department of Mathematics and Statistics, The Flinders
  University of South Australia.
\newblock Copy available from
  {http://wwwsyseng.anu.edu.au/$\sim$jon/papers/thesis.ps.gz}.

\bibitem[\protect\BCAY{Baxter}{Baxter}{1995b}]{95a}
Baxter, J. \BBOP1995b\BBCP.
\newblock \BBOQ Learning internal representations\BBCQ\
\newblock In {\Bem Proceedings of the Eighth International Conference on
  Computational Learning Theory}, \BPGS\ 311--320. ACM Press.
\newblock Copy available from
  {http://wwwsyseng.anu.edu.au/$\sim$jon/papers/colt95.ps.gz}.

\bibitem[\protect\BCAY{Baxter}{Baxter}{1997a}]{97b}
Baxter, J. \BBOP1997a\BBCP.
\newblock \BBOQ A {B}ayesian/information theoretic model of learning to learn
  via multiple task sampling\BBCQ\
\newblock {\Bem Machine Learning}, {\Bem 28}, 7--40.

\bibitem[\protect\BCAY{Baxter}{Baxter}{1997b}]{icml_97}
Baxter, J. \BBOP1997b\BBCP.
\newblock \BBOQ The canonical distortion measure for vector quantization and
  function approximation\BBCQ\
\newblock In {\Bem Proceedings of the Fourteenth International Conference on
  Machine Learning}, \BPGS\ 39--47. Morgan Kaufmann.

\bibitem[\protect\BCAY{Baxter \BBA\ Bartlett}{Baxter \BBA\
  Bartlett}{1998}]{nips_97}
Baxter, J.\BBACOMMA\  \BBA\ Bartlett, P.~L. \BBOP1998\BBCP.
\newblock \BBOQ The canonical distortion measure in feature space and 1-{NN}
  classification\BBCQ\
\newblock In {\Bem Advances in Neural Information Processing Systems 10},
  \BPGS\ 245--251. {MIT} Press.

\bibitem[\protect\BCAY{Berger}{Berger}{1985}]{Berger85}
Berger, J.~O. \BBOP1985\BBCP.
\newblock {\Bem Statistical Decision Theory and {B}ayesian Analysis}.
\newblock Springer-Verlag, New York.

\bibitem[\protect\BCAY{Blumer, Ehrenfeucht, Haussler, \BBA\ Warmuth}{Blumer
  et~al.}{1989}]{blumer89a}
Blumer, A., Ehrenfeucht, A., Haussler, D., \BBA\ Warmuth, M.~K. \BBOP1989\BBCP.
\newblock \BBOQ Learnability and the vapnik-chervonenkis dimension\BBCQ\
\newblock {\Bem Journal of the ACM}, {\Bem 36}, 929--965.

\bibitem[\protect\BCAY{Caruana}{Caruana}{1997}]{caruana97a}
Caruana, R. \BBOP1997\BBCP.
\newblock \BBOQ Multitask learning\BBCQ\
\newblock {\Bem Machine Learning}, {\Bem 28}, 41--70.

\bibitem[\protect\BCAY{Devroye, Gy\"{o}rfi, \BBA\ Lugosi}{Devroye
  et~al.}{1996}]{gabor97a}
Devroye, L., Gy\"{o}rfi, L., \BBA\ Lugosi, G. \BBOP1996\BBCP.
\newblock {\Bem A Probabilistic Theory of Pattern Recognition}.
\newblock Springer, New York.

\bibitem[\protect\BCAY{Dudley}{Dudley}{1984}]{Dudley}
Dudley, R.~M. \BBOP1984\BBCP.
\newblock {\Bem A Course on Empirical Processes}, \lowercase{\BVOL}\ 1097 of
  {\Bem Lecture Notes in Mathematics}, \BPGS\ 2--142.
\newblock Springer-Verlag.

\bibitem[\protect\BCAY{Dudley}{Dudley}{1989}]{Dud}
Dudley, R.~M. \BBOP1989\BBCP.
\newblock {\Bem Real Analysis and Probability}.
\newblock Wadsworth \& Brooks/Cole, California.

\bibitem[\protect\BCAY{Gelman, Carlin, Stern, \BBA\ Rubim}{Gelman
  et~al.}{1995}]{Gelman95}
Gelman, A., Carlin, J.~B., Stern, H.~S., \BBA\ Rubim, D.~B.\BEDS.
  \BBOP1995\BBCP.
\newblock {\Bem {B}ayesian Data Analysis}.
\newblock Chapman and Hall.

\bibitem[\protect\BCAY{Good}{Good}{1980}]{Good80}
Good, I.~J. \BBOP1980\BBCP.
\newblock \BBOQ Some history of the hierarchical {B}ayesian methodology\BBCQ\
\newblock In Bernardo, J.~M., Groot, M. H.~D., Lindley, D.~V., \BBA\ Smith, A.
  F.~M.\BEDS, {\Bem {B}ayesian Statistics II}. University Press, Valencia.

\bibitem[\protect\BCAY{Haussler}{Haussler}{1992}]{haussler92a}
Haussler, D. \BBOP1992\BBCP.
\newblock \BBOQ Decision theoretic generalizations of the pac model for neural
  net and other learning applications\BBCQ\
\newblock {\Bem Information and Computation}, {\Bem 100}, 78--150.

\bibitem[\protect\BCAY{Heskes}{Heskes}{1998}]{heskes98}
Heskes, T. \BBOP1998\BBCP.
\newblock \BBOQ Solving a huge number of similar tasks: a combination of
  multi-task learning and a hierarchical {B}ayesian approach\BBCQ\
\newblock In Shavlik, J.\BED, {\Bem Proceedings of the 15th International
  Conference on Machine Learning (ICML '98)}, \BPGS\ 233--241. Morgan Kaufmann.

\bibitem[\protect\BCAY{Intrator \BBA\ Edelman}{Intrator \BBA\
  Edelman}{1996}]{edelman96a}
Intrator, N.\BBACOMMA\  \BBA\ Edelman, S. \BBOP1996\BBCP.
\newblock \BBOQ How to make a low-dimensional representation suitable for
  diverse tasks\BBCQ\
\newblock {\Bem Connection Science}, {\Bem 8}.

\bibitem[\protect\BCAY{Kechris}{Kechris}{1995}]{kechris95}
Kechris, A.~S. \BBOP1995\BBCP.
\newblock {\Bem Classical Descriptive Set Theory}.
\newblock Springer-Verlag, New York.

\bibitem[\protect\BCAY{Khan, Muggleton, \BBA\ Parson}{Khan
  et~al.}{1998}]{khan98}
Khan, K., Muggleton, S., \BBA\ Parson, R. \BBOP1998\BBCP.
\newblock \BBOQ Repeat learning using predicate invention\BBCQ\
\newblock In Page, C.~D.\BED, {\Bem Proceedings of the 8th International
  Workshop on Inductive Logic Programming (ILP-98)}, LNAI 1446, \BPGS\ 65--174.
  Springer-Verlag.

\bibitem[\protect\BCAY{Langford}{Langford}{1999}]{langford99}
Langford, J.~C. \BBOP1999\BBCP.
\newblock \BBOQ Staged learning\BBCQ\
\newblock \BTR, CMU, School of Computer Science.
\newblock http://www.cs.cmu.edu/$\sim$jcl/research/ltol/staged\_latest.ps.

\bibitem[\protect\BCAY{Mitchell}{Mitchell}{1991}]{mitchell91}
Mitchell, T.~M. \BBOP1991\BBCP.
\newblock \BBOQ The need for biases in learning generalisations\BBCQ\
\newblock In Dietterich, T.~G.\BBACOMMA\  \BBA\ Shavlik, J.\BEDS, {\Bem
  Readings in Machine Learning}. Morgan Kaufmann.

\bibitem[\protect\BCAY{Parthasarathy}{Parthasarathy}{1967}]{parthasarathy67}
Parthasarathy, K.~R. \BBOP1967\BBCP.
\newblock {\Bem Probabiliity Measures on Metric Spaces}.
\newblock Academic Press, London.

\bibitem[\protect\BCAY{Pollard}{Pollard}{1984}]{pollard84a}
Pollard, D. \BBOP1984\BBCP.
\newblock {\Bem Convergence of Stochastic Processes}.
\newblock Springer-Verlag, New York.

\bibitem[\protect\BCAY{Pratt}{Pratt}{1992}]{pratt}
Pratt, L.~Y. \BBOP1992\BBCP.
\newblock \BBOQ Discriminability-based transfer between neural networks\BBCQ\
\newblock In Hanson, S.~J., Cowan, J.~D., \BBA\ Giles, C.~L.\BEDS, {\Bem
  Advances in Neural Information Processing Systems 5}, \BPGS\ 204--211. Morgan
  Kaufmann.

\bibitem[\protect\BCAY{Rendell, Seshu, \BBA\ Tcheng}{Rendell
  et~al.}{1987}]{Rendell87}
Rendell, L., Seshu, R., \BBA\ Tcheng, D. \BBOP1987\BBCP.
\newblock \BBOQ Layered concept learning and dynamically-variable bias
  management\BBCQ\
\newblock In {\Bem Proceedings of the Tenth International Joint Conference on
  Artificial Intelligence (IJCAI '87)}, \BPGS\ 308--314. IJCAI , Inc.

\bibitem[\protect\BCAY{Ring}{Ring}{1995}]{ring95}
Ring, M.~B. \BBOP1995\BBCP.
\newblock {\Bem Continual Learning in Reinforcement Environments}.
\newblock R. Oldenbourg Verlag.

\bibitem[\protect\BCAY{Russell}{Russell}{1989}]{russell86}
Russell, S. \BBOP1989\BBCP.
\newblock {\Bem The Use of Knowledge in Analogy and Induction}.
\newblock Morgan Kaufmann.

\bibitem[\protect\BCAY{Sauer}{Sauer}{1972}]{sauer72}
Sauer, N. \BBOP1972\BBCP.
\newblock \BBOQ On the density of families of sets\BBCQ\
\newblock {\Bem Journal of Combinatorial Theory A}, {\Bem 13}, 145--168.

\bibitem[\protect\BCAY{Sharkey \BBA\ Sharkey}{Sharkey \BBA\
  Sharkey}{1993}]{sharkey93}
Sharkey, N.~E.\BBACOMMA\  \BBA\ Sharkey, A. J.~C. \BBOP1993\BBCP.
\newblock \BBOQ Adaptive generalisation and the transfer of knowledge\BBCQ\
\newblock {\Bem Artificial Intelligence Review}, {\Bem 7}, 313--328.

\bibitem[\protect\BCAY{Silver \BBA\ Mercer}{Silver \BBA\
  Mercer}{1996}]{silver96}
Silver, D.~L.\BBACOMMA\  \BBA\ Mercer, R.~E. \BBOP1996\BBCP.
\newblock \BBOQ The parallel transfer of task knowledge using dynamic learning
  rates based on a measure of relatedness\BBCQ\
\newblock {\Bem Connection Science}, {\Bem 8}, 277--294.

\bibitem[\protect\BCAY{Singh}{Singh}{1992}]{singh92}
Singh, S. \BBOP1992\BBCP.
\newblock \BBOQ Transfer of learning by composing solutions of elemental
  sequential tasks\BBCQ\
\newblock {\Bem Machine Learning}, {\Bem 8}, 323--339.

\bibitem[\protect\BCAY{Slud}{Slud}{1977}]{slud77}
Slud, E. \BBOP1977\BBCP.
\newblock \BBOQ Distribution inequalities for the binomial law\BBCQ\
\newblock {\Bem Annals of Probability}, {\Bem 4}, 404--412.

\bibitem[\protect\BCAY{Suddarth \BBA\ Holden}{Suddarth \BBA\
  Holden}{1991}]{Suddarth91}
Suddarth, S.~C.\BBACOMMA\  \BBA\ Holden, A. D.~C. \BBOP1991\BBCP.
\newblock \BBOQ Symolic-neural systems and the use of hints in developing
  complex systems\BBCQ\
\newblock {\Bem International Journal of Man-Machine Studies}, {\Bem 35},
  291--311.

\bibitem[\protect\BCAY{Suddarth \BBA\ Kergosien}{Suddarth \BBA\
  Kergosien}{1990}]{Suddarth90}
Suddarth, S.~C.\BBACOMMA\  \BBA\ Kergosien, Y.~L. \BBOP1990\BBCP.
\newblock \BBOQ Rule-injection hints as a means of improving network
  performance and learning time\BBCQ\
\newblock In {\Bem Proceedings of the EURASIP Workshop on Neural Networks}\
  Portugal. EURASIP.

\bibitem[\protect\BCAY{Sutton}{Sutton}{1992}]{sutton92}
Sutton, R. \BBOP1992\BBCP.
\newblock \BBOQ Adapting bias by gradient descent: An incremental version of
  delta-bar-delta\BBCQ\
\newblock In {\Bem Proceedings of the Tenth National Conference on Artificial
  Intelligence}, \BPGS\ 171--176. {MIT} Press.

\bibitem[\protect\BCAY{Tate}{Tate}{1953}]{tate53}
Tate, R.~F. \BBOP1953\BBCP.
\newblock \BBOQ On a double inequality of the normal distribution\BBCQ\
\newblock {\Bem Annals of Mathematical Statistics}, {\Bem 24}, 132--134.

\bibitem[\protect\BCAY{Thrun}{Thrun}{1996}]{thrun96a}
Thrun, S. \BBOP1996\BBCP.
\newblock \BBOQ Is learning the n-th thing any easier than learning the
  first?\BBCQ\
\newblock In {\Bem Advances in Neural Information Processing Systems 8}, \BPGS\
  640--646. {{MIT}} Press.

\bibitem[\protect\BCAY{Thrun \BBA\ Mitchell}{Thrun \BBA\
  Mitchell}{1995}]{thrun95b}
Thrun, S.\BBACOMMA\  \BBA\ Mitchell, T.~M. \BBOP1995\BBCP.
\newblock \BBOQ Learning one more thing\BBCQ\
\newblock In {\Bem Proceedings of the International Joint Conference on
  Artificial Intelligence}, \BPGS\ 1217--1223. Morgan Kaufmann.

\bibitem[\protect\BCAY{Thrun \BBA\ O'Sullivan}{Thrun \BBA\
  O'Sullivan}{1996}]{thrun96b}
Thrun, S.\BBACOMMA\  \BBA\ O'Sullivan, J. \BBOP1996\BBCP.
\newblock \BBOQ Discovering structure in multiple learning tasks: The {TC}
  algorithm\BBCQ\
\newblock In Saitta, L.\BED, {\Bem Proceedings of the 13th International
  Conference on Machine Learning (ICML '96)}, \BPGS\ 489--497. Morgen Kaufmann.

\bibitem[\protect\BCAY{Thrun \BBA\ Pratt}{Thrun \BBA\ Pratt}{1997}]{thrun97a}
Thrun, S.\BBACOMMA\  \BBA\ Pratt, L.\BEDS. \BBOP1997\BBCP.
\newblock {\Bem Learning to Learn}.
\newblock Kluwer Academic.

\bibitem[\protect\BCAY{Thrun \BBA\ Schwartz}{Thrun \BBA\
  Schwartz}{1995}]{thrun95c}
Thrun, S.\BBACOMMA\  \BBA\ Schwartz, A. \BBOP1995\BBCP.
\newblock \BBOQ Finding structure in reinforcement learning\BBCQ\
\newblock In Tesauro, G., Touretzky, D., \BBA\ Leen, T.\BEDS, {\Bem Advances in
  Neural Information Processing Systems}, \lowercase{\BVOL}~7, \BPGS\ 385--392.
  {MIT} Press.

\bibitem[\protect\BCAY{Utgoff}{Utgoff}{1986}]{utgoff86}
Utgoff, P.~E. \BBOP1986\BBCP.
\newblock \BBOQ Shift of bias for inductive concept learning\BBCQ\
\newblock In {\Bem Machine Learning: An Artificial Intelligence Approach},
  \BPGS\ 107--147. Morgan Kaufmann.

\bibitem[\protect\BCAY{Valiant}{Valiant}{1984}]{valiant84}
Valiant, L.~G. \BBOP1984\BBCP.
\newblock \BBOQ A theory of the learnable\BBCQ\
\newblock {\Bem Comm. ACM}, {\Bem 27}, 1134--1142.

\bibitem[\protect\BCAY{Vapnik}{Vapnik}{1982}]{vapnik82a}
Vapnik, V.~N. \BBOP1982\BBCP.
\newblock {\Bem Estimation of Dependences Based on Empirical Data}.
\newblock Springer-Verlag, New York.

\bibitem[\protect\BCAY{Vapnik}{Vapnik}{1996}]{vapnik96a}
Vapnik, V.~N. \BBOP1996\BBCP.
\newblock {\Bem The Nature of Statistical Learning Theory}.
\newblock Springer Verlag, New York.

\end{thebibliography}

\end{document}
