# An Efficient AdaBoost Algorithm with the Multiple Thresholds Classification
## 2 Background
### Multiple Thresholds Classification
\(h^{\prime},h^{\prime\prime}\) classify correctly, but \(h^{\prime\prime\prime}\) not, \(h^{\prime}(X)=Y\), \(h^{\prime\prime}(X)=Y\), \(h(X)=Y\) in that \(\epsilon^{\prime}\leq\epsilon^{\prime\prime}\leq\epsilon^{\prime\prime\prime}\) and the probability is: \[p_{2}=(1-\epsilon^{\prime})(1-\epsilon^{\prime\prime})\epsilon^{\prime\prime}\] (3)
3. \(h^{\prime\prime}\) classify correctly, but \(h^{\prime\prime}\) not. The probability is: \[p_{3}=(1-\epsilon^{\prime})\epsilon^{\prime\prime}(1-\epsilon^{\prime\prime})\] (4)
4. \(h^{\prime\prime}\), \(h^{\prime\prime\prime}\) classify correctly, but \(h^{\prime}\) not and the sum of accuracies of \(h^{\prime\prime}\) and \(h^{\prime\prime\prime}\) is larger than that of \(h^{\prime}\), \((1-\epsilon^{\prime\prime})+(1-\epsilon^{\prime\prime})\geq(1-\epsilon^{\prime})\), in other words, \(\epsilon^{\prime\prime}+\epsilon^{\prime\prime\prime}-\epsilon^{\prime}\leq 1\). The probability is:\[p_{4}=\epsilon^{\prime}(1-\epsilon^{\prime\prime})(1-\epsilon^{\prime\prime})\cdot p\] (5) \(p\) is the probability that \(\epsilon^{\prime\prime}+\epsilon^{\prime\prime\prime}-\epsilon^{\prime}\leq 1\). 5. \(h^{\prime}\) classifies correctly, but \(h^{\prime\prime},h^{\prime\prime\prime}\) not and the sum of accuracies of \(h^{\prime\prime}\) and \(h^{\prime\prime\prime}\) is smaller than that of \(h^{\prime}\), \((1-\epsilon^{\prime\prime})+(1-\epsilon^{\prime\prime\prime})\leq(1-\epsilon^ {\prime})\), in other words, \(\epsilon^{\prime\prime}+\epsilon^{\prime\prime\prime}-\epsilon^{\prime}\geq 1\). The probability is: \[p_{5}=(1-\epsilon^{\prime})\epsilon^{\prime\prime}(1-\epsilon^{\prime\prime}) \cdot(1-p)\] (6) According to Equations (2)-(6), expectation of accuracy of Multiple Thresholds Classification \(h(X)\) is: \[\partial=p_{1}+p_{2}+p_{3}+p_{4}+p_{5}\] (7) Assume that the errors follow uniform distribution pattern: \(\epsilon^{\prime}\sim U(0,1)\), \(\epsilon^{\prime\prime}\sim U(\epsilon^{\prime},1)\), and \(\epsilon^{\prime\prime\prime}\sim U(\epsilon^{\prime\prime},1)\), then the joint density function is: \[f(x,y,z)\big{|}_{\epsilon^{\prime},\epsilon^{\prime\prime\prime}}=\left\{ \begin{array}{ll}\frac{1}{(1-x)(1-y)},1\geq x\geq y\geq 0&\\ 0,&\text{else}\end{array} \right.\] (8) \[\epsilon^{\prime\prime}+\epsilon^{\prime\prime}-\epsilon^{\prime}\geq 1 \text{ and }0\leq\epsilon^{\prime}\leq\epsilon^{\prime\prime}\leq\epsilon^{\prime\prime \prime}\leq 1\text{ mean that }\max\{1+\epsilon^{\prime}-\epsilon^{\prime\prime},\epsilon^{\prime\prime}\} \leq\epsilon^{\prime\prime\prime}\leq 1\text{ while }\] \[\epsilon^{\prime}\leq\epsilon^{\prime}\leq 1\cdot 1+\epsilon^{\prime}- \epsilon^{\prime\prime}\text{ and }\epsilon^{\prime\prime}\text{ are compared as shown: }\left\{ \begin{array}{ll}1+\epsilon^{\prime}-\epsilon^{\prime\prime}> \epsilon^{\prime\prime},\text{as }\epsilon^{\prime\prime}<\frac{1+\epsilon^{\prime}}{1+ \epsilon^{\prime}-\epsilon^{\prime\prime}\leq\epsilon^{\prime\prime},\text{as }\epsilon^{\prime\prime}\geq\frac{1+\epsilon^{\prime}}{2}}\\ 1+\epsilon^{\prime}-\epsilon^{\prime\prime}\leq\epsilon^{\prime\prime},\text{ as }\epsilon^{\prime\prime}\geq\frac{1+\epsilon^{\prime}}{2}\end{array} \right.\] besides Equation (8), \(\partial\) in Equation (7) is calculated as followed: \[\partial=\int_{0}^{1}dx\int_{x}^{\frac{1+x}{2}}dy\int_{1+x-y}^{1}\frac{1}{(1-x )\left(1-y\right)}dz+\int_{0}^{1}dx\int_{\frac{1+x}{2}}^{1}dy\int_{y}^{1}\frac{ 1}{(1-x)\left(1-y\right)}dz=\ln 2\] The accuracy of threshold classifier \(1-\epsilon\) in Algorithm 2 is equal to the accuracy of Multiple Thresholds Classifier \(1-\epsilon^{\prime}\) in Algorithm 3. If \(\epsilon^{\prime}\sim U(0,1)\) expectation of \(\epsilon^{\prime}\) is 50%, so is \(1-\epsilon^{\prime}\). Obviously, expectation of accuracy of Multiple Thresholds Classification \(\partial\) in Algorithm 4 is better than that of Threshold Classification \(1-\epsilon^{\prime}\). ```
1.Input: Training dataset \(S\) and Ensemble size T as the same as in Algorithm 1; Multiple Thresholds Classification.