感知机的收敛性

1. 感知机基础

1.1 模型

感知机是最基础的机器学习模型之一，它的类别为：

分类（√）、回归、标注
概率软分类（√）、非概率硬分类
监督（√）、无监督、强化
线性（√）、非线性
判别（√）、生成

模型定义：
输入空间 $X\subseteq\R ^n$ ，输出空间 $Y=\left\{ +1,-1\right\}$ ，定义由输入空间到输出空间的函数映射为：
$f(x)=\mathrm{sign}(\omega \cdot x+b)$
该模型称为感知机。其中 $\omega,b$ 为感知机参数， $\omega \in \R ^n$ 称为权值， $b\in\R$ 称为偏置， $\mathrm{sign}$ 为符号函数，即：
$\mathrm{sign}(x)= \left\{ \begin{aligned} &+1, \quad x\geq 0 \\ &-1, \quad x<0 \end{aligned} \right.$

该模型本质上是在输入空间定义了一个分离超平面： $\omega\cdot x+b=0$ ， $\omega$ 为该超平面的法向量， $b$ 为该超平面的截距。该超平面将输入空间划分为两部分，位于两侧的点（输入数据）分别属于正负两类。
给定一个线性可分的训练样本集，通过寻找合适的 $\omega$ 和 $b$ 使得训练样本集的数据被正确划分到超平面的两侧，该过程即感知机模型的训练过程。
这里有一个前提“训练样本集线性可分”，即对于训练样本集： $T=\lbrace(x_1,y_1),(x_2,y_2,\cdots,(x_N,y_N)\rbrace$ ，其中， $x_i\in X=\R ^n,y_i\in Y=\lbrace+1,-1\rbrace,i=1,2,\cdots,N$ ，若存在某超平面 $S:\omega\cdot x+b=0$ ，使得 $\forall(x_i,y_i)\in T:y_i(\omega\cdot x_i+b)>0$ ，则称 $T$ 为线性可分数据集。

1.2 函数间隔与训练策略

为了寻找能正确划分训练样本集的超平面，需要定义损失函数，并将损失函数极小化。如何度量损失呢？如下图所示，有A、B、C三点，表示三个样本，都在分离超平面的正侧，距离分离超平面的距离依次减小。距离越远，预测为正类的确信度越大，反之则不那么确信。

样本距离分类超平面的距离与分类确信度.png

在超平面 $\omega\cdot x+b=0$ 确定的情况下， $|\omega\cdot x+b|$ 能够相对地表示点 $x$ 距离超平面的远近，而 $\omega\cdot x+b$ 的符号与类标记 $y$ 的符号是否一致能够表示分类是否正确。所以可以用 $y(\omega\cdot x+b)$ 来表示分类的正确性与确信度，这就是函数间隔（functional margin）的概念。
设 $M$ 为 $T$ 上被超平面 $S$ 误分类的所有点的集合，则 $\forall (x_i,y_i) \in M:y_i(\omega\cdot x_i+b)<0$
按照机器学习约定俗成的惯例，损失函数为正，对损失函数求极小值。因此，我们将感知机的损失函数定义为 $T$ 上所有被误分类的点到超平面 $S$ 的函数间隔的绝对值，即： $-\sum_{x_i\in M}{y_i(\omega\cdot x_i+b)}$
感知机的学习策略是在假设空间中选取使上式最小的分离超平面系数 $\omega$ 和 $b$ 。

1.3 学习算法

感知机的学习问题可转化为求解使损失函数最小的最优化问题，即求参数 $\omega,b$ ，使其为以下极小化问题的解。 $\min_{\omega,b}L(\omega,b)=-\sum_{x_i\in M}{y_i(\omega\cdot x_i+b)}$
其中，M为误分类点的集合。求解该问题可使用梯度下降算法。
损失函数 $L(\omega,b)$ 的梯度为：
$\begin{aligned} \Delta _{\omega} L(\omega,b) &=-\sum_{x_i\in M}{y_ix_i} \\ \Delta _{b} L(\omega,b) &=-\sum_{x_i\in M}{y_i} \end{aligned}$
如果样本集非常大，梯度下降算法每轮迭代都要计算全局梯度，这需要耗费非常大的计算资源，实际应用中通常使用随机梯度下降算法代替，即每次随机选取一个误分类点 $(x_i,y_i)$ ，对 $\omega,b$ 沿梯度负方向更新。
$\begin{aligned} \omega \leftarrow & \omega +\eta y_ix_i \\ b\leftarrow & b+\eta y_i \end{aligned}$
其中 $\eta(0<\eta\leq 1)$ 为步长，又叫做学习率。随机梯度的期望为全局梯度，因此其收敛性与梯度下降算法一致。通过不断迭代以上步骤，可以期待损失函数 $L(\omega,b)$ 不断减小，直到为0.
该算法的直观理解为：当一个实例点被误分类，调整 $\omega,b$ 的值，使分离超平面向该误分类点移动，减小该误分类点与超平面的距离，直至超平面越过该点，使其被正确分类。
该算法在训练开始时需要选取一个初始分类超平面 $(\omega_0,b_0)$ ，经过 $k$ 轮迭代后：
$\begin{aligned} \omega _k &= \omega _0+\eta \sum_{i=1}^{k-1}{y_ix_i} \\ b_k &=b_0+\eta \sum_{i=1}^{k-1}{y_i} \end{aligned}$
其中， $(x_i,y_i)$ 为第 $i$ 轮迭代时随机选取的误分类点。当 $(\omega_0,b_0)=0$ 时，第 $k$ 轮迭代时的超平面方程为：
$\begin{aligned} &\quad\omega _k x+b_k=0 \\ \Rightarrow &\quad \eta\sum_{i=1}^{k-1}{y_ix_i}x+\eta \sum_{i=1}^{k-1}{y_i}=0 \\ \Rightarrow &\quad \sum_{i=1}^{k-1}{y_ix_i}x+\sum_{i=1}^{k-1}{y_i}=0 \end{aligned} \tag{1}$
可以看出，学习速率 $\eta$ 可以被约去，说明当 $(\omega_0,b_0)=0$ 时，算法收敛速度与 $\eta$ 无关。下面证明感知机训练算法收敛性，证明过程可进一步验证该结论。

2. 算法收敛性证明

证明感知机训练算法是收敛的，即证明训练过程可在有限轮迭代内完成，即迭代次数 $k$ 存在一个上界。
为了便于叙述，将偏置 $b$ 并入权重向量 $\omega$ ，记作 $\hat{\omega}=(\omega^T,b)$ ，同时对输入向量 $x$ 进行扩充，记作 $\hat{x}=(x^T,1)$ ，显然 $\hat{\omega}\cdot \hat{x}=\omega\cdot x+b$ 。

Novikoff定理：
设训练数据集 $T=\lbrace(x_1,y_1),(x_2,y_2,\cdots,(x_N,y_N)\rbrace$ 是线性可分的，其中， $x_i\in X=\R ^n,y_i\in Y=\lbrace+1,-1\rbrace,i=1,2,\cdots,N$ ，令 $R=\max_{1\leq i\leq N}{||\hat{x}_i||}$ ，则感知机学习算法在训练数据集上的误分类次数 $k$ 满足不等式：
$k\leq\left(\frac{R}{\gamma}\right)^2\Vert\hat{\omega}_{opt}\Vert^2$
其中 $\hat{\omega}_{opt}$ 为该训练数据集的任一分离超平面的扩展系数向量。

证明：
训练数据集线性可分，则存在能将数据集完全正确分开的分离超平面，对任一满足要求的分离超平面 $\hat{\omega}_{opt}\cdot\hat{x}=0$ ，存在 $\gamma>0$ ，对所有 $i=1,2,\cdots,N$ ：
$y_i(\hat{\omega}_{opt}\cdot \hat{x}_i)\geq\gamma \tag{2}$
初始时， $\hat{\omega}_0=0$ ，随机选取某样本，若被误分类，则更新权重。令 $\hat{\omega}_{k-1}$ 是第 $k$ 次迭代时的扩充权重向量，此次迭代随机选择的第 $k$ 个误分类样本满足条件：
$y_i(\hat{\omega}_{k-1}\cdot\hat{x}_i)\leq 0 \tag{3}$
迭代时进行如下更新：
$\hat{\omega}_k=\hat{\omega}_{k-1}+\eta y_i\hat{x}_i \tag{4}$
联合(2)(4)式，有：
$\begin{aligned} \hat{\omega}_k\cdot\hat{\omega}_{opt} &=\hat{\omega}_{k-1}\cdot\hat{\omega}_{opt}+\eta y_i\hat{x}_i\cdot\hat{\omega}_{opt} \\ &\geq \hat{\omega}_{k-1}\cdot\hat{\omega}_{opt}+\eta \gamma \\ &\geq \hat{\omega}_{k-2}\cdot\hat{\omega}_{opt}+2\eta \gamma \\ &\cdots \\ &\geq k\eta \gamma \end{aligned} \tag{5}$
联合(3)(4)式，有：
$\begin{aligned} |Vert\hat{\omega}_k\Vert^2&=\Vert\hat{\omega}_{k-1}+\eta y_i\hat{x}_i \Vert^2 \\ &=\Vert\hat{\omega}_{k-1}\Vert^2+2\eta y_i\hat{\omega}_{k-1}\cdot\hat{x}_i+\eta^2\hat{x}_i^2 \\ &\leq\Vert\hat{\omega}_{k-1}\Vert^2+\eta^2\hat{x}_i^2 \\ &\leq\Vert\hat{\omega}_{k-1}\Vert^2+\eta^2R^2 \\ &\leq\Vert\hat{\omega}_{k-2}\Vert^2+2\eta^2R^2 \\ &\cdots \\ &\leq k\eta^2R^2 \end{aligned} \tag{6}$
联合(5)(6)式，有：
$\begin{aligned} &k\eta \gamma \leq\hat{\omega}_k\cdot\hat{\omega}_{opt}\leq\Vert\hat{\omega}_k\Vert\Vert\hat{\omega}_{opt}\Vert\leq\sqrt{k}\eta R\Vert\hat{\omega}_{opt}\Vert \\ \Rightarrow &k^2\gamma ^2\leq kR^2 \Vert\hat{\omega}_{opt}\Vert^2 \\ \Rightarrow &k\leq\left(\frac{R}{\gamma}\right)^2\Vert\hat{\omega}_{opt}\Vert^2 \end{aligned} \tag{7}$
定理得证。
从(7)式可知，迭代次数 $k$ 存在上界，这说明当训练数据集线性可分时，感知机学习算法是收敛的。
进一步地，通过调整 $\eta$ 可以改变 $\Vert\hat{\omega}_{opt}\Vert^2$ 的取值。算法经过 $k$ 次迭代结束后得到分离超平面 $\hat{\omega}_{opt}\hat{x}=0$ ，由(1)式可知， $\hat{\omega}_{opt}=\eta\sum_{i=1}^{k}{y_ix_i}$ ，令 $\eta=\frac{1}{\Vert\sum_{i=1}^{k}{y_ix_i}\Vert}$ ，则可使得 $\Vert\hat{\omega}_{opt}\Vert=1$ ，从而得到感知机迭代次数收敛上界的精简形式：
$k\leq\left(\frac{R}{\gamma}\right)^2$

3. 附录

from sklearn.datasets import make_blobs
from matplotlib import pyplot as plt
import numpy as np
import random

X,Y=make_blobs(n_samples=100,
               n_features=2,
               centers=2,
               cluster_std=2.5,
               random_state=1)
Y[Y==0]=-1

fig=plt.figure(figsize=(7,5))
ax=fig.add_subplot(111)
plt.show()
ax.scatter(X[:,0],X[:,1],c=Y, s=5, cmap='rainbow')

w=np.zeros(2)
b=0
eta=0.1
watcher=True
i=0
while(watcher):
    watcher=False
    for k in range(100):
        xk=X[k]
        yk=Y[k]
        if yk*(np.dot(w,xk)+b)>0:
            continue
        w=w+eta*yk*xk
        b=b+eta*yk
        i+=1
        print('第%d个误分类样本，w=%s,b=%s'%(i,w,b))
        watcher=True
        x1=np.arange(-7.5,1,0.01)
        x2=-(w[0]*x1+b)/w[1]
        ax.plot(x1,x2)
        plt.pause(0.01)

感知机学习算法.png

最后编辑于：2021.07.07 15:02:00

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 194,242评论 5赞 459
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 81,769评论 2赞 371
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 141,484评论 0赞 319
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 52,133评论 1赞 263
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 61,007评论 4赞 355
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 46,080评论 1赞 272
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 36,496评论 3赞 381
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 35,190评论 0赞 253
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 39,464评论 1赞 290
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 34,549评论 2赞 309
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 36,330评论 1赞 326
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 32,205评论 3赞 312
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 37,567评论 3赞 298
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 28,889评论 0赞 17
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 30,160评论 1赞 250
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 41,475评论 2赞 341
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 40,650评论 2赞 335