规则化与模型选择

这部分的内容主要是模型选择、特征选择以及使用参数的最大后验概率来规避最大似然估计可能出现的过拟合问题。

模型选择的主要方法有保留交叉验证、k重交叉验证、留1交叉验证。
特征选择的主要方法有封装特征选择（前向搜索与后向搜索的启发式算法）、过滤特征选择（计算特征与标签之间的互信息进行排名的启发式算法）
最大后验概率是最大似然估计与贝叶斯估计融合的产物，最大似然估计与贝叶斯估计分别是频率学派与贝叶斯学派的代表，目前内容所涉及到的区别主要是频率学派认为模型的参数是一个固定不变的未知值，而贝叶斯学派认为参数是一个具有先验分布的未知值，在知乎上看到一个回答很有趣，其大意为你打麻将的时候，根据麻将规则，某人P有一张牌A，如果他出了胜算更大，但是根据观察他没有出这张牌，如果你是是频率学派，那么你会单纯的根据你所已经观察到的牌去推断你摸到牌A的概率，即P是没有这张牌的，没有出现的牌一定还在剩余的牌里，如果你是贝叶斯学派，除了观察已经出现的牌，你还会根据别人所打出的牌（对方是否有什么套路，有牌但是还没打出），打牌人之间的关系(是否有喂牌情况，故意让别人所以不出)去得到摸出牌A的先验概率，不断修正你摸到牌A的概率。当然，这些估计方法与学派之间的区别不仅是这样，有必要专门学习一下。

交叉验证

如果给定训练集$S$,模型集合$M$中有着不同的假设，选取经验风险最小化的假设不是合理的解决办法，因为存在过拟合的情况。为了避免出现这种情况，有以下几种模型选择方法。

保留交叉验证

保留交叉验证(hold-out cross validation)又叫做简单交叉验证，算法步骤如下：

将训练集随机划分，70%z作为$S_{train}$训练集，30%作为$S_{CV}$交叉验证集。
使用$S_{train}$训练模型，获得对应的假设$h_i$
选择并输出在交叉验证机上既有最小误差的假设$h_i$
（可选步骤）重新使用整个训练集对模型$M_i$训练假设$h_i$

缺点：如果数据本来就比较少，将30%数据作为交叉验证集，会对训练效果造成较大影响

K重交叉验证

K重交叉验证(k-fold cross validation)的目的就是为了解决保留交叉验证在数据比较少时效果不好的缺点。

随机将数据划分为k份，记作$S_1,…,S_k$
对于每个模型$M$，其评估方法如下：每个模型都训练k次，从i=1循环至i=k，每次使用除开$S_i$的数据作为训练集，使用$S_i$作为测试集合，其误差记作$\hat{\mathcal{E}}(h_i)$。经过k次循环后，记录这个模型的平均训练误差。
选择具有最小平均训练误差的模型$M$,使用整个训练集进行训练，最后得到的假设就是最终结果。

留1交叉验证

当数据实在十分稀少的时候，在k重交叉的基础上，令$k=m$。

特征选择

对模型给定n个特征，有$2^n$中可能的特征子集，当$n$非常大的时候，对每一种特征子集都训练一遍的代价是非常大的，因此使用一种启发式的方式去寻找合适的特征子集。

foward search算法

初始化$\mathcal{F}=\phi$
Repeat
$\{ \\ (a)for \quad i=1,…,n,如果i \notin \mathcal{F}，令\mathcal{F_i}=\mathcal{F}\cup\{i\}使用交叉验证去评估特征\mathcal{F_i}\\ (b)将上一步得到的最好的特征子集赋值给\mathcal{F}\\ \}$
选择并输出整个过程中最好的特征子集

在该算法中，外部循环停止的条件可以是当$\mathcal{|F|}=n$时，也可以是自己设定的一个界限。
该算法的实例化被称作封装特征选择(wrapper model feature selection),除了foward search，还有一种被称作backward search的算法，其将$\mathcal{F}$初始化为包含全部特征的全集，每次循环从中去除一个特征，直到$\mathcal{F}=\phi$。

这个算法不是实时更新最佳特征集合的，每次循环的最佳子集都会参与最后的特征选择。
算法的缺点：计算复杂度较大，一个完整的foward search算法会调用$O(n^2)$次学习算法。

过滤特征选择(Filter feature selection)

过滤特征选择的目的是为了在启发式的基础上让计算代价降低。其基本思想是计算每个特征$x_i$对标签$y$的影响程度，记作$S(i)$，然后根据其排名来决定优先选择哪些特征。
具体的，使用MI(mutual infomation)互信息作为$S(i)$,其计算公式为：

