放牧代码和思想
专注自然语言处理、机器学习算法

Michael Collins NLP公开课任务3 机器翻译

目录

hankcs.com 2017-01-22 下午10.04.58.pnghankcs.com 2017-01-31 下午5.23.32.pnghankcs.com 2017-01-31 下午5.23.57.pnghankcs.com 2017-01-31 下午5.29.18.pnghankcs.com 2017-01-30 下午8.15.08.pnghankcs.com-2017-01-28-下午10.55.28.pnghankcs.com 2017-01-28 下午11.10.28.pnghankcs.com 2017-01-31 上午11.19.52.pnghankcs.com 2017-01-14 下午10.00.04.png说是机器翻译,其实只涉及最最简单的两个模型:IBM1和2以及启发式改进,用来做文本对齐。代码见文末,包括附加题在内全部达到了预期目标。

文本对齐

文本对齐是这么一个问题,将母语翻译为外语时,给定一个长l的母语句子hankcs.com 2017-01-14 下午9.15.20.png和长度m,估计一个长m的外语句子hankcs.com 2017-01-14 下午9.22.24.png及后者到前者的对齐方式hankcs.com 2017-01-14 下午9.23.03.png的概率hankcs.com 2017-01-14 下午9.34.26.png

无论哪种模型,通用的抽象框架都是一样的。分为两步,先根据e和m得到某个对齐方式a的概率hankcs.com 2017-01-14 下午10.05.12.png,然后根据这个a计算对应外语句子f的概率hankcs.com 2017-01-14 下午10.06.54.png

第一步中所谓的对齐方式,其实只是将外语中的每个单词映射到母语的某个单词(多对一),却并不要求母语的每个单词都有对应的外语映射。举个例子:

hankcs.com 2017-01-14 下午9.57.13.png

其中,hankcs.com 2017-01-14 下午9.57.38.png

hankcs.com 2017-01-14 下午9.59.31.png

则表示如下对齐方式

hankcs.com 2017-01-14 下午10.00.04.png

英语第一个and就没有对应的法语单词。

甚至可以举个极端的例子:

hankcs.com 2017-01-14 下午10.02.19.png

对应着一个很糟糕的对齐方式:

hankcs.com 2017-01-14 下午10.03.25.png

你也许会很好奇,凭什么多个外语单词能映射到同一个母语单词,反过来却不行呢?对,这的确是个不合实际的约束。加了这个约束后,IBM模型变得简单可实现了,但也带来了失真的问题。接下来的课程Phrase-based_Translation_Models会详细讲这个问题。

hankcs.com 2017-01-31 上午11.19.52.png

无论如何,要点是第一步不要纠结双方的单词,只得出一个抽象的下标数组。

第二步就要考虑双方单词的这种对应方式存在的概率了。为了表述方便,定义此概率为hankcs.com 2017-01-28 下午11.06.03.png,表示已知母语单词e,对应到外语单词f的条件概率。

把两步的概率乘起来,就得到最终的文本对齐概率。

IBM1

第一步,简单地认为所有对齐方式都是等可能的:

hankcs.com 2017-01-14 下午10.05.12.png=hankcs.com 2017-01-14 下午10.11.05.png

第二步,简单地认为所有映射关系都是独立的:

hankcs.com 2017-01-14 下午10.12.01.png

最终得到:

hankcs.com 2017-01-14 下午10.13.58.png

接连做了两个简单粗暴的假设,可以预见这不是个好模型。

IBM2

第一步,对对齐方式的估计,IBM2做了改进:

定义hankcs.com 2017-01-14 下午10.21.52.png为给定母语长度l外语长度m,第j个外语单词映射到第i个母语单词的概率,于是有:

hankcs.com 2017-01-14 下午10.23.30.png

第二步,与IBM1一样:

hankcs.com 2017-01-14 下午10.12.01.png

最终得到:

hankcs.com 2017-01-14 下午10.26.47.png

模型大致的框架就是这样了。

参数估计问题

输入训练语料——n个双语句子hankcs.com 2017-01-28 下午10.58.59.png,其中hankcs.com 2017-01-28 下午10.59.13.png

输出模型参数——参数hankcs.com 2017-01-28 下午11.00.57.pnghankcs.com 2017-01-28 下午11.01.17.png,复习一下Micheal Collins在讲义中给出的两者定义:

hankcs.com 2017-01-28 下午11.10.28.png

具体估计时用EM算法,到时候再说。

由于IBM1中hankcs.com 2017-01-28 下午10.51.28.png,所以实际上只有一个参数hankcs.com 2017-01-28 下午11.00.57.png。用Python描述如下:

class IBM1:
    def __init__(self):
        self.t = defaultdict(float) # t[(fword, eword)] := t(f|e)

而IBM2就是完整的t和q了:

class IBM2:
    def __init__(self):
        self.t = defaultdict(float)  # t[(fword, eword)] := t(f|e)
        self.q = defaultdict(float)  # q[(j, i, l, m)] := q(j|i,l,m)

训练数据

训练数据是来自Europarl corpus的英语-西班牙语双语语料:

> head -n 3 corpus.en
resumption of the session
i declare resumed the session of the european parliament adjourned on ...
Although , as you will have seen , the dreaded ’ millennium bug ’ failed  ...

					
> head -n 3 corpus.es
reanudaci ́on del per ́ıodo de sesiones
declaro reanudado el per ́ıodo de sesiones del parlamento europeo ...
como todos han podido comprobar , el gran " efecto del a ̃no 2000 " no se ...

评估

如何评估对齐的效果呢?

除了训练数据之外,assignment中还给出了人工标注的对齐数据h3/dev.key:

6 7 3
6 7 4
6 8 5

每行数据的意思是:

SentenceIndex EnglishIndex ForeignIndex

6 7 3代表第6个句子对中,第7个英语词语对应第3个西班牙词语。

• e=Do we want to make it happen?

• f = ¿ Deseamos hacerla realidad ?

整个句子的对齐方式是

hankcs.com 2017-01-22 下午10.04.58.png

评估脚本h3/eval_alignment.py已经给出,其工作原理很简单,将每行数据读入,做交并集得到各个指标

self.gold += len(gold_set)
self.test += len(test_set)
self.correct += len(gold_set & test_set)

问题1 IBM Model 1

由于没有标注好的对齐数据,“对齐数据”实际上是个隐变量。此时应该使用含有隐变量的概率模型参数的极大似然估计法,也即EM算法。

定义k为第k个句子,定义

hankcs.com 2017-01-28 下午10.46.47.png

hankcs.com 2017-01-28 下午11.21.08.png其实是在当前模型参数下hankcs.com 2017-01-28 下午11.21.30.png的概率。

在IBM1模型中,简单地认为所有对齐方式都是等可能的

hankcs.com 2017-01-14 下午10.05.12.png=hankcs.com 2017-01-14 下午10.11.05.png

所以hankcs.com 2017-01-28 下午10.51.28.png,代入上上式有

hankcs.com 2017-01-28 下午10.50.35.png

于是得到IBM1的EM算法伪码

hankcs.com-2017-01-28-下午10.55.28.png

初始化的时候可以取随机数,也可以取c(e,f)/c(e),虽然两者差别并不大。

def initialize(self, corpus):
    words = defaultdict(float)
    pairs = defaultdict(float)
    for e, f in corpus:
        for eword in e:
            for fword in f:
                if (fword, eword) not in pairs:
                    words[eword] += 1.0
                    pairs[(fword, eword)] = 1.0

    for (fword, eword) in pairs:
        self.t[(fword, eword)] = pairs[(fword, eword)] / words[eword]

hankcs.com 2017-01-28 下午11.22.51.png其实是hankcs.com 2017-01-28 下午11.21.08.png的求和,前面说过hankcs.com 2017-01-28 下午11.21.08.png其实是在当前模型参数下hankcs.com 2017-01-28 下午11.21.30.png的概率。概率求和得到期望,所以hankcs.com 2017-01-28 下午11.22.51.png其实是e_j与f_j对齐的期望(可以理解为估计频次)。同理理解hankcs.com 2017-01-28 下午11.26.30.png为e_j在母语中的估计词频,同理理解剩下的两个c。

其中每个迭代t和q的更新都用到了最大似然估计:

hankcs.com 2017-01-28 下午11.12.18.png

下标ML是maximum-likelihood的缩写。

由于IBM1和IBM2有许多通用的方法,不如写一个wrapper,把model包装起来统一训练,这部分代码

