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

Masashi Yoshikawa

2019-10-11 13:26:38

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

 

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

 

概要

 

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

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

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

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

 

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

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

 

アプローチ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 

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

 

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

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

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

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

 

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

 

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

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

 

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

 

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

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

 

実験

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

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

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

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

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

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

表1. 予測精度の比較

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

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

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

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

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

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

関連研究

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

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

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

 

Future Work

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

まとめ

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

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

参考文献

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

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

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

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

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

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

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

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

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

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

Masahiro Sakai

2019-10-10 12:10:39

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


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

要旨

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

はじめに

木幅とは?

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

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

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

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

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

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

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

木幅は何の役に立つ?

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

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

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

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

Graph Neural Network とは?

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

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

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

 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

アプローチ 1

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

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

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

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

今回導入する枝刈り

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

アプローチ 2

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

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

実験結果

アプローチ 1

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

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

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

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

結果を下図に示します。

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

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

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

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

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

アプローチ 2

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

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

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

まとめ

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

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

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

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

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

参考文献

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

メンターからのコメント

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

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

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

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

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

Kengo Nakasuka

2019-10-08 14:40:58

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


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

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

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

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

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

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

手法の説明

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

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

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

実験結果

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

下図に結果を示します。

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

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

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

まとめ

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

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

謝辞

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

おまけ:メンターより

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

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

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

 

Disentangled な表現の教師なし学習手法の検証

Keisuke Nakata

2019-10-08 11:20:57

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


はじめまして。PFN の2019夏季インターンシップに参加した東京大学の蕭喬仁です。 大学では自然言語処理について研究しており、SNS からのマイニングに興味があります。
今回のインターンでは「Disentangled な表現の教師なし学習手法の検証 (Unsupervised Disentangled Representation Learning)」というテーマで研究を行いましたので、その紹介をいたします。

実験に使用したコードはこちら https://github.com/pfnet-research/chainer-disentanglement-lib で公開しています。

Disentangledな表現

映画 Star Wars がお好きな方は ”imperial entanglements” という表現でおなじみかもしれませんが、entangle とはもつれるという意味の英単語です。したがって Disentangled Representation とは直訳するともつれを解いた表現ということを指します。
では、もつれを解いた表現とは何なのでしょうか?実は disentangled な表現の定義は研究者の間でもまだ定まったものが無いのですが、多くの研究では潜在空間中の各次元が観測データ中の因子や性状ごとに分かれているような状態を disentangled な表現としています。たとえば、画像認識における disentangled な表現の各次元は被写体の「色」「形」「大きさ」などをそれぞれ表すことが期待されます。このような性質を持つ表現はある1つの次元を変動させても観測データ中の複数の要素が同時に変わる事が無いため、観測データの情報が解釈可能で低次元な潜在空間に圧縮された表現とも言えます。そのため教師有り・半教師有り学習などの機械学習タスクや few-shot learning, domain adaptation などに有用であるとされており、様々な手法が近年提案されてきました。

先行研究

教師なしで disentangled な表現を得る手法として state-of-the-art を主張している論文の多くは変分オートエンコーダ (Variational AutoEncoder; VAE) [1] をベースにした手法を採用しています。

図1. VAE の概念図

VAE では潜在変数の確率分布を標準正規分布に近づけながら学習を行いますが、disentangled な表現を得るためには潜在変数の事後分布がより標準正規分布に近い必要があります。データ \(X\) を生成している真の因子は各々独立であることを仮定しているからです。このような仮定のもと近年提案されてきた手法は VAE にどのような正則化項を加えるかで以下のように分類することができます。

  • 近似事後分布 \(q(z \mid x) \) をより事前分布である標準正規分布に近づける正則化項を加えた β-VAE [2]
  • aggregated variational posterior \(q(z) \) が各成分独立になるような正則化項を加えた FactorVAE [3] や β-TCVAE [4]
  • aggregated variational posterior \(q(z) \) が事前分布と近くなるような正則化項を加えた DIPVAE-1/DIPVAE-2 [5]

また、潜在変数に離散変数を使えるようにした、JointVAE [6] や CascadeVAE [7] などの手法もあります。

