Support Vector Machine

考虑输入空间为 \(\mathbb{R}^2\) 时的情况。在图 2 中，正实例点 \((2,2)\) 到分离超平面的函数间隔为多少呢？

显然，函数间隔没有唯一值。如果分离超平面表示为 \(x^{(1)} + x^{(2)} - 1 = 0\) ，则函数间隔为 \((+1)(2 + 2 - 1) = 3\) ；如果分离超平面表示为 \(\frac{1}{3} x^{(1)} + \frac{1}{3} x^{(2)} - \frac{1}{3} = 0\) ，则函数间隔为 \((+1)(\frac{2}{3} + \frac{2}{3} - \frac{1}{3}) = 1\) 。

所以，在同一模型中，函数间隔可取“任何正数”，我们总可以找到对应的分离超平面的参数。

如果约定正（或负）训练数据集到分离超平面的函数间隔为 1，则几何间隔可表示为：
\[\gamma = \frac{1}{\Vert \boldsymbol{w} \Vert}\]

下文将利用这个约定来简化优化问题。

广义拉格朗日函数为：
\[\mathcal{L}(\boldsymbol{w},b, \boldsymbol{\alpha}) = \frac{1}{2} \Vert \boldsymbol{w} \Vert^2 - \sum_{i=1}^{N} \alpha_i \big ( y_i (\langle \boldsymbol{w}, \boldsymbol{x_i} \rangle + b) - 1 \big)\]

原问题的对偶问题为：
\[\begin{aligned} & \underset{\boldsymbol{\alpha}}{\text{maximize}} & & \min\limits_{\boldsymbol{w},b} \mathcal{L}(\boldsymbol{w},b, \boldsymbol{\alpha})\\ & \text{subject to} & & \alpha_i \ge 0, \; i = 1,2,\cdots,N \end{aligned}\]

下面化简 \(\min\limits_{\boldsymbol{w},b} \mathcal{L}(\boldsymbol{w},b, \boldsymbol{\alpha})\) ，分别对 \(\boldsymbol{w},b\) 求偏导数并令其为 0，有：
\[\begin{cases} \dfrac{\partial \mathcal{L}}{\partial w^{(1)}} = w^{(1)} - \sum\limits_{i=1}^{N} \alpha_i y_i {x_i}^{(1)} = 0 \\ \dfrac{\partial \mathcal{L}}{\partial w^{(2)}} = w^{(2)} - \sum\limits_{i=1}^{N} \alpha_i y_i {x_i}^{(2)} = 0 \\ \quad \vdots \\ \dfrac{\partial \mathcal{L}}{\partial w^{(m)}} = w^{(m)} - \sum\limits_{i=1}^{N} \alpha_i y_i {x_i}^{(m)} = 0 \\ \dfrac{\partial \mathcal{L}}{\partial b} = - \sum\limits_{i=1}^{N} \alpha_i y_i = 0 \\ \end{cases}\]
由上式，有：
\[\begin{cases} \boldsymbol{w} = \sum\limits_{i=1}^{N} \alpha_i y_i \boldsymbol{x_i} \\ \sum\limits_{i=1}^{N} \alpha_i y_i = 0 \\ \end{cases}\]
利用上面两式，化简广义拉格朗日函数，有：
\[\begin{aligned} \mathcal{L}(\boldsymbol{w},b, \boldsymbol{\alpha}) & = \frac{1}{2} \Vert \boldsymbol{w} \Vert^2 - \sum_{i=1}^{N} \alpha_i \big ( y_i (\langle \boldsymbol{w}, \boldsymbol{x_i} \rangle + b) - 1 \big) \\ & = \frac{1}{2} \left \Vert \sum\limits_{i=1}^{N} \alpha_i y_i \boldsymbol{x_i} \right \Vert^2 - \sum_{i=1}^{N} \alpha_i y_i \left \langle \sum\limits_{j=1}^{N} \alpha_j y_j \boldsymbol{x_j} , \boldsymbol{x_i} \right \rangle - \sum_{i=1}^{N} \alpha_i y_i b + \sum_{i=1}^{N} \alpha_i \\ & = \frac{1}{2} \left \Vert \sum\limits_{i=1}^{N} \alpha_i y_i \boldsymbol{x_i} \right \Vert^2 - \sum_{i=1}^{N} \alpha_i y_i \left \langle \sum\limits_{j=1}^{N} \alpha_j y_j \boldsymbol{x_j} , \boldsymbol{x_i} \right \rangle + \sum_{i=1}^{N} \alpha_i \\ & = \frac{1}{2} \left \Vert \sum\limits_{i=1}^{N} \alpha_i y_i \boldsymbol{x_i} \right \Vert^2 - \left \langle \sum\limits_{j=1}^{N} \alpha_j y_j \boldsymbol{x_j} , \sum\limits_{i=1}^{N} \alpha_i y_i \boldsymbol{x_i} \right \rangle + \sum_{i=1}^{N} \alpha_i \\ \end{aligned}\]
由于 \(\left \langle \sum\limits_{j=1}^{N} \alpha_j y_j \boldsymbol{x_j} , \sum\limits_{i=1}^{N} \alpha_i y_i \boldsymbol{x_i} \right \rangle = \left \Vert \sum\limits_{i=1}^{N} \alpha_i y_i \boldsymbol{x_i} \right \Vert^2\) ，所以上式可写为：
\[\begin{aligned} \mathcal{L}(\boldsymbol{w},b, \boldsymbol{\alpha}) & = - \frac{1}{2} \left \Vert \sum\limits_{i=1}^{N} \alpha_i y_i \boldsymbol{x_i} \right \Vert^2 + \sum_{i=1}^{N} \alpha_i \\ & = - \frac{1}{2} \sum\limits_{i=1}^{N} \sum\limits_{j=1}^{N} \alpha_i \alpha_j y_i y_i \langle \boldsymbol{x_i}, \boldsymbol{x_j} \rangle + \sum\limits_{i=1}^{N} \alpha_i \end{aligned}\]

