统计学习方法

Published: August 18, 2022 by Daltao

• Categories:
• ML 1

• Tags:

• 概念
  • 分类
  • 三要素
    • 模型
    • 策略
    • 算法
  • 过拟合
    • 正则化
    • 交叉验证
  • 泛化能力
• 感知机
  • 损失函数
  • 学习算法
  • 算法的收敛性
• k近邻法
  • 距离度量
  • k值选择
  • 分类决策规则
  • 算法实现
• 朴素贝叶斯法
  • 原理
  • 后验概率最大化的解释
  • 极大似然估计
  • 学习算法
  • 贝叶斯估计
• 决策树
  • 学习算法
  • 特征选择
    • 信息增益
    • 信息增益比
  • ID3算法
  • C4.5算法
  • 剪枝
  • CART算法
    • 生成回归树
    • 生成分类树
• Logistic回归与最大熵模型
  • 二项Logistic回归模型
  • 多项Logistic回归
  • 最大熵模型

概念

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

分类

按学习分类

• 监督学习
• 无监督学习
• 强化学习
• 半监督学习
• 主动学习

按模型分类

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

按算法分类

• 在线学习和批量学习

按技巧分类

• 贝叶斯学习
• 核方法

三要素

模型

决策函数组成的假设空间

$$F=\left\{f_\theta|Y=f_\theta(X),\theta\in R^n\right\}$$

条件概率组成的假设空间

$$F=\left\{P_\theta|P_\theta(Y|X),\theta\in R^n\right\}$$

其中$\theta$是模型参数，它的取值范围$R^n$称为参数空间。

策略

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

损失函数记作$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))=-\log P(Y|X)$

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

$$\begin{aligned} &R_{\exp}(f) \\=&E_P[L(Y,f(X))] \\=&\int_{X\times Y}L(y,f(x))P(x,y)dxdy \end{aligned}$$

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

对于训练数据集

$$T=\left\{(x_i,y_i)|i\in [1,N]\right\}$$

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

$$R_{\mathrm{emp}}(f)=\frac{1}{N}\sum_{i=1}^NL(y_i,f(x_i))$$

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

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

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

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

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

算法

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

过拟合

正则化

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

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

$$\min\limits_{f\in F}\frac{1}{N}\sum_{i=1}^NL(y_i,f(x_i))+\lambda J(f)$$

正则化项可以采用参数向量的$L_1$或$L_2$范数。

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

交叉验证

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

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

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

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

泛化能力

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

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

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

$$R(f)\leq \widehat{R}(f)+\sqrt{\frac{1}{2N}\log \frac{d}{\delta}}$$

感知机

感知机是二类分类的线性分类模型。输出值为$\left\{+1,-1\right\}$。

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

假设输入空间是$X\subseteq R^n$，输出空间是$Y=\left\{+1,-1\right\}$。输出$x\in X$表示实例的特征向量，对应于输入空间的点，输出$y\in Y$表示实例的类别。由输入空间到输出空间的如下函数：

$$f(x)=\mathrm{sign}(w\cdot x+b)$$

称为感知机。其中$w$和$b$称为感知机模型参数，$w\in R^n$叫做权值向量，$b\in R$叫做偏置。

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

损失函数

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

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

$$\frac{1}{\|w\|}|w\cdot x_0+b|$$

其次对误分类的数据$(x_i,y_i)$来说有：

$$-y_i(w\cdot x_i+b)>0$$

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

$$-\frac{1}{\|w\|}y_i(w\cdot x_i+b)$$

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

$$-\frac{1}{\|w\|}\sum_{x_i\in M}y_i(w\cdot x_i+b)$$

定义损失函数为

$$L(w,b)=-\sum_{x_i\in M}y_i(w\cdot x_i+b)$$

学习算法

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

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

$$\nabla_wL(w,b)=-\sum_{x_i\in M}y_ix_i\\ \nabla_bL(w,b)=-\sum_{x_i\in M}y_i$$

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

