第十六章：统计机器翻译中的形式模型

基于语料库的机器翻译方法可分为两种：基于统计的机器翻译方法和基于实例的机器翻译方法。前者的知识表示是统计数据，后者语料库本身就是翻译知识的一种表现形式。

机器翻译与噪声信道模型

1947 年，美国洛克菲勒基金会自然科学部主任 Weaver 提出使用解读密码的方法进行机器翻译，这实际上是一种统计的方法，需要大量的数学运算，在当时的技术条件下难以实现。

20 世纪 90 年代，在 Weaver 思想的基础上，IBM 的 Peter F. Brown 等提出了统计机器翻译的数学模型。

基于统计的机器翻译把机器翻译看成一个噪声信道问题：根据观察到的语言 T，恢复最为可能的语言 S。S 是信道意义上的源语言，在翻译意义上就是目标语言；T 在信道意义上是目标语言，在翻译意义上就是源语言。比如法译英翻译器，信道意义上看，S 为源语言法语，T 为目标语言英语；翻译意义上看，要翻译成的英语才是源语言。

$P(T|S) = \frac {P(T) P(S|T)}{P(S)}$

即： $\hat{T} = arg max P(T) P(S|T)$

三个问题：

语言模型 P(T) 的参数估计：计算句子概率，N 元语法问题
翻译模型 P(S|T) 的参数估计：使用 EM 发现隐藏在两种语言结构后面的单词之间的对应关系，进行单词对齐
快速有效的搜索算法（解码器）：求解 T’，使得 P(T)P(T|S) 最大

在目标语言句子 T 的长度为 l，源语言句子 S 的长度为 m 时，T 和 S 之间有 l×m 种对应关系。解码器搜索时，需要在所有的 $t_1^l$ 中搜索使 $p(t_1^l) \times p(s_1^m|t_1^l)$ 最大的结果（1 应该表示一对对齐的句子，显然有 l×m 中结果）。因此单词对齐是一个关键问题，引入隐变量 A 表示对齐：

$P(S|T) = \sum_A P(S, A|T)$

假设源语言 $S = s_1^m = s_1^1s_1^2…s_1^m$ 有 m 个单词，目标语言句子 $T = t_1^l = t_1^1t_1^2…t_1^l$ ，

对齐序列 $A=a_1^m = a_1^1a_1^2…a_1^m$ ， $a_1^j=(0,1,…,l), j=(1,2,…,m)$ ，如果源语言第 j 个单词与目标语言第 i 个单词对齐，则： $a_1^j = i$ ，如果没有单词与它对齐，则： $a_1^j = 0$ ，于是有：

$P(S, A|T) = P(m|T) \prod_{j=1}^m P(a_1^j|a_1^{j-1}, s_1^{j-1}, m, T)P(s_j|a_1^j, s_1^{j-1}, m, T)$

首先根据已有的关于目标语言句子的知识，考虑源语言句子长度的概率；然后，再选择在给定目标语言句子和源语言句子长度情况下，目标语言句子中与源语言句子的第一个单词的位置以及对齐的概率；再考虑在给定目标语言句子和源语言句子长度，并且目标语言句子中与源语言句子的第一个单词对齐的那个位置的情况下，源语言句子第一个单词的概率。以此类推分别计算其他单词的概率。

对于翻译模型 P(F|E)（T 是英语 E，S 是法语 F），IBM 提出了五个复杂程度递增的数学模型：

模型 1：只考虑词对词相互翻译的概率 $P(f_j|e_j)$
模型 2：考虑翻译过程中单词位置的变化，引入参数 $P(a_j|j,m,l)$ ，其中 m 是源语言法语句子的长度，l 是目标语言英语句子的长度，j 是法语单词的位置，aj 是位置为 j 的法语单词对应的英语单词的位置
模型 3：考虑源语言中一个单词翻译为目标语言中的多个单词的概率，以及目标语言中的一个单词对应于源语言中的多个单词的概率
模型 4：不仅考虑在对齐时单词位置的变化，而且还考虑在该位置上单词类别的差异，建立了一个基于类的模型，自动把源语言和目标语言的单词划分到 50 个不同的类别中。U. Germann 基于该模型提出了贪心爬山解码算法，这种算法不是通过在每一时刻处理一个输入单词的方法最终建立一个优化完整的翻译假设，而是直接从输入句子的一个完整可能的翻译结果开始，不断地调整源语言（法语）单词和目标语言（英语）单词之间的对应关系，逐步得到最优结果。
模型 5：修正了模型 4 的一些缺陷，避免对于一些不可能出现的对齐给出非零的概率

