18 KiB
title, draft, tags
| title | draft | tags | |
|---|---|---|---|
| 6 第六章 核光滑方法 | false |
|
[逻辑架构图]
本章知识的内在逻辑可以用一条“从局部直觉到高维结构，再到概率与计算权衡”的演进主线来概括：
-
基础直觉（点）：从 KNN 的生硬截断，平滑过渡到基于距离加权的核光滑（Nadaraya-Watson）。
-
局部建模（线与面）：在核的局部权重内，引入多项式拟合（局部回归），解决边界偏差。
-
高维解构（空间）：面对高维空间的“维数灾难”，通过假设特定结构（ANOVA、可变系数模型）将复杂问题降维，并使用Backfitting算法分而治之。
-
横向扩展（概率与分类）：将局部加权的思想从回归推广到似然估计（局部似然）、密度估计（KDE）和分类（混合模型）。
-
工程落地（底层计算）：在真实系统运行这些非参数模型时的复杂度权衡与优化策略。
[深度整理正文]
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 W X)^{-1} X^T W y$。其中 W 是一个对角线为核权重的 N \times N 稀疏对角矩阵。在底层线性代数库（如 BLAS/LAPACK）中，由于 X^T W X 在数据稀疏或边界处可能接近奇异（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) + \dots \to （优化方法）backfitting \to （具体拟合）核平滑/spline/局部回归。
-
可变系数模型：$f(X) = \alpha(Z) + \beta_1(Z)X_1 + \dots + \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 \neq 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} + \dots + \beta_k y_{t-k} + \varepsilon_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) 的穷举扫描，工业界不会使用朴素遍历，而是依赖空间划分数据结构：
-
KD-Tree（K维树）/ Ball-Tree：通过预建树形结构将搜索复杂度降至 $O(\log N)$。但在高维空间（$p > 20$）中，由于“空旷空间”现象，树的回溯会退化为近乎全遍历。
-
局部敏感哈希（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') = \langle \phi(x), \phi(x') \rangle$。即：不需要显式定义高维映射 $\phi$，只要知道高维空间里的内积怎么算就行。
}
2. 核光滑在哪里使用了内积？ (寻找 Inner Product)
这是一个非常深刻的误区。在Nadaraya-Watson 估计器这种纯粹的核光滑中，并没有直接使用希尔伯特空间的内积，它使用的是距离的度量（通常是欧氏距离的函数）。但是，当你深入到以下三个层面时，内积就会浮出水面：
A. 局部回归的投影视角
在进行局部多项式回归时，我们需要最小化加权损失函数。
{ 扩充部分：在底层实现 WLS（加权最小二乘）时，求解方程 $\hat{\beta} = (X^T W X)^{-1} X^T W y$。这里的 X^T X 项本质上就是样本特征向量之间的加权内积集。从几何上讲，这是将目标向量 y 投影到由特征列向量张起的子空间中，而“投影”这一线性代数操作的核心就是内积。}
B. 等价核 (Equivalent Kernels) 与 线性算子
我原本的内容：核函数在某一点附近主要依赖邻域数据。
{ 扩充部分：对于任何线性光滑器（如回归样条、局部线性回归），其预测值都可以写成 \hat{f} = Sy 的形式，其中 S 是光滑矩阵。S 的每一行可以看作是一个“等价核”。在泛函分析中，预测值 \hat{f}(x_0) 可以表示为观测值 y 与等价核函数在 L^2 空间下的内积：$\hat{f}(x_0) = \langle y, s(x_0, \cdot) \rangle = \int y(t)s(x_0, t)dt$。这是内积在函数空间层面的体现。}
C. 再生核希尔伯特空间 (RKHS) 的统一
这是两者关系的终极答案。
{ 扩充部分：根据 表征定理 (Representer Theorem)，许多正则化损失函数的解（包括某些形式的光滑插值）都可以写成核函数的线性组合：$f(x) = \sum \alpha_i K(x, x_i)$。
此时，核光滑中的“核”变身成了核方法中的“正定核”。当我们衡量函数复杂度（正则项）时，使用的是 RKHS 中的范数：$|f|_{\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 来加速核光滑计算的深层原因。