Title: DUAL LEARNING: THEORETICAL STUDY AND ALGORITHMIC EXTENSIONS

Abstract: Dual learning has been successfully applied in many machine learning applications including machine translation, image-to-image transformation, etc. The high-level idea of dual learning is very intuitive: if we map an x from one domain to another and then map it back, we should recover the original x. Although its effectiveness has been empirically verified, theoretical understanding of dual learning is still missing. In this paper, we conduct a theoretical study to understand why and when dual learning can improve a mapping function. Based on the theoretical discoveries, we extend dual learning by introducing more related mappings and propose highly symmetric frameworks, cycle dual learning and multipath dual learning, in both of which we can leverage the feedback signals from additional domains to improve the qualities of the mappings. We prove that both cycle dual learning and multipath dual learning can boost the performance of standard dual learning under mild conditions. Experiments on WMT 14 English↔German and MultiUN English↔French translations verify our theoretical findings on dual learning, and the results on the translations among English, French, and Spanish of MultiUN demonstrate the efficacy of cycle dual learning and multipath dual learning.

1. INTRODUCTION:

Most machine learning tasks can be formulated as learning a mapping from one domain to another one, like image classification (from image to label), neural machine translation (from source language to target language), speech recognition (from voice to text), etc. Among them, quite a few tasks are of dual forms, like image classification v.s. image generation (from label to image), the neural machine translation between two languages (English→French v.s. French→English), speech recognition v.s. speech synthesis (from text to voice), etc. Such duality can be utilized to improve the model qualities.

One prominent framework is dual learning, first proposed by He et al. (2016) for machine translation and then applied to many other applications like image translation (Kim et al., 2017; Zhu et al., 2017) , question answering and generation (Tang et al., 2017) , etc. In dual learning, two mapping functions between two domains are trained simultaneously so that one function is close to the inverse of the other. The intuition is that, if we translate a sentence from English to French and then translate the obtained French sentence back to English, we should get the same sentence or a very simlar one.

Dual learning is of great interest because it can accommodate any unidirectional architecture, e.g. a transformer (Vaswani et al., 2017) , and provide a performance boost. Moreover, dual learning can be used in semi-supervised learning, which is highly desirable since deep neural networks are generally thirst for labeled data.

Despite of the empirical success of dual learning, the theoretical understanding is largely missing. In this paper, we conduct both theoretical analyses and empirical studies to answer the following questions: Q1: Why and when does dual learning improve a mapping function? Q2: Can we further improve the performance of a mapping function?

1.1 OUR CONTRIBUTIONS Our contributions are in two folds: a theoretical study of dual learning and the frameworks of cycle dual learning and multipath dual learning, which subsume dual learning as a special case. Without loss of generality, we take machine translation as the example for the study and algorithm presentation.

Dual learning. We take a novel statistical approach to model the problem. Suppose there are two baseline translators between two language spaces, one forward and one backward. Based on our Theorem 1, dual learning outperforms both baseline translators as long as the baseline translators are better than random mappings under natural assumptions. Empirical studies show that an improvement is observed even if the reconstruction is far from perfect.

Cycle dual learning and multipath dual learning. We propose cycle dual learning and multipath dual learning frameworks by extending dual learning. Both frameworks use dual learning as the basic building block and leverage a third, a fourth, or more languages to help boost the translator qualities between the original two languages. We prove that under mild conditions, the two symmetric frameworks outperform dual learning (Theorems 2 and 3). Our experiments on MultiUN dataset show a significant improvement (1.45 BLEU points, see Table 4 ) against dual learning.

1.2. RELATED WORK:

Dual learning was first proposed by He et al. (2016) in the context of machine translation, where the two dual translators are updated in a reinforcement learning manner with the reconstructed distortion as the feedback signal. A similar approach proposed by Cheng et al. (2016) has the same high-level idea but a very different implementation. Since then dual learning architectures have been proposed for other applications including image processing (Kim et al., 2017; Zhu et al., 2017) , sentiment analysis (Xia et al., 2017a) , image segmentation (Luo et al., 2017) , etc.

Built upon the dual learning framework, Xia et al. (2017b) and Wang et al. (2018) consider the joint distribution constraint, which says the joint distribution of sample over two domains is invariant when computing from either domain. We relax this constraint for simplicity of analysis. Xia et al. (2018) proposed model-level dual learning, which shares components between the primary direction and the dual direction. Dual learning was also leveraged for unsupervised learning (Lample et al., 2018; Artetxe et al., 2018) .

Despite the vast number of works related to dual learning, none of them explain why it works or when it fails. Galanti et al. (2018) claim that dual learning does not circumvent the alignment problem, where a sentence is translated wrong by the forward translator but translated back to it by the backward translator. We show that the alignment problem occurs with a small probability under dual learning compared to the baseline translator, and this probability can be further reduced by our cycle dual learning and multipath dual learning. Furthermore, their hypothesis that the translator should not be too complex is not verified in the context of machine translation.

2. PRELIMINARIES:

In this section, we introduce the notations and the essential assumptions used for theoretical analysis. A table summarizing the notations can be found in Appendix A. Let S 1 , . . . , S k be k language spaces, composed of sentences in each language. For any S i , we denote the distribution of sentences in S i by µ (i) and let X (i) be the random variable, i.e. Pr(X (i) = x) = µ (i) (x). For any x (i) ∈ S i , we denote the correct translation in S j by x (j) . In practice, we may select a threshold BLEU (Papineni et al., 2002a) score, above which the translation is considered correct. Let T ij denote the baseline translator that translates from a sentence in S i to one in S j , i.e. the desired mapping is T ij (x (i) ) = x (j) . When a random sentence x (i) is sampled from S i according to µ (i) , it is possible that this sentence is translated incorrectly. We use accuracy of the translator p ij , the accuracy of the translator, to describe the probability of translating a sentence correctly when this sentence is randomly sampled from S i according to µ (i) . Formally,

p ij = Pr x (i) ∼µ (i) (T ij (x (i) ) = x (j) ) = E x (i) ∼µ (i) [1 Tij (x (i) )=x (j) ] = x (i) ∈Si 1 Tij (x (i) )=x (j) µ (i) (x (i) )

, where 1 is the indicator function.

We sometimes omit the subscript x (i) ∼ µ (i) for simplicity. It is also easy to see that

EQUATION

In order to characterize reconstruction accuracy, we let X (j,r) denote the random variable that follows the distribution T ij (X (i) ) where X (i) ∼ µ (i) . We define µ (j,r) (x) = Pr(X (j,r) = x), and further define p r ji = Pr X (j,r) ∼µ (j,r) (T ji (x j) ). The superscript r means "reconstruction". The difference be- tween p r ji and p ji lies in the distributions of samples in space S j . We assume that T ij and T ji are independent translators. This is natural because T ij and T ji are usually trained independently. Then, for any j = i, we have

