You must know the principles of XGBoost

Principle derivation

The general form of defining the loss function is $L$. Although many tutorials default to $MSE$, this is more general. The base learner is $T(X, \Theta)$, where $\Theta$ is the parameter of the learner

Then:

$$L(y, y_i^k) = L(y, y_i^{k - 1} + T(X_i, \Theta)) = L(y, y_i^{k - 1}) + T(X_i, \Theta) \frac{\\partial L(y, y_i^{k - 1})}{\\partial y_i^{k - 1}} + \frac{1}{2} T^2(X_i, \Theta) \frac{\\partial ^2 L(y, y_i^{k - 1})}{\\partial (y_i^{k - 1})^ 2}$$

Note that although the formulas of $g_i$ and $h_i$ are ugly, once the form of $L$ is determined, $g_i$ and $h_i$ can derive a definite value or a concise form.

For example, assuming $L = MSE$, then $g_i = \frac{ \\partial (y - y_i^{k - 1})^2 }{y_i^{k - 1}} = 2 (y_i^{k -1} - y)$ , $h_i = 2$

Here, the first-order derivative and the second-order derivative are recorded as $g_i$ and $h_i$ respectively to facilitate mathematics. The objective function $Obj$ is:

$$Obj = \sum_i L(y_i, y_i^k) = \sum_i L(y, y_i^{k - 1}) + T(X_i, \Theta) g_i + \frac{1}{2} T^2(X_i, \Theta) h_i$$

It is definitely necessary to do some operations to prevent overfitting of the model. We assume that the base learner is the most commonly used Cart tree, then the complexity of the tree is represented by the number of leaf nodes $T$ and the output value of each leaf node $T_i$.

Because XGBoost is an additive model, the sum of the trained N trees is the final output. Therefore, if the output result of a certain tree is very large, it will dominate the overall output result and is prone to overfitting. Therefore, we hope that the output value of the leaf node of each tree should be as small as possible.

Therefore, the base model uses a regularization formula: $T + \sum_{j = 1} \frac{1}{2} ||T_j||^2$ , where $j$ represents the $j$th leaf node of the tree, and $T_j$ represents the output value of the $j$th leaf node.

The objective function is rewritten as:

$$Obj = \sum_{i = 1}[ L(y, y_i^{k - 1}) + T(X_i, \Theta) g_i + \frac{1}{2} T(X_i, \Theta) h_i ] + T + \sum_{j = 1} \frac{1}{2} ||T_j||^2$$

Anyway, each sample $i$ will always be output to a certain leaf node $j$, and the output result is $T_j$. Then the part of the above formula $\sum_{i = 1}$ is not as good as directly changed to be represented by leaf nodes. In addition, $L(y, y_i^{k - 1})$ is a fixed value and does not affect optimization, so the formula is updated as:

$$Obj = \sum_{j = 1}[ (number of samples at node j) \cdot T_j \cdot G_j + \frac{1}{2} \cdot (number of samples at node j) \cdot T^2_j H_j ] + T + \sum_{j = 1} \frac{1}{2} ||T_j||^2 \\ = \sum_{j = 1}[ (Number of samples at node j) \cdot T_j \cdot G_j + \frac{1}{2} \cdot T^2_j ((Number of samples at node j) \cdot H_j + 1 ) ] + T$$

To optimize $Obj$, it is equivalent to optimizing $(number of samples at node j) \cdot T_j \cdot G_j + \frac{1}{2} \cdot T^2_j ((number of samples at node j) \cdot G_j + 1 )$. This is a simple quadratic equation of one variable. The position and size of the optimal value can be obtained through the discriminant formula

$$T_j^* = \frac{ (Number of samples at node j) \cdot G_j }{(Number of samples at node j) \cdot H_j + 1}\\ Obj_{min} = ... (I won’t write it down anymore, anyway, just substitute T_j^* to get the minimum value of the quadratic equation)$$

Training method

The conclusion has been derived: the output value of the leaf node $j$ of a tree needs to be $T_j^*$, and the value of the optimization target becomes $Obj_{min}$. The question now is how to construct such a Cart tree.

First, suppose there are three features $A, B, C$:

Characteristics	Value range
Feature A	[1, 3, 6, 8, 10]
Feature B	[3, 5, 9, 89, 49]
Feature c	[2, 4, 5, 7, 10, 22]

Traverse each feature, traverse all possible split nodes for each feature, and calculate $Obj$ before splitting, $Obj_{left}$ of the left subtree after splitting, and $Obj_{right}$ of the right subtree respectively. Since we have calculated the formula of $Obj$, these can directly obtain specific values. We compare the gain of the split $Gain = Obj_{left} + Obj_{right} - Obj$ , and determine the best split feature and split value by finding the maximum gain.

