人工智能与机器翻译

第3章产生式系统及其搜索方法人工智能与机器翻译主讲：杨宪泽——产生式系统及其搜索方法第3章产生式系统及其搜索方法第3章产生式系统及其搜索方法3.1产生式系统3.2产生式系统的搜索(控制)策略3.3图搜索算法3.4产生式系统的规则问题3.5应用举例3.6产生式系统的不确定性问题3.7系统设计技巧第3章产生式系统及其搜索方法3.1产生式系统产生式系统使用类似于文法的规则,对符号串作替换运算。它是智能软件中使用最普遍、最典型的一种结构。为什么要采用产生式系统作为智能软件的主要结构呢?这可以有两点理由:(1)用产生式系统结构求解问题的过程和人类求解问题时的思维过程很相象,因而可以用它来模拟人类求解问题时的思维过程;(2)可以把产生式系统作为智能软件中的基本结构单元或基本模式看待,就好象是积木世界中的积木块一样,因而研究产生式系统的基本问题就具有一般意义。第3章产生式系统及其搜索方法3.1产生式系统3.1.1产生式系统的组成部分一个智能软件用产生式系统设计的基本组成是:一个综合数据库;一组产生式规则;一个控制系统。综合数据库是产生式系统所使用的主要数据结构,用来表述问题的状态或有关事实。它包含求解问题的信息,其中有些部分可以是不变的,有些部分可能只与当前问题的解有关。人们可以根据问题的性质,用适当的方法来构造综合数据库的信息。第3章产生式系统及其搜索方法3.1产生式系统3.1.1产生式系统的组成部分产生式规则的一般形式为:条件─→行动或前提─→结论即表示成为:if┄┄then┄┄的形式。其中,左边确定了该规则可应用的先决条件;右边描述了应用这条规则所采取的行动或得出的结论。一条产生式规则满足了应用的先决条件之后,就可对综合数据库进行操作,使其发生变化。如综合数据库代表当前状态,则应用规则后就使状态发生转换,生成新状态。第3章产生式系统及其搜索方法3.1产生式系统3.1.1产生式系统的组成部分控制系统是软件的控制程序,也是规则的解释(推理)程序。它规定了如何选择一条可应用的规则对数据库进行操作,即确定了求解过程的推理路线。当数据库满足结束条件时,系统就应停止运行;还要使系统在求解过程中记住应用过的规则序列,以便最终能给出解的路径。控制系统也称控制策略,它也可以是从规则集中选择规则并作用于状态的一种广义选取函数。确定某一种策略后,可以算法的形式给出。在建立产生式系统描述时,还要给出初始状态和目标条件,具体说明所求解的问题。产生式系统中控制策略的作用就是从初始状态出发,寻求一个满足一定条件的问题状态。目标条件也是产生式系统结束条件的基础。第3章产生式系统及其搜索方法3.1产生式系统3.1.1产生式系统的组成部分上述产生式系统的定义具有一般性,它可用来模拟任一可计算过程。在研究人类进行问题求解过程时,完全可用一个产生式系统来模拟求解过程,及可作为描述搜索的一种有效方法。作为智能中的一种形式体系,它还具有以下优点:(1)适合于模拟强数据驱动特点的智能行为。当一些新的数据数入时,系统的行为就要改变;(2)易于添加新规则去适应新的情况,而不破坏系统的其他部分。这是由于产生式系统的各组成部分具有相对的独立性,因而便于扩展和修改。第3章产生式系统及其搜索方法3.1产生式系统3.1.1产生式系统的组成部分用产生式系统来求解问题,首先必须建立起问题的产生式系统描述,即规定出数据库、规则集合及其控制策略。这种把一个问题的叙述转化为产生式系统的三个组成部分,在智能技术中通常称为问题的表示。一般来说一个问题可有多种表示方式,而选择一种较好的表示是运用智能技术解决实际问题首先要考虑的,而且要有一定的技巧。建立了产生式系统描述之后,通过控制策略,可求得实现目标的一个规则序列,这就是所谓问题的解,这个解序列是根据控制系统记住搜索目标过程中用过的所有规则而构造出来的。第3章产生式系统及其搜索方法3.1产生式系统3.1.1产生式系统的组成部分在一般情况下,问题可能有多个解的序列,但有时会要求得到有某些附加约束条件的解,例如要求步数最少、距离最短等。这些约束条件通常是用耗散或代价这一概念来概括,这时问题可称为寻找具有最小耗散的解。在用产生式系统求解问题时,有时引入状态空间图。状态空间图是一个有向图,其节点可表示问题的各种状态(综合数据库),节点之间的弧线代表一些操作(产生式规则),它们可把一种状态导向另一种状态。这样建立起来的状态空间图,描述了问题所有可能出现的状态及状态和操作之间的关系,因而可以较直观地看出问题的解路径及其性质。当然,只有问题空间规模较小才可能作出状态空间图。第3章产生式系统及其搜索方法3.1产生式系统3.1.1产生式系统的组成部分建立产生式系统描述的过程,就是所谓问题的表示。对问题表示的好坏,往往对求解过程的效率有很大的影响。一种较好的表示法会简化状态空间和规则集表示,此外,高效率的问题求解过程与控制策略有关,合适的控制策略可缩小状态空间的搜索范围,提高求解的效率。从以上论述可知,用产生式系统来描述和求解问题,就是在问题空间中搜索一条从初始状态到达某一个目标状态的路径。这完全可以模拟人的求解过程,也就是可以把产生式系统作为求解问题思考过程的一种模拟。第3章产生式系统及其搜索方法3.1产生式系统3.1.2产生式系统的基本算法E1:DATA←初始事实库E2:untilDATA满足结束条件以前,doE3:beginE4:在规则集中,选某一条可用于DATA的规则E5:DATA←规则应用到DATA得到的结果E6:结束第3章产生式系统及其搜索方法3.1产生式系统3.1.3产生式系统的类型正向、逆向、双向产生式系统用产生式系统求解某一问题时,如果按照规则使用的方式或者说按推理方向来划分的话,有正向、逆向和双向产生式系统。正向产生式系统是从初始状态出发朝着目标状态这个方向使用规则,即正推的方式工作,称这些规则为F规则;若选目标状态作为初始数据库逆向进行求解,即逆向使用规则,产生子目标状态,反方向一步一步朝着初始状态方向求解,整个逆推方式工作,称逆向产生式系统,逆向应用的规则称B规则;若以双向搜索的方式(即正向和逆向同时进行)去求解问题,则称为双向产生式系统。第3章产生式系统及其搜索方法3.1产生式系统3.1.3产生式系统的类型可交换的产生式系统可交换式产生式系统的可交换性指几条规则的应用可以任意交换次序而不影响求解。一般来说,当一个产生式系统对任何一个数据库D都具有如下性质时,这样一个产生式系统是可交换的。(1)可应用于D的规则集合,使用了其中任意一条规则之后所生成的任何数据库,这样一个规则集合还适用;(2)满足目标条件的某个数据库D,当应用任何一个可应用于数据库D的规则之后所生成的任何数据库,任然满足目标条件;(3)若对D应用某一规则序列后得到的一个数据库D'(并能达到解),当改变这些规则次序后,任然可求得解,即求得D'与使用满足D的可应用规则集合中的规则次序无关。第3章产生式系统及其搜索方法3.1产生式系统3.1.3产生式系统的类型可交换的产生式系统例:给定一个整数集合的初始状态{a,b,c},设目标状态为具有a,b,c,ab,bc,ca这六个元素组成的集合。可应用的规则集合为R1:if{a,b,c}then{a,b,c,ab}R2:if{a,b,c}then{a,b,c,bc}R3:if{a,b,c}then{a,b,c,ca}显然,这个产生式实例具有可交换性。一个产生式系统具有可交换性,求解时只需搜索其中任一条途径,只要解存在就一定能找到目标,不必探索多条途径,因此不可撤回的控制方式(下节论述)在这种系统中使用很合适,因解与最初可应用的规则系列的次序无关,系统不必提供特殊选择规则的机理。第3章产生式系统及其搜索方法3.1产生式系统3.1.3产生式系统的类型可分解的产生式系统先研究一个重写问题的产生式系统,初始数据库为(C,B,Z),产生式规则如下:•R1:C→(D,L)•R2:C→(B,M)•R3:B→(M,M)•R4:Z→(B,B,M)结束条件是生成只包含M组成的数据库,即(M,…,M)。第3章产生式系统及其搜索方法3.1产生式系统3.1.3产生式系统的类型可分解的产生式系统用图搜索方式求解这个问题时,搜索得到的部分状态空间图见图26。图中只给出两条达到目标的路径和一条失败的路径。实际搜索时有可能去探索更多的路径,往往导致效率降低。对于个问题,为了避免搜索多余的路径,可以将初始数据库分解成几个可以独立加以处理的分量,分别对它们进行求解。即可以分别对每一个分量数据库,测试产生式规则可以应用的条件,如此进行下去,直到分量数据库满足某种结束条件为止。要注意一般结束条件应是所有分量数据库都已满足结束条件。第3章产生式系统及其搜索方法3.1产生式系统3.1.3产生式系统的类型可分解的产生式系统能够分解产生式系统的综合数据库和结束条件的产生式系统称为可分解的产生式系统。一个可分解的产生式系统,其基本算法描述如下:•(1)DATA:=初始数据库•(2){Di}:=DATA的分解式;每个Di元素都看成单独的数据库•(3)Until{Di}的所有元素都满足结束条件之前,do:•(4)begin•(5)从{Di}中选一个不满足结束条件的D*•(6)从{Di}中删去D*•(7)在规则集中选择一条可应用于D*的规则R•(8){di}:=R应用于D*的结果•(9)在{Di}上添加di•(10)end第3章产生式系统及其搜索方法下图为分解方式(C,B,Z)初态┌──────┼──────┐↓R2↓R4R1↓(B,M,B,Z)(C,B,B,B,M)(D,L,B,Z)↓R3↓R2↓R3(M,M,M,B,Z)(B,M,B,B,B,M)(D,L,M,M,Z)↓R3↓R3↓R4(M,M,M,M,M,Z)(M,M,M,B,B,B,M)(D,L,M,M,B,B,M)│┌─────┘│↓R4↓R3↓R3(M,M,M,M,M,B,B,M)(D,L,M,M,M,B,M)↓R3↓R3(M,M,M,M,M,M,M,B,M)─┐(D,L,M,M,M,M,M,M,M)R3↓目标(M,M,M,M,M,M,M,M,M,M)图26第3章产生式系统及其搜索方法3.2产生式系统的搜索(控制)策略在3.1.2节的算法中,如何选择一条可应用的规则,作用于当前的综合数据库,生成新的状态以及记住选用的规则序列是构成控制策略的主要内容。对大多数的智能应用问题,所拥有的控制策略知识或信息并不足以使每次通过算法E4时,一下子就能选出最合适的一条规则来,因而产生式系统还必须把E4扩大成搜索(推理)算法,以至于基本算法的每一循环中选一条规则试用,最终找出某一序列能产生一个满足结束条件的数据库为止。由此可见,高效率的控制策略需要有关被求解问题的足够知识,这样才能在搜索过程减少盲目性,比较快的找到解路径。第3章产生式系统及其搜索方法过去三十多年中,人们研究了许多种搜索算法,归纳起来主要有两类:一类是非启发式算法;另一类是启发式算法。非启发式算法是按预定的控制策略进行搜索,在其过程中获得的中间信息不用来改进控制策略。由于搜索总是按预先规定的路线进行,没有考虑问题本身的特性,所以不容易选择到最优的搜索途径,效率较低,且出现组合爆炸的频率高。启发式算法是在搜索中加入了与问题有关的启发性信息,用以指导搜索朝着最有希望的方向前进,加速问题的求解过程并找到最优解。3.2产生式系统的搜索(控制)策略第3章产生式系统及其搜索方法3.2产生式系统的搜索(控制)策略3.2.1产生式系统控制策略分类可分解的产生式系统控制策略可划分为两大类:┌不可撤回方法┌回溯方法└试探性方法─┤└图搜索方法第3章产生式系统及其搜索方法3.2产生式系统的搜索(控制)策略3.2.2不可撤回方法这种方法相当于沿着单独一条路搜索下去,利用问题给出的局部知识决定如何选取规则,就是说根据当前可靠的局部知识选一条可应用规则并作用于当前综合数据库。接着再根据新状态继续选取规则,搜索过程一直进行,不必考虑撤回用过的规则。这是由于在搜索过程中如能有效利用局部知识,即使使用了一