美文网首页
统计学习方法概论

统计学习方法概论

作者: 又双叒叕苟了一天 | 来源:发表于2020-07-16 17:52 被阅读0次

这篇文章是对《统计学习方法》10个监督学习算法的概论和总结。分别是感知机、k近邻法、朴素贝叶斯法、决策树、逻辑斯蒂回归与最大熵模型、支持向量机、提升方法、EM算法、隐马尔可夫模型、条件随机场。

统计学习方法概论

统计学习是关于计算机基于数据构建概率统计模型并运用模型对数据进行预测与分析的一门学科，统计学习也称为统计机器学习。

统计学习的方法

假设数据独立同分布产生，并且假设要学习的模型属于某个函数的集合，称为假设空间；应用某个评价准则，从假设空间选取一个最优的模型，使它对已知训练数据及测试数据在给定的评价准则下有最优的预测；最优模型的选取由算法实现。所以统计学习包含三要素：

  1. 模型：模型的假设空间
  2. 策略：模型选择的准则
  3. 算法：模型学习的算法

监督学习和非监督学习

监督学习的训练数据有标签的标注，非监督学习则没有。

输入空间、特征空间与输出空间

  1. 输入空间\mathcal X：输入x所有可能取值的集合称为输入空间
  2. 特征空间：所有特征向量存在的空间称为特征空间
  3. 输出空间\mathcal Y：输出y所有可能取值的集合称为输出空间

模型的学习都是在特征空间上进行的。通常情况下，输入空间等同于特征空间。但是在有些情况下，通过输入空间无法对数据进行很好的划分，此时需要通过转换将输入空间映射到特征空间，在特征空间上进行学习。例如非线性的支持向量机或者最大熵模型。

回归问题、分类问题与标注问题

  1. 回归问题：输入变量与输出变量均为连续变量的预测问题称为回归问题
  2. 分类问题：输出变量为有限个离散变量的预测问题称为分类问题
  3. 标注问题：输入变量与输出变量均为变量序列的预测问题称为标注问题

联合概率分布

监督学习假设输入与输出随机变量x和Y遵循联合概率分布P(X,Y)。这是监督学习关于数据的基本假设。

统计学习三要素

统计学习的三要素：模型、策略、算法。

模型

模型的假设空间\mathcal F通常有两类表示方式：决策函数f(X)或条件概率P(Y|X)

决策函数：
\mathcal F= \{f|Y=f_\theta(X),\theta\in\textbf R^n\}
条件概率：
\mathcal F= \{P|P_\theta(Y|X),\theta\in\textbf R^n\}
其中\theta是模型参数。由决策函数表示的模型称为非概率模型，由条件概率表示的模型称为概率模型。

策略

学习策略通常是经验风险R_{\mathrm{emp}(f)}最小化或者结构风险最小化。

  1. 期望风险（损失）R_{\mathrm{exp}(f)}：模型关于联合分布的期望损失，这个期望一般求不出，所以转而求经验风险（损失）。
    R_{\mathrm{exp}(f)}=E_{P(X,Y)}[L(Y,f(X))]=\int_{\mathcal X\times\mathcal Y}P(X,Y)L(y,f(X))\mathrm dx\mathrm dy

  2. 经验风险（损失）R_{\mathrm{emp}(f)}：模型在样本上的平均损失。
    R_{\mathrm{exp}(f)}=\frac1N\sum_{i=1}^NL(y_i,f(x_i))

  3. 结构风险（损失）：为了防止过拟合加上正则化的经验损失。
    R_{\mathrm{srm}(f)}=\frac1N\sum_{i=1}^NL(y_i,f(x_i))+\lambda J(f)

极大似然估计是经验风险最小化的一个例子，例如深度学习中定义并最小化损失函数。假设模型是条件概率分布，损失函数是对数损失函数时，经验风险最小化就等价于极大似然估计。

算法

一般指模型的最优化算法，每个模型都不一样。

过拟合和欠拟合

过拟合：在训练集上误差小，但是在测试集上误差大。低偏差，高方差。

欠拟合：在训练集和测试集上误差都很大。高偏差，低方差。

正则化

对模型参数复杂度的一个惩罚。通常使用模型参数w的L1范数或者L2范数。
L(w)=\frac1N\sum_{i=1}^N(f(x_i;w)-y_i)^2+\frac\lambda2||w||^2

L(w)=\frac1N\sum_{i=1}^N(f(x_i;w)-y_i)^2+|w|

S折交叉验证

把样本分成S份，留一份用于测试，其余S-1份用于测试。这样，测试样本的选取有S个可能，将S次测试结果平均，作为最终的测试结果。留一交叉验证是S折交叉验证的特例，每个样本为一折。

生成模型与判别模型

  1. 判别模型：直接学习f(X)和P(Y|X)的参数的模型。常见的判别模型有：k近邻法、感知机、决策树、逻辑斯谛回归、最大熵模型、支持向量机、提升方法和条件随机场。
  2. 生成模型：学习联合分布P_\theta(X,Y)的参数，然后通过P(Y|X)=\frac{P(X,Y)}{P(X)}，进行预测的模型。常见的生成模型有：朴素贝叶斯法和隐马尔可夫模型。

一、感知机

具体可以查看《统计学习方法》第二章或统计机器学习-感知机。

感知机是二分类的线性分类模型，即通过一个超平面将数据集分割在两侧，同在一个侧的为同一个分类，一般上侧的为正例，下侧的为负例。模型直接学习f_\theta(X)的参数，给出分类。

感知机的定义

感知机的决策函数为：
f(x)=\mathrm{sign}(w\cdot x+b)
其中，w和b为感知机模型参数，w\in\textbf R^n叫做权值或权值向量，b\in\textbf R叫做偏置，w\cdot x表示w和x的内积，\mathrm{sign}是符号函数。

