## 3 Machine Learning Models
### CatBoost, XGBoost and LightGBM  
CatBoost, XGBoost and LightGBM share basically the same principle, and can be categorized into the family of gradient boosting decision tree algorithms. The characteristics of these three models are described below.  
CatBoost takes a symmetric decision tree as a base model, having only a few parameters. CatBoost combines category features to construct new features, which enriches the feature dimension and facilitates the model to find important features. CatBoost is very flexible in handling category-based features, and the processing process is as follows:(1) Randomly sort the input sample set and generate multiple sets of random permutations. (2) Convert floating point or attribute value token to integers. (3) All the category-based feature results are converted into numerical results according to Equation (7). Where, \(\varphi\) represents the indicator function. The function value takes 1 if it satisfy the condition \(\left(x_{j}^{i}=x_{k}^{i}\right)\), otherwise takes 0. \(p\) is the a priori value, and \(\alpha\) is the weight of the a priori value.  
\[\hat{x}_{k}^{i}=\frac{\sum\limits_{j=1}^{n}\varphi\left(x_{j}^{i}=x_{k}^{j} \right)^{y_{j}+ap}}{\sum\limits_{j=1}^{n}\varphi\left(x_{j}^{i}=x_{k}^{j} \right)^{y_{j}}} \tag{7}\]  
XGBoost adds the complexity of the tree model into the regularization to avoid over-fitting. The model performs well in generalization and supports training and prediction for data containing the missing value. The essence of XGBoost is integrated from decision trees, so the model can be written as Equation (8), where \(k\) is the number of decision trees in the model, \(X_{i}\) is the \(i\)th input sample, \(\hat{y}_{i}\) denotes the predicted value of the model after the \(k\)th iteration, \(f_{k}(X_{i})\) denotes the predicted value of the \(k\)th tree and \(F\) is the set of all decision trees.  
\[\hat{y}_{i}=\sum\limits_{k=1}^{K}f_{k}(X_{i}),\ f_{k}\in F \tag{8}\]  
GBDT requires multiple training of the entire training data at each iteration. With a higher training efficiency, LihhtGBM takes GBDT as its core and makes essential improvements in many aspects, including second-order Taylor expansion for objective function optimization, a histogram algorithm and an optimized leaf growth strategy. It also makes the algorithm more adaptable to high-dimensional data. LightGBM uses the Gradient-based One-Side Sampling algorithm, which maintains the accuracy of the information gain estimation. The information gain is measured using the variance gain after splitting, keeping only those samples with larger contributions. The formula of variance gain is given in Equation (9), where \(j\) is the split feature used, \(d\) is the split point of the sample feature and \(n\) is the number of samples. \(A\) and \(B\) are samples with large and small gradients, respectively. \(l\) and \(r\) are the left and right subtrees, respectively, and \(g\) is the sample gradient.  
\[\widehat{V}_{j}(d)=\frac{1}{n}\left(\frac{\left(\sum\limits_{x_{i}\in A_{l}}g_ {i}+\frac{1-a}{b}\sum\limits_{x_{i}\in B_{l}}g_{i}\right)^{2}}{n_{l}^{j}(d)}+ \frac{\left(\sum\limits_{x_{i}\in A_{r}}g_{i}+\frac{1-a}{b}\sum\limits_{x_{i} \in B_{r}}g_{i}\right)^{2}}{n_{r}^{j}(d)}\right) \tag{9}\]