逻辑、计算和博弈 (6).pdf

《逻辑、计算和博弈 (6).pdf》由会员分享，可在线阅读，更多相关《逻辑、计算和博弈 (6).pdf（69页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、Dynamic Logics of Belief ChangeAbstractThis chapter gives an overview of current dynamic logics that describebelief update and revision,both for single agents and in multi-agent set-tings.We employ a mixture of ideas from AGM belief revision theory anddynamic-epistemic logics of information-driven a

2、gency.After describingthe basic background,we review logics of various kinds of beliefs basedon plausibility models,and then go on to various sorts of belief changeengendered by changes in current models through hard and soft infor-mation.We present matching complete logics with dynamic-epistemicrec

3、ursion axioms,and develop a very general perspective on belief changeby the use of event models and priority update.The chapter continueswith three topics that naturally complement the setting of single steps ofbelief change:connections with probabilistic approaches to belief change,long-term tempor

4、al process structure including links with formal learningtheory,and multi-agent scenarios of information flow and belief revisionin games and social networks.We end with a discussion of alternative ap-proaches,further directions,and windows to the broader literature,whilelinks with relevant philosop

5、hical traditions are discussed throughout.Human cognition and action involve a delicate art of living dangerously.Beliefs are crucial to the way we plan and choose our actions,even thoughour beliefs can be very wrong and refuted by new information.What keepsthe benefits and dangers in harmony is our

6、 ability to revise beliefs as the needarises.In this chapter,we will look at the logical structure of belief revision,andbelief change generally.But before we can do this,we need background of twokinds:(a)the pioneering AGM approach in terms of postulates governing beliefrevision which showed that t

7、his process has clear formal structures regulatingits behavior,and(b)the basics of dynamic-epistemic logics of information flowwhich showed that change of attitudes for agent and the events triggering suchchanges are themselves susceptible to exact logical analysis.This is what wewill provide in the

8、 first two sections of this chapter.With this material in place,Section 3 will then start our main topic,the logical treatment of belief revision.11Basics of belief revisionThe AGM account of belief revision.What happens when an agent is confrontedwith a new fact that goes against her prior beliefs?

9、If she is to accept thenew fact and maintain a consistent set of beliefs,she will have to give upsome of her prior beliefs.But which of her old beliefs should she give up?Moregenerally,what policy should she follow to revise her beliefs?As we will seein this chapter,several answers to this question

10、are possible.The standardanswer in the literature says that our agent should accept the new fact and atthe same time maintain as many as possible of her old beliefs without arrivingat a contradiction.Making this more precise has been the driving force behindBelief Revision Theory.Standard Belief Rev

11、ision Theory,also called AGMtheory(after the pioneering authors Alchourr on,G ardenfors and Makinson)hasprovided us with a series of“rationality conditions”,that are meant to preciselygovern the way in which a rational agent should revise her beliefs.AGM theory.The AGM theory of belief revision is b

12、uilt up from three basicingredients:1)the notion of a theory(or“belief set”)T,which is a logicallyclosed set of sentences,.belonging to a given language L;2)the input ofnew information,i.e.,a syntactic formula;and 3)a revision operator whichis a map associating a theory T to each pair(T,)consisting

13、of a theory Tand an input sentence.The construct T is taken to represent the agentsnew theory after learning.Hence T is the agents new set of beliefs,giventhat the initial set of beliefs is T and that the agent has learnt that.Expansion.The AGM authors impose a number of postulates or rationalitycon

14、ditions on the revision operation.To state these postulates,we first need anauxiliary belief expansion operator+,that is often considered an unproblematicform of basic update.Belief expansion is intended to model the simpler casein which the new incoming information does not contradict the agents pr

15、iorbeliefs.The expansion T+of T with is defined as the closure underlogical consequence of the set T .AGM provides a list of 6 postulatesthat exactly regulate the expansion operator,but instead of listing them herewe will concentrate on belief revision.However,later on,we will see that evenexpansion

16、 can be delicate when complex epistemic assertions are added.Revision.Now,belief revision goes beyond belief expansion in its intricacies.Itis regulated by the following famous set of postulates:2AGM Belief Revision Postulates:(1)ClosureT is a belief set(2)Success T (3)InclusionT T+(4)PreservationIf