化简广义拉格朗日函数时利用了 \(\mathcal{L}(\boldsymbol{w},b, \boldsymbol{\alpha})\) 取极值时的结论，从而有 \(\min\limits_{\boldsymbol{w},b} \mathcal{L}(\boldsymbol{w},b, \boldsymbol{\alpha}) = \mathcal{L}(\boldsymbol{w},b, \boldsymbol{\alpha}) = - \dfrac{1}{2} \sum\limits_{i=1}^{N} \sum\limits_{j=1}^{N} \alpha_i \alpha_j y_i y_i \langle \boldsymbol{x_i}, \boldsymbol{x_j} \rangle + \sum\limits_{i=1}^{N} \alpha_i\)

所以，对偶问题等价于：
\[\begin{aligned} & \underset{\boldsymbol{\alpha}}{\text{maximize}} & & - \frac{1}{2} \sum\limits_{i=1}^{N} \sum\limits_{j=1}^{N} \alpha_i \alpha_j y_i y_i \langle \boldsymbol{x_i}, \boldsymbol{x_j} \rangle + \sum_{i=1}^{N} \alpha_i \\ & \text{subject to} & & \sum\limits_{i=1}^{N} \alpha_i y_i = 0 \\ & & & \alpha_i \ge 0, \; i = 1,2,\cdots,N \end{aligned}\]

又可以写为：
\[\begin{aligned} & \underset{\boldsymbol{\alpha}}{\text{minimize}} & & \frac{1}{2} \sum\limits_{i=1}^{N} \sum\limits_{j=1}^{N} \alpha_i \alpha_j y_i y_i \langle \boldsymbol{x_i}, \boldsymbol{x_j} \rangle - \sum_{i=1}^{N} \alpha_i \\ & \text{subject to} & & \sum\limits_{i=1}^{N} \alpha_i y_i = 0 \\ & & & \alpha_i \ge 0, \; i = 1,2,\cdots,N \end{aligned}\]

