# XGBoost

Ensemble tree model:

$$\hat{y}_{i} = \sum_{k=1}^{K}f_{k}(x_{i}), f_{k}\in\mathcal{F}$$

The objective function:

$$\mbox{obj} = \sum_{i=1}^{n}l(y_{i}, \hat{y}_{i}) + \sum_{k=1}^{K}\Omega(f_{k})$$

where $l$ is the loss term, $\Omega$ is the regularization term.

## Second Order Objective

Step by step:

$$
\begin{equation}
\begin{split}
\mbox{obj}^{(t)} =& \sum_{i=1}^{n}l(y_{i}, \hat{y}_{i}^{(t)}) + \sum_{k=1}^{t}\Omega(f_{k}) \\
=& \sum_{i=1}^{n}l(y_{i}, \hat{y}_{i}^{(t - 1)} + f_{t}(x_{i})) + \Omega(f_{t}) + \mbox{constant}
\end{split}
\end{equation}
$$

Take the taylor expansion up to the second order:

$$\mbox{obj}^{(t)} \approx \sum_{i=1}^{n}[l(y_{i}, \hat{y}_{i}^{(t - 1)}) + g_{i}f_{t}(x_{i}) + \frac{1}{2}h_{i}f_{t}(x_{i})^{2}] + \Omega(f_{t}) + \mbox{constant}$$

$$g_{i} = \frac{\partial l(y_{i}, \hat{y}_{i}^{(t - 1)})}{\partial \hat{y}_{i}^{(t-1)}}$$

$$h_{i} = \frac{\partial^{2} l(y_{i}, \hat{y}_{i}^{(t - 1)})}{{\partial \hat{y}_{i}^{(t-1)}}^2}$$

After removing all the constants, the specific objective at step $t$ becomes:

$$\sum_{i=1}^{n}[g_{i}f_{t}(x_{i}) + \frac{1}{2}h_{i}f_{t}(x_{i})^{2}] + \Omega(f_{t})$$

## Optimization Given Tree Structure

We can define the complexity as ( $w_{j}$ is the value of the $j$-th leaf ):

$$\Omega(f_{t}) = \gamma{T} + \frac{1}{2}\lambda\sum_{j=1}^{T}w_{j}^{2}$$

Rearrange the loss function:

$$
\begin{equation}
\begin{split}
\mbox{obj}^{(t)} = & \sum_{i=1}^{n}[g_{i}f_{t}(x_{i}) + \frac{1}{2}h_{i}f_{t}(x_{i})^{2}] + \gamma{T} + \frac{1}{2}\lambda\sum_{j=1}^{T}w_{j}^{2} \\
=& \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}
\end{split}
\end{equation}
$$

where $I_{j} = \{i|q_{i}=j\}$ is the set of indices of data-points assign to the $j$-th leaf.

Denote $G_{j} = \sum_{i\in{I_{j}}}g_{i}, H_{j} = \sum_{i\in{I_j}}h_{i}$:

$$\mbox{obj}^{(t)} = \sum_{j=1}^{T}[G_{j}w_{j} + \frac{1}{2}(H_{j} + \lambda)w_{j}^2] + \gamma{T}$$

Quadratic optimization result:

$$w_{j}^{\ast} = -\frac{G_{j}}{H_{j} + \lambda}$$

$$\mbox{obj}^{\ast} = -\frac{1}{2}\sum_{i=1}^{T}\frac{G_{j}^2}{H_{j} + \lambda} + \gamma{T}$$

## Learn Tree Structure

When we try to split a leaf into two leaves, the score gain is:

$$\mbox{Gain} = \frac{1}{2}\left [\frac{G_L^2}{H_L + \lambda} + \frac{G_R^2}{H_R + \lambda} - \frac{(G_L + G_R)^2}{H_L + H_R + \lambda}\right ] - \gamma$$

Select split that maximize that Gain, thus form tree structure step-by-step.

## Examples


```python
"""quadratic dataset"""
import numpy as np

np.random.seed(42)
X = np.random.rand(100, 1) - 0.5
y = 3 * X[:, 0] ** 2 + 0.05 * np.random.randn(100)
```


```python
"""basic xgboost"""
import xgboost

reg = xgboost.XGBRegressor()
reg.fit(X, y)
```




    XGBRegressor(base_score=0.5, booster='gbtree', colsample_bylevel=1,
                 colsample_bynode=1, colsample_bytree=1, gamma=0, gpu_id=-1,
                 importance_type='gain', interaction_constraints='',
                 learning_rate=0.300000012, max_delta_step=0, max_depth=6,
                 min_child_weight=1, missing=nan, monotone_constraints='()',
                 n_estimators=100, n_jobs=16, num_parallel_tree=1, random_state=0,
                 reg_alpha=0, reg_lambda=1, scale_pos_weight=1, subsample=1,
                 tree_method='exact', validate_parameters=1, verbosity=None)



0b6593540f041dc53e6d7ca3d6eaa41bff7f095a
ipynb
Jupyter Notebook
machine-learning-book/b5.xgboost.ipynb
newfacade/jupyters
12d3c8bf1b91a7fc2f84e89b5a55efa176f4da23
MIT
2022-01-10T16:20:34.000Z
2022-01-10T16:20:34.000Z
machine-learning-book/b5.xgboost.ipynb
newfacade/jupyters
12d3c8bf1b91a7fc2f84e89b5a55efa176f4da23
MIT
machine-learning-book/b5.xgboost.ipynb
newfacade/jupyters
12d3c8bf1b91a7fc2f84e89b5a55efa176f4da23
MIT
Qwen/Qwen-72B
1. YES
2. YES