人工智能知识表示方法状态空间法

人工智能ArtificialIntelligence(AI)许建华xujianhua@njnu.edu.cn南京师范大学计算机科学与技术学院2011年秋季第2章知识示2.1状态空间法2.2问题归约法2.3谓词逻辑法用计算机技术解决实际问题的一般思路:实际问题问题表达知识表达数学建模求解的方法或者算法结果的解释例：求侧面积为150平方米的体积最大的长方体？设长、宽、高分别为x,y,z侧面积为：2(xy+yz+xz)体积为：xyz数学模型maxxyzs.t.2(xy+yz+xz)=150xyz利用最优化技术中的算法，可以得到结果：x=y=z=5.0解释：长、宽、高都等于5米时，体积最大说明：在计算数学的课程中，主要关心求解的具体算法在人工智能中，重点关注两个方面的内容：①问题的表示（知识的表示）：即要找到问题的一种合适的表示方法在人工智能中，我们要涉及到： 状态空间法 问题归约法 谓词逻辑法 样本向量法②问题的求解：从问题表示方法出发，找到一个合理的来求解在人工智能中，常有的方法有： 搜索法 推理法 计算方法2.1状态空间法在日常的一些智力游戏（八数码、走八卦阵、走迷宫等）中，我们采用的策略：试着向前走，如果走不通，则往后退，不停地试、试、试，直到成功 1 2 4 5 7 8 3 6 1 2 3 4 5 6 7 8类似地，在人工智能中，一种最基本的求解方法就是试探搜索法，即，通过在某个可能的解空间（例如，所有可能的走法）中寻找一个解这种基于解空间的问题表示和求解方法就是状态空间法，其基础是状态和算符（算子）2.1.1问题状态描述状态：描述某一类不同事物间的差别而引入的一组最少变量q0,q1,…,qn的有序集合例：描述在坐的同学变量可以有年级班级姓名性别学号……根据要解决的问题、从中选择最少的一组变量例： 区分哪一个班：年级、班级 区分哪一位同学：姓名、性别、学号矢量形式：Q=[q0,q1,…,qn]T其中，元素qi(i=0,1,…,n)为集合的分量，称为状态变量。具体状态：给每一个状态变量一个具体的值（符号、数值等）。矩阵形式例：八数码问题矢量形式的状态表示：矩阵形式的状态表示： 1 2 3 4 7 8 6 5算符（操作符）：使问题从一个状态变换到另一状态的手段。例如：走步、规则、数学算子、运算符号等等。例：描述在坐的同学（续）状态变量可以有年级班级姓名性别学号……操作符入学正常升级毕业例：八数码问题算符：1、数字的上、下、左、右移动2、空格的上、下、左、右移动 1 2 3 4 7 8 6 5问题的状态空间：一个表示问题全部可能状态及其关系的图，它包含了三个集合： 所有可能的问题初始状态集合S 操作符集合F 目标状态集合G状态空间记作三元状态（S,F,G）例：十五数码问题 初始状态：左图目标状态：右图操作符集合F＝[空格的左移、上移、右移、下移] 11 9 4 15 1 3 12 7 5 8 6 13 2 10 14可能的求解过程注：在程序和图示求解过程中，需要规定好操作符的使用顺序要完成某一个具体问题的状态描述，必须完成三项工作：①如何描述状态，特别是初始状态②操作符集合及其对状态描述的作用③如何描述目标状态即定义好三元状态（S,F,G）中的三个成分状态空间法：从某一个初始状态开始，每次施加一个操作符，递增地建立操作符序列，直到达到目标状态为止状态空间法的问题：寻找从初始状态到目标状态的某一个操作符序列状态空间法的解：从初始状态变换到目标状态的操作符序列左、下、上….. 11 9 4 15 1 3 12 7 5 8 6 13 2 10 14 1 2 3 4 5 6 7 8 9 10 11 12 13 14 152.1.2状态图示法图是由节点（不一定是有限个的节点）的集合构成的注意：在图论中，图的定义中还包括边的集合状态空间法（求解过程）的表示方法：用图来表示（借助于图论中某些技术）有向图和无向图：无向图：一对节点可能互为后裔，边用线段来表示有向图：一对节点用弧线连接起来，并且从一个节点指向另一个节点父辈节点或祖先ni后继节点或后裔nj对于某一个节点序列（ni0,ni2,…nij,…,nik）如果每一个节点nij-1都有一个后继节点nij存在，则将这一序列称为从节点ni0到nik的长度为k的路径。nikni0如果从节点ni到nj存在一条路径，则称节点nj是从节点ni可到达的节点，或者称nj是ni的后裔节点、称ni是nj的祖先。njni祖先后裔当用有向图来表示状态空间法时，对应关系： 图中的一个节点对应于某一个状态 图中的一个有向弧对应于某一个算符注：有向弧的旁边可以标以具体算符状态节点操作符有向弧问题：寻找从初始状态到目标状态的某个操作符序列问题：寻找图中初始节点（对应初始状态）到目标节点（对应于目标状态）的一条路径转化为c(ni,nj)表示从节点ni指向节点nj（相邻）的那一段弧的代价njni在某些情况下，每个操作符作用、成本是不一样的，需要引入代价的概念（不相邻的）两个节点间路径的代价等于连接该路径的各个节点的所有弧线的代价之和nkn0C(n0,n1)C(nk-1,nk)引入代价的概念后，我们的问题可能是：寻找初始节点到目标节点之间的代价最小的路径对应的原始问题：寻找从初始状态到目标状态的操作符代价之和最小的操作符序列利用图论的技术，我们要解决两个问题：第一、找出初始节点到目标节点的一条路径。对应于寻找初始状态到目标状态的操作符序列第二、找出初始节点到目标节点的一条代价最小的路径。对应于寻找将初始状态变换到目标状态所用操作符代价之和最小的操作符序列2.1.3例子例1：八数码问题八数码的任何一种摆法是一个状态，状态总数为9！。用一个长度为9的一维数组来描述状态：（q1,q2,…,q9）其中，qi取0,1,…,8个数，0表示空格，且取值互不相同。算符是空格的上、下、左、右移动如果记空格的位置为P，这时空格的移动规则是：PP-3P+1P+3P-1表示位置123456789P 1 2 3 8 5 6 7 4 1 2 3 8 5 6 7 4 0空格移动规则表示位置 1 2 3 4 5 6 7 8 9初始状态：(2，0，3，1，8，4，5，6，7）目标状态:（1，2，3，8，0，4，7，6，5）部分状态空间图注意： 事先规定操作符的前后顺序，便于编程 不要生成已有的状态（节点），防止进入死循环例2：迷宫问题给图上加一个坐标系，定义每一个分叉路口为一个状态。操作符为人的上、下、左、右走动初始状态为（1，1）目标状态为（4，4）部分状态空间图例3：梵塔问题（三个盘）对于n个盘的问题，我们用n维向量（a1a2…an）表示问题的一个状态其中ai=1,2,3表示第i个盘位于第一、二、三个柱子上，a1an中盘的大小从大到小初始状态为（1…1），目标状态为（3…3）操作符m(i,j)：表示一个盘从i根柱子搬到第j根柱子。T(k)：表示第k根柱子上（最上面）的盘的大小。操作符集合为：O={m(i,j)|T(i)<T(j)}部分状态空间图例4：猴子与香蕉问题acb用一个四元组（W，x,Y,z）来表示问题的状态W：猴子的水平位置x：当猴子爬到箱子顶上取1，否则取0Y：箱子的水平位置z：当猴子摘到香蕉时取1，否则取0初始状态是（a,0,b,0），目标状态是（c,1,c,1）操作符：①猴子当前位置W走到水平位置U：goto(U)：（W,0,Y,z）(U,0,Y,z)注：猴子必须不在箱子上②猴子将箱子从W位置推到水平位置V：pushbox(V)：（W,0,W,z）(V,0,V,z)注：猴子与箱子必须在同一位置操作符：③猴子爬到箱子上：climbbox：（W,0,W,z）(W，1,W,z)④猴子摘到香蕉：grasp：（c,1,c,0）(c,1,c,1)acb部分状态空间图初始状态目标状态pushbox例5：四皇后问题状态：任意一种合法的摆法操作符：摆下一个皇后，先摆第一行，每一行从左开始摆，并满足皇后不成线的规则 Q Q思考题：小结用状态空间法表示八数码问题的讲课内容，考虑如何在计算机上加以实现？学科前沿讲座——皇帝的新脑还是人类的终结一、关于人工智能莱布尼兹，德国哲学家、数学家、自然科学家和物理学家。29岁时，提出Leibniz法则：(xn)‘=nxn-1,nQ，而且也已经使用常见的积分符号f(x)dx。最先提出：将人的思维机械化的思想。一、关于人工智能帕斯卡,法国数学家、物理学家、哲学家,发明了加法机、发展了现代概率理论19岁时，设计出机械式加法机，这是世界上第一台机械式数字计算机。莱布尼兹在1674年发明了能做乘法、除法的机械式计算机(十进制),即乘法机，并首先系统研究了二进制记数方法，这对于现代计算机的发明至关重要。巴比奇，查尔斯：1792-1871，英国数学家和分析仪发明者在1822年发明了差分机，依据的原理与现代数字计算器的原理相似。 从数值计算文字、图像等多媒体信息处理初步实现了Leibniz提出的“将人的思维机器化”的思想 让机器拥有人的心智——成为计算机专家梦寐以求的理想！ 1956年，M.L.Minsky，C.Shanon，J.McCarthy(人工智能之父)等在美国达德茅斯大学召开第一届人工智能学术会议。 会上首次使用“人工智能”这一术语。 标志着人工智能学科的诞生。一、关于人工智能这些机械的发明，以及其他技术的快速发展，使机器的应用成为可行。此后，人们开始编写程序以解决智力测验难题、下棋以及把文本从一种语言翻译成另一种语言，这是第一批人工智能程序。这些程序使机器不仅能进行数值计算，还能进行文字、图像等多媒体信息处理，初步实现了Leibniz提出的“将人的思维机器化”的思想。“让机器拥有人的心智”已成为许多计算机专家梦寐以求的理想。由此，出现了一个新的研究领域——“人工智能”。 1950年，W.格雷.瓦尔特，可以自己充电的“乌龟” 1960年，K.M.柯尔，模拟了一个精神病疗法专家 电脑下棋方面，97年的“深蓝”(DeepBlue)，03年的“小深”(DeepJunior)一、关于人工智能 医生：我可以为你效劳吗 病人：我不知道 医生：请告诉我一些情形 病人：不 医生：请你说得仔细些 病人：今天我厌烦得很 医生：你知道这是什么原因 病人：是的我老了 医生：请继续讲 病人：仿佛任何事情都激不起我的兴致　 医生：请更多地告诉我你的这种感觉 病人：我也有些知道为何我会这样感觉 医生：是吗 病人：我似乎在想有一个家 医生：什么东西使你有这样的想法 病人：它是一种挑战 医生：为什么那对你是重要的二、电脑能否实现人的智能？ 机器  体力 电脑  计算速度和准确性 人脑  思维 是否电脑能代替人脑实现智能？ 一旦能够实现，这种被认为是特权的智能行为将受到挑战。二、电脑能否实现人的智能？那么，电脑能否像人脑一样思维呢？要讨论这个问题，必须要提到科学家：图灵，英国数学家，计算机科学家二、电脑能否实现人的智能？“图灵机”的概念，它是一个抽象计算模型，用来精确定义可计算函数。经典计算机实际上就是一个通用图灵机。二、电脑能否实现人的智能？ 人真实地回答问题并试图说服质问者，他确实是人； 电脑被编好“说谎”的程序，试图说服质问者它是人。三、目前人工智能两个代表性的观点：三、目前人工智能两个代表性的观点： 爱因斯坦曾经将其比喻为“与上帝的对话”三、目前人工智能两个代表性的观点：渥维克教授是控制论领域中居世界领先地位的专家。他在书中展示了第一批能够学习、互相交流和自我设计程序的机器人，并且向我们发出了警告：未来的机器人将会统治世界。尽管这本书很多地方看起来像一部小说，但它并没有丝毫虚构。三、目前人工智能两个代表性的观点：四、对人工智能领域有影响的理论与书籍科特•哥德尔，是廿世纪最伟大的数理逻辑学家之一，四、对人工智能领域有影响的理论与书籍 推荐网址 http://homepage.fudan.edu.cn/~Ayukawa/at/20050606.htm 阅读本书道格拉斯•霍夫斯塔特，埃舍尔著名版画家，巴赫，著名作曲家。基本上，这本书讲述逻辑学家哥德尔，艺术家埃舍尔，和作曲家巴赫的创造性的成就怎样交织在一起。该书对丘奇和图灵提出的关于逻辑和计算的思想以及它们与人工智能的关系，做出了透彻而且引人入胜的解释。并因此获得了1980年的普利策奖。四、对人工智能领域有影响的理论与书籍 镶嵌图案埃舍尔的版画(1957)四、对人工智能领域有影响的理论与书籍 问题求解 逻辑推理与定理证明 自然语言理解 自动程序设计 专家系统 机器学习 神经网络 机器人学五、目前人工智能的研究与应用领域 模式识别 机器视觉 智能控制 智能检索 智能调度与指挥 分布式人工智能与Agent 计算智能与进化智能 数据挖掘与知识发现六、计算机视觉中的困惑 这些与人类视觉活动相比，显得微不足道。 人类视觉中的视觉含义的把握以及主观经验在视觉中的作用，使机器不可能拥有的。六、计算机视觉中的困惑六、计算机视觉中的困惑六、计算机视觉中的困惑六、计算机视觉中的困惑 著名的混沌理论“蝴蝶效应”： 美国气象学家洛伦芝（Lorenz）于1960年代提出一篇论文，名叫《一只蝴蝶拍一下翅膀会不会在德克萨斯州引起龙卷风？》，他说，亚马逊流域的一只蝴蝶扇动翅膀，会掀起密西西比河流域的一场风暴。 洛伦芝把这种现象戏称做"蝴蝶效应"，意思即一件表面上看来毫无关系、非常微小的事情，可能带来巨大的改变。六、计算机视觉中的困惑 眼睛和大脑的组合并不只具有“摄像机”般的功能。 虽然，人们对“视觉理解”发生的机制还不太清楚，但可以肯定其中含有非线性突变的因素，而且导致某种结果的因素是不确定的。（即蝴蝶效应） “视觉理解”中抹不去的主观因素不可能通过确定的算法给出。七、展望 在计算机上要实现人的心智，充满困境。 要冲破这一困境，必须有理论性的突破： ————大自然的机理+算法七、展望 问题的解决不依赖于复杂的逻辑运算，而是利用装置本身的复杂性功能。七、展望 ————大自然的机理+算法 目前，在计算原理和模式方面出现了一些新的尝试： 生物计算 量子计算 光子计算 ……莱布尼兹，德国哲学家、数学家、自然科学家和物理学家。29岁时，提出Leibniz法则：(xn)‘=nxn-1,nQ，而且也已经使用常见的积分符号f(x)dx。最先提出：将人的思维机械化的思想。帕斯卡,法国数学家、物理学家、哲学家,发明了加法机、发展了现代概率理论19岁时，设计出机械式加法机，这是世界上第一台机械式数字计算机。莱布尼兹在1674年发明了能做乘法、除法的机械式计算机(十进制),即乘法机，并首先系统研究了二进制记数方法，这对于现代计算机的发明至关重要。巴比奇，查尔斯：1792-1871，英国数学家和分析仪发明者在1822年发明了差分机，依据的原理与现代数字计算器的原理相似。这些机械的发明，以及其他技术的快速发展，使机器的应用成为可行。此后，人们开始编写程序以解决智力测验难题、下棋以及把文本从一种语言翻译成另一种语言，这是第一批人工智能程序。这些程序使机器不仅能进行数值计算，还能进行文字、图像等多媒体信息处理，初步实现了Leibniz提出的“将人的思维机器化”的思想。“让机器拥有人的心智”已成为许多计算机专家梦寐以求的理想。由此，出现了一个新的研究领域——“人工智能”。那么，电脑能否像人脑一样思维呢？要讨论这个问题，必须要提到科学家：图灵，英国数学家，计算机科学家“图灵机”的概念，它是一个抽象计算模型，用来精确定义可计算函数。经典计算机实际上就是一个通用图灵机。渥维克教授是控制论领域中居世界领先地位的专家。他在书中展示了第一批能够学习、互相交流和自我设计程序的机器人，并且向我们发出了警告：未来的机器人将会统治世界。尽管这本书很多地方看起来像一部小说，但它并没有丝毫虚构。科特•哥德尔，是廿世纪最伟大的数理逻辑学家之一，道格拉斯•霍夫斯塔特，埃舍尔著名版画家，巴赫，著名作曲家。基本上，这本书讲述逻辑学家哥德尔，艺术家埃舍尔，和作曲家巴赫的创造性的成就怎样交织在一起。该书对丘奇和图灵提出的关于逻辑和计算的思想以及它们与人工智能的关系，做出了透彻而且引人入胜的解释。并因此获得了1980年的普利策奖。