基于IBM Model 1的词对齐与短语抽取Python实现

发表于 | 阅读次数:

本学习报告是作为2018年春季学期《机器翻译》课程的部分笔记和实验报告。参考书为 Philipp Koehn 的 Statistical Machine Translation1。完整代码见于我的GitHub Repo。

说明

其中实验所使用的运行环境如下：

  • 操作系统：Linux
  • Python版本：3.6
  • 可选：csvkit（pip3 install csvkit）

基于词的翻译模型

简介

基于词的翻译模型起源于上世纪IBM关于统计机器翻译的原创性工作，教材主要介绍的是IBM Model 1模型。该模型能够从大量句对齐的语料中自动实现词对齐。

显然这个任务中，我们即不知道英文词和外文词的对齐方式，也不知道他们两两之间的对齐概率。虽然对齐方式和对齐概率我们都不知道，但是如果我知道其中一个，问题就解决了：知道对齐方式，直接得到答案；知道对齐概率，则通过统计可以得到不同对齐方式的概率，取最大概率的对齐方式即可（极大似然估计）。

我们称“对齐”在这个任务中是隐变量，而解决包含隐变量的训练算法是期望最大算法（EM算法）。EM算法的工作流程如下：

  1. 初始化模型，通常从均匀分布开始。
  2. 将模型应用于数据（求期望步骤）。
  3. 从数据中学习模型（最大化步骤）。
  4. 重复迭代步骤2和3直至收敛。

详细的推导详见教材第4章。

词对齐（IBM Model 1）实验

代码解释

本小节我们基于Python使用EM算法实现一个IBM Model 1模型，算法的伪代码位于教材图4.3。

由于使用EM算法，实验需要迭代多轮，直至轮数达到预设值或者误差小于设定阈值。每一轮的训练函数如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
def train_iter(f_sents, e_sents, f_vocab, e_vocab, t_prev):
    t = deepcopy(t_prev)
    # Initialize count(e|f) and total(f)
    count = {e: {f: 0 for f in f_vocab}
             for e in e_vocab}
    total = {f: 0 for f in f_vocab}
    for f_sent, e_sent in zip(f_sents, e_sents):
        fs = f_sent.split()
        es = e_sent.split()
        # In fact s_total is a float,
        # we make it a dict for better readability
        s_total = {e: 0 for e in e_vocab}
        # Compute normalization
        # Eq 4.13 denominator part
        for e in es:
            s_total[e] = 0
            for f in fs:
                s_total[e] += t[e][f]
        # Collect counts
        for e in es:
            for f in fs:
                # Eq 4.14 numerator part
                count[e][f] += t[e][f] / s_total[e]
                # Eq 4.14 denominator part
                total[f] += t[e][f] / s_total[e]
    # Estimate probabilities
    # Eq 4.14
    for e in t.keys():
        for f in t[e].keys():
            t[e][f] = count[e][f] / total[f]
    return t

代码中比较重要的地方标注了教材对应的公式，方便对照查阅。

总训练函数train在每一轮训练中调用以上train_iter函数，代码如下（结果输出部分省略）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def train(f_corpus, e_corpus, epsilon, iter_num, save_dir, save_iteration=False, save_alignment=True):
    f_sents = load_corpus(f_corpus)
    e_sents = load_corpus(e_corpus)
    f_vocab = build_vocab(f_corpus)
    e_vocab = build_vocab(e_corpus)
    t_prev = init_t(f_sents, e_sents, e_vocab)
    converged = False
    i = 0
    while not converged and i < iter_num:
        t = train_iter(f_sents, e_sents, f_vocab, e_vocab, t_prev)
        converged, delta = is_converged(t_prev, t, epsilon)
        i += 1
        t_prev = t
    return t

程序使用argparse来输入参数，需要输入的参数有：

  • --f-corpus：外语语料路径，每行一句（中文语料需分好词）。
  • --e-corpus：英语语料路径，每行一句，须与外语语料句对齐。
  • --save-dir：结果保存路径。
  • --epsilon：设定误差阈值。（默认值=1e3）
  • --iter-num：设定训练轮数。（默认值=10）
  • --save-iteration/--no-save-iteration：是否保存每一轮迭代后的词翻译概率（语料较大勿用，内存容易溢出，仅作为演示用）
  • --save-alignment/--no-save-alignment：是否保存词对齐的结果。

