人工智能-非单调推理1课件

非单调推理陈志华主要内容1.缺省理论2.界限理论3.正确性维持理论前言单调推理加进系统的新知识（信念）必须与已有的知识（信念）相一致，不会引起矛盾。随着运行时间的推移，系统内含的结论有增无减

传统的逻辑系统实际上做的是单调推理真实世界充斥了不完全信息和不断变化的状况，在解决复杂问题的过程中，要求不断应用并不保证正确的假设假设可作为推理的依据，但在推理过程中，随着新事物的出现，可能到头来会发现原先所作的假设不正确，应予删除，从而造成推理的非单调性因此，新知识（事实）的加入会引起已有知识（假设以及基于假设的推理结果）的删除。单调推理新证据的出现，不会证明原有结论错误，结论单调增加非单调推理新证据会否定原来推出的结论，结论可能会减少非单调推理，更符合现实，符合人类的认识规律非单调推理的使用场合（1）不完全信息的出现要求缺省推理（2）世界是不断变化的，即使能获得关于问题求解的全部知识，也不能持久。解决的办法是取消那些已经变得不精确的知识，而代之以另一些更精确的知识。（3）产生一个问题的完全解答或许要求关于部分解答的暂时性假设。这些假设可能不正确，需要在以后发现时加以修改或删除，从而形成非单调推理。

现在观察一个为三个忙人安排会议时间的问题求解任务。先假设会议在某个具体日期举行，比如星期三，并将此假设作为部分解答存储于知识库然后再查这一天三人是否有相容的会议参与时间，若出现冲突，则取消该假设，改用另一天作为假设的会议日期这是一个非单调推理1.缺省理论缺省推理的形式定义设：x：某个证据

y:默认x为真时的某结论；则缺省推理包含以下三种情形：

定义1：若不知道x为假，则有结论y定义2：若不能证明x为假，则有结论y；定义3：若不能在某个给定的时间期限内证明x为假，则有结论y。这三个定义汇总起来意指：若无x为假的证据，就认为y是真。

例子在美国第一次应邀去朋友家作客，应带礼物，但不了解朋友喜欢什么样的礼物，这时可以根据常识进行猜测--鲜花总是受欢迎的。注：最有可能的选择。意指，若已知在一组可选事物中必有一个为真，则在缺乏完全信息的情况下，应该选择最有可能的一个1.1缺省规则的形式令A(x)为先决条件；Bi(x)为默认条件；C(x)为结论；M为模态算子，表示：无法证明…为假或假定…是正确的缺省规则可表示为：含义：如果先决条件A(x)成立，且没有证据证明Bi(x)为假，则结论C(x)成立推理思想：非假即真；不是假的就认为是真的例：利用非单调推理表示“一般来说，鸟都会飞”缺省规则适合表示：大多数P是Q，或大多数P具有Q性质1.2分类规范缺省半规范缺省不规范缺省规范缺省默认条件与结论相同，由先决条件可以直接推理出结论形式如下：例：同学们大都爱游戏半规范缺省默认条件：规则形式：含义：除D(x)外，由先决条件A(x)的成立，可以推导出结论B(x)的成立例子除了企鹅以外，大多数的鸟都会飞；除了鹦鹉以外，一般动物都不会讲话2.界限理论现实当中，完成一件事情通常都会遇到很多限制条件，而且罗列出所有限制通常既不可能，也无必要通常人们不会考虑到大量的限制，只有没有发现存在限制，就认为可行例子：一周后飞往北京；周末爬黄山界限理论不考虑大量不确定的限制因素或条件这些限制条件如果不能证明是真的，那就是假的，不需考虑界限理论的思想不是真的（已知的），就认为是假的只有存在的，才是真的；不知道的，都认为是假的界限理论的表示方法表示方法：引入特定谓词Ab表示异常例：一般鸟都会飞表示为：不是异常的鸟都会飞再添加两条规则：

3.正确性维持系统在非单调推理中，一旦有新的知识出现，就有可能要对原先得到的结论进行修正，甚至抛弃如何删除错误的结论，从而保持正确性？多伊尔在1979年建立和提出了正确性维持系统TMS(TruthMaintenanceSystem)

