# Comparative Analysis of Classifiers for Classification of Emergency Braking of Road Motor Vehicles
## Methods
### Extreme Gradient Boosting  
The last method which is considered in our work is Extreme gradient boosting (XGBoost) [22]. XGBoost is a scalable machine learning approach which has proved to be successful in many machine learning and data mining challenges [23; 24]. Essentially, XGBoost is an ensemble of \(K\) classification and regression trees (CART) [25]. Unlike decision trees, CART assign a real score to each leaf (outcome or target). The final score of \(y\) (output) is a sum of \(K\) additive functions as follows:  
\[\hat{y}=\sum_{k=1}^{K}f_{k}(x_{i}),\ f_{k}\in F\]  
where\(f_{k}\) corresponds to independent tree structure and leaf weights, while \(x_{i}\) is a testing object. \(F\) represents a testing space of all CART. For learning the set of functions, the following objective is used:  
\[\mathcal{L}(\varphi)=\sum_{i}l(\hat{y}_{i},y_{i})+\sum_{k}\Omega(f_{k}),\ \Omega(f)= \gamma T+\frac{1}{2}\lambda\|w\|^{2}.\]  
The first term \(l\) is a differentiable loss function, \(l\), which calculates the difference between the target \(y_{i}\) and the predicted \(\hat{y}_{i}\). \(\Omega\) is a regularization term which prevents over-fitting by penalizing the complexity of the model. Parameters T and w correspond to the number of leaf nodes and the weight of each of them, respectively. Parameters \(\gamma\) and \(\lambda\) are constants which control the degree of regularization.  
The ensemble tree model includes functions as parameters and cannot be optimized within traditional methods in Euclidian space; therefore, we employed the following additive approach for its training: assuming that at the \(t\)th iteration we have a prediction \(\hat{y}_{i}\) of the \(i\)th instance, we add \(f_{t}(x_{i})\) to our objective function.  
\[\mathcal{L}^{(t)}=\sum_{i}^{n}l(y_{i},\hat{y}_{i}^{(t-1)}+f_{t}(x_{i}))+\Omega (f_{t})\]  
In order to quickly optimize the general setting of this objective, the second-order approximation is used:  
\[\mathcal{L}^{(t)}\approx\sum_{i}^{n}[l(y_{i},\hat{y}_{i}^{(t-1)})+g_{i}f_{t}(x _{i})+\frac{1}{2}h_{i}f_{t}^{2}(x_{i})]+\Omega(f_{t}),\]  
\[g_{i}=\partial_{g^{(t-1)}}l\left(y_{i},\hat{y}_{i}^{(t-1)}\right),\ h_{i}= \partial_{g^{(t-1)}}^{2}l\left(y_{i},\hat{y}_{i}^{(t-1)}\right).\]  
Because the loss function is calculated at the current time step \(t\), we can easily remove it:  
\[\hat{\mathcal{L}}^{(t)}=\sum_{i}^{n}[g_{i}f_{t}(x_{i})+\frac{1}{2}h_{i}f_{t}^ {2}(x_{i})]+\Omega(f_{t}).\]  
By defining \(I_{j}=\{i\,l\,q(x_{i})=j\}\) as an instance set of leaf \(j\) for a given tree structure \(q(x)\), the objective function can be rewritten as follows:  
\[\hat{\mathcal{L}}^{(t)}=\sum_{i}^{n}[g_{i}f_{t}(x_{i})+\frac{1}{2}h_{i}f_{t}^ {2}(x_{i})]+\Omega(f_{t})=\sum_{j=1}^{T}[(\sum_{i\in I_{j}}g_{i})w_{j}+\frac{1} {2}(\sum_{i\in I_{j}}h_{i}+\lambda)w_{j}^{2}]+\gamma T.\]  
For a fixed structure \(q(x)\), the optimal weight \(w_{j}\) of leaf \(j\) will be  
\[w_{j}^{*}=-\frac{\sum_{i\in I_{j}}g_{i}}{\sum_{i\in I_{j}}h_{i}+\lambda}\]  
while the corresponding optimal value will be\[\hat{\mathcal{L}}^{(t)}(q)=-\frac{1}{2}\sum_{j=1}^{T}\frac{\left(\sum_{i\in I_{l}}g _{i}\right)^{2}}{\sum_{i\in I_{l}}h_{i}+\lambda}+\gamma T.\]  
Finally, in order to score a leaf node during splitting, we use the following expression:  
\[\mathcal{L}_{split}=\frac{1}{2}\left[\sum_{j=1}^{T}\frac{\left(\sum_{i\in I _{l}}g_{i}\right)^{2}}{\sum_{i\in I_{l}}h_{i}+\lambda}+\frac{\left(\sum_{i\in I _{j}}g_{i}\right)^{2}}{\sum_{i\in I_{R}}h_{i}+\lambda}+\frac{\left(\sum_{i\in I _{l}}g_{i}\right)^{2}}{\sum_{i\in I_{l}}h_{i}+\lambda}\right]-\gamma.\]  
Here \(I_{L}\) and \(I_{R}\) are the instance sets of the left and right nodes after the split, \(I=I_{L}\cup I_{R}\), and \(\gamma\) is the regularization on the additional leaves. It is important to note that--besides the regularization technique--shrinkage and feature subsampling are also used in XGBoost [22].