8.3 基于语言学句法的模型 247
8.3 基于语言学句法的模型
层次短语模型是一种典型的基于翻译文法的模型。它把翻译问题转化为语言分
析问题。在翻译一个句子的时候，模型会生成一个树形结构，这样也就得到了句子
结构的层次化表示。图8.14展示了一个使用层次短语模型进行翻译时所生成的翻译
推导 d，以及这个推导所对应的树形结构（源语言）。这棵树体现了机器翻译的视角
下的句子结构，尽管这个结构并不是人类语言学中的句法树。
S
X
决定
X
的
董事会
公司
S
X
执行
没有
S
X
他
S
X
但
r
2
r
2
r
2
r
1
r
3
r
4
r
5
r
6
r
7
层次短语翻译规则:
r
1
S → ⟨ X
1
, X
1
⟩
r
2
S → ⟨ S
1
X
2
, S
1
X
2
⟩
r
3
X → ⟨ 但, but ⟩
r
4
X → ⟨ 他, he ⟩
r
5
X → ⟨ 没有 执行,
r
5
did not implemente ⟩
r
6
X → ⟨ 公司 X
1
决定,
r
6
the decision X
1
the board of directors ⟩
r
7
X → ⟨ 董事会 的, of ⟩
d = r
3
◦r
1
◦r
4
◦r
2
◦r
5
◦r
2
◦r
7
◦r
6
◦r
2
图 8.14 层次短语模型所对应的翻译推导及树结构（源语言）
在翻译中使用树结构的好处在于，模型可以更加有效地对句子的层次结构进行
抽象。而且树结构可以作为对序列结构的一种补充，比如，在句子中距离较远的两
个单词，在树结构中可以很近。不过，传统的层次短语模型也存在一些不足：
• 层次短语规则没有语言学句法标记，很多规则并不符合语言学认知，因此译文
的生成和调序也无法保证遵循语言学规律。比如，层次短语系统经常会把完整
的句法结构打散，或者“破坏”句法成分进行组合；
• 层次短语系统中有大量的工程化约束条件。比如，规则的源语言部分不允许两
个变量连续出现，而且变量个数也不能超过两个。这些约束在一定程度上限制
了模型处理翻译问题的能力。
实际上，基于层次短语的方法可以被看作是介于基于短语的方法和基于语言学
句法的方法之间的一种折中。它的优点在于，短语模型简单且灵活，同时，由于同步
翻译文法可以对句子的层次结构进行表示，因此也能够处理一些较长距离的调序问
题。但是，层次短语模型并不是一种“精细”的句法模型，当翻译需要复杂的结构信
息时，这种模型可能会无能为力。
图8.15展示了一个翻译实例，对图中句子进行翻译需要通过复杂的调序才能生
成正确译文。为了完成这样的翻译，需要对多个结构（超过两个）进行调序，但是这
种情况在标准的层次短语系统中是不允许的。
248 Chapter 8. 基于句法的模型 肖桐 朱靖波
参考答案： The Xiyanghong star performance troupe presented a wonderful Peking opera as well as singing and dancing
Reference: performance to the national audience .
层次短语系统： Star troupe of Xiyanghong, highlights of Peking opera and dance show to the audience of the national .
句法系统： The XYH star troupe
presented
a wonderful Peking opera singing and dancing
to
the national audience
.
源语言句法树：
IP
.
VP
PP
NP
全国
13
观众
14
P
给
12
VP
VV
呈现
11
NP
一
5
台
6
精彩
7
的
8
京剧
9
歌舞
10
BA
将
4
NP
夕阳红
1
明星
2
艺术团
3
图 8.15 含有复杂调序的翻译实例（汉语翻译到英语）
从这个例子中可以发现，如果知道源语言的句法结构，翻译其实并不“难”。比
如，语言学句法结构可以告诉模型句子的主要成分是什么，而调序实际上是在这些
成分之间进行的。从这个角度说，语言学句法可以帮助模型进行更上层结构的表示
和调序。
S
VP
NP
NN
ball
DT
the
VBD
hit
NP
NNP
Messi
(a) 短语结构树
Messi
hit
the ball
(b) 依存树
图 8.16 短语结构树 vs 依存树
显然，使用语言学句法对机器翻译进行建模也是一种不错的选择。不过，语言
学句法有很多种，因此首先需要确定使用何种形式的句法。比如，在自然语言处理
中经常使用的是短语结构分析和依存分析（图8.16）。二者的区别已经在第二章进行
了讨论。
在机器翻译中，上述这两种句法信息都可以被使用。不过为了后续讨论的方便，
这里仅介绍基于短语结构树的机器翻译建模。使用短语结构树的原因在于，它提供
了较为丰富的句法信息，而且相关句法分析工具比较成熟。如果没有特殊说明，本
章中所提到的句法树都是指短语结构树（或成分句法树），有时也会把句法树简称为
8.3 基于语言学句法的模型 249
树。此外，这里也假设所有句法树都可以由句法分析器自动生成
7
。
8.3.1 基于句法的翻译模型分类
可以说基于句法的翻译模型贯穿了现代统计机器翻译的发展历程。从概念上讲，
不管是层次短语模型，还是语言学句法模型都是基于句法的模型。基于句法的机器
翻译模型种类繁多，这里先对相关概念进行简要介绍，以避免后续论述中产生歧义。
表8.2给出了基于句法的机器翻译中涉及的一些概念。
表 8.2 基于句法的机器翻译中常用概念
术语 说明
翻译规则 翻译的最小单元（或步骤）
推导 由一系列规则组成的分析或翻译过程，推导可以被看作是规
则的序列
规则表 翻译规则的存储表示形式，可以高效进行查询
层次短语模型 基于同步上下文无关文法的翻译模型，非终结符只有 S 和 X
两种，文法并不需要符合语言学句法约束
树到串模型 一类翻译模型，它使用源语语言学句法树，因此翻译可以被
看作是从句法树到词串的转换
串到树模型 一类翻译模型，它使用目标语语言学句法树，因此翻译可以
被看作是从词串到句法树的转换
树到树模型 一类翻译模型，它同时使用源语和目标语语言学句法树，因
此翻译可以被看作从句法树到句法树的转换
基于句法 使用语言学句法
基于树 （源语言）使用树结构（大多指句法树）
基于句法的翻译模型可以被分为两类：基于形式化文法的模型和语言学上基于
句法的模型（图8.17）。基于形式化文法的模型的典型代表包括，基于反向转录文法
的模型
[343]
和基于层次短语的模型
[338]
。而语言学上基于句法的模型包括，句法树到串
的模型
[86, 344]
、串到句法树的模型
[87, 345]
、句法树到句法树的模型
[346, 347]
等。
通常来说，基于形式化文法的模型并不需要句法分析技术的支持。这类模型只
是把翻译过程描述为一系列形式化文法规则的组合过程。而语言学上基于句法的模
型则需要源语言和（或者）目标语言句法分析的支持，以获取更丰富的语言学信息
来提高模型的翻译能力。这也是本节所关注的重点。当然，所谓分类也没有唯一的
标准，比如，还可以把句法模型分为基于软约束的模型和基于硬约束的模型，或者
分为基于树的模型和基于串的模型。
7
对于汉语、英语等大语种，句法分析器的选择有很多。不过，对于一些小语种，句法标注数据有限，
句法分析可能并不成熟，这时在机器翻译中使用语言学句法信息会面临较大的挑战。
250 Chapter 8. 基于句法的模型 肖桐 朱靖波
术语 说明
基于串 （源语言）使用词串，比如串到树翻译系统的解码器一般
都是基于串的解码方法
基于森林 （源语言）使用句法森林，这里森林只是对多个句法树的一
种压缩结构表示
单词化规则 含有终结符的规则
非单词规则 不含有终结符的规则
句法软约束 不强制规则推导匹配语言学句法树，通常把句法信息作为特
征使用
句法硬约束 要求推导必须符合语言学句法树，不符合的推导会被过滤掉
（广义上）
基于句法的模型
基于形式文法
的模型
基于语言学
句法的模型
反向转录
文法
层次短语
模型
串到树
模型
树到串
模型
树到树
模型
(Wu, 1995)
(Chiang, 2005)
(Galley et al.,
2004; 2006)
(Liu et al.,
2006)
(Eisner, 2003)
图 8.17 基于句法的机器翻译模型的分类
表 8.3 基于句法的机器翻译模型对比
模型 形式句法 语言学句法
树到串 串到树 树到树
源语句法 否 是 否 是
目标语句法 否 否 是 是
基于串的解码 是 否 是 是
基于树的解码 否 是 否 是
健壮性 高 中 中 低
8.3 基于语言学句法的模型 251
表8.3进一步对比了不同模型的区别。其中，树到串和树到树模型都使用了源语
言句法信息，串到树和树到树模型使用了目标语言句法信息。不过，这些模型都依
赖句法分析器的输出，因此会对句法分析的错误比较敏感。相比之下，基于形式文
法的模型并不依赖句法分析器，因此会更健壮一些。
8.3.2 基于树结构的文法
基于句法的翻译模型的一个核心问题是要对树结构进行建模，进而完成树之间
或者树和串之间的转换。在计算机领域中，所谓树就是由一些节点组成的层次关系
的集合。计算机领域的树和自然世界中的树没有任何关系，只是借用了相似的概念，
因为这种层次结构很像一棵倒过来的树。在使用树时，经常会把树的层次结构转化
为序列结构，称为树结构的序列化或者线性化（Linearization）。
S
VP
VP
AS
VV
AD
NN
[S
NN
VP[
AD
VP[
VV
AS]]]
(S NN VP(AD
VP(VV AS)))
(a) 树状表示
(b) 序列表示（缩进）
(c) 序列表示
图 8.18 树结构的不同表示形式
比如，使用树的先序遍历就可以得到一个树的序列表示。图8.18就对比了同一棵
树的不同表示方式。实际上，树的序列表示是非常适合计算机进行读取和处理的。因
此，本章也会使用树的序列化结果来表示句法结构。
在基于语言学句法的机器翻译中，两个句子间的转化仍然需要使用文法规则进
行描述。有两种类型的规则：
• 树到串翻译规则（Tree-to-String Translation Rule）：在树到串、串到树模型中使
用；
• 树到树翻译规则（Tree-to-Tree Translation Rule）：在树到树模型中使用。
树到串规则描述了一端是树结构而另一端是串的情况，因此树到串模型和串到
树模型都可以使用这种形式的规则。树到树模型需要在两种语言上同时使用句法树
结构，需要树到树翻译规则。
1. 树到树翻译规则
虽然树到串翻译规则和树到树翻译规则蕴含了不同类型的翻译知识，但是它们
都在描述一个结构（树/串）到另一个结构（树/串）的映射。这里采用了一种更加通
用的文法
——
基于树结构的文法
——
将树到串翻译规则和树到树翻译规则进行统
252 Chapter 8. 基于句法的模型 肖桐 朱靖波
一。定义如下：
定义 8.3.1 基于树结构的文法
一个基于树结构的文法由七部分构成 (N
s
,N
t
,T
s
,T
t
,I
s
,I
t
,R)，其中
1. N
s
和 N
t
是源语言和目标语言非终结符集合；
2. T
s
和 T
t
是源语言和目标语言终结符集合；
3. I
s
⊆ N
s
和 I
t
⊆ N
t
是源语言和目标语言起始非终结符集合；
4. R 是规则集合，每条规则 r ∈ R 有如下形式：
⟨ α
h
,β
h
⟩ → ⟨ α
r
,β
r
,∼ ⟩
其中，规则左部由非终结符 α
h
∈ N
s
和 β
h
∈ N
t
构成；规则右部由三部分组成，α
r
表示由源语言终结符和非终结符组成的树结构；
β
r
表示由目标语言终结符和非终
结符组成的树结构；∼ 表示 α
r
和 β
r
中叶子非终结符的 1-1 对应关系。
基于树结构的规则非常适合于描述树结构到树结构的映射。比如，图8.19是一个
汉语句法树结构到一个英语句法树结构的对应。其中的树结构可以被看作是完整句
法树上的一个片段，称为树片段（Tree Fragment）。
→
VP
VP
NN
VV
表示
PP
VP
VP
PP
VBN
VBZ
was
图 8.19 汉语句法树到英语句法树的结构对应
树片段的叶子节点既可以是终结符（单词）也可以是非终结符。当叶子节点为
非终结符时，表示这个非终结符会被进一步替换，因此它可以被看作是变量。而源
语言树结构和目标语言树结构中的变量是一一对应的，对应关系用虚线表示。
这个双语映射关系可以被表示为一个基于树结构的文法规则，套用规则的定义
⟨ α
h
,β
h
⟩ → ⟨ α
r
,β
r
,∼ ⟩ 形式，可以知道：
α
h
= VP
β
h
= VP
α
r
= VP(PP:x VP(VV(表示) NN:x))
β
r
= VP(VBZ(was) VP(VBN:x PP:x))
∼ = {1 −2,2 −1}
这里，α
h
和 β
h
表示规则的左部，对应树片段的根节点；α
r
和 β
r
是两种语言的树结
8.3 基于语言学句法的模型 253
构（序列化表示），其中标记为 x 的非终结符是变量。∼= {1 −2,2 −1} 表示源语言
的第一个变量对应目标语言的第二个变量，而源语言的第二个变量对应目标语言的
第一个变量，这也反应出两种语言句法结构中的调序现象。类似于层次短语规则，可
以把规则中变量的对应关系用下标进行表示。例如，上面的规则也可以被写为如下
形式：
⟨ VP,VP ⟩ → ⟨ PP
1
VP(VV(表示) NN
2
)), VP(VBZ(was) VP(VBN
2
PP
1
)) ⟩
其中，两种语言中变量的对应关系为 PP
1
↔ PP
1
，NN
2
↔ VBN
2
。
2. 基于树结构的翻译推导
规则中的变量预示着一种替换操作，即变量可以被其他树结构替换。实际上，上面
的树到树翻译规则就是一种同步树替换文法（Synchronous Tree-substitution Grammar）
规则。不论是源语言端还是目标语言端，都可以通过这种替换操作不断生成更大的
树结构，也就是通过树片段的组合得到更大的树片段。图8.20就展示了树替换操作的
一个实例。
VP
VP
NN
VV
表示
PP
NN
满意
⇒
VP
VP
NN
满意
VV
表示
PP
图 8.20 树替换操作（将 NN 替换为一个树结构）
这种方法也可以被扩展到双语的情况。图8.21给出了一个使用基于树结构的同
步文法生成双语句对的实例。其中，每条规则都同时对应源语言和目标语言的一个
树片段（用矩形表示）。变量部分可以被替换，这个过程不断执行。最后，四条规则
组合在一起形成了源语言和目标语言的句法树。这个过程也被称作规则的推导。
规则的推导对应了一种源语言和目标语言树结构的同步生成过程。比如，使用
254 Chapter 8. 基于句法的模型 肖桐 朱靖波
目标语言
NP
NNS
imports
DT
the
S
VP
NP
VP
ADVP
VBN
fallen
RB
VBZ
have
RB
drastically
源语言
NN
进口
IP
VP
NN
VP
ADVP
AS
了
VV
下降
AD
AD
大幅度
表示对变量的替换操作
NN
进口
NP
NNS
imports
DT
the
AD
大幅度
RB
drastically
VP
ADVP
AS
了
VV
下降
AD
VP
ADVP
VBN
fallen
RB
VBZ
have
IP
VP
NN
S
VP
NP
NN
进口
NP
NNS
imports
DT
the
AD
大幅度
RB
drastically
VP
ADVP
AS
了
VV
下降
AD
VP
ADVP
VBN
fallen
RB
VBZ
have
IP
VP
NN
S
VP
NP
图 8.21 使用基于树结构的同步文法生成汉英句对
下面的规则集：
r
3
: AD(大幅度) → RB(drastically)
r
4
: VV(减少) → VBN(fallen)
r
6
: AS(了) → VBP(have)
r
7
: NN(进口) → NP(DT(the) NNS(imports)
r
8
: VP(AD
1
VP(VV
2
AS
3
)) → VP(VBP
3
ADVP(RB
1
VBN
2
))
r
9
: IP(NN
1
VP
2
) → S(NP
1
VP
2
)
可以得到一个翻译推导：
⟨ IP
[1]
, S
[1]
⟩
IP
[1]
⇔S
[1]
−−−−−−−→
r
9
⟨ IP(NN
[2]
VP
[3]
), S(NP
[2]
VP
[3]
) ⟩
NN
[2]
⇔NP
[2]
−−−−−−−−→
r
7
⟨ IP(NN(进口) VP
[3]
), S(NP(DT(the) NNS(imports)) VP
[3]
) ⟩
VP
[3]
⇔VP
[3]
−−−−−−−−→
r
8
⟨ IP(NN(进口) VP(AD
[4]
VP(VV
[5]
AS
[6]
))),
S(NP(DT(the) NNS(imports)) VP(VBP
[6]
ADVP(RB
[4]
VBN
[5]
))) ⟩
AD
[4]
⇔RB
[4]
−−−−−−−−→
r
3
⟨ IP(NN(进口) VP(AD(大幅度) VP(VV
[5]
AS
[6]
))),
S(NP(DT(the) NNS(imports)) VP(VBP
[6]
ADVP(RB(drastically) VBN
[5]
))) ⟩
8.3 基于语言学句法的模型 255
VV
[5]
⇔VBN
[5]
−−−−−−−−−→
r
4
⟨ IP(NN(进口) VP(AD(大幅度) VP(VV(减少) AS
[6]
))),
S(NP(DT(the) NNS(imports)) VP(VBP
[6]
ADVP(RB(drastically) VBN(fallen)))) ⟩
AS
[6]
⇔VBP
[6]
−−−−−−−−−→
r
6
⟨ IP(NN(进口) VP(AD(大幅度) VP(VV(减少) AS(了)))),
S(NP(DT(the) NNS(imports)) VP(VBP(have)
ADVP(RB(drastically) VBN(fallen)))) ⟩
其中，箭头 → 表示推导之意。显然，可以把翻译看作是基于树结构的推导过程（记
为 d）。因此，与层次短语模型一样，基于语言学句法的机器翻译也是要找到最佳的
推导
ˆ
d = argmax
d
P (d)。
3. 树到串翻译规则
基于树结构的文法可以很好地表示两个树片段之间的对应关系，即树到树翻译
规则。那树到串翻译规则该如何表示呢？实际上，基于树结构的文法也同样适用于
树到串模型。比如，图8.22是一个树片段到串的映射，它可以被看作是树到串规则的
一种表示。
VP
NN
VV
提高
increases
NN
图 8.22 树片段到串的映射
在图8.22中，源语言树片段中的叶子结点 NN 表示变量，它与右手端的变量 NN
对应。这里仍然可以使用基于树结构的规则对上面这个树到串的映射进行表示。参
照规则形式 ⟨ α
h
,β
h
⟩ → ⟨ α
r
,β
r
,∼ ⟩，有：
α
h
= VP
β
h
= VP
α
r
= VP(VV(提高) NN:x)
β
r
= VP(increases NN:x)
∼ = {1 −1}
这里，源语言部分是一个树片段，因此 α
h
和 α
r
很容易确定。对于目标语部分，
可以把这个符号串当作是一个单层的树片段，根结点直接共享源语言树片段的根结
256 Chapter 8. 基于句法的模型 肖桐 朱靖波
点，叶子结点就是符号串本身。这样，也可以得到 β
h
和 β
r
。从某种意义上说，树到
串翻译仍然体现了一种双语的树结构，只是目标语部分不是语言学句法驱动的，而
是一种借用了源语言句法标记所形成的层次结构。
这里也可以把变量的对齐信息用下标表示。同时，由于 α
h
和 β
h
是一样的，可
以将左部两个相同的非终结符合并，于是规则可以被写作：
VP → ⟨ VP(VV(提高) NN
1
), increases NN
1
⟩
另外，在机器翻译领域，大家习惯把规则看作源语言结构（树/串）到目标语言
结构（树/串）的一种映射，因此常常会把上面的规则记为：
VP(VV(提高) NN
1
) → increases NN
1
在后面的内容中也会使用这种形式来表示基于句法的翻译规则。
8.3.3 树到串翻译规则抽取
基于句法的机器翻译包括两个步骤：文法归纳和解码。其中，文法归纳是指从
双语平行数据中自动学习翻译规则及规则所对应的特征；解码是指利用得到的文法
对新的句子进行分析，并获取概率最高的翻译推导。
本节首先介绍树到串文法归纳的经典方法——GHKM 方法
[87, 345]
。所谓
GHKM
是
四位作者名字的首字母。GHKM 方法的输入包括：
• 源语言句子及其句法树；
• 目标语言句子；
• 源语言句子和目标语言句子之间的词对齐。
它的输出是这个双语句对上的树到串翻译规则。GHKM 不是一套单一的算法，
它还包括很多技术手段用于增加规则的覆盖度和准确性。下面就具体看看 GHKM 是
如何工作的。
1. 树的切割与最小规则
获取树到串规则就是要找到源语言树片段与目标语言词串之间的对应关系。一
棵句法树会有很多个树片段，那么哪些树片段可以和目标语言词串产生对应关系呢？
在 GHKM 方法中，源语言树片段和目标语言词串的对应是由词对齐决定的。
GHKM 假设：一个合法的树到串翻译规则，不应该违反词对齐。这个假设和双语
短语抽取中的词对齐一致性约束是一样的（见第七章短语抽取小节）。简单来说，规
则中两种语言互相对应的部分不应包含对齐到外部的词对齐连接。
为了说明这个问题，来看一个例子。图8.23包含了一棵句法树、一个词串和它们
8.3 基于语言学句法的模型 257
之间的词对齐结果。图中包含如下规则：
PP(P(对) NP(NN(回答))) →with the answer
IP
VP
VP
NN
满意
VV
表示
PP
NP
NN
回答
P
对
NP
PN
他
he
was
satisfied with the
answer
正确的规则
错误的规则
因为 “satisfied” 会
对齐到规则外，
也就是这条规则
与词对齐不相容
图 8.23 树到串规则与词对齐兼容性示例
该规则是一条满足词对齐约束的规则（对应于图8.23中红色部分），因为不存在
从规则的源语言或目标语言部分对齐到规则外部的情况。但是，如下的规则却是一
条不合法的规则：
NN(满意) → satisfied
这是因为，“satisfied”除了对齐到“满意”，还对齐到“表示”。也就是，这条规
则会产生歧义，因为“satisfied”不应该只由“满意”生成。
为了能够获得与词对齐相兼容的规则，GHKM 引入了几个概念。首先，GHKM
方法中定义了可达范围（Span）和补充范围（Complement Span）：
定义 8.3.2 可达范围（Span）
对于一个源语言句法树节点，它的可达范围是这个节点所对应到的目标语言第一个
单词和最后一个单词所构成的索引范围。
定义 8.3.3 补充范围（Complement Span）
对于一个源语言句法树节点，它的补充范围是除了它的祖先和子孙节点外的其他节
点可达范围的并集。
可达范围定义了每个节点覆盖的源语言片段所对应的目标语言片段。实际上，它
表示了目标语言句子上的一个跨度，这个跨度代表了这个源语言句法树节点所能达
到的最大范围。因此可达范围实际上是一个目标语单词索引的范围。补充范围是与
可达范围相对应的一个概念，它定义了句法树中一个节点之外的部分对应到目标语
258 Chapter 8. 基于句法的模型 肖桐 朱靖波
的范围，但是这个范围并不必须是连续的。
有了可达范围和补充范围的定义之后，可以进一步定义：
定义 8.3.4 可信节点（Admissible Node）
对于源语言树节点 node ，如果它的可达范围和补充范围不相交，节点 node 就是一个
可信节点，否则是一个不可信节点。
可信节点表示这个树节点 node 和树中的其他部分（不包括 node 的祖先和孩子）
没有任何词对齐上的歧义。也就是说，这个节点可以完整地对应到目标语言句子的
一个连续范围，不会出现在这个范围中的词对应到其他节点的情况。如果节点不是
可信节点，则表示它会引起词对齐的歧义，因此不能作为树到串规则中源语言树片
段的根节点或者变量部分。图8.24给出了一个可信节点的实例。
IP
VP
VP
NN
满意
VV
表示
PP
NP
NN
回答
P
对
NP
PN
他
he
1
was
2
satisfied
3
with
4
the
5
answer
6
可达范围 ={3}
补充范围 ={1,3-6}
可达范围 ={3-6}
补充范围 ={1}
不可信
可信
可信
不可信
图 8.24 标注了可信节点信息的句法树
进一步，可以定义树到串模型中合法的树片段：
定义 8.3.5 合法的树片段
如果一个树片段的根节点是可信节点，同时它的叶子节点中的非终结符节点也是可
信节点，那么这个树片段就是不产生词对齐歧义的树片段，也被称为合法的树片段。
图8.25是一个基于可信节点得到的树到串规则：
VP(PP(P(对) NP(NN(回答))) VP
1
) → VP
1
with the answer
其中，蓝色部分表示可以抽取到的规则，显然它的根节点和叶子非终结符节点都是
可信节点。由于源语言树片段中包含一个变量（VP），因此需要对 VP 节点的可达范
围进行泛化（红色方框部分）。
至此，对于任何一个树片段都能够使用上述方法判断它是否合法。如果合法，就
可以抽取相应的树到串规则。但是，枚举句子中的所有树片段并不是一个很高效的
8.3 基于语言学句法的模型 259
IP
VP
NN
满意
VV
表示
PP
NP
NN
回答
P
对
NP
PN
他
he
1
was
2
with
4
the
5
answer
6
可信
不可信
VP
VP
变量
变量
图 8.25 根据可信结点得到的树到串翻译规则
方法，因为对于任何一个节点，以它为根的树片段数量随着其深度和宽度的增加呈
指数增长。在 GHKM 方法中，为了避免低效的枚举操作，可以使用另一种方法抽取
规则。
实际上，可信节点确定了哪些地方可以作为规则的边界（合法树片段的根节点
或者叶子节点），可以把所有的可信节点看作是一个边缘集合（Frontier Set）。所谓边
缘集合就是定义了哪些地方可以被“切割”，通过这种切割可以得到一个个合法的树
片段，这些树片段无法再被切割为更小的合法树片段。图8.26给出了一个通过边缘集
合定义的树切割。图右侧中的矩形框表示切割得到的树片段。
可信
不可信
IP
VP
VP
NN
满意
VV
表示
PP
NP
NN
回答
P
对
NP
PN
他
he
was
satisfied
with the
answer
（a）标有可信节点信息的句法树
NP
PN
他
P
对
NP
NN
回答
VP
NN
满意
VV
表示
PP
NP
P
VP
VP
PP
IP
VP
NP
he
was
satisfied with the
answer
（b）通过边缘集合定义切割得到的句法树
图 8.26 根据边缘节点定义的树切割
260 Chapter 8. 基于句法的模型 肖桐 朱靖波
需要注意的是，因为“NP→PN→ 他”对应着一个单目生成的过程，所以这里
“NP(PN(他))”被看作是一个最小的树片段。当然，也可以把它当作两个树片段“NP(
PN)”和“PN(他)”，不过这种单目产生式往往会导致解码时推导数量的膨胀。因此，
这里约定把连续的单目生成看作是一个生成过程，它对应一个树片段，而不是多个。
将树进行切割之后，可以得到若干树片段，每个树片段都可以对应一个树到串
规则。由于这些树片段不能被进一步切割，因此这样得到的规则也被称作最小规则
（Minimal Rules）。它们构成了树到串模型中最基本的翻译单元。图8.27展示了基于
树切割得到的最小规则。其中左侧的每条规则都对应着右侧相同编号的树片段。
r
1
NP(PN(他)) → he
r
2
P(对) → with
r
3
NP(NN(回答)) → the answer
r
4
VP(VV(表示) NN(满意) →
satisfied
r
5
PP(P
1
NP
2
) →
P
1
NP
2
r
6
VP(PP
1
VP
2
) →
VP
2
PP
1
r
7
IP(NP
1
VP
2
) →
NP
1
VP
2
NP
PN
他
P
对
NP
NN
回答
VP
NN
满意
VV
表示
PP
NP
P
VP
VP
PP
IP
VP
NP
he
was
satisfied with the
answer
1 2
3
4
5
6
7
图 8.27 基于树切割得到的最小规则实例
2. 空对齐处理
空对齐是翻译中的常见现象。比如，一些虚词经常找不到在另一种语言中的对
应，因此不会被翻译，这种情况也被称作空对齐。在图8.27中目标语中的“was”就
是一个空对齐单词。空对齐的使用可以大大增加翻译的灵活度。具体到树到串规则
抽取任务，需要把空对齐考虑进来，这样能够覆盖更多的语言现象。
处理空对齐单词的手段非常简单。只需要把空对齐单词附着在它周围的规则上
即可。也就是，检查每条最小规则，如果空对齐单词能够作为规则的一部分进行扩
展，就可以生成一条新的规则。
图8.28展示了前面例子中“was”被附着在周围的规则上的结果。其中，含有红
色“was”的规则是通过附着空对齐单词得到的新规则。比如，对于规则：
NP(PN(他)) → he
“was”紧挨着这个规则目标端的单词“he”，因此可以把“was”包含在规则的
8.3 基于语言学句法的模型 261
r
1
NP(PN(他)) → he
r
4
VP(VV(表示) NN(满意) →
satisfied
r
6
VP(PP
1
VP
2
) → VP
2
PP
1
r
7
IP(NP
1
VP
2
) → NP
1
VP
2
r
8
NP(PN(他)) → he was
r
9
VP(VV(表示) NN(满意)) →
was satisfied
r
10
VP(PP
1
VP
2
) →
was VP
2
PP
1
r
11
IP(NP
1
VP
2
) →
NP
1
was VP
2
NP
PN
他
P
对
NP
NN
回答
VP
NN
满意
VV
表示
PP
NP
P
VP
VP
PP
IP
VP
NP
he
was
satisfied with the
answer
1 4
6
7
图 8.28 树到串规则抽取中空对齐单词的处理（绿色矩形）
目标端，形成新的规则：
NP(PN(他)) → he was
通常，在规则抽取中考虑空对齐可以大大增加规则的覆盖度。
3. 组合规则
最小规则是基于句法的翻译模型中最小的翻译单元。但是，在翻译复杂句子的
时候，往往需要更大范围的上下文信息，比如，本节开始图8.15中的例子，需要一条
规则同时处理多个变量的调序，而这种规则很可能不是最小规则。为了得到“更大”
的规则，一种方法是对最小规则进行组合。得到的规则称为 composed-m 规则，其中
m 表示这个规则是由 m 条最小规则组合而成。
规则的组合非常简单。只需要在得到最小规则之后，对相邻的规则进行拼装。也
就是说，如果某个树片段的根节点出现在另一个树片段的叶子节点处，就可以把它
们组合成更大的树片段。图8.29给了规则组合的实例。其中，规则 1、5、6、7 可以
组合成一条 composed-4 规则，这个规则可以进行非常复杂的调序。
在真实系统开发中，组合规则一般会带来明显的性能提升。不过随着组合规则
数量的增加，规则集也会膨胀。因此往往需要在翻译性能和文法大小之间找到一种
平衡。
4. SPMT 规则
组合规则固然有效，但并不是所有组合规则都非常好用。比如，在机器翻译中
已经发现，如果一个规则含有连续词串（短语），这种规则往往会比较可靠。但是由
262 Chapter 8. 基于句法的模型 肖桐 朱靖波
r
1
NP(PN(他)) → he
r
5
PP(P
1
NP
2
) → P
1
NP
2
r
6
VP(PP
1
VP
2
) → VP
2
PP
1
r
7
IP(NP
1
VP
2
) → NP
1
VP
2
r
1,7
IP(NP(PN(他)) VP
1
) →
he VP
1
r
1,6,7
IP(NP(PN(他)) VP(PP
1
VP
2
))
→ he VP
2
PP
1
r
1,5,6,7
IP(NP(PN(他))
VP(P
1
NP
2
VP
3
))
→ he VP
3
P
1
NP
2
NP
PN
他
P
对
NP
NN
回答
VP
NN
满意
VV
表示
PP
NP
P
VP
VP
PP
IP
VP
NP
he
was
satisfied with the
answer
1
5
6
7
图 8.29 对最小规则进行组合（绿色矩形）
于句法树结构复杂，获取这样的规则可能会需要很多次规则的组合，规则抽取的效
率很低。
NP
PN
他
P
对
NP
NN
形式
VP
NN
担心
VV
表示
VP
VP
NP
P
IP
VP
NP
he
was
worried about the situation
2
3
5
图 8.30 短语（红色）所对应的树片段（绿色）
针对这个问题，一种解决办法是直接从词串出发进行规则抽取。这种方法被称
为 SPMT 方法
[348]
。它的思想是：对于任意一个与词对齐兼容的短语，可以找到包含
它的“最小”翻译规则，即 SPMT 规则。如图8.30所示，可以得到短语翻译：
对 形式 → about the situation
然后，从这个短语出发向上搜索，找到覆盖这个短语的最小树片段，之后生成
8.3 基于语言学句法的模型 263
规则即可。在这个例子中可以得到 SPMT 规则：
VP(P(对) NP(NN(形式)) VP
1
) → VP
1
about the situation
而这条规则需要组合三条最小规则才能得到，但是在 SPMT 中可以直接得到。相
比规则组合的方法，SPMT 方法可以更有效地抽取包含短语的规则。
5.
句法树二叉化
句法树是使用人类语言学知识归纳出来的一种解释句子结构的工具。比如，
CTB
[349]
、
PTB
[350]
等语料就是常用的训练句法分析器的数据。
但是，这些数据的标注中会含有大量的扁平结构，如图8.31所示，多个分句可能
会导致一个根节点下有很多个分支。这种扁平的结构会给规则抽取带来麻烦。
IP
.V
VP
,
VP
,
VP
,
VP
NP
图 8.31 CTB 中含有多个分句的句法树结构
图8.32给出了一个实例，其中的名词短语（NP），包含四个词，都在同一层树结
构中。由于“乔治 华盛顿”并不是一个独立的句法结构，因此无法抽取类似于下面
这样的规则：
NP(NN(乔治)) NN(华盛顿)) →Washington
NP
NN
华盛顿
NN
乔治
NN
总统
NNP
美国
U.S.
President
Washington
抽取到的规则：
NP(NNP
1
NN
2
NN(乔治) NN(华盛顿))
→ NNP
1
NN
2
Trump
NP(NNP
1
NN(总统) NN(乔治) NN(华盛顿))
→ NNP
1
President Trump
不能抽取到的规则：
NP(NN(乔治) NN(华盛顿)) → Washington
图 8.32 一个扁平的句法结构所对应的规则抽取结果
对于这个问题，一种解决办法是把句法树变得更深，使局部的翻译片段更容易
被抽取出来。常用的手段是树二叉化（Binarization）。比如，图8.33就是一个树二叉
化的实例。二叉化生成了一些新的节点（记为 X-BAR），其中“乔治 华盛顿”被作
为一个独立的结构体现出来。这样，就能够抽取到规则：
264 Chapter 8. 基于句法的模型 肖桐 朱靖波
NP-BAR(NN(乔治)) NN(华盛顿)) →Washington
NP-BAR(NN
1
NP-BAR
2
) → NN
1
NP-BAR
2
由于树二叉化可以帮助规则抽取得到更细颗粒度的规则，提高规则抽取的召回
率，因此成为了基于句法的机器翻译中的常用方法。二叉化方法也有很多不同的实
现策略
[351, 352, 353]
，比如：左二叉化、右二叉化、基于中心词的二叉化等。具体实现时
可以根据实际情况进行选择。
NP
NN
华盛顿
NN
乔治
NN
总统
NNP
美国
U.S.
President
Washington
二叉化
NP
NP-BAR
NP-BAR
NN
华盛顿
NN
乔治
NN
总统
NNP
美国
U.S.
President
Washington
图 8.33 句法树二叉化结果
8.3.4 树到树翻译规则抽取
树到串/串到树模型只在一个语言端使用句法树，而树到树模型可以同时利用源
语言和目标语言句法信息，因此可以更细致地刻画两种语言结构的对应关系，进而
更好地完成句法结构的调序和生成。树到树翻译中，需要两端都有树结构的规则，比
如：
⟨ VP,VP ⟩ → ⟨ VP(PP
1
VP(VV(表示) NN
2
)),
VP(VBZ(was) VP(VBN
2
PP
1
)) ⟩
也可以把它写为如下形式：
VP(PP
1
VP(VV(表示) NN
2
)) → VP(VBZ(was) VP(VBN
2
PP
1
))
其中，规则的左部是源语言句法树结构，右部是目标语言句法树结构，变量的下标
表示对应关系。为了获取这样的规则，需要进行树到树规则抽取。最直接的办法是
把 GHKM 方法推广到树到树翻译的情况。比如，可以利用双语结构的约束和词对齐，
定义树的切割点，之后找到两种语言树结构的映射关系
[354]
。
8.3 基于语言学句法的模型 265
1. 基于节点对齐的规则抽取
不过，GHKM 方法的问题在于过于依赖词对齐结果。在树到树翻译中，真正需
要的是树结构（节点）之间的对应关系，而不是词对齐。特别是在两端都加入句法树
结构约束的情况下，词对齐的错误可能会导致较为严重的规则抽取错误。图8.34就给
出了一个实例，其中，中文的“了”被错误的对齐到了英文的“the”，导致很多高质
量的规则无法被抽取出来。
S
VP
ADVP
VBN
fallen
RB
drastically
VBZ
have
NP
NNS
imports
DT
the
IP
VP
VP
AS
了
VV
下降
AD
大幅度
NN
进口
抽取得到的规则
r
1
AS(了) → DT(the)
r
2
NN(进口) → NNS(imports)
r
3
AD(大幅度) → RB(drastically)
r
4
VV(下降) → VBN(fallen)
r
6
IP(NN
1
VP(AD
2
VP(VV
3
AS
4
)) →
S(NP(DT
4
NNS
1
) VP(VBZ(have) ADVP(RB
2
VBN
3
))
无法得到的规则
r
?
AS(了) → VBZ(have)
r
?
NN(进口) →NP(DT(the) NNS(imports))
r
?
IP(NN
1
VP
2
) → S(NP
1
VP
2
)
图 8.34 基于词对齐的树到树规则抽取
S
VP
ADVP
VBN
fallen
RB
drastically
VBZ
have
NP
NNS
imports
DT
the
IP
VP
VP
AS
了
VV
下降
AD
大幅度
NN
进口
抽取得到的规则 (子树对齐)
r
1
AS(了) → DT(the)
r
2
NN(进口) → NNS(imports)
r
3
AD(大幅度) → RB(drastically)
r
4
VV(下降) → VBN(fallen)
r
5
IP(NN
1
VP(AD
2
VP(VV
3
AS
4
)) →
S(NP(DT
4
NNS
1
) VP(VBZ(have) ADVP(RB
2
VBN
3
))
r
6
AS(了) → VBZ(have)
r
7
NN(进口) →
r
?
NP(DT(the) NNS(imports))
r
8
VP(AD
1
VP(VV
2
AS
3
)) →
r
?
VP(VBZ
3
ADVP(RB
1
VBN
2
)
r
9
IP(NN
1
VP
2
) → S(NP
1
VP
2
)
图 8.35 基于节点对齐的树到树规则抽取
换一个角度来看，词对齐实际上只是帮助模型找到两种语言句法树中节点的对
应关系。如果能够直接得到句法树节点的对应，就可以避免掉词对齐的错误。也就
是，可以直接使用节点对齐来进行树到树规则的抽取。首先，利用外部的节点对齐
工具获得两棵句法树节点之间的对齐关系。之后，将每个对齐的节点看作是树片段
的根节点，再进行规则抽取。图8.35展示了基于节点对齐的规则抽取结果。
可以看到，节点对齐可以避免词对齐错误造成的影响。不过，节点对齐需要开发
266 Chapter 8. 基于句法的模型 肖桐 朱靖波
额外的工具，有很多方法可以参考，比如可以基于启发性规则
[355]
、基于分类模型
[356]
、
基于无指导的方法
[250]
等。
2. 基于对齐矩阵的规则抽取
同词对齐一样，节点对齐也会存在错误，这样就不可避免地造成规则抽取的错
误。既然单一的对齐中含有错误，那能否让系统看到更多样的对齐结果，进而提高正
确规则被抽取到的几率呢？答案是肯定的。实际上，在基于短语的模型中就有基于
多个词对齐（如 n-best 词对齐）进行规则抽取的方法
[357]
，这种方法可以在一定程度
上提高短语的召回率。在树到树规则抽取中也可以使用多个节点对齐结果进行规则
抽取。但是，简单使用多个对齐结果会使系统运行代价线性增长，而且即使是 n-best
对齐，也无法保证涵盖到正确的对齐结果。对于这个问题，另一种思路是使用对齐
矩阵进行规则的“软”抽取。
VP
[1]
ADVP
[3]
VBN
[5]
fallen
RB
[4]
drastically
VBZ
[2]
have
VP
[1]
VP
[3]
AS
[5]
了
VV
[4]
减少
AD
[2]
大幅度
VP
[1]
VBZ
[2]
ADVP
[3]
RB
[4]
VBN
[5]
VP
[1]
AD
[2]
VP
[3]
VV
[4]
AS
[5]
1
1
1
1
= 确定的对齐
Matrix 1: 1-best 对齐
VP
[1]
VBZ
[2]
ADVP
[3]
RB
[4]
VBN
[5]
VP
[1]
AD
[2]
VP
[3]
VV
[4]
AS
[5]
0.9
0.1
0.1
0.6
0.6
0.1
0.1
0.1
0.8
0.2
0.4
0.3
0.7
= 概率化对齐
Matrix 2: 对齐概率
(a) 节点对齐矩阵（1-best vs Matrix）
最小规则
Matrix 1 (基于 1-best 对齐)
r
3
AD(大幅度) → RB(drastically)
r
4
VV(减少) → VBN(fallen)
r
6
AS(了) → VBZ(have)
r
8
VP(AD
1
VP(VV
2
AS
3
)) →
VP(VBZ
3
ADVP(RB
1
VBN
2
)
最小规则
Matrix 2 (基于对齐概率)
r
3
AD(大幅度) → RB(drastically)
r
4
VV(减少) → VBN(fallen)
r
6
AS(了) → VBZ(have)
r
8
VP(AD
1
VP(VV
2
AS
3
)) →
VP(VBZ
3
ADVP(RB
1
VBN
2
)
r
10
VP(VV(减少) AS(了)) → VBN(fallen)
r
11
VP(AD
1
VP
2
) → VP(VBZ
1
ADVP
2
)
...
(b) 抽取得到的树到树翻译规则
图 8.36 使用 1-best 节点对齐和概率化节点对齐矩阵的树到树规则抽取
[250]
所谓对齐矩阵，是描述两个句法树节点之间对应强度的数据结构。矩阵的每个
单元中都是一个 0 到 1 之间的数字。规则抽取时，可以认为所有节点之间都存在对
齐，这样可以抽取出很多 n-best 对齐中无法覆盖的规则。图8.36展示了一个用对齐矩
8.3 基于语言学句法的模型 267
阵的进行规则抽取的实例。其中矩阵 1（Matrix 1）表示的是标准的 1-best 节点对齐，
矩阵 2（Matrix 2）表示的是一种概率化的对齐矩阵。可以看到使用矩阵 2 可以抽取
到更多样的规则。另外，值得注意的是，基于对齐矩阵的方法也同样适用于短语和
层次短语规则的抽取。关于对齐矩阵的生成可以参考相关论文的内容
[250, 356, 357, 358]
。
此外，在基于句法的规则抽取中，一般会对规则进行一些限制，以避免规则数
量过大，系统无法处理。比如，可以限制树片段的深度、变量个数、规则组合的次数
等等。这些限制往往需要根据具体任务进行设计和调整。
8.3.5 句法翻译模型的特征
基于语言学句法的翻译模型使用判别模型对翻译推导进行建模（第七章数学建
模小节）。给定双语句对 (s,t)，由 M 个特征经过线性加权，得到每个翻译推导 d 的
得分，记为 score(d,t,s) =
P
M
i=1
λ
i
·h
i
(d,t,s ) ，其中 λ
i
表示特征权重，h
i
(d,t,s ) 表示
特征函数。翻译的目标就是要找到使 score(d,t,s) 达到最高的推导 d。
这里，可以使用最小错误率训练对特征权重进行调优（第七章最小错误率训练
小节）。而特征函数可参考如下定义：
基于短语的特征（对应于每条规则 r : ⟨ α
h
,β
h
⟩ → ⟨ α
r
,β
r
,∼ ⟩ ）
• (h
1
−
2
) 短语翻译概率（取对数），即规则源语言和目标语言树覆盖的序列翻译
概率。令函数 τ(·) 返回一个树片段的叶子节点序列。对于规则：
VP(PP
1
VP(VV(表示) NN
2
)) → VP(VBZ(was) VP(VBN
2
PP
1
))
可以得到：
τ(α
r
) = PP 表示 NN
τ(β
r
) = was VBN PP
于是，可以定义短语翻译概率特征为 log(P(τ(α
r
)|τ(β
r
))) 和 log(P(τ(β
r
)|τ(α
r
)))。
它们的计算方法与基于短语的系统是完全一样的
9
；
• (h
3−4
) 单词化翻译概率（取对数），即 log(P
lex
(τ(α
r
)|τ(β
r
))) 和 log(P
lex
(τ(β
r
)|τ(α
r
)))。
这两个特征的计算方法与基于短语的系统也是一样的。
基于句法的特征（对应于每条规则 r : ⟨ α
h
,β
h
⟩ → ⟨ α
r
,β
r
,∼ ⟩ ）
• (h
5
) 基于根节点句法标签的规则生成概率（取对数），即 log(P(r|root(r)))。这
里，root(r) 是规则所对应的双语根节点 (α
h
,β
h
)；
• (h
6
) 基于源语言端的规则生成概率（取对数），即 log(P(r|α
r
)))，给定源语言端
9
对于树到串规则，τ(β
r
) 就是规则目标语言端的符号串。
268 Chapter 8. 基于句法的模型 肖桐 朱靖波
生成整个规则的概率；
• (h
7
) 基于目标语言端的规则生成概率（取对数），即 log(P(r|β
r
)))，给定目标语
言端生成整个规则的概率。
其他特征（对应于整个推导 d）
• (h
8
) 语言模型得分（取对数），即 log(P
lm
(t))，用于度量译文的流畅度；
• (h
9
) 译文长度，即 | t| ，用于避免模型过于倾向生成短译文（因为短译文语言模
型分数高）；
• (h
10
) 翻译规则数量，学习对使用规则数量的偏好。比如，如果这个特征的权重
较高，则表明系统更喜欢使用数量多的规则；
• (h
11
) 组合规则的数量，学习对组合规则的偏好；
• (h
12
) 单词化规则的数量，学习对含有终结符规则的偏好；
• (h
13
) 低频规则的数量，学习对训练数据中出现频次低于 3 的规则的偏好。低频
规则大多不可靠，设计这个特征的目的也是为了区分不同质量的规则。
8.3.6 基于超图的推导空间表示
在完成建模后，剩下的问题是：如何组织这些翻译推导，高效地完成模型所需
的计算？本质上，基于句法的机器翻译与句法分析是一样的，因此关于翻译推导的
组织可以借用句法分析中的一些概念。
在句法分析中，上下文无关文法（CFG）的分析过程可以被组织成一个叫有向超
图（Directed Hyper-graph）的结构，或者简称为超图
[359]
：
定义 8.3.6 有向超图
一个有向超图 G 包含一个节点集合 N 和一个有向超边（Hyper-edge）集合 E。每个
有向超边包含一个头（Head）和一个尾（Tail），头指向 N 中的一个节点，尾是若干个 N
中的节点所构成的集合。
与传统的有向图不同，超图中的每一个边（超边）的尾可以包含多个节点。也就
是说，每个超边从若干个节点出发最后指向同一个节点。这种定义完美契合了 CFG
的要求。比如，如果把节点看作是一个推导所对应树结构的根节点（含有句法标记），
那么每个超边就可以表示一条 CFG 规则。
图8.37就展示了一个简单的超图。其中每个节点都有一个句法标记，句法标记下
面记录了这个节点的跨度。超边 edge1 和 edge2 分别对应了两条 CFG 规则：
8.3 基于语言学句法的模型 269
VP → VV NP
NP → NN NP
VP
[0,2]
NP
[0,2]
VV
[0,1]
NN
[1,2]
NP
[1,2]
edge1
edge2
图 8.37 超图实例
对于规则“VP →VV NP”，超边的头指向 VP，超边的尾表示规则右部的两个变
量 VV 和 NP。规则“NP → NN NP”也可以进行类似的解释。
不难发现，超图提供了一种非常紧凑的数据结构来表示多个推导，因为不同推导
之间可以共享节点。如果把图8.37中的蓝色和红色部分看作是两个推导，那么它们就
共享了同一个节点 NN[1,2]，其中 NN 是句法标记，[1,2] 是跨度。能够想象，简单枚
举一个句子所有的推导几乎是不可能的，但是用超图的方式却可以很有效地对指数
级数量的推导进行表示。另一方面，超图上的运算常常被看作是一种基于半环的代
数系统，而且人们发现许多句法分析和机器翻译问题本质上都是
半环分析
（
Semi-ring
Parsing）。不过，由于篇幅有限，这里不会对半环等结构展开讨论。感兴趣的读者可
以查阅相关文献
[360, 361]
。
从句法分析的角度看，超图最大程度地复用了局部的分析结果，使得分析可以
“结构化”。比如，有两个推导：
d
1
= r
1
◦r
2
◦r
3
◦r
4
(8.9)
d
2
= r
1
◦r
2
◦r
3
◦r
5
(8.10)
其中，r
1
−r
5
分别表示不同的规则。r
1
◦r
2
◦r
3
是两个推导的公共部分。在超图表示
中，r
1
◦r
2
◦r
3
可以对应一个子图，显然这个子图也是一个推导，记为 d
′
= r
1
◦r
2
◦r
3
。
这样，d
1
和 d
2
不需要重复记录 r
1
◦r
2
◦r
3
，重新写作：
d
1
= d
′
◦r
4
(8.11)
d
1
= d
′
◦r
5
(8.12)
270 Chapter 8. 基于句法的模型 肖桐 朱靖波
引入 d
′
的意义在于，整个分析过程具有了递归性。从超图上看，d
′
可以对应以
一个（或几个）节点为“根”的子图，因此只需要在这个（或这些）子图上增加新的
超边就可以得到更大的推导。这个过程不断执行，最终完成对整个句子的分析。
在句法分析中，超图的结构往往被组织为一种表格（Chart）结构。表格的每个
单元代表了一个跨度，因此可以把所有覆盖这个跨度的推导都放入相应的表格单元
（Chart Cell）。对于上下文无关文法，表格里的每一项还会增加一个句法标记，用来
区分不同句法功能的推导。
cell[1,2] cell[0,2]
cell[0,1]
N/A
VV[0,1]
NN[1,2]
NP[1,2]
VP[0,2]
NP[0,2]
跨度大小
起
始
位
置
Chart（表格）
图 8.38 句法分析 Chart（表格）结构实例
如图8.38所示，覆盖相同跨度的节点会被放入同一个表格单元，但是不同句法标
记的节点会被看作是不同的项（Item）。这种组织方式建立了一个索引，通过索引可
以很容易地访问同一个跨度下的所有推导。比如，如果采用自下而上的分析，可以
从小跨度的表格单元开始，构建推导，并填写表格单元。这个过程中，可以访问之前
的表格单元来获得所需的局部推导（类似于前面提到的 d
′
）。该过程重复执行，直到
处理完最大跨度的表格单元。而最后一个表格单元就保存了完整推导的根节点。通
过回溯的方式，能够把所有推导都生成出来。
基于句法的机器翻译仍然可以使用超图进行翻译推导的表示。和句法分析一样，
超图的每条边可以对应一个基于树结构的文法，超边的头代表文法的左部，超边的
尾代表规则中变量所对应的超图中的节点
10
。图8.39 给出了一个使用超图来表示机
器翻译推导的实例。可以看到，超图的结构是按源语言组织的，但是每个规则（超
边）会包含目标语言的信息。由于同步翻译文法可以确保规则的源语言端和目标语
言端都覆盖连续的词串，因此超图中的每个节点都对应一个源语言跨度，同时对应
一个目标语的连续译文。这样，每个节点实际上代表了一个局部的翻译结果。
不过，机器翻译与句法分析也有不同之处。最主要的区别在于机器翻译使用了
语言模型作为一个特征，比如 n-gram 语言模型。因为语言模型并不是上下文无关的，
因此机器翻译中计算最优推导的方法和句法分析会有不同。常用的方法是，直接在
每个表格单元中融合语言模型的分数，保留前 k 个结果；或者，在构建超图时不计算
语言模型得分，等到构建完整个超图之后对最好的若干个推导用语言模型重新排序；
10
也可以把每个终结符看作是一个节点，这样一个超边的尾就对应规则的树片段中所有的叶子。
8.3 基于语言学句法的模型 271
X | 0,4 | the answer | a question X | 0,4 | a question | the answer
X | 0,2 | the answer | NA X | 3,4 | a question | NA
根结点
对
0
回答
1
with the answer
有
2
have
疑问
3
a question
NP → ⟨ NP(NN(回答)), 回答⟩ NP → ⟨ NP(疑问), 疑问⟩
NP → ⟨ VP(NP
1
VP(VV(有) NN
2
)),
have NP
1
NN
2
⟩
NP → ⟨ VP(NP
1
VP(VV(有) NN
2
)),
NP
1
possess NN
2
⟩
NP → ⟨ VP(NP
1
VP(VV(有) NN
2
)),
NP
1
exist NN
2
⟩
NP → ⟨ VP(NP
1
VP(VV(有) NN
2
)),
there is NP
1
NN
2
⟩
S → ⟨ NP
1
, NP
1
⟩ S → ⟨ NN
2
, NN
2
⟩
图 8.39 机器翻译推导的超图表示
再或者，将译文和语言模型都转化为加权有限状态自动机，之后直接对两个自动机
做组合（Composition）得到新的自动机，最后得到融合语言模型得分的译文表示。
基于超图的推导表示方法有着很广泛的应用。比如，8.2节介绍的层次短语系统
也可以使用超图进行建模，因为它也使用了同步文法。从这个角度说，基于层次短
语的模型和基于语言学句法的模型本质上是一样的。它们的主要区别在于规则中的
句法标记和抽取规则的方法不同。
8.3.7 基于树的解码 vs 基于串的解码
解码的目标是找到得分 score(d) 最高的推导 d。这个过程通常被描述为：
ˆ
d = argmax
d
score(d,s,t ) (8.13)
这也是一种标准的基于串的解码（String-based Decoding），即通过句法模型对输
入的源语言句子进行翻译得到译文串。不过，搜索所有的推导会导致巨大的解码空
间。对于树到串和树到树翻译来说，源语言句法树是可见的，因此可以使用另一种
解码方法
——
基于树的解码（Tree-based Decoding），即把输入的源语句法树翻译为
目标语串。
表8.4对比了基于串和基于树的解码方法。可以看到，基于树的解码只考虑了与
源语言句法树兼容的推导，因此搜索空间更小，解码速度会更快。
这里需要注意的是，不论是基于串的解码还是基于树的解码都是使用句法模型
272 Chapter 8. 基于句法的模型 肖桐 朱靖波
表 8.4 基于串的解码 vs 基于树的解码
对比 基于树的解码 基于串的解码
解码方法
ˆ
d = argmax
d∈D
tree
score(d)
ˆ
d = argmax
d∈D
score(d)
搜索空间 与输入的源语句法树兼容的推导 D
tree
所有的推导 D
适用模型 树到串、树到树 所有的基于句法的模型
解码算法 Chart 解码 CKY + 规则二叉化
速度 快 一般较慢
的方法，在翻译过程中都会生成翻译推导和树结构。二者的本质区别在于，基于树
的解码把句法树作为显式输入，而基于串的解码把句法树看作是翻译过程中的隐含
变量。图8.40进一步解释了这个观点。
隐含结构
IP
VP
VP
吃 鱼
VV
喜欢
NP
NN
猫
Cats like eating fish
(a) 基于树的解码
显式输入的结构
猫 喜欢 吃 鱼
Cats like eating fish
(b) 基于串的解码
IP
VP
VP
VV
NP
NN
图 8.40 句法树在不同解码方法中的角色
1. 基于树的解码
基于树和基于串的解码都可以使用前面的超图结构进行推导的表示。基于树的
解码方法相对简单。直接使用表格结构组织解码空间即可。这里采用自底向上的策
略，具体步骤如下：
• 从源语言句法树的叶子节点开始，自下而上访问输入句法树的节点；
• 对于每个树节点，匹配相应的规则；
• 从树的根节点可以得到翻译推导，最终生成最优推导所对应的译文。
这个过程如图8.41所示，可以看到，不同的表格单元对应不同跨度，每个表格单
元会保存相应的句法标记（还有译文的信息）。
这里的问题在于规则匹配。对于每个树节点，需要知道以它为根可以匹配的规
则有哪些。比较直接的解决方法是遍历这个节点下一定深度的句法树片段，用每个
树片段在文法中找出相应的匹配规则，如图8.42所示。不过这种匹配是一种严格匹
8.3 基于语言学句法的模型 273
猫
喜欢
吃
鱼
l=1 l=2 l=3 l=4
Chart
猫
喜欢
吃
鱼
0
1
2
3 4
源语言句子
序号
跨度 标记
源语句子片段
1
2
3
4
5
6
7
8
9
10
[0,1]
[1,2]
[2,3]
[3,4]
[0,2]
[1,3]
[2,4]
[0,3]
[1,4]
[0,4]
NN & NP
VV
VV
NN & NP
N/A
N/A
VP
N/A
VP
IP (root)
猫
喜欢
吃
鱼
猫喜欢
喜欢吃
吃鱼
猫喜欢吃
喜欢吃鱼
猫喜欢吃鱼
图 8.41 基于树的解码中 Chart 的内容
配，因为它要求句法树片段内的所有内容都要与规则的源语言部分严格对应。有时，
句法结构中的细微差别都会导致规则匹配不成功。因此，也可以考虑采用模糊匹配
的方式提高规则的命中率，进而增加可以生成推导的数量
[362]
。
IP
VP
VP
NN
满意
13
VV
感到
12
PP
NP
自己
3
四
4
个
5
多
6
月
7
以来
8
的
9
教学
10
改革
11
P
对
2
NP
NR
校长
1
VP(PP(P(对) NP
1
) VP
2
)
→ VP
2
with NP
1
树到串翻译规则
.. .
.
.
.
.
.
.
.
.
.
Chart
树片段的匹配
图 8.42 基于树的规则匹配
2. 基于串的解码
基于串的解码过程和句法分析几乎一样。对于输入的源语言句子，基于串的解
码需要找到这个句子上的最优推导。唯一不同的地方在于，机器翻译需要考虑译文
的生成（语言模型的引入会使问题稍微复杂一些），但是源语言部分的处理和句法分
析是一样的。因为不要求用户输入句法树，所以这种方法同时适用于树到串、串到
树、树到树等多种模型。本质上，基于串的解码可以探索更多潜在的树结构，并增大
搜索空间（相比基于树的解码），因此该方法更有可能找到高质量翻译结果。
基于串的解码仍然可以用表格结构来组织翻译推导。不过，一个比较有挑战的
274 Chapter 8. 基于句法的模型 肖桐 朱靖波
问题是如何找到每个规则能够匹配的源语言跨度。也就是，对于每个表格单元，需
要知道哪些规则可以被填入其中。因为，没有用户输入的句法树做指导，理论上输
入句子的所有子串要与所有规则进行匹配。匹配时，需要考虑规则中源语言端的符
号串（或者树结构的叶子序列）与输入词串匹配的全部可能性。
校长
1
对
2
自己
3
四
4
个
5
多
6
月
7
以来
8
的
9
教学
10
改革
11
感到
12
满意
13
校长
1
对
2
自己
3
四
4
个
5
多
6
月
7
以来
8
的
9
教学
10
改革
11
感到
12
满意
13
校长
1
对
2
自己
3
四
4
个
5
多
6
月
7
以来
8
的
9
教学
10
改革
11
感到
12
满意
13
...
校长
1
对
2
自己
3
四
4
个
5
多
6
月
7
以来
8
的
9
教学
10
改革
11
感到
12
满意
13
在跨度 [0,13] 上匹配 “NP 对 NP VP”
NP（第二个）
VP
图 8.43 在一个词串上匹配“NP 对 NP VP”。连续变量的匹配对应了对词串不同位置的切割。
图8.43展示了规则匹配输入句子（包含 13 个词）的所有可能。可以看到，规则
源语言端的连续变量会使得匹配情况变得复杂。对于长度为 n 的词串，匹配含有 m
个连续变量的规则的时间复杂度是 O(n
m−1
)。显然当变量个数增加时规则匹配是相
当耗时的操作，甚至当变量个数过多时解码无法在可接受的时间内完成。
对于这个问题，有两种常用的解决办法：
• 对文法进行限制。比如，可以限制规则中变量的数量；或者不允许连续的变量，
这样的规则也被称作满足单词化标准形式（Lexicalized Norm Form）（LNF）的
规则。比如，层次短语规则就是 LNF 规则。由于 LNF 中单词（终结符）可以
作为锚点，因此规则匹配时所有变量的匹配范围是固定的；
• 对规则进行二叉化，使用 CKY 方法进行分析。这个方法也是句法分析中常用
的策略。所谓规则二叉化是把规则转化为最多只含两个变量或连续词串的规则
（串到树规则）。比如，对于如下的规则：
喜欢 VP
1
NP
2
→ VP(VBZ(likes) VP
1
NP
2
)
二叉化的结果为：
喜欢 V103 → VP(VBZ(likes) V103)
VP
1
NP
2
→ V103( VP
1
NP
2
)
可以看到，这两条新的规则中源语言端只有两个部分，代表两个分叉。V103 是
8.3 基于语言学句法的模型 275
一个新的标签，它没有任何句法含义。不过，为了保证二叉化后规则目标语部
分的连续性，需要考虑源语言和目标语二叉化的同步性
[351, 352]
。这样的规则与
CKY 方法一起使用完成解码，具体内容可以参考8.2.4节的内容。
总的来说，基于句法的解码器较为复杂，无论是算法的设计还是工程技巧的运
用，对开发者的能力都有一定要求。因此开发一个优秀的基于句法的机器翻译系统
是一项有挑战的工作。
