CMS

Question 1

À quoi servent les modèles de raisonnement qualitatifs spatiaux-temporels ?

Answer 1

À pallier le problèmes de logique des systèmes en apprentissage (ML) qui ne savent pas créer les bons liens logiques (spatiaux et temporels)

Question 2

Que signifie QSTR ?

Answer 2

Qualitative Spatial and Temporal Reasoning

Question 3

Relations de base de RCC8

Answer 3

• DC : disconnected
• EC : externally connected
• PO : partially overlaps
• EQ : equals
• TPP : tangential proper part
• NTPP : non-tangential propre part

Question 4

Relations de base de l’algèbre des intervalles

Answer 4

• p : precedes
• m : meets
• o : overlaps
• s : starts
• d : during
• f : finishes
• eq : equals

Question 5

Que signifie QCL ?

Answer 5

Qualitative Constraint Language

Question 6

Définition d’un QCL

Answer 6

Un QCL est basé sur un ensemble B fini de relations de base et qui a les propriétés suivantes :
- les relations de bases sont définies sur un domaine infini D
- les relations de base sont JEPD
- B contient l’identité
- B est clos par inversion
- 2^{B</sub> est équipé de l’union, l’intersection, l’inverse et la composition faible}

Question 7

Que signifie JEPD ?

Answer 7

Jointly Exhaustive & Pairwise Disjoint

Question 8

Quelles sont les propriété du domain des relations de bases d’un QCL ?

Answer 8

Il correspond à une entité spatiale ou temporelle et est infini, ce qui rend généralement les relations de bases infinies également : elles correspondent à des ensembles infinis de tuples acceptés

Question 9

Qu’est-ce qu’un ensemble de relations de base jointly exhaustive ? (formule)

Answer 9

Une ensemble de relations de base B tel que ⋃{b ∈ B} = D × D × … × D

Question 10

Qu’est-ce qu’un ensemble de relations de base pariwise disjoint ? (formule)

Answer 10

Une ensemble de relations de base B tel que ∀ b, b’ ∈ B, b != b’ ⇒ b ∩ b’ = ∅

Question 11

Qu’est-ce qu’un ensemble de relations de base qui vérifie la propriété JEPD ? (langage naturel)

Answer 11

Un tuple de ϵ éléments de D, le domaine des relations de base de l’ensemble, peut satisfaire au plus une seule relation de base de B

Question 12

Qu’est-ce qui est exprimé par l’ensemble des relations de base d’un ensemble B ?

Answer 12

Une connaissance définie entre un certain nombre d’entités (arité des relations)

Question 13

Qu’est-ce qui est exprimé par un sous-ensemble de relations de base d’un ensemble B ?

Answer 13

{b₁, …, b_j} avec j < |B| correspond à b₁ ∪ … ∪ b_j, qui représente une certaine connaissance indéfinie

Question 14

Soit B un ensemble de relations de base, qu’est-ce que 2^B ?

Answer 14

L’ensemble des sous-ensembles de relations possibles, donc la connaissance définie et indéfinie entre les entités

Question 15

Qu’est-ce qu’un tuple qui satisfait une relation de base b ?

Answer 15

(x₁, …, x_ϵ) ∈ D^ϵ tel que (x₁, …, x_ϵ) ∈ b

Question 16

Qu’est-ce qu’un tuple qui satisfait un sous-ensemble de relations de base r ∈ 2^B ?

Answer 16

(x₁, …, x_ϵ) ∈ D^ϵ tel que ∃ b ∈ r, (x₁, …, x_ϵ) ∈ b

Question 17

Relations de base de l’algèbre des points

Answer 17

• < : precedes
• = : equals
• > : follows

Question 18

Domaine de RCC8

Answer 18

L’ensemble T_reg des sous-ensembles réguliers non-vides et fermés d’un espace topologique T

Question 19

Domaine de l’algèbre d’intervalle

Answer 19

{ x = (x^-, x⁺) ∈ {Q}² | x^- < x⁺}

Question 20

Domaine de l’algèbre de points

Answer 20

{Q}

Question 21

Inverse d’une relation de base b

Answer 21

b^-1 = {(y, x) | (x, y) ∈ b}

Question 22

Inverse d’un sous-ensemble r de l’ensemble des relations de base B

Answer 22

r^-1 = {b^-1 | b ∈ r}

Question 23

Composition de deux relations de base b et b’

Answer 23

