On the Doubt about Margin Explanation of Boosting

Introduction

The AdaBoost algorithm (Freund and Schapire, 1996, 1997), which aims to construct a “strong” classifier by combining some “weak” learners (slightly better than random guess), is a representative of ensemble methods (Zhou, 2012) and has been one of the most influential classification algorithms (Caruana and Niculescu-Mizil, 2006; Wu and Kumar, 2009), and it has exhibited excellent performance both on benchmark datasets and real applications (Bauer and Kohavi, 1999; Dietterich, 2000).

Many studies are devoted to understanding the mysteries behind the success of AdaBoost, among which the margin theory proposed by Schapire et al. (1998) has been very influential. For example, AdaBoost often tends to be empirically resistant (but not completely) to overfitting (Quinlan, 1996; Drucker and Cortes, 1996; Breiman, 1998), i.e., the generalization error of the combined learner keeps decreasing as its size becomes very large and even after the training error has reached zero; it seems violating the Occam’s razor (Blumer et al., 1987), i.e., the principle that less complex classifiers should perform better. This remains one of the most famous mysteries of AdaBoost. The margin theory provides the most intuitive and popular explanation to this mystery, that is: AdaBoost tends to improve the margin even after the error on training sample reaches zero.

However, Breiman (1999) raised serious doubt on the margin theory by designing arc-gv, a boosting-style algorithm. This algorithm is able to maximize the minimum margin, i.e., the smallest margin over the training data (The formal definition will be given in Eqn. 2), but its generalization error is high on empirical datasets, and similar experimental evidence has also been observed in (Grove and Schuurmans, 1998). Thus, Breiman (1999) concluded that the margin theory for AdaBoost failed. Breiman’s argument was backed up with a minimum margin bound, which is sharper than the generalization bound given by Schapire et al. (1998), and a lot of experiments. Garg and Roth (2003) presented a margin-distribution algorithm based on a data-dependent complexity measure. Later, Reyzin and Schapire (2006) found that there were flaws in the design of experiments: Breiman used CART trees (Breiman et al., 1984) as base learners and fixed the number of leaves for controlling the complexity of base learners. However, Reyzin and Schapire (2006) found that the trees produced by arc-gv were usually much deeper than those produced by AdaBoost. Generally, for two trees with the same number of leaves, the deeper one is with a larger complexity because more judgements are needed for making a prediction. Therefore, Reyzin and Schapire (2006) concluded that Breiman’s observation was biased due to the poor control of model complexity. They repeated the experiments by using decision stumps for base learners, considering that decision stump has exactly two leaves and thus with a fixed complexity, and observed that though arc-gv produced a larger minimum margin, its margin distribution was quite poor. Nowadays, it is well-accepted that the margin distribution is crucial to relate margin to the generalization performance of AdaBoost. To support the margin theory, Wang et al. (2011) presented a sharper bound in term of Emargin (the formal definition will be given in Theorem 3), which was believed to be relevant to margin distribution.

In this paper, we first present the $k$th margin bound and further study its relationship to previous work such as the minimum margin bound and Emargin bound. Then, by using empirical Bernstein bounds, we present a new generalization error bound for voting classifier, which considers exactly the same factors as Schapire et al. (1998), but is sharper than the bounds of Schapire et al. (1998) and Breiman (1999). Therefore, we defend the margin-based explanation against Breiman’s doubt. Moreover, we provide a generalization error bound, by incorporating other factors such as average margin and variance, which are heavily relevant to the whole margin distribution. We also give a margin distribution bound for generalization error of voting classifiers in finite VC-dimension space. It is also worth mentioning that our new empirical Bernstein bounds improve the main results of (Maurer and Pontil, 2009; Audibert et al., 2009), with a simpler proof, and we present empirical Bernstein bounds for finite VC-dimension space; these results can be interesting, independently to the main purpose of the paper, to the machine learning community.

The rest of this paper is organized as follows. We begin with some notations and background in Sections 2 and 3, respectively. Then, we prove the $k$th margin bound and discuss on its relation to previous bounds in Section 4. Our main results are presented in Section 5, and detailed proofs are provided in Section 6. We conclude in Section 7.

Notations

Let $\mathcal{X}$ and $\mathcal{Y}$ denote an input space and output space, respectively. In this paper, we focus on binary classification problems, i.e., $\mathcal{Y}=\{+1,-1\}$. Denote by $D$ an (unknown) underlying probability distribution over the product space $\mathcal{X}\times\mathcal{Y}$. A training sample of size $m$

is drawn independently and identically (i.i.d) according to the distribution $D$. We use $\Pr_{D}[\cdot]$ to refer as the probability with respect to $D$, and $\Pr_{S}[\cdot]$ to denote the probability with respect to uniform distribution over the sample $S$. Similarly, we use $E_{D}[\cdot]$ and $E_{S}[\cdot]$ to denote the expected values, respectively. For an integer $m>0$, we set $[m]=\{1,2,\cdots,m\}$.

The Bernoulli Kullback-Leibler (or KL) divergence is defined as

For a fixed $q$, we can easily find that $KL(q||p)$ is a monotone increasing function for $q\leq p<1$, and thus, the inverse of $KL(q||p)$ for the fixed $q$ is given by

Let $\mathcal{H}$ be a hypothesis space. A base learner is a function which maps a distribution over $\mathcal{X}\times\mathcal{Y}$ onto a function $h\colon\mathcal{X}\rightarrow\mathcal{Y}$. In this paper, we only focus on binary base classifiers, i.e., the outputs are in $\{-1,1\}$. Let $\mathcal{C}(\mathcal{H})$ denote the convex hull of $H$, i.e., a voting classifier $f\in\mathcal{C}(\mathcal{H})$ is of the following form

