统计学习方法 五到九章笔记

第五章 决策树

5.1 决策树模型与学习

决策树代表着一组if-else规则，互斥且完备。决策树的内部节点表示一个特征或者属性，叶节点表示一个类，也就是最终分类的确定是在叶结点上做的。 决策树要做的是与训练数据矛盾最小，同时具有良好泛化能力。

5.2 特征选择

特征选择指的是用哪个特征来划分空间，有的特征做出来和随机分类是差不多的，这样的特征没有意义。可以用信息增益用来衡量这件事情。

先对熵进行定义，记住熵括号里面的写法： 给定X是有限个取值范围的离散随机变量，有， 熵可以记作 然而熵只依赖于X的分布而和X的取值没有关系，所以也可以记作。这个的写法见到了也要会辨认。 特别地，定义这里的。 在定义了熵之后，定义条件熵，意义为在X给定的条件下Y的条件概率分布的熵对X的数学期望： 这里的右边是给定X之后的条件分布，对这个分布求熵。

有了这些对熵的定义，考察信息增益：

经验增益等价于互信息，也就是经验熵减去条件熵。直观地，经验熵表明原有的分类不确定度，而条件熵是给定了条件A（特征A）之后的不确定度，那么信息增益越大对应的特征A说明用这个特征来分类是越好的。

求信息增益的算法如下：

其中(1)里面的指的是各个类别的标签，指的是总样本数；(2)里面，指的是选定的特征的各个取值，只在当前选定的特征的某一个取值上的那些样本计算熵。用这个算法遍历所有的特征可以找到最大的信息增益。例题由于篇幅过大，不在此给出，可以看课本P75。

