本文最后更新于：2023年2月14日下午

复习参考题

填空

构成产生式系统的基本元素有（综合数据库）（产生式规则）（控制系统），控制策略按执行规则的方式分类，分为（正向）（逆向）（双向）三类。
归结过程中控制策略的作用是给出控制策略，以使仅对选择合适的子句间方可做归结，避免（多余的、不必要的归结式出现）。常见的控制策略有（线性归结策略）（支持集策略）（单元归结）（输入归结）。
公式G和公式的子句集并不等值，但它们在（不可满足）的意义下是一致的。
与或图的启发式搜索算法AO*的两个过程分别是（图生成过程，即扩展节点）和（计算耗散值）
人工智能的研究途径主要有两种不同的观点，一种观点称为（符号主义），认为人类智能基本单元是（符号）。另一种观点称为（连接主义/仿生主义），认为智能的基本单元是（神经元）。
集合$\{P(a,x,f(g(y)),P(z,f(z),f(u)))\}$的最一般合一置换mgu为（$\{a/z,x/f(z),g(y)/u\}$）。
语义网络是对知识的（有向图）表示方法，一个最简单的语义网络是一个形如（$(结点1,弧,结点2)$）的三元组，语义网络可以描述事物间多种复杂的语义关系，常用ISA、AKO弧表示节点间具有（类属）的分类关系。语义网络下的推理是通过（继承和匹配）实现的。
当前人工智能研究的热点之一就是机器学习。常见的机器学习方法可分为（归纳学习）、（连接学习）、（分析学习）和遗传算法等。一个机器学习系统应有（环境）、（知识库）、（学习环节）和（执行环节）四个基本部分组成。
常用的知识表示法有逻辑表示法、（产生式规则表示法）、（语义网络表示法）、（框架表示法）、（脚本表示法）等。
有两个A*算法A1和A2，若A1比A2有较多的启发信息，则h1(n)（$>$）h2(n)。
关于A算法与A*算法，若规定$h(n)\ge 0$，并且定义启发函数f*(n)=g*(n)+h*(n)表示初始状态$S_0$经点n到目标状态$S_g$最优路径的费用。其中g*(n)为$S_0$到n的最小费用，h*(n)为到$S_g$的实际最小费用。若令$h(n)\equiv 0$，则A算法相当于（BFS），因为上一层节点的（搜索费用）一般比下一层的小。若（$g(n)\equiv h(n)\equiv 0$）则相当于随机算法。若（$g(n)\equiv 0$），则相当于最佳优先算法。特别是当要求（$h(n)\le h^(n)$）就称这种A算法为A\算法。
群智能是指无智能或简单智能的主体通过任何形式的聚集协同而表现出智能行为的特性。群智能潜在的两大特点是（并行性）和（分布式）。其典型算法有（蚁群算法）和（粒子群算法）。已有的群智能理论的研究和应用证明群智能方法是一种能够有效解决（大多数优化问题）的新方法。
蚁群算法是模拟自然界中蚂蚁寻找从巢穴到十五的最佳路径的行为而设计的，蚂蚁在遇到食物返回的路上会分泌（信息素），信息素会随着时间慢慢挥发，且关键路径上的信息素相对浓度（高），蚁群算法已被广泛应用于许多优化问题中，其中有（聚类问题）（图着色）（路由问题）（车辆调度）。
粒子群优化算法是模拟（鸟群）或（蜂群）的觅食行为而设计的，其基本思想是通过群体中（个体之间的协作）和（信息共享）来寻找最优解。粒子群优化算法的应用领域有（人工生命）（军事领域）（车辆路径问题）（邮政投递）。
遗传算法是以达尔文的自然选择学说为基础发展起来的。遗传算法的三种基本操作是（复制）（交叉）（变异），在遗传算法中，衡量个体优劣的尺度是（适应度），它决定某些个体是繁殖或是消亡，同时也是驱动遗传算法的动力。
蚁群算法是模拟自然界中蚂蚁寻找从巢穴到食物的最佳路径的行为而设计的，根据蚁群算法的基本原理，蚁群算法中的行为因子有（范围）（环境）（觅食规则）（移动规则）（避障规则）（信息素规则）等。
近年有学者提出的人工鱼群算法是模仿自然界中鱼群的行为而提出来的解决问题的算法，从模拟鱼群的（聚集行为）（觅食行为）（跟随行为）（移动行为）等方面来模拟自然界中的鱼群行为。
遗传算法将“优胜劣汰，适者生存”的（生物进化原理）引入优化参数形成的编码串群体中，按所选择的（适应度函数）并通过遗传中的（复制）（交叉）（变异）对个体进行（筛选），（适应度高）的个体被保留下来，组成新的群体，新的群体既继承了上一代的信息，又优于上一代。
决策树是一种知识概念表示方法，能表示（与或）规则，是一种（图形符号表示法）。而人工神经网络ANNs是（非图形符号表示法），是一种函数表示法，即从大量的数据中（抽取规则函数）。人工神经网络对于训练数据中的“错误”数据的（健壮性很好）。人工神经网络的训练学习过程中有一个称为“学习速率$\eta$”的常数，$\eta$取值过大会（引起漂移），$\eta$取值过小会（收敛速度太慢，学习效率不高）。
多层神经网络的学习过程中有一种是反向传播算法BP，其基本思想是利用（输出单元的误差再计算上一层单元的误差），依次向上传播，俗称反向传播，又称（逆推学习）算法。
归纳学习需要的预先假定，称为归纳偏置，归纳学习算法隐含了归纳偏置，候选消除算法的归纳偏置是（目标概念可以在假设空间找到），所以又称限定偏置。ID3是一种典型的决策树学习方法，ID3的归纳偏置有两点，分别是（较短的树比较长的树优先）（信息增益高的属性更靠近根节点的树优先）。FIND-S寻找极大特殊假设算法使用一般到特殊的顺序，在偏序结构的一个分支上执行（一般到特殊）搜索，寻找一个与样例一致的（最特殊）假设。
自然语言处理是研究用机器处理人类语言的理论和技术，又叫（自然语言理解/计算语言学/人类语言技术），它研究能实现人与计算机之间用自然语言进行有效通信的各种理论和方法，自然语言处理研究面临的两大困难是（歧义）和（病构），其中歧义分为（注音歧义）（分词歧义）（词义歧义）（语用歧义）四个方面。
在证据理论Evident Theory中引入了信任函数BeL，它满足了（概率论弱公理）。在概率论中，当先验概率很难获得，但又要被迫给出时，用证据理论能区分（不确定性）和（不知道）的差别。因而它比概率论更适合于（专家系统推理方法）。概率论是证据理论的一个特例，有时也称（证据理论）为广义概率论。
贝叶斯网就是一个在弧的连接关系上加入连接强度的因果关系网络。由两个部分组成，其一是DAG，即（有向无环图），其二是CPT，即（条件概率表）。贝叶斯网络通常使用三种推理是（因果推理）（诊断推理）（辩解推理）。
在确定性推理模型中可信度因子$CF(h,e)$（知识静态强度）取值范围为（$[-1,1]$），主观Bayes方法中规定规则的静态强度LS,LN的值应（$[0,\infty)$）