For $N\geq 1$, denote by $\mathcal{C}_{N}(\mathcal{H})$ the set of unweighted averages over $N$ elements from $\mathcal{H}$, that is

For voting classifier $f\in\mathcal{C}(\mathcal{H})$, we can associate with a distribution over $\mathcal{H}$ by using the coefficients $\{\alpha_{i}\}$, denoted by $\mathcal{Q}(f)$. For convenience, $g\in\mathcal{C}_{N}(\mathcal{H})\sim\mathcal{Q}(f)$ implies $g=\sum_{j=1}^{N}{h_{j}}/{N}$ where $h_{j}\sim\mathcal{Q}(f)$.

For an example $(x,y)$, the margin with respect to the voting classifier $f=\sum\alpha_{i}h_{i}(x)$ is defined as $yf(x)$; in other words,

which shows the difference between the weights of base learners that classify $(x,y)$ correctly and the weights of base learners that misclassify $(x,y)$. Therefore, margin can be viewed as a measure of the confidence of the classification. Given a sample $S=\{(x_{1},y_{1}),(x_{2},y_{2}),\cdots,(x_{m},y_{m})\}$, we denote by $\hat{y}_{1}f(\hat{x}_{1})$ the minimum margin and $E_{S}[yf(x)]$ the average margin, which are defined respectively as follows:

Background

In the statistics community, great efforts have been devoted to understanding how and why AdaBoost works. Friedman et al. (2000) made an important stride by viewing AdaBoost as a stagewise optimization and relating it to fitting an additive logistic regression model. Various new boosting-style algorithms were developed by performing a gradient decent optimization of some potential loss functions (Mason et al., 1999; Rätsch et al., 2001; Buhlmann and Yu, 2003). Based on this optimization view, some boosting-style algorithms and their variants have been shown to be Bayes’s consistent under different settings (Breiman, 2000; Jiang, 2004; Zhang, 2004; Lugosi and Vayatis, 2004; Bartlett et al., 2006; Bickel et al., 2006; Bartlett and Traskin, 2007; Mukherjee et al., 2011), i.e., those studies theoretically ensure that boosting is asymptotically convergent to the Bayes’s classifiers. However, such theories can not be used to explain the resistance of AdaBoost to overfitting for small sample problems, and some statistical views have been questioned by Mease and Wyner (2008) with empirical evidences. In this paper, we focus on margin theory.

Algorithm 1 provides a unified description of AdaBoost and arc-gv. The only difference between them lies in the choice of $\alpha_{t}$. In AdaBoost, $\alpha_{t}$ is chosen by

where $\gamma_{t}=\sum_{i=1}^{m}D_{t}(i)y_{i}h_{t}(x_{i})$ is called the edge of $h_{t}$, which is an affine transformation of the error rate of $h_{t}(x)$. However, Arc-gv sets $\alpha_{t}$ in a different way. Denote by $\rho_{t}$ the minimum margin of the voting classifier of round $t-1$, that is,

Schapire et al. (1998) proposed the first margin theory for AdaBoost and upper bounded the generalization error as follows:

(Schapire et al., 1998) For any $\delta>0$ and $\theta>0$, with probability at least $1-\delta$ over the random choice of sample $S$ with size $m$, every voting classifier $f\in\mathcal{C}(\mathcal{H})$ satisfies the following bound:

Breiman (1999) provided the minimum margin bound for arc-gv by Theorem 2 with our notations.

then, for any $\delta>0$, with probability at least $1-\delta$ over the random choice of sample $S$ with size $m$, every voting classifier $f\in\mathcal{C}(\mathcal{H})$ satisfies the following bound:

Empirical results show that arc-gv probably generates a larger minimum margin but with higher generalization error, and Breiman’s minimum bound is $O({\ln m}/{m})$, sharper than $O(\sqrt{{\ln m}/{m}})$ in Theorem 1. Thus, Breiman cast serious doubt on margin theory. To support the margin theory, Wang et al. (2011) presented a sharper bound in term of Emargin by Theorem 3, which was believed to be related to margin distribution. Notice that the factors considered by Wang et al. (2011) are different from that considered by Schapire et al. (1998) and Breiman (1999).

(Wang et al., 2011) If $8<|\mathcal{H}|<\infty$, then for any $\delta>0$, with probability at least $1-\delta$ over the random choice of the training set $S$ of size $m>1$, every voting classifier $f\in\mathcal{C}(\mathcal{H})$ such that

and \hat{\theta}(q)=\sup\big{\{}\theta\in\big{(}\sqrt{{8}/{|\mathcal{H}|}},1\big{]}\colon\Pr_{S}[yf(x)\leq\theta]\leq q\big{\}}. Also, the Emargin is given by $\theta^{*}\in\arg\inf_{q\in\{q_{0},q_{0}+\frac{1}{m},\cdots,1\}}KL^{-1}(q;u[\hat{\theta}(q)])$.

Instead of the whole function space, much work developed margin-based data-dependent bounds for generalization error, e.g., empirical cover number (Shawe-Taylor and Williamson, 1999), empirical fat-shattering dimension (Antos et al., 2002), Rademacher and Gaussian complexities (Koltchinskii and Panchanko, 2002, 2005), etc. Some of these bounds are proven to be sharper than Theorem 1, but it is hard to show that these bounds are sharper than the bounds of Theorems 2 and 3, and fail to explain the resistance of AdaBoost to overfitting.

The k𝑘kth Margin Bounds

Given a sample $S$ of size $m$, we define the $k$th margin $\hat{y}_{k}f(\hat{x}_{k})$ as the $k$th smallest margin over sample $S$, i.e., the $k$th smallest value in $\{y_{i}f(x_{i}),i\in[m]\}$. The following theorem shows that the $k$th margin can be used to measure the performance of a voting classifier, whose proof is deferred in Section 6.1.

