Transformer are Deep Infinite-Dimensional Non-Mercer Binary Kernel Machines

前言

文章：Transformer are Deep Infinite-Dimensional Non-Mercer Binary Kernel Machines

essay link

无限维non-mercer跟Transformer关联的文章，感觉这是最近五篇文章中最难的，主要泛函已经还给老师了，老天爷啊！

摘要

尽管它们在自然语言处理等核心 AI 领域无处不在，但Transformer等基于深度注意力的神经网络机制尚未得到充分理解。在本文中，我们提出了理解 Transformer 工作原理的新视角。

特别是，我们展示了作为 Transformer 操作核心的“点积注意力”可以表征为一对 Banach 空间上的核学习方法。尤其是，Transformer 的内核具有无限的特征维度。在此过程中，我们考虑将标准内核学习问题扩展到二进制设置，其中数据来自两个输入域，并且为每个跨域对定义了一个响应。

我们为这些具有非 Mercer（不定、不对称）内核的二进制内核机器证明了一个新的表示定理（这意味着学习的函数是再生内核 Banach 空间而不是 Hilbert 空间的元素），并且还证明了一个新的通用逼近定理表明 Transformer 计算可以学习任何二进制非 Mercer 再生内核 Banach 空间对。

我们在 Transformers 中用新内核进行实验，获得的结果表明标准 Transformer 内核的无限维度对其性能有部分影响。本文的结果为现代机器学习中一个非常重要但鲜为人知的模型提供了新的理论理解。

1，介绍

自从 bahdanau_neural_2015 提出以来，所谓的神经注意力已经成为许多最先进的深度学习模型的支柱。在自然语言处理 (NLP) 中尤其如此，其中 Transformer 模型已经无处不在。这种无处不在的现象使得过去几年 NLP 的大部分突破都归功于为 Transformers 开发新的训练机制。

与大多数现代深度神经网络一样，对 Transformer 的理论理解已经落后于基于 Transformer 的 AI 任务（如 NLP）的性能改进速度。最近，一些作者注意到 Transformer 操作与深度学习理论中其他更容易理解的主题之间的关系，例如注意力和卷积之间的相似性以及多层 Transformer 中残差块的设计；另请参阅原始 Transformer 作者的官方参考代码库和最近的一些研究中对主要学习（全连接或注意）操作、元素非线性和归一化的重新排序用以研究更深层次的 Transformers 到归一化的“预规范”排序、学习操作、非线性，添加现代（“v2”）Resnets 的残差排序。

在本文中，我们提出了一个新的视角来理解 Transformer 的核心组件，即它的“点积注意力”操作。特别是，我们表明点积注意力可以表征为一类特定的内核方法。更具体地说，它是所谓的“非定”和“对称”的核方法，它们指的是经典类核的两个独立推广，不需要对称和（半）正定的经典假设确定性。事实上，我们在下面的定理2中表明，点积注意力可以学习任何不对称的不定核。

这种见解有几个有趣的含义。最直接的是，它为 Transformer 中一个更神秘的组件提供了一些理论依据。它还可能为应用数十年的经典核方法理论打开大门，以理解当今最重要的神经网络模型之一，这可能类似于数字信号处理工具如何广泛用于研究卷积神经网络。我们在本文的最后一点上迈出了第一步，提出了我们称为“二进制”内核机器的先前的内核方法泛化，它学习如何预测两个输入集中的元素对的不同值，类似于注意力模型。

本文的其余部分安排如下。Section2部分回顾了 Transformers 和经典内核方法的数学背景。Section3 节介绍了我们用来表征 Transformer 的再生内核 Banach 空间 (RKBS) 上的内核机器的定义。我们特别注意到，Transformer 可以描述为具有无限维特征的空间。Section4 开始了我们的理论结果，明确地描述了 Transformer 的再生内核，包括 Transformer 的内核特征映射的显式公式及其与先前内核的关系。Section5 部分讨论了作为内核学习器的Transformer，包括一个新的表示定理和将随机梯度下降训练的注意力网络表征为近似内核学习器。在第 Section6 节中，我们提供了经验证据，证明 Transformer 内核的无限维特征可能在某种程度上对模型的有效性负责。 Section7 部分给出结论，并总结了我们的工作。

2，背景和相关工作

2.1 Transformer神经网络模型

Transformer 模型在自然语言处理等许多核心 AI 应用中无处不在。在这里，我们回顾了它的核心组件。假设我们有两组有序的向量，一组source元素 $\{s_1, s_2, \dots, s_S\},\;s_j \in \mathbb{R}^{d_s}$ 和一组target元素 $\{t_1, t_2, \dots, t_T\},\; t_i \in \mathbb{R}^{d_t}$。在其一般的形式中，构成 Transformer 模型主干的神经网络“注意力”操作是为每个 $t_i$， 计算源序列 $\{ s_j\}_{j=1}^s$ 的嵌入向量。通常，源集和目标集被认为是相同时，即 $s_i=t_i,\forall i$，这种注意力此时称为自注意力。

Transformer 中使用的特殊函数是所谓的“缩放点积”注意力，其形式为：

$$a_{ij}=\frac{(W^Qt_i)^T(W^Ks_j)}{\sqrt{d}},\alpha_{ij}=\frac{exp(a_{ij})}{\sum^S_{j=1}exp(a_{ij})}, t'_i=\sum\limits^S_{j=1}\alpha_{ij}W^Vs_j \tag{1}\label{eq1}$$

