Real Boosting a la Carte with an Application to Boosting Oblique Decision Tree

1 Introduction

Loosely speaking, a boosting algorithm repeatedly trains moderately accurate learners from which it gets its weak hypotheses, and combines them to output a strong classifier which boosts the accuracy to arbitrary high levels [Kearns and Valiant, 1989]. A pioneering paper [Schapire, 1990] proved the existence of such boosting algorithms, and another one drew the roots of their most popular representative: AdaBoost, that builds a linear combination of the predictions of the weak hypotheses [Freund and Schapire, 1997]. Another paper due to [Kearns and Mansour, 1999] proved that some of the most popular top-down decision tree induction algorithms are also boosting algorithms in disguise [Breiman et al., 1984; Quinlan, 1993]. These two kinds of algorithms are outwardly different from each other: while AdaBoost repeatedly modifies weights on the training examples and directly minimizes a convex exponential loss, top-down decision tree induction algorithms do not modify weights on the examples, and they minimize the expectation of a concave, so-called permissible function [Kearns and Mansour, 1999].

This explains why the starting point of this paper is a quite surprising result, as we prove that these two kinds of algorithms are in fact the same algorithm, whose induction is performed on two different classifier "graphs". The apparent perceptual differences in the algorithms stem only from different structural properties of the classifiers. This suggests a generic induction scheme which gives, for many classifiers that meet

Frank Nielsen

SONY CS Labs Inc. Tokyo 141-0022, Japan Nielsen@csl.sony.co.jp

a simple assumption, a corresponding boosting algorithm. Using a recent result due to [Nock and Nielsen, 2006], this algorithm uses real-valued weak hypotheses, but it does not face the repetitive minimization of the exponential loss faced by previous Real boosting algorithms [Friedman et al., 2000; Schapire and Singer, 1999]. When the classifier is an oblique decision tree, the algorithm obtained has three key features: it is fast, simple, and the first provable boosting algorithm that fully exploits this class. This is important, as the problem of inducing oblique decision trees has a longstanding history, and the algorithms available so far are either time consuming or complex to handle formally [Breiman et al., 1984; Cant´u-Paz and Kamath, 2003; Heath et al., 1993; Murthy et al., 1994; Shawe-Taylor and Cristianini, 1998]. The following Section presents definitions; it is followed by a Section on our theoretical results, and a Section that discusses them and gives our boosting algorithm for oblique decision trees; two last Sections discuss experiments, and conclude. For the sake of clarity, proofs have been postponed to an appendix.

2 Definitions and problem statement

Bold-faced variables such as w and x, represent vectors. Unless otherwise stated, sets are represented by calligraphic upper-case alphabets, e.g. X, and (unless explicitely stated) enumerated following their lower-case, such as {xi : i = 1, 2, ...} for vector sets, and {xi : i = 1, 2, ...} for other sets. Consider the following supervised learning setting. Let X denote a domain of observations of dimension n, such as Rn, {0, 1}n, etc. . We suppose a set S of |S| = m examples, with |.| the cardinal notation, defined as S = {si = 〈xi, yi〉 ∈ X × {-1,+1} : i = 1, 2, ...,m}, onto which a discrete distribution w1 is known. "+1" is called the positive class, and "-1" the negative class. Our primary objective is related to building an accurate classifier (or hypothesis) H : X → R. The goodness of fit of H on S may be evaluated by two quantities:

Here, sign(a) = +1 iff a ≥ 0 and -1 otherwise, 1[.] is the 0/1 indicator variable, and E.() is the expectation. (1) is the conventional empirical risk, and (2) is an upperbound, the exponential loss [Schapire and Singer, 1999]. We are interested in the stagewise, greedy fitting of H to S, from scratch. A large number of classes of classifiers have popular induction algorithms whose core procedure follows this scheme, including Decision Trees (DT) [Breiman et al., 1984; Quinlan, 1993], Branching Programs (BP) [Mansour and McAllester, 2002] and Linear Separators (LS) [Freund and Schapire, 1997; Nock and Nielsen, 2006]. Virtually all these procedures share another common-point: the components that are used to grow H are also classifiers. These are the DTs for AdaBoost with trees, the internal node splits for the DTs and BPs (akin to decision stumps), etc.

