链语法介绍
常宝宝，1999年4月25日
1.	形式语法系统的分类

Unification-based

Word Grammar

Category-based

Formal grammatical system
(Grammar Formalism)

……

LFG

FUG

GPSG HPSG

TAG

TG GB 

Link Grammar

Categorial Grammar

Dependency Grammar

Word-based

(1)关于category-based Grammar
在Catrgory-based类的语法系统中都使用(1)类(Category);和(2)成分(Constituent)两个概念描述语言现象。
从TG到Unification-based语法系统，带来了两个特别是对计算语言学颇有吸引力的好处。(1)取消了转换规则；(2)引入了复杂特征集和合一运算。
这些形式语法系统的基础都是上下文无关语法，从这些形式语法系统的发展可以看出，人们尽力在力图设法避免这个不稳定的根基带来的局限性，而使得形式语法系统能够处理上下文敏感(context-sensitive)的语言现象。
(2) 关于Word-based Grammar
反映了语法理论的词汇主义倾向，在词汇主义理论中，关于语言的所有知识都记录在词典中。在这些体系中，没有明显的语法规则，而代之以元规则(Meta-rule)。
2. 链语法的提出
由CMU计算机学院的Daniel Sleator、Columbia University 音乐系的Davy Temperley共同提出，最早的文章发表于1991年，题目是“Parsing English with a Link Grammar”。
目前基于Link Grammar研究并不很常见。
2.	链语法的形式定义和基本概念
(1)	形式语法系统G必须回答的问题
G所定义的语言是什么？什么样的符号串是G所定义的语言L(G)中的合法句子?形式语法系统怎样生成自然语言中合法的句子？怎样排除掉不合法的句子。链语法对这些问题同样要做出回答。
(2)	一部链语法(Link Grammar)就是一个单词的集合，其中的每个单词后面记录着各自的链接要求(Linking requirement)。下面我们会进一步谈到，这些链接要求可以通过一系列链接子表达式(formula of connectors)指定。
(3)	怎样判定一个单词串是否链语法所定义的语言中的句子？
一个由单词组成的串(word sequence)，如果在单词之间存在满足下列条件的链(link)的话，(或者说，能够在单词之间画出一些链，并且这些链满足下面的条件)，就说，这个单词串是链语法所定义的语言中的句子(sentence)。
首先这些链满足了其中所有单词的链接要求，其次满足下面4条元规则。
平面性(Planarity)，这些链之间互相不交叉(do not cross)。
连通性(Connectivity)，这些链足以把所有的单词链在一起。
顺序性(Ordering)，公式中较左边的链接子必须和距离单词较近的单词链接，反之，公式中较右边的链接子必须和距离单词较远的单词链接。
排它性(Exclusion)，一对单词之间同时不能有两条链链接。
	下面给出一部含有7个单词的链语法，对上面的一些概念进行解释。

words	formula	
a the	D+	
snake cat	D- & (O- or S+)	
chased	S- & O+	
ran	S-	
Mary	O- or S+	

	简单的链接表达式由链接子(connector)、二元操作符&和or以及圆括号组成。
	每个链接子(connector)由名字(name)和后缀(suffix)两部分组成。后缀有两个，分别是+和-。+和-表示链接的方向，+表示向右面链接，-表示向左面链接。
	单词串中某个单词如果有一个向右的链接子，例如X+，而另一个单词有一个向左的链接子X-，那么这两个链接子相互匹配(match)，(这里暂把匹配的含义定义为两个链接子的名字相同，)这两个单词之间可以画一条X链。同时我们可以说，链接子X+或X-得到了满足(Satisfication)或说链接满足了链接子X+或X-。
	在链接子被满足的基础上，可以定义公式的满足。
	公式X & Y要被满足，则链接必须同时满足链接子X和Y。
	公式X or Y要被满足，则链接必须满足链接子X和Y中的一个。
