On Learning Language-Invariant Representations
for Universal Machine Translation
Han Zhao, Junjie Hu, Andrej Risteski{han.zhao, junjieh, aristesk}@cs.cmu.edu
Carnegie Mellon University

Recent Success of Neural Machine Translation

3545

Machine Translation, ~3M parallel sentences [Cho et al. 2014; Devlin et al. 2014]2

Neural Machine Translation is Data Hungry

Figure from [Gu et al. 18]

SourceEnglishEnglishFinnishRomanian

TargetFrenchGermanEnglishEnglishCorpora size
~3M
~1.92M~1.96M~400K

BLEU Scores~40~35~34~30

WMT ’16-19, Europarl Parallel Corpus 3

Typical Pipeline of Multilingual Machine Translation•Separate MT systems: Hard to maintain all systems•Pivot methods: src-to-pivot & pivot-to-tgt translations

Japanese
EnglishMachine Translation
SystemJapanese
Machine Translation
SystemJapanese

Machine Translation
SystemMachine Translation
SystemKoreanEnglishKoreanMachine translation by triangulation: Making effective use of multi-parallel corpora, [Cohn et al 07]

4

Cross-Lingual Representations by Neural Models•Language similarity: similar words, grammar, order.

•Shared space: learning word/sentence
representations jointly

Photo credit: https://ai.googleblog.com/2016/11/zero-shot-translation-with-googles.html
5Why Universal Machine Translation (UMT)?
•Single model: many-to-one, one-to-many•

Zero-shot translation: improve low-resource translation

Johnson et al. Google's Multilingual Neural Machine Translation System: Enabling Zero-Shot Translation, TACL 2017.

6

Recent Advances of UMT•

Language coverage: 100+ languages in Google’s M4•

Web-mined data: 25 billion examples•Quality: +5 BLEU score over all 100+ languages

Massively Multilingual Neural Machine Translation in the Wild: Findings and Challenges [Arivazhagan et al. 19]

7

Challenge: Theoretical Understanding of UMT
Despite the empirical success, theoretical understandingis only nascent- Translation Error: Is there a performance limit evenwith unlimited amount of computation & data
- Sample Complexity: How many language pairs arerequired to train UMT?
Japanese

KoreanQuality?
Universal MachineTranslation System

EnglishGerman8

Challenge: Theoretical Understanding of UMT
Despite the empirical success, theoretical understandingis only nascent- Translation Error: Is there a performance limit even withunlimited amount of computation & data- Without assumption on the parallel corpus used fortraining, at least one translation task has to incur a largeerror- Sample Complexity: How many language pairs arerequired to train UMT?
- Under an encoder-decoder generative assumption of thedata, a linear number of translation pairs suﬃce for thepurpose of UMT
9

A Theoretical Model for UMT
Let L = {English, French, German, Chinese, …} be the setof all languages of interest.
- For each L 2 L, we associate with L an alphabet ⌃L⇤- A sentence x in L is a sequence of symbols from ⌃L, i.e., x 2 ⌃L0L,
L- For a pair of languages, we use DL,L0 to denote the joint
0distribution over the parallel sentence pairs from L and L

JapaneseKorean

Universal MachineTranslation SystemEnglish

German10

A Theoretical Model for UMT
Problem Setting:-0L,
LFor each pair of languages, there exists a true translator⇤⇤⇤
fL!L0 : ⌃L ! ⌃L0-Given a translator f from L to L0, we use the 0-1 loss to measure thetranslation quality w.r.t. the true translator:
L!L0⇤ErrD(f ) := ED [`(f (X), fL!L0 (X))]
00`(x,x)=0x=xwhereiﬀ.

There exists a perfect translator that translates input sentence fromany language to a target language L:fL⇤ (x) =X

L0 2L

I(x 2 ⌃⇤L0 ) · fL⇤ 0 !L (x)Can we recover the perfect translator through UMT?
11

Universal Machine Translation
Universal Language Mapping:A function mapping g :[i2[K]⌃⇤Li ! Z is called universal ifg] Di = g] Dj , 8i 6= j

Diﬀerent languages have the same distribution under representation Z12An Impossibility Theorem
A simple warm-up (Two-to-One):
Theorem (informal): Consider a restricted setting of universal machinetranslation task with two source languages and one target language. If g isa universal language mapping, then for any decoder h : Z ! ⌃⇤L ,L1 !L
0 !LErrL(hg)+Err(h g)
D0D1Translation errors from L0 , L1 to LdTV (DL0 ,L (L), DL1 ,L (L)).

