支持向量机与核机器

作者: 有机会一起种地OT | 来源:发表于2019-10-17 13:58 被阅读0次

支持向量机与核机器
支持向量机
核函数与支持向量机入门
机器学习面试和答案(一)(自己)
【机器学习基础】核支持向量机
【机器学习】核支持向量机SVM
核支持向量机
机器学习之支持向量机
支持向量机的核函数
SVM支持向量机（三）

介绍
第一部分参数方法——类密度模型参数估计
第二部分监督学习——分类（基于似然的方法）
第三部分监督学习——分类（基于判别式的方法）（参数方法——判别式参数估计）
第四部分监督学习——回归
第五部分监督学习——关联规则
第六部分维度规约（特征的提取和组合）
第七部分半参数方法
第八部分非监督学习——聚类
第九部分非参数方法——密度估计
第十部分非参数方法——决策树实现的判别式
第十一部分多层感知器——非参数估计器
第十二部分局部模型
第十三部分支持向量机与核机器
第十四部分隐马尔科夫模型
第十五部分参数的贝叶斯估计
第十六部分集成学习——组合多学习器
第十七部分增强学习
第十八部分机器学习实验
第十九部分特征工程与数据预处理

本部分介绍支持向量机（SVM），是一种不同的分类和回归方法（也就是一种不同的归纳偏倚）。该模型最大化实例的分离性，或称最大化边缘的方法。将模型表示为训练实例的一个子集的影响之和。这些影响用面向应用的相似核给出。
SVM是基于判别式的方法。通过训练实例来估计边界。边界的线性模型用训练实例的一个子集表示，这个子集称作支持向量。对于分类，这个子集是靠近边界的实例。输出用支持向量的影响之和表示，用核函数给出。
核函数是数据实例之间相似度的面向应用的度量。根据相似性定义新的空间，如果一个核函数在其对应的新空间中有更好的分离性，则它是好的。

支持向量机

首先讨论最简单的二类分类问题，并假设线性可分。

对于二类分类，使用-1和+1标记这两个类，样本为 $X=\left\{ \mathbf{x}^t,r^t \right\}$ 。希望找到 $\boldsymbol{\omega}$ 和 $\omega_0$ ，使得对于 $r^t=+1$ ， $\boldsymbol{\omega}^T\mathbf{x}^t+\omega_0\geq +1$ ；而对于 $r^t=-1$ ， $\boldsymbol{\omega}^T\mathbf{x}^t+\omega_0\leq -1$ 。
或可改写为 $r^t(\boldsymbol{\omega}^T\mathbf{x}^t+\omega_0)\geq +1$ 。

这不同于线性判别式中常见的 $r^t(\boldsymbol{\omega}^T\mathbf{x}^t+\omega_0) \geq 0$ ，这里不仅希望实例在超平面正确的一侧，还希望它们离超平面有一定距离。超平面到它两侧最近实例的距离称作边缘。为了更好地泛化，希望最大化边缘。

实例 $\mathbf{x}^t$ 到判别式的距离为 $\frac{|\boldsymbol{\omega}^T\mathbf{x}^t+\omega_0|}{\|\boldsymbol{\omega}\|}=\frac{r^t(\boldsymbol{\omega}^T\mathbf{x}^t+\omega_0)}{\|\boldsymbol{\omega}\|}$ （见《监督学习——分类（基于判别式的方法）》中的推导），而我们希望这个距离大于某个 $\rho$ 值， $\frac{r^t(\boldsymbol{\omega}^T\mathbf{x}^t+\omega_0)}{\|\boldsymbol{\omega}\|}\geq \rho, \forall \ t$ 。
我们希望最大化 $\rho$ ，为了得到唯一解，我们固定 $\rho\|\boldsymbol{\omega}\|=1$ 。这样，为了最大化边缘，则最小化 $\|\boldsymbol{\omega}\|$ 。也就是
$\min_{\boldsymbol{\omega},\omega_0} \frac12\|\boldsymbol{\omega}\|^2 , \ s.t. \ r^t(\boldsymbol{\omega}^T\mathbf{x}^t+\omega_0)\geq +1,\ \forall \ t \tag{a}$

