グラフ上の確率推論に関する数理的研究

图概率推理的数学研究

• 批准号: 08J00993
• 负责人: 渡辺 有祐
• 金额: $ 1.15万
• 依托单位: The Institute of Statistical Mathematics (2010)The Graduate University for Advanced Studies (2008-2009)
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for JSPS Fellows
• 财政年份: 2008
• 资助国家: 日本
• 起止时间: 2008 至 2010
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-08J00993/
• 关键词: 確率伝搬法; ビリーフプロパゲーション; ベーテ近似; 誤り訂正符号; グラフ; グラフゼータ関数; グラフ多項式; 離散幾何

グラフ構造をもった確率分布が与えられた時に,その規格化定数もしくは周辺確率分布を求める問題は,誤り訂正符号,音声認識,人工知能,最適化などに幅広く関係した,応用的にも数理的にも重要な問題である.私は,この問題の確率伝搬法による計算法について研究している.実際にこの方法はLDPC符号などでは広く実用されている.その中でも特に,グラフの幾何学的な構造と,計算の難しさの関係について着目し,研究を進めた.昨年度は確率伝搬法,ベーテ自由エネルギーとグラフのゼータ関数が非常に密接に関係していることを発見したが,今年度はそれをさらに発展させ,拡張した.解の一意性に関して今までで最も強い結果など,新しい結果を得た.それらに関して論文にまとめて投稿した.現在査読中である.また,昨年度に投稿していた論文が出版された.

鉴于具有图形结构的概率分布，找到归一化常数或周围概率分布的问题是应用程序和数学上重要的问题，它与误差校正代码，语音识别，人工智能，优化等广泛相关。我正在研究使用概率传播方法研究此问题的计算方法。实际上，该方法广泛用于LDPC代码等。我专注于图的几何结构与计算难度之间的关系，并且进行了研究。去年，我发现概率传播方法，伯特自由能和图的Zeta功能密切相关，但是今年我已经进一步开发并扩展了它。我已经获得了新的结​​果，包括曾经是独特的解决方案的最强结果。我已经在论文中提交了所有内容。目前正在同行评审中。另外，我去年提交的一篇论文也发表了。

项目成果

グラフ上のメッセージ伝搬型アルゴリズムの解の一意性とグラフのゼータ関数

图上消息传播算法解的唯一性及图的zeta函数

• 发表时间: 2010
• 作者: 櫻井伸治;藤川陽子;角本真澄美;濱崎竜英;菅原正孝;福井正美;梅田幹雄;高橋千太郎;Yusuke Watanabe;Yusuke Watanabe;Yusuke Watanabe;Yusuke Watanabe;渡辺有祐;渡辺有祐;渡辺有祐
• 通讯作者: 渡辺有祐

分配関数のビリーフプロパゲーションによる計算とグラフ多項式

通过配分函数和图多项式的置信传播进行计算

• 发表时间: 2009
• 作者: 櫻井伸治;藤川陽子;角本真澄美;濱崎竜英;菅原正孝;福井正美;梅田幹雄;高橋千太郎;Yusuke Watanabe;Yusuke Watanabe;Yusuke Watanabe;Yusuke Watanabe;渡辺有祐;渡辺有祐;渡辺有祐;渡辺有祐;渡辺有祐;渡辺有祐;渡辺有祐
• 通讯作者: 渡辺有祐

Graph Zeta Function in the Bethe Free Energy and Loopy Belief Propagation

• 发表时间: 2009-12
• 期刊: ArXiv
• 作者: Yusuke Watanabe;K. Fukumizu

New graph polynomials from the Bethe approximation of the Ising partition function

来自伊辛配分函数 Bethe 近似的新图多项式

• 发表时间: 2010
• 期刊: Combinatorics, Probability and Computing
• 作者: 櫻井伸治;藤川陽子;角本真澄美;濱崎竜英;菅原正孝;福井正美;梅田幹雄;高橋千太郎;Yusuke Watanabe;Yusuke Watanabe
• 通讯作者: Yusuke Watanabe

グラフ上のメッセージ伝搬アルゴリズムに現れるグラフのゼータ関数について

关于图消息传播算法中出现的图zeta函数

• 发表时间: 2010
• 作者: 櫻井伸治;藤川陽子;角本真澄美;濱崎竜英;菅原正孝;福井正美;梅田幹雄;高橋千太郎;Yusuke Watanabe;Yusuke Watanabe;Yusuke Watanabe;Yusuke Watanabe;渡辺有祐;渡辺有祐
• 通讯作者: 渡辺有祐