概率提升树

这是本科毕设用到的树，概率提升树（Probabilistic Boosting-Tree, PBT）是Tu在2005年《Probabilistic Boosting-Tree: Learning Discriminative Models for Classification, Recognition, and Clustering》中提到的分层分类框架。

AdaBoost

PBT的实质是对Adaboost的改进，首先回顾一下Adaboost： Adaboost是针对二分类问题设计的，核心点是关注那些被错误分类的训练样本，通过多轮弱分类器的训练逐渐提高被错分样本的权重，对每个弱分类器根据分类精度给一个权重，然后将所有弱分类器用加权的方式制作一个强分类器来达到分类的目的。算法如下：

---

【输入】n个训练样本特征向量及其类别$(x_1,y_1),...,(x_n,y_n)$，其中$x_i\in R^m，y_i\in \{-1,+1\}$

1. 初始化训练样本分布：$D_1(i)=\frac{1}{n}$。

初始的权重是平均的。

2. FOR t = 1..T DO

训练T轮，T个弱分类器

3. 使用分布$D_t$训练弱分类器$h_t：R^m\to Y$

就是训练一个假设：看到这个特征向量→应该判别为什么类别

4. 获得这个假设的加权分类误差：${\theta }_t=\sum _{i:h_t({\mathbf{x}}_{\mathbf{i}})\ne y_i}{D}_t(i)$

也就是把分类错了的权重累加起来。

5. 计算这个假设（弱分类器）的权重：${\alpha }_t=\frac{1}{2}\ln (\frac{1-{\theta }_t}{{\theta }_t})$
6. 更新训练样本分布：$D_{t+1}(i)=\frac{D_t(i)e^{-{\alpha }_t{y}_i{h}_t({\mathbf{x}}_{\mathbf{i}})}}{Z_t}$，其中，$Z_t=\sum _i{D}_t(i)e^{-{\alpha }_t{y}_i{h}_t({\mathbf{x}}_{\mathbf{i}})}=2\sqrt{{\theta }_t(1-{\theta }_t)}$
7. END FOR

【输出】最终的假设（强分类器）：$H(\mathbf{x})=sign(\sum _{t=1}^T{\alpha }_t{h}_t(\mathbf{x}))=sign(g(\mathbf{x}))$

---

有关误差上下界的数学推导和为什么选取α为这个式子，可以参看《Boosting Methods for Automatic Segmentation of Focal Liver Lesions》。我们从结果来分析算法中各个参数的性质和作用：

1. 我们知道弱分类器错误率（加权分类误差）$\theta \le 0.5$（不可能大于0.5比随机猜测更差，否则取反就能得到< 0.5的分类器了）
2. ${\alpha }_t\ge 0$（因为$\frac{(1-\theta )}{\theta }\ge 1$），且其随着错误率的减小而增大，说明错误率越小的弱分类器被看得越重要。
3. 对于一个被错误分类的样本，必有真实类别≠弱分类器判别的假设类别，也就是$y_i\ne h_t({\mathbf{x}}_{\mathbf{i}})$，那么$e^{-({\alpha }_t{y}_i{h}_t({\mathbf{x}}_{\mathbf{i}}))}$必然大于1，反之分对的样本$e^{-({\alpha }_t{y}_i{h}_t({\mathbf{x}}_{\mathbf{i}}))}$必然小于1，当对下一轮的样本分布权重进行归一化之后，被错分的样本权重必然提高，被正确分类的样本权重降低。
4. 如此一来，一旦被错分的样本再次被错分，会造成$\theta$错误率的巨额提升，弱分类器肯定会尽力去避免这样的高错误率，也就是被错分的样本被弱分类器更多地当作考虑因素考虑进去了。

举个实际的应用例子，我们想用决策桩（就是阈值判别器）去划分平面上红色、蓝色小球，初始状态是这样的：

然后第一个桩分类器竖着划分，错分了两个：

于是在重新计算分布后，它们的权重变大了：