利用 KKT 最优化条件容易求解上面的对偶问题（求解它比直接求解原始优化问题容易得多，可以用 Sequential minimal optimization, SMO 算法快速地求解它）。
假设求得的对偶问题解为 \(\boldsymbol{\alpha}^{*} = (\alpha_1^* , \alpha_2^*, \cdots, \alpha_N^*)^{\mathsf{T}}\) （注：在这里我们把向量的分量记为下标形式，这和 \(\boldsymbol{w},\boldsymbol{x}\) 把向量分量记为上标形式不同），如何利用对偶问题的解（即 \(\boldsymbol{\alpha}^{*}\) ）得到原始优化问题的解呢？请看下文分解。

原问题满足“强对偶定理”的条件，由“强对偶定理”知，对偶问题的解 \(\boldsymbol{\alpha}^{*}\) 就是原问题取得最小值时广义拉格朗日函数 \(\mathcal{L}(\boldsymbol{w}, b, \boldsymbol{\alpha})\) 中 \(\boldsymbol{\alpha}\) 的值。有了这个信息，原问题的 KKT 最优化条件迎刃而解，原始问题也迎刃而解。

原问题的 KKT 条件：
\[\begin{cases} \dfrac{\partial \mathcal{L}}{\partial w^{(1)}} = w^{(1)} - \sum\limits_{i=1}^{N} \alpha_i^* y_i {x_i}^{(1)} = 0 \\ \dfrac{\partial \mathcal{L}}{\partial w^{(2)}} = w^{(2)} - \sum\limits_{i=1}^{N} \alpha_i^* y_i {x_i}^{(2)} = 0 \\ \quad \vdots \\ \dfrac{\partial \mathcal{L}}{\partial w^{(m)}} = w^{(m)} - \sum\limits_{i=1}^{N} \alpha_i^* y_i {x_i}^{(m)} = 0 \\ \dfrac{\partial \mathcal{L}}{\partial b} = - \sum\limits_{i=1}^{N} \alpha_i^* y_i = 0 \\ \alpha_i^* \big (y_i (\langle \boldsymbol{w}, \boldsymbol{x_i} \rangle + b) - 1 \big) = 0, \; i = 1,2,\cdots,N \\ y_i (\langle \boldsymbol{w}, \boldsymbol{x_i} \rangle + b) - 1 \ge 0, \; i = 1,2,\cdots,N \\ \alpha_i^* \ge 0, \; i = 1,2,\cdots,N \\ \end{cases}\]
上式中，只有 \(\boldsymbol{w},b\) 是待求的参数， \(\boldsymbol{\alpha}^{*}\) 是求解对偶问题时得到的解， \(\boldsymbol{x_i}, y_i\) 分别是训练数据及其分类标记。
由上面方程组可知：
\[\boldsymbol{w} = \sum\limits_{i=1}^{N} \alpha_i^* y_i \boldsymbol{x_i}\]
现在我们来求解 \(b\) 。至少可以找到一个 \(\alpha_j^* > 0\) （用反证法，如果 \(\forall i, \alpha_i = 0\) ，那么 \(\boldsymbol{w} = \boldsymbol{0}\) ，这不是原始问题的解）。所以，对满足 \(\alpha_j^* > 0\) 的 \(j\) 有：\(\alpha_j^* \big ( y_j (\langle \boldsymbol{w}, \boldsymbol{x_j} \rangle + b) - 1 \big) = 0\) ，即有：
\[y_j (\langle \boldsymbol{w}, \boldsymbol{x_j} \rangle + b) - 1 = 0\]
注意到 \(y_j^2 = 1\) ，所以有：
\[\begin{aligned} b & = y_j - \langle \boldsymbol{w}, \boldsymbol{x_j} \rangle \\ & = y_j - \left \langle \sum\limits_{i=1}^{N} \alpha_i^* y_i \boldsymbol{x_i} , \boldsymbol{x_j} \right \rangle \\ & = y_j - \sum\limits_{i=1}^{N} \alpha_i^* y_i \langle \boldsymbol{x_i} , \boldsymbol{x_j} \rangle \end{aligned}\]

