核方法（二）：数学基础——正定核与 Mercer 定理

写核 SVM 的第一周，我自信地造了一个相似度函数 tanh(1.5 * x.dot(y) - 2.0)：对称、有界、看起来一切都很正常。然后 sklearn 给我吐了一句 ValueError: kernel matrix is not positive semidefinite，模型效果比瞎猜还差。

那条报错背后藏着 20 世纪分析学最深的一组结果。“正定"不是个 checkbox，它是核技巧能存在的唯一理由。函数 PSD，就有一个希尔伯特空间装着它的内积；不 PSD，你就是在一个根本不存在的空间里假装做几何。这篇把这句话拆开讲透，建立可操作的检验流程，推导 Mercer 定理，并跑足够多的数值例子，让你下次再看到报错时一眼就能定位是哪一行数学被你违反了。

这篇按顺序讲三件事：合法核的定义与 Gram 矩阵实操判别，配上为何此检验正确的概要证明，以及五个常见核加一个反例的 Python 验证代码；Mercer 定理——把抽象正定性翻译成具体（可能无穷维的）特征映射，附 $[0, 1]$ 上 RBF 前三个特征函数的数值算例；核的代数——哪些操作能造新核，每条规则为何成立，以及哪些"看起来挺像"的函数其实根本不是核。

这是整个 series 里最数学化的一篇。第一遍读跳过证明也可以，每节末尾我都用 小结： 给出实操结论，每个理论命题后面都跟着可跑的代码。

什么样的函数才是合法核#

设 $\mathcal{X}$ 是任意集合——向量、字符串、图、图像都行。一个函数 $K: \mathcal{X} \times \mathcal{X} \to \mathbb{R}$ 称为合法核，要满足两条：

对称： $K(x, y) = K(y, x).$

严格来讲 $\geq 0$ 定义的是半正定（PSD），但文献里一般把它直接叫"正定”，因为严格 $>$ 的情况实际很少遇到。本文跟随这个松散约定。

直觉值得讲清楚。核是个相似度函数，它得"像内积一样"在多个点上同时立得住。把 $c_i$ 想成点 $x_i$ 的权重，$\sum_i c_i \Phi(x_i)$ 是特征向量的加权和。双重和 $\sum_{ij} c_i c_j K(x_i, x_j)$ 就是特征空间中 $\|\sum_i c_i \Phi(x_i)\|^2.$ PSD 正是要求这个范数的平方非负——几何上，长度不能是虚数。

两项都是实数平方，各自非负。对称性直接由公式可见。这个核也是 Mercer 核，显式特征映射 $\Phi(x) = (x, 1) \in \mathbb{R}^2$ ：验证 $\Phi(x)^\top \Phi(y) = xy + 1$ 完全匹配。同样的技巧——把双重和写成平方和——处理所有多项式核，只是次数高了代数项数变多。

为什么单有对称还不够。 对称是必要条件，免费送的：内积都是对称的，所以不对称直接淘汰。但很多对称函数过不了 PSD 这关。最经典的陷阱就是 cos(distance)：对称、有界，看着很顺眼，不是核。等下你会在图里看到它的 Gram 矩阵长什么样。

Bochner 定理——一段插话。 对平移不变候选 $K(x, y) = k(x - y),$ Bochner 定理给出干净的谱刻画：$k$ 合法 当且仅当 它的傅里叶变换是非负测度。RBF 能 work 是因为它的傅里叶变换是高斯（非负密度）；cosine-of-distance 不行是因为它的傅里叶变换是 delta 峰的有符号组合。后面陷阱小节会回到 Bochner。

小结： “对称 + PSD"是入场券。两条都过，是核；任意一条不过，不是——不管你的函数看起来多合理。

Gram 矩阵：正定性的实操判别#

PSD 的抽象定义没人会徒手验证。实际中我们检查Gram 矩阵。

对称函数 $K$ 是正定核当且仅当它生成的每个 Gram 矩阵——任意 $n,$ 任意点选择——都是 PSD 矩阵。这个"任意"是抽象定义的力量来源；实操上抽几个数据集查一下就够了。

判断对称矩阵 $G$ 是否 PSD 有三种等价方法，按"教学清晰"到"代码最快"排：

特征值检验： $G$ 的所有特征值非负，$\lambda_i(G) \geq 0.$ np.linalg.eigvalsh 一行就出，$O(n^3),$ 常数中等。

二次型检验： 对任意 $v \in \mathbb{R}^n,$ $v^\top G v \geq 0.$ 理论上等价，代码上完全没法用（$v$ 不可数），主要在证明里出现。

Cholesky 检验： 分解 $G = LL^\top$ （$L$ 下三角实矩阵）成功。生产代码用这条——$O(n^3)$ 小常数（约 $\tfrac{1}{3} n^3$ flops，特征分解的一半），遇到不定矩阵立刻失败。

三种为何等价。 对称矩阵有谱分解 $G = U \Lambda U^\top,$ $U$ 正交，$\Lambda = \text{diag}(\lambda_i).$ 那么 $v^\top G v = (U^\top v)^\top \Lambda (U^\top v) = \sum_i \lambda_i w_i^2,$ $w = U^\top v.$ 这对所有 $v$ 非负，当且仅当所有 $\lambda_i$ 非负。Cholesky 算法按列计算 $L_{jj} = \sqrt{G_{jj} - \sum_{k < j} L_{jk}^2}$ ；根号下出现负数就是失败信号，恰好对应不定性。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

import numpy as np

