Chainer Chemistryの大規模グラフのタスクへの拡張

Kosuke Nakago

2019-10-01 13:09:08

本記事は、2019年インターンシップで勤務した 阿部健信 さんによる寄稿です。

こんにちは。2019年夏季インターンに参加した東京大学の阿部健信です。「Chainer Chemistryの大規模グラフのタスクへの拡張」というテーマで取り組んだ内容を説明させていただきます。インターン内容のスライドはこちらにアップロードされています。

PFN Summer Internship 2019 / Kenshin Abe: Extension of Chainer-Chemistry for Large and Sparse Graph from Preferred Networks

 

TLDR;

  • Chainer Chemistryで大規模グラフのデータを扱えるようにしました。
  • convolution演算を\( O(V^2) \)から\( O(E) \)にしました。
  • メモリ使用量も抑えて、PyTorch Geometricでは動かないRedditデータセット(23万頂点, 1100万辺)を16GBのsingle GPU上で学習できるようにしました。

 

はじめに

 

graph convolution [1]

画像に対する2D ConvolutionとGraph Convolutionの比較 [1]

入力としてグラフを受け取ることのできる、Graph Neural Network(GNN)という分野が近年注目を集めています。
その注目の高まりから、PyTorch Geometric [2]やDeep Graph Library (DGL) [3]といった高機能で最適化されたGNNライブラリの開発が盛んに進められています。

Chainer Chemistryは、PFNが開発しているGNNのオープンソースのライブラリです。
名前からも分かるとおり、もともと分子など化学データへの適用を目的として作られたもので、qm9などの化学データセットが手厚くサポートされています。一方、他にGNNの研究でよく用いられるSNSなどのネットワークデータのサポートはなされていませんでした。

 

課題内容

今回のインターンのタスクは、Chainer Chemistryでネットワークデータのサポートを行うことです。そのために、大きく以下の2つの内容を行いました。

1. node classificationのサポート
化学分子データなどたくさんの小さなグラフのデータセットに対してGNNは、graph classification/regressionといった、グラフ全体の性質を学習するのに用いられます。
一方、巨大なネットワークデータに対しては、1つのグラフを入力として各頂点ラベルの分類を行うといった異なるタスクに用いられる事が多いです。
[4]で提案されているようなsemi-supervised node classificationへの対応を行いました。
具体的なフレームワークの違いはスライドをご参照ください。

2. 巨大でsparseなグラフのためのGNNの効率的な実装
こちらが今回のインターン内容のメインで、巨大なグラフを動かすためには必要不可欠な内容でした。
以下、\( V \) 個の頂点、\( E \)個の辺からなるグラフを考えます。
Message passingにもとづくGNNでは、各頂点に対して近傍の頂点の特徴量のaggregationの操作を行います。このaggregationの関数はpermutation invariantな様々な関数が用いられ、例えばよく使われるsumの場合は以下の式になります。
\( H’ = AH \)
(\( H \): 頂点の特徴量行列, \( A \): 隣接行列, \( H’ \): aggregateされた特徴量)

既存の実装は全てこの行列演算に基づくものでしたが、これは2つ問題点があります。
1つめは、グラフが疎な際にメモリ的にも実行時間的にも無駄が生じてしまうことです。
2つめは、batch化の際のゼロパディングのオーバーヘッドです。

これらの問題を解決するために、辺の情報を密な隣接行列ではなく、疎なデータ形式で持たせるという事が考えられます。今回のインターンでは、こちらのレポジトリでsparse patternとして紹介されているデータの持ち方を新たに実装しました。
これは辺の情報を\( [2, E] \)のサイズの行列で持つ手法で、PyTorch Geometricでも採用されています。

Sparse patternでは、scatter演算と呼ばれる命令を用いることでaggregation部分の計算量を\( O(E) \)で行うことができます。
またbatch化の際に、複数のグラフを全体として大きな1つのグラフとしてみなすことによってゼロパディングのオーバーヘッド完全になくすことができます。
こちらも、より詳細な手法が知りたい方はスライドをご覧ください。

 

結果

行列演算による既存実装と、sparse patternによる実装の速度比較は以下のようになりました。
まず、3312頂点、4660辺の疎なネットワークグラフに対しては、CPUでは50倍以上、行列演算との相性が良いGPU上でも2倍以上の速度改善が見られました。
また、1つ予想外だったのは、最大でも38頂点という比較的小さなグラフからなる化学データセットに対してもGPU上でも1.5倍程度の速度改善が見られたことです。
これには、バッチ化のオーバーヘッドをなくす工夫が効いていると考えられます。

