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

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

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

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.

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 に興味を持っていただけた方はぜひ応募を検討ください。また、フルタイムの採用も通年で行っております。こちらもご検討いただければ幸いです。

プログラミング教育推進月間の教材について

Hiroshi Maruyama

2019-02-18 18:00:37

PFNフェローの丸山です。2月18日に、PFNは文部科学省、総務省及び経済産業省の「未来の学び プログラミング教育推進月間」に協力して、小学校向けのプログラミング教材を作成することを発表しました。この教材は、今年の9月に一部の小学校で、総合学習の一環として利用されることを目指しています(指導案のページはこちらです)。この記事では、私達PFNがなぜこのような活動をしているかをお話ししたいと思います。

PFNは若い会社です。多くの若い社員が次々に家庭を持ち、子どもを育て始めています。社長の西川をはじめ皆、次の世代が活躍し、よりよい社会を作っていくことを強く願っています。これからの社会を考えたとき、マーク・アンドリーセンが「ソフトウェアが世界を侵食する」(Software is eating the world) と言ったことに象徴されるように、社会の価値の多くが情報技術、特にソフトウェアから得られることは明らかです。ですから、私達の次の世代の誰もが、小さい頃から情報技術に親しみ、プログラミングの楽しさを知る機会を持てることは、私達にとっても大変喜ばしいことです。そんな若い人たちが、ソフトウェアに興味を持ち、将来社会のあらゆる場で活躍している、そんな社会の実現をPFNは願っています。

新しいスタイルのプログラミング

同時に私達は、技術の進歩によって、今までとは違う新しいスタイルのプログラミングが現れつつあることも強く認識しています。簡単にするため、プログラムとはある入力Xに対して出力Yを計算する箱であると考えます。

このようなプログラムを作る1つの方法は、計算のルールを書き下すことです。たとえば、商品の価格を入力としてその消費税を出力するプログラムを考えましょう。このようなプログラムは、入力Xに対して「X の0.08倍を計算してYとせよ」 というルールで表現することができます。これが普通のプログラムの作り方で、ここではルールによるプログラミングと呼ぶことにしましょう。

しかし、深層学習という新しい技術によって、別の形のプログラミングが現れてきました。こんな例を考えてみましょう。人とじゃんけんをする機械を作るために、カメラで撮った手の画像を入力として、それがグー・チョキ・パーのいずれであるかを判定して出力するプログラムを作りたいとします。

このようなプログラムを、ルールによるプログラミングで作るのは容易ではありません。カメラで撮影した画像は画素が格子状に並んだものですが、ある画素が肌色だからこれはチョキだ、と判断するわけにはいきません。同じチョキでも位置や角度や光源が違ったりして毎回異なる画像になるからです。

そこで、深層学習では、様々に異なるチョキの画像をプログラムに見せて「これはチョキだよ」と教えていくことによってプログラミングを行います。これを例示によるプログラミングと呼ぶことにします。例示によるプログラミングでは、ルールを書くのが難しいようなプログラムも作ることができます。

一方で、例示によるプログラミングでは、例示に使うデータによっては、必ずしも毎回正解が出ないかもしれません。あるいは例示に偏りがあった場合には、偏りのある結果が出るかもしれません。これは、ルールによるプログラミングが(プログラムに誤りが無い限り)常に正しい答えを出すこととは対照的です。

将来のソフトウェア

例示によるプログラミングは、ここ10年ほどの、深層学習の急速な発展によって可能になってきていて、今までのルールによるプログラミングでは難しかった画像認識、音声認識、機械翻訳などに応用されつつあります。これは、1950年代にデジタル計算機が発明されて以来の最大のパラダイムシフトかもしれません。おそらく、将来のソフトウェアの多くは、ルールによるプログラミングと例示によるプログラミングを組み合わせたハイブリッドなものになるでしょう。

私達が今回の「未来の学び プログラミング教育推進月間」にご協力している真の理由はここにあります。今の子供達が大人になって、社会におけるソフトウェア開発の一翼を担うころには、例示によるプログラミングが広く使われていることは間違いありません。ルールによるプログラミングが苦手でも、例示によるプログラミングは得意だ、という子どももいるでしょう。

