講演抄録/キーワード |
講演名 |
2007-10-16 11:15
尤度最大化問題の複雑さ ○渡辺 治(東工大) COMP2007-42 |
抄録 |
(和) |
Most Likely Solution problem(MLS 問題と略記)の一般形を導入する.
これは与えられた確率モデルのもとで最大尤度解を探索する問題である.
MLS 問題は最悪時では NP-困難となることが多いが,
ここでは,それらの平均時の計算の複雑さを議論することを考える.
とくに,自然な入力分布として,
各 MLS 問題で仮定している確率モデルのもとでの平均時の計算の複雑さを議論することを提案する.
そのような MLS 問題の例を 3 つあげ,
それらの問題に対して「平均的に」有効である
メッセージ伝播アルゴリズム(例:確率伝播アルゴリズム)を紹介する. |
(英) |
We introduce Most Likely Solution problem,
a task of finding a most likely solution (MLS in short)
for a given problem instance
under some given probability model.
Although many MLS problems are NP-hard,
we propose, for these problems,
to study their average-case complexity
under their assumed probabality models.
We show three examples of MLS problems,
and explain that
``message passing algorithms''
(e.g., belief propagation)
work reasonably well for these problems. |
キーワード |
(和) |
最大尤度解 / 探索問題 / NP困難 / 平均時計算複雑さ / 解埋め込み確率モデル / メッセージ伝播アルゴリズム / / |
(英) |
most likely solution / solution search problem / NP-hard / average-case complexity / planted solution model / message passing algorithm / / |
文献情報 |
信学技報, vol. 107, no. 258, COMP2007-42, pp. 7-12, 2007年10月. |
資料番号 |
COMP2007-42 |
発行日 |
2007-10-09 (COMP) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2007-42 |