Learning Optimal Policy for Simultaneous Machine Translation via Binary Search (2023)

Abstract: Simultaneous machine translation (SiMT) starts to output translation while reading the source sentence and needs a precise policy to decide when to output the generated translation. Therefore, the policy determines the number of source tokens read during the translation of each target token. However, it is difficult to learn a precise translation policy to achieve good latency-quality trade-offs, because there is no golden policy corresponding to parallel sentences as explicit supervision. In this paper, we present a new method for constructing the optimal policy online via binary search. By employing explicit supervision, our approach enables the SiMT model to learn the optimal policy, which can guide the model in completing the translation during inference. Experiments on four translation tasks show that our method can exceed strong baselines across all latency scenarios.

## introduction simultaneous machine translation (simt) @xcite @xcite @xcite , which outputs the generated translation before reading the whole source sentence, is applicable to many realtime scenarios, such as live broadcast and real-time subtitles. to achieve the goal of high translation quality and low latency @xcite , the simt model relies on a policy that determines the number of source tokens to read during the translation of each target token. the translation policy plays a pivotal role in determining the performance of simt, as an imprecise policy can lead to degraded translation quality or introduce unnecessary delays, resulting in poor translation performance @xcite . therefore, it is crucial to establish an optimal policy that achieves good latency-quality trade-offs. however, the absence of a golden policy between the source and target makes it challenging for the simt model to acquire the explicit supervision required for learning the optimal policy. according to @xcite , the simt model will learn better policy if it is trained with external supervision. consequently, by constructing the optimal policy between the source and target, we can train the simt model, which will then generate translations based on the learned policy during inference. however, the existing methods, including fixed policy and adaptive policy, have limitations in learning the optimal policy due to the lack of appropriate explicit supervision. for fixed policy @xcite @xcite , the model relies on heuristic rules to generate translations. however, these rules may not prompt the simt model to output the generated translation immediately, even when there is sufficient source information to translate the current target token. consequently, the fixed policy often cannot achieve good latency-quality tradeoffs because of its rigid rules. for adaptive policy @xcite @xcite , the model can dynamically determine its policy based on the translation status, leading to improved performance. nevertheless, precise policy learning without explicit supervision remains challenging. some methods @xcite attempt to construct learning labels for the policy offline by introducing external information. but the constructed labels for policy learning cannot guarantee that they are also optimal for the translation model. under these grounds, our goal is to search for an optimal policy through self-learning during training, eliminating the need for external supervision. subsequently, this optimal policy can be employed to guide policy decisions during inference. in simt, increasing the number of source tokens read improves translation quality but also leads to higher latency @xcite . however, as the length of the read-in source sequence grows, the profit of translation quality brought by reading more source tokens will also hit bottlenecks @xcite . therefore, the gain of reading one source token can be evaluated with the ratio of the improvement in translation quality to the corresponding increase in latency. the optimal policy will make sure that every decision of reading or writing will get the greatest gain. in this way, after translating the whole source sequence, the simt can get the greatest gain, thereby achieving good latency-quality trade-offs. in this paper, we propose a simt method based on binary search (bs-simt), which leverages binary search to construct the optimal translation policy online and then performs policy learning accordingly. specifically, bs-simt model consists of a translation model and an agent responsible for policy decisions during inference. to construct the optimal policy, the translation model treats potential source positions as search interval and selects the next search interval by evaluating the concavity in binary search. this selection process effectively identifies the interval with the highest gain, thus enabling the construction of an optimal policy that ensures good performance. subsequently, the constructed policy is used to train the agent, which determines whether the current source information is sufficient to translate the target token during inference. if the current source information is deemed sufficient, the translation model outputs the generated translation; otherwise, it waits for the required source tokens. experiments on de↔en and en↔vi translation tasks show that our method can exceed strong baselines under all latency. ## background for simt task, the model incrementally reads the source sentence @xmath0, ..., x j ) with length j and generates translation @xmath1, ..., y i ) with length i according to a policy. to define the policy, we introduce the concept of the number of source tokens read when translating target token y i , denoted as g i . then the translation policy can be formalized as @xmath2, ..., g i ). the probability of translating target token y i is p θ (y i |@xmath3, @xmath4, where @xmath5, @xmath6. consequently, the simt model can be optimized by minimizing the cross-entropy loss: wait-k policy for wait-k policy @xcite , which is the most widely used fixed policy, the model initially reads k source tokens and subsequently outputs and reads one token alternately. therefore, g i is represented as: multi-path to avoid the recalculation of the encoder hidden states every time a source token is read, multi-path @xcite introduces a unidirectional encoder to make each source token only attend to preceding tokens. furthermore, during training, the model can be trained under various by sampling latency k uniformly: ## preliminary analysis in this section, we explore the influence of the number of read-in source tokens on translation quality. we employ the multi-path translation model (elbayad et al., 2020) and select a bucket of samples from the iwslt14 @xmath7, consisting of 295 sentences with the same target length @xcite . to analyze the variations, we utilize the probability of translating the groundtruth token as a measure of translation quality. for each relative source position q, we compute the probability p q i of translating the ground-truth y ⋆ i : ## the proposed method our bs-simt model contains two components: the translation model and the agent. the transla-tion model, which is fine-tuned from the multi-path model, employs binary search to iteratively select the next interval with the highest gain. this process allows the model to search for the optimal policy and subsequently train itself based on the searched policy. subsequently, we utilize the bestperforming translation model to construct the optimal policy, which serves as explicit supervision for training the agent. during inference, the agent guides the translation model to generate translations with good latency-quality trade-offs. the details are introduced in the following sections. ## analysis to gain insights into the improvements achieved by our method, we conduct extensive analyses. understanding of our method. ## related work recent simt methods can be roughly divided into two categories: fixed policy and adaptive policy. for fixed policy, the model relies on predefined heuristic rules to generate translations. @xcite proposed static-rw, which reads and writes rw tokens alternately after reading s tokens. @xcite proposed wait-k policy, which writes and reads a token alternately after reading k tokens. @xcite introduced the unidirectional encoder and enhanced wait-k policy by uniformly sampling latency k during training. @xcite proposed future-guided training to help simt model invisibly embed future source information through knowledge distillation. @xcite proposed char-level wait-k policy to make the simt model adapt to the streaming input environment. @xcite proposed moe wait-k policy, which makes different heads execute different wait-k policies, and combine the results under multiple latency settings to predict the target tokens. for adaptive policy, the translation policy is determined based on current translation status. @xcite trained the agent for policy decisions using reinforcement learning. zheng et al. (2019) trained the agent with optimal action sequences generated by heuristic rules. arivazhagan et al. (2019) proposed milk, which applies the monotonic attention and determines the policy based on a bernoulli variable. ma et al. (2020) proposed mma, which implements milk on transformer architecture and achieves superior performance in simt. zhang et al. (2020) proposed mu, which is an adaptive segmentation policy @xcite . @xcite used a full-sentence model to construct the translation policy offline, which can be used to train the agent. @xcite implemented the adaptive policy by predicting the aligned source positions of each target token directly. @xcite introduced dual constraints to make forward and backward models provide path supervision for each other. @xcite proposed the wait-info policy to balance source and target at the information level. @xcite performed the adaptive policy by integrating post-evaluation into the fixed policy. @xcite proposed hidden markov transformer, which models simultaneous machine translation as a hidden markov process. the previous methods often lack explicit supervision for the learning of the policy. some papers use external information, such as generated heuristic sequences, to learn the policy @xcite @xcite . however, their methods heavily rely on heuristic rules and offline reference sequence construction, which affects the translation performance. our bs-simt constructs the optimal translation policy online by checking the concavity via binary search without utilizing external information, thereby obtaining good latency-quality trade-offs. ## conclusion in this paper, we propose bs-simt, which utilizes binary search to construct the optimal translation policy online, providing explicit supervision for the agent to learn the optimal policy. the learned policy effectively guides the translation model in generating translations during inference. experiments and extensive analyses show that our method can exceed strong baselines under all latency and learn a translation policy with good trade-offs.