转载

山东大学人工智能课程复习提要（2017）

本篇博客为山东大学人工智能课程（2016-2017）的复习提要，希望对大家的考试复习有所帮助。

填空部分

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

简答部分

人工智能方法与传统程序的不同有哪些？

答：传统方法解决问题利用已有知识 , 问题可以方便的结构化数据结构 , 数学形式表达，数学公式、算法。利用知识特别是依赖人类经验的启发知识是人工智能方法与传统数学方法的根本不同之处，基于此，人工智能可以解决众多的难以数学表达的非结构化的实际问题 , 人工智能首先研究的是以符号表示的知识 , 而不是数值为研究对象 , 其次采用的是启发式推理的方法而不是常规的算法 , 控制结构和领域知识是分离的，同时还允许出现相对正确的答案。
在与或图的问题求解过程中，哪几类节点称为能解节点?

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

答：宽度优先搜索就是逐层穷举搜索。深度优先搜索就是分支优先搜索待搜索问题的解存在且关键路径较短时宽度优先搜索优于深度优先搜索;待搜索问题的解存在且关键路径较长，而深度优先搜索过程中优先发展的正好是解所在的路径时深度优先搜索优于宽度优先搜索。宽度优先搜索是完备的。
举例解释语义网络(Semantic Network)与知识图谱(Knowledge graph)的区别与联系。

答：知识图谱是通过将数学、图形学、可视化技术、信息科学等的理论与方法与计量学的引文分析、共现分析等方法结合，并利用可视化的图谱形象地展示知识体系的方法。它把复杂的知识领域通过数据挖掘、信息处理、知识计量和图形绘制而显示出来，揭示知识领域的动态发展规律，为学科研究供切实的、有价值的参考。据不完全统计，Google 知识图谱到目前为止包含了 5 亿个实体和 35 亿条事实(形如实体-关系-实体，和实体-属性值)。

语义网络特点 (1) 结构性好: 语义网络是一种结构化的知识表示方法，它能够把事物的属性和事物间的各种语义关系显示地表示出来; (2)联想性: 语义网络作为人类联想记忆模型提出来，强调的就是事物之间的语义关系。 (3)自然性: 语义网络实际上是一个带有标示的有向图，可直观的把事物的属性及事物间的语义联系表示出来，便于理解。利用语义网络表示知识的问题有:自然语言理解，问答系统，专家系统等。缺点:推理规则不十分明显，表达范围有限，一旦结点个数太多，网络结构复杂。
举例说明大型应用软件系统开发过程中采用的软件技术(体系)架构是如何体现框架理论知识表示思想的。

答：软件开发过程中框架理论的使用软件框架(架构)特点: 为某一特定目的实现一个基本的、可执行的构架；包含了应用程序从启动到运行的主要流程；流程中那些无法确定的步骤留给用户来实现；程序运行时框架系统自动调用用户实现的功能组件；系统的行为是主动的。

软件开发过程中框架理论的使用：人们将相同类型问题的解决途径进行抽象，抽取成一个应用框架 Framework；提供了一套明确机制；让开发人员很容易的扩展和控制整个 Framework 开发上的结构。

软件开发过程中框架理论的使用：

系统级框架： MFC 框架、 .NET 中的应用框架、 JavaAWT

中间件框架： Spring 框架、 Struts 框架、 Hibernate 框架、 EXTjs 框架

企业应用框架为不同行业的应用开发专用的企业级框架系统：JBOSS, eBOSS, websphere等

软件开发过程中框架理论的使用：

Struts 框架: Struts 对 Model，View 和 Controller 都提供了对应的组件;

Mode 槽:ActionForm 和 JavaBean 组成;

View 槽: JSP(或 HTML、PHP……)实现;

Controller 槽:核心控制器，业务逻辑控制器。
简要说明粒子群优化算法与遗传算法的共性和差异。

共性：( 1 )都属于仿生算法;( 2 )都属于全局优化方法;( 3 )都属于随机搜索算法;( 4 )都隐含并行性;( 5 )根据个体的适配信息进行搜索，因此不受函数约束条件的限制，如连续性、可导性等;( 6 )对高维复杂问题，往往会遇到早熟收敛和收敛性能差的缺点，都无法保证收敛到最优点。

差异：(1) PSO 有记忆，所有粒子都保存较优解的知识，而 GA ，以前的知识随着种群的改变被改变; (2) PSO 中的粒子是一种单向共享信息机制。而 GA 中的染色体之间相互共享信息，使得整个种群都向最优区域移动; (3) GA 需要编码和遗传操作，而 PSO 没有交叉和变异操作，粒子只是通过内部速度进行更新，因此原理更简单、参数更少、实现更容易。
影响算法 A 启发能力的重要因素有哪些。

( 1 )路径的耗散值; ( 2 )求解路径时所扩展的节点数; ( 3 )计算 h 所需的工作量。

因此选择 h 函数时，应综合考虑这些因素以便使启发能力最大
决策树学习法与神经网络学习法的区别。

决策树是知识一种图形符号表示，能表示与或规则;形象直观地图形符号

神经网络学习是非图形符号表示法，是一种函数表示法;从大量的数据中抽取规则函数
为什么说遗传算法是一种“智能式搜索”，又是一种“渐进式优化搜索”。

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

渐进式优化 : 遗传算法利用复制、交换、突变等操作，使新一代的结果优越于旧一代，通过不断迭代，逐渐得出最优的结果，它是一种反复迭代的过程
简述α-β过程的剪枝规则。

后辈节点的值≤祖先节点的值时，α剪枝

后辈节点的值≥祖先节点的值时，β剪枝
简述关于群智能理论(算法)研究存在那些问题。

数学理论基础相对薄弱，涉及的各种参数设置没有确切的理论依据带有随机性，每次的求解不一定一样，当处理突发事件时，系统的反映可能是不可预测的，这在一定程度上增加了其应用风险。