@misc{oai:ir.soken.ac.jp:00001676,
author = {渡辺, 有祐 and ワタナベ, ユウスケ and WATANABE, Yusuke},
month = {2016-02-17, 2016-02-17},
note = {近年、グラフィカルモデルと呼ばれる確率モデルが様々な分野で用いられている。グラ
フィカルモデルは一般に複数の確率変数に関する同時分布を定めるが、実用上は各確率変
数に関する周辺確率や分配関数が必要となることが多い、しかし、同時分布からこれらを
求めることは計算量の観点から必ずしも簡単ではない。確率伝搬法はこれらを近似的に計
算する効率の良い局所伝搬型のアルゴリズムであり、同等のアルゴリズムは古くから広く
用いられている。本論文は確率伝搬法に関して渡辺氏の行った離散幾何学的観点からの数
理的研究をまとめてある。英語で書かれており、全8章からなる。
第1章では、研究の背景と論文で必要となる基本的な概念を説明している。本論文で用
いるグラフィカルモデルの定義を行い、古くから同様の記述が用いられている統計物理学
との関係についても概説している。続いて確率推論の重要性、そして計算量の観点からの
困難さを述べている。続いて確率伝搬法について説明している。確率伝搬法はグラフが木
の場合には正しい推論を与えるが、ループのあるグラフィカルモデルに対しては近似的な
計算手法となる。この近似的計算手法としての確率伝搬法(Loopy Belief Propagation、以
下LBP)を説明している。また、本章の最後の節において、本研究の特徴である離散幾何
的アプローチに関する簡単な例と、離散幾何学を用いる理由について簡単な説明を与えて
いる。
第2章は本論文で扱う問題を数学的に定式化している。本論文で必要となるグラフィカ
ルモデルを定義し、確率分布、特に指数型分布のもつ性質を述べ、その後LBPに関する既
存の知見をまとめている。具体的にはLBPと密接に関係しているベーテ自由エネルギーを
説明し、確率伝搬法の更新則に対する固定点とベーテ自由エネルギー関数の停留点が一致
するという重要な既存の結果を説明している。
本論文の主要結果はこの後に続く第3章から第7章にまとめられており、2部に分かれ
ている。第1部は第3章から第5章である。ここでは渡辺氏が提案するグラフゼータ関数
によるLBPの解析に関する結果が述べられている。続く第2部は第6章と第7章であり、
分配関数のループ展開に関する結果について論じている。
第3章では、グラフ理論の分野で定義されているグラフゼータ関数を示し、その拡張を
行っている。グラフの幾何的性質を表現する量として、グラフの素サイクルを用いた多変
数グラフゼータ関数を導入し、その行列式表示を2通りの方法で与える「伊原の公式」の
多変数拡張を証明している。
第4章では渡辺氏が拡張したグラフゼータ関数と確率伝搬法の関係を議論している。ま
ず、第3章で証明した行列式の関係を用い、ベーテ自由エネルギーのヘッセ行列の行列式
を多変数グラフゼータ関数によって表す公式を証明している。この結果を応用してべーテ
自由エネルギーのヘッセ行列が正定値となるための十分条件を示している。
確率伝搬法の固定点とベーテ自由エネルギー関数の停留点とは一致することから、この
ヘッセ行列の正定値性は確率伝搬法の安定性を解析のために重要である。第5章ではこの
関係からLBPの固定点の局所安定性を示している。また、グラフィカルモデルのサイクル
の個数とLBPの固定点の個数に関するこれまで知られていない理論的な結果を導いてい
る。
第2部では、主に分配関数のループ展開を扱っている。まず第6章において、正しい分
配関数や周辺確率と、LBPによるそれらの近似との比を、グラフの一般化ループによって
展開する方法について説明している。この展開方法は渡辺氏と米国のグループが同時期に
独立に同等の結果を得たものである。この展開の応用として、マッチング問題に適用した
例を示している。また、グラフゼータ関数との関係についても述べている。
第7章は、分配関数のループ展開から導かれるグラフ多項式について論じている。グラ
フ上の確率分布のパラメータを2変数や1変数に低減することにより、グラフ不変量とな
る多項式を定義し、それらがグラフのエッジの削除と縮約によって特定の関係式を満たす
TutteのV関数というクラスに属することを示している。また、このグラフ多項式と、マ
ッチング多項式やグラフゼータ関数を含めた既存のグラフ不変量との間のさまざまな関係
を導いている。
第8章は論文のまとめである。本論文で示した内容についてまとめ、今後の課題につい
て述べている。
Abstract
We often encounter probability distributions given as unnormalized products of non-negative functions. The factorization structures of the probability distributions are represented by hypergraphs called factor graphs. Such distributions appear in various fields, including statistics, artificial intelligence, statistical physics, error correcting codes, etc.
Given such a distribution, computations of marginal distributions and the normalization constant are often required. However, they are computationally intractable because of their computational costs. One, empirically successful and tractable, approximation method is the Loopy Belief Propagation (LBP) algorithm.
The focus of this thesis is an analysis of the LBP algorithm. If the factor graph is a
tree, i.e. having no cycle, the algorithm gives the exact quantities, not approximations. If the factor graph has cycles, however, the LBP algorithm does not give exact results and possibly exhibits oscillatory and non convergent behaviors. The thematic question of this thesis is "How do the behaviors of the LBP algorithm are affected by the discrete geometry of the factor graph? " Here, the word "discrete geometry" means the geometry of the factor graph as a space.
The primary contribution of this thesis is the discovery of a formula called the Bethe-
zeta formula, which establishes the relation between the LBP, the Bethe free energy and the graph zeta function. This formula provides new techniques for analysis of the LBP algorithm, connecting properties of the graph and of the LBP and the Bethe free energy.
We demonstrate applications of the techniques to several problems including (non) convexity of the Bethe free energy, the uniqueness and stability of the LBP fixed point.
We also discuss the loop series initiated by Chertkov and Chernyak (2006). The loop
series is a subgraph expansion of the normalization constant, or partition function, and
reflects the graph geometry. We investigate theoretical natures of the series. Moreover, we show a partial connection between the loop series and the graph zeta function., application/pdf, 総研大甲第1334号},
title = {Discrete geometric analysis of message passing algorithm on graphs},
year = {}
}