深層学習モデルを用いたノンパラメトリック回帰問題に関する最近の研究

大野 健太
エンジニア

2019-11-05 11:03:46

図1:ReLU-MLPによる2次関数の近似.このネットワークを用いるとHölder関数を効率的に近似できる([Yarotsky, 2017]より引用)

 

深層学習モデルはこれまで様々な機械学習タスクにおいて成功を収めてきています.それに触発され,深層学習モデルの成功要因を理論面から解明する試みが盛んに行われています.特に深層学習の理論研究(特に統計的学習理論と呼ばれる分野)では,主に3つの問題提起がなされ,それに対する様々な回答がなされています [Poggio et al., 2016]:

  • 表現能力:深層学習モデルはどんな関数を(効率的に)推定できるのか [Cybenko, 1989; Telgarsky, 2016; Eldan and Shamir, 2016; Sonoda and Murata, 2017]
  • 最適化:なぜ(確率的)勾配法が「良い」解を見つけることができるのか [Li et al., 2017; Jacot et al, 2018; Du et al., 2018; Allen-Zhu et al., 2018]
  • 汎化能力:深層学習モデルは多数のパラメータを持つにも関わらず,なぜ過学習せずに汎化するのか [Hardt et al., 2016; Belkin et al., 2018; Arora et al., 2018]

(関連文献を網羅することはできませんので代表的な研究や最近注目されている論文のみを挙げました,それぞれのトピックに興味のある方は上記の論文の関連研究を参照ください.また,[Suzuki, 2019b]も参考にしてください)本稿では,ノンパラメトリックな回帰問題における,表現能力と汎化性能に関する一連の研究を紹介します.

続きを読む »

分散深層学習における耐故障性と可塑性

Kota Uenishi

2019-11-01 10:22:40

ImageNetを15分で学習して以来 [1]、Chainerと沢山のGPUを使って深層学習を並列化し、一回の学習に必要な時間を大きく短縮することができるようになりました。その後、ImageNetの学習は深層学習における並列化 ・高速化のデファクト標準ベンチマークとなりました [2]。それと同時に、深層学習の並列化および大規模化は進み、複数GPUどころか複数ノードで学習することは当たり前のこととなりました。深層学習の計算が大規模化し所要時間はどんどん短くなりましたが、一般的にはノードが増えれば増えただけ部分故障の確率は高くなります。また、大規模なクラスタでは個々の分散ジョブをスケールアウトしたりスケールダウンする機能、つまり可塑性をもとにした計算資源のやりくりが運用上重要になってきます。そこでChainerを拡張し、分散深層学習に耐故障性だけでなく可塑性を導入する実験を行いましたので、ここで報告したいと思います。また、実験に利用したライブラリを eChainer として公開しました [3]。

深層学習の計算が大規模化し所要時間はどんどん短くなりましたが、一般的にはノードが増えれば増えただけ部分故障の確率は高くなります。そこで、部分故障があっても計算が継続できるような仕組みがあれば、このような問題に頭を悩ませるようなこともなくなります。

また、ノードが途中で減っても動作継続できるということは、大抵の場合はノードを途中で追加しても動作継続できるということです。これができると、学習を実行中にGPUを追加することで学習を加速することができます。これは、大規模なクラスタ環境ではとてもメリットが大きいことで、例えば、ジョブ終了や失敗などが原因で、クラスタ上の別の場所で余っていた計算資源を動的にジョブに追加することで、ジョブを早く終わらせることができるようになり、クラスタ上のリソース配分の柔軟性が増します。リソース利用効率を上げることができ、同じ計算基盤への投資でより多くのリターン(よいモデル、よい計算結果)を得ることができるようになります。動的に計算資源と追加したり減らしたりできることを、そのシステムに可塑性(Elasticity)があるといいます。 eChainer というプロトタイプ名は、 Elastic Chainer を短縮してつけたものです。

基本設計とシステム構成

Chainerには、分散学習用の内部コンポーネントが含まれており、ChainerMN という名前がついています。これを使ったこれまでの分散深層学習については、弊社鈴木の解説[4] や、その肝となる AllReduce の計算についてはインターンの上野さんの寄稿 [5] をご覧ください。ChainerMNの Communicator [6] [7] は、MPIにおけるCommunicatorをPythonのインターフェースクラスとして表現し、それを実装したものです。ChainerMNにおける分散深層学習は、基本的に全てこのCommunicatorを使っています。Communicator の実装クラス PureNcclCommunicator を通じて NCCLを利用した場合のイメージを図1に示します。NCCLは、NVIDIAが開発しているGPU専用の集団通信ライブラリです[8] 。ChainerMNでは、CuPyのCythonの実装を通じてNCCLを利用します。

図1: Chainerを使った分散深層学習の内部コンポーネントの構成図
図1: Chainerを使った分散深層学習の内部コンポーネントの構成図: PureNcclCommunicator はCuPy を通じてNCCLを呼び出す

いくつかあるCommunicatorの実装は、いずれもシステムの部分故障を前提としたものにはなっていません。最も利用されているのは PureNcclCommunicator ですが、その内部で利用しているNCCLが 2.3 まではシステムの部分故障を前提としたものになっていませんでした。例えば ncclAllReduce() の集団通信に参加しているプロセスがひとつでも故障すると、他のプロセスで呼ばれた ncclAllReduce() は永遠にブロックされたままになります。

このとき、Communicatorの内部で起きていることを詳しく解説します。ChainerMNは内部的にはCuPy経由で ncclAllReduce() を利用します。CuPy は Cython 経由で全ての関数を呼び出します。ところがPythonのC拡張の仕様では、ユーザーから送られるUnixシグナルはPythonが設定したシグナルハンドラによって擬似的にブロックされた状態になり、シグナルに対するコールバックはPython上の実行に戻ってから呼ばれます [9] 。つまり、ncclAllReduce() の呼び出しが戻らない限りは SIGTERM等を全く受け付けず、ずっと ncclAllReduce() の中で止まったままになります。集団通信に参加しているプロセスが一つでも故障すると、その集団通信はずっと終わらないままブロックするということになります。この様子を図 2 に示します。


図2: AllReduce を呼んでいる最中はSIGTERMが擬似的にブロックされ、 ncclAllReduce() 中のループから抜け出すまでユーザー側で処理をすることはできない。ncclAllReduce() は故障プロセスを含む他のプロセスからの通信を待ち続ける。

実用的には、集団通信がハングしていることを検知して、シグナルハンドラを設定できないSIGKILL等で各ノードでひとつひとつ手動でkillしてまわらなければならなくなります。 OpenMPIはこの状態は検知してジョブを強制終了するといったことはできませんから、ジョブが進行しないまま半永久的に計算リソースを占拠し続けることになります。これが、 ncclDestroy() のAPI導入前の状態でした。

ちょうどよいタイミングで、昨年の今頃のことでしたが、NCCL 2.4から導入される ncclDestroy() というAPIをリリース前にテストすることができました [10]。この関数は、NCCLを使ったアプリケーションに耐故障性を導入するために、最小限でありながら十分な機能追加です。個人的なことですが、NCCLの開発者とメールをやり取りしてこのアイディアを聞いたときはに本当に感心しました。わたしが一年近く悩んでいたこの問題について、既存のコードに影響を与えず問題をエレガントに解決するベストなアプローチだったからです。

ChainerMNを利用した分散深層学習が全てCommunicatorに立脚しているということは、これさえ故障に耐えうる仕様になれば、ChainerMN上の分散深層学習は全て耐故障性を備えることができるようになります。ということで、まずはCommunicatorに耐故障性をもたせるためにncclDestroy() を導入することを目指します。 ncclDestroy() は、任意のタイミングで特定の ncclCommunicator (混乱しそうですが、これはNCCLで内部的に利用するオブジェクトです)を破壊して、そのタイミングで実行されていたあらゆる集団通信を強制終了させることができます。つまり、 ncclAllReduce() が故障したプロセスからの永久にこないメッセージを待っているときに横から強制終了させることができるということです。これによって、NCCLの集団通信中にブロックされた状態から戻れなくなるという問題が解決できます。あとは、NCCLを利用するアプリケーションが、どのようにシステムとして故障を検出し、 ncclDestroy() によってどのようにncclAllReduce() の強制終了をハンドリングするかという問題になります。

まず、ノードの死活監視のために etcd を導入します [11]。Chainerを使っている学習プロセス内で etcd クライアントを別スレッド上で動作させ、このスレッドが etcd とKeepAliveをします。これによって、システムの基本構成は図3 のようになります。


図3: eChainer を使った学習プロセスの基本構成:
Communicator 内にetcd を用いた故障検出器を追加した。

このように死活監視するチャンネルを設けることによって、ひとつのプロセスの故障を全体に通知することができるようになります。具体的には、各プロセスは etcd の特定のprefix上にエフェメラルファイルを作って、それをお互いに監視することで死活監視とします。エフェメラルファイルとは、クライアントとサーバーの双方が正常に動作してKeepAliveが維持されているときにだけ保持されるファイルです。例えばクライアントが故障すると、一定時間後にこのエフェメラルファイルが消滅し、他のプロセスはこのエフェメラルファイルが消滅した通知を受け取ることができます。実はここが分散システムで最も難しい故障検出の問題を解決している部分なのですが、etcdを使うことで複雑な実装も簡単に済ませることができました。

この通知をトリガーにして、全てのプロセスは学習(および集団通信)を一旦停止します。このときに ncclDestroy() を利用します。これによって動作中の ncclAllReduce() と、それを利用していた NCCL のリングは全プロセスで破棄されます。ncclAllReduce() は同期的な集団通信で、全てのプロセスが同じ iteration 中にいることが保証されていますから、このように破棄されたことをPythonの例外によって表現することができます。これで、アプリケーションからも故障を検出をできるようになりました。その様子を図4 に示します。


図4: プロセス故障の検出はファイル削除のイベントとして全ノードに通知され、それをもとに ncclDestroy() が呼ばれる。ncclDestory() であれば、通信待ちの ncclAllReduce() を強制的に終了させることができる

このようにノードの離脱を etcd のイベントとして表現しましたが、実は、ノードの追加も同様に etcd のイベント(エフェメラルファイルの追加)として表現することができます。同様に、 ncclDestroy() を発行してNCCLのリングを破棄して、あらたに追加されたノートを加えてNCCLのリングを再構築することにより、分散学習の動的なスケールアウトを実現することができます。

しかしながら、NCCLのリングの破棄と再構築はCommunicator の size や rank の変更を必要とします。つまり、全体のプロセス数が変わった場合は、配った学習データを割り当てなおしたり、学習率のスケールルール[12] に従って、改めて学習率を設定する必要があります。また、新しく追加されたプロセスはモデルのパラメータやオプティマイザのパラメータなどの学習の途中状態を知りませんから、学習を再開するためには、これらの情報を別のプロセスのメモリから集めてやる必要があります。これらの処理はなるべく共通化してユーザーが書かなくてもよいようにしたいところでしたが、今回の実験ではImageNetにフォーカスして学習スクリプト上に作り込むことにしました。基本的には、プロセス増減の例外を受けて、

  1. 学習データの割当をやり直す
  2. Optimizer やモデルのオブジェクトを作り直す
  3. ChainerのTrainerを作り直してプロセス間で配り直す
  4. 学習を再開する

という処理をフラットに while ループの中に実装しました。詳しくは eChainer に付属するサンプルコードをご覧ください。

ここまで基本的な設計を解説しましたが、実はこのアプローチには難しい問題がひとつあります。ノードの追加や故障は、現実的にはそうそう起こるものではありませんが、追加や故障を受けた際に計算を再開してよいかどうかの条件は自明ではありません。以下は簡単な例ですが、

  • 分散深層学習を実行するプロセス数が大きく減ると、学習率の調整によって学習自体は続けることができるが、学習にかかる時間は大きく延びる。例えば48時間で終わると思っていた学習が、途中でプロセスが大きく減って残りETAが64時間まで伸びてしまった。この学習を途中で停止してやり直した方が早くはないか?
  • 分散深層学習を実行するプロセス数が増えると、学習率の調整によって学習を続けることはできるが、例えばバッチサイズが64000まで増えてしまったら、32000のときとは別の学習レシピが必要になる(LARS [13] 等)。バッチサイズをある範囲でコントロールしたい
  • ノード追加のタイミングがすこしバラバラになってしまって、 8プロセス(8GPU)追加するときに1回ずつ認識されてしまい、計8回の例外が投げられてしまい、NCCLのリング再構築やモデルの再同期など重い処理が不必要に走ってしまうと非効率
  • ある学習レシピは32プロセス8GPUでしか動作しない(バッチサイズなどのパラメータが慎重に設計されている)。重要な学習なので、1プロセスの失敗で止まることなく、自動的に動作継続はしてほしいが、1プロセス減った状態で勝手に計算を再開させることなく、再度計算リソースが追加するまで待ちたい
  • ジョブの進捗が8割を過ぎていたら頑張って動作継続をしてほしいが、5割程度の進捗ならまた別途やり直してもよい

といったことがあります。こういった、計算資源の増減に対する複雑な対応や要件をすべて単一の実装で実現したり、設定ファイルで記述させるといったことは簡単ではありません。そこで、Chainerが持っている Define-by-Run という考え方[14]に触発されて、私もこれをDefine-by-Runで実現することができないかと考えました。

Define-by-Run Re-configuration

Define-by-Runの基本的な考え方は、 (1) やりたいことをプログラムで表現する (2) そのプログラム表現と実行が 1:1 で対応する、というものです。こうやって書くと当たり前のことに見えますが、これによって、高い表現力と、任意の条件判断を追加できる、失敗した箇所がスタックトレースと対応するなどのメリットがあります。 Chainerではニューラルネットワークの入力、途中の forward 処理、出力を表現して実行することが目的でしたが、 eChainer では計算資源の増減と、それに対してジョブがとるべき対応を表現して実行することが目的となります。 eChainer では、これを ScalePolicy() の継承クラス として実装してCommunicatorに渡すことで、学習時にポリシーが評価および実行されるようになります。ScalePolicy()を継承して、ok2run(self, hosts, initial) というメソッドを実装するだけです。例えば、Fail-stopといわれる最も簡単なポリシーを表現するには、以下で十分です。

class FailStop(echainer.ScalePolicy):
    def __init__(self, n): self.n = n
    def ok2run(self,  hosts, initial):
        if len(hosts) == self.n: return “ok”
        elif initial: return “wait”
        else: return “fail”

ok2run() は、計算を再開してよければ “ok” を返します。規定の条件を満たすまで待機するべきであれば “wait” を返します。このジョブを失敗として終了するには、 “fail” を返します。このオブジェクトはジョブの実行中は保持されますから、Optimizerなどの任意の状態や条件をこのオブジェクトのメンバーとして持たせることによって、上記で述べたような条件を好きなように設定することができます。ユーザーは計算の再開、待機、中止を決定する任意の条件をプログラムによって表現することができます。

このPolicyとetcdのアクセス先を渡すことで、ChainerMNのCommunicatorと互換で、耐障害性のあるCommunicatorを作ることができます。

policy = YourOwnCoolScalePolicy(...)
etcd = “etcd://e1:2379,e2:2379,e3:2379/your-job-name”
listen = “10.0.0.1:9889”
comm = echainer.NcclCommunicator(policy, etcd, listen)

実験

この eChainer を使って、実際にImageNetの学習をスケールアップさせたり、スケールダウンさせる実験を行いました。

ChainerCVの example にあるImageNetの学習スクリプトをベースにしたので、学習レシピは [12] と同じです。実験に用いた環境はMN-1b上のKubernetesを使ったコンテナです。ncclAllReduce は InfiniBand HDR上で動作しますが、その他の通信は 10GbE上のTCP/IP上で行われます。2-4 ノード(16−32GPU)の間で増減する実験をしました。ノード故障は簡単に SIGTERM で行われています。ScalePolicy は MinMax というものを実装しました。プロセス数が一定範囲内にある限り動作を継続するというものです。

まず、ノードの増減がなく正常に終了した学習の進捗です。以下の図はいずれも横軸に実時間、縦時間にImageNetの学習エポックをプロットしています。


図5: さまざまなGPU数でImageNet を学習した際の速度

