6 第六章 核光滑方法

[逻辑架构图]

本章知识的内在逻辑可以用一条“从局部直觉到高维结构，再到概率与计算权衡”的演进主线来概括：

1. 基础直觉（点）：从 KNN 的生硬截断，平滑过渡到基于距离加权的核光滑（Nadaraya-Watson）。

2. 局部建模（线与面）：在核的局部权重内，引入多项式拟合（局部回归），解决边界偏差。

3. 高维解构（空间）：面对高维空间的“维数灾难”，通过假设特定结构（ANOVA、可变系数模型）将复杂问题降维，并使用Backfitting算法分而治之。

4. 横向扩展（概率与分类）：将局部加权的思想从回归推广到似然估计（局部似然）、密度估计（KDE）和分类（混合模型）。

5. 工程落地（底层计算）：在真实系统运行这些非参数模型时的复杂度权衡与优化策略。

---

[深度整理正文]

1. 核光滑方法 (Kernel Smoothing Methods)

你的笔记：KNN引入，对30-NN来说，拟合的函数并不连续，“不连续是不好看并且不必要的”，“我们可以分配权重,使其随着与目标点的距离平滑降低.” 核：“根据距离远近分配发言权的投票机制。”“核”本质上都在回答一个问题：两个点之间到底有多“亲近”？

{ 系统级扩充：从系统执行的角度看，传统的 K-NN 需要维护一个大小为 $K$ 的优先队列来进行边界截断，这在底层会导致极其频繁的分支预测失败（Branch Prediction Penalties）。而核方法（如高斯核）通过引入连续的衰减函数，将离散的条件判断转化为连续的浮点运算，这对于现代 CPU 的SIMD（单指令多数据流）向量化指令集（如 AVX-512）极其友好，能够在寄存器层面实现流水线式的并行计算。}

2. 一维核光滑器 (One-Dimensional Kernel Smoothers)

你的笔记：在统计学和机器学习中，Nadaraya–Watson 核回归是一种非参数预测方法。核心思想：对于新输入点 $x$，其预测值 $\hat{f}(x)$ 是训练集目标值 $y_i$ 的加权平均，权重取决于距离。距离越近的点，权重越大。

• 数学表达式：$\hat{f}(x)=\frac{{\sum }_{i=1}^{n}K\left(\frac{x-x_i}{h}\right)y_i}{{\sum }_{j=1}^{n}K\left(\frac{x-x_j}{h}\right)}$

• $K(\cdot )$：核函数，常用高斯核 $K(u)=\frac{1}{\sqrt{2\pi }}{e}^{-\frac{u^2}{2}}$。必须非负，0处最大。

• 分母：用于归一化，确保所有权重的总和为 1。

• 优缺点：优点是非参数的，能拟合复杂非线性；缺点是计算量大（预测需遍历全集，复杂度 $O(n)$），受“边界偏差”影响，在高维空间表现差（维度灾难）。

{ 系统级扩充：Nadaraya-Watson 估计器在本质上是一个Lazy Learning（惰性学习）机制。与参数化模型在训练阶段把知识压缩进权重矩阵（存入 L1/L2 Cache）不同，NW 核回归在推断时必须将整个数据集 $X$ 频繁载入内存。这使得它在系统层面是一个典型的Memory-bound（内存带宽受限）任务。每次查询都需要遍历内存，容易引发高昂的 Cache Miss 和 TLB Miss 惩罚。}

3. 核的宽度 (Width of the Kernel)

你的笔记：$h$：带宽（Bandwidth）。这是最重要的超参数。$h$ 越大，平滑程度越高（可能欠拟合）；$h$ 越小，曲线越波动（可能过拟合）。

{ 系统级扩充：带宽 $h$ 的选择本质上是在控制偏差-方差权衡（Bias-Variance Tradeoff）。在数学上，一维情况下的渐近均方误差（AMSE）的最优带宽解析解通常与 $n^{-1/5}$ 成正比（其中 $n$ 为样本量）。从编译器优化的视角来看，过小的 $h$ 会导致大量的核函数计算结果下溢（Underflow）至0，这在 IEEE 754 浮点数标准下会触发 Subnormal numbers（次正规数）处理机制，可能导致 CPU 计算周期暴增（硬件异常处理），因此在工程实现时常需要对 $h$ 的极小值施加硬性截断或开启编译器的 -ffast-math 选项以平滑忽略次正规数。}

4. ${\mathbb{R}}^p$ 中局部回归 (Local Regression in ${\mathbb{R}}^p$)

你的笔记：核函数在非参数估计中充当局部加权机制，使得函数估计在某一点附近主要依赖邻域数据；当与局部多项式拟合结合时，其效果类似于对目标函数在该点进行加权的局部泰勒近似。流形：约束、自由度、轨道。

