Conditional preference networks (CP-nets) exploit the power of ceteris paribus rules to represent preferences over combinatorial decision domains compactly. CP-nets have much appeal. However, their study has not yet advanced sufficiently for their widespread use in real-world applications. Known algorithms for deciding dominance---whether one outcome is better than another with respect to a CP-net---require exponential time. Data for CP-nets are difficult to obtain: human subjects data over combinatorial domains are not readily available, and earlier work on random generation is also problematic. Also, much of the research on CP-nets makes strong, often unrealistic assumptions, such as that decision variables must be binary or that only strict preferences are permitted. In this thesis, I address such limitations to make CP-nets more useful. I show how: to generate CP-nets uniformly randomly; to limit search depth in dominance testing given expectations about sets of CP-nets; and to use local search for learning restricted classes of CP-nets from choice data.

La modélisation structurée de préférences, fondée sur les notions d'indépendance préférentielle, a un potentiel énorme pour fournir des approches efficaces pour la représentation et le raisonnement sur les préférences des décideurs dans les applications de la vie réelle. Cette thèse soulève la question de la représentation des préférences par une structure graphique. Nous proposons une nouvelle lecture de réseaux possibilistes, que nous appelons p-pref nets, où les degrés de possibilité représentent des degrés de satisfaction. L'approche utilise des poids de possibilité non instanciés (appelés poids symboliques), pour définir les tables de préférences conditionnelles. Ces tables donnent naissance à des vecteurs de poids symboliques qui codent les préférences qui sont satisfaites et celles qui sont violées dans un contexte donné. Nous nous concentrons ensuite sur les aspects théoriques de la manipulation de ces vecteurs. En effet, la comparaison de ces vecteurs peut s'appuyer sur différentes méthodes: celles induites par la règle de chaînage basée sur le produit ou celle basée sur le minimum que sous-tend le réseau possibiliste, les raffinements du minimum le discrimin, ou leximin, ainsi que l'ordre Pareto, et le Pareto symétrique qui le raffine. Nous prouvons que la comparaison par produit correspond exactement au celle du Pareto symétrique et nous nous concentrons sur les avantages de ce dernier par rapport aux autres méthodes. En outre, nous montrons que l'ordre du produit est consistant avec celui obtenu en comparant des ensembles de préférences satisfaites des tables. L'image est complétée par la proposition des algorithmes d'optimisation et de dominance pour les p-pref nets. Dans ce travail, nous discutons divers outils graphiques pour la représentation des préférences. Nous nous focalisons en particulier sur les CP-nets car ils partagent la même structure graphique que les p-pref nets et sont basés sur la même nature de préférences. Nous prouvons que les ordres induits par les CP-nets ne peuvent pas contredire ceux des p-pref nets et nous avons fixé les contraintes nécessaires pour raffiner les ordres des p-pref nets afin de capturer les contraintes Ceteris Paribus des CP-nets. Cela indique que les CP-nets représentent potentiellement une sous-classe des p-pref nets avec des contraintes. Ensuite, nous fournissons une comparaison approfondie entre les différents modèles graphiques qualitatifs et quantitatifs, et les p-pref nets. Nous en déduisons que ces derniers peuvent être placés à mi- chemin entre les modèles qualitatifs et les modèles quantitatifs puisqu'ils ne nécessitent pas une instanciation complète des poids symboliques alors que des informations supplémentaires sur l'importance des poids peuvent être prises en compte. La dernière partie de ce travail est consacrée à l'extension du modèle proposé pour représenter les préférences de plusieurs agents. Dans un premier temps, nous proposons l'utilisation de réseaux possibilistes où les préférences sont de type tout ou rien et nous définissons le conditionnement dans le cas de distributions booléennes. Nous montrons par ailleurs que ces réseaux multi-agents ont une contrepartie logique utile pour vérifier la cohérence des agents. Nous expliquons les étapes principales pour transformer ces réseaux en format logique. Enfin, nous décrivons une extension pour représenter des préférences nuancées et fournissons des algorithmes pour les requêtes d'optimisation et de dominance. / Structured modeling of preference statements, grounded in the notions of preferential independence, has tremendous potential to provide efficient approaches for modeling and reasoning about decision maker preferences in real-life applications. This thesis raises the question of representing preferences through a graphical structure. We propose a new reading of possibilistic networks, that we call p-pref nets, where possibility weights represent satisfaction degrees. The approach uses non-instantiated possibility weights, which we call symbolic weights, to define conditional preference tables. These conditional preference tables give birth to vectors of symbolic weights that reflect the preferences that are satisfied and those that are violated in a considered situation. We then focus on the theoretical aspects of handling of these vectors. Indeed, the comparison of such vectors may rely on different orderings: the ones induced by the product-based, or the minimum based chain rule underlying the possibilistic network, the discrimin, or leximin refinements of the minimum- based ordering, as well as Pareto ordering, and the symmetric Pareto ordering that refines it. We prove that the product-based comparison corresponds exactly to symmetric Pareto and we focus on its assets compared to the other ordering methods. Besides, we show that productbased ordering is consistent with the ordering obtained by comparing sets of satisfied preference tables. The picture is then completed by the proposition of algorithms for handling optimization and dominance queries. In this work we discuss various graphical tools for preference representation. We shed light particularly on CP-nets since they share the same graphical structure as p-pref nets and are based on the same preference statements. We prove that the CP-net orderings cannot contradict those of the p-pref nets and we found suitable additional constraints to refine p-pref net orderings in order to capture Ceteris Paribus constraints of CP-nets. This indicates that CP-nets potentially represent a subclass of p-pref nets with constraints. Finally, we provide an thorough comparison between the different qualitative and quantitative graphical models and p-pref nets. We deduce that the latter can be positioned halfway between qualitative and quantitative models since they do not need a full instantiation of the symbolic weights while additional information about the relative strengths of these weights can be taken into account. The last part of this work is dedicated to extent the proposed model to represent multiple agents preferences. As a first step, we propose the use of possibilistic networks for representing all or nothing multiple agents preferences and define conditioning in the case of Boolean possibilities. These multiple agents networks have a logical counterpart helpful for checking agents consistency. We explain the main steps for transforming multiple agents networks into logical format. Finally, we outline an extension with priority levels of these networks and provide algorithms for handling optimization and dominance queries.

