Poole’s Specificity Revised

Claus-Peter Wirth & Frieder Stolzenburg

wirth@logic.at, fstolzenburg@hs-harz.de

FB AI, Hochschule Harz, 38855Wernigerode, Germany

Specificity of Explanations in Logic Programm.

[Poole, 1985]: David L. Poole. On the Comparison of Theories: Preferring the Most Specific Explanation. IJCAI 9, pp. 144–147.

[Simari & Loui, 1992]: Guillermo R. Simari, Ronald P. Loui. A Mathematical Treatment of Defeasible Reasoning and its Implementation. Artificial Intelligence 53, pp. 125–157.

[Stolzenburg &al., 2003]: Frieder Stolzenburg, Alejandro J. García, Charlos I. Chesñevar, Guillermo R. Simari. Computing Generalized Specificity. J. Applied Non-Classical Logics 13, pp. 87–113.

Wirth & Stolzenburg, July 21, 2014 – p.2

Theory �_{Π} / Entailment ⊢

A literal L is an atom A or a negated atom ¬A. Let Π be a set of rules of the form L [ ⇐ L′_{0} ∧ … ∧ L′_{n} ].

The theory �_{Π} is inductively defined to contain all instances of literals from Π, and all literals L for which there is a conjunction C of literals from �_{Π} such that L ⇐ C is an instance of a rule in Π.

For �⊆ �_{Π}, we also write Π ⊢ �.

The negation symbol “¬” provides an interface to the application context, but is not active in this notion of entailment.

Wirth & Stolzenburg, July 21, 2014 – p.3

Specifications will always be given by 3 sets:

Π^{F} of literals — \underline{F}acts of the concrete situation under consideration Π^{G} of rules — \underline{G}eneral rules that hold in all possible worlds Δ of rules — \underline{D}efeasible / \underline{D}efault rules that hold in most situations

The set Π := Π^{F} ∪ Π^{G} is the set of strict rules that — contrary to the defeasible rules — are

considered to be safe and not doubted in the concrete situation. →Blackboard

Wirth & Stolzenburg, July 21, 2014 – p.4

Concrete Specificity Orderings

Non-Transitive Specificity Relations:

≲_{P1} David Poole’s original
≲_{P2} Guillermo R. Simari’s minor correction of ≲_{P1}
≲_{P3} Our minor correction of ≲_{P2}

Corollary 1 ≲_{P3} ⊆ ≲_{P2} ⊆ ≲_{P1}. Transitive Specificity Relations:

≲_{CP1} Compared to ≲_{P3}:

– Reduction from �_{Π∪Δ} to �_{Π}.

– Admission of Π^{F} after completed defeasible argumentations.

≲_{CP2} Minor correction of ≲_{CP1}

Wirth & Stolzenburg, July 21, 2014 – p.5

Example 1 of [Poole, 1985]

¬flies(edna)  flies(edna)  flies(tweety)

bird(edna)

bird(tweety)

\underline{\underline{emu(edna)}} A2

Π^{F} := {bird(tweety), emu(edna)}, Π^{G} := {bird(x) ⇐ emu(x), ¬flies(x) ⇐ emu(x)}, Δ := {flies(x) ← bird(x)}. A_{2} := {flies(edna) ← bird(edna)}. (∅, ¬flies(edna)) <_{P1,P2,P3,CP1,CP2} (A_{2}, flies(edna)).

Wirth & Stolzenburg, July 21, 2014 – p.6

Ex.2 of [Poole,1985]. Pref. of “More Concise”

¬flies(edna)  flies(edna)  flies(tweety)

bird(edna)

bird(tweety)

\underline{\underline{emu(edna)}} A2 A1

Π^{F} := {bird(tweety), emu(edna)}, Π^{G} := {bird(x) ⇐ emu(x)}, Δ := {flies(x) ← bird(x), ¬flies(x) ← emu(x)}. A_{1} := {¬flies(edna) ← emu(edna)}. A_{2} := {flies(edna) ← bird(edna)}. (A_{1}, ¬flies(edna)) <_{P1,P2,P3,CP1,CP2} (A_{2}, flies(edna)).

Wirth & Stolzenburg, July 21, 2014 – p.7

Example 3 of [Poole, 1985] (renamed)

¬flies(edna)  flies(edna)

bird(edna)

\underline{\underline{emu(edna)}} A2 A2 A1

