1
Introduction
Boosting has proven itself as a powerful tool both from a theoretical and a prac- tical perspective of Machine Learning [11]. From a theoretical perspective, it gives a very clean and elegant model in which one can develop new algorith- mic ideas and even hope to analyze some existing heuristics. From a practical perspective, although the weak learning assumption can rarely be proven, the boosting algorithms have had a dramatic impact on practitioners. In a sense, this work can be viewed as a step towards providing a theoretical explanation to this phenomenon. We prove that under certain conceivable conditions, boosting has some nontrivial performance guarantees even when no weak learners exist. The Probably Approximately Correct (PAC) model [12] developed two sepa- rate models. The first one assumes that the target function belongs to the class studied, which was the original PAC assumption, and tries to drive the error as close to zero as possible. The second allows an arbitrary target function, but rather than shooting for absolute success, compares the error of the learner's hypothesis to that of the best predictor in some pre-specified comparison class of predictors. This model is also known as agnostic learning [8]. When one tries to consider which model is more realistic, it has to be the case that the agnostic model wins. We rarely know if there is a clear target function, let alone if it belongs to some simple class of hypotheses. The aim of this paper is to study the boosting question in an agnostic setting. The first step has to be to define an analogue of the weak learning assumption. In the original formulation, a fixed but unknown target function generated labels, and a weak learner was assumed to achieve error less than 1/2 — γ for any distribution over the instances. We define a β-weak agnostic learner with respect to a hypothesis class F as follows: given any distribution P over instance-label pairs it outputs some hypothesis h ∈ F whose error is at most er P ( F ) + β . Since error of 1/2 can be trivially achieved (let us assume that every concept class we consider contains both the constant 1 and the constant 0 functions), this implies that in order for the answer of the weak learner to convey interesting information it has to be the case that erp(F) is less than 1/2 - β. Note that the β-weak agnostic learner assumption is only an assumption about the learner and not about the hypothesis class F, that is, such learners exist for every hypothesis class, even if we take β = 0. The interesting aspect of such weak learners is their complexity (both sample complexity and computa¬ tional complexity). The search for a 'strong' hypothesis in the agnostic setting is NP hard. More precisely, there are no known learning algorithm that, for a non-trivial hypothesis class F , finds in time polynomial in 1/e a hypothesis in F that has error below er P (F) + ε . Furthermore, for many interesting classes F , for small enough β (in the order of 0.005), unless P = NP there exist no β -weak agnostic learner ( [2], [3]). However, no currently known result rules out the existence of agnostic β -weak learners for these classes once β is sufficiently large (say, β > 0.1). Furthermore, the hardness results cited above rule out only the existence of efficient finders of good hypothesis within a class F . Since the output of a boosting algorithm is a member of a larger class of functions - the convex hull of F, all currently known hardness results are consistent with the existence of efficient algorithms that solve the agnostic learning task for non-trivial classes via boosting. The question is what can one hope to achieve under the β -weak agnostic learner assumption. It seems unreasonable to expect that agnostic weak learners can be always transformed into strong learners, as weak learners exist also for trivial classes, say F that includes only a single hypothesis. On the other hand, clearly we can find a hypothesis whose error is erp(F)+ β, but can we do better? In this paper we answer this question in the affirmative. We show that given a parameter ε, there is an efficient algorithm that, using a β-weak agnostic learner as an oracle, can construct a predictor whose error is at most
c 1 (β)er p (F)c 2 (β) + ε
where c 2 ( β ) = 2(1/2 − β ) 2 / ln(1/β − 1), and c 1 ( β ) is a constant which depends only on β. Note that for small values of er ρ (F) we outperform the naive bound. Our algorithm simply runs AdaBoost [6] for a certain number of pre-specified steps. The interesting part is to show that one can exhibit a significant gain in the accuracy this way. By no means do we think that this is the ultimate answer. A major open problem of this research is whether one can achieve a bound of O(er p (F) + ε) using a β -weak agnostic learner. To motivate our results and model we consider agnostic learning of a general hypothesis class of VC dimension d. Assume that the error-minimization task - finding a member of the class that minimizes the error over a sample of size m - is performed in T(m) time. The naive way to produce a hypothesis h such that er P (h) < er P (F) + ε, is to sample m = Õ (d/ε 2 ) examples, and try to find the best hypothesis from our class. The running time of such a learner is therefore of order T( 4 ). Our approach would be to create β-weak agnostic learner, for some fixed β . For that purpose we need to sample only m' = Õ(d), and the running time of the minimization is T ( Õ ( d )), independent of ε . Applying our boosting result we get a learner that runs in time T ( Õ ( d ) ) × poly (1/c ) for some polynomial poly(), and finds a hypothesis such that er P (h) ≤ c 1 (β)er P (F) c π (β) + ε . The main benefit is that the running time depends fairly weakly on ε . This benefit becomes apparent as erp(F) approaches zero. (A similar result, for the case of er P (F) = 0, is implicit in [10,5]. While they consider the sample complexity, their ideas can be used also for the computational complexity.)
2
Preliminaries
Fix a set X. An example is an element of X x {-1,1} and a sample is a finite sequence of examples.  A hypothesis is a function from X to {-1,1}. For a hypothesis h, and a probability distribution P over X x {-1,1}, define the error of h with respect to P, to be erp(h) = E(z,y)~p(h(x) ≠ y)) Similarly, for a sample S, let ers (h) be the fraction of examples (x, y) in S for which h(x) ≠ y. For a set F of functions from X to {-1,1}, define erp(F) = infhef erp(h) A learning strategy is a mapping from samples to hypotheses; If it is com¬ putable, then it is a learning algorithm. For some domain X and a comparison class F of functions from X to {-1,1}, a β-weak agnostic learning oracle, given as input an oracle for sampling according to some probability distribution P over X × {—1,1}, returns a hypothesis h such that erp(h) < erp(F) + β The following definition places a mild requirement that is satisfied by most common concept classes. Definition 1. Let F be a class of functions from some domain X to {-1,1}. - The F-consistency problem is defined as follows: Input:  A  finite labeled sample S Output: A hypothesis h ∈ F such that ers(h) = 0, if such h exists, and NO otherwise - We say that a class F is con-decidable if the F - consistency problem is decidable Notation: Let H 2 (p) be the binary entropy function, i.e. H 2 (p) = -plog2 (p) — (1 - p) log(1 - p). It is well known that for k < n/2, Ei-o (j) < 2H2(k/n)n

 

