Tree Ensemble methods
- 不需要归一化（normalization)
- 能够学习到特征之间的高阶交互
- 可用于分类、回归、排序、……
Boosting Tree
- 二叉分类树：分类问题决策树
- 二叉回归树：回归问题决策树
前向分步算法
输入:
- 样本特征数据$x_1,\cdots,x_N$
- 样本因变量数据$y_1,\cdots,y_N$
- 初始提升树$H_0(x)=h_0(x)=0$
输出： 提升树
$$H(x)=\sum_{t=1}^Th_t(x;\theta_t)$$
- 对于$t=1,2,\cdots,T$，
- 要训练一棵决策树$h_t(x;\theta_t)$
- 提升树为
$$H_t(x)=H_{t-1}(x)+h_t(x;\theta_t)$$ - 通过经验风险最小化确定该棵决策树的参数$\theta_t$
$$ \hat{\theta}t = \arg \min{\theta_t} \sum_{i=1}^N L \left( y_i, H_{t-1} (x_i) + h_t (x_i; \theta_t) \right)$$
损失函数
针对不同问题的提升树学习算法，使用的损失函数不同
- 回归问题：平方误差损失函数
- 分类问题：指数损失函数
- 一般决策问题：一般损失函数
对于二分类问题，若将Post not found: 算法-AdaBoost AdaBoost算法中的基分类器限定为二类决策树，则为提升树。
此时，Boosting Tree是AdaBoost的特殊情况。
回归提升树
输入：训练数据集${(x_1,y_1),\cdots, (x_N,y_N)}$
$x_i\in X\subseteq \mathbb{R}^p,\quad y_i\in Y\subseteq \mathbb{R}$
输出：提升树
$$H(x)=\sum_{t=1}^Th_t(x)$$
- 初始化提升树$H_0(x)=0$
- 对$t=1,\cdots,T$($T$为迭代次数)，
- 计算上一轮迭代的残差
$$r_i^{(t)}=y_i-H_{t-1}(x_i),\quad i=1,\cdots,N.$$ - 拟合残差$r_i^{(t)}$学习得到一棵回归树
$$h_t(x;\theta_t)$$ - 更新提升树
$$H_t(x)=H_{t-1}(x)+h_t(x;\theta_t)$$
Objective
$$Obj= \sum_{i=1}^n l( y_i,\hat{y}i ) + \sum{k=1}^K \Omega (f_k)$$
-
如何定义树的复杂度$\Omega(f_k)$？
-
树的结点数、树的深度
-
叶子权重的$l2$范数
-
……
-
信息增益information gain → 训练误差
-
剪枝prunning → 由结点数定义的正则化
-
最大深度max depth → 函数空间的约束
-
smoothing leaf values → 叶子权重的$l2$正则
类别
- Gradient Boosted Machine：使用平方损失$l(y_i,\hat{y}_i)=(y_i-\hat{y}_i)^2$
- LogitBoost：使用Logistic损失
$$l(y_i, \hat{y}_i)= y_i \ln (1+e^{-\hat{y}_i}) +(1-y_i) \ln (1+e^{\hat{y}_i})$$
Pre-stopping
- stop split if the best split have negative gain
- but maybe a split can benefit future splits
Post-Prunning
事后剪枝
- grow a tree to maximum depth, recursively prune all the leaf splits with negative gain
