Lesson 62: 感知机二分类器

练习任务

难度：中

实现一个单层感知机 (Perceptron)，学习 AND 逻辑函数的线性决策边界，然后演示 XOR 逻辑函数的线性不可分——感知机永不收敛。你需要完成 7 个核心任务：

序号	函数	任务描述	难度
TODO 1	`dot(w, b, x)`	计算点积 w·x + b	★☆☆
TODO 2	`sign(val)`	符号函数，返回 +1 或 -1	★☆☆
TODO 3	`predict(w, b, x)`	预测标签 sign(dot(w, b, x))	★☆☆
TODO 4	`train_one_epoch(w, &b, X, Y)`	遍历数据集，误分类时更新权重/偏置	★★★
TODO 5	`print_weights(w, b)`	按格式打印权重和偏置	★☆☆
TODO 6	AND 训练主流程	串联训练循环，按格式输出全部结果	★★☆
TODO 7	XOR 训练段	演示线性不可分，紧凑输出 100 轮	★★☆

固定参数（不可修改）：

AND 数据集: (0,0)→-1  (0,1)→-1  (1,0)→-1  (1,1)→+1
XOR 数据集: (0,0)→-1  (0,1)→+1  (1,0)→+1  (1,1)→-1
学习率:     α = 0.1
初始值:     w = {0, 0}, b = 0
最大轮数:   MAX_EPOCHS = 100 (两个数据集均使用)

本课的标准输出可通过 make test 比对验证（./perceptron | diff - expected_output.txt）。

提示：感知机的核心更新规则——w ← w + α·y·x、b ← b + α·y——仅对误分类的样本生效。训练过程中权重逐步向正确方向调整，决策边界随之旋转。AND 约 4 轮收敛，XOR 100 轮永不收敛——这是感知机最根本的局限，也直接导致了 1969 年第一次 AI 寒冬。

核心知识点

感知机 = 线性二分类器 — 决策函数 ŷ = sign(w·x + b)，用超平面将输入空间分为两个半空间
线性可分性 — 存在超平面完全分开正负类的性质。AND、OR 线性可分；XOR 线性不可分——任何直线都无法分开
感知机学习规则 — w ← w + α·y·x，b ← b + α·y，几何含义是：当预测错误时，将权重向量向正确方向"推"
梯度下降视角 — 更新规则等价于对感知机损失函数 L = Σ max(0, -y(w·x+b)) 做 SGD，梯度为 -y·x
感知机收敛定理 (Novikoff 1962) — 若数据线性可分，算法在有限步内收敛；若不可分，权重无限振荡
sign(0) 与浮点误差 — IEEE 754 中 -0.0 >= 0.0 == true，浮点舍入误差可能在边界上"帮助"或"阻碍"收敛
决策边界不唯一 — 感知机找到的分离超平面依赖于初始权重和样本遍历顺序，SVM 通过最大化间隔挑选唯一解
XOR → 第一次 AI 寒冬 — 1969 年 Minsky & Papert 以 XOR 不可分"论据批判感知机，导致神经网络研究陷入十年低谷

代码框架

62_perceptron_classifier.c

#include <stdio.h>

#define N_POINTS   4
#define N_FEATURES 2

/* ─── 数据集 (已提供，不可修改) ─── */
static const double X_AND[N_POINTS][N_FEATURES] =
    {{0.0,0.0},{0.0,1.0},{1.0,0.0},{1.0,1.0}};
static const double Y_AND[N_POINTS] = {-1.0, -1.0, -1.0, 1.0};

static const double X_XOR[N_POINTS][N_FEATURES] =
    {{0.0,0.0},{0.0,1.0},{1.0,0.0},{1.0,1.0}};
static const double Y_XOR[N_POINTS] = {-1.0, 1.0, 1.0, -1.0};

static const double ALPHA = 0.1;
static const int MAX_EPOCHS = 100;

/* TODO 1: 实现点积 dot(w, b, x) = w0*x0 + w1*x1 + b */
static double dot(const double w[], double b, const double x[]) {
#error TODO 1: Compute dot product w0*x0 + w1*x1 + b.
}

/* TODO 2: 实现符号函数 sign(val) — val>=0 返回 +1, 否则 -1 */
static double sign(double val) {
#error TODO 2: Return +1.0 if val >= 0.0, else -1.0.
}

/* TODO 3: 实现预测函数 predict(w, b, x) = sign(dot(w, b, x)) */
static double predict(const double w[], double b, const double x[]) {
#error TODO 3: Return sign(dot(w, b, x)). One line.
}

/* TODO 4: 单轮训练 — 遍历 N_POINTS，误分类时更新 w 和 *b
 *   w[j] += ALPHA * Y_data[i] * X_data[i][j]
 *   *b   += ALPHA * Y_data[i]
 * 返回本轮误分类次数 */
