首先来说几种验证训练结果的方法。
保留交叉验证法 hold out cross validation
给出一个训练集，随机分成两个，一部分当做训练子集（一般占70%）用于训练，另一部分当做保留交叉验证子集（30%）用于测试。
k重交叉验证法 k-fold cross validation
将整个数据集分成k部分，拿出k-1部分进行训练，将剩下一个用于测试。重复上述过程k次（每次都不一样），求出均值即为验证结果。一般k取10。
优点：增加了训练数据；缺点：计算代价高；
留一交叉验证法 leave one out cross validation
当k=m（训练数据量）时，称之为留一交叉验证法。一般用于训练数据过少的情况。
特征选择
在进行学习时，过多的特征容易带来过拟合，需要选出一个特征子集，其中的特征与学习算法最相关。
前向搜索法 forward search
过程如下：
- 初始化特征集$\cal F$
- 对于不属于$\cal F$的每一个特征，计算添加该特征后模型精度的提升；
- 选择提升最大的特征加入$\cal F$
- 重复2和3，直到精度不在上升。
当然可以设置阈值k，当$\cal F$包含了k个特征后即停止。
后向搜索法 backward search
基本步骤与上述类似，只是过程相反：首先从满的特征集开始，之后每次删除表现最差的特征。
上述的方法都被称为“wrapping” feature selection（“封装”特征选择），”封装”这个词，意味着：
当你进行选择时（前向搜索或者后向搜索）你需要重复使用学习算法去训练模型，根据结果来选择特征子集。
这种方法主要缺点是计算量大，但是它是一种比较准确的选择方法。
另外有一种算法，可能它的泛化误差不会太低，但是计算代价较小。
特征过滤 filter method
主要方法是，计算每一个特征的一些度量，来衡量对y（label）的影响有多大，一般使用互信息（Mutual Information）来度量：
$$
\begin{align}
MI(x_i, y) &= \sum_{x_i \in \lbrace 0,1 \rbrace} \sum_{y \in \lbrace 0,1 \rbrace} p(x_i, y) \log \frac{p(x_i, y)}{p(x_i)p(y)} \\
&= KL(p(x, y) || p(x)p(y)) \text{, KL divergence}
\end{align}
$$
然后去选择最好的k个特征。