前言
SVM是一种二分类模型，是定义在特征空间上的间隔最大的线性分类器，间隔最大使它有别于感知机，SVM还包括核技巧，使它成为非线性分类器，而间隔最大的策略使得形式化为一个求解凸二次规划，等价于正则化的合页损失函数的最小化问题。
SVM学习方法包含构建由简到繁的模型：线性可分支持向量机【训练集线性可分，对应硬间隔最大化，又称硬间隔支持向量机】、线性支持向量机【训练集近似线性可分，对应软间隔支持向量机】、非线性支持向量机【当线性不可分，通过核技巧以及软间隔最大化学习】
核函数： 当输入空间为欧式空间或者离散集合、特征空间为希尔伯特空间(完备的内积空间)时，核函数表示将输入从输入空间映射到特征空间得到的特征向量之间的内积。通过使用核函数可以学习非线性支持向量机，等价于隐式地在高维的特征空间中学习线性支持向量机。
线性可分SVM与硬间隔最大化
线性可分支持向量机
概念：输入空间&特征空间
假设输入空间为欧式空间或者离散集合，特征空间为欧式空间或希尔伯特空间。线性/线性可分支持向量值假设这两个空间元素一一对应，而非线性支持向量机利用核函数将输入从输入空间映射到特征空间形成特征向量，因此svm的学习是在特征空间进行的。
假设特征空间上的训练集：
$$T=\lbrace(x_1,y_1),(x_2,y_2),…,(x_N,y_N)\rbrace$$
其中$y_i=\lbrace-1,+1\rbrace$
学习的目标是在特征空间找到一个分离超平面($w\cdot x+b$)能将实例分为不同的类别，一般地当数据集线性可分时，存在无数个分离超平面可以将这个两类数据正确分开，感知机利用误分类最小的策略，求得超平面，不过解有无穷多个，而线性可分支持向量机是利用间隔最大求最优的分离超平面，这个解释唯一。
假设学习到的分离超平面为$w^{\ast}\cdot x+b^{\ast}$
那么线性可分支持向量机的决策函数为$f(x)=sign(w^{\ast}\cdot x+b^{\ast})$
函数间隔&几何间隔
函数间隔
一般，一个点到分离超平面的远近可以表示为分类预测的确信程度，在超平面$w\cdot x+b$确定的情况下，$|w\cdot x+b|$表示点$x$到超平面的远近，而$w\cdot x+b$与类标记$y$是否一致表示分类是否正确，所以用$y(w\cdot x+b)$来表示分类的正确性以及确信度，这就是函数间隔。
定义：
超平面关于训练集$T$的函数间隔为超平面关于$T$中所有样本点的函数间隔之最小值，表示为：$$\hat{\gamma}=\min\limits_{i=1,2,…,N}\quad y_i\left(w\cdot x_i+b\right)$$几何间隔
但是选择超平面时，光有函数间隔是不够的，因为只要成比例的改变$w$和$b$，超平面没有变，但是函数间隔变成了原来的比例倍，因此需要对法向量$w$加约束，eg规范化$||w||$，使间隔确定，这时就是几何间隔。
定义：
超平面关于训练集$T$的几何间隔为超平面关于$T$中所有样本点的几何间隔之最小值，表示为
$$\gamma=\min\limits_{i=1,2,…,N}\quad y_i\left(\frac{w}{||w||}\cdot x_i+\frac{b}{||w||}\right)$$- 函数间隔与几何间隔关系
$$\gamma = \frac{\hat{\gamma}}{||w||}$$
如果$||w||=1$那么几何间隔=函数间隔，如果超平面参数$w,b$成比例的改变(超平面不变)，函数间隔按该比例改变，而几何间隔不变。
间隔最大化
支持向量机学习的基本思想求解能够正确划分训练数据集并且几何间隔最大的超平面，几何间隔最大的分离超平面是唯一的。
直观解释：对训练集找到几何间隔最大的超平面意味着以充分大的确信度对训练数据进行分类，这样的超平面对未知的新实例有很好的泛化能力。
最大化间隔分离超平面转化为如下约束最优化问题：
$$\begin{equation}
\mathop{\max}_{(w,b)} \quad\gamma \\
\begin{cases}
& s.t.\quad y_i\left(\frac{w}{||w||}\cdot x_i+\frac{b}{||w||}\right)\geq \gamma,i=1,2,…,N
\end{cases}
\end{equation}$$
即最大化超平面关于训练集的几何间隔$\gamma$，约束条件表示超平面关于每个训练样本的几何间隔至少为$\gamma$。
用函数间隔表示为：
$$\begin{equation}
\mathop{\max}_{(w,b)} \quad\frac{\hat{\gamma}}{||w||} \\
\begin{cases}
& s.t.\quad y_i\left(w\cdot x_i+b\right)\geq \hat{\gamma},i=1,2,…,N
\end{cases}
\end{equation}$$
函数间隔$\hat{\gamma}$的取值不影响最优化问题的解，这样就可以取$\hat{\gamma}=1$，代入上式，将$\frac{1}{||w||}$的最大化转化为$\frac{1}{2}||w||^2$最小化，它们是等价的，即线性可分支持向量机学习的最优化问题转化为：
$$\begin{equation}
\mathop{\min}_{(w,b)} \quad\frac{1}{2}||w||^2 \\
\begin{cases}
& s.t.\quad y_i(w\cdot x_i+b)-1\geq 0,i=1,2,…,N
\end{cases}
\end{equation}$$
此为一个凸二次规划问题求解最优值。
NOTE：
概念：支持向量&间隔边界
$H1:w\cdot x+b=1，H2:w\cdot x+b=-1$。在H1\H2上的点就是支持向量，H1\H2就是间隔边界，H1\H2之间的距离为$\frac{2}{||w||}$为间隔
学习对偶算法
原因：对偶问题比原始问题更好求解，方便引入核函数。
具体算法：
输入：线性数据集$T=\lbrace(x_1,y_1),(x_2,y_2),…,(x_N,y_N)\rbrace$,
输出：分离超平面和决策函数
- 构造并求解约束最优化问题
$$\begin{equation}
\mathop{\min}_{\alpha} \quad\frac{1}{2} \sum\limits_{i=1}^{N}\sum\limits_{j=1}^{N}\alpha_{i}\alpha_{j}y_iy_j(x_i \cdot x_j)-\sum\limits_{i=1}^{N}\alpha_{i} \\
\begin{cases}
& s.t.\quad \sum\limits_{i=1}^{N}\alpha_{i}y_i=0 \\
&\quad \alpha_i \geq 0,i=1,2,…,N
\end{cases}
\end{equation}$$
- 计算
$$w^{\ast} = \sum\limits_{i=1}^{N}\alpha_{i}^{\ast}y_ix_i$$
并选择$\alpha^{\ast}$的一个正分量$a_j^{\ast}>0$计算$b^{\ast}$
$$b^{\ast} = y_j -\sum\limits_{i=1}^{N}\alpha_{i}^{\ast}y_i(x_i\cdot x_j) $$ - 求得分离超平面和分类决策函数
$$w^{\ast}\cdot x+b^{\ast}=0,\quad f(x)=sign(w^{\ast}\cdot x+b^{\ast})$$
线性支持向量机与软间隔最大化
在现实中，训练集往往是不可分的，线性可分的支持向量机对线性不可分训练数据不适用，因为上述的不等式约束不能都成立，因此需要修改硬间隔最大化为软间隔最大化。
线性不可分意味着某些样本点不能满足函数间隔大于等于1的约束条件，为了解决这个问题，对每个样本引入了一个松弛变量$\xi_i \geq 0$，使得函数间隔加上松弛变量大于等于1，约束条件变为$y_i(w \cdot x_i+b)+\xi_i\geq 1$，同时对每个松弛变量$\xi_i$支付一个代价$\xi_i$，目标函数由原来的$\frac{1}{2}||w||^2$变成$$\frac{1}{2}||w||^2+C\sum\limits_{i=1}^N\xi_i$$
上述公式$C>0$为惩罚参数，越大时，对误分类的惩罚增大，最小化上述目标函数：一方面使$\frac{1}{2}||w||^2$尽量小即间隔尽量大，同时是误分类点的个数尽量少。
线性不可分的支持向量机转为学习如下的凸二次规划最优化问题：
$$\begin{equation}
\mathop{\min}_{(w,b)} \quad\frac{1}{2}||w||^2 +C\sum\limits_{i=1}^N\xi_i\\
\begin{cases}
s.t.\quad &y_i(w \cdot x_i+b)\geq 1-\xi_i,i=1,2,…,N \\
\quad &\xi_i \geq 0,i=1,2,…,N
\end{cases}
\end{equation}$$
转化为对偶算法(具体转化方法类似线性可分支持向量机)，即计算如下的凸二次规划：
$$\begin{equation}
\mathop{\min}_{\alpha} \quad\frac{1}{2} \sum\limits_{i=1}^{N}\sum\limits_{j=1}^{N}\alpha_{i}\alpha_{j}y_iy_j(x_i \cdot x_j)-\sum\limits_{i=1}^{N}\alpha_{i} \\
\begin{cases}
& s.t.\quad \sum\limits_{i=1}^{N}\alpha_{i}y_i=0 \\
&\quad 0 \leq \alpha_i \leq C,i=1,2,…,N
\end{cases}
\end{equation}$$
线性支持向量机的算法：
输入：训练数据集
输出：分离超平面和分类决策函数
- 选择惩罚参数$C$，构造并求解凸二次规划问题,求解最优$\alpha^{\ast}=(\alpha_1^{\ast},\alpha_2^{\ast},…,\alpha_N^{\ast})^T$
$$\begin{equation}
\mathop{\min}_{\alpha} \quad\frac{1}{2} \sum\limits_{i=1}^{N}\sum\limits_{j=1}^{N}\alpha_{i}\alpha_{j}y_iy_j(x_i \cdot x_j)-\sum\limits_{i=1}^{N}\alpha_{i} \\
\begin{cases}
& s.t.\quad \sum\limits_{i=1}^{N}\alpha_{i}y_i=0 \\
&\quad 0 \leq \alpha_i \leq C,i=1,2,…,N
\end{cases}
\end{equation}$$
- 计算$$w^{\ast} = \sum\limits_{i=1}^{N}\alpha_{i}^{\ast}y_ix_i$$
并选择$\alpha^{\ast}$的一个正分量$0\leq a_j^{\ast} \leq C$计算$b^{\ast}$
$$b^{\ast} = y_j -\sum\limits_{i=1}^{N}\alpha_{i}^{\ast}y_i(x_i\cdot x_j) $$ - 求得分离超平面和分类决策函数
$$w^{\ast}\cdot x+b^{\ast}=0,\quad f(x)=sign(w^{\ast}\cdot x+b^{\ast})$$
线性svm的支持向量
在线性不可分的情况下，通过对偶问题求解到$\alpha^{\ast}=(\alpha_1^{\ast},\alpha_2^{\ast},…,\alpha_N^{\ast})^T$中对应$\alpha_i^{\ast}>0$的样本点的实例$x_i$为支持向量，其中实例$x_i$到间隔编辑的距离为$\frac{\xi_i}{||w||}$
软间隔的支持向量：
- 在间隔边界上$(若\alpha_i^{\ast}<C，则\xi_i=0)$，
- 在间隔边界与分离超平面之间$(若\alpha_i^{\ast}=C，则0<\xi_i<1)$，
- 在分离超平面误分的一侧$(若\alpha_i^{\ast}=C，则\xi_i>1)$
- 在分离超平面上$(若\alpha_i^{\ast}=C，则\xi_i=1)$
合页损失函数(hinge loss)
损失函数表示为$$L(y，f(x))=max(0,1-yf(x))$$
而线性支持向量机的原始问题为：
$$\begin{equation}
\mathop{\min}_{(w,b)} \quad\frac{1}{2}||w||^2 +C\sum\limits_{i=1}^N\xi_i\\
\begin{cases}
s.t.\quad &y_i(w \cdot x_i+b)\geq 1-\xi_i,i=1,2,…,N \\
\quad &\xi_i \geq 0,i=1,2,…,N
\end{cases}
\end{equation}$$
应用合页损失函数，线性svm的原始问题等价于最优化问题：😇😇😇
$$\mathop{\min}_{(w,b)} \quad\sum\limits_{i=1}^{N} max(0,1-y_i(w\cdot x_i +b)) + \lambda ||w||^2$$
而$max(0,1-y_i(w\cdot x_i +b))=\xi_i, \lambda=\frac{1}{2C}$
总结
线性支持向量机很好理解跟解释，下一章节见非线性支持向量机的原理。
