Analysis of Belief Propagation algorithms based on Information Geometry

基于信息几何的置信传播算法分析

基本信息

批准号：
14084208
负责人：
MOTOMURA Yoichi
金额：
$ 4.22万
依托单位：
The National Institute of Advanced Industrial Science and Technology (2003-2005)Kyushu Institute of Technology (2002)
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research on Priority Areas
财政年份：
2002
资助国家：
日本
起止时间：
2002 至 2005
项目状态：
已结题

项目摘要

In the research of turbo codes, many studies have appeared. Although experimental results strongly support the efficacy of turbo codes, further theoretical analysis is necessary. We extend the geometrical framework initiated by Richardson to the information geometrical framework of dual affine connections, focusing on both of the turbo and LDPC decoding algorithms. The framework helps our intuitive 'understanding of the algorithms and opens a new prospect of further analysis. We reveal some properties of these codes in the proposed framework, including the stability and error analysis. Based on the error analysis, we finally propose a correction term for improving the approximation.Belief propagation (BP) gives exact inference for stochastic models with tree interactions. Its performance has been analyzed separately in many fields, such as AI, statistical physics, information theory, and information geometry. We give a unified framework for understanding BP and related methods and summ … More arizes the results obtained in many fields. In particular, BP and its variants, including tree reparameterization and concave-convex procedure, are reformulated with information-geometrical terms, and their relations to the free energy function are elucidated from an information-geometrical viewpoint. Then a family of new algorithms are proposed The stabilities of the algorithms are analyzed, and methods to accelerate them are investigated.Bayesian networks can be utilized for constructing a mathematical model of human cognitive and psychological functions, executable on a computer. We propose probabilistic modeling based on the Personal Construct Theory, a basic theory used in cognitive/evaluative structure models for individuals. After extracting a skeleton structure using the Evaluation Grid, Bayesian network model is constructed though statistical learning. By executing a probabilistic reasoning algorithm using belief propagation on the constructed model, our proposal is applied to user-adaptable information systems, information recommendation, car navigation systems, etc. Less

在涡轮代码的研究中，已经出现了许多研究。尽管实验结果强烈支持涡轮代码的有效性，但需要进一步的理论分析。我们将理查森（Richardson）启动的几何框架扩展到双重仿射连接的信息几何框架，重点是涡轮和LDPC解码算法。该框架有助于我们对算法的直观理解，并为进一步的分析打开了新的前景。我们在提出的框架中揭示了这些代码的某些属性，包括稳定性和错误分析。基于误差分析，我们最终提出了一个改正术语以改善近似值。宽容繁殖（BP）对具有树相互作用的随机模型提供了精确的推断。在许多领域，例如AI，统计物理学，信息理论和信息几何形状，已分别分析了其性能。我们提供了一个统一的框架，以理解BP和相关方法，并总结一下在许多领域获得的结果。特别是，BP及其变体，包括树木的重新聚集和凹形 - 概念程序，用信息 - 地形术语重新构建，并且从信息地形角度阐明了它们与自由能函数的关系。然后提出了一个新算法的家族，分析了算法的稳定性，并研究了加速它们的方法。可以利用Bayesian网络来构建计算机上可执行的人类认知和心理功能的数学模型。我们提出了基于个人构造理论的概率建模，这是一个用于个人的认知/评估结构模型中的基本理论。使用评估网格提取骨骼结构后，通过统计学习构建了贝叶斯网络模型。通过在构造模型上使用信念传播执行概率推理算法，我们的建议应用于用户适应的信息系统，信息建议，汽车导航系统等。