Python 中的高精度词对齐算法

Question

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

两种语言的词序不一样，而且顺序不断变化
源句中的某些词在目标句中没有对应的词，反之亦然
有时源中的一个单词对应目标中的多个单词，反之亦然，可以存在多对多映射
句子中可能会出现多次使用同一个词的句子，所以对齐需要对词及其索引进行，而不仅仅是词

这是我所做的：

从句子对列表开始，比如英语-德语，每个句子标记为单词
索引每个句子中的所有单词，并为每个单词创建一个倒排索引（例如单词 "world" 出现在句子 # 5, 16, 19, 26 ... 等），对于源和目标词
现在这个倒排索引可以预测任何源词和任何目标词之间的相关性，即两个词的交集除以它们的并集。例如tagret词"Welt"出现在句子5,16,26,32中，(world,Welt)之间的相关性是交集(3)中的索引数除以交集(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)

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

这里有一些数据，如果您愿意，可以试试，它在 Google 张中： https://docs.google.com/spreadsheets/d/1-eO47RH6SLwtYxnYygow1mvbqwMWVqSoAhW64aZrubo/edit?usp=sharing

Answer 1

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

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

自己实现 Giza++ 使用的 "IBM models"（或者如果你够勇敢，试试 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 2

最近也有两篇论文使用bi-/multilingual word/contextual embeddings做词对齐。他们都构建了一个二分图，其中单词用它们的嵌入距离加权，并使用图算法来获得对齐。

One paper 在图形部分之间进行最大匹配。因为匹配不是对称的，所以他们从两侧进行匹配，并使用与 FastAlign 类似的对称启发式算法。

The other one提到对齐只是简单地在图上使用了最小加权边缘覆盖并将其作为对齐。

他们都声称比 FastAlign 更好。

Answer 3

我强烈建议测试 Awesome-Align。它依赖于多语言 BERT (mBERT)，结果看起来很有希望。我什至用阿拉伯语对其进行了测试，它在一个困难的对齐示例中表现出色，因为阿拉伯语是一种形态学丰富的语言，我相信它比德语等基于拉丁语的语言更具挑战性。

如您所见，一个阿拉伯语单词对应多个英语单词，而 Awesome-Align 在很大程度上成功地处理了多对多映射。您可以试试看，相信一定能满足您的需求。

在 https://colab.research.google.com/drive/1205ubqebM0OsZa1nRgbGJBtitgHqIVv6?usp=sharing#scrollTo=smW6s5JJflCN

上还有一个 Google Colab 演示

祝你好运！

Answer 4

由于问题是专门针对 Python 实现的，而 Giza++ 和 FastAlign 似乎仍然代表 SOTA，因此可以查看

https://pypi.org/project/systran-align/: replicates FastAlign. Seems to be relatively mature. Also note that the original FastAlign code contains a Python wrapper (https://github.com/clab/fast_align/blob/master/src/force_align.py).
https://www.nltk.org/api/nltk.align.html：复制大多数 GIZA 模型（性能和质量之间的良好折衷是 IBM4）。然而，尚不清楚测试的彻底程度和维护的程度，因为人们通常更喜欢直接使用 GIZA++。

关于该主题的大多数研究代码如今都将出现在 Python 中并基于嵌入，例如 https://github.com/cisnlp/simalign, https://github.com/neulab/awesome-align 等。但是，对于它们是否优于旧模型尚无定论如果是这样，适用于哪些应用程序。最后，您需要在上下文感知（重新排序！）、精确度、召回率和运行时之间寻求折衷。神经模型具有更多上下文感知的巨大潜力，统计模型具有更可预测的行为。

Python 中的高精度词对齐算法

High Precision Word Alignment Algorithm in Python

python

machine-translation