【机器学习】支持向量机【上】硬间隔

支持向量机

支持向量机（support vector machines，SVM）是一种二分类模型。它的基本模型是定义在特征空间上的间隔最大的线性分类器，其决策方式与感知机一致，但是采用最大间隔的思想进行学习使它有别于感知机。支持向量机学习方法包含构建由简至繁的模型：线性可分支持向量机（linear support vector machine in linearly separable case）、线性支持向量机（linear support vector machine）以及非线性支持向量机（non-linear support vector machine）。当训练数据线性可分时，通过硬间隔最大化（hard margin maximization）学习一个线性的分类器，即线性可分支持向量机，又称为硬间隔支持向量机；当训练数据近似线性可分时，通过软间隔最大化（soft margin maximization），也学习一个线性的分类器，即线性支持向量机，又称为软间隔支持向量机；当训练数据线性不可分时，通过使用核技巧（kernel trick）及软间隔最大化，学习非线性支持向量机。

线性可分支持向量机

硬间隔最大化

给定数据集 D = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , … , ( x n , y n ) } D=\{(x_1,y_1),(x_2,y_2),\dots,(x_n,y_n)\} D={(x1​,y1​),(x2​,y2​),…,(xn​,yn​)}， x i ∈ R d x_i\in \mathbb R^d xi​∈Rd， y i ∈ { − 1 , + 1 } y_i\in \{-1,+1\} yi​∈{−1,+1}，分类学习最基本的想法就是基于训练集 D D D 在样本空间找到一个划分超平面，将不同类别的样本分开。在感知机算法中，参数初值的选取影响最终确定的划分超平面，这是因为能将训练样本分开的划分超平面可能很多，而支持向量机通过对感知机算法进一步限制，意在找到唯一“最佳”划分超平面。

图 1    存在多个划分超平面将两类训练样本分开

直观上看，应该去找位于两类训练样本“正中间”的划分超平面，也就是“最佳”划分超平面，即图 1 1 1 中红色直线，因为该划分超平面对训练样本局部扰动的“容忍”性最好。比如，对于绿色划分超平面而言，紧邻这些超平面的样本仅仅是发生轻微变动，便会出现越过超平面的情况，此时划分超平面将不再能将训练集正确划分，而红色划分超平面距离两类样本都比较远，分类结果受轻微变动的影响最小。换言之，红色划分超平面所产生的分类结果是最鲁棒的，泛化能力最强。