様々なモデルの提案と同時に disentangled な表現を定量的に評価する指標も数多く提案されています。評価指標には以下のような2系統が存在しますが、いずれの指標でも値の計算のためにデータの真の生成因子が必要となります。こちらでは紹介していませんが、インターンに参加していた8月中にも新しい評価指標 [8] が提案されており、どの指標を用いるべきかは研究者の間でも定まっていません。

  • データ \(X \) のある生成因子を固定した状態でその他の因子を変化させた時の潜在変数の変化をみる BetaVAE metric [2], FactorVAE metric [3], IRS [9]
  • エンコードした潜在変数から真の生成因子をどれだけ予測可能かをみる MIG [4], SAP-SCORE [5], DCI [10]

一方で、disentangled な表現を完全に教師無しで学習することは困難なのではないかという主張が最近なされるようになりました。Locattello らの研究 [11] では近年 state-of-the-art を主張してきた手法に対して大規模な検証実験を行い以下のようなことを示しています。

  1. モデルや正則化項等のハイパーパラメータよりも乱数による影響が大きいということ。
  2. モデルが学習した disentangled な表現が人間の直感に合う保証が無いこと。
  3. 再構成誤差や ELBO などの教師無しで得られるモデルの評価指標と教師有りの disentangled な表現の評価指標には相関が見られないこと。
  4. データ \(X \) を生成する確率 \(P(X) \) しか持っていない状況では、disentangled な潜在変数 \(p(z) \) と entangled な潜在変数 \(p(z^\prime) \) の識別が数学的に不可能であること。

ただし、論文では適切な帰納バイアスを取り入れることで教師ラベルを用いる事なく disentangled な表現を得ることは可能かもしれないとされており、別の論文 [12] でも損失関数に潜在変数の事前分布を適切に調整することでより良い disentangled な表現を得ることが可能であったという報告もされています。disentangled な表現を得る試みはまだまだ始まったばかりと言えるでしょう。

実験設定

今回のインターンでは、先行研究では検証されていなかった潜在変数の次元数や種類がパフォーマンスにどのような影響を与えるかを検証するために state-of-the-art を主張してきた BetaVAE, FactorVAE, DIPVAE-1/-2 に加えて離散変数を潜在変数として扱える JointVAE の Chainer 実装を行い、2つのデータセットを用いて実験をしました。モデル間で公平な比較を行うために、encoder/decoder の構造や optimizer・バッチサイズ・iteration の数などは共通にした上で、モデルごとに30個のシードで学習を実施しました。

本記事では代表的な実験結果として、データセットのうちの dSprites データに関する結果を紹介したいと思います。このデータセットにはハートや楕円などの物体がサイズや位置を変えて配置された2次元画像が納められており、データを生成する真の因子には物体の種類・物体の大きさ・物体の回転・x軸座標・y軸座標の5種類があります。

図2. データセットの例

実験設定1

上で紹介したモデルを使用する時にまず気になるのが潜在因子の次元数をどのように設定するべきかだと思います。そこで、今回は連続変数を潜在変数とする BetaVAE, FactorVAE, DIPVAE-1/-2 に関して、潜在変数の次元数を真の生成因子の数の半分・同じ・倍の3パターンのモデルを用意して学習結果を比較しました。

実験設定2

実務で使用する際には、dSprites データのように因子の全組み合わせに対応する網羅的なデータを用意することは現実的ではないことが考えられます。そこで、x座標と物体の大きさに相関ができるように因子の組み合わせを半分削除したデータと、比較対象として因子の組み合わせをランダムに半分削除したデータを dSprites データセットから人工的に作成し、パフォーマンスがどの程度落ちるのかを検証しました。

結果

実験1

以下に、潜在変数のある次元だけを動かして、その他の次元を固定した時にデータがどのように変化するかを見た latent traversal という図を掲載します。一番左の列は VAE に与えた元のデータを示しており、その右隣の画像は VAE による再構成画像です。その他の列は潜在変数中の各次元を \(-1.5 \) から \(1.5 \) まで動かした時の画像の変化を順番に描画しています。

 

潜在変数を3次元とした場合
BetaVAE
FactorVAE
DIPVAE-1
DIPVAE-2

 

潜在変数を5次元とした場合
BetaVAE
FactorVAE
DIPVAE-1
DIPVAE-2

 

潜在変数を10次元とした場合
BetaVAE
FactorVAE
DIPVAE-1
DIPVAE-2

 

潜在変数の次元数が小さい場合は、各画像の左から2番目、つまり再構成画像を見ると、どのモデルを使っても画像の再構成が上手くいかず、物体の形がぼやけてしまっているのが見て取れます。どうやら次元数を少なくしすぎるのは問題のようです。しかし、BetaVAE は潜在変数を大きくしても再構成があまり上手くいっておらず物体の形がぼやけてしまっています。実はこの問題は FactorVAE を提唱した論文でも述べられており、BetaVAE に観測データ \(X \) と潜在変数 \(Z \) の相互情報量を小さくするような効果があるから起きるとされています。次元数を真の生成因子と同じ5次元にした場合は、FactorVAE はx軸座標とy軸座標、サイズの変化を disentangle できていますが、DIPVAE-1/-2 では entangled された特徴が学習されてしまっています。次元数が10次元の場合も FactorVAE が5つの因子を disentangle できているのに対して、DIPVAE-1/-2 は直感的ではない特徴を学んでしまっているように見えます。次元数を真の生成因子の数よりも多くした場合は全てのモデルで latent traversal 上で動かない次元が出てきていますが、FactorVAE では真の生成因子の学習が上手くいっていることから、実務で使用する際には潜在変数の次元数は出来るだけ余分にとっておいたほうがいいことが推察されます。

実験2

以下では実験1で定性的に性能がよかった FactorVAE による結果を掲載しています。x座標と物体の大きさに相関があるデータで学習したものは、latent traversal 上でもx座標の移動とともに物体の大きさが変化していることがわかります。また、y軸方向の移動とともに物体の形状が変化しているのをみると、その他の因子の学習にも悪影響を及ぼしていてそうです。ランダムな欠損を与えたデータでは、完全なデータと同じレベルとまではいかないものの、ある程度は5つの因子を獲得できています。今回は全データの半分を削除したので、データを削除しすぎた可能性もあります。しかし、実務で使用する際に生成因子の全ての組み合わせのデータの準備が難しい場合は、せめて因子に相関がないようなデータに整えた上で学習を行うべきである事がこの結果から推察できます。

完全なデータ

x座標と物体の大きさに相関があるデータ
ランダムな欠損を与えたデータ

 

メンターからのコメント

メンターを担当した PFN の仲田と吉川です。

本文中でも触れられている通り、disentangled な表現の教師なし学習は few-shot learning や domain adaptation といった分野への応用や、機械学習モデルの解釈性の向上が期待できます。これらは現実世界への機械学習の適用をする際にいつも直面する課題です。
深層学習などの先端技術による現実世界の課題解決をミッションとする PFN としても以前から取り組んではいるのですが、タスク自体の難しさはもちろん、問題設定をおこなうことも難しい分野です。インターン期間中は手法の再現性や各種文献の実装の読解などにお互い苦労しましたが、最終的には代表的な手法を一通り Chainer で実装し、様々なデータやパラメータ、評価指標を広く調査して頂いた蕭さんの今回の成果は、今後の PFN における研究開発にあたっての足がかりとなることと思います。

参考文献

PFNが提供する教育コンテンツについて

Hiroshi Maruyama

2019-10-07 15:38:56

PFNフェローの丸山(宏)です。2月にプログラミング教育についてのブログを書きました。またそれに合わせて制作した教材を利用して、6月に弊社カフェテリアで、小学生を対象にした体験教室を開催しました。この体験教室については、丸山(史郎)がロボットカーの体験教室について西澤が火星語翻訳を題材にした教材について書いています。今回、山梨大学と共同で、高専・大学学部向けの教材 ロボットカーで学ぶ深層学習の基礎 を開発しました。このブログでは、これら一連の教育関連の活動について、その意義と全体像をもう一度整理してみたいと思います。

また、付録に、現在PFNが提供する教育用コンテンツのリストがありますので、そちらもご利用ください。

古典的プログラミング

2016年に文部科学省が主宰する「小学校段階における論理的思考力や創造性、問題解決能力等の育成とプログラミング教育に関する有識者会議」は、議論の取りまとめを公表し、その中で

自分が意図する一連の活動を実現するために、どのような動きの組合せが必要であり、一つ一つの動きに対応した記号を、どのように組み合わせたらいいのか、記号の組合せをどのように改善していけば、より意図した活動に近づくのか、といったことを論理的に考えていく力

プログラミング的思考と呼び、それをこれからの時代における普遍的な能力として教育課程に組み込んでいく必要を訴えました。ここで言う「プログラミング」は、アルゴリズムを実行するステップを明示的に書き下すタイプの通常のプログラミングで、このようなプログラミング作られたソフトウェアをここでは古典的ソフトウェアと呼ぶことにしましょう。

ソフトウェア2.0

