[DL輪読会]Clebsch?Gordan Nets: a Fully Fourier Space Spherical Convolutional Neural Network

DEEP LEARNING JPClebsch-Gordan Nets: a Fully Fourier Space Spherical [DL Papers] Convolutional Neural Network Rei Mizuta, Graduate School of Mathematical Sciences, UT http://deeplearning.jp/ 1

• http://deeplearning.jp/

書誌情報
• 著者:Risi Kondor, Zhen Lin, Shubhendu Trivedi
• NIPS 2018 (12/2~12/8 @Canada)
• （cf. On the generalization of equivalence and convolution in neural
networks to the action of compact groups.; ICLR 2018）
• Spherical CNNs（Taco S. Cohen et al.; ICLR 2018）のアーキテクチャを変え
てSO(3)-equivariant（つまり入力を回転してもNNの出力は同じ）にしたもの
• 定義：SO(3):={𝑔 ∈ 𝑀3 (ℝ)|𝑔𝑔 𝑡 = 𝑔 𝑡 𝑔 = 𝐼, det 𝑔 = 1}
• SO(3)は3次元、非可換、コンパクト
球面を中心を固定して
動かす操作の全体！
2

何をするのか • 球面上のデータの分類問題を学習したい • 例えば、CNNのようにcross-correlation（≒convolution）を使った処理をした い（Spherical CNNs） – 今回のスライドではSpherical CNNsのみこの操作を行うが、cross-correlationは convolutionと同一視して構わないので以降convolution（or 畳み込み）と呼ぶ • 普通にCNNのような処理をしようとすると移動するごとにフィルタの形が変わっ てしまいグリッドの数に応じてメモリが必要 3

目的 • 3D Shape Recognition • meshで与えられる3Dデータに対して周囲から中心点に向けてのray castingで得 られる情報のみを使って物体についての情報を推測する • 一般に物体が凸でないとray castingで情報が落ちてしまうが、今回のタスクには 十分 • 一般に物体が回転しているかも しれない状況でも、NN自体に SO(3)-equivariantの性質があ るとpredictionの出力は回転に 依らない 4

要点 (1)Spherical CNNsは球面上のデータに対してCNNのような処理をすることを目的 にしている。そのためにフーリエ変換の（可換でない群への）拡張を使う。 (2)Clebsch-Gordan netでは活性化層にReluやSigmoidなどを使わず、Fusion Ruleから来る関数を使っている。結果NNがSO(3)-equivaliantになる。 (3)3D Shape Recognitionの実験結果はSpherical CNNsや（このタスクに特化し た）他の既存手法と比べて遜色ない 5

目次 1. 既存手法 1. 2. 3. 4. Review of CNN The Convolution over SO(3) Representations of SO(3) Spherical CNNs 3. 各手法の評価 1. データセットと評価指標 2. アーキテクチャ 3. 結果 4. まとめと感想 2. 提案手法 1. The Fusion Rule of SO(3) 2. Clebsch-Gordan net 6

1.1 Review of CNN 1. 画像データをR^2の上の関数だと思うと、畳み込みは入力画像が並行移動し た場合に計算結果が平行移動する。 2. （1次元データで）畳み込みがO(N^2)かかるのに対しFourier Transformし て掛けてからInverse FTするとFast FTを挟むことでO(Nlog N)で計算できる。 3. しかしCNNはFTを使わない。<- フィルタは局所的な関数であるため、普通に 畳み込みをしてもO(N)だから。 4. しかしSpherical CNNでは普通の畳み込みができないので、Fourier Transformの類似を使う！ 7

1.2 The Convolution over SO(3) 1. ℝ上でフーリエ変換の理論から𝑓෣ ∗ 𝑔 = 𝑓መ𝑔だが、これのSO(3)版はどうなるの ො か？ 2. 定義（Cohen et al. ’18）：球面上のℂ𝐾 -valued関数𝜓, 𝑓に関して畳み込み𝜓 ⋆ 𝑓: 𝑆𝑂(3) → ℂを次で定義する 3. 定理（同上）： ただし両辺はl番目のフーリエ変換で(2l+1) 次行列（後述）、つまりℝ上でフーリエ変換した時と同様の式が成り立つ。 4. 上を認めるとSO(3)上の畳み込みはフーリエ変換の積になることがわかったが、 ではここでいうフーリエ変換とは何か？→表現論 8