sparse patternはグラフのconvolution演算に特化して実装されているため速いもののメモリ使用量にまだ無駄があり、Redditデータセット(23万頂点, 1100万辺)を動かすことはできませんでした。
これについては、ChainerのサポートしているCooMatrix演算によるモデルを用いたところsingle GPU (16GB)で動かすことができました。

これまで触れた、既存の隣接行列・sparse pattern・CooMatrixの3パターンについてまとめると、グラフが疎であったりバッチ化のオーバーヘッドが大きかったりすれば基本的にsparse patternが早く、それではメモリが足りない場合はCooMatrixを使うとよい、という結果になりました。
この結果を踏まえて、3つのパターンを場合に応じて使い分けられるように実装しています。
特に、現状のPyTorch Geometricでは動かすことができないredditなどの超巨大なグラフを動かせるという点は、Chainer Chemistryを使うモチベーションの1つになると思います。
新しいモデルを自分で実装したいときに、ChainerでサポートされているCooMatrix演算を普通の行列演算と同じようなインターフェースで直感的に使えるのも魅力です。

 

 

まとめ

今回の成果はChainer Chemistryにマージされています。新しい実装方針に対応しているモデルはまだ多くはありませんが、これからどんどん対応していく予定です。
exampleのコードを動かすことで簡単に巨大グラフ上での学習ができるようになっているので、ぜひ試してみてください。

 

参考資料

[1] https://arxiv.org/pdf/1901.00596.pdf
[2] https://rlgm.github.io/papers/2.pdf
[3] https://rlgm.github.io/papers/49.pdf
[4] https://arxiv.org/pdf/1609.02907.pdf

 

CuPy カーネル融合の拡張

Daisuke Nishino

2019-09-27 14:44:40

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


2019年度夏季インターンのJoeです。この度インターンプロジェクトとしてCuPyのカーネル融合の拡張に取り組み、既存のカーネル融合の適用範囲を大幅に拡張しました。さらにその応用として、ResNet50のバッチ正規化においてCPU実行時間を30%ほど、GPU実行時間を(入力サイズに大きく依存しますがおおよそ)70%ほど削減することに成功しましたので、その取り組みをご紹介します。

背景

CuPyはNumPyと同じAPIを提供するPythonのライブラリで、CUDAを用いて演算を高速に行います。具体的には、行列・ベクトルの要素ごとの演算や、リダクションと呼ばれる、演算によって配列の次元が落ちる演算(たとえばcupy.sum)など、GPUが得意とする計算を高速に行うことができます。

さて、CuPyのGPU演算は強力ですが、CPUからGPUカーネルを呼び出す際には、GPU内で実際に行われる処理によらずおおよそ10 μsほどのオーバーヘッドがCPU側にかかってしまいます。cupy.addcupy.mulのような演算が呼ばれるたびにGPUカーネルを呼び出していては、無視できない量のオーバーヘッドが発生してしまいます。

そこで、いくつかの演算を融合したCUDAコードを実行時に動的に生成することにより、GPUカーネルの呼び出しを減らすことによる高速化が重要となります。この技術をカーネル融合といいます。詳しくは後述しますが、要素ごとの演算を組み合わせた関数やリダクション演算を一度まで含む関数に対するカーネル融合は現在のCuPyにもすでに実装されています。

https://docs-cupy.chainer.org/en/v6.4.0/reference/generated/cupy.fuse.html

カーネル融合で行っている処理を具体的に説明するために、以下のPythonで書かれた関数に配列(cupy.ndarray)を引数に与えて実行したときに、カーネル融合をしない場合とする場合に生成されるCUDAコードを比較してみます。


def f(x):
    return x + x * x

カーネル融合をしない場合

このとき掛け算と足し算の両方の呼び出しでCUDAコードが生成され、2度のカーネル呼び出しが発生します。

具体的には以下のようなコードが生成され、関数single_op_mulsingle_op_addがそれぞれ実行されます。


__device__ void mul_element(int &src1, int &src2, int &dst) {
    dst = src1 * src2;
}

__global__ void single_op_mul(Array& in, Array& out) {
    int a = in[tid], b;
    mul_element(a, a, b);
    out[tid] = b;
}

__device__ void add_element(int &src1, int &src2, int &dst) {
    dst = src1 + src2;
}

__global__ void single_op_add(Array& in1, Array& in2, Array& out) {
    int a = in1[tid], b = in2[tid], c;
    add_element(a, b, c);
    out[tid] = c;
}

