机器学习小白视角（一）：感知机 （附原始形式和对偶形式Python实现代码）

感知机是二分类的线性模型，是神经网络和SVM的基础。输入特征 x ∈ X x∈X x∈X，输出 y = { + 1 , − 1 } y = {+1 , -1} y={+1,−1}

那么感知机算法可以表示为 f ( x ) = s i g n ( w ⋅ x + b ) f(x) = sign(w·x+b) f(x)=sign(w⋅x+b)，相当于一个简单的线性函数

其中 s i g n ( a ) = { + 1 , if a ≥ 0 − 1 , if a<0 sign(a)= begin{cases} +1, & text {if a$geq$0} \ -1, & text{if a<0} end{cases} sign(a)={+1,−1,​if a≥0if a<0​

数据的线性可分性：存在 w ⋅ x + b = 0 w·x+b = 0 w⋅x+b=0能将数据集中的正负样本分开。说人话就是能找到一条直线将两组不同的点分开。

在这里，感知机的数据集假设为线性可分的，即表示在一堆坐标点中，总能找到一条线将正副样本给分开，并且一般能找到多条线满足要求，如下图所示。

损失函数若选取误分类点的个数，则对于 w w w和 b b b而言不连续可导，不易优化

所以，选取误分类点到超平面S的总距离作为损失函数，即 − 1 ∣ ∣ w ∣ ∣ ∑ x i ∈ M y i ( w ⋅ x i + b ) -frac{1}{||w||}displaystylesum_{x_i∈M}y_i(w·x_i+b) −∣∣w∣∣1​xi​∈M∑​yi​(w⋅xi​+b)，最终不考虑 1 ∣ ∣ w ∣ ∣ frac{1}{||w||} ∣∣w∣∣1​，即得到最终的损失函数：
L ( w , b ) = − ∑ x i ∈ M y i ( w ⋅ x i + b ) L(w,b) = -displaystylesum_{x_i∈M}y_i(w·x_i+b) L(w,b)=−xi​∈M∑​yi​(w⋅xi​+b)
推导：某一点到S的距离为 − 1 ∣ ∣ w ∣ ∣ ∣ w ⋅ x 0 + b ∣ -frac{1}{||w||}|w·x_0+b| −∣∣w∣∣1​∣w⋅x0​+b∣，而误分类数据会有 − y i ( w ⋅ x i + b ) > 0 -y_i(w·x_i+b)>0 −yi​(w⋅xi​+b)>0，所以上上式可以转化为 − 1 ∣ ∣ w ∣ ∣ y i ( w ⋅ x i + b ) -frac{1}{||w||}y_i(w·x_i+b) −∣∣w∣∣1​yi​(w⋅xi​+b)，总距离： − 1 ∣ ∣ w ∣ ∣ ∑ x i ∈ M y i ( w ⋅ x i + b ) -frac{1}{||w||}displaystylesum_{x_i∈M}y_i(w·x_i+b) −∣∣w∣∣1​xi​∈M∑​yi​(w⋅xi​+b)

L ( w , b ) L(w,b) L(w,b)非负，没有误分类点则为0

使用随机梯度下降(SGD)来优化参数，算法如下：

1. 选取初值 w 0 w_0 w0​， b 0 b_0 b0​

2. 在训练集中选取数据 ( x i , y i ) (x_i,y_i) (xi​,yi​)

3. 如果 y i ( w ⋅ x i + b ) ≤ 0 y_i(w·x_i+b)leq 0 yi​(w⋅xi​+b)≤0，则有：

   w = w + η y i x i w = w+eta y_ix_i w=w+ηyi​xi​

   b = b + η y i b = b + eta y_i b=b+ηyi​

4. 转至2，直到没有误分类点

其中 η eta η为学习率， w w w和 b b b的梯度通过对损失函数 L ( w , b ) L(w,b) L(w,b)求导而来

import numpy as np
import matplotlib.pyplot as plt

x_true = np.array([[3,3],[4,3]])
x_false = np.array([[1,1]])
y = [1]* len(x_true) + [-1] * len(x_false)
x_all = np.vstack([x_true,x_false])

w = np.array([0,0])
lr = 1
b = 0
i = 0
#循环判断每一个样本有没有误分类，有则更新参数重新开始判断
while i 
实现结果：
 
 

    
     
      
       
        w
       
      
      
       w
      
     
    w和
    
     
      
       
        b
       
      
      
       b
      
     
    b变化过程以及最终的平面S：
 
 
换一组更复杂的数据测试：
 
 
3.感知机对偶形式 
对偶形式是将原始形式中的
    
     
      
       
        w
       
      
      
       w
      
     
    w和
    
     
      
       
        b
       
      
      
       b
      
     
    b表示为
    
     
      
       
        
         x
        
        
         i
        
       
      
      
       x_i
      
     
    xi​和
    
     
      
       
        
         y
        
        
         i
        
       
      
      
       y_i
      
     
    yi​的线性组合，即
 

     
      
       
        
         {
        
        
         
          
           
            
             
              w
             
             
              =
             
             
              
               
                ∑
               
               
                
                 i
                
                
                 =
                
                
                 1
                
               
               
                N
               
              
              
               
                n
               
               
                i
               
              
              
               η
              
              
               
                y
               
               
                i
               
              
              
               
                x
               
               
                i
               
              
             
            
           
          
         
         
          
           
            
             
              b
             
             
              =
             
             
              
               
                ∑
               
               
                
                 i
                
                
                 =
                
                
                 1
                
               
               
                N
               
              
              
               
                n
               
               
                i
               
              
              
               η
              
              
               
                y
               
               
                i
               
              
             
            
           
          
         
        
       
       
        begin{cases} w =displaystylesum_{i = 1}^Nn_ieta y_ix_i \b = displaystylesum_{i=1}^Nn_ieta y_i end{cases} 
       
      
     ⎩⎪⎪⎪⎪⎨⎪⎪⎪⎪⎧​w=i=1∑N​ni​ηyi​xi​b=i=1∑N​ni​ηyi​​
 

    
     
      
       
        
         n
        
        
         i
        
       
      
      
       n_i
      
     
    ni​值越大，表示这个样本被误分类的次数越多，就意味着这个点离我们所需要的超平面越近，左移一点或者右移一点就会误分类，对于SVM而言，这个点极有可能就是支持向量
 
根据原始形式，
    
     
      
       
        f
       
       
        (
       
       
        x
       
       
        )
       
       
        =
       
       
        s
       
       
        i
       
       
        g
       
       
        n
       
       
        (
       
       
        w
       
       
        x
       
       
        +
       
       
        b
       
       
        )
       
       
        =
       
       
        s
       
       
        i
       
       
        g
       
       
        n
       
       
        (
       
       
        
         
          ∑
         
         
          
           j
          
          
           =
          
          
           1
          
         
         
          N
         
        
        
         
          n
         
         
          j
         
        
        
         η
        
        
         
          y
         
         
          j
         
        
        
         
          x
         
         
          j
         
        
        
         ⋅
        
        
         x
        
        
         +
        
        
         
          
           ∑
          
          
           
            i
           
           
            =
           
           
            1
           
          
          
           N
          
         
         
          
           n
          
          
           i
          
         
         
          η
         
         
          
           y
          
          
           j
          
         
         
          )
         
        
       
      
      
       f(x) = sign(wx+b) = sign(displaystylesum_{j=1}^Nn_jeta y_jx_j·x+displaystylesum_{i=1}^Nn_ieta y_j)
      
     
    f(x)=sign(wx+b)=sign(j=1∑N​nj​ηyj​xj​⋅x+i=1∑N​ni​ηyj​)
 
从之前的的优化
    
     
      
       
        w
       
      
      
       w
      
     
    w和
    
     
      
       
        b
       
      
      
       b
      
     
    b，变成了优化
    
     
      
       
        n
       
      
      
       n
      
     
    n
 
误分类的判断条件也变成了
    
     
      
       
        
         y
        
        
         i
        
       
       
        (
       
       
        
         
          ∑
         
         
          
           j
          
          
           =
          
          
           1
          
         
         
          N
         
        
        
         
          n
         
         
          j
         
        
        
         η
        
        
         
          y
         
         
          j
         
        
        
         
          x
         
         
          j
         
        
        
         ⋅
        
        
         x
        
        
         +
        
        
         
          
           ∑
          
          
           
            i
           
           
            =
           
           
            1
           
          
          
           N
          
         
         
          
           n
          
          
           i
          
         
         
          η
         
         
          
           y
          
          
           j
          
         
         
          )
         
         
          <
         
         
          0
         
        
       
      
      
       y_i(displaystylesum_{j=1}^Nn_jeta y_jx_j·x+displaystylesum_{i=1}^Nn_ieta y_j)<0
      
     
    yi​(j=1∑N​nj​ηyj​xj​⋅x+i=1∑N​ni​ηyj​)<0
 
3.1 计算过程 
《统计学习方法》中将
    
     
      
       
        
         n
        
        
         i
        
       
       
        η
       
      
      
       n_ieta
      
     
    ni​η用
    
     
      
       
        
         α
        
        
         i
        
       
      
      
       alpha_i
      
     
    αi​表示
 
 
选取初值
      
       
        
         
          α
         
        
        
         alpha
        
       
      α，
      
       
        
         
          b
         
        
        
         b
        
       
      b
 
 
在训练集中选取数据
      
       
        
         
          (
         
         
          
           x
          
          
           i
          
         
         
          ,
         
         
          
           y
          
          
           i
          
         
         
          )
         
        
        
         (x_i,y_i)
        
       
      (xi​,yi​)
 
 
如果
      
       
        
         
          
           y
          
          
           i
          
         
         
          (
         
         
          
           
            ∑
           
           
            
             j
            
            
             =
            
            
             1
            
           
           
            N
           
          
          
           
            α
           
           
            j
           
          
          
           
            y
           
           
            j
           
          
          
           
            x
           
           
            j
           
          
          
           ⋅
          
          
           
            x
           
           
            i
           
          
          
           +
          
          
           b
          
          
           )
          
          
           ≤
          
          
           0
          
         
        
        
         y_i(displaystylesum_{j=1}^Nalpha_jy_jx_j·x_i+b)leq 0
        
       
      yi​(j=1∑N​αj​yj​xj​⋅xi​+b)≤0，则有：
 

      
       
        
         
          α
         
         
          =
         
         
          α
         
         
          +
         
         
          η
         
        
        
         alpha = alpha+eta
        
       
      α=α+η
 

      
       
        
         
          b
         
         
          =
         
         
          b
         
         
          +
         
         
          η
         
         
          
           y
          
          
           i
          
         
        
        
         b = b + eta y_i
        
       
      b=b+ηyi​
 
 
转至2，直到没有误分类点
 
 
在对偶形式中，样本以内积的形式计算，如果以内积矩阵形式存储，则会大大缩短计算时间，即Gram矩阵：
 

    
     
      
       
        G
       
       
        =
       
       
        [
       
       
        
         x
        
        
         i
        
       
       
        ⋅
       
       
        
         x
        
        
         j
        
       
       
        ]
       
      
      
       G = [x_i·x_j]
      
     
    G=[xi​⋅xj​]，代码可以表示成Gram = x.dot(x.T)
 
3.2 代码实现 
import numpy as np
import matplotlib.pyplot as plt

x_true = np.array([[3, 3], [4, 3]])
x_false = np.array([[1, 1]])
x_all = np.vstack([x_true,x_false])
y = [1]*len(x_true) + [-1] * len(x_false)
n = len(x_all)


a = np.zeros(n)
b = 0
lr = 1

Gram = x_all.dot(x_all.T) #计算G

i = 0
#循环判断每一个样本有没有误分类，有则更新参数重新开始判断
while i < n:
    error = 0
    for j in range(n):
        error += a[j] * y[j] * Gram[j,i]
    if y[i] * (error + b) <= 0: 3 #有负样本
        a[i] += lr
        b += lr * y[i]
        print('a = {},b = {}'.format(a,b))
        i = 0
    else:
        i += 1

w = np.zeros(2)
for j in range(n):
    w += a[j] * y[j] * x_all[j]

print('平面S为：{:.2f}x1 + {:.2f}x2 {} = 0'.format(w[0],w[1], str(b) if b < 0 else '+'+str(b)))

plot_x = [0,1,2,3,4,5]
plot_y = [-(x*w[0]+b)/w[1] for x in plot_x]
plt.figure(figsize =(10,10))
plt.scatter([x[0] for x in x_true], [x[1] for x in x_true] , c = 'blue')
plt.scatter([x[0] for x in x_false], [x[1] for x in x_false] , c = 'red')
plt.plot(plot_x , plot_y , c = 'black')
plt.xlim(0, 5.0) #坐标轴
plt.ylim(0, 5.0)
plt.xlabel('x1',fontsize = 16)
plt.ylabel('x2',fontsize = 16)
plt.pause(0.001)
plt.show()
 
实验结果：
 
 
其中
    
     
      
       
        a
       
      
      
       a
      
     
    a和
    
     
      
       
        b
       
      
      
       b
      
     
    b的变化过程，以及最终的平面S：
 
 
4.结语 
本为初学者，难免有错误，有问题欢迎评论区指出或私信。
 
联系方式：1759412770@qq.com ; zn1759412770@163.com