Now, given some fixed class of classifiers in which we fit H, here is the problem statement. A weak learner (WL) is assumed to be available, which can be queried with a sample S ′ and (discrete) distribution w′ on S ′ ; the assumption of its existence is called a Weak Learning Assumption (WLA). It returns in polynomial time 1 a classifier h on which only the following can be assumed: ε(h,w′ ) ≤ 1/2 - γ for some γ > 0 [Schapire and Singer, 1999]. Given 0 < ϵ < 1, is it possible to build in polynomial time some H with ε(H,w1) ≤ ϵ, after having queried T times WL for classifiers h1, h2, ..., hT , for some T > 0 ? Provided additional assumptions are made for its generalization abilities (see Section "Discussion" below), this algorithm is called a boosting algorithm [Freund and Schapire, 1997; Kearns and Valiant, 1989].

3 Unifying boosting properties

For the sake of clarity, we now plug T in subscript on H; An element of LS is a classifier HT with HT (x) = ∑Tt=1 αtht(x), where αt ∈ R is a leveraging coefficient that may be interpreted as a confidence in ht. An element of DT is a rooted directed tree in which each internal node supports a single boolean test over some observation variable, and each leaf is labeled by a real. The classification of some observation proceeds by following, from the root, the path whose tests it satisfies, until it reaches a leaf which gives its class. Figure 2 (left) presents an example of DT (n = 2), where v1, v2 are Boolean description variables. Finally, Oblique Decision Trees (ODT) generalizes DT, as linear combinations of variables are authorized for the internal nodes, which allows splits that are oblique instead of just axis-parallel [Breiman et al., 1984].

1 For the sake of simplicity, polynomial time means polynomial in the relevant parameters throughout the paper.

Figure 1 gives an abstract view of some of the most popular induction algorithms, or at least of their core procedure which induces a large classifier: AdaBoost with trees [Freund and Schapire, 1997; Schapire and Singer, 1999], C4.5 [Quinlan, 1993], CART [Breiman et al., 1984], OC1 [Murthy et al., 1994], SADT [Heath et al., 1993]; the first algorithm for the induction of ODT dates back to the mid-eighties; it was a descendant of CART [Breiman et al., 1984]. Most of the induction algorithms for DT or ODT integrate a pruning stage; here, we are only interested in the greedy induction scheme. WL has various forms: it induces a decision tree on the whole sample S and on a distribution which is repeatedly modified for AdaBoost; it induces a decision tree with a single internal node (a stump) on the subset of S that reaches leaf ℓ (noted Sℓ) and on a distribution which is not modified for CART and C4.5; it replaces this ordinary, axis-parallel stump, by a linear separator stump (also called stump for the sake of simplicity) for OC1 and SADT. The choice of a split for DT and ODT relies on the repetitive minimization of an "impurity" criterion which is the expectation, over the leaves of the current tree H, of a so-called permissible function [Kearns and Mansour, 1999]:

here, w1,S ′ is the total weight of S ′ in w1 and w+ . is its weight further restricted to the positive class. In the expectation, the weight of a leaf ℓ is w1,Sℓ . The permissible function f : [0, 1] → [0, 1] has to be concave, symmetric around 1/2, and with f(0) = f(1) = 0 and f(1/2) = 1. Examples of permissible functions are f(z) = 4z(1 - z) for Gini index [Breiman et al., 1984], f(z) = -z log z - (1 - z) log(1 - z) for the entropy [Quinlan, 1993] (log base-2), or even f(z) = 2√z(1 - z) for the optimal choice of [Kearns and Mansour, 1999]. Remark that we have εimp(H, w1, f ) ≥ εimp(H, w1, 2 min{z, 1 - z}) = 2ε(H,w1), for any permissible f, and so minimizing (3) amount to minimizing the empirical risk of H as well. The reason why this is a better choice than focusing directly on the empirical risk comes from the concavity of the permissible function [Kearns and Mansour, 1999]. Though seemingly very different from each other, AdaBoost and DT induction algorithms from the CART-family were independently proven to be boosting algorithms [Freund and Schapire, 1997; Kearns and Mansour, 1999; Schapire and Singer, 1999]. So far, no such formal boosting algorithm or proof exist for ODT that would take full advantage of their structure combining oblique stumps and decision trees. For this objective, let us shift to a more general standpoint on our problem, and address the following question: what kind of classifiers may be used to solve it ? Consider the following assumption, that HT represents some kind of local linear classifier:

(assumption A) ∀T > 0, denote HT = {h1, h2, ..., hT } the set of outputs of WL; then, there exists a function which maps any observation to a non-empty subset of HT , gHT : X → 2HT \{∅}. ∀x ∈ X, gHT (x) is required to be computable polynomially in n and the size of HT ; it describes the classification function of HT , in the following way:

By means of words, the classification of HT is obtained by summing the outputs of some elements of HT . Many classifiers satisfy (A), such as decisition trees, decision lists, linear separators, etc.

Definition 1 The decision graph ofHT (onX) is an oriented graph G = (HT , E); an arc (ht, ht′ ) ∈ E iff t < t′ and there exists some x ∈ X such that ht, ht′ ∈ gHT (x) and no ht′′ with t < t′′ < t′ is in gHT (x).

Remark that G is acyclic, and gHT maps each observation of X to some path of G. We also define P as representing the set of paths of G that is mapped from X by gHT :

The simplest case of G is obtained when gHT (x) = HT , ∀x ∈ X: HT is a linear separator, and G a single path from h1 to hT . Examples of classes of classifiers different from linear separators and that fit to (A) include DT and ODT. In this case, G is a tree and weak hypotheses are in fact constant predictions on the tree nodes. Figure 2 (right) displays the way we can represent a DT so as to meet (A). Remark that there exists many possible equivalent transformations of a DT; the way we induce HT shall favor a single one out of all, as follows. We define two types of subsets of S (with p ∈ P and 1 ≤ t ≤ T + 1):

We also extend the weight notation, and let wt′ ,Sp = ∑si∈Sp wt′ ,i and wt′ ,St = ∑si∈St wt′ ,i (with p ∈ P and 1 ≤ t′ ≤ T + 1). We also define h⋆t = maxsi∈St |ht(xi)| ∈ R, the maximal absolute value of ht over St. After [Nock and Nielsen, 2006], we define two notions of margins: the first is the normalized margin ht over S:

With the help of this definition, Figure 3 presents the generic greedy induction of HT . Remark that when HT is a linear separator, G2 is the AdaBoostR boosting algorithm of [Nock and Nielsen, 2006]. The second margin definition is the margin of HT on example 〈x, y〉 [Nock and Nielsen, 2006]:

This margin comes to mind from the relationships between boosting and the logistic prediction HT (x) = log(Pr[y = +1|x]/Pr[y = -1|x]) [Friedman et al., 2000]. In this case, (7) becomes νT (〈x, y〉) = y(Pr[y = +1|x] - Pr[y = -1|x]), whose expectation is the normalized margin (6) of the Bayesian prediction in [-1,+1] (also called gentle logistic approximation [Friedman et al., 2000]). Following [Nock and Nielsen, 2006], we define the margin error of HT (∀θ ∈ [-1, +1]):

and we have ε(HT ,w1) ≤ νw1,HT ,0. Thus, minimizing νw1,HT ,0 would amount to minimize ε(HT , w1) as well. The following Theorem shows much more, as under some weak conditions, we can show that νw1,HT ,θ is minimized for all values of θ ∈ [-1, +1) (and not only for θ = 0).

Theorem 1 After T ≥ 1 queries of WL, the classifier obtained, HT , satisfies:

for any θ ∈ [-1, +1].

(proof in appendix). To read Theorem 1, consider the following WLA for real-valued weak hypotheses, borrowed from [Nock and Nielsen, 2006]:

Under the WLA, Theorem 1 states that νw1,HT ,θ ≤ Kθ exp(- minp∈P |p|γ 2/2), with Kθ constant whenever θ is a constant ∈ [-1,+1). In other words, provided the induction in G2 is performed so as to keep paths with roughly equal size, such as by a breadth-first induction of the decision graph, the margin error is guaranteed to decrease exponentially fast. To see how G2 fits to tree-shaped decision graphs, consider the following assumption:

(assumption B) (i) each ht ∈ HT is a constant, and (ii) G is a rooted tree.

Assumption (B) basically restricts HT to be a tree of any arity, still in which any kind of classifier may be used to split the internal nodes. As in (3), we use notation w+/- . as the index' weight for class "+1" or "-1", respectively.

Theorem 2 Suppose that (A) and (B) hold. Then:

∀x ∈ X and ht is the leaf of gHT (x). Furthermore, (2) simplifies as:

(proof in appendix).

4 Discussion

