PAC Analogues of Perceptron and Winnow Via Boosting the Margin.
We describe a novel family of PAC model algorithms for learning linear threshold functions. The new algorithms work by boosting a simple weak learner and exhibit sample complexity bounds remarkably similar to those of known online algorithms such as Perceptron and Winnow, thus suggesting that these well-studied online algorithms in some sense correspond to instances of boosting. We show that the new algorithms can be viewed as natural PAC analogues of the online p-norm algorithms which have recently been studied by Grove, Littlestone, and Schuurmans (1997, Proceedings of the Tenth Annual Conference on Computational Learning Theory (pp. 171183) and Gentile and Littlestone (1999, Proceedings of the Twelfth Annual Conference on Computational Learning Theory (pp. 111). As special cases of the algorithm, by taking p &equals; 2 and p &equals;  we obtain natural boosting-based PAC analogues of Perceptron and Winnow respectively. The p &equals;  case of our algorithm can also be viewed as a generalization (with an improved sample complexity bound) of Jackson and Craven's PAC-model boosting-based algorithm for learning sparse perceptrons (Jackson & Craven, 1996, Advances in neural information processing systems 8, MIT Press). The analysis of the generalization error of the new algorithms relies on techniques from the theory of large margin classification.
INTRODUCTION
One of the most fundamental problems in computational learning
theory is that of learning an unknown linear threshold
function from labeled examples. Many different learning
algorithms for this problem have been considered over the
past several decades. In particular, in recent years many researchers
have studied simple online additive and multiplicative
update algorithms, namely the Perceptron and Winnow
algorithms and variants thereof [3, 5, 8, 14, 15, 16, 25, 26,
27, 28, 33, 36].
This paper takes a different approach. We describe a natural
parameterized family of boosting-based PAC algorithms
for learning linear threshold functions. The weak hypotheses
used are linear functionals and the strong classifier obtained
is a linear threshold function. Although these new algorithms
Supported in part by an NSF Graduate Fellowship, by NSF
grant CCR-95-04436 and by ONR grant N00014-96-1-0550.
are conceptually and algorithmically very different from Perceptron
and Winnow, we establish performance bounds for
the new algorithms which are remarkably similar to those of
Perceptron and Winnow; we thus refer to the new algorithms
as PAC analogues of Perceptron and Winnow. We hope that
the analysis of these new algorithms will yield fresh insights
into the relationship between boosting and online algorithms.
We give a unified analysis of our Perceptron and Winnow
analogues which includes many other algorithms as well.
Grove, Littlestone and Schuurmans [16] have shown that
Perceptron and (a version of) Winnow can be viewed as the
cases of a general online p-norm linear
threshold learning algorithm, where p - 2 is any real
number. We present PAC-model boosting-based analogues
of these online p-norm algorithms for any value 2 - p -
1: The PAC-model Perceptron and Winnow analogues mentioned
above are respectively the cases of
this general algorithm.
The case of our algorithm can also be viewed as
a generalization of Jackson and Craven's PAC-model algorithm
for learning "sparse perceptrons" [20]. Their algorithm
boosts using weak hypotheses which are single Boolean lit-
erals; this is similar to what the case of our algorithm
does. Our analysis of the case generalizes their algorithm
to deal with real-valued rather than Boolean input variables
and yields a substantially stronger sample complexity
bound than was established in [20].
Section 2 of this paper contains preliminary material, including
an overview of the online p-norm algorithms from
[15, 16]. In Section 3 we present a simple PAC-model p-norm
algorithm and prove that it is a weak learning algorithm
for all 2 - In Section 4 we apply techniques from
the theory of large margin classification to show how our
learning algorithm can be boosted to a strong learning
algorithm with small sample complexity. Finally, in Section
5 we compare our PAC algorithms with the analogous online
algorithms, extend our algorithm to the case discuss
the relationship between the case of our algorithm
and the Jackson-Craven algorithm for learning sparse
perceptrons.
1.1 RELATED WORK
Several authors have studied linear threshold learning algorithms
which work by combining weak predictors. Freund
and Schapire [14] describe an algorithm which combines intermediate
Perceptron algorithm hypotheses using a weighted
majority vote (so the final classifier is a depth-2 threshold
circuit) and prove bounds on the generalization error of the
resulting classifier. Their algorithm does not use boosting to
combine the Perceptron hypotheses but rather weights them
according to their survival time. Ji and Ma [21] propose a
random-search-and-test approach to find weak classifier linear
threshold functions and combine them by a simple majority
vote (thus also obtaining a depth-2 threshold circuit). Our
approach is closest to that of Jackson and Craven [20] who
use boosting to combine single literals into a strong hypothesis
linear threshold function. As described in Section 5,
the case of our algorithm strengthens and generalizes
their results. More generally, we also note that Freund
and Schapire [12] and Schapire [32] have exhibited a close
relationship between boosting and online learning.
We start with some geometric definitions. For a point ~
to denote the
p-norm of ~
namely
The 1-norm of ~
x is k~xk
the q-norm is dual to the p-norm if 1
hence the
1-norm and the 1-norm are dual to each other and the 2-
norm is dual to itself. In this paper p and q always denote
dual norms. The following facts are well known (e.g. [37]
pp.
H- older Inequality: j~u \Delta ~
Minkowski Inequality: k~u
~
Throughout this paper the example space X is a subset
of linear threshold function over X is a function f
such that
the function sign(z) takes value 1 if z - 0 and takes value
We note that the standard definition of a linear
threshold function allows a nonzero threshold, i.e.
can be any real number. However,
any linear threshold function of this more general form over
n variables is equivalent to a linear threshold function with
threshold 0 over our definition incurs no
real loss of generality.
We write kXk p to denote sup ~ x2X k~xk We use the symbol
u;X to denote the quantity
~ x2X
which is a measure of the separation between examples in X
and the hyperplane whose normal vector is ~
u: We assume
throughout the paper that kXk p ! 1; i.e. the set X is
bounded, and that ffi ~
there is some nonzero lower
bound on the separation between the hyperplane defined by
~
u and the examples in X .
2.1 PAC LEARNING
For ~ denote an example oracle which,
when queried, provides a labeled example
where ~ x is drawn according to the distribution D over X: We
say that an algorithm A is a strong learning algorithm for ~ u
on X if it satisfies the following condition: there is a function
X) such that for any distribution D over X; for
A makes at most m(ffl; ffi; ~
calls to EX(~u; D); and with probability at least
A outputs a hypothesis h 1g such that
Pr x2D [h(~x) 6= sign(~u \Delta ~
We say that such a hypothesis
h is an ffl-accurate hypothesis for ~
under D and that
the function m(ffl; ffi; ~
X) is the sample complexity of algorithm
A:
As our main result we describe a strong learning algorithm
and carefully analyze its sample complexity. To do this
we must consider algorithms which do not satisfy the strong
learning property but are still capable of generating hypotheses
that have some slight advantage over random guessing
(such so-called weak learning algorithms were first considered
by Kearns and Valiant in [24]). Let
be a finite sequence of labeled examples from X and let D
be a distribution over S: For we say that
We say that an algorithm A is a (1=2 \Gamma fl)-weak learning
algorithm for ~ u under D if the following condition holds: for
any finite set S as described above and any distribution D on
if A is given D and S as input then A outputs a hypothesis
which is a (1=2 \Gamma fl)-approximator for ~ u
under D: Thus for our purposes a weak learning algorithm
is one which can always find a hypothesis that outperforms
random guessing on a fixed sample.
2.2 ONLINE LEARNING AND p-NORM
ALGORITHMS
In the online model, learning takes place over a sequence
of trials. Throughout the learning process the learner maintains
a hypothesis h which maps X to f\Gamma1; 1g: Each trial
proceeds as follows: upon receiving an example x 2 X the
learning algorithm outputs its prediction - of the
associated label y: The learning algorithm is then given the
true label y 2 f\Gamma1; 1g and the algorithm can update its hypothesis
h based on this new information before the next trial
begins. The performance of an online learning algorithm on
an example sequence is measured by the number of prediction
mistakes which the algorithm makes.
Grove, Littlestone and Schuurmans [16] and Gentile and
Littlestone [15] have studied a family of online algorithms
for learning linear threshold functions (see Figure 1). We refer
to this algorithm, which is parameterized by a real value
as the online p-norm algorithm. Like the well-known
Perceptron algorithm, the online p-norm algorithm updates
its hypothesis by making an additive change to a weight vector
~
z: However, as shown in steps 4-5 of Figure 1, the p-norm
Input parameter: real number p - 2; initial weight vector ~
positive value a ? 0
1. set
2. while examples are available do
3. get unlabeled example ~
4. for all
5. predict -
6. get label y t 2 f\Gamma1; +1g
7. for all
8. set
9. enddo

Figure

1: The online p-norm algorithm.
algorithm does not use the ~ z vector directly for prediction
but rather predicts using a vector ~
w which is a transformed
version of the ~ z vector, namely w
that when
w and
hence the online 2-norm algorithm is the Perceptron algo-
rithm. In [16] it is shown that as p ! 1 the online p-norm
algorithm approaches a version of the Winnow algorithm.
More precisely, the following theorem from [16] gives mistake
bounds for the online p-norm algorithms:
Theorem 1 Let be a sequence
of labeled examples where ~
every example h~x; yi 2 S:
(a) For any 2 - a ? 0; if the online p-norm
algorithm is invoked with input parameters (p; ~ z
then the mistake bound on the example
sequence S is at most
~
(b) For any 2 -
; then the mistake bound on S is at
most
~
z 0
(c) Let ~
suppose that
a is as described in part (b),
then the mistake bound given in (b) converges to
~ u;X
log
log
2.3 FROM ONLINE TO PAC LEARNING
Various generic procedures have been proposed [1, 18, 22]
for automatically converting on-line learning algorithms into
PAC-model algorithms. In these procedures the sample complexity
of the resulting PAC algorithm depends on the mistake
bound of the original on-line learning algorithm. The
strongest general result of this type (in terms of minimizing
the sample complexity of the resulting PAC algorithm) is
the "longest-survivor" conversion due to Kearns, Li, Pitt and
Theorem 2 Let A be an on-line learning algorithm which
is guaranteed to make at most M mistakes. Then there is a
PAC-model learning algorithm A 0 which uses
O
logffi
log M
examples and outputs an ffl-accurate hypothesis with probability
Theorems 1 and 2 yield sample complexity bounds on
a generic PAC-model conversion of the online p-norm algo-
rithm. We now describe a completely different PAC-model
algorithm which has remarkably similar sample complexity
bounds.
3 A PAC-MODEL p-NORM WEAK
The p-norm weak learning algorithm is motivated by the following
simple idea: Suppose that
is a collection of labeled examples where y
for each replacing each negative
example by the equivalent positive example
to obtain a new collection S 0 of examples. Let
~
be the average location of an example in S 0 ; i.e. ~
z is
the "center of mass" of every example in S 0 must
lie on the same side of the hyperplane ~
as the vector
~
u; it is clear that ~
z must also lie on this side of the hyper-
plane. One might even hope that ~
z; or some related vector,
points in approximately the same direction as the vector ~ u:
Our p-norm weak learning algorithm, which we call WLA,
is presented in Figure 2. As in the online p-norm algorithm,
WLA transforms the vector ~
z to a vector ~
w using the mapping
now show that this simple
algorithm is in fact a weak learner:
Theorem 3 WLA is a (1=2 \Gamma fl)-weak learning algorithm for
~
under D for
1 Littlestone [27] gives a conversion procedure which yields a
PAC sample complexity bound of O(ffl Although
this improves on the result of [22] by a log M factor, Littlestone's
procedure requires the example space X to be finite, which is a
stronger assumption than we make in this paper.
Input parameters: real number p - 2; sequence labeled examples, distribution D
1. set ~
1. for all
2. return hypothesis h(~x) j ~

Figure

2: The p-norm weak learning algorithm WLA.
Proof: Let be a sequence of
labeled examples where ~ x 2 X and
x) for every
let D be a distribution over S: We will
show that the hypothesis h which WLA(p; S; D) returns is a
To see that h maps X into [\Gamma1; 1]; note that for any ~
H-older's inequality implies
Now we show that inequality (1) from Section 2.1 holds.
we have that
and thus2
wk q
Thus it suffices to show that
wk q
We first note that
x jA
and hence the left-hand side of the desired inequality equals
where in the second equality we used the fact that (p \Gamma
p: Consequently the left-hand side can be further simplified
to k~zk p
thus our goal is to
show that k~zk p - ffi ~
x jA
where the last line follows from the H-older inequality, and
the theorem is proved.
We have shown that the simple WLA algorithm is a weak
learning algorithm for our halfspace learning problem. In
this section we use techniques from boosting and large margin
classification to obtain a strong learning algorithm with
small sample complexity.
4.1 BOOSTING TO ACHIEVE HIGH ACCURACY
In a series of important papers Schapire [31] and Freund [10,
11] have given boosting algorithms which transform weak
learning algorithms into strong ones. In this paper we use the
Adaboost algorithm from [13] which is shown in Figure 3;
our notation for the algorithm is similar to that of [34, 35].
The input to Adaboost is a sequence
labeled examples, a weak learning algorithm
WL, and two parameters Given a distribution
outputs a hypothesis h
Adaboost successively generates new distributions
uses WL to obtain hypotheses h t ; and
ultimately outputs as its final hypothesis a linear threshold
function over the h t s.
In [13] Freund and Schapire prove that if the algorithm
WL is a (1=2 \Gamma fl)-weak learning algorithm (i.e. each call of
WL in Adaboost generates a hypothesis h t such that ffl t -
then the fraction of examples in S which are mis-classified
by the final hypothesis h is at most -: Given this
result, one straightforward way to obtain a strong learning algorithm
for our halfspace learning problem is to draw a sufficiently
large (as specified below) sample S from the example
oracle EX(~u; D) and run Adaboost on S using WLA as
the weak learning algorithm, fl as given in Theorem 3, and
This choice of - ensures that Adaboost's final
hypothesis makes no errors on S; moreover, since each
hypothesis generated by WLA is of the form h t
for some ~ v final hypothesis is of the
Using the well-known
fact that the VC dimension of the class of zero-bias
Input parameters: sequence labeled examples, weak learning algorithm WL: S !
[\Gamma1; 1]; two real values
1. set
log 1
2. for all
3. for do
4. let h t be the output of WL(D t ; S)
5. set ffl
7. for all
normalizing factor (so that D t+1 will be a distribution)
9. enddo
10. output as final hypothesis h(x) j sign(f(x)); where

Figure

3: The Adaboost algorithm.
linear threshold functions over ! n is n; the main result of
implies that with probability at least 1 \Gamma ffi the final hypothesis
h is an ffl-accurate hypothesis for ~
u under D provided
that jSj - c(ffl \Gamma1 (n log(ffl
c ? 0:
This analysis, though attractively simple, yields a rather
crude bound on sample complexity which does not depend
on the particulars of the learning problem (i.e. ~
u and X). In
the rest of this section we use recent results on Adaboost's
ability to generate a large-margin classifier and the generalization
ability of large-margin classifiers to give a much
tighter bound on sample complexity for this learning algorithm

4.2 BOOSTING TO ACHIEVE A LARGE MARGIN
Suppose that is a classifier of the form
We say
that the margin of h on a labeled example hx; yi is yf(x);
note that this quantity is nonnegative if and only if h correctly
predicts the label y associated with x:
The following theorem, which is an extension of Theorem
5 from [34], shows that Adaboost generates large-
margin hypotheses.
Theorem 4 Suppose that Adaboost is run on an example
sequence using a weak learning
algorithm WL: S ! [\Gamma1; 1]: Then for any value ' - 0 we
have
Y
The theorem stated in [34] only covers the case when WL
maps S to f\Gamma1; 1g: We need this more general version because
the weak hypotheses of Theorem 3 map S to [\Gamma1; 1]
rather than f\Gamma1; 1g: The proof of Theorem 4 is given in Appendix
A.
The results of Section 3 imply that if WLA is used as the
learning algorithm in Adaboost, then the value ffl t
will always be at most 1=2 \Gamma fl; and the upper bound of Theorem
4 becomes ((1\Gamma2fl) 1\Gamma' (1+2fl) 1+'
easy lemma is proved in Appendix B:
1=4:
If we set and apply this lemma with the
upper bound of Theorem 4 becomes
obtain the following:
Corollary 6 If Adaboost is run on a sequence S of labeled
examples drawn from EX(~u; D) using WLA as the
learner, fl as defined in Theorem 3 and
then the hypothesis h which Adaboost generates will have
margin at least fl=2 on every example in S:
Proof: The bound on - causes T to be greater than 2
log 1
and consequently the upper bound of Theorem 4 is less than
1=jSj:
In the next subsection we use Corollary 6 and the theory
of large margin classification to establish a bound on the
generalization error of h in terms of the sample size m:
4.3 LARGE MARGINS AND GENERALIZATION
Let F be a collection of real-valued functions on a set X:
A finite set fx is said to be -shattered by
F if there are real numbers r such that for all
(b there is a function f b 2 F such
that
For - 0; the fat-shattering dimension of F at scale -;
denoted fat F (-); is the size of the largest set which is -
shattered by F ; if this is finite, and infinity otherwise. The
fat-shattering dimension is useful for us because of the following
theorem from [4]:
Theorem 7 Let F be a collection of real-valued functions
on X and let D be a distribution over X \Theta f\Gamma1; 1g: Let
be a sequence of labeled examples
drawn from D: With probability at least 1 \Gamma ffi over the
choice of S; if a classifier h(x) j sign(f(x)) with f 2 F
has margin at least - ? 0 on every example in S; then
Pr
d log
8em
d
8m
As noted in Section 4.1, the final hypothesis h which
Adaboost outputs must be of the form
with
x for some ~
each invocation of WLA generates a hypothesis of the form
x with k~v t k q - 1
implies that the vector ~
must satisfy k~vk q - 1
consider the class of functions
ae
~
x 7! ~
oe
If we can bound fat F (-); then given any sample size m;
Theorem 7 immediately yields a corresponding bound on
Pr x2D [h(~x) 6= sign(~u \Delta ~
x)] for our halfspace learning prob-
lem. The following theorem proved in Appendix C gives the
desired bound on fat F (-) :
Theorem 8 Let X be a bounded region in ! n and let F
be the class of functions on X defined in (2) above. Then
fat F (- 2 log 4n
Combining Theorem 3, Corollary 6, and Theorems 7 and
it follows that if our algorithm uses a sample of size
m; then with probability at least 1 \Gamma ffi the hypothesis h which
is generated will satisfy
Pr
~ x2D
O
~
log n log 2 m+ log
Thus we have established the following (where the ~
O-notation
hides log
Theorem 9 The algorithm obtained by applying Adaboost
to WLA using the parameter settings described in Corollary 6
is a strong learning algorithm for ~
u on X with sample complexit

O
~
The sample complexity of our boosting-based p-norm PAC
learning algorithm is remarkably similar to that of the PAC-
transformed online p-norm algorithms of Section 2.1. Up to
log factors both sets of bounds depend linearly on ffl \Gamma1 and
quadratically on k~uk q kXk p =ffi ~
Comparing the bounds in
more detail, we see that the online variant described in part
(a) of Theorem 1 has an extra factor of in its bound
which is not present in the sample complexity of our algo-
rithm. Variant (a) offers the advantage, though, that the user
does not need to know the values of any quantities such as
kXk p or k~uk q in advance in order to run the algorithm. Turning
to part (b) of Theorem 1, we see that if the parameter a
is set appropriately in the online algorithm then the online
bound differs from our PAC algorithm bound only by an extra
factor of
z 0
(again ignoring log factors). Part (c) of Theorem 1 shows that
as even when
~
z 0 is chosen to be We also note that when
\Omega\Gamma557 n) Gentile and Littlestone [15] have given alternative
expressions for the online p-norm bounds in terms of kXk1
and Using an entirely similar analysis the bounds of
our algorithm can be analogously rephrased in this case as
well.
5.1
Since the case of the online p-norm algorithm is precisely
the Perceptron algorithm, the case of our algorithm
can be viewed as a natural PAC-model analogue of
the online Perceptron algorithm. We note that when
the upper bound given in Lemma 12 of Appendix C can be
strengthened to
d \Delta kXk 2 (see Lemma 1.3 of [4] or Theorem
4.1 of [2] for a proof). This means that the fat-shattering
dimension upper bound of Theorem 8 can be improved to- 2
which removes a log factor from the bound of Theorem
9; however this bound will still contain various log factors
because of the log terms in Theorem 7.
5.2
ALGORITHM
At the other extreme, we now define a natural
of our algorithm. Consider the vectors ~
z and ~
w which are
computed by the weak learning algorithm WLA. If we let r
be the number of coordinates z i of ~
z such that jz
then for any i we have
lim
wk q
ae sign(z i )=r if jz
Hence it is natural to consider a version of WLA,
which we denote WLA 0 , in which the vector ~
w is defined by
taking
wise. All of our analysis continues to hold (with minor modifications
described in Appendix D) and we obtain a
strong learning algorithm:
Theorem 9 holds for in place of
WLA.
There is a close relationship between this
and the work of Jackson and Craven on learning sparse
perceptrons [20]. Note that if only one coordinate
of ~
z has jz then the WLA 0 hypothesis is
kXk1 where ' is the signed variable from
which is most strongly correlated under distribution D with
the value of sign(~u \Delta ~
This is very similar to the weak learning
algorithm used by Jackson and Craven in [20], which
takes the single best-correlated literal as its hypothesis (break-
ing ties arbitrarily).
The proof that this "best-single-literal" algorithm used
in [20] is a weak learning algorithm is due to Goldmann,
H-astad and Razborov [17]. However, the proof in [17] assumes
that the example space X is f0; 1g n and the target
vector ~
u has all integer coefficients; thus, as noted by Jackson
and Craven in [20], their algorithm for learning sparse
perceptrons only applies to learning problems which are defined
over discrete input domains. In contrast, our
algorithm can be applied on continuous input domains - the
only restrictions are that the example space X and the target
vector ~ u satisfy
We also observe that Theorem 9 establishes a tighter sample
complexity bound for our strong learning algorithm
than was given in [20]. To see this, let
and suppose that the target vector ~
coefficients, so the algorithm from [20] can be applied. For
this learning problem we have ffi ~ u;X
=\Omega\Gamma20 and
letting Theorem 9 implies that our
learning algorithm has sample complexity roughly s 2 =ffl (ig-
noring log factors). This is a substantial improvement over
the roughly s 4 =ffl sample complexity bound given in [20].
More generally, the sample complexity bound given in [20]
for learning "s-sparse k-perceptrons" is roughly ks 4 =ffl; the
analysis of this paper can easily be extended to establish a
sample complexity bound of roughly ks 2 =ffl for learning s-
sparse k-perceptrons.
6 OPEN QUESTIONS
Our results give evidence of the broad utility of boosting algorithms
such as Adaboost. A natural question is how much
further this utility extends: are there simple boosting-based
PAC versions of other standard learning algorithms? We note
in this context that Kearns and Mansour [23] have shown that
various heuristic algorithms for top-down decision tree induction
can be viewed as instantiations of boosting. Another
goal is to construct more powerful boosting-based PAC algorithms
for linear threshold functions. All of the algorithms
discussed in this paper have an inverse quadratic dependence
on the separation parameter ffi ~
linear-programming based
algorithms for learning linear threshold functions (see, e.g.,
[6, 7, 9, 29, 30]) do not have such a dependence. Is there
a natural boosting-based PAC algorithm for linear threshold
functions with performance bounds similar to those of the
linear-programming based algorithms?

ACKNOWLEDGEMENTS

We warmly thank Les Valiant for helpful comments and suggestions



--R

Machine Learning 2
The Probabilistic Method
"Proc. 36th Symp. on Found. of Comp. Sci."
"Advances in Kernel Methods - Support Vector Learning,"
The perceptron algorithm is fast for nonma- licious distributions
"Proc. 37th Symp. on Found. of Comp. Sci."
Learnability and the Vapnik-Chervonenkis Dimension

"Proc. 38th Symp. on Found. of Comp. Sci."
Boosting a weak learning algorithm by ma- jority
"Fifth Ann. Work. on Comp. Learning Theory"
"Proc. Ninth Ann. Conf. on Comp. Learning Theory"
A decision-theoretic generalization of on-line learning and an application to boosting
"Proc. Eleventh Ann. Conf. on Comp. Learning Theory"
"Proc. 12th Ann. Conf. on Comp. Learning Theory"
"Proc. 10th Ann. Conf. on Comp. Learning Theory"
Majority gates vs. general weighted threshold gates
Space efficient learning algorithms
Probability inequalities for sums of bounded random variables
"Advances in Neural Information Processing Systems 8,"
Combinations of weak classifiers
"Proc. Fourth Int. Workshop on Machine Learning"
"Proc. 28th Symp. on Theor. of Comp.,"
21st ACM Symp. on Theor. of Comp.,"
"Proc. Eighth Ann. Conf. on Comp. Learning Theory"
Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm
Mistake bounds and logarithmic linear-threshold learning algorithms
"Proc. Fourth Ann. Conf. on Comp. Learning Theory"
Halfspace learning
"Comput. Learning Theory and Natural Learning Systems: Volume I: Constraints and Prospects,"
The strength of weak learnability
"Proc. Twelfth Ann. Conf. on Comp. Learning Theory"
"Proc. Twelfth Ann. Conf. on Comp. Learning Theory"
Boosting the margin: a new explanation for the effectiveness of voting methods
"Proc. Eleventh Ann. Conf. on Comp. Learning Theory"
criteria and lower bounds for Perceptron-like learning rules
Advanced Calculus
--TR
linear threshold functions;probably approximately correct learning;boosting