For any $\delta>0$ and $k\in[m]$, if $\theta=\hat{y}_{k}f(\hat{x}_{k})>\sqrt{{8}/{|\mathcal{H}|}}$, then with probability at least $1-\delta$ over the random choice of sample with size $m$, every voting classifier $f\in\mathcal{C}(\mathcal{H})$ satisfies the following bound:

Particularly, when $k$ is constant with $m>4k$, we have

Here, we present the $k$th margin bound to link previous results on margin bounds, and it is interesting to study the relation between Theorem 4 and previous results, especially Theorems 2 and 3. It is straightforward to get a result similar to Breiman’s minimum margin bound in Theorem 2, by setting $k=1$ in Eqn. 5:

For any $\delta>0$, if $\theta=\hat{y}_{1}f(\hat{x}_{1})>\sqrt{{8}/{|\mathcal{H}|}}$, then with probability at least $1-\delta$ over the random choice of sample $S$ with size $m$, every voting classifier $f\in\mathcal{C}(\mathcal{H})$ satisfies the following bound:

Notice that when $k$ is a constant, the bound in Eqn. 5 is $O({\ln m}/{m})$ and the only difference lies in the coefficient. Thus, there is no essential difference to select constant $k$th margin (such as the $2$nd margin, the $3$rd margin, etc.) to measure the confidence of classification for large-size sample.

Based on Theorem 4, it is not difficult to get a result similar to the Emargin bound in Theorem 3 as follows:

For any $\delta>0$, if $\theta_{k}=\hat{y}_{k}f(\hat{x}_{k})>\sqrt{8/|\mathcal{H}|}$, then with probability at least $1-\delta$ over the random choice of the sample $S$ with size $m$, every voting classifier $f\in\mathcal{C}(\mathcal{H})$ satisfies the following bound:

From this corollary, we can easily understand that the Emargin bound ought to be tighter than the minimum margin bound because the former takes the infimum over all $k\in[m]$ while the latter only focuses on the minimum margin. Intuitively, the bound of Corollary 2 might be sharper than that of Corollary 1 if the minimum margin is very small whereas some $k$th margin is very large. We also notice that, as shown by Eqn. 2, the minimum margin can also be expressed as taking the infimum over all margin, whereas it is well accepted that the minimum margin bound is a single-margin bound.

Main Results

We begin with the standard deviation bounds as follows:

For independent random variables $X_{1},X_{2},\ldots,X_{m}$ ($m\geq 5$) with values in $$, and for$\delta\in(0,1)$, we have

where the sample variance $\hat{V}_{m}=\sum_{i\neq j}{(X_{i}-X_{j})^{2}}/{2m(m-1)}$.

The detailed proof is presented in Section 6.2. This theorem improves the results of (Maurer and Pontil, 2009, Theorem 10), especially for Eqn. 6. Based on this result, we can derive the following empirical Bernstein bounds, with proof deferred to Section 6.3.

For independent random variables $X_{1},X_{2},\ldots,X_{m}$ ($m\geq 5$) with values in $$, and for$\delta\in(0,1)$, with probability at least$1-\delta$ we have

where $\hat{V}_{m}=\sum_{i\neq j}(X_{i}-X_{j})^{2}/2m(m-1)$.

For identical and independent distribution (i.i.d) variables, we have

For i.i.d. random variables $X,X_{1},X_{2},\ldots,X_{m}$ ($m\geq 5$) with values in $$, and for$\delta\in(0,1)$, with probability at least$1-\delta$ we have

where $\hat{V}_{m}=\sum_{i\neq j}(X_{i}-X_{j})^{2}/2m(m-1)$.

There are two results (Audibert et al., 2009; Maurer and Pontil, 2009) closely related to Theorem 6 (or Corollary 3). Audibert et al. (2009) presented the first empirical Bernstein bound and applied to analyze multi-armed bandit algorithms. Soon after, Maurer and Pontil (2009) improved the constants and explored the sample variance penalization methods. Comparing with these results, our bounds in Eqns. 8 and 9 are with better constants and the technique of proof is simpler.

Based on this Corollary 3, we can derive the following corollary for the finite function space:

Let $S=\{X_{1},\ldots,X_{m}\}$ $(m\geq 5)$ be drawn i.i.d. from a distribution $\mathcal{D}$ over $\mathcal{X}$, and let $\mathcal{H}=\{h\colon\mathcal{X}\to\}$ be a finite function space. For any $\delta\in(0,1)$, every $h\in\mathcal{H}$ satisfies the following bound with probability at least $1-\delta$:

where $\hat{V}_{m}(h)=\sum_{i\neq j}(h(X_{i})-h(X_{j}))^{2}/2m(m-1)$.

Then, we get a new generalization bound for infinite hypothesis space with finite VC-dimension, with proof deferred to Section 6.4.

Let $S=\{X_{1},\ldots,X_{m}\}$ $(m\geq 5)$ be drawn i.i.d. from a distribution $\mathcal{D}$ over $\mathcal{X}$, and let $\mathcal{H}=\{h\colon\mathcal{X}\to\{0,1\}\}$ be a hypothesis space with finite VC-dimension $d$. For any $\delta\in(0,1)$, every $h\in\mathcal{H}$ satisfies the following bound with probability at least $1-\delta$:

where $\hat{V}_{m}(h)=\sum_{i\neq j}(h(X_{i})-h(X_{j}))^{2}/2m(m-1)$.

We now present our first margin bound for AdaBoost as follows:

For any $\delta>0$, with probability at least $1-\delta$ over the random choice of sample $S$ with size $m\geq 5$, every voting classifier $f\in\mathcal{C}(\mathcal{H})$ satisfies the following bound:

This proof is based on the techniques developed by Schapire et al. (1998), and the main difference is that we utilize the empirical Bernstein bound of Eqn. 8 in Theorem 6 for the derivation of generalization error. The detailed proof is deferred to Section 6.5.

It is noteworthy that Theorem 8 shows that the generalization error can be bounded in term of the empirical margin distribution $\Pr_{S}[yf(x)\leq\theta]$, the training sample size and the hypothesis complexity; in other words, this bound considers exactly the same factors as Schapire et al. (1998) in Theorem 1. However, the following corollary shows that, the bound in Theorem 8 is sharper than the bound of Schapire et al. (1998) in Theorem 1, as well as the minimum margin bound of Breiman (1999) in Theorem 2.

For any $\delta>0$, if the minimum margin $\theta_{1}=\hat{y}_{1}f(\hat{x}_{1})>0$ and $m\geq 5$, then we have

where $\mu={8\ln m}\ln(2|\mathcal{H}|)/{\theta^{2}}+\ln({2|\mathcal{H}|}/{\delta})$ and $\mu_{1}={8\ln m}\ln(2|\mathcal{H}|)/{\theta_{1}^{2}}+\ln({2|\mathcal{H}|}/{\delta})$; moreover, if

This proof is deferred to Section 6.6. From Eqn. 10, we can see clearly that the bound of Theorem 8 is $O(\ln m/m)$, sharper than the bound of Schapire et al. (1998) $O(\sqrt{\ln m/m})$ in Theorem 1. In fact, we could also guarantee that bound of Theorem 8 is $O(\ln m/m)$ even under weaker assumption that $\hat{y}_{k}f(\hat{x}_{k})>0$ for some $k\leq O(\ln m)$.

It is also noteworthy Eqns. 11 and 12 are the conditions of Theorem 2, and the term \exp\Big{(}\frac{\theta_{1}^{2}}{4\ln(2|\mathcal{H}|)}\ln\frac{|\mathcal{H}|}{\delta}\Big{)}\leq(\frac{e}{\delta})^{\frac{1}{4}} in Eqn. 13, which is small for many real applications, e.g., it is less than $13$ even if $\delta=0.0001$. Eqn. 14 shows that the bound of Theorem 8 is sharper than Breiman’s minimum margin bound of Theorem 2.

Breiman (1999) doubted the margin theory because of two recognitions: i) the minimum margin bound of Breiman (1999) is sharper than the margin distribution bound of Schapire et al. (1998), and therefore, the minimum margin is more essential than margin distribution to characterize the generalization performance; ii) arc-gv maximizes the minimum margin, but demonstrates worse performance than AdaBoost empirically. However, our result shows that the margin distribution bound in Theorem 1 can be greatly improved such that it is even sharper than the minimum margin bound, and therefore, it is natural that AdaBoost outperforms arc-gv empirically on some datasets; in a word, our results provide a complete answer to Breiman’s doubt on margin theory.

The Emargin bounds of Wang et al. (2011) are also proven to be sharper than those of Schapire et al. (1998) and Breiman (1999). The main difference between Theorem 8 and the Emargin bounds lies in the consideration of different factors for margin theory, e.g., Theorem 8 considers exactly the same factors as Schapire et al. (1998), whereas Wang et al. (2011) considered the Emargin as the key factor. Moreover, Theorem 8 is advantageous in that its margin interval is wider than that of EmarginThis observation owes to a reviewer. Note that it is not easy to directly compare Theorem 8 and the Emargin bounds because it is difficult to get a closed-form for the $D^{-1}(p||q)$ term contained in the Emargin bounds, whereas Theorem 8 is relatively easier to estimate.

It is well-accepted that the margin distribution is crucial to relate margin to the generalization performance of AdaBoost, whereas it is unclear how to measure the “goodness” of a margin distribution. The first-order and second-order statistics, i.e., the average margin and variance, are natural and intuitive measures. Indeed, Reyzin and Schapire (2006) has recommended to take the average margin for a characterization for the margin distribution. However, there is no theory, to the best of our knowledge, to support that a larger average margin or a smaller variance implies a smaller generalization error. The following theorem fills the gap for such theory:

For any $\delta>0$, with probability at least $1-\delta$ over the random choice of sample $S$ with size $m\geq 5$, every voting classifier $f\in\mathcal{C}(\mathcal{H})$ satisfies the following bound:

The detailed proof is deferred to Section 6.7. It is easy to find in almost all boosting experiments that the average margin $E_{S}[yf(x)]$ is positive. Thus, the bound of Theorem 9 can be sharper for larger average margin. The statistics $\hat{\mathcal{I}}(\cdot)$ reflects the margin variance in some sense, and the term including $\hat{\mathcal{I}}(\cdot)$ can be small or even vanished except for a small interval when the variance is small. This new generalization error bound depends not only on the sample size and the complexity of base classifiers, but also on the average margin, variance, and empirical margin distribution; this implying that, completely explaining AdaBoost’s resistance to overfitting is more difficult than what has been expected and disclosed by previous theoretical results.

Theorem 9 also provides a theoretical support to the suggestion of Reyzin and Schapire (2006); that is, the average margin can be used to measure the performance. It is noteworthy that, however, merely considering the average margin is insufficient to bound the generalization error tightly, as shown by the simple example in Figure 1. Indeed, as this theorem discloses, “average” and “variance” are two important statistics to capture a distribution, and it is reasonable that both the average margin and margin variance are considered.

We have the following corollary with proof presented in Section 6.8.

