表題番号:2011B-100 日付:2012/05/17
研究課題整数計画法に基づいた高性能な確率推論アルゴリズムの開発
研究者所属(当時) 資格 氏名
(代表者) 理工学術院 助手 堀井 俊佑
研究成果概要
確率変数の間に存在する因果関係をグラフで表現したグラフィカルモデルにおいて,観測できる変数から観測できない変数を推定する確率推論の問題を扱った.
グラフィカルモデルにおける標準的な確率推論アルゴリズムとして確率伝搬法が広く知られているが,近年,凸最適化に基づいた推論アルゴリズムの研究が盛んに行われるようになっている.
本研究では,主に凸最適化に基づいた推論アルゴリズムの設計を行い,その性能を解析的・実験的に評価した.
特に,応用としてストリーム暗号の鍵推定,誤り訂正符号の復号,マルチコンピュータシステムにおける故障診断の問題を扱った.
ストリーム暗号は,平文をビット単位あるいはバイト単位などで逐次、暗号化する暗号方式である.
暗号の安全性評価のため,暗号の鍵推定に関する研究が重要な研究課題となる.
本研究においては,一部のストリーム暗号のクラスにおいて確率推論アルゴリズムによる鍵推定が効率的に行えることを示した.
誤り訂正符号は,ノイズのある通信チャネルを通してメッセージを高信頼度で通信する為の技術の1つで,LDPC 符号と呼ばれる符号に対して確率伝搬法に基づく復号を行うことで,シャノン限界と呼ばれる理論的限界に近い性能を得られることが知られている.
近年,LDPC 符号の復号法として,確率伝搬法に代わる新たな復号法として,線形計画法に基づいた復号法に関する研究が盛んに行われているが,本研究では,複雑な通信路モデルにおいても凸最適化に基づいた推論アルゴリズムが有効に働くことを示した.
マルチプロセッサシステムあるいはマルチコンピュータシステムにおける故障ノードを発見する問題は,古くから様々なモデルに対して研究が行われてきた.
本研究では,この問題が確率推論の問題として定式化が可能であり,凸最適化に基づいた故障診断システムを構築した.数値シミュレーションにより,提案したアルゴリズムが従来のものより良い性能を示すことを確認した.