Π^{F} := {emu(edna)}, Π^{G} := ∅ Δ := {flies(x) ← bird(x), ¬flies(x) ← emu(x), bird(x) ← emu(x)}. A_{1} := {¬flies(edna) ← emu(edna)}. A_{2} := {flies(edna) ← bird(edna), bird(edna) ← emu(edna)}. (A_{1}, ¬flies(edna)) ≈_{CP1,CP2} (A_{2}, flies(edna)). (A_{1}, ¬flies(edna)) <_{P1,P2,P3} (A_{2}, flies(edna)).

Wirth & Stolzenburg, July 21, 2014 – p.8

Computing Specificity Relations

(phase 1) Derive the literals that provide the basis for specificity considerations. CP1/2: �_{Π}. P1–3: �_{Π∪Δ}.

(phase 2) On the basis of a subset H of the literals derived in phase 1, the first item A of a given argument (A, L), and the general rules Π^{G},

we derive a further set of literals � : H ∪ A ∪ Π^{G} ⊢ �.

(phase 3) On the basis of �, the literal of the argument is derived: �∪ Π ⊢ {L}. P1–3: phase 3 is empty: �= {L}. CP1/2: It is admitted to use the facts from Π^{F} in phase 3, in addition to the general rules from Π^{G}.

Wirth & Stolzenburg, July 21, 2014 – p.9

Definition [Minimal] [Simplified] Activation Set

Let A be a set of ground instances of rules from Δ, and let L be a literal.

H is a simplified activation set for (A, L) if L ∈ �_{H ∪ A ∪ Π^{G}} .

H is an activation set for (A, L) if L ∈ �_{�∪Π} for some �⊆ �_{H ∪ A ∪ Π^{G}} .

H is a minimal [simplified ] activation set for (A, L) if H is an [simplified] activation set for (A, L), but no proper subset of H is an [simplified] activation set

for (A, L).

Wirth & Stolzenburg, July 21, 2014 – p.10

Definitions of ≲_{CP1} and ≲_{P3}

(A_{1}, L_{1}) ≲_{CP1} (A_{2}, L_{2}) if (A_{1}, L_{1}) and (A_{2}, L_{2}) are arguments, and we have

1. L_{1} ∈ �_{Π} or

2. L_{2} ∉ �_{Π} and every H ⊆ �_{Π} that is an [minimal] activation set for (A_{1}, L_{1}) is also an activation set for (A_{2}, L_{2}).

(A_{1}, L_{1}) ≲_{P3} (A_{2}, L_{2}) if (A_{1}, L_{1}) and (A_{2}, L_{2}) are arguments, L_{2} ∈ �_{Π} implies L_{1} ∈ �_{Π}, and if, for every H ⊆ �_{Π∪Δ} that is a [minimal] simplified activation set for (A_{1}, L_{1}) but not a simplified activation set for (∅, L_{1}), H is also a simplified activation set for (A_{2}, L_{2}).

Example Not Transitive. Pref. of “More Precise”

Propose  Kiss Kiss  Smile
Promising(Jo) \underline{\underline{Bold}}
\underline{\underline{HAkimbo(Jo)}}  \underline{\underline{Smiles(Jo)}}  \underline{\underline{Sexy(Jo)}}

A1

A1

A1

A1

A1

A2

A2

A2

A3

A_{1} := \begin{cases}Promising(Jo) ← HAkimbo(Jo)∧Smiles(Jo)∧Sexy(Jo), \\ Propose & ← & Promising(Jo) & ∧ & Bold \end{cases}\},
A_{2} := {Kiss ← Bold∧Smiles(Jo)∧Sexy(Jo)},
A_{3} := {Smile ← Sexy(Jo)}. Π^{G} := {Kiss ⇐ Promising(G)}.
Π^{F} := {Bold, HAkimbo(Jo), Smiles(Jo), Sexy(Jo)}.

(A_{1}, Propose) <_{P1–3,CP1/2} (A_{2}, Kiss) <_{P1–3,CP1/2} (A_{3}, Smile), but (A_{1}, Propose) <_{CP1/2} (A_{3}, Smile) ≵_{P1–3} (A_{1}, Propose).

Wirth & Stolzenburg, July 21, 2014 – p.12

Conclusion: Novel Specificity Relations are …

Transitive! Monotonic w.r.t. Conjunction! Even More Intuitive! Slightly More Efficient! More Comparing?

