Inférence en logique du premier ordre Chap. 9. Plan Réduire linférence de la logique du premier...

Inférence en logique du premier ordre

Chap. 9

Plan

• Réduire l’inférence de la logique du premier ordre en celle de la logique propositionnelle

• Unification• Modus Ponens généralisé• Chaînage avant et arrière• Résolution

Instanciation universelle (UI)

• Chaque instanciation d’une phrase universellement quantifiée est entraînée par cette dernière:

v αSubst({v/g}, α)

pour toute variable v et tout terme instancié (grounded) g

• E.g., x King(x) Greedy(x) Evil(x) peut entraîner:

King(John) Greedy(John) Evil(John)

King(Richard) Greedy(Richard) Evil(Richard)

King(Father(John)) Greedy(Father(John)) Evil(Father(John))

Instanciation existentielle (EI)• Pour toute phrase α et variable v, et un symbole

de constante k qui n’apparaît pas dans la base de connaissances:

v αSubst({v/k}, α)

• E.g., x Crown(x) OnHead(x,John) entraîne:

Crown(C1) OnHead(C1,John)

en supposant que C1 est un nouveau symbole de constante jamais utilisé dans la base de connaissances.

Cette constante est appelée constante Skolem

Réduction en inférence propositionnelle

Supposons que la KB contient les phrases suivantes:

x King(x) Greedy(x) Evil(x)King(John)Greedy(John)Brother(Richard,John)

• Instancier la phrase universelle de toutes les façns possibles:King(John) Greedy(John) Evil(John)King(Richard) Greedy(Richard) Evil(Richard)King(John)Greedy(John)Brother(Richard,John)

La nouvelle KB est propositionnalisée: les symboles de propositions sont:•• King(John), Greedy(John), Evil(John), King(Richard), etc.

Réduction contd.

• Chaque base de connaissances en LPO peut être propositionnalisée pour préserver l’entraînement

• (Une phrase instanciée est entraînée par la nouvelle KB ssi elle est entraînée par la KB originale)

• Idée: propositionnaliser KB et requête, appliquer la résolution, et retourner le résultat

• Problème: avec le symbole de fonction, il y a un nombre infini de termes instanciés:

• e.g., Father(Father(Father(John)))–

Réduction contd.

Théorème: Herbrand (1930). Si une phrase α est entraînée par une KB en LPO, alors elle est aussi entraînée par un sous-ensemble de KB propositionnalisée

Idée: Pour n = 0 à ∞ do créer la KB propositionnalisée en instanciant les termes à la profondeur n vérifier si α est entraînée par cette KB

Problème: fonctionne si α est entraînée. Mais boucle infini sinon.

Théorème: Turing (1936), Church (1936) L’entraînement en LPO est semidécidable (des algorithmes existent pour répondre “oui” à toute

phrase entraînée, mais il n’y a pas d’algorithme pour répondre “non” à toute phrase non-entraînée)

Problèmes avec la propositionnalisation

• La propositionnalisation peut générer beaucoup de phrases non pertinentes.

E.g., à partir de:•

x King(x) Greedy(x) Evil(x)King(John)y Greedy(y)Brother(Richard,John)

• Il semble évident que Evil(John), mais la propositionnalisation produit beaucoup de faits tels que Greedy(Richard) qui n’est pas pertinente

Avec un nombre p de prédicats à k arguments et n constantes, il y a p·nk instanciations.•

Unification• On peut obtenir l’inférence immédiatement si on peut trouver une

substitution θ telle que King(x) et Greedy(x) match King(John) et Greedy(y)

θ = {x/John,y/John} fonctionne pour ça

• Unify(α,β) = θ si αθ = βθ

p q θ

Knows(John,x) Knows(John,Jane)

Knows(John,x) Knows(y,OJ)

Knows(John,x) Knows(y,Mother(y))

Knows(John,x) Knows(x,OJ)

Standardizing apart élimine la confusion des variables, e.g., Knows(z17,OJ)

•

Unification• On peut obtenir l’inférence immédiatement si on peut trouver une

substitution θ telle que King(x) et Greedy(x) match King(John) et Greedy(y)

θ = {x/John,y/John} fonctionne pour ça

• Unify(α,β) = θ si αθ = βθ

p q θ

Knows(John,x) Knows(John,Jane) {x/Jane}}

Knows(John,x) Knows(y,OJ)

Knows(John,x) Knows(y,Mother(y))

Knows(John,x) Knows(x,OJ)

Standardizing apart élimine la confusion des variables, e.g., Knows(z17,OJ)

•

Unification• On peut obtenir l’inférence immédiatement si on peut trouver une

substitution θ telle que King(x) et Greedy(x) match King(John) et Greedy(y)

θ = {x/John,y/John} fonctionne pour ça

• Unify(α,β) = θ si αθ = βθ

p q θ

Knows(John,x) Knows(John,Jane) {x/Jane}}

Knows(John,x) Knows(y,OJ) {x/OJ,y/John}}

Knows(John,x) Knows(y,Mother(y))

Knows(John,x) Knows(x,OJ)

