算法基本功：SVM part2 - 2019-03-02

上一篇文章推导了针对不等式约束优化问题的KKT条件。

接下来具体到svm 问题上推导: 只有支持向量才决定最优解。

svm 要解决的问题是：找到使得几何间隔最大的分类超平面。

数学表达为：

min $\frac{1}{2}| |x||^2$

subject to: $1 - y_i( wx_i +b) <= 0$

转化为拉格朗日表达式：

L: $\frac{1}{2}| |x||^2$ + $\Sigma _i \alpha _i (1-(y_i(wx+b)))$

kkt 条件：

1. $\alpha _i (1-(y_i(wx+b)))$ <= 0 # g(x*) <=0

2. 同右注释 # L的梯度（在W,b上） = 0， $\lambda >= 0$ 。

3. $\alpha _i （1-（y_i* (wx_i +b )））= 0$ # $\lambda$ g(x*) = 0

对于第三个条件，结合不等式约束的两类子情况（上一篇文章SVM-part1: KKT条件）

当系数严格大于0: 必有 g(x*) = 0；

即 $y_i(wx_i+b)=1$ , 即样本 $（x_i, y_i）$ 为支持向量，在‘那’两条分类边界上（你懂的）。

当系数等于0: 必有g(x*) 严格小于0（#即最优解在可行域内，而非边界.）

即 $y_i(wx_i+b) > 1$ 。

利用第二个条件，我们求出：

2.1: W* = $\Sigma_i \alpha _ix_iy_i$ # L对w 求偏导数，令其为0

2.2: $\Sigma_i \alpha _i y_i = 0$ # # L对b求偏导数，令其为0

2.3 $y_j$ = W* $x_j$ + b*, 故 b* = $y_j - \Sigma _i\alpha ixiyi *x_j$

算法基本功：SVM part2 - 2019-03-02

算法基本功：SVM part2 - 2019-03-02

综合上述两个推导，我们可以说：最优解W*仅仅是全部支持向量（且形式为 $x_iy_i$ ）的线性组合,与非支持向量无关。

下一章详细说说对偶问题。

推荐阅读更多精彩内容

算法基本功：SVM part2 - 2019-03-02

综合上述两个推导，我们可以说：最优解W*仅仅是全部 支持向量（且形式为） 的线性组合,与非支持向量无关。

下一章详细说说对偶问题。

推荐阅读更多精彩内容

综合上述两个推导，我们可以说：最优解W*仅仅是全部支持向量（且形式为 $x_iy_i$ ）的线性组合,与非支持向量无关。