> For the complete documentation index, see [llms.txt](https://json007.gitbook.io/svm/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://json007.gitbook.io/svm/kejian/lecture_xgboost_evolution.md).

# xgboost算法演进

## 对数几率比的解释

$$
logit(P(y=1|x)) = \log \frac{P(y=1|x)}{P(y=0|x)} = \log \frac{P(y=1|x)}{1-P(y=1|x)} = w \cdot x \\
P(y=1|x) = logit^{-1} (w \cdot x) = \color{Blue}{\frac {1}{1+\exp(-w \cdot x)}} = \frac {\exp(w \cdot x)}{1+\exp(w \cdot x)} \\
P(y=0|x) = 1-P(y=1|x) = \color{Blue}{\frac {1}{1+\exp(w \cdot x)}}
$$

**Bernoulli分布**

$$p(y|p) = p^y(1-p)^{1-y} = \exp (y \log \frac {p}{1-p} + \log (1-p))$$

## Exponential model的解释

$$
P(y=k) = \frac {\exp(\sum\_{i=1}^n w\_{ki}x\_i)}{\sum\_k \exp(\sum\_{i=1}^n w\_{ki}x\_i)} = \frac {\exp(W\_k^T X)}{\sum\_k \exp(W\_k^T X)}
$$

若只有两类，将分子分母同除分子，则有$$P(Y=1|x) = \frac {1}{1+exp(-w \cdot x)}$$

## 模型参数估计

模型学习时，可以用**极大似然估计法**估计模型参数

$$
\max\_w L(w) = \prod\_j p^y (1-p)^{(1-y)}
$$

如果类别标签为$${-1,1}$$,则极大似然可以改写成

$$
max\_w L(w) = \prod\_j \frac {1}{1+\exp(-y\_j w^T x\_j)} \\
\min\_w -\log L(w) = \sum\_j \log(1+\exp(-y\_j w^T x\_j)) \\
\text{这个形式方便于并行化,比如梯度：} \\
G = \sum\_j \[\frac {1}{1+\exp(-y\_j w^T x\_j)} -1]y\_i x\_i
$$

**L1正则形式：**

$$
\frac {1} {N} \sum\_{n=1}^N \log (1+\exp(-y\_n W^T X\_n)) + \lambda \left | W \right |\_1
$$

## 并行化

![](https://2270971654-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M7DcNFhVrwIk3Tks_pB%2Fsync%2F06ca215f6c26cb9fcc19cccea38ed3d92af51a64.jpg?generation=1589383924791632\&alt=media)

## GBDT+LR

1. 就是先用已有特征训练GBDT模型，
2. 然后利用GBDT模型学习到的树来构造新特征，
3. 最后把这些新特征加入原有特征一起训练模型。  

构造的新特征向量是取值0/1的，向量的每个元素对应于GBDT模型中树的叶子结点。当一个样本点通过某棵树最终落在这棵树的一个叶子结点上，那么在新特征向量中这个叶子结点对应的元素值为1，而这棵树的其他叶子结点对应的元素值为0。新特征向量的长度等于GBDT模型里所有树包含的叶子结点数之和。

举例说明。下面的图中的两棵树是GBDT学习到的，第一棵树有3个叶子结点，而第二棵树有2个叶子节点。对于一个输入样本点x，如果它在第一棵树最后落在其中的第二个叶子结点，而在第二棵树里最后落在其中的第一个叶子结点。那么通过GBDT获得的新特征向量为\[0, 1, 0, 1, 0]，其中向量中的前三位对应第一棵树的3个叶子结点，后两位对应第二棵树的2个叶子结点。

![](https://2270971654-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M7DcNFhVrwIk3Tks_pB%2Fsync%2F01f3f746a44fbd3a4f685caf331ba9dc5dfb0751.png?generation=1589383949336036\&alt=media)