=Paper=
{{Paper
|id=Vol-550/paper-1
|storemode=property
|title=download
|pdfUrl=https://ceur-ws.org/Vol-550/invited1.pdf
|volume=Vol-550
}}
==download==
https://ceur-ws.org/Vol-550/invited1.pdf
Nonmonotonic Multi-Context Systems:
State of the Art and Future Challenges
Gerhard Brewka
Computer Science Institute
University of Leipzig
brewka@informatik.uni-leipzig.de
joint work with Thomas Eiter
G. Brewka (Leipzig) LOG-IC 2009 1 / 36
1. Motivation
• Larger and larger bodies of knowledge being formalized
• Sheer size of, say, medical ontologies requires methods for
structuring and modularizing KBs
• Wealth of existing logical tools to model ontologies, actions,
interactions, dynamic processes, forms of human reasoning, ...
• Single all-purpose formalism not in sight: necessary to integrate
several formalisms into a single system
• Often done in an ad hoc way for particular pair of formalisms (e.g.
rules and ontologies)
• Can we do this in a more principled way?
G. Brewka (Leipzig) Nonmonotonic Multi-Context Systems LOG-IC 2009 2 / 36
Contexts
• In AI first investigated by John McCarthy (1987), without definition
• Intuitively, a context describes a particular viewpoint, perspective,
granularity, person/agent/database ...
• Here: (almost/somewhat) independent unit of reasoning
• Aspects of multi-context systems:
• Locality: different languages, reasoning methods, logics
• Compatibility: information flow between contexts
• Provide a particular form of information integration
Example: Magic Box
G. Brewka (Leipzig) Nonmonotonic Multi-Context Systems LOG-IC 2009 3 / 36
Outline
1 Motivation (done)
2 Nonmonotonic MCS
• Background
• Logics and Contexts
• Acceptable Belief States
3 Argumentation Context Systems
• Background
• Context Dependent Argumentation
• Mediators
• The Framework and Acceptable Argumentation States
4 Combining MCS and ACS: Outlook
• Making Logics Context Dependent
• Mediators and Framework
5 Conclusions
G. Brewka (Leipzig) Nonmonotonic Multi-Context Systems LOG-IC 2009 4 / 36
2. Multi-Context Systems
Historical Background
• Monotonic multi-context systems developed by Giunchiglia,
Serafini et al. in the 90s
• Integrate different monotonic inference systems
• Information flow modeled using bridge rules
• First attempts to make bridge rules nonmonotonic by
Roelofsen/Serafini (2005) and Brewka/Roelofsen/Serafini
(Contextual Default Logic, 2007)
• Resulting system homogeneous: reasoners of same type (namely
logic programs or Reiter’s default logic)
G. Brewka (Leipzig) Nonmonotonic Multi-Context Systems LOG-IC 2009 5 / 36
Our Goals
• Generalize existing approaches
• Define a heterogeneous multi-context framework accommodating
both monotonic and nonmonotonic contexts
• Should be capable of integrating logics like description logics,
modal logics, default logics, logic programs, etc.
G. Brewka (Leipzig) Nonmonotonic Multi-Context Systems LOG-IC 2009 6 / 36
“Logics”
Want to capture the “typical” KR logics, including nonmonotonic logics
with multiple acceptable belief sets (e.g., Reiter’s Default Logic).
Logic
A logic L is a tuple
L = (KBL , BSL , ACCL )
• KBL is a set of well-formed knowledge bases, each being a
set (of formulas)
• BSL is a set of possible belief sets, each being a set (of
formulas)
• ACCL : KBL → 2BSL assigns to each knowledge base a set
of acceptable belief sets
L is called monotonic, if (1) |ACCL (kb)| = 1 and (2) kb ⊆ kb0 ,
ACCL (kb) = {S}, and ACCL (kb0 ) = {S 0 } implies S ⊆ S 0 .
G. Brewka (Leipzig) Nonmonotonic Multi-Context Systems LOG-IC 2009 7 / 36
Example Logics Over Signature Σ
Propositional logic
• KB: the sets of prop. Σ-formulas
• BS: the deductively closed sets of prop. Σ-formulas
• ACC(kb): Th(kb)
Default logic
• KB: the default theories over Σ
• BS: the deductively closed sets of Σ-formulas
• ACC(kb): the extensions of kb
Normal LPs under answer set semantics
• KB: the logic programs over Σ
• BS: the sets of atoms of Σ
• ACC(kb): the answer sets of kb
G. Brewka (Leipzig) Nonmonotonic Multi-Context Systems LOG-IC 2009 8 / 36
Multi-Context Systems
• As in monotonic MCS, information integration via bridge rules
• As in Contextual Default Logic, bridge rules (and logics used) can
be nonmonotonic
• Unlike in Contextual Default Logic, arbitrary logics can be used
Bridge Rules
L = L1 , . . . , Ln a collection of logics.
Lk -bridge rule over L (1 ≤ k ≤ n):
s ← (r1 : p1 ), . . . , (rj : pj ),
not (rj+1 : pj+1 ), . . . , not (rm : pm )
where (1) every kb ∈ KBk fulfills kb ∪ {s} ∈ KBk , (2) each
rk ∈ {1, . . . , n}, and (3) each pk is in some belief set of Lrk .
G. Brewka (Leipzig) Nonmonotonic Multi-Context Systems LOG-IC 2009 9 / 36
Multi-Context Systems, ctd.
Multi-Context System
A Multi-Context System
M = (C1 , . . . , Cn )
consists of contexts
Ci = (Li , kbi , bri ), i ∈ {1, . . . , n},
where
• each Li is a logic,
• each kbi ∈ KBi is a Li -knowledge base, and
• each bri is a set of Li -bridge rules over M’s logics.
M can be nonmonotonic because one of its context logics is AND/OR
because a context has nonmonotonic bridge rules.
G. Brewka (Leipzig) Nonmonotonic Multi-Context Systems LOG-IC 2009 10 / 36
Example
Consider the multi-context system M = (C1 , C2 ), where the contexts
are different views of a paper by the authors.
• C1 :
• L1 = Classical Logic
• kb1 = { unhappy ⊃ revision }
• br1 = { unhappy ← (2 : work ) }
• C2 :
• L2 = Reiter’s Default Logic
• kb2 = { good : accepted/accepted }
• br2 = { work ← (1 : revision),
good ← not (1 : unhappy ) }
G. Brewka (Leipzig) Nonmonotonic Multi-Context Systems LOG-IC 2009 11 / 36
Acceptable Belief States
• Belief state: sequence of belief sets, one for each context
• Fundamental Question: Which belief states are acceptable?
• Must be based on the knowledge base of a context AND the
information accepted in other contexts (if there are appropriate
bridge rules)
• Intuition: belief states must be in equilibrium:
The selected belief set for each context Ci must be among
the acceptable belief sets for Ci ’s knowledge base together
with the heads of Ci ’s applicable bridge rules.
G. Brewka (Leipzig) Nonmonotonic Multi-Context Systems LOG-IC 2009 12 / 36
Acceptable Belief States, ctd.
Applicable Bridge Rules
Let M = (C1 , . . . , Cn ). The bridge rule
s ← (r1 : p1 ), . . . , (rj : pj ),
not (rj+1 : pj+1 ), . . . , not (rm : pm )
is applicable in belief state S = (S1 , . . . , Sn ) iff
(1) pi ∈ Sri (1 ≤ i ≤ j), and (2) pk 6∈ Srk (j + 1 ≤ k ≤ m).
Equilibrium
A belief state S = (S1 , . . . , Sn ) of M is an equilibrium iff for
i ∈ {1, . . . , n}
Si ∈ ACCi (kbi ∪ {head(r ) | r ∈ bri is applicable in S}).
G. Brewka (Leipzig) Nonmonotonic Multi-Context Systems LOG-IC 2009 13 / 36
Example (ctd)
Reconsider multi-context system M = (C1 , C2 ):
• kb1 = { unhappy ⊃ revision } (Classical Logic)
• kb2 = { good : accepted/accepted } (Default Logic)
• br1 = { unhappy ← (2 : work ) }
• br2 = { work ← (1 : revision),
good ← not (1 : unhappy ) }
M has two equilibria:
• E1 = (Th({unhappy , revision}), Th({work })) and
• E2 = (Th({unhappy ⊃ revision}), Th({good, accepted}))
G. Brewka (Leipzig) Nonmonotonic Multi-Context Systems LOG-IC 2009 14 / 36
Groundedness
• Problem: self-justifying beliefs
• Present e.g. in Autoepistemic Logic:
L rich ⊃ rich
• Other nonmonotonic formalisms are “grounded,” e.g.
• Reiter’s Default Logic,
• logic programs with Answer Set Semantics (Gelfond & Lifschitz,
91),
• ...
• Equilibria of MCSs are possibly ungrounded, e.g. E1 ; may be
wanted or not
• Groundedness can be achieved by restriction to special class of
nonmonotonic formalisms
• Generalization of Gelfond/Lifschitz reduct applied to belief state
G. Brewka (Leipzig) Nonmonotonic Multi-Context Systems LOG-IC 2009 15 / 36
3. Argumentation Context Systems
Motivation
• Nonmonotonic MCS neglect 2 important aspects:
• What if information provided by different contexts is conflicting?
• What if a context does not only add information?
• ACS provide an answer to these questions.
• Focus on a particular type of local reasoners: argumentation
frameworks.
• Goals achieved by introducing mediators.
G. Brewka (Leipzig) Nonmonotonic Multi-Context Systems LOG-IC 2009 16 / 36
Argumentation Context Systems: Background
• Work based on Dung’s widely used abstract argumentation
frameworks (AFs).
• Abstract approach: arguments un-analyzed, attacks represented
in digraph; can be instantiated in many different ways.
• Argument accepted unless attacked by an accepted argument.
• Semantics single out appropriate accepted sets of arguments:
• Grounded extension: accept unattacked args, eliminate args
attacked by accepted args, continue until fixpoint reached.
• Preferred extension: maximal conflict free set which attacks each of
its attackers.
• Stable extension: conflict-free set of arguments which attacks each
excluded argument.
• (Value based) preferences captured: modify original AF.
G. Brewka (Leipzig) Nonmonotonic Multi-Context Systems LOG-IC 2009 17 / 36
Limitations
• No distinction between arguments, meta-arguments, sources of
arguments etc.
• Our interest: additional structure and modularity
• Benefits:
• A handle on complexity and diversity
• A natural account of multi-agent argumentation
• Explicit means to model meta-argumentation
G. Brewka (Leipzig) Nonmonotonic Multi-Context Systems LOG-IC 2009 18 / 36
Motivating Example: Conference Reviewing
Consider model of the paper review process for a conference
• Hierarchy consisting of PC chair, area chairs, reviewers, authors.
• PC chair determines review criteria.
• Area chairs make sure reviewers make fair judgements and
eliminate unjustified arguments from reviews.
• Authors give feedback on reviews. Information flow thus cyclic.
• Reviewers exchange arguments in peer-to-peer discussion.
• Area chairs generate a consistent recommendation.
• PC chair takes recommendations as input for final decision.
Need a flexible framework allowing for cyclic structures
encompassing different information integration methods.
G. Brewka (Leipzig) Nonmonotonic Multi-Context Systems LOG-IC 2009 19 / 36
The Short Story
A1
A (lonely) Dung style argumentation framework.
G. Brewka (Leipzig) Nonmonotonic Multi-Context Systems LOG-IC 2009 20 / 36
The Short Story
Med1
A1
An argumentation module equipped with a mediator,
can “listen" to other modules and “talk" to A1 :
sets an argumentation context using a context
definition language; handles inconsistency.
G. Brewka (Leipzig) Nonmonotonic Multi-Context Systems LOG-IC 2009 21 / 36
The Short Story
Med3 Med4
A3 A4
Med1 Med2
A1 A2
An argumentation context system.
G. Brewka (Leipzig) Nonmonotonic Multi-Context Systems LOG-IC 2009 22 / 36
More Background
Inconsistency Handling
Use 4 methods for picking consistent subset of
(F1 , . . . , Fn ), Fi set of formulas (details irrelevant)
Preference based Majority based
Credulous sub maj
Skeptical subsk , majsk
Bridge Rules
Only rules referring to single other module needed
⇒ bridge rules ordinary logic programming rules:
s ← p1 , . . . , pj , not pj+1 , . . . , not pm (1)
head s a context expression (to be defined), body atoms
arguments pi from a parent argumentation framework.
G. Brewka (Leipzig) Nonmonotonic Multi-Context Systems LOG-IC 2009 23 / 36
Context Based Argumentation
First step: a language for representing context:
a, b args; v , v 0 values; r ∈ {skep, cred}; s ∈ {grnd, pref , stab}
arg(a) / arg(a) a is a valid (invalid) argument
att(a, b) / att(a, b) (a, b) is a valid (invalid) attack
a>b a is strictly preferred to b
val(a, v ) the value of a is v
v > v0 value v is strictly better than v 0
mode(r ) the reasoning mode is r
sem(s) the chosen semantics is s
Context C: set of context expressions.
G. Brewka (Leipzig) Nonmonotonic Multi-Context Systems LOG-IC 2009 24 / 36
Contexts as Modifiers
What are extensions of AF A under context C?
C transforms A to AC by (in)validating args and
attacks appropriately using new argument def:
d
a b c
Let C = {arg(a), val(b, v1 ), val(d, v2 ), v1 > v2 , c > b}. AC is:
def d
a b c
G. Brewka (Leipzig) Nonmonotonic Multi-Context Systems LOG-IC 2009 25 / 36
Acceptable Extensions
• Transformation handles statements except mode and sem.
• These are captured in the following definition:
Acceptable C-extension
Let sem(s) ∈ C. S ⊆ AR is an acceptable C-extension for A, if
either
1 mode(skep) ∈ C and S ∪ {def} is the intersection of all s-
extensions of AC , or
2 mode(cred) ∈ C and S ∪ {def} is an s-extension of AC .
Proposition: Definitions “do the right thing"
G. Brewka (Leipzig) Nonmonotonic Multi-Context Systems LOG-IC 2009 26 / 36
Mediators
• Context information may come from parent modules
• Need to “translate" abstract arguments to context statements ⇒
use bridge rules
• Also need to guarantee consistency ⇒
use consistency method, potentially preferences on parents
Mediator
A1 and A2 , . . . , Ak AFs. A mediator for A1 based on A2 , . . . , Ak is
Med = (E1 , R2 , . . . , Rk , choice)
where
• E1 is a set of context statements for A1 ;
• Ri (2 ≤ i ≤ k ) is a set of bridge rules for A1 based on Ai ;
• choice ∈ { sub , sub sk , , maj, majsk }, where is a strict
partial order on {1, . . . , k }.
G. Brewka (Leipzig) Nonmonotonic Multi-Context Systems LOG-IC 2009 27 / 36
Mediators, ctd.
Mediator determines consistent context based on
• arguments accepted by parents and
• chosen consistency method.
Acceptable context
Let Med = (E1 , R2 , . . . , Rk , choice) be a mediator for A1 based on
A2 , . . . , Ak . A context C for A1 is acceptable wrt. sets of arguments
S2 , . . . , Sk of A2 , . . . , Ak , if C is a choice-preferred set for
(E1 , R2 (S2 ), . . . , Rk (Sk )).
Here Ri (Si ) are the context statements derivable from Si under Ri :
{h | h ← a1 , ..., aj , not b1 , ..., not bn ∈ Ri , each ai ∈ Si , each bm 6∈ Si }
G. Brewka (Leipzig) Nonmonotonic Multi-Context Systems LOG-IC 2009 28 / 36
The Framework
• Put the pieces together
• Take collection of context based argument systems
• Add mediator to each of them
• Connect them in an arbitrary graph
• Use mediator to generate consistent context
(Argumentation) Module
Pair M = (A, Med), where A is an AF and Med a mediator for A
based on some AFs A1 , . . . , Ak .
Argumentation context system
Set F = {M1 , . . . , Mn } of modules Mi = (Ai , Medi ) such that each
Medi is based only on AFs Ai1 , . . . , Aik , where ij ∈ {1, . . . , n}
(self-containedness).
G. Brewka (Leipzig) Nonmonotonic Multi-Context Systems LOG-IC 2009 29 / 36
The Module Graph
Module graph
Digraph G(F) = (F, E) where Mj → Mi in E iff Aj is among the
Ai1 , . . . , Aik Medi is based on.
Med3 Med4
A3 A4
Med1 Med2
A1 A2
An argumentation context system
G. Brewka (Leipzig) Nonmonotonic Multi-Context Systems LOG-IC 2009 30 / 36
Acceptable States
• For each module, pick accepted set of arguments and context
• Must fit together: chosen arguments acceptable given context,
chosen context acceptable given chosen arguments of parents
Acceptable state
State S of F: maps each Mi = (Ai , Medi ) to S(Mi ) = (Acci , Ci ),
Acci a set of arguments of Ai , Ci a context for Ai .
S acceptable, if
• each Acci is an acceptable Ci -extension for Ai , and
• each Ci is an acceptable context for Medi wrt. all Accj for
which G(F) has an arc Mj → Mi .
G. Brewka (Leipzig) Nonmonotonic Multi-Context Systems LOG-IC 2009 31 / 36
Some Results
• Existence of acceptable states
• Not guaranteed, even without stable semantics and default negation
• Guaranteed if F hierarchic and sem(stab) does not occur in any
mediator.
• Complexity
• Reasoning tasks related to acceptable states intractable in general.
• Deciding whether ACS F has some acceptable state Σp3 -complete.
• Has lower complexity depending on the various parameters and
graph structure.
• F hierarchic, modules use grounded semantics and either sub or
maj ⇒ acceptable state computable in polynomial time.
• Complexity of C-extensions dominated by underlying
argumentation framework.
G. Brewka (Leipzig) Nonmonotonic Multi-Context Systems LOG-IC 2009 32 / 36
4. Generalizing MCS and ACS: An Outlook
• Advantage of MCS: cover large variety of logics
• Advantage of ACS: mediators
1 include consistency mechanisms integrating conflicting views
2 allow for KB updates which are more general than just adding
premises
3 can even select the adequate semantics
• Want best of both worlds: Mediator-based MCS
G. Brewka (Leipzig) Nonmonotonic Multi-Context Systems LOG-IC 2009 33 / 36
4. Generalizing MCS and ACS: An Outlook
• Advantage of MCS: cover large variety of logics
• Advantage of ACS: mediators
1 include consistency mechanisms integrating conflicting views
2 allow for KB updates which are more general than just adding
premises
3 can even select the adequate semantics
• Want best of both worlds: Mediator-based MCS
G. Brewka (Leipzig) Nonmonotonic Multi-Context Systems LOG-IC 2009 33 / 36
4. Generalizing MCS and ACS: An Outlook
• Advantage of MCS: cover large variety of logics
• Advantage of ACS: mediators
1 include consistency mechanisms integrating conflicting views
2 allow for KB updates which are more general than just adding
premises
3 can even select the adequate semantics
• Want best of both worlds: Mediator-based MCS
G. Brewka (Leipzig) Nonmonotonic Multi-Context Systems LOG-IC 2009 33 / 36
MMCS: Context Formalisms
• Need updatable logics.
• Need parameterized semantics.
Context formalism
A context formalism L is a tuple
L = (KBL , BSL , SemL = {ACCiL }, UL , updL }
• KBL and BSL as before.
• SemL a set of possible semantics, each ACCiL : KBL → 2BSL
assigns to a KB a set of acceptable belief sets.
• UL a context language with adequate notion of consistency.
• updL : KBL × 2UL → KBL × SemL assigns to a KB and a set
of context formulas an updated KB and a semantics.
G. Brewka (Leipzig) Nonmonotonic Multi-Context Systems LOG-IC 2009 34 / 36
MMCS: The Rest
• Acceptable belief set: E acceptable for KB under context C:
E ∈ ACCi (KB 0 ) where upd(KB, C) = (KB 0 , ACCi ).
• Mediator: as in ACS, bridge rules with heads taken from UL and
bodies elements of belief sets of parents.
• MMCS: as in ACS, modules consisting of a KB of particular
formalism and corresponding mediator connecting to parents.
• Acceptable state: context and belief set for each module such that
• belief set acceptable under chosen context,
• context acceptable given belief sets of parents.
G. Brewka (Leipzig) Nonmonotonic Multi-Context Systems LOG-IC 2009 35 / 36
5. Conclusions
• Account of recent/ongoing work on multi-context systems.
• Part I: heterogeneous nonmonotonic systems.
• Part II: generalized updates and consistency mechanisms, focus
on argumentation.
• Part III: try to capture best of both worlds.
• MCS special case (cum grano salis): updates extensions, no
consistency handling
• ACS special case: all formalisms Dung AFs
• MMCS very general and flexible; cover wide range of applications
involving multi-agent meta-reasoning.
THANK YOU!
G. Brewka (Leipzig) Nonmonotonic Multi-Context Systems LOG-IC 2009 36 / 36
5. Conclusions
• Account of recent/ongoing work on multi-context systems.
• Part I: heterogeneous nonmonotonic systems.
• Part II: generalized updates and consistency mechanisms, focus
on argumentation.
• Part III: try to capture best of both worlds.
• MCS special case (cum grano salis): updates extensions, no
consistency handling
• ACS special case: all formalisms Dung AFs
• MMCS very general and flexible; cover wide range of applications
involving multi-agent meta-reasoning.
THANK YOU!
G. Brewka (Leipzig) Nonmonotonic Multi-Context Systems LOG-IC 2009 36 / 36
5. Conclusions
• Account of recent/ongoing work on multi-context systems.
• Part I: heterogeneous nonmonotonic systems.
• Part II: generalized updates and consistency mechanisms, focus
on argumentation.
• Part III: try to capture best of both worlds.
• MCS special case (cum grano salis): updates extensions, no
consistency handling
• ACS special case: all formalisms Dung AFs
• MMCS very general and flexible; cover wide range of applications
involving multi-agent meta-reasoning.
THANK YOU!
G. Brewka (Leipzig) Nonmonotonic Multi-Context Systems LOG-IC 2009 36 / 36
5. Conclusions
• Account of recent/ongoing work on multi-context systems.
• Part I: heterogeneous nonmonotonic systems.
• Part II: generalized updates and consistency mechanisms, focus
on argumentation.
• Part III: try to capture best of both worlds.
• MCS special case (cum grano salis): updates extensions, no
consistency handling
• ACS special case: all formalisms Dung AFs
• MMCS very general and flexible; cover wide range of applications
involving multi-agent meta-reasoning.
THANK YOU!
G. Brewka (Leipzig) Nonmonotonic Multi-Context Systems LOG-IC 2009 36 / 36
5. Conclusions
• Account of recent/ongoing work on multi-context systems.
• Part I: heterogeneous nonmonotonic systems.
• Part II: generalized updates and consistency mechanisms, focus
on argumentation.
• Part III: try to capture best of both worlds.
• MCS special case (cum grano salis): updates extensions, no
consistency handling
• ACS special case: all formalisms Dung AFs
• MMCS very general and flexible; cover wide range of applications
involving multi-agent meta-reasoning.
THANK YOU!
G. Brewka (Leipzig) Nonmonotonic Multi-Context Systems LOG-IC 2009 36 / 36
5. Conclusions
• Account of recent/ongoing work on multi-context systems.
• Part I: heterogeneous nonmonotonic systems.
• Part II: generalized updates and consistency mechanisms, focus
on argumentation.
• Part III: try to capture best of both worlds.
• MCS special case (cum grano salis): updates extensions, no
consistency handling
• ACS special case: all formalisms Dung AFs
• MMCS very general and flexible; cover wide range of applications
involving multi-agent meta-reasoning.
THANK YOU!
G. Brewka (Leipzig) Nonmonotonic Multi-Context Systems LOG-IC 2009 36 / 36
5. Conclusions
• Account of recent/ongoing work on multi-context systems.
• Part I: heterogeneous nonmonotonic systems.
• Part II: generalized updates and consistency mechanisms, focus
on argumentation.
• Part III: try to capture best of both worlds.
• MCS special case (cum grano salis): updates extensions, no
consistency handling
• ACS special case: all formalisms Dung AFs
• MMCS very general and flexible; cover wide range of applications
involving multi-agent meta-reasoning.
THANK YOU!
G. Brewka (Leipzig) Nonmonotonic Multi-Context Systems LOG-IC 2009 36 / 36
5. Conclusions
• Account of recent/ongoing work on multi-context systems.
• Part I: heterogeneous nonmonotonic systems.
• Part II: generalized updates and consistency mechanisms, focus
on argumentation.
• Part III: try to capture best of both worlds.
• MCS special case (cum grano salis): updates extensions, no
consistency handling
• ACS special case: all formalisms Dung AFs
• MMCS very general and flexible; cover wide range of applications
involving multi-agent meta-reasoning.
THANK YOU!
G. Brewka (Leipzig) Nonmonotonic Multi-Context Systems LOG-IC 2009 36 / 36