4.1 Kearns andMansour's algorithm, AdaBoost and G2

The similarity between (12) and (3) with f (z) = 2√z(1 - z) is immediate, and quite surprising as it shows the identity between a convex loss and the expectation of a concave loss. However, this is not a coincidence. Indeed, Theorem 2 shows a rather surprising result: the choice of the weak hypotheses does not impact at all on HT (see (10)). When (A) and (B) hold, the only way to modify HT is thus through its decision graph, i.e. on the choice of the splits of the tree. There is a simple way to choose them, which is to do the same thing as the most popular LS boosting algorithms [Friedman et al., 2000; Schapire and Singer, 1999]: repeatedly minimize the exponential loss in (2). Because of Theorem 2, this amounts to the minimization of the impurity criterion in (3) with f(z) = 2√z(1 - z). This is exactly the DT induction algorithm proposed by [Kearns and Mansour, 1999] that meets the representation optimal bound.

On the other hand, when HT is a linear separator, there is no influence of the decision graph on the induction of HT as it is a single path from h1 to hT . The only way to modify HT is thus through the choice of the weak hypotheses. Suppose that each weak hypothesis has output restricted to the set of classes, {-1,+1}. In this case, αt = (1/2) ln((1 - ε(ht,wt))/ε(ht,wt)) =

argminREw1 (exp(-yht(x))) (Figure 1), and G2 matches exactly discrete AdaBoost [Freund and Schapire, 1997].

Thus, decision trees and linear separators are somehow extremal classifiers with respect to G2 . Finally, when HT is a linear separator without restriction on the weak hypotheses, G2 specializes to AdaBoostR [Nock and Nielsen, 2006].

4.2 All boosting algorithms

In the original boosting setting, the examples are drawn independently according to some unknown but fixed distribution D over X, and the goal is to minimize the true risk ε(HT ,D) with high probability, i.e. we basically wish that ε(HT , D) ≤ ϵ with probability ≥ 1 - δ over the sampling of S [Freund and Schapire, 1997; Kearns and Valiant, 1989]. Two sufficient conditions for a polynomial time induction algorithm to satisfy this constraint are (i) return HT with ε(HT ,w1) = 0, and (ii) prove that structural parameters of the class of classifiers to which HT belongs satisfy particular bounds [Freund and Schapire, 1997; Shawe-Taylor and Cristianini, 1998]. Theorem 1 is enough to prove that (i) holds under fairly general conditions for algorithm G2 in Figure 3 provided WLA holds. For example, T = (2/γ 2) log(1/ϵ) iterations for LS and T = (1/ϵ)2/γ 2 for DT are enough to have ε(HT , w1) ≤ ϵ from Theorem 1. Fixing ϵ < mini w1,i easily yields (i). The bound for LS is the same as AdaBoost (discrete or real) [Schapire and Singer, 1999], while that for DT improves upon the exponent constant of [Kearns and Mansour, 1999]. Finally, (ii) is either immediate, or follows from mild assumptions on G and WL. As a simple matter of fact, (i) and (ii) also hold when inducing ODT with G2 .

4.3 Recursive Boosting and Oblique Decision Trees

The preceeding Subsections suggest that G2 could be used not only to build HT , but also as the core procedure for WL. For example, it comes from Theorem 2 that AdaBoost + trees without pruning (Figure 1) is equivalent to G2 growing linear separators, in which WL is G2 growing a decision tree, in which WL returns any constant weak hypothesis. In the general case, we would obtain a recursive/composite design of the "master" G2 , via G2 itself, and the recursion would end until we reach a WL that can afford exhaustive search for simple classifiers (e.g. axis-parallel stumps, constant classifiers, etc.), instead of calling again G2 . However, G2 can also be used to build the decision graph of HT , in the same recursive fashion. Consider for example the class ODT. The internal nodes' splits are local classifiers from LS that decide the path based on the sign of their output, or equivalently, on the class they would give. This suggest to build the tree with G2 on both the linear separators in the internal nodes of HT (use Sℓ to split leaf ℓ, where the linear separator uses ordinary decision stumps), and on the tree shape as well. Call BoostODT this ODT induction algorithm. It turns out that it brings a boosting algorithm, that takes full advantage of the ODT structure. However, this time, it is enough to assume the WLA one level deeper, i.e. only for the stumps of the linear separators, and not for the splits of the oblique decision tree.

