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

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

1、 LOGIC,COMPUTATION AND GAMES Probability&Logic puzzle occurs in many different forms:The Jailer Glasses The Quizmaster Discussion Answer 1:no difference,Answer 2:Door 2 has become more probable,you should switch.The right solution is to switch?Better:analyze what is involved.puzzle occurs in many fo

2、rms:The Jailer,Three Glasses Bayes Law:Two Computations P(Door 2|Door 3)=P(Door 3|Door 2)P(Door 2)/P(Door 3)=(1 x 1/3)/2/3=1/2 P(Door 2|QM opens 3)=P(QM opens 3|Door 2)P(Door 2)/P(QM opens 3)=(1 x 1/3)/1/2=2/3 What is the right computation?Bayes Law does not tell.Tree Representation epistemic model

3、probability tree Issues represent the problem update with the right information only then:compute infer does the text give enough information?role of protocol for the quizmaster what is the update mechanism?what logic fits with this?are the probabilities over-kill,given the qualitative decision prob

4、lem“Switch”?Logic and Probability,Three Approaches combine logical and probabilistic systems (often in practice)find qualitative base logic underneath probability,then derive probability measure(de Finettis program)find probability underneath logic,then derive logical notions as qualitative shorthan

5、d (Locke on belief,several philosophical logicians today)Epistemic Probabilistic Logic,1 models M=(W,R,V)as usual,we will ignore agent indices finite models!Note:Linear Inequalities the linear inequalities in the syntax may look surprising,but they are useful when proving a completeness theorem wher

6、e we have to produce a suitable probability measure.With our later dynamic update logic PDEL with events,another test is that the linear inequality format is just what is needed to make the recursion axioms work.In combined logics of quantifiers and counting(ongoing work)integer programming problems

7、 with inequalities turn out just the right counterpart for basic logical reasoning.Epistemic Probabilistic Logic,2 for simplicity,assume that all worlds in an epistemic equivalence class assign the same probability measure.I.e.,agents know their probability distribution add:s I t Epistemic Probabili

8、stic Logic,3 Theorem (Halpern)Epistemic probability logic is axiomatizable and decidable.The restriction to the rationals may not be essential.Theorem(Tarski)The first-order theory of the reals(R,0,1,+,)is decidable.PS about combining knowledge and probability probability 1 and knowledge:are they th

9、e same,or not?language:iterated knowledge vs.iterated probability Probabilistic PAL,Recursion Axioms PAL update M|on epistemic probability model M defined just as in Week 1,except that the probability measure is normalized to s in M|M,s|=valid recursion law the version on p.148 of LDII mistakenly dr

10、opped need to extend this to conditional probability:HW 3 Theorem Probabilistic epistemic PAL is complete.Aside:PAL and Bayes Law !P()=k looks like P(|)=k but they are not the same Fact Bayes Law fails for the PAL modality see posted LDII book,p.150 Explanation truth values after update for complex

11、epistemic formulas the equivalence only holds for factual formulas Similar phenomena in recentwork on probabilistic reasoning with indexical expressions(“now”,“here”,”the president”)Recent News:PAL and Probabilistic Update new paper just seen for a conference make the PAL updates themselves probabil

12、istic give information that with certain force/probability q and adjust the probability values of worlds appropriately this seems more like the Jeffrey Update of a later slide,or it might be a simple form of Wednesdays PDEL Occurrence Probability PAL cannot analyze the Quizmaster yet at least not in

13、 a natural manner that fits our tree diagram QMs action of Opening Door 3 has different probabilities depending on the world where it is performed:if the car is behind Door 1,1 if the car is behind Door 2 information about this occurrence probability typically comes from the protocol,any p 1 in case

14、 of Door 1 suffices Tree Representation Once More update rule for the probability of a history,take product of the probabilities for the events along the history (and renormalize w.r.t.all surviving histories)Update Through Events start initial epistemic probability model,prior probabilities (these

15、could themselves have come from learning history)update step events can happen,creating the next layer of history M x E,events have preconditions on worlds where they occur (precondition of!Is ,or think of concrete actions)preconditions viewed probabilistically:occurrence probabilities P MxE(s,e)=PM

16、(s)x preM(s,e)dynamic logic system plus yet more complex updates:Wednesday QM in Cognition A B C My friend wears glasses Who is my friend?high percentage of respondents:B what could be said:“glasses”,“hat”Gricean conversational explanation probabilistic statistical percentage,individual degree of be

17、lief?general issue:equivalence of probabilistic scenarios Outlook:Finite vs Infinite we assumed finite models this is a huge simplification compared with standard probability theory where the passage to the infinite is crucial,e.g.,with the distinction knowledge/probability 1.problem Lift the theory

18、 of this week to the infinite case Note:There are well-developed interfaces of logic and probability where the infinite case is central,e.g.,algorithmic randomness Individuals vs.Groups,Discrete vs Continuous related issues,though not the same from our focus on single agent behavior to long-term sta

19、tistical group behavior Example:interface our agent logics for belief change with Markov chain models for opinion diffusion in groups/networks discrete vs continuous dynamics our recursion axioms are like discrete difference equations,logic of continuous information dynamics/differential equations?O

20、utlook:Natural Language Why is the puzzle stated in natural language?Or is crucial information only given in context(protocol,etc.)Can we get the representation just from NLP/formal semantics?Or are additional problem-oriented representations needed?John McCarthy vs the linguists/logicians Replacement views of NL by logic/math have never worked Why do even the exact sciences keep a mixture of natural and formal languages?(Staal on artificial languages in history)more sophisticated views of strengths/weakness of both