Non-Parametric Online Learning from Human Feedback for Neural Machine Translation

We study the problem of online learning with human feedback in the human-in-the-loop machine translation, in which the human translators revise the machine-generated translations and then the corrected translations are used to improve the neural machine translation (NMT) system. However, previous methods require online model updating or additional translation memory networks to achieve high-quality performance, making them inflexible and inefficient in practice. In this paper, we propose a novel non-parametric online learning method without changing the model structure. This approach introduces two k-nearest-neighbor (knn) modules: one module memorizes the human feedback, which is the correct sentences provided by human translators, while the other balances the usage of the history human feedback and original NMT models adaptively. Experiments conducted on EMEA and JRC-Acquis benchmarks demonstrate that our proposed method obtains substantial improvements on translation accuracy and achieves better adaptation performance with less repeating human correction operations.


Introduction
The quality of the neural machine translation (NMT) system has been significantly improved recently (Sennrich, Haddow, and Birch 2016a;Vaswani et al. 2017;Zhang et al. 2018b;Hassan et al. 2018). However, recent research has shown that machine translation still lags behind human parity on translation quality (Läubli, Sennrich, and Volk 2018;Freitag et al. 2021). In some scenarios where highquality translation should be guaranteed, human-in-the-loop machine translation, i.e., machine translation with human post-editing, is still indispensable. As human corrections on machine-translated text are constantly produced, adapting the NMT model to these corrections could improve translation quality and effectively reduce human efforts, as shown in Figure 1. However, the training of NMT models requires a certain amount of data and consumes dozens or hundreds of GPU hours, which is unavailable in this scenario. Therefore, online learning from human feedback at a low training cost has become a promising research topic in recent years.
A series of studies (Turchi et al. 2017;Kothur, Knowles, and Koehn 2018) propose to on-the-fly update the NMT Figure 1: The workflow of online learning from human feedback in the human-in-the-loop machine translation. Given the source sentence SRC, the NMT System generates the translation MT. The user corrects it and produces PE. Then the corrected sample is used to adapt the NMT system. model right after humans correct the translation. Although these methods improve translation performance, they require extra costs for frequent gradient computations at the inference time. Tuning parameters only on the new-coming sentences also brings the risk of catastrophic forgetting problems. Another research line (Gu et al. 2018;Zhang et al. 2018a) augments the NMT model with the translation memory to cache the human-corrected sentences. For each sentence to translate, cached sentences with similar context are retrieved to help the decoding process of the NMT model. Memory-augmented NMT avoids updating parameters onthe-fly, but it requires careful network architecture design to model the retrieved translation memories. Also, extra training overhead is inevitable to optimize the memory network.
Recently, Khandelwal et al. (2020) proposed KNN-MT, a non-parametric and model-agnostic method for domain adaptation. It equips the pre-trained NMT model with a knearest-neighbor classifier over a datastore of cached context representations and corresponding target tokens. The final translation probability is the interpolation between the probability calculated by the NMT model and the KNN module. KNN-MT provides a simple but effective way to exploit human feedback by adding human-corrected translations into the datastore. However, the success of KNN-MT is owed to enough in-domain samples pre-cached in the datastore. In the human-in-the-loop translation, to learn the cor-rected translation, human translators have to make repetitive corrections on the same mistake to provide enough samples for KNN-MT. Biasing the interpolation to the KNN module could accelerate this learning process, but it takes the risk of being interfered by the noise in retrieved neighbors when retrieved items are not relevant enough. Therefore, it is crucial to balance the usage of the probability from the NMT model and the KNN module when applying KNN-MT.
In this paper, we propose KNN-over-KNN (KoK), a plugand-play non-parametric approach for online learning from human feedback. KoK equips the NMT model with two KNN modules, Token-KNN and Policy-KNN. Token-KNN is used to model the translation probability as in KNN-MT. Human-corrected sentences are incrementally added to the datastore of Token-KNN to improve the translation quality of proceeding sentences. Policy-KNN is introduced to model the balance mechanism between the Token-KNN module and the NMT model. It interpolates between the two modules with a Bernoulli distribution. The distribution is estimated by a k-nearest-neighbor classifier over a datastore. For building the datastore, we extract features from the retrieval results of Token-KNN as the key, and heuristically induce a binary flag for each result as the value (1 means using this result and vice versa).
We conduct experiments on translating domain-specific documents with various lengths. Oracle references are used to mimic human feedback. KoK obtains significant improvements (up to 12.9 BLEU improvement and 9.7 TER reduction) compared to the Pre-Trained NMT model. KoK also achieves consistent improvements over existing online learning methods on documents at all lengths. We further show that KoK can adapt to human feedback with less repeated corrections, which reduces human effort. Our code is open-sourced at https://github.com/wangqi1996/KoK.