「プログラミング」を狭く捉えないで、いろいろな考え方があるのだ、ということを知ってほしい、それが私達の願いです。

 

インターン参加報告: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開発の人材も募集しています)

分散深層学習とモデル並列性

Kota Uenishi

2018-12-21 15:29:18

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

はじめまして。Preferred Networksの分散深層学習チームでアルバイトをしている包です。私は分散深層学習の中でも主にモデル並列に関する機能実装を行っています。今回はモデル並列性の概要と、ChainerMNにおいてどのようにモデル並列性を実現しているのかについて紹介します。

分散深層学習: データ並列性とモデル並列性

深層学習における各種フレームワークは目覚ましい発展を遂げ続けており、最近では一般ユーザーでも簡単に複数GPUを用いたニューラルネットの訓練ができるようになってきました。たとえば、ChainerMNではoptimizerの定義にほんの数行加えるだけでニューラルネットを複数GPUで訓練できます[1]。これにより1024GPU上でImageNetによるResNet-50の学習を15分で行うなどの実績を上げています[2]。このような複数プロセス、複数ノードを用いた分散深層学習によってニューラルネットの訓練は高速に行えるようになっており、分散深層学習は現在の深層学習の基盤を支えているといえます。

ところで、「分散深層学習」にはデータ並列とモデル並列という2通りのアプローチがあることが知られています[3]。データ並列では、全プロセスに同じモデルのコピーして訓練することでバッチサイズをプロセス数倍し、学習を高速化させる手法です。先程お話したImageNetの並列訓練もデータ並列による高速化の一例です。一方でモデル並列とは、1つのモデルを分割して複数のプロセスに配置し、全プロセスで協調して1つのモデルを訓練する手法です。主なユースケースとしては超解像度を入力とするCNNやMixture of Experts[4]など、1プロセス上に載りきらないサイズのモデルを訓練したい場合に用いられます。最近ではMesh-Tensorflow[5]というTensorflow用のモデル並列ライブラリが公開されましたが、現状ではモデル並列をサポートしているフレームワークは非常に少ないです。

この記事では、ChainerMNに実装されているモデル並列APIを、実例を交えて紹介します。特に、Define-by-Runとともにモデル並列を実現する際に発生する問題と、その解決方法について重点的にお話をします。

ChainerMNにおけるモデル並列性の実現

ChainerMNでは、通信をChainerの関数呼び出しによって定義 します。これにより非常に柔軟な通信パターンを実現することができます。

図1: 関数呼び出しによる通信の定義の例

ChainerMNにおける通信はMPIを用いて実現されており、モデル並列でも基本的にMPIの通信スタイルを踏襲しています。MPIでは大きく分けて MPI_Send を始めとした1対1通信と、 MPI_Bcast のような集団通信向けのAPIが提供されています。ChainerMNでは、これらの通信APIと対応するように chainermn.functions.sendchainermn.functions.bcast のように、Chainerの関数を提供しています。通信用の関数は、それぞれbackwardにおいて「勾配を逆向きに通信」するように設計されています。例えば bcast の場合、forward計算ではmasterからslaveに対して入力変数がbroadcast通信されます。一方で、backward計算ではslaveからmasterに対して勾配をallreduceします。

ChainerMNに実装されているforward通信に対応するbackwardの通信パターンは以下のようになります。

表: forward と backward における通信パターンの対応

forward backward
allgather allgather
alltoall alltoall
bcast allgather
gather scatter
scatter gather
send recv
recv send

 

次に、モデル並列APIの具体的な使い方について見ていきます。まず、データ並列の際と同様に、通信を行うためのコミュニケータを作成します。

comm = chainermn.create_communicator()

例えば、図1のようなモデルの実装イメージは次のようになります(図1のモデルに特に意味はありません)。

class ExampleModel(chainer.Chain):
    def __init__(self):
        self.comm = chainermn.create_communicator()
        self.conv = L.Convolution2D(...)

    def forward(self, x):
        x = chainermn.functions.bcast(self.comm, x)
        h = self.conv(x)
        y = F.relu(h)
        ys = chainermn.functions.gather(self.comm, y)
        ...