Theorem 3 BoostODT is a boosting algorithm.

The proof, omitted due to the lack of space, builds upon Theorem (1) plus Lemma 2.1 in [Mansour and McAllester, 2002], and structural arguments in [Freund and Schapire, 1997; Shawe-Taylor and Cristianini, 1998]. The proof emphasizes the relative importance of sizes: suppose that each linear separator contains the same number of weak hypotheses (T1), and the tree is complete with T2 internal nodes; then, having

is enough to have ε(HT ,w1) ≤ ϵ. From an experimental standpoint, this suggests to build trees with T1 ≫ T2.

5 Experiments

We have performed comparisons on a testbed of 25 domains with two classes, most of which can be found on the UCI repository of ML databases [Blake et al., 1998]. Comparisons are performed via ten-fold stratified cross-validation, against OC1 and AdaBoost in which the weak learner is C4.5 unpruned. BoostODT was ran for T1 ∈ {50, 200} (the weak hypotheses of the linear separators are decision stumps) and T2 = 4. To make fair comparisons, we ran AdaBoost for a total number of T = 5 boosting iterations. This brings fair comparisons, as an observation is classified by 5 nodes (including leaves) in BoostODT, and 5 unpruned trees in AdaBoost. Before looking at the results, BoostODT has proven to be much faster than OC1 in practice (ten to hundred times faster). OC1's time complexity is O(nm2 logm) [Murthy et al., 1994], without guarantee on its result, while BoostODT's is O(nm) under the WLA, with the guarantee to reach empirical consistency in this case. Complexity reductions have almost the same order of magnitude with respect to SVM based induction of ODT [Shawe-Taylor and Cristianini, 1998]. Table 1 summarizes the results obtained. With rejection probabilities p ranging from less than .05 to less than .005 for the hypothesis H0 that BoostODT does not perform better, the four sign tests comparing both runs of BoostODT to its opponents are enough to display its better performances, and this is confirmed by student paired t-tests. There is more: we can tell from simulated domains that BoostODT performs as better as the domain gets harder. It is the case for the Monks domains, and the LEDeven domains. BoostODT is indeed beaten by both opponents on LEDeven, while it beats both on LEDeven+17 (=LEDeven +17 irrelevant variables).

Looking at these simulated domains, we have drilled down the results of BoostODT. Using (8), we have plotted on Figure Table 1: Results on 25 domains. For each domain, bold faces indicate the lowest errors. In each row "#Wins (T1 = z)", bold faces denote the number of times the corresponding algorithm in column is the best over three columns: BoostODT(T1 = z), OC1 and AdaBoost+C4.5 (z ∈ {50, 200}). Furthermore, the four numbers in parentheses in each row are the number of significant wins (student paired t-test, p = .05), for BoostODT vs OC1, BoostODT vs AdaBoost+C4.5, and OC1 vs BoostODT, AdaBoost+C4.5 vs BoostODT (from left to right).

4 its margin error curves on domain XD6 with variable class noise (see e.g. [Nock and Nielsen, 2006] for a description of the domain), averaged over the test folds [Nock and Nielsen, 2006]. The margin curve obtained is compared to that of the logistic prediction of [Friedman et al., 2000], which can be computed exactly. The approximation of the logistic model by BoostODT is quite remarkable. Indeed, its margin curves display the single stair-shape of a theoretical logistic model for a domain XD6 with 8-13% additional class noise, uniformly distributed among the ODT leaves.

6 Conclusion

Perhaps one main contribution of this paper is to show that formal boosting is within reach using the same unified algorithm, for a wide variety of formalisms not restricted to the most popular included in this paper (such as decision lists [Rivest, 1987], simple rules [Nock, 2002], etc. ). Another contribution, quite surprising, is to show that a boosting algorithm follows immediately even for complex combinations of these formalisms, such as linear combinations of oblique decision trees, decision trees in which splits are decided by decision lists, etc. This is crucial, as our last contribution, the first boosting algorithm for the class of oblique decision trees, contrasts in simplicity with respect to previous approaches on inducing oblique decision trees. In future works, we plan to evaluate the experimental and theoretical potentials of these boosting algorithms for these other formalisms.

Acknowledgments and code availability

R. Nock gratefully thanks Sony CS Labs Tokyo for a visiting grant during which this work was started. Resources related to BoostODT, including related Java classes for the Weka platform, can be obtained from the authors.