古典的プログラミングでは、「計算機にやってほしいこと」を記述するのに、計算のステップを明示的に計算機に指示するプログラミング方法しかありませんでした。しかし、それが計算機に対する唯一のプログラミング方法でしょうか。深層学習による帰納的プログラミングにおいては、入出力の例示(訓練データセット)を与えることによって「やってほしいこと」を記述します。Optunaのようなベイズ最適化ツールは最大化(最小化)したい関数の、特定の点の値を返す「オラクル」を記述することによって「やってほしいこと」を記述します。どちらも、計算のステップは記述しません。このようなプログラミングによるソフトウェアをTeslaのAndrej Karpathy氏はソフトウェア2.0と呼んでいます。

ソフトウェア2.0では、計算機内部で実行されるアルゴリズムを知らなくても構いません。「やってほしいこと」を伝える方法さえ知っていれば計算機というツールを使うことができのです。たとえば乗換案内というツールを考えてみましょう。「やりたいこと」は出発地と目的地を指定することで伝えることができます。場合によっては、航空便を使わない、とか時間よりも価格を重視する、とかの最適化もできます。乗換案内を実装している中のアルゴリズムをご存知でしょうか。基本は初期の人工知能研究の成果、たとえば手段目的分析(means-end analysis)などの探索アルゴリズムのようなものだと思います(私は中身を見たわけではないので、想像にすぎません)が、中身を知らなくても乗換案内を効果的に使うことができます。

乗換案内のような道具を使う際に大事なのは、その中身がどのようなメカニズムで実装されているかではなく、それが提供する機能、すなわち「A地点からB地点まで移動する最短時間(最短コスト)の経路を表示する」というものだと思います。機能さえ知っていれば、中のメカニズムを知らなくても使えるのです。私達が毎日使っているテレビ、スマホ、電車などは、その機能はよく知っていますが、中のメカニズムを正確に知っている人はほとんどいないと思います。それでも上手に使えます。同様に、これからの計算機は、古典的プログラミングを知らなくても、深層学習やベイズ最適化の「機能」だけ知っていれば使える時代が来るのだと思います。

小学生に対して私たちが教育コンテンツを提供するのは、このような未来を想定しているからです。

深層学習の正しい理解と普及

長期的には「やってほしいこと」を記述するだけのソフトウェア2.0的なプログラミングが可能になると思いますが、一方で、直近では深層学習という新しい技術を正しく理解し、社会問題の解決に効果的に使っていくスキルが求められます。深層学習は人工知能研究における偉大なブレークスルーですが、それだけで人間の知性のような、いわゆる「汎用人工知能」が実現できるわけではありません。ホーキング博士が言う「人間を超えるAI」は、まだSFの世界の話であり、現在の深層学習技術の延長上にはない、というのが多くの人工知能研究者の意見です。深層学習にできること、できないことを正しく理解し、それを等身大に発信していくことが私たちには求められています。

PFNが提供する「ディープラーニング入門 Chainerチュートリアル」などの教育コンテンツは、これは社会で実際に深層学習を利用する社会人の方々、あるいは卒業後にそのような職種につきたいという大学生・大学院生の方々に対して、この技術を正しく理解して、正しく有効に活用していただきたい、という意図で提供しているものです。このため、深層学習のベースとなる数学や確率・統計の理解を含め、記述の正確性に重点を置いたコンテンツになっています。

今回山梨大学の牧野先生・西﨑先生と共同で作らせていただいたコンテンツは、より間口を広くして、高等専門学校から大学学部レベルの学生の方々に、深層学習に興味を持っていただく内容になっています。このため、レゴ(R) マインドストーム(R) EV3というロボットカーを実際に深層学習で制御して走らせてみる、というハンズオンスタイルの教材になっています。また、ルールベースの古典的プログラミングと深層学習によるSoftware2.0のプログラミングを対比して学べるようになっています。深層学習の訓練(学習)を含めすべてのPythonプログラミングがRaspberry Pi上で完結するように設計されていて、クラウドに依存することなく、授業を実施することができます。このあたりは、ワークショップ型の授業の経験豊富な牧野先生・西﨑先生のノウハウが存分に活かされています。

今後もPFNは、将来を見通して、社会にとって必要な教育コンテンツを、初等教育からリカレント教育まで幅広く提供していきます。

PFN提供教育用コンテンツ一覧

いずれのコンテンツも、自習や学校での授業には自由にお使いいただけます。

大学・大学院・社会人向け

高校・高専・大学学部向け

初等教育向け 

 

微分可能なMPCのChainer実装および追加実験

Yo Iida

2019-10-04 14:30:30

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


