Séminaire

Date : 25 juin 2020 10:00 - Salle :Visio-conférence Automatic Cost Function Learning with Interpretable Compositional Networks Florian Richoux, MCF - Laboratoire des Sciences du Numérique de Nantes (LS2N, ex-LINA) à l'Université de Nantes, actuellement en délégation CNRS au JFLI - NII à Tokyo

Cost Function Networks are a formalism in Constraint Programming to model combinatorial satisfaction or optimization problems. By associating a function to each constraint type to evaluate the quality of an assignment, it extends the expressivity of regular Constraint Programming formalisms but at a price of making harder the problem modeling. Indeed, in addition to regular variables/domains/constraints sets, one must provide a set of cost functions that are not always easy to define.

We propose a method to automatically learn a cost function of a constraint, given a function deciding if assignments are valid or not. Our method aims to learn cost functions in a supervised fashion, trying to reproduce the Hamming distance, by using a variation of neural networks we named Interpretable Compositional Networks (ICN), allowing us to get explainable results, unlike regular artificial neural networks. ICN shows itself to be versatile, able to learn cost functions of very different constraints. Another interesting characteristic of ICNs is that they scale: cost functions learned over small dimension spaces remain very effective on high dimension spaces, outputting a perfect or near-perfect Hamming distance for most tested constraints.

Our system can be used to automatically generate cost functions and then having the expressivity of CFN with the same modeling effort than for regular Constraint Programming formalisms. A user can use our system either as a tool to find cost functions automatically or as a decision support system to find promising cost functions that the user can modify and adapt by hand.

https://arxiv.org/abs/2002.09811