joint work with Thomas Eiter
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)
G. Brewka (Leipzig)
Nonmonotonic Multi-Context Systems LOG-IC 2009
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
G. Brewka (Leipzig)
Nonmonotonic Multi-Context Systems
LOG-IC 2009 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 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
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 Want to capture the “typical” KR logics, including nonmonotonic logics with multiple acceptable belief sets (e.g., Reiter’s Default 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) jACCL(kb)j = 1 and (2) kb ACCL(kb) = fSg, and ACCL(kb0) = fS0g implies S S0.
kb0, G. Brewka (Leipzig)
Nonmonotonic Multi-Context Systems LOG-IC 2009
KB: the sets of prop. -formulas BS: the deductively closed sets of prop. -formulas ACC(kb): Th(kb)
KB: the default theories over BS: the deductively closed sets of -formulas ACC(kb): the extensions of kb
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
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
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 2 KBk fulfills kb [ fsg 2 KBk , (2) each rk 2 f1; : : : ; ng, and (3) each pk is in some belief set of Lrk . G. Brewka (Leipzig)
Nonmonotonic Multi-Context Systems LOG-IC 2009
A Multi-Context System consists of contexts where
M = (C1; : : : ; Cn)
Ci = (Li ; kbi ; bri ), i 2 f1; : : : ; ng, each Li is a logic, each kbi 2 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 Consider the multi-context system M = (C1; C2), where the contexts are different views of a paper by the authors.
C1: C2:
L1 = Classical Logic kb1 = f unhappy br1 = f unhappy revision g (2 : work) g L2 = Reiter’s Default Logic kb2 = f good : accepted=accepted g br2 = f work (1 : revision);
good not (1 : unhappy) g G. Brewka (Leipzig)
Nonmonotonic Multi-Context Systems
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
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 2 Sri (1 i j), and (2) pk 62 Srk (j + 1 k m).
A belief state S = (S1; : : : ; Sn) of M is an equilibrium iff for i 2 f1; : : : ; ng
Si 2 ACCi (kbi [ fhead (r ) j r 2 bri is applicable in Sg): G. Brewka (Leipzig)
Nonmonotonic Multi-Context Systems LOG-IC 2009 Reconsider multi-context system M = (C1; C2): kb1 = f unhappy revision g (Classical Logic) kb2 = f good : accepted=accepted g (Default Logic) br1 = f unhappy
(2 : work) g br2 = f work good (1 : revision); not (1 : unhappy) g M has two equilibria:
E1 = (Th(funhappy; revisiong); Th(fworkg)) and E2 = (Th(funhappy
revisiong); Th(fgood; acceptedg)) G. Brewka (Leipzig)
Nonmonotonic Multi-Context Systems
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 3. Argumentation Context Systems
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 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
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 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
A1
A (lonely) Dung style argumentation framework.
G. Brewka (Leipzig)
Nonmonotonic Multi-Context Systems LOG-IC 2009
First step: a language for representing context: a; b args; v ; v 0 values; r 2 fskep; cred g; s 2 fgrnd ; pref ; stabg
Context C: set of context expressions.
G. Brewka (Leipzig)
Nonmonotonic Multi-Context Systems LOG-IC 2009
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: Let C = farg(a); val(b; v1); val(d ; v2); v1 > v2; c > bg: AC is: G. Brewka (Leipzig)
Nonmonotonic Multi-Context Systems LOG-IC 2009
Transformation handles statements except mode and sem.
These are captured in the following definition:
Let sem(s) 2 C. S AR is an acceptable C-extension for A, if either 1 mode(skep) 2 C and S [ fdefg is the intersection of all sextensions of AC , or 2 mode(cred ) 2 C and S [ fdefg is an s-extension of AC .
Proposition: Definitions “do the right thing" G. Brewka (Leipzig)
Nonmonotonic Multi-Context Systems LOG-IC 2009
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
A1 and A2; : : : ; Ak AFs. A mediator for A1 based on A2; : : : ; Ak is
Med = (E1; R2; : : : ; Rk ; choice) choice 2 f sub ; subsk; ; maj; majsk g, where partial order on f1; : : : ; k g.
G. Brewka (Leipzig)
Nonmonotonic Multi-Context Systems
LOG-IC 2009
Mediator determines consistent context based on arguments accepted by parents and chosen consistency method.
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 : fh j h
a1; :::; aj ; not b1; :::; not bn 2 Ri ; each ai 2 Si ; each bm 62 Si g G. Brewka (Leipzig)
Nonmonotonic Multi-Context Systems
LOG-IC 2009
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 .
Set F = fM1; : : : ; Mng of modules Mi = (Ai ; Medi ) such that each Medi is based only on AFs Ai1; : : : ; Aik , where ij 2 f1; : : : ; ng (self-containedness).
G. Brewka (Leipzig)
Nonmonotonic Multi-Context Systems
Digraph G(F ) = (F ; E ) where Mj ! Mi in E iff Aj is among the Ai1 ; : : : ; Aik Medi is based on.
Med3 A3 Med1 A1
Med4 A4 Med2
A2
An argumentation context system G. Brewka (Leipzig)
Nonmonotonic Multi-Context Systems
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
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
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 maj ) acceptable state computable in polynomial time. or Complexity of C-extensions dominated by underlying argumentation framework.
G. Brewka (Leipzig)
Nonmonotonic Multi-Context Systems Advantage of MCS: cover large variety of logics 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 Advantage of MCS: cover large variety of logics 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 Advantage of MCS: cover large variety of logics 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
Need parameterized semantics.
A context formalism L is a tuple
L = (KBL; BSL; SemL = fACCiLg; 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
Acceptable belief set: E acceptable for KB under context C: E 2 ACCi (KB0) where upd(KB; C) = (KB0; 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
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.
G. Brewka (Leipzig)
Nonmonotonic Multi-Context Systems
LOG-IC 2009 36 / 36
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.
G. Brewka (Leipzig)
Nonmonotonic Multi-Context Systems
LOG-IC 2009 36 / 36
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.
G. Brewka (Leipzig)
Nonmonotonic Multi-Context Systems
LOG-IC 2009 36 / 36
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.
G. Brewka (Leipzig)
Nonmonotonic Multi-Context Systems
LOG-IC 2009 36 / 36
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.
G. Brewka (Leipzig)
Nonmonotonic Multi-Context Systems
LOG-IC 2009 36 / 36
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.
G. Brewka (Leipzig)
Nonmonotonic Multi-Context Systems
LOG-IC 2009 36 / 36
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.
G. Brewka (Leipzig)
Nonmonotonic Multi-Context Systems
LOG-IC 2009 36 / 36
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.