台湾大学林轩田机器学习基石课程学习笔记5 -- Training versus Testing

简介: 上节课,我们主要介绍了机器学习的可行性。

上节课,我们主要介绍了机器学习的可行性。首先,由NFL定理可知,机器学习貌似是不可行的。但是,随后引入了统计学知识,如果样本数据足够大,且hypothesis个数有限,那么机器学习一般就是可行的。本节课将讨论机器学习的核心问题,严格证明为什么机器可以学习。从上节课最后的问题出发,即当hypothesis的个数是无限多的时候,机器学习的可行性是否仍然成立?


一、Recap and Preview


我们先来看一下基于统计学的机器学习流程图:

image.png

该流程图中,训练样本D和最终测试h的样本都是来自同一个数据分布,这是机器能够学习的前提。另外,训练样本D应该足够大,且hypothesis set的个数是有限的,这样根据霍夫丁不等式,才不会出现Bad Data,保证Ein≈Eout,即有很好的泛化能力。同时,通过训练,得到使Ein最小的h,作为模型最终的矩g,g接近于目标函数。


这里,我们总结一下前四节课的主要内容:第一节课,我们介绍了机器学习的定义,目标是找出最好的矩g,使g≈f,保证Eout(g)≈0;第二节课,我们介绍了如何让Ein≈0,可以使用PLA、pocket等演算法来实现;第三节课,我们介绍了机器学习的分类,我们的训练样本是批量数据(batch),处理监督式(supervised)二元分类(binary classification)问题;第四节课,我们介绍了机器学习的可行性,通过统计学知识,把Ein(g)与Eout(g)联系起来,证明了在一些条件假设下,Ein(g)≈Eout(g)成立。

image.png

上节课介绍的机器学习可行的一个条件是hypothesis set的个数M是有限的,那M跟上面这两个核心问题有什么联系呢?

我们先来看一下,当M很小的时候,由上节课介绍的霍夫丁不等式,得到Ein(g)≈Eout(g),即能保证第一个核心问题成立。但M很小时,演算法A可以选择的hypothesis有限,不一定能找到使Ein(g)足够小的hypothesis,即不能保证第二个核心问题成立。当M很大的时候,同样由霍夫丁不等式,Ein(g)与Eout(g)的差距可能比较大,第一个核心问题可能不成立。而M很大,使的演算法A的可以选择的hypothesis就很多,很有可能找到一个hypothesis,使Ein(g)足够小,第二个核心问题可能成立。


image.png


二、Effective Number of Line


我们先看一下上节课推导的霍夫丁不等式:

image.png

当M=∞时,上面不等式右边值将会很大,似乎说明BAD events很大,Ein(g)与Eout(g)也并不接近。但是BAD events Bm级联的形式实际上是扩大了上界,union bound过大。这种做法假设各个hypothesis之间没有交集,这是最坏的情况,可是实际上往往不是如此,很多情况下,都是有交集的,也就是说M实际上没那么大,如下图所示:

image.png

也就是说union bound被估计过高了(over-estimating)。所以,我们的目的是找出不同BAD events之间的重叠部分,也就是将无数个hypothesis分成有限个类别。

如何将无数个hypothesis分成有限类呢?我们先来看这样一个例子,假如平面上用直线将点分开,也就跟PLA一样。如果平面上只有一个点x1,那么直线的种类有两种:一种将x1划为+1,一种将x1划为-1:

image.png

如果平面上有两个点x1、x2,那么直线的种类共4种:x1、x2都为+1,x1、x2都为-1,x1为+1且x2为-1,x1为-1且x2为+1:

image.png

image.png

image.png

也就是说,对于平面上三个点,不能保证所有的8个类别都能被一条直线划分。那如果是四个点x1、x2、x3、x4,我们发现,平面上找不到一条直线能将四个点组成的16个类别完全分开,最多只能分开其中的14类,即直线最多只有14种:image.pngimage.png

三、Effective Number of Hypotheses

image.pngimage.pngimage.png

image.png

