Christophe Gonzales

ECAI Conference 2024 Conference Paper

A Full DAG Score-Based Algorithm for Learning Causal Bayesian Networks with Latent Confounders

• Christophe Gonzales
• Amir-Hosein Valizadeh

Causal Bayesian networks (CBN) are popular graphical probabilistic models that encode causal relations among variables. Learning their graphical structure from observational data has received a lot of attention in the literature. When there exists no latent (unobserved) confounder, i. e. , no unobserved direct common cause of some observed variables, learning algorithms can be divided essentially into two classes: constraint-based and score-based approaches. The latter are often thought to be more robust than the former and to produce better results. However, to the best of our knowledge, when variables are discrete, no score-based algorithm is capable of dealing with latent confounders. This paper introduces the first fully score-based structure learning algorithm searching the space of DAGs (directed acyclic graphs) that is capable of identifying the presence of some latent confounders. It is justified mathematically and experiments highlight its effectiveness.

TCS Journal 2015 Journal Article

Performance guarantees for a scheduling problem with common stepwise job payoffs

• Yasmina Seddik
• Christophe Gonzales
• Safia Kedad-Sidhoum

We consider a single machine scheduling problem with unequal release dates and a common stepwise payoff function for the jobs. The goal is to maximize the sum of the jobs payoffs, which are defined with regard to some common delivery dates. The problem is strongly NP-hard. In this paper, we propose a polynomial time approximation algorithm with both absolute and relative performance guarantees. The time complexity of the approximation algorithm is O ( K N log ⁡ N ), N being the number of jobs and K the number of delivery dates.

ECAI Conference 2014 Conference Paper

An Efficient Bayesian Network Structure Learning Algorithm in the Presence of Deterministic Relations

• Ahmed Mabrouk
• Christophe Gonzales
• Karine Jabet-Chevalier
• Eric Chojnacki

Faithfulness is one of the main hypotheses on which rely most Bayesian network (BN) structure learning algorithms. When some random variables are deterministically determined by others, faithfulness is ruled out and classical learning algorithms fail to discover many dependences between variables, hence producing incorrect BNs. Even state-of-the-art algorithms dedicated to learning with deterministic variables prove to be inefficient to discover many dependences/independences. For critical applications, e. g. , in nuclear safety, such failure is a serious issue. This paper introduces a new hybrid algorithm, combining a constraint-based approach with a greedy search, that includes specific rules dedicated to deterministic nodes that significantly reduce the incorrect learning. Experiments show that our method significantly outperforms state-of-the-art algorithms.

UAI Conference 2012 Conference Paper

DBN-Based Combinatorial Resampling for Articulated Object Tracking

• Séverine Dubuisson
• Christophe Gonzales
• Xuan Son Nguyen

Particle Filter is an effective solution to track objects in video sequences in complex situations. Its key idea is to estimate the density over the possible states of the object using a weighted sample whose elements are called particles. One of its crucial step is a resampling step in which particles are resampled to avoid some degeneracy problem. In this paper, we introduce a new resampling method called Combinatorial Resampling that exploits some features of articulated objects to resample over an implicitly created sample of an exponential size better representing the density to estimate. We prove that it is sound and, through experimentations both on challenging synthetic and real video sequences, we show that it outperforms all classical resampling methods both in terms of the quality of its results and in terms of response times.

IJCAI Conference 2009 Conference Paper

• Jean-Philippe Dubus
• Christophe Gonzales
• Patrice Perny

This paper deals with multiobjective optimization in the context of multiattribute utility theory. The alternatives (feasible solutions) are seen as elements of a product set of attributes and preferences over solutions are represented by generalized additive decomposable (GAI) utility functions modeling individual preferences or criteria. Due to decomposability, utility vectors attached to solutions can be compiled into a graphical structure closely related to junction trees, the so-called GAI net. We first show how the structure of the GAI net can be used to determine efficiently the exact set of Paretooptimal solutions in a product set and provide numerical tests on random instances. Since the exact determination of the Pareto set is intractable in worst case, we propose a near admissible algorithm with performance guarantee, exploiting the GAI structure to approximate the set of Pareto optimal solutions. We present numerical experimentations, showing that both utility decomposition and approximation significantly improve resolution times in multiobjective search problems.

IJCAI Conference 2009 Conference Paper

• Jean-Philippe Dubus
• Christophe Gonzales
• Patrice Perny

This paper deals with Decision-Making in the context of multiattribute utility theory and, more precisely, with the problem of efficiently determining the best alternative w. r. t. an agent’s preferences (choice problem). We assume that alternatives are elements of a product set of attributes and that the agent’s preferences are represented by a generalized additive decomposable (GAI) utility on this set. Such a function allows an efficient representation of interactions between attributes while preserving some decomposability of the model. GAI utilities can be compiled into graphical structures called GAI networks that can be exploited to solve choice problems using collect/distribute schemes essentially similar to those used in Bayesian networks. In this paper, rather than directly using this scheme on the GAI network for determining the most preferred alternative, we propose to work with another GAI function, acting as an upper-bound on utility values and enhancing the model’s decomposability. This method still provides the exact optimal solution but speeds up significantly the search. It proves to be particularly useful when dealing with choice and ranking under constraints and within collective Decision-Making, where GAI nets tend to have a large size. We present an efficient algorithm for determining this new GAI function and provide experimental results highlighting the practical efficiency of our procedure.

AAAI Conference 2008 Conference Paper

Preference Aggregation with Graphical Utility Models

• Christophe Gonzales

This paper deals with preference representation and aggregation in the context of multiattribute utility theory. We consider a set of alternatives having a combinatorial structure. We assume that preferences are compactly represented by graphical utility models derived from generalized additive decomposable (GAI) utility functions. Such functions enable to model interactions between attributes while preserving some decomposability property. We address the problem of finding a compromise solution from several GAI utilities representing different points of view on the alternatives. This scheme can be applied both to multicriteria decision problems and to collective decision making problems over combinatorial domains. We propose a procedure using graphical models for the fast determination of a Pareto-optimal solution achieving a good compromise between the conflicting utilities. The procedure relies on a ranking algorithm enumerating solutions according to the sum of all the GAI utilities until a boundary condition is reached. Numerical experiments are provided to highlight the practical efficiency of our procedure.

KR Conference 2004 Conference Paper

GAI Networks for Utility Elicitation

• Christophe Gonzales
• Patrice Perny

This paper deals with preference representation and elicitation in the context of multiattribute utility theory under risk. Assuming the decision maker behaves according to the EU model, we investigate the elicitation of generalized additively decomposable utility functions on a product set (GAI-decomposable utilities). We propose a general elicitation procedure based on a new graphical model called a GAI-network. The latter is used to represent and manage independences between attributes, as junction graphs model independences between random variables in Bayesian networks. It is used to design an elicitation questionnaire based on simple lotteries involving completely specified outcomes. Our elicitation procedure is convenient for any GAI-decomposable utility function, thus enhancing the possibilities offered by UCP-networks.