支持向量机是一种分类模型，我们将由简至繁地引入线性可分支持向量机，线性支持向量机以及非线性支持向量机等。
线性可分支持向量机
考虑一个二分类问题，给定训练样本 $D = {(x_1,y_1), (x_2,y_2),\dots,(x_n,y_n)}$, 其中 $x_i \in R^p,y_i\in {-1,1}$。我们的想法是在 p 维空间中找到一个超平面，使得不同类别的样本分割开来。
超平面可由以下的方程刻画：
\[w^Tx +b = 0,\]其中 $w \in R^d$
假设这样的超平面存在，即这个数据集是线性可分的，我们往往能找到无数个这样的超平面分隔数据集，即存在无数个 $w$ 和 $b$ 。
为使分类结果是最鲁棒的，我们希望最大化所有样本点与该超平面几何距离中的最小值。
我们知道，样本点 $x_i$ 与超平面 $(w,b)$ 的几何距离 $r_i$ 的计算公式是：
\[r_i = \frac{|w^Tx_i +b|}{\|w\|}\]我们希望 $(w,b)$ 的取值满足：当 $y_i = 1$ 时，$w^Tx_i + b >0$，当 $y_i = -1$ 时，$w^T x_i+ b <0$。则距离 $r_i$ 的计算公式可简化为：
\[r_i = \frac{y_i(w^Tx_i +b)}{\|w\|}\]记最小几何距离为 $r$, 则
\[r = \min_{i = 1,\dots,n} r_i\]优化问题为：
\[\begin{array}{11} \max _{w,b} & r\\ s.t. & \frac{y_i(w^Tx_i +b)}{\|w\|} \ge r ,\ \ \ \ i = 1,\dots,n \end{array}\]解该优化问题，我们可以得到一个唯一的超平面使 $r$ 取到最大值。事实上，该超平面的 $(w,b)$ 的值也不唯一，因为当 $w$ 和 $b$ 同比例变化时，该超平面不变。一种自然的想法是可以固定 $|w|$ 的值，例如1，则 $w$ 是一个单位向量。可以这么做，但没必要，因为这样对解该优化化问题没有任何的帮助。为简化该问题，我们令 $|w| =1/r$ 。则原问题改写为：
\[\begin{array}{11} \max _{w,b} & \frac{1}{\|w\|} \\ s.t. & y_i(w^Tx_i +b) \ge 1 ,\ \ \ \ i = 1,\dots,n \end{array}\]注意到最大化 $\frac{1}{|w|}$ 与最小化 $\frac{1}{2}|w|^2$ 是等价的，于是就得到了线性可分支持向量机的最优化问题：
\[\begin{array}{11} \min _{w,b} & \frac{1}{2}\|w\|^2 \\ s.t. & y_i(w^Tx_i +b) \ge 1 ,\ \ \ \ i = 1,\dots,n \end{array}\]这是一个凸二次规划问题。
凸二次规划
凸优化问题，是指形如下列形式的优化问题：
\[\begin{array}{11} \min _w &f(w) \\ s.t. & g_i(w) \le 0 ,\ \ \ \ i = 1,\dots,k \\ & h_j(w) = 0,\ \ \ \ i = 1,\dots,l \end{array}\]其中，目标函数 $f(w)$ 和约束函数 $g_i(w)$ 都是 $R^d$上的连续可微的凸函数，等式约束函数 $h_j(w)$ 是 $R^d$ 上的仿射函数。
当目标函数 $f(w)$ 是二次函数且约束函数 $g_i(w)$ 是仿射函数时，上述凸优化问题即为凸二次规划问题。
对偶问题
引入拉格朗日乘子 $\alpha_i \ge0,i = 1,\dots,n$ ，定义拉格朗日函数：
\[L(w,b,\alpha) = \frac{1}{2}\|w\|^2 - \sum_{i=1}^n \alpha_i y_i (w^T x + b) + \sum_{i=1}^{n} \alpha_i\]其中, $\alpha = (\alpha_1, \alpha_2, \dots,\alpha_n)^T$ 为拉格朗日乘子向量。
则该问题的对偶问题为：
\[\max_{\alpha} \min_{w,b} L(w,b,\alpha)\](1) 求 $\min_{w,b} L(w,b,\alpha)$
将 $L(w,b,\alpha) $ 分别对 $w$ 和 $b$ 求偏导
\[\begin{array}{l}{\nabla_{w} L(w, b, \alpha)=w-\sum_{i=1}^{n} \alpha_{i} y_{i} x_{i}=0} \\ {\nabla_{b} L(w, b, \alpha)=-\sum_{i=1}^{n} \alpha_{i} y_{i}=0}\end{array}\]得
\[\begin{array}{c}{w=\sum_{i=1}^{n} \alpha_{i} y_{i} x_{i}} \\ {\sum_{i=1}^{n} \alpha_{i} y_{i}=0}\end{array}\]将其代入 $L(w,b,\alpha)$，即得
\[\begin{aligned} L(w, b, \alpha) &=\frac{1}{2} \sum_{i=1}^{n} \sum_{j=1}^{n} \alpha_{i} \alpha_{j} y_{i} y_{j}x_{i} ^T x_{j}-\sum_{i=1}^{n} \alpha_{i} y_{i}\left(\left(\sum_{j=1}^{n} \alpha_{j} y_{j} x_{j}\right) ^Tx_{i}+b\right)+\sum_{i=1}^{n} \alpha_{i} \\ &=-\frac{1}{2} \sum_{i=1}^{n} \sum_{j=1}^{n} \alpha_{i} \alpha_{j} y_{i} y_{j}x_{i} ^T x_{j}+\sum_{i=1}^{n} \alpha_{i} \end{aligned}\](2) 对 $\min_{w,b} L(w,b,\alpha)$ 对 $\alpha $ 求极大，即是对偶问题：
\[\begin{array}{11} \max _{\alpha} & -\frac{1}{2} \sum_{i=1}^{n} \sum_{j=1}^{n} \alpha_{i} \alpha_{j} y_{i} y_{j}x_{i} ^T x_{j}+\sum_{i=1}^{n} \alpha_{i} \\ \text { s.t. } & \sum_{i=1}^{n} \alpha_{i} y_{i}=0 \\ &\alpha_{i} \geqslant 0, \quad i=1,2, \cdots, n \end{array}\]等价于最小化：
\[\begin{array}{11} \min _{\alpha} & \frac{1}{2} \sum_{i=1}^{n} \sum_{j=1}^{n} \alpha_{i} \alpha_{j} y_{i} y_{j}x_{i} ^T x_{j}-\sum_{i=1}^{n} \alpha_{i} \\ \text { s.t. } & \sum_{i=1}^{n} \alpha_{i} y_{i}=0 \\ &\alpha_{i} \geqslant 0, \quad i=1,2, \cdots, n \end{array}\]其中 KKT 条件为：
\[\begin{array}{l}{\alpha_{i}^{*}\left(y_{i}\left(w^{*T} x_{i}+b^{*}\right)-1\right)=0, \quad i=1,2, \cdots, n} \\ {y_{i}\left(w^{*} \cdot x_{i}+b^{*}\right)-1 \geqslant 0, \quad i=1,2, \cdots, n} \\ {\alpha_{i}^{*} \geqslant 0, \quad i=1,2, \cdots, n}\end{array}\]由于
\[w^*=\sum_{i=1}^{n} \alpha_{i}^* y_{i} x_{i}\]即只有 $\alpha_i >0$ 对应的样本点才会影响 $w^$ 的取值。而由 KKT 条件得，该样本点必须满足 $y_{i}\left(w^{} \cdot x_{i}+b^{*}\right)-1 = 0$ ，我们称这些点为支持向量。
