1.4 归纳偏好
  通过学习得到的模型对应了假设空间中的一个假设. 会有多个与训练集一致的假设.如何选择.
  机器学习算法在学习过程中对某种类型假设的偏好, 称为 “归纳偏好”(inductive bias), 或简称为"偏好". e.g.,若算法喜欢 “特殊” 的模型, 则它会选择 $"好瓜"\leftrightarrow(色泽=*)\bigwedge(根蒂=蜷缩)\bigwedge(敲声=浊响)$;而若算法喜欢 “一般” 的模型. 并且由于某种原因更 “相信” 根蒂, 则它会选择 $"好瓜"\leftrightarrow(色泽=*)\bigwedge(根蒂=蜷缩)\bigwedge(敲声=*)$.
  任何一个有效的机器学习算法必有其归纳偏好, 否则它将被假设空间中看似在训练集上 “等效” 的假设所迷惑而无法产生确定的学习结果.
  归纳偏好的作用在下面这个学习图示中可能更直观.这里的每个训练样本是图中的一个点$(x,y)$, 要学得一个与训练集一致的模型, 相当于找到一条穿过所有训练样本点的曲线. 对有限个样本点组成的训练集, 存在很多条曲线与其一致. 我们的学习算法必须有某种偏好, 才能产出它认为 “正确” 的模型.



  归纳偏好可看作学习算法自身在一个可能很庞大的假设空间中对假设进行选择的启发式或 “价值观”. “奥卡姆剃刀”(Occam’s razor)是一种常用的、自然科学研究中最基本的原则, 即 “若有多个假设与观察一致, 则选择最简单的那个”.
  对于一个学习算法$\frak  L_a$, 若它在某些问题上比学习算法$\frak  L_b$好, 则必然存在另一些问题, 在那里$\frak  L_b$比$\frak  L_a$好.



证明: 假设样本空间 $X$ 和假设空间 $H$ 都是离散的. 令

$P(h\mid X,\frak  L_a)$ :算法$\frak  L_a$基于训练数据 $X$ 产生假设 $h$ 的概率;

$f$: 我们希望学习的真实目标函数;

$\frak  L_a$ 的 “训练集外误差” ,即 $\frak  L_a$ 在训练集之外的所有样本上的误差为

$E_{ote}(\frak  L_a\mid X,f)=\sum _h\sum_{x\in \chi-X} P(x)\Bbb I(h(x)\not=f(x))P(h\mid X,\frak L_a)$,

其中 $\Bbb I(\cdot)$ 是指示函数, 若 $\cdot$ 为真则取值1, 否则取值0.

  考虑二分类问题, 且真实目标函数可以是任何函数$X \mapsto \{0,1\}$, 函数空间为$\{0,1\}^{\left|X\right|}$. 对所有可能的 $f$ 按均匀分布对误差求和, 有

$\sum _fE_{ote}(\frak  L_a\mid X,f)=\sum_f \sum_h \sum_{x\in \chi-X} P(x)\Bbb I(h(x)\not=f(x))P(h\mid X,\frak L_a)$

$=\sum_{x\in \chi-X}P(x) \sum_hP(h\mid X,\frak L_a) \sum_f  \Bbb I(h(x)\not=f(x))$

$=\sum_{x\in \chi-X}P(x) \sum_hP(h\mid X,\frak L_a) \frac122^{\left|\chi\right|}$

$=\frac122^{\left|\chi\right|}\sum_{x\in \chi-X}P(x) \sum_hP(h\mid X,\frak L_a)$

$=2^{\left|\chi\right|-1}\sum_{x\in \chi-X}P(x)\cdot1.$
  最终结果显示出, 总误差与学习算法无关! 对于任意两个学习算法 $\frak  L_a$ 和 $\frak  L_b$, 我们都有

$\sum _fE_{ote}(\frak  L_a\mid X,f)=\sum _fE_{ote}(\frak  L_b\mid X,f)$ ,