至此，原优化问题中的 \(\boldsymbol{w}, b\) 都已经得到。

前面已经完整介绍了线性可分支持向量机（硬间隔支持向量机）的求解过程，现在总结如下。

设有线性可分的训练数据集 \(T = \{ (\boldsymbol{x_1},y_1), (\boldsymbol{x_2},y_2), \cdots, (\boldsymbol{x_N},y_N) \}\) ，其中 \(\boldsymbol{x_i} \in \mathbb{R}^n, y_i \in \{ -1 , +1 \}, i=1,2,\cdots, N\) ，求最大间隔分类器。

求解过程如下：
第一步，构造并求解下面约束优化问题：
\[\begin{aligned} & \underset{\boldsymbol{\alpha}}{\text{minimize}} & & \frac{1}{2} \sum\limits_{i=1}^{N} \sum\limits_{j=1}^{N} \alpha_i \alpha_j y_i y_i \langle \boldsymbol{x_i}, \boldsymbol{x_j} \rangle - \sum_{i=1}^{N} \alpha_i \\ & \text{subject to} & & \sum\limits_{i=1}^{N} \alpha_i y_i = 0 \\ & & & \alpha_i \ge 0, \; i = 1,2,\cdots,N \end{aligned}\]
求解它（如用 SMO 算法），假设得到的解为 \(\boldsymbol{\alpha}^{*} = (\alpha_1^* , \alpha_2^*, \cdots, \alpha_N^*)^{\mathsf{T}}\)

第二步，计算 \(\boldsymbol{w},b\) ：
\[\boldsymbol{w} = \sum\limits_{i=1}^{N} \alpha_i^* y_i \boldsymbol{x_i}\]
任意选择 \(\boldsymbol{\alpha}^{*}\) 的一个正分量 \(\alpha_j^* >0\) ，找到对应的训练数据 \((\boldsymbol{x_j}, y_j)\) ，计算：
\[b = y_j - \sum\limits_{i=1}^{N} \alpha_i^* y_i \langle \boldsymbol{x_i} , \boldsymbol{x_j} \rangle\]

特别说明 ：由 \(\boldsymbol{w},b\) 的计算公式可知， \(\boldsymbol{w},b\) 只依赖于训练数据集中对应于 \(\alpha_i^{*} >0\) 的训练数据 \((\boldsymbol{x_i}, y_i)\) ，而其他训练数据对 \(\boldsymbol{w},b\) 没有影响。 这些对应于 \(\alpha_i^* >0\) 的训练数据 \((\boldsymbol{x_i}, y_i)\) 就是 支持向量(Support Vector) 。

第三步，分类决策函数为：
\[\begin{aligned} f(\boldsymbol{x}) & = sign(\langle \boldsymbol{w}, \boldsymbol{x} \rangle + b) \\ & = sign \left( \left \langle \sum\limits_{i=1}^{N} \alpha_i^* y_i \boldsymbol{x_i}, \boldsymbol{x} \right \rangle + b \right) \\ & = sign \left( \sum\limits_{i=1}^{N} \alpha_i^* y_i \left \langle \boldsymbol{x_i}, \boldsymbol{x} \right \rangle + b \right) \end{aligned}\]

广义拉格朗日函数为：
\[\begin{aligned} \mathcal{L}(\boldsymbol{w},b, \boldsymbol{\zeta}, \boldsymbol{\alpha}, \boldsymbol{r} ) & = \frac{1}{2} \Vert \boldsymbol{w} \Vert^2 + C \sum_{i=1}^{N} \zeta_i - \sum_{i=1}^{N} \alpha_i \big ( y_i (\langle \boldsymbol{w}, \boldsymbol{x_i} \rangle + b) - 1 + \zeta_i \big) - \sum_{i=1}^{N} r_i \zeta_i \\ & = \frac{1}{2} \Vert \boldsymbol{w} \Vert^2 - \sum_{i=1}^{N} \alpha_i \big ( y_i (\langle \boldsymbol{w}, \boldsymbol{x_i} \rangle + b) - 1 \big) + \sum_{i=1}^N (C - \alpha_i - r_i) \zeta_i \\ \end{aligned}\]

