模型选择问题

在机器学习中，通常需要评估若干候选模型的表现并从中选择模型。这一过程称为模型选择（model selection）。形式化定义来说可以认为：假设我们有一个有限的模型集合M = {M₁，M₂，… ,M_d}，我们应该选择哪个模型Mi来作为最优模型。可供选择的候选模型可以是有着不同超参数的同类模型。以多层感知机为例，我们可以选择隐藏层的个数，以及每个隐藏层中隐藏单元个数和激活函数；再比如在多项式回归模型h_θ(x)= g(θ₀+θ₁x+...+θ_kx^k)中，我们应该如何选择合适的k值使得模型的偏差方差达成平衡；又比如在局部加权线性回归问题中，我们应该如何选择合适的波长参数τ使得模型的拟合效果最好呢？
一般主要考虑以下几个方面：

交叉验证

通过交叉验证可以从多个模型中选择一个最佳模型，具体参照链接即可。

模型复杂度

以多项式函数的拟合为例，目标是寻找一个K阶多项式函数
$\widehat{y}= b + \sum_{k=1}^{K} x^{k}w_{k}$
在上式中，w_k 是模型的权重参数，b是偏差参数。与线性回归相同，多项式函数拟合也使用平方损失函数。线性函数拟合是特殊的一阶多项式函数拟合。
因为高阶多项式函数模型包含参数更多，模型函数的选择空间更大，所以高阶多项式函数比低阶多项式函数的复杂度更高。因此，高阶多项式函数比低阶多项式函数更容易在相同的训练数据集上得到更低的训练误差。
在给定训练数据集的基础上，模型复杂度和误差之间的关系通常如下图所示。如果模型的复杂度过低，很容易出现欠拟合；如果模型复杂度过高，很容易出现过拟合。应对欠拟合和过拟合的一个办法是针对数据集选择合适复杂度的模型。还有的关于过拟合和欠拟合的参照链接即可。

image.png

特征选择

模型选择的一个特殊并且重要的场景是特征选择(Feature Selection)。假设一个监督学习问题中的特征数n非常大，远远大于训练样本数m，但是我们怀疑其中只有一部分特征和学习问题相关，那么我们就要从中选择出我们需要的特征。
给定n个特征，我们可以有2ⁿ种可能的模型(每个特征要么出现在模型中，要么不出现在模型中)。这样我们就将特征选择问题转化为规模为2ⁿ的模型选择问题。但是这样的计算量太大了，因此我们需要用一些启发式搜索方法进行特征选择。下面的这个算法称为前向搜索(Forward Search)：
1. 初始化特征集合F为空
2. 不断循环以下步骤，直到F的长度达到预设要求：
a. 将i从1到n进行遍历，如果i不在F中，令F_i = F ∪ {i}，然后用某种交叉验证算法计算F_i的误差
b. 选择误差最小的F_i，并更新为F
3.输出最佳特征集合F

上述算法属于封装模型特征选择(Wrapper Model Feature Selection)。前向搜索是指每次循环都是从剩余未被选中的特征中选出一个最好的特征加到特征集合中。与之相对的还有后向搜索(Backward Search)，初始化特征集合F = {1,…,n}，每次循环都是从现有特征集合中选出一个最差的特征，然后将其从特征集合中移除，循环直到F的长度达到预设要求后才结束。
封装模型特征选择可以很好地工作，但是计算量比较大，时间复杂度达到了O(n²)。

过滤特征选择(Filter Feature Selection)算法是另一个启发式搜索方法，拥有较低的计算复杂度。算法的主要思想是，对每一个特征x_i，计算其与y的信息量S(i)，S(i)越大说明x_i与y的相关性越强。计算完所有的S(i)后，选择前k个拥有最大S(i)的特征即可。

在实际应用中，S(i)通常选择为x_i和y的互信息(Mutual Information)MI(x_i, y)：
$MI\left ( x_{i},y \right )= \sum_{x_{i}\in \left \{ 0,1 \right \}}^{ } \sum_{y_{i}\in \left \{ 0,1 \right \}}^{ }p\left ( x_{i},y\right )log\frac{p\left ( x_{i},y\right )}{p\left (x_{i}\right )p\left (y\right )}$
上述公式中的几个概率值都可以在训练集上计算得到。为了对这个公式有直观的感受，我们可以将互信息表示成KL散度(Kullback-Leibler (KL) divergence)的形式：
$MI\left(x_{i},y\right )= KL\left ( p\left ( x_{i},y\right )||p\left (x_{i}\right )p\left (y\right ) \right )$
如果x_i和y互相独立，那么 $p\left ( x_{i},y\right )= p\left (x_{i}\right )p\left (y\right )$ ，那么这两个概率分布的KL散度为0，因此x_i和y是不相关的，对应的S(i)较小。相反地，如果x_i和y的相关性越大，那么KL散度越大，对应的S(i)也较大。
还有一个细节需要注意，计算完所有的S(i)后，应该如何选择k值。一个标准做法是使用交叉验证法来选择k值，不过这次的时间复杂度是线性的。

