KubernetesのSchedulerを評価するためのシミュレーター「k8s-cluster-simulator」公開

Daisuke Taniwaki

2019-04-11 08:00:27

概要

2018年夏のインターンおよびPEとして勤務した薮内さんとそのメンターである谷脇大村で開発したKubernetesクラスターのシミュレーターであるk8s-cluster-simulatorのアルファ版をオープンソースとして公開しました。このシミュレーターはKubernetesクラスタに投入されるPodのワークロードを時間とともにシミュレートできるため、Kubernetesのスケジューラーを本番環境に投入する前に評価することができます。

開発の動機

PFNでは巨大なオンプレのGPUクラスタを持っており、その上でKubernetesを使って様々な実行時間の機械学習ジョブを研究者が実行しています。我々クラスターサービスチームのミッションの一つとして、GPUの利用率を向上させ費用対効果をあげることが挙げられます。一方で、研究者間で使えるリソースの平等さも考慮しなければなりません。これを実現させるために、我々はKubernetesのスケジューラーを独自で開発したり、Extender (例 kube-throttler)を拡張したりしています。しかし、新しく開発したロジックを本番環境で走っている機械学習ジョブに影響させずに評価するのは難しく、また頻繁に試行錯誤を本番環境上で行うのは好ましくありません。バグのあるスケジューラーをデプロイしてしまった場合には研究者の仕事を止めてしまうことになるので、絶対に避けなければなりません。またスケジューラーのアルゴリズムを試すためだけに、大規模なクラスタを用意し、多くのワークロードを実際に可動させることも現実的ではありません。これらの理由からKubernetesのスケジューラーを評価するためのクラスタのシミュレーターの開発を開始しました。

デザイン

シミュレーターを開発するにあたって以下のことを考慮しました。

  • シミュレーター用のスケジューラーの実装を最小限の変更で本番環境で動かせるようにする。
  • 時間をシミュレートすることで評価を高速化するとともに、通信や内部処理のレイテンシーがスケジューリングのロジックの評価に影響しないようにする。
  • シミュレートするワークロードを自由に設計できる。
  • 後段の分析のために様々なメトリックスを出力できる。

 

アーキテクチャ

以下は簡単なフロー図になります。

 

アイデアはすごく簡単です。シミュレーターはループのステップ毎にクロックを1つ進めます。各ステップでサブミッターにそのクロックで投入するPodがあるかどうかを聞いて、サブミッターは投入または削除するPodがあればPodのリストを返します。シミュレーターはPodのリストをスケジューラーに渡し、スケジューラーはBindするものと削除するPodを選んでイベントとして返し、シミュレーターがリソース管理を行います。そして、この時に処理されたPodのメトリックスをMetrics Loggerに出力する流れになります。

 

以下はハイレベルなクラス図になります。

 

本シミュレーターでは拡張できる点は以下の2つになります。

 

Submitters

シミュレーターの定義するインターフェースに沿っていれば任意の数、組み合わせのサブミッターを使用することができます。複数のサブミッターをシミュレーターにプラグインできるので、例えばAさんは朝たくさんのPodをサブミットする傾向があるが、Bさんは夕方たくさんのPodをサブミットする傾向があるといったシミュレーションをする場合、それぞれのユーザの振る舞いモデルを独立に開発してシミュレーターにプラグインできます。

また、サブミッターはクロック毎のメトリックスを受け取ることができるため、クラスターの利用状況に応じて挙動を変えることも可能です。

Scheduler

スケジューラーの拡張方法は2種類あります。
Kubernetesのスケジューラー(kube-scheduler)をそのままもしくは拡張したアルゴリズムを利用したい場合、kube-schedulerが用意しているのと同様, Prioritizer, Extender, Predicateをセットできるミミックスケジューラーが用意されています。kube-schedulerはキューベースのスケジューラーですが、複数のPodを条件に応じてまとめてスケジュールするような、例えばより複雑なスケジューラーをシミュレーションしたい場合には、シミュレーターが定義するインターフェースを実装するように少しラッパーメソッドを書くと、それも評価できるようになっています。

*kube-schedulerの挙動については大村によるQiita投稿をご覧ください。

ロードマップ

