Nyströmformer：透過 Nyström 方法在線性時間與記憶體中近似自注意力

TL;DR

Nyströmformer 是一種高效的 Transformer 變體，透過近似標準自注意力機制以達到線性時間與記憶體複雜度 $O(n)$，取代傳統的二次複雜度 $O(n^2)$。這使得模型能夠處理顯著更長的輸入序列，同時在自然語言處理與電腦視覺任務上保持競爭性的表現。

Nyström 方法於矩陣近似

Nyström 方法透過抽樣 $m$ 個列與行來近似大型矩陣 $P^{n imes n}$。將這些抽樣排列成區塊矩陣後，原始矩陣被分割為四個子矩陣：$A_{P}$（$m imes m$）、$B_{P}$（$m imes (n - m)$）、$F_{P}$（$(n - m) imes m$）以及 $C_{P}$（$(n - m) imes (n - m)$）。

由於 $A_{P}$、$B_{P}$ 與 $F_{P}$ 的元素可透過抽樣取得，未知的子矩陣 $C_{P}$ 可以估計為：

$$C_{P} = F_{P} A_{P}^{+} B_{P}$$

其中 $+$ 代表 Moore-Penrose 偽逆。得到的 Nyström 近似 $\hat{P}$ 以三個矩陣的乘積表示，降低了計算完整矩陣的計算負擔。

將 Nyström 套用於自注意力

標準自注意力依賴於 softmax 矩陣 $S = \text{softmax}(\frac{QK^T}{\sqrt{d}})$。直接將 Nyström 方法套用於 $S$ 是不可行的，因為計算 softmax 矩陣的單一列需要知道所有其他列以計算列方向的 softmax 分母。

為了解決此問題，Nyströmformer 從查詢 ($Q$) 與鍵 ($K$) 中抽樣「landmarks」（Nyström 點），而非從產生的 softmax 矩陣抽樣。模型基於查詢 landmarks $\tilde{Q}$ 與鍵 landmarks $\tilde{K}$ 定義了三個矩陣：

  • $\tilde{F} = \text{softmax}(\frac{Q\tilde{K}^T}{\sqrt{d}})$
  • $\tilde{A} = \text{softmax}(\frac{\tilde{Q}\tilde{K}^T}{\sqrt{d}})^{+}$
  • $\tilde{B} = \text{softmax}(\frac{\tilde{Q}K^T}{\sqrt{d}})$

近似的 softmax 矩陣 $\hat{S}$ 隨後計算為 $\hat{S} = \tilde{F} \tilde{A} \tilde{B}$。將此近似與值 ($V$) 相乘，模型即可在不計算完整 $QK^T$ 乘積的情況下，實現線性的自注意力近似。

Landmark 選取與實作

Nyströmformer 透過區段均值來構建 $\tilde{Q}$ 與 $\tilde{K}$。將 $n$ 個 token 分成 $m$ 個區段，計算每個區段的平均值作為 landmark。研究顯示，即使僅使用 32 或 64 個 landmark，也能在 $n = 4096$ 或 $8192$ 的序列長度下提供具競爭力的表現。

實作細節

  • Depthwise Convolution（深度可分卷積）: 架構包含一個 1D 深度可分卷積（DConv）作為加到 values 上的 skip connection。
  • Complexity（複雜度）: 此方法成功避免 $O(n^2)$ 複雜度，使得在長序列上具備高效能。

在 Hugging Face 上的可用性與使用方式

Nyströmformer 可透過 Hugging Face Transformers 套件用於遮蔽語言模型（MLM）。提供四個基於序列長度的檢查點：nystromformer-512、nystromformer-1024、nystromformer-2048 與 nystromformer-4096。

使用者可透過 NystromformerConfig 中的 num_landmarks 參數來控制 landmark 數量 $m$。模型可使用 NystromformerForMaskedLM 類別或高階的 pipeline API（如 fill-mask 任務）進行部署。

Sources