武汉理工大学-人工智能-2019年期末复习提纲_武汉理工大学人工智能大纲

人工智能2019年期末复习提纲

制作：纪元 - 彭冠淇

本提纲遵循CC-BY-NC-SA协议

(署名-非商业性-相同方式共享)

第二章 知识表示（重点）

• 知识的概念：在长期的生活及社会实践中、在科学研究及实验中积累起来的额对客观世界的认识与经验。（把有关信息关联在一起所形成的信息结构）它反映了客观世界中事物之间的关系，不同事物或者相同事物间的不同关系形成了不同的知识。
• 知识的性质：知识具有相对正确性（在某一环境下正确），不确定性（由随机性，模糊性，经验以及不完全性引起的不确定性），可表示性（利用适当的形式表示出来，语言、文字、图形、神经网络等）与可利用性。
• 知识表示：将人类知识形式化或者模型化。是对知识的一种描述或者一组约定，是一种计算机可以接受的用于描述知识的数据结构。
• 命题：非真即假的陈述句
• 连接词：﹁，∨，∧，→，↔
• 量词： ，
• 学会用谓词逻辑表达式描述推理以及谓词公式。
• 公式的性质：永真性、可满足性、不可满足性、等价性和蕴含性。
• P规则（任何步骤都可引入前提），T规则（可把永真蕴含公式S引入推理过程中，CP规则用前提以及引入的命题R可得S，这从前提集合可以获得R→S）
• 用一阶谓词表示：
  首先定义谓词 Human(x)和Die(x)
  然后用连接词连接各个谓词，形成谓词公式。
  所有的人都是会死的，
  因为诸葛亮是人， Human（Zhugeliang）
  所以诸葛亮是会死的。 Die（Zhugeliang）
• 产生式的基本结构：规则库，综合数据库和推理机
• 产生式表示法的特点：自然醒，模块性，有效性和清晰性。但是效率不高，不能表达结构性知识
• 基本形式： IF P THEN Q
  或者：
  例如：
  r4：IF 动物会飞 AND 会下蛋 THEN 该动物是鸟
  三元组表示：（对象，属性，值）
  或者：（关系，对象1，对象2）
  例：老李年龄是40岁： （Li，age，40）
  老李和老王是朋友：（friend，Li，Wang）
• 框架：
  一种描述所论对象属性的数据结构。
  一个框架由若干个被称为“槽”（slot）的结构组成，每一个槽又可根据实际情况划分为若干个“侧面”（faced）。
  一个槽用于描述所论对象某一方面的属性。
  一个侧面用于描述相应属性的一个方面。
  槽和侧面所具有的属性值分别被称为槽值和侧面值。
  例子： 框架名：〈教师〉
  姓名：单位（姓、名）
  年龄：单位（岁）
  性别：范围（男、女）
  缺省：男
  职称：范围（教授，副教授，讲师，助教）
  缺省：讲师
  部门：单位（系，教研室）
  住址：〈住址框架〉
  工资：〈工资框架〉
  开始工作时间：单位（年、月）
  截止时间：单位（年、月）
  缺省：现在
• 框架的特点：结构性，继承性和自然性

第三章 确定性推理方法（重点）

• 模式匹配：
  确定性匹配是指两个知识模式完全一致，或者经过变量代换后变得完全一致。
  例如，设有如下两个知识模式：
  P1：Father（李四，李小四）and Man (李小四)
  P2：Father(x,y) and Man (y)

• 不确定性匹配是指两个知识模式不完全一致，但从总体上看，它们的相似程度又落在规定的限度内。

• 变量代换：

  1. 代换（置换）是形如 {t1/x1,t2/x2,…,tn/xn} 的有限集合。其中，t1,t2,…,tn是项；x1,x2,…,xn是互不相同的变元；ti/xi表示用ti替换xi。并且要求ti与xi不能相同，xi不能循环地出现在另一个ti中。
     例如， {a/x, c/y, f(b)/z} 是一个代换。
     但{g(y)/x, f(x)/y}不是一个代换。
     原因是循环代换。
     若改为{g(a)/x, f(x)/y}即可
  2. 设
     θ={t1/x1,t2/x2,…,tn/xn}
     λ={ u1/y1, u2/y2, … , um/ym }
     是两个代换。则θ与λ的复合也是一个代换，记作θ°λ。它是从集合
     { t1λ/x1, t2λ/x2, … , tnλ/xn, u1/y1, u2/y2, … , um/ym }
     中删去以下两种元素（tiλ相当于在λ中寻找合适的代换去代替ti中的项）
     ① 当tiλ=xi时，删去tiλ/xi (i=1, 2 ,…, n)；（删除用xi代替xi的项和变元）
     ② 当yj∈{ x1, x2 ,…, xn }时，删去uj/yj (j=1, 2 ,…, m)
     最后剩下的元素所构成的集合。（删去具有相同变元的项与变元的代换式）
     例如 设θ={ f(y)/x, z/y }，λ={a/x, b/y ,y/z }，求θ与λ的复合。
     解:先求出集合
     {f(b/y)/x, (y/z)/y, a/x, b/y , y/z}={f(b)/x, y/y, a/x, b/y , y/z}
     其中，f(b)/x中的f(b)是置换λ作用于f(y)的结果；y/y 中的y是置换λ作用于z的结果。
     在该集合中，y/y满足定义中的条件①，需要删除；
     a/x和b/y满足定义中的条件②，也需要删除。
     最后得θ°λ={f(b)/x, y/z}