接下来我们看看下面两个单词串是否为上述语法定义的语言中的合法句子。
(1)	 the cat chased a snake.
(2)	 *the Mary chased cat.
首先看单词the 的链接表达式，其中只有一个向右的链接子D+，再看单词cat的链接表达式 D- & ( O- or S+)，其中有一个D-，可以和单词the的D-匹配，在它们之间可以画一条D链，单词the 的链接要求得到满足。但单词cat的链接表达式尚未完全得到满足，要使cat的链接表达式完全得到满足，链接子O-和S+必须有一个得到满足。再看chased的链接表达式 S- & O+。可以在cat 和chased 之间画一条S链，同样的道理，在chased和snake之间也可以画一条O链，在单词a和snake 之间画一条D链，到此为止，词串中所有单词的链接要求都得到了满足，并且得到下面的一个图。

D

S

D

O

	
  the		cat		 chased		 a 		snake

	进而检查这这种链接方法是否满足4条元规则，首先满足平面性，4条链互不交叉。连通性也满足，四条链把词串中所有5个单词都链在一起。顺序性，可以看单词snake，在snake的链接表达式中，D-靠左，所以链接和它距离较近的单词a，O-链靠右，链接和它距离较远的单词chased。最后，排它性也得到满足，所有的单词对之间都只有一条链链接。所以，现在可以说，单词串(1)是语法所定义的语言中的合法句子。
	链语法把这样一组可以证明一个单词串是链语法所定义语言中的合法句子的链的集合叫做一个链接集(Linkage)，链接集是用链语法分析句子所得到的结果，正如一般句法分析中所得到的句法树一样。
	按照同样的原则，对于词串(2),我们可以画出下面的链接图。

D

S

O

O

S

  the		Mary		 chased		 cat

	同样所有单词的链接要求都得到了满足。仔细检查，顺序性未得到满足，单词cat的链接表达式D- & ( O- or S+)，D-链靠左面，却链接了一个较远的单词the。因此，词串(2)不是上面的链语法定义的句子。
	现在，再来看一下这些链的具体含义：
	
link type	description	
D	链接determiner和noun	
S	链接subject-noun和finite verb	
O	链接transitive verb和direct或indirect object	

	除用链接子的表达式表示外，链接要求还可以用disjunct范式(disjunct form)来表示。用表达式描述链接要求对于建立自然语言语法很方便，但对于分析链语法和描述分析算法则显得很不方便。
	如果用disjunct范式来描述链接要求，每个单词后面的链接要求是由一系列disjunct组成。一个disjunct由两个有序表组成，左表(left list)和右表(right list)。左表由所有向左的链接子组成(即那些后缀是-的链接子)，右表由所有向右的链接子组成(即那些后缀是+的链接子)，这样，一个disjunct可以写成下面的形式：

			( (L1,L2,……,Lm) (Rn,Rn-1,……,R1) )
	这里，L1,L2,……,Lm是所有向左的链接子。Rn,Rn-1,……,R1是所有向右的链接子。左表和右表都可以为空，后缀+或-可以省略不写，因为已经隐含在disjunct中。
	要满足某个单词的链接要求，那么它所有disjunct中必须有一个disjunct被满足。一个disjunct被满足当且仅当它两个表中的所有链接子同时被满足。disjunct的两个表中的链接子是有序的，左表中L1,L2,……,Lm链接的单词距离当前单词越来越远，右表中Rn,Rn-1,……,R1链接的单词距离当前单词越来越近。
	链接表达式和disjunct范式互相转换很容易，例如，下面的链接表达式
(A-	or ()) & D- & (B+ or ()) & (O- or S+)
对应下面8个disjunct范式：