原问题的对偶问题为：
\[\begin{aligned} & \underset{\boldsymbol{\alpha}, \boldsymbol{r}}{\text{maximize}} & & \min\limits_{\boldsymbol{w},b,\boldsymbol{\zeta}} \mathcal{L}(\boldsymbol{w},b, \boldsymbol{\zeta}, \boldsymbol{\alpha}, \boldsymbol{r} ) \\ & \text{subject to} & & \alpha_i \ge 0, \; i = 1,2,\cdots,N \\ & & & r_i \ge 0, \; i = 1,2,\cdots,N \end{aligned}\]

下面化简 \(\min\limits_{\boldsymbol{w},b,\boldsymbol{\zeta}} \mathcal{L}(\boldsymbol{w},b, \boldsymbol{\zeta}, \boldsymbol{\alpha}, \boldsymbol{r})\) ，分别对 \(\boldsymbol{w},b,\boldsymbol{\zeta}\) 求偏导数并令其为 0，有：
\[\begin{cases} \dfrac{\partial \mathcal{L}}{\partial w^{(1)}} = w^{(1)} - \sum\limits_{i=1}^{N} \alpha_i y_i {x_i}^{(1)} = 0 \\ \dfrac{\partial \mathcal{L}}{\partial w^{(2)}} = w^{(2)} - \sum\limits_{i=1}^{N} \alpha_i y_i {x_i}^{(2)} = 0 \\ \quad \vdots \\ \dfrac{\partial \mathcal{L}}{\partial w^{(m)}} = w^{(m)} - \sum\limits_{i=1}^{N} \alpha_i y_i {x_i}^{(m)} = 0 \\ \dfrac{\partial \mathcal{L}}{\partial b} = - \sum\limits_{i=1}^{N} \alpha_i y_i = 0 \\ \dfrac{\partial \mathcal{L}}{\partial \zeta_1} = C - \alpha_i - r_i = 0 \\ \dfrac{\partial \mathcal{L}}{\partial \zeta_2} = C - \alpha_i - r_i = 0 \\ \quad \vdots \\ \dfrac{\partial \mathcal{L}}{\partial \zeta_N} = C - \alpha_i - r_i = 0 \\ \end{cases}\]
由上式，有：
\[\begin{cases} \boldsymbol{w} = \sum\limits_{i=1}^{N} \alpha_i y_i \boldsymbol{x_i} \\ \sum\limits_{i=1}^{N} \alpha_i y_i = 0 \\ C - \alpha_i - r_i = 0 \\ \end{cases}\]

利用上面三式，化简广义拉格朗日函数，可得（具体过程和“硬间隔支持向量机”中化简对偶问题时非常类似）：
\[\min\limits_{\boldsymbol{w},b,\boldsymbol{\zeta}} \mathcal{L}(\boldsymbol{w},b, \boldsymbol{\zeta}, \boldsymbol{\alpha}, \boldsymbol{r}) = - \dfrac{1}{2} \sum\limits_{i=1}^{N} \sum\limits_{j=1}^{N} \alpha_i \alpha_j y_i y_i \langle \boldsymbol{x_i}, \boldsymbol{x_j} \rangle + \sum\limits_{i=1}^{N} \alpha_i\]

所以，对偶问题等价于：
\[\begin{aligned} & \underset{\boldsymbol{\alpha}, \boldsymbol{r}}{\text{maximize}} & & - \frac{1}{2} \sum\limits_{i=1}^{N} \sum\limits_{j=1}^{N} \alpha_i \alpha_j y_i y_i \langle \boldsymbol{x_i}, \boldsymbol{x_j} \rangle + \sum_{i=1}^{N} \alpha_i \\ & \text{subject to} & & \sum\limits_{i=1}^{N} \alpha_i y_i = 0 \\ & & & C - \alpha_i - r_i = 0, \; i = 1,2,\cdots,N \\ & & & \alpha_i \ge 0, \; i = 1,2,\cdots,N \\ & & & r_i \ge 0, \; i = 1,2,\cdots,N \\ \end{aligned}\]

