总结自刘东老师《统计学习》课程，教材选用周志华老师《机器学习》西瓜书
每节都给了小结，可以快速了解每节内容

From 1 to 2

从简单的问题入手

问题：珠穆朗玛峰的高度是多少？

答案1：给出一个变量值：8848米

答案2：从数据中获取知识
有一系列测量值{$y_1,y_2,...,y_n$y1​,y2​,...,yn​}，则给出结果
$\hat{y}=\frac{y_1+y_2+...+y_n}{n}$y^​=ny1​+y2​+...+yn​​

几何平均的意义：
1.最小二乘法的估计结果
2.统计解释：极大似然的估计结果（将珠穆朗玛峰的高度看作高斯分布，这时不仅能估计均值，还能估计方差）

考虑相关变量
珠穆朗玛峰高度和四季有关，则定义
$y=ax+b$y=ax+b
y是高度，x是季节，将春夏秋冬简单的量化为0，1，2，3，则采样可以得到类似如下的图

通过最小二乘法可以得到如下的拟合结果

显然这个结果并不够好，那么将变量重新映射为

夏季	春季/秋季	冬季
1	2	3

那么拟合的结果会变为

统计解释

将(y-(ax+b))看作一个0均值的高斯分布变量，也可以用统计学的角度对其进行极大似然估计

小结

1 常用的均值估计与最小二乘法、极大似然估计的关系
2 最小二乘拟合与极大似然估计存在关联，但不存在因果关系
3 变量的重映射很重要！

正则化 Regularization

为什么要有正则化

对待估计的参数进行约束。

考虑上一节的问题，y=ax+b中，显然季节与珠穆朗玛峰高度变化的关系较小，这时就要对a的大小进行限定。
我们有2种约束方法：
1、给定a的范围，求最小平方误差的解
2、同时最小化最小平方误差和a的值

第一种，即有约束问题
$\min\sum{(y_i-(ax_i+b))^2} ,\quad a^2≤C$min∑(yi​−(axi​+b))2,a2≤C
第二种，即无约束问题
$\min\sum{(y_i-(ax_i+b))^2}+\lambda a^2$min∑(yi​−(axi​+b))2+λa2
这两种形式是等价的，也就是说有约束优化问题和无约束优化问题可以互相转化，这种转化通过添加（或减去）正则化项实现。

对于一般情况
$\min f(x),subject \quad to \quad g(x)=0,h(x)≤0$minf(x),subjecttog(x)=0,h(x)≤0
可以用Lagrange乘子法转化为
$L(x,\lambda,\eta)=f(x)+\lambda g(x)+\eta h(x)$L(x,λ,η)=f(x)+λg(x)+ηh(x)
后两项均成为正则化项。可以得到对偶函数
$d(\lambda,\eta)=\min_{x}L(x,\lambda,\eta)$d(λ,η)=xmin​L(x,λ,η)
当$\eta>0$η>0时，对偶函数是原问题的一个下界，即对偶函数的最大值也是原问题的下界。那么
$\max_{\lambda,\eta}d(\lambda,\eta)=\max_{\lambda,\eta}\min_{x}L(x,\lambda,\eta)=d^*$λ,ηmax​d(λ,η)=λ,ηmax​xmin​L(x,λ,η)=d∗
原问题的解记作$f^*$f∗，那么$d^*≤f^*$d∗≤f∗
当一个凸优化问题满足KKT条件时，等价于强对偶性成立，即$d^*=f^*$d∗=f∗

理解KKT条件

