1 概述

感知机（preceptron）是二类分类的线性分类模型，其输入为实例的特征向量，输出为实例的类别，取+1和-1二值。
感知机1957年由Rosenblatt提出，是神经网络与支持向量机的基础。

2 算法

2.1 模型

定义2.1（感知机） 假设输入空间（特征空间）是，输出空间是。输入表示实例的特征向量，对应输入空间（特征空间）的点；输出表示实例的类别。由输入空间到输出空间的如下函数：
(2.1)
称为感知机。其中，和为感知机模型参数，叫做权值（weight）或权值向量（weight vector），叫作偏置（bias），表示和的内积。是符号函数，即
(2.2)
感知机是一种线性分类模型，属于判别模式。感知机模型的假设空间是定义在特征空间中的所有线性分类模型（linear classfication model）或线性分类器（linear classifier），即函数集合。
感知机有如下集合解释：线性方程
(2.3)
对应于特征空间中的一个超平面，其中是超平面的法向量，是超平面的截距。这个超平面将特征空间划分为两部分。位于两部分的点（特征向量）分别被分为正、负两类。因此，超平面成为分离超平面（separating hyperplane），如图2.1所示。
感知机学习，有训练数据集（实例的特征向量机及类别）

其中，，求得感知机模型（2.1），即求得模型参数，。感知机预测，通过学习得到的感知机模型，对于新的输入实例给出其对应的输出类别。

2.2 感知机学习策略

数据集的线性可分性

定义2.2（数据集的线性可分性） 给定一个数据集

其中，，如果存在某个超平面

能够将数据集的正实例点和负实例点完全正确地划分到超平面的两侧，即对所有的实例，有，对所有的实例，有，则称数据集为线性可分数据集（linearly separable data set）；否则，称数据集线性不可分。

感知机学习策略

假设训练数据是线性可分的，感知机学习的目标是求得一个能够将训练集正实例点和负实例点完全正确分开的分离超平面。为了找出这样的超平面，即确定感知机模型，，需要确定一个学习策略，及定义（经验）损失函数并将损失函数极小化。
损失函数的一个自然选择是误分类点的个数。但是，这样损失函数是不是参数，的连续可导函数，不易优化。损失函数的另一个选择是误分类点到超平面的总距离，这是感知机所采用的。为此，首先写出输入空间中任一点到超平面的距离：

这里，是的范数。
其次，对于误分类的数据来说，

成立。因为当时，；而当时，；因此，误分类点到超平面的距离是

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

不考虑，就得到感知机学习的损失函数。
给定训练数据集

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

2.3 感知机学习算法

感知机学习问题转换为求解损失函数式(2.4)的最优化问题，最优化的方法是随机梯度下降法。

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

感知机学习算法是对一下最优化问题的算法。给定一个训练数据集

其中，，求参数，，使其为以下损失函数极小化问题的解
(2.5)
其中为误分类点的集合。
感知机学习算法是误分类驱动的，具体采用随机梯度下降算法（stochastic gradient descent）。首先，任意选取一个超平面，然后用梯度下降法不断地极小化目标函数（2.5）。极小化过程不是一次使中所有误分类点的梯度下降，而是一次随机选取一个误分类点使其梯度下降。
假设误分类点集合M是固定的，那么损失函数的梯度由

随机选取一个误分类点，对进行更新：

式中是步长，在统计学习中又称为学习率（learing rate）。这样，通过迭代可以期待损失函数不断减少，直至为0。综上所述，得到如下算法；
算法2.1（感知机学习算法的原始形式）
输入：训练数据集，其中，，；学习率；
输出：；感知机模型。
（1）选取初始值;
（2）在训练集中选取数据；
（3）如果
(2.6)
(2.7)
（4）转至（2），直至训练集中没有误分类点
这种学习算法直观上有如下解释：当一个实例点被误分类，即位于分离平面的错误一侧时，则调整的值，使分离超平面向该误分类点的一侧移动，以减少该误差分类点与超平面的距离，直至超平面越过该误分类点使其被正确分类。
算法2.1是感知机学习的基本算法，对于后面的对偶形式，成为原始形式。感知机学习算法简单且易于实现。

算法的收敛性

现在证明，对于现行可分数据集感知学习算法原始形式收敛，即经过有限次迭代可以得到一个将训练数据集完全正确划分的分离超平面及感知机模型。
为了便于叙述与推导，将偏置并入权重向量，记作，同样也将输入向量加以扩充，加进常数1，记作。这样，。显然，。
定理2.1（novikoff） 设训练数据集是线性可分的，其中，，则
（1）存在满足条件的超平面将训练数据集完全正确分开；且存在，对所有
(2.8)
（2）令，则感知机算法在2.1在训练集上的误分类次数满足不等式
(2.9)
证明 （1）由于训练数据集是线性可分的，按照定义2.2，存在超平面可将训练数据集完全正确分开，取此超平面为，使。由于对于有限的，均有

所以存在

使

（2）感知机算法从开始，如果实例被误分类，则更新权重。零是第个误分类实例之前的扩充权重向量，即

