言語の再帰性を実現する方法〜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)$
$Attention(q,k,v):=softmax(q^Tk/\sqrt{d})v$
$h=concat(head_1,head_2,...,head_k)O^l$
(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をパラメーターεを用いて
$f'(x)=F(f,\epsilon)(x)$

(例えば線形補間 $f'(x)=(1-\epsilon)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で引き伸ばすような処理によって得られます。

(出力Zの水色の点がある行を計算したい場合Aの水色の行とVのそれぞれの列との内積を取ります。この場合Aの水色の行の非零要素は水色の点しかないので、その列数(横←→)と同じ行数に非零要素があるVの列(水色)との内積しか非零になる要素はなく、結果としてAの水色と同じ行、Vの水色と同じ列のZの要素のみが非零となる)

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

上で挙げた例では各行の1つの要素のみが非零の場合のみを説明しましたが、複数の要素が非零の多価関数、確率分布関数(確率過程)を変換する写像と捉えることもできます。(Transformerでは確率分布の正規化に類似した処理をsoftmax,$\sqrt{d}$での割り算で行っています。)

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

関数マップの拡張

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

類似点、相違点の整理

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

課題

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

関連

RNNとの関係

トランスフォーマーは重み$w_n$を状態としたRNNです

この「圧縮」と「汎化」と「効率」の関係はモデルの振る舞いを考えるうえでとても重要です。トランスフォーマーを 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

Transformerはチューリング完全だという主張の論文を一つ一つ批判しているブログ

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

追記

arxivに出たそうです。
https://www.arxiv.org/abs/2506.22084

Dyck言語で性質を捉える

Transformerの階層的言語をとらえる能力をはDyck言語という入れ子になった括弧による文字列を学習によって認識、生成できるかを測定した関連研究
https://www.arxiv.org/abs/2105.11115

https://www.arxiv.org/abs/1906.06755
上記論文には２〜３層によるStackを作った具体的な生成方法もある。最初のAttentionの層で入れ子の深さを数え、次の層で括弧の対応を判定する。

https://x.com/issei_sato/status/1846784935388225934
https://arxiv.org/abs/2410.12413

その他

Attention自体が階層的な場合性能は向上する
https://www.cs.cmu.edu/~hovy/papers/16HLT-hierarchical-attention-networks.pdf

https://chatgpt.com/share/68692f99-744c-8008-800e-9ea5578fd468