If the minimum margin $\theta_{1}=\hat{y}_{1}f(\hat{x}_{1})>0$, then, for any $\delta>0$, with probability at least $1-\delta$ over the random choice of sample $S$ with size $m\geq 5$, every voting classifier $f\in\mathcal{C}(\mathcal{H})$ satisfies the following bound:

where $\mu_{1}={144}\ln m\ln(2|\mathcal{H}|)/{\theta_{1}^{2}}+\ln({2|\mathcal{H}|}/\delta)$, $\mu$ and $\hat{\mathcal{I}}(\theta)$ are given in Theorem 9.

This corollary shows that the bounds of Theorem 9 are $O(\ln m/m)$, comparable to the Emargin bounds (Wang et al., 2011) and the bounds of Theorem 8, but with different constants. The main difference lies in the consideration of different factors, as we have considered the average margin and variance, that are better for the characterization of margin distribution. It is noteworthy that the best bounds for AdaBoost and arc-gv are both $O(\ln m/m)$ whereas AdaBoost outperforms arc-gv empirically because AdaBoost tends to improve the margin distribution; this provides an example showing that it is very important to consider factors that are heavily relevant to the whole distribution. We also notice that a recent study in (Shen and Li, 2010) provides empirical evidence to support our theoretical result. Indeed, designing new Boosting algorithms that maximize average margin but minimize variance simultaneously is an interesting direction, and (Shivaswamy and Jebara, 2011) may shed some light.

Finally, we generalize our main margin bounds to the case when the space of base classifiers has finite VC-dimension. The detailed proofs are presented in Section 6.9.

If the base classifiers space $\mathcal{H}$ has finite VC-dimension $d$, then for any $\delta>0$, with probability at least $1-\delta$ over the random choice of sample $S$ with size $m\geq 5$, every voting classifier $f\in\mathcal{C}(\mathcal{H})$ satisfies the following bound:

where \mu=\frac{8\ln m}{\theta^{2}}\big{(}\ln 2+d\ln(2em/d)\big{)}+\ln\big{(}\frac{8}{\delta}(1+\frac{8\ln m}{\theta^{2}})\big{)}.

If the base classifiers space $\mathcal{H}$ has finite VC-dimension $d$, then for any $\delta>0$, with probability at least $1-\delta$ over the random choice of sample $S$ with size $m\geq 5$, every voting classifier $f\in\mathcal{C}(\mathcal{H})$ satisfies the following bound:

Proofs

In this section, we provide the detailed proofs for the main theorems and corollaries. First, we present a series of useful lemmas as follows:

Let $X,X_{1},X_{2},\ldots,X_{m}$ be $m+1$ i.i.d random variables with $X\in$. Then, for any $\epsilon>0$, we have

For independent random variables $X,X_{1},X_{2},\ldots,X_{m}$ with $X_{i}\in$, and for any $\delta>0$, the followings hold with probability at least $1-\delta$

where $V(X)$ denotes the variance $\sum_{i=1}^{m}E[(X_{i}-E[X_{i}])^{2}]/m$.

For $f\in\mathcal{C}(\mathcal{H})$, let $g\in\mathcal{C}_{N}(\mathcal{H})$ be drawn i.i.d according to distribution $\mathcal{Q}(f)$. If $\hat{y}_{k}f(\hat{x}_{k})\geq\theta$ and $\hat{y}_{k}g(\hat{x}_{k})\leq\alpha$ with $\theta>\alpha$, then there is an example $(x_{i},y_{i})$ in $S$ such that $y_{i}f(x_{i})\geq\theta$ and $y_{i}g(x_{i})\leq\alpha$.

Proof: There exists a bijection between $\{y_{j}f(x_{j})\colon j\in[m]\}$ and $\{y_{j}g(x_{j})\colon j\in[m]\}$ according to the original position in $S$. Suppose $\hat{y}_{k}f(\hat{x}_{k})$ corresponds to $\hat{y}_{l}g(\hat{x}_{l})$ for some $l$. If $l\leq k$ then the example $(\hat{x}_{k},\hat{y}_{k})$ of $\hat{y}_{k}f(\hat{x}_{k})$ is desired; otherwise, except for $(\hat{x}_{k},\hat{y}_{k})$ of $\hat{y}_{k}f(\hat{x}_{k})$ in $S$, there are at least $m-k$ elements larger than or equal to $\theta$ in $\{y_{j}f(x_{j})\colon j\in[m]\setminus\{k\}\}$ but at most $m-k-1$ elements larger than $\alpha$ in $\{y_{j}g(x_{j})\colon j\in[m]\setminus\{l\}\}$. This completes the proof from the bijection.\qed

Proof of Theorem 4 For finite $\mathcal{H}$, we denote by $\mathcal{A}=\{{i}/{|\mathcal{H}|}\colon i\in[|\mathcal{H}|]\}$. For every $f\in\mathcal{C}(\mathcal{H})$, we can construct a $g\in\mathcal{C}_{N}(\mathcal{H})$ by choosing $N$ elements i.i.d according to distribution $\mathcal{Q}(f)$, and thus $E_{g\sim\mathcal{Q}(f)}[g]=f$. For $\alpha>0$, the Chernoff’s bound in Lemma 1 gives

For any $\epsilon_{N}>0$, we consider the following probability:

where $\hat{y}_{k}g(\hat{x}_{k})$ denotes the $k$th margin with respect to $g$. For any $k$, Eqn. 18 can be bounded by \exp\big{(}-mKL\big{(}\frac{k-1}{m}\big{|}\big{|}\epsilon_{N}\big{)}\big{)} from Lemma 2; for constant $k$ with $m>4k$, we have

