Contraintes linéaires et apprentissage sans-conflit pour les modèles graphiques
DOCTORAT DE L’UNIVERSITÉ DE TOULOUSE, École doctorale MITT Unités INRAE/MIAT & INRAE/MIA Paris
Contraintes linéaires et apprentissage sans-conflit pour les modèles graphiques Pierre MONTALBANO pierre.montalbano@inrae.fr Vendredi 15 Décembre 2023 - 14:30 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/94019919944 The presentation will be in English
Simon de Givry, MIAT-INRAE, ANITI George Katsirelos, MIA Paris-INRAE, ANITI
Daniel Le Berre, CRIL-CNRS, Lens Jakob Nordström University of Copenhagen, Danemark
Martin C. Cooper, Univ. Toulouse, ANITI Pierre Schaus, Université catholique de Louvain, Belgique Charlotte Truchet, Université de Nantes
Les modèles graphiques définissent une famille de modèles mathématiques offrant une représentation succincte des problèmes comportant des relations complexes entre les variables. Ils définissent un cadre flexible capable de combiner des informations probabilistes avec des informations logiques et trouvent des applications dans divers domaines tels que l’analyse d’images ou la bio-informatique. L’objectif de cette thèse est d’améliorer l’efficacité des algorithmes de raisonnement sur des modèles graphiques non dirigés tels que les réseaux de fonctions de coût (CFN). Nous montrons tout d’abord comment intégrer des contraintes linéaires dans un CFN. Ce sont des contraintes expressives et compactes qui sont au centre de solveurs de programmation linéaire en nombres entiers (PLNE) très efficaces. Ainsi, la prise en compte des contraintes linéaires dans le cadre d’un CFN peut considérablement élargir son utilisation pratique. Ensuite, nous définissons la virtual pairwise consistency, une nouvelle cohérence locale souple produisant des bornes inférieures de bonnes qualités. Enfin, guidés par le succès des méthodes d’apprentissage basées sur les conflits dans de nombreux domaines (tels que SAT, l’optimisation pseudo-booléenne ou PLNE), nous concevons un nouveau mécanisme d’apprentissage sans conflit. Il vise à mémoriser, par le biais d’une contrainte linéaire, les bornes inférieures des sous-problèmes rencontrés. Si ce sous-problème apparaît une seconde fois dans la recherche, la contrainte précédemment apprise permettra d’obtenir une borne inférieure forte. Nous montrons comment ce mécanisme peut être intégré dans les solveurs PLNE classiques, avant de l’étendre au cadre CFN.
Modèles graphiques, réseaux de fonctions de coût, programmation par contraintes, apprentissage de contraintes, Sac-à-dos, optimisation pseudo-booléenne.
Graphical models define a family of mathematical models providing a succinct representation for problems with complex relationships between variables. This defines a flexible framework capable of combining probabilistic information with logical information and finds application in various fields such as image analysis or bioinformatics. The goal of this thesis is to improve the efficiency of reasoning algorithms on undirected graphical models such as Cost Function Networks (CFN). We first show how to integrate linear constraints in a CFN. They are expressive and compact constraints and are at the center of very efficient Integer Linear Programming (ILP) solvers. Thus, handling linear constraints in the CFN framework can significantly broaden its practical use. Secondly, we define Virtual Pair-Wise Consistency, a new soft local consistency enforcing strong bounds. Finally, guided by the success of conflict-based learning methods in multiple domains (such as SAT, Pseudo Boolean Optimization, or ILP), we design a new conflict-free learning mechanism. It aims to memorize through a linear constraint the lower bounds of the encountered sub-problems. If this sub-problem appears a second time in the search then the previously learned constraint will help to obtain a strong lower bound. We show how such mechanism can be embedded in classic MILP solvers, before extending it to CFN framework.
Graphical Models, Cost Function Networks, Constraint Programming, Constraint Learning, Knapsack, Pseudo-Boolean Optimization.