人工智能及其应用   分类:其他 | 上传于: 2019-12-06 18:54:05

1."1
人工智能及其应用
主讲:李敏 教授
智能信息处理与仪器研究室
2007年3月
" 2."2
第3章 问题求解技术
智能信息处理与仪器研究室
学习要求:
1.了解命题逻辑与谓词逻辑的区别与联系,掌握谓词公式的概念及可满足性的定义,弄清置换与合一的概念,掌握求取最一般合一置换的方法。
2.掌握归结原理及归结推理方法。激扬SKOLEM标准式和子句集的求取方法,理解谓词公式和子句集在不可满足意义下的一致性,弄懂HERBRAND定理,掌握H域、原子集、H域上的解释的求法,掌握命题逻辑和谓词逻辑中的归结原理。
3.掌握利用归结原理进行定理证明的方法。
4.掌握应用归结原理进行问题求解的方法。
5.掌握归结过程中的控制策略。
" 3."3
第3章 问题求解技术
智能信息处理与仪器研究室
学习要求:
6.理解不确定推理的基本概念和意义,了解不确定推理方法的种类,充分认识不确定推理中的基本问题,即不确定性的表示问题(包括证据不确定性和知识不确定性的表示)、不确定性的推理计算问题以及不确定性的度量问题。
7.可信度方法又称确定性方法,是目前常用的不确定推理方法之一。要求充分理解可信度的概念,理解CF的含义,掌握利用可信度表示知识(规则)和证据的方法,掌握计算结论可信度的推理计算方法,并熟记各种推理计算公式。
" 4."4
第3章 问题求解技术
智能信息处理与仪器研究室
学习要求:
8.主观BAYES方法是常用的不确定性推理方法之一。要求理解主观BAYES方法与基本BAYES概率公式之间的关系,了解主观BAYES方法的推理网络;掌握主观BAYES方法中知识(规则)不确定性和证据不确定性的表示方法,充分理解(LS 5.LN)的含义;掌握各种情况下的结论不确定性的推理计算方法,熟记各种情况下的推理计算公式。
9.证据理论又称D-S理论,是常用的第三种不确定性推理计算方法。要求充分了解与前两种不确定性推理方法在证据和结论表示方面的不同;理解概率分配函数、信任函数及似然函数的定义以及它们之间的相互关系;掌握概率分配函数正交和的计算方法;理解定义特定概率分配函数的意义,掌握基于该特定概率分配函数的不确定性推理方法,包括知识(规则)和证据的不确定性表示及结论不确定性的推理计算。
" 6."5
命题逻辑
智能信息处理与仪器研究室
命题逻辑与谓词逻辑是最先应用于人工智能的两种逻辑,对于知识的形式化表示,
特别是定理的自动证明发挥了重要作用。谓词逻辑是在命题逻辑的基础上发展起来的
命题
定义1 能够分辨真假的语句 7.称做命题。
定义2 一个语句如果不能再进一步分解成更简单的语句,并且本身是一个
命题,则称此命题为原子命题。

