核函数

上一篇我们说了，对偶之后如果直计算内积的话，复杂度依然很高，取决于映射之后的空间维度，那么有没有办法快速计算内积呢？

这个时候核函数应运而生了，它使得我们可以直接在低维空间计算高维空间的内积，而不需要先映射到高维空间。

常用核

  • 多项式核：$K(v_1,v_2) = (R+<v_1,v_2>)^d$

  • 高斯核（RBF）:$K(v_1,v_2) = exp(-\gamma\lvert v_1-v_2 \rvert^2)$

  • 线性核：$K(v_1,v_2) = <v_1,v_2>$
  • Sigmoid：$K(v_1,v_2) = tanh(\gamma<v_1,v_2>+c)$

Soft-Margin SVM

对于线性不可分的情况，我们可以通过核函数将数据映射到高维空间，使得线性可分的概率大大增加。

但是有的时候数据可能并非线性不可分，而是数据中存在噪声，这个时候如果使用核函数可能会过拟合，比如：

我们可以引入松弛变量，允许我们的数据在一定程度上偏离超平面，但是我们同时希望偏离量越小越好。

其中C是一个参数，用于控制目标函数中两项（“寻找margin最大的超平面”和“保证数据点偏差量最小”）之间的权重。

然后套用之前Hard-Margin SVM的步骤：

  • 拉格朗日乘数法（转化为无约束）

  • 偏导等于0，化简

  • 简化之后的对偶问题

  • 求解(关键是计算b)

Physical Meaning of $\alpha_n$