GPUの数に応じて学習の速度(線の傾き)が変化しているのがわかります。以降のグラフもそうなのですが、 epoch が離散的に変化するために線が破線状になっています。次に、学習の途中で2ノード(8GPU)追加してみます。


図6: 学習途中でノード追加した場合の学習速度の変化

緑の線と、茶色の線がそれぞれ別のタイミングで途中ノードを追加したものです。追加の前後でも同様に学習が動作していることがわかります。それぞれ、20000秒付近、34000秒付近で学習の速度が変化し、32GPUと同じ速度になっていることがわかります。また、このときのvalidation set に対する最終精度は 76.4% でした。1回だけの測定ですが、元の論文[12]と同程度の精度がノード追加にも関わらず再現できました。

次に、ノードが途中離脱した場合です。32GPUと16GPUで実行していたジョブを、それぞれ途中でプロセスを落とすことでGPU数を減らしています。


図7: 学習途中でノード削除した場合の学習速度の変化

赤線では、GPU数が32から16に途中で減っています。同じタイミングで、線の傾きも16GPUのそれと同じになっています。同様に、16から8に減った緑線の場合でも8GPUと同じ速度に傾きが落ち込んでいることがわかります。また、プロセスが離脱する前後でもジョブ全体が落ちることはなく動作継続することができました。このときのvalidation set に対する最終精度は 76.0% でした(1回測定)。スケールダウンのときと比較して 0.4% 低下していますが、これが常に下がるものなのかどうかは原因も含めて今後調査する必要があります。

このように、分散深層学習のジョブを実行中に動的に計算資源を追加することにより学習の進行速度を上げたり、ジョブを止めることなく動的に計算資源を一部取り除くことができるようになりました。

関連研究および関連システム

分散深層学習の先駆けであるDistBeliefはもともとGoogleの大規模分散システム上で耐障害性を持って動作していました[15]。この系譜を受け継ぐ TensorFlow はパラメーターサーバーを持つモデルで、パラメーターサーバー以外のワーカーノードが故障しても、その部分のミニバッチを別のノードで再計算すれば済みました。これは非同期(Asynchronous) SGD といわれる分散方式で、始めから耐障害性を考慮されたものです。しかしながら、これにはパラメーターサーバーに負荷が集中してボトルネックになりやすい、古い勾配を使って学習してしまうなどの問題がありました。
ChainerMNを始めとするMPIベースの分散深層学習では、同期(Synchronous) SGDといわれる分散方式を採用し、HPC技術の恩恵を受けて上記の問題点を解決し、深層学習の高速化に寄与しました。しかしながら、HPC技術の恩恵を受ける代わりに、非同期SGDが持っていた耐障害性を失うこととなりました。
HPCの分野でも、もちろん同期的な集団通信に耐障害性を与える研究が行われています。中でもULFM (User Level Fault Mitigation) [15][16] はMPIのWGで精力的に標準化が検討されています。これはMPIに障害のハンドリングするAPIを追加しようとするものです。

まとめ

分散深層学習に耐障害性と、可塑性を導入する実験的なライブラリ eChainer と、その実験結果をまとめました。特にプロセス数が増減したときのハンドリングをどう行うかについて、 Define-by-Run の考え方に基づいた表現方法を提案しました。

[1] T. Akiba, S. Suzuki and K. Fukuda, “Extremely Large Minibatch SGD: Training ResNet-50 on ImageNet in 15 Minutes,” arXiv:1711.04325, 2017.
[2] https://mlperf.org
[3] eChainer
[4] 分散深層学習とChainerMNについて
[5] 分散深層学習を支える技術:AllReduceアルゴリズム
[6] 分散深層学習パッケージ ChainerMN 公開
[7] Chainer Doc: Communicators
[8] NVIDIA Collective Communications Library (NCCL) https://developer.nvidia.com/nccl
[9] signal — Set handlers for asynchronous events
[10] Preliminary abort mechanism and an API for querying asynchronous errors.
[11] https://etcd.io
[12] P. Goyal, P. Dollár, R. Girshick, P. Noordhuis, L. Wesolowski, A. Kyrola, A. Tulloch, Y. Jia and K. He, “Accurate, Large Minibatch SGD: Training ImageNet in 1 Hour,” arXiv:1706.02677, 2017.
[13] Y. You, I. Gitman, and B. Ginsburg. Large Batch Training Of Convolutional Networks. arXiv:1708.03888, 2017.
[14] Tokui, Seiya, et al. “Chainer: A Deep Learning Framework for Accelerating the Research Cycle.” Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. ACM, 2019.
[15] ULFM 2.0 Release
[16] George Bosilca , Aurelien Bouteiller , Amina Guermouche , Thomas Herault , Yves Robert , Pierre Sens , Jack Dongarra, Failure detection and propagation in HPC systems, SC’16.

話者の顔ランドマークを用いた音声分離

Motoki Sato

2019-10-29 14:48:18

本記事は、2019年夏のインターンシップに参加された柴田佳祐さんによる寄稿です。



はじめに

PFN2019年夏季インターンに参加した柴田佳祐です.普段は京都大学情報学研究科でコンピュータビジョンの研究をしています.今回のインターンでは音声信号処理をやってみたいと思い,インターンではSpeech Separation(音声分離)のタスクに取り組みました.

背景

まず,Speech Separationとは,複数人の音声が混ざった混合信号から各人の音声を取り出すタスクです.人間の場合は,カクテルパーティー効果として知られているように関心のある話者の音声に注意を向けることができます.しかし,複数人の音声が混ざるような環境で音声を聞き取って利用するロボットの場合,そのままではカクテルパーティー効果は働きません.


今回取り組んだAudio-Visual Speech Separationは,Speech Separationに聴覚情報だけではなく,視覚情報を利用するという研究です.視覚情報を利用すると性能の向上が見込まれるだけではなく,映像中で話している人と,分離された音声の対応づけを行うことができます.

先行研究

Audio-Visual Speech Separationの先行研究については,以下の2つの論文を主に参考にしました.

[Ephrat+2018]

https://looking-to-listen.github.io/
視覚情報を利用するためにFaceNetのような顔認識ネットワークを利用しており,全体のモデルサイズが非常に大きくなっています.また,分離を行う対象が対象の人数,例えば2人の場合と3人の場合でモデルの構造が異なっており,話者の数や検出できる顔の数が異なる場合に単一のモデルで適用できないという問題がありました.

[Morrone+2019]

https://arxiv.org/abs/1811.02480
こちらは,顔から特徴を抽出するネットワークを使わずに既存の顔ランドマーク検出器を視覚情報として利用するという論文です.顔ランドマークとは,目,眉,唇の輪郭などの識別可能な顔のパーツ上の点のことを言います.そのため,サイズが小さく利用しやすいモデルになっています.このモデルは,一度に全話者の音声の分離を行うのではなく,混合信号と一人分の話者の視覚情報を入力することで当該話者の音声信号の分離抽出を行います.これにより,話者の数に依存しないモデルになっています.

https://www.youtube.com/watch?v=YQ0q-OFphKM

問題設定

どちらの先行研究も音声分離のために顔情報を利用していますが,現実的には常に顔検出器によって顔を検出できるとは限りません.後ろを向いている話者やカメラから映らない範囲にいる話者など,顔検出が失敗する場合が考えられます.例えば,2話者の混合音声から1話者の音声を取り出す場合を考えると以下のような顔情報の入手パターンが考えられます.

  • A: 2人とも手に入る場合
  • B: 目的話者(取り出したい話者)のみ手に入る場合
  • C: 非目的話者(取り出さない話者)のみ手に入る場合

Ephrat+2018のモデルでは,顔1と顔2を両方同時に利用して,顔1の人に対応する音1,顔2の人に対応する音2をそれぞれ取り出します.この場合は,どちらか片方の顔が手に入らない場合に対応することができません.

Morrone+2019のモデルでは,Aの設定の場合,目的話者(話者1)の顔を利用して目的話者の音声を取り出します.次に,両方の人の音声を取り出すために話者1と話者2を入れ替えて同様に音声を取り出します.この場合,2人分の顔が手に入る場合にも1人分の顔のみを利用して音声分離を行いますが,2人の顔が手に入る場合は2人の顔を使う方が性能が向上すると考えられます.今回は,手に入った分の顔を使えるだけ使って音声分離を行うような手法を考えて実装しました.

 

A:
両方
(目的話者, 非目的話者)の顔
が利用可能
B:
目的話者
のみ利用可能
C:
非目的話者
のみ利用可能
Ephrat+2018
Morrone+2019
Ours

 

提案手法

顔が見えない場合に対応するため,最大の人数(今回は2人)に対応するモデルを作り,顔が手に入らない部分にはダミーの顔情報(今回は要素が0のベクトル)を入れて学習しました.

実験

今回考案した手法では,A,B,Cそれぞれの設定で訓練を行なった場合と,それぞれの設定を混ぜたデータで訓練を行なった場合について実験を行いました.データセットはThe GRID audiovisual sentence corpusを利用しました.データセットの33話者のうち,訓練データは25話者,バリデーションは4話者,テストには4話者を用い,話者に依存しないモデルとしてのテストができるように分割しました.

 

結果

SDR(音声対全歪比)を用いて評価しました.テストデータの混合信号のSDRは,0.292でした.SDRは,高ければ高いほど分離結果が良いことを表しています.ベースラインは,Morrone+2019の手法を参考にして実装したものを用いています.
Aの実験:2人の顔が利用可能

手法 訓練時 テスト時 SDR
ベースライン
([Morrone+2019] を参考とした実装)
両方 両方 4.50
提案手法 両方 両方 5.09


A(2人の顔が利用可能)の設定では,ベースラインの手法では1つしか顔を利用できないため,目的話者の顔のみを利用して訓練とテストを行いました.Aの設定でもベースラインが実質的に利用できる顔情報はBの設定の場合と同じです.一方,提案手法は顔を複数受け付けることができるモデルであり,2人の顔を利用して訓練し2人の顔を使ってテストしました.
訓練とテストで2人の顔を使うことでSDRが上がり,性能が向上しました.

 

Bの実験 : 目的話者のみ利用可能

手法 訓練時 テスト時 SDR
ベースライン
([Morrone+2019] を参考とした実装)
目的話者のみ 目的話者のみ 4.50
提案手法 (Bのみで訓練) 目的話者のみ 目的話者のみ 4.50
提案手法 (A, Bを混ぜて訓練) 両方 目的話者のみ 4.65


B(取り出したい話者のみ利用可能)の設定では,ベースラインの手法と提案手法ともにテスト時には目的話者の顔のみを利用しました.提案手法の訓練時は,目的話者の顔とダミーの顔のデータ(Bの設定)のみで訓練する場合と,両方の話者の顔のデータ(Aの設定)とBの設定のデータで訓練する場合をテストしました.

AとBを混ぜて訓練する場合では,ベースラインと比較してSDRは低下しませんでした.

 

Cの実験 : 非目的話者のみ利用可能

手法 訓練時 テスト時 SDR
ベースライン ([Morrone+2019] を参考とした実装) N/A N/A N/A
提案手法 (A, B, Cを混ぜて訓練) 両方 非目的話者のみ 4.15


C(取り出さない話者のみ利用可能)の設定では,ベースラインの手法は利用できる顔が無いためテストすることができません(
今回のような2話者のケースであれば,顔2を入力することで顔2音声を取り出し,入力信号から減算することもできますが).提案手法では,A, B, Cの設定の全てのデータを混合して訓練し,テスト時に非目的話者のみを用いた場合,SDRは他の設定でテストする場合と比較して少しの低下となる結果が得られました.


まとめ・感想・謝辞

今回の手法は,2話者で顔情報が得られない場合について実験を行いました.3,4話者の場合や不特定多数の話者の場合,雑音が混ざる場合についてはまだ実験を行なっておらず,今後の課題だと考えています.

このインターンでは,GPUクラスタを利用して学習を行いました.ChainerMNを用いると,16GPUなど,多数のGPUを使いたい場合も簡単に学習を行うことができました.また,並列でジョブを実行させることができ複数の条件で比較を行いたい時にすぐに結果が得られたため,多くの試行錯誤を行うことができました.環境設定にはDockerfileを利用でき,さらにcuDNNのdeterministicモードと乱数シード値の固定を行うことで,同じ設定なら同じ結果が再現する環境だったのも非常に良かったです.

1ヶ月半という通常であれば研究をするには短い期間でしたが,データセットの準備をしていただけたことやすぐに整う再現性のある環境,同じチームの方や社員の方のアドバイスのおかげで期間内に新しいアイディアを定量的に評価することができました.特に,メンターの佐藤さん,谷口さんには非常にお世話になりました.音声のタスクに取り組むのは初めてでしたが,学習を行う際のテクニックや音声信号処理の議論など非常に勉強になりました.ありがとうございました.


メンターからのコメント

メンターを担当したPFNの佐藤と谷口です.

今回柴田さんに取り組んでいただいた音声分離はロボット向けの音声ユーザインタフェース(VUI)における音声処理において重要な技術です.1990年代から複数マイク(マイクアレイ)を用いた方式は盛んに研究されてきましたが,ここ最近,deep clusteringpermutation invariant trainingなど,深層学習を活用して1マイクでも高精度に音声分離が可能な技術が発表されており,大きな期待を集めています.しかし,遠距離からの音声の分離,耐雑音性能,話者のトラッキングなど,ロボットVUIへの実応用には多くの課題が残っています.
今回, 柴田さんに取り組んで頂いた,映像など他のモーダルの活用はその課題へのアプローチの一つだと考えられます.

マルチモーダルな機械学習のため,通常より大きいデータセットのサイズに起因する問題や,実装そのものが難しい部分が多くありましたが,柴田さんにはコンピュータービジョンの分野の知識を活かしつつ,研究開発をしていただきました.音声分野は本人の分野外でしたが,意欲的に勉強して取り組んで頂き,インターンの限られた時間の中で性能評価まで行うことができました.

ニューラルネット3D表現に対する微分可能レンダラー

hkato

2019-10-25 10:42:30

本記事は、2019年夏のインターンシップに参加された島田直治さんによる寄稿です。