TMS的原理TMS在程序所产生的各个命题中，保持命题间的相容性一旦发现命题出现不相容（矛盾），TMS就调用推理机制，回溯找到不相容的根源修正由这一根源以前推理得到的所有命题，从而消除不相容，维持系统的正确性在TMS中，每个命题或规则称为节点。节点的状态包括：IN:该命题被认为是真OUT:该命题不被认为是真每个节点可以带有一个证实表（也可没有），证实表包括两种形式：支持表条件证明支持表:(SL(IN节点表)(OUT节点表))只有当“IN节点表”中所有节点的当前状态为IN,且“OUT节点表”中所有节点的当前状态为OUT，它所证实的节点是IN状态，有效IN表和OUT表均为空的节点为原始证据节点，所证实的节点是IN条件证明:(CP(结论)(IN假设)(OUT假设))只有当“IN假设”中所有节点的当前状态为IN,且“OUT假设”中所有节点的当前状态为OUT，结论节点为IN状态，这时条件证实有效例子设有下列节点：(1)现在是冬天(SL()())IN;(2)天气是寒冷的(SL(1)(3))(3)天气是温暖的OUT分析：节点2的IN表中只有节点1，且状态为IN;OUT表中只有节点3，且状态为OUT因此，节点2的状态为IN节点2的含义是：如果现在是冬天(对应IN表中含有节点1)且没有天气是温暖的证据(对应OUT表中含有节点3)则可以得出结论“天气是寒冷的”当推理程序得到了新证据，而且这个新证据与某个节点发生矛盾时，程序就会自动产生一个矛盾节点：矛盾SL((…)(…)),且状态置为IN,然后调用TMSTMS的工作过程当TMS遇到一个矛盾节点为IN，则唤醒面向从属关系的回溯,找出并删除当前的一个假设，即让该假设的状态为OUT,从而使得矛盾节点为OUT步骤1:从矛盾节点开始，寻找它的基础节点，设为A1,A2,…,An，一般都放在矛盾节点的IN表中步骤2:从A1开始，令此节点状态为OUT步骤3:进行正确性维持检查，如果无法维持所有节点的IN/OUT状态，则撤销A1，取出下一个节点A2,返回步骤2如果A1,A2,…,An的任何一个或多个为OUT都无法维持所有节点的IN/OUT状态，则说明这是一个不可解决的矛盾

例子--会议安排问题节点命题支持表状态１TIME(M)=9:00(SL()(2))IN２TIME(M)≠9:00OUT３ROOM(M)=813(SL()(4))IN４ROOM(M)≠813OUT推理程序在它处发现9点钟813房间已被其它事务占用，于是生成节点5节点5矛盾(SL(1,3)())INTMS的工作过程：首先找出节点5的基础节点1,3,所以将节点1的状态改为OUT相应的，节点1的支持表(SL()(2))中，节点2的状态为IN节点5的状态为OUT，矛盾消除处理后，各节点的状态如下：节点命题支持表状态１TIME(M)=9:00(SL()(2))OUT２TIME(M)≠9:00(SL()(5))IN３ROOM(M)=813(SL()(4))IN４ROOM(M)≠813OUT５矛盾(SL(1,3)())OUT如果推理过程又发现节点2，3矛盾，于是又生成节点6如下：6矛盾(SL(2,3)())INTMS的工作过程找出节点6的基础节点2,使得节点2的状态改为OUT，节点2的支持表为(SL()(5))，这样就必须使得矛盾节点5的状态改为IN,从而产生矛盾原因分析：上次不应该选基础节点2，再尝试改选节点3为基础节点将节点3的状态改为OUT，并按顺序调整其它节点的状态最后各节点的状态如下表节点命题支持表状态1TIME(M)=9:00(SL()(2))OUT2TIME(M)≠9:00(SL()(5))IN3ROOM(M)=813(SL()(4))OUT4ROOM(M)≠813(SL()(6))IN5矛盾(SL(1,3)())OUT6矛盾(SL(2,3)())OUT例子假设John被人杀害，推理程序要找到凶手。根据它的知识库，首先考虑Tom:节点命题支持表状态命题含义１Guilty(Tom)OUTTom是凶手２Innocent(Tom)OUTTom清白