其中 $W^V, W^K \in \mathbb{R}^{d_s \times d}$, 和 $W^Q \in \mathbb{R}^{d_t \times d}$ 是可学习的权重矩阵，通常称为分别为“value”、“key”和“query”权重矩阵。

通常具有独立参数矩阵的多个所谓的“注意力头”实现了方程(1)的几个并行计算，几个 $d$ 维头输出的笛卡尔积（向量级联）形成最终输出 $t’_i$。通常未归一化的 $a_{ij}$ 称为注意力分数或注意力对数，而归一化的 $\alpha_{ij}$ 称为注意力权重。

在本文中，我们将注意力限制在 方程(1) 中所示的注意力点积公式。其他几种注意力替代形式执行大致相同功能， 但Transformer 的点积公式是迄今为止最受欢迎的。

2.2 核方法和生成核

核方法是一类经典而强大的机器学习方法，关键组成部分是核函数，它允许有效映射低维的输入数据，如用其他线性方案来解决此类问题（如分类或回归等）是不可能的，将低维输入数据映射到高维数据域或无限维嵌入域，这是有线性解决方案的。

给定两个非空集 $\mathcal{X}$ 和 $\mathcal{Y}$，核函数 $\kappa$ 是一个连续函数 $\kappa: \mathcal{X} \times \mathcal{Y} \to \mathbb{R}$。在接下来的几节中，我们将回顾经典的对称和（半）正定或 Mercer 内核，然后讨论更一般的形式。

2.2.1 对称和半正定 (Mercer) 内核

如果 $\mathcal{X}=\mathcal{Y}$，并且对于所有 $x_i, x_j \in \mathcal{X}=\mathcal{Y}$，特定内核 $\kappa$ 具有以下属性:

$$\begin{align*} & \kappa (x_i,x_j) =\kappa (x_j,x_i) \tag{2a}\label{eq2a}\\ c^T\mathbf{K}c\geq 0 \quad & \forall c\in\mathbb{R}^n;\quad i,j=1,\cdots n \tag{2b}\label{eq2b} \end{align*}$$

其中 \eqref{eq2b} 中的 $\mathbf{K}$ 是 Gram 矩阵，定义为 $\mathbf{K}_{ij} = \kappa(x_i, x_j)$，那么 $\kappa$ 被称为 Mercer 内核。性质 \eqref{eq2a} 是对称性要求，而 \eqref{eq2b} 是（半）正定性的条件。

对于 Mercer 内核，众所周知，除其他事实外，

• (i) 我们可以在 $\mathcal{X}$ 上定义函数的 Hilbert 空间，表示为 $\mathcal{H}_\kappa$（称为再生核 Hilbert 空间，或 RKHS，与再生核 $\kappa$ 相关联）；
• (ii) $\mathcal{H}_\kappa$ 对于每个 $x$ 都有一个（连续的）唯一元素 $\delta_x$，称为点评估泛函，具有性质 $f(x) = \delta_x(f) \quad \forall f \in \mathcal{H}_\kappa$；
• (iii) $\kappa$ 具有所谓的复制属性，$\langle f,\kappa(x, \cdot)\rangle_{\mathcal{H}_\kappa} = f(x) \; \forall f \in \mathcal{H}_\kappa$，其中 $\langle\cdot，\cdot\rangle_{\mathcal{H}_\kappa}$ 是 $\mathcal{H}_\kappa$ 上的内积；
• (iv) 我们可以定义一个“特征映射” $\Phi: \mathcal{X} \to \mathcal{F}_\mathcal{H}$，其中 $\mathcal{F}_\mathcal{H}$ 是另一个希尔伯特空间，有时也称为特征空间，$\kappa(x, y) = \langle\Phi(x), \Phi(y)\rangle_{\mathcal{F}_\mathcal{H}}$ （其中 $\langle\cdot, \cdot\rangle_{\mathcal{F}_\mathcal{H}}$ 是与 $\mathcal{F}_\mathcal{H}$ 关联的内积。

最后一点指出了 RKHS 的内核技巧。

从机器学习和优化的角度来看，对称和正（半）定（PSD）内核是可取的，因为这些属性保证经验风险最小化内核学习问题（如支持向量机（SVM）、高斯过程等）是凸的。凸性为学习问题的易处理性和解决方案的最优性提供了有吸引力的保证。

2.2.2 用非 Mercer 内核学习

使用非 Mercer 内核或放松假设 \eqref{eq2a} 和 \eqref{eq2b} 的内核的学习方法已经研究了一段时间。工作 lin_study_2003等专注于使用对称但不正定的内核进行学习，即不满足 \eqref{eq2b}。自 schwartz_sous-espaces_1964 等以来，不定内核已被确定为所谓的再生内核 Krein 空间 (RKKS) 的再生内核。

在学习问题（例如具有不确定内核的 SVM）中替换 Mercer 内核使得优化问题通常是非凸的（因为内核 Gram 矩阵 $\mathcal{K}$ 不再总是 PSD）。一些使用不定内核学习的早期工作试图通过修改 Gram 矩阵的频谱来改善这个问题，使其再次变为 PSD。

最近，loosli_learning_2016 等提出了直接在 RKKS 中学习的优化程序。
他们报告说，与流行的 Mercer 核或光谱修改的不定核相比，使用不定核时在某些学习问题上的性能更好，这表明牺牲凸性可以根据经验提高性能。这个结论当然让人联想到深度神经网络的并发体验，由于其高度的非凸性，很难优化，但却提供了优于许多其他方法的性能。

