两遍读懂支持向量机 SVM (Kernel SVM)数据结构与算法Yongfeng's Blog-

1. Kernel SVM

SVM 算法中 软间隔 SVM 和硬间隔 SVM 是用来求解线性可分 (或勉强线性可分) 的分类问题的，而 Kernel SVM 则是用来求解线性不可分的分类问题的。顾名思义，Kernel SVM 利用 核函数 (Kernel function) 将样本从低维空间 (输入空间) 映射到高维空间 (特征空间) 来进行线性划分。

考虑如下图 (a) 中的例子，假设样本
$x$

x 是 1 维特征向量 (
$xin R$

x∈R，
$x^{(i)}$

x(i)表示第
$i$

i 个样本)，即可看做是
$x$

x 轴上的实数。现在需要将其进行分类。很显然，在一维空间内无法用一条直线将他们区分开，因此这是一个典型的线性不可分问题。于是乎，我们需要再增加一维特征，如
$x^2$

x2 轴，这样一来，我们可以非常轻松的在二维空间上线性分割。这个就是 Kernel SVM 思想的简单体现，即：既然低维空间无法线性分割，那我们就将样本转换到高维空间进行线性分割吧。

此时，摆在我们面前的有两道难题：(1) 如何进行映射？(2) 如何求解高维
$w^*,b^*$

w∗,b∗ 参数？ 对于第一个问题，当然是利用核函数进行维度的转变 (如
$x rightarrow phi(x)$

x→ϕ(x))。对于第二个问题，我们将原先求解软硬间隔 SVM 的优化目标中的
$x$

x 替换为
$phi(x)$

ϕ(x) ，并结合核技巧来求解最终的超平面
$w^*phi(x)+b^*=0$

w∗ϕ(x)+b∗=0。

2. 利用 Kernel 函数进行维度转变

假定映射函数为
$phi(x)$

ϕ(x)，即
$phi:x rightarrow phi(x)$

ϕ:x→ϕ(x)。其中，
$x$

x 表示输入空间样本，为
$p$

p 维向量，将其表示为
$x=(x_1,x_2,…,x_p)^T$

x=(x1​,x2​,...,xp​)T。
$phi(x)$

ϕ(x) 为其映射的高维空间的样本，为
$k$

k 维向量，记为
$phi(x)=(x_1,x_2,…,x_k)^T$

ϕ(x)=(x1​,x2​,...,xk​)T。如下图所示，这里的
$phi$

ϕ 函数将
$p$

p 维向量转换为高维的向量。

我们“惊喜的”发现，在输入空间的点
$x$

x 与高维特征空间的点
$phi(x)$

ϕ(x) 存在这么一个等式，即，

$phi(x^{(i)})·phi(x^{(j)})=(x^{(i)}·x^{(j)}+1)^2$

ϕ(x(i))⋅ϕ(x(j))=(x(i)⋅x(j)+1)2

于是乎，高维向量 (
$phi(x)$

ϕ(x)) 的计算可以用 (
$x$

x) 来表示。可以想象成将会极大的节省计算量。在SVM 中，我们定义一些数学公式为 核函数 (Kernel fucntion)，它们能将输入空间的样本转化为高维空间的形式，同时将高维向量的操作转化为低维向量的操作，从而节省巨大的计算量 (也称为 核技巧 (Kernel trick))。我们将核函数定义为
$kappa(x^{(i)},x^{(j)})$

κ(x(i),x(j))，其输入是两个向量
$x^{(i)},x^{(j)}$

x(i),x(j)，输出是
$x^{(i)}$

x(i) 和
$x^{(j)}$

x(j) 的内积，即，

$kappa(x^{(i)},x^{(j)})=phi(x^{(i)})·phi(x^{(j)})$

κ(x(i),x(j))=ϕ(x(i))⋅ϕ(x(j))

常见的核函数包括多项式核函数 (Polynomial Kernel)，高斯核函数 (Gaussion Kernel) 等，这些函数都有上述性质。全部核函数请参照博客 Kernel Functions¹ 。

• Polynomial Kernel：
  $kappa(x_i,x_j)=(x_i·x_j+1)^d$

  κ(xi​,xj​)=(xi​⋅xj​+1)d，其中
  $dgeq0$

  d≥0

