归纳偏置

 

定义

  • 一个具体的学习算法,必须要产生一个模型,这时,学习算法本身的“偏好”就会起到关键的作用;
  • 任何一个有效的机器学习算法必有其归纳偏置,否则它将被假设空间中看似在训练集上“等效”的假设所迷惑,进而无法产生确定的学习结果;
  • 如果没有偏好,则该模型在每次同样的输入中,输出的结果并不一致,所以该学习没有意义。

以下图为例,在训练过程中需要找到一条穿过所有训练样本的曲线。而对于有限个样本组成的训练集,存在多条曲线与其一致,所以需要有偏好才能选择出一条合适的曲线。

通过上图,可以发现,平滑的曲线A更合适。但是,这不能说曲线A一定比曲线B合适,因为必定存在某种情况,曲线B会比曲线A好。

假设样本空间${\chi}$和假设空间$H$都是离散的。另$P(h X, \varsigma_{\alpha} )$代表算法$\varsigma_{\alpha} $基于训练数据$X$产生假设$h$的概率,再另$f$代表我们希望学习的真实目标函数。$\varsigma_{\alpha} $的训练集外误差,即$\varsigma_{\alpha} $在训练集值外的所有所有样本上的误差为:
\[E_{ote}(\varsigma_{\alpha} | X, f ) = \sum_{h}{\sum_{x∈{\chi}-X}{P(x) \parallel (h(x)≠f(x))P(h|X, \varsigma_{\alpha})}}\]

其中${\parallel}(·)$表示指示函数,若$·$为真值,则取1,否则取0.

在二分类问题中,真实目标函数可以是任何函数$\chi \mapsto {0, 1}$,所以函数空间为${ {0, 1} }^{|\chi|}$,对所有可能的$f$按照均匀分布对误差求和,有:

若$f$均匀分布,则有一半的$f$对$x$的预测与$h(x)$不一致。

可以发现,总误差与学习算法无关,也就是说,无论学习算法多聪明,多笨拙,它们的期望是相同的,这就是“天下没有免费的午餐”定力(No Free Lunch)。

NFl定力最重要的意义,就是使我们明白,脱离具体问题,空泛谈论“什么学习算法最好”是没有意义的,所以必须针对具体的学习问题。