另一项工作探索了内核方法​​在更一般的 Banach 空间中的学习应用，即再生内核 Banach 空间 (RKBS)。已经提出了各种结构作为 Banach 空间的再生核（取代 RKHS 的内积），包括半内积、通过傅立叶变换构造的正定双线性形式，以及其他。在这项工作中，我们考虑 RKBS 的内核可能既不是对称的也不是 PSD 的，接下来介绍这些空间的定义。

3，一般再生内核 Banach 空间

最近，georgiev_construction_2014等 提出了 RKBS 及其再生内核的类似定义和构造，旨在包含先前的定义。在本文中，我们采用了定义的融合，并尝试使符号尽可能简单以满足我们的目的。

定义1 再生内核 Banach 空间
$\mathcal{X}$ 和 $\mathcal{Y}$ 是非空集合，核 $\kappa$ 是个度量函数，$\kappa:\mathcal{X} \times\mathcal{Y}\rightarrow\mathbb{R}$，$\mathcal{B}x$ 和 $\mathcal{B}y$ 是定义在$\mathcal{X}$ 和 $\mathcal{Y}$ 上带实数度量函数的Banach空间，定义 $\langle\cdot,\cdot\rangle:\mathcal{B}x\times\mathcal{B}y\rightarrow\mathbb{R}$ 是一个双线性非退化映射，使得：

$$\begin{align*} \kappa(x,\cdot)\in\mathcal{B}y \quad & \forall x\in\mathcal{X}\tag{3a}\label{eq3a}\\ \langle f,\kappa(x,\cdot)\rangle_{\mathcal{B}x\times\mathcal{B}y}=f(x)\quad & \forall x\in\mathcal{X},f\in\mathcal{B}x \tag{3b}\label{eq3b}\\ \kappa(\cdot,y)\in\mathcal{B}x\quad & \forall y\in\mathcal{Y} \tag{3c}\label{eq3c}\\ \langle\kappa(\cdot,y),g\rangle_{\mathcal{B}x\times\mathcal{B}y}=g(y)\quad & \forall y\in\mathcal{Y},g\in\mathcal{B}y \tag{3d}\label{eq3d} \end{align*}$$

那么，$\mathcal{B}_\mathcal{X}$ 和 $\mathcal{B}_\mathcal{Y}$ 分别是 $\mathcal{X}$ 和 $\mathcal{Y}$ 上的一对再生核Banach空间（RKBS），$\kappa$ 是它们的再生核。

式 \eqref{eq3a} (或者\eqref{eq3c})的含义为，如果我们取 $\kappa$，两个变量 $x \in \mathcal{X}$ 和 $y \in \mathcal{Y}$ 的函数 , 并固定 $x$ (或者 $y$), 然后我们得到一个变量的函数。这个函数的一个变量必须是 $\mathcal{B}_\mathcal{Y}$ (或者 $\mathcal{B}_\mathcal{X}$) 的一个元素。
式子 \eqref{eq3b} 和 \eqref{eq3d} 是 $\kappa$ 再生属性。

出于我们的目的，扩展此定义以包含类似于 RKHS 的某些解释中针对特征使用的“特征映射”将很有用。

定义2(RKBS 的特征映射)
对于定义1中定义的一对 RKBS，假设存在映射 $\Phi_\mathcal{X}: \mathcal{X} \to \mathcal{F}_\mathcal{X}, \Phi_\mathcal{Y}: \mathcal{Y} \to \mathcal{F}_\mathcal{Y}$，其中 $\mathcal{F}_\mathcal{X}$ 和 $\mathcal{F}_\mathcal{Y}$ 是我们称为特征空间的 Banach 空间，以及一个非退化双线性映射 $\langle\cdot,\cdot\rangle_{\mathcal{F}_\mathcal{X} \times \mathcal{F}_\mathcal{Y}}: \mathcal{F}_\mathcal{X} \times \mathcal{F}_\mathcal{Y}\to \mathbb{R}$ 这样就有：

$$\kappa(x,y)=\langle\Phi_{\mathcal{X}(x)},\Phi_{\mathcal{Y}(y)}\rangle_{\mathcal{F}_{\mathcal{X}}\times\mathcal{F}_{\mathcal{Y}}}\quad \forall x\in\mathcal{X},y\in\mathcal{Y} \tag{4}\label{eq4}$$

在这种情况下，空格 $\mathcal{B}_\mathcal{X}$ 和 $\mathcal{B}_\mathcal{Y}$ 可以定义如下，可参考文献 xu_generalized_2019 。

