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