def is_psd(G, tol=1e-8):
    """三种检查，从宽松到严格。"""
    if not np.allclose(G, G.T, atol=tol):
        return False, "not symmetric"
    try:
        np.linalg.cholesky(G + tol * np.eye(len(G)))
        return True, "cholesky succeeded"
    except np.linalg.LinAlgError:
        eig_min = np.linalg.eigvalsh(G).min()
        return False, f"min eigenvalue = {eig_min:+.3e}"


def gram(K_fn, X):
    n = len(X)
    G = np.empty((n, n))
    for i in range(n):
        for j in range(n):
            G[i, j] = K_fn(X[i], X[j])
    return G


rng = np.random.default_rng(0)
X = rng.normal(size=(30, 2))

kernels = {
    "linear":     lambda x, y: x @ y,
    "poly d=3":   lambda x, y: (x @ y + 1.0) ** 3,
    "rbf g=0.5":  lambda x, y: np.exp(-0.5 * np.sum((x - y) ** 2)),
    "laplace":    lambda x, y: np.exp(-0.5 * np.sum(np.abs(x - y))),
    "cosine":     lambda x, y: (x @ y) / (np.linalg.norm(x) * np.linalg.norm(y) + 1e-12),
    # 反例：距离的 cos——对称、有界，但 NOT PSD。
    "cos(2*d)":   lambda x, y: np.cos(2.0 * np.linalg.norm(x - y)),
}

for name, K in kernels.items():
    G = gram(K, X)
    print(f"{name:10s} -> {is_psd(G)}")

跑出来前五个核 True，cos(2*d) False 且最小特征值显著为负（这组数据下约 $-3$ ）。注意：这个检验不能证明核一般 PSD，只能证明某一个数据集上失败。证明一般 PSD 需要上面 $xy + 1$ 那种解析论证（或引用 Bochner）；证否只需一个反例 Gram 矩阵。

看右边那张图。矩阵是对称的、光滑的、有界的，肉眼看起来不比左边糟。但它的最小特征值明显是负的，意味着存在某个 $v$ 使得 $v^\top G v < 0.$ 这种 $v$ 对应的样本"自相似度是负的”——几何上完全说不通。

浮点容忍。 实际中 $-10^{-12}$ 这种小负特征值通常是浮点舍入，不是真不定。多数库会先加个 $\epsilon I$ 抖动再做分解；上面代码里 tol=1e-8 是常见默认值。GP 库里常见的 jitter 是对角加 $10^{-6},$ 大到能盖住浮点噪声，小到不会偏置后验。

复杂度表。 SVM 上规模时每次迭代都要碰 Gram 矩阵。代价表如下：

小结： Gram 矩阵既是 PSD 实操检验，也是计算瓶颈。搞对很重要；保持小更重要。

插话——对角线作为自相似先验。 PSD 强制 $G_{ii} = K(x_i, x_i) \geq 0,$ 因为 $n = 1, c = 1$ 单点情形直接给出 $K(x, x) \geq 0.$ 更强：对隐式特征映射用 Cauchy–Schwarz 得 $|K(x, y)| \leq \sqrt{K(x, x) K(y, y)}.$ 这就是"归一化核" $\tilde K(x, y) = K(x, y) / \sqrt{K(x, x) K(y, y)}$ 总落在 $[-1, 1]$ 且像特征空间余弦相似度的原因。余弦相似度本身就是归一化的线性核，是这一构造的特例。

Mercer 定理：陈述与直觉#

一旦接受 PSD 是对的条件，自然下一个问题是：那个隐式特征映射到底长什么样？ Mercer 定理就是答案。

级数在 $\mathcal{X} \times \mathcal{X}$ 上绝对一致收敛。

的特征值-特征函数对，即 $T_K \phi_k = \lambda_k \phi_k.$

这是"对称 PSD 矩阵有谱分解 $G = \sum_k \lambda_k u_k u_k^\top$ “在连续情形下的完整对偶。积分算子 $T_K$ 是矩阵；特征函数是特征向量；谱不再是有限列表而是无穷（但衰减的）序列。

证明概要（分步走）： 四步，每步都是标准动作。

(1) $T_K$ 紧。 $K$ 在紧集上连续故有界，所以 $K \in L^2(\mathcal{X} \times \mathcal{X}).$ 形如 $T_K f(x) = \int K(x,y) f(y) dy$ 且 $K \in L^2$ 的算子叫 Hilbert–Schmidt, 而 Hilbert–Schmidt 算子是紧的（单位球映射到 $L^2$ 的预紧集）。

(2) 自伴。 $K$ 对称故 $\langle T_K f, g \rangle = \int\!\!\int K(x,y) f(y) g(x) dy dx = \langle f, T_K g\rangle,$ 即 $T_K = T_K^*.$

(3) 谱定理。 Hilbert 空间上紧自伴算子的谱定理给出完整的正交特征基 $\{\phi_k\} \subset L^2(\mathcal{X})$ 和实特征值 $\{\lambda_k\},$ 后者只能聚于 $0$ （$\lambda_k \to 0$ ）。

(4) 非负与一致收敛。 $K$ 正定意味着 $\langle T_K \phi_k, \phi_k\rangle = \lambda_k \geq 0.$ 在特征基里展开 $K$ 得 $K(x, y) = \sum_k \lambda_k \phi_k(x) \phi_k(y),$ 这是 $L^2$ 收敛。Mercer 的连续性假设把它升级为一致收敛——最后这一步是 Mercer 1909 年原文最技术的部分，也是定理冠他名字的原因。

所以核技巧不是魔术。是真有一个希尔伯特空间 $\mathcal{H} = \ell^2$ 和映射 $\Phi$ 满足 $K = \langle \Phi(\cdot), \Phi(\cdot)\rangle.$ Mercer 只是告诉你 $\Phi$ 长什么样。