Background Neural Machine translation
Neural machine translation systems formulate the translation task as a conditional probability model p(y|x), which defines the translation process from source sentence x = {x 1 , x 2 , ..., x m } into target sentence y = {y 1 , y 2 , ..., y n }. The representative works decompose it in an auto-regressive manner from left to right : where y <t = {y 1 , y 2 , ..., y t−1 } denotes the prefix tokens. Then the probability of each target token is defined as: where h t is the representation for context (x, y <t ), and W , b are the trainable parameters to mapping the dimension of h t to the vocab size.

Online Learning from Human Feedback
In the human-in-the-loop translation, a complete translation step is: the NMT model generates machine-translated text, and then the human translator makes revisions on it (human feedback). Online Learning from human feedback follows such a paradigm: after the human completes the revision of the current sentence, the machine translation system is adapted incrementally by taking this sample into account. Concretely, given a document D = {x 1 , x 2 , .., x |D| }, where x i represents i th sentence, the translation for x i is generated asŷ is the NMT model adapted by x <i sentences and f 0 is the pre-trained model. The human translator correctsŷ i , and then produces the reference y i . The model f i is acquired by adapting f i−1 over the new sample (x i , y i ): The adaptation process could be tuning the model parameters, or updating the external translation memory. In the rest of the paper, we omit the superscript i for simplicity.

KNN-MT
Recently, Khandelwal et al. (2020) proposed KNN-MT, a non-parametric method. It augments the NMT model with a token-level k-nearest-neighbor retrieval mechanism, allowing it to directly access the cached examples stored in the datastore during inference. It consists of two steps: datastore construction and inference.

Datastore Construction
The datastore consists of a set of key-value pairs. More specifically, given the parallel sentence in the dataset (x, y) ∈ (X , Y), the pre-trained NMT model generates the context representation h t as Equation 1 at every timestep t, then the datastore takes the h t as the key and the corresponding target tokens y t as the value: (K, V) = {(h t , y t ), ∀y t ∈ y|(x, y) ∈ (X , Y)}. Inference The inference process performs in a token-bytoken manner. Given the source sentence x and the generated target prefixŷ <t , the pre-trained NMT model generates the representationĥ t and then predicts a probability p NMT (ŷ t |x,ŷ <t ) for the target tokenŷ t .
Then, the k-nearest-neighbor model retrieves the similar K neighbours R = {(k i , v i ), i ∈ {1, 2, ..., K}} in the datastore according to Euclidean distance toĥ t . The retrieved result is converted into a distribution over the vocabulary by where d(k i ,ĥ t ) represents the Euclidean distance between k i andĥ t , p(k i |ĥ t ) is the probability of i th retrieval neighbor (k i , v i ). T is a hyper-parameter to control the sharpness of the softmax function. The final output distribution is an interpolation between distributions from the NMT model and the KNN retrieved neighbors with a tuned parameter λ ∈ [0, 1] p(ŷ t |x,ŷ <t ) = λ * p KNN (ŷ t |x,ŷ <t )

Amoxil is an
Amasilin is an antibiotic.
Amoxil is an antibiotic.
value key Amoxil antibiotic … Amasilin ist ein Antibiotikum. Amoxil is an antibiotic xŷ t y <t Figure 2: An illustration of proposed KoK.

Proposed Method
In this section, we describe the proposed method, KNNover-KNN (KoK). Based on KNN-MT, we model a balance mechanism between the usage of the pre-trained NMT model and the KNN module cached history human corrections, i.e., we replace the fixed λ in Equation 3 into a dynamic λ t varies at each predictingŷ t : KoK learns to predict p KNN and λ t from history human feedback in a non-parametric way, and can be applied to NMT models with various architectures.
Architecture Figure 2 shows the overall architecture of KoK. It parameterizes the final translation probability (Equation 4) with two KNN modules besides the pre-trained NMT model, in which the Token-KNN module predicts the probability p KNN over target words and the Policy-KNN module predicts an interpolation coefficient λ t . During the translation process of one sentence, for each decoding step t, Token-KNN takes the hidden representation h t as query and retrieves from its datastore to generate the translation probability p KNN . Then features extracted from the retrieval result of Token-KNN are used as the query of Policy-KNN to calculate the λ t value. The final translation probability (Equation 4) is computed as an interpolation between p KNN and p NMT with λ t .