然而只看信息增益会有一些bias，信息增益会偏向于选择取值比较多的特征。为什么？设想一个比较极限的情况，一共五个样本，如果有一个特征的取值范围有五种，那么每一种取值都能对应一种标签，这个时候，导致信息增益会很大。不过这里好像并不是一个非常好的解释，有空的话可以看看[c4.5为什么使用信息增益比来选择特征？ - 多姆杨的回答 - 知乎 https://www.zhihu.com/question/22928442/answer/787244316]。

为了解决这一点，提出了信息增益比：

不过好像信息增益和信息增益比各有千秋，并没有一劳永逸的解决办法，

5.3 决策树的生成

在说了这么多基础知识之后终于要到怎么构建决策树了。

ID3算法

ID3算法是自根到叶地选择最大信息增益直到阈值的构建过程，只有树的生成，容易过拟合。

在(3)中，计算各特征对D的信息增益改为信息增益比，就变成了C4.5算法。

5.4 决策树的剪枝

剪枝为了抑制决策树的过拟合。 先引入决策树里的损失函数： 其中的alpha是个超参数，C(T)表示模型对训练数据的预测误差，可以从里面看出来，因为如果比如说叶结点上并不能很好地分类，以二分类为例最后的标签50%是正类，这个值就很大。其中的K就是所有的类别，表示决策树的叶节点数。第二项用来表达模型的复杂度。 剪枝就是在确定了之后选择损失函数最小的子树。这里损失函数的极小化等价于正则化的极大似然估计。

在得到树之后，给定，可以通过剪枝算法获得修剪后的树。 步骤为：

1. 计算每个结点的经验熵
2. 递归地从树的叶节点向上回缩，如果子树的损失函数值更小那就回缩
3. 重复2直到不能回缩

5.5 CART算法

CART算法事实上更为实用？ 不论如何，CART是和ID3和C4.5平行的算法。CART算法是把生成和剪枝都包括了，而且CART的树是二分的；CART既有回归树也有生成树。

CART回归树

课本对这块介绍有点少，看了很久才知道在说什么，这里尽量把记号都表述清楚。 现在给定一堆数据，回想上面的决策树，是把空间切割成若干块，每块对应一个分类。那么在回归里面，只要把这个分类的标签改成值，那就可以看成是连续的回归问题，只不过这个回归的取值可能离散了一点（当然，切割极细就可以让这个回归连续，不管如何都是一个回归）。 因此，回归树可以表示成一个函数（就是一块区域）： 当划分确定之后，可以使用平方误差表示训练误差。而且这里还有一个特性，就是一个区域里面落下的所有输入的取值都是一样的，这个取值会取当前区域所有样本的标签均值，这个值用表示，也就是

最重要的就是如何切割空间。课本说这里使用的是启发式方法，在所有的样本特征里面，比如说特征一共有D维，在里面挑选一个维度j，以及挑选j维上的切分点s（回想上面决策树的切割平面的模型），s会把整个空间一分为二，得到两个区域：但是怎么样的维度j和切分点s是最好的？我们想要的就是切出来之后的各个\hat{c}m和标签做平方误差是最小的。化成数学形式，也就是求解：\mathop{argmin}\limits{j,s}[\mathop{min}\limits_{c_1}\sum\limits_{x_i \in R_1(j,s)}(y_i-c_1)^2+\mathop{min}\limits_{c_2}\sum\limits_{x_i \in R_2(j,s)}(y_i-c_2)^2]这里其实应该是，不是课本里的，不过表达清楚就好了。这个式子虚空设出来一个，当作是输出。但其实我认为这里的表达太别扭了，而且这里对求可以取个导数，直接把结论套进去，可能更加的清楚：\mathop{argmin}\limits_{j,s}[\sum\limits_{x_i \in R_1(j,s)}(y_i-\bar{y}1)^2+\sum\limits{x_i \in R_2(j,s)}(y_i-\bar{y}_2)^2]

因此就有了最小二乘回归树算法（就是刚刚说的，给个名字）：

CART分类树

CART分类树就不用这么大费周章的去找这个j特征和s划分点了，有更加好用的手段，叫做基尼指数：

然而这里也有比较混乱的记号。 样本集合记为D，也可以写成: 注意这里的括号里面写的是D。 还有，对于D里给定的特征A，比如说A可能取1和其他值，就会划分和，而不是所有的可能取值。然后可以给出： 课本直接写了，可能会引起误导。

对于基尼指数，课本还有一个图来说明这个基尼指数和分类误差率的关系：

而且从基尼指数的定义可以看出，基尼指数越小说明这个特征选的越好。

定义了基尼指数之后，就可以引出CART的生成算法了：

CART决策树剪枝

CART决策树的剪枝仍然需要损失函数，也就是上面定义过的： 这里的是对训练数据的预测误差（如基尼指数）。这里的控制了树的规模，所以CART剪枝策略围绕着这一点进行剪枝：

这里(3)的自下而上指的是从叶到根的方向，而且剪枝发生在非叶节点。

第六章 logistic回归与最大熵模型

6.1 logistic回归模型

课本介绍这块有点莫名其妙的，引入了一堆莫名其妙的定义，又跳到了最大熵模型。

定义logistic分布的概率分布函数和概率密度函数： 画个图：

然后定义了二项logistic回归模型，虽然名字叫回归，但是是个分类的模型： 这里可以扩充，也就是，在这个条件下有：

logistic模型的学习可以用极大似然估计来学参数。对于上面的二项logistic回归，令： 似然函数： 对数似然函数： 把求出来的代入概率的两条式子就是学到的logistic回归模型。

然后把二项logistic回归拓展到多维，如果Y的取值集合是，那么： 其中。

6.2 最大熵模型

最大熵模型对于给定的输入X，以条件概率输出Y。应该记得，最大熵模型关心的永远是。所以，为了获得真正的，可以从样本里面估计和，用商来表示。加上~是为了说明这是经验分布，也就是计算的时候使用。 这里还建模了一个特征函数f，满足： 与满足某一事实 在有了样本集合之后，为了验证学习的效果好不好，在有样本的时候的估计方法这里采用期望。抓住我们已经有的条件：(1) (2) (3)，根据这里的恒等关系对不同的分布关于求期望，有：

如果模型能够学到信息，就会满足：

对于不同约束条件下的这些，定义最大熵模型：

其中6.13式是对条件熵的展开，也就是：

那么求解最大熵模型可以写成：

求解这样的问题，使用拉格朗日函数法解，先引入拉格朗日函数系数，转换为对偶问题。课本P99有一些相关的推导，这里略过，直接看例题：

对对偶函数极大化等价于最大熵模型的极大似然估计。这一点证明在篇幅上不好给出，见课本P102。

6.3 模型学习的最优化算法

感觉6.3节都是工具性质的，非常难形成方法论的东西，我认为看一下就好了，这种东西完全记不住。 到这里为止都还没介绍最大熵模型的具体写法，下面给出： 最大熵模型是 其中， 这个东西由6.2节里面求解拉格朗日函数法得来。 对数似然函数可以算得： 希望通过极大似然估计算出。

这里有一大段推导，在课本P104，读懂这些东西还是交给上帝吧。 最优化方法给出了这个最优参数的求解方法：

拟牛顿法在课本P107，懒得贴上来了，这是人能看懂的东西吗(╯▔皿▔)╯

第七章 支持向量机

7.1 线性可分支持向量机与硬间隔最大化

线性可分支持向量机和感知机类似，都是拟合一个的超平面，但是这里的解是唯一的，回想感知机，只需要正确分类就好了，解有无穷个，这里利用间隔最大化来求解，解是唯一的。

为了界定离更远的那些点的分类，有着更高的确信度这一事实，定义函数间隔：

如果只使用函数间隔，比如w和b都变为原来2倍，平面没有变化而函数间隔增大了，这可能不太好（为什么？）。对加规范化约束，即限制，这个时候函数间隔叫几何间隔，几何间隔就是几何上的那个距离（带个正负号）：

SVM在做的就是找到正确划分数据集，并让几何间隔最大的分离超平面。这里的间隔最大化叫做硬间隔最大化。间隔最大化希望以充分大的确信度对所有点分类，对最难分类的点也要有足够大的间距。 也就是，对于几何间隔，我们希望求这个问题的解： 对于下面的不等号，移项后换元得到： 观察这里，不管取什么值（），都可以同时在不等式左边乘一个系数抵消这样的变化，而不影响最终我们求解这个东西。为了方便，取，以及为了方便，把max转成min，还要取个平方，也就是最后的样子：

这个“最好”的超平面是存在且唯一的。证明见课本P117。

线性可分的时候，离分离超平面最近的点叫做支持向量。从公式上看，支持向量满足：（这条所在的直线叫做间隔边界，要和分离超平面区分开）。而且由于支持向量机这个最优解的性质，总会有至少一个正例和至少一个负例满足是支持向量这样的关系。支持向量以外的点不会影响分离超平面的样子。同时这个性质会让和中间出现两段空隙，这段空隙没有样本，且宽是一定的：

原来的这个求解问题的样子可以化成对偶形式，对偶问题更易求解且可以推广至非线性分类问题（加入核技巧）。一顿推导之后（见课本P120），得到：

例题：

注意这里的维度，这里取了和，是因为。 从这里也能观察到，只有对应的那些向量是有用的，那些向量就是支持向量。

7.2 线性支持向量机与软间隔最大化

线性可分支持向量机对于线性不可分的数据无能为力，但是大部分数据都是线性不可分的。因此需要让硬间隔转化为软间隔。在原来线性可分的时候，支持向量满足，而那些不好的点（特异点）比这个条件还要坏，达到了，因此为了把这些点也包进来，引入松弛变量，以及要限制这个松弛变量的大小，因此最后问题变成：

然后又是一顿推导（课本P127），得到这个对偶问题的解法：

同样地，这里的支持向量也是对应的那些样本。但是相比之下会更加复杂：

这里还提出一种等价形式：

证明见课本P131。 这里提出了一个合页损失函数，也就是，和0-1loss的关系为：

合页损失函数在正确分类的时候（的时候）仍然可能会产生一小段损失，它要求这个正确分类要有足够高的确信度，也就是，才会让损失=0，有着更高要求。0-1损失是感知机里面使用的，而合页损失函数是SVM里面使用的。

7.3 非线性支持向量机与核函数

核函数能让原本特征可以通过一个超曲面分离的样本，转换为特征空间中可以用超平面分离的样子。核函数定义如下：

核技巧中，关心而不显式地定义。其中这个空间和并不唯一。 引入核函数之后，上面的对偶问题式子就可以变成： 以及把原来计算的式子换成带有的运算，在这一条件下，SVM变成：

对于给定的函数K(x, z)，可以通过这个定义得出，虽然感觉一般不会用到：

证明在课本P136，非常地有数学意味。 核函数常用有这几种：

• 多项式核函数：
• 高斯核函数：
• 字符串核函数，和前面的不同，建立在离散数据上。课本有一大堆繁琐的定义，这里直接给出例子进行理解：

这里的计算了s和t中所有长度=n的子串（这里的子串未必连续）组成的特征向量的余弦相似度。

如前所述，引入核函数之后的问题可以写成：

7.4 序列最小最优化算法

这一节考虑SVM的具体实现。全都是数学推导过程，具体参见课本这一节，方法如下：

第八章 提升方法

8.1 AdaBoost

• 弱可学习：一个概念如果能用多项式的学习算法学习，正确率比随机猜测略好，那么就是弱可学习的；
• 强可学习：一个概念如果能用多项式的学习算法学习，正确率很高，那么就是强可学习的。

然而这两个概念是等价的。一般地，我们期望对很容易得到的弱分类器进行组合，构成一个强分类器，adaboost就是这样一种方法。 adaboost（先看下方说明）:

说明：

1. 最开始初始化的权值是平均的。
2. 在给定的权值下，不断地学习各个，并且之后更新权值。式(8.1)事实上是，也就是误分类的数目总和乘以权值。
3. 看，当的时候，，也就可以看出来分类误差率越小的基分类器在最后的权值越大。
4. 对于式(8.4)，有一个更加人性化的写法： 在这个写法下可以看出来，误分类的样本会导致权值更大。这里也能看出adaboost的特点，不改变数据本身，而不断改变训练数据权值的分布。
5. 最后这里是基于各个阶段（时间）得到的进行线性组合输出的，这里的之和并不=1；而在给定的m下之和=1。

adaboost的例子见课本P159。

8.2 adaboost算法的训练误差分析

adaboost对最后的分类器有一个训练误差上界：这里，也就是最后的模型，f是最后线性组合的各个，而在式(8.5)给出。先证不等号，，而在预测错误的时候，那么预测错误的时候，，不等号得证；证右边等号：（因为初始权重平均）根据式(8.4)，变形得到：继续我们的等式：这说明了，当在选择合适的时候，可以控制，让这个训练误差下降最快。在二分类下，adaboost有个定理可以给出更加好用的上界：

由此有个推论：对于的下界，如果，有 这说明了adaboost的训练误差是指数速率下降的。

8.3 adaboost算法的解释

看到adaboost的式子，是一个形如（其中是参数，是系数）的式子，这样的模型叫做加法模型，里面优化的问题是：。而前向分布算法希望把每次都要看M个这么多的模型简化到一个，也就是： 因此有了前向分步算法：

有了这个理论，有一个定理：adaboost算法是前向分步加法算法的特例，其中是基本分类器组成的加法模型，loss是指数函数，即。

证明如下：（一大堆证明，很好看懂，但是篇幅比较大）这里事实上更严谨的应该用数学归纳法，不过意思到位了就可以。前m-1轮迭代得到了，第m轮同理，有，那么怎么找想要的和？有这个式子：可以整理为：

其中

然后还有权值更新，在知道了\bar{w}{mi} = \exp (-y_if{m-1}(x_i))和f_{m}(x) = f_{m-1}(x)+\alpha_{m}G_{m}(x)，可以知道：\bar{w}{m+1, i} = \bar{w}{mi} \exp (-y_i \alpha_m G_m(x))

8.4 提升树

提升树被认为是统计学习中性能最好的方法之一。提升树可以写成是多个决策树的加法模型：使用前向分步算法，第m步的模型是：，其中当前模型是，使用经验风险最小化来确定下一颗树的参数：

回归问题的提升树的算法如下：

基函数选为树桩，也就是基本分类器和。例子见课本P168。

对提升树，当损失函数是平方损失或者指数损失，优化比较简单，而损失函数比较复杂的时候，使用梯度提升算法：

不一样的就是这里的残差使用了梯度，而原来的提升树使用的是直接作差。

课后题总结： ||学习策略|算法| |-|-|-| |支持向量机|软间隔最大化、最小化由合页损失函数和正则化项组成的目标函数|凸二次规划、SMO算法（序列最小最优化算法）| |adaboost|极小化通过加法模型组成的指数损失函数|学习加法模型的前向分步算法| |Logistic回归|极大似然估计法|改进的迭代尺度法、梯度下降法、牛顿法或拟牛顿法|

第九章 EM算法及其推广

9.1 EM算法的引入

一般地，对于观测变量，给定数据可以直接用极大似然估计或者贝叶斯估计来估计参数，然而有隐变量的时候，极大似然估计就是EM算法。 EM算法的三硬币模型在课本P176，是个例题。

EM算法迭代在干什么，推导在课本P179，有点长。 把这个事情转化成图形，

其中是的下界，在给定初始化的时候，要找B函数的极大化，也就是Q的极大化。因为L的下界是B，B的增加也让L增加。在这个过程，L的极大化就是极大似然估计，但是并不保证是最优解。 EM算法可以用来做无监督学习。

9.2 EM算法的收敛性

这里一大堆证明在P181，不太容易看懂，EM算法关于对数似然函数序列和参数估计序列的收敛是相互分开的，并没有蕴含关系。EM算法只能保证收敛到对数似然函数序列的稳定点而非极大值点。

9.3 EM算法在高斯混合模型学习中的应用

高斯混合模型就是一堆高斯分布的线性组合。

这里还有一段推导，看不懂。

9.4 EM算法的推广

EM算法可以解释为F函数的极大-极大算法。有推广GEM算法。这里太奇怪了，完全看不懂，直接看课本P187吧。