PFNの2019年夏季インターンシップに参加させていただいた東京大学大学院・情報理工学系研究科・修士2年の島田直治 (http://ut25252.starfree.jp/) です。大学ではCG (コンピューター・グラフィックス) 関連の研究をしています。インターンでの研究テーマとして、CGとの関わりも深い「微分可能レンダラーを用いた3D再構成」を選びました。研究としては、3D表現としてニューラルネット関数を用いることを着想し、これに対する新たな微分可能なレンダリング方法を考案、実装して数値実験を行い3D再構成の精度を先行研究と比較評価しました。

研究内容に関するまとめスライドをこちらに公開しています。このスライドの内容について、以下で解説していきます。


 
また、作成したプログラムはこちらで公開しています。

微分可能レンダラーを用いた3D再構成

CV (コンピューター・ビジョン) の分野で現在精力的に研究が行われているテーマの一つに、たった1枚の画像が与えられた場合にそこに写っている物体や景色の3D構造を把握しようという “single-view 3D reconstruction” があります。


これは、例えばロボットが目の前にある物体を掴む動作(グラスピングと呼ばれる)を行う場合や、自動運転車が歩行者や障害物を把握して回避する場合などに応用が見込まれます。

問題点として、1枚画像からの3D再構成という課題は明らかに条件不足な不良設定問題であり、他の情報を使わない限りは解くことが出来ないということが挙げられます。我々が日常生活において視覚情報からある程度3D構造を把握できるのは、これまでの人生経験で「学習した常識」を使って形状を「予測」しているからです。パソコンに3D再構成を行わせる場合にも、同様に常識を学習させて予測させる手法が考えられます。

3D supervisionによる学習 [2]

画像を入力とし、3D構造を出力とするような予測モデルをニューラルネットワークで表現し、教師3D構造データとの差分を用いて最適化学習すれば出来そうです。実際数多くの研究が行われています[5-10]。このように3D構造を教師データとして用いる学習を3D supervisionと呼びます。

3D supervisionによる学習の問題点としては、教師データとなる3Dデータを大量に必要とすることです。現状では3Dの教師データを大量に用意するというのはあまり現実的な選択肢ではありません。そこで、画像のみを用いて予測モデルを学習させる、2D supervisionな学習方法が模索されています [1-4]。

2D supervisionによる学習 [2]

予測モデルの出力した3D構造から、2Dの画像を生成する (レンダリングと呼ばれる) ことは容易であり、その生成画像と教師データ画像との差分を計算することができます (この場合、教師画像データはどの位置・方向から撮影されたものであるかというカメラパラメータがわかっているものとし、レンダリングの際にはその位置・方向と同じような仮想カメラを設定して画像生成することになります)。出力画像における差分を誤差逆伝播させて、予測モデルのニューラルネットを学習させることになりますが、この時レンダリング部分が微分可能でないと誤差を逆伝播させることが出来なません (直感的には、3D構造を少し変化させた場合に、それに応じて出力画像がなめらかに変化することが要求されます。例えば、三角形メッシュで表現された3D構造をラスタライズの手法によりレンダリングする場合、ピクセル中央にメッシュが入るか入らないかで不連続にピクセル値が変化してしまいます。メッシュの位置変化に対して出力がなめらかに変化しないので、このままでは微分可能ではありません [1])。このように、2D supervisionな学習には微分可能なレンダラーの開発が必要となります。

3D表現と微分可能レンダラー

3D構造の表現方法にはボクセル、点群、メッシュ、ニューラルネットなどがあります。

各3D表現を可視化した図 [8]

それぞれの3D表現(点群以外)について微分可能レンダラーが提案されています。代表的な手法とその利点欠点を以下の表にまとめています。

メッシュ表現を用いる場合 [1][2]は、何らかの初期形状を仮定して、これを変形させることで3D構造の再構成を行うアプローチが主流です (例えば最初に球を仮定してメッシュ構造を作り、目的のティーポットなどに連続的に変形させていきます)。この場合、トポロジー的にことなる物体(穴が空いていたり、複数であったり)を再構成することが難しいという欠点があります。メッシュ表現のもう一つの難点としては、頂点と面からなる複雑な構造のデータを深層学習のフレームワークでうまく扱うことは容易でないことが挙げられます。また、ボクセル表現を用いたDRC [3]では、解像度を上げるにつれて必要なメモリ容量が解像度の3乗で増大するという欠点があります。さらに、ニューラルネット3D表現を用いたSRN [4]では、上2つの欠点を克服しているが、レンダラー部分までニューラルネットで表現することで微分可能レンダラーとしており、その分学習が大変になっているという欠点があります(1つの物体に対して50視点分もの画像を必要としています)。

今回のインターンでは、これらの欠点をすべて克服するような、ニューラルネット3D表現に対する微分可能レンダラーを開発することを目的としました。SRNのようなレンダラー部分をニューラルネットによるものにするではなく、より直接的に行うようなレンダラーを微分可能な形で実現することで達成出来るはずです。これにはボクセル表現のDRCを参考にして拡張することを考えました。まずはDRCについての簡単な解説を行います。

Differentiable Ray Consistency (DRC) [3]

DRCでは、以下のようなパイプラインで3D再構成とレンダリングを行っています。簡単のため、教師データとして白黒のmask画像を用いる場合に限定します。

3D再構成のパイプライン [3]

まず、RGBの画像 (64×64 ピクセル) をEncoder-DecoderによりVoxel 3D表現 (32×32×32) に変換します。次にカメラから見てレイの通り道にVoxelが存在すれば黒、しなければ白といった形でレンダリングします。

微分可能レンダリングとLoss関数 [3]

ただし、Voxelが存在するかしないかという2値表現では微分可能なレンダリングにはなりません。そこで、Voxelには曖昧な中間状態を許すことにし、[0,1]の実数値でレイの透過確率を表すものと定義します。つまり、レンダリング画像の各ピクセルには、レイが通過する全voxelの透過確率をかけ合わせた値が出てくることになります。ここで、Loss関数を教師画像と出力画像の各ピクセル値の絶対値差分の合計値と定義すると、各voxel値について微分可能であることが示されます(論文参照)。つまり、微分可能レンダラーとなっており、Encoder-Decoderのネットワークを学習させて3D再構成を行うことができます(上図参照)。

DRCによる3D再構成の例 [3]

実際に学習したモデルで3D再構成を行った結果はこのようになります(上左図)。また、教師データとしてmask画像だけでなくRGB画像を用いる場合にもLoss関数を拡張することで対応出来ます(上右図)。

Our algorithm (DRS)

DRCでの3D表現をvoxelからニューラルネットに置き換えることを考えます。

voxel表現というのは、323のメモリにそれぞれ一つの実数が格納されていて、(x,y,z)のindex値を指定するとそれに対応する値が一つ返ってくるようなものと考えることができます。これは一つの関数とみなすことが出来るため、上右図のような3入力-1出力のニューラルネットによる非線形関数で置き換えることが可能です。ニューラルネット表現に置き換えることで、一つ一つの値を保持するvoxelよりメモリ効率が大幅に改善することが見込まれます。さらに、入力のx,y,zには連続的な座標の実数値を直接使うことが出来るようになることで学習やレンダリングの自由度が高まり、またデータ点間が関数の滑らかさにより自動的に補完されるため、表面形状が綺麗に再現されるというメリットがあります。これらの特徴は、3D supervisionでの文脈で近年盛んに行われているニューラルネット表現の研究において確認されています [8-10]。

レンダリングについては、カメラから出たレイを適当な間隔で区切ってサンプリングし、サンプリング点の座標をニューラルネット3D関数に入力することで、その点でのレイ透過確率を計算します。これをかけ合わせた値をピクセル値として扱い、Loss関数はDRCの場合と同じように定義することで微分可能となります (上図)。

全体のパイプラインとしては上図のようになり、Encoder-Decoderはニューラルネット3Dの重みパラメータを出力するようになっています。

Results

学習条件をDRCと同様な設定で行いました。データセットにはshapenet V1を用い、car (chair)クラスについては、全7000 (5000) instancesをおよそ7:1:2の比率でTrain,Valid,Testに分け、教師データとしては各instanceにつきレンダリング画像5枚を使用します。

まずは、ニューラルネットによる3Dの学習および表現力をテストする目的で、1 instanceのみの学習を行いました。つまり、ある特定の1物体に限定して、その物体を様々な角度から見たRGB画像およびシルエット画像を用いてネットワークを学習し、学習データには含まれないような未知視点からの画像を再現出来るかどうかをテストします。

左から順に、InputのRGB画像、学習後に未知視点からのレンダリングを行った結果(Gt, 出力, 差分)、3D構造をスライスして可視化した図(ニューラルネット3Dを一定のthreshold値でvoxel化, 教師3Dデータ, 差分)、3D再構成の精度(voxel IoU)を表しています。DRCと比べても十分な精度が出ています。

次に、複数instanceでの学習を行いました。

3D再構成のQualitativeな結果 (見た目)とQuantitativeな結果 (平均精度) を示しています。DRCと同等の精度が得られました。つまり、ボクセルの予測と同等の精度を保ちつつ、メモリ使用量の問題を解決したことになります。さらに、同じくニューラルネット表現を用いたSRN [4]と比べても、学習に必要な視点数(1つの物体あたりに用いることが出来る画像数)が50→5枚へと大幅に削減することに成功しました (SRNでは3D再構成の精度を計測することが困難であるため、精度の比較に関しては行っていません)。

今後の課題

今後の課題としては、

  • 3D再構成の精度を上げる。
  • メモリ使用量の比較。
  • RGB画像での3D再構成実験。
  • DRC以外の先行研究と同条件での比較。

などが考えられます。

引用文献

微分可能レンダラー (2D supervision)

[1] “Neural 3D Mesh Renderer” (Kato+ CVPR 2018)
[2] “Learning View Priors for Single-view 3D Reconstruction” (Kato and Harada CVPR 2019)
[3] “Multi-view Supervision for Single-view Reconstruction via Differentiable Ray Consistency” (Tulsiani+ CVPR 2019)
[4] “Scene Representation Networks: Continuous 3D-Structure-Aware Neural Scene Representations” (Sitzmann+ NIPS 2019)

3D supervision (メッシュ、ボクセル、点群)

[5] “PM-GANs: Discriminative Representation Learning for Action Recognition Using Partial-modalities” (Wang+ ECCV 2018)
[6] “Octree Generating Networks: Efficient Convolutional Architectures for High-Resolution 3D Outputs” (Tatarchenko+ ICCV 2017)
[7] “A Point Set Generation Network for 3D Object Reconstruction From a Single Image” (Fan+ CVPR 2017)

3D supervision (ニューラルネット関数)

[8] “Occupancy Networks: Learning 3D Reconstruction in Function Space” (Mescheder+ CVPR 2019)
[9] “DeepSDF: Learning Continuous Signed Distance Functions for Shape Representation” (Park+ CVPR 2019)
[10] “Learning Implicit Fields for Generative Shape Modeling” (Chen and Zhang CVPR 2019)


メンターからのコメント

メンターを担当したPFNの加藤と安藤です。CGのスキルを活かしつつ深層学習のスキルを高めたい、という希望をもとに両者が交差するテーマである新規な微分可能レンダラーの開発を担当していただきました。自ら関連研究をサーベイし読み込み手法を開発してゆく能力が高く、本人の主軸とする分野から少し離れるにも関わらずメンターとしてのサポートは最小限で済み、さすがと思わせられました。

ニューラルネットワークによる3D形状の表現は近年急速にホットになりつつあるトピックですが [8, 9, 10]、そのレンダリングと深層学習との接続に関してはほとんど前例がない状況です。その中で、素直なアルゴリズムによって、複雑な学習 [4] を用いずともボクセルによる先行例 [3] と同等程度の性能が出せるという発見は大きな意味があると考えています。一方で、インターンは一ヶ月と少しという短い期間であったため細部の調整は十分ではなく、数値性能の向上や色の扱いなどまだまだ発展の余地があり、もっと長期間取り組めばさらに面白いものが見られたのでは、という無念さも残るインターンでした。

サンプル点制限と再起動戦略に基づくベイズ最適化の計算量削減

Takeru Ohta

2019-10-24 10:30:35

本記事は、2019年インターンシップとして勤務した武田惇史さんによる寄稿です。

 

こんにちは。2019年PFN夏季インターンシップに参加した東京大学の武田惇史です。インターンでは、Optunaチームのもと、「効率の良いブラックボックス最適化手法の開発」というテーマに取り組みました。

概要

ブラックボックス最適化のアルゴリズムの一つに、ガウス過程に基づくベイズ最適化(GP-BO)があります。GP-BOは、局所解に陥りにくく、少ない探索回数で良い解を得ることができる手法として知られていますが、ナイーブな方法だと探索回数が増えたときに計算が非常に重くなってしまいます。

インターンでは、数万回の探索回数を想定した問題に対しGP-BOを適用するため、高速に動作するベイズ最適化手法を提案し、あるベンチマークテストに対して、過去のコンペティションで優勝したBIPOP-CMA-ESという手法より良い性能を出すことに成功しました。

はじめに

インターンでは、Optunaチームで「効率の良いブラックボックス最適化手法の開発」というテーマに取り組みました。

Optunaとは

Optunaは、PFNが開発しオープンソースとして公開しているハイパーパラメータ自動最適化フレームワークです。

ディープラーニングを例にとると、学習係数、バッチサイズ、中間層の数等、様々なハイパーパラメータが存在し、重み学習後のモデルの性能はハイパーパラメータによって異なります。この性能を最大化するハイパーパラメータを探索するのがハイパーパラメータ最適化であり、これを自動化するのがOptunaです。

ブラックボックス最適化(BBO)とは

ハイパーパラメータ最適化は、ブラックボックス最適化という問題として定式化されます。ブラックボックス関数とは、具体的な入力値に対する出力を見ることでしか情報を得られないような関数であり、これを最大化(最小化)するのがブラックボックス最適化(BBO)です。

image

図:ブラックボックス関数f。入力と出力は見えるが、出力が得られる過程は不明

ベイズ最適化

BBOの手法として近年注目されているのがベイズ最適化です。ベイズ最適化では、評価済みの関数値から未知の入力に対する予測値(の確率分布)を算出し、それに基づいて次に評価する点を決定します。この確率分布は、ベイズ推定における予測分布に対応します。任意の入力に対する出力値の予測分布を求めるため、関数の予測分布を求めていると言うことができます。この関数の予測分布を求めるのに、ベイズ最適化ではガウス過程回帰が一般に用いられます。

ガウス過程回帰は、任意のN点の出力値の同時分布がガウス分布であり、それらのうちのどの2点の入力に対応する出力値の共分散も、その2点の入力値の関数(カーネル関数と呼ばれる)として表されるという仮定に基づいて、未知の入力に対する出力の予測分布をガウス分布として求めます。近い入力同士ほどそれらの出力の相関が強いことを表すようなカーネル関数を用いることで関数の滑らかさに関する制約をソフトに(確率的に)表現することができます。

ガウス過程回帰で正確に関数値を予測するには、カーネル関数をどう設計するかが重要になります。ブラックボックス関数に対しては、関数に対する事前知識がないので、パラメタライズされたカーネル関数を用い、そのパラメータを学習することで対応します。学習においては、周辺尤度最大化や交差検証などを基準に最適化問題として定式化し、ニュートン法やMCMCなどのアルゴリズムが用いられます。

image

図:1次元上のベイズ最適化の動作例[1]

インターン課題

GP-BOは局所解に陥りにくく、少ない探索回数で良い解を得ることができる手法として知られています。しかし、適切にカーネル関数が設定されていないと入力変数間のスケールの違いに対応できず、非効率な探索となります。その一方で、適切なカーネル関数を推定させるためには多くの計算時間が必要となります。

もし適用対象がディープラーニングのハイパーパラメータ最適化であれば、一回の関数評価は一回の学習に相当し、関数評価に時間がかかるため、関数評価の回数はせいぜい数十回から数百回であり、計算が重いというデメリットは問題になりません。しかし、Optunaのユースケースには関数評価に時間がかからず、数万回探索可能な問題設定もあります。このような場合にGP-BOを適用すると、GP-BO自体がボトルネックとなり、現実的な時間では計算を終えることができません。

そこで、探索範囲を優秀なサンプルに限定することで数万回の探索が可能であるような最適化手法を考案しました。

GP-BOの課題

GP-BOでは、探索回数を\(N\)としたとき、ガウス過程における学習・推論時に必要なN×N行列の逆行列の計算を\(N\)ステップ行います。この際、Sherman-Morrisonの公式により、逆行列を1ステップ\(O(N^2)\)の計算量で求めることができ、全体で\(O(N^3)\)かかってしまいます。そのうえ、性能を出すためにはカーネル関数やパラメータを学習する必要があり、カーネル関数のパラメータが変わると逆行列を求める行列全体の値が変わるためSherman-Morrisonの公式が使えず、逆行列の差分計算を効率的にすることが難しくなるため、計算量は\(O(N^4)\)となります。

性能を出すために重要なパラメータが変数のスケールに関するパラメータです。もし関数の入力変数間のスケールが大きく異なる場合、カーネル関数として通常のユークリッド距離のみに依存するものを選んでいたとすると、本来影響の少ない方向からの影響を大きく見積もり、関数の予測が上手く動きません。変数間の相関やスケールの違いに対応するには、カーネル関数に多くのパラメータを設定し、それをメタレベルの最適化問題を解くことによって調整する必要があります。場所によってスケールが異なる性質(悪スケール性)を持つ関数に対しては、より複雑なカーネル関数のパラメータを適切に学習する必要が生じ、さらに計算量が増えます。

提案手法

Limited-GP

提案手法ではこの点を解決するため、ガウス過程で参照するサンプル点を制限します。

まず、これまで探索した点から上位\(K\)点に対する平均ベクトルと共分散行列を求めます。求めた平均ベクトルと共分散行列が定める各点へのマハラノビス距離を計算します。距離が小さい方から\(K\)番目の点を通る(マハラノビス距離での)超球の内部に限って獲得関数が最も良くなる値の探索を行い、次の探索点を決めます。獲得関数は、距離が小さい方から\(2K\)個の点のみを参照したときのガウス過程回帰の結果に基づいて計算されます。カーネル関数としては2点間のマハラノビス距離が遠いほど値が指数的に小さくなるようなものを選びます。遠くの点の影響が小さいので、参照点を近い方から\(2K\)個に限れば十分となります。

image

図:マハラノビス距離を原点からのユークリッド距離に対応させる線形変換。黄色い点はK=5としたとき関数値の評価が最も良かったK点を表す。変換後、図に収まらない点は省略している。

image

図:ガウス過程において参照する点の範囲(外側の円)とサンプルを得る範囲(内側の円)

上位\(K\)点に対する平均ベクトルと共分散行列に基づくマハラノビス距離における円は、それまでに見つかった最適値付近における関数の等高線を楕円形に近似したものと考えられます。すなわち、このマハラノビス距離が通常のユークリッド距離になるように空間を変換すると、等高線は正円に近くなると考えられます。このため、関数は等方性(方向によって性質が変化しない性質)を得ることができ、ガウス過程のカーネルパラメータを用いたスケールの調整が不要になります。

これまでに探索した点の数が一定値を超えた場合、新たに探索点が増えるたびに対応する関数値が最も悪い点の情報を捨てます(これにより性能が落ちないことは実験的に確かめています)。こうすることで、参照点全体の個数が定数個で抑えられ、1ステップの計算量は\(O(1)\)となり、Nステップでは\(O(N)\)となりますので、ナイーブなGP-BOにおける\(O(N^4)\)と比べ、大きく改善します。

再スタート戦略

Limited-GPで制限される探索範囲は、実験上多くの場合でだんだんと狭まっていきます。そのため、多峰な関数では一度局所解に陥るとそこから抜け出すことは困難です。

そこで、本手法ではLimited-GPを繰り返し行うことで大域的な最適解の発見を試みます。この際、Limited-GPへの初期値として与えられる平均ベクトルと共分散行列をCMA-ES[2]というアルゴリズムのrank-μ-updateを参考にした方法で適応させます。具体的には、毎ステップ、それまでにLimited-GPが発見した解のうち特に良かった点に対する共分散行列を求め、その移動平均を用いて次のLimited-GPへの初期値を決定します。CMA-ESベースの方法によって、平均ベクトルと共分散行列は関数の細かいノイズを無視したときの大域的な構造を学習します。

動作の様子

以下に50回の探索点をプロットを載せます。数字は探索順を示します。また、明るいところほど良い解であることを示しています。

徐々に探索位置が最適解へと近づき、50ステップのうちに最適解へ収束していることが分かると思います。

続いて、入力変数間に相関があるような関数に対する探索範囲の変遷について見ます。

image

10ステップの図を示しています。この図では青い線が探索領域を表し、黒い点がガウス過程で参照される点を示し、赤い点が新たにサンプルされた点を表します。探索範囲が等高線に添うように変形しつつ、最適解へと収束していることが分かります。

次に、多峰関数(Rastrigin関数)に対して、再スタートの度に最適解へ収束しやすくなっていることを確認します。

image
10ステップおきの図を取っています。×印が最適解を示します。また、青い線がLimited-GPの初期値として入力される平均ベクトルと共分散行列が規定するマハラノビス距離上の半径1の円を示し、赤い点が直近10回のLimited-GPが発見した最良点を示しています。青い線は最適解へ収束していき、Limited-GPの到達点も最適値付近へ収束していることが分かります。

ベンチマーク

データセット

COCOCOmparing Continuous Optimisers)と呼ばれるベンチマークを使ってテストをしました。COCOは2009年より使われているブラックボックス最適化用のベンチマークで、次元数を自由に変更できるような関数を24種類、360個提供しています。毎年コンペティションが開かれており、多くの手法が試されています。

image

図:COCOが提供する関数群の一部

 

実験設定

手法のハイパーパラメータについては、\(K=7+3logD\)(\(D\)は目的関数の入力次元数)と定め、カーネル関数はガウスカーネル、獲得関数はLCBに固定します。

関数の次元数\(D\)は\(D=2\)と\(D=3\)でそれぞれ実験しました。探索回数は\(10^4×D\)としました。

結果

image

図:ベンチマーク結果

結果が上図になります。左は2次元、右は3次元での結果で、横軸がlog(探索回数/次元数)を表し、縦軸がすべての関数に対する平均精度を表します(※正確には、このグラフはempirical cumulative distribution function [3]と呼ばれるものです)。グラフ上の×印は探索の終了点を表し、それより後の部分は、結果描画時に補完された値となります(詳細は参考文献を参照して下さい)。

”Limited-GP(proposed)”が提案手法を表しています。”BIPOP-CMA-ES”はBBOにおいて有望視されている手法であるCMA-ESの亜種で、2009年のコンペティションで最も高い性能を出した手法であり、総合的に最も強い手法と言われています[4]。”GP-BO(skopt)”はBBO用pythonライブラリで、GP-BOの実装であるscikit-optimize(skopt)の結果になります。skoptは非常に実行時間がかかるため、探索回数は100×(次元数)回で、一部の関数インスタンスに対してのみベンチをとっており、あくまで参考までに比較として載せています。また、”best 2009”は各関数ごとに2009年のコンペティションで提出された手法のうち最も良い結果が得られたものを選んだ場合の学習曲線を表しています。実際にはブラックボックス関数であるため手法をあらかじめ選ぶということはできず、ある種の性能上界として参考までに載せています。

提案手法はBIPOP-CMA-ESと比べても効率良く探索できるという結果が得られました。

なお、今回はインターン期間が限られているという制約もあり、低次元関数のみに対象を絞って開発・検証を行いました。高次元関数においては、まだBIPOP-CMA-ESの方が良い性能を示すことが確認できており、そこでの最適化性能の向上は今後の課題となります。

まとめ

今回のインターンでは、ガウス過程に基づくベイズ最適化を改良したLimited-GPと再スタート戦略の組み合わせを提案し、過去のベンチマークテストにて高い性能を出すことができました。

本手法の実装はhttps://github.com/pfnet-research/limited-gpで公開されています。

参考文献

[1] Eric Brochu, Vlad M. Cora, and Nando de Freitas. A tutorial on Bayesian optimization of expensive cost functions, with application to active user modeling and hierarchical reinforcement learning. pre-print, 2010. arXiv:1012.2599.

[2] Hansen, N.: The CMA Evolution Strategy: A tutorial. 

[3] N. Hansen, A. Auger, D. Brockhoff, D. Tušar, T. Tušar (2016). COCO: Performance Assessment. ArXiv e-prints, arXiv:1605.03560.

[4] Posìk, P. Huyer, W. & Pal, L. A comparison of global search algorithms for continuous black box optimization. Evol. Comput. 20, 509–541 (2012).

メンターからのコメント 

メンターを担当したPFNの太田と柳瀬です。

昨年12月にOSSとしてリリースしてから、Optunaの応用は広がっており、当初想定していた機械学習のパラメータ最適化だけではなく、ブラックボックス最適化のソルバとしても使われるようになってきました。

そうした状況のもとで、武田さんにはブラックボックス最適化のソルバの調査と改善に取り組んでいただきました。学会発表が重なるなど,必ずしも時間が十分だったわけではありませんが,武田さんは次々とアイデアを出して、限定的な評価環境ではありますが計算が軽くて探索性能の良いソルバの可能性を示してくれました。

Optunaではライブラリの機能開発だけではなく、こうした将来に向けての研究開発も引き続き行っていきます。興味のある学生の皆さんは、ぜひ来年のPFNインターンシップへの応募を検討ください。もちろん、中途・新卒での人材募集も通年で行っていますので、こちらも興味のある方はぜひご検討ください。PFNの人材募集のページはこちらです。

Implicit biasによる正則化効果

Kohei Hayashi

2019-10-23 16:47:09


本記事は,2019年度インターン生だった東京大学 D1 の中島蒼さんによる寄稿です.中島さんはインターンシップにおいて,畳み込みニューラルネットワークの学習について研究を行いました.この記事は,インターンシップ中に文献調査していたimplicit bias に関するレビューとなっています.


NN の学習はなぜうまくいくのか

畳み込みニューラルネットワーク(Convolutional NN; CNN)は画像処理など様々な分野に応用され,大きな成功を納めています.すなわち,様々なデータについて,訓練データから学習したニューラルネットワーク(Neural Network; NN)を用いて未知のデータについての予測や分類が行われています.このようにNN の学習が上手くいく,すなわち未知データに良く汎化することは経験的には分かっていますが,理論的な説明はまだ完全には成功していません.

NN に限らず学習一般において,訓練データだけから未知なデータについて予測をするのは本来原理的に不可能です.未知のデータに対しては,何が起こってもおかしくないからです.それにも関わらず学習が上手くいくのは,未知のデータに関しても何らかの仮定ができ(帰納バイアス; inductive bias),その仮定を利用することで既知のデータから帰納的に推論が行えるためです.例えば,「データの生成過程は単純であり,学習されたモデルが単純なら未知のデータについても予測できる」と仮定し,過学習を抑制し単純なモデルが学習されるようにする正則化が良く行われてきました.NN の学習が上手くいく背景にも,このような正則化が働いていると考えられます.

しかしながら,現実に使われている NN はパラメタ数がデータより非常に多く,一見すると自由度が高すぎて過学習が起きやすいモデルに思えます.それにも関わらず,なぜ NN の学習は上手くいくのでしょうか?実はパラメタ数が多くなっても,学習された NN は過学習を起こしにくいことが実験的に示唆されています.例えば,Neyshabur ら [1] による実験では,NN のパラメタ数が増えても未知のデータに対する予測精度は保たれていて,過学習が防げていることが分かります.Zhang ら [2] による別の実験でも,\(l_2\)-正則化などの明示的な正則化がなくても学習後のNN の性能は良いことが示されています.これらの結果は,パラメタ数が多く明示的に正則化が行われない状況でも,何らかの形で過学習が抑制される正則化がかかっていることを示唆しています.

この暗黙的な正則化(implicit bias)の正体は何なのでしょうか?Neyshabur ら [1] は最適化アルゴリズムの性質によるものだという仮説を提示しました.例えば,確率的勾配降下法 (Stochastic Gradient Descent; SGD) は連続的にパラメタを更新していくアルゴリズムなため,初期値からあまり離れることができません.そのため,初期値が非常に小さい場合は,学習されたパラメタのノルムが小さくなると期待されます(図1).この小ノルム性が正則化として機能し,未知のデータに対する汎化性能に効いているのだというのが彼らの仮説です.Zhang ら [2] も同様に SGD に起因する小ノルム性に基づいた議論を行っています.

図1:SGD に起因する implicit bias.パラメタ \(\boldsymbol{\theta} = (\theta_i)_{i=1,2,\dots,}\) の数がデータより多い場合,大域的最適解(訓練誤差がゼロになる点)は典型的には複数あり,連続的に存在していることもあります.ゼロに近い初期値からSGD で最適化する場合,このように複数ある大域的最適解のうちで,ノルムが小さいものが得られることが期待できます.特に,行列補完という問題では,ノルムが最小な大域的最適解に到達するといくつかの状況で示されています.

Neyshabur ら [1] の議論は,行列補完という問題で,小ノルム性が良い解につながるという既存の知見に着想を得ています.行列補完は,行列 \(X \in \mathbb{R}^{n \times n}\) の成分の線形和がいくつか分かっているときに,すべての成分を求める問題です.具体的には,行列 \(A^{(\lambda)} \in \mathbb{R}^{n \times n}\) \(\lambda = 1,2,\dots, m\) と線形和 \(o^{(\lambda)} := \sum_{i,j = 1}^n A_{i,j}^{(\lambda)} X_{i,j} \) が与えられたとき,行列 \(X\) を推定する問題になります.行列補完は,線形 NN による回帰を具体例として含んでいて,NN の学習を単純化した問題とも捉えられます.線形和の個数 \(m\) が \(X\) の要素数 \(n^2\) より少ない場合,線形和の条件を満たす \(X\) は複数存在するため,元々の \(X\) を決定することは原理的には不可能です.しかし,\(X\) が低ランクであると分かっている場合には,トレースノルムを最小にする手法が上手くいくことが知られています.すなわち,線形和に関する条件を満たす \(X\) のうちで,トレースノルムを最小にするものを求めることで,元々の \(X\) を良く復元できることが知られています [3].ここで,行列 \(X\) のトレースノルムは,\(X\) の特異値が \(\{\sigma_i\}_{i=1,2,\dots,n}\) であるとき,以下の式で定義されます.

\[ \|X\|_{\mathrm{trace}} = \sum_{i=1}^n \sigma_i\].

Implicit bias は存在するのか

では,最適化手法に起因してパラメタのノルムが小さくなるという implicit bias は本当に起こっているのでしょうか?いくつかのモデルについては,implicit bias があることが理論・実験的に検証されています.例えば,先述した行列補完 [4,5,6] や,巡回畳み込みを行う線形 CNN [7] で証明されています.この記事では,行列補完に関する implicit bias について紹介します.

行列補完

先述した行列補完については,implicit bias の存在が理論的に証明されています.すなわち,明示的にトレースノルムを最小にする正則化を行わなくても,初期値が十分小さいなら勾配法の結果としてトレースノルム最小解が得られると,いくつかの状況で示されています.ここで,勾配法では,線形和についての二乗誤差

\[ \sum_{\lambda = 1}^m \left \| o^{\lambda} – \sum_{i,j=1}^n A_{i,j}^{(\lambda)} X_{i,j} \right\|_2^2 \]

を最小化します.また,最適化するパラメタとしては,\(X = U^\top U\) と分解された \(U\) を用います.この設定の下,Gunasekar ら [4] は,線形和を決めている行列 \(A^{(\lambda)}\) たちが可換であるときにimplicit bias の存在を証明しています.また,Li ら [5] は,線形和についてある種の等方性を仮定することで,implicit bias を示しています.一方で,Arora ら [6] は,より多層な分解 \(X = U_1 U_2 \dots U_n\) についての implicit bias を [4] と同じ設定の下で示しています.また,一般にはトレースノルムではなくeffective rank [8] という量が小さくなる正則化が起こっているのではないかと実験的に議論しています.行列補完は線形 NN による回帰を含んでいたので,これらの結果は線形 NN で回帰をする場合には implicit bias が存在することを意味しています.

まとめ

この記事では,パラメタ数が多く一見すると過学習が置きそうに思える NN であっても,学習アルゴリズムによる implicit bias のため過学習が抑制され,良い汎化性能につながっているという仮説を紹介しました.Implicit bias の存在は,限定的な状況ではありますが,いくつかの例では理論的に証明されていました.現実的な状況では,常にノルムの最小化が行われるわけではなく,アルゴリズムに起因する小ノルム性と勾配の関係で学習されるパラメタが決定されていると考えられますが,このような状況での実験・理論の両面での解析は未だに発展の余地があるものになっています.また,NN の学習を説明する試みは, Neural Tangent Kernel [9] のように他にも存在しています.

最後に,NN の学習という挑戦的で面白い課題に取り組む機会を与えてくださった PFN やサポートしてくださった皆さんにこの場を借りて謝意を表します.特に,メンターの林浩平さんと南賢太郎さんには,日々の議論など様々な面でご支援いただきました.本当にありがとうございました.

参考文献

[1] Behnam Neyshabur, Ryota Tomioka, Nathan Srebro: In Search of the Real Inductive Bias: On the Role of Implicit Regularization in Deep Learning. ICLR (Workshop) 2015.

[2] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, Oriol Vinyals: Understanding deep learning requires rethinking generalization. ICLR 2017.

[3] Emmanuel J. Candès, Benjamin Recht: Exact matrix completion via convex optimization. Commun. ACM 55(6): 111-119 2012.

[4] Suriya Gunasekar, Blake E. Woodworth, Srinadh Bhojanapalli, Behnam Neyshabur, Nati Srebro: Implicit Regularization in Matrix Factorization. NIPS 2017: 6151-6159.

[5] Yuanzhi Li, Tengyu Ma, Hongyang Zhang: Algorithmic Regularization in Over-parameterized Matrix Sensing and Neural Networks with Quadratic Activations. COLT 2018: 2-47

[6] Sanjeev Arora, Nadav Cohen, Wei Hu, Yuping Luo: Implicit Regularization in Deep Matrix Factorization. NIPS 2019, to appear.

[7] Suriya Gunasekar, Jason D. Lee, Daniel Soudry, Nati Srebro: Implicit Bias of Gradient Descent on Linear Convolutional Networks. NeurIPS 2018: 9482-9491.

[8] Olivier Roy and Martin Vetterli. The effective rank: A measure of effective dimensionality. In15th European Signal Processing Conference, IEEE: 606–610. 2007.

[9] Arthur Jacot, Clément Hongler, Franck Gabriel: Neural Tangent Kernel: Convergence and Generalization in Neural Networks. NeurIPS 2018: 8580-8589.


総評

今回のインターンシップでは,中島さんには「最適化由来の正則化効果」という機械学習の中でも比較的新しいトピックに取り組んでいただきました.本記事で紹介されている implicit bias は理論研究としての側面が強く,正則化効果が発生することは限られた条件下では理論的に証明されているものの,現段階では工学的応用には結びついていません.しかしながら,implicit bias は最適化によって自動的に生じるため,追加の計算量を必要としない「経済的な」手法であるといえます.また,ニューラルネットワークがどのようにしてその強力な汎化能力を得ているのか,その原理の解明につながる一歩としても興味深い存在です.

PFNインターンでは,このような理論的トピックにも果敢に挑戦できる環境を提供しています.同様の興味を持つ学生の方はぜひ次の機会にご応募ください.

リサーチャー 林浩平,リサーチャー 南賢太郎

少数の教師データと弱い教師データを用いた物体検出

Niitani Yusuke

2019-10-17 15:10:03

本記事は、2019年夏のインターンシップに参加された本間喜明さんによる寄稿です。

 

はじめに

PFN2019夏期インターンに参加した慶應義塾大学 理工学研究科 M1 本間喜明です.大学では斎藤英雄研究室に所属しており,普段はコンピュータビジョンの研究をしています.今回のインターンではFew-Shot Object DetectionをWeb画像を使うことで拡張した Few-Shot + Web Object Detectionという新たなタスクに取り組みました.

 

背景

一般に物体検出で用いられている多層のCNNの学習には大量の教師データが必要となります.

この問題を解決するために,非常に少ない教師データのみを使って新たなクラスの物体を検出するFew-Shot Object Detectionの手法[1, 2]が提案されています.しかし,教師データの数が少ない場合にはデータに偏りが生じやすく,偏ったデータから検出対象クラスの物体の特徴を学習することは困難です.また,サンプル数が少なすぎると与えられたクラスラベルの表すべき概念のサブセットを検出器が学習してしまうリスクがあるという問題があります.例えば犬を新たに検出するために,ある特定の犬種が写った画像を教師データとして与えたとします.このとき,人は”犬”というクラスのサンプルとして特定の犬種についての画像を与えているつもりでも,物体検出器からはクラスラベルという整数値が与えられただけで,与えられたクラスラベルが”犬”に対応しているのか,それともある特定の犬種に対応しているのかを判断できません.そのため,このままでは他の犬種のデータが与えられたときに検出すべきか否かという問題を解くことはできません.

そこで,少量の教師データに加えて,Web検索により取得した画像(Web画像)を学習データに用いることで上記の問題を解決することができないかと考えました.通常,ユーザが新たに追加したいクラスはその名前が既知であるため,Web検索をすることで追加クラスの物体が写った大量の画像を容易に取得することができます.

しかし,Web画像を物体検出に学習データに用いる場合には2つの問題があります.1つ目はWeb検索をした場合,必ずしも正しいクラス情報が得られるとは限らないことです.2つ目はWeb検索で得られるのは画像だけで,物体の画像内での位置に関する情報は得られないことです.

実際にWeb画像を用いる場合には両方の問題を解決しなければなりません.しかし,インターンという限られた期間で2つの問題に取り組むことは難しいと考え,今回はWeb画像の代わりに ImageNet[3]の画像を用いることにしました. ImageNetではWebから収集された画像についてカテゴリラベルが人手で付与・検証されており、1つ目のクラス情報が間違う問題が原則起きない設定で実験することができます.これにより,2つ目の物体の位置に関する情報が得られないという問題に集中して取り組むことにしました.

 

問題設定

まずはFew-Shot Object Detectionの問題設定について説明します.Few-Shot Object Detectionでは3種類のデータセットがあります.

1つ目のTrain-setは大量の既知クラスの物体についてデータで構成されています.2つ目のSupport-setは新たに学習させたいクラス(未知クラス)のデータで構成されていますが,少量のデータしかありません.3つ目のQuery-setは未知クラスのいずれかが写った画像で構成された評価対象のデータセットです.Few-Shot Object DetectionではTrain-setとSupport-setの2つを使ってモデルを学習させ,Query-setを使って評価します.このときに未知クラスの数がn個,各クラスに与えられる教師データの数がk個の場合は,n-way k-shot検出と呼ばれます.また,Few-Shot Object Detectionでは未知クラスとそのデータのサンプリングから学習・評価までの一連の過程をエピソードと呼び,いくつものエピソードを繰り返して評価します.

今回のインターンで取り組んだFew-Shot + Web Object Detectionでは上記の3つのデータセットに加えてWeb画像とそのクラスラベルで構成されたデータセットであるWeb-setを新たに追加します.このタスクでは物体のクラスラベルと位置情報の両方が付与された少量の教師データと物体のクラスラベルのみが付与された大量のWeb画像をどのように組み合わせてネットワークを学習させるかが重要になります.

 

提案手法

 

提案手法の流れを上図に示します.Web画像には画像単位のラベル付けしかされておらず,物体の位置情報については一切与えられません.そこで提案手法では位置情報を補うために,事前に学習させたResion Proposal Network (RPN)と異なるクラスの物体を取り除くLabel Cleaning Networkを用います.

RPNはFaster R-CNN[4]などで用いられるネットワークで,物体の大まかな位置を表すRegion of Interest (RoI)とその信頼度を表すスコアを出力します.提案手法ではスコアが高いRoIを付与されたクラスラベルの物体のRoI,スコアが低いRoIを背景のRoIとします.

しかし,実際の画像には与えられた未知クラスとは異なるクラスの物体が写っていることが多々あり,上記の方法だけでは異なるクラスの物体に対して誤ったクラスラベルを付与してしまいます.

そこで提案手法では,事前に学習をさせておいた2つの分類器から成るLabel Cleaning Networkを用います.1つ目はTrain-setで学習を行った分類器(既知クラス分類器),2つ目はSupport-setで学習を行った分類器(未知クラス分類器)です.

 

既知クラス分類器は物体のRoIから既知クラス物体のRoIを取り除くのに使われ,未知クラス分類器は物体のRoIから特定の未知クラス物体のRoIのみを残し,それ以外のRoIを取り除くのに使われます.

 

実験

提案手法の有効性を検証するためにMS COCO[5]とImageNetを使って,1. 少量のCOCOのデータのみを使った場合,2. 少量のCOCOとImageNetのデータを使った場合についての比較実験を行いました.

Web画像として追加されるImageNetの画像には各クラスにつき,最大1000枚の画像をサンプリングしたものを使いました.このとき,WordNet[6]を使い,COCOの各クラス名の同義語と下位語を取得し,それらとImageNetのクラス名のマッチングを行うことでCOCOのクラスとImageNetのクラスを対応させました.

COCOの全80クラスのうち60クラスを既知クラス,20クラスを未知クラスとしました.Train-setにはCOCOの学習用データセットから未知クラスのアノテーションを削除したものを使いました.Support-setとQuery-setにはCOCOの評価データセットから各クラス5つずつサンプリングしたものを使いました.また各エピソードでは未知クラスの中から5つをランダムにサンプリングし,エピソードの数は50としました.

今回の実験では上記の2つに加え,位置情報が与えられたImageNet Localization Datasetを使って学習させた場合についても評価しました.これにより,もし位置情報が正しく得られる場合には,ImageNetを追加することでどれほど精度向上可能なのかという上界を擬似的に測れると考えました.

評価にはクラスごとのAverage Precision (AP)と,各クラスのAPの平均値であるmAPを用いました.推定した検出領域と正解データの検出領域の重なり度合いを表すIoUが0.5以上,かつ,推定した物体のクラスが正しいときに正しく検出できたとみなしました.

 

結果と考察

実験結果は下表のようになりました.

mAPについては少量のCOCOのデータのみを使った場合が最も良い結果となった一方で,提案手法によりいくつかのクラスではAPが向上しました.また位置情報が与えられていない画像を使う場合にはLabel Cleaningを行うことでmAPが向上したことを確認しました.

ImageNetを使うことでmAPが向上しなかった原因として,1. Label Cleaningがうまくできていないこと,2. COCOのクラスとImageNetのクラスで対応関係が取れていないことなどが挙げられます.

ImageNet Localization Datasetを使ったときにAPが向上したにも関わらず,提案手法ではAPが向上しなかったクラスはLabel Cleaningがうまく機能していないため,APが向上しなかったと考えられます.Label Cleaningが機能していない原因の1つに,Support-setのみを使ってLabel Cleaning Networkを学習させたことが挙げられます.背景で説明をしたように,少量の学習データだけを使って学習をさせた場合にはクラスラベルの表す概念を誤って学習してしまう場合があります.クラスラベルの表す概念を誤って学習してしまった場合には,誤って学習したクラスの概念をもとにLabel Cleaningが行われてしまい,正しくLabel Cleaningを行うことができません.そのため物体検出器の学習だけでなく,Label Cleaning Networkの学習においてもWeb-setを活用し,クラスラベルが表す概念を誤って学習させないようにする工夫が必要なのではないかと考えています.

また,いくつかのクラスではCOCOとImageNetのクラスの対応付けをうまく行うことができていませんでした例えば,COCOのBirdクラスは様々な種類の鳥を表しているのに対し,ImageNetのBirdクラスではhenという特定の種類の鳥のみを表してしまっており,それ以外の種類の鳥は含まれていませんでした.正しくクラスの対応付けができているクラスの中から未知クラスを選ぶことで,誤ってクラスが対応付けられるのを防ぐことができるため,改めてクラスを分け直し,実験することでより正確に提案手法の有効性を検証できるのではないかと考えています.

ランダムに選んだ20クラスではなく上記のような根本的なエラーのないようなクラス集合での評価をした上で、Label Cleaningの手法を改善していくことが課題となりそうです.

 

まとめ・感想

今回のインターンではWeb画像を使うことでFew-Shot Object Detectionを拡張したタスクに取り組みました.事前に学習を行ったRPNと,2つの分類器からなるLabel Cleaning Networkを使うことでWeb画像に位置情報についての擬似的なアノテーションを与える手法を提案しました.クラスラベルの不一致などの影響もあり,残念ながらmAPを向上させることはできなかった一方で,いくつかのクラスではAPを向上させることができました.

約2ヶ月間という限られた期間ではありましたが,社員の方のサポートのおかげで非常に充実したインターン生活を送ることできました.特に,メンターの二井谷さん,小林さんには毎日ミーティングをして頂くなど,多大なサポートをして頂きました.本当にありがとうございました.大学の研究室に戻ってもPFNで学んだことを忘れずに,精一杯頑張っていきたいと思います.

 

参考文献

[1] Leonid Karlinsky, Joseph Shtok, Sivan Harary, Eli Schwartz, Amit Aides, Rogerio Feris, Raja Giryes, and Alex M Bronstein. RepMet: Representative-based metric learning for classification and few-shot object detection. In CVPR, 2019.

[2]Hao Chen, Yali Wang, Guoyou Wang, and Yu Qiao. LSTD: A Low-Shot Transfer Detector for Object Detection. In AAAI, 2018.

[3]  J. Deng, W. Dong, R. Socher, L.-J. Li, K. Li, and L. FeiFei. ImageNet: A large-scale hierarchical image database. In CVPR, 2009.

[4]  S. Ren, K. He, R. Girshick, and J. Sun. Faster R-CNN: Towards real-time object detection with region proposal networks. In NIPS, 2015. 

[5]  T.-Y. Lin, M. Maire, S. Belongie, J. Hays, P. Perona, D. Ramanan, P. Dollar, and C. L. Zitnick. Microsoft COCO: Common objects in context. In ECCV, 2014.

[6] Miller GA. Wordnet: a lexical database for english. In ACM, 1995.

時間方向に集約されたデータを用いた時系列予測

Masashi Yoshikawa

2019-10-11 13:26:38

本記事は、2019年夏のインターンシップに参加された太田真人さんによる寄稿です。

 

こんにちは、2019年夏のインターン生だった関西学院大学大学院M1の太田です。大学では、ベイズモデリングの応用で研究しています。インターンでおこなった業務について紹介します。

 

概要

 

私は、時系列予測に取り組みました。実問題では、データを細かい時間スケールで長期間保存できず、過去のデータから秒を分スケールに集約して保存することがあります。

他にも、数年前までは、1ヶ月や1日単位で来場者数(売り上げ)をカウントしていましたが、最近は、高い時間分解能(日にち、時間単位)で予測したい需要が高まり、細かくデータを取り始めることもあると考えます。

その場合、データを集めたばかりの頃は、時系列長が短く予測が難しいことがあります。そこで、集約されていない時系列データは直近の短い期間しかないが、集約された時系列データは長期間あるという問題設定を考え、本研究に取り組みました。毎分計測されるデータを例に出すと、集約されていない時系列データとは1分単位のデータ1つ1つを、集約された時系列データとは1時間ごとの合計等を表します。

ここで、本研究で扱う時系列データを図1に示します。青色が観測値で白色は未観測値になります。タスクは、これらの時系列データが与えられたもとで、集約されていない時系列の予測になります。

 

図1. 本研究で扱う時系列データ

提案アプローチにより、直近の短期間の時系列データから、高い精度で予測ができるような手法を検討しました。つまり、集約されていないデータが貯まるまで数年や数十ヶ月待つ必要が無く、なるべく早い段階で予測が行えるようになります。

 

アプローチ

素朴なアプローチとしては、短期間の時系列データだけで予測モデルを作ることですが、トレンドが捉えられず、予測が難しいです。

そこで、時間方向に集約された時系列データを分解(Disaggregation)することが考えられます。その素朴なアプローチは、直近の集約されていない時系列データから分解の割合の平均を計算して、過去の集約された時系列データに適応することです。

これは直近の集約されていない時系列データが少ない場合、データによっては分解が不適切になることがあります。例えば、数週間分のデータから1週間で金曜日が一番売り上げが良いとわかると、このアプローチだと過去の集約されたデータを分解するときに、金曜に多く売り上げが割り振られてしまいます。本当は、夏季休暇と通常時で売り上げの量が変わるなど、違う場合は多くあると思います。1週間や2週間分のデータで過去の全てに適応するのは不適切です。

提案アプローチはこれらを解決する方法を作りました。まず、提案アプローチを図2を用いて簡単に説明すると、上段の集約された時系列データを分解しつつ、下段の分解された赤色の推定値と青色の集約されていない時系列データを合わせて、時系列モデルを学習し、未来の集約されていない時系列データを予測する確率モデルです。

図2. 提案アプローチの概略

詳しく説明していくと、集約された時系列データは、図2の上段のように\({C}_{\tilde t}\ ({\tilde t}=1,\dots,{\tilde T})\)と集約されていない時系列データは下段のように \({x}_{t}\ (t=1,…,T)\)と表します。このとき、集約されていない時系列データは\(x_{t_H}\)まで未観測のデータになります。この集約された時系列データとされていない時系列データの関係は,時間方向の合計\(C_{\tilde t}= \frac{1}{K}\sum_{i =1}^K x_{i+({\tilde t}-1)K}\)によって求まります。ここで、集約された方の時系列長は\({\tilde T}=T/K\)と表せ、\(K\)は自分で決定するパラメータになります。例えば、1日のデータを24時間に分解したければ、\(K=24\)になります。

集約された時系列データの分解比率は, \({\rho} = {\rho}_1,…,{\rho}_K\)とあらわし、この分解比率は時間に依存しない確率変数として扱い、ディリクレ分布 \({\mathrm Dir}({\alpha})\)に従うと仮定します。ディリクレ分布を用いることで、分解した後のデータの総和がまた集約されたデータに戻ることを保証します。

尤度関数は \(\prod_{t}{\mathcal N}({x}_t|f_{\theta}( {x}_{<t}),{\sigma}^2)\)とします。 \(f_{\theta}( {x}_{<t})\) は,時系列モデルであり,本研究では,AR(Auto Regressive)モデルとFacebookが開発したProphet[1]を使用しました。\({\theta}\)は時系列モデルのパラメータになります。

同時分布は、\(p(x_{\le T},{\mathbf \rho}|C_{\le \tilde{T}}) = p(x_{\le T}|{\mathbf \rho}, C_{\le \tilde {T}}) p_{\alpha}({\mathbf \rho})\)となります。ここで、\(p_{\alpha}({\mathbf \rho})\)のディリクレ分布のパラメータは、完全に一様分布にするのではなく、直近の集約されていない時系列データから求まる分解比率をほどよく生成するような値にします。(一様分布にすると、分解比率の事前の信念として、全て均等に分解されることを表します。)

では、そのようなパラメータ値を求めるために、次の同時分布\(p(x_{t_H:T},{\mathbf \rho}|C_{{\tilde t_{H}}:{\tilde T}})=p(x_{t_H:T},{\mathbf \rho}|C_{{\tilde t_{H}}:{\tilde T}})p({\mathbf \rho})\)について説明します。この分布は、直近の集約されていない時系列データと分解比率の同時分布です。尤度関数にあたる\(p(x_{t_H:T},{\mathbf \rho}|C_{{\tilde t_{H}}:{\tilde T}})\)は、\(\prod_{{\tilde t}={\tilde t}_H}^{\tilde T}{\mathcal N}({\mathbf x}_{\tilde t}|C_{\tilde t}{\mathbf \rho},\sigma^2)\)と表します。ここで、\({\mathbf x}_{\tilde t}=(x_t,…,x_{t+K})^{\rm T}\)となります。また、\({\tilde t_{H}}\)は、集約されていない時系列データが観測され始めた時の集約された時系列データでの時刻です。

事前分布\(p({\mathbf \rho})\)は、ディリクレ分布です。ただし、ここでは、\({\mathbf \alpha}=1\)として、一様分布にしました。この同時分布から事後分布\(p({\mathbf \rho}|x_{t_H:T},C_{{\tilde t_{H}}:{\tilde T}})\)を、変分推論により求めます。近似事後分布には、ディリクレ分布を仮定します。この近似事後分布は、先ほど事前分布に求めていた「直近の集約されていない時系列データから求まる分解比率をほどよく生成する」ことを実現しています。したがって、近似事後分布の変分パラメータ\({\tilde \alpha}\)を先ほどの事前分布\(p_{\alpha}({\mathbf \rho})\)のパラメータとして用います。つまり、事後分布を事前分布として用いることになります。

また、グラフィカルモデルは図のようになります。

図3a. 直近の観測している集約されていない時系列データから事前分布を学習するグラフィカルモデル。

図3b. 時系列予測のグラフィカルモデル。図の左側のプレートが集約されていない時系列データが未観測時刻のグラフィカルモデルを表し、右側のプレートが観測され始めた時刻のそれを表します。θは、ARモデルのときパラメータであり、Prophetのとき確率変数になります。

この後は、時系列モデルのパラメータの学習と近似推論について説明していきます。

モデルパラメータの学習は、周辺尤度の最大化をおこないます。これは、2つのELBO(Evidence Lower BOund)の最大化により達成されます。1つ目は、

 

$$\log p({\bf x}_{t_H:T}|C_{{\tilde t_{H}}:{\tilde T}}) \ge \mathbb{E}_{q_{\tilde \alpha}({ \rho})}[ \sum_{t=t_H}^T \log p_{\theta}( {\bf x}_t | {\mathbf \rho}, C_{\tilde t}) ]-KL(q_{\tilde \alpha}({\mathbf \rho})|p({\mathbf \rho})).$$

 

このELBO最大化により、近似事後分布\(q_{\tilde \alpha}({\mathbf \rho})\)を学習します。

このELBOの1項目は、集約されていない時系列データから、分解の比率\({\rho}\)が尤もらしい値をサンプルするように\({\tilde \alpha}\)を学習する再構成誤差項です。

2項目のKL項が、\({\tilde \alpha}\)が過剰適合しないようにする正則化の役割を果たします。近似事後分布は、ディリクレ分布を仮定しており、\(p({\rho})\)のディリクレ分布(一様分布)に近づくよう変分パラメータ\({\tilde \alpha}\)を学習します。この正則化によって、素朴なアプローチのような過去のデータに対して分解を強く仮定しないため、分解時の規則性がはっきりしないノイズのあるデータに対しても予測がうまくいく可能性があります。ちなみにディリクレ分布のreparameterization trick はFigurnovら[2]が提案しています。

求めた近似事後分布\(q_{\tilde \alpha}({\mathbf \rho})\)を事前分布\(p_{\tilde \alpha}({\mathbf \rho})\)として用いて,次のELBOを最大化します。

 

$$\log p({\bf x}_{ \le T}|C_{\le {\tilde T}}) \ge \mathbb{E}_{q_{\alpha}({\mathbf \rho})}[\sum_{t=1}^T \log p_{\theta}({\bf x}_t|{\bf x}_{<t},{\mathbf \rho},C_{\le {\tilde T}})]-KL(q_{\alpha}({\mathbf \rho})|p_{\tilde \alpha}({\mathbf \rho})).$$

 

このELBOは、時系列モデルの出力を平均とするガウス分布を尤度関数に、事前確率は先ほど求めた近似事後分布をもとに、近似事後分布\(q_{\alpha}({\mathbf \rho})\)を求めながら、時系列モデルのパラメータを学習する段階になります。ARを時系列モデルに使う場合、ARモデルのパラメータは、VAE(Variational AutoEncoder)[3]のdecorderの学習方法に習い、近似事後分布を求めるELBO最大化と同時に学習します。また、Prophetを時系列モデルに用いる場合は、別途モデルパラメータの事前確率を用い、また近似事後分布を仮定し、KL項がさらに増えます。

予測分布は、以下の式で与えられます。

 

$$p(x_{T+1}|x_{\le T},C_{\le {\tilde T}})=\int p_{\theta}(x_{T+1}|x_{\le T, },{\mathbf \rho},C_{\le {\tilde T}})q_{{\alpha}}(\mathbf \rho){\rm d}{\mathbf \rho}.$$

 

ここまでを数式を使わずに説明すると、直近の時間方向に集約されているデータの分解比率を、事前分布に組み込み、過去の集約されたデータから集約されていないデータを推定しつつ、時系列モデルを学習しようというアプローチです。

以後、提案アプローチの時系列モデルにARモデルを用いた場合、TDAR (Temporal Disaggregation AR)と呼び、Prophetを用いた場合、TDProphet (Temporally Disaggregation Prophet)と呼びます。

 

実験

実験は、集約されていない時系列の予測精度の比較と集約さていない時系列データの量がどのくらい少なくても精度が高いのかを実験しました。データセットは、アメリカの複数地区の1時間毎の消費電力を記録したHourly Energy Consumption[4]、毎月の飛行機の乗客数を記録したAir passengers[5]、複数のレストランの毎日の来場者数を記録したRecruit Restaurant Visitor Forecasting[6]です。また、集約の方法は図4のように、毎時は毎日に、毎日は毎週に、毎月は四半期に集約しデータセットを作成しました。

図4a. Hourly Energy Consumptionの1地区のデータを集約した時系列データ。赤枠が学習データに使用します。

図4b. Recruit Restaurant Visitor Forecastingのデータセットの1店舗分のデータを集約した時系列データ

図4c. Air passengersのデータを集約した時系列データ

比較手法は、短い期間の時系列データだけで学習したARモデルと直近の集約されていない時系列データから分解比率の平均を求め、過去の集約されたデータを分解し、分解されたデータを含めて学習したARモデル(MDAR:Mean Disaggregation AR)を使用しました。また時系列モデルにProphetを使用した方は、Recruit Restaurant Visitor Forecasting (RRVF) のデータセットとAir Passengersのデータセットで試しました。

評価指標に関しては、RRVFのデータセットに対する予測にはRMLSEを用いて、他はRMSEで評価しました。予測範囲は、スケールがそれぞれ違いますが、集約されたデータ3点分の分解されたデータです。RRVFのデータなら21日分、Air passengersのデータなら9ヶ月分、Hourly Energy Consumptionデータなら72時間分になります。

表1. 予測精度の比較

表1が実験結果になります。予測精度を比較した結果、提案手法のTDARがRRVFのデータセットとHourly Energy Consumptionのデータセットに対して精度が一番高いです。提案アプローチは、データにノイズが乗りやすく、集約されていないデータが少ない場合に効果がありました。それゆえに、Air Passengers のデータセットでは、提案アプローチはMDARに予測精度が劣りました。このデータセットは、データにノイズが少なく、直近の観測された分解比率から精度高く集約されたデータを分解できてしまうからです。また集約されたデータを活かすことにより、長期的なトレンドを捉えることができます。Air Passengers のデータセットには右上がりのトレンドがあり、直近のデータだけで学習したARモデルの場合、トレンドは捉えられないですが、集約されたデータを活かすことでトレンドは捉えることができます。

TDProphetの精度が高くないと考えられる理由は、それ以外のProphetは、MAP推定でパラメータ推定しているのに対し、提案アプローチはELBOの計算をしているため、近似事後分布のパラメータの初期値に依存し、局所解に落ちて精度が振るわなかったのかもしれません。

実験2:集約されていない時系列データの量に伴う予測精度の比較

RRVFデータセットに対して、集約されたデータは固定し、集約されていないデータがどれだけ少なくても、精度が出るのかを実験しました。図5は、横軸が集約されていないデータを2週間隔で増やし10週分、縦軸に予測精度RMLSEをとりました。

図5. 学習に使用する集約されていない時系列の長さを変えて予測精度の比較

縦軸の値が低いほど精度が高いことを示します。集約されていないデータ量が少ないときに提案手法の赤線が2か月分のデータ量が手に入る段階では、他の手法より精度が高いことがわかりました。

関連研究

本研究と一番関連のある研究は、階層時系列予測 (Hierarchical time series forecasting)[7] になります。それは、各層が異なる時間スケールで集約された時系列データを表し、一番下の層が最も細かい粒度の時系列データになります。そのデータがあたえられたもとで、どの層の予測もおこなう研究です。本研究の集約されていないデータが過去にも多く手に入っていると階層時系列予測と同じ問題設定になります。

データが少ない場合、転移学習が考えられます。時系列データの転移学習[8]は、分類や予測、分解があります。転移学習で行われている時系列分解は、多変量の時系列とそれらを集約した時系列が与えられたもとで、ある変量の時系列予測をおこなう研究です。例えば、各家の家電の消費電力とその家の合計の消費電力が複数の家が与えられたとき、ある家の家電の消費電力を予測しようという応用があります。本研究の分解は時間方向の分解なので、この転移学習で行われている時系列分解とは異なります。

最後に、時系列データではありませんが、空間的に集約されたデータの高解像度化をおこなう研究として[9]があります。この研究は、州ごとに集計されたデータを、共変量データを補助的に使用しつつ、ガウス過程を用いた確率モデルから、空間の高解像度化をしています。さらに、ガウス過程を用いながらも、100万件を超える観測データがあっても計算できるように工夫されています。

 

Future Work

本研究で用いた事前分布は、無情報を意味する一様分布を使用しましたが、ここにデータのドメイン知識を詰め込むことができます。例えば、長期休暇期間とそれ以外の期間でデータの分布が変わるとわかっているなら、その事前の信念を事前分布に組み込む事も考えられます。また、時系列モデルに素朴なARモデルとProphetを用いましたが、場合によってはRNNを用いることもできます。さらに、集約データの分解の比率も今回は時間に対して独立でしたが、時間方向に依存関係のあるようなモデルの拡張も考えられます。

まとめ

本研究では、集約された時系列データは長期間あり、集約されていない時系列データは直近の短期間しか手に入らない状況下で、集約されていない時系列の予測をおこなうタスクに取り組みました。アプローチとして、集約された時系列データを細かい粒度に分解しつつ時系列モデルから予測する確率モデルを構築しました。実際に集約されていないデータが少ないとき、予測精度が高いことを実験的に示しました。

最後に、インターンの中盤にこのテーマに切り替え、残りの短い時間の中で、メンターのお二人の指導があったおかげで最後までやり遂げれました。本当にありがとうございました。

参考文献

[1] Taylor, S. J., & Letham, B. (2018). Forecasting at scale. The American Statistician, 72(1), 37-45.

[2] Figurnov, M., Mohamed, S., & Mnih, A. (2018). Implicit reparameterization gradients. In Advances in Neural Information Processing Systems (pp. 441-452).

[3] Kingma, D. P., & Welling, M. (2013). Auto-encoding variational bayes. arXiv preprint arXiv:1312.6114.

[4] Hourly Energy Consumption https://www.kaggle.com/robikscube/hourly-energy-consumption

[5] Air Passengers https://www.kaggle.com/abhishekmamidi/air-passengers

[6] Recruit Restaurant Visitor Forecasting https://www.kaggle.com/c/recruit-restaurant-visitor-forecasting

[7] Hyndman, R. J., & Athanasopoulos, G. (2018). Forecasting: principles and practice. OTexts.

[8] Laptev, N., Yu, J., & Rajagopal, R. (2018). Applied time series transfer learning.

[9] Law, H. C., Sejdinovic, D., Cameron, E., Lucas, T., Flaxman, S., Battle, K., & Fukumizu, K. (2018). Variational learning on aggregate outputs with Gaussian processes. In Advances in Neural Information Processing Systems (pp. 6081-6091).

Graph Neural Network を用いたグラフの木幅予測

Masahiro Sakai

2019-10-10 12:10:39

本記事は、2019年夏のインターンシップに参加された中野裕太さんによる寄稿です。


皆様はじめまして。2019 年 PFN 夏季インターンシップに参加していた北海道大学の中野裕太です。本ブログでは、私が夏季インターンで取り組んだテーマである、「Graph Neural Network を用いたグラフの木幅予測」について説明します。

要旨

与えられた無向グラフがどれくらい木に近いかを表す値である木幅は、グラフ上の組み合わせ最適化問題に対するアルゴリズムの効率性や解そのものと深く関係しています。しかし、木幅を計算することは NP 困難なため、木幅を計算するには頂点数に対し指数時間かかってしまいます。そこで、今回 Graph Neural Network を用いた 2 つの方法でこの問題にアプローチしました。1 つ目は、よく知られた既存のアルゴリズムと組み合わせ探索木の枝刈りを行い高速化を図り計算する方法です。結果は、多くの場合で枝刈りがうまく働き、関数呼び出し回数が 90% 以上減少しました。2 つ目はグラフ回帰問題として直接木幅を計算する方法で、平均絶対誤差が 0.75 となりました。また、真値との誤差が 5 を超えるような、大きく間違えた例はありませんでした。

はじめに

木幅とは?

グラフ理論において木幅とは、ある無向グラフに対し定義されるグラフ不変量の一つであり、大雑把にいうとグラフがどれくらい木に近いかを表す値です。この値を厳密に定義するためにまず、グラフに対する木分解*1というものを定義します。

ある無向グラフ \(G=(V,E)\) に対する木分解とは、下記の条件を満たす \((X = \{X_i\ |\ i \in I \},\ T = (I,\ F))\) のことをいいます。

  1. \(i \in I\) に対し、\(X_i \subseteq V\) である。
  2. \(V = \bigcup_{i \in I}\ X_i\)
  3. 全ての \(\{v, w\} \in E\) に対し、\(v, w \in X_i\) となる \(i \in I\) が存在する。
  4. 全ての \(v \in V\) に対し、\(\{i \in I\ |\ v \in X_i\}\) で誘導される、\(T\) の部分グラフが木となる。

下図に、グラフと木分解の一例を示します。

また、木分解 \((T = (I,\ F),\ X)\) に対する幅を \(\max_{i \in I} |X_i| – 1\) と定義します。例えば、先程の図における木分解の幅は 2 です。ここで、ある無向グラフ \(G=(V,E)\) に対する木幅 \(tw(G)\) は、\(G\) に対し可能な全ての木分解における幅の値の最小値として定義されます。

