2017-05-19 Optimisation and Counting in Graphical Models

19 mai à 14h, salle des séminaires (bâtiment 4)
Thomas Schiex (DR à l'INRA-Toulouse)

Résumé
"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.

Mots-clés

Optimisation

Dernière mise à jour le 15/05/2017