{ 系统级扩充：为了消除 NW 估计器的“边界偏差（Boundary Bias）”，我们使用局部多项式回归。对于每个查询点 $x_0$，我们需要解一个加权最小二乘（WLS）问题：$\hat{\beta }=(X^{T}WX{)}^{-1}{X}^{T}Wy$。其中 $W$ 是一个对角线为核权重的 $N\times N$ 稀疏对角矩阵。在底层线性代数库（如 BLAS/LAPACK）中，由于 $X^{T}WX$ 在数据稀疏或边界处可能接近奇异（ill-conditioned），直接求逆会导致严重的数值不稳定。工程上强制要求使用Cholesky分解或QR分解，并且利用局部矩阵的高速缓存局部性（Cache Locality）分块计算以压榨 CPU 的 FMA（乘加计算）单元。}

5. ${\mathbb{R}}^p$ 结构化局部回归模型 (Structured Local Regression Models in ${\mathbb{R}}^p$)

你的笔记：高维展开：把复杂函数拆成低维函数的叠加，主动砍掉高阶交互。问题：拟合 $f(X)\to$ （结构假设）ANOVA 分解/加性模型/可变系数模型 $\to f(X)=g_1(X_1)+g_2(X_2)+\cdots \to$ （优化方法）backfitting $\to$ （具体拟合）核平滑/spline/局部回归。

• 可变系数模型：$f(X)=\alpha (Z)+{\beta }_1(Z)X_1+\cdots +{\beta }_q(Z)X_q$。直观理解：工龄对薪资的影响斜率随行业类型 $Z$ 平滑变化。通过核函数 $K_{\lambda }(z_0,z_i)$ 对样本加权进行局部加权最小二乘估计：

  $\min {\sum }_{i=1}^N{K}_{\lambda }(z_0,z_i){\left(y_i-\alpha (z_0)-\sum x_{ji}{\beta }_j(z_0)\right)}^2$

• 后验拟合算法 (Backfitting)：“分而治之”的迭代算法。初始化为0 $\to$ 计算残差 $\text{Residual}=Y-\alpha -{\sum }_{k\ne j}{\hat{f}}_k(X_k)\to$ 用残差对 $X_j$ 平滑更新 $\to$ 轮流更新直到收敛（像调音师调钢琴）。无需庞大矩阵求逆，处理高维数据极高效。

{ 系统级扩充：Backfitting 算法在数值计算本质上等同于求解庞大线性系统的Gauss-Seidel 迭代法。因为我们规避了构造 $O((Np{)}^3)$ 的巨型 Hessian 矩阵求逆，而是用一系列 $O(N)$ 的 1D 平滑器代替。从内存管理角度看，Backfitting 的每一次变量循环（Coordinate Descent）都需要遍历特征列 $X_j$。如果数据在内存中是行优先（Row-major）存储的（如 C/C++ 默认），按列提取会引发灾难性的 Cache Thrashing（缓存抖动）。因此，高效的底层实现会强制将数据集转置为列优先（Column-major）（如 Fortran/R 机制），以保证每次平滑操作都能享受到完美的空间局部性（Spatial Locality）。}

6. 局部似然和其他模型 (Local Likelihood and Other Models)

你的笔记：阶数为 $k$ 的自回归时间序列：$y_t={\beta }_0+{\beta }_1{y}_{t-1}+\cdots +{\beta }_k{y}_{t-k}+{\epsilon }_t$。用局部最小二乘拟合允许模型根据序列的短期记忆（short-term history）来变化。这区别于传统因窗口时间变化的动态线性模型。

{ 系统级扩充：局部加权不仅限于最小二乘，还可以扩展到任何似然函数（如 Logistic 回归）。对于局部对数似然 $\sum K(x_0,x_i)l(y_i,\theta (x_0))$，我们需要结合局部权重进行迭代加权最小二乘（IRLS）。在这个过程中，系统需要大量计算指数函数（$\exp$）和对数函数（$\log$），这些是昂贵的复杂指令。现代机器学习框架通常在这里调用高度优化的数学库（如 Intel MKL 的 VML 模块），使用泰勒展开或查表法（LUT）来进行并行化的近似运算。}

7. 核密度估计和分类 (Kernel Density Estimation and Classification)

{ 深度扩充：当我们丢掉响应变量 $Y$，只看特征 $X$ 的分布时，核方法就演变成了Parzen Window（核密度估计 KDE）：${\hat{f}}_X(x)=\frac{1}{N}{\sum }_{i=1}^N{K}_h(x-x_i)$。在分类任务中，我们可以分别对各个类别的数据拟合 KDE，然后通过贝叶斯定理转化为后验概率进行分类（这相当于非参数版本的朴素贝叶斯）。

计算加速黑魔法：由于一维或低维 KDE 本质上是一个信号与核函数的离散卷积（Convolution）操作，当评估网格点密集时，$O(N^2)$ 的复杂度会致系统于死地。底层算法通常通过快速傅里叶变换（FFT）将空间域的卷积转化为频域的乘法，从而将时间复杂度断崖式降至 $O(N\log N)$。}

