title: 13. SVM（四）非线性决策边界 date: 2018-07-25 13:53:00 categories: SVM tags: [SVM, 非线性决策边界, 坐标上升法] mathjax: true

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

观察原SVM问题的目标： $$ \min_{w, b} \frac{1}{2}||w|2 \
\text{ s.t. }y{(i)} \cdot (wT \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 (wT \cdot x{(i)}+b) \geq 1-\xi_i, i=1,\ldots,m $$ 注意到，我们之前认为$ y{(i)} \cdot (wT \cdot x{(i)}+b) \geq 1 $是分类正确的，在这里我们允许一部分样本小于1，也就是说明我们允许了一部分样本分类错误。

构建拉格朗日算子： $$ {\cal L}(w, b, \xi, \alpha, \gamma) = \frac{1}{2}||w|2+c\sum_i\xi_i-\sum_im\alpha_i(y{(i)} (wT \cdot x{(i)}+b)-1+\xi_i)-\sum_im\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)} (wT \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_im \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 $$ 很容易就能求解。