第 04 章 感知机学习规则

对应原书第 4 章。第 03 章靠画图为感知机设计权值，但输入维数一高就画不出来了。本章给出第一个真正的学习算法——Rosenblatt 的感知机学习规则，证明它在问题线性可分时一定在有限步内收敛，并指出单层感知机的根本局限。收敛证明中出现的"间隔"概念，是理解后来的支持向量机和过拟合问题的钥匙。

学习目标

读完本章，你应当能够：

1. 区分有监督学习、强化学习、无监督学习三类学习规则，说出各自的数据形式。
2. 用"权值向量指向输出为 1 的一侧、与边界正交"的几何事实，图解设计单神经元和多神经元感知机，或把设计问题写成不等式组。
3. 从三条直观规则推导出统一的感知机学习规则 \(\mathbf{W}^{new}=\mathbf{W}^{old}+\mathbf{e}\mathbf{p}^T\)，\(\mathbf{b}^{new}=\mathbf{b}^{old}+\mathbf{e}\)，并能手算若干次迭代。
4. 复述收敛定理的证明：长度平方的下界随 \(k^2\) 增长、上界随 \(k\) 增长，得出迭代次数上界 \(\Pi\|\mathbf{x}^*\|^2/\delta^2\)，并解释间隔 \(\delta\) 的含义。
5. 判断一个问题是否线性可分，说明 XOR 为何不能由单层感知机解决。
6. 理解感知机规则在不可分（含噪声）数据上的行为，知道量化实践中应改用哪些方法。

读前导读

这一章在解决什么问题

结论先说：本章给出第一个"让机器自己找权值"的算法，并证明它在数据能被一条直线（超平面）完全分开时一定会停下来。算法本身只有一行：分错了，就把这个样本加到权值上（或从权值里减掉）；分对了，就不动。

和你熟悉的回归对照：线性回归是一次性用 \((\mathbf{X}^T\mathbf{X})^{-1}\mathbf{X}^T\mathbf{y}\) 算出系数；感知机则是一个样本一个样本地"边看边改"，类似分析师每看到一次预测失误就调整一下打分卡的权重。它没有一个"误差平方和"之类的目标函数要最小化，只追求"把训练集全分对"。这带来两个后果，也是本章的重点：数据可分时它保证收敛，但找到的只是"某一个"可分的解，可能紧贴样本、不稳健；数据不可分时（金融数据几乎都是这样）它永远不收敛。第 10 章的 LMS 和逻辑回归会用连续的损失函数解决这个问题。

本章还有一个证明（4.4 节），这是本册第一个完整的数学证明。它不难，核心是一个"两头夹"的论证，值得完整读懂。

需要先想起来的数学

• 外积。列向量 \(\mathbf{e}\)（\(S\times1\)）乘行向量 \(\mathbf{p}^T\)（\(1\times R\)）得到 \(S\times R\) 矩阵，第 \((i,j)\) 元是 \(e_ip_j\)。例：\(\begin{bmatrix}1\\-1\end{bmatrix}[2\ \ 3]=\begin{bmatrix}2&3\\-2&-3\end{bmatrix}\)。注意与内积 \(\mathbf{p}^T\mathbf{p}\)（一个数）区分。见 第 00 册第 06 章 线性代数速成。
• 向量长度与长度平方的展开。\(\|\mathbf{x}\|^2=\mathbf{x}^T\mathbf{x}\)；\(\|\mathbf{x}+\mathbf{z}\|^2=\|\mathbf{x}\|^2+2\mathbf{x}^T\mathbf{z}+\|\mathbf{z}\|^2\)，和 \((a+b)^2=a^2+2ab+b^2\) 完全对应。这是收敛证明上界部分的唯一工具。
• Cauchy–Schwarz 不等式。\((\mathbf{x}^T\mathbf{y})^2\le\|\mathbf{x}\|^2\|\mathbf{y}\|^2\)，等号在两向量同向或反向时成立。金融上的熟悉形式是"相关系数的绝对值不超过 1"：\(|\mathrm{Cov}(X,Y)|\le\sigma_X\sigma_Y\)。见 第 00 册第 07 章 概率中的分析工具（常用不等式）。
• 反证法与"上下界夹逼"。要证明"\(k\) 不能无限大"，就假设 \(k\) 很大，推出"某个量既大于 \(ck^2\) 又小于 \(Ck\)"，而 \(k\) 足够大时 \(ck^2>Ck\)，矛盾。见 第 00 册第 08 章 读懂数学证明与符号。
• 记号 \(\max\) 与 \(\blacksquare\)。\(\max_i\|\mathbf{z}'(i)\|^2\) 是"所有 \(i\) 中最大的那个值"；\(\blacksquare\) 表示证明结束。

怎么读这一章

4.2 节（图解设计、不等式组）和 4.3 节（学习规则）是核心，建议跟着手算 4.3.4 和 4.3.5 两个例子。4.4 节收敛定理请完整读一遍，至少把"下界随 \(k^2\) 长、上界随 \(k\) 长"这条主线看懂；4.4.3 节的"间隔"解读很重要，它是理解过拟合和支持向量机的起点。4.1 节和 4.5 节可快速浏览，但要记住 XOR 的不等式反证。4.6 节量化实战的结论（不可分数据上要平均或改用逻辑回归）请务必读。

4.1 历史与学习规则的分类

4.1.1 从 McCulloch–Pitts 到 Rosenblatt

1943 年的 McCulloch–Pitts 神经元把输入加权求和、与阈值比较：大于等于阈值输出 1，否则输出 0。这样的网络可以计算任意算术或逻辑函数，但参数必须人工设计，没有训练方法。

1950 年代末 Rosenblatt 的关键贡献是感知机的学习规则，并且证明了：只要存在能解决问题的权值，规则一定收敛到一组正确的权值。学习过程简单而自动——给网络看正确行为的样例，网络从错误中学习，甚至可以从随机初值开始。

1969 年 Minsky 与 Papert 的《Perceptrons》严格地指出了感知机不能实现某些基本函数（例如 XOR）。这个局限直到 1980 年代多层感知机及其学习规则（第 11、12 章）出现才被克服。不过原书提醒：对于它能解决的那一类问题，感知机至今仍是快速可靠的网络，也是理解复杂网络的最好起点。

4.1.2 三类学习规则

学习规则（learning rule，也叫训练算法 training algorithm）是修改网络权值和偏置的程序，目的是让网络完成某项任务。分三大类：

1. 有监督学习（supervised learning）：给定一个训练集（training set）
   \[\{\mathbf{p}_1,\mathbf{t}_1\},\{\mathbf{p}_2,\mathbf{t}_2\},\dots,\{\mathbf{p}_Q,\mathbf{t}_Q\},\tag{4.1}\]
   \(\mathbf{p}_q\) 是输入，\(\mathbf{t}_q\) 是对应的正确输出，叫目标（target）。比较网络输出与目标，调整参数使输出向目标靠拢。感知机规则以及第 7–14 章的算法都属于这一类。
2. 强化学习（reinforcement learning，也叫 graded learning）：不告诉网络每个输入的正确输出，只给一个评分（grade），衡量网络在一段输入序列上的表现。原书写作时它远不如有监督学习常见，被认为最适合控制问题。（今天强化学习已是独立的大领域，在量化里用于最优执行和做市，但超出本书范围。）
3. 无监督学习（unsupervised learning）：只根据输入调整参数，没有目标输出。大多数这类算法做某种聚类，把输入归入有限个类别，用于向量量化等（第 15–19 章）。

量化里的对应关系很直接：用因子预测下期收益是有监督学习；直接优化策略的夏普比率、只在一段时间后得到一个"成绩"，接近强化学习；对股票按收益特征聚类、识别市场状态，是无监督学习。

4.2 感知机的结构与决策边界

一般的感知机网络是

（第 03 章用 hardlims，两者能力相同，见练习 6。）把 \(\mathbf{W}\) 的第 \(i\) 行记为列向量

则第 \(i\) 个输出是

当第 \(i\) 行与输入的内积 \(\ge -b_i\) 时输出 1，否则输出 0。每个神经元把输入空间分成两个区域。

4.2.1 单神经元：图解设计

两输入时 \(a=\mathrm{hardlim}(w_{1,1}p_1+w_{1,2}p_2+b)\)。决策边界是使净输入为零的输入集合：

例　\(w_{1,1}=1\)，\(w_{1,2}=1\)，\(b=-1\)，边界为 \(p_1+p_2-1=0\)。它与两轴的交点：\(p_1=0\) 时 \(p_2=-b/w_{1,2}=1\)；\(p_2=0\) 时 \(p_1=-b/w_{1,1}=1\)。检验点 \(\mathbf{p}=[2,0]^T\)：\(a=\mathrm{hardlim}(2-1)=1\)，所以边界右上方输出 1。

图解法的依据。边界上的所有点与 \({}_1\mathbf{w}\) 的内积都等于 \(-b\)，即在 \({}_1\mathbf{w}\) 上的投影相同，所以边界是一条与 \({}_1\mathbf{w}\) 正交的直线。输出为 1 的区域内积大于 \(-b\)，所以权值向量总是指向输出为 1 的区域。设计步骤是：先画一条分开两类的边界；再画一个与之正交、指向类 1 的权值向量（长度任意）；最后在边界上任取一点 \(\mathbf{p}\)，由 \(b=-{}_1\mathbf{w}^T\mathbf{p}\) 求偏置。

例：AND 门。训练集为

选一条位于两类"正中间"的边界，权值向量与之正交，取 \({}_1\mathbf{w}=[2,2]^T\)。边界上取一点 \(\mathbf{p}=[1.5,0]^T\)：\([2\ 2][1.5,0]^T+b=3+b=0\)，得 \(b=-3\)。检验 \(\mathbf{p}_2\)：\(a=\mathrm{hardlim}(2-3)=\mathrm{hardlim}(-1)=0=t_2\)。

4.2.2 把设计写成不等式组

图解法只适用于二维。原书 P4.2 给出了代数方法：目标为 1 要求净输入 \(\ge0\)，目标为 0 要求净输入 \(<0\)。对训练集 \(\{[0,2]^T,1\},\{[1,0]^T,1\},\{[0,-2]^T,0\},\{[2,0]^T,0\}\)：

\(w_{1,1}\) 只出现在 (ii)(iv)，\(w_{1,2}\) 只出现在 (i)(iii)，可以分别在 \((w_{1,1},b)\) 和 \((w_{1,2},b)\) 平面上画可行域再取交集。一个解是 \(\mathbf{W}=[-2\ \ 3]\)，\(b=3\)。

推导拆解：怎样从不等式凑出这个解？先由 (ii)(iv) 看 \(w_{1,1}\)：\(-b\le w_{1,1}<-b/2\)，要求区间非空即 \(-b<-b/2\)，得 \(b>0\)。再由 (i)(iii) 看 \(w_{1,2}\)：\(w_{1,2}\ge-b/2\) 且 \(w_{1,2}>b/2\)，合起来 \(w_{1,2}>b/2\)。取 \(b=3\)：\(w_{1,1}\in[-3,-1.5)\)，取 \(-2\)；\(w_{1,2}>1.5\)，取 \(3\)。代回检验：(i) \(6+3\ge0\)，(ii) \(-2+3\ge0\)，(iii) \(-6+3<0\)，(iv) \(-4+3<0\)，全部满足。可以看到可行解是一整块区域，任取其中一点都行。 原书指出：解不等式比解等式难，而且通常有无穷多解。感知机设计本质上是一个线性可行性问题——这和线性规划是同一类数学对象（第 04 册第 13、14 章）。

4.2.3 多神经元

每个神经元有自己的边界 \({}_i\mathbf{w}^T\mathbf{p}+b_i=0\)。单个神经元只能分两类；\(S\) 个神经元的输出向量每个元素取 0 或 1，最多能表示 \(2^S\) 个类别。

例（原书 P4.3）　四类问题：类 1 \(\{[1,1]^T,[1,2]^T\}\)，类 2 \(\{[2,-1]^T,[2,0]^T\}\)，类 3 \(\{[-1,2]^T,[-2,1]^T\}\)，类 4 \(\{[-1,-1]^T,[-2,-2]^T\}\)。四类至少要 2 个神经元。思路：第一条边界把四类分成两组（类 1、2 一组，类 3、4 一组），第二条边界再把每组一分为二。目标编码取类 1 \([0,0]^T\)、类 2 \([0,1]^T\)、类 3 \([1,0]^T\)、类 4 \([1,1]^T\)。选 \({}_1\mathbf{w}=[-3,-1]^T\)，\({}_2\mathbf{w}=[1,-2]^T\)，在各自边界上取点求得 \(b_1=1\)，\(b_2=0\)：

4.3 感知机学习规则

4.3.1 一个测试问题

训练集

为了能在平面上看清楚，先用无偏置的网络 \(a=\mathrm{hardlim}(\mathbf{W}\mathbf{p})\)，只有 \(w_{1,1},w_{1,2}\) 两个参数。无偏置时边界必须过原点；画图可以看出确实有无穷多条过原点的直线能把 \(\mathbf{p}_1\) 与 \(\mathbf{p}_2,\mathbf{p}_3\) 分开。我们希望学习规则找到一个指向"允许方向"之一的权值向量——只有方向重要，长度无关。

4.3.2 从三条直观规则出发

随机初始化 \({}_1\mathbf{w}^T=[1.0,\ -0.8]\)。

呈现 \(\mathbf{p}_1\)：\(a=\mathrm{hardlim}([1.0\ -0.8][1,2]^T)=\mathrm{hardlim}(-0.6)=0\)，而目标是 1，错分。我们需要让 \({}_1\mathbf{w}\) 更多地指向 \(\mathbf{p}_1\)。

• 方案一：直接令 \({}_1\mathbf{w}=\mathbf{p}_1\)。简单，但可能失败。原书给了一个反例：两个类 1 向量方向差别很大时，权值直接指向其中任一个都不能把两者都分对；每次错分就把权值设成该向量，会来回振荡，永不收敛。
• 方案二：把 \(\mathbf{p}_1\) 加到 \({}_1\mathbf{w}\) 上，让它的方向往 \(\mathbf{p}_1\) 偏一些。反复这样做，权值方向会渐近地趋向 \(\mathbf{p}_1\)。

于是得到第一条规则：若 \(t=1\) 且 \(a=0\)，则 \({}_1\mathbf{w}^{new}={}_1\mathbf{w}^{old}+\mathbf{p}\)（4.23）。更新后 \({}_1\mathbf{w}=[1.0,-0.8]^T+[1,2]^T=[2.0,1.2]^T\)。

呈现 \(\mathbf{p}_2\)：\(a=\mathrm{hardlim}([2.0\ 1.2][-1,2]^T)=\mathrm{hardlim}(0.4)=1\)，目标是 0。这次是类 0 被错分为 1，应该让权值远离该输入，把加法改为减法——第二条规则：若 \(t=0\) 且 \(a=1\)，则 \({}_1\mathbf{w}^{new}={}_1\mathbf{w}^{old}-\mathbf{p}\)（4.26）。更新得 \([2.0,1.2]^T-[-1,2]^T=[3.0,-0.8]^T\)。

呈现 \(\mathbf{p}_3\)：\(a=\mathrm{hardlim}([3.0\ -0.8][0,-1]^T)=\mathrm{hardlim}(0.8)=1\)，错分，用第二条规则：\([3.0,-0.8]^T-[0,-1]^T=[3.0,0.2]^T\)。此时三个向量全部分对。

第三条规则——"能用就别修"：若 \(t=a\)，则权值不变（4.30）。三条规则覆盖了输出与目标的全部组合。

4.3.3 统一的规则

定义感知机误差

三条规则变成：\(e=1\) 时加 \(\mathbf{p}\)，\(e=-1\) 时减 \(\mathbf{p}\)，\(e=0\) 时不变。\(\mathbf{p}\) 前面的符号恰好与 \(e\) 相同，所以合并为

偏置是输入恒为 1 的权值，把 \(\mathbf{p}\) 换成 1 即得

多神经元时每一行独立更新，\({}_i\mathbf{w}^{new}={}_i\mathbf{w}^{old}+e_i\mathbf{p}\)，\(b_i^{new}=b_i^{old}+e_i\)。写成矩阵就是感知机规则：

注意 \(\mathbf{e}\mathbf{p}^T\) 是一个 \(S\times R\) 的外积矩阵。第 07 章的 Hebb 规则 \(\mathbf{W}^{new}=\mathbf{W}^{old}+\mathbf{t}\mathbf{p}^T\)、第 10 章的 LMS 规则 \(\mathbf{W}^{new}=\mathbf{W}^{old}+2\alpha\mathbf{e}\mathbf{p}^T\) 都是这个外积形式，区别只在用什么乘以 \(\mathbf{p}^T\)。

白话解释：为什么"加上 \(\mathbf{p}\)"能让分类变对？看更新后同一个样本的净输入：\(({}_1\mathbf{w}+\mathbf{p})^T\mathbf{p}+(b+1)=({}_1\mathbf{w}^T\mathbf{p}+b)+(\|\mathbf{p}\|^2+1)\)。净输入严格增加了 \(\|\mathbf{p}\|^2+1>0\)，朝"输出 1"推了一把；减法则相反。一次未必推过边界，但方向永远是对的。这和回归的残差修正很像：误差 \(e=t-a\) 为正说明预测偏低，就沿着输入方向把系数往上调。区别是感知机的 \(e\) 只取 \(0,\pm1\)，只知道"错没错"，不知道"错了多少"；第 10 章 LMS 用连续的 \(e\)，调整幅度与误差大小成正比，这就是最小二乘的随机梯度下降。

4.3.4 例：苹果/橙子

用 hardlim，所以橙子的目标取 0 而不是 −1：

权值通常初始化为小随机数，这里取 \(\mathbf{W}=[0.5\ \ -1\ \ -0.5]\)，\(b=0.5\)。

• 第 1 次（\(\mathbf{p}_1\)）：\(a=\mathrm{hardlim}(0.5+1+0.5+0.5)=\mathrm{hardlim}(2.5)=1\)，\(e=-1\)。\(\mathbf{W}=[0.5\ -1\ -0.5]-[1\ -1\ -1]=[-0.5\ \ 0\ \ 0.5]\)，\(b=-0.5\)。
• 第 2 次（\(\mathbf{p}_2\)）：\(a=\mathrm{hardlim}(-0.5+0-0.5-0.5)=\mathrm{hardlim}(-1.5)=0\)，\(e=1\)。\(\mathbf{W}=[-0.5\ 0\ 0.5]+[1\ 1\ -1]=[0.5\ \ 1\ \ -0.5]\)，\(b=0.5\)。
• 第 3 次（\(\mathbf{p}_1\)）：\(a=\mathrm{hardlim}(0.5-1+0.5+0.5)=\mathrm{hardlim}(0.5)=1\)，\(e=-1\)。\(\mathbf{W}=[0.5\ 1\ -0.5]-[1\ -1\ -1]=[-0.5\ \ 2\ \ 0.5]\)，\(b=-0.5\)。

继续迭代会发现两个输入都已分对，算法收敛。最终边界与第 03 章人工设计的 \(\mathbf{W}=[0\ 1\ 0]\) 不同，但同样正确——感知机规则找到的是"某一个"可行解，而不是"最好的"可行解。

（注：第 2 次迭代的净输入，精读笔记依据的抽取文本显示为 −0.5，按计算应为 \(-1.5\)，结论 \(a=0\) 不变。）

4.3.5 例：原书 P4.4 的完整过程

训练集 \(\{[2,2]^T,0\},\{[1,-2]^T,1\},\{[-2,2]^T,0\},\{[-1,1]^T,1\}\)，初值 \(\mathbf{W}(0)=[0\ 0]\)，\(b(0)=0\)，按顺序循环：

再循环一遍全部正确，收敛于 \(\mathbf{W}=[-2\ -3]\)，\(b=1\)，边界 \(-2p_1-3p_2+1=0\)。注意这条边界恰好穿过训练点 \(\mathbf{p}_4\)（\(2-3+1=0\)）：因为 \(\mathrm{hardlim}(0)=1\) 且 \(t_4=1\)，按问题的定义算分对，但只要 \(\mathbf{p}_4\) 有一点点扰动就可能被分错。这是"只求在训练集上分对"的典型后果，下一节的间隔概念会解释它。

4.4 收敛定理

定理　若存在一组权值能把所有训练样本正确分类，则单神经元感知机学习规则在有限步内收敛。

4.4.1 记号

把权值和偏置合并、在输入后面补 1：

规则变为 \(\mathbf{x}^{new}=\mathbf{x}^{old}+e\,\mathbf{z}\)。只统计权值真正改变的迭代，记第 \(k\) 次改变为

（类 1 被错分时加 \(\mathbf{z}_q\)，类 0 被错分时加 \(-\mathbf{z}_q\)。）假设存在解 \(\mathbf{x}^*\)，且它把每个样本分对时留有余量 \(\delta>0\)：

白话解释：增广记号的作用是把偏置"藏"进权值。原来净输入是 \(\mathbf{w}^T\mathbf{p}+b\)，现在把 \(b\) 接在 \(\mathbf{w}\) 末尾、把 1 接在 \(\mathbf{p}\) 末尾，内积 \(\mathbf{x}^T\mathbf{z}=\mathbf{w}^T\mathbf{p}+b\cdot1\) 一模一样。好处是只需处理一个向量 \(\mathbf{x}\)，规则统一为 \(\mathbf{x}^{new}=\mathbf{x}^{old}+e\mathbf{z}\)。这和回归里在设计矩阵 \(\mathbf{X}\) 左边加一列 1 来估计截距是同一个技巧。

把类 0 样本"取负号"后统一记作 \(\mathbf{z}'\)，两类条件就合并为同一个式子 \(\mathbf{x}^{*T}\mathbf{z}'>\delta\)：类 1 原样，\(\mathbf{x}^{*T}\mathbf{z}_q>\delta\)；类 0 取负，\(\mathbf{x}^{*T}(-\mathbf{z}_q)>\delta\) 等价于 \(\mathbf{x}^{*T}\mathbf{z}_q<-\delta\)。余量 \(\delta\) 为什么一定存在？样本只有有限个，只要解 \(\mathbf{x}^*\) 让每个样本的净输入都严格不等于 0（若某个类 1 样本恰好落在边界上，把 \(b^*\) 稍微调大一点即可），取这些净输入绝对值中的最小值的一半当 \(\delta\) 就行。

4.4.2 证明：长度的上下界相互挤压

思路是给出 \(\|\mathbf{x}(k)\|^2\) 的一个随 \(k^2\) 增长的下界和一个随 \(k\) 增长的上界。\(k\) 足够大时下界会超过上界，矛盾，所以 \(k\) 有上限。

下界。不失一般性取 \(\mathbf{x}(0)=\mathbf{0}\)，则 \(\mathbf{x}(k)=\mathbf{z}'(0)+\cdots+\mathbf{z}'(k-1)\)。与解向量作内积：

每个 \(\mathbf{z}'(i)\) 都已按类别校正过符号，所以 \(\mathbf{x}^{*T}\mathbf{z}'(i)>\delta\)，于是 \(\mathbf{x}^{*T}\mathbf{x}(k)>k\delta\)。由 Cauchy–Schwarz 不等式 \((\mathbf{x}^{*T}\mathbf{x}(k))^2\le\|\mathbf{x}^*\|^2\|\mathbf{x}(k)\|^2\)，

直观地说：每次更新都让 \(\mathbf{x}\) 在"正确方向" \(\mathbf{x}^*\) 上前进至少 \(\delta\)。

推导拆解：下界一共三步。第一步，\(\mathbf{x}(0)=\mathbf{0}\)，每次更新加一个 \(\mathbf{z}'\)，所以 \(\mathbf{x}(k)\) 是前 \(k\) 个 \(\mathbf{z}'\) 之和。第二步，内积对加法可以拆开（线性），\(\mathbf{x}^{*T}\mathbf{x}(k)\) 等于 \(k\) 个 \(\mathbf{x}^{*T}\mathbf{z}'(i)\) 之和；每项都大于 \(\delta\)（这就是上一个讲解框里合并后的条件），所以总和大于 \(k\delta\)。第三步，用 Cauchy–Schwarz 把"在 \(\mathbf{x}^*\) 方向上的投影"转成"\(\mathbf{x}(k)\) 自身的长度"：投影大，长度必然大。式 (4.70) 是把 \((\mathbf{x}^{*T}\mathbf{x}(k))^2\le\|\mathbf{x}^*\|^2\|\mathbf{x}(k)\|^2\) 两边除以 \(\|\mathbf{x}^*\|^2\)，再代入 \(\mathbf{x}^{*T}\mathbf{x}(k)>k\delta>0\)（两边都为正，平方不改变大小顺序）。

上界。展开一次更新：

只有在上一步错分时才更新，错分意味着 \(\mathbf{x}^T(k-1)\mathbf{z}'(k-1)\le0\)，所以

递推，并令 \(\Pi=\max_i\|\mathbf{z}'(i)\|^2\)：

直观地说：每次更新只是"侧向"加一个长度有限的向量，长度平方最多线性增长。

合并：

权值只会改变有限次，算法在有限步内收敛。\(\blacksquare\)

推导拆解：上界那一步"错分意味着 \(\mathbf{x}^T(k-1)\mathbf{z}'(k-1)\le0\)"值得核对：类 1 被错分，说明当时 \(n=\mathbf{x}^T\mathbf{z}_q<0\)，而 \(\mathbf{z}'=\mathbf{z}_q\)；类 0 被错分，说明 \(n=\mathbf{x}^T\mathbf{z}_q\ge0\)，而 \(\mathbf{z}'=-\mathbf{z}_q\)，于是 \(\mathbf{x}^T\mathbf{z}'\le0\)。两种情况交叉项都不为正，丢掉它只会让右边变大，所以得到"\(\le\)"。

合并一步的代数：由 \(k\Pi>(k\delta)^2/\|\mathbf{x}^*\|^2=k^2\delta^2/\|\mathbf{x}^*\|^2\)，两边除以 \(k>0\) 得 \(\Pi>k\delta^2/\|\mathbf{x}^*\|^2\)，移项即式 (4.76)。数值感受：若 \(\Pi=3\)、\(\|\mathbf{x}^*\|=1\)、\(\delta=0.1\)，最多更新 300 次；\(\delta\) 缩小到 0.01，上界变成 30,000 次。

4.4.3 解读

• 间隔（margin）。若把 \(\mathbf{x}^*\) 归一化为单位长度，\(\delta\) 就是所有样本到解边界的（增广空间中的）最小距离。上界 \(\Pi/\delta^2\) 说明：类别越靠近边界、越难分，需要的迭代越多，并且是平方关系。
• 证明只用了三个假设：①解存在；②只在错分时更新；③输入长度有上界 \(\Pi\)。正因为证明如此一般，很多变体也能证明收敛，例如带学习率 \(\alpha\) 的规则 \(\mathbf{W}^{new}=\mathbf{W}^{old}+\alpha\mathbf{e}\mathbf{p}^T\)（练习 7）。
• 没有说的事。定理只保证"找到一个分对训练集的解"，不保证这个解离样本有多远。P4.4 的解恰好贴着一个训练点，就是例子。想要"离两类都尽量远"的解，需要显式最大化间隔——这就是支持向量机。

金融直觉：间隔可以类比信用分析里的"安全边际"。一个评分模型把所有违约企业和正常企业都分对了，但如果某家正常企业的得分只比临界值高 0.01，下季度财报稍有波动就会被误判。间隔 \(\delta\) 衡量的就是"最危险的那个样本离临界值有多远"。上界 \(\Pi\|\mathbf{x}^*\|^2/\delta^2\) 中，\(\Pi\) 是样本的最大"尺度"，\(\delta/\|\mathbf{x}^*\|\) 是几何间隔，二者之比的平方决定了学习难度——这和"信号相对于噪声的大小"在统计检验中决定所需样本量的道理相通。

4.5 局限性：线性可分

单神经元感知机的边界 \({}_1\mathbf{w}^T\mathbf{p}+b=0\) 是一个超平面（hyperplane），所以它只能分类线性可分的向量。AND 门（二维）和苹果/橙子（三维）是线性可分的。经典的反例是 XOR 门：

用不等式法很容易证明它不可解：四个条件分别是 \(b<0\)，\(w_2+b\ge0\)，\(w_1+b\ge0\)，\(w_1+w_2+b<0\)。把中间两式相加得 \(w_1+w_2+2b\ge0\)，即 \(w_1+w_2+b\ge-b>0\)，与第四式矛盾。

白话解释：XOR 的意思是"两个条件恰好满足一个时为真"。几何上，四个点在正方形的四角，同类的两点在对角线上，任何一条直线都没法让一条对角线的两端在一侧、另一条对角线的两端在另一侧。金融里这类关系并不罕见：设 \(p_1\) 表示"估值低"、\(p_2\) 表示"动量强"（各取 0/1），若历史上只有两者恰好一个成立时才有超额收益、两者同时成立或同时不成立都没有，这就是 XOR。这种交互作用，单个线性打分卡画不出来，必须加入乘积项 \(p_1p_2\)（回归里的交互项）或多层网络。

基本感知机连这样简单的问题都解决不了，这是 1970 年代研究降温的部分原因。Rosenblatt 研究过更复杂的网络，但没能把感知机规则推广过去。第 11 章的多层感知机能解决任意分类问题，用反向传播训练。原书在结语中强调：感知机的弱点不在学习规则，而在网络结构。

4.6 量化实战：方向分类、间隔与不可分数据

4.6.1 感知机在量化中的位置

以因子向量为输入、以"下期是否上涨"（0/1）为目标的线性分类器，本质上就是一个感知机。感知机规则逐样本更新，是在线学习（online learning）最简单的例子：每来一个新交易日的数据，就用它修正一次权值。但它有两个致命问题：

1. 金融数据几乎从不线性可分。同样的因子值，下期可能涨也可能跌，噪声远大于信号。收敛定理的前提不成立，感知机规则不会收敛，而是不停震荡；最后停在哪一组权值，取决于最后看到的几个样本。
2. 它不区分"刚好分对"和"稳稳分对"。只要在训练集上分对就停，得到的边界可能紧贴样本（P4.4），对噪声极其敏感。这正是量化中过拟合的直观来源。

实践中的补救有三类：对感知机的权值轨迹取平均（平均感知机，averaged perceptron）以抑制震荡；改用基于连续损失函数的方法——第 10 章的 LMS、逻辑回归（第 03 册第 13b 章）；或显式最大化间隔（支持向量机）。

4.6.2 代码

下面的代码做四件事：复现原书 4.3.4 节和 P4.4 的迭代；在可分数据上验证"间隔越小、更新越多"；最后在一个低信噪比的模拟方向预测问题上，对比感知机最后一步的权值、平均感知机和逻辑回归。

import numpy as np
from sklearn.linear_model import LogisticRegression

hardlim = lambda n: (n >= 0).astype(float)

def perceptron_train(P, T, W, b, max_epochs=100, verbose=False):
    """原书感知机规则：W += e p^T, b += e。P: R x Q, T: S x Q。返回 (W, b, 更新次数, 收敛轮数)"""
    W, b = W.astype(float).copy(), b.astype(float).copy()
    updates = 0
    for epoch in range(1, max_epochs + 1):
        changed = False
        for q in range(P.shape[1]):
            p, t = P[:, [q]], T[:, [q]]
            e = t - hardlim(W @ p + b)
            if np.any(e != 0):
                W += e @ p.T; b += e; updates += 1; changed = True
                if verbose:
                    print(f"  epoch{epoch} q={q+1}: e={e.ravel()}, W={W.ravel()}, b={b.ravel()}")
        if not changed:
            return W, b, updates, epoch
    return W, b, updates, None

# ---------- 原书 4.3 节：苹果/橙子（hardlim，橙子目标 0） ----------
P = np.array([[1, 1], [-1, 1], [-1, -1]], float)        # 列 = 橙子, 苹果
T = np.array([[0, 1]], float)
W, b, k, ep = perceptron_train(P, T, np.array([[0.5, -1, -0.5]]), np.array([[0.5]]), verbose=True)
print("apple/orange final W =", W.ravel(), "b =", b.ravel(), "updates =", k)

# ---------- 原书 P4.4 ----------
P = np.array([[2, 1, -2, -1], [2, -2, 2, 1]], float)
T = np.array([[0, 1, 0, 1]], float)
W, b, k, ep = perceptron_train(P, T, np.zeros((1, 2)), np.zeros((1, 1)))
print("P4.4 final W =", W.ravel(), "b =", b.ravel(), "updates =", k)

# ---------- 收敛界：间隔越小，更新次数越多 ----------
rng = np.random.default_rng(0)
w_true = np.array([1.0, -1.0, 0.5]); b_true = 0.2
x_star = np.r_[w_true, b_true] / np.linalg.norm(np.r_[w_true, b_true])   # 单位化的解向量
for gap in [0.5, 0.2, 0.05]:
    X = rng.uniform(-1, 1, (5000, 3))
    s = X @ w_true + b_true
    X = X[np.abs(s) / np.linalg.norm(np.r_[w_true, b_true]) > gap][:400]    # 去掉边界附近的点
    t = (X @ w_true + b_true >= 0).astype(float)
    Z = np.c_[X, np.ones(len(X))]                                            # 增广输入 z = [p; 1]
    delta = np.min(np.abs(Z @ x_star))
    Pi = np.max(np.sum(Z ** 2, axis=1))
    _, _, k, ep = perceptron_train(X.T, t[None, :], np.zeros((1, 3)), np.zeros((1, 1)), max_epochs=10000)
    print(f"gap>{gap:4.2f}: delta={delta:.3f}  updates={k:5d}  bound Pi/delta^2={Pi/delta**2:9.0f}  epochs={ep}")

# ---------- 量化：方向分类，金融数据几乎不可分 ----------
n_train, n_test, R = 1500, 1000, 5
beta = np.array([0.4, -0.3, 0.2, 0.0, 0.1])
F = rng.standard_normal((n_train + n_test, R))
ret = F @ beta * 0.01 + rng.standard_normal(n_train + n_test) * 0.02     # 信噪比很低
y = (ret > 0).astype(float)
Ftr, ytr, Fte, yte = F[:n_train], y[:n_train], F[n_train:], y[n_train:]

W, b = np.zeros((1, R)), np.zeros((1, 1))
W_sum, b_sum, cnt = np.zeros_like(W), np.zeros_like(b), 0
err_path = []
for epoch in range(20):
    for q in rng.permutation(n_train):
        p = Ftr[q][:, None]; e = ytr[q] - hardlim(W @ p + b)
        W += e @ p.T; b += e
        W_sum += W; b_sum += b; cnt += 1              # 平均感知机：累计每一步的权值
    err_path.append(np.mean(hardlim(Ftr @ W.T + b).ravel() != ytr))
print("train error by epoch (last W):", np.round(err_path[:10], 3))
acc = lambda Wt, bt: np.mean(hardlim(Fte @ Wt.T + bt).ravel() == yte)
print("test acc  last-W perceptron : %.3f" % acc(W, b))
print("test acc  averaged perceptron: %.3f" % acc(W_sum / cnt, b_sum / cnt))
lr = LogisticRegression().fit(Ftr, ytr)
print("test acc  logistic regression: %.3f" % lr.score(Fte, yte))
cos = lambda u, v: u @ v / np.linalg.norm(u) / np.linalg.norm(v)
print("cos(w, beta): last=%.3f  avg=%.3f  logit=%.3f"
      % (cos(W.ravel(), beta), cos((W_sum / cnt).ravel(), beta), cos(lr.coef_.ravel(), beta)))

运行输出：

  epoch1 q=1: e=[-1.], W=[-0.5  0.   0.5], b=[-0.5]
  epoch1 q=2: e=[1.], W=[ 0.5  1.  -0.5], b=[0.5]
  epoch2 q=1: e=[-1.], W=[-0.5  2.   0.5], b=[-0.5]
apple/orange final W = [-0.5  2.   0.5] b = [-0.5] updates = 3
P4.4 final W = [-2. -3.] b = [1.] updates = 3
gap>0.50: delta=0.500  updates=    3  bound Pi/delta^2=       15  epochs=2
gap>0.20: delta=0.202  updates=    6  bound Pi/delta^2=       87  epochs=2
gap>0.05: delta=0.051  updates=   51  bound Pi/delta^2=     1382  epochs=3
train error by epoch (last W): [0.493 0.495 0.525 0.508 0.495 0.584 0.519 0.513 0.531 0.551]
test acc  last-W perceptron : 0.547
test acc  averaged perceptron: 0.574
test acc  logistic regression: 0.574
cos(w, beta): last=0.576  avg=0.968  logit=0.969

解读：

• 前五行与原书 4.3.4 节、P4.4 的结果逐步一致（P4.4 的 3 次更新对应表中第 1、4、6 步）。
• 间隔实验：把边界附近的点剔除得越少（\(\delta\) 越小），需要的更新次数越多，从 3 次升到 51 次；理论上界 \(\Pi/\delta^2\)（这里 \(\|\mathbf{x}^*\|=1\)）从 15 升到 1382。实际次数远低于上界，上界是最坏情况，但"\(\delta\) 变小、代价按平方变大"的趋势很清楚。
• 方向分类实验：训练误差每轮都在 0.49–0.58 之间来回跳，没有任何收敛迹象——这就是不可分数据上的感知机。最后一步的权值与真实因子方向 \(\beta\) 的余弦只有 0.58，测试准确率 54.7%；把整条权值轨迹取平均后，余弦升到 0.97，测试准确率 57.4%，与逻辑回归持平。教训是：在噪声主导的金融数据上，单步的在线更新结果不可信，必须平滑（平均）或改用有明确损失函数的方法。第 07 章的"带衰减的 Hebb 规则"和第 10 章的 LMS 都会再碰到"在线更新 + 平滑"的问题。
• 57% 的方向准确率看起来不高，但在日频截面选股里已经是很强的信号；本例的信噪比是人为设定的，真实数据通常更低。

本章小结

学习规则分有监督、强化、无监督三类。感知机是有监督的：它的每个神经元画一个超平面，边界与权值向量正交、权值向量指向输出 1 的一侧、偏置负责平移，\(S\) 个神经元最多分 \(2^S\) 类。感知机规则 \(\mathbf{W}^{new}=\mathbf{W}^{old}+\mathbf{e}\mathbf{p}^T\)、\(\mathbf{b}^{new}=\mathbf{b}^{old}+\mathbf{e}\) 从"错分为 0 就加、错分为 1 就减、分对不动"三条直观规则统一而来。收敛定理用长度平方的上下界相互挤压，证明线性可分时更新次数不超过 \(\Pi\|\mathbf{x}^*\|^2/\delta^2\)，间隔越小越难学。单层感知机的根本局限是只能处理线性可分问题（XOR 不行），而且它只找"某一个"可行解，可能紧贴样本、不稳健；在不可分的金融数据上它不会收敛。

练习

基础

1. 判断五个点 \([-1,1]^T,[0,0]^T,[1,-1]^T\)（目标 1）与 \([1,0]^T,[0,1]^T\)（目标 0）能否由单神经元感知机分开。（原书 E4.1） 提示：三个类 1 点都在直线 \(p_1+p_2=0\) 上，两个类 0 点在 \(p_1+p_2=1\) 上；可取边界 \(p_1+p_2=0.5\)，即 \(\mathbf{W}=[-1\ -1]\)，\(b=0.5\)。
2. 用感知机规则从 \(\mathbf{W}(0)=[0\ 0]\)，\(b(0)=0\) 出发，求解 \(\{[-1,1]^T,1\},\{[-1,-1]^T,1\},\{[0,0]^T,0\},\{[1,0]^T,0\}\)，并用所得网络分类新点 \([-2,0]^T,[1,1]^T,[0,1]^T,[-1,-2]^T\)。哪些新点的分类与具体解无关？（原书 E4.2、E4.4） 提示：\([-2,0]^T\) 落在类 1 点的凸包外侧"更远"处，任何可行解都把它分到类 1；\([0,1]^T\) 这类点的分类依赖于具体解——训练集没有约束到的区域，不同的可行解会给出不同答案。这是"泛化"问题的雏形。
3. 用不等式组证明 \(\{[-1,1]^T,1\},\{[-1,-1]^T,0\},\{[1,-1]^T,1\},\{[1,1]^T,0\}\) 对两输入单神经元感知机不可解。（原书 E4.5） 提示：四个不等式为 \(-w_1+w_2+b\ge0\)，\(-w_1-w_2+b<0\)，\(w_1-w_2+b\ge0\)，\(w_1+w_2+b<0\)。第 1、3 式相加得 \(b\ge0\)，第 2、4 式相加得 \(b<0\)，矛盾。
4. 手算原书 P4.5：用感知机规则训练 4.2.3 节的四类问题，初值 \(\mathbf{W}(0)=\mathbf{I}\)，\(\mathbf{b}(0)=[1,1]^T\)，按 \(\mathbf{p}_1,\dots,\mathbf{p}_8\) 顺序循环。 答案要点：第 1 次更新后 \(\mathbf{W}=\begin{bmatrix}0&-1\\-1&0\end{bmatrix}\)，\(\mathbf{b}=[0,0]^T\)；第 3 次后 \(\mathbf{W}=\begin{bmatrix}-2&0\\1&-1\end{bmatrix}\)，\(\mathbf{b}=[-1,1]^T\)；第 9 次后 \(\mathbf{W}=\begin{bmatrix}-2&0\\0&-2\end{bmatrix}\)，\(\mathbf{b}=[-1,0]^T\)，此后收敛。
5. 训练集 \(\{[-1,-1]^T,0\},\{[0,0]^T,0\},\{[-1,1]^T,1\}\)，初值 \(\mathbf{W}(0)=[1\ 0]\)，\(b(0)=0.5\)。训练一遍并画出初始与最终边界。任意初值下感知机规则是否总能学会这个问题？（原书 E4.8） 提示：问题线性可分，收敛定理对任意初值都成立（证明中取 \(\mathbf{x}(0)=\mathbf{0}\) 只是为了简化，非零初值只改变常数项）。

进阶

6. hardlims（目标 ±1）与 hardlim（目标 0/1）的感知机：写出两种目标之间的映射；相同初值、相同输入下两者的权值更新有何差别？怎样初始化能让两者的训练过程完全一致？（原书 E4.10） 答案要点：\(t^{s}=2t-1\)。hardlims 的误差取值为 \(\{0,\pm2\}\)，更新量是 hardlim 的两倍；把 hardlims 网络的初值取为 hardlim 网络初值的 2 倍，两者的权值轨迹始终差一个因子 2，而 \(\mathrm{hardlims}(2n)\) 与 \(\mathrm{hardlim}(n)\) 给出相同的判决。
7. 证明带学习率的变体 \(\mathbf{W}^{new}=\mathbf{W}^{old}+\alpha\mathbf{e}\mathbf{p}^T\)，\(\mathbf{b}^{new}=\mathbf{b}^{old}+\alpha\mathbf{e}\) 在线性可分时也收敛。是否需要限制 \(\alpha\) 的大小？（原书 E4.13） 答案要点：从零初值出发时，\(\alpha\) 只是把整个权值轨迹放大 \(\alpha\) 倍，判决不变，更新序列完全相同；也可直接在证明中把 \(\mathbf{z}'\) 换成 \(\alpha\mathbf{z}'\)，下界变为 \((k\alpha\delta)^2/\|\mathbf{x}^*\|^2\)，上界变为 \(k\alpha^2\Pi\)，\(\alpha\) 约掉。故对任意 \(\alpha>0\) 都收敛。
8. 玩具兔子与熊：特征为重量与耳长，兔子 \([1,4],[1,5],[2,4],[2,5]\)（目标 0），熊 \([3,1],[3,2],[4,1],[4,2]\)（目标 1）。用本章代码训练并测试。再设计一种添加辅助训练向量的方法，保证解的边界不会穿过原始样本。（原书 E4.11） 提示：在每个原始样本周围加一圈小扰动的同类样本（例如 \(\pm0.1\) 的方形邻域四角），边界就被迫离开原始样本至少这个距离——这是"人为制造间隔"，也是数据增强的雏形。
9. 把 4.2.3 节四类问题中的一个类 2 向量改为 \([2,2]^T\)，问题是否仍线性可分？再改为 \([2,1.5]^T\) 呢？分别用代码训练，观察不可分时的表现。（原书 E4.12） 提示：观察每轮是否仍有更新、权值是否周期性地回到同一组值。
10. 量化思考：在 4.6.2 节的方向分类实验中，把噪声标准差从 0.02 降到 0.002，平均感知机与最后一步权值的差距会变大还是变小？为什么？ 提示：噪声越小，数据越接近线性可分，最后一步的权值越稳定，平均的好处越小。

原书推荐习题：P4.4、P4.5（手算感知机规则）、E4.5（不等式证明不可分）、E4.10（hardlim 与 hardlims 等价）、E4.11(iii)（提高边界稳健性）、E4.13（带学习率的收敛性）。

原书对照

原书配套演示：nnd4db（决策边界）、nnd4pr（感知机规则）。