Standardizing apart élimine la confusion des variables, e.g., Knows(z17,OJ)

•

Unification• On peut obtenir l’inférence immédiatement si on peut trouver une

substitution θ telle que King(x) et Greedy(x) match King(John) et Greedy(y)

θ = {x/John,y/John} fonctionne pour ça

• Unify(α,β) = θ si αθ = βθ

p q θ

Knows(John,x) Knows(John,Jane) {x/Jane}}

Knows(John,x) Knows(y,OJ) {x/OJ,y/John}}

Knows(John,x) Knows(y,Mother(y)) {y/John,x/Mother(John)}}

Knows(John,x) Knows(x,OJ)

Standardizing apart élimine la confusion des variables, e.g., Knows(z17,OJ)

•

Unification• On peut obtenir l’inférence immédiatement si on peut trouver une

substitution θ telle que King(x) et Greedy(x) match King(John) et Greedy(y)

θ = {x/John,y/John} fonctionne pour ça

• Unify(α,β) = θ si αθ = βθ

p q θ

Knows(John,x) Knows(John,Jane) {x/Jane}}

Knows(John,x) Knows(y,OJ) {x/OJ,y/John}}

Knows(John,x) Knows(y,Mother(y)) {y/John,x/Mother(John)}}

Knows(John,x) Knows(x,OJ) {fail}

Standardizing apart élimine la confusion des variables, e.g., Knows(z17,OJ)

•

Unification

• Pour unifier Knows(John,x) et Knows(y,z),θ = {y/John, x/z } ou θ = {y/John, x/John, z/John}

• La première est plus générale que la seconde.

Il y a une seule unification la plus générale (most general unifier - MGU) qui est unique, excepté la rénomination des variables•• MGU = { y/John, x/z }

Algorithme d’unification

Algorithme d’unification

Modus Ponens généralisé (GMP)p1', p2', … , pn', ( p1 p2 … pn q) qθ

p1' est King(John) p1 est King(x) θ1={x/John}

p2' est Greedy(y) p2 est Greedy(x) θ2={x/y} ou θ={y/x}