Theorem: ≲_{P3} ⊆ ≲_{CP1}. Corollary: △_{CP1} ⊆ △_{P3}. But in general: <_{P3} ⊈ <_{CP1}. Luckily! Otherwise monotonicity w.r.t. ∧ would be lost.

Wirth & Stolzenburg, July 21, 2014 – p.13

[Poole,1985,Example 6]: Monotonicity w.r.t. ∧

g_{1} g_{2}

¬c c f ¬f
b  e
\underline{\underline{a}}  \underline{\underline{d}} A2 A2 A1 A2 A2 A1

(A_{1},¬c)<_{P1–3}(A_{2},c), (A_{1},¬f)<_{P1–3}(A_{2},f), but (A_{1},g_{1})△_{P1–3}(A_{2},g_{2}). (A_{1},¬c)≈_{CP1/2}(A_{2},c), (A_{1},¬f)≈_{CP1/2}(A_{2},f), so (A_{1},g_{1})≈_{CP1/2}(A_{2},g_{2}).

Wirth & Stolzenburg, July 21, 2014 – p.14

1^{st} Variation of [Poole,1985,Example 6]

g_{1} g_{2}

¬c c f ¬f
b  e
\underline{\underline{a}}  \underline{\underline{d}} A2 A1 A2 A2 A1

(A_{1},¬c)<_{P1–3}(A_{2},c), (A_{1},¬f)<_{P1–3}(A_{2},f), but (A_{1},g_{1})△_{P1–3}(A_{2},g_{2}). (A_{1},¬c)<_{CP1/2}(A_{2},c), (A_{1},¬f)≈_{CP1/2}(A_{2},f), so (A_{1},g_{1})<_{CP1/2}(A_{2},g_{2}).

Wirth & Stolzenburg, July 21, 2014 – p.15

“More Precise”

¬lovely  lovely
grandpa  grandma
\underline{\underline{noisy}}  \underline{\underline{somebody}}

A1 A1

A2

(A_{1},¬lovely) <_{P1–3} (A_{2},lovely). (A_{1},¬lovely)<_{CP1/2}(A_{2},lovely).

“More Precise”, 2^{nd} Var. of [Poole,1985,Ex. 6]

g_{1} g_{2}

¬c c f
b  e
\underline{\underline{a}}  \underline{\underline{d}} A2 A2 A1 A2 A2

(A_{1},¬c)<_{P1–3}(A_{2},c), but (A_{1},g_{1})△_{P1–3}(A_{2},g_{2}). (A_{1},¬c)≈_{CP1/2}(A_{2},c), but (A_{1},g_{1})>_{CP1/2}(A_{2},g_{2}), “more precise”.

Wirth & Stolzenburg, July 21, 2014 – p.17

“Precise vs. Concise”, 3^{rd}Var.[Poole,1985,Ex. 6]

g_{1} g_{2} ¬c  c  f b  e \underline{\underline{a}}  \underline{\underline{d}} A_{2} A_{1} A_{2} A_{2} (A_{1}, g_{1}) △_{P1−3,CP1/2} (A_{2}, g_{2}).

The conflict between a being “more concise” than b and b∧d being “more precise” than a is indeed irresolvable.

Wirth & Stolzenburg, July 21, 2014 – p.18

[Stolzenbg, 2003, Ex.11]: No Pruning for ≲_{P3}!

x  x
¬x
a  b  f
\underline{\underline{d}}  \underline{\underline{c}}  \underline{\underline{e}} A1 A1 A1 A2 A2 A3 A4 A5

Π^{F} := {c, d, e}, Π^{G} := {x ⇐ a∧f}, Δ := A^{1} ∪ A^{2} ∪ A^{3} ∪ A^{4} ∪ A^{5}.

A^{1} := {x ← a∧b∧c}. A^{2} := {¬x ← a∧b}. A^{3} := {f ← e}. A^{4} := {a ← d}. A^{5} := {b ← e}.

(A^{1}∪A^{4}∪A^{5}, x) <_{CP1/2} (A^{2}∪A^{4}∪A^{5}, ¬x) ≈_{CP1/2} (A^{3}∪A^{4}, x). All ≲_{P1−3}-incomparable! For (A^{1}∪A^{4}∪A^{5}, x) ≴_{P3} (A^{2}∪A^{4}∪A^{5}, ¬x) we have to consider (implicitly via {d, f} ⊆ �_{Π∪Δ}) the defeasible rule of A^{3}, which is not part of any of the two arguments under comparison. No pruning possible for ≲_{P1−3} .

