《非单调推理.ppt》由会员分享，可在线阅读，更多相关《非单调推理.ppt（15页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、非非单调推理推理n在经典逻辑中，我们经常考虑这样一个推理：从前提“所有的人都是有死的”和“苏格拉底是人”推出结论“苏格拉底是有死的”。这样的推理我们称为演绎推理。此类推理有一种非常本质的逻辑特性-单调性单调性（monotonicity）。这种性质表示增加前提不会影响原有结论的推出。n 经典逻辑（其代表是命题逻辑和一阶逻辑）只研究单调推理，所以我们称此类逻辑为单调逻辑（monotonic logics）。n然而在人类日常推理中，因为根据的信息往往是不完全的，所以推理出的结论往往是可错的。n比如我们通常认为“鸟会飞”，知道“tweety是一只鸟”的话就会推出结论“tweety会飞”。n一旦我们又有
2、了新的证据，例如，增加前提“tweety是一只鸵鸟”，我们知道通常“鸵鸟是不会飞的”，则先前的结论“tweety会飞”就不合理了。也就是说，增加前提使原先推出的结论推不出。n换句话讲，这样的推理不具单调性。我们称这种性质为非单调性（非单调性（nonmonotonicity），称这样的推理为非单调推理（非单调推理（nonmonotonic reasoning），），有时也称为常识推理常识推理(commonsense reasoning)。n目前，关于非单调推理的研究已成为人工智能领域中的一个热点，在著名的人工智能会议上，如IJCAI、AAAI、KR及NMR等，均集中地反映了其研究的进展。尤其是进
3、入80年代后，各主要发达国家（如美国、欧洲和日本等）的著名大学和研究机构均投入了相当的力量，自AI杂志1980年出版该领域研究专集以来，大量关于常识推理的研究论文出现在主要的计算机及人工智能学术刊物中，引起国内外学术界的广泛重视。nStanford大学的McCarthy教授也曾说过：人工智能最关键的问题是常识和推理近十年来在常识和推理研究方面，形式化非单调推理的发展是重要的一步。n目前对于非单调推理的研究一般有两种途径：n一种方法认为经典逻辑对于研究非单调推理明显有不足的地方，因此最好是建立新的语义机制跟建立新的语义机制跟逻辑系统逻辑系统。在此基础上进行非单调推理的研究以解决一些问题，例如Re
4、iter缺省逻辑（default logic）和Moore的自认识逻辑（autoepistemic logic），还有扩充逻辑程序(extended logic program)。n另一种观点与此正好相反，坚持这种观点的人认为，在经典逻辑框架下研究非单调推理经典逻辑框架下研究非单调推理是完全可以的，关键是怎么使用经典逻辑。例如闭世界假设CWA，McCarthy的限定推理（Circumscription）和Poole提出的假设推理（default reasoning）。nMcCarthy提出的限定推理限定推理采用了上述的第二种途径，他的基本做法就为经典逻辑增加新的公理，以达到限定的目的。举个例子
5、，如果我们说人类能够思考，通过新的公理，我们可以得出只有人类可以思考的结论。n而Poole的假假设推理推理也是坚持在经典逻辑的框架内可以进行非单调问题的研究，他的主要想法是推理时增加假设知识来弥补知识的不完全。增加的缺省知识不与现有的事实产生矛盾，即与现有的事实一致。非单调推理的一些问题n名声最大的也许是McDermott和他的合作者提出的所谓耶鲁射击问题耶鲁射击问题。这个问题乍听起来非常简单，大意如下：n某甲在时刻t1是活着的。n某乙在时刻t2t1把子弹装进枪膛。n某乙在时刻t3t2举枪对某甲射击。n问题：某甲在时刻t4t3还活着吗？n由于他们在研究此问题并发表文章时正在耶鲁大学工作，所以此
6、问题被称为耶鲁射击问题。n非单调推理的一般形式是：“如果没有意外，一般情况下某事实成立”。Reiter提出了以下的悖论：n通常情况下，基督徒是和平主义者；共和党人不是和平主义者。尼克松(Nixon)既是基督徒又是共和党人，他是和平主义者还是非和平主义者?n蝙蝠是鸟还是兽？n凤凰寿，百鸟朝贺，惟蝙蝠不至。凤责之曰：“汝居吾下，何踞傲乎？”蝠曰：“我有足，属于兽，贺汝何用？”一日，麒麟生诞，蝠亦不至，麟亦责之。蝠曰：“我有翼，属于禽，何以贺与？”（明.冯梦龙笑府)n彩票悖彩票悖论(lottery paradox)n根据常识推理，彩票往往是不会中奖的。所以张三买的彩票不会中奖，李四买的彩票不会中奖n
7、合取就得到：所有人买的彩票都不会中奖n这与有人会中奖矛盾！n为了解决非单调推理中遇到的问题，Poole认为有两种方法比较有前景：一种是基于概率的基于概率的非单调推理非单调推理，另一种是基于论据的非单调推理基于论据的非单调推理。n基于概率的非单调推理与基于概率的归纳推理有密切的联系：基于概率的非单调推理与基于概率的归纳推理有密切的联系：n尼克松是一个共和党人（命题p1），而且尼克松也是一个基督徒（命题p2），已知基督徒通常是和平主义者（命题p3），共和党人通常是非和平主义者，问他是和平主义者还是非和平主义者?n我们用如下的规则来表示上述所说，并根据经验引入适当的概率：np1 1 （表示尼克松是共
8、和党人）np2 1（表示尼克松是基督徒）np2 p3 0.8 （表示基督徒是和平主义者的概率是0.8）np1 p3 0.5 （表示共和党人是非和平主义者的概率是0.5）这样来看，尼克松有0.8的概率是和平主义者，有0.5的概率是非和平主义者，取最大值，因此认为尼克松倾向于是和平主义者。n基于基于论据的方法据的方法：n在知识库中，如果发现某个知识错了，那么就得撤消此错误知识，同时还得撤消依赖于此知识成立的知识。而要做到这一点，就必须研究知识间的依赖关系。n真值维护系统（TMS）完成类似的任务。Doyle实现了一个基于论据的真值维护系统（JTMS）。在JTMS中，知识用节点表示，节点包含节点编号、
9、节点内容（该节点对应的命题）以及该节点的论据集。在JTMS中，记录所有可信的节点。节点之间的依赖关系可以用与或树技术来解决。Kleer克服了JTMS的一些不足，实现了一个基于假设的真值维护系统（ATMS）。给定规则，ATMS可以根据该规则更新命题间的依赖关系。n我目前也在思考基于依赖关系的知识库的生成及其应用，可参见一个基于依赖关系的知识库。n我认为还要反思经典逻辑的推理机制：我认为还要反思经典逻辑的推理机制：n对于经典推理形式的置疑：一个真命题为任何命题所蕴涵，一个假命题则蕴涵任何命题；n经典命题的实质蕴涵，会出现蕴涵怪论模态逻辑的严格蕴涵，还是有严格蕴涵怪论相干逻辑与衍推逻辑，用相干蕴涵来
10、代替实质蕴涵n相干推理相干推理n张清宇主编：逻辑哲学九章（第三章蕴涵），江苏人民出版社，2004年n冯棉：相干逻辑与衍推逻辑，上海人民出版社，1993年n重点要找到相干逻辑在计算机科学领域的应用，或者编程实现相干逻辑的判定性。理想的论文结构理想的论文结构：综述创新程序综述创新程序n综述部分综述部分：同学们在阅读文献的时候，就要有整理材料的习惯。n创新部分创新部分：在前人的基础上，提出自己的一些新思路，说明自己方法的优点所在，及其应用可能。n程序程序：用程序来验证自己思路的有效性和正确性，程序的话，界面不重要，主要是用C语言或者C+编程，重要的是时间复杂性要小，一般要在多项式时间内。如果是指数时间，在算法复杂性里经常称为难解问题，也就是当问题规模较大时用计算机来计算速度很慢的意思，不实用。n参考文献参考文献：一般要参考具有学术价值的论文和书籍，可以顺着一篇好的文章顺藤摸瓜，找找它引用的文献，再找找引用它的文献。大家可以充分利用图书馆和电子资源：n论文：ACM，IEEE，西文电子期刊如Artificial Intelligence，作者主页，中国期刊网，图书馆期刊。Google搜索论文。n书籍：图书馆，国家图书馆