Admin CliCours
Modèles graphiques décomposables pour la décision individuelle et collective
Modèles graphiques de représentation de préférences
Les modèles graphiques, tels que les réseaux bayésiens, ont connu un grand succès en optimisant l’élicitation et le raisonnement avec probabilités (voir par exemple Cowell et al. (1999)). L’efficacité de ces modèles est fondée sur l’exploitation des indépendances existantes dans le modèle probabiliste. Ce succès a suscité l’idée d’utiliser les concepts d’indépendance des utilités pour arriver à des modèles graphiques efficaces pour l’élicitation et le raisonnement avec des utilités (Bacchus et Grove, 1995), ou bien avec des préférences qualitatives. Ainsi, au cours des dernières années, différents modèles graphiques pour représenter des préférences ont été développés.
CP-Nets
Les CP-Nets (acronyme pour Conditional Preference Networks – réseaux de préférences conditionnelles) ont été introduits par Boutilier et al. (1999). Un CP-Net est un modèle graphique développé pour représenter de manière compacte des préférences qualitatives du type ceteris paribus dans des espaces multi-attributs. Pour cela, un CP-Net utilise un graphe orienté (pas forcément acyclique) où chaque nœud correspond à un attribut. Chaque nœud est préférentiellement indépendant des autres nœuds conditionnellement à 1.3. Modèles graphiques de représentation de préférences 29 ses parents dans le graphe. Formellement, un CP-Net C est un n-uplet hA,cp, cpti, tel que : 1. A est l’ensemble de nœuds qui correspond aux attributs du problème {A1,…,An}. 2. cp est un ensemble d’arêtes orientées h −−−→ Ai ,Aj i (nommées cp-arcs) signifiant que les préférences du décideur sur les valeurs de Aj sont dépendantes de la valeur de Ai . Soit PAj = {Ai |h−−−→ Ai ,Aj i ∈ cp} l’ensemble de parents de Aj . Les indépendances conditionnelles du réseau impliquent que pour tout Ai , nous avons CPI(Ai ,PAi ,Yi) où Yi = A − {PAi ∪ {Ai}}. 3. cpt associe pour chaque Ai ∈ A, un tableau de préférences conditionnelles (CPT – de l’anglais Conditional Preference Table), c’est-à-dire une application de PAi à une relation de préférence sur Ai . Selon la sémantique standard des CP-Nets, les préférences exprimées dans le CPT d’un CP-net sont des préférences strictes (≻), mais des extensions où les préférences dans les CPT sont des préférences non-strictes (%) ont aussi été proposées (Brafman et Dimopoulos, 2004). La sémantique standard des CP-Nets est définie en fonction des rangements des alternatives qui sont consistants avec les contraintes imposées par ses CPT. Formellement, on définit les rangements des alternatives qui sont consistants avec un CP-Net de la manière suivante : Définition 1.15. Soit C un CP-Net sur des attributs A, Ai ∈ A un attribut, et PAi ⊂ A les parents de Ai dans C. Soit Yi = A − {PAi ∪ {Ai}}. Soit ≻pAi l’ordre de préférences sur Ai induit par le CPT(Ai) en fonction de l’instantiation aPAi ∈ PAi . Enfin, soit ≻ un rangement des alternatives dans A. 1. Un rangement des alternatives ≻ satisfait ≻pAi ssi (aYi ,aPAi ,ai) ≻ (aYi ,aPAi ,a′ i ), pour tout aYi ∈ Yi , quand ai ≻pAi a ′ i . 2. Un rangement des alternatives ≻ satisfait CPT(Ai) ssi il satisfait ≻pAi pour tout aPAi ∈ PAi . 3. Un rangement des alternatives ≻ satisfait le CP-Net C ssi il satisfait CPT(Ai) pour tout attribut Ai . Dans ce cas, on dit que ≻ est consistant avec le CP-Net C. Un CP-Net C est satisfiable ssi il existe un rangement des alternatives ≻ qui satisfait C. Exemple 1.13. La Figure 1.3 illustre l’utilisation d’un CP-Net pour un problème de choisir un vol pour aller à une conférence à Recife (Brésil) à partir de Paris (France). Ce réseau possède quatre attributs correspondants aux paramètres du vol : • D – Date du départ. Le décideur préfère partir un jour avant la conférence (d 1j ) plutôt que deux jours avant (d 2j ). 30 1. Modélisation et Représentation de Préférences H A D S d 1j ≻ d 2j h d s e ≻ s a h n s a ≻ s e a TAM ≻ a d TAP 1j h d ≻ h n d 2j h n ≻ h d Fig. 1.3 – Un CP-Net pour l’exemple du choix de vols • A – Compagnie aérienne. Le décideur préfère TAM (a T AM) à TAP (a T AP ). • H – Horaire du vol. Pour partir deux jours avant la conférence, le décideur préfère un vol nocturne, h n (comme ça il peut travailler pendant la journée). Pour partir un jour avant la conférence, le décideur préfère un vol diurne, h d (sinon il ne va pas arriver à temps). • S – Classe de service. Pour un vol nocturne, le décideur préfère la classe d’affaires (s a ) puisqu’il n’arrive pas à dormir dans les sièges inconfortables de la classe économique (s e ). Pour un vol pendant la journée les préférences s’inversent puisque le décideur ne pense pas à dormir. Comme on peut le constater dans l’exemple, les CP-Nets permettent l’expression de deux types de préférences ceteris paribus : des préférences inconditionnelles, comme « je préfère TAM à TAP » ; et des préférences conditionnelles, comme « si je pars un jour avant la conférence je préfère un vol diurne ; dans le cas contraire je préfère un vol nocturne ». La figure 1.4 montre les préférences induites par le CP-Net. Les flèches sont orientées d’une alternative moins préférée vers une alternative plus préférée selon une préférence ceteris paribus. Par exemple, une flèche lie (d 2j ,hn ,se ,aT AM) et (d 1j ,hn ,se ,aT AM) parce que ces deux alternatives diffèrent seulement dans la date du départ et, toutes choses égales par ailleurs, d 1j ≻ d 2j (préférence inconditionnelle). Analogiquement, une flèche lie (d 1j ,hn ,se ,aT AM) et (d 1j ,hn ,sa ,aT AM) parce que ces deux alternatives diffèrent seulement dans la classe de service et, étant donné qu’il s’agit d’un vol nocturne (h n ), s a ≻ s e (préférence conditionnelle). Notons que le CP-net induit une relation de préférences partielle (quand le graphe de préférences induit est acyclique, nous avons un ordre partiel sur des alternatives). Par exemple, nous ne pouvons pas décider si (d 1j ,hn ,sa ,aT AP ) ≻ (d 1j ,hn ,se ,aT AM) ou vice-versa. Toutefois, il y a des préférences qui ne sont pas dérivées directement des CPT mais qui sont révélées par transitivité, par exemple, nous pouvons affirmer que 1.3. Modèles graphiques de représentation de préférences 31 (d 2j ,hd ,sa ,aTAM) (d 2j ,hd ,se ,aTAM) (d 2j ,hn,se ,aTAM) (d 2j ,hn,sa ,aTAM) (d 1j ,hn,se ,aTAM) (d 1j ,hn,sa ,aTAM) (d 1j ,hd ,sa ,aTAM) (d 1j ,hd ,se ,aTAM) (d 2j ,hd ,sa ,aTAP ) (d 2j ,hd ,se ,aTAP ) (d 2j ,hn,sa ,aTAP ) (d 1j ,hd ,sa ,aTAP ) (d 2j ,hn,se ,aTAP ) (d 1j ,hd ,se ,aTAP ) (d 1j ,hn,sa ,aTAP ) (d 1j ,hn,se ,aTAP ) Fig. 1.4 – Préférences sur des configurations pour l’exemple de choix de vols (d 2j ,hn ,sa ,aT AM) ≻ (d 2j ,hd ,se ,aT AP ). En effet, déterminer si on peut conclure que a ≻ a ′ à partir d’un CP-Net C (nous notons cela par C a ≻ a ′ ), équivaut à trouver un chemin de a ′ à a dans le graphe de préférences induites. Dans la littérature de CP-Nets, on le nomme une séquence d’échanges améliorants (en anglais, on l’appelle une improving flipping sequence). Définition 1.16. (Boutilier et al., 1999) Soit C un CP-Net sur les attributs A ; PAi l’ensemble de parents de Ai ∈ A et Yi = A − {PAi ∪ {Ai}}. Soit (aPAi ,a′ i ,aYi ) une alternative dans A. Une alternative (aPAi ,ai ,aYi ) peut être obtenue par un échange améliorant à partir de l’alternative (aPAi ,a′ i ,aYi ) par rapport à l’attribut Ai si ai ≻ a ′ i 32 1. Modélisation et Représentation de Préférences étant donné aPAi dans C. ∗ Une séquence d’échanges améliorants dans C est toute séquence d’alternatives a 1 ,. .. ,ak telle que a j+1 est obtenue par un échange améliorant à partir de a j par rapport à un attribut quelconque (pout tout j < k).† Toute séquence d’échanges améliorants telle que a 1 = a ′ et a k = a est une séquence d’échanges améliorants de l’alternative a ′ à l’alternative a. Théorème 1.2. (Boutilier et al., 1999) Soit C un CP-Net sur les attributs A : ∀a,a′ ∈ A, C a ≻ a ′ ⇔ il existe une séquence d’échanges améliorants de a ′ à a. Il s’avère que la recherche d’une séquence d’échanges améliorants est une tâche difficile (même quand les attributs ont un domaine binaire). Sa compléxité varie en fonction de la structure du CP-Net. Nous savons que (Boutilier et al., 2004a; Goldsmith et al., 2005) : 1. Quand le CP-Net binaire est un arbre orienté, la complexité est quadratique dans le nombre d’attributs. 2. Quand le CP-Net binaire est un multi-arbre (c’est-à-dire que le graphe non-orienté induit n’a pas de cycles), la complexité est polynomiale dans la taille de la description du réseau. 3. Quand le CP-Net binaire est un graphe orienté connecté simple (c’est-à-dire qu’il y a au maximum un chemin orienté entre deux nœuds), le problème est NP-complet. 4. Le problème reste NP-complet si le nombre de chemins orientés entre deux nœuds est limité par une constante. 5. Le problème est PSPACE-complet‡ si le CP-Net possède des cycles. Ainsi, étant donné deux alternatives a ′ ,a ∈ A, et un CP-Net C sur A, déterminer si nous pouvons affirmer C a ≻ a ′ ou C a ′ ≻ a (dans la littérature des CP-Nets, on l’appelle le problème de dominance) est loin d’être une tâche facile pour une bonne partie des CP-Nets. Toutefois, si l’objectif est de trouver la meilleure alternative dans A (problème d’optimisation), la tâche peut être plus simple (Domshlak et al., 2003; Boutilier et al., 2004a,b) : ∗De manière analogue, une alternative (aPAi , ai, yi) peut être obtenue par un échange empirant à partir de l’alternative (aPAi , a′ i , aYi ) par rapport à l’attribut Ai si a ′ i ≻ ai, étant donné aPAi dans C. †De manière analogue, une séquence d’échanges empirants dans C est toute séquence d’alternatives a 1 , . . . , ak telle que a j+1 est obtenue par un échange empirant à partir de a j par rapport à un attribut quelconque (pout tout j < k). ‡PSPACE est la classe de tous les langages reconnaissables en espace polynomial par un programme qui utilise une machine de Turing déterministe et qui termine pour toute entrée. Le fait qu’un problème soit PSPACE-complet est une évidence encore plus forte qu’il soit intractable que s’il était NP-complet, en effet nous savons que P ⊆ NP ⊆ PSPACE (Garey et Johnson (1979, pages 170–178), Papadimitriou (1994, pages 455–490.)). 1.3. Modèles graphiques de représentation de préférences 33 1. Si le CP-Net est un graphe acyclique, la complexité est polynomiale dans le nombre d’attributs. Intuitivement, on parcourt le réseau de haut en bas (c’est-à-dire des parents aux descendants), en fixant la valeur de chaque attribut à sa valeur préférée étant donnée l’instantiation de ses parents. Toutefois, s’il y a des contraintes sur des configurations possibles, le problème devient NP-complet. 2. Si le CP-Net possède des cycles, déterminer s’il y a une alternative non-dominée est un problème NP-complet. L’ordre partiel induit par un CP-Net suppose implicitement que les attributs-parents sont plus importants que les attributs-fils, c’est-à-dire que les préférences sur les attributsparents ont plus de priorité que les préférences sur les attributs-fils. Toutefois, les CP-Nets ne permettent pas que le décideur exprime l’importance entre deux attributs qui ne sont pas un descendant de l’autre dans le graphe. Exemple 1.14. Dans l’exemple 1.7 (page 20), nous avons vu que pour l’auteur de l’épigraphe de ce chapitre, les préférences sur l’attribut « attitude » ont une priorité plus élevée que les préférences sur l’attribut « nourriture ». Toutefois, ces deux attributs sont conditionnellement indépendants. Un CP-Net ne permet pas d’exprimer une telle relation de préférences, malgré le fait qu’elle soit suffisamment simple pour être modélisable par une fonction d’utilité additive. Exemple 1.15. Le CP-Net de la figure 1.3 ne peut pas déterminer si l’option (d 1j ,hd ,se , a T AP ) (la préférence sur A est violée) est meilleure que l’option (d 1j ,hn ,se ,aT AM) (la préférence sur H est violée). Or il est fort probable que pour le décideur il soit plus important d’arriver dans les temps que de voyager avec sa compagnie aérienne favorite, donc la première option serait préférable à la deuxième. Les TCP-Nets (Trade-off CP-Nets) ont été introduits in Brafman et Domshlak (2002) pour permettre l’expression de l’importance relative entre attributs∗ .
TCP-Nets
Les TCP-Nets étendent les CP-Nets en permettant l’expression de deux types d’importance relative entre attributs : l’importance relative inconditionnelle, par exemple, « l’horaire du vol est plus important que la compagnie aérienne » ; et l’importance relative conditionnelle, par exemple, « l’horaire du vol est plus important que la compagnie aérienne, si je présente dans le premier jour de la conférence. Sinon, la compagnie aérienne est plus importante ». Formellement, on peut définir l’importance relative entre attributs comme suit (Brafman et al., 2006) : ∗Un formalisme logique qui généralise les CP-Nets (c’est-à-dire que les CP-Nets peuvent être représentés dans ce langage) et qui est capable de représenter des préférences lexicographiques a aussi été proposé (Wilson, 2004). Toutefois, dans ce cas nous n’avons plus de modèle graphique.
Modélisation et Représentation de Préférences D
éfinition 1.17. Soient Ai , Aj deux attributs conditionnellement indépendants étant donné W = A − {Ai ,Aj} (CPI(Ai ,W, Aj )). On dit que Ai est inconditionnellement plus important que Aj (on écrit Ai ⊲ Aj ), si pour tout aW ,ai ,a′ i ,aj ,a′ j tels que ai ≻ a ′ i étant donné aW , alors : (ai ,aj ,aW ) ≻ (a ′ i ,a′ j ,aW ) Définition 1.18. Soient Ai , Aj deux attributs conditionnellement indépendants étant donné W = A − {Ai ,Aj} (CPI(Ai ,W, Aj )), et soit Z ⊆ W. On dit que Ai est plus important que Aj étant donné aZ (on écrit Ai ⊲z Aj ), ssi pour tout aV ∈ A−({Ai ,Aj , }∪ Z),aj ,a′ j , ai ,a′ i tels que ai ≻ a ′ i étant donnés aZ,aV : (ai ,aj ,aZ,aV ) ≻ (a ′ i ,a′ j ,aZ,aV ) Si pour tout aZ ∈ Z nous avons, soit Ai ⊲z Aj , soit Aj⊲zAi , nous disons que l’importance relative de Ai et Aj est conditionnelle à Z (on écrit RI(Ai ,Aj |Z)). Pour exprimer des importances relatives entre attributs, les TCP-Nets introduisent deux nouveaux types d’arêtes dans le graphe de préférences conditionnelles : les i-arcs , qui sont des arêtes orientées pour les importances relatives inconditionnelles ; et les ci-arcs , qui sont des arêtes non-orientées pour les importances relatives conditionnelles. Formellement, un TCP-Net C est un n-uplet hA,cp, cpt,i,ci, citi, tel que : 1. A, cp et cpt sont comme dans les CP-Nets. 2. i est un ensemble d’arêtes orientées h −−−→ Ai ,Aj i (nommées i-arcs). Un i-arc de Ai à Aj signifie que Ai ⊲ Aj . 3. ci est un ensemble d’arêtes non-orientées hAi ,Aj i (nommées ci-arcs) signifiant que l’importance relative entre les deux attributs Ai et Aj est conditionnée à la valeur des variables d’un ensemble de sélection (selector set, en anglais) Z ⊆ A − {Ai ,Aj} (RI(Ai ,Aj |Z)). 4. cit associe pour chaque ci-arc entre {Ai ,Aj} une fonction du domaine de Z à un ordre ⊲ entre {Ai ,Aj}. Exemple 1.16. Les préférences induites par l’épigraphe de ce chapitre (voir exemple 1.7, page 20) peuvent être facilement réprésentées par un TCP-Net, comme le montre la figure 1.5. Exemple 1.17. Revenons au problème de choix d’un vol pour aller à une conférence à Recife (Brésil) au départ de Paris (France). Supposons que nous avons maintenant un nouvel attribut : 1.3. Modèles graphiques de représentation de préférences 35 A1 A2 a 1 1 ≻ a 2 1 a 1 2 ≻ a 2 2 Fig. 1.5 – Un TCP-net pour l’épigraphe de ce chapitre. Un ci-arc indique que A1 ⊲ A2 H A D C S A d 1j ≻ d 2j h d s e ≻ s a h n s a ≻ s e a TAM ≻ a d TAP 1j h d ≻ h n d 2j h n ≻ h d h d c 1c ≻ c 0c h n c 0c ≻ c 1c a TAP C ⊲ S a TAM S ⊲ C Fig. 1.6 – Un TCP-net pour l’exemple du choix de vols réitéré • C – correspondance. Pour un vol diurne, le décideur aimerait faire une pause, donc il préfère les vols avec une escale. (c 1c ). Pour un vol nocturne, le décideur préfère dormir pendant le voyage, il préférera donc un vol direct (c 0c ). Le voyageur exprime encore les préférences additionnelles suivantes : • l’horaire du vol est plus important que la compagnie aérienne ; • pour les vols de TAP, la correspondance est plus importante que la classe (Lisbonne est sur le trajet, donc faire une escale là-bas ne prendrait pas beaucoup de temps additionnel), mais pour les vols de TAM, la classe est plus importante que la correspondance (l’escale à São Paulo représente un grand détour). La figure 1.6 illustre l’utilisation d’un TCP-Net pour exprimer les nouvelles préférences du voyageur. La complexité pour résoudre des problèmes de dominance et optimisation avec des TCP-Nets a été moins étudiée que pour les CP-Nets. Toutefois, comme un CP-Net est un cas particulier d’un TCP-Net, les résultats de complexité pour le second seront, dans tous les cas, au moins aussi difficiles à resoudre que pour le premier. Les algorithmes pour raisonner avec des TCP-Nets sont aussi plus difficiles à construire. Ainsi, l’une des stratégies possible est de transformer le TCP-Net en un modèle plus tractable avant de l’utiliser. C’est l’approche adoptée dans Brafman et al. (2004), où le TCP-Net est 36 1. Modélisation et Représentation de Préférences d’abord transformé dans une fonction d’utilité GAI-décomposable pour que l’on puisse raisonner d’une manière efficace avec le modèle. Pourtant, tous les TCP-Nets ne sont pas modélisables par une fonction GAI, les conditions suffisantes et nécessaires pour qu’un TCP-Net soit modélisable par une fonction GAI sont introduites dans Brafman et al. (2004). Réciproquement, notons que toutes les fonctions GAI ne sont pas représentables par un TCP-Net. Supposons que concernant la compagnie aérienne on avait une troisième option, aMEN , avec des préférences a T AM ≻ a T AP ≻ aMEN et que comme le voyageur ne fait pas confiance à la compagnie aMEN , l’horaire du vol est plus important que la compagnie aérienne mais uniquement pour a T AM et a T AP , car il préfère arriver un peu en retard en prenant une autre compagnie (a T AM ou a T AP ) plutôt que d’empreinter aMEN . On voit ici une limite descriptive intrinsèque des TCP-Nets en raison de l’impossibilité de prendre en compte les intensités de préférences entre les attributs en fonction de leur valeurs respectives.
UCP-Nets
Une autre extension des CP-Nets combine la structure du graphe de préférences conditionnelles avec des fonctions d’utilité. Le modèle résultant est un CP-Net où cpt est remplacé pour des fonctions d’utilité. Formellement, un UCP-Net C est un n-uplet hA,cp, ui, tel que : 1. A et cp sont comme dans les CP-Nets. 2. u est une fonction u : A 7→ R, telle que u(a1,…,an) = P i ui(ai ,Pai ). 3. Le graphe de l’UCP-Net est orienté et acyclique (DAG – de l’anglais Directed Acyclic Graph) et les utilités respectent les propriétés d’indépendance conditionnelle pour %, c’est-à-dire que pour tout Ai ∈ A, CPI(Ai ,PAi ,Yi), où Yi = A − {PAi ∪ {Ai}}. Exemple 1.18. La Figure 1.7 illustre un UCP-net pour l’exemple de choix de vols. Ce réseau correspond à la fonction GAI u(d, h, s, a) = u1(d)+u2(h, d)+u3(s,h)+u4(a). Chacun des facteurs ui possède un tableau de préférences dans le réseau. Les tableaux de préférences et l’interprétation GAI du réseau établissent la fonction d’utilité du décideur. Dans l’exemple, à l’alternative (d 1j ,hd ,sa ,aT AM) correspond l’utilité u(d 1j ,hd ,sa ,aT AM) = u1(d 1j ) + u2(h d ,d1j ) + u3(s a ,hd ) + u4(a T AM) = 100 + 40 + 3 + 1 = 144. Avec les utilités cardinales nous avons pu exprimer le fait que le choix de la compagnie aérienne est moins important que les autres attributs. Notons que, du point de vue de la décomposition GAI, le terme u1(d) est redondant (il pourrait être intégré à u2(h, d)), mais en gardant la structure graphique des CP-Nets, on préserve la représentation explicite des dépendances conditionnelles, qui d’une part, facilite l’élicitation, et d’autre part, permet l’utilisation d’algorithmes de résolution plus efficaces.
s |