• 合一：设有公式集F={F1, F2,…,Fn}，若存在一个置换θ，可使
  F1θ=F2θ=…=Fnθ，则称θ是F的一个合一。称F1,F2,…,Fn是可合一的。
  例如，设有公式集F={P(x,y,f(y)), P(a,g(x),z)}，则
  λ={a/x, g(a)/y, f(g(a))/z}
  是它的一个合一。
  一般来说，一个公式集的合一不是唯一的。

• 最一般合一方法MGU：设σ是公式集F的一个合一，如果对F的任一个合一θ都存在一个置换λ，使得θ=σ°λ，则称σ是一个最一般合一。（Most General Unifier）简称MGU。

• 一个公式集的最一般合一是唯一的。

• MGU算法（例子见PPT P14-P19）
  （1）初始化，令k=0, Fk=F,σk=Φ。其中，Φ是代换空集。
  （2）若Fk只含一个表达式，则算法停止，σk就是最一般合一；否则转步骤（3）。
  （3）找出Fk的差异集Dk。
  （4）若Dk中存在变元xk和项tk，且xk不在tk中出现，则：
  σk+1=σk о {tk/xk}
  Fk+1=Fk {tk/xk}
  k=k+1
  转步骤（2）；否则， 算法终止，F的最一般合一不存在。
  字句和字句集：
  原子谓词公式及其否定统称为文字。
  例如，P(x)、Q(x)、﹁ P(x)、 ﹁ Q(x)
  任何文字的析取式称为子句。
  例如，P(x)∨Q(x)，P(x，f(x))∨Q(x，g(x))
  不含任何文字的子句称为空子句。
  空字句是永假的，不可满足的。
  由子句或空子句所构成的集合称为子句集。

• 谓词公式化为字句集的过程PPT P23-P28

• 归结原理和归结树：P33-P36

• 归结式C12是其亲本子句C1和C2的逻辑结论。
  证明：（按定义）设C1=L∨C1 ’ ，C2=﹁L∨C2’关于解释I为真，则只需证明C12= C1 ’ ∨C2’关于解释I也为真。
  对于解释I，L和﹁L中必有一个为假。
  若L为假，则必有C1’为真，不然就会使C1为假，这将与前提假设C1为真矛盾，因此只能有C1’为真。
  同理，若﹁L为假，则必有C2’为真。
  因此，必有C12= C1’∨C2’关于解释I也为真。即C12是C1和C2的逻辑结论。
  归结反演：
  在命题逻辑中，已知F，证明G为真的归结反演过程如下：
  ①否定目标公式G，得﹁G;
  ②把﹁G并入到公式集F中，得到{F，﹁G}；
  ③把{F，﹁G}化为子句集S。
  ④ 应用归结原理对子句集S中的子句进行归结，并把每次得到的归结式并入S中。如此反复进行，若出现空子句，则停止归结，此时就证明了G为真。（例题 P47）
  谓词逻辑的归结反演过程与命题逻辑的归结反演过程相比，其步骤基本相同，但每步的处理对象不同。例如，在步骤(3)化简子句集时，谓词逻辑需要把由谓词构成的公式集化为子句集；在步骤(4)按归结原理进行归结时，谓词逻辑的归结原理需要考虑两个亲本子句的最一般合一。（例题 P49-P55）
  归结原理除了可用于定理证明外，还可用来求取问题答案，其思想与定理证明相似。其一般步骤为：
  ①把已知前提用谓词公式表示出来，并且化为相应的子句集S；
  ②把待求解的问题也用谓词公式表示出来，然后把它的否定式与谓词ANSWER构成一个析取式，ANSWER是一个为了求解问题而专设的谓词，其变元数量和变元名必须与问题公式的变元完全一致；
  ③把此析取式化为子句集，并且把该子句集并入到子句集S中，得到子句集S；
  ③ 对S应用归结原理进行归结；
  ④ 若在归结树的根节点中仅得到归结式ANSWER，则答案就在ANSWER中。（例题P57–P59）

第四章 不确定性推理