Distance between sentence
distributions over L

Uncertainty Principle: UMT has to make a large error
on at least one translation task13

An Impossibility Theorem
A simple warm-up (Two-to-One):
Theorem (informal): Consider a restricted setting of universal machinetranslation task with two source languages and one target language. If g isa universal language mapping, then for any decoder h : Z ! ⌃⇤L ,L1 !L0 !LErrL(hg)+Err(h g)
D0
D1Translation errors from L0 , L1 to LdTV (DL0 ,L (L), DL1 ,L (L)).

Distance between sentence
distributions over L-This is an information-theoretic lower bound, i.e., algorithm-independent-The theorem still holds even if we use diﬀerent encoders for diﬀerent
languages, but wouldn’t hold any more if we use target-dependentdecoder!

-The lower bound gets larger whenever target data are dissimilar between
diﬀerent translation tasks
14

An Impossibility Theorem
In general (Many-to-One):
Maximum Translation Error:
max

i2[K]i !LErrL(hDi

Average Translation Error:
1 X
i !LErrL(h g)
DiKi2[K]g)1K(K1max E(i, j)
2 i6=jX1) i<jL

E(i, j)
L !LErrD4L !LErrD1
14L !LErrD5

5L !LE(i, j) measures how diﬀerent two translation

tasks are:E(i, j) := dTV (DLi ,L (L), DLj ,L (L))

ErrD2

2L1L5L !LErrD3

3

L4

G=
L2

L315

A Generative Model of UMT
The impossibility theorem holds in the worst case without any assumption
on the data generating distribution of parallel corpus. What if we assume
an encoder-decoder generative process?

Representation Space Z =E0E1 D1D0L0L1L2D(Z)

E2
D2···

We assume that Ek 2 GLd (R), Dk = Ek 1 , 8k 2 [K]EKDKLK16

A Generative Model of UMT
Why this assumption on data generative process helps?

Representation Space Z =E0

E1 D1E2D0L0L18i, j 2 [K],i !LErrL(hDi

D(Z)

L2
Lj !Lg) + ErrDj (hD2EK···g)

DK

LKdTV DLi ,L (L), DLj ,L (L) = 0

The lower bound still holds, but it gracefully reduces to 0 under thisencoder-decoder assumption on data generative process.

17How Many Language Pairs Suﬃces?
2⌦(K) language pairs, one for each pair.
Naively, one might think we need

Our result: under some mild assumptions, only a linear number O(K) oftranslation pairs suﬃces!

Translation Graph: H- Each node = a language- Two nodes are connected if we see the corresponding translation pair
- H is assumed to be connected: we need to see every language atleast once
- The diameter of H is bounded by K

L0

L1

L2LK18

How Many Language Pairs Suﬃces?
Translation Graph: H- Each node = a language- Two nodes are connected if we see the corresponding translation pair
- H is assumed to be connected: we need to see every language at leastonce- The diameter of H is bounded by K
Theorem (informal): Let diam(H) be the diameter of the translation graph
H , then for any pair of language Li , Lj , the translation error has thefollowing upper bound:"(Êi , Êj )  ⇢ · diam(H) · ✏2L0

L1L2LK19

How Many Language Pairs Suﬃces?
Theorem (informal): Let diam(H) be the diameter of the translation graph
H , then for any pair of language Li , Lj , the translation error has thefollowing upper bound:"(Êi , Êj )  ⇢ · diam(H) · ✏2-"(Êi , Êj ) is measured w.r.t. the ground truth encoder-decoder-⇢ is the Lipschitz-constant of the ground truth encoder and decoder-✏ is the maximum error on each seen translation pair-2O(1/✏) parallel
For a specified translation error ✏, a corpora containing

sentences suﬃces

L0We use a epsilon-net argument
to prove this result✏L1✏L2✏LK20

Summary
Without data generating assumption: An Impossibility Theorem,
UMT has to incur a large error on at least one translation pair.
Theorem (informal): Consider a restricted setting of universal machinetranslation task with two source languages and one target language. If g is a universal⇤language mapping, then for any decoder h : Z ! ⌃L ,L1 !L
0 !L
ErrL
(hg)
+Err(h g)
D0
D1dTV (DL0 ,L (L), DL1 ,L (L)).

With a natural data generating assumption:Linear number of translation pairs suﬃces!
Theorem (informal): Let diam(H) be the diameter of the translation graph H , then forany pair of language Li , Lj , the translation error has the following upper bound:"(Êi , Êj )  ⇢ · diam(H) · ✏2L0✏L1L2✏✏LK21