Quick Real-Boost with: Weight Trimming, Exponential Impurity, Bins, and Pruning

The central point of attention for this paper is weight trimming — a technique known for speeding up boosted learning procedures. The loss of accuracy introduced by the technique is typically negligible. Recently, an elegant algorithm has been proposed by Appel et al.: it applies weight trimming under AdaBoost, prunes some features using a special error bound, but simultanouesly guarantees the same outcome (ensemble of trees with exactly the same parameters) as if with no trimming. Thus, no loss of training accuracy occurs. In this paper, we supplement the idea by Appel with a suitable extension for real-boosting. We prove that this approach gives the same outcome guarantees, both for stumps and trees. Additionally, we analyze the complexity of Appel’s idea and we show that in some cases it may lead to computational losses.

1. 1.

   For simplification, assume data indexes mapped to successive integers, so that there are no indexing holes and therefore \(m_j-m_{j-1}\) differences reflect sizes of portions.

Authors and Affiliations

1. Faculty of Computer Science and Information Technology, West Pomeranian University of Technology, Ul. Żołnierska 49, 71-210, Szczecin, Poland

   Przemysław Klęsk

Corresponding author

Correspondence to Przemysław Klęsk .

Editors and Affiliations

1. Częstochowa University of Technology, Czestochowa, Poland

   Leszek Rutkowski

2. Częstochowa University of Technology, Czestochowa, Poland

   Marcin Korytkowski

3. Częstochowa University of Technology, Czestochowa, Poland

   Rafał Scherer

4. AGH University of Science and Technology, Krakow, Poland

   Ryszard Tadeusiewicz

5. University of California, Berkeley, California, USA

   Lotfi A. Zadeh

6. University of Louisville, Louisville, Kentucky, USA

   Jacek M. Zurada

A Proof of Outcome Guarantee for ‘quick’ Tree Growing Procedure with Exponential Impurity

Proof

(Theorem 2 ). First, let us define the Gini error (for the n-subset):

(21)

where \(Z_{\rho _l}^{+}=\sum _{i\in \rho _l}w_i[y=+1]\), \(Z_{\rho _l}^{-}=\sum _{i\in \rho _l}w_i[y=-1]\) are probability masses for classes. Let us write two representations (22), (23) for the products — mass times Gini error — that will be useful later on:

We now write out the exponential error and show its connection to Gini error.

(24)

(25)

We aim at showing that , which means that if one removes from a leaf the examples that are not in the m-subset but keeps the tree parameters fixed then the mass times error product must decrease or stay unchanged. We remind that \(\rho _l=u_l\cup \bar{u_l}\) and \(n>m\), see back to definitions (14). Let us observe the square of using a representation from (25) for the leaf error.

(26)

Note the similarity of the last expression to a Gini representation (22).

We shall now expand (26) taking advantage of the following lemma (for straightforward algebraic proof see [1]) true for either class label \(y\in \{-1,+1\}\):

Therefore, we have:

(28)

The equality pass comes from grouping odd and even terms using representations (22). Hence, finally: . \(\quad \Box \)

Reprints and permissions

© 2016 Springer International Publishing Switzerland

Policies and ethics