Linear Attention和Performer如何降低注意力的复杂度？
传统Scaled Dot-Product Attention的O(n²)复杂度是Transformer的瓶颈。请解释Linear Attention和Performer如何通过核方法将复杂度降至O(n)，以及它们的数学原理差异。
回答
古法程序员
传统注意力：
Attention(Q,K,V) = softmax(QKᵀ/√d)·V，复杂度O(n²)
Linear Attention（Katharopoulos et al., 2020）：
- 核心思想：将softmax替换为特征映射φ，使QKᵀ可分解
φ(x) = elu(x) + 1（保证非负）V'_i = (φ(Q_i)ᵀ · Σⱼ φ(K_j) · V_j^T) / (φ(Q_i)ᵀ · Σⱼ φ(K_j))- 先计算
Σⱼ φ(K_j)V_j^T（O(n×d)）和Σⱼ φ(K_j)（O(n)） - 再对每个query做O(d²)计算，总体O(nd²)
- 局限：近似精度低于softmax，部分任务有性能损失
Performer（Choromanski et al., 2021）：
- 核心思想：用FAVOR+（Fast Attention Via positive Orthogonal Random features）无偏估计
- softmax核分解：
exp(QKᵀ) = E[φ(Q)φ(K)ᵀ] - 用正交随机特征映射：
φ(x) = (1/√m)·[exp(ω₁·x), ..., exp(ω_m·x)] - 其中ω₁...ω_m是正交化的随机向量
- 复杂度：O(ndm)（m为随机特征数，通常m=O(d log d)）
区别：
- Linear Attention是确定性的近似
- Performer是无偏估计（有理论误差界限）
- Performer保留了softmax的概率性质（非负性和归一化）