[DL輪読会]Neural Ordinary Differential Equations

DEEP LEARNING JP [DL Papers] Neural Ordinary Differential Equations Joji Toyama, DeepX, Matsuo-lab http://deeplearning.jp/ 1

• http://deeplearning.jp/

本資料で紹介する論文 • Neural Ordinary Differential Equations – NeurIPS2018 Best paper – Ricky T.Q. Chen*, Yulia Rubanova*, Jesse Bettencourt*, David Duvenand – Vector Institute, Toronto Univ • FFJORD: Free-form Continuous Dynamics for Scalable Reversible Generative Models – ICLR2019 Oral – Will Grathwohl*, Rickey T.Q. Chen*, Jesse Bettencourt, Ilya Sutskever, David Duvenand – Vector Institute, Toronto Univ • １本目が、ニューラルネットワークを微分方程式として見る、という新しい概 念を提案。２本目は、それをflow-basedな生成モデルに応用した論文。 • めっちゃ面白い（と思ってくれると発表者冥利に尽きる） 2

事前知識：常微分方程式（ODE: Ordinary Differential Equations） • 未知関数の導関数を含む関数方程式を微分方程式と呼ぶ。 • その中で、独立変数が１つだけのものを常微分方程式と呼ぶ。 • 例１： 𝑑𝑥(𝑡) 𝑑𝑡 = −𝑐𝑥(𝑡) – 独立変数はtのみ – この解は、初期値𝑋0 として、 𝑥(𝑡) = 𝑥0 exp(−𝑐𝑡)と一意に定まる。 – 放射性物質の崩壊式 • 𝑑 2 𝑥(𝑡) 例２： 𝑑𝑡 2 = −𝑐 2 𝑥(𝑡) – 独立変数はtのみ – 任意定数AとBを用いて、 𝑥 𝑡 = A ∗ sin ct + B ∗ cos(ct)と一意に定まる。 – 単振動の式 3

事前知識：ODE Solver • 常微分方程式の解析解（＝数式で表された解）を求めるのは一般に困難。 • そこで、ある時刻tにおける値を、計算機を使って数値解として求める！ – ＝ ODE Solver • 代表的なODE Solver – オイラー法 – ルンゲクッタ法 – etc… 4

事前知識：オイラー法 • 最も簡単なODE Solver • 𝑑𝑦 𝑑𝑡 = 𝑓 𝑡, 𝑦 , 𝑦 𝑡0 = 𝑦0であるとき、 𝑓 𝑡, 𝑦 はyの微分なので、ステップ幅h後 のyの値は、 𝑦 𝑡0 + ℎ = 𝑦0 + 𝑓 𝑡0 , 𝑦0 ∗ ℎと近似できる • これを繰り返すことで、任意のステップ後の𝑦(𝑡)を求めることができる。 – 下の図では𝑡ではなく𝑥が変数になっていることに注意 https://guide.freecodecamp.org/mathematics/differential-equations/eulers-method/ 5

• https://guide.freecodecamp.org/mathematics/differential-equations/eulers-method/

ResNetとオイラー法 DeepNet ResNet h1 = f1(x) h2 = f2(h1) h3 = f3(h2) h4 = f4(h3) y = f5(h4) h1 = f1(x)+x h2 = f2(h1)+h1 h3 = f3(h2)+h2 h4 = f4(h3)+h3 y = f5(h4)+h4 • ResNetは差分を学習させることによって、従来のDeepNetより精度向上 6

ResNetとオイラー法 DeepNet ResNet h1 = f1(x) h2 = f2(h1) h3 = f3(h2) h4 = f4(h3) y = f5(h4) h1 = f1(x)+x h2 = f2(h1)+h1 h3 = f3(h2)+h2 h4 = f4(h3)+h3 y = f5(h4)+h4 • ResNetは差分を学習させることによって、従来のDeepNetより精度向上 7