カーネル融合をする場合

この場合、2つの演算は1つの関数にまとめられて、以下のように生成される関数fusedが呼ばれ、カーネル呼び出しは1回で済みます。


__device__ void add_element(int &src1, int &src2, int &dst);

__device __ void mul_element(int &src1, int &src2, int &dst);

__global__ void fused(Array& in, Array& out) {
    int a = x[tid], b, c;
    mul_element(a, a, b);
    add_element(a, b, c);
    out[tid] = c;
}

このとき、カーネル呼び出しの回数が1回に減るのでCPU時間が短縮されます。さらに、x[tid]部分はグローバルな配列にアクセスしていて、GPU側のボトルネックになりがちですが、処理をまとめることで、こうしたグローバル領域のアクセスの回数を減らすことができ、GPU側の高速化にも繋がります。

要素ごとの演算とリダクション演算のカーネル融合

既存のカーネル融合は要素ごとの演算だけではなく、一度までリダクションを含む関数ならば融合することができます。上述した例に示したような要素ごとの演算を組み合わせた関数に対するカーネル融合は比較的イメージしやすく、生成するCUDAコードもcupy.addcupy.mulに相当する演算をつなげるだけでいいので簡単ですが、要素ごとの演算とリダクション演算を融合しようとすると話は少しややこしくなります。要素ごとの演算のカーネル融合ではGPUの各スレッドが特定の位置の要素を独立に扱っていましたが、リダクション演算では、各スレッドは適切に同期されながらシェアードメモリに読み書きを行い、演算を処理します。

上の図は、既存のカーネル融合で、要素ごとの演算とリダクション演算からなる関数を融合した場合にGPUで行われる処理を表したものです。ここで、リダクション前の演算はすべてリダクションの入力と同じサイズ(正しくは、cupy.ndarrayshapeのこと。以下同様)をもち、 リダクション後の演算はすべてリダクションの出力と同じサイズをもちます。逆にこのような制約のもとで表せない関数には既存のカーネル融合を適用できません。

このような、リダクションを一度行う関数を融合することは、先程説明したような要素ごとの演算のみからなる関数を融合する場合よりは難しいですが、それでも元のリダクション演算の前後に、要素ごとの演算を織り込むだけで実現することができます。

課題

今回のインターンの課題は、カーネル融合で扱える関数の範囲を広げ、要素ごとの演算とリダクションからなる関数ならなんでも融合できるようにする、というものでした。実際既存のカーネル融合において、リダクションが一度までというのは大きな制約であり、例えば平均や分散の計算を伴うバッチ正規化の関数を融合することはできませんでした。バッチ正規化はResNet50などで何度も実行される関数であり、特にカーネル融合の効果が期待される処理でした。

取り組んだこと

リダクションを二度以上含む関数の融合は、一見リダクションを一度だけ含む関数の融合方法を簡単に拡張するだけで実現できるように思えますが、このニ者の間には大きな違いがあります。というのも、複数回リダクションが行われるとき、一度前のリダクションの結果を一時的にGPUのグローバル領域に格納する必要が生まれます。同じサイズの要素ごとの演算のみだと、各スレッドは配列の特定の要素を見続けるので、演算結果の変数をスレッドのローカル変数に保持しておくことができます(リダクション演算が一度だけの場合、出力用配列にそのまま保存するので問題ありません)。しかし、配列のサイズが演算間で変化するとき、スレッドが担当する要素がずれるため、一度結果をグローバル(スレッド間で共通してアクセスできる位置)に保存してやる必要があるのです。具体的には新たな空の配列をグローバル領域に確保しておき、それを使います。

カーネル融合の処理の流れ

具体的なアルゴリズムを説明する前に、カーネル融合の処理の流れについて整理しておきます。

各々の部分の詳細な説明は後述しますが、カーネル融合の処理は大まかに、解析パートと実行時パートに別れます。解析パートでは、CUDAコードを生成するために必要な情報を解析し、CUDAコードの最適化を行います。解析パートは同様な引数の組み合わせに対しては一度だけ実行されることを想定しています。一方、実行時パートは、毎回の関数呼び出しで実行されるパートのことを指します。ここでは、配列の次元圧縮とよばれる実行時最適化を行い、解析パートで得られた情報から実際にCUDAコードを生成し、コンパイルしてカーネルを呼び出します。何度も呼び出されることが想定される関数の場合、関数呼び出しあたりの平均的なCPUの処理時間は、この実行時パートの処理時間にかかっています。それでは、解析パートおよび実行時パートで行っていることを順に説明していきます。

