群対称性を用いた深層学習
三内顕義

理研AIP/慶応大学

タスクにﬁtしたモデルの設計
タスクの数学的分類

対称性?

モデル設計

CNN、RNN、GNN etc..

実際のタスク

画像、時系列データ、グラフ etc..

今回の研究対象•

対称性（群を元にした）を持ったタスクに対する深層ニューラルネットモデルの研究•タスクが対称性を持つという事前知識の下、特別な深層ニューラルネットを使うことで少数サンプルでもワークする(Deep sets,NeurIPS2018)•

基本的に考える群は対称群（Sm)がベースとなる

同変性のあるタスク•

仲間外れ探し（Deep sets NeurIPS 2018)•

列ごとに一人だけ仲間外れがいる(他は二つの性質を共有）•

写真の順を変えると答えもそれに応じて変わる不変性のあるタスク

wikipedia[点群]より•

入力がポイントクラウド
である分類問題•点たちに順序づけをする必要があるが、その順番を変えても答えは変わらない

群論の復習

群とは
定義

集合Gは二項演算・を持つ、つまり任意のa, b ∈ Gに対しa ⋅ b ∈ Gが定まるとする。これが次の条件を満たす時、(G, ⋅ )を群という。
(1) 任意のa, b, c ∈ Gに対して(a ⋅ b) ⋅ c = a ⋅ (b ⋅ c).
(2) 単位元と呼ばれる元 e ∈ Gが存在し、任意のa ∈ Gに対してa ⋅ e = e ⋅ a = a.
(3) 任意のa ∈ Gに対してa −1 ∈ Gが存在しa ⋅ a −1 = a −1 ⋅ a = e.

群の例•

点の順序づけの置換群SM•３次元空間の回転群
SO(3)•wikipedia[点群]より正則行列のなす群GL(ℝ)

対称群Sm•SMの元はM点集合{1,..,M}の置換（全単射）を表す•

・は写像の合成

1 2 3 41 2 3 4,g =S の元は対応表を使って表すことができる。例: g1 =• M
(3 1 2 4) 2 (2 4 1 3)•gをSMの元とする時、g(i)でiの行き先を表すことにする（上の例ではg1(1) = 3, g2(3) = 1など）•

iとjを入れ替えるだけの置換（互換）を(i j)と書くことにする
例：(1 3) =1 2 3 4(3 2 1 4)

作用とは定義

Gを群、Xを集合とする。GがXに作用するとは、(1)任意のa ∈ Gと任意のx ∈ Xに対してa(x) ∈ Xが定まっていて、(2)単位元eに対してはe(x) = xであり、(3)任意のa, b ∈ Gに対して(a ⋅ b)(x) = a(b(x)) が成り立つことをいう。
•群GがXに作用している時、G ↷ Xと書くことにする

ベクトル空間への自然な作用
ベクトル空間の標準基底e1, . . , emに対し、g ⋅ ei = eg(i)とし、これを線形に拡張することで自然な作用が定義される。つまりベクトル(x1, . . , xM )とg ∈ Gに対し、
g ⋅ (x1, . . , xM ) = (xg−1(1), . . , xg−1(M))とする。
DNNの各層に対応するベクトル空間の場合、これはnodeの入れ替えに対応する不変/同変な関数
定義 (1)関数f : ℝM → ℝが置換不変とはf(g ⋅ (x1, . . , xM)) = f(x1, . . , xM )が全ての置換g ∈ SMについて成り立つことを言う.
(2)関数 f = ( f1, . . , fM) : ℝM → ℝM が置換同変とはf(g ⋅ (x1, . . , xM)) = g ⋅ [ f1(x1, . . , xM), . . , fM(x1, . . , xM)]⊤が全ての置換g ∈ Smについて成り立つことを言う.

置換同変なニューラルネット

置換同変な層
Lemma3(Deep sets): 関数 fΘ(x) = σ(Θx) ( Θ ∈ ℝM×M )が置換同変になるための必要十分条件はΘが以下の形に書けることである⊤⊤

Θ = λI + γ(11 ) λ, γ ∈ ℝ 1 = [1, . . . , 1] ∈ ℝ

M•

各層の変換が同変を仮定すると行列が2パラメータで具体的に書ける

同変深層ニューラルネット•

同変な層（のコピー）を積み重ねることで深層にする•

各層の変換が同変であることから深層が誘導する関数も同変となる

同変深層学習•

同変な深層NNはlem3より具体的なパラメータを持つため、このパラメータに対するback propagationを行うことで学習ができる•

結果として得られる関数は同変な関数となる•

同じ構造の場合、通常の深層ニューラルネットに比べて各層のコピー一つあたりM 2 → 2まで圧縮できている•

仲間外れ探し（前述）においてはtest accuracyが6.3%(CNN+fully conn.)から75%程度まで改善（CNN＋同変)置換不変なニューラルネット

Kolmogorov-Arnoldの表現定理
定理：連続関数f : [0, 1]M → ℝが置換不変関数になるための必要十分条件は次の形で表現できることである
f(x1, . . . , xM ) = ρ(M∑m=1ϕ(xm))