计算证明

设公理集：$(\forall x)(R(x)\to L(x)),(\forall x)(D(x)\to \sim L(x)),(\exists x)(D(x)\wedge I(x))$

求证：$(\exists x)(I(x)\wedge\sim R(x))$ ，给出归结步骤并画出归结树
求下列公式的Skolem范式

(1) $\exists x \forall y \forall z \exists u \forall v \exists w G(x,y,z,u,v,w)$

(2) $\sim(\forall x)(\exists y)P(a,x,y)\to (\exists x)(\sim (\forall y)Q(y,b)\to R(x))$

(3) $\forall x(P(x)\to \forall y(\forall z Q(x,y)\to \neg \forall z R(y,x)))$
用归结法证明：$A_1\wedge A_2 \wedge A_3 \to B$

即B是A1、A2、A3的有效结论

$A_1=(\forall x)((P(x)\wedge \neg Q(x))\to (\exists y)(W(x,y)\wedge V(y)))$

$A_2=(\exists x)(P(x)\wedge U(x)\wedge (\forall y)(W(x,y)\to U(y)))$

$A_3=\neg(\exists x)(Q(x)\wedge U(x))$

$B=(\exists x)(V(x)\wedge U(x))$

简答

在与或图的问题求解过程中，哪几类节点称为能解节点？

终节点是能解节点；

若非终节点有“或”子节点时，当且仅当其子节点至少有一能解时，该非终节点才能解；

若非终节点有“与”子节点时，当且仅当其子节点均能解时，该非终节点才能解。
宽度优先搜索和深度优先搜索有何不同？在何种情况下深度优先搜索优于宽度优先搜索？两种搜索策略是否都是完备的？

BFS是逐层穷举搜索，DFS是分支优先搜索。

如果带搜索问题的解存在且关键路径较长，目标节点恰好在搜索所进入的分支上时，DFS优于BFS。

深度优先搜索不完备，宽度优先搜索完备。
遗传算法的“智能式搜索”主要体现在哪些方面？
为什么说遗传算法是一种“智能式搜索”，又是一种“渐进式优化搜索”？