(j) ) = x (i) ) = E X (j,r) ∼µ (j,r) [1 Tji(x (j) )=x (i) ] = x (j) ∈Sj 1 Tji(x (j) )=x (i) µ (j,r) (x (

EQUATION

Further, we make the following assumption.

Assumption 1. For any j = i, any y

(j) ∈ S j , E[1 y (j) =x (j) ,Tij (x (i) )=y (j) ] = 1-pij m ,

where m is a constant.

The interpretation of this assumption is as follows. For all x (i) ∈ S i that are incorrectly translated into S j , there are m possibly incorrect translations (in S j ) with positive probabilities. Assumption 1 states that each of the incorrect translations is chosen uniformly at random. Justification of Assumption 1. It is generally not true in the real-world since the probabilities of different translations are usually very different. However, this assumption can be approximated by partitioning the possibly wrong translations into several clusters, where the probability of the translation falling into each cluster is close. The best case is that the incorrect translation with the largest probability p max is treated as one cluster. All the other possibly incorrect translations are clustered so that the probability of each cluster is close to p max . Then we have m ≤ 1-pij pmax . A small p max (a large m) is desirable. Note that the correct translation is indeed also a group of translations if we set a threshold BLEU score, above which the translation is considered correct.

To analyze the efficacy of dual learning, we consider the following two cases:

(Case 1)

T ji (T ij (x (i) )) = x (i) ; (Case 2) T ji (T ij (x (i) )) = x (i) .

Dual learning will detect Case 2 and train the translators so that Case 2 is minimized. We use superscript d for the translators trained from dual learning. For any given x i ∈ S i which fails in reconstruction (Case 2), we define

EQUATION

where "Case 2" denotes the condition T ji (T ij (x (i) )) = x (i) . Here α can be viewed as the probability of correcting the wrong translations by dual learning, β the probability of the occurrence of the alignment problem under Case 2, and γ the probability of nonzero reconstruction error. γ models the imperfectness of dual learning, which should be zero in the ideal case. It is easy to see α+β +γ = 1.

3. THEORETICAL STUDY:

In this section, we provide a theoretical study of why dual learning outperforms the baseline translatorby the following theorem. Theorem 1. Under Assumption 1, for any language spaces S i and S j , the accuracy of dual learning outcome

T d ij is p d ij = (1 -α)p ij p r ji + α(1 - (1-pij )(1-p r ji ) m

), where α is defined in equation 3.

This theorem is proved by explicitly computing the probabilities of each case. During dual learning, Case 2 is redistributed to α case (a desirable subcase of Case 1, defined in equation 3), β case (an undesirable but unavoidable subcase of Case 1, defined in equation 4), and γ case (remaining in Case 2, defined in equation 5). See Appendix B for the full proof. We have the following observations from Theorem 1.

Relation to the baseline translators. The accuracy is dual learning improvement is positively correlated to the baseline translators of both directions. The larger the p ij or p r ji is, the higher accuracy of T d ij dual learning can achieve. The role of m and α. When p ij , p r ji are fixed, a large m is desired for better accuracy. As α increases, the outcome of dual learning improves. In the optimistic (but maybe unrealistic) case where α = 1, β = γ = 0, we have

p d ij -p ij = 1 - (1-pij )(1-p r ji ) m -p ij = (1-pij )(m-1+p r ji ) m

. This means dual learning provides an improvement as long as m ≥ 1 and p r ji > 0, which is trivial. A hypothesis. We consider the case where the probabilities of redistribution to α case and β case are proportional to α and β. Formally, α β =

EQUATION

where

Γ = γ(1-p ij p r ji - (1-pij )(1-p r ji ) m

). To compare p d ij with the accuracy of the original translator, we compute the difference

p d ij -p ij =p ij ( mp r ji (1 -Γ) mp ij p r ji + (1 -p ij )(1 -p r ji ) -1) =p ij ( mp r ji mp ij p r ji + (1 -p ij )(1 -p r ji ) -1 - Γmp r ji mp ij p r ji + (1 -p ij )(1 -p r ji ) ) =p ij ( (1 -p ij )((m + 1)p r ji -1) mp ij p r ji + (1 -p ij )(1 -p r ji ) - Γmp r ji mp ij p r ji + (1 -p ij )(1 -p r ji )

)

Ideally, we have γ = 0, which means Γ = 0. If p r ji > 1 m+1 , the outcome of dual learning is better than the baseline translator. This means, as long as the overall probability of a correct translation is greater than choosing from the m + 1 translations (1 correct and m incorrect) uniformly at random, dual learning outperforms the baseline translator. The expression with the Γ factor is negative, which is consistent with the intuition that γ should be minimized. For the nonideal case where

Γ > 0, if both p r ji > 1 m+1 and Γ < (1 -p ij )(1 + 1 m -1 mp r ji

) hold, dual learning also improves against the baseline translator. 

4. EXTENSIONS: CYCLE DUAL LEARNING AND MULTIPATH DUAL LEARNING:

In Theorem 1, we found that both p ij and p r ji play a positive role in improving p d ij under mild assumptions. A natural question is whether this probability could be further enhanced by exploiting multiple language domains. Therefore, we propose the two frameworks, cycle dual learning and multipath dual learning, both of which leverage multiple languages and significantly extend the standard dual learning. In this section, we mainly present the cycle dual learning framework due to the space constraint.

4.1. FRAMEWORK:

The proposed frameworks are illustrated in Figure 1 . Let S 1 and S 2 denote the source language space and the target language space respectively. To use these frameworks, we first train the following translators: S 1 ↔ S 2 , S 1 ↔ S k and S 2 ↔ S k where k ≥ 3. Then, for cycle dual learning, we require a sentence from S 2 to be very similar to S 2 → S k → S 1 → S 2 (or equivalently, a sentence from S 1 to be very similar to S 1 → S 2 → S k → S 1 ); for multipath dual learning, we require the translation S 1 → S 2 to be the very similar S 1 → S k → S 2 . In this way, we build another constraint, where the translation S 1 → S 2 could leverage the information pivoted by the domain S k . In practice, to use cycle dual learning to enhance the S 1 → S 2 model, we need to minimize

x (2) ∈S2 D(T 12 (T k1 (T 2k (x (2) ))), x (2)

), where D(•, •) measures the differences of two inputs; to use multipath dual learning, we need to minimize x (1) ∈S1 D(T 12 (x (1) ), T k2 (T 1k (x (1) ))). Similar update could also be applied to S 2 → S 1 translation and leverage more language domains. If no auxiliary domain is provided, both cycle dual learning and multipath dual learning will degenerate to the standard dual learning. We design sampling based algorithms for the two frameworks. This section focuses on the cycle dual learning framework with corresponding theoretical analysis. See Appendix D and F for the multipath dual learning framework. In both frameworks, let θ ij denote the parameters of translator T ij .

Algorithm 1: Cycle Dual Learning Framework:

Input: Samples from spaces S 1 . . . S k , initial translators T 12 , T 21 and T 1i , T i1 ∀i = 3, . . . , K; learning rates η; Train each of T 12 , T 21 and T 1i , T i1 ∀i = 3, . . . , k by dual learning; Randomly sample a k from {3, 4, • • • , K}; randomly sample one x (1) ∈ S 1 and one x (2) ∈ S 2 ; Generate x(2) by T k2 • T 1k (x (1) ) and generate x(1) by T k1 • T 2k (x (2) ); Update the parameters of T 12 and T 21 , denoted as θ 12 and θ 21 , as follows: (1) ; θ 12 ); θ 21 ← θ 21 + η∇ θ21 log P (x (1) |x (2) ; θ 21 ); (7) Repeat Step 3 to Step 5 until convergence;

θ 12 ← θ 12 + η∇ θ12 log P (x (2) |x

4.2. THEORETICAL ANALYSIS:

The theoretical analyses of cycle dual learning and multipath dual learning are highly symmetric. In this section, we take cycle dual learning as an example. The analysis for multipath dual learning can be found in Appendix F.

For simplicity, we focus on the triangle structure that contains only S 1 , S 2 and S 3 . Now dual learning serves as the basic structure. For simplicity, we use q ij to denote the accuracy of T d ij , i.e. q ij = p d ij . We further define q

(2) 31 = Pr X (3) ∼T d 23 (X (1) ) (T d 31 (x (3) ) = x (1)

), which as the accuracy of T d 31 when the sentence in S 3 is translated from a random sentence in S 2 . This is analogous to reconstruction accuracy. To analyze cycle dual learning, we consider the following two cases (analogous to Case 1 and Case 2 for dual learning): 1) ))); and Case 2: ) ))). Cycle dual learning will detect Case 2 and train the translators so that Case 2 is minimized. To quantify this effect, we define the following probabilities:

EQUATION

EQUATION

EQUATION

where Case 2 denotes the condition 1) ))) and superscripts d and c denote the translators obtained from dual learning and cycle dual learning, respectively. α , β , γ can be viewed as the probability of correcting the wrong translations by cycle dual learning, the probability of the occurrence of the alignment problem under Case 2, and the probability of nonzero reconstruction error. γ models the imperfectness of dual learning. And we have α + β + γ = 1. We assume that T d 23 and T d 31 are independent translators. That implies,

EQUATION