こんにちは、2019年夏にPFNでインターンをしていた新幡です。大学では連続最適化の研究室に所属しています。PFNではモデル予測制御 (MPC; Model Predictive Control) を「微分可能」にするAmosら (2018) の論文“Differentiable MPC for End-to-end Planning and Control”[1] について、著者によるPyTorch実装のChainerへの移植と追加実験を行いました。MPCはモデルを用いて将来の状態を予測しながら制御を行う手法であり、化学プラントの制御などに用いられています。

【2019/10/7追記】Chainerへの移植実装はGitHubで公開しています。
https://github.com/pfnet-research/chainer-differentiable-mpc

1. OptNet

Amosらは、2017年に二次計画法を微分可能にする層として“OptNet: differentiable optimization as a layer in neural networks”[2] を提案しました。二次計画法を微分可能にすることで、勾配降下法を用いて二次計画法の目的関数や制約条件を、ネットワークの損失関数に対して最適化することができます。OptNetの順伝播は、二次計画問題を主双対内点法という収束するまで反復を繰り返す方法を用いて解いていますOptNetの誤差逆伝播は、主双対内点法を全て連鎖律で逆にたどるのではなく、最適解の満たすべき条件のうち等式で書けるもの (KKT行列) から効率的に偏微分を求めています。大量のデータを用いて学習する為に、二次計画問題を大量に解く必要があるので、Amosらはバッチで計算できるような主双対内点法を実装しており、著者実装は A fast and differentiable QP solver for PyTorch として公開されています。また、副メンターの酒井さんによるChainerへの移植の試みとして chainer-optnet があります

図1. OptNetの概要図

2. Differentiable MPC

OptNetで二次計画法を微分可能にする手法が提案されたので、有限離散時間線形二次レギュレータ (Linear-Quadratic Regulator; LQR) などの二次計画法を用いて解ける最適制御問題はOptNetを用いて微分可能にできます。しかし、LQR二次計画問題として解くのではなく、動的計画法を用いた方が効率的に解くことができることが知られています。Amosらは、LQRの順伝播の計算に動的計画法を用い、誤差逆伝播の計算もKKT行列の時間的構造を用いてOptNetより効率的に微分を求められるLQRを提案しました。

さらに有限離散時間MPCのようなコスト関数やダイナミクスが非線形な問題に対しても、微分可能にした論文がAmosらによるDifferentiable MPCです。著者による実装はアルゴリズムの主な部分が mpc.pytorch としてライブラリになっており、著者の実験コードは differentiable-mpc といレポジトリにあります。

3. 前提知識

3.1. LQR

LQRは一般的には、コスト関数が二次でダイナミクスの制約が線形、操作量が無制約な次のような形で表される最適制御問題です。

$$
\begin{align*}
&\underset{\tau_{1:T}}{\text{minimize}} & & \sum_t \frac{1}{2} \tau^T_t C_t \tau_t+c^T_t \tau_t \\
&\text{subject to} & & x_1 = x_\text{init}\\
& & & x_{t+1} = F_t \tau_t + f_t
\end{align*}
$$

ここで \(x\) は状態、 \(\tau\) は状態と操作量を連結したもの、 \(C\) はコスト関数の二次の項を表す行列、 \(c\) はコスト関数の1次の項を表すベクトル、\(F\) はダイナミクスを表す行列になります。Amosらは、LQRを動的計画法を用いて、ベルマン方程式を再帰的に解くことで解いています。詳しくは[3]を参照してください。

3.2. MPC

MPCはLQRと異なり、コスト関数は2次に限らず、ダイナミクスも線形に限りません。さらに、操作量に制約がつく場合もあります。元論文で扱ったMPCは以下の式です。

$$
\begin{align*}
&\underset{\tau_{1:T}}{\text{minimize}} && \sum_t C_{\theta, t}(\tau_t) \\
& \text{subject to } && x_1= x_{\mathrm{init}}\\
&&& x_{t+1} = f_{\theta}(\tau_t)\\
&&& \underline{u} \leq u \leq \overline{u}
\end{align*}
$$

Amosらは、コスト関数を二次近似、ダイナミクスを一次近似して、収束するまでLQRソルバを繰り返し用いるiLQRという手法を用いて解いています。また、制約については、Tassaら (2012) による“Control-Limited Differential Dynamic Programming”[4] と同じように扱っています。

4. 応用

