Large Scale Parallel Document Mining for Machine Translation
以前的对齐文档挖掘依赖于metadata,比如发布日期。但web内容是非结构化的。

系统描述

  1. 将所有文档翻译为英文
  2. 提取match n-gram(构建候选集合)和score n-gram(计算document得分)
    这个阶段生成两个索引,forward index列出所有提取的score n-gram,按文档索引。
    倒排索引,match n-gram匹配的所有文档,match n-gram作为索引。
    倒排索引还用于累计出现score n-gram 文档的频率等
  3. 为倒排索引中每个mache n-gram生成文档对。只保留源自不同语言的对,删除单一n-gram或单一语言文档。
  4. 丢弃匹配频率超过一定阈值的match ngram。由于match ngram的长尾分布,仅会导致一小部分的n-gram被过滤掉。(这个过滤步骤会导致系统运行的整体时间和输出数据呈线性关系)
  5. 根据score n-gram文档频率更新forward index(pairwise scoring)
  6. 计算所有候选文档的pairwise scores,分数低于一定阈值的将会被丢掉。为每种语言生成一个n-best列表
  7. 从n-best列表中丢弃非对称文档。

pairwise scoring

对于文档\(d_1\)和\(d_2\)
\(F_{d_{1}}={f_1,f_2,...,f_n}\)score ngram的集合
\(idf(f)=log\frac{D}{df(f)}\) D输出的文档个数,df(f)是包含ngram f的文档个数。
将\(F_{d_{1}},F_{d_{2}}\)视为特征向量。
通过余弦相似度来计算两个文档的相似评分。

作者在初步实验中,结合词频得到基本的tf/idf,以及使用其他结合词频的信息检索排序函数,如bm25,与上述更简单的评分函数相比,性能有所下降。
除此之外,作者新增了一个score n-gram相对位置距离的过滤条件,保证,score ngram的顺序基本一致。在统计score ngram信息时,也会抽取他的相对位置存储在forward index中。

计算复杂度

c:倒排索引中match ngram出现的最大次数。
m:表示单个文档中提取match ngram小于c的平均文档数
D:输入的文档数
系统生成的候选文档数最大为:\(xD*c*m\),针对候选文档,我们需要计算pair score(score n-gram点积),假设score ngram格式为s。最终的复杂度为\(O(D*m*c*s)\)

句子级别对齐

是用动态规划句子对齐算法,以句子长度和多语言概率字典,对每个句子进一步过滤。粗略的对齐source target句子单词。这种粗略的对齐只用于过滤不平行的句子。

p(s,t),p(s),p(t)都是单词对齐语料库中的经验分布(统计),结果除以近似期望值

丢弃了实际得分与期望得分之比小于1/3的句子

参数选择

不同score ngram比较
不同match ngram下pairwise比较次数

End

本文标题:google-平行文档挖掘(n-gram)

本文链接:https://www.tzer.top/archives/464.html

除非另有说明,本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议

声明:转载请注明文章来源。

最后修改:2022 年 05 月 18 日
如果觉得我的文章对你有用,请随意赞赏