Wirth & Stolzenburg, July 21, 2014 – p.19

Variation of [Stolzenbg, 2003, Ex.11]

x  x
¬x
a  b  f
\underline{\underline{d}}  \underline{\underline{c}}  \underline{\underline{e}} A1 A1 A1 A2 A2 A4 A5

Π^{F} := {c, d, e},

Π^{G} := {x ⇐ a∧f, f ⇐ e}, Δ := A^{1} ∪ A^{2} ∪ A^{4} ∪ A^{5}. A^{1} := {x ← a∧b∧c}. A^{2} := {¬x ← a∧b}. A^{4} := {a ← d}. A^{5} := {b ← e}.

(A^{4}, x) ≈_{CP1/2} (A^{1}∪A^{4}∪A^{5}, x) >_{CP1/2} (A^{2}∪A^{4}∪A^{5}, ¬x). Makes sense because d∧e is more precise (specific) than d. c∧d∧e is irrelevant because approach is model-theoretic. (A^{4}, x) <_{P1−3} (A^{1}∪A^{4}∪A^{5}, x) △_{P1−3} (A^{2}∪A^{4}∪A^{5}, ¬x) △_{P1−3} (Bullshit!) (A^{4}, x).

Wirth & Stolzenburg, July 21, 2014 – p.20

[Stolzenburg, 2003, Ex. p.95]: Global Effect!

¬p(a)  p(a)

s(a)

\underline{\underline{q(a)}} A1 A1 A2

Π^{F} := {q(a)}, Π^{G} := {s(x) ⇐ q(x)},

Δ := {p(x) ← q(x), ¬p(x) ← q(x)∧s(x)}.

A_{1} := {¬p(a) ← q(a)∧s(a)}.

A_{2} := {p(a) ← q(a)}.

(A_{1}, ¬p(a)) ≈_{P1−3,CP1/2} (A_{2}, p(a)).

≲_{CP1} vs. ≲_{CP2}

drink alarm alarm

\underline{\underline{danger}}

\underline{\underline{thirst}} A1 A2 A3 A3

Π^{F} := {thirst, danger}, Π^{G} := ∅, Δ := A_{1} ∪ A_{3}, A_{1} := {drink ← thirst}, A_{2} := {alarm ← danger}. A_{3} := A_{2} ∪ {danger ← thirst}.

(A_{2}, alarm) <_{CP1} (A_{3}, alarm) ≈_{CP2} (A_{2}, alarm) (A_{1}, drink) <_{CP1} (A_{3}, alarm) △_{CP2} (A_{1}, drink) (A_{1}, drink) △_{CP1} (A_{2}, alarm) △_{CP2} (A_{1}, drink)

Example Not Transitive. Pref. of “More Precise”

beer  wine  wine  vodka

e

\underline{\underline{thirst}}  \underline{\underline{blessing}}  \underline{\underline{alcohol}}

A1

A1

A1

A1

A2

A2

A3

A_{1} := {e ← alcohol∧blessing∧thirst, beer ← e}, A_{2} := {wine ← alcohol∧blessing}, A_{3} := {vodka ← alcohol}, Δ := A_{1} ∪ A_{2} ∪ A_{3}, Π^{F} := {alcohol, blessing, thirst}, Π^{G} := {wine ⇐ e}, (A_{1}, beer) <_{P1–3,CP1/2} (A_{2}, wine) <_{P1–3,CP1/2} (A_{3}, vodka), but (A_{1}, beer) <_{CP1/2} (A_{3}, vodka) ≵_{P1–3} (A_{1}, beer).

Wirth & Stolzenburg, July 21, 2014 – p.23

All you need is Quasi-Ordering

A quasi-ordering is a reflexive transitive relation. An (irreflexive) ordering is an irreflexive transitive relation. A reflexive ordering (also called: “partial ordering”) is an anti-symmetric quasi-ordering. An equivalence is a symmetric quasi-ordering.

We will use several binary relations ≲_{N} comparing arguments according to their specificity.

Corollary 2 If ≲_{N} is a quasi-ordering, then its equivalence ≈_{N} is an equivalence, its ordering <_{N} is an ordering, and its reflexive ordering ≤_{N} is a reflexive ordering.

Wirth & Stolzenburg, July 21, 2014 – p.24

