人智导统计机器学习

统计机器学习

对于数据集 $D = \{(x_{i}, y_{i})\}$ ，输入输出之间存在关系 $f$ ，算法 $A$ 根据训练集从假设空间 $\mathcal{H}$ 中选取一个合适的函数 $g\approx f$

主要决定因素：模型、策略、算法

分类方式：

监督式学习
半监督式学习
弱监督式学习

支持向量机(SVM)

按照模型的复杂程度，分为线性可分、线性与非线性

线性可分SVM

定义线性可分SVM相关概念如下：

线性可分训练集：

T = \{ (x_{i}, y_{i}) \,|\, 1\leq i\leq N, x_{i}\in \mathbb{R}^{n}, y_{i}\in\{-1, 1\} \}

给定超平面 $wx+b = 0$ ，于是可以定义函数间隔为：

\hat{\gamma} = \mathop{\min}\limits_{1\le i \le N}\{(wx_{i} + b)y_{i}\}

相对应的，定义几何间隔为函数间隔的归一化，也即考虑超平面的缩放的影响

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

通过间隔最大化得到分类超平面 $w^{*}x+b^{*} = 0$ ，则得到决策函数：

f(x) = \mathrm{sgn}(w^{*}x+b^{*})

此即线性可分SVM

于是关键问题即为间隔最大化：

\max\limits_{w, b}\gamma = \max\limits_{w, b}{\frac{\hat{\gamma}}{||w||}}

显然，函数间隔是可缩放的（函数缩放表示为$w, b$等比例缩放），因此不妨令 $\hat{\gamma} = 1$ ，则进一步转化为规划问题：

\max\limits_{w, b}\frac{1}{||w||} = \min\limits_{w, b} \frac{1}{2}||w||^{2}

使得：

\forall i,\quad \hat{\gamma_{i}} = (wx_{i} + b)y_{i} \geq 1

定义相对应的拉格朗日函数为：

L(w, b, \alpha) = \frac{1}{2}||w||^{2} + \sum\limits_{i=1}^{N}\alpha_{i}[1 - (wx_{i} + b)y_{i}]

则在满足优化条件的情况下，原问题转化为：

\min\limits_{w, b}\max\limits_{\alpha}L(w, b, \alpha)

当满足KKT条件时，该问题可转化为其对偶问题：

\max\limits_{\alpha}\min\limits_{w, b}L(w, b, \alpha)

\begin{align*}\nabla_{w, b}L(w, b, \alpha) &= 0 \\\alpha_{i}[1 - (wx_{i} + b)y_{i}] &= 0 \\1 - (wx_{i} + b)y_{i} &\leq 0 \\\alpha_{i} &\geq 0 \end{align*}

利用KKT条件转化为对偶问题之后，可以化简为：

\begin{align*}&\quad \max\limits_{\alpha}\bigl(-\frac{1}{2}\sum\limits_{i = 1}^{N}\sum\limits_{j=1}^{N}\alpha_{i}\alpha_{j}y_{i}y_{j}(x_{i}\cdot x_{j}) + \sum\limits_{i=1}^{N}\alpha_{i} \bigr) \\&= \min\limits_{\alpha}\bigl(\frac{1}{2}\sum\limits_{i = 1}^{N}\sum\limits_{j=1}^{N}\alpha_{i}\alpha_{j}y_{i}y_{j}(x_{i}\cdot x_{j}) - \sum\limits_{i=1}^{N}\alpha_{i} \bigr) \\\end{align*}

使得：

\sum\limits_{i=1}^{N}\alpha_{i}y_{i} = 0\quad \alpha_{i} \geq 0

于是可以求出 $\alpha^{*}$ ，相对应的根据KKT条件求出 $w^{*}, b^{*}$ ：

