统计学习是指：从给定的、有限的、用于学习的训练数据集合出发，假设数据是独立同分布产生的；并且假设要学习的模型属于某个函数的集合，称为假设空间；应用某个评价准则，从假设空间中选取一个最优模型；最优模型的选取由算法实现。

按学习分类

• 无监督学习
• 半监督学习

按模型分类

• 概率模型和非概率模型
• 线性模型和非线性模型
• 参数化模型和非参数化模型

按算法分类

• 在线学习和批量学习

按技巧分类

• 贝叶斯学习

决策函数组成的假设空间

F={fθ|Y=fθ(X),θ∈Rn}

条件概率组成的假设空间

F={Pθ|Pθ(Y|X),θ∈Rn}

其中θ是模型参数，它的取值范围Rn称为参数空间。

损失函数度量模型一次预测的好坏，风险函数度量平均意义下模型预测的好坏。

损失函数记作L(Y,f(X))。常用的有

• 0-1损失函数：L(Y,f(X))=[Y=f(X)]
• 平方损失函数：L(Y,f(X))=(Y−f(X))2
• 绝对损失函数：L(Y,f(X))=|Y−f(X)|
• 对数损失函数：L(Y,P(Y|X))=−logP(Y|X)

损失函数越小，模型就越好。模型的输入(X,Y)遵循联合分布P(X,Y)，所以损失函数的期望为：

Rexp(f)=EP[L(Y,f(X))]=∫X×YL(y,f(x))P(x,y)dxdy

学习的目标是寻找期望风险最小的模型。但是由于联合分布是未知的，因此我们无法比较不同模型的期望风险。

对于训练数据集

T={(xi,yi)|i∈[1,N]}

模型f(X)关于T的平均损失称为经验风险

Remp(f)=1NN∑i=1L(yi,f(xi))

根据大数定理，当样本数量N趋于无穷时，经验风险趋于期望风险。我们可以用经验风险来估计期望风险。

监督学习的基本策略有两种：

• 经验风险最小化（ERM）
• 结构风险最小化（SRM）

经验风险最小化选择经验风险最小的模型，它在样本容量足够大的情况下效果很好，但是样本容量较小的时候会发生过拟合。

结构风险最小化可以避免过拟合，结构风险是在经验风险的基础上加上表示模型复杂度的正则化项。

我们需要设计良好的算法，在假设空间中找到风险最小的模型。

随着模型的复杂度上升，训练误差会逐步降低，但是测试误差在选择模型复杂度低于真实模型复杂度的时候降低，高于真实模型复杂度的时候升高。

一种避免过拟合的方法是正则化，采用结构风险最小化策略。其一般形式为：

minf∈F1NN∑i=1L(yi,f(xi))+λJ(f)

正则化项可以采用参数向量的L1或L2范数。

从贝叶斯估计的角度来看，正则化项对应于模型的先验概率，假设越复杂的模型出现的概率越低。

另外一种方式是交叉验证。

如果给定的样本数量足够，可以将数据集随机地切分为三部分：训练集，验证集，测试集。其中训练集用于训练模型，验证集用于挑选模型，而测试集用于对模型的泛化能力进行评估。

但是实际上数据是不充足的，为了选择更好的模型，可以采用交叉验证的方式。

• 简单交叉验证：随机地将已知数据分为两部分，一部分作为训练集，另一部分作为测试集。然后用训练集在各种条件下训练模型，之后选择在测试集上测试误差最小的模型
• S折交叉验证：随机将数据切分为S个互不相交、大小相同的子集；然后利用S−1个子集的数据训练模型，利用剩下的一个子集测试模型；总共可以进行S次，选择S次评测中平均测试误差最小的模型。
• 留一交叉验证：S则交叉验证的特殊情况，此时S=N（即每个子集大小都是1），适用于数据极度缺乏的情况。

泛化误差用来评价学习方法的泛化能力。泛化误差等价于模型的期望风险，我们实践中一般用测试误差来估计泛化误差。

学习方法的泛化能力的比较一般通过研究泛化误差的概率上界进行，简称为泛化误差上界。

对于二类分类问题，如果假设空间是有限的且大小为d，对任意一个函数f∈F，至少以概率1−δ使得下面不等式成立，其中0<δ<1：

R(f)≤ˆR(f)+√12Nlogdδ

感知机是二类分类的线性分类模型。输出值为{+1,−1}。

感知机学习旨在求出将训练数据进行线性划分的分离超平面。

假设输入空间是X⊆Rn，输出空间是Y={+1,−1}。输出x∈X表示实例的特征向量，对应于输入空间的点，输出y∈Y表示实例的类别。由输入空间到输出空间的如下函数：

f(x)=sign(w⋅x+b)

称为感知机。其中w和b称为感知机模型参数，w∈Rn叫做权值向量，b∈R叫做偏置。

感知机的几何解释是线性方程w⋅x+b是Rn中的一个超平面S，其中w是超平面的法向量，b是超平面的截距。这个超平面将特征空间划分为两个部分，两个部分中的点分别被分类为正负两类。而超平面S称为分离超平面。

感知机的损失函数的定义，一个自然的选择是误分类点的总数，但是这样的损失函数不是参数w和b的连续可导函数，不易优化。另外一个选择是使用误分类点到超平面S的总距离。

定义任一点x0到超平面S的距离为：

1‖w‖|w⋅x0+b|

其次对误分类的数据(xi,yi)来说有：

−yi(w⋅xi+b)>0

因此误分类点到超平面S的距离是

−1‖w‖yi(w⋅xi+b)

记所有误分类点的集合为M，那么总距离为

−1‖w‖∑xi∈Myi(w⋅xi+b)

定义损失函数为

L(w,b)=−∑xi∈Myi(w⋅xi+b)

感知机学习算法是误分类驱动的，具体采用随机梯度下降法。首先任意选择一个超平面w0,b0，之后不断用梯度下降法极小化损失函数。极小化过程中不是一次使M中所有误分类点的梯度下降，而是一次随机选取一个误分类点并使其梯度下降。

假设误分类点集合M是固定的，那么损失函数L(w,b)的梯度由

∇wL(w,b)=−∑xi∈Myixi∇bL(w,b)=−∑xi∈Myi

随机选取一个误分类点(xi,yi)，对w,b进行更新：

w←w+ηyixib←b+ηyi

其中η是步长（学习率），取值范围为0<η≤1。

重复上述流程直到不存在误分类点。

算法的收敛性

设训练数据集T是线性可分的，则：

(1) 存在满足条件$|\widehat{w}{opt}|=1的超平面\widehat{w}{opt}\cdot \widehat{x}=0将训练数据完全正确分开，且存在\gamma>0，对于任意1\leq i\leq N$，有

yi(ˆwopt⋅ˆxi)≥γ

(2) 令R=max1≤i≤N‖ˆxi‖，则感知机算法在训练数据集上的误分类次数k满足不等式：

k≤(Rγ)2