也就是说, 所有学习算法的期望性能都相同. 这就是 “没有免费的午餐” 定理(No Free Lunch Theorem, 简称NFL定理).
  然而, NFL定理有一个重要前提: 所有 “问题” 出现的机会相同、或所有问题同等重要. 但实际情形并不是这样. 很多时候, 我们只关注自己正在试图解决的问题(例如某个具体应用任务), 希望为它找到一个解决方案, 至于这个解决方案在别的问题、甚至在相似的问题上是否为好方案, 我们并不关心.
  事实上, NFL定理的论述过程中假设了 $f$ 的均匀分布, 而实际情形并非如此.

e.g.,${假设1: 好瓜\leftrightarrow(色泽=*)\bigwedge(根蒂=蜷缩)\bigwedge(敲声=浊响)}$

和

${假设2: 好瓜\leftrightarrow(色泽=*)\bigwedge(根蒂=硬挺)\bigwedge(敲声=清脆)}$

从NFL定理可知, 这两个假设同样好. 然而, $"(根蒂=蜷缩);(敲声=浊响)"$的好瓜很常见, 而$"(根蒂=硬挺);(敲声=清脆)"$的好瓜罕见, 甚至不存在.
  所以, NFL定理是让我们清楚地认识到, 脱离具体问题, 空泛地谈论 “什么学习算法更好” 毫无意义. 要谈论算法的相对优劣, 必须要针对具体的学习问题.

1.为什么会产生归纳偏好？
   假设现在有三个与训练集一致的假设，但是与它们对应的模型在面临新的一个样本时，会产生不同的输出。这时明显是不合适的。这时我们需要对其得到的假设进行筛选，因此就产生了归纳偏好.
2.深入理解：
  实质上，其归纳偏好知识一种判断当一个训练集面对多种假设时的一种思想.
                          
  上表展示的是一个西瓜的数据集，首先要明确，这是一个二分类问题，我们的目的就是判断一个新的拿来的瓜究竟是不是好瓜，我们将判断好瓜的标准暂且就由三种属性进行判定（色泽，根蒂，敲声）.
   现在假设我们训练完成后，有多种对应好瓜的假设。