这是一个标准的二次优化问题，复杂度依赖于 $x$ 的维度d。
由于很多问题都不是线性可分的，我们会使用非线性基函数将问题映射到新空间，变成新空间中的线性问题。但新空间的维度往往比原始空间高很多。所以希望将问题转换成复杂度依赖于训练实例数N而不依赖于d的形式。

求解约束问题
问题（a）的函数和约束条件都是凸函数，所以可以解其对偶问题来得到原问题的最优解，并且解满足KKT条件。
首先使用拉格朗日乘子 $\alpha^t\geq 0$ ，得到广义拉格朗日方程：
$\begin{align} L(\boldsymbol{\omega},\omega_0,\alpha)=&\frac12\|\boldsymbol{\omega}\|^2-\sum^N_{t=1}\alpha^t[r^t(\boldsymbol{\omega}^T\mathbf{x}^t+\omega_0)-1] \\ =&\frac12\|\boldsymbol{\omega}\|^2-\sum^N_{t=1}\alpha^tr^t(\boldsymbol{\omega}^T\mathbf{x}^t+\omega_0)+\sum^N_{t=1}\alpha^t \end{align}$
原始问题等价于 $\min_{\boldsymbol{\omega},\omega_0}\max_{\alpha\geq0}L(\boldsymbol{\omega},\omega_0,\alpha)$ ，其对偶问题为 $\max_{\alpha\geq0}\min_{\boldsymbol{\omega},\omega_0}L(\boldsymbol{\omega},\omega_0,\alpha)$ 。
先求 $\min_{\boldsymbol{\omega},\omega_0}L(\boldsymbol{\omega},\omega_0,\alpha)$ ，有
$\frac{\partial L}{\partial \boldsymbol{\omega}}=\boldsymbol{\omega}-\sum_t\alpha^tr^t\mathbf{x}^t=0$ ， $\frac{\partial L}{\partial \omega_0}=-\sum_t\alpha^tr^t=0$
将结果带入拉格朗日方程中
$\begin{align} L(\boldsymbol{\omega},\omega_0,\alpha)=&\frac12\|\boldsymbol{\omega}\|^2-\sum^N_{t=1}\alpha^tr^t(\boldsymbol{\omega}^T\mathbf{x}^t+\omega_0)+\sum^N_{t=1}\alpha^t\\ =&\frac12(\boldsymbol{\omega}^T\boldsymbol{\omega})-\boldsymbol{\omega}^T\sum^N_{t=1}\alpha^tr^t\mathbf{x}^t-\omega_0\sum^N_{t=1}\alpha^tr^t+\sum^N_{t=1}\alpha^t\\ =&-\frac12(\boldsymbol{\omega}^T\boldsymbol{\omega})+\sum^N_{t=1}\alpha^t \\ =&-\frac12\sum_t\sum_s\alpha^t\alpha^sr^tr^s(\mathbf{x}^t)^T\mathbf{x}^s+\sum^N_{t=1}\alpha^t \end{align}$
进而只需对下面的对偶问题求解
$\max_{\alpha}\ -\frac12\sum_t\sum_s\alpha^t\alpha^sr^tr^s(\mathbf{x}^t)^T\mathbf{x}^s+\sum^N_{t=1}\alpha^t,\ s.t. \ \sum_t\alpha^tr^t=0,\alpha\geq0,\ \forall t$

