Transcript Slides - ijcai-11

Relating the Semantics of
Abstract Dialectical Frameworks
and Standard AFs
Gerd Brewka (II, Leipzig)
Paul E. Dunne (DCS, Liverpool)
Stefan Woltran (DBAI, Vienna)
22/07/11
IJCAI 2011 Barcelona
Argumentation Frameworks
•
•
•
•
•
•
•
Introduced in Dung (AIJ, 1995)
Arguments: X
Attacks AXX
Acceptability concept: : 2X {,T}
E(<X,A>)={S X :(S)}
Examples: Grounded, Preferred, Stable
S is stable if conflict-free (SSA=)
and for each yS we have some xS
with <x,y>A.
22/07/11
IJCAI 2011 Barcelona
Problematic Aspects
• Approach is extremely abstract, so can
complicate modelling “real-world” cases.
• Incompatibility of arguments, p and q,
can only be (directly) expressed through
a binary attack relation, <p,q>A, so
that “p is acceptable if q is not”.
• But, we may often want to describe
more sophisticated interactions.
22/07/11
IJCAI 2011 Barcelona
3
Extending from Binary Attacks
• Amgoud, Cayrol et al. (2005, 2008)
propose bipolar frameworks, whereby
an additional (binary) support relation,
R, is used: <p,q>R expresses “q is
acceptable if p is so”.
• Brewka & Woltran (KR2010) develop
this notion of describing more complex
argument interaction by introducing
Abstract Dialectical Frameworks.
22/07/11
IJCAI 2011 Barcelona
Abstract Dialectical Frameworks
(ADFs) r3
Conditions for s to be
acceptable expressed
via acceptability of
its parents – {r1,r2,…,}
r2
s
r1
That is, as a propositional
function, over the acceptance
conditions controlling each r
22/07/11
IJCAI 2011 Barcelona
r4
r5
Abstract Dialectical Frameworks
(ADFs) (continued)
• Formally, an ADF is a triple (S,L,C) with
S a set of arguments, LSS a set of
links, (cf <X,A> in AFs) and C a set of
acceptance conditions, Cs, the
acceptance condition for sS being a
predicate
Cs: 2par(s) {,T}
• Hence, “s is acceptable if an
appropriate configuration of its attackers
as given through Cs is acceptable”
22/07/11
IJCAI 2011 Barcelona
Examples
a. Dung-style standard AF:
C = ({r : rpar(s))
b. All links are supporting:
C = ({r : rpar(s)}
c. s is acceptable if exactly one of its
parents is
({r : rpar(s)}) 
{(r  t) : {r,t}par(s)}
22/07/11
IJCAI 2011 Barcelona
Models in ADFs
• The most basic semantics for
“acceptable sets” in ADFs are models.
• For (S,L,C) and MS, M is conflict-free
if for each s in S, Cs[Mpar(s)]=T; M is
a model if M is conflict-free and should
Cs[Mpar(s)]=T then sM.
22/07/11
IJCAI 2011 Barcelona
AFs to ADFs (and back again?)
• From Example (a) it is easy to transform
an AF <X,A> to an ADF (SX,LA,C) so
that stable extensions map to models.
• This translation has |SX|=|X|.
• In going from an ADF (S,L,C) to an AF
<XS,AL> with models mapping to stable
extensions a naïve translation gives
|XS|2|S| .
• Is this exponential increase needed?
22/07/11
IJCAI 2011 Barcelona
Polynomial size simulations
•
We say <XS,AL> model simulates (S,L,C) if
S XS and
A. For every model M of (S,L,C) there is a
subset Y of XS with MY a stable extension
of <XS,AL>.
B. For every stable extension P of <XS,AL>,
PS is a model of (S,L,C).
• A model simulation is polynomial if |XS| is
polynomially bounded in the “size” of
(S,L,C).
22/07/11
IJCAI 2011 Barcelona
What is the “size” of an ADF?
• Defining the size of D=(S,L,C) to be |S|
fails to acknowledge that the conditions
given in C may be very intricate.
• In addition, for computation, some
formal description of C must be used.
• We should, therefore, include the “cost”
of such descriptions in defining size.
• e.g. if each Cs is presented as a
propositional formula, s then size(D) is
the sum of |s|, ie operations defining .
22/07/11
IJCAI 2011 Barcelona
Main Results
1. Let D=(S,L,C) be an ADF. There is an AF,
<XS,AL> that model simulates D and has
|XS| =O(size(D)).
2. <XS,AL> may be constructed in time
polynomial in size(D).
3. Both (1) & (2) continue to hold if
“propositional formula” is replaced by
“Boolean combinational network” as the
representational formalism for Cs.
22/07/11
IJCAI 2011 Barcelona
Outline of Proof
• Translate each Cs to an AF, <Xs,As>
containing par(s) and s amongst its
arguments.
• Each subset R of par(s) for which Cs[R]=T
induces a stable extension of <Xs,As>.
• Each stable extension, P, of <Xs,As> has
Cs[P par(s)]=T.
• Combine individual <Xs,As> (respecting L) to
complete simulation.
22/07/11
IJCAI 2011 Barcelona
Some Issues
• Models are a very limited solution concept.
• The notions of stable and well-founded model
are far more useful.
• The former, defined for bipolar ADFs, B, are
the least models of an ADF, BM, obtained by
a translation similar to the Gelfond-Lifschitz
rewriting of logic programs.
• The latter is the least fixed point of a
particular binary operator on S.
• How do these relate to structures within AFs?
22/07/11
IJCAI 2011 Barcelona
Well-founded & Stable Models
1. If G is the grounded extension of the model
simulating AF for (S,L,C) then GS is the
well-founded model of (S,L,C).
2. If B is a BADF, we may construct in
polynomial time, an ADF, D*, whose models
define exactly the stable models of B.
3. The construction in (2) is rather indirect and
exploits ideas originating in the treatment of
“loop formulae” and “level mappings”.
22/07/11
IJCAI 2011 Barcelona
Summary
• Several basic solution concepts for ADFs
may be “easily” mapped to extensions in a
corresponding AF.
• ADFs are a more natural modelling
technique, however, there is a significant
body of work on algorithms in AFs.
• Motivates modelling scenarios as ADFs and
computation via the related AF (cf HLL to
machine-level compilation).
• Potential realistic application is given through
the Carneades frameworks of (Gordon et al.,
2007) and the reconstruction of these as
ADFs (Brewka & Gordon, 2010).
22/07/11
IJCAI 2011 Barcelona