核函数

在逻辑回归中，我们会通过多项式扩展来处理非线性分类问题：
$h_θ(x)=θ_0+θ_1x_1+θ_2x_2+θ_3x_1x_2+θ_4x^2_1+θ_5x^2_2+⋯$hθ​(x)=θ0​+θ1​x1​+θ2​x2​+θ3​x1​x2​+θ4​x12​+θ5​x22​+⋯

假设我们令：
$f_1=x_1,f_2=x_2,f_3=x_1x_2,f_4=x^2_1,f_5=x^2_2$f1​=x1​,f2​=x2​,f3​=x1​x2​,f4​=x12​,f5​=x22​

则预测函数为：
$h_θ(x)=θ_0+θ_1f_1+θ_2f_2+θ_3f_3+⋯$hθ​(x)=θ0​+θ1​f1​+θ2​f2​+θ3​f3​+⋯

但多项式回归所带来的高阶项不一定作用明显，针对这一问题，SVM 不会引入高阶项来作为新的特征，而是会选择一些标记点（landmark），并将样本 $x$x 与标记点 $l^{(i)}$l(i) 的相似程度作为新的训练特征 $f_i$fi​ ：
$f_i=similarity(x,l^{(i)})$fi​=similarity(x,l(i))

距离度量的方式就称之为核函数（Kernel），最常见的核函数是高斯核函数（Gaussian Kernel）：
$f_i=exp(\frac {−||x−l^{(i)}||^2}{2δ^2})$fi​=exp(2δ2−∣∣x−l(i)∣∣2​)

在高斯核中，注意到：

• 如果样本与标记点足够接近，即 x≈l(i) ，则：
  $f≈exp(−\frac {0^2}{2δ^2})≈1$f≈exp(−2δ202​)≈1

• 如果样本远离标记点，则：
  $f≈exp(−\frac {(large\ number)^2}{2δ^2})≈0$f≈exp(−2δ2(large number)2​)≈0

这一关系可以被如下的热力图所反映：

在使用高斯核函数前，需要做特征缩放（feature scaling），以使 SVM 同等程度地关注到不同的特征。

标记点选取

假定我们有如下的数据集：
$(x^{(1)},y^{(1)})，(x^{(2)},y^{(2)})，(x^{(3)},y^{(3)})，⋯，(x^{(m)},y^{(m)})$(x(1),y(1))，(x(2),y(2))，(x(3),y(3))，⋯，(x(m),y(m))

我们就将每个样本作为一个标记点：
$l^{(1)}=x^{(1)}，l^{(2)}=x^{(2)}，l^{(3)}=x^{(3)}，⋯，l^{(m)}=x^{(m)}$l(1)=x(1)，l(2)=x(2)，l(3)=x(3)，⋯，l(m)=x(m)

则对于样本 $(x^{(i)},y^{(i)})$(x(i),y(i)) ，我们计算其与各个标记点的距离：
$f^{(i)}_1=sim(x^{(i)},l^{(1)})$f1(i)​=sim(x(i),l(1))$f^{(i)}_2=sim(x^{(i)},l^{(2)})$f2(i)​=sim(x(i),l(2))$⋮$⋮$f^{(i)}_m=sim(x^{(i)},l^{(3)})$fm(i)​=sim(x(i),l(3))

得到新的特征向量： $f∈\R^{m+1}$f∈Rm+1
$f=\left( \begin{matrix} f_0 \\ f_1 \\ f_2 \\ ⋮ \\ f_m \end{matrix} \right)\quad 其中f_0=1$f=⎝⎜⎜⎜⎜⎜⎛​f0​f1​f2​⋮fm​​⎠⎟⎟⎟⎟⎟⎞​其中f0​=1

则具备核函数的 SVM 的训练过程如下：
$\min_θC[∑_{i=1}^m y^{(i)}cost_1(θ^Tf^{(i)})+(1−y^{(i)})cost_0(θ^Tf^{(i)})]+\frac12∑_{j=1}^nθ^2_j$θmin​C[i=1∑m​y(i)cost1​(θTf(i))+(1−y(i))cost0​(θTf(i))]+21​j=1∑n​θj2​