この例では、masterからブロードキャストされた変数が Convolution2D の入力になります。一方で、backward計算の際には、 Convolution2D の勾配が自動的に Bcast のbackwardによってmasterへ集約されます。

ChainerMNに用意されているAPIの詳細については、ドキュメントを参照してください[6]。なお、モデル並列関連のAPIに関しては現状では実験段階なので、将来的に後方互換でないAPIの変更が起こる可能性があります。

Define-by-Runにおける注意点(その1)

ChainerをはじめとしたDefine-by-Runによる計算グラフの定義はモデルを直感的に記述することができる点で優れているといえます。backward計算時には、出力変数からグラフのバックトラックを行うことによってパラメータの更新を行うことができます。しかし、モデル並列を実現するために上述のように通信を関数として定義すると、計算グラフが正しくバックトラックできない状況が発生します。

例えば、下記のような2つのプロセス間におけるシンプルな1対1通信の例を考えます。

図2: 1対1通信の例

「Process #0」に注目してみると、出力変数 y からバックトラックを行ったときに、 recv から send へ戻ることができません。その結果、「Process #1」は recv のbackward(すなわち勾配のsend)を呼んでいるにもかかわらず、「Process #0」は send のbackward(すなわち勾配のrecv)を呼ぶことができず、デッドロックが発生します。このような状況は、1つのプロセス上における計算グラフが非連結になっているときに生じます。そのため、 send 関数が戻り値として返す特別な変数を recv に渡すことによって、 計算グラフが連結になるようにモデルの定義を行います

図3: delegate variableによる計算グラフの連結化

このような sendrecv を繋ぐような send 関数の戻り値を、便宜的に「delegate variable」と呼ぶことにします。Delegate variableは「Process #0」においてグラフを連結にする役割を果たす他に、「Process #1」でもバックトラックの起点となるダミーの出力変数として振る舞います。図3をコードで記述すると以下のようになります。

class ExampleModel_0(chainer.Chain):
    def forward(self, x):
        # first component
        z = f(x)
        phi = chainermn.functions.send(z, comm, rank=1)

        # second component
        z = chainermn.functions.recv(comm, rank=1, delegate_variable=phi)
        y = h(z)

        return y

class ExampleModel_1(chainer.Chain):
    def forward(self, _):
        z = chainermn.functions.recv(comm, rank=0)
        z = g(z)
        phi = chainermn.functions.send(z, comm, rank=0)
        return phi

Define-by-Runにおける注意点 (その2)

先程の節ではグラフが非連結になると計算グラフのバックトラックができない例を1つ挙げました。このような例は他にも存在します。

 

図4: 1対1通信を2回呼ぶ例

 

図4では、1対1通信が2回発生しています。この場合、「Process #0」における send が返す2つのdelegate variableを適切に処理する必要があります。そこで、以下のように2つの変数を1つにまとめる処理を行います。

 

図5: pseudo_connectを用いた例

 

chainermn.functions.pseudo_connect という関数は、「delegate variableがあたかも別の変数であるかのように振る舞うような変数」を返す関数です。図5の例では、 \( \phi_1 \) というdelegate variableが実際には \( \phi_2 \) という別の変数として振る舞うような変数 \( \psi \) を返します。 \( \psi \) をバックトラックする際には、まず \( \phi_1 \) のバックトラックを行い、次に \( \phi_2 \) のバックトラックを行います。このようにして、backward計算の際に2つのdelegate variableを正しくトラックバックすることができます。図5をコードで記述すると次のようになります。

class ExampleModel_0(chainer.Chain):
    def forward(self, x):
        z1, z2 = f(x)
        phi1 = chainermn.functions.send(z1, comm, rank=1)
        phi2 = chainermn.functions.send(z2, comm, rank=1)
        psi = chainermn.functions.pseudo_connect(phi1, phi2)
        return psi

class ExampleModel_1(chainer.Chain):
    def forward(self, _):
        z1 = chainermn.functions.recv(comm, rank=0)
        z2 = chainermn.functions.recv(comm, rank=0)
        y = g(z1, z2)
        return y

図5では pseudo_connect で2つのdelegate variableをまとめましたが、次の図6のように通常の変数にdelegate variableを結合することも可能です。

図6: delegate variableと通常の変数を結合する例

 

