Step-1. 两遍读懂支持向量机 SVM (软硬 SVM) Step-2. 两遍读懂支持向量机 SVM (Kernel SVM) Step-3. 两遍读懂支持向量机 SVM (一些细节)

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

考虑如下图 (a) 中的例子，假设样本 x x x 是 1 维特征向量 ( x ∈ R x\in R x∈R， x ( i ) x^{(i)} x(i)表示第 i i i 个样本)，即可看做是 x x x 轴上的实数。现在需要将其进行分类。很显然，在一维空间内无法用一条直线将他们区分开，因此这是一个典型的线性不可分问题。于是乎，我们需要再增加一维特征，如 x 2 x^2 x2 轴，这样一来，我们可以非常轻松的在二维空间上线性分割。这个就是 Kernel SVM 思想的简单体现，即：既然低维空间无法线性分割，那我们就将样本转换到高维空间进行线性分割吧。

此时，摆在我们面前的有两道难题：(1) 如何进行映射？(2) 如何求解高维 w ∗ , b ∗ w^*,b^* w∗,b∗ 参数？ 对于第一个问题，当然是利用核函数进行维度的转变 (如 x → ϕ ( x ) x \rightarrow \phi(x) x→ϕ(x))。对于第二个问题，我们将原先求解软硬间隔 SVM 的优化目标中的 x x x 替换为 ϕ ( x ) \phi(x) ϕ(x) ，并结合核技巧来求解最终的超平面 w ∗ ϕ ( x ) + b ∗ = 0 w^*\phi(x)+b^*=0 w∗ϕ(x)+b∗=0。

假定映射函数为 ϕ ( x ) \phi(x) ϕ(x)，即 ϕ : x → ϕ ( x ) \phi:x \rightarrow \phi(x) ϕ:x→ϕ(x)。其中， x x x 表示输入空间样本，为 p p p 维向量，将其表示为 x = ( x 1 , x 2 , . . . , x p ) T x=(x_1,x_2,...,x_p)^T x=(x1​,x2​,...,xp​)T。 ϕ ( x ) \phi(x) ϕ(x) 为其映射的高维空间的样本，为 k k k 维向量，记为 ϕ ( x ) = ( x 1 , x 2 , . . . , x k ) T \phi(x)=(x_1,x_2,...,x_k)^T ϕ(x)=(x1​,x2​,...,xk​)T。如下图所示，这里的 ϕ \phi ϕ 函数将 p p p 维向量转换为高维的向量。

我们“惊喜的”发现，在输入空间的点 x x x 与高维特征空间的点 ϕ ( x ) \phi(x) ϕ(x) 存在这么一个等式，即，

ϕ ( x ( i ) ) ⋅ ϕ ( x ( j ) ) = ( x ( i ) ⋅ x ( j ) + 1 ) 2 \phi(x^{(i)})·\phi(x^{(j)})=(x^{(i)}·x^{(j)}+1)^2 ϕ(x(i))⋅ϕ(x(j))=(x(i)⋅x(j)+1)2

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

κ ( x ( i ) , x ( j ) ) = ϕ ( x ( i ) ) ⋅ ϕ ( 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 Functions1 。