static int train_one_epoch(double w[], double *b,
                           const double X_data[][N_FEATURES],
                           const double Y_data[]) {
#error TODO 4: Iterate, predict, compare, update on mismatch.
}

/* TODO 5: 格式化打印 "w = {%.4f, %.4f}, b = %.4f" */
static void print_weights(const double w[], double b) {
#error TODO 5: printf with 4 decimal places, space after comma.
}

int main(void) {
    /* ──────── TODO 6: AND 训练主流程 ────────
     * 标题 → 数据集 → 突触权重 → 训练循环 (最多 100 轮)
     * → 每轮打印 Before/After + 4 点分类 (✓/✗)
     * → mistakes == 0 → break → 决策边界 → 收敛信息
     *
     * ──────── TODO 7: XOR 演示 ────────
     * 重置 w={0,0}, b=0 → 标题 → 训练 (紧凑输出)
     * → 前 5 轮完整 → 之后每 10 轮快照 → 中间用 "... oscillating ..." 摘要
     * → 100 轮后打印"未收敛"警告 → 决策边界 → "Did not converge"
     */
#error TODO 6 & 7: Implement AND training + XOR demo.
}

阅读骨架后，尝试自己填充 7 个 TODO 标记的部分。核心挑战在于：train_one_epoch 中对 b 的指针解引用（*b += ... 而非 b += ...）；AND 收敛时的 epoch 计数 off-by-one；XOR 段的紧凑输出格式——前 5 轮完整，之后每 10 轮一帧，中间用 ... (epochs M–N: oscillating, 2 mistakes each) ... 跳过。

TIP

先不看参考解答。用纸笔追踪 AND 训练的前 3 轮——记录每轮 w 和 b 的变化，理解决策边界从"无"到"有"的旋转过程。重点关注 epoch 3 结束后 w={0.2,0.1}, b=-0.2 为什么已经能正确分类所有点。

深度讲解

1. 感知机的数学模型——最简单的神经网络

感知机 (Perceptron) 是 Frank Rosenblatt 于 1957 年提出的第一个可学习的人工神经网络模型。它是一个线性二分类器——用一个超平面将输入空间分成两个半空间，，每个半空间对应一个类别。

决策函数:  ŷ = sign(w·x + b)

其中:
  x ∈ R²   — 输入特征向量 (本题 2 维)
  w ∈ R²   — 权重向量 (决定超平面方向)
  b ∈ R    — 偏置 (决定超平面到原点的距离)
  sign(·)  — 符号函数，输出 +1 或 -1

计算图：

  ┌────┐
  │x0 │──→ w0 ──┐
  └───┘         │    ┌──────┐     ┌──────┐
                ├───→│ Σ + b│────→│ sign │──→ ŷ ∈ {+1, -1}
  ┌───┐         │    └──────┘     └──────┘
  │x1 │──→ w1 ──┘       ↑
  └───┘                  b (偏置)

对于 2D 数据，超平面退化为一条直线：w₀x₀ + w₁x₁ + b = 0，改写为 x₁ = -(w₀/w₁)x₀ - b/w₁。

感知机的设计灵感来自生物神经元：树突 (输入) → 突触权重 (w) → 细胞体 (Σ + 阈值) → 轴突 (sign 激活)。总输入超过阈值 (-b) 时，神经经元"发放"(输出 +1)，否则保持静默 (输出 -1)。

感知机算法伪代码：

算法: Perceptron Training (在线学习)
输入: D = {(x_i, y_i)}, α, MAX_EPOCHS
输出: w, b, converged

1. w ← 0, b ← 0
2. for epoch = 1 to MAX_EPOCHS:
3.     mistakes ← 0
4.     for each (x_i, y_i) in D:
5.         ŷ 测标签 sign(w·x_i + b)
6.         if ŷ ≠ y_i:
7.             w ← w + α · y_i · x_i
8.             b ← b + α · y_i
9.             mistakes ← mistakes + 1
10.    if mistakes == 0:
11.        converged ← true; break
12. return w, b, converged

这就是感知机算法的全部——一个简单的双层循环。外层控制训练轮数，内层遍历每个样本。误分类时立即更新权重，无误分类时提前停止。

2. 线性可分性——感知机能力边界

定义：数据集是线性可分的，当且仅当存在一个超平面将正负样本完全分开。

AND 的 4 个数据点在 2D 平面上:

  x₁ ↑
     │
  1  │  ●(-1)              ★(+1)      ● = 负类, ★ = 正类
     │
     │        ← 决策边界 (可以画一条直线分开!)
  0  │  ●(-1)              ●(-1)
     │
     └────────────────────────────→ x₀
        0                    1

  AND 是线性可分的 ✓

反例——XOR (异或) 的线性不可分性：

  x₁ ↑
     │
  1  │  ●(-1)              ★(+1)
     │
     │        ← 任何一条直线都无法同时分开!
  0  │  ★(+1)              ●(-1)
     │
     └────────────────────────────→ x₀
        0                    1

  XOR 线性不可分 ✗

逻辑函数	数据点 (x₀,x₁)→y	线性可分	感知机可学习？
AND	(0,0)→-1, (0,1)→-1, (1,0)→-1, (1,1)→+1	是	是
OR	(0,0)→-1, (0,1)→+1, (1,0)→+1, (1,1)→+1	是	是
XOR	(0,0)→-1, (0,1)→+1, (1,0)→+1, (1,1)→-1	否	否 (振荡)

XOR 的不可分性在 1969 年被 Minsky & Papert 在《Perceptrons》一书中用作批判感知机的核心论据，触发了第一次 AI 寒冬。直到多层感知机 (MLP) 和反向传播算法的出现才解决了 XOR 才得以解决。

3. 感知机学习规则——几何直觉与梯度视角

感知机采用在线学习策略策略——每遇到一个误分类样本就立即更新。

核心更新公式（对误分类点 x，真实标签 y ∈ {+1, -1}）：

  w_new = w_old + α · y · x
  b_new = b_old + α · y

几何解释——两种情况：

情况 A: y = +1，但预测为 -1 (漏报)
  → w ← w + α·x  (向 x 方向旋转，使 w·x 增大)
  → b ← b + α    (向正方向推)

情况 B: y = -1，但预测为 +1 (误报)
  → w ← w - α·x  (向 -x 方向旋转，使 w·x 减小)
  → b ← b - α    (向负方向推)

从梯度下降视角理解：

感知机损失函数 (Perceptron Loss):

  L(w, b) = Σ_i max(0, -y_i · (w·x_i + b))

对误分类点 (y_i·(w·x_i+b) ≤ 0):

  ∂L/∂w = -y_i · x_i
  ∂L/∂b = -y_i

  w ← w - α(-y_i·x_i) = w + α·y_i·x_i  ✓
  b ← b - α(-y_i) = b + α·y_i           ✓

这就是感知机学习规则。

IMPORTANT

更新时必须使 x，真实标签 y 而非预测值 ŷ。用预测值会"奖励"错误预测，导致权重发散。train_one_epoch 中 b 参数是 double*，更新时写 *b += ... 而非 b += ...——后者修改的是局部指针变量本身而非原值。

4. AND 训练全流程追踪

以 α=0.1, w₀={0,0}, b₀=0 为例，完整追踪 AND 训练过程：

═══════════════════════════════════════════════════
Epoch 1: w={0, 0}, b=0
═══════════════════════════════════════════════════
  (0,0,-1): dot=0 → sign(0)=+1 ≠ -1 → w=(0,0), b=-0.1
  (1,0,-1): dot=-0.1 → sign=-1 = y ✓ (无更新)
  注意: (0,1) 和 (1,1) 依次触发更新
  结束后: w={0.1, 0.1}, b=0, mistakes=2

═══════════════════════════════════════════════════
Epoch 2: w={0.1, 0.1}, b=0
═══════════════════════════════════════════════════
  (0,0,-1): dot=0 → sign=+1 ≠ -1 → w={0.1,0.1}, b=-0.1
  (0,1,-1): dot=0.1-0.1=0 → sign=+1 ≠ -1 → w={0.1,0}, b=-0.2
  (1,0,-1): dot=0.1-0.2=-0.1 → sign=-1 = y ✓
  (1,1,+1): dot=0.1-0.2=-0.1 → sign=-1 ≠ +1 → w={0.2,0.1}, b=-0.1
  结束后: w={0.2, 0.1}, b=-0.1, mistakes=3

═══════════════════════════════════════════════════
Epoch 3: w={0.2, 0.1}, b=-0.1
═══════════════════════════════════════════════════
  (0,0,-1): dot=-0.1 → sign=-1 = y ✓
  (0,1,-1): dot=0.1-0.1=0 → sign=+1 ≠ -1 → w={0.2,0}, b=-0.2
  (1,0,-1): dot=0.2-0.2=0 → sign=+1 ≠ -1 → w={0.1,0}, b=-0.3
  (1,1,+1): dot=0.1-0.3=-0.2 → sign=-1 ≠ +1 → w={0.2,0.1}, b=-0.2
  结束后: w={0.2, 0.1}, b=-0.2, mistakes=3

═══════════════════════════════════════════════════════
Epoch 4: w={0.2, 0.1}, b=-0.2
═══════════════════════════════════════════════════
  (0,0,-1): dot=-0.2 → sign=-1 = y ✓
  (0,1,-1): dot=-0.1 → sign=-1 = y ✓
  (1,0,-1): dot=0.2-0.2≈-ε → sign=-1 = y ✓   (*)
  (1,1,+1): dot=0.1 → sign=+1 = y ✓
  mistakes=0 → 收敛!
═══════════════════════════════════════════════════

(*) 关键细节：0.2 - 0.2 在 IEEE 754 双精度浮点数中可能算出一个极小的负数（如 -2.78×10⁻¹⁷），使得 sign 返回 -1 而非 +1。这一浮点舍入误差恰好避免了 (1,0) 的误分类——某种意义上"帮助"了收敛。这是数值计算中理论与实践微妙差异的经典案例。

收敛后的决策边界：0.2·x₀ + 0.1·x₁ - 0.2 = 0，即 x₁ = -2x₀ + 2。

5. XOR——永不收敛的振荡

XOR 数据集 {(0,0)→-1, (0,1)→+1, (1,0)→+1, (1,1)→-1} 的追踪结果：

Epoch 1: w={0,0}, b=0
  → (0,1) 误分类 → w={0,-0.1}, b=0.1
  → (1,0) 误分类 → w={-0.1,-0.1}, b=0
  → (1,1) 误分类 → w={-0.1,0}, b=-0.1
  mistakes=3

Epoch 2: w={-0.1,0}, b=-0.1
  → (0,0) 误分类 → w={-0.1,0}, b=0
  → (1,1) 误分类 → w={-0.1,0}, b=0
  mistakes=2

Epoch 3–100: w={-0.1, 0}, b=0 (稳定振荡)
  → 每轮 2 个误分类: (0,0) 和 (1,1) 或 (0,1) 和 (1,0)
  → 权重不会变化——感知机进入无限循环

**关键观察：XOR 训练第 2 轮后权重稳定在 w={-0.1, 0}, b=0，之后每轮始终有 2 个误分类点。感知机既不收敛也不发散，而是陷入一个固定振荡模式——这是线线性不可分数据集上的典型行为。

6. 感知机收敛定理 (Perceptron Convergence Theorem)

由 Novikoff 于 1962 年严格证明：

若训练数据集是线性可分的，则感知机算法在有限次迭代后必然收敛。

收敛所需的更新次数上界为：

  mistakes ≤ (R / γ)²

  其中:
    R = max ||x_i||    — 所有样本的最大欧氏范数
    γ = min |w*·x_i|   — 最优超平面的间隔 (margin)

对于本题 AND 数据集：R = √(1²+1²) = √2 ≈ 1.414。存在 γ > 0（因为 AND 线性可分），故算法必然在有限步收敛。定理的价值在于回答了"感知机什么时候能学成"这一根本问题——答案是"数据线性可分时必然收敛"。反面推论同样重要：若数据线性不可分，感知机永远不会停止更新，权重要么无限增长，要么陷入振荡。

7. 边缘情况分析

场景	输入条件	预期行为	原因
sign(0)	dot = 0 精确	sign(0) = +1	C 标准: 0.0 >= 0.0 为 true
sign(-0.0)	dot = -0.0 (IEEE 754)	sign(-0.0) = +1	IEEE 754: -0.0 == +0.0
sign(-ε)	dot ≈ -1e-17 (浮点误差)	sign(-ε) = -1	极小负数，返回 -1
全部正确分类	mistakes == 0 一整轮	提前停止，打印收敛信息	感知机收敛定理保证
XOR 永不收敛	线性不可分 (XOR)	运行满 100 轮，每轮 2 个错误	感感知机无法处理线性不可分数据
学习率 α = 0	α = 0	权重永远不变，永不收敛	没有学习发生
极大学习率	α 很大 (如 α = 10)	可能振荡甚至发散	步长过大越过最优解
初始权重非零	w₀ ≠ 0	从不同起点开始，可能更快或更慢收敛	收敛性与初值无关，只影响收敛路径

8. 感知机 vs 逻辑回归 vs 线性 SVM

特性	感知机	逻辑回归	线性 SVM
模型类型	线性硬分类	线性概率分类	最大间隔线性分类
输出	ŷ ∈	P(y=1\|x) ∈ [0,1]	ŷ ∈
决策函数	sign(w·x+b)	σ(w·x+b) (sigmoid)	sign(w·x+b)
损失函数	max(0, -y·ŷ) (hinge 近似)	log(1+e^{-y·ŷ}) (交叉熵)	max(0, 1-y·ŷ) (hinge)
优化方法	SGD (在线)	SGD/BGD (凸优化)	QP/拉格朗日对偶 (凸优化)
收敛保证	仅线性可分时	总是收敛	总是收敛
唯一解	否 (无穷多个)	是 (强凸)	是 (最大间隔唯一)
核方法	不支持 (可扩展为核感知机)	不支持	支持 (核技巧)
提出年份	1957 (Rosenblatt)	1958 (Cox)	1995 (Vapnik)