KKT条件是
$\nabla f+\lambda \nabla g+\eta \nabla h=0 \\ g(x)=0\\ h(x)≤0\\ \eta≥0\\ \eta h(x)=0$∇f+λ∇g+η∇h=0g(x)=0h(x)≤0η≥0ηh(x)=0
第一条即可导的条件，2、3条为原有的约束条件，4为约束弱对偶性的条件（可以通过调整h(x)的符号调整）
最后一条则较难理解，$\eta h(x)=0$ηh(x)=0即$\eta=0$η=0或$h(x)=0$h(x)=0。
对于一个凸优化问题，若不考虑约束的全局最优解（平方误差最小的点）在$h(x)≤0$h(x)≤0的约束范围内，则这个不等式约束不起作用，无论有没有这个约束，找到的都会是全局最优的解，则$\eta=0$η=0即表示不等式约束不起作用；相反，若全局最优解不在约束范围内，则不等式约束起作用，这时找到的解一定在不等式约束边界上，则$h(x)=0$h(x)=0。

正则化的贝叶斯解释

对待估计参数做约束，在统计角度看来，就是待估计参数有一个先验分布。
正则化项加的越大，说明我们对先验的估计越确信，也说明对样本数据的越不确信；而正则化项越小，说明我们更相信样本。

小结

1 正则化：增加额外信息解决病态优化问题的方法
2 增加额外信息：正则化可以将有约束问题转化为无约束问题来求解
3 解决病态优化问题：正则化约束了模型复杂度
4 KKT条件与对偶性

基函数 Basis Function

变量重映射

第一节提到，变量重映射具有优点且很重要，可以提高回归的精度
重映射用的就是基函数，即把输入x变为$\phi(x)$ϕ(x)，在进行拟合
基函数，常用的有多项式基函数、高斯函数、sigmoid函数等等。
基函数可以让拟合结果出现非线性的形式，但通过改变维度获得简单的线性表达（$w^T\phi(x)+b$wTϕ(x)+b可以看作一个线性的简单表达）

统计解释

类似之前，将$w^T\phi(x)+b$wTϕ(x)+b看作高斯分布变量，即可进行极大似然估计，得到的结果和最小二乘法的结果依然相同

几何解释

每一个样本，通过基函数得到一个向量，所有样本张成一个空间，最终估计的$\hat{y}$y^​是真实的y在这个子空间的投影

等效核函数

本节在SVM中详细解释
考虑正则化项时，优化
$\min \sum (y-w^T\phi(x))+\frac{\lambda}{2}w^Tw$min∑(y−wTϕ(x))+2λ​wTw
得到的系数解记为$w_{ridge}$wridge​（这一形式即ridge回归）
对测试集的回归结果中，存在只与测试集的输入x和训练集的各个输入$x_i$xi​有关的项，这一项可以用核函数表示为$k(x,x_i)$k(x,xi​)
核函数等效于使用基函数进行重映射

小结

1 基函数十分重要，将输入重映射可以提高精度
2 基函数的使用可以简化模型表达，将其表示为线性回归形式

偏差-方差分解

偏差与方差的trade-off

对一个正弦函数采样多个训练集，采样时有高斯噪声干扰，用高斯基函数拟合并应用正则化项，改变$\lambda$λ的结果如下



显然，$\lambda$λ越小，拟合的平均结果越接近正确的正弦函数，但每次回归的结果方差越大；$\lambda$λ越大，回归结果间的方差很小，但均与正确的函数有较大偏差
考虑准确值与回归的估计值的差的期望，$E(y-\hat{w}^T\phi(x))$E(y−w^Tϕ(x))，其结果中三项分别为偏差的平方，方差与噪声之和，噪声为无法避免的，而另外两项是可以trade-off的，即把这两项和作为loss function

由以上实验可知，施加正则化过强，将增大偏差，而正则化施加不足，则会导致方差过大，即所谓的过拟合
在训练时，通过交叉验证（cross-validation）可以验证trade-off的效果

小结

1 偏差与方差是一对矛盾，可以trade-off
2 通过正则化进行trade-off，通过训练时的cross-validation可以验证
3 正则化项越大，偏差越大；正则化项越小，方差越大

常用的正则化形式

L范数与best subset, Lasso, Ridge回归