ResNetとオイラー法 DeepNet ResNet h1 = f1(x) h2 = f2(h1) h3 = f3(h2) h4 = f4(h3) y = f5(h4) h1 = f1(x)+x h2 = f2(h1)+h1 h3 = f3(h2)+h2 h4 = f4(h3)+h3 y = f5(h4)+h4 • ResNetは差分を学習させることによって、従来のDeepNetより精度向上 • なんかよく見るとオイラー法っぽい – “These iterative updates can be seen as an Euler discretization of a continuous transformation (Lu et al., 2017; Haber and Ruthotto, 2017; Ruthotto and Haber, 2018)” – 筆者はここから着想を得たとのこと。 8

ODENet • ResNetの更新則は ℎ𝑡+1 = ℎ𝑡 + 𝑓(ℎ𝑡 , 𝜃𝑡 ) • 一回の更新幅（＝層の深さに該当）が微小であるときを考える。すると、 𝑑ℎ 𝑡 = 𝑓(ℎ 𝑡 , 𝑡, 𝜃) 𝑑𝑡 という常微分方程式（Neural ODE）を用いてResNetの更新則を表現できる – ある時刻（深さ）での隠れ層のダイナミクスを出力する𝑓(ℎ 𝑡 , 𝑡, 𝜃)を、ニューラル ネットワークでモデル化し、これをODENetと呼ぶ – 今まで離散的だった”層”が、連続になる（！） • ResNetでは各層で異なるパラメータを持つ関数 𝑓(ℎ𝑡 , 𝜃𝑡 )が用いられるが、ODENetは単一の関 数𝑓(ℎ 𝑡 , 𝑡, 𝜃)のみが存在する • ℎ(𝑡)はODE Solverによって計算される。 9

ResNet vs ODENet • ResNetは変換が層においてのみ行われる。一方で、ODENetは層を連続値と して扱って入力に用いるので、連続的な変換が行われる。 • 丸い点は値の評価がされていることを示す。ResNetは各層ごとに値が出力さ れるが、ODENetはいかなる点でも値を評価することができる。 – 実際には、評価の回数と場所はあらかじめ適当に決めたり、ODE Solverによって自 動的に決まる 10

ODENetの嬉しいこと • Memory efficiency – 計算グラフを保持する必要なしに勾配を求めることができるようになる • Adaptive computation – ResNetは最も簡単なODE Solverである、オイラー法を用いていると見ることができ る。ODENetではもう少し賢いODE solverを使う（e.g. Runge-kutta 4）ことにより、 数値解の許容誤差と推論速度のトレードオフを取ったり、ステップ幅の適応制御を可 能にする。 • Parameter efficiency – 各層に異なるパラメータを持たないので、パラメータ効率が良い • Scalable and invertible normalizing flows – Normalizing flowの計算上のボトルネックである行列式計算が、トレース計算で済む 様になる。 • Continuous time-series models – RNNにおけるタイムステップが連続になるため、より自然に時間をモデリングできる。 11

ODENetの順伝播と逆伝播 • Given – ODENetのパラメータ𝜃,開始時刻𝑡0 ,終了時刻𝑡1 , ODE Solver • 順伝播 𝑡 𝑧(𝑡1 ) = ‫ 𝑡׬‬1 𝑓 𝑧 𝑡 , 𝑡, 𝜃 𝑑𝑡 = 𝑂𝐷𝐸𝑆𝑜𝑙𝑣𝑒𝑟(𝑧 𝑡0, 𝑓, 𝑡0 , 𝑡1, 𝜃 ) 0 – ODE Solverによってちまちま𝑧(𝑡1 )まで計算していくだけ。 • 逆伝播 – 素直にやろうとすると、ODESolverの各ステップで毎回微分をする必要があり、 forward時の計算グラフの保持に大量のメモリを必要とする。 – そこで、adjoint method(Pontryagin et al., 1962)という賢い方法を用いて、ODEをブ ラックボックスとして扱いながら、計算グラフの保持なしに、各変数についての勾配 を求める。 12