8. 径向基函数和核 (Radial Basis Functions and Kernels)

{ 深度扩充：径向基函数网络（RBF Networks）形式为 $f(x)={\sum }_{j=1}^M{\alpha }_j{K}_{{\lambda }_j}(x,{\mu }_j)$。与前面提到的每次推断都依赖全量数据的局部回归不同，RBF 是一种从惰性学习（Lazy）到急切学习（Eager）的妥协。它预先挑选出 $M$ 个质心（Centroids，通常通过 K-Means 获得），从而极大地压缩了模型尺寸。这在系统级意味着模型的推断阶段从内存密集型（Memory-bound）转变成了计算密集型（Compute-bound），可以被轻松装入 L1 Cache 中高速执行。这里也是支持向量机（SVM）核技巧和再生核希尔伯特空间（RKHS）表征定理的理论交汇点。}

9. 混合模型的密度估计和分类 (Mixture Models for Density Estimation)

{ 深度扩充：核密度估计（KDE）在每一个数据点上放了一个“核”，这太重了。高斯混合模型（GMM）通过引入隐变量（潜类），假设数据由固定数量（$K\ll N$）的高斯分布混合而成，是 KDE 的参数化、精简版。求解 GMM 依赖于 EM算法（期望最大化）。 在硬件视角下，EM 算法的 E 步（计算所有点在各个高斯分量下的后验概率）是极度数据并行（Embarrassingly Parallel）的，非常适合丢给 GPU 执行 CUDA Kernel 矩阵乘法；而 M 步（聚合更新均值和协方差）则是一个规约操作（Reduction），需要精细控制 GPU 的共享内存（Shared Memory）和线程块同步（__syncthreads()）。}

10. 计算上的考虑 (Computational Considerations)

{ 深度扩充：基于核的非参数方法最大的痛点在于推断时的高延迟。为了避免 $O(N)$ 的穷举扫描，工业界不会使用朴素遍历，而是依赖空间划分数据结构：

1. KD-Tree（K维树）/ Ball-Tree：通过预建树形结构将搜索复杂度降至 $O(\log N)$。但在高维空间（$p>20$）中，由于“空旷空间”现象，树的回溯会退化为近乎全遍历。

2. 局部敏感哈希（LSH）或 HNSW：在现代推荐系统和向量数据库（如 Milvus, FAISS）中，我们通常牺牲一定的理论绝对正确性，采用近似最近邻（ANN）图算法。它用空间换时间，大幅度削减核权重极小的长尾计算，保障了在线系统的低延迟（Latency）SLA。}

---

[边界知识联动]

本章知识并非孤岛，其核心理念与计算机系统与算法的其他领域有着极深的同构性：

• 硬件层面 (CPU 缓存与内存带宽)：Lazy Learning 算法（K-NN, 核回归）是测试内存带宽（Memory Bandwidth）的绝佳基准；而通过 Backfitting 和 RBF 抽取参数的过程，本质上是为了迎合 CPU Cache 局部性（Locality of Reference）所做的模型压缩。

• 编译与指令集 (SIMD与流水线)：连续核函数（高斯核）避免了类似传统树模型或严格截断模型中的大量 if-else 跳转分支，极大提高了 CPU 流水线的执行效率和 SIMD 寄存器的利用率。

• 系统内核 (调度器设计)：操作系统中 CFS（完全公平调度器）对进程权重的平滑衰减处理，与局部加权思想（历史执行时间越近权重越大）在哲学上是同源的。

• 前端/图形学 (渲染与着色)：在计算机图形学（如 OpenGL/Vulkan）中，图像的抗锯齿（Anti-aliasing）和模糊后处理，本质上就是对像素点阵在 2D 空间进行高斯核密度计算和二维核平滑。

---

核光滑和核方法的区别与联系

[逻辑架构图]

• 核光滑 (Kernel Smoothing)：本质是局部加权 (Local Weighting)。利用核函数作为“平滑窗”，在原始特征空间内对邻域数据进行物理加权。

• 核方法 (Kernel Methods)：本质是特征映射 (Feature Mapping)。利用核函数作为“度量工具”，将数据隐式映射到高维希尔伯特空间，并在该空间执行线性运算。

• 交汇点：再生核希尔伯特空间 (RKHS)。核光滑的解在特定条件下可以表征为核方法的特殊形式。

---

[深度整理正文]

1. 核光滑 vs 核方法：定义与动机的解耦

我原本的内容：核光滑是“根据距离远近分配发言权的投票机制”。

