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 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.

Ziel dieser Dissertation ist es, den Begriff des Risikos unter den Aspekten seiner Quantifizierung durch robuste Darstellungen zu untersuchen. In einem ersten Teil wird Risiko anhand Kontext-Invarianter Merkmale betrachtet: Diversifizierung und Monotonie. Wir führen die drei Schlüsselkonzepte, Risikoordnung, Risikomaß und Risikoakzeptanzfamilen ein, und studieren deren eins-zu-eins Beziehung. Unser Hauptresultat stellt eine eindeutige duale robuste Darstellung jedes unterhalbstetigen Risikomaßes auf topologischen Vektorräumen her. Wir zeigen auch automatische Stetigkeitsergebnisse und robuste Darstellungen für Risikomaße auf diversen Arten von konvexen Mengen. Diese Herangehensweise lässt bei der Wahl der konvexen Menge viel Spielraum, und erlaubt damit eine Vielfalt von Interpretationen von Risiko: Modellrisiko im Falle von Zufallsvariablen, Verteilungsrisiko im Falle von Lotterien, Abdiskontierungsrisiko im Falle von Konsumströmen... Diverse Beispiele sind dann in diesen verschiedenen Situationen explizit berechnet (Sicherheitsäquivalent, ökonomischer Risikoindex, VaR für Lotterien, "variational preferences"...). Im zweiten Teil, betrachten wir Präferenzordnungen, die möglicherweise zusätzliche Informationen benötigen, um ausgedrückt zu werden. Hierzu führen wir einen axiomatischen Rahmen in Form von bedingten Präferenzordungen ein, die lokal mit der Information kompatibel sind. Dies erlaubt die Konstruktion einer bedingten numerischen Darstellung. Wir erhalten eine bedingte Variante der von Neumann und Morgenstern Darstellung für messbare stochastische Kerne und erweitern dieses Ergebnis zur einer bedingten Version der "variational preferences". Abschließend, klären wir das Zusammenpiel zwischen Modellrisiko und Verteilungsrisiko auf der axiomatischen Ebene. / The goal of this thesis is the conceptual study of risk and its quantification via robust representations. We concentrate in a first part on context invariant features related to this notion: diversification and monotonicity. We introduce and study the general properties of three key concepts, risk order, risk measure and risk acceptance family and their one-to-one relations. Our main result is a uniquely characterized dual robust representation of lower semicontinuous risk orders on topological vector space. We also provide automatic continuity and robust representation results on specific convex sets. This approach allows multiple interpretation of risk depending on the setting: model risk in the case of random variables, distributional risk in the case of lotteries, discounting risk in the case of consumption streams... Various explicit computations in those different settings are then treated (economic index of riskiness, certainty equivalent, VaR on lotteries, variational preferences...). In the second part, we consider preferences which might require additional information in order to be expressed. We provide a mathematical framework for this idea in terms of preorders, called conditional preference orders, which are locally compatible with the available information. This allows us to construct conditional numerical representations of conditional preferences. We obtain a conditional version of the von Neumann and Morgenstern representation for measurable stochastic kernels and extend then to a conditional version of the variational preferences. We finally clarify the interplay between model risk and distributional risk on the axiomatic level.