((A,D)	(S,B))	
((A,D,O)	(B))	
((A,D)	(S))	
((A,D,O)	())	
((D)	(S,B))	
((D,O)	(B))	
((D)	(S))	
((D,O)	())	
3.链语法的主要特点
(1)	链语法是词汇主义(lexicalism)的语法系统，对于任何一个单词，词典中都详尽地描述了这个单词在句子中如何使用。
(2)	所有词汇主义的语法系统所带来的优点：构造大型语法系统很容易，一个单词的描述只对包含这个单词的句子的分析产生影响。同时，允许我们逐步地建立一个大型语法系统(incrementally)。进而对于特殊的不规则的词语描述很方便，它们在词典中单独占据一个条目。实际经验告诉我们，语言中任何现象都可以分为典型的和非典型的，描述典型规律的规则很容易，而描述非典型的规则则要麻烦得多。
(3)	链语法用单词间得关系描述代替了成分描述。
(4)	一般认为，词汇主义得语法系统易于用来构造统计模型，单词间得关系描述也使我们收集词汇之间得统计信息变得容易。
(5)	D.Sleator等已经论证了链语法系统得生成能力等价于上下文无关语法。是否可以考虑把复杂特征集和合一运算加进去，限制其生成能力。
5.分析算法
D.Sleator和D.Temperley提出了一个基于动态规划(Dynamic programming)的分析算法或识别算法。(过程类似于optimal triangulation of convex polygon)算法以一种自顶向下的方式(top-down fashion)建立句子的链接集。自顶向下在这里的含义是，算法总是先建立较大的链，然后在这些链的范围内建立范围较小的链。
为了简单介绍一下这个算法，首先介绍存储disjunct范式的数据结构。一个disjunct d含有两个指针，一个指向左表，标记为left[d]，一个指向右表，标记为right[d]。假设c是一个链接子，那么next(c)用来指表中位于c后面的链接子。以d = ( (D,O) () )为例，left[d] = O, next(left[d]) = D, next(next(left[d])) = NIL, right[d] = NIL。我们再用0，1，……，N-1表示单词串中单词的序号，然后下面大致解释一下这个算法是如何工作的。
首先假定我们已经有一个部分结果(partial solution)，即假定算法在单词L的链接子l'和单词R的链接子r'之间已经画出了一条链。并且为了方便，令l = next(l')  r = next(r')，这时的分析结果可以表示成下图。

R

L

r

r'

l

l'

                                                                               

	这里L和R上面的方框表示单词L和R的数据结构，再往上的小一点的方框代表单词的disjunct，(可能不止一个)，由这些方框指向的更小的方框表示链接子。
	算法怎样处理这样一个部分结果，怎样把新链加入到区间(L,……,R)之内呢?首先假定区间之内根本没有单词，即R=L+1，这时如果l  NIL 并且r  NIL,那么这个部分结果肯定是错误的，因为链接子l和r最终无法满足。如果 l = NIL 并且 r = NIL ,那么这个区间已经处理完毕。
	现在假定，区间之内至少含有一个单词，那么为了把这个区间内的单词和句子中的其余部分连到一起，肯定至少存在一条链，或从L出发，或从R出发，链到区间内部的某个单词，因为这个区间内的单词不能直接链到区间以外，否则就违背了元规则平面性或顺序性等。并且因为l'和r'已经得到满足，加上满足必须遵循顺序性，现在剩下可用的链接子只有l和r了，而且它们也必须链到区间内的某个单词。
	假定目前l 不是 NIL，它一定要链接到区间内的某个单词。因为排它性，l不能链接到单词R，算法尝试所有可能找这样一个单词，假定找到了一个单词W,单词W的某个disjunct d中有一个链接子left[d]和l匹配。这时会得到得到下图的情形。

l

left[d]

r

l'

r'

right[d]

d

				

				

W

R

L

	怎么进一步把这个结果扩展为一个完全解呢？其实这个问题已经变成两个同上述问题类似的子问题。尤其是对于区间(L,…,W)。区间(W,…,R)的问题似乎和上面的问题不同，这个区间的两个边界词W和R并没有被直接链在一起。但实际上它们已经被间接地链在一起，因此，问题可以按照同样的方法处理。
	值得说明的是，在L和W之间存在一条链的同时，W和R之间也可能有链存在，链语法的分析结果可能是有环图(cyclic)。算法照顾到了这种情况。
	算法可以进一步形式化成下面的形式：
	令要分析的句子为S = W0W1…WN-1，再引入一个边界单词WN，并令这个边界单词(boundary word)只有一个disjunct范式: ( ( NIL ) ( NIL ) )，用D(W)表示单词W所有disjunct范式的集合。用c(L,R,l,r)表示在单词L和W之间用链接子l和r能够建立的子链接集(sublinkage)的数量。那么根据上面对算法的描述，可以得到下面的结论：即，若，l = r = NIL，则c(L,L+1,l,r) = 1，否则c(L,L+1,l,r) = 0。子区间L和R之间的子链接集数量可由下面的递归表达式算得。