y_ = chainermn.functions.pseudo_connect(phi, y)

以上がChainerMNにおけるモデル並列の概要になります。次に、実際のモデルの例を見てみます。

1対1通信を用いた例: encoder-decoderモデル

Encoder-decoderモデル[7]は可変長の入力を可変長の出力に変換することを目的としたモデルで、自然言語処理をはじめとした応用分野で広く用いられています。
Chainerのexampleにも機械翻訳の例があります[8]。Encoder-decoderモデルの入力や出力に画像を用いるようなモデルの場合、CNNをencoderやdecoderに用いることになりますが、層数やパラメータ数が膨大なencoderやdecoderになると、全体のモデルが1GPUに載らないケースが発生します。その場合、モデルをいくつかに分割して複数プロセスでモデル並列学習を行うことによって学習できます。例えば、下図のようにencoderとdecoderにそれぞれ1プロセスずつ割り当てるような分割が考えられます。

図7: encoder-decoderのモデル並列化

 

ここでは、はじめのプロセスでencodeしたcontext vectorをdecoderへ送信して、decoder側のプロセスでdecodeするように分割を行っています。例えばLSTMの場合はcontext vectorが2つあるので、2回の1対1通信を行うことで実現できます。ただし、図5の例と同様に、encoder側では pseudo_connect を用いてdelegate variableを1つにまとめる必要があることに注意してください。基本的には sendrecvpseudo_connect を用いれば実装することができますが、encoder-decoderモデルの分割は実装が煩雑になるので、専用のLinkを用意しています。

rnn = chainermn.links.create_multi_node_n_step_rnn(
        L.NStepLSTM(n_layers, n_units, n_units, 0.1),
        comm, rank_in=None, rank_out=1)

create_multi_node_n_step_rnn は、Chainerで提供されている NStepRNN [9](可変長系列をまとめて入出力するAPI)をラップして、内部で別のプロセスと自動的にcontext vectorを送受信します。rank_in に指定したプロセスからcontext vectorを受信し、 rank_out に指定したプロセスに対してcontext vectorを送信します。これを用いると、次のようにモデル並列なencoder-decoderモデルを簡単に実装することができます。

class Encoder(chainer.Chain):
    def __init__(self, comm, n_layers, n_units):
        super(Encoder, self).__init__(
            # Corresponding decoder LSTM will be invoked on process 1.
            mn_encoder=chainermn.links.create_multi_node_n_step_rnn(
                L.NStepLSTM(n_layers, n_units, n_units, 0.1),
            comm, rank_in=None, rank_out=1
            ),
        )
        self.comm = comm
        self.n_layers = n_layers
        self.n_units = n_units

    def forward(self, *xs):
        exs = f(xs)
        c, h, _, phi = self.mn_encoder(exs)
        return phi

class Decoder(chainer.Chain):
    def __init__(self, comm, n_layers, n_units):
        super(Decoder, self).__init__(
            # Corresponding encoder LSTM will be invoked on process 0.
            mn_decoder=chainermn.links.create_multi_node_n_step_rnn(
                L.NStepLSTM(n_layers, n_units, n_units, 0.1),
            comm, rank_in=0, rank_out=None),
        )
        self.comm = comm
        self.n_layers = n_layers
        self.n_units = n_units

    def forward(self, *ys):
        c, h, os, _ = self.mn_decoder(ys)
        ...

この例はChainerMNのexampleに公開されています[10]。

集団通信を用いた例: チャネル方向の並列化

集団通信を用いると、下図のようにCNNのチャネル方向の並列化が実現できます。この並列化は高解像度画像を扱う際や、バッチサイズを大きくする際に有用です。

図8: チャネル方向の並列化

 

各プロセスはCNNのチャネルのうち一部だけを入力としてとって畳み込みを行うので、各々のプロセス上のCNNのパラメータ数を減らすことができます。CNNの出力に対して “allgather“ を用いることで、全チャネルを集約することができます。実装のイメージは以下のようになります。