这些模型的主要区别在于它们在计算源语言单词与目标语言单词之间连接的概率的方式不同。

IBM 的英法机器翻译系统：Candide 分为分析——转换——生成三个阶段，中间表示是线性的，分析和生成都是可逆的。

分析阶段，需要对于输入的法语文本预处理
转换阶段，使用基于统计的方法解码，又分为两个阶段：
- 第一阶段使用粗糙模型的堆栈搜索，输出 140 个评分最高的译文，语言模型为三元语法，翻译模型使用 EM
- 第二阶段使用精细模型的扰动搜索，对第一阶段的结果先扩充再重新评分，语言模型采用链语法，翻译模型采用最大熵模型

1999 年 JHU 夏季研讨班的 EGYPT 包括四个模块：

GIZA++：语料库工具，用于从双语并行语料库中抽取统计知识，进行参数训练
Decoder：解码器，执行翻译过程
Cairo：可视化界面
Whittle：语料库预处理工具

CMU 王野翊和 Alex Waible 提出基于结构的对齐模型改进 IBM 模型：

德语英语语法结构差异较大，训练数据有限，有严重的数据稀疏问题
使用两个层次对齐模型，一个是短语之间的粗对齐模型，一个是短语之内单词的细对齐模型
粗对齐过程中引入了一种短语的语法推导算法，在语料库基础上，通过基于互信息的双语词语聚类和短语归并反复迭代，得到一组基于词语聚类的短语规则，再用这些规则进行句子的短语分析

最大熵模型

统计机器翻译需要训练两个不同的知识源：一个是语言模型 P(T)，一个是翻译模型 P(S|T)，比如法译英翻译器中，要把源语言法语翻译成英语的句子的时候，使用如下模型训练：

$\hat e_1^l = \arg\max\ P(e_1^l)P(f_1^j|e_1^l)$

其中， $f_1^j = f_1,…,f_j$ 表示法语句子， $e_1^l = e_1,…,e_l$ 表示英语句子。

F. J. Och 在 1999 年指出可以通过以下式子得到一样好的结果：

$\hat e_1^l = \arg\max\ P(e_1^l)P(e_1^l|f_1^j)$

这用噪声信道模型是解释不通的，因为法语被看成是目标语言英语在噪声信道中受到干扰形成的，我们首先要做的是从英语的角度出发，来训练把受到干扰形成的法语翻译为英语的统计参数。因此可以不拘泥于该模型，使用直接翻译模型替代：

假设 e 和 f 是目标语言和源语言的句子， $h_1(e,f),…h_m(e,f)$ 是 e 和 f 上的 M 个特征函数，λ1…λm 是与这些特征函数分别对应的 M 个模型参数，直接翻译概率可以用下面的公式模拟：

$P(e|f) \approx p_{\lambda_1…\lambda_m} (e|f)$$ = $$\exp[\sum_{m=1}^M \lambda_m h_m(e,f)] \sum_{e'} \exp[\sum_{m=1}^M \lambda_m h_m(e',f)]$

对于给定法语句子 f，最佳的英语译文 e 可用下式表示：

$\hat e = \arg\max_e P(e|f) = \arg\max_e \sum_{m=1}^M \lambda_m h_m (e,f)$

只要不断调整特征函数 h 和模型参数 λ，进行参数训练和全局搜索，获得最合适的参数值，从而得到：

$\arg\max_e \sum_{m=1}^M \lambda_m h_m (e, f)$

参数训练可以使用最大后验概率标准作为训练标准，最大后验概率标准也就是最大互信息标准（MMI），它使得系统的熵最大，所以模型叫作 ”最大熵模型“（ME）。

参数训练问题也就是如何获得模型参数 $\lambda_1^M$ 的问题：

$\lambda_1^M = \arg \max \sum_{s=1}^S \log_2 P_{\lambda_1}^M (e_s|f_s)$

最大熵模型直接使用统计翻译模型，是一种比噪声信道模型更具有一般性的模型，噪声信道模型是最大熵模型的一个特例。

最大熵模型的基本原理是：在只掌握关于未知分布的部分信息的情况下，符合已知知识的概率分布可能有多个，但使熵值最大的概率分布最真实地反映了事件的分布情况，因为熵定义了随机变量的不确定性，熵最大时，随机变量最不确定，最难准确预测其行为。也就是说，在已知部分信息的前提下，关于未知分布最合理的推断应该是符合已知信息最不确定或最大随机的推断。——宗成庆《统计自然语言处理》

基于平行概率语法的形式模型

基本思想是在源语言和目标语言之间建立一套平行的语法规则，规则一一对应，两套规则服从同样的概率分布。这样源语言的句法分析和目标语言的生成是同步进行的，分析的过程决定了生成的过程。主要有 H. Alshawi 的基于 “中心词转录机” 的模型、同步上下文无关语法（Synchronous Context-Free Grammar，SCFG）模型、吴德恺的 “反向转录语法（Inverse Transduction Grammar，ITG）” 模型。

中心词转录机

一种有限状态转录机，定义为：<q, q', w, v, α, β, c>，其中 q 是输入状态，q’ 是输出状态，w 是输入符号，v 是输出符号，α 是输入位置，β 是输出位置，c 是转录的权重或者代价。

与一般有限状态转录机的区别是：

中心词转录机每条边上不仅有输入，也有输出
中心转录机不是从左至右输入，而是以中心词为坐标往两边输入

中心词转录机可以把源语言的一个中心词以及它左右侧依存的单词构成的序列转换成目标语言的单词 v 及它左右侧依存的单词构成的另一个序列。转录时权重的参数需要根据语料库训练。

中心词转录机对齐的结果是依存树，依存树中所有结点都是具体的单词，不使用词性标记和短语标记。

使用中心词转录机进行统计翻译时，所有的语言知识（词典、规则）都表现为中心词转录机。可以嵌套。

参数使用统计方法训练，根据依存树库中的数据获取统计规则。

同步上下文无关语法（SCFG）

由两个上下文无关语法 G1 和 G2 构成，G1 表示源语言的上下文无关语法，G2 表示目标语言的上下文无关语法，G1 和 G2 中所有规则彼此对应，在句法剖析时同步进行。在对源语言分析时，同步生成了目标语言的句子。

规则左部是非终极符号，右部是用尖括号表示的符号串，逗号前的符号串表示源语言中的重写结果，逗号后的符号串表示目标语言中相应的重写结果。右部可以由非终极符号组成，下标数字表示该符号在符号串中的顺序。右部也可以是具体的单词，表示源语言与目标语言单词的对应关系。

规则使用统计方法，通过训练双语树库获取。

反向转录语法（ITG）

引入了反向产生式，对源语言和目标语言句子进行同步处理，ITG 可以定义为一个五元组：

G = (N, W1, W2, R, S)

G 表示反向转录语法，N 是非终极符号的有限集合，W1 是语言 1 的终极符号（单词）有限集合，W2 是语言 2 的，R 是重写规则有限集合，S∈N 是初始符号。

两种语言的终极符号偶对（单词偶对） $X = (W_1 \cup \{\epsilon\}) \times (W_2 \cup \{\epsilon\})$ 之间含有一个表示翻译的符号，表示为：x/y, x/ε, ε/y 的形式，x ∈ W1，y ∈ W2，x/y 表示语言 1 中的单词 x 在语言 2 中翻译为 y，x/ε 表示 x 没有对应的翻译，ε/y 表示某个空位置被翻译成 y，这时在语言 2 需要插入一个单词（一般是虚词）。后两种在 ITG 中被叫作 “单身汉”。