若l和r 可以匹配match(l,r) = 1，否则match(l,r) = 0。是标准的delta函数，这样整个句子的链接集的数量是：

	算法的时间复杂度是O(D3N3)
	为了降低算法的时间复杂度，D.Sleator等设计了一些策略加快算法的执行，其中主要包括下面的技术：(1)剪枝(Pruning);(2)快速匹配数据结构(fast-match data structure);(3)强力剪枝(power pruning)，限于篇幅，这里不在祥述。作为进一步研究，95年，D.Grinsberg等开发了一个更为有效的算法，但可能带来一些局限性，感兴趣的人可以参阅有关文献，这里不再赘述。
6.特殊现象的处理
英语中似乎有些现象不宜用链语法描述，主要有下面几个方面的现象：
(1)	并列现象(Coordinating Conjunction)
下面看一看用链语法描述下面的英语句子会发生什么问题。
		 Danny and Dave wrote and debugged a program.
    按照前面所介绍的方法，将会有下面的链出现(仅为说明问题，这里没有画出和问题无关的链)。

S

S

S

S

S

  Danny   and   Davy   wrote   and   debugged   a   program

可以发现两条S链发生了交叉，这样的句子不是链语法的合法句子，而实际上，这个句子是符合英语语法的合法句子。英语中的并列连词除and之外，还有neither…nor…, either … or…, or, both … and…, not only … but…等等，因此这不是一个小问题。
有并列连词的句子的链接集可以表示如下图：

S

J

D

EV

O

O

  We   ate   popcorn   and   watched   movies   for   three   days.  

这样做，是一个解决办法，但会引起别的问题，限于问题这里不再赘述这个问题。
(2)	形式代词(Non-referential it)
    英语中可以说(1)，但不能说(2)和(3)中的句子。
1)	It seemed likely that John would go.
2)	*Joe seemed likely that John would go.
3)	*It acted likely that John would go.
    用链语法描述这种现象很困难，上述句子在链语法中都可能被认为是合法的句子。
(3)	选择性限制(Selectional restriction)
链语法中对动词和名词之间的选择性限制问题处理能力弱，例如，在英语中不能说：the black idea died. 当然这似乎更可以看作是语义问题。
针对(2)、(3)两个问题，D.Sleator提出了一个新概念-域(domain),并基于域设计了一套后处理(post-processing)机制，用后处理规则(post-processing rule)限制掉这些现象，有兴趣的人可以参看有关文献。
7.链接集向短语结构树的转换
链语法分析句子得到的链接集可以转换成短语结构树，尽管这很难说是否是链语法的一个优点。
词类(POS)、句法功能(syntactic functions)以及成分(constituents)从链接集中可以有规律的得到。我们举一个例子来说明怎样从链接集中得到一个名词短语。 (这里只为说明问题，下面的表述可能并不严格)。
仍以句子the cat chased a sanke.为例，链接集参看前文。当我们从S链开始向左追踪，或沿着O链的右端开始向左追踪，就可以得到两个名词短语"the cat"和"a snake"。
做一个程序去转换要复杂得多，但基本道理是相同，就是说，短语可以通过追踪特定得链类型而获得。
8.和范畴语法、依存语法的关系
(1)	依存语法
   大家可以感觉到，链语法和依存语法似乎很相似。依存语法中也有类似平面性的特点。这里可以大致回忆一下依存语法的基本要点。依存语法是法国著名语言学家Tesniere.L于1959年在其所著的《结构语法基础》中提出的。他主张将主要动词作为句子的中心，支配其他成分，而它本身不受其他成分的支配。此后，1970年，Robin J.J.提出了依存关系的四大公理，为依存语法奠定了基础。这四条公理是：
    ①一个句子中只有一个成分是独立的；
    ②其他成分直接依存于某一成分；
    ③任何一个成分都不能依存于两个或两个以上的成分；
    ④如果A成分直接依存于B成分，而C成分在句子中位于A和B之间，则C或者直接依存于A，或者直接依存于B，或者直接依存于A和B之间的某一成分。