$MI(x_i,y)=\sum_{x_i\in\{0,1\}}\sum_{y\in\{0,1\}}p(x_i,y)log\frac{p(x_i,y)}{p(x_i)p(y)}$

上式中所需的概率都可以从训练集中的经验分布得到。
互信息还可以用相对熵(KL散度)来表示。

贝叶斯统计和正则化

贝叶斯正则化是用来防止过拟合的工具。

最大似然估计（Maximum likelihood）

在此前推导线性回归和逻辑回归的代价函数时，都是通过最大似然估计ML得到的优化函数。

$\theta_{ML}=arg\quad max_\theta \prod_{i=1}^mp(y^{(i)}|x^{(i)};\theta)$

关于最大似然估计，这是之前的记录：似然函数，最大似然估计来源于概率中的频率学派(frequentist),其观点是对于一组数据，基于一个模型去拟合参数时，参数$\theta$本身没有概率分布，它是一个未知的常量，通过对观测到的事件进行最大似然估计得到的$\theta$就是最符合已知训练数据的参数。
例子：抛一枚硬币10次，观测到9正1反，设正面向上的概率为p，那么使用最大似然估计，9正1反的概率为$p^9(1-p)$，对此概率最大化，此时对应的p就是通过最大似然估计得到的参数。

贝叶斯估计与最大后验概率（Maximum A Posteriori）

贝叶斯估计是属于贝叶斯学派拟合参数的方法，与最大似然估计相反，在拟合参数时，它认为$\theta$是本身有着先验概率分布的未知值，要做的工作就是在知道观测结果$S$时，哪一个$\theta$的概率最大，这个概率可以通过贝叶斯统计得到。

$\begin{align} p(\theta|S)&=\frac{p(S|\theta)p(\theta)}{p(S)} \\ &=\frac{(\prod_{i=1}^mp(y^{(i)}|x^{(i)},\theta))p(\theta)}{\int_\theta(\prod_{i=1}^mp(y^{(i)}|x^{(i)},\theta)p(\theta))d\theta} \end{align}$

例子：抛一枚硬币10次，观测到9正1反，设正面向上的概率为p，求在事件S为9正1反的条件下，使概率$p(p|S)$
取最大值的p。

如何使用贝叶斯估计的后验概率：

已知数据$S$,要预测一个新的样本$x$的标签$y$，即在已知数据$S$的情况下计算新样本标签$y$的数学期望。

$\begin{align} E[y|x,S]=\int_yyp(y|x,S)dy \end{align}$

此时需要求$p(y|x,S)$，这个式子隐藏了一个含义，y的分布与$\theta$有关，而$\theta$服从于某种分布，因此考虑所有$\theta$可能的情况，使用全概率公式：

$\begin{align} p(y|x,S)=\int_\theta p(\theta,y|x,S)d\theta \end{align}$

运用条件概率：

$\begin{align} p(\theta,y|x,S)=p(y|x,\theta,S)p(\theta|S) \end{align}$

其含义为：已知数据为S的条件下，参数为$\theta$且$x$的标签为$y$的概率=已知数据S和参数为$\theta$的条件下$x$的标签为$y$的概率乘以数据为S的条件下参数为$\theta$的概率
同时，有化简 $p(y|x,\theta,S)=p(y|x,\theta)$
这是因为对于预测$x$,当参数$\theta$确定后，数据S如何分布与x的标签是什么已经没有关系了，x的标签的取值概率完全由参数和模型决定。将（4）代入（3）得到：

$\begin{align} p(y|x,S)=\int_\theta p(y|x,\theta)p(\theta|S)d\theta \end{align}$

现在，如果$\theta$确定，则$p(\theta|S)$确定（使用公式2），$p(y|x,\theta)$也确定，计算出$p(y)$，代入公式3，那么标签y的数学期望也就求出，完成预测。

贝叶斯估计的缺点

由于参数是随机分布的，在公式2中进行积分是非常困难的。通过观察公式2，可以发现分母是一个归一化因子，因此可以不必计算。
于是使用

$\theta_{MAP}=arg\quad max_{\theta}\prod_{i=1}^{i=m}p(y^{(i)}|x^{(i)},\theta)p(\theta)$

上式过程即为最大后验概率，它属于最大似然估计与贝叶斯估计互相融合的方法，一方面具有点估计的特征，另一方面考虑了参数的先验概率$p(\theta)$，通常$p(\theta)$这个先验概率被定义为高斯分布$\theta~\mathcal{N}(0,\tau^2I)$，通过贝叶斯估计的最大后验概率选择的参数与最大似然估计选择的参数相比，过拟合的程度会更小。