Optimisation convexe pour les modèles graphiques discrets
DOCTORAT DE L’UNIVERSITÉ DE TOULOUSE, École doctorale MITT Unités INRAE/MIAT & INRAE/MIA Paris
Optimisation convexe pour les modèles graphiques discrets Valentin DURANTE valentin.durante@inrae.fr Vendredi 15 Décembre 2023 - 9:00 INRAE-MIAT - Bâtiment C8 - Salle de Séminaire - 24 Chem. de Borde Rouge, 31320 Auzeville-Tolosane https://maps.app.goo.gl/r4Y7WmTUobz7DAMJ8
Visio: https://inrae-fr.zoom.us/j/2853006652
The presentation will be in English
George Katsirelos, MIA Paris-INRAE, ANITI Thomas Schiex, MIAT-INRAE, ANITI
Renata Sotirov, Tilburg University, The Netherlands Pawel Swoboda, University Düsseldorf, Germany
Martin C. Cooper, Univ. Toulouse, ANITI Amélie Lambert, CEDRIC-CNAM, Paris Edouard Pauwels, Univ. Toulouse, ANITI Clément Royer, Université Paris Dauphine-PSL, Paris
Les modèles graphiques définissent une famille de formalismes et d’algorithmes utilisés en particulier pour le raisonnement logique et probabiliste, dans des domaines aussi variés que l’analyse d’image ou le traitement du langage naturel. Ils sont capables d’être appris à partir de données, donnant une information probabiliste qui peut ensuite être combinée avec des informations logiques. L’objectif de la thèse est d’améliorer l’efficacité des algorithmes de raisonnement sur ces modèles afin d’augmenter la puissance du mécanisme de raisonnement fondamental utilisé dans ces outils (le calcul de minorant) en exploitant les progrès réalisés ces dernières années dans le domaine de l’optimisation convexe. Tout d’abord, nous avons introduit deux nouvelles relaxations pour le problème du Maximum A Posteriori (MAP) sur les modèles graphiques discrets. Le problème d’optimisation combinatoire est relaché en deux programmes semi-définis (SDP), que nous résolvons en utilisant des méthodes de rang faible. Le premier solveur est basé sur la mixing method, une méthode de rang faible dédiée aux SDPs à contraintes diagonales. Pour la seconde relaxation, nous avons développé un solveur de rang faible dédié qui effectue des étapes de descente en coordonnées par bloc. Nous démontrons notamment la qualité des solutions SDP pour certains types de problèmes. Au cours des expérimentations, nous prouvons également que notre deuxième méthode possède de bonnes propriétés de passage à l’échelle. Par la suite, nous avons exploré un nouvel ensemble de contraintes pour renforcer la relaxation SDP du problème MAP. Pour maintenir un bon compromis entre l’effort de calcul et la qualité de la solution, nous avons décidé d’utiliser une méthode du premier ordre pour résoudre approximativement la relaxation. Finalement, nous avons travaillé sur la résolution exacte du problème MaxCut, qui est un problème central en l’optimisation combinatoire. En particulier, le problème MaxCut partage des liens étroits avec le problème MAP sur les modèles graphiques discrets. Nous avons proposé un nouveau solveur semi-défini basé sur l’une des méthodes de rang faible introduites précédemment. Nous avons montré comment cette méthode peut être incorporée dans un algorithme de branch and cut.
Modèles Graphiques, Optimisation discrète, Optimisation Convexe, Programmation Semi-definie Positive, Méthodes de Rang Faible.
Graphical models define a family of formalisms and algorithms used for logical and probabilistic reasoning, in fields as varied as image analysis or natural language processing. They can be learned from data, giving probabilistic information which can later be combined with logical information. The objective of the thesis is to improve the efficiency of the reasoning algorithms on these models in order to increase the power of the fundamental reasoning mechanism used in these tools (minorant computation) by exploiting the progress made in the field of convex optimisation. First, we introduced two new relaxations for the Maximum A Posteriori (MAP) problem on discrete pairwise graphical models. The original combinatorial problem is relaxed into two semidefinite programs (SDP), which we solve by using efficient low-rank methods. The first solver is based on the mixing method, a low-rank solver dedicated to diagonally constrained SDPs. For the second relaxation, we developed a dedicated low-rank solver that performs block coordinate descent steps. Among other things, we demonstrate the quality of the SDP solutions for certain types of problem. There is also evidence that our second method has good scalability properties. Then, we explored a new set of constraints to tighten the SDP relaxation of the MAP problem. To keep a good trade-off between the effort spent and the quality of the solution, we decided to use a first-order method to approximately solve the relaxation. Finally, we worked on solving MaxCut to optimality which is a central problem in combinatorial optimization. Solving MaxCut was relevant in the context of this thesis since it shares tight links with the MAP problem on discrete graphical models. We proposed a new semidefinite solver based on one of the low-rank methods introduced previously. We showed how this method can be incorporated into a branch and cut algorithm.
Graphical Models, Combinatorial Optimization, Convex Optimization, Semidefinite Programming, Low-Rank Methods.