Pr(T d 23 (x (2) ) = x (3) , T d 31 (x (3) ) = x (1) ) = q 23 q

(2) 31

(9) We will also need a similar assumption to Assumption 1 as follows.

Assumption 2. For any j = i, any y

(j) ∈ S j , E[1 y (j) =x (j) ,T d ij (x (i) )=y (j) ] = 1-qij m ,

where m is a constant.

The interpretation and justification of Assumption 2 is similar to those of Assumption 1. Then we have the following theorem about the triangle structure. The more general case can be viewed as adding one path a time so Theorem 2 can be applied. Theorem 2. Given languages spaces S 1 , S 2 , and S 3 , where the objective is to train a translator that maps from S 1 to S 2 , the accuracy of cycle dual learning outcome is

p c 12 = q 12 (1 -α )(q 23 q (1) 31 + (1 -q 23 )(1 -q (1) 31 ) m ) + α (1 - (1 -q 12 )(q 23 + q (1)

31 -(m + 1)q 23 q

(1)

EQUATION

)

under Assumption 2.

Theorem 2 is also proved by explicitly computing the probability of each case. The full proof can be found in the Appendix C. Theorem 2 is much harder to interpret than Theorem 1, but we can still observe how factors affect the accuracy of T c 12 . The role of T d 12 . The accuracy increases as q 12 increases. So a good initial translator is desirable. However, if T d 12 is arbitrarily bad, it is still possible to improve it significantly. This implies the application of this framework on low-resource or even zero-shot machine translation.

A similar hypothesis. Similar to the analysis of dual learning, we consider the condition where

α β = Pr(T d 12 (x (1) )=x (2) ,T d 31 (T d 23 (x (2)

))=x (1) ) Pr(T d 12 (x (1) ) =x (2) ,T d 31 (T d 23 (T d 12 (x (1) )))=x (1) ) and define Γ = γ Pr(x (1) = T d 31 (T d 23 (T d 12 (x (1) )))). Then the accuracy simplifies to

EQUATION

31 -(m+1)q23q

(2) 31 +m-1) mq12(mq23q

(2) 31 +(1-q23)(1-q (2) 31 )) = 1 -Γ 1 + M 1-q12 q12 where M = q23+q (2) 31 -(m+1)q23q (2) 31 +m-1 m(mq23q (2) 31 +(1-q23)(1-q (2) 31 ))

. We observe that When γ = 0 (and therefore Γ = 0) and M = 1, it simplifies to q 12 , which is the accuracy of dual learning and that p c 12 increases as M decreases. To characterize the condition when p c 12 > q 12 , we let M < 1. We have q13+q

32 -(m+1)q13q

(1)

32 +m-1 m(mq13q

(1) 32 +(1-q13)(1-q (1) 32 ))

< 1, which leads to ((m + 1)q 13 -1)((m + 1)q

(1) 32 -1) > 0. When q 13 , q

(1) 32 > 1 m+1 , which means the probability of correctly translating a sentence is greater than choosing from potentially wrong translations uniformly at random, cycle dual learning outperforms dual learning.

We also prove a similar theorem for multipath dual learning (see Appendix F). The accuracy of multipath dual learning has a similar form. We observe similar empirical performances as well (see Appendix E).

5. EXPERIMENTS OF DUAL LEARNING:

Since previous works (He et al., 2016; Xia et al., 2017a; b; Wang et al., 2018; Xia et al., 2018) have demonstrated strength of dual learning, we aims at providing some theoretical insights. We choose WMT2014 English↔Germen translation 1 and MultiUN (Eisele & Chen, 2010 ) English↔French translation2 to verify our theoretical analysis for dual learning. For ease of reference, denote English, French and German as En, Fr and De respectively.

5.1. SETTINGS:

Datasets Following the common practice in NMT, for the En↔De, we preprocess the data in the same way as that used in Vaswani et al. (2017) and eventually obtain 4.5M training sentence pairs. We concatenate newstest2012 and newstest2013 as the validation set (6K sentence pairs) and choose newstest2014 as the test set (3K sentence pairs). For the MultiUN En↔Fr translation, we sample 2M/6K/3K sentence pairs as the training/validation/test sets. All the sentence are split into wordpiece following (Johnson et al., 2016) . To leverage dual learning as that used in (He et al., 2016) , for WMT'14 En↔De translation, we choose 8M monolingual English sentences and 8M monolingial German sentences from newscrawl. For MultiUN En↔Fr translation, we randomly sample 1M English and 1M French sentences as the monolingual data to construct the duality loss.

Architecture & Optimization We use Transformer (Vaswani et al., 2017) , the state-of-the-art NMT system, for each direction. For WMT En↔De translation, we choose the transformer big configuration, in which the word embedding dimension, hidden dimension filter sizes and number of multihead attention are 1024, 1024 and 4096 respectively. For MultiUN En↔Fr translation, we choose the transformer base configuration, in which the aforementioned four numbers are 512, 512, 2048 and 8 respectively. The optimization algorithm is Adam with learning rate 2 × 10 -4 , β 1 = 0.99 and 7168 tokens per GPU. We train our models on 8 M40 GPUs for 7 days.

Evaluation For WMT 2014 En↔De translation, following Vaswani et al. (2017) , we use beam search with beam width 4 and length penalty 0.6 to generate candidates. The evaluation metric is BLEU score (Papineni et al., 2002b) , which is a geometric mean of n-gram precisions (n = 1, 2, 3, 4). A large BLEU score indicates a better translation quality.

