Belief propagation in Bayesian networks and Markov chains and extensions with polynomials

schedule le lundi 17 juin 2019 de 17h00 à 18h00

Organisé par : A. Lefebvre, N. Meyer, O. Safsafi, T. Touati

Intervenant : Alexandra Lefebvre (LPSM)
Lieu : Jussieu, salle Paul Levy 16-26 - 209

Sujet : Belief propagation in Bayesian networks and Markov chains and extensions with polynomials

Résumé :

A Bayesian network (BN) is a set of variables whose joint distribution can be factorized over a Directed Acyclic Graph (DAG). On such a structure the probability of an evidence (observations) or the conditional marginal distribution of a variable can be computed through the sum of product of so called potentials. The forward-backward algorithm (also called belief propagation, message-passing or sum-product) allows one to compute these quantities with a complexity dropping from exponential in n (number of variables) to linear in n. In this presentation we will first recall the principles of the classical forward-backward algorithm before seeing extensions based on polynomial potentials and generating functions to compute other quantities of interest such as the distribution of a number of events and its moments up to a chosen order, or the derivatives of the likelihood in parametric BN. We will see some examples of application such as the number of carriers of a deleterious allele in a family, the number of errors in a Hidden Markov Model, or the derivative of the likelihood in linkage analysis aiming at localizing a gene of interest on the genome.