当前位置:   article > 正文

人工智能复习题_请用相应的谓词公式表示下列语句“如果jones制造了一个传感器,且这个传感器不

请用相应的谓词公式表示下列语句“如果jones制造了一个传感器,且这个传感器不

第一章(选择填空)

1.2  人工智能的定义

人工智能:就是用人工的方法在机器(计算机)上实现的智能;或者说,是人们使用机器模拟人类的智能。

1.3  人工智能研究的方法及途径

(1).研究途径:

第一种观点主张运用计算机科学的方法进行人工智能的研究,通过研究逻辑演绎在计算机上的实现方法,实现人类智能在计算机上的模拟。这种观点称为符号主义。其原理主要为物理符号系统假设和有限合理性原理。

第二种观点主张用仿生学的方法进行研究,通过研究人脑的工作模型,搞清楚人类智能的本质,这种观点称为联结主义。其原理主要为神经网络及神经网络间的连接机制与学习算法。

第三种观点主张应用进化论的思想进行人工智能的研究,通过对外界事物的动态感知与交互,使计算机智能模拟系统逐步进化,提高智能水平,这种观点称为行为主义。其原理主要是通过控制论和机器学习算法实现智能系统的逐步进化。

(2).技术途径:(了解

专用路线,通用路线,硬件路线,软件路线

1.4  人工智能的应用领域

  问题求解,机器学习,专家系统,识别模式,自动定理证明,自动程序设计,自然语言理解,机器人学,智能检索。

1.5  课后习题

1. 什么是人类智能?它有哪些特征或特点?

定义:人类所具有的智力和行为能力。

特点:主要体现为感知能力、记忆与思维能力、归纳与演绎能力、学习能力以及行为能力。

2. 什么是人工智能?它的研究目标是什么?

定义:用机器模拟人类智能。

研究目标:用计算机模仿人脑思维活动,解决复杂问题;从实用的观点来看,以知识为对象,研究知识的获取、知识的表示方法和知识的使用。

3. 人工智能有哪些主要研究领域?

解:问题求解、专家系统、机器学习、模式识别、自动定论证明、自动程序设计、自然语言理解、机器人学、人工神经网络和智能检索等。

4. 人工智能有哪几个主要学派?各自的特点是什么?

主要学派:符号主义和联结主义。

特点:符号主义认为人类智能的基本单元是符号,认识过程就是符号表示下的符号计算,从而思维就是符号计算;联结主义认为人类智能的基本单元是神经元,认识过程是由神经元构成的网络的信息传递,这种传递是并行分布进行的。

5. 什么是以符号处理为核心的方法?它有什么特征?

解:通过符号处理来模拟人类求解问题的心理过程。

特征:基于数学逻辑对知识进行表示和推理。

6. 什么是以网络连接为主的连接机制方法?它有什么特征?

解:用硬件模拟人类神经网络,实现人类智能在机器上的模拟。

特征:研究神经网络。

 

第二章

2.1 概述

  2.1.2 知识的特性

(1)相对正确性: (2)不确定性: (3)可表示性: (4)可利用性

  2.1.3 知识的分类

(1)以知识的作用范围来划分,知识可分为常识性知识和领域性知识

(2)就知识的作用及表示来划分,可分为事实性知识、规则性知识、控制性知识和元知识

(3)以知识的确定性来划分,可分为确定知识和不确定知识

(4)按照人类的思维及认识方法来分,可分为逻辑性知识和形象性知识

2.2 一阶谓词逻辑表示法          (计算、课后习题)

  2.2.1 知识的谓词逻辑表示法

事实性知识,谓词逻辑的表示法通常是由以合取符号(∧)和析取符号(∨)连接形成的谓词公式来表示。例如,对事实性知识“张三是学生,李四也是学生”,可以表示为:

ISSTUDENT(张三)∧ISSTUDENT(李四)

这里,ISSTUDENT(x)是一个谓词,表示 x是学生;

规则性知识,谓词逻辑表示法通常由以蕴涵符号连接形成的谓词公式(即蕴涵式)来表示。例如,对于规则:

如果 x,则 y

可以用下列的谓词公式进行表示:

x → y

  2.2.3 谓词公式表示知识的举例(重中之重)

例2.1 设有下列事实性知识:

张晓辉是一名计算机系的学生,但他不喜欢编程序。

李晓鹏比他父亲长得高。

用谓词公式表示这些知识。

解:按照表示知识的步骤,用谓词公式表示上述知识。

第一步:定义谓词如下:

COMPUTER(x):x 是计算机系的学生

LIKE(x,y):x喜欢y

HIGHER(x,y):x比y 长得高

这里涉及的个体有:张晓辉(zhangxh),编程序(programming),李晓鹏(lixp),以函数father(lixp)表示李晓鹏的父亲。

第二步:将这些个体代入谓词中,得到

COMPUTER(zhangxh),~LIKE(zhangxh,programming),

HIGHER(lixp,father(lixp))

第三步:根据语义,用逻辑连接词将它们连接起来,就得到了表示上述知识的谓词公式:

COMPUTER(zhangxh)∧~LIKE(zhangxh,programming)

HIGHER(lixp,father(lixp))

 

例2.2 下列知识是一些规则性知识:

人人爱劳动。

所有整数不是偶数就是奇数。

自然数都是大于零的整数。

用谓词公式表示这些知识。

解:定义谓词如下:

MAN( x):x 是人

LOVE( x,y):x爱y

N( x):x 是自然数

I( x):x 是整数

E(x):x是偶数

O( x):x 是奇数

GZ( x):x 大于零

“人人爱劳动”用谓词公式表示为( x )(MAN( x )→LOVE( x ,labour))

“自然数都是大于零的整数”表示为( x )(N( x )→GZ( x )∧I( x ))

“所有的整数不是偶数就是奇数”表示为( x )(I( x )→E( x )∨O( x ))

 

  2.2.4 一阶谓词逻辑表示法的特点

(1)自然性

(2)适宜于精确性知识的表示,而不适宜于不确定性知识的表示

(3)易实现

(4)与谓词逻辑表示法相对应的推理方法

2.3 产生式表示法(特点:清晰性、模块性、自然性) 

  2.3.2 知识的表示方法

(1)确定性规则知识的产生式表示

确定性规则知识的产生式形式为

P → Q

或者 IF P THEN Q

(2)不确定性规则知识的产生式表示

产生式可用于不确定知识的表示,不确定性规则知识的产生式形式为

P → Q (可信度)

或者 IF P THEN Q (可信度)

(3)确定性事实性知识的产生式表示

事实性知识的表示形式一般使用三元组来表示:

(对象,属性,值)如事实“老李年龄是40岁”,便可表示成

(Li,Age,40)

或者 (关系,对象1,对象2)“老李、老张是朋友”可写成

 (Friend,Li,Zhang)

(4)不确定性事实性知识的产生式表示

不确定事实性知识的表示形式一般使用四元组来表示:

(对象,属性,值,可信度值)

或者 (关系,对象1,对象2,可信度值)

  2.3.3 产生式系统的组成

 

1.规则库:就是用于描述某领域内知识的产生式集合,是某领域知识(规则)的存储器,其中的规则是以产生式形式表示的。

2.综合数据库:又称为事实库,用于存放输入的事实、从外部数据库输入的事实以及中间结果(事实)和最后结果的工作区。

3.推理机:是一个或一组程序,用来控制和协调规则库与综合数据库的运行,包含了推理方式和控制策略。通常从选择规则到执行操作分3步完成:匹配、冲突解决(专一性排序、规则排序、规模排序、就近排序)和操作。

  2.3.4 产生式系统的推理方式(正反向推理)

1.正向推理(数据驱动方式/自底向上的方式)

正向推理是从已知事实出发,通过规则库求得结论。

过程:1)规则库中的规则与综合数据库中的事实进行匹配,得到匹配的规则集合;

(2)使用冲突解决算法,从匹配规则集合中选择一条规则作为启用规则;

(3)执行启用规则的后件,将该启用规则的后件送入综合数据库或对综合数据库进行必要的修改。

重复这个过程直至达到目标。

2.反向推理(目标驱动方式/自顶向下的方式)

反向推理是从目标(作为假设)出发,反向使用规则,求得已知事实。

过程:1)规则库中的规则后件与目标事实进行匹配,得到匹配的规则集合;

