Vendredi 19 mai, 14h00, Salle Séminaire, Lirmm
Promenade autour de l’optimisation sur modèles graphiques probabilistes, réseaux de fonctions de coût et application en bioinfo
Title: Optimisation and Counting in Graphical Models “Graphical models”
(GMs) define a family of mathematical modeling frameworks that have been independently explored as deterministic models (Constraint and Cost Function Networks – CN/CFNs) and stochastic models (eg. Markov Random Fields – MRFs, factor graphs).
In this talk, I’d like to show that while dynamic and linear programming underlie both local consistency filtering in CN/CFNs and message passing in MRFs, the specific focus on optimized guaranteed methods for deterministic GMs translates into a technology that is directly useful for stochastic models.
This is true both for decision NP-complete optimization (Maximum a Posteriori or MAP-MRF problem) and for #P-complete counting (computing Z, the normalizing constant aka the Partition Function). This will be illustrated on recent results obtained in Computational Structural Biology in the context of protein design.