《李航：统计学习方法》笔记之感知机

感知机学习问题转化为求解损失函数式（1）的最优化问题，最优化的方法是随机梯度下降法。感知机学习算法是误分类驱动的，具体采用随机梯度下降法。首先，任意选取一个超平面w₀，b₀，然后用梯度下降法不断极小化目标函数式（1）。极小化的过程不是一次使M中所有误分类点的梯度下降，而是一次随机选取一个误分类点使其梯度下降。

损失函数L(w,b)的梯度是对w和b求偏导，即：

其中，（0<<=1）是学习率，即学习的步长。综上，感知机学习算法如下：

这种算法的基本思想是：当一个实例点被误分类，即位于分类超平面错误的一侧时，则调整w和b，使分类超平面向该误分类点的一侧移动，以减少该误分类点与超平面的距离，直到超平面越过该误分类点使其被正确分类为止。

需要注意的是，这种感知机学习算法得到的模型参数不是唯一的，它会由于采用不同的参数初始值或选取不同的误分类点，而导致解不同。为了得到唯一的分类超平面，需要对分类超平面增加约束条件，线性支持向量机就是这个想法。另外，当训练数据集线性不可分时，感知机学习算法不收敛，迭代结果会发生震荡。而对于线性可分的数据集，算法一定是收敛的，即经过有限次迭代，一定可以得到一个将数据集完全正确划分的分类超平面及感知机模型。

以上是感知机学习算法的原始形式，下面介绍感知机学习算法的对偶形式，对偶形式的基本想法是，将w和b表示为实例x _i和标记y _i的线性组合形式，通过求解其系数而求得w和b。对误分类点（x _i, y _i）通过

所以，感知机学习算法的对偶形式如下：

感知机的原始形式和对偶形式在解决问题的计算上是一致的，但是他们的思想不同，原始形式的基本思想是对于误分类点，调整w和b，使分类超平面向该误分类点的一侧移动，以减少该误分类点与超平面的距离，直到超平面越过该误分类点使其被正确分类为止。而对偶形式的基本思想是将w和b表示成x和y的线性组合形式，从而求出w和b。

1）原始形式代码如下：

[cpp]  view plain copy  
 #include <iostream>  
 using namespace std;  
   
 int x[3][2] = {  
     {3, 3},  
     {4, 3},  
     {1, 1}  
 };  
   
 int y[3] = {1, 1, -1};  
   
 int w[2] = {0};  
 int b = 0;  
   
 int L(int y, int* x)  
 {  
     int temp = (w[0] * x[0] + w[1] * x[1] + b) * y;  
     if (temp <= 0)  
         return 1;//存在错误点  
     else  
         return 0;  
 }  
   
 int main(void)  
 {  
     int j = 1;  
     while (true)  
     {  
         cout << j++ << " ";  
           
         int i;  
         int num = 0;  
         for (i = 0; i < 3; i++)  
         {  
             if (L(y[i], x[i]) == 1)  
             {  
                 cout << "error point:";  
                 cout << "x" << i <<" w:";  
                 int j;  
                 for (j = 0; j < 2; j++)  
                 {  
                     w[j] += y[i] * x[i][j];  
                     cout << w[j] << " ";  
                 }  
                 b += y[i];  
                 cout << "b:" << b <<endl;  
                 num++;  
                 break;  
             }  
         }  
         if (num == 0)  
             break;  
     }  
     return 0;  
 }  

实验结果：

1 error point:x0 w:3 3 b:1

2 error point:x2 w:2 2 b:0

3 error point:x2 w:1 1 b:-1

4 error point:x2 w:0 0 b:-2

5 error point:x0 w:3 3 b:-1

6 error point:x2 w:2 2 b:-2

7 error point:x2 w:1 1 b:-3

这跟p30的结果是一样的，不过要注意的是，在极小化的过程中，为了达到书中的结果，选择的误分类点都是第一次遇到的误分类点，而实际上在选择误分类点时应该采用随机的方法来选取，而且每次梯度下降的时候并不是对所有误分类点进行梯度下降，而是只对随机选择的一个误分类点进行梯度下降。结果与误分类点的选择有关。

2）对偶形式，代码如下：

[cpp]  view plain copy  
 #include <iostream>  
 using namespace std;  
   
 int x[3][2] = {  
     {3, 3},  
     {4, 3},  
     {1, 1}  
 };  
   
 int y[3] = {1, 1, -1};  
   
 int b = 0;  
 int a[3] = {0};  
 int G[3][3] = {  
     {18, 21, 6},  
     {21, 25, 7},  
     {6, 7, 2}  
 };//Gram matrix  
 int L(int j)  
 {  
     int temp = 0;  
     for (int i=0 ;i < 3; i++)  
     {  
         temp += a[i] * G[i][j] * y[i];  
     }  
     temp += b;  
     temp *= y[j];  
     if (temp <= 0)  
         return 1;//存在错误点  
     else  
         return 0;  
 }  
   
 int main(void)  
 {  
     int j = 1;  
     while (true)  
     {  
         cout << j++ << " ";  
           
         int i;  
         int num = 0;  
         for (i = 0; i < 3; i++)  
         {  
             if (L(i) == 1)  
             {  
                 cout << "error point:";  
                 cout << "x" << i <<" a:";  
                 int j;  
                 a[i] += 1;  
                 for (j = 0; j < 3; j++)  
                 {  
                     cout << a[j] << " ";  
                 }  
                 b += y[i];  
                 cout << "b:" << b <<endl;  
                 num++;  
                 break;  
             }  
         }  
         if (num == 0)  
             break;  
     }  
     return 0;  
 }  