核心区分：感知机有无数个解（任何分离正负类的直线都算成功），SVM 选唯一最大间隔解，逻辑回归给出概率输出。这是三者在实际应用中选择的关键依据。

参考解答

TODO 1–3: dot, sign, predict — 基础函修改）

solution_62_todo1_3.c

static double dot(const double w[], double b, const double x[]) {
    double sum = b;
    for (int j = 0; j < N_FEATURES; j++)
        sum += w[j] * x[j];
    return sum;
}

static double sign(double val) {
    return (val >= 0.0) ? 1.0 : -1.0;
    /* IEEE 754: -0.0 >= 0.0 is true, sign(-0.0)=+1.0 */
}

static double predict(const double w[], double b, const double x[]) {
    return sign(dot(w, b, x));
}

要点：sign(0.0) = +1.0——因为 0.0 >= 0.0 为 true，这符合 C 语言标准和本题要求。predict 只需一行组合 dot 和 sign。

TODO 4: train_one_epoch — 单轮训练

solution_62_todo4.c

static int train_one_epoch(double w[], double *b,
                           const double X_data[][N_FEATURES],
                           const double Y_data[]) {
    int mistakes = 0;
    for (int i = 0; i < N_POINTS; i++) {
        double pred = predict(w, *b, X_data[i]);
        if (pred != Y_data[i]) {         /* 误分类 */
            for (int j = 0; j < N_FEATURES; j++)
                w[j] += ALPHA * Y_data[i] * X_data[i][j];
            *b += ALPHA * Y_data[i];    /* 注意：*b 解引用 */
            mistakes++;
        }
    }
    return mistakes;
}

要点：b 参数是 double*——必须写 *b += ... 而非 b += ...。更新使用真实标签 Y_data[i] 而非预测值 pred。X_data/Y_data 通过参数传入以便复用于 AND 和 XOR 两个数据集。

TODO 5: print_weights — 格式化打印

solution_62_todo5.c

static void print_weights(const double w[], double b) {
    printf("w = {%.4f, %.4f}, b = %.4f", w[0], w[1], b);
}

格式严格：小数点后固定 4 位，花括号内逗号后有空格 ({%.4f, %.4f})，不加换行符（由调用方控制）。

TODO 6: AND 训练主流程

solution_62_todo6.c

/* AND 训练主流程（在 main 中实现） */
double w[N_FEATURES] = {0.0, 0.0};
double b = 0.0;
int epoch;

printf("=== Perceptron Binary Classifier (AND logic) ===\n\n");
printf("Dataset:\n");
printf("  x=(0,0) y=-1  x=(0,1) y=-1  x=(1,0) y=-1  x=(1,1) y=+1\n");
printf("Learning rate α = 0.1, max epochs = %d\n", MAX_EPOCHS);
printf("Initial: ");
print_weights(w, b);
printf("\n");

printf("\n=== Training Rounds ===\n");
for (epoch = 0; epoch < MAX_EPOCHS; epoch++) {
    printf("--- Epoch %d ---\n", epoch + 1);
    printf("Before: ");
    print_weights(w, b);
    printf("\n");

    int mistakes = train_one_epoch(w, &b, X_AND, Y_AND);

    printf("After:  ");
    print_weights(w, b);
    printf("\n");

    printf("Classification:");
    for (int i = 0; i < N_POINTS; i++) {
        double pred = predict(w, b, X_AND[i]);
        printf("  (%.0f,%.0f)→%+.0f%c",
               X_AND[i][0], X_AND[i][1],
               pred, (pred == Y_AND[i]) ? '✓' : '✗');
    }
    printf("\n");

    if (mistakes == 0) {
        printf("All points correctly classified — converged!\n");
        epoch++;  /* 补偿循环内的 epoch 计数 */
        break;
    }
}
/* 决策边界 */
printf("\n=== Final Decision Boundary ===\n");
printf("Equation: w0*x0 + w1*x1 + b = 0\n");
printf("  %.4f * x0 + %.4f * x1 + %.4f = 0\n",
       w[0], w[1], b);
if (w[1] != 0.0)
    printf("  x1 = %.4f * x0 + %.4f\n",
           -w[0] / w[1], -b / w[1]);
else
    printf("  x0 = %.4f  (vertical line)\n", -b / w[0]);
printf("Converged in %d epochs.\n", epoch);

