## 2 Background Theories
### Ensemble Support Vector Machine  
Support vector machine (SVM), a kind of kernel-based learning algorithm, is a state-of-the-art approach that learns a discriminating hyperplane to maximize the margin and to produce a good generalization ability for classification. It works by implicitly mapping original examples into a high-dimensional space with a kind of nonlinear function and then by optimizing the decision function with the maximal margin to classify different classes. Actually, SVM is originally designed for two-class problems. Denoting the \(n\) original examples and the corresponding class labels as set \(\{(\mathbf{x}_{i},\,y_{i}),\,i=1,2,\ldots,\,n\}\), where \(\mathbf{x}_{i}\in R^{d}\) is the \(d\)-dimensional input features for the \(i\)-sample and \(y_{i}\in\{+1,-1\}\) is the label for the positive and negative class and with the decision function \(f(\mathbf{x})=\mathbf{w}^{T}\varphi(\mathbf{x})+b\) (\(T\) is the transpose operator), the primal problem of soft-margin SVM is formulated as  
\[ \begin{array}{c}\min_{\mathbf{w},b}\frac{1}{2}\|\mathbf{w}\|^{2}+C{\sum_{i= 1}^{n}\xi_{i}}\\ s.t.\,y_{i}\Big{(}\mathbf{w}^{T}\varphi(\mathbf{x}_{i})+b\Big{)}\geq 1-\xi_{i}, \,\,\text{with}\,\,\xi_{i}\geq 0,\,\,i=1,2,\cdots,n\end{array}  \tag{3}\]  
where \(\mathbf{w}\) and \(b\) are the weight vector and bias, \(\varphi(\mathbf{x})\) is the nonlinear function that maps \(\mathbf{x}\) to the high-dimensional space, \(\xi_{i}\) are slack variables, and \(C\) is the penalty factor. Since \(\|\mathbf{w}\|^{2}\) is convex, the above minimizing problem can be achieved with Lagrange multipliers method and the dual problem follows:  
\[ \begin{array}{c}\min_{\mathbf{\alpha}}\frac{1}{2}{\sum_{i=1}^{n}\sum_{j=1}^{ n}\alpha_{i}\alpha_{j}y_{j}\varphi^{T}(\mathbf{x}_{i})\varphi\Big{(}\mathbf{x}_{j} \Big{)}-\sum_{i=1}^{n}\alpha_{i}}\\ s.t.\,\sum_{i=1}^{n}\alpha_{i}y_{i}=0,\,\,\text{with}\,\,0\leq\alpha_{i}\leq C,\,\,i=1,2,\cdots,n\end{array}  \tag{4}\]  
where \(\alpha_{i}\) is the Lagrange multiplier coefficients. The solution of Equation (4) gives \(\mathbf{w}=\sum_{i=1}^{n}\alpha_{i}y_{i}\varphi(\mathbf{x}_{i})\) and the estimated bias \(b\), inserting back to the linear decision function \(f(\mathbf{x})=\mathbf{w}^{T}\varphi(\mathbf{x})+b\) and defining \(K(\mathbf{x}_{i}\mathbf{\cdot}\mathbf{\cdot}\mathbf{\cdot}\mathbf{\cdot} \mathbf{\cdot})=\varphi(\mathbf{x}_{i})^{T}\varphi(\mathbf{x}_{j})\) as a kernel function to calculate the inner product; finally, the decision function of soft-margin SVM is represented with the signature function \(\text{sgn}\left(\cdot\right)\) as  
\[f(\mathbf{x})=\text{sgn}\left(\sum\
olimits_{i=1}^{n}\alpha_{i}y_{i}K(\mathbf{ x}_{i},\mathbf{x})+b\right) \tag{5}\]  
In practice, there are abundant multi-class classification applications, so it is required that the original SVM is extended to multi-category problems. For this purpose, the task has been solved by decomposing into multiple two-class problems. Initially, the two strategies of one-against-all and one-against-one have been adopted to construct a number of binary SVMs for discrimination of more than two classes. However, a single SVM may not learn exact parameters for the global optimum and SVM learning is time-consuming for a large scale of data. To address these problems, the ensemble SVM (ESVM) has been proposed and has been verified to improve the classification performance greatly compared to a single SVM [36]. ESVM is a collection of several SVMs in which individual decisions are combined in some way to output the classification result. Each individual SVM is independently trained with the randomly chosen training samples to form one base learner. In such a way, each base learner learns a certain area of the data samples space and is unlikely to be wrong at the same time, so ensemble of these base learners provides complementary information and thus more accurate classification results can be obtained.