感知机的损失函数

损失定义为误分类点到超平面的距离之和：
L(w,b)=-\frac1{||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)

感知机的学习算法

通常采用梯度下降算法，该梯度下降分为原始形式和对偶形式，对偶形式通过\mathrm{Gram}矩阵加速优化。具体可以查看《统计学习方法》第二章或统计机器学习-感知机。

二、k近邻法

k近邻法既可以用于分类，也可以用于回归，这里只讨论分类的k近邻法。k近邻法的思路是：给定一个输入，在训练集中找出k个最相近的实例，然后分到这k个实例大多数归属的一个类。

k近邻法包含三个要素：

  1. k值的选择

  2. 距离度量（如欧氏距离、曼哈顿距离等等）

  3. 分类决策规则（如多数表决）

具体可以查看《统计学习方法》第三章或统计机器学习-k近邻法。

k近邻算法

  1. 根据给定的距离度量，在训练集T中找出与x最邻近的k个点，涵盖这k个点的x的领域记做N_k(x)；

  2. 在N_k(x)中根据分类决策规则（如多数表决）决定x的类别y：

y=\arg\max_{c_j}\sum_{x_i\in N_k(x)}I(y_i=c_k), \ \ i=1,2,\cdots,N;\ \ j=1,2,\cdots,K
其中I是指示函数，当y_i=c_j时为1，否则为0。

k近邻法的三个要素

k值的选择、距离度量（如欧氏距离、曼哈顿距离等等）、分类决策规则（如多数表决）。

k值的选择

k值的选择会对k近邻法的结果产生重大影响。一般k越小代表模型变复杂，容易出现过拟合（低偏差，高方差），尤其是当近邻点是噪声点时，预测就会出错。k越大，模型越简单。当k等于样本数N时，模型最简单，但是忽略了样本中大量的有用信息。在应用中，k值一般取一个较小的数值，然后采用交叉验证法来选取最优的k值。

距离度量

距离可以选择如下度量方式：

  1. L_p距离：
    L_p(x_i,x_j)=\bigg(\sum_{l=1}^n|x_i^{(l)}-x_j^{(l)}|^p\bigg)^{\frac1p}

  2. 欧氏距离（L_2距离）：
    L_2(x_i,x_j)=\bigg(\sum_{l=1}^n|x_i^{(l)}-x_j^{(l)}|^2\bigg)^{\frac12}

  3. 曼哈顿距离（L_1距离）：
    L_1(x_i,x_j)=\sum_{l=1}^n|x_i^{(l)}-x_j^{(l)}|

分类决策规则

通常使用多数表决规则，即有输入实例的k个邻近的训练实例中的多数类决定输入实例的类。多数表决相当于经验风险最小化。

kd树

k近邻法需要计算输入实例和训练集中所有实例的距离。当训练集很大时，如果采用线性扫描的方式，是十分费时的。为了提高效率，对训练样本可以采用树结构存储，减少计算距离的次数。kd树是平衡二叉搜索（排序）树，即左子树小于右子树，且任意子树高度差小于等于1。构造和搜索方法，具体可以查看《统计学习方法》第三章或统计机器学习-k近邻法。

三、朴素贝叶斯法

朴素贝叶斯法首先学习输入/输出的联合概率分布P(Y|X)。然后基于此模型给定的输入x，利用贝叶斯定理求出后验概率最大的输出y，即概率最大的P(y|X=x)。具体可以查看《统计学习方法》第四章或统计机器学习-朴素贝叶斯法

条件独立性假设

由于P(y|X=x)需要计算每个分类的概率：
P(y=c_k|X=x)=\frac{P(X=x,Y=c_k)}{P(X=x)}
其中分布可以通过P(X=x)在训练样本中的经验分布获得其参数，但是统计分子
P(X=x|Y=c_k)=P(X^{(1)}=x^{(1)},\cdots,X^{(n)}=x^{(n)}|Y=c_k)\\
是不可行的。所以朴素贝叶斯做出如下条件独立性假设：
\begin{align} P(X=x|Y=c_k)&=P(X^{(1)}=x^{(1)},\cdots,X^{(n)}=x^{(n)}|Y=c_k)\\ &=\prod_{j=1}^nP(X^{(j)}=x^{(j)}|Y=c_k),\ \ k=1,2,\cdots,K \end{align}
其中P(X^{(j)}=x^{(j)}|Y=c_k)可以通过样本中统计的方式学到经验分布。

朴素贝叶斯算法

在样本中通过统计的方式，计算先验概率P(Y=c_k)和条件概率的P(X^{(j)}=a_{jl}|Y=c_k)的经验分布。然后给定实例x=(x^{(1)},x^{(2)},\cdots,x^{(n)})^T，计算：
P(Y=c_k)=\prod_jP(X^{(j)}=x^{(j)}|Y=c_k),\ \ k=1,2,\cdots,K
选择概率最大的分类作为预测。原因是根据P(y=c_k|X=x)=\frac{P(X=x,Y=c_k)}{P(X=x)}，给定x，其分母都是相同的，所以只需考虑分子。

贝叶斯估计