要点：After: 两个空格与 Before: 对齐。点之间用两个空格 " " 分隔。✓ 和 ✗ 是 Unicode 字符 U+2713 和 U+2717。收敛时 epoch++ 补偿计数（循环内的 break 落在 epoch 完成值上）。

TODO 7: XOR 演示段

solution_62_todo7.c

/* XOR 训练段（AND 收敛后继续） */
printf("\n=== Perceptron Binary Classifier (XOR logic) ===\n\n");
printf("Dataset:\n");
printf("  x=(0,0) y=-1  x=(0,1) y=+1  x=(1,0) y=+1  x=(1,1) y=-1\n");
printf("Learning rate α = 0.1, max epochs = %d\n", MAX_EPOCHS);

/* 重置权重 */
w[0] = 0.0; w[1] = 0.0; b = 0.0;
printf("Initial: ");
print_weights(w, b);
printf("\n");

printf("\n=== Training Rounds ===\n");
for (epoch = 0; epoch < MAX_EPOCHS; epoch++) {
    int print_full = (epoch < 5)                /* 前 5 轮完整 */
                  || (epoch >= 9 && (epoch+1) % 10 == 0); /* 每 10 轮快照 */

    if (print_full) {
        printf("--- Epoch %d ---\n", epoch + 1);
        printf("Before: ");
        print_weights(w, b);
        printf("\n");

        int mistakes = train_one_epoch(w, &b, X_XOR, Y_XOR);

        printf("After:  ");
        print_weights(w, b);
        printf("\n");

        printf("Classification:");
        for (int i = 0; i < N_POINTS; i++) {
            double pred = predict(w, b, X_XOR[i]);
            printf("  (%.0f,%.0f)→%+.0f%c",
                   X_XOR[i][0], X_XOR[i][1],
                   pred, (pred == Y_XOR[i]) ? '✓' : '✗');
        }
        printf("\n");
    } else {
        train_one_epoch(w, &b, X_XOR, Y_XOR);  /* 静默执行 */
    }

    /* 跳过轮次的摘要行 */
    if (epoch == 5)
        printf("  ... (epochs 6–9: oscillating, 2 mistakes each) ...\n");
    if (epoch == 10)
        printf("  ... (epochs 11–19: oscillating, 2 mistakes each) ...\n");
    if (epoch == 20)
        printf("  ... (epochs 21–29: oscillating, 2 mistakes each) ...\n");
    if (epoch == 30)
        printf("  ... (epochs 31–39: oscillating, 2 mistakes each) ...\n");
    if (epoch == 40)
        printf("  ... (epochs 41–49: oscillating, 2 mistakes each) ...\n");
    if (epoch == 50)
        printf("  ... (epochs 51–59: oscillating, 2 mistakes each) ...\n");
    if (epoch == 60)
        printf("  ... (epochs 61–69: oscillating, 2 mistakes each) ...\n");
    if (epoch == 70)
        printf("  ... (epochs 71–79: oscillating, 2 mistakes each) ...\n");
    if (epoch == 80)
        printf("  ... (epochs 81–89: oscillating, 2 mistakes each) ...\n");
    if (epoch == 90)
        printf("  ... (epochs 91–99: oscillating, 2 mistakes each) ...\n");
}
printf("\nWarning: Did not converge within %d epochs.\n", MAX_EPOCHS);
printf("XOR is not linearly separable "
       "— a single perceptron cannot learn it.\n");
printf("This demonstrates the fundamental limitation "
       "that led to the first AI winter.\n");

/* XOR 决策边界 */
printf("\n=== Final Decision Boundary ===\n");
printf("Equation: w0*x0 + w1*x1 + b = 0\n");
printf("  %.4f * x0 + %.4f * x1 + %.4f = 0\n", w[0], w[1], b);
if (w[1] != 0.0)
    printf("  x1 = %.4f * x0 + %.4f\n", -w[0]/w[1], -b/w[1]);
else
    printf("  x0 = %.4f  (vertical line)\n", -b / w[0]);
printf("Did not converge — dataset is not linearly separable.\n");

要点：紧凑输出策略——前 5 轮逐轮完整打印，之后每 10 轮打印一次 (epoch 10, 20, ... 100)。中间轮次用 ... (epochs M–N: oscillating, 2 mistakes each) ... 摘要行跳过。注意每轮即使不打印也要调 train_one_epoch 推进权重状态。

对照检查：sign(0) == +1 吗？train_one_epoch 中用 *b += ...（而非 b += ...）吗？更新用的是 Y_data[i]（真实标签）吗？点之间是两个空格 " " 吗？XOR 段 epoch++ 计数正确吗？AND 收敛后重置了 w 和 b 吗？

课堂讨论

