Accès direct au contenu


Version anglaise


Accueil > Formations > Master MVA > Présentation des cours

Discrete Inference and Learning

Lecturer : Yuliya Tarabalka (Chargée de recherche INRIA) - Nikos Paragios (Centrale Supélec), Karteek Alahari (Chargé de rcherche INRIA)


Solid understanding of mathematical methods, including linear algebra, integral transforms and differential equations

Description of the course :

Discrete optimization provides a very general and flexible modeling paradigm that is ubiquitous in several research areas, such as machine learning and computer vision. As a result, related optimization methods form an indispensable computational tool for a wide variety of inference and learning tasks nowadays. The aim of this course is to introduce students to the relevant concepts and techniques of discrete inference and learning and to familiarize them with how these methods can be applied. We will cover state of the art algorithms used for energy minimization, marginal computation and parameter estimation of rich, expressive models, focusing not only on the accuracy but also on the efficiency of the resulting methods.

Topics :

  • Introduction, basic concepts, dynamic programming, message-passing methods
  • Sum-product belief propagation, generalizing belief propagation, message-passing for higher-order models, accelerating message-passing
  • Graph-cuts: binary energy minimization, multi-label energy minimization
  • Reparameterization
  • Convex relaxations, linear programming relaxations
  • Tree-reweighted message passing
  • Dual decomposition
  • Minimizing free energy
  • Recent advances

    Organization of courses :

    • 8 lectures
    • Final exam, 3 hours

    Validation :

    • examen écrit (3h), contrôle continu

      References :

      Convex Optimization, Stephen Boyd and Lieven Vanderbeghe

      Numerical Optimization, Jorge Nocedal and Stephen J. Wright

      Introduction to Operations Research, Frederick S. Hillier and Gerald J. Lieberman

      An Analysis of Convex Relaxations for MAP Estimation of Discrete MRFs, M. Pawan Kumar, Vladimir Kolmogorov and Phil Torr

      Convergent Tree-reweighted Message Passing for Energy Minimization, Vladimir Kolmogorov