4.

各定理解决的核心问题

Theorem 1 (Bochner's Theorem - 波赫纳定理):
- 解决的问题： 提供理论基础。它本身不直接降低复杂度，但它揭示了（特定类型的）核函数计算等价于一个傅里叶变换下的期望。这个发现是“可被近似”的理论基石，它允许我们将一个复杂的、成对的（ $O (N^{2})$ ）核函数计算问题，转化为一个线性（ $O (N)$ ）的特征映射和内积问题。它告诉我们“为什么”可以这么做。
Theorem 2 (Positive Fixed Features - PFF - 正固定特征):
- 解决的问题： 提供一种具体的、可操作的降维方法。它基于 Bochner 定理，给出了如何通过蒙特卡洛或准蒙特卡洛方法进行随机特征采样，来构造一个无偏估计，从而将注意力机制的复杂度从 $O (N^{2})$ 降低到 $O (N \cdot m)$ （其中 $m$ 是特征维度， $m ≪ N$ ）。它告诉我们“如何”去做这个近似。
Theorem 3 (Weighted Positive Fixed Features - WPFF - 加权正固定特征):
- 解决的问题： 提高近似的精度。PFF 使用的是固定的随机特征，其近似效果有好有坏。WPFF 通过引入一个可学习的参数 $λ (x)$ ，允许模型根据输入数据动态地“加权”这些特征，从而在不增加计算复杂度的情况下，获得一个误差更小、更精确的近似。它解决了“如何让近似更有效”的问题。

Theorem 1 (Bochner's Theorem)

定理陈述： 一个连续的移位不变（shift-invariant）核函数 $k (x, y) = k (x - y)$ 是正定的（Positive Definite），当且仅当它是一个唯一的、有限的、非负的博雷尔测度（Borel measure）的傅里叶变换。

更具体地说，对于在 $R^{d}$ 上的连续函数 $k$ ，如果 $k$ 是正定的，那么存在一个唯一的、有限的、非负的博雷尔测度 $μ$ ，使得：

k (δ) = \int_{R^{d}} e^{i ω^{T} δ} d μ (ω)

其中 $δ = x - y$ 。如果这个测度 $μ$ 存在一个密度函数 $p (ω)$ ，那么这个关系可以写成一个更常见的积分形式：

k (x - y) = \int_{R^{d}} p (ω) e^{i ω^{T} (x - y)} d ω

这里的 $p (ω)$ 是一个概率密度函数，因为测度是有限且非负的。

数学知识详解

1. 连续移位不变核函数

核函数 (Kernel Function)：在机器学习中，核函数是一个函数，它接受两个输入 $x$ 和 $y$ ，并返回一个表示它们相似度的标量。它隐式地将数据映射到一个高维特征空间，并计算该空间中的内积。
移位不变性 (Shift-Invariance)：如果一个核函数仅依赖于输入向量的差 $x - y$ ，即 $k (x, y) = k (x - y)$ ，那么它就是移位不变的。这意味着无论数据点在空间中的绝对位置如何，只要它们的相对位置（即差向量）相同，它们之间的相似度就相同。高斯核 $k (x, y) = \exp (- γ ∥ x - y ∥^{2})$ 就是一个典型的例子。

2. 正定性 (Positive Definiteness)

一个核函数 $k (x, y)$ 被称为是正定的，如果对于任意数量的样本点 $x_{1}, x_{2}, \dots, x_{n}$ ，由 $K_{i j} = k (x_{i}, x_{j})$ 构成的 $n \times n$ 核矩阵（格拉姆矩阵）是半正定的。这意味着对于任意非零的实向量 $c = (c_{1}, c_{2}, \dots, c_{n})^{T}$ ，都有：

\sum_{i = 1}^{n} \sum_{j = 1}^{n} c_{i} c_{j} K_{i j} \geq 0

正定性是核函数能够被视为某个特征空间内积的充要条件，这是核方法有效性的理论基础。

3. 傅里叶变换 (Fourier Transform)

傅里叶变换是一种将函数从其原始域（通常是时间或空间）转换到频域的数学工具。Bochner 定理将核函数的正定性这个代数性质，与一个函数的傅里叶变换是一个概率密度函数这个分析性质联系了起来。

从理论到实践：近似核函数

Bochner 定理不仅是一个理论上的结论，它还为近似复杂的核函数提供了一条强大的路径。根据定理，核函数可以表示为期望的形式：

k (x - y) = \int p (ω) e^{i ω^{T} (x - y)} d ω = E_{ω \sim p (ω)} [e^{i ω^{T} x} \cdot e^{- i ω^{T} y}]

上述公式表明，核函数可以被看作是 $e^{i ω^{T} x}$ 和 $e^{- i ω^{T} y}$ （即 $e^{i ω^{T} y}$ 的复共轭）乘积在 $ω$ 服从 $p (ω)$ 分布下的期望值。

有限维特征图与蒙特卡洛近似

直接计算这个积分是困难的，但我们可以通过蒙特卡洛方法来近似它。

从概率分布 $p (ω)$ 中独立采样 $m$ 个样本 $ω_{1}, ω_{2}, \dots, ω_{m}$ 。
用这些样本的平均值来近似期望： $k (x, y) \approx \frac{1}{m} \sum_{j = 1}^{m} e^{i ω_{j}^{T} x} \cdot e^{- i ω_{j}^{T} y}$

为了得到实数值的特征，可以利用欧拉公式：

e^{i θ} = \cos (θ) + i \sin (θ)

通过展开并重组，可以构造一个显式的有限维特征图 $ϕ (x)$ ：

ϕ (x) = \frac{1}{\sqrt{m}} [\cos (ω_{1}^{T} x), \sin (ω_{1}^{T} x), \dots, \cos (ω_{m}^{T} x), \sin (ω_{m}^{T} x)]^{T}

这样，原始的核函数计算 $k (x, y)$ 就可以被近似为两个低维特征向量的内积：

k (x, y) \approx ϕ (x)^{T} ϕ (y)

这种方法被称为随机傅里叶特征 (Random Fourier Features, RFF)。

准蒙特卡洛方法

标准的蒙特卡洛方法使用随机采样，这可能导致样本分布不均。为了提高积分估计的效率和精度，可以使用准蒙特卡洛方法。该方法使用低差异序列代替随机数，以更均匀的方式探索积分空间，从而通常能用更少的样本获得更好的近似效果。

定理中强调**“唯一有限概率测度”**，其含义是：

测度 (Measure): 为了让定理具有普适性。它囊括了频率成分是连续分布、离散分布或混合分布的所有可能性。这是最严谨、最根本的数学语言。
概率 (Probability): 意味着这个测度是有限 (Finite) 且总和可以被归一化为1的。即 $μ (R^{d}) = 1$ 。这保证了 $k (0)$ 是一个有限值，符合核函数的性质。
唯一 (Unique): 指的是一个正定核函数和一个概率测度之间存在着一一对应的完美关系。每一个合法的核函数都对应着独一无二的“频谱配方”，反之亦然。

在 Transformer 中的应用：注意力机制

在 Transformer 模型中，注意力机制的核心是计算 Query (Q) 和 Key (K) 之间的相似度，通常是通过点积 $Q K^{T}$ 来实现的。当 $Q$ 和 $K$ 的行向量 $q_{i}, k_{j}$ 被 L2 归一化后，点积与高斯核密切相关。

因为当 $∥ q_{i} ∥ = ∥ k_{j} ∥ = 1$ 时：

∥ q_{i} - k_{j} ∥^{2} = ∥ q_{i} ∥^{2} - 2 q_{i} \cdot k_{j} + ∥ k_{j} ∥^{2} = 2 - 2 q_{i} \cdot k_{j}

所以点积可以表示为：

q_{i} \cdot k_{j} = 1 - \frac{1}{2} ∥ q_{i} - k_{j} ∥^{2}

这表明点积与欧几里得距离的平方呈线性关系。因此，基于点积的注意力可以被看作是与高斯核 $k (q, k) = \exp (- γ ∥ q - k ∥^{2})$ 密切相关的一种相似性度量。

通过引入 Bochner 定理，可以将注意力机制中的高斯核（或类似的核）用随机傅里叶特征来近似。这允许将注意力计算的复杂度从 $O (N^{2})$ （其中 $N$ 是序列长度）降低到 $O (N \cdot m)$ （其中 $m$ 是随机特征的维度，通常 $m ≪ N$ ），从而极大地提高了处理长序列的效率。

Theorem 2: Positive Fixed Features (PFF) - 证明其为无偏估计

我们要证明的是，通过有限采样构造的近似核 $\hat{k} (x, y)$ 是真实核 $k (x, y)$ 的无偏估计。也就是说，证明 $E [\hat{k} (x, y)] = k (x, y)$ 。

1. 构造实数特征图

Bochner 定理给了我们一个复数形式的期望。为了在实际中计算，我们需要将其转换为实数。利用欧拉公式 $e^{i θ} = \cos (θ) + i \sin (θ)$ ：

\begin{aligned} e^{i ω^{T} x} (e^{i ω^{T} y})^{*} & = (\cos (ω^{T} x) + i \sin (ω^{T} x)) (\cos (ω^{T} y) - i \sin (ω^{T} y)) \\ = (\cos (ω^{T} x) \cos (ω^{T} y) + \sin (ω^{T} x) \sin (ω^{T} y)) + i (\dots) \end{aligned}

由于核函数 $k (x - y)$ 通常是实数值的（例如高斯核），在取期望后，虚部会因为 $p (ω)$ 是偶函数（对于高斯核，其傅里叶变换也是高斯分布，是偶函数）而抵消为零。因此，我们只关心实部：

k (x - y) = E_{ω \sim p (ω)} [\cos (ω^{T} x) \cos (ω^{T} y) + \sin (ω^{T} x) \sin (ω^{T} y)]

利用三角恒等式 $\cos (a - b) = \cos (a) \cos (b) + \sin (a) \sin (b)$ ，上式可以写为：

k (x - y) = E_{ω \sim p (ω)} [\cos (ω^{T} (x - y))]

为了构造一个内积形式，我们定义一个特征映射 $z_{ω} (x)$ ：

z_{ω} (x) = [\cos (ω^{T} x), \sin (ω^{T} x)]^{T}

那么， $z_{ω} (x)^{T} z_{ω} (y)$ 正好是上面期望内的表达式：

z_{ω} (x)^{T} z_{ω} (y) = \cos (ω^{T} x) \cos (ω^{T} y) + \sin (ω^{T} x) \sin (ω^{T} y)

所以，我们有：

k (x - y) = E_{ω \sim p (ω)} [z_{ω} (x)^{T} z_{ω} (y)]

2. 蒙特卡洛近似与无偏性证明

现在，我们使用蒙特卡洛方法来近似这个期望。我们从分布 $p (ω)$ 中独立同分布地抽取 $m$ 个样本 $ω_{1}, \dots, ω_{m}$ 。然后构造近似核 $\hat{k} (x, y)$ ：

\hat{k} (x, y) = \frac{1}{m} \sum_{j = 1}^{m} z_{ω_{j}} (x)^{T} z_{ω_{j}} (y)

为了证明它是无偏的，我们对 $\hat{k} (x, y)$ 本身求期望。这里的期望是针对所有可能的采样集 ${ω_{j}}_{j = 1}^{m}$ 而言的。

\begin{aligned} E [\hat{k} (x, y)] & = E_{ω_{1}, \dots, ω_{m} \sim p (ω)} [\frac{1}{m} \sum_{j = 1}^{m} z_{ω_{j}} (x)^{T} z_{ω_{j}} (y)] \end{aligned}

根据期望的线性性质，我们可以将求和与常数移到期望外面：

\begin{aligned} E [\hat{k} (x, y)] & = \frac{1}{m} \sum_{j = 1}^{m} E_{ω_{j} \sim p (ω)} [z_{ω_{j}} (x)^{T} z_{ω_{j}} (y)] \end{aligned}

因为所有的 $ω_{j}$ 都是从同一个分布 $p (ω)$ 中独立抽取的，所以每一项的期望都是相同的：

E_{ω_{j} \sim p (ω)} [z_{ω_{j}} (x)^{T} z_{ω_{j}} (y)] = E_{ω \sim p (ω)} [z_{ω} (x)^{T} z_{ω} (y)]

而我们从第一步已经知道，这个期望值正好就是 $k (x - y)$ ：

E_{ω \sim p (ω)} [z_{ω} (x)^{T} z_{ω} (y)] = k (x - y)

将这个结果代回，我们得到：

E [\hat{k} (x, y)] = \frac{1}{m} \sum_{j = 1}^{m} k (x - y) = \frac{1}{m} \cdot m \cdot k (x - y) = k (x - y)

证明完毕。 这表明，我们通过有限采样构造的 PFF 近似核 $\hat{k} (x, y)$ ，其期望值恰好等于真实的核函数 $k (x, y)$ ，因此它是一个无偏估计。

Theorem 3: Weighted Positive Fixed Features (WPFF) - 证明思路

WPFF 的核心是引入了一个可学习的权重函数 $λ (x)$ 。我们这里不严格证明其“误差上界更小”，因为这需要引入再生核希尔伯特空间 (RKHS) 和积分算子理论，非常复杂。但我们可以从方差缩减 (Variance Reduction) 的角度来理解为什么它可能更优。

1. 加权形式

WPFF 的近似核可以写成：

{\hat{k}}_{w p f f} (x, y) = \frac{1}{m} \sum_{j = 1}^{m} λ (x)^{T} z_{ω_{j}} (x)^{T} z_{ω_{j}} (y) λ (y)

为了让它仍然是无偏的，我们需要对 $λ (x)$ 做出一些约束，或者调整采样分布。在许多实际应用中，这种加权更像是一种重要性采样 (Importance Sampling) 的思想。

2. 与重要性采样的联系

回忆一下，PFF 的方差（即近似的稳定性）为：

Var [\hat{k} (x, y)] = \frac{1}{m} {Var}_{ω \sim p (ω)} [z_{ω} (x)^{T} z_{ω} (y)]

这个方差取决于被积函数 $f (ω) = z_{ω} (x)^{T} z_{ω} (y)$ 在分布 $p (ω)$ 下的波动情况。如果函数在某些区域剧烈变化，而我们的采样点又很稀疏，那么近似结果的方差就会很大。

重要性采样的思想是，我们不从原始分布 $p (ω)$ 采样，而是从一个更优的分布 $q (ω)$ 采样，然后对结果进行加权修正，以保持无偏性：

k (x - y) = E_{ω \sim p (ω)} [f (ω)] = E_{ω \sim q (ω)} [f (ω) \frac{p (ω)}{q (ω)}]

这里的 $\frac{p (ω)}{q (ω)}$ 就是“重要性权重”。如果我们能精心设计一个 $q (ω)$ ，使得被积函数 $f (ω) \frac{p (ω)}{q (ω)}$ 的方差变得更小，那么我们的蒙特卡洛近似就会更稳定、更准确。

WPFF 中的可学习权重 $λ (x)$ 可以被看作是这个思想的一种简化或变体。模型在训练过程中学习到的 $λ (x)$ ，实际上是隐式地在学习一个“更优”的采样策略。它试图放大那些对最终结果贡献更大（即方差更大或数值更大）的特征维度 $ω_{j}$ ，同时抑制那些贡献小的维度。

通过端到端的训练，优化器会调整 $λ (x)$ 的参数，其目标是最小化模型的整体损失函数。这个过程会驱使 $λ (x)$ 形成一种权重分配，使得近似核 ${\hat{k}}_{w p f f}$ 能够更好地拟合目标（即真实的注意力分布），这等价于找到了一个方差更小的估计量。

因此，虽然我们没有严格证明其误差上界，但从方差缩减的角度可以直观地理解，通过学习数据相关的权重，WPFF 有潜力找到比固定、随机的 PFF 更稳定、更精确的核函数近似。