2.支持向量机.md

1.支持向量机理论知识

1.1 概述

支持向量机是一种二分类模型，它的基本模型是定义在特征空间上的间隔最大的线性分类器。

• 线性可分的支持向量机
• 线性支持向量机
• 非线性支持向量机

1.2 线性可分支持向量机-硬间隔支持向量机

训练集 $D = {(x^1,y^1),...,(x^m,y^m)}$,其中x^i=(x_1^i,x_2^i,...x_n^i)为第i个样本的n个特征$, $y_i\subset{{-1,1}}$ 给定线性可分的训练集，通过间隔最大化或等价求解相应的凸二次规划问题等到的分离的超平面:

$$ \begin{aligned} &w^.x+b=0\ &f(x) = sign(w^.x+b) 分类决策函数 \end{aligned} $$

函数间隔与几何间隔 $$ \begin{aligned} &\hat{r}_i = y_i*(w.x+b) : 对于每一个样本i的函数间隔\ &\hat{r} = \min_i{y_i*(w.x+b)} 所有样本函数间隔最小值\ &r_i = \frac{y_i*(w.x+b)}{||w||} 几何间隔 \ &r = \min_i\frac{y_i*(w.x+b)}{||w||} 几何间隔最小值 \

\end{aligned} $$

支持向量机的优化问题是最大化几何间隔中的最小值即：

$$ \begin{aligned} &\max_{w,b} r \ &s.t\quad \frac{y_i(w*x+b)}{||w||}>=r \end{aligned} $$ 取$\hat{r_i}=1$,同时最大化改成最小化，则公式可改写为：

$$ \begin{aligned} &\min\frac{1}{2}||w||^2 \\ &s.t.\quad y_i*(w*x) - 1 >= 0 对于所有样本 \end{aligned} $$

2. 对偶问题的求解方式

优点：

• 1. 对偶问题更容易求解
• 2. 可以很自然的引用核函数

$$ \begin{aligned} L(w,b,\alpha) &= \frac{1}{2}||w||^2 + \sum_i^m\alpha_i[1-y_i*(wx_i+b)] \quad\alpha为拉格朗日乘子\ 求解min_{w,b}L(w,b,\alpha): \ \triangledown_{w} &= w - \sum_i^m\alpha_iy_ix_i = 0 \ \triangledown_{b} &= -\sum_i^m \alpha_iy_i = 0 \ 将w,b带入L(w,b,\alpha）: \ L(w,b,\alpha） &= \frac{1}{2}\sum_i^m\sum_j^m\alpha_i\alpha_jx_ix_jy_iy_j - \sum_i^m\alpha_iy_i(wx_i+b) + \sum_i^m\alpha_i\ &= -\frac{1}{2}\sum_i^m\sum_j^m\alpha_i\alpha_jx_ix_jy_iy_j + \sum_i^m\alpha_i \ \end{aligned} $$ 所以问题变成对偶问题的求解最小化： $$ \begin{aligned} &\min_\alpha \frac{1}{2}\sum_i^m\sum_j^m\alpha_i\alpha_jx_ix_jy_iy_j - \sum_i^m\alpha_i \ &s.t.\quad\sum_i^m \alpha_iy_i = 0 \ &\qquad\alpha_i>=0\quad i=1,..m \end{aligned} $$

设$\alpha^\star=(\alpha_1^\star,...\alpha_m^\star)$为对偶问题的解，则存在下标$j$,$\alpha_j^\star>0$,可求解$w,b$:

$$ \begin{aligned} w^\star &= \sum_i^m\alpha_i^{\star}y_ix_i\\ b^\star &= y_j - \sum_i^m\alpha_i^{\star}y_ix_ix_j \end{aligned} $$

所以可求得分离超平面: $$ \begin{aligned} &\sum_i^m\alpha_i^{\star}y_ix_ix + b^\star = 0\ &f(x) = sign(\sum_i^m\alpha_i^{\star}y_ix_ix + b^\star)\ &其中\alpha_i^\star>=0为支持向量 \end{aligned} $$

1.3 线性支持向量机-软间隔支持向量机

对于线性不可分问题，不满足函数间隔$y_i(w.x_i+b)>=1$这一条件，因此可以引入一个松弛变量使得函数间隔加上松弛变量大于等于1，因此约束的条件变成了:

$$ \begin{aligned} &y_i(w*x_i+b) >= 1- \epsilon_i \qquad其中\epsilon_i>=0 \\ \end{aligned} $$

因此线性不可分的线性支持向量机的学习问题为：

$$ \begin{aligned} &\min_{w,b,\epsilon}\frac{1}{2}||w||^2 + C*\sum_i^m\epsilon_i\\ &s.t.\quad y_i*(w*x) >= 1-\epsilon_i \\ &\qquad\epsilon_i>=0 \end{aligned} $$

同样对软间隔通过对偶问题求解可得，原始问题的对偶问题为:

选择惩罚系数C>0 : $$ \begin{aligned} &\min_\alpha \frac{1}{2}\sum_i^m\sum_j^m\alpha_i\alpha_jx_ix_jy_iy_j - \sum_i^m\alpha_i \ &s.t.\quad\sum_i^m \alpha_iy_i = 0 \ &\qquad0<=\alpha_i<=C\quad i=1,..m \end{aligned} $$ 可以看到，通过对偶问题，软间隔和硬间隔的对偶问题基本是相似的，这点非常重要。

1.3 软间隔支持向量问题

对于线性可分问题，其支持向量是$\alpha_i>=0$的点，因为其没有做松弛，但是对于软间隔的支持向量则比较复杂，实例$x_i$到间隔边界的距离为： $$ \frac{\epsilon_i}{||w||} $$

• $\alpha_i&lt;C$,则$\epsilon_i=0$,支持向量$x_i$在间隔边界上
• $\alpha_i=C, 0&lt;\epsilon_i&lt;1$,分类正确，$x_i$落在间隔边界和分类超平面之间
• $\alpha_i=C,\epsilon_i=1$,则落在分类超平面上
• $\alpha_i=C,\epsilon_i&gt;1$ 则落在分离超平面误分一侧