支持向量机

支持向量机是一种二分类模型。它的基本模型是定义在特征空间上的间隔最大化的线性分类器，间隔最大是他有区别于感知机。
支持向量机由简至繁：线性可分支持向量机，线性支持向量机和非线性支持向量机。

1.线性可分支持向量机与硬间隔最大化

分离超平面： $w^*$ ·x+ $b^*$ =0

分类决策函数：f(x)=sign( $w^*$ ·x+ $b^*$ )

  函数间隔： $r_i$ = $y_i$ (w· $x_i$ +b)
  几何间隔： $r_i$ = $y_i$ ( $\frac{1}{||w||}$ · $x_i$ + $\frac{b}{||w||}$ )
  如果超平面参数w和b成比例的改变，函数间隔也会按比例改变，而几何间隔不变。

对训练数据集找到几何间隔最大的超平面意味着以充分大的确信度对训练数据进行分类
max r —> max $r^{'}$ /||w|| —> min $\frac{1}{2}$ $||w||^2$

(1)最大间隔算法：
输入：线性可分训练数据集T
输出：最大间隔分离超平面和分离决策函数

构造并求解约束最优化问题：
$min_{w,b}$ $\frac{1}{2}$ $||w||^2$
s.t. $y_i$ (w· $x_i$ +b)-1≥0 ,i=1,2,…,N
由此得到分离超平面：
$w^*$ ·x+ $b^*$ =0

分类决策函数：
f(x)=sign( $w^*$ ·x+ $b^*$ )

(2)例题

(1)对偶算法
输入：同原始算法
输出：同原始算法

构造并求解约束最优化问题:
$min_a$    $\frac{1}{2}$ $\sum^{N}_{i=1}$ $\sum^{N}_{j=1}$ $a_i$ $a_j$ $y_i$ $y_j$ ( $x_i$ · $x_j$ ) - $\sum^{N}_{i=1}$ $a_i$
s.t.    $\sum^{N}_{i=1}$ $a_i$ $y_i$ =0
$a_i$ ≥0   ,i=1,2,…,N
求解最优解 $a^*$ =( $a^*_1$ , $a^*_2$ ,…, $a^*_N$ )
计算:
$w^*$ = $\sum^{N}_{i=1}$ $a^*_i$ $y_i$ $x_i$
$b^*$ = $y_j$ - $\sum^{N}_{i=1}$ $a^*_i$ $y_i$ ( $x_i$ · $x_j$ )
由此得到分离超平面：
$w^*$ ·x+ $b^*$ =0

分类决策函数：
f(x)=sign( $w^*$ ·x+ $b^*$ )

(2)例题