CM1

Question 1

Quel est l’ensemble des résultats possibles (outcomes ω) pour un ensemble de variables donné (X_i)_i=1..n ?

Answer 1

Le produit cartésien des domaines des variables :
Π _{i=1 → n} Dom(X_i)

Question 2

Qu’est-ce que la modélisation ?

Answer 2

L’écriture mathématique d’une relation de préférence/de plausibilité

Question 3

Quels sont les deux types de représentation des préférences possibles ?

Answer 3

La représentation ordinale et la représentation cardinale

Question 4

Qu’est-ce que la représentation ordinale des préférences ?

Answer 4

La relation de préférence est exprimée sous la forme d’un pré-ordre/ordre partiel ou complet entre les outcome avec les opérateurs >, ≥, ≈ et ∼

Question 5

Qu’est-ce que la représentation cardinale des préférences ?

Answer 5

La relation de préférence est exprimée grâce à une fonction numérique qui associe une valeur à chaque outcome

Question 6

Comment se traduit le symbole suivant en langage naturel ? ω > ω’

Answer 6

ω est strictement préféré à/plus plausible que ω’

Question 7

Comment se traduit le symbole suivant en langage naturel ? ω ≥ ω’

Answer 7

ω est au moins aussi préféré/plausible ω’

Question 8

Comment se traduit le symbole suivant en langage naturel ? ω ≈ ω’

Answer 8

ω est aussi préféré/plausible que ω’

Question 9

Comment se traduit le symbole suivant en langage naturel ? ω ∼ ω’

Answer 9

ω et ω’ sont incomparables

Question 10

Qu’est-ce qu’un préordre ?

Answer 10

Une relation réflexive et transitive

Question 11

Qu’est-ce qu’un ordre strict (dans le sens d’une relation) ?

Answer 11

Une relation irréflexive et transitive

Question 12

Qu’est-ce qu’un ordre complet ?

Answer 12

Un ordre dont tous les éléments sont comparables deux à deux

Question 13

Que peut-on dire d’une relation de préférence si celle-ci est un ordre complet ?

Answer 13

Tous les outcomes peuvent être ordonnés de façon à proposer un ordre des préférences

Question 14

Comment passer de la représentation cardinale à ordinale ?

Answer 14

• Si u(ω) > u(ω’), alors ω > ω’
• Si u(ω) ≥ u(ω’), alors ω ≥ ω’
• Si u(ω) ≈ u(ω’), alors ω ≈ ω’

Question 15

Quel défaut la représentation cardinale a-t-elle ?

Answer 15

Il n’est pas possible de représenter l’incomparabilité

Question 16

Qu’est-ce qu’une logique pondérée ?

Answer 16

L’association d’une certaine sûreté ou d’un degré de priorité (qualitatif ou quantitatif) à des formules de logique propositionnelle

Question 17

Quelles sont les deux formes de logique pondérée ?

Answer 17

La logique possibiliste et la logique de pénalité

Question 18

Quelle fonction utilise la logique possibiliste ?

Answer 18

π : Ω → [0, 1], la distribution de possibilité

Question 19

Comment interpréter les valeurs associées aux outcome par la fonction π ?

Answer 19

• Si π(ω) = 1, rien n’empêche ω d’être plausible/satisfaisant
• Si π(ω) = 0, ω n’est pas plausible/satisfaisant
• Si π(ω) > π(ω’), ω est plus satisfaisant/plausible que ω’

Question 20

Qu’est-ce qu’une base de connaissances générales ?

Answer 20

Σ = {(φ_i, a_i)|i = 1, . . . , n} telle que ∀i = 1, . . . , n π(¬φ_i) ≤ 1 − a_i (un outcome et son contraire ne peuvent avoir en tout une valeur supérieur à 1)

Question 21

Comment se calcule l’unique distribution de possibilité associée à une base de connaissances générale Σ ?

Answer 21

∀ ω ∈ Ω,
- Si ω |= φ₁ ∧ … ∧ φ_n, π(ω) = 1 (si toutes les formules de Σ sont vérifiées par ω, possibilité maximale)
- Sinon, π(ω) = 1 - max{a_i |(φ_i , a_i) ∈ Σ, ω |!= φ_i} (on enlève à la plausibilité associée à ω la valeur de la formule la plus plausible de Σ qui n’est pas vérifiée par ω)