每一个产生式的右部生成的符号都可以有两个方向：一个是正常的顺向，从左到右连接，表示为：A → [a1,a2…ar]；一个是反向，从右到左连接，表示为：A → <a1, a2…ar>。ITG 转录结果记为 T(G)，语言 1 的字符串集合记为 L1(G)，语言 2 的记为 L2(G)。

对于任何一个反向转录语法 G，存在着一个等价的反向转录语法 G‘，可以把一个反向转录语法改成同步上下文无关语法。

反向转录语法句法分析过程中，输入的是两种语言的句子偶对，而不是单个句子，句法分析的过程就是为输入的句子偶对建立彼此匹配的结构成分的过程。

吴德恺还提出随机反向转录语法（Stochastic ITG，SITG），每一条重写规则都有一个概率。重写规则概率需要在双语并行树库中用统计方法获取。

基于短语的统计机器翻译

前面的翻译模型是建立在单词基础上的，可以叫作基于单词的统计机器翻译模型（Word-Based SMT，WBSMT），有以下不足：

当源语言中多个单词对应目标语言一个单词时（多对一），无法处理
无法处理源语言中的固定短语

因此有必要建立基于短语的统计机器翻译系统（Phrase-Based SMT，PBSMT）。源语言的句子首先切分为短语和单词的组合，然后根据从双语语料库中获取短语翻译的知识，把每一个源语言短语翻译成目标语言短语的可能性用概率表示。好处是：

可以实现双语多对多映射（多对多时可以当作短语处理）
利用短语的局部上下文排歧

实践证明，基于短语的技术可以改善统计机器翻译的质量，但当短语的长度扩大到 3 个以上的单词时（可以理解为 Bi-gram 和 Tri-gram），翻译系统性能就很难得到提高。

David Chiang 提出基于层次短语的统计翻译模型，基本思想是：在不干预基于短语的机器翻译方法的前提下，第一遍调整短语内部单词的顺序，第二遍调整短语之间的顺序。短语由单词和子短语构成，这样短语内就出现了子短语这个层次，这种基于层次短语的翻译模型在形式上是一个同步的上下文无关语法（SCFG），这种句法是从没有任何句法信息标注的双语语料库中通过机器学习获得的。

这种模型主要依靠源语言和目标语言的短语对应表进行翻译，短语对应表要通过双语并行语料库进行抽取，而关键的问题是要进行 “短语对齐”。Och 提出了建造短语 “对齐模板” 的方法。

首先实现子短语的对齐，然后再实现整个短语对齐。注意保持两种语言的短语中所包含的单词的一致性。短语对齐建立在单词对齐的基础上。

对可能产生的很多对齐偶对，可以使用高频词过滤掉多余的短语偶对。
如果一个源语言短语对应于目标语言中若干个短语，就会出现对齐歧义，可以根据上下文排歧。

进行基于短语的机器翻译时，先把源语言句子切分成短语串，然后按照短语对应表映射，最后对映射后的目标语言短语串进行排序，得到目标语言的输出。短语中包含了局部的单词选择和局部顺序以及很多习惯表达和搭配信息，这是基于单词的统计机器翻译不具备的。

基于句法的统计机器翻译

基于短语的机器翻译没考虑短语与短语之间的关系，因此难以处理短语之间重新排序的问题，另外对于短语之间的长距离依存关系也难以处理。

2001 年 Yamada 和 Knight 提出了基于句法的统计机器翻译（syntax-based SMT，SBSMT），输入源语言的句法树，输出目标语言的句子。

