4 MapReduce 粒子フィルタ
5.3 MapReduce 反復あり MRPF の結果
前節で述べた非線形状態推定問題に対し，T = 1とし てMapReduce反復ありMRPFを適用した．計算処理 にかかった時間を表2に、また各粒子数毎のデータ転送 にかかった時間を表3にそれぞれ示す。
計算処理時間の短縮に関しての並列化の効果は MapRe-duce反復無しMRPFの結果とほぼ同様の結果となって いる。しかし、50万粒子、100万粒子ではすべてのクラ スタ数に対してデータ転送時間が計算処理時間を上回っ ている。16クラスタ、100万粒子使用時のデータ転送時 間は計算処理時間の約12倍もかかっている。このため、
計算時間の短縮のためにはデータ転送時間がボトルネッ クとなることが分かる。また、実験結果を100倍して
T = 100に対する100万粒子使用時の計算時間の推定
を行うと、1クラスタでは約32時間、16クラスタでは 約23時間となった。
表3: データ転送時間[秒]
0.1M 0.5M 1M
75 351 761
6 考察
MapReduce反復ありMRPFに関しては、100万粒子 使用時に関して並列分散化の効果が大きく表れている。
16クラスタ使用時には1クラスタ使用時に比べ約10.6 倍の高速化が実現されている。50万粒子、10万粒子の 使用時に100万粒子使用時と比べ並列分散化の効果が低 いのは、並列分散化による計算速度は分散させる粒子の セット数に依存しているためと考えられる。1万粒子×
10セット（10万粒子）に対して16クラスタを利用する のは、目的に対して不適切である。そのため、分散させ る粒子のセット数と使用するクラスタ数による費用対効 果などの関係性を調べることは今後の課題である。
MapReduce反復ありMRPFにおけるデータ転送時
間の問題は、ローカルなクラスタ計算機を用いることや ローカリティを有したネットワークデータ転送を必要と しないクラウドコンピューティングを用いることで解決 できる。しかし、本論の趣旨から外れるため、ここでは 議論しない。また計算処理時間に関しては、表2よりア ルゴリズムによる並列分散化の有効性を確認できるてい る。そのため、ローカリティを伴うMapReduceフレー ムワーク実行環境を有するサービスが提供されること で、本アルゴリズムは実用可能となるであろう。
本論で述べたMRPFのアルゴリズムは比較的単純な粒 子フィルタのMapReduceでの実装である．MapReduce の特性を活かした効率の良いアルゴリズムの考案は今後 の課題である．
7 むすび
本論ではMapReduceフレームワークにおける粒子
フィルタアルゴリズムについて述べた．2種類の MapRe-duce粒子フィルタアルゴリズムを提案・実装し，クラ ウドコンピューティングのサービスを使用して計算時間 の短縮について検証した．その結果クラウドコンピュー ティングとMapReduceフレームワークを用いた並列分 散処理化の効果を確認することができた．これにより，
クラスタコンピュータを持たない研究者・実務家におい ても大量の粒子を使用する粒子フィルタの実装と応用が 可能であることを示すことができた．近年，粒子フィル タの応用はマーケティングの分野へも広がりつつあり，
大規模統計モデルを実務へ応用したい実務家にとって有 益な指針を示すことができた．より大規模なモデルでの
検証や実問題への応用は今後の課題である．
謝辞
本研究では，経済産業省サービス工学研究開発事業IT とサービスの融合による新市場創出促進事業の支援を受 けている．
参考文献
[1] N. J. Gordon, D. J. Salmond and A. F.
M. Smith, “Novel approach to nonlinear/non-Gaussian Bayesian state estimation,” The Pro-ceedings of IEE F, Vol. 140, No. 2, pp. 107-113, 1993
[2] G. Kitagawa, “Monte Carlo filter and smoother for non-Gaussian nonlinear state space model,”
Journal of Computational and Graphical Statis-tics, Vol. 5, No. 1, pp. 1-25 1996
[3] A. Doucet, J. de Freitas and N. Gordon, Sequen-tial Monte Carlo Methods in Practice, Springer-Verlag, 2001
[4] 樋口知之, “粒子フィルタ”, 電子情報通信学会誌, Vol.88, No.12, pp.989-994, 2005
[5] M. Isard and A. Blake, “CONDENSATION-Conditional Density Propagation for Visual Tracking”, International Journal of Computer Vi-sion, Vol29, No.1, pp.1573-1405, 1998
[6] S. Thrun, W. Burgard and D.Fox, Probabilistic Robotics, MIT Press, 2005
[7] K. Nakamura, N. Hirose, B.H. Choi and T.
Higuchi, “Particle Filtering in Data Assimilation and its Application to Boundary Condition of Tsunami Simulation Model”, Data Assimilation for Atmospheric, Oceanic and Hydrologic Appli-cations, pp.353-366, S.K. Park and L. Xu (ed.), Springer, 2009
[8] S. Nakano and T. Higuchi, “Estimation of a long-term variation of a magnetic- storm index us-ing the mergus-ing particle filter”, IEICE Trans.
on Information and Systems, Vol.E92-D, No.7, pp.1382-1387, 2009
[9] M. Nagasaki, R. Yamaguchi, R. Yoshida, S.
Imoto, A. Doi, Y. Tamada, H. Matsuno, S.
Miyano and T. Higuchi, “Genomic Data Assim-ilation for Estimating Hybrid Functional Petri Net from Time-Course Gene Expression Data”, Genome Informatics, Vol.17, No.1, pp.46-61, 2006 [10] R. Yoshida, M. Nagasaki, R. Yamaguchi, S.
Imoto, S. Miyano and T. Higuchi, “Bayesian learning of biological pathways on genomic data assimilation”, Bioinformatics, Vol.24, No.22, pp.2592-2601, 2008
[11] K. Nakamura, R. Yoshida, M. Nagasaki, S.
Miyano and T. Higuchi, “Parameter Estimation of In Silico Biological Pathways with Particle Filter-ing Towards a Petascale ComputFilter-ing””, The Pro-ceedings of 14th Pacific Symposium on Biocom-puting, pp.227-238, 2009.
[12] 佐藤、樋口, “動的個人モデルによる消費者来店行 動の解析”,日本統計学会誌, Vol.38, No.1, pp.1-19, 2008
[13] 中野、上野、中村、樋口、 Merging Particle Filter とその特性 、統計数理、Vol.56 No.2、pp. 225-234，
2008．
[14] S. Nakano, G. Ueno and T. Higuchi, “Merging particle filter for sequential data assimilation”, Nonlinear Processes in Geophysics, Vol.14, No.4, pp. 395-408, 2007
[15] J.H. Kotecha and P.M. Djuric, “Gaussian particle filtering”, IEEE Transactions on Signal Process-ing, Vol.51, No.10, pp.2592-2601, 2003
[16] 日経BP社出版局,クラウド大全,日経BP社, 2009 [17] J. Dean and S. Ghemawat, “MapReduce: Simpli-fied Data Processing on Large Clusters”, OSDI’04:
Sixth Symposium on Operating System Design and Implementation, 2004
[18] D. Borthaku, “The Hadoop Distributed File Sys-tem: Architecture and Design”, Retrieved from lucene.apache.org/hadoop, 2007.
[19] C-T. Chu, S.K. Kim, Y-A. Lin, Y.Y. Yu, G.
Bradski, A.Y. Ng and K. Olukotun, “Map-Reduce for Machine Learning on Multicore”, Advances in Neural Information Processing Systems 19, 2006
[20] C. Ji, C. Vecchiola and R. Buyya, “MRPGA: An Extension of MapReduce for Parallelizing Genetic Algorithms”, 4th IEEE International Conference on eScience, pp.214-221, 2008
[21] R. E. Kalman, “A new approach to linear filtering and prediction problems,” Transaction of ASME - Journal of Basic Engineering, Vol.82 pp. 35–45, 1960
[22] G. Kitagawa, “Non-Gaussian State-Space Model-ing of Nonstationary Time Series”, Journal of the American Statistical Association, Vol.82, No.400 pp.1032-41, 1987
[23] 中村、上野、樋口, “データ同化：その概念と計算ア ルゴリズム”, 統計数理, Vol.53, No.2, pp.211-229, 2005
情報論的学習理論テクニカルレポート2009
Technical Report on Information-Based Induc-tion Sciences 2009 (IBIS2009)
Virutual Concept Drift 環境における RBFNN のモデル選択
Model selection for RBFNN under Virtual Concept Drift Environments
山内康一郎
∗Abstract: In this research, a model-selection criterion for RBFNN under virtual concept drift environments is proposed. Under such environments, the prior distribution of learning samples is changing over time so that online learning tasks usually cause catastrophic forgetting. Such environments are parts ofcovariate shift.
First of all, a statistical model of such environments is constructed. Then, we applied the learning strategies under covariate-shift using the statistical model. The method also provides the model selection criterion. Moreover, several strategies for reducing the com-putational complexity are also discussed.
Keywords: Virutal Concept Drift, 追記学習，共変量シフト，RBFNN,汎化誤差，分布予 測，t分布,情報量基準
1 まえがき
同時分布P(x, y) =P(y|x)P(x)から発生する学習サ ンプル(xb, yb) (b= 1,2,· · ·)によって，入力ベクトルx と出力yとの間の条件付き分布P(y|x)をRadial Basis Function Neural Network(RBFNN)に学習させること を考える．これをonline学習で実現するには，独立かつ 同一分布(i.i.d)のxが与えられることを前提としなけれ ばならない．しかし，現実の環境ではP(x)自体が時間 と共に変化することが多くonline学習がCatastrophic forgettingを起こして失敗する．これをここではVirtual Concept Drift環境[1]と呼ぶ．
この問題を克服するため多くの研究者が追記学習法 を提案してきた [2–9]. これらのシステムは忘却を抑制 しつつも，個々の学習サンプルを一度提示されるだけで 学習が完了するというone-pass-learningを可能とする．
これは，学習サンプル提示直後に運用期間に移ったネッ トワークが，いかなる入力が与えられても可能な限り誤 りリスクを少なくするための学習戦略である．つまり，
少なくとも既学習サンプルに似た入力に対しては確実に 正解できるようにしておくことによって，誤りリスクを 最小限に抑えようとするヒューリスティックな学習戦略 である．これはすなわち，未来に与えられるサンプル分 布が既学習サンプル分布を包含し，未知のサンプルを含
∗中部大学工学部 情報工学科,〒487-8501愛知県春日井市松本町 1200, tel. 0568-51-9391, e-mail [email protected], Chubu University Department of Information Science, 1200, Matsumoto-cho, Kasugai-shi, Aichi, 487-8501, JAPAN
む分布であることを仮定しており，既学習サンプルその ものとは異なる分布であることを仮定した学習戦略と言 える．
一方，近年，学習サンプルの分布とテストサンプルの 分布が異なる場合の学習戦略に関して深い議論がなされ るようになってきている(e.g [10] [11]). このような環境 のことを一般に共変量シフト(Covariate Shift)と呼び，
テストサンプルに対する誤差を最小にする重みつき評価 関数や，モデル選択基準も開発されている．もしこれら の知見を追記学習法に適用できれば，理論的に妥当な追 記学習アルゴリズムとこれに適したモデル選択法の両方 を構築できる可能性がある．
しかしながら，追記学習ではテストサンプル分布は未 来に提示される新しいサンプルに相当するため，未知で あると仮定せねばならない．残念ながら従来の研究には このテストサンプルの分布を予測する研究はほとんど見 当たらず，これまでの研究成果をそのまま追記学習に適 用することができない．
そこで筆者は，既に与えられたサンプルから，未来に提 示されるサンプルの分布を予測する方法を考案し，これ を使用した追記学習アルゴリズムの構築を試みた[12,13]．
さらに，このような環境に適したRBFNNのモデル選 択基準を与え，その性能を評価した[14]．本研究ではこ れに加えて計算量の削減方法について考察を行った．
次節2ではここで想定する学習器について説明する．
3では追記学習環境のモデルとして未来に提示されるサ ンプルの予測分布の導出を試みる．4では3で求めた予
測分布を用いたモデル選択付き追記学習アルゴリズムを 示す．6ではいくつかのベンチマークテストの結果を示 し，7でまとめる．
2 想定する学習システム
本研究では以下のように簡単化した追記学習システム を仮定する(図 .1)．すなわち，Radial Basis Function Neural Network(RBFNN)の横に提示された学習サンプ ル全てを保持するバッファが設けられてある．システム は学習サンプルの収集期間とリハーサル期間(再学習期 間)とを繰り返す．
これは，各々の学習期間において新しいサンプルのみ ならず過去の学習サンプルの再学習も行うタイプの追記 学習法[2, 3, 5–7, 9]に共通する基本的な構造となっいる．
(x1, F(x1 ))
x fθ(x)
(xnew , F(xnew))
Append new instances Rehearsal
(x2, F(x2 ))
Buffer RBFNN
図1: 本研究で仮定する学習システム
但し，ここでは簡単のためバッファのサイズに制限は 無く，無限個貯められるものとする．またリハーサル期 間中，RBFはバッファに貯められた全サンプルをオフ ライン学習するものとする．またRBFは毎度リセット され学習と後述するモデル選択とを最初からやり直すも のとする．このように新しいサンプルが与えられる度に 学習をやり直すことからRBFNN単体で見た場合には 追記学習とはかけはなれているように見えるかもしれな いが，バッファを含めた本学習システム全体に対しては，
逐次的に学習データを与える形となっている．
fθ(x)をRBFNNの出力値とすると，
fθ(x) =
∑M j=1
wjexp (
−kx−ujk2 2v2j
)
, (1)
ここにM は隠れユニット(Kernel)の数である．
ここでの学習の目的は以下の評価関数を最小化するこ とである．
E=
∫
(F(x)−fθ(x))2q(x)dx, (2) ここにF(x)は望ましい出力値を表し，q(x)は真の入 力分布を表している．q(x)は学習サンプルの分布P(x) とは異なるものであることに注意する．
3 追記学習環境のモデル化
共変量シフト環境下での学習では以下のような重みつ き誤差関数を使用する．
E=∑
b
W(xt){
yt−fθ(xt)}2
(3)
ここに(xt, yt)は各々の学習サンプルを表す．W(x)は 各々のサンプルの重みを表し，
W(x) = (q(x)
P(x) )λ
(4)
である．ここにP(x)は学習サンプル分布，q(x)はテス トサンプル分布を表す．0≤λ≤1は平坦化パラメータ である．
追記学習ではq(x)は将来提示されるサンプル全体の 分布を表すものと仮定せねばならない．すなわち，q(x) をP(x)から予測する必要がある．これを如何にして行 うかがここでの主要課題となる．