人工智能复习资料.docx

人工智能复习资料.docx

《人工智能复习资料.docx》由会员分享，可在线阅读，更多相关《人工智能复习资料.docx（24页珍藏版）》请在冰点文库上搜索。

人工智能复习资料

第一章绪论

1.1人工智能的定义与发展

①人工智能的定义：

A、（学科）人工智能是计算机科学中，涉及研究、设计和应用智能机器的一个分支；

B、（能力）人工智能是智能机器所执行的、通常与人类智能有关的智能行为，如判断、推理、证明、识别、感知、理解、通信、设计、思考、规划、学习和问题求解等思维活动。

②起源与发展（三个阶段：

孕育期、形成期、发展期）

③人工智能之父：

图灵

④人工智能系统：

是一个知识表示系统（三个基本问题：

知识的表示、利用、获取）

⑤专家系统与知识工程之父：

费根鲍姆

1.2人类智能与人工智能

①人类认知活动与计算机的比较：

3个层次：

人类：

思维策略、初级信息处理、生理过程；

计算机：

计算机程序、计算机语言、计算机硬件；

研究认知过程的主要任务：

3；

人工智能的研究任务：

按照人类的思维来编制计算机程序的这项工作；

②信息处理系统/符号操作系统/物理符号系统：

符号：

模式；

基本功能和任务：

辨认相同的符号、区别不同的符号；

具有6种基本功能：

输入符号、输出符号、存储符号、复制符号、建立符号结构、条件性迁移；

物理符号系统的1个假设（智能—系统）和3个推论（人—计算机）

③对认知本质的研究：

4个层次：

认知生理学（人的神经系统）、认知心理学（人的思维策略）、认知信息学（生理活动与心理活动的相互转变）、认知工程学（认知行为的加工处理）

④为什么能够用机器（计算机）模仿人的智能？

由于人和计算机都是一个物理符号系统，并且这两个物理符号系统所使用的物理符号是相同的，因而可以用计算机来模仿人类智能。

⑤智能计算机（下棋、定理证明、语言翻译）、新型智能计算机（神经计算机、量子计算机）

⑥人工智能的研究目标：

近期：

建造智能计算机代替人类的部分智力活动；远期：

用自动机来模仿人类的思维过程和智能行为；

1.3人工智能各学派的认知观（名称、源于、原理）

①符号主义（主流派别）；数理逻辑；基于物理符号系统假设和有限合理性原理；

连接主义；仿生学；基于神经网络及其间的连接机制与学习算法；

行为主义；控制论；基于控制论及感知——动作型控制系统；

1.4人工智能的研究与应用领域

①人工智能的基本技术：

知识表示、状态空间法、问题归约法、谓词逻辑法…

②推理搜索：

启发式搜索、消解原理、不确定性推理…

③计算智能：

模糊计算、神经计算、进化计算…

④构成技术（系统与语言）：

产生式系统、LISP语言、Prolog语言…

⑤人工智能的主要研究和应用领域：

问题求解、逻辑推理与定理证明、自然语言理解、自动程序设计、专家系统、模式识别、机器学习、机器人学、机器视觉、智能控制、智能检索、智能调度与指挥、神经网络、计算智能与进化计算、数据挖掘与知识发现、分布式人工智能与Agent、人工生命、系统与语言工具

第二章知识表示与推理

2.1知识表示的一般方法

①一般计算机科学：

数据结构+算法；

人工智能：

（知识表示+搜索）+推理；搜索过程即推理过程；

②以符号和逻辑为基础的传统人工智能的问题求解：

通过知识表示和知识推理而实现的；

③问题求解：

两方面：

问题的表示、求解的方法

④知识表示方法：

状态空间法（状态、算符）、问题归约法（目标、逆向）、谓词逻辑法（合式公式、消解算法）、语义网络（节点表示概念、弧表示关系）、框架（层次：

槽、侧面）、剧本（场景、角色、事件）、过程

2.2图搜索策略

①图搜索控制策略：

一种在图中寻找路径的方法。

图中每个节点对应一个状态，每条连线对应一个操作符。

这些节点和连线（即状态与操作符）又分别由产生式系统的数据库和规则来标记。

