感知机

• 感知机模型
• 感知机学习策略
• 感知机学习算法
• 算法的收敛性
• 感知机学习算法的对偶形式

感知机实现二分类模型

• 梯度下降法
• scikit-learn 感知机学习

感知机（perceptron）是二类分类的线性分类模型，其输入为实例的特征向量，输出为实例的类别，取+1和–1二值。感知机对应于输入空间（特征空间）中将实例划分为正负两类的分离超平面，属于判别模型。感知机学习旨在求出将训练数据进行线性划分的分离超平面，为此，导入基于误分类的损失函数，利用梯度下降法对损失函数进行极小化，求得感知机模型。

感知机模型

1. 假设输入空间（特征空间）是 ，输出空间是 ，输入 表示实例的特征向量，对应于输入空间（特征空间） 的点；输出 表示实例的类别。由输入空间到输出空间的如下函数：
   
   称为感知机。其中 和 称为感知机模型参数。 叫作权值（weight）或权值向量（weight vector）， 叫作偏置（bias）， 表示 和 的内积。
   是符号函数，即
   
   感知机是一种线性分类模型，属于判别模型。
   
   
2. 感知机有如下几何解释：线性方程 ，对应于特征空间 中的一个超平面 ，其中 是超平面的法向量， 是超平面的截距。这个超平面将特征空间划分为两个部分。位于两部分的点（特征向量）分别被分为正、负两类。因此，超平面 称为分离超平面（separating hyperplane）。
   

感知机学习策略

1. 给定数据集 ，其中，，，，如果存在某个超平面
   
   能够将数据集的正实例点和负实例点完全正确地划分到超平面的两侧，即对所有 的实例 ，有 ，对所有 的实例 ，有 ，则称数据集 为线性可分数据集（linearly separable data set）；否则，称数据集 线性不可分。
   
   
2. 损失函数的一个自然选择是误分类点的总数。但是，这样的损失函数不是参数 的连续可导函数，不易优化。
   
   
3. 损失函数的另一个选择是误分类点到超平面 的总距离，这是感知机所采用的。为此，首先写出输入空间 中任一点 到超平面 的距离：
   
   其次，对于误分类的数据 来说， 成立，因为当 时，，当 时，。因此，误分类点 到超平面 的距离是：
   
   这样，假设超平面 的误分类点集合为 ，那么所有误分类点到超平面 的总距离为：
   
   不考虑 ，就得到感知机学习的损失函数。这个损失函数就是感知机学习的经验风险函数。
   
   
4. 证明空间 中任一点 到超平面 的距离：
   设点 到超平面 的距离为 ，点 在超平面 的投影为 ，则
   由于向量 与 平面的法向量 平行， 所以
   
   又
   
   所以
   
   即
   

感知机学习算法

1. 给定数据集 ，其中，，，，求参数 ，使其为以下损失函数极小化问题的解：
   
   其中 为误分类点的集合。
   
   
2. 感知机学习算法是误分类驱动的，具体采用随机梯度下降法（stochastic gradient descent）。假设误分类点集合 是固定的，那么损失函数 的梯度由
   
   给出。随机选取一个误分类点 ， 对 进行更新：
   
   式中 是步长，在统计学习中又称为学习率（learning rate）。这样，通过迭代可以期待损失函数 不断减小，直到为0。
   
   
3. 感知机模型
   1>> 选取初值
   2>> 在训练集中选取数据
   3>> 如果 ，则 ，
   4>> 转至 2>>，直至训练集中没有误分点。

算法的收敛性

为了方便推导，将偏置 并入权重向量 ，记作 ，同样也将输入向量加以扩充，记作 。这样， ，。显然，。

1. 设数据集 是线性可分的，其中，，，，则
   
   
   <1> 存在满足条件 的超平面 将训练数据集完全正确分开；且存在 ，对所有 ，有 。
   
   
   <2> 令 ，则感知机 在训练数据集上的误分类次数 满足不等式 。
   
   
2. 证明 <1>：由于训练数据集是线性可分的，存在超平面可将训练数据集完全正确分开，取此超平面为 ，使 。由于对有限的 ，均有
   
   所以存在
   
   使
   
   
   
3. 证明 <2>：感知机算法从 开始，如果实例被误分类，则更新权重。令 是第 个误分类实例之前的扩充权重向量，即
   
   则第 个误分类实例的条件是
   
   若 是被 误分类的数据， 则 和 的更新是
   
   即
   
   下面推导两个不等式
   1>>



2>>
   
   结合以上两个不等式得
   
   
   
4. 上述证明表明，误分类的次数 是有上界的，经过有限次搜索可以找到将训练数据完全正确分开的分离超平面。也就是说，当训练数据集线性可分时，感知机学习算法原始形式迭代是收敛的。

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