5.2. RESULTS:



Translation qualities:

The BLEU scores of each translation tasks are summarized in Table 1 , in which the second row and third row represent the results of the standard Transformer and dual learning. We can see that after applying dual learning, the performances of all tasks are boosted. Specially, on En→De and De→En translations, we can improve the baseline from 28.40 to 29.97, and from 32.15 to 35.16. On the other task, dual learning can achieve 0.65 and 0.86 point improvement, which demonstrates its effectiveness. We found that on MultiUN, we do not achieve as much improvement as WMT. The reason is that MultiUN dataset is a collection of translated documents from the United Nations, which are usually of formal and simple patterns that are easy to learn. As a result, introducing more data might not increase the BLEU so much. The roles of m and γ It appears that all theories throughout this paper are independent of the selection of threshold score. However, in practice, different thresholds result in different m and γ values. A higher threshold BLEU score usually means there are more incorrect possible translations, and it will be harder reconstruct the original sentence well. Despite of this, we assume m and γ are constants and performed a regression analysis using equation 6, where m and γ are independent variables. we compute p 12 , p 21 , and p d 12 for all integer threshold scores between 1 and 100, and fit equation 6 by minimizing the absolute value of differences between the predicted p d 12 and true p d 12 , resulting in m = 92 and γ = 0.45 for the En↔De task (m = 12 and γ = 0.57 for the En↔Fr task). The high γ value on one hand implies that machine translation is generally a hard task, and on the other hand means there is still space to improve.

6. EXPERIMENTS OF MULTIPATH DUAL LEARNING:

To verify the effectiveness of cycle dual learning and multipath dual learning, we focus on the translation between English (En), French (Fr) and Spanish (Es). Again, we choose the MultiUN dataset to build the translation models since any two of the aforementioned three languages have bilingual sentence pairs. We study two different settings, where for each language pair, we are provided with 2M or 0.2M bilingual sentence pairs. For both settings, we choose 1M monolingual sentences for each language. We use transformer base for all experiments in this section, where the model is a six-block network, with word embedding size, hidden state size and filter size 512, 512 and 2048. The training process is the same as that in Section 5. The results of using 0.2M bilingual data plus 1M monolingual data is shown in Table 4 . We have the following observations: (1) Since there are fewer bilingual sentences, the baselines of the six translation tasks are not as good as those in Table 3 . (2) For this setting, dual learning can improve the BLEU scores by 1.93 points on average, which is consistent with the discovery in He et al.

(2016) that dual learning can obtain more improvements when the number of bilingual sentences is small.(3) When cycle dual learning is added to the conventional dual learning, we can achieve an extra 1.45 improvements.

7. CONCLUSIONS:

We provide the first theoretical study of dual learning and characterize conditions when dual learning outperforms baselines. We also propose two algorithmic extensions of dual learning, the cycle dual learning framework and multipath dual learning framework, which are provably better than dual learning under mild conditions. Our dual learning experiments demonstrate the efficacy of dual learning w.r.t. accuracy and provide insights on the potential power of dual learning. Our cycle dual learning framework achieves a new state-of-the-art BLEU score.

A NOTATIONS k number of language spaces S i i-th language space µ (i) distribution of sentences in S i X (i) the random variable that follows µ (i) x (i) one sample (sentence) in S i x (j) the correct translation of x (i) in S J T ij the baseline translatorthat translates from S i to S j p ij accuracy of the T ij T d ij translator that translates from S i to S j trained using dual learning Proof. Consider a random sample x (1) and the translation from x (1) ∈ S 1 to S 2 . Before dual learning, the accuracy is p 12 . We analyze the two cases defined earlier in this section.

Case 1. T 21 (T 12 (x (1) )) = x (1) . Case 1 consists of two subcases: Case 1.1: T 12 (x (1) ) = x (2) ; Case 1.2: T 12 (x (1) 

) = x (2) .

Although Case 1.2 is not desired, dual learning does not detect it. From equation 2, the probability of Case 1.1 is Pr(T 12 (x (1) ) = x (2) , T 21 (T 12 (x (1) )) = x (1) ) = p 12 p r 21 , According to Assumption 1, we have

Pr(T 12 (x (1) ) = x (2) , T 21 (T 12 (x (1) )) = x (1) ) = y (2) ∈S2,y (2) =x (2)

Pr(T 12 (x (1) 

) = y (2) , T 21 (y (2) ) = x (1) ) = (1 -p 12 )(1 -p r 21 ) m

Case 2. T 21 (T 12 (x (1) )) = x (1) . Dual learning will train the translators so that this case is minimized. The probability of this case is simply the complement of Case 1.

Pr(Case 2) = 1 -p 12 p r 21 - (1 -p 12 )(1 -p r 21 ) m

After dual learning, Case 2 is redistributed to the two subcases of Case 1, with probabilities α and β respectively. So we have

EQUATION

Pr(T d 12 (x (1) ) = x (2) , T d 21 (T d 12 (x (1) )) = x (1) ) = (1 -β)(1 -p 12 )(1 -p r 21 ) m + β(1 -p 12 p r 21 ) Pr(T d 21 (T d 12 (x (1) )) = x (1) ) = γ(1 -p 12 p r 21 - (1 -p 12 )(1 -p r 21 ) m ),

where equation 11 computes the accuracy of dual learning.