原子命题是命题中的最基本的单位,一般用大写字母P、Q、R…表示,而命
题的真与假分别用“T”与“F”表示。
命题一般是一个陈述句,如
太阳从东边升起,雪是白色的 (是命题)
真漂亮啊!,请站起来!,你到哪里去?(不是命题)
1 1=10 (条件命题,在二进制情况下)
这盘菜太咸(是命题,但真假不能唯一确定,因人而异)
" 8."6
命题公式
智能信息处理与仪器研究室
连接词: 在命题逻辑中用连接词将一些原子命题连接起来形成复合命题。
~ : “非”或“否定”。
∨:析取,表示两个连接的命题具有“或”关系。
∧:合取,表示两个连接的命题具有“与”关系。
→:条件或蕴含,P→Q表示P蕴含Q 9.即“如果P则Q” 10.其中,P称为条件
的前件,Q称为条件的后件。
↔:双条件,P↔Q表示“P当且仅当Q”.
表1 命题逻辑真值表
" 11."7
命题公式
智能信息处理与仪器研究室
定义3: 以下面的递归形式给出命题公式的定义:
①原子命题是命题公式
②A是命题公式,则~A也是命题公式。
③若A和B都是命题公式,则A∧B 12.A∨B 13.A→B 14.A↔B也都是命题公式 。
④只有按①~③得到的公式才是命题公式。
命题公式就是按照上述规则由原子命题、连接词及圆括号所形成的字符串。有时也称
命题演算公式。
连接词的优先级别为:
~ 15.∧.∨.→.↔
命题逻辑虽然可以用来表示知识,但它有较大的局限性,无法把所描述的客观事物的结构及逻辑特征反映出来,也不能把不同事物的共同特征表示出来。
张三是李四的老师,用P表示,反映不出关系。
贝多芬是作曲家和柴可夫斯基是作曲家,用命题逻辑表示时,是作曲家的共同特征无法形式化表示出来。
" 16."8
谓词逻辑
智能信息处理与仪器研究室
谓词与个体
在谓词逻辑中,将原子命题分解为谓词与个体两部分。
如,李白是诗人,POET(LIBAI)
5>3 17. GREATER(5 18.3)
一元谓词:一个谓词与一个个体相关联。
多元谓词:一个谓词与多个个体相关联。

谓诩的一般形式:
P(x1,x2,…,xn)
其中P是谓词,x1,x2,…,xn是个体,谓词通常用大写字母,个体用小写字母表示。
P(x)是一元谓词,P(x 19.y)是二元谓词,
P(x1,x2,…,xn)是N元谓词。
在谓词P(x1,x2,…,xn)中,若x都是个体常量,变元或函数,称一阶谓词,如果x本身又是一个一阶谓词,则称二阶谓词。
" 20."9
谓词公式
智能信息处理与仪器研究室
①连接词,与命题逻辑中的连接词相同,复合谓词公式的真值表同复合命题逻辑的真值表。
②量词,全称量词(∀x) 21.它表示“对个体域中的所有(或任一个)个体x”
存在量词(∃x) 22.它表示“在个体域中存在个体x”
(∀x)(∃y)F(x 23.y):个体域中的任何个体x都存在一个个体y,x与y是朋友
(∀x)(∀y)F(x 24.y):个体域中的任何两个个体x和y,x与y都是朋友
③谓词演算公式
定义4 谓词演算中,由单个谓词构成的不含任何连接词的公式,称为原子谓词公式 25.一般地 26.形如F(x1 27.x2 28.… 29.xn)的谓词公式称为原子谓词公式 30.或简称为原子 31.其中F为n元谓词 32.而x1 33.x2 34.… 35.xn为个体变元.
" 36."10
谓词公式
智能信息处理与仪器研究室
由原子谓词公式、连接词、量词及圆括号所组成的字符串,按照上述规则构成谓词演算公式。
由原子公式的定义出发.可定义谓词演算的合式公式如下:
例如:
" 37."11
谓词公式的永真性和可满足性
智能信息处理与仪器研究室
①谓词公式的解释
定义:设D为谓词公式P的个体域,若对P中的个体常量、函数和谓词按照如下规定赋值:
为每个个体常量指派D中的一个元素;
为每个n元函数指派一个从Dn到D的映射,
其中Dn={(x1 38.x2 39.… 40.xn)| x1 41.x2 42.… 43.xn∈D}
为每个n元谓词指派一个从Dn到{F 44.T}的映射.
则称这些指派为公式P在D上的一个解释。
②谓词公式的永真性
定义:如果谓词公式P对于个体域D上的任何一个解释都取得真值T 45.则称P在D上是永真的,如是P在每个非空个体域上均永真,则称P永真。
定义:如果谓词公式P对于个体域D上的任何一个解释都取得真值F 46.则称P在D上是永假的,如是P在每个非空个体域上均永假,则称P永假。
谓词公式的永假性又称为不可满足性或不相容性。
" 47."12
谓词公式的永真性和可满足性
智能信息处理与仪器研究室
①谓词公式的可满足性
定义: 对于谓词公式P 48.如果存在至少一个解释,使得公式P在此解释下的真值为T 49.则称公式P是可满足的。