解析パート

サイズの抽象化と制約生成

多段階のリダクションを実現する上で重要なことは、サイズが異なる演算が発生するたびに一時変数をグローバル領域に保存してやることでした。そうした一時変数のメモリを割り当ててやるためには、カーネル呼び出しの直前にサイズを決定してやる必要があります。なぜならば、同一の関数が異なるサイズの入力で繰り返し呼ばれる可能性があるからです。サイズが異なる入力が来るたびにPython関数を解析し直すのは非常に高コストなので、入力の配列のサイズが変わった場合にも同じコードを使えるように変数のサイズ情報を抽象化してを保存したいです。

サイズを抽象化して保存するためには、まず関数の引数で渡される配列のサイズを抽象化して保持します。たとえば、三次元配列xのサイズを(x0, x1, x2)のようにして保持します。これらの抽象化したサイズをもとに、演算を順に追っていき、一時変数の抽象的なサイズを決定します。こうした演算を追う過程で、演算がただしく成立するために必要な、サイズ間の制約が発生します。たとえば、(x0, x1, x2)のサイズの配列と、(y0, y1)のサイズの配列の要素ごとの演算を行うには、後者をブロードキャストする必要があり、このとき、x1, x2, y0およびy1がいずれも1でないとすると、y0 == x1かつy1 == x2がサイズ間の制約となります。これらの制約は関数の解析時に順次保存され、2度目以降の関数呼び出しの際に、与えられた引数のサイズが保存された制約を満たすならば、以前に解析した結果およびコードを使い回すことができます。

CUDAコードの生成

CUDAコードを生成する上での基本的なアイデアは、本稿の初めで説明した、要素ごとの演算のみからなる関数のカーネル融合とほとんど同じです。すなわち、関数内に登場するそれぞれの演算を呼び出し順に記録し、それをつなげて一つのCUDAコードにします。リダクション演算が続いたり、サイズが異なる要素ごとの演算が連続したりするときは、スレッド間で同期をとる必要が生まれますが、基本的にはそれぞれの演算を順につなげたコードを生成すればよいです。

CUDAコードの最適化

さて、ここまでの説明だけだと、カーネル融合が簡単なものに思えるかもしれません。実際、GPUの実行時間を考慮しないならば、演算ごとにサブルーチンを生成し、そのサブルーチンをすべて順につなげればひとつのCUDAコードが完成します。しかし、このままだと本当にGPUを呼び出すための10 μs程度のCPU側の高速化しかなされません。カーネル融合ではCPUのオーバーヘッドをへらすだけではなく、GPUコードの無駄な処理を省くことでGPU側の高速化をも期待することができます。

さて、各演算を順に結合しただけのCUDAコードは無駄な処理を多く含みます。たとえば直前の演算で結果をグローバルな配列に格納し、次の演算でまた同じ要素をグローバルな配列から読み出すのは明らかに無駄です。こうしたケースでは演算結果をスレッドごとのローカル変数に記録してやると大きな高速化に繋がります。

たとえば、愚直に生成したCUDAコード内で以下のような部分があったとします。


tmp[tid] = a;

// ここまで一つの演算に対応。変数aを出力として一時変数に格納
// ここから新しい演算が開始。変数aを新しい入力として一時変数から読み出す

int b = tmp[tid];

このとき、配列tmpが一時変数で、しかもここでしかアクセスされない変数であるならば、


int b = a;

と処理を短縮してやることができます。GPU演算で各スレッドが担当する演算は非常に軽量であることが多いため、このようにグローバル配列へのメモリアクセスを削減してやるだけでも大きな高速化に繋がります。

今回、要素ごとの演算間のみならず、リダクション演算が混じる場合にもこうしたグローバルなメモリアクセスを減らす最適化を行いました。他にもスレッド同期の削減など非常に多様な最適化を試行錯誤し、結果として、従来のカーネル融合を適用できる演算については、ほとんど劣ることがないレベルまでに最適化がなされています。また、高速化とは直接関係ないですが、一時変数の生存解析をすることにより、メモリを共有できる変数はメモリを共有することで、実行時の消費メモリを抑える最適化も実装されています。

実行時パート

配列の次元圧縮