求得把一个数据库变换为另一数据库的规则序列问题就等价于求得图中的一条路径问题。

②图搜索的一般过程：

P27

③搜索图与搜索树

④OPEN表：

未扩展节点；CLOSED表：

已扩展节点；包括：

在搜索树中没有生成后继节点的端节点、搜索树的非端节点；

⑤重排OPEN表：

原则和意义：

按照某个试探值（或准则、启发信息）重新对未扩展节点进行排序，将决定该图搜索过程是无信息搜索还是启发式搜索。

2.3一般搜索与推理技术

①盲目搜索：

特点：

不需重排OPEN表；种类：

宽度优先、深度优先、等代价搜索；

启发式搜索：

特点：

重排OPEN表，选择估价函数，对最有希望的节点加以扩展；种类：

有序搜索、A*算法、AO*算法等；

②问题的搜索：

正向搜索、逆向搜索、双向搜索

③启发式搜索：

A、为什么用启发式搜索？

盲目搜索效率低，耗费过多的计算空间与时间，这是组合爆炸的一种表现形式。

B、定义：

进行搜索技术一般需要某些有关具体问题领域的、特性的信息，把此种信息叫做启发信息。

利用启发信息的搜索方法叫做启发式搜索方法。

C、沿着被认为是最有希望通向目标的最佳路径向外扩展。

2.4A*算法

①估价函数：

为获得某些节点“希望”的启发信息，提供一个评定侯选扩展节点的方法，以便确定哪个节点最有可能在通向目标的最佳路径上。

②估计函数f：

f（n）估算从节点S0到节点n的最小代价路径的代价：

g（n）与从节点n到某一目标节点的最小代价路径的代价h（n）之总和；即：

f（n）是约束通过节点n的一条最小代价路径的代价的一个估计；

③k（n,t）、k（S,n）

④f是f*的一个估计：

f*（n）=g*（n）+h*（n）f（n）=g（n）+h（n）；

估计函数：

f；启发函数：

h；g（n）≥g*（n）

⑤A*算法的定义：

A、在GRAPHSEARCH过程中，如果第8步的重排OPEN表是依据f（x）=g（x）+h（x）进行的，则称该过程为A算法。

B、在A算法中，如果对所有的x存在h（x）≤h*（x）,则称h（x）为h*（x）的下界，它表示某种偏于保守的估计。

C、采用h*（x）的下界h（x）为启发函数的A算法，称为A*算法。

当g=0时，A*算法就变为有序搜索算法；h=0时，A*算法就变为等代价搜索算法。

⑥A*算法步骤：

P30

2.5消解原理

①原子公式：

P（x）、Q（x,y）；

文字：

一个原子公式及其否定。

～P（x）、R（x,y,z）；

子句：

由文字的析取组成的合式公式。

P（x）∨～Q（x,y）；

消解：

对谓词演算公式进行分解和化简，消去一些符号，以求得导出子句。

②消解原理：

归结原理、推理规则；从公式集证明某个定理，将公式集化为子句集，利用消解作为推理规则。

③消解：

如果存在某个公理E1∨E2和另一公理～E2∨E3，那么E1∨E3在逻辑上成立，这就是消解；称E1∨E3是E1∨E2和～E2∨E3的消解式；

④子句集的求解：

共9个步骤：

消去蕴含符号、减少否定符号的辖域（否定内移）、对变量标准化（哑元；同一辖域内重名；保证每个量词有其自己唯一的哑元）、消去存在量词（Skolem函数；g（x）、A）、化为前束形（全称量词外移）、把母式化为合取范式（分配律：

A∨{B∧C}—>{A∨B}∧{A∨C}）、消去全称量词（直接消去）、消去连接符号∧（更改表示形式）、更换变量名称（使一个变量符号不出现在一个以上的子句中）

前束形：

{前缀}{母式}->（全称量词串；无量词公式）

⑤文字基例：

一个表达式的变量被不含变量的项所置换，得到文字基例。

⑥消解推理规则：

令L1，L2为两任意原子公式；L1和L2具有相同的谓词符号，但一般具有不同的变量。

已知两子句L1∨α和～L2∨β,如果L1和L2具有最一般合一σ，那么通过消解可以从这两个父辈子句推导出一个新子句（α∨β）σ。

