Vol-3197/short2
Jump to navigation
Jump to search
Paper
| Paper | |
|---|---|
 edit
| |
| description | scientific paper published in CEUR-WS Volume 3197 |
| id | Vol-3197/short2 |
| wikidataid | Q117341470โQ117341470 |
| title | Abductive Reasoning with Sequent-Based Argumentation |
| pdfUrl | https://ceur-ws.org/Vol-3197/short2.pdf |
| dblpUrl | https://dblp.org/rec/conf/nmr/ArieliBHS22 |
| volume | Vol-3197โVol-3197 |
| session | โ |
Freitext
Abductive Reasoning with Sequent-Based Argumentation
Abductive Reasoning with Sequent-Based Argumentation
(Extended Abstract)
Ofer Arieli1 , AnneMarie Borg2 , Matthis Hesse3 and Christian Straรer3
1
School of Computer Science, Tel-Aviv Academic College, Israel
2
Department of Information and Computing Sciences, Utrecht University, The Netherlands
3
Institute for Philosophy II, Ruhr University Bochum, Germany
Abstract
We show that logic-based argumentation, and in particular sequent-based frameworks, is a robust argumentative setting for
abductive reasoning and explainable artificial intelligence.
1. Introduction monotonic (if ๐ฎ โฒ โข ๐ and ๐ฎ โฒ โ ๐ฎ, then ๐ฎ โข ๐), and tran-
sitive (if ๐ฎ โข ๐ and ๐ฎ โฒ , ๐ โข ๐ then ๐ฎ, ๐ฎ โฒ โข ๐).
Abduction is the process of deriving a set of explanations
โ The language L contains at least a โข-negation opera-
of a given observation relative to a set of assumptions.
tor ยฌ, satisfying ๐ ฬธโข ยฌ๐ and ยฌ๐ ฬธโข ๐ (for atomic ๐), and
The systematic study of abductive reasoning goes back
a โข-conjunction operator โง, forโ๏ธ which ๐ฎ โข ๐ โง ๐ iff
to Peirce (see [1]). Abduction is closely related to โin-
๐ฎ โข ๐ and ๐ฎ โข ๐. We denote by ฮ the conjunction of
ference to the best explanation (IBE)โ [2]. However, it is
the formulas in ฮ. We sometimes assume the availability
often distinguished from the latter in that abductive infer-
of a deductive implication โ, satisfying ๐ฎ, ๐ โข ๐ iff
ence may provide explanations that are not known as the
๐ฎ โข ๐ โ ๐.
best explanation available, but that are merely worthy of
A set ๐ฎ of formulas is โข-consistent, if there are no
conjecturing or entertaining (see, e.g., [3, 4, 5]).
formulas ๐1 , . . . , ๐๐ โ ๐ฎ for which โข ยฌ(๐1 โง ยท ยท ยท โง ๐๐ ).
In this work, we model abduction (not in the strict
sense of IBE) by computational argumentation, and show โ Arguments based on a logic L = โจL, โขโฉ are single-
that sequent-based argumentation frameworks [6, 7] are conclusioned L-sequents [8], i.e., expressions of the form
a solid argumentative base for abductive reasoning. Ac- ฮ โ ๐, where โ is a symbol that does not appear in L,
cording to our approach, abductive explanations are han- and such that ฮ โข ๐. ฮ is called the argumentโs support
dled by ingredients of the framework, and so different (also denoted Supp(ฮ โ ๐)) and ๐ is its conclusion
considerations and principles concerning those explana- (denoted Conc(ฮ โ ๐)). An ๐ฎ-based argument is an L-
tions are expressed within the framework. The advantages argument ฮ โ ๐, where ฮ โ ๐ฎ. We denote by ArgL(๐ฎ)
of this are discussed in the last section of the paper. the set of the L-arguments that are based on ๐ฎ.
We distinguish between two types of premises: a โข-
consistent set ๐ณ of strict premises, and a set ๐ฎ of defea-
2. Sequent-Based Argumentation sible premises. We write Arg๐ณ L (๐ฎ) for ArgL(๐ณ โช ๐ฎ).
We denote by L a propositional language. Atomic formu- โ Attack rules are sequent-based inference rules for rep-
las in L are denoted by ๐, ๐, ๐, formulas are denoted by resenting attacks between sequents. Such rules consist
๐, ๐, ๐ฟ, ๐พ, ๐, sets of formulas are denoted by ๐ณ , ๐ฎ, โฐ, and of an attacking argument (the first condition of the rule),
finite sets of formulas are denoted by ฮ, โ, ฮ , ฮ, all of an attacked argument (the last condition of the rule), con-
which can be primed or indexed. The set of atomic formu- ditions for the attack (the other conditions of the rule)
las appearing in the formulas of ๐ฎ is denoted Atoms(๐ฎ). and a conclusion (the eliminated attacked sequent). The
The set of the (well-formed) formulas of L is denoted elimination of ฮ โ ๐ is denoted by ฮ ฬธโ ๐.
WFF(L), and its power set is denoted โ(WFF(L)). Given a set ๐ณ of strict (non-attacked) formulas, we
shall concentrate here on the following two attack rules:
โ The base logic is an arbitrary propositional logic,
namely a pair L = โจL, โขโฉ consisting of a language L Direct Defeat (for ๐พ ฬธโ ๐ณ ):
and a consequence relation โข on โ(WFF(L))รWFF(L). ฮ1 โ ๐1 ๐1 โ ยฌ๐พ ฮ2 , ๐พ โ ๐2
The relation โข is assumed to be reflexive (๐ฎ โข ๐ if ๐ โ ๐ฎ), ฮ2 , ๐พ ฬธโ ๐2
Consistency Undercut (for ฮ2 ฬธ= โ
, ฮ2 โฉ๐ณ = โ
, ฮ1 โ๐ณ ):
ฮ2 , ฮโฒ2 โ ๐
โ๏ธ
NMR 2022: 20th International Workshop on Non-Monotonic Reasoning, ฮ1 โ ยฌ ฮ2
August 7-9, 2022, Haifa, Israel
ยฉ 2022 Copyright for this paper by its authors. Use permitted under Creative Commons License ฮ2 , ฮโฒ2 ฬธโ ๐
Attribution 4.0 International (CC BY 4.0).
CEUR
Workshop
Proceedings
http://ceur-ws.org
ISSN 1613-0073
CEUR Workshop Proceedings (CEUR-WS.org)
143
๏ฟฝDirect Defeat (DirDef) indicates that if the conclusion E1 E2
(๐1 ) of the attacker entails the negation of a formula (๐พ)
clear_skies โ clear_skies rainy โ rainy
in the support of an argument, the latter is eliminated.
When ฮ1 = โ
, consistency undercut (ConUcut) elimi- clear_skies, rainy,
clear_skies โ ยฌrainy rainy โ ยฌsprinklers
nates an argument with an inconsistent support. โ ยฌrainy โ ยฌsprinklers
โ A (sequent-based) argumentation framework (AF), rainy,
based on the logic L and the attack rules in AR, for a set clear_skies โ ยฌrainy
of defeasible premises ๐ฎ and a โข-consistent set of strict wet_grass โ
โ ยฌclear_skies
premises ๐ณ , is a pair AFL,AR (๐ฎ) = โจArgL (๐ฎ), Aโฉ where
๐ณ ๐ณ
[sprinkler], rainy,
sprinklers โ wet_grass rainy โ wet_grass
A โ Arg๐ณ L (๐ฎ)รArg ๐ณ
L (๐ฎ) and (๐1 , ๐ 2 ) โ A iff there is a โ wet_grass
rule R๐ณ โ AR, such that ๐1 R๐ณ -attacks ๐2 . We shall use
AR and A interchangeably, denoting both of them by A. Figure 1: Part of the AF of Example 1 (without the gray node)
โ Semantics of sequent-based frameworks are defined as and of Example 2 (with the gray node).
usual by Dung-style extensions [9]: Let AF = AF๐ณ L,A (๐ฎ)
= โจArg๐ณ L (๐ฎ), Aโฉ be an AF and let E โ Arg ๐ณ
L (๐ฎ). E
attacks ๐ if there is an ๐โฒ โ E such that (๐โฒ , ๐) โ A. E
defends ๐ if E attacks every attacker of ๐, and E is conflict- (since the argument rainy, rainy โ wet_grass โ
free (cf) if for no ๐1 , ๐2 โ E it holds that (๐1 , ๐2 ) โ A. wet_grass is in E2 ), but it is not skeptically deducible
E is admissible if it is conflict-free and defends all of (there is no ๐ โ E1 such that Conc(๐) = wet_grass).
its elements. A complete (cmp) extension of AF is an
admissible set that contains all the arguments that it
defends. The grounded (grd) extension of AF is the โ-
minimal complete extension of Arg๐ณ
3. Abductive Reasoning
L (๐ฎ), a preferred (prf)
extension of AF is a โ-maximal complete extension of For supporting abductive explanations in sequent-based
Arg๐ณ L (๐ฎ), and a stable (stb) extension of AF is a conflict- argumentation, we introduce abductive sequents, which
free set in Arg๐ณ L (๐ฎ) that attacks every argument not in are expressions of the form ๐ โ ฮ, [๐], intuitively mean-
it.1 We denote by Extsem (AF) the set of all the extensions ing that โ(the explanandum) ๐ may be inferred from ฮ,
of AF of type sem. assuming that ๐ holdsโ. While ฮ โ ๐ฎ โช ๐ณ , ๐ may not be
โ Entailments of AF = AF๐ณ ๐ณ
L,A (๐ฎ) = โจArgL (๐ฎ), Aโฉ an assumption, but rather a hypothetical explanation of
with respect to a semantics sem are defined as follows: the conclusion.
โ Skepticalโ๏ธentailment: ๐ฎ |โผโฉ,sem ๐ if there is an argu- Abductive sequents are produced by the following rule
L,A,๐ณ
ment ๐ โ Extsem (AF) such that Conc(๐) = ๐. that models abduction as โbackwards reasoningโ:
L,A,๐ณ ๐ if for every
โ Weakly skeptical entailment: ๐ฎ |โผโ,sem ๐, ฮ โ ๐
โข Abduction:
extension E โ Extsem (AF) there is an argument ๐ โ E ๐ โ ฮ, [๐]
such that Conc(๐) = ๐.
โช,sem This rule allows us to produce abductive sequents like
โ Credulous โ๏ธentailment: ๐ฎ |โผL,A,๐ณ ๐ iff there is an argu- wet_grass โ [sprinklers], sprinklers โ wet_
ment ๐ โ Extsem (AF) such that Conc(๐) = ๐. grass that provides an explanation to wet_grass.
Example 1. Consider a sequent-based AF, based on Since abductive reasoning is a form of non-monotonic
classical logic CL and the set ๐ฎ of defeasible assumptions: reasoning, we need a way to attack abductive sequents.
To this end, we consider rules like those from Section 2:
โจ clear_skies, rainy, clear_skies โ ยฌrainy, โฌ
โง โซ
rainy โ ยฌsprinklers, rainy โ wet_grass, โข Abductive Direct Defeat (for ๐พ โ (ฮ2 โช {๐}) โ ๐ณ ):
sprinklers โ wet_grass
โฉ โญ
ฮ1 โ ๐1 ๐1 โ ยฌ๐พ ๐2 โ [๐], ฮ2
Suppose further that ๐ณ = โ
and the attack rules are ๐2 ฬธโ [๐], ฮ2
DirDef and ConUcut. Then, for instance, the arguments
Note that this attack rule assures, in particular, the con-
๐1 : clear_skies, clear_skies โ ยฌrainy โ ยฌrainy
sistency of explanations with the strict assumptions, thus
๐2 : rainy, clear_skies โ ยฌrainy โ ยฌclear_skies
it renders the following rule admissible:
DirDef-attack each other. There are two stable/preferred
extensions E1 and E2 , where ๐1 โ E1 and ๐2 โ E2 (see โข Consistency (for ฮ โ ๐ณ ): ฮ1 โ ยฌ๐ ๐ โ [๐], ฮ2
1
Fig. 1). Thus, with respect to stable or preferred seman- ๐ ฬธโ [๐], ฮ2
tics, wet_grass credulously follows from the framework
Abductive explanations should meet certain require-
1
For an in-depth discussion of extension types see [10]. ments to ensure their behavior (see, e.g., [11]). Below,
144
๏ฟฝwe express some of the common properties in terms of โ weakly-skeptical sem-explanation of ๐, if in every sem-
attack rules that may be added to the framework. extension
โ๏ธ of AAFL,Aโ(๐ฎ) there is an abductive argument
๐ณ
๐ โ [ โฐ], ฮ for some ฮ โ ๐ฎ.
โข ๐ โ ๐ ๐ โ [๐]
โข Non Vacuousity: โ credulous sem-explanation of ๐, if there is ฮ โ ๐ฎ
๐ ฬธโ [๐]
such that ๐ โ [ โฐ], ฮ is in some sem-extension of
โ๏ธ
This rule prevents self-explanations. Thus, in the running AAF๐ณ L,Aโ(๐ฎ).
example, wet_grass โ [wet_grass] is excluded.
Example 2. As mentioned, the abductive sequent wet_
โข Minimality: grass โ [sprinklers], sprinklers โ wet_grass
๐ โ [๐1 ], ฮ ๐2 โ ๐1 ๐1 ฬธโ ๐2 ๐ โ [๐2 ], ฮ is producible by Abduction from the sequent-based frame-
work in Example 1, and belongs to a stable/preferred
๐ ฬธโ [๐2 ], ฮ extension of the related abductive sequent-based frame-
This rule assures the generality of explanations. Thus, in work (see again Fig. 1). Therefore, sprinklers is a cred-
our example, sprinklers โง irrelevant_fact should ulous (but not [weakly] skeptical) stb/prf-explaination
not explain wet_grass, since sprinklers is a more gen- of wet_grass.
eral and so more relevant explanation. Example 3. Let L = CL, A = {DirDef, ConUcut}
ฮ1 โ ๐ ๐ โ [๐], ฮ2 with ๐ฎ = {๐, ยฌ๐ โง ๐} and ๐ณ = {๐ โง ๐ โ ๐ }. For sem โ
โข Defeasible Non-Idleness: {stb, prf}, ๐ โง ๐ is a weakly-skeptical sem-explanation
๐ ฬธโ [๐], ฮ2
of ๐ , since the corresponding abductive framework has
ฮ1 โ ๐ ๐ โ [๐], ฮ2 two sem-extensions, one with ๐ โ [๐ โง ๐], ๐, ๐ โง ๐ โ ๐
โข Strict Non-Idleness (ฮ1 โ ๐ณ ):
๐ ฬธโ [๐], ฮ2 and the other with ๐ โ [๐ โง ๐], ยฌ๐ โง ๐, ๐ โง ๐ โ ๐ . This
holds also when the non-vacuousity or the strict non-
The two rules above assure that assumptions shouldnโt al- idleness attack rules are part of the framework. However,
ready explain the explanandum. Defeasible non-idleness ๐ โง ๐ is no longer a weakly-skeptical sem-explanation of
rules out explaining wet_grass by sprinklers, since ๐ when minimality attack is added, since the extension
the former is already inferred from the defeasible assump- that contains ๐ โ [๐ โง ๐], ยฌ๐ โง ๐, ๐ โง ๐ โ ๐ includes a
tions (assuming that it is rainy), while strict non-idleness minimality attacker, ๐ โ [๐], ยฌ๐ โง ๐, ๐ โง ๐ โ ๐ .
allows this alternative explanation (wet_grass cannot
be inferred from the strict assumptions). These two at- Example 4. Consider now ๐ฎ = {๐ โง ๐, ยฌ๐ โง ๐}. This
tack rules are particularly interesting when abductive time, with minimality, ๐ โง ๐ is not even a credulous
reasoning is used to generate novel hypotheses explain- sem-explanation of ๐ (sem โ {stb, prf}), since each of
ing observations that are not already explained by a given the two sem-extensions contains a minimality attacker
theory resp. the given background assumptions.2 (๐ โ [๐], ๐โง๐, ๐ โง๐ โ ๐ or ๐ โ [๐], ยฌ๐โง๐, ๐ โง๐ โ ๐ ).
So, ๐ โง ๐, unlike ๐, does not sem-explain ๐ .
Next, we adapt sequent-based argumentation frame-
works to an abductive setting, using abductive sequents,
the new inference rule, and additional attack rules. 4. Discussion and Conclusion
Given a sequent-based framework AF๐ณ L,A (๐ฎ), an ab-
Abduction has been widely applied in different deduc-
ductive sequent-based framework AAF๐ณ L,Aโ(๐ฎ) is construc-
ted by adding to the arguments in ArgL (๐ฎ) also abduc- tive systems (such as adaptive logics [12]) and AI-based
๐ณ
tive arguments, produced by Abduction, and where Aโ is disciplines (e.g., logic programing [13]), including in the
obtained by adding to the attack rules in A also (some of) context of formal argumentation (see the survey in [14]).
the rules for maintaining explanations that are described This ongoing work offers several novelties. In terms
above. Explanations are then defined as follows: of knowledge representation we transparently represent
abductive inferences by an explicit inference rule that
Definition 1. Let AAF๐ณ L,Aโ(๐ฎ) be an abductive sequent- produces abductive arguments. The latter are a new type
based argumentation framework as described above. A of hypothetical arguments that are subjected to poten-
finite set โฐ of L-formulas is called: tial defeats. Specifically designed attack rules address
the quality of the offered explanation and thereby model
โ๏ธ sem-explanation of ๐, if there is ฮ ๐ณโ ๐ฎ s.t. critical questions [15] and meta-argumentative reason-
โ skeptical
๐ โ [ โฐ], ฮ is in every sem-extension of AAFL,Aโ(๐ฎ).
ing [16]. This is both natural and philosophically moti-
2
In some accounts of abduction, e.g. [5], it is argued that the ab- vated, as argued in [17]. Our framework offers a high
ductively inferred ๐ should be of lesser epistemic status than the degree of modularity, and may be based on a variety of
reasonerโs starting point and so โthe fundamental conceptual fact
about abduction is that abduction is ignorance-preserving reason- propositional logics. Desiderata on abductive arguments
ingโ (p. 40). Our attack rules ensure that the reasoner faces what can be disambiguated in various ways by simply chang-
Gabbay & Woods call an โignorance problemโ (p. 42, Def. 3.2). ing the attack rules, all in the same base framework.
145
๏ฟฝReferences of explanatory hypotheses: an argumentative ap-
proach, Logic Journal of the IGPL 29(4) (2021) 523โ
[1] C. S. Peirce, The Collected Papers of Charles 535.
Sanders Peirce, Vol. I: The Principles of Philosophy,
Harvard University Press, Cambridge, 1931.
[2] P. Lipton, Inference to the Best Explanation, Rout-
ledge, 2004. 2nd edition.
[3] S. Yu, F. Zenker, Peirce knew why abduction isnโt
IBE โ A scheme and critical questions for abductive
argument, Argumentation 32 (2017) 569โ587.
[4] G. Minnameier, Peirce-suit of truth โ Why infer-
ence to the best explanation and abduction ought
not to be confused, Erkenntnis 60 (2004) 75โ105.
[5] D. Gabbay, J. Woods, The reach of abduction. A
practical logic of cognitive systems, North-Holland,
2005.
[6] O. Arieli, C. Straรer, Sequent-based logical argu-
mentation, Argument & Computation 6 (2015) 73โ
99.
[7] A. Borg, Assumptive sequent-based argumenta-
tion, Journal of Applied Logics โ IfCoLog Journal
of Logics and Their Applications 7 (2020) 227โ294.
[8] G. Gentzen, Untersuchungen รผber das logische
schlieรen I, II, Mathematische Zeitschrift 39 (1934)
176โ210, 405โ431.
[9] P. M. Dung, On the acceptability of arguments and
its fundamental role in nonmonotonic reasoning,
logic programming and n-person games, Artificial
Intelligence 77 (1995) 321โ357.
[10] P. Baroni, M. Caminada, M. Giacomin, Abstract
argumentation frameworks and their semantics, in:
P. Baroni, D. Gabbay, M. Giacomin, L. van der Torre
(Eds.), Handbook of Formal Argumentation, vol-
ume 1, College Publications, 2018, pp. 159โ236.
[11] J. Meheus, L. Verhoeven, M. Van Dyck, D. Provijn,
Ampliative adaptive logics and the foundation of
logic-based approaches to abduction, Logical and
Computational Aspects of Model-Based Reasoning
25 (2002) 39โ71.
[12] J. Meheus, D. Batens, A formal logic for abductive
reasoning, Logic Journal of the IGPL 14 (2006) 221โ
236.
[13] M. Denecker, A. Kakas, Abduction in logic pro-
gramming, in: Computational Logic: Logic Pro-
gramming and Beyond, LNCS 2407, Springer, 2002,
pp. 402โ436.
[14] K. Cyras, A. Rago, E. Albini, P. Baroni, F. Toni, Ar-
gumentative XAI: A survey, in: Proc. 30th IJCAI,
2021, pp. 4392โ4399.
[15] D. Walton, C. Reed, F. Macagno, Argumentation
Schemes, Cambridge University Press, 2008.
[16] G. Boella, D. Gabbay, L. van der Torre, S. Villata,
Meta-argumentation modelling I: Methodology and
techniques, Studia Logica 93 (2009) 297โ355.
[17] P. Olmos, Abduction and comparative weighing
146
๏ฟฝ