写在前面：
第二章主要让我们了解经验误差与拟合，评估方法，比较检验以及偏差与方法，重点主要是评估方法，理解过拟合与欠拟合，roc曲线。
知识点归纳
经验误差与过拟合
【错误率(error rate)】：分类错误的样本占样本总数的比例
例：m个样本中有a个样本分类错误，则错误率$E = a / m$
【精度(accuracy)】：分类正确的样本数占样本总数的比例
例：m个样本中有m-a个分类正确，则精度$A = 1 - E$
【误差(error)】:学习器的实际预测输出与样本的真实输出之间的差异
例：比如有1000个西瓜，其中真实的好瓜有600个，但是学习器预测的只有400个，这之间的差异就是误差。
【训练误差(training error)或经验误差(empirical error)】：学习器在训练集上的误差
注意：学习器就是在训练集上训练出来的，但实际上在回到训练集上对样本进行结果预测的时候，仍会存在误差。（换句话说，就是结果值与标记值不同）
【泛化误差(generalization error)】:学习器在新样本上的误差
在机器学习中，我们希望做的以及实际能做的如下：
希望: 得到泛化误差最小的学习器，在新样本能表现的很好的学习器，尽可能学出适用于所有潜在样本的“普遍规律”
实际能做到的：努力使经验误差最小化，在训练集上表现的很好的学习器，但是有可能不是我们所希望得到的学习器
【过拟合(overfitting)】：学习能力过于强大。学习器把训练样本学得太好，导致将训练样本中自身的一些特点当做了所有潜在样本都会具有的一般性质，从而导致泛化能力下降。
例：比如10000个球形西瓜来当训练集，此时学习器得到的结果结果是球形西瓜是好瓜，但实际上有的方形西瓜也是好瓜，这就让学习器在面对方形西瓜时候泛化能力就变差了
【欠拟合(underfitting)】：学习能力低下，指对训练样本的一般性质尚未学好。
例：比如形状是判断是否好瓜的重要标准，但经过训练得到的决策树没有对形状进行判断的步骤。
我们实际能做的：努力使经验误差最小化，是指在“过拟合”与“欠拟合”之间寻找一种平衡，并且尽可能的使学习器在不太过拟合的情况下使得训练集的分类更准确，泛化能力更强。
**注意：任何学习算法都有针对过拟合的措施，但是过拟合是无法完全避免的，只能缓解或减小其风险，欠拟合是比较容易克服的。
【多项式时间(polynomial time)】：在计算复杂度理论中，指的是一个问题的计算时间m不大于问题大小n的多项式倍数。任何抽象机器都拥有一复杂度类，此类包括可用于此以多项式时间求解的问题。
【P问题】：指的是能够在多项式的时间里得到解决的问题
【NP问题】：指的是能够在多项式的时间里验证一个解是否正确的问题
【证明过拟合无法避免】：
1.机器学习面临一个NP或更难的问题，即$\exists NP$
2.有效的算法需要在多项式时间内运行完成，即$\exists P$
3.当可彻底避免过拟合时，通过最小化经验误差就可获得最优解，即$P = NP$
4.但是实际情况是$P \ne NP $，所以过拟合是无法避免的
评估方法
模型选择(model selection)问题中，理想的解决方案当然是对候选模型的泛化误差进行评估，然后选择泛化误差最小的模型，但实际上，我们无法直接获得泛化误差，而训练误差又由于过拟合现在的存在而不适合作为标准，我们可以通过评估方法、性能度量等方法来进行模型选择。
希望：通过学习评估学习器的泛化误差，选出泛化误差最小的学习器
实际：泛化误差只能通过测试求得的测试误差来表现
为了通过实验测试来对学习器的泛化误差进行评估并进而做出选择，我们需要使用一个测试集(testing set)来测试学习器对新样本的判别能力，然后以测试误差(testing error)作为泛化误差的近似。
注意：测试集应尽可能与训练集互斥，即测试样本尽量不在训练集出现，未在训练过程中使用过。
【测试误差(testing error)】：学习器在测试集上的实际预测输出与测试样本的真实输出之间的差异
【数据集】：包含所有样例的数据集的集合。$D = {(x_1,y_1),(x_2,y_2),(x_3,y_3),\cdots,(x_m,y_m)}$
注意：数据集既要训练，又要测试，所以通过对$D$进行适当的处理，从中产生训练集$S$和测试集$T$。
留出法
【留出法(hold-out)】：直接将数据集$D$划分为两个互斥的集合，其中一个集合作为训练集$S$，另一个作为测试集$T$，即$D = S \cup T$，$S \cup T = \oslash $,在$S$上训练出模型后，用$T$ 来评估其测试误差，作为对泛化误差的估计。
需要注意的是，训练/测试集的划分要尽可能保持数据分布的一致性，避免因数据划分过程引入额外的偏差而对最终结果产生影响。通常使用分层采样。
不同的划分会导致不同的训练/测试集，相应的模型评估的结果也会有差别。故单次使用留出法的估计结果往往不可靠，使用留出法一般要若干次随机划分，重复进行实验评估后取平均值作为留出法的评估结果。
问题：
我们评估的是用训练出的模型的性能，但留出法划分了数据集，使得实际上训练的数据集小了，若比例较大，训练的模型较为接近训练的模型，但是由于较小，评估结果可能就不太稳定准确。若令比重较大，则与差别就更大了。
建议：
训练集/测试集：2/3~4/5
例：
如上，可以看到是两个同心圆。其中红色的内圆是训练集，绿色的部分是测试集，两部分是互不包含的。
因为要保持数据分布的一致性，所以一般采用分层采样，所以如下图所示。（注：用圆心角来体现数据分布的一致性，无论是训练集还是测试集，均在360度范围内分布。）
单次使用留出法得到的估计结果往往不够稳定可靠，所以在使用留出法的时候，一般采用若干次随机划分，重复进行实验评估后取平均值作为留出法的评估结果。(例如进行100次划分，每次会产生一个评估结果，共得出100个评估结果，最后留出法返回的是这100个评估结果的平均值)
如上图，每次测试集取的是绿色的部分，所有得出的结果再取平均值，即时留出法的评估结果。
###交叉验证法(重要)
【交叉验证法(cross validation)】：先将数据集$D$ 划分为$k$个大小相似的互斥子集，即$D = D_1 \cup D_2 \cup \dots \cup D_k$；$D_i \cap D_j = \emptyset( i \not= j)$ .但每个子集$D_i$ 都尽可能保持数据分布的一致性。
如上图所示，每个子集仍然要分层采样。每次用$k-1$子集作为训练集，余下的子集作为测试集。这样就可以获得$k$个测试结果，进行$k$次训练和测试，最终返回的是这$k$个测试结果的均值。
交叉验证法评估结果的稳定性和保真性在很大程度上取决于$k$的取值，所以通过把交叉验证法称为“k折交叉验证法(k-fold corss validation)”，k的常用值为10，下图为10折交叉验证法的图示。
与留出法相似，为了减小因样本划分不同而引入的差别，交叉验证法也需要进行多次试验，用不同的划分方法重复$p$次试验，最终的结果是是这$p$次$k$折交叉验证结果的均值。
总结：
交叉验证法得到的结果是均值的均值，即p个“k个结果的均值”的均值，因此交叉验证法又可以叫做p次k折交叉验证。
交叉验证法的特点：
1、每个子集都会做测试集
2、每个子集分层采样
3、单次k折，切换测试集试验取均值
4、k折划分p次，重复试验再取均值
优点：准确；缺点：开销大
自助法
【自助法(bootstrapping)】：直接以自助采样法(bootstrapping sampling)为基础。给定包含$m$个样本的数据集$D$，我们对它进行采样数据集$D^\prime$：每次随机从$D$中挑选一个样本，将其拷贝放入$D^\prime$，再将该样本放回初始数据集$D$中，使得该样本在下次采样时仍有可能被采到，执行m次(有放回取$m$次)，我们可以得到包含m个样本的数据集$D^\prime$，这就是自助采样的结果。
按此类方法，保证了$D$和$D^\prime$的规模一致。但$D^\prime$虽然也有m个样本，可其中可能出现重复的样本，而$D$中会存在$D^\prime$采样没有采到的样本，这些样本就留作当测试集。
样本在$m$次采样中始终不被采到的概率是:$(1-\frac{1}{m})^m$，即取得的极限为：
$$
\lim_{m\to \infty}（1-\frac{1}{m}）^m \mapsto \frac{1}{e} \approx 0.368
$$
由上可知，初始数据集D中大约有36.8%的样本未出现在采样数据集$D^\prime$中，所以将$D^ \prime$用作训练集，$D$ \ $D^\prime$用作测试集。
优点：自助法在数据集较小，难以有效划分训练/测试集时很有效。能从初始数据集中产生多个不同的训练集，这样对集成学习等方法有很大的好处。
缺点：自助法产生的数据集改变了初始数据集的分布，会引入估计偏差。因此，在初始数据集量足够时，留出法和交叉验证法更常用一些。
调参与最终模型
学习算法中都有参数(parameter)需要设定，参数配置的不同，学得模型的性能往往有显著差别。不仅要对适用学习算法进行选择，还需要对算法参数进行设定，这就是通常指的“参数调节”或简称“调参(parameter tuning)”。
参数调的好不好往往对最终模型性能有关键性影响。
注意以及说明：
通常把学得模型在实际使用中遇到的数据成为测试数据。
模型评估与选择中用于评估测试的数据集称为验证集(validation set)。以便加以区分。
例子：
在研究对比不同算法的泛化性能时，用测试集上的判别效果来估计模型在实际使用时的泛化能力，而把训练数据另外划分为训练集与验证集，基于验证集上的性能来进行模型选择和调参。
