SVM的简单理解

  对于经典的SVM以及核函数等概念，总是感觉有点陌生，平常都是直接调用现成的第三方库，没有深究其原理， 但该学还是得学，不学不行啊

问题：

  给定训练样本集 $D=(x_1,y_1),(x_2,y_2),...,(x_n,y_n)$D=(x1​​x1​​​x1​,y1​),(x2​​x2​​​x2​,y2​),...,(xn​​xn​​​xn​,yn​)，其中 $y_i\in \{-1,+1\}$yi​∈{−1,+1}（这里为什么是-1而不是0，主要是为了推出后面的公式）。在此假定样本集线性可分，即能在样本空间中找到一个超平面（ $x$xxx为二维时，该划分平面为直线； $x$xxx三维时为平面），将不同类别的样本分开。如下图所示， $x$xxx为二维向量，此时应该找到一条位于两类训练样本正中间的直线 $A{x}_1+B{x}_2+C=0$Ax1​+Bx2​+C=0，比较理想的即红色的那条

在样本空间中，划分超平面为
${\omega }^{T}x+b=0$ωωωTxxx+b=0
其中法向量 ${\omega }^T=\{{\omega }_1,{\omega }_2,...,{\omega }_n\}$ωωωT={ω1​,ω2​,...,ωn​}决定超平面的方向； $b$b为位移项，决定了原点到超平面的距离。类似于点到平面的距离，对于样本空间中的任意点 $x$xxx到该超平面的距离为
$r=\frac{\mid {\omega }^{T}x+b\mid }{\mid \mid \omega \mid \mid }$r=∣∣ωωω∣∣∣ωωωTxxx+b∣​
对于 $y_i=-1$yi​=−1，有 ωωωTxi​​xi​​​xi​+b<0；对于 $y_i=1$yi​=1，有 ${\omega }^T{x}_i+b>0$ωωωTxi​​xi​​​xi​+b>0。当线性可分时，存在 $\omega ，b$ωωω，b使得下面成立
$\{\begin{array}{c}{\omega }^T{x}_i+b\ge +1，y_i=1\\ {\omega }^T{x}_i+b\le -1，y_i=-1.\end{array}${ωωωTxi​​xi​​​xi​+b≥+1，yi​=1ωωωTxi​​xi​​​xi​+b≤−1，yi​=−1.​
使得上面两个不等式中的等号成立的点被称作支持向量（可以理解为不同类别的样本向量撑起了这个超平面），且两个不同类别的支持向量到超平面的距离之和如下，且被称为间隔
$\gamma =\frac{2}{\mid \mid \omega \mid \mid }$γ=∣∣ωωω∣∣2​
找最优的划分超平面即寻找 $\omega ，b$ωωω，b使得间隔 $\gamma$γ最大，等价于最小化 $\mid \mid \omega \mid \mid$∣∣ωωω∣∣。因此，原问题可以转化为一个凸二次规划问题，具体可以使用凸优化技术，比如拉格朗日数乘数法等进行求解：
ω, bargmin​21​∣∣ωωω∣∣s.t.yi​(ωωωTxi​​xi​​​xi​+b)≥1,i=1,2,...,n

核函数

  上文所说的都是基于训练样本线性可分的前提下，而当样本线性不可分时，此时在原样本空间无法找到一个超平面能将样本正确de划分开来（比如下图的“异或”问题）。

对于这样的问题，可以将原始空间映射到一个更加高维的空间，原本在低维空间不可分的样本在更加高维的空间线性可分。例如下图，将“异或”问题对应的原始二维空间映射到一个合适的三维空间，就能找到一个合适的超平面。而且有，如果原始空间是有限维，即特征数量有限，则一定存在更加高维的空间使得样本可分。

$\varphi \left(x\right)$ϕ(x)表示一种非线性映射关系，表示将原来的 $x$x映射到更高维的特征空间，在新的特征空间划分超平面所对应的模型变为
$f\left(x\right)={\omega }^T\varphi \left(x\right)+b$f(x)=ωωωTϕ(xxx)+b
在求解新模型时，会涉及到到 $\varphi {\left(x_i\right)}^T\varphi \left(x_j\right)$ϕ(xi​​xi​​​xi​)Tϕ(xj​​xj​​​xj​)的计算，即 $x_i和x_j$xi​​xi​​​xi​和xj​​xj​​​xj​映射到新的特征空间之后的内积，由于映射后的空间维度更大（可能无穷维），因此直接计算内积 $\varphi {\left(x_i\right)}^T\varphi \left(x_j\right)$ϕ(xi​​xi​​​xi​)Tϕ(xj​​xj​​​xj​)通常比较困难，因此，核函数(kernel trick)被提出来解决这个问题。核函数是指，低维输入空间存在函数 $\kappa$κ，它恰好等于在高维空间中的这个内积，这样就避免了复杂的非线性变换以及高维内积的计算，公式如下所示。
κ(xi​​xi​​​xi​,xj​​xj​​​xj​)=<ϕ(xi​​xi​​​xi​),ϕ(xj​​xj​​​xj​)>=ϕ(xi​​xi​​​xi​)Tϕ(xj​​xj​​​xj​)
当 $\varphi (\ast )$ϕ(∗)已知，则可以求出对应的 $\kappa (\ast ,\ast )$κ(∗,∗)，但问题是我们往往不知道 $\varphi (\ast )$ϕ(∗)是什么形式，而且我们通常也不会去显式地找到这个 $\varphi (\ast )$ϕ(∗)。若核函数的选择不合适，则样本被映射到的空间仍然不能构造出一个好的划分超平面，因此核函数的选择至关重要。下面是常用的几种核函数：