def EM(self, iterations=5):
    c_fe = defaultdict(int)
    c_e = defaultdict(int)
    c_jilm = defaultdict(int)
    c_ilm = defaultdict(int)

    t = defaultdict(float)
    q = defaultdict(float)

    for s in range(iterations):

        c_fe.clear()
        c_e.clear()
        c_jilm.clear()
        c_ilm.clear()
        t.clear()
        q.clear()

        for fe, (e, f) in enumerate(self.text):

            l = len(e)
            m = len(f)
            for i, fword in enumerate(f):
                total, vals = self.model.prob_list(fword, e, i, l, m)
                for j, eword in enumerate(e):
                    delta = vals[j] / total
                    c_fe[fword, eword] += delta
                    c_e[eword] += delta
                    c_jilm[j, i, l, m] += delta
                    c_ilm[i, l, m] += delta

        for fe in c_fe:
            t[fe] = c_fe[fe] / c_e[fe[1]]

        for j, i, l, m in c_jilm:
            q[j, i, l, m] = c_jilm[j, i, l, m] / c_ilm[i, l, m]

        self.model.set_t(t)
        self.model.set_q(q)

Micheal Collins的讲义(上图伪码)有一处笔误,set了t之后,不需要再set q,保持hankcs.com 2017-01-28 下午10.51.28.png即可。

在实现中,IBM1的set_q其实是个空白的方法:

def set_q(self, qvals):
    pass

IBM1模型测试

既然hankcs.com 2017-01-14 下午10.13.58.png,且上下文无联系。那么每一个连乘子项都取最大就行了:

def prob_list(self, fword, e, i, l, m):
    a = defaultdict(float)
    total = 0.0
    for j, eword in enumerate(e):
        val = self.t[fword, eword]
        total += val
        a[j] = val

    return total, a
...
for i, fword in enumerate(f):
    total, vals = self.model.prob_list(fword, e, i, l, m)
    d1 = max(vals, key=(lambda x: vals[x]))
    output.write("%s %s %s\n" % (s + 1, i + 1, d1))

调用方法

先执行

model = IBM1()
mt = IBM(model)
mt.read_file("corpus.en", "corpus.es")
mt.EM()
mt.read_dev_file("dev.en", "dev.es", "dev.ibm1.out")

评测

然后跑一跑评测脚本

#!/usr/bin/env bash
python eval_alignment.py dev.key dev.out

得到

      Type       Total   Precision      Recall     F1-Score
===============================================================
     total        5920     0.413        0.427        0.420

这次assignment的三道题对应的三个预期分值如下:

The expected development F-Scores are 0.420, 0.449, and a basic intersection alignment should give 0.485 for the last part.

问题2 IBM Model 2

理解了IBM1之后,IBM2的训练也没什么复杂的。

hankcs.com 2017-01-30 下午8.15.08.png

比较一下两者,发现唯一的核心不同点在于q的引入,IBM2中的q不再是定值,而是一个可变的参数。为此,引入了另外两个计数器c来统计期望。hankcs.com 2017-01-28 下午11.21.30.png的概率delta的计算方式也有所不同:

hankcs.com 2017-01-28 下午10.46.47.png

反映在代码上,算法主框架EM不变,但delta计算方法不同。

IBM2模型测试

利用到了q:

def prob_list(self, fword, e, i, l, m):
    a = {}
    total = 0.0
    for j, eword in enumerate(e):
        val = self.t[fword, eword] * self.q[j, i, l, m]
        total += val
        a[j] = val

    return total, a

c1和c2的计算与IBM1一致,后面追加了c3和c4。

于是测试的时候也要利用参数q

hankcs.com 2017-01-30 下午8.37.05.png

另外,算法初始化的时候可以直接利用IBM1模型的t作为初值,效果比随机数要好。

调用方法

类似地

model = IBM2()
mt = IBM(model)
mt.read_file("corpus.en", "corpus.es")
mt.EM()
mt.read_dev_file("dev.en", "dev.es", "dev.ibm2.out")

评测

跑跑评估

#!/usr/bin/env bash
python eval_alignment.py dev.key dev.ibm2.out

得到

      Type       Total   Precision      Recall     F1-Score
===============================================================
     total        5920     0.442        0.456        0.449

效果的确好了一些。

附加问题3:Growing Alignments

上面提到过,答案中允许一个母语单词对齐到多个外语单词(这才是正常的,答案是人工标注的),而IBM模型却不允许。