=q 23 q (1) 31 + (1 -q 23 )(1 -q (1)

31 ) m where the first equality is obtained by the law of total probability, and the second quality is obtained by equation 9 and Assumption 2. Then the probability of Case 1.1 is computed as follows.

EQUATION

Case 1.2. For the S 1 ↔ S 2 path we have Pr(T d 12 (x (1) ) = x (2) ) = 1 -q 12 . Let y (2) ∈ S 2 denote this incorrect translation. Now we compute Pr(T d 31 (T d 23 (x (2) )) = y (1) ). There are three cases depending on the translation at S 3 : x (3) , y (3) , and others. They are computed as follows.

EQUATION

Pr(T d 31 (T d 23 (y (2) )) = x (1) |T d 23 (x (2) ) = y (3) ) = 1 -q (1) 31 m Pr(T d 31 (T d 23 (y (2) )) = x (1) |T d 23 (x (2) ) = x (3) , y (3) ) = 1 -q (1) 31 m

Using the law of total probability we have

Pr(T d 31 (T d 23 (y (2) )) = x (1) ) = q (1) 31 (1 -q 23 ) m + q 23 (1 -q (1) 31 ) m + (m -1)(1 -q 23 )(1 -q (1) 31 ) m 2 = m(q 32 + q (1)

31 -2q 23 q

(1)

31 ) + (m -1)(1 -q 23 )(1 -q (1) 31 ) m 2 = q 23 + q (1)

31 -(m + 1)q 23 q

(1)

31 + m -1 m 2

Then the probability of Case 1.2 is 1) ))) = x (1) ) =

EQUATION

(1 -q 12 )(q 23 + q

(1)

31 -(m + 1)q 32 q

(1)

31 + m -1) m 2 (13) Case 2. The probability of Case 2 is simply the complement of Case 1.

Pr(T d 31 (T d 23 (T d 12 (x (1) ))) = x (1) ) = 1 -Pr(T d 31 (T d 23 (T d 12 (x (1) ))) = x (1) ) =1 -q 12 (q 23 q (1) 31 + (1 -q 23 )(1 -q (1) 31 ) m ) - (1 -q 12 )(q 23 + q (1)

31 -(m + 1)q 23 q

(1)

EQUATION

)

Then the accuracy of this triple learning is 1) ))) = x (1) ), (15

EQUATION

)

where α is defined in equation 8. equation 10 is obtained by substitute equation 12 and equation 14 into equation 15.

D MULTIPATH DUAL LEARNING FRAMEWORK:

The algorithm of multipath dual learning is shown in Algorithm 2. 1) ∈ S 1 and one x (2) ∈ S 2 ; Sample one x(k) ∼ T 1k (x (1) ), x(2) ∼ T k2 (x (k) ); x(k) ∼ T 2k (x (2) ) and x(2) ∼ T k2 (x (k) ); Update the parameters of T 12 and T 21 , denoted as θ 12 and θ 21 , as follows:

θ 12 ← θ 12 -η∇ θ12 log P (x (2) |x (1) ; θ 12 ); θ 21 ← θ 21 -η∇ θ21 log P (x (1) |x (2) ; θ 21 );

(16)

Repeat:

Step 3 to Step 5 until convergence;

It is well-known that the two gradients in equation 16 are unbiased estimators of ∇ θ12 D KL (P (•|x (1) ; T k2 • T 1k ) P (•|x (1) ; θ 12 )) ; ∇ θ21 D KL (P (•|x (1) ; T k2 • T 1k ) P (•|x (1) ; θ 12 )).

(17) The reason is shown as follows. For any given x (1) ∈ S 1 , min θ12 D KL (P (•|x (1) ; θ 1k , θ k2 ) P (•|x (1) ; θ 12 )) = x (2) ∈S2 P (x (2) |x (1) ; θ 1k , θ k2 ) log P (x (2) |x (1) ; θ 1k , θ k2 ) P (x (2) |x (1) ; θ 12 ) ,

which is equivalent to 1) ; θ 1k , θ k2 ) log P (x (2) |x (1) ; 1) ; θ 1k , θ k2 ) log P (x (2) |x (1) ; 1) ; θ 1k , θ k2 )P (x (2) |x (k) , x (1) ; θ 1k , θ k2 ) log P (x (2) |x (1) ; 1) ; θ 12 ).

EQUATION

EQUATION

EQUATION

EQUATION

(

EQUATION

Therefore, we can first sample x(k) from P (•|x (1) ; θ 12 ), then sample x(2) from P (•|x (k) ; θ k2 ), and then maximize log P (x (2) |x (1) ; θ 12 ). Obviously, -∇ θ12 log P (x (2) |x (1) ; θ 12 ) is the unbiased estimator of ∇ θ12 D KL (P (•|x (1) ; θ 1k , θ k2 ) P (•|x (1) ; θ 12 )).

The performance of multipath dual learning is shown in 2) . We have that 2) ; θ 2k )P (x (1) |x (k) ; θ k1 ) log P (x (2) |x (1) ; 1) ; θ 12 ).

