过拟合和前剪枝在线视频

我们刚才来讨论一下 这种归纳偏置Inductive bias

这是我们第一次提到 bias这个词 偏置

但这个偏置是大家一定一定要小心的东西 就是要注意的

我们刚才提到过了 我们说在决策树学习里面

这个假设集合其实就是你所有实例集合的超集

所以其实所有可能的情况它都已经在这个假设空间里面了

所以呢 我们说在这个假设空间本身没有损失 没有限定

但是呢 我们再比如说刚才的ID3算法里面 对ID3算法来说

我们每次选的是信息增益最大的那个节点作为当前的最优节点

因此呢 在这个过程中 我们的preference 我们的选择

search的过程的偏好是有偏好的 我们不是做了一个完整的搜索

所以我们把这种偏好 把它叫做search bias 就搜索偏置

然后我们不把它当做 我们有时候在machine learning里面

我们把刚才假设空间的缩小

把它的偏置叫做language bias 或者假设空间的限制

事实上你会发现 我们现在只是简单的说一下

我们刚才说 我们之所以有这个原则 带来这样的偏置

是因为我们也follow了奥卡姆剃刀原则 就是希望越短的树越好

事实上你会发现 我们会提到无偏的学习是无用的

就事实上 对于所有的机器学习算法 你一定会有某种bias

要么是假设空间bias 要么是你的搜索空间的bias

就是你的preference bias 一定会有某一种bias

如果没有偏的这种 或者是两者 二者都有 然后无偏学习呢

基本上也就只有这种memory 就是查表 就是所有情况都见过

你去查表来去给一个已知的东西

而这种东西在预测新的东西上是没有用的

关于无偏学习是无用的这部分 如果特别有同学感兴趣

你可以看一下 那本《机器学习》的那本书上

有一小部分做了一些解释 但总的来说

我觉得大家主要了解一个问题就是 每一个算法

它一定在某一个程度上都会引入自己的假设和先验的知识

这个东西都是 它要么是hypothesis bias要么是preference bias 或者二者都有

好 那么Occam’s razor 我们在这个课的开始

已经提到过了一些如果特别感兴趣Occam’s razor的事情

建议大家可以看一下Domingos在99年发表的

这篇paper The role of Occam’s razor in knowledge discovery

就是可以对这个讨论的比较更多一些

好 那么接下来看起来我们的决策树已经最基本的已经学完了

你确实根据这个也已经可以构造决策树了 但是 不是很能实用

为什么呢 是因为决策树特别容易发生过拟合问题

所以我们要做剪枝 好 所以过拟合问题不是决策树问题独有的

是所有的机器学习算法在处理问题的时候都要考虑的问题

但是在决策树上体现的比较明显 比较容易出现这种情况

所以我们在现在一上来就跟大家介绍

而且这个问题一定一定要小心

因为它特别影响实际的效果和在真实情况下的应用

那么什么是over-fitting 什么是过拟合呢

我们看假设我们已经观察到这些样本点

你如果要去把它做一个拟合的话 你有这种办法去做拟合

你可以认为它是一条直线 但是在这个直线上面它每一个点

它有一点噪声的影响 你还可以认为

它是一个有点类似于这种正弦曲线的这样的样子

你甚至还可以认为它是这种形状 你后来会发现

如果是用这种形状来看的话 每一个点都完美的匹配了

所以没有噪声 就是没有误差 但另外的两个一定都有误差

但是我们大家一看这样画你就会觉得 这个看起来不太靠谱啊

这个呢它其实很有可能是over-fitting了 为什么呢

因为如果在这个情况下 有一个新的点的话在这的话

你会发现对新的没见过的样本点 它的误差错误率会非常的大

它的误差会非常大 因此呢 我们怎么说什么是over-fitting呢

通常我们会有两个算法来去比较你才会知道

我们如果是在训练样例上有一个假设空间

其中h和h’分别是两个假设 然后你会发现在训练样例上面

h的错误率是小于h’的 但是呢 在测试集上 在没见过的样例上

测试集上h的错误率要大于h’了 这个时候我们就会说

我们不能说这个时候就发生了过拟合 我们往年有时候会考试

考试的时候大家前面都答得挺好

然后说这个时候就表示发生了过拟合 不对

我们这个时候我们会说h发生了过拟合

就是哪一个发生了过拟合

这个时候我们通常会觉得h发生了过拟合

过拟合现象在Decision Tree里面特别容易出现 为什么呢

因为有一个极端的情况 就是如果你把每一个叶子节点

等于其中一个样例 你是可以找到长出这样的一棵树的

每个叶子节点就是一个样例

它一定training set的那个上面完美的分类 错误率为零

但是它的泛化能力就非常弱 来了一个新的话

你其实这个就变成了一个查表

来了一个新的时候你就不知道应该往哪走了 所以说呢

决策树这个是有人观察过的 做的实际实验结果

你会发现这个实线是在training set上面我的精度

精度越高越好 然后呢 这个是在test data上就会发现

这个横坐标是树的大小

你会发现你树越大就是你的树的节点越多 精度越来越好

但事实上会发现在test set上面

在新的样例上面过了一个点之后就效果会越来越差了

我们其实会说 在这一点之后的这些值

