古典的なDot product Attentionは大きな空間と時間の複雑さを持ち、効果は優れているが、画像と動画の入力データ量はテキストよりも多いことが多いため、これらの古典的なAttentionは高解像度画像での応用が制限されます。本論文では、これらの問題を解決し、パフォーマンスに大幅な劣化が生じないように、新しい線形のAttentionモジュールを提案します。

この論文の主な貢献点は次の通りです：
1) 新しい線形Attention方式を提案し、計算複雑度を𝑂(𝑁^2)から𝑂(𝑁)まで低減します
2) このAttentionメカニズムにより、Attentionとネットワークの組み合わせがより汎用的で柔軟になります；
3) 意味分割タスクにおいて、このAttentionメカニズムを導入することで、複数のベースラインでパフォーマンスが向上しました。

1 方法論

A.ドット積注意の定義

给定一个输入的特征向量 X=left[boldsymbol{x}_{1}, cdots, boldsymbol{x}_{N}right] in mathbb{R}^{N times D_{x}}，其中 N 代表特征长度，D_x 代表特征维度。那么 Dot-Product Attention 通过点乘变换矩阵 boldsymbol{W}_{q} in mathbb{R}^{D_{x} times D_{k}}、boldsymbol{W}_{k} in mathbb{R}^{D_{x} times D_{k}} 以及 boldsymbol{W}_{v}= mathbb{R}^{D_{x} times D_{v}} 分别生成 Query Matrix、Key Matrix と Value Matrix ，其公式如下： begin{aligned} &boldsymbol{Q}=boldsymbol{X} boldsymbol{W}_{q} in mathbb{R}^{N times D_{k}} \ &boldsymbol{K}=boldsymbol{X} boldsymbol{W}_{k} in mathbb{R}^{N times D_{k}} \ &boldsymbol{V}=boldsymbol{X} boldsymbol{W}_{boldsymbol{v}} in mathbb{R}^{boldsymbol{N} times boldsymbol{D}_{v}} end{aligned}tag{1} ここで、Q と K の次元は同じでなければなりません。 在此基础上，引入一个归一化函数 rho 来度量 boldsymbol{q}_{i}^{T} in mathbb{R}^{D_{k}} 和 boldsymbol{k}_{j} in mathbb{R}^{D_{k}} 的相似度 rholeft(boldsymbol{q}_{i}^{T} boldsymbol{k}_{j}right) in mathbb{R}^{1}。而 Scaled Dot-Product Attention 就是相当于以 rholeft(boldsymbol{q}_{i}^{T} boldsymbol{k}_{j}right) in mathbb{R}^{1} 为权重对 v_j 做加权平均。Dot-Product Attention 对于整个矩阵的定义如下： D(boldsymbol{Q}, boldsymbol{K}, boldsymbol{V})=rholeft(boldsymbol{Q} boldsymbol{K}^{T}right) boldsymbol{V}tag{2} 最も一般的に使用される正規化関数は softmax です： rholeft(boldsymbol{Q}^{T} boldsymbol{K}right)=operatorname{softmax}_{text{row }}left(boldsymbol{Q} boldsymbol{K}^{T}right)tag{3} に対して boldsymbol{Q} in mathbb{R}^{N times D_{k}} と boldsymbol{K}^{T} in mathbb{R}^{D_{k} times N} ，boldsymbol{Q}boldsymbol{K}^{T} in mathbb{R}^{N times N} したがって rho の時間および空間の複雑さは次のとおりです 𝑂(𝑁^2)。

B.Generalization of Dot-Product Attention Based on Kernel

Kernel に基づいて Dot-Product Attention の一般化を定義します。softmax 形式の正規化関数に関しては、次のように書くことができます： D(boldsymbol{Q}, boldsymbol{K}, boldsymbol{V})_{i}=frac{sum_{j=1}^{N} e^{boldsymbol{q}_{i}{ }^{T} boldsymbol{k}_{j}} boldsymbol{v}_{j}}{sum_{j=1}^{N} e^{boldsymbol{q}_{i}{ }^{T} boldsymbol{k}_{j}}}tag{4} e^{boldsymbol{q}_i^{top}boldsymbol{k}_j} これは v_j の重み付き平均に対する重みです。 该公式可以更进一步一般化定义为： begin{gathered} D(boldsymbol{Q}, boldsymbol{K}, boldsymbol{V})_{i}=frac{sum_{j=1}^{N} operatorname{sim}left(boldsymbol{q}_{i}, boldsymbol{k}_{j}right) boldsymbol{v}_{j}}{sum_{j=1}^{N} operatorname{sim}left(boldsymbol{q}_{i}, boldsymbol{k}_{j}right)} \ operatorname{sim}left(boldsymbol{q}_{i}, boldsymbol{k}_{j}right) geq 0 end{gathered}tag{5} 显然当定义 operatorname{sim}left(boldsymbol{q}_{i}, boldsymbol{k}_{j}right)=e^{boldsymbol{q}_{i}{ }^{T} boldsymbol{k}_{j}} 时，该式和标准 softmax 的 Attention 公式等价。この形式の注意は CV では一般に Non-Local ネットワークとも呼ばれます。 显然如果直接去掉指数定义 text{sim}(boldsymbol{q}_i, boldsymbol{k}_j) = boldsymbol{q}_i^{top}boldsymbol{k}_j 不满足非负性质，为了完成这一点可以考虑加入核函数，更改定义为： text{sim}(boldsymbol{q}_i, boldsymbol{k}_j) = phi(boldsymbol{q}_i)^{top} varphi(boldsymbol{k}_j)tag{6} そうすると、Attention の公式を再定義できます： D(boldsymbol{Q}, boldsymbol{K}, boldsymbol{V})_{i}=frac{sum_{j=1}^{N} phileft(boldsymbol{q}_{i}right)^{T} varphileft(boldsymbol{k}_{j}right) boldsymbol{v}_{j}}{sum_{j=1}^{N} phileft(boldsymbol{q}_{i}right)^{T}varphileft(boldsymbol{k}_{j}right)}=frac{phileft(boldsymbol{q}_{i}right)^{T} sum_{j=1}^{N} varphileft(boldsymbol{k}_{j}right) boldsymbol{v}_{j}^{T}}{phileft(boldsymbol{q}_{i}right)^{T} sum_{j=1}^{N} varphileft(boldsymbol{k}_{j}right)}tag{7}

