第五讲 经典人工智能技术—知识表示、推理与搜索课件

人工智能课程改革与建设第五讲经典人工智能技术——推理与搜索TraditionalTechnologyofAI中南大学刘丽珏2011本讲授课要点讲授基于符号主义的经典人工智能技术。符号主义的研究以知识为核心。知识的表示是问题求解的基础，但单纯介绍知识表示容易让学生感觉枯燥，且无法直观理解其作用，可考虑将表示与求解放在一起讲授，例如：谓词逻辑表示与推理技术状态空间表示与搜索技术宜用问题带出内容，通过问题引发学生思考：“这样的问题机器能解决吗？可以怎么做？”以增加兴趣。引言——经典人工智能出色的老式人工智能（GoodOldFashionedAI，GOFAI）——哲学家约翰.豪格兰德一个用规则和事实来程序化的高速数字计算机可能表现出智力行为——图灵人类是借助事实与规则来产生智力行为的经典人工智能技术主要以符号表示、符号处理为实现智能的主要手段，推理和搜索是其中的核心技术5.1.1机器真的能够自动推理吗？5个房间问题有5间不同颜色的房间，每间住个不同国籍的人，每人有自己喜欢的饮料、香烟和宠物。已知信息：英国人在红房间中西班牙人有一条狗挪威人住在左边第一间房里黄房间中的人在抽库尔斯牌香烟抽切斯菲尔德牌香烟的人是养了一只狐狸的人的邻居挪威人住在蓝房间隔壁抽温斯顿牌香烟的人有一只蜗牛抽幸运牌香烟的人喝橘子汁乌克兰人喝茶日本人抽国会牌香烟抽库尔斯牌烟的房间在有匹马的房间隔壁绿房间中的人喝咖啡绿房间在白房间的左边中间房间的人喝牛奶问题：斑马在哪个房间中？哪个房间中的人喝水？自动推理示例：5个房间问题房间号12345颜色国籍香烟饮料宠物挪威人牛奶咖啡库尔斯马英国人水橘子汁西班牙幸运狗茶乌克兰日本人国会温斯顿切斯菲尔德蜗牛狐狸斑马3.挪威人住在左边第一间房里6.挪威人住在蓝房间旁边14.中间房间的人喝牛奶12.绿房间中的人喝咖啡14.绿房间在白房间的左边1.英国人在红房间中4.黄房间中的人在抽库尔斯牌香烟11.抽库尔斯牌烟的房间在有匹马的房间隔壁8.抽幸运香烟的人喝橘子汁9.乌克兰人喝茶2.西班牙人有一条狗8.抽幸运牌香烟的人喝橘子汁9.乌克兰人喝茶10.日本人抽国会牌香烟7.抽温斯顿牌香烟的人有一只蜗牛5.抽切斯菲尔德牌香烟的人的是养了一只狐狸的人的邻居机器真的能自动完成这样的推理吗？自动推理示例求解5.1.2自动推理 证明 住所证明下载场所使用证明下载诊断证明下载住所证明下载爱问住所证明下载爱问 的发展史笛卡尔莱布尼茨自动证明的提出笛卡尔、莱布尼茨（17世纪）萌发了用机械系统实现定理证明的想法把一类数学问题当作一个整体，建立统一的证明过程，按照 规定 关于下班后关闭电源的规定党章中关于入党时间的规定公务员考核规定下载规定办法文件下载宁波关于闷顶的规定 的程序步骤机械地进行下去，在有限步骤之后判断出定理的正确性自动证明的发展塔斯基塔斯基（波兰）1950年，证明了：“一切初等几何和初等代数范围的命题都可以用机械方法判定”为几何定理的机器证明开拓了一条利用代数方法的途径方法太复杂，即使用高速计算机也证明不了稍难的几何定理自动证明的发展—王浩王浩美籍华裔王浩（1921—1995）数学家、逻辑学家、计算机科学家、哲学家。简历生于山东济南市1943年毕业于西南联合大学数学系1945年毕业于清华大学研究生院哲学系1948年获哈佛大学哲学博士学位1954-1956年在牛津大学任高级教职1961-1967年任哈佛大学教授1967-1991年任洛克菲勒大学逻辑学教授20世纪50年代初当选美国科学院院士及不列颠科学院外籍院士。自动证明的发展—王浩美籍华裔王浩1983年，获国际人工智能联合会“数学定理机械证明里程碑奖”，表彰他在数学定理机械证明研究领域的开创性贡献。1972年以后，王浩数次回国讲学。1985年兼任北京大学教授；1986年兼任清华大学教授。新中国成立之初，公开发表演说表示对新中国的支持。1972年回国时曾受周恩来总理的接见。1973年撰写了《访问中国的沉思》，赞美新中国，被报纸与杂志广泛刊载。为此，他受到了许多攻击。他热爱祖国和中华民族的精神值得人们学习与称道。自动证明的发展1977年，美国年轻的数学家阿佩尔等在高速电子计算机上耗费1200小时的计算时间，证明了著名的“四色定理”，人类百年悬而未决的疑问最终被圆满解决了。这一成就轰动一时，成为机器定理证明的一个典范。属于中国的自动证明方法—吴方法著名数学家吴文俊中国科学院数学与系统科学研究院研究员、中国科学院院士、第三世界科学院院士1919年出生于上海1940年毕业于交通大学数学系1949年获法国国家博士学位1951年回到祖国，任北京大学数学系的教授1956年与华罗庚、钱学森同台领取国家自然科学奖一等奖；38岁时当选为中国科学院学部委员1993年获得陈嘉庚数理科学奖1994年获首届求是科技基金会杰出科学家奖1997年获Herbrand自动推理杰出成就奖2001年获国家最高科学技术奖属于中国的自动证明方法—吴方法吴文俊1984年出版专著《几何定理机器证明的基本原理》，利用中国古典数学的成就，提出具有中国特色的定理自动证明方法，被国际上誉为“吴氏方法”。1985年发表 论文 政研论文下载论文大学下载论文大学下载关于长拳的论文浙大论文封面下载 “关于代数方程组的零点”—吴文俊消元法，即“吴氏公式”。2010年5月4日，国际小行星中心发布公报通知国际社会，将国际永久编号为第7683号的小行星永久命名为“吴文俊星”。如何实现自动推理证明？逻辑方法是自动证明中常用的方法如何进行逻辑推理？推理的过程怎样？怎么实现自动推理？谁是马克谁是约尔？马普尔小姐的推理过程观察结果马克是右撇子，手表戴在左手约尔是左撇子，手表戴在右手推理规则如果手表戴在左手，那么他是马克如果手表戴在右手，那么他是约尔事实规则人类的推理可以理解语义机器如何进行这样类似的推理？需要将推理的过程与理解分割开，将其形式化结论只是穿着不同衣服的同一个人——约尔符号与形式语言自然语言不适合计算机处理例：小王不方便接电话，他方便去了需要一种无歧义，方便存储和表达的形式化符号表征体系数理逻辑命题逻辑谓词逻辑5.1.3谓词逻辑什么是谓词？原子命题中刻画个体的性质或个体间关系的成分谓词逻辑是一种形式语言是目前为止能够表达人类思维活动规律的一种最精确的语言接近自然语言，又方便存入计算机处理最早应用于人工智能中表示知识适合于表示事物的状态、属性、概念等，也可用来表示事物间确定的因果关系WFF（合适公式）AnatomisWFF如果F和G是WFF，则~F，F∧G，F∨G，F→G，F≡G都是WFF如果F是WFF，x是自由变量则(x)F，(x)F都是WFFWFF仅由有限次使用规则(a)(b)(c)产生。[例]man(smith)smith是人between(albert,susan,david)albert在susan与david之间(x)(man(x)→mortal(x))人都会死(x)(man(x)∧clever(x))有的人聪明推理是如何进行的？推理过程多种多样例1：如果今天不下雨，我就去你家今天没有下雨例2：小王说他下午或者去图书馆或者在家休息小王没去图书馆计算机如何选择？什么叫消解PQ﹁PRQR消解式亲本子句消解式是亲本子句的逻辑结论消解只能在仅含否定和析取联接词的公式（子句）间进行必须先把公式化成 规范 编程规范下载gsp规范下载钢格栅规范下载警徽规范下载建设厅规范下载 的形式（范式，子句集）析取联接词，类似“或”什么叫消解例1：小王说他下午或者去图书馆或者在家休息小王没去图书馆R—小王下午去图书馆S—小王下午在家休息RS﹁RS例2：如果今天不下雨，我就去你家﹁P→Q今天没有下雨﹁PPQ含变量的消解例：苏格拉底论断凡人都会死.x(Man(x)Mortal(x))苏格拉底是人.Man(Socrates)如何得到结论：苏格拉底会死.Mortal(Socrates)要完成消解还面临几个问题“”和“”必须消去Man(x)Mortal(x)Man(x)Mortal“”怎么办？化为子句集置换与合一如果能消去“”，Man(x)和Man(Socrates)也不能构成互补对，形式不一样，怎么办？置换与合一要把消解推理规则推广到含有变量的子句，必须找到一个作用于亲本子句的置换，使亲本子句含有互补文字置换（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)/y}s={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(mostgeneralunifier,最一般合一者)若s为{Fi}的任一合一者，又存在某个置换s'，使得s=gs'则称g为{Fi}的最一般(最简单的)合一者，记作mgu。mguisuniqueF={P(x,f(y),B)}s={A/x,B/y}g={B/y}s’={A/x}gs’=s相关概念文字：原子公式及其否定统称为文字子句集(1)子句定义任何文字的析取式称为子句不包含任何文字的子句称为空子句（空子句是永假的）由子句构成的集合称为子句集例：{P（x）∨Q(x),~P（x，f(x)）∨Q(x,g(x))}化子句集(2)谓词演算公式化为子句式任何一个谓词演算公式可以化为一个子句集合步骤：1)消去蕴涵符号用~A∨B代换A→B2)把非号~移入内层P~x)(=x)P(~P~x)(=x)P(~Q~P~Q)(P~Q~P~Q)(P~"$$"Ù=ÚÚ=Ù3)对变量 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 化改变变量名，使不同的变量不同名4)消去存在量词(具体化Skolemnizing)，两种情况：存在量词不在全称量词的辖域内——用新的个体常量替换受存在量词约束的变元存在量词在全称量词的辖域内Skolem函数，即具体化函数x)Q(x)(x)P(x)($Ú"y)Q(y)(x)P(x)($Ú")a(Q)x(P)x(Ú"Þ)y(Q)y()x(P)x($Ú")y,x,...,x,x(P)y)(x)...(x)(x(n21n21$""")x,...,x,x(f,x,...,x,x(P)x)...(x)(x()n21n21n21"""Þ)x,...,x,x(f,x,...,x,x(P)x)...(x)(x()n21n21n21"""Þ5)化为前束形式把全称量词提到最外层前束形:=(前缀){母式}↑↑全称量词串无量词公式6)把母式化为合取范式7)消去全称量词8)消去连词符号∧，写成子句集9)变量分离标准化改变变量名称，使一个变量符号不出现在一个以上的子句中消解式的定义命题逻辑的消解式设C1与C2是子句集中的任意两个子句，如果C1中的文字L1与C2中的文字L2互补，那么从C1和C2中分别消去L1和L2，并将两个子句中余下的部分析取，构成一个新子句C12，则称这一过程为消解，称C12为C1和C2的消解式，C1，C2为C12的亲本子句例：子句C1=P∨C1'C2=~P∨C2'消解式C12=C1'∨C2'一阶谓词逻辑的消解式设C1与C2是两个没有相同变元的子句，L1和L2分别是C1和C2中的文字，若σ是L1和~L2的最一般合一者，则称C12=(C1σ-{L1σ})∪(C2σ-{L2σ})为C1和C2的二元消解式，L1和L2为消解式上的文字怎么利用消解原理进行证明？消解反演通俗的说就是“反证法”要证命题A恒为真，等价于证﹁A恒为假证明过程否定结论R，得﹁R；把﹁R添加到已知前提集合F中去；把新产生的集合｛﹁R，F｝化成范式；应用消解原理，不断求消解式，直到得到一个表示矛盾的空子句假设：所有不贫穷并且聪明的人都是快乐的，那些看书的人是聪明的。李明能看书且不贫穷，快乐的人过着激动人心的生活。求证：李明过着激动人心的生活。解：先定义谓词：Poor(x)x是贫穷的Smart(x)x是聪明的Happy(x)x是快乐的Read(x)x能看书Exciting(x)x过着激动人心的生活消解反演示例—“激动人心的生活”问题消解反演示例—“激动人心的生活”问题问题谓词表示：“所有不贫穷并且聪明的人都是快乐的”(∀x)((~Poor(x)∧Smart(x))→Happy(x))“那些看书的人是聪明的”(∀y)(Read(y)→Smart(y))“李明能看书且不贫穷”Read(Liming)∧~Poor(Liming)“快乐的人过着激动人心的生活”(∀z)(Happy(z)→Exciting(z))目标“李明过着激动人心的生活”的否定~Exciting(Liming)消解反演示例—“激动人心的生活”问题将上述谓词公式转化为子句集如下：(1)Poor(x)∨~Smart(x)∨Happy(x)(2)~Read(y)∨Smart(y)(3)Read(Liming)(4)~Poor(Liming)(5)~Happy(z)∨Exciting(z)(6)~Exciting(Liming)(结论的否定)消解反演示例—“激动人心的生活”问题~Exciting(Liming)~Happy(z)∨Exciting(z)~Happy(Liming)Happy(x))∨~Smart(x)∨Happy(x)Poor(Liming)∨~Smart(Liming)~Read(y)∨Smart(y)Poor(Liming)∨~Read(Liming)~Poor(Liming)~Read(Liming)Read(Liming)NIL{Liming/z}{Liming/x}{Liming/y}消解原理的局限性消解原理推进了用逻辑方法进行机器证明的研究，使得自动定理证明领域发生了质的变化。但是要求把逻辑公式转化为某种范式，丧失了其固有的逻辑蕴含语义。例如：如果一个人发烧、肚子痛，那么很可能是感染了。x(has_fever(x)∧tummy_pain(x)→has_an_infection(x))has_fever(x)∨tummy_pain(x)∨has_an_infection(x)表达能力的局限性,限制了应用范围后来有许多重要改进：语义归结（消解）、锁归结（消解）、线性归结（消解）等。5.2问题求解与图搜索策略问题求解问题表示解的搜索5.2.1问题求解—什么是问题求解问题求解是人工智能的核心问题之一问题求解的目的机器自动找出某问题的正确解决策略更进一步，能够举一反三，具有解决同类问题的能力是从人工智能初期的智力难题、棋类游戏、简单数学定理证明等问题的研究中开始形成和发展起来的一大类技术求解的手段多种多样其中搜索技术是问题求解的主要手段之一问题表示解的搜索八数码难题在3×3的棋盘，摆有八个棋子，每个棋子上标有1至8的某一数字。棋盘上还有一个空格，与空格相邻的棋子可以移到空格中。12384567初始状态81324567目标状态如何将棋盘从某一初始状态变成最后的目标状态？5.2.1问题求解—问题示例问题示例*怎样找到两点之间的最短路径呢？问题有了，可怎么让计算机知道这些问题呢？5.2.2问题表示——状态空间图例：真空吸尘器的世界假设：吸尘器的世界只有两块地毯大小，地毯或者是脏的，或者是干净的吸尘器能做的动作只有三个{向左(Left)，向右(Right)，吸尘(Suck)}一共有多少种可能的情况？状态状态转换状态之间可以互相转换状态空间图传教士野人问题（Missionaries&Cannibals，MC问题）有三个传教士M和三个野人C过河，只有一条能装下两个人的船，在河的一方或者船上，如果野人的人数大于传教士的人数，那么传教士就会有危险，你能不能提出一种安全的渡河方法呢？状态及其表示状态：问题在某一时刻所处的“位置”，“情况”等根据问题所关心的因素，一般用向量形式表示，每一位表示一个因素0：右岸1：左岸初始状态：(0,0,0)目标状态：(3,3,1)哪些操作能导致状态变化？状态可有多种表示方法：(左岸传教士数,右岸传教士数,左岸野人数,右岸野人数,船的位置)或(左岸传教士数,左岸野人数,船的位置)状态的转换算子（算符，操作符）——使状态发生改变的操作MC问题中的算子将传教士或野人运到河对岸Move-1m1c-lr：将一个传教士(m)一个野人(c)从左岸(l)运到右岸(r)所有可能操作Move-1m1c-lrMove-1m1c-rlMove-2c-lrMove-2c-rlMove-2m-lrMove-2m-rlMove-1c-lrMove-1c-rlMove-1m-lrMove-1m-rl传教士野人问题状态空间图MC5.2.3解的搜索求解过程转化为在状态空间图中搜索一条从初始节点到目标节点的路径问题图的搜索无信息搜索（盲目搜索）有信息搜索（启发式搜索）宽度优先搜索深度优先搜索A算法A*算法图的一般搜索策略图的搜索过程状态：(城市名)算子：常德→益阳益阳→常德益阳汨罗益阳宁乡益阳娄底…？？？？必须记住哪些点走过了必须记住下一步还可以走哪些点深度优先搜索必须记住从目标返回的路径图的搜索过程必须记住哪些点走过了必须记住下一步还可以走哪些点必须记住从目标返回的路径OPEN表(记录还没有扩展的点)CLOSED表(记录已经扩展的点)每个表示状态的节点结构中必须有指向父节点的指针图的一般搜索策略开始把S放入OPEN表OPEN表为空表？把第一个节点(n)从OPEN表移至CLOSED表n为目标节点吗？把n的后继节点放入OPEN表，提供返回节点n的指针修改指针方向重排OPEN表失败成功是是否否盲目搜索不同的搜索策略其搜索的效率是不同的盲目搜索又称无信息搜索宽度优先搜索深度优先搜索特点搜索过程中不使用与问题有关的经验信息不重排OPEN表搜索效率低不适合大空间的实际问题求解是什么影响了搜索的效率？八数码难题1238456712384567（目标状态）（初始状态）操作:空格上移，空格下移，空格左移，空格右移1238456712384123845674123856712384123845671238456712384567678910111213123845675675671123845671238456712384567123845672345宽度优先搜索树12384567271345612384567123845671238456712384567232425262782212384567123845671238456712384567123845671238456712384567141516171819202112384567123845671238456712384567123845671238456712384567123845671238456741238567深度优先搜索树(深度约束=4)123845671238456712384567123845671238456713456278能否预先知道下一步应选择谁？启发式搜索有信息搜索搜索过程中利用与问题有关的经验信息（启发式信息）引入估价函数来估计节点位于解路径上的“希望”，函数值越小“希望”越大搜索过程中按照估价函数的大小对OPEN表排序每次选择估价函数值最小的节点作为下一步考察的节点估价函数是启发式搜索中最重要的因素启发式搜索和盲目搜索的不同就体现在对OPEN表按估价函数的大小排序不同的估价函数所体现出来的搜索效率不同，甚至天差地远不同的估价函数也决定了不同的启发式搜索算法A算法1964年，尼尔逊提出一种算法以提高最短路径搜索的效率，被称为A1算法1967年，拉斐尔改进了A1算法，称为A2算法尼尔逊拉斐尔A算法特征：估价函数f(x)=g(x)+h(x)从起始状态到当前状态x的代价从当前状态x到目标状态的估计代价（启发函数）虽提高了算法效率，但不能保证找到最优解A*算法1968年，彼得.哈特对A算法进行了很小的修改，并证明了当估价函数满足一定的限制条件时，算法一定可以找到最优解估价函数满足一定限制条件的算法称为A*算法f(x)=g(x)+h(x)A*算法的限制条件大于0不大于x到目标的实际代价彼得.哈特利用A*算法求解八数码问题估价函数的定义f(x)=g(x)+h(x)g(x)：从初始状态到x需要进行的移动操作的次数h(x)：？谁更接近目标状态？错放的棋子越少越好！=x状态下错放的棋子数满足限制条件123845671238456781324567h(x)=1h(x)=2h(x)=445631238456712384567123845671+31+51+51238456712384567123845672+42+32+312384567123845673+23+412384567123845673+33+4123845674+181324567123845675+05+25711238460+4752OPEN表CLOSED表估价函数对算法的影响不同的估价函数对算法的效率可能产生极大的影响不同的估价函数甚至产生不同的算法f(x)=g(x)+h(x)h(x)=0：Dijkstra算法，非启发式算法g(x)=0：贪婪搜索，无法保证找到解即使采用同样的形式f(x)=g(x)+h(x)，不同的定义和不同的值也会影响搜索过程估价函数对算法的影响示例例：八数码问题f(x)=g(x)+h(x)g(x)：从初始状态到x需要进行的移动操作的次数h(x)：所有棋子与目标位置的曼哈顿距离之和曼哈顿距离：两点之间水平距离和垂直距离之和仍满足估价函数的限制条件12384567h(x)=2+1+1+2=63451238456712384567123845671+41+61+61238456712384567123845672+52+52+312384567123845673+23+4123845674+181324567123845675+05+20+5571123846752例：路径规划SG4G4G56445566A*算法被广泛应用于静态路网中的最短路径规划用距离表示代价每一步可以往相邻的8个无障碍格子移动，移动距离为1g(x)：从出发点S到当前点x的距离h(x)：从当前点x到目标点G的距离4G56455665644G564455666564G5644665756755667777455644556665675675567766677777谢谢大家！