17、 6 T,then T+T (5)VacuityT is inconsistent iff(6)ExtensionalityIf ,then T =T (7)SubexpansionT ()(T )+(8)SuperexpansionIf 6 T ,thenT ()(T )+.These postulates look attractive,though there is more to them than meetsthe eye.For instance,while the success postulate looks obvious,in our laterdynamic-episte

18、mic logics,it is the most controversial one in this list.In a log-ical system allowing complex epistemic formulas,the truth value of the targetformula can change in a revision step,and the Success Postulate would recom-mend incorporating a falsehood into the agents theory T.One importantcase in whic

19、h this can occur is when an introspective agent revises her beliefs onthe basis of new information that refers to beliefs or higher-order beliefs(i.e.,beliefs about beliefs).Because the AGM setting does not incorporate“theoriesabout theories”,i.e.,it ignores an agents higher-order beliefs,this probl

20、em isside-stepped.All the beliefs covered by AGM are so-called factual beliefs aboutontic facts that do not refer to the epistemic state of the agent.However anylogic for belief change that does allow explicit belief-operators in the language,will have to pay attention to success conditions for comp

21、lex updates.A final striking aspect of the Success Postulate is the heavy emphasis placedon the last incoming proposition,which can abruptly override long accumu-lated earlier experience against.This theme,too,will return later when wediscuss connections with formal theories of inductive learning.Co

22、ntraction.A third basic operation considered in AGM is that of belief con-traction T,where one removes a given assertion from a belief set T,whileremoving enough other beliefs to make underivable.This is harder than ex-pansion,since one has to make sure that there is no other way within the newtheor

23、y to derive the target formula after all.And while there is no unique way toconstruct a contracted theory,AGM prescribes the following formal postulates:(1)ClosureT is a belief set(2)Contraction(T )T(3)Minimal ActionIf 6 T,then T =T(4)SuccessIf 6 then 6(T )(5)RecoveryIf T,then T (T )+(6)Extensionali

24、tyIf ,then T =T (7)Min-conjunctionT T T ()(8)Max-conjunctionIf 6 T (),then T ()T 3Again,these postulates have invited discussion,with Postulate 5 being the mostcontroversial one.The Recovery Postulate is motivated by the intuitive principleof minimal change,which prescribes that a contraction should

25、 remove as littleas possible from a given theory T.The Levi-Identity.The three basic operations on theories introduced here areconnected in various ways.A famous intuition is the Levi-identityT =(T )+saying that a revision can be obtained as a contraction followed by an expansion.An important result

26、 in this area is a theorem by G ardenfors which showsthat if the contraction operation satisfies postulates(1-4)and(6),while theexpansion operator satisfies its usual postulates,then the revision operationdefined by the Levi-identity will satisfy the revision postulates(1-6).Moreover,if contraction

27、satisfies the seventh postulate,then so does revision,and likewisefor the eight postulate.Conditionals and the Ramsey Test.Another important connection runs betweenbelief revision theory and the logic of conditionals.The Ramsey Test is a keyingredient in any study of this link.In 1929,F.P.Ramsey wro

28、te:“If two people are arguing If A,will B?and are both in doubt asto A,they are adding A hypothetically to their stock of knowledgeand arguing on that basis about B;so that in a sense If A,B andIf A,B are contradictories.”Clearly,this evaluation procedure for conditional sentences A B uses thenotion

29、 of belief revision.G ardenfors formalized the connection with the RamseyTest as the following statement:A B TiffB T Awhich should hold for all theories T and sentences A,B.In a famous impossi-bility result,he then showed that the existence of such Ramsey conditionals isessentially incompatible with

30、 the AGM postulates for the belief revision oper-ator.The standard way out of G ardenfors impossibility result is to weakenthe axioms of,or else to drop the Ramsey test.Most discussions in this line are cast in purely syntactic terms,and in asetting of propositional logic.However,in section 3 we wil

31、l discuss a semanticperspective which saves much of the intuitions underlying the Ramsey Test.This is in fact a convenient point for turning to the modal logic paradigmin studying belief revision.Like we saw with belief expansion,it may help tofirst introduce a simpler scenario.The second part of th

32、is introductory sectionshows how modal logics can describe information change and its updates1in1Our use of the term“update”in this chapter differs from a common terminology of“beliefupdate”in AI,due to Katsuno and Mendelzon.The latter notion of update refers to beliefchange in a factually changing

33、world,while we will mainly(though not exclusively)considerepistemic and doxastic changes but no changes of the basic ontic facts.4what agents know.The techniques found in this realm will then be refined andextended in our later treatment of belief revision.2Modal logics of belief revisionStarting in

