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$$

并行化

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个叶子结点。