第一种标准(尽可能特殊)：
   好瓜<->(色泽=青绿）^(根蒂=蜷缩)^(敲声=浊响)
第二种标准（尽可能一般）:
   好瓜<->(色泽=*)^(根蒂=蜷缩)^(敲声=*)
机器学习对于上面的标准选择的思想就使用了归纳偏好，具体是偏好不同的属性比如在上述的两种标准中，独自偏爱色泽为青绿的这一属性.这就是归纳偏好.
另外需要补充的是在实际的应用中，对于不同的属性的偏好选择是应该是基于信赖可视为某种领域知识而产生的归纳偏好，而不是你想当然就视哪一个属性的属性值为你的归纳偏好.
3.更加直观的描述（周志华《机器学习》）
   假设在下图中，每个训练样本是图中的一个点（x,y）,要学得一个与训练一致的模型，相当于找到一条穿过所有的点的一条曲线,注意，下图中穿过这些样本点的曲线可以有很多种，这就相当于我们的上面所述训练的集合对应的不同的假设，而我们的归纳偏好，就是基于一种偏好选择一种适当的假设。比如：如果我们以最终的曲线要尽量的简洁为一个偏好，那么直观上我们肯定选择下面的曲线A，而不选择曲线B.

   

   

机器学习（1）归纳偏好和NFL
这是萌新小白第一次写博客，也是刚刚开始机器学习的系统学习。第一次的博客主要介绍的是归纳偏好和NFL定理。


归纳偏好

任何一个有效的机器学习算法都必然有其归纳偏好，否则其就会因为假设空间中在训练集上假设的“等效”而感到困惑无法产生确定的学习结果。譬如面对一个有很多西瓜的验证集，对于同样要素（样本特征）的西瓜算法会有时判定为“好瓜”，有时判定为“坏瓜”。这样子的学习结果显然是没有实际作用的。
譬如，训练集中的数据点为

{(0, 0), (1, 1), (-1, 1)}

那么在没有归纳偏好的前提下学习结果可以为

y = 1 - cos(π / 2 * x)

或者为

y = x ^ 2

等等，有无数的曲线可以拟合，也就是作为机器学习第得到的结论，并且这些结论在误差期望上都是相同的（下面的NFL即为证明）。在这种情况下，只有规定了归纳偏好为“平滑”或者其他，才能够得到更为精确的机器学习结果。
归纳偏好可以视为学习算法在自身一个很庞大的假设空间中对假设进行选择的启发式或“价值观”。“奥卡姆剃刀”的简单有效原理便是一种原则。事实上，归纳偏好对应了学习算法本身做出的关于“什么样的模型更好”的假设。具体问题中，归纳偏好是否和问题本身相匹配，大多数时候直接决定了算法能否取得好的性能。

NFL定理

NFL定理证明的是由于对所有可能函数的相互补偿，最优化算法的性能是等价的。该定理暗指，没有其它任何算法能够比搜索空间的线性列举或者纯随机搜索算法更优。该定理只是定义在有限的搜索空间，对无限搜索空间结论是否成立尚不清楚。
NFL定理的结论为：

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

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

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

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

NFL定理表明没有一个学习算法可以在任何领域总是产生最准确的学习器。不管采用何种学习算法，至少存在一个目标函数，能够使得随机猜测算法是更好的算法。
首先，假设一个算法为a，而随机胡猜的算法为b，为了简单起见，假设样本空间为 和假设空间为H都是离散的。令P(h|X,a)表示算法a基于训练数据X产生假设h的概率，再令f代表希望的真实目标函数。a的训练集外误差，即a在训练集之外的所有样本上的误差为

$E_{ote}（a|X,f）=\sum_h\sum_{x\isin\chi-X}P(x)Ⅱ(h(x)\neq f(x))P(h|X, a)$

其中，Ⅱ（.）是指示函数，若括号内为真则取值1，否则为0.

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

$\begin{aligned}
\sum_f E_{ote}(a, |X,f ) &=\sum_f\sum_h\sum_{x\isin\chi-X}P(x)Ⅱ(h(x)\neq f(x))P(h|X, a) \\
&=\sum_{x\isin\chi-X} P(x)\sum_hP(h|X, a)\sum_fⅡ(h(x)\neq f(x))\\
&=\sum_{x\isin\chi-X} P(x)\sum_hP(h|X, a)*2^{|\chi|-1}\\
&=2^{|\chi|-1}\sum_{x\isin\chi-X} P(x)\sum_hP(h|X, a)\\
&=2^{|\chi|-1}\sum_{x\isin\chi-X} P(x)
\end{aligned}$

其中最后一步是因为$\sum_hP(h|X, a) = 1$

上式结果证明了，当分布均匀时，也就是没有实际背景时，无论算法多好在没有实际背景情况下都不优于随机胡猜。

所以，NFL定理对于机器学习最重要的寓意，是让我们清晰地认识到，脱离具体问题，空泛地谈论“什么学习算法更好”是没有实际意义的。谈论算法的相对优劣，必须要针对具体的学习问题。大部分学习算法的自身的归纳偏好与问题相匹配时，对于算法性能往往会起到决定性作用。

归纳偏好（inductive bias）：机器学习算法在学习过程中对某种类型假设的偏好。

例如：算法喜欢尽可能特殊的模型，则会选择“好瓜<->(色泽=*)^(根蒂=蜷缩)^(敲声=浑浊)”，如果算法尽可能一般的模型，则会选择“好瓜<->(色泽=*)^(根蒂=蜷缩)^(敲声=*)”。

通俗来讲：即在样本空间中存在多种假设，算法选择某种模型假设的偏好。

奥卡姆剃刀：若有多个假设和观察一致，选择最简单的那个。（但有时奥卡姆剃刀也会有不适用，当无法判断哪个更简单时，需要其他机制来解决这个问题）

概括：从假设空间中剪枝，剩余样本空间，样本空间中有多种符合的类型，对某种类型（特殊的，一般的，，，）假设的偏好，就叫归纳偏好。