ここでρ : ℝM+1 → ℝとϕ : ℝ → ℝM+1は連続関数でϕはfによらない。
2M ⊤は具体的にϕ(x)=[1,x,x,.
.
,x] の形で書ける
ϕ••

この定理からϕを近似するパートとρを近似するパートで分けてNNを構成するのがDeep setsのアイデアf(x1, . . . , xM) = ρ(M∑

m=1の計算例

ϕ(xm))(1)f(x1, x2) = x1x2(x1 + x2 + 3)とする.
ϕ(x) = [x, x 2, x 3], ρ([u, v, w]) = uv − w + 3(u 2 − v)/2と置
くとρ(ϕ(x1) + ϕ(x2)) = f(x1, x2)が成り立つ.
(2)f(x1, x2, x3) = x1x2 x3 + x1 + x2 + x3とする。
ϕ(x) = [x, x 2, x 3], ρ(u, v, w) = (u 3 − 2w + 3uv)/6 + uと置
くとρ(ϕ(x1) + ϕ(x2) + ϕ(x3)) = f(x1, x2, x3)が成り立つ.f(x1, . . . , xM) = ρ(m∑i=1ϕ(xi))の深層ニューラルネット的解釈

x1

ϕx2ϕ.
.
.

.
.
.
xmϕ

Σ
ρ
ϕを近似するパートは全く同じDNNをとることができ全体として同変な層にできる

不変深層ニューラルネット
L1L2…

Ld•

Liは同変な層•mはmulti layer perceptron•

Σは軌道の和を取る関数

Σm不変深層学習•

Lの部分はlem3のパラメータがありmの部分は普通のパラメータがある。これらのパラメータに対しback propagationで学習可能•

結果として得られる関数は置換不変（Σの部分でそうなる）•

今回はLの部分のパラメータのみ圧縮されている

まとめ•

不変のケースも同変のケースも各層に対応する行列を制限することでDNNが表現する関数自体を不変/同変にした。

•

パラメータが具体的に与えられているため、その範囲で学習ができる。

•不変ケースは数学的背景があるが、同変ケースは同変な関数を近似できる保証がないのでは？

Universal approximation
theorem(Sannai-Takai-Matthieu)
定理2.2 GをSMの部分群とする。KをℝMのコンパクトな部分集合でGの作用で安定なものとする。任意の連続でG同変な写像F : K → ℝMと任意のε > 0に対し、（STMの意味での）G不変深層ニューラルネットHが存在し、∥F − H∥∞ < εとなる。
定義（STMの意味でのG不変深層ニューラルネット）
各層のノードの集合（ベクトル空間の基底集合）へのG作用を自然な作用ではなく、任意の作用まで一般化する。他は今までと同じ。

証明の方針••不変関数と同変関数の間にある対応を深層ニューラルネットレベルにリフトし、不変関数のUniversal approximationに帰着
不変関数の時のZaheerらの定理（SMのケース)あるいはMaronらの定理（有限群G)を適応する

同変関数の表現定理
系3.1(Sannai-Takai-Matthieu):写像F : ℝM → ℝMがSM-同変になるための必要十分条件はStab(1)-不変関数f : ℝM → ℝが存在し、F = ( f ∘ (1 1), f ∘ (1 2), . . . , f ∘ (1 M))⊤の形で書けること。ここで互換(i j)はℝM → ℝMの線形写像とみなしている。
•

Stab(1): 1を固定する置換のなすSMの部分群•

SM同変な関数は互換とStab(1)不変な関数の合成で書ける•

一般の部分群Gに対しても互換を別の表現に置き換えた表記がある

⊤F = ( f ∘ (1 1), f ∘ (1 2), . . . , f ∘ (1 M)) の深層ニューラルネット表現••

第1層で互換に対応する部分を表現
コピーの一つ一つはfを近似している

Sannai-Takai-Matthieuより

部分群とテンソル表現

部分群とその作用•群Gの部分集合HがGの演算で群となる時、HをGの部分群という•Smの部分群Gを考える•

GはSmの部分集合であるからSmの自然な作用がGの作用を誘導する。これを部分作用と呼ぶ。

•部分群を考えることでどのような状況を含むことができるか？

グラフのノード置換と隣接行列グラフ（の同型類）と隣接行列の関係を考える
グラフとノードのラベリングを固定すると隣接行列が定まるが、ラベリングを置換すると隣接行列もそれに応じて変化する
12340100101101000100

グラフのノード置換と隣接行列
M2

この関係はノードの置換群SMのℝ≅ GL(M, ℝ)への非自明な作用を与える。

この作用はSM 2の自然な作用の部分作用となっている部分群による非自明な作用で役に立つ例となっている
12340100101101000100ノード置換の二階テンソル表現
この作用は行列の(i, j)成分と(σ(i), σ( j))成分を置換する作用となっている
つまり行列を二階テンソルとみなした時、自然な作用を二階テンソルしたものと同値になっている
12340100101101000100

テンソルの定義ℝm × ℝm上の同値関係〜を以下で定義する：(λx, y) ∼ (x, λy)ただしλは0でない実数
M22

