表題番号：2013A-969 日付：2014/04/09
研究課題凸最適化と確率伝搬法に基づいた高性能な確率推論アルゴリズムの開発
研究者所属（当時） 資格 氏名
（代表者） メディアネットワークセンター 助教 堀井　俊佑
研究成果概要
確率変数の間に存在する因果関係をグラフで表現したグラフィカルモデルにおいて，観測できる変数から観測できない変数を推定する確率推論の問題を扱った．
確率推論は、誤り訂正符号の復号問題や、自然言語処理における統計的係り受け解析、画像処理における画像セグメンテーションなど様々な問題に応用されている．
本研究では，凸最適化に基づいた推論アルゴリズムの設計を行い，その性能を解析的・実験的に評価した．
本研究のポイントは，1) 様々な問題をグラフィカルモデル上の確率推論問題として定式化し，2) 各問題に適した形で凸最適化に基づいた高速な推論アルゴリズムを構築することであった．
様々な問題に対して高性能な推論アルゴリズムを得ることが主な研究目的であった．
理論的な側面からは，確率推論の問題は整数計画問題の部分クラスを与えていると考えられるが，どのような問題のクラスが効率的に，また良い近似精度で解く事が出来るかを明らかにすることは意義がある．
現実の様々な問題をグラフィカルモデルの確率推論の問題として定式化した場合の性質を，問題の数学的構造により分類し，それぞれの問題に対して従来提案されている推論アルゴリズムを整理した．
また，確率伝搬法・線形計画法・双対分解などを組み合わせた新たなアルゴリズムを提案し，アルゴリズムの計算量などの理論評価，コンピュータシミュレーションによる数値実験での評価を行った．
問題の一つとして，符号化CDMAシステムにおける復号問題を扱った．
この問題をグラフィカルモデル上の確率推論問題として定式化し，拡張ラグランジュ法とADMMとよばれるアルゴリズムを適用することで，効率的かつ高性能な復号アルゴリズムを得ることができた．
また，他の問題として，相関を有する複数の低ランク行列の補完問題を扱った．
この問題を凸最適化問題として定式化し，拡張ラグランジュ法とADMMを適用することで，従来のものよりも精度の良い補完アルゴリズムを得ることができた．