《统计学习方法》-感知机

今天又看了李航博士写的有关感知机的文章，觉得讲解得非常细腻，通俗易懂，也让我醍醐灌顶。在这里自己再转述一遍，以让自己能够更加深刻的理解和记忆,所以路过的同学如果看到有写得不全的地方，还望见谅。

感知机定义 #

要知道的是，感知机是二类分类的线性分类模型。其输入为$X\subseteq R^n$，输出为$Y={+1,-1}$。 $R^n$表示特征空间。

要理解的感知机模型的函数：$f(x)=sign(w.x+b)$其中$w$和$b$为感知机的模型参数，$w$叫做权值(weight)，$b$叫做偏置(bias),$w.x$表示$w$和$x$的内积。

数据集的线性可分性定义 #

给定一个数据集$T={(x_1,y_1),(x_2,y_2),…,(x_N,y_n)}$，其中$x_i$输入特征空间$R_n$中的点。$y_i$为$-1$或者$+1$。那么如果存在某个超平面S$w.x+b=0$能够将数据集的正实例点和负实例点完全正确地划分到超平面的两侧，也就是$w.x_i+b>0\Rightarrow y=+1$$w.x_i+b<0\Rightarrow y=-1$那么数据集$T$就是线性可分数据集(linearly separable data set),否则，成数据集$T$线性不可分。

感知机的学习策略是为其定义一个损失函数，公式为：$L(w,b)=-\sum _{x_i\in M}y_i(w.x_i+b)$显然损失函数是非负的。如果没有分类点，损失函数值为０，而且，误分类点越少，误分类点离超平面越近，损失函数值就越小。一个特定的样本点的损失函数：在误分类时是参数$w,b$的线性函数，在正确分类时是０．因此，给定训练数据集$T$,损失函数$L(w,b)$是$w,b$的连续可导函数。

损失函数可以用代码这样实现：$w\leftarrow w+\eta y_ix_i$$b\leftarrow b+\eta y_i$，其中$\eta =1$，下面会讲到


    def update(item):
        global w, b
        w[0] += 1 * item[1] * item[0][0]
        w[1] += 1 * item[1] * item[0][1]
        b += 1 * item[1]

例：

有训练集T=[[(3, 3), 1], [(4, 3), 1], [(1, 1), -1]],试用感知机学习算法的原始形式求感知机模型$f(x)=sign(w.x+b)$

感知机学习算法的原始形式 #

选取初始值$w_0,b_0$，任意值，一般都为０就行。
在训练集中选取数据$(x_i,y_i)$
如果$y_i(w.x_i+b)\le 0$,则$w\leftarrow w+\eta y_ix_i$$b\leftarrow b+\eta y_i$
转至(2)，直至训练集中没有误分类点。

这种学习算法直观上有如下解释：当一个实例点被误分类，即位于分离超平面的错误一侧时，则调整$w,b$的值，使分离超平面向该分类点的一侧移动，以减少分类点与超平面间的距离，直至超平面越过该误分类点使其被正确分类。

按照上述方法求解$w,b$，$\eta =1$

取初值$w_0=0,b_0=0$
对$x_1=(3,3)^T,y_1(w_0.x_1+b_0)=0$,未能被正确分类，更新$w,b$$$w_1=w_0+y_1x_1=(3,3)^T,b_1=b_0+y_1=1$$得到线性模型$$w_1.x+b_1=3x^{(1)}+3x^{(2)}+1$$
对$x_1,x_2$,显然，$y_i(w_1.x_i+b_1)>0$，被正确分类，不修改$w,b$；对$$x_3=(1,1)^T,y_3(w_1.x_3+b_1)<0$$，被误分类，更新$w,b$.$$w_2=w_1+y_3x_3=(2,2)^T,b_2=b_1+y_3=0$$得到线性模型$$w_2.x+b_2=2x^{(1)}+2x^{(2)}$$

如此继续下去，直到$$w_7=(1,1)^T,b_7=-3$$ $$w_7.x+b_7=x^{(1)}+x^{(2)}-3$$对所有数据点$$y_i(w_7.x_i+b_7)>0$$,没有误分类点，损失函数达到极小。

分离超平面为　　　　$x^{(1)}+x^{(2)}-3=0$

感知机模型为　　　　$f(x)=sign(x^{(1)}+x^{(2)}-3)$

代码实现：

training_set = [[(3, 3), 1], [(4, 3), 1], [(1, 1), -1]]
w = [0,0]
b = 0

# update parameters using stochastic gradient descent
def update(item):
    global w,b
    w[0] += 1 * item[1] * item[0][0]
    w[1] += 1 * item[1] * item[0][1]
    b += 1 * item[1]
    print w,b

# calculate the functional distance between 'item' an the dicision surface
def cal(item):
    res = 0
    for i in range(len(item[0])):
        res += item[0][i] * w[i]
    res += b
    res *= item[1]
    return res

# check if the hyperplane can classify the examples correctly
def check():
    flag = False
    for item in training_set:
        if cal(item) <= 0:
            flag = True
            update(item)
    if not flag: #always False
        print "RESULT: w: " + str(w) + " b: " + str(b)
    return flag

if __name__=="__main__":
    for i in range(10):
        check()
    print "The training_set is not linear seperable..."