この同値関係の商集合はM 次元のベクトル 空間ℝ となり、(ei, ej)が基底となる。この基底を簡単のためeijと書く
同様にℝM × ⋯ × ℝMに対し、(λx1, x2, ⋯xl) ∼ (x1, ⋯, λxi, . . , xl)といmlう同値関係を考えることでl階のテンソルℝ が定義され、その基底をei1,..,ilと書く

テンソル自然表現
MlGをSMの部分群とする。x = (xi1,..il) ∈ ℝ とg ∈ Gに対し、g ⋅ x = (xg−1(i1),..,g−1(il))と定義する。この作用はM自然な作用SM ↷ ℝ のl階のテンソルと同値になっている。

On the universality of invariant networksより

テンソルネットワーク
定義: 同変テンソル層とはアファイン写像
L:ℝ

m k×a→ℝm k×ax∈ℝm l×bであって全てのg ∈ Gと全てのに対し、L(g ⋅ x) = g ⋅ L(x)を満たすもの。
m k×a

不変テンソル層とはアファイン写像h : ℝであって、全てのg ∈ Gと全てのx ∈ ℝh(g ⋅ x) = h(x)を満たすもの。

m k×a→ ℝbに対し

Maronʼs model
L1L2…

Ldh定義 G不変テンソルネットワークとは関数m k×a

F:ℝ→ ℝであってF = m ∘ h ∘ Ld ∘ σ⋯σ ∘ L1の形のもの。ここでLiは同変テンソル層でσは活性化関数、hは不変テンソル層で、mはMulti layer perceptronとする。

mUniversality of invariant tensornetworks
定理1(On the universality of invariant networks):m

K ⊂ ℝ をコンパクト集合としG ⊂ Smを部分群とする。連続なG不変関数f : K → ℝはG不変テンソルネットワークで任意精度で近似可能
この結果と同変関数の不変関数による表現を組み合わせることで同変関数のUniversal approximation theoremが得られる。

不変学習の汎化誤差基本領域を使った汎化誤差の評価定理(Sannai-Imaizumi) f : ℝM → ℝを深層ニューラルネットであって関数としてSM自然な作用に対して不変なものであるとする。この時、十分小さい正のεに対し、確率1 − O(ε)で次の不等式が成立する。
R( f ) ≤ Rn( f ) +ここでRn( f ) = n −1n∑i=1C+ O(log(1/ε))
pm! nεL(Yi, f(Xi)), R( f ) = 𝔼[L(Y, f(X ))], Cはnとmに依らない定数とする。

ポイントクラウドの時はm = 1000くらいのオーダーなので大きく改善している
仲間外れ探しの時でも16! = 20922789888000の改善

証明のアイデア
M(1){ℝ からの不変連続関数}≅{Δからの連続関数}となるようなΔ ⊂ ℝMを構成。
(2)Δ( ∩ [0,1]M)のcovering数を計算してcovering数と汎化誤差の一般論から不等式を得る。

40

Δの意味と構成•

一般の群Gに対し、一つ目の要請を満たすΔは存在する（商空間ℝM /Gを取れば良い）。

Mの時はと取ればの中に実現するこℝΔ={(x,.
.
,x)∣x≥x≥,.
.
,
≥x}
S
• M
1M
12Mとができる。
•Sort : ℝM → Δ (大きい順にソートする写像）が構成できf ↦ f ∘ Sortが右から左への対応を与えている（左から右は制限）•

ちなみにこの対応を深層ニューラルネットレベルで見ることで置換不変の場合のUniversal approximationも出る41

まとめと今後の課題•（有限）群対称性という事前知識からそれにﬁtする深層モデルを設計し、ある程度の理論保証（UATと汎化誤差不等式）をつけた。

•

ハイパラの調整については全く手をつけていない。

•

ニューラルネットの積分表現論+対称性•

SO2, SO3などの回転群の時にも良いモデルを設計することはできるか？

•

有限群の場合でもテンソルネットは少し大きすぎるように思える。群を限定しても良いのでより小さいものを取れないか？

•対称性+ノイズのような状況を取り扱う方法はあるか？

•

データから背後に潜む対称性を発見する方法はあるか？

[Reference]•Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas
Poczos, Ruslan Salakhutdinov, Alexander Smola. Deep Sets , NIPS,
2017. arXiv:1703.06114.

•

Haggai Maron, Heli Ben-Hamu, Nadav Shamir, Yaron
Lipman. Invariant and Equivariant Graph Networks . ICLR
2019. arXiv:1812.09902•

Haggai Maron, Ethan Fetaya, Nimrod Segol, Yaron Lipman, On theUniversality of Invariant Networks, ICML2019, arXiv: 1901.09342•Akiyoshi Sannai, Yuuki Takai, Matthieu Cordonnier. Universal
approximations of permutation invariant/equivariant functions by
deep neural networks , arXiv:1903.01939.

•Improved Generalization Bound of Permutation Invariant Deep NeuralNetworks, Akiyoshi Sannai, Masaaki Imaizumi,arXiv:1910.06552