支持向量机

动机

线性二分类问题，找到最优分类面

最优分类面

• 优点：容忍局部扰动
• 定义：离两类样本最小距离最大
  由定义容易得到，对称；而且是一个min-max问题

拓展

• 拓展至线性不可分问题
• 离群值的处理

最优超平面只由支持向量决定

超平面的求解

问题的重写-有约束的优化问题

原始问题与等价问题。可以归结到凸优化问题。

一般凸优化问题

最小化目标函数；约束不等式组；约束等式组。
约束构成了可行域。
归结到一般的凸优化问题。

使用拉格朗日乘数法求解

对于一个有约束的优化问题，使用拉格朗日乘数法转化到无约束优化问题。
对乘子求拉格朗日函数最大化，使得其满足约束。
再求最小值则转化为原问题。
此时是一个min-max优化问题，不易求解，它的对偶问题max-min

对偶问题

三个定理。
定理1：原始问题是对偶问题的上界。
定理2：在一定条件下，两个问题的最优解相等。
定理3：满足定理2的一定条件，$W^*$是原问题最优解，$\alpha^*$、$\beta^*$是对偶问题最优解，只要它们一起满足KKT条件。

对偶形式计算

非线性问题-核函数

如果原始空间样本特征是有限维的，那么一定存在一个高维特征空间使得样本变得可分。

• 寻找低维向高维映射函数（基函数）
• 利用核函数简化计算，核函数是一类广义内积，是这种映射的隐式表征

常见核函数

• 线性
• 多项式
• RBF
• sigmoid

非线性问题-软间隔

$1-\xi_i$为软间隔，超参数$C$，优化$\xi_i$