Python中的高精度字对齐算法

Question

我正在进行一个项目，目的是在句子和其他语言的翻译之间建立一个高精度的词对齐，以衡量翻译质量。我知道Giza++和其他单词对齐工具被用作统计机器翻译管道的一部分，但这不是我想要的。我正在寻找一种算法，可以将单词从源句映射到目标句子中的相应单词，并以透明和准确的方式给出这些限制：

• 这两种语言的语序不一样，顺序也在不断变化。
• 源句中的一些词在目标句中没有对应的词，反之亦然。
• 有时，源中的一个单词对应于目标中的多个单词，反之亦然，并且可以有多到多的映射。
• 在句子中可以使用相同的单词多次，所以对齐需要使用单词及其索引，而不仅仅是单词。

以下是我所做的：

• 从句子对的列表开始，比如英语-德语，每个句子都标记为单词。
• 将每个句子中的所有单词编入索引，并为每个单词创建一个倒排索引(例如，在第5、16、19、26句中出现的单词"world“)。)，无论是源词还是目标词
• 现在，这个倒排索引可以预测任何源词和任何目标词之间的相关性，因为这两个词之间的交集除以它们的联合。例如，如果"Welt“这个词出现在句子5、16、26、32中，则(world，Welt)之间的关联是相交(3)中的索引数除以联合(5)中的索引数，因此相关性为0.6。使用联合使用会降低与高频单词(如" the“)和其他语言中相应单词的相关性。
• 再次遍历所有句子对，并使用给定句子对的源词和目标词的索引来创建相关矩阵。

下面是英语和德语句子之间关联矩阵的一个例子。我们可以看到上面讨论的挑战。

​

​

在图像中，有一个英语和德语句子对齐的例子，显示单词之间的相关性，绿色单元格是正确的对齐点，应该通过单词对齐算法来识别。

以下是我尝试过的一些内容：

• 在某些情况下，预期的对齐可能只是在其各自的列和行中具有最高相关性的单词对，但在许多情况下并非如此。
• 我尝试过类似Dijkstra的算法来绘制一条连接对齐点的路径，但它似乎并不是这样工作的，因为你似乎可以来回跳到句子中的前几个单词，因为词序的关系，而且没有合理的方法跳过没有对齐的单词。
• 我认为最优的解决方案将涉及像扩展矩形这样的东西，从最有可能的通信开始，跨越多到多个通信，跳过没有对齐的单词，但我不确定实现这一点的好方法是什么。

下面是我使用的代码：

import random
src_words=["I","know","this"]
trg_words=["Ich","kenne","das"]
def match_indexes(word1,word2):
    return random.random() #adjust this to get the actual correlation value

all_pairs_vals=[] #list for all the source (src) and taget (trg) indexes and the corresponding correlation values
for i in range(len(src_words)): #iterate over src  indexes
    src_word=src_words[i] #identify the correponding src word
    for j in range(len(trg_words)): #iterate over trg indexes
        trg_word=trg_words[j] #identify the correponding trg word
        val=match_indexes(src_word,trg_word) #get the matching value from the inverted indexes of     each word (or from the data provided in the speadsheet)
        all_pairs_vals.append((i,j,val)) #add the sentence indexes for scr and trg, and the corresponding val

all_pairs_vals.sort(key=lambda x:-x[-1])  #sort the list in descending order, to get the pairs with the highest correlation first
selected_alignments=[]
used_i,used_j=[],[] #exclude the used rows and column indexes
for i0,j0,val0 in all_pairs_vals:
    if i0 in used_i: continue #if the current column index i0 has been used before, exclude current pair-value
    if j0 in used_j: continue #same if the current row was used before
    selected_alignments.append((i0,j0)) #otherwise, add the current pair to the final alignment point selection
    used_i.append(i0) #and include it in the used row and column indexes so that it will not be used again
    used_j.append(j0)

for a in all_pairs_vals: #list all pairs and indicate which ones were selected
    i0,j0,val0=a
    if (i0,j0) in selected_alignments: print(a, "<<<<")
    else: print(a)

这是有问题的，因为它不包含多对多，甚至是一对到多对齐，而且在开始时很容易出错，因为它选择了一个相关性最高的错误对，不包括它的行和列在未来选择中。一个好的算法将考虑到一个对在其各自的行/列中具有最高的相关性，但也会考虑到与其他具有高度相关性的对的接近性。

以下是一些数据，如果您愿意的话，可以在Google中找到：https://docs.google.com/spreadsheets/d/1-eO47RH6SLwtYxnYygow1mvbqwMWVqSoAhW64aZrubo/edit?usp=sharing

Answer 1

我强烈建议测试太棒了-对齐。它依赖于多语言的BERT (mBERT)，其结果看起来非常有希望。我甚至用阿拉伯语测试了它，它在一个困难的对齐例子上做了很好的工作，因为阿拉伯语是一种丰富的词法语言，我相信它比德语这样的拉丁语言更具挑战性。

​

​

正如你所看到的，阿拉伯语中的一个单词对应于英语中的多个单词，然而，令人惊奇的-对齐在很大程度上成功地处理了多到多的映射。你可以试一试，我相信它能满足你的需要。

在https://colab.research.google.com/drive/1205ubqebM0OsZa1nRgbGJBtitgHqIVv6?usp=sharing#scrollTo=smW6s5JJflCN也有Google Colab的演示

祝好运!

Answer 2

词对齐在一定程度上仍是一个开放的研究课题。Giza++背后的概率模型相当重要，参见：http://www.ee.columbia.edu/~sfchang/course/svia/papers/brown-machine-translate-93.pdf。

您可以采取许多现有的方法，例如：

• 实现Giza++自己使用的"IBM模型“(或者如果您勇敢，可以尝试NLTK实现)
• 实现fast_align https://www.aclweb.org/anthology/N13-1073/背后的(简单得多的)算法
• 实现某种形式的基于HMM的对齐https://www.aclweb.org/anthology/C96-2141/
• 使用深度学习，有多种可能性；本文似乎包含了https://www.aclweb.org/anthology/P19-1124.pdf方法的一个很好的概述(通常人们试图利用神经MT模型的注意力机制来实现这一点)。

这是一个非常困难的机器学习问题，虽然像您这样的简单方法可以工作并不是不可能的，但是最好先研究现有的工作。尽管如此，我们在这一领域看到了相当多的技术突破，所以谁知道呢？)

Answer 3

最近，也有两篇论文使用双/多语言的词/上下文嵌入来实现单词对齐。这两种方法都构造了一个二分图，该二部图根据词的嵌入距离进行加权，并利用图算法得到对齐。

一张纸在图形部件之间进行最大匹配。由于匹配是不对称的，它们从两边进行匹配，并使用类似于FastAlign的对称化启发式算法。

另一个提到的对齐只是在图形上使用最小加权边缘覆盖，并使用它作为对齐。

他们两人都声称自己比FastAlign好。