提升树模型

提升方法实际采用加法模型(即基函数的线性组合)与前向分布算法。以决策树为基函数的提升方法称为提升树(boosting tree)。提升树模型和梯度提升树是两种不同的模型，梯度提升是在提升树模型上进一步优化。提升树对分类问题决策树是二叉分类树，对回归问题决策树是二叉回归树；而梯度提升树对分类问题、回归问题都使用的是CART回归树。具体情况，还需要查看其对应的实现方法。TODO：sklearn里面的GBDT实现方式。提升树模型可以表示为决策树的加法模型：

$$ f_{M}(x)=\sum_{m=1}^{M}T(x;\Theta_{m}) $$
其中 $ T(x;\Theta_{m}) $ 表示决策树， $ \Theta_{m} $ 为决策树的参数， M 为树的个数。

# 提升树算法

提升树算法采用前向分布算法，首先确定初始提升树 $ f_{0}=0 $ ,第m步的模型是： $ f_{m}=f_{m-1}(x)+T(x; \Theta_{m}) $ 。

其中， $ f_{m-1}(x) $ 为当前模型，通过经验风险极小化确定下一颗决策树参数 $ \Theta_{m} $ ：
$$ \Theta_{m}^{*}=argmin_{\Theta_{m}}\sum_{i=1}^{N}L(y_{i},f_{m-1}(x_{i})+T(x_{i};\Theta_{m})) $$

树的线性组合可以很好的拟合训练数据，即使数据中的输入与输出关系复杂也是，所以提升树一般是高功能的学习算法。

下面讨论针对不同问题的提升树学习算法，主要区别在于损失函数的不同。包括用平方误差损失的回归问题，用指数损失函数的分类问题，以及用一般损失函数的决策问题。

二分类问题

对于二分类问题，提升树算法只需将 AdaBoost 算法中的基本分类器限定为二类分类树即可，可以说这时的提升树算法是 AdaBoost 算法的特殊情况。

回归问题

已知一个训练数据集 $ T = ((x_{1},y_{1}),(x_{2},y_{2}),…,(x_{N},y_{N})),x_{i}\epsilon \chi \subseteq \mathbb{R}^{n} $ , $ \chi $ 为输入空间，$ y_{i}\epsilon y \subseteq \mathbb{R} $, y 为输出空间。如果将输入空间 $ \chi $ 划分为 $ \jmath $ 个互不相交的区域 $ R_{1},R_{2},…,R_{J} $ ，并且在每个区域上确定输出常量 $ c_{j} $ , 那么树可表示为:

$$ T(x;\Theta)=\sum_{j=1}^{J}c_{j}I(x\epsilon R_{j}) $$

其中，参数 $ \Theta = ((R_{1},c_{1}),(R_{2},c_{2}),…,(R_{J},c_{J})) $ 表示树的区域划分和各区域上的常数，J 是回归树的复杂度，即叶节点个数。

回归问题提升树的前向分布算法为：

$$ f_{0}(x)=0 $$
$$ f_{m}(x)=f_{m-1}+T(x;\Theta_{m}),m=1,2,…,M $$
$$ f_{M}(x)=\sum_{m=1}^{M}T(x;\Theta_{m}) $$

在前向分布算法的第m步，给定当前模型 $ f_{m-1}(x) $, 需求解

$$ \hat{\Theta_{m}}=arg\underset{\Theta_{m}}{min}\sum_{i=1}^{N}L(y_{i},f_{m-1}(x_{i})+T(x_{i};\Theta_{m})) $$

得到 $ \hat{\Theta_{m}} $，即第m颗树的参数.

当采用平方误差损失函数时,

$$ L(y,f(x))=(y-f(x))^{2} $$

其损失函数为:

$$ L(y,f_{m-1}(x)+T(x;\Theta_{m}))=[y-f_{m-1}(x)-T(x;\Theta_{m})]^{2}=[r-T(x;\Theta_{m})]^{2} $$

这里的 $ r=y-f_{m-1}(x) $, 是当前模型拟合数据的残差。所以，对于回归模型的提升树而言，只需简单的拟合当前模型的残差。

回归问题的提升树算法

输入：训练数据集 $ T = ((x_{1},y_{1}),(x_{2},y_{2}),…,(x_{N},y_{N})),x_{i}\epsilon \chi \subseteq \mathbb{R}^{n} $.

输出：提升树 $ f_{M}(x) $.

(1) 初始化 $ f_{0}(x)=0 $
(2) 对 m=1,2,…,M
– (a)按上式计算残差 $ r_{mi}=y_{i}-f_{m-1}(x_{i}), i=1,2,…,N $
– (b)拟合残差 $ r_{mi} $ 学习一个回归树，得到 $ T(x;\Theta_{m}) $
– (c)更新 $ f_{m}(x)=f_{m-1}(x)+T(x;\Theta_{m}) $
(3) 得到回归问题提升树 $ f_{M}(x)=\sum_{m=1}^{M}T(x;\Theta_{m}) $

梯度提升树(GBDT)

负梯度拟合

GBDT损失函数拟合方法采用的是 Freidman 提出的损失函数负梯度来拟合本轮损失近似值，进而拟合一个CART回归树。第t轮的第i个样本的损失函数的负梯度表示为：

$$ r_{ti}=-\left [ \frac{\partial L(y_{i},f(x_{i})))}{\partial f(x_{i})} \right ]_{f(x)=f_{t-1}(x)} $$
利用 $ (x_{i}, r_{ti})(i=1,2,…,m) $ ，可以拟合一颗CART回归树，其对应的叶子点区域 $ R_{tj}, j=1,2,…,J $ .其中J为叶子结点个数。

