泛化理论整理
泛化理论的目的就是模型在未知的数据上能够表现的够好。它主要考虑的是模型在训练集样本的损失函数(ERM)达到的最小化的情况下，是否在更广阔的大众化的样本中是否能够达到损失函数最小化，通常是不一定的。
ERM模型empirical risk minimization
- 广泛数据分布(Population distribution)
- 特征Feature(x∈X⊂(R^d))：比如一张图片
- 标签Label(y∈Y⊂R)：比如猫狗分类
这里的x和y其实都是随机变量(有关随机变量的内容可以参考概率论整理 中的随机变量及其分布),(x,y)~P，它们服从于一种概率分布。这个P就是广泛数据分布，但是这个P具体是如何分布的，我们是不知道的。
- 训练数据集(Trainning Dataset)
由于广泛数据分布我们是不知道的，但是我们可以得到一组训练数据集S=({(x_i,y_i)}_{i=1}^n)，它是广泛数据分布的一个特例。
- 最小化的经验损失(empirical risk minimization)
这个其实就是训练损失函数
它表示服从训练数据集概率分布的损失函数。
算法A:x×y->θ，这个θ表示模型参数，输入的是数据x、y，输出的是模型参数θ
- 模型(y=f_θ(x))
训练好的模型就是找到最好的θ的过程。
- 推理(Evaluation)
广泛损失(Population risk)
这个D就是广泛数据分布，由于D未知，所以我们取代的另外一些测试数据集。
泛化差距(generalization gap)
它表示的广泛损失和训练损失之间的差距。等式右边是一种常用的写法。对其进行分解
它表示如果我们的训练优化做的比较好，并且训练损失的分布离广泛损失又比较近，那么就是一个比较好的广泛损失结果。
这里我们主要研究的就是泛化差距(Generalization Gap)，当存在标签噪声(label noise)的时候，广泛损失
是不可能到0的，比如我们推理出来的图片的概率是0.9是猫，0.1是狗。所以无论是Generalization Gap还是Optimization至少有一个不可能到0。
在一个参数量小于样本数的线性回归(Under-para linear reg)中，它的泛化差距是比较小的(~d/n,d是参数量，n是样本数)，但是训练损失是比较大的(~({n-d\over n}σ^2),(σ^2)为方差)，因为线性模型过于简单，无法完全拟合好数据。
在一个参数量大于样本数的线性回归(Over-para linear reg)中，泛化差距是比较大的(≥(σ^2))，训练损失是比较小的(=0)，因为参数量大，可以直接插值。
故而，泛化研究中会基于一个假设，
，即存在一个f(模型的前向运算，这里指线性模型，指数模型的不同分类)，使得广泛损失趋近于0。否则我们需要考虑超额损失(excess risk)，例如过拟合(begin overfitting)。
超额损失(excess risk)
我们已经知道了所有的f都不能使得广泛损失达到比较好的情况下，在得到的测试集最好的损失
跟最好的广泛损失
去做对比。对上式进行拆解
拆解出来的第一个量(橙色框中的内容)表示在某一种f模型(线性、多项、指数等不同类型的模型)里面损失能达到的最小能够有多小，这里就是我们在训练前需要挑选一种特定的模型才能去进行训练。第二个量(蓝色框中的内容)表示在某一种f模型跟所有种类的模型中最好的损失能够达到多小，它表示近似误差(Appproximation error)。这两个部分就是超额损失(excess risk)。我们继续将第一部分进行拆解
分解出的三个部分，第一部分就是泛化差距，其意义就是相同的模型，不同的数据集，
表示全样本数据集，
表示训练数据集。第二部分就是都是使用训练数据集，但是使用的不同的模型所得到的损失的差值，
表示使用的指定的一种模型，而
表示所有模型中最好的那个模型的损失，这个差值是小于等于0的，因为针对具体的一种模型训练完成所得到的结果是可以学到更多的东西的，它的损失更小；第三部分就是都是使用所有模型中最好的模型损失，它们使用的是不同的数据集，
表示使用的是训练数据集，
表示使用的是全样本数据集，它被称为专注(Concentration)。
没有免费的午餐
通用学习器：对任务没有任何先验信息，对任何任务都适用。
这里要研究的是是否存在一个算法A，对于m个样本的训练数据集，使得对任意的分布D，如果A能够接受到这个分布的m个样本，以一个很高的概率输出一个非常好的模型h，这个是非常困难的。
在上图中有A和B两个图，其中黑色的点是训练集中的数据，对我们是已知的。但是对于全样本数据的广泛分布，我们是未知的，对于A和B中灰色的点以及黑点是两种不同的分布，我们的模型有可能拟合出A的分布，也有可能拟合出B的分布。即不存在一个算法在只看到训练集的5个点之后，就能够拟合任意的分布。对于上图的A和B两种分布，我们的模型是不可能同时满足的。
没有免费的午餐定理(No-free-lunch Theorem)：作为一个二分类任务域X的算法A，从该域中取出m个样本训练数据集，并且m<(X\over 2)。存在着一个分布D(代表X的(0,1)标签)使得：
- 存在着一个模型f:X->{0,1}使得损失函数(L_D(f)=0)，即存在着一个好的预测模型。
- 对于训练样本的分布S，类比于全样本分布D，仅仅只有(1\over 7)的概率能使得广泛损失(L_D(A(S))≥{1\over 8})，即我们无法找到1中的好模型。
总结：对于任意的算法A，存在着一个广泛分布D，尽管存在着一个好的模型，但大概率，我们无法找到这个好的模型。
PAC(Probably Approximately Correct) Learning
PAC理论的前提是需要知道一些先验知识的。
- Probably(概率)：对于任意的分布只要满足先验。
- Approximately(近似)：抽取出来的训练集不是太差。
- Correct(正确)：就能够找到一个好的算法找到这个最好的模型
定义：一个假设函数集合H，如果存在着一个函数(m_H:(0,1)^2->N)以及一个满足任意的ɛ,δ∈(0,1)的学习算法使得任意分布D以及任意的标签函数f:X->{0,1}，如果这些关系(H、D、f)成立(能够在H中找到一个h，使得(L_D(f)=0))，那么有一个学习算法，当样本数比较多的时候m≥(m_H(ɛ,δ))(由D产生，由f标注)，有一个很高的概率(1-δ)使得广泛损失(L_{(D,f)}≤ɛ)。
这里的先验指的是：(广泛)数据集(可以理解成验证集)分布本身能够被假设函数集合H中的某一个h实现，即该数据集的损失为0。
它跟没有免费的午餐定理的不同在于，没有免费的午餐定理对数据没有要求，而这里是有要求的，即对于数据有一定的限制，而不是任意分布的。
不可知的(Agnostic)PAC Learning
对于PAC Learning的强限制性，我们可以适当放宽。
定义：一个假设函数集合H，如果存在着一个函数(m_H:(0,1)^2->N)以及一个满足任意的ɛ,δ∈(0,1)的学习算法使得任意分布D(X×Y,笛卡尔积)，那么有一个学习算法，当样本数比较多的时候m≥(m_H(ɛ,δ))(由D产生)，有一个很高的概率(1-δ)使得广泛损失(L_D(h)≤min_{h'∈H}L_D(h')+ɛ)。
这里跟PAC Learning不同在于，它不需要一个完全可知的(广泛)数据集，当H中最好的h，这里记为h'可以使得广泛损失达到一定的值(min_{h'∈H}L_D(h'))，如果该数据集遵守先验，那么该值就为0，退回到了之前的PAC Learning。对于不可知的PAC Learning的先验，就为(min_{h'}L_D(h'))。
证明PAC learnable
先给结论，当假设函数集合H是有限的时候，那么就是一个PAC learnable。
引理：每一个有限的假设函数集合H在一定的样本复杂度上都是PAC可学习的。
(m_H(ɛ,δ)≤{log(|H|/δ)\over ɛ})
假设在H中有一个不好的h，它会以很高的概率将数据分错(0-1分类)，那么它把数据分对的概率≤1-ɛ。故而我任意去收集一个训练集，它里面有m个样本，那么对于这个不好的损失函数h达到0的概率为≤((1-ɛ)^m)=(e^{mlog(1-ɛ)})，因为数据集中的每一个数据都是独立分布的。也就是说：一个坏的损失函数在训练中被选中的概率是很低的。
对于整个H来说，我们挑选的都是好的h的概率就为≤(|H|e^{mlog(1-ɛ)})=(e^{log|H|+mlog(1-ɛ)})，为了使得这个概率等于δ，那么有(log|H|+mlog(1-ɛ)=logδ)，从而计算出我们需要的训练集样本量(m=-{log{|H|\over δ}\over log(1-ɛ)}≈{log{|H|\over δ}\over ɛ})
结论：一个有限个假设函数集合H是PAC可学习的，并且需要的训练集样本量为(m_H={log{|H|\over δ}\over ɛ})。