1.3 归纳偏好

习题1.4 针对教材1.4节关于“归纳偏好”（inductive bias）的概念，回答以下问题：

1.试举例说明常见机器学习算法中使用了哪些归纳偏好.

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

解答

1.机器学习算法一般都有自身的归纳偏好.如教材第6章介绍的支持向量机方法假设好的分类器应最大化分类间隔（margin）；而深度学习中的代表性方法如卷积神经网络（Convolutional Neural Network，CNN）具有局部性（locality）和空间不变性（spatial invariance）的归纳偏好，循环神经网络具有时序性（sequentiality）和时间不变性（time invariance）等归纳偏好[5].

深度神经网络的相关介绍见教材5.6节.

最常用的一种归纳偏好莫过于线性模型（linear model）中对分类器w的约束.如在岭回归（ridge regression）、支持向量机中，优化目标中包含，即在最小化训练集误差的同时，寻找范数最小的分类器.范数在一定程度上描述了参数的平滑性，避免分类器的参数取值过大.例如，对于两个维数（dimensionality）为4的线性分类器，其各维数的参数取值如表1.7所示：

表1.7 两个四维线性分类器的参数取值

在支持向量机的推导中，一项来源于对间隔的最大化.

可以看出，第一个分类器的范数取值较小，各参数也较小，而第二个分类器的参数中存在一些较大的数值，不如第一个分类器平滑，在预测过程中可能造成预测结果出现较大的“抖动”.这一归纳偏好能够被反映在分类器的范数中.

2.可从以下两个方面考虑设置归纳偏好：

1）若假设i能够正确判断的训练样例占训练集全集的比率为ξi，则选取ξi最大的假设；

2）若存在多个假设i1，i2，…，其正确判断训练样例的比率相同，，则由“奥卡姆剃刀”（Occam's razor）原则，选择其中最简单的假设.

习题注释 本题考查对归纳偏好的理解.任何一个有效的机器学习算法必有其归纳偏好，否则它将被假设空间中看似在训练集上“等效”的假设所迷惑，而无法产生确定的学习结果.归纳偏好并没有对错之分，然而好的归纳偏好大多数时候直接决定了算法能否取得好的性能.在训练样本少的场景中归纳偏好的选择尤为重要，在本书11.4节中将进一步探讨这一问题.

习题1.5相关符号的定义请参考教材1.4节.

习题1.5 教材1.4节介绍了“没有免费的午餐”（No Free Lunch，NFL）定理，请回答以下问题：

1.请说明对NFL定理的理解.定理表明所有学习算法的期望性都能和随机猜测一样，那是否还有必要继续研究机器学习算法？

2.教材1.4节在论述NFL定理时，默认使用了“分类错误率”（classification error rate）作为性能度量来对分类器进行评估.若换用其他性能度量ℓ，则教材中式（1.1）将改为

试证明在此情况下NFL仍成立.

解答

1.首先回顾当使用“分类错误率”作为性能度量来评估分类器时NFL的证明方式.令X表示样本空间，X表示训练集，希望学习的真实目标函数为f.为了衡量泛化能力，需要计算模型针对非训练集的样本的预测能力.在当前算法产生的某个假设h下，如果h（x）≠f（x）则表示当前假设与真实目标不一致，计入误差：

其中P（x）表示训练集外数据的分布.例如，数据服从均匀分布，共有5个样本，其中有2个样本在当前假设下预测的结果与真实结果不一致，则误差为2/5=0.4.若使用式（1.2）计算，则有0.2×1+0.2×1+0.2×0+0.2×0+0.2×0=0.4，得到同样的结果.

因此，算法La在给定f情况下的“训练集外误差”可表示为

P（h|X，La）表示算法La基于训练集产生某个假设h的概率.NFL定理需要计算在所有可能的任务中“训练集外误差”的期望，假设f服从均匀分布，即计算

结合教材1.4节的推导，的计算关键在于计算在二分类问题（标记为0或1）中，函数空间为，即有个假设.若样本空间X=2，即有两个样本|x|1和x2，则该函数空间的表示如图1.3所示.对于每个样本有两种映射结果，若空间中有|X|个样本，则共有2|X|=4种映射情况.在f服从均匀分布的情况下，有P（f1）=P（f2）=P（f3）=P（f4）.假如当前的h对x1的预测为1，即h（x1）=1，则图1.3中只有f1和f2与h的预测相同，即只有一半的f与h相同，故P（f（x）=h（x））=1/2.

图1.3 函数空间表示示意图

依此类推，假设所有可能的f均匀分布，有一半的f对x的预测与h（x）不一致，故有

综上，可以得到

即NFL定理，算法在所有任务上的期望性能与算法本身无关！但是注意到，在进行上述推导时，有一个很重要的前提，即所有可能的目标函数f均匀分布.换句话来说，所有“问题”出现的机会相同，或所有问题同等重要.不同的机器学习方法都有它们各自的侧重.当样本有特征有缺失时，可以选用决策树（decision tree）；当需要快速高效并具有可解释性的简单模型时，可以选用线性模型.目前还有很多问题亟待大家去发现和解决，所以进行机器学习算法的研究是很有必要的.

2.在二分类问题下，需证明损失函数具有如下性质，即任意性能度量ℓ对正确分类和错误分类的得分应该为一个常数C，即

对于二分类问题来说，在不指定性能度量ℓ时仅有四种情况，假设ℓ（0，0）=ℓ1，ℓ（0，1）=ℓ2，ℓ（1，0）=ℓ3，ℓ（1，1）=ℓ4.其中ℓ1，ℓ2，ℓ3，ℓ4均为常数.则可得

对于每种情况，均考虑f（x）=3和f（x）=1两种情况.

在二分类的情况下，不考虑代价敏感（cost-sensitive）损失，则应有ℓ1+ℓ2=ℓ3+ℓ4，故式（1.7）中第二项为0.可得当前情况下ℓ（h（x），f（x））=C.结合这一性质，NFL定理的推导变为

因此算法期望性能在任意性能度量下与当前算法无关.

上一章目录下一章