• Gaussion Kernel：
  $kappa(x_i,x_j)=exp(-frac{||x_i-x_j||^2}{2sigma^2})$

  κ(xi​,xj​)=exp(−2σ2∣∣xi​−xj​∣∣2​) ，其中
  $sigma>0$

  σ>0

• Gaussion Radial Basis Kernel：
  $kappa(x_i,x_j)=exp(-gamma||x_i-x_j||^2)$

  κ(xi​,xj​)=exp(−γ∣∣xi​−xj​∣∣2)，其中
  $gamma>0$

  γ>0

• Hyperbolic tangent kernel：
  $kappa(x_i,x_j)=tanh(kx_i·x_j+c)$

  κ(xi​,xj​)=tanh(kxi​⋅xj​+c)，其中
  $k>0,c<0$

  k>0,c<0

注意，每一种核函数对应着一种映射方式
$phi$

ϕ。比如 Polynomial Kernel 中，输入样本
$x$

x 可以转换为，

$phi(x)=(xi,sqrt{2gammaxi}(x_1),sqrt{2gammaxi}(x_2),…,sqrt{2gammaxi}(x_p),gamma (x_1)^2,gamma (x_2)^2,…,gamma (x_p)^2)^T$

ϕ(x)=(ξ,2γξ​(x1​),2γξ​(x2​),...,2γξ​(xp​),γ(x1​)2,γ(x2​)2,...,γ(xp​)2)T

在一些教材中，人们提出了一种叫 线性核函数 (Linear Kernel)² 的概念，即
$kappa(x^{(i)},x^{(j)})=x^{(i)}·x^{(j)}$

κ(x(i),x(j))=x(i)⋅x(j)。事实上，当 Kernel SVM 使用这个核函数时，并没有进行维度的变化。换句话说，如果 Kernel SVM 使用 Linear Kernel，其效果等价于之前的 硬间隔 SVM。

3. 求解高维空间中的线性参数
$w^*,b^*$

w∗,b∗

原先在原空间上，我们推导的 SVM 最优化问题的表达形式为，

$L(w,b,lambda) = frac{1}{2}||w||^2 + sum_{i}^{m}lambda_i[1-y^{(i)}(w^Tx^{(i)}+b)] \ s.t. lambda_i geq 0$

L(w,b,λ)=21​∣∣w∣∣2+i∑m​λi​[1−y(i)(wTx(i)+b)]s.t. λi​≥0

现在通过映射函数
$phi$

ϕ 将
$x$

x 映射到
$phi(x)$

ϕ(x) 之后，优化问题变成，

$L(w,b,lambda) = frac{1}{2}||w||^2 + sum_{i}^{m}lambda_i[1-y^{(i)}(w^Tphi(x^{(i)})+b)] \ s.t. lambda_i geq 0$

L(w,b,λ)=21​∣∣w∣∣2+i∑m​λi​[1−y(i)(wTϕ(x(i))+b)]s.t. λi​≥0

我们将其转换为对偶问题，求
$w,b$

w,b 的偏导，得到

$frac{partial L}{partial w} = w-sum_{i=1}^{m}lambda_iy^{(i)}phi(x^{(i)}), frac{partial L}{partial b} = -sum_{i=1}^{m}lambda_iy^{(i)}$

∂w∂L​=w−i=1∑m​λi​y(i)ϕ(x(i)),  ∂b∂L​=−i=1∑m​λi​y(i)

令
$w,b$

w,b 的偏导数为 0，我们得到
$w^*=sum_{i=1}^mlambda_iy^{(i)}phi(x^{(i)})$

w∗=∑i=1m​λi​y(i)ϕ(x(i)) 以及
$sum_{i=1}^mlambda_iy^{(i)}=0$

∑i=1m​λi​y(i)=0。我们将它们带入到
$L$

L 中可得到其最小值
$theta(lambda)=L_{min}(w,b,lambda)$

θ(λ)=Lmin​(w,b,λ)，最优化问题转变为求解
$theta(lambda)$

θ(λ) 的最大值问题，即

$theta(lambda) = -frac{1}{2}sum_{i=1}^{m}sum_{j=1}^m lambda_ilambda_jy^{(i)}y^{(j)}[phi(x_i)]^Tphi(x_j) + sum_{i=1}^mlambda_i \ s.t. sum_{i=1}^mlambda_iy^{(i)}=0, lambda_i geq 0, i=1…m.$

