零 问题提出
在机器学习中的偏差与方差一文中提到了偏差与方差。那么在多种预测模型，如线性回归(y=θTx)，多项式回归(y=θTx^(1~m))等，应使用那种模型才能达到偏差与方差的平衡最优？
形式化定义：假设可选的模型集合是M={M1,M2,...,Md}，比如SVM，logisitic回归都在M中。
一 交叉验证（Cross validation）
第一个任务就是从M中选择最好的模型。假设训练集用S表示，若使用如下算法：
那么得出的最好结果一定是属于较为复杂的拟合式，比如高阶多项式，因为这种算法只考虑了误差，只是用训练数据检验拟合结果。所以应使用不同的检验样本，考虑如下算法：
这种方法称为 hold-out cross validation 或者称为简单交叉验证。由于测试集是和训练集中是两个世界的，因此我们可以认为这里的经验错误。这里测试集的比例一般占全部数据的 1/4-1/3。30%是 典型值。
还可以对模型作改进，当选出最佳的模型??后，再在全部数据 S 上做一次训练，显然 训练数据越多，模型参数越准确。
简单交叉验证方法的弱点在于得到的最佳模型是在 70%的训练数据上选出来的，不代表 在全部训练数据上是最佳的。还有当训练数据本来就很少时，再分出测试集后，训练数据就 太少了。 我们对简单交叉验证方法再做一次改进，如下：
这个方法称为 k-fold cross validation（k-折叠交叉验证）。说白了，这个方法就是将简单 交叉验证的测试集改为 1/k，每个模型训练 k 次，测试 k 次，错误率为 k 次的平均。一般讲 k 取值为 10。这样数据稀疏时基本上也能进行。显然，缺点就是训练和测试次数过多。
极端情况下，k 可以取值为 m，意味着每次留一个样例做测试，这个称为 leave-one-out cross validation。
如果我们发明了一种新的学习模型或者算法，那么可以使用交叉验证来对模型进行评价。 比如在 NLP 中，我们将训练集中分出一部分训练，一部分做测试。
二 特征选择（Feature Selection）
特征选择严格来说也是模型选择中的一种。这里不去辨析他们的关系，重点说明问题。 假设我们想对维度为n的样本点进行回归，然而， n可能大多以至于远远大于训练样例数m。 但是我们感觉很多特征对于结果是无用的，想剔除 n 中的无用特征。n 个特征就有2^?种去除 情况（每个特征去或者保留），如果我们枚举这些情况，然后利用交叉验证逐一考察在该情 况下模型的错误率，太不现实。因此需要一些启发式搜索方法。
第一种 前向搜索
前向搜索属于 wrapper model feature selection。Wrapper 这里指不断地使用不同的特征 集来测试学习算法。前向搜索说白了就是每次增量地从剩余未选中的特征选出一个加入特征 集中，待达到阈值或者 n 时，从所有的 F 中选出错误率最小的。 既然有增量加，那么也会有增量减，后者称为后向搜索。先将 F 设置为{1,2,..,n}，然后 每次删除一个特征，并评价，直到达到阈值或者为空，然后选择最佳的 F。 这两种算法都可以工作，但是计算复杂度比较大。时间复杂度为O(n+(n−1)+ (n−2)+⋯+1) = O(?^2)。
第二种 过滤特征选择（Filter feature selection）
过滤特征选择方法的想法是针对每一个特征??，i 从 1 到 n，计算??相对于类别标签y的 信息量S(i)，得到 n 个结果，然后将 n 个S(i)按照从大到小排名，输出前 k 个特征。显然， 这样复杂度大大降低，为 O(n)。
那么关键问题就是使用什么样的方法来度量S(i)，我们的目标是选取与 y 关联最密切的 一些??。而 y 和??都是有概率分布的。因此我们想到使用互信息来度量S(i)，对于??是离散值的情况更适用，不是离散值，将其转变为离散值
互信息（Mutual information）公式
MI 衡量的是??和 y 的独立性。如果它俩独立（?(??,?) = ?(??)?(y)），那么 KL 距离值为 0，也就是说??和 y 不相关了，可以去除??。相反，如果两者密切相关，那么 MI 值会很大。在对 MI 进行排名后，最后剩余的问题就是如何选择 k 值（前 k 个??）。我们 继续使用交叉验证的方法，将 k 从 1 扫描到 n，取最大的 F。不过这次复杂度是线性的了。 比如，在使用朴素贝叶斯分类文本的时候，词表长度 n 很大。使用 filter 特征选择方法，能够增加分类器的精度。
三 贝叶斯统计和规则化（Bayesian statistics and regularization）
