Tuesday, 13 February 2007

7, DeLP an Argumentative Approach

Notes take from ‘Defeasible Logic Programming An Argumentative Approach’ (2004), by Alejandro J. Garcia and Guillermo R. Simari

“… The defeasible argumentation basis of DeLP allows building applications that deal with incomplete and contradictory information in dynamic domains, where information may change. Thus, DeLP can be used for representing agent’s knowledge and for providing an inference engine…”

2, the Language

2.1 Fact: a literal, i.e. a ground atom, or a negated ground atom.
2.2 Strict Rule: an ordered pair, denoted “Head <- Body”.
2.3 Defeasible Rule: an ordered pair, denoted “Head -< Body”.

2.4 Defeasible Logic Program: a possibly infinite set of facts, strict rules and defeasible rules. In a program P, denoted as (H, A), we distinguish the subset H of facts and rules, and the subset A of defeasible rules.

2.5 Defeasible Derivation (monotonic)…
2.6 Strict Derivation: all the rules used in the defeasible derivation are strict rules.
2.7 A set of rules is contradictory iff there exists a defeasible derivation for a pair of complementary literals from the set.

3, Defeasible Argumentation

3.1 Argument Structure (non-monotonic): Denoted as [A, h]… or simply an argument A for h, is a minimal non-contradictory set of defeasible rules, obtained from a defeasible derivation for a given literal h… Note that strict rules are not part of an argument structure.
3.2 [B, q] is a sub-argument structure of [A, h] if B is a subset of A.

3.3 Two literals h and h1 disagree iff the set ‘H U {h, h1}’ is contradictory, where H is the set of facts and rules of the program.
3.4 We say that [A1, h1] counter-argues, rebuts, or attacks [A2, h2] at literal h iff there exists a sub-argument [A, h] of [A2, h2] such that h and h1 disagree.

3.5 (Generalised) Specificity: Criterion which allows discriminating between two conflicting arguments. Intuitively, this notion of specificity favours two aspects in an argument: it prefers an argument (1) with greater information content (and thus more precise) or (2) with less use of rules (more direct and thus more concise).

3.6 Equi-Specificity: Two arguments [A1, h1] and [A2, h2] are equi-specific iff A1 = A2, and the literal h2 has a strict derivation from ‘H U {h1}’, and the literal h1 has a strict derivation from ‘H U {h2}’.

3.7 Argument Comparison Using Rule’s Priorities: The argument [A1, h1] will be preferred (denoted “>”) over [A2, h2] iff:
1. there exists at least one rule ra (from A1) and one rule rb (from A2) such that ra > rb.
2. and there is no rb’ (from A2) and ra’ (from A1) such that rb’ > ra’.

4, Defeaters and Argumentation Lines

4.1 [A1, h1] is a proper defeater for [A2, h2] at literal h iff there exists a sub-argument [A, h] of [A2, h2] such that [A1, h1] counter-argues [A2, h2] at h, and [A1, h1] is strictly more specific than [A, h].
4.2 [A1, h1] is a blocking defeater for [A2, h2] at literal h iff there exists a sub-argument [A, h] of [A2, h2] such that [A1, h1] counter-argues [A2, h2] at h, and [A1, h1] is unrelated by the preference order to [A, h], i.e., neither argument structure is more specific than the other.
4.3 [A1, h1] is a defeater for [A2, h2] iff it is either a proper defeater or a blocking defeater.

4.4 Argumentation Line (for [A0, h0]): A sequence of argument structures from P, denoted [[A0, h0], [A1, h1], [A2, h2] …], where each element of the sequence [Ai, hi], i > 0, is a defeater of its predecessor [Ai-1, hi-1].
4.5 Supporting and Interfering argument structures: Let [[A0, h0], [A1, h1], [A2, h2] …] be an argumentation line, we define the set of supporting argument structures {[A0, h0], [A2, h2], [A4, h4] …} and the set of interfering argument structures {[A1, h1], [A3, h3], [A5, h5] …}.