θ est {x/John,y/Johnq est Evil(x) q θ est Evil(John)

• GMP utilisé avec KB de clauses définies (definite clauses) (exactement un littéral positif)– ( p1 p2 … pn q)– (p1 p2 … pn q)

• Toute variable est supposée être avec quantificateur universel

••

où pi'θ = pi θ pour tout i

Adéquation de GMP• On a besoin de prouver • p1', …, pn', (p1 … pn q) ╞ qθ

en supposant que pi'θ = piθ pour tout i

• Lemma: Pour une phrase quelconque p, nous avons p ╞ pθ par UI (instanciation universelle)

(p1 … pn q) ╞ (p1 … pn q)θ = (p1θ … pnθ qθ)1.2. p1', …, pn' ╞ p1' … pn' ╞ p1'θ … pn'θ 3. De 1 et 2, qθ suit en utilisant Modus Ponens ordinaire4.

Exemple de base de connaissances

The law says that it is a crime for an American to sell weapons to hostile nations. The country Nono, an enemy of America, has some missiles, and all of its missiles were sold to it by Colonel West, who is American.• (La loi dit que c’est un crime pour un américain de

vendre des armes aux pays hostiles. Le pays Nono, un ennemie de l’Amérique, a des missiles, et tous ses missiles étaient vendus par Colonel West, qui est un américain.)

Prove that Col. West is a criminal•

Exemple de base de connaissances

... it is a crime for an American to sell weapons to hostile nations:American(x) Weapon(y) Sells(x,y,z) Hostile(z) Criminal(x)

Nono … has some missiles, i.e., x Owns(Nono,x) Missile(x):Owns(Nono,M1) and Missile(M1)

… all of its missiles were sold to it by Colonel WestMissile(x) Owns(Nono,x) Sells(West,x,Nono)

Missiles are weapons:Missile(x) Weapon(x)

An enemy of America counts as "hostile“:Enemy(x,America) Hostile(x)

West, who is American …American(West)

The country Nono, an enemy of America …Enemy(Nono,America)

Chaînage avant

Chaînage avant

Chaînage avant

Chaînage avant

Propriétés du chaînage avant

• Adéquat et complet pour les clauses définies du premier ordre

• Datalog = clauses définies du premier ordre + sans fonctions

• Ch. avant termine pour Datalog en un nombre fini d’itérations

• Peut ne pas terminer en général si α n’et pas entraîné

Ceci est inévitable: l’entraînement avec les clauses définies est semidécidable•

Efficacité du chaînage avant

Chaînage avant incrémental: pas besoin de matcher une règle à l’itération k si une prémise n’était pas ajoutée à l’itération k-1Þ Matcher chaque règle don’t la prémise contient un ittéral positif

nouvellement ajouté

Matching peut être coûteux:Indexation de base de données (Database indexing)

permet O(1) pour retrouver des faits connus

– e.g., requête Missile(x) retrouve Missile(M1)

Ch. avant est largement utilisé dans les bases de données déductives

Exemple de match difficile

• Colorable() est inféré ssi CSP a une solution• CSPs contiennent 3SAT comme cas spécial,

donc matching est NP-difficile•

Diff(wa,nt) Diff(wa,sa) Diff(nt,q) Diff(nt,sa) Diff(q,nsw) Diff(q,sa) Diff(nsw,v) Diff(nsw,sa) Diff(v,sa) Colorable()

Diff(Red,Blue) Diff (Red,Green) Diff(Green,Red) Diff(Green,Blue) Diff(Blue,Red) Diff(Blue,Green)

Chaînage arrière

SUBST(COMPOSE(θ1, θ2), p) = SUBST(θ2, SUBST(θ1, p))

Chaînage arrière: Exemple

Chaînage arrière: Exemple

Chaînage arrière: Exemple

Chaînage arrière: Exemple

Chaînage arrière: Exemple

Chaînage arrière: Exemple

Chaînage arrière: Exemple

Chaînage arrière: Exemple

Propriétés du chaînage arrière

• Preuve en recherche en profondeur récursive: espace de taille linéaire

• Incomplet à cause de boucles infinis possiblesÞ Fixer le problème en examinant le but courant avec

tout le stack de buts

• Inefficace dû aux sous-buts répétés (réussis ou échoués) Fixer le prob. en utilisant le cashe (espace additionnel)

• Largement utilisé en programmation logique (Prolog)

Programmation logique: Prolog• Algorithme = Logique + Contrôle

• Base: chaînage arrière avec clauses Horn + certains gadgetsRépandu en Europe, Japon (base du projet de 5ième génération)Technique de compilation 60 million LIPS

• Programme = ensemble de clauses = head :- literal1, … literaln.• criminal(X) :- american(X), weapon(Y), sells(X,Y,Z),

hostile(Z).

• Recherche en profondeur, de gauche à droite, chaînage arrière• Prédicats prédéfinis (Built-in) pour des opérations arithmétiques. etc., e.g., X

is Y*Z+3• Prédicats prédéfinis pour entrée-sortie, assertion/retract, …• Hypothèse du monde clos (Closed-world assumption) ("negation as failure")

– e.g., avec alive(X) :- not dead(X).– alive(joe) réussi si dead(joe) échoue–

Prolog• Concaténer 2 listes pour produire la 3ième:

append([],Y,Y). append([X|L],Y,[X|Z]) :- append(L,Y,Z).

• Équivalent en logique: append([],Y,X)append(L,Y,Z) append([X|L],Y,[X|Z])

• requête: append(A,B,[1,2]) ?

• réponse: A=[] B=[1,2] A=[1] B=[2] A=[1,2] B=[]

Règle de Résolution• Version complète du premier ordre:• l1 ··· lk, m1 ··· mn

(l1 ··· li-1 li+1 ··· lk m1 ··· mj-1 mj+1 ··· mn)θ

avec Unify(li, mj) = θ.

• Exemple Rich(x) Unhappy(x) Rich(Ken)

Unhappy(Ken)avec θ = {x/Ken}

Appliquer la résolution sur CNF(KB α); complet pour LPO•

Factoring

• Une application binaire de la règle de résolution– Combiner 2 clauses chaque fois– Non complète seule

• Ajouter le factoring– Si 2 éléments dans la clause sont unifiables,

alors réduire la clause en unifiant les éléments

– Application binaire + factoring = complet

Uitliser la preuve de résolution par contradiction

1. Convertir la KB en clauses (CNF)

2. Convertir la négation de la conclusion en clause

3. Appliquer la règle de résolution

4. Si on produit une clause vide (contradiction), alros la conclusion est prouvée

Conversion en CNF

• Everyone who loves all animals is loved by someone:x [y Animal(y) Loves(x,y)] [y Loves(y,x)]

• 1. Éliminner biconditionnels et implications• x [y Animal(y) Loves(x,y)] [y Loves(y,x)]

• 2. bouger vers l’intérieur (x p ≡ x p, x p ≡ x p)

x [y (Animal(y) Loves(x,y))] [y Loves(y,x)] x [y Animal(y) Loves(x,y)] [y Loves(y,x)] x [y Animal(y) Loves(x,y)] [y Loves(y,x)]

Conversion en CNF contd.3. Standardiser les variables: chaque quantificateur

utilise une variable différentex [y Animal(y) Loves(x,y)] [z Loves(z,x)]

4. Skolemiser:Chaque variable existancielle est remplacé par une Fonction

Skolem des variables universelles reliées: x [Animal(F(x)) Loves(x,F(x))] Loves(G(x),x)

5. Enlever les quantificateurs universels [Animal(F(x)) Loves(x,F(x))] Loves(G(x),x)

6. Distribuer sur :7. [Animal(F(x)) Loves(G(x),x)] [Loves(x,F(x)) Loves(G(x),x)]

Preuve avec la résolution par contradiction

Sommaire

• Généralisation des procédures d’inférence: Logique propositionnelle LPO

• Unification pour traiter des variables• Règle de résolution (avec contradiction)• Adéquat et complet pour LPO• Prolog