187 lines
18 KiB
Markdown
187 lines
18 KiB
Markdown
---
|
||
title: 6 第六章 核光滑方法
|
||
draft: false
|
||
tags:
|
||
- ESL
|
||
---
|
||
## [逻辑架构图]
|
||
|
||
本章知识的内在逻辑可以用一条“从局部直觉到高维结构，再到概率与计算权衡”的演进主线来概括：
|
||
|
||
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 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)$ 的穷举扫描，工业界不会使用朴素遍历，而是依赖空间划分数据结构：
|
||
|
||
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') = \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 来加速核光滑计算的深层原因。 |