在样本空间中，划分超平面可通过如下线性方程来描述：
w T x + b = 0 w^Tx+b=0 wTx+b=0
其中 w = ( w 1 w 2 … w d ) T w=\left( \begin{matrix} w_1 & w_2 & \dots & w_d \end{matrix} \right)^T w=(w1​​w2​​…​wd​​)T 为法向量，决定了超平面的方向； b b b 为偏置项，（与 w w w 共同）决定了超平面与原点之间的距离。划分超平面可以被法向量 w w w 和偏置 b b b 确定，将超平面记为 ( w , b ) (w,b) (w,b)。样本空间中任意点 x x x 到超平面 ( w , b ) (w,b) (w,b) 的距离可写为
r = ∣ w T x + b ∣ ∣ ∣ w ∣ ∣ r = \frac{|w^Tx+b|}{||w||} r=∣∣w∣∣∣wTx+b∣​
假设超平面 ( w , b ) (w,b) (w,b) 能将训练样本正确分类，即对于 ( x i , y i ) ∈ D (x_i,y_i)∈ D (xi​,yi​)∈D，若 y i = + 1 y_i=+1 yi​=+1，则有 w T x i + b > 0 w^Tx_i+b > 0 wTxi​+b>0；若 y = − 1 y=-1 y=−1，则有 w T x i + b < 0 w^Tx_i+b<0 wTxi​+b<0。令
{ w T x i + b ≥ + 1 , y i = + 1 w T x i + b ≤ − 1 , y i = − 1 (1) \left\{ \begin{matrix} w^Tx_i+b\ge +1,& y_i=+1\\ w^Tx_i+b\le -1,& y_i=-1\\ \end{matrix} \right.\tag{1} {wTxi​+b≥+1,wTxi​+b≤−1,​yi​=+1yi​=−1​(1)

如图 2 2 2 所示，距离超平面最近的这几个训练样本点使式 ( 1 ) (1) (1) 的等号成立，它们被称为“支持向量”（support vector），两个异类支持向量到超平面的距离之和为
γ = 2 ∣ ∣ w ∣ ∣ \gamma = \frac{2}{||w||} γ=∣∣w∣∣2​
它被称为“间隔”（margin）。

图 2    支持向量与间隔

欲找到具有“最大间隔”（maximum margin）的划分超平面，也就是要找到能满足式 ( 1 ) (1) (1) 中约束的参数 w w w 和 b b b，使得 γ \gamma γ 最大，即
max ⁡ w , b 2 ∣ ∣ w ∣ ∣ s . t .      y i ( w T x i + b ) ≥ 1 ,      i = 1 , 2 , … , n \max_{w,b}\frac{2}{||w||} \\ s.t.\space\space\space\space y_i(w^Tx_i+b)\ge 1,\space\space\space\space i=1,2,\dots, n w,bmax​∣∣w∣∣2​s.t.    yi​(wTxi​+b)≥1,    i=1,2,…,n
显然，为了最大化间隔，仅需最大化 ∣ ∣ w ∣ ∣ − 1 ||w||^{-1} ∣∣w∣∣−1，这等价于最小化 ∣ ∣ w ∣ ∣ 2 ||w||^2 ∣∣w∣∣2。上式重写为
min ⁡ w , b 1 2 ∣ ∣ w ∣ ∣ 2 s . t .      y i ( w T x i + b ) ≥ 1 ,      i = 1 , 2 , … , n (2) \min_{w,b}\frac{1}{2}||w||^2 \\ s.t.\space\space\space\space y_i(w^Tx_i+b)\ge1,\space\space\space\space i=1,2,\dots, n \tag{2} w,bmin​21​∣∣w∣∣2s.t.    yi​(wTxi​+b)≥1,    i=1,2,…,n(2)
如果求出了约束最优化问题式 ( 2 ) (2) (2) 的最优解 w ∗ w^* w∗ 和 b ∗ b^* b∗，那么就可以得到最大间隔划分超平面 w ∗ T x + b ∗ = 0 {w^*}^Tx+b^*=0 w∗Tx+b∗=0 及分类决策函数 f ( x ) = s i g n ( w ∗ T x + b ∗ ) f(x)={\rm sign}({w^*}^Tx+b^*) f(x)=sign(w∗Tx+b∗)，即线性可分支持向量机模型。

对偶问题

注意到式 ( 2 ) (2) (2) 本身是个凸优化问题，甚至是凸二次规划问题，能直接用现成的优化计算包求解，但是我们可以考虑其对偶问题，实现更高效的求解。将式 ( 2 ) (2) (2) 作为原始最优化问题，应用拉格朗日对偶性，通过求解对偶问题得到原始问题的最优解。这样做的优点，一是对偶问题往往更容易求解；二是自然引入核函数，进而推广到非线性分类问题。

构建广义拉格朗日函数

L ( w , b , α ) = 1 2 ∣ ∣ w ∣ ∣ 2 + ∑ i = 1 n α i ( 1 − y i ( w T x i + b ) ) = 1 2 ∣ ∣ w ∣ ∣ 2 − ∑ i = 1 n α i y i ( w T x i + b ) + ∑ i = 1 n α i \begin{aligned} L(w, b, \alpha) &= \frac{1}{2} ||w||^2 +\sum_{i=1}^n \alpha_i \big(1-y_i(w^Tx_i+b)\big) \\ &=\frac{1}{2} ||w||^2 -\sum_{i=1}^n \alpha_i y_i(w^Tx_i+b)+\sum_{i=1}^n \alpha_i \end{aligned} L(w,b,α)​=21​∣∣w∣∣2+i=1∑n​αi​(1−yi​(wTxi​+b))=21​∣∣w∣∣2−i=1∑n​αi​yi​(wTxi​+b)+i=1∑n​αi​​

其中， α = { α i } \alpha = \{\alpha_i\} α={αi​} 为拉格朗日乘子，且满足 α i ≥ 0 \alpha_i\ge 0 αi​≥0。

根据拉格朗日对偶性，原始问题的对偶问题为
max ⁡ α min ⁡ w , b L ( w , b , α ) \max_\alpha \min_{w,b}L(w, b, \alpha) αmax​w,bmin​L(w,b,α)
先求 L ( w , b , α ) L(w,b, \alpha) L(w,b,α) 对 w w w 和 b b b 的极小。将拉格朗日函数 L ( w , b , α ) L(w, b, \alpha) L(w,b,α) 分别对 w , b w,b w,b 求偏导并令其等于零
∇ w L ( w , b , α ) = w − ∑ i = 1 n α i y i x i = 0 ∇ b L ( w , b , α ) = − ∑ i = 1 n α i y i = 0 \nabla_w L(w,b,\alpha) = w - \sum_{i=1}^n \alpha_iy_ix_i = 0 \\ \nabla_b L(w,b, \alpha) = -\sum_{i=1}^n \alpha_iy_i=0 ∇w​L(w,b,α)=w−i=1∑n​αi​yi​xi​=0∇b​L(w,b,α)=−i=1∑n​αi​yi​=0
得
w = ∑ i = 1 n α i y i x i (3) w = \sum_{i=1}^n\alpha_iy_ix_i\tag{3} w=i=1∑n​αi​yi​xi​(3)

∑ i = 1 n α i y i = 0 (4) \sum_{i=1}^n\alpha_iy_i = 0\tag{4} i=1∑n​αi​yi​=0(4)

将式 ( 3 ) (3) (3) 代入拉格朗日函数，并利用式 ( 4 ) (4) (4)，得

L ( w , b , α ) = 1 2 ( ∑ i = 1 n α i y i x i ) T ( ∑ j = 1 n α j y j x j ) − ∑ i = 1 n α i y i ( ( ∑ j = 1 n α j y j x j ) T x i + b ) + ∑ i = 1 n α i = 1 2 ∑ i = 1 n ∑ j = 1 n α i α j y i y j ( x i T x j ) − ∑ i = 1 n ∑ j = 1 n α i α j y i y j ( x i T x j ) − b ∑ i = 1 n α i y i + ∑ i = 1 n α i = − 1 2 ∑ i = 1 n ∑ j = 1 n α i α j y i y j ( x i T x j ) + ∑ i = 1 n α i \begin{aligned} L(w,b, \alpha) &= \frac{1}{2} \left( \sum_{i=1}^n\alpha_iy_ix_i \right)^T\left( \sum_{j=1}^n\alpha_jy_jx_j \right) - \sum_{i=1}^n\alpha_iy_i\left( \Big( \sum_{j=1}^n \alpha_jy_jx_j \Big)^Tx_i+b \right) + \sum_{i=1}^n \alpha_i \\ &=\frac{1}{2} \sum_{i=1}^n\sum_{j=1}^n \alpha_i\alpha_jy_iy_j(x_i^Tx_j) - \sum_{i=1}^n\sum_{j=1}^n \alpha_i\alpha_jy_iy_j(x_i^Tx_j) -b\sum_{i=1}^n \alpha_iy_i + \sum_{i=1}^n \alpha_i \\ &= -\frac{1}{2}\sum_{i=1}^n\sum_{j=1}^n \alpha_i\alpha_jy_iy_j(x_i^Tx_j) +\sum_{i=1}^n \alpha_i \end{aligned} L(w,b,α)​=21​(i=1∑n​αi​yi​xi​)T(j=1∑n​αj​yj​xj​)−i=1∑n​αi​yi​((j=1∑n​αj​yj​xj​)Txi​+b)+i=1∑n​αi​=21​i=1∑n​j=1∑n​αi​αj​yi​yj​(xiT​xj​)−i=1∑n​j=1∑n​αi​αj​yi​yj​(xiT​xj​)−bi=1∑n​αi​yi​+i=1∑n​αi​=−21​i=1∑n​j=1∑n​αi​αj​yi​yj​(xiT​xj​)+i=1∑n​αi​​

即

min ⁡ w , b L ( w , b , α ) = − 1 2 ∑ i = 1 n ∑ j = 1 n α i α j y i y j ( x i T x j ) + ∑ i = 1 n α i \min_{w,b} L(w, b,\alpha) = -\frac{1}{2}\sum_{i=1}^n\sum_{j=1}^n \alpha_i\alpha_jy_iy_j(x_i^Tx_j) +\sum_{i=1}^n \alpha_i w,bmin​L(w,b,α)=−21​i=1∑n​j=1∑n​αi​αj​yi​yj​(xiT​xj​)+i=1∑n​αi​

再求 min ⁡ w , b L ( w , b , α ) \min\limits_{w,b} L(w, b,\alpha) w,bmin​L(w,b,α) 对 α \alpha α 的极大，即是对偶问题

max ⁡ α − 1 2 ∑ i = 1 n ∑ j = 1 n α i α j y i y j ( x i T x j ) + ∑ i = 1 n α i s . t .      ∑ i = 1 n α i y i = 0 α i ≥ 0 ,      i = 1 , 2 , … , n \max_\alpha -\frac{1}{2}\sum_{i=1}^n\sum_{j=1}^n \alpha_i\alpha_jy_iy_j(x_i^Tx_j) +\sum_{i=1}^n \alpha_i \\\\ s.t.\space\space\space\space \sum_{i=1}^n \alpha_iy_i = 0 \\ \alpha_i\ge0,\space\space\space\space i=1,2,\dots, n αmax​−21​i=1∑n​j=1∑n​αi​αj​yi​yj​(xiT​xj​)+i=1∑n​αi​s.t.    i=1∑n​αi​yi​=0αi​≥0,    i=1,2,…,n

将目标函数转化为等价的求极小形式

min ⁡ α 1 2 ∑ i = 1 n ∑ j = 1 n α i α j y i y j ( x i T x j ) − ∑ i = 1 n α i s . t .      ∑ i = 1 n α i y i = 0 α i ≥ 0 ,      i = 1 , 2 , … , n \min_\alpha \frac{1}{2}\sum_{i=1}^n\sum_{j=1}^n \alpha_i\alpha_jy_iy_j(x_i^Tx_j) -\sum_{i=1}^n \alpha_i \\\\ s.t.\space\space\space\space \sum_{i=1}^n \alpha_iy_i = 0 \\ \alpha_i\ge0,\space\space\space\space i=1,2,\dots, n αmin​21​i=1∑n​j=1∑n​αi​αj​yi​yj​(xiT​xj​)−i=1∑n​αi​s.t.    i=1∑n​αi​yi​=0αi​≥0,    i=1,2,…,n

原始问题式 ( 2 ) (2) (2) 为凸优化问题，且满足 Slater 条件，所以问题具有强对偶性，而且存在 w ∗ w^* w∗， b ∗ b^* b∗ 和 α ∗ \alpha^* α∗，使 w ∗ w^* w∗ 和 b ∗ b^* b∗ 是原始问题的解， α ∗ \alpha^* α∗ 是对偶问题的解。

由于问题具有强对偶性，所以 KKT 条件成立，即得
y i ( w ∗ T x i + b ∗ ) − 1 ≥ 0 ,      i = 1 , 2 , … , n ∇ w L ( w ∗ , b ∗ , α ∗ ) = w ∗ − ∑ i = 1 n α ∗ y i x i = 0 ∇ b L ( w ∗ , b ∗ , α ∗ ) = − ∑ i = 1 n α ∗ y i = 0 α i ∗ ≥ 0 ,      i = 1 , 2 , … , n α i ∗ ( y i ( w ∗ T x i + b ∗ ) − 1 ) = 0 ,      i = 1 , 2 , … , n y_i({w^*}^Tx_i+b^* )-1\ge 0,\space\space\space\space i=1,2,\dots,n\\\\ \nabla_{w} L(w^*,b^*,\alpha^*) = w^* - \sum_{i=1}^n\alpha^*y_ix_i = 0 \\ \nabla_{b} L(w^*,b^*,\alpha^*) = - \sum_{i=1}^n\alpha^*y_i = 0 \\ \alpha_i^*\ge 0,\space\space\space\space i=1,2,\dots,n\\ \\ \alpha_i^*\big(y_i({w^*}^Tx_i+b^* )-1 \big)=0,\space\space\space\space i=1,2,\dots,n\\ yi​(w∗Txi​+b∗)−1≥0,    i=1,2,…,n∇w​L(w∗,b∗,α∗)=w∗−i=1∑n​α∗yi​xi​=0∇b​L(w∗,b∗,α∗)=−i=1∑n​α∗yi​=0αi∗​≥0,    i=1,2,…,nαi∗​(yi​(w∗Txi​+b∗)−1)=0,    i=1,2,…,n
由此可得
w ∗ = ∑ i = 1 n α i ∗ y i x i (5) w^* = \sum_{i=1}^n \alpha_i^*y_ix_i\tag{5} w∗=i=1∑n​αi∗​yi​xi​(5)
其中至少有一个 α j ∗ > 0 \alpha_j^*>0 αj∗​>0（反证法：假设 α ∗ = 0 \alpha^*=0 α∗=0，由式 ( 5 ) (5) (5) 可知 w ∗ = 0 w^*=0 w∗=0，而 w ∗ = 0 w^*=0 w∗=0 不是原始问题式 ( 2 ) (2) (2) 的解，产生矛盾），对此 j j j 有
y j ( w ∗ T x j + b ∗ ) − 1 = 0 (6) y_j({w^*}^Tx_j+b^*)-1=0\tag{6} yj​(w∗Txj​+b∗)−1=0(6)

将式 ( 5 ) (5) (5) 代入式 ( 6 ) (6) (6)，并注意到 y j 2 = 1 y_j^2=1 yj2​=1，即得
y i ( ∑ i = 1 n α i ∗ y i ( x i T x j ) + b ∗ ) = 1 ∑ i = 1 n α i ∗ y i ( x i T x j ) + b ∗ = y j y_i\Big( \sum_{i=1}^n\alpha_i^*y_i(x_i^Tx_j)+b^* \Big) = 1 \\ \sum_{i=1}^n\alpha_i^*y_i(x_i^Tx_j)+b^* = y_j yi​(i=1∑n​αi∗​yi​(xiT​xj​)+b∗)=1i=1∑n​αi∗​yi​(xiT​xj​)+b∗=yj​
解得
b ∗ = y j − ∑ i = 1 n α i ∗ y i ( x i T x j ) (7) b^* = y_j - \sum_{i=1}^n\alpha_i^*y_i(x_i^Tx_j) \tag{7} b∗=yj​−i=1∑n​αi∗​yi​(xiT​xj​)(7)
划分超平面可以写为
∑ i = 1 n α ∗ y i ( x i T x ) + b ∗ = 0 \sum_{i=1}^n \alpha^* y_i(x^T_ix) + b^* = 0 i=1∑n​α∗yi​(xiT​x)+b∗=0
分类决策函数可以写为
f ( x ) = s i g n ( ∑ i = 1 n α ∗ y i ( x i T x ) + b ∗ ) (8) f(x) = {\rm sign}\Big(\sum_{i=1}^n \alpha^* y_i(x^T_ix) + b^* \Big)\tag{8} f(x)=sign(i=1∑n​α∗yi​(xiT​x)+b∗)(8)
可见，分类决策函数只依赖于输入 x x x 和训练样本输入的内积。式 ( 8 ) (8) (8) 称为线性可分支持向量机的对偶形式。

综上所述，对于给定的线性可分训练数据集，可以首先求对偶问题的解 α ∗ α^* α∗；再利用式 ( 5 ) (5) (5) 和式 ( 7 ) (7) (7) 求得原始问题的解 w ∗ w^* w∗ 和 b ∗ b^* b∗；从而得到分离超平面及分类决策函数。这种算法称为线性可分支持向量机的对偶学习算法，是线性可分支持向量机学习的基本算法。完整算法流程如下：

输入:   线 性 可 分 训 练 集   D = { ( x 1 , y 1 ) , ⋅ ⋅ ⋅ , ( x n , y n ) } ,   其 中   x i ∈ R d ,   y i ∈ { + 1 , − 1 } ,   i = 1 , … , n 过程: \begin{array}{ll} \textbf{输入:}&\space线性可分训练集\space D = \{(x_1,y_1),···,(x_n,y_n)\},\space 其中\space x_i\in \mathbb R^{d},\space y_i\in \{+1,-1\},\space i=1,\dots,n \\ \textbf{过程:} \end{array} 输入:过程:​ 线性可分训练集 D={(x1​,y1​),⋅⋅⋅,(xn​,yn​)}, 其中 xi​∈Rd, yi​∈{+1,−1}, i=1,…,n

1 : 构 造 并 求 解 约 束 最 优 化 问 题 min ⁡ α 1 2 ∑ i = 1 n ∑ j = 1 n α i α j y i y j ( x i T x j ) − ∑ i = 1 n α i s . t .      ∑ i = 1 n α i y i = 0 α i ≥ 0 ,      i = 1 , 2 , … , n 求 得 最 优 解   α ∗ = { α i ∗ } ,   i = 1 , 2 , … , n 2 : 计 算 w ∗ = ∑ i = 1 n α i ∗ y i x i 3 : 选 择   α j ∗ > 0 ,   计 算 b ∗ = y j − ∑ i = 1 n α i ∗ y i ( x i T x j ) 4 : 求 得 划 分 超 平 面 w ∗ T x + b ∗ = 0 分 类 决 策 函 数 f ( x ) = s i g n ( w ∗ T x + b ∗ ) \begin{array}{rl} 1:& 构造并求解约束最优化问题\\ \\ &\begin{array}{c} & \min \limits_\alpha \frac{1}{2}\sum \limits_{i=1}^n\sum \limits_{j=1}^n \alpha_i\alpha_jy_iy_j(x_i^Tx_j) -\sum \limits_{i=1}^n \alpha_i &\\ &s.t.\space\space\space\space \sum\limits_{i=1}^n \alpha_iy_i = 0 \\ &\alpha_i\ge0,\space\space\space\space i=1,2,\dots, n \\\\ \end{array}\\ & 求得最优解 \space \alpha^* = \{\alpha_i^*\},\space i=1,2,\dots,n \\ 2:& 计算\\ \\ &\begin{array}{c} &&w^* = \sum \limits_{i=1}^n \alpha_i^*y_ix_i \end{array}\\\\ 3:& 选择 \space \alpha_j^*>0,\space 计算\\ \\ &\begin{array}{c} &&b^* = y_j - \sum\limits_{i=1}^n\alpha_i^*y_i(x_i^Tx_j) \end{array}\\\\ 4:& 求得划分超平面\\ \\ &\begin{array}{c} &&{w^*}^Tx+b^*=0 \end{array}\\\\ & 分类决策函数\\ \\ &\begin{array}{c} &&f(x)={\rm sign}({w^*}^Tx+b^*) \end{array} \end{array} 1:2:3:4:​构造并求解约束最优化问题​αmin​21​i=1∑n​j=1∑n​αi​αj​yi​yj​(xiT​xj​)−i=1∑n​αi​s.t.    i=1∑n​αi​yi​=0αi​≥0,    i=1,2,…,n​求得最优解 α∗={αi∗​}, i=1,2,…,n计算​​w∗=i=1∑n​αi∗​yi​xi​​选择 αj∗​>0, 计算​​b∗=yj​−i=1∑n​αi∗​yi​(xiT​xj​)​求得划分超平面​​w∗Tx+b∗=0​分类决策函数​​f(x)=sign(w∗Tx+b∗)​​

输出:   划 分 超 平 面 和 分 类 决 策 函 数 \begin{array}{l} \textbf{输出:}\space 划分超平面和分类决策函数 &&&&&&&&&&&&&&&&&& \end{array} 输出: 划分超平面和分类决策函数​​​​​​​​​​​​​​​​​​​

算法 1    线性可分支持向量机学习算法

算法 1 1 1 还遗留着一个问题， α ∗ \alpha^* α∗ 如何求解。注意到约束最优化问题的约束条件 ∑ i = 1 n α i y i = 0 \sum_{i=1}^n\alpha_iy_i=0 ∑i=1n​αi​yi​=0，其中 y i = ± 1 y_i=±1 yi​=±1，所以该等式约束条件可以很容易变形为一个 α i \alpha_i αi​ 由多个其他的 α j \alpha_j αj​ 表示的形式。将 α i \alpha_i αi​ 的表达式代入目标函数，求偏导并令偏导等于零，便可计算出 α ∗ \alpha^* α∗。还应该注意到问题有另外一个不等式约束条件 α i ≥ 0 \alpha_i\ge 0 αi​≥0，所以令偏导为零计算出的 α ∗ \alpha^* α∗ 不一定满足不等式约束，但是这也就意味着最优解在不等式约束边界（即取等）取到。具体做法见下面的例题。

例题：训练数据正样本是 x 1 = ( 3 , 3 ) T x_1 = (3,3)^T x1​=(3,3)T， x 2 = ( 4 , 3 ) T x_2=(4,3)^T x2​=(4,3)T，负样本是 x 3 = ( 1 , 1 ) T x_3=(1,1)^T x3​=(1,1)T，试用算法 1 1 1 求线性可分支持向量机。

根据所给数据，对偶问题为
min ⁡ α      1 2 ∑ i = 1 n ∑ j = 1 n α i α j y u y j ( x i T x j ) − ∑ i = 1 n α i      = 1 2 ( 18 α 1 2 + 25 α 2 2 + 2 α 3 2 + 42 α 1 α 2 − 12 α 1 α 3 − 14 α 2 α 3 ) − α 1 − α 2 − α 3 s . t .        α 1 + α 2 − α 3 = 0        α i ≥ 0 ,      i = 1 , 2 , 3 \begin{aligned} \min_\alpha & \space\space\space\space \frac{1}{2} \sum_{i=1}^n \sum_{j=1}^n\alpha_i\alpha_jy_uy_j(x_i^Tx_j)-\sum_{i=1}^n\alpha_i\\ &\space\space\space\space=\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 \\ s.t. & \space\space\space\space\space\space \alpha_1+\alpha_2-\alpha_3=0\\ & \space\space\space\space\space\space \alpha_i\ge 0,\space\space\space\space i=1,2,3 \end{aligned} αmin​s.t.​    21​i=1∑n​j=1∑n​αi​αj​yu​yj​(xiT​xj​)−i=1∑n​αi​    =21​(18α12​+25α22​+2α32​+42α1​α2​−12α1​α3​−14α2​α3​)−α1​−α2​−α3​      α1​+α2​−α3​=0      αi​≥0,    i=1,2,3​
解这一最优化问题。将 α 3 = α 1 + α 2 \alpha_3=\alpha_1+\alpha_2 α3​=α1​+α2​ 代入目标函数并记为
s ( α 1 , α 2 ) = 4 α 1 2 + 13 2 α 2 2 + 10 α 1 α 2 − 2 α 1 − 2 α 2 s(\alpha_1,\alpha_2) = 4\alpha_1^2+\frac{13}{2}\alpha_2^2 +10\alpha_1\alpha_2 - 2\alpha_1 -2\alpha_2 s(α1​,α2​)=4α12​+213​α22​+10α1​α2​−2α1​−2α2​
对 α 1 \alpha_1 α1​ 和 α 2 \alpha_2 α2​ 求偏导数并令其为 0 0 0，易知 s ( α 1 , α 2 ) s(\alpha_1,\alpha_2) s(α1​,α2​) 在点 ( 3 2 , − 1 ) \left(\begin{matrix} \frac{3}{2},-1 \end{matrix}\right) (23​,−1​) 取极值，但该点不满足约束条件 α 2 ≥ 0 \alpha_2\ge 0 α2​≥0，所以最小值应在边界上达到。

当 α 1 = 0 \alpha_1=0 α1​=0 时，最小值 s ( 0 , 2 13 ) = − 2 13 s(0,\frac{2}{13})=-\frac{2}{13} s(0,132​)=−132​；当 α 2 = 0 \alpha_2=0 α2​=0 时，最小值 s ( 1 4 , 0 ) = − 1 4 s(\frac{1}{4},0)=-\frac{1}{4} s(41​,0)=−41​。于是 s ( α 1 , α 2 ) s(\alpha_1,\alpha_2) s(α1​,α2​) 在 α 1 = 1 4 \alpha_1=\frac{1}{4} α1​=41​， α 2 = 0 \alpha_2=0 α2​=0 达到最小。此时 α 3 = α 1 + α 2 = 1 4 \alpha_3 = \alpha_1+\alpha_2=\frac{1}{4} α3​=α1​+α2​=41​。

这样， α 1 ∗ = α 3 ∗ = 1 4 \alpha_1^*=\alpha_3^*=\frac{1}{4} α1∗​=α3∗​=41​ 对应的样本点 x 1 x_1 x1​ 和 x 3 x_3 x3​ 是支持向量。根据式 ( 5 ) (5) (5) 和 ( 7 ) (7) (7) 计算得
w 1 ∗ = w 2 ∗ = 1 2 b ∗ = − 2 w_1^*=w_2^*=\frac{1}{2}\\ b^* = -2 w1∗​=w2∗​=21​b∗=−2
划分超平面为
1 2 x ( 1 ) + 1 2 x ( 2 ) − 2 = 0 \frac{1}{2} x^{(1)} + \frac{1}{2} x^{(2)} - 2 = 0 21​x(1)+21​x(2)−2=0
分类决策函数为
f ( x ) = s i g n ( 1 2 x ( 1 ) + 1 2 x ( 2 ) − 2 ) f(x) = {\rm sign} \Big( \frac{1}{2} x^{(1)} + \frac{1}{2} x^{(2)} - 2 \Big) f(x)=sign(21​x(1)+21​x(2)−2)