→ S k → S 1 → S 2 , x (2) is reconstructed to x (

EQUATION

EQUATION

(20) Then, we can use the algorithm proposed in Algorithm 1 to solve the above optimization problem, i.e., min -log P (R(x (2) )).

F THEORETICAL ANALYSIS FOR MUTIPATH DUAL LEARNING:

We define q

(1) 32 = Pr X (3) ∼T d 13 (X (1) ) (T d 32 (x (3) ) = x (2)

), which as the accuracy of T d 32 when the sentence in S 3 is translated from a random sentence in S 1 . This is analogous to reconstruction accuracy, and is reduced to the reconstruction accuracy when S 2 = S 1 . To analyze multipath learning, we consider the following cases (analogous to Case 1 and Case 2 for dual learning and cycle dual learning): Case 1: T 12 (x (1) ) = T 32 (T 13 (x (1) )); Case 2: T 12 (x (1) ) = T 32 (T 13 (x (1) )).

multipath dual learning will detect Case 2 and train the translators so that the difference between translations from the two paths is minimized. To quantify this effect, we define the following probabilities: 1) )) = x (2) |Case 2) β = Pr(T m 12 (x (1) ) = x (2) , T m 32 (T m 13 (x (1) )) = T m 12 (x (2) )|Case 2) γ = Pr(T m 21 (T m 12 (x (1) )) = x (1) |Case 2),

EQUATION

where Case 2 denotes the condition T 12 (x (1) ) = T 32 (T 13 (x (1) )) and superscripts d and m denote the translators obtained from dual learning and multipath learning, respectively. α , β , γ can be viewed as the probability of correcting the wrong translations by multipath learning, the probability of the occurrence of the alignment problem under Case 2, and the probability of nonzero reconstruction error. γ models the imperfectness of dual learning. And again, we have α + β + γ = 1. We assume that T d 13 and T d 32 are independent translators before multipath learning. That implies, Pr(T d 13 (x (1) ) = x (3) , T d 32 (T d 13 (x (1) )) = x (2) ) = Pr(T d 13 (x (1) ) = x (3) , T d 32 (x (3) ) = x (2) ) = q 13 q (1) 32

(22) Then we have the following theorem, which focuses one the triangle structure containing only S 1 , S 2 , and S 3 . The more general case can be viewed as adding one path a time so Theorem 3 can be applied. Theorem 3. Given languages spaces S 1 , S 2 , and S 3 , where the objective is to train a translator that maps from S 1 to S 2 , the accuracy of two-path learning (Figure 1 ) outcome is p m 12 = q 12 (1 -α )(q 13 q (1) 32 +

(1 -q 13 )(1 -q

(1) 32 ) m )