{ 扩充部分：

• 核光滑 (Smoothing) 关注的是连续性 (Continuity)。它在低维空间（通常是原始输入空间）操作，目的是为了让预测函数变得平滑，解决诸如 KNN 这种硬截断带来的非连续性问题。它不需要数据在高维空间线性可分。

• 核方法 (Methods) 关注的是线性化 (Linearization)。它通过“核技巧 (Kernel Trick)”解决原始空间非线性的问题。其核心逻辑是：$K(x,x^{\prime })=⟨\varphi (x),\varphi (x^{\prime })⟩$。即：不需要显式定义高维映射 $\varphi$，只要知道高维空间里的内积怎么算就行。

  }

2. 核光滑在哪里使用了内积？ (寻找 Inner Product)

这是一个非常深刻的误区。在Nadaraya-Watson 估计器这种纯粹的核光滑中，并没有直接使用希尔伯特空间的内积，它使用的是距离的度量（通常是欧氏距离的函数）。但是，当你深入到以下三个层面时，内积就会浮出水面：

A. 局部回归的投影视角

在进行局部多项式回归时，我们需要最小化加权损失函数。

{ 扩充部分：在底层实现 WLS（加权最小二乘）时，求解方程 $\hat{\beta }=(X^{T}WX{)}^{-1}{X}^{T}Wy$。这里的 $X^{T}X$ 项本质上就是样本特征向量之间的加权内积集。从几何上讲，这是将目标向量 $y$ 投影到由特征列向量张起的子空间中，而“投影”这一线性代数操作的核心就是内积。}

B. 等价核 (Equivalent Kernels) 与 线性算子

我原本的内容：核函数在某一点附近主要依赖邻域数据。

{ 扩充部分：对于任何线性光滑器（如回归样条、局部线性回归），其预测值都可以写成 $\hat{f}=Sy$ 的形式，其中 $S$ 是光滑矩阵。$S$ 的每一行可以看作是一个“等价核”。在泛函分析中，预测值 $\hat{f}(x_0)$ 可以表示为观测值 $y$ 与等价核函数在 $L^2$ 空间下的内积：$\hat{f}(x_0)=⟨y,s(x_0,\cdot )⟩=\int y(t)s(x_0,t)dt$。这是内积在函数空间层面的体现。}

C. 再生核希尔伯特空间 (RKHS) 的统一

这是两者关系的终极答案。

{ 扩充部分：根据 表征定理 (Representer Theorem)，许多正则化损失函数的解（包括某些形式的光滑插值）都可以写成核函数的线性组合：$f(x)=\sum {\alpha }_{i}K(x,x_i)$。

此时，核光滑中的“核”变身成了核方法中的“正定核”。当我们衡量函数复杂度（正则项）时，使用的是 RKHS 中的范数：$\Vert f{\Vert }_{\mathcal{H}}^2=\sum \sum {\alpha }_i{\alpha }_{j}K(x_i,x_j)$。这里的 $K(x_i,x_j)$ 正是高维特征空间里的内积。 换句话说，核光滑是我们在观察“平滑”这一结果，而核方法是我们利用“内积”这一工具来实现平滑。}

3. 统计学习要素 (ESL) 中的计算折中

我原本的内容：计算量大，受维度灾难影响。

{ 扩充部分：在计算机系统层面，核方法（如 SVM）由于内积的存在，其计算核心是 格拉姆矩阵 (Gram Matrix) $G_{ij}=K(x_i,x_j)$。这是一个 $N\times N$ 的对称矩阵。

• 内存开销：对于 $N=10^6$ 的数据集，存储 $G$ 需要约 4TB 显存，这超出了单机极限。

• 系统优化：因此系统专家会采用 Nyström 方法（通过采样 $m\ll N$ 个点来低秩近似内积矩阵）或 随机傅里叶特征 (Random Fourier Features)。后者利用 Bochner 定理，将内积计算转化为显式的低维线性运算，从而将模型从 $O(N^2)$ 的核方法拉回到 $O(N)$ 的线性计算效率。}

---

[边界知识联动]

• 硬件加速 (Tensor Cores)：现代 GPU 的 Tensor Core 专门优化了 $D=A\times B+C$ 的矩阵乘加运算。核方法中的大规模内积计算（Gram Matrix）可以被高度并行化地映射到这些硬件单元上。

• 泛函分析 (Riesz Representation Theorem)：在希尔伯特空间中，任何连续线性泛函都可以表示为与某个元素的内积。这解释了为什么“评估一个点的值”这种操作，在核方法视野下本质上就是在算内积。

• 数字信号处理 (FIR Filter)：核光滑其实是一个滑动平均滤波器。在信号处理系统中，这被称为卷积。根据卷积定理，空域的卷积等价于频域的点积（内积的另一种形式）。这也是为什么我们可以用 FFT 来加速核光滑计算的深层原因。