调序：输入树形图的每个子树要根据概率重新排列，进行顺序调整
- 根据双语并行语料库中两种语言调序关系的概率
- 需要建立调序表：记录着调序规则的概率
插入：在子树结点的左边或右边随机插入恰当的功能词，左插、右插或不插的概率取决于父结点和当前结点的标记，概率只与该单词有关，与位置无关
- 根据目标语言语法规则插入
- 需要建立结点表：记录非终极符号插入树形图中有关结点的概率，还要考虑功能词本身的插入概率
- 整个树的插入概率等于 “插入结点位置概率的乘积” 与 “插入功能词概率的乘积” 相乘
翻译：根据词对词的翻译概率把途中每一个叶子结点上的单词翻译为目标语言的相应单词
- 需要建立翻译表：记录源语言单词翻译为目标语言单词的概率
- 单词的翻译概率等于源语言句子中单词翻译为目标语言的单词的翻译概率的乘积
输出：输出译文句子
- 计算 “调序-插入-翻译” 联合概率：三者概率的乘积

使用期望最大算法进行概率估计：

初始化所有概率表（通常设置为均匀分布）
清楚每种操作的计数器
对每一个源语言句法树和目标语言句子的偶对执行：
- 计算调序、插入、翻译三中操作每种可能的组合方式的概率
- 把每种操作的概率分别加到相应的计数器
根据计数器的值重新计算三张概率表的概率值
重复上述三步直至收敛

小结

机器翻译与噪声信道模型
- 1947 年，美国洛克菲勒基金会自然科学部主任 Weaver 提出使用解读密码的方法进行机器翻译。20 世纪 90 年代，在 Weaver 思想的基础上，IBM 的 Peter F. Brown 等提出了统计机器翻译的数学模型。
- 基于统计的机器翻译把机器翻译看成一个噪声信道问题：根据观察到的语言 T，恢复最为可能的语言 S。S 是信道意义上的源语言，在翻译意义上就是目标语言；T 在信道意义上是目标语言，在翻译意义上就是源语言。
- 三个问题：
  - 语言模型的参数估计：计算句子概率，N 元语法问题
  - 翻译模型的参数估计：使用 EM 发现隐藏在两种语言结构后面的单词之间的对应关系，进行单词对齐
  - 快速有效的搜索算法（解码器）
- IBM 提出了五个复杂程度递增的数学模型，这些模型的主要区别在于它们在计算源语言单词与目标语言单词之间连接的概率的方式不同。
- IBM 的英法机器翻译系统：Candide 分为分析——转换——生成三个阶段，中间表示是线性的，分析和生成都是可逆的。
- 1999 年 JHU 夏季研讨班的 EGYPT 包括四个模块：GIZA++, Decoder, Cairo 和 Whittle。
- CMU 王野翊和 Alex Waible 提出基于结构的对齐模型改进 IBM 模型，使用两个层次对齐模型，一个是短语之间的粗对齐模型，一个是短语之内单词的细对齐模型。
最大熵模型
- 最大熵模型直接使用统计翻译模型，是一种比噪声信道模型更具有一般性的模型，噪声信道模型是最大熵模型的一个特例。
基于平行概率语法的形式模型
- 基本思想是在源语言和目标语言之间建立一套平行的语法规则，规则一一对应，两套规则服从同样的概率分布。这样源语言的句法分析和目标语言的生成是同步进行的，分析的过程决定了生成的过程。
- H. Alshawi 的基于 “中心词转录机” 的模型
  - 与一般有限状态转录机的区别是：中心词转录机每条边上不仅有输入，也有输出；中心转录机不是从左至右输入，而是以中心词为坐标往两边输入。
  - 中心词转录机可以把源语言的一个中心词以及它左右侧依存的单词构成的序列转换成目标语言的单词 v 及它左右侧依存的单词构成的另一个序列。转录时权重的参数需要根据语料库训练。
  - 中心词转录机对齐的结果是依存树，依存树中所有结点都是具体的单词，不使用词性标记和短语标记。
  - 使用中心词转录机进行统计翻译时，所有的语言知识（词典、规则）都表现为中心词转录机。可以嵌套。
  - 参数使用统计方法训练，根据依存树库中的数据获取统计规则。