这个新子句叫做消解式。

⑦含有变量的消解式：

使用消解规则前，找到一个置换作用于父辈子句，使其含有互补文字；置换σ={f（y）/x}，所有出现的地方均要置换，｛函数/变量｝、｛常量/变量｝、｛变量/变量｝

⑧消解反演：

证明思想：

要证明某个命题，其目标公式被否定并化成子句形，然后添加到命题公式集中去，把消解反演系统应用于联合集，并推导出一个空子句（NIL），产生一个矛盾，从而使定理得到证明。

⑨证明步骤（给出{S0}，L）：

（把前提化为子句形，把～L化为子句形，消解反演求NIL）

否定L，得～L；把～L添加到S0中去；

把新产生的集合｛～L，S0｝化成子句集；

应用消解原理，力图推导出一个表示矛盾的空子句；

⑩反演求解过程：

A、从反演树求取答案步骤：

把由目标公式的否定产生的每个子句添加到目标公式否定之否定的子句中去（～L∨L）；按照反演树，执行和以前相同的消解，直至在根部得到某个子句止；用根部的子句作为一个回答语句。

B、实质：

把一棵根部有NIL的反演树变换为根部带有回答语句的一棵证明树。

C、关键：

把问题化为一个包含某个存在量词的目标公式，使得此存在量词量化变量表示对该问题的一个解答。

D、L：

参加置换，不会被消解，最后剩下，同时x被求出。

⑪先证明，再求解

⑫含状态项的回答语句的求取→

⑬含有状态项的谓词公式证明：

A、状态：

用谓词公式集描述问题状态（合式公式集、状态空间）。

B、算符：

包括：

适应性公式（条件）、变换规则（删除表列、添加表列、$代表任意项）。

C、搜索过程：

检验结论是否可从初始状态得到；将可适用算符施于初始状态S0极其后裔，直至产生出某个包含目标谓词H的状态为止；

->添加、删除、设定（代替：

每一个出现的都要，得到某一算符的适应性公式的适用一例）。

⑭含有状态项的谓词公式求解：

A、状态：

谓词公式集：

把某个状态项添加到每个谓词上，指定该状态为谓词作用到的状态。

B、算符：

将一种状态映射到另一种状态（新状态）的函数；作用：

对状态进行替换；

适用性公式∧适用性公式…　→　变换规则（算符（算符当前作用到的状态S））

C、回答语句：

以算符函数的组合形式表示的目标状态表达式。

⑮先证明（反演证明树），再求解（从证明树求解或建立求取答案的反演树）

2.6产生式系统

①定义：

用来描述若干个不同的以一个基本概念为基础的系统。

这个基本概念就是产生式规则或产生式条件和操作对的概念。

②实质：

在产生式系统中，论域的知识分为两部分：

用事实表示静态知识，如事物、事件和它们之间的关系；用产生式规则表示推理过程和行为。

由于这类系统的知识库主要用于存储规则，因此又把此类系统称为基于规则的系统。

③基本形式：

IF前提THEN结论

④组成：

A、一个总数据库：

它含有与具体任务有关的信息。

B、一套规则：

它对数据库进行操作运算。

每条规则由左右两部分组成，左部鉴别规则的适用性或先决条件，右部描述规则应用时所完成的动作。

应用规则来改变数据库。

C、一个控制策略：

它确定应该采用哪一条适用规则，而且当数据库的终止条件满足时，就停止计算。

（事实、前提、匹配、被激活、结论、新的事实）

⑤控制策略主要任务：

A、按一定策略，从规则库中选择与总数据库中的已知事实相匹配的规则。

B、当存在多条匹配成功的规则时，控制策略能够按照某种策略从中选出一条适合的规则去执行。

C、如果要执行的规则的右部不是问题的目标，且为一个或多个结论时，则把这些结论（即中间事实）加入到总数据库中；当其为一个或多个操作时，执行这些操作。

D、如果要执行的规则的右部满足问题的结束条件，则停止推理。

E、记住问题求解过程中应用过的规则序列，以便求解结束时能够给出问题的解答路径。

⑥选择规则到执行操作分3步：

