Python手撸机器学习系列（八）：硬间隔SVM（原始形式梯度下降法求解）

• • 一、硬间隔SVM
  • • 1.1 原始形式
    • 1.2 原始形式代码实现（梯度下降）
    • 1.3 参考文献

话不多说，直接上图：

最基本的原理如图所示，即找一条最好的线把两边的点分开（本文以二维坐标点为基础举例）

复习一下线性可分的定义：

给定数据集 { ( x 1 , y 1 ) , ( x 2 , y 2 ) , . . . , ( x N , y N ) } {(x_1,y_1),(x_2,y_2),...,(x_N,y_N)} {(x1​,y1​),(x2​,y2​),...,(xN​,yN​)}，其中 y i ∈ { + 1 , − 1 } y_iin{+1,-1} yi​∈{+1,−1}，如果存在某个超平面 w ⋅ x + b = 0 w·x+b=0 w⋅x+b=0能够将数据集的正例和负例分开，即对于所有正例有 w ⋅ x i + b > 0 w·x_i+b>0 w⋅xi​+b>0，对于所有负例有 w ⋅ x i + b < 0 w·x_i+b<0 w⋅xi​+b<0，则称该数据集为线性可分的。

对于线性可分数据，可以使用硬间隔SVM

在线性可分的情况下，SVM需要寻找一条满足如下条件的直线：

1. 这个直线可以分开两类点
2. 这个直线可以最大化两类之间的间隔
3. 这个直线处于间隔的中间，到所有支持向量的距离相等

要找到这样一条直线，我们首先需要掌握两条基本知识：

1. W T X + b = 0 W^TX+b=0 WTX+b=0与 ( a W T ) X + ( a b ) = 0 (aW^T)X + (ab) = 0 (aWT)X+(ab)=0是同一个超平面
2. 一个点 X 0 X_0 X0​到超平面 W T X + b = 0 W^TX+b = 0 WTX+b=0的距离为 d = ∣ W T X 0 + b ∣ ∣ ∣ W ∣ ∣ d = frac{|W^TX_0+b|}{||W||} d=∣∣W∣∣∣WTX0​+b∣​

假设我们现在找到了该直线： w ⋅ x + b = 0 w·x+b=0 w⋅x+b=0

对于支持向量而言，其到该直线的距离为 d d d

则我们可以根据该距离将两组点一分为二：

