现在收集到西瓜的数据
编号 | 色泽 | 根茎 | 敲声 |
---|---|---|---|
1 | 青绿 | 蜷缩 | 浊响 |
2 | 乌黑 | 稍蜷 | 沉闷 |
3 | 青绿 | 硬挺 | 清脆 |
假设空间与版本空间:
EG:现有房价数据如下表,要求根据学校数量预测房价:
[ 表quad1-2quad房价数据 ]
年份 | 学校数量 | 房价 |
---|---|---|
2020 | 1所 | 1万/平方米 |
2021 | 2所 | 4万/平方米 |
科学推理两大手段:
归纳的广义与狭义之分:
一个简单的概念学习示例:布尔概念学习
表(quad1-3quad)西瓜数据集
编号 | 色泽 | 根茎 | 敲声 | 好瓜 |
---|---|---|---|---|
1 | 青绿 | 蜷缩 | 浊响 | 是 |
2 | 乌黑 | 蜷缩 | 浊响 | 是 |
3 | 青绿 | 硬挺 | 清脆 | 否 |
4 | 乌黑 | 稍蜷 | 沉闷 | 否 |
色泽有青绿、乌黑、浅白3种取值,根蒂有蜷缩、稍蜷、硬挺3种取值,敲声有浊响、清脆、沉闷3种取值。
那么好瓜的布尔表达式:好瓜 (色泽=?)&& (根茎=?)&& (敲声=?)
如何找到正确的布尔表达式?
如果直接用第一条数据去填写,我们发现,该模型将会在其余样本上失败。
我们可以将学习的过程看作一个在假设空间上搜索的过程,搜索目标是找到与训练集匹配的假设,不匹配的删去。那么,每种属性取值为(这里以色泽为例):青绿、乌黑、浅白、任何情况都行。那么情况为((3+1)*(3+1)*(3+1)=64)种。此外还有一种极端情况:好瓜这个概念根本不存在,可以用空来表示该假设,因此假设空间规模为(64+1=65),有六十五种假设。
假设空间图形:
如何在假设空间选择:
版本空间:但是在现实生活中,我们发现在训练集筛选假设空间完毕后,可能得到多个假设与训练集一致,也就是存在一个符合训练集的训练集合,我们称之为假设空间。
上述表对应的版本空间为:
色泽=*,根蒂=蜷缩,敲声=*
色泽=*,根蒂=*,敲声=浊响
色泽=*,根蒂=蜷缩,敲声=浊响
上述得到的西瓜问题的版本空间给我们带来一个问题:我们需要的只是一个假设用于输出结果,而不是多个假设,否则我们的模型在面临相同的新数据时,有可能产生不同的输出。
如何解决版本空间的问题:为算法在学习过程中设置某种类型的偏好,如喜欢尽可能特殊情况的算法模型,那它就会选择好瓜 (色泽=*)&& (根茎=蜷缩)&& (敲声=清脆)
版本空间的几何表示:每一个训练样本是图中的一个点,而找到一个与训练集一致的模型,就是要找到一个穿过所有的点的曲线。
我们发现:有多条曲线与有限样本训练集一致,此时就需要偏好来选择使用哪一条曲线。
奥卡姆剃刀理论:
那么另一个问题来了:基于不同选择偏好的产生的模型,究竟哪个更好?这里以奥卡姆剃刀原理为偏好原则进行讨论:
让我们看(a)图,可以看到A模型对于未训练的数据泛化能力缺失比B要优秀。但是图(b)呢,难道b的情况不会出现吗?事实上,这是完全有可能的。这也说明:对于一个算法A,若它在某些问题上表现比学习算法B好,那么一定会有一些问题,在哪里B比A要好。这就导出了NFL理论:没有免费的午餐。
NFL定理的数学证明:
我们记样本空间为M,假设空间为H。(为了方便,将二者视为离散的)
(P(h|X,L_a))是算法(L_a)在训练集X上产生假设h的概率。(可能产生多个假设)
(f):我们所希望得到的真实目标函数。(显然唯一)
那么(L_a)的训练集外误差,也就是在M-X外的样本的误差为:
[ ]
(遍历该算法在样本上可能取到的所有目标函数,遍历样本空间内、训练集外的所有样本,对每一个取到的样本,判断假设(h(x)=f(x))的取值,这里要乘上取得样本x的概率和产生假设h的概率,随后对结果进行累加即可。)
接下来我们以二分类问题为例进行正式求解:
二分类问题中,真实的目标函数可以是任意的(Xrightarrow{0,1})。例如现有训练集(X={x_1,x_2}),那么可能有的目标函数如下:
[ f_1(x_1)=0,f_1(x_2)=0\ f_2(x_1)=1,f_2(x_2)=0\ f_3(x_1)=0,f_3(x_2)=1\ f_4(x_1)=1,f_4(x_2)=1 ]
共有四个可能的目标函数,函数空间为({0,1}^{|X|}),可能的真实目标函数有(2^{|X|})个
我们假设所有可能的f是均匀分布的(具体问题上并非如此,通常我们认为可以高度拟合样本数据的函数才是目标函数),那么我们对所有可能的f按照均匀分布对误差求和,得到:
[ 公式quad(1-2) ]
公式(1-2)第二步到第三步:因为无论h(x)对任意样本x取什么值,都会有一半的f(x)取值与其相同。
由公式(1-2)可以证得:总误差与学习算法无关。
NFL定理得前提条件:
NFL的启示:
若考虑所有潜在的问题,则所有算法都一样好。但在实际生活中,我们需要针对具体的问题,选择在某些问题上表现良好的算法。
学习算法自身归纳偏好与问题是否相配,往往会起到决定性作用。
参与评论
手机查看
返回顶部