b ∘ b’ = {(x, z) ∈ D² | ∃ y ∈ D, (x, y) ∈ b ∧ (y, z) ∈ b’}

Question 24

Composition de deux sous-ensembles r et r’ de l’ensemble des relations de base B

Answer 24

r ∘ r’ = ⋃{b ∘ b’ | b ∈ r, b’ ∈ r’}

Question 25

Composition faible de deux relations de base b et b’

Answer 25

b ⋄ b’ = {b’’ ∈ B | b’’ ∩ (b ∘ b’) != ∅}

Question 26

Composition faible de deux sous-ensembles r et r’ de l’ensemble des relations de base B

Answer 26

r ⋄ r’ = ⋃{b ⋄ b’ | b ∈ r, b’ ∈ r’}

Question 27

Principe de la composition faible de deux relations de base

Answer 27

Plus petite relation r ∈ 2^B qui contient b ∘ b’

Question 28

Axiomes d’une relation algébrique au sens de Tarski

Answer 28

• Commutativité de ⋃
• Associativité de ⋃
• Axiome d’Huntington : !(!r ∪ !s) ∪ !(!r ∪ s) = r
• Commutativité de ⋄
• Associativité de ⋄
• Loi de l’identité : r ⋄ Id = r
• Involution de ^-1 : (r^-1)^-1 = r
• Distibutivité de ^-1 : (r ∪ s)^-1 = r^-1 ∪ s^-1
• Distributivité involutive de ^-1 : (r ⋄ s)^-1 = r^-1 ⋄ s^-1
• Axiome de Tarski : r^-1 ⋄ !(r ⋄ s) ∪ !s = !s

Question 29

Clôtures de 2^B

Answer 29

2^B est clos par composition faible, union, intersection et inversion

Question 30

Définition d’un sous-classe de relations

Answer 30

Une sous-classe de relations est une partie A ⊆ 2^B qui contient les relations-singletons de 2^B et de B, et qui clos sous inversion, intersection et composition faible

Question 31

Que signifie QCN ?

Answer 31

Qualitative Constraint Network

Question 32

Définition d’un QCN

Answer 32

Un QCN d’un QCL est un tuple (V, C) tel que
- V est un ensemble de variables sur le domaines infini D du langage
- C est un mapping de V² dans 2^B, qui associe un sou-ensemble de relations de base à chaque paire de variables de V

Question 33

Propriétés des contraintes C de QCN

Answer 33

Elles sont binaires et normalisées : ∀ v, v’ ∈ V, C(v, v’) = (C(v’, v))^-1

Question 34

Comment s’assurer de l’application de la condition de normalisation dans un QCN ?

Answer 34

Pour toute contrainte C, en appliquant :
- C(i, j) ← (C(j, i))^-1 ∩ C(i, j)
- C(j, i) ← (C(i, j))^-1 ∩ C(j, i)

Question 35

Qu’est-ce qu’un QCN trivialement incohérent ?

Answer 35

N = (V, C) est trivialement incohérent si et seulement si ∃ v, v’ ∈ V, C(v, v’) = ∅

Question 36

Qu’est-ce qu’une solution pour une QCN ?

Answer 36

Une solution de N = (V, C) est un mapping σ : V → D tel que ∀ v, v’ ∈ V, ∃ b ∈ C(v, v’) tel que (σ(v), σ(v’)) ∈ b

Question 37

Qu’est-ce qu’un QCN satisfiable (ou cohérent) ?

Answer 37

N = (V, C) est cohérent (ou satisfiable) si et seulement si il admet une solution

Question 38

Qu’est-ce qu’un sous-QCN ?

Answer 38

Un QCN N’ = (V, C’) est un sous-QCN de N = (V, C), noté N’ ⊆ N, si ∀ u, v ∈ V, C’(u, v) ⊆ C(u, v)

Question 39

Qu’est-ce qu’un scenario d’un QCN ?

Answer 39

Un scénario d’un QCN N = (V, C) est un sous-QCN S ⊆ N cohérent et atomique

Question 40

Qu’est-ce qu’un QCN atomique ?

Answer 40

N = (V, C) est atomique si et seulement si ∀ v, v’ ∈ V, |C(v, v’)| = 1

Question 41

Complexité du problème de satisfiabilité d’un QCN sur la plupart des langages

Answer 41

NP-complet

Question 42

Complexité du problème de satisfiabilité d’un QCN sur l’algèbre des points

Answer 42

P-TIME

Question 43