{ w T x + b ∣ ∣ w ∣ ∣ ≥ d       y = + 1 w T x + b ∣ ∣ w ∣ ∣ ≤ − d       y = − 1 large begin{cases} frac{w^Tx+b}{||w||}geq d y=+1 \large frac{w^Tx+b}{||w||}leq -d y=-1 end{cases} ⎩⎨⎧​∣∣w∣∣wTx+b​≥d     y=+1∣∣w∣∣wTx+b​≤−d     y=−1​

两边同时除去 d d d

{ w T x + b ∣ ∣ w ∣ ∣ d ≥ 1       y = + 1 w T x + b ∣ ∣ w ∣ ∣ d ≤ − 1       y = − 1 large begin{cases} large frac{w^Tx+b}{||w||d}geq 1 y=+1 \large frac{w^Tx+b}{||w||d}leq -1 y=-1 end{cases} ⎩⎨⎧​∣∣w∣∣dwTx+b​≥1     y=+1∣∣w∣∣dwTx+b​≤−1     y=−1​

由于 ∣ ∣ w ∣ ∣ ||w|| ∣∣w∣∣和 d d d是标量，我们可以将 w T ∣ ∣ w ∣ ∣ d frac{w^T}{||w||d} ∣∣w∣∣dwT​和 b ∣ ∣ w ∣ ∣ d frac{b}{||w||d} ∣∣w∣∣db​分别用 w T w^T wT和 b b b表示，相当于上述知识中的 a = 1 ∣ ∣ w ∣ ∣ d a=frac{1}{||w||d} a=∣∣w∣∣d1​，则上述式子可以变为：

{ w T x + b ≥ 1       y = 1 w T x + b ≤ − 1       y = − 1 large begin{cases} large w^Tx+bgeq 1 y=1 \large w^Tx+bleq-1 y=-1 end{cases} ⎩⎨⎧​wTx+b≥1     y=1wTx+b≤−1     y=−1​

即，支持向量到超平面的距离为 d = ∣ w T x + b ∣ ∣ ∣ w ∣ ∣ = 1 ∣ ∣ w ∣ ∣ d = frac{|w^Tx+b|}{||w||}= frac{1}{||w||} d=∣∣w∣∣∣wTx+b∣​=∣∣w∣∣1​

最大化支持向量到超平面的距离即为最大化 1 ∣ ∣ w ∣ ∣ frac{1}{||w||} ∣∣w∣∣1​，也可以看做最小化 ∣ ∣ w ∣ ∣ ||w|| ∣∣w∣∣，为了便于求导和后续计算，我们最小化 1 2 ∣ ∣ w ∣ ∣ 2 frac{1}{2}||w||^2 21​∣∣w∣∣2

最后，可以得到硬间隔SVM的原始形式：
min ⁡ w , b 1 2 ∣ ∣ w ∣ ∣ 2 s . t .     y i ( w i T x i + b ) ≥ 1   , i = { 1 , . . . , N } min_{w,b} frac{1}{2}||w||^2\ s.t. y_i(w_i^Tx_i+b)geq1 ,i={1,...,N} w,bmin​21​∣∣w∣∣2s.t.   yi​(wiT​xi​+b)≥1 ,i={1,...,N}
其中 y i y_i yi​的作用是协调超平面（直线）的左右，1可以更换为任意实数（放缩）

对于原始形式，以及是一个凸优化问题，可以采用许多最优化理论高效求解，这里我还是使用了梯度下降法求解（深度学习惯出来的，最好理解）。

在进行梯度下降之前，得先了解SVM所采用的损失函数：Hinge Loss

Hingle Loss是针对二分类问题提出的，标签值为(+1和-1)，预测值 y ^ hat y y^​为实数，当 y ^ ≥ + 1 hat ygeq +1 y^​≥+1或者 y ^ ≤ − 1 hat yleq -1 y^​≤−1时都能很好地确定该预测值，此时损失为0，而当 y ^ hat y y^​在1到-1之间时，分类器对分类结果不确定了，此时loss不为0，当 y ^ = 0 hat y=0 y^​=0时，loss达到最大。

Hinge Loss在SVM中的数学表达式为：
l ( y ) = m a x ( 0 , 1 − y ⋅ y ^ ) l(y) = max(0,1-y·hat y) l(y)=max(0,1−y⋅y^​)
写作模型输出的格式：
l ( y i ) = m a x ( 0 , 1 − y i ( w T x i + b ) ) l(y_i) = max(0,1-y_i(w^Tx_i+b)) l(yi​)=max(0,1−yi​(wTxi​+b))
所以，对于梯度的更新有两种情况：

1. y i ( w T x i + b ) ≥ 1 y_i(w^Tx_i+b)geq 1 yi​(wTxi​+b)≥1或者 y i ( w T x i + b ) ≤ − 1 y_i(w^Tx_i+b)leq -1 yi​(wTxi​+b)≤−1时，此时分类正确， 1 − y i ( w T x i + b ) < 0 1-y_i(w^Tx_i+b)<0 1−yi​(wTxi​+b)<0， l ( y i ) = 0 l(y_i)=0 l(yi​)=0，损失函数为0，梯度也为0，此时不更新梯度，即模型权重保持不变。（可以理解为支持向量之外的点对模型梯度没有贡献）

2. − 1 < y i ( w T x i + b ) < 1 -1< y_i(w^Tx_i+b)< 1 −1 0 1-y_i(w^Tx_i+b)>0 1−yi​(wTxi​+b)>0， l ( y i ) = 1 − y i ( w T x i + b ) l(y_i)=1-y_i(w^Tx_i+b) l(yi​)=1−yi​(wTxi​+b)，损失函数不为0，按照梯度更新模型权重。

   此时 w w w的梯度为 g w = − y i x i g_w = -y_ix_i gw​=−yi​xi​， b b b的梯度为 g b = − y i g_b = -y_i gb​=−yi​

   更新梯度： w = w − g w   ,   b = b − g b w = w-g_w , b=b-g_b w=w−gw​ , b=b−gb​

代码实现：

注意，图中公式 w T x + b w^Tx+b wTx+b参照的是 x x x是 p p p维列向量的情况，而在代码中 x x x为行向量，由于矩阵乘法的格式，所以代码写出来可能与文中不同

import numpy as np
import matplotlib.pyplot as plt

def get_point():
    x_true =  [[1,1.5],[1,3],[4,5],[2,4]]
    x_false = [[1,0.5],[4,2],[5,1],[4,1]]
    x_all = np.array(x_true+x_false)
    y = [1]*len(x_true) + [-1]*len(x_false)
    return x_all,y,x_true,x_false

def gradient_descent(epochs,x,y,w,b):
    for epoch in range(epochs):
        for i in range(len(y)):
            if y[i]*(x[i].dot(w.T)+b) <= 1:
                w -= lr * (-y[i]*x[i])
                b -= lr * -y[i]
    return w,b

def plot(x_true,x_false,w,b):
    plot_x = np.arange(0,7)
    plot_y = -(w[0]*plot_x+b)/w[1]
    plt.scatter([x[0] for x in x_true],[x[1] for x in x_true] , c='r' , label='+1')
    plt.scatter([x[0] for x in x_false],[x[1] for x in x_false] , c='b',label='-1')
    plt.plot(plot_x,plot_y,c = 'green')
    plt.xlim(0,6)
    plt.ylim(0,6)
    plt.legend()
    plt.plot()
    plt.show()

if __name__ == '__main__':
    x,y,x_true,x_false = get_point()
    w = np.array([0,0],dtype=float)
    b = 0
    lr = 0.01
    epochs = 1000
    w,b = gradient_descent(epochs,x,y,w,b)
    plot(x_true,x_false,w,b)

运行结果：

在实验中，我发现删除、增加除支持向量以外的点确实对于直线没有任何影响

有影响的是迭代次数epochs和学习率，这两个参数调节可以使直线有细微的变化，但当epoch足够大时趋于稳定

另外，测试一下支持向量到直线的距离（分母一致省去）：

print(w.dot(np.array([1,1.5]))+b)  
print(w.dot(np.array([1, 0.5])) + b)

结果：

极为相近，但仍有精度上的差异（忽略正负号）

1. https://zhuanlan.zhihu.com/p/91322308
2. https://zhuanlan.zhihu.com/p/77750026
   https://zhuanlan.zhihu.com/p/31886934
3. 浙江大学 胡浩基 《机器学习》