统计学习方法 五到九章笔记
第五章 决策树
习题参见[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的特点,不改变数据本身,而不断改变训练数据权值的分布。 - 最后这里是基于各个阶段(时间)得到的
进行线性组合输出的,这里的