Complexité du problème de satisfiabilité d’un QCN sur l’algèbre des intervalles (schéma de preuve)

Answer 43

• Chaque littéral de 3-sat et sa négationassocié à une paire d’intervalles
• Chaque paire d’intervalles associée à une troisième intervalle “middle”
• Pour chaque intervalle, si elle est avant middle, sont littéral associé prend “faux” sinon il prend “vrai”
• La CNF instance de 3-SAT doit être construite de façon à ce qu’au plus deux intervalles correspondantes aux littéraux d’une même clause sont avant “middle”

Question 44

Qu’est-ce que le problème d’étiquetage minimal ?

Answer 44

Soient N = (V, C) un QCN et C(u, v) une contrainte, le problème d’étiquetage minimal consiste à décider si C contient des relations de base infaisables,c’est-à-dire telles qu’il n’existe aucun scénario qui les contienne

Question 45

Complexité du problème d’étiquetage minimal

Answer 45

Le problème d’étiquetage minimal peut être réduit au problème de satisfiabilité d’un QCN, il a donc la même complexité

Question 46

Qu’est-ce que le problème de redondance ?

Answer 46

Soient N = (V, C) un QCN et C(u, v) une contrainte, le problème d’étiquetage minimal consiste à décider si C est impliqué par les autres contraintes de N

Question 47

Complexité du problème de redondance

Answer 47

Le problème de redondance peut être réduit au problème de satisfiabilité d’un QCN, il a donc la même complexité

Question 48

Qu’est-ce qu’un réseau _G^⋄-cohérent ?

Answer 48

Soit N = (V, C) un QCN et G = (V, E) un graphe, N est _G^⋄-cohérent si et seulement si ∀ {v_i, v_j}, {v_j, v_k}, {v_i, v_k} ∈ E, C(v_i, v_j) ⊆ C(v_i, v_k) ⋄ C(v_k, v_j), c’est-à-dire si tous les triplets de variables qui correspondent à des triangles dans G sont clos par composition faible

Question 49

Qu’est-ce qu’un réseau ⋄-cohérent ?

Answer 49

Un réseau _G^⋄-cohérent pour lequel G est complet

Question 50

Propriété des réseaux atomiques ⋄-cohérents

Answer 50

Pour les algèbres de points et d’intervalle et pour RCC8, tout réseau atomique ⋄-cohérent est satisfiable

Question 51

Complexité de vérifier si un réseau est _G^⋄-cohérent

Answer 51

