0 绪论 —— 西瓜书 | Ziuch の Blog

type

status

date

slug

summary

📝 主旨内容

教材及读法

机器学习

https://cs.nju.edu.cn/zhouzh/zhouzh.files/publication/MLbook2016.htm

课程定位

科学：是什么，为什么

技术：怎么做

工程：做得多快好省

应用

以科学和技术为主

机器学习

💡

利用经验改善系统自身性能

另一本经典教材的作者Mitchell给出了一个形式化的定义，假设：

P：计算机程序在某任务类T上的性能。

T：计算机程序希望实现的任务类。

E：表示经验，即历史的数据集。

若该计算机程序通过利用经验E在任务T上获得了性能P的改善，则称该程序对E进行了学习。

典型的机器学习过程

计算学习理论(PAC)

💡

以很高概率得到很好的模型

这是一个机器学习中的概率论公式，它描述了算法的泛化性能。让我来逐步解释它的含义：

这个公式可以这样理解：

是模型的预测输出

是真实值

表示预测值与真实值之间的误差的绝对值

(epsilon) 是误差的上限阈值

(delta) 是一个很小的概率值

整体含义是：预测值与真实值之间的误差小于或等于 的概率至少为 。

用更通俗的话说：

有的概率，模型的预测误差不会超过

比如，如果，，那么就意味着有95%的概率，预测误差不会超过0.1

这个公式在机器学习中经常用于：

评估模型的可靠性

提供模型性能的概率保证

在学习理论中证明算法的收敛性

这也是PAC（Probably Approximately Correct，概率近似正确）学习理论中的一个重要概念。

为什么不能追求每次都是以100%概率完全预测正确？

性质：知识不能够精确地给出答案(机器在90度左右容易发生故障)

理论：NP问题，在多项式时间内判断是否是最优解。P问题，在多项式时间内给出最优解。机器学习问题一般是NP以外的问题，如果假设成立，那么P问题得到解决了。P=NP？

基本术语

💡

机器学习的基本假设：独立同分布

假设空间

属性类别内部的"+1"（即n1+1, n2+1, n3+1）:

这是因为对于每个属性（色泽、根茎、敲声），除了已有的取值外，还需要考虑"不关心"或"任意值"的情况

比如色泽有"青绿"和"乌黑"两种取值(n1=2)，加上"不关心"的情况就是2+1=3种可能

这个"不关心"的选项很重要，因为它允许假设在某些属性上不做具体要求

最后的"+1":

这代表了一个特殊的假设：空假设或"拒绝一切"的假设

它表示无论输入是什么，都返回"否"的情况

这个假设在机器学习中是必要的，因为有时候所有已知的正例可能都是噪声或错误数据

举个例子：如果我们要判断"好瓜"，可能会有这样的规则：

"色泽=青绿且根茎=蜷缩且敲声=浊响"

"色泽=任意且根茎=硬挺且敲声=清脆"

"拒绝一切"（最后的+1对应的情况）

这种设计使得假设空间更完整，能够覆盖更多可能的决策规则。

中间的假设：(色泽=*; 根茎=蜷缩; 敲声=浊响)

这里"*"表示"任意值"或"不关心"

也就是说，这个假设只关心"根茎是否蜷缩"和"敲声是否浊响"，而不关心西瓜的色泽

它可以泛化出两个更具体的假设：

左边：(色泽=*; 根茎=蜷缩; 敲声=*)

这个假设进一步放宽了条件，只关心"根茎是否蜷缩"

右边：(色泽=*; 根茎=*; 敲声=浊响)

这个假设也放宽了条件，只关心"敲声是否浊响"

这种结构展示了假设之间的包含关系，上面的假设比下面的假设更一般化（更宽松）。可以理解为：

中间的假设是一个比较具体的规则

向上分别放宽了其中的一个条件，形成了两个更一般的规则

这些假设都与训练集保持一致，但具有不同程度的具体性/一般性

归纳偏好

💡

奥卡姆剃刀原则：若有多个假设与观察一致，则选最简单的那个(泛化性可能会更好，当然需要根据问题本身来定，判断是否简单这一问题也并不简单)

NFL定理

💡

NFL(No Free Lunch Theorem)定理：当我们在所有可能的问题上平均来看，没有任何一个算法可以在所有问题上都表现最好。

这个定理的实际意义是：

在机器学习和优化领域，不存在一个通用的"最佳算法"

算法的性能总是依赖于具体的问题

要解决特定问题，我们需要根据问题的特点来选择或设计合适的算法

这就像是在提醒我们："天下没有免费的午餐"——想要在某类问题上获得更好的表现，就必然要在其他类型的问题上付出代价。

🤗 总结归纳

易错题

给定包含两个西瓜样例的西瓜数据集,

1.色泽：青绿；根蒂：蜷缩；好瓜：是

2.色泽：乌黑；根蒂：稍蜷；好瓜：否

请结合"假设空间"相关概念回答，计算得版本空间大小为____

空间类型	计算公式	具体计算过程	结果
假设空间	(n1+1) × (n2+1) × (n3+1) + 1	(2+1) × (2+1) + 1 = 10	10
版本空间	(色泽可能取值数 × 根蒂可能取值数) - 无效组合	(2 × 2) - 1 = 3	3

解释二者的区别:

假设空间的计算:

n1表示色泽的可能取值数(青绿,乌黑),所以n1=2

n2表示根蒂的可能取值数(蜷缩,稍蜷),所以n2=2

加1是考虑了每个属性的"任意"情况

最后额外加1是考虑了"空集"的情况

这个计算包含了所有可能的假设组合,不考虑其是否满足训练样例

版本空间的计算:

只考虑能够正确分类训练样例的假设

对于每个属性,可以是具体值或"?"

需要排除(?,?)这种无法正确分类训练集的情况(因为已经存在了不是好瓜的情况)

结果包含(青绿,蜷缩)、(青绿,?)、(?,蜷缩)这三种假设

主要区别:

假设空间包含了所有可能的假设,不论其是否合理

版本空间则是假设空间的子集,只包含与训练样例相一致的假设

习题

1.1 表 1.1 中若只包含编号为 1 和 4 的两个样例, 试给出相应的版本空间.

假设空间

版本空间(与训练样例一致)

1.2

1.3 若数据包含噪声, 则假设空间中有可能不存在与所有训练样本都一致的假设. 在此情形下, 试设计一种归纳偏好用于假设选择.

最简单的设计就是：训练样本一致特征越多越好（一致性比例越高越好）为归纳偏好。

另外，考虑归纳偏好应尽量与问题相匹配，这里可使归纳偏好与噪声分布相匹配。

基于错误容忍的归纳偏好: 设定阈值，在误差不超过给定阈值的情况下拟合数据

基于概率的归纳偏好: 将噪声建模为随机变量，采用最大似然估计的思想

1.4

我们对所有可能的“真函数”（或任务） f 一视同仁(“均匀先验”)；

当对所有 f 取平均时，任何算法都无法在整体平均上比其他算法更优。

1.5 试述机器学习能在互联网搜索的哪些环节起什么作用

📝 主旨内容

教材及读法

课程定位

机器学习

典型的机器学习过程

计算学习理论(PAC)

基本术语

假设空间

归纳偏好

NFL定理

🤗 总结归纳

易错题

习题

📎 参考文章