class ParallelConvolution(chainer.Chain):
    def __init__(self, comm, in_channels, out_channels):
        self.comm = comm
        self.in_channels = in_channels
        self.out_channels = out_channels
        self.conv = L.Convolution2D(...)

    @property
    def _indices(self):
        # index % comm.size == comm.rankとなるインデックスのチャネルを担当
        # 例 (size=4, rank=1の場合): _indices = [1, 5, 9, ...]
        idx = numpy.arange(self.in_channels)
        return idx[idx % self.comm.size == self.comm.rank]

    def forward(self, x):
        # 当該プロセスの担当チャネルをスライス
        x = x[:, self._indices, :, :]

        y = self.conv(x)

        # 全チャネルを集約
        ys = chainermn.functions.allgather(self.comm, y)
        return F.concat(ys, axis=1)

この例はchainerMNのexampleに公開されています[11]。

まとめ

本記事では、ChainerMNにおけるモデル並列の実現と、実際の例をいくつか紹介しました。特に、Defined-by-Runの下では計算グラフが連結でなければならないため、delegate variableやpseudo_connectなどのテクニックが必要になります。今回はスペースの都合で紹介がかないませんでしたが、特定のタイプのモデル向けによりシンプルにモデルを定義できるようなAPI( MultiNodeChainList, MultiNodeNStepRNN)も用意されているので、お手軽に試してみたい方はぜひドキュメント[6]をご覧ください。

参考文献

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

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 です。

[BoF] How to choose programming language for product/in-house software development

kashihara
エンジニア

2018-08-24 15:35:26

Preferred Networksでエンジニアをしている柏原です。PFN Dayでは “How to choose programming language for product/in-house software development” という題でBoFのセッションを開きました。PFN Dayとはトビアスのブログエントリ「[PFN Day] BoF session: How to Improve Sharing of Software Components and Best Practices」にもあるように、社内向けの技術カンファレンスです。

ソフトウェア開発において、プログラミング言語は開発環境をはじめとして、開発チームやサポート体制などに大きな影響を与えます。 PFNの中でもたくさんのプログラミング言語が使われていると思います。 今回は社内で何が使われているかという現状については言及せず、社外にリリースする製品/社内製品を開発することを想定して、どうやってプログラミング言語を選択するか、どのような要素がプログラミング言語の選択に影響を与えるのか議論したいと考えました。

まず、参加メンバーのバックグラウンドを共有するため、どういったソフトウェア開発・プログラミング言語の経験があるか自己紹介をしました。 その後、過去にどのような点を重視してプログラミング言語を選んだのか、プログラミング言語を選ぶときの重要な点についての項目を議論の中であげていきました。

結論としては必要としているものを正しく選ぶ、ということになりますが、以下の優先順位がプログラミング言語の決定に大きく依存しているということになりました。

  • Priority 1: Real world restrictions (E.g. frameworks, platforms)
  • Priority 2: Real world needs (E.g. stability, production readiness, concurrency, distributed computed)
  • Priority 3: Real world benefits (E.g. productivity factors)

1番目のrestrictionsでは、実行環境(OS、モバイル端末、組込)や、目的を実現するためのフレームワークが優先されます。 近年ではたくさんのプログラミング言語が増えてきたとはいえ、その言語が利用できるかは環境に大きく依存します。

2番目は、ソフトウェアで求められている機能・非機能要件を満たすことが、当然ながらソフトウェアの開発で求められます。 プログラミング言語やランタイム環境は、適材適所であるべきといえるでしょう。 ソフトウェアの安定性が求められるのはもちろんのこと、近年ではCPUのマルチコア環境を活かすことも必要とされてきています。 プログラミング言語の機能や特性によって、ソフトウェアの要求を実現できるというのはとても心強いです。

3番前は、プログラマーがプログラミングするにあたって、あると嬉しい部分です。 例えば、テキストエディタやIDEによる、プログラミング言語を書くことをサポートする機能(プラグイン)があげられます。

BoFを開催する前は極端な意見に偏るかもしれないと少し不安でしたが、最終的には現実的な結論に落ち着いたと思います。 その他、興味深いトピックとして、ソフトウェアの正しさを検証するものとして、モデル検査やHDLのSystemVerilog(言語)といったものも話題にあがりました。 80分と長いような短い時間の議論でしたが、興味深い会話ができたと思います。BoFのメモがもし公開されたら、そちらも是非ご覧ください。

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

