平成21（2009）年度　一般研究２実施報告書

 

課題番号

21−共研−2057

分野分類

統計数理研究所内分野分類

h

主要研究分野分類

2

研究課題名

グラフ上の計算推論アルゴリズムの幾何学的研究とその統計的学習への展開

フリガナ

代表者氏名

フクミズ　ケンジ

福水　健次

ローマ字

Kenji Fukumzu

所属機関

統計数理研究所

所属部局

モデリング研究系

職　　名

准教授

配分経費

研究費

0千円

旅　費

0千円

研究参加者数

4　人

 

 

研究目的と成果（経過）の概要

本研究は、確率伝搬法をはじめとした、グラフによって表現される分布を用いた統計的推論に現れる確率計算の効率的計算アルゴリズムに関して、その数理的基盤を代数幾何・代数的位相幾何・情報幾何などの幾何学的手法を用いて理論的に再構築し、それに基づいたアルゴリズムの理解と発展および応用への展開を目的としている。
近年の情報通信や生命科学の発達は、ネットワーク上の文書や遺伝情報に関する大規模データといった、複雑な構造を伴った高次元・大容量データを出現させている。このようなデータに対する統計的推論には、グラフィカルモデルに対する確率伝搬法をはじめとして、複雑な計算アルゴリズムを必要とすることが多い。したがって、そのようなアルゴリズムの数理的基盤を確立し発展させることは重要な課題になっている。確率伝搬法に関しては、符号の問題における復号アルゴリズムなど応用での成功はあるが、グラフにループがある場合の収束性や解の厳密性に関していまだ十分な数理的解明が行われていない。
本研究では、整数論やグラフ理論と関連して知られていたグラフゼータ関数を多変数に拡張することによって，この多変数グラフゼータ関数によって，確率伝搬法と密接なつながりを持つベーテ自由エネルギーのヘッセ行列式を記述する関係式を証明し，その関係式を用いて確率伝搬法の理論的性質を解析した．その結果，確率伝搬アルゴリズムの局所安定性の十分条件や，収束解の一意性に関して新たな理論的結果を得た．
本研究で得られたグラフゼータ関数による解析は，これまでにある方法と異なる全く新しいもので，グラフゼータ関数の数学的に興味深い性質を用いることにより，より進んだ幾何学的研究へ発展することが期待される．

 

当該研究に関する情報源（論文発表、学会発表、プレプリント、ホームページ等）

　論文
Watanabe, Y. and K. Fukumizu. Graph Zeta Function in the Bethe Free Energy and Loopy Belief Propagation. Advances in Neural Information Processing Systems 22, MIT Press to appear (2010)

学会発表
Yusuke Watanabe and Kenji Fukumizu. Graph Zeta Function in the Bethe Free Energy and Loopy Belief Propagation. Advances in Neural Information Processing Systems (NIPS2009). Dec. 7-10, 2009.（2010年出版予定）
渡辺有祐，福水健次. ベーテ自由エネルギーとLoopy belief Propagation に現れるグラフ のゼータ関数について. 第12回情報論的学習理論ワークショップ　(IBIS 2009)　（オンライン予稿集）2009年10月19−21日，九州大学
Yusuke Watanabe and Kenji Fukumizu. New graph polynomials satisfying deletion-contraction relations. The 7th Japan Conference on Computational Geometry and Graphs (JCCGG2009). Nov. 11-13, 2009, 金沢.
Yusuke Watanabe. Graph zeta function in the Bethe free energy. Physics of Algorithms Workshop (Aug. 31- Spt. 4, 2009, Santa Fe, New Mexico)
渡辺有祐，福水健次.　グラフ上のメッセージ伝搬アルゴリズムに現れるグラフゼータ関数について．2010年度日本数学会年会．2010年3月25日（慶應義塾大学）

ホームページ
http://www.ism.ac.jp/~fukumizu/

研究会を開催した場合は、テーマ・日時・場所・参加者数を記入してください。


 

研究参加者一覧

氏名

所属機関

池田　思朗

統計数理研究所

田中　利幸

京都大学

渡辺 有祐

総合研究大学院大学