智能式搜索：遗传算法的搜索策略，既不是盲目式的乱搜索，也不是穷举式的全面搜索，它是有指导的搜索。指导遗传算法执行搜索的依据是适应度，也就是它的目标函数。利用适应度，使遗传算法逐步逼近目标值。

渐进式优化搜索：遗传算法利用复制、交换、突变等操作，使新一代的结果优越于旧一代，通过不断迭代逐渐得出最优的结果，它是一种反复迭代的过程。
举例说明大型应用软件系统开发过程中采用的软件技术（体系）架构是如何体现框架理论知识表示思想的。

人们将相同类型问题的解决途径进行抽象，抽取成一个应用框架，并提供了一套明确的机制让开发人员很容易地扩展和控制整个框架开发的结构。

比如，MFC是一个应用程序的编程框架，三类文件：app,view,doc，编译运行机制：消息映射
简要说明粒子群优化算法PSO与遗传算法GA的共性和差异。

共性：
- 都属于仿生算法
- 都属于全局优化方法
- 都属于随机搜索算法
- 都隐含并行性
- 根据个体的适应信息进行搜索，因此不受函数约束条件的限制，如连续性、可导性等
- 对高维复杂问题，往往会遇到早熟收敛和收敛性能差的缺点，都无法保证收敛到最优点
差异：
- PSO有记忆，所有粒子都保存较优解的知识；GA以前的知识随着种群的改变被改变
- PSO的粒子是一种单向共享信息机制；GA的染色体之间相互共享信息，使得整个种群都向最优区域移动
- GA需要编码和遗传操作；PSO没有交叉和变异操作，粒子只是通过内部速度进行更新，因此原理更简单、参数更少、实现更容易
影响算法A启发能力的重要因素有哪些？

路径的耗散值；求解路径时所扩展的节点数；计算h所需的工作量
简述$\alpha-\beta$过程的剪枝规则。

$\alpha$剪枝：设MAX节点的下限为$\alpha$，则其所有的MIN子结点中，其评估值$\beta \le \alpha$的节点被剪枝

$\beta$剪枝：设MIN节点的上限为$\beta$，则其所有的MAX子结点中，其评估值$\alpha \ge \beta$的节点被剪枝
朴素贝叶斯分类器算法思想的理论依据。

假设属性之间条件独立，朴素贝叶斯模型：
$\begin{align} &P(Y=y|X_1=x_1,X_2=x_2,...,X_n=x_n)\\ =&\frac{P(X_1=x_1,...,X_n=x_n|Y=y)P(Y=y)}{P(X_1=x_1,...,X_n=x_n)}\\ =&\frac{P(Y=y)\Pi_{j=1}^mP(X_j=x_j|Y=y)}{P(X_1=x_1,..,X_n=x_n)} \end{align}$
那么：
$P(Y=y|X_1=x_1,X_2=x_2,...,X_n=x_n)\varpropto P(Y=y)\Pi_{j=1}^mP(X_j=x_j|Y=y)$
给定输入$x=[x_1,x_2,…,x_n]$，朴素贝叶斯分类器的输出结果为：
$\arg\max_{y\in\{1,...,k\}}(P(y)\Pi_{j=1}^m{P_j(x_j|y)})$
举例说明决策树如何代表实例属性值约束的合取的析取式。

从树根到树叶的每一条路径对应一组属性值的合取，树本身对应这些合取的析取。
在主观贝叶斯方法中，为什么LS,LN不能同时大于1或小于1，但可以出现LS,LN等于1的情况。

由公式 $LS=\frac{P(A|B)}{P(A|\neg B)},\ LN=\frac{P(\neg A|B)}{P(\neg A|\neg B)}$
$\begin{align} LS>1 &\Leftrightarrow \frac{P(A|B)}{P(A|\neg B)}>1 \\ &\Leftrightarrow P(A|B)>P(A|\neg B) \\&\Leftrightarrow 1-P(A|B)<1-P(A|\neg B)\\&\Leftrightarrow \frac{P(\neg A|B)}{P(\neg A|\neg B)}<1\\&\Leftrightarrow LN<1 \end{align}$

LS(Likelihood Sufficiency) 充分似然率：表示A为真时对B的影响（规则成立的充分性）
$LS=\frac{O(B|A)}{O(B)}=\frac{P(A|B)}{P(A|\neg B)}=\frac{\frac{P(B|A)}{P(\neg B|A)}}{\frac{P(B)}{P(\neg B)}}$
LN(Likelihood Necessity) 必要似然率：表示A为假时对B的影响（规则成立的必要性）
$LN=\frac{O(B|\neg A)}{O(B)}=\frac{P(\neg A|B)}{P(\neg A|\neg B)}=\frac{\frac{P(B|\neg A)}{P(\neg B|\neg A)}}{\frac{P(B)}{P(\neg B)}}$