By using the union bound and $|\mathcal{C}_{N}(\mathcal{H})|\leq|\mathcal{H}|^{N}$, we have, for any $k\in[m]$,

Setting \delta_{N}=|\mathcal{H}|^{N+1}\exp\big{(}-mKL\big{(}\frac{k-1}{m}\big{|}\big{|}\epsilon_{N}\big{)}\big{)} gives

Thus, with probability at least $1-\delta_{N}$ over sample $S$, for all $f\in\mathcal{C}(\mathcal{H})$ and all $\alpha\in\mathcal{A}$, we have

Similarly, for constant $k$, with probability at least $1-\delta_{N}$ over sample $S$, it holds that

From $E_{g\sim\mathcal{Q}(f)}[I[\hat{y}_{k}g(\hat{x}_{k})\leq\alpha]]=\Pr_{g\sim\mathcal{Q}(f)}[\hat{y}_{k}g(\hat{x}_{k})\leq\alpha]$, we have, for any $\theta>\alpha$,

Notice that the example $(\hat{x}_{k},\hat{y}_{k})$ in $\{\hat{y}_{i}f(\hat{x}_{i})\}$ may be different from example $(\hat{x}_{k},\hat{y}_{k})$ in $\{\hat{y}_{i}g(\hat{x}_{i})\}$; therefore, we can not bound the last term on the right-hand side of Eqn. 21 as done in (Wang et al., 2011), whereas it can be bounded by using Lemma 4

Combining Eqns. 17, 19, 21 and 22, we have that with probability at least $1-\delta_{N}$ over the sample $S$, for all $f\in\mathcal{C}(\mathcal{H})$, all $\theta>\alpha$, all $k\in[m]$ but fixed $N$:

To obtain the probability of failure for any $N$ at most $\delta$, we select $\delta_{N}=\delta/2^{N}$. Setting $\alpha=\frac{\theta}{2}-\frac{\eta}{|\mathcal{H}|}\in\mathcal{A}$ and $N=\lceil\frac{8}{\theta^{2}}\ln\frac{2m^{2}}{\ln|\mathcal{H}|}\rceil$ with $0\leq\eta<1$, we have

from the fact $2m>\exp(N/(2|\mathcal{H}|))$ for $\theta>\sqrt{8/|\mathcal{H}|}$. Finally we obtain

where $q=\frac{8\ln(2|\mathcal{H}|)}{\theta^{2}}\ln\frac{2m^{2}}{\ln|\mathcal{H}|}+\ln|\mathcal{H}|+\ln\frac{m}{\delta}$. This completes the proof of Eqn. 4. In a similar manner, we have

for constant $k<m/4$. This completes the proof of Eqn. 5 as desired.\qed

2 Proof of Theorem 5

For notational simplicity, we denote by $\bar{X}=(X_{1},X_{2},\ldots,X_{m})$ a vector of $m$ i.i.d. random variables, and further set

i.e., the vector with the the $k$th variable $X_{k}$ in $\bar{X}$ replaced by variable $Y$. We first introduce some lemmas as follows:

Suppose that $\bar{X}=(X_{1},X_{2},\ldots,X_{m})$ is a vector of $m$ i.i.d. random variables taking values in a set $\mathcal{A}$. If $|F(\bar{X})-F(\bar{X}^{k,Y})|\leq c_{k}$ for $k\in[m]$ and $Y\in\mathcal{A}$, then the following holds for any $t>0$,

For two i.i.d random variables $X$ and $Y$, we have

Proof: This lemma follows from the obvious fact $E[(X-Y)^{2}]=E(X^{2}+Y^{2}-2XY)=2E[X^{2}]-2E^{2}[X]=2E[(X-E[X])^{2}]$.\qed

Proof of Theorem 5 We will utilize Lemmas 5 and 6 to prove Eqns. 6 and 7, respectively. For Eqn. 6, we first observe that, for any $k\in[m]$,

where we use $\hat{V}_{m}(\bar{X}),\hat{V}_{m}(\bar{X}^{k,Y})\leq 1/2$ from $X_{i}\in$. By using the Jenson’s inequality, we have E\big{[}\sqrt{\hat{V}_{m}(\bar{X})}\big{]}\leq\sqrt{E[\hat{V}_{m}(\bar{X})]} and thus,

where the last inequality holds by applying McDiarmid formula in Lemma 5 to $\sqrt{\hat{V}_{m}}$. Therefore, we complete the proof of Eqn. 6 by setting $\delta=\exp(-4m\epsilon^{2})$.

To prove Eqn. 7, we set $\xi_{m}(\bar{X})=m\hat{V}_{m}(\bar{X})$. For $X_{i}\in$ and $\xi_{m}(\bar{X}^{k,Y})$, it is easy to obtain the optimal solution by simple calculation

Therefore, for any $t>0$, the following holds by using Lemma 6 to $\xi_{m}(\bar{X})$,

Setting $\delta=\exp({-mt^{2}}/{2E[\hat{V}_{m}(\bar{X})]})$ gives

which completes the proof of Eqn. 7 by using the square-root’s inequality and $\sqrt{a+b}\leq\sqrt{a}+\sqrt{b}$ for $a,b\geq 0$. \qed

3 Proof of Theorem 6

For independent random variables $\bar{X}=(X_{1},X_{2},\ldots,X_{m})$, we set $\hat{V}_{m}(\bar{X})=\sum_{i\neq j}(X_{i}-X_{j})^{2}/2m(m-1)$, and observe that

where we denote by $V=\sum_{i}E(X_{i}-E[X_{i}])^{2}/m$ and the second equality holds from $(a+b+c)^{2}=a^{2}+b^{2}+c^{2}+2ab+2ac+2bc$. For any $\delta>0$, the following holds with probability at least $1-\delta$ from Eqn. 15,