可见对偶问题的复杂度依赖于训练集的大小N，而不依赖于输入维度d。记 $\boldsymbol{\omega}^*$ ， $\omega_0^*$ ， $\alpha^*$ 为问题的解。根据KKT条件有 $\alpha^{*t}(r^t(\boldsymbol{\omega}^{*T}\mathbf{x}^t+\omega_0^*)-1)=0, \ \forall t$ 。
又由 $r^t(\boldsymbol{\omega}^T\mathbf{x}^t+\omega_0)\geq +1$ ，可知对于 $\alpha^{*t}>0$ 的实例 $\mathbf{x}^t$ ，有 $r^t(\boldsymbol{\omega}^T\mathbf{x}^t+\omega_0)-1=0$ ，或 $\boldsymbol{\omega}^T\mathbf{x}^t+\omega_0=\pm1$ 。也就是说 $\mathbf{x}^t$ 一定在边缘的边界上，也就是支持向量。
由上面求解最小化时所得的 $\boldsymbol{\omega}^*=\sum_t\alpha^tr^t\mathbf{x}^t$ 可以看出，只有那些 $\alpha^*>0$ ，处于边缘上的实例的集合才决定了 $\boldsymbol{\omega}$ 。并得以求得 $\omega_0=r^t-\boldsymbol{\omega}^T\mathbf{x}^t$ 。

作为基于判别式的算法，SVM值关注那些靠近边界的实例。丢弃落在边界之外的实例，不会影响结果。所以在使用SVM之前，可以使用较简单的分类器，过滤掉远离边界的大部分实例，从而降低SVM阶段的复杂度。

对于数据不是线性可分时

可以考虑寻找错分类最少的超平面。定义松弛变量 $\xi^t\geq 0$ ，表示实例 $\mathbf{x}^t$ 到边缘的误差。我们要求
$r^t(\boldsymbol{\omega}^T\mathbf{x}^t-\omega_0)\geq1-\xi$ 。
有两种情况的误差，一种是实例被正确分类，但不像线性可分情况下所讨论的在边缘外，而是在边缘内，这时令 $0 < \xi <1$ 。另一种情况，是实例被误分类， $\xi>1$ 。而当 $\xi=0$ 时，则实例仍在边缘上。
对每个 $\xi_i$ ，记为误差，并作为惩罚项。则目标函数变为
$\begin{array}{} \min_{\boldsymbol{\omega},\omega_0,\xi} & \frac12\|\boldsymbol{\omega}\|^2 +C\sum^N_{t=1}\xi^t\\ s.t. & r^t(\boldsymbol{\omega}^T\mathbf{x}^t+\omega_0)\geq 1-\xi^t\\ & \xi^t\geq0,\ \forall \ t \tag{b} \end{array}$
C称作惩罚因子。

这样，广义拉格朗日方程变成
$L(\boldsymbol{\omega},\omega_0,\xi,\alpha,\mu)=\frac12\|\boldsymbol{\omega}\|^2+C\sum^N_{t=1}\xi^t-\sum^N_{t=1}\alpha^t[r^t(\boldsymbol{\omega}^T\mathbf{x}^t+\omega_0)-1+\xi^t]-\sum^N_{t=1}\mu^t\xi^t$
求解对偶问题，先对 $\boldsymbol{\omega},\omega_0,\xi$ 最小化方程，对参数求导
$\frac{\partial L}{\partial \boldsymbol{\omega}}=\boldsymbol{\omega}-\sum_t\alpha^tr^t\mathbf{x}^t=0$ ，
$\frac{\partial L}{\partial \omega_0}=-\sum_t\alpha^tr^t=0$ ，
$\frac{\partial L}{\partial \xi^t}=C-\alpha^t-\mu^t=0$
带入拉格朗日方程中，得 $\min_{\boldsymbol{\omega},\omega_0,\xi}L=-\frac12\sum_s\sum_t\alpha^s\alpha^tr^sr^t(\mathbf{x}^t)^T\mathbf{x}^s+\sum_t\alpha^t$ 。
再对 $\alpha$ 求极大，也就是对偶问题
$\begin{array}{} \max_{\alpha} & -\frac12\sum_s\sum_t\alpha^s\alpha^tr^sr^t(\mathbf{x}^t)^T\mathbf{x}^s+\sum_t\alpha^t\\ s.t. & \sum_t\alpha^tr^t=0 \\ & C-\alpha^t-\mu^t=0\\ & \alpha^t\geq0,\ \mu^t\geq0,\ \ \forall \ t \end{array}$

