人工智能例题大纲

1 用谓词逻辑知识表示方法表示如下知识 用谓词逻辑知识表示方法表示如下知识 1 有人喜欢梅花 有人喜欢菊花 有人既喜欢梅花又喜欢菊花 有人喜欢梅花 有人喜欢菊花 有人既喜欢梅花又喜欢菊花 2 不是每个计算机系的学生都喜欢在计算机上编程序 不是每个计算机系的学生都喜欢在计算机上编程序 解 1 定义谓词 P x x 是人 L x y x 喜欢 y 其中 y 的个体域是 梅花 菊花 将知识用谓词表示为 x P x L x 梅花 L x 菊花 L x 梅花 L x 菊花 解 2 定义谓词 S x x 是计算机系学生 L x pragramming x 喜欢编程序 U x computer x 使用计算机 将知识用谓词表示为 x S x L x pragramming U x computer 2 请用语义网络表示如下知识 请用语义网络表示如下知识 高老师从高老师从 3 月到月到 7 月给计算机系的学生讲月给计算机系的学生讲 计算机网络计算机网络 课 课 解 解 3 判断以下子句集是否为不可满足判断以下子句集是否为不可满足 P x Q x R x P y R y Q a R b 解 采用归结反演 存在如下归结树 故该子句集为不可满足 2 4 证明 证明 G 是是 F 的逻辑结论的逻辑结论 F x y P f x Q f y G P f a P y Q y 证 先转化成子句集 对 F 进行存在固化 有 P f v Q f w 得以下两个子句 P f v Q f w 对 G 有 P f a P y Q y 先进行内部合一 设合一 f a y 则有因子 P f a Q f a 再对上述子句集进行归结演绎推理 其归结树如下图所示 即存在一个到空子句的归 结过程 因此 G 为真 5 设有如下结构的移动将牌游戏 设有如下结构的移动将牌游戏 其中 其中 B 表示黑色将牌 表示黑色将牌 W 表是白色将牌 表是白色将牌 E 表示空格 游戏的规定走法是 表示空格 游戏的规定走法是 1 任意一个将牌可移入相邻的空格 规定其代价为任意一个将牌可移入相邻的空格 规定其代价为 1 2 任何一个将牌可相隔任何一个将牌可相隔 1 个其它的将牌跳入空格 其代价为跳过将牌的数目加个其它的将牌跳入空格 其代价为跳过将牌的数目加 1 游戏要达到的目标什是把所有游戏要达到的目标什是把所有 W 都移到都移到 B 的左边 对这个问题 请定义一个启发函的左边 对这个问题 请定义一个启发函 数数 h n 并给出用这个启发函数产生的搜索树 你能否判别这个启发函数是否满足下界要 并给出用这个启发函数产生的搜索树 你能否判别这个启发函数是否满足下界要 求 在求出的搜索树中 对所有节点是否满足单调限制 求 在求出的搜索树中 对所有节点是否满足单调限制 解 设 h x 每个 W 左边的 B 的个数 f x d x 3 h x 其搜索树如下 3 6 设有如下一组推理规则设有如下一组推理规则 r1 IF E1 THEN E2 0 6 r2 IF E2 AND E3 THEN E4 0 7 r3 IF E4 THEN H 0 8 r4 IF E5 THEN H 0 9 且已知且已知 CF E1 0 5 CF E3 0 6 CF E5 0 7 求 求 CF H 解 1 先由 r1求 CF E2 CF E2 0 6 max 0 CF E1 0 6 max 0 0 5 0 3 2 再由 r2求 CF E4 CF E4 0 7 max 0 min CF E2 CF E3 0 7 max 0 min 0 3 0 6 0 21 3 再由 r3求 CF1 H CF1 H 0 8 max 0 CF E4 0 8 max 0 0 21 0 168 4 再由 r4求 CF2 H CF2 H 0 9 max 0 CF E5 0 9 max 0 0 7 0 63 5 最后对 CF1 H 和 CF2 H 进行合成 求出 CF H CF H CF1 H CF2 H CF1 H CF2 H 0 692 7 设训练例子集如下表所示 设训练例子集如下表所示 4 请用请用 ID3 算法完成其学习过程 算法完成其学习过程 解 设根节点为 S 尽管它包含了所有的训练例子 但却没有包含任何分类信息 因此具 有最大的信息熵 即 H S P log 2P P log2 P 式中 P 3 6 P 3 6 即有 H S 3 6 log 3 6 3 6 log 3 6 0 5 1 0 5 1 1 按照 ID3 算法 需要选择一个能使 S 的期望熵为最小的一个属性对根节点进行扩展 因此我们需要先计算 S 关于每个属性的条件熵 H S xi ST S H ST SF S H SF 其中 T 和 F 为属性 xi的属性值 ST和 SF分别为 xi T 或 xi F 时的例子集 S ST 和 SF 分别为例子集 S ST和 SF 的大小 下面先计算 S 关于属性 x1的条件熵 在本题中 当 x1 T 时 有 ST 1 2 3 当 x1 F 时 有 SF 4 5 6 其中 ST 和 SF中的数字均为例子集 S 中例子的序号 且有 S 6 ST SF 3 由 ST可知 P 2 3 P 1 3 则有 H ST P log2 P P log2 P 2 3 log2 2 3 1 3 log2 1 3 0 9183 再由 SF可知 PSF 1 3 PSF 2 3 则有 5 H SF PSF log2 PST PSF log2 PSF 2 3 log2 2 3 1 3 log2 1 3 0 9183 将 H ST 和 H SF 代入条件熵公式 有 H S x1 ST S H ST SF S H SF 3 6 0 9183 3 6 0 9183 0 9183 下面再计算 S 关于属性 x2的条件熵 在本题中 当 x2 T 时 有 ST 1 2 5 6 当 x2 F 时 有 SF 3 4 其中 ST 和 SF中的数字均为例子集 S 中的各个例子的序号 且有 S 6 ST 4 SF 2 由 ST可知 PST 2 4 PST 2 4 则有 H ST P ST log2 P ST P ST log2 P ST 2 4 log2 2 4 2 4 log2 2 4 1 再由 SF可知 PSF 1 2 PSF 1 2 则有 H SF P log2 P P log2 P 1 2 log2 1 2 1 2 log2 1 2 1 将 H ST 和 H SF 代入条件熵公式 有 H S x2 ST S H ST SF S H SF 4 6 1 2 6 1 1 可见 应该选择属性 x1对根节点进行扩展 用 x1对 S 扩展后所得到的部分决策树如下 图所示 6 8 八数码难题八数码难题 f n d n P n d n 深度深度 P n 与目标距离与目标距离 显然满足显然满足 P n h n 即即 f g h 9 修道士和野人问题修道士和野人问题 解 用 m 表示左岸的修道士人数 c 表示左岸的野人数 b 表示左岸的船数 用三 元组 m c b 表示问题的状态 对 A 算法 首先需要确定估价函数 设 g n d n h n m c 2b 则有 f n g n h n d n m c 2b 其中 d n 为节点的深度 通过分析可知 h n h n 满足 A 算法的限制条件 M C 问题的搜索过程如下图所示 7 10 设有如下一组知识 设有如下一组知识 r1 IF E1 THEN H 0 9 r2 IF E2 THEN H 0 6 r3 IF E3 THEN H 0 5 r4 IF E4 AND E5 OR E6 THEN E1 0 8 已知 已知 CF E2 0 8 CF E3 0 6 CF E4 0 5 CF E5 0 6 CF E6 0 8 求 求 CF H 解 由 r4得到 CF E1 0 8 max 0 CF E4 AND E5 OR E6 0 8 max 0 min CF E4 CF E5 OR E6 0 8 max 0 min CF E4 max CF E5 CF E6 0 8 max 0 min CF E4 max 0 6 0 8 0 8 max 0 min 0 5 0 8 0 8 max 0 0 5 0 4 由 r1得到 CF1 H CF H E1 max 0 CF E1 0 9 max 0 0 4 0 36 由 r2得到 CF2 H CF H E2 max 0 CF E2 0 6 max 0 0 8 0 48 由 r3得到 CF3 H CF H E3 max 0 CF E3 0 5 max 0 0 6 0 3 根据结论不精确性的合成算法 CF1 H 和 CF2 H 同号 有 67 017 084 0 48 036 048 036 0 21212 1 HCFHCFHCFHCFHCF CF12 H 和 CF3 H 异号 有 8 53 0 7 0 37 0 3 0 67 0min1 3 067 0 min1 32 1 32 1 3 2 1 HCFHCF HCFHCF HCF 即综合可信度为 CF H 0 53 11 设有如下知识 设有如下知识 r1 IF E1 0 6 AND E2 0 4 THEN E5 0 8 r2 IF E3 0 5 AND E4 0 3 AND E5 0 2 THEN H 0 9 已知 已知 CF E1 0 9 CF E2 0 8 CF E3 0 7 CF E4 0 6 求 求 CF H 解 CF E1 AND E2 0 9 0 6 0 8 0 4 0 86 CF E5 0 86 0 8 0 69 CF E3 AND E4 AND E5 0 7 0 5 0 6 0 3 0 69 0 2 0 67 CF H 0 67 0 9 0 60 12 设有如下规则 设有如下规则 r1 IF E1 AND E2 THEN A a1 a2 CF 0 3 0 5 r2 IF E3 THEN H h1 h2 CF 0 4 0 2 r3 IF A THEN H h1 h2 CF 0 1 0 5 已知用户对初始证据给出的确定性为 已知用户对初始证据给出的确定性为 CER E1 0 8 CER E2 0 6 CER E3 0 9 并假并假 定中的元素个数定中的元素个数 10 求 求 CER H 解 由给定知识形成的推理网络如下图所示 解 由给定知识形成的推理网络如下图所示 1 求求 CER A 由由 r1 9 CER E1 AND E2 min CER E1 CER E2 min 0 8 0 6 0 6 m a1 a2 0 6 0 3 0 6 0 5 0 18 0 3 Bel A m a1 m a2 0 18 0 3 0 48 Pl A 1 Bel A 1 0 1 f A Bel A A Pl A Bel A 0 48 2 10 1 0 48 0 584 故故 CER A MD A E f A 0 584 2 求求 CER H 由由 r2得得 m1 h1 h2 CER E3 0 4 CER E3 0 2 0 9 0 4 0 9 0 2 0 36 0 18 m1 1 m1 h1 m1 h2 1 0 36 0 18 0 46 由由 r3得得 m2 h1 h2 CER A 0 1 CER A 0 5 0 58 0 1 0 58 0 5 0 06 0 29 m2 1 m2 h1 m2 h2 1 0 06 0 29 0 65 求正交和求正交和 m m1 m2 K m1 m2 m1 h1 m2 h1 m1 h1 m2 m1 m2 h1 m1 h2 m2 h2 m1 h2 m2 m1 m2 h2 0 46 0 65 0 36 0 06 0 36 0 65 0 46 0 06 0 18 0 29 0 18 0 65 0 46 0 29 0 30 0 02 0 23 0 03 0 05 0 12 0 13 0 88 32 0 06 046 065 036 006 036 0 88 0 1 1 12121112111 hmmmhmhmhm K hm 同理可得 同理可得 10 34 0 29 046 065 018 029 018 0 88 0 1 1 22122122212 hmmmhmhmhm K hm 故有 故有 m 1 m h1 m h2 1 0 32 0 34 0 34 再根据再根据 m 可得可得 Bel H m h1 m h2 0 32 0 34 0 66 Pl H m Bel H 0 34 0 66 1 73 0 66 01 10 2 66 0 HBelHPl H HBelHf CER H MD H E f H 0 73 13 用用 ID3 算法完成下述学生选课的例子算法完成下述学生选课的例子 假设将决策假设将决策 y 分为以下分为以下 3 类 类 y1 必修 必修 AI y2 选修 选修 AI y3 不修 不修 AI 做出这些决策的依据有以下做出这些决策的依据有以下 3 个属性 个属性 x1 学历层次 学历层次 x1 1 研究生 研究生 x1 2 本科本科 x2 专业类别 专业类别 x2 1 电信类 电信类 x2 2 机电类机电类 x3 学习基础 学习基础 x3 1 修过修过 AI x3 2 未修未修 AI 表表 6 1 给出了一个关于选课决策的训练例子集给出了一个关于选课决策的训练例子集 S 该训练例子集该训练例子集 S 的大小为的大小为 8 ID3 算法就是依据这些训练例子 以算法就是依据这些训练例子 以 S 为根节点 按照信为根节点 按照信 息熵下降最大的原则来构造决策树的 息熵下降最大的原则来构造决策树的 解 解 首先对根节点 其信息熵为 首先对根节点 其信息熵为 log 2 3 1 i i i yPyPSH 11 其中 为可选的决策方案数 且有其中 为可选的决策方案数 且有 P y1 1 8 P y2 2 8 P y3 5 8 即有 即有 H S 1 8 log2 1 8 2 8 log2 2 8 5 8 log2 5 8 1 2988 按照按照 ID3 算法 需要选择一个能使算法 需要选择一个能使 S 的期望熵为最小的一个属性对根节点进行扩的期望熵为最小的一个属性对根节点进行扩 展 因此我们需要先计算展 因此我们需要先计算 S 关于每个属性的条件熵 关于每个属性的条件熵 t it t S H S xH S S 其中 其中 t 为属性为属性 xi的属性值 的属性值 St为为 xi t 时的例子集 时的例子集 S 和和 St 分别是例子集分别是例子集 S 和和 St的的 大小 大小 下面先计算下面先计算 S 关于属性关于属性 x1的条件熵 的条件熵 在表在表 6 1 中 中 x1的属性值可以为的属性值可以为 1 或或 2 当 当 x1 1 时 时 t 1 时 有 时 有 S1 1 2 3 4 当当 x1 2 时 时 t 2 时 有 时 有 S2 5 6 7 8 其中 其中 S1和和 S2中的数字均为例子集中的数字均为例子集 S 中的各个例子的序号 且有中的各个例子的序号 且有 S 8 S1 S2 4 由由 S1可知 可知 Ps1 y1 1 4 Ps1 y2 1 4 Ps1 y3 2 4 则有 则有 H S1 Ps1 y1 log2 Ps1 y1 Ps1 y2 log2 Ps1 y2 Ps1 y3 log2 Ps1 y3 1 4 log2 1 4 1 4 log2 1 4 2 4 log2 2 4 1 5 再由再由 S2可知 可知 Ps2 y1 0 4 Ps2 y2 1 4 Ps2 y3 3 4 则有则有 H S2 Ps2 y2 log2 Ps2 y2 Ps2 y3 log2 Ps2 y3 1 4 log2 1 4 3 4 log2 3 4 0 8113 将将 H S1 和和 H S2 代入条件熵公式代入条件熵公式 有有 H S x1 S1 S H S1 S2 S H S2 4 8 1 5 4 8 0 8113 1 1557 同样道理 可以求得 同样道理 可以求得 H S x2 1 1557 H S x3 0 75 可见 应该选择属性可见 应该选择属性 x3对根节点进行扩展 用对根节点进行扩展 用 x3对对 S 扩展后所得到的得到部分决扩展后所得到的得到部分决 策树如图策树如图 6 5 所示 所示 S x3 1 y3 x3 2 x1 x2 图图 6 5 部分决策部分决策 树树 x3 1 x3 2 12 在该树中 节点在该树中 节点 x3 1 y3 为决策方案为决策方案 y3 由于 由于 y3已是具体的决策方案 故该节点的已是具体的决策方案 故该节点的 信息熵为信息熵为 0 已经为叶节点 已经为叶节点 节点节点 x3 2 x1 x2 的含义是需要进一步考虑学历和专业这两个属性 它是一个的含义是需要进一步考虑学历和专业这两个属性 它是一个 中间节点 还需要继续扩展 至于其扩展方法与上面的过程类似 中间节点 还需要继续扩展 至于其扩展方法与上面的过程类似 通过计算可知 该节点对属性通过计算可知 该节点对属性 x1和和 x2 其条件熵均为 其条件熵均为 1 由于它对属性 由于它对属性 x1和和 x2的的 条件熵相同 因此可以先选择条件熵相同 因此可以先选择 x1 也可以先选择 也可以先选择 x2 依此进行下去 依此进行下去 若先选择若先选择 x1可得到如图可得到如图 6 6 所示的最终的决策树 若先选择所示的最终的决策树 若先选择 x2 可得到如图可得到如图 7 7 所示的最终的决策树 所示的最终的决策树 14 归结反演 归结反演 已知 已知 张和李是同班同学 如果张和李是同班同学 如果 x 和和 y 是同班同学 则是同班同学 则 x 的教室也是的教室也是 y 的教室 现的教室 现 在张在在张在 302 教室上课 教室上课 问 问 现在李在哪个教室上课 现在李在哪个教室上课 解 首先定义谓词 C x y x 和 y 是同班同学 At x u x 在 u 教室上课 把已知前提用谓词公式表示如下 C zhang li x y u C x y At x u At y u 13 At zhang 302 把目标的否定用谓词公式表示如下 v At li v 把上述公式化为子句集 C zhang li C x y At x u At y u At zhang 302 把目标的否定化成子句式 并用重言式 At li v At li v 代替之 把此重言式加入前提子句集中 得到一个新的子句集 对这个新的子句集 应用 归结原理求出其证明树 其求解过程如下图所示 该证明树的根子句就是所求的答案 即 李明在 302 教室 公式 公式 A 估价函数估价函数 用来估计节点重要性 定义为从初始节点 S0出发 约束经过节点 n 到达目标节点 Sg的所有路径中最小路径代价的估计值 一般形式 f n g n h n 其中 g n 是从初始节点 S0到节点 n 的实际代价 h n 是从节点 n 到目标节点 Sg的最 优路径的估计代价 B A 算法是对算法是对 A 算法的估价函数算法的估价函数 f n g n h n 加上某些限制后得到的一种启发式搜加上某些限制后得到的一种启发式搜 索算法索算法 假设 f n 是从初始节点 S0出发 约束经过节点 n 到达目标节点 Sg的最小代价 估价函数 f n 是对 f n 的估计值 记 f n g n h n 其中 g n 是从 S0出发到达 n 的最小代价 h n 是 n 到 Sg的最小代价 如果对 A 算法 全局择优 中的 g n 和 h n 分别提出如下限制 第一 g n 是对最小代价 g n 的估计 且 g n 0 第二 h n 是最小代价 h n 的下界 即对任意节点 n 均有 h n h n 则称满足上述两条限制的 A 算法为 A 算法 14 C 不确定性知识的表示形式 不确定性知识的表示形式 在 C F 模型中 知识是用产生式规则表示的 其一般形式为 IF E THEN H CF H E 其中 E 是知识的前提条件 H 是知识的结论 CF H E 是知识的可信度 D 组合证据组合证据 合取 E E1 AND E2 AND En 时 若已知 CF E1 CF E2 则 CF E min CF E1 CF E2 CF En 析取 E E1 OR E2 OR En 时 若已知 CF E1 CF E2 则 CF E max CF E1 CF E2 CF En E 不确定性的更新公式不确定性的更新公式 CF H CF H E max 0 CF E 若 CF E 0 则 CF H 0 即该模型没考虑 E 为假对 H 的影响 若 CF E 1 则 CF H CF H E F 设有知识 设有知识 IF E1 THEN H CF H E1 IF E2 THEN H CF H E2 则结论则结论 H 的综合可信度可分以下两步计算 的综合可信度可分以下两步计算 1 分别对每条知识求出其 CF H 即 CF1 H CF H E1 max 0 CF E1 CF2 H CF H E2 max 0 CF E2 2 用如下公式求 E1与 E2对 H 的综合可信度 异号 与 若 0 且 0 若 0 且 0 若 min1 2 1 2 1 2 1 21 21 2121 2121 HCF HCF HCF HCF HCF HCF HCFHCF HCFHCF HCFHCFHCFHCF HCFHCFHCFHCF HCF G 带加权因子的可信度推理带加权因子的可信度推理 在这种不确定性推理中 证据的不确定性仍然用可信度因子表示 组合证据的可信度 可通过计算得到 对于前提条件 E E1 1 AND E2 2 AND AND En n 所对应的组合证据 其可信度由下式计算 CF E CF E1 1 CF E2 2 CF En n 如果不满足归一条件 则可信度由下式计算 CF E CF E1 1 CF E2 2 CF En n 1 2 n H 证据理论证据理论 15 设函数 m 2 0 1 且满足 A Am m 1 0 则称 m 是 2 上的概率分配函数 m A 称为 A 的基本概率数 I 概率分配函数的合成概率分配函数的合成 设 m1和 m2是 2 上的基本概率分配函数 它们的正交和 21 mmm 定义为 212121 1 iiiii smmmsmsmsmKsm 其中 21 1 212121i n i iii smmmsmsmsmmmK J 信任函数 下限函数 信任函数 下限函数 对任何命题 A 其信任函数为 1 1 msmBmBel smABel n i i B As i i K 似然函数 上限函数 似然函数 上限函数 对任何命题 A 其似然函数为 1 1 1 1 1 1 1 1 1 BelBelPl ABelm ABelm smsmsmABelAPl n iAs ii As i ii 似然函数也称为上限函数 表示对 A 的非假信任度 可以看出 对任何命题 A A 都有 Pl A B