Differentiable MPCの応用として、Amosらが行っているのがエキスパートの操作列を模倣する模倣学習 (imitation learning) です。Amosらによる模倣学習は、ダイナミクスやコスト関数をパラメータ化した形で表して、エキスパートの操作列との二乗誤差をネットワークの損失関数としてパラメータを最適化させています。最適化によって得られたダイナミクスやコスト関数をMPCに用いることで、エキスパートの操作列を模倣する方策を得られると期待できます。Amosらは、実験設定として、倒立振子 (inverted pendulum) を題材に、学習するものがダイナミクスのパラメータのみ・コスト関数のパラメータのみ・両方の三通りの学習を試しています。

図2. 模倣学習の設定

例として、ダイナミクスを既知として、コスト関数をパラメータ化した形で学習を行うと次のようになります。エキスパートの操作列から、正しく倒立振子を安定化させることができていることがわかります。

図3. 学習したコスト関数を用いた制御

5. 追加実験

追加実験として、コスト関数をAmosらのように特定の形にパラメータ化した形ではなく一般の二次関数の場合もうまく学習できるのかを試しました。ここでAmosらのパラメータ化を詳しく説明すると、以下の数式のようになっていて、\(q_{\text{logit}}\)と\(p\)という二つのベクトルをパラメータとしています。

$$
\begin{align*}
q &= \mathrm{sigmoid}(q_{\rm{logit}})\\
C(\tau) &= \frac{1}{2}\tau^T q \tau + (\sqrt{q} \circ p)^T \tau
\end{align*}
$$

追加実験として試したパラメータ化は、半正定値行列\(Q\)とベクトル\(p\)をパラメータとして用いてコスト関数をより多くのパラメータで表現しています。

$$
\begin{align*}
C(\tau) = \frac{1}{2}\tau^T Q \tau + p\tau
\end{align*}
$$

5.1. 真のコスト関数がAmosらのパラメータ化で表現できる場合

図4. 真のコスト関数がAmosらのパラメータ化で表現できる時

この場合は、真のコスト関数の構造を取りいれているAmosらによる手法の方が損失関数の値が下がりました。

5.2. 真のコスト関数がAmosらのパラメータ化で表現できない場合

真のコスト関数がAmosらのパラメータ化で表せないように問題設定を変えました。

この場合、一般的な二次関数のパラメータを用いた手法とAmosらの手法を比較すると、損失関数がどの程度まで下がるかは同等でしたAmosらの手法では、真のコスト関数を表現できないので、一般的な二次関数を用いて学習させる方が損失関数の値が下がることを期待していたのですが、これは意外な結果でした。Amosらは、LQRの場合に、ダイナミクスを一般的な行列の形にして模倣学習を行い、その際は半分程度は損失関数がうまく下がらないという現象を確認していますが、これを模倣学習の損失関数が、ダイナミクスのパラメータに対して、勾配降下法では最適化することが難しい非凸な関数であったからと結論づけています。今回、一般的な形のコスト関数でうまく学習できなかったのも、コスト関数を一般的な形にすると、損失関数がコスト関数のパラメータに対して非凸な関数になったからではないかと考えられます。

図5. 真のコスト関数がAmosのパラメータ化で表現できない時

6. 感想

今回のインターンでは、Differentiable MPCのChainerへの移植を行い、色々と実験設定を変えてみました。コスト関数を凸なニューラルネットワークで置き換えられるとおもしろそうだなという思いつきから、まずはコスト関数のパラメータを増やして実験してみました。元論文では模倣学習の損失関数が制御器のパラメータに関して非凸な関数になることがあると指摘されており、追加実験でもパラメータを増やしたところあまり損失関数の値が下がらないという結果になりました。

Differentiable MPCは理論、実装共にかなり複雑で、Chainerにライブラリを移植するのにかなり苦労し、時間がかかってしまいましたが、メンターさん方の助けもあってなんとかできました。ありがとうございました。

参考文献

[1] B. Amos, I. Jimenez, J. Sacks, B. Boots, and Z. Kolter. “Differentiable MPC for End-to-end Planning and Control” In NIPS’18 Proceedings of Advances in Neural Information Processing Systems. Available: https://arxiv.org/abs/1810.13400

[2] Brandon Amos, and J. Zico Kolter, “OptNet: differentiable optimization as a layer in neural networks” In ICML’17 Proceedings of the 34th International Conference on Machine Learning. Available: https://arxiv.org/abs/1703.00443

[3] Sergey Levine.  Optimal control and planning. berkeley cs 294-112:  Deep reinforcement learning. Available: http://rail.eecs.berkeley.edu/deeprlcourse-fa17/f17docs/lecture_8_model_based_planning.pdf

