%final JMLR paper
\documentclass[twoside,11pt]{article}
\usepackage{jmlr2e}
\usepackage{natbib}
\usepackage{amsmath}



\def\rest#1{{\vert_{#1}}}
\def\p{{\mathbb P}}
\def\pr{{\rm Pr}}
\def\circplus{\bigoplus}
\def\blankbox{~\hfill$\rlap{$\sqcap$}\sqcup$}
\def\iff{\Longleftrightarrow}
\def\ip#1#2{{\left\langle #1, #2 \right\rangle}}
%\def\ve#1{{\bf #1}}
\def\ve#1{{#1}}
\def\ph{\hspace{1em}}
\def\zero{{\xi}}
\def\td{{\rm TD}}
\def\pos{{\rm pos}}
\def\neg{{\rm neg}}
\def\proof{\noindent{\bf Proof:}\hspace{0.5em}}
\def\l{{\cal L}}
\def\tup{t\negthinspace\uparrow}
\def\tdown{t\negthinspace\downarrow}
\def\rep{\leftarrow}
\def\lessthan{\preceq}
\def\P{{\cal P}}
\def\tdl{{\rm TDL}}
\def\mlt{{\rm MLT}}
\def\one{{\mathbb T}}
\def\example{{\bf Example:}\ }
\def\barx{{\bar x}}
\def\bary{{\bar y}}
\def\comp{\mbox{\rm COMP}}
\def\membership{\mbox{\sc MEMBERSHIP}}
\def\C{{\cal C}}
\def\ipn{{\rm IP}}
\def\inp{{\rm IP}}
\def\mlt#1#2{{\rm MLT}_{n,k}}
\def\vcdim{\mbox{{\rm VC-dim}}}
\def\parity{{\rm Parity}}
\def\L{{\cal L}}
\def\e{{\bf e}}
\def\o{{\bf o}}

\usepackage{amssymb}
%}
%{}

\def\bbr{\mathbb R}
\def\bbq{\mathbb Q}
\def\bbz{\mathbb Z}
\def\bbn{\mathbb N}



\def\vc{{\rm VCdim}}
\def\sgn{{\rm sgn}}
\def\LTM{{\rm LTM}}
\def\LT{{\rm LT}}

\def\w{{\bf w}}
\def\x{{\bf x}}
\def\cover{{\cal N}_\infty}
\def\er{{\rm er}}

%\renewcommand{\baselinestretch}{1.5}


%\textwidth=16truecm \textheight=20truecm

%\hoffset=-0.75truein

\bibpunct{(}{)}{;}{a}{,}{,}

\begin{document}


\jmlrheading{5}{2004}{189--217}{8/03}{2/04}{Martin Anthony}
\firstpageno{189}
\ShortHeadings{Generalization by Threshold Decision
Lists}{Anthony}


\title{Generalization Error Bounds for Threshold Decision Lists}

\author{{\bf Martin Anthony} \hfill {\sc m.anthony@lse.ac.uk}\\\addr{Department of Mathematics}\\\addr{London School of Economics}\\
\addr{London WC2A 2AE\\\addr{United Kingdom}}}

\editor{Yoram Singer}

\maketitle


\begin{abstract} In this paper we consider the generalization
accuracy of classification methods based on the iterative use of
linear classifiers. The resulting classifiers, which we call {\em
threshold decision lists} act as follows. Some points of the data
set to be classified are given a particular classification
according to a linear threshold function (or hyperplane). These
are then removed from consideration, and the procedure is iterated
until all points are classified. Geometrically, we can imagine
that at each stage, points of the same classification are
successively chopped off from the data set by a hyperplane.
 We analyse theoretically the generalization properties of data classification techniques
 that are based on the
 use of threshold decision lists and on the special subclass of {\em multilevel threshold
 functions}. We present bounds on the generalization error in a standard probabilistic learning framework.
 The primary focus in this paper is on obtaining generalization error bounds
 that
 depend on the levels of separation---or {\em margins}---achieved by the successive linear
 classifiers. We also improve and extend previously published
 theoretical bounds on the generalization ability of perceptron
 decision trees.
\end{abstract}

\vspace*{\baselineskip}

\begin{keywords} Threshold decision lists, generalization error, large margin bounds,
growth function, covering numbers, perceptron decision trees
\end{keywords}

%\newpage

\section{Introduction}

This paper concerns the use of {\em threshold decision lists} for
classifying data into two classes. The use of such methods has a
natural geometrical interpretation and can be appropriate for an
iterative or sequential approach to data classification, in which
some points of the data set are given a particular classification,
according to a linear threshold function (or hyperplane), are then
removed from consideration, and the procedure iterated until all
points are classified. We
 analyse theoretically the generalization properties of data classification techniques
 that are based on the
 use of threshold decision lists and the subclass of {\em multilevel threshold
 functions}. This analysis is carried out within the framework of the probabilistic PAC model of learning
 and its variants \citep[see][]{Valiant,Vapnik,AnthonyBiggs,ab,BEHW}.


 \subsection{Outline of the Paper}

Probabilistic approaches to the theory of machine learning can
provide bounds on the `generalization error' of classifiers. Such
results give probabilistic guarantees on the future performance of
a classifier trained on a large random training set.
 This paper takes three main approaches to bounding the generalization error of threshold decision lists.

 First, in the `classical' approach to the PAC model, we present
 results on generalization that are obtained through bounding the
 growth function of these classes.

 Secondly, we
 obtain bounds on the generalization error of threshold decision lists that
 depend on the levels of separation---or {\em margins}---achieved by
 the successive linear classifiers. We use techniques inspired by~\citet{STC} and~\citet{bennett}, and
 also give generalization bounds for {\em perceptron
 decision trees}, improving upon and extending previous such
 results from~\citet{STC} and~\citet{bennett}.

 Thirdly,
 we focus specifically on the special subclass comprising the {multilevel
 threshold functions}. Here, a different and more specialized analysis results in
 generalization error bounds that are
 better than those that follow from the general results on threshold decision lists.

The rest of this section introduces the classes of threshold
decision lists and multilevel threshold functions, and discusses
related work. Section~\ref{sec:model} discusses the definitions of
generalization error. In Section~\ref{sec:PAC}, we derive bounds
on the growth function and use these to bound the generalization
error. Section~\ref{sec:margintdls} discusses the important idea
of large-margin classification as it applies to threshold decision
lists. Here, we give generalization error bounds that depend on
the sizes of the margins and we also indicate some improved bounds
for perceptron decision trees. Section~\ref{sec:mlt} discusses the
more specific margin-based analysis for multilevel threshold
functions. Section~\ref{sec:conclusions} concludes the paper and
suggests some possible directions for future work.

\subsection{Threshold Decision Lists}

 Suppose that $F$ is any
set of functions from $\bbr^n$ to $\{0,1\}$, for some fixed $n \in \bbn$.
    A function $f: \bbr^n \to \{0,1\}$
    is a {\em
    decision list} based on $F$ if it can be evaluated
    as follows, for some $k \in \bbn$, some functions $f_1, f_2, \dots, f_k \in F$,
     some $c_1, c_2, \dots, c_k \in \{0,1\}$, and all $y \in \bbr^n$: if $f_1(y) =
    1$, then $f(y)=c_1$; if not, we evaluate $f_2(y)$, and if $f_2(y) = 1$, then
    $f(y) = c_2$; otherwise we evaluate $f_3(y)$, and
    so on. If $y$ fails to
    satisfy any $f_i$ then $f(y)$ is given the default value
    $0$.
 We can regard a decision list
     based on $F$ as a
     finite sequence $$f = (f_1, c_1), \;
    (f_2, c_2), \ldots,\; (f_r, c_r), $$ such that $f_i
    \in F$ and $c_i \in \{0,1\}$ for  $1 \le i \le r$.
 The
    values of $f$ are defined by $f(y) =c_j$ where
 $j = \min\{i : f_i(y) = 1\}$, or $0$ if there are no $j$ such that $f_j(y)=1$.
We call each $f_i$ a {\em test}, and the pair $(f_i,c_i)$ a {\em
term} of the decision list. Decision lists were introduced by
\citet{Rivest}, in the context
    of learning Boolean functions (and where the tests were conjunctions of literals).

A function $t: \bbr^n \to \{0,1\}$ is a {\em threshold function} if
 there are $w \in \bbr^n$ and $\theta \in \bbr$ such that
