统计学习方法-Perceptron

导读

感知机是二分类的线性分类模型，输入是实例的特征向量（每个属性），输出是实例的类别。感知机对应于输入空间中将实例划分为正负两类的分离超平面，属于判别模型。

• 目的：找出将训练数据进行线性划分的分离超平面
• 导入基于误分类的损失函数，利用梯度下降法对损失函数进行极小化，求出最小值
• 有原始形式和对偶形式两种
• 感知机是种线性分类模型，属于判别模型。

感知机原理剖析及实现

定义

表示实例的类别，其中输入到输出的函数表示如下：

称为感知机

• w，b称为感知机模型参数；w称为权值或者权值向量；b\in R称为偏置bias。w\bullet x表示二者的内机，sign表示符号函数：

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

感知机的几何解释为线性方程：

这条直线就是最好的那条线，最优解。特征空间

栗子（图2.1）：

策略

给定一个数据集

其中

• 到距离是，

其中||w||表示w的范数，即

对于误分类的点，总有如下结论：

。因此，误分类的点到超平面的距离：，假设超平

面中的所有误分类的集合M，所有误分类的点到S的总距离为：

不考虑的损失函数为：

• M是误分类点的集合
• 损失函数就是感知机学习的经验风险函数
• 梯度只是向量，代表下降的方向
• 通过学习率来控制下降的大小
• 如果没有误分类点，损失函数是0
• 误分类点越少，总距离越小，损失函数越小
• L是参数(w,b)的连续可导函数

算法

原始形式

算法思想

感知机学习算法的最优化问题就是求解损失函数的最小值，即：

。感知机的算法是误分类驱动的，具体采用的是随机梯度下降法(stochastic gradient descent)，大致过程如下：

• 选取任意的超平面w_0,b_0
• 利用梯度下降方法去不断地极小化目标损失函数L(w, b)
• 在不断极小化的过程中，不是一次性使用M中所有误分类点进行梯度下降，而是一次随机选取一个误分类点进行梯度下降。
• 损失函数L(w, b)的梯度由如下的式子决定：

每次随机选取一个误分类点进行更新：

其中

算法描述

输入：训练数据集

，其中

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

• 选取初值w_0,b_0，一般是0
• 在训练集中选取数据(x_i,y_i)
• 的更新：

• 转到第二步，直至训练集中没有误分类点停止

直观解释：当有一个误分类点在超平面的错误一侧，调整w,b的值，使得分离超平面向着该误分类点的一侧移动，从而较小误分类点和超平面的距离，直至超平面越过该点，使其被正确地分类

栗子（2.1）：

对偶形式

算法思想

对偶形式的基本思想是将w,b表示为实例x_i和输出类别y_i的线性组合的形式，通过求解系数从而求得w和b。

的初值是都是0，对于误分类点通过：

分别表示为：​

在上面两个迭代式子中，\alpha_i \geq{0}, i=1,2,…N；当\eta=1时，表示第i个实例点由于误分类而进行更新的次数。

算法描述

输入：给定线性可分的训练数据集T={(x_1,y_1),(x_2,y_2),…,(x_N,y_N)}，其中x_i\in X=R^n,y_i \in Y={-1, +1}, i=1,2,…,N；学习率0 < \eta \leq 1

；感知机模型

其中，

1.给定初值\alpha \gets 0,b\gets0

2.在训练数据集中选取数据(x_i,y_i)

3.如果

进行的更新：

4.转到第二步，直至训练集中没有误分类点停止

对偶形式中训练实例仅仅是以内积的形式出现，著名的Gram矩阵

栗子（2.2）：

算法收敛性

，则

具体证明过程见书本。

代码实现

import numpy as np
import matplotlib.pyplot as plt
from sklearn.linear_model import Perceptron

x1 = np.array([3, 4, 1])
x2 = np.array([3, 3, 1])
y = np.array([1, 1, -1])
plt.scatter(x1[0:2], x2[0:2], c='g', label='1')
plt.scatter(x1[2:3], x2[2:3], c='r', marker='x', label='-1')

plt.title("Preceptron Method", fontsize=14)
plt.xlabel("the data x1", fontsize=14)
plt.ylabel("the data x2", fontsize=14)
plt.legend()
plt.axis([0 ,6, 0, 6])

# 初始化系数
i=0
w1=0
w2=0
b=0

while i<3:
    if y[i] * (w1 * x1[i] + w2 * x2[i] + b) <= 0:
        w1 = w1 + y[i] * x1[i]
        w2 = w2 + y[i] * x2[i]
        b += y[i]
        i = 0
    else:
        i += 1

x_new = np.array([[0], [6]])
y_new = (-b - w1 * x_new) / w2
y_new

array([[ 3.],
       [-3.]])