which completes the proof of Eqn. 8 by combining with Eqn. 7 in a union bound and simple calculations. Similar proof could be made for Eqn. 9. \qed

4 Proof of Theorem 7

We will use classical double sample method (Devroye et al., 1996; Vapnik, 1998) to prove Theorem 7. Let $\mathscr{A}$ be a subsets of space $\mathcal{Z}$, and we define

We first introduce a useful lemma as follows:

For space $\mathscr{A}$ of subsets of $\mathcal{Z}$, and for sample $S=(z_{1},z_{2},\ldots,z_{m})$ drawn i.i.d. from distribution $\mathcal{D}$ over $\mathcal{Z}$, we have, for $t>\ln 4$

where $\Pr_{\mathcal{D}}[A]=\Pr_{z\sim\mathcal{D}}[z\in A]$, $\Pr_{S}[A]=\Pr_{z\sim S}[z\in A]$ and $\hat{V}_{S}(A)=\sum_{i\neq j}(I[z_{i}\in A]-I[z_{j}\in A])^{2}/2m(m-1)$.

Proof: We begin with another sample $\hat{S}=(\hat{z}_{1},\hat{z}_{2},\ldots,\hat{z}_{m})$ drawn identically and independently from distribution $\mathcal{D}$, and denote by

From Corollary 3, we have $\Pr_{\hat{S}\sim\mathcal{D}^{m}}[\Pr_{\mathcal{D}}[A]\leq\Psi_{\hat{S}}(A)]\geq 1/2$ for $h\in\mathcal{H}$ and $t>\ln 4$. This follows for any $\epsilon>0$

Now, we introduce the sign random variable vector $\sigma=(\sigma_{1},\sigma_{2},\ldots,\sigma_{m})$ with probability $\Pr[\sigma_{i}=1]=\Pr[\sigma_{i}=-1]=1/2$ for $i\in[m]$, and denote by $S^{\sigma}=(z^{\sigma}_{i})_{i=1}^{m}$ and $\hat{S}^{\sigma}=(\hat{z}^{\sigma}_{i})_{i=1}^{m}$

Given $S$ and $S^{\prime}$, $z^{\sigma}_{i}$ ($i\in[m]$) are not identically distributed but independent. Conditioned on $S$ and $S^{\prime}$, we have

where we denote by $A^{*}\in\arg\sup_{A\in\mathscr{A}}\Pr_{\sigma}\left[\Psi_{\hat{S}^{\sigma}}(A)>\Psi_{S^{\sigma}}(A)+\epsilon|S,S^{\prime}\right]$ and $\Pr_{\sigma}[A^{*}]=E_{\sigma}[\Pr_{S^{\sigma}}[A^{*}]|S,\hat{S}]=E_{\sigma}[\Pr_{\hat{S}^{\sigma}}[A^{*}]|S,\hat{S}]$. Further, we denote by

The first term in the above can be bounded by $e^{-t}$ from Bennett’s inequality (Lemma 3), and the second term can be bound by $e^{-t}$ by setting $\epsilon=4t/m$ and using Theorem 5. Similarly, we can prove

by setting $\epsilon=4t/m$. This complete the proof as desired.\qed

where $A(h)=\{(X,h(X)\in\mathcal{X}\times\{-1,+1\})\}$. For space $\mathcal{H}$ with finite VC-dimension $d$, Sauer’s lemma (Sauer, 1972) gives

Combining with Lemma 8, we have, for $t\geq\ln 4$

Setting $\delta=8({2m}/{d})^{d}e^{-t}$, we have

5 Proof of Theorem 8

Similarly to the proof of Theorem 4, we have

for any given $\alpha>0$, $f\in\mathcal{C}(\mathcal{H})$ and $g\in\mathcal{C}_{N}(\mathcal{H})$ drawn i.i.d according to $\mathcal{Q}(f)$. Recall that $|\mathcal{C}_{N}(\mathcal{H})|\leq|\mathcal{H}|^{N}$. Therefore, for any $\delta_{N}>0$, combining union bound with Eqn. 8 in Theorem 3 guarantees that the following holds with probability at least $1-\delta_{N}$ over sample $S$, for any $g\in\mathcal{C}_{N}(\mathcal{H})$ and $\alpha\in\mathcal{A}$,

for $m\geq 5$. By using Lemma 1 again, the following holds for any $\theta_{1}>0$,

Setting $\theta_{1}=\alpha=\theta/2$ and combining Eqns. 24, 25, 26 and 27, we have

where $\mu=\ln(2|\mathcal{H}|^{N+1}/\delta_{N})$. By utilizing the fact $\sqrt{a+b}\leq\sqrt{a}+\sqrt{b}$ for $a\geq 0$ and $b\geq 0$, we further have

Finally, we set $\delta_{N}=\delta/2^{N}$ so that the probability of failure for any $N$ will be no more than $\delta$. This theorem follows by setting $N=\lceil 8\ln m/\theta^{2}\rceil$. \qed

6 Proof of Corollary 5

If the minimum margin $\theta_{1}=\hat{y}_{1}f(\hat{x}_{1})>0$, then we have $\Pr_{S}[yf(x)<\theta_{1}]=0$ and further get

where $\mu_{1}={8\ln m}\ln(2|\mathcal{H}|)/{\theta_{1}^{2}}+\ln({2|\mathcal{H}|}/{\delta})$. This gives the proof of Eqn. 10. If $m\geq 5$, then we have

Therefore, the following holds by combining Eqn. 28 and the above facts,

where the last inequality holds from the conditions of Eqn. 13 and ${8}/{m}<R$. This completes the proof of Eqn. 14.\qed

7 Proof of Theorem 9