Token-KNN
Token-KNN module predicts the translation probability p KNN with k-nearest-neighbor classifier over the datastore. It is similar to the KNN module in the KNN-MT, but the datastore is built incrementally. During the translation process, with theĥ t as the query, the Token-KNN queries from the token datastore. The translation probability is computed as Equation 2. During the adaptation process, given source sentence x and its human-corrected translation y, we build the key-values pairs and then store them into the datastore.

Policy-KNN
Policy-KNN module calculates the λ t , which expresses the balance mechanism between the usage of the pre-trained NMT model and the Token-KNN module. We introduce a random variable λ which obeys the Bernoulli distribution. λ = 1 represents to use the translation probability of Token-KNN and vice versa for the NMT model. Thus, predicting coefficient λ t in Equation 4 is demonstrated as estimating the conditional probability p(λ = 1|x, y <t ) Policy-KNN estimates this probability with k-nearestneighbor classifier over the datastore as well. In the following, we will describe in detail the datastore construction and inference process of Policy-KNN. At the t th decoding step, we denote the retrieval results from Token-KNN as Zheng et al. (2021a), we construct the key vector s t using two kinds of features extracted from the retrieval results of Token-KNN. One feature is the distance, we denote the Euclidean distance between the context rep- The other feature is the counts of distinct values for all retrieval results, marked as c i . Specially, c i is computed as: where UNIQUE represents the unique elements in the list. s t is constructed by concatenating all the features: Intuitively speaking, the distance features d i stand for similarity, which directly evaluates the importance of each retrieval result. The count features c i represents the consistency of retrieval results, as more distinct retrieved values mean less credible KNN retrieval. Both of these two features are crucial for predicting an optimal value of λ.
We further re-weight the key vector according to the significance of each element. We adopt exponential reweighting on distance features and count features, respectively: Value The retrieval result of Token-KNN does not explicitly come with a golden value of λ indicating whether to use this result or not. Instead, we implicitly induce the value of λ through a simple heuristic: where x and y is the source sentence and its humancorrected translation, respectively.
This heuristic is actually mathematically meaningful. To find the value of λ t to maximize the probability of KNN-MT (Equation 4), we need to solve the optimization problem below: Inference During the translation process, at the t th decoding step, given the retrieval result R tok t of Token-KNN, we build the query featureŝ t as in Equation 6, then Policy- .., K}}, from its datastore. The retrieval result λ t is calculated by: The final translation probability is calculated as Equation 4.

Implementation
Overall, KoK is performed as an online learning paradigm. It takes three steps when translating a source sentence x:

Experiments Experimental Setup
We evaluate the proposed method by equipping the generaldomain pre-trained NMT model with KoK and use it to translated in-domain documents with various document sizes. We use the oracle reference as the human-corrected translations to simulate the real human-in-the-loop scenario.  (Tiedemann 2009), which consists of sentencealigned documents focusing on medical products.
(2) JRC-Acquis corpus (Steinberger et al. 2006), which contains the European Union laws applicable to the EU member states.
Following common practices, we use the Moses toolkit 2 to tokenize the documents, remove the same sentences in a document and then segment the words into subword units (Sennrich, Haddow, and Birch 2016b) with the bpecodes provided by the pre-trained model. We validate our method on documents with various lengths. Specifically, we divide the documents into five buckets based on their length (0-50, 50-100, 100-200, 200-500 and 500-1000). We randomly select some documents so that the total document length of each bucket is upper than 1000. Detailed for EMEA/JRC dataset statistics are shown in Table 1 (2018), we train the model 5 steps on every single sentence with the adam optimizer. The hyper-parameters setting follows the pretrained models, except the learning rate is set to 1.0 × 10 −7 and fixed during the inference process. • KNN-MT: After every sentence is translated, we add the human-corrected sentences to the datastore of KNN-MT. Similar to our method, the K is 8. The λ value for the EMEA dataset and the JRC-Acquis dataset are 0.2 and 0.3, respectively. • Adaptive KNN-MT (Zheng et al. 2021a): A variant of KNN-MT, which introduces a network to dynamically determine the number of K for each target token. We use the model pre-trained on the IT domain (provided by the paper) and incrementally update the datastore as in the KNN-MT.
Evaluation. We use SacreBLEU 5 (Post 2018) to measure the result with case-sensitive detokenized BLEU (Papineni et al. 2002). We concatenate the translations of all the documents in each bucket and calculate the corpus-level BLEU. For the completeness of the results, we also report the TER (Snover et al. 2006) metric to compute the edit distance between the reference and system translation.