第二个分类器更多的考虑了被错分的样本，然而第一次被分对的样本又被分错了两个：

于是再次进行权重调整：

第三次继续划分：

第三次权重调整+第四次继续划分：

最后得到强分类器的决策平面：

当然这是理想情况，实际中不应该划分到这么细，否则会对训练样本产生过拟合。

概率提升树PBT

通常来说，我们希望建立的模型都是生成式模型（generative model），也就是输入考虑的多种因素，输出一个完整的模型，我们可以提取里面任意的信息。举个例子，我想判断一个动物是不是“斑马”，那么我希望建立一个模型，包含“体型”、“花纹”、“生活习性”、“饮食习惯”、“眼睛大小/颜色/花纹”等等，然后输入这些数值，就能够知道它是不是斑马了。从数学上来说，就是求取整体联合分布$P(X)$，代入数值，得到结果，也就是我们希望知道$p(x|y)$。常见的生成式模型有隐马尔科夫模型HMM、朴素贝叶斯模型、高斯混合模型GMM、LDA。

实际中，考虑完所有的东西是不现实的（因此通常都是估计），并且会带来庞大计算量，更多的算法采用了判别式模型（discriminative model），输入特征，输出yes或者no或者其他类别，也就是对后验概率$p(y|x)$建模。常见的判别式模型有线性回归、支持向量机SVM、神经网络。

Adaboost和PBT都是判别式模型。然而Tu发现，Adaboost具有一些缺点：

1. 需要大量的弱分类器，这带来了庞大计算量
2. 没有提取特征向量中的语义信息
3. 更新权重的过程可能导致被分对的样本再次被分错
4. 只适用于二值分类，多类别分类会非常艰难

作者还顺便踩了一脚Grossmann提出的AdaTree，说PBT是对后验概率建模，AdaTree只是在剪枝；PBT每个节点都是强分类器，AdaTree知识把弱分类器放在树结构上而已……下面只讨论PBT的二值分类，多值分类可以转换为二值分类处理。

PBT的二值分类过程

我们知道，Adaboost错误率上限是（这里更换了字母，含义和前面一致）：

$$ϵ\le 2^T\prod _{t=1}^T\sqrt{{ϵ}_t(1-{ϵ}_t)}$$

${ϵ}_t$很快地接近了0.5，然而收敛得非常慢，还造成了反复波动。所以PBT采用分治策略，划分样本空间，当错误率达到一定程度就提前结束Adaboost的训练。

Friedman等人在论文《Additive Logistic Regression:A Statistical View of Boosting》已经证明过，Adaboost在用这样的逻辑回归式去求取后验概率$p(y|x)$：

$$g(\mathbf{x})=\sum _{t=1}^T{\alpha }_t{h}_t(\mathbf{x})\approx \frac{1}{2}\ln \frac{p(y=+1|\mathbf{x})}{p(y=-1|\mathbf{x})}$$

其中$y\in \{-1,+1\}$。于是可以得到估计的后验概率：

