支持向量机（support vector machine，SVM）是一种二类分类模型。它的基本模型定义是定义在特征空间上的间隔最大的线性分类器；支持向量机还包括核技巧，这使得它成为实质上的非线性分类器。支持向量机的学习策略就是间隔最大化，可形式化为一个解凸二次规划的问题。
线性可分支持向量机和硬间隔最大化
线性可分支持向量机
给定线性可分的训练数据集，通过间隔最大化或等价地求解相应地凸二次规划问题学习得到的分离超平面为：
$$w^*\cdot x+b^* = 0$$
以及相应地分类决策函数为：
$$f(x)=sign(w^*\cdot x+b^*)$$
称为线性可分支持向量机。例如下图：
函数间隔和几何间隔
对于给定的训练集$ T $和超平面$(w,b)$，定义超平面和样本的函数间隔为：
$$\hat{\gamma}_i=y_i(w\cdot x_i + b)$$
定义超平面$(w,b)$关于训练数据集$ T $的函数间隔为超平面$(w,b)$关于$ T $中所有样本点$(x_i,y_i)$的函数间隔的最小值，即：
$$\hat{\gamma}=\min_{i=1,\cdots,N}\hat{\gamma}_i$$
由于函数间隔会随$ w $和$ b $成比例的改变，因此可以对分离超平面的法向量$ w $进行规范化，$||w||=1$，使得函数间隔是确定的，这时函数间隔就变成了几何间隔。
对于给定的训练集$ T $ 和超平面$(w,b)$，定义超平面$(w,b)$和样本的几何间隔为：
$$\gamma_i=y_i\Big(\frac{w}{||w||}\cdot x_i + \frac{d}{||w||}\Big)$$
定义超平面$(w,b)$关于训练数据集$ T $的几何间隔为超平面$(w,b)$关于$ T $中所有样本点$(x_i,y_i)$的几何间隔的最小值，即：
$$\gamma=\min_{i=1,\cdots,N}\gamma_i$$
因此函数间隔与几何间隔之间的关系为：
$$
\gamma_i=\frac{\hat{\gamma_i}}{||w||} \\\
\gamma=\frac{\hat{\gamma}}{||w||}
$$
间隔最大化
间隔最大化的直观解释就是：不仅将正负实例点分开，而且对最难分的实例点也有足够大的确信度将它们分开。这样的超平面应该对未知的新实例有很好地分类预测能力。
最大间隔分离超平面
最大化几何间隔的分类超平面问题可以表示为下面的约束最优化问题：
$$ \begin{align}
\max_{w,b} \quad & \gamma \\\
s.t. \quad & y_i\Big(\frac{w}{||w||}\cdot x_i + \frac{d}{||w||}\Big) \ge \gamma, \quad i=1,2,\cdots,N
\end{align} $$
考虑几何间隔与函数间隔的关系，上述问题可以改写为：
$$ \begin{align}
\max_{w,b} \quad & \frac{\hat{\gamma}}{||w||} \\\
s.t. \quad & y_i(w\cdot x_i + b) \ge \hat{\gamma}, \quad i=1,2,\cdots,N
\end{align} $$
不失一般性，我们令$ \hat{\gamma}=1$，并作一些转化，我们可以得到：
$$ \begin{align}
\min_{w,b} \quad & \frac{1}{2}{||w||}^2 \\\
s.t. \quad & y_i(w\cdot x_i + b) - 1 \ge 0, \quad i=1,2,\cdots,N
\end{align} $$
学习的对偶算法
显然上面是一个凸二次规划（convex quadratic programming）问题。通过拉格朗日对偶性这篇博客的启发，我们首先构造拉格朗日函数,引入拉格朗日乘子$\alpha_i \ge 0,\quad i=1,2,\cdots,N$，则有：
$$L(w,b,\alpha)=\frac{1}{2}||w||^2-\sum^{N}_{i=1}\alpha_iy_i(w\cdot x_i+b)+\sum^{N}_{i=1}\alpha_i
$$
根据拉格朗日对偶性，原始问题的对偶问题是极大极小问题：
$$\max_\alpha \min_{w,b} L(w,b,\alpha)$$
因此，为了得到对偶问题的解，需要先求$ L(w,b,\alpha) $对$ w,b $的极小，再求对$ \alpha $的极大。我们可以得到下面的对偶最优化问题：
$$ \begin{align}
\min_\alpha \quad & \frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)-\sum_{i=1}^{N}\alpha_i \\\
s.t. \quad & \sum_{i=1}^{N}\alpha_iy_i=0 \\\
& \alpha_i \ge 0, \quad i=1,2,\cdots,N
\end{align} $$
若对偶最优化的解为$ \alpha^*=(\alpha_1^*,\alpha_2^*,\cdots,\alpha_l^*)^T $，原始问题的最优解为$ (w^*,b^*) $，有KKT条件可知：
$$
w^* = \sum_{i=1}^{N}\alpha_i^*y_ix_i \\\
b^* =y_i-\sum_{i=1}^{N}\alpha_i^*y_i(x_i\cdot x_j)
$$
支持向量
将训练数据集中对应于$ \alpha_i^* > 0 $的样本点$ (x_i,y_i) $的实例$ x_i\in R^n $称为支持向量。有KKT互补条件可知：
$$\alpha_i^*(y_i(w^*\cdot x_i+b^*)-1) = 0, \quad i=1,2,\cdots,N$$
中对应于$ \alpha_i^* > 0 $的实例$ x_i $，有：
$$w^*\cdot x_i+b^* = \pm 1$$
即$ x_i $一定在间隔边界上。
综上所述，对于给定的线性可分的训练数据集，可以首先求对偶问题的解$ \alpha^* $；在求出原始问题的解$ (w^*,b^*) $；从而得到分离超平面及分类决策函数。这种算法称为线性可分的对偶学习算法。
线性支持向量机与软间隔最大化
线性支持向量机
在线性不可分训练数据集中，上述的线性可分支持向量机的学习算法是不适用的，下面就需要修改硬间隔最大化为软间隔最大，即引入松弛变量$ \xi \ge 0 $，使函数间隔加上松弛变量大于1，即可得到线性不可分的线性支持向量机的学习问题变成下面的凸二次规划问题（原始问题）：
$$ \begin{align}
\max_{w,b,\xi} \quad & \frac{1}{2}{||w||}^2 + C\sum_{i=1}^{N}\xi_i \\\
s.t. \quad & y_i(w\cdot x_i + b) \ge 1 - \xi_i, \quad i=1,2,\cdots,N \\\
& \xi_i \ge 0, \quad i=1,2,\cdots,N
\end{align} $$
由拉格朗日对偶性可得出原始问题的对偶问题是：
$$ \begin{align}
\min_\alpha \quad & \frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)-\sum_{i=1}^{N}\alpha_i \\\
s.t. \quad & \sum_{i=1}^{N}\alpha_iy_i=0 \\\
& 0 \le \alpha_i \le C, \quad i=1,2,\cdots,N
\end{align} $$
同样的，若对偶问题的解为$ \alpha^*=(\alpha_1^*,\alpha_2^*,\cdots,\alpha_N^*)^T $，原始问题的最优解为$ (w^*,b^*) $，必须满足KKT条件（这里特别的列出了线性支持向量机的KKT条件，这对后面的学习算法（SMO算法）十分重要）：
$$ \begin{align}
\nabla_wL(w^*,b^*,\xi^*,\alpha^*,\mu^*) & = w^*-\sum_{i=1}^{N}\alpha_i^*y_ix_i=0 \\\
\nabla_wL(w^*,b^*,\xi^*,\alpha^*,\mu^*) & = -\sum_{i=1}^{N}\alpha_i^*y_i=0 \\\
\nabla_wL(w^*,b^*,\xi^*,\alpha^*,\mu^*) & = C-\alpha^*-\mu^*=0 \\\
\alpha_i^*(y_i(w^*\cdot x_i+b^*)-1+\xi_i^*) & = 0\\\
\mu_i^*\xi_i^* & = 0 \\\
y_i(w^*\cdot x_i+b^*)-1+\xi_i^* & \ge 0 \\\
\xi_i^* & \ge 0 \\\
\alpha_i^* & \ge 0 \\\
\mu_i^* & \ge 0, \quad i=1,2,\cdots,N
\end{align} $$
并可推导出对于一个分量$ \alpha_j^* , 0 < \alpha_j^* < C$，则原始问题的解$ w^*,b^* $可按下式求得：
$$ \begin{align}
w^* & = \sum_{i=1}^{N}\alpha_i^*y_ix_i \\\
b^* & = y_j - \sum_{i=1}^{N}\alpha_i^*y_i(x_i\cdot x_j)
\end{align} $$
支持向量
在线性不可分的情况下，将对偶问题的解$ \alpha^*=(\alpha_1^*,\alpha_2^*,\cdots,\alpha_N^*)^T $中对应于$ \alpha_i^* > 0 $的样本点$ (x_i,y_i) $的实例$ x_i $称为支持向量（软间隔的支持向量）。这时的支持向量$ x_i $或者在间隔边界上，或者在间隔边界与分离超平面之间，或者在分离超平面误分类一侧。
- $ \alpha_i^* < C $，则$ \xi_i^* = 0 $，支持变量$ x_i^* $恰好落在间隔边界上；
- $ \alpha_i^* = C $，则$ 0 < \xi_i^* < 1 $，则分类正确，支持变量$ x_i^* $恰好落在间隔边界与分离超平面之间；
- $ \alpha_i^* = C $，则$ \xi_i^* = 1 $，支持变量$ x_i^* $在分离超平面上；
- $ \alpha_i^* = C $，则$ \xi_i^* > 1 $，支持变量$ x_i^* $位于分离超平面误分类一侧；
支持向量分类机(SVC)
前面介绍了两种处理线性不可分问题，即线性软间隔分类机（线性支持向量分类机）和非线性硬间隔分类机（可分支持向量分类机）。综合这两种方法，得到更常用的非线性软间隔分类机，主要有以下两种形式：
$C$-支持向量机($C$-SVC)
原始问题：
$$ \begin{align}
\min_{w,b,\xi} \quad & \frac{1}{2}{||w||}^2 + C\sum_{i=1}^{N}\xi_i \\\
s.t. \quad & y_i(w\cdot x_i + b) \ge 1 - \xi_i, \quad i=1,2,\cdots,N \\\
& \xi_i \ge 0, \quad i=1,2,\cdots,N
\end{align} $$
对偶问题：
$$ \begin{align}
\min_\alpha \quad & \frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_i\alpha_jy_iy_jK(x_i,x_j)-\sum_{i=1}^{N}\alpha_i \\\
s.t. \quad & \sum_{i=1}^{N}\alpha_iy_i=0 \\\
& 0 \le \alpha_i \le C, \quad i=1,2,\cdots,N
\end{align} $$
算法：
（1）已知训练数据集$ T=\\{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)\\}$，其中，$x_i\in\mathcal{X}= R^n,y\in\mathcal{Y}=\\{-1,1\\}, i=1,2,\cdots,N $
（2）选取适当地核函数$ K(x,x^{‘}) $和适当的参数$ C $，构造并求解优化问题：
$$\begin{align}
\min_\alpha \quad & \frac{1}{2}\sum^N_{i=1}\sum^N_{j=1}y_iy_j\alpha_i\alpha_jK(x_i,x_j)-\sum^N_{j=1}\alpha_j \\\
s.t. \quad & \sum^N_{i=1}y_i\alpha_i=0 \\\
& 0 \le \alpha_i \le C, \quad i=1,2,\cdots,N
\end{align}$$
的最优解$ \alpha^*=(\alpha_1^*,\cdots,\alpha_n^*)$；
（3）选取$ \alpha^* $的一个分量$ 0<\alpha_j^* < C$，并据此计算阀值$ b^*=y_j-\sum^N_{i=1}y_i\alpha_i^*K(x_i,x_j)$
（4）构造决策函数$\displaystyle f(x)=sgn\Big(\sum^N_{i=1}\alpha_i^*y_iK(x,x_i)+b^*\Big)。$
$v$-支持向量分类机($v$-SVC)
原始问题：
$$ \begin{align}
\min_{w,b,\xi,\rho} \quad & \frac{1}{2}{||w||}^2 - v\rho + \frac{1}{N}\sum_{i=1}^{N}\xi_i \\\
s.t. \quad & y_i(w\cdot x_i + b) \ge \rho - \xi_i, \quad i=1,2,\cdots,N \\\
& \xi_i \ge 0, \quad i=1,2,\cdots,N \\\
& \rho \ge 0
\end{align} $$
对偶问题：
$$ \begin{align}
\min_\alpha \quad & \frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_i\alpha_jy_iy_jK(x_i,x_j)-\sum_{i=1}^{N}\alpha_i \\\
s.t. \quad & \sum_{i=1}^{N}\alpha_iy_i=0 \\\
& 0 \le \alpha_i \le \frac{1}{N}, \quad i=1,2,\cdots,N \\\
& \sum^N_{i=1}\alpha_i \ge v
\end{align} $$
算法：
（1）已知训练数据集$ T=\\{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)\\}$，其中，$x_i\in\mathcal{X}= R^n,y\in\mathcal{Y}=\\{-1,1\\}, i=1,2,\cdots,N $
（2）选取适当地核函数$ K(x,x^{‘}) $和适当的参数$ v $，构造并求解优化问题：
$$ \begin{align}
\min_\alpha \quad & \frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_i\alpha_jy_iy_jK(x_i,x_j)-\sum_{i=1}^{N}\alpha_i \\\
s.t. \quad & \sum_{i=1}^{N}\alpha_iy_i=0 \\\
& 0 \le \alpha_i \le \frac{1}{N}, \quad i=1,2,\cdots,N \\\
& \sum^N_{i=1}\alpha_i \ge v
\end{align} $$
的最优解$ \alpha^*=(\alpha_1^*,\cdots,\alpha_n^*)$；
（3）选取$ j\in S_+=\\{i | \alpha_i^*\in(0,1/N),y_i=1\\},k\in S_-=\\{i | \alpha_i^*\in(0,1/N),y_i=1\\}, $的一个分量$ 0<\alpha_j^* < C$，并据此计算阀值:
$$ b^*=-\frac{1}{2}\sum^N_{i=1}y_i\alpha_i^*(K(x_i,x_j)+K(x_i,x_k))$$
（4）构造决策函数$\displaystyle f(x)=sgn\Big(\sum^N_{i=1}\alpha_i^*y_iK(x,x_i)+b^*\Big)。$
参数$ v $的意义：
间隔错误样本点的定义为：如果$ \xi_i^*>0$，则对应的样本点$ (x_i,y_i) $为间隔错误样本点。由KKT条件可知间隔错误样本点$ (x_i,y_i) $满足$ y_i(w^*\cdot x_i+b)=\rho^* - \xi_i^*$，也即$ y_i(w^*\cdot x_i+b)<\rho^* $，相应地两个间隔超平面为：
$$(w^*\cdot x)+b^*=\pm\rho^*$$
若记间隔错误样本点的个数为$ p$，支持向量的个数为$ q$，则有：$p/N \le v \le q/N$。
另外，在一定条件下，当样本点个数 $N\rightarrow\infty$ 时，$v$ 以1的概率渐近于支持向量个数和样本点个数之比。为 $v$ 值的选取提供了一个依据。