最小二乘法回归的优化目标为
$\min \sum (y_i-w^T\phi(x_i))$min∑(yi​−wTϕ(xi​))
常用的Ridge回归（岭回归）优化目标为
$\min \sum (y_i-w^T\phi(x_i))+\frac{\lambda}{2}w^Tw$min∑(yi​−wTϕ(xi​))+2λ​wTw
即约束了$||w||_2$∣∣w∣∣2​的范围
更一般化的形式则为
$\min \sum (y_i-w^T\phi(x_i))+||w||_q$min∑(yi​−wTϕ(xi​))+∣∣w∣∣q​
即$L_q$Lq​范数正则化
定义$L_q$Lq​范数
$||w||_q=\sqrt [q]{\sum|{w_{|i}}|^q}$∣∣w∣∣q​=q∑∣w∣i​∣q​
常用的正则化形式有
best subset：最小化w中不为0的个数
$\min \sum (y_i-w^T\phi(x_i))+||w||_0$min∑(yi​−wTϕ(xi​))+∣∣w∣∣0​
Lasso回归（套索回归）：最小化绝对值之和
$\min \sum (y_i-w^T\phi(x_i))+||w||_1$min∑(yi​−wTϕ(xi​))+∣∣w∣∣1​
Ridge回归（岭回归）：最小化$l_2$l2​范数，若w是向量则最小化的是w的模
$\min \sum (y_i-w^T\phi(x_i))+||w||_2$min∑(yi​−wTϕ(xi​))+∣∣w∣∣2​

稀疏性

best subset正则化使系数矩阵w中的0的个数最多，即得到尽可能稀疏的系数矩阵
为什么要稀疏？
稀疏性使得与回归结果时最相关的元素被提取出来
但是，$l_0$l0​范数在0点不可导，其他位置导数为0，其优化问题是NP-hard的
可以证明，$l_0$l0​范数的正则化与$l_1$l1​范数的正则化大多数情况下等效，因此可以用Lasso回归代替best subset回归

小结

1 常用L范数作为正则化项
2 best subset挑选与回归结果最相关的输入分类，保证稀疏性，但求解是NP-hard问题
3 Lasso回归与best subset通常等效
4 Ridge回归，结果通常不稀疏，即正则化力度较弱

线性回归贝叶斯方法

从概率的角度看回归问题

回归，即估计映射的系数矩阵，则可以将待估计的量视作一个分布，系数先验分布假设为
$p(w|\mu,S)$p(w∣μ,S)
采样后，对每个样本有似然概率
$p(y_i|x_i,w)$p(yi​∣xi​,w)
则利用先验概率和似然概率，可以计算后验概率
$p(w|x_i,y_i)$p(w∣xi​,yi​)
根据最大后验概率原则，可以估计回归系数矩阵w


上图为一个线性回归的例子，表明了样本点数增加对后验概率的改变以及回归结果的改变

先验概率与正则化

先验概率的设计，相当于对系数的约束
先验概率为0均值高斯分布，相当于用了Ridge回归
先验概率为0均值拉普拉斯分布，相当于用了Lasso回归
而先验概率中的参数（均值，方差等）可以视为超参，超参的估计也可以通过样本进行估计，将超参纳入贝叶斯模型的考虑，作为变量进行估计

小结

1 线性回归可以利用贝叶斯方法求解，估计待求系数的分布
2 贝叶斯方法和正则化存在对应关系

总结

1.线性回归，根据样本对，估计了输入输出之间的映射
2.正则化，实现了有约束问题与无约束问题的转化，约束模型复杂度解决病态回归问题，实现偏差-方差trade-off（正则化越强偏差越大，正则化越弱方差越大越容易过拟合）
3.基函数，实现输入的重映射，能将更复杂的回归模型进行简单的表示，能提高精度
4.常用的3中正则化方式，在不同程度上约束模型复杂度，追求稀疏性
5.线性回归，均可以从统计的角度理解，通过贝叶斯方法进行估计