[4] Yuval Tassa, Nicolas Mansard and Emo Todorov. “Control-Limited Differential Dynamic Programming” ICRA’14 IEEE International Conference on Robotics and Automation. Available: https://homes.cs.washington.edu/~todorov/papers/TassaICRA14.pdf


メンターからのコメント

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

PFNは深層学習に強みがありますが、現実の問題を解決するには深層学習だけでは不十分なこともあり、最適化や制御の技術を組み合わせて用いることも多いです。しかし、昨年までのインターンシップではそういったバックグラウンドの学生の方にはあまりリーチ出来ていませんでした。

そこで、今年のインターンシップ募集でのテーマ「機械学習アルゴリズムの応用 (数理最適化、シミュレーション、時系列予測など) に関する研究開発」では「数理最適化」もキーワードに含め、結果として最適化のバックグラウンドを持つ学生さんとの研究開発を幾つか実施することができました。微分可能MPCに関するこのテーマはその一つです。

今回のテーマは、再現実装の負荷がメンター二人の想定していたよりも重く、新幡さんには随分苦労させてしまいましたが、再現実装と追加実験までを行っていただくことができました。社内の他のプロジェクトでも深層学習とMPCを組み合わせて用いており、今回の新幡さんの成果も今後それらにうまく活用していきたいと考えています。

スポーツ映像に対するシーンのアノテーション効率化

Tatsuya Takamura

2019-10-02 12:03:57

本記事は、2019年インターンシップとして勤務した佐々木 克仁さんによる寄稿です。


はじめまして。PFNの2019年夏季インターンシップに参加させていただいた東京大学修士1年の佐々木克仁です。大学ではHCIの研究をしています。WEB開発が好きです。

テーマとその背景

今回のインターンシップで私が取り組んだ研究テーマは「スポーツ映像に対するシーンのアノテーション効率化」です。

PFNでは、スポーツ映像の中でチームが取っている戦術を推定し、スポーツの戦術解析に応用するシステムを開発しています。このような推定を実現する機械学習モデルを学習するためには、チームが取っている戦術とその時間範囲(以降シーンと呼びます)がスポーツ映像にアノテーションされた大量のデータセットが要求されます。しかし、スポーツ映像におけるシーンの戦術レベルでの詳細な区別を一般の人々が行うのは困難で、そのスポーツに精通した専門家しかアノテーションできず、彼らの限られたリソースを効率的に利用するためにアノテーションの効率化が必要となります。

今回私が着目したのは「シーンの境界線を決めるのに時間がかかっている」という課題でした。アノテーターは先頭からスポーツ映像を見ていって各シーン間の境界線の時間を記録することでアノテーションしていきます。境界線はルールに基づいて決定するのですが、この作業に時間がかかっており、またアノテーターのストレスに繋がっています。インターンシップではこの課題を解決するための取り組みを行いました。

手法

私が取り組んだ手法では、各シーンに対してアノテーターは「シーンの境界線を決める」代わりに「シーンの中の適当な一時点を決める」作業を行います。これによってシーンの境界線を決める労力が削減されるためアノテーションが効率化されると考えられます。以降では「シーンの境界線を決める」アノテーションを「Boundary型」、「シーンの中の適当な一時点を決める」アノテーションを「Timestamp型」と呼びます。Timestamp型アノテーションの考え方は[1]から取り入れました。

annotation-image

図1: アノテーターはシーンの中の適当な一時点を決める

しかし、Timestamp型のアノテーションはそのままデータセットとして利用することはできず、一つのTimestampを元にそのTimestampが示すシーンの境界線を推定する必要があります。そこで今回は、学習させた機械学習モデルの反応を見て、与えられたTimestampを元に暫定的に決めた境界線から徐々に境界線を更新させるという方法を採用しました(図2)。境界線の更新と機械学習モデルの学習を並行して行うことで、相互に作用しながら解に近づいていきます。

iteration

図2: Timestampから境界線を推定する手法の概要

境界線は、機械学習モデルが出力した各クラスの確率分布に基づいて更新されます(図3)。図2は、クラスAとクラスBのシーンの境界線を示しています。現在の境界線(点線)において機械学習モデルが出力したAの確率とBの確率の差Δが、閾値よりも大きい場合に境界線をB方向に更新します。更新の大きさは、Aの確率を示す曲線とBの確率を示す曲線の交点を基準に学習率をかけたものとなります:

eq1

ここで、bは境界線の時刻、cは曲線の交点の時刻、rは学習率です。

