# Severity Prediction of Highway Crashes in Saudi Arabia Using Machine Learning Techniques
## 3 Materials and Methods
### Methods
#### 3.3.4 Extreme Gradient Boosting (XGBoost)  
XGBoost was used to solve problems requiring supervised learning, where multiple features were used to predict the target variable from the training data. XGBoost is based on the gradient boosting technique, which is a term coined by [64], in a paper titled \"Greedy Function Approximation: A Gradient Boosting Machine\". The gradient boosting decision tree (GBDT) algorithm was improved by [PERSON] and [PERSON] in 2016, resulting in the XGBoost algorithm [38]. This method helps models to predict more accurately, reduce computational efforts, and avoid overfitting issues. In addition, it has been reported that XGBoost demonstrates better predictive performance compared with traditional machine learning algorithms. XGBoost provides a parallel tree boosting and is a leading machine-learning library for regression, classification, and ranking. XGBoost is an ensemble algorithm, which refers to the use of multiple learning algorithms to achieve better predictive performance than any single algorithm. The general form of the XGBoost objective function is presented in Equation (3), where \(l\) is the training loss function, and \(\Omega\) is the regularization term. It uses the training data (with multiple features) \(x_{i}\) to predict a target variable \(y_{i}\), and \(\hat{y}_{i}\) is the prediction; k refers to the number of trees; and \(f_{k}\) represents a function in the functional space. However, the XGBoost objective function at iteration \(t\) needs to be minimized using Equation (4):  
\[Objective\ Obj=\sum_{i=1}^{n}l(y_{i},\hat{y}_{i})+\sum_{k=1}^{K}\Omega(f_{k}) \tag{3}\]  
\[obj^{(t)}=\sum_{i=1}^{n}l\left(y_{i},\hat{y}_{i}{}^{(t-1)}\right)+f_{t}(x_{i} )+\Omega(f_{t}) \tag{4}\]  
In the regularization term in Equation (5), XGBoost uses two parameters to define the complexity of a tree,... as the number of leaves and \(L_{2}\) as the norm of leaf scores, while \(\gamma\) and \(\lambda\) are hyperparameters. The overall complexity is defined as the sum of the number of leaves weighted by \(\gamma\) and a \(\lambda\) weighted \(L_{2}\) norm of the leaf score-leaf weight:  
\[\Omega(f_{t})=\gamma T+\frac{1}{2}\lambda\sum_{j=1}^{T}w_{j}^{2} \tag{5}\]  
The second part is the training loss, which can be represented as an additive model since it is under the boosting space as given in Equation (6). This is the final model \(\hat{y}\) of \(t\) composed of the previous model, which is \(\hat{y}_{i}{}^{(t-1)}\) plus the new model that we want to learn:  
\[Final\ model\ (t)=\hat{y}_{i}{}^{(t)}=\sum_{k=1}^{t}f_{k}(x_{i})=\hat{y}_{i}{}^{(t-1 )}+f_{t}(x_{i}) \tag{6}\]  
To use traditional optimization techniques, the objective function must be transformed into a Euclidean domain via [PERSON] approximation using Equation (7). To simplify the objective function's training loss, [PERSON]'s equation is applied on the two terms in Equation (8), which will introduce two new terms \(g_{i}\) and \(h_{i}\) in Equation (9), representing the values of each leaf in the tree. Making the original function in quadratic form:  
\[[PERSON]\ approximation=f(x+\Delta x)\simeq f(x)+f^{\prime}(x)\Delta x+\frac{1}{2}f^{ \prime\prime}(x)\Delta x^{2} \tag{7}\]  
XGBoost Simplified with [PERSON] Approximation:  
\[obj^{(t)}\simeq\sum_{i=1}^{n}\left[l\left(y_{i},\dot{g}_{i}{}^{(t-1)}\right) +g_{i}f_{i}(x_{i})+\frac{1}{2}h_{i}{f_{i}}^{2}(x_{i})\right]+\Omega(f_{i}) \tag{8}\]  
\[ \begin{array}{c}g_{i}=\partial_{g_{i}{}^{(t-1)}}l\left(y_{i},\dot{g}_{i}{}^{( t-1)}\right)\\ h_{i}=\partial^{2}{}_{g_{i}{}^{(t-1)}}l\left(y_{i},\dot{g}_{i}{}^{(t-1)}\right) \end{array}  \tag{9}\]  
where the \(g_{i}\) term indicates the first-order differentiation, and \(h_{i}\) is the second order differentiation for approximating the function. The new form is when it is put together, i.e., training loss and regularization, and it is simplified in Equation (10) by using G and H to refer to the summation of \(g_{(s)}\) and \(h_{(s)}\), respectively.