On doit visiter tous les triangles de G : O(O(|V|³) si G est complet et O(∆ · |E|) sinon

Question 52

Qu’est-ce que la procédure de clôture algébrique ?

Answer 52

Soit N = (V, C) un QCN et G = (V, E) un graphe, il s’agit d’appliquer l’opération suivante jusqu’à atteindre un état stable :
∀ {v_i, v_j}, {v_j, v_k}, {v_i, v_k} ∈ E, C(v_i, v_j) ← C(v_i, v_j) ∩ (C(v_i, v_k) ⋄ C(v_k, v_j))

Question 53

Algorithme naïf de clôture algébrique

Answer 53

• Pour tout triplet {v_i, v_j}, {v_j, v_k}, {v_i, v_k} de E, appliquer C(v_i, v_j) ← C(v_i, v_j) ∩ (C(v_i, v_k) ⋄ C(v_k, v_j))
• Si une contrainte C(v_i, v_j) a été modifiée, répéter l’étape précédente

Question 54

Complexité temporelle et spatiale de l’algorithme naïf de clôture algébrique

Answer 54

• Temporelle : On refait l’étape de tous les triplets au plus pour O(|E|) contraintes, O(|B|) fois, donc au total : O(∆ × |E|² × |B|)
• Spatiale : O(1)

Question 55

Algorithme SOTA de clôture algébrique (PWC)

Answer 55

• Pour tout triplet {v_i, v_j}, {v_j, v_k}, {v_i, v_k} de E, appliquer C(v_i, v_j) ← C(v_i, v_j) ∩ (C(v_i, v_k) ⋄ C(v_k, v_j))
• Si une contrainte C(v_i, v_j) a été modifiée, revisiter les contraintes qui ont pu être affectées par cette modification, c’est-à-dire celles qui forment un triangle avec C(v_i, v_j), qui sont au plus Δ

Question 56

Complexité de l’algorithme SOTA de clôture algébrique

Answer 56

• Temporelle : On refait l’étape de tous les triplets au plus pour O(|E|) contraintes, O(|B|) fois, et la révision coûte O(∆ × |E|) donc au total : O(∆ × |E| × |B|)
• Spatiale : O(|E|)

Question 57

Qu’est-ce que _G^⋄(N) ?

Answer 57

La clôture algébrique de N

Question 58

Correction de la _G^⋄-cohérence

Answer 58

Soit N = (V, C) un QCN et G = (V, E) un graphe, si ∅ ∈ _G^⋄(N), alors N est insatisfiable

Question 59

Complétude de la _G^⋄-cohérence

Answer 59

La clôture algébrique n’est pas complète

Question 60

Propriétés de _G^⋄(N) vis-à-vis de N

Answer 60

• Dominance : _G^⋄(N) est le plus grand sous-QCN cohérent de N
• Équivalence : _G^⋄(N) est équivalent à N
• Idempotence : _G^⋄(_G^⋄(N)) = _G^⋄(N)
• Monotonie : Si N’ ⊆ N, _G^⋄(N’) ⊆ _G^⋄(N)

Question 61

Lien entre la tractabilité des QCN et des sous-classes de relations

Answer 61

Une sous-classe de relations A est tractable si et seulement si la classe des QCN définis sur A est tractable, c’est-à-dire si la satisfiabilité de chaque QCN de la classe peut-être décidé satisfiable (ou non) en temps polynomial

Question 62

Comment vérifier qu’un QCN sur l’algèbre des intevalles est tractable en utilisant la Horn-satisfiabilité ?

Answer 62

• Transformer chaque intervalle du QCN en la formule suivante : x^- ≤ x⁺ ∧ x^- != x⁺
• Pour chaque contrainte, la convertir en CNF grâce à la théorie des ordres partiels et vérifier si la formule est Horn : elle contient au plus un littéral positif et un nombre arbitraire de littéraux négatifs
• Si toutes les formules sont de Horn, le QCN est Horn-satisfiable et donc tractable

Question 63

Lien entre la ⋄-cohérence des QCN et les sous-classes de relations

Answer 63

Tout QCN défini à partir d’une sous-classe de relations tractable peut être réécrit en un QCN ⋄-cohérent atomique

Question 64

Qu’est-ce qu’une sous-classe de relations maximale ?

Answer 64

Une sous-classe de relations A qui n’est contenue dans aucune autre

Question 65

Qu’est-ce qu’une sous-classe de relations distributive ?

Answer 65

Une sous-classe de relations A telle que la composition faible est distributive sur les intersections non-vides, c’est-à-dire si pour toutes relations r, s, t telles que (s ∩ t) != ∅
- r ⋄ (s ∩ t) = (r ⋄ s) ∩ (r ⋄ t)
- (s ∩ t) ⋄ r = (s ⋄ r) ∩ (t ⋄ r)

Question 66

Qu’est-ce qu’un sous-ensemble de relations convexe ?

Answer 66

r = {r₁, …, _n} ⊆ 2^B est un sous-ensemble de relations convexe si ∀ r_i, r_j ∈ r, ∀ x₁, x₂, (x₁ < r < x₂, x₁ r₁ y et x₂ r₂ y) ⇒ x {r₁, r₂} y

Question 67

Relation entre la convexité et la distributivité

Answer 67

Les sous-classes de relations distributives sont convexes au sens de Helly

Question 68

Qu’est-ce qu’une sous-classe de relations qui a la propriété d’Helly ?

Answer 68

Une sous-classe de relations A a la propriété d’Helly si et seulement si pour tout sous-ensembles de n relations {r₁, …, r_n}, ⋂_i=1..n r_i != ∅ si et seulement si ∀ i, j ∈ {1, …, n}, r_i ∩ r_j != ∅

Question 69

Lien entre la distributivité et la propriété d’Helly

Answer 69

Une sous-classe de relations est distributive si et seulement si elle a la propriété d’Helly

Question 70

Quand est-ce qu’un QCN ⋄-cohérent défini à partir d’une sous-classe de relations distributive est-il minimal (ne contient aucune relation de base infaisable) ?

Answer 70

Lorsque chaque QCN ⋄-cohérent atomique du langage est satisfiable (comme on l’a vu pour l’algèbre des points et des intervalle, et RCC8)

Question 71

Lien entre la distributivité et la tractabilité

Answer 71

Les sous-classes de relations distributives sont tractables

Question 72

Comment identifier une sous-classe de relations distributive maximale ?

Answer 72

En regardant s’il existe un sous-ensemble Z ⊆ 2^B tel que ^(^(B) ∪ Z) est distributif, ce qui peut être fait en brute force

Question 73

Qu’est-ce que N ⋓ N’ ?

Answer 73

Soient N = (V, C) et N’ = (V’, C’) deux QCN avec le même étiquetage sur V ∩ V’, alors N ⋓ N’ est le réseau construit comme suit
- V’’ = V ∪ V’
- ∀ (u, v) ∈ (V \V’) × (V’ \ V), C’‘(u, v) = C’‘(v, u) = B
- ∀ u, v ∈ V, C’‘(u, v) = C(u, v)
- ∀ u, v ∈ V’, C’‘(u, v) = C’(u, v)

Question 74

Qu’est-ce que la propriété du patchwork ?

Answer 74

Une sous-classe de relations A ⊆ 2^B a la prorpiété du patchwork si et seulement si pour toute paire de réseaux N, N’ ⋄-cohérents et non trivialement incohérents définis sur A et avec le même étiquetage sur V ∩ V’, N ⋓ N’ est satisfiable

Question 75

Qu’est-ce que le graphe de contraintes (ou graphe primal de contraintes) d’un QCN ?

Answer 75

G = (V, E) tel que (u, v) ∈ E si et seulement so C(u, v) != B

Question 76

Lien entre la propriété du patchwork et le graphes de contraintes (énoncé)

Answer 76

Soit A une sous-classe de relations avec la propriété du patchwork et soit N un QCN défini sur A, alors si N est _G^⋄-cohérent et non trivialement incohérent, et que G est un graphe cordal tel que G(N) ⊆ G, alors N est satisfiable

Question 77

Lien entre la propriété du patchwork et le graphes de contraintes (explication)

Answer 77

Lorsqu’on applique la _G^⋄-cohérence sur un graphe cordal G tel que G(N) ⊆ G, on peut considérer les QCN plus petits qui sont tous des cliques et deviennent donc _G^⋄-cohérent , puis appliquer la propriété du patchwork pour les réunir en un seul réseau satisfiable

Question 78

Qu’est-ce qu’un graphe cordal ?

Answer 78

Soit G = (V, E) un graphe, G est cordal si tout cycle de taille supérieure à 3 a une corde, c’est-à-dire une arête connectant deux sommet non-adjacent du cycle

Question 79

Lien entre les graphes cordaux et la décomposition arborescente

Answer 79

Un graphe est cordal si et seulement s’il a une décomposition arborescente (T, {X₁, …, X_n}) où X_i où X_i est une clique de G

Question 80

Exemple de sous-classes avec la propriété du patchwork

Answer 80

Toutes les sous-classes de relations maximales tractables pour les alèbres de points et d’intervalles et pour RCC8 ont la propriété du patchwork

Question 81

Comment fonctionne l’algorithme qui permet de passer de la _G^⋄-cohérence à la satisfiabilité ?

Answer 81

L’idée est de considérer chaque contrainte d’un QCN N et de la séparer en relations r_i appartenant à la sous-classe de relations A sur laquelle les QCN sont tractables, puis à chaque fois qu’une relation r est changée en une de ses sous-relations, vérifier que le changement est valide et continuer, ou alors backtracker si on se rend compte qu’il n’est pas valide

Question 82

Algorithme qui permet de passer de la _G^⋄-cohérence à la satisfiabilité (entrée, sortie, algorithme)

Answer 82

• Entrée : N un QCN, G un graphe, A une sous-classe de relations de 2^B
• Sortie : Null, ou N modifié pour être sur A
• Cohérence(N, G, A) :
  
  • N ← SOTA(N, G)
  • S’il existe u, v tels que C(u, v) = ∅, renvoyer NULL
  • Si pout tou u, v, C(u, v) ⊆ A, renvoyer N
  • Choisir une contrainte C(u, v) !⊆ A
  • Spliter C en r₁, …, r_k ∈ A
  • Pour chaque r_i
    
    • N[u, v] ← r, N[v, u] ← r^-1
    • Résultat ← Cohérence(N, G, A)
    • Si Résultat != NULL, renvoyer Résultat
• renvoyer NULL

Question 83

Quelles sont les heuristiques possibles d’ordre dans les choix de contraintes pour l’algorithme de cohérence ?

Answer 83

• MRV (Minimum Remaining Values)
• LCV