1.3 Representations of SO(3) 1. 定義：SO(3)の有限次元（ユニタリ）表現とは、連続群準同型𝜋: 𝑆𝑂(3) → 𝑈𝑛 (ℂ)である。ただし𝑈𝑛 (ℂ)はn次ユニタリ行列全体。ここでnを𝜋の次元と呼ぶ。 2. 定義：二つの表現𝜋, 𝜌が同値とはあるユニタリ行列Uがあって ∀𝑔 ∈ 𝑆𝑂 3 , 𝜋 𝑔 𝑈 = 𝑈𝜌(𝑔)となることを言う。また表現𝜋が既約とは 𝜋と𝜌1 ⨁𝜌2 が同値になるような表現𝜌1 , 𝜌2 が存在しないことを言う。 3. 定理：任意のSO(3)の有限次元表現𝜋は既約表現の直和に分解する。 4. 定理：SO(3)の既約表現は全て𝜋𝑛 : 𝑆𝑂(3) → 𝑈2𝑛+1 (ℂ)という形をしている (n>=0) 5. 定理（Peter-Weyl）：任意のSO(3)上の連続関数は既約表現の成分の和で近 似できる。 6. 定義：標準的な(2l+1)次既約表現(𝐷∙𝑙 )を作り、 (m,n)成分とSO(3)上の関数f 𝑙 とのSO(3)上の内積をfのフーリエ変換と呼び、𝑓መ𝑚𝑛 と書く。ただし内積は SO(3)上のHaar measureでの積分で定義する。 := 9

1.3 Representations of SO(3)（補足） 1. 定義（ZYZ-coding）：SO(3)上のchart R: (0,2𝜋) × (0, 𝜋) × (0,2𝜋) → 𝑆𝑂(3)を R(α, 𝛽, 𝛾) ≔ 𝑍 𝛼 𝑌 𝛽 𝑍(𝛾)で定める。ただし𝑌 𝑎 , 𝑍(𝑏)はそれぞれY軸,Z軸周り のa,b回転を表す。この写像でSO(3)（のほとんど）と(0,2𝜋) × (0, 𝜋) × (0,2𝜋) を同一視する。 2. 同様に(0,2𝜋) × (0, 𝜋)と𝑆 2を(α, β) ↦ 𝑍 𝛼 𝑌 𝛽 𝑛で同一視できる。ここで𝑛は𝑆 2 の北極点（Z座標が一番大きい点） 3. 定義（Haar measure）：上のchart上の密度 をHaar measureと呼ぶ。関数を回転させてもこの密度上の積分は不変 4. 球面上の関数𝑓を𝐹𝑓 α, 𝛽, 𝛾 ≔ 𝑓(α, 𝛽)によってSO(3)上の関数とみなすと、 色々うまくいく。例えば次が成り立つ。 1. ‫ 𝑂𝑆׬‬3 𝐹𝑓 𝑅 𝑑𝑅= ‫ 𝑆׬‬2 𝑓 𝑥 𝑑𝑥 2. 𝐹𝑓 ∗ 𝐹𝑔 𝑅 : = ‫𝑂𝑆׬‬ 3 𝐹𝑓 𝑅−1𝑆 𝐹𝑔 𝑆 𝑑𝑆 = 𝑓 ⋆ 𝑔(𝑅) 10

1.4 Spherical CNNs 1. NaiveにやるとSO(3)上の関数のFT(=既約表現との内積を求める)は O(L_max^6)かかる。ただしL_maxはBandwidth(=内積を取る既約表現の番 号の最大値) 2. 以上より、Spherical CNNの畳み込み層は 1. 2. 3. 4. 球面上の関数をSO(3)上の関数にする 1にGFTをかける 2をフィルタのGFTと掛け合わせる Inverse DFTをする SO(3)上の関数のフーリエ変換は番号lで (2l+1)(2l+1)サイズだが、球面上の関 数だと(2l+1)サイズ！(cf. Appendix D in (Cohen et al.)) 11

