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

第五章 决策树

习题参见[https://datawhalechina.github.io/statistical-learning-method-solutions-manual]

5.1 决策树模型与学习

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

5.2 特征选择

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

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

这里的右边是给定X之后的条件分布,对这个分布求熵。

有了这些对熵的定义,考察信息增益:
image.png
经验增益等价于互信息,也就是经验熵减去条件熵。直观地,经验熵表明原有的分类不确定度,而条件熵是给定了条件A(特征A)之后的不确定度,那么信息增益越大对应的特征A说明用这个特征来分类是越好的。

求信息增益的算法如下:

image.png

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

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

为了解决这一点,提出了信息增益比:
image.png
不过好像信息增益和信息增益比各有千秋,并没有一劳永逸的解决办法,

5.3 决策树的生成

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

ID3算法

image.png
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]
$$

因此就有了最小二乘回归树算法(就是刚刚说的,给个名字):

image.png

CART分类树

CART分类树就不用这么大费周章的去找这个j特征和s划分点了,有更加好用的手段,叫做基尼指数:
image.png
然而这里也有比较混乱的记号。
样本集合记为D,也可以写成:

注意这里的括号里面写的是D。
还有,对于D里给定的特征A,比如说A可能取1和其他值,就会划分,而不是所有的可能取值。然后可以给出:

课本直接写了,可能会引起误导。

对于基尼指数,课本还有一个图来说明这个基尼指数和分类误差率的关系:
image.png
而且从基尼指数的定义可以看出,基尼指数越小说明这个特征选的越好。

定义了基尼指数之后,就可以引出CART的生成算法了:
image.png

CART决策树剪枝

CART决策树的剪枝仍然需要损失函数,也就是上面定义过的:

这里的是对训练数据的预测误差(如基尼指数)。这里的控制了树的规模,所以CART剪枝策略围绕着这一点进行剪枝:
image.png

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

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

6.1 logistic回归模型

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

定义logistic分布的概率分布函数和概率密度函数:


画个图:
image.png

然后定义了二项logistic回归模型,虽然名字叫回归,但是是个分类的模型:


这里可以扩充,也就是,在这个条件下有:

logistic模型的学习可以用极大似然估计来学参数。对于上面的二项logistic回归,令:

似然函数:

对数似然函数:

把求出来的代入概率的两条式子就是学到的logistic回归模型。

然后把二项logistic回归拓展到多维,如果Y的取值集合是,那么:


其中

6.2 最大熵模型

最大熵模型对于给定的输入X,以条件概率输出Y。应该记得,最大熵模型关心的永远是。所以,为了获得真正的,可以从样本里面估计,用商来表示。加上~是为了说明这是经验分布,也就是计算的时候使用
这里还建模了一个特征函数f,满足:

在有了样本集合之后,为了验证学习的效果好不好,在有样本的时候的估计方法这里采用期望。抓住我们已经有的条件:(1) (2) (3),根据这里的恒等关系对不同的分布关于求期望,有:

如果模型能够学到信息,就会满足:

对于不同约束条件下的这些,定义最大熵模型:
image.png

其中6.13式是对条件熵的展开,也就是:

那么求解最大熵模型可以写成:
image.png

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

image.png
image.png

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

6.3 模型学习的最优化算法

感觉6.3节都是工具性质的,非常难形成方法论的东西,我认为看一下就好了,这种东西完全记不住。
到这里为止都还没介绍最大熵模型的具体写法,下面给出:
最大熵模型是

其中,

这个东西由6.2节里面求解拉格朗日函数法得来。
对数似然函数可以算得:

希望通过极大似然估计算出

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

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

第七章 支持向量机

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

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

为了界定离更远的那些点的分类,有着更高的确信度这一事实,定义函数间隔:image.png
如果只使用函数间隔,比如w和b都变为原来2倍,平面没有变化而函数间隔增大了,这可能不太好(为什么?)。对加规范化约束,即限制,这个时候函数间隔叫几何间隔,几何间隔就是几何上的那个距离(带个正负号):
image.png

SVM在做的就是找到正确划分数据集,并让几何间隔最大的分离超平面。这里的间隔最大化叫做硬间隔最大化。间隔最大化希望以充分大的确信度对所有点分类,对最难分类的点也要有足够大的间距。
也就是,对于几何间隔,我们希望求这个问题的解:

对于下面的不等号,移项后换元得到:

观察这里,不管取什么值(),都可以同时在不等式左边乘一个系数抵消这样的变化,而不影响最终我们求解这个东西。为了方便,取,以及为了方便,把max转成min,还要取个平方,也就是最后的样子:
image.png
这个“最好”的超平面是存在且唯一的。证明见课本P117。

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

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

例题:
image.png
注意这里的维度,这里取了,是因为
从这里也能观察到,只有对应的那些向量是有用的,那些向量就是支持向量。

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

线性可分支持向量机对于线性不可分的数据无能为力,但是大部分数据都是线性不可分的。因此需要让硬间隔转化为软间隔。在原来线性可分的时候,支持向量满足,而那些不好的点(特异点)比这个条件还要坏,达到了,因此为了把这些点也包进来,引入松弛变量,以及要限制这个松弛变量的大小,因此最后问题变成:
image.png
然后又是一顿推导(课本P127),得到这个对偶问题的解法:
image.png
同样地,这里的支持向量也是对应的那些样本。但是相比之下会更加复杂:
image.png

这里还提出一种等价形式:
image.png
证明见课本P131。
这里提出了一个合页损失函数,也就是,和0-1loss的关系为:
image.png
合页损失函数在正确分类的时候(的时候)仍然可能会产生一小段损失,它要求这个正确分类要有足够高的确信度,也就是,才会让损失=0,有着更高要求。0-1损失是感知机里面使用的,而合页损失函数是SVM里面使用的。

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

核函数能让原本特征可以通过一个超曲面分离的样本,转换为特征空间中可以用超平面分离的样子。核函数定义如下:
image.png
核技巧中,关心而不显式地定义。其中这个空间并不唯一。
引入核函数之后,上面的对偶问题式子就可以变成:

以及把原来计算的式子换成带有的运算,在这一条件下,SVM变成:

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

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

  • 多项式核函数:
  • 高斯核函数:
  • 字符串核函数,和前面的不同,建立在离散数据上。课本有一大堆繁琐的定义,这里直接给出例子进行理解:
    image.png
    这里的计算了s和t中所有长度=n的子串(这里的子串未必连续)组成的特征向量的余弦相似度。

如前所述,引入核函数之后的问题可以写成:
image.png

7.4 序列最小最优化算法

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

第八章 提升方法

8.1 AdaBoost

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

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

说明:

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