机器学习算法系列之三：SVM（4）
“你听过的最有哲理，也是你最喜欢的一句话是什么？”，他问。
“我也不知道…”，她淡淡的说道。
一、对偶算法
在本系列的第（3）篇中，我们证明了分割超平面的存在性和唯一性，这章我们来看看如何求解这个分割超平面。我们先来看看要求解的最优化问题，如下式：
$$
\begin{cases}
\min \limits_{w,b}{\frac{1}{2} {||w||}}^2\\\\
y_i \lgroup {\vec w} · \vec x_i + {b} \rgroup - 1 \geq 0, \ \ i = 1,2,···,N
\end{cases}
\tag{*2 - 14}
$$
为了求解该凸优化问题，先构造出其广义拉格朗日函数（见本博客“拉格朗日对偶问题”专栏），如下式1-1：
$$
L(\vec w, \vec \alpha, b) = {\frac{1}{2} {||w||}}^2 - { \sum_{i=1}^N \alpha_i y_i (\vec w · \vec x_i + b) } + { \sum_{i=1}^N \alpha_i }
\tag{1 - 1}
$$
这里有一点要特别说明：上式中的第二项表明，每一个输入样本都可以成为一个不等式（或等式）约束，每一个样本对应一个唯一的拉格朗日乘子$\alpha_i$，请务必牢记这一点，它将有助于你理解下文。
由拉格朗日对偶问题（见本博客“拉格朗日对偶问题”专栏）可知，原始问题的解转化为如下问题的解：
$$
\max \limits_{\vec \alpha} \min \limits_{w,b}{L(\vec w, \vec \alpha, b)}
\tag{1 - 2}
$$
欲求解该问题，要先求解$L(\vec w, \vec \alpha, b)$对$\vec w, b$的极小值，再求对$\vec \alpha$的极大值。
1.1 求极小值
要求$\min \limits_{w,b}{L(\vec w, \vec \alpha, b)}$，利用高数的知识，只需要分别对$\vec w, b$求偏导并另其等于零即可求出极小值情况下$\vec w, b, \vec \alpha$这些未知变量需要满足的约束条件，即要求解如下两个方程：
$$
\nabla _ \vec w L(\vec w, \vec \alpha, b) = 0
\tag{1 - 3}
$$
$$
\nabla _ b L(\vec w, \vec \alpha, b) = 0
\tag{1 - 4}
$$
网上几乎所有资料在讲解上式（1 - 3）、(1 - 4)的时候，都是直接给出一个结果，并没有给出详细的证明和求解过程，大多数人在看的时候也是一眼带过，似乎认为得出这种结果是理所当然的，然而数学中从来就没有理所当然。
我们来看看式（1 - 3），式中要求的偏导是对一个向量$\vec w$，注意，$\vec w$是一个向量，是我们的权重系数向量$\vec w = (w_1, \ w_2, \ \dots)$，不是一个标量（Scalar）！我们在高数里面学的函数的极值问题求解，是针对某个标量而言的，非数学专业的同学可以回想下，你们大学学过函数对向量的偏导吗，没有吧？所以我们不能简单的把$\frac{1}{2} ||\vec w||^2$对向量$\vec w$的偏导按照对标量$w$的偏导的求解方法来做。
设输入的维度为$M$，则我们有权重向量$\vec w = (w_1, \ w_2, \ \dots, \ w_M)$，则：
$$
\frac{1}{2} ||\vec w||^2 = \vec w · \vec w = w_1^2 + w_2^2 + \dots + w_M^2
$$
于是有广义拉格朗日函数（1 - 1）第一项$\frac{1}{2} ||\vec w||^2$对向量$\vec w$的偏导如下（标量对向量的偏导的求解参见本博客的“概念定义杂记”专栏）：
$$
\begin{split}
\frac {\partial(\frac{1}{2} ||\vec w||^2)} {\partial \vec w} &= (\frac {\partial(\frac{1}{2} ||\vec w||^2)} {\partial w_1}, \ \frac {\partial(\frac{1}{2} ||\vec w||^2)} {\partial w_2}, \ \dots, \ \frac {\partial(\frac{1}{2} ||\vec w||^2)} {\partial w_M}) \\\\
&= (\frac{1}{2} · 2w_1, \ \frac{1}{2} · 2w_2, \ \dots, \ \frac{1}{2} · 2w_M) \\\\
&= (w_1, \ w_2, \ \dots, \ w_M) \\\\
&= \vec w
\end{split}
\tag{1 - 5}
$$
我们再来看式（1 - 1）的第二项，${ \sum_{i=1}^N \alpha_i y_i (\vec w · \vec x_i + b) }$，该项又可以拆分成两项${ \sum_{i=1}^N \alpha_i · y_i · \vec w · \vec x_i}$及${ \sum_{i=1}^N \alpha_i · y_i · b}$，后一项因为不包含与$\vec w$相关的内容，因此根据标量对向量的求导法则，该项对向量$\vec w$的偏导恒为零向量，因此我们直接忽略这项，直接看第一项的结果。
$$
\begin{split}
{\sum_{i=1}^N \alpha_i · y_i · \vec w · \vec x_i} &= \alpha_1 · y_1 · \vec w · \vec x_1 + \alpha_2 · y_2 · \vec w · \vec x_2 + \dots + \alpha_N · y_N · \vec w · \vec x_N \\\\
\end{split}
\tag{1 - 6}
$$
为了方便书写，我们把上式记作$g(\vec w, \ \vec \alpha)$，于是根据标量对向量的偏导法则有：
$$
\begin{split}
\frac{\partial [g(\vec w, \ \vec \alpha)]}{\partial \vec w} &= \alpha_1 · y_1 \frac{\partial (\vec w · \vec x_1)}{\partial \vec w} + \alpha_2 · y_2 \frac{\partial (\vec w · \vec x_2)}{\partial \vec w} + \dots + \alpha_N · y_N \frac{\partial (\vec w · \vec x_N)}{\partial \vec w} \\\\
&= \sum_{i=1}^N \alpha_i · y_i \frac{\partial (\vec w · \vec x_i)}{\partial \vec w} \\\\
&= \sum_{i=1}^N \alpha_i · y_i \frac{\partial (w_1 · x_i^1 + w_2 · x_i^2 + \dots + w_M · x_i^M)}{\partial \vec w} \\\\
&= \sum_{i=1}^N \alpha_i · y_i (x_i^1 , \ x_i^2 , \ \dots , \ x_i^M) \\\\
&= \sum_{i=1}^N \alpha_i · y_i · \vec x_i
\end{split}
\tag{1 - 7}
$$
注意：上式中$x_i^k$表示的是第$i$个样本的第$k$个特征（或属性）的取值，而非$x_i$的$k$次方。
我们再来看式（1 - 1）第三项${\sum_{i=1}^N \alpha_i }$，该项是由拉格朗日乘子组成的，不含与向量$\vec w$相关的项，同样由标量对向量的偏导法则，该项对向量$\vec w$求偏导后恒为零向量，即有$\partial ({\sum_{i=1}^N \alpha_i }) / \partial \vec w \equiv 0$，我们同样忽略该项。
综上，我们有：
$$
\nabla _ \vec w L(\vec w, \vec \alpha, b) = \vec w - \sum_{i=1}^N \alpha_i · y_i · \vec x_i
\tag{1 - 8}
$$
对于式（1 - 4），因为求的是对标量b的偏导，与我们在大学时候学的内容契合，这里就不赘述，可得到：
$$
\nabla _ b L(\vec w, \vec \alpha, b) = \sum_{i=1}^N \alpha_i · y_i
\tag{1 - 9}
$$
分别另式（1 - 8）、（1 - 9）等于零，即可求解出极值情况未知变量需要满足的约束条件，可得：
$$
\begin{cases}
\vec w = \sum_{i=1}^N \alpha_i · y_i · \vec x_i \\\\
\sum_{i=1}^N \alpha_i · y_i = 0
\tag{1 - 10}
\end{cases}
$$
将上式回代入式（1 - 1），可以消掉未知变量$\vec w、b$。
1.2 回代化简
同样的，几乎所有对这部分的讲解都是一笔带过，让有些数学基础不怎么好的同学有点犯晕，不知道是怎么得出来的。这里我给出详细的回代化简过程，我们先来看$\frac{1}{2} ||\vec w||^2$这一项：
$$
\begin{split}
& \frac{1}{2} ||\vec w||^2 \\\\
&= \frac{1}{2} \vec w · \vec w \\\\
&= \frac{1}{2} (\sum_{i=1}^N \alpha_i · y_i · \vec x_i) · (\sum_{i=1}^N \alpha_i · y_i · \vec x_i) \\\\
&= \frac{1}{2} (\alpha_1 · y_1 · \vec x_1 + \dots + \alpha_N · y_N · \vec x_N) · (\alpha_1 · y_1 · \vec x_1 + \dots + \alpha_N · y_N · \vec x_N)
\end{split}
\tag{1 - 11}
$$
上式展开出来后不进行同类项合并的话，一共有$N·N = N^2$项，为了方便书写和分析，我们把这些展开项按顺序放在一个$N·N$的方阵$A$中，矩阵的元素$A_{ij}$表示上式中第一个括号中的第$i$项与后面括号的第$j$项相乘的结果，可得：
$$
\begin{split}
A &= \frac{1}{2}
\begin{bmatrix}
\alpha_1 y_1 \vec x_1 · \alpha_1 y_1 \vec x_1 & \alpha_1 y_1 \vec x_1 · \alpha_2 y_2 \vec x_2 & \dots & \alpha_1 y_1 \vec x_1 · \alpha_N y_N \vec x_N \\\\
\alpha_2 y_2 \vec x_2 · \alpha_1 y_1 \vec x_1 & \alpha_2 y_2 \vec x_2 · \alpha_2 y_2 \vec x_2 & \dots & \alpha_2 y_2 \vec x_2 · \alpha_N y_N \vec x_N \\\\
\vdots & \vdots & \vdots & \vdots \\\\
\alpha_N y_N \vec x_N · \alpha_1 y_1 \vec x_1 & \alpha_N y_N \vec x_N · \alpha_2 y_2 \vec x_2 & \dots & \alpha_N y_N \vec x_N · \alpha_N y_N \vec x_N \\\\
\end{bmatrix} \\\\
\\\\
&= \frac{1}{2}
\begin{bmatrix}
\alpha_1^2 y_1^2 \vec x_1 · \vec x_1 & \alpha_1 \alpha_2 y_1 y_2 \vec x_1 · \vec x_2 & \dots & \alpha_1 \alpha_N y_1 y_N \vec x_1 · \vec x_N \\\\
\alpha_1 \alpha_2 y_1 y_2 \vec x_1 · \vec x_2 & \alpha_2^2 y_2^2 \vec x_2 · \vec x_2 & \dots & \alpha_2 \alpha_N y_2 y_N \vec x_2 · \vec x_N \\\\
\vdots & \vdots & \vdots & \vdots \\\\
\alpha_1 \alpha_N y_1 y_N \vec x_1 · \vec x_2 & \alpha_2 \alpha_N y_2 y_N \vec x_1 · \vec x_N & \dots & \alpha_N^2 y_N^2 \vec x_N · \vec x_N \\\\
\end{bmatrix}
\end{split}
\tag{1 - 12}
$$
可以看出，这是一个对称阵，矩阵的任意元素为$\alpha_i \alpha_j y_i y_j (\vec x_i · \vec x_j), 其中\ i,j \in [1,N]$，因此有：
$$
\frac{1}{2} ||\vec w||^2 = \frac{1}{2} \sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j y_i y_j (\vec x_i · \vec x_j)
\tag{1 - 13}
$$
再来看第二项的化简，结合式（1 - 10)，如下：
$$
\begin{split}
& {\sum_{i=1}^N \alpha_i y_i (\vec w · \vec x_i + b) } \\\\
&= {\sum_{i=1}^N \alpha_i y_i (\vec w · \vec x_i) } + b{ \sum_{i=1}^N \alpha_i y_i} \\\\
&= {\sum_{i=1}^N \alpha_i y_i ((\sum_{j=1}^N \alpha_j · y_j · \vec x_j) · \vec x_i) } + b · 0 \\\\
&= \sum_{j=1}^N \alpha_i y_i(\alpha_1 y_1 \vec w · \vec x_1 + \alpha_2 y_2 \vec w · \vec x_2 + \dots + \alpha_N y_N \vec w · \vec x_N) · \vec x_i \\\\
&= \sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j y_i y_j (\vec x_i · \vec x_j)
\end{split}
\tag{1 - 14}
$$
最后来看第三项${\sum_{i=1}^N \alpha_i }$，该项已是最简形式，保持不变。
综上，我们有：
$$
\begin{split}
& \min \limits_{\vec w, b} L(\vec w, \vec \alpha, b) \\\\
&= \frac{1}{2} \sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j y_i y_j (\vec x_i · \vec x_j) - \sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j y_i y_j (\vec x_i · \vec x_j) + \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 (\vec x_i · \vec x_j) + \sum_{i=1}^N \alpha_i
\end{split}
\tag{1 - 15}
$$
1.3 求极大值
更进一步，式（1 - 2）的对偶问题就是上式再对$\vec \alpha$极大化，如下：
$$
\max \limits_{\vec \alpha} \lbrack -\frac{1}{2} \sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j y_i y_j (\vec x_i · \vec x_j) + \sum_{i=1}^N \alpha_i \rbrack
\tag{1 - 16}
$$
当然，上式的$\vec \alpha$还需要满足约束条件：
$$
\begin{cases}
\sum_{i=1}^N \alpha_i y_i = 0 \\\\
\\\\
\alpha_i \geq 0, \ i=1,2, \dots, N
\end{cases}
\tag{1 - 17}
$$
上式的求解，也是利用构造拉格朗日函数，然后分别对各个拉格朗日乘子求偏导并令偏导式等于零，即可求解出各个拉格朗日乘子的值，即可以求出$\vec \alpha^* = (\alpha_1^*, \ \alpha_2^*, \ \dots, \ \alpha_N^*)$，利用$\vec \alpha^*$以及式（1 - 10），我们就可以求出分割超平面的参数$\vec w^*$。根据式（1 - 10）有：
$$
\begin{split}
\vec w^* &= \sum_{i=1}^N \alpha_i^* · y_i · \vec x_i \\\\
&= \alpha_1^* y_1 \vec x_1 + \ \alpha_2^* y_2 \vec x_2 + \ \dots + \ \alpha_N^* y_N \vec x_N
\end{split}
\tag{1 - 18}
$$
由上式可知，对于$\alpha_i^* = 0$的拉格朗日乘子（约束不起作用），它对整个式子的贡献值$\equiv 0$，因此无论这些乘子取什么值，都不会影响分割超平面，因此我们再计算的时候也只需要代入$\alpha_i^* > 0$的拉格朗日乘子。这里要多说一句，该系列的前一篇机器学习算法系列之三：SVM3中我们已经证明了$\vec w^*$的存在性，并且$\vec w^* = 0$并非问题的解，因此必然存在$\alpha_j^* > 0, \ j \in [1, N]$，即至少有一项不等式（或等式）约束是起作用的。
求出$\vec w^*$后，结合$\vec \alpha^*$的值，再根据KKT条件的互补松弛$\alpha_i^* [y_i(\vec w^* · x_i + b^*) - 1] = 0$，可以求解出分割超平面参数$b^*$，这样整个分割超平面$H(\vec w, b)$就确定了。对$b^*$的求解，由互补松弛条件可知：
1.3.1 $\alpha_i = 0$
当$\alpha_i = 0$即对应的第$i$个样本约束不起作用时，则$\vec b^*$可取任意值而互不松弛条件均能满足，这个时候$\vec b^*$有任意多个解，因此无法由拉格朗日乘子为零的样本来计算$\vec b^*$。
1.3.2 $\alpha_i > 0$
当$\alpha_i > 0$即对应的第$i$个样本约束起作用时，要满足互不松弛条件，则必然有：
$$
y_i(\vec w^* · x_i + b^*) - 1 = 0
\tag{1 - 19}
$$
此时可以利用不为零的拉格朗日乘子求出$\vec b^*$，如下：
$$
\begin{split}
y_i[y_i(\vec w^* · x_i + b^*) - 1] &= y_i · 0 \\\\
y_i^2(\vec w^* · x_i + b^*) - y_i &= 0
\end{split}
$$
$\because$
$y_i^2 \equiv 1, \ \vec w^* = \sum_{j=1}^N \alpha_j^* · y_j · \vec x_j$
$\therefore$
$$
\begin{split}
& (\vec w^* · x_i + b^*) = y_i \\\\
& b^* = y_i - \vec w^* · \vec x_i \\\\
& b^* = y_i - \sum_{j=1}^N \alpha_j^* · y_j · \vec x_j · \vec x_i
\end{split}
\tag{1 - 20}
$$
到此，整个超平面的参数$\vec w^*、b^*$就解出来了，并且从上式可以看出，$b^*$的求解也不依赖于那些拉格朗日乘子为0的样本。
1.4 求解过程梳理
SVM的分割超平面的求解就讲完了（严格来说是线性可分SVM的分割超平面），因为这部分内容实在是太重要了，它是我们深入理解SVM精髓的基石，所以我们重新把分割超平面的求解算法梳理一下，方便大家回顾之前的内容和平滑的切入到下一章的内容。
- 确定样本特征属性维度M，确定样本数量N；
- 根据样本数量确定拉格朗日乘子数量N，并设拉格朗日乘子向量为$\vec \alpha = (\alpha_1, \ \alpha_2, \ \dots, \ \alpha_N)$;
- 求函数$-\frac{1}{2} \sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j y_i y_j (\vec x_i · \vec x_j) + \sum_{i=1}^N \alpha_i$在给定条件$\sum_{i=1}^N \alpha_i y_i = 0$及$\alpha_i \geq 0, \ i=1, 2, 3, \dots, N$下的极值点（注意：极值点有可能在边界上取得。）；
- 利用上一步求得的解$\vec \alpha^* = (\alpha_1^*, \ \alpha_2^*, \ \dots, \ \alpha_N^*)$计算$\vec w^* = \sum_{i=1}^N \alpha_i^* · y_i · \vec x_i$；
- 取任意一个非零拉格朗日乘子$\alpha_i^*$对应的样本$(\vec x_i , y_i)$计算$b^* = y_i - \sum_{j=1}^N \alpha_j^* · y_j · \vec x_j · \vec x_i$；
- 利用上述结果得出分割超平面方程$\vec w^* · \vec x + b^* = 0$。
1.5* 极大转极小转化
顺便提一句，上述极大化问题还可以转换为如下的极小化问题，本质没有发生任何变化：
$$
\begin{cases}
\min \limits_{\vec \alpha} \lbrack \frac{1}{2} \sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j y_i y_j (\vec x_i · \vec x_j) - \sum_{i=1}^N \alpha_i \rbrack \\\\
\\\\
\sum_{i=1}^N \alpha_i y_i = 0 \\\\
\\\\
\alpha_i \geq 0, \ i=1,2, \dots, N
\end{cases}
\tag{1 - 21}
$$
1.6 实例
理论比较抽象，我们用一个例子来说明上述求解过程，帮助理解消化。注：以下例子选自李航老师的《统计学习方法》P107的例2，略有改动和补充说明。
1.6.1 已知条件
三个样本点$x_1 = (3,3)^T, \ x_2 = (4,3)^T, \ x_3 = (1,1)^T $，两个正样本$y_1 = +1, \ y_2 = +1$，一个负样本$y_3 = -1$。
1.6.2 解决问题
利用1.4节的求解算法求出分割超平面。
1.6.3 求解过程
特征向量维度$M = 2$，样本数量$N = 3$；
设拉格朗日乘子向量$\vec \alpha = (\alpha_1, \ \alpha_2, \ \alpha_3)$;
求$\max \limits_{\vec \alpha} \lbrack -\frac{1}{2} \sum_{i=1}^3 \sum_{j=1}^3 \alpha_i \alpha_j y_i y_j (\vec x_i · \vec x_j) + \sum_{i=1}^3 \alpha_i \rbrack$在限制条件$\alpha_1, \ \alpha_2, \ \alpha_3 \in [0, \ +\infty) $及$\alpha_1 · (+1) + \alpha_2 · (+1) + \alpha_3 · (-1) = \alpha_1 + \alpha_2 - \alpha_3 = 0$下的极值:
$$
\begin{split}
& \max \limits_{\vec \alpha} \lbrack -\frac{1}{2} \sum_{i=1}^3 \sum_{j=1}^3 \alpha_i \alpha_j y_i y_j (\vec x_i · \vec x_j) + \sum_{i=1}^3 \alpha_i \\\\
&= -\frac{1}{2} (18 \alpha_1^2 + 25 \alpha_2^2 + 2 \alpha_3^2 + 42 \alpha_1 \alpha_2 - 12 \alpha_1 \alpha_3 - 14 \alpha_2 \alpha_3) \\\\
& \ \ - \alpha_1 - \alpha_2 - \alpha_3
\end{split}
\tag{1 - 22}
$$
记上式为$f(\alpha_1 , \alpha_2 , \alpha_3)$，将$\alpha_3 = \alpha_1 + \alpha_2$代入上式有：
$$
f(\alpha_1 , \alpha_2 , \alpha_3) = -4 \alpha_1^2 - \frac{13}{2} \alpha_2^2 - 10 \alpha_1 \alpha_2 + 2\alpha_1 + 2 \alpha_2
\tag{1 - 23}
$$ 分别对$\alpha_1、\alpha_2$求偏导有：
$$
\begin{split}
\begin{cases}
\frac{\partial f(\alpha_1 , \alpha_2 , \alpha_3)}{\partial \alpha_1} \ = \ -8 \alpha_1 - 10 \alpha_2 + 2= 0 \\\\
\frac{\partial f(\alpha_1 , \alpha_2 , \alpha_3)}{\partial \alpha_2} \ = \ -13 \alpha_2 - 10 \alpha_1 + 2= 0
\end{cases}
\end{split}
\tag{1 - 24}
$$ 联立上式得唯一解：
$$
\begin{cases}
\alpha_1^* = \frac{3}{2} \\\\
\alpha_2^* = -1
\end{cases}
\tag{1 - 25}
$$虽然求出了解，但是该解对应的$\alpha_2^*$不满足约束$\alpha_2^* \geq 0$，因此极大值必然在边界处。因为拉格朗日乘子的取值范围都是$[0 , \ +\infty)$，显然拉格朗日乘子不可能取右边界$+\infty$，因此必然在左边界即0处取极值。
若$\alpha_1 = 0$，则$f(\alpha_1 , \alpha_2 , \alpha_3) = - \frac{13}{2} \alpha_2^2 + 2 \alpha_2$，再用该式对$\alpha_2$求一阶偏导可求出极值点为$\alpha_2^* = -\frac{2}{13}$，不符合拉格朗日乘子恒为非负的条件，因此最大值不在此处。
- 若$\alpha_2 = 0$，则$f(\alpha_1 , \alpha_2 , \alpha_3) = - 4 \alpha_1^2 + 2 \alpha_1$，再用该式对$\alpha_1$求一阶偏导可求出极值点为$\alpha_1^* = \frac{1}{4}$，且$\frac{\partial f^2}{\partial \alpha_1^2} = -8$，则在$\alpha_2^* = 0 ， \alpha_1^* = \frac{1}{4}$处$f(\alpha_1 , \alpha_2 , \alpha_3)$取得最大值，此时有$\alpha_3^* = \alpha_1^* + \alpha_2^* = \frac{1}{4}$。
根据$\alpha_1^* = \alpha_3^* = \frac{1}{4}$可求得$\vec w^*$：
$$
\begin{split}
\vec w^* &= \alpha_1^* y_1 \vec x_1 + \alpha_3^* y_3 \vec x_3 \\\\
&= \frac{1}{4} · (+1) · (3,3)^T + \frac{1}{4} · (-1) · (1,1)^T \\\\
&= (\frac{1}{2} , \frac{1}{2})^T
\end{split}
\tag{1 - 26}
$$再根据$\vec w^* = (\frac{1}{2}, \frac{1}{2})^T$或选择拉格朗日乘子$\alpha_1^* = \frac{1}{4}(或 \alpha_3^* = \frac{1}{4})$来计算$b^*$：
$$
\begin{split}
b^* &= y_1 - [\alpha_1^* y_1 (\vec x_1 · \vec x_1) + \alpha_3^* y_3 (\vec x_3 · \vec x_1)]\\\\
&= +1 - [\frac{1}{4} · (+1) · (3,3)^T·(3,3)^T + \frac{1}{4} · (-1) · (1,1)^T·(3,3)^T] \\\\
&= -2 \\\\
\\\\
或 \\\\
\\\\
b^* &= y_1 - \vec w^* · \vec x_1 \\\\
&= +1 - (\frac{1}{2}, \frac{1}{2})^T · (3,3)^T \\\\
&= -2
\end{split}
$$所以分割超平面为：
$$
注：上式中$x^{(i)}$表示某个样本的第$i$个属性的值。
\frac{1}{2} x^{(1)} + \frac{1}{2} x^{(2)} - 2 = 0
\tag{1 - 27}
$$
1.7 小结
从上述过程可以看出，SVM分割超平面的求解是先把不易求解的原始极小极大最优化问题转换为易于求的极大极小最优化问题。
转换后，通过先求解极小化问题，求解出超平面参数$\vec w, b$与拉格朗日乘子$\vec \alpha$的关系，从而消去原最优化问题中的未知变量$\vec w, b$，只剩下$\vec \alpha$。
消元后，再求解极大化(也可以转换为求极小化)问题的解，从而求出$\vec \alpha$。
求出$\vec \alpha$后即可求出分割超平面，其公式为：
$$
(\sum_{i=1}^N \alpha_i^* · y_i · \vec x_i) \cdot \vec x + b^* = \sum_{i=1}^N \alpha_i^* · y_i · (\vec x_i \cdot \vec x) + b^* = 0
\tag{1 - 28}
$$
此外，其分类决策函数则为：
$$
f(x) = sign \lgroup \sum_{i=1}^N \alpha_i^* · y_i · (\vec x_i \cdot \vec x) + b^* \rgroup
\tag{1 - 29}
$$
二、支持向量
在上一节中我们提到了分割超平面参数$\vec w, \ b$的求解不需要那些拉格朗日乘子为0的样本参与，因为这些样本对分割超平面的位置不产生任何有效约束力。从几何上来理解，这些样本因为远离交界处，因此不会影响分割面。
而对于那些拉格朗日乘子不为0的样本（更准确的说，是训练数据集中对应于$\alpha_i > 0$的样本），它们直接决定了分割超平面，我们称这些样本点为支持向量，如下图2-1所示：
2.1 定义
由上可知，支持向量一定在边界处，它的文字性定义为：
在线性可分情况下，训练数据集的样本点中与分离超平面距离最近的样本点的实例成为支持向量。
——摘自李航《统计学习方法》$P_{102}$
其数学定义式如下：
$$
\begin{split}
& y_i (\vec w^* · \vec x_i + b^*) - 1 = 0 , \ \alpha_i^* > 0\\\\
\\\\
& 或 \\\\
\\\\
& (\vec w^* · \vec x_i + b^*) = \pm1 , \ \alpha_i^* > 0\\\\
\end{split}
$$
2.2 小结
支持向量机的名字就是由支持向量而来的，从这一点出发就可以理解支持向量的重要性。一旦决定分割超平面的支持向量保持不变，其它的点无论怎么改变，都不会影响分割超平面，也就不会影响我们的分类决策模型。但是线性SVM由于其线性特征，导致其对噪声数据比较敏感，它只适用于线性可分的数据（即能通过画一条直线区分开）。一旦不同类别数据之间互有交错（即线性不可分），就无法求出分割超平面，线性可分/线性非可分数据的示例如下图所示：
对于线性非可分数据的问题，我们将在本系列的下一篇文章里讲怎么解决。
实际上，就我们生活中的数据而言，根据最后学习出来的SVM的类型，可以划分成以下三种情况：
- 线性可分（最简单，最理想）；
- 线性非可分（比线性可分稍微复杂一点，但仍然是比较好处理的）；
- 非线性（比线性的情况复杂的多，需要借助核技巧）。
注意：刚接触SVM的同学很容易把非线性和线性非可分两个概念混淆在一起。关于非线性支持向量机，会在本系列的后面讲。