La croissance exponentielle des données personnelles, et leur mise à disposition sur la toile, a motivé l’émergence d’algorithmes d’apprentissage de préférences à des fins de recommandation, ou d’aide à la décision. Les réseaux de préférences conditionnelles (CP-nets) fournissent une structure compacte et intuitive pour la représentation de telles préférences. Cependant, leur nature combinatoire rend leur apprentissage difficile : comment apprendre efficacement un CP-net au sein d’un milieu bruité, tout en supportant le passage à l’échelle ?Notre réponse prend la forme de deux algorithmes d’apprentissage dont l’efficacité est soutenue par de multiples expériences effectuées sur des données réelles et synthétiques.Le premier algorithme se base sur des requêtes posées à des utilisateurs, tout en prenant en compte leurs divergences d’opinions. Le deuxième algorithme, composé d’une version hors ligne et en ligne, effectue une analyse statistique des préférences reçues et potentiellement bruitées. La borne de McDiarmid est en outre utilisée afin de garantir un apprentissage en ligne efficace. / The rapid growth of personal web data has motivated the emergence of learning algorithms well suited to capture users’ preferences. Among preference representation formalisms, conditional preference networks (CP-nets) have proven to be effective due to their compact and explainable structure. However, their learning is difficult due to their combinatorial nature.In this thesis, we tackle the problem of learning CP-nets from corrupted large datasets. Three new algorithms are introduced and studied on both synthetic and real datasets.The first algorithm is based on query learning and considers the contradictions between multiple users’ preferences by searching in a principled way the variables that affect the preferences. The second algorithm relies on information-theoretic measures defined over the induced preference rules, which allow us to deal with corrupted data. An online version of this algorithm is also provided, by exploiting the McDiarmid's bound to define an asymptotically optimal decision criterion for selecting the best conditioned variable and hence allowing to deal with possibly infinite data streams.