logo EDITE Nawal BENABBOU
Identité
Nawal BENABBOU
État académique
Thèse soutenue le 2017-05-05
Sujet: Recherche de solutions potentiellement optimales en décision multicritère, décision multi-agents et décision dans l'incertain.
Direction de thèse:
Laboratoire:
Voisinage
Ellipse bleue: doctorant, ellipse jaune: docteur, rectangle vert: permanent, rectangle jaune: HDR. Trait vert: encadrant de thèse, trait bleu: directeur de thèse, pointillé: jury d'évaluation à mi-parcours ou jury de thèse.
Productions scientifiques
oai:hal.archives-ouvertes.fr:hal-01215884
Incremental Weight Elicitation for Multiobjective State Space Search
International audience
This paper proposes incremental preference elicitation methods for multiobjective state space search. Our approach consists in integrating weight elicitation and search to determine, in a vector-valued state-space graph, a solution path that best fits the Decision Maker's preferences. We first assume that the objective weights are imprecisely known and propose a state space search procedure to determine the set of possibly optimal solutions. Then, we introduce incremental elicitation strategies during the search that use queries to progressively reduce the set of admissible weights until a nearly-optimal path can be identified. The validity of our algorithms is established and numerical tests are provided to test their efficiency both in terms of number of queries and solution times.
Proceedings of the 29th AAAI Conference on Artificial Intelligence (AAAI'15) The 29th AAAI Conference on Artificial Intelligence (AAAI'15) https://hal.archives-ouvertes.fr/hal-01215884 The 29th AAAI Conference on Artificial Intelligence (AAAI'15), Jan 2015, Austin, Texas, United States. pp.1093-1099ARRAY(0x7f54709fa8f8) 2015-01
oai:hal.archives-ouvertes.fr:hal-01212850
Combining Preference Elicitation and Search in Multiobjective State-Space Graphs
International audience
The aim of this paper is to propose a new approach interweaving preference elicitation and search to solve multiobjective optimization problems. We present an interactive search procedure directed by an aggregation function, possibly non-linear (e.g. an additive disutility function, a Choquet integral), defining the overall cost of solutions. This function is parameterized by weights that are initially unknown. Hence, we insert comparison queries in the search process to obtain useful preference information that will progressively reduce the uncertainty attached to weights. The process terminates by recommending a near-optimal solution ensuring that the gap to optimality is below the desired threshold. Our approach is tested on multiobjective state space search problems and appears to be quite efficient both in terms of number of queries and solution times.
Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI'15) The 24th International Joint Conference on Artificial Intelligence (IJCAI'15) https://hal.archives-ouvertes.fr/hal-01212850 The 24th International Joint Conference on Artificial Intelligence (IJCAI'15), Jul 2015, Buenos Aires, Argentina. pp.297-303ARRAY(0x7f54709f2530) 2015-07
oai:hal.archives-ouvertes.fr:hal-01213322
On Possibly Optimal Tradeoffs in Multicriteria Spanning Tree Problems
International audience
In this paper, we propose an interactive approach to determine a compromise solution in the multicriteria spanning tree problem. We assume that the Decision Maker’s preferences over spanning trees can be represented by a weighted sum of criteria but that weights are imprecisely known. In the first part of the paper, we propose a generalization of Prim’s algorithm to determine the set of possibly optimal tradeoffs. In the second part, we propose an incremental weight elicitation method to reduce the set of feasible weights so as to identify a necessary optimal tradeoff. Numerical tests are given to demonstrate the practical feasibility of the approach.
Proceedings of the 4th International Conference on Algorithmic Decision Theory (ADT'15) The 4th International Conference on Algorithmic Decision Theory (ADT'15) https://hal.archives-ouvertes.fr/hal-01213322 The 4th International Conference on Algorithmic Decision Theory (ADT'15), Sep 2015, Lexington, KY, United States. Springer International Publishing, 9346, pp.322-337, Lecture Notes in Computer Science. <10.1007/978-3-319-23114-3_20>ARRAY(0x7f54709f2488) 2015-09
oai:hal.archives-ouvertes.fr:hal-01215599
Incremental Elicitation of Choquet Capacities for Multicriteria Decision Making
International audience
The Choquet integral is one of the most sophisticated and expressive preference models used in decision theory for multicriteria decision making. It performs a weighted aggregation of criterion values using a capacity function assigning a weight to any coalition of criteria, thus enabling positive and/or negative interactions among criteria and covering an important range of possible decision behaviors. However, the specification of the capacity involves many parameters which raises challenging questions, both in terms of elicitation burden and guarantee on the quality of the final recommendation. In this paper, we investigate the incremental elicitation of the capacity through a sequence of preference queries selected one-by-one using a minimax regret strategy so as to progressively reduce the set of possible capacities until a decision can be made. We propose a new approach designed to efficiently compute minimax regret for the Choquet model. Numerical experiments are provided to demonstrate the practical efficiency of our approach.
Proceedings of the 21st European Conference on Artificial Intelligence (ECAI'14) The 21st European Conference on Artificial Intelligence (ECAI'14) https://hal.archives-ouvertes.fr/hal-01215599 The 21st European Conference on Artificial Intelligence (ECAI'14), Aug 2014, Prague, Czech Republic. 263, pp.87-92, Frontiers in Artificial Intelligence and Applications. <10.3233/978-1-61499-419-0-87>ARRAY(0x7f54709f5570) 2014-08
oai:hal.archives-ouvertes.fr:hal-01170030
Minimax Regret Approaches for Preference Elicitation with Rank-Dependent Aggregators
International audience
Recently there has been a growing interest in non-linear aggregation models to represent the preferences of a decision maker in a multicriteria decision problem. Such models are expressive as they are able to represent synergies (positive and negative) between attributes or criteria, thus modeling different decision behaviors. They also make it possible to generate Pareto-optimal solutions that cannot be obtained by optimizing a linear combination of criteria. This is the case of rank-dependent aggregation functions such as Ordered Weighted Averages and their weighted extensions, but more generally of Choquet integrals. A key question is how to assess the parameters of such models to best fit decision maker’s behaviors or preferences. In this work, adopting a principled decision-theoretic approach, we consider the optimization problem induced by adaptive elicitation using the minimax regret criterion.
EURO Journal on Decision Processes https://hal.archives-ouvertes.fr/hal-01170030 EURO Journal on Decision Processes, 2015, 3 (1-2), pp.29-64. <10.1007/s40070-015-0040-6>ARRAY(0x7f54709f27d0) 2015-06
oai:hal.archives-ouvertes.fr:hal-01217672
Possible Optimality and Preference Elicitation for Decision Making
International audience
Decision support systems often rely on a mathematical decision model allowing the comparison of alternatives and the selection of a proper solution. In the field of Multicriteria Decision Making, an aggregation function is often used to synthesize the different evaluations of each alternative into an aggregated value representing its overall utility. The aggregation function must be sufficiently expressive to efficiently approximate the decision maker's preferences in human decision support, or simulate a prescribed decision behavior in automated decision systems. This explains the diversity of decision models available in the literature but also the increasing interest for sophisticated parameterized models such as the Choquet integral [32, 14] which enables the representation of complex preferences and includes many other models as special cases (e.g. leximin and lexicographic aggregators [11], the Ordered Weighted Average operator [38], and Weighted Ordered Weighted Average [34]). To make use of such models, one needs to assess the model parameters in order to fit to the decision maker's preferences. Most of the previous work on the elicitation of Choquet integral parameters consider a static database of preference statements, and focus on the determination of the parameters that best fit to the available database (e.g. [16, 26, 27, 13, 15]) for instance by minimizing a quadratic error. However, these approaches require a relatively large number of preference statements to model the decision maker's behaviour accurately which are not always possible to obtain. Preference elicitation with limited available information is a crucial task in many application domains, including recommender systems and interface customization [28]. Departing from these standard approaches , we consider incremental elicitation methods based on the minimax regret which is a decision criterion that has been advocated as a means for robust optimization in the presence of data uncertainty [21] and has been used for decision making with utility function uncertainty [5, 31, 6]. The general principle of this approach is to iteratively ask questions to the decision maker so as to reduce the set of possible parameters until the preferred alternative can be detected with some guarantees (as given by the minimax regret). This elicitation approach enables limiting the decision maker's burden as preference information is only required to discriminate between alternatives (not to assess the model parameters). Incremental elicitation methods have been proposed for the simple case of linear utilities but have never been studied for Choquet Integrals.
The 4th International Conference on Algorithmic Decision Theory http://hal.upmc.fr/hal-01217672 The 4th International Conference on Algorithmic Decision Theory, Sep 2015, Lexington, United States. 2015, <10.1007/978-3-319-23114-3_34>ARRAY(0x7f54709f20b0) 2015-09-27
oai:hal.archives-ouvertes.fr:hal-01480147
Incremental elicitation of choquet capacities for multicriteria choice, ranking and sorting problems
International audience
This paper proposes incremental preference elicitation methods for multicri-teria decision making with a Choquet integral. The Choquet integral is an evaluation function that performs a weighted aggregation of criterion values using a capacity function assigning a weight to any coalition of criteria, thus enabling positive and/or negative interactions among them and covering an important range of possible decision behaviors. However, the specification of the capacity involves many parameters which raises challenging questions, both in terms of elicitation burden and guarantee on the quality of the final recommendation. In this paper, we investigate the incremental elicitation of the capacity through a sequence of preference queries (questions) selected one-by-one using a minimax regret strategy so as to progressively reduce the set of possible capacities until the regret (the worst-case " loss " due to reasoning with only partially specified capacities) is low enough. We propose a new approach designed to efficiently compute minimax regret for the Choquet model and we show how this approach can be used in different settings: 1) the problem of recommending a single alternative, 2) the problem of ranking alternatives from best to worst, and 3) sorting several alternatives into ordered categories. Numerical experiments are provided to demonstrate the practical efficiency of our approach for each of these situations.
ISSN: 0004-3702 Artificial Intelligence http://hal.upmc.fr/hal-01480147 Artificial Intelligence, Elsevier, 2017, <10.1016/j.artint.2017.02.001>ARRAY(0x7f54709f5b88) 2017
oai:hal.archives-ouvertes.fr:hal-01423287
A regret-based preference elicitation approach for sorting with multicriteria reference profiles
International audience
In this paper we present an incremental elicitation method to determine the importance of the coalitions of criteria in a multicri-teria sorting method. The method is designed to assign alternatives to predefined categories by comparing their performance vector to reference profiles. These comparisons lead to binary preference indices that are aggregated to determine the membership of the alternatives to predefined categories. We present an active learning process to determine the weighting coefficients modeling the importance of criteria in the aggregation process. Learning examples are generated one by one and presented to the Decision Maker to efficiently reduce the uncertainty attached to criteria weights. The process is stopped when all alternatives can be assigned to a category with the desired guarantee. We present the formal elicitation method as well as numerical tests showing its practical efficiency.
From Multicriteria Decision Making to Preference Learning (DA2PL'16) http://hal.upmc.fr/hal-01423287 From Multicriteria Decision Making to Preference Learning (DA2PL'16), Nov 2016, Paderborn, Germany. 2016ARRAY(0x7f54709f58e8) 2016-11-07
oai:hal.archives-ouvertes.fr:hal-01342500
Incremental Preference Elicitation in Multi-Attribute Domains for Choice and Ranking with the Borda Count
International audience
In this paper, we propose an interactive version of the Borda method for collective decision-making (social choice) when the alternatives are described with respect to multiple attributes and the individual preferences are unknown. More precisely, assuming that individual preferences are representable by linear multi-attribute utility functions, we propose an incremental elicitation method aiming to determine the Borda winner while minimizing the communication effort with the agents. This approach follows the recent work of Lu and Boutilier [8] relying on the minimax regret as a criterion for dealing with uncertainty in the preferences. We show that, when preferences are expressed on a multi-attribute domain and are additively separable over attributes, regret-based incremental elic-itation methods can be made more efficient to determine or approximate the Borda winner. Our approach relies on the representation of incomplete preferences using convex polyhedra of possible utilities and is based on linear programming both for minimizing regrets and selecting informative preference queries. It enables to incrementally collect preference judgements from the agents until the Borda winner can be identified. Moreover, we provide an incremental technique for eliciting a collective ranking instead of a single winner.
The tenth International Conference on Scalable Uncertainty Management http://hal.upmc.fr/hal-01342500 The tenth International Conference on Scalable Uncertainty Management, Sep 2016, Nice, France. 2016ARRAY(0x7f54709fa9d0) 2016-09-21
Soutenance
Thèse: Procédures de décision par élicitation incrémentale de préférences en optimisation multicritère, multi-agents et dans l'incertain
Soutenance: 2017-05-05
Rapporteurs: Marc PIRLOT    Jerôme LANG