后三条约束条件等价于 $0 \leq \alpha^t \leq C$
同样的， $\alpha^t>0$ 的实例为支持向量，它们定义 $\boldsymbol{\omega}$ 。这当中， $\alpha^t<C$ 的实例在边缘上， $\alpha^t=C$ 的实例在边缘内或被误分类。

C的取值与任意正则化模式一样，需要交叉检验微调，在边缘最大化和误差最小化之间权衡。如果C太大，则对未正确分类的点惩罚较大，边缘更宽而纳入许多支持变量，且过拟合；如果太小，则可能过于简单而欠拟合。

当存在多个类

情况同基于判别式的分类方法中所提及的一样。
考虑每个类可与其他类分开的情况，学习K个支持向量机 $g_i(\mathbf{x})(i=1.\cdots,K)$ 。
或对于复杂情况，构建 $K(K-1)/2$ 个逐对分类器，

换个角度，在SVM中如果实例在错误一侧或者离边界距离小于1在边缘内，可视为错误。这样，用 $y^t=\boldsymbol{\omega}^T\mathbf{x}^t+\omega_0$ 反应实例到超平面的距离， $r^t$ 为期望的输出。
SVM相当于最小化转折点损失（hinge loss）：
$L_{hinge}(y^t,r^t)=\left\{\begin{equation} \begin{array}{} 0 & if \ y^tr^t \geq1 \\ 1-y^tr^t & else \\ \end{array} \end{equation} \right.$
$|\boldsymbol{\omega}\|^2$ 为正则项。
$\min_{\boldsymbol{\omega},\omega_0} L_{hinge}(y^t,r^t)+C\|\boldsymbol{\omega}\|^2$

非线性边界的情况

如果类边界是非线性的，则使用合适的基函数将非线性问题映射到新空间，在新空间使用线性模型。这种方法在介绍线性判别式和多层感知器的章节中都有运用。

核技巧

设有基函数 $\mathbf{z}=\Phi(\mathbf{x})$ ，其中 $z_j=\phi_j(\mathbf{x}),j=1,\cdots,k$ 。将 d 维的 $\mathbf{x}$ 空间映射到 k 维的 $\mathbf{z}$ 空间。新空间中的线性判别式为
$g(\mathbf{z})=\boldsymbol{\omega}^T\mathbf{z}=\boldsymbol{\omega}^T\Phi(\mathbf{x})=\sum^k_{j=1}\omega_j\phi_j(\mathbf{x})$
这里判别式的常数项 $\omega_0$ 不单独使用，而是假定 $z_1=\phi_1(\mathbf{x})=1$ 。这样问题和线性可分的情况一样：
$\min_{\boldsymbol{\omega}} \frac {1}{2}\|\boldsymbol{\omega}\|^2+C\sum^t\xi^t$
约束条件变为 $r^t\boldsymbol{\omega}^T\Phi(\mathbf{x}^t)\geq1-\xi^t$
拉格朗日方程是 $L=\frac 12\|\boldsymbol{\omega}\|^2+C\sum^N_{t=1}\xi^t-\sum^N_{t=1}\alpha^t[r^t(\boldsymbol{\omega}^T\Phi(\mathbf{x}^t)+\omega_0)-1+\xi^t]-\sum^N_{t=1}\mu^t\xi^t$

这时作为新空间上的线性可分问题，由前文可知对偶问题为
$\begin{array}{} \max_{\alpha} & -\frac12\sum_s\sum_t\alpha^s\alpha^tr^sr^t\Phi(\mathbf{x}^t)^T\Phi(\mathbf{x}^s)+\sum_t\alpha^t\\ s.t. & \sum_t\alpha^tr^t=0\\ & C-\alpha^t-\mu^t=0\\ & \alpha^t\geq0,\ \mu^t\geq0,\ \ \forall \ t \end{array}$
判别式参数 $\boldsymbol{\omega}^T=\sum^t\alpha^tr^t\Phi(\mathbf{\mathbf{x}^t})$
这其中 $K(\mathbf{x}^t,\mathbf{x}^s)=\Phi(\mathbf{x}^t)^T\Phi(\mathbf{x}^s)$ 称为核函数，它是原向量经基函数映射到新空间后的内积。在计算时，直接计算核函数要比计算基函数映射后的向量内积简单得多。所以很多算法都被核化，使用原空间中实例之间的核函数，取代基函数的内积，这正是使用核机器的原因。

核值矩阵记做 $\mathbf{K}$ ，其中 $\mathbf{K}_{ts}=K(\mathbf{x}^t,\mathbf{x}^s)$ ，是Garm矩阵。对称半正定。

一些常用的核函数如下

q次多项式
$K(\mathbf{x}^t,\mathbf{x})=(\mathbf{x}^T\mathbf{x}^t+1)^q$
径向基函数
$K(\mathbf{x}^t,\mathbf{x})=\exp[-\frac{\|\mathbf{x}^t-\mathbf{x}\|^2}{2s^2}]$
推广欧氏距离，可使用马氏距离的核
$K(\mathbf{x}^t,\mathbf{x})=\exp[-\frac12(\mathbf{x}^t-\mathbf{x})^T\mathbf{S}^{-1}(\mathbf{x}^t-\mathbf{x})]$
或更一般地，对于某个距离函数 $D(\mathbf{x}^t,\mathbf{x})$ 定义核函数
$K(\mathbf{x}^t,\mathbf{x})=\exp[-\frac{D(\mathbf{x}^t,\mathbf{x})}{2s^2}]$
S型核
tanh函数、Sigmoid函数
面向应用的核
除了使用常用的核函数，还可以定义面向应用的核。核通常被看做相似性的度量，从应用的角度看，当x 和y 更相似时， $K(\mathbf{x},\mathbf{y})$ 取更大的值。这意味着，关于应用的先验知识可以通过定义合适的核提供给学习系统。

除了单一核，还可以通过使用多核。如一些简单的核可以构造新的核。如任意两个合法的核 $K_1(\mathbf{x},\mathbf{y})$ ， $K_2(\mathbf{x},\mathbf{y})$ ，c是常数，则
$K(\mathbf{x},\mathbf{y})=cK_1(\mathbf{x},\mathbf{y})$ 、 $K(\mathbf{x},\mathbf{y})=K_1(\mathbf{x},\mathbf{y})+K_2(\mathbf{x},\mathbf{y})$ 、
$K(\mathbf{x},\mathbf{y})=K_1(\mathbf{x},\mathbf{y})*K_2(\mathbf{x},\mathbf{y})$ 也是合法的核。
一般地对多个和求加权和，可由数据学习权重 $K(\mathbf{x},\mathbf{y})=\sum^m_{i=1}\eta_iK_i(\mathbf{x},\mathbf{y})$ 。这称为多核学习。

此外，还可以对x的不同维度子集，分别使用不同的核。将x表示为 $\mathbf{x}=[\mathbf{x}_A,\mathbf{x}_B]$ ，分别对两部分使用不同的核，每个核分别度量子集领域的相似度，
$\begin{align} K_A(\mathbf{x}_A,\mathbf{y}_A)+K_B(\mathbf{x}_B,\mathbf{y}_B)=&\Phi_A(\mathbf{x}_A)^T\Phi_A(\mathbf{y}_A)+\Phi_B(\mathbf{x}_B)^T\Phi_B(\mathbf{y}_B)\\ =&\Phi(\mathbf{x})^T\Phi(\mathbf{y}) \\ =&K(\mathbf{x},\mathbf{y}) \end{align}$
这也是一种局部思想。一般地，固定一个向量输入为 $\mathbf{x}^t$ ,使用混合模型表示有 $K(\mathbf{x}^t,\mathbf{x})=\sum^m_{i=1}\eta_i(\mathbf{x}|\theta_i)K_i(\mathbf{x}^t,\mathbf{x})$

用于回归的核机器

先从线性回归问题开始，后面在推广核函数的运用。
考虑线性模型 $f(\mathbf{x})=\boldsymbol{\omega}^T\mathbf{x}+\omega_0$ ，对于一般的回归方法，使用拟合输出与实际输出差的平方作为误差：
$e=[r^t-f(\mathbf{x})]^2$
在支持向量机中，使用敏感损失函数：
$e=\left\{\begin{equation} \begin{array}{} 0 & if \ |r^t-f(\mathbf{x})|<\epsilon \\ |r^t-f(\mathbf{x})|-\epsilon & else \end{array} \end{equation} \right.$
这意味着对于拟合与实际差小于 $\epsilon$ 的误差是被接受的，而超出的误差才保留线性影响，而不是平方影响。
SVM就是用超平面来拟合未知函数， $\epsilon$ 对应于边缘。类似于软边缘超平面，引入松弛变量来处理超出 $\epsilon$ 范围外的误差。任务可描述为
$\min_{\boldsymbol{\omega},\xi^t_+,\xi^t_-}\frac12\|\boldsymbol{\omega}\|^2+C\sum_t(\xi^t_++\xi^t_-)$
$s.t. \ -(\epsilon+\xi^t_-)\leq r^t-(\boldsymbol{\omega}^T\mathbf{x}+\omega_0)\leq\epsilon+\xi^t_+,\ \xi^t_+ \geq0,\ \xi^t_-\geq0$
拉格朗日方程是
$\begin{align} L_p=&\frac12\|\boldsymbol{\omega}\|^2+C\sum_t(\xi^t_++\xi^t_-)-\sum_t\alpha^t_+[\epsilon+\xi^t_+-r^t+(\boldsymbol{\omega}^T\mathbf{x}+\omega_0)]\\ &-\sum_t\alpha^t_-[\epsilon+\xi^t_-+r^t-(\boldsymbol{\omega}^T\mathbf{x}+\omega_0)]-\sum^t(\mu^t_+\xi^t_++\mu^t_-\xi^t_-)\\ \end{align}$
求解对偶问题，首先对 $\boldsymbol{\omega},\xi^t_+,\xi^t_-$ 最小化 $L_p$ ，
$\frac{\partial L_p}{\partial \boldsymbol{\omega}}=\boldsymbol{\omega}-\sum_t(\alpha^t_+-\alpha^t_-)\mathbf{x}^t=0$
$\frac{\partial L_p}{\partial \omega_0}=-\sum_t(\alpha^t_+-\alpha^t_-)=0$
$\frac{\partial L_p}{\partial \xi^t_+}=C-\alpha^t_+-\mu^t_+=0$
$\frac{\partial L_p}{\partial \xi^t_-}=C-\alpha^t_--\mu^t_-=0$
再对 $\alpha_+^t,\alpha_-^t$ 最大化。
通过训练数据集，求出问题的解。其中落在 $[-(\epsilon+\xi^t_-),\epsilon+\xi^t_+]$ 内的实例，都有 $\alpha^t_+=\alpha^t_-=0$ ；支持向量满足 $0<\alpha^t_+<C$ 或者 $0<\alpha^t_-<C$ ；而在 $[-(\epsilon+\xi^t_-),\epsilon+\xi^t_+]$ 外的实例， $\alpha^t_+=C$ 或 $\alpha^t_-=C$ 。
所得到的的拟合直线为
$f(\mathbf{x})=\boldsymbol{\omega}^T\mathbf{x}+\omega_0=\sum_t(\alpha^t_+-\alpha^t_-)(\mathbf{x}^t)^T\mathbf{x}+\omega_0$