感知机模型

2017-08-01

未来几周应该都不会很忙，趁着闲暇时间整理一下机器学习方面的知识。
先从最简单的感知机模型说起。感知机是一种二分类的线性模型，其假设训练数据集是线性可分的，目标是找到一个能够将训练数据集的正样本和负样本完全正确分割开的分离超平面。其实，模型只要找到该分离超平面，学习目的就达到了，并不要求样本能被最大限度地划分。

分类器

分类器能够通过输入的特征向量映射到给定类别中的一个，也就是所谓的物以聚类人以群分。如下图一，蓝色直线将A和B完全分割开，那么该直线$y=ax+b$就是一个分类器。根据分类器是否线性可分的性质，分类器有线性分类器(图一)和非线性分类器（图二图三），从类别上，有二元分类器（图一）和多元分类器（两个类别以上，图二图三），而本章要讨论的感知机模型，就是一个二分类线性模型。

感知机模型

感知机模型很简单，为什么说它简单呢，因为该模型只用了一个线性方程$y = ax + b$ 以及一个符号函数$sign(x)$（初中的知识是不是？）
下面来看下感知机模型的定义。
假设有$N$维的特征输入$X = \lbrace x_1,x_2,…,x_n \rbrace $，输出的类别有两类$ Y = \lbrace +1,-1\rbrace $，则由特征输入映射到类别输出的函数$$f(x) = sign(w*x+b)$$称为感知机模型，其中，$w$ 和$b$是我们要求解的模型的参数，这里的$w$其实是一个跟特征输入维度一样$N$维的权值向量（也称为权重），而参数$b$为偏置（在二维平面上，$b$就是截距）。
我们从公式上去解读下为什么说感知机模型是一个线性二分类模型。
先看符号函数里面的线性方程$$y=w*x+b$$显然，方程$ y = w*x +b $在二维平面上是一条直线，在三维空间上是一个平面，在四维甚至更高维空间上就是一个超平面。（哈哈哈，这个实在是画不出来）

也就是说，不管是在二维三维空间还是更高维空间，超平面都可以将空间一分为二，并且都可以表示成方程$ y = w*x +b $，所以感知机模型首先是一个线性模型。
再看符号函数，这个更简单，符号函数的定义如下：
$$
sign(x)=\begin{cases}
+1,\quad x\geq 0\\
-1, \quad x<0
\end{cases}$$

如果$x>=0$则$f(x)=+1$，否则$f(x)=-1$。那么对于函数$f(x) = sign(w*x+b)$，如果输入样本$w*x+b>=0$，那么该样本会被判为+1类，否则判为-1类。举个例子，回到上文图一，对于直线上方有$w*x+b>0$，所以所有的A样本都会归为+1类，对于直线下方有$w*x+b<0$，这样所有的B样本都会归为-1类。因此，感知机模型是一个线性二分类模型，其任务就是，找到这样的一个超平面，能够把两个不同的分类完全分割开。

学习策略

原理清楚了，那么现在的问题是，给定一个包含正负类的训练样本，我们应该如何找出这样的一个超平面，使之能够将正样例和负样例点完全分割开，也就是应该如何确定模型的参数$w$和$b$

如上图，如何找到一条直线，使之能够将蓝色实例和褐色实例分割开（这里只是举个例子哈，在实际构建模型过程中，涉及的数据动不动就成百上千万，你想拿支笔来，往两个样本点之间一画一条直线，这是妥妥的不行的，更何况实际处理的数据维度一般都有两位数以上）。直接求解好像无从下手，不妨先假设参数$w$和$b$已知，也就是说这个超平面$S$我们已经找到了，但是不知道这超平面对样例数据的分类效果怎样。如何去评估分类的效果呢，一个很自然的想法就是看有多少样例数据是误分类的，也就是将总误分类数作为模型的损失函数，但是这样的函数对于参数$w$和$b$来说不是连续可导的，难以优化。另一种方法就是可以通过衡量误分类点到超平面的总距离来评估效果。高中的时候我们就学过点到平面的距离的公式是这样子的。$$d=\frac{|A*x_0+B*y_0+C*z_0+D|}{\sqrt{A^2+B^2+C^2}}$$ 其中$(A,B,C)$是平面法向量，在这里是权值向量，上面距离公式也可以简写成$$d=\frac{1}{||w||}|wx_0+b|$$ 其中$w=(A,B,C)$，这里||w||也称为$w$的L2范数。
依然以上文图一为例，对于任意一个样本点$(x_i,y_i)$:

如果该样本点是位于直线上方，并且刚好属于类别A的话，那么该样本点被直线正确分类，此时有$w*x_i+b>0,y_i=+1$，显然$-y_i*(w*x_i+b)<0$
如果该样本点位于直线下方，并且刚好属于类别B的的话，那么该样本点被直线正确分类，此时有$w*x_i+b<0,y_i=-1$，显然$-y_i*(w*x_i+b)<0$
如果该样本点位于直线上方，并且刚好属于类别B的的话，那么该样本点被直线错误分类，此时有$w*x_i+b>0,y_i=-1$，显然$-y_i*(w*x_i+b)>0$
如果该样本点位于直线下方，并且刚好属于类别A的的话，那么该样本点被直线错误分类，此时有$w*x_i+b<0,y_i=+1$，显然$-y_i*(w*x_i+b)>0$

所以，对于误分类的点$(x_i,y_i)$来说$-y_i*(w*x_i+b)>0$成立。
我们可以用$-y_i*(w*x_i+b)$（相当于$|w*x_i+b|$）去衡量误分类点的效果，$w*x_i+b$值越大，说明该点离分离超平面越远，误分类效果越差（虽然分错了就是分错了）。如下图中的红色直线对于点A的分类效果明显比点B的要差