目次 1. 既存手法 1. 2. 3. 4. Review of CNN The Convolution over SO(3) Representations of SO(3) Spherical CNNs 3. 各手法の評価 1. データセットと評価指標 2. アーキテクチャ 3. 結果 4. まとめと感想 2. 提案手法 1. The Fusion Rule of SO(3) 2. Clebsch-Gordan net 12

2.1. Fusion Rule • 以下、𝜋𝑛 : 𝑆𝑂(3) → 𝑈2𝑛+1 (ℂ)(𝑛 = 0,1,2, … )は既約表現とする。 • 定義（covariant vector）：関数𝑉: (𝑆𝑂(3) → ℂ) → ℂ2𝑙+1 で𝑔𝑉 ≔ 𝑉(𝑔 ∙) = 𝜋𝑙 (𝑔)𝑉 となるものを𝜋𝑙 -covariant vectorと呼ぶ。ただし関数𝑓: 𝑆𝑂(3) → ℂに対し𝑔𝑓 ≔ 𝑓(𝑔 −1 ∙) • 例：関数𝑓: 𝑆𝑂(3) → ℂのl番目のフーリエ変換の列ベクトル𝑓መ∙𝑘𝑙 は𝜋𝑙 -covariant vector • ここで、テンソル積表現𝜋 ⊗ 𝜌: 𝑆𝑂(3) → 𝑈dim 𝜋×dim 𝜌 (ℂ)を𝜋 ⊗ 𝜌 𝑔 𝑣 ⊗ 𝑤 : = (𝜋 𝑔 𝑣) ⊗ (𝜌 𝑔 𝑤)で定義する。 • 定理（Clebsch-Gordan Rule） ：SO(3)の既約表現 𝜋𝑚 , 𝜋𝑛 に対して次が成り立つ。 𝜋𝑚 ⊗ 𝜋𝑛 ≅⊕𝑚+𝑛 𝑙= 𝑚−𝑛 𝜋𝑙 • 定理（Kondor ‘18）：2つのSO(3)-covariant vector V,Wに対し、あるユニタリ Uが存在して𝑈 𝑉 ⊗ 𝑊 は𝜋 𝑚−𝑛 , 𝜋 𝑚−𝑛 +1, … , 𝜋𝑚+𝑛 -covariant vectorsの直和にな る。 13

2.1. Fusion Rule（捕足） • 関数𝑓: 𝑆𝑂(3) → ℂのl番目のフーリエ変換の列ベクトル𝑓መ∙𝑘 は𝐷𝑙 -covariant vector −1 𝑙 ෢∙𝑘 = ‫׬‬ • 𝑔𝑓መ∙𝑘 = 𝑔𝑓 𝑓 𝑔 ℎ 𝐷 ∙𝑘 (ℎ)𝑑ℎ 𝑆𝑂(3) =න 𝑆𝑂(3) 𝑙 𝑓 ℎ 𝐷∙𝑘 (𝑔ℎ)𝑑ℎ = 𝐷𝑙 (𝑔) න 𝑆𝑂(3) 𝑙 𝑓 ℎ 𝐷∙𝑘 (ℎ)𝑑ℎ = 𝐷𝑙 (𝑔)𝑓መ∙𝑘 • 定理（Kondor ‘18）：2つの𝜋𝑚 , 𝜋𝑛 -covariant vector V,Wに対し、あるユニタリ Uが存在して𝑈 𝑉 ⊗ 𝑊 は𝜋 𝑚−𝑛 , 𝜋 𝑚−𝑛 +1, … , 𝜋𝑚+𝑛 -covariant vectorsの直和にな る。 • CG Ruleよりあるユニタリが存在して𝑈 𝜋𝑚 ⊗ 𝜋𝑛 = ⊕𝑚+𝑛 𝑙= 𝑚−𝑛 𝜋𝑙 𝑈 • 𝑔 𝑈 𝑉 ⊗ 𝑊 = 𝑈𝜋𝑚 ⊗ 𝜋𝑛 𝑔 𝑉 ⊗ 𝑊 = (⊕𝑚+𝑛 𝑙= 𝑚−𝑛 𝜋𝑙 (𝑔))(𝑈 𝑉 ⊗ 𝑊 ) 14

