决策树

1. 历史背景

1984 年，Leslie Valiant 提出概率近似正确（probably approximately correct，PAC）学习框架。当存在算法满足 $P[R(h_S)\le\epsilon]\ge 1-\delta$，$R(h_S)$ 是算法 $h$ 数据集 $S$ 上的经验误差，同时样本量 $m\ge poly(1/\epsilon,1/\delta,n,size(c))$，则称该算法为 PAC可学习的（learnable）。当 $\epsilon \in (0, 0.5)$ 且 $\delta \in (0, 0.5)$ 时，即算法学习成功的概率大于 $0.5$，且误分类率 $err(h)<\epsilon$，则称算法拟合的那个概念是强可学习的；如果满足 $\delta \in [0, 0.5]$ 的基础上，算法的误差率 $err(h)<1/2-\gamma$，则称为弱可学习。

1988 年，Michael Kearns 提出问题 “is weakly learnability equivalent to strong learnability?” 是提升机器学习算法（boosting）的起源。

1990 年，Yoav Freund 提出 Boost-by-majority 算法，并给予证明，即 PAC 学习架构下强可学习和弱可学习是充分必要条件，但该算法并不实用。

1995 年，Yoav Freund 和 Robert Schapire 提出 AdaBoost 算法，他们的工作获得了 2003 年哥德尔奖。

2000 年，Friedman 等人提出 Boosting Tree 算法。

2. Adaboost 算法

boosting 算法是一种集成算法，主要作用就是将弱可学习分类器转化为强可学习分类器，因为在分类问题中，给定一个训练样本集，弱分类器是比较容易得到的。Adaboost 是自适应算法，通过调整训练数据的概率分布，使随后的弱学习器更关注那些被先前分类器错误分类的实例，这样就保证在不同的弱分类器中，使得所有训练数据都能被有效的分类，最后通过多个弱学习器加权多数表决的方法，得到最终分类结果。

给定二元分类训练数据集：

$$T=\{(\mathbf x_1,y_1),(\mathbf x_2,y_2),...,(\mathbf x_N,y_N)\}$$

其中，${\displaystyle \mathbf x_i\in \mathcal{X}\subseteq R^n}$ 表示实例的特征向量，$y\in \mathcal{Y}=\{-1,+1\}$ 表示实例的类别，也就是标记（label）。给定实例特征向量$\mathbf x$，输出所属的类 $y$ 。

首先初始化训练数据集的权重

$$D_1=(1/N,1/N,\dots,1/N)$$

假设第 $t$ 轮的权重为 $D_t$，通过弱分类算法 $A$ 产生一个弱分类器 $h_t\in \mathcal{H},h_t:\mathcal{X}\rightarrow \mathcal{Y}$，

弱分类器的误分类率为

$$\begin{aligned} \epsilon_t &= error_{D_t}(h_t)\\ &=P(h_t(\mathbf x_i)\ne y_i) \\ &=\sum_{i=t}^N D_t(i)\cdot I (h_t(\mathbf x_i)\ne y_i)\\ &=\sum_{h_t(\mathbf x_i)\ne y_i} D_t(i) \end{aligned}$$

弱分类算法 $A$ 的损失函数就是最小化误分类率 $\epsilon_t$，在这里需要保证 $\epsilon_t<1/2$，否则就不是弱分类器，算法停止。

计算弱分类器 $h_t$ 的系数

$$\alpha_t=\frac{1}{2}\ln \frac{1-\epsilon_t}{\epsilon_t}$$

从公式中可以看出，当 $\epsilon_t<1/2$ 时，$\alpha_t>0$，且 $\alpha_t$ 随着 $\epsilon_t$ 的减小而增加，因此分类误差率越小的弱分类器在最后多数表决时起的作用越大。

更新训练数据集的权重

$$D_{t+1}(i)=\frac{D_t(i)}{Z_t}e^{-\alpha_ty_ih_t(\mathbf x_i)}$$

$Z_t$ 是规范化因子，它保证了更新后的权重也是一个概率分布

$$Z_t=\sum_{i=1}^N D_t(i)e^{-\alpha_ty_ih_t(\mathbf x_i)}$$