Main Results
We can see that consistent improvements (up to 12.9 BLEU improvement and 9.7 TER reduction) are achieved by KoK on different document lengths. As a comparison, Online Tuning achieves relatively minor improvement on long documents, probably because that several thousand samples are still not enough for a gradient-based approach. KNN-MT fails to attain similar improvements as KoK on long documents because of the small but fixed λ value. This indicates the benefit of adjusting λ adaptively. Instead, the per-5 https://github.com/mjpost/sacrebleu formance of adaptive KNN-MT deteriorates when the length of a document is relatively small. As the training of the adaptive KNN-MT is based on a static datastore built from all indomain training data, it is not compatible with the human-inthe-loop machine translation scenario that the human feedback comes in a streaming way. Overall, the results demonstrate the effectiveness and generalization of our method on different document conditions. We also conduct experiments on the JRC-Acquis dataset, which contains documents related to the law domain. All the results are listed in Table 3. KoK consistently outperforms all the baselines, which demonstrates that our approach can be generalized to other domains. We show the performance on the full test sets in Appendix.

Comparing With Translation Memory
We also compare our method with the NMT model augmented by the translation memory (TM-NMT) (Kuang et al. 2020;Bapna and Firat 2019). Due to the training data of the WMT19 NMT model is unavailable, we implement the TM-NMT model and the NMT model of KoK on the WMT14 DE-EN dataset for a fair comparison, and evaluate them on the EMEA dataset. For the NMT model, we use the transformer big architecture, and the training detail follows the introduction of fairseq 6 . For the TM-NMT, we follow the source similarity method in Cai et al. (2021), and the architecture is the same as the transformer big model.
The result is illustrated in Table 4. As seen, KoK still achieves improvements on all the document sizes. However, TM-NMT fails to exceed the pretrained NMT model except on the 200-500 bucket, which may be resulted from the inability to handle the low quality of retrieval memories (Cai et al. 2021).   Table 5: Decoding latency of different models on the EMEA dataset. We also list the speedup w.r.t the pre-trained NMT model.

Latency
In the human-in-the-loop translation scenario, human translators are sensitive to decoding latency. Therefore, we also evaluate the latency of the proposed KoK. We simulate the Computer Aided Translation(CAT) task setting and measure the decoding latency sentence-by-sentence 7 . The latency is calculated on the EMEA dataset, and we report the average latency in milliseconds. The speed-up ratio is also computed by comparing it with the Pre-Train Model following the previous practice (Zheng et al. 2021a). The result is summarized in Table 5. Our method slightly slows down the inference time, but significantly improves translation quality, which is tolerable for users.

Analysis
In this section, we perform several analyses and ablation studies for the proposed KoK.

Can KoK Learn Optimal λ
KoK equips KNN-MT with a Policy-KNN to adaptively decide between adopting knowledge from human feedback or keeping decoding results from the pre-trained NMT model on every token. In this section, we demonstrate that KoK indeed learns an optimal policy to make the decision. We first compare KoK with KNN-MT which chooses different λ values. The results are shown in Figure 3. We try λ ∈ [0.0, 1.0) with 0.1 as the step size, and report average BLEU scores on the various document length buckets on the EMEA dataset. KNN-MT is sensitive to the choice of λ value (BLEU varies from 18 to 43), which indicates the importance of selecting a proper λ value. KNN-MT achieves the best performance when λ is around 0.2, but still lags behind KoK. This experiment shows that it is crucial to decide the λ value token-by-token adaptively. 7 The latency is measured on a single GeForce GTX 1080-Ti GPU.
We further evaluate whether KoK could learn an optimal λ. Given oracle target y, for each y t ∈ y, we compute the Token-KNN probability of y t as p knn (y t ), and the corresponding λ t predicted by Policy-KNN. To show the relationship between λ t and p knn (y t ), we divide all the Token-KNN probability values into five buckets and compute the average λ values in every bucket. The result is shown in Figure 4. As seen, the λ value becomes high when the Token-KNN probability gets bigger, and vice versa. This is in line with the motivation that KoK should bias to the usage of Token-KNN probability when retrieved human feedbacks indeed help the translation. We also evaluate the effectiveness of K in the Appendix.