(2)使用冲突解决算法,从匹配规则集合中选择一条规则作为启用规则;

(3)将启用规则的前件作为子目标。

重复这个过程直至各子目标均为已知事实,则反向推理的过程就算成功结束。

3.双向推理

既自顶向下又自底向上从两个方向同时进行推理率更高

2.4语义网络表示法 

  2.4.2 语义网络中常用的语义联系   (各种关系重点看一下)

1.类属关系

常用的类属关系有:

AKO:含义为“是一种”(A-Kind-Of),表示一个事物是另一个事物的一种类型。

AMO:含义为“是一员”(A-Member-Of),表示一个事物是另一个事物的一个成员。

ISA:含义为“是一个”(IS-A),表示一个事物是另一个事物的一个实例。

2.包含关系 3.占有关系4.时间关系5.位置关系6.相近关系(接近、相似)7.推论关系8.因果关系9.组成关系10.属性关系

  2.4.3 语义网络表示知识的方法(篮球赛的语义网络)

(1)事实性知识的表示

 

(2)情况和动作的表示

①情况的表示

 

②动作和事件的表示

(篮球赛的语义网络)黄河大学与长江大学两校篮球队在长江大学进行一场比赛,结局的比分是98:110

 

(3)逻辑关系的表示

①具有合取与析取关系的语义网络(参加比赛者有工人、有干部、有高的、有低的。)

a.工人、高的;b.工人、低的;c.干部、高的;d.干部、低的

 

②具有一个全称量词的语义网络

 

 具有两个全称量词的语义网络

 

 非全称变量节点不为全称变量函数的语义网络

 

  2.4.4 用语义网络表示知识的步骤

(1)确定问题中的所有对象以及各对象的属性。

(2)分析并确定语义网络中所论对象间的关系。

(3)根据语义网络中所涉及的关系,对语义网络中的节点及弧进行整理,包括增加节点、弧和归并节点等。

4)分析检查语义网络中是否含有要表示的知识中所涉及的所有对象,若有遗漏,则须补全。并将各对象间的关系作为网络中各节点间的有向弧,连接形成语义网络。

(5)根据第(1)步的分析结果,为各对象标示属性。

  2.4.5 语义网络表示知识举例(计算题)

例2.5 用语义网络表示下列命题:

(1)树和草都是植物;

(2)树和草是有根有叶的;

(3)水草是草,且长在水中;

(4)果树是树,且会结果;

(5)苹果树是果树中的一种,它结苹果。

 

例2.6 用语义网络表示下列知识:

猎狗是一种狗,而狗是一种动物。狗除了动物的有生命、能吃食物、有繁殖能力、能运动外,还有以下特点:身上有毛、有尾巴、四条腿;猎狗的特点是吃肉、个头大、奔跑速度快、能狩猎;而狮子狗也是一种狗,它的特点是吃饲料、身体小、奔跑速度慢、不咬人、供观赏。

 

例2.7 用语义网络表示以下事实:

山西大学是一所具有百年历史的综合性大学,位于太原市笔直宽广的坞城路。张广义同志今年36岁,男性,中等身材,他工作在山西大学。

 

例2.9 苹果树枝繁叶茂,上结了很多苹果,有大的,也有小的,有红的,也有绿的。

 

  2.4.6 语义网络表示下的推理过程

1.匹配推理

例2.10 匹配推理例。

设在语义网络系统的知识库中,存有下列事实的语义网络:

山西大学是一个学校,位于太原市,建立时间是1902年。

这一事实的语义网络如图所示。

 

假若要求解的问题是:山西大学位于哪个城市?如何利用语义网络进行推理求解呢?

解 :首先将待求解的问题表示成一个局部的语义网络,如图所示。

 

然后到语义网络系统中的知识库中去匹配,就会发现,与待求问题局部网络未知处相匹配的事实是“太原市”,所以这个问题的解就是太原市。

2.继承推理 (1)值继承(属性继承) (2)过程继承(方法继承)

2.5 框架表示法 √(小题)

(1)框架的定义及组成

框架是一种描述所论对象属性的数据结构。一个框架由若干个“槽”组成,每个“槽”又可划分为若干个“侧面”。一个槽用于描述所论及对象的某一方面的属性,一个侧面用于描述相应属性的一个方面。

例:

框架名:<计算机主机>

主机品牌(槽):联想1+1

生产厂商(槽):北京联想集团公司

CPU(槽):品牌:Intel

型号:奔腾Ⅲ/933 侧面

主板(槽):品牌:QDI

型号:ATXVA5

内存(槽):品牌:现代

型号:SDRAM

容量:128MB

硬盘(槽):品牌:Seagate

型号:ST320423A

容量:20GB

(2)用框架表示知识的步骤

(1)分析待表达知识中的对象及其属性,对框架中的槽进行合理设置。

(2)对各对象间的各种联系进行考察。使用一些常用的或根据具体需要定义一些表达联系的槽名,来描述上下层框架间的联系。

①ISA槽

ISA槽用于指出对象间抽象概念上的类属关系。

② AKO槽

AKO槽用于具体地指出对象间的类属关系。

③Instance槽

Instance槽用来表示 AKO的逆关系。

④ Part-of槽

Part-of槽用于指出“部分”与“全体”的关系。

(3)对各层对象的“槽”及“侧面”进行合理的组织安排,避免信息描述的重复。

(3)举例

例2.13 教师框架。

框架名:<教师>

姓名:单位(姓、名)

年龄:单位(岁)

性别:范围(男、女)

缺省:男

职称:范围(教授,副教授,讲师,助教)

缺省:讲师

部门:单位(系,教研室)

住址:<住址框架>

工资:<工资框架>

参加工作时间:单位(年,月)

该框架中共有8个槽,分别描述了“教师”的8个方面的情况。如果把具体某个教师的有关情况填入槽或侧面后,就得到一个实例框架。

(4)框架表示下的推理方法

(1)把待求解问题用一个框架表示出来,其中有的槽是空的,表示待求解的问题,称做未知处。

(2)通过与知识库中已有的框架进行匹配。

(3)使用一种评价方法对预选框架进行评价,以便决定是否接受它。

(4)若可接受,则与问题框架的未知处相匹配的事实就是问题的解。

(5)框架表示法特点

结构性、继承性、自然性

习题二  2.1   2.2

2.1 什么是知识?它有哪些特性?有哪几种分类方法?

答:知识是人们对自然现象的认识和从中总结出来的规律和经验。

它的特性有相对正确性、不确定性、可表示性和可利用性。

分类方法:(1)按知识的作用范围分为:常识性知识和领域性知识;(2)按知识的作用及表示分为:事实性知识、规则性知识、控制性知识和元知识;(3)按知识的确定性分为:确定知识和不确定知识;(4)按人类思维及认识方法分为:逻辑性知识和形象性知识。

2.2 何谓知识表示?陈述性知识表示与过程性知识表示的区别是什么?

答:知识表示是研究用机器表示知识的可行性、有效性的一般方法,是一种数据结构与控制结构的统一体,考虑知识的存储与使用。

区别:陈述性知识表示法主要用来描述事实性知识,将知识表示与应用分开处理,是一种表态的描述方法;过程性知识表示法主要用来描述规则性知识和控制结构知识,将知识的表示与应用相结合,是一种动态的描述方法。

2.3 在选择知识的表示方法时,应该考虑哪些主要因素?

解:可行性、有效性、易理解性、模块性和灵活性。

2.4 一阶谓词逻辑表示法适合于表示哪种类型的知识?它有哪些特点?

解:可以表示事物的状态、属性、概念等事实性的知识,也可以表示事物间具有确定关系的规则性知识。

特点:(1)自然性,表示问题易于理解和接受;(2)适用于精确性知识的表示,不适用不确定性知识的表示;(3)易实现性;(4)会产生组合爆炸,效率低。

2.5 写出用一阶谓词逻辑表示法表示知识的步骤。

步骤:(1)定义谓词及个体,确定每个谓词及个体的确切含义;(2)根据所要表达的事物或概念,为每个谓词中的变元赋予特定的值;(3)根据所要表达的知识的语义用适当的联接符号将各个谓词联接起来,形成谓词公式。

2.6 设有下列语句,请用相应的谓词公式把它们表示出来:

(1)有的人喜欢梅花,有的人喜欢菊花,有的人既喜欢梅花又喜欢菊花;