Preferred Networks における研究活動

秋葉 拓哉
リサーチャー

2018-06-08 14:36:39

こんにちは、新しく執行役員兼 Chief Research Strategist に就任した秋葉です。就任の挨拶を兼ねて、PFN における研究活動に関する考えを共有したいと思います。

PFN における研究とは何か?

何が研究であり何が研究でないかという境界を引くのは非常に難しく、またそれを積極的に行う意味もありません。研究とは「研ぎ澄まし究めること」を語義とし、一般に、物事について深く調査・考察を行い事実を解明したり発明を行ったりすることを指します。

PFN では挑戦的であり不確実性の高いプロジェクトが大部分を占めており、ほぼ全てのプロジェクトが少なからず研究的側面を伴います。深層学習関連のコア技術の研究開発は勿論、その応用に関してもデータやタスクに応じた適切な手法の選択や非自明な工夫がなければ上手くいかないことが殆どです。また、ロボティクス、コンピュータビジョン、自然言語処理等のような多分野の技術を組み合わせることにより新たに出てくる課題もあります。それに加えて、クラスタの設計やそのリソース管理、及びディープラーニングフレームワークに関しても、深層学習特有の要求を満たし、便利かつ高性能にするために、多くのことを考え試行錯誤をしています。

そのような中でも、特に研究的側面を強く持つプロジェクトには、以下のようなものがあります。

  • 論文となるような学術的研究
  • デモンストレーションの制作と展示
  • コンペティションへの参加
  • 社会での未解決問題の解決

このような分野でも、既に素晴らしい成果が出ています。論文に関しては、ICML, CVPR, ACL, CHI など、幅広い分野のトップ会議に論文が継続的に採択されるようになりました。また、数が増えているだけでなく、ICRA’18 にて論文が Best Paper Award on Human-Robot Interaction を受賞したり、ICLR’18 にて論文が Oral に選ばれたりと、世界的に極めて高い注目を集める論文を出すことに成功しています。デモンストレーションとしては、CEATEC 2016 や ICRA 2017 等で制作したものを展示しました。コンペティションとしても、Amazon Picking Challenge 2016 や IPAB 創薬コンテスト等で優れた成果を残しています。

PFN はなぜ研究をするのか?

PFN のような企業で、今すぐ直接お金に結びつかないような研究をする意味はあるのでしょうか?例えば、論文を書こうと思えば貴重な業務の時間をごっそりと使ってしまうことになるし、それを出版すれば社外の人たちに技術を教えてしまうことになります。こう考えると、学術的研究や論文執筆は、会社にとってマイナスの活動のようにすら見えます。

実際には、PFN においてそのような研究活動は極めて重要視されており、今後もなお重点的に強化を行っていく予定です。コンピュータや AI 分野のビジネスでは、しばしば「Winner takes all」といったことが言われます。このような領域では、ビジネスに国境がなく、中途半端では生き残ることはできません。世界でトップクラスの技術を持ちリードを保ち続ける必要があります。従って、我々は、研究活動を通じ技術力を中心とした競争力を持ち続けることがビジネス上で極めて重要だと考えています。また、現実的には、優れた特許ポートフォリオを構築するといったことも重要です。

また、「よそから出てくる論文の実用化に注力する方が効率的ではないのか?」という疑問もよく聞きます。しかし、論文が出てきて我々の目に止まるタイミングでは、世界のトップは必ずもっと進んでしまっています。そして、論文を読んで得られる情報はかなり限られており、試行錯誤したり著者に問い合わせながら再現に成功したり、他のデータセットへの適用を通じて論文に書かれていない手法のネガティブな性質について把握したりするのには、さらにかなりの時間がかかります。パーソナルコンピュータの父として知られるアラン・ケイの「未来を予測する最善の方法は、それを発明することだ」という言葉は、実際にいくつかの分野で世界をリードしたりトップに迫ったりといった成果を出すことができている我々にとって、大きな実感があります。