例えば、木に対する木幅を考えてみると、\(X_i\) を各辺の端点 2 点とすることで、定義を満たす \(T\) が構成できるため、頂点数 2 以上の木は木幅 1 を持ちます。このように、木幅が 1 に近いほどそのグラフが木に近いこと、つまり木へと分解しやすいということを意味します。また、任意の 3 頂点がサイクルを形成し、最も木から離れている完全グラフは、\(X_1\) に全ての頂点を含める以外に条件を満たす \(T\) を構成できないため、\(|V| – 1\)の木幅を持ちます。

*1 機械学習の分野などでは Junction Tree とも呼ばれます。

木幅は何の役に立つ?

グラフ上における組み合わせ最適化問題は、大きく 2 種類に分けられます。1 つは与えられたグラフのサイズ(辺数や頂点数)に対し多項式時間で解ける問題、もう 1 つは多項式時間で解けるアルゴリズムが \(P \neq NP\) 予想の下で存在が知られていない問題です。前者の例として、最短経路問題や最大流問題、後者の例として、最大独立点集合問題や巡回セールスマン問題があります。

しかし後者の問題のほとんどにおいて、入力として与えられるグラフが木である場合に、グラフのサイズに対する多項式時間で解けるということが知られています。では、木に似ているグラフ、つまり木幅が小さいグラフではどうでしょうか?これは、先程述べた木分解を用いることで、 木幅を固定した際、つまり木幅 \(k\) が定数の場合、グラフのサイズに対し多項式時間で解けることが知られています。これは、アルゴリズム分野における Fixed Parameter Tractability (FPT) と深く関係しています。詳しくは [1] をご参照ください。

また、先程も述べたように木幅はグラフ不変量であるため、他のグラフ不変量との間で、上界や下界の関係が存在します。例えばグラフ彩色数 [2] に関して、木幅 \(k\) を持つグラフは高々 \(k + 1\) の彩色数を持つといった関係があることが知られています。詳しくは、[3] をご参照ください。

このようなことから、木幅を計算することや予測することは、グラフ上の組み合わせ最適化問題に取り組む上で重要なことといえます。

Graph Neural Network とは?

Graph Neural Network (GNN) とは、グラフ構造を扱う新しいニューラルネットワークです。一般的なニューラルネットワークでは、入力として実数ベクトルや行列、テンソルなどを扱っていますが、GNN では下記に示すフレームワークを用いるなどで、グラフ構造を扱うことを可能にしています。GNN が主に扱う問題としては、教師ありのグラフ分類・回帰問題やノード分類・回帰問題があります。GNN に関するサーベイ論文として [4] などがあります。詳細はこちらを参照してください。

GNN にも様々な種類がありますが、今回用いる大きなフレームワークとして [6] で提案されているものを用います。これは、各ノードに特徴ベクトルが与えられており、それらを一定回数更新していくことで、ノードに対する特徴表現を獲得し、グラフ全体における全てのノード特徴表現を集約することで、グラフに対する特徴表現を獲得するという仕組みになっています。

入力として、無向グラフ \(G=(V, E)\) が与えられ、各頂点 \(v \in G\) に対し特徴ベクトル \(h_v\) が割り当てられていると仮定し、具体的なノード特徴ベクトルの更新方法を下図に示します。

 

Aggregate で更新ノードの近傍(\(\mathcal{N}(v)\) で表される部分です)の特徴ベクトルを集約し、Combine で、自身の特徴ベクトルと集約した特徴ベクトルを用い、新しい特徴ベクトルを生成します。グラフ分類・回帰タスクを行う場合、最終的に Readout でグラフ全体の特徴ベクトルを生成します。

実際のモデルにおいて、Aggregation や Readout の部分にあたる特徴ベクトルの多重集合に対する関数は、Max, Average, Sum などが用いられることが多いです。例えば、Kipf らにより提案されたノード分類における GNN モデルである、 Graph Convolutional Networks (GCN) [5] では、Aggregation の部分に Element-wise mean を、Combine の部分に1層のパーセプトロンを用いています。

では、GNN の性能を最大限に引き出すためにはどのような操作が良いでしょうか?これに関し Xu らは、ノード近傍の特徴ベクトルの多重集合における区別可能性を基に考察しています [6]。これを簡単に説明します。

上図におけるノードの色は、特徴ベクトルを表しており、同じ色は同じ特徴ベクトルです。今、黄色のノードの特徴ベクトルを更新する際の Aggregation について、具体的な例として上げた Max と Average と Sum の 3 つについて考えます。Max や Average を取った場合は、左右どちらとも緑色が 1 つになってしまい、2 つのグラフを区別できません。しかし、Sum をとった場合、左は緑が 3 つ、右は緑が 2 つとなり、区別できるようになります。

このようないくつかの考察を通し、Xu らは Graph Isomorphism Network (GIN) と呼ばれる、Aggregation や Readout を Sum ベースに行う、シンプルなネットワーク構造を提案し、多くのグラフ分類タスクで State-of-The-Art を達成しています。今回、木幅を予測するために試したいくつかの GNN 構造は、この GIN における、Aggregation や Readout の部分を変えて得られるものを用いました。詳しくは後述するコードをご覧ください。

どのように木幅を予測するか

今回、下記に示す 2 つの手法を用い木幅の予測を行いました。

  1. 既存のアルゴリズムと GNN を組み合わせての予測
  2. GNN を用いた直接予測

それぞれの手法について説明する前に、今回用いたグラフデータセットについて簡単に説明します。

今回用いたグラフデータセット

GNN を学習させるためのデータセットが必要になりますが、木幅に関するデータセットはほとんどありません。見つけたデータセットとして、Parameterized Algorithms and Computational Experiments Challenge (PACE) と呼ばれる様々な組合せ最適化問題に対するアルゴリズムの設計を競うコンテストにおいて、2016 年、2017 年に木幅に関するコンテスト [7, 8] が開かれた際に用いられたデータセット [9] がありましたが、200 グラフほどしか含まれておらず、GNN の学習に用いるためには少し心許ない数量でした。そこで、ランダムにグラフを生成し、木幅を既存の木幅計算プログラムで計算することで、GNN の学習に用いるためのデータセットを作成しました。

今回、グラフを生成する際に用いたランダムグラフ生成モデルは下記の 3 つです。

各モデルからそれぞれ 10000 グラフを生成し混ぜ合わせたデータセットを用いました。後述する各分類タスクにおいては、ラベルが均等になるように選択し、回帰タスクにおいては、30000 グラフの中から、10000 グラフをランダムに選択し、それぞれのタスクにおいてデータセットとして 1 割をテストデータ、残りを訓練データとしています。

また、ラベル付けのために木幅を計算するための既存のプログラムとして、先程も取り上げた 2017年に開催された PACE の木幅の計算コンテストにおいて提出された、明治大学の玉木先生の実装 [10] を用いました。

アプローチ 1

既存の木幅を計算するアルゴリズムに対し、GNN による木幅に関する分類タスクの予測結果を探索状態の枝刈りに用いることで、既存のアルゴリズムの高速化を図りました。

既存アルゴリズムについて

木幅を計算する既存アルゴリズムは複数あります。詳しくは [11] をご参照ください。今回は、[11] にて取り上げられていた 空間計算量、時間計算量ともに \(O^{\ast}(2^n)\)*2 である木幅計算アルゴリズムを参考にした、下記に示す Algorithm 1 を用います。アルゴリズム中に登場する、\(\mathrm{Q}(G, S, v)\) の詳細については [11] を御覧ください。これは、あるグラフ \(G=(V, E)\) に対し \(\mathbf{TWCheck}(G, V, opt)\) を呼び出すことで、\(G\) が木幅 \(opt\) 以下であるかどうかを判定します。つまり、\(opt = 1\) から値を 1 ずつ増やしながら順に代入していき、初めて true を返した値、または \(opt = |V| – 1\) から値を 1 ずつ減らしながら順に代入していき、初めて false を返した値に 1 を加えた値として、\(G\) の木幅を計算できます。以降、前者を Lower-Calculation、後者を Upper-Calculation と呼びます。

*2 Big-O Star 記法と呼ばれ、ある評価関数の指数部オーダのみを記述するためのものです。Parameterized Algorithm 分野でよく用いられます。詳しくは文献 [14] をご参照ください。

今回導入する枝刈り

上記の擬似コードを見ていただくとわかるように、一度の木幅判定において最大で \(\mathbf{TWCheck}\) が \(O(|V|!)\) 回呼び出されてしまいます。そこで、 \(\mathbf{TWCheck}(G, S, opt)\) が、\(G\) において、\(V\) の部分集合 \(S\) で誘導される部分グラフ \(G[S]\) の木幅が \(opt\) 以下であるかどうかを返す関数であることに着目し、この誘導部分グラフの木幅を GNN により分類し、その結果次第で枝刈りを行う部分を追加します。これにより、結果が不正確なものになる可能性と引き換えに、再帰回数が減るため関数呼び出し回数の減少、実行時間の削減が見込まれます。この枝刈りについて具体的に説明していきます。

まず、木幅がしきい値 \(thresh\) 以下かどうかでラベル付けを行った二値分類タスクの学習を行った GNN を考えます。枝刈りを行うために、 \(G[S]\) に対しこの GNN を用い推論を行います。

ここで、現在の \(opt\) の値が \(thresh\) より小さく、GNN による予測結果が \(thresh\) より大きい場合、部分グラフの木幅が十分に大きいと判断し、枝刈りを行って false を返します。これを Upper-Prune と呼びます。一方、現在の \(opt\) の値が \(thresh\) より大きく、GNN による予測結果が \(thresh\) より小さい場合には、部分グラフの木幅が十分小さいと判断し、枝刈りを行って true を返します。これを Lower-Prune と呼びます。これら 2 つの枝刈りをまとめたものを下図に示します。

この枝刈り方法の利点として、下記の 3 つがあります。

  • 先述の Lower-Calculation や Upper-Calculation と適切に組み合わせることで、正確に上界や下界の計算が可能な点
  • Softmax Cross Entropy 関数を損失関数に用いモデルを学習させることで、モデルの予測確率を考慮した枝刈りが可能になる点
  • 今回の二値分類モデルだけではなく、多値分類モデルを用いる際にも容易に拡張できる点

正確な上界・下界の計算が可能

これら 2 つの枝刈り方法は、先程述べた Lower-Calculation や Upper-Calculation と適切に組み合わせることにより、与えられたグラフに対する木幅の上界や下界を計算できます。前者は Upper-Prune と、後者は Lower-Prune と組み合わせることにより、それぞれ正確に上界と下界を計算できます。

前者について少し説明します。Lower-Calculation のアルゴリズムを、\(opt = |V| – 1\) が入力された場合必ず \(true\) を返すように書き換えます。ここで Upper-Prune において、本来は True であるべき場所で False を返してしまった場合を考えます。これにより、本来はある木幅 \(k\) 以下であると判定されるべき値で、木幅は \(k\) より大きいと判定することとなり、本来よりも大きい値として算出してしまいます。後者についても同様に示すことができます。

モデルの予測確率を用いた枝刈りが可能

Cross Entropy 関数を損失関数としてニューラルネットワークを学習するということは、モデルの出力ベクトルを活性化関数(Softmax 関数)に通した際の各要素が、各クラスへの割り当て確率となるように学習することとみなせます。そのため、出力ベクトルの要素の最大値 \(x_{max}\) に対し、\(x_{max} \geq \mathrm{prob\_bound}\) となる場合にのみ、枝刈りを行うことで、モデルの予測確率が \(\mathrm{prob\_bound}\) 以上である予測のみを考慮でき、最終的に出力する木幅の精度の向上が見込まれます。

多値分類モデルへの拡張が可能

二値分類を行う GNN だけでなく、多値分類タスクに対して訓練済みの GNN を用いる場合にも容易に拡張可能です。また、前述の予測確率を組み合わせることで、さらなる精度の向上が見込まれます。

GNN は木幅に関する分類タスクを適切に学習できるか?

今回導入した 2 つの枝刈りにおいて、GNN による予測性能が重要になるため、分類タスクを適切に学習した GNN が要求されます。しかし、木幅は [12] でも述べられているように、大域的な連結度を表す値であり、近傍の集約を繰り返し特徴ベクトルを更新していく今回の GNN では、木幅に関する特徴を適切に学習できない可能性があります。そのため、まずは木幅に関する分類タスクの実験による検証を行いました。

今回は、しきい値 \(thresh\) に関して \(\frac{|V|}{2}\) を用いる二値分類タスクと、\(\lfloor \frac{5tw(G)}{|V|} \rfloor\) の値でラベル付けした 5 クラス分類タスクを考えました。詳しいハイパパラメータの設定などは後述するコードをご覧ください。

GNN における木幅に関する分類タスク実験の結果

それぞれのタスクにおける実験結果として、テストデータに対する精度の推移を下図に示します。

Operation Type における、A は Aggregation、R は Readout の種類を表しています。どちらの場合も、Aggregation に max を使用したもの以外は 9 割前後、8 割前後といった高い精度が得られています。この結果より、GNN は Aggregation, Readout の方法をうまく選択することで、木幅に関する分類タスクを適切に学習できると判断しました。今回用いる GNN モデルにおける Aggregation, Readout の方法として、総合的に精度が良かった、どちらも sum を用いる組み合わせを使用しました。

アプローチ 2

先程は分類タスクに対する GNN を利用しましたが、こちらは直接グラフ回帰問題として GNN により End-to-End で木幅を予測しようというアプローチです。先程の実験結果より、GNN を用いた木幅に対する分類タスクの精度が良く、GNN が、木幅に関する特徴を適切に捉えていると考えました。そのため、End-to-End で予測を行うことで、より精度良い予測が可能になると考えました。しかし先程とは異なり、この方法では正確な上界や下界などは得られません。

今回、アプローチ 1 で用いた GNN 構造により出力されるベクトルの次元数を 32 に変え、続いてそれを 2 層の MLP に入力し、最終的に 1 つの実数値を得るといったネットワーク構造を用いました。詳しいネットワーク構造は後述するコードをご覧ください。

実験結果

アプローチ 1

今回、先程紹介した既存のアルゴリズムと GNN による枝刈りを導入したアルゴリズムの両方を python 3.7 にて実装し、先程のランダムグラフ生成モデルより生成された 50 個のグラフに対し、アプローチ 1 の有効性を検証するための実験を行いました。

今回、GNN による枝刈りを導入したアルゴリズムのうち下記の 3 つを実装しました。

  • 上界を求める Upper-Prune と Lower-Calculation を組み合わせたもの(Upper-Alg)
  • 下界を求める、 Lower-Prune と Upper-Calculation を組み合わせたもの(Lower-Alg)
  • 双方の枝刈りを採用した上で、Lower-Calculation を行うもの(Combine-Alg)

これらと Lower-Calculation ベースの既存のアルゴリズム(Existing-Alg)との比較を行いました。また、グラフの大きさによっては途方も無い時間がかかってしまうことが予期されるため、タイムアウトを 10 分に設定しました。

結果を下図に示します。

10 分以内に実行が完了したインスタンス数は、既存のアルゴリズムでは 9 となったのに対し、 Combine-Alg では 18 と、既存アルゴリズムより多くのインスタンスに対し計算できていることがわかりました。また Lower-Alg や Upper-Alg ではそれぞれ 8, 10 となり、既存アルゴリズムとほぼ変わりませんでした。

続いて、この枝刈りによりどの程度既存のアルゴリズムが効率よく動作するようになったかを見るために、関数呼び出し回数を比較しました。今回、Upper-Alg で枝刈りが行われたインスタンスは、Combine-Alg や Lower-Alg ではタイムアウトしていたため、Combine-Alg と Lower-Alg に関して、平均の減少率を計算しました。これは、どちらも 9 割前後となり、GNN による枝刈りが効率よく動作していることがわかりました。

また、精度を比較するために、近似解と真の値との絶対値の平均を計算したところ、Combine-Alg では 1.6 、Lower-Alg では 2.6 となりました。より積極的な枝刈りを行う Combine-Alg のほうが精度が良く、直感と反する結果となっているため、今後より多くのインスタンスで実験を行い検証する必要があります。

しかし、表には載せていませんが総合的な実行時間を比較すると、Combine-Alg などで平均よりも多く枝刈りを行っているいくつかのインスタンスを除き、既存のアルゴリズムのほうが実行時間が速いです。これは、GNN の推論に時間がかかっているためと考えられます。多くの場合、総実行時間の 9 割ほどを占めていました。

