Fast Lexically Constrained Decoding with Dynamic Beam Allocation for Neural Machine Translation
Matt Post, David Vilar
cs.CL
2018-04-18
DBA 把受限解码复杂度从随约束个数线性/指数增长压到无关,英德翻译里不管塞多少约束都约 0.6 秒一句,BLEU 还略优于网格束搜索。
神经机器翻译端到端训练,好处是全自动,代价是你几乎没法手动干预输出。老的统计翻译时代,塞一本领域词典、强制某个词翻成特定译法,是常规操作;到了神经网络这里,这些手动干预基本都被砍掉了。
受限解码(lexically constrained decoding)是把其中一根杠杆接回来的办法:你在解码时指定一批目标词或短语,模型输出里必须包含它们。问题是已有的两套算法都贵。Hokamp 和 Liu 的网格束搜索(grid beam search,GBS)复杂度随约束个数线性增长;Anderson 等人的受限束搜索(CBS)是指数增长。约束一多就跑不动,而且它们把束搜索的结构改得面目全非,很难再和批量解码这些提速手段配合。
DBA(Dynamic Beam Allocation,动态束分配)的核心思路是把 GBS 的「乘」换成「除」。GBS 给每个约束完成状态预留一个独立的小束,所以总束长是 k 乘以状态数,约束越多束越宽。DBA 保持一个固定大小 k 的束,每一步动态决定把这几个名额切给哪个状态。
具体说,它把候选分成几个「银行」(bank),每个银行对应「已经满足了几个约束」这个状态。每一步从三类候选里收:全体 token 里的 top-k、所有还没满足的约束(保证进度往前走)、以及每条假设的单最优 token(保住半成品)。然后一个分配函数决定每个银行这步拿几个名额,下一步再根据实际情况重新分配。这套操作让复杂度掉到 O(Nk),和约束个数无关。
关键的一招是「银行调整」:它让 DBA 在约束个数 C 超过束宽 k 的时候照样能工作,而 GBS 在这种情况下直接失效。
实验在英德翻译上做,WMT'17 训练,4 层 RNN,解码框架是 Sockeye。测试集约 2737 句。
速度上差别一目了然。GBS 的每句耗时随约束个数线性上升,DBA 是一条几乎水平的线。在 Tesla V100 上,DBA(k=10)不管塞多少约束都是约 0.6 秒一句,大约只有无约束解码的 3 倍开销(K80 上约 1.4 秒)。
质量上 DBA 也不输。无约束基线(k=10)BLEU 22.3,DBA(k=10)做到 26.7,(k=20)做到 27.2。和 GBS 公平比:把 GBS 的基础束设成 1(约束多时束宽也到 10 以上),它的 BLEU 是 25.6,DBA 用同样的运行时间、还是固定束宽,拿到 26.7。
| 设置 | BLEU | 备注 |
| 无约束 (k=10) | 22.3 | 基线 |
| DBA (k=10) | 26.7 | 固定束,耗时与约束数无关 |
| DBA (k=20) | 27.2 | |
| GBS 基础束=1 (k≥10) | 25.6 | 同运行时间 |
作者还验证约束词是被放对了位置,而不是仅仅因为出现在句子里抬高了 n-gram 计数:约束首词在参考译文和实际输出里的位置相关系数达到 0.82,而且全程没用任何源端词对齐信息。
这篇 2018 年的论文当时是为机器翻译写的,但它解决的那个底层问题,今天在智能体场景里又热了起来。让大模型在解码时强制吐出指定 token、指定格式,正是今天函数调用、结构化输出(JSON schema)、工具调用的技术底座,统称受引导生成(guided generation)。这篇给出的关键结论是:受约束越多解码越慢这件事可以被打掉,复杂度能做到和约束个数无关。
作者顺带揭了一个翻译圈的老问题:模型打分和 BLEU 不是一回事。把约束从无到有逐渐加满,模型的似然分数越来越差(对数概率从 −1039 一路掉到参考译文的 −4396),BLEU 却越来越好(22.3 涨到 95.9)。模型觉得不太可能的句子,反而翻译质量更高。这说明拿困惑度当翻译质量的代理指标是有水分的。
实验只在英德这一对语言上做了,主实验用的还是 RNN,作者承认只是声明代码对 Transformer「无需修改就能跑」,并没有给出 Transformer 的实测数字。约束个数相对于束宽不能太大,否则质量下降,他们自己指出正确摆放多个独立约束本身是个指数难度的排列问题。文里还描述了一个解码器通病:被强行逼进低概率区后,解码器会在束的低位持续生成无意义文本,只有靠剪枝才压得住。