\begin{align*}w^{*} &= \sum\limits_{i=1}^{N}\alpha_{i}^{*}y_{i}x_{i} \\b^{*} = y_{j} - &\sum\limits_{i=1}^{N}\alpha_{i}^{*}y_{i}(x_{i}\cdot x_{j})\quad \alpha_{j} \neq 0\end{align*}

所得到的 $\alpha_{i} > 0$ 对应的实例 $x_{i}$ 即为支持向量

线性SVM

在线性可分SVM中，约束条件要求每一个样本点的函数间隔都不小于 $1$ ，这个条件事实上要求样本拥有很强的分类性，而对于一些分类性较弱的样本，很难全部满足这个条件，因此引入松弛变量 $\xi_{i}$ ，将约束条件修改为

(wx_{i} + b)y_{i} \geq 1 - \xi_{i}

为了让分隔尽量好，因此要满足松弛变量尽量小，因此调整优化问题为：

\min\limits_{w, b, \xi}\bigl( \frac{1}{2}||w||^{2} + C\sum\limits_{i=1}^{N}\xi_{i} \bigr)

其中 $C$ 为惩罚参数，用于调整间隔最大与误分类点数之间的矛盾
于是，可以转化为：

\min\limits_{\alpha}\bigl(\frac{1}{2}\sum\limits_{i = 1}^{N}\sum\limits_{j=1}^{N}\alpha_{i}\alpha_{j}y_{i}y_{j}(x_{i}\cdot x_{j}) - \sum\limits_{i=1}^{N}\alpha_{i} \bigr)

使得：

\sum\limits_{i=1}^{N}\alpha_{i}y_{i} = 0\quad 0\leq \alpha_{i} \leq C

可以看出与线性可分的唯一区别在与 $\alpha_{i}$ 的范围，因此最终求出 $w^{*}, b^{*}$ 时同样和线性可分只有这个区别，具体来说：

\begin{align*}w^{*} &= \sum\limits_{i=1}^{N}\alpha_{i}^{*}y_{i}x_{i} \\b^{*} = y_{j} - &\sum\limits_{i=1}^{N}\alpha_{i}^{*}y_{i}(x_{i}\cdot x_{j})\quad 0 < \alpha_{j} < C\end{align*}

同样， $\alpha_{i}^{*} > 0$ 所对应的样本成为软间隔的支持向量，具体来说：

$\alpha_{i}^{*} < C$ 时， $\xi_{i} = 0$ ， $x_{i}$ 位于间隔边界
$\alpha_{i}^{*} = C$ $α_{i}^{*} = C$ 时， $\xi_{i} > 0$ $ξ_{i} > 0$ ：
- $0 < \xi_{i} < 1$ 时，分类正确
- $\xi_{i} = 1$ 时，位于超平面上
- $\xi_{i} > 1$ 时，分类错误

非线性SVM

关键思想：利用变换 $\phi: \mathcal{X}\to \mathcal{H}$ 将原空间的数据映射到特征空间，使之变为线性的，相对应的问题为：

\min\limits_{\alpha}\bigl(\frac{1}{2}\sum\limits_{i = 1}^{N}\sum\limits_{j=1}^{N}\alpha_{i}\alpha_{j}y_{i}y_{j}(\phi(x_{i})\cdot \phi(x_{j})) - \sum\limits_{i=1}^{N}\alpha_{i} \bigr)

使得：

\sum\limits_{i=1}^{N}\alpha_{i}y_{i} = 0\quad 0\leq \alpha_{i} \leq C

可以看出其中只有内积有变化，因此若存在函数 $K$ 满足 $K(x, z) = \phi(x)\cdot \phi(z)$ 对任二元素都成立，则称 $K(x, z)$ 为核函数

同一个核函数对应的映射不一定相同

映射到新空间之后，可以解得：

\begin{align*}w^{*} &= \sum\limits_{i=1}^{N}\alpha_{i}^{*}y_{i}\phi(x_{i}) \\b^{*} = y_{j} - &\sum\limits_{i=1}^{N}\alpha_{i}^{*}y_{i}K(x_{i}, x_{j})\quad 0 < \alpha_{j} < C\end{align*}