Question 22

Quelle fonction utilise la logique de pénalité ?

Answer 22

p : Ω → {R}, la distribution de pénalité

Question 23

Comment interpréter les valeurs associées aux outcome par la fonction p ?

Answer 23

Si p(ω) < p(ω’), ω est plus satisfaisant/plausible que ω’

Question 24

Qu’est-ce qu’une base de pénalité ?

Answer 24

Σ = {(φ_i, a_i)|i = 1, . . . , n}

Question 25

Comment se calcule l’unique distribution de pénalité associée à une base de pénalité Σ ?

Answer 25

∀ ω ∈ Ω,
- Si ω |= φ₁ ∧ … ∧ φ_n, p(ω) = 0 (si toutes les formules de Σ sont vérifiées par ω, pas de pénalité)
- Sinon, p(ω) = Somme{a_i |(φ_i , a_i) ∈ Σ, ω |!= φ_i} (on pénalise ω de la valeur de chaque de Σ qui n’est pas vérifiée par ω)

Question 26

Qu’est-ce qu’une logique conditionnelle ?

Answer 26

Une logique dans laquelle les préférences sont exprimées les unes en fonction des autres, par exemple :
C : A > B (équivalent à (C ∧ A) > (C ∧ B))

Question 27

Qu’est-ce que le principe de von Wright ?

Answer 27

Si p > q, alors (p ∧ ¬q) > (q ∧ ¬p), c’est-à-dire que si p > q est dans les préférences conditionnelles, alors les outcomes vérifiant p ∧ ¬q seront préférés à ceux vérifiant q ∧ ¬p

Question 28

Quelles sont les différentes sémantiques utilisées pour comparer les préférences ?

Answer 28

• La sémantique forte
• La sémantique Ceteris Paribus
• La sémantique optimiste
• La sémantique pessimiste
• La sémantique opportuniste

Question 29

Qu’est-ce que la sémantique forte ?

Answer 29

Si p > q, p est toujours préféré à q, c’est-à-dire que n’importe quel outcome vérifiant p ∧ ¬q est préféré à n’importe quel outcome vérifiant q ∧ ¬p
(∀ > ∀)
Autrement dit, le pire outcome vérifiant p ∧ ¬q est préféré au meilleur outcome vérifiant q ∧ ¬p

Question 30

Qu’est-ce que la sémantique Ceteris Paribus ?

Answer 30

Si p > q, c’est-à-dire que n’importe quel outcome vérifiant p ∧ ¬q est préféré à n’importe quel outcome vérifiant q ∧ ¬p s’ils sont tous les deux complétés de la même façon
(p ∧ x > q ∧ x ∀, p ∧ x !> q ∧ y)

Question 31

Qu’est-ce que la sémantique optimiste ?

Answer 31

Si p > q, il existe au moins un outcome vérifiant p ∧ ¬q préféré à n’importe quel outcome vérifiant q ∧ ¬p
(∃ > ∀)
Autrement dit, le meilleur outcome vérifiant p ∧ ¬q est préféré au meilleur outcome vérifiant q ∧ ¬p

Question 32

Qu’est-ce que la sémantique pessimiste ?

Answer 32

Si p > q, n’importe quel outcome vérifiant p ∧ ¬q est préféré à au moins un outcome vérifiant q ∧ ¬p (le même pour tous)
(∀ > ∃)
Autrement dit, le pire outcome vérifiant p ∧ ¬q est préféré au pire outcome vérifiant q ∧ ¬p

Question 33

Qu’est-ce que la sémantique opportuniste ?

Answer 33

Si p > q, il existe au moins un outcome vérifiant p ∧ ¬q préféré à au moins un outcome vérifiant q ∧ ¬p
(∃ > ∃)
Autrement dit, le pire outcome vérifiant p ∧ ¬q est préféré au pire outcome vérifiant q ∧ ¬p

Question 34

Qu’est-ce qu’un ensemble de préférences ?

Answer 34

Un ensemble de préférences {P}_> = {p_i >_> q_i | i=1..n} obéissant à la même sémantique, avec < ∈ {st, cp, opt, pes, opp}

Question 35

Qu’est-ce qu’un ordre qui satisfait un ensemble de préférences {P}_> ?

Answer 35