• 不确定性推理的概念：从不确定性的初始证据出发，通过运用不确定性的知识，最终推出具有一定程度的不确定性但却是合理或者近乎合理的结论的思维过程。
• 可信度方法：1975年肖特里菲（E. H. Shortliffe）等人在确定性理论（theory of confirmation）的基础上，结合概率论等提出的一种不确定性推理方法。
  - 优点：直观、简单，且效果好。
• 可信度：根据经验对一个事物或现象为真的相信程度。
  可信度带有较大的主观性和经验性，其准确性难以把握。
  C－F模型：基于可信度表示的不确定性推理的基本方法。
• 静态强度CF（H，E）：知识的强度，即当 E 所对应的证据为真时对 H 的影响程度。
• 动态强度 CF（E）：证据 E 当前的不确定性程度。
• CF（H，E）的取值范围: [-1,1]。
  若由于相应证据的出现增加结论 H 为真的可信度，则 CF（H，E）> 0，证据的出现越是支持 H 为真，就使CF（H，E) 的值越大。
  反之，CF（H，E）< 0，证据的出现越是支持 H 为假，CF（H，E）的值就越小。
  若证据的出现与否与 H 无关，则 CF（H，E）= 0。
• .证据不确定性的表示
  对于CF（E），证据E的可信度取值范围：[-1，1] 。
  对于初始证据，若所有观察S能肯定它为真，则CF(E)= 1。
  若肯定它为假，则 CF(E) = –1。
  若以某种程度为真，则 0 < CF(E) < 1。
  若以某种程度为假，则 －1 < CF(E) < 0 。
  若未获得任何相关的观察，则 CF(E) = 0。
• 结论不确定性的合成算法
  （第一个公式缺少符号和第三个公式缺少符号为减号，例题P23-P28）
  证据理论方法：PPt P31-最后，或者书P84。

第五章 搜索求解策略（重点）

• 按问题的表示方式
  状态空间搜索(State Space)
  与或树搜索(And/Or Tree)

• 按是否使用启发式信息
  盲目搜索（Blind Search）
  启发式搜索(Heuristic Search)

• 为了进行搜索，首先必须考虑问题及其求解过程的形式表示，其表示是否适当，将直接影响到搜索求解的效率。
  状态空间表示
  与或树表示
  状态空间表示法：状态空间表示法用“状态”和“算符”来表示问题
  状态—描述问题求解过程不同时刻的状态
  算符—表示对状态的操作

• 算符的每一次使用就使状态发生变化。当到达目标状态时，由初始状态到目标状态所使用的算符序列就是问题的一个解。（例子P11-p14），（P15-P16）

• 状态空间盲目搜索：
  OPEN表用于待考察的节点，CLOSED表用于存放已考察的节点。
  深度优先为open堆栈，宽度优先为队列。

• 状态空间启发式搜索：全局择优搜索，有序搜索（A算法），A*算法

• 估计函数：用于估计节点的重要性的函数称为估计函数。其一般形式为：
  f(x) = g(x) + h(x)
  其中g(x)为从初始节点S0到节点x已经实际付出的代价；h(x)是从节点x到目标节点Sg的最优路径的估计代价， h(x)称为启发函数，它体现了问题的启发性信息。
  定义启发函数要根据具体问题具体分析，可以参考的思路有：
  　①　一个结点到目标结点的某种距离或差异的度量；
  　②　一个结点处在最佳路径上的概率；
  　③　根据经验主观打分

• 与或树表示法：（PPT P68-P77）
  与/或树是用于表示问题及其求解过程的又一种形式化方法，也称为问题归约方法。

• 问题归约:

  • 含义: 把复杂问题转换为若干需要同时处理的较为简单的子问题后再加以分别求解的策略,可以递归地进行,直到把问题转换为本原问题的集合.
  • 方法: 分解,等价变换

• 与或树盲目搜索：深度优先和宽度优先。
  解树的代价：

  1. 如果x是终止节点，则定义节点x的代价h(x) = 0；
  2. 如果x是”或”节点，y1,y2…yn是它的子节点，则节点x的代价为：h(x) = min{c(x,yi) + h(yi)}
     3)如果x是”与”节点，则节点x的代价有两种计算方法：和代价法与最大代价法。
     若按和代价法计算，则有：h(x) = ∑(c(x,yi) + h(yi)) 若按最大代价法计算，则有：h(x) = max{c(x,yi) + h(yi)}
  3. 如果x不可扩展，且又不是终止节点，则定义h(x) = ∝
     由上述计算节点的代价可以看出，如果问题是可解的，则由子节点的代价就可推算出父节点代价，这样逐层上推，最终就可求出初始节点S0的代价，S0的代价就是解树的代价

但是和代价与最大代价对应的解树不一定相同。