对谓词公式P,如果不存在任何解释.使得P的取值为T.则称公式P是不可满足的。不存在任何解释可使P的取值为T,即可理解为对于所有的解释都使公式P取值为F(因为谓词公式要么为T,要么为F),谓词公式P永假与不可满足是等价的。若P为永假,则也可称P不可满足的。
" 50."13
智能信息处理与仪器研究室
例1
" 51."14
谓词公式的等价性
智能信息处理与仪器研究室
定义:
设P与Q是两个谓词公式,D是它们共同的个体域,若对D上的任何一个解释,P与Q的取值都相同,则公式P和Q在域D上是等价的。如果D是任意个体域,则称P和Q
是等价的,记做P⇔Q.

常用的等价式
" 52."15
谓词公式的永真蕴含
智能信息处理与仪器研究室
定义:
对于谓词公式P和Q 53.如果P→Q永真,则称P永真蕴含Q 54.且称Q为P的逻辑结论,称P为Q的前提,记作P⇒Q.
一些永真蕴含式
" 55."16
置换与合一
智能信息处理与仪器研究室
要使计算机模拟人类智能,就必须使计算机具有推理的功能,在用各种知识表示法对知识进行表示以后,这些知识就可以输入计算机了。在基于这些知识进行推理时,模式匹配是必须要进行的一项工作。因为只有经过模式匹配,才能从知识库中选出当前适用的知识,才能进行推理。例如,在产生式系统中,为了由已知的初始事实推出相应的结论,就必须从知识库中选出与初始事实相匹配的产生式规则,然后才能运用这些产生式规则进行推理,逐
步推出结论。
基于谓词逻辑的归结推理方法是一种确定性的推理方法,所以.它所做的知识模式匹配也是一种确定性的匹配。为了使己知事实与知识库中的知识完全匹配,需要作某种变元置换,这里涉及到置换与合—的有关概念及方法。
" 56."17
置换
智能信息处理与仪器研究室
" 57."18
合一
智能信息处理与仪器研究室
" 58."19
智能信息处理与仪器研究室
例2
" 59."20
智能信息处理与仪器研究室
例2
" 60."21
智能信息处理与仪器研究室
例2
" 61."22
归结推理方法
智能信息处理与仪器研究室
人工智能的目的之一就是使计算机能够模拟人的智能,解决实际中遇到的问题。研究自动定理证明,不仅使许多数学问题可以通过定理证明得以解决,而且可以使得许多如机器人规划等非数学的问题,归结为定理证明问题而得到解决。研究用计算机实现定理证明的机械化,已是人工智能研究的一个重要领域。对于定理证明问题,如果用一阶谓词逻辑表示的话.就是要求对前提P和结论Q证明P→Q是永真的。然而,要证明这个谓词公式的永真性.必须对所有个体域上的每一个解释进行验证,这是极其困难的。为了化简问题,同数学上常采用的方法一样,可以考虑反证法。即,先否定逻辑结论Q,再由否定后的逻辑结论~Q及前提条件P出发推出矛盾,即可证明原问题。换一句话说,为了证明P→Q,只要从公式P∧~Q中推出矛盾即可,也就是说,只要证明P∧~Q是不可满足的即可。
" 62."23
谓词公式与子句集
智能信息处理与仪器研究室
对于定理证明问题,最终可以通过一阶谓词逻辑表示为P∧~Q的不可满足性问题,这里前提条件P和结论Q又都是以谓词公式表示的。当然,根据谓词公式的定义,P∧~Q也是一个谓词公式。所以,要解决的问题是要证明谓词公式的不可满足性。然而,由于谓词公式的形式干变万化,给谓词演算的研究带来一定的困难。
先介绍两种谓词演算公式的标准型,也就是范式。因而对谓词演算的研究就可以化归为对范式的研究。
" 63."24
谓词公式与子句集
智能信息处理与仪器研究室
" 64."25
谓词公式与子句集
智能信息处理与仪器研究室
" 65."26
谓词公式与子句集
智能信息处理与仪器研究室
" 66."27
谓词公式与子句集
智能信息处理与仪器研究室
" 67."28
智能信息处理与仪器研究室
例3
" 68."29
子句与子句集
智能信息处理与仪器研究室
Herbrand理论和Robinson的归结原理都是以子句集为背景开展研究的。
" 69."30
不可满足意义下的一致性
智能信息处理与仪器研究室
公式G与其子句集S并不等值,但它们在不可满足的意义下是—致的。
定理 设有谓词公式G,而其相应的子句集为S,则G是不可满足的充分必要条件是S是不可满足的。
" 70."31
Herbrand理论
智能信息处理与仪器研究室
对于一个谓词公式来说,要证明它的不可满足性是困难的。所以,需要考虑它的子句集的不可满足性。然而,对子句集的不可满足性的判定仍然是困难的,因为要判断子句集的不可满足性就要对于句集中的每一个子句逐个进行判定。由于个体变元域D的任意性以及解释个数的无限性,这实际上是一项难以完成的工作。能否针对某一个具体的谓词公式,找到一个比较简单的特殊域,只要使谓词公式在该特殊域上是不可满足的,就能保证它在任一域上也是不可满足的呢? Herbrand理论构造了这样的一个域,称为Herbrand(H域)。只要对H域上的所有解释进行判定 71.即可得知谓词公式是否是不可满足的。
" 72."32
Herbrand理论
智能信息处理与仪器研究室
" 73."33
Herbrand理论
智能信息处理与仪器研究室
" 74."34
Herbrand理论
智能信息处理与仪器研究室
" 75."35
智能信息处理与仪器研究室
例4
" 76."36
智能信息处理与仪器研究室
例5
" 77."37
智能信息处理与仪器研究室
例6
" 78."38
智能信息处理与仪器研究室
例7
" 79."39
智能信息处理与仪器研究室
例8
" 80."40
Herbrand定理
智能信息处理与仪器研究室
" 81."41
消解原理(归结原理)
智能信息处理与仪器研究室
Herbrand定理只是从理论上给出证明子句集不可满足性的可行性和方法。但要在计算机上实现其证明过程却是非常困难的。1965年,Robinson提出了归结原理 82.这是对自动推理的重大突破,使得机器定理证明变为现实。 归结原理又称为消解原理,是Robinson提出的证明子句集不可满足性,从而实现了定理证明的一种理论和方法。
子句集中各子句间的关系是合取关系,因此,只要有一个子句是不可满足的,则子句集就是不可满足的。另外,在前面已经指出,空子句是不可满足的,所以只要子句集中包含一个空子句,则此子句集就一定是不可满足的。Robinson的归结原理正是基于这一认识提出来的,其基本思想是:检查子句集S中是否有空子句,若有,则表明S是不可满足的;若没有,就在子句集中选择合适的子句对其进行归结推理,如果能推出空子句,就说明子句集S是不可满足的。
" 83."42
命题逻辑中的归结原理
智能信息处理与仪器研究室
定义 若P是原子谓词公式或原子命题,则称P与~P为互补文字。
" 84."43
命题逻辑中的归结原理
智能信息处理与仪器研究室
" 85."44
命题逻辑中的归结原理
智能信息处理与仪器研究室
" 86."45
一阶谓词逻辑中的归结原理
智能信息处理与仪器研究室
" 87."46
一阶谓词逻辑中的归结原理
智能信息处理与仪器研究室
" 88."47
一阶谓词逻辑中的归结原理
智能信息处理与仪器研究室
" 89."48
一阶谓词逻辑中的归结原理
智能信息处理与仪器研究室
在谓词逻辑中,对子句进行归结推理时,要注意以下几个问题:
" 90."49
一阶谓词逻辑中的归结原理
智能信息处理与仪器研究室
" 91."50
一阶谓词逻辑中的归结原理
智能信息处理与仪器研究室
" 92."51
一阶谓词逻辑中的归结原理
智能信息处理与仪器研究室
在命题逻辑推理中所结出的归结推理过程,在一阶谓词逻辑的
归结推理中仍然适用。
" 93."52
利用归结原理进行定理证明
智能信息处理与仪器研究室
" 94."53
利用归结原理进行定理证明
智能信息处理与仪器研究室
应用归结原理进行定理证明的步骤如下:
" 95."54
应用归结原理进行问题求解
智能信息处理与仪器研究室
" 96."55
智能信息处理与仪器研究室
例9
" 97."56
智能信息处理与仪器研究室
例10
" 98."57
智能信息处理与仪器研究室
例11
" 99."58
智能信息处理与仪器研究室
例12
" 100."59
智能信息处理与仪器研究室
例13
" 101."60
智能信息处理与仪器研究室
例13
" 102."61
智能信息处理与仪器研究室
例13
" 103."62
智能信息处理与仪器研究室
例14
" 104."63
智能信息处理与仪器研究室
例14
" 105."64
智能信息处理与仪器研究室
例14
" 106."65
智能信息处理与仪器研究室
例15
" 107."66
智能信息处理与仪器研究室
例15
" 108."67
智能信息处理与仪器研究室
例15
" 109."68
智能信息处理与仪器研究室
例15
" 110."69
智能信息处理与仪器研究室
例16
" 111."70
智能信息处理与仪器研究室
例16
" 112."71
智能信息处理与仪器研究室
例16
" 113."72
智能信息处理与仪器研究室
例16
" 114."73
智能信息处理与仪器研究室
例16
" 115."74
智能信息处理与仪器研究室
例16
" 116."75
智能信息处理与仪器研究室
例16
" 117."76
不确定推理
智能信息处理与仪器研究室
基于一阶谓词逻辑的归结推理方法所依据的证据是确定性的.即谓词所表示的知识要么为“真”,要么为“假”,其推理过程也是以数理逻辑为基础.推理过程是严密的,所推出的结论也是确定的,即结论要么成立,要么不成立。所以,基于一阶谓词逻辑的归结推理方法是一种确定性的推理方法。但是,在日常生活中。人们通常所遇到的情况是信息不够完善、不够精确,即所掌握的知识具有不确定性。人们就是运用这种不确定性的知识进行思维、推理、进而求解问题。所以,为了解决实际问题,必须对不确定知识的表示、推理过程等进行研究。
" 118."77
不确定推理的概念
智能信息处理与仪器研究室
所谓推理就是从已知事实出发,运用相关的知识(或规则)逐步推出结论或者证明某个假设成立或个成立的思维过程。其中,已知事实和知识(规则)是构成椎理的两个基本要素。巳知事实是推理过程的出发点及推理中使用的知识,将其称为证据,而知识(或规则)则是推理得以向前推进、并逐步达到最终目标的根据。
—个人工智能系统由总数据库、知识库和推理机构成。其中,总数数据库就是已知事实的集合,而知识库即是规则库,是一些人们总结的规则的集合,推理机则是由—些推理算法构成,这些算法将依据知识库中的规则和总数据库中的事实进行推理计算。基中,知识库是人工智能系统的核心。由于现实世界中的事物以及事物之间的关系极其复杂,再加上客观上存在的随机性、模糊性以及某些事物或现象暴露的不充分性,从而导致了人们对它们认识的不精确和不完全,具有一定的不确定性。
不确定性推理就是从具有不确定性的证据出发,运用不确定性的知识(或规则)库中的知识,最终推出具有一定程度的不确定性,但却是合理的或近乎合理的结论的思维过程。
" 119."78
不确定推理方法的分类
智能信息处理与仪器研究室
模型方法:
模型方法的特点是把不确定的证据和不确定的知识分别与某种度量标准对应起来,并给出更新结论不确定性的合适的算法,从而构成相应的不确定性推理模型。不同的结论不确定性更换算法就对应不同的模型。后面介绍的几种不确定性推理方法都属于模型法。
控制方法:
控制方法的特点是通过识别领域中引起不确定性的某些特征及相应的控制策略来限制或减少不确定性系统产生的影响,这类方法没有处理不确定性的统一模型,其效果极大地依赖于控制策略,控制策略的选择和研究是这类不确定性推理方法的关键:启发式搜索、相关性制导问题等是目前常见的几种控制制方法。
" 120."79
不确定推理方法的分类
智能信息处理与仪器研究室
模型方法又分为数值方法和非数值方法两大类.
数值方法是对不确定性的一种定量表示和处理方法,目前对它的研究及应用都比较多,形成了多种应用模型。它又可以按其所依据的理论不同分为基于概率的方法和模糊推理方法。基于概率的方法所依据的理论是概率沦,而模糊推理方法所依据的理论则是模糊理论。
非数值方法是指除数值方法外的其他各种处理不确定性的方法,它又包括很多方法。逻辑法就是一种非数值方法,它采用多值逻辑、非单调逻辑来处理不确定性。
" 121."80
三种不确定推理方法
智能信息处理与仪器研究室
在各类不确定性推理方法中,由于概率论有着完善的理论,同时还为不确定性的合成与传递提供了现成的公式,因而被用来表示和处理知识的不确定性,成为度量不确定性的重要手段。这种纯粹依靠概率模型来表示和处理不确定性的方法称为纯概率方法或概率方法。纯概率方法虽然有严密的理论依据,但它却要求给出事件的先验概率和条件概率,而这些数据又不易获得,因而使其应用受到限制。为此.人们经过多年的研究,在概率沦的基础上,发展了一些新的处理不确定性的方法,这些方法包括:可信度方法、主观BAYES方法和证据理论方法。
" 122."81
可信度方法
智能信息处理与仪器研究室
可信度方法是美国斯坦福大学E.H.Shortliffe等人在确定性理论(Theory of confirmation)的基础上,结合概率论等提出的一种不确定性推理方法。1976年在专家系统MYCIN中首先应用,它是不确定推理方法中应用最早、且简单有效的方法之一。
具有不确定性知识(规则)如何表示?不确定性的证据如何表示?如何进行推理计算,即如何将证据的不确定性和知识的不确定性传递到结论?
" 123."82
可信度概念
智能信息处理与仪器研究室
可信度是人们在实际生活中根据自己的经验或观察对某一事件或现象为真的相信程度:例如,孙晓强昨天没来上课,他的理由是因为肚子疼,就此理由而言,只有以下两种可能:一种是孙晓强真的肚子疼了,即理由为真;另一种是孙晓强根本没有肚子疼,只是找个借口不来上课,即理由为假。可信度也可以称做确定性因子,在以产生式作为知识表示的专家系统MYClN中,用以度量知识和证据的不确定性。显然,可信度具有较大的主观性和经验性,其准确性是难以把握的。但是,对某一具体领域而言.由于该领域专家具有丰富的专业知识及实践经验,要给出该领域知识的可信度还是完全有可能的。另外,人工智能所面临的问题,较难用精确的数学模型进行描述,并且先验概率及条件概率的确定也比较困难,因此用可信度来表示知识及证据的不确定性仍不失为一种可行的方法。
" 124."83
知识不确定性的表示
智能信息处理与仪器研究室
在基于可信度的不确定性推理模型中 125.知识是以产生式规则的形式表示的,知识的不确定性则是以可信度CF(H,E)表示的。其一般形式为
IF E THEN H (CF(H,E))
其中:
E是知识的前提条件,或称为证据。它既可以是一个简单条件,也可以是用AND及OR把多个简单条件连接起来所构成的复合条件。例如,有
E=E1 AND E2 AND (E3 0R E4)
H是结论,它可以是一个单一的结论,也可以是多个结论。
CF(H 126.E)是该条知识的可信度 127.称为可信度因子(Certainty Factor)或规则强度.
" 128."84
证据不确定性的表示
智能信息处理与仪器研究室
①单个证据的不确定性获取方法
如果支持结论的证据只有一条,则证据可信度值的确定分两种情况。
第一种情况是,证据为初始证据,其可信度的值一般由提供证据的用户直接指定,指定的方法也是用可信度因子对证据不确定性进行表示,
例如 CF(E)=0.8 129.表示证据E的可信度为0.8。
第二种情况就是用先前推出的结论作为当前推理的证据,对于这种情况的证据,其可信度的值在推出该结论时通过不确定性传递算法计算得到。证据E的可信度CF(E)也是在[-1 130.1

查看更多