感知机学习及实践

感知机是二分类的线性分类模型，其输入为实例的特征向量，输出为实例的类别，取＋1和－1二值。感知机对应于输入空间中将实例划分为正负两类的分离超平面，属于判别模型，感知机学习旨在求出将训练数据进行线性划分的分离超平面。为此，导入基于误分类的损失函数，利用梯度下降法对损失函数进行极小化，求的感知机模型。感知机算法具有简单而易于实现的优点，分为原始形式和对偶形式。感知机预测是用机器学习得到的感知机模型对新输入的实例进行分类。本篇博客依次从感知机模型、感知机的学习策略(损失函数)、感知机学习算法三方面进行介绍。

感知机模型

定义：假设输入空间(特征向量)是X，输出空间是Y={-1,+1}，输入表示实例的特征向量，对应于输入空间的点，输出y∈Y表示实例的类别，由输入空间到输出空间的函数如下：

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

称为感知机。其中，w和b为感知机模型参数，w∈R叫做权值或权值向量，b 叫做偏置。w·x表示w和x的内积。sign是符号函数，即：

感知机模型的假设空间是定义在特征空间中的所有线性分类模型或线性分类器，即函数集合｛f|f(x)=w·x+b}。线性方程w·x+b=0对应于特征空间中的一个超平面S，其中w是超平面的法向量，b是超平面的截距。这个超平面将特征空间划分为两个部分。位于两部分的点(特征向量)分别被划分为正负两类。因此超平面S称为分离超平面。

感知机学习策略

对于给定的数据集T={(x₁,y₁),(x₂,y₂),···,(x_n,y_n)}，如果存在超平面S，能够将数据集的正实例点和负实例点完全正确地划分到超平面的两侧，即对所有y_i＝+1的实例，都有w·x_i+b>0，对于所有的y_i＝－1的实例，都有w·x_i+b<0，则称数据集T为线性可分数据集，否则T为线性不可分数据集。

假设数据集T是线性可分的，感知机的学习目标是求得一个能将T完全正确分离的超平面S，即确定参数w和b。因此需要确定一个学习策略，即定义经验损失函数并将损失函数最小化。提到损失函数，大家会想到的是误分类点的个数。但是误分类点的个数不是参数w,b的连续可导函数，不易优化。损失函数的另一个选择是误分类点到超平面的距离，输入空间R中任意一点x到超平面S的距离公式如下：

这里，||w||是w的范数。其次对于误分类的数据(x_i,y_i)来说，有-y_i(w·x_i+b)>0成立。因为当w·x_i+b>0时，y_i<0，反之当时w·x_i+b<0，y_i>0。因此误分类点到超平面S的距离为：

这样超平面S的误分类点的集合为M，那么所有误分类点到超平面S的总距离为：

不考虑，得到感知机的损失函数，也就是感知机学习的经验风险函数：

显然，损失函数L(w,b)是非负的。如果没有误分类点，损失函数为0，而且误分类点越少，误分类点离超平面越近，损失函数值就越小。一个特定样本点的损失函数：在误分类时是参数w,b的线性函数，在正确分类时是0。因此，给定训练数据集T，损失函数L(w,b)是w,b的连续可导函数。感知机学习策略是在假设空间中选取损失函数（经验风险函数）最小的模型参数w,b。

感知机学习算法

感知机学习策略已经将问题转化为求解损失函数式的最优化问题，最优化的方法是随机梯度下降法。本节叙述感知机学习的具体算法，包括原始形式和对偶形式，并证明在训练集线性可分的条件下，感知机学习算法的收敛性。

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

感知机学习算法是误分类驱动的，具体采用梯度下降法。首先，任意选取一个超平面w₀、b₀，然后用梯度下降法不断的极小化目标函数。极小化过程中不是一次使误分类集合M中所有点的梯度下降，而是一次随机选取一个误分类点使其梯度下降。

假设误分类点集合M是固定的，那么损失函数L(w,b)的梯度由：

随机选取一个点(x_i、y_i)，对w,b进行更新：

式中（0<≤1）是步长，在统计学习中又称为学习率。这样，通过迭代可以期待损失函数不断减小，直到0。综上得到如下算法：

输入：训练数据集T={(x₀,y₀),...,(x_i,y_i),...,(x_N,y_N)}，其中x_i∈X＝R，y_i∈Y＝{+1,-1},学习率

