自然语言理解讲义第三章.ppt

《自然语言理解讲义第三章.ppt》由会员分享，可在线阅读，更多相关《自然语言理解讲义第三章.ppt（73页珍藏版）》请在装配图网上搜索。

1、自然语言理解讲义,第三章 特征与扩充文法,主要内容,特征系统与扩充文法 英语基本特征系统 词语形态分析与词典 一个带特征的文法及其分析 扩充转移网络 通用特征系统与合一文法,特征系统与扩充文法(1),语言中成分之间的搭配需要满足一定的约束，普通的上下文不容易处理这样的情况，需要进行扩充。例如，对于规则NPART N，在处理英语句子时可改写为 NP-sART-s N-s 及 NP-pART-p N-p s与p分别表示单数与复数。 这样显然很麻烦。 另一种方法是定义成分的特征。例如用特征NUMBER(取值可以是s(单数)或p(复数)可对上诉特征进行如下扩充 NPART N仅当NUMBER1与NUM

2、BER2一致时适用,特征系统与扩充文法(2),更方便的是使用一种特征结构(feature structure)来定义成分。一特征结构是一个从特征到定义某成分的相关特征的值的映射。例如，冠词a的特征结构可表示为 ART1: (CAT ART ROOT a NUMBER s) 通常词性特征的名省略。于是上述特征结构又可表示为 ART1: (ART ROOT a NUMBER s),特征系统与扩充文法(3),某些复杂特征结构的特征值可以是另一特征结构。这时需要用一些特殊的特征名：1、2、3等等，来表示第一个子成分、第二个子成分、第三个子成分。例如名词短语a fish的特征结构可表示如下 NP1: (

3、NP NUMBER s 1 (ART ROOT a NUMBER s) 2 (N ROOT fish NUMBER s) 也可以用后面的分析树的形式来表示。,特征系统与扩充文法(4),特征系统与扩充文法(5),扩充文法中的重写规则将采用特征结构。而且，规则中的特征值往往需要采用变量的形式，例如关于简单名词短语的规则可表示为 (NP NUMBER ?n)(ART NUMBER ?n) (N NUMBER ?n) 这就是说，NP成分可以包含两个子成分，其中第一个子成分是ART，第二个是N；而这三个成分的NUMBER (数)特征必须相同。在规则中引入特征值变量，使规则的适用范围更广泛。,特征系统与扩

4、充文法(6),根据这条规则，NP1是合法的成分。而 *(NP 1 (ART NUMBER s) 2 (N NUMBER s) 不能被规则所接受，因为NP没有NUMBER特征。 成分 *(NP NUMBER s 1 (ART NUMBER s) 2 (N NUMBER p) 也不合理，因为N的NUMBER特征的值与其他成分的NUMBER特征值不同。,特征系统与扩充文法(7),变量在表达成分的二义性方面也很有用。例如单词fish既可以是单数也可以是复数，这样在词典中可表示为 (N ROOT fish NUMBER ?n) 以说明fish的NUMBER特征可取(取值范围内的)任意值。 在更多情况下，

5、某特征能取的值是一个范围(可能取值集合的子集)，而不是任意值。这时可采用约束变元来进行表示：在变元后面用一个表将变元能取的值全部列出来。例如?ns p表示变元?n只能取值s或p。因而单词fish可表示为 (N ROOT fish NUMBER ?ns p) 甚至简单表示为 (N ROOT fish NUMBER s p),英语基本特征系统(1),人称和数 主语和(主)动词除了在数上要一致以外，在人称(person)上也要一致。特征person的可能值包括： 第一人称(First Person(1)： 第二人称(Second Person(2)： 第三人称(Third Person(3)： 人称

6、和数经常一起出现，所以通常把它们合在一起用一个特征AGR来表示。AGR有6个可能值：第一人称单数(1s)，第二人称单数(2s)，第三人称单数(3s)，第一人称复数(1p)，第二人称复数(2p)，第三人称复数(3p)。 are的AGR特征的取值可为2s, 1p, 2p, 3p。,英语基本特征系统(2),动词形式 英语中动词有时态的变化，动词形式用特征VFORM表示，其取值包括： base动词原型 pres一般现在时 past一般过去时 fin限定式(finite，等价于pres, past) ing现在进行时 pastprt过去完成时 inf不定式,英语基本特征系统(3),动词次范畴 动词次范畴

7、特征，SUBCAT，用来处理词与其补足语之间的相互作用。为方便记忆，SUBCAT的值由补足语中各部分的主要语法类所组成。若某语法类的值被限定为一特征值，则在类名之后加一冒号，然后紧跟该值。如SUBCAT值_np_vp:inf用来表示由一NP跟一个动词不定式(即VFORM为inf的VP)所组成。而关于VP的规则 (VP)(V SUBCAT _np_vp: inf) (NP) (VP VFORM inf) 表示包含一SUBCAT值为_np_vp:inf的动词的VP，动词后面应该有一个NP，然后跟一个VFORM值为inf的VP(即一动词不定式)。,英语基本特征系统(4),动词次范畴 很多动词后面的补

8、语结构需要特定介词的短语，或者具有特定功能的介词短语。下面用PP表示介词短语。而关于PP的特征是PFORM。若PFORM的值为TO，表示介词短语必须以to开头；若值为LOC，则必须是描述地点的PP；若值为MOT，则描述的是路径或运动方向，如We walked to the store.,英语基本特征系统(5),关于LOC与MOT的区别，可比较 Jack put the box in on by the corner. (OK) *Jack put the box to from along the corner. (ill-formed),英语基本特征系统(6),值 动词例子例句 _none

9、laughJack laughed. _np findJack found a key. _np_np giveJack gave Sue the paper. _vp: inf wantJack wants to fly. _np_vp: inf tell Jack told the man to go. _vp: ing keepJack keeps hoping for the best. _np_vp: ing catchJack caught Sam looking at his desk. _np_vp: base watchJack watched Sam look at his

10、 desk.,以NP/VP组合为值的SUBCAT,英语基本特征系统(7),值介词例子 例句 TOto I gave it to the bank. LOCin, on, by, inside, on top ofI put it on the desk. MOTto, from, along I walked to the store.,介词短语PFORM特征的某些值,英语基本特征系统(8),有些动词可带从句作补足语。例如，动词tell可带以that开头的从句；这样tell的一个SUBCAT值为_s:that。类似地，wish的补语从句以for开头(We wished for the rain

11、 to stop)，wish的一个SUBCAT值为_s:for。句子及从句的结构统称S结构。,英语基本特征系统(9),值 动词例子例句 _np_pp:togive Jack gave the key to the man. _pp:loc be Jack is at the store. _np_pp:locput Jack put the box in the corner. _pp:mot go Jack went to the store. _np_pp:mottake Jack took the hat to the party. _adjp be, seem Jack is happ

12、y. _np_adjpkeep Jack kept the dinner hot. _s:that believe Jack believed that the world was flat. _s:for hope Jack hoped the man to win the prize.,更多的SUBCAT值,英语基本特征系统(10),有些特征只有两种可能的取值，称为布尔特征。相应的两个特征值用和来表示。例如，我们将用特征INV来表示一个S结构是否为倒装的。句子Jack laughed的S结构的INV特征值是；而句子Did Jack laugh?的S结构的INV特征值是。通常会把布尔特征的值

13、放在特征名之前作为前缀，这样就可以说一个结构具有特征INV或INV 。其他布尔特征也可以类似地进行表示。 在很多情况下给特征指定默认值会很有用，特别是对于布尔特征，经常指定其默认值为。,词语形态分析与词典(1),词典须包含所有能被使用的不同词的信息，这包括对每个词的相关特征的取值限制。对于多义词，在词典中应该有多个条目，每个条目对应一种用法。 英语中词语大多遵循一些有规律的词语形态模式。如果没有词语形态分析，词典中就必须包含词的每一种变换形式。例如，动词“want”就需要有六个词条，分别是：want(基本形式和现在时)，wants，wanting，wanted(过去时和过去分词形式)。这显然是

14、不必要的。 实际上，结合前面讲过的有限自动转录机的方法，将句子中词的后缀剥离出来，则词典中只须存储词的基本形式，然后使用上下文无关规则将词与后缀相结合，从而派生出其他词条。,词语形态分析与词典(2),例如下面是产生动词现在时的规则： (V ROOT ?r SUBCAT ?s VFORM pres AGR 3s) (V ROOT ?r SUBCAT ?s VFORM base)+S 在这里，+S是一种只包含后缀词素“s”的新词类。给定 输入串want +s，该规则结合下面的词条： want: (V ROOT want SUBCAT _np _vp:inf _np_vp:inf VFORM bas

15、e) 会生成下面的语法成分： want: (V ROOT want SUBCAT _np _vp:inf _np_vp:inf VFORM pres AGR 3s),词语形态分析与词典(3),另外一条规则可以生成非第三人称单数情况下的一般现在时成分，对于大部分动词来说，该成分与词根形式一致： (V ROOT ?r SUBCAT ?s VFORM pres AGR 1s 2s 1p 2p 3p) (V ROOT ?r SUBCAT ?s VFORM base) 这条规则可以把任意的动词基本形式直接转化为现在时，但这对不规则变化的动词是不适用的。例如，动词be就不能用作一般现在时(*We be a

16、t the store)。要处理这种情况可以引入二元特征IRREG-PRES 。具体地说，特征为+IRREG-PRES的动词存在不规则的现在时形式。因此上诉规则可正确表述如下： (V ROOT ?r SUBCAT ?s VFORM pres AGR 1s 2s 1p 2p 3p) (V ROOT ?r SUBCAT ?s VFORM base IRREG-PRES ),词语形态分析与词典(4),对于变化比较规则的词，可以通过句法规则来把握。而不规则的词则需要在词典中指明。是否规则变化将分别用特征IRREG-PRES(现在时)、IRREG-PAST(过去时)、IRREG-PL(复数)等来表示。对

17、于这几个特征，特征值将作为后缀。 例如，IRREG-PRES表示现在时态是规则变化的。对于完成时，将用特征EN-PASTPRT来区分加-en(EN-PASTPRT)与加-ed(EN-PASTPRT)两种完成时后缀。 在词典中将采取默认机制，以上二元特征只需对不规则动词进行说明，规则动词的默认值设为“”。,词语形态分析与词典(5),现在时 . (V ROOT ?r SUBCAT ?s VFORM pres AGR 3s) (V ROOT ?r SUBCAT ?s VFORM base IRREG-PRES)+S . (V ROOT ?r SUBCAT ?s VFORM pres AGR 1s 2

18、s 1p 2p 3p) (V ROOT ?r SUBCAT ?s VFORM base IRREG-PRES ) 过去时 . (V ROOT ?r SUBCAT ?s VFORM past AGR 1s 2s 3s 1p 2p 3p) (V ROOT ?r SUBCAT ?s VFORM base IRREG-PAST)+ED,词语形态分析与词典(6),过去完成时 . (V ROOT ?r SUBCAT ?s VFORM pastprt) (V ROOT ?r SUBCAT ?s VFORM base EN-PASTPRT)+ED . (V ROOT ?r SUBCAT ?s VFORM pa

19、st) (V ROOT ?r SUBCAT ?s VFORM base EN-PASTPRT)+EN 现在进行时 . (V ROOT ?r SUBCAT ?s VFORM ing) (V ROOT ?r SUBCAT ?s VFORM base)+ING 名词复数 . (N ROOT ?r AGR 3p) (N ROOT ?r AGR 3p IRREG-PL)+S,词语形态分析与词典(7),词语形态分析与词典(8),一个带特征的文法及其分析(1),一些约定 若某特征值只会作为一个特征的值，则当规则中有这样的值时，可省去特征名。如inf只能是特征VFORM的值，则(VP VFORM inf)将被

20、简记为VPinf。 布尔特征的表示也可简化：对于布尔特征B，将用C+B表示成分(C B )。 通常限定重写规则左边成分很多特征的取值为规则右边主要子成分相应特征的值相同，这些特征称为中心特征(head feature)。如下面规则所示，在所有关于动词短语的规则中，VP和VP中的主动词的VFORM与AGR值是相同的： (VP VFORM ?v AGR ?a) (V VFORM ?v AGR ?a SUBCAT _np_vp: inf) (NP) (VP VFORM inf),一个带特征的文法及其分析(2),如果中心特征被独立地定义，则系统可在需要的时侯自动地将这些特征加到规则中。在VFORM与A

21、GR被定义为中心特征的情况下，上面的规则可简化为 VP(V SUBCAT _np_vp: inf) NP (VP VFORM inf) 若加上所有约定，则此规则还可简化为 VPV_np_vp:inf NP VPinf,一个带特征的文法及其分析(3),. SINV (NP AGR ?a) (VPpres past AGR ?a) . NP (ART AGR ?a) (N AGR ?a) . NP PRO . VP V_none . VP V_np NP . VP V_vp:inf VPinf . VP V_np_vp:inf NP VPinf . VP V_adjp ADJP . VPinf T

22、O VPbase 0. ADJP ADJ 1. ADJP ADJ_vp:inf VPinf S和VP的中心特征：VFORM，AGR NP的中心特征： AGR,一个带特征的文法及其分析(4),. (S INV VFORM ?vpres past ) (NP AGR ?a) (VP VFORM ?vpres past AGR ?a) . (NP AGR ?a)(ART AGR ?a) (N AGR ?a) . (NP AGR ?a)(PRO AGR ?a) . (VP AGR ?a VFORM ?v)(V SUBCAT _none AGR ?a VFORM ?v) . (VP AGR ?a VFO

23、RM ?v)(V SUBCAT _np AGR ?a VFORM ?v) NP . (VP AGR ?a VFORM ?v) (V SUBCAT _vp:inf AGR ?a VFORM ?v) (VP VFORM inf) . (VP AGR ?a VFORM ?v) (V SUBCAT _np_vp:inf AGR ?a VFORM ?v) NP (VP VFORM inf) . (VP AGR ?a VFORM ?v) (V SUBCAT _adjp AGR ?a VFORM ?v) ADJP . (VP SUBCAT inf AGR ?a VFORM inf) (TO AGR ?a V

24、FORM inf) (VP VFORM base) 0. ADJPADJ 1. ADJP(ADJ SUBCAT inf) (VP VFORM inf),一个带特征的文法及其分析(5),S3s,NP3s,VPpres, 3s,Vpres, 3s, _none,ART3s,N3s,the,man,cries,NP3s,VPpres, 3s,Vpres, 3s, _vp:inf,PRO3s,He,wants,S3s,VPinf,VPbase,to,Vbase, _adjp,ADJP,be,happy,一个带特征的文法及其分析(6),带特征的分析法 规则中句子成分的特征值可为变元，因此在句法分析的过程

25、中经常需要对这样的变元进行实例化，并同时判断给定句子是否合法。 考虑规则 1. (NP AGR ?a) (ART AGR ?a) (N AGR ?a) 现在用以下成分对规则1进行扩展： 2. (ART ROOT A AGR 3s) 为了使1能适用，1中的变元?a必须被实例化为3s，这将产生 3. (NP AGR 3s) (ART AGR 3s) (N AGR 3s),一个带特征的文法及其分析(7),带特征的分析法 而3就可被扩展为 4. (NP AGR 3s)(ART AGR 3s) (N AGR 3s) 现在考虑用单词dog的成分对4进行扩展 5. (N ROOT DOG1 AGR 3s)

26、因为AGR特征的值相同，所以可进行扩展并产生 6. (NP AGR 3s)(ART AGR 3s) (N AGR 3s) 这意味着分析器已得到了一个形如(NP AGR 3s)的成分。,一个带特征的文法及其分析(8),给定一条边A，其在句号后的成分记为NEXT，并设用来扩展边A的新成分为X，上述算法可更精确的描述如下： 为NEXT与X的公共特征中的变元进行实例化， 生成一条新边A，A是A的一份拷贝，它与A的不同之处仅仅在于步骤(a)所确定的变元实例化上， 采取与线图分析法一样的办法对A进行更新。 对于像?a3s 3p这样的受限变元，匹配过程是一样的，但变元只能被实例化为所列值中的一个。,一个带特

27、征的文法及其分析(9),如果规则和成分都包括变元，则匹配后的结果也应该是一个变元，而对于受限变元，匹配后的取值范围是两者的交集(若交集为空则失败)。例如，考虑用成分(ART ROOT the AGR ?v3s 3p)，即单词the，对1进行扩展。这时?a必须实例化为?v3s 3p，然后得到规则(边) (NP AGR ?v3s 3p) (ART AGR ?v3s 3p) (N AGR ?v3s 3p) 这条边可被(N ROOT dog AGR 3s)扩展，因为?v3s 3p能被实例化为值3s，而结果也与6相同。但是图中the的条目并没有因这一操作而改变，其AGR值仍为?v3s 3p，它的AGR特

28、征只是在这条边中才被限制为3s。,一个带特征的文法及其分析(10),另外一种扩展对于记录句法分析的结构非常有用：每次对边进行扩展时，句法分析器会自动添加子成分的特征(1,2,关键看添加的是哪个子成分)，这些子成分特征的值已经在线图中。根据此处理办法，假定线图中已包含了两个成分ART1和N1，它们分别对应于词语“the”和”dog”，则加入到线图中关于“the dog”的语法成分为 (NP AGR 3s 1 ART1 2 N1) 其中，ART1=(ART ROOT the AGR 3s 3p)，N1=(N ROOT dog AGR 3s)。注意，ART1的AGR特征保持不变，因此在可能的时候，它

29、可以用于其他需要作为3p值的分析当中去。,一个带特征的文法及其分析(11),通过扩展边和语法成分创建的扩充手段，前面给出的任何一种线图分析算法均可以处理扩充文法。 例，用前面给出的扩充文法来分析英文句子 “He wants to cry”. 用规则3 (NP AGR ?a)(PRO AGR ?a) 生成语法成分NP1。为了匹配成分PRO1，变量?a实例化为3s。因此产生新成分为： NP1：(CAT NP AGR 3s 1 PRO1),一个带特征的文法及其分析(12),接下来，考虑用规则4建立成分VP1，即 (VP AGR ?a VFORM ?v)(V SUBCAT _none AGR ?a V

30、FORM ?v) 为了让规则的右边和成分V2进行匹配，变量?v必须实例化为“base”，而V2的AGR特征没有专门定义，所以取其默认值“-”。因此，得到的新成分为： VP1：(CAT VP AGR VFORM base 1 V2) 一般来说，线图中并不给出默认值。采取类似的方法，运用规则9，TO1和VP1可以生成VP2；运用规则9，V1和VP2生成VP3。最后，运用规则1，由NP1和VP3可生成S1。最终的线图见下页。,扩充转移网络(1),加入特征的递归转移网络称为扩充转移网络(ATN)。 ATN中的特征通常称为寄存器(register)。通过给每个网络设置一组寄存器，可以方便地生成句子成分的

31、结构。 每当压入一个新网络，一组新的寄存器将被生成。遍历网络时，寄存器的值可通过与每条弧相关联的动作来设置。 当网络被弹出时，相应的寄存器被组合起来以产生一个新的成分结构，而成分的CAT为该网络名。,扩充转移网络(2),一个简单的NP网络,扩充转移网络(3),在ATN中，若当前分析所走的弧表示词性，如文法中的边1，那么由输入词所产生的成分将用一个特殊变量*来表示(*是输入语句中当前正被加工的部分)。而动作 DET:=* 将这一成分赋给寄存器DET，这条弧的第二个动作 AGR:=AGR* 把新词(*中的成分)的AGR寄存器值赋给网络的AGR寄存器。,扩充转移网络(4),一致性检查在测试中指明。一

32、个测试是一表达式。若表达式返回非空值，则测试成功；返回空值或nil则失败。若一测试失败，则相应的边不能被转移。文法3.10中弧2的测试表示：该边成功仅当网络的AGR特征与新单词(*中的名词成分)的AGR寄存器的交集非空。,扩充转移网络(5),一个简单的S网络,扩充转移网络(6),对压入(push)边的处理是类似的。例如，通过转移到NP网络产生的成分的值以*的形式返回。所以上面的文法中，从S到S1的边的动作 SUBJ:=* 将把NP网络产生的成分赋给SUBJ寄存器。而5上的测试实际上是要求句子的主谓应该一致。 例：分析句子1 The 2 dog 3 saw 4 Jack 5,扩充转移网络(7),

33、对第一个NP网络调用的跟踪：S网络的边4 步骤 节点 位置 通过的边 寄存器设置 2. NP 1 1 DETthe AGR3s 3p 3. NP1 2 2(测试交集 HEADdog 3s 3p3s) 4. NP2 3 pop 返回(NP DET the HEAD dog AGR 3s) 对第二个NP网络调用的跟踪：S网络的边4 步骤 节点 位置 通过的边 寄存器设置 7. NP 4 3 NAMEJack AGR3s 8. NP2 5 pop 返回(NP NAME Jack AGR 3s),扩充转移网络(8),S网络的跟踪 步骤 节点 位置 所走的边 寄存器设置 1. S 1 边4, 成功 SU

34、BJ(NP DET the (见对NP HEAD dog 网的跟踪) AGR 3s) 5. S1 3 边5(测试 MAIN-Vsaw 3s1s,1p, AGR3s 2s,2p,3s,3p 6. S2 4 边6, 成功 OBJ(NP NAME Jack (见前面的跟踪) AGR 3s) 9. S3 5 弹出边成功 返回 (S SUBJ(NP DET the HEAD dog AGR 3s) MAIN-V saw AGR 3s OBJ(NP NAME Jack AGR 3s),扩充转移网络(9),边 测试 动作 S/1 none SUBJ:=* MOOD:=DECL S1/1 AGRSUBJAGR

35、* MAIN-V:=* S2/1 SUBCATMAIN-V OBJ:=* _np, _np_np SUBCAT:= SUBCATMAIN-V_np _np_np S2/2 SUBCATMAIN-V_none SUBCAT:=_none S3/1 SUBCATMAIN-V_np_np IOBJ:=OBJ OBJ:=* S5/1 none MODS:=Append(MODS, *),S,S1,S2,NP,verb,NP,S3,pop,5,1,S4,2,jump,jump,2,NP,1,1,PP,2,扩充转移网络(10),边 测试 动作 NP/1 none DET:=* NP/2 none PRO:

36、=* NP/3 AGR*3p HEAD:=* AGR:=AGR* NP/4 none NAME:=* NP1/1 none ADJS:=Append(ADJS,*) NP1/2 AGRAGR* HEAD:=* AGR:= AGRAGR* NP2/1 none MODS:=Append(MODS,*),扩充转移网络(11),边 测试 动作 PP/1 none P:=* PP1/1 none POBJ:=*,PP,PP1,PP2,prep,NP,pop,扩充转移网络(12),寄存器的预置 类似程序设计语言中的参数传递，在ATN中，当一个网络被调用时，可以对该网络的某些寄存器进行预设(初始化)。在最

37、初的ATN系统中，这一功能被称作SENDR动作。SENDR动作的作用在于向新网络传递信息并指导新网络对新成分的分析。,扩充转移网络(13),例如，考虑象want和pray这种类型的动词，他们必须以to开头的动词不定式作补语，这包括 _vp:inf Mary wants to have a party. _np_vp:inf Mary wants John to have a party. 在前面的上下文无关文法中，这些补语被作为是VFORM值为inf的VP来处理的。为了在ATN中进行同样的分析，需要调用VP的相应网络来进行分析，但需要将该网络的VFORM寄存器的值预置为inf。,扩充转移网络(

38、14),另一常用分析是将补语看作特殊的句子形式，其中，句子中具备逻辑上可理解的主语。例如上面的第一句中不定式的主语是Mary，第二句中不定式的主语则是John。为达到这一分析，很多ATN语法都会在调用新的S网络时预置SUBJ寄存器的值。,扩充转移网络(15),SETR：把一个值送入指定的寄存器。 SENDR：把一个值送入下层网络。 APPEND：把一个值附加到当前寄存器的值中去。,通用特征系统与合一文法(1),特征系统与合一文法 一个特征结构F1包含另一特征结构F2(也称F2包含于F1)，若F2中的每个特征值都可被F1中的相应特征取到。例如，特征结构 (CAT V) 包含特征结构 (CAT V

39、 ROOT cry) 因为前一结构的ROOT特征可取任意值。,通用特征系统与合一文法(2),下面两个特征结构 (CAT V (CAT V ROOT cry) VFORM pres) 则互不包含，因为两个结构都有对方所不含的信息。,通用特征系统与合一文法(3),如果特征结构F2包含于F1，记为F2F1。 定义(合一与最一般合一) 设F1和F2是两个特征结构，如果它们都包含另一特征结构F3，则称F3为F1和F2的一个合一。若除此之外，对F1和F2的任何一个合一F，皆有FF3，则F3还是F1和F2的最一般合一。,通用特征系统与合一文法(4),(CAT V 和 (CAT V ROOT cry) VFO

40、RM pres) 的最一般合一是 (CAT V ROOT cry VFORM pres),通用特征系统与合一文法(5),下面两个特征结构 (CAT V (CAT V AGR 3s) AGR 3p) 不存在合一。 事实1 设F1和F2是两个特征结构，它们有合一F3，则它们一定也有唯一的最一般合一F4，使F4F3。,通用特征系统与合一文法(6),合一也可以用来定义文法。一个像SNP VP这样的规则可以表述为如下的合一文法 X0X1 X2 CAT0=S CAT1=NP CAT2=VP AGR0=AGR1=AGR2 VFORM0=VFORM2 这意味着成分X0可由成分X1和X2组成的序列构成，如果：X

41、0的CAT为S、X1的CAT为NP、X2的CAT为VP、所有三个成分的AGR特征值相同，且X0与X2的VFORM特征值相同。,通用特征系统与合一文法(7),若CAT值总被指明，上述规则可简写为 SNP VP AGR=AGR1=AGR2 VFORM=VFORM2 其中CAT值直接用于规则。注意下标0也被省略。,通用特征系统与合一文法(8),运用上述约定对前面文法的部分规则进行改写，得到如下所示的合一文法。,1. SNP VP AGR=AGR1=AGR2 VFORM=VFORM2 2. NPART N AGR=AGR1=AGR2 8. VPV ADJP SUBCAT1=_adjp VFORM=VF

42、ORM1 AGR=AGR1 10. ADJPADJ,通用特征系统与合一文法(9),基于合一的形式系统可以通过将特征结构表示为有向图(Directed Acyclic graph, DAG)而精确定义。特征结构的每个成分和(特征的)值表示为节点，特征则表示为带标记的边。例如，下面两个成分可表示为如下页所示的有向图： N1: (CAT N N2: (CAT N ROOT fish AGR 3s) AGR 3s 3p),通用特征系统与合一文法(10),通用特征系统与合一文法(11),在有向图中没有输入边(incoming)的节点称为源(source)，如前页图的节点N1和N2。特征结构的有向无环图有

43、唯一的源点，称为根节点(root node)；有向图也叫做置根于(rooted)该节点。有向图中没有输出边(outgoing)的节点称为汇(sink)。汇点是原子特征或原子特征集合所标记的特征结构(如3s 3p)。,通用特征系统与合一文法(12),两个特征结构的合一可通过图合一算法来定义。此算法以两个有根节点的有向图作为输入，输出则是两个结构最一般合一的有向图。,输入：根节点为Ni和根节点为Nj的有向图 、若Ni和Nj相等，则成功并返回Ni。 、若Ni和Nj都是汇点， . 如果它们的标记集合的交集非空，则返回一个新节点，该节点的标记为Ni和Nj的交集。 . 否则，两个图不能合一。 、若Ni和N

44、j不是汇点，则创建一个新节点N。对每条由Ni指向NFi的标记为F的边， . 如果有一条从Nj到NFj的标记为F的边，则递归地合一NFi和NFj。并在成功返回时，构造一条从N到返回节点的标记为F的边。 . 如果没有从Nj到NFj的标记为F的边，则构造一条从N到NFi的标记为F的边。 . 对于每条从Nj到NFj的标记为F的边，如果找不到离开Ni的标记为F的边，则构造一条从N到NFj的标记为F的边。,通用特征系统与合一文法(13),运用图合一算法，可将下图的两个结构合一为 N3: (CAT N ROOT fish AGR 3s),通用特征系统与合一文法(14),有了图合一算法，我们就能够得到构造新成

45、分的算法，而这可用于任何标准的分析器。算法在构造一个类型为C的新成分时，要用到带特征(合一)等式的重写规则，特征(合一)等式的形式为Fi=V，其中Fi是(规则右边)第i个子成分的F特征，V可以是具体的值或另一特征名。,通用特征系统与合一文法(15),给定规则X0X1 Xn及一组形如Fi=V的特征等式。SC1,SCn是 对应于X1 Xn的子成分。算法将构造一个满足所有特征等式的有向图。 、构造新特征结构的根节点CC0。 、作以SCi为根节点的图的一份拷贝(称拷贝的根节点为CCi)，i=1,n。增加 一条从CC0到每个CCi的标记为i的边。 、对于每个形如Fi=V的特征等式，其中V是一个值。沿标记

46、为F的边从节点CCi到另一节点Ni，将Ni与V合一。 、对于每个形如Fi=Gj的特征等式， . 如果有一条从CCi出发的标记为F的边及一条从CCj出发的标记为G的边，则 . 沿F边到达节点Ni，沿G边到达节点Nj； i. 用图合一算法对Ni和Nj进行合一，并(在成功时)构造新节点X； ii. 将所有指向Ni或Nj的改为指向X； . 如果没有从CCi出发的标记为F的边，但有一条从CCj到节点Nj的标记为G的边，则添加一条从CCi到节点Nj的标记为F的边； . 如果有一条从CCi到节点Ni的标记为F的边，但没有从CCj出发的标记为G的边，则添加一条从CCj到节点Ni的标记为G的边。,通用特征系统与合一文法(16),考虑一个例子。假定如下两个成分(表示在下页图中)已预先定义： ART1: (CAT N N1: (CAT N ROOT the ROOT fish) AGR 3s 3p) AGR 3s 3p) 新成分NP将通过规则2(NPART N)来生成。相应等式为 CAT0=NP CAT1=ART CAT2=N AGR0=AGR1=AGR2,通用特征系统与合一文法(17),the和fish的DAG,通用特征系统与合一文法(18),名词短语the fish的DAG,