则第k个误分类实例的条件是
(2.10)
若是被误分类的数据，则和的更新是


即
(2.11)
下面推导两个不等式（2.12）及（2.13）
由式（2.11）及式（2.8）得

由此递推得出不等式（2.12）
(2.12)
(2.13)
由式（2.11）及式（2.10）得

结合不等式（2.12）及式（2.13）即得

定理表明，误分类的次数是有上限的，经过优先次搜索可以找到将训练数据完全正确分开的分离超平面。也就是说，当训练数据集线性可分时，感知机学习算法原始形式迭代是收敛的。但是感知机算法存在许多解，这些解依赖于初值的选择，也依赖于迭代过程中误分类点的选择顺序。为了得到唯一的超平面，需要对分离超平面增加约束条件。这是后面要讲述的线性支持向量机的想法。当训练集线性不可分时，感知机学习算法不收敛，迭代结果会发生震荡。

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

现在考虑感知机学习算法的对偶形式。感知机学习算法的原始形式和对偶形式与支持向量机学习算法的原始形式和对偶形式相对应。
对偶形式的基本想法是，将和表示为实例和标记的线性组合形式，通过求解其系数而求得和。不是一般性，在算法2.1中可假设初始值均为0.对误分类点的增量分别是和，这里。这样，从学习过程不难看书，最后学习得到的可以分别表示为
(2.14)
(2.15)
这里，，当时，表示第个实例点由于误分而进行更新的次数。实例点更新次数越多，意味着它距离分离超平面越近，也就越难正确分类，换句话说，这样的实例对学习结果影响最大。
下面对照原始形式来叙述感知机学习算法的对偶形式。
算法2.2（感知机学习算法的对偶形式）
输入：训练数据集，其中，，；学习率；
输出：；感知机模型，其中。
（1）；
（2）在训练集中选取数据；
（3）如果


（4）转至（2），直至没有误分类数据
对偶形式中训练形式仅以内积的形式出现。为了方便，可以预先将训练集中实例间的内积计算出来并以矩阵的形式存储，这个举证就是所谓的Gram举证（Gram matrix）

3 实现

3.1 原始算法实现（基于sklearn）

import numpy as np
class Perceptron(object):
    def __init__(self, eta=1, max_iteration=100):
        self.max_iteration = max_iteration
        self.eta = eta
        self.w_ = None
        self.b_ = None
    def _sign(self, x):
        """
        对特征向量取符号函数
        :param x:特征向量
        :return: 分类符号
        """
        return 1 if np.dot(x, self.w_) + self.b_ > 0 else -1
    def fit(self, x_train, y):
        assert len(x_train) == len(y), \
            "the size of x_train must be equal to the size of y_train"
        self.w_ = np.array([0.0] * (len(x_train[0])))  # 取初值 w=[0,0,..,0] b=0
        self.b_ = 0
        cnt = 0
        length = len(x_train)
        while cnt < self.max_iteration:  # 迭代次数限制条件
            cnt += 1
            error_cnt = 0  # 没有错误时则跳出循环
            for i in range(length):
                tem_y = self._sign(x_train[i, :])
                if tem_y * y[i] <= 0:  # 若存在误差变量
                    error_cnt += 1
                    tmp = self.eta * y[i] * x_train[i, :]
                    tmp = tmp.reshape(self.w_.shape)
                    self.w_ = tmp + self.w_  # w权值更新
                    self.b_ = self.b_ + y[i]  # b偏置更新
                    print('第%d次迭代：\n更新后参数 w 为%s，b 为%s' % (cnt, str(self.w_), str(self.b_)))
                    break
            if error_cnt == 0:
                print("训练完成，第%d次迭代时退出" % cnt)
                break
    def predict(self, x_predict):
        """结果待预测数据集x_predict,返回表示x_predict的结果向量"""
        assert self.w_ is not None and self.b_ is not None, \
            "must fit before predict"
        return np.array([self._sign(x) for x in x_predict])
    def __repr__(self):
        return "Perceptron(w=%s,b=%s)" % (self.w_, self.b_)
def create_data():
    X_train = np.array([[1, 1], [3, 3], [4, 3]])
    y = [-1, 1, 1]
    return X_train, y
if __name__ == '__main__':
    X_train, y = create_data()
    p = Perceptron()
    p.fit(X_train, y)
    print(p.__repr__())

3.2 对偶形式实现（待实现）

4 实践

4.1 一般使用流程

4.2 超参数和模型参数

4.3 基于scikit-learn的使用

5 问题集合

1. Minsky与Papert指出：感知机因为是线性模型，所以不能表示复杂的函数，如异或（XOR）。验证感知机为什么不能表示异或。
2.模仿例题1，构建从训练数据集求解感知机模型的例子。
3.证明以下定理：样本集线性可分的充分必要条件是正实例点所构成的凸壳与负实例点集所构成的凸壳互不相较。

6 继续阅读

详见《统计机器学习》第二版参考文献

CHANGELOG

2020年12月19日11:50:22
第一版更新，参考自《统计机器学习》第二版 -