摘要：归纳偏好

参考：

（1）《机器学习》周志华著，清华大学出版社

（2）归纳偏置_百度百科 (baidu.com)

（3）没有免费午餐定理_百度百科 (baidu.com)

4.归纳偏好

问题引入：版本空间中的每一个假设都代表了一种与训练集一致模型，但他们面临新样本时产生的输出却不一定相同，这并不符合我们的预期。我们想要的模型，是一个输入数据后得到唯一输出的一个“函数”，否则学得的模型有时告诉我们结果是，有时告诉我们结果是，这样的学习结果将毫无意义，因此我们必须从版本空间中选出一个假设来作为我们最后解决问题的模型，这时，学习算法本身的“偏好”就会起到关键作用。

4.1定义

周志华老师的机器学习中对“归纳偏好”有如下定义：

机器学习算法在学习过程中对某种类型假设的偏好，称为“归纳偏好”（inductive bias），或简称为“偏好”。

百度百科对“归纳偏置”有如下定义：

当学习器去预测其未遇到过的输入的结果时，会做一些假设（Mitchell, 1980）。而学习算法中归纳偏置则是这些假设的集合。

任何一个有效的额机器学习算法必有其归纳偏好，否则它将被假设空间中看似在训练集上“等效”的假设所迷惑，而无法产生确定的学习结果。

“归纳偏好”在一些文章里也被叫做“归纳偏置”。

4.2常用的归纳偏好假设

最大条件独立性（conditional independence）：如果假说能转成贝叶斯模型架构，则试着使用最大化条件独立性。这是用于朴素贝叶斯分类器（Naive Bayes classifier）的偏置。

最小交叉验证误差：当试图在假说中做选择时，挑选那个具有最低交叉验证误差的假说，虽然交叉验证看起来可能无关偏置，但天下没有免费的午餐理论显示交叉验证已是偏置的。

最大边界：当要在两个类别间画一道分界线时，试图去最大化边界的宽度。这是用于支持向量机的偏置,它假设不同的类别是由宽界线来区分。

最小描述长度（Minimum description length）：当构成一个假设时，试图去最小化其假设的描述长度。假设越简单，越可能为真的。例如奥卡姆剃刀。

最少特征数（Minimum features）：除非有充分的证据显示一个特征是有效用的，否则它应当被删除。这是特征选择（feature selection）算法背后所使用的假设。

最近邻居：假设在特征空间（feature space）中一小区域内大部分的样本是同属一类。给一个未知类别的样本，猜测它与它最紧接的大部分邻居是同属一类。这是用于最近邻居法的偏置。这个假设是相近的样本应倾向同属于一类别。

4.3举例：奥卡姆剃刀（Occam's razor）

“奥卡姆剃刀”是一种常用的、自然科学研究中最基本的原则。即“若有多个假设与观察一致，则选择最简单的那个”。

例如我们现在处理一个回归问题，训练集为图一中的实心圆点，曲线A和B分别代表了版本空间中的两个模型，假设我们认为“越平滑”代表着“越简单”，那么对于该例，我们会自然的偏好“平滑”的曲线A。

图1：回归问题的版本空间（摘自周志华《机器学习》）

4.4没有免费午餐定理（No Free Lunch Theorem）

4.4.1定理内容

1）对所有可能的的目标函数求平均，得到的所有学习算法的“非训练集误差”的期望值相同；

2）对任意固定的训练集，对所有的目标函数求平均，得到的所有学习算法的“非训练集误差”的期望值也相同；

3）对所有的先验知识求平均，得到的所有学习算法的“非训练集误差”的期望值也相同；

4）对任意固定的训练集，对所有的先验知识求平均，得到的所有学习算法的的“非训练集误差”的期望值也相同。

NFL定理表明没有一个学习算法可以在任何领域总是产生最准确的学习器。不管采用何种学习算法，至少存在一个目标函数，能够使得随机猜测算法是更好的算法。

简单概括来说，对于一个算法，如果在某些问题上它的性能比算法要好，那么必然存在另外一些问题，在这些问题上算法比算法的性能好。也就是说算法的好坏是相对的而不是绝对的。

4.4.2定理结论

该定理的结论是，由于对所有可能函数的相互补偿，最优化算法的性能是等价的。该定理暗指，没有其它任何算法能够比搜索空间的线性列举或者纯随机搜索算法更优。

关于定理的证明周志华老师在书中很详细，南瓜书也有详细记载，可以参考南瓜书PumpkinBook (datawhalechina.github.io)

4.4.3定理的前提

1.所有“问题”出现的机会相同、或所有问题同等重要

2.假设f均匀分布

然而实际情况并不一定能满足上列条件，而且大多数情况是满足不了这个条件的，所以

NFL最重要的寓意，是让我们清楚的认识到，脱离具体问题，空泛地谈论“什么学习算法更好”毫无意义