言語の再帰性を実現する方法〜Attention, GNN, 関数マップ

自然言語のみならず様々なデータを取り込み、変換し、解釈しているように見えるニューラルネットの構成であるTransformerとその構成要素であるSelf Attentionの意味と機能には多くの注目が集まっています。
ここでは言語の単語間の参照関係や自己言及性を表現できる他のモデルと比べて類似点、相違点をまとめます。

グラフニューラルネット(GNN)とTransformerの類似性

グラフを処理するニューラルネットアーキテクチャとしてはグラフニューラルネット(GNN)というものがあります。
GNNはfoward計算としてグラフの頂点にある値を重み付けして隣接する頂点に伝搬させる処理を層ごとに行うもので、CNNは格子状に並んだピクセルに対するGNNとして見ることができます。
ノードiに隣接するノード$j \in Nei(i)$から伝搬する重みを
$h_i^{l+1}=\sigma(h_i^l+\sum_{j \in Nei(i)}w_{ij}^l h_i^l)$

という形です。
https://graphdeeplearning.github.io/post/transformers-are-gnns/
ではGNNとTransformerの類似性が語られています。

Transformerの構成は
$head_k=Attention(Q^lh_j^l,K^lh_j^l,V^lh_j^l)$
$h=concat(head_1,head_2,...,head_k)O^l$
$Attention(q,k,v):=softmax(q^Tk/\sqrt{d})v$
(Sはwordの集合,lは層のindex,jはのindex)

となっていて行列wとして
$w_{ij}:=softmax( (Qh_j^l) \cdot Kh_j^l)$
とおくと
$h_i^{l+1}=\sum_{j\in S}w_{ij}(V^lh_j^l)$
と書けてGNNと比べるとTransformerのself attention部分WはGNNの重み部分が層ごとの発展で動的に変化しているような見方ができます。
実際に以下のコードのように各層で共通なランダムな初期値行列Q,K,Vを置くとhとwはトークン間の関係を表すグラフのノードとエッジであり層を経るごとに動的に変化します。以下のnotebookでその様子を見ることができます。

https://arxiv.org/abs/1906.04341
ではBERTのAttensionでの単語間の依存関係が図示されていますがあくまで単語単位でありそれによって構成される句や節の単位の関係までは表現することはできません。

関数マップとグラフ

より直接的に要素の集合間の参照関係や自己言及性を実現する方法として関数マップ(functional dynamics)という手法が提唱されています。
https://www.kurims.kyoto-u.ac.jp/~kyodo/kokyuroku/contents/pdf/1244-23.pdf
http://chaos.c.u-tokyo.ac.jp/papers/others/kataoka-BS2000.pdf

これは関数fを自身に適用した関数f'へ移す写像をパラメーターεを用いて
$f'(x)=f\cdot f(x)+\epsilon f(x)$
と定義したもので関数fの写像の繰り返しによる挙動は離散的な点集合に作用する場合は図のように出発点と到達点を結んだグラフがステップごとに切り替わる様子が見られ(点の数が素数の場合は$f^n$は全ての点間を結ぶがここでは$f^{n^2}$なのでその限りではない)、1次元線分の場合には入出力を2次元のグラフとしてプロットすることができ、$\epsilon \neq 0$のときは不動点(図のtype I,$f(x^I)=x^I$)と不動点に移されるような点(type II,$f(x^{II})=x^I$)、さらにtype IIに移されるような点と階層的な構造を持ち得ます。

Functional Dynamics I:Articulation Processより引用

Natural Language from function dynamicsより引用
また初期関数の形が対角線をまたぐようになっていると適用により関数は折り畳まれ、複雑な形に発展していきます。

Functional Dynamics I:Articulation Processより引用

挙動の一部を再現したnotebookは以下に有ります。

関数マップとself attention(の一部)の等価性

この関数に関数自身を適用する演算はself attentionに類似するところがありますが実際にattentionの構造は関数マップを含むことが示せます。
self-attention-from-scratchの図

で簡単のため$d=d_q=d_k=d_v$とし、xは各行に非零の値を1列しか持たないような形とします。するとその要素は2次元平面に1次元関数のグラフを描いた形になります。下図のように赤い線で示された関数fのグラフにfを適用しようとすると書くx座標に対して矢印のようにf(x),f○f(x)を辿って値をプロットすることができます。1つ山の関数は2つ山になりさらに4つ、8つとなっていきます。

さらに$W_v$を対角行列とするとVとattention map Aの積を考えます。このとき図のようにAの要素もVと同様な形状をしていれば行列積によってVのグラフを折りたたむような出力が得られます。これはAの元になっているQの形状をKで引き伸ばすような処理によって得られます。

これによってattentionにおいて自己参照的な構造が得られることになります。$W_q$は単位行列でありKでその形をnxnに引き伸ばすようにすれば良さそうですがもともとのKey,Queryの意味付けと比べると消極的であるようにも見えます。別の言い方をするとattentionでは1回の繰り返しでより多くの自己参照をしていると言えます。関数マップにおけるεの調整もモデル内部で行っていると言えるかもしれません。

またここでの例では層ごとに同じ重みパラメーターを用いるものとしてGNN,関数マップとの類似性、等価性を見てきましたがattentionを用いたネットワークでは層ごとに異なるパラメーターを用いています。

関数マップの拡張

以上に書いたように入力行列xを1行に1つの非零要素しか持たない制約を外すことができます。またattentionのように3入力を用いた変換によって計算の能力に違いが見られると考えられます。

類似点、相違点の整理

	GNN	Self Attention	関数マップ
Wの変化	学習により固定	固定+初期値で自発的に変化	初期関数に依存して動的に変化｜
参照	ノード単位	領域単位	領域単位

課題

• in-context learningの位置づけ
• 文脈の保存のされ方の可視化
• Key, Queryの関数マップでの位置づけ、または関数マップの拡張(変動するε)
• 階層的な構造がなぜ画像(Vision Transformerでも有効なように見えるのか)
• 層を進めることによる忘却の限界、または不確定性

関連

RNNとの関係
トランスフォーマーは重み$w_n$を状態としたRNNです
https://joisino.hatenablog.com/entry/2024/09/30/173416

力学系の軌道としてのBERTの出力を捉えた研究
http://arxiv.org/abs/2106.03181

Transformerの要素attentionとMLPの動作の意味について論じられています
https://www.youtube.com/watch?v=N-0eFoQYkrs&t=349s

https://lifeiscomputation.com/transformers-are-not-turing-complete/

本

https://www.amazon.co.jp/d/4065347823

https://gihyo.jp/book/2024/978-4-297-14393-0