第 2–3 章 · 感知机与 K 近邻：最小起点

两个最简单的算法，恰好占据两个极端：感知机是"错误驱动"的线性分类最小实现（SVM 与神经网络的祖先）；KNN 是"懒惰学习"的极端（没有训练过程，全靠存储与比较）。从最小处理解学习。

感知机：线性可分的错误驱动学习

模型 $f(x) = \text{sign}(w\cdot x + b)$。Novikoff 定理保证：数据线性可分时，随机梯度更新

在有限步内收敛（误分次数上界 $\propto 1/\gamma^2$，$\gamma$ 为间隔）。不可分时算法永不收敛——这个缺陷是 SVM（软间隔）与神经网络（多层 + 非线性）诞生的直接动因。感知机的对偶形式（权重 = 训练点的线性组合）预告了 SVM 的对偶结构。

K 近邻：没有模型的模型

预测：找 $k$ 个最近邻投票（分类）/平均（回归）。三件套：

KNN 的理论靠山：$k \to \infty$、$k/N \to 0$ 时错误率趋贝叶斯最优率的两倍以内——非参数方法的底线保证。

• 距离：欧氏、曼哈顿、$L_p$——度量决定"相似"的含义；
• $k$ 值：小 k 欠平滑（过拟合、对噪声敏感）、大 k 过平滑（欠拟合、决策边界趋平）——交叉验证定 k；
• 结构（kd 树）：低维（$d \lesssim 20$）搜索近似 $O(\log N)$；高维失效（维度灾难：距离对比度消失）——KNN 的高维死穴。

老师的提醒

• 感知机实验（手推 10 步以内更新）理解"错误驱动"：每一步只看一个错样本——SGD 的原型心智模型。
• KNN 实用三查：特征尺度标准化了吗？维度高吗（高维改用学习度量或降维）？k 用交叉验证选了吗？

自检

• Novikoff 定理的条件与结论？
• k 值如何影响偏差-方差？
• kd 树为什么在高维失效？

更深一层：感知机的"错误驱动"是 SGD 的原型

感知机的更新规则 $w \leftarrow w + \eta y_ix_i$（误分时）有一个深刻的身份：它是随机梯度下降的最小实现。每次只看一个错样本、朝修正它的方向挪一步——SGD 的全部心智模型都在这里。Novikoff 定理（线性可分时有限步收敛）给出误分次数上界 $\propto 1/\gamma^2$（$\gamma$ 为间隔）——"间隔"这个概念第一次出场，它在第 7 章 SVM 里将成为主角。感知机的收敛性证明 + 间隔概念是理解 SVM 与神经网络训练动态的最短路径。

感知机的对偶形式（权重 = 训练点的线性组合 $w = \sum\alpha_i y_i x_i$）预告了核方法：所有计算只依赖内积 $x_i \cdot x_j$——对偶形式是核技巧的入口。

推导细读：KNN 的"懒惰学习"与高维死穴

KNN 的"没有训练过程"（懒惰学习）是它的全部优势与全部弱点：优势是没有归纳偏置（局部结构自适应）；弱点是维度灾难——高维空间里"最近邻"的距离对比度消失（所有点对几乎等距），KNN 在高维失效。对策：降维（PCA/学习度量）或用近似最近邻（kd 树在低维 $d \lesssim 20$ 有效，高维换 LSH/Faiss 的近似索引）。KNN 的理论靠山：$k \to \infty$、$k/N \to 0$ 时错误率趋贝叶斯最优率的两倍以内——非参数方法的底线保证。

在真实世界里：感知机与 KNN 的"极简基线"价值

两个算法在现代 ML 工作流里的价值是极简基线：感知机（或逻辑回归）与 KNN 是任何新任务的"第一参照系"——如果一个复杂模型打不过这两个基线，说明数据或特征有问题，而不是模型不够深。基线先行的纪律（先跑最简模型、再上复杂模型）是工业 ML 的第一守则，而感知机与 KNN 就是这对"基线双子星"。

专题深入：感知机的"最小完备"与 KNN 的"懒学习"完整版

第二章-第三章的对照是"最小起点"的两面：感知机是二分类的最小模型（$f(x) = \mathrm{sign}(w\cdot x + b)$）+ 最小算法（错分驱动随机梯度：$\Delta w = \eta y_i x_i$）——Novikoff 定理保证线性可分时有限步收敛（$\|w - w^*\| \le \|w_0\| + k\gamma$ 的几何直觉：间隔 γ 越大收敛越快）；不可分时算法震荡不停——"收敛定理 + 不可分震荡"两面合起来才是完整感知机；对偶形式 + 核化是通往 SVM 的桥。KNN 的懒学习哲学：不训练、预测时全库检索——模型就是数据本身；k 的偏差-方差（k 小噪声敏感、k 大边界模糊）；kd 树的加速与失效（低维剪枝快、维度灾难下退化为线性扫描——"kd 树只在 d < 20 有效"是工程边界；高维改用 ANN（HNSW、IVF-PQ））。距离度量的隐性权力（标准化与否改变一切：量纲大的特征统治欧氏距离——KNN 的特征预处理 = 模型的一部分）。

推导细读：KNN 的"理论安全带"与感知机的"对偶性"完整版

两章的推导细节：Cover-Hart 定理（无穷样本下 1-NN 的误码率不超过两倍贝叶斯错误率：$P \le P^*(2 - cP^*)$——"最笨的方法在最坏意义下不超过 2 倍最优"——KNN 的理论安全带，也是"先跑 KNN 基线"的理论背书）；一致性与 k 的增长条件（$k \to \infty$ 且 $k/N \to 0$ 时 KNN 一致——k 要比样本长得慢）；感知机对偶形式（$w = \sum_i \alpha_i y_i x_i$，α 累计更新次数——内积提前算成 Gram 矩阵，核化的接口就在这）；间隔的首次出场（Novikoff 证明里的 γ 是"最近样本到超平面的距离"——SVM 的 Margin 思想在感知机证明里已经埋伏）。Minkowski 距离族的语义（p=1 曼哈顿抗离群、p=2 欧氏、p→∞ 切比雪夫取最大维差；文本用余弦——方向相似度）。

工程案例细节：最小起点算法的现代岗位工程版

两三章的工程出口：KNN 的现代岗位（推荐系统的 item-CF 变体、图像检索的向量检索——"KNN + 学习型 embedding"在深度时代复活：ANN 引擎（Faiss、Milvus）就是工业级 KNN）；异常检测的 KNN 密度（k-距离作为局部密度——LOF 异常检测的基石）；感知机思想的现代回声（在线学习与误分驱动的更新规则活在 FTRL/logistic online 的逻辑里——"错就修，对不动"是最古老的 SGD）；kd 树/球树的空间检索（地理围栏附近搜索——LBS 服务的几何索引）。两个"玩具"算法的岗位证明：最小模型 + 工程化检索/索引 = 真实产品——李航把它们放在前两章正是"简单方法先上场"的方法论示范。