小语料运行演示

我们可以先使用教材上的例句来进行实验，这时输入语料为：

1
2
3
4
5
6
7
8
9
$ cat example.de
das haus
das buch
ein buch
$ cat example.en
the house
the book
a book

在终端按如下参数输入命令即可开始训练，输出的日志会记载每一轮的时间和误差：

1
2
3
4
5
6
7
8
9
10
11
12
13
$ python ibm_model_1.py --f-corpus example.de --e-corpus example.en --iter-num 10 --save-iteration --save-alignment
2018-04-16 18:51:45  Start!
2018-04-16 18:51:45  Iteration 1 finished! Delta = 0.6123724356957945.
2018-04-16 18:51:45    Iteration information saved!
2018-04-16 18:51:45    Alignment result saved!
2018-04-16 18:51:45  Iteration 2 finished! Delta = 0.27603131567314654.
2018-04-16 18:51:45    Iteration information saved!
2018-04-16 18:51:45    Alignment result saved!
...
2018-04-16 18:51:45  Iteration 10 finished! Delta = 0.030043132479938874.
2018-04-16 18:51:45    Iteration information saved!
2018-04-16 18:51:45    Alignment result saved!
2018-04-16 18:51:45  Finished!

输出的结果中的iterations.csv文件记录每一个词对齐的翻译概率，可以看到和教材图4.4一致：

1
2
3
4
5
6
7
8
9
10
11
12
13
$ csvlook iterations.csv
| e     | f    | 0 it. | 1 it. |  2 it. |  3 it. |  4 it. |  5 it. |  6 it. | … |
| ----- | ---- | ----- | ----- | ------ | ------ | ------ | ------ | ------ | - |
| the   | das  |  0.25 |  0.50 | 0.636… | 0.748… | 0.834… | 0.896… | 0.937… | … |
| the   | haus |  0.25 |  0.50 | 0.429… | 0.347… | 0.276… | 0.218… | 0.174… | … |
| the   | buch |  0.25 |  0.25 | 0.182… | 0.121… | 0.075… | 0.044… | 0.025… | … |
| a     | ein  |  0.25 |  0.50 | 0.571… | 0.653… | 0.724… | 0.782… | 0.826… | … |
| a     | buch |  0.25 |  0.25 | 0.182… | 0.131… | 0.090… | 0.060… | 0.038… | … |
| book  | das  |  0.25 |  0.25 | 0.182… | 0.121… | 0.075… | 0.044… | 0.025… | … |
| book  | buch |  0.25 |  0.50 | 0.636… | 0.748… | 0.834… | 0.896… | 0.937… | … |
| book  | ein  |  0.25 |  0.50 | 0.429… | 0.347… | 0.276… | 0.218… | 0.174… | … |
| house | das  |  0.25 |  0.25 | 0.182… | 0.131… | 0.090… | 0.060… | 0.038… | … |
| house | haus |  0.25 |  0.50 | 0.571… | 0.653… | 0.724… | 0.782… | 0.826… | … |

输出结果中的alignment.txt文件记录了每一个英文词对应概率最大的外文词：

1
2
3
4
5
$ cat output/example/alignment.txt 
the	das	0.9629780468299598
book	buch	0.9629780468299598
a	ein	0.8592290797833062
house	haus	0.8592290797833062

以上试运行表明程序设计正确，接下来我们将程序运行于较大的语料上。

大语料运行演示

我们使用的FBIS语料为中英对齐语料，数量为10k，内容如下：