又可以写为：
\[\begin{aligned} & \underset{\boldsymbol{\alpha}}{\text{minimize}} & & \frac{1}{2} \sum\limits_{i=1}^{N} \sum\limits_{j=1}^{N} \alpha_i \alpha_j y_i y_i \langle \boldsymbol{x_i}, \boldsymbol{x_j} \rangle - \sum_{i=1}^{N} \alpha_i \\ & \text{subject to} & & \sum\limits_{i=1}^{N} \alpha_i y_i = 0 \\ & & & 0 \le \alpha_i \le C, \; i = 1,2,\cdots,N \end{aligned}\]

说明：这个对偶问题和“硬间隔支持向量机”的对偶问题非常相似，仅仅是多了一个约束条件 \(\alpha_i \le C\) 。

利用 KKT 最优化条件容易求解上面的对偶问题（求解它比直接求解原始优化问题容易得多，可以用 Sequential minimal optimization, SMO 算法快速地求解它）。
假设求得的对偶问题解为 \(\boldsymbol{\alpha}^{*} = (\alpha_1^* , \alpha_2^*, \cdots, \alpha_N^*)^{\mathsf{T}}\) ，下文将介绍如何利用对偶问题的解（即 \(\boldsymbol{\alpha}^{*}\) ）得到原始优化问题的解。

原问题满足“强对偶定理”的条件，由“强对偶定理”知，对偶问题的解 \(\boldsymbol{\alpha}^{*}\) 就是原问题取得最小值时广义拉格朗日函数 \(\mathcal{L}(\boldsymbol{w},b, \boldsymbol{\zeta}, \boldsymbol{\alpha}, \boldsymbol{r})\) 中 \(\boldsymbol{\alpha}\) 的值。有了这个信息，原问题的 KKT 最优化条件迎刃而解，原始问题也迎刃而解。

先直接给出结论：
设 \(\boldsymbol{\alpha}^{*} = (\alpha_1^* , \alpha_2^*, \cdots, \alpha_N^*)^{\mathsf{T}}\) 是对偶问题的解，如果存在 \(\boldsymbol{\alpha}^{*}\) 的一个分量 \(\alpha_j^*\) 满足条件 \(0 < \alpha_j^* < C\) ，我们找到对应的训练数据 \((\boldsymbol{x_j}, y_j)\) ，则原始问题的解可以按下式求得（ \(\boldsymbol{\zeta}\) 没有出现在“软间隔支持向量机”的决策函数中，所以不用求它）：
\[\begin{cases} \boldsymbol{w} = \sum\limits_{i=1}^{N} \alpha_i^* y_i \boldsymbol{x_i} \\ b = y_j - \sum\limits_{i=1}^{N} \alpha_i^* y_i \langle \boldsymbol{x_i} , \boldsymbol{x_j} \rangle \end{cases}\]