在训练数据集中，可能出现P(X^{(j)}=x^{(j)}|Y=c_k)=0的情况，即样本中这种情况一次都没有出现，这样会造成P(Y=c_k)\prod_jP(X^{(j)}=x^{(j)}|Y=c_k)=0，使分类产生偏差。解决这个问题的方法是贝叶斯估计，即在统计P(Y=c_k)和P(X^{(j)}=x^{(j)}|Y=c_k)时加入一个平滑
P_\lambda(X^{(j)}=x^{(j)}|Y=c_k)=\frac{\sum_{i=1}^NI(x_i^{(j)}=a_{jl},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\gt0，可以看出，此时P_\lambda(Y=c_k)和P_\lambda(X^{(j)}=x^{(j)}|Y=c_k)仍是符合概率分布的。\lambda通常取1，这时称为拉普拉斯平滑。

四、决策树

决策树是一种基本的分类与回归方法。ID3和C4.5决策树可以用于分类，CART（分类与回归树）既可以用于分类，也可以用于回归。决策树的学习通常包括3个步骤：特征选择、决策树的生成和决策树的修剪。这里主要介绍分类决策树。决策树学习的是条件概率P(Y|X)的参数，具体可以查看《统计学习方法》第五章或统计机器学习-决策树。

决策树的定义

分类决策树模型是一种描述对实例进行分类的树形结构，决策树由结点和有向边组成。结点由两种类型：内部结点和叶结点。内部结点表示一个特征或属性，叶结点表示一个类。由决策树的根结点到叶结点的每一条路径构建一条规则：路径上内部结点的特征对应着规则的条件，而叶结点的类对应着规则的结论。决策树的路径对应的规则互斥且完备，每一个实例都只被一条路径所覆盖。

决策树学习的三个步骤

特征选择、生成、剪枝。

  1. 特征选择：选择一个特征对当前样本进行划分
  2. 生成：生成一棵决策树
  3. 剪枝：删减生成决策树的一些子树，减少模型复杂度，提高模型泛化能力

特征选择

通常选信息增益（比）最大的特征作为依据对当前训练集进行划分，生成子树。

信息增益：
g(D,A)=H(D)-H(D|A)
其中H(X)和H(Y|X)分别是信息熵和条件熵，D是数据集，A是特征集合：
H(X)=-\sum_{i=1}^nP(X=x_i)\log P(X=x_i)

H(Y|X)=\sum_{i=1}^nP(X=x_i)H(Y|X=x_i)

信息增益比：
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生成算法和C4.5生成算法，区别在于ID3使用信息增益最大选择划分的特征，而C4.5使用信息增益比最大。

决策树的剪枝

剪枝根据最小化损失：
C_\alpha(T)=C(T)+\alpha|T|
上式中C(T)表示模型对训练数据的预测误差，|T|表示模型复杂度。参数\alpha控制两者之间的影响，较大的\alpha促使选择简单的模型，较小的\alpha促使选择复杂的模型，\alpha=0表示不考虑模型复杂度。该损失函数的极小化等价于正则化的极大似然估计。

CART算法

CART是分类与回归树的简写，即既可以实现分类，也可以实现回归的树。CART是二叉树，内部结点有两个分支，左边是“是”，右边是“否”，对特征进行递归的二分。

CART算法由以下两步组成：

  1. 决策树生成：基于训练数据集生成决策树，生成的决策树要尽量大；

  2. 决策树剪枝：用验证数据集对已生成的树进行剪枝并选择最优子树，这时用损失函数最小作为剪枝的标准。

（最小二乘）回归树的生成

使用平方误差最小寻找切分的特征和切分点。

分类树的生成

使用切分后基尼指数最小的特征进行切分。即：
\mathrm{Gini}(D,A)=\frac{|D_1|}{|D|}\mathrm{Gini}(D_1)+\frac{|D_2|}{|D|}\mathrm{Gini}(D_2)
最小。基尼指数\mathrm{Gini}(D)表示集合D的不确定性，基尼指数越大，不确定性越高，和熵有相似的性质。基尼指数\mathrm{Gini}(D,A)表示按特征A=a划分后的不确定性。

CART剪枝

对每个内部结点计算
\alpha=g(t)=\frac{C(t)-C(T_t)}{|T_t|-1}
每次，选择g(t)最小的子树不断剪枝得到子树序列T_0,T_1,\cdots,T_n，然后用验证集验证选择最优。

五、逻辑斯谛回归与最大熵模型

逻辑斯谛回归（逻辑回归）模型，是统计学习中的经典分类方法。最大熵是概率模型学习的一个准则，推广到分类问题得到最大熵模型。逻辑斯谛回归和最大熵模型都属于对数线性模型。逻辑斯谛回归学习的是条件概率P(Y|X)的参数，具体可以查看《统计学习方法》第六章或统计机器学习-逻辑斯谛回归与最大熵模型。

逻辑斯谛回归

二项逻辑斯谛回归

二项逻辑斯谛回归模型是如下的条件概率分布：
P(Y=1|x)=\frac{\exp(w\cdot x+b)}{1+\exp(w\cdot x+b)}

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

这里，x\in\textbf R^n是输入，Y= \{0,1\}是输出，w\in\textbf R^n和b\in\textbf R是参数，w称为权值向量，b称为偏置，w\cdot x为w和x的内积。

二项逻辑斯谛回归的参数估计

似然函数为：
\prod_{i=1}^N\bigg[[\pi(x_i)]^{y_i}[1-\pi(x_i)]^{1-y_i}\bigg]
对数似然函数为：
L(w)=\sum_{i=1}^N\bigg[y_i(w\cdot x_i)-\log(1+\exp(w\cdot x_i))\bigg]
通过极大似然估计求解参数w。主要的方法是梯度下降，具体可以查看统计机器学习-梯度下降法。

多项逻辑斯谛回归

多分类的多项逻辑斯谛回归模型，假设随机变量Y的取值集合是\{1,2,\cdots,K\}，其概率分布为：
P(Y=k|x)=\frac{\exp(w_k\cdot x)}{1+\sum_{k=1}^{K-1}(w_k\cdot x)},\ \ k=1,2,\cdots,K-1

P(Y=K|x)=\frac1{1+\sum_{k=1}^{K-1}(w_k\cdot x)}

类似的，其似然函数为N个样本中每个x_i预测为标签y_i概率的乘积。

最大熵模型

最大熵原理是概率模型学习的一个准则。最大熵原理认为，学习概率模型时，在所有可能的概率模型中，熵最大的模型是最好的模型。最大熵原理是选择模型的思想，将其应用到分类模型就叫做最大熵模型。其中熵：
H(P)=-\sum_xP(x)\log P(x)
熵代表了X的不确定性。对未知的变量，给予它每个取值相同的概率，此时不确定最大，熵也最大，并且这种假设也是合理的。

最大熵模型的定义

最大熵模型是指在满足已知的约束下，熵最大的分类的模型。例如：假设随机变量X有5个取值\{A,B,C,D,E\}，并且已知P(A)+P(B)=\frac3{10}，要求各个取值的概率。根据最大熵原理，P(A)=P(B)=\frac3{20}，P(C)=P(D)=P(E)=\frac7{30}。

约束的定义通过特征函数f(x,y)表示：
f(x,y)= \begin{cases} 1,&x与y满足某一事实\\ 0,&否则 \end{cases}
如果模型能够获取训练数据中的信息，那么就可以假设下面两个期望（特征函数关于联合分布P(X,Y)和联合分布的经验分布P(X,Y)的期望）相等：
E_{P(X,Y)}(f(x,y))=E_{\tilde P(X,Y)}(f(x,y))
于是，在这些约束下选择条件熵H(P(Y|X))最大的模型：
\max_{P\in\mathcal C}\ \ H(P)=-\sum_{x,y}[\tilde P(x)P(y|x)\log P(y|x)]
可以表述为以下最优化问题：

\min_{P\in\mathcal C}\ \ -H(P)=\sum_{x,y}[\tilde P(x)P(y|x)\log P(y|x)]

\mathrm{s.t.}\ \ E_P(f_i)=E_{\tilde P}(f_i),\ \ i=1,2,\cdots,n

\sum_yP(y|x)=1\tag{14}\sum_yP(y|x)=1

通过拉格朗日对偶性，转为求解对偶问题。得到对偶问题的解后，代入拉格朗日函数，得到最大熵模型的形式：
\max_w\Psi(w)=\max_wL(P_w,w)
其中P_w：
P_w(y|x)=\frac1{Z_w(x)}\exp\bigg(w_if_i(x,y)\bigg)

Z_w(x)=\sum_y\exp\bigg(\sum_{i=1}^nw_if_i(x,y)\bigg)

这个形式和逻辑斯谛回归相同，都是对数线性模型，即对数几率\log\frac p{1-p}为线性模型。这个问题可以通过IIS算法（迭代极大化似然函数增量的下界），或者梯度下降法（取反转化为凸函数极小化问题）、拟牛顿法求解。

六、支持向量机

考虑一个二分类问题。假设输入空间与特征空间为两个不同的空间。输入空间为欧氏空间或离散集合，特征空间为欧式空间或希尔伯特空间。线性可分支持向量机、线性支持向量机假设这两个空间的元素一一对应，并将输入空间中的输入映射为特征空间中的特征向量。非线性支持向量机利用一个从输入空间到特征空间的非线性映射将输入映射为特征向量（核技巧）。支持向量机的学习是在特征空间进行的。具体可以查看《统计学习方法》第七章。

线性可分支持向量机、线性支持向量机处理的样本在输入空间上就通过线性划分，所以输入空间和特征空间一一对应。非线性支持向量机处理的样本在输入空间上不可以线性划分，所以需要通过映射函数从输入空间映射到特征空间使其在特征空间上可以线性划分，最终转化成线性可分支持向量机、线性支持向量机的形式。

线性可分支持向量机

假设数据线性可分（用一个超平面可以将正负例完全正确的划分在超平面两侧），学习的目的是找到一个超平面：
w^*\cdot x+b^*=0
对于一个新的输入x的分类决策函数为：
f(x)=\mathrm{sign}(w^*\cdot x+b^*)
满足条件的这样的超平面可能有很多个，但是支持向量机通过几何间隔在超平面的选择上加上了约束，即最大化几何间隔，使最后得到的超平面是唯一的。具体可以查看统计机器学习-线性可分支持向量机与硬间隔最大化。

函数间隔

一般来说，一个样本点到超平面的距离代表了支持向量机对这个样本分类的确信程度。由于当超平面确定，点到平面的距离公式
\frac {|w\cdot x+b|}{||w||}
的分母为一个常量，所以确信程度的大小由分子|w\cdot x+b|决定。于是定义样本点(x_i,y_i)的函数间隔：
\hat \gamma_i=y_i(w\cdot x_i+b)
对于T中所有样本的函数间隔：
\hat \gamma=\min_{i=1,\cdots N}\hat\gamma_i
当超平面能够完全分类正确时y_i(w\cdot x_i+b)\geq0，所以函数间隔代表确信程度最小样本的确信程度，最大化函数间隔就等于最大化支持向量机对样本分类的确信程度。在线性可分支持向量机中，这也成为硬间隔最大化。

几何间隔

由于对参数w和b成比例缩放，就可以改变函数间隔\hat\gamma的大小，但这仍然表示同一个超平面。所以对提出几何间隔\gamma对w规范化：
\gamma_i=\frac{\hat \gamma_i}{||w||}

\gamma=\frac{\hat \gamma}{||w||}

||w||代表w的L2范数。

线性可分支持向量机的最优化问题

线性可分支持向量机可以表示为以下最优化问题，即极大化几何间隔（提高分类确信程度）：
\max_{w,b}\gamma

\mathrm{s.t.}\ \ y_i(\frac{w}{||w||}\cdot x_i+\frac{b}{||w||})\geq\gamma,\ \ i=1,2,\cdots,N

转化为以下最优化问题：
\min_{w,b}\ \ \frac12||w||^2

\mathrm{s.t.}\ \ 1-y_i(w\cdot x_i+b)\leq0,\ \ i=1,2,\cdots,N

通过拉格朗日对偶性，转化为极大极小问题：
\max_\alpha\min_{w,b}L(w,b,a)
其中：
L(w,b,a)=\frac12||w||^2-\sum_{i=1}^N\alpha_iy_i(w\cdot x_i+b)+\sum_{i=1}^N\alpha_i
为拉格朗日函数。求解内部极小问题的解w^*,b^*后，代入得到外部极大化问题：
\min_\alpha\frac12\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)+\sum_{i=1}^N\alpha_i

\mathrm{s.t.}\ \ \sum_{i=1}^N\alpha_iy_i=0

\alpha_i\geq0,\ \ i=1,2,\cdots,N

线性可分支持向量机解的形式

w^*=\sum_{i=1}^N\alpha_i^*y_ix_i

b^*=y_j-\sum_{i=1}^N\alpha_i^*y_i(x_i\cdot x_j)

分离超平面
w^*\cdot x+b^*=0
分类决策函数：
f(x)=\mathrm{sign}(w^*\cdot x+b^*)

间隔边界

支持向量是使约束条件公式1-y_i(w\cdot x_i+b)\leq0,\ \ i=1,2,\cdots,N等号成立的点，即
w\cdot x_i+b=y_i
对于正例y_i=+1，支持向量在超平面
H_1:w\cdot x+b=1
对于负例y_i=-1，支持向量在超平面
H_2:w\cdot x+b=-1
如图所示

间隔边界

落在H_1和H_2上的实例点称为支持向量，H_1和H_2之间的距离称为间隔，H_1和H_2称为间隔边界。在决定超平面时，只有支持向量起作用，所以这种模型叫做支持向量机。

支持向量

根据解的公式
w^*=\sum_{i=1}^N\alpha_i^*y_ix_i
可以知道对w^*的结果有影响的样本点(x_i,y_i)，其\alpha_i^*\neq0，又因为\alpha_i^*\geq0，所以\alpha_i^*\gt0，根据KKT条件：
\alpha_i^*g_i(w^*)=\alpha_i^*(1-y_i(w^*\cdot x_i+b^*))=0
所以
1-y_i(w^*\cdot x_i+b^*)=0
这样的样本点落在间隔边界上
w^*\cdot x_i+b^*=\pm1

线性支持向量机

假设给定一个特征空间上的训练数据集
T= \{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)\}
其中，x_i\in\mathcal X=\textbf R^n，y_i\in\mathcal Y= \{+1,-1\}，i=1,2,\cdots,N，x_i为第i个特征向量，也称为实例，y_i为x_i的类标记，当y_i=+1时，称x_i为正例；当y_i=-1时，称x_i为负例，(x_i,y_i)称为样本点。再假设训练数据集不是线性可分的。通常情况是，训练数据中有一些特异点，将这些特异点除去后，剩下大部分的样本点组成的集合是线性可分的。

