232 Chapter 8. 基于句法的模型 肖桐 朱靖波
8.2 基于层次短语的模型
在机器翻译中，如果翻译需要局部上下文的信息，把短语作为翻译单元是一种
理想的方案。但是，单词之间的关系并不总是“局部”的，很多时候需要距离更远一
些的搭配。比较典型的例子是含有从句的情况。比如：
我 在 今天 早上 没有 吃 早 饭 的 情况 下 还是 正常 去 上班 了。
这句话的主语“我”和谓语“去 上班”构成了主谓搭配，而二者之间的部分是
状语。显然，用短语去捕捉这个搭配需要覆盖很长的词串，也就是整个“我 ... 去上
班”的部分。如果把这样的短语考虑到建模中，会面临非常严重的数据稀疏问题，因
为无法保证这么长的词串在训练数据中能够出现。
表 8.1 不同短语在训练数据中出现的频次
短语（中文） 训练数据中出现的频次
包含 3341
包含 多个 213
包含 多个 词 12
包含 多个 词 的 8
包含 多个 词 的 短语 0
包含 多个 词 的 短语 太多 0
实际上，随着短语长度变长，短语在数据中会变得越来越低频，相关的统计特
征也会越来越不可靠。表8.1就展示了不同长度的短语在一个训练数据中出现的频次。
可以看到，长度超过 3 的短语已经非常低频了，更长的短语甚至在训练数据中一次
也没有出现过。
显然，利用过长的短语来处理长距离的依赖并不是一种十分有效的方法。过于
低频的长短语无法提供可靠的信息，而且使用长短语会导致模型体积急剧增加。
再来看一个翻译实例，图8.4是一个基于短语的机器翻译系统的翻译结果。这个
例子中的调序有一些复杂，比如，“众多/高校/之一”和“与/东软/有/合作”的英文
翻译都需要进行调序，分别是“one of the many universities”和“have collaborative
relations with Neusoft”。基于短语的系统可以很好地处理这些调序问题，因为它们仅
仅使用了局部的信息。但是，系统却无法在这两个短语（1 和 2）之间进行正确的调
序。
这个例子也在一定程度上说明了长距离的调序需要额外的机制才能得到更好的
处理。实际上，两个短语（1 和 2）之间的调序现象本身对应了一种结构，或者说模
板。也就是汉语中的：
与 [什么 东西] 有 [什么 事]
8.2 基于层次短语的模型 233
1
2
源语言句子: 东北大学 是 与 东软 有 合作 的 众多 高校 之一
系统输出:
NEU is collaborative relations with Neusoft
is one of the many universities
参考译文:
NEU is one of the many universities that have
collaborative relations with Neusoft
图 8.4 基于短语的机器翻译实例
可以翻译成：
have [什么 事] with [什么 东西]
这里 [什么 东西] 和 [什么 事] 表示模板中的变量，可以被其他词序列替换。通
常，可以把这个模板形式化描述为：
⟨ 与 X
1
有 X
2
, have X
2
with X
1
⟩
其中，逗号分隔了源语言和目标语言部分，X
1
和 X
2
表示模板中需要替换的内容，或
者说变量。源语言中的变量和目标语言中的变量是一一对应的，比如，源语言中的
X
1
和目标语言中的 X
1
代表这两个变量可以“同时”被替换。假设给定短语对：
⟨ 东软 , Neusoft ⟩
⟨ 合作 , collaborative relations ⟩
可以使用第一个短语替换模板中的变量 X
1
，得到：
⟨ 与 [东软] 有 X
2
, have X
2
with [Neusoft] ⟩
其中，[·] 表示被替换的部分。可以看到，在源语言和目标语言中，X
1
被同时替换为
相应的短语。进一步，可以用第二个短语替换
X
2
，得到：
⟨ 与 东软 有 [合作] , have [collaborative relations] with Neusoft ⟩
至此，就得到了一个完整词串的译文。类似的，还可以写出其他的翻译模板，如
234 Chapter 8. 基于句法的模型 肖桐 朱靖波
下：
⟨ X
1
是 X
2
, X
1
is X
2
⟩
⟨ X
1
之一, one of X
1
⟩
⟨ X
1
的 X
2
, X
2
that have X
1
⟩
使用上面这种变量替换的方式，就可以得到一个完整句子的翻译。
与
X
1
有
X
2
have
X
2
with
X
1
东软
Neusoft
合作
collaborative relations
X
1
的
X
2
X
2
that
X
1
众多高校
the many universities
X
1
之一
one of
X
1
X
1
是
X
2
X
1
is
X
2
东北大学
NEU
图 8.5 使用短语和翻译模板进行双语句子的同步生成
这个过程如图8.5所示。其中，左右相连接的方框表示翻译模版的源语言和目标
语言部分。可以看到，模版中两种语言中的变量会被同步替换，替换的内容可以是
其他模版生成的结果。这也就对应了一种层次结构，或者说互译的句对可以被双语
的层次结构同步生成出来。
实际上，在翻译中使用这样的模版就构成了层次短语模型的基本思想。下面就
一起看看如何对翻译模版进行建模，以及如何自动学习并使用这些模版。
8.2.1 同步上下文无关文法
基于层次短语的模型（Hierarchical Phrase-based Model）是一个经典的统计机器翻
译模型
[88, 338]
。这个模型可以很好地解决短语系统对翻译中长距离调序建模不足的问
题。基于层次短语的系统也在多项机器翻译比赛中取得了很好的成绩。这项工作也
获得了自然语言处理领域顶级会议 ACL2015 的最佳论文奖。
层次短语模型的核心是把翻译问题归结为两种语言词串的同步生成问题。实际
上，词串的生成问题是自然语言处理中的经典问题，早期的研究更多的是关注单语
句子的生成，比如，如何使用句法树描述一个句子的生成过程。层次短语模型的创
8.2 基于层次短语的模型 235
新之处是把传统单语词串的生成推广到双语词串的同步生成上。这使得机器翻译可
以使用类似句法分析的方法进行求解。
1. 文法定义
层次短语模型中一个重要的概念是同步上下文无关文法（Synchronous Context-free
Grammar，SCFG）。SCFG 可以被看作是对源语言和目标语言上下文无关文法的融合，
它要求源语言和目标语言的产生式及产生式中的变量具有对应关系。具体定义如下：
定义 8.2.1 同步上下文无关文法
一个同步上下文无关文法由五部分构成 (N, T
s
,T
t
,I,R)，其中：
1. N 是非终结符集合。
2. T
s
和 T
t
分别是源语言和目标语言的终结符集合。
3. I ⊆ N 是起始非终结符集合。
4. R 是规则集合，每条规则 r ∈R 有如下形式：
LHS →< α,β, ∼>
其中，LHS ∈ N 表示规则的左部，它是一个非终结符；规则的右部由三部分组成，α ∈
(N
S
T
s
)
∗
表示由源语言终结符和非终结符组成的串；β ∈ (N
S
T
t
)
∗
表示由目标语言终结
符和非终结符组成的串；∼ 表示 α 和 β 中非终结符的 1-1 对应关系。
根据这个定义，源语言和目标语言有不同的终结符集合（单词），但是它们会共
享同一个非终结符集合（变量）。每个产生式包括源语言和目标语言两个部分，分别
表示由规则左部生成的源语言和目标语言符号串。由于产生式会同时生成两种语言
的符号串，因此这是一种“同步”生成，可以很好地描述翻译中两个词串之间的对应。
下面是一个简单的
SCFG
实例：
S → ⟨ NP
1
希望 VP
2
, NP
1
wish to VP
2
⟩
VP → ⟨ 对 NP
1
感到 VP
2
, be VP
2
wish NP
1
⟩
NN → ⟨ 强大, strong ⟩
这里的 S、NP、VP 等符号可以被看作是具有句法功能的标记，因此这个文法和
传统句法分析中的 CFG 很像，只是 CFG 是单语文法，而 SCFG 是双语同步文法。非
终结符的下标表示对应关系，比如，源语言的 NP
1
和目标语言的 NP
1
是对应的。因
此，在上面这种表示形式中，两种语言间非终结符的对应关系 ∼ 是隐含在变量下标
中的。当然，复杂的句法功能标记并不是必须的。比如，也可以使用更简单的文法形
236 Chapter 8. 基于句法的模型 肖桐 朱靖波
式：
X → ⟨ X
1
希望 X
2
, X
1
wish to X
2
⟩
X → ⟨ 对 X
1
感到 X
2
, be X
2
wish X
1
⟩
X → ⟨ 强大, strong ⟩
这个文法只有一种非终结符 X，因此所有的变量都可以使用任意的产生式进行
推导。这就给翻译提供了更大的自由度，也就是说，规则可以被任意使用，进行自
由组合。这也符合基于短语的模型中对短语进行灵活拼接的思想。基于此，层次短
语系统中也使用这种并不依赖语言学句法标记的文法。在本章的内容中，如果没有
特殊说明，把这种没有语言学句法标记的文法称作基于层次短语的文法（Hierarchical
Phrase-based Grammar），或简称层次短语文法。
2. 推导
下面是一个完整的层次短语文法：
r
1
: X → ⟨ 进口 X
1
, The imports X
1
⟩
r
2
: X → ⟨ X
1
下降 X
2
, X
2
X
1
fallen ⟩
r
3
: X → ⟨ 大幅度, drastically ⟩
r
4
: X → ⟨ 了, have ⟩
其中，规则 r
1
和 r
2
是含有变量的规则，这些变量可以被其他规则的右部替换；规则
r
2
是调序规则；规则 r
3
和 r
4
是纯单词化规则，表示单词或者短语的翻译。
对于一个双语句对：
源语言： 进口 大幅度 下降 了
目标语言： The imports have drastically fallen
可以进行如下的推导（假设起始符号是 X）：
⟨ X
1
,X
1
⟩
r
1
−→ ⟨ 进口 X
2
, The imports X
2
⟩
r
2
−→ ⟨ 进口 X
3
下降 X
4
, The imports X
4
X
3
fallen ⟩
r
3
−→ ⟨ 进口 大幅度 下降 X
4
,
The imports X
4
drastically fallen ⟩
r
4
−→ ⟨ 进口 大幅度 下降 了,
The imports have drastically fallen ⟩
8.2 基于层次短语的模型 237
其中，每使用一次规则就会同步替换源语言和目标语言符号串中的一个非终结符，替
换结果用红色表示。通常，可以把上面这个过程称作翻译推导，记为：
d = r
1
◦r
2
◦r
3
◦r
4
(8.1)
在层次短语模型中，每个翻译推导都唯一地对应一个目标语译文。因此，可以
用推导的概率 P (d) 描述翻译的好坏。同基于短语的模型是一样的（见第七章数学建
模小节），层次短语翻译的目标是：求概率最高的翻译推导
ˆ
d = argmax P (d)。值得
注意的是，基于推导的方法在句法分析中也十分常用。层次短语翻译实质上也是通
过生成翻译规则的推导来对问题的表示空间进行建模。在8.3 节还将看到，这种方法
可以被扩展到语言学上基于句法的翻译模型中。而且这些模型都可以用一种被称作
超图的结构来进行建模。从某种意义上讲，基于规则推导的方法将句法分析和机器
翻译进行了形式上的统一。因此机器翻译也借用了很多句法分析的思想。
3. 胶水规则
由于翻译现象非常复杂，在实际系统中往往需要把两个局部翻译线性拼接到一
起。在层次短语模型中，这个问题通过引入胶水规则（Glue Rule）来处理，形式如下：
S → ⟨ S
1
X
2
, S
1
X
2
⟩
S → ⟨ X
1
, X
1
⟩
胶水规则引入了一个新的非终结符 S，S 只能和 X 进行顺序拼接，或者 S 由 X
生成。如果把 S 看作文法的起始符，使用胶水规则后，相当于把句子划分为若干个
部分，每个部分都被归纳为 X。之后，顺序地把这些 X 拼接到一起，得到最终的译
文。比如，最极端的情况，整个句子会生成一个 X，之后再归纳为 S，这时并不需要
进行胶水规则的顺序拼接；另一种极端的情况，每个单词都是独立地被翻译，被归
纳为 X，之后先把最左边的 X 归纳为 S，再依次把剩下的 X 依次拼到一起。这样的
推导形式如下：
S → ⟨ S
1
X
2
, S
1
X
2
⟩
→ ⟨ S
3
X
4
X
2
, S
3
X
4
X
2
⟩
→ ...
→ ⟨ X
n
... X
4
X
2
, X
n
... X
4
X
2
⟩
实际上，胶水规则在很大程度上模拟了基于短语的系统中对字符串顺序翻译的
操作，而且在实践中发现，这个步骤是十分必要的。特别是对法英翻译这样的任务，
由于语言的结构基本上是顺序翻译的，因此引入顺序拼接的操作符合翻译的整体规
律。同时，这种拼接给翻译增加了灵活性，系统会更加健壮。
238 Chapter 8. 基于句法的模型 肖桐 朱靖波
需要说明的是，使用同步文法进行翻译时，由于单词的顺序是内嵌在翻译规则
内的，因此这种模型并不依赖额外的调序模型。一旦文法确定下来，系统就可以进
行翻译。
4. 处理流程
训练用双语数据
文法（规则）抽取
同步翻译文法
特征值学习
翻译模型
特征权重调优
调优用双语数据
解码新句子
目标语数据
n-gram 语言建模
语言模型
图 8.6 层次短语系统的处理流程
层次短语系统的流程如图8.6所示。其核心是从双语数据中学习同步翻译文法，
并进行翻译特征的学习，形成翻译模型（即规则 + 特征）。同时，要从目标语言数据
中学习语言模型。最终，把翻译模型和语言模型一起送入解码器，在特征权重调优
后，完成对新输入句子的翻译。
8.2.2 层次短语规则抽取
层次短语系统所使用的文法包括两部分：
• 不含变量的层次短语规则（短语翻译）；
• 含有变量的层次短语规则。短语翻译的抽取直接复用基于短语的系统即可。
此处重点讨论如何抽取含有变量的层次短语规则。在第七章短语抽取一节已经
介绍了短语与词对齐相兼容的概念。这里，所有层次短语规则也是与词对齐相兼容
（一致）的。
定义 8.2.2 与词对齐相兼容的层次短语规则
对于句对 (s, t) 和它们之间的词对齐 a，令 Φ 表示在句对 (s,t) 上与 a 相兼容的双语
短语集合。则：
1. 如果 (x,y) ∈ Φ，则 X → ⟨x,y,Φ⟩ 是与词对齐相兼容的层次短语规则。
2. 对于 (x, y) ∈ Φ，存在 m 个双语短语 (x
i
,y
j
) ∈ Φ，同时存在 (1,...,m) 上面的一个排
8.2 基于层次短语的模型 239
序 ∼ = {π
1
,...,π
m
}，且：
x = α
0
x
1
...α
m−1
x
m
α
m
(8.2)
y = β
0
y
π
1
...β
m−1
y
π
m
β
m
(8.3)
其中，{α
0
,...,α
m
} 和 {β
0
,...,β
m
} 表示源语言和目标语言的若干个词串（包含空
串）。则 X → ⟨x, y,∼⟩ 是与词对齐相兼容的层次短语规则。这条规则包含 m 个变
量，变量的对齐信息是 ∼ 。
这个定义中，所有规则都是由双语短语生成。如果规则中含有变量，则变量部
分也需要满足与词对齐相兼容的定义。按上述定义实现层次短语规则抽取也很简单。
只需要对短语抽取系统进行改造：对于一个短语，可以通过挖“槽”的方式生成含有
变量的规则。每个“槽”就代表一个变量。
The
weather
is
very
good
today
.
EOS
今天
天气
真
好
。
EOS
抽取得到的短语:
抽取得到的层次短语规则:
天气 真好 – The weather is very good
X
1
真好 – X
1
is very good
图 8.7 通过双语短语抽取层次短语规则
图8.7展示了一个通过双语短语抽取层次短语的示意图。可以看到，在获取一个
“大”短语的基础上（红色），直接在其内部抽取得到另一个“小”短语（绿色），这
样就生成了一个层次短语规则。
这种方式可以抽取出大量的层次短语规则。但是，不加限制的抽取会带来规则
集合的过度膨胀，对解码系统造成很大负担。比如，如果考虑任意长度的短语会使
得层次短语规则过大，一方面这些规则很难在测试数据上被匹配，另一方面抽取这
样的“长”规则会使得抽取算法变慢，而且规则数量猛增之后难以存储。还有，如果
一个层次短语规则中含有过多的变量，也会导致解码算法变得更加复杂，不利于系
统实现和调试。针对这些问题，在标准的层次短语系统中会考虑一些限制
[338]
，包括：
• 抽取的规则最多可以跨越 10 个词；
• 规则的（源语言端）变量个数不能超过 2；
• 规则的（源语言端）变量不能连续出现。
在具体实现时还会考虑其他的限制，比如，限定规则的源语言端终结符数量的
上限等。
240 Chapter 8. 基于句法的模型 肖桐 朱靖波
8.2.3 翻译特征
在层次短语模型中，每个翻译推导都有一个模型得分 score(d, t,s)。score(d,t,s)
是若干特征的线性加权之和：score(d,t,s) =
P
M
i=1
λ
i
·h
i
(d,t,s ) ，其中 λ
i
是特征权重，
h
i
(d,t,s ) 是特征函数。层次短语模型的特征包括与规则相关的特征和语言模型特征，
如下：
对于每一条翻译规则 LHS→ ⟨α,β,∼⟩，有：
• (h
1−2
) 短语翻译概率（取对数），即 log(P (α | β)) 和 log(P (β |α)) ，特征的计算
与基于短语的模型完全一样；
• (h
3−4
) 单词化翻译概率（取对数），即 log(P
lex
(α | β)) 和 log(P
lex
(β | α))，特征
的计算与基于短语的模型完全一样；
• (h
5
) 翻译规则数量，让模型自动学习对规则数量的偏好，同时避免使用过少规
则造成分数偏高的现象；
• (h
6
) 胶水规则数量，让模型自动学习使用胶水规则的偏好；
• (h
7
) 短语规则数量，让模型自动学习使用纯短语规则的偏好。
这些特征可以被具体描述为：
h
i
(d,t,s ) =
X
r∈d
h
i
(r) (8.4)
公式(8.4)中，r 表示推导 d 中的一条规则，h
i
(r) 表示规则 r 上的第 i 个特征。可
以看出，推导 d 的特征值就是所有包含在 d 中规则的特征值的和。进一步，可以定义
rscore(d,t,s ) =
7
X
i=1
λ
i
·h
i
(d,t,s ) (8.5)
最终，模型得分被定义为：
score(d,t,s ) = rscore(d,t,s) + λ
8
log(P
lm
(t)) + λ
9
| t | (8.6)
其中：
• log(P
lm
(t)) 表示语言模型得分；
• | t | 表示译文的长度。
在定义特征函数之后，特征权重 {λ
i
} 可以通过最小错误率训练在开发集上进行
调优。关于最小错误率训练方法可以参考第七章的相关内容。
8.2 基于层次短语的模型 241
8.2.4 CKY 解码
层次短语模型解码的目标是找到模型得分最高的推导，即：
ˆ
d = argmax
d
score(d,t,s ) (8.7)
这里，
ˆ
d 的目标语部分即最佳译文
ˆ
t。令函数 t(· ) 返回翻译推导的目标语词串，于是
有：
ˆ
t = t(
ˆ
d) (8.8)
由于层次短语规则本质上就是 CFG 规则，因此公式(8.7)代表了一个典型的句法
分析过程。需要做的是，用模型源语言端的 CFG 对输入句子进行分析，同时用模型
目标语言端的 CFG 生成译文。基于 CFG 的句法分析是自然语言处理中的经典问题。
一种广泛使用的方法是：首先把 CFG 转化为 ε-free 的乔姆斯基范式（Chomsky Normal
Form）
5
，之后采用 CKY 方法进行分析。
CKY 是形式语言中一种常用的句法分析方法
[339, 340, 341]
。它主要用于分析符合乔
姆斯基范式的句子。由于乔姆斯基范式中每个规则最多包含两叉（或者说两个变量），
因此 CKY 方法也可以被看作是基于二叉规则的一种分析方法。对于一个待分析的字
符串，CKY 方法从小的“范围”开始，不断扩大分析的“范围”，最终完成对整个字
符串的分析。在 CKY 方法中，一个重要的概念是跨度（Span），所谓跨度表示了一
个符号串的范围。这里可以把跨度简单地理解为从一个起始位置到一个结束位置中
间的部分。
猫
喜欢
吃
鱼
0
1
2
3 4
图 8.8 一个单词串及位置索引
比如，如图8.8 所示，每个单词左右都有一个数字来表示序号。可以用序号的范
围来表示跨度，例如：
span[0,1] = “猫”
span[2,4] = “吃 鱼”
span[0,4] = “猫 喜欢 吃 鱼”
5
能够证明任意的 CFG 都可以被转换为乔姆斯基范式，即文法只包含形如 A→BC 或 A→a 的规则。
这里，假设文法中不包含空串产生式 A→ ε，其中 ε 表示空字符串。
242 Chapter 8. 基于句法的模型 肖桐 朱靖波
CKY 方法是按跨度由小到大的次序执行的，这也对应了一种自下而上的分析
（Bottom-Up Parsing）过程。对于每个跨度，检查：
• 是否有形如 A→a 的规则可以匹配；
• 是否有形如 A→BC 的规则可以匹配。
对于第一种情况，简单匹配字符串即可；对于第二种情况，需要把当前的跨度
进一步分割为两部分，并检查左半部分是否已经被归纳为 B，右半部分是否已经被
归纳为 C。如果可以匹配，会在这个跨度上保存匹配结果。后面，可以访问这个结果
（也就是 A）来生成更大跨度上的分析结果。
Function CKY-Algorithm(s,G)
for j = 0 to J −1
span[j,j + 1].Add(A → a ∈ G)
for l = 1 to J
// 跨度长度
for j = 0 to J −l
// 跨度起始位置
for k = j to j + l
// 跨度结束位置
hypos = Compose(span[j,k], span[k,j + l])
span[j,j + l].Update(hypos)
return span[0,J]
参数：s 为输入字符串。G 为输入 CFG。J 为待分析字符串长度。
输出：全部可能的字符串语法分析结果
输入：符合乔姆斯基范式的待分析字符串和一个上下文无关文法（CFG）
图 8.9 CKY 算法
CKY 算法的伪代码如图8.9所示。整个算法的执行顺序是按跨度的长度（l）组织
的。对于每个 span[j,j +l]，会在位置 k 进行切割。之后，判断 span[j,k] 和 span[k,j +
l] 是否可以形成一个规则的右部。也就是判断 span[j,k] 是否生成了 B，同时判断
span[k,j +l] 是否生成了 C，如果文法中有规则 A→BC，则把这个规则放入 span[j, j +
l]。这个过程由 Compose 函数完成。如果 span[j,j + l] 可以匹配多条规则，所有生成
的推导都会被记录在 span[j,j + l] 所对应的一个列表里
6
。
图8.10展示了 CKY 方法的一个运行实例（输入词串是 aabbc）。算法在处理完最
后一个跨度后会得到覆盖整个词串的分析结果，即句法树的根结点 S。
不过，CKY 方法并不能直接用于层次短语模型，主要有两个问题：
• 层次短语模型的文法不符合乔姆斯基范式；
• 机器翻译中需要语言模型。由于计算当前词的语言模型得分需要前面的词做条
件，因此机器翻译的解码过程并不是上下文无关的。
6
通常，这个列表会用优先队列实现。这样可以对推导按模型得分进行排序，方便后续的剪枝操作。
8.2 基于层次短语的模型 243
S → AB A → CD | CF B → c | BE
C → a D → b E → c F → AD
a
a
b
b
c
l=1 l=2 l=3 l=4 l=5
(a)
0
1
2
3
4
5
序号
跨度
推导
1
[0,1]
C → a
C
a
a
b
b
c
l=1 l=2 l=3 l=4 l=5
(b)
0
1
2
3
4
5
序号
跨度
推导
1
[0,1]
C → a
C
2
[1,2]
C → a
C
3
[2,3]
D → b
D
4
[3,4]
D → b
D
5
[4,5]
B → c ,
E → c
B,E
a
a
b
b
c
l=1 l=2 l=3 l=4 l=5
(c)
0
1
2
3
4
5
序号
跨度
推导
1
[0,1]
C → a
C
2
[1,2]
C → a
C
3
[2,3]
D → b
D
4
[3,4]
D → b
D
5
[4,5]
B → c ,
E → c
B,E
6
[0,2]
none
7
[1,3]
A → CD
A
a
a
b
b
c
l=1 l=2 l=3 l=4 l=5
(d)
0
1
2
3
4
5
序号
跨度
推导
1
[0,1]
C → a
C
2
[1,2]
C → a
C
3
[2,3]
D → b
D
4
[3,4]
D → b
D
5
[4,5]
B → c ,
E → c
B,E
6
[0,2]
none
7
[1,3]
A → CD
A
...
15
[0,5]
S → AB
F
A
S
图 8.10 CKY 算法执行实例
解决第一个问题有两个思路：
• 把层次短语文法转化为乔姆斯基范式，这样可以直接使用原始的 CKY 方法进
行分析；
• 对 CKY 方法进行改造。解码的核心任务要知道每个跨度是否能匹配规则的源
语言部分。实际上，层次短语模型的文法是一种特殊的文法。这种文法规则
的源语言部分最多包含两个变量，而且变量不能连续。这样的规则会对应一
种特定类型的模版，比如，对于包含两个变量的规则，它的源语言部分形如
α
0
X
1
α
1
X
2
α
2
。其中，α
0
、α
1
和 α
2
表示终结符串，X
1
和 X
2
是变量。显然，如
果 α
0
、α
1
和 α
2
确定下来那么 X
1
和 X
2
的位置也就确定了下来。因此，对于每
一个词串，都可以很容易的生成这种模版，进而完成匹配。而 X
1
和 X
2
和原始
CKY 中匹配二叉规则本质上是一样的。由于这种方法并不需要对 CKY 方法进
行过多调整，因此层次短语系统中广泛使用这种改造的 CKY 方法进行解码。
对于语言模型在解码中的集成问题，一种简单的办法是：在 CKY 分析的过程中，
用语言模型对每个局部的翻译结果进行评价，并计算局部翻译（推导）的模型得分。
注意，局部的语言模型得分可能是不准确的，比如，局部翻译片段最左边单词的概
率计算需要依赖前面的单词。但是由于每个跨度下生成的翻译是局部的，当前跨度
244 Chapter 8. 基于句法的模型 肖桐 朱靖波
下看不到前面的译文。这时会用 1-gram 语言模型的得分代替真实的高阶语言模型得
分。等这个局部翻译片段和其他片段组合之后，可以知道前文的内容，这时才会得
出最终的语言模型得分。
另一种解决问题的思路是，先不加入语言模型，这样可以直接使用 CKY 方法进
行分析。在得到最终的结果后，对最好的多个推导用含有语言模型的完整模型进行
打分，选出最终的最优推导。
不过，在实践中发现，由于语言模型在机器翻译中起到至关重要的作用，因此对
最终结果进行重排序会带来一定的性能损失。不过这种方法的优势在于速度快，而
且容易实现。另外，在实践时，还需要考虑两方面问题：
• 剪枝：在 CKY 中，每个跨度都可以生成非常多的推导（局部翻译假设）。理论
上，这些推导的数量会和跨度大小成指数关系。显然不可能保存如此大量的翻
译推导。对于这个问题，常用的办法是只保留 top-k 个推导。也就是每个局部
结果只保留最好的 k 个，即束剪枝。在极端情况下，当 k=1 时，这个方法就变
成了贪婪的方法；
• n-best 结果的生成：n-best 推导（译文）的生成是统计机器翻译必要的功能。比
如，最小错误率训练中就需要最好的 n 个结果用于特征权重调优。在基于 CKY
的方法中，整个句子的翻译结果会被保存在最大跨度所对应的结构中。因此一
种简单的 n-best 生成方法是从这个结构中取出排名最靠前的 n 个结果。另外，
也可以考虑自上而下遍历 CKY 生成的推导空间，得到更好的 n-best 结果
[342]
。
8.2.5 立方剪枝
相比于基于短语的模型，基于层次短语的模型引入了“变量”的概念。这样，可
以根据变量周围的上下文信息对变量进行调序。变量的内容由其所对应的跨度上的
翻译假设进行填充。图8.11展示了一个层次短语规则匹配词串的实例。可以看到，规
则匹配词串之后，变量 X 的位置对应了一个跨度。这个跨度上所有标记为 X 的局部
推导都可以作为变量的内容。
输入字符串：
进口 和 出口 大幅度 下降 了
匹配规则：
X→ ⟨ X
1
大幅度 下降 了, X
1
have drastically fallen ⟩
Span[0,3] 下的翻译假设：
X：the imports and exports
X：imports and exports
X：exports and imports
X：the imports and the exports
S：the import and export
替换 X
1
后生成的翻译假设：
X：the imports and exports have drastically fallen
X：imports and exports have drastically fallen
X：exports and imports have drastically fallen
X：the imports and the exports have drastically fallen
组合
图 8.11 层次短语规则匹配及译文生成
8.2 基于层次短语的模型 245
真实的情况会更加复杂。对于一个规则的源语言端，可能会有多个不同的目标
语言端与之对应。比如，如下规则的源语言端完全相同，但是译文不同：
X → ⟨ X
1
大幅度 下降 了, X
1
have drastically fallen ⟩
X → ⟨ X
1
大幅度 下降 了, X
1
have fallen drastically ⟩
X → ⟨ X
1
大幅度 下降 了, X
1
has drastically fallen ⟩
输入字符串：
进口 和 出口 大幅度 下降 了
匹配规则：
X → ⟨ X
1
大幅度 下降 了, X
1
have drastically fallen ⟩
X → ⟨ X
1
大幅度 下降 了, X
1
have fallen drastically ⟩
X → ⟨ X
1
大幅度 下降 了, X
1
has drastically fallen ⟩
Span[0,3] 下的翻译假设：
X：imports and exports
S：the import and export
替换 X
1
后生成的翻译假设：
X：imports and exports have drastically fallen
X：the import and export have drastically fallen
X：imports and exports have drastically fallen
X：the import and export have drastically fallen
X：imports and exports has drastically fallen
X：the import and export has drastically fallen
组合
图 8.12 不同规则目标语端及变量译文的组合
这也就是说，当匹配规则的源语言部分“X
1
大幅度 下降 了”时会有三个译文
可以选择。而变量 X
1
部分又有很多不同的局部翻译结果。不同的规则译文和不同的
变量译文都可以组合出一个局部翻译结果。图8.12展示了这种情况的实例。
假设有 n 个规则的源语言端相同，规则中每个变量可以被替换为 m 个结果，对
于只含有一个变量的规则，一共有 nm 种不同的组合。如果规则含有两个变量，这
种组合的数量是 nm
2
。由于翻译中会进行大量的规则匹配，如果每个匹配的源语言
端都考虑所有 nm
2
种译文的组合，解码速度会很慢。
在层次短语系统中，会进一步对搜索空间剪枝。简言之，此时并不需要对所有
nm
2
种组合进行遍历，而是只考虑其中的一部分组合。这种方法也被称作立方剪枝
（Cube Pruning）。所谓“立方”是指组合译文时的三个维度：规则的目标语端、第一
个变量所对应的翻译候选、第二个变量所对应的翻译候选。立方剪枝假设所有的译
文候选都经过排序，比如，按照短语翻译概率排序。这样，每个译文都对应一个坐
标，比如，(i,j,k) 就表示第 i 个规则目标语端、第一个变量的第 j 个翻译候选、第
二个变量的第 k 个翻译候选的组合。于是，可以把每种组合看作是一个三维空间中
的一个点。在立方剪枝中，开始的时候会看到 (0,0, 0) 这个翻译假设，并把这个翻译
假设放入一个优先队列中。之后每次从这个优先队里中弹出最好的结果，之后沿着
三个维度分别将坐标加 1，比如，如果优先队列弹出 (i,j , k)，则会生成 (i + 1,j, k)、
(i,j + 1,k) 和 (i,j,k + 1) 这三个新的翻译假设。之后，计算出它们的模型得分，并压
246 Chapter 8. 基于句法的模型 肖桐 朱靖波
入优先队列。这个过程不断被执行，直到达到终止条件，比如，扩展次数达到一个上
限。
X →< 从 X
1
, from X
1
>
X →< 从 X
1
, since X
1
>
X →< 从 X
1
, from the X
1
>
X →< 从 X
1
, through X
1
>
plan
scheme
project
times
2.1
(a) 当前最好结果为 2.1
X →< 从 X
1
, from X
1
>
X →< 从 X
1
, since X
1
>
X →< 从 X
1
, from the X
1
>
X →< 从 X
1
, through X
1
>
plan
scheme
project
times
2.1 5.1
5.5
(b) 当前最好结果为 5.5
X →< 从 X
1
, from X
1
>
X →< 从 X
1
, since X
1
>
X →< 从 X
1
, from the X
1
>
X →< 从 X
1
, through X
1
>
plan
scheme
project
times
2.1 5.1
5.5
8.5
7.7
(c) 当前最好结果为 8.5
X →< 从 X
1
, from X
1
>
X →< 从 X
1
, since X
1
>
X →< 从 X
1
, from the X
1
>
X →< 从 X
1
, through X
1
>
plan
scheme
project
times
2.1 5.1
5.5
8.5
7.7
8.5
7.7
4.2
8.2
(d) 当前最好结果为 8.2
图 8.13 立方剪枝执行过程（行表示规则，列表示变量可替换的内容）
图8.13展示了立方剪枝的过程（规则只含有一个变量的情况）。可以看到，每个
步骤中，算法只会扩展当前最好结果周围的两个点（对应两个维度，横轴对应变量
被替换的内容，纵轴对应规则的目标语端）。
理论上，立方剪枝最多访问 nm
2
个点。但是在实践中发现，如果终止条件设计
的合理，搜索的代价基本上与 m 或者 n 呈线性关系。因此，立方剪枝可以大大提高
解码速度。立方剪枝实际上是一种启发性的搜索方法。它把搜索空间表示为一个三
维空间。它假设：如果空间中某个点的模型得分较高，那么它“周围”的点的得分也
很可能较高。这也是对模型得分沿着空间中不同维度具有连续性的一种假设。这种
方法也可以使用在句法分析中，并取得了很好的效果。