Zero-Shot and Few-Shot Ability of KoK
In machine translation with the human-in-the-loop scenario, users not only care about the quality of the translation model, but also care about how fast the model can learn from their feedback to avoid repeatedly making the same mistakes they already corrected before. Therefore, in this section, we evaluate the adaptation speed of KoK to user feedback.
We follow the R-indicator used in Simianer, Wuebker, and DeNero (2019), which measures the translation recall of words with different occurrence times in users' feedback. We denote R i as the recall of tokens that have appeared i times in the previous corrected sentences: where H j represents unique words in the j th machinegenerated translation and R i,j represents unique words in the j th reference that are their (i + 1) th occurrence in the whole document. Specifically, R 0 evaluates the tokens that first appear in the translating document and R 1 considers those that have appeared once.
We conduct experiments on documents with [200, 500] bucket from EMEA. R 0 , R 1 , R 2∼5 , R 5∼9 and R 9+ are computed for KoK and other baselines as Equation 9 respectively (R m∼n is defined as the micro average of R m , R m+1 , ..., R n ). The results are shown in Figure 5. KoK achieves the comparable R 0 , but the R i values improve quickly and outperform all the other methods. It indicates KoK's ability to reduce interference from unrelated retrieval results of Token-KNN, and to adapt to helpful human feedback faster. Adaptive KNN-MT achieves a lower R 0 , which may due to the same reason about worse performance in main experiments.   Figure 4: Average λ in different ranges of reference Token-KNN probability. We compute the Token-KNN probability and its corresponding λ value by Policy-KNN for each words in the reference.

Related Work
Online Learning from Human Feedback. Online updating (Álvaro Peris and Casacuberta 2019; Turchi et al. 2017;Weng et al. 2019) the NMT model has been proved to be an effective and efficient method to adapt the model to the target domain. Kothur, Knowles, and Koehn (2018) proposed the single-sentence adaptation, which performed online adaptation one sentence at a time. Simultaneously, they introduced the dictionary adaptation to address the problem of translating novel words. Karimova, Simianer, and Riezler (2018); Domingo et al. (2019bDomingo et al. ( , 2020 presented a user study to prove the advantages of online adaptation. Domingo et al. (2019a) applied online adaptation technology in a production environment. Mueller and Lal (2019) proposed to finetune the model over a subset of similar sentences extracted from the training set. However, these methods require updating the model frequently, which brings a non-negligible computation cost in the human-in-the-loop translation scenario, and is prone to catastrophic forgetting problems.
1 Figure 5: Results on documents with [200, 500] bucket from EMEA dataset for the proposed R-indicator.
(2018) proposed to retrieve samples similar to the source sentence and then encoded retrieved source-target pairs using key-value memory networks. Cai et al. (2021) proposed to store the target-language sentence in the memory and used a cross-lingual retrieval model. Cao and Xiong (2018) Khandelwal et al. (2020) generated the translation with the nearest neighbor classifier over a large datastore of cached examples. Zheng et al. (2021a) proposed to dynamically determine the number of K for each target token. Zheng et al. (2021b) further extended the capability of KNN-MT on unsupervised domain adaptation setting.

Conclusion
In this paper, we propose KNN-over-KNN (KoK), a plugand-play non-parametric method for online learning from human feedback. KoK introduces two KNN modules, one to memorize the corrected sentences by the human and the other to balance the importance of the in-domain corrected sentences and the general-domain pretrain NMT model. In the experiments, our method significantly improves the performance and achieves better performance than state-of-theart baselines on one-shot or few-shot learning for domainspecific lexical items. As KoK achieves competitive performance compared with existing online learning methods, applying our approach to other generation tasks is a promising direction for future work.

The Creating/Updating Process of Datastore
At the beginning of the inference process, the datastore is empty. For each source sentence x and the human corrected sentence y, the adaptation process is: • The pre-trained model generates the hidden representation h by teacher forcing. • With h as the query, the retrieval result of Token-KNN is R tok . • The items for the datastore of Policy-KNN are extracted from R tok as described in the subsection Policy-KNN in page 3. • The items for the datastore of Token-KNN are h and the corresponding target token y. • These items are added into the datastores of Token-KNN and Policy-KNN respectively.
The KNN models are non-parametric and don't need pretraining. We will make it clearer in the next version.

The Performance on The Full Test Sets
We calculate the average BLEU score over the buckets in the main paper, and re-calculate the BLEU scores on the full test sets. The scores are listed in Table 1. We will add these results in the next version.