集合の順列不変表現 - yuuk1's Digital Garden

# 集合の順列不変表現 ## 定義集合の順列不変表現は、入力要素の並びを入れ替えても集合全体の出力が変わらない表現である。集合$X=\{x_1,\ldots,x_n\}$と任意の順列$\pi$に対し、集合レベルの符号化関数$f$は$f(x_1,\ldots,x_n)=f(x_{\pi(1)},\ldots,x_{\pi(n)})$を満たす必要がある。(Source: [[@2026__30papers__Order Matters Sequence to Sequence for Sets]]) ## 縮約と可変長メモリ各要素の埋め込みを和・平均・最大値で縮約する方法は順列不変である。ただし集合の大きさにかかわらず一つの固定次元ベクトルへ直ちに圧縮するため、要素数に応じて記憶容量を増やしにくい。Read-Process-and-Writeは各要素を別々のメモリベクトルとして保持し、内容ベースアテンションで反復的に読み出すことで、可変長メモリと順列不変性を両立させる。(Source: [[@2026__30papers__Order Matters Sequence to Sequence for Sets]]) ## 内容ベースアテンションによる不変性クエリ$q_t$とメモリ$m_i$からスコア$e_{i,t}$を計算し、ソフトマックス重み$a_{i,t}$による読み出し$r_t=\sum_i a_{i,t}m_i$を作る。メモリの並びを置換するとスコアと重みも同じように置換されるため、総和$r_t$は変わらない。反復後の状態を集合全体の表現として使えば、入力順序に依存しない文脈をデコーダへ渡せる。(Source: [[@2026__30papers__Order Matters Sequence to Sequence for Sets]]) ## 不変性と同変性集合全体の分類・回帰では、要素を入れ替えても出力が変わらない不変性が必要である。一方、各要素に対応する出力を返す場合は、入力の置換に合わせて出力も置換される同変性が必要になる。[[GNN同変性]]で扱うノード順序の対称性は後者を含み、集合表現と同じ置換群$S_n$を異なる出力粒度で扱う。(Source: [[@2026__30papers__Order Matters Sequence to Sequence for Sets]], [[joisino-ICLR-2024-GNN]]) ## 出力集合との違い入力集合の順列不変性は、同じ集合をどの順番で提示しても内部表現を同じにする要請である。出力集合を自己回帰的に生成する場合は、同じ集合に複数の等価な系列が対応するため、確率をどの系列化へ割り当てるかが別の問題になる。Order Mattersは、学習中に良い出力順序を探索することでこの等価類を狭めた。(Source: [[@2026__30papers__Order Matters Sequence to Sequence for Sets]]) ## 横断的知見 - Order Mattersの内容ベースアテンションは、位置情報を与えなければメモリの置換に不変である。一方、Transformerは系列順序をアテンションだけでは表現できないため、位置エンコーディングを明示的に加える。両者を合わせると、アテンションは本質的に順序を仮定する演算ではなく、位置情報を除けば集合、加えれば系列を扱える構成要素だと分かる。(Source: [[@2026__30papers__Order Matters Sequence to Sequence for Sets]], [[@2017__NeurIPS__Attention Is All You Need]]) - Order Mattersは集合全体の状態を順列不変にし、GNNはノードごとの状態を置換同変に保つ。どちらも同じ置換対称性を利用するが、必要な性質は出力が集合レベルか要素レベルかで不変性と同変性に分かれる。(Source: [[@2026__30papers__Order Matters Sequence to Sequence for Sets]], [[joisino-ICLR-2024-GNN]]) ## 未解決の問い - 和・平均による縮約、反復アテンション、自己アテンション、メッセージパッシングは、集合サイズ・計算量・表現力の条件ごとにどう使い分けるべきか。 - 順列不変な入力表現と、自己回帰的な出力順序探索をエンドツーエンドで同時に最適化すると、訓練はどの程度安定するか。 - 長い集合でRead-Process-and-Writeの完全一致精度が急落した原因は、LSTMの容量、反復回数、ポインター復号、訓練分布のどこにあるか。 - 出力集合の複数の正解順序へ確率を割り当てる方法は、順序を一つ選ぶ以外にどのような対称性を利用できるか。 ## 関連 - 原論文: [[@2026__30papers__Order Matters Sequence to Sequence for Sets]] - 系列モデル: [[Transformer]] - 要素レベルの置換対称性: [[GNN同変性]] - 著者: [[Oriol Vinyals]]、[[Samy Bengio]]、[[Manjunath Kudlur]] ## 出典 - [[@2026__30papers__Order Matters Sequence to Sequence for Sets]] - [[@2017__NeurIPS__Attention Is All You Need]] - [[joisino-ICLR-2024-GNN]]