为什么感知机必须使用 sign 函数？能否用 sigmoid 代替？
如果将 AND 数据集中 (0,0) 的标签改改为 +1，感知机还能收敛吗？
为什么说"感知机找到的决策边界不唯一"？
感知机的更新规则为什么是对误分类点做 w ← w + α·y·x？
本题中浮点误差"帮助"收敛是好还是坏？
如果 MAX_EPOCHS 设为 3 会发生什么？

讨论答案

Q1: 为什么必须用 sign？能否用 sigmoid？

感知机的 sign 产生硬分类 (+1/-1)，训练时判断"是否正确分类"是二元元的 (对/错)。如果使用 sigmoid（输出连续概率 [0,1]），则需要定义新损失函数 () (交叉熵) 和训练规则 (梯度下降)，模型实质上变为逻辑回归。sigmoid + 交叉熵是凸优化问题，有唯一最优解；而感知机有无限多解。两者的数学性质有本质区别。

Q2: (0,0) 改为 +1 后能收敛吗？

新数据集：(0,0)→+1, (0,1)→-1, (1,0)→-1, (1,1)→+1。这本质上是 XNOR (同或) 逻辑。XNOR 和 XOR 一样是线性不可分的——不存在直线使 (0,0) 和 (1,1) 在同一侧而 (0,1) 和 (1,0) 在另一侧。因此感知机不能收敛！**

Q3: 决策边界为什么不唯一？

感知机的学习目标是"将所有点正确分类"，只要达到零错误就停止。任何位于正负样本之间的直线都满足条件。AND 的可行边界包括 x₁ = -2x₀ + 2、x₁ = -1.5x₀ + 1.8、x₀ = 0.6 等。初始权重和样本遍历顺序决定收敛到哪一条。SVM 通过最大化间隔 (max margin) 挑选唯一最优边界——这是 SVM 相对感知机的重要优势。

Q4: 为什么更新规则是 w ← w + α·y·x？

从几何角度：y=+1 但被错分到负侧时，需将超平面向正方向"推"过 x。w ← w + αx 使 w 向 x 方向旋转，增加 w·x 的值。从优化角度：感知机损失 L = max(0, -y(w·x+b)) 对 w 的梯度，在误分类时为 -y·x，沿负梯度方向更新即 w ← w + α·y·x。

Q5: 浮点误差""帮助"收敛是好还是坏？

在这个具体例子中，0.2-0.2 的浮点舍入产生一个极小负数 (-ε)，使 (1,0) 的 sign 返回 -1，恰好避免了误分类。但从数值分析角度：如果误差导致本应正确分类的点被判错，可能延长训练；大数据集上浮点误差累积可能导致不可预测行为。生产级机器学习中常用 > 小阈值 (如 1e-9) 而非 >= 0 判断 sign，以降低浮点误差影响。

Q6: MAX_EPOCHS=3 发生什么？

本题第 4 轮才收敛。若 MAX_EPOCHS=3，第 3 轮后 mistakes=3≠0 继续，epoch=3 时循环条件 epoch < 3 为 false 退出。输出警告 "Did not converge within 3 epochs"。有趣的是：第 3 轮结束后的权重 w={0.2,0.1}, b=-0.2 恰好已经能正确分类所有点（第 4 轮验证了 0 错误）。这是一个边界情况——权重虽然正确，但算法尚未"察觉"。

课后练习

实现 OR 逻辑分类。保持感知机代码框架不变，将数据集换为 OR 逻辑 {(0,0)→-1, (0,1)→+1, (1,0)→+1, (1,1)→+1}，观察收敛轮数和最终决策边界。
参考解答
ex1_or_classifier.c
c
```
static const double Y_OR[N_POINTS] = {-1.0, 1.0, 1.0, 1.0};
/* OR 也是线性可分的——通常 2–3 轮收敛。决策边界典型为
 * x1 = -x0 + 1 (即 w={0.1,0.1}, b=-0.1) */
```
1
2
3

编写 is_linearly_separable() 判断函数。对于 2D 的 4 点数据集，编写一个函数判断是否线性可分（暴力检查所有可能的直线方向即可）。

参考解答

ex2_linear_separable.c

/* 4 点 2D 数据：检查是否线性可分
 * 思路：4 点中选 2 点确定直线（6 种），测试其余 2 点是否可分 */