从更新公式中可以看出，当分类正确时，权重乘以 $e^{-\alpha}$ 会降低 ，当分类错误时，权重乘以 $e^{\alpha}$ 会增加。相较于正确分类样本，误分类样本的权值被放大 $\displaystyle e^{2\alpha}=\frac{1-\epsilon}{\epsilon}$倍。

将以上步骤重复 $T$ 次，就得到了 $T$ 个弱分类器，最终 Adaboost 的输出结果为

$$H(\mathbf x)=\mathrm{sign}\left(\sum_{t=1}^T \alpha_t h_t(\mathbf x)\right)$$

在式中，$\displaystyle \sum_{t=1}^T \alpha_t h_t(\mathbf x)$ 的正负号决定了实例 $\mathbf{x}$ 的分类结果，绝对值表示分类的确信度。

2. Adaboost 算法分析与证明

Adaboost 算法对于给定的训练数据集，对于足够多的轮次 $T$ 之后，可以证明出最后的分类器 $H$ 的训练误差很小。定义 $H$ 在训练数据集 $S$ 上的训练误差为

$$err_S(H)=\frac{1}{N}\sum_{i=1}^N \mathbf I (H(\mathbf x_i)\ne y_i)$$

对于每一轮 $t$，目前为止构建的弱分类器的线性组合为

$$F_t(\mathbf x)=\sum_{j=1}^t\alpha_j h_j(\mathbf{x})$$

引理 1. 对于每一轮 $t$，$D_{t+1}(i)\propto e^{-y_iF_t(\mathbf x_i)}$，即分布 $D_{t+1}(i)$ 根据历史弱分类器 $F_t$ 的值对结果进行加权。

证明：

$$\begin{aligned} D_{t+1}(i) &= \frac{D_t(i)}{Z_t}e^{-\alpha_ty_ih_t(\mathbf x_i)}\\ &=\frac{D_{t-1}(i)}{Z_tZ_{t-1}}e^{-\alpha_ty_ih_t(\mathbf x_i)}e^{-\alpha_{t-1}y_ih_{t-1}(\mathbf x_i)} \\ &\dots \\ &= \frac{D_1(i)}{ \prod_{j=1}^t Z_j}e^{ -y_i \sum_{j=1}^t\alpha_jh_j(\mathbf x_i)} \\ &= \frac{1}{ N\prod_{j=1}^t Z_j}e^{-y_iF_t(\mathbf x_i)} \end{aligned}$$

因此，分布 $D_{t+1}$ 根据目前得到的函数 $F_t$ 的间隔（margin） $y_iF_t(\mathbf x_i)$ 为 $S$ 中的样本 $(\mathbf x_i, y_i)$ 分配权重。间隔越小表示分类效果越差，因此权重越大，这迫使第 $t+1$ 轮的弱学习器专注于 $F_t$ 未准确分类的实例。

引理 2. $\displaystyle err_S(H)\le \frac{1}{N}\sum_{i=1}^N e^{-y_iF_T(\mathbf x_i)}=\prod_{j=1}^T Z_j$

证明：当 $H(\mathbf x_i)\ne y_i$ 时，$y_iF_T(\mathbf x_i)\le0$，因此 $e^{-y_iF_T(\mathbf x_i)}\ge1$，从而得到

$$err_S(H)\le 1 \le \frac{1}{N}\sum_{i=1}^N e^{-y_iF_T(\mathbf x_i)}$$

进一步地，由引理 1 得到

$$\begin{aligned} \frac{1}{N}&\sum_{i=1}^N e^{-y_iF_T(\mathbf x_i)} \\ &= \prod_{j=1}^t Z_j \sum_{i=1}^ND_{t+1}(i) \end{aligned}$$

由于

$$\displaystyle \sum_{i=1}^ND_{t+1}(i) =1$$

因此

$$\displaystyle \frac{1}{N}\sum_{i=1}^N e^{-y_iF_T(\mathbf x_i)}=\prod_{j=1}^T Z_j$$

引理 3. 对于给定的 $\alpha_t$，每一轮归一化常数具有简单形式 $Z_t=2\sqrt{\epsilon_t(1-\epsilon_t)}$

证明：根据前面可知

$$\displaystyle e^{2\alpha_t}=\frac{1-\epsilon_t}{\epsilon_t}$$

推出