$$t(x)=
\left\{\begin{array}{ll} 1&\mbox{if $\ip{w}{x}\ge\theta$}\\ 0
&\mbox{if $\ip{w}{x}<\theta$,}\end{array}\right.$$ where
$\ip{w}{x}$ is the standard inner product of $w$ and $x$. Thus,
$t(x)=\sgn(\ip{w}{x}-\theta)$,  where $\sgn(z)=1$ if $z \ge 0$ and
$\sgn(z)=0$ if $z<0$. Given such $w$ and $\theta$, we say that $t$
is represented by $[w, \theta]$ and we write  $t\rep [w, \theta]$.
The vector $w$ is known as the {\it weight vector}, and $\theta$
is known as the {\it threshold}.
 Geometrically, a threshold function is defined by a hyperplane: all points lying to
 one side of the plane and on the plane are given the value $1$, and all points on the other
 side are given the value $0$.

{\em Threshold decision lists} are decision lists in which the
tests are threshold functions. These have also been called {\em
neural} decision lists by \citet{Marchand} and {\em linear}
decision lists by \citet{Turan}.  Formally, a threshold decision
list
$$f=(t_1, c_1), (t_2, c_2), \dots, (t_r,c_r)$$
has each $t_i: \bbr^n \to \{0,1\}$ of the form
$t_i(x)=\sgn(\ip{w_i}{x}-\theta_i)$ for some $w_i \in \bbr^n$ and
$\theta_i \in \bbr$. The value of $f$ on $y \in \bbr^n$ is $f(y)
=c_j$ if
 $j = \min\{i : t_i(y) = 1\}$ exists, or $0$ otherwise (that is,
 if there are no $j$ such that $t_j(y)=1$).

There is a natural geometrical interpretation of the use of
threshold decision lists.
 Suppose we are given some
data points in $\bbr^n$, each one of which is labeled $0$ or $1$.
It is unlikely that the positive and negative points can be
separated by a hyperplane. However, we could use a hyperplane to
separate off a set of points all of the same classification
(either all are positive points or all are negative points). These
points can then be removed from consideration and the procedure
iterated until no points remain. This procedure is similar in
nature to one of \citet{Jeroslow}, but at each stage in his
procedure, only positive examples may be `chopped off' (not
positive {\em or} negative).

 If we consider threshold decision lists in which the
hyperplanes are parallel, we obtain a special subclass, known as
the {\em multilevel threshold functions}.  A {\em $k$-level
threshold function} $f$ is one that is representable by a
threshold decision list of length $k$ in which the test
hyperplanes are parallel to each other. Any such function is
defined by $k$ parallel hyperplanes, which divide $\bbr^n$ into
$k+1$ regions. The function assigns points in the same region the
same value, either $0$ or $1$.
 Without any loss, we may suppose that the
classifications assigned to points in neighboring regions are
different (for, otherwise, at least one of the planes is
redundant); thus, the classifications alternate as we traverse the
regions in the direction of the normal vector common to the
hyperplanes.

\subsection{Related Work}

The chopping procedure described above suggests that the use of
threshold decision lists is fairly natural, if an iterative
approach is to be taken to pattern classification. Other iterative
approaches---which proceed by classifying some points, removing
these from consideration, and proceeding recursively---have been
taken, using different types of base classifier. For example,
Magasarian's multisurface method~\citep{Mangasarian} finds, at
each stage, two parallel hyperplanes (as close together as
possible) such that the points not enclosed between the two planes
all have the same classification. It then removes these points and
repeats. This method may be regarded as constructing a decision
list in which the set of base functions $F$ are the indicator
functions of the complements of regions enclosed between two
parallel hyperplanes.

The focus of this paper is generalization error rather than
learning algorithms. The `chopping procedure' as we have described
it is a useful device to help us see that threshold decision lists
have a fairly natural geometric interpretation. However, the
algorithmic practicalities of implementing such a procedure
 have been investigated
by~\citet{Marchand}. They propose a method that relies on an
incremental approximation algorithm for the NP-hard problem of
finding at each stage a hyperplane that chops off as many
remaining points as possible (the `densest hyperplane problem').
Reports on the experimental performance of their method can be
found in~\citet{Marchand}.


Threshold decision lists are special types of {\em perceptron
decision trees}, decision trees in which the decision nodes
compute threshold functions. Such trees have been studied
by~\citet{STC} and~\cite{bennett}, where the importance of large
margins was emphasised. The techniques used to derive the results
of Section~\ref{sec:margintdls} extend those used to derive
generalization error bounds in those papers. \citet{bennett}
consider learning algorithms for perceptron decision trees:
specifically, they propose and test three variants of the OC1
perceptron decision tree learning algorithm~\citep{Murthy} that
aim for a large margin of separation at each decision node. The
theoretical generalization error bounds they derive apply to the
case in which a perceptron decision tree is produced that is
consistent with the training sample. The bounds for perceptron
decision trees presented in this paper improve upon the bounds
presented there and also apply, more generally, to the case in
which some empirical error (measured with respect to the margins)
is permitted.


The representational properties of threshold decision lists and
multilevel threshold functions have been studied by a number of
researchers, particularly in the context of Boolean functions. We
mentioned above the paper of~\citet{Jeroslow}. There, it is shown,
essentially, that any Boolean function can be realized as a
disjunction of threshold functions (and hence as a special type of
threshold decision list). The general problem of decomposing a
Boolean function into a disjunction of threshold functions has
been considered independently of any machine learning
considerations. \citet{Hammer} defined the {\em threshold number}
of a Boolean function to be the minimum $s$ such that $f$ is a
disjunction of $s$ threshold functions;  they and~\citet{Zuev}
obtained results on the threshold numbers of increasing Boolean
functions.
 Although any Boolean function can be expressed as a disjunction of threshold
 functions, threshold decision lists provide a more flexible representation.
 For instance, the parity function on $n$ variables (in which the
 output is $1$ precisely when the input to the function contains
 an odd number of entries equal to $1$) can be represented by a
 threshold decision list with $n$ terms; whereas, as observed
 by~\citet{Jeroslow}, the shortest decomposition of parity into a
 disjunction of threshold functions involves $2^{n-1}$ threshold functions.
  \citet{Turan}, by contrast, gave a specific example of a function with a
necessarily long threshold decision list representation.

Decision lists in which the tests are defined with respect to
points in the training sample have recently been investigated
by~\cite{Sokolova}. They considered the case where the base class
of tests consists of data-dependent balls (that is, the
characteristic functions of balls centered on data points, and
their complements). Additionally,~\cite{SCMhalf} considered the
use of disjunctions and conjunctions of functions constructed as
threshold functions, possibly in some `feature space'. Here,
examples $x \in X$ are transformed by a fixed function $\phi$ into
points of the feature space $\phi(X)$, and the classifiers used
are disjunctions or conjunctions
 of functions that, acting in feature
 space and on transformed examples $\phi(x)$, are
 threshold functions with weight vectors defined by three
 of the transformed examples.
  The problems studied in this paper are rather
 different: here, we consider general threshold decision lists
 (rather than just conjunctions or disjunctions), and the
 individual tests need not be data-dependent \citep[or, at least, not in
 the explicit way that they are in][]{SCMhalf}.

Multilevel threshold functions have been studied in a number of
papers~\citep[][for instance]{BohossianBruck,Olafsson,Takiyama}.
They originally were of interest as the sets of functions computed
by devices knows as {\em multilevel threshold
elements}~\citep{Takiyama}, generalizations of the linear
threshold elements. The `capacity' (in our terminology, the growth
function) has been of particular interest. \citet{Olafsson} gave
an upper bound on the capacity, correcting a claimed upper bound
of~\citet{Takiyama}. Subsequently, \citet{ngom} claimed to have
improved this bound, but were mistaken~\citep{partitions}. A bound
improving upon that of~\citet{Olafsson}, and which is used in this
paper, was given in~\cite{partitions}. Just as threshold decision
lists (and disjunctions of threshold functions) are `universal'
for Boolean functions, so too are the multilevel threshold
functions. \citet{BohossianBruck} observed that any Boolean
function can be realized as a multilevel threshold function.
(Specifically, they showed that every Boolean function is a
 $2^n$-level threshold function, an appropriate weight-vector
 being $w=(2^{n-1},2^{n-2}, \dots, 2,1)$. For that reason,
 they paid particular attention to the question of
 whether a function can be computed by a multilevel threshold function
 where the number of levels is polynomial.)
 Functions similar to multilevel threshold functions have also been of interest in
  multiple-valued logic~\citep{OP,ngom} where, instead of
  classification labels alternating between $0$ and $1$, a
  partition by $k$ parallel planes defines a $(k+1)$-valued
  function.


\section{Generalization Error}
\label{sec:model}

 Following a form of the PAC model of computational learning theory
\citep[see][]{AnthonyBiggs,Vapnik,BEHW}, we assume that labeled
data points $(x,b)$ (where $x \in \bbr^n$ and $b \in \{0,1\}$)
have been generated randomly (perhaps from some larger corpus of
data) according to a fixed probability distribution $P$ on
$Z=\bbr^n \times \{0,1\}$. (Note that this includes as a special
case the situation in which $x$ is drawn according to a fixed
distribution $\mu$ on $\bbr^n$ and the label $b$ is then given by
$b=t(x)$ where $t$ is some fixed function.) Thus, if there are $m$
data points, we may regard the data set as a {\em sample}
$\ve{s}=((x_1,b_1), \dots, (x_m,b_m)) \in Z^m$, drawn randomly
according to the product probability distribution $P^m$. Suppose
that $H$ is a set of functions from $X$ to $\{0,1\}$. Given any
function $f \in H$, we can measure how well $f$ matches the sample
$\ve{s}$ through its {\em sample error},
$$\er_\ve{s}(f)=\frac{1}{m}|\{i: f(x_i) \neq b_i\}|,$$ (the proportion of points in the
sample incorrectly classified by $f$). An appropriate measure of how well $f$ would
perform on further examples is its {\em error},
$$\er_P(f)=P\left(\{(x,b) \in Z: f(x) \neq b\}\right),$$
 the probability that a further randomly drawn labeled data point would be
 incorrectly classified by $f$.

 Much effort has gone into obtaining high-probability bounds on $\er_P(f)$ in terms of
 the sample error. A typical result would state that, for all $\delta \in (0,1)$, with
 probability at least $1-\delta$, for all $h \in H$,
 $\er_P(h)<\er_s(h)+\epsilon(m,\delta)$, where $\epsilon(m,\delta)$ (known as a {\em
 generalization
 error bound}) is decreasing in
 $m$ and $\delta$.
 Such results can be derived using uniform convergence theorems from probability
 theory~\citep{VC,Pollard,Dudley}, in which case $\epsilon(m,\delta)$ would typically
 involve the growth function \citep[see][]{VC,BEHW,Vapnik,ab}. We
 indicate in the next section how this may be done for threshold
 decision lists.

 Recently, emphasis has been placed in
practical machine learning techniques such as Support Vector
Machines \citep[see][for instance]{Cristianini} on `learning with
a large margin'. \citep[See][for
example]{Bartletteditedbook,ab,fli,SRM}.
 Broadly speaking, the rationale behind margin-based
generalization error bounds is that if a classifier has managed to
achieve a `wide' separation between (most of) the points of
different classification, then this indicates that it is a good
classifier, and it is possible that a better (that is, smaller)
generalization error bound can be obtained. The classical example
of this is linear separation, where the classifier is a linear
threshold function. If we have found a linear threshold function
that classifies the points of a sample correctly {\em and},
moreover, the points of opposite classifications are separated by
a wide margin (so that the hyperplane achieves not just a correct,
but a `definitely' correct classification), then this function
might be a better classifier of future, unseen, points than one
which `merely' separates the points correctly, but with a small
margin. In Section~\ref{sec:margintdls}, we apply such ideas to
threshold decision lists.


 \section{Generalization Bounds Based on the Growth Function}
\label{sec:PAC}
 In this section, we use some by-now
classical techniques of computational or statistical learning
theory to bound the generalization error.

\subsection{Bounding the Error}

 The {\em growth function} of a set of
functions $H$ mapping from $X=\bbr^n$ to $\{0,1\}$ is defined as
follow \citep{BEHW,VC}. Let $\Pi_H: \bbn \to \bbn$ be given by
$$\Pi_H(m)=\max\{ |H\rest{S}| : S \subseteq X, |S|=m\},$$
where $H\rest{S}$ denotes $H$ restricted to domain $S$. Note that
$\Pi_H(m) \le 2^m$ for all $m$. The key probability results we
employ are the following bounds, due respectively to \citet{VC}
and \citet{BEHW} \citep[see also][]{ab}: for any $\epsilon \in
(0,1)$,
$$P^m\left(\{s \in Z^m: \mbox{\rm there exists}\; f \in H, \; \er_P(f)\ge  \er_s(f)+\epsilon\}\right)
<4\,\Pi_H(2m)\,e^{-m\epsilon^2/8},$$ and, for $m \ge 8/\epsilon$,
$$P^m\left(\left\{s \in Z^m: \mbox{\rm there exists}\; f \in H, \;
\er_s(f)=0\;\mbox{\rm and}\; \er_P(f)\ge \epsilon \right\}\right)
<2\,\Pi_H(2m)\,2^{-\epsilon m/2}.$$
 Thus, we can obtain (probabilistic) bounds on the error $\er_P(f)$ of a function
  from a class $H$ when we know something about the growth function of $H$.

\subsection{Growth Function Bounds}

 We first consider the
set of
 threshold decision lists on $\bbr^n$ with some number $k$ of terms.
 (So, the length of the
 list is no more than $k$.)

 \begin{theorem} \label{thm:tdlgrowth} Let $H$ be the set of threshold decision lists
 on $\bbr^n$
 with $k$ terms, where $n,k \in \bbn$. Then
 $$\Pi_H(m) <4^{k}\left(\sum_{i=0}^n {m-1 \choose i}\right)^{k}.$$
 \end{theorem}

 \begin{proof} Let $S$ be any  set of $m$ points in $\bbr^n$.
 Suppose we have two decision lists $$f=(f_1,c_1), \dots,
 (f_k,c_k),\;\;
 g=(g_1,d_1), \dots, (g_k, d_k)$$ in $H$, where the $f_i$ and $g_j$ are threshold
 functions on $\bbr^n$.
  Clearly, $f$ and $g$ will agree on all points of $S$ if
  (i) $c_i=d_i$ for each $i$ and (ii) $f_i(x)=g_i(x)$ for all $x \in S$.
   For fixed $i$, condition (ii) is
 an equivalence relation among threshold functions. The
  number of equivalence classes is $|K\rest{S}|$ where $K$ is the set
 of threshold functions. This is bounded by $\Pi_K(m)$, which, it
 is known~\citep{Cover,BEHW,ab}, is bounded above as follows:
 $$\Pi_K(m) \le 2\sum_{i=0}^n {m-1 \choose i}.$$
 We can therefore upper bound $|H\rest{S}|$ as follows:
 $$|H\rest{S}| \le 2^k \left(2\,\sum_{i=0}^n {m-1 \choose i}\right)^{k}.$$
 Here, the first $2^k$ factor corresponds to the number of possible
sequences of $c_i$
 and the remaining factor bounds the number of ways of choosing an equivalence class (with
 respect to $S$) of
 threshold functions,
 for each $i$ from $1$ to $k$.
 \end{proof}

There is a useful connection between certain types of decision
list and threshold functions. We say that a decision list defined
on $\{0,1\}^n$ is a {\em $1$-decision list} if the Boolean
function in each test is given by a formula that is a single
literal. (So, for each $i$, there is some $l_i$ such that {\em
either} $f_i(y)=1$ if and only if $y_{l_i}=1$, {\em or} $f_i(y)=1$
if and only if $y_{l_i}=0$.) Then, it is known~\citep{Ehrenfeucht}
\citep[see also][]{labeled,siambook} that any $1$-decision list is
a threshold function. In an easy analogue of this, any threshold
decision list is a threshold function of threshold
functions~\citep{siambook}. But a threshold function of threshold
functions is nothing more than a two-layer threshold network, one
of the simplest types of artificial neural network. (A similar
observation was made by \citet{Marchand} and
\citet{MarchandGoleaRujan}, who construct a `cascade' network from
a threshold decision list.) So another way of bounding the growth
function of threshold decision lists is to use this fact in
combination with some known bounds~\citep{BaumHaussler,ab} for the
growth functions of linear threshold networks. This gives a
similar, though slightly looser, upper bound.

To bound the growth function of the subclass consisting of
$k$-level threshold functions, we use a result
from~\citep{partitions}, which shows that the number of ways in
which a set $S$ of $m$ points can be partitioned by $k$ parallel
hyperplanes is at most $\displaystyle{\sum_{i=0}^{n+k-1}{km
\choose i}.}$ (For fixed $n$ and $k$, this bound
 is tight to within a constant, as a function of $m$.)
 Noting that we may assume adjacent regions to have
different labels, there corresponds to each such partition at most
two $k$-level threshold functions (defined on the domain
restricted to $S$) and we therefore have the following bound.

\begin{theorem} \label{thm:mltgrowth}
Let $H$ be the set of $k$-level threshold functions on $\bbr^n$.
Then
$$\Pi_H(m) \le 2\,\sum_{i=0}^{n+k-1}{km \choose i}.$$
\end{theorem}


\subsection{Generalization Error Bounds}

Combining the results of the previous two subsections, we can
obtain the following generalization error bounds.

 \begin{theorem} \label{thm:tdlmlt}
Suppose that $n$ and $k$ are fixed positive integers and that $s$
is a sample of $m$ labeled points $(x,b)$ of $Z=\bbr^n\times
\{0,1\}$, each generated at random according to a fixed
probability distribution $P$ on $Z$.  Let $\delta$ be any positive
number less than one. Then the following hold with probability at
least $1-\delta$:
\begin{enumerate} \item If $f$ is a threshold decision list with $k$ terms,
then
 the error $\er_P(f)$ of $f$ and its sample error on $s$, $\er_s(f)$ are such that
 $$\er_P(f) < \er_s(f)+ \sqrt{\frac{8}{m}\left(2k \ln 2+nk \ln\left(\frac{e(2m-1)}{n}\right)
 +\ln\left(\frac{4}{\delta}\right)\right)}.$$
 \item If $f$ is a $k$-level threshold function, then
 $$\er_P(f) < \er_s(f)+ \sqrt{\frac{8}{m}\left((n+k-1)\ln\left(\frac{2emk}{n+k-1}\right)
 +\ln\left(\frac{4}{\delta}\right)\right)}.$$
 \end{enumerate}
 \end{theorem}


\begin{proof} We approximate the growth function of the
class of $k$-term threshold decision lists by $$\Pi_H(m) \le
4^{k}\left(\sum_{i=0}^n {m-1 \choose
i}\right)^{k}<4^{k}\left(\frac{e(m-1)}{n}\right)^{nk},$$
 for $m>n$. Similarly, when $H$ is the class of $k$-level
 threshold functions,
 $$\Pi_H(m) \le 2\,\sum_{i=0}^{n+k-1}{km \choose i}
 < 2\left(\frac{emk}{n+k-1}\right)^{n+k-1},$$ for $m \ge n+k.$
 The first part of the theorem is trivially true if $m \le n$ (since then the stated
 upper bound on the error is at least $1$). If $m > n$, then
 $$\epsilon_0=\sqrt{\frac{8}{m}\left(2k \ln 2+nk \ln\left(\frac{e(2m-1)}{n}\right)
 +\ln\left(\frac{4}{\delta}\right)\right)} \ge
 \sqrt{\frac{8}{m}\left(\ln\left(\frac{4\,\Pi_H(2m)}{\delta}\right)\right)},$$
 and so
 $$ P^m\left(\{s \in Z^m: \mbox{\rm there exists}\; f \in H, \;
\er_P(f)\ge  \er_s(f)+\epsilon_0\}\right) <
4\,\Pi_H(2m)\,e^{-m\epsilon_0^2/8}\le \delta.$$ Thus, with
probability at least $1-\delta$, for all $f \in H$, $\er_P(f)<
\er_s(f)+\epsilon_0$. The second part follows similarly. It is
trivial for $m <n+k$ and it follows for $m \ge n+k$ on observing
that, for $H$ the class of $k$-level threshold functions,
$$\epsilon_0'=\sqrt{\frac{8}{m}\left((n+k-1)\ln\left(\frac{2emk}{n+k-1}\right)
 +\ln\left(\frac{4}{\delta}\right)\right)} \ge
 \sqrt{\frac{8}{m}\left(\ln\left(\frac{4\,\Pi_H(2m)}{\delta}\right)\right)}.$$
\end{proof}

 For threshold decision lists that are consistent with a
training sample, the following tighter bounds can be used.

\begin{theorem} \label{thm:extension}
Suppose that $k$ and $n$ are fixed positive integers and that $s$
is a sample of $m$ labeled points $(x,b)$ of $Z=\bbr^n\times
\{0,1\}$, each generated at random according to a fixed
probability distribution $P$ on $Z$.  Let $\delta$ be any positive
number less than one. Then the following hold with probability at
least $1-\delta$:
\begin{enumerate} \item If $f$ is a threshold decision list with
$k$ terms and $f$ is consistent with $s$ (so that $\er_s(f)=0$),
then
 $$\er_P(f) <\frac{2}{m}\left(2k +nk \log_2\left(\frac{e(2m-1)}{n}\right)
 +\log_2\left(\frac{2}{\delta}\right)\right).$$
 \item If $f$ is a $k$-level threshold function and $f$ is
consistent with $s$, then
 $$\er_P(f) < \frac{2}{m}\left((n+k-1)\log_2\left(\frac{2emk}{n+k-1}\right)
 +\log_2\left(\frac{2}{\delta}\right)\right),$$ for $n+k\ge 3$.
 \end{enumerate}
 \end{theorem}

\begin{proof} We use the growth function approximations
of the proof of Theorem~\ref{thm:tdlmlt}. For the class of
threshold decision lists with $k$ terms, and for $m>n$,
$$\epsilon_0=\frac{2}{m}\left(2k +nk \log_2\left(\frac{e(2m-1)}{n}\right)
 +\log_2\left(\frac{2}{\delta}\right)\right) \ge
 \frac{2}{m}\log_2\left(\frac{2\,\Pi_H(2m)}{\delta}\right),$$
 and so
$$P^m\left(\left\{s \in Z^m: \mbox{\rm there exists}\; f \in H, \;
\er_s(f)=0\;\mbox{\rm and}\; \er_P(f)\ge \epsilon_0
\right\}\right) <2\,\Pi_H(2m)\,2^{-\epsilon_0 m/2}=\delta.$$
(Also, for $m \le n$, the bound trivially holds.)
 The second part follows similarly on noting that,
for the class of $k$-level threshold functions, if $m\ge n+k$,
then
$$\epsilon_0'=\frac{2}{m}\left((n+k-1)\log_2\left(\frac{2emk}{n+k-1}\right)
 +\log_2\left(\frac{2}{\delta}\right)\right) \ge
 \frac{2}{m}\log_2\left(\frac{2\,\Pi_H(2m)}{\delta}\right).$$ The
 bound is trivially true for $m <n+k$; and, for $m \ge n+k$, the
 condition $n+k \ge 3$ ensures that $m \ge 8/\epsilon_0$, so that
 the bound of~\citet{BEHW} applies.
\end{proof}

 The following variations of these results, in which $k$ is not prescribed in
advance, are perhaps more useful, since one does not necessarily
know {\em a priori} how many terms a suitable threshold decision
list will have.


\begin{theorem} \label{thm:variable}
With the notations as above, and for $n \ge 3$, the following
holds with probability at least $1-\delta$:
\begin{enumerate}
\item If $f$ is a threshold decision list, then
 $$\er_P(f) < \er_s(f)+
 \sqrt{\frac{8}{m}\left(2k \ln 2+nk \ln\left(\frac{e(2m-1)}{n}\right)
 +\ln\left(\frac{14k^2}{\delta}\right)\right)},$$
 where $k$ is the number of terms of $f$.
 \item If $f$ is a multilevel threshold function, then
   $$\er_P(f) <
 \er_s(f)+ \sqrt{\frac{8}{m}\left((n+k-1)\ln\left(\frac{2emk}{n+k-1}\right)
 +\ln\left(\frac{14k^2}{\delta}\right)\right)},$$ where $k$ is the number of levels (terms) of $f$.
 \item If $f$ is a threshold decision list
and $\er_s(f)=0$, then
 $$\er_P(f) <\frac{2}{m}\left(2k +nk \log_2\left(\frac{e(2m-1)}{n}\right)
 +\log_2\left(\frac{4k^2}{\delta}\right)\right)$$ where $k$ is the number of
 terms of $f$;
\item If $f$ is a multilevel threshold function and $\er_s(f)=0$,
then
 $$\er_P(f) < \frac{2}{m}\left((n+k-1)\log_2 \left(\frac{2emk}{n+k-1}\right)
 +\ln\left(\frac{4k^2}{\delta}\right)\right),$$
where $k$ is the number of terms of $f$. \end{enumerate}
\end{theorem}

\begin{proof} We prove the last part, the other three
being very similar. We use a well-known technique often found in
discussions of `structural risk minimisation'
 and model selection~\citep[see][for instance]{Vapnikoldbook,SRM,ab}.
  From Theorem~\ref{thm:extension}, for any $\delta \in (0,1)$
 and any $k \in \bbn$, if $n+k \ge 3$, then the probability $p_k$ that there is
a $k$-level threshold function  $f$  such that $\er_s(f)=0$ and
$$\er_P(f) < \epsilon'_k =\frac{2}{m}\left((n+k-1)\log_2\left(\frac{2emk}{n+k-1}\right)
 +\ln\left(\frac{2 \pi^2 k^2}{6\delta}\right)\right)$$ is less
 than $(\delta/k^2)(6/\pi^2)$.
The fact that $n \ge 3$ ensures that $n+k \ge 3$.
 Hence the probability that, for some $k \in
 \bbn$, there is $f \in H$ with $\er_P(f) \ge
 \er_s(f)+\epsilon_k$ is less than $\sum_{k=1}^\infty p_k< \delta(6/\pi^2)\sum_{k=1}^\infty(1/k^2)=\delta$.
 The result follows on noting that $2\pi^2/6<4$.
\end{proof}

\section{Margin-Based Error Bounds for Threshold Decision Lists}

\label{sec:margintdls}


We now derive generalization error bounds dependent on the size of
margins. The key qualitative difference between these bounds and
those of Section~\ref{sec:PAC} is that the margin-based bounds are
dimension-independent, in that they do not depend on $n$.

\subsection{Definition of Margin Error}

 Suppose that $h$ is a threshold decision list, with $k$
terms, and suppose that the tests in $h$ are the threshold
functions $t_1, t_2, \dots, t_k$, and that $t_i$ is represented by
weight vector $w_i$ and threshold $\theta_i$. Assume also, without
any loss of generality, that $\|w_i\|=1$ for each $i$. We say that
$h$ classifies the labeled example $(x,b)$ (correctly, and) with
margin $\gamma>0$ if $h(x)=b$ and, for all $1 \le i\le k$,
$|\ip{w_i}{x}-\theta_i| \ge \gamma$. In other words, $h$
classifies $x$ with margin $\gamma$ if, overall, the
classification of $x$ given by the threshold decision list $h$ is
correct and, additionally, $x$ is distance at least $\gamma$ from
{\em all} of the $k$ hyperplanes
 defining $h$.\footnote{The assumption that $\|w_i\|=1$ ensures that the
 interpretation in terms of distance is valid; for, in this case
 the `functional' and `geometric' margins coincide. See the paper by \citet{Cristianini}.}
 Note that we do not simply stipulate that $x$ is distance at
 least $\gamma$ from the single hyperplane involved in the first test that $x$ passes: rather,
 we require $x$ to be distance at least $\gamma$ from all of the hyperplanes.
 (In this sense, the classification given to $x$ by $h$ is not just correct,
 but `definitely' correct.)
 Given a labeled sample $\ve{s}=((x_1,b_1), \dots, (x_m,b_m))$, the
error of $h$ on $\ve{s}$ at margin $\gamma$, denoted
$\er^\gamma_\ve{s}(h)$, is the proportion of labeled examples in
$\ve{s}$ that are {\em not} classified by $h$ with margin
$\gamma$. Thus, $\er^\gamma_\ve{s}(h)$ is the fraction of the
sample points that are either misclassified by $h$, or are
classified correctly but are
 distance less than $\gamma$ from one of the planes.

 Following the analysis of perceptron decision trees in~\citet{STC} and
\citet{bennett}, we may want to consider separate margin
parameters $\gamma_1, \gamma_2, \dots, \gamma_k$ for each of the
$k$ terms of the decision list. We have the following definition.

\begin{definition} \label{def:marginerror} Suppose $h=(t_1,c_1), \dots, (t_k,c_k)$
 is a threshold decision list, where $t_i$ is represented by weight vector $w_i$ and threshold
 $\theta_i$, where $\|w_i\|=1$. Given $\Gamma=(\gamma_1,\gamma_2, \dots, \gamma_k)$,
  we say that $h$ classifies the
labeled example $(x,b)$ (correctly and) with margin $\Gamma$ if
$h(x)=b$ and, for all $1 \le i\le k$, $|\ip{w_i}{x}-\theta_i| \ge
\gamma_i$. We define $\er^\Gamma_\ve{s}(h)$ to be the proportion
of labeled examples in the sample $s$ that are not classified with
margin $\Gamma$.
\end{definition}

 \subsection{Covering Numbers}

A useful tool in the derivation of margin-based generalization
error bounds is the {\em covering number} of a class of real
functions. Suppose that $F:X \to \bbr$ is a set of real-valued
functions with domain $X$, and that $x=(x_1,x_2,\dots,x_m)$ is an
unlabeled sample of $m$ points of $X$. Then, for $\epsilon>0$, $C
\subseteq F$ is an {\em $\epsilon$-cover of $F$ with respect to
the $d_\infty^x$-metric} if for all $f \in F$ there is $\hat{f}
\in C$ such that $d_\infty^x(f,\hat{f})<\epsilon$, where, for $f,g
\in F$,  $$d_\infty^x(f,g)=\max_{1 \le i \le m}|f(x_i)-g(x_i)|.$$
 (Coverings with respect to other metrics derived from $x$ can also be defined, but
 this paper needs only the present definition.)
 The class $F$ is said to be totally bounded if it has a finite $\epsilon$-cover with respect
 to the $d_\infty^x$ metric, for
 all $\epsilon>0$ and all $x \in X^m$ (for all $m$).
 In this case, given $x \in X^m$,
 we define the {\em $d^x_\infty$-covering number}
 $\cover(F,\epsilon,x)$ to be the minimum cardinality of an $\epsilon$-cover of $F$
 with respect to the $d_\infty^x$-metric. We then define the (uniform) {\em $d_\infty$-covering
 numbers} $\cover(F,\epsilon,m)$ by
 $$\cover(F,\epsilon,m)=\sup\{\cover(F,\epsilon,x): x \in X^m\}.$$
 Many bounds on covering numbers for specific classes have been
 obtained
 \citep[see][for an overview]{ab}, and general bounds on covering numbers in terms of a
 generalization of the VC-dimension, known as the {\em fat-shattering dimension}, have
 been given~\citep{Alon}.

 In this paper, we use a recent
bound of \citet{zhang} for the $d_\infty$-covering numbers of
bounded linear mappings.
 For $R>0$, let $B_R=\{x \in \bbr^n: \|x\| \le R\}$ be the closed ball
in $\bbr^n$ of radius $R$, centred on the origin. For $w \in
\bbr^n$, let $f_w: B_R \to \bbr$ be given by $f_w(x)=\ip{w}{x}$,
and let $$L_R=\{f_w: w \in \bbr^n, \|w\| =1\}.$$ \citet{zhang} has
shown that
\begin{eqnarray}\label{eqn:zhang} \log_2\cover(L_R, \epsilon, m) \le
36\,\frac{R^2}{\epsilon^2} \log_2\left(2\left\lceil
4R/\epsilon+2\right\rceil m+1\right).\end{eqnarray} One thing of
note is that this bound is dimension-independent: it does not
depend on $n$. This bound differs from previous
bounds~\citep{Bartlett,ab,SRM} for the logarithm of the
$d_\infty$-covering numbers in that it involves a factor of order
$\ln m$ rather than $(\ln m)^2$.\footnote{Previous approaches to bounding
the $d_\infty$-covering numbers first bounded the {\em
fat-shattering dimension} and then used a result of \citet{Alon}
that relates the covering numbers to the fat-shattering dimension.
An additional $\ln m$ factor appears when this route is taken.}



\subsection{Margin-based Bounds}

Following a method used by~\citet{STC} and \citet{bennett},
together with the covering number bound of \citet{zhang}, we can
obtain the following two results.
 (In these results, it simplifies matters to
assume that $R \ge 1$ and $\gamma_i \le 1$, but it will be clear
how to modify them otherwise.)

\begin{theorem} \label{thm:tdlnonzero}
 Suppose $R\ge 1$ and $Z=B_R \times \{0,1\}$, where $B_R=\{x \in
\bbr^n: \|x\| \le R\}$. Fix $k \in \bbn$ and let $H$ be the set of
all threshold decision lists with $k$ terms, defined on domain
$B_R$. Let $\gamma_1, \gamma_2, \dots, \gamma_k \in (0,1]$ be
given. Then, with probability at least $1-\delta$, the following
holds for $s \in Z^m$: if $h \in H$ and
$\Gamma=(\gamma_1,\gamma_2, \dots, \gamma_k)$, then
$$\er_P(h)< \er_s^\Gamma(h)+\sqrt{\frac{8}{m}\left(576\,R^2 D(\Gamma)
\ln\left(8m\right)+ \ln\left(\frac{2}{\delta}\right)+k\right)},$$
where $D(\Gamma)=\sum_{i=1}^k (1/\gamma_i^2)$ and where the margin
error $\er_s^\Gamma(h)$ is as in Definition~\ref{def:marginerror}.
\end{theorem}


\begin{proof} The proof extends a technique of
\citet{STC} and \citet{bennett} (where the case of zero margin
error was the focus), and is motivated by proofs of
\citet{ab,fli}, \citet{Bartlett}, \citet{SRM}, which in turn are
based on the original work of~\citet{VC}.

Given $\Gamma=(\gamma_1, \gamma_2,\dots, \gamma_n)$, it can fairly easily be shown
that if
$$Q=\{\ve{s} \in Z^m: \exists h \in H \;{\rm with}\; \er_P(h)\ge
\er^\Gamma_\ve{s}(h)+\epsilon\}$$ and
$$T=\{(s,s') \in Z^m \times Z^m: \exists h \in H \;{\rm with}\; \er_{s'}(h)\ge
\er^\Gamma_{s}(h)+\epsilon/2\},$$ then for $m \ge 2/\epsilon^2$,
$P^m(Q) \le 2\,P^{2m}(T).$ For, we have
\begin{eqnarray*} P^{2m}(T) &\ge & P^{2m}\left(\exists h\in H: \er_P(h)\ge
\er_s^\Gamma(h)+\epsilon \;\;{\rm and}\; \;\er_{s'}(h) \ge
\er_P(h)-\epsilon/2\right) \\
& =& \int_Q P^m\left(\left\{s': \exists h \in H, \er_P(h)\ge
\er_s^\Gamma(h)+\epsilon \;\; {\rm and}\; \er_{s'}(h) \ge
\er_P(h)-\epsilon/2\right\}\right)\,dP^m(s) \\
& \ge & \frac{1}{2} P^m(Q),\end{eqnarray*} for $m \ge
2/\epsilon^2$, where the final inequality follows from
$P^m(\er_{s'}(h) \ge \er_P(h)-\epsilon/2) \ge 1/2$, for any $h \in
H$, true by Chebyshev's inequality.

Let $G$ be the permutation group (the `swapping group') on the set
$\{1,2,\dots,2m\}$ generated by the transpositions $(i,m+i)$ for
$i=1,2,\dots, m$. Then $G$ acts on $Z^{2m}$ by permuting the
coordinates: for $\sigma \in G$, $\sigma (z_1,z_2,\dots, z_{2m})=
(z_{\sigma(1)}, \dots, z_{\sigma(m)})$. Now, by invariance of
$P^{2m}$ under the action of $G$, $P^{2m}(T)\le \max\{\pr(\sigma z
\in T): z \in Z^{2m}\},$ where $\pr$ denotes the probability over
uniform choice of $\sigma$ from $G$. (See~\citeauthor{VC},~\citeyear{VC}, and
\citeauthor{ab},~\citeyear{ab}, for instance.)

Given a threshold decision list on $B_R \subseteq \bbr^n$, each
test is of the form $f_i \rep [w_i,\theta_i]$; that is, the test
is passed if and only if $\ip{w_i}{x}\ge \theta_i$. An equivalent
functionality is obtained by using inputs in $B_R$ augmented by
$-1$, and using {\em homogeneous} threshold functions of $n+1$
variables; that is, ones with zero threshold. So any threshold
decision list of length $k$ on $B_R$ can be realized as one on
$\bbr^{n+1}$, defined on the subset $B_R \times \{-1\}$, and with
homogeneous threshold functions as its tests.  Fix $z \in Z^{2m}$
and let $x=(x_1,x_2,\dots, x_{2m}) \in X^{2m}$
 be the corresponding vector of $x_i$, where
 $z_i=(x_i,b_i)$. For $i$ between $1$ and
$k$, let $C_i$ be a minimum-sized $\gamma_i/2$-cover of $L$ with
respect to the $d^x_\infty$ metric, where $L$ is the set of linear
functions $x\mapsto \ip{w}{x}$ for $\|w\|=1$, defined on the
domain $D=\{(x,-1): x \in \bbr^n, \|x\| \le R\}$. Note that if $x
\in \bbr^n$ satisfies $\|x\| \le R$, then the corresponding
$(x,-1)$ has length at most $\sqrt{R^2+1}$. So, by the covering
number bound~(\ref{eqn:zhang}),
\begin{eqnarray} \label{eqn:cibound} \log_2|C_i| \le
\frac{144(R^2+1)}{\gamma_i^2}\log_2\left(\left(\frac{32\sqrt{R^2+1}}{\gamma_i}+
14\right)m\right)\le
\frac{288R^2}{\gamma_i^2}\log_2\left(\frac{60Rm}{\gamma_i}\right).\end{eqnarray}
Suppose that $h=(f_1,c_1),\dots, (f_k,c_k)$ is a threshold
decision list with $k$ homogeneous threshold tests, defined on
$D$. Denote the tests of the list by $f_1,f_2, \dots, f_k$, where
$f_i$ corresponds to weight vector $w_i \in \bbr^{n+1}$. For each
$i$, let $\hat{f}_i \in C_i$ satisfy
$d^x_\infty(f_i,\hat{f}_i)<\gamma_i/2$, let $\hat{w}_i$ be the
corresponding weight vector, and let $\hat{h}$ be the threshold
decision list obtained from $h$ by replacing each $f_i$ by
$\hat{f}_i$, leaving the $c_i$ unchanged. The set $\hat{H}$ of all
possible such $\hat{h}$ is of cardinality at most
$2^k\prod_{i=1}^k|C_i|$ (where the $2^k$ factor corresponds to the
choices of the values $c_i$). Suppose that $\sigma z=(s,s') \in T$
and that $\er_{s'}(h)\ge \er^\Gamma_{s}(h)+\epsilon/2$. Let
$\Gamma/2=(\gamma_1/2, \dots, \gamma_k/2)$. Then, because for all
$1\le j \le 2m$ and all $1\le i \le k$,
$|\ip{w_i}{x_j}-\ip{\hat{w}_i}{x_j}| <\gamma_i/2,$ it can be seen
that $\er^{\Gamma/2}_{s'}(\hat{h})\ge \er_{s'}(h)$ and
$\er_{s}^{\Gamma}(h) \ge \er_{s}^{\Gamma/2}(\hat{h})$. Explicitly
(denoting any given $x_i$ by $x$),
$\er^{\Gamma/2}_{s'}(\hat{h})\ge \er_{s'}(h)$ follows from the
observation that if $\ip{w_i}{x}< 0$, then $\ip{\hat{w}_i}{x}
<\gamma_i/2$ and if $\ip{w_i}{x}> 0$, then $\ip{\hat{w}_i}{x} >
-\gamma_i/2$; and $\er_{s}^{\Gamma}(h) \ge
\er_{s}^{\Gamma/2}(\hat{h})$ follows from the facts that if
$\ip{\hat{w}_i}{x}<\gamma_i/2$ then $\ip{w_i}{x}<\gamma_i$, and if
$\ip{\hat{w}_i}{x}>-\gamma_i/2$ then $\ip{w_i}{x}>-\gamma_i$. So,
$\er^{\Gamma/2}_s(\hat{h})\ge
\er^{\Gamma/2}_s(\hat{h})+\epsilon/2$, and therefore, for any $z
\in Z^{2m}$, $$\pr\left(\sigma z \in T\right) \le \pr\left(\sigma
z \in
 \bigcup_{\hat{h} \in \hat{H}} S(\hat{h})\right),$$
 where
 $\displaystyle{S(\hat{h})=\{(s,s') \in Z^{2m}: \er^{\Gamma/2}_{s'}(\hat{h}) \ge
 \er^{\Gamma/2}_s(\hat{h})+\epsilon/2\}.}$
 Fix $\hat{h} \in \hat{H}$ and let $v_i=0$ if $\hat{h}$ classifies $z_i$ with
  margin at least $\Gamma/2$, and
 $1$ otherwise. Then
 $$\pr\left(\sigma z \in S(\hat{h})\right)=
 \pr\left(\frac{1}{m}\sum_{i=1}^m (v_{m+i}-v_i) \ge \epsilon/2\right)
 =\pr\left(\frac{1}{m}\sum_{i=1}^m \varepsilon_i |v_i-v_{m+i}| \ge
 \epsilon/2\right),$$ where the $\varepsilon_i$ are independent (Rademacher) $\{-1,1\}$ random
 variables, each taking value $1$ with probability $1/2$, and where the last
 probability is over the joint distribution of the $\varepsilon_i$. Hoeffding's
 inequality bounds this probability by
$\exp(-\epsilon^2m/8)$. (See~\citeauthor{ab},~\citeyear{ab}, for
 instance, for details.)

 We therefore have
 $$ \pr\left(\sigma z \in
 \bigcup_{\hat{h} \in \hat{H}} T(\hat{h})\right)\le \sum_{\hat{h} \in \hat{H}} \pr\left(\sigma z \in
 T(\hat{h})\right)\le |\hat{H}| \exp(-\epsilon^2
 m/8),$$ which gives
$$P^m(Q) \le 2\,P^{2m}(T) \le 2\,2^k\,\prod_{i=1}^k|C_i|\exp(-\epsilon^2m/8).$$
Using the bound~(\ref{eqn:cibound}),  we see that, provided
$$\epsilon \ge \epsilon_0=\sqrt{\frac{8}{m}\left(\sum_{i=1}^k
\frac{288R^2}{\gamma_i^2}\ln\left(\frac{60Rm}{\gamma_i}\right)+
\ln\left(\frac{2}{\delta}\right)+k\right)},
$$ (in which case we certainly also have $m \ge 2/\epsilon^2$)
then the probability of $Q$ is at most $\delta$. So, with probability at most
$1-\delta$, $\er_P(h)<\er^\Gamma_s(h)+\epsilon_0$ for all $h \in
H$. If, for each $i$, $m\ge R^2/\gamma_i^2$, then
$\ln(60Rm/\gamma_i)\le 2\ln(8m)$ and so, with probability at least
$1-\delta$, for all $h \in H$,
\begin{eqnarray} \label{eqn:bd1} \er_P(h)<
\er_s^\Gamma(h)+\sqrt{\frac{8}{m}\left(\sum_{i=1}^k
\frac{576R^2}{\gamma_i^2}\ln\left(8m\right)+
\ln\left(\frac{2}{\delta}\right)+k\right)}.\end{eqnarray} If,
however, for some $i$, $m< R^2/\gamma_i^2$, then the
bound~(\ref{eqn:bd1}) is trivially true (since the term under the
square root is greater than $1$). The result follows. \end{proof}

A tighter bound can be given when the margin error is zero, as
follows. (The bound involves $1/m$ rather than $1/\sqrt{m}$.)

\begin{theorem}\label{thm:tdlzero}  Suppose $R\ge 1$ and $Z=B_R \times \{0,1\}$,
where $B_R=\{x \in \bbr^n: \|x\| \le R\}$. Fix $k \in \bbn$ and let $H$ be the set of
all threshold decision lists with $k$ terms, defined on domain $B_R$. Let $\gamma_1,
\gamma_2, \dots, \gamma_k \in (0,1]$ be given. Then, with probability at least
$1-\delta$, the following holds for $s \in Z^m$: if $h$ is any threshold decision list
with $k$ terms, and $h$ classifies $s$ with margin $\Gamma=(\gamma_1, \dots,
\gamma_k)$, then
$$\er_P(h)< \frac{2}{m}\left(576\,R^2D(\Gamma)\log_2(8m)+
\log_2\left(\frac{2}{\delta}\right)+k\right)$$ where
$D(\Gamma)=\sum_{i=1}^k (1/\gamma_i^2)$.\end{theorem}

\begin{proof} This proof is
similar to that of Theorem~\ref{thm:tdlnonzero}. It uses, first,
the fact\footnote{For similar results, see \citet{VC,BEHW}; and \citet{ab}.} that if
$$Q=\{\ve{s} \in Z^m: \exists h \in H \;{\rm with}\; \er^\Gamma_\ve{s}(h)=0, \,
\er_P(h)\ge \epsilon\}$$ and $$T=\{\ve{(s,s')} \in Z^m \times Z^m:
\exists h \in H \;{\rm with}\; \er^\Gamma_\ve{s}(h)=0, \,
\er_{s'}(h)\ge \epsilon/2\},$$ then, for $m \ge 8/\epsilon$,
$P^m(Q) \le 2\,P^{2m}(T)$. This is so, because
\begin{eqnarray*} P^{2m}(T) &\ge &
P^{2m}\left(\exists h\in H: \er_s^\Gamma(h)=0, \;\;\er_P(h) \ge
\epsilon\;{\rm and}\;\;\er_{s'}(h)\ge
\epsilon/2 \right) \\
& =& \int_Q P^m\left(\left\{s': \exists h \in H,
\;\er_s^\Gamma(h)=0, \; \er_P(h)\ge \epsilon \;\; {\rm and}\;
\er_{s'}(h) \ge
\epsilon/2\right\}\right)\,dP^m(s) \\
& \ge & \frac{1}{2} P^m(Q),\end{eqnarray*} for $m \ge 8/\epsilon$.
The final inequality follows from the fact that if $\er_P(h)=0$,
then for $m \ge 8/\epsilon$, $P^m(\er_{s'}(h) \ge \epsilon/2) \ge
1/2$, for any $h \in H$, something that follows for $m \ge
8/\epsilon$ by Chebyshev's inequality or a Chernoff
bound~\citep[][for instance]{AnthonyBiggs}.
 As before,
 $P^{2m}(T)\le \max_{z \in Z^{2m}}\pr(\sigma z \in T),$ where $\pr$ denotes the
probability over uniform choice of $\sigma$ from the `swapping
group' $G$. A very similar argument to that given in the proof of
Theorem~\ref{thm:tdlmlt} establishes that for any $z \in Z^{2m}$,
$$\pr\left(\sigma z \in T\right) \le \pr\left(\sigma z \in
 \bigcup_{\hat{h} \in \hat{H}} S(\hat{h})\right),$$
 where
 $\displaystyle{S(\hat{h})=\{(s,s') \in Z^{2m}:  \er^{\Gamma/2}_\ve{\hat{s}}(h)=0,
 \, \er_{s'}^{\Gamma/2}(\hat{h})\ge
\epsilon/2\}.}$ Now, suppose $S(\hat{h}) \neq \emptyset$, so that
for some $\tau \in G$,
 $\tau z=(s,s') \in
 S(\hat{h})$, meaning that $\er^{\Gamma/2}_s(\hat{h})=0$ and
 $\er^{\Gamma/2}_{s'}(\hat{h})\ge \epsilon/2$.
 Then, by symmetry, $\pr\left(\sigma z \in S(\hat{h})\right)=\pr\left(\sigma(\tau
 z) \in S(\hat{h})\right)$. Suppose that
 $\er^{\Gamma/2}_{s'}(\hat{h})=r/m$, where $r \ge \epsilon m/2$ is
 the number of $x_i$ in $s'$ not classified with margin $\Gamma/2$
 by $\hat{h}$. Then those permutations $\sigma$ such that
 $\sigma(\tau z)\in S(\hat{h})$ are precisely those that `swap'
 elements other than these $r$, and there are $2^{m-r}\le
 2^{m-\epsilon m/2}$ such $\sigma$.
 It follows that, for each fixed $\hat{h} \in \hat{H}$,
 $$\pr\left(\sigma z \in S(\hat{h})\right)\le \frac{2^{m(1-\epsilon/2)}}{|G|}=
 2^{-\epsilon m/2}.$$
 The proof then proceeds as does the proof of
 Theorem~\ref{thm:tdlnonzero}, using the bound~(\ref{eqn:cibound}).
 \end{proof}

\subsection{Uniform Margin-based Bounds}

 One difficulty with Theorems~\ref{thm:tdlnonzero}
and~\ref{thm:tdlzero} is that the number, $k$, of terms, and the
margins $\gamma_i$ are specified {\em a priori}. A more useful
generalization error bound would enable us to choose, tune, or
observe these parameters after learning. We now derive such a
result.
 The approach we take to obtaining a `uniform' result of
this type differs from that taken by \citet{STC} and
\citet{bennett}, and gives a slightly better bound.

We first need a generalization of a result from \citep{Bartlett},
where the following is shown. Suppose $\p$ is any probability
measure and that
 $\{E(\alpha_1,\alpha_2,\delta): 0 < \alpha_1, \alpha_2,
  \delta \le 1\}$ is a set of events such that:
\begin{itemize}
\item for all $\alpha$, $\p(E(\alpha,\alpha,\delta)) \le \delta$,
\item if $0<\alpha_1\le \alpha \le \alpha_2<1$ and $0<\delta_1\le \delta\le 1$, then
 $E(\alpha_1,\alpha_2,\delta_1) \subseteq E(\alpha,\alpha,\delta)$.
\end{itemize}
Then $\displaystyle{\p\left(\bigcup_{\alpha \in (0,1]} E(\alpha/2,
\alpha, \delta \alpha/2)\right)\le \delta}$ for $0<\delta <1$.

We modify and extend this result as follows.

\begin{theorem} \label{thm:uniformize}
Suppose $\p$ is any probability measure, $k \in \bbn$, and that
 $$\{E(\Gamma_1,\Gamma_2,\delta): \Gamma_1,
\Gamma_2 \in (0,1]^k,
  \delta \le 1\}$$ is a set of events such that:
\begin{enumerate}
\item[(a)] for all $\Gamma \in (0,1]^k$,
$\p(E(\Gamma,\Gamma,\delta)) \le  \delta$, \item[(b)] $\Gamma_1
\le \Gamma \le \Gamma_2$ (component-wise) and $0<\delta_1\le
\delta\le 1$ imply $E(\Gamma_1,\Gamma_2,\delta_1) \subseteq
E(\Gamma,\Gamma,\delta)$.
\end{enumerate}
Then $$\p\left(\bigcup_{\Gamma \in (0,1]^k} E\left((1/2)\Gamma,
\Gamma, \delta c(\Gamma)\right)\right)\le \delta$$ for $0<\delta
<1$, where
$$c(\Gamma)=\left\{\prod_{i=1}^k\log_2\left(\frac{4}{\gamma_i}\right)\right\}^{-2}.$$
\end{theorem}

\begin{proof} Denoting by ${\bf u}=(1,1,\dots, 1)$ the
all-$1$ vector of length $k$, we have
\begin{eqnarray*} & &\p\left(\bigcup_{\Gamma \in (0,1]^k}
E\left((1/2)\Gamma, \Gamma, \delta c(\Gamma)\right)\right)\\&\le &
\p\left(\bigcup_{i_1, \dots,i_k=0}^\infty
\left\{E\left((1/2)\Gamma, \Gamma, \delta c(\Gamma)\right): {\rm
for\;}j=1,\dots,k, \gamma_j \in
\left(\left(\frac{1}{2}\right)^{i_j+1},
\left(\frac{1}{2}\right)^{i_j}\right]\right\}\right)
\\
&\le & \p\left(\bigcup_{i_1,\dots, i_k=0}^\infty
E\left(\left(\frac{1}{2}\right)^{i_1+1}\!\!{\bf u},\;
\left(\frac{1}{2}\right)^{i_1+1}\!\!{\bf u}, \;\delta
\prod_{j=1}^k\frac{1}{i_j+1}\frac{1}{i_j+2}\right)\right).\end{eqnarray*}
 Here, we have used property (b) of the events $E(\Gamma_1,\Gamma_2,\delta)$, together with
 the following two observations: if $\gamma_j \in ((1/2)^{i_j+1},(1/2)^{i_j}]$, then
 $(1/2)\Gamma \le (1/2)^{i_j+1}{\bf u}$ and $\Gamma \ge (1/2)^{i_j+1} {\bf u}$; and $\gamma_i \in ((1/2)^{i_j+1},
(1/2)^{i_j}]$ implies
$$\left(\log_2\left(\frac{4}{\gamma_j}\right)\right)^2 \ge (i_j+2)^2 \ge
(i_j+1)(i_j+2),$$ so that $$c(\Gamma) \le \prod_{j=1}^k
\frac{1}{(i_j+1)(i_j+2)}.$$ Now, by property (a),
\begin{eqnarray*}
 & & \p\left(\bigcup_{i_1,\dots, i_k=0}^\infty
E\left(\left(\frac{1}{2}\right)^{i_1+1}\!\!{\bf u},\;
\left(\frac{1}{2}\right)^{i_1+1}\!\!{\bf u}, \;\delta
\prod_{j=1}^k\frac{1}{i_j+1}\frac{1}{i_j+2}\right)\right)\\
&\le & \sum_{i_1, i_2, \dots, i_k=0}^\infty
\p\left(E\left(\left(\frac{1}{2}\right)^{i_1+1}\!\!{\bf u},\;
\left(\frac{1}{2}\right)^{i_1+1}\!\!{\bf u}, \;\delta
\prod_{j=1}^k\frac{1}{i_j+1}\frac{1}{i_j+2}\right)\right)\\
& \le & \sum_{i_1, i_2, \dots, i_k=0}^\infty \delta\,\prod_{j=1}^k
\left(\frac{1}{(i_j+1)(i_j+2)}\right) \\ & =&  \delta\,
\prod_{j=1}^k \sum_{i_j=0}^\infty
\left(\frac{1}{(i_j+1)(i_j+2)}\right)\\
&=&  \delta \,\prod_{j=1}^k
\sum_{i_j=0}^\infty\left(\frac{1}{i_j+1}-\frac{1}{i_j+2}\right)\\
&=& \delta \,\prod_{j=1}^k 1 =\delta.\end{eqnarray*}
\end{proof}

%\newpage

 We can now obtain the following `uniform' result.

\begin{theorem} \label{thm:tdluniform}
Suppose $R\ge 1$ and $Z=B_R
\times \{0,1\}$, where $B_R=\{x \in \bbr^n: \|x\| \le R\}$. Let
$H$ be the set of all threshold decision lists (with any number of
terms) defined on domain $B_R$. With probability at least
$1-\delta$, the following statements hold for $s \in Z^m$:
\begin{enumerate} \item {\em for all} $k \in \bbn$ and {\em for all} $\gamma_1,
\gamma_2, \dots, \gamma_k \in (0,1]$, if $h \in H$ has $k$ terms,
and \newline $\Gamma=(\gamma_1,\gamma_2, \dots, \gamma_k)$, then
$$\er_P(h)< \er_s^\Gamma(h)+\sqrt{\frac{8}{m}\left(2304\,R^2 D(\Gamma)
\ln\left(8m\right)+ \ln\left(\frac{2}{\delta}\right)+2k
+2\,\sum_{i=1}^k
\ln\left(\log_2\left(\frac{4}{\gamma_i}\right)\right)\right)},$$
where $D(\Gamma)=\sum_{i=1}^k (1/\gamma_i^2)$. \item {\em for all}
$k \in \bbn$, and {\em for all} $\gamma_1, \gamma_2, \dots,
\gamma_k \in (0,1]$, if $h \in H$ has $k$ terms, and $h$
classifies $s$ with margin $\Gamma=(\gamma_1,\gamma_2, \dots,
\gamma_k)$, then
$$\er_P(h)< \frac{2}{m}\left(2304\,R^2 D(\Gamma)
\log_2\left(8m\right)+
\log_2\left(\frac{2}{\delta}\right)+2k+2\,\sum_{i=1}^k
\ln\left(\log_2\left(\frac{4}{\gamma_i}\right)\right)\right),$$
where $D(\Gamma)=\sum_{i=1}^k (1/\gamma_i^2)$.
\end{enumerate}
\end{theorem}

\begin{proof} Fix $k \in \bbn$. If
$\Gamma_1=(\gamma_1^{(1)}, \dots, \gamma_k^{(1)})$ and
$\Gamma_2=(\gamma_1^{(2)}, \dots, \gamma_k^{(2)})$,
 let $E(\Gamma_1,\Gamma_2, \delta)$ be the event that there exists a threshold
 decision list $h$ with $k$ terms such that
$$\er_P(h)\ge \er_s^{\Gamma_2}(h)+\sqrt{\frac{8}{m}\left(576\,R^2D(\Gamma_1)
 \ln\left(8m\right)+
\ln\left(\frac{2}{\delta}\right)+k\right)},$$ where
$D(\Gamma_1)=\sum_{i=1}^k (1/\gamma_i^{(1)})^2$.  Then, by
Theorem~\ref{thm:tdlnonzero}, $P^m(E(\Gamma, \Gamma, \delta)) \le
\delta$, and it is easily seen that $\Gamma_1 \le \Gamma \le
\Gamma_2$ and $0<\delta_1\le \delta\le 1$ imply
$E(\Gamma_1,\Gamma_2,\delta_1) \subseteq E(\Gamma,\Gamma,\delta)$.
 It follows that
$$P^m\left(\bigcup_{\Gamma \in (0,1]^k} E\left(
(1/2)\Gamma, \Gamma, \delta\,c(\Gamma)\right)\right)\le \delta,$$
where
$$c(\Gamma)=\left\{\prod_{i=1}^k\log_2\left(\frac{4}{\gamma_i}\right)\right\}^{-2}.$$
 So, with probability at least $1-\delta$, {\em for all} $\gamma_1,
\gamma_2, \dots, \gamma_k \in (0,1]$, if $h$ is any threshold decision list with $k$
terms, and $\Gamma=(\gamma_1,\gamma_2, \dots, \gamma_k)$, then
$$\er_P(h)< \er_s^\Gamma(h)+\sqrt{\frac{8}{m}\left(2304\,R^2D(\Gamma)
\ln\left(8m\right)+ \ln\left(\frac{2}{\delta}\right)+k
+\ln\left(\frac{1}{c(\Gamma)}\right)\right)},$$ where
$D(\Gamma)=\sum_{i=1}^k (1/\gamma_i^2)$.
 This holds for any {\em fixed} $k$. Replacing $\delta$ by $\delta/2^k$, we see that,
 with probability at least $1-\delta/2^k$,
 for any $h$ with $k$ terms and any $\Gamma$,
$$\er_P(h)< \er_s^\Gamma(h)+\sqrt{\frac{8}{m}\left(2304\,R^2D(\Gamma)
\ln(8m)+
\ln\left(\frac{2\,2^k}{\delta}\right)+k+\ln\left(\frac{1}{c(\Gamma)}\right)\right)},$$
and so, with probability at least $1-\sum_{k=1}^\infty
(\delta/2^k)=1-\delta$, for all $k$, for all $h$ of length $k$,
and for all $\Gamma$,
$$\er_P(h)<
\er_s^\Gamma(h)+\sqrt{\frac{8}{m}\left(2304R^2 D(\Gamma)
\ln\left(8m\right)+ \ln\left(\frac{2}{\delta}\right)+2k+
2\,\sum_{i=1}^k
\ln\left(\log_2\left(\frac{4}{\gamma_i}\right)\right)\right)}.$$
(Note that we could have replaced $\delta$ by $\delta \alpha_k$
where $(\alpha_k)$ is any sequence such that $\sum_{i=1}^\infty
\alpha_k=1$.) The second part of the theorem is proved similarly,
using Theorem~\ref{thm:tdlzero}. \end{proof}

\subsection{Comparison with Related Results}

\citet{STC} and
  \citet{bennett}
  proved a margin-based generalization result for the more
general class of perceptron decision trees, in the case where
there is zero $\Gamma$-margin error on the sample.
 The special case of their result that applies to threshold decision
lists gives a bound (with probability at least $1-\delta$) of the
form \begin{eqnarray}\label{eqn:orderbennett} \er_P(h) <
O\left(\frac{1}{m} \left( D(\Gamma)\, (\ln m)^2 +k \ln
m+\ln\left(\frac{1}{\delta}\right)\right)\right).\end{eqnarray}
(The $O$-notation indicates that constants have been suppressed.)

By comparison, the bound given in Theorem~\ref{thm:tdluniform} is
of order \begin{eqnarray}\label{eqn:ordernew} \er_P(h) <
O\left(\frac{1}{m}\left(D(\Gamma) \ln m + k+\sum_{i=1}^k\ln
\ln\left(\frac{1}{\gamma_i}\right)+
\ln\left(\frac{1}{\delta}\right)\right)\right).\end{eqnarray}


The first term of bound~(\ref{eqn:ordernew}) is a $\ln m$ factor
better than the corresponding term of~(\ref{eqn:orderbennett}).
That this is so is because we have used Zhang's covering number
bound,~(\ref{eqn:zhang}), rather than bounding the covering number
by using results on fat-shattering dimension, coupled with the
bound of\citet{Alon}.  Additionally, since all these probability
bounds are trivial (greater than $1$) unless $m>(R/\gamma_i)^2$
for all $i$, the remaining terms of the bound~(\ref{eqn:ordernew})
are of order no more than $O(k+ \ln \ln m)$ rather than the
$O(k\ln m)$ of~(\ref{eqn:orderbennett}), and they are potentially
much smaller. This improvement results from the use of
Theorem~\ref{thm:uniformize}. Theorem~\ref{thm:tdluniform} is
therefore an improvement over the results implied by \citet{STC}
and \citet{bennett}.

\subsection{Bounds for Perceptron Decision Trees}

Although the focus of this paper is threshold decision lists, we
now show how the analysis here can be used to improve and extend
results on perceptron decision trees given by~\citet{STC} and
\citet{bennett}. Recall that these are decision trees in which the
decision nodes compute threshold functions. The definition of
margin error $\er^\Gamma(h)$ for a perceptron decision tree
classifier $h$ is defined in a straightforward way by extending
Definition~\ref{def:marginerror}. Suppose the threshold functions
computed at the decision nodes are $t_1, \dots, t_k$, where $k$ is
the number of decision nodes, and suppose that $t_i$ is
represented by weight vector $w_i$ and threshold
 $\theta_i$, where $\|w_i\|=1$. Given $\Gamma=(\gamma_1,\gamma_2, \dots, \gamma_k)$,
  we say that the tree $h$ classifies the
labeled example $(x,b)$  with margin $\Gamma$ if $h(x)=b$ and, for
all $1 \le i\le k$, $|\ip{w_i}{x}-\theta_i| \ge \gamma_i$. Then,
for a labeled sample $s$,
 $\er^\Gamma_\ve{s}(h)$ is the proportion of labeled
examples in $s$ that are not classified with margin $\Gamma$.

\citet{STC} and \cite{bennett} obtain a generalization error bound
for the special case in which the margin error is zero. The
following theorem improves that bound and provides a bound
applicable in the case of non-zero margin error. (We have stated
only a `uniform' result; that is, one in which the margin
parameters and tree size are not fixed {\em a priori}. However,
embedded in the proof are the corresponding non-uniform results.)
The proof is a modification of the proofs of the theorems for
threshold decision lists, in which we make use of the fact that
the number of binary trees with $k$ vertices---and hence the
number of decision tree skeletons with $k$ decision
nodes~\citep[as noted in][]{Quinlan,bennett}---is given by the
Catalan number $N_k={1\over k+1}{2k \choose k}$.

\begin{theorem} \label{thm:trees} For $k \in \bbn$, let
 $\displaystyle{N_k=\frac{1}{k+1}{2k \choose k}}$. Suppose
$R\ge 1$ and $Z=B_R \times \{0,1\}$, where $B_R=\{x \in \bbr^n:
\|x\| \le R\}$. Let $H$ be the set of all perceptron decision
trees (of any size and structure) defined on domain $B_R$. With
probability at least $1-\delta$, the following statements hold for
$s \in Z^m$:
\begin{enumerate} \item {\em for all} $k \in \bbn$ and {\em for all} $\gamma_1,
\gamma_2, \dots, \gamma_k \in (0,1]$, if $h \in H$ has $k$
decision nodes, and
\newline $\Gamma=(\gamma_1,\gamma_2, \dots, \gamma_k)$, then
\begin{align*}
\begin{split}
\er_P(h) &< \er_s^\Gamma(h) \\
&+\sqrt{\frac{8}{m}\left(2304\,R^2 D(\Gamma)
\ln\left(8m\right)+ \ln\left(\frac{2^{k+2}N_k}{\delta}\right)+k
+2\,\sum_{i=1}^k
\ln\left(\log_2\left(\frac{4}{\gamma_i}\right)\right)\right)},
\end{split}
\end{align*}
where $D(\Gamma)=\sum_{i=1}^k (1/\gamma_i^2)$. \item {\em for all}
$k \in \bbn$, and {\em for all} $\gamma_1, \gamma_2, \dots,
\gamma_k \in (0,1]$, if $h \in H$ has $k$ decision nodes, and $h$
classifies $s$ with margin $\Gamma=(\gamma_1,\gamma_2, \dots,
\gamma_k)$, then
$$\er_P(h)< \frac{2}{m}\left(2304\,R^2 D(\Gamma)
\log_2\left(8m\right)+
\log_2\left(\frac{2^{k+2}N_k}{\delta}\right)+k+2\,\sum_{i=1}^k
\ln\left(\log_2\left(\frac{4}{\gamma_i}\right)\right)\right),$$
where $D(\Gamma)=\sum_{i=1}^k (1/\gamma_i^2)$.\end{enumerate}
\end{theorem}

\begin{proof} The proof is similar to that of
Theorems~\ref{thm:tdlnonzero}, \ref{thm:tdlzero} and
\ref{thm:tdluniform}, so we will omit some of the detail. As in
the proof of Theorem~\ref{thm:tdlnonzero}, for any $k \in \bbn$,
for $H$ the class of perceptron decision trees (or, rather, the
functions represented by such trees) with $k$ decision nodes, for
any $\Gamma$, if
$$Q=\{\ve{s} \in Z^m: \exists h \in H \;{\rm with}\; \er_P(h)\ge
\er^\Gamma_\ve{s}(h)+\epsilon\}$$ and
$$T=\{(s,s') \in Z^m \times Z^m: \exists h \in H \;{\rm with}\; \er_{s'}(h)\ge
\er^\Gamma_{s}(h)+\epsilon/2\},$$ then for $m \ge 2/\epsilon^2$,
$P^m(Q) \le 2\,P^{2m}(T).$ With $G$ the swapping permutation
group, we have, as before, $P^{2m}(T)\le \max\{\pr(\sigma z \in
T): z \in Z^{2m}\},$ where $\pr$ denotes the probability over
uniform choice of $\sigma$ from $G$.  Given a perceptron decision
tree on $B_R$, we may (as discussed in the proof of
Theorem~\ref{thm:tdlnonzero}) realize the tree as one defined on
$D=\{(x,-1): x \in \bbr^n, \|x\| \le R\}$, in which the decision
nodes compute homogeneous threshold functions. Fixing $z \in
Z^{2m}$, and arguing as in the proof of
Theorem~\ref{thm:tdlnonzero}, for $i$ between $1$ and $k$, let
$C_i$ be a minimal-cardinality $\gamma_i/2$-cover of $L$ with
respect to the $d^x_\infty$ metric, where $L$ is the set of linear
functions $x\mapsto \ip{w}{x}$ for $\|w\|=1$, defined on $D$. Then
$|C_i|$ is bounded as in~(\ref{eqn:cibound}). Suppose that, in a
given perceptron decision tree $h$, and at a given decision node,
the test is given by the threshold function $f_i$, represented by
weight vector $w_i$ and let $\hat{w}_i$ be an element of the cover
$C_i$ which is distance less than $\gamma_i/2$ from $w_i$. Then a
very similar analysis to that in Theorem~\ref{thm:tdlnonzero}
establishes that if $\hat{h}$ is the tree obtained by replacing
each $f_i$ by $\hat{f}_i$, we have $$\pr\left(\sigma z \in
T\right) \le \pr\left(\sigma z \in
 \bigcup_{\hat{h} \in \hat{H}} S(\hat{h})\right),$$
 where
 $\displaystyle{S(\hat{h})=\{(s,s') \in Z^{2m}: \er^{\Gamma/2}_{s'}(\hat{h}) \ge
 \er^{\Gamma/2}_s(\hat{h})+\epsilon/2\}.}$
 Now, the set $\hat{H}$ of all such $\hat{h}$ will have
 cardinality bounded as follows:
 $$|\hat{H}| \le 2^{k+1}N_k \prod_{i=1}^k |C_i| \le
 2^{k+1}N_k\prod_{i=1}^k
 2^{(288R^2/\gamma_i^2)\log_2(60Rm/\gamma_i)},$$ where the factor
 of $2^{k+1}$ accounts for the possible binary values at the $k+1$
 leaves of the tree, and $N_k$ accounts for the number of
 skeletons of trees with $k$ decision nodes.
 By arguing precisely as in
 Theorem~\ref{thm:tdlnonzero}, we can then establish that for $\delta \in (0,1)$, for
 fixed $k$ and fixed $\Gamma$, with probability at least
 $1-\delta$, for all perceptron decision trees with $k$ decision
 nodes,
$\er_P(h)< \er_s^\Gamma(h)+\epsilon(\Gamma,\delta,k,m),$ where
$$\epsilon(\Gamma,\delta,k,m)=\sqrt{\frac{8}{m}\left(576\,R^2 D(\Gamma) \ln\left(8m\right)+
\ln\left(\frac{2^{k+2}N_k}{\delta}\right)\right)},$$
 Next, we apply Theorem~\ref{thm:uniformize}. Fixing $k$ and taking $E(\Gamma_1,\Gamma_2, \delta)$ to
 be the event that there exists a perceptron decision tree $h$ with $k$ decision nodes
 such that $\er_P(h)\ge
 \er_s^{\Gamma_2}(h)+\epsilon(\Gamma_1,\delta,k,m)$, we establish
 that with probability at least $1-\delta$, for {\em all}
 $\Gamma$,
 $$\er_P(h)< \er_s^\Gamma(h)+\sqrt{\frac{8}{m}\left(2304\,R^2 D(\Gamma)
\ln\left(8m\right)+ \ln\left(\frac{2^{k+2}N_k}{\delta}\right)
+2\,\sum_{i=1}^k
\ln\left(\log_2\left(\frac{4}{\gamma_i}\right)\right)\right)}.$$
Finally, replacing $\delta$ by $\delta/2^k$ and proceeding as in
the final part of the proof of Theorem~\ref{thm:uniformize}, we
obtain the desired result. The proof of the second part of the
theorem is similar.
\end{proof}

The result given in~\citet{STC} and ~\cite{bennett} corresponds to
the second case given in Theorem~\ref{thm:trees} and takes the
form: with probability at least $1-\delta$, for all $\Gamma$ and
for any perceptron decision tree such that $\er^\Gamma(h)=0$,
$$\er_P(h)<O\left(\frac{1}{m} \left( D(\Gamma)\, (\ln m)^2
+k \ln m+\ln N_k
+\ln\left(\frac{1}{\delta}\right)\right)\right),$$ where we have
suppressed the constants. Theorem~\ref{thm:trees} improves upon
this, as can be seen by similar considerations to those made in
comparing bounds~(\ref{eqn:orderbennett}) and~(\ref{eqn:ordernew})
above. In particular, an expression of order $D(\Gamma)\, (\ln
m)^2+k \ln m$ is replaced by one of order $D(\Gamma)\,\ln m+ k +
\ln \ln m$.

\bigskip

\section{Margin-Based Error Bounds for Multilevel Threshold Functions}
\label{sec:mlt}

 Suppose that $h$ is a $k$-level threshold
function, represented by weight vector $w$ with $\|w\|=1$ and
threshold vector $\theta=(\theta_1, \theta_2, \dots, \theta_k)$
(where $\theta_1 \le \theta_2 \cdots \le \theta_k$). Regarded as a
threshold decision list, the tests are the threshold functions
$t_i$, where $t_i(y)=\sgn(\ip{w}{x}-\theta_i)$. Recall that we say
$h$ classifies the labeled example $(x,b)$ with margin $\gamma>0$
if $h(x)=b$ and, for all $1 \le i\le k$, $|\ip{w}{x}-\theta_i| \ge
\gamma$. (In other words, $h$ classifies $x$ correctly, and $x$ is
distance at least $\gamma$ from any of the hyperplanes defining
the multilevel threshold function $h$.) As above, for a labeled
sample $\ve{s}$, $\er^\gamma_\ve{s}(h)$, the sample error at
margin $\gamma$, is the proportion of labeled examples in $\ve{s}$
that are {\em not} correctly classified with margin $\gamma$.

To bound generalization error in this special case, we take a
slightly different approach to the one used above for general
threshold decision lists. Rather than take a cover for each term
of the decision list, a more `global' approach can be taken,
exploiting the fact that the planes are parallel. In taking this
approach, however, the analysis considers only one margin
parameter, $\gamma$, rather than $k$ possibly different margin
parameters, one for each plane. (As before, for the sake of
simplicity, we assume that $R \ge 1$ and $\gamma \le 1$.)


\subsection{Generalization Error Bounds for $k$-level Threshold
Functions}

We have the following result.

\begin{theorem} \label{thm:mltnonzero}
Suppose $R\ge 1$ and $Z=B_R \times \{0,1\}$, where $B_R=\{x \in
\bbr^n: \|x\| \le R\}$. Fix $k \in \bbn$ and let $H$ be the set of
all $k$-level threshold functions defined on domain $B_R$. Let $P$
be any probability distribution on $Z$, and suppose $\gamma \in
(0,1]$ and $\delta \in (0,1)$. Then, with $P^m$-probability at
least $1-\delta$, a sample $\ve{s}$ is such that if $h \in H$,
then
 $$\er_P(h) <  \er^\gamma_s(h)+
\sqrt{\frac{8}{m}\left(\frac{1152R^2}{\gamma^2}\ln\left(9m\right)+
k\ln\left(\frac{10R}{\gamma}\right)+\ln\left(\frac{4}{\delta}\right)\right)}.$$
 \end{theorem}

\begin{proof} Fix $\gamma\in (0,1]$. As earlier, with $H$ the set of
$k$-level threshold functions on $B_R$, if
$$Q=\{\ve{s} \in Z^m: \exists h \in H \;{\rm with}\; \er_P(h)\ge
\er^\gamma_\ve{s}(h)+\epsilon\}$$ and
$$T=\{(s,s') \in Z^m \times Z^m: \exists h \in H \;{\rm with}\; \er_{s'}(h)\ge
\er^\gamma_{s}(h)+\epsilon/2\},$$ then $P^m(Q) \le 2\,P^{2m}(T).$
Also as before, $P^{2m}(R)\le \max\{\pr(\sigma z \in R): z \in
Z^{2m}\},$ where $\pr$ denotes the probability over uniform choice
of $\sigma$ from the `swapping group' $G$. Let $L_R$ be the set of
all functions of the form $x \mapsto \ip{w}{x}$, where $w \in
\bbr^n$ satisfies $\|w\|=1$, and where the domains of the
functions are $B_R$. Now fix $z \in Z^{2m}$, let $x \in X^{2m}$ be
the corresponding $x_i$-vector, and let $C$ be a $\gamma/4$-cover
of minimum size of $L$ with respect to the $d_\infty^x$ metric.
By~(\ref{eqn:zhang}),
\begin{eqnarray*} \log_2|C| & \le & \log_2\cover(L_R, \gamma/4, 2m) \\
&\le & \frac{576 R^2}{\gamma^2} \log_2\left(2\left\lceil
16R/\gamma+2\right\rceil 2m+1\right)\\ &\le & \frac{576
R^2}{\gamma^2}
\log_2\left(\frac{80Rm}{\gamma}\right).\end{eqnarray*}
 Each
function in $C$ is represented by a weight vector, and we shall
denote the set of these weight vectors by $\hat{W}$. For each $w
\in \bbr^n$, denote by $\hat{w}$ a member of $\hat{W}$ such that
for $i=1,2,\dots, 2m$, $|\ip{w}{x_i}-\ip{\hat{w}}{x_i}|<\gamma/4$.
Let
$$D=\left\{ \theta \in \bbr: \exists n \in \bbz\cap [-(4R/\gamma)-1,
(4R/\gamma)+1]\;{\rm such\;that}\; \theta =n(\gamma/4)\right\},$$
and let $\hat{\Theta}=D^k$.
 Then
 $$|\hat{\Theta}| \le \left(\frac{8R}{\gamma}+2\right)^k \le
 \left(\frac{10R}{\gamma}\right)^k.$$ Now, suppose $h$ is a
  $k$-level threshold function
 defined on $B_R$. Then, of course, $h$ is represented by a weight
 vector $w \in \bbr^n$ with $\|w\|=1$ and a threshold vector $\theta\in \bbr^k$. Since,
 for all $x \in B_R$, $|\ip{w}{x}|\le \|w\|\|x\| =\|x\|
 \le R$, we can assume that each $\theta_i$ satisfies $|\theta_i| \le R$. Then,
 denote by $\hat{\theta}$ a member of $\hat{\Theta}$ such that for
 $i=1,2,\dots, k$, $|\theta_i-\hat{\theta}_i| \le \gamma/4$. (Such
 a $\hat{\theta}$ exists by the way in which $\hat{\Theta}$ is
 defined.)
 Let $\hat{H}$ be the set of all $k$-level threshold functions representable by weight
 vectors $\hat{w} \in \hat{W}$ and threshold vectors $\hat{\theta}
 =(\theta_1, \dots, \theta_k) \in
 \hat{\Theta}$. Then
 $$|\hat{H}| \le 2\,2^{(576 R^2/\gamma^2) \log_2(80Rm/\gamma)}\,
 \left(\frac{10R}{\gamma}\right)^k.$$ (Here, the first factor of $2$ accounts for the two different
 ways in which the classifications can alternate as we traverse the planes is a normal direction.)
 For each $h \in H$, let $\hat{h}$ be the
 $k$-level threshold vector with weight vector $\hat{w} \in \hat{W}$ and threshold
 vector $\hat{\theta} \in \theta$, where $\hat{w}$ and $\hat{\theta}$ satisfy the
 properties indicated above.
 For each $i=1,2,\dots, 2m$, for each $j=1,2,\dots, k$,
$$|(\ip{w}{x_i}-\theta_j)-(\ip{\hat{w}}{x_i}-\hat{\theta}_j)| \le
|\ip{w}{x_i}-\ip{\hat{w}}{x_i}| + |\theta_i-\hat{\theta}_i| \le
\gamma/4+\gamma/4=\gamma/2.$$ This means that, when $x$ is any one of the $x_i$, and
$1\le j \le k$,
\begin{eqnarray*} \ip{w}{x}< \theta_j & \Longrightarrow & \ip{\hat{w}}{x}
< \hat{\theta}_j +\gamma/2,\\
\ip{w}{x}> \theta_j & \Longrightarrow & \ip{\hat{w}}{x}
> \hat{\theta}_j -\gamma/2,\\
\ip{\hat{w}}{x}\le \hat{\theta}_j+\gamma/2 & \Longrightarrow & \ip{w}{x}
< \theta_j +\gamma,\\
\ip{\hat{w}}{x}\ge \hat{\theta}_j-\gamma/2 & \Longrightarrow & \ip{w}{x}
> \theta_j -\gamma.\end{eqnarray*}
It follows that $\er^{\gamma/2}_{s'}(\hat{h})\ge \er_{s'}(h)$ and
$\er_{s}^{\gamma}(h) \ge \er_{s}^{\gamma/2}(\hat{h})$. So, if
 we have $\sigma z=(s,s') \in T$ and $\er_{s'}(h)\ge
\er^\gamma_{s}(h)+\epsilon/2$, then
$$\er_{s'}^{\gamma/2}(\hat{h}) \ge \er_{s'}(h) \ge \er^\gamma_{s}(h)+\epsilon/2 \ge
\er_s^{\gamma/2}(\hat{h})+\epsilon/2.$$
The proof now proceeds as the proof of
Theorem~\ref{thm:tdlnonzero}. For any $z \in Z^{2m}$,
$$\pr\left(\sigma z \in T\right) \le \pr\left(\sigma z \in
 \bigcup_{\hat{h} \in \hat{H}} S(\hat{h})\right),$$
 where
 $$S(\hat{h})=\{(s,s') \in Z^{2m}: \er^{\gamma/2}_{s'}(\hat{h}) \ge
 \er^{\gamma/2}_s(\hat{h})+\epsilon/2\}.$$
 Fixing $\hat{h} \in \hat{H}$, we find that, by Hoeffding's
 inequality,
 $$\pr\left(\sigma z \in S(\hat{h})\right)\le \exp(-\epsilon^2m/8).$$
 Therefore,
 $$P^m(Q) < 2\,|\hat{H}|\,\exp(-\epsilon^2m/8) \le
4\,2^{576 R^2/\gamma^2 \log_2(80Rm/\gamma)}\,
 \left(\frac{10R}{\gamma}\right)^k \,\exp(-\epsilon^2m/8).$$
So, with probability at least $1-\delta$, for all $h \in H$,
$$\er_P(h)< \er_s(h)+
\sqrt{\frac{8}{m}\left(\left(\frac{576R^2}{\gamma^2}\right)\ln\left(\frac{80Rm}{\gamma}\right)+
k\ln\left(\frac{10R}{\gamma}\right)+\ln\left(\frac{4}{\delta}\right)\right)}.$$
 The result follows on noting that the bound stated in the theorem is trivially true
 if $m<R^2/\gamma^2$, and is implied by the bound just derived if $m\ge R^2/\gamma^2$.
\end{proof}

For the case in which the margin error is zero, a better bound can
be derived.

\begin{theorem} \label{thm:mltzero} Suppose $R>0$ and $Z=B_R \times \{0,1\}$,
where $B_R=\{x \in \bbr^n: \|x\| \le R\}$. Fix $k \in \bbn$ and
let $H$ be the set of all $k$-level threshold functions defined on
domain $B_R$. Let $P$ be any probability distribution on $Z$, and
suppose $\gamma\in (0,1]$ and $\delta \in (0,1)$. Then, with
$P^m$-probability at least $1-\delta$, a sample $\ve{s}$ is such
that if $h \in H$ and
 $\er^\gamma_\ve{s}(h)=0$, then
 $$\er_P(h) <
 \frac{2}{m}\left(\frac{1152 R^2}{\gamma^2}\log_2(9m)+k\log_2\left(\frac{10R}{\gamma}\right)
 +\log_2\left(\frac{2}{\delta}\right)\right).$$
 \end{theorem}

\begin{proof} This result is obtained by modifying the proof of
Theorem~\ref{thm:mltnonzero}, just in the same way as
Theorem~\ref{thm:tdlzero} is obtained by modifying the proof of
Theorem~\ref{thm:tdlnonzero}. First, one uses the fact that if
$$Q=\{\ve{s} \in Z^m: \exists h \in H \;{\rm with}\; \er^\gamma_\ve{s}(h)=0, \,
\er_P(h)\ge \epsilon\}$$ and $$T=\{\ve{(s,s')} \in Z^m \times Z^m:
\exists h \in H \;{\rm with}\; \er^\gamma_\ve{s}(h)=0, \,
\er_{s'}(h)\ge \epsilon/2\},$$ then, for $m \ge 8/\epsilon$,
$P^m(Q) \le 2\,P^{2m}(T)$.
 As before,
 $P^{2m}(T)\le \max_{z \in Z^{2m}}\pr(\sigma z \in T),$ where $\pr$ denotes the
probability over uniform choice of $\sigma$ from the `swapping
group' $G$.  Then, it can be seen that for any $z \in Z^{2m}$,
$$\pr\left(\sigma z \in T\right) \le \pr\left(\sigma z \in
 \bigcup_{\hat{h} \in \hat{H}} S(\hat{h})\right),$$
 where
 $\displaystyle{S(\hat{h})=\{(s,s') \in Z^{2m}:  \er^{\gamma/2}_\ve{\hat{s}}(h)=0,
 \, \er_{s'}^{\gamma/2}(\hat{h})\ge
\epsilon/2\}}$ and where $\hat{H}$ is as in the proof of
Theorem~\ref{thm:mltnonzero}. Arguing as in the proof of
Theorem~\ref{thm:tdlzero}, if $S(\hat{h}) \neq \emptyset$, so that
for some $\tau \in G$,
 $\tau z=(s,s') \in
 S(\hat{h})$, then  $\pr\left(\sigma z \in S(\hat{h})\right)=\pr\left(\sigma(\tau
 z) \in S(\hat{h})\right)$. Supposing that
 $\er^{\gamma/2}_{s'}(\hat{h})=r/m$, where $r \ge \epsilon m/2$ is
 the number of $x_i$ in $s'$ not classified with margin $\gamma/2$
 by $\hat{h}$, we see that there are at most $2^{m-r}\le
 2^{m-\epsilon m/2}$ $\sigma$ such that $\sigma(\tau z) \in S(\hat{h})$.
 Hence, for each  $\hat{h} \in \hat{H}$,
 $$\pr\left(\sigma z \in S(\hat{h})\right)\le \frac{2^{m(1-\epsilon/2)}}{|G|}=
 2^{-\epsilon m/2}.$$
 The proof then proceeds as does the proof of
 Theorem~\ref{thm:mltnonzero}.
 \end{proof}


\subsection{Uniform Margin-based Bounds for Multilevel Threshold Functions}

It is straightforward to remove the {\em a priori} specification
of $\gamma$ and $k$, using Theorem~\ref{thm:uniformize}. The
following bounds are obtained.

\begin{theorem} \label{thm:mltuniform}
Suppose $R>0$ and $Z=B_R \times \{0,1\}$, where $B_R=\{x \in
\bbr^n: \|x\| \le R\}$. Let $H$ be the set of all multilevel
threshold functions defined on domain $B_R$. Let $P$ be any
probability distribution on $Z$. Then, with $P^m$-probability at
least $1-\delta$, the following hold:
\begin{enumerate} \item {\em for all} $k \in \bbn$ and
{\em for all} $\gamma \in (0,1]$, if $h \in H$ is a $k$-level
threshold function, then
$$\er_P(h)< \er_s^\gamma(h)+\epsilon(\gamma,\delta,k,m)$$ where
$\epsilon=\epsilon(\gamma,\delta,k,m)$ is given by
$$\epsilon=\sqrt{\frac{8}{m}\left(\frac{4608 R^2}{\gamma^2}
\ln\left(9m\right)+ k +
k\ln\left(\frac{20R}{\gamma}\right)+\ln\left(\frac{4}{\delta}\right)+
2\ln\left(\log_2\left(\frac{4}{\gamma}\right)\right)\right)}.$$
\item {\em for all} $k \in \bbn$, and {\em for all} $\gamma \in
(0,1]$, if $h \in H$ is a $k$-level threshold function and $h$
classifies $s$ with margin $\gamma$, then
$$\er_P(h)<
\frac{2}{m}\left(\frac{4608 R^2}{\gamma^2}\log_2(9m)+k +k
\log_2\left(\frac{20R}{\gamma}\right)
 +\log_2\left(\frac{4}{\delta}\right)+2\ln\left(\log_2\left(\frac{4}{\gamma}\right)\right)\right).$$
\end{enumerate}
\end{theorem}

\begin{proof} Let
 $E(\gamma_1,\gamma_2,\delta)\subseteq Z^m$ be the event that
 there exists $h \in H$ with $k$ terms such that $$\er_P(h) \ge
 \er^{\gamma_2}_s(h)+\epsilon'(\gamma_1,\delta,k,m),$$ where
$$\epsilon'(\gamma,\delta,k,m)=\sqrt{\frac{8}{m}\left(\frac{1152R^2}{\gamma^2}\ln\left(9m\right)+
k\ln\left(\frac{10R}{\gamma}\right)+\ln\left(\frac{4}{\delta}\right)\right)}.$$
Then, by Theorem~\ref{thm:mltnonzero}, $P^{2m}(E(\gamma, \gamma,
\delta))\le \delta$. It is also clear that $0<\gamma_1\le \gamma
\le \gamma_2<1$ and $0<\delta_1\le \delta\le 1$ imply
$E(\gamma_1,\gamma_2,\delta_1) \subseteq E(\gamma,\gamma,\delta)$.
By Theorem~\ref{thm:uniformize}, with $\delta/2^k$ in place of
$\delta$, we therefore have that, for any fixed $k \in \bbn$, with
probability at least $1-\delta/2^k$, for {\em all} $\gamma \in
(0,1]$, every $k$-level threshold function $h$ satisfies
$$\er_P(h)<\er_s^\gamma(h)+\epsilon'(\gamma/2,\delta
c(\gamma)/2^k,k,m),$$ where
$c(\gamma)=1/\left(\log_2(4/\gamma)\right)^2$. Thus, with
probability at least $1-\delta$, {\em for all} $\gamma \in (0,1]$
and {\em all} $k \in \bbn$, every $k$-level threshold function has
$$\er_P(h)<\er_s^\gamma(h)+\epsilon'(\gamma/2,\delta
c(\gamma)/2^k,k,m)\le \er_s^\gamma(h)+
\epsilon(\gamma,\delta,k,m).$$ The first part of the result now
follows, and the second is proved similarly, using
Theorem~\ref{thm:mltzero}.
\end{proof}

\subsection{Comparison with the Bounds for General Threshold Decision Lists}

The generalization error bound implied by
Theorem~\ref{thm:tdlnonzero} in the case in which
$\gamma_i=\gamma$ for all $i$ is, suppressing constants,
$$\er_P(h)< \er_s^\gamma(h)+ O\left(\sqrt{\frac{1}{m}\left(\frac{R^2k}{\gamma^2}\ln
m+\ln\left(\frac{1}{\delta}\right)\right)}\right)$$ (with
probability at least $1-\delta$), whereas that of
Theorem~\ref{thm:mltnonzero} is
$$\er_P(h)< \er_s^\gamma(h)+
O\left(\sqrt{\frac{1}{m}\left(\frac{R^2}{\gamma^2}\ln
m+k\ln\left(\frac{R}{\gamma}\right)+
\ln\left(\frac{1}{\delta}\right)\right)}\right),$$ so there is
some advantage in the more particular analysis that has been
carried out for multi-level threshold functions. Similar comments
apply to the respective `uniform' bounds of
Theorem~\ref{thm:tdluniform} and Theorem~\ref{thm:mltuniform}.


\section{Conclusions and Further Work}
\label{sec:conclusions}

 This paper has derived different types of
theoretical bounds on the generalization error of threshold
decision lists.
 Applying the standard PAC model, by bounding the growth functions, we have given bounds
 for threshold decision lists and multilevel threshold functions.
   We then derived generalization error bounds that involve the
    margins by which successive
 planes in the threshold decision list `clear' the training
 examples. These bounds improve upon those that follow (for the special
 case in which the margin error is zero) from earlier results
 of~\citet{bennett} and~\citet{STC}. Although threshold decision lists have been the
 focus of this paper, we have also presented generalization error bounds for perceptron
 decision trees that improve and
 extend (to the case in which margin error need not be zero)
 previous such bounds from~\citet{bennett} and~\citet{STC}.
 For the subclass of multilevel threshold functions (those
 threshold decision lists in which the defining hyperplanes may be
 taken to be parallel), a different approach to constructing
 empirical covers has been shown to lead to better margin-based bounds than
 those that would follow from the general bounds obtained for threshold
 decision lists.

There are several possible directions for further investigation.

 We used upper bounds on the
growth functions of threshold decision lists and multilevel
threshold functions to upper bound generalization error. An
interesting combinatorial question concerns the VC-dimension of
these classes. Lower bounds on the VC-dimension would provide
worst-case lower bounds on generalization
error~\citep[see][]{Ehrenfeucht,AnthonyBiggs,ab,BEHW}. Certainly,
upper bounds on the VC-dimensions follow from the bounds we
obtained on the growth functions, but these are quite likely to be
loose and a more direct attempt might be productive in obtaining
not only better upper bounds, but also lower bounds, on the
VC-dimension.

There are other approaches to deriving generalization error
bounds. Of particular importance recently have been methods using
Rademacher complexity and local Rademacher complexity, together
with concentration-of-measure
results~\citep{BartlettMendelson,Mendelson,BBM,BKP,Bousquet}. It
would be interesting to investigate such approaches for threshold
decision lists.

The margin-based results obtained here for multilevel threshold
functions only involve a single margin parameter rather than
separate ones for each plane, and it is possible that a different
approach might permit such added flexibility.


We have not considered in this paper the algorithmics of learning
threshold decision lists. As mentioned, heuristics for learning
threshold decision lists were studied by~\citet{Marchand}, and
although no theoretical generalization error bounds were derived
there, the techniques appeared to perform well in experiments.
Furthermore, the perceptron decision tree algorithms FAT, MOC1,
and MOC2 due to~\cite{bennett} are variants of the OC1
algorithm~\citep{Murthy} that are explicitly driven by the aim of
maximising the margins at the decision nodes. It would be
interesting to modify the techniques of~\cite{Marchand} with a
view to obtaining large margins, and to modify the algorithms
of~\cite{bennett} so as to learn a threshold decision list rather
than a perceptron decision tree.

\section*{Acknowledgements}

I am grateful to the referees for a number of helpful suggestions
and, in particular, for comments leading to an improvement of
Theorem~\ref{thm:uniformize}.



\bibliographystyle{natbib}
\begin{thebibliography}{100}

\bibitem[Alon et al.(1997)Alon, Ben-David, Cesa-Bianchi and Haussler]{Alon} N. Alon,  S. Ben-David, N. Cesa-Bianchi, and D.
Haussler (1997). Scale-sensitive dimensions, uniform convergence,
and learnability. {\em Journal of the ACM} {44}(4): 615--631.

\bibitem[Anthony(2001)]{siambook} M. Anthony (2001). {\it Discrete Mathematics of Neural Networks: Selected
Topics}. SIAM Monographs on Discrete Mathematics and Applications.
Society for Industrial and Applied Mathematics, Philadelphia, PA.

\bibitem[Anthony(2002)]{partitions} M. Anthony (2002). Partitioning points by parallel planes.
RUTCOR Research Report RRR-39-2002, Rutgers Center for Operations
Research. (Also, CDAM research report LSE-CDAM-2002-10, Centre for
Discrete and Applicable Mathematics, London School of Economics.)
To appear, {\em Discrete Mathematics}.


\bibitem[Anthony and Bartlett(1999)]{ab} M. Anthony and P.~L. Bartlett (1999).
{\it Neural Network Learning: Theoretical Foundations}. Cambridge
University Press,
 Cambridge UK.

\bibitem[Anthony and Bartlett(2000)]{fli} M. Anthony and P.~L. Bartlett (2000).
Function learning from interpolation. {\em Combinatorics,
Probability and Computing}, 9: 213--225.

\bibitem[Anthony and Biggs(1992)]{AnthonyBiggs} M. Anthony and N. L.~Biggs (1992).
{\it Computational Learning Theory: An Introduction}.
     Cambridge Tracts in Theoretical Computer Science, 30.
 Cambridge University Press, Cambridge, UK.

\bibitem[Anthony et al.(1995)]{labeled}  M. Anthony, G. Brightwell and J. Shawe-Taylor (1995).
  On specifying {B}oolean functions by labelled examples.
  {\em Discrete Applied Mathematics}, 61: 1--25.

\bibitem[Bartlett(1998)]{Bartlett} P. L. Bartlett (1998). The sample complexity of pattern classification with
neural networks: the size of the weights is more important than
the size of the network. {\em IEEE Transactions on Information
Theory} {44}(2): 525--536.

\bibitem[Bartlett et al.(2002)]{BBM} P. L.~Bartlett, O. Bousquet and S. Mendelson (2002),  Localized
Rademacher complexities. {\em Proceedings of the $15$th Annual
Conference on Computational Learning Theory}, ed. J.~Kivinen and
R. H.~Sloan. Springer Lecture Notes in Artificial Intelligence
2375.

\bibitem[Bartlett and Mendelson(2001)]{BartlettMendelson} P. Bartlett and S. Mendelson (2001), Rademacher
 and Guassian complexities: risk bounds and structural results. In
{\em Proceedings of the $14$th Annual Conference on Computational
Learning Theory}, Lecture Notes in Artificial Intelligence,
Springer, 224-240.

\bibitem[Baum and Haussler(1989)]{BaumHaussler}   E.~Baum and D.~Haussler (1989).
\newblock What size net gives valid generalization?
\newblock {\em Neural Computation}, 1(1): 151--160.

\bibitem[Bennett et al.(2000)Bennett, Cristianini, Shawe-Taylor and Wu]{bennett} K. Bennett, N. Cristianini, J.
Shawe-Taylor and D. Wu (2000). Enlarging the Margins in Perceptron
Decision Trees. {\em Machine Learning}, 41: 295--313.

\bibitem[Blumer et al.(1989)Blumer, Ehrenfeucht, Haussler and Warmuth]{BEHW} A. Blumer, A. Ehrenfeucht, D. Haussler, and M.
K.~Warmuth (1989).
 Learnability and the {V}apnik-{C}hervonenkis dimension.
{\em Journal of the ACM}, {36}(4): 929--965.

\bibitem[Bohossian and Bruck(1998)]{BohossianBruck} V. Bohossian and J. Bruck (1998). Multiple
threshold neural logic. In {\em Advances in Neural Information
Processing, Volume 10: NIPS'1997}, Michael Jordan, Michael Kearns,
Sara Solla (eds), MIT Press.

\bibitem[Bousquet(2003)]{Bousquet} O. Bousquet (2003).
 New Approaches to Statistical Learning Theory. Annals of the Institute of Statistical Mathematics
 55 (2): 371-389.

\bibitem[Boucheron et al.(2000)]{BLM} S. Boucheron, G. Lugosi and P.
Massart (2000). A sharp concentration inequality with
applications. {\em Random Structures and Algorithms}, {16}:
277--292.

\bibitem[Bousquet et al.(2002)]{BKP} O. Bousquet, V. Koltchinskii and D. Panchenko
(2002).
 Some local measures of complexity on convex hulls and generalization bounds.
 {\em Proceedings of the $15$th Annual Conference on
 Computational Learning Theory}, ed. J.~Kivinen and R. H.~Sloan. Springer Lecture
 Notes in Artificial Intelligence 2375.

\bibitem[Cover(1965)]{Cover} T. M. Cover (1965). Geometrical and statistical properties of
systems of linear inequalities with applications in pattern
recognition, {\it IEEE Trans.~Electronic Computers} 14: 326--334.

\bibitem[Cristianini and Shawe-Taylor(2000)]{Cristianini} N. Cristianini and J. Shawe-Taylor (2000).
{\em An Introduction to Support Vector Machines}, %and Other Kernel Methods
 Cambridge University Press, Cambridge, UK.

\bibitem[Dudley(1999)]{Dudley} R. M.~Dudley (1999). {\em Uniform Central Limit Theorems},
 Cambridge Studies in Advanced Mathematics, 63,
 Cambridge University Press, Cambridge, UK.


\bibitem[Ehrenfeucht et al.(1989)]{Ehrenfeucht} A. Ehrenfeucht, D. Haussler, M. Kearns, and L. Valiant (1989).
A general lower bound on the number of examples needed for
learning.
 {\em Information and Computation}, 82: 247--261.

\bibitem[Hammer et al.(1981)]{Hammer} P. L Hammer, T. Ibaraki and U. N. Peled (1981). Threshold numbers and
threshold completions. {\em Annals of Discrete Mathematics} 11:
125--145.

\bibitem[Jeroslow(1975)]{Jeroslow} R. G. Jeroslow (1975). On defining sets of vertices of the
hypercube by linear inequalities. {\em Discrete Mathematics}, 11:
119--124.

\bibitem[Mangasarian(1968)]{Mangasarian} O. L. Mangasarian (1968). Multisurface method of pattern separation.
{\em IEEE Transactions on Information Theory} IT-14 (6): 801--807.

\bibitem[Marchand and Golea(1993)]{Marchand} M. Marchand and M. Golea (1993). On learning simple neural
concepts: from halfspace intersections to neural decision lists.
{\em Network: Computation in Neural Systems}, 4: 67--85.


\bibitem[Marchand et al.(1990)]{MarchandGoleaRujan} M. Marchand, M. Golea and P. Ruj\'an (1990). A convergence
theorem for sequential learning in two-layer perceptrons. {\em
Europhys. Lett.} 11: 487--492.

\bibitem[Marchand et al.(2003)]{SCMhalf} M. Marchand, M. Shah, J. Shawe-Taylor and
M. Sokolova (2003). The Set Covering Machine with Data-Dependent
Half-Spaces. Proceedings of the Twentieth International Conference
on Machine Learning (ICML'2003), 520--527, Morgan Kaufmann, San
Francisco CA.

\bibitem[Mendelson(2003)]{Mendelson} S. Mendelson (2003). A few notes on Statistical Learning Theory.
In  {\em Advanced Lectures in Machine Learning}, (S. Mendelson,
A. J. Smola Eds), LNCS 2600, 1-40, Springer.

\bibitem[Murthy et al.(1994)]{Murthy} S. K. Murthy, S.Kasif and S.
Salzberg (1994). A system for induction of oblique decision trees.
{\em Journal of Artificial Intelligence Research} 2: 1--32.

\bibitem[Ngom et al.(2003)]{ngom} A. Ngom, I. Stojmenovi\'{c} and J. \v{Z}uni\'{c} (2003). On the
number of multilinear partitions and the computing capacity of
multiple-valued multiple-threshold perceptrons, IEEE Transactions
on Neural Networks 14(3): 469--477.

\bibitem[Obradovi\'{c} and Parberry(1994)]{OP} Z. Obradovi\'{c} and I. Parberry (1994). Learning with discrete multivalued
neurons.  {\em Journal of Computer and System Sciences} 49:
375--390.

\bibitem[Olafsson and Abu-Mostafa(1988)]{Olafsson} S. Olafsson and Y. S. Abu-Mostafa (1988). The capacity of
multilevel threshold functions.  {\em IEEE Transactions on Pattern
Analysis and Machine Intelligence}, 10 (2): 277--281.

\bibitem[Pollard(1984)]{Pollard} D. Pollard (1984). {\em Convergence of Stochastic Processes}.
 Springer-Verlag.

\bibitem[Quinlan and Rivest(1989)]{Quinlan} J. R. Quinlan and R. Rivest (1989). Inferring decision
trees using the minimum description length principle. {\em
Information and Computation} 80: 227--248.

\bibitem[Rivest(1987)]{Rivest} R. L. Rivest (1987). Learning Decision Lists. {\it Machine
Learning} 2 (3): 229--246.

\bibitem[Shawe-Taylor et al.(1996)]{SRM} J. Shawe-Taylor,
P. L. Bartlett, R. C. Williamson and
M. Anthony (1996). Structural risk minimization over
data-dependent hierarchies. {\em IEEE Transactions on Information
Theory}, 44(5): 1926--1940.

\bibitem[Shawe-Taylor and Cristianini(1998)]{STC} J. Shawe-Taylor and N. Cristianini (1998). Data-Dependent
Structural Risk Minimisation for Perceptron Decision Trees.
Neurocolt Technical Report NC2-TR-1998-003.

\bibitem[Bartlett et al.(2000)]{Bartletteditedbook} A. J. Smola,
 P. L. Bartlett, B. Sch\"{o}lkopf and D. Schuurmans (editors) (2000). {\em
Advances in Large-Margin Classifiers (Neural Information
Processing)}, MIT Press.

\bibitem[Sokolova et al.(2003)]{Sokolova}
M. Sokolova, M. Marchand, N. Japkowicz, and J. Shawe-Taylor
(2003). The Decision List Machine. Advances in Neural Information
Processing Systems 15, 921--928, MIT-Press, Cambridge, MA, USA.



\bibitem[Takiyama(1985)]{Takiyama} R. Takiyama (1985). The separating capacity of
a multi-threshold element. {\em IEEE Transactions on Pattern
Analysis and Machine Intelligence}, 7: 112--116.

\bibitem[Turan and Vatan(1997)]{Turan} G. Tur\'an and F. Vatan (1997). Linear decision lists and
partitioning algorithms for the construction of neural networks.
Foundations of Computational Mathematics: selected papers of a
conference held at Rio de Janeiro, Springer, 414-423.

\bibitem[Valiant(1984)]{Valiant} L. G. Valiant (1984). A theory of the learnable.
 {\em Communications of the  ACM}, {27}(11): 1134--1142.

\bibitem[Vapnik(1982)]{Vapnikoldbook} V. N.~Vapnik (1982). {\em Estimation of Dependences Based on Empirical Data}.
 Springer-Verlag, New York..

\bibitem[Vapnik(1998)]{Vapnik} V. N.~Vapnik (1998). {\em Statistical Learning Theory},
Wiley.


\bibitem[Vapnik and Chervonenkis(1971)]{VC} V. N.~Vapnik and A. Y.~Chervonenkis (1971).
On the uniform convergence of relative frequencies of events to
their
  probabilities.
 {\em Theory of Probability
 and its Applications}, {16}(2): 264--280.

\bibitem[Zhang(2002)]{zhang} T. Zhang (2002). Covering number bounds of certain
regularized linear function classes. {\em Journal of Machine
Learning Research}, 2: 527--550.

\bibitem[Zuev and Lipkin(1988)]{Zuev}A. Zuev and L. I. Lipkin (1988). Estimating the efficiency of threshold
representations of Boolean functions. {\em Cybernetics} 24:
713--723. (Translated from Kibernetika (Kiev), 6, 1988: 29--37.)

\end{thebibliography}

\end{document}