1
2
3
4
5
6
7
8
9
$ head -n 3 fbis.zh.10k 
伊犁 大规模 开展 “ 面 对 面 ” 宣讲 活动
新华社 乌鲁木齐 2 月 1 日 电 ( 记者 樊英利 、 丁建刚 、 李秀芩 ) 为 促进 民族 团结 , 维护 社会 安定 , 近年 来 新疆 伊犁 创造 性地 开展 了 “ 面 对 面 ” 宣讲 活动 , 让 各 族 群众 听到 了 党 和 政府 的 声音 , 受到 热烈 欢迎 。
地处 西北 边陲 的 伊犁 是 我国 对外 开放 的 重要 窗口 , 改革 开放 以来 , 伊犁 经济 获得 长足 发展 , 人民 生活 水平 迅速 提高 。
$ head -n 3 fbis.en.10k 
" Yili Launches Large-Scale ' Face-to-face ' Propaganda Activity "
Urumqi , 1 Feb ( Xinhua ) -- Over the past few years , in order to promote nationality solidarity and safeguard social stability , Xinjiang 's Yili has launched in a creative way a " face-to-face " propaganda activity to let the people of all nationalities hear the voice of the party and government , and the activity has been warmly welcomed .
Located in the country 's northwestern border , Yili has served as an important window during the country 's opening up to the outside world . Since reform and opening up , Yili has developed the economy by a large margin and rapidly improved the people 's livelihood .

在终端使用如下参数训练：

1
2
3
4
5
6
7
8
9
10
$ python ibm_model_1.py --f-corpus fbis.zh.10k --e-corpus fbis.en.10k --iter-num 10 --save-alignment
2018-04-16 10:43:08  Start!
2018-04-16 10:44:39  Iteration 1 finished! Delta = 23.41954195051294.
2018-04-16 10:45:10    Alignment result saved!
2018-04-16 10:46:38  Iteration 2 finished! Delta = 14.01728672063726.
2018-04-16 10:47:10    Alignment result saved!
...
2018-04-16 11:01:38  Iteration 10 finished! Delta = 1.5178054587297218.
2018-04-16 11:02:08    Alignment result saved!
2018-04-16 11:02:09  Finished!

查看输出的alignment.txt可见：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
$ less alignment.txt
introduction    引言    1.0
military        军事    0.9304993049061553
or      	或      0.9282035832570313
kosovo  	科索沃  0.9240566375315791
other   	其他    0.920736615880717
15      	十五日  0.8979442872284269
mobile  	移动    0.8891564322429747
information     信息    0.8889118851814501
spokesman       发言人  0.8861872025346202
advanced        先进    0.881666924721701
taiwan  	台湾    0.8799311621606325
shenzhen        深圳    0.8628715295934547
grain   	粮食    0.86138574336857
power   	权力    0.86018486222242
coal    	煤炭    0.8597328766954059
"       	」      0.8563750182248889
new     	新      0.8513703789669643
...

当然为了下一章的短语抽取实验，我们还需要记录每个英文词所有的对齐候选词以及翻译概率，这个文件以json格式输出存储，内容较杂乱，这里不再展示。

基于短语的翻译模型

简介

基于词的翻译模型并不符合语言学，可以使用短语来作为基本的翻译单元。显然，基于短语的翻译系统性能取决于从基于词的翻译模型中得到的短语翻译表。得到词对齐后，每输入一个句对，可以将其表示为教材图5.3所示矩阵，使用黑色方块表示词的对齐。我们的任务是从这个含有黑色方块的矩阵中，用灰色矩形框出满足一致性（“一致性”从视觉上很容易理解，详见图5.4；其形式化定义见公式（5.3））的一个或者多个黑色方块。

算法思想比较简单，即使用两层for循环遍历矩阵，遇到符合的区域就提取其中的短语。但是需要处理一些边角情形，如对空的情况等。

短语抽取实验

代码解释

本小节我们使用Python实现一个短语抽取的模型，该模型能根据之前实验得到的词对齐，从大量句对齐的语料中通过实现短语自动抽取（抽取的短语不一定具有语言学意义）。算法的伪代码位于教材图5.5。

1
2
3
4
5
6
7
8
9
10
11
12
def phrase_extraction(f_sent, e_sent, A):
    BP = []
    for e_start in range(1, len(e_sent) + 1):
        for e_end in range(e_start, len(e_sent) + 1):
            # Find the minimally matching foreign phrase
            f_start, f_end = len(f_sent), 0
            for (e, f) in A:
                if e_start <= e <= e_end:
                    f_start = min(f, f_start)
                    f_end = max(f, f_end)
            BP += extract(f_start, f_end, e_start, e_end, f_sent, e_sent, A)
    return BP