$$\displaystyle e^{-\alpha_t}=\sqrt{\frac{\epsilon_t}{1-\epsilon_t}}$$

并且

$${\displaystyle y_ih_t(\mathbf x_i)={ \begin{cases} +1&\mathrm{if}\quad h_t(\mathbf x_i)=y_i\\ -1&\mathrm{otherwise} \end{cases} } }$$

因此

$$\begin{aligned} Z_t&=\sum_{i=1}^N D_t(i)e^{-\alpha_ty_ih_t(\mathbf x_i)}\\ &= \sum_{i=1}^N D_t(i)\left(e^{-\alpha_t}I( h_t(\mathbf x_i)=y_i)+e^{\alpha_t}I( h_t(\mathbf x_i)\ne y_i)\right)\\ &=e^{-\alpha_t}\sum_{i=1}^N D_t(i)\cdot I( h_t(\mathbf x_i)=y_i) + e^{\alpha_t}\sum_{i=1}^N D_t(i)\cdot I( h_t(\mathbf x_i)\ne y_i)\\ &= \sqrt{\frac{\epsilon_t}{1-\epsilon_t}} (1-\epsilon_t)+\sqrt{\frac{1-\epsilon_t}{\epsilon_t}}\epsilon_t \\ &=2\sqrt{\epsilon_t(1-\epsilon_t)} \end{aligned}$$

引理 4. $\displaystyle\gamma \in (0,\frac{1}{2}]$时，如果 $\displaystyle\epsilon_t\le \frac{1}{2}-\gamma$，存在 $err_S(H)\le e^{-2T\gamma^2}$

证明：由引理 2 和引理 3 可得

$$\begin{aligned} err_S(H)&\le \prod_{t=1}^T Z_j\\ &= \prod_{t=1}^T 2\sqrt{\epsilon_t(1-\epsilon_t)}\\ &\le2^T\prod_{t=1}^T \sqrt{(\frac{1}{2}-\gamma)(\frac{1}{2}+\gamma)},\\ &\qquad \text{ since } \epsilon_t\le \frac{1}{2}-\gamma，\mathrm{and} \sqrt{x(1-x)} \text{ is an increasing function of } x \text{ on } (0,\frac{1}{2}]\\ &= 2^T\prod_{t=1}^T \sqrt{\frac{1}{4}-\gamma^2} \\ &= (1-4\gamma^2)^{T/2}\\ &\le e^{-2T\gamma^2},\text{ since } 1-x\le e^{-x} \end{aligned}$$

从引理中可以看出，如果弱学习器的分类结果比随机预测 $(0.5)$ 的结果要好，那么最终分类器 $H$ 的误差将随着 $T$ 的增加呈指数下降，且对于足够大的 $T$，误差会变得足够小。

3. Adaboost 损失函数

前面的算法过程是直接给出了 $\alpha$ 的取值方式，如果给定 Adaboost 的损失函数，事实上每一步 $\alpha_t$ 的取值都是为了使损失函数最小。

定义指数损失函数为

$$L(y,f)=e^{-yf}$$

定义 Adaboost 的损失函数为指数损失函数

$$L(Y,F_T(X))=\sum_{i=1}^N e^{-y_iF_T(\mathbf x_i)}$$

其中

$$F_T(\mathbf x)=\sum_{j=1}^T\alpha_j h_j(\mathbf{x})$$

求解该损失函数极小化问题是一个复杂的优化问题，可以使用前向分布算法的思想。前向分步算法类似动态规划中的前向计算，每一步只求取一个的最优分类器 $h_j$ 及其参数 $\alpha_j$，与之前的过程无关，即前 $t-1$ 步求取的分类器及参数都当做定值。

从上述思想中可以得到第 $t$ 次迭代得到的分类器为

$$F_t(\mathbf{x}_i)=F_{t-1}(\mathbf{x}_i)+\alpha_th_t(\mathbf{x}_i)$$

损失函数为

$$\begin{aligned} L(Y,F_t(X))&=\sum_{i=1}^N e^{-y_i(F_{t-1}(\mathbf{x}_i)+\alpha_th_t(\mathbf{x}_i))}\\ &=\sum_{i=1}^Ne^{-y_iF_{t-1}(\mathbf{x}_i)} e^{\alpha_t y_ih_t(\mathbf{x}_i)}\\ &=\sum_{i=1}^N (N\prod_{j=1}^{t-1} Z_j) D_{t}(i) e^{\alpha_t y_ih_t(\mathbf{x}_i)} \end{aligned}$$

