[2Win5] Poster session 2

[2Win5-08] Accelerating the RAI algorithm using parallel computing and recursion in Bayesian network structure learning

〇Hirotaka Nishikori¹, Ryota Miyagi¹, Hiroshi Nakamura¹, Hideki Takase¹ (1.The University of Tokyo)

Keywords:Bayesian network, Probabilistic Graphical Model, Bayes

確率的グラフィカルモデルの一種であるベイジアンネットワークの構造学習手法として，近年では高速に動作する制約ベースの手法が多く提案されており，中でもRAIアルゴリズムは制約ベースの構造学習手法として最も高速な学習を実現している．しかしながら，データ数や変数の数が大きい場合は依然として学習が困難である．
本研究では，アーキテクチャおよび数理的な観点からRAIアルゴリズムの高速化を目指す．アーキテクチャの観点からは，C++で実装したRAIアルゴリズムに対して，並列処理可能な頻度表計算についてOpenMPを適用して高速化を実現する．数理的な観点では，RAI アルゴリズムの再帰的な部分構造への分解という性質を利用して，事前に部分構造の頻度表を計算して保持しておきその周辺化によってCIテストを高速に行う手法を提案する．
評価実験では，特にデータ数が大きい場合に従来手法と比べて高速であることが確認された．提案手法は学習データの多い大規模なネットワークの学習において有用である．