前言
cs229讲义 斯坦福大学的CS229课程是学习机器学习的必备之课，之前是由吴恩达主讲的课程，后来由于不明原因课程被斯坦福大学下架。
note5的主要内容：模型选择，特征选择，贝叶斯估计
重新理解，加油~
Part VII 正则化和模型选择
设想给一个机器学习的问题选择模型，例如，若选择多项式回归模型$h_{\theta}(x) = g(\theta_{0}+\theta_{1}x+\theta_{2}x^{2}…+\theta_{k}x^{k})$，然后$k$的取值。那怎么才能自动选择一个可在偏差（bias）和方差（variance）之间平衡的模型呢？或者换一个说法，怎么自动选出来一个带宽参数（bandwidth parameter） $\tau $ 用于局部加权回归（locally weighted regression），或者怎么自动选出一个参数 C 用于拉格朗日正则化的支持向量机算法（l1-regularized SVM）？
为了具体一些，假设个数有限的模型集合$M = {M_{1},…,M_{d}} $。例如，在上面提到的例子，$M_{i} $ 就是 $i $次多项式回归模型。换个说法就是，如果我们要从支持向量机算法（SVM）、神经网络算法（neural network）、逻辑回归算法（logistic regression）当中三选一，那么这里的 M 就应该都包含这些模型。
1，交叉验证
假设有一个训练集$S $，了解了经验风险最小化（empirical risk minimization，缩写为 ERM），就像算法初始化一样，接下来通过ERM来进行模型选择：
- 1，对训练集 $S $ 中的每一个模型$M_{i} $ 进行训练，得到相应的假设$h_{i} $。
- 2，从这些假设中选取训练误差最小的假设（hypotheses）。
这个算法是行不通的。
若考虑多项式模型，要考虑多项式的阶（最高次项的次数），阶越高，对训练集 S 的拟合程度就越好，训练误差自然也就更小。然而，这个方法选出来的总是那种波动非常强（high-variance）的高次多项式模型（high-degree polynomial model），这种情况之前讨论过，通常都是很差的选择。
下面这个算法就更好一些，叫做保留交叉验证（hold-out cross validation），也叫做简单交叉验证（simple cross validation），步骤如下：
- 1，随机拆分训练集 $S $ 成 $S_{train} $ (如可选 70% 的比例) 和 $S_{cv} $ (训练集中剩余的 30%用于验证)。这里的 $S_{cv} $ 就叫做保留交叉验证集。
- 2，只对集合 $S_{train} $ 中的每一个模型 Mi 进行训练，然后得到假设$h_{i} $。
- 3，筛选并输出验证集上有最小误差的 $\hat{\epsilon}S_{cv}(h_{i}) $假设$h_{i} $ 。
这样通过在部分未进行训练的样本集 $S_{cv}$ 上进行测试，我们对每个假设 hi 的真实泛化误差（generalization error）就能得到相对更好的估计，然后就能选择出来一个最小估计泛化误差的假设了。通常可以选择 $\frac{1}{4} ~ \frac{1}{3} $ 的数据样本用来作为交叉验证集，30% 是一个很典型的选择。
还有另外一种备选方法，就是在第三步的时候，选择与最小估计经验误差 $\hat{\epsilon}S_{cv}(h_{i}) $ 对应的模型 $M_{i} $ ，然后在完整数据集 S 上用 $M_{i} $ 来再次训练。（这个思路通常都不错，但有一种情景例外，就是学习算法对初始条件和数据的扰动非常敏感的情况。在这样的方法中，适用于$S_{train} $ 的模型未必就能够同样适用于 $S_{cv} $，这样就最好还是放弃再训练的步骤。）
使用保留交叉验证集的一个弊端就是“浪费”了30% 左右的训练样本数据集，甚至即便对整个训练集重新训练模型，也无非是尝试在一个 0.7m 规模的训练样本集上试图寻找一个好的模型来解决一个机器学习问题，而并不是使用了全部的 m 个训练样本，因为我们每次都是在仅 0.7 m 规模样本上进行训练得到模型。当然了，如果数据非常充足，或者是很廉价的话，也可以用这种方法，而如果训练样本数据本身就很稀缺的话，那就最好用其他方法了。
下面就是一种这样的方法，名字叫k-折交叉验证(k-fold cross validation)，这样验证集数据规模都更小：
- 1，随机将训练集 $S $ 切分成 $k $ 个不相交的子集，其中每一个子集的规模为 $\frac{m}{k} $ 个训练样本，把这些子集称为 $S_{1},…,S_{k} $。
- 2，对每个模型 $M_{i} $，我们都按照下面的步骤来进行评估：对$j = 1, …, k $，在 $ S_{1}···\bigcup S_{j−1} \bigcup S_{j+1}\bigcup ···S_{k} $上（也就是除了 $S_{j} $ 之外的其他所有数据）对模型 $M_{i} $ 进行训练，然后得到假设 $h_{ij} $ 。接下来针对 $S_{j} $ 使用假设 $h_{ij} $ 进行测试，得到经验误差 $\hat{\epsilon}S_{j}(h_{ij}) $，对其取平均值（也就是对所有的 $j $ 都计算然后取平均值），计算得到的值就当做是模型 $M_{i} $ 的估计泛化误差。
- 3，选择具有最小估计泛化误差的模型 $M_{i} $，然后在整个训练样本集 $S $ 上重新训练该模型，这样得到的假设就可以输出作为最终结果了。
通常这里折叠的次数 $k $ 一般是 10，即 $k = 10 $。这样每次进行保留用于验证的数据块就只有 $\frac{1}{k} $ ，这就比之前的 30% 要小多了，当然这样一来这个过程也要比简单的保留交叉验证方法消耗更多算力成本，因为现在需要对每个模型都进行 k 次训练。
虽然通常选择都是设置 $k = 10 $，不过如果一些问题中数据量确实很匮乏，那有时候也可以走一点极端，设 $k = m $，这样是为了每次能够尽可能多地利用数据，尽可能少排除数据。这种情况下，我们需要在训练样本集 $S $ 中除了某一个样本外，在其他所有样本上进行训练，然后在保留出来的单独样本上进行检验。然后把计算出来的 $m = k $个误差放到一起求平均值，这样就得到了对一个模型的泛化误差的估计。这个方法有专门的名字；由于每次都保留了一个训练样本，所以这个方法就叫做弃一法交叉验证（leave-one-out cross validation）。
最后总结一下，咱们讲了不同版本的交叉验证，在上文中是用来作为选择模型的方法，实际上也可以更单纯地用来对一个具体的模型或者算法进行评估。例如，如果你已经实现了某种学习算法，然后想要估计一下算法的性能表现（或者是你创造了一种新的学习算法，然后希望在技术论文中报告你的算法在不同测试集上的表现），交叉验证都是个很好的解决方法。
2，特征选择
模型选择的重要阶段就是特征选择，设想你面对一个监督学习问题，其中特征值的数量 $n $ 特别大（甚至可能比训练样本集规模还大，即$n >> m $），然而可能只有小部分的特征是与学习任务“相关”的。即便是针对 $n $ 个输入特征值使用一个简单的线性分类器，假设类的 VC 维也依然能达到 O(n)，就很有过拟合的潜在风险，除非训练样本集也足够巨大。
在这样的背景下，就可以用特征选择算法来降低特征值的数目。假设有 $n $ 个特征，那么就有 $2^{n} $ 种可能的特征子集（因为 n 个特征中的任意一个都可以被某个特征子集包含或者排除），因此特征选择就可以看做是对 $2^{n} $ 个可能的模型进行选择。对于特别大的 $n $，要是彻底枚举和对比全部 $2^{n} $ 种模型，成本就太高了，所以通常的做法都是使用启发式搜索过程（heuristic search procedure）来找到一个好的特征子集。下面的搜索过程叫做向前搜索（forward search）：
- 1，初始化集合 $ \mathcal{F} = \emptyset $.
- 2，循环下面的过程
{
(a) 对于 $ i =1, …, n $ ，如果 $ i\notin \mathcal{F} $, 则令 $\mathcal{F}_{i} = \mathcal{F} \bigcup \{i\} $，然后使用某种交叉验证来评估特征 $\mathcal{F}_{i} $。（也就是说，仅仅使用 $\mathcal{F}_{i} $ 当中的特征来训练你的学习算法，然后估计一下泛化误差。）
(b) 将 $\mathcal{F} $ 设为步骤 (a) 中的最佳特征子集。
} - 3，整个搜索过程中筛选出来了最佳特征子集，将其输出。
上述算法最外层的循环体可以在 $\mathcal{F} = \{1, … , n\} $ 为全部特征时终止，或者也可以在 $|\mathcal{F}| $ 超过某个预设阈值时终止（当算法要用到的特征数量达到了最大值）。
这个算法本质是模型特征选择包装器的一个实例，算法本身就是将学习算法进行“打包”的过程，然后重复调用这个学习算法来评估算法对不同特征子集的效果。除了向前搜索，还有其他的搜索过程，例如逆向搜索，从 $\mathcal{F} = \{1, …, n\} $ ，即全部特征开始，然后重复，每次删减一个特征，直到 $\mathcal{F} $ 为空集，即 $ \mathcal{F} = \emptyset $ 时终止。
这种包装器特征选择算法通常效果不错，不过对算力开销也很大，尤其是要对学习算法进行多次调用。实际上，完整的向前搜索（是 $\mathcal{F} $ 从空集开始，到最终达到整个样本集规模，即 $\mathcal{F} = \{1, …, n\} $ 终止），要对学习算法调用约 $O(n^{2}) $ 次。
过滤器特征选择算法（Filter feature selection methods）给出的特征子集选择方法更具有启发性，而且在算力上的开销成本也更低。思路是，计算一个简单的分值 $S(i)$，用来衡量每个特征 $x_{i} $ 对分类标签 $y $ 的信息量。然后，只需找到最大信息量分值 $S(i) $ 的一组，选择使用其中的 $k $ 个特征。
怎么去定义用于衡量信息量的分值 $S(i) $ 呢？一种思路是使用 $x_{i} $ 和 $y $ 之间相关系数的值（或其绝对值），这可以在训练样本数据中算出。这样我们选出的就是与分类标签$y $关系最密切的特征值。实践中，通常（尤其当特征 $x_{i} $ 为离散值时）选择 $x_{i} $ 和 $y $ 的互信息（mutual information）来作为 $S(i) $，缩写为 $MI(x_{i}, y) $。
上式中，假设了 $x_{i} $ 和 $y $ 都已经二值化，更广泛的情况下总和将会超过变量的范围。$p(x_{i},y)$， $p(x_{i}) $和 $p(y) $ 的概率都可以根据它们在训练集上的经验分布而推测得到。
要对这个信息量$x_{i}$的作用有一个更直观的印象，也可以将互信息表达成 KL 散度（Kullback-Leibler divergence，也称 KL 距离，常用来衡量两个概率分布的距离）：
在下一节当中，会更多描述 KL ，这里比较通俗地说，这个概念对 $p(x_{i},y) $ 和 $p(xi)p(y)$ 的概率分布差异大小给出一个衡量。如果 $x_{i} $ 和 $y $ 是两个独立的随机变量，那么必然有 $p(x_{i}, y) = p(x_{i})p(y) $，而两个分布之间的 KL 散度就应该是 $0 $。这也符合下面这种很自然的认识：如果 $x_{i} $ 和 $y $ 相互独立，那么 $x_{i} $ 很明显对 $y $ 是“完全无信息量”的，因此对应的信息量分值 $S(i) $ 就应该很小。与之相反地，如果 $x_{i} $ 对 $y $ “有很大的信息量”，那么这两者的互信息$MI(x_{i},y) $ 就应该很大。
最后一个细节：现在已经根据信息量分值 $S(i) $ 的高低来对特征组合进行了排序，那么要如何选择特征个数 $k$ 呢？一个标准办法就是使用交叉验证从可能的不同 $k $ 值中进行筛选。例如，在对文本分类使用朴素贝叶斯方法），这个问题中的词汇规模$n $ 通常都会特别大，使用交叉验证的方法来选择特征子集，一般都能提高分类器精度。
3，贝叶斯估计和正则化
在本章，我们要讲一下我们“军火库”中的另外一种工具，用于我们对抗过拟合。
在本章的开头部分，我们谈到了使用最大似然来进行参数拟合，然后根据下面的式子来选择参数：
在随后的讨论中，我们将$\theta$视为一个未知参数，概率统计中将$\theta $视为未知常值，并不是随机的，但恰好是未知的，我们的工作就是提出统计处理流程（如最大似然）来尝试估计这个参数。
另外一种解决参数估计的方法是贝叶斯估计，$\theta$ 当做是未知的随机变量，先给定一个在 $\theta $ 上的先验分布$p(\theta) $，这个分布表示关于参数的“预先判断”。给定一个训练集合 $S = \{(x^{(i)},y^{(i)})\}^{m}_{i=1} $，当对一个新的 $x $ 进行预测的时候，可以计算在参数上的后验分布（posterior distribution）：
上式中，$p(y^{(i)}|x^{(i)},\theta) $ 是机器学习问题中的模型。例如，如果是贝叶斯逻辑回归，可能就会选择 $p(y^{(i)}|x^{(i)}, \theta) = h_{\theta}(x^{(i)})^{y(i)}(1−h_{\theta}(x^{(i)}))(1−y^{(i)}) $，其中 $h_{\theta}(x^{(i)}) = 1/(1 + exp(−\theta^{T}x^{(i)}))^{3} $。
若有一个新的测试样本 $x $，需要进行预测，可以使用$\theta$ 上的后验分布来计算分类标签上的后验分布：
上面等式中，$p(\theta|S) $ 前面介绍过，如果目标是要根据给定的 $x $ 来预测对应的 $y $ 值，那就可以输出：
简单概述这个过程，可认为是一种“完全贝叶斯”预测，其中预测是通过计算相对于 $\theta$ 上的后验概率 $p(\theta|S) $ 的平均值而得出的。但是，这个后验分布的计算通常是比较困难的，需要对 $\theta$ 进行积分，而 $\theta$ 通常是高维度的，这通常是不能以闭合形式来实现的。
因此在实际应用中，我们都是用一个与 $\theta$ 后验分布近似的分布来替代。常用的一个近似是把对 $\theta$ 的后验分布替换为一个单点估计。对 $\theta$的最大后验估计（MAP，maximum a posteriori estimate）为：
注意到了么，这个式子基本和对 $\theta$ 的最大似然估计（ML,maximum likelihood estimate）形式一样，除了末尾多了一个先验概率分布 $p(\theta)$。
实际应用里面，对先验概率分布 $p(\theta) $ 的常见选择是假设 $\theta \sim N(0 ,\tau^{2}I) $。使用这样的一个先验概率分布，拟合出来的参数 $θ_{MAP} $ 将比最大似然估计得到的参数范数更小。在实践中，贝叶斯最大后验估计（Bayesian MAP estimate）对比参数的最大似然估计（ML estimate of the parameters），前者就更易于避免过拟合。例如，贝叶斯逻辑回归就是一种非常有效率的文本分类算法，即便在文本分类中参数规模 $n $ 通常是远远大于样本规模 $m $ 的，即 $n ≫ m $。