詳細な説明は省きますが、多次元配列の要素にアクセスするとき、一次元配列の要素アクセスよりも時間がかかります。そこで、配列のデータ領域がメモリ上で連続していて低次元配列だとみなせるときに、要素アクセスをより単純に行うための実行時最適化を行います。完全なCUDAコードを生成するためにはこの最適化後の次元を知る必要があるため、完全なコードの生成およびコンパイルは実行時に行われます。CUDAコードのコンパイルはCPU時間に含まれますが、キャッシュされるので一般に高速であり、次元圧縮によるGPU実行時間の削減のほうが効果が大きいため、この方式を採用しています。

実験結果

ResNet50のバッチ正規化部分のコードを融合し、CPU時間とGPU時間を比較しました。実験を行った環境は以下のとおりです。CUDA: 10.1, GCC: 5.4.0 GPU: Tesla P100. また、ResNet50でバッチ正規化される配列のサイズは様々ですが、今回はその中の一つである(32,256,56,56)を採用しました。これは縦横56×56の画像を256チャネル分、32枚を正規化する処理に対応し、軸(0,2,3)について正規化をすることで、出力のサイズは(256,)になります。

比較対象は、カーネル融合をせずにそのまま呼び出した場合(naive)と、実際に採用されている実装である、要素ごとの演算部分だけを融合した実装(custom kernel)です。今回実装したカーネル融合(new fusion)はCPU時間、GPU時間の両方の削減に成功しました。

CPU時間は、実行時の配列のサイズに依存せずほぼ一定の割合短縮されました。また、GPU時間についても、従来のボトルネックであった、分散計算時の余分なメモリアクセスを潰すことができたため大幅に短縮されました。

まとめ

今回のインターンでは、既存のカーネル融合を拡張し、複数回のリダクション演算が含まれる場合にも対応し、無事高速化を達成できました。複数回のリダクション演算にも対応させたカーネル融合を実現する上での理論的な大枠はかなりシンプルで、一時変数に多くの情報(もっとも重要なものは抽象的なサイズ情報)を記録させながら演算をたどれば実現できるのですが、そうして生成されたコードは既存のカーネルで生成されるコードに比べ極めて冗長で、最適化を十分に施さない限り高速化が見込めない、という点が大変でした。アルゴリズムの大枠は序盤から見えていましたが、実際にベンチマークを更新したのはインターン終了直前という形になってしまいました。

アプリケーションに新しい機能を追加をする開発と違い、高速化を目指すための機能追加は、高速化を実現できて初めて世に広まるものなので、プロジェクト自体が成功するかどうかはインターン後半までかなり心配していましたが、無事に高速化を実現できてよかったです。

今回のインターンを通して、頼りになるメンター・副メンターとともにこのような挑戦的なプロジェクトに携われてよかったです。

ベイズ最適化を用いた高次元ブラックボックス最適化手法の検証

Yuhei Otomo

2019-09-27 14:12:18

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


概要

2019年PFN夏季インターンに参加していた森 雄人です. 本インターンでは高次元空間中のベイズ最適化問題について, 実装・研究していました. 特にREMBO [1] [2]  やLINEBO [3] を用いた最適化を行うことで, どのようにアルゴリズムの振る舞いが異なるかを数値的に検証していました.

ブラックボックス最適化

本稿ではブラックボックス最適化問題, 特に最小化問題について考えます. 変数を\(\lambda\), 目的関数を\(L(\lambda)\)と書き, 探索空間を\(\Lambda \subset \mathbb{R}^{D}\)と書くことにします. ここで「ブラックボックス」とは, 最小化したい目的関数\(L(\lambda)\)にまつわる情報が手に入らないという想定を指します. すなわち, 自分である入力\(\lambda\)を選び, その出力\(L(\lambda)\)を得ることはできるけれども, \(L(\lambda)\)の勾配\(\nabla L(\lambda)\)などの情報は手に入れることができない, という最小化問題を扱います. このような状況では勾配法に基づく最適化アルゴリズムを用いることができないため, 異なる手法を適用する必要があります.

ブラックボックス最適化が必要となる代表的なシーンとしては「ハイパーパラメータ最適化」があります. 例えばSupport Vector Machine (SVM)の訓練時において, validationデータに対する損失を, SVMの最適化問題に現れる正則化項係数\(C\)や, カーネルのスケールパラメータ\(\gamma\)の関数として捉えてみましょう. するとこれはvalidationに対する損失を目的関数とした\(C, \gamma\)についてのブラックボックス最適化問題になります. 通常ハイパーパラメータ探索はランダムサーチやグリッドサーチが用いられますが, 近年次に示すベイズ最適化などのアプローチが注目されてきています.

ベイズ最適化 (Bayesian Optimization)

