支持向量机

发表于

支持向量机

间隔与支持向量

考虑这样的训练样本\(D = {(x_1, y_1), (x_2, y_2), ... , (x_m, y_m)}, y_i \in {-1, +1}\)。分类学习最重要的基于训练集D找到一个划分超平面，使得不同类别的样本能够分考。虽然划分平面可能很多，但我们应该尽量找到"位于正中间"的平面，使得robust最好。

在样本空间中，划分超平面可以这样描述： \[ w^Tx + b = 0 \] 其中\(w=(w_1;w_2;...;w_d)\)为法向量，决定平面的方向，而b则是位移，决定的事平面与原点的距离。

样本空间中任意点x到平面的距离记为： \[ r = \frac {|w^Tx+b|} {||w||} \] 假设平面能够正确分类，那么对于 \[ w^T x_i + b \geq +1, y_i +1 \\ w^T x_i + b \leq -1, y_i -1 \] 根据这个公式可以得知，距离平面最近的点使得上式成立，那么这几个样本就成为支持向量，两个异类支持向量到平面的距离之和为： \[ \gamma = \frac {2} {||w||} \] 这就是间隔(margin)。

但如果我们希望找到具有最大间隔的平面，应该要最大化\(\gamma\)，则使得\(\frac{1}{2}{||w||}^2\)最大化。

这就是support vector machine(SVM)的基本模型。

对偶问题

TODO

核函数

在现实生活中，很可能无法找到使得原始样本空间可分的超平面，比如抑或问题就是这样。但我们可以将样本从原始空间映射到一个更高维空间，使得样本在这个特征空间内是线性可分。

经过映射后，假设超平面模型为： \[ f(x) = w^T \Phi(x) + b \] 在利用对偶问题求解时会涉及得到计算内积——\(\Phi(x)^T\Phi(x)\)，由于映射后的特征空间可能维度很高，甚至是无穷维，要想直接计算通常是困难的。因此可以设计这样一个函数，即\(x_i\)与\(x_j\)在特征空间的内积等于它们在原始空间中通过函数k计算的结果。重写解为： \[ f(x) = w^T\Phi(x) + b \\ =\sum_{i=1}^{m}\alpha_iy_i\Phi(x_i)^T\Phi(x) + b \\ =\sum_{i=1}^{m}\alpha_iy_ik(x, x_i) + b \] 但这样还存在一个问题，在不知道$ (x) $形式时该怎么得到核函数呢？

有这么一个定理，如果有这么一个对称函数，它在输入空间中对应的核矩阵是半正定的，那么它就能作为核函数使用。（不懂？？）

以下为一些常见和核函数：

  • 线性核：\(k(x_i, x_j) = x_i^Tx_i\)
  • 多项式核：\(k(x_i, x_j) = (x_i^Tx_j)^d\)
  • 高斯核：\(k(x_i, x_j) = exp(- \frac{ || x_i - x_j ||^2 }{2\sigma^2})\)
  • 拉普拉斯核：\(k(x_i, x_j) = exp(- \frac{ || x_i - x_j ||^2 }{\sigma})\)
  • sigmoid核：\(k(x_i, x_j) = tanh(\beta x_i^T x_j + \theta)\)

软间隔与正则化

todo

支持向量回归

这样的训练样本\(D = {(x_1, y_1), (x_2, y_2), ... , (x_m, y_m)}\)，希望学得一个回归模型，使得f(x)与y尽可能接近，在传统的回归模型中，我们是基于模型输出f(x)与真实输出y之间的差别来计算损失，在这种情况中当且仅当f(x)与y完全相同时，损失才为零。

但是对于SVR，假设我们能容忍f(x)与y之间最多有\(\epsilon\)的偏差，这相当于以f(x)为中心，构建了一个宽度为\(2\epsilon\)的间隔带，若训练样本落入间隔带，则认为是被预测正确的。

于是，SVR问题可以转化为：

\[ min_{w, b} \frac{1}{2}||w||^2+C\sum_{i=1}^{m}\ell_{\epsilon}(f(x_i)-y_i) \\ \]

\[ f(x)=\left\{ \begin{aligned} 0, if |z| \le \epsilon \\ |z| - \epsilon,otherwise \\ \end{aligned} \right. \]

引入松弛变量： \[ min_{w, b, \xi_{i2}, \xi_{i1}} \frac{1}{2}||w||^2+C\sum_{i=1}^{m}(\xi_{i2}+\xi_{i1}) \]

通过引入拉格朗日乘子，并对目标参数求偏导，最后得到SVR表示为： \[ f(x) = \sum_{i=1}^m (\alpha_{i1}-\alpha_{i2})k(x, x_i)+b \]

核方法

todo