该函数内双重for循环不断调整着预计抽取短语对的开始、结束下标。每找到一组可行的下标（e_start，e_end，f_start, f_end），就进入第11行使用extract函数进行抽取。例如输入的对齐A=[(1,1), (2,2)]（即教材上的黑格子坐标），则可以进行三次抽取，每次抽取的下标范围为(1,1,1,1)、(1,2,1,2)、(2,2,2,2)（即教材上的灰矩形坐标，由两个顶点确定）。

抽取的函数代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def extract(f_start, f_end, e_start, e_end, f_sent, e_sent, A):
    if f_end == 0:
        return []
    # Check if alignment points violate consistency
    for (e, f) in A:
        if (e < e_start or e > e_end) and f_start <= f <= f_end:
            return []
    # Add phrase pairs (incl. additional unaligned f)
    E = []
    f_s = f_start
    while True:
        f_e = f_end
        while True:
            e_phrase = ' '.join(e_sent[e_start-1: e_end])
            f_phrase = ' '.join(f_sent[f_s-1: f_e])
            E.append((e_phrase, f_phrase))
            f_e += 1
            if not is_aligned(A, f_e, f_sent, e_start, e_end):
                break
        f_s -= 1
        if not is_aligned(A, f_s, f_sent, e_start, e_end):
            break
    return E

注意教材上伪代码第4行（对应此代码第6行）缺少条件，这里添加了后半个条件，否则输出将是整个句对。

抽取给定的下标范围的短语后，还要检测其前后有无对空的可能性。is_aligned函数用于检测这种情况：

1
2
3
4
5
6
7
8
9
10
def is_aligned(A, f_ind, sent, e_start, e_end):
    f_align = []
    for (e, f) in A:
        if f == f_ind:
            f_align.append(e)
    if f_ind < 1 or f_ind > len(sent):
        return False
    if len(f_align) > 0 and (min(f_align) < e_start or max(f_align) > e_end):
        return False
    return True

程序使用argparse来输入参数，需要输入的参数有：

  • --f-corpus：外语语料路径，每行一句（中文语料需分好词）。

  • --e-corpus：英语语料路径，每行一句，须与外语语料句对齐。

  • --save-dir：结果保存路径。

  • --alignment：对齐文件路径，json格式，可由上一个实验自动生成。内容为一个嵌套字典，如下所示：

1
2
3
4
{"the": {"das": 0.9629780468299598, "haus": 0.14077092021669385, "buch": 0.01385591209260682}, 
 "a": {"ein": 0.8592290797833062, "buch": 0.023166041077433423}, 
 "book": {"das": 0.013855912092606825, "buch": 0.9629780468299598, "ein": 0.14077092021669385}, 
 "house": {"das": 0.023166041077433423, "haus": 0.8592290797833062}}

小语料运行演示

我们使用以上程序演示一下教材图5.6的实例：

1
2
3
4
5
6
7
8
if __name__ == '__main__':
    f_sent = 'michael geht davon aus , dass er im haus bleibt'.split()
    e_sent = 'michael assumes that he will stay in the house'.split()
    A = [(1,1), (2,2), (2,3), (2,4), (3,6), (4,7), (5,10), (6,10), (7,8), (8,9), (9,9)]
    phrases = phrase_extraction(f_sent, e_sent, A)
    print(phrases)
    print('Total {} phrases.'.format(len(phrases)))

在终端执行后可以得到和教材完全一致的结果：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
$ python demo.py 
[('michael', 'michael'), 
 ('michael assumes', 'michael geht davon aus'), 
 ('michael assumes', 'michael geht davon aus ,'), 
 ('michael assumes that', 'michael geht davon aus , dass'), 
 ('michael assumes that he', 'michael geht davon aus , dass er'), 
 ('michael assumes that he will stay in the house', 'michael geht davon aus , dass er im haus bleibt'), 
 ('assumes', 'geht davon aus'), 
 ('assumes', 'geht davon aus ,'), 
 ('assumes that', 'geht davon aus , dass'), 
 ('assumes that he', 'geht davon aus , dass er'), 
 ('assumes that he will stay in the house', 'geht davon aus , dass er im haus bleibt'), 
 ('that', 'dass'), 
 ('that', ', dass'), 
 ('that he', 'dass er'), 
 ('that he', ', dass er'), 
 ('that he will stay in the house', 'dass er im haus bleibt'), 
 ('that he will stay in the house', ', dass er im haus bleibt'), 
 ('he', 'er'), 
 ('he will stay in the house', 'er im haus bleibt'), 
 ('will stay', 'bleibt'), 
 ('will stay in the house', 'im haus bleibt'), 
 ('in', 'im'), 
 ('in the house', 'im haus'), 
 ('the house', 'haus')]
