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

Posted on 2023-02-13

第五章决策树

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

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就是所有的类别，表示决策树的叶节点数。第二项用来表达模型的复杂度。
剪枝就是在确定了之后选择损失函数最小的子树。这里损失函数的极小化等价于正则化的极大似然估计。

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

计算每个结点的经验熵
递归地从树的叶节点向上回缩，如果子树的损失函数值更小那就回缩
重复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（先看下方说明）:

说明：

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

第五章 决策树