贝叶斯统计与规则化

在逻辑回归中使用最大似然估计（Maximum Likelihood (ML）法来拟合参数，其公式为：
$\theta _{ML} = arg \: max_{\theta }\prod_{i=1}^{m}p\left ( y^{(i)}|x^{(i)};\theta \right )$
在上式中，我们把θ视为一个未知的常数，这一观点被认为是频率学派(Frequentist)的观点。在频率学派的观点下，θ不是随机的，只是一个未知的变量，我们的任务就是通过某些方法估计出θ的值。
另一种看待θ的观点来自贝叶斯学派(Bayesian)。贝叶斯学派认为θ是随机的未知的变量，因而首先为θ指定一个先验概率(Prior distribution) $p(\theta )$ 。给定一个训练集S = {x(i), y(i)}_i=1,...,m，我们可以计算出θ的后验概率(Posterior distribution)：
$p(\theta |S) = \frac{p(S|\theta)p(\theta))}{p(S))} = \frac{\left ( \prod_{i=1}^{m}p\left ( y^{(i)}|x^{(i)};\theta \right )\right )p\left ( \theta \right )}{\int \left (\left ( \prod_{i=1}^{m}p\left ( y^{(i)}|x^{(i)};\theta \right ) \right )p\left ( \theta \right )\right )d\theta }$
上式中的 $p\left ( y^{(i)}|x^{(i)};\theta \right )$ 的计算取决于我们使用的具体模型。比如在贝叶斯逻辑回归模型中，
$p\left ( y^{(i)}|x^{(i)};\theta \right ) = h_{\theta }\left ( x^{(i)} \right )^{y^{(i)}}\left ( 1- h_{\theta }\left ( x^{(i)} \right )\right )^{1-y^{(i)}}$
$h_{\theta }\left ( x^{(i)} \right ) = 1/ \left ( 1+exp\left ( -\theta ^{T}x^{(i)} \right ) \right )$
对于一个新的输入 $x$ ，我们可以用下面的公式进行预测：
$p(y|x,S) = \int p(y|x,\theta )p(\theta |S)d\theta$
如果我们要求期望的话，可以用如下公式：
$E[y|x,S] = \int yp(y|x)dy$
我们可以把上面步骤理解为“全贝叶斯预测”，因为我们在求后验概率时是对θ所有的值都计算了一遍，遗憾的是通常我们很难计算出这样的后验概率，因为对所有θ(通常是高维的)求积分是非常困难的。

因此，在实际应用中，我们需要对后验概率作一个近似估计，通常用单个θ的取值来替代整个后验概率。最大后验概率估计(Maximum a Posteriori(MAP))方法就采用了这个思想，其估计公式为：
$\theta _{MAP} = arg \: max_{\theta }\prod_{i=1}^{m}p\left ( y^{(i)}|x^{(i)},\theta \right )p(\theta )$
可以发现， $\theta _{MAP}$ 和 $\theta _{ML}$ 的公式非常相似，除了在最大后验概率估计公式后面多了一项θ的先验概率。

在实际应用中，我们通常让θ服从高斯分布 $N(0,\tau ^{2}l)$ 。确定了这样的先验概率后，通常 $\theta _{MAP}$ 比 $\theta _{ML}$ 的拟合效果更好，出现过拟合的概率更低。

总结

模型选择的常用方法是交叉验证，交叉验证具体又分为简单交叉验证、k重交叉验证和留一交叉验证等方法；
特征选择的常用方法有封装模型特征选择和过滤特征选择。封装模型特征选择分为前向搜索和后向搜索，时间复杂度都为O(n2)；过滤特征选择的时间复杂度为O(n)；
在参数拟合问题上有频率学派和贝叶斯学派两种观点。频率学派认为θ是固定的未知-的变量，使用最大似然估计法；贝叶斯学派认为θ是随机的未知的变量，使用最大后验概率估计法；最大后验概率估计法拟合出来的参数通常拟合效果更好，出现过拟合的概率更低。

收集与：
https://www.dazhuanlan.com/2020/02/02/5e364aa02195c/
https://www.jianshu.com/p/4b21f2549c26
https://blog.csdn.net/qq_41455420/article/details/79671237
https://www.jianshu.com/p/d5d59d94ea5f
http://cs229.stanford.edu/notes/cs229-notes5.pdf

机器学习笔记（四）——模型选择