(这篇文章是本人学习机器学习课程CS685后的一些总结。如有任何错误，欢迎指出)
1. 基本概念定义
当我们利用机器学习构建模型时，我们获得训练集，然后利用算法从训练集中学习到模型，接着就可以用该模型进行各种预测。为什么这是可行的呢? 想要弄清楚为什么可行，我们定义一下东西:(这些用英语写的都是因为本人不知道怎么翻译最准确，干脆不翻译了)
Domain set: 指的是特征所有可取值的集合。一般来说是一个向量。
Label set: 指的是所有标签的集合。接下来我们讨论的二分类问题，即label set里面只有0,1两种情况。
训练样本 S: 即我们平时说的训练集。S = {(x1,y1),(x2,y2),......(xn,yn)}。Trainning sample是我们已知的一切信息，除此之外我们什么都不知道。并且假设所有的数据都是满足分布D，并且由标签函数f进行贴标签。即f(x)就是x的真实标签。
Learner output: 一个函数h, h: X -> Y。也就是最后要学习得到的一个预测器。
H: hypothesis class。即所有的可能的预测器组成的集合。
以上就是我们要定义的一些东西。所以机器学习要做的就是获得training sample，利用这些数据去学习从而从H空间里面去挑选出最好的预测器h。
2. Empirical risk minimization
现在假设我们从满足分布D的数据中取出了一定数量的训练样本，目标是要找到h:X->Y。因为不知道数据的分布D具体是怎么样的，所以无法获取到整体数据的真实误差。在这里能够利用的只有经验误差。因此定义经验误差概念如下:
其中m是训练样本的个数。由于无法获得真实误差，通过学习得到一个预测器h使得经验误差最小是合理的。因为训练样本是从所有的服从分布D样本集里挑出来的，所以大概率训练样本会反映出所有满足分布D的样本的一些特性。因此学习的目标变为从H中找到一个预测器h，从而使得()最小。也就是我们说的Empirical risk minimization。
3.Empirical risk minimization with inductive bias
Empirical risk minimization有一个很明显的问题就是会发生overfitting。因为能使()最小的预测器h属于H，因此是可以被学习得到的。而许多的这些预测器泛化能力很差，对于新取的样本很有可能无法正确预测。导致这种问题的原因是我们没有对hypothesis class H做任何的限制。
因此为了避免overfitting，我们需要人为的引入一些限制，使得学习时偏向于选择某一些类型的预测器。我们称这些限制为inductive bias。
比如我们进行线性回归算法的时候，我们已经假定了算法的形式是Y=wX+b。这样我们进行学习时不会得到其他类型的预测器h。这就是引入的归纳偏置。
Empirical risk minimization with inductive bias的定义如下，注意这里的H是引入了inductive bias的假说集:
4.ERMH分析
我们可以分析在ERMH学习规则的性能如何。我们定义，即能使经验误差最小化的预测器的集合。现在规定两个assumption：
1.The realizability assumption。简单的说就是在H中存在预测器，使得() = 0。
2.The i.i.d. assumption。我们说过训练样本是从满足分布D的数据集中拿出来的，那么训练集中的样本根据分布D独立且相同地分布。可以看出来当训练集越大，越能够反映出分布D以及函数f。
由于从H中找到使经验误差最小的预测器是很难的一件事，所以要做的是尽量去逼近。因此引入参数，如果 ，则认为h是一个成功的预测器。我们再定义以下两个集合:
失败的预测器:
不好的训练样本:
可以看到M集是由一些能使预测器h在训练样本S上无误差，但是泛化能力很差的样本。其中表示真实误差，也可以理解为测试误差。大概可以理解为：
由The realizability assumption可以知道存在预测器h，其() = 0。
而如果一个训练集S使我们的学习算法计算得到预测器，那么这个样本。这是因为挑选预测器h时是尽量挑选使经验误差最小的那个那个预测器。所以被挑选出来的预测器() = 0。
所以。 因此可以计算得到:(A是指学习算法，A: S -> h，通过样本计算得到预测器。)
即我们通过样本S学习到失败的预测器的概率小于S是不好的训练样本的概率。
其中(m为样本集的尺大小)。 因为() = 0，那么训练集中的每一个S都要能被预测器成功预测。由于，所以预测器能够正确预测的区域小于。我们一共取m个样本，所以。
我们可以看出如果m趋向于无穷大，即训练样本的大小趋向于无穷时，训练样本是不好的样本的概率为0，所以我们得到失败的预测器的概率也为0。这就是为什么我们希望训练集越大越好。
5. PAC学习
我们用符号代替公式 的有右半部分。因此表示我们容忍的误差，表示我们失败的概率。m表示训练集的大小m。通过计算可以得到。
这就表明只要训练集样本数大于m这个公式，我们就有的概率(Probably)学习到误差在(Approximately)之内的预测器。这就是我们说的PAC学习。