输出：w,b；感知机模型f(x)=sign(w·x+b)

(1)选取初始值w₀、b₀

(2)在训练数据集T中选择点(x_i,y_i)

(3)如果y_i(w·x_i+b)≤0

(4)转至(2)，直至训练集中没有误分类点。

这种学习算法直观上有如下解释：当一个实例被误分类时，调整w和b的值，使分离超平面向该误分类点的一测移动，以减少该误分类点与超平面间的距离，直至超平面越过该点使其正确分类。这种方法就被称为感知机的原始形式。

说了这么多理论，来个感知机学习原始形式的例子加深一下对理论的理解吧，首先给定了训练数据集，正实例点是[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]。试用感知机原始形式求感知机模型f(x)=sign(w·x+b)。首先是构建最优化问题：

按照如上算法求解w，b。η＝1。初始值w＝0，b＝0。算法如下：

import sys
import numpy as np
#加载训练集数据路径
sys.path.append('/home/work/study/machineLearning/data/')
import recommendations
class Perceptron:
    def __init__(self):
        #加载训练集数据
        self.data = np.array(recommendations.trainingData)
        self.result = np.array(recommendations.resultData)
        #初始化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()

trainingData=[[1,2],[2,2],[3,1],[10,8],[6,9],[1,1],[3,6],[4,4],[6,8],[7,6],[3,2],[7,8],[6,2],[9,6],[11,3],[10,6],[12,5],[2,6]]
resultData=[-1,-1,-1,1,1,-1,-1,-1,1,1,-1,1,-1,1,1,1,1,-1]

recommendations.py

通过算法最终计算w=[7,2]^T,b=-48,从而超平面为7x₁＋2x₂－48=0。

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

对偶形式的基本想法是，将w和b表示为实例x_i和标记y_i的线性组合的形式，通过求解其系数而得到w和b。在如上算法中我们假设w₀和b₀的初始值均为0。对误分类点(x_i,y_i)通过:

逐步修改w和b，假设修改n次，则w，b关于(xi,yi)的增量分别为α_iy_ix_i和α_iy_i，这里α_i＝n_iη。这样不难看出，最后学习到的w和b可以分别表示为:

这里，当α_i≥0，当η＝1时，表示第i个实例点由于误分而进行更新的次数。实例点更新的次数越多，意味着它离分离超平面的距离越近，也就越难正确分类。换句话说，这类实例对学习的结果影响最大。

综上感知机学习算法对偶形式的算法如下：

输入：训练数据集T={(x₀,y₀),...,(x_i,y_i),...,(x_N,y_N)}，其中x_i∈X＝R，y_i∈Y＝{+1,-1},学习率

输出：α,b；感知机模型

(1)选取初始值α₀=0、b₀=0

(2)在训练数据集T中选择点(x_i,y_i)

(3)如果y_i≤0

(4)转至(2)，直至训练集中没有误分类点。

关于为什么第三步α_j＝α_j＋η和b=b+ηy_i链接如下：https://www.zhihu.com/question/26526858。

最后同样用感知机的对偶形式求解一下上个例子的解：

# -*- coding: UTF-8 -*-  
import sys
import numpy as np
#加载训练集数据路径
sys.path.append('/home/work/study/machineLearning/data/')
import recommendations
class Perceptron:
    def __init__(self):
        #加载训练集数据
        self.data = np.array(recommendations.trainingData)
        self.result = np.array(recommendations.resultData)
        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()

求出来解也是7x₁+2x₂-48=0。

总结

感知机是根据输入实例的特征向量x对其进行二类分类的线性分类模型：f(x)=sign(w·x+b).感知机模型对应于输入空间中的分离超平面w·x+b=0
感知机学习的策略是极小化损失函数，该函数对应于误分类点到分离超平面的总距离：

感知机学习算法是基于随机梯度下降法来对损失函数进行最优化的算法，有原始形式和对偶形式。原始形式中，首先任意选取一个超平面，然后用梯度下降法不断极小化目标函数，这个过程中一次随机选取一个误分类点使其梯度下降。
当训练数据集线性可分时，感知机学习算法是收敛的，而且感知机学习算法存在无穷多个解，其解由于不同的初值或不同的迭代顺序而可能有所不同。