現在、シミュレーターの使いやすさを向上させ、またより現実的な環境をシミュレーションできるように、ベータバージョンに向けて以下の機能を開発しています。

  • より疎結合なコンポーネント(例:スケジューラーとサブミッターにRPCインターフェースをサポート)
  • よく使われるサブミッターの提供(例: 典型的な確率分布に従うサブミッター(一様分布、二項分布、ポアソン分布等)
  • より多くのクラスターイベントへの対応(ノード故障、突発的なPod故障、ノード追加、削除)
  • デファクトなプロッターツール(matplotlib, gnuplot等)で直接読み込める出力フォーマットのサポート

興味のある方は是非試していただいて、フィードバックをいただけると幸いです。

 

深層強化学習エージェント可視化ライブラリChainerRL Visualizer公開

ofk
エンジニア

2019-03-19 12:40:11

本記事は、2018年インターンシップを経て、PEとして勤務した石川さんによる寄稿です。

ChainerRLで学習したエージェントの挙動などを, ブラウザ上に可視化するライブラリ「ChainerRL Visualizer」を公開しました.

PFN2018年夏季インターンシップに引き続き, 現在アルバイトをしている東京大学の石川貴大です.

このライブラリは「強化学習のデバッグを容易にする」「強化学習のエージェントの仕組みの理解に貢献する」という思想の元で作られ,
学習済み, 及び学習途中の強化学習のエージェントの挙動をインタラクティブにブラウザ上から観察できるような機能が実装されています.

使い方は非常に簡単で, このライブラリで提供されている launch_visualizer という関数に,
ChainerRLで実装した agent オブジェクトと, 特定のインターフェースを満たした env オブジェクトを, オプションと共に渡すだけです.

from chainerrl_visualizer import launch_visualizer

# Prepare agent and env object here
#

# Prepare dictionary which explains meanings of each action
ACTION_MEANINGS = {
  0: 'hoge',
  1: 'fuga',
  ...
}

launch_visualizer(
    agent,                           # required
    env,                             # required
    ACTION_MEANINGS,                 # required
    port=5002,                       # optional (default: 5002)
    log_dir='log_space',             # optional (default: 'log_space')
    raw_image_input=False,           # optional (default: False)
    contains_rnn=False,              # optional (default: False)
)

実行するとローカルにサーバーが立ち上がり, ブラウザ上から以下のような操作ができます.

1. 指定したステップ分, エージェントをサーバー上で動作させる
サーバー上でエージェントが指定されたステップ分の動作をし, エージェントのモデルの出力が時系列で可視化されます.
以下の動画では, A3Cで学習されたエージェントの Probability of next action と State Value が時系列で出力されています.

2. エージェントを1ステップずつ動作させ, その時の挙動をモデルの出力と共に可視化する
以下の動画では, A3Cで学習されたエージェントを1ステップずつ(前後に)動作させ, その出力をenvの様子と共に観察しています.
右下の円グラフは, 各ステップにおける Probability of next action を表しています.

3. Saliency mapの可視化 (モデルの入力が画像のピクセルデータの場合のみ)
エージェントが画像のどの部分に特に注目して特徴量を抽出しているのかを可視化する機能を, モデルの入力が画像のピクセルデータの場合に特化して実装しました.
この機能は, Visualizing and Understanding Atari Agents を参考にして実装しました.
以下の動画では, CategoricalDQNで学習されたエージェントのSaliency mapを可視化しています.
現時点でSaliency mapを可視化する計算コストがかなり大きいため, Saliency mapを可視化するステップの範囲を指定できるようにしています.

4. その他様々な可視化
エージェントの種類に応じて様々な可視化をサポートしています.
例えば以下の動画では, CategoricalDQNで学習したエージェントの, ステップごとの価値の分布を可視化しています.

とりあえず動かしてみるためのクイックスタートガイドを用意しています.

これまでの多くの可視化ツールは, 「学習の進行に合わせたスコアの表示, およびその他指標の遷移」を可視化することに主眼が置かれていましたが,
ChainerRL Visualizerは, 学習済み, 及び学習途中のエージェントの挙動を動的かつインタラクティブに可視化したという点に, これまでにない可視化ツールとしての特徴があります.

似た思想の元作られたライブラリとしては, Uber Researchによる Atari Zoo が挙げられます.
このライブラリは, 強化学習エージェントを理解するための研究を加速することを設計理念として掲げ, 学習済みモデルと, その学習済みモデルを分析するツールを提供することによって, 計算リソースを十分に持たない研究者に対して, 強化学習エージェントを理解するための研究を促進することを狙っています.
Atari Zooでは, 特定のアーキテクチャ(RawImagePIxel => Conv => Conv .. => FC => FC..)とALEという環境に限定した学習済みモデルと分析ツールを提供しているのに対し, ChainerRL Visualizerでは, ChainerRLで学習したエージェントならばユーザーが学習したどんなエージェントも動的に可視化できるという点で差別化ができています.

また, DQNViz のようにDQNに特化して各種メトリクスを可視化し, DQNのエージェントがどのようなStrategyを学習過程で獲得しているのかを研究しやすいようにサポートするツールの提案も出てきています.

これまで数多くの強化学習の性能向上に関する研究がなされてきましたが, 強化学習のエージェントがどのように環境を解釈し, 何を学習したのかについての研究は比較的少ないものでした.
しかし今後, 以上に見た各種ツールの提案に見られるような強化学習エージェントを理解するための研究が徐々に増えていくことが予想されます.

現在ChainerRL Visuailzerはベータ版であり, エージェントを分析するための機能もまだまだ少ない状態です.
今後発展していくであろう強化学習エージェントを理解するための研究開発に少しでも貢献できるようなライブラリとして進化していけるように, さらなる継続的な開発が必要です.

機能の追加やUX向上に関する調整に関して, OSSなどを通したChainerRL Visualizerへの貢献を歓迎しています.

インターン参加報告:Concolic Testing による SystemVerilog 向けテストパターン生成

Masahiro Sakai

2018-12-25 12:00:56

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


こんにちは。2018年夏季インターンシップに参加していた東京大学の押川広樹です。大学では定理証明支援系やモデル検査を用いたソフトウェアの検証について研究しています。

インターンでは、PFN で開発中のハードウェアに対して「良い」テストを実行することが目標でした。「良い」テストの基準は色々ありますが、今回は効率的で効果的なテストケースを生成することを目指しました。ここで言う効率的なテストとは、短い時間で実行できるように出来るだけサイズの小さいテストセットのことです。また、効果的なテストとはプログラムのより多くの部分を検査できるカバレッジの高いもののことです。

今回はそのようなテストケースを Concolic Testing と呼ばれる手法に基づいて生成することを試みました。

Concolic Testing

まず、テストというとランダムテストが考えられます。ランダムテストは手軽ですが効果的だとは言えません。例えば以下のようなコードを考えてみます。

int x, y;
if (x == y)
  if (x == 10)
    fail;
  else
    ...
else
  ...

上の例は xy が共に 10 の時だけバグがあるプログラムを表します。ランダムテストによってバグを見つけられる確率は単純計算で (int が 32 ビットの時) 232 × 232 回に一回です。

このためランダムテストはコーナーケースになるような微妙な部分のテストには向いておらず、高いカバレッジをとるためにはもう少し賢くテストケースを作る必要があります。その一つの例が Concolic Testing と呼ばれる手法です。Concolic は Concrete と Symbolic を組み合わせた言葉で、Concolic Testing とはプログラムの実際の実行とシンボリックな実行を交互に行うテスト手法です。

Concolic Testing では次の手順でテストを進めて行きます。

  1. ランダムな入力を生成する
  2. 入力に対して プログラム を実行する
  3. 実行時にプログラムのどの部分が実行されたかを記録しておく
  4. 3. の情報を元にその部分が使われるための条件を計算する
  5. 4. の条件の一部を変更し、プログラムの別の部分が実行されるための制約を得る
  6. 5. の制約を論理ソルバーで解くことで、実際にその部分を使うような入力を得る
  7. 2.-6. を繰り返す

各イテレーションごとにプログラムの新しい部分を実行するような入力が得られるので、理想的にはラインカバレッジ100%のテストケースを生成することが出来ます。

ランダムテストと同じ例でどのように動作するかをみてみます。
プログラムは if 文などで分岐する木だと思えるので、上の例は次のように表せます。

まず、xy の値をランダムに生成します。例えば x = 1163551168y = 1363922006 だとします。この下でプログラムを実行すると以下のようなパスを通ります。

このパスを通ったのは、x == y が成り立たなかったからです。したがって制約としてこの条件の否定、つまり x != y を考えます。これを満たすような xy をソルバーを使って求めます。
例えば x = 0y = 0 はこの制約を満たします。次はこれを入力としてプログラムを実行します。次のようになります。

確かに1度目の実行とは異なる部分が実行されています。先ほどと同様、このパスを通ったことから、「x == y かつ x != 10」が成り立つとわかります。x != 10 を否定した制約、「x == y かつ x == 10」をソルバーを用いて解くことで次の入力 x = 10y = 10 を得ます。そして、x = 10y = 10で実行することでちゃんと fail を見つけることができます。

Concolic Testing は Godefroid らによる DART (Directed Automated Random Testing) [1] によって導入されました。[1] では Concolic Testing の手続きの導入と、Cで書かれたプログラムに対しての実装の実験がなされています。

上で説明した Concolilc Testing の手続きを素朴に行うと、対象のプログラムが大きくなるにつれてたどる必要のあるパスの数が爆発するためスケールしません。また、生成される制約が大きくなりすぎてソルバーで制約が解消できなくなる可能性もあります。

そのため実用上は、できるだけ早くカバレッジを増やすようにパスをたどったり、生成される制約を小さくする最適化を加えることで、実際のアプリケーションにも適応できるように改良されています。実際、DART にこのような最適化を加えたものに SAGE [2] があります。SAGE は X86 アセンブリを対象にしており、Microsoft で Office のバグを見つけるのに使われたようです。

また、対象をハードウェア設計言語にしたものに HYBRO [3] があります。HYBRO は Verilog を対象とします。

やったこと

今回は SystemVerilog で記述されたプログラムに対して Concolic Testing を行うフレームワークを作成しました。実装時間の都合で、受け入れられるプログラムの種類は限られていています。具体的には、ある程度制限された SystemVerilog の機能を用いて書かれた組み合わせ回路になります。例えば、interface が使われていないことなどを仮定しています。

テストケース生成の手続きの全体像は以下の図のようになります。

大まかには上で説明した手順と同じです。

  1. まず、SystemVerilog のソースコードをパース・解析して always 文ごとに Control Flow Graph (CFG) を作ります。この際にプログラムが期待する入力の情報(名前や型)を得ます。
  2. 次に、得た情報を使って最初の入力をランダムに生成し、シミュレータを用いて実行します。シミュレータは実行時の各変数の値の情報を Value Change Dump (VCD) というフォーマットで出力します。
  3. VCD には各タイミングでの変数の値の情報が入っているのでこれを元に CFG のどのパスが実行されたかを計算します。
  4. そこからその実行が行われるための条件を求めて、まだ実行されていない部分を次に実行するような入力を生成するのための制約を求めます。
  5. この制約をSMT ソルバーで解くことで次の入力を得ます。
  6. このプロセスをラインカバレッジが100%になるまで繰り返します。

SMTソルバーは Z3 [4] を用い、その他は OCaml によって実装しました。Z3 の API は OCaml から利用することができ便利です。

実装は https://github.com/pfnet-research/ATPG4SV で公開しています。

結果

300行程度の比較的小さめの回路に対して実行したところ10イテレーションほどで100%のカバレッジになるテストケースが得られました。

まだ実装が不完全なので対象に制限がありますが、実際の回路に対して動作させることができました。

まとめ

効率的で効果的なテストケースを生成する手法として Concolic Testing を紹介しました。また、インターンで取り組んだ、SystemVerilog で記述されたハードウェアへの適用例を紹介しました。まだ実用的に役に立つレベルのものではないですが、プロトタイプとして面白いことができたと思います。

最後になりましたが、メンターの酒井さんと Kühn さんには、テーマ決め、自分の知識が少なかったハードウェアに関する質問、発表練習、そして休憩中の雑談、とインターン期間を通して大変お世話になりました。ありがとうございました。

参考文献

  • [1] P. Godefroid, N. Klarlund, and K. Sen. DART: Directed Automated Random Testing
  • [2] P. Godefroid, M. Levin, and D. Molnar. Automated Whitebox Fuzz Testing
  • [3] L. Liu and S. Vasudevan. Efficient validation input generation in RTL using hybridized source code analysis
  • [4] The Z3 Theorem Prover https://github.com/Z3Prover/z3

おまけ:メンターより

押川さんのメンターを担当した、PFNの酒井とKühnです。

PFN ではディープラーニングを高速化する専用プロセッサー MN-Core™(エムエヌ・コア)の開発も行っていますが、チップ設計の検証は大きな課題の一つでした。 今回の取り組みは、この課題への取り組みとして始まった実験的なプロジェクトであり、押川さんには短い期間で、Coqによる部分的な証明などのアプローチも含めた複数のアプローチを検討のうえ、Concolic Testing に基づいたアプローチを選択し、プロトタイプを実装して実際の回路を対象にテストパターン生成のループを回せるところまで開発していただきました。(注: 既存の回路を対象に実験したものであり、現時点でのMN-Coreの実際の開発に適用しているわけではありません。)

PFNは上から下まで様々なことに取り組んでいていますが、まだまだ手が回っていないことも沢山あり、そこに興味のあるインターンの学生さんが来てくれたことをきっかけに新たな取組みが始まることがしばしばあります。今回のプロジェクトはそのような取り組みの一例でもあります。我こそはという学生の皆さんは、ぜひ来年のPFNインターンシップへの応募をご検討ください。 また、もちろん中途・新卒の人材募集も通年で行っていますので、こちらも興味のある方はぜひご検討ください!PFNの人材募集のページはこちら https://www.preferred-networks.jp/ja/jobs です。(FPGA/ASIC開発の人材も募集しています)

インターン参加報告:確率的なプログラムの型による静的検証

Masahiro Sakai

2018-12-19 12:00:32

本記事は、2018年インターンシップに参加された南條陽史さんによる寄稿です。


はじめまして。PFNの2018夏季インターンシップに参加した筑波大学の南條陽史です。 大学ではプログラム言語について研究しており, 型理論やプログラム検証に興味があります。

今回のインターンで“確率的なプログラムの型による静的検証”というテーマで研究開発を行いましたので、その紹介をいたします。

テーマの説明

確率的なプログラムの検証

確率的プログラム、というと色々な意味がありますがここでは確率分布からのサンプリングといった確率的な挙動を含むプログラムを指します。 研究の目的はこの確率的プログラムに対して“悪いことが起きる確率はいくら以下である”とか“よいことが起きる確率はいくら以上である”といった確率についての仕様検証をすることです。

確率的なプログラムの仕様検証の応用例として以下が挙げられます。

  • 確率的に生じる観測誤差によってシステムが誤った判断をしてしまう確率がしきい値以下であることの検証
  • クライアントに仕事を割り振るシステムについて、あるクライアントに捌き切れないほど多くの仕事を流してしまう確率がしきい値以下であることの検証

このように確率的なプログラムの検証は現実的な問題に直接結びついています。

型による検証

僕のテーマはこの確率的なプログラムの検証を“型”主導で行うというものです。 型というのはintとかcharとかstringとかのあの型です。 プログラムの仕様としての型という考えを推し進めると、例えば以下のように詳細な仕様を型として記述できます。

rand(0, 5) : {x:int|Prob(x%2=0) = 1/2}

これは0から5の整数を一様分布からサンプリングするプログラム (rand(0, 5)) に対して, その値が偶数である確率は1/2だという仕様 (Prob(x%2=0) = 1/2) を与えています。

型主導で検証することの利点として一般に以下が挙げられます

  • 再利用性 : 検証が合成的なのであるプログラムの検証の結果をより大きなプログラムの検証に再利用することができます
  • 網羅性 : 型による検証は数学的な証明に対応するので単体テストなどと違ってカバレッジ100%です
  • 静的 : 検証がプログラムのコンパイル時に行われるので実際にプログラムを実行する必要はありません

既存研究

既存の確率的なプログラム検証のツールに確率的モデル検査器PRISM[1][2] があります。 これは確率的な状態遷移系に対して、悪い状態に到達する確率が十分低いことや良い状態に到達する確率が十分高いことを検証できます。

しかしPRISMを使うためには確率的状態遷移系を書き下す必要があり、人間が読み書きするには不向きでした。 一方で今回のテーマでは検証の対象をプログラムという形で与えることで、関数などのプログラム言語が持つ抽象化の手段を使うことにより検証の対象を人間が読みやすく記述することを可能にしています。

実装

インターンでは確率的なプログラムを記述できる小さなプログラミング言語のインタプリタとその型検査器を実装しました。ソースコードは[3]で公開しています。 この型検査器では型付可能性問題を既存ツールPRISMが扱える妥当性判定問題に帰着させて解いています。

実装したプログラミング言語では例えば次のプログラムの型検査が可能です。

(let a = rand(-10, 10) in
let b = a + rand(0, 10) in
 not (b - a >= 10) /\ ((b + rand(0, 5)) - (a + rand(0, 5)) >= 10))
 : {x:bool | Prob(x) <= 1/10}

このプログラムは“GPSに基づいてスピード違反を検出するシステムが観測誤差によって誤った判断をする確率がしきい値以下”であることの検証を簡単にモデル化したものです。

詳細に説明すると、 a はある時点での自動車の真の座標で b は微小時間後の自動車の真の座標として、 実際にはスピード違反していない (not (b - a >= 10)) のに観測誤差によってスピード違反と判定される ((a + rand(0, 5)) - (b + rand(0, 5)) >= 10) 確率が1/10以下である (Prob(x) <= 1/10) と言っています。

このプログラムと同等な検証をPRISMを使って行うと確率的状態遷移系は 1460 bytes ほどの非直感的なコードになり、確かに実装した言語上の方が簡潔にわかりやすく記述できることがわかります。

実装したプログラミング言語は一様な離散分布からのサンプリングのみを考えており言語機能も大きく制限されているので、現実的な問題を考えるためにはいくつかの機能拡張をする必要があります。 つまり

  • 連続分布からのサンプリング
  • 高階関数
  • 条件付き確率

などです。 考えるべきことはまだまだ残っているので今後も開発を進めていきたいと考えています。

謝辞

インターンが始まった頃は機械学習について全く詳しくなかったのですが、メンターの方が僕にレベルを合わせてかなり初歩的なことから丁寧に説明をしてくださったのでとても助かりました。 メンターの方々以外にも多くの社員さんと交流する機会が用意されており、どの方のお話もとても楽しかったです。 社員の方々だけでなくインターン生にも優秀な方が多くとても刺激的で心地よい夏休みを過ごせました。 皆様に心から感謝いたします。貴重な経験をありがとうございました。

参考文献


おまけ:メンターより

南條さんのメンターを担当したPFNの吉川と酒井です。

PFNは機械学習/深層学習そのものの研究開発のイメージが強いとは思いますが、フレームワークの開発などにおいてはプログラミング言語理論も含め幅広い分野の知識が必要となります。 今回南條さんに取り組んでもらったのも、現時点では非常に簡単なものではありますが、プログラミング言語理論的な知見を確率モデリング等に活かしていけないかと考えての試みです。お互いのバックグラウンドとなる知識の違いから苦労した部分もありましたが、最終的には簡単な言語の設計と実装までこぎつけることができました。

これに限らず、機械学習・深層学習にはプログラミング言語理論などで解決できる課題がまだまだあるのではないかと考えています。それらに興味をお持ちの皆さんも、ぜひ来年のPFNインターンシップへの応募をご検討ください。 また、もちろん中途・新卒の人材募集も通年で行っています。興味のある方はぜひご検討ください!PFNの人材募集のページはこちら https://www.preferred-networks.jp/ja/jobs です。

2018年 PFN夏季インターンシップのコーディング課題公開

楠本充
エンジニア

2018-07-18 11:32:38

PFN 2018夏季インターンシップの選考で用いたコーディング課題を github 上で公開しました。

https://github.com/pfnet/intern-coding-tasks

PFN の楠本です。PFN では毎年8,9月前後に2ヶ月間の長期インターンシップを行っています。コーディング課題はその選考で応募者のプログラミング能力や問題解決能力を見るために出題させて頂いているものです。PFN のインターンシップでは機械学習をはじめとする幅広い分野で応募を行っているため、今年は「機械学習・数理」「バックエンド」「フロントエンド」「プロセッサ/コンパイラ」「Chainer」の5種類のコーディング課題を用意し、応募者の希望するテーマに応じてこのうちのいずれかを解いていただく形にしていました。

今年は去年を大きく上回る数の応募を国内外双方からいただくことができました。それに伴い、インターン生の受け入れ人数も去年よりもさらに拡充する形になりました。

今年の問題は以下のような構成になっています。

  • 機械学習・数理課題: ニューラルネットワークの敵対的入力(Adversarial Example)のアルゴリズムを実装し、性能を報告するためのレポートを記す課題。
  • バックエンド課題: 与えられたログファイルを分析するツールを作る課題。
  • フロントエンド課題: セミナー発表のような動画に対して、発表内容のアノテーションを行うウェブサービスのプロトタイプを作る課題。
  • プロセッサ/コンパイラ課題: 行列積コードの最適化と、行列積回路の設計を行う課題。
  • Chainer 課題: モデルの学習を行うコードを Chainer で実装する課題。

コーディング課題では毎年、出題者が趣向を凝らした問題を作成しています。これらの課題が、興味のある分野を実践的に学ぶための練習問題になれば幸いです。

私は今年の機械学習・数理課題の出題に携わりました。少し余談になりますが、課題を作る際に意識していたことについて書きたいと思います。他の課題ではまた話が違ってくるかもしれませんが、共通しているところもありそうです。

  • 前提知識があまり無くても解けるようにする: PFN では幅広い分野の方々を募集しています。そのため、機械学習そのものの経験や知識が無くても課題を一通り解けるように問題を設定したり、問題文を記述するようにしています。また、特定の知識を持っている人が有利になりすぎるということがあまりないようにも配慮しているつもりです。
  • 実際の研究に近いような設定にする: 深層学習のような分野の研究では「何か良いテーマを見つけて手法を考える → 実装する → 出てきた結果をまとめ、考察を与える」という過程を繰り返しますが、このうち「実装して考察する」という流れを短期間で一通り辿れるような設定にしています。大学の授業の課題のような感じに近いかもしれません。
  • できるだけ興味深いテーマを問う: 機械学習・深層学習の分野では日々研究が進んで面白い結果が次々に出ているので、それに少しでも触れられるような課題を設定しているつもりです。今回の課題である Fast Gradient Signed Method という手法は、シンプルな手法でありながらランダムよりも遥かに強い攻撃手法であるという点で興味深いものだったと思います。
  • 時間が掛かりすぎないようにする: 学業に支障が出ると良くないので、実力が十分あれば1~2日程度で終わるような分量にすることを目標にしています。

提出されたコードは様々な観点から評価するようにしています。単に実装されたコードが正しいのかどうかだけではなく、コードが読みやすいものになっているか、単体テストなどの検証のためのコードが適切に書かれているか、他人がコードの追試をしやすいようになっているか、といった要素も考慮するようにしています。
実験ではコードを書いて動かしたら終わりではなく、手法がどの程度うまくいったのかを評価し、なぜそのような結果になったのかを考察するのが重要になります。特に、複数人で一つの課題に取り組む際にはそれら(評価・考察)を他のチームメンバーに共有することも大事になるでしょう。レポートでは結果の評価と考察ができているかを評価するようにしています。

これらの課題を見て PFN に興味を持っていただけた方は、ぜひ来年のインターンシップへ応募することを検討していただければ幸いです。また、PFN ではフルタイムの採用も通年で行っておりますので、こちらもご検討をよろしくお願いします。

分散深層学習を支える技術:AllReduceアルゴリズム

kfukuda

2018-07-10 11:49:43

本記事は、2017年インターンシップを経て現在はアルバイトとして勤務されている上野さんによる寄稿です

数式が正しく表示されない場合は、こちらのリンクから再読込をお試しください。


みなさんはじめまして。Preferred Networksの2017夏季インターンに参加し、現在アルバイトをしている上野裕一郎です。普段は東京工業大学でHigh-Performance Computingに関する研究を行っており、分散・並列計算に興味があります。

今回は、分散深層学習を行う際に使用されるAllReduceという通信パターンについて調査・実装・評価を行いましたので、それについてご説明いたします。

分散深層学習とは

現在、ディープニューラルネットワークを用いた学習には長い時間がかかることが知られています。そして、様々な種類のモデルや、大量のデータを組み合わせて学習を試すためには、学習にかかる時間を短縮する必要があります。そのために、多数のプロセスに分散して計算を行うことで、学習にかかる時間を短縮することを目的とするのが分散深層学習です。分散深層学習の詳細については、Preferred ResearchのChainerMN 公開に関する記事[1] をご参照ください。

弊社では、深層学習の研究開発や関連技術の迅速な実用化のために、スーパーコンピュータ MN-1 を運用しています。これは、民間企業のプライベートな計算環境としては国内最大級で、NVIDIA(R)製 Tesla(R) P100 GPUを1,024基、Mellanox(R) InfiniBand FDRを搭載しています。これを用いて、ImageNetの画像分類データセットを利用したResNet-50の学習を15分で完了することができました[2]。

しかし、このような多数のGPUを用いて効率的に計算を行うのは多くの困難が伴います。そのうちの1つとして、データ並列型分散深層学習において、GPU同士の通信にかかる時間がボトルネックとなっていることが挙げられます。

分散深層学習では、どのような通信が発生し、なぜ時間がかかるのか、もう少し詳しくご説明します。

分散深層学習におけるAllReduceの重要性

データ並列型分散深層学習では、異なるデータでモデルのパラメータでの損失関数の勾配を求めたあと、プロセス間で勾配の平均を求め、求めた平均を得られた勾配とみなして、モデルに適用を行います。この勾配の平均を求める操作として、多対多の通信を行う集団通信アルゴリズム:AllReduceが用いられています。

このとき、最もよく用いられているのが、NVIDIA社が提供しているNCCL[3] (NVIDIA Collective Communications Library)です。NCCLは、並列・高性能計算の分野の標準であるMPIと比較して、圧倒的に高速な通信を実現しています。前述のImageNet15分実験においても、NCCLが実現する高速通信は、記録の達成には不可欠なものでした。現在、ChainerMNでデータ並列型分散深層学習を実行するにあたっては、NCCLは必須のライブラリとなっています。

さて、NCCLの高い性能の秘密はどこにあるのか、社内でも多くのリサーチャーやエンジニアが興味を持ちました。今回は、実験的にAllReduce通信プログラムを作成し、最適化することによって、NCCLの性能にどこまで迫れるかを試してみました。

AllReduceのアルゴリズム

では、分散深層学習のスループットに大きな影響を与えるAllReduceについて詳しく見ていきます。
AllReduceとは、すべてのプロセスが持っている配列データを集約(Reduce)したうえで、すべてのプロセスがその結果を等しく取得する操作です。まず、総プロセス数を \(P\), そして、それぞれのプロセスには\(1\)から\(P\)までの番号\(p\)がついているとします。そして、各プロセス\(p\)が長さ\(N\)の配列\(A_{p}\)を持っているとしましょう。さらに、プロセスpが持つi番目のデータを \(A_{p,i}\) とします。このとき、最終的に得られる配列を \(B\)とすると、

$$ B_{i}~~=~~A_{1,i}~~Op~~A_{2,i}~~Op~~…~~Op~~A_{P,i} $$

となります。ここで、\(Op\) は2項演算子で、SUM(合計)、MAX/MIN(最大値/最小値)などがよく用いられます。つまり、ここでいう集約(Reduce)とは、配列の要素 \(A_{p,i}\) を、\(p=1,…,P\)までの全プロセスにわたって \(Op\)を用いて畳み込み計算することになります。分散深層学習においては損失関数の勾配の平均が必要であるため、勾配の要素ごとにSUMを用いて合計を計算します。以降では、集約操作に用いる演算はSUMだと仮定します。図1に、\(P=4\), \(N=4\)のAllReduceを実行する模式図を示しています。

図1. AllReduceの模式図

このようなAllReduce処理を実装する方法として、複数の方法が考えられます。

例えば、最も単純な方法として、代表となるプロセスを1つ決め、そこに全ての配列を集め、そのプロセスが全てのReductionを行い、計算結果を全プロセスに配布する、というアルゴリズムを考えることができます。しかし、このアルゴリズムは、プロセス数が増えると代表プロセスの通信量、Reduceの計算量、メモリ使用量がそれに比例して増え、処理量に不均衡があります。

このようにプロセス間の処理量に不均衡が存在しないよう、うまく通信や計算を全てのプロセスに分散させたアルゴリズムが提案されています。代表的なものとして以下のものが挙げられます。

  • Ring-AllReduce
  • Rabenseifnerのアルゴリズム[4]

本稿では、Ring-AllReduceアルゴリズムについて紹介します。NCCLも、Ring-AllReduceを用いて実装されています[5]。

Ring-AllReduce

まず、総プロセス数を\(P\), そして、それぞれのプロセスには\(1\)から\(P\)までの番号がついているとします。そして、各プロセスが図2のようにリングを構成するとしましょう。

図2. リングの構成例

ここで、プロセスpに着目して処理の流れを見ていきます。

まず、プロセスpは、自分の配列をP個に分割し、この分割された配列のp個目をチャンク[p]と表記するとします。そして、プロセスpは、チャンク[p]を次のプロセスp+1に送信します。この時、同時にプロセスp-1はチャンク[p-1]の送信を行っているので、プロセスpはこれを受信することができます(図3)。

図3. 各プロセスpがチャンク[p]を送信する

そして、プロセスpは、受信したチャンクに自分のチャンク[p-1]を足し込み(Reduceし)、計算結果を次のプロセスに転送します(図4)。

図4. 各プロセスがReduce後のチャンク[p-1]を送信する

これをP-1ステップ繰り返すことで、それぞれのプロセスが、Reduce済みのチャンクを1つ手に入れることができます(図5)。

図5. P-1ステップの繰り返しが終了し、Reduce済みのチャンクを1つ手に入れる

言い換えれば、各々のプロセスが、リングの上をまわるチャンクに、自分のチャンクを少しずつ足しこんでいきます。そして、チャンクがリングに沿って全プロセスを1度ずつ訪問した時点で、そのチャンクは、全てのプロセスのチャンクの集約の結果になっています。つまり、最終的には、それぞれのプロセスが、チャンクごとの集約の結果を1つ保持していることになります。

そして、それぞれのプロセスが持つ集約済みチャンクを、さらにリング上で一周回すことで、全てのプロセスが集約済みチャンクを全て取得でき、AllReduceが完了したことになります。

では、このアルゴリズムの通信量を、先程挙げた単純なアルゴリズムと比較してみましょう。

単純なアルゴリズムの場合、代表プロセスが受信するデータの量は、代表プロセスでない全てのプロセスからデータを受信する必要があるので、\((P-1) * N\)となります。その後、代表プロセスでない全てのプロセスにデータを送信する必要があります。これは、Pに対して代表プロセスの受信量が比例しています。

対して、Ring-AllReduceにおける1プロセスあたりの送信(受信)したデータの量は、以下のように求めることができます。最初に、P個に分割した配列をReduceしながらP-1回送信しました。そして、全プロセスにそのReduce済みチャンクを配布するために、P-1回送信しました。よって、1プロセスあたりの送信量はこの合計である \(2(P-1)/P * N\)となり、1プロセスあたりの送信量はPに関して定数であることが分かりました。

よって、2つのアルゴリズムを比べると、Ring-AllReduceは代表プロセスに集中していた送信・受信量を各プロセスにうまく分散させたアルゴリズムになっていることが分かります。このような特徴から、多くのAllReduceの実装でRing-AllReduceアルゴリズムが用いられています。

実装と最適化

Ring-AllReduceのアルゴリズムそのものは、GPU対GPUの通信を行う送受信関数を用いれば、簡単に実装することができます。Baidu社によるbaidu-allreduce[6]は、MPIのライブラリ上で実装済みの MPI_Send, MPI_Recv関数を用いてこれを実現しています。

今回は、MPIではなく、InfiniBandを直接扱うことができるInfiniBand Verbsを用いて実装し、より進んだ最適化を試みました。まず、InfiniBand、GPU、CPUのそれぞれのハードウェアリソースのアイドル時間を可能な限り削減して性能を引き出すために、アルゴリズムの処理をRegistration, Send, Reduction, Receive, Deregistrationなどのステージに分割し、パイプライン化を行っています。ここで、Registration, Deregistrationは、メモリ領域をDMAを用いて転送する際に必要な前処理、後処理を表しています。これらは、MPIを用いて実装すると、 分割してパイプラインに組み込むことができません。
さらに、配列を分割したものであるチャンクを、パイプラインの粒度をより細かくするために更に分割しました。また、メモリ確保は低速であることが知られているので、メモリプールを導入してコストを隠蔽しています。

性能評価

本稿で実装したプロトタイプ(PFN-Proto)の性能を、他の既存実装(詳細は付録に記載)と比較しました。比較対象を、スーパーコンピュータで広く用いられている通信ライブラリであるOpen MPI[7]、Baidu社によるbaidu-allreduce[6]、NVIDIA社によるNCCL[3]です。

なお、今回の我々のプロトタイプ実装は、ノード間通信に焦点を当てて開発しており、ノード内でのGPU間のDMA通信や共有メモリを使った通信最適化は実装されていません。実験では、1ノードに1プロセスを実行する条件でのみ測定しています。また、Open MPIについては、最新シリーズであるバージョン3.xではGPU Directに関係するバグがあり、弊社内ではまだ導入していないため、2.1.3を測定対象としています。

総プロセス数を8として、1ノードに1プロセスを起動することとし、256MBの配列のAllReduceをそれぞれ10回ずつ実行して測定を行いました。実験環境は、MN-1を用いています。実験環境の詳細は付録「実験環境」をご参照ください。図6に性能評価の結果を示します。

図6. AllReduceの実行時間の評価

この棒グラフは実行時間を示しており、低いほうが良い結果を示します。各棒は、それぞれのライブラリの10回の実行時間の中央値、エラーバーは実行時間の95%信頼区間を表しています。各実装の名前の意味、バージョンなどは、付録「比較対象ソフトウェア」をご参照ください。

まず、実行時間の中央値について見てみましょう。一番右側に示されているPFN-Protoが、最も高い性能を示しています。これは、ompi, ompi-cuda, Baidu, NCCLと比較して、それぞれ約82%, 286%, 28%, 1.6% 高速となっています。なお、グラフ上には示されていませんが、10回試行中の最速は、baidu-allreduceで0.097 [s] となりました。

次に、実行時間の分布について見てみましょう。中央値を基準にした実行時間の最大値と最小値は、PFN-Protoが +/-3%、NCCLが+/- 6%以内に収まっています。一方、baidu-allreduceは最大値が中央値の7.5倍という大きな数字となりました。これは、初回実行時に大幅に時間がかかるためです。なお、初回の試行を除いた最大値も中央値の+9.6%となっており、依然としてNCCLおよびPFN-Protoよりもばらつきが大きいことがわかります。

MPI、およびMPIをベースにした実装でこのように性能にばらつきが出る原因としては、MPIが内部で行っているメモリ領域の扱い方に関連していると推測しています。MPIは、InfiniBandによる送受信に必要となるメモリ領域の確保とRegistrationなどを抽象化したインターフェイスを提供しています。これにより、Ring-AllReduceの実装から、それらの発生タイミングを精密に制御することができないため、性能にばらつきが出ると考えられます。

関連研究

今回は、分散深層学習の中のAllReduce操作の高速化についてご説明しました。それ以外にも、分散深層学習の通信部分を高速化する方法として様々なものが考えられています。例えば、

  • 勾配の送受信を1イテレーション遅延させて、Forward, Backwardと通信をオーバーラップする方法(例:ChainerMNにおけるDouble Buffering[8])
  • データの浮動小数点精度を下げることによって通信量を削減する方法(例:ChainerMNにおけるFP16通信[8])
  • 勾配の値の重要度によって送受信するデータを間引いて通信量を削減する方法[9]

などがあります。特に、InfiniBandを持たないような環境(例えばAWS)では、このようなテクニックを用いることで学習を高速化することができます。

まとめ

本記事では、分散深層学習を支える技術である、AllReduceという通信パターン、特にRing-AllReduceという通信アルゴリズムについて説明しました。

そして、このアルゴリズムを実装し、今回の実験環境・実験条件では、NCCLと同等の性能まで最適化することができました。そのためには、InfiniBand Verbsを使用し、徹底的なパイプライン化を行うことが必要であったことが分かりました。これにより、高いハードウェアの性能と並行性を十分に活用することができました。これからも、より高速で、高い信頼性を持つ通信にはどのようなアルゴリズムやチューニングが最適か、調査・開発を進めていきたいと考えています。

ただし、今回の実装は、社内のクラスタを使用して開発・最適化しており、社内のクラスタのみに最適化された実装になっている可能性があります。それに対してNCCLは、幅広い環境で安定して利用できる高速な集団通信ライブラリであり、依然として、NVIDIA製GPUを用いて分散深層学習を行うためには、NCCLを使用するべきであると考えています。

謝辞

最後に、インターンの頃からメンターの方々やチームの方々には手厚いサポートをしていただきながら、大量の計算資源のもとでプロジェクトを進めることができており、非常に貴重な経験をさせていただいています。本当にありがとうございます。


おまけ:メンターより

上野さんのインターンシップメンターを務めています、PFN 大規模分散計算チームの福田(@keisukefukuda) です。今回は、NCCLの高い通信性能はどのように実現されているのだろうか?という疑問からスタートした実験的なプロジェクトでしたが、上野さんの高い技術力によってNCCLに近い性能を出すことに成功しました。

PFNでは、機械学習/深層学習そのものの研究だけでなく、ソフトウェアからハードウェアまで、広い分野で研究開発を進めています。

HPC・高性能計算に興味を持っている学生の皆さんは、ぜひ来年のPFNインターンシップへの応募をご検討ください(このブログ記事の公開時点では、残念ながら2018年の夏季インターンの募集は終わってしまいました)。

また、もちろん中途・新卒の人材募集も通年で行っています。興味のある方はぜひご検討ください!PFNの人材募集のページはこちら https://www.preferred-networks.jp/ja/jobs です。

参考文献

[1] 分散深層学習パッケージ ChainerMN 公開
[2] Akiba, et al., “Extremely Large Minibatch SGD: Training ResNet-50 on ImageNet in 15 Minutes”
[3] NVIDIA Collective Communications Library
[4] Rabenseifner, “Optimization of Collective Reduction Operations”, ICCS 2004
[5] Jeaugey, “Optimized Inter-GPU Collective Operations with NCCL”, GTC 2017
[6] baidu-allreduce
[7] Open MPI
[8] ChainerMNのクラウド環境向け新機能とAWSにおける性能評価
[9] Tsuzuku, et al., “Variance-based Gradient Compression for Efficient Distributed Deep Learning”, In Proceedings of ICLR 2018 (Workshop Track)

付録

比較対象ソフトウェア

Implementation Version Note
MPI (ompi) Open MPI 2.1.3 CPUメモリからCPUメモリへの転送
(他の実装はすべてGPUメモリからGPUメモリへの転送)
CUDA-aware MPI Open MPI 2.1.3
baidu-allreduce (baidu) A customized version of baidu-allreduce, based on commit ID 73c7b7f https://github.com/keisukefukuda/baidu-allreduce
NCCL 2.2.13

実験環境

  • Intel(R) Xeon(R) CPU E5-2667 x 2
  • Mellanox(R) ConnectX(R)-3 InfiniBand FDR (56Gbps) x 2
  • NVIDIA(R) Tesla(R) P100 GPU (with NVIDIA Driver Version 375.20)

Emergence of Locomotion Behaviors in Rich Environment の追試

Manabu Nishiura

2018-06-29 10:48:38

1.内容紹介

はじめまして。PFNでSummer Internship 2017に続き、アルバイトをしている東京大学の西浦です。現在は駒場2キャンパスの先端研で神経科学・循環器系の数理モデルの研究をしています。

さて、2017年の春頃、DeepMindから”Emergence of Locomotion Behaviours in Rich Environments”[1]という論文が公開され、その動画が話題になりました。しかし、この論文では公開されている情報が限られており(深層学習分野でよくあることなのですが)、実験環境の設定、ネットワークの構成や学習に必要なパラメータで不明なものが多く、論文の結果を再現するためには不明な部分を推定するために多くの組み合わせを試す必要がありました。そのため、このような実験の再現は深層学習の実践的な知識と学習のための大規模なリソースが必要とされ、個人で行うのはなかなか難しいと思います。今回はその論文をChainer FamilyのひとつであるChainerRLを利用して再実装し追試を行い、その結果として様々な知見が得られましたのでご報告させていただきます。

Emergence of Locomotion Behaviors in Rich Environmentsの元動画

2.元論文の概要

強化学習のパラダイムは、原理的には単純な報酬のみから複雑な振る舞いを学習することができるようになっています。しかし実際は、意図した振る舞いを学習させるためには、報酬関数を慎重にチューニングすることが一般的です。この論文では、報酬はなるべく直感的な構成で固定してしまい、学習に使う環境(タスク)を様々な種類用意して、エピソードごとにランダムにその環境を変更するというアプローチが採用されています。これにより、様々な環境に対してロバストで、複雑な行動を獲得させようということをモチベーションに実験が行われています。

アルゴリズムとしては、方策勾配法(Policy Gradient)をベースにして、現在の方策に近い方策へと徐々に更新していくProximal Policy Optimization(PPO)[3]を用いています。PPOは論文公開当時では一番性能の良い強化学習のアルゴリズムだったのでそれが採用されていて、論文には同じく性能のよいTrust Reigion Policy Optimization(TRPO)[4]との比較もされています。

3.アルゴリズム、実験手法の解説

前提知識

まず強化学習のフレームワークについて説明します。強化学習では環境とエージェントというのがあり、エージェントが環境に対して行動をし、環境はそれを受けてエージェントに対して観測と報酬を返すという枠組みになっています。エージェントは、報酬に基づいて行動を決定するためのルール「方策(Policy)」を学習していきます。この論文では、ロボットなど連続値の行動を扱いやすい方策勾配法を採用しています。方策勾配法ではActor-Criticモデルという、エージェントをActor(行動器)とCritic(評価器)でモデル化し、例えばそれぞれをニューラルネットワークで表現します。また、エージェントがActor-Criticモデルだと、例えば、Actorのネットワークを決定しているパラメータが方策に該当します。Criticは、現在の方策の元である状態がどれだけの価値を持つかを表す価値関数(ある状態以降の報酬の期待値に割引率をかけたものが一般的)でモデル化されます。

 

実験環境としては、物理エンジンのMuJoCo [2]と強化学習のフレームワークであるOpenAI Gym [5]を用いています。代表的なものとしては、Planar walker(またはWalker2d)と呼ばれる二次元平面内でエージェントに二足歩行を行わせるモデルが挙げられます。Planar walkerの場合、それぞれのエージェントは各関節を曲げるトルクにより行動を表現することになります。また、エージェントが環境から受けとる観測は、大きく内部状態と外部状態に分けられ、各関節の角度、角速度、位置、接触、トルクセンサ情報などを内部情報、地形の高さ情報を外部情報として受け取っています。報酬はPlanar walkerの場合だと以下のように設計されており、基本的には前に進むと報酬がもらえ、それに加えて姿勢のペナルティー(負の報酬)などが含まれています[1]。

Planar walker [4]

今回追試したアプローチでは、方策を決定するネットワークは内部状態と外部状態を別々に処理して最後に合わせて処理して、行動の次元個分、平均と分散の組を指定した正規分布を確率的方策としてを出力する構成になっています。

アルゴリズム

ここで、追試で使ったTRPOとPPOの二つのアルゴリズムについて解説します。まず、ベースになっている方策勾配法は、目的関数(原則としては現在の方策による期待値を用いる)を方策のパラメータに関して微分し、得られた勾配方向にパラメータを更新する方法です。目的関数を計算するために、現在の方策で行動して、その系列データを貯めること(一般化方策反復)を行います。しかし、方策の更新には慎重になる必要があり、一度方策が劣化してしまうと、それから後に得られるサンプル系列も悪化してしまい、持ち直すのが難しくなるという問題があります。

そこでTRPOは、方策の更新に制限をかけながら更新していきます。具体的には、KLダイバージェンスを使って信頼領域(trust region)を定義して、その信頼領域を超えないように、制約条件つきの最適化問題を解くことにより方策のパラメータを更新します。これにより方策の分布として大きな変化を抑制することができて、方策の大きな劣化を防ぐことができます。TRPOが二回微分を計算するので、計算量が多いことを踏まえ、PPOはTRPOの制約条件を目的関数に含めて非厳密化することで、TRPOより単純で軽い計算量でそれなりの性能を発揮するアルゴリズムになっています。

具体的には、方策を \(T * N\) time steps走らせて(Nはスレッドの数)集めた \(s_t\) ,\(a_t\), \(r_t\) を用いて \(A_t\)(アドバンテージ)を計算し、\(L^{CLIP} \)を前の方策と新しい方策の比率を \(\pm \epsilon\) 内にクリップして勾配方向にパラメータを更新していきます。方策のネットワークと価値関数のネットワークでパラメータを共有する(最後の出力層のみそれぞれのパラメータを使う)なら、方策と価値関数のネットワークを独立に更新できないので、目的関数に価値関数の誤差項を加え、探索の幅を増やしたければ、エントロピーボーナスを加えることもあります。(最終的な目的関数は \(L^{CLIP+VF+S} \))ここで登場するアドバンテージとは、収益(報酬の期待値)からベースラインを引いたもので、勾配の推定値の分散を減らすためのテクニックです。それぞれの計算式を以下に示します[3]。

元論文ではPPOをさらに分散版にしたものを使っています。追試としては、PPOで方策ネットワークと状態価値関数にLSTMを含んだものと、TRPOを用いましたが、1スレッドの場合では、TRPOの方がかなり性能がよかったです。したがって、以下の結果は全てChainerRLのTRPOで学習させた結果となります。

実験手法

追試としては2通りの環境で訓練しました。一つ目は元論文の動画に近い3種類のタスクがある環境で、もう一つは地形の凸凹の状態がランダムに変わるものです。

元論文に近い環境では、Planar Walkerを①箱を飛び越えるタスク、②穴を飛び越えるタスク、③浮いている板を避けるタスクの3種類の環境で順番に訓練した後、3種類の環境(タスク)がランダムにエピソードごとに切り替わる環境で訓練します。

地形の凸凹の状態がランダムに変わる環境では、エピソードごとにすべての地形が変わる中で訓練します。

4.結果

学習し始めのエピソードごとにランダムに地形が変わる中で試行錯誤している様子

学習後歩いている動画

こちらでは、学習初期段階からランダムに地形を変更していたためか、とにかく脚を高く上げて、どんな障害物でも越えられるような動きになってしまったようです。

動画に示した歩行行動を獲得するまでの学習曲線を上に示します。10,000ステップごとに10エピソード走らせて評価を行なっており、青のrewardは10エピソードの平均累積報酬で、上下の灰色の線は10エピソード内での最小値最大値になっています。200万ステップほどで収束していることが分かります。

 

元論文に近い環境で学習後歩いている様子

障害物によって頭を下げたり、ジャンプする高さが変わったり、動きが変わっていることが見て取れます。一つ目と二つ目の動画ではPlanar walkerの関節の減速比のパラメータが違っていて、このような微妙な差でも獲得される動きに違いが出てしまいます。

 動画に示した歩行行動を獲得するまでの学習曲線を上に示します。歩く動作は120万ステップほど、穴を飛び越える動作は800万ステップほど、浮いている板を避ける動作は400万ステップほどで学習が収束していることが分かります。

タスクによって報酬の平均がそこまで変動していないものもあり、歩く動作を獲得した状態から箱を飛び越える動作の獲得にはそれほど学習が必要ではないが、箱を飛び越える動作を獲得した状態から穴を飛び越える動作を獲得するのと、箱を飛び越える動作を獲得した状態から浮いている板を避ける動作を獲得するためにはかなり学習が必要であることが分かります。

元論文では適切に実験設定が考えられていて、カリキュラムラーニングになっていたために、タスクに応じて行動をうまく切り替えられるようになっていましたが、ただ単に地形やタスクをランダムに変えるだけでは、どんな環境にも対応するような方策を獲得してしまうようです。

5.考察

問題点の一つに、初期条件を注意深く設定しないと意図した学習結果になりづらいという問題があります。今回の場合も初期の状態変数の分散や、地面とMuJoCoのモデル(Planar walkerなど)との高さ方向の相対的な位置は学習の様子をみながら調整することが必要でした。具体的に注意した点としては以下のような点が挙げられます。

  • ある程度初期状態に分散がないと、分散の範囲で実現できる行動になってしまう。(逆に分散が大きすぎても学習がうまく進まないことがある)
  • 環境をリセットした時に何ステップ分フレームをスキップしてから指令を出し始めるか、によって獲得されるモーションが変わってくる。(例えばMuJoCo環境内で、完全に地に足が着いてから指令値を出すようにした、など)
  • 歩行を獲得させる場合、学習の過程で最初に獲得されるのはその場に立っているという方策なので、初期位置の周辺はなるべく平らな方がよさそう。

その他にも、下記の記事[6]に現状の深層強化学習の課題はよくまとまっているので、ぜひ読んでいただきたいです。(方策を更新していくために特定のアルゴリズムを採用しても、報酬関数、方策を表現するネットワークのパラメータなどは自分で任意に決定する必要があり、設定する報酬によって獲得される方策がかなり変わってしまうという問題など。)

 

失敗例の動画

けんけんを獲得している動画(初期化した時の相対的な高さの問題で、片足を前に出す方策を獲得できなかった例、初期状態の分散はうまくいった例と同じ)

6.PFNインターンの感想

ある仮説を検証するのに、「ある実験系でやってみて上手く行かなければもっと単純化した系でやってみる。」という、研究の基礎的なプロセスの体験ができたのはとてもよかったです。また、ロボティクス関係の様々な研究を知ることができ、そこで研究している人たちとの繋がりができたのは一番大きな収穫だったかもしれません。最後に、情報交換の重要性も強く意識することができました。有名なライブラリやパッケージの使い方(インストールで苦戦するものなど)や、こういう手法を試したけどいまいちだった、ハイパーパラメータの情報など、公開されていなけど実験をしていく中では欠かせない情報などを共有できる環境が、とてもありがたいなと感じました。

元論文の情報が結構少なく、なかなか学習が進まず進捗が出ずに精神的に辛い時期もありましたが、様々な方に積極的に相談するようになってからは比較的スムーズに乗り切ることができたように思います。最後になりましたが、ご指導いただいてるメンターの皆様をはじめ、社員の方々に感謝を表して報告を終わらせていただきたいと思います。

参考文献

[1] “Emergence of Locomotion Behaviours in Rich Environment” https://arxiv.org/abs/1707.02286v2

[2] MuJoCo advanced physics simulation http://mujoco.org/

[3] “Proximal Policy Optimization Algorithms” https://arxiv.org/abs/1707.06347

[4] “Trust Reigion Policy Optimization” https://arxiv.org/abs/1502.05477v5

[5] OpenAI Gym https://gym.openai.com/docs/

[6] “Deep Reinforcement Learning Doesn’t Work Yet” https://www.alexirpan.com/2018/02/14/rl-hard.html

 

実センサを搭載したロボットカーの深層強化学習による自律制御

Megumi Miyashita

2017-12-12 12:24:19

はじめに

はじめまして。PFNで夏季インターンに続き、アルバイトをしている宮下恵です。普段は東京農工大学大学院で強化学習に関する研究をしており、ものづくりやロボットに興味があります。

「実センサを搭載したロボットカーの深層強化学習による自律制御」について報告させていただきます。

 

続きを読む »

2017年 PFN夏季インターンシップのコーディング課題公開

Kosuke Nakago

2017-07-27 09:54:00

* English blog is also written here.

PFNでは毎年8、9月に学生の方を対象とした2カ月間の長期インターンシップを実施しています。

今年も2017年のPFN 夏季インターンを募集したところ多数の応募をいただき、先日無事に選考が終了しました。

PFN 2017夏季 インターン募集

それに伴い、今回PFNのインターンコーディング課題をgithub上で公開しました。

https://github.com/pfnet/intern-coding-tasks

 

続きを読む »

深層強化学習による自動駐車の実装

Shiba Shintaro

2017-03-22 19:15:13

初めまして! PFN でアルバイトをさせてもらっている芝慎太朗です。普段は東京大学大学院で行動神経科学の研究をしています。僕が去年取り組んでいた、「車が自ら駐車場に向かい停止する」自動駐車プロジェクトについて報告します。まずはこちらのアニメーションをご覧ください。(アニメーションがうまく再生されない場合は画像をクリックしてください)

We implemented self-driving car that parks itself using deep reinforcement learning. The English slide is available at SlideShare!

背景

深層強化学習は、2015年から非常に注目され始めた人工知能技術であり、深層学習と強化学習を組み合わせたものです。深層強化学習によって、それまでできなかったような複雑なタスクにおいてもコンピューターが人を上回り始めました。プロ棋士を破ったことで一躍話題になった Google DeepMind による囲碁の人工知能 AlphaGo もこの技術を使っています。最近では スマッシュブラザーズにおいても威力を発揮し 話題になりました。

深層強化学習は制御タスクとの相性がよく、実際に PFN でもぶつからない車の自動運転ドローンの制御などに成功してきました。

PFN が CES 2016 で展示した自動運転(参照)では、アルゴリズムとして深層強化学習ブームの火付け役となった Deep Q Network(以下DQN)を用いています [Mnih et al., 2015]。ニューラルネットワークへの入力は、LIDAR(wikipediaによる解説)を模した近接物への距離と角度センサー、直前の行動、現在の車のスピードとステアリング(ハンドルの曲がり具合)でした。

しかし自動運転技術を現実に応用することを考えると、一般に距離センサーよりもカメラの方が安価という特徴があります。一方で、距離の計算が必要になるためカメラ画像の方が制御は難しくなると考えられます。実際、つい最近も ブラウザ上で動作するような簡単な自動運転デモ が公開されたばかりですが、これも距離センサーを使用しており、使用しているニューラルネットは3層程度の簡易なものです。
距離センサー・カメラそれぞれに得意・不得意な状況や利点・欠点があるので一概にどちらを用いるべきとは言えませんが、いずれにせよ、距離センサーに頼らずカメラ画像のみを用いて車を制御するようなアルゴリズムの研究開発は非常に重要です。

本プロジェクト

このプロジェクトでは、距離センサーではなく、車に取り付けられたカメラによる主観的な画像の入力によってend-to-endのアルゴリズムで車を制御できないか、ということに挑戦しました。具体的なタスクとして選んだのは駐車です。すなわち、車を駐車スペースに移動して停止させます。

アルゴリズムとしては DQN の改善版である Double DQN を使用しました。Double DQN は行動価値の見積もり値である Q 値の過大評価を防ぎ、ニューラルネットの発散を防ぐことで学習を安定させるという特徴があります [Hasselt et al., 2015]。詳しくは解説スライド(この投稿の最後にリンクが貼ってあります)や元論文をご覧ください。

まずは環境の定義です。今回は実機や既存のシミュレータを使用せず、簡単な車の物理シミュレータを自分で実装しました。このシミュレータはアクセル、ブレーキ、ハンドルの曲がり具合を受け取り、牽引力、空気抵抗、転がり抵抗、遠心力、制動力、コーナリング力を計算し、車の位置、速度、加速度を更新します。車や駐車スペースの大きさと、車が探索できる地面の範囲なども定義しました。次の図は、シミュレーションされた環境を上から見た俯瞰画像です。黒い長方形が駐車スペース、赤と黄色の長方形が車(黄色が前)になります。


次にエージェントへの入出力を定義します。エージェントは環境の状態を入力として受け取り、アルゴリズムにしたがって適切な行動を選択します。現実世界に例えるなら車に乗っている人に相当するでしょう。行動はアクセル、ブレーキ、ハンドルを左右に曲げることの組み合わせで全部で9種類用意しました。状態としては、環境を車から見た主観画像と、現在の車のスピードとステアリング(ハンドルの曲がり具合)を使用しました。つまり、車の現在位置や駐車スペースまでの距離を直接知ることはできません。

主観画像は、車を中心に3方向または4方向に設置されたカメラ画像を用意し、車の周りをぐるりと見渡せるようにします。次の画像はカメラが4台の場合の主観画像です。画像の大きさはニューラルネットに入力する直前で 80 x 80 に縮小します。わかりやすいように中心に先ほどと同様の俯瞰画像を載せました。


エージェントは、画像の入力に合わせて適切な行動を選択し、車を駐車スペースに導いてそこで停車することが求められます。状態がカメラ台数分の画像と、画像でないパラメータ(現在の車のスピードとステアリング)からなるため、ニューラルネットの構造を工夫して以下のようにしました。この図はカメラが3台の場合に使用されたニューラルネットワークです。図中の Convolution とは、画像を処理するための畳み込みニューラルネットを示します。


最後に報酬を定義しておきます。「車が駐車スペースに向かい、その中で停止する」、すなわち「車ができるだけ長く駐車スペースの内側にいる」ことを学習するような報酬の与え方を考えます。いろいろな設定を試しましたが、最終的に

  • 車が駐車スペースの内側にいる場合、+1
  • 車が地面の外にいる場合、-1
  • その他の場合、0.01 – 0.01 * ゴールまでの距離

というふうに設定してみました。
その他の細かい設定や、他に試した報酬の設計などは末尾のスライドをご覧ください。

結果

GeForce GTX TITAN X 上で約一週間ほど学習を回し続けた結果、冒頭で示したように、車が自動で駐車スペースに向かい停止するように学習できました。次のアニメーションは冒頭と同じもので、左が車の軌跡、右が実際にニューラルネットワークに入力された画像です。

しかしながらやはりタスクの難しさもあって、このまま学習を続けていくと車が地面をぐるぐる回り続けたり、パラメタによっては学習途中でニューラルネットの出力が発散してしまったりという場合もありました。こちらも詳細はスライドを見ていただければと思います。


考察

深層強化学習を用いて、主観画像の入力から自動駐車を学習できました。画像を入力して車を制御するのは、距離や角度のセンサーよりも一段階難しいタスクです。実は、このプロジェクトも距離などを入力にして学習させるところから始めました。距離を直接入力した場合には安定してすぐに学習できたものの、主観画像では Q 値の発散や、うねうねと動き続ける車が誕生したりとなかなか安定しませんでした。

原因として考えられることの1つに、畳み込み層で車や駐車スペースの場所がうまく検出しきれていない可能性があります。先にCNNから位置を回帰するような事前学習をおこなってその重みを初期値として使うことや、一度 CNN 部分の出力を可視化してみることも有用でしょう。

また学習を安定させるために、アルゴリズムの変更も効果的かもしれません。例えば A3C [Mnih et al., 2016] や TRPO [Schulman et al., 2016] を使ってみたり、モンテカルロ法と組み合わせた学習などは試す価値があると考えられます。

実際にはいきなり始めから主観画像を入力したわけではなく、上で少し述べたように、簡単なタスクから徐々に難しくしていました。また、報酬の設計を変更しつつ、駐車スペースの位置や車の初期設定を変えながらカリキュラム学習をしたりと細かい実験を試しています。これらの詳細が知りたい方は上記のスライドを見ていただければと思います。

まとめ

本プロジェクトの結果はまだ様々な状況で完全に対応できるものではありませんが、深層強化学習によってカメラ画像のみで自動駐車が実装できる可能性を示したものだと言えます。今後の方向性としては、学習アルゴリズムを変更して学習を安定させたいです。シミュレーションだけではなく、実機でも実現できれば非常に面白いと思います。

僕は現在も他のプロジェクトに取り組みながらアルバイトを続けています。初めからプログラミングや強化学習ができたわけではなく、自分で勉強しつつ、わからないところをメンターに教えていただきながら、大変恵まれた環境で進めることができたプロジェクトでした。学生の皆さんも興味があればアルバイトやインターンに積極的に飛び込んでいってみてはいかがでしょうか。