解:定义谓词如下:

    Like(x,y):x喜欢y。  Club(x):x是梅花。

    Human(x):x是人。   Mum(x):x是菊花。

“有的人喜欢梅花”可表达为:($x)(Human(x)ÙLike(x,Club(x)))

“有的人喜欢菊花”可表达为:($x)(Human(x)ÙLike(x,Mum(x)))

“有的人既喜欢梅花又喜欢菊花”可表达为:($x)(Human(x)ÙLike(x,Club(x))Ù Like(x,Mum(x)))

(2)李明每天下午都去玩足球;

解:定义谓词如下:

    PlayFootball(x):x玩足球。  Day(x):x是某一天。

则语句可表达为:("x)(D(x)®PlayFootball(Ta))

(3)太原市的夏天既干燥又炎热;

解:定义谓词如下:

    Summer(x):x的夏天。  Dry(x):x是干燥的。  Hot(x):x是炎热的。

则语句可表达为:Dry(Summer(Taiyuan))ÙHot(Summer(Taiyuan))

(4)所有人都有饭吃;

解:定义谓词如下:

    Human(x):x是人。  Eat(x):x有饭吃。

则语句可表达为:("x)(Human(x)®Eat(x))

(5)喜欢玩篮球的人必喜欢玩排球;

解:定义谓词如下:

    Like(x,y):x喜欢y。  Human(x):x是人。

则语句可表达为:("x)((Human(x)ÙLike(x,basketball))®Like(x,volleyball))

(6)要想出国留学,必须通过外语考试。

解:定义谓词如下:

Abroad(x):x出国留学。  Pass(x):x通过外语考试。

则语句可表达为:Abroad(x)®Pass(x)

2.7房内有一只猴子、一个箱子,天花板上挂了一串香蕉,其位置关系如图2.33所示,猴子为了拿到香蕉,它必须把箱子推到香蕉下面,然后再爬到箱子上。请定义必要的谓词,写出问题的初始状态(即图2.33所示的状态)、目标状态(猴子拿到了香蕉,站在箱子上,箱子位于位置 b )。

 

本问题涉及的常量定义为: 猴子:Monkey 箱子:Box 香蕉:Banana 位置:a,b,c

定义谓词如下:

SITE(x,y):表示x在y处。

HANG(x,y):表示x悬挂在y处。

ON(x,y):表示x站在y上。

HOLDS(y,w);表示y手里拿着w。

根据问题的描述将问题的初始状态和目标状态分别用谓词公式表示如下:

问题的初始状态表示:

SITE(Monkey,a)∧HANG(Banana,b)∧SITE(Box,c)∧~ON(Monkey,Box)∧~HOLDS (Monkey,Banana)

问题的目标状态表示:

SITE(Monkey,b)∧~HANG(Banana,b)∧SITE(Box,b)∧ON(Monkey,Box)∧HOLDS (Monkey,Banana)

2.9 产生式的基本形式是什么?它与谓词逻辑中的蕴涵式有什么共同处及不同处?

解:基本形式:P®Q 或者 IF  P  THEN Q 其中,P是产生式的前提,用于指出该产生式是否可用的条件;Q是一组结论或操作,用于指出前提P所指示的条件被满足时应该得出的结论或应该执行的操作。

产生式与谓词逻辑中蕴含式的区别:(1)蕴含式只能表示精确性知识,而产生式可以表示精确性知识,也可以表示不精确性知识。(2)产生式前提条件的匹配可以是精确匹配,也可以是不精确匹配,而蕴含式前提条件的匹配问题要求精确匹配。

2.10 何谓产生式系统?它由哪几部分组成?

解:一组产生式一起相互配合,协同作用,一个产生式生成的结论可以供另一个产生式作为已知事实使用,以解决问题,这样的系统称为产生式系统

组成:规则库、综合数据库和推理机。

2.11 产生式系统中,推理机的推理方式有哪几种?在产生式推理过程中,如果发生策略冲突,如何解决?

解:推理方式有正向,反向和双向推理三种。在产生式推理过程中,如果发生策略冲突,常见的解决策略有专一性排序、规则排序、规模排序和就近排序。

2.14 何谓语义网络?语义网络表示法的特点是什么?

定义:通过概念及其语义关系来表示知识的一种带有标注的有向图。

特点:结构性、自然性、联想性和非严格性。

2.15 语义网络表示法与产生式表示法、谓词逻辑表示法之间的关系如何?

解:产生式表示法是以一条产生式规则作为知识的单位,各条产生式规则之间没有直接的联系。语义网络将基本网元视作一种知识的单位,各个网元之间相互联系。从谓词逻辑表示法来看,一个基本网元相当于一组一阶二元谓词。

2.16 用语义网络表示下列知识:

(1)所有的鸽子都是鸟;

(2)所有的鸽子都有翅膀;

(3)信鸽是一种鸽子,它有翅膀,能识途。

解:本题涉及对象有信鸽、鸽子和鸟。鸽子和信鸽的属性是有翅膀。鸽子和鸟是ISA关系,信鸽和鸽子是AKO关系。根据分析得到本题的语义网络如下:

         

2.17 对下列命题分别写出它的语义网络:

(1)每个学生都有多本书;

解:根据题意可得本题的语义网络如下:

(2)孙老师从2月至7月给计算机应用专业讲“网络技术”课程;

解:根据题意可得本题的语义网络如下:  

(3)雪地上留下一串串脚印,有的大,有的小,有的深,有的浅;

解:根据题意可得本题的语义网络如下:

(4)王丽萍是天发电脑公司的经理,她35岁,住在南内环街68号。

解:根据题意可得本题的语义网络如下:

2.18 请把下列命题用一个语义网络表示出来:

(1)猪和羊都是动物;

(2)猪和羊都是偶蹄动物和哺乳动物;

(3)野猪是猪,但生长在森林中;

(4)山羊是羊,且头上长着角;

(5)绵羊是一种羊,它能生产羊毛。

解:本题涉及对象有猪、羊、动物、野猪、山羊和绵羊。猪和羊的属性是偶蹄和哺乳。野猪的属性是生长在森林中。山羊的属性是头上长着角。绵羊的属性是产羊毛。根据对象之间的关系得到本题的语义网络如下:

2.19 何谓框架?框架的一般表示形式是什么?

定义:一种描述所论对象属性的数据结构。

  一个框架可以由框架名、槽、侧面和值四部分组成。一般可表示为:

  框架名

  <槽名>

    <侧面>

      <值>

    <侧面>

         <值>

  <槽名>

    <侧面>

      <值>

    <侧面>

      <值>

2.20 框架表示法有何特点?叙述用框架表示法表示知识的步骤。

解:特点:结构性、继承性和自然性。

  框架表示知识的步骤:(1)分析等表达知识中的对象及其属性,对框架中的槽进行合理设置。(2)对各对象间的各种联系进行考察。使用一些常用的或根据具体需要定义一些表达联系的槽名,来描述上下层框架间的联系。(3)对各层对象的“槽”及“侧面”进行合理的组织安排,避免信息描述的重复。

2.21 试写出“学生框架”的描述。

解:框架名:<学生>

            姓名:温安平

            班级:24020102

            学号:2402010214

            性别:男

            年龄:22

            职务:无

            籍贯:福建龙岩

            民族:汉

            政治面貌:团员

第三章

3.1 推理概述

3.1.2 推理的方法及其分类(了解

                 演绎推理

逻辑基础分类     归纳推理

     默认推理

                         确定性分类

所用知识的确定性分类

                         不确定性分类

                         单调推理

推理过程的单调性分类

                         非单调推理

3.1.3 推理的控制策略简答题

           按照推理方向对各种推理方式进行讨论

正向推理:正向推理是一种从已知事实出发、正向使用推理规则的推理方式,它是一种数据(或证据)驱动的推理方式,又称前项链推理或自底向上推理。

优点是比较直观,允许用户主动提供有用的事实信息,适合于诊断、设计、预测、监控等领域的问题求解。缺点是推理无明确目标,求解问题时可能会执行许多与求解无关的操作,导致推理效率较低。

反向推理:反向推理是一种以某个假设目标为出发点,反向运用推理规则的推理方式,它是一种目标驱动的推理方式,又称反向链推理或自顶向下推理。

优点是推理过程的目标明确,不必寻找和使用那些与假设目标无关的信息和知识,同时也有利于向用户提供解释,在诊断性专家系统中较为有效。缺点是当用户对解的情况认识不清时,由智能系统自主选择假设目标的盲目性比较大,若选择不好,可能需要多次提出假设,导致智能系统的推理效率降低。

混合推理:为了更好地发挥这两种推理方式的长处,避免各自的短处,互相取长补短,可以将它们结合起来使用。这种把正向推理和反向推理结合起来所进行的推理称为混合推理。

双向推理:双向混合推理是指正向推理和反向推理同时进行,使推理过程在中间的某一步骤相汇合而结束的一种推理方法。

  3.1.4 推理的冲突消解策略

   冲突消解:按照某种策略从多条匹配的知识中选择一条最佳知识用于推理,这种解决冲突的过程称。

   常用排序方法:就近原则排序、知识特殊性排序、上下文限制排序、知识的新鲜性排序、知识的差异性排序、领域问题的特点排序、规则的次序排序、前提条件的规模排序。

3.2 命题逻辑(

3.2.1命题

1.命题:能够分辨真假的语句。

  2.原子命题:一个语句如果不能再进一步分解成更简单的语句,并且又是一个命题。

3.2.2 命题公式(与 或 非)

3.3 谓词逻辑(重点哦

  3.3.1 谓词与个体(了解

1.谓词的一般形式是P(x1,x2,…,xn)其中P是谓词,而x1,x2,…,xn是个体。

2.谓词中包含的个体数目称为谓词的元数,例如 P(x)是一元谓词,

P(x,y)是二元谓词,而P(x1,x2,…,xn)则是n元谓词。

  3.3.2 谓词公式(量词、辖域、约束变元

1.连接词:与或非

2.量词:为刻画谓词与个体间的关系,在谓词逻辑中引入了两个量词,一个是全称量词( x),它表示“对个体域中的所有(或任一个)个体 x”;另一个是存在量词(x),它表示“在个体域中存在个体 x”。

 

3.谓词演算公式:

(1)谓词演算中,由单个谓词构成的不含任何连接词的公式,叫做原子谓词公式。形如 F(x1,x2,…,xn)的谓词公式,称做原子谓词公式,或简称原子。

(2)谓词演算的合式公式:

<1>原子谓词公式是合式公式;

<2>若A是合式公式,则 ~ A也是合式公式;

<3>若A和B都是合式公式,则 A∧ B、A ∨ B、A → B、A  B也都是合式公式;

<4>若 A是合式公式, x 是任一个体变元,则( x)A和(x)A 也都是合式公式;

<5>只有按(1)~(4)所得的公式才是合式公式。

4.量词辖域约束变元

在一个公式中,如果有量词出现,位于量词后面的单个谓词或者用括弧括起来的合式公式称为量词的辖域

在辖域内与量词中同名的变元称为约束变元,不受约束的变元称为自由变元

 

3.3.4 谓词公式的等价性与永真蕴涵

 1.等价性:设 P与 Q是两个谓词公式,D是它们共同的个体域。若对 D 上的任何一个解释,P与 Q 的取值都相同,则公式 P和 Q在域 D上是等价的。

 

 

2.永真蕴涵:对于谓词公式P和Q,如果P→Q永真,则称P永真蕴涵Q,且称 Q为P的逻辑结论,称P为Q的前提,记作P从Q。

 

 

   3.3.5 置换与合一(计算题)

1.置换

(1)定义:置换是形如{t1/x1,t2/x2,…,tn/xn}的一个有限集。其中,xi是变量,ti是不同于xi的项(常量,变量,函数),且xi≠xj(i≠ j),i,j =1,2,…,n。

例如,{a/x,b/y,f(x)/z}、{f(z)/x,y/z}都是置换。

    (2)置换乘法:

 

 

 

    (3)置换结合律:一般地说,下述置换结合律成立(θ·λ)·μ=θ· (λ·μ)

但除了空置换外,置换的交换律并不成立,即只有ε·θ=θ·ε=θ。

2.合一

(1)设有公式集{E1,E2,…,En}和置换θ,使E1θ=E2θ=…=Enθ,便称E1,E2,…,En是可合一的,且θ称为合一置换

(2)若E1,E2,…,En有合一置换σ,且对E1,E2,…,En的任一置换θ都存在一个置换λ,使得θ=σ·λ,则称σ是E1,E2,…,En的最一般合一置换,记为mgu。

例子:

 

 

(3)最一般的合一置换算法:在给出最一般合一置换的求取算法之前,先引入不一致集的概念。所谓不一致集是指,在对两个谓词公式中的项从左到右进行比较时,那些不相同的项所构成的集合。例子:

 

3.4 自然演绎推理(计算题

1.概念:自然演绎推理是指从一组已知为真的事实出发,直接运用命题逻辑或谓词逻辑中的推理规则推出结论的过程。

2.解决问题:(例题好好看

 

 

 

3.5 习题:

1. 什么是命题?请写出3个真值为T及真值为F的命题。

定义:能够分辨真假的语句。

3个真值为T的命题:太阳从东边升起;地球绕着太阳转;人是高级动物。

3个真值为F的命题:太阳从西边升起;瞎子看得见;太阳绕着地球转。

2. 什么是谓词?什么是谓词个体及个体域?函数与谓词的区别是什么?

解:谓词是用于刻画个体的性质、状态或个体间关系语句片断。谓词个体是可以独立存在的物体。个体域是谓词个体的集合。

区别:谓词具有逻辑值“真”或“假”,而函数是自变量到因变量之间的一个映射。

3. 谓词逻辑和命题逻辑的关系如何?有何异同?

解:谓词逻辑是命题逻辑的扩充与发展,它将一个原子命题分解成谓词与个体两部分。命题逻辑是谓词逻辑的基础,是谓词逻辑的一种特殊形式。

不同点:命题逻辑不能描述不同事物的共同特征,而谓词逻辑可以。命题逻辑中可以直接通过真值指派给出解释,而谓词逻辑不行。

相同点:归结原理都是完备的,都可以用来表示事实性知识。

4. 什么是谓词的项?什么是谓词的阶?请写出谓词的一般形式。

解:是个体常数、变量和函数的统称。若谓词个体是常量、变元或函数,则为一阶谓词,若谓词个体是一阶谓词,则为二阶谓词,依此类推是为谓词的阶

谓词的一般形式:P(x1,x2,…,xn),其中P是谓词,x1,x2,…,xn是个体。

5. 什么是谓词公式?什么是谓词公式的解释?

6. 解:谓词公式是按照下述五个规则由原子公式、连接词、量词及圆括号所组成的字符串。

(1)原子谓词公式是合式公式。 (2)若A是合式公式,则~A也是合式公式。 (3)若A和B都是合式公式,则AÙB、AÚB、A®B、A«B也都是合式公式。 (4)若A是合式公式,x是任一个体变元,则("x)A和($x)A也都是合式公式。 (5)只有按(1) ¾ (4)所得的公式才是合式公式。

谓词公式的解释:设D为谓词公式P的个体域,若对P中的个体常量、函数和谓词按照如下规定赋值:(1)为每个个体常量指派D中的一个元素;(2)为每个n元函数指派一个从Dn到D的映射,其中Dn={(x1,x2,…,xn)| x1,x2,…,xn  ÎD} (3)为每个n元谓词指派一个从Dn到{F,T}的映射;则这些指派称为公式P在D上的解释。

7.对下列谓词公式分别指出哪些是约束变元?哪些是自由变元?并指出各量词的辖域。

(1)("x)(P(x,y)Ú($y)(Q(x,y)ÙR(x,y)))

解:("x)的辖域是(P(x,y)Ú($y)(Q(x,y)ÙR(x,y))),x是受("x)约束的变元;($y)的辖域的(Q(x,y)ÙR(x,y)),y是受($y)约束的变元;没有自由变元。

(2)($z)("y)(P(z,y) ÚQ(z,x)) ÚR(u,v)

解:($z)的辖域是("y) (P(z,y) ÚQ(z,x)),z是受($z)约束的变元;("y)的辖域是(P(z,y) ÚQ(z,x)),y是受("y)约束的变元;u、v是自由变元。

(3)("x)(~P(x,f(x)) Ú($z)(Q(x,z) Ù~R(x,z)))

解:("x)的辖域是(~P(x,f(x)) Ú($z)(Q(x,z) Ù~R(x,z))),x是受("x)约束的变元;($z)的辖域是(Q(x,z) Ù~R(x,z)),z是受($z)约束的变元;没有自由变元。

(4)("z)(($y)(($t)(P(z,t) ÚQ(y,t))ÙR(z,y)))

解:("z)的辖域是(($y)(($t)(P(z,t) ÚQ(y,t))ÙR(z,y))),z是受("z)约束的变元;($y)的辖域是(($t)(P(z,t) ÚQ(y,t))ÙR(z,y)),y是受($y)约束的变元;($t)的辖域是(P(z,t) ÚQ(y,t)),t是受($t)约束的变元;没有自由变元。

(5)("z)($y)(P(z,y) Ú($z)(("y)(P(z,y) ÙQ(z,y) Ú($z)(Q(z,y)))))

解:("z)的辖域是($y) (P(z,y) Ú($z)(("y)(P(z,y) ÙQ(z,y) Ú($z)(Q(z,y))))),z是受("z)约束的变元;($y)的辖域是(P(z,y) Ú($z)(("y)(P(z,y) ÙQ(z,y) Ú($z)(Q(z,y))))),y是受($y)约束的变元;($z)的辖域是(("y)(P(z,y) ÙQ(z,y) Ú($z)(Q(z,y)))),z是受($z)约束的变元;("y)的辖域是(P(z,y) ÙQ(z,y) Ú($z)(Q(z,y))),y是受("y)约束的变元;($z)的辖域是(Q(z,y)),z是受($z)约束的变元;没有自由变元。

7. 什么是谓词公式的永真性、永假性、可满足性、等价性及永真蕴含?

解:永真性:如果谓词公式P,对个体域D上的任何一个解释都取得真值T,则称P在D上是永真的;如果P在每个非空个体域上均永真,则称P永真。

永假性:如果谓词公式P,对个体域D上的任何一个解释都取得真值F,则称P在D上是永假的;如果P在每个非空个体域上均永假,则称P永假。

可满足性:对于谓词公式P,如果至少存在一个解释使得公式P在此解释下的真值为T,则称公式P是可满足的。

等价性:若对共同的个体域D上的任何一个解释,谓词公式P与Q的取值都相同,则公式P和Q在域D上是等价的;如果D是任意个体域,则称P和Q是等价的。

永真蕴含:对于谓词公式P和Q,如果P®Q永真,则称P永真蕴含Q。

8. 什么是置换?什么是合一?什么是最一般的合一?

解:置换是形如{t1/x1,t2/x2,…,tn/xn}的一个有限集。其中xi是变量,ti是不同于xi的项(常量,变量,函数),且xi¹xj(i¹j),i,j=1,2,…,n。

设有公式集{E1,E2,…,En}和置换q,使E1q=E2q=…=Enq,便称E1,E2,…,En是可合一的,用称q为合一置换。

若E1,E2,…,En有合一置换s,且对E1,E2,…,En的任一置换q都存在一个置换l,使得q=s×l,则称s是E1,E2,…,En的最一般合一置换。

9. 写出最一般合一置换的步骤。

解:设E1,E2两个谓词公式,其最一般合一置换算法:

(1) 令W={E1,E2}。

(2) 令k=0,Wk=W,sk=e;e是空置换,它表示不作置换。

(3) 如果Wk只有一个表达式,则算法停止,sk就是所要求的mgu。

(4) 找出Wk的不一致集Dk。

(5) 若Dk中存在元素xk和tk,其中xk是变元,tk是项,且xk不在tk 中出现,则置:

       sk+1=sk×{ tk/xk}    Wk+1=Wk×{ tk/xk}    k=k+1  然后转(3)。

(6) 算法终止,W的mgu不存在。

10. 判断以下公式对是否可合一;若可合一,则求出最一般的合一。

(1)P(a,b),  P(x,y)

解:依据算法:

(1) 令W={P(a,b),P(x,y)}。

(2) 令s0=e,W0=W。

(3) W0未合一。

(4) 从左到右找不一致集,得D0={a,x}。

(5) 取x0=x,t0=a,则

s1=s0×{ t0/ x0}=s0×{a/ x}={a/ x}

W1= W0s1={P(a,b),P(a,y)}

       (3’) W1未合一。

       (4’) 从左到右找不一致集,得D1={b,y}。

(5’) 取x1=y,t1=b,则

s2=s1×{ t1/ x1}=s1×{b/ y}={a/ x}×{b/ y}={a/x,b/y}

W2= W1s2={P(a,b),P(a,b)}

       (3’’) W2已合一,因为其中包含相同的表达式,这时s2={a/x,b/y}即为所求的mgu。

(2)P(f(z)),b),  P(y,x)

解:依据算法:

(1) 令W={P(f(z),b),P(y,x)}。

(2) 令s0=e,W0=W。

(3) W0未合一。

(4) 从左到右找不一致集,得D0={f(z),y}。

(5) 取x0=y,t0=f(z),则

s1=s0×{ t0/ x0}=s0×{f(z)/ y}={f(z)/y}

W1= W0s1={P(f(z),b),P(f(z),x)}

       (3’) W1未合一。

       (4’) 从左到右找不一致集,得D1={b,x}。

(5’) 取x1=x,t1=b,则

s2=s1×{ t1/ x1}=s1×{b/ x}={ f(z)/ y}×{ b/ x}={f(z)/y,b/x}

W2= W1s2={P(f(z),b),P(f(z),b)}

       (3’’) W2已合一,因为其中包含相同的表达式,这时s2={f(z)/y,b/x}即为所求的mgu。

(3)P(f(x),y),  P(y,f(a))

解:依据算法:

(1) 令W={P(f(x),y),P(y,f(a))}。

(2) 令s0=e,W0=W。

(3) W0未合一。

(4) 从左到右找不一致集,得D0={f(x),y}。

(5) 取x0=y,t0=f(x),则

s1=s0×{ t0/ x0}=s0×{f(x)/ y}={f(x)/y}

W1= W0s1={P(f(x),f(x)),P(f(x),f(a))}

       (3’) W1未合一。

       (4’) 从左到右找不一致集,得D1={y,f(a)}。

(5’) 取x1=y,t1=f(a),则

s2=s1×{ t1/ x1}=s1×{f(a)/ y}={ f(x)/ y}×{ f(a)/ y}={f(x)/y}

W2= W1s2={P(f(x),f(x)),P(f(x),f(a))}

    (6) 算法终止,W的mgu不存在。

(4)P(f(y),y,x),  P(x,f(a),f(b))

解:依据算法:

(1) 令W={P(f(y),y,x),P(x,f(a),f(b))}。

(2) 令s0=e,W0=W。

(3) W0未合一。

(4) 从左到右找不一致集,得D0={f(y),x}。

(5) 取x0=x,t0=f(y),则

s1=s0×{ t0/ x0}=s0×{f(y)/ x}={f(y)/x}

W1= W0s1={P(f(y),y,f(y)),P(f(y),f(a),f(b))}

       (3’) W1未合一。

       (4’) 从左到右找不一致集,得D1={y,f(a)}。

(5’) 取x1=y,t1=f(a),则

s2=s1×{ t1/ x1}=s1×{f(a)/ y}={ f(y)/ x}×{ f(a)/ y}={f(f(a))/x,f(a)/y}

W2= W1s2={P(f(f(a)),f(a),f(f(a))),P(f(f(a)),f(a),f(b))}

    (6) 算法终止,W的mgu不存在。

(5)P(x,y),  P(y,x)

解:依据算法:(1) 令W={P(x,y),P(y,x)}。

(2) 令s0=e,W0=W。

(3) W0未合一。

(4) 从左到右找不一致集,得D0={x,y}。

(5) 取x0=x,t0=y,则

s1=s0×{ t0/ x0}=s0×{y/ x}={y/ x}

W1= W0s1={P(y,y),P(y,y)}

    (3’) W2已合一,因为其中包含相同的表达式,这时s1={y/x}即为所求的mgu。

第四章

4.2 可信度方法(计算题 例4.1 例4.2

  4.2.1 可信度的概念

可信度就是人们在实际生活中根据自己的经验或观察对某一事件或现象为真的相信程度。

  4.2.2 知识不确定性的表示

知识的不确定性则是以可信度CF(H,E)表示的。其一般形式为

IF E THEN H(CF(H,E))

其中:

(1)E是知识的前提条件或称为证据。它既可以是一个简单条件,也可以是用 AND及OR把多个简单条件连接起来所构成的复合条件。例如

E=E1 AND E2 AND(E3 OR E4)

(2)H是结论,它可以是一个单一的结论,也可以是多个结论。

(3)CF(H,E)是该条知识的可信度,称为可信度因子(CertaintyFactor)或规则强度。在专家系统 MYCIN中,CF(H,E)被定义为:CF(H,E)=MB(H,E)-MD(H,E)

其中,MB称为信任增长度,它表示因与前提条件E匹配的证据的出现,使结论 H为真的信任增长度。MD称为不信任增长度,它表示因与前提条件E匹配的证据的出现,对结论H为真的不信任增长度。

 

这里,P(H)表示 H的先验概率;P(H/E)表示在前提条件E所对应的证据出现的情况下,结论H的条件概率。

 

要想运用公式计算CF(H,E),就要知道P(H)和P(H/E)。然而,在实际应用中要想获取P(H)和P(H/E)的值是很难的。因此CF(H,E)的值一般由领域专家直接给出。

  4.2.3 证据不确定性的表示

1.单个证据:

可信度值的确定分两种情况:第一种情况是,证据为初始证据,其可信度的值一般由提供证据的用户直接指定,指定的方法也是用可信度因子对证据不确定性进行表示,例如CF(E)=0.8表示证据 E的可信度为 0.8。第二种情况就是用先前推出的结论作为当前推理的证据,对于这种情况的证据,其可信度的值在推出该结论时通 过不确定 性传递算 法计算得 到(传 递算法将在下面讨论)。

2.组合证据:

证据是多个单一证据的合取时,即E=E1∧E2∧E3∧…∧En,若E1,E 2,E3,…,En各证据的可信度分别为CF(E1),CF(E2),…,CF(En),则 :

CF(E)=min{CF(E1),CF(E2),…,CF(En)}

  证据是多个单一证据的析取时,即E=E1∨E2∨E3∨…∨En若E1,E2,E3,…,En各证据的可信度分别为CF(E1),CF(E2),…,CF(En),则

CF(E)=max{CF(E1),CF(E2),…,CF(En)}

  4.2.4 不确定性的推理计算(重点 计算

1.单条知识支持结论:

支持结论的知识只有一条时,结论 H的可信度计算公式如下:

CF(H)=CF(H,E)×max{0,CF(E)}

若CF(E)<0,即相应证据以某种程度为假,则CF(H)=0;

若CF(E)= 1,即相应证据以某种程度为真,则CF(H)=CF(H,E);

2.多条知识支持同一结论

若由多条不同知识推出了相同的结论,但可信度不同,则可用合成算法求出结论的综合可信度。由于对多条知识的综合可通过两两的合成实现,所以下面只考虑两条知识的情况。

设有如下知识:

IF E1 THEN H(CF(H,E1))

IF E2 THEN H(CF(H,E2))

则结论 H的综合可信度可分如下两步算出:

(1)利用公式分别计算每一条知识的结论可信度 CF(H):

 

(2)用公式求出 E1与E2对H的综合影响所形成的可信度CF12 (H):

 

      3. 已知结论原始可信度的情况下,结论可信度的更新计算方法

在某些情况下,如果已知证据 E对结论 H有影响,且知识IF E THEN H 的可信度为CF(H,E),同时结论 H原来的可信度为CF(H),那么如何求在证据 E下结论 H 可信度的更新值CF(H/E)呢?即已知规则IF E THEN H(CF(H,E))及 CF(H),求 CF(H/E)。

这时分三种情况进行讨论:

 

 

4.2.5 可信度方法应用举例(计算题例题  例4.1 例4.2)

1. 多条知识下,合成法求结论可信度举例:

 

例4.2 设有一组知识:

 

 

 

2.多条知识下,更新法求结论可信度举例

 

 

 

4.3 主观Bayes方法

  4.3.1 基本Bayes公式

1. Bayes公式

 

2.产生式规则

IF E THEN  Hi中的前提条件E代替Bayes公式中的 A,用Hi代替公式中的Bi,就可得到:

 

 

3.Bayes例题:(计算  例4.6)

 

4.3.2 主观Bayes方法及其推理网络

推理网络中的每一个节点H都有一个先验概率P(H),每条规则都有一个数值对(LS,LN)表示规则强度。每条规则的(LS,LN)值以及每个节点的先验概率P(H)均由领域专家给出。

   4.3.3 知识不确定性的表示

它的不确定性是以一个数值对(LS,LN)来进行描述的。若以产生式规则的形式表示,则具体为

IF E THEN (LS,LN) H (P(H))

(LS,LN)是为度量产生式规则的不确定性而引入的一组数值,LS表示规则成立的充分性,用于指出证据E对结论H为真的支持程度;而LN则表示规则成立的必要性,用于指出证据E对结论H为真的必要性程度。它们的定义如下:

 

LS和 LN 的取值范围为[ 0,+∝)。它们的具体取值由领域专家根据实际经验给出。

   4.3.4 证据不确定性的表示

1.单个证据不确定性的表示方法

可信度C(E/S)与后验概率P(E/S)的值,有简单的保持大小次序的对应关系,如表所示:

 

 

2.组合证据不确定性的表示方法

(1)当证据 E是由多个单一证据的合取组合而成时,即

E=E1 AND E2 AND … AND E

 

(2)当证据 E是由多个单一证据的析取组合而成时,即

E=E1 OR E2 OR … OR E

 

  4.3.5 不确定性的推理计算(确定性  计算)

确定性证据和不确定性证据两种情况分别讨论结论H后验概率的推理计算方法。

1.确定性证据:证据肯定出现和证据肯定不出现。

 (1)证据肯定出现:

 

 (2)证据肯定不出现

 

(3)关于知识规则强度(LS,LN)的意义的讨论

 

 

 

 

 

(3)确定性证据例题:

 

 

 

2.不确定性证据

 (1)用概率表示证据的不确定性

 

 

(2)用可信度表示证据的不确定性

 

4.3.6 结论不确定性的合成与更新算法

 

 

4.3.7 主观Bayes方法应用举例(计算  例4.9 例4.10)

 

 

 

 

 

 

 

 

4.4 证据理论

  4.4.1 D-S

1.概率分配函数

 

2.信任函数

 

 

 

3.似然函数

 

 

 

  4.4.4 证据理论解题举例(计算)

 

 

4.4.3 信任度函数

 

4.5  习题

 

求CF(H)= ?

 

 

 

答案:

 

 

4.5 由于对H的初始可信度一无所知,所以使用合成算法进行计算,推理网络图:

 

 

 

 

 

 

 

        = 0.45

同理:   

 

 

 

 

 

 

 

0

补充:信任度例题

 

 

 

 

 

第五章

搜索分为盲目搜索(无信息搜索;即问题本身的特性对搜索控制策略没有任何影响;效率低,解决比较简单的问题)和启发式搜索(考虑到问题本身的特性;效率高,求解复杂的问题;但并不是对所有的问题都能方便地抽取问题的相关特性和信息)

5.2 盲目搜索策略

  5.2.2 宽度优先搜索策略(搜索顺序)

宽度优先搜索又称为广度优先搜索,是一种盲目搜索策略。其基本思想是,从初始节点开始,逐层对节点进行依次扩展,并考察它是否为目标节点,在对下层节点进行扩展(或搜索)之前,必须完成对当前层的所有节点的扩展(或搜索)。在搜索过程中,未扩展节点表OPEN 中的节点排序准则是:先进入的节点排在前面,后进入的节点排在后面。其搜索过程如图5.2所示。

 

搜索过程: (1)把初始节点 S 放入 OPEN 表中。

(2)如果 OPEN表是空表,则没有解,失败退出;否则继续。

(3)把 OPEN表中的第一个节点(记为节点 n )移出,并放入CLOSED表中。

(4) 判断节点 n 是否为目标节点,若是,则求解结束,并用回溯法找出解的路径,退出;否则继续执行(5)。

(5)若节点 n 不可扩展,转第(2)步;否则继续执行(6)步。

(6)对节点 n 进行 扩展,将它的所有后继节 点放入OPEN 表的末端,并为这些后继节点设置指向父节点 n 的指针,然后转第(2)步。

 

  5.2.3 深度优先搜索(搜索顺序)

深度优先搜索也是一种盲目搜索策略,其基本思想是:首先扩展最新产生的(即最深的)节点,即从初始节点开始,在其后继节点中选择一个节点,对其进行考察,若它不是目标节点,则对该节点进行扩展,并再从它的后继节点中选择一个节点进行考察。依次类推,一直搜索下去,当到达某个既非目标节点又无法继续扩展的节点时,才 选择其兄弟节点进行考察。搜索过程如图5.6所示。

 

搜索过程:(1)把初始节点 S 放入 OPEN 表;

(2)如果 OPEN表为空,则问题无解,退出;

(3)从 OPEN表中将其第一个节点(节点 n )移出,放入已扩展节点表 CLOSED中;

(4)考察节点 n 是否为目标节点,若是,则找到问题的解,用回溯法求解的路径,退出;

(5)若节点 n 不可扩展,则转第(2)步;

(6)扩展节点 n ,将其后继节点放到OPEN表的前端,并为其设置指向节点 n 的指针,然后转第(2)步。

深度优先搜索与宽度优先搜索的区别就在于:在对节点 n 进行扩展时,其后继节点在OPEN 表中的存放位置。宽度优先搜索是将后继节点放入 OPEN 表的末端,而深度优先搜索则是将后继节点放入 OPEN 表的前端。

 

  5.2.4 有界深度优先搜索(搜索顺序)

为了避免搜索过程沿着无穷的路径搜索下去,往往对一个节点扩展的最大深度进行限制。任何节点如果达到了深度界限,就把它作为没有后继节点进行处理,即对另一个分支进行搜索。为此,先定义搜索树中节点深度的概念如下:(1)搜索树中初始节点(即根节点)的深度为0。

(2)任何其他节点的深度等于其父辈节点的深度加上1

搜索过程:(1)把初始节点 S 0 放入 OPEN 表中。

(2)如果 OPEN表为空,则问题无解,退出。

(3)把 OPEN表中的第一个节点从 OPEN 表移到CLOSED表。

(4)考察节点 n 是否为目标节点,若是,则求得问题的解,退出;否则继续执行第(5)步。

(5)如果节点 n 的深度等于最大深度,则转第(2)步。

(6)如果节点 n 不可扩展,即没有后继节点,则转第(2)步;否则继续第(7)步。

(7)扩展节点n,将其后继节点放入OPEN表的前端,并为其设置指向节点n的指针,转第(2)步。

 

5.3 启发式搜索策略

利用问题自身特性信息,以提高搜索效率的搜索策略,称为启发式搜索有信息搜索。

估价函数 f(x) 定义为从初始节点经过节点 x 到达目标节点的最小代价路径的代价估计值。它的一般形式为

f(x) = g(x) + h(x)

其中 g(x) 为初始节点 S0 到节点 x 已实际付出的代价;h(x) 是从节点 x 到目标节点 S g 的最优路径的估计代价,搜索的启发信息主要由 h(x) 来体现,故把 h(x) 称做启发函数

  5.3.2 最佳优先搜索(有序搜索或择优搜索)

(1)局部最佳优先搜索

其思想是:当对某一个节点扩展之后,对它的每一个后继节点计算估价函数 f(x) 的值,并在这些后继节点的范围内,选择一个 f(x) 的值最小的节点,作为下一个要考察的节点。由于它每次只在后继节点的范围内选择下一个要考察的节点,范围比较小,所以称为局部最佳优先搜索或局部择优搜索。

搜索过程:算法5.7 局部最佳优先搜索算法

(1)把初始节点 S0 放入 OPEN 表,并计算估价函数 f(S 0 )。

(2)如果 OPEN为空,则问题无解,退出;否则转第(3)步。

(3) 从 OPEN 表中选取第一个节点(记作节点 n ,其估价函数值最小)移入 CLOSED表。

(4)考察节点 n 是否为目标节点,若是,则求得问题的解,退出;否则转第(5)步。

(5)如果节点 n 可扩展,转(6)步;否则转第(2)步。

(6)对节点 n 进行扩展,并对它的所有后继节点计算估价函数 f(x) 的值,并按估价函数 f(x) 从小到大的顺序依次放入 OPEN表的前端。

(7)为每个后继节点设置指向 n 的指针。

(8)转第(2)步。

 

图5.16 局部最佳优先搜索框图

(2)全局最佳优先搜索

它的思想类似于宽度优先搜索,所不同的是,在确定下一个扩展节点时,以与问题特性密切相关的估价函数 f(x) 作为标准,不过这种方法是在 OPEN 表中的全部节点中选择一个估价函数值 f(x) 最小的节点,作为下一个被考察的节点。正因为选择的范围是 OPEN 表中的全部节点,所以它称为全局最佳优先搜索全局择优搜索

搜索过程:算法5.8 全局最佳优先搜索算法

(1)把初始节点 S0 放入 OPEN 表,计算 f(S 0 )。

(2)如果 OPEN为空表,则问题无解,退出。

(3)把 OPEN表中第一个节点作为节点 n 移入CLOSED表。

(4)考察节点 n 是否为目标节点,若是,则求得问题的解,退出;否则转第(5)步。

(5)如果节点 n 可扩展,转第(6)步;否则转第(2)步。

(6)对节点 n 进行扩展,并计算所有后继节点的估价函数 f(x) 的值,并为每个后继节点设置指向 n 的指针。

(7)把这些后继节点都送入 OPEN 表,然后对 OPEN 表中的全部节点按照估价值从小到大的顺序排序。

(8)转第(2)步。

 

(3)A*算法(也是一种启发式搜索方法)

定义:如果在一般状态空间图的搜索算法(即算法5.1)中的第(8)步,依据估价函数

f(x) = g(x) + h(x)

对OPEN 表 中的 节 点进 行 排序,并 且要 求 启发 函 数 h(x) 是 h* (x)的 一个 下 界,即h(x) ≤ h* (x),则这种状态空间图的搜索算法就称为 A *算法。

性质:可采纳性、单调性、信息性

5.6 习题

5.4 什么是盲目搜索?主要有几种盲目搜索策略?

5.5 宽度优先搜索与深度优先搜索有何不同?在何种情况下,宽度优先搜索优于深度优先搜索?在

何种情况下,深度优先搜索优于宽度优先搜索?

5.6 用深度优先搜索和宽度优先搜索分别求如图5.20所示的迷宫出路。

 

 

 

 

 

 

 

 

 

 

 

 

 

宽度优先搜索

深度优先搜索

 

 

 

 

第六章 机器学习

6.1 概述

  6.1.1  什么是机器学习

(1)学习(机器学习的核心)是一个有特定目的的知识获取过程,其内在行为是获取知识、积累经验、发现规律,其外在表现是使系统性能得到改进、系统实现自我完善、自适应环境。

(2)机器学习是研究如何使用计算机来模拟人类学习活动的一门学科。更严格地说,就是研究计算机获取新知识和新技能、识别现有知识、不断改善性能、实现自我完善的方法。

(3)机器学习研究的目标:人类学习过程的认知模型;通用学习算法;构造面向任务的专用学习系统的方法。

6.1.3 机器学习的发展史

(1)神经元模型和决策理论的研究(始于20世纪50年代中期)

主要研究目标是应用决策理论的方法,研制各类自组织的、自适应的通用学习系统。这类系统实际上可以称为神经网自组织系统

基本思想:系统是一个由互连的元件组成的网络,网络结构可能是任意的,这些元件类似于神经元;如果给系统一组刺激、一个反馈源和修改自身组织的自由度,那么系统就可以自适应地趋向最优化。

典型代表:F.Rosenblatt提出的感知器模型,它由阈值性神经元组成,试图模拟动物和人的感知及学习能力。

(2)符号概念获取研究(始于20世纪60年代中期)

研究目标是模拟人类的概念学习过程,并采用逻辑结构或图结构作为机器的内部描述。

代表性工作:Winston的结构学习系统 ARCH 和海叶斯-罗斯(F.Hayes-Roth)等的基于逻辑的归纳学习系统。

(3)知识增强和论域专用学习(始于20世纪70年代中期)

这一阶段对机器学习的研究从学习单个概念扩展到学习多个概念,探索不同的学习策略和各种学习方法。学习系统中包括预先确定的概念、知识结构、论域约束、启发式规则和论域有关的变换。

系统在开始时并不具有所有的属性或概念,但在学习过程中系统将会得到一些新的属性或概念,并将这些新的属性或概念加入知识库中,使知识得到增强,这个过程称为构造性的归纳。这类学习系统一般是为专门的领域开发的,不能直接用于其他领域,故可以称为论域专用学习。这类系统的学习策略不仅有实例学习,而且有类比学习、观察与发现学习。

典型代表例子:Meta-DENDRAL(Buchanan和Feigenbaum,1978)和AM(Lenat,1983)。

(4)连接学习的研究(始于20世纪80年代中期)

这一阶段机器学习进入了连接学习的研究阶段。连接学习是一种以非线性大规模并行处理为主流的神经网络研究。

6.1.4 机器学习的主要策略

学习中使用的推理方法称为学习策略。

主要策略有:机械学习、传授学习、演绎学习、归纳学习(实例学习、观察与发现学习)、类比学习。

6.2 机器学习系统的基本模型 √  (填空题)

 

图6.1 机器学习系统的基本模型

“环境”和“知识库”是以某种知识表示形式表达的信息的集合,分别代表外界信息来源和系统所具有的知识;“学习环节”和“执行环节”代表两个过程。“环境”向系统的“学习环节”提供某些信息,而“学习环节”则利用这些信息对系统的“知识库”进行改进,以增进系统“执行环节”完成任务的效能,“执行环节”根据知识库中的知识来完成某种任务,同时把获得的信息反馈给“学习环节”。

  6.2.1 环境

环境就是指系统外部信息的来源,它可以是系统的工作对象,也可以是包括工作对象和外界条件。例如,在控制系统中,环境就是生产流程或受控的设备;在计算机故障维修系统中,环境就是待修计算机当前的症状以及与损坏相关的操作情况说明。总之,环境就是为学习系统提供获取知识所需的相关对象的素材或信息。

  6.2.2 学习环节

学习环节通过对环境的搜索获得外部信息,并将这些信息与执行环节所反馈回的信息进行比较,从比较的差距中获取相关对象的知识,并将这些知识存入知识库中。

  6.2.3 知识库

知识库用于存放由学习环节所学到的知识。知识库中知识的表示形式以及存储组织结构是影响学习系统设计的第二个因素。知识库中常用的知识表示方法有:谓词逻辑、产生式规则、语义网络、特征向量、过程、LISP函数、数字多项式和框架等。

选择知识表示方法考虑的准则:表达能力的强弱、推理难度的大小、修改的难易、是否便于扩充。

  6.2.4 执行环节

执行环节是整个学习系统的核心。执行环节用于处理系统面临的现实问题,即应用知识库中所学到的知识求解问题,如智能控制、自然语言理解和定理证明等,并对执行的效果进行评价,将评价的结果反馈回学习环节,以便系统进一步的学习。

执行环节的问题复杂性、反馈信息和执行过程的透明度都对学习环节有一定的影响。

 

习题六

6.1 什么是学习?有哪几种主要观点?

 

6.2 什么是机器学习?机器学习研究的目标是什么?研究机器学习的意义何在?

 

6.3 机器学习的研究经历了哪几个阶段?

 

6.4 机器学习有哪些主要学习策略?

答:机器学习的主要策略有:记忆学习(又称机械学习)、传授学习、演绎学习、类比学习和归纳学习。其中归纳学习又分为实例学习、观察与发现学习。

6.5 试述机器学习系统的基本结构,并说明各部分的作用。

 

第七章 自然语言理解

7.1 自然语言(概念)及其理解     

  7.1.1 自然语言及其构成

(1)什么是自然语言

自然语言是指人类本身使用的语言,是人类在与大自然的搏斗中,为充分表达思想、交流信息而自然形成的交流工具,是人类进行通信的自然媒介。更确切地说,自然语言是用于传递信息的表示方法、约定和规则的集合,它由语句组成,每个语句又由单词组成;组成语句和语言时,应遵循一定的语法与语义规则。

(2)自然语言的构成

 

  7.1.2 自然语言理解的概念

在人工智能界或语言信息处理领域,人们普遍认为,自然语言理解是指机器能够执行人类所期望的某些语言功能。这些功能包括:(1)回答有关提问、(2)摘要生成、(3)文本释义、(4)不同语言间的翻译

语言理解的困难是由下列3个因素引起的:① 目标表示的复杂性;② 映射的歧义性;③ 句子成分间交互程度的差异性。

自然语言理解是语言学、逻辑学、生理学、心理学、计算机科学和数学等相关学科发展和结合而形成的一门交叉学科,它可以分为两个方面:口语的理解和书面语的理解。

  7.1.3 自然语言理解研究的进展

(1)萌芽时期

自然语言理解的研究可以追溯到20世纪的40年代末50年代初。

机器翻译成了自然语言理解的主要研究课题。

在机器翻译研究进行期间,国际上出现了数理语言学的研究热潮。1956年,美国《信息论》杂志上发表了语言学家乔姆斯基的论文“语言描述的三个模型”,文中提出了形式语言和形式文法的概念。乔姆斯基所建立的语法体系,已经成为计算机科学中程序语言编译系统和形式语言系统中的重要内容,也是自然语言理解中语法分析所必须依赖的语法体系。

(2)发展时期

人们开始在人-机对话领域开展研究,让计算机以人-机对话的方式理解以自然语言形式提出的问题,并用自然语言进行回答。

这时的自然语言理解系统的发展实际上可分为两个阶段:第一阶段为20世纪60年代,以关键字匹配为主流技术,系统建立在对词类和词序分析的基础之上。第二阶段为20世纪70年代,以句法—语义分析为主流技术,甚至考虑语用和语境的因素。

在这一时期,各种有关自然语言处理的理论逐渐成熟,出现了一大批理论成果,包括短语结构语法、转换生成语法、各种增强型的短语结构语法、词汇功能语法和功能合一语法。在语义自动分析方面,提出了“格语法”和概念依存理论,建立了句法与语义之间的关系。

(3)繁荣时期:大规模真实文本处理的新时期

进入20世纪80年代后,自然语言理解的最大特点就是实用化和工程化。一大批商品化的自然语言人-机接口系统和机器翻译系统出现在市场上。

人们更强调知识在自然语言理解中的重要作用。1990年8月,在芬兰赫尔辛基召开的第13届国际计算机语言学大会(COLING’90)上,首次提出了处理大规模真实文本的战略目标。会前的讲座主题是“处理大规模真实文本的理论、方法和工具”,并组织了“大型语料库在建造自然语言系统中的作用”和“词典知识的获取与表示”等专题讲座,预示着语言信息处理的一个新时期的到来。从此,一门崭新的语料库语言学(CorpusLinguistics)在自然语言理解的研究中得以崛起。

习题七

7.1 什么是自然语言?自然语言是由哪些要素构成的?

7.2 什么是自然语言理解?自然语言理解过程有哪些层次,各层次的功能如何?

答:自然语言理解就是研究如何让计算机理解人类自然语言的一个研究领域。从宏观上看,自然语言理解就是指使计算机能够执行人类所期望的某些语言功能,包括理解并回答人们用自然语言提出的有关问题;生成文本摘要和对文本进行释义:把一种自然语言表示的信息自动地翻译为另一种自然语言等等。从微观上讲,自然语言理解是指从自然语言到机器(计算机系统)内部之间的一种映射。

自然语言理解过程有3个层次:词法分析、句法分析和语义分析。词法分析的主要目的是找出词汇的各个词素,从中获得语言学信息,如unchangeable是由un change able构成的。句法分析就是要对句子或短语的结构进行分析,以确定构成句子的各个词、短语等之间的相互关系以及各自在句子中的作用等,并将这些关系用层次结构加以表达。语义分析就是通过分析找出词义、结构意义及其结合意义,从而确定语言所表达的真正含义或概念。

7.4 自然语言理解的发展分几个阶段?各阶段的研究重点是什么?

7.5 语言学家乔姆斯基的论文“语言描述的三个模型”的意义是什么?

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/酷酷是懒虫/article/detail/736020
推荐阅读
相关标签
  

闽ICP备14008679号