由于这两个节点都没有得到证实，支持表SL为空。推理程序继续推理，发现Tom有谋杀John的动机，于是产生节点3作为原始证据，状态为IN节点命题支持表状态3Has_Motives(Tom)(SL()())IN推理程序再继续推理，找到一条规则“任何有杀人动机且没有被证实是清白的人是嫌疑犯”，由节点2,3生成新节点4节点命题支持表状态含义4Suspect(Tom)(SL(3)(2))INTom是嫌疑犯推理程序再继续推理，发现了Tom不在现场的证据，于是生成新节点5节点命题支持表状态含义5Has_Alibi(Tom)(SL()())INTom不在现场推理程序应用规则“如果某人不在现场，则不是嫌疑犯”，于是节点4和5产生矛盾，从而生成矛盾节点6节点命题支持表状态含义6ContradictionSL((4,5)())IN矛盾TMS的工作过程首先找节点6的基础节点4和5令节点4为OUT,则节点3为OUT或者节点2为IN因为节点3是原始证据，必须为IN,因此只能将节点2改为IN状态，即TOM是清白的小结在非单调推理中，原有的结论有可能被新的证据推翻缺省理论不是假的，就认为是真的界限理论不是真的，就认为是假的TMS可以找到冲突的根源并消除关于小讲座围绕人工智能领域，做5分钟PPT。作为平时加分：4-10倍加分（根据演讲情况）每团队1-3人，成员都要讲。12周-15周上课的部分时间，课前报名内容多样，形式吸引人人工智能的软件演示和介绍人工智能的应用人工智能的技术点、知识点介绍人工智能领域的研究团队、公司介绍……评分标准内容扣题，吸引人PPT简洁表述流畅、思路清晰有亮点分值A(加分额度：8-10)B(6-7)C(4-5)人工智能

是一门交叉学科

脑科学认知科学心理学语言学逻辑学哲学计算机科学人工智能什么是人工智能人工智能的定义可以分为两部分，即“人工”和“智能”。关于什么是“智能”？智能需要具备的特征？具有感知能力（系统输入）:

机器视觉，机器听觉，图像语音识别……具有记忆与思维能力：思维是智能的根本原因，思维是一个动态的过程。思维分为：逻辑思维，形象思维和顿悟思维。具有学习能力及自适应能力：适应环境的变换、积累经验的能力

具有行为能力（系统输出）：对外界的智能化反应早期判断是否有智能的方法———图灵测试英国数学家阿兰·图灵(AlanTuring)提出了现称为“图灵测试”(TuringTest)的方法。简单来讲,图灵测试的做法是:让一位测试者分别与一台计算机和一个人进行交谈(当时是用电传打字机),而测试者事先并不知道哪一个是人,哪一个是计算机。如果交谈后测试者分不出哪一个被测者是人,

哪一个是计算机,则可以认为这台被测的计算机具有智能。

Turing测试存在的问题“图灵测试”没有规定问题的范围和提问的标准仅反映了结果的比较，无涉及思维过程没指出是什么人争论：通过了图灵检验的电脑就具备思维能力了么？测试主持人被测机器被测人中文屋子约翰·西尔勒的中文屋子假设是说:有一台计算机阅读了一段故事并且能正确回答相关问题,这样这台计算就通过了图灵测试。而西尔勒设想将这段故事和问题改用中文描述(因为他本人不懂中文),然后将自己封闭在一个屋子里,代替计算机阅读这段故事并且回答相关问题。描述这段故事和问题的一连串中文符号只能通过一个很小的缝隙被送到屋子里。西尔勒则完全按照原先计算机程序的处理方式和过程(如符号匹配、查找、照抄等)对这些符号串进行操作,然后把得到的结果即问题答案通过小缝隙送出去。西尔勒也得到了问题的正确答案。西尔勒认为尽管计算机用这种符号处理方式也能正确回答问题,并且也可通过图灵测试,但仍然不能说计算机就有了智能。

人工智能的发展概况