ベイズ最適化とは不確かさを用いながら次に探索すべき点を決定するブラックボックス最適化アルゴリズムです. 具体的なアルゴリズムとしては次のようになります.

キーとなるステップは非常に単純です.

  1. 今まで調べた点を用いて真の関数\(L(\lambda)\)を近似する関数\(a(\lambda)\)を作る
  2. \(a(\lambda)\)を最小化する点\(\hat{\lambda}\)を求める
  3. \(L(\hat{\lambda})\)を求め, 調べた点のリストに追加する

真の関数\(L(\lambda)\)を近似した関数\(a(\lambda)\)を獲得関数 (acquisition function) と言います. この獲得関数の構成に確率過程, 特にガウス過程を用いる手法がベイズ最適化と呼ばれます.

次に示す図は\(a(\lambda)\)としてLower Confidence Bound (LCB) を用いた図です. 今までチェックした点から, 探索できていない領域の不確かさをも含めて関数を近似し, 次に探索すべき点を探す流れを表しています.

ベイズ最適化は一般に, 20次元以上ほどの高次元空間では局所解に陥ってしまったり, 獲得関数の最小化がうまくいかないなどの理由で, 度々うまく動かないことがあります. そこで高次元空間中のベイズ最適化問題が研究されてきています.

REMBO

Random EMbedding Bayesian Optimization (REMBO) [1] [2] は, ランダム行列を用いて低次元空間を高次元空間に埋め込むことで, 高次元空間を陽に扱わずにベイズ最適化を行う手法です. この手法は真の関数\(L(\lambda)\)に
$$ L(\lambda_{\top} \oplus \lambda_{\perp}) = L(\lambda_{\top} \oplus 0) $$
という「縮退した線形空間があって, ある方向に動かしても\(L(\lambda)\)の値が変わらない」性質がある場合に効果を発揮します. これは\(\lambda\)の中に冗長なパラメータがある場合や, \(L(\lambda)\)に寄与しないノイズのような次元があるときに対応しています.

アルゴリズムとしては直接, 高次元空間\(\Lambda\)を扱うのではなく, 低次元空間\(Z \subset \mathbb{R}^{d}\)上でガウス過程を構成し, この空間内で最適化を行います. このとき\(z \in Z\)に対し, 各成分が独立な正規分布\(\mathcal{N}(0, 1)\)に従うランダム行列\(A \in \mathbb{R}^{D \times d}\)を用いて\(L(Az)\)を求めることで真の関数の評価を得ます. なお, 埋め込んだ\(\lambda = Az\)が現在考えている探索空間\(\Lambda\)の外に出てしまっている場合は探索空間上に射影を行います.

LINEBO

Line Bayesian Optimization (LINEBO) [3] は獲得関数の最小化を1次元空間に制限した上で行う手法です. 探索空間を1次元空間に制限する方法はいくつか考えられますが, \(\lambda\)を座標降下させる方法, または\(– \nabla a(\lambda)\)の方向に下る方法が比較的優位であることが数値的に示されています.

 

実験・観察

本稿ではテスト関数\(L(\lambda)\)としてSTYBLINSKI-TANG関数を用います. これはブラックボックス最適化のベンチマークとして使われる標準的な関数の一つで, 入力の次元数\(D\)を柔軟に設定することができます. 今回はベイズ最適化にとって比較的高次元とされる次元数である25に設定し, 探索空間\(\Lambda\)は通常用いられる\([-5.0, 5.0]^{25}\)としています.

実装としてはGPyTorch [4] をベースにしたベイズ最適化ライブラリBoTorchを用いています. GPyTorch・BoTorchを用いることの利点として, 従来ベイズ最適化の計算量のボトルネックであった「ガウス過程の予測」の段階における高速化が挙げられます.

さて, 次に示すのはアルゴリズムごとに各ステップにおける評価値\(L(\lambda)\)をプロットした図です.

 

ここで実験設定の詳細についてさらに述べておきます. Basic-BOとは獲得関数の最大化の際に特に何もせず, そのまま25次元空間上を探索するアルゴリズムを指します. またREMBOにおいて, 低次元空間の次元数は10次元, 探索空間\(Z\)は\([-1.0, 1.0]^{10}\)に設定しています. LINEBOでは降下方向として各次元の軸に沿った方向, すなわち座標降下法を用いています. 降下する軸の選び方は25次元の中から一様ランダムに選んでいます.  global optとは25次元STYBLINSKI-TANG関数の大域的最適解\(\lambda^{*}\)における\(L(\lambda^{*})\)の値を示しています.