C’est un ordre qui est un modèle de {P}_>, c’est-à-dire qui satisfait chaque formule de {P}_>

Question 36

Qu’est-ce que le principe de spécificité minimale ?

Answer 36

Chaque outcome est le plus haut (le plus satisfaisant) possible dans le pré-ordre associé à un ensemble de préférences donné.

Question 37

Sur quel principe repose le principe de spécificité minimale ?

Answer 37

On considère qu’un outcome est satisfaisant, sauf s’il existe une raison de dire le contraire.

Question 38

Qu’est-ce que le principe de spécificité maximale ?

Answer 38

Chaque outcome est le plus bas (le moins satisfaisant) possible dans le pré-ordre associé à un ensemble de préférences donné.

Question 39

Sur quel principe repose le principe de spécificité maximale ?

Answer 39

On considère qu’un outcome n’est pas satisfaisant, sauf s’il existe une raison de dire le contraire.

Question 40

Pour quelles sémantiques existe-t-il un modèle minimalement spécifique (unique) ?

Answer 40

• Sémantique forte
• Sémantique Ceteris Paribus
• Sémantique optimiste

Question 41

Pour quelles sémantiques existe-t-il un modèle maximalement spécifique (unique) ?

Answer 41

• Sémantique forte
• Sémantique Ceteris Paribus
• Sémantique pessimiste

Question 42

Algorithme de calcul d’un modèle minimalement unique pour la sémantique optimiste (entrée, sortie, algorithme)

Answer 42

• Entrée : {P} = {s_i : p_i >_opt q_i | i=1..n}
• Sortie : modèle minimalement unique pour {P}
• Algorithme :
  
  • i = 0
  • {L}({P}) ← {(L(s_i), R(s_i)) | s_i ∈ {P}} où L(s_i) = Mod(p_i ∧ ¬q_i) et R(s_i) = Mod(q_i ∧ ¬p_i)
  • Tant que Ω != ∅ :
    
    • i+=1
    • E_i = {t | t ∈ Ω, !∃ (L(s_i), R(s_i)) ∈ {L}({P}), t ∈ R(s_i)}
    • Si E_i = ∅ :
      
      • i-=1
      • Sortir de la boucle
    • Ω = Ω\E_i
    • Supprimer de Ω les (L(s_i), R(s_i) tels que L(s_i) ∩ E_i != ∅
  • Renvoyer E₁ ≥ … ≥ E_i

Question 43

Qu’est-ce que l’indépendance de préférences ?

Answer 43

Un ensemble de variables X est indépendant d’un ensemble Y si et seulement si les préférences sur X peuvent être exprimées alors que les valeurs données aux variables de Y sont fixées : ∀ x, x’ ∈ X , ∀ y, y’ ∈ Y, xy ≥ x’y ⇔ xy’ ≥ x’y’

Question 44

Qu’est-ce que l’indépendance conditionnelle de préférences ?

Answer 44

Un ensemble de variables X est indépendant d’un ensemble Y à la condition d’un ensemble Z si et seulement si les préférences sur X peuvent être exprimées alors que les valeurs données aux variables de Y sont fixées lorsque les variables de Z ont une certaine valeur : ∀ x, x’ ∈ X , ∀ y, y’ ∈ Y, xyz ≥ x’yz ⇔ xy’z ≥ x’y’z

Question 45

Sur quel principe sont construits les CP-nets ?

Answer 45

Sur l’indépendance conditionnelle des préférences

Question 46

Comment construire un CP-net ?

Answer 46

Les sommets représentent les variables et les arcs sont orientés des variables qui conditionnent vers les variables conditionnées

Question 47

Quelle sémantique est associée aux CP-nets ?

Answer 47

La sémantique Ceteris Paribus

Question 48

Qu’est-ce que le “worsening flip” ?

Answer 48

C’est le fait que dans le CP-net, les seuls outcomes comparables sont ceux qui n’ont qu’un critère qui diffère

Question 49

Quels outcomes peuvent être comparés à l’aide d’un CP-net ?

Answer 49

Les outcomes pour lesquels il existe une chaîne de préférences tel que chaque couple d’éléments qui s’enchaînent n’ont qu’un critère qui diffère (Ceteris Paribus)

Question 50

Quel est un défaut des CP-nets ?

Answer 50

Tous les ordres partiels ne peuvent pas être représentés par des CP-nets