依存语法描述的是句子中词与词之间直接的句法关系。这种句法关系是有方向的，通常是一个词支配另一个词。这种支配和被支配关系体现了句子中的词间句法关系。
上述四条公理也可以认为是依存语法的元规则。可以看出依存关系结构是一个有向的无环图，有一个词称为根词(root word)。而在链语法中，链没有方向，可以构成环，且没有根词的概念。
Gaifman是第一个形式化依存语法的人，他论证过依存语法是上下文无关的。可以根据依存语法生成一部链语法，二者所接受的语言是一样的。
(2)	范畴语法
就象链语法中词典中每个单词都标记有链接要求一样，范畴语法的词典中，每个单词后面都记录有各个词条的范畴表达式(categorial expression)。一个范畴表达式要么是一个原子符号(atomic symbol)要么是由二元操作符"/"或"\"组合起来的一对表达式。
在范畴语法中，有两个元操作，可以看作是范畴语法中的元规则。这两条元规则是：
1)     e        e\f
            f

2)    f/e         e
            f 
判定一个单词串是否范畴语法中所定义的语言中的合法句子，就是看使用这两条规则能否把一串词的范畴表达式归结成单一的符号S。
下面是一部含有4个单词的范畴语法。

words	categorial expression	
Harry	NP, S/(S\NP)	
likes	(S\NP)/NP	
peanuts	NP	
passionately	(S\NP)\(S\NP)	

通过下页最上方图示的过程可以判定"Harry likes peanuts passionately."是这部语法中合法的句子。
    同样也可以有规律地把范畴表达式转换成链接表达式。令d代表范畴表达式 ，单词w的所有范畴表达式为{d1,d2,……,dk}，那么与之等价的链接表达式E(d)可以通过下面的公式有规律的转换。

        E(w) = E(d1) or E(d2) or …… or E(dk)

     Harry       likes       peanuts       passionately
S/(S\NP)   (S\NP)/NP      NP         (S\NP)\(S\NP)
                 S\NP
                               S\NP
                S

   其中，
	E(.)可以递归定义如下：
        E(f/e)  =  f/e+  or  f/e- or (e+ & E(f))
        E(e\f)  =  e\f+  or  e\f- or (e- & E(f))
        E(A) 	=  A-  or   A+
增加一个边界词WALL，规定它的链接要求是S+
就可以得到一部链语法。上述句子用转换的链语法可以表示为：

S\NP

S\NP

NP

S

S

     WALL       Harry        likes        peanuts        passionately

9.统计模型
目前关于句法的统计模型，最为常见的是概率上下文无关语法，上下文无关语法中的参数为PA(ABC)和PA(Aw)。经验证明，这个模型并不有效，其捕捉上下文之间相互依赖关系的能力很弱。似乎，词汇主义的统计语言模型，更能有效地捕捉上下文依赖关系，这可以从人们看好LTAG得到证实。
链语法也是词汇主义的，根据它建立一个统计语言模型，怎么样呢。J.Lafferty提出按照下面的方式建立模型，用IO算法训练参数。

参考文献
[Grinberg 1995] D.Grinberg, J.Lafferty, D.Sleator, A robust parsing algorithm for link grammars, Carnegie Mellon University Computer Science technical report CMU-CS-95-125, and Proceedings of the Fourth International Workshop on Parsing Technologies, Prague, September, 1995. 
[Lafferty 1992] J. Lafferty, D.Sleator, D.Temperley, Grammatical Trigrams: A Probabilistic Model of Link Grammar, Proceedings of the AAAI Conference on Probabilistic Approaches to Natural Language, October, 1992. 
[Sleator 1991] D.Sleator, D.Temperley, Parsing English with a Link Grammar, Carnegie Mellon University Computer Science technical report CMU-CS-91-196, October 1991. 
[Sleator 1993] D. Sleator, D.Temperley, Parsing English with a Link Grammar, Third International Workshop on Parsing Technologies, August 1993. 
[黄 1998] 现代语言学给我们的启迪, 黄昌宁等, 世界汉语教学, 1998年第4期
[翁 1998]《计算语言学导论》, 翁富良等, 中国社会科学出版社, 1998, pp.55-56，pp.82-85