1. 对偶形式的基本想法是，将 和 表示为实例 和标记 的线性组合的形式，通过求解其系数而求得 和 。
   
   
2. 设 均为 0，对误分类点 , 通过
   
   逐步修改 ，设修改 次，则 关于 的增量分别是 和 ，这里的 ，最后学习到的 可以分别表示为
   
   这里，， ，当 时，表示第i个实例点由于误分而进行更新的次数，即 。实例点更新次数越多，意味着它距离分离超平面越近，也就越难正确分类。换句话说，这样的实例对学习结果影响最大。
   
   
3. 感知机模型 ，其中 。
   1>> 选取初值
   2>> 在训练集中选取数据
   3>> 如果 ，则 ，
   4>> 转至 2>>，直至训练集中没有误分点。
   
   
4. 对偶形式中训练实例仅以内积的形式出现。为了方便，可以预先将训练集中实例间的内积计算出来并以矩阵的形式存储，这个矩阵就是所谓的Gram矩阵（Gram matrix）
   
   例如 ，那么其Gram矩阵为
   

感知机实现二分类模型

梯度下降法

import pandas as pd
import numpy as np
import matplotlib.pyplot as plt
from sklearn.datasets import load_iris


class Perceptron(object):
    def __init__(self, s):
        # s: 权重参数个数
        # omega: 权重参数
        # b: 斜率
        # eta: 学习率
        self.omega = np.ones(s, dtype=np.float32)
        self.b = 0
        self.eta = 0.1
    
    # 符号函数
    def sign(self, x, omega, b):
        return np.dot(x, omega) + b
    
    # 拟合函数，梯度下降
    def fit(self, x_train, y_train):
        while True:
            errors = 0
            for index in range(len(x_train)):
                _x = x_train[index]
                _y = y_train[index]
                if _y * self.sign(_x, self.omega, self.b) <= 0:
                    self.omega = self.omega + self.eta * np.dot(_y, _x)
                    self.b = self.b + self.eta * _y
                    errors += 1
            if errors == 0:
                break


if __name__ == '__main__':
    # 获取鸢尾花数据集
    iris = load_iris()
    df = pd.DataFrame(iris.data, columns=iris.feature_names)
    df['label'] = iris.target
    df.columns = ['sepal length', 'sepal width', 'petal length', 'petal width', 'label']
    # 生成训练样本，只取 sepal length，sepal width 作为样本特征
    train = np.array(df.iloc[:100, [0, 1, -1]])
    x_train, y_train = train[:, :-1], train[:, -1]
    y_train = np.array([1 if i==1 else -1 for i in y_train])
    # 初始化感知机模型
    pmodel = Perceptron(len(train[0])-1)
    # 拟合训练
    pmodel.fit(x_train, y_train)
    print('omage: ', pmodel.omega)
    print('b: ', pmodel.b)
    # 绘制拟合函数
    length_points = np.linspace(4, 7, 10)
    width_points = -(pmodel.omega[0] * length_points + pmodel.b)/pmodel.omega[1]
    plt.plot(length_points, width_points, label='fitting')
    plt.plot(train[:50, 0], train[:50, 1], 'bo', color='blue', label='0')
    plt.plot(train[50:100, 0], train[50:100, 1], 'bo', color='orange', label='1')
    plt.xlabel('sepal length')
    plt.ylabel('sepal width')
    plt.legend()

scikit-learn 感知机学习

import pandas as pd
import numpy as np
from sklearn.datasets import load_iris
from sklearn.linear_model import Perceptron


def fit(x_train, y_train):
    # fit_intercept 训练模型是否需要截距项
    pmodel = Perceptron(fit_intercept=True, max_iter=1000, shuffle=False, eta0=0.01)
    pmodel.fit(x_train, y_train)
    return pmodel


if __name__ == '__main__':
    # 获取鸢尾花数据集
    iris = load_iris()
    df = pd.DataFrame(iris.data, columns=iris.feature_names)
    df['label'] = iris.target
    df.columns = ['sepal length', 'sepal width', 'petal length', 'petal width', 'label']
    # 生成训练样本，只取 sepal length，sepal width 作为样本特征
    train = np.array(df.iloc[:100, [0, 1, -1]])
    x_train, y_train = train[:, :-1], train[:, -1]
    y_train = np.array([1 if i==1 else -1 for i in y_train])
    # 使用 sklearn 感知机模型拟合训练
    pmodel = fit(x_train, y_train)
    print('omage: ', pmodel.coef_)
    print('b: ', pmodel.intercept_)
    # 绘制拟合函数
    length_points = np.linspace(4, 7, 10)
    width_points = -(pmodel.coef_[0][0] * length_points + pmodel.intercept_)/pmodel.coef_[0][1]
    plt.plot(length_points, width_points, label='fitting')
    plt.plot(train[:50, 0], train[:50, 1], 'bo', color='blue', label='0')
    plt.plot(train[50:100, 0], train[50:100, 1], 'bo', color='orange', label='1')
    plt.xlabel('sepal length')
    plt.ylabel('sepal width')
    plt.legend()