线性不可分意味着某些样本点(x_i,y_i)不能满足函数间隔大于等于1的约束条件。为了解决这个问题，可以对每个样本点(x_i,y_i)引进一个松弛变量\xi_i\geq0，使函数间隔加上松弛变量大于等于1。这样，约束条件变为
1-\xi_i-y_i(w\cdot x_i+b)\leq0
目标函数由原来的最小化\frac12||w||^2变成最小化
\frac12||w||^2+C\sum_{i=1}^N\xi_i
C是对误分类的惩罚，C越大，对误分类惩罚越大。相对于线性可分支持向量机的硬间隔最大化，这叫做软间隔最大化。具体可以查看统计机器学习-线性支持向量机与软间隔最大化。

线性支持向量机学习算法

类似线性可分支持向量机，可以使用拉格朗日对偶性，通过求解对偶问题的解来得到原始问题的解。

其解的形式：
w^*=\sum_{i=1}^N\alpha_i^*y_ix_i

b^*=y_j-\sum_{i=1}^Ny_i\alpha_i^*(x_i\cdot x_j)

求得分离超平面
w^*\cdot x+b^*=0
分类决策函数：
f(x)=\mathrm{sign}(w^*\cdot x)+b^*

支持向量

由公式
w^*=\sum_{i=1}^N\alpha_i^*y_ix_i
得知\alpha_i^*\neq0的样本点x_i能够影响支持向量机的参数。而0\leq\alpha_i^*\leq C，所以支持向量为0\lt\alpha_i^*\leq C的样本点x_i。这些支持向量分布在间隔边界上、间隔边界与分离超平面之间或者在分离超平面误分一侧。若\alpha_i^*\lt C，则\xi_i=0（由KKT条件可以推出，由于\xi^*的结果不影响分离超平面，所以一般也不去算，其计算过程略），支持向量恰好落在间隔边界上；若\alpha_i^*=C，0\lt\xi_i\lt1，则分类正确，支持向量在间隔边界与分离超平面之间；若\alpha_i^*=C，\xi_i=1，则x_i在分离超平面上；若\alpha_i^*=C，\xi_i\gt1，则x_i在分离超平面误分一侧。