常用的核函数包括：

\begin{align*} K(x, z) &= (x\cdot z + 1)^{p} \\ K(x, z) &= \exp(-\frac{||x - z||^{2}}{2\sigma^{2}})\quad (\text{Gaussian}) \end{align*}

采用高斯核函数的时候，关键为 $\sigma$ 的选取，不当会导致欠拟合与过拟合

σ过大导致欠拟合

σ过小导致过拟合

由于求解凸二次规划的算法在样本数很多的时候非常低效，因此有许多快速算法，例如序列最小最优化算法SMO

当样本中有多类怎么办？

将一类视为正，其余所有视为负
任意两类构造一个SVM，分类时采取投票法
二分类别，依次二分整体直至单独类别

SVM应用举例

文本分类：文本表达为一个向量 $(w_{1j}, \dots, w_{nj})^{T}$ ， $w_{ij}$ 表示词 $i$ 在文档 $j$ 中的权重，具体计算有很多版本，在此介绍两种：

$w_{ij} = \mathrm{tf}_{ij}$ 即tf权重，用词频代表权重
$w_{ij} = \mathrm{tf}_{ij}*\mathrm{idf}_{i}$ 即tf-idf权重，其中idf为逆文档频率，记 $\mathrm{cnt}(i)$ 为词 $i$ 所出现的文档数，则 $\mathrm{idf}_{i} = \log(\frac{N}{\mathrm{cnt}(i)})$

决策树

对样本进行分类，由节点和有向边组成，每个内部节点表示一个特征或者一个属性，每个叶节点表示一个类
决策树通过在训练集中对于分类规则进行训练，得到一组矛盾较小的特征，即 $K$ 分类问题，而最优决策树的选择是一个NPC问题，因此通常采用启发式方法
学习过程包括：

特征选择
决策树生成与剪枝

特征选择

按照信息增益来选择特征，信息增益 $g(D, A)$ 代表了特征 $A$ 对于数据集 $D$ 分类的不确定性的减少程度，计算如下：

记 $X, Y$ 是两个随机变量， $P(X = x_{i}) = p_{i}$ ，则：
随机变量的熵：

H(X) = -\sum\limits_{i=1}^{n}p_{i}\log(p_{i})

条件熵：

H(Y\,|\, X) = \sum\limits_{i=1}^{N}p_{i}H(Y \,|\, X = x_{i})

信息增益：

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

信息增益越大的特征分类能力越强

具体到特征 $A$ 对于数据集 $D$ 的信息增益，设一共有 $K$ 个类别 $(C_{1}, \dots, C_{K})$ ， $A$ 有 $n$ 种不同值 $(a_{1},\dots, a_{n})$ ，对应了一个划分 $(D_{1}, \dots, D_{n})$ ，记 $D_{ij}$ 为 $D_{i}$ 中属于类 $C_{j}$ 的集合，则：

\begin{align*}H(D) &= \sum\limits_{j=1}^{K}\frac{|C_{j}|}{|D|}\log(\frac{|C_{j}|}{|D|}) \\H(D\,|\, A) &= \sum\limits_{i=1}^{n}\frac{|D_{i}|}{|D|}H(D_{i}) \\&= -\sum\limits_{i=1}^{n}\biggl(\frac{|D_{i}|}{|D|}\sum\limits_{j=1}^{K}\bigl(\frac{|D_{ij}|}{|D_{i}|}\log(\frac{|D_{ij}|}{|D_{i}|})\bigr)\biggr) \\g(D, A) &= H(D) - H(D\,|\, A)\end{align*}

决策树的生成

两个常用的算法为ID3与C4.5

ID3算法

输入：训练集 $D$ ，特征 $A$ ，阈值 $\varepsilon$
输出：决策树 $T$

算法如下：