Common difficulties

The training speed is too slow, what should I do?

In engineering implementation, XGBoost adopts the pre-sorting idea to accelerate training. For example, for feature A, we sort all possible values of feature A (the above table is already the sorted result)

When we select a certain value split node, we will get the left subtree and the right subtree, and calculate $Obj$ respectively. If we continue to calculate the next feature value as the split node at this time, we only need to move some samples of the right subtree to the left subtree, greatly reducing the amount of calculation.

How to parallelize?

XGboost itself is a serial model and cannot be parallelized. The generation of the next tree must wait for the completion of the previous tree. But the generation inside the tree can be parallelized.

XGBoost internally stores data according to the Block structure. Specifically, it stores data according to characteristic columns. The block structure allows independent processing of each feature, for example, one thread calculates the split gain on feature A, and another thread calculates the split gain on feature B. In addition, Block block structure takes advantage of the locality principle of computers, because when traversing all possible values ​​of a feature, samples need to be frequently classified (classified into the left subtree or the right subtree). Block data directly puts the feature column and sample data together, and the cache hit rate is higher.

Summary: Use Block to store the data of an entire feature column, and the information gain calculation for different features can be parallelized by multiple threads. Within Block, the early version of XGBoost used a pre-sorting idea, because it is faster to find the best split point. Later versions used the histogram approximation method in LightGBM to separate continuous features into different Bin boxes. This is equivalent to having only data in different Bin boxes. Calculate the gradient and Hessian matrix inside the Bin box.

How to deal with high-dimensional features

We know that when performing feature splitting, it is necessary to traverse all features and all values of the features. In the case of high-dimensional features, traversing feature values will be very time-consuming.

XGBoost approximates through the bucketing idea (also called histogram approximation method), sorts all possible values of a certain feature (such as A), and then divides it into several buckets, counts $G_i$ and $H_i$ of each bucket respectively, and then tries to split each bucket to find the gain. This method will reduce the training time

How to alleviate overfitting

In addition to the regularization ideas mentioned above, XGBoost also draws on the random feature selection method in RF, also called column sampling. When splitting a certain node, why bother traversing all the features (such as A, B, C)? Isn't it better to extract some of them? For example, just extract A and B and calculate the split gain separately.

The level wise growth strategy of XGBoost can also be used as a measure to alleviate overfitting. When the nodes of one layer are split, they are split at the same time, so that a certain node will not be over-split (leaf wise). Of course, this method takes up slightly more memory.

How to do classification problems

We know that the base learner Cart tree can be used for classification or regression problems.

In the second classification, we directly process the output result of the overall model with Sigmoid, thus turning the real value output into probability, then the loss function is modified to Log Loss, that is:

$$Log Loss(y, \hat{y}_i^k) = -(y \log (\hat{p_i}) + (1 - y) \log( 1 - \hat{p_i}))\\ \hat{p_i} = sigmoid(\hat{y}_i^k)$$

This can also calculate the first and second derivatives:

$$g_i = \frac{\partial LogLoss}{\partial \hat{y}_i^k } = \hat{p_i} - y_i\\ h_i = \frac{ \partial^2 LogLoss }{ \partial (\hat{y}_i^k)^2 } = \hat{p_i} (1 - \hat{p_i})$$

In multi-classification problems, the output of XGBoost is slightly different, because one tree cannot output the probabilities of multiple categories, so we let one tree focus on the prediction of one category. In this way, the $N$ tree outputs the scores of $N$ categories, which are then normalized to probabilities through the softmax function.

$$p_i = \frac{\exp (f_i(x))}{\sum_{j = 1}^C \exp(f_j(x))}$$

N trees are constructed in each round, and $M \cdot N$ trees are constructed in $M$ rounds of training.

How is the importance of xgboost features evaluated?

Feature importance evaluation is a very common problem, and the evaluation method is also common in GBDT-type models.

Feature importance can be calculated through the Gini index: during the training process, the total number of feature splits is recorded (more splits must be important), the total/average information gain is used to quantify the feature importance, and finally the importance of all features is ranked. This is a method for evaluating the feature importance of a single tree species. Then GBDT/XGBoost is an Ensemble of multiple trees, just average it.

Which one of LR and XGBoost is suitable for processing high-dimensional sparse data?

GBDT's tree models (XGBoost, LightGBM) are not suitable for processing high-dimensional data, and LR is more suitable.

Most of the high-dimensional sparse features are 0, and only a few are non-0. The tree model can only utilize a very small amount of non-zero information when splitting features, and LR can handle this well using weights. It can be explained similarly that GBDT is not suitable for one hot.