支持向量机SVM

2019-11-01 本文已影响0人陈文瑜

概述（Support Vector Machines）

可以做有监督学习、无监督学习

分类问题，聚类问题 (SVC)，在输入空间做一个映射，映射到一个更高维的空间去做分类。

$L_2$ 范数

欧几里得距离

点到超平面 $g(x) = w\cdot x +b$ 的距离为 $M= \frac {|g(x)|}{||w||}$ ，则圆点到超平面距离为 $\frac{|b|}{||w||}$

评估分类好坏

是否无偏

margin，边际，能平移的距离，目标是最大化margin。

如何描述出margin

+1 ， -1代表两类问题。则有 $g(x)>=1,g(x)<=-1两类$ ，则 $M=\frac {2}{||w||}$

前提条件是把每个样本都分对

则有 $y_i(wx_i+b)-1\geq 0$

我们的目标是最大化Margin

也就是 $max M = \frac {2}{||w||} \Rightarrow min \frac{1}{2} w^Tw$

完整的表述

在条件 $y_i(w\cdot x_i +b) \geq 1$ 下，最小化 $\Phi(x) = \frac12 w^Tw$

求解方法拉格朗日乘子法

有： $L_p = \frac12 ||w||^2 - \sum _{i=1}^l a_iy_i(w\cdot x_i +b) + \sum_{i=1}^l a_i$
对w和b求导后有：
$\frac {\partial L_p}{\partial w} = 0 \quad \Rightarrow \quad w= \sum_{i=1}^l a_iy_ix_i$
$\frac {\partial L_p}{\partial b} = 0 \quad \Rightarrow \quad \sum_{i=1}^l a_iy_i = 0$
将上式带入到 $L_p$ 中，可以得到其对偶函数：
$L_D = \sum_i a_i - \frac12 \sum_{i,j}a_ia_jy_iy_jx_i \cdot x_j = \sum_i a_i - \frac12 \alpha^T H\alpha \quad where \quad H_{ij} = y_iy_jx_i \cdot x_j$
前提是： $\sum_i \alpha_i y_i =0 \quad \& \quad \alpha_i \geq 0$