$$\{\begin{array}{l}q(+1|\mathbf{x})=\frac{e^{2g(\mathbf{x})}}{1+e^{2g(\mathbf{x})}}\\ q(-1|\mathbf{x})=\frac{e^{-2g(\mathbf{x})}}{1+e^{-2g(\mathbf{x})}}\end{array}$$

然后根据这个估计的后验概率，创造一个极小的控制变量ε，PBT可以对样本空间进行划分：

1. 样本算得$q(+1|x)>0.5+\epsilon$，则划分到正样本空间；
2. 样本算得$q(-1|x)=1-q(+1|x)>0.5+\epsilon$，则划分到负样本空间；
3. 样本算得$q(\pm 1|x)\in [0.5-\epsilon ,0.5+\epsilon ]$，则是疑例，同时分配到两个空间。

随着树的生长，样本空间就越来越纯净，所构建的Adaboost强分类器也就越来越好，并且越来越快，无需从头对整个样本空间进行划分。$ϵ$的作用原文说是为了防止过拟合，通常来说取0.1是合适的。

另外，还限制了每个Adaboost节点的错误上限，当超过上限直接停止生成新的弱分类器，通常来说取0.45是合适的。整个PBT的图像类似于：

我们来描述一下PBT的训练算法：

---

【输入】训练集 $S=({\mathbf{x}}_{\mathbf{1}},y_1,w_1),\dots ,({\mathbf{x}}_{\mathbf{n}},y_n,w_n)$ ，其中 ，其中$\mathbf{x}$为特征向量， $$\begin{gathered} y\in \\ -1,+1 \end{gathered}$$，且 $\sum _{w_i}=1$。

1. 计算并存储经验分布 $q_c(y)=\sum _{y_i=i}{w}_i$
2. 用Adaboost在节点c处根据当前样本训练强分类器$H_c$，当错误率大于$\theta =0.45$的时候提前退出
3. IF 达到最大树深 L THEN
4. $$ return
5. ELSE
6. $$ 新建空集$S_{left}$和$S_{right}$
7. $$ FOR all $x_i\in S_c$ DO
8. $$ 用$g_c(x)$计算 $q(\pm 1|x_i)$
9. $$ IF $q(+1|x_i)>0.5+\epsilon$ THEN
10. $$ 将样本$(x_i,y_i,1)$加入右子树
11. $$ELIF $q(-1|x_i)>0.5+\epsilon$ THEN
12. $$ 将样本$(x_i,y_i,1)$加入左子树
13. $$ELSE
14. $$ 将样本$(x_i,y_i,q(+1|x_i))$加入左子树
    $$ 将样本$(x_i,y_i,q(-1|x_i))$加入左子树
15. $$ ENDIF
16. $$ ENDFOR
17. $$ 将左子树权值归一化，继续训练左子树
18. $$ 将右子树权值归一化，继续训练右子树
19. ENDIF

【输出】训练好的PBT

---

测试算法：

---

【输入】特征$\mathbf{x}$，训练好的PBT

1. 用节点c的强分类器$H_c$，计算$q(\pm 1|\mathbf{x})$
2. IF c是叶子节点
3. $$IF $y==1$
4. $$return $q(+1|\mathbf{x})$
5. $$ELSE
6. $$return $q(-1|\mathbf{x})$
7. $$ENDIF
8. ENDIF
9. IF $q(+1|\mathbf{x})>0.5+\epsilon$ THEN
10. $$return $q(-1|\mathbf{x}){\hat{q}}_{c_{left}}(y)+q(+1|\mathbf{x})p_{c_{right}}(y|\mathbf{x})$
11. ELIF $q(-1|\mathbf{x})>0.5+\epsilon$ THEN
12. $$return $q(-1|\mathbf{x})p_{c_{left}}(y|\mathbf{x})+q(+1|\mathbf{x}){\hat{q}}_{c_{right}}(y)$
13. ELSE
14. $$return $q(-1|\mathbf{x})p_{c_{left}}(y|\mathbf{x})+q(+1|\mathbf{x})p_{c_{right}}(y|\mathbf{x})$
15. ENDIF

【输出】近似的后验概率 $p_c(y|\mathbf{x})$

---

其中，p是Adaboost给出的概率，q是PBT训练过程中计算的概率，$\hat{q}$是训练时得到的先验估计（因为数据没有被分配到那个分支去）。

这样一棵完整的PBT流程就走完了，我们分析一下它的参数：

参数名称	参数符号	参数推荐值	参数说明
调整值	$ϵ$	0.1	越小样本空间划分越开，越过拟合
Adaboost错误率上限	$\theta$	0.45	越小Ada停止越快，精度越低
PBT的最大树深	L	-	越小PBT停止越快，精度越低
Adaboost最大训练轮数	T	-	越小弱分类器越少，精度越低

最后再欣赏一下PBT的结构：