また, アルゴリズムに依らずカーネル関数はRBFカーネル, 獲得関数はLCB, 初期点の数は200で統一しています.  REMBOのみ探索空間が低次元空間であるため, 初期点は低次元探索空間\(Z\)上から, Basic-BOとLINEBOは\(\Lambda\)から一様にサンプリングしてきた共通のものを使用しています.

実験結果から得られる観察として, まずどのアルゴリズムも大域的な最適解に収束できていない様子が見られます. 各アルゴリズムごとに見ると, Basic-BOはステップ数が増え, 探索点が増えていった場合にほとんど同じ評価値を取り続けており, 探索が十分に行われていない様子が見られます. 一方でREMBO, LINEBOはステップ数が増えた場合にも探索が行われている様子が確認できますが, 評価値の大きな改善には至っていないことがわかります. しかし, REMBO, LINEBOはBasic-BOに比べ少ないステップ数でより小さい評価値を得ていることがわかります.

結論

本稿では高次元空間中のベイズ最適化手法の収束性について数値的に検証しました. 結果として, どのアルゴリズムもテスト関数に対して大域的な解を得ることはできていなかったものの, REMBO, LINEBOは高次元空間中でも探索する様子が見られ, 標準的なベイズ最適化よりも速い収束性が観察されました.

一点注意すべき点としてベイズ最適化はフレームワークとして柔軟であるが故に, カスタマイズできる点が複数あることが挙げられます. 例えば, 「どのような獲得関数を使うか」, 「カーネル関数はどのようなものを用いるか」, 「初期点はどれぐらいにするか」などといった点です. そのため, 本稿での実験結果がそのままベイズ最適化の限界を表している訳ではないことに留意すべきです.

実際の業務ではテスト関数に留まらず, より複雑な関数に対してベイズ最適化を適用し, どのような結果が得られるか, どのような発展が考えられるかを試行していました. 今回, このような大変刺激的なテーマで研究する機会を頂いたことに感謝致します.

参考文献

[1] Wang, Ziyu, et al. “Bayesian optimization in high dimensions via random embeddings.” Twenty-Third International Joint Conference on Artificial Intelligence. 2013.

[2] Wang, Ziyu, et al. “Bayesian optimization in a billion dimensions via random embeddings.” Journal of Artificial Intelligence Research 55 (2016): 361-387.

[3] Kirschner, Johannes, et al. “Adaptive and Safe Bayesian Optimization in High Dimensions via One-Dimensional Subspaces.” arXiv preprint arXiv:1902.03229 (2019).

[4] Gardner, Jacob, et al. “GPyTorch: Blackbox matrix-matrix gaussian process inference with gpu acceleration.” Advances in Neural Information Processing Systems. 2018.

GraphNVP

Kosuke Nakago

2019-07-16 12:00:06

本記事は、2018年インターンシップ・PEとして勤務した Kaushalya Madhawa さんによる寄稿です。
本記事はこちらの英語ブログの日本語訳です。

本記事では、私たちが最近投稿した論文 “GraphNVP: An Invertible Flow Model for Generating Molecular Graphs” を紹介します。
コードも公開しています → Github repo

分子の生成モデル

望ましい薬理学的な物性値をもつ新しい分子の発見は創薬の分野において重要な問題です。これまで、候補となる化合物を実際に合成して実験を行うといったことがされてきました。
しかし、化合物のとりえる形の可能性は膨大でそれらを合成し、実験するということはとても時間がかかります。
このように望む物性値をもつ分子を探す代わりに、”de novo drug design” では、新しい化合物を興味対象とする物性値とともに設計するということを行います。

近年の深層学習の技術発展、特に深層生成モデルの分野は “de novo drug design” にとって重要な技術となってきています。

分子の表現方法

深層学習で分子の生成モデルを考える際、初めの重要なステップはどのように化合物を表現するかということです。
初期の研究では SMILES という、文字列ベースの表現方法を採用していました。
これらの研究は、 RNN ベースの言語モデルや、Variational AutoEncoder (VAE) を用いることで、SMILES の文字列を生成しそれを分子に変換します。
このアプローチの問題点はSMILES 文字列での小さな変化が分子全体でみると大きく変化するような場合があるということです。
そこで、分子をグラフを用いて表現しようというアプローチが出てきました。この問題は “molecular graph generation” として扱われます。