Our proof is based on a new Bernstein-type bound as follows:

For $f\in\mathcal{C}(\mathcal{H})$ and $g\in\mathcal{C}_{N}(\mathcal{H})$ drawn i.i.d according to distribution $\mathcal{Q}(f)$, we have

Proof: For $\lambda>0$, we utilize the Markov’s inequality to have

where the last inequality holds from the independence of $h_{j}$. Notice that $|yh_{j}(x)-yf(x)|\leq 2$ from $\mathcal{H}\subseteq\{h\colon\mathcal{X}\to\{-1,+1\}\}$. By using Taylor’s expansion, we further get

where the last inequality holds from Jensen’s inequality and $1+x\leq e^{x}$. Therefore, it holds that

If $0<\lambda<3$, then we could use Taylor’s expansion again to have

Now by picking $\lambda={t}/(1/2-E^{2}_{S}[yf(x)]/2+t/3)$, we have

which completes the proof as desired.\qed

Proof of Theorem 9 This proof is rather similar to the proof of Theorem 8, and we just give main steps. For any $\alpha>0$ and $\delta_{N}>0$, the following holds with probability at least $1-\delta_{N}$ over sample $S_{m}$ ($m\geq 5$),

where $\hat{V}^{*}_{m}=\Pr_{S}[yg(x)<\alpha]\Pr_{S}[yg(x)\geq\alpha]$. For any $\theta_{1}>0$, we use Lemma 1 to obtain

Let $\theta_{1}=\theta/6$, $\alpha=5\theta/6$, and set $\delta_{N}=\delta/2^{N}$ so that the probability of failure for any $N$ will be no more than $\delta$. We complete the proof by setting $N=\lceil 144\ln m/\theta^{2}\rceil$ and simple calculation. \qed

8 Proof of Corollary 6

If the minimum margin $\theta_{1}=\hat{y}_{1}f(\hat{x}_{1})>0$, then we have $\Pr_{S}[yf(x)<\theta_{1}]=0$ and $\hat{\mathcal{I}}(\theta_{1})=\Pr_{S}[yf(x)<\theta_{1}]\Pr_{S}[yf(x)\geq 2\theta_{1}/3]=0$. Further, we have

where $\mu_{1}={144\ln m}\ln(2|\mathcal{H}|)/{\theta_{1}^{2}}+\ln({2|\mathcal{H}|}/{\delta})$. This completes the proof.\qed

9 Proof of Theorems 10 and 11

For finite VC-dimension space $\mathcal{H}$, we denote by $\mathcal{A}=\{i/N\colon i\in[N]\}$. Similarly to the proof of Theorem 4, we have

for $\alpha\in\mathcal{A}$, $f\in\mathcal{C}(\mathcal{H})$ and $g\in\mathcal{C}_{N}(\mathcal{H})$ chosen i.i.d according to $\mathcal{Q}(f)$. Define

and by using Sauer’s lemma (Sauer, 1972), we have

for $m>d$. By setting $4s(\mathscr{A},2m)e^{-t}=\delta_{N}>0$ in Lemma 8, the following holds with probability at least $1-\delta_{N}$ over sample $S$, for any $g\in\mathcal{C}_{N}(\mathcal{H})$ and $\alpha\in\mathcal{A}$,

where $\hat{V}^{*}_{m}=\Pr_{S}[yg(x)<\alpha]\Pr_{S}[yg(x)\geq\alpha]$.

To prove Theorem 10, we proceed as the proof of Theorem 8. Setting $\alpha=\theta/2$, we have

where $\mu=\ln(8s(\mathscr{A},2m)/\delta_{N})$. This completes the proof by using $\sqrt{a+b}\leq\sqrt{a}+\sqrt{b}$ and setting $\delta_{N}=\delta/2^{N}$ and $N=\lceil 8\ln m/\theta^{2}\rceil$.

To prove Theorem 11, we proceed as the proof of Theorem 9. Setting $\alpha=5\theta/6$, we have

where $\mu=\ln(8s(\mathscr{A},2m)/\delta_{N})$ and $\hat{\mathcal{I}}(\theta)=\Pr_{S}[yf(x)<\theta]\Pr_{S}[yf(x)\geq 2\theta/3]$. This completes the proof by using $\sqrt{a+b}\leq\sqrt{a}+\sqrt{b}$ and setting $\delta_{N}=\delta/2^{N}$ and $N=\lceil 144\ln m/\theta^{2}\rceil$. \qed

Conclusion

The margin theory provides one of the most intuitive and popular theoretical explanations to AdaBoost. It is well-accepted that the margin distribution is crucial for characterizing the performance of AdaBoost, and it is desirable to theoretically establish generalization bounds based on margin distribution.

In this paper, we first present the $k$th margin bound and further study on its relationship to previous work such as the minimum margin bound and Emargin bound. Then, we improve the empirical Bernstein bound with different skills. As our main results, we prove a new generalization bound which considers exactly the same factors as Schapire et al. (1998) but is sharper than the bounds of Schapire et al. (1998) and Breiman (1999), and thus provide a complete answer to Breiman’s doubt on the margin theory. By incorporating other factors such as average margin and variance, we present another generalization error bound which is heavily related to the whole margin distribution. In addition, we provide margin bounds for generalization error of voting classifiers in finite VC-dimension space. An interesting future issue is to develop new algorithms based on our theory.

Acknowledgements

We want to thank the editor and reviewers for helpful comments and suggestions. This work was supported by the National Fundamental Research Program of China (2010CB327903), the National Science Foundation of China (61073097, 61021062), the Jiangsu Province Graduate Students Innovative Research Project (CXZZ11_0046) and the Nanjing University PhD Students Promoting Program (201301A07).

References