声明：

         1，本篇为个人对《2012.李航.统计学习方法.pdf》的学习总结。不得用作商用，欢迎转载，但请注明出处（即：本帖地址）。

         2，因为本人在学习初始时有非常多数学知识都已忘记。因此为了弄懂当中的内容查阅了非常多资料。所以里面应该会有引用其它帖子的小部分内容，假设原作者看到能够私信我。我会将您的帖子的地址付到以下。

         3，假设有内容错误或不准确欢迎大家指正。

         4，假设能帮到你，那真是太好了。

概述

         随意选取一超平面w₀、b₀，然后用随机梯度下降算法不断极小化L(w, b)。

                  Ps: 极小化的过程不是一次使M中的全部误分类点的梯度下降，而是随机选取一个误分类点使其梯度下降。

过程概述

         1，对于L(w, b) = -y_i(w·x_i+ b)。L(w, b)的梯度例如以下：

                   ▽w L(w, b) = - y_ix_i

                   ▽b L(w, b) =- y_i

            2，随机选取一个误分类点(x_i, y_i)，对w，b更新：

                   w= w + ηy_ix_i

                   b= b + ηy_i

                   （η为步长。在统计学习中又称学习率）

         这样，通过迭代能够期待L(w,b)不断下降，直到为0。

算法的第一种形式(感知机算法的原始形式)

    输入：

        训练数据集 T={(x₁,y₁),(x₂,y₂),...,(x_n,y_n)}，当中x₁∈Rⁿ，y_i={+1,-1},i=1, 2, ..., n，学习率η(0 < η<= 1)

    输出：

        w, b。感知机模型 f(x) = sign(w·x + b)

    过程:

        1， 选取初值w, b

        2， 在训练集中取数据(x_i,y_i)

        3。 若 y_i(w·x_i+ b) <= 0 即分类不对。则：

                  w= w + ηy_ix_i

                  b= b + ηy_i

                  注：由于此时分类不正确，所以y_i= -1

        4， 转至步骤2，直到训练数据集中无误分类点

    总结：

            若一个实例点被误分类，即：位于超平面的错误一側时，需调整w, b 的值，使分离超平面向该误分类点的一側移动。以降低该误分类点与超平面的距离。直至超平面越过该误分类点使其被正确分类。

例：

         输入：

                   训练数据集 x₁= (3, 3)。x₂ = (4, 3)，为正实例点(被正确分类)。x₃ = (1, 1)为负实例点

         求：

                   f(x)= sign(w·x + b)

                   ps：这里的w = (w⁽¹⁾,w⁽²⁾)，x = (x⁽¹⁾, x⁽²⁾)

         解：

                   1。  令η=1，并取初值w₀ = 0, b₀= 0

                   2，  对x₁= (3, 3)。y_i(w·x_i + b) = 0，未能被正确分类，因此更新w, b

                             w = w + ηy₁x₁ = (3, 3)

                             b= b + ηy₁ = 1

                          获得线性模型：w·x + b = 3x⁽¹⁾ + 3x⁽²⁾ + 1

                   3，  检查该线性模型：

                          对于x₁和x₂，∵正确分类，∴不改动w,b

                          对于x₃= (1, 1)。∵y3(w·x₃ + b) < 0。∴被误分类，∴须要改动w, b

                          继续第三步，更新w, b：

                                  w = w + ηy₃x₃ = (3, 3) + -1 * (1, 1) = (2, 2)

                                  b= b + ηy₃ = 1 + -1 = 0

                          于是，线性模型更新为：

                                     w·x + b = 2x⁽¹⁾+ 2x⁽²⁾

                   4。  迭代上述过程，直到：

                                  w = (1, 1)，b = -3

                          即，线性模型为：

                                  x⁽¹⁾+ x⁽²⁾ – 3

                          此时对全部的点均有y_i(w·x_i+ b) > 0。无误分类点，于是损失函数达到最小。

                   终于求得：

                            分离超平面：x⁽¹⁾+ x⁽²⁾ – 3

                            感知机模型：f(x) =sign(x⁽¹⁾ + x⁽²⁾ – 3)

         附，迭代过程：

         注：

                   上述过程中误分类点先后取：

                            x₁，x₃，x₃，x₃，x₁，x₃，x₃

                            得到 w = (1, 1)， b = -3

                   若误分类点先后取：

                            x₁，x₃，x₃。x₃，x₂，x₃，x₃，x₃，x₁，x₃，x₃

                   那w = (2, 1)， b = -5

                   可见：

                            感知机学习算法假设採用不同的初值或迭代不同的误分类点，那结果也不同。

感知机算法的收敛性

         到这里有个问题：

                   怎么知道对一个数据集，我们可採用感知机学习策略？

         答案就是：

                   在经过有限次搜索后。可找到将训练数据全然正确分类的超平面，也就是说算法具有收敛性。

         Ps1：算法收敛意味着训练数据集线性可分

         Ps2：线性支持向量机可解决上例有多个解的问题

算法的另外一种形式(感知机算法的对偶形式)

         在原始形式中有公式：

                   w= w + ηy_ix_i

                   b= b + ηy_i

         那么如果一共改动了n次，则w，b关于(x_i⁽¹⁾,x_i⁽²⁾)的增量分别为：

                   a_iy_ix_i和 a_iy_i                    (a_i= n_iη)

         即：

         若η=1，则a_i就是第i个点因为误分类而进行更新的次数。即a_i = n_i。

         a_i越大 => 实例点更新次数越多 =>越难正确分类，换句话说：这种实例对学习结果影响更大！