几率函数$O(X)$
$O(X)=\frac{P(X)}{1-P(X)}=\frac{P(X)}{P(\neg X)}$
在确定性方法CF的推理模型中，规则$A\to B$的可信度表示为CF(B,A)，分析CF(B,A)取值范围及表示的意义。
$CF(B,A)=\begin{cases} \frac{P(B|A)-P(B)}{1-P(B)},when\ P(B|A)\ge P(B)\\ \frac{P(B|A)-P(B)}{P(B)},when\ P(B|A)<P(B) \end{cases}$
证据为真时，为相对于$P(\neg B)$而言A对B为真的支持程度，即A发生更支持B发生，此时$CF(B,A)\ge 0$

反之，为相对于$P(B)$而言A对B为真的不支持程度，即A发生不支持B发生，此时$CF(B,A)<0$

结论：$-1\le CF(B,A)\le 1$
在贝叶斯网络推理计算中，什么叫D分离？有哪些情况？对推理有什么作用？

如果节点$V_i,V_j$之间所有的路径都被阻塞，就叫证据集合$\epsilon$可以D分离$V_i,V_j$。

D分离是寻找网络节点之间条件独立的有效方法
在粒子群优化算法的速度更新公式中惯性权重w的作用是什么？

使粒子保持运动惯性，使其有扩展空间的趋势，有能力探索新的区域；

表示微粒对当前自身运动状态的信任，依据自身的速度进行惯性运动；

较大的w有利于跳出局部极值，较小的w有利于算法收敛。
在遗传算法的复制操作中，依据轮盘赌方式选择复制对象，给出下表中随机数所选中的个体。
变形空间与候选消除的算法思想及实例分析。变形空间与候选消除学习算法的归纳偏置又是什么？

候选消除算法的归纳偏置：目标概念在给定的假设空间中
给出粒子群优化算法的“速度”和“位置”更新公式，并对公式的每部分给出解释。
在粒子群优化算法的“速度”更新公式中有加速常数c1和c2，一般将c1和c2统一为一个控制参数，$\phi=c1+c2$。如果$\phi$很小（如0.1），粒子群运动轨迹将非常缓慢，如果$\phi$很大（如100），则粒子群位置变化非常快。请对这种现象结合粒子群的“速度”更新公式给出你的解释分析。

如果$\phi$很小，则“认知部分”和“社会部分”的变化会很小，所以粒子群运动轨迹将非常缓慢；如果$\phi$很大，则“认知部分”和“社会部分”的变化会很大，所以粒子群位置变化非常快。
如图是贝兹德克于1994年提出的一种A,B,C智能模型，用于表示神经网络、模式识别和智能之间的关系，根据你的理解对该模型给出分析解释。

计算智能是一种智力方式的底层认知，它与人工智能的区别是认知层次从中层下降到底层而已。中层系统含有知识，底层系统没有知识。
假设：命题S(smoker)：该患者是一个吸烟者；命题C(coal miner)：该患者是一个煤矿矿井工人；命题L(lung cancer)：肺癌患者；命题E(emphysema)：肺气肿患者。建立如图贝叶斯网络，给定患者是一个吸烟者S，计算他患肺气肿E的概率P(E|S)。S称作推理的证据，E叫询问结点。
已知：证据$A_1,A_2$必然发生，且$P(B_1)=0.02$。规则如下：

$R_1: A_1\to B_1 \ LS=10 \ LN=1$

$R_2: A_2\to B_1 \ LS=400 \ LN=1$

求结论$B_1$的更新值$P(B_1|A_1A_2)$
已知：$R_1: A_1\to B_1\ CF(B_1,A_1)=0.6$

$R_2:A_2\to B_1\ CF(B_1, A_2)=0.5$

$R_3:B_1\wedge A_3\to B_2\ CF(B_2,B_1\wedge A_3)=0.8$

$CF(A_1)=CF(A_2)=CF(A_3)=1;\ CF(B_1)=CF(B_2)=0$

计算$CF(B_1), CF(B_2)$并画出推理网络
利用遗传算法求下列函数的极值$f(x_1,x_2)=21.5+x_1\cdot \sin(4px_1)+x_2\cdot\sin(20px_2)$，其中$-3.0\le x_1\le 12.1,\ 4.1\le x_2\le 5.8$

要求计算结果精确到小数点后第4位，请完成编码，并举例说明如何解码？
课本、课件或实验中关于产生式系统描述的例子（如八数码难题、野人传教士、走迷宫、水壶装水等问题），见课件、课本、实验指导书。