$$w\leftarrow w+\eta y_ix_i\\ b\leftarrow b+\eta y_i$$

其中$\eta$是步长（学习率），取值范围为$0<\eta\leq 1$。

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

算法的收敛性

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

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

$$y_i(\widehat{w}_{opt}\cdot \widehat{x}_i)\geq \gamma$$

(2) 令$R=\max\limits_{1\leq i\leq N}\|\widehat{x}_i\|$，则感知机算法在训练数据集上的误分类次数$k$满足不等式：

$$k\leq (\frac{R}{\gamma})^2$$

k近邻法

k近邻法（k-NN)：给定一个训练数据集，训练数据被分到不同的类中。对新的输入，在训练数据集中找到与该实例最近的k个训练实例，这k个实例的多数属于某个类，就把该输入实例分为这个类。

对于输入点$x$，记最近$k$个训练点组成的集合为$N_k(x)$。之后在$N_k(x)$中根据分类决策规则来决定$x$的类别$y$。

当$k=1$的时候是特殊情况，这时候称为最近邻算法。

特征空间中，对每个训练实例点$x_i$，距离该点比其他点更近的所有点组成一个区域叫做单元（cell）。每个训练实例点都有一个单元，所有训练实例点的单元构成对特征空间的一个划分。

距离度量

采用的距离可以是$L_p$距离

$$L_p(x_i,x_j)=(\sum_{l=1}^n|x_i^{(l)}-x_j^{(l)}|^p)^{\frac{1}{p}}$$

$L_1$称为曼哈顿距离，$L_2$称为欧式距离，而$L_\infty$则计算的是所有坐标距离的最大值。

k值选择

如果k值较小，则仅使用较小的邻域进行预测，容易受到噪音点的干扰，发生过拟合。

如果选择较大的k值，这时候较远的点也会对预测起作用，整个模型变得简单。当$k=N$的时候只有一种可能的分类。

分类决策规则

k近邻法中的分类决策规则往往是多数表决，即由输入实例的k个邻近的训练实例的多数类决定输入实例的类。

算法实现

k近邻可以通过kd树来实现高效的搜索。

朴素贝叶斯法

原理

考虑输入空间$X\subseteq R^n$，输出集合$Y=\left\{c_1,\ldots,c_K\right\}$。

设$P(X,Y)$是$X$和$Y$的联合概率分布。训练数据集$T$是由$P(X,Y)$独立同分布产生。

朴素贝叶斯法通过训练数据集学习联合概率分布$P(X,Y)$。具体的，学习以下先验概率分布及条件概率分布。先验概率分布：

$$P(Y=c_k)\\ P(X=x|Y=c_k)=P(X^{(1)}=x^{(1)},\ldots,X^{(n)}=x^{(n)}|Y=c_k)$$

第二个式子我们需要存储$k\prod_{j=1}^nS_j$，其中$S_j$表示$x^{(j)}$中可能的取值数。

朴素贝叶斯法对条件概率分布作了条件独立性的假设。因此有

$$P(X=x|Y=c_k)=\prod_{j}^nP(X^{(j)}=x^{(j)}|Y=c_k)$$

朴素贝叶斯法实际上学到生成数据的机制，所以属于生成模型。

对给定的输入$x$，学习到的后验概率为：

$$\begin{aligned} P(Y=c_k|X=x)&=\frac{P(X=x|Y=c_k)P(Y=c_k)}{\sum_{i}P(X=x|Y=c_i)P(Y=c_i)}\\ &=\frac{P(Y=c_k)\prod_jP(X^{(j)}=x^{(j)}|Y=c_k)}{\sum_{i}P(Y=c_i)\prod_jP(X^{(j)}=x^{(j)}|Y=c_i)} \end{aligned}$$

朴素贝叶斯分类器可以写作：

$$f(x)=\argmax\limits_{c_k}P(Y=c_k|X=x)$$

其中考虑到分母等价于$P(X=x)$，因此我们需要只是最大化分子：

