SVM（四）非线性决策边界

当数据中存在异常点时，比如上述的情况，导致原先可以用直线a分割的数据现在不得不用b来进行，以保证完美的分割。由此我们引出了非线性决策边界（non-linear decision boundaries）来解决这样的问题。

观察原SVM问题的目标： \[ \min_{w, b} \frac{1}{2}||w|^2 \\\ \text{ s.t. }y^{(i)} \cdot (w^T \cdot x^{(i)}+b) \geq 1, i=1,\ldots,m \] 我们为原公式增加惩罚项，对不同的数据点增加不同的惩罚，使得所有样本能够更好地分割： \[ \min_{w, b} \frac{1}{2}||w|^2+c\sum_{i=1}^m\xi_i, \xi_i\geq0 \] 使得 \[ y^{(i)} \cdot (w^T \cdot x^{(i)}+b) \geq 1-\xi_i, i=1,\ldots,m \] 注意到，我们之前认为$ y^{(i)} (w^T x^{(i)}+b) 1 $是分类正确的，在这里我们允许一部分样本小于1，也就是说明我们允许了一部分样本分类错误。

构建拉格朗日算子： \[ {\cal L}(w, b, \xi, \alpha, \gamma) = \frac{1}{2}||w|^2+c\sum_i\xi_i-\sum_i^m\alpha_i(y^{(i)} (w^T \cdot x^{(i)}+b)-1+\xi_i)-\sum_i^m\gamma_i\xi_i \] 对偶： \[ \max W(\alpha) = \sum_{i=1}\alpha_i-\frac{1}{2}\sum_{i=1}\sum_{j=1}\alpha_i\alpha_jy_iy_j\langle x_i \cdot x_j \rangle \] 跟原先的SVM问题的唯一区别在于其限制条件为： \[ \sum_{i=1}^my^{(i)}\alpha_i=0 \\\ 0 \leq \alpha_i \leq c \] 其收敛条件：

对于大部分数据点：

\[ \alpha_i=0 \Rightarrow y^{(i)} (w^T \cdot x^{(i)}+b) \geq 1 \]
对于异常点：

\[ \alpha_i = c \]
对于最近点：

\[ 0<\alpha_i<c \]

坐标上升法（Coordinate Ascent）

考虑优化问题： \[ \max W(\alpha_1, \alpha_2, ..., \alpha_m) \] 不考虑约束条件，

重复 {

For i = 1 to m: \[ \alpha_i := \arg \max_{\hat{\alpha}_i} W(\alpha_1,\ldots,{\hat{\alpha}}_i,\ldots,\alpha_m) \] } 直到收敛；

这个算法，可以认为是执行了以下这个过程（以m=2为例）：

顺序最小优化算法（Sequential minimal optimization, SMO）

顺序最小优化算法的基本理念就是在坐标上升法的基础上，改成一次性优化其中两个$\alpha$，而固定其他的$m-2$个$\alpha$。

假如我们更新$\alpha_1, \alpha_2$：

因为在之前我们提到: \[ \sum_i^m \alpha_iy^{(i)}=0 \] 于是有： \[ \alpha_1 y^{(1)}+\alpha_2 y^{(2)} = -\sum_{i=3}^m\alpha_iy^{(i)}= \zeta \] 那么 \[ \alpha_1=\frac{\zeta-\alpha_2y^{(2)}}{y^{(1)}} \]

\[ W(\alpha_1, \alpha_2, ..., \alpha_m) = W(\frac{\zeta-\alpha_2y^{(2)}}{y^{(1)}}, \alpha_2, ..., \alpha_m) \]

在非线性决策边界优化问题中，其实$W$是一个关于$\alpha_i$的二次函数，固定其他$\alpha$之后，$W$函数就可以被简化为： \[ a\alpha_2^2+b \alpha_2 + c \] 很容易就能求解。