θ(λ)=−21​i=1∑m​j=1∑m​λi​λj​y(i)y(j)[ϕ(xi​)]Tϕ(xj​)+i=1∑m​λi​s.t.i=1∑m​λi​y(i)=0,  λi​≥0,i=1...m.

由于
$phi(x_i), phi(x_j)$

ϕ(xi​),ϕ(xj​) 都是 (nx1) 维向量，因此上式中的
$[phi(x_i)]^Tphi(x_j)$

[ϕ(xi​)]Tϕ(xj​) 也可以写为内积的形式
$phi(x_i)·phi(x_j)$

ϕ(xi​)⋅ϕ(xj​)，故
$theta(lambda)$

θ(λ) 也可以写成
$theta(lambda)= -frac{1}{2}sum_{i=1}^{m}sum_{j=1}^m lambda_ilambda_jy^{(i)}y^{(j)}phi(x_i)phi(x_j) + sum_{i=1}^mlambda_i$

θ(λ)=−21​∑i=1m​∑j=1m​λi​λj​y(i)y(j)ϕ(xi​)ϕ(xj​)+∑i=1m​λi​。

此时利用我们的核技巧
$kappa(x_i,x_j)=phi(x_i)·phi(x_j)$

κ(xi​,xj​)=ϕ(xi​)⋅ϕ(xj​)，将
$theta(lambda)$

θ(λ) 写作，

$theta(lambda) = -frac{1}{2}sum_{i=1}^{m}sum_{j=1}^m lambda_ilambda_jy^{(i)}y^{(j)}kappa(x_i,x_j) + sum_{i=1}^mlambda_i$

θ(λ)=−21​i=1∑m​j=1∑m​λi​λj​y(i)y(j)κ(xi​,xj​)+i=1∑m​λi​

此时带入任一合理的核函数
$kappa(x_i,x_j)$

κ(xi​,xj​) 即可算出
$theta(lambda)$

θ(λ)，与之前类似的，利用 SMO 算法，我们可以解出使得
$theta(lambda)$

θ(λ) 最大的
$lambda^*$

λ∗ 的值。

接着，我们找到位于决策平面上的点
$phi(x^{(s)})$

ϕ(x(s))，并将其带入方程
$y^{(s)}((w^*)^Tphi(x^{s})+b)=1$

y(s)((w∗)Tϕ(xs)+b)=1，我们可以计算出
$b^*$

b∗ 的值，

$b^*=y^{(s)}-sum_{i=1}^{m}lambda_iy^{(i)}phi(x^{(i)})phi(x^{(i)})=y^{(s)}-sum_{i=1}^{m}lambda_iy^{(i)}kappa(x^{(i)},x^{(s)})$

b∗=y(s)−i=1∑m​λi​y(i)ϕ(x(i))ϕ(x(i))=y(s)−i=1∑m​λi​y(i)κ(x(i),x(s))

于是乎，超平面
$(w^*)^Tphi(x)+b=0$

(w∗)Tϕ(x)+b=0，可以写为，

$sum_{i=1}^mlambda_iy^{(i)}phi(x^{(i)})phi(x)+b^*=0$

i=1∑m​λi​y(i)ϕ(x(i))ϕ(x)+b∗=0

将
$w^*,b^*$

w∗,b∗ 全部带入上式，最终超平面可以写为，

$sum_{i=1}^mlambda_iy^{(i)}kappa(x^{(i)},x)+y^{(s)}-sum_{i=1}^{m}lambda_iy^{(i)}kappa(x^{(i)},x^{(s)})=0$

i=1∑m​λi​y(i)κ(x(i),x)+y(s)−i=1∑m​λi​y(i)κ(x(i),x(s))=0

通过上述可以知道，通过核技巧，我们甚至不用知道映射的具体细节
$phi(x)$

ϕ(x)，而直接计算出了高维空间中的线性
$w^*,b^*$

w∗,b∗，这些都是核函数的功劳。在应用中，我们倾向于将核函数看做一个黑盒子而不去理解其内部原理，但一定要理解 kernel SVM 的思想，即将输入空间转换为高维空间来进行线性划分。