合页损失函数

线性支持向量机的学习还等价于最小化以下目标函数：
\min_{w,b}\sum_{i=1}^N[1-y_i(w\cdot x_i+b)]_++\lambda||w||^2
其中目标函数的第一项是经验损失或经验风险，函数
L(y(w\cdot x+b))=[1-y(w\cdot x+b)]_+
称为合页损失函数。下标"+"表示ReLU函数，由于函数形状像一个合页，故名合页损失函数。合页损失函数相比感知机的0-1损失，不仅要求分类正确，还要求确信度足够高时（函数间隔大于等于1）损失才是0，所以支持向量机的学习比感知机有更高的要求。

非线性支持向量机

非线性支持向量机在输入空间上不可分，通过映射z=\phi(x)将输入映射到特征空间，在特征空间上类似线性支持向量机进行学习。具体可以查看统计机器学习-非线性支持向量机。

非线性支持向量机的解

\sum_{i=1}^N\alpha_i^*y_iK(x_i,x)

b^*=y_j-\sum_{i=1}^N\alpha_i^*y_iK(x_i\cdot x_j)

其中K(x,z)是正定核函数。

决策函数
f(x)=\mathrm{sign}\bigg(\sum_{i=1}^N\alpha_i^*y_iK(x_i,x)+b^*\bigg)

