# An Efficient AdaBoost Algorithm with the Multiple Thresholds Classification
## 2 Background
### Multiple Thresholds Classification  
Instead of building the complicated relation between labels and all the attributes, AdaBoost algorithm based on threshold focuses on the liner relation between labels and the most critical attribute. However, this classifier may achieve a low accuracy and poor generalization due to the following reasons: (1) this Weak Learn algorithm just searches only the one optimal threshold from all the attributes as the classified rule that wastes the potential value of other resources; (2) this classifier still has the tendency of overfitting as it focuses on training examples which is misclassified by just the one threshold in each iteration. If the labels tend to have certain degree linear relations with not only one attribute, such as the relation between gender and height or weight, AdaBoost algorithm with Threshold Classification may achieve not only a low accuracy but also poor generalization. For example, if we classify persons by height, like that the taller persons are divided into males and shorter ones into females, there must be many short males and tall females misclassified, the same as by weight. To solve the dilemma, we can divide those who are tall and heavy into males and the others into females, so there will be less persons misclassified. To improve the Threshold Classification, we proposed the Multiple Thresholds Classification which uses three crucial thresholds as a classifier, not only the one. Firstly, we sort examples in sequences by attributions, and choose thresholds from every sequence, the same as step 2 of Algorithm 2. According to the errors of these thresholds, we choose the best three ones and assign different weights to them, then we integrate those three classifiers by weighted majority voting rule as a Weak Learn algorithm. It is formally demonstrated in Algorithm 3. ```
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 \(j\)th attribute as the classifier \(h_{j}\) so that we obtain the lowest weighted error \(\varepsilon_{j}=\sum_{i=1}^{m}\omega_{i},Y_{i}\
eq h_{t}(X_{i})\) as the step (2.2) in Algorithm 2. 3. Output: Compare weighted errors \(\varepsilon_{1},\varepsilon_{2},\cdots,\varepsilon_{d}\) of these classifiers, \(h_{1},h_{2},\cdots,h_{d}\), to find the three best classifiers \(h^{\prime},h^{\prime\prime},h^{\prime\prime}\) with the lowest errors \(\epsilon^{\prime},\epsilon^{\prime},\epsilon^{\prime\prime},\epsilon^{\prime \prime}\), which \(0\leq\epsilon^{\prime}\leq\epsilon^{\prime\prime}\leq\epsilon^{\prime\prime}\leq 1\). The prediction result is weighted majority voted by the three rules: \(h(X)=sign\left\{(1-\epsilon^{\prime})h^{\prime\prime}(X)+(1-\epsilon^{\prime \prime})h^{\prime\prime}(X)+(1-\epsilon^{\prime\prime})h^{\prime\prime}(X)\right\}\) Weighted error of \(h(X)\) is \(\epsilon=\sum_{i=1}^{m}\omega_{i}^{\prime}\), \(Y_{i}\
eq h(X_{i})\). ```  
**Algorithm 3** Multiple Thresholds Classification. The error \(\varepsilon\) of a classifier means that the classifier will classify an example correctly with the probability of \(1-\varepsilon\), so in Algorithm 3, the weak classifier \(h\) with multiple thresholds will classify examples correctly in the following five cases:  
1. all the three classifiers \(h^{\prime}\), \(h^{\prime\prime}\), \(h^{\prime\prime\prime}\) classify correctly, \(h^{\prime}(X)=Y,\quad h^{\prime\prime}(X)=Y\), \(h^{\prime\prime\prime}(X)=Y\) according to Equation (1), there is \(h\ \ (X)=Y\), and the probability is: This is example 1 of an equation: \[p_{1}=(1-\epsilon^{\prime})(1-\epsilon^{\prime\prime})(1-\epsilon^{\prime \prime})\] (2)
2.