117 lines
6.4 KiB
Markdown
117 lines
6.4 KiB
Markdown
---
|
||
title: 13 第十三章 原型方法和最邻近
|
||
draft: false
|
||
tags:
|
||
- ESL
|
||
---
|
||
在统计学习和机器学习中，**原型方法（Prototype Methods）** 是一类基于“代表性样本”进行分类或回归的算法。
|
||
|
||
简单来说，它的核心思想是：**与其记住所有的训练数据，不如选出（或计算出）一组具有代表性的“原型”来概括数据的特征。** 当新样本出现时，通过比较它与这些原型的相似度来进行决策。
|
||
|
||
原型方法（Prototype Methods）在系统层面本质上是一个“以空间换时间，再以计算复杂度换取缓存命中率”的权衡过程。
|
||
|
||
---
|
||
|
||
## [逻辑架构图]
|
||
|
||
- **动机层 (Motivation)**：解决 $k$-NN 的存储开型 ($O(N)$) 与计算开销 ($O(Np)$) 的维数灾难。
|
||
|
||
- **构造层 (Construction)**：
|
||
|
||
- **无监督构造**：K-Means / K-Medoids（基于质心的拓扑空间划分）。
|
||
|
||
- **有监督构造**：LVQ（基于决策边界的动态向量调整）。
|
||
|
||
- **决策层 (Inference)**：基于 Voronoi 图（泰森多边形）的最近邻搜索。
|
||
|
||
- **系统优化层 (Systems)**：数据压缩、缓存局部性优化、分支预测友好性。
|
||
|
||
|
||
---
|
||
|
||
## [深度整理正文]
|
||
|
||
### 1. 从“基于记忆”到“基于抽象”的范式转移
|
||
|
||
在统计学习中，$k$-最近邻（$k$-NN）被归类为**懒惰学习 (Lazy Learning)**，它将所有的决策推迟到预测阶段。
|
||
|
||
- **原本内容**：k-NN 需要存储所有训练样本。原型方法是对其的优化，通过找到数量更少的点（原型）来实现压缩性和代表性。
|
||
|
||
- **扩充部分**：{从系统架构角度看，$k$-NN 的瓶颈在于 **Memory Wall**（存储墙）。当数据集 $N$ 极大时，每一次预测都会触发海量的非连续内存访问，导致严重的 **Cache Miss** 和 **TLB Thrashing**。原型方法通过构造一组 $K \ll N$ 的原型向量，将模型规模从 $O(N)$ 降低到 $O(K)$，使得原型向量能够完整驻留在 **L2 甚至 L1 Cache** 中，从而将 I/O 密集型任务转化为计算密集型任务。}
|
||
|
||
|
||
### 2. K-均值聚类 (K-Means)：无监督的原型提取
|
||
|
||
- **原本内容**：K-Means 是典型的原型方法。每个簇的质心（Centroid）就是该簇的原型，用 K 个点来代表数据。
|
||
|
||
- **扩充部分**：{K-Means 的本质是在最小化重构误差（Reconstruction Error）。在实现上，它是 **Lloyd 算法**的迭代过程。为了在底层提高执行效率，专家级实现会利用 **SIMD (Single Instruction, Multiple Data)** 指令集（如 AVX-512）并行计算样本到 $K$ 个质心的欧氏距离。
|
||
|
||
$$ J = \sum_{n=1}^N \sum_{k=1}^K r_{nk} \| x_n - \mu_k \|^2 $$
|
||
|
||
同时，在硬件加速中，我们会使用 **半精度浮点数 (FP16)** 甚至 **INT8 量化**来存储质心向量，以进一步榨取内存带宽。}
|
||
|
||
|
||
### 3. 学习向量量化 (LVQ)：有监督的边界增强
|
||
|
||
- **原本内容**：这是一种有监督方法。如果原型正确预测了样本，向样本靠近；预测错误，则远离样本。
|
||
|
||
- **扩充部分**：{LVQ（尤其是 LVQ2.1）是在修正 **Bayes 决策边界**。它的更新法则遵循随机梯度下降（SGD）的变体：
|
||
|
||
- 正确分类：$w_j \leftarrow w_j + \epsilon (x - w_j)$
|
||
|
||
- 错误分类：$w_j \leftarrow w_j - \epsilon (x - w_j)$
|
||
|
||
这种“推拉”机制在底层实现时，对**分支预测器 (Branch Predictor)** 极不友好，因为更新逻辑取决于标签匹配的条件判断。在高性能实现中，我们通常采用 **Predication（谓词化指令）** 或掩码操作来消除条件跳转，保持指令流水线的平滑。}
|
||
|
||
|
||
### 4. 关键算法变体对比
|
||
|
||
- **原本内容**：
|
||
|
||
- **质心分类器**：每个类一个均值，简单但高效。
|
||
|
||
- **K-Medoids**：必须是真实样本点，对异常值鲁棒。
|
||
|
||
- **RNN (Reduced Nearest Neighbor)**：删掉不影响准确率的样本，为 k-NN 瘦身。
|
||
|
||
- **扩充部分**：{**K-Medoids** 的优势在于它不要求特征空间满足欧氏空间的公理化假设，仅需定义距离矩阵 $D_{ij}$。这在处理非数值型对象（如进程系统调用序列）时极具价值。从 **OS 调度**的角度看，RNN 留下的样本点可以被视为 **Support Vectors** 的原型版，它们决定了内核中分类器所需的最小驻留集大小（Working Set Size）。}
|
||
|
||
|
||
### 5. 原型方法的系统级应用
|
||
|
||
- **原本内容**：
|
||
|
||
- 数据压缩：降低存储，适合嵌入式。
|
||
|
||
- 降噪与提速：抵消异常值，降低推理延迟。
|
||
|
||
- 可解释性：观察原型即代表类别特征。
|
||
|
||
- **扩充部分**：{在**嵌入式实时系统**（如你关注的健康监测 Rust 项目 `hGuard`）中，原型方法的应用涉及 **Interrupt Latency**。
|
||
|
||
- **快速路径优化**：通过线性扫描极少量的原型（$K=10\sim50$），可以将判别延迟控制在微秒级，避免了 $k$-NN 在检索树（KD-Tree）查找时可能产生的最坏情况 $O(N)$ 时间复杂度。
|
||
|
||
- **冷热数据分离**：常用的原型放在高速 SRAM 中，次要原型放在 Flash 中，利用存储层级结构最大化能效比。}
|
||
|
||
|
||
---
|
||
|
||
## [边界知识联动]
|
||
|
||
1. **CPU 缓存（L1/L2/L3）**：
|
||
|
||
- $k$-NN 的随机访问模式会导致大量的 **Cache Miss**；而原型方法通过缩减参数规模，使原型向量集符合 **Temporal Locality（时间局部性）**，显著提升了 CPU 的计算吞吐量（IPC）。
|
||
|
||
2. **虚拟内存与 TLB**：
|
||
|
||
- 大规模数据集在进行全量搜索时会频繁触发 **Page Fault**。原型方法将数据集压缩后，模型通常小于一个内存页（4KB）或驻留在少数几个大页（Huge Pages）中，极大地减少了 **TLB Miss**。
|
||
|
||
3. **编译器优化（Vectorization）**：
|
||
|
||
- 在计算欧氏距离 $\|x - w\|^2$ 时，现代编译器（如 LLVM/Clang 或 Rust 的 `rustc`）能自动将循环展开并应用 **Auto-Vectorization**。如果原型数量 $K$ 是 8 或 16 的倍数，将完美对齐 SIMD 寄存器宽度。
|
||
|
||
4. **统计学习理论 (ESL 视角)**：
|
||
|
||
- 原型方法本质上是 **高度非线性的降维**。它将高维流形通过 Voronoi 划分投影到了低维的离散代表点上，这与 **Vector Quantization (VQ)** 在信号处理中的有损压缩原理完全一致。
|
||
|