总结自刘东老师《统计学习》课程，教材选用周志华老师《机器学习》西瓜书
每节都给了小结，可以快速了解每节内容
监督学习
什么是监督学习
此前章节所述的回归、分类、概率密度估计问题，都是（全）监督学习的例子。监督学习的过程主要分为两步：训练和推演。
模型分类
决策模型 vs 概率模型
这就是之前介绍所有方法时，一般的回归/分类方法与贝叶斯方法的区别。
一般的方法，求得的解是一个固定的映射
y
^
=
f
(
x
)
\hat{y}=f(x)
y^=f(x)
如果
y
^
\hat{y}
y^可以取连续值，那么就是一个回归问题，如果只能取离散值就是分类问题。对问题如此建模，即利用了决策模型。
贝叶斯方法则是对输入、输出以及参数都赋予一个概率密度函数，需要求的是在某个输入
x
x
x条件下，输出
y
^
\hat{y}
y^的概率
q
(
y
^
∣
x
)
q(\hat{y}|x)
q(y^∣x)。利用贝叶斯方法对问题建模，利用的就是概率模型。
判别模型 vs 生成模型
判别模型，即基于训练样本，估计某一个输入所对应的输出值，即求解
y
=
f
(
x
)
o
r
q
(
y
∣
x
)
y=f(x)\;or\;q(y|x)
y=f(x)orq(y∣x)
而生成模型反之，需要估计某一个输出所对应的输入的值，
x
=
f
(
y
)
o
r
q
(
x
∣
y
)
x=f(y)\;or\;q(x|y)
x=f(y)orq(x∣y)
对于具有连续输入和输出的回归问题，以上两者显得比较自然，甚至可能可以互逆。因此，这两类模型对于分类问题更具有讨论的意义。
通常，求解一个生成模型需要先得到判别模型，毕竟这个模型生成的结果应当能自己判断对错才合理。
判别模型一般不需要很大的训练集就可以得到，且表现很好；生成模型则需要更大的训练集来保证收敛。
ERM
损失函数
评估一个模型的优劣，我们可以用损失函数来判断。损失函数的大小，总是和模型对训练样本估计的结果与真值的差的大小有关。
最小二乘法中，我们用到的损失函数即
(
y
i
−
f
(
x
i
)
)
2
(y_i-f(x_i))^2
(yi−f(xi))2
除此之外，常用的损失函数还有绝对值函数、0-1函数等等。
在感知机、SVM这些分类问题中，我们也定义了更复杂的损失函数。Logistic回归这类估计概率密度的问题，我们通常用对数损失函数
L
(
x
i
,
y
i
,
q
)
=
−
log
q
(
y
i
∣
x
i
)
L(x_i,y_i,q)=-\log{q(y_i|x_i)}
L(xi,yi,q)=−logq(yi∣xi)
风险函数与ERM
假设我们要求的输入输出映射有参数，可以表示为
f
(
x
∣
θ
)
f(x|\theta)
f(x∣θ)，那么风险函数即
R
(
θ
)
=
∫
x
,
y
L
(
x
,
y
,
θ
)
p
(
x
,
y
)
d
x
d
y
R(\theta)=\int_{x,y}{L(x,y,\theta)p(x,y)dxdy}
R(θ)=∫x,yL(x,y,θ)p(x,y)dxdy
可以看出，风险函数是损失函数的函数，即损失函数在所有输入输出上的期望，是平均意义上的损失（误差大小）。显然，最小化（期望）风险函数是我们真正的目标。
上式的定义中，输入输出的联合分布在实际问题中是不可知的，因此在训练集上，我们用经验风险(Empirical Risk)来近似风险函数
R
e
m
p
(
θ
)
=
1
N
∑
1
N
L
(
x
i
,
y
i
,
θ
)
R_{emp}(\theta)=\frac{1}{N}\sum_1^N{L(x_i,y_i,\theta)}
Remp(θ)=N11∑NL(xi,yi,θ)
最小化风险函数，此时就变成了最小化经验风险(Empirical Risk Minimization, ERM)，也就是之前所有问题中我们的优化目标。
ERM好吗？
ERM会导致优化问题变成不适定问题（复杂度变高，解变得不稳定），因此我们引入正则化。
ERM没有考虑先验分布（直接对训练集上的损失函数做平均），因此我们引入贝叶斯方法。
ERM没有考虑数据集方差，因此我们引入偏差-方差tradeoff。
ERM没有考虑模型复杂度，因此我们引入最大描述长度MDL。
这些问题我们都在第一章讨论过了，这里再做一个总结：ERM必然会导致模型复杂度的逐渐上升，导致过拟合，因此需要一系列方法予以解决。
稍后的小节将介绍统计学习理论以及其引入的优化方法。
小结
1 监督学习的模型：决策vs概率，判别vs生成
2 ERM与它的问题
统计学习理论
统计学习理论，主要由Vapnik老爷子和他的合作者共同建立，从数学层面解释了很多统计学习中的问题，比如为什么会出现过拟合等等。ERM导致的产生过拟合问题，在其中也有相应解释，数据的噪声、分布、数量等等都是过拟合产生的原因。
由于本人对这一部分理解不深，所有仅介绍最重要的Hoeffding不等式与VC维。
Hoeffding不等式
经验风险，是对风险函数的近似，Hoeffding不等式为
sup
θ
(
R
(
θ
)
−
R
e
m
p
(
θ
)
)
≤
1
2
N
(
log
M
−
log
η
)
\sup_{\theta}{(R(\theta)-R_{emp}(\theta))}\le \sqrt{\frac{1}{2N}(\log M-\log \eta)}
θsup(R(θ)−Remp(θ))≤2N1(logM−logη)
等价的解释为，用0-1损失函数，有
M
M
M个参数的有限参数模型，当样本数
N
N
N越大时，经验风险以
1
−
η
1-\eta
1−η的概率收敛至风险函数。也就是说，训练集越大，估计的模型越准确。
VC维
对模型
f
(
x
)
f(x)
f(x)，它的VC维定义为，能被模型打散的最大样本数。
如何理解打散？
考虑指示函数
f
(
x
)
f(x)
f(x)（即输出只有分类0或1），给定
N
N
N个样本
x
1
,
.
.
.
,
x
N
x_1,...,x_N
x1,...,xN，对这
N
N
N个样本任意标注，
f
(
x
)
f(x)
f(x)都能将这些样本正确分类，那么称
f
(
x
)
f(x)
f(x)能打散
N
N
N个样本。
N
N
N的最大值，就是
f
(
x
)
f(x)
f(x)的VC维。
下面是几个例子：
线性分类器的VC维是
D
+
1
D+1
D+1（
D
D
D是输入
x
x
x的维数），例如二维输入的线性分类器的VC维是3，二维线性分类器可以打散任意3个样本，但不能打散任意的4个样本
一维可变频率的正弦函数的VC维是无穷大
样本在半径为
R
R
R的球内，SVM的VC维是
h
≤
min
(
D
,
[
R
2
Δ
2
]
)
+
1
h\le \min{(D,[\frac{R^2}{\Delta^2}])}+1
h≤min(D,[Δ2R2])+1
其中， D D D是输入的维数， Δ \Delta Δ是边距， w T x + b ≥ Δ w^Tx+b\ge\Delta wTx+b≥Δ时判为1， w T x + b ≤ − Δ w^Tx+b\le-\Delta wTx+b≤−Δ时判为0。可以看出SVM的VC维是远小于线性分类器的。
可见，VC维衡量了一个函数集的复杂度，表达了模型的容量。
VC维越大学习的过程越复杂，泛化能力越差，要求训练集越大。
这其实解释了为什么SVM那么强大，利用核函数可以让SVM处理更复杂的问题但并不会增大SVM的VC维，因此SVM可以在复杂问题上有更好的表现。
小结
1 Hoeffding不等式：经验风险一致收敛到风险函数
2 VC维：VC维越大，模型容量越大，模型越复杂，越容易过拟合；VC维越小，模型越简单，越难达到较好的效果
改进ERM
ERM一节提到了最小化经验风险可能带来的过拟合问题，统计学习理论（尤其是VC维理论）数学的解释了一系列机器学习中的问题。实际应用中，我们引入结构风险来考虑模型复杂度带来的影响。
SRM
结构风险(Structural Risk)，是随着模型复杂度增大而增大的风险函数。
根据Hoeffding不等式和VC维理论，可以看出模型复杂度越大（
M
M
M越大），收敛越慢，当样本有限时经验风险和期望风险函数的差的上界越大，模型复杂度在这里引入的风险，就是结构风险。
同时最小化经验风险和结构风险，成为了优化问题的目标。
正则化，是引入结构风险的一种常用的具体方法。同样，其他方法（比如贝叶斯方法，MDL等）也可以作为一种正则化，引入经验风险所没有考虑的因素，用于约束模型复杂度。
SRM的哲学思想——奥卡姆剃刀原理
“如无必要，勿增实体”
即，当我们有正确且充分的理论去解释我们观察的现象时，就不需要增加额外的解释了。
小结
1 结构风险最小化SRM与正则化
2 奥卡姆剃刀原理
监督学习的实际应用
应用监督学习时，步骤为：
1.采集数据集（包括数据清洗、数据增强等预处理）
2.确定模型的形式（包括超参数等）
3.确定优化方式（包括优化目标等）
4.训练
5.评估模型
数据集
数据集表示着所感兴趣的问题，数据集采集时需满足独立同分布，数据集中的噪声或离群数据需要被剔除，数据不足时可以进行数据增强。
模型设计
设计模型时需要考虑：
风险函数：除了ERM还需要考虑什么
效率：训练、执行效率以及可扩展性
可解释性
其他特定任务的要求
损失函数的设计应当与评价模型的准则对应。
总结
1 监督学习的基本形式与ERM，ERM的问题
2 统计学习理论与VC维
3 SRM–对ERM的改进
4 监督学习应用中的注意