在这一点之后的所有的那些树 都是发生了过拟合的树

怎么去解决 这个怎么办很好玩 两类方法 很直观

第一类方法是说最好的是 我能不能长的时候

我们叫预剪枝就是我长 先树一直不停的往下长

长到一定程度我觉得会过拟合了我就停 这是第一类思路

第二类思路是说 是后剪枝 我先把树长成什么样就长成什么样

可能有一百个节点没事 长完了之后我再一点一点往下剪

退回来的剪 这两类思路都有人做 也都有它的解决办法

那么第一类思路 我到底什么时候应该停

什么时候我会判断说下一步它就有可能会过拟合了呢

也有不同的做法 第一种做法是我去看一看从这一步之后

我这个节点还剩多少个样例点了

如果说我的当前的这个样例点已经小于一个值了

已经数据点太少了 我就不要再继续往下分裂了

即使它没有很好的分开就可以停 这个基本思想就是说

你如果数据样例点太少的话 学习到的有可能是特殊情况

有可能是噪声 有可能是不可靠的

在我们机器学习的这个领域里面非常大的一个就是样本的大小

是一个特别特别重要的因素 我们有一句话叫归纳学习假设

这个我们会在下周的课上一上来就会说

是说要在足够大的训练样例上 你的这个效果如果足够好

足够大的训练样例集合 这个足够大很重要

我们这个会既在期中期间的第一次理论课上提到

又会在期末的样本复杂度的上面第二次理论课上再次提到

所以在现在 大家至少知道一个 树立这样一个概念

样本点太少得到的结论就很可能不可靠

所以比如说如果你的这个已经少于5%的训练样例了

那就不要再继续长了 它很有可能会over-fitting

那么还有什么办法呢 还有

还有就是我们不是用Information Gain来计算吗

你可以说我的Information Gain如果已经小了

或者说已经持续的小于一个阈值了 那就不要再长了

也就说我再继续长下 继续做下去呢

我的这个信息的增益没有太大变化 有很微小的变化

那就可以停了 这个也是一种办法

好 那么 这个的好处是说 你其实还是使用了所有的训练样例

但是缺点是这个阈值怎么给呢 还是得训练出来或者是凭经验

拍脑袋想出来或者给一个什么值

所以这仍然是一个有点困难的问题 因此预处理

就像刚才我们说的预剪枝 刚才说如果这个数据量太少

少于多少呢 少于5% 那少于6%行不行 少于3%行不行

或者我就少于一百个点行不行 不知道呀 我只能说不知道

所以说对于这种预处理的方法你会发现有很多经验值可以用

其实很多真实的情况下可以用

因为你不用再继续长下去你就少了很多计算的开销

所以它比较简单 所以真实情况下很多人是会这么用的

但是你要知道这个里面会有很多经验值在里面 你的阈值要小心

可能换了一些问题或者数据更多的时候

阈值就要换一换再做一些training了

第二类方法后剪枝 后剪枝其实有好几种方法

就是我们说先长好了 长好之后我一步一步去看

我应该怎么剪让这个树变得更好一点 第一类方法其实是很棒的

这类方法是说 我来去计算它的

基于统计的效果来去看我们在如果剪掉了之后 我的置信度

就是考虑到置信度和置信区间的话

我有多大的置信度会觉得这个树应该剪掉

所以它是一个基于统计分析的

这个呢 对现在大家来说稍微复杂一点点

我们会在第一次理论的中期的课上会讲什么是置信度

什么是置信区间 这样的统计假设检验的时候 会再回到这个

把它作为一个例子来看这样的假设检验能做什么用

所以现在给大家留一个小小的悬念说 我们可以这样做

那还可以怎么做呢 就是我们可以这样

把训练数据集切分出一个小的集合来把它作为验证集

validation set 这个验证集呢 你其实是知道答案的

但你假装不知道 就跟模考一样

所以你去训练你的decision tree的时候 只用那些纯粹的训练集

不要用validation验证集上的结果 然后训练出树了之后

用validation set的数的结果做模拟测试来做剪枝

来去判断剪掉之后是不是效果更好 这个意思大家应该很明白对吧

其实就相当于你做一次模拟测试

来看一看应该剪到什么样这个树是更好的

那么还有 其实这个 我们总的来说呢

事实上剪枝它符合了这样的原理 就是最小描述长度

这个又是一个概念 大家不用特别了解 后面我们还会再提到

大家会看到 在机器学习的学习课程里面

我们往往会反复强调某一个概念 一开始你可能听说过

后来你了解一点点 再后来再多了解一点

等你上完课你就对这个概念了解的非常深入了 最小描述长度

它的意思是说 我其实并不是说错误率最低越好

并不是错率最低是最好的

而是说我应该最小化的是被误分类的那个数

就是我的错误分类的东西 以及树的大小

这两个因素加到一起越小越好

就树太复杂了错误率低也不一定好 树太简单错误率很高也不行

你可能要找到的是一个适中的大小的树 不复杂也不简单

并且错误率还是可以接受 它们俩加到一起损失是最小的

那到底怎么做我们后面会再稍微提到一点

但在我们整个s概论课上不会给大家一个清晰的一个公式

说怎么去计算这个