证明如下：
原问题的 KKT 条件：
\[\begin{cases} \dfrac{\partial \mathcal{L}}{\partial w^{(1)}} = w^{(1)} - \sum\limits_{i=1}^{N} \alpha_i^* y_i {x_i}^{(1)} = 0 \\ \dfrac{\partial \mathcal{L}}{\partial w^{(2)}} = w^{(2)} - \sum\limits_{i=1}^{N} \alpha_i^* y_i {x_i}^{(2)} = 0 \\ \quad \vdots \\ \dfrac{\partial \mathcal{L}}{\partial w^{(m)}} = w^{(m)} - \sum\limits_{i=1}^{N} \alpha_i^* y_i {x_i}^{(m)} = 0 \\ \dfrac{\partial \mathcal{L}}{\partial b} = - \sum\limits_{i=1}^{N} \alpha_i^* y_i = 0 \\ \dfrac{\partial \mathcal{L}}{\partial \zeta_1} = C - \alpha_i^* - r_i = 0 \\ \dfrac{\partial \mathcal{L}}{\partial \zeta_2} = C - \alpha_i^* - r_i = 0 \\ \quad \vdots \\ \dfrac{\partial \mathcal{L}}{\partial \zeta_N} = C - \alpha_i^* - r_i = 0 \\ y_i ( \boldsymbol{w} \cdot \boldsymbol{x_i} + b ) \ge 1 - \zeta_i, \quad i=1,2,\cdots,N \\ \zeta_i \ge 0, \quad i=1,2,\cdots,N \\ \alpha_i^* \ge 0, \; i = 1,2,\cdots,N \\ r_i \ge 0, \; i = 1,2,\cdots,N \\ \alpha_i^* \big (y_i (\langle \boldsymbol{w}, \boldsymbol{x_i} \rangle + b) - 1 + \zeta_i \big) = 0, \; i = 1,2,\cdots,N \\ r_i \zeta_i = 0, \; i = 1,2,\cdots,N \\ \end{cases}\]

上式中， \(C\) 是用户设定的惩罚参数， \(\boldsymbol{\alpha}^{*}\) 是求解对偶问题时得到的解， \(\boldsymbol{x_i}, y_i\) 分别是训练数据及其分类标记，它们都是已知的。

由方程组中前几个式子有：
\[\boldsymbol{w} = \sum\limits_{i=1}^{N} \alpha_i^* y_i \boldsymbol{x_i}\]

方程组中最后两个式子可以写为：
\[\begin{cases} \alpha_i^* \big (y_i (\langle \boldsymbol{w}, \boldsymbol{x_i} \rangle + b) - 1 + \zeta_i \big) = 0, \; i = 1,2,\cdots,N \\ (C - \alpha_i^*) \zeta_i = 0, \; i = 1,2,\cdots,N \\ \end{cases}\]

由上面式子可知，如果存在 \(\boldsymbol{\alpha}^{*}\) 的一个分量 \(\alpha_j^*\) 满足条件 \(0 < \alpha_j^* < C\) ，我们找到对应的训练数据 \((\boldsymbol{x_j}, y_j)\) ，则 \(y_j (\langle \boldsymbol{w}, \boldsymbol{x_j} \rangle + b) - 1 = 0\) ，又由于 \(y_j^2 = 1\) ，所以有：
\[\begin{aligned} b & = y_j - \langle \boldsymbol{w}, \boldsymbol{x_j} \rangle \\ & = y_j - \left \langle \sum\limits_{i=1}^{N} \alpha_i^* y_i \boldsymbol{x_i} , \boldsymbol{x_j} \right \rangle \\ & = y_j - \sum\limits_{i=1}^{N} \alpha_i^* y_i \langle \boldsymbol{x_i} , \boldsymbol{x_j} \rangle \end{aligned}\]

至此，原优化问题中的 \(\boldsymbol{w}, b\) 都已经得到。

由 \(\boldsymbol{w},b\) 的计算公式可知， \(\boldsymbol{w},b\) 只依赖于训练数据集中对应于 \(\alpha_i^{*} >0\) 的训练数据 \((\boldsymbol{x_i}, y_i)\) ，而其他训练数据对 \(\boldsymbol{w},b\) 没有影响。 这些对应于 \(\alpha_i^* >0\) 的训练数据 \((\boldsymbol{x_i}, y_i)\) 就是 支持向量(Support Vector) ，如图 4 所示。

上一节分析的 KKT 条件中有：
\[\begin{cases} \alpha_i^* \big (y_i (\langle \boldsymbol{w}, \boldsymbol{x_i} \rangle + b) - 1 + \zeta_i \big) = 0, \; i = 1,2,\cdots,N \\ (C - \alpha_i^*) \zeta_i = 0, \; i = 1,2,\cdots,N \\ \end{cases}\]

从而可以得到下表：

Table 1: 软间隔支持向量机中的支持向量