核函数（正定核）

上式只需计算核函数K(x,z)而无需知道具体的映射函数\phi(x)。那么如何判断一个函数是否具备这样的的映射函数\phi(x)满足核函数的要求呢？我们可以根据核函数的充要条件判断：

设K:\mathcal X\times\mathcal X\rightarrow\textbf R是对称函数，则K(x,z)为正定核函数的充要条件是对任意x_i\in\mathcal X，i=1,2,\cdots,m，K(x,z)对应的\mathrm{Gram}矩阵：
K=[K(X_i,X_j)]_{m\times m}
是半正定矩阵。所以核函数也叫正定核函数。

常用的核函数

多项式核函数

K(x,z)=(x\cdot z+1)^p

高斯核函数

K(x,z)=\exp\bigg(-\frac{||x-z||^2}{2\sigma^2}\bigg)

字符串核函数

k_n(s,t)=\sum_{u\in\Sigma^n}[\phi_n(s)]_u[\phi_n(t)]_u=\sum_{u\in\Sigma^n}\sum_{(i,j):s(i)=t(j)=u}\lambda^{l(i)}\lambda^{l(j)}

计算字符串s和t的相似程度。

序列最小最优化算法

通过对偶问题求解支持向量机的参数，都需要计算最优解\alpha^*=(\alpha_1^*,\alpha_2^*,\cdots,\alpha_N^*)。通过解析求解是很困难的，而序列最小最优化算法（SMO）算法通过迭代方式，逐步更新\alpha^*=(\alpha_1^*,\alpha_2^*,\cdots,\alpha_N^*)的值，使其满足KKT条件，从而得到最优解。同时优化所有参数是很复杂的，SMO的思路是每次只选择两个变量进行优化。选择的标准是：外层循环在训练样本中选取违反KKT条件最严重的样本点，并将其对应的变量作为第1个变量\alpha_1，内层循环选择标准是希望能使\alpha_2有足够大的变化。具体可以查看统计机器学习-序列最小最优化算法（SMO）。

七、提升方法

提升方法的思路就是学习多个分类器，对多个分类器进行线性组合，提高分类的性能。首先定义强可学习和弱可学习。如果存在一个多项式的学习算法可以学习一个分类，并且正确率很高，则称为强可学习。如果一个多项式的学习算法可以学习一个分类，并且正确率相比随机猜测要略好，那么称为弱可学习。事实上，两者是等价的，即一个问题弱可学习，则可以强可学习。提升方法的目标就是组合弱分类器，使其称为一个强分类器。大多数的提升方法都是改变训练数据的概率分布（训练数据的权值分布），针对不同的训练数据分布调用弱学习算法学习一系列弱分类器。具体可以查看《统计学习方法》第八章或统计机器学习-提升方法。

提升方法需要解决两个问题：

  1. 每一轮如何改变训练数据的权值或概率分布

  2. 如何将若分类器组合成一个强分类器

Adaboost算法

对于上述两个问题，Adaboost（适应性提升方法）的做法是：

  1. 训练数据被分类错误，权值上升，被分类正确，权值下降

  2. 加权多数表决，误差率越小，权值越高

回归提升树

在每一步使用一棵回归树T(x;\Theta_m)拟合预测样本的残差（均方损失情况下）。通过M步得到回归提升树：
f_M(x)=\sum_{m=1}^MT(x;\Theta_m)

梯度提升

在每一步使用一棵回归树T(x;\Theta_m)拟合预测样本的残差的近似，即损失函数的负梯度：
-\bigg[\frac{\partial L(y,f(x_i))}{\partial f(x_i)}\bigg]_{f(x)=f_{m-1}(x)}
通过M步得到回归提升树。

八、EM算法

EM算法用于含有隐变量的概率模型参数的极大似然估计。这里首先对隐变量解释，举下面的例子

（三硬币模型）假设有3枚硬币，分别记做A，B，C，这些硬币正面出现的概率分别是\pi，p和q。进行如下掷硬币试验：先掷硬币A，根据其结果选出硬币B或硬币C，正面选硬币B，反面选硬币C；然后掷选出的硬币，掷硬币的结果，出现正面记做1，出现反面记做0；独立的重复n次试验（这里，n=10），观测结果如下：
1,1,0,1,0,0,1,0,1,1
假设能观测到掷硬币的结果，不能观测掷硬币的过程，问如何估计三硬币正面出现的概率，即三硬币模型的参数\pi，p和q。