详解范例——$[0, 1]$ 上 RBF 前三个特征函数。 RBF 核 $K(x, y) = \exp(-\gamma(x - y)^2)$ 在 $[0, 1]$ 上没有闭式特征函数，但可以把积分算子离散化到网格上数值求解。流程：取 $m = 200$ 等距点 $x_i \in [0, 1],$ 构 $m \times m$ 矩阵 $G_{ij} = K(x_i, x_j) / m$ （$1/m$ 是积分权重），算它的前几个特征值和特征向量。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

import numpy as np

m, gamma = 200, 25.0
xs = np.linspace(0, 1, m)
K = np.exp(-gamma * (xs[:, None] - xs[None, :]) ** 2) / m
w, V = np.linalg.eigh(K)
order = np.argsort(w)[::-1]
w, V = w[order], V[:, order]

# 前 3 个特征值与归一化特征函数样本。
for k in range(3):
    phi_k = V[:, k] * np.sqrt(m)        # 在 [0, 1] 上 L^2 归一化
    sign = np.sign(phi_k[m // 2]) or 1  # 固定符号约定
    phi_k *= sign
    print(f"lambda_{k+1} = {w[k]:.4f}, phi_{k+1}(0.5) = {phi_k[m // 2]:+.3f}")

$\gamma = 25$ 下大致得到 $\lambda_1 \approx 0.18,$ $\lambda_2 \approx 0.18,$ $\lambda_3 \approx 0.13.$ 第一个特征函数是单峰正值，第二个有一次振荡（一次过零），第三个有两次过零。规律延续：第 $k$ 个特征函数在 $[0, 1]$ 上约有 $k - 1$ 个零点。这就是核版本的傅里叶模式，也正是 fig 3 在对称区间 $[-3, 3]$ 上可视化的内容。

完整性验证。 用前 $r$ 个特征对重建 $K$ 并测残差 $\|K - \sum_{k=1}^{r} \lambda_k \phi_k \phi_k^\top\|_F,$ $r$ 增大时残差应快速下降。$\gamma = 25, r = 30$ 时，相对 $\|K\|_F$ 的 Frobenius 残差已低于 $10^{-6}.$ 这是 Mercer 级数对 RBF 收敛快的实证。

与特征空间 PCA 的桥。 Mercer 特征对正是隐式特征映射 $\Phi$ 之后（中心化）数据的主成分。更精确：$n$ 点上的经验 kernel PCA 算的是中心化 Gram 矩阵 $\tilde G = (I - \tfrac{1}{n} \mathbf{1}\mathbf{1}^\top) G (I - \tfrac{1}{n} \mathbf{1}\mathbf{1}^\top)$ 的特征向量，它的特征值是 Mercer 特征值 $\lambda_k$ 乘 $n$ 的有限样本估计。$n \to \infty$ 时收敛速率 $O(1/\sqrt{n}).$ 这就是 kernel PCA 不必实例化 $\Phi$ 就能"直接工作"的原因——Gram 矩阵已经把 PCA 需要的信息打包成了无穷维真相的有限维子矩阵。

堆起来，$G = \Phi_n \Lambda \Phi_n^\top,$ $\Phi_n \in \mathbb{R}^{n \times \infty},$ $(\Phi_n)_{ik} = \phi_k(x_i),$ $\Lambda$ 对角。$G$ 的前几个特征向量正是前几个 Mercer 特征函数在数据点上的加权采样。上面 $n = m = 200$ 网格点的数值算例就是在干这件事，唯一近似是把积分换成黎曼和。

Mercer 定理的几何含义#

看下面这张图。它画的是 RBF 核在 $[-3, 3]$ 上前五个 Mercer 特征函数。

三件事值得刻进脑子：

特征函数像越来越振荡的光滑波包。 这是核版本的傅里叶模式。第 $k$ 个特征函数 $\phi_k$ 大约有 $k$ 个零点，对应越来越细的空间尺度。核同时"看到"所有这些尺度的相似度，谱告诉你每个尺度贡献多少。

特征值衰减得很快。 RBF 是指数衰减。这就是低秩近似为什么 work——保留前 $r$ 个 Mercer 分量就抓住了核几乎全部的结构。Nystrom、Random Fourier Features 这些方法显式利用这个衰减来便宜地近似 $\Phi.$ 相关理论结论：$\mathbb{R}^d$ 上带宽 $\sigma$ 的高斯核在亚高斯分布数据上，$\lambda_k$ 大约按 $\exp(-c k^{1/d})$ 衰减——按维度修正后的指数下降。

谱真的是无穷的。 对 RBF，每个 $\lambda_k$ 都严格大于 $0$ ——隐式特征空间真无穷维。听起来吓人，但快速衰减意味着只有头十几个维度承载有意义的"信号能量”。你拿到了无穷空间的表达力，却只付出小空间的有效复杂度。这就是"RBF 能拟合一切但不必动用一切"这句口号的形式版本。

和多项式核的对比。 对 $K(x,y) = (x^\top y + 1)^d$ （$x \in \mathbb{R}^p$ ），Mercer 展开是有限的：恰好有 $\binom{p+d}{d}$ 个非零特征值，每个对应一个 $\leq d$ 次单项式。特征函数就是单项式本身。所以多项式核确实给的是暴力多项式特征展开，Mercer 只是把它"官方化"了。

与 Bochner 和傅里叶的桥。 对平稳核 $K(x, y) = k(x - y),$ Bochner 定理给出另一种谱表示：$K(x, y) = \int e^{i \omega^\top (x - y)} d\mu(\omega),$ $\mu$ 非负测度。这与 Mercer 在精确意义上是对偶的：Mercer 给的是离散谱，绑定到支撑集 $\mathcal{X};$ Bochner 给的是连续谱，活在频率域 $\mathbb{R}^d$ 上。Random Fourier Features 把 Bochner 积分提升为蒙特卡洛近似：采样 $\omega_j \sim \mu$ 后用随机特征映射 $\Phi(x) = (\cos(\omega_j^\top x), \sin(\omega_j^\top x))_j.$ 这是把任意平稳核变成有限维特征映射、且不必算特征函数的桥。

小结： PSD 是抽象条件；Mercer 把它翻译成具体（常常无穷，永远正交）的特征展开。$\{\lambda_k\}$ 衰减速度控制"有效维度"，也是 Nystrom 和 Random Fourier Features 共同撬动的杠杆。

用图看正定性#

有时候内化"正定"最好的方式是看二次型。下图把 $Q(v) = v^\top G v$ 画在 $v$ 的 2-D 切片上，左右分别是 PSD 和不定的 $3 \times 3$ Gram-like 矩阵。

左边是个完全在零之上的碗——PSD 的几何含义就是这样：每个方向 $v$ 都给出非负值。右边是个鞍面，在一整个半平面里都掉到零以下（红色等值线是零等高线）。这个穿越零面就是"负特征值"的几何意义。

把不定 Gram 矩阵喂给 SVM solver，优化器就会朝那个负的区域走——因为对偶目标长得像 $-\tfrac{1}{2} v^\top G v + \text{线性},$ 而最小化一个凹二次（带约束）要么跑到无穷，要么停在毫无意义的角点。$G$ PSD，二次部分有下界（或上界，看符号约定），对偶是正常凸问题；$G$ 不定，目标在错方向无界，solver 要么发散、要么报错、要么返回鬼东西。这就是 kernel matrix is not positive semidefinite 报错的真实含义。

碗-鞍面图为什么够用。 三维以上画不出来，但定性二分不变。实对称矩阵要么 PSD（每个方向非负），要么负半定（每个方向非正），要么不定（有正有负）。不定是核的唯一失败模式——负半定 Gram 矩阵实际不会出现，因为 $G_{ii} = K(x_i, x_i) \geq 0$ 对任何合理相似度都成立，强制至少一个非负特征值。

五大核的特征值谱#

下图把五种常见核在同样的 120 个 $[-3, 3]$ 点上的特征值衰减（log 尺度）画在一起。

几个关键读数：

Linear 一步衰完：秩 $= \min(n, d) = 1$ （这里 $X$ 是一维）。$\lambda_1$ 之外全是数值噪声。

Polynomial (d=3) 秩恰好 $4$ ——四个单项式 $1, x, x^2, x^3$ ——之后断崖到数值零。

RBF $(\gamma = 0.5)$ 平滑慢衰：多个分量都有意义。这是"无穷维但可压缩"的视觉标志。

RBF $(\gamma = 2.0)$ 比 $\gamma = 0.5$ 慢得多——$\gamma$ 大 ⇒ 波包窄 ⇒ 细节多 ⇒ 特征空间更丰富 ⇒ 谱衰减更慢。这是 bias-variance 的谱版本：大 $\gamma$ 买表达力，花泛化预算。

Laplace 介于 RBF 和多项式之间：$\lambda_k \sim k^{-2}$ 幂律而非指数。所以 Laplace 处理非光滑信号比 RBF 好——它有更大的"高频预算"，因为幂律尾比指数尾在高 $k$ 模式上放更多质量。

汇总表：

这一张图浓缩了核选择的大部分实操直觉。衰减越快 = 隐式特征空间越简单 = 模型容量越低 = 越难过拟合。Part 5 调带宽时还会回来再看。

它数的是"在所选正则化水平下，有多少 Mercer 模真正参与"。光滑数据上的 RBF，$d_{\text{eff}}$ 小且随 $1/\mu$ 对数增长；Laplace 则按 $\mu^{-1/2}$ 增长。核岭回归的泛化界是 $O(d_{\text{eff}} / n),$ 所以谱直接控制统计风险。Part 4 详推这条界。

算子范数与迹。 核理论里反复出现的两个标量：

• $\|T_K\|_{\text{op}} = \lambda_1$ （最大特征值），界定核对任意输入函数的最大放大率。
• $\text{tr}(T_K) = \sum_k \lambda_k = \int_{\mathcal{X}} K(x, x) dx$ （迹），度量隐式特征映射的总"能量"。

RBF 带宽 $\sigma$ 在体积 $V$ 的有界域上：$\text{tr}(T_K) = V$ （$K(x, x) = 1$ ）。多项式 $(x^\top y + c)^d$ 在 $[-1, 1]^p$ 上：迹 $= \int (\|x\|^2 + c)^d dx,$ 按 $(p + c)^d$ 增长。迹-秩权衡正是核版本的神经网络宽度-深度权衡。

核的组合规则#

你几乎不会从头写核。实际是用一小套保 PSD 的运算把简单核组合起来。记住这些规则，就能给结构化数据设计自定义核，不必每次都重证 PSD。

规则 1（和）： $K_1, K_2$ 都是核，则 $K_1 + K_2$ 是核。

证明概要： $v^\top (G_1 + G_2) v = v^\top G_1 v + v^\top G_2 v \geq 0.$ 每项假设非负，和自然非负。

反例警示： $K_1 - K_2$ 一般不是核。快速验证：$K_1 = K_{\text{linear}},$ $K_2 = 2 K_{\text{linear}}.$ 那 $K_1 - K_2 = -K_{\text{linear}},$ Gram 矩阵 $-X X^\top$ 严格负半定，绝非 PSD（除非 $X = 0$ ）。

规则 2（正标量倍数）： $K$ 是核，$c \geq 0,$ 则 $cK$ 是核。证明一行：$v^\top (cG) v = c (v^\top G v) \geq 0.$ 负标量破坏 PSD，理由同减法。

规则 3（Hadamard 积）： $K_1, K_2$ 都是核，则逐点积 $(K_1 K_2)(x, y) = K_1(x,y) K_2(x, y)$ 是核。这是 Schur 积定理：两个 PSD 矩阵的逐元素积是 PSD。证明用 $G_1 \otimes G_2$ （Kronecker 积）在两因子都 PSD 时 PSD，而 $G_1 \odot G_2$ （Hadamard）是 $G_1 \otimes G_2$ 的主子矩阵。证明不平凡，威力极大。

规则 4（张量积 / 积空间）： $K_1$ 是 $\mathcal{X}_1$ 上核，$K_2$ 是 $\mathcal{X}_2$ 上核，则 $K\big((x_1, x_2), (y_1, y_2)\big) = K_1(x_1, y_1) K_2(x_2, y_2)$ 是 $\mathcal{X}_1 \times \mathcal{X}_2$ 上核。这是混合数据类型（数值 + 类别）的标准玩法。特征空间是张量积 $\mathcal{H}_1 \otimes \mathcal{H}_2.$

规则 5（与 $\phi$ 复合）： $f: \mathcal{X} \to \mathcal{Z}$ 任意映射，$K_Z$ 是 $\mathcal{Z}$ 上核，则 $K(x, y) = K_Z(f(x), f(y))$ 是 $\mathcal{X}$ 上核。证明 trivial：$K$ 的任意 Gram 矩阵也是 $K_Z$ 在像点 $\{f(x_i)\}$ 上的 Gram 矩阵，故 PSD。这条规则让你为字符串、图等非向量数据造核：选个特征提取器 $f$ 就能 lift 任意向量核。

规则 6（极限与无穷和）： 核的逐点极限（存在时）是核。所以非负系数的收敛幂级数作用于核仍是核——特别地 $\exp(K)$ 总是核，$(1 - K)^{-1}$ （在收敛区）也是核，任何 $\sum_k a_k K^k$ （$a_k \geq 0$ ）也是。

上图对同一 RBF 和 $d=2$ 多项式核应用了六种运算。每张得到的 Gram 矩阵最小特征值都是正的（标题里写得很清楚）。代数封闭性活生生看在眼里。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

# 给 (numeric, categorical) 数据对造一个自定义核。
def K_numeric(x_num, y_num, gamma=0.5):
    return np.exp(-gamma * np.sum((x_num - y_num) ** 2))

def K_categorical(x_cat, y_cat):
    return float(x_cat == y_cat)        # Kronecker delta —— 合法核

def K_combined(p, q):
    # 规则 4：积空间张量积
    return K_numeric(p[0], q[0]) * K_categorical(p[1], q[1])

# 减法反例的数值验证。
X = np.random.default_rng(0).normal(size=(20, 2))
K1 = X @ X.T                            # 线性核 Gram
K2 = 2 * (X @ X.T)                      # 2 倍线性核 Gram
diff = K1 - K2                          # = -线性，不该 PSD
print("min eig of K1 - K2:", np.linalg.eigvalsh(diff).min())   # 负

这十几行按规则 4 就是个完整的 Mercer 核，你不需要推它的特征函数就能用。底下减法检查实证了"每条规则都有它没声明那侧的反例"：能加不能减，能乘正不能乘负。

小结： 和、（正）标量、积、张量、复合、exp。六条规则，自由组合。减法和负标量自负其责。

用规则 5 设计字符串核——具体例子。 想比较 DNA 序列。选 $k$ -mer 特征提取器：$f(s) \in \mathbb{R}^{4^k}$ 数 $s$ 中每个长度 $k$ 的子串出现次数。然后规则 5 给出 $K(s, t) = K_Z(f(s), f(t))$ 是字符串上的合法核，$K_Z$ 任意向量核。最常见选择 $K_Z(u, v) = u^\top v$ （线性），得"spectrum kernel" $K(s, t) = \sum_{w \in \Sigma^k} \#_w(s) \cdot \#_w(t).$ $k = 4,$ 字母表 4，显式特征空间 256 维；用后缀树 $O(|s| + |t|)$ 算核，比实例化两个特征向量便宜得多。这个套路——选有组合结构的特征提取器、规则 5 lift、利用结构加速计算——是 2000 年代每篇 “X 上的核” 论文的模板。

哪些函数不是核——三个经典陷阱#

知道什么会失败，能让你更清楚什么能通过。三个常见"看起来像但不是核"的函数，每个配数值证据：

陷阱 1：sigmoid 核 $\tanh(\alpha x^\top y + c).$ 老式神经网络风 SVM 里很有名。它只在很窄一段 $(\alpha, c)$ 参数下 PSD——而且只在有界输入区上。多数参数选择下，Gram 矩阵有负特征值。

上图右边那张是 $\alpha = 1.5, c = -2.0$ 的结果：一半以上特征值是负的。sklearn 会照单全收并产出"模型"，但优化在数学上毫无意义。现代代码默认 RBF 而不是 sigmoid，就是这个原因。

1
2
3
4
5

# 数值证据：典型参数下 sigmoid 核失败 PSD。
rng = np.random.default_rng(1)
X = rng.normal(size=(50, 5))
G_sig_bad = np.tanh(1.5 * X @ X.T - 2.0)
print("sigmoid min eig:", np.linalg.eigvalsh(G_sig_bad).min())   # 负

陷阱 2：距离函数 $K(x, y) = d(x, y).$ 欧式距离是对称的、感觉很像相似度，但不是核——对角是 $0,$ 非对角是正的，对常向量 $\mathbf{1}$ 有 $\mathbf{1}^\top G \mathbf{1} = \sum_{ij} d(x_i, x_j) > 0$ 但特征值检验失败。距离的高斯函数 $K(x,y) = \exp(-\gamma d(x,y)^2)$ 才是核，这也是 RBF 那么造的原因。

1
2
3

# 距离不是核。
D = np.linalg.norm(X[:, None] - X[None, :], axis=-1)
print("distance min eig:", np.linalg.eigvalsh(D).min())          # 负

陷阱 3：$K(x, y) = \cos(\alpha \cdot d(x, y)).$ 对称、有界、看起来像广义相似度。不是核：fig 1 右图就是它，Gram 矩阵有大量负特征值。振荡破坏正定性，因为 $\cos(\alpha r)$ 的傅里叶变换是一对有符号 delta 峰，违反 Bochner 条件。

Bochner 救生圈。 对平移不变候选核 $K(x, y) = k(x - y),$ Bochner 定理告诉你：$k$ 是合法核 当且仅当 它的傅里叶变换是非负测度。RBF 能 work 是因为它的傅里叶变换是高斯（非负）；$\cos(\alpha \|x - y\|)$ 不行是因为它的傅里叶变换是两个 delta 峰之差——有正有负。要自己设计平稳核，就在傅里叶域设计：先选个非负谱密度，再做逆傅里叶得到 $k.$ Matern 族正是按这个模板设计的。

30 秒证明五大经典核#

收尾，这五个最常用的核为什么 PSD：

Linear： $K(x, y) = x^\top y.$ Gram 矩阵就是 $X X^\top,$ 任意 $A^\top A$ 都 PSD（$v^\top A^\top A v = \|Av\|^2 \geq 0$ ）。秩 $\min(n, d).$ 高维稀疏数据通常这就够；现代用 TF-IDF 的文本分类器默认是线性核 SVM。

Polynomial： $K(x, y) = (x^\top y + c)^d$ （$c \geq 0, d \in \mathbb{N}$ ）。$\binom{p+d}{d}$ 个秩 1 PSD 矩阵之和，每个对应一个单项式（多项式展开）。或者直接对线性核套规则 1、2、3、6：$K_{\text{linear}} + c$ 是 PSD（常数核 $c \cdot \mathbf{1}\mathbf{1}^\top$ 是秩 1 PSD），核的整数次方是迭代 Hadamard，规则 3 保 PSD。

RBF / 高斯： $K(x, y) = \exp(-\gamma \|x - y\|^2).$ Bochner + 高斯傅里叶变换；或者规则 6，把 $\exp$ 展为（负的）平方距离的幂级数，每项 PSD 性用上面多项式核的分解验证。

Laplace： $K(x, y) = \exp(-\gamma \|x - y\|_1).$ Bochner + 柯西分布傅里叶变换——非负，故 PSD。Laplace 的谱密度在 $L^1$ 而非 $L^2,$ 这正是前面看到 $\lambda_k$ 幂律衰减的原因。等价地说，Laplace 核是高斯-柯西卷积；柯西谱的重尾决定 $k$ 域 $\lambda_k$ 的重尾。

Sigmoid： 一般情况下不是 PSD（见陷阱 1）。挂着"核"名字是历史原因，能用 RBF 就别用它。$\tanh(\alpha x^\top y + c) = \tanh \circ K_{\text{linear, shifted}}$ 这个关系不能调规则 5，因为规则 5 是把输入和函数 $f$ 复合，不是把输出和符号交替级数（$\tanh = x - x^3/3 + \dots$ ）复合。

实际中的数值复杂度#

PSD 机制直接影响运行时。各操作的代价与主导阶段：

我们一直在讲的特征值谱正是让最后两行可能的关键：$\lambda_k$ 衰减快，$m \ll n$ 的低秩近似就能基本捕获整个核。Part 7 会用这一点把 RBF SVM 从 $10^4$ 推到 $10^7$ 点。

与神经网络的桥——一段话。 宽神经网络的"神经正切核"（NTK）是 Mercer 核，特征函数是单位球 $S^{d-1}$ 上的球谐函数，特征值按谐波指标幂律衰减。宽网络在"惰性区"训练——每个权重移动 $O(1/\sqrt{\text{width}})$ ——正是当代关心核理论（超越经典 SVM）的理由。NTK 特征值衰减控制梯度下降拟合目标函数各频率分量的速度，所以低频目标先被学到（“谱偏置"现象）。本文所有结论都适用，只需把 $\Phi$ 换成初始化时网络的梯度。

三个真实场景——PSD 在生产中的失败#

把理论锚到实例上，三个我亲自踩过的 PSD 失败模式与 Mercer 视角的诊断：

Case A——sigmoid SVM，金融时序，2018。 tanh-核 SVM 在滚动窗口收益上训练，交叉验证各 fold AUC 离奇震荡。诊断：对偶非凸，Gram 矩阵 250 个特征值里 8 个负。SMO solver 返回的局部极小取决于随机初始化。修复：换 RBF，AUC 稳定，训练时间砍半。教训：solver 不稳定且收紧容忍度无效时，必特征分解 Gram 矩阵。

Case B——序列核，NLP 关系抽取，2020。 子树计数和构造的"树核"在长句上 PSD 失败。诊断：实现少了 bag-of-subtrees 内积中的平方，实际算的是 $\sum_t \#_t(s) - \sum_t \#_t(t)$ 而非 $\sum_t \#_t(s) \cdot \#_t(t).$ Gram 矩阵项是无符号的计数差，不是相似度。修复：一行补丁把核改回正规规则 5 lift。教训：写自定义核时，把显式特征映射写在核旁边，三个小例上验证 $K(x, y) = \Phi(x)^\top \Phi(y).$

Case C——Nystrom 近似，图像特征，2021。 Nystrom 近似的 RBF SVM 在 CIFAR-10 上正常，在 STL-96 上炸 LinAlgError: leading minor not positive definite。诊断：$m = 500$ Nystrom landmarks 加 96 维特征，Nystrom 核矩阵 $\hat K_{mm}$ 秩缺，因为多个 landmark 几乎重复。数值上 $\hat K$ 有若干 $10^{-14}$ 量级特征值，低于 jitter 容忍。修复：jitter 提到 $10^{-5}$ 并用最远点采样去重 landmark。教训：低秩近似只在近似条件好时保 PSD；jitter 慷慨给。

横向教训。 三个失败都是同一个底层事实的不同表层症状：优化器假设 PSD Gram 矩阵，实际拿到符号不定的。修复总是"用真正 PSD 的核"或"数值上把 Gram 正则化到 PSD”。懂 Mercer 故事告诉你该调哪个旋钮。

对照表——核一览#

紧急场合选核的一屏总结：

“PSD 论证"列对理论工作最关键——它告诉你哪条 Mercer / Bochner / 封闭规则保证合法性。“谱"列控制有效维度，从而控制 Parts 4 和 5 讲的泛化行为。

详解范例——2 次多项式核的 Mercer 展开#

$\sqrt{2}$ 因子在那里是因为展开点积时交叉项被算两次。验证：$\Phi(x)^\top \Phi(y) = x_1^2 y_1^2 + x_2^2 y_2^2 + 2 x_1 x_2 y_1 y_2 + 2 x_1 y_1 + 2 x_2 y_2 + 1,$ 与 $K$ 完全匹配。

此情形下 Mercer 特征函数是六个归一化单项式 $\{1, x_1, x_2, x_1^2, x_2^2, x_1 x_2\}$ （差一个 $\mathcal{X}$ 上测度的缩放）；特征值是系数 $\{1, 2, 2, 1, 1, 2\}.$ 这复现了多项式秩公式预测的 $\binom{2 + 2}{2} = 6.$ $\mathbb{R}^p$ 上 $d$ 次的同样构造给出 $\binom{p + d}{d}$ 维显式特征映射；$p = 100, d = 4$ 时是 400 多万特征——这正是大家用核技巧而不实例化 $\Phi$ 的原因。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

import numpy as np
from itertools import combinations_with_replacement

def poly_feature_map(x, d):
    """(x^T y + 1)^d 核在 R^p 上的显式特征映射。"""
    p = len(x)
    feats = []
    for k in range(d + 1):
        for idx in combinations_with_replacement(range(p), k):
            # 多项式系数确保 K_explicit 与核匹配
            from math import factorial
            counts = np.bincount(idx, minlength=p)
            coef = factorial(d) / (factorial(d - k) * np.prod([factorial(c) for c in counts]))
            feats.append(np.sqrt(coef) * np.prod([x[i] for i in idx]))
    return np.array(feats)

x = np.array([0.7, -0.3])
y = np.array([1.1,  0.4])
K_direct = (x @ y + 1) ** 2
K_explicit = poly_feature_map(x, 2) @ poly_feature_map(y, 2)
print(K_direct, K_explicit)            # 应在浮点精度内相同

这是隐式特征映射有限、可以写全的少见情形。RBF 同样的练习不可能——特征映射有无穷多分量，只能退回 Nystrom 或随机特征近似。

FAQ——学生总会问的几个问题#

Q：既然正定是条件，为什么教材有时讲"条件正定（CPD）"？ A：CPD 把 PSD 条件松弛为只对 $\sum_i c_i = 0$ 的权重 $c$ 成立。很多距离类函数如 $-\|x - y\|^2$ 是 CPD 但不 PSD。Krein 空间 SVM、“不定核学习"在这个松弛设定里 work。初步直觉先把 CPD 当脚注；99% 的核文献用的是 PSD。

Q：我的 Gram 矩阵 $\lambda_{\min} = -10^{-13}.$ 核坏了吗？ A：几乎不是。这个数低于 float64 相对精度。加 $\epsilon I$ 抖动，$\epsilon \sim 10^{-6},$ 走人。$\lambda_{\min}$ 大于 $-10^{-8} \cdot \|G\|_2$ 就算"浮点意义下 PSD”，实操可当 PSD 处理。

Q：是不是任何对称函数加大的 $\lambda I$ 就能变核？ A：能——叫"核岭正则化"或"谱裁剪”，永远可行。代价是你改了核：新函数 $K'(x, y) = K(x, y) + \lambda \mathbb{1}[x = y]$ 一般没有自然解释。还是选构造上就 PSD 的核更好。

Q：Mercer 定理需要 $\mathcal{X}$ 紧吗？ A：经典版本需要。非紧域有推广（Mercer–Hilbert–Schmidt，关于概率测度的积分算子），在核平方可积时给出类似的谱分解。实操上限到一个紧包络盒里没问题。

Q：PSD 与特征缩放怎么交互？ A：特征缩放 $x \to D x$ （$D$ 对角）相当于把核从 $K(x, y)$ 改为 $K(Dx, Dy).$ 规则 5 保 PSD。所以特征缩放对核总是安全的——但改变了有效带宽，重缩放后要重新 CV $\gamma.$

Q：为什么 GP 库总有 jitter 或 noise 项？ A：就是上面讲的 $\epsilon I$ 抖动，包装成超参数。GP 里有"观测噪声方差"的贝叶斯解释，操作意义相同：阻止 Cholesky 在近奇异 Gram 矩阵上失败。

Q：SVM 收敛了但 held-out 分数很差，可能是核的锅吗？ A：按顺序查三件事。一，在小子样本上特征分解 Gram 矩阵看 $\lambda_{\min}.$ 显著为负说明核不定，收敛"解"是对偶的鞍点。二，看条件数 $\kappa(G) = \lambda_{\max} / \lambda_{\min}.$ $\kappa > 10^{10}$ solver 在跟数值噪声搏斗；加 jitter 或归一化特征。三，画谱：若除一个外几乎所有特征值都为 0，核塌缩成秩一（如 RBF $\gamma \to 0$ ），不再分类。每个诊断指向不同修复。

Q：有没有非平凡核有闭式 Mercer 展开？ A：少数几个。$\mathbb{R}$ 上带高斯测度的 RBF，特征函数是 Hermite 多项式，特征值显式（Mehler 公式）。多项式核特征函数是单项式（上面算过）。圆上周期核特征函数是正弦。其他多数核无闭式，需数值或渐近分析。Hermite-RBF 情形研究最多，因为它是高斯分布数据的自然配对。

Q：现代论文常提的"核均值嵌入（kernel mean embedding）“是什么？ A：给 $\mathcal{X}$ 上的概率分布 $P,$ 其均值嵌入 $\mu_P(\cdot) = \int K(\cdot, y) dP(y) \in \mathcal{H}.$ 核"characteristic”（RBF $\gamma > 0$ 符合）时，$P \mapsto \mu_P$ 是单射，分布被核均值唯一确定。这是 MMD 双样本检验、kernel ABC 以及一大堆当代贝叶斯推断的基础。它在 Mercer 之下游，正如整个 $L^2$ 分析在谱定理之下游。

Q：$n = 10^6$ 时还能用 Mercer 思考吗？ A：能，但不再实例化完整 Gram 矩阵。改成采样 $m \ll n$ 个 Mercer 模——Nystrom 采 $G$ 的列，或随机特征从 Bochner 谱密度采频率 $\omega \sim \mu$ ——用得到的 $m$ 维特征表示工作。任一近似的精度由 Mercer 谱的尾巴控制：$\sum_{k > m} \lambda_k$ 小，近似就忠实。RBF 在光滑数据上，$m = O(\log n)$ 通常够；Laplace 接近 $m = O(\sqrt{n}).$

实际中 Mercer 的收敛#

所以速率完全由谱衰减决定。三种值得认识的区段：

• 指数衰减（$\lambda_k \sim e^{-c k},$ 如光滑数据上的 RBF）：每加 $O(1/c)$ 个模，截断误差减半。实操低秩近似 work 得惊人。
• 幂律衰减（$\lambda_k \sim k^{-\alpha},$ 如 Laplace、低 $\nu$ Matern）：截断误差降得慢，达到目标精度需要更多模。这是 Nystrom / RFF 需要大 $m$ 的警示。
• 重尾 / 无衰减：核在数据上基本满秩。要么数据真高维（想想 one-hot 多 level 类别），要么核选错。

这个谱图景也是读核学习曲线的正确方式。常见诊断图”$\log \lambda_k$ vs $k$ " 在 held-out 样本上：直线 = 指数，曲线 = 幂律。两种都信息丰富，平的就是警报。

收尾思考#

本文的两条定理——PSD 核的 Gram 矩阵刻画与 Mercer 谱分解——共同扛起后续核理论的全部重活。下游一切（RKHS、表示定理、核岭界、GP 边际似然、Nystrom 误差分析）都是这两条事实的推论或精炼。如果你能闭眼背出两条，并且不查就能在 2 次多项式上做显式特征映射与核公式的相互转换，你已经具备读三十年内任意核方法论文的能力。

历史线也值得知道。Mercer 1909 年的论文埋在泛函分析里直到 1990 年代 Vapnik 等人意识到核技巧让 SVM 计算可行。1995–2005 年的"核革命"大体是把每一种经典 ML 方法（PCA、CCA、logistic 回归、ICA）在核框架里重推一遍，每次都发现是同一条 Mercer 定理批准了这步操作。2017 年之后的 NTK 时代是第三波：重新发现宽神经网络也是伪装的核方法。数学没怎么动；对其可能性的欣赏在不断扩展。

如果你要本系列剩下部分的单一心智模型，就是这个。核是 PSD 函数。Mercer 把它变成带特征值 $\{\lambda_k\}$ 和特征函数 $\{\phi_k\}$ 的正交特征分解。特征值控制容量；特征函数是隐式特征。你将遇到的每个核方法——SVM、KRR、GP、kernel PCA、MMD、特征嵌入——底层都是用 $\{\lambda_k, \phi_k\}$ 的不同方式，只通过 Gram 矩阵 $G_{ij} = K(x_i, x_j)$ 暴露给用户。脑中保持此图景，剩下的系列就是按算法拆解后果。

接下来#

你已经知道核是什么、怎么检查、隐式特征空间从哪儿来。Part 3 把同样的 Mercer 展开重新组织成 再生核希尔伯特空间（RKHS）——核 SVM、高斯过程、核岭回归实际上在的那个函数空间。RKHS 视角能给出表示定理（representer theorem）——核方法尽管隐式工作在（有时是无穷维）特征空间里却仍然计算可行的结构性理由。

如果只能带走一句话，让它是这句：PSD 不是技术细节，它是核技巧能存在的全部理由。Gram 矩阵搞对了，剩下的——SVM、GP、KRR、核 PCA——都从同一组定理流出来。搞错了，solver 会大声告诉你。本系列后面所有文章都假设你已吸收这两个事实；如果未来哪一篇看不懂了，回这里再读 Mercer 节。

本文是 核方法 系列的第 2 篇，共 8 篇。 上一篇: 第 1 篇 — 为什么需要核方法 · 下一篇: 第 3 篇 — RKHS：核方法的理论灵魂