下記に、どの程度関数呼び出し回数が減少しているかの例として 、2 つのインスタンスに対し、実際のグラフと関数呼び出し回数をプロットした棒グラフを示します。

アプローチ 2

テストデータに対する Mean Absolute Error (MAE) の値の推移を下図に示します。

このグラフを見ていただくとわかるように、分類タスクと同様に、Aggregation, Readout ともに sum を用いるモデルが最も精度がよく、最終的な値は 0.75 ほどとなりました。これは、予想したように手法 1 よりも良い結果が得られています。また、テストデータに対し、予測した木幅と実際の木幅をプロットした散布図を下記に示します。左側が GNN (Aggregation, Readout ともに sum を用いるモデル)による結果で、右側が同じデータを用い、頂点数、辺数、平均次数で線形回帰を行った際の結果です。

散布図を見るとわかるように、大きく外している例は無いことがわかります。これら結果を比較してもわかるように、比較的精度良く予測ができていると考えられます。

まとめ

まず、アプローチ 1 についてですが、いくつかのインスタンスで枝刈りルールがうまく働き、関数呼び出し回数の観点において 90% ほどの減少が見られました。しかし、推論に時間がかかっており、総実行時間の面では改善が見られないインスタンスも多くありました。今回のインターンシップでは推論の高速化については特別には取り組みませんでしたが、推論フレームワーク(例えば Menohchainer-trt, chainer-compiler)の利用や各種の最適化によって、ある程度は高速化できる可能性があります。

続いて、アプローチ 2 についてですが、平均絶対誤差が 0.75 ほどのモデルが学習でき、いくつか計算が容易なグラフ不変量を用い線形回帰を行った結果と比較し、精度よく予測ができていました。

今後の課題として、より素早く正確に推論が可能なモデルや推論フレームワークを使用すること、素早く計算が終わる状態から探索木を展開していくために、探索順序を学習させ高速化を図るなどがあります。また、ハイパパラメータのチューニングなどは一切行っていないため、ハイパパラメータのチューニングなどで更に精度が向上すると考えています。

今回、実験に使ったコードはこちらにまとめられています。もし、興味がありましたらご覧ください。

インターンシップ全体を通しての感想ですが、今回取り組むテーマとして選んだこの課題は、自分で興味を持ったテーマを選んだため、結果が出るかどうかがわからなく不安なことも多くありましたが、メンターの酒井さんや劉さん、並びに他の社員の皆さんやインターンの皆さんに助けられながら、なんとかここまで進められました。お世話になった皆様、本当にありがとうございました。

参考文献

  1. Hans L. Bodlaender, Arie M. C. A. Koster, Combinatorial Optimization on Graphs of Bounded Treewidth, The Computer Journal, Volume 51, Issue 3, May 2008, pp. 255–269.
  2. Paul Erdős and András Hajnal, On chromatic number of graphs and set-systems,  Acta Mathematica Hungarica, 17.1-2, 1966.
  3. Manuel Sorge,  The graph parameter hierarchy, 2013.
  4. Ziwei Zhang, Peng Cui and Wenwu Zhu, Deep learning on graphs: A survey, arXiv preprint, 2018.
  5. Thomas N. Kipf and Max Welling, Semi-supervised classification with graph convolutional networks, ICLR 2017.
  6. Keyulu Xu, Weihua Hu, Jure Leskovec and Stefanie Jegelka, How powerful are graph neural networks?, ICLR 2019.
  7. Holger Dell, Thore Husfeldt, Bart M. P. Jansen, Petteri Kaski, Christian Komusiewicz and Frances A. Rosamond, The First Parameterized Algorithms and Computational Experiments Challenge, IPEC 2016.
  8. Holger Dell, Christian Komusiewicz, Nimrod Talmon and Mathias Weller, The PACE 2017 Parameterized Algorithms and Computational Experiments Challenge: The Second Iteration, IPEC 2017.
  9. PACE-challenge/Treewidth: List of Treewidth solvers, instances, and tools, https://github.com/PACE-challenge/Treewidth
  10. Tamaki, Hisao. Positive-instance driven dynamic programming for treewidth, ESA 2017.
    著者実装 https://github.com/TCS-Meiji/PACE2017-TrackA
  11. Hans L. Bodlaender, Fedor V. Fomin, Arie M. C. A. Koster, Dieter Kratsch, Dimitrios M. Thiliko. On exact algorithms for treewidth, ACM Transactions on Algorithms, Vol 9, 1, Article 12, 2012.
  12. 河原林 健一, グラフの木分解と木幅に関する研究とグラフマイナー, 数学, 2015, 67 巻, 4 号, p. 337-355, 2017.
  13. 木分解とグラフ・アルゴリズム (最適化と数え上げ) – IBISML 2008,  岡本 吉央
  14. Woeginger, Gerhard J. “Exact algorithms for NP-hard problems: A survey.” Combinatorial optimization—eureka, you shrink!. Springer, Berlin, Heidelberg, 2003.

メンターからのコメント

メンターを担当したPFNの酒井と劉です。

当初こちら側では、組合せ最適化問題に機械学習・深層学習を応用するようなテーマを考えていたのですが、中野さんから「直接計算するのが難しいグラフの不変量をGNNを使って予測できないか」という提案を受け、劉のグラフアルゴリズムに関する知識や興味もあって、トントン拍子に決まったのが今回のテーマです。

最初は、「木幅は大域的な性質なので、GNNによる予測はあまりうまく行かないのではないか」と予想していて、そういう結果が出たときに、それをどう改善したり問題を単純化すれば解けるのかを考えていくことになると想定していたのですが、中野さんに一通りの実装と最初の実験をしてもらってみると、想像以上の精度で予測することができ、メンター二人もとても驚きました。

インターンシップの限られた期間では、より本格的なアルゴリズムへの組み込みや、現実的な応用方法については踏み込むことは出来ず、それらは今後の課題になりますが、今回の結果だけでも非常に面白い結果だと考えています。

微分可能なシミュレータ上での方策最適化

Kengo Nakasuka

2019-10-08 14:40:58

本記事は、2019年インターンシップに参加された金川さんによる寄稿です。


こんにちは。PFNの2019夏季インターンシップに参加した、東京大学の金川です。大学では、強化学習を使って賢くロバストなゲームAIを作る研究をしています。

今回のインターンシップでは、「微分可能なシミュレータ上での方策最適化」というテーマで研究を行いました。この記事では、その内容と結果について、簡単に紹介させていただきたいと思います。

なぜ微分可能なシミュレータか

現実世界では、時間が途切れることなく流れているので、次々と行動を決定していかなくてはいけません。そのため現実世界でロボットを動かしたい時にとれる選択肢の一つは、状態Sを観測した時、あらかじめ学習しておいた方策\(\pi(\cdot|S)\)から行動aをサンプリングし、それにしたがって行動させることです。方策が例えばニューラルネットで表現されていれば、各タイムステップで行動計画を最適化する方法と比べ高速に行動を計算できるため、リアルタイム性が求められるドメインでは大きなメリットがあります。

方策を訓練する方法として、強化学習が注目され、さかんに研究されています。強化学習とは、エージェントがある行動をとると次の状態と報酬が返ってくる、というブラックボックスな環境で、報酬和の期待値を最大化するように方策を訓練する枠組みです。強化学習の課題として、しばしばそのサンプル効率の悪さが挙げられます。例えば、昨年のリサーチブログ で紹介されたEmergence of Locomotion Behaviours in Rich Environmentsでは、シミュレータ上のロボットに歩行動作を獲得させるため、1千万回程度ネットワークのパラメタを更新する必要がありました。

しかし、もしブラックボックスな環境を仮定しないならば、シミュレータの内部情報を上手に使って、学習を効率化できるのではないでしょうか。方策としてニューラルネットを使う場合、報酬をネットワークのパラメタについて微分した値が得られれば、それを利用して直接パラメタを更新できそうです。

手法の説明

そこで今回は微分可能なシミュレータを作成し、勾配という形でシミュレータの内部情報をエージェントに渡すことで、効率よく方策を訓練する手法を試みました。具体的に、シミュレータ内部での遷移関数・報酬関数の計算を、微分可能な演算のみに限定します。この演算過程をchainerの提供するdefine by runスタイルの自動微分を使って記述することで、状態遷移・報酬関数をパラメタで微分できるようになります。

すると、方策と未来の状態・報酬が微分可能な計算グラフでつながり、強化学習における最大化ターゲットである報酬和を、直接方策のパラメタについて微分できます。こうして得られた勾配\(\frac{\partial\sum_{t}\gamma^t R_t}{\partial \theta}\)を使って、方策を勾配上昇法により直接最適化します。

実際のアルゴリズムでは、適当な定数Nをとって、Nステップ分の割引報酬和\(\sum_{t=t_0}^{t_0 + N} \gamma^{t-t_o} R_t\) を最大化します。また学習高速化のため、A2C スタイルの環境並列化およびバッチ学習を行いました。これはシミュレータ内部の物理パラメタをベクトルとして持つだけで、簡単かつ効率的に実装できます。行動についてはすべて連続値をとるものとし、決定的に行動を出力する方策と、行動の正規分布を出力する確率的な方策の2種類を試しました。正規分布からのサンプリングは、再パラメータ化トリック を使うことで逆伝播可能な演算として表現できます。

実験結果

今回のインターンシップではOpen AI gymのClassical Controlタスクを中心に、いくつかの環境をchainerを用いて微分可能なシミュレーションとして実装しました。その上でシミュレータの勾配を使った方策の学習を行って、以下の3点を検証します。

  1. この手法がうまくいくような問題があるか
  2. 決定的な方策を使うものと確率的な方策を使うものでは、どちらの性能が良いか
  3. この手法は、どのような問題に対してうまくいかないか

まず、特に簡単な問題であるCartPole での結果を示します。

これは、台車に力を加え、上に乗っている棒を安定させる問題です。棒が一定以上倒れるか台車が画面の外に出ると、ゲームオーバーになります。

オリジナルの問題での行動は、 「-1or1の力を加える」という離散的でなものですが、今回の設定では[-1, 1]の連続値をとるように変更しました。報酬についてはオリジナルの問題ではゲームオーバーなら0、それ以外なら1が貰えますが、今回は微分可能になるように改造した \(1.0 -\frac{2|\theta |}{\pi} \) を与えました。実装した他の環境に対しても同様に、なるべく元の問題と変わらないよう行動を連続値に、報酬を微分可能にする変更を行っています。

上図に結果を示します(シミュレータのステップ数で性能を比較していますが、同じステップ数の場合ネットワークの更新回数は提案手法の方が20倍程度少ないです。)

どちらの方策を使う場合も、ベースラインとして使用した深層強化学習の手法(TD3) と比べ、20倍以上早く収束していることがわかります。

次にFlappyBirdでの実験結果を示します。これは元々iOS向けに公開されていたゲームですが、今回はOSSとして公開されているPythonクローン をもとに、chainerにより再実装しました。

ゲームの内容としては、鳥に上方向の力を加え土管にぶつからないように飛行させる、という単純なものです。オリジナルの問題では画面をタップするとかなり強い力が加わりますが、今回は連続値の力を加えるため、やや簡単になっています。しかし内部状態(=位置、速さ、角度など)だけが与えられた先程のCartPoleと比べると、この問題では土管の位置など多様な観測情報をもとに行動決定を行う必要があるため、学習は難しくなりそうです。下図に、実験の結果を示します。

実際に行動を観察(上図左)してみると、スタート直後から急激に上昇し、画面外で土管に激突していることがわかります。

この原因について考えるため、この手法での最大化ターゲット\(\sum_{t=t_0}^{t_0 + N} \gamma^{t-t_o} R_t\) を再訪してみましょう。方策を変えれば将来貰える報酬は変化しますから、この式は現在の方策のもとでの報酬の期待値\(\sum_{t=t_0}^{t_0 + N} \mathbb{E}_\pi  \left[ \gamma^{t-t_o} R_t\right]\) (…式1) を最大化しています。

そのため方策がランダム性を持っていないとき、局所最適解に陥りやすくなってしまうのです。強化学習では、局所最適に陥らないよう広範な行動データを収集する必要があり、そのための行動を探査(exploration)といいます。

一方で確率的な方策を使うものは、やや不安定ではあるもののベースラインを大きく上回る性能を残しています。この問題では探査に成功しているようです。(上図右)に示すように、飛行動作も安定しています。

以上の2つの実験から、この手法が単純な状態遷移のダイナミクスを持つ問題に対しては非常にうまくいくこと、探査が必要な問題では確率的な方策の方が性能がよいことがわかりました。

しかしもっと複雑な、カオス的な挙動をする系では、少しの方策の違いが将来の報酬を大きく変動させます。そのため式(1)の分散は非常に大きくなり、学習は難しくなりそうです。

カオス的な問題として、CartPoleSwingUp(下図)での実験を行いました。これは先程のCartPoleとほとんど同じ問題ですが、通常のCartPoleで初期位置がθ=0の近傍から始まるのに対し、θの値が[-π, π]からランダムに与えられます。

この変更はダイナミクスに強い非線形性をもたらすだけでなく、探査も難しくします。

報酬については原論文に似せた \(\frac{\cos (\theta) + 1)}{2} \)を使用しました。下図に結果を示します。

どちらの方策を使う場合も、ベースラインより大きく劣るという結果になりました。

次に探査に失敗する例として、MountainCar(下図)での結果を紹介します。この問題では右上の旗にたどり着かないと正の報酬が貰えませんが、そのためにはいったん左の坂を登って勢いをつけないといけません。

下図に結果を示します。

これも、ベースラインよりはるかに劣るという結果になりました。

この問題では車を動かすため使用した燃料の量に応じて負の報酬が入りますが、それに過剰に反応し、なるべく力をかけないような方策を学習してしまいます。

以上の2つの実験から、この手法がカオス的なダイナミクスを持つ問題や、局所最適に陥りやすい問題に対してはあまり性能が出ないことがわかりました。

まとめ

微分可能な物理シミュレータは新しい研究分野です。決定的な方策を最適化するもの物理パラメタの推定に用いるもの などが提案されていますが、いまだにロボット制御など複雑なシミュレータで検証を行った研究は、我々の知識ではありません。そのため今回のインターンでトイモデルではあるものの、様々な問題で微分可能シミュレータ上での方策最適化の性質を調べられたことは、この手法をより複雑なドメインへ適用するために大きくプラスになったと考えています。

今回の実験では様々な課題が見つかり、単にシミュレータを微分可能にすれば何でもうまくいくという訳ではない、ということがわかりました。しかし簡単な問題では性能が出ることを確認できましたし、またシミュレータ自身が訓練可能になるなど、今回は検証できなかった多くの興味深い性質を持っています。今後も様々な側面から、微分可能シミュレータの可能性を探っていければと思います。

謝辞

慣れないテーマで困惑することや大変に感じることもありましたが、メンターのお二方、インターン同期の方々、同じチームの方々と相談しながら楽しく作業を進めることができました。ありがとうございました。

おまけ:メンターより

金川さんのメンターを担当した、PFNの中須賀と今城です。

PFNでは微分可能シミュレーションの研究開発を行っています。微分可能シミュレーションによって初期値同定など様々な問題が解けることがわかりつつありますが、ただオプティマイザーに投げるだけでは十分な探索が行われないがゆえの問題があり、これを強化学習のアイディアをうまく取り入れて解決できないかということで始まったプロジェクトでした。金川さんには短い期間で様々なアプローチで強化学習のアイディアを取り入れ検証し微分可能シミュレータの可能性を見出していただきました。

深層学習をただ適用するだけではなく問題の性質を考えた学習方法を提案できるというのがPFNの強みの一つであり、問題の性質を理解したり新たな学習方法を理解し現実で解かれていない難しい問題を解くために、このように基礎研究に近いようなアイディアから取り組むということも行っています。今回のプロジェクトはそのような取り組みの一環でもあります。興味のある学生の皆さんは、ぜひ来年のPFNインターンシップへの応募をご検討ください。 また、もちろん中途・新卒の人材募集も通年で行っていますので、こちらも興味のある方はぜひご検討ください!PFNの人材募集のページはこちらです。