boundary-update

図3: 境界線の更新

この境界線の更新手法は、[2]を参考にして改良を加えたものになっています。[1]の方法は、Backgroundクラスが大部分を占めるAction Recognitionのタスクでは有効ですが、スポーツ映像のようなほぼ全てのフレームがBackgroundでないクラスを持つタスクではうまく機能しないと考えられるため採用しませんでした。

実験・評価

境界線の推定精度

まず、境界線を推定する手法が適切に機能するかどうかをシミュレーションによって評価しました。アノテーターによるTimestamp型アノテーションのシミュレーションを、Ground-Truthのデータにおけるそれぞれのシーンの時間範囲からガウス分布に基づいてサンプリングすることで行います。推定された境界線の精度は、Ground-Truthの境界線と推定された境界線のIoU(Intersection over Union)によって評価しました。IoUは2つの領域が重なっている割合を示す値であり、IoUが高いほど境界線の推定精度が高いことを示しています。

以下に結果を示します(図4)。「学習→境界線の更新」の繰り返しを行うたびにIoUの平均値が向上することが示されています。最終的に0.76まで到達しています。今回推定された境界線に基づいたデータセットの有用性の検証は今後の課題となります。

estimated boundary

図4: IoUの平均値(横軸は境界線の更新回数)

Timestamp型アノテーションの効率

次に、Timestamp型アノテーションによって実際にアノテーションの速度が向上することをユーザースタディによって検証しました。ユーザースタディに向けてBoundary型とTimestamp型のWEBインターフェースを実装しました(図5)。被験者としてスポーツ解析の専門家2人にご協力いただきました。被験者は制限時間内に可能な限りのアノテーションを行い、それぞれの方式でアノテーションできる数を比較します。今回は被験者数が十分ではありませんが、初期検討の材料としての実験とし、追加実験は今後の取り組みとします。

compare mode

図5: アノテーションツールの実装(左はBoundary型、右はTimestamp型)
※スポーツ映像の部分はイメージ図です

ユーザースタディの結果、Timestamp型ではBoundary型の約2倍の速度でアノテーションできることが分かりました。アノテーションが速くなった原因としては、当初想定していた境界線を決める時間が削減されたこと以外にも、Timestamp型のほうがツールとして操作が容易であったこともあるようでした。被験者となっていただいた専門家の方からは「直感的」「映像を見ている感覚でできるのでストレスが少ない」という今回の手法に対する肯定的なフィードバックをいただくことができました。一方で、アノテーターによってシーンの中のどのタイミングでアノテーションするかの傾向が異なるという課題も発見されました。シーンの中のどのタイミングでアノテーションするるかは境界線の推定における初期値を決める重要な因子です。ユーザスタディを実際に行ったからこそ判明した重要な発見でした。

研究のまとめ

今回の研究では、スポーツ映像に対するシーンのアノテーションを効率化するための手法として、Timestamp型のアノテーションに取り組みました。Timestampからシーンの境界線を推定する手法では、Ground-Truthと比較してIoUで0.76の精度を実現しました。また、スポーツ解析の専門家2名によるユーザースタディによってTimestamp型のアノテーションでは従来の方式より2倍速くアノテーションできることが分かりました。今後の課題としては、シーンの境界線推定の精度が得られた結果で十分であるかどうか検証する必要があり、またユーザによるアノテーションのタイミングのばらつきに対処する必要があります。

インターンシップの感想・謝辞

今回2ヶ月間のインターンシップに参加させていただき、非常に充実した時間を過ごすことができました。2ヶ月もの間1つの研究について考え続けるのはとても楽しく、かつてない経験をさせていただきました。PFN社員の方々のレベルが非常に高く、せっかくこの環境にいるのだから難しい問題に取り組んでみようと前向きな気持ちでチャレンジすることができました。また、インターンの同期も同世代と思えないほど実力のある人ばかりで自分の至らない部分を知ることができ、多大な刺激を受けました。本当に参加してよかったと思えるインターンシップでした。

最後に、メンターをはじめとしたチームの皆さま、研究のサポートをして頂き誠にありがとうございました。また、ポスターセッションでフィードバックをくださった皆さま、適切な助言をありがとうございました。

参考文献

[1] Moltisanti, Davide, Sanja Fidler, and Dima Damen. “Action Recognition from Single Timestamp Supervision in Untrimmed Videos.” Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 2019.

[2] Ding, Li, and Chenliang Xu. “Weakly-supervised action segmentation with iterative soft boundary assignment.” Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 2018.

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