Adjoint methodを用いた逆伝播 𝑡 • 𝐿(𝑧(𝑡1 )) = 𝐿 ‫ 𝑡׬‬1 𝑓 𝑧 𝑡 ,𝑡, 𝜃 𝑑𝑡 = 𝐿 𝑂𝐷𝐸𝑆𝑜𝑙𝑣𝑒𝑟 𝑧 𝑡0 ), 𝑓, 𝑡0 , 𝑡1 , 𝜃 0 – Lを最適化するため、 𝑧 𝑡0 , 𝑡0 ,𝑡1, 𝜃に関する勾配を求めたい • ある状態𝑧 𝑡 の、損失に関する勾配をadjointと呼び、 𝑎 𝑡 = −𝜕𝐿/𝜕𝑧(𝑡) • このadjointは、以下の微分方程式に従う。 𝑑𝑎 𝑡 = −𝑎 𝑡 𝑑𝑡 𝑇 𝜕𝑓 𝑧 𝑡 , 𝑡, 𝜃 𝜕𝑧 – 未知の関数が𝑎 𝑡 で、独立変数がtのみであるため、これも常微分方程式であり、初期値を 𝑎 𝑡1 = −𝜕𝐿/𝜕𝑧(𝑡1 )とすることで、 𝑎 𝑡0 = −𝜕𝐿/𝜕𝑧(𝑡0) をODE Solverによって解くことが できる。 • 同様のことを、𝑎𝜃 𝑡 = −𝜕𝐿/𝜕𝜃 𝑡 、 𝑎𝑡 𝑡 = −𝜕𝐿/𝜕𝑡 𝑡 とおくことで、 𝑡0 , 𝑡1 , 𝜃につ いての勾配もODE Solverによって求めることができる。 – ※細かい導出は本論文のappendixをみてください（そんなに難しくないです） 13

勾配計算アルゴリズム 14