若 $D$ 中所有实例属于同一类 $C$ ，则 $T$ 单节点，类标记为 $C$ ，直接返回
若 $A = \varnothing$ ，则 $T$ 也为单节点，类标记为 $D$ 中最多的类 $C_{j}$ ，直接返回
计算 $A$ 中所有特征对 $D$ 的信息增益，选择其中信息增益最大的特征 $A_{k}$
若 $g(D, A_{k}) \leq \varepsilon$ ，则将 $T$ 置为单节点树，类标记为 $D$ 中最多的类 $C_{j}$ ，直接返回
反之，遍历 $A_{k} = (a_{k1}, \dots, a_{kn_{k}})$ ，将 $D$ 划分为 $n_{k}$ 个子集分别作为子节点
遍历子节点 $D_{i}$ ，若为空，则将 $D$ 中最多的类标记这个子节点
反之以 $(D_{i}, A - A_{k}, \varepsilon)$ 递归
返回 $T$

也就是按照特征集合不断划分，当出现所有属于同一类或某一个划分为空集的时候进行特判即可

问题：信息增益倾向于选择分支较多的特征，但是有的分支是毫无意义的

C4.5算法

考虑信息增益比：

g_{R}(D, A) = \frac{g(D, A)}{H_{A}(D)} = g(D, A)\bigl(-\sum\limits_{i=1}^{n}\frac{|D_{i}|}{|D|}\log(\frac{|D_{i}|}{|D|})\bigr)^{-1}

因此C4.5引入信息增益比来选择特征，同时允许特征的取值为连续的而非离散的，相对于ID3的改进如下：

将选择信息增益最大的特征改为：
- 选择信息增益前 $k$ 大的特征，再从其中选择信息增益比最大的特征
- 原因是信息增益比倾向于选择分割不均匀的特征
对于连续的特征，采用二分，找到中间值 $a_{0}$ ，将 $\leq a_{0}$ 的划分到左子树， $>a_{0}$ 的划分到右子树

决策树的剪枝

由于决策树非常容易出现过拟合，因此需要对其进行剪枝先生成树再剪枝，这种方法称之为后剪枝

剪枝方式为：

对于某个内部节点，删除这棵子树，用这棵子树的根节点作为新的叶节点，其类别标记为其中最多的类

当数据集比较大的时候，剪枝方式为：

在训练集上训练，逐步剪枝
在验证集上验证直至性能下降
在测试集上测试

当数据集比较小的时候，直接利用训练集进行剪枝，方法如下：
设决策树 $T$ 的叶节点为 $\mathrm{leaf}(T) = (T_{1}, \dots, T_{t})$ ， $T_{i}$ 有 $N_{i}$ 个样本，其中第 $k$ 类的样本点有 $N_{ik}$ 个， $H_{i}(T)$ 为经验熵， $a$ 为参数，记损失函数为：

\begin{align*} C_{a}(T) &= \sum\limits_{i=1}^{t}N_{i}H_{i}(T) + at \\ &= -\sum\limits_{i=1}^{t}\sum\limits_{j=1}^{K}N_{ij}\log\frac{N_{ij}}{N_{i}} + at \end{align*}

其中两项分别代表预测误差与模型复杂程度

最终，剪枝算法为：

输入：整个树 $T$ ，参数 $a$
输出：修剪后的 $T_{a}$

计算每个节点的经验熵
从叶节点向上回溯，如果在某个点剪枝之后可以降低损失函数，则剪枝，反之跳过
直到不能继续剪枝，结束

随机森林

由于决策树非常容易过拟合，因此使用多棵决策树组成一片随机森林，利用投票机制进行决策
单棵决策树的生成是通过有放回的数据采样，关键点为集外数据的使用（也即别的决策树怎么使用某棵决策树没使用的数据）

本文采用署名-非商业性使用-相同方式共享 4.0 国际许可协议，转载请注明出处。

IAI-统计机器学习