人工智能ppt（新）.ppt

人工智能及其应用 制作人 王思文刘玉奇于斌 第1章绪论 1 重点掌握人工智能的几种定义 2 掌握目前人工智能的三个主要学派及其认知观 3 一般了解人工智能的主要研究范围和应用领域 定义2人工智能 学科 人工智能 学科 是计算机科学中涉及研究 设计和应用智能机器的一个分支 它的近期主要目标在于研究用机器来模仿和执行人脑的某些智力功能 并开发相关理论和技术 定义3人工智能 能力 人工智能 能力 是智能机器所执行的通常与人类智能有关的智能行为 如判断 推理 证明 识别 感知 理解 通信 设计 思考 规划 学习和问题求解等思维活动 人工智能的三大学派及其认知观 1 符号主义认为人工智能起源于数理逻辑 2 连接主义认为人工智能起源于仿生学 特别是对人脑模型的研究 3 行为主义认为人工智能起源于控制论 第2章知识表示方法 重点掌握用状态空间法 问题归约法 谓词逻辑法 语义网络法 框架表示法来描述问题 解决问题 2 1状态空间法 许多问题求解方法是采用试探搜索方法的 也就是说 这些方法是通过在某个可能的解空间内寻找一个解来求解问题的 这种基于解答空间的问题表示和求解方法就是状态空间法 它是以状态和算符 operator 为基础来表示和求解问题的 2 1状态空间法 状态空间法三要点 1 状态 state 表示问题解法中每一步问题状况的数据结构 2 算符 operator 把问题从一种状态变换为另一种状态的手段 3 状态空间方法 基于解答空间的问题表示和求解方法 它是以状态和算符为基础来表示和求解问题的 2 1状态空间法 由上可知 对一个问题的状态描述 必须确定3件事 1 该状态描述方式 特别是初始状态描述 2 操作符集合及其对状态描述的作用 3 目标状态描述的特性 例2 分油问题 有A B C三个不带刻度的瓶子 分别能装8kg 5kg和3kg油 如果A瓶装满油 B和C是空瓶 怎样操作三个瓶 使A中的油平分两份 假设分油过程中不耗油 解 第一步 定义问题状态的描述形式 设Sk b c 表示B瓶和C瓶中的油量的状态 其中 b表示B瓶中的油量 c表示C瓶中的油量 初始状态集 S 0 0 目标状态集 G 4 0 第二步 定义操作符 操作 把瓶子倒满油 或把瓶子的油倒空 f1 从A瓶往B瓶倒油 把B瓶倒满 f2 从C瓶往B瓶倒油 把B瓶倒满 f3 从A瓶往C瓶倒油 把C瓶倒满 f4 从B瓶往C瓶倒油 把C瓶倒满 f5 从B瓶往A瓶倒油 把B瓶倒空 f6 从B瓶往C瓶倒油 把B瓶倒空 f7 从C瓶往A瓶倒油 把C瓶倒空 f8 从C瓶往B瓶倒油 把C瓶倒空 第三步 求解过程 0 3 3 0 2 3 f1 f1 f1 从A瓶往B瓶倒油 把B瓶倒满 f2 从C瓶往B瓶倒油 把B瓶倒满 f3 从A瓶往C瓶倒油 把C瓶倒满 f4 从B瓶往C瓶倒油 把C瓶倒满 f5 从B瓶往A瓶倒油 把B瓶倒空 f6 从B瓶往C瓶倒油 把B瓶倒空 f7 从C瓶往A瓶倒油 把C瓶倒空 f8 从C瓶往B瓶倒油 把C瓶倒空 由上述状态空间图 可见从初始状态 0 1 到目标状态 4 0 的任何一条通路都是问题的一个解 其中 f1 f4 f7 f6 f1 f4 f7 是算符最少的解之一 例 设有3个传教士和3个野人来到河边 打算乘一只船从右岸渡到左岸去 该船的负载能力为两人 在任何时候 如果野人人数超过传教士人数 那么野人就会把传教士吃掉 他们怎样才能用这条船安全地把所有人都渡过河去 解 第一步 定义问题状态的描述形式 设Sk M C B 表示传教士和野人在河右岸的状态 其中 M表示传教士在右岸的人数 C表示野人在右岸的人数 B用来表示船是不是在右岸 B 1表示在右岸 B 0表示在左岸 初始状态集 S 3 3 1 目标状态集 G 0 0 0 第二步 定义算符 算符R i j 表示划船将i个传教士和j个野人送到左岸的操作 算符L i j 表示划船从左岸将i个传教士和j个野人带回右岸的操作 由于过河的船每次最多载两个人 所以i j 2 这样定义的算符集F中只可能有如下10个算符 F R 1 0 R 2 0 R 1 1 R 0 1 R 0 2 L 1 0 L 2 0 L 1 1 L 0 1 L 0 2 第三步 求解过程 1 1 0 2 2 1 3 1 1 0 2 0 3 0 0 R 2 0 L 2 0 R 1 1 L 1 1 L 0 1 R 0 1 L 2 0 R 2 0 2 2 0 3 3 1 3 2 1 3 2 0 3 1 0 L 0 2 R 0 2 R 0 1 L 0 1 L 1 0 R 1 0 L 0 1 R 0 1 L 1 1 R 1 1 L 0 2 R 0 2 1 1 1 0 0 0 0 1 0 0 1 1 0 2 1 R 0 1 L 1 0 L 0 1 R 0 1 R 1 0 L 1 0 R 0 1 L 0 1 R 1 1 L 1 1 R 0 2 L 0 2 0 3 1 R 0 2 L 0 2 由上述状态空间图 可见从初始状态 3 3 1 到目标状态 0 0 0 的任何一条通路都是问题的一个解 其中 R 1 1 L 1 0 R 0 2 L 0 1 R 2 0 L 1 1 R 2 0 L 0 1 R 0 2 L 1 0 R 1 1 是算符最少的解之一 2 2问题归约法 问题归约法的概念已知问题的描述 通过一系列变换把此问题最终变为一个子问题集合 这些子问题的解可以直接得到 从而解决了初始问题 该方法也就是从目标 要解决的问题 出发逆向推理 建立子问题以及子问题的子问题 直至最后把初始问题归约为一个平凡的本原问题集合 这就是问题归约的实质 2 2问题归约法 问题归约法的组成部分 1 一个初始问题描述 2 一套把问题变换为子问题的操作符 3 一套本原问题描述 2 3谓词逻辑法 一阶谓词逻辑表示法适于表示确定性的知识 它具有自然性 精确性 严密性及易实现等特点 2 3谓词逻辑法 用一阶谓词逻辑法表示知识的步骤如下 1 定义谓词及个体 确定每个谓词及个体的确切含义 2 根据所要表达的事物或概念 为每个谓词中的变元赋以特定的值 3 根据所要表达的知识的语义 用适当的连接符号将各个谓词连接起来 形成谓词公式 例1 设有下列事实性知识 张晓辉是一名计算机系的学生 但他不喜欢编程序 李晓鹏比他父亲长得高 请用谓词公式表示这些知识 1 定义谓词及个体 Computer x x是计算机系的学生 Like x y x喜欢y Higher x y x比y长得高 这里涉及的个体有 张晓辉 zhangxh 编程序 programming 李晓鹏 lixp 以及函数father lixp 表示李晓鹏的父亲 第二步 将这些个体代入谓词中 得到Computer zhangxh Like zhangxh programming Higher lixp father lixp 第三步 根据语义 用逻辑联结词将它们联结起来 就得到了表示上述知识的谓词公式 Computer zhangxh Like zhangxh programming Higher lixp father lixp 例2 设有下列语句 请用相应的谓词公式把它们表示出来 1 人人爱劳动 2 自然数都是大于零的整数 3 西安市的夏天既干燥又炎热 4 喜欢读 三国演义 的人必读 水浒 5 有的人喜欢梅花 有的人喜欢菊花 有的人既喜欢梅花又喜欢菊花 6 他每天下午都去打篮球 解 1 人人爱劳动 定义谓词如下 Man x x是人 Love x y x爱y x Man x Love x 劳动 2 自然数都是大于等于零的整数 定义谓词如下 N x x是自然数 I x x是整数 GZ x x大于等于零 x N x GZ x I x 3 西安市的夏天既干燥又炎热 定义谓词 SUMMER x x处于夏天 DRY x x很干燥 HOT x x很炎热 SUMMER Xi an DRY Xi an HOT Xi an 4 喜欢读 三国演义 的人必读 水浒 定义谓词 MAN x x是人 LIKE x y x喜欢读y x MAN x LIKE x SANGUOYANYI LIKE x SHUIHU 5 有的人喜欢梅花 有的人喜欢菊花 有的人既喜欢梅花又喜欢菊花 定义谓词 MAN x x是人 LIKE x y x喜欢y Meihua表示梅花 Juhua表示菊花 x MAN x LIKE x Meihua y MAN y LIKE y Juhua z MAN z LIKE z Meihua LIKE z Juhua 6 他每天下午都去打篮球 定义谓词及个体 设TIME x x是下午 PLAY x y x去打y Liming表示李明 Basketball表示足球 则 x TIME x PLAY Liming Basketball 2 4语义网络法 语义网络是1968年J R Quillian在研究人类联想记忆时提出的心理学模型 2 4语义网络法 语义网络的概念语义网络是通过概念及其语义关系来表示知识的一种结构化网络图 它由节点和弧线或链线组成 节点用来表示各种概念 事物 属性 情况 动作 状态等 每个节点可以带有若干个属性 以表征其所代表的对象的特性 弧线用于表示节点间的关系 其上的标注则表示被连接的两个节点间的某种语义联系或语义关系 2 4语义网络法 语义网络表示知识的方法及步骤 a 确定问题中的所有对象以及各对象的属性 b 确定所讨论对象间的关系 c 语义网络中 如果节点间的联系是ISA AKO 则下层节点对上层节点的属性具有继承性 整理同一层节点的共同属性 并抽出这些属性 加入上层节点中 以免造成属性信息的冗余 d 将各对象作为语义网络的一个节点 而各对象间的关系作为网络中各节点间的弧 连接形成语义网络 节点可代表一个事物或一个具体概念 也可代表某种情况 事件或某一动作 当节点表示某种事件或某一动作时 可以从该节点引出一组向外的弧 用于指出事件的因果或动作的主体及客体 例1 用一个语义网络表示下列命题 树和草都是植物 树和草是有根有叶的 水草是草 且长在水中 果树是树 且会结果 苹果树是果树中的一种 它结苹果 分析 问题涉及的对象有 植物 树 草 水草 果树 苹果树各对象的属性分别为 树和草的属性 有根 有叶 水草的属性 长在水中 果树的属性 会结果 苹果树的属性 结苹果 植物 苹果树 水草 果树 草 树 AKO AKO AKO AKO AKO 有根 有叶 有根 有叶 会结果 结苹果 长在水中 例 用语义网络表示下列知识 猎狗是一种狗 而狗是一种动物 狗除了动物的有生命 能吃食物 有繁殖能力 能运动外 还有以下特点 身上有毛 有尾巴 四条腿 猎狗的特点是吃肉 奔跑速度快 能狩猎 个头大 而狮子狗也是一种狗 它的特点是吃饲料 身体小 奔跑速度慢 不咬人 供观赏 解题分析 1 本知识涉及的对象有4个 猎狗 狮子狗 狗 动物 猎狗和狮子狗都是一种狗 除了它们本身的属性外 具有狗的一般特性 身上有毛 有尾巴 四条腿 而狗是一种动物 动物所具有的属性它也具有 2 猎狗与狗之间是一种类属关系 狗和动物之间也是一种类属关系 它们都可以用AKO表示 3 整理各对象节点之间的属性 使上层节点所具有的属性不在下层节点中标出 4 将各对象作为一个节点 而它们之间的关系作为弧 得到如下图所示的语义网络 动物 狮子狗 猎狗 狗 AKO AKO AKO 身上有毛 有尾巴 有四条腿 跑得快 能狞猎 有生命 吃饲料 能吃食物 有繁殖能力 能运动 个头大 吃肉 个头小 跑得慢 不咬人 供观赏 2 5框架表示 1974年 由Minsky在 Aframeworkforrepresentingknowledge 中提出 框架是一种描述所论对象属性的数据结构 所论对象可以是一个事物 一个事件或者一个概念 一个框架由若干个 槽 组成 每个 槽 又可划分为若干个 侧面 一个槽用于描述所论及对象的某一方面的属性 一个侧面用于描述相应属性的一个方面 槽和侧面所具有的属性值分别称为槽值和侧面值 槽值可以是逻辑型或数字型的 具体的值可以是程序 条件 默认值或是一个子框架 框架表示 用框架表示法表示知识的步骤如下 1 分析待表达知识中的对象及其属性 对框架中的槽进行合理设置 2 对各对象间的各种联系进行考察 使用一些常用的名称或根据具体需要定义一些表达联系的槽名 来描述上 下层框架间的联系 3 对各层对象的 槽 及 侧面 进行合理的组织安排 避免信息描述的重复 例 用框架表示下述报道的地震事件 虚拟新华社3月15日电 昨日 在云南玉溪地区发生地震 造成财产损失约10万元 统计部门如果需要详细的损失数字 可电询62332931 另据专家认为震级不会超过4级 并认为地处无人区 不会造成人员伤亡 提示 分析概括用下划线标出的要点 经过概念化形成槽 slot 侧面 facet 值 特别要注意 值 value 默认值 default 如果需要值 if needed 如果附加值 if added 的区别与应用 建议采用格式如下 不用的侧面值可删 解 第一步 确定框架的名字和框架的槽 本报道中 涉及地震的发生时间 地点 财产损失 伤亡人数 震级大小等属性 所以 可将时间 地点 震级 伤亡人数 财产损失等作为槽名 第二步 分析本报道中各对象间的关系 由于报道中只涉及地震一件事 所以该步可省略 第3章搜索推理技术 重点掌握一般图搜索策略和消解原理 掌握各种搜索方法和产生式系统原理 了解规则演绎系统的基本原理 对系统组织技术 不确定性推理和非单调推理等高级推理技术作一般性了解 第3章搜索推理技术 从问题表示到问题的解决 有一个求解的过程 而实现求解的过程 采用的基本方法包括搜索和推理 第3章搜索推理技术 和搜索相对应的知识表示法一般有两种 状态空间法 S F G 与或图表示法 基于一种分解与变换的思想 利用树状结构对复杂问题进行表示 使复杂问题简单化 第3章搜索推理技术 图搜索策略是一种在图中寻找路径的方法 搜索种类 盲目搜索 只按预先规定的搜索控制策略进行搜索 启发式搜索 根据问题本身的特性或搜索过程中产生的一些信息来不断改变和调整搜索的方向 图搜索过程框图 3 2盲目搜索 盲目搜索又叫做无信息搜索 一般只适用于求解比较简单的问题 宽度优先搜索和深度优先搜索 属于盲目搜索方法 3 2 1宽度优先搜索 搜索是以接近起始节点的程度依次扩展节点的 如左图所示 从图可见 这种搜索是逐层进行的 在对下一层的任一节点进行搜索之前 必须搜索完本层的所有节点 s L O M F P Q N F F F 例 把宽度优先搜索应用于八数码难题时所生成的搜索树 这个问题就是要把初始棋局变为如右图所示的目标棋局问题 3 2 2深度优先搜索 分析深度优先搜索示意图可看出 在深度优先搜索中 我们首先扩展最新产生的 即最深的 节点 深度相等的节点可以任意排列 我们定义节点的深度如下 1 起始节点 即根节点 的深度为0 2 任何其它节点的深度等于其父辈节点深度加上1 3 2 2深度优先搜索 有界深度优先搜索给出一个节点扩展的最大深度 深度界限 有界深度优先搜索过程是沿着一条路径进行下去 直到深度界限为止 然后再考虑只有最后一步有差别的相同深度或较浅深度可供选择的路径 接着再考虑最后两步有差别的那些路径 等等 3 2 3等代价搜索 宽度优先搜索的推广用来解决从起始状态至目标状态的具有最小代价的路径问题 从起始节点S到任一节点i的路径代价记为g i 从节点i到它的后继节点j的连接弧线代价记为c i j 则节点j的路径代价为g j g i c i j 待扩展的节点是路径代价最小的节点 3 3启发式搜索 盲目搜索的不足 效率低 耗费过多的计算空间与时间 分析前面介绍的宽度优先 深度优先搜索 或等代价搜索算法 其主要的差别是OPEN表中待扩展节点的顺序问题 人们就试图找到一种方法用于排列待扩展节点的顺序 即选择最有希望的节点加以扩展 那么 搜索效率将会大为提高 启发信息 进行搜索技术一般需要某些有关具体问题领域的特性的信息 把此种信息叫做启发信息 把利用启发信息的搜索方法叫做启发式搜索方法 3 3启发式搜索 启发式搜索策略启发信息用于决定要扩展的下一个节点 以免象在宽度优先或深度优先搜索中那样盲目地扩展 这种搜索总是选择 最有希望 的节点作为下一个被扩展的节点 这种搜索叫做有序搜索 orderedsearch 3 2 1有序搜索 有序搜索又称为最好优先搜索 它总是选择最有希望的节点作为下一个要扩展的节点 估价函数f的确定 一个节点的希望程度越大 则其f值越小 为此 被选为扩展的节点 是估价函数最小的节点 f是从起始节点约束地通过节点n而到达目标节点的最小代价路径上的一个估算代价 3 3 1有序搜索 宽度优先搜索 等代价搜索和深度优先搜索统统是有序搜索技术的特例 对于宽度优先搜索 我们选择f i 作为节点i的深度 对于等代价搜索 f i 是从起始节点至节点i这段路径的代价 3 3 2A 算法 A 算法是一种有序搜索算法 其特点在于对估价函数的定义上 估价函数f f n g n h n g n 就是到目前为止用搜索算法找到的从S到n的最小路径代价 h n 依赖于有关问题的领域的启发信息 从节点n到某目标节点的一条最佳路径的代价的估计 例 八数码难题 解 采用估价函数f n d n W n 其中 d n 是搜索树中节点n的深度 W n 用来计算对应于节点n的数据库中错放的棋子个数 因此 起始节点棋局的f值等于0 3 3 Sg S0 3 4 4 5 5 5 6 4 6 4 4 6 3 4消解原理 重点掌握子句集的求解步骤和消解反演过程 掌握消解推理的规则 3 4 1子句集的求取 例 将下列谓词演算公式化为一个子句集 x P x y P y P f x y y Q x y P y 1 x P x y P y P f x y y Q x y P y 2 x P x y P y P f x y y Q x y P y x P x y P y P f x y y Q x y P y 4 x P x y P y P f x y Q x g x P g x 式中w g x 为一个Skolem函数 5 x y P x P y P f x y Q x g x P g x 3 x P x y P y P f x y w Q x w P w 6 x y P x P y P f x y P x Q x g x P x P g x 8 P x P y P f x y P x Q x g x P x P g x 9 更改变量名称 在上述第 8 步的3个子句中 分别以x1 x2 x3代替变量x 这种更改变量名称的过程 有时称为变量分离标准化 于是 可以得到下列子句集 P x1 P y P f x1 y P x2 Q x2 g x2 P x3 P g x3 7 P x P y P f x y P x Q x g x P x P g x 3 4 2消解反演求解过程 1 消解反演给出一个公式集S和目标公式L 通过反证或反演来求证目标公式L 其证明步骤如下 1 否定L 得 L 2 把 L添加到S中去 3 把新产生的集合 L S 化成子句集 4 应用消解原理 力图推导出一个表示矛盾的空子句NIL 例1 判断下列子句集中哪些是不可满足的分析 子句集中各子句间的关系是合取关系 因此只要有一个子句不可满足 则子句集就是不可满足的 1 NIL 空子句 是不可满足的 2 在子句集中选择合适的子句对其进行消解 若能推出空子句 就说明子句S是不可满足的 1 S P Q Q P P 对子句集S进行归结推理 1 P Q 2 Q 3 P 4 P 5 NIL 3 4 归结故该子句集是不可满足的 2 S P x Q f x a P h y Q f h y a P z 解 因子句集中无互补对 故在子句集S中不存在空子句 故S为可满足的 例2证明 x P x Q x R x x P x T x x T x R x 证明 第一步 先对结论否定并与前提合并得到谓词公式G G x P x Q x R x x P x T x x T x R x 第二步 将公式G化为子句集 可将G看作是三项的合取 对每一项分别求子句集 G1 x P x Q x R x x P x Q x R x x P x Q x P x R x 所以S1 P x1 Q x1 P x2 R x2 G2 x P x T x 所以S2 P a T a B x T x R x x T x R x 所以S B T x R x 从而求得公式G的子句集 S S1 S2 S B P x1 Q x1 P x2 R x2 P a T a T x3 R x3 第三步 例用消解原理 对子句集S进行消解 P x2 R x2 P a R a T x3 R x3 T a 1 a x2 T a 2 a x3 NIL 由此得出子句集S是不可满足的 因此公式G也是不可满足的 从而命题得证 例3某公司招聘人员 A B C三人应试 经面试后 公司有如下想法 1 三人中至少录用一人 2 如果录用A而不录用B 则一定录用C 3 如果录用B 则一定录用C 求证 公司一定录取C 证 定义 P x 表示录用x 则前提为 1 P A P B P C 2 P A P B P C 3 P B P C 则结论为P C 将前提化为子句集 1 P A P B P C 2 P A P B P C 3 P B P C 将结论否定并化为子句集 4 P C 利用消解原理 对子句集进行消解 故证得结论 公司一定录取C 2 反演求解过程步骤 1 把已知前提用谓词公式表示出来 并化为相应的子句集S 2 把待求解的问题也用谓词公式表示出来 然后把它的否定与谓词ANSWER构成析取式 3 把第 2 步得到的析取式化为子句集 并入子句集S中 得到子句集S 4 对子句集S 应用消解原理进行消解 5 若得答案ANSWER 则答案就在ANSWER中 例1 应用消解反演求解如下问题 如果无论约翰 John 到哪里去 菲多 Fido 也就去那里 那么如果约翰在学校里 菲多在哪里呢 解 定义谓词 AT x y 表示x在y那里 则前提为 x AT JOHN x AT FIDO x 和AT JOHN SCHOOL 目标公式 x AT FIDO x 目标公式否定为 x AT FIDO x 其子句形为 AT FIDO x 对本例应用消解反演过程 1 目标公式否定的子句形为 AT FIDO x 将它与谓词ANSWER构成析取式 AT FIDO x ANSWER FIDO x 2 用下图的反演树进行消解 并在根部得到子句 ANSWER FIDO SCHOOL 例2某公司招聘人员 A B C三人应试 经面试后 公司有如下想法 1 三人中至少录用一人 2 如果录用A而不录用B 则一定录用C 3 如果录用B 则一定录用C 求公司录用谁 解 定义 P x 表示录用x 则前提为 1 P A P B P C 2 P A P B P C 3 P B P C 则结论为P x 将前提化为子句集 1 P A P B P C 2 P A P B P C 3 P B P C 将结论否定与谓词ANSWER构成析取式 4 P x ANSWER x 利用消解原理 对子句集进行消解 可见公司一定录取C 例3已知 1 王是李的老师 2 李是张的同学 3 如果x与y是同学 则x的老师也是y的老师 求 张的老师是谁 解 令T x y x是y的老师 C x y x是y的同学 则已知的三个事实可解释为下列公式集T Wang Li C Li Zhang x y z C x y T z x T z y 目标公式 x T x Zhang 将上述事实化为子句集 T Wang Li C Li Zhang C x y T z x T z y 目标公式否定的子句形为 T x Zhang 将它与谓词ANSWER构成析取式 T w Zhang ANSWER w Zhang 用下图的反演树进行消解 并在根部得到子句 C x y T z x T z y T Wang Li C Li y T Wang y C Li Zhang T Wang Zhang 1 Wang z Li x T w Zhang ANSWER w Zhang 2 Zhang y ANSWER Wang Zhang 3 Wang w 3 5产生式系统 1 产生式系统的组成产生式系统由3个部分组成 即总数据库 或全局数据库 产生式规则和控制策略