+ α (1 -(1 -q 12 )(q 13 + q

(1)

32 -(m + 1)q 13 q (1)

EQUATION

)

under Assumption 2.

Proof. Similar to the analysis of Theorem 1, we focus on the mapping from x (1) ∈ S 1 to S 2 and consider the following two cases:

Case 1: T d 12 (x (1) ) = T d 32 (T d 13 (x (1) )); Case 2: T d 12 (x (1) ) = T d 32 (T d 13 (x (1) )). We first characterize the probability of Case 1.

Case 1: According to whether the translation in S 2 is correct, Case 1 can be partitioned into two subcases: Case 1.1: T d 12 (x (1) ) = x (2) , T d 23 (T d 13 (x (1) )) = x (2) ; Case 1.2: T d 12 (x (1) ) = x (2) , T d 23 (T d 13 (x (1) )) = T d 12 (x (1) ). Case 1.1. For the path S 1 ↔ S 2 , we have Pr(T d 12 (x (1) ) = x (2) ) = q 12 . For the path S 1 ↔ S 3 ↔ S 2 , since we only care about the translation in S 2 , we have Pr(T d 32 (T d 13 (x (1) )) = x (2) ) = Pr(T d 13 (x (1) ) = x (3) ) Pr(T d 32 (T d 13 (x (1) )) = x (2) |T d 13 (x (1) ) = x (3) ) + Pr(T d 13 (x (1) ) = x (3) ) Pr(T d 32 (T d 13 (x (1) )) = x (2) |T d 13 (x (1) ) = x (3) ) =q 13 q

(1) 32 +

(1 -q 13 )(1 -q

(1)

32. ) m:

where the first equality is obtained by the law of total probability, and the second quality is obtained by equation 22 and Assumption 2. Then the probability of Case 1.1 is computed as follows.

Pr(T d 12 (x (1) ) = x (2) , T d 23 (T d 13 (x (1) )) = x (2) ) = q 12 (q 13 q (1) 32 +

(1 -q 13 )(1 -q

(1)

EQUATION

Case 1.2. For the S 1 ↔ S 2 path we have Pr(T d 12 (x (1) ) = x (2) ) = 1 -q 12 . Let y (2) ∈ S 2 denote this incorrect translation. Now we compute Pr(T d 32 (T d 13 (x (1) )) = y (2) ). There are three cases depending on the translation at S 3 : x (3) , y (3) , and others. They are computed as follows.

Pr(T d 32 (T d 13 (x (1) )) = y (2) |T d 13 (x (1) ) = x (3) ) = 1 -q

(1) 32 m Pr(T d 32 (T d 13 (x (1) )) = y (2) |T d 13 (x (1) ) = y (3) ) = q

(1) 32

Pr(T d 32 (T d 13 (x (1) )) = y (2) |T d 13 (x (1) ) = x (3) , y (3) ) = 1 -q

(1) 32 m

:

Data available at http://www.statmt.org/wmt14/translation-task.html.

Data available at http://opus.nlpl.eu/MultiUN.php

m+1 , which means the probability of correctly translating a sentence is greater than choosing from potentially wrong translations uniformly at random, the two-path learning outperforms dual learning.

Figures and Tables:

Figure 1: The proposed multipath dual learning and cycle dual learning.

from S i to S j trained using cycle dual learning p from S i to S j trained using multipath dual learningp m ij accuracy of T m ijTable 5: Notations B PROOF OF THEOREM 1

Multi-path Dual Learning Framework Input: Samples from spaces S 1 . . . S k , initial translators T 12 , T 21 and T 1i , T i1 ∀i = 3, . . . , K; learning rates η; Train each of T 12 , T 21 and T 1i , T i1 ∀i = 3, . . . , k by dual learning; Randomly sample a k from {3, 4, • • • , K}; randomly sample one x (

BLEU scores of WMT2014 En↔De and MultiUN En↔Fr translations tasks.The translator accuracy We interpret the results in terms of accuracy when different thresholds are selected. We vary the threshold BLEU score from 10 to 40, and the accuracy of each translator is shown in Table2. Let S 1 and S 2 denote English and German respectively for the En↔De task (English and French respectively for the En↔Fr task). Values are percentages of translations that are above the threshold.

Table content: <table><tr><td/><td colspan="4">En→De De→En En→Fr Fr→En</td></tr><tr><td>Standard</td><td>28.40</td><td>32.04</td><td>50.26</td><td>50.56</td></tr><tr><td>Dual Learning</td><td>29.97</td><td>34.93</td><td>50.91</td><td>51.42</td></tr></table>

Accuracy of translators using different threshold BLEU scores.

Table content: <table/>

Experimental Results on MultiUN (2M bilingual data)The experimental results of using 2M bilingual data and 1M monolingual data are shown in Table3. We can see that on average, dual learning can boost the six baselines (i.e., standard transformer) by 0.55 point. Although dual learning can achieve verify high scores on MultiUN translation tasks, our proposed cycle dual learning can still improve it by 0.41 point on average.

Table content: <table><tr><td/><td colspan="6">En→Fr Fr→En En→Es Es→En Es→Fr Fr→Es</td></tr><tr><td>Baseline</td><td>50.26</td><td>50.56</td><td>55.15</td><td>55.23</td><td>47.75</td><td>48.13</td></tr><tr><td>Dual Learning</td><td>50.91</td><td>51.42</td><td>55.51</td><td>55.77</td><td>48.23</td><td>48.52</td></tr><tr><td>Cycle</td><td>51.28</td><td>51.89</td><td>55.97</td><td>56.17</td><td>48.62</td><td>48.87</td></tr><tr><td/><td colspan="6">En→Fr Fr→En En→Es Es→En Es→Fr Fr→Es</td></tr><tr><td>Baseline</td><td>43.12</td><td>43.26</td><td>49.28</td><td>47.80</td><td>41.47</td><td>41.21</td></tr><tr><td>Dual Learning</td><td>45.54</td><td>45.44</td><td>51.07</td><td>50.31</td><td>42.81</td><td>42.57</td></tr><tr><td>Cycle</td><td>47.23</td><td>46.72</td><td>52.56</td><td>51.65</td><td>43.52</td><td>44.97</td></tr></table>

Experimental Results onMultiUN (0.2M bilingual data)

Table content: <table/>

Table 6 in comparison with other translators. We observe that multipath dual learning has a very similar performance with cycle dual learning, which is consistent with our theoretical analysis. Experimental Results on MultiUN (2M bilingual data)E DERIVATION OF CYCLE DUAL LEARNING ALGORITHMWe follow the notations used in Appendix D. Let R(x (2) ) denote the event that after passing S 2

Table content: <table><tr><td colspan="3">Under review as a conference paper at ICLR 2019</td><td/><td/><td/><td/></tr><tr><td/><td colspan="6">En→Fr Fr→En En→Es Es→En Es→Fr Fr→Es</td></tr><tr><td>Baseline</td><td>50.26</td><td>50.56</td><td>55.15</td><td>55.23</td><td>47.75</td><td>48.13</td></tr><tr><td>Dual Learning</td><td>50.91</td><td>51.42</td><td>55.51</td><td>55.77</td><td>48.23</td><td>48.52</td></tr><tr><td>Multi-path</td><td>51.27</td><td>51.74</td><td>55.89</td><td>56.06</td><td>48.34</td><td>48.76</td></tr><tr><td>Cycle</td><td>51.28</td><td>51.89</td><td>55.97</td><td>56.17</td><td>48.62</td><td>48.87</td></tr></table>

Peer review (iclr2019):
 The paper addresses a means of boosting the accuracy of automatic translators (sentences) by training dual models (a.k.a. language A to B, B to A), multipath (e.g. A to B to C) and cyclical (e.g. A to B to C to A) while starting with well initialized models for translating simple pairs. The idea that additional errors are revealed and allow classifiers to adapt, thus boosting classifier performance, is appealing and intuitive. That a theoretical framework is presented to support this assumption is encouraging, but the assumptions behind this analysis (e.g. Assumption 1) are rather strong. Equation 2 assumes independence. Equations 3-5 can be presented more clearly. Not only are translation errors not uniform in multiclass settings, but they can be highly correlated - this being a possible pitfall of boosting approaches, seen as general classifier errors. The same strong assumptions permeate from the dual to the cyclical case. On the other hand, the (limited) empirical test presented, using a single dataset and baseline classifier method, does support the proposed improvement by boosting, albeit leading to improvements which are slight.