Abstract Specificity Orderings

For any relation written as ≲_{N}

(“being more or equivalently specific w.r.t. N”),

we define:

≳_{N} := { (X, Y) | Y ≲_{N} X }(“less or equivalently specific”),
≈_{N} := ≲_{N} ∩ ≳_{N}  (“equivalently specific”),
<_{N} := ≲_{N} \ ≳_{N}  (“properly more specific”),
≤_{N} := <_{N} ∪ { (X, X) | X is an argument }

(“more specific or equal”),

△_{N} := { (X, Y) X, Y are arguments with X ≴_{N} Y and X ≵_{N} Y }

(“incomparable w.r.t. specificity”).

Wirth & Stolzenburg, July 21, 2014 – p.25

Efficiency Considerations

Let H be a set of hypotheses. Then, roughly speaking, (A_{1}, L_{1}) ≲ (A_{2}, L_{2}) if every activation set H for (A_{1}, L_{1}) is also one for (A_{2}, L_{2}). Naïve procedure enumerates possible activation sets, which is exponential in the number of possible hypothesis literals. Clearly, the effort for computing ≲_{CP1} is lower than that of ≲_{P3} because of �_{Π} ⊆ �_{Π∪Δ}. While checking ≲_{Px}, attention cannot be restricted to derivations which make use only of defeasible rules given in the arguments. Therefore, [Stolzenburg&al, 2003] introduce pruning derivation trees.

Path Characterization for Specificity

(A_{1}, L_{1}) ≤ (A_{2}, L_{2}) if (A_{1}, L_{1}) and (A_{2}, L_{2}) are two arguments in the given specification and for each derivation tree T_{1} for L_{1} there is a derivation tree T_{2} for L_{2} such that T_{1} ⊴ T_{2}. Let T_{1} and T_{2} be derivation trees. Then, T_{1} ⊴ T_{2} if for each t_{2} ∈ Paths(T_{2}) there is a path t_{1} ∈ Paths(T_{1}) such that t_{1} ⊆ t_{2} (omitting the root nodes). If the arguments involved in the comparison correspond to exactly one and-tree, then ≲_{P2} coincides with the path characterization (≤ and ⊴). Cf. Example 1 of [Poole, 1985]. Two and-trees can be compared efficiently w.r.t. ⊴. It requires pairwise comparison of all nodes in the trees for each path. Hence, the respective complexity is polynomial in the size of the derivation trees.

Wirth & Stolzenburg, July 21, 2014 – p.27

Path vs. Argument Characterization

¬lovely  lovely
grandpa  grandpa
\underline{\underline{noisy}}  \underline{\underline{somebody}}

A1

A1

A2

Poole’s specificity: (A_{1},¬lovely) <_{P1–3} (A_{2},lovely) Corrected version: (A_{1},¬lovely)<_{CP1/2}(A_{2},lovely) Path characterization: (A_{1},¬lovely) ≤ (A_{2},lovely)

{{noisy, grandpa}, {someb., grandpa}} {{someb., grandpa}}

Argument sets: (A_{1},¬lovely) ⊑ (A_{2},lovely)

{{noisy, somebody}, {grandpa}} {{somebody}, {grandpa}}

Wirth & Stolzenburg, July 21, 2014 – p.28

Back to the Arguments

Characterization dual to ⊴ based on the rules in the arguments: Let (A_{1}, L_{1}) and (A_{2}, L_{2}) be two arguments and R_{i} (i = 1, 2) be the set of (strict and defeasible) rule bodies used in the respective proofs. We define: R_{1} ⊑ R_{2} if for all r_{1} ∈ R_{1} there exists an r_{2} ∈ R_{2} such that r_{2} ⊆ r_{1}. Simplified version: Interpret ⊑ simply as subset (w.r.t. complete rule sets). This is close to the notion more conservative than [Besnard&Hunter, 2001]: A_{1} ⊆ A_{2} and L_{2} entails L_{1}. Checking ⊆ on ground literal sets can be done efficiently (NP-complete for general literals).

Wirth & Stolzenburg, July 21, 2014 – p.29

Further Conclusions

Computing ≲_{CPx} can be done by a modified SLD-resolution procedure, but has to enumerate all possible derivations for each query. Path (⊴) and argument (⊑) characterizations can be computed efficiently. However, they coincide with specificity notion only in special cases (e.g. no strict rules). Further investigation is required … Thank you very much for your attention!