再来看这个例子,假设在二维空间里,如果hypothesis是凸多边形或类圆构成的封闭曲线,如下图所示,左边是convex的,右边不是convex的。那么,它的成长函数是多少呢?

image.png


四、Break Point


上一小节,我们介绍了四种不同的成长函数,分别是:

image.pngimage.png

五、总结


本节课,我们更深入地探讨了机器学习的可行性。我们把机器学习拆分为两个核心问题:Ein(g)≈Eout(g)和Ein(g)≈0。对于第一个问题,我们探讨了M个hypothesis到底可以划分为多少种,也就是成长函数mH。并引入了break point的概念,给出了break point的计算方法。下节课,我们将详细论证对于2D perceptrons,它的成长函数与break point是否存在多项式的关系,如果是这样,那么机器学习就是可行的。



相关文章
|
4月前
|
机器学习/深度学习 Python
训练集、测试集与验证集:机器学习模型评估的基石
在机器学习中,数据集通常被划分为训练集、验证集和测试集,以评估模型性能并调整参数。训练集用于拟合模型,验证集用于调整超参数和防止过拟合,测试集则用于评估最终模型性能。本文详细介绍了这三个集合的作用,并通过代码示例展示了如何进行数据集的划分。合理的划分有助于提升模型的泛化能力。
|
8月前
|
机器学习/深度学习 数据采集 数据可视化
【机器学习】样本、特征、标签:构建智能模型的三大基石
【机器学习】样本、特征、标签:构建智能模型的三大基石
3312 0
|
机器学习/深度学习 算法 数据安全/隐私保护
精心整理 | 林轩田机器学习资源汇总
精心整理 | 林轩田机器学习资源汇总
198 0
精心整理 | 林轩田机器学习资源汇总
|
机器学习/深度学习 数据挖掘
干货|机器学习基石精选文章链接
下面这部分内容列出了机器学习基石的精选文章。
205 0
干货|机器学习基石精选文章链接
|
机器学习/深度学习
台湾大学林轩田机器学习基石课程学习笔记16(完结) -- Three Learning Principles
上节课我们讲了一个机器学习很重要的工具——Validation。
135 0
台湾大学林轩田机器学习基石课程学习笔记16(完结) -- Three Learning Principles
|
机器学习/深度学习 算法
台湾大学林轩田机器学习基石课程学习笔记15 -- Validation
上节课我们主要讲了为了避免overfitting,可以使用regularization方法来解决。
165 0
台湾大学林轩田机器学习基石课程学习笔记15 -- Validation
|
机器学习/深度学习 算法 数据挖掘
干货 | 林轩田机器学习「基石+技法」历史文章汇总
干货 | 林轩田机器学习「基石+技法」历史文章汇总
171 0
|
2月前
|
机器学习/深度学习 算法 数据挖掘
K-means聚类算法是机器学习中常用的一种聚类方法,通过将数据集划分为K个簇来简化数据结构
K-means聚类算法是机器学习中常用的一种聚类方法,通过将数据集划分为K个簇来简化数据结构。本文介绍了K-means算法的基本原理,包括初始化、数据点分配与簇中心更新等步骤,以及如何在Python中实现该算法,最后讨论了其优缺点及应用场景。
116 4
|
15天前
|
算法
PAI下面的gbdt、xgboost、ps-smart 算法如何优化?
设置gbdt 、xgboost等算法的样本和特征的采样率
39 2
|
2月前
|
机器学习/深度学习 算法 数据挖掘
C语言在机器学习中的应用及其重要性。C语言以其高效性、灵活性和可移植性,适合开发高性能的机器学习算法,尤其在底层算法实现、嵌入式系统和高性能计算中表现突出
本文探讨了C语言在机器学习中的应用及其重要性。C语言以其高效性、灵活性和可移植性,适合开发高性能的机器学习算法,尤其在底层算法实现、嵌入式系统和高性能计算中表现突出。文章还介绍了C语言在知名机器学习库中的作用,以及与Python等语言结合使用的案例,展望了其未来发展的挑战与机遇。
51 1