其中掷硬币A的结果是未观测的，叫做隐变量，记做z。将观测数据表示为Y=(Y_1,Y_2,\cdots,Y_n)^T，未观测数据表示为Z=(Z_1,Z_2,\cdots,Z_n)^T，则观测数据的似然函数为
P(Y|\theta)=\sum_ZP(Y,Z|\theta)=\sum_ZP(Z|\theta)P(Y|Z,\theta)\tag1
即
P(Y|\theta)=\prod_{j=1}^n[\pi p^{y_j}(1-p)^{1-y_i}+(1-\pi)q^{y_j}(1-q)^{1-y_j}]\tag2
对模型参数\theta=(\pi,p,q)进行极大似然估计，即
\hat\theta=\arg\max_\theta\log P(Y|\theta)\tag3
因为掷硬币A的结果未知，所以没有这个问题解析解，只能通过迭代的方式，逐步增加对数似然函数，找到一个解。EM算法解决的就是这样的一类问题。具体可以查看《统计学习方法》第九章或统计机器学习-EM算法（期望极大算法）。

EM算法的推出

EM算法叫做Exception maximization算法，顾名思义，包含求期望（Exception ）和极大化（maximization）两个步骤。

  1. E步：记\theta^{(i)}为第i次迭代参数\theta的估计值，在第i+1次迭代的E步，计算
    \begin{align} Q(\theta,\theta^{(i)})&=E_Z[\log P(Y,Z|\theta)|Y,\theta^{(i)}]\\ &=\sum_ZP(Z|Y,\theta^{(i)})\log P(Y,Z|\theta) \end{align}
    这里P(Z|Y,\theta^{(i)})是在给定观测数据Y和当前参数估计\theta^{(i)}下隐变量数据Z的条件概率分布；

  2. M步：求使Q(\theta,\theta^{(i)})极大化的\theta，确定第i+1次迭代的参数的估计值\theta^{(i+1)}
    \theta^{(i+1)}=\arg\max_\theta Q(\theta,\theta^{(i)})

Q函数是Y关于参数\theta的对数似然函数的下界：
L(\theta)=\log P(Y|\theta)=\log\sum_ZP(Y,Z|\theta)=\log\bigg(\sum_ZP(Y|Z,\theta)P(Z|\theta)\bigg)\geq Q(\theta,\theta^{(i)})
所以，在EM算法中最大化Q函数，就等同于最大对数似然函数的下界，从而进行极大似然估计。但是这种算法并不能保证找到全局最优值。

九、隐马尔可夫模型

隐马尔可夫模型（HMM）是用于标注问题的统计学习模型，描述由隐藏的马尔科夫链随机生成观测序列的过程，属于生成模型。隐马尔可夫模型在语音识别、自然语言处理、生物信息、模式识别等领域有着广泛的应用。具体可以查看《统计学习方法》第十章或统计机器学习-隐马尔可夫模型。

隐马尔可夫模型的定义

隐马尔可夫模型由初始状态概率向量\pi，状态转移概率矩阵A和观测概率矩阵B决定。\pi和A决定状态序列，B决定观测序列。因此隐马尔可夫模型\lambda可以用三元符号表示，即
\lambda=(A,B,\pi)
隐马尔可夫模型做了两个基本假设：

  1. 齐次马尔可夫性假设，即假设隐藏的马尔可夫链在任意时刻t的状态只依赖于其前一时刻的状态，与其他时刻的状态及观测无关，也与时刻t无关。（当前状态只依赖上个状态，而与再前面的状态无关）
    P(i_t|i_1,o_1,\cdots,i_{t-1},o_{t-1})=P(i_t|i_{t-1}),\ \ t=1,2,\cdots,T

  2. 观测独立性假设，即假设任意时刻的观测只依赖于该时刻的马尔可夫链的状态，与其他观测及状态无关。（每个时刻的观测只依赖于当前时刻的状态）

P(o_t|i_1,o_1,\cdots,i_{t-1},o_{t-1},i_t,i_{t+1},i_{t+1},\cdots,i_T,o_T)=P(o_t|i_t)

隐马尔可夫模型的3个基本问题

  1. 概率计算问题。给定模型\lambda=(A,B,\pi)和观测序列O=(o_1,o_2,\cdots,o_T)，计算在模型\lambda下观测序列O出现的概率P(O|\lambda)。

  2. 学习问题。已知观测序列O=(o_1,o_2,\cdots,o_T)，估计模型\lambda=(A,B,\pi)参数，使得在该模型下观测序列概率P(O|\lambda)最大。即用极大似然估计的方法估计参数。

  3. 预测问题，也称为解码问题。已知模型\lambda=(A,B,\pi)和观测序列O=(o_1,o_2,\cdots,o_T)，求对给定观测序列条件概率P(I|O)最大的状态序列I=(i_1,i_2,\cdots,i_T)。即给定观测序列，求最有可能的对应状态序列。

三个问题都有各自的算法。

概率计算法

解决的是第一个问题：概率计算问题。给定模型\lambda=(A,B,\pi)和观测序列O=(o_1,o_2,\cdots,o_T)，计算在模型\lambda下观测序列O出现的概率P(O|\lambda)。通常的计算方法有直接计算法（事实上不太可行）、前向-后向算法。

学习算法

解决的是第二个问题：学习问题。已知观测序列O=(o_1,o_2,\cdots,o_T)，估计模型\lambda=(A,B,\pi)参数，使得在该模型下观测序列概率P(O|\lambda)最大。即用极大似然估计的方法估计参数。该问题分为无监督和监督学习两种方式。在状态序列标注的情况下，可以使用无监督方式，但是情况通常是不知道状态序列，这时候就需要通过无监督学习的方式，估计模型参数。无监督学习的算法叫做Baum-Welch算法，是EM算法在隐马尔可夫模型中的具体应用。

预测算法