Existence of Efficient Agnostic Weak Learners
It should be clear from the definition that, for every hypothesis class F of finite VC-dimension, for every fixed β, a β-weak agnostic learning strategy always exists – simply chose h to minimize er 5 (h) for a sufficiently large sample S drawn independently at random according to P . The interesting question that arises in this context is the computational complexity of weak learning algorithms. Theorem 1. Let F be a con-decidable class with VC-dim(F) = d < ∞. Then, for every β > 0 there exist a β - weak learner for F that succeeds with probability > 1 – δ and runs in time
where t F : N H N is the running time of an algorithm for the consistency problem for the class F, and s(β,d) = c ft , for some constant c Proof. Let d denote the VC-dimension of the class F. Having access to an oracle sampling according to a distribution P, the weak learner starts by asking for a sample S of size s( β, d ). By the standard VC-dimension uniform convergence bounds, such sample size guarantees that with probability exceeding 1/2, for every h ∈ F , |er s (h) — er p (h)| ≤ β /2. Next, the weak learner performs an exhaustive search for Argmin{ers(h) : h E F}. One way of carrying out such a search is as follows: Given a sample S of size m, the algorithm considers all subsets T ⊂ S in order of their size, breaking ties arbitrarily. Once it finds a hypothesis h ∈ F that classifies all the examples in S - T correctly, it returns this h. It follows that the running time of the algorithm can be bounded by t F (| S |) × exp( H 2 (er P ( F ) + β/2)|S|). Finally, using a standard 'test and re-sample' trick, for a multiplicative factor of order ln(1/5), the confidence parameter can be boosted from 1/2 to 1 – δ口(see e.g., [10]). Corollary 1. If F is s con-decidable class having a constant VC-dimension, then, for every β > 0 there exist a β - weak agnostic learner for F that runs in time O(ln(1/δ)) and succeeds with probability > 1 — δ
4
Agnostic Boosting
In this section we prove our main theorem about boosting using β -weak agnostic learner. Theorem 1 above essentially states that for classes of finite VC dimension there are learning algorithms that run in time exponential in a parameter β (and some other parameters) and outputs a hypothesis whose expected error is within an additive factor β from the best hypothesis in the class. The boosting results of this section show that, as long as the additive approximation factor β (or, as it is commonly denoted, ε) is above some threshold, there are learning algorithms whose running time is only polynomial in ε . The threshold for which we can prove these results is a function only of erp(F) and goes to zero as erp(F) does. The algorithm that we analyze is a slight variant of AdaBoost [6]. It uses the oracle for sampling according to P to generate oracles for sampling under a sequence D 1 , D 2 , . . of filtered distributions, and passes these to the weak learner, which in response returns a sequence h1, h2, ... of weak hypotheses. The main intuition is as follows. The generalization guarantee that the algo- rithm has to achieve is sufficiently weak as to allow a trivial hypothesis for input probability distributions that drive the error rate of a weak learner close to 1/2. Consequently, we only have to address input distributions relative to which a β- weak agnostic learner is guaranteed to have small error. In order to carry out the usual analysis of boosting, we have to make sure that this assumption remains valid for the new distributions that are generated by the boosting algorithm. We therefore work out an upper bound on the rate at which the boosting distribu- tions may change. We can keep iterating the boosting steps as long as we do not generate distributions that are too far from the input sample distribution. The final step of our analysis is a calculation of the amount of progress that boosting can achieve under this constraint. Theorem 2. Fix a domain X , and a class F of functions from X to {-1,1}. There is an algorithm A such that, for any probability distribution P over X x {-1,1}, if A is given access to a β-weak agnostic learning oracle for F, and a source of random examples of P, then for any c > 0, in polynomial in 1/c time, with probability at least 1/2, algorithm A returns a hypothesis h such that erp(h) ≤ c 1 (β)erp(F)c 2 (β) + ε, where c 2 ( β ) = 2 (1/2 - β ) 2 / 1 n (1/β - 1), and c 1 (β) is a constant which depends only on β. Proof  We will begin by assuming that the algorithm is also given er P (F) as input. We will discuss how to remove this assumption at the end of the proof (in short, standard guessing and hypothesis testing techniques suffice). We now spell out algorithm A, which is simply AdaBoost [6], with some of the parameters fixed. Let
and
This implies that η; ≥ 0 for i ≤ T. Also
which implies that Algorithm A starts by setting Do to be P, then for t = 0, ..., T, it - passes D ξ to the weak learning algorithm, – gets h ξ in return - generates D t +1 in two steps by first, for each ( x, y ) E X x {-1,1}, setting
then normalizing by setting Z t+1 = E(z,y) D t+1 (x,y) and D t+1 (x,y) = D ξ +1 ( x, y ) / Z ξ . Finally, it outputs a function h obtained through a majority vote over h 1 , …, h T Note that
This implies that for any (x,y), Df+1(x,y) ≤ e 2α , Df(x,y). By induction, for each t < T , D ξ ( x, y ) ≤ e ² ∑ έ = σ ª ' P ( x, y ) Since, by assumption, erd, (hi) < erd, (F) + β, this implies that
and A achieves an edge of at least η t in round t . The performance of AdaBoost [6] guarantees that
Recall that,
where the last identity uses the fact that (1/3 - 1)T < (1/2 - β)/er P (F). In , then er p (h) ≤ ε, completing the proof. In the the case that T = 172-312 ln 1 —ß)/crp(F) In( (1 case that T , then In(1/β —1)
for some constant c 1 ( β ) which depends only on β It is easy to see how to simulate the distributions D 1 , ..., D T , given access to a source of examples for P , in polynomial time, using the rejection method [9], since always e- Ei-i ai > (1/8 - 1)-T/2. Therefore, since T is bounded by a logarithm in 1/e, the time for Algorithm A is polynomially bounded. Recall that we assumed that Algorithm A "knew" erp(F). One can con¬ struct an algorithm that does not need to know er P (F) from A as follows. Note that Algorithm A can use an upper bound b on erp(F), and achieve er P (h) ≤ c 1 (β)b c 2 (β) + γ in poly(1/γ) time. Define φ : [0,1] → [0,c 1 (β)] by φ(x) = c 1 (β)x c 2 (β). Consider the Algorithm B that uses as guesses for b all val- ues of φ-1(z) for multiples z of ε/4, sets γ = ε/4, calls Algorithm A for each of these values, then uses hypothesis testing as in [7] to estimate which of those roughly 4/ε hypotheses is the best. One of the poly(1/ε) runs would produce a hypothesis with error at most c 1 ( β )er ρ ( F )c 2 (β) + ε /2, and hypothesis testing can be applied to find from among a set of hypothesis with one such good one a hypothesis with error at most c 1 (β)er ρ (F)c 2 (β) + ε口We can now apply the bound of Theorem 1 on the time complexity of weak learners to the above boosting result to obtain: Corollary 2. Let F be a con-decidable class so that VC-dim(F) = d < ∞. For every β > 0, there is an algorithm A such that, for any probability distribution P over X × {-1,1}, if A is given access to a source of random examples of P, A runs in time
(where t F : N → N is the running time of an algorithm for the consistency problem for the class F, and s(β,d,δ) = πξτ (d + ln(ξ)), for some constant c). Also, with probability at least 1/2, algorithm A returns a hypothesis h such that erp(h) ≤ c 1 (β)erp(F)c 2 (β) + ε, where c 2 ( β ) = 2 (1/2 - β ) 2 / ln(1/β - 1), and c 1 (β) is a constant which depends only on β. Proof Sketch. We apply the boosting algorithm to the agnostic weak learning algorithm of Theorem 1. However, one has to make sure that the success proba¬ bility of the weak learner is high enough to endure the T many iterations required by the boosting algorithm. For that purpose, we have to chose the δ of the weak learner to be of order (ln(l/c)))-1.口Corollary 3. Let F be a con-decidable class of functions from some domain X to {-1,1}. If the VC dimension of F is finite then, for every β > 0, there is an algorithm A such that, for any probability distribution P over X × {-1,1}, if A is given access to a source of random examples of P, then for any e > 0, in polynomial in 1/c time, with probability at least 1/2, algorithm A returns a hypothesis h such that
where c 2 (β) = 2 (1/2 - β) 2 / ln(1/β - 1), and c 1 (β) is a constant which depends only on β
5
Learning with large-margin half-spaces
As a first application of the above results we briefly present a learning algorithm for learning with margin half-spaces. In this learning problem the instance space is the n-dimensional Euclidean unit ball and the learner is assessed by compari- son with the best half-space, but where examples falling within a given distance γ of a separating hyper-plane in the comparison class are counted as wrong. The motivation for such learning is that, as agnostically learning with half- spaces is computationally infeasible (see [3]), a hypothesis half-space that is computed an efficient learner is bound to make more mistakes that the best possible hyper-plane. However, it may be argued that making mistakes near the boundary of a separating hyper-plane is less costly than erring on points that are classified with large margins. The margin half-space learning model can be viewed as a model that adopts this view by ignoring mistakes on points that are within γ margins of a comparison half-space. Previous work [4] provided an algorithm for this problem whose hypothesis h satisfies er p (h) < er p (H γ,n) + ε in (1/ε) O (1/γ²) time. Using the basic margin generalization bound (see [1]) it is not difficult to prove the following weak learner result. Let Bn be the unit ball in Rn and, for a probability distribution P over Bn x {-1,1}, let erp(Hy,n) denote the minimal P- expected error of any half- space in Rn, when points that have margin less than γ to the half-space are counted as errors. Theorem 3. Choose γ,ε > 0. There is a polynomial-time learning algorithm A and a polynomial p such that, for any natural number n, any δ > 0, and any probability distribution P over Bn x {-1,1} (where Bn is the unit ball in Rn), if p(n, 1/5) examples are drawn according to P and passed to algorithm A, then with probability at least 1 - δ, the output h of algorithm A satisfies
er p (h) ≤ er(H γ ,n) + ε.
We can now apply our boosting technique, namely Theorem 2, to obtain: Theorem 4. Choose γ > 0. There is a learning algorithm that runs in time poly(cf(1/72),1/c) time, while achieving erp(h) < c2erp(Hy,n)ca + c, where c1, c2 and c3 are constants
Acknowledgments
We thank Peter Bartlett and Nadav Eiron for valuable conversations. Phil Long acknowledges the support of National University of Singapore Aca- demic Research Fund Grant RP252-000-070-107. Yishay Mansour acknowledges the support of the Israeli Science Foundation.