Support Vector Machines & Kernels: 解释核技巧，为什么它能在不显式计算高维映射的情况下工作。

Core Concept: 对偶形式只依赖样本内积，用核函数直接算高维内积，避免显式映射。

核技巧的逻辑链：① SVM 的对偶问题中，目标函数与决策函数<strong>只通过内积 ⟨xᵢ,xⱼ⟩ 依赖数据</strong>；② 若把输入映射到高维空间 φ(x)，则只需把内积替换为 ⟨φ(xᵢ),φ(xⱼ)⟩；③ 若存在函数 K(xᵢ,xⱼ)=⟨φ(xᵢ),φ(xⱼ)⟩，则可<strong>直接用 K 计算而无需显式构造 φ</strong>——这就是核技巧。<strong>Mercer 定理</strong>保证：任何对称正半定的函数 K 都可表示为某个特征空间的内积。<strong>两个经典核</strong>：① <strong>多项式核</strong> K=(xᵀx'+c)^d 对应所有 d 阶以下单项式的特征空间（维度 O(nᵈ)，显式构造不可行）；② <strong>RBF/高斯核</strong> K=exp(−γ‖x−x'‖²) 对应<strong>无限维</strong>特征空间（可用泰勒展开验证），故显式映射根本不可能，只有核技巧能实现。

实践要点：① <strong>复杂度与维度无关</strong>——核 SVM 的计算复杂度只取决于<strong>样本数</strong>（O(n²–n³)），与特征维度无关；这是它在高维小样本（如基因数据 p≫n）上表现出色的原因。② <strong>RBF 核的 γ</strong>——控制单个样本影响范围：γ 大 → 影响范围小 → 决策边界复杂（过拟合）；γ 小 → 影响范围大 → 边界平滑（欠拟合）。γ 与 C 需联合调优（常用 2 的幂次网格）。③ <strong>核函数的构造</strong>——核可相加、相乘、与正系数组合仍为核（闭包性质），这允许领域知识注入（如字符串核、图核）。④ <strong>核方法的代价</strong>——需存储 n×n 核矩阵（O(n²) 内存）并做 QP 求解，故 n>10⁵ 时不可行；大规模场景改用线性 SVM（LIBLINEAR）、随机傅里叶特征（近似 RBF 核转为线性）、或 Nyström 近似。⑤ <strong>核与深度学习的对比</strong>——核方法是'固定特征 + 凸优化'，深度学习是'学习特征 + 非凸优化'；核方法在小样本、凸性、理论保证上有优势。