统计学习方法 五到九章笔记
第五章 决策树
习题参见[https://datawhalechina.github.io/statistical-learning-method-solutions-manual]
5.1 决策树模型与学习
决策树代表着一组if-else规则,互斥且完备。决策树的内部节点表示一个特征或者属性,叶节点表示一个类,也就是最终分类的确定是在叶结点上做的。
决策树要做的是与训练数据矛盾最小,同时具有良好泛化能力。
5.2 特征选择
特征选择指的是用哪个特征来划分空间,有的特征做出来和随机分类是差不多的,这样的特征没有意义。可以用信息增益用来衡量这件事情。
先对熵进行定义,记住熵括号里面的写法:
给定X是有限个取值范围的离散随机变量,有
熵可以记作
然而熵只依赖于X的分布而和X的取值没有关系,所以
特别地,定义这里的
在定义了熵之后,定义条件熵
这里的右边
有了这些对熵的定义,考察信息增益:
经验增益
求信息增益的算法如下:
其中(1)里面的
然而只看信息增益会有一些bias,信息增益会偏向于选择取值比较多的特征。为什么?设想一个比较极限的情况,一共五个样本,如果有一个特征的取值范围有五种,那么每一种取值都能对应一种标签,这个时候
https://www.zhihu.com/question/22928442/answer/787244316]。
为了解决这一点,提出了信息增益比:
不过好像信息增益和信息增益比各有千秋,并没有一劳永逸的解决办法,
5.3 决策树的生成
在说了这么多基础知识之后终于要到怎么构建决策树了。
ID3算法
ID3算法是自根到叶地选择最大信息增益直到阈值的构建过程,只有树的生成,容易过拟合。
在(3)中,计算各特征对D的信息增益改为信息增益比,就变成了C4.5算法。
5.4 决策树的剪枝
剪枝为了抑制决策树的过拟合。
先引入决策树里的损失函数:
其中的alpha是个超参数,C(T)表示模型对训练数据的预测误差,可以从
剪枝就是在确定了
在得到树之后,给定
步骤为:
- 计算每个结点的经验熵
- 递归地从树的叶节点向上回缩,如果子树的损失函数值更小那就回缩
- 重复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}[\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决策树的剪枝仍然需要损失函数,也就是上面定义过的:
这里的
这里(3)的自下而上指的是从叶到根的方向,而且剪枝发生在非叶节点。
第六章 logistic回归与最大熵模型
6.1 logistic回归模型
课本介绍这块有点莫名其妙的,引入了一堆莫名其妙的定义,又跳到了最大熵模型。
定义logistic分布的概率分布函数和概率密度函数:
画个图:
然后定义了二项logistic回归模型,虽然名字叫回归,但是是个分类的模型:
这里可以扩充,也就是
logistic模型的学习可以用极大似然估计来学参数。对于上面的二项logistic回归,令:
似然函数:
对数似然函数:
把求出来的
然后把二项logistic回归拓展到多维,如果Y的取值集合是
其中
6.2 最大熵模型
最大熵模型对于给定的输入X,以条件概率
这里还建模了一个特征函数f,满足:
在有了样本集合之后,为了验证学习
如果模型能够学到信息,就会满足:
对于不同约束条件下的这些
其中6.13式是对条件熵的展开,也就是:
那么求解最大熵模型可以写成:
求解这样的问题,使用拉格朗日函数法解,先引入拉格朗日函数系数,转换为对偶问题。课本P99有一些相关的推导,这里略过,直接看例题:
对对偶函数极大化等价于最大熵模型的极大似然估计。这一点证明在篇幅上不好给出,见课本P102。
6.3 模型学习的最优化算法
感觉6.3节都是工具性质的,非常难形成方法论的东西,我认为看一下就好了,这种东西完全记不住。
到这里为止都还没介绍最大熵模型的具体写法,下面给出:
最大熵模型是
其中,
这个东西由6.2节里面求解拉格朗日函数法得来。
对数似然函数可以算得:
希望通过极大似然估计算出
这里有一大段推导,在课本P104,读懂这些东西还是交给上帝吧。
最优化方法给出了这个最优参数的求解方法:
拟牛顿法在课本P107,懒得贴上来了,这是人能看懂的东西吗(╯▔皿▔)╯
第七章 支持向量机
7.1 线性可分支持向量机与硬间隔最大化
线性可分支持向量机和感知机类似,都是拟合一个
为了界定离
如果只使用函数间隔,比如w和b都变为原来2倍,平面没有变化而函数间隔增大了,这可能不太好(为什么?)。对
SVM在做的就是找到正确划分数据集,并让几何间隔最大的分离超平面。这里的间隔最大化叫做硬间隔最大化。间隔最大化希望以充分大的确信度对所有点分类,对最难分类的点也要有足够大的间距。
也就是,对于几何间隔
对于下面的不等号,移项后换元得到:
观察这里,不管
这个“最好”的超平面是存在且唯一的。证明见课本P117。
线性可分的时候,离分离超平面最近的点叫做支持向量。从公式上看,支持向量满足:
原来的这个求解问题的样子可以化成对偶形式,对偶问题更易求解且可以推广至非线性分类问题(加入核技巧)。一顿推导之后(见课本P120),得到:
例题:
注意这里的维度,这里取了
从这里也能观察到,只有
7.2 线性支持向量机与软间隔最大化
线性可分支持向量机对于线性不可分的数据无能为力,但是大部分数据都是线性不可分的。因此需要让硬间隔转化为软间隔。在原来线性可分的时候,支持向量满足
然后又是一顿推导(课本P127),得到这个对偶问题的解法:
同样地,这里的支持向量也是
这里还提出一种等价形式:
证明见课本P131。
这里提出了一个合页损失函数,也就是
合页损失函数在正确分类的时候(
7.3 非线性支持向量机与核函数
核函数能让原本特征可以通过一个超曲面分离的样本,转换为特征空间中可以用超平面分离的样子。核函数定义如下:
核技巧中,关心
引入核函数之后,上面的对偶问题式子就可以变成:
以及把原来计算
对于给定的函数K(x, z),可以通过这个定义得出,虽然感觉一般不会用到:
证明在课本P136,非常地有数学意味。
核函数常用有这几种:
- 多项式核函数:
- 高斯核函数:
- 字符串核函数,和前面的不同,建立在离散数据上。课本有一大堆繁琐的定义,这里直接给出例子进行理解:
这里的计算了s和t中所有长度=n的子串(这里的子串未必连续)组成的特征向量的余弦相似度。
如前所述,引入核函数之后的问题可以写成:
7.4 序列最小最优化算法
这一节考虑SVM的具体实现。全都是数学推导过程,具体参见课本这一节,方法如下:
第八章 提升方法
8.1 AdaBoost
- 弱可学习:一个概念如果能用多项式的学习算法学习,正确率比随机猜测略好,那么就是弱可学习的;
- 强可学习:一个概念如果能用多项式的学习算法学习,正确率很高,那么就是强可学习的。
然而这两个概念是等价的。一般地,我们期望对很容易得到的弱分类器进行组合,构成一个强分类器,adaboost就是这样一种方法。
adaboost(先看下方说明):
说明:
- 最开始初始化的权值是平均的。
- 在给定的权值下,不断地学习各个
,并且之后更新权值。式(8.1)事实上是 ,也就是误分类的数目总和乘以权值。 - 看
,当 的时候, ,也就可以看出来分类误差率 越小的基分类器在最后的权值越大。 - 对于式(8.4),有一个更加人性化的写法:
在这个写法下可以看出来,误分类的样本会导致权值更大。这里也能看出adaboost的特点,不改变数据本身,而不断改变训练数据权值的分布。 - 最后这里是基于各个阶段(时间)得到的
进行线性组合输出的,这里的 之和并不=1;而 在给定的m下之和=1。
adaboost的例子见课本P159。
8.2 adaboost算法的训练误差分析
adaboost对最后的分类器有一个训练误差上界:
这里
先证不等号,
证右边等号:
根据式(8.4),变形得到:
继续我们的等式:
这说明了,当
在二分类下,adaboost有个定理可以给出更加好用的上界:
$$\prod\limits_{m=1}^M Z_m = \prod\limits_{m=1}^M 2\sqrt{e_m(1 - e_m)} = \prod\limits_{m=1}^M \sqrt{1 - 4\gamma
m^2} \le \exp(-2\sum\limits{m=1}^M \gamma_m^2)
= \sum\limits_{y_1 = G_m(x_i)} w_{mi}e^{-\alpha_m} + \sum\limits_{y_1 \neq G_m(x_i)} w_{mi}e^{\alpha_m} \
= (1 - e_m)e^{-\alpha_m} + e_m e^{\alpha_m}\ (e_m的意义) \ =…$$
由此有个推论:对于
这说明了adaboost的训练误差是指数速率下降的。
8.3 adaboost算法的解释
看到adaboost的式子,是一个形如
因此有了前向分步算法:
有了这个理论,有一个定理:adaboost算法是前向分步加法算法的特例,其中是基本分类器组成的加法模型,loss是指数函数,即
证明如下:(一大堆证明,很好看懂,但是篇幅比较大)
这里事实上更严谨的应该用数学归纳法,不过意思到位了就可以。
前m-1轮迭代得到了
有这个式子:
可以整理为:
$$
(\alpha_m, G_m(x)) = \mathop{argmin}\limits_{\alpha, G} \sum\limits_{i = 1}^N \bar{w}{mi}\exp(-y_i\alpha G(x_i))
$$
其中$\bar{w}{mi} = \exp (-y_if_{m-1}(x_i))
\sum\limits_{i = 1}^N \bar{w}{mi}\exp(-y_i\alpha G(x_i)) = \sum\limits{y_i = G_m(x_i)}\bar{w}{mi} e^{-\alpha} + \sum\limits{y_i \neq G_m(x_i)}\bar{w}{mi} e^{\alpha} \ = \sum\limits{y_i = G_m(x_i)}\bar{w}{mi} e^{-\alpha} + \sum\limits{i=1}^N \bar{w}{mi} e^{\alpha} I(y_i \neq G_m(x_i)) \
= \sum\limits{i=1}^N \bar{w}{mi} e^{-\alpha} (1 - I(y_i \neq G_m(x_i))) + \sum\limits{i=1}^N \bar{w}{mi} e^{\alpha} I(y_i \neq G_m(x_i)) \
= (e^\alpha - e^{-\alpha})\sum\limits{i=1}^N \bar{w}{mi}I(y_i \neq G_m(x_i)) + e^{-\alpha}\sum\limits{i=1}^N \bar{w}{mi}
就是adaboost里面求出来的误差率。
然后还有权值更新,在知道了$\bar{w}{mi} = \exp (-y_if{m-1}(x_i))
这个更新和adaboost的更新差规范化因子,是等价的。
8.4 提升树
提升树被认为是统计学习中性能最好的方法之一。
提升树可以写成是多个决策树的加法模型:
使用前向分步算法,第m步的模型是:
回归问题的提升树的算法如下:
基函数选为树桩,也就是基本分类器
对提升树,当损失函数是平方损失或者指数损失,优化比较简单,而损失函数比较复杂的时候,使用梯度提升算法:
不一样的就是这里的残差
课后题总结:
||学习策略|算法|
|-|-|-|
|支持向量机|软间隔最大化、最小化由合页损失函数和正则化项组成的目标函数|凸二次规划、SMO算法(序列最小最优化算法)|
|adaboost|极小化通过加法模型组成的指数损失函数|学习加法模型的前向分步算法|
|Logistic回归|极大似然估计法|改进的迭代尺度法、梯度下降法、牛顿法或拟牛顿法|
第九章 EM算法及其推广
9.1 EM算法的引入
一般地,对于观测变量,给定数据可以直接用极大似然估计或者贝叶斯估计来估计参数,然而有隐变量的时候,极大似然估计就是EM算法。
EM算法的三硬币模型在课本P176,是个例题。
EM算法迭代在干什么,推导在课本P179,有点长。
把这个事情转化成图形,
其中
EM算法可以用来做无监督学习。
9.2 EM算法的收敛性
这里一大堆证明在P181,不太容易看懂,EM算法关于对数似然函数序列和参数估计序列的收敛是相互分开的,并没有蕴含关系。EM算法只能保证收敛到对数似然函数序列的稳定点而非极大值点。
9.3 EM算法在高斯混合模型学习中的应用
高斯混合模型就是一堆高斯分布的线性组合。
这里还有一段推导,看不懂。
9.4 EM算法的推广
EM算法可以解释为F函数的极大-极大算法。有推广GEM算法。这里太奇怪了,完全看不懂,直接看课本P187吧。