1.形成期（1956--1970年）AI诞生于一次历史性的聚会(Dartmouth人工智能夏季研讨会)时间：1956年夏季地点：美国达特茅斯(Dartmouth)大学目的：为使计算机变得更“聪明”，或者说使计算机具有智能发起人：麦卡锡(J.McCarthy），Dartmouth的年轻数学家、计算机专家，后为MIT教授明斯基(M.L.Minsky），哈佛大学数学家、神经学家，后为MIT教授洛切斯特(N.Lochester)，IBM公司信息中心负责人香农(C.E.Shannon)，贝尔实验室信息部数学研究员会议结果：由麦卡锡提议正式采用了“ArtificialIntelligence”这一术语人工智能的发展概况2.形成期（1956----1970年）其他开创性贡献1958年，美籍华人数理逻辑学家王浩在IBM-740计算机上仅用了3-5分钟就证明了《数学原理》命题演算全部220条定理。1965年，费根鲍姆(E.A.Feigenbaum)开始研究化学专家系统DENDRAL，用于质谱仪分析有机化合物的分子结构。1969年召开了第一届国际人工智能联合会议（InternationalJointConferenceonAI，IJCAI），标志着人工智能作为一门独立学科登上了国际学术舞台。此后IJCAI每两年召开一次。1970年《InternationalJournalofAI》创刊。人工智能的发展概况3.暗淡期（1966----1974年）失败的预言给人工智能的声誉造成重大伤害“20年内，机器将能做人所能做的一切”---------1965在博弈方面：塞缪尔的下棋程序在与世界冠军对弈时，5局败了4局。在定理证明方面：发现鲁宾逊归结法的能力有限。当用归结原理证明两个连续函数之和还是连续函数时，推了10万步也没证出结果。在机器翻译方面：发现并不那么简单，甚至会闹出笑话。例如，把“心有余而力不足”的英语句子翻译成俄语，再翻译回来时竟变成了“酒是好的，肉变质了”在问题求解方面：对于不良结构，会产生组合爆炸问题。在神经生理学方面：研究发现人脑有1011-12以上的神经元，在现有技术条件下用机器从结构上模拟人脑是根本不可能的。在英国，剑桥大学的詹姆教授指责“人工智能研究不是骗局，也是庸人自扰”。从此，形势急转直下，在全世界范围内人工智能研究陷入困境、落入低谷。

人工智能的发展概况

4.知识应用期（1970----1988年）整个20世纪80年代，专家系统和知识工程在全世界得到了迅速发展。专家系统为企业等用户赢得了巨大的经济效益。在开发专家系统过程中，许多研究者获得共识，即人工智能系统是一个知识处理系统，而知识获取、知识表示和知识利用则成为人工智能系统的三大基本问题。同时出现新的问题：专家系统本身所存在的应用领域狭窄、缺乏常识性知识、知识获取困难、推理方法单一、没有分布式功能、不能访问现存数据库等问题被逐渐暴露出来。人工智能的发展概况

5.集成发展期（1986年以来）1997年5月11日，由IBM研制的超级计算机“深蓝”首次击败了国际象棋特级大师卡斯帕洛夫。2000年，中国科学院计算所开发出知识发现系统MSMiner。该系统是一种多策略知识发现平台，能够提供快捷有效的数据挖掘解决方案，提供多种知识发现方法。2011年，IBM超级电脑“沃森”亮相美国最受欢迎的智力竞赛节目《危险边缘》战胜该节目两位最成功的选手。人工智能研究形成了三大学派符号主义连接主义行为主义符号主义又称：逻辑主义、心理学派或计算机学派符号主义的实现基础是纽威尔和西蒙提出的物理符号系统假设。该学派认为：人类认知和思维的基本单元是符号，而认知过程就是在符号表示上的一种运算。它认为人是一个物理符号系统,计算机也是一个物理符号系统,因此,我们就能够用计算机来模拟人的智能行为,即用计算机的符号操作来模拟人的认知过程。这种方法的实质就是模拟人的左脑抽象逻辑思维，通过研究人类认知系统的功能机理，用某种符号来描述人类的认知过程，并把这种符号输入到能处理符号的计算机中，就可以模拟人类的认知过程，从而实现人工智能。可以把符号主义的思想简单的归结为“认知即计算”。连接主义又称：仿生学派或生理学派原理：神经网络及神经网络间的连接机制与学习算法。起源：源于仿生学，特别是人脑模型的研究。学派代表：卡洛克、皮茨、Hopfield、鲁梅尔哈特等。连结主义基本理论认为思维基元是神经元，而不是符号处理过程。认为人脑不同于电脑，并提出连结主义的大脑工作模式，用于取代符号操作的电脑工作模式。行为主义又称：进化主义或控制论学派原理：控制论及感知—动作型控制系统认为智能不需要知识、不需要表示、不需要推理；人工智能可以象人类智能一样逐步进化(所以称为进化主义)；智能行为只能在现实世界中与周围环境交互作用而表现出来。催化当今人工智能的出现三大催化剂1）摩尔定律在价格、体积不变的条件下，计算机的计算能力可以不断增长。这就是被人们所熟知的摩尔定律，它以Intel共同创办人GordonMoore命名。GordonMoore从各种形式的计算中获利，包括人工智能研究人员使用的计算类型。数年以