更に、単に社内で研究を行うことだけでなく、成果をコミュニティに発表し還元することも重要視しています。一つには国内外でのプレゼンスを得るという目的もあります。それに加えて、我々の発表した技術に基づいた研究や我々の発表に触発された研究が社外でも行われることにより、トータルで考えて我々に必要な技術の発展が加速されると考えています。そのため、OSS としてソフトウェアを公開したり、研究に使ったコードやデータなども積極的に公開しています。また、アカデミックなコミュニティへ貢献するため、学会や論文誌の査読も業務で行えるようにしています。

どのような研究を推進していくのか?

深層学習を中心として、コンピュータビジョン、自然言語処理、音声認識、ロボティクス、コンパイラ、分散処理、専用ハードウェア、バイオインフォマティクス、ケモインフォマティクスといった、幅広い分野での研究を行っており、これを以下のような理念に基づき強化していきます。

正しくクレイジーに

全ての研究は現在だけでなく未来を見据えて行われるべきです。研究の価値も、今の常識だけで判断するべきではありません。「そんな計算が重い方法は実用的じゃないよ」といったことや「今はそんな処理したい人いないよ」といったことは、必ずしもネガティブではありません。例えば、我々は昨年、1024 台の GPU を用いた分散処理により画像認識モデルを高速に学習するというプロジェクトを成功させ、世界的に大きな注目を集めました。達成した速度が常識外れだっただけでなく、1024 台の GPU を一度に使うと言った実験の規模自体も常識外れでした。1024 台の GPU を使って日常的な学習を行うといったことは現実的ではないかもしれません。それでは、このような研究の価値は無いのでしょうか?

計算機は未だに速くなり続けています。特に、深層学習に関しては、専用チップの開発も盛んです。OpenAI の調査によれば、深層学習の大規模なトレーニングで使われる計算力は、3.5 ヶ月で倍という急速なペースで上がっています。今は馬鹿げた計算力に見えるそのような設定も、数年のうちに当たり前のように使える状況が来る可能性は高いでしょう。未来を見据え、そのような状況では何が起こるのかといったことを知り、そこでの課題を解決したり新たにできることを模索したりといったことに早く乗り出すことは、非常に重要だと考えています。1024 台の GPU を用いた上述の実験はその第一歩であり、プライベートスーパーコンピュータと並列分散計算チームを持つ強みを活かしながら、大規模な実験を促進し、このような規模での実験を当たり前のように感じられるぐらいの環境を作りたいと考えています。

世界とグラウンディングする

全ての研究は何らかの意味で世界の最先端を目指すべきです。技術力は、世界的にリードを持つことにより大きな価値に繋がります。社内だけでなく、積極的に外を向き、論文が世界的に高く評価されたり、世界的なコンペティションで高い順位を取ったり、注目を集め講演に呼ばれたり、といったことを目指すべきだと考えています。実際には、全ての研究プロジェクトで世界をリードするようなことは難しいかもしれません。しかし、世界トップをしっかり意識し目指すことで、自分たちの相対的な位置を知ることができます。

また、世界的なコミュニティに食い込むことも非常に重要です。社外の世界トップを走る人たちと知り合いになり、無視できない存在だと認識してもらうことで、有益な情報の交換ができます。そのためにも、外部発表を推奨しており、貢献をしたメンバーの顔がしっかり外に出るようにしています。

積極的に展開する

全ての研究は小さく閉じこもることなく積極的な展開を目指すべきです。例えば、研究を論文にすることは非常に重要なマイルストーンですが、それは完成ではありませんし、それだけを目標にするべきではありません。深層学習では共通の技術が異なる応用分野を跨がり力を発揮することがあります。PFN には幅広い分野に取り組む人がいるという利点を活かし、研究のスコープを狭く捉えず、人を巻き込み、幅広い展開を目指してほしいです。また、新たなソフトウェアを開発したり社内のソフトウェアにフィードバックしたりして人が利用できる形にすることも可能であれば検討するべきです。社内での実務に成果を還元できれば素晴らしいでしょう。トップ会議への論文採択数は重要視していますが、一方で、論文の本数や論文が採択された会議のランクのみから研究開発活動を評価することはしないつもりです。