最小化上述损失函数，对于任意的 $\alpha_t>0$，使损失函数最小可以得到

$$h_t(\mathbf{x})=\arg\min_h \sum_{i=1}^N D_{t}(i)I( h_t(\mathbf x_i)\ne y_i)$$

其实就是弱分类器的误分类率

由之间的定理 3 将损失函数进一步拆分

$$\begin{aligned} L(Y,F_t(X))&=(N\prod_{j=1}^{t-1} Z_j)\sum_{i=1}^N D_t(i)e^{-\alpha_ty_ih_t(\mathbf x_i)}\\ &= (N\prod_{j=1}^{t-1} Z_j)\sum_{i=1}^N D_t(i)\left(e^{-\alpha_t}I( h_t(\mathbf x_i)=y_i)+e^{\alpha_t}I( h_t(\mathbf x_i)\ne y_i)\right)\\ &= (N\prod_{j=1}^{t-1} Z_j)(e^{-\alpha_t} (1-\epsilon_t)+e^{\alpha_t}\epsilon_t) \\ \end{aligned}$$

对 $\alpha_t$ 求导，并令导数为 0，可以得到

$$-e^{-\alpha_t} (1-\epsilon_t)+e^{\alpha_t}\epsilon_t=0$$

解得

$$\alpha_t=\frac{1}{2}\ln{\frac{1-\epsilon_t}{\epsilon_t}}$$

结果与前面给出的一致。

实际上每一步 $t$ 的弱分类器是加权后的误分类率 $\epsilon_t$ 最小，然后确定最小的误分类率之后，$\alpha_t$ 的取值使最终分类器的损失函数最小。

3. Adaboost 回归

相对应于分类问题的误分类率，在回归问题中则是误差率，需要归一化处理并最后取平均值得到平均误差率，保证其值在 $[0,1]$ 之间即可。

首先初始化训练数据集的权重

$$D_1=(1/N,1/N,\dots,1/N)$$

假设第 $t$ 轮的权重为 $D_t$，通过弱分类算法 $A$ 产生一个弱学习器 $h_t\in \mathcal{H},h_t:\mathcal{X}\rightarrow \mathcal{Y}$

每个样本的相对误差

$$e_i = \frac{|y_i-h(\mathbf x_i)|}{\displaystyle \max_j |y_j-h(\mathbf x_j)|}$$

这里是曼哈顿距离，如果是平方误差则为

$$e_i = \frac{(y_i-h(\mathbf x_i))^2}{\displaystyle \max_j (y_j-h(\mathbf x_j))^2}$$

指数误差则为（存疑）

$$e_i = 1-\exp({\frac{|y_i-h(\mathbf x_i)|}{\displaystyle\max_j |y_j-h(\mathbf x_j)|}})$$

第 $t$ 轮弱学习器的误差率为

$$\epsilon_t = \sum_i^N D_t(i)e_i$$

计算弱学习器 $h_t$ 的系数

$$\alpha_t=\frac{1}{1-\epsilon_t}-1=\frac{\epsilon_t}{1-\epsilon_t}$$

更新训练数据集的权重

$$D_{t+1}(i)=\frac{D_t(i)}{Z_t}\alpha_t^{1-e_i}$$

$Z_t$ 是规范化因子

$$Z_t=\sum_{i=1}^N D_t(i)\alpha_t^{1-e_i}$$

最后是结合策略，采用的是对加权的弱学习器取权重中位数对应的弱学习器作为强学习器的方法，最终的强回归器为

$$\ln \frac{1}{\alpha_t},t=1,2,3,\dots,T$$

的中位数值序号 $t^$ 对应的学习器 $h_{t^}$

1. 【Mohri-机器学习基础】第2章: PAC学习框架-zhihu
2. PAC（probably approximately correct） 学习架构介绍-csdn
3. Boosting (Machine Learning)-wiki)
4. CIS 520: Machine Learning Spring 2018: Lecture 9 Boosting

---

Machine Learning

2022-03-19