匹配、冲突解决、操作

⑦按照搜索方向可分为：

正向推理（事实驱动）、逆向推理（目标驱动）、双向推理（中间实现事实与目标的匹配）

⑧匹配时：

对变量的统一置换，规则左部、右部、事实

⑨正向推理：

从一组表示事实的谓词或命题出发，使用一组产生式规则，用以证明该谓词公式或命题是否成立。

（策略P58）直到没有可匹配的新规则，不再有新的事实加入到数据库中为止。

⑩逆向推理：

从表示目标的谓词或命题出发，使用一组产生式规则证明事实谓词或命题成立，即首先提出一批假设目标，然后逐一验证这些假设。

（策略P58）假设目标、前提作为新的假设目标（假设子目标）、终叶节点

⑪双向推理：

双向推理的推理策略是同时从目标向事实推理和从事实向目标推理，并在推理过程中的某个步骤，实现事实与目标的匹配。

⑫正向推理与逆向推理的比较：

（定义、特点、优点、缺点、适用于）

第三章高级知识推理

3.1经典推理和非经典推理

①经典推理和非经典推理的比较，有什么不同？

经典逻辑

非经典逻辑

推理方法

演绎逻辑推理

归纳逻辑推理

辖域取值

二值逻辑（真、假）

多值逻辑

运算法则

数理逻辑法则

特殊法则

逻辑算符

∧∨～≣

模态算符

单调性

单调的

非单调的

②传统的人工智能（即逻辑学派）是建立在符号逻辑推理的基础上的。

逻辑（涉及思维的规范）和推理（涉及思维的法则）是以逻辑为基础的人工智能的两个基石。

③目前用得较多的不精确推理模型有：

概率推理、贝叶斯推理、可信度方法、证据理论、模糊推理等。

3.5概率推理

①随机事件、必然事件、不可能事件；

事件的概率：

事件发生的可能性大小，记为P（A）。

②概率的6个基本性质：

A、对任何事件A，有：

0≤P（A）≤1

B、必然事件D：

P（D）=1；不可能事件Φ：

P（Φ）=0

C、任意两个事件A和B：

P（A∩B）=P（A）+P（B）-P（A∩B）

D、若Ai∩Bj=（i≠j），则P（∩Ai）=P（A1）+…+P（An）

E、若AB，P（A\B）=P（A）-P（B）

F、P（～A）=1-P（A）

③概率的常用计算公式：

A、条件概率：

P（A|B）=P（A∩B）/P（B）（当P（B）>0）

P（A|B）=0（当P（B）=0）

B、乘法公式（变换）：

P（A∩B）=P（B）*P（A|B）=P（A）*P（B|A）（当P（A）>0，P（B）>0）

P（A1A2…An）=P（A1）P（A2|A1）P（A3|A1A2）…P（An|A1A2…An-1）

（当P（A1A2…An-1）>0；P（A1∩A2∩…∩An）简写为：

P（A1A2…An））

C、独立性公式：

P（A|B）=P（A），则称事件A关于事件B是独立的。

这时若P（A）与P（B）同时大于0，则P（B|A）=P（B），称A、B相互独立。

A与B相互独立的充要条件：

P（A∩B）=P（A）*P（B）

D、全概率公式：

若Bi∩Bj=（互斥，不同时发生）；P（∪Bi）=1；P（Bi）>0

则：

P（A）=ΣP（A|Bi）P（Bi）（i=1,2,…）

F、贝叶斯公式：

⑥概率推理方法→

⑦产生式规则（以表示知识）：

IFETHENH

已知：

P（E）、P（H）、P（E|H）。

→证据E（前提条件）的不确定性概率为P（E）、H的先验概率P（H）、条件概率P（E|H）；

概率方法不确定推理的目的就是：

求在证据E下，结论H发生的概率P（H|E）。

⑧若：

ifEthenH，已知：

P（E），P（H），P（E|H），求P（H|E）？

若：

ifEthenHj，（j=1,2,…,n），已知：

P（Hj），P（E|Hj），求P（Hi|E）？

若：

if（E1∧E2∧…∧Em）thenHi，（i=1,2,…,n），求P（Hi|E1E2…Em）？

⑨优点：