• 希望树：（PPT P104）
• 与或树启发式搜索：（PPT P107-P109例题）
• 博弈树：
• 全信息:对垒的双方A，B轮流采取行动，任何一方都了解当前的格局及过去的历史。
• 二人零和:博弈的结果只有三种情况：A方胜，B方败；B方胜，A方败；双方战成平局。
• 非偶然:博弈的过程是寻找置对手于必败状态的过程。
• 极大极小分析法：
  • 基本思想：设博弈的双方中一方为A，另一方为B。然后为其中的一方(例如A)寻找一个最优行动方案。
    为了找到当前的最优行动方案，需要对各个可能的方案所产生的后果（得分）进行比较。
    为计算得分，需要根据问题的特性信息定义一个估价函数，用来估算当前博弈树端节点的得分。
  • 推算方法：对“或”节点，选其子节点中一个最大的得分作为父节点的得分，这是为了使自己在可供选择的方案中选一个对自己最有利的方案；
    对“与”节点，选其子节点中一个最小的得分作为父节点的得分，这是为了立足于最坏的情况。
    如果一个行动方案能获得较大的倒推值，则它就是当前最好的行动方案。（例题P121-P125）
• α-β剪枝技术：
  • 网页https://www.cnblogs.com/tk55/articles/6012314.html

第六章 智能计算

https://www.jianshu.com/p/ae5157c26af9

• 遗传算法：一类借鉴生物界自然选择和自然遗传机制的随机搜索算法,非常适用于处理传统搜索方法难以解决的复杂和非线性优化问题。可广泛应用于组合优化、机器学习、自适应控制、规划设计和人工生命等领域。

  • 基本思想：
    在求解问题时从多个解开始，然后通过一定的法则进行逐步迭代以产生新的解。

  • 基本求解步骤：

  • 常用编码方式：位串编码（二进制编码，Gray编码），实数编码

  • 群体设定：群体规模一般取为20-100。（太小算法优化性能不好，容易陷入局部最优解。太大计算复杂）

  • 基本遗传算子：选择，交叉，变异。

  • 选择-复制：从当前群体中按照一定概率选出优良的个体，使它们有机会作为父代繁殖下一代子孙。（判断个体优良与否的准则是各个个体的适应度值，个体适应度越高，其被选择的机会就越多。

  • 选择方法：

    1.转盘赌选择（按个体的选择概率产生一个轮盘，轮盘每个区的角度与个体的选择概率成比例；产生一个随机数，它落入转盘的哪个区域就选择相应的个体交叉。）

    2.锦标赛选择方法（从群体中随机选择k个个体，将其中适应度最高的个体保存到下一代。这一过程反复执行，直到保存到下一代的个体数达到预先设定的数量为止。）

    3.最佳个体保存方法（把群体中适应度最高的个体不进行交叉而直接复制到下一代中，保证遗传算法终止时得到的最后结果一定是历代出现过的最高适应度的个体。）。

• 遗传算法的应用：函数极值问题，流水车间调度问题，求解FSP的遗传算法

• 粒子群优化算法：

  • 基本思想
    将每个个体看作n维搜索空间中一个没有体积质量的粒子，在搜索空间中以一定的速度飞行，该速度决定粒子飞行的方向和距离。所有粒子还有一个由被优化的函数决定的适应值。
  • 基本原理
    PSO初始化为一群随机粒子，然后通过迭代找到最优解。在每一次迭代中，粒子通过跟踪两个“极值”来更新自己。第一个就是粒子本身所找到的最优解，这个解称为个体极值。另一个是整个种群目前找到的最优解，这个解称为全局极值。
  • 算法定义
    在n 维连续搜索空间中，对粒子群中的第i (i=1, 2, , m)个粒子进行定义：式(6.20a)等号右边的第1部分是粒子在前一时刻的速度；
    第2部分为个体“认知”分量，表示粒子本身的思考，将现有的位置和曾经经历过的最优位置相比。
    第3部分是群体“社会(social)”分量，表示粒子间的信息共享与相互合作。
    ， 分别控制个体认知分量和群体社会分量相对贡献的学习率。
    随机系数增加搜索方向的随机性和算法多样性。

参数分析见PPT P72-最后

第七章 专家系统

• 专家系统的基本概念：一类包含知识和推理的智能计算机程序 。
• 专家系统的基本组成：知识库（数据库和规则库）和推理机（解释程序和调度程序）。
• 专家系统的特点：具有专家水平的专业知识，能进行有效的推理，启发性，灵活性，透明性，交互性。
• 专家系统的工作原理：
• 专家系统的实例：医学专家系统（MYCIN P53-P63），地址勘探专家系统（PROSPECTOR P65-P69）
• 专家系统的开发工具：（P73-最后）
• 骨架系统，通用型知识表达语言，专家系统开发环境，专家系统程序设计语言。