命題論理に基づく確率モデルのための二分決定グラフと順序符号化を用いた効率的なEMアルゴリズム

摘要

本論文では命題論理に基づく確率モデルに対するEMアルゴリズムを二分決定グラフと順序符号化を用いて効率的に実行する方法を提案する．提案手法の時間／空間計算量は観測を表現するBDDのサイズに比例し，noisy-OR モデルと隠れマルコフモデルに対する確率学習計算量は従来法と一致する．更に，提案手法は論理に基づくアブダクションより得られた任意の論理式で表される仮説を統計的に評価可能である．本論文ではアブダクションにより得られたバイオデータに関する仮説を提案手法により評価し，化学的にに妥当な仮説が上位にランキングきれることを確認した．