int is_linearly_separable(double X[][2], double Y[], int n) {
    if (n <= 2) return 1;  /* ≤2 点必然线性可分 */
    /* 遍历所有点对作为决策边界参考方向 */
    for (int i = 0; i < n; i++) {
        for (int j = i+1; j < n; j++) {
            double wx = X[j][1] - X[i][1];  /* 法向量 x 分量 */
            double wy = -(X[j][0] - X[i][0]); /* 法向量 y 分量 */
            /* 检查过点 i 的直线是否分开所有点 */
            int pos = 0, neg = 0;
            for (int k = 0; k < n; k++) {
                double d = wx*(X[k][0]-X[i][0])+wy*(X[k][1]-X[i][1]);
                if (d > 0 && Y[k] == 1.0)  pos++;
                if (d < 0 && Y[k] == -1.0) neg++;
                if (d > 0 && Y[k] == -1.0) break;
                if (d < 0 && Y[k] == 1.0)  break;
            }
            if (pos + neg == n) return 1;
        }
    }
    return 0;  /* 线性不可分 */
}

学习率敏感性实验。将 α 分别设为 0.01、0.5、1.0、10.0，观察 AND 训练的收敛轮数变化。学习率是"越大越快"吗？

参考解答

α=0.01: 约 30–40 轮收敛 (步长太小，权重变化慢)
α=0.1:  4 轮收敛              (本题设定，适中)
α=0.5:  2–3 轮收敛            (步长大，更新激进)
α=1.0:  2 轮收敛              (可能跳过一些中间状态)
α=10.0: 可能振荡/不收敛        (步长过大，跨过最优解)

结论: α 太小收敛慢，α 适中最优，α 过大可能振荡。
感知机中 α 只影响收敛速度——sign 对缩放不敏感
(sign(αv)=sign(v) for α>0)，因此 α 不改变最终分类结果。

前后衔接

前置知识

课程	知识点	本题应用
Unit 1: 循环与条件	for/while 循环，if-else 分支	train_one_epoch 中的双层循环和条件判断
Unit 2: 数组与指针	数组遍历，指针传参	w[] 数组遍历，*b 指针解引用
Unit 2: 浮点数	double 类型，IEEE 754	权重/偏置的浮点运算，浮点误差的影响
Unit 2: printf 格式化	%f, %.4f 精度控制	print_weights 和 main 中的格式化输出
Unit 2: 堆与 Top-K	数据结构与算法设计思维	感知机同样是"模型 + 优化"的经典范式

后续课程

课程	知识点	与本题的关系
多层感知机 (MLP)	隐藏层，反向传播	感知机是 MLP 的组成单元
逻辑回归	sigmoid, 交叉熵	感知机的概率化版本
SVM	最大间隔，核方法	感知机的间隔最大化版本
梯度下降优化器	SGD, Adam, Momentum	感知机使用最朴素的 SGD
深度学习框架	PyTorch, TensorFlow	底层原理与感知机相同

参考资料

Rosenblatt, F. (1958). The Perceptron: A Probabilistic Model for Information Storage and Organization in the Brain. Psychological Review, 65(6), 386–408.
Minsky, M. & Papert, S. (1969). Perceptrons: An Introduction to Computational Geometry. MIT Press.
Novikoff, A. B. (1962). On Convergence Proofs for Perceptrons. Symposium on the Mathematical Theory of Automata, 12, 615–622.
Bishop, C. M. (2006). Pattern Recognition and Machine Learning. Springer. Chapter 4: Linear Models for Classification.
Goodfellow, I., Bengio, Y. & Courville, A. (2016). Deep Learning. MIT Press. Chapter 6: Deep Feedforward Networks.
Wikipedia: Perceptron
Wikipedia: Linear separability

"You don't understand anything until you learn it more than one way." ── Marvin Minsky

Lesson 62: 感知机二分类器 ​

练习任务 ​

核心知识点 ​

代码框架 ​

深度讲解 ​

1. 感知机的数学模型——最简单的神经网络 ​

2. 线性可分性——感知机能力边界 ​

3. 感知机学习规则——几何直觉与梯度视角 ​

4. AND 训练全流程追踪 ​

5. XOR——永不收敛的振荡 ​

6. 感知机收敛定理 (Perceptron Convergence Theorem) ​

7. 边缘情况分析 ​

8. 感知机 vs 逻辑回归 vs 线性 SVM ​

参考解答 ​

课堂讨论 ​

讨论答案 ​

课后练习 ​

前后衔接 ​

前置知识 ​

后续课程 ​

参考资料 ​

Lesson 62: 感知机二分类器

练习任务

核心知识点

代码框架

深度讲解

1. 感知机的数学模型——最简单的神经网络

2. 线性可分性——感知机能力边界

3. 感知机学习规则——几何直觉与梯度视角

4. AND 训练全流程追踪

5. XOR——永不收敛的振荡

6. 感知机收敛定理 (Perceptron Convergence Theorem)

7. 边缘情况分析

8. 感知机 vs 逻辑回归 vs 线性 SVM

参考解答

课堂讨论

讨论答案

课后练习

前后衔接

前置知识

后续课程

参考资料