$$f(x)=\argmax\limits_{c_k}P(Y=c_k)\prod_jP(X^{(j)}=x^{(j)}|Y=c_k)$$

后验概率最大化的解释

在使用0-1损失函数的时候，后验概率最大化等价于期望风险最小化。

极大似然估计

要学习$P(Y=c_k)$和$P(X^{(j)}=x^{(j)}|Y=c_k)$。可以使用极大似然估计法估计想要的概率。

$$P(Y=c_k)=\frac{1}{N}\sum_{i=1}^NI(y_i=c_k)$$

条件概率$P(X^{(j)}=a_{j,l}|Y=c_k)$的极大似然估计是

$$P(X^{(j)}=a_{j,l}\|Y=c_k)=\frac{\sum_{i=1}^NI(x_i^{(j)}=a_{j,l},y_i=c_k)}{\sum_{i=1}^NI(y_i=c_k)}$$

学习算法

（1）先计算先验概率

$$P(Y=c_k)\\ P(X^{(j)}=x^{(j)}|Y=c_k)$$

（2）对于给定的实例$x$，获得

$$\argmax\limits_{c_k}P(Y=c_k)\prod_jP(X^{(j)}=x^{(j)}|Y=c_k)$$

贝叶斯估计

用极大似然估计中可能出现概率值为$0$的情况，这时候除法操作是未定义的。

可以用贝叶斯估计来解决这个问题，具体地

$$P_\lambda(X^{(j)}=a_{j,l}\|Y=c_k)=\frac{\sum_{i=1}^NI(x_i^{(j)}=a_{j,l},y_i=c_k)+\lambda}{\sum_{i=1}^NI(y_i=c_k)+S_j\lambda}\\ P_\lambda(Y=c_k)=\frac{\sum_{i=1}^NI(y_i=c_k)+\lambda}{N+K\lambda}$$

其中$\lambda\geq 0$。当$\lambda=0$的时候就是极大似然估计。通常取$\lambda=1$，这时候称为拉普拉斯平滑。这时候有：

$$P_{\lambda}(X^{(j)}=a_{j,l}|Y=c_k)>0\\ \sum_{l=1}^{S_j}P(X^{(j)}=a_{j,l}|Y=c_k)=1$$

决策树

分类决策树模型是一种描述对实例分类的树形结构。决策树由结点和有向边组成。结点分为内部结点和叶结点。内部结点表示一个特征或属性，叶结点表示一个类。

用决策树分类，从根结点开始，对实例的某一特征进行测试，根据测试结果，将实例分配到其子结点。重复测试直到抵达叶结点。

决策树于一个if-then规则集合对应，满足互斥且完备的特性。

决策树还表示概率分布，叶结点的分类表示满足所有内部结点测试的实例最可能属于的分类。

学习算法

给定样本集$D$，其中$n$为特征个数，$Y=\left\{1,\ldots,K\right\}$，$N$为样本容量。

能正确处理样本集的决策树可能有多个，也可能一个没有。在损失函数确定后，我们要选择的是使损失函数最小化的决策树。选择最优决策树是NP完全问题，因此我们采用的是启发式方法，来近似求解。

决策树的构建算法是一个递归的流程。假设我们用一组训练数据构建根结点：

• 如果数据已经被正确分类了，根结点就是叶结点
• 否则找到一个最优的特征，按照这一特征将训练数据分割为子集，使得每个子集都有一个在当前条件下最好的分类。之后对每个子集递归构建决策树。

上面生成的决策树可能对训练数据有很好的分类能力，但是对测试数据不具有很好的分类能力，即发生过拟合。我们需要对树自上向下进行剪枝，使树变得更简单，从而提高泛化能力。具体就是删除内部结点下的所有后代，将其转换为根结点。

决策树生成时只需要考虑局部最优，但是决策树剪枝时考虑的是全局最优。

决策树的生成算法有ID3，C4.5，CART。

特征选择

信息增益

当存在多个可用特征的时候，该选择那个特征进行分类。信息增益用来衡量选择的特征的优劣。

