核技巧与 RBF

SVM 对偶问题的优化与预测只依赖样本内积 $x_i^Tx_j$。核技巧用核函数 $K(x, z) = \langle\phi(x), \phi(z)\rangle$ 直接计算高维 (甚至无穷维) 特征空间的内积, 而无需显式构造特征映射 $\phi$——只要 $K$ 是 Mercer 核 (对称半正定)。常用核: 线性核 $K = x^Tz$、多项式核 $K = (x^Tz + c)^d$、RBF 高斯核 $K(x, z) = \exp(-\gamma\Vert x - z\Vert^2)$, 其中带宽 $\gamma = \frac{1}{2\sigma^2}$: $\gamma$ 越大边界越复杂 (易过拟合), 越小越平滑 (易欠拟合)。核化后的决策面 $f(x) = \sum_{i \in SV} \alpha_i y_i K(x_i, x) + b$, 复杂度 $O(n_{SV} \cdot d)$, 与特征映射维度无关。

非线性可分数据的首选武器; 面试必问 RBF 的 $\gamma$/$\sigma$ 调参方向、核与特征映射的对应 (多项式核对应 $\binom{n+d}{d}$ 维映射, RBF 对应无穷维 RKHS)、核方法为何依赖数据量。

显式特征映射的维度随展开爆炸 (二次多项式映射是 $O(d^2)$ 维), 高次甚至无穷 (RBF 经泰勒展开 $e^{-\gamma\Vert x-z\Vert^2} = e^{-\gamma\Vert x\Vert^2} e^{-\gamma\Vert z\Vert^2} \sum_k \frac{(2\gamma x \cdot z)^k}{k!}$ 对应无穷维特征); 核函数把内积计算降回原始维度 $O(d)$, 让“线性 SVM + 核”获得非线性分类能力——训练只需 Gram 矩阵 $K_{ij} = K(x_i, x_j)$, 对偶与预测都只读内积/核值, 与特征维度解耦; 核的线性组合仍是核 (Mercer), 可自由设计领域核 (如文本的字符串核)。

推导 RBF 核是无穷维特征映射: 用泰勒展开 $e^{-\gamma\Vert x-z\Vert^2} = e^{-\gamma\Vert x\Vert^2} e^{-\gamma\Vert z\Vert^2} \sum_k \frac{(2\gamma x \cdot z)^k}{k!}$ 展开特征。

Mercer 定理: 合法核需要什么条件 (对称半正定), 哪些函数不是合法核? 证明核的线性组合/乘积仍是核。

推导多项式核 $K = (x^Tz + c)^d$ 对应的显式特征映射维度 (如 $\binom{n+d}{d}$), 说明核如何避免构造它。

RBF 调参: $\gamma$ (或 $\sigma$) 变大/变小的偏差-方差行为, 与 C 的配合, 欠/过拟合时各自往哪个方向调?

哪些算法可以核化 (只需内积/范数), 哪些不行? 线性核 vs RBF 在特征维度 $d$ 很大或 $n$ 很小时怎么选?