- 同步上下文无关语法（Synchronous Context-Free Grammar，SCFG）模型
  - 由两个上下文无关语法 G1 和 G2 构成，G1 表示源语言的上下文无关语法，G2 表示目标语言的上下文无关语法，G1 和 G2 中所有规则彼此对应，在句法剖析时同步进行。在对源语言分析时，同步生成了目标语言的句子。
  - 规则使用统计方法，通过训练双语树库获取。
- 吴德恺的 “反向转录语法（Inverse Transduction Grammar，ITG）” 模型
  - 引入了反向产生式，对源语言和目标语言句子进行同步处理。
  - 每一个产生式的右部生成的符号都可以有两个方向：一个是正常的顺向，从左到右连接；一个是反向，从右到左连接。
  - 对于任何一个反向转录语法 G，存在着一个等价的反向转录语法 G‘，可以把一个反向转录语法改成同步上下文无关语法。
  - 反向转录语法句法分析过程中，输入的是两种语言的句子偶对，而不是单个句子，句法分析的过程就是为输入的句子偶对建立彼此匹配的结构成分的过程。
基于短语的统计机器翻译
- 基于单词的统计机器翻译模型无法处理多对一和固定短语问题，David Chiang 提出基于层次短语的统计翻译模型，基本思想是：在不干预基于短语的机器翻译方法的前提下，第一遍调整短语内部单词的顺序，第二遍调整短语之间的顺序。
- 这种模型主要依靠源语言和目标语言的短语对应表进行翻译，短语对应表要通过双语并行语料库进行抽取，而关键的问题是要进行 “短语对齐”。Och 提出了建造短语 “对齐模板” 的方法：首先实现子短语的对齐，然后再实现整个短语对齐。注意保持两种语言的短语中所包含的单词的一致性。短语对齐建立在单词对齐的基础上。
基于句法的统计机器翻译
- 基于短语的机器翻译没考虑短语与短语之间的关系，因此难以处理短语之间重新排序的问题，另外对于短语之间的长距离依存关系也难以处理。2001 年 Yamada 和 Knight 提出了基于句法的统计机器翻译（syntax-based SMT，SBSMT），输入源语言的句法树，输出目标语言的句子。
- 步骤如下：
  - 调序：输入树形图的每个子树要根据概率重新排列，进行顺序调整
  - 插入：在子树结点的左边或右边随机插入恰当的功能词，左插、右插或不插的概率取决于父结点和当前结点的标记，概率只与该单词有关，与位置无关
  - 翻译：根据词对词的翻译概率把途中每一个叶子结点上的单词翻译为目标语言的相应单词
  - 输出：输出译文句子
- 使用期望最大算法进行概率估计。

本章中的内容现在看来已经有点过时了，事实上本书大部分内容都是自然语言处理的形式模型，这在这个深度学习满天飞的时代多少显得有些另类。但其中的一些思想并不过时，能给人不少启发，比如基于短语的翻译；而且涉及到的一些模型和算法也是现在常用的，比如 Viterbi，前向后向算法，beamsearch 等等。不过对于最新的一些技术我觉得更加需要了解掌握，正好收集整理了一些，罗列如下：

Microsoft/NPMT: Towards Neural Phrase-based Machine Translation Microsoft 基于短语的翻译系统
tensorflow/nmt: TensorFlow Neural Machine Translation Tutorial Google 基于 Seq2Seq 和 Attention 的翻译系统
models/official/transformer at master · tensorflow/models Google 基于纯 Attention 的翻译模型
pytorch/fairseq: Facebook AI Research Sequence-to-Sequence Toolkit written in Python. Facebook 基于 CNN 的翻译系统
facebookresearch/UnsupervisedMT: Phrase-Based & Neural Unsupervised Machine Translation Facebook 基于无监督的翻译系统
DeepL Translator DeepL 基于 CNN 的翻译工具
OpenNMT/OpenNMT: Open Source Neural Machine Translation

Yam

Feeling, Coding, Thinking

自然语言计算机形式分析的理论与方法笔记(Ch16)