Message-passing algorithms for graphical models- Coffee Meeting Talk by Yingying Xu

Описание: Date: August 6, 2021
Speaker: Dr. Yingying Xu (iTHEMS)
Title: Message-passing algorithms for graphical models

Abstract: Inference problems like marginalization and maximization are NP-hard to solve exactly and approximately in a graphical model. The complexity can be reduced dramatically when the underlying factor graph has some special structure. One extreme case is that of tree factor graphs, in which marginals can be computed in a number of operations which grows linearly with number of notes. This can be done by a ‘dynamic programming’ procedure often called as message passing or belief propagation algorithms. The update rules have been discovered independently in several different contexts: statistical physics (‘Bethe-Peierls approximation’), coding theory (the ‘sum-product’ algorithm), and artificial intelligence (‘belief propagation’, BP). The time evolution of the message’s distributions is known under the name of ‘density evolution’, and the fixed-point analysis of them is done by the replica-symmetric cavity method.