# An Efficient AdaBoost Algorithm with the Multiple Thresholds Classification
## 2 Background
### Threshold Classification  
By increasing weights of error-classifying examples, AdaBoost focuses the 'hard' (misclassified) examples and trains learners in an iterative way. The final decision is combined by a set of diverse classifiers using weighted majority voting rule. Without the difficulty in directly designing an excellent algorithm, AdaBoost takes full advantage of Weak Learn algorithm, which is easily available. For a great many kinds of training example sets, there are obvious relations between labels and certain attributes, in other words, most examples with larger values of certain attribute fall in the same category, and the ones with smaller values fall in the other category. Based on the relation, University of Twente has written out the program of the classical AdaBoost algorithm, AdaBoost with Threshold Classification, in 2010. Finding the best threshold from all attributes as classification rule, this AdaBoost provides a rough but easily obtainable learner in each iteration. The Threshold Classification algorithm is presented in Algorithm 2.  
1. Input: Training dataset: \(S=\{(X_{1},Y_{1}),(X_{2},Y_{2}),\cdots,(X_{m},Y_{m})\}\); weight distribution \(\omega\).  
2. Do for \(j=1,2,\cdots,d\)  
(2.1) Sort the \(m\) training examples by the size of their \(j\)th attribute;  
(2.2) Find the threshold \(\tau_{j}\) in the attribute as the classifier \(h_{j}\).  
3. Output: Compare these weighted errors, \(\epsilon_{1},\epsilon_{2},\cdots,\epsilon_{d}\), and find the minimum  
\(\epsilon=\min\{\epsilon_{j}\}(j=1,2,\cdots,d)\), the threshold classifier is \(h=h_{j}\) with the error \(\epsilon_{j}=\epsilon\).  
**Algorithm 2** Threshold Classification.  
In the train dataset \(S\), \((X_{i},Y_{i})\) is the \(i\)th example, and \(X_{i}=(x_{i1},x_{i2},\cdots,x_{ij})\) describes the \(i\)th example \((j=1,2,\cdots,d)\), while \(Y_{i}\in\{-1,1\}\) does the label \((i=1,2,\cdots,m)\). So \(x_{ij}\) is the \(j\)th attribute Absolutely of \(i\)th example and every example is described by \(d\) attributes and a label. We find the threshold \(\tau_{j}\) as a classifier \(h_{j}\) from \(\{x_{ij},x_{2j},\cdots,x_{mj}\}\) which are the \(j\)th attributes of all the examples so that we obtain the lowest weighted error \(\epsilon_{j}=\sum_{i=1}^{m}\omega_{i}\,Y_{i}\
eq h_{t}(X_{i})\) when we distinguish the examples whose \(j\)th attribute are larger than \(\tau_{j}\) from those that are smaller than \(\tau_{j}\). When the \(j\)th attributes of most positive examples are larger than \(\tau_{j}\) and that of most negative examples are smaller than \(\tau_{j}\):  
\[h_{j}(X_{i})=\left\{\begin{array}{ll}1,&x_{ij}\geq\tau_{j}\\ -1,&x_{ij}<\tau_{j}\end{array}\right. \tag{1}\]  
when the \(j\)th attributes of most positive examples are smaller than \(\tau_{j}\) and that of most negative examples are larger than \(\tau_{j}\): \(h_{j}(X_{i})=\left\{\begin{array}{ll}1,&x_{ij}\leq\tau_{j}\\ -1,&x_{ij}>\tau_{j}\end{array}\right.\) in step 2. The accuracy of the weak classifier \(h\) based on Threshold Classification is \(1-\epsilon\).  
**3. AdaBoost with Multiple Thresholds Classification**  
This section explains the basic idea of our Multiple Thresholds Classification in Section 3.1. Afterwards, we will construct the Weak Learn algorithm in the Algorithm frame and then briefly describe our algorithm in Section 3.2.