Year: 2018

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.

text: 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.

heading: 1 INTRODUCTION
text: 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?

heading: 1.1 OUR CONTRIBUTIONS
text: 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.

heading: 1.2 RELATED WORK
text: 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.

heading: 2 PRELIMINARIES
text: 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 S1, . . . , Sk be k language spaces, composed of sentences in each language. For any Si, we denote the distribution of sentences in Si by µ(i) and let X(i) be the random variable, i.e. Pr(X(i) = x) = µ(i)(x). For any x(i) ∈ Si, we denote the correct translation in Sj by x(j). In practice, we may select a threshold BLEU (Papineni et al., 2002a) score, above which the translation is considered correct. Let Tij denote the baseline translator that translates from a sentence in Si to one in Sj , i.e. the desired mapping is Tij(x
(i)) = x(j). When a random sentence x(i) is sampled from Si according to µ(i), it is possible that this sentence is translated incorrectly. We use accuracy of the translator pij , the accuracy of the translator, to describe the probability of translating a sentence correctly when this sentence is randomly sampled from Si according to µ(i). Formally, pij = Prx(i)∼µ(i)(Tij(x(i)) = x(j)) = Ex(i)∼µ(i) [1Tij(x(i))=x(j) ] = ∑ x(i)∈Si 1Tij(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
Pr(Tij(x (i)) 6= x(j)) = E[1Tij(x(i))6=x(j) ] = 1− pij . (1)
In order to characterize reconstruction accuracy, we let X(j,r) denote the random variable that follows the distribution Tij(X(i)) where X(i) ∼ µ(i). We define µ(j,r)(x) = Pr(X(j,r) = x), and further define prji = PrX(j,r)∼µ(j,r)(Tji(x
(j)) = x(i)) = EX(j,r)∼µ(j,r) [1Tji(x(j))=x(i) ] =∑ x(j)∈Sj 1Tji(x(j))=x(i)µ
(j,r)(x(j)). The superscript r means “reconstruction”. The difference between prji and pji lies in the distributions of samples in space Sj . We assume that Tij and Tji are independent translators. This is natural because Tij and Tji are usually trained independently. Then, for any j 6= i, we have
Pr(Tij(x (i)) = x(j), Tji(x (j)) = x(i)) = pijp r ji. (2)
Further, we make the following assumption.
Assumption 1. For any j 6= i, any y(j) ∈ Sj , E[1y(j) 6=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) ∈ Si that are incorrectly translated into Sj , there are m possibly incorrect translations (in Sj) 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 pmax is treated as one cluster. All the other possibly incorrect translations are clustered so that the probability of each cluster is close to pmax. Then we have m ≤ 1−pijpmax . A small pmax (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) Tji(Tij(x(i))) = x(i); (Case 2) Tji(Tij(x(i))) 6= 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 xi ∈ Si which fails in reconstruction (Case 2), we define
α = Pr(T dij(x (i)) = x(j), T dji(T d ij(x (i))) = x(i)|Case 2) (3)
β = Pr(T dij(x (i)) 6= x(j), T dji(T dij(x(i))) = x(i)|Case 2) (4)
γ = Pr(T dji(T d ij(x (i))) 6= x(i)|Case 2), (5)
where “Case 2” denotes the condition Tji(Tij(x(i))) 6= 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.

heading: 3 THEORETICAL STUDY
text: 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 Si and Sj , the accuracy of dual learning outcome T dij is p d ij = (1− α)pijprji + α(1− (1−pij)(1−prji) 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 pij or prji is, the higher accuracy of T dij dual learning can achieve.
The role of m and α. When pij , prji 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 pdij − pij = 1− (1−pij)(1−prji) m − pij = (1−pij)(m−1+prji) m . This means dual learning provides an improvement as long as m ≥ 1 and prji > 0, which is trivial. A hypothesis. We consider the case where the probabilities of redistribution to α case and β case are proportional to α and β. Formally, αβ = Pr(Tij(x (i))=x(j),Tji(Tij(x (i)))=x(i)) Pr(Tij(x(i))6=x(j),Tji(Tij(x(i)))=x(i)) = mpijp r ji (1−pij)(1−prji) . Then we have α = mpijp r ji(1−γ)
mpijprji+(1−pij)(1−prji) and
pdij = Pr(T d ij(x (i)) = x(j), T dji(x (j)) = x(i))
= mpijp
r ji(1− γ(1− pijprji − (1−pij)(1−prji) m ))
mpijprji + (1− pij)(1− prji) =
mpijp r ji(1− Γ)
mpijprji + (1− pij)(1− prji) , (6)
where Γ = γ(1−pijprji− (1−pij)(1−prji) m ). To compare p d ij with the accuracy of the original translator, we compute the difference
pdij − pij =pij( mprji(1− Γ)
mpijprji + (1− pij)(1− prji) − 1)
=pij( mprji
mpijprji + (1− pij)(1− prji) − 1− Γmprji mpijprji + (1− pij)(1− prji) )
=pij( (1− pij)((m+ 1)prji − 1) mpijprji + (1− pij)(1− prji) − Γmprji mpijprji + (1− pij)(1− prji) )
Ideally, we have γ = 0, which means Γ = 0. If prji > 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 prji > 1 m+1 and Γ < (1 − pij)(1 + 1 m − 1 mprji
) hold, dual learning also improves against the baseline translator.

heading: 4 EXTENSIONS: CYCLE DUAL LEARNING AND MULTIPATH DUAL LEARNING
text: In Theorem 1, we found that both pij and prji 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.

heading: 4.1 FRAMEWORK
text: The proposed frameworks are illustrated in Figure 1. Let S1 and S2 denote the source language space and the target language space respectively. To use these frameworks, we first train the following translators: S1 ↔ S2, S1 ↔ Sk and S2 ↔ Sk where k ≥ 3. Then, for cycle dual learning, we require a sentence from S2 to be very similar to S2 → Sk → S1 → S2 (or equivalently, a sentence from S1 to be very similar to S1 → S2 → Sk → S1); for multipath dual learning, we require the translation S1 → S2 to be the very similar S1 → Sk → S2. In this way, we build another constraint, where the translation S1 → S2 could leverage the information pivoted by the domain Sk. In practice, to use cycle dual learning to enhance the S1 → S2 model, we need to minimize∑ x(2)∈S2 D(T12(Tk1(T2k(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(T12(x (1)), Tk2(T1k(x (1)))). Similar update could also be applied to S2 → S1 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 Tij .
Algorithm 1: Cycle Dual Learning Framework 1 Input: Samples from spaces S1 . . . Sk, initial translators T12, T21 and T1i, Ti1 ∀i = 3, . . . ,K;
learning rates η; 2 Train each of T12, T21 and T1i, Ti1 ∀i = 3, . . . , k by dual learning; 3 Randomly sample a k from {3, 4, · · · ,K}; randomly sample one x(1) ∈ S1 and one x(2) ∈ S2; 4 Generate x̃(2) by Tk2 ◦ T1k(x(1)) and generate x̃(1) by Tk1 ◦ T2k(x(2)); 5 Update the parameters of T12 and T21, denoted as θ12 and θ21, as follows:
θ12 ← θ12 + η∇θ12 logP (x(2)|x̃(1); θ12); θ21 ← θ21 + η∇θ21 logP (x(1)|x̃(2); θ21); (7)
Repeat Step 3 to Step 5 until convergence;

heading: 4.2 THEORETICAL ANALYSIS
text: 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 S1, S2 and S3. Now dual learning serves as the basic structure. For simplicity, we use qij to denote the accuracy of T dij , i.e. qij = p d ij . We further define q(2)31 = PrX(3)∼Td23(X(1))(T d 31(x
(3)) = x(1)), which as the accuracy of T d31 when the sentence in S3 is translated from a random sentence in S2. 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): Case 1: x(1) = T d31(T d23(T d12(x(1)))); and Case 2: x(1) 6= T d31(T d23(T d12(x(1)))). 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:
α′ = Pr(T c12(x (1)) = x(2), T c31(T c 23(x (2))) = x(1)|Case 2) β′ = Pr(T c12(x
(1)) 6= x(2), T c31(T c23(T c12(x(1)))) = x(1)|Case 2) γ′ = Pr(x(1) 6= T c31(T c23(T c12(x(1))))|Case 2), (8)
where Case 2 denotes the condition x(1) 6= T d31(T d23(T d12(x(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 d23 and T d 31 are independent translators. That implies,
Pr(T d23(x (2)) = x(3), T d31(x (3)) = x(1)) = q23q (2) 31 (9)
We will also need a similar assumption to Assumption 1 as follows.
Assumption 2. For any j 6= i, any y(j) ∈ Sj , E[1y(j) 6=x(j),Tdij(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 S1, S2, and S3, where the objective is to train a translator that maps from S1 to S2, the accuracy of cycle dual learning outcome is
pc12 = q12(1− α′)(q23q (1) 31 + (1− q23)(1− q(1)31 ) m )
+ α′(1− (1− q12)(q23 + q (1) 31 − (m+ 1)q23q (1) 31 +m− 1)
m2 ) (10)
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 c12.
The role of T d12. The accuracy increases as q12 increases. So a good initial translator is desirable. However, if T d12 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(Td12(x (1))=x(2),Td31(T d 23(x (2)))=x(1))
Pr(Td12(x (1))6=x(2),Td31(Td23(Td12(x(1))))=x(1)) and define Γ′ = γ′ Pr(x(1) 6= T d31(T d23(T d12(x(1))))). Then the accuracy simplifies to
pc12 = α′(1− Γ′) α′ + β′ = q12(q23q (2) 31 + (1−q23)(1−q(2)31 ) m )(1− Γ ′)
q12(q23q (2) 31 + (1−q23)(1−q(2)31 ) m ) + (1−q12)(q23+q(2)31 −(m+1)q23q (2) 31 +m−1) m2
= 1− Γ′
1 + (1−q12)(q23+q(2)31 −(m+1)q23q (2) 31 +m−1)
mq12(mq23q (2) 31 +(1−q23)(1−q (2) 31 ))
= 1− Γ′
1 +M 1−q12q12
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 q12, which is the accuracy of dual learning and that pc12 increases as M decreases. To characterize the condition when pc12 > q12, we let M < 1. We have q13+q (1) 32 −(m+1)q13q (1) 32 +m−1 m(mq13q (1) 32 +(1−q13)(1−q (1) 32 )) < 1, which leads to
((m+ 1)q13 − 1)((m+ 1)q(1)32 − 1) > 0.
When q13, 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).

heading: 5 EXPERIMENTS OF DUAL LEARNING
text: 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 translation1 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.

heading: 5.1 SETTINGS
text: 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.

heading: 5.2 RESULTS
text: 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 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 Table 2. Let S1 and S2 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.
Qualitively, we observe that dual learning outcomes are better than single transformers. More interesting observations lie in the following quantitative analysis.
1Data available at http://www.statmt.org/wmt14/translation-task.html. 2Data available at http://opus.nlpl.eu/MultiUN.php
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 p12, p21, and pd12 for all integer threshold scores between 1 and 100, and fit equation 6 by minimizing the absolute value of differences between the predicted pd12 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.

heading: 6 EXPERIMENTS OF MULTIPATH DUAL LEARNING
text: 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 experimental results of using 2M bilingual data and 1M monolingual data are shown in Table 3. 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.
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.

heading: 7 CONCLUSIONS
text: 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.

heading: A NOTATIONS

heading: B PROOF OF THEOREM 1
text: Proof. Consider a random sample x(1) and the translation from x(1) ∈ S1 to S2. Before dual learning, the accuracy is p12. We analyze the two cases defined earlier in this section.
Case 1. T21(T12(x(1))) = x(1). Case 1 consists of two subcases:
Case 1.1: T12(x(1)) = x(2); Case 1.2: T12(x(1)) 6= 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(T12(x(1)) = x(2), T21(T12(x(1))) = x(1)) = p12pr21, According to Assumption 1, we have
Pr(T12(x (1)) 6= x(2), T21(T12(x(1))) = x(1)) = ∑
y(2)∈S2,y(2) 6=x(2) Pr(T12(x
(1)) = y(2), T21(y (2)) = x(1)) = (1− p12)(1− pr21) m
Case 2. T21(T12(x(1))) 6= 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− p12pr21 − (1− p12)(1− pr21)
m
After dual learning, Case 2 is redistributed to the two subcases of Case 1, with probabilities α and β respectively. So we have
Pr(T d12(x (1)) = x(2), T d21(T d 12(x (1))) = x(1)) = p12p r 21 + α(1− p12pr21 − (1− p12)(1− pr21) m ) = (1− α)p12pr21 + α(1− (1− p12)(1− pr21)
m ) (11)
Pr(T d12(x (1)) 6= x(2), T d21(T d12(x(1))) = x(1)) = (1− β)(1− p12)(1− pr21) m + β(1− p12pr21)
Pr(T d21(T d 12(x (1))) 6= x(1)) = γ(1− p12pr21 − (1− p12)(1− pr21)
m ),
where equation 11 computes the accuracy of dual learning.

heading: C PROOF OF THEOREM 2
text: Proof. We focus on the mapping from x(1) ∈ S1 to S2 and consider the following two cases:
Case 1: T d31(T d 23(T d 12(x (1)))) = x(1); Case 2: T d31(T d 23(T d 12(x
(1)))) 6= x(1). We first characterize the probability of Case 1.
Case 1: According to whether the translation in S2 is correct, Case 1 can be partitioned into two subcases:
Case 1.1: T d12(x (1)) = x(2), T d31(T d 23(x (2))) = x(1);
Case 1.2: T d12(x (1)) 6= x(2), T d31(T d23(T d12(x(1)))) = x(1).
Case 1.1. For the path S1 ↔ S2, we have Pr(T d12(x(1)) = x(2)) = q12. For the path S2 ↔ S3 ↔ S1, since we only care about the translation in S1, we have
Pr(T d31(T d 23(x (2))) = x(1)) = Pr(T d23(x (2)) = x(3)) Pr(T d31(T d 23(x (2))) = x(1)|T d23(x(2)) = x(3)) + Pr(T d23(x (2)) 6= x(3)) Pr(T d31(T d23(x(2))) = x(1)|T d23(x(2)) 6= x(3))
=q23q (1) 31 + (1− q23)(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.
Pr(T d12(x (1)) = x(2), T d23(T d 13(x (1))) = x(2)) = q12(q23q (1) 31 + (1− q23)(1− q(1)31 ) m ) (12)
Case 1.2. For the S1 ↔ S2 path we have Pr(T d12(x(1)) 6= x(2)) = 1−q12. Let y(2) ∈ S2 denote this incorrect translation. Now we compute Pr(T d31(T d 23(x
(2))) = y(1)). There are three cases depending on the translation at S3: x(3), y(3), and others. They are computed as follows.
Pr(T d31(T d 23(y (2))) = x(1)|T d23(x(2)) = x(3)) = q (1) 31
Pr(T d31(T d 23(y (2))) = x(1)|T d23(x(2)) = y(3)) = 1− q(1)31 m
Pr(T d31(T d 23(y (2))) = x(1)|T d23(x(2)) 6= x(3), y(3)) = 1− q(1)31 m
Using the law of total probability we have
Pr(T d31(T d 23(y
(2))) = x(1)) = q (1) 31 (1− q23) m + q23(1− q(1)31 ) m + (m− 1)(1− q23)(1− q(1)31 ) m2
= m(q32 + q
(1) 31 − 2q23q (1) 31 ) + (m− 1)(1− q23)(1− q (1) 31 )
m2
= q23 + q
(1) 31 − (m+ 1)q23q (1) 31 +m− 1
m2
Then the probability of Case 1.2 is
Pr(T d12(x (1)) 6= x(2), T d31(T d23(T d12(x(1)))) = x(1)) =
(1− q12)(q23 + q(1)31 − (m+ 1)q32q (1) 31 +m− 1)
m2 (13)
Case 2. The probability of Case 2 is simply the complement of Case 1.
Pr(T d31(T d 23(T d 12(x (1)))) 6= x(1)) = 1− Pr(T d31(T d23(T d12(x(1)))) = x(1))
=1− q12(q23q(1)31 + (1− q23)(1− q(1)31 ) m )− (1− q12)(q23 + q (1) 31 − (m+ 1)q23q (1) 31 +m− 1) m2 .
(14)
Then the accuracy of this triple learning is
pm12 = Pr(T d 12(x (1)) = x(2), T d31(T d 23(x (2))) = x(1)) + α′ Pr(T d31(T d 23(T d 12(x (1)))) 6= x(1)), (15)
where α′ is defined in equation 8. equation 10 is obtained by substitute equation 12 and equation 14 into equation 15.

heading: D MULTIPATH DUAL LEARNING FRAMEWORK
text: The algorithm of multipath dual learning is shown in Algorithm 2.
Algorithm 2: Multi-path Dual Learning Framework 1 Input: Samples from spaces S1 . . . Sk, initial translators T12, T21 and T1i, Ti1 ∀i = 3, . . . ,K;
learning rates η; 2 Train each of T12, T21 and T1i, Ti1 ∀i = 3, . . . , k by dual learning; 3 Randomly sample a k from {3, 4, · · · ,K}; randomly sample one x(1) ∈ S1 and one x(2) ∈ S2; 4 Sample one x̂(k) ∼ T1k(x(1)), x̂(2) ∼ Tk2(x̂(k)); x̃(k) ∼ T2k(x(2)) and x̂(2) ∼ Tk2(x̃(k)); 5 Update the parameters of T12 and T21, denoted as θ12 and θ21, as follows:
θ12 ← θ12 − η∇θ12 logP (x̂(2)|x(1); θ12); θ21 ← θ21 − η∇θ21 logP (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
∇θ12DKL(P (·|x(1);Tk2 ◦ T1k)‖P (·|x(1); θ12)) ;∇θ21DKL(P (·|x(1);Tk2 ◦ T1k)‖P (·|x(1); θ12)). (17)
The reason is shown as follows. For any given x(1) ∈ S1,
min θ12
DKL(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) , (18)
which is equivalent to
max θ12 ∑ x(2)∈S2 P (x(2)|x(1); θ1k, θk2) logP (x(2)|x(1); θ12)
= ∑
x(2)∈S2 ∑ x(k)∈Sk P (x(2), x(k)|x(1); θ1k, θk2) logP (x(2)|x(1); θ12)
= ∑
x(2)∈S2 ∑ x(k)∈Sk P (x(k)|x(1); θ1k, θk2)P (x(2)|x(k), x(1); θ1k, θk2) logP (x(2)|x(1); θ12)
= ∑
x(2)∈S2 ∑ x(k)∈Sk P (x(k)|x(1); θ1k)P (x(2)|x(k); θk2) logP (x(2)|x(1); θ12)
=Ex(k)∼P (·|x(1);θ1k)Ex(2)∼P (·|x(k);θk2) logP (x (2)|x(1); θ12).
(19)
Therefore, we can first sample x̂(k) from P (·|x(1); θ12), then sample x̂(2) from P (·|x̂(k); θk2), and then maximize logP (x̂(2)|x(1); θ12). Obviously, −∇θ12 logP (x̂(2)|x(1); θ12) is the unbiased estimator of ∇θ12DKL(P (·|x(1); θ1k, θk2)‖P (·|x(1); θ12)). The performance of multipath dual learning is shown in 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.

heading: E DERIVATION OF CYCLE DUAL LEARNING ALGORITHM
text: We follow the notations used in Appendix D. Let R(x(2)) denote the event that after passing S2 → Sk → S1 → S2, x(2) is reconstructed to x(2). We have that
logP (R(x(2))) = logP (x(2)|start from x(2); θ2k, θk1, θ12) = ∑
x(k)∈Sk ∑ x(1)∈S1 logP (x(2), x(1), x(k)|start from x(2); θ2k, θk1, θ12)
= ∑
x(k)∈Sk ∑ x(1)∈S1 logP (x(1), x(k)|start from x(2); θ2k, θk1)·
P (x(2)|start from x(2), x(1), x(k); θ2k, θk1, θ12) ≥ ∑
x(k)∈Sk ∑ x(1)∈S1 P (x(1), x(k)|x(2); θ2k, θk1) logP (x(2)|start from x(2), x(1), x(k); θ2k, θk1, θ12)
= ∑
x(k)∈Sk ∑ x(1)∈S1 P (x(1), x(k)|x(2); θ2k, θk1) logP (x(2)|x(1); θ12)
= ∑
x(k)∈Sk ∑ x(1)∈S1 P (x(k)|x(2); θ2k)P (x(1)|x(k); θk1) logP (x(2)|x(1); θ12)
=Ex(k)∼P (·|x(2);θ2k)Ex(1)∼P (·|x(k));θk1 logP (x (2)|x(1); θ12).
(20) Then, we can use the algorithm proposed in Algorithm 1 to solve the above optimization problem, i.e., min− logP (R(x(2))).

heading: F THEORETICAL ANALYSIS FOR MUTIPATH DUAL LEARNING
text: We define q(1)32 = PrX(3)∼Td13(X(1))(T d 32(x (3)) = x(2)), which as the accuracy of T d32 when the sentence in S3 is translated from a random sentence in S1. This is analogous to reconstruction accuracy, and is reduced to the reconstruction accuracy when S2 = S1. 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: T12(x(1)) = T32(T13(x(1))); Case 2: T12(x(1)) 6= T32(T13(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:
α′ = Pr(Tm12(x (1)) = x(2), Tm32(T m 13(x (1))) = x(2)|Case 2) β′ = Pr(Tm12(x
(1)) 6= x(2), Tm32(Tm13(x(1))) = Tm12(x(2))|Case 2) γ′ = Pr(Tm21(T m 12(x (1))) 6= x(1)|Case 2), (21)
where Case 2 denotes the condition T12(x(1)) 6= T32(T13(x(1))) and superscripts d andm 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 d13 and T d 32 are independent translators before multipath learning. That implies,
Pr(T d13(x (1)) = x(3), T d32(T d 13(x (1))) = x(2)) = Pr(T d13(x (1)) = x(3), T d32(x (3)) = x(2)) = q13q (1) 32 (22) Then we have the following theorem, which focuses one the triangle structure containing only S1, S2, and S3. The more general case can be viewed as adding one path a time so Theorem 3 can be applied. Theorem 3. Given languages spaces S1, S2, and S3, where the objective is to train a translator that maps from S1 to S2, the accuracy of two-path learning (Figure 1) outcome is
pm12 = q12(1− α′)(q13q (1) 32 + (1− q13)(1− q(1)32 ) m )
+ α′(1− (1− q12)(q13 + q (1) 32 − (m+ 1)q13q (1) 32 +m− 1)
m2 ) (23)
under Assumption 2.
Proof. Similar to the analysis of Theorem 1, we focus on the mapping from x(1) ∈ S1 to S2 and consider the following two cases:
Case 1: T d12(x (1)) = T d32(T d 13(x (1))); Case 2: T d12(x
(1)) 6= T d32(T d13(x(1))). We first characterize the probability of Case 1.
Case 1: According to whether the translation in S2 is correct, Case 1 can be partitioned into two subcases:
Case 1.1: T d12(x (1)) = x(2), T d23(T d 13(x (1))) = x(2);
Case 1.2: T d12(x (1)) 6= x(2), T d23(T d13(x(1))) = T d12(x(1)).
Case 1.1. For the path S1 ↔ S2, we have
Pr(T d12(x (1)) = x(2)) = q12.
For the path S1 ↔ S3 ↔ S2, since we only care about the translation in S2, we have
Pr(T d32(T d 13(x (1))) = x(2))
= Pr(T d13(x (1)) = x(3)) Pr(T d32(T d 13(x (1))) = x(2)|T d13(x(1)) = x(3)) + Pr(T d13(x (1)) 6= x(3)) Pr(T d32(T d13(x(1))) = x(2)|T d13(x(1)) 6= x(3))
=q13q (1) 32 + (1− q13)(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 d12(x (1)) = x(2), T d23(T d 13(x (1))) = x(2)) = q12(q13q (1) 32 + (1− q13)(1− q(1)32 ) m ) (24)
Case 1.2. For the S1 ↔ S2 path we have Pr(T d12(x(1)) 6= x(2)) = 1−q12. Let y(2) ∈ S2 denote this incorrect translation. Now we compute Pr(T d32(T d 13(x
(1))) = y(2)). There are three cases depending on the translation at S3: x(3), y(3), and others. They are computed as follows.
Pr(T d32(T d 13(x (1))) = y(2)|T d13(x(1)) = x(3)) = 1− q(1)32 m
Pr(T d32(T d 13(x (1))) = y(2)|T d13(x(1)) = y(3)) = q (1) 32
Pr(T d32(T d 13(x (1))) = y(2)|T d13(x(1)) 6= x(3), y(3)) = 1− q(1)32 m
Using the law of total probability we have
Pr(T d32(T d 13(x
(1))) = y(2)) = q13(1− q(1)32 ) m + q (1) 32 (1− q13) m + (m− 1)(1− q13)(1− q(1)32 ) m2
= m(q13 + q
(1) 32 − 2q13q (1) 32 ) + (m− 1)(1− q13)(1− q (1) 32 )
m2
= q13 + q
(1) 32 − (m+ 1)q13q (1) 32 +m− 1
m2
Then the probability of Case 1.2 is
Pr(T d12(x (1)) 6= x(2), T d23(T d13(x(1))) = T d12(x(1)))
= (1− q12)(q13 + q(1)32 − (m+ 1)q13q (1) 32 +m− 1)
m2 (25)
Case 2. The probability of Case 2 is simply the complement of Case 1.
Pr(T d12(x (1)) 6= T d32(T d13(x(1)))) = 1− Pr(T d12(x(1)) = T d32(T d13(x(1))))
=1− q12(q13q(1)32 + (1− q13)(1− q(1)32 ) m )− (1− q12)(q13 + q (1) 32 − (m+ 1)q13q (1) 32 +m− 1) m2 .
(26)
Then the accuracy of this two-path learning is
pm12 = Pr(T d 12(x (1)) = x(2), T d23(T d 13(x (1))) = x(2)) + α′ Pr(T d12(x (1)) 6= T d32(T d13(x(1)))), (27)
where α′ is defined in equation 21. equation 23 is obtained by substitute equation 24 and equation 26 into equation 27.
The role of T d12. The accuracy increases as q12 increases. So a good original translator trained from dual learning is desirable. However, if T d12 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(Td12(x (1))=x(2),Td23(T d 13(x (1)))=x(2))
Pr(Td12(x (1)) 6=x(2),Td23(Td13(x(1)))=x(2))
and define Γ′ = γ′ Pr(T d12(x (1)) 6= T d32(T d13(x(1)))).
Then the accuracy simplifies to
pm12 = α′(1− Γ′) α′ + β′ = q12(q13q (1) 32 + (1−q13)(1−q(1)32 ) m )(1− Γ ′)
q12(q13q (1) 32 + (1−q13)(1−q(1)32 ) m ) + (1−q12)(q13+q(1)32 −(m+1)q13q (1) 32 +m−1) m2
= 1− Γ′
1 + (1−q12)(q13+q(1)32 −(m+1)q13q (1) 32 +m−1)
mq12(mq13q (1) 32 +(1−q13)(1−q (1) 32 ))
= 1− Γ′
1 +M 1−q12q12
where M = q13+q (1) 32 −(m+1)q13q (1) 32 +m−1
m(mq13q (1) 32 +(1−q13)(1−q (1) 32 ))
. When γ′ = 0 (and therefore Γ′ = 0) and M = 1, it
simplifies to q12, which is the accuracy of dual learning. Observing pm12 increases as M decreases, we let M < 1 so that pm12 > q12. We have
q13 + q (1) 32 − (m+ 1)q13q (1) 32 +m− 1
m(mq13q (1) 32 + (1− q13)(1− q (1) 32 ))
< 1
((m+ 1)q13 − 1)((m+ 1)q(1)32 − 1) > 0
when q13, 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, the two-path learning outperforms dual learning.

Review summaries:
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.