C.Linear Attention Mechanism

以前の多くの線形化方法とは異なり、本論文では一次テイラー展開を用いて線形化します： e^{boldsymbol{q}_{i}^{T} boldsymbol{k}_{j}} approx 1+boldsymbol{q}_{i}{ }^{T} boldsymbol{k}_{j}tag{8} 为了保证 boldsymbol{q}_{i}{ }^{T} boldsymbol{k}_{j} geq-1 我们将 boldsymbol{q}_{i} と boldsymbol{k}_{j} を l2 ノルムにする： operatorname{sim}left(boldsymbol{q}_{i}, boldsymbol{k}_{j}right)=1+left(frac{boldsymbol{q}_{i}}{left|boldsymbol{q}_{i}right|_{2}}right)^{T}left(frac{boldsymbol{k}_{j}}{left|boldsymbol{k}_{j}right|_{2}}right) .tag{9} Attention の公式は次のように書き直すことができます： D(boldsymbol{Q}, boldsymbol{K}, boldsymbol{V})_{i}=frac{sum_{j=1}^{N}left(1+left(frac{boldsymbol{q}_{i}}{left|boldsymbol{q}_{i}right|_{2}}right)^{T}left(frac{boldsymbol{k}_{j}}{left|boldsymbol{k}_{j}right|_{2}}right)right) boldsymbol{v}_{j}}{sum_{j=1}^{N}left(1+left(frac{boldsymbol{q}_{i}}{left|boldsymbol{q}_{i}right|_{2}}right)^{T}left(frac{boldsymbol{k}_{j}}{left|boldsymbol{k}_{j}right|_{2}}right)right)}=frac{sum_{j=1}^{N} boldsymbol{v}_{j}+left(frac{boldsymbol{q}_{i}}{left|boldsymbol{q}_{i}right|_{2}}right)^{T} sum_{j=1}^{N}left(frac{boldsymbol{k}_{j}}{left|boldsymbol{k}_{j}right|_{2}}right) boldsymbol{v}_{j}^{T}}{N+left(frac{boldsymbol{q}_{i}}{left|boldsymbol{q}_{i}right|_{2}}right)^{T} sum_{j=1}^{N}left(frac{boldsymbol{k}_{j}}{left|boldsymbol{k}_{j}right|_{2}}right)}tag{10} ベクトル形式を使用した記述： D(boldsymbol{Q}, boldsymbol{K}, boldsymbol{V})=frac{sum_{j} boldsymbol{V}_{i, j}+left(frac{boldsymbol{Q}}{|boldsymbol{Q}|_{2}}right)left(left(frac{boldsymbol{K}}{|boldsymbol{K}|_{2}}right)^{T} boldsymbol{V}right)}{N+left(frac{boldsymbol{Q}}{|boldsymbol{Q}|_{2}}right)sum_{j}left(frac{boldsymbol{K}}{|boldsymbol{K}|_{2}}right)_{i, j}^{T}}tag{11} これら sum_{j=1}^{N}left(frac{boldsymbol{k}_{j}}{left|boldsymbol{k}_{j}right|_{2}}right) boldsymbol{v}_{j}^{T} と sum_{j=1}^{N}left(frac{boldsymbol{k}_{j}}{left|boldsymbol{k}_{j}right|_{2}}right) は事前に計算し、各クエリで再利用できます。

2 実験結果

著者は一般的な幾つかの画像分割フレームワークに提案された Linear Attention を導入し、ベースラインと比較してポイントアップの結果を得ました。これは提案された構造が普遍的な有効性を持っていることを示しています。

論文 & ソースコード

論文 1636966378-Linear Attention Mechanism- An Efficient Attention for Semantic Segmentation ソースコード https://github.com/lironui/Linear-Attention-Mechanism https://github.com/lironui/MAResU-Net https://github.com/lironui/MACU-Net

参考文献

[1] https://kexue.fm/archives/7546