这道题目探索如何通过IBM模型生成多对多的对齐。事实上,phrase-based translation里面的提取短语就要利用这道题目的思路。

其做法是

1、与问题2相同,估计IBM2的分布hankcs.com 2017-01-31 下午4.51.16.png

2、将母语视作外语,外语视作母语,送入IBM2估计分布hankcs.com 2017-01-31 下午4.52.22.png

3、根据hankcs.com 2017-01-31 下午4.51.16.pnghankcs.com 2017-01-31 下午4.52.22.png计算各自的最佳对齐

hankcs.com 2017-01-31 下午5.23.32.png

4、计算这两个对齐方式的交集

hankcs.com 2017-01-31 下午5.23.57.png

5、从交集开始,启发式地对齐,启发规则如下:

  • 先把交集都采用

  • 一次只加一个点

  • 只给那些还未对齐的单词添加点

  • 优先考虑相邻的点

  • 然后考虑其他点

最终效果如下:

hankcs.com 2017-01-31 下午5.29.18.png

可见最终效果达到了多对多。

实现的时候倒是怪无聊的,无非是一些杂七杂八的规则。

首先直接读入IBM2的输出,免得再去训练啊对齐之类。

def read_alignments(self):
    a1 = file("dev.ibm2.out", "r")
    a2 = file("dev.ibm2r.out", "r")

    for line in a1:
        line = line.split(" ")
        line[-1] = line[-1].strip()
        self.all_f[int(line[0])].append((int(line[1]), int(line[2])))

    for line in a2:
        line = line.split(" ")
        line[-1] = line[-1].strip()
        self.all_e[int(line[0])].append((int(line[1]), int(line[2])))

然后取交集和并集,交集全部应用。对并集中的pair,将其视作二维点。对并集的每个点找寻离已应用的pair最近的距离,若最近距离足够小,则认为相邻,也加进去。

既然是规则,必然是丑陋的,什么是足够小?为什么足够小的就是好的?只能说经验证明如此,无法深究。

这些规则如下:

def growing(self):
    self.uni()
    self.intersection()
    self.grow = self.insec.copy()

    for sent in self.grow:
        u = self.union[sent]
        for ef in u:
            fdone = set([k[1] for k in self.grow[sent]])
            edone = set([k[0] for k in self.grow[sent]])
            if ef[1] not in fdone or ef[0] not in edone:
                if self.distance(ef, self.grow[sent]) <= 9:
                    self.grow[sent].append(ef)

        d1 = [k[0] for k in self.all_e[sent]]
        d2 = [k[1] for k in self.all_f[sent]]
        d = math.fabs(max(d1) - max(d2)) + 3

        self.grow[sent] = [v for v in self.grow[sent]
                           if math.fabs(v[0] - v[1]) < (d + v[1] / 4)]

距离小于3,然后根据ef最大下标差值过滤一遍,没什么好说的。

调用方法

调用方法如下

model = IBM1()
mt = IBM(model)
mt.read_file("corpus.es", "corpus.en")
mt.EM()

model = IBM2()
mt = IBM(model)
mt.read_file("corpus.es", "corpus.en")
mt.EM()
mt.read_dev_file("dev.es", "dev.en", "dev.ibm2r.out", invert=True)

p = Phrase()
p.read_alignments()
p.growing()
output_dev_file(p.grow, "dev.phase.out")

注意IBM1和2的代码与问题1和2不同,es在前en在后,相当于掉转了母语和外语,得到的是分布hankcs.com 2017-01-31 下午4.52.22.png。将该分布在dev文件上的输出与问题2合在一起送入Phrase做启发式的growing,得到最终答案。

评测

调用评测脚本

#!/usr/bin/env bash
python eval_alignment.py dev.key dev.phase.out

这部分得到

      Type       Total   Precision      Recall     F1-Score
===============================================================
     total        5920     0.587        0.457        0.514

超过预期了。

Reference

https://github.com/hankcs/Coursera_NLP_MC 

https://github.com/successar/NLP 

知识共享许可协议 知识共享署名-非商业性使用-相同方式共享码农场 » Michael Collins NLP公开课任务3 机器翻译

分享到:更多 ()

评论 欢迎留言

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

我的开源项目

HanLP自然语言处理包基于DoubleArrayTrie的Aho Corasick自动机