概述

**感知机(perceptron)**是个二类分类的线性分类模型,该算法对应于特征空间将实例划分为正负两类的分离超平面,属于判别模型。判别模型是一种对未观测数据y与已观测数据x之间关系进行建模的方法,直接对条件概率p(y|x;θ)建模。直接假设判别函数的参数形式是已知的 ,然后基于训练样本,使用某种学习算法,来学习判别函数的参数值,被称为判别式方法,感知机所得到的是一个线性判别函数。而一般来说,寻找线性判别函数的问题,会被形式化为极小化准则函数的问题,以分类为目的的准则函数可以是样本的风险函数,或者是训练误差。 从机器学习的角度来讲,感知机属于监督学习(supervised learning),它是一个单层的二分类器。感知机算法非常重要,它是神经网络和SVM的基础。感知机算法如下图所示:

感知机算法

感知机模型

算法定义

假设我们的输入空间(特征空间)是X⊆R,输出空间是y={+1,−1}。输入xX表示实例的特征向量,对应于输入空间(特征空间)的点;输出y∈y表示实例的类别。由输入空间到输出空间的函数:

$$ f(x)=sign(w \cdot x+b) $$

其中,其中w和b为感知机模型参数,$w \in R^n$ 叫做weight或者weight vector,$b \in R$ 叫做bias,$w \cdot x$ 表示w和x的内积,sign是符号函数。

$$ sign(x) = \begin{cases} +1, &x \ge 0 \
-1, &x \lt 0 \end{cases} $$

感知机的几何模型

  • 线性方程 $w \cdot x +b=0$

  • 对应超平面S,w为法向量,b为截距,分离正负两类

  • 分离超平面如下如图所示:

    感知机模型

感知机算法模型

学习策略

再详细介绍感知机学习策略之前,我们先了解下数据集的线性可分 vs 线性不可分

线性可分

给定一个数据集$T={(x_1,y_1),(x_2,y_2)……(x_n,y_n)}, x_i \in X=R^n,y_i \in Y,i=1,2,3…N$ ,如果存在某个超平面S

$$w \cdot x + b = 0$$

能够将数据集的正实例点(+1)和负实例点(-1)完全正确地划分到超平面的两侧,即对所有的$y_i = +1$的实例,有$w \cdot x_i + b > 0$ ;对所有$y_i=-1$的实例,有$w \cdot x_i + b < 0$,则称数据集T为线性可分数据集(Linearly Separable Data Set),否则为数据集T为线性不可分。也可以利用不同样本集用凸包包起来,判断不同凸包的边是否有交叉来判断是否线性可分。

现在神经网络对于线性可分的定性理解特点如下:

线性可分的特点:低维转高维,还能保持原来的线性可分性的特点;但是高维转低维就不能保持原来的线性可分性。

线性不可分的特点:只要是线性变化到高维或者是低维,都不能是线性可分;但是经过一次非线性变化+仿射变换后或者多次就能实现线性可分。

我们看下示意图:

线性可分 vs 线性不可分

假设数据集T是线性可分的,感知机的学习目标是求得一个能将T完全正确分离的超平面S,即确定参数w和b。因此需要确定一个学习策略,即定义经验损失函数并将损失函数最小化。自然想到可能选择误分类点的个数,但是误分类点的个数不是参数w,b的连续可导函数,不易优化;我们选择误分类点到超平面的总距离作为我们的优化策略。首先写出输入空间 $R^n$ 中任一点 $x_i$到超平面S的距离:

$$ \frac {1}{||w||} \cdot (w^T \cdot x_i + b) $$

假设误分类的点集为M,则任意误分类点$(x_i,y_i) \in M,$

$$w^T \cdot x_i+b>0时,有y_i=-1\\\ w^T \cdot x_i + b <0时,有y_i=+1$$

所以误分类点$(x_i,y_i) \in M $,那么所有误分类点到超平面S的距离

$$-\frac{1}{||w||} \sum_{(x_i,y_i) \in M}\cdot y_i(w^T \cdot x_i+b)$$

先不考虑权重空间的范数,得到我们的损失函数,即感知机的经验风险函数:

$$ argminL(w,b)=-\sum_{(x_i,y_i) \in M} y_i(w^T \cdot x_i +b) $$

**所以,感知机模型的学习问题,最终成为了损失函数最小化的问题。**这里需要注意一个特殊情况: 如果样本点刚好落在了决策超平面上这个点可以不予考虑。

求解感知机的损失函数

感知机算法的原始形式

假设误分类点集合M是固定的,那么损失函数L(w,b)的梯度优化则如下:

$$ \nabla_w L(w,b)=-\sum_{x_i \in M} y_i \cdot x_i \
\nabla_b L(w,b)=-\sum_{x_i \in M} y_i $$

随机选择一点对w,b进行更新,如下:

$$ w:=w+ \alpha \cdot x_i \cdot y_i \
b:=b+\alpha \cdot y_i $$

