一些零碎的知识点

1、归纳与演绎

2、归纳学习：广义的归纳学习是指从样例中学习；狭义的归纳学习是指从样例数据中习得概念，因此也称概念学习。

3、布尔概念学习：也是一种归纳学习，即从所有训练数据的输入和布尔输出结果之间的关系中，推断出布尔函数的所有可能。（黑箱模型）

什么是假设空间

        假设空间就是从样本空间中归纳所有样本构成的假设集合。通过样本数据中每个特征的属性值个数，可以构造出假设空间的大小和规模。

        在归纳学习中，学习的过程可以看做在一个所有假设组成的空间进行探索的过程，找到所有可以将训练集中的数据正确判断的假设的集合。最终获得一个和训练值一直的假设的集合，即成为该数据集的版本空间。

归纳偏好

       根据训练集可以从假设空间中最终得到一个适合训练集的多个假设，但是当一个新的数据需要进行预测时，选择不同的假设进行预测得到的结果会是不一样的(此处获得的不同假设可以看做不同的模型)。那么归纳偏好则会决定，我们在版本空间中应该选择哪一个假设。

       归纳偏好可以认为学习算法自身在一个非常庞大的假设空间中对假设进行选择的启发式价值观。归纳偏好的最终结果，就是算法自身找到一个可以满足所有训练集的假设，并且对于训练集之外的数据，也可以做到较好的预测。

偏好选择原则

        需要有理论上的指导，来指导算法从庞大的假设空间之中找到最适合的偏好。   

奥卡姆剃刀原则

         奥卡姆剃刀定义

         在机器学习领域，奥卡姆剃刀原则就是在多个满足训练集的假设空间中，找到最简单的那一个，对于一些简单的场景，奥卡姆剃刀原则可以找到相应的假设，对于比较复杂的场景，则会面临另外一个问题：在多个假设之间，如何判定哪一个假设更简单。

NFL（No Free Lunch）定理

       可以通过训练集外的样本在不同假设上的误差，来决定两个假设之间的性能好坏，那么在同一个样本空间χ和一个假设空间H，P(h|X,ζa)代表算法ζa在样本空间X中，产生假设h的概率。令f(x)代表真实的目标函数，那么算法ζa在训练集外（χ-X）的误差的误差的期望值为：

算法ζa在训练集外（χ-X）的误差的误差的期望值

        其中，Ⅱ(h(x)≠f(x))为指示函数，当对样本x预测失败时，值为1。P(x)为遇到样本x的概率。以上为使用同一种假设造成的误差期望，对于假设空间中所有可能的假设，都有可能选中，概率为P(h|X,ζa)，那么对于所有的假设空间，误差的期望值为：

（1,1即为在所有假设上算法的误差期望）

      这里假设在整个函数空间中，所有可能的目标函数f是均匀分布的（即所有真实的问题是均匀出现的），对所有可能的f(x)，按照均匀分布对误差求和：

对于所有f进行误差求和

     推导得出：

中间结果

     对于

     由于f是均匀分布的，同一个数据可能满足f(x)也可能不满足。而且数据也是独立同分布的，因此h(x)≠f(x)的概率为1/2，在整个样本空间中的预测结果即为：

     所以，对于均匀分布对误差求和的结果：

容易得出：

误差的期望与算法本身无关

但是，得出这一结论的前提，是所有的样本数据遵从独立同分布原则，所有问题出现的概率相同。并且在实际中f(x)也是同等概率出现的。但是实际并不是这样，我们只关系我们所要解决的问题，只是为了解决明确的需求来获得最佳的方案

NFL定理只是让我们认识到：脱离具体问题来讨论算法的优劣，是没有意义的。学习算法的归纳偏好是否与需求匹配，是最重要的。