信息增益表示得知特征$X$的信息而使类$Y$的信息的不确定性减少的程度。记$H(X)$表示随机分布$X$的信息熵，$H(Y|X)$表示条件概率下的信息熵。则特征$A$对训练数据$D$的信息增益定义为

$$g(D,A)=H(D)-H(D|A)$$

每次我们选择拥有最大信息增益的特征进行分类。

计算信息增益的算法如下，设选择特征$A$拥有$n$个不同的取值，并将$D$划分为$N$个子集$D_i$。记$D_i$中属于类$C_j$的样本的集合为$D_{i,j}$，则算法如下：

1. 计算数据集$D$的经验熵

$$H(D)=-\sum_{k=1}^K\frac{|C_k|}{|D|}\log_2 \frac{|C_k|}{|D|}$$

1. 计算特征$A$对数据集的经验条件熵

$$H(D|A)=\sum_{i=1}^n\frac{|D_i|}{|D|}H(D_i)$$

1. 计算信息增益

$$g(D,A)=H(D)-H(D|A)$$

信息增益比

使用信息增益作为特征的挑选准则，偏向于选择取值较多的特征的问题。使用信息增益比可以对这一问题进行校正。其定义如下：

$$g_R(D,A)=\frac{g(D,A)}{H_A(D)}$$

其中

$$H_A(D)=-\sum_{i=1}^n\frac{|D_i|}{|D|}\log_2 \frac{D_i}{D}$$

ID3算法

ID3算法用极大似然法进行概率模型的选择。

输入：训练数据集$D$，特征集$A$和阈值$\epsilon$; 输出：决策树$T$。

1. 若$D$中所有实例属于同一类，则$T$为单结点树。并将该类作为该结点的类标记，返回$T$。
2. 若$A=\emptyset$，则$T$为单结点树，并将$D$中实例数最大的类$C_k$作为该结点的标记，返回$T$。
3. 否则，计算不同特征对$D$的信息增益，选择信息增益最大的特征$A_g$。
4. 如果$A_g$的信息增益小于阈值$\epsilon$，则$T$为单结点树，并将$D$中实例数最大的类$C_k$作为该结点的类标记，返回$T$。
5. 否则，对$A_g$的每一可能值$a_i$，依$A_g=a_i$将$D$分割为若干子集，将$D_i$中实例数最大的类作为标记，构建子结点，由结点及其子结点构成树$T$，返回$T$。
6. 对第$i$个子结点，以$D_i$为训练集，以$A-A_g$作为特征集，递归构建决策树。

C4.5算法

C4.5算法与ID3类似，只不过使用信息增益比来选择特征。

剪枝

剪枝是从下向上计算的过程。记$C_\alpha(T)$表示树$T$的损失函数，如果将某个结点转换为叶结点可以得到更小的损失函数，那么就将其转换为叶结点。

设$T$表示决策树的叶子结点集合，对于叶子$t$，记$N_t$表示叶子中样本数，$N_{t,k}$表示叶子中类$C_k$的样本数，决策树的损失函数定义为

$$C_\alpha(T)=\sum_{i=1}^{|T|}N_tH_t(T)+\alpha|T|$$

其中

$$H_t(T)=-\sum_{k}\frac{N_{t,k}}{N_t}\log \frac{N_{t,k}}{N_t}$$

CART算法

分类回归树(CART)既可以用于分类也可以用于回归。

CART用于计算$P(Y|X)$，它假设决策树为二叉树，内部结点特征的取值为“是否”值，左分支代表是，右分支代表否。这时候决策树等价于递归地二分每个特征，将输入空间即特征空间划分为有限个单元，并在这些单元上确定预测的概率分布。

生成决策树时，对回归树用平方误差作为损失函数，对分类树用基尼指数作为损失函数。

生成回归树

假设输入空间被划分为$M$个单元$R_1,\ldots,R_M$，并且在每个单元$R_m$上有一个固定的输出值，于是回归树模型可以表示为

$$f(x)=\sum_{m=1}^Mc_mI(x\in R_m)$$

此时平方误差为

$$\sum_{x_i\in R_m}(y_i-f(x_i))^2$$

易知$c_m$最优值$\widehat{c}_m$正好等于$R_m$上的所有输入实例$x_i$对应的$y_i$的均值。

至于如何选择划分输入空间，这里采用启发式的方法。假设选择的是第$j$个变量$x^{(j)}$和它取得值$s$，作为切分变量和切分点，并定义两个区域：

$$R_1(j,s)=\{x|x^{(j)}\leq s\}, R_2(j,s)=\{x|x^{(j)}>s\}$$

至于寻找最优切分变量$j$和最优切分点$s$，等价于求解

$$\min_{j,s}[\min_{c_1}\sum_{x_i\in R_1(j,s)}(y_i-c_1)^2+\min_{c_2}\sum_{x_i\in R_2(j,s)}(y_i-c_2)^2]$$

生成分类树

分类树用基尼指数作为损失函数。假设有$K$个类，样本点属于第$k$类得概率为$p_k$，则概率分布得基尼指数定义为：

$$Gini(p)=\sum_{k=1}^Kp_k(1-p_k)=1-\sum_{k=1}^Kp_k^2$$

而对于给定的样本集合$D$，其基尼指数为

$$Gini(D)=1-\sum_{k=1}^K(\frac{|C_k|}{|D|})^2$$

如果将样本集合$D$划分为$D_1$和$D_2$两部分，则

$$Gini(D,A)=\frac{|D_1|}{|D|}Gini(D_1)+\frac{|D_2|}{|D|}Gini(D_2)$$

Logistic回归与最大熵模型

Logisitic分布：设$X$是连续随机变量，$X$服从Logistics分布是指$X$具有下列分布函数和密度函数

$$F(x)=P(X\leq x)=\frac{1}{1+e^{-(x-\mu)/\gamma}} f(x)=F'(x)=\frac{e^{-(x-\mu)/\gamma}}{\gamma(1+e^{-(x-\mu)/\gamma})^2}$$

Logistics的分布函数是一条S形曲线，该曲线以点$(\mu,\frac{1}{2})$为中心对称，并且在中心附近增长快，在两端增长速度较慢。

二项Logistic回归模型

二项Logistic回归模型是如下的条件概率分布：

$$P(Y=0|x)=\frac{1}{1+\exp(w\cdot x+b)}\\ P(Y=1|x)=1-P(Y=0|x)$$

Logistic回归比较两个条件概率值得大小，将实例$x$分到概率值较大的分类。

一个事件发生的几率（odds）是指事件发生的概率除上事件不发生的概率。几率的对数值为：

$$\log\frac{P(Y=1|x)}{1-P(Y=1|x)}=w\cdot x$$

线性函数$w\cdot x$越接近无穷，概率趋向于$1$，越接近负无穷，概率越接近$0$。

对于模型参数，可以使用极大似然估计法估计模型参数，设$\pi(x)=P(Y=1|x)$，对于样本集合$T=\left\{(x_1,y_1),\ldots,(x_n,y_n)\right\}$，有似然函数

$$\prod_{i=1}^N[\pi(x_i)]^{y_i}[1-\pi(x_i)] ^{1-y_i}$$

其对数似然函数为：

$$L(w)=\sum_{i=1}^n[y_i(w\cdot x_i)-\log(1+\exp(w\cdot x_i))]$$

多项Logistic回归

假设共有$K$类，则

$$P(Y=k|x)=\frac{\exp(w_k\cdot x)}{1+\sum_{k=1}^{K-1}\exp(w_k\cdot x)},1\leq k< K\\ P(Y=K|x)=\frac{1}{1+\sum_{k=1}^{K-1}\exp(w_k\cdot x)}$$

最大熵模型

最大熵原理是概率模型学习的一个准则：在所有可能的概率模型中，熵最大的模型是最好的模型。

最大熵原理认为在没有足够的信息情况下，那些不确定的部分都是等可能的。