34、 the 1980s,several authors have been struck by analogies betweenAGM revision theory and modal logic over suitable universes.Belief and relatednotions like knowledge could obviously be treated as standard modalities,whilethe dynamic aspect of belief change suggested the use of ideas from Propositiona

35、lDynamic Logic of programs or actions to deal with update,contraction,andrevision.There is some interest in seeing how long things took to crystallizeinto the format used in this chapter,and hence we briefly mention a few ofthese proposals before introducing our final approach.Propositional dynamic

36、logic over information models.Propositional DynamicLogic(PDL)is a modal logic that has both static propositions and programsor actions.It provides dynamic operators that one can use to reasonabout what will be true after an action takes place.One special operator ofPDL is the“test of a proposition”(

37、denoted as?):it takes a proposition into a program that tests if the current state satisfies.Using this machineryover tree-like models of successive information states ordered by inclusion,in1989,van Benthem introduced dynamic operators that mirror the operations ofAGM in a modal framework.One is th

38、e addition of (also called“update”,denoted as+),interpreted as moving from any state to a minimal extensionsatisfying.Other operators included“downdates”moving back to the firstpreceding state in the ordering where is not true.Revision was defined viathe Levi-identity.In a modification of this appro

39、ach by de Rijke in the 1990s,these dynamic operators were taken to work on universes of theories.Dynamic doxastic logic over abstract belief worlds.These developments inspiredSegerberg to develop the logical system of Dynamic Doxastic Logic(DDL),which operates at a higher abstraction level for its m

40、odels.DDL combines aPDL dynamics for belief change with a static logic with modalities for knowledgeK and belief B.The main syntactic construct in DDL is the use of the dynamicmodal operator which reads“holds after revision with”,where denotes a relation(often a function)that moves from the current

41、world of themodel to a new one.Here and were originally taken to be factual formulasonly,but in later versions of DDL they can also contain epistemic or doxasticoperators.This powerful language can express constructs such as B statingthat after revision with the agent believes.In what follows,we wil

42、l takea more concrete modal approach to DDLs abstract world,or state,changesinvolved in revision but a comparison will be given in Section 9.1.Degrees of belief and quantitative update rules.In this paper,we will mainlyfocus on qualitative logics for belief change.But historically,the next stepwere

43、quantitative systems for belief revision in the style of Dynamic Epistemic5Logic,where the operations change current models instead of theories or singleworlds.Such systems were proposed a decade ago,using labelled operators toexpress degrees of belief for an agent.In 2003,van Ditmarsch and Labuscha

44、gnegave a semantics in which each agent has associated accessibility relations corre-sponding to labeled preferences,and a syntax that can express degrees of belief.Revision of beliefs with new incoming information was modeled using a binaryrelation between information states for knowledge and degre

45、es of belief.A morepowerful system by Aucher in 2003 had degrees of belief interpreted in Spohnranking models,and a sophisticated numerical“product update rule”in thestyle of Baltag,Moss and Solecki(BMS,see Section 5.2 below)showing howranks of worlds change under a wide variety of incoming new info

46、rmation.Belief expansion via public announcement logic.An early qualitative approach,due to van Ditmarsch,van der Hoek and Kooi in 2005,relates AGM beliefexpansion to the basic operation of public announcement in Dynamic EpistemicLogic.The idea is to work with standard relational modal models M for

47、belief(in particular,these need not have a reflexive accessibility relation,since beliefscan be wrong),and then view the action of getting new information as apublic announcement that takes M to its submodel consisting only of its-worlds.Thus,an act of belief revision is modeled by a transformation

48、of somecurrent epistemic or doxastic model.The system had some built-in limitations,and important changes were made later by van Benthem and Baltag&Smetsto the models and update mechanism to achieve a general theory but it wason the methodological track that we will follow now for the rest of this c

49、hapter.Public announcement logic.To demonstrate the methodology of Dynamic Epis-temic Logic to be used in this chapter,we explain the basics of Public An-nouncement Logic(PAL).The language of PAL is built up as follows:=p|Ki|!Here we read the Ki-modality as the knowledge of agent i and we read thedy

50、namic construct!as“holds after the public announcement of”.Wethink of announcements!as public events where indubitable hard informationthat is the case becomes available to all agents simultaneously,whether bycommunication,observation,or yet other means.In what follows,we define andstudy the corresp