Total 24 phrases.

大语料运行演示

仍旧使用的FBIS语料为中英对齐语料，在终端以如下参数执行程序：

1
$ python phrase_extraction.py --f-corpus fbis.zh.10k --e-corpus fbis.en.10k --alignment alignment_all.json

抽取的短语如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
$ less phrases.txt
"  --  “
"  --  开展 “
" yili launches large-scale ' face-to-face  --  伊犁 大规模 开展 “ 面
" yili launches large-scale ' face-to-face  --  伊犁 大规模 开展 “ 面 对
" yili launches large-scale ' face-to-face  --  伊犁 大规模 开展 “ 面 对 面
" yili launches large-scale ' face-to-face  --  伊犁 大规模 开展 “ 面 对 面 ”
...
yili  --  伊犁
large-scale  --  大规模
large-scale  --  大规模 开展
' propaganda activity  --  宣讲
' propaganda activity  --  宣讲 活动

结果基本正确，但由于部分词没有相应的对齐，以及没有对抽取行为做限制，仍有较多瑕疵。后续可以通过训练更好的词对齐（如正反训练一遍做并集）、对抽取短语的长度做限制等，可以提升抽取结果的质量。

结语：神经机器翻译与其他

机器翻译从形式上来说，是序列到序列的任务，但是和序列标注任务（如词性标注）不同的是，大多属情况下，源端序列和目标端序列长度不一致。因此序列标注任务中使用的HMM、CRF等模型不再适用，需要有其他的翻译模型。

在机器翻译的课堂上，除了传统的统计机器翻译（SMT）外，我们也涉猎了若干前沿的神经机器翻译（NMT）模型。神经机器翻译基于深度的神经网络模型，比如CNN和RNN。RNN擅长处理时序模型，可以从输入端随着时序喂入一个分词的句子（以词向量形式），RNN能够在内部维持一个隐状态参数矩阵，用于将上一个时刻的输出，通过该参数矩阵传入下一个时刻，以此解决长程依赖。

为了解决RNN在长距离上梯度传递的消失和爆炸，可以引入LSTM。LSTM在内部使用三个具有可学习参数的门控来决定哪些信息该输入、遗忘、输出，从而解决梯度消失和爆炸的问题。

神经机器翻译模型一般采用seq2seq模型2，seq2seq模型采用encoder-decoder的结构，这里的encoder和decoder可以是CNN也可以是RNN。encoder将输入的句子转化（编码）为一个中间状态向量，decoder则通过此中间状态向量和前面已经翻译好的词汇解码出下一个翻译词汇。seq2seq模型还可以搭配attention机制，可以得到更优秀的、更具有语言学意义的翻译模型。

尽管NMT全面胜出SMT，但NMT参数过多，运行时间过长的缺点也不容小觑，课堂上也讨论了众多的方案。可以使用简单但同样强大的结构来提速，如FAIR提出的纯CNN翻译模型3；也有通过改进梯度传导过程中类似“剪枝”的手段来避免无用部分的梯度传导等根本性的改进4。NMT有比较大的潜力，后续有精力将尝试研究和实现。

参考文献

  1. Koehn, P., 2009. Statistical machine translation. Cambridge University Press.↩

  2. Sutskever, I., Vinyals, O. and Le, Q.V., 2014. Sequence to sequence learning with neural networks. In Advances in neural information processing systems (pp. 3104-3112).↩

  3. Gehring, J., Auli, M., Grangier, D., Yarats, D. and Dauphin, Y.N., 2017. Convolutional sequence to sequence learning. arXiv preprint arXiv:1705.03122.↩

  4. Sun, X., Ren, X., Ma, S. and Wang, H., 2017. meProp: Sparsified back propagation for accelerated deep learning with reduced overfitting. arXiv preprint arXiv:1706.06197.↩