有了单个误分类点离超平面的距离，那么对于所有的误分类点有：$$ -\frac{1}{||w||}\sum_i^m y_i(wx_i+b)$$ 其中$m$为误分类点数量。当不考虑$\frac{1}{||w||}$时（$\frac{1}{||w||}$恒大于0，去掉的话不影响评估效果），就得到感知机模型的损失函数$Loss Function$（用来度量模型预测的好坏）：$$ L(w,b) =-\sum_i^m y_i(wx_i+b)$$既然误分类点离分离超平面越远，误分类效果越差，那么，误分类点离分离超平面越近，误分类效果越好，当$$-\sum_i^m y_i(wx_i+b) = 0$$时，样本没有被误分类，所有样本都被超平面恰当地分割开。所以只要找到$w$和$b$使得$L(w,b)$取最小值，此时超平面的分类效果是最好的，这个时候我们可以将参数$w$和$b$的求解转化为最小化函数$L(w,b)$ $$minL(w,b) = -\sum_i^m y_i(wx_i+b)$$

算法实现

最优化方法有很多，比如牛顿下降法、拉格朗日乘子法、共轭梯度下降法、梯度下降法，这里使用最简单也最常用的一样方法：随机梯度下降法（梯度下降法的一种方法）来优化上文提到的损失函数$L(w,b)$ $$L(w,b) = -\sum_i^m y_i(wx_i+b)$$ 梯度其实就是求偏导，随机梯度下降其实就是一次随机选一个误分类点，使其函数值$L(w,b)$往着负梯度方向移动，不断逼近最小值的一个过程。函数$L(w,b)$关于参数$w$和$b$的梯度分别为：$$\nabla_w L(w,b)= -\sum_i^m y_i x_i $$ $$\nabla_b L(w,b)= -\sum_i^m y_i $$ 现在，我们随便找一个分割超平面，比如$w=0,b=0$（注意$w$是一个向量），然后随机选一个实例点，判断$-y_i*(w*x_i+b)$ 是否大于等于0，如果大于等于0则说明该点被误分类，这时对$(w,b)$进行如下更新（如果$-y_i*(w*x_i+b)$小于0则不更新$w$和$b$）：$$w \leftarrow w+\eta y_i x_i$$ $$b \leftarrow b+\eta y_i$$ 这里的$\eta$$(0<=\eta<=1)$为步长，也称为学习率，这样，通过不断选取误分类点，更新参数$(w,b)$，降低函数$L(w,b)$的值，直到$L(w,b)=0$时对应的$(w,b)$的取值就是要求解的值。
算法很简单，分成4步，也就是：

(1)选取初值$(w_0,b_0)$;
(2)在训练数据集中随机选取一个数据$(x_i,y_i)$;
(3)如果$-y_i*(w*x_i+b)>=0$，则进行如下更新：$$w \leftarrow w+\eta y_i x_i$$ $$b \leftarrow b+\eta y_i$$
(4)转至(2)，直至数据集中没有误分类的点或者达到指定的迭代次数。

用python实现基于随机梯度下降的简单感知机模型。

import numpy as np
import random
import matplotlib.pyplot as plt
%matplotlib inline
from sklearn.datasets.samples_generator import make_blobs
#随机生成特征维度为2，分别以[-1,-1],[1,1]为中心，类别方差为0.4,0.5的两个类
x,y = make_blobs(n_samples=100,n_features=2,centers=[[-1,-1],[1,1]],cluster_std=[0.4,0.5])
# 将 0 替换成-1
y[y==0] = -1
w = np.zeros(2)#初始权重赋值为0
b = 0 #初始偏置为0
k=200 #最大迭代次数
l_rate = 0.5 #学习率
i=0
while i <= k:
    i = i+1
    #生成随机数
    random_num = random.randint(0,99)
    #损失函数
    if sum(-y[random_num]*(w*x[random_num] + b)) >= 0:
        #梯度更新权重
        w = w + l_rate*y[random_num]*x[random_num]
        #梯度更新偏置
        b = b + l_rate*y[random_num]
#---------------------画图-------------------------

x1 = -3.0
y1 = -(b + w[0] * x1) /w[1]
x2 = 3.0
y2 = -(b + w[0] * x2) / w[1]
plt.figure(figsize=(8, 6))  
plt.plot([x1,x2],[y1,y2],'r')
plt.scatter(x[:,0],x[:,1],marker='o',c=y,s=50)
plt.xlabel('x1')
plt.ylabel('x2')
plt.show()

因为这里的两个样本区分度太明显，所以经过几次迭代就已经收敛了。最终求得参数$w=[1.03972853 \ 0.97360177] ,b=0$，根据参数$(w,b)$画出的直线如下图所示：

选取不同的初始值$(w,b)$或者不同的误分类点，划分的超平面很有可能会不一样，这也就是为什么在线性可分数据集中，用感知机模型求出来的解有无穷多个。如下面直线$A,B,C$都可作为解。

后记

感知机模型假设训练数据集是线性可分的，如果线性不可分，算法会一直震荡无法收敛，所以其无法处理一些复杂的数据，如在分类器中提到的图二和图三。考虑到实际业务的数据一般比较复杂，简单的感知机模型无法有效地处理如此复杂的数据，所以在建模中很少会使用该模型。但是感知机模型还是比较重要的，为什么这么说呢，因为只要稍微修改下模型的损失函数，感知机模型就可转变为广受欢迎的分类神器：支持向量机，而通过简单的堆叠可演变为神经网络模型。