実験１：ODENetによる教師あり学習 ーMNIST 定量評価ー • 1-Layer MLP, ResNet, RK-Net(ODE-Netの時のソルバとしてルンゲクッタを 用い、普通に誤差逆伝播させるモデル）と,ODE-Net（adjoint methodで勾配 計算）をMNISTで比較 – Lはレイヤー数、𝐿෨ はODE Solverが要したステップ回数（＝関数評価回数） • 𝐿෨ はODENetにおける層の数と解釈もできる • ResNetと同じ精度ながら、パラメータ数が少なくメモリ使用量も少ない 15

実験１：ODENetによる教師あり学習 ーMNIST 定性分析ー • 関数評価回数を増やすと数値誤差は減少する（当たり前） • 関数評価回数を増やすと時間がかかる（当たり前） – 数値誤差とフォワード時の推論時間のトレードオフを取れる。例えば、テスト時だけ許容 数値誤差を大きくすることで、関数評価回数が減り、短時間での推論が可能になる。 • バックワード時のODE Solverの関数評価回数は、フォワード時の関数評価回数の 約半分 – 素直にやったらバックワード時の関数評価回数はフォワード時と同じ。つまり、Adjoint methodはメモリ効率がいいだけでなく、計算効率も良い！ • 訓練が進むにつれ、関数評価回数は増えていく – 訓練が進むにつれ、ダイナミクスの複雑さが増していくことを示唆。 16

Normalizing FlowをNODEとして見る • Normalizing Flowの変数変換 𝑧1 = 𝑓 𝑧0 => log 𝑝(𝑧1) = log 𝑝 𝑧0 𝜕𝑓 − log | det | 𝜕𝑧0 – ただし𝑓は全単射な関数 – ヤコビアンの行列式を求めるのにO(𝐷 3 )かかるため、 𝑓に様々な工夫を必要としてい た。 • Normalizing Flowの更新も、NODEとして見ることができる。 𝑑𝑧 = 𝑓(𝑧 𝑡 , 𝑡) 𝑑𝑡 • すると、なんと 𝜕 log 𝑝(𝑧 𝑡 ) 𝑑𝑓 = −𝑡𝑟 ( ) 𝜕𝑡 𝑑𝑧 𝑡 • となる（証明が気になる人は論文のAppendixを読んでください） – また、ODEは解の一意性が担保されているため、 𝑓 に何を選ぼうとも、変換は全単射。 17

Continuous normalizing flow • planar normalizing flowを改良したContinuous normalizing flow(CNF)を提案 – Planar normalizing flow 𝑧 𝑡 + 1 = 𝑧 𝑡 + 𝑢ℎ 𝑤 𝑇 𝑧 𝑡 + 𝑏 𝑢, 𝑤 ∈ 𝑅𝐷 , 𝑏 ∈ 𝑅, ℎ 𝑖𝑠 𝑛𝑜𝑛𝑙𝑖𝑛𝑖𝑎𝑟𝑖𝑡𝑦 𝑎𝑐𝑡𝑖𝑣𝑎𝑡𝑖𝑜𝑛 – Continuous normalizing flow 𝑑𝑧 𝑡 =𝑓 𝑧 𝑡 𝑑𝑡 = 𝑢ℎ 𝑤 𝑇𝑧 𝑡 +𝑏 , 𝜕 log 𝑝 𝑧 𝑡 𝜕𝑡 = −𝑢 𝑇 𝜕ℎ 𝜕𝑧 𝑡 • トレースは線形性を持つため、 𝑓を関数の和として表現した場合、log densityもト レースの和として計算できる。 – つまり、CNFは隠れユニットを増やしても計算量がO(M)のオーダでしか増えないため、 wideなPlanar NFが構築可能！ 𝑀 𝑑𝑧 𝑡 = ෍ 𝑓𝑛 (𝑧 𝑡 ) , 𝑑𝑡 𝑛=1 𝑑 log 𝑝 𝑧 𝑡 𝑑𝑡 𝑀 = ෍ 𝑡𝑟( 𝑛=1 𝜕𝑓𝑛 ) 𝜕𝑧 18

実験２：Density matching • • • • Target分布になるように訓練 LossはKL KはNFの深さ、Mは隠れ層のユニット数（CNFは常にK=1） CNFのほうがNFよりもLossが下がっていて、定性的にもよくモデリングでき てる 19

実験２：Maximum Likelihood Training • Two CirclesとTwo Moons • %はflowの時間（深さ）を表す • CNFはターゲットにうまくフィットできると共に、そこから遡って元のガウス 分布にきちんと対応する。 20

NODEのRNNへの応用 • RNNでは時間は離散化されている。そのため、時間に対して不均一に得られ るデータの扱いが難しい。 – 医療診断のログ – ネットワークトラフィック • 従来では、時間に不均一なデータに対し、以下の対策を講じていた – 欠損値補完 – タイムスタンプ情報を入力にする • NODEは時間を連続的に扱えるため、上の問題を根本的に解決できる。 21

ODENetをデコーダもちいたRNN型VAE • 本論文では、時系列の潜在変数を出力するデコーダをODENetでモデリングし たRNN型VAEを考える。 22

実験３：ODERNN • データ：渦巻き状（時計回りと反時計 回り）の時系列データで、観測点が不 均一 • ODERNNはうまく予測できている。 また、観測点が終わった後の外挿もう まくできている。 • 潜在空間は、時計回りと反時計回りの 回転をうまく獲得できている。 • 定量的にも良い。 23

結論 • 微分方程式にNNを組み込み、ODE Solverによって順伝播と勾配計算を行う、 全く新しい学習スキームを提案 • ５つのメリット – – – – – メモリ効率が良い 計算時間と正確さを自由に調整できる パラメータ効率が良い 計算コストが少ないNF 時間を連続的に扱えるRNN • NeurIPS Best paper取るわけですわ、という面白さと革新さ 24

FFJORD: Free-form Continuous Dynamics for Scalable Reversible Generative Models • 先の論文で、変数変換を常微分方程式の 形で表すことで、NFのレイヤーの幅を増 やすことが可能になったことを見たが、 あくまでplanar normalizing flowの形に 限定されていた。 • 本論文では、Reversible generative modelsのアーキテクチャの制約を完全に 外すことを目指す。 – FFJORD(Free-form Jacobian of Reversible Dynamics)と名付ける（もう少しいい名前 を考えられなかったものか） • ODEなので、右みたいに連続的なダイナ ミクスが学習されます。 25

Flow-based Generative Models • Flow-based generative models – 変数変換によって、単純な分布（e.g. ガウス分布）からデータへの変換を直接学習する生 成モデル • 変数変換時にヤコビアンの行列式を求める際の工夫の仕方で、Flow-based generative modelsは以下の３クラスに分類できる（筆者談） – Normalizing Flow • 普通に変数変換するモデルのことを言っている。関数𝑓の形を限定することで行列式を計算しやすく する。ただ 𝑓 −1 は求められないため、reversibleではなく、データ点𝑋のみから学習はできない。 – Planar NF, Radial NF – Autoregressive Transformations • 変数変換を自己回帰的に行うことで、ヤコビアンが三角行列になり行列式を計算しやすくする。 – MAF, IAF – Partitioned Transformations • データの特定の次元を不変にし、他の残った次元を、不変にしたデータを入力として出力されるパラ メータによって変換をするように変数変換をすることで、ヤコビアンが三角行列になる。 – NICE, RealNVP, Glow • ここらへんよくわからない人はこちらを読むことをお勧め – https://lilianweng.github.io/lil-log/2018/10/13/flow-based-deep-generativemodels.html#realnvp 26

• https://lilianweng.github.io/lil-log/2018/10/13/flow-based-deep-generative-

Reversible generative models • この論文で定義された生成モデルクラスであり、以下を満たす。 – – – – • 変数変換を行う 効率よく密度推定ができる 効率よくサンプリングができる(One-pass) （表で言うと、下から二列目から下がreversible generative modelsになる） FFJORDはReversible generative modelsで、かつ、ヤコビアン行列式計算困難問題による 諸々の制約を解消 27

CNF振り返り • Continuous Normalizing Flowでは変数変換の行列式をトレースに置き換えら れる 𝑑𝑧 𝜕 log 𝑝(𝑧 𝑡 ) 𝑑𝑓 = 𝑓 𝑧 𝑡 ,𝑡 , = −𝑇𝑟 ( ) 𝑑𝑡 𝜕𝑡 𝑑𝑧 𝑡 • Flow後のlog-densityは次のようになる log 𝑝 𝑧 𝑡1 • 通常𝑇𝑟 𝜕𝑓 𝜕𝑧 𝑡 = log 𝑝 𝑧 𝑡0 𝑡1 − න 𝑇𝑟 𝑡0 𝜕𝑓 𝜕𝑧 𝑡 𝑑𝑡 の計算コストは𝑂(𝐷 2)だが、これを𝑂(𝐷)にするため、以下の二つ の工夫を用いる – 自動微分 – Hutchinson’s Trace Estimator 28

Unbiased Linear-time log-density estimation • 𝑣𝑇 𝜕𝑓 は、自動微分によってフォワード計算と同コストで計算可能。 𝜕𝑧 • 𝐸 𝜖 = 0, 𝐶𝑜𝑣 𝜖 = 𝐼に従う𝜖を用いて、トレースは以下を満たす(Hutchinson Trace Estimator) 𝑇𝑟 𝐴 = 𝐸𝑝(𝜖)[𝜖 𝑇 𝐴𝜖] • ODE solverの間は同じ𝜖を用いても大丈夫 29

FFJORD アルゴリズム ෨ • 𝑓の評価に𝑂(𝐷𝐻)かかるとすると、NFは𝑂( 𝐷𝐻 + 𝐷 3 𝐿), CNFは𝑂( 𝐷𝐻 + 𝐷 2 𝐿), ෨ の計算量がかかる。 FFJORDは𝑂( 𝐷𝐻 + 𝐷 𝐿) – 𝐻は最大の隠れ層の次元、 𝐿はレイヤー数、 𝐿෨ はODE Solverの評価回数 30

実験１：Toy dataでの密度推定 • Glow, Planar CNFとFFJORDを比較。 • Glowは密度の境目をうまくモデリン グできていない • CNFは1レイヤーしかないため、複雑 なダイナミクスをモデリングしきれ ない • 一方FFJORDは多層に積めるので、 表現力が高く、すべてのデータの密 度をうまく推定できている。 – ODE Solverの評価回数は70~100回 だった 31

実験２：Real dataでの密度推定 • • • • UCI Datasetsから５つと、MNIST,CIFAR10で実験 Reversible generative modelsの中では、CIFAR10を除きFFJORDが最も良い結果 最新の自己回帰モデルにはちょいちょい負ける GlowやReal NVPは複数のフローを必要とするが、FFJORDは単一のフローでもそ こそこいいモデリングができる • Glowと比べ、モデルのパラメータ数は2%以下 – 本気出せばGlowに勝てそうだけど、あえて研究の余地を残してる感がある。 32

実験３：VAEのvariational inference • VAEのエンコーダにFFJORDを用いる。 • Planar NF, IAF, Sylvester NF(Berg et al., 2018)と比較 • ４つのデータセット全てでFFJORDが最も良い 33

分析：Bottleneck Capacity • Hutchinsonのトレース推定の用いるノイズの次元は、以下のトリックで𝑓の中 の最小の隠れ層（bottleneck）の次元ℎで済み、それによって推定の分散を下 げることができるんじゃない？と筆者は（理論根拠無く）述べている。 – なお、先の実験ではbottleneckは𝑓の表現力を落とすので用いられていない。 • それを確かめた結果が以下。ノイズの分布としてガウス分布を用いた時は訓練 が早く進むけど、ラデマッハ分布(半々の確率で-1か1)だとその効果はない。 34

分析：関数評価回数とデータの次元の関係 ෨ • データの次元が増えるほど、関数評価回数𝐿も増えるんじゃない？という分析 – 𝐿෨ がDに依存することは、計算量の観点から好ましくない • VAEの潜在変数の次元を色々変えた時に、関数評価回数がどう変わるかを可視 化 – データの次元と関数評価回数の関係性は見られなかった。 – データの次元というよりは、学習しなければいけない変換の難しさに関数評価回数は 依存すると思われる。 35

分析：Single-scaleとMulti-scaleなアーキテクチャ • Real NVPやGlowはMulti-scaleなアーキテクチャを用いることによってモデル の表現力を高めた。 • FFJORDで同様のことをすると、関数評価回数がだいたい二倍になり、精度は 少しだけ上がった。 36

FFJORDの限界１：関数評価回数が増えすぎると計算できなくなる • 関数評価回数は事前にどれくらいまで増えるかはわからず、学習が進むに従い 増えていくが、あまりに増えていくとフォワード計算に時間がかかり過ぎてし まう。 – Weight decayやSpectral Normalizationが関数評価回数を抑えるのに役立つが、それ はモデルの表現力を損なってしまうことにつながってしまう。 37

FFJORDの限界２：硬い微分方程式を解くのは大変 • 近似解を計算するためのある数値的方法が、刻み幅が限りなく小さくない限り 数値的不安定になる微分方程式を、硬い方程式、と呼ぶ。 • 硬い方程式でもうまく解けるようなODE Solverはあるが、計算時間がかかり 過ぎて今回のような実用には耐えない。 • 実験的には、わずかなweight decayを入れれば、微分方程式は硬くならないら しい。 38

結論 • 尤度計算可能でone-passでサンプリングできるreversible generative modelで あるFFJORDを提案。 • 変数変換に用いられる関数𝑓の制約を外すために、以下の工夫 – – – – Continuous dynamics 自動微分 Hutchinson’s trace estimator black-box ODE solvers • Continuous dynamicsの研究には多くの改善の余地があるだろう。 39

感想 • 結局、 𝑑ℎ 𝑡 𝑑𝑡 = 𝑓(ℎ 𝑡 , 𝑡, 𝜃)というアイディアが全て • 高次元データに適用するには計算時間の課題があるが、それも来年あたりには 解決されてそう • Optical flowや、流体シミュレータとかに応用できないかな。 • 読んでてとても楽しかった。 • 実装も上がってる（ODE solverの勾配計算をGPUでやるところも含め）ので、 すぐ試せる。 40

Appendix: NODEの解の一意性 • 一般に、ODEの解が一意に定まるためには、zについてリプシッツ連続、tにつ いて連続であれば良い – ピカール・リンデレフの定理 • ダイナミクスをNNとする場合、重みが有限であり、tanhやReluを活性化関数 として用いていれば大丈夫。 41