もちろん、全てを自分でやる必要はありません。世界のトップレベルに食い込んでいくためには、自分の能力的な強みとモチベーションを存分に発揮することが必要です。従って、自分が持っていない能力は積極的に人に頼ることも検討するべきです。これは技術領域のみでなく、研究のまとめ方に関してもです。せっかく面白い研究開発をやっていても、論文執筆の経験を持たないためどうやって論文にしていいか分からなかったり、誤解が原因で学会投稿で過小評価され採択に繋がらないこともあります。論文の執筆方法や徹底したサーベイ、正しい比較実験の仕方などについて、基礎研究で活躍してきた研究のベテランが社内に多く存在することを活かしていけるようにしたいと考えています。

PFN で研究開発をする魅力は?

リサーチャー・エンジニアとして PFN における研究開発に携わる良さとは何でしょう?

最も魅力的な点の 1 つは、PFN の対象とする深層学習を中心とした技術領域の特徴として、個人及び組織的な卓越した技術力が、本当に必要とされており、非常に重要であるということです。個人としても組織としても技術力の差が成果に反映されやすいという意味で、高い技術力を持つことが高い価値に直接的につながります。個人として高い技術力を持つこと、そしてチームとしてさらなる力を発揮することが非常に高く評価されます。これは、技術力に自信を持つ人や、技術力の向上にモチベーションを持つ人に、とても良いことであると感じます。

取り組み方が非常にフレキシブルな点も魅力だと考えています。100% の時間をピュアな基礎研究に費やすメンバーも今では複数人いてチームも構成しており、増強していく予定です。一方で、実務的な課題にも触れながら研究活動を行っているメンバーも多数います。また、アカデミアとの共同研究も積極的に行われていますし、社会人博士としてパートタイムで大学院に通い専門性を磨くメンバーもいます。

研究開発活動を促進するための社内制度にも気を使っています。会社がメンバーを信頼して大きな裁量を与え、足りない社内制度や資産があればフレキシブルに対応するなど、新しいチャレンジを積極的に支援しています。例えば、20% ルールにより、全てのメンバーは 20% までの時間を自分の裁量で使うことができます。これにより、誰でも思いついたアイディアをすぐに試すことができます。強いモチベーションやユニークなアイディアを持つ取り組みがボトムアップに出てくることを期待しています。

PFN が取り組む深層学習を中心とした技術領域では、アルゴリズムからソフトウェアフレームワーク、研究支援ミドルウェア、そしてハードウェアまで、その全てが重要になってきます。深層学習、強化学習、コンピュータビジョン、自然言語処理、バイオインフォマティクス、高性能計算、分散システム、ネットワーク、ロボティクス、シミュレーション、データ解析、最適化、異常検知といったような幅広い専門を持つ人が社内の近い位置にいて、気軽に情報交換ができる点もとても魅力的だと思います。分からない事柄について教えてもらったり、実務上出てくる問題を交換したり、一緒に研究に取り組んだりすることができます。

終わりに

最後に、少し個人的な抱負を書かせてください。今回、執行役員兼 Chief Research Strategist という身に余る大役を頂戴しました。能力面でもそれ以外でも心から尊敬できるメンバー達が素晴らしいチームとなり活躍しているこの会社で、私なんかにこのような大役が務まるのかという不安もあり、引き受けていいものか迷いました。

私は前職ではアカデミアでの研究者でしたが、企業での研究にも学生時代から興味を持ち、海外の企業研究所でのインターンにも複数回参加していました。その中で一度、インターン期間中にレイオフが起こり、自分のメンターも含めてその研究所に所属していた全研究者が解雇になるという様子を目の当たりにしたことがあります。企業での研究を意義あるものに保つ難しさを実感しました。

そのような経験を踏まえて考えても、私は PFN は企業として研究活動をするべきだと思います。それを健全な状態に保ち価値に繋げるのは決して簡単なことではないと思いますが、そのような部分にもし私の色々な場所での経験や考えを活かして貢献できるのであれば、それは非常に刺激的かつ意義のあることだと感じ、新たなポジションで頑張ってみることにしました。

また、研究とエンジニアリング、深層学習と分散計算など、複数面の得意分野を融合させることのできる自分の強みや、勝ちにこだわり戦略を練り遂行できる自分の強みを、今後はより広範囲で活かしていければと考えています。

PFN では、このような研究開発活動に興味を持ち一緒に取り組んでくれるメンバーをリサーチャー・エンジニアとして募集しています