机器学习：支持向量机

发表于 更新于 分类于

超平面

任一平面都可以用它上面的一点及它的法线向量来确定。易于理解的形式：

xcos⁡α+ycos⁡β+zcos⁡γ=px\cos{\alpha} + y\cos{\beta} + z\cos{\gamma} = p

其中 pp 为平面到原点的距离，3 个角度分别为平面法向量在 x y z 轴方向的方向余弦

超平面 (ω,b)(\omega, b) 表示超平面方程为：

ωTx+b=0\omega^Tx+b=0

  • ω\omega 为超平面的法向量，决定了超平面的方向
  • bb 为位移项，决定了超平面与原点的距离

任意点 x0x_0 到超平面 (ω,b)(\omega, b) 的距离 rr 可写为：

r=∣ωTx0+b∣∣∣ω∣∣r = \frac{|\omega^Tx_0+b|}{||\omega||}

式子的分子为法向量和以点 x0x_0 为终点的向量的数量积，分母为法向量的模，得出的结果即为平面上的任意一点与点 x0x_0 的连线的模乘以其与法向量的夹角的余弦值，显然为点到平面的距离。

超平面用于分类

设有样本 xix_i ，其类别为 yi(yi∈{1,−1})y_i(y_i \in \{1, -1\})，若超平面 (ω,b)(\omega, b) 能将其正确分类，则 (ω,b)(\omega, b) 应满足：