如果数据集是线性可分的,那么感知机算法一定是收敛的,即经过有限步的迭代后可以得出正确分类样本数据的参数w,b,虽然一定收敛但是分割超平面却不一定是惟一的。 详细的证明算法可以参考数学上的Novikoff定理,很多书籍资料都给出了详细的证明,感兴趣的朋友可以看下。

感知机算法原始形式代码实现

比如我们业务现在需要对现有数据进行分类,比如用户是否为真实用户还是作弊用户,这是一个简单的二分类模型。我们现在拿到了样本的数据,需要对该数据进行分类,当然前提是该数据集是线性可分的,可以将数据集进行可视化和初步分析看一下数据。比如样本实例只有两维特征,正实例点是[10,8],[6,9],[6,8],[7,6],[7,8],[9,6],[11,3],[10,6],[12,5];负实例点是[1,2],[2,2],[3,1],[1,1],[3,6],[4,4],[3,2],[2,6],[6,2]。我们根据感知器算法进行学习并得到模型。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import numpy as np
class Perceptron(object):
    def __init__(self,data,result):
        #加载训练集数据
        self.data = np.array(data)
        self.result = np.array(result)
        #初始化w和b
        self.length = len(self.data[0])
        self.w = np.zeros((1,self.length))
        self.b = 0
        
    def calculate(self):
        i = 0
        while i < len(self.data):
            if self.result[i] * (np.dot(self.w, self.data[i]) + self.b) <= 0 :
                self.w += self.result[i] * self.data[i]
                self.b += self.result[i]
                i = 0
            else :
                i += 1
            print self.w
            print self.b
perceptron = Perceptron()
perceptron.calculate()

通过算法结果输出为:

$$ w = [7,2]^T \
b = -48 $$

感知机算法的对偶形式

感知机模型最重要的并不是它的原始形式,而是他的对偶形式,这个里的对偶形式就是SVM求解中对偶形式的原型。

每一个线性规划问题,我们称之为原始问题,都有一个与之对应的线性规划问题我们称之为对偶问题。原始问题与对偶问题的解是对应的,得出一个问题的解,另一个问题的解也就得到了。并且原始问题与对偶问题在形式上存在很简单的对应关系:

  • 目标函数对原始问题是极大化,对偶问题则是极小化
  • 原始问题目标函数中的系数,是对偶问题约束不等式中的右端常数,而原始问题约束不等式中的右端常数,则是对偶问题中目标函数的系数
  • 原始问题和对偶问题的约束不等式的符号方向相反
  • 原始问题约束不等式系数矩阵转置后,即为对偶问题的约束不等式的系数矩阵
  • 原始问题的约束方程数对应于对偶问题的变量数,而原始问题的变量数对应于对偶问题的约束方程数
  • 对偶问题的对偶问题是原始问题

对偶形式的基本想法是,将w 和 b表示为实例$x_i和y_i$的线性组合的形式,通过求解其系数而求得 w 和 b ,我们在通过误分类点逐步修改w和b,我们假设修改了n次,则w,b关于$(x_i,y_i)$的增量分别是$\alpha y_i x_i和\alpha y_i$,这里$\alpha_i=n_i η$,这里具体的表示为:

$$ w=\sum_{i=1}^{n}\alpha_i \cdot x_i \cdot y_i \
b=\sum_{i=1}^{n}\alpha_i \cdot y_i $$

输入是我们的训练数据集,输出$\alpha,b$而感知机模型

$$f(x)= sign(\sum_{j=1}^{N}\alpha_j {y_i} {x_i} \cdot x +b)$$

其中$\alpha=(\alpha_1,\alpha_2,\alpha_3,……\alpha_n)^T$ 。

  • $\alpha_0=0,b_0=0 $

  • 随机选取数据实例$(x_i,y_i)$

  • 那么如果 $$ y_i(\sum_{j=1}^{N}\alpha_j y_j x_j \cdot x_i+b) \le 0 \
    \alpha_i=\alpha_i+η \
    b=b+ηy_i $$

或者将数据集中的内积先计算出来并存储为矩阵,即Gram矩阵

$$G=[x_i \cdot x_j]_{M \times N}$$

  • 直到全部没有误分类点

感知机算法对偶形式代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
import numpy as np

class Perceptron:
    def __init__(self,data,result):
        #加载训练集数据
        self.data = np.array(data)
        self.result = np.array(result)
        self.length = len(self.data[0])
    def calculateDual(self):
        #首先计算gram矩阵
        gram = np.matmul(self.data[:,0:self.length],self.data[:,0:self.length].T)
        #初始化参数a、w和b
        a = np.zeros((len(self.data),1))
        w = np.zeros((1,self.length))
        b = 0
        i = 0
        while i < len(self.data) :
            temp = 0
            for j in range(len(self.data)) :
                temp += a[j] * self.result[j] * gram[j][i]
            if self.result[i] * (temp + b) <= 0 :
                a[i] += 1
                b += self.result[i]
                i = 0
            else :
                i += 1
       
        for j in xrange(len(self.data)):
            w += a[j] * self.result[j] * self.data[j]
        print w
        print b
perceptron = Perceptron()
perceptron.calculateDual()