具有较强的理论基础和较好的数学描述。

不足：

要求给我先验概率P（Hi）和条件概率P（E|Hi），获得这些概率数据相当困难；

要求各事件彼此独立；

3.6主观Bayes方法

①知识不确定性的表示

②产生式规则（以表示知识）：

IFETHEN（LS,LN）H

（LS,LN）：

表示知识的静态强度。

LS：

该式成立的充分性因子；衡量E对结论H的支持程度；（证据/前提：

E）

LN：

该式成立的必要性因子；衡量～E对结论H的支持程度；

③LS=P（E|H）/P（E|～H）

LN=P（～E|H）/P（～E|～H）=[1-P（E|H）]/[1-P（E|～H）]

④O（X）：

X的几率，等于X的概率与X不出现的概率之比。

将取值为[0,1]的P（X）放大为取值[0,+）的O（X）。

⑤修改的贝叶斯公式：

O（H|E）=LS*O（H）

O（H|～E）=LN*O（H）

当E为真时，可利用LS将H的先验概率O（H）更新为其后验概率O（H|E）；

当E为假时，可利用LN将H的先验概率O（H）更新为其后验概率O（H|～E）；

⑥由上式可得一些结论：

A、LS越大，O（H|E）就越大，P（H|E）也越大。

若LS，则O（H|E），P（H|E）1

若LS0，则O（H|E）0，P（H|E）0

若LS=1，则O（H|E）=O（H）,P（H|E）=P（H）无关

B、LN越大，O（H|～E）就越大，P（H|～E）也越大。

若LN，则O（H|～E），P（H|～E）1

若LN0，则O（H|～E）0，P（H|～E）0

若LN=1，则O（H|～E）=O（H）,P（H|～E）=P（H）无关

⑦证据不确定性的表示

⑧对初始证据的观察:

S概率（动态强度）:

P（E|S）初始证据的可信度:

C（E|S）

⑨初始证据的获取：

（概率投影）

⑩杜达公式（duda）：

P（H|S）=P（H|E）P（E|S）+P（H|～E）P（～E|S）

A、当P（E|S）=1时:

P（～E|S）=0，P（H|S）=P（H|E）

B、当P（E|S）=0时:

P（～E|S）=1，P（H|S）=P（H|～E）

C、当P（E|S）=P（E）时：

P（H|S）=P（H）

⑪EH公式：

（当前已知中间结论，由推理过程中得到）

⑫CP公式：

（当前已知初始证据，由用户给出）

⑬主观贝叶斯方法的推理过程：

如果有n条知识都支持结论H，而且每条知识的前提条件分别是n个相互独立的证据E1,E2,…,En，而且这些证据又分别与观察S1,S2,…,Sn相对应。

可先对每条知识分别求出H的后验概率O（H|Si），然后再按一下公式求出所有观察下H的后验概率：

⑭主观贝叶斯方法的优缺点：

优点：

（1）建立在概率论的基础上，具有比较坚实的理论基础；

（2）LS、LN由领域专家给出，比较全面地反映了证据与结论间的因果关系；（3）在证据不确定的情况下，更新先验概率为后验概率，实现了不确定性的逐级传递；

缺点：

（1）需要给出H的先验概率P（H）；

（2）要求各事件彼此独立；

3.7可信度方法

①可信度：

根据经验对一个事物或现象为真的相信程度。

不确定性用可信度表示，知识用产生式规则表示。

②知识不确定性的表示：

③此方法中产生式规则形式：

IFETHENH（CF（H,E））

④CF（H,E）：

规则的可信度，称为可信度因子或规则强度。

往往是专家根据经验给出的。

作用域：

CF（H,E）[-1,1]；CF（H,E）越大，H越真。

一些结论：

CF（H,E）=1，则结论H为真；

CF（H,E）>0，证据E增加了结论H为真的程度；

CF（H,E）=0，则结论H与证据E无关；

CF（H,E）<0，证据E增加了结论H为假的程度；

CF（H,E）=-1，则结论H为假。

⑤CF（H,E）=MB（H,E）-MD（H,E）

信任增长度：

MB（H,E）当MB（H,E）>0时，P（H|E）>P（H）；

不信任增长度：

MD（H,E）当MD（H,E）>0时，P（H|E）

⑥定义：

MB（H,E）

⑦MB,MD的性质：

A、0≤MB（H,E）≤1；0≤MD（H,E）≤1；-1≤CF（H,E）≤1

B、MB与MD是互斥的：

当MB（H,E）>0时，MD（H,E）=0，CF（H,E）=MB（H,E）>0；支持

当MD（H,E）>0时，MB（H,E）=0，CF（H,E）=-MD（H,E）<0；排斥

C、CF（H|E）=0；（没有意义）无关

D、若P（H|E）=1，则MB（H,E）=1，MD（H,E）=0，CF（H,E）=1

若P（H|E）=0，则MD（H,E）=1，MB（H,E）=0，CF（H,E）=-1

若P（H|E）=P（H），则MD（H,E）=0，MB（H,E）=0，CF（H,E）=0

E、若Hi是互不相容的假设，则：

⑧CF（H,E）的计算公式：

（支持、无关、排斥）

⑨对概率有：

P（H|E）+P（～H|E）=1

对可信度有：

CF（H|E）+CF（～H|E）=0

⑩证据不确定性的表示CF（E）是证据的可信度，初始可信度由用户给出。

CF（E）[-1,1]，CF（E）越大，E越真。

CF（E）=1，则证据E为真；

CF（E）>0，证据E以某种程度为真；

CF（E）=0，对证据E一点不知道；

CF（E）<0，证据E以某种程度为假；

CF（E）=-1，则证据E为假。

⑪组合证据的不确定性算法：

A、合取证据

E=E1ANDE2AND…ANDEn

若已知CF（E1）,CF（E2）,…,CF（En），则有：

CF（E）=min{CF（E1）,CF（E2）,…,CF（En）}

B、析取证据

E=E1ORE2OR…OREn

若已知CF（E1）,CF（E2）,…,CF（En），则有：

CF（E）=max{CF（E1）,CF（E2）,…,CF（En）}

⑫不确定性的传递算法：

IFETHENH（CF（H,E））

A、若已知CF（E），则有：

CF（H）=CF（H,E）max{0,CF（E）}

B、CF（E）=1，则CF（H）=CF（H,E）

CF（E）>0，则CF（H）=CF（H,E）CF（E）

CF（E）<0，则CF（H）=0（没有考虑证据为假时对结论的影响。

）

⑬多个独立证据推出同一假设的合成算法：

已知：

IFE1THENH（CF（H,E1））CF1（H）=CF（H,E1）max{0,CF（E1）}

IFE2THENH（CF（H,E2））CF2（H）=CF（H,E2）max{0,CF（E2）}

求:

CF1（H）和CF2（H）合成的可信度CF1,2（H）：

改进：

3.8证据理论（D-S理论）

①证据理论使用集合表示命题的。

D是变量x所有取值的集合，D中各元素是互斥的。

称D为x的样本空间。

D的任何一个子集A都对应于一个关于x的命题：

该命题为：

x的值在A中。

②概率分配函数：

M

A、定义：

设函数：

M:

2D→[0,1]，满足：

M（）=0；

称M是2D上的概率分配函数，M（A）是A的基本概率数。

B、几点说明：

（1）2D表示D中的所有子集；

（2）概率分配函数把D的任意一个子集都映射为[0,1]中数，且总和为1；

（3）概率分配函数不是概率；

③信任函数：

Bel（A）

A、定义：

设函数：

Bel:

2D→[0,1]，对所有AD，满足：

Bel（A）=

B、Bel（A）表示对A命题为真的信任程度。

C、也称下限函数。

D、Bel（）=M（）=0

Bel（D）=1

④似然函数：

A、定义：

设函数：

Pl:

2D→[0,1]，对所有AD，满足：

Pl（A）=1-Bel（～A）（～A=D-A）

B、Bel（～A）表示对A为假的信任程度，Pl（A）表示对A为非假的信任程度。

C、也称上限函数（不可驳斥函数）。

⑤信任函数与似然函数的关系：

Pl（A）≥Bel（A）

⑥记为：

A（Pl（A），Bel（A））：

命题的上限和下限

⑦总结：

Bel（