{ωxi+b≥1y=1ωxi+b≤−1y=−1\left\{ \begin{array}{rcl} \omega x_i + b &\geq& 1& & {y = 1}\\ \omega x_i + b &\leq& -1& & {y = -1}\\ \end{array} \right.

支持向量机的基本型

距离超平面最近的几个样本点称为支持向量，支持向量点 xjx_j 满足

ωxi+b=1y=1ωxi+b=−1y=−1\begin{aligned} \omega x_i + b &=1 & & {y = 1}\\ \omega x_i + b &=-1 & & {y = -1}\\ \end{aligned}

因此，两个异类支持向量到平面的距离之和为

γ=2∣∣ω∣∣\gamma = \frac{2}{||\omega||}

显然，超平面与支持向量之间的距离越远越好，此时分类结果是最鲁棒的，泛化能力最强，故分类的目标是：

max⁡ω,b2∣∣ω∣∣ s.t. yi(ωTxi+b)≥1i=1,2,3,...,m.\begin{aligned} &\max_{\omega,b}\frac{2}{||\omega||} \\ \text{ s.t. }& y_i(\omega^Tx_i+b)\geq1 & i=1,2,3,...,m. \end{aligned}

最大化间隔等效于最大化 ω\omega 的倒数，等效于最小化 12ω2\frac{1}{2}\omega^2，此即为支持向量机（Support Vector Machine，SVM）的基本型

求解

利用拉格朗日乘数法来求解上述基本型

考研数学中，拉格朗日乘数法用于多元函数的求条件极值问题，若求 f(x,y)f(x,y) 在条件 φ(x,y)=0\varphi(x,y)=0 下的极值，只需构造拉格朗日函数 F(x,y,λ)=f(x,y)+λφ(x,y)F(x,y, \lambda) = f(x,y) + \lambda \varphi(x,y) ，然后求解使其偏导均为 0 的方程组即可。

此时的条件极值的条件为：yi(ωTxi+b)≥1y_i(\omega^Tx_i+b)\geq1 （其意义为对每一个样本 xix_i，都能正确计算其类别）

写出拉格朗日函数：

L(ω,b,α)=12∣∣ω∣∣2+∑i=1mαi(1−yi(ωTxi+b))L(\omega, b, \alpha) = \frac{1}{2}||\omega||^2+\sum^m_{i=1}\alpha_i(1-y_i(\omega^Tx_i+b))

学习中…

核函数

原始样本空间内不存在可以划分样本的超平面时，可选择将样本空间映射到一个更高维的特征空间，使样本在这个特征空间内线性可分。

如果原始空间是有限维，那么一定存在一个高维特征空间使样本可分。

令 ϕ(x)\phi(x) 表示 xx 映射到高维空间后的向量，则对应的超平面可表示为：

f(x)=ωTϕ(x)+bf(x) = \omega^T\phi(x)+b

其对偶问题为：

max⁡α∑i=1mαi−12∑i=1m∑j=1mαiαjyiyjϕ(xi)Tϕ(xj)s.t.∑i=1mαiyi=0αi≥0,i=1,2,...,m.\begin{aligned} &\max_\alpha\sum^m_{i=1}\alpha_i-\frac{1}{2}\sum^m_{i=1}\sum^m_{j=1}\alpha_i\alpha_jy_iy_j\phi(x_i)^T\phi(x_j) \\ &\text{s.t.} \sum^m_{i=1}\alpha_iy_i=0 \\ &\alpha_i\geq0, i=1,2,...,m. \end{aligned}

其中涉及到 ϕ(xi)Tϕ(xj)\phi(x_i)^T\phi(x_j) 的计算，计算比较困难，用函数 κ(xi,xj)\kappa(x_i,x_j) 来代替，即函数

κ(xi,xj)=ϕ(xi)Tϕ(xj)\kappa(x_i,x_j) = \phi(x_i)^T\phi(x_j)

此即为核函数，关于核函数是否存在的问题，有一个核函数定理如下：

令 χ\chi 为输入空间，κ(⋅,⋅)\kappa(·,·) 是定义在 χ×χ\chi \times \chi 上的对称函数，设 κ\kappa 是核函数当且仅当对于任意数据 D={x1,x2,...,xm}D=\{x_1,x_2,...,x_m\} ，“核矩阵” KK 总是半正定的。

K=(κ(x1,x1)κ(x1,x2)⋯κ(x1,xn)κ(x2,x1)κ(x2,x2)⋯κ(x2,xn)⋮⋮⋱⋮κ(xn,x1)κ(xn,x2)⋯κ(xn,xn))K = \begin{pmatrix} \kappa(x_1,x_1) & \kappa(x_1,x_2) & \cdots & \kappa(x_1,x_n) \\ \kappa(x_2,x_1) & \kappa(x_2,x_2) & \cdots & \kappa(x_2,x_n) \\ \vdots & \vdots & \ddots & \vdots \\ \kappa(x_n,x_1) & \kappa(x_n,x_2) & \cdots & \kappa(x_n,x_n) \end{pmatrix}

也就是只要对称函数对应的核矩阵是半正定的，它就可以作为核函数，对于一个半正定核矩阵，总能找到一个相对应的映射空间，也就是任意一个核函数都隐式地定义了一个特征空间（称为“再生核希尔伯特空间”， RKHS）

特征空间的好坏对支持向量机至关重要，故选择核函数十分控妖，必须将样本映射到合适的特征空间，使其尽可能地线性可分，常用核函数有：

1679541327226

svm常用核函数_svm核函数_wolfrevoda的博客-CSDN博客

核函数的组合也是核函数

  • 对于 γ1\gamma_1 和 γ2\gamma_2 均为正数的情况， γ1κ1+γ2κ2\gamma_1\kappa_1 + \gamma_2\kappa_2 也是核函数
  • 核函数的直积也是核函数
  • 对于任意的函数 g(x)g(x) ，g(x)κ1(x,z)g(z)g(x)\kappa_1(x,z)g(z) 也是核函数

软间隔

软间隔允许支持向量机在一些样本上出错，即允许部分样本不满足 yi(ωTxi+b)≥1y_i(\omega^Tx_i+b) \geq 1

此时优化目标变成了：

min⁡ω,b12∣∣ω∣∣2+C∑i=1ml(yi(ωTxi+b)−1)\min_{\omega, b} \frac{1}{2}||\omega||^2+C\sum^m_{i=1}l(y_i(\omega^Tx_i+b)-1)

其中 CC 为常数，ll 为损失函数，常见的损失函数有：

  • hinge 损失：max⁡(0,1,−z)\max(0,1,-z)
  • 指数损失：exp⁡(−z)\exp(-z)
  • 对率损失：log⁡(1+exp⁡(−z))\log(1+\exp(-z))

支持向量回归

传统回归模通常直接基于模型输出 f(x)f(x) 与真实输出 yy 计算损失，而支持向量机则允许计算值和真实值之间有一定的误差 ϵ\epsilon ，也就是仅当预测值和真实值之间的绝对差大于 ϵ\epsilon 时才计算损失，这相当于以 f(x)f(x) 为中心，构建一条宽度为 2ϵ2\epsilon 的间隔带，只要预测值落入其中，即为预测正确。