分子は無向グラフとして表現されます。原子をノード、結合 (bond) を辺に対応させます。この表記を用いると分子の構造・結合情報は Adjacency tensor (隣接テンソル) \( A \) として、また各ノードの原子(酸素、フッ素など)を node feature matrix \( X \) で表すことができます。この定式化の下で、分子の生成問題はグラフの生成問題として扱うことができ、これまでに技術発展してきた GANやVAEといった深層学習のモデルを用いることができます。さらにグラフの生成問題は2つのタイプに分類することができます。1つめは分子のグラフを”順番に” 生成する方法で ノード (原子) や 辺 (結合) を1つずつ生成していきます。もう1つの方法が直接グラフを生成するタイプで、画像の生成と似たように一度に全体を生成します。

可逆性

上記で紹介したVAEやGANと比較して、可逆な Flow を用いたモデルは尤度の最大化を直接行えるという長所があります。

さらに、Flow モデルは可逆な変換のみで構成されているので、逆変換が可能で100% 分子→潜在変数→分子 の再構成を行うことができます。

GANのみの生成モデルなどEncoder がない場合は、特定の分子を操作して生成・最適化を行うことは困難です。例えば、特定のベースとなる分子 (query) に似ている分子を生成して最適化を行っていくということが (創薬の分野で Lead optimization と呼ばれる) 困難です。一方Flow モデルは 分子の潜在変数を直接計算できるので、query 分子に対する潜在変数を簡単に求めることができそこから最適化を行うことも可能です。

提案モデル

model_reverse

提案モデルであるGraphNVPは上図のような構成をとります。GraphNVPは私たちの知る限りではOne-shot Graph生成モデルとして初めてFlow を用いたモデルです。
このモデルは辺に対応する変数とノードに対応する変数の2つの潜在変数を使用し、グラフ構造や原子種類の分布を表現できるようにします。
これらのをFlowの定式下で計算できるよう、 Adjacency Coupling および Node Feature Coupling と呼ばれる2つのCoupling layerを提案しました。
グラフの生成を行う際は、まずAdjacency tensorを生成し、次に Node feature tensor を graph convolutional network を用いて生成します。

結果

訓練データから分子をとり、その潜在変数 \( z_0 \) をGraphNVPで計算します。そして潜在空間上でランダムに選んだ2つの方向の軸に対して \( z_0\) が中心となるような2次元グリッドを構成し、その各点で潜在変数をデコードして分子を生成したものが下図となります。
下図の可視化結果では、似たような分子が並んでおり、隣どおしでは少しの原子が変わっているだけというようなものとなっており、提案モデルがスムーズな潜在空間の学習をできていることが見て取れます。

zinc_neighborhood_2d

 

 

さいごに:メンターより

Kaushalyaさんのメンターを担当した、中郷・石黒です。
今回の研究は2018年夏のインターンシップから始めたものです。このころはGraphの生成モデルの研究が盛んになり様々なアプローチでの生成モデルが提案され始めたころでしたが、まだFlowを用いたグラフの生成モデルはないので取り組んでみたいというKaushalyaさんの持ち込みからはじまったものでした。

グラフ生成モデルとしては初めての取り組みであり、またFlowを用いるモデルはかなり深いネットワークを使用する必要があり計算量も大きくなるということで、研究には時間がかかりましたが、最終的には論文として形にすることができ、コードも公開することができました。

最後に宣伝となりますが、PFNでは今回の “Drug Discovery / Material Discovery” の分野だけでなく、多種多様な業界で機械学習適用の横断プロジェクトを実施しており、中途・新卒の人材募集も通年で行っております!
興味のある方はぜひこちらのページをご覧ください。

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

楠本充
エンジニア

2019-06-25 15:27:28

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

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

PFN 楠本です。PFN では毎年8月9月の夏季休暇に約2ヶ月間の長期インターンシップを行っています。コーディング課題はその選考で応募者のプログラミング能力や問題解決能力を見るために出題させて頂いているものです。今年は「機械学習・数理」「バックエンド」「フロントエンド」「チップ」「性能最適化」「コンピュータービジョン(Chainer)」の6種類のコーディング課題を用意し、応募者の希望テーマに応じてこのうちのいずれかを解いていただく形にしていました。

今年のインターンシップでは去年をさらに上回る数の応募を頂きました。PFN では来年以降もインターンシップを開催する予定ですので、これらの課題を見て PFN に興味を持っていただけた方はぜひ応募を検討ください。また、フルタイムの採用も通年で行っております。こちらもご検討いただければ幸いです。

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 ではフルタイムの採用も通年で行っておりますので、こちらもご検討をよろしくお願いします。