CMS Flashcards
À quoi servent les modèles de raisonnement qualitatifs spatiaux-temporels ?
À 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)
Que signifie QSTR ?
Qualitative Spatial and Temporal Reasoning
Relations de base de RCC8
- DC : disconnected
- EC : externally connected
- PO : partially overlaps
- EQ : equals
- TPP : tangential proper part
- NTPP : non-tangential propre part
Relations de base de l’algèbre des intervalles
- p : precedes
- m : meets
- o : overlaps
- s : starts
- d : during
- f : finishes
- eq : equals
Que signifie QCL ?
Qualitative Constraint Language
Définition d’un QCL
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
- 2B</sub> est équipé de l’union, l’intersection, l’inverse et la composition faible
Que signifie JEPD ?
Jointly Exhaustive & Pairwise Disjoint
Quelles sont les propriété du domain des relations de bases d’un QCL ?
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
Qu’est-ce qu’un ensemble de relations de base jointly exhaustive ? (formule)
Une ensemble de relations de base B tel que ⋃{b ∈ B} = D × D × … × D
Qu’est-ce qu’un ensemble de relations de base pariwise disjoint ? (formule)
Une ensemble de relations de base B tel que ∀ b, b’ ∈ B, b != b’ ⇒ b ∩ b’ = ∅
Qu’est-ce qu’un ensemble de relations de base qui vérifie la propriété JEPD ? (langage naturel)
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
Qu’est-ce qui est exprimé par l’ensemble des relations de base d’un ensemble B ?
Une connaissance définie entre un certain nombre d’entités (arité des relations)
Qu’est-ce qui est exprimé par un sous-ensemble de relations de base d’un ensemble B ?
{b1, …, bj} avec j < |B| correspond à b1 ∪ … ∪ bj, qui représente une certaine connaissance indéfinie
Soit B un ensemble de relations de base, qu’est-ce que 2B ?
L’ensemble des sous-ensembles de relations possibles, donc la connaissance définie et indéfinie entre les entités
Qu’est-ce qu’un tuple qui satisfait une relation de base b ?
(x1, …, xϵ) ∈ Dϵ tel que (x1, …, xϵ) ∈ b
Qu’est-ce qu’un tuple qui satisfait un sous-ensemble de relations de base r ∈ 2B ?
(x1, …, xϵ) ∈ Dϵ tel que ∃ b ∈ r, (x1, …, xϵ) ∈ b
Relations de base de l’algèbre des points
- < : precedes
- = : equals
- > : follows
Domaine de RCC8
L’ensemble Treg des sous-ensembles réguliers non-vides et fermés d’un espace topologique T
Domaine de l’algèbre d’intervalle
{ x = (x-, x+) ∈ {Q}2 | x- < x+}
Domaine de l’algèbre de points
{Q}
Inverse d’une relation de base b
b-1 = {(y, x) | (x, y) ∈ b}
Inverse d’un sous-ensemble r de l’ensemble des relations de base B
r-1 = {b-1 | b ∈ r}
Composition de deux relations de base b et b’
b ∘ b’ = {(x, z) ∈ D2 | ∃ y ∈ D, (x, y) ∈ b ∧ (y, z) ∈ b’}
Composition de deux sous-ensembles r et r’ de l’ensemble des relations de base B
r ∘ r’ = ⋃{b ∘ b’ | b ∈ r, b’ ∈ r’}
Composition faible de deux relations de base b et b’
b ⋄ b’ = {b’’ ∈ B | b’’ ∩ (b ∘ b’) != ∅}
Composition faible de deux sous-ensembles r et r’ de l’ensemble des relations de base B
r ⋄ r’ = ⋃{b ⋄ b’ | b ∈ r, b’ ∈ r’}
Principe de la composition faible de deux relations de base
Plus petite relation r ∈ 2B qui contient b ∘ b’
Axiomes d’une relation algébrique au sens de Tarski
- 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
Clôtures de 2B
2B est clos par composition faible, union, intersection et inversion
Définition d’un sous-classe de relations
Une sous-classe de relations est une partie A ⊆ 2B qui contient les relations-singletons de 2B et de B, et qui clos sous inversion, intersection et composition faible
Que signifie QCN ?
Qualitative Constraint Network
Définition d’un QCN
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 V2 dans 2B, qui associe un sou-ensemble de relations de base à chaque paire de variables de V
Propriétés des contraintes C de QCN
Elles sont binaires et normalisées : ∀ v, v’ ∈ V, C(v, v’) = (C(v’, v))-1
Comment s’assurer de l’application de la condition de normalisation dans un QCN ?
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)
Qu’est-ce qu’un QCN trivialement incohérent ?
N = (V, C) est trivialement incohérent si et seulement si ∃ v, v’ ∈ V, C(v, v’) = ∅
Qu’est-ce qu’une solution pour une QCN ?
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
Qu’est-ce qu’un QCN satisfiable (ou cohérent) ?
N = (V, C) est cohérent (ou satisfiable) si et seulement si il admet une solution
Qu’est-ce qu’un sous-QCN ?
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)
Qu’est-ce qu’un scenario d’un QCN ?
Un scénario d’un QCN N = (V, C) est un sous-QCN S ⊆ N cohérent et atomique
Qu’est-ce qu’un QCN atomique ?
N = (V, C) est atomique si et seulement si ∀ v, v’ ∈ V, |C(v, v’)| = 1
Complexité du problème de satisfiabilité d’un QCN sur la plupart des langages
NP-complet
Complexité du problème de satisfiabilité d’un QCN sur l’algèbre des points
P-TIME
Complexité du problème de satisfiabilité d’un QCN sur l’algèbre des intervalles (schéma de preuve)
- 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”
Qu’est-ce que le problème d’étiquetage minimal ?
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
Complexité du problème d’étiquetage minimal
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é
Qu’est-ce que le problème de redondance ?
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
Complexité du problème de redondance
Le problème de redondance peut être réduit au problème de satisfiabilité d’un QCN, il a donc la même complexité
Qu’est-ce qu’un réseau G⋄-cohérent ?
Soit N = (V, C) un QCN et G = (V, E) un graphe, N est G⋄-cohérent si et seulement si ∀ {vi, vj}, {vj, vk}, {vi, vk} ∈ E, C(vi, vj) ⊆ C(vi, vk) ⋄ C(vk, vj), c’est-à-dire si tous les triplets de variables qui correspondent à des triangles dans G sont clos par composition faible
Qu’est-ce qu’un réseau ⋄-cohérent ?
Un réseau G⋄-cohérent pour lequel G est complet
Propriété des réseaux atomiques ⋄-cohérents
Pour les algèbres de points et d’intervalle et pour RCC8, tout réseau atomique ⋄-cohérent est satisfiable
Complexité de vérifier si un réseau est G⋄-cohérent
On doit visiter tous les triangles de G : O(O(|V|3) si G est complet et O(∆ · |E|) sinon
Qu’est-ce que la procédure de clôture algébrique ?
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 :
∀ {vi, vj}, {vj, vk}, {vi, vk} ∈ E, C(vi, vj) ← C(vi, vj) ∩ (C(vi, vk) ⋄ C(vk, vj))
Algorithme naïf de clôture algébrique
- Pour tout triplet {vi, vj}, {vj, vk}, {vi, vk} de E, appliquer C(vi, vj) ← C(vi, vj) ∩ (C(vi, vk) ⋄ C(vk, vj))
- Si une contrainte C(vi, vj) a été modifiée, répéter l’étape précédente
Complexité temporelle et spatiale de l’algorithme naïf de clôture algébrique
- Temporelle : On refait l’étape de tous les triplets au plus pour O(|E|) contraintes, O(|B|) fois, donc au total : O(∆ × |E|2 × |B|)
- Spatiale : O(1)
Algorithme SOTA de clôture algébrique (PWC)
- Pour tout triplet {vi, vj}, {vj, vk}, {vi, vk} de E, appliquer C(vi, vj) ← C(vi, vj) ∩ (C(vi, vk) ⋄ C(vk, vj))
- Si une contrainte C(vi, vj) 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(vi, vj), qui sont au plus Δ
Complexité de l’algorithme SOTA de clôture algébrique
- 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|)
Qu’est-ce que G⋄(N) ?
La clôture algébrique de N
Correction de la G⋄-cohérence
Soit N = (V, C) un QCN et G = (V, E) un graphe, si ∅ ∈ G⋄(N), alors N est insatisfiable
Complétude de la G⋄-cohérence
La clôture algébrique n’est pas complète
Propriétés de G⋄(N) vis-à-vis de N
- 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)
Lien entre la tractabilité des QCN et des sous-classes de relations
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
Comment vérifier qu’un QCN sur l’algèbre des intevalles est tractable en utilisant la Horn-satisfiabilité ?
- 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
Lien entre la ⋄-cohérence des QCN et les sous-classes de relations
Tout QCN défini à partir d’une sous-classe de relations tractable peut être réécrit en un QCN ⋄-cohérent atomique
Qu’est-ce qu’une sous-classe de relations maximale ?
Une sous-classe de relations A qui n’est contenue dans aucune autre
Qu’est-ce qu’une sous-classe de relations distributive ?
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)
Qu’est-ce qu’un sous-ensemble de relations convexe ?
r = {r1, …, n} ⊆ 2B est un sous-ensemble de relations convexe si ∀ ri, rj ∈ r, ∀ x1, x2, (x1 < r < x2, x1 r1 y et x2 r2 y) ⇒ x {r1, r2} y
Relation entre la convexité et la distributivité
Les sous-classes de relations distributives sont convexes au sens de Helly
Qu’est-ce qu’une sous-classe de relations qui a la propriété d’Helly ?
Une sous-classe de relations A a la propriété d’Helly si et seulement si pour tout sous-ensembles de n relations {r1, …, rn}, ⋂i=1..n ri != ∅ si et seulement si ∀ i, j ∈ {1, …, n}, ri ∩ rj != ∅
Lien entre la distributivité et la propriété d’Helly
Une sous-classe de relations est distributive si et seulement si elle a la propriété d’Helly
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) ?
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)
Lien entre la distributivité et la tractabilité
Les sous-classes de relations distributives sont tractables
Comment identifier une sous-classe de relations distributive maximale ?
En regardant s’il existe un sous-ensemble Z ⊆ 2B tel que ^(^(B) ∪ Z) est distributif, ce qui peut être fait en brute force
Qu’est-ce que N ⋓ N’ ?
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)
Qu’est-ce que la propriété du patchwork ?
Une sous-classe de relations A ⊆ 2B 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
Qu’est-ce que le graphe de contraintes (ou graphe primal de contraintes) d’un QCN ?
G = (V, E) tel que (u, v) ∈ E si et seulement so C(u, v) != B
Lien entre la propriété du patchwork et le graphes de contraintes (énoncé)
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
Lien entre la propriété du patchwork et le graphes de contraintes (explication)
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
Qu’est-ce qu’un graphe cordal ?
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
Lien entre les graphes cordaux et la décomposition arborescente
Un graphe est cordal si et seulement s’il a une décomposition arborescente (T, {X1, …, Xn}) où Xi où Xi est une clique de G
Exemple de sous-classes avec la propriété du patchwork
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
Comment fonctionne l’algorithme qui permet de passer de la G⋄-cohérence à la satisfiabilité ?
L’idée est de considérer chaque contrainte d’un QCN N et de la séparer en relations ri 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
Algorithme qui permet de passer de la G⋄-cohérence à la satisfiabilité (entrée, sortie, algorithme)
- Entrée : N un QCN, G un graphe, A une sous-classe de relations de 2B
- 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 r1, …, rk ∈ A
- Pour chaque ri
- 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
Quelles sont les heuristiques possibles d’ordre dans les choix de contraintes pour l’algorithme de cohérence ?
- MRV (Minimum Remaining Values)
- LCV