分情况讨论	此时会满足	支持向量的位置描述
\(0 < \alpha_i < C\) （此时一定有 \(\zeta_i = 0\) ）	\(y_i (\langle \boldsymbol{w}, \boldsymbol{x_i} \rangle + b) = 1\)	对应的支持向量恰好在正确分类那一侧的“间隔边界”上
\(\alpha_i = C, 0 < \zeta_i <1\)	\(0 < y_i (\langle \boldsymbol{w}, \boldsymbol{x_i} \rangle + b) < 1\)	对应的支持向量在正确分类那一侧的“间隔边界”和“分离超平面”之间
\(\alpha_i = C, \zeta_i = 1\)	\(\langle \boldsymbol{w}, \boldsymbol{x_i} \rangle + b = 0\)	对应的支持向量在“分离超平面”上
\(\alpha_i = C, \zeta_i > 1\)	\(y_i (\langle \boldsymbol{w}, \boldsymbol{x_i} \rangle + b) < 0\)	对应的支持向量在“分离超平面”错误分类的那一侧
\(\alpha_i = 0\)	\(y_i (\langle \boldsymbol{w}, \boldsymbol{x_i} \rangle + b) > 1\)	不是支持向量
\(\alpha_i > C\)		不会出现，因为和对偶问题的约束条件矛盾

前面已经完整介绍了线性支持向量机（软间隔支持向量机）的求解过程，现在总结如下。

设有近似线性可分的训练数据集 \(T = \{ (\boldsymbol{x_1},y_1), (\boldsymbol{x_2},y_2), \cdots, (\boldsymbol{x_N},y_N) \}\) ，其中 \(\boldsymbol{x_i} \in \mathbb{R}^n, y_i \in \{ -1 , +1 \}, i=1,2,\cdots, N\) ，求软间隔支持向量机决策函数。

求解过程如下：
第一步，选择一个惩罚参数 \(C=0\) ，构造并求解下面约束优化问题：
\[\begin{aligned} & \underset{\boldsymbol{\alpha}}{\text{minimize}} & & \frac{1}{2} \sum\limits_{i=1}^{N} \sum\limits_{j=1}^{N} \alpha_i \alpha_j y_i y_i \langle \boldsymbol{x_i}, \boldsymbol{x_j} \rangle - \sum_{i=1}^{N} \alpha_i \\ & \text{subject to} & & \sum\limits_{i=1}^{N} \alpha_i y_i = 0 \\ & & & 0 \le \alpha_i \le C, \; i = 1,2,\cdots,N \end{aligned}\]

求解它（最常用的算法是 SMO 算法），假设得到的解为 \(\boldsymbol{\alpha}^{*} = (\alpha_1^* , \alpha_2^*, \cdots, \alpha_N^*)^{\mathsf{T}}\)

第二步，计算 \(\boldsymbol{w},b\) ：
\[\boldsymbol{w} = \sum\limits_{i=1}^{N} \alpha_i^* y_i \boldsymbol{x_i}\]

选择满足条件 \(0 < \alpha_j^* < C\) 的 \(\boldsymbol{\alpha}^{*}\) 的分量 \(\alpha_j^*\) ，找到对应的训练数据 \((\boldsymbol{x_j}, y_j)\) ，计算：
\[b = y_j - \sum\limits_{i=1}^{N} \alpha_i^* y_i \langle \boldsymbol{x_i} , \boldsymbol{x_j} \rangle\]

第三步，分类决策函数为：
\[\begin{aligned} f(\boldsymbol{x}) & = sign(\langle \boldsymbol{w}, \boldsymbol{x} \rangle + b) \\ & = sign \left( \left \langle \sum\limits_{i=1}^{N} \alpha_i^* y_i \boldsymbol{x_i}, \boldsymbol{x} \right \rangle + b \right) \\ & = sign \left( \sum\limits_{i=1}^{N} \alpha_i^* y_i \left \langle \boldsymbol{x_i}, \boldsymbol{x} \right \rangle + b \right) \end{aligned}\]