然后，感知机算法的对偶形式的算法例如以下：

    输入：

        线性可分数据集 T={(x₁,y₁),(x₂,y₂),...,(x_n,y_n)}，当中x₁∈Rⁿ。y_i={+1,-1},i=1, 2, ..., n。学习率η(0 < η<= 1)

    输出：

        感知机模型 f(x) = sign( a_iy_ix_i·x + b)

    过程:

        1， 令a = 0。b = 0

        2。  在训练集中取数据(x_i,y_i)

        3，  若

               则：

                    a_i= a_i + η

                    b= b + ηy_i

        4。  转至2直到无误分类数据

               而因为对偶形式的训练实例仅以内积形式出现

               所以我们预先将训练集中实例间的内积计算出来并以矩阵形式存储，即：产生Gram矩阵（格拉姆矩阵）

                    G = [ x_i, y_i ]_n*n

样例

         输入：

                   正样本点x₁= (3, 3)。x₂ = (4,3)

                   负样本点x₃= (1, 1)

         求：

                   感知机模型

         解：

                   1，  令a_i= 0。i = 1, 2, 3。b = 0，η=1

                   2，  计算Gram矩阵

                                  x1·x1  x1·x2  x1·x3  

                          G =  x2·x1  x2·x2  x2·x3  

                                  x3·x1  x3·x2  x3·x3  

                   3，  误分条件

                              y_i( a_iy_ix_i·x + b) <= 0

                          时。參数更新

                              a_i = a_i +1

                              b = b + y_i

                   4，  開始迭代

                          由于这里仅仅有3个点

                          所以：

                              = y_i((a₁y₁x₁·x_i + a₂y₂x₂·x_i + a₃y₃x₃·x_i) + b)

                              = y_i((a₁x₁·x_i + a₂x₂·x_i - a₃x₃·x_i)+ b)

                   4.1，遍历全部的点。然而在对点x₁(第一次迭代)时

                          由于1*(0 + 0*0 – 0*0) = 0  误分类

                          所以。

                              a₁ = a₁ +1 = 0 + 1 = 1

                              b = b + y₁ = 0 + 1 =1

                          如今：

                              a₁ = 1, a₂= 0, a₃ = 0, b = 1

                   4.2, 遍历全部的点

                          对点x₁

                              y₁*(1 *x₁·x₁+ 0 – 0 + 1) = 1*(18 + 1) > 0    被正确分类

                          x2同理，也被正确分类

                          对点x₃

                              y₃*(1 * x₁·x₃ + 0 – 0 + 1) = -1 * (6 +1) < 0  误分类

                          所以。

                              a₃ = a₃ +1 = 0 + 1 = 1

                              b = b + y₃ = 1 - 1 =0

                          如今：

                              a₁ = 1, a₂= 0, a₃ = 1, b = 0

                   4.3, 遍历全部的点。这一步中x₁和x₂被正确分类，而x₃

                              y₃*(1 *x₁·x₃+ 0 – 0 * x₃·x₃ + 0) = -1 * (6 -2) < 0  误分类

                          所以，

                              a₃ = a₃ +1 = 1 + 1 = 2

                              b = b + y₃ = 0 - 1 =-1

                          如今：

                              a₁ = 1, a₂= 0, a₃ = 2, b = -1

                   4.4, 同理，这一步中x₁和x₂被正确分类。而x_{3被误分类}

                          所以，

                              a₃ = a₃ +1 = 3

                              b = b + y₃ = -2

                          如今：

                              a₁ = 1, a₂= 0, a₃ = 3, b = -2

                   4.5, 这一步中刚遍历到x₁时就发现其被误分类

                          所以，

                              a₁ = a₁ +1 = 1 + 1 = 2

                              b = b + y₁ = -2 + 1 =-1

                          如今：

                              a₁ = 2, a₂= 0, a₃ = 3, b = -1

                   4.6，同理，遍历到x₃时发现被误分类

                          更新a₃和b之后，如今：

                              a₁ = 2, a₂= 0, a₃ = 4, b = -2

                   4.7，同理，遍历到x₃时发现被误分类

                          更新a₃和b之后。如今：

                              a₁ = 2, a₂= 0, a₃ = 5, b = -3

                   4.8。全被正确分类

                   5，得出结果：

                              w = 2x₁ + 0x₂-5x₃ = 2(3,3) – 5(1,1) = (1,1)

                              b = -3

                          所以超平面为：

                              x⁽¹⁾ + x⁽²⁾-3 = 0

                          所以感知机模型为：

                               f(x) = sign(x⁽¹⁾ + x⁽²⁾-3)

随机梯度下降算法中感知机原始模式的代码演示样例

#-*-coding:utf-8-*-
# LANG=en_US.UTF-8
# 梯度下降算法 -- 感知机原始模式
# 文件名称：stochastic_gradient_descent.py

_list = [
    [1, 1, -1],
    [3, 3, 1],
    [4, 3, 1],
]

w1 = w2 = 0
b = 0
n = 1
_len = len(_list)

while [ 1 ]:
    num = 0

    for i in _list:
        x1 = i[0]
        x2 = i[1]
        y = i[2]
        judge = y * (w1*x1 + w2*x2 + b)
        if judge <= 0:
            w1 = w1 + y*x1
            w2 = w2 + y*x2
            b = b + y
        else:
            num += 1

    if num == _len:
        print("f(x) = sign( (%s,%s)*x + %s )" % (w1, w2, b) )
        break