4.6 A set of arguments {[Ai, hi]} (for i = 1 to n) is concordant iff the set ‘H U A1 U A2 U … U An’ is non-contradictory.

4.7 An argumentation line is acceptable iff:
1. It is a finite sequence.
2. The set of supporting arguments is concordant, and the set of interfering arguments is concordant.
3. No argument in the argumentation line is a sub-argument of an argument appearing earlier.
4. For all i, such that the argument [Ai, hi] is a blocking defeater for [Ai-1, hi-1], if [Ai+1, hi+1] exists, then [Ai+1, hi+1] is a proper defeater for [Ai, hi].

It is interesting to note that changes in the definition of acceptable argumentation line may produce a different behaviour of the formalism. Thus, the definition could be used as a way of tuning the system to obtain different results.

5, Warrant through Dialectical Analysis

In DeLP a literal h will be warranted if there exists a non-defeated argument structure [A, h]. In order to establish whether [A, h] is non-deafeated, the set of defeaters for A will be considered. Since each defeater D for A is itself an argument structure, defeaters for D will in turn be considered, and so on. Therefore, more than one argumentation line could arise, leading to a tree structure.

5.1 Dialectical Tree… Every node (except the root) represents a defeater (proper or blocking) of its parent, and leaves correspond to non-defeated arguments. Each path from the root to a leaf corresponds to one different acceptable argumentation line.

Marking of a dialectical tree (a bottom-up process through which we are able to determine the marking of the root):
(1) All leaves in the tree are marked as “U”.
(2) An inner node will be marked as “U” iff every child of it is marked as “D”. Otherwise it will be marked as “D”, i.e. iff it has at least one child marked as “U”.

5.2 Warranted Literals: Let [A, h] be an argument structure and T* its associated marked dialectical tree. The literal h is warranted iff the root of T* is marked as “U”. We will say that A is a warrant for h.

5.3 Answer to Queries: The answers of a DeLP interpreter can be defined in terms of a modal operator B. In terms of B, there are four possible answers for a query h:
- YES, if Bh (h is warranted)
- NO, if B~h (the compliment of h is warranted)
- UNDECIDED, if Bh and B~h (neither h nor ~h are warranted)
- UNKNOWN, if h is not in the language of the program.

The Warrant Procedure with pruning

6, DeLP Extensions

DeLP with Default Negation… In DeLP “absence of sufficient evidence” means “there is no warrant”. Therefore, the default negation ‘not F’ will be assumed when the literal F is not warranted… Default negation will be allowed only preceding literals in the body of defeasible rules, e.g., ‘~cross_railway_tracks -< not ~train_is_coming’…

Extended Defeasible Rules: defeasible rules that use default negation.

… The reason not allowing default negotiation in strict rules is twofold. On one hand, a strict rule ‘p <- not q’ is not completely strict, because the head ‘p’ will be derived assuming ‘not q’. On the other hand, the set of strict rules and facts could become a contradictory set in many cases…

Extended Defeasible Logic Program: A set of Facts, Strict Rules and Extended Defeasible Rules.

6.1 Extended Defeasible Derivation: Since the decision of assuming an extended literal ‘not L’ will be carried out by the dialectical process, the definition of defeasible derivation is modified accordingly in extended DeLP. The change reflects that when an extended literal is found in the body of a rule, the literal will be ignored…

6.2 Extended Argument Structure: The definition of argument structure is also extended in order to avoid the introduction of self-defeating arguments… The definition is as before but with an addition rule:
- if L is a literal in the defeasible derivation (from the union of the supporting argument, and set of facts and rules) of h, then there is no defeasible rule in the argument containing ‘not L’ in its body.

6.3 In extended DeLP, default negated literals (assumptions on which the derivation is based) will be another point of attack in an argument… An argument structure [A1, h1] is a defeater for [A2, h2] iff it is a proper or blocking defeater for [A2, h2], or an attack to an assumption of [A2, h2].

DeLP with presumptions (a defeasible rule with an empty body, e.g. ‘a -<’)…

7, Implementation and Application (visit http://cs.uns.edu.ar/~ajg/DeLP.html)

No comments: