表格模板-第五讲经典人工智能技术—知识表示、推理与搜索77 精品.ppt

《表格模板-第五讲经典人工智能技术—知识表示、推理与搜索77 精品.ppt》由会员分享，可在线阅读，更多相关《表格模板-第五讲经典人工智能技术—知识表示、推理与搜索77 精品.ppt（77页珍藏版）》请在第一文库网上搜索。

1、 人工智能课程改革与建设人工智能课程改革与建设 第五讲第五讲 经典人工智能技术经典人工智能技术 推理与搜索推理与搜索 Traditional Technology of AI 中南大学中南大学 刘丽珏刘丽珏2011本讲授课要点本讲授课要点讲授基于符号主义的经典人工智能技术。符号主义的研究以知识为核心。知识的表示是问题求解的基础，但单纯介绍知识表示容易让学生感觉枯燥，且无法直观理解其作用，可考虑将表示与求解放在一起讲授，例如：谓词逻辑表示与推理技术状态空间表示与搜索技术宜用问题带出内容，通过问题引发学生思考：“这样的问题机器能解决吗？可以怎么做？”以增加兴趣。引言引言经典人工智能经典人工智能出色

2、的老式人工智能（Good Old Fashioned AI，GOFAI）哲学家约翰.豪格兰德一个用规则和事实来程序化的高速数字计算机可一个用规则和事实来程序化的高速数字计算机可能表现出智力行为能表现出智力行为图灵人类是借助事实与规则来产生智力行为的经典人工智能技术主要以符号表示、符号处理为实现智能的主要手段，推理和搜索是其中的核心技术 5.1自动推理证明自动推理证明机器真的能够自动推理吗？自动推理证明的发展史谓词逻辑消解原理5.1.1 机器真的能够自动推理吗？机器真的能够自动推理吗？5个房间问题有5间不同颜色的房间，每间住个不同国籍的人，每人有自己喜欢的饮料、香烟和宠物。已知信息：1.英国人在

3、红房间中2.西班牙人有一条狗3.挪威人住在左边第一间房里4.黄房间中的人在抽库尔斯牌香烟5.抽切斯菲尔德牌香烟的人是养了一只狐狸的人的邻居6.挪威人住在蓝房间隔壁7.抽温斯顿牌香烟的人有一只蜗牛8.抽幸运牌香烟的人喝橘子汁9.乌克兰人喝茶10.日本人抽国会牌香烟11.抽库尔斯牌烟的房间在有匹马的房间隔壁12.绿房间中的人喝咖啡13.绿房间在白房间的左边14.中间房间的人喝牛奶问题：斑马在哪个房间中？问题：斑马在哪个房间中？哪个房间中的人喝水？哪个房间中的人喝水？自动推理示例自动推理示例：5个房间问题房间号12345颜色国籍香烟饮料宠物挪威人牛奶咖啡库尔斯马英国人水橘子汁西班牙幸运狗茶乌克兰日本

4、人国会温斯顿切斯菲尔德蜗牛狐狸斑马3.挪威人住在左边第一间房里6.挪威人住在蓝房间旁边14.中间房间的人喝牛奶12.绿房间中的人喝咖啡14.绿房间在白房间的左边1.英国人在红房间中4.黄房间中的人在抽库尔斯牌香烟11.抽库尔斯牌烟的房间在有匹马的房间隔壁8.抽幸运香烟的人喝橘子汁9.乌克兰人喝茶2.西班牙人有一条狗8.抽幸运牌香烟的人喝橘子汁9.乌克兰人喝茶10.日本人抽国会牌香烟7.抽温斯顿牌香烟的人有一只蜗牛5.抽切斯菲尔德牌香烟的人的是养了一只狐狸的人的邻居机器真的能自动完机器真的能自动完成这样的推理吗？成这样的推理吗？自动推理示例自动推理示例求 解5.1.2 自动推理证明的发展史自动推

5、理证明的发展史笛卡尔莱布尼茨自动证明的提出笛卡尔、莱布尼茨（17世纪）萌发了用机械系统实现定理证明的想法把一类数学问题当作一个整体，建立统一的证明过程，按照规定的程序步骤机械地进行下去，在有限步骤之后判断出定理的正确性 由于传统的兴趣和应用的价值，初等几何问题的自动求解成为数学机械化的研究焦点。 希尔伯特希尔伯特20世纪初，在他的名著几何基础中给出了一条可以对一类几何命题进行判定的定理。希尔伯特对命题的要求太高，当时仅能解决很少的一类几何定理的机器证明，却是历史上第一个关于某类几何命题的机械化检验方法的定理。塔斯基塔斯基（波兰）1950年，证明了：“一切初等几何和初等代数范围的命题都可以用机械

6、方法判定”为几何定理的机器证明开拓了一条利用代数方法的途径方法太复杂，即使用高速计算机也证明不了稍难的几何定理艾伦.纽厄尔纽厄尔,西蒙和肖1956年, 发表了论文逻辑理论机(LTM)认为LTM不仅是计算机智力的有力证明，也是人类认知本质的证明1957年开发了最早的AI程序设计语言IPL语言1960年，成功地合作开发了“通用问题求解系统” GPS (General Problem Solver)赫伯特.西蒙王浩王浩美籍华裔王浩（19211995）数学家、逻辑学家、计算机科学家、哲学家。简历生于山东济南市1943年毕业于西南联合大学数学系1945年毕业于清华大学研究生院哲学系1948年获哈佛大学哲

7、学博士学位1954-1956年在牛津大学任高级教职1961-1967年任哈佛大学教授1967-1991年任洛克菲勒大学逻辑学教授20世纪50年代初当选美国科学院院士及不列颠科学院外籍院士。王浩王浩美籍华裔王浩（19211995）l953年起开始计算机理论与机器证明的研究。他敏锐地感觉到被认为过分讲究形式的精确又十分繁琐而无任何实际用处的数理逻辑，可以在计算机领域发挥极好的作用。1959年，采用“王浩算法”用计算机证明了罗素 、 怀海德的巨著数学原理中的几百条有关命题逻辑的定理，仅用了 9 分钟（vs 10年），宣告了用计算机进行定理证明的可能性，第一次明确提出“走向数学的机械化走向数学的机械化

8、”。王浩美籍华裔王浩1983 年，获国际人工智能联合会 “数学定理机械证明里程碑奖”，表彰他在数学定理机械证明研究领域的开创性贡献。1972年以后，王浩数次回国讲学。1985年兼任北京大学教授；1986年兼任清华大学教授。新中国成立之初，公开发表演说表示对新中国的支持。1972年回国时曾受周恩来总理的接见。1973年撰写了访问中国的沉思，赞美新中国，被报纸与杂志广泛刊载。为此，他受到了许多攻击。他热爱祖国和中华民族的精神值得人们学习与称道。1977年，美国年轻的数学家阿佩尔等在高速电子计算机上耗费 1200 小时的计算时间，证明了著名的“四色定理” ，人类百年悬而未决的疑问最终被圆满解决了。这

9、一成就轰动一时，成为机器定理证明的一个典范。著名数学家吴文俊中国科学院数学与系统科学研究院研究员、中国科学院院士、第三世界科学院院士1919年出生于上海1940年毕业于交通大学数学系1949年获法国国家博士学位1951年回到祖国，任北京大学数学系的教授1956年与华罗庚、钱学森同台领取国家自然科学奖一等奖；38岁时当选为中国科学院学部委员1993年获得陈嘉庚数理科学奖1994年获首届求是科技基金会杰出科学家奖1997 年获Herbrand自动推理杰出成就奖2001年获国家最高科学技术奖 吴文俊1984 年出版专著几何定理机器证明的基本原理，利用中国古典数学的成就，提出具有中国特色的定理自动证明

10、方法，被国际上誉为“吴氏方法”。1985 年发表论文“关于代数方程组的零点”吴文俊消元法，即“吴氏公式”。2010年5月4日，国际小行星中心发布公报通知国际社会，将国际永久编号为第7683号的小行星永久命名为“吴文俊星”。 如何实现自动推理证明？如何实现自动推理证明？逻辑方法是自动证明中常用的方法如何进行逻辑推理？推理的过程怎样？怎么实现自动推理？推理示例马普尔小姐探案阿加莎.克里斯蒂侦探小说改编的电视剧“马普尔小姐探案”马克和约尔是孪生兄弟谁是作案者：马克或约尔？马普尔小姐的结论谁是马克谁是约尔？马普尔小姐的推理过程观察结果马克是右撇子，手表戴在左手约尔是左撇子，手表戴在右手推理规则如果手表

11、戴在左手，那么他是马克如果手表戴在右手，那么他是约尔事实事实规则规则人类的推理可以理解语义人类的推理可以理解语义机器如何进行这样类似的推理？机器如何进行这样类似的推理？需要将推理的过程与理解分割开，将其形式化需要将推理的过程与理解分割开，将其形式化结论只是穿着不同衣服的同一个人约尔推理的一般形式已知：事实1，事实2， 如果 事实1 那么 结论1 如果 事实2 那么 结论2 .得到：结论1，结论2，将事实与规则等抽象出来，不涉及具体内容，借助一些符号来表示，推理过程可以被形式化 P：某已知事实 PQ：如果 P 那么 Q结论：Q这个过程不需要直觉和解释符号与形式语言自然语言不适合计算机处理例：小王

12、不方便接电话，他方便去了需要一种无歧义，方便存储和表达的形式化符号表征体系数理逻辑命题逻辑谓词逻辑5.1.3 谓词逻辑谓词逻辑什么是谓词？原子命题中刻画个体的性质或个体间关系的成分谓词逻辑是一种形式语言 是目前为止能够表达人类思维活动规律的一种最精确的语言 接近自然语言，又方便存入计算机处理最早应用于人工智能中表示知识 适合于表示事物的状态、属性、概念等，也可用来表示事物间确定的因果关系Terms（项） a.一个常量是项 b.一个变量是项c.如果f是一个n元函数符号，t1,t2,.,tn是项，则f(t1,t2,.,tn)也是项 d.所有项都是由规则(a)(b)(c)产生的 Atoms（原子公式

13、 ）如果P是一个n元谓词符号，t1,t2,.,tn是项，则P(t1,t2,.,tn) 是一个原子公式，其他任何表达式都不是原子公式 WFF（合适公式）a.An atom is WFFb.如果F和G是WFF，则F，FG，FG，FG，FG都是WFFc.如果F是WFF，x是自由变量则(x)F，(x)F都是WFFd.WFF仅由有限次使用规则(a)(b)(c)产生。 例man(smith) smith是人between(albert, susan, david) albert在susan与david之间 (x)(man(x)mortal(x) 人都会死 (x)(man(x)clever(x) 有的人聪明

14、推理是如何进行的？推理过程多种多样例1：如果今天不下雨，我就去你家今天没有下雨例2：小王说他下午或者去图书馆或者在家休息小王没去图书馆计算机如何选择？鲁滨逊美国数学家鲁滨逊提出消解原理（1965年）基本的出发点：要证明一个命题为真都可以通过证明其否命题为假来得到将多样的推理规则简化为一个消解消解P QP RQ R消解式消解式亲本子句亲本子句消解式是亲本子消解式是亲本子句的逻辑结论句的逻辑结论消解只能在仅含否定和析取联接词的公式（子句）间进行必须先把公式化成规范的形式（范式，子句集）析取联接词，类似析取联接词，类似“或或”例1：小王说他下午或者去图书馆或者在家休息小王没去图书馆R小王下午去图书馆

15、S小王下午在家休息R SRS例2：如果今天不下雨，我就去你家 PQ今天没有下雨 PP Q含变量的消解例：苏格拉底论断凡人都会死. x (Man (x) Mortal (x)苏格拉底是人.Man (Socrates)如何得到结论：苏格拉底会死. Mortal(Socrates)要完成消解还面临几个问题“”和“ ”必须消去Man (x) Mortal (x) Man (x) Mortal “”怎么办？ 化为子句集化为子句集 置换与合一置换与合一如果能消去“”，Man (x) 和Man (Socrates)也不能构成互补对，形式不一样，怎么办？置换与合一要把消解推理规则推广到含有变量的子句，必须找到

16、一个作用于亲本子句的置换，使亲本子句含有互补文字置换（Substitution）置换是形为t1/x1, t2/x2, ., tn/xn的一个有限集xi是互不相同的变元，ti是项 用ti代换xi，不允许ti与xi相同，也不允许变元xi循环出现在另一个tj中a/x,f(b)/y,w/z f(a)/x, b/y, t/x g(y)/x,f(x)/ys=z/x,w/y =P(x,f(y),B) s =P(z,f(w),B)置换与合一合一（Unification)寻找项对变量的置换，以使两表达式一致的过程。如果一个置换s作用于表达式集Ei的每个元素，则我们用Ei s来表示置换例的集。我们称表达式集Ei是可合一的（unifiable）,s为合一者（unifier）mgu(most general unifier, 最一般合一者)若s为Fi的任一合一者，又存在某个置换s，使得 s=gs则称g为Fi的最一般(最简单的)合一者，记作mgu。mgu is unique F=P(x,f(y),B) s=A/x,B/y g=B/y s=A/x gs=s相关概念文字：原子公式及其否定统称为文字子句集(1)子句定