统计学习方法概论

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

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

统计学习方法概论

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

统计学习的方法

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

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

监督学习和非监督学习

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

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

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

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

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

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

联合概率分布

监督学习假设输入与输出随机变量 $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)}$ 最小化或者结构风险最小化。

期望风险（损失） $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$
经验风险（损失） $R_{\mathrm{emp}(f)}$ ：模型在样本上的平均损失。
$R_{\mathrm{exp}(f)}=\frac1N\sum_{i=1}^NL(y_i,f(x_i))$
结构风险（损失）：为了防止过拟合加上正则化的经验损失。
$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$ 折交叉验证的特例，每个样本为一折。

生成模型与判别模型

判别模型：直接学习 $f(X)$ 和 $P(Y|X)$ 的参数的模型。常见的判别模型有： $k$ 近邻法、感知机、决策树、逻辑斯谛回归、最大熵模型、支持向量机、提升方法和条件随机场。
生成模型：学习联合分布 $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近邻法包含三个要素：

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

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

k近邻算法

根据给定的距离度量，在训练集 $T$ 中找出与 $x$ 最邻近的 $k$ 个点，涵盖这 $k$ 个点的 $x$ 的领域记做 $N_k(x)$ ；
在 $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值。

距离度量

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

$L_p$ 距离：
$L_p(x_i,x_j)=\bigg(\sum_{l=1}^n|x_i^{(l)}-x_j^{(l)}|^p\bigg)^{\frac1p}$
欧氏距离（ $L_2$ 距离）：
$L_2(x_i,x_j)=\bigg(\sum_{l=1}^n|x_i^{(l)}-x_j^{(l)}|^2\bigg)^{\frac12}$
曼哈顿距离（ $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)$ 的参数，具体可以查看《统计学习方法》第五章或统计机器学习-决策树。

决策树的定义

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

决策树学习的三个步骤

特征选择、生成、剪枝。

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

特征选择

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

信息增益：
$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算法由以下两步组成：

决策树生成：基于训练数据集生成决策树，生成的决策树要尽量大；
决策树剪枝：用验证数据集对已生成的树进行剪枝并选择最优子树，这时用损失函数最小作为剪枝的标准。

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

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

分类树的生成

使用切分后基尼指数最小的特征进行切分。即：
$\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）。

七、提升方法

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

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

每一轮如何改变训练数据的权值或概率分布
如何将若分类器组合成一个强分类器

Adaboost算法

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

训练数据被分类错误，权值上升，被分类正确，权值下降
加权多数表决，误差率越小，权值越高

回归提升树

在每一步使用一棵回归树 $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）两个步骤。

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$ 的条件概率分布；
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)$
隐马尔可夫模型做了两个基本假设：

齐次马尔可夫性假设，即假设隐藏的马尔可夫链在任意时刻 $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$
观测独立性假设，即假设任意时刻的观测只依赖于该时刻的马尔可夫链的状态，与其他观测及状态无关。（每个时刻的观测只依赖于当前时刻的状态）

$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个基本问题

概率计算问题。给定模型 $\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)$ 最大。即用极大似然估计的方法估计参数。
预测问题，也称为解码问题。已知模型 $\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)$ 。即给定观测序列，求最有可能的对应状态序列。可是使用近似算法和维特比算法。

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

十、条件随机场

条件随机场是给定一组输入随机变量条件下另一组随机变量的条件概率分布模型 $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$ 表示对应的输出标记序列或状态序列。