针对每一个叶子结点的样本，我们求出使损失函数最小，也就是拟合叶子结点最好的输出值 $ c_{tj} $ 如下：
$$ c_{tj}=\underbrace{argmin}_{c}\sum_{x_{i}\epsilon R_{tj}}L(y_{i},f_{t-1}(x_{i})+c) $$
这样就可以得到本轮决策树拟合函数如下：
$$ h_{t}(x)=\sum_{j=1}^{J}c_{tj}I(x\epsilon R_{tj}) $$
从而本轮最终得到的强学习器的表达式为：
$$ f_{t}(x)=f_{t-1}(x) + \sum_{j=1}^{J}c_{tj}I(x\epsilon R_{tj}) $$
通过损失函数的负梯度来拟合，我们找到了一种通用的拟合损失误差的办法，这样无轮是分类问题还是回归问题，我们通过其损失函数的负梯度的拟合，就可以用GBDT来解决我们的分类回归问题。区别仅仅在于损失函数不同导致的负梯度不同而已。

## GBDT回归问题

输入: 训练数据集 $ T=((x_{1}, y_{1}),(x_{2},y_{2}),…,(x_{N},y_{N})),x_{i}\epsilon \chi \subseteq \mathbb{R}^{n} $ ;损失函数 $ L(y,f(x)) $

输出：回归树 $ \hat{f}(x) $

- (1) 初始化: $ f_{0}(x)=arg\underset{c}{min}\sum_{i=1}^{N}L(y_{i},c) $
- (2) 对迭代次数 $ t=1,2,…,T $ 有：
– (a) 对 $ i=1,2,..,N $ ，计算：$ r_{ti}=-\left [ \frac{\partial L(y_{i},f(x_{i})))}{\partial f(x_{i})} \right ]_{f(x)=f_{t-1}(x)} $
– (b) 对 $ (x_{i},r_{ti}) $ 拟合一个回归树，得到第 t 课树的叶节点区域 $ R_{tj}, j=1,2,…,J $
– (c) 对 $ j=1,2,…,J $ , 计算 $ c_{tj}=\underbrace{argmin}_{c}\sum_{x_{i}\epsilon R_{tj}}L(y_{i},f_{t-1}(x_{i})+c) $
– (d) 更新 $ f_{t}(x)=f_{t-1}(x) + \sum_{j=1}^{J}c_{tj}I(x\epsilon R_{tj}) $
- (3) 得到强学习器为:
$$ f(x)=f_{T}(x)=f_{0}(x)+\sum_{t=1}^{T}\sum_{j=1}^{J}c_{tj}I(x\epsilon R_{tj}) $$

二类分类问题

对于二元GBDT，使用类似于逻辑回归的对数似然损失函数，则损失函数为：

$$ L(y,f(X))=log(1+exp(-yf(x))) $$

其中 $ y\epsilon(-1,+1) $ .则此时的负梯度误差为:

$$ r_{ti}=-\left [ \frac{\partial L(y_{i},f(x_{i})))}{\partial f(x_{i})} \right ]_{f(x)=f_{t-1}(x)}=y_{i}/(1+exp(y_{i}f(x_{i}))) $$

对于生成的决策树，各个叶子节点的最佳负梯度拟合值为:

$$ c_{tj}=arg\underset{c}{min}\sum_{x_{i}\epsilon R_{tj}}log(1+exp(-y_{i}(f_{t-1}(x_{i})+c))) $$

由于上式比较难以优化，一般使用近似值代替为:

$$ c_{tj}=\sum_{x_{i}\epsilon R_{tj}}r_{ti}/\sum_{x_{i}\epsilon R_{tj}}|r_{ti}|(1-|r_{ti}|) $$

除了负梯度计算和叶子节点的最佳负梯度拟合的线性搜索，二元GBDT分类和GBDT回归算法过程相同。

多元分类问题

多元 GBDT 要比二元 GBDT 复杂一些，对应的多元逻辑回归和二元逻辑回归的复杂度差别。假设类别树设为K,则此时的对数似然损失函数为：

$$ L(y,f(x))=-\sum_{k=1}^{K}y_{k}logp_{k}(x) $$

其中，如果样本输出类别为k, 则 $ y_{k}=1 $, 第k类的概率 $ P_{k}(x) $ 的表达式为：

$$ p_{k}=exp(f_{k}(x))/\sum_{l=1}^{K}exp(f_{l}(x)) $$

通过上面两式，可以推导出，第 t 轮的第i个样本对应类别l的负梯度误差为:

$$ r_{til}=-\left [ \frac{\partial L(y_{i},f(x_{i}))}{\partial f(x_{i})} \right ]_{f_{k}(x)=f_{l,t-1}(x)}=y_{il}-p_{l,t-1}(x_{i}) $$

观察上式可以得出，这里的误差是样本i对应类别l的真实概率和t-1轮预测概率的差值。

对于生成的决策树，我们各个叶子节点的最佳负梯度拟合值为：

$$ c_{tjl}=arg\underset{c_{jl}}{min}\sum_{i=0}^{m}\sum_{k=1}^{K}L(y_{k},f_{t-1,l}(x)+\sum_{j=0}^{J}c_{jl}I(x_{i}\epsilon R_{tjl})) $$

由于上式比较难以优化，一般采用的近似替代值为：

$$ c_{tjl}=\frac{K-1}{K}\frac{\sum_{x_{i}\epsilon R_{tjl}}r_{til}}{\sum_{x_{i}\epsilon R_{tjl}}|r_{til}|(1-|r_{til}|)} $$

3. GBDT