[3, 3] 1
[2, 2] 0
[1, 1] -1
[0, 0] -2
[3, 3] -1
[2, 2] -2
[1, 1] -3
RESULT: w: [1, 1] b: -3
RESULT: w: [1, 1] b: -3
RESULT: w: [1, 1] b: -3
RESULT: w: [1, 1] b: -3
RESULT: w: [1, 1] b: -3
The training_set is not linear seperable...

感知机学习算法的对偶形式 #

对偶形式的基本思想是，将$w$和$b$表示为实例$x_i$和标记$y_i$的线性组合的形式，通过求解其系数而求得$w$和$b$.不失一般性，在之前的算法中我们将$w_0,b_0$初始为０，通过$w\leftarrow w+\eta y_ix_i$$b\leftarrow b+\eta y_i$逐步修改$w,b$，设修改$n$次，则$w,b$关于$(x_i,y_i)$的增量分别是$a_iy_ix_i$和$a_iy_i$，这里$a_i=n_i\eta $.这样，从学习过程中不难看出，最后学习到的$w,b$可以分别表示为$w=\sum _{i=1}^{N}\alpha _iy_ix_i$ $b=\sum _{i=1}^{N}\alpha _iy_i$这里，$\alpha \ge 0$，$i=1,2,…,N$，当$\eta =1$时，表示第$i$个实例点由于误分而进行更新的次数。实例点更新次数越多，意味着它距离分离超平面越近，也就越难正确分类。

例

有训练集T=[[(3, 3), 1], [(4, 3), 1], [(1, 1), -1]],试用感知机学习算法的原始形式求感知机模型$f(x)=sign(w.x+b)$

感知机学习算法的对偶形式

$a\leftarrow 0,b\leftarrow 0$
在训练集中选取数据$(x_i,y_i)$
如果$$y_i(\sum _{j=1}^{N}\alpha _jy_jx_j.x_i+b)\le 0$$，则$$a_i\leftarrow a_i+\eta $$ $$b\leftarrow b+\eta y_i$$
转至(2)，直至训练集中没有误分类点。

对偶形式中训练实例仅以内积的形式出现。为了方便，可以预先将训练集中实例间的内积计算出来并以矩阵的形式存储，这个矩阵就是所谓的Gram矩阵(Gram matrix)$G=[x_i.x_j]_{N.N}$

按照上述方法求解：

取$\alpha _i=0,i=1,2,3,b=0,\eta =1$

计算Gram矩阵$$G= \begin{bmatrix} 18 & 21 & 6 \ 21 & 25 & 7 \ 6 & 7 & 2 \ \end{bmatrix} $$

误分条件$$y_i(\sum _{j=1}^{N}\alpha _jy_j.x_i+b)\le 0$$参数更新$$\alpha _i\leftarrow \alpha _i+1，b\leftarrow b+y_i$$

迭代。

$$w=2x_1+0x_2-5x_3=(1,1)^T$$ $b=-3$分离超平面　$$x^{(1)}+x^{(2)}-3=0$$感知机模型$$f(x)=sign(x^{(1)}+x^{(2)}-3)$$

代码实现：

import numpy as np
 
# An example in that book, the training set and parameters' sizes are fixed
training_set = np.array([[[3, 3], 1], [[4, 3], 1], [[1, 1], -1]])
 
a = np.zeros(len(training_set), np.float)
b = 0.0
Gram = None
y = np.array(training_set[:, 1])
x = np.empty((len(training_set), 2), np.float)
for i in range(len(training_set)):
    x[i] = training_set[i][0]
history = []
 
def cal_gram():
    """
    calculate the Gram matrix
    :return:
    """
    g = np.empty((len(training_set), len(training_set)), np.int)
    for i in range(len(training_set)):
        for j in range(len(training_set)):
            g[i][j] = np.dot(training_set[i][0], training_set[j][0])
    return g
 
 
def update(i):
    """
    update parameters using stochastic gradient descent
    :param i:
    :return:
    """
    global a, b
    a[i] += 1
    b = b + y[i]
    history.append([np.dot(a * y, x), b])
    print a, b # you can uncomment this line to check the process of stochastic gradient descent
 
 
# calculate the judge condition
def cal(i):
    global a, b, x, y
 
    res = np.dot(a * y, Gram[i])
    res = (res + b) * y[i]
    return res
 
 
# check if the hyperplane can classify the examples correctly
def check():
    global a, b, x, y
    flag = False
    for i in range(len(training_set)):
        if cal(i) <= 0:
            flag = True
            update(i)
    if not flag:
 
        w = np.dot(a * y, x)
        print "RESULT: w: " + str(w) + " b: " + str(b)
        return False
    return True
 
 
if __name__ == "__main__":
    Gram = cal_gram()  # initialize the Gram matrix
    for i in range(20):
        if not check(): break

[ 1.  0.  0.] 1.0
[ 1.  0.  1.] 0.0
[ 1.  0.  2.] -1.0
[ 1.  0.  3.] -2.0
[ 2.  0.  3.] -1.0
[ 2.  0.  4.] -2.0
[ 2.  0.  5.] -3.0
RESULT: w: [1.0 1.0] b: -3.0

参考 #

[1] http://www.hankcs.com/ml/the-perceptron.html

[2] http://www.cnblogs.com/OldPanda/archive/2013/04/12/3017100.html