$$\begin{align*} \mathcal{B}_{\mathcal{X}} & =\{f_v:\mathcal{X}\rightarrow\mathbb{R}:f_v(x)\triangleq\langle\Phi_{\mathcal{X}}(x),v\rangle_{\mathcal{F}_{\mathcal{X}}\times\mathcal{F}_{\mathcal{Y}}};v\in\mathcal{F}_{\mathcal{Y}},x\in\mathcal{X} \tag{5a}\label{eq5a}\\ \mathcal{B}_{\mathcal{Y}} & =\{g_u:\mathcal{Y}\rightarrow\mathbb{R}:g_u(y)\triangleq\langle u,\Phi_{\mathcal{Y}}(y)\rangle_{\mathcal{F}_{\mathcal{X}}\times\mathcal{F}_{\mathcal{Y}}};u\in\mathcal{F}_{\mathcal{X}},y\in\mathcal{Y} \tag{5b}\label{eq5b} \end{align*}$$

注意1
我们简要讨论如何理解 \eqref{eq5a}和\eqref{eq5b} 给出的空间，以 \eqref{eq5a} 为例。它是一个变量 $x$ 的实值函数空间，其中该函数也由 $v$ 参数化。在 \eqref{eq5a} 中选取 $v \in \mathcal{F}_\mathcal{Y}$ 定义 $\mathcal{B}_\mathcal{X}$ 中的函数流形。这种具有固定 $v$ 的函数流形随函数 $\Phi_\mathcal{X}$ 而变化。通过取 $\Phi_\mathcal{X}(x)$ 和选定的 $v$ 的双线性积来定义在点 $x$ 处计算此流形中的函数 $f_v$。这也意味着我们可以结合 \eqref{eq4},\eqref{eq5a} 和 \eqref{eq5b}有：

$$\kappa(x,y)=\langle\Phi_{\mathcal{X}}(x),\Phi_{\mathcal{Y}}(y)\rangle_{\mathcal{F}_{\mathcal{X}}\times\mathcal{F}_{\mathcal{Y}}}=\langle f_{\Phi_{\mathcal{X}}(x)},g_{\Phi_{\mathcal{Y}}(y)}\rangle_{\mathcal{B}_{\mathcal{X}}\times\mathcal{B}_{\mathcal{Y}}} \tag{6}\label{eq6}$$

对所有的 $x\in \mathbb{X}, y\in\mathbb{Y}$

注意2
如果 $\Phi_\mathcal{X}(x)$ 和 $\Phi_\mathcal{Y}(y)$ 可以表示为实值可测函数的可数集，$\{\phi_\mathcal{X}(x)_\ell\}_{\ell \in \mathbb{N}}$ 和 $\{\phi_\mathcal{Y}(y)_\ell\}_{\ell \in \mathbb{N}}$ 对于 $(\phi_{\mathcal{X}})_\ell: \mathcal{X} \to \mathbb{R}$ 和 $(\phi_{\mathcal{Y}})_\ell: \mathcal{Y} \to \mathbb{R}$ （即 $\mathcal{F}_\mathcal{X}, \mathcal{F}_\mathcal{Y} \subset \prod_{\ell \in \mathbb{N}} \mathbb{R}$）； 而且 $\langle u,v\rangle_{\mathcal{F}_{\mathcal{X}}\times\mathcal{F}_{\mathcal{Y}}} = \sum_{\ell \in \mathbb{N}} u_\ell v_\ell$ 对 $u \in \mathcal{F}_\mathcal{X}, v \in \mathcal{F}_\mathcal{Y}$ 都成立。 那么我们从 lin_reproducing_2019 借用其“特征映射”构造对应于 xu_generalized_2019 的“广义 Mercer 内核”。

4，作为 RKBS 内核的点积注意力

我们现在正式陈述作为 RKBS 学习者的点积注意力公式。与 RKHS 非常相似，对于给定的内核及其关联的 RKBS 对，特征映射（以及双线性映射）不是唯一的。在下文中，我们基于其他内核的经典特征（例如 RBF 内核）展示了一个特征映射。

命题1
方程\eqref{eq1} 的（缩放）点积注意力计算是定义1和2意义上的 RKBS 的再生内核，输入集 $\mathcal{X}$ 和 $\mathcal{Y}$ 分别是目标元素 $\{t_i\}_{i=1}^T, \; t_i \in \mathbb{R}^{d_t}$ 和源元素 $\{s_j\}_{j=1}^S, s_j \in \mathbb{R}^{d_s}$ 所在的向量空间。那么特征映射为：

$$\begin{align*} \Phi_{\mathcal{X}}(t) & =\sum\limits^{\infty}_{n=0}\sum\limits_{p_1+\cdots+p_d=n}\frac{\sqrt{\frac{n!}{p_1!\cdots p_d!}}\prod^d_{l=1}(q_\ell)^{p_\ell}}{d^{1/4}} \tag{7a}\label{eq7a}\\ \Phi_{\mathcal{Y}}(s) & =\sum\limits^{\infty}_{n=0}\sum\limits_{p_1+\cdots+p_d=n}\frac{\sqrt{\frac{n!}{p_1!\cdots p_d!}}\prod^d_{l=1}(k_\ell)^{p_\ell}}{d^{1/4}} \tag{7b}\label{eq7b} \end{align*}$$

其中 $q_\ell$ 是 $q = W^Qt$ 的第 $\ell$ 个元素，$k_\ell$ 是 $k = W^Ks$ 的第 $\ell$ 个元素，其中 $W^Q \in \mathbb{R}^{d \times d_t}, W^K \in \mathbb{R}^{d \times d_s}$，在 $d \leq d_s$ 的条件下，而且 $rank(W^Q) = rank(W^K) = d$。双线性映射为 $\langle\Phi_\mathcal{X}(t),\Phi_\mathcal{Y}(s)\rangle_{\mathcal{F}_{\mathcal{X}}\times\mathcal{F}_{\mathcal{Y}}} = \Phi_\mathcal{X}(t) \cdot \Phi_\mathcal{Y}(s)$，巴拿赫空间定义为：

$$\begin{align*} \mathcal{B}_{\mathcal{X}} & =\{f_k(t)=exp((W^Qt)^Tk/\sqrt{d});\; k\in\mathcal{F}_{\mathcal{Y}},t\in\mathcal{X} \} \tag{8a}\label{eq8a}\\ \mathcal{B}_{\mathcal{Y}} & =\{g_q(s)=exp(q^T(W^Ks)/\sqrt{d});\; q\in\mathcal{F}_{\mathcal{X}},s\in\mathcal{Y} \} \tag{8b}\label{eq8b} \end{align*}$$

使用“幂级数query-key内核”相关的再生内核，定义如下：

$$\begin{align*} \kappa(t,s) & =\langle\Phi_{\mathcal{X}}(t),\Phi_{\mathcal{Y}}(s)\rangle_{\mathcal{F}_{\mathcal{X}}\times\mathcal{F}_{\mathcal{Y}}}\tag{}\\ & =\langle f_{\Phi_{\mathcal{Y}}(s)},g_{\Phi_{\mathcal{X}}(t)}\rangle_{\mathcal{B}_{\mathcal{X}}\times\mathcal{B}_{\mathcal{Y}}}\tag{}\\ & =exp(\frac{(W^Qt)^T(W^Ks)}{\sqrt{d}}) \tag{9}\label{eq9} \end{align*}$$

命题1的证明很简单，涉及通过将 \eqref{eq9} 中的两个无限级数相乘来验证 \eqref{eq7a}和\eqref{eq7b}，然后使用多项式定理和指数的泰勒展开。

在上面，当特别提到 Transformer 类型的模型而不是一般的 RKBS 时，我们使用 $t,s,q$ 和 $k$ 来表示 $x、y、u$ 和 $v$ ，分别绘制 RKBS 的元素与广泛使用的术语“目标”、“源”、“查询”和“键”之间的联系。

$W^Q$ 和 $W^K$ 的秩要求，意味着 $span(\{\Phi_\mathcal{X}(t), t \in \mathcal{X}\}) = \mathcal{F}_\mathcal{X}$ 和 $span(\{\Phi_\mathcal{Y}(s), s \in \mathcal{Y}\}) = \mathcal{F}_\mathcal{Y}$。这反过来意味着双线性映射是非退化的。

注意3
现在我们有了一对 RKBS 的例子，我们可以更具体地讨论注意1中的一些讨论。例如，验证 \eqref{eq8a}，当我们在 $\mathcal{F}_\mathcal{Y}$ 中选择 $k$ 时，在 $\mathcal{B}_\mathcal{X}$ 中定义了一个流形函数，其中 $k$ 是固定的 , 但 $W^Q$ 可以变化。类似地，选择 $q \in \mathcal{F}_\mathcal{X}$ 在 $\mathcal{B}_\mathcal{Y}$ 中定义流形。从 $\mathcal{F}_\mathcal{X}$ 和 $\mathcal{F}_\mathcal{Y}$ 中选择一个元素会将我们锁定到 $\mathcal{B}_\mathcal{X}$ 和 $\mathcal{B}_\mathcal{Y}$ 中的一个元素，这导致 \eqref{eq6} 中的相等性。

注意4
检查 \eqref{eq8a}-\eqref{eq9}，可以看到从 $\mathcal{F}_\mathcal{Y}$ 提取的元素参数化了 $\mathcal{B}_\mathcal{X}$ 的元素，如 \eqref{eq8a} 所示，是 $\Phi_\mathcal{Y}$ 的函数（反之亦然，对于 \eqref{eq8b}）。 这揭示了 Transformer 类型的注意力计算是针对 SVM 等应用程序考虑的 RKBS 泛化的确切机制，这些功能空间的其中之一被认为是固定的。

注意5
由于特征映射定义了 Banach 空间 \eqref{eq5a} 和 \eqref{eq5b}，学习到的参数 $W^Q$ 和 $W^K$ 意味着 Transformer 学习 RKBS 自身的参数表示。这与经典内核方法形成对比，在经典内核方法中，内核（以及再生空间）通常是固定的。事实上，在下面的定理2中，我们证明了 Transformer 架构（的变体）可以近似任何 RKBS 映射。

注意6
已知指数点积内核的对称版本是所谓的巴格曼空间的再生内核，它出现在量子力学中。

注意7
在命题1中值得注意的是，我们将点积注意力的内核定义为包括 softmax 运算的指数。因此，此操作的输出不是注意力分数 $a_{ij}$，而是非标准化的注意力权重 $\bar{\alpha}_{ij} = \alpha_{ij} \sum_j \alpha_{ij}$。将指数视为核运算的一部分表明，Transformer 的特征空间实际上是无限维的，就像 RBF 核被称为具有无限维特征空间一样。在第6节中，我们发现经验证据表明这种无限维度可能是 Transformer 有效性的部分原因。

5，Transformer作为核学习者

5.1 二元 RKBS 学习问题及其表示定理

大多数内核学习问题都采用经验风险最小化问题的形式。例如，如果我们有一个有限数据集 $(x_1, z_1), \dots, (x_n, z_n), x_i \in \mathcal{X}, z_i \in \mathbb{R}$ 的学习问题，并且想要学习一个函数 $f： \mathcal{X} \to \mathbb{R}$ 在 RKHS $\mathcal{H}_\mathcal{K}$ 中，学习问题可以写成：

$$f^\ast=\mathop{argmin}_{f\in\mathcal{H}_{\kappa}}\frac{1}{n}\sum\limits^n_{i=1}L(x_i,z_i,f(x_i))+\lambda R(\|f\|_{\mathcal{H}_{\kappa}}) \tag{10}\label{eq10}$$

其中 $L: \mathcal{X} \times \mathbb{R} \times \mathbb{R} \to \mathbb{R}$ 是凸损失函数，$R: [0, \infty) \to \mathbb{R}$ 是严格递增的正则化函数，$\lambda$ 是比例常数。最近考虑在 RKBS 中学习的参考文献考虑了与 \eqref{eq10} 类似的问题，但 RKHS 中 $\mathcal{H}$ 替换为 RKBS。

然而，注意力的内核学习问题与 \eqref{eq10} 的不同之处在于，正如我们在上一节中讨论的那样，我们需要对每个参数对 $(t_i, s_j)$ 预测响应 $z_{ij}$（即注意力 logit）。这激发了在输入空间对上运行的经典内核学习问题类的泛化。我们现在讨论这种概括。

定义3(二元核学习问题——正则化经验风险最小化)

设 $\mathcal{X}$ 和 $\mathcal{Y}$ 为非空集，分别定义其上的RKBS $\mathcal{B}_\mathcal{X}$ 和 $\mathcal{B}_\mathcal{Y}$ 。设 $\langle\cdot,\cdot\rangle_{\mathcal{B}_\mathcal{X}\times\mathcal{B}_\mathcal{Y}}: \mathcal{B}_\mathcal{X} \times \mathcal{B}_\mathcal{Y} \to \mathbb{R}$ 是两个 RKBS 上的双线性映射。设 $\Phi_\mathcal{X}: \mathcal{X} \to \mathcal{F}_\mathcal{X}$，$\Phi_\mathcal{Y}: \mathcal{Y} \to \mathcal{F}_\mathcal{Y}$ 是固定特征映射，其属性为 $\langle\Phi_\mathcal{X}(x_i),\Phi_\mathcal{Y}(y_i)\rangle_{\mathcal{F}_\mathcal{X}\times\mathcal{F}_\mathcal{Y}} = \langle f_{\Phi_\mathcal{Y}(y)},g_{\Phi_\mathcal{X}(x)}\rangle_{\mathcal{B}_\mathcal{X}\times\mathcal{B}_\mathcal{Y}}$。若 $\{x_1, \dots, x_{n_x}\}, x_i \in \mathcal{X}$, $\{y_1, \dots, y_{n_y}\}, y_j \in \mathcal{Y}$, 且 $\{z_ {ij}\}_{i=1,\dots,n_x; \; j=1,\dots,n_y},\;z_{ij} \in \mathbb{R}$ 是有限数据集，其中为定义在 $(i,j)$ 的 $x_i$ 和 $y_j$ 数据对定义响应 $z_{ij}$。设 $L: \mathcal{X} \times \mathcal{Y} \times \mathbb{R} \times \mathbb{R} \to \mathbb{R}$ 是固定 $(x_i, y_j, z_{i,j})$ 的凸损失函数，定义 $R_{\mathcal{X}}: [0, \infty) \to \mathbb{R}$ 和 $R_{\mathcal{Y}}: [0, \infty) \to \mathbb{R}$ 是凸的，且为严格增加正则化函数。

用于在一对 RKBS 上学习的二进制经验风险最小化核学习问题采用以下形式

$$\begin{align*} f^\ast,g^\ast=\mathop{argmin}_{f\in\mathcal{B_{\mathcal{X}}},g\in\mathcal{B_{\mathcal{Y}}}}[\frac{1}{n_xn_y}\sum\limits_{i,j}L(x_i,y_j,z_{ij},\langle f_{\Phi_{\mathcal{Y}}(y_j)},g_{\Phi_{\mathcal{X}}(x_i)}\rangle_{\mathcal{B}_{\mathcal{X}}\times\mathcal{B}_{\mathcal{Y}}})\tag{}\\ +\lambda_{\mathcal{X}}R_{\mathcal{X}}(\|f\|_{\mathcal{B_{\mathcal{X}}}})+\lambda_{\mathcal{Y}}R_{\mathcal{Y}}(\|g\|_{\mathcal{B_{\mathcal{Y}}}})] \tag{11}\label{eq11} \end{align*}$$

其中 $\lambda_\mathcal{X}$ 和 $\lambda_\mathcal{Y}$ 又是缩放常数。

注意8
在两个集合组成的成对数据上运行的二进制内核问题的想法并不是全新的：在协同过滤和张量内核方法等文献中都有先前的工作。我们的问题和结果在泛化到 Banach 而不是 Hilbert 空间方面是新的：正如 RKBS 文献中的前置工作指出的那样，RKBS 学习问题与 RKHS 学习问题的不同之处在于它们的额外非线性 和/或非凸性。因此，将二元学习问题扩展到 Banach 空间是由 Transformer 设置推动的，其中内核方法处于非线性和非凸深度神经网络的上下文中，而不是像 SVM 或矩阵完成那样的浅层学习器。有关更多讨论，请参阅附录A。

几乎所有经典的内核学习方法都能找到其形式由所谓的表示定理指定的解决方案。表示定理指出，再生核空间上正则化经验风险最小化问题的解可以表示为再生核对数据集评估的线性组合。因此，内核学习问题的经典解决方案简化为寻找该线性组合的系数。

fasshauer_solving_2015 等为 RKBS 学习问题提供了表示定理。然而，他们的定理只处理学习问题，其中数据点仅来自定义再生内核的集合之一（即，只有 $\mathcal{X}$ 而没有 $\mathcal{Y}$），这意味着寻求的解决方案是只有一个 Banach 空间（例如 $f: \mathcal{X} \to \mathbb{R}, f \in \mathcal{B}_\mathcal{X}$）。在这里，我们陈述并证明了定义3中提出的与 Transformers 更相关的二元情况的定理。

定理1
假设我们有一个形式为 \eqref{eq11} 的内核学习问题。设 $\kappa: \mathcal{X} \times \mathcal{Y} \to \mathbb{R}$ 为 RKBS 上 $\mathcal{B}_\mathcal{X}$ 和 $\mathcal{B}_\mathcal{Y}$ 的再生内核，满足定义1 和 定义2。然后，给定 $\mathcal{B}_\mathcal{X}$ 和 $\mathcal{B}_\mathcal{Y}$ 的一些条件（参见附录B），正则化经验风险最小化问题 \eqref{eq11} 就有一个唯一的解法数据对 $(f^_, g^_)$，具有以下性质：

$$\iota(f^\ast)=\sum\limits^{n_x}_{i=1}\xi_i\kappa(x_i,\cdot);\quad \iota(g^\ast)=\sum\limits^{n_y}_{j=1}\zeta_j\kappa(\cdot,y_j) \tag{12}\label{eq12}$$

其中 $\iota(f)$ (或者 $\iota(g)$) 表示 $f$ (resp. $g$) 范数的 Gateaux 导数，约定 $\iota(0) \triangleq 0$，且有 $\xi_i,\zeta_j \in \mathbb{R}$。

证明见附录B。

5.2 一个新的近似核学习问题和通用逼近定理

按照表示定理的建议，寻找内核学习问题（如 \eqref{eq10} 或 \eqref{eq11} 形式的 \eqref{eq12} 解决方案的缺点是它们很难扩展到大型数据集。众所周知，对于 RKHS 学习问题，找到与内核评估相乘的标量系数需要花费大约数据集大小三次方的时间，而查询模型需要线性时间。最流行的一类近似技术基于所谓的 Nystrom 方法，它构造核 Gram 矩阵的低阶近似并求解由该近似生成的问题。最近的一项工作已将 Nystrom 方法扩展到 RKKS 学习。

在本节中，我们将 Transformer 学习问题描述为一类新的近似核方法——可以称之为“蒸馏”方法。我们现在正式陈述这个想法。

命题2（二进制核学习问题的参数化近似求解）
考虑定义3中二进制内核学习问题的陈述，我们想找到解决方案对 $(f^\ast, g^\ast)$ 的近似值。特别地，我们会说我们想要一个近似值 $\hat \kappa: \mathcal{X} \times \mathcal{Y} \to \mathbb{R}$ 这样就有：

$$\hat{\kappa}(x,y)\approx \langle f^\ast_{\Phi_{\mathcal{Y}}(y)},g^\ast_{\Phi_{\mathcal{X}}(x)}\rangle_{\mathcal{B}_{\mathcal{X}}\times\mathcal{B}_{\mathcal{Y}}} \tag{13}\label{eq13}$$

对于所有 $x \in \mathcal{X}$ 和 $y \in \mathcal{Y}$ 都成立。

比较 \eqref{eq13} 和 \eqref{eq6} 提出了一个解决方案：学习一个近似 $\kappa$ 的函数 $\hat \kappa$。特别是，\eqref{eq6} 建议学习特征映射的显式近似，即

$$\hat{\kappa}(x,y)\approx\langle f^\ast_{\Phi_{\mathcal{Y}}(y)},g^\ast_{\Phi_{\mathcal{X}}(x)}\rangle_{\mathcal{B}_{\mathcal{X}}\times\mathcal{B}_{\mathcal{Y}}}$$

事实上，Transformer q-k映射正是这样做的。也就是说，虽然命题1中概述的 Transformer 核计算是有限维的，但它实际上可以近似潜在的无限维最优解 $(f^\ast, g^\ast)$，其特征在于定理1。下面证明这一事实。

定理2
设 $\mathcal{X} \subset \mathbb{R}^{d_t}$ 和 $\mathcal{Y} \subset \mathbb{R}^{d_s}$ 是紧致的； $t \in \mathcal{X}, s \in \mathcal{Y}$; 并设 $q_\ell: \mathcal{X} \to \mathbb{R}$ 和 $k_\ell: \mathcal{Y} \to \mathbb{R}$，且 $\ell=1, \dots, d$ 是两层神经网络，其中 $ m$ 是隐藏单元个数。然后，对于任何连续函数 $F: \mathcal{X} \times \mathcal{Y} \to \mathbb{R}$ 和 $\epsilon >0$，存在整数 $m, d >0$ 使得：

$$\bigg |F(t,s)-\sum^d_{l=1}q_l(t)k_l(s) \bigg |< \epsilon,\quad \forall t\in\mathcal{X},s\in\mathcal{Y} \tag{14}\label{eq14}$$

证明详见附录C。

我们现在概述定理2与Transformer的关系。如果我们将两层神经网络 $\{q_\ell\}_{\ell=1}^d$ 和 $\{k_\ell\}_{\ell=1}^d$ 的输出连接成$d$ 维向量 $q: \mathbb{R}^{d_t} \to \mathbb{R}^d$ 和 $k: \mathbb{R}^{d_s} \to \mathbb{R}^d$，然后点积 $q(t)^Tk(s)$ 由 \eqref{eq14} 中的和表示，可以逼近 $\mathcal{X} \times \mathcal{Y}$ 上的任何实值连续函数。减去通用逼近定理应用中的常见警告（即，在实践中，输出元素共享隐藏单元而不是独立单元），这个点积正是注意力的对数 $a_{ij}$ 的计算结果，即 $F(t,s) \approx \log \kappa(t,s)$ 对于 \eqref{eq14} 中的 $F$ 和 \eqref{eq9} 中的 $\kappa$ 逼近直到一个比例常数 $\sqrt{d}$。

由于注意力对数和 Transformers 中使用的求幂q-k内核之间的指数映射是一对一的映射，如果我们取 $F(t, s) = \log \langle f^\ast_{\Phi_\mathcal{Y}(s)},g^\ast_{\Phi_\mathcal{X}(t)}\rangle_{\mathcal{B_{\mathcal{X}}\times\mathcal{B_{\mathcal{Y}}}}}$，那么我们可以使用 Transformer 的点积注意力很好地逼近任意 RKBS 中的最优解。

基于注意力的深度神经网络的核心思想是通过随机梯度下降学习 $q_\ell$ 和 $k_\ell$ 的参数表示。与传统的基于表示定理的学习函数不同，基于注意力的内核机器（如深度Transformer）的训练时间（通常，但没有保证）随数据集大小呈亚立方体缩放，而无论数据集大小如何，评估时间都保持不变。

6，取幂的点积对Transformer来说是必不可少的吗？

我们研究了具有经典内核机器中使用的多个内核 Transformer 的修改，训练了两个标准的机器翻译数据集和两个标准的情感分类任务。对于机器翻译，IWSLT14 DE-EN 是一个相对较小的数据集，而 WMT14 EN-FR 是一个相当大的数据集。对于情感分类，考虑 SST-2 和 SST-5。保留标准的非对称查询和关键特征映射，即 $q = W^Qt$ 和 $k = W^Ks$，并且只修改内核 $\kappa : \mathbb{R}^d \times \mathbb{R}^d \to \mathbb{R}_{\geq 0}$。下面，$\tau >0$ 和 $\gamma \in \mathbb{R}$ 是每个头学习的标量。

我们感兴趣的内核是：

• (缩放)取幂点积 (EDP)，$\kappa(q,t) = \exp(q^Tk/\sqrt{d})$，即标准 Transformer 内核；
• 径向基函数 (RBF) 内核，$\kappa(q,t) = \exp(|-{\tau}/\sqrt{d} (q - k)|^2_2)$，其中 $| \cdot |_2$ 是标准的 2-范数。众所周知，RBF 内核是取幂点积的规范化版本，规范化使其具有平移不变性；
• vanilla L2 距离，$\kappa(q,t) = {\tau}/\sqrt{d} | q - k |_2$;
• 交集内核的指数版本，$\kappa(q,t) = \exp(\sum_{\ell=1}^d \min( q_\ell, k_\ell ))$。交集内核的对称版本在计算机视觉应用的内核机器中很流行，通常被描述为具有关联的 RKHS，它是函数空间 $L^2$ 的子空间（即，在具有连续函数的特征空间的意义上，它是无限维的，与 EDP和RBF的无限维无限级数相反）；
• 一个二次多项式内核，$\kappa(q,t) = ( 1/\sqrt{d} q^Tk + \gamma)^2$。

附录D中提供了完整的实施细节。

机器翻译的结果显示在表1中，几个结果脱颖而出。首先，据称具有无限维特征空间的取幂点积、RBF 和取幂交集核确实比具有低维特征映射的核（如二次核）表现更好。事实上，RBF 和 EDP 内核的性能大致相同，这表明深度 Transformer 可能不需要使 RBF 内核优于经典内核机器中的 EDP 的平移不变性。有趣的是，在 IWSLT14 DE-EN 上，（非正统的）取幂交集内核与 EDP 和 RBF 内核的性能大致相同，但在 WMT14 EN-FR 上稍差。如前所述，EDP 和 RBF 核具有无穷级数的特征空间，而交集核对应于连续函数的特征空间。在这两个数据集上，二次核比最好的无限维核表现稍差，而 L2 距离表现明显更差。

情绪分类的结果显示在表2中。与机器翻译实验不同，无限维内核在此任务上并不严格优于有限维内核。事实上，这里明显的输家是取幂的交集内核，而在机器翻译中表现最差的 L2 距离与表现最好的内核的标准差不超过一个标准差。然而，值得注意的是，情感分类测试准确度的差异意味着不可能在此任务上选择具有统计显着性的“最佳”。内核间的小变化可能与这个问题的相对简单性（以及数据集的相对较小）与机器翻译有关：也许不需要无限维的特征空间来在更简单的上获得 Transformer 级别的性能问题。

值得注意的是，取幂的点积内核（同样是标准的 Transformer 内核）始终保持高性能。这可能是他们所享有的通用近似属性的实际用途的实验证据（参见定理2）。

内核之间相对较小但具有统计显着性的性能差异让人联想到神经网络的激活函数（ReLU、ELU 等）的相同现象。此外，与 SST 情感分析任务的小得多的性能差异相比，机器翻译的内核间性能差异很大，表明不同复杂性问题的不同表征需求。总的来说，这些结果表明内核选择可能是 Transformer 网络的一个额外设计参数。

7，结论

在本文中，我们将经典内核方法与最先进的 Transformer 网络联系起来。除了对开发新的 RKBS 表示定理和其他核理论的理论兴趣之外，我们对什么可能使 Transformers 起作用有了新的认识。

我们的实验结果表明，Transformer 内核的无限维数使其成为应用中的一个很好的选择，类似于 RBF 内核如何成为标准选择，例如支持向量机。我们的工作还揭示了 Transformer 研究的新途径。例如，我们的实验结果表明，Transformer 内核的选择与神经网络设计中的激活函数具有相似的设计选择。

新的开放研究问题包括：

• (1) 指数点积是否应该始终是首选，或者不同的内核是否更适合不同的任务（参见 GELU 最近如何在 Transformers 中替代 ReLU 变得非常流行）；
• (2) 用于结构化预测的向量值内核与例如多个注意力头之间的任何关系；
• (3) 将 Transformer 类型的深度内核学习器扩展到非欧几里德数据（使用，例如，图形内核或流形上的内核）。