2.2. Clebsch-Gordan net • l=0,l=1,…,l=L_maxまで球面上の関数のフーリエ変換を求める（それぞれ𝐹𝑙と 書く）以降のClebsch-Gordan netの計算は以下の手順になる – 各𝐹𝑙1と𝐹𝑙2のテンソル積を計算し、CG Ruleにより分解した𝐹𝑙 成分を𝐹𝑙 の段に追加する。 非線形！（Relu等の活性化層の代わり） – 各𝐹𝑙 を𝑊𝑙 とかける（学習時はこの𝑊𝑙 を学習する） – 以上繰り返す。結果として入力がg∈SO(3)で回転した場合、l段目は𝜋𝑙 (g)が左から掛けられる • 自明表現 (= 𝜋0 )の係数は SO(3)不変なので、その係数を 出力層にすることによりNNが SO(3)-equivariantになる 15

目次 1. 既存手法 1. 2. 3. 4. Review of CNN The Convolution over SO(3) Representations of SO(3) Spherical CNNs 3. 各手法の評価 1. データセットと評価指標 2. アーキテクチャ 3. 結果 4. まとめと感想 2. 提案手法 1. The Fusion Rule of SO(3) 2. Clebsch-Gordan net 16

3.1. データセットと評価指標（SHREC17） • 51300個くらいのShapeNetのサブセット。55 categoriesの分類 • [Savva et al.]で70/10/20比でtrain/valid/testのデータセットをそのまま/ラン ダムに回転させたもので生成。 • 今回はランダムに回転させたもののみ使う • 大元の中身は点の3D座標と面のデータの集まり • 今回はそのデータを球面上の6Dデータにする – 視点からぶつかる平面への距離(1D) – ぶつかる平面の傾き(2D) – Meshの凸包へのray castingのデータ(3D)<-衝突点の座標? • バンド幅128のDiscroll-Healy grid でデータを離散化 • 評価指標はPR,F1のMacro average等 17

3.2. アーキテクチャ • • • • L_max=14 出力はF_0の最終層を55 nodesに全結合 最終層にのみBatch Normalization ADAM,learning rate = 0.0005,L2 reg weight decay of 0.0005 18

3.3. 結果 • 他手法でnon-Rotatedなデータではよりよいスコアを出す手法があるが、 RotatedなデータでのSOTAは以下 • cf. https://shapenet.cs.stanford.edu/shrec17/ 既存手法と比 べて遜色はな い 19

目次 1. 既存手法 1. 2. 3. 4. Review of CNN The Convolution over SO(3) Representations of SO(3) Spherical CNNs 3. 各手法の評価 1. データセットと評価指標 2. アーキテクチャ 3. 結果 4. まとめと感想 2. 提案手法 1. The Fusion Rule of SO(3) 2. Clebsch-Gordan net 20

まとめと感想 (1)Spherical CNNは球面上のデータでCNNのような枠組みを使うため作られた (2)Clebsch-Gordan netsは活性化層をFusion Ruleを使って実装しており、その結 果NN自体がSO(3)-equivariantなものになった [感想] - NN自体はSO(3)-equivariantだが、学習はSO(3)回転したデータで結果が異なる ため、学習データをランダムに回転して学習した時にパフォーマンスが変わらな いのかが気になる。 21

参考文献 • Savva, M., Yu, F., Su, H., Kanezaki, A., Furuya, T., Ohbuchi, R., Zhou, Z., Yu, R., Bai, S., Bai, X., Aono, M., Tatsuma, A., Thermos, S., Axenopoulos, A., Papadopoulos, G. T., Daras, P., Deng, X., Lian, Z., Li, B., Johan, H., Lu, Y., and Mk., S. (2017). Large-scale 3d shape retrieval from shapenet core55. Eurographics Workshop on 3D Object Retrieval. • A. X. Chang, T. Funkhouser, L. Guibas, P. Hanrahan, Q. Huang, Z. Li, S. Savarese, M. Savva, S. Song, H. Su, J. Xiao, L. Yi, and F. Yu. Shapenet: An information-rich 3d model repository. 2015. • T.S.Cohen,M.Geiger,J.Köhler,andM.Welling.SphericalCNNs.Interna tionalConferenceonLearning Representations, 2018. • Risi Kondor, Zhen Lin, and Shubhendu Trivedi. Clebsch–gordan nets: a fully fourier space spherical convolutional neural network. In Neural Information Processing Systems (NIPS), 2018. 22