解决的是第二个问题：预测问题，也称为解码问题。已知模型\lambda=(A,B,\pi)和观测序列O=(o_1,o_2,\cdots,o_T)，求对给定观测序列条件概率P(I|O)最大的状态序列I=(i_1,i_2,\cdots,i_T)。即给定观测序列，求最有可能的对应状态序列。可是使用近似算法和维特比算法。

  1. 近似算法：缺点是没有考虑整个序列，如果存在转移概率a_{ij}=0，序列q_j,q_i是不可能出现的，但是依然会存在这样的预测。
  2. 维特比算法：采用动态规划思想，划分子问题，逐步取最优。

十、条件随机场

条件随机场是给定一组输入随机变量条件下另一组随机变量的条件概率分布模型P(Y|X)，其特点是假设输出随机变量构成马尔可夫随机场。类似隐马尔可夫模型，条件随机场也有概率计算问题，学习问题和预测问题。具体可以查看《统计学习方法》第十一章或统计机器学习-条件随机场。

条件随机场和概率无向图

条件随机场模型P(Y|X)其实是有输入变量X决定的Y的一个概率无向图：

条件随机场

没有连线的两个随机变量之间独立。条件随机场为了简化问题，通常使用链式的条件随机场：

线性链条件随机场

每个随机变量Y_i只依赖于有边相连接的随机变量Y_{i-1}，Y_{i+1}。

线性链条件随机场的参数化形式

设X=(X_1,X_2,\cdots,X_n)，Y=(Y_1,Y_2,\cdots,Y_n)均为线性链表示的随机变量序列，若在给定随机变量序列X的条件下，随机变量序列Y的条件概率分布P(Y|X)构成条件随机场，即满足马尔可夫性
P(Y_i|X,Y_i,\cdots,Y_{i-1},Y_{i+1},\cdots,Y_n)=P(Y_i|X,Y_{i-1},Y_{i+1})\\ i=1,2,\cdots,n\ \ (在i=1和n时只考虑单边)
则称P(Y|X)为线性链条件随机场。在标注问题中，X表示输入观测序列，Y表示对应的输出标记序列或状态序列。

线性链条件随机场的简化形式

线性链条件随机场的参数形式可以简化为
P(y|x)=\frac1{Z(x)}\exp{\sum_{k=1}^Kw_kf_k(y,x)}

Z(x)=\sum_y\exp\sum_{k=1}^Kw_kf_k(y,x)

其中f_k(y,x)是特征函数。回顾最大熵模型：
P_w(y|x)=\frac1{Z_w(x)}\exp\bigg(w_if_i(x,y)\bigg)

Z_w(x)=\sum_y\exp\bigg(\sum_{i=1}^nw_if_i(x,y)\bigg)

可以看出两者有着非常类似的形式，并且线性链条件随机场也是对数线性模型。

条件随机场模型的3个基本问题

概率计算问题、学习问题、预测问题。

概率计算问题

条件随机场的概率计算问题是给定条件随机场P(Y|X)，输入序列x和输出序列y，计算条件概率P(Y_i=y_i|x)，P(Y_{i-1}=y_{i-1},Y_i=y_i|x)以及相应的数学期望的问题。类似隐马尔可夫模型，使用前向-后向算法。

条件随机场的学习算法

条件随机场模型实际上是定义在时序数据上的对数线性模型，类似最大熵模型，所以也可以用IIS法，梯度下降法以及拟牛顿法。

条件随机场的预测算法

条件机场的预测问题是给定条件随机场P(Y|X)和输入序列（观测序列）x，求条件概率最大的输出序列（标记序列）y^*。常用的算法是维特比算法，使用了动态规划的思路。

相关文章

  • 《统计学习方法》读书笔记

    本文总结了《统计学习方法》（李航）中的一些机器学习方法，组织目录如下： 【第1章】 统计学习方法概论【第2章】 感...

  • 2018-11-25 统计学习方法-李航 第一章

    第一章 统计学习方法概论 1.1 统计学习 实现统计学习方法的步骤如下： 1）得到一个有限的训练数据集合 2）确定...

  • 统计学习方法(一)——统计学习方法概论

    文章作者：Tyan博客：noahsnail.com | CSDN | 简书 1. 统计学习方法概论 本文是统计学习...

  • 无标题文章

    # CH01 统计学习方法概论 [TOC] ## 前言 ### 章节目录 1. 统计学习 2. 监督学习 1....

  • 《统计学习方法概论》思维导图

    〇、说明 这个是根据李航博士《统计学习方法》[1]的第一章《统计学习方法概论》整理的思维导图。 之前看这一章时对机...

  • 统计学习方法概论

    统计学习方法概论 统计学习 监督学习 统计学习三要素 模型评估与模型选择 泛化能力 生成模型与判别模型 分类问题 ...

  • 《统计学习方法》读书笔记（一）

    第一章 统计学习方法概论 一、统计学习 1.1.统计学习的特点 （1）统计学习以计算机与网络为平台，建立在它们...

  • 统计学习方法概论

    统计学习方法 1.监督学习 （分类、回归） 学习一个模型，使模型能够对任意给定的输入，与其相应的输出做一个好的预...

  • 统计学习方法概论

    1.统计学习 统计学习包括监督学习、非监督学习、半监督学习、强化学习 输入空间：输入变量取值的集合 输出空间：输出...

  • 《统计学习方法》-概论

    date: 2018-1-15看完周志华老师的《机器学习》，对机器学习有了一个全面的了解，但其细节部分不是很了解，...

网友评论

      本文标题：统计学习方法概论

      本文链接：https://www.haomeiwen.com/subject/sqlmhktx.html

      延伸阅读

      深度阅读

      • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

      栏目导航

      热点阅读

      关于我们|服务条款|联系我们|统计学习方法概论|投稿指南|网站地图|RSS订阅|排版工具|手机版

      提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

      Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

      备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

      本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

      所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！