A Theory of Unsupervised Translation Motivated by Understanding Animal Communication
Authors: Shafi Goldwasser
David Gruber
Adam Tauman Kalai
Orr Paradise
Venue: NeurIPS 2023 poster (2023)
Keywords: Theory
Unsupervised Machine Translation
TL;DR: A theoretical framework for analyzing the data requirements of unsupervised machine translation, making minimal assumptions on the source language.

Abstract: Neural networks are capable of translating between languages—in some cases even between two languages where there is little or no access to parallel translations, in what is known as Unsupervised Machine Translation (UMT). Given this progress, it is intriguing to ask whether machine learning tools can ultimately enable understanding animal communication, particularly that of highly intelligent
animals. We propose a theoretical framework for analyzing UMT when no parallel translations are available and when it cannot be assumed that the source and target corpora address related subject domains or posses similar linguistic structure. We
exemplify this theory with two stylized models of language, for which our framework provides bounds on necessary sample complexity; the bounds are formally proven and experimentally verified on synthetic data. These bounds show that the error rates are inversely related to the language complexity and amount of common ground. This suggests that unsupervised translation of animal communication may be feasible if the communication system is sufficiently complex.

A Theory of Unsupervised Translation Motivated by Understanding Animal Communication
Shafi Goldwasser' UC Berkeley & Project CETI
David E. Gruber"
Project CETI
shafi wol.dvaaserbbeeeeeeeyy...
david@projecttcet... org
Adam Tauman Kalai' Microsoft Research & Project CETI adam@kal.c
Orr Paradise"
UC Berkeley & Project CETI
orrpfeecs www..eeee.......... edu
Abstract
Neural networks are capable of translating between languages some cases even between two languages where there is little access to parallel trans- lations, in what is known as Unsupervised Machine Translation (UMT). Given this progress, it is intriguing ask whether machine learning tools can ultimately enable understanding animal communication, particularly that of highly intelligent animals. We propose a theoretical framework for analyzing UMT when no parallel translations are available and when it cannot be assumed that the source and target corpora address related subject domains posses similar linguistic structure. We exemplify this theory with two stylized models of language, for which our frame- work provides bounds on necessary sample complexity; the bounds are formally proven and experimentally verified on synthetic data. These bounds show that the eиror rates are inversely related to the language complexity and amount of common ground. This suggests that unsupervised translation of animal communication may feasible if the communication system is sufficiently complex.
Introduction
Recent interest in translating animal communication 2 9 has been motivated by breakthrough performance of Language Models (LMs). Empirical work has succeeded in unsupervised translation between human- language pairs such as English-Frent French 223 5 and programming languages such as Python-Java B33. Key to this feasibility seems to be the fact that language statistics, captured by a LM (a probability distribution over text), encapsulate more than just grammar. For example, though both are grammatically correct, The calf nursed from its mother is more than 1,000 times more likely than The calf nursed from its father?
Given this remarkable progress, it is natural to ask whether it is possible to collect and analyze animal communication data, aiming towards translating animal communication to a human language description. This particularly interesting when the source language may be of highly social and intelligent animals, such as whales, and the target language is a human language, such English.
Challenges. The first and most basic challenge is understanding the goal, question with rich history of philosophical debate [38]. To define the goal, we consider a hypothetical ground-truth translator. As a thought experiment, consider "mermaid" fluent in English and the source language
Authors listed alphahetically.
Probabilitiis computed using the GPT-3 API PPPhttsss///peeaa wttp:ii.oo//pp/pp/ text-davinci-02 model.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Have you seen any orcas today? I just got back from the reet.
Have you seen mom? I just returned from the ocean basin.
Hat out hat dsigh!!! p(Ci) Rs 48
p(A1) R 10 18
p(Bi) = 10-18
At the reef, there were lot of sea turtles. p(A) z 22
At the reef, there were lot of bicycle turtles. p(B) 10
OMG and. P(C)
Figure 1: LMs identify incoherent text. The probabilities of three two- wwo-parggraph texts computed using the GPT-3 API. The probabilities of just the first paragraphs A1, B1, C1 are also shown. Although p(A1) ~ p(B and the second paragraphs of A and B are identical, overall p(A) >> p(B) due to coherence between the paragraphs. C. is gibberish.
(e.g. sperm whale communication). Such mermaid could translate whale vocalizations that English naturally expresses. An immediate worry arises: what about communications that the source language may have about topics for which English has no specific words? For example, sperm whales have sonar sense which they use to perform echolocation. In that case, lacking a better alternative, the mermaid may translate such conversation as (something about echolocation)
Thus, we formally define the goal to be to achieve translations similar to those that would be output by a hypothetical ground-trum -ruth translator. While this does not guarantee functional utility, it brings the general task of unsupervised translation and the specific task of understanding animal communication into the familiar territory of supervised translation, where one can use existing error metrics to define (hypothetical) error rates.
The second challenge is that animal communication is unlikely to share much, if any, linguistic structure with human languages. Indeed, our theory will make no assumption on the source language other than that it is presented in a textual format. That said, one of our instantiations of the general theory (the knowledge graph) shows that translation is easier between compositional languages.
The third challenge is domain gap, i.e. that ideal translations of animal communications into English would be semantically different from existing English text, and we have no precise prior model of this semantic content. (In contrast, the distribution of English translations of French text would resemble the distribution of English text.) Simply put: whales do not "talk" about smartphones. Instead, we assume the existence of broad prior that models plausible English translations of animal communication. LMs assign likelihood an input text based not only on grammatical correctness, but also on agreement with the training data. In particular, LMS trained on massive and diverse data, including some capturing facts about animals, may be able reason about the plausibility of candidate translation. See Figure I and the discussion in Appendix H
1.1 Framework and results
Fl is a function f: X' + y that translates source text x E X' into the target language f(x) E y. We focus on the easier-to-analyze case of lossless translation, where f is invertible (one-to-one) denoted by Se X' + y. See Appendix I.I for an extension to lossy translation.
A translator
We will consider a parameterized family of translators {fe: X - VYoge, with the goal being to learn the parameters 8 E è of the most accurate translator. Accuracy (defined shortly) is measured with respect to hypothetical ground-truth translator denoted by f. X' V. We make realizability assumption that the ground-truth translator can be represented in our family, i.e., E e.
The source language is defined as a distribution over x E X, where (u(z) is the likelihood that text æ occurs in the source language. The error of a model 0 E will be measured in terms of err (0) := [fa & fa (x)), or at times general bounded loss function L(O). Given μ and fx, will be useful to consider the translated language distribution t over y by taking f. (x) for x ~ p.
In the case of similar source and target domains, one may assume that the target language distribution y/ over close to r. This a common intuition given for the "magic" behind why UMT sometimes
'A better description might possible. Consider the fact that some people who are congenitally blind comprehend vision-related verbs as accurately as sighted people (8)
In this work, translator refers to the function f: X + y while translation refers to output y =(x).

---

works: for complex asymmetric distributions, there may a nearly unique transformation in { leee that maps j to something close (namely f. which maps μ to r). A common approach in UMT is to embed source and target text as high-dimensional vectors and learn low-complexity transformation, e.g., rotation between these Fuclidean spaces. Similarly, translator complexity will also play an important role in our analysis.
Priors. Rather than assuming that the target distribution v is similar to the translated distribution T, we will instead assume access to broad prior p over y meant to capture how plausible translation is, with larger p(y) indicating more natural and plausible translation. Appendix H discusses one way a prior oracle can be created, starting with an LM & v learned from many examples in the target domain, and combined with a prompt, in the target language, describing the source domain.
We define the problem of unsupervised machine translation (with prior) to be finding accurate 0 E + given m iid unlabeled source texts 21...., ~ I and oracle access to prior p.
MLE. Our focus is on the Maximum- L Likelihood Estimator (MLE), which selects model parameters 0 E θ that (approximately) maximize the likelihood of translations II, (ff(2z)))
Definition 1.1 (MLE). Given input a translator family Us: X + Yese, samples , X and a distribution p over Y, the MLE outputs
MLE (11, T2, Tm == argmin
log p(fo(z:))
OE@
If multiple 9 have equal empirical loss, it breaks ties, say, lexicographically.
We note that heuristics for MLE have proven extremely successful in training the breakthrough LMs, even though MLE optimization is intractable in the worst case.
Next, we analyze the efficacy of MLE in two complementary models of language: one that is highly structured (requiring compositional language) and one that is completely unstructured. These analyses both make strong assumptions on the target language, but make few assumptions about the source language itself. In both cases, the source distributions are uniform over subsets of X, which (informally) is the "difficult" case for UMT as the learner cannot benefit from similarity in text frequency across languages. Both models are parameterized by the amount of "common ground" between the source language and the prior, and both are randomized. Note that these models are not intended to accurately capture natural language. Rather, they illustrate how theory can be used to study the effect of language similarity and complexity on data requirements for UMT.
Knowledge graph model. Our first model consists of a pair of related knowledge graphs, in which edges encode knowledge of binary relations. Each edge yields text that described the knowledge it encodes. For example, in Figure 2 edges encode which animal A eats which other animal B, and text is derived as a simple description A eats B
Formally, there are two Erdös Erdös-Rényi random digraphs. The target graph is assumed to contain n nodes, while the source graph has r < n nodes corresponding to an (unknown) subset of the n target nodes. The model has two parameters: the average degree d in the manddomly-genertted target language graph, and the agreement a E (0. between the source and the target graphs. Here a = 1 complete agreement on edges in the subgraph, while a = 0 complete independence. We assume the languages use compositional encoding for edges, meaning that they encode given edge by encoding both nodes, so we may consider only |+| = nl/(n- -r) translators consistently mapping the source nodes to the target nodes, which is many fewer than the number of functions f X y mapping the | = Or source edges into the y = O(n²) target edges. Human languages as well as the communication systems of several animals are known to be compositional (39
We analyze how the error of the learned translator depends on this "common knowledge" ac
Theorem 1.2 (Theorem 3.2 simplified). Consider source language μ and a prior p generated by the knowledge graph model over r source nodes, n target nodes, average degree d and agreement
'In future work, would interesting to consider k-ary relations (hypergraphs) or multiple relations. A system is compositional if the meaning of an expression is determined by the meaning of its parts.
3

---

siarc
Welsh sentences
English sentences sharks eat salmon. salmon eat herring. sharks eat sharks. herring eat mysidacea.
mysidacea
bwytaodd siarc siarc. bwytaodd eog bennog. bwytaodd siarc eog.
herring
eog
bennog
salmon
sharks
Figure 2: An illustration of the knowledge graph model. In this example, the Welsh graph is an exact subgraph of the English knowledge graph, but model allows for differences.
parameter a. Then, with least 99% probability, when given m source sentences It I1y,.. Z'm and access to a prior p. MLE outputs a translator 9 with error
log 1 add
log
err(0) S0
a
m
The second term decreases to 0 Note that the first term does not decrease with the number of samples. The average degree d is rough model of language complexity capturing per-node knowledge, while the agreement parameter captures the amount of common ground. Thus, more complex languages can be translated (within given error rate) with less common ground. Even with m oo source data, there could still be errors in the mapping. For instance, there could be multiple triangles in the source and target graphs that lead ambiguities. However, for complex knowledge relations (degree d >>> 1/a²), there will be few such ambiguities.
rate, similar (noisy) generalization bounds [30]].
Figure 2 illustrates example of four English sentences and three sentences (corresponding to an unknown subset of three of the English sentences) Welsh. For UMT, one might hypothesize that bwytaodd means eat because they both appear in every sentence. One might predict that siarc means shark because the word siarc appears twice in a single Welsh sentence and only the word shark appears twice in English sentence. Next, note that eog may are the only other words occurring with siarc and shark. Similar logic suggests that bennog means herring. Furthermore, the word order consistently permuted, with subject-verb-object in English and warb-subject-objee in Welsh. This translation is indeed roughly correct. This information is encoded in the directed graphs as shown, where each node corresponds an animal species and an edge between two nodes is present if the one species eats the other.
salmon because they
"Common nonsense" model. The second model, the common nonsense model, assumes linguistic structure on the source language. Here, we set out to capture the fact that the translated language f o f+ and the prior p share some common ground through the fact that the laws of nature may exclude common "nonsense" outside both distributions' support.
Earlier work has justified alignment for UMT under the intuition that the target language distribution v is approximated by a nearly unique simple transformation, e.g., a rotation, of the source distribution μ. However, for prior p, work suggests that UMT may also be possible if there is nearly unique simple transformation that maps T so that contained in p. Figure B illustrates such a nearly unique rotation the UMT "puzzle" of finding transformation fo of μ which is contained within is subtly different from finding an alignment.
In the common nonsense model, and are uniform over arbitrary sets 7 C P P from which common a E (0, 1/2] fraction of text removed (hence the name "common nonsense"). Specifically, r and are defined to be uniform over 7 = T \ S, P P\ S. respectively, for a set S sampled by including each y E y with probability a.
We analyze the error of the learned translator function of the amount of common nonsense:
Theorem 1.3 (Theorem 3.4, simplified). Consider source language μ and a prior p generated by the common nonsense model over [T] source texts and common-nonsenne parameter and a translator family parameterized by (O). Then, with at least 99% probability, when given m source sentences T1 ... F' and access to a prior p. MLE outputs translator with error
err (0) = Pr x [fa()) # f.(x)) =0 min(m, (T')
In |

---

X
y
y
f*
V
μ
Figure 3: The previous intuition behind UMT has the distributions of target language (middle) close to ground-truth translations т, which is assumed to be a low-complexity transformation (in this example a rotation) of the source language μ (left). When source and target are not aligned, restricting to prior region (right) allows for translation, as long as there are enough "nonsense" texts (black regions) that there is nearly unique rotation of μ that is contained in p. For example, both distributions may assign negligible probability to nonsensical texts such as died times tomorrow. (In this toy example, is uniform over two-dimensional shape that happens look like whale.)
Theorem 3.5 gives a nearly matching lower bound. Let us unpack the relevant quantities. First, we think of as measuring the amount of agreement or common ground required, which might be small constant. Second, note that [T'] is a coarse measure of the complexity of the source language, which requires total of Ô(TT)) bits to encode. Thus, the bound suggests that accurate UMT requires the translator be simple, with description length that an a-factor of the language description length, and again captures the agreement between т, p. Thus, even with limited common ground, one may able to translate from a source language that is sufficiently complex. Third, for simplicity, we require X, X C (0, 1 to be finite sets of binary strings, so WLOG @ may be also assumed to be finite. Thus, log2 ( is the description length, a coarse but useful complexity measure that equals the number of bits required to describe any model. (Neural network parameters be encoded using a constant number of bits per parameter.) Appendix 1.2 discusses how this can be generalized to continuous parameters.
Importantly, we note that (supervised) neural machine translators typically use far fewer parameters than LMs |
To see why, consider the example of the nursing calf (page 1) and the fact that a translator needs not know that calves nurse from mothers. On the other hand, such knowledge is essential to generate realistic text. Similarly, generating realistic text requires maintaining coherence between paragraphs, while translation can often be done at the paragraph level.
As warm-up. we include simplified version of the common nonsense model, called the tree-based model (Appendix B.T. in which texts are constructed word-by-word based on tree structure.
Comparison to supervised classification. Consider the dependency m, the number of training examples. Note that the classic Occam bound O L log (+) is what one gets for noiseless supervised classification, that is, when one is also given labels y, = f. (z;) at training time, which is similar to Theorem 1.3, and give (m 1/2) bounds for noisy classification as in Theorem 1.2 Furthermore, these bounds apply to translation, which can be viewed special case of classincation with many classes V. Thus, both cases, the data dependency on m quite similar to that of classification.
Experiments. We validate our theorems generating synthetic data from mandomly-generatee lan- guages according to each model, and evaluating translator error function of the number of samples and amount of common ground. The knowledge graph model (Figure left) is used to generate source graph (language) on r 9 nodes to target graph (language) on 10 nodes and average degree d x 5, while varying the agreement parameter a. We also vary r (Figure 4 right) supporting main message: more complex languages can be translated more accurately. For the common nonsense model (Figure 5) we simulate translation of a source language size [T' = 10 while varying the fraction of common nonsense a. Appendix contains details and code.
For example, multilingual model achieves state-of tftte-of-the-r performance using only billion parameters compared to 175 billion for GPT-3 []].
5

---

Knowledge Graph
alpha:
alpha: 0. 66
alpha: 0.33
alpha: 0
Translation error
0.8
0.6
Accuracy
4
0.10 + 0.05
0.4
7
0.74 + 0.08
10
1.00 = 0.00
0.2
#Samples
0
20
40
60
80
Figure 4: Knowledge Graph model experiments, each run twenty seeds with standard errors shown. Left: error of the top-scoring translator vs. number of source samples m. Right: effect of source language complexity (number of source nodes translator accuracy in the knowledge graph model. We report the accuracy of the top-scoring translator after all source edges were input to the learning algorithm, i.e., the number of samples >>
Common Nonsense
alpha: 0.8
alpha: 0.7
alpha: 0.6
alpha: 0.5 alphha: 0.4
alpha: 0.3
alpha: 0.2
alpha: 0.1
alpha:
1
Average translato error
0.8
0.6
0.4
0.2
#Samples
0
40
80
Figure 5: Common Nonsense model. The X-axis is the number source samples m, and the Y-axis
is the average error among plausible translators (that have not been ruled-out far). Each experiment was run on five seeds, with standard error depicted by the shaded area.
Contributions. The first contribution of this work is formalizing and analyzing model of UMT. As an initial work, its value is in the opportunities which it opens for further work more than the finality and tightness/generalityy of its bounds. Our model applies massive domain gap and linguistic distance. We emphasize that this work is only first step in the theoretical analysis of UMT (indeed, there little theoretical work on machine translation in general). Second, we exhibit two simple complementary models for which we prove that: (a) more complex languages require less common ground, and (b) data requirements may not be significantly greater than those of supervised translation (which tends to use less data than training a large LM). These findings may have implications for the quantity and type of communication data that collected for deciphering animal communication and for UMT more generally. They also give theoretical evidence that UMT can be successful and worth pursuing, in lieu of parallel (supervised) data, the case of sufficiently complex languages. All of that said, we note that our sample complexity bounds are information theoretic, that is, they do not account for the computational complexity of optimizing the translator. Finally, animal communication aside, to the best of our knowledge this work is the first theoretical treatment of UMT, and may also shed light on translation between human languages.
low-resource source languages with
The framework formally described Section 2 and is instantiated with models of language in Section 3 (proofs, experiments, and other details deferred to Appendices A to E Key takeaways from this work are presented in Section 4 Related and future work discussed Appen- We illustrate how prompting LMs may give priors in Appendix H Appendix I sketches
Organization.
dices F G

---

generalization of our framework to the settings of lossy translation and infinite translator families. Lastly, Appendix proves sample complexity bounds for the settings of supervised translation.
The General Framework
We use f: + y to denote a 1-1 function, in which (z) * f(x') for all x x x'. For S S X, we write ((S) = {s(x) S). The indicator 1p is if the predicate P holds, and otherwise. The uniform distribution over set S is denoted by (d()), and log = logg denotes base-2 logarithm.
Language and Prior. A source language is distribution j over of possible texts X. Similarly, a target language is distribution v over a set of possible texts y. When clear from context, we associate each language with its corresponding set of possible texts. A prior distribution p translations )' aims to predict the probability of observing each translation. One could naively take p v, but Appendix (I describes how better priors focus on the domain of interest. Intuitively, p(y) measures how "plausible" a translation is. For simplicity, we assume that X C {0, 1 are finite, non-empty sets of binary strings. Appendix 1.2 discusses extensions to infinite sets.
Translators. A translator is a mapping f: X' + V. There is known set of 1-1 functions (Ja: X' - y' we will omit them from the theorem statements and algorithm inputs, for ease of presentation. Like N. the θ is assumed be finite. Appendix I.I considers translators that are not 1-1.
} with parameter Ô. Since parameters assumed to be known and fixed,
Divergence. A translator fe and distribution μ induce a distribution over fe(z), which we denote by o p. The divergence between this distribution and p quantified using the Kullback- Leibler (KL) divergence,
m(x)
m(xx) p(fo(z))
D(0) = o
E anp
log
Σ
[u(x) log
20. 0.
((J((z))
Note that since D(0)= = E Exay Σ p(fo (z;))] H(H), and H(μ) is a constant independent of 0, the MLE of Definition approximately minimizes divergence.
Ground truth. In order to define semantic loss, we consider ground- translator f. for some O We can then define the (ground-truth) translated language T f. и over y, obtained by taking (z) for z μ.. This is similar to the standard realizability assumption, and some of our bounds resemble Occam bounds with training labels y; = ff (x;). ). Of course, the ground translator is not known to the unsupervised learning algorithm. In our setting, we further require that ground-truth translations never have probability under pt:
Definition 2.1 (Realizable prior). (x)=)((((+(x)) = 0] = 0, or equivalently D(*) < oc.
Semantic loss. The semantic loss of a translator is defined with respect semantic difference function &: y x y > [0, 1]. This function, unknown to the learner, measures the difference between two texts from the target language V, with E(y, v) 0 for all y. For a given semantic difference é and ground-truth translator f., we define the semantic loss of a translator fe by
((0)
E [((]()) zmp
Of particular interest to us is the semantic error err(.,),, obtained when is taken to be the 0-1 difference Em (v. ) for all * y. Note that since any semantic difference f is upper bounded by 1, the semantic error apper-bounde any other semantic loss L. That is,
(()) S err(O)
Pr [fo(x) # fx(r)..
z~
Section analyzes this error err(O), which thus directly implies bounds on L()).
7

---

3 Models of Language: Instantiating the General Framework
3.1 Random knowledge graphs
In this section, we define a model in which each text represents an edge between pair of nodes in knowledge graph. Both languages have knowledge graphs, with the source language weakly agrecing with an unknown subgraph of the target language.
We fix X' = X x X = X and y Y x x = y with r= [X] and |Y). The set of translators considered is all mappings from the r source nodes to the n target nodes, namely Oxy = {0 + Y and So (uu, v)) == (0(u), ((w)). The random knowledge graph is parametrized by the number of source nodes r, target node set V, an edge density parameter p E (0, 1) representing the expected fraction of edges present in each graph, and an agreement parameter a E (0, 1] representing the correlation between these edges. In particular, a corresponds to the case where both graphs agree on all edges, and a 0 corresponds to the case where edges in the graphs are completely independent. These parameters are unknown to the learner, who only knows X and Y (and thus X' x=
Definition 3.1 (Random knowledge graph). For natural numberr r S [Y) the KG = KG T,,, a) model determines distribution over sets T, P C. (which determine distributions p and p). The sets T and P are sampled as follows:
1. Set P S y is chosen by including each edge y E y with probability p. independently.
2. Set S C Y of size [S| is chosen uniformly random.
3. Set T S S is chosen as follows. For each edge y E S², independently.
(a) With probability y T if and only if P.
ox, (b) With probability aa, toss another p-biased coin and add y to T if lands on "heads";
that is, y E T with probability p, independently.
It is easy that T C S² and P C Y marginally represent the edges of Erdös-Rényi random graphs Gr.p and Gn.ps respectively. Moreover, the event that y E T is positively correlated with E P: for each y E 5², since with probability a > 0 they are identical and otherwise they are independent. Formally, the equations below deseribe the probability of y E T for each y S after we fix 5 and choosing T S S². Letting g = (1 p). for each y E S2:
Prly E 7] Prly Pl =
Prly E T Pl Prly E P T = a)p
(2)
(1 - a)pg = a0)4
Pr(y $ P
E T Prly $
E P.
(3)
The last equality, shows that the probability of excluding random y T from P is smaller than the probability of excluding a random "incorrect translation" y' * y. Priy & PI= = < (1 aa)g.
We now describe how p, t, are determined from T, P and how μ,, may be chosen complete the
model description. The ground-truth target translated distribution 7 := ((T) is uniform over T., The prior p is uniform over P, and then "smoothed" over the rest of the domain V. Formally,
if
p(v)
DI
if
2JJ
The ground-truth translator E θ is obtained by sampling uniformly random * X + S. Lastly, we take f = U( (T)), which agrees with the definition of 7
Next, state the main theorem for this model, formalizing Theorem 1.2 from the introduction.
FFormally, the KG model outputs T, P which may not determine S if some nodes have zero edges. In that case, we choose randomly among such that fo(x') 2 T. exponentially unlikely event that either or I' is empty, we define both r, p to be the singleton distribution concentrated on (y. y) for the lexicographically smallest Y and to concentrated on (z, x) for f- f It is not difficult to see that MLE selects translator with 0 error.
8

---

Theorem 3.2 (Translatability in the KG model). Fix any m 2 (0. 1), and let r - |r p.p. Then, with probability
over from KG(S.Y,p.a)
64
Gn
2
6n
crr(f) S max
p2
In
8
oog V
m
In
5
where 0 = MLE $2. ...,,,.......................... Fm) is from Definition 1.1 2 0.99,
Simply, for p < 0.99, with probability
log nt 222r
logn
err(0) 0
+
m
The proof, given Appendix D
requires generalizing our theory to priors that have full support. Experimental validation of the theorem is descrihed in Appendix
3.2 Common nonsense model
We next perform "smoothed analysis" of arbitrary LMS μr, p that uniform small amount of randomness, i.e., a small common random set has been removed from both. This shared randomness captures the fact that some texts are implausible in both languages and that this set has some complex structure determined by the laws of nature, which we model as random.
that share
The a-common-nonseen distribution is meta-distribution over pairs (μ, p) which themselves uniform distributions over perturbed versions of P.T. This is inspired by Smoothed Analysis [36]. Recall that (S) denotes the uniform distribution over the set S.
Definition 3.3 (Common nonsense). The a-common-nonsens, distribution D...T with respect to nonempty sets T C P S y is the distribution over (p == ()(PP))).. U(T U(TTS)) where S C formed by removing each y y with probability a, independently
To make this concrete in terms of a distribution μ X, for any ground-truth translator f. X' + y,
similarly define a distribution D.PTT over (n, p) where μ = UTf 8)) is the uniform distribution over the subset of that translates into T. We now state the formal version of Theorem!
Theorem 3.4 (Translatability in the CN model). Let (fe + V x E θ} family of translators,
E O, a. E (0, 1/2], T P _ y, and m 2 1. Then with probability 2 - 6, MLE run on p and m 2 tid samples from μ outputs 0 with,
err 6
1
16 [T]]
6
max
Im
a
m
Note that the probability is over both (μ. p) drawn from D.T P.T and the iid samples from μ. More simply, with probability 2 0.99,
crr(0) -000)=o( =0(
log | min(m, )
When the amount of shared randomness is constant, then this decreases asymptotically like the bound of supervised translation (Theorem I.I) up until constant, similar to Theorem For very large m, each extra bit describing the translator (increase by 1 in log (+]) amounts to constant number mistranslated x's 's out all X. The proof is deferred to Appendix
We also prove the following lower-bound that is off by constant factor of the upper bound.
Theorem 3.5 (CN lower-bound). There exists consiunts C₁ 2 1 such that: for any set T C for any m 2 1, any a E (0, 1/2), and any with 6 S log O S min min(m,,ITl) there exists @' size
Again, in the exponentially unlikely event that either Pn or 1 n S is empty, we define both T, p to be the singleton distribution concentrated on the lexicographically smallest element of y, so MLE outputs a O-error translator.

---

|0'| S |6) such that, for any P 2 T and any algorithm A x - O with probability 2 0.99
over ~ u(e') and (n, p) drawn from D and 2 Im p.,
log O
err(0) 2
C2 min(m, (T))
where 0 = (21,,, 12,,,,,22221. .2,..., T.).
The only purpose of θ in the above theorem is to upper-bound the description length of translators, as we replace it with an entirely different (possibly smaller) translator family O' that still has the lower bound using log |+| 2 log (0'). Since (e') is the uniform distribution over Ø' the ground-truth classifier is uniformly random from O'. A requirement of the form log | = O(a min(m, (T))) is inherent as otherwise one would have impossible right-hand side error lower-bound greater than 1, though the constants could be improved.
The proof of this theorem is given in Appendix C.2 and creates model with Olog n) independent "ambiguities" that cannot be resolved, with high probability over S, T1, 22. Im- Experimental validation of the theorem is described in Appendix
4
Discussion
We have given a framework for unsupervised translation and instantiated it in two stylized models. Roughly speaking, in both models, the error rate is inversely related to the amount of samples, common ground, and the language complexity. The first two relations are intuitive, while the last is perhaps more surprising. All error bounds were informattion-hhooetiic meaning that they guarantee learnable accurate translator, but learning this translator might be computationally intensive.
In both models, the translators are restricted. In the knowledge graph, the translators must operate node-by-node following an assumed compositional language structure [T] In the common nonsense model, the restriction is based on the translator description bit length log @ To illustrate how such restrictions can be helpful, consider block-by boockbb-blook translators which operate on limited contexts (e.g., by paragraph). Consider again the hypothetical example of Figure 1 Suppose the three texts are outputs of three translators = {A, B, C). Let us suppose that translator A always produces accurate and natural translations, and further that all translators work modern translation algorithms operate within some limited context window. In fact, one can imagine set of isolated adversaries where each adversary is trying
as
the translators of different paragraphs to mistranslate a paragraph, knowing the ground-truth translation of their paragraph, while attempting to maintain the plausibility of the entire translation. If only the first- mnst-paragraph adversary mistranslates reef to ocean basin, then the translation lacks coherence and is unlikely. If the adversaries are in cahoots and coordinate to all translate reef ocean basin, they would generate: Have you seen mom? just returned from the ocean basin. At the basin, there were a lot of sea turtles. which has low probability 10 presumably because encoded in GPT-3's training data is the knowledge that there are no turtles deep in the ocean near the basin. While the adversary could also decide to change the word turtle something else when it appears near basin, eventually would get caught in its "web of deceit." The intuition is that, across sufficiently many translations, the prior will not "rule out" the ground-truth translations while very incorrect translators will be ruled out.
Judging success. Our analysis sheds some light on whether it is even possible to tell if translation without parallel data (UMT) is successful. A positive sign would be if millions of translations fluent English accounts that are consistent over time across translations. In principle, however, this is what LM likelihood should measure (excluding consistencies across translations which sufficiently powerful LMS may be able to measure better than humans). We also considered a statistical distance (KL divergence) between the translations fa(x) for ~ μ and the prior y ~ p. and μ could be estimated given enough samples. If this distance is close to zero, then one can have predictive accuracy regardless of whether the translations are correct. This raises a related philosophical quandary: a situation in which two beings are communicating via an erroneous translator, but both judge the conversation to be natural.
That is. we assume that each translator has a latent map from nodes in the source graph into nodes in the target graph, and edges are mapped from the source to target graphs in the natural way. The study of compositional communication systems, among humans and animals, has played central role in linguistics (39
10

---

Acknowledgments and Disclosure of Funding
We thank Madhu Sudan, Yonatan Belinkov and the entire Project CETI team, especially Pratyusha Sharma, Jacob Andreas, Gašper Beguš, Michael Bronstein, and Dan Tchernov for illuminating discussions. This study was funded by Project CETI via grants from Dalio Philanthropies and Ocean X; Sea Grape Foundation; Rosamund Zander/Hansjorg Wyss, Chris Anderson/Jacquelin Novogratz through The Audacious Project: collaborative funding initiative housed TED.
References
[1] S. Ahyong, C.B. Boyko, N. Bailly, J. Bernot, R. Bieler, S.N. Brandão, M. Daly, S. De Grave, Gofas, Hernandez, L. Hughes, T.A. Neubauer, G. Paulay, W. Decock, S. Dekeyzer, L. Vandepitte, B. Vanhoorne, R. Adlard, S. Agatha, K.J. Ahn, N. Akkari, B. Alvarez, V. Amorim,
A. Anderberg. G. Anderson, S. Andrés Sánchez, Y. Ang. D. Antic, L.S., Antonietto, C. Arango,
T. Artois, S. Atkinson, K. Auffenberg, B.G. Baldwin, R. Bank, A. Barber, J.P. Barbosa, I. Bartsch, and A. Zullini. World register of marine species (worms). https::/wwwwe http:://www.marresspccessss
D. Dellan-Santini, N. Bergh, A. Berta, T.N. Bezerra, S. Blanco. I. Blasco-Coste 2022.
URL htt.s::t///.t..... http///wwww.../ htwp///maaaaama.mm......m http://wwww.a.nnppcce.e... www.ecieeeeeseeeee .org
Accessed: 2022-10-22.
[2] Jacob Andreas, Gašper Beguš, Michael M. Bronstein, Roee Diamant, Denley Delaney, Shane Gero, Shafi Goldwasser, David F. Gruber, Sarah de Haas, Peter Malkin, Nikolay Pavlov, Roger Payne, Giovanni Petri, Daniela Rus, Pratyusha Sharma, Dan Tchernov, Pernille Tønnesen, Antonio Torralba, Daniel Vogt, and Robert Wood. Toward understanding the communication in sperm whales. iScience, 25(6):104393, 2022, ISSN 2589-0042. doi: https://do..rgg/0..0066 00sci20022.103393 URL https:/ www. www.ssseeeeeeiieeee com/ science/article pi p11/$2539002220668
[3]
Emily Anthes. 2022.
The animal translators.
The New York Times, Aug
URL
https: /ttp:://wwww.o nytimes.ttte... na mole--oole-eee htt.t/mmm...ccm/2//m/0m0000 2ttmm//2222///3////oo//o
trans maanslatorsaaae
html
[4] Mikel Artetxe, Gorka Labaka, and Eneko Agirre A robust self-learning method for fully unsupervised cross-lingual mappings of word embeddings. In Proceedings of the 56th Anmual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 789-798, Melbourne, Australia, July 2018. Association for Computational Linguistics. doi: 10.18653/v1/P18--
https:/::: waw.aaaaaaoooootoooooooooo wwwthholooy..oro/18881100
[5] Mikel Artetxe, Gorka Labaka, and Eneko Agirre. Unsupervised neural machine translation, new paradigm solely based on monolingual text. Proces. del Leng. Natural, 63:151-154, 2019. URL h/tt::///ooonaaat sepln. wto/ssppnn/os//o/////oaaoaaa phppplx/ article/view/6l
[6] László Babai, Paul Erdo "s, and Stanley M. Selkow. Random graph isomorphism. SIAM Journal on Computing, 9()):628-63) 635, 1980. doi: 10.1137/0209047. URL htttps://dii.on org/10
1137/0209047
[7] Christos Baziotis, Barry Haddow. and Alexandra Birch. Language model prior for low low-resource neural machine translation. In Bonnie Webber, Trevor Cohn, Yulan Hc, and Yang Liu, editors, Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing, EMNLP 2020, Online, November 16-20, 2020, pages 7622-7634. Association for Computational Linguistics, 2020. doi:
http5///1112200.mmpmmamaaaa I8653/v1/2022 www.:/200...m..mmma.a....m.m
URL htt.httts://di..oottt
[8] Marina Bedny, Jorie Koster-Hale, Giulia Elli, Lindsay Yazzolino, and Rebecca Saxe. There's more to "sparkle" than meets the eye: Knowledge of vision and light verbs among congenitally blind and sighted individuals. Cognition, 189: 1001105-110 15, 2019. ISSN 0010-0277. doi: https:
URL https:/ www. www.wccieeeeiirrttttt com/ sccienncesrrtaaee//////000011119
[9] Mélissa Berthet, Camille Coye, Guillaume Dezecache, and Jeremy Kuhn. Animal linguistics:
a primer. Biological Reviews, n/a(n/a), 2022. doi: https:///oi.orrg//0 11t.11111/bbbvv2e00 12897. URL.
https: attps://onlinelibreee htwpaaaee....aaaaaaaaaooaoooeeee http:///...aoaoaoooo.ooooooooaa.
12897

---

[10] Thorsten Brants, Ashok C. Popat, Peng Xu. Franz Josef Och, and Jeffrey Dean. Large language models in machine translation. In Jason Eisner, editor, EMNLP- CoNLL 2007, Proceedings of the 2007 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning, June 28-30, 2007, Prague, Czech Republic, pages 858-867. ACL,, 2007. htt.tttss//acclaaie
[11] Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, and Dario Amodei. Language models are few-shot learners. In Advances in Neural Information P Processing Systems, volume 33, pages 1877-1901. Curran Associates, Inc., 2020. URL
neur cc wwtppppp//p/.ppp//////
[12] Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gaurav Mishra, Adam Roberts, Paul Barham, Hyung Won Chung. Charles Sutton, Sehastian Gehrmann, Parker Schuh, Kensen Shi, Sasha Tsvyashchenko, Joshua Maynez, Abhishek Rao. Parker Barnes, Yi Tay, Noam Shazeer, Vinodkumar Prabhakaran, Emily Reif, Nan Du, Ben Hutchinson, Reiner Pope. James Bradbury, Jacob Austin, Michael Isard, Guy Gur-Ari, Pengcheng Yin, Toju Duke, Anselm Levskaya, Sanjay Ghemawat, and Noah Fiedel. Palm: Scaling language modeling with pathways. arXiv preprint 2rXiv:2204.02311, 2022. URL https: /ttp::///axxvvvvoa///e /bbs/
2204. 02311
[13] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv:1810.04805, 2018.
[14] Benjamin Doerr Probabilistic tools for the analysis of randomized optimization heuris- tics. In Natural Computing Series, pages 1-87. Springer International Publishing, nov 2019. doi: 10.1007/978-3-000
URL https://doi. org/10.00111.000 1007
[15] Daniel Edmiston, Phillip Keung, and Noah A. Smith. Domain mismatch doesn't always prevent cross-lingual transfer learning. In Nicoletta Calzolari, Frédéric Béchet, Philippe Blache, Khalid Choukri, Christopher Cieri, Thierry Declerck, Sara Goggi, Hitoshi Isahara, Bente Maegaard, Joseph Mariani, Hélène Mazo, Jan Odijk, and Stelios Piperidis, editors, Proceedings of the Thirteenth Language Resources and Evaluation Conference, LREC 2022, Marseille, France, 20-25 June 2022, pages 892-899. European Language Resources Association, 2022. URL https: /tt///aaaatttta
org/2022 2022 1rel-rree- 1. 94
[16] Shane Gero, Hal Whitehead, and Luke Rendell. Individual, unit and vocal clan level identity cues in sperm whale codas. Royal Society Open Science, 3(1):150372, 2016.
[17] Oded Goldreich, Brendan Juba, and Madhu Sudan. A theory of goal-oriented communication. ACM, 1- 2012. doi: 10.114552160158.11661111 URL htttps:///oii.. /rg/ 10.1145/216015.. 210066
[18] Jesse Michael Han, Igor Babuschkin, Harrison Edwards, Arvind Neelakantan, Tao Xu, Stanislas Polu, Alex Ray, Pranav Shyam, Aditya Ramesh, Alec Radford, and Ilya Sutskever. Unsupervised neural machine translation with generative language models only. CoRR, abs/21 10.05448, 2021.
httpttts::// /ttttttsss///iiii.../ org/ abs/ 2110.000000 05448
[19] Zhiwei He, Xing Wang. Rui Wang. Shuming Shi, and Zhaopeng Tu. Bridging the data gap between training and inference for unsupervised neural machine translation. In Smaranda Muresan, Preslav Nakov, and Aline Villavicencio, editors, Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), ACL 2022, Dublin, Ireland, May 22-27, 2022, pages 661 1-6233,, Association for Computational Linguistics. 2022. doi: 10. 10.18663/v 1ttp://w//2222lllll1. 22t/2/2222.-ooog.555666233 URL B.R._tttpss//o...g//0....B 2022. acl. long 456
[20] Yaofang Hu, Wanjie Wang, and Yi Yu. Graph matching beyond perfeatly-overlappiin rényi random graphs. Stat. Comput., (2)1) 2022. doi: 10. 12200727191222-222200000--1 URI
erdös- erdös
https: / 101.1...110//11222000... -2-2222-2222222 10079-1
12

---

[21] Brendan Juba and Madhu Sudan. Universal semantic communication I. In Cynthia Dwork, editor, Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008, pages 123-132. ACM, 2008. doi: 10.1145/ 1374376.1374397. URL. wwwpt:ttpp//cmm //oi: .rg. 44444//7770001111111444114333333 1374337
[22] Yunsu Kim, Miguel Graça, and Hermann Ney. When and why is unsupervised neural machine translation useless? In Mikel L. Forcada, André Martins, Helena Moniz, Marco Turchi, Arianna Bisazza, Joss Moorkens, Ana Guerberof Arenas, Mary Nurminen, Lena Marg. Sara Fumega, Bruno Martins, Fernando Batista, Luísa Coheur, Carla Parra Escartín, and Isabel Trancoso, editors, Proceedings of the 22nd Annual Conference of the European Association for Machine Translation, EAMT 2020, Lisboa, Portugal, November 3-5, 2020, pages 35 44. European Association for Machine Translation, 2020. URL https::/aaaeee http///llaattoll.....ooooooooo eamt 1.mt
[23] Guillaume Lample, Alexis Conneau, Ludovic Denoyer, and Marc' Aurelio Ranzato. Unsuper- vised machine translation using monolingual corpora only. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Conference Track Proceedings. OpenReview.net, 2018. URL
[24] Guillaume Lample, Myle Ott, Alexis Conneau, Ludovic Denoyer, and Marc' Aurelio Ran- zato. Phrase-based & neural unsupervised machine translation. In Ellen Riloff, David Chi- ang. Julia Hockenmaier, and Jun' ichi Tsujüi, editors, Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, Brussels, Belgium, October 31 November 4, 2018, pages 5039-5049. Association for Computational Linguistics, 2018. URL https:://at www.aantwhooo..oooooooo.ooom
(25] Guillaume Lample, Myle Ott, Alexis Conneau, Ludovic Denoyer, and Mare' Aurelio Ran- zato. Phrase-based & neural unsupervised machine translation. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pages 5039-5049, Brus- sels, Belgium, October-November 2018. Association for Computational Linguistics. doi:
10.18653/v//D18. 1549. URL https: awlaaaaaanttooooo soo.aaattooooooorr//l-----1
org/D18-1545
[26] Lorenzo Livi and Antonello Rizzi. The graph matching problem. Pattern Analysis and Applications, I 16:253-283, 08 2013. doi: 10.1007/s (007//110044001--22843
[27] André Lynum, Erwin Marsi, Lars Bungum, and Björn Gambäck. Disambiguating word trans- lations with target language models. In Petr Sojka, Ales Horák, Ivan Kopecek, and Karel Pala, editors, Text, Speech and Dialogue 15th International Conference, TSD 2012, Brno, Czech Republic, September 3-7, 2012. Proceedings, volume 7499 of Lecture Notes in Com- puter Science, pages 378 385. Springer, 2012. doi: 10. 01111000797---4444 0422-2299---2- 46. URL https: /ttps://doi.orgg 1ttp://....1011711111111 101111007700---222277-------1110
[28]
Kelly Marchisio, Kevin Duh, and Philipp Koehn. When does unsupervised machine translation work? Loic Barrault, Ondrej Bojar, Fethi Bougares, Rajen Chatterjee, Marta R. Costa- jusså, Christian Federmann, Mark Fishel, Alexander Fraser, Yvette Graham, Paco Guzman, Barry Haddow, Matthias Huck, Antonio Jimeno- Yepes, Philipp Koehn, André Martins, Makoto Morishita, Christof Monz, Masaaki Nagata, Toshiaki Nakazawa, and Matteo Negri, editors, Proceedings of the Fifth Conference on Machine Translation, WMT@@ EMNLP 2020, Online, November 19-20, 2020, pages 571-583. Association for Computational Linguistics, 2020. URL https://acll http:///aaaattohoggo.oo or org 20wg./222...2 wm...1.....77777.
[29] Antonio Valerio Miceli Barone. Towards cross-lingual distributed representations with- out parallel text trained with adversarial autoencoders. In Proceedings of the 1st Work- shop on Representation Learning for NLP, pages 121-126, Berlin, Germany, August 2016. Association for Computational Linguistics. doi: 10. 111655//11W16--1144 URL https: //aclanthhology.orr//B.I.
[30] Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning. MIT press, 2018.
13

---

[31] Surangika Ranathunga, En-Shiun Annie Lee, Marjana Prifti Skenduli, Ravi Shekhar, Mehreen Alam, and Rishemjit Kaur. Neural machine translation for low-resource languages: survey. arXiv preprini arXiv: 106. 15/ 2021.
[32] Sujith Ravi and Kevin Knight. Deciphering foreign language. In Dekang Lin, Yuji Matsumoto, and Rada Mihalcea, editors, The 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies. Proceedings of the Conference, 19-24 June, 2011, Portland, Oregon, USA, pages 12-21, The Association for Computer Linguistics, 2011. URL
https: httpss//acaaathhooooooooo org
10027
[33] Baptiste Rozière, Jie Zhang, François Charton, Mark Harman, Gabriel Synnaeve, and Guillaume Lample. Leveraging automated unit tests for unsupervised code translation. In The Tenth Inter- national Conference Learming Representations, ICLR 2022, Virtual Event, April 25-29, 2022. OpenReview.net, 2022. URL https: http:///ppneeeeiiiee net wwt.:eettnut..eee. Eorum Rid
cat 64
[34] Taylor Shin, Yasaman Razeghi, Robert L. Logan IV, Eric Wallace, and Sameer Singh. Auto- Prompt: Eliciting Knowledge from Language Models with Automatically Generated Prompts. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLPP), pages 4222 4235, Online, November 2020. Association for Computational Lin- guistics. doi: 10. 10.188633/112022 http:///0020.mmmmmmm.mm224. URLhttps: ac anthologyy org/
2020. main. 346
[35] Kaitao Song. Xu Tan, Tao Qin, Jianfeng Lu, and Tie- Yan Liu. MASS: masked sequence to se- quence pre- pre-training for language generation. In Kamalika Chaudhuri and Ruslan Salakhutdinov. editors, Proceedings of the 36th International Conference on Machine Learning, ICMI. 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learming Research, pages 5926-5936. PMLR, 2019. URL http: / /ttp://///ceeeeeeoeoooooooo ings ml ..w..rsss. v97/song html
[36] Daniel A. Spielman and Shang- Hua Teng. Smoothed analysis: An attempt explain the behavior of algorithms in practice. Commun, ACM, 52(10):76-84, oct 2009. ISSN 0001- 0782. doi: 10. 145/1562764.1. 1562788. URL 1562785
[37] Chau Tran, Shruti Bhosale, James Cross, Philipp Koehn, Sergey Edunov, and Angela Fan. Facebook ai's WMT21 news translation task submission. In Loic Barrault, Ondrej Bojar, Fethi Bougares, Rajen Chatterjee, Marta R. Costa-jussà, Christian Federmann, Mark Fishel, Alexander Fraser, Markus Freitag, Yvette Graham, Roman Grundkiewicz, Paco Guzman, Barry Haddow, Matthias Huck, Antonio Jimeno- Yepes, Philipp Koehn, Tom Koemi, André Martins, Makoto Morishita, and Christof Monz, editors, Proceedings of the Sixth Conference on Machine Translation, @MT@ EMNLP 2021, Online Event, November 10-11, 2021, pages Association for Computational Linguisties, 2021. BRLhhtpps:/ http://cclaattoooy..oooooo
2021 wmt 11.19
[38] Ludwig Wittgenstein. Philosophical Investigations. Basil Blackwell, Oxford, 1953. ISBN 0631119000.
[39] Klaus Zuberbühler. Syntax and compositionality in animal communication. Philosophical Transactions of the Royal Society 375(1789):20190022 2020.
14

---

A Translator Revisions and Plausible Ambiguities
Even though is unknown, it will be convenient define, for each 0 E θ revision of f. which is
the permutation Tz. } + J/ between fe and f., (v) = fe(f. (v)) II We write T = T3 when clear from context, and π. (v) y the identity revision.
Note that the divergence D(f) and semantic loss (()) can equivalently be defined using revisions,
E log T(y) you p(To(V))
D(0) = KT.(Jo o P) = KT To p) ( = E [(I+())) = E [e(v. [_[[(v. mo()]]] xm-p
To relate divergence and loss, it is helpful to define a notion of plausible ambiguities which are whose revisions To 7) are not too unlikely under the prior. These may also be of independent interest as they capture certain types of ambiguities that can only be resolved with supervision.
Definition A.1 (y-Plausible ambiguities). For any 7 E [0, 1). O, and distributions T. over y the set of 7-plausible ambiguities A. ANT C is:
Ay +
Pr Pr(p(To(V)) = 0] s 5 and E, = max L()). M-T
DEA,
For example, lefttt would constitute 7-plausible ambiguity if one could swap the two words, making y fraction of the translations have 0 probability. Such revision would have low loss if such swaps are considered similar in meaning. Condition 2.1 equivalent to * E Ag-
The quantity of interest is Ex, the maximum loss of any y-plausible ambiguity Next, we prove that the loss of the translator output by the Maximum Likelihood Estimator is not greater than Ey given m In [e] examples.
Theorem A.2. Let pt, p be probability distributions over X, resp., and f. satisfy Condition 2.1 1 In [el Then, m
(r)) = O. Fix any 5 (0,1), 1), 2 and let 7 2
Pr
( S Eg
> 1 5,
where 0 (M........... [m) and Exy is from Definition
A.1
Since e, is non-decreasing in y, the number of examples increases the loss bound e., decreases to approach En. This bound and its proof Appendix A are analogous to the realizable Oceam bound of supervised classification, see Appendix
Proof of Theorem A.2 MLE minimizes 6(0) = 1
m Zism log p[na(x]]] over E θ where yi fo(x:). By the realizable prior assumption i(*) < x. Thus, for the algorithm to fail, there must be "bad" 0 E B (Ø @ (()) En} with i()) I 6(*)
If p(To(())) 0 for any i, then ((TT) = co. Note that by Definition A.1 B n A, = thus for all E B: Pr Pr(p((T(()) = 0] >
and,
8
Pr (0()) oo] (1 7)m S mm mm <
|
By the union bound over 0 E B, 0 E B (0) < xc| < 8 since
|B|
< |0].
B The Tree-based Model
B.1 A tree-based probabilistic model of language
The last model, which we view as secondary to the previous two, is a simpler version of the common
nonsense model. can be viewed as a "warm-up" leading up to that more general model, and we
Formally, fo f= fz) + y only defined on f-(X') but can extended a permutation on y many ways. For concreteness, we take lexicographically smallest extension on y C {0,1)" 1)*
For intuition, note that E. can be bounded using 7: .2 2 mingeo Pry [p(TT(() (v)) To( + v]
15

---

Sharks
Do
Ocean
Aara
eet
swiRy
you
not
whales
sunfish
basins
waves
harmonicas
Poot
hockey
sharks
quickly
salmer
slow
stone
fast
dance
cook
mind
go
worry sleep
burp
daydream
chew
hatch
hunt fivve
join
change quiekky
break refract crest
Figure 6: An example of a language tree of plausible texts and the subtree of ground-trute translations illustrated in green.
hope it helps illuminate that model by instantiating the language therein with simple tree-based syntax.
In the tree-based model, the nodes of tree are labeled with random words, and plausible texts (according to the prior p) correspond to paths from root to leaf. A translated language (or equivalently, a source language (4) is then derived from root-to-leaf paths in random subtree H G. We prove that, with high probability, a prior p and translated language T sampled by this process satisfy Condition 2 semantic error e,, (1/ min(m, a")). Therefore, MLE yields semantically accurate translator for the sampled language with high probability, for sufficiently large
The random tree language (RT) model is a randomized process for generating a tree-based source language μl, translated language and prior p. is parameterized by finite vocabulary set W, depth E N, and arities a, b N such that S a S b < [W]/4. For simplicity, the possible target texts are taken to be the set of all possible n-grams over W, namely, J = W Again for simplicity, we also assume X = | so that each fe: X + y is bijection. To generate an IT, first a full b-ary, depth + 1 tree G is constructed. Labeled edges shall correspond to words, and paths shall correspond to texts (sentences), as follows:
1. Starting from the root node and proceeding in level-order traversal, for each node ot sample b words Wi...., Wbb E W uniformly at random and without replacement; label each of v's child edges with one of the sampled words.
2. The labels on each path from the root to a leaf (y.....,y,) corresponds to a plausible text, giving set of plausible texts
ty y (y1...., Vv) labels of path in G}.
3. A subtree I/ G is obtained by sampling uniformly at random a out of b of the children at each level of the tree, in level-order traversal. The set of translated texts is analogously defined as
T
y y = (yn...... yv) labels of a path in H) C.
The prior p U(P) is uniform over plausible texts P. while μ is uniform over f- (T') We let (p, p) ~ RT(W, n, a, b) denote the sampling of a prior and translated language obtained via this randomized process. When the parameters W, n, a, b are clear from context we simply write RT.
Note that θ and f. E e may be arbitrary, and by definition of r, μ = (T)- is uniform over T's preimage. Since assumed | [>] above, f. is invertible.
Next, we will argue that a random tree language sampled this process satisfies realizability (Condition 2 and Definition A. with appropriate choice of parameters. While we make no assumptions on O is important that the plausible texts are sampled after the possible permutations (ambiguities) II are specified. Otherwise, if an adversary were able to choose a permutation n: y
16

---

Y based on P. then they could arbitrarily permute P. resulting in a permutation with high expected loss but no change in likelihood according to the prior p -heerre violating Definition A
You can think of Theorem B.I as pointing to the required text length n and an upper bound on the number of parameters [+] for which Condition and and Definition A.1 hold with high probability. As we know from Theorem A.2 and state clearly next, these in turn imply translatability of a random tree language.
Theorem B.1 (Translatability in the RT model). Fix any m 2 1, 5 E (0.) 1) vocabulary set W, and tree arities a S S [W]/4, Then, for any O and any * E O with probability at least 8 over (H, ~ (TW, n, a, b) and iid samples 11, 22...... Immm pb.
6 6
err(0) S max
In
a"
where 0 = MLE (21, (21,422... 22,............................. 3m) and MLE is from Definition 1.1
Note that the probability in the corollary is over both (p. p) ~ RT and the m iid training samples. Again, note how the first term is similar to the 1 log J term from realizable supervised learning (see Theorem J.Ip, and the second term additional due to the unsupervised case. The proof, given in Appendix B uses Theorem A.2 and a lemma stating that e < 167 for 7 that are not too small. The main challenge is that there are dependencies between the paths, so one cannot directly use standard concentration inequalities.
To better understand Theorem B.1 we are trying to apply Theorem B. to get bounds on the sample complexity m needed to translate (H, ~ RT(,, n, a, b) with small constant loss and small constant failure probability.
let us consider two possible families of translators and suppose
First, since | = | = |W]", the above bound is meaningless (bigger than 1) if O is the family of all translators, as the set of all translators has log([X?!)) = O(WI n log (W]) parameters which is much larger than a". In other words, no free lunch.
On the other hand, let us consider the family of word-for-wont translators Ow, which work by translat- ing each word text separately, ignoring the surrounding context. The number of such translators is the same as the number of word-to-word permutations. i.e., 10w, = |W]t. So Theorem B. gives a sample complexity bound of m = O(log W!) = O(WI log (V)). The number of words in the English language is about N ~ 10 The quantity a is equal to what is called the perplexity of μr, the effective number of words that may typically appear after a random prefi. For a constant a, the minimum text (or communication) length Ollog N) needed is thus logarithmic in the vocabulary size. While word-for-word translators are poor, this analysis still sheds some light on the possible asymptotic behavior (barring computational constraints) of translation, at least in simplistic model.
Common tree analysis. The tree model helps us demonstrate the generality of the common nonsense model. Instead of the fixed arities a < b in the tree model, one can consider an arbitrary language tree over plausible texts and an arbitrary subset T C P corresponding to a subtree of ground-truth translations. The common nonsense model implies that if the sets are perturbed by removing, say, a a 0.01 common fraction of translations, then with high probability MLE's error decreases at an Õ(1/ / min(m, (T))) rate. Note that Theorem 3.4 not directly apply to the random tree LM because in that LM, the choice of which branches to include are not independent due to the fixed a-arity constraint.
B.2 Proof of Theorem B.1
The proof of Theorem B. follows from Lemma B.2 below. In this section, we will prove this lemma and then derive the theorem from it.
Lemma B.2 (RT conditions). Consider any vocabulary set W. tree arities < < ( /4, tree
depth n E N. Then, for any E (0, 1) and 7 2 4a -a-n In(4[0]/6), with probability 2 8, (H,p) give,
Pr [ S 1671 2 S. (H.
(4)
Moreover, any p. P sampled from RT(W, n, a, b) satisfy Prawu (p(s((:))))))))))))))))()))))[ = 0] = 0 as needed for the realizability Condition 2.1
17

---

The proof of Lemma B.2 requires two additional lemmas, stated and proved next. The first is known variant the Chernoff bound for so-called O-negatively correlated random variables.
Lemma B.3 (Chemoof bound for O-negatively correlated random variables). Let Zi...., , Zn be O-negatively correlated Boolean random variables, that is, they satisfy
IA
S [n] Pr[Vie Z, - 0J
I1 SEI
Pr Pr 0
Then, letting Z Ei=1 Ze it holds that
Pr
Z
S
Lemma B.3 follows from 14 Theorem 1.10.24(a)) with ó == 1/2, a; == 0, b= and Y; = X, That theorem, in turn, is simply Theorem 1.10.10 for O-negatively correlated random variables.
The second lemma used for the proof Lemma B.2 is combinatorial argument that we prove below.
Lemma B.4. Given any т : y + V, it is possible to partition A=
= {y E ) ( + y) into four disjoint sets A = A U A2 U Ag A4 such that, for each i 1,2,3, 4, the following two conditions hold:
x (A,)) A,
[W] 2
42 E W Hy A, y begins with z}
Proof. of Lemma B.4
We will partition A greedily to achieve the two conditions. Begin with four A4 0. For each y e in turn, assign one of the 4 sets as
empty sets A₁ follows.
A2 As
1. Let i be the index of the set A, such that (yy) A, has already been assigned to. If (T)) has not yet been assigned, let i
2. Similarly, t (y) E Aj has been assigned, let j be its index otherwise j = 1.
3. Let 2 be the first n elements of æ. Let be the index of the A such that Hy E A y begins with = /W1/2 if there is such a set, otherwise k 1. Note that there can be at most one such because there are at most [V] - other elements beginning with z that have been assigned already.
Thus S = (1,2,3,4) (i) and assign x any (say the minimum) element in that set. By induction, we preserve the two properties stated in the lemma.
With Lemmas B.3 and B.4 hand, are ready to prove Lemma
B.2
Proof. of Lemma B.2 The realizability Condition 2.1
Preva (afff(az (x)) Pr..
0] = 0. follows immedi-
ately from the fact that p uniform over P and that IS supported on T P. To prove the lemma, suffices to show that for any 2 4a (n44@)//8).
Pr (T
30 err(O) > 167, Pr Pr(p(to(v)) = 0] < s yur
Note that err(0) Pry-r ly of ne (v)), and that ())o(y)) if and only if To(y) P. Therefore, by the union bound over E θ it suffices to show that, for each 0 E O,
8
Pr (R
Pr v + To(y)) 16y, your
Pr (r(mo()) & <
(S)
yuT
|0]
We will show that, more generally, for any permutation π 3 + D. Equation (5) can be restated
in terms of ambiguous texts {y E y π ()) + y) and implausible ambiguities B (v E )
T (v) P}:
18

---

[+(A) > 16y, 7(B) 1 y
(H.P)~RT
|
Using Lemma B.4 partition A into four disjoint sets A = A U A2 U Ag U Aa such that for each i [4], the following two conditions hold:
x (AA)) NA, =0
(6)
W
V2 E mn (y As begins with 2}1
(7)
2
By the union bound, it suffices to show that,
5
Vi [4]
Pr [T(A) > 47, T(B) S 2 (H.P)~R
4/0)
because T(A) Σ
=i=1 T(Ai).
so (A) > 16y then it must follow that T TAA)) > 16y/4 for some i.
suffices to show that this holds conditioned on any value of A, nT:
VV [ A
Pr [T(A)) > 4y, (B) 5 A AA= VJ (MT
(8)
O
Thus, fix any V C A₁. We proceed by analyzing two cases, based on [V| versus (T) aa
Case 1: V < 4-/7]- Then Equation 8 holds with probability 0, because conditioning on
A; A V. we have
TA.)) = A NT
47
Case 2: V 4T| For each V define Boolean random variable Z, LuBB, i.e.,
{1 VEB 10 u& B.
Z, =
We claim that the Z,'s satisfy the condition of Lemma B.3 which follows inductively from the fact any subset of Z, 's being 0 only makes it less likely for another Z, to be O, because the way that the Z, 's are chosen is such that there exactly b many I's among the Zu 's (and other symmetric random variables which we have not named).
Therefore, if we define Z Ever Zu and
( Z A
VJ. Lemma B.3 gives,
C AnT <e C/8 Pr Z < 2
(9)
We conclude by bounding both sides of Equation
9 to obtain Equation S
For the right-hand side eq. V: Fix v and let
9 we claim that Pr [Z.
A nT 2 1/2 for each
Q {v E y y and (u)) agree the first n words). So Q WI and IQn Pl
Equation (6) implies that TTv) A;, and eq. 7 implies
that Q A, Z |W/22. Thus, there are 2 /W elements in Q A, that, by symmetry, are as likely to be in Q P as (v) is, and Q n P contains exactly S [WI/4 elements, thus the conditional probability that T(V) is in Q n. P (equivalently, (e) P is at most:
|W/4
<
W1/2 2
Since (()) & equivalent to Z,, 1, this means that Pr [2, 1| A 1/2. and hence:
V E|Z,1 A V = V Pr Z2 = A V
2
Note that while I' is randomly sampled, [T'] a always, and therefore the case-analysis is valid.
19

---

Because we are in the case that [V > 4 we have
V >
2
4y [T] = 2ny a".
(10)
2
Therefore the right-hand side of eq. 9 satisfies
8
5/8 e 70"0
4 |
where the rightmost inequality holds because by our assumption that y 2 4a -a" [ln(4]1/66).
For the left-hand side of eq.
1 note that
Z
Σ Zo
Σ -Ve
VEV
and therefore, using eq.
110). the left-hand side of eq.
satisfies
Pr 7 407=11 v 2 Pr
V V B
A
Sy T
We claim that VnB S BnT: Due the conditional event, we have VnB A A E T B. However, we argue that A n n B C CT B, i.e., that T n B S A. Indeed, by definition, y E 7 n then y E T but (t) & P, and since P 2 T, this implies that x (v) # y; that is, that A, as needed.
We have just shown that VOB C BnT, and therefore
V
B
B B
Pr
Sy
A A v
2 Pr
SS
A AnT=v
T
T
( S
This shows that the left-hand side of eq. proof.
9 upper bounds that eq. (8) and concludes the
Lastly, prove Theorem B.1 using Lemma B.2
Proof. of Theorem B.1 Let y be,
1 m
4 a
7 max
In
Lemma B.2 below shows that with probability > 28/3 3 over μ, we have that s, S. 16y.
Theorem A.2 implies that with probability 2 8/3 over 21, Ima we have err(ō) Ey. Thus, by the union bound, with probability 2 we have
1
4 a
err(ō) Sey 167 = 16 max
In
C Proofs for the Common Nonsense Model
C.1 Upper bound in the common nonsense model
C.1.1 Proof overview
To convey intuition, we think of the case of say 99%, and we omit constants in the following discussion. Recall that Theorem A.2 asserts that with high probability, the learned translator has error at most Eyy for 7 log | min(m, [TT) > log 10|m.. As such, the main technical challenge
20

---

in this proof is to show that, with high probability over the generated source language and the prior p. holds that
Ey 2
By definition of E-y we ought show that w.h.p over μ and p. any 0 θ with large semantic error must have many translations fz) deemed implausible by Slightly more formally: Since any y E y implausible (p(v) = 0) only if y & S, a union bound over 0 E @ means that is suffices to show that
Pr Pr[fo(() f 2 Pr (f(rr) $ s S.E.P
7 <ep(-->111) -
2mp
O
where the right inequality is by choice of y log / min(m, (T). The above inequality "looks like" it could be proven by a Chernoff bound, but a closer look reveals a subtle flaw with this argument.
To use a Chernoff bound, we'd first want to fix (i.e., condition on) each supp(u) = (( and then use Chernoff over the conditional random variables 1 fe(=)gs for each E supp(p) such that fa(x) * f- (z). Unfortunately, these conditional random variables are not independent. To see this, consider the case that (a( (x(') for two different of x'. Then, since we are considering
x' E supp(μ)), we have fa = f+ E S with probability 1.
To avoid this dependency, we prove a combinatorial lemma showing that it is possible to partition the set
A {x E X fe(x) + fx)))
into three parts = Ai U A2 U A3 such that (o() n (+.) = for each i E [3]. This resolves the dependency issue demonstrated above. We then proceed by applying Chernoff bound separately for each A,, which suffices since a union bound (over E [3]) loses only a constant factor in the upper-bound.
C.1.2 The full proof
The proof of Theorem 3.4 follows from the following main lemma. We first prove this lemma, and then show how the theorem follows from it.
Lemma C.1.
Let ax 8 E (0, 1) and C C. Then, for any 7 2 [I-a) [7
4 6 In
8
6y 2 1 -
Pr (m.D) P.T
E
The proof of Lemma C.I relies on a simple combinatorial proposition. This proposition is a special case of Lemma B.4 but since it is much simpler we give a self-contained proof.
Proposition C.2. For any finite y and any π y + V, is possible to partition ty (1(( + y} = A1 U A2 U Ay into three sets such that, π (AA) n A: = 0 for = 1,2,3. 3.
Proof. Let S = {y Tgee) y m(y) # y). We proceed iteratively, dividing each (non-trivial) cycle of separately into the three A/'s: Fix a cycle (2,.8,,.. sn} such that (s;)) = 8441 and T(*x) = $1. If is even we can just partition it into two sets: put the s; for even i's into A₁ and odd i's into Ag If n is odd, we can do the same except put the last element 8,, into Ag.
We can now prove Lemma
Proof. Lemma C.I Note that the lemma holds trivially for any 1/6 because we always have
E, < 1. Assume that y < 1/6. Let = 87 The probabilities in this proof are over the choice of
S C y. It suffices to show that,
Pr = Pr(mo(v) # v] > A Pr(mo(v) $ > < 8,
(11)
because (v)) = 0 whenever To(y) & S, thus A, = {0 E e Pr (ro())(y)) $ $] - 7). The set
S determines the perturbed sets T = T n and P = P n S and the distributions T = u(T) and UP))
21

---

Define 8 == 1 a. Since E [[T]] = =B multiplicative Chernoff bound gives
14
T - 2
|
I exp (-g (m)
I exp (
(-8
8
8
4
8
8
Pr
ln
S
8 By
5
4
4'
Thus, to show eq. (II.. it suffices to show that
8 [T]
38
Pr T
30 Pr( + y >
Pr(mo(y) $ S ?
(12)
By the union bound, to show eq.
12) it thus suffices to show that for any y + y
35
Pr
IT 2 T
(r(m(y) * v) > a A Pr(A(U) E S E - 4
(13)
Fix any т : : 4 V. By Lemma
C.2 we can partition fy E y Tty) * y = U U L2 A
such that o ((.)) n A, 0, and hence Pr, (ry(+(y) + y) Σ, 7 (A,). So Pry( # ツ > a, then
T(A,) > a/3 for some i. Therefore, suffices to show that
35
Pr
|TI Bie 3] T(A))
> 3
A Pr(m(y) $ Ss 5
|
With a union bound over E [3]. it suffices show that for each E 33
8 IT A -(A) 3 A Pr(M(() # $ 2
5 1
Pr
T
(14)
Thus, now in addition to fixing म, we fix S 3, thus fixing A.. To continue, imagine we are picking S by first selecting A, n S, and subsequently selecting S A. We will show that Equation (14) holds when conditioning on each possible value for the first selection, that is, each possible A, n.S. Formally, we fix V S A, and condition on A, An V, claiming that
Pr
T
2 I ITI A T(A))
> A Pr(m(y) $ S S V - V
S 4
(15)
3
First, observe that
nT
A n
V
7 (A.))
[''
T
therefore if |V| < Ba[T)/e then Equation
15
holds with probability 0 (due to the first two events in ///T)/6.
the conjunction). Thus, we can assume that
Note that +(V) T(A),, and that r(A.)= 2 a/3 implies
Pr (v) & S) 2 Pr gm07
Pr( S) 7(V)
Pr Pr(T(V) $ $] 3' yer
therefore the left-hand side of Equation
15 is upper-bounded by
3 3-7 v v= Annss
Pr Pr Pr( yEV
$)
Pr
Pr LEV
(T $ 5) V I-
(16)
a
We conclude the proof by upper-bounding Equation (66) with a Chernoff bound. Consider the random variables Z, Lr(jee for y V. These random variables are independent by definition of a-common-nonsenn Furthermore, due to the fact that ((A)) n A, 0, they remain independent even when conditioning on the event A, S = V. By linearity of expectation,
Σ Z VEV
V= A = alVl.
"SSpecifically, that the probability that sum of binary random variables is less than half its mean 3 1 is at most exp(-3111/88)
22

---

Using the same Chernoff bound as above, we have
Σ VEV Zy
Pr
V= V=AAn
<xp((-a\V1/)
2
Noting that / Pryev(((y) $ S), conclude that that Equation (66 is upper-bounded by
alV
8
exp
exp
4
This proves the inequality in Equation
15 thereby concluding the proof.
Finally, with the main technical lemma in hand, we prove Theorem 3.4
Proof. Theorem 3.4 The proof is very similar that in Appendix First, the realizability Condition 2.1 Przza (x)) 0] 0, follows immediately from the fact that are uniform
distributions with f. (supp())) C (p) which follows from the fact that C and the definitions of
Let == a and define 7 by,
8
6
max
In
m 3(T)
6
Lemma C.1 below shows that with probability 2 26/3 over Ht, P. we have that Ey S 67/0. Theorem implies that with probability 2 1 8/3 over 31 ........ Fm we have err(0) Ey. Thus, by the union bound, with probability 2 - we have
67 6 crr(A) 0 S E, v
In 6/0
max
a a
m S
C.2 Lower bound in the common nonsense model
The proof of the lower bound works by creating log n candidate "plausible ambiguities" and arguing that constant fraction of survive the random removal of elements.
Proof. of Theorem 3.5 The constants C1, C2 will also be determined through this proof to be large enough satisfy multiple conditions defined below. No effort has been made minimize the constants in this proof.
Let == [
We will lay out two x grids X X' and Y Ç V. for:
1 max 1,
(T)
log mg,
10
For integer denote [t] := 21, t). For i E [a]. j [6]. choose distinct elements zy E X and Viy T. To ensure this is even possible, we must make sure ab < [T', which holds because we assumed log n < min(m, (T]) thus,
ab < min [T]) max (1,
[T] min(m, (TT) max m
1 [
T= IT)
Let X = (zg i E [a], [b] and Y == {us E [a].j E B]} Let h fixed 1-1 mapping, say the lexicographically smallest. The parametrized translator family is defined by.
X X - y Y be
yig. (i(j+t1 mod b),
0, 1
O' 1 1- fo(z.))
Va X fo(x) h(x).
0, = -11
23

---

Clearly 10' = 2" < n = |
as needed. Let x = (I1, T2..,........... Fm). It suffices to show:
log n Cya min(10 [T)
Pr err 2
2 0.99,
for some constant O3 sufficiently large, because we can set C2 10 The above equation is equivalent to the following two cases based on m.
log n 2
Case 10
[T]
Pr
err(0)
0.99
(17)
S,x
C3
log n C3 100100m
Case 10 S
[T)
Pr S,x
err(0)
0.99
(18)
In both cases, will be convenient notice that, for any z 2 2, [z] (because S 1/2), we therefore have
2
z/z Since
(1. 10
max
< b
S
max
(19)
2a
10
10 > T. In this case consider the "full rows":
Case 1:
1 2a
S b < by Equation
19
We will show Equation 17
Now,
C(S) = {i E [a] Vj E M uy E).
These rows will be useful consider because nothing has been removed from the entire row, information about 0g has been revealed and (on average) one cannot achieve error < 1/2 on these examples, because cannot distinguish between the permutations on this row.
Note that the membership of different i, E C(S) is independent since S is chosen independently, and by definition of C' and S:
BJC(S)I = (1 a) a 2 (1 a)) a/aa 4'
since (1 -1-a) (1-a) is decreasing in and a I 1/2. Thus, by multiplicative Chernoff bounds (specifically, Pr[Z s | S =221/8).
S a Pr [C(S)
S a/32 v e 16/1/3 $ 0.001,
(20)
8
for sufficiently large e₁. Thus, Prs(IC(S)) > a/8 > 0.999. Let (S( C C(S) be those i which 0, + ki.
x) = fie C(S) 0, }
Clearly, for any algorithm and any C(S). Ex C' x) S = C(S)) because information whatsoever has been revealed about 02 for any i E C. Thus, by the same Chernoff bound, we have:
(S(ss C(S)
[C(S)
< 0.001,
for sufficiently large Cı, because 2 c1. By the union bound over this and Equation 20).
Pr S
(S(
32 z 0.998.
Since each row E C' incurs emorr examples one for each j because fx(g)) S:
b CS,
err 0 z
[T
Thus,
ba
Pr crr
> 0.998.
Sxx
32a T
Now, a 2 1 log n for sufficiently large e and as mentioned 2 2n Thus,
2
log n
Pr
err (0) 2 128a 7
0.998.
S.x
This establishes Equation 117 as long as 0g 2 128.
It remains to prove Equation
18

---

Case 2: 10 S T. In this case 2m
12'
< b
T ml0mm
by Equation 19
Next, consider the set of
rows with at least 1/2 of the elements S:
D(S)= = ( [
b 2
D(S)
Ki () vis E SS} 2
Intuitively, any row i E D(S) is "dangerous" in the sense that if 0; + kis then it causes errors on 6/2 different æ's in the support of ps, i.e., for which f. (11y) S. Observe that [[[[(S)]] 2 a/2 since each size = { [6] Myy E [}] 2 b/2 least likely as the size b since a - 1/2.
And also, membership of i E (()) since is independent. Thus, by the same Chernoff bound as above, for sufficiently large C1,
Pr
D(S)
0 4 S E a/16 e --a/// 0.001.
(21)
Let 0 = (-0,, 02 ................................ ..... 02). This makes it convenient define the giveaways G(S) S X to be,
G(S) = {az ja]. f. (24)) S, $ S}.
These are the points Viş which we might observe fa (Iis) which would imply that = *; (and its negative). Also let,
x() {21, ................................ ................................ Zm n G(S).
(Note that if for a give row i, we do not have any Tij E G(S, x), then we have no information about 0, As preview to what is come, now argue that with high probability |G(S, < a/8 which will mean that, if (D() > a/4, then we have no information about 0; for at least a/8 of the rows
i D(S).)
For any fixed j. observe that Pr[zi, E G(S) a(1 a.) so E[[G(()]] a(1 a)aa S aab. By
the Chernoff bound that Pr[Z 2 2 2 S e 2/21/3
Pr[|C(S)] 2aab] < aaah/3 <e 4/3 < 0.001,
5
for sufficiently large C1- (We have used the fact that the above probability is smaller than ([S) were actually aab.)
Also, Es|T /2/2 since S 1/2. So, by the Chernoff bound Pr(Z < B[Z]/2] < e B/2//8
[
Pr g
T |ns <
<e < < 0.001,
for sufficiently large e since Thus, by the union bound:
[T|
2 logn c1.
Pr $
TUs < VIG(S) 2 2aab $ 0.002.
(22)
Also,
|G(S)
E [G(())) 5) S m
7 S
Thus, using Markov's inequality in the second line below,
E
G()
TOs
[ |G(S)
< 2aab
Σ T
20ab
Saaam
[2'
80000abm
(T
Pr
|G(S,
Tns
|G(S) < 2aab
I 0.001.
x.S
[T]
By the union bound over the above and Equation
22 since Pr[
Pr Pr[-F]
G((S
8000aabm
Pr
0.001 + 0.002.
x.5
[T]
25

---

Finally, since
[
b S
a10mm
8000aabm
a
Σ 0.08
S
8
Pr x.5
G(S,x)
0.003
By the union bound with Equation
21
Pr x,5
[(S) - 4 v |G((s)) > 388 - 0.004
Let
F(S,x) E D(S) Vj [ my & (() c D. 2 [D(S) (S) x)
Clearly |F(S, x)]
because each x E G(S,x) can remove at most one row
from D(S). Thus,
Pr x.9
F(S)x)
S 88 0.004.
(23)
F(S, x) will function exactly like C in the analysis above of Equation 17 We repeat this analysis
for completeness, replacing C by F. Let F'(S, C F(S, x) be those which 0, A *;.
F'(S,x) = {i F(S, x) 0 + +;}.
For any algorithm and any F(S,x). Fs x) whatsoever has been revealed about 0; for any F.
S] [F(S, x)1/2 because no information Thus, by the same Chernoff bound, we have:
1 [(()
Pr 3x
[S))
&
[F()
x - 0.001,
for sufficiently large e₁. By the union bound over this and Equation (23
Pr 8x
(S,
a > 0.995.
32
Since each row E F incurs 2 b/2 errors on examples x by definition of F" and D, since F" C and thus at least 6/2 errors on j for which f. (I11) S. Thus,
crr 2 b FS)
2
Thus,
ba
Pr err (0)
2 0.995.
64a T
Now, 7 logn for sufficiently large ei and also have 2010 m [T]
2 by Equation 19
since
a100m 2 2 since a S 1/2 and we are in the case where 10 S [T] Thus,
log n 25mm
Pr 8.x
err (0)
2 0.995.
This establishes Equation (18 for C3 2 256 x 105.
D Proofs for random knowledge graph
Our goal in this section is to prove Theorem 3.2 The proof is based on the following main lemma. We first state and prove this lemma, and then derive the theorem from it. Recall that the sets T. T x ===² 2 represent the edges of the two knowledge graphs.
26

---

Lemma D.1. Fix 1 C :: y + Y s, E (0, = 1 and
In(1/5)
c pa pa²
For any Y,,,o) chosen from the random knowledge graph distribution, we define
A {y T
Fly) +
B = (y E A
π (w) P}
C E
y $ P}
Then,
Pr T.P
A 2TT A B - |C|
29
|A|
s 56.
2
Proof. Let A' = {y S² ((y) fy) so A
A'. If h is the identity then the lemma holds trivially, therefore can assume that A' * (8. e > 1 then the lemma holds trivially as well, because A C T and therefore |A| < (T', so we assume e E ().
For each y A', Equations 1 and (2) under Definition 3.1 imply that Pr(y C1 = Prly E P|
(1 - a)pq and Pr(y E A = Prly ET| p. thus Bayes rule gives
Vy A' Prly VEE A]= (1 (1-w)pg a)pp
a))--
p
Now suppose we fix V S and condition on A'n = V. Note that the event y C' is independent for different y E V, therefore for any V holds that
Pr. w E
VJ Pr. ly E 1 E A = (1 a)).
Pp
A Therefore, B|[C| ||C||A==1 V = (1 44) and so Chernoff bound gives
S A'
Pr T.P
c s (1-a))/ |/ V 2 A|in
A=V 2 1-
(Normally, Chernoff bounds would give the tight inequality that xr|ic)<...121) the above is necessary for the case in which A 0 in which case Chernoff bounds do not apply because it would be over |A| 0 coin flips.) Since this holds for every V, we have:
2 8, but the <
Pr T.P
a)9/A +
V 14
2 1
(24)
8
By Lemma C.2
partition A' into three disjoint sets,
A' A₁ U A/ A/g such that =(Ai) 0 A/ 0.
As above, we are going to condition on the value of A; = A n. Also, define,
B, {u A, K (v) & P) B BOA,
Now, fix any E [3] and any set C A'. We now claim that for all E [3], V A/, and y V
Pr T.P.
PLIVE B
A = Pp (T()) P y = q.
The rightmost equality follows from the fact that 7 (1) # y (vy) & P is independent of y T. The leftmost equality follows similarly: Since (A4) 0 A = 0. the event A; = V is independent of T (v) P. Thus, again by Chernoff bounds we have
Vi E [3] VV C A
Pr T.P
[BI2 [ g/Ai
| In
A = v > 2 6.
Since this holds for all V, it holds unconditionally, and by the union bound follows that
Pr T.P
ViE
3
A. 8
2 1 35.
(25)
27

---

Now, since the sets B; partition B and A, partition A, we have = = E, | = [A, and also >
Ail I /3 by Cauchy-Schwartz. Thus, summing the three equations in Equation 25 probability implies
1 5 V ||
Pr T.P
B 2 g) A|
2 1 - 36.
Combining with Equation
24
gives, by the union bound,
3 A
1
Pr T.P
B
C 9/
V
(1-a))gl -11-a)/AA
(1-
V |n 8
21-40 46.
Since v3/2 + 112 < 2, this implies:
1
B |C| 2 ag|/i 2 2/ |4|
2 21 48.
T.P
6
Or equivalently,
og| < 2//11 S 45.
Pr T.P
[B] | - -B|-1C|-
Since adding additional restrictions can only reduce a probability, we have:
p|s
| A < aql - 22 |A In
1
Pr T,P
S
T
S
46.
2
8
But if p|
<
AAI
then A|
cp|S|² and then, since
32
In J.
2
S|
A
2
09
2
A In
< 2
| In 8
S
2|
In 8
|.A..
8
Sp
p
32
In
2
aty-p1s
Thus,
S|S
A
aq |4|
Pr T.P
|T|
S
A A
B
|C|
S 45.
Since, in general, for any two events X and Y it holds that Pr[Y]
& Pr[X, Y + Pr[X], we have
A
ag
S|
A
ag
Pr
A
|C|
A
<
Pr T.P
[
<
A B
|C|
|||
+
T.P
e
2
D|S|2
Pr
|
T.P
2
Sp
< + Pr
T
T.P
2
< 48 + 6,
which is equivalent to the statement in the lemma. To see the last step above, note that B[[T] S/S12 and thus by multiplicative Chernoff bounds,
Pr T
S <
S exp
p|S|
S exp
p|S|
32
In 5 = 8 8 < 8.
2
8
Q2
In the last step have utilized the fact that a, q, 8 E (0, 1], and the fact (observed in the first paragraph this proof) that we may assume that e E (0, 1] else the lemma holds trivially. r
Using the above lemma, now prove main theorem regarding knowledge graphs.
28

---

Proof. of Theorem 3.2 Let = 1 - and,
64
6n 91
2
6n |1
= max
sSp
In
oq V
m
In
8
For any 0 O define,
Ag {y T Toly) * y)
Bg = {y Ag mo(y) $ P)
C. (y Ag y P}
Note that since err( |Aa our goal to show that, with probability 8, will not output any 0 with AAg 2 <(?".
Recall that [0] I s By Lemma D.I substituting
তe 8 and the union bound over 0 E
which is of size |0| < 18
aq
58
Pr T.P
3 E θ |Aal 2 e A Bal - 1Ca S
|Aa]
2
6
Using err(0) = | , this implies,
aqc
T
56
Pr T.P
3 E θ err(0) 2 Bol
-Cal
1
2
6
Ba
[Cp
aqe
56
Pr T.P
30
( 2 E
S
(26)
[
T
2
6
Finally, define the empirical "errors" for any to be,
é (i fo(2.) P).
It is not difficult to see that the algorithm outputs a & with minimal ég, and thus it will not output any with ég - é. > O. Now, it also not difficult to see that ég é. the mean of m random variables in 1 1,0,1] 1 and
= Bg [T]
Ca [T]
Eie e Pr (TO(V) & P Pr M
The last step above follows because is the identity, and because if y To then y E P + TV) E P. (Formally, one may define Eg == (y E T To(y) & P} and observe that Bg C Eg. Co C E. and Eg \ Ba E. Co). Thus, by Chernoff bounds.
Ba T
Ca
2
6 ln
VO E
Pr 21....mm
ég é 5
By the union bound over 0 E θ,
BB
Co
6
8
Pr
3 èo - è. 5
In
<
T
T
m
6
Combining with Equation 26 gives,
agc
2
6 6
58
8
Pr
m e err(0) e ê0
S
In
8.
T.P
m
8
Since, for our choice of c 2
og In l88
2
Pr 30 E θ err(0) 2 E T.P
E, 50
29

---

for Put another way,
Pr 40 E e err(i) S v én é, 0] 6.
We claim that we are done: Observe that MLE outputs some 0 # * then, bo S by. To see this, recall the definition of the prior
(lo(z)) = (1 +
( ) fo(c)) if fo(x) E
2
and therefore the objective function minimized by MLE, namely, 1n E log(p(f((z;))), is strictly monotonic in bg:
m
log(p(Jo(x:))) by log 1/13
+11 bo) log 1/1P| 1/13/
2
+ bo -log 1/1P| 1/12/
=log 1/1 + 1/131
1/131
so the I output by MLE necessarily minimizes bg.
Finally, for the simplification in the theorem, note that for 0.99, 1/g 100 is most constant and note that a maximum is never more than a sum.
It is interesting to note that it is possible prove the same theorem using generalization of Plausible Ambiguities, though we use the shorter proof above here because it is somewhat more involved. This generalization may be useful for other priors of full support. Many LMs, in practice, assign non-zero probability to every string due to softmax distributions or a process called "smoothing." A full-support prior p has full support, then A., θ and so the parameter E-y becomes too large to be meaningful even for 0. To address this, we refine our definition of plausible ambiguities as follows. For generality, semantic eтror C err.
state them in terms of arbitrary loss L. though we only use them for the
Definition D.2 ((y, -ll-uuusieeeee ambiguities). For any 7, K. E [0, 1}, the set of (7, plypuussibblle
ambignities is:
Ay, { I
Pr Pr(p(=((v)) SM and Ey,x max L()). yut
BEA,
Furthermore, A, = Ay,o and Ey = Eq,0
E Experiments
For the experiments used generate Figures 4 and we sampled random languages according ei- ther the knowledge graph model or the common nonsense model, and then used a brute-force learning algorithm to find the optimal translator given increasing amount of samples. A detailed description follows, and code can be found at htttt:://// /ttpp/s/////httt/t//// com/ hotpbuu//ooo/orrttet/tttr of unt
E.1 Experiments in the knowledge graph model
Recall that in the knowledge graph model, text describes relations between nodes in a directed graph. Due to computational constraints, we consider ten nodes, each corresponding to a different word in the target language. To generate edges corresponding to the target language P, two nodes are connected with a directed edge independently, with probability 0.5. We then consider source languages with < 10 words. Given a ground-truit -truth translator f.: [r] + [10], the source language graph is obtained by choosing a random subset of nodes of size r, taking the pre-image of graph induced on S under f., and (3) adding noise by redrawing each edge with probability fixed agreement coefficient a E 1).
The prior is derived from the edges of P. and the source language is derived from the (noisy) permuted subgraph T. We consider the translator family {fo E Q) of all node-to-node (word- to-word) injective translators, of which one is secretly chosen to be ground-truth. Similarly to the
30

---

Name
Symbol
Value
Number of source nodes
f
1, 4, 10
Number of target nodes
n
10
Number of training data
77 1,2, up to all edges
Edge density (probability of including an edge)
P
0.5
Agreement parameter
0, 0.33, 0.66,
Figure 7: Parameters for experiments in the knowledge graph model (Figure 4). For ablations on take 0.5, and for ablations AWS r6i 4xlarxe for a total two and a half CPU-hours.
take 9. The experiments were in parallel on
Name
Symbol
Value
Number of source sentences
T
105
Number of target sentences
P
106
Number of training data
m
1,...,
100
Number of validation data
1000
Fraction of common nonsense
0,0.1....,0.. 0.8
Figure 8: Parameters for experiments in the common nonsense model (Figure The experiments were run in parallel on an AWS 4xlare for a total of four CPU-hours.
previous setting, we train an MLE algorithm on randomly chosen edges from T, which correspond to sentences in the source language. For each sampled edge (x1, 12), increase the "score" of each translator that agrees with the edge, that is, that (ff())), (x2)) is an edge in the graph P.
To show how common ground affects translatability, we ablate the parameter determines the fraction of edges on which the source language graph and the target language graph P agree. Figure E validates the intuition that increased agreement results in lower translation error, and that as the number of samples increases, the error of the top-scoring translator decreases.
To show how language complexity affects translatability, we ablate r, which is the size of the subgraph corresponding to the source language. Figure (right) validates the intuition that larger subgraph results in lower translation error.
The error of translator is computed as the fraction of edges whose labels different than the ground-truth. The values with which the model is instantiated are detailed Figure 7
E.2 Experiments in the common nonsense model
Since in this model the structure of sentences is arbitrary, represent sentences by integer IDs, [10*] = 1,2,... .2.....0' 10 and [10*] for the target language. We generate a prior from the common nonsense model by taking the target sentence ids [10 and labeling random a-fraction of them as nonsense; the remaining sentences are called sensical S. Given ground-trun -ruth translator fx: [10*] the back-trane takkssaansltoon of sensical sentences,
[10%] the source language then distributes uniformly (S).
The translator family [Jo E θ} is taken to be set of 10 random one-to-one translators, of which one is secretely chosen to be ground-truth f.. We then train an MLE algorithm on random samples from the source language: Each sample such that fz( & S. i.e., nonsensical.
rules-out subset of translators, namely, all 0 e θ
Figure that as the number of samples increases, the average error over the plausible translators (that have not been ruled-out) decreases. To show how language complexity common ground affect translatability, we ablate the parameter which determines the fraction of common nonsense. Our experiments validate the intuition that increased common nonsense results lower translation error. The error of a translator is computed as the fraction of disagreements with the ground-truth on hold-out validation set of size 1000. The values with which the model instantiated are detailed in Figure g
31

---

F
Related work
Project CETI. The sperm whale data collection effort began with longitudinal dataset from community of whales off the coast of Dominica that revealed interesting communication findings, such as dialects and vocal clans [16]. A recent effort by the Cetacean Translation Initiative (Project CETT) has been to collect custom-built passive bioacoustic arrays (installed in Fall 2022) covering a 20 x 20 kilometer area where these whale families reside (collecting over 3 TB/month) in tandem with on-whale robotic acoustic and vidco tags, underwater (robotic swimming fish) and acrial drones as well as other observation techniques in efforr to augment rich contextual communication data. CETT's scientific team consists of specialists in machine learning, robotics, natural language processing, marine biology, linguistics, cryptography, signal processing and bio-acoustics. Andreas et al. 2 present CETT's initial scientific roadmap for understanding sperm whale communication, identifying the potential for unsupervised translation to be applied to whale communication. That roadmap suggests training full generative LM for whale communication (often using trillions of bits for parameters [T] (2).. In contrast, our analysis suggests that the data requirements for translation may be similar to those of supervised translation, which is often several orders of magnitude smaller [37].
With this setting in mind, our requirements from source and target language are not symmetric: it would be unreasonable (and unnecessary) for our framework to assume that any sentence in the target language could be expressed in the source language. Put simply: whales need not understand what a smartphone is for us to gain some understanding of their communication. Also note, regarding domain gap. that some (although not all) knowledge can be inferred by training data from, e.g.. online catalogs of hundreds of thousands of marine species []. Of course, there are also data-collection and transcription challenges, a challenge also present in the setting of low-resource (human) language translation (31) While these challenges are outside the scope of this paper, our theoretical bounds on the data requirements may inform how much and what types of data are collected. For instance, it is less expensive to acquire textual data alone than both textual and video data. Therefore. if it is believed that an adequate translation statistically possible using textual data alone, then greater effort may be placed on collecting this data and on UMT algorithms.
Unsupervised translation. In unsupervised machine translation (32 translator between two languages is learned based only on monolingual corpora from each language. A body of work on UMT uses neural networks (2 23 5 24 351 or statistical methods 25 for this task. Empirical evaluation of UMT found that it is outperformed by supervised machine translation. even when UMT is trained on several orders of magnitude more data [28] 22). Among the key barriers for UMT identified in these evaluations are the domain gap and the data gap, and recent works propose techniques for bridging these gaps 15 19. Our theory suggests that sample complexity should remain roughly the same between the supervised and unsupervised settings, barring computational constraints. This, we hope, will encourage practitioners to bridge the remaining gaps.
Language models (LMs). In recent years, LMs such as GPT 11. BERT 13 and PaLM 12 were shown to achieve state-of-the-an performance on many tasks in natural language processing (NLP) such as text generation, summarization, or (supervised) MT. These models are indeed large, with hundreds of billions of parameters, and are pre-trained on hundreds of billions of tokens.
LMs are useful for machine translation in a variety of ways (e.g. [T0 (8)) Of particular relevance are empirical works that use target LMs as priors to improve machine translation (27 77. To our knowledge, our work is the first theoretical work formally proving error bounds for psior-assisted translation. Appendix BaainddixiHiiuuuu discusses the use of LMs to establish priors for translation.
Goal-oriented communication. It is interesting to contrast our work with the work on goal-oriented communication, which was introduced by (2]] and extended in [17]. They study the setting two communicating parties (one of which is trying to achieve a verifiable goal) using each a language completely unknown to the other. They put forward theory of goal-oriented communication. where communication is not an end in itself, but rather a means to achieving some goals of the communicating parties. Focusing on goals provides way to address "misunderstanding" during communication, as in when one can verify whether the goal is (or is not) achieved. Their theory shows how to overcome any initial misunderstanding between parties towards achieving given goal. Our setting is different: Informally, rather than be a participant in communication with someone
32

---

Sentence
Probability
I just ate giant squid.
1.5 x 10-9
just ate a giant cheeseburger.
1.9 x 10-8
A sperm whale said: I just ate giant squid.
6.8 x 10-14
A sperm whale said: just ate a giant cheeseburger.
1.2 x 10-17
Figure 9: Without using prompt, the sentence just ate giant cheeseburger is more likely, but using the prompt sperm whale said', the sentence just ate a giant squid is much more likely. Probabilities are from the GPT-3 API.
speaking a different language, we wish to translate communications between two external parties speaking in language unknown to us and there is no verifialle goal to aid us in this process.
Subgraph isomoprhism. For simplicity, model the knowledge graphs of Section as pair of correlated Erdós-Réng (ER) graphs. The computational problem of identifying a subgraph of an ER graph has been studied by Erdós and others 6 26 20) In particular, (20] consider model in which two correlated graphs P, T are derived from a "parent graph" G by independently deleting rows and edges G, and then applying permutation x the vertices of T. Although their model differs from our knowledge graph model 15 they propose efficient algorithms for recovering the latent permutation x² and provide an empirical evaluation on synthetic and real-world data. Given the similarity between our models, it would be interesting to see if their algorithm can be adapted to our setting, which would nicely complement our proee---ooo-----eeeeeee senfffiiet- algorithm.
G
Future Work
Our initial exploration leaves plenty of room for future work. In particular, we propose the following possible directions:
In our lossless models, the target language subsumes the source language in the sense that everything that is representable in the source language can also be represented in the target language. would be interesting to extend our work to the partially case.
2. The language distribution in our models are all uniform. It would be interesting examine non-uninn con-uniform distributions such as Zipfian or power-law distributions.
3. As stated earlier, analysis is purely information -hherrrtttt and leaves the question of the efficiency of UMT open.
4. A good starting point for the efficiency question would be design efficient UMT algorithms for one the randomized models of language presented in this paper.
H Good Priors through Prompts
The most direct way to improve prior is to train (or fine-tune) the I.M on dataset that includes large number of articles relevant to the source language, e.g., volumes of oceanic research, for whales. In addition, training on wide variety of sources including multiple languages, diverse sources, and encoding systems may be helpful. It is possible that system that has how to transfer knowledge between hundreds of languages and even programming languages, may have better prior.
Another general strategy for creating prior is to use prompting: Given prompt string one can define p(y) x v(s y), that is the prior distribution of text that that LM generates conditioned on the text beginning with s. Figure Saneeellluue illlsttrates some toy examples of how even simple prompt like A sperm whale said: can help focus on translations that are more likely for a sperm whale to say, and eliminate irrelevant translations.
In the knowledge graph (a) the vertices If are always subset of the vertices of P. and (b) the deleted vertices are fixed rather than randomly chosen
33

---

Background prompts. There is natural and potentially powerful idea that an unsupervised translator, in addition to outputting translations, would automatically generate a background prompt that increases the intelligibiliit of many translations! 16 Suppose, for example, across numerous communications, the unsupervised translator determines that sperm whales measure time "number of naps" and that typical nap duration varies by age. Then, rather than having to repeatedly explain this in each translation, it can explained once a background prompt that is automatically inserted before each translation. For example, following the prompt
Sperm whales measure time in numbers of naps. but each whale's typical nap duration depends on their age. So a whale's nap duration is 9 minutes, then naps about 36 minutes (though whales tend to exaggerate times). A sperm whale said:
would make translations like Wow, I just dove for 6 naps or How many naps ago was that? both more likely and more understandable.
I Generalizations of the framework
I.1 Lossy Translation
Many things can be included in textual transcriptions suitable for translation. For instance, one can distinguish the speakers, e.g., "Whale 1: Whale 2:
Whale 1:..." if the source data is annotated with speaker identifiers. Some aspects of the way one is speaking can be transcribed, e.g., "Whale
(fast tempo clicking): Whale (slow, loud clicking): It may be possible to encode these textually x.
However, x is encoded a more flexible format, such as arbitrary binary files, one can include as much raw information as possible, including the source audio recording, to provide the translator with as much context as possible. In that case, lossless translation will no longer be possible, because one cannot compute the raw from a textual translation.
Given the possible benefits of such annotations, we propose an extension of our theory to the lossy setting. A natural generalization of the maximum-likellhonn approach is as follows:
1 log p(S(x,)) - ā log sio (2r fo(x:))
min 8EB m
Here du: X' x y + [0, 1] is a probabilistic inverse ("randomized back translation") of f whose parameters are also encoded in 0. Note that the family {(fe, Φe) 0 E θ} must satisfy that for all E y. Exe/-(() (x y) 1. though it is no longer required that fo be 1-1.
X' - y and de that are not perfect inverses, where there is some (with positive probability under μ1) such that do(a y - fo(x)) < 1. Thus, for sufficiently small X, the algorithm is exactly the minimum cross- entropy (maximum likelihood) algorithm of Definition I.I For arbitrarily large X, the algorithm will collapse to always outputting the most likely E y under p. For example, everything could be translated to Hello regardless of its contents.
As À decreases to O, the optimal solution would assign infinite loss to any fo:
For intermediate values of X, the chosen translator trades off naturalness in the form of ff (x)) versus information loss which is inversely related to ( y fo(x)). This trf makes challenging to define and analyze the success of a lossy unsupervised translation algorithm. Nonetheless, the algorithm is intuitive.
I.2 Infinite parameter sets
In some cases, one can learn with many fewer examples, which is important when parameters are real-valued and |e| oc or when the model is over-parameterized. However, one can analyze even these cases in our model using the following "trick." " Suppose one has a supervised translation algorithm SUPER that takes m labeled examples (æ,, yi) as input and outputs 0 E e. A simple
In general, the problem of Al-based prompt generation has recently attracted attention, e.g.. (34
34

---

observation in these cases is that one could use an initial set of m unlabeled examples, 21, Fm. define a subset of translators:
2 (SUPER (SUPER((211.00) U1), (12,, y2), (F Um)) yı, 3/2 -.. V/n E c)).
That is, we restrict attention to the set of possible translators that we could output for any given ground-truth translations, then it is not difficult to see log [ S m log [ If we assume that one of these is accurate and natural, then restricting the attention of MLE this will suffice, and Theorem A.2 means that the number of examples required is Ollog (@) Om log (3[) which is linear blowup in the number of examples m used for supervised translation. To make this formal, one would start from only assuming that one of the translators had negligible error-this left future work.
J Bounds for Supervised Translation
In this work, for ease of presentation, we have stated that error decreases like O 1 log - for m noiseless supervised translation. This is based in the classic Occam bound for supervised learning:
@
Theorem J.1 (Oceam bounds). Let X, V, be sets, D be a joint distribution over X x V, l: y x
Y + [0 be loss, and fo X' + y be family of functions parameterized by A O and (()) = E( ((n.i)-((((() fo fo(x))).
For any 5 > 0,
1
O
Pr (o. Min Dm
((0)
In
21-8
if [(+) = 0,
m
8
O
Pr (11.))) (Zm Min M Dm
((0) S ((+)
V
ln
1 8
if ((+) + O,
for 0 = argminngee E; (yyi (x.)))
Note that supervised translation is simply classification with many classes V.
As in MLE, ties be broken arbitrarily, e.g., lexicographically. Our bounds, like the Occam bound, hold simultaneously for all minimizers. In the realizable case, the Empirical Risk Minimizer will have Σ E(m, fo(z:)) 0.
35


Reviews:
[{"review_id": "SteUvd1mjt", "reviewer": "Reviewer_sQGQ", "summary": "The first contribution of this work is formalizing and analyzing a model of Unsupervised Machine Translation (UMT). The model applies even to low-resource source languages with massive domain gap and linguistic distance. Second, the paper exhibits two simple complementary models for which it is proved that:\n(a) more complex languages require less common ground, and \n(b) data requirements are not significantly greater than those of supervised translation (which tend to be significantly less than generative language modeling). These findings may have implications for the quantity and type of communication data that is collected for deciphering animal communication and for UMT more generally.", "questions": "What has changed in this submission from the arxiv version (https://arxiv.org/pdf/2211.11081.pdf)?", "limitations": "N/A", "rating": 9, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "This work is the first theoretical work formally proving error bounds for prior-assisted translation, which shows that the sample complexity should remain roughly the same between the supervised and unsupervised settings (specifically, the two stylized models of language -- Random sentence trees and Random knowledge graphs), barring computational constraints.", "weaknesses": "There isn't any empirical evaluation aside from using text-davinci-02 to evaluate sentence likelihoods", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your enthusiastic review and recognition of the importance of our findings, and  more generally of introducing a theoretical UMT framework.\n\n> There isn't any empirical evaluation aside from using text-davinci-02 to evaluate sentence likelihoods\n\nThank you for this great suggestion. To address this, we have added synthetic experiments to validate our theoretical results. See the pdf attached to our overall response. "}, {"review_id": "kqgb1o2Oow", "reviewer": "Reviewer_5Kio", "summary": "### Update\n\nI'm satisfied with the author's rebuttal and decided to overall improve my score.\n\n\nThis paper proposes a theoretical framework for analyzing Unsupervised MT motivated by animal communication. The paper is only the first step in the theoretical analysis of UMT. The theoretical framework was analyzed for two models: Knowledge graph and Common nonsense models. The authors show theoretically that the error rate is inversely related to the number of samples, common ground, and language complexity.", "questions": "Could the authors provide experimental findings for their theoretical framework? Take a simple case of language translation example and validate their theoretical findings using a few experiments. Right now, the paper focuses on the theoretical framework only. \n\nProvide more intuition on why they found error rates are inversely proportional to language complexity.\n\nImprove the connection with learning animal communication. There was very little discussion about animal communication apart from the introduction section.", "limitations": "The authors did not provide any limitations on their work.", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "The authors work on providing a theoretical framework for analyzing unsupervised MT. The task is motivated by a real-world challenge of understanding animal communication.\n\nThe paper is well-written and was not too hard to follow. The general framework was well-defined and motivated. \n\nThe paper instantiated two models with common-nonsense and knowledge graphs. The paper derived theoretical bounds for error rates and provided comprehensive proof.", "weaknesses": "Purely descriptive: what is the key takeaway from the paper? How can we improve unsupervised MT based on these findings? Where can we use the theoretical framework?\n\nNo experimental results? I realize the paper focuses on the theory of unsupervised translation. However, none of the author's theoretical claims are validated using experimental findings which I find a bit hard to follow. \n\nThe authors claim that the error rate is inversely proportional to language complexity. This is counterintuitive to what I would expect in Machine Translation. However, there is no in-depth discussion, reasoning, or intuition as to why this is the case. Additionally, the related work or motivation section is missing in the main paper, where I believe they should motivate UMT.\n\nI missed the connection in the paper with learning animal communication. The paper initially has a strong motivation to learn animal communication, however, the discussion section is weak and I could not find what to conclude, or whether can we actually use the unsupervised MT theoretical framework.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review and detailed feedback.\n\nWeaknesses:\n> Purely descriptive: what is the key takeaway from the paper? How can we improve unsupervised MT based on these findings? Where can we use the theoretical framework?\n\nWe believe strongly that our theoretical findings are illuminating despite the fact that we do not introduce a new algorithm (theoretical ML results often provide insights rather than new algorithms, such as *The no free-lunch theorem* and *The lottery ticket hypothesis*). To quote the reviewer who gave us a score of 9 :-), *\"These findings may have implications for the quantity and type of communication data that is collected for deciphering animal communication and for UMT more generally.\"*\n\nIn particular, a fundamental question facing scientists working on translating animal communication is: **how much and what kinds of data need to be collected?** Our findings suggest that unsupervised data alone may suffice, at least from an information-theoretic/sample-complexity perspective. For example, [1] discusses that the project must decide how to allocate its data-collection investments between pure audio and other more expensive modalities such as video. Our work may shed light in this direction.\n\nAnd to quote another reviewer discussing their takeaways regarding how UMT works: *In my opinion, this paper’s assumption about the existence of a set of plausible translations is very realistic and insightful for understanding the mechanism of unsupervised translation. As far as I know, attributing the success of unsupervised translation to this characteristic is novel and I think it is convincing (though may not be a complete explanation).* They then go on to say,\n*\"The knowledge graph model is inspiring to me. I think it suggests that the success of unsupervised translation is because of the interaction between some high-level structure and some low-level structure of language. In this model, the high-level structure is the plausibility of the combination of nodes, while the low-level structure is the one-to-one mapping of the nodes.\"*\n\n> No experimental results? I realize the paper focuses on the theory of unsupervised translation. However, none of the author's theoretical claims are validated using experimental findings which I find a bit hard to follow.\n\nThank you for this great suggestion. To address this, we have added synthetic experiments to validate our theoretical results. **See the new experiments in the pdf attached to our overall response.** \n\n> The authors claim that the error rate is inversely proportional to language complexity. This is counterintuitive to what I would expect in Machine Translation. However, there is no in-depth discussion, reasoning, or intuition as to why this is the case. \n\nWe are glad you find the result surprising. The intuition is that simple languages, as we see in our experiments, admit many plausible (but erroneous) translations. Consider a trivial language (e.g., of a cow) which has two utterances, $A$ and $B$, meaning \"I'm happy\" or \"I'm sad\"--one could not confidently get error less than 50\\% in an unsupervised setting without any clue about which is A and which is B.  On the other hand, real-world constraints mean that we expect translations like \"The shark ate the salmon\" more than \"The salmon ate the shark,\" which can make it feasible to eliminate a constant fraction of incorrect translators. More complex languages have more such constraints that rule out more erroneous translators. An example is illustrated in Figure 2 in the original submission, and we will add more intuition to the paper. In analogy, imagine solving a hard jigsaw puzzle with only blank white pieces. If there were just two identical square pieces, it would be trivial to fit them together but there would be no way to gain confidence that you had the pieces correctly positioned. In contrast, if all the pieces had unique, complex shapes, there may be only one way to fit them all together. \n\n> Additionally, the related work or motivation section is missing in the main paper, where I believe they should motivate UMT.\n\nThank you for the suggestion. If our paper is accepted, we will be given an extra page and will add a related work section (currently in Appendix E) to the paper. The main motivation for the work is understanding animal communication, as discussed in the introduction.\n\n# References\n\n[1] Jacob Andreas, (and 19 others). Toward understanding the communication in sperm whales. iScience, 25(6):104393, 2022. ISSN 2589-0042."}, {"review_id": "X4AE50QJ9T", "reviewer": "Reviewer_7v3M", "summary": "The paper describes a theoretical analysis of error bounds for unsupervised machine translation, motivated by considering the unusual, and so far only speculative, case of translation between animal \"languages\" to human natural languages.\n\nThe paper consider the case where a number of examples of the source (animal) language utterances are available, as well as a prior on the target language (e.g., a conventional pretrained LLM), and attempts to investigate what error an invertible translation function trained to maximize a MLE objective may achieve compared to a hypothetical golden truth translator.\n\nThe paper considers two specific cases with different assumptions over the languages and the priors: in the first case the languages are assumed to be Erdős–Rényi random graphs parametrized by an edge agreement parameter. The authors prove a bound which does not vanish even in the limit of infinite source sentences but vanishes in the limit of perfect agreement. I do not find this model to be very realistic for natural languages.\n\nThe second case consider the two languages to be uniform distributions over a subset that excludes a \"nonsense\" set. The authors prove an bound similar to supervised learning. I am not sure why uniformity is considered a plausible hypothesis here, as actual natural languages are characterized by power law distributions.\n\nOverall, I think there is not enough justification connecting the formal models with the motivation of translating animal communication.\n", "questions": "Is there any evidence that the formal models you propose can correctly capture the relevant factors of unsupervised translation even between human languages, let alone between animal and human languages?\n\n", "limitations": "Yes.", "rating": 4, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "- Novel and interesting topic.\n\n- Theoretical analysis.", "weaknesses": "- Assumptions not well justified\n\n- Formal model not well connected with motivation\n\n- Too much background and related work is missing. Some is provided in the supplementary material, but it should be in the main paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review and feedback. We are glad you find the topic novel and interesting.\n\n> Assumptions not well justified\n\nWe make the assumptions and justification more explicit in the paper, as follows. The two assumptions underlying all our models, are:\n\n1. There exists a hypothetical translator from the animal to human language (e.g., a hypothetical \"mermaid\" Transformer) that does not have a prohibitively large number of parameters, specifically the number of parameters needs to be fewer than the number of animal data.\n\nFor assumption 1, neural networks have proven useful for translation, e.g., between (human) natural languages, between images and natural languages, speech and text, between programming and natural languages, etc. It seems plausible that they could translate animal communication, or at least as well as a hypothetical mermaid could if one existed. To understand the number of parameters required, as discussed in the submission, translators often require fewer parameters than the underlying LMs. Because human language is compositional, it is possible to translate the sentence \"The tuna ate the mackerel\" to French by knowing the meanings of tuna, mackerel and ate and their French equivalents (and grammar)--one does not need to apply the knowledge of whether tuna eat mackerel or vice versa. In contrast, we have learned from GPTs that a good LM must be able to spit out encyclopedic articles about tuna and mackerel fish. Our knowledge graphs model this type of phenomenon, for example for a “food web,” the nodes correspond to fish and the edges correspond to which fish eat which other fish. In some sense, the crux of the low-complexity translator assumption is that the source animal language is also compositional, deriving their meaning from the meaning of smaller units composed together. As discussed in the paper, some simple animal languages have already been shown to be compositional, and compositionality is useful for language efficiency. \n\n2. There is common ground between the languages, e.g., there are certain things that are implausible in both languages.\n\nFor assumption 2, LMs embed many properties of nature, as can be seen by the fact that GPTs (trained unsupervised on natural language corpora) can write accurate articles about each fish, currents, diving, and many other topics, full of details that may also be known to animals such as whales. If an animal language is sufficiently rich, it should also embed similar real-world knowledge. The common ground includes knowledge that \"the shark ate the salmon\" is more likely than \"the salmon ate the shark\". \n\nMoreover, as discussed in the paper, there are currently several major interdisciplinary efforts under way to translate animal communication  [1, 2] involving interdisciplinary teams of linguists, marine biologists, and computer scientists, whose efforts are resting on the assumption that translation is possible. Our models formalize what assumptions are required for unsupervised translation. \n\n> Too much background and related work is missing. Some is provided in the supplementary material, but it should be in the main paper.\n\nThank you for the suggestion. If our paper is accepted, we will be given an extra page and will add a related work section (currently in Appendix E) to the paper.\n\n> Is there any evidence that the formal models you propose can correctly capture the relevant factors of unsupervised translation even between human languages, let alone between animal and human languages?\n\nFor unsupervised translation between human languages, the main findings are consistent with our models: more data and more common ground improves translation accuracy. For example, accuracy increases as the amount of ``common ground'' or overlap in training data topics [3]. \n\n\n## References\n\n[1] Jacob Andreas, (and 19 others). Toward understanding the communication in sperm whales. iScience, 2022.\n\n[2] Emily Anthes. The animal translators. The New York Times, 2022.\n\n[3] Jiajun Shen, Peng-Jen Chen, Matt Le, Junxian He, Jiatao Gu, Myle Ott, Michael Auli, Marc'Aurelio Ranzato. The Source-Target Domain Mismatch Problem in Machine Translation. EACL, 2021."}, {"review_id": "ly82U45NTh", "reviewer": "Reviewer_LYrz", "summary": "This paper introduces a theoretical framework for unsupervised machine translation (UMT) when no parallel data available and source and target language do not share similar linguistic structures. To do this, they first define and clarify the three main challenges: understanding the goal, no linguistic structure shared and domain gap. In response to these challenges, they propose a general framework and instantiate it with two models: knowledge graph model , which is highly structured with text representing an edge between a pair of nodes, and \"Common nonsense\" model which is completely unstructured. For both models, they establish the error bounds and demonstrate that the error rate is inversely related to the amount of samples, common ground, and the language complexity.", "questions": "* I am not sure what the \"prior\" proposed in the text refers to, but I tentatively comprehend it to be a prefix LM, where the prefix may be a prompt like \"a whale said:\".\n* Why maximizing the likelihood of the prior implies translation. After all, the source language is not involved in the calculation of this likelihood, so how to reflect the fidelity of the translation?", "limitations": "Same as Weaknesses. Or can we consider a real experiment, such as mutual translation between knowledge graphs constructed by English and Chinese respectively?", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "* The paper presents a novel theoretical framework for UMT, which is needed but challenging in the field of UMT.\n* The authors propose two complementary models of language, one that is highly structured and one that is completely unstructured, which provides a relatively comprehensive analysis of UMT.\n* The authors provide theoretical bounds on the data requirements for UMT, which can inform how much data are collected for such tasks.\n* The authors' ideas are interesting and insightful, such as the motivating example in the knowledge graph model where one can complete the mapping based on the similar structure of the graph, and enough \"nonsense\" make a nearly unique mapping in \"common nonsense\" model.", "weaknesses": "* The paper makes strong assumptions about the language, which may limit the applicability of the proposed models in real-world scenarios. \n* The paper does not provide any empirical validation of the proposed theoretical framework and models. The absence of experimental results makes it difficult to assess the practical effectiveness of the proposed methods.\n* The paper does not provide a clear explanation of how the proposed models can be implemented in practice, which may limit their usability for practitioners in the field.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review and feedback.\n\n> The paper does not provide any empirical validation of the proposed theoretical framework and models. \n\nThank you for this great suggestion. To address this, we have added synthetic experiments to validate our theoretical results. See the pdf attached to our overall response. \n\n> The paper does not provide a clear explanation of how the proposed models can be implemented in practice, which may limit their usability for practitioners in the field.\n\nWe believe strongly that our theoretical findings are illuminating despite the fact that we do not introduce a new algorithm (theoretical ML results often provide insights rather than new algorithms, such as *The no free-lunch theorem* and *The lottery ticket hypothesis*). To quote the reviewer who gave us a score of 9 :-), *\"These findings may have implications for the quantity and type of communication data that is collected for deciphering animal communication and for UMT more generally.\"*\n\nIn particular, a fundamental question facing scientists working on translating animal communication is: **how much and what kinds of data need to be collected?** Our findings suggest that unsupervised data alone may suffice, at least from an information-theoretic/sample-complexity perspective. For example, [1] discusses that the project must decide how to allocate its data-collection investments between pure audio and other more expensive modalities such as video. Our work may shed light in this direction.\n\nAnd to quote another reviewer discussing their takeaways regarding how UMT works: *In my opinion, this paper’s assumption about the existence of a set of plausible translations is very realistic and insightful for understanding the mechanism of unsupervised translation. As far as I know, attributing the success of unsupervised translation to this characteristic is novel and I think it is convincing (though may not be a complete explanation).* They then go on to say,\n*\"The knowledge graph model is inspiring to me. I think it suggests that the success of unsupervised translation is because of the interaction between some high-level structure and some low-level structure of language. In this model, the high-level structure is the plausibility of the combination of nodes, while the low-level structure is the one-to-one mapping of the nodes.\"*\n\n\n> I am not sure what the \"prior\" proposed in the text refers to, but I tentatively comprehend it to be a prefix LM, where the prefix may be a prompt like \"a whale said:\".\n\nYes, that is correct. The prior is a probabilistic model of text (i.e., a LM) which we anticipate might be generated by the translator. \n\n> Why maximizing the likelihood of the prior implies translation. After all, the source language is not involved in the calculation of this likelihood, so how to reflect the fidelity of the translation?\n\nWe are choosing the translator parameters (not the prior, which remains fixed) so as to maximize the probability (under the fixed prior) of the translations of the source data. In this way, the source language samples are crucially involved in the optimization process."}, {"review_id": "z3YxPO7KI6", "reviewer": "Reviewer_CDK4", "summary": "### After rebuttal\n\nThanks the authors for the detailed rebuttal, especially with new experiments. Provided the condition that the authors will add the new experiments and adjust the presentation after reviewers' comments, I gladly change my scores and recommendation!\n\n----\nThe paper presents a rather interesting theory about how unsupervised machine translation (UMT) without any parallel data. The paper taps into the analysis of world knowledge graph models, which may model relationships between objects/subjects of the world, and presented by words in the data. And suggests that it is the compositionality of languages somewhat allows UMT to work.\n\nThe paper also analyze the common nonsense model concept, where UMT generally tries to rotate the source distribution so that it can fit in a unique orientation in the target distribution, given enough nonsense data.\n\nThe paper presents some conclusion about the theorical error rate of UMT in relation with data and languages, though no experiments were done.", "questions": "N.A", "limitations": "There is no discussion of limitations.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 2, "contribution": 4, "strengths": "* The concept and analysis of the UMT in the paper is very interesting and novel.\n* The theoretical models of random knowledge graph and common nonsense models are interesting and should be investigated further.\n* Some observation from such formulation is that error rate is inversely related with language complexity, which is indeed non-intuitive, but there is no experiment to confirm such observation. ", "weaknesses": "\n* The paper is very math heavy with limited visualization or intuitive explanation. This makes it rather difficult to comprehend and and grasp the content. More intuitive explanation with figures and illustration are needed to understand. I am also unsure about the correctness of the formulation and the math, and can only assume it to be correct in the review.\n* There is no experiments to validate the theory at all, even with a toy experiments. This makes it hard to conclude the completeness of the paper.\n* The organization is not very well-structured and rather strange. There are no experiments and related work sections.\n* Despite heavily advertised in the initial part of the paper, there is limited correlation, conclusion, or elaboration about how we can model such human-animal communications, which is quite disappointing.\n* There is no clear indication and suggestion of what to do with UMT after reading this theory. The paper does not make recommendations on how to design better UMT models, how to train them, which aspects of existing UMT models need to be fixed so that it can handle low-resource languages and more ambitiously human-animal translations. This is real challenges that UMT performs very poorly when domains of unlabeled data sources are very distant.\n\nGiven the high degree of novelty of implication of this work, I would give much higher score if the rebuttal addresses some of the concerns.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> There is no experiments to validate the theory at all, even with a toy experiments.\n\nThank you for this great suggestion. To address this, we have added synthetic experiments to validate our theoretical results. See the pdf attached to our overall response.\n\n> The paper is very math heavy with limited visualization or intuitive explanation. \n\nWe have dedicated a significant amount of space (Figures 1-3 in the original submission) to visualizations aiming to provide intuition. We hope the newly-added experiments provide even more intuition.\n\n> The organization is not very well-structured and rather strange.\n\nWe will make our assumptions (and justification) more explicit as follows:\n\n1. There exists a hypothetical translator from the animal to human language (e.g., a hypothetical \"mermaid\" Transformer) that does not have a prohibitively large number of parameters, specifically the number of parameters needs to be fewer than the number of animal data.\n\nFor assumption 1, neural networks have proven useful for translation, e.g., between (human) natural languages, between images and natural languages, speech and text, between programming and natural languages, etc. It seems plausible that they could translate animal communication, or at least as well as a hypothetical mermaid could if one existed. To understand the number of parameters required, as discussed in the submission, translators often require fewer parameters than the underlying LMs. Because human language is compositional, it is possible to translate the sentence \"The tuna ate the mackerel\" to French by knowing the meanings of tuna, mackerel and ate and their French equivalents (and grammar)--one does not need to apply the knowledge of whether tuna eat mackerel or vice versa. In contrast, we have learned from GPTs that a good LM must be able to spit out encyclopedic articles about tuna and mackerel fish. Our knowledge graphs model this type of phenomenon, for example for a “food web,” the nodes correspond to fish and the edges correspond to which fish eat which other fish. In some sense, the crux of the low-complexity translator assumption is that the source animal language is also compositional, deriving their meaning from the meaning of smaller units composed together. As discussed in the paper, some simple animal languages have already been shown to be compositional, and compositionality is useful for language efficiency. \n\n2. There is common ground between the languages, e.g., there are certain things that are implausible in both languages.\n\nFor assumption 2, LMs embed many properties of nature, as can be seen by the fact that GPTs (trained unsupervised on natural language corpora) can write accurate articles about each fish, currents, diving, and many other topics, full of details that may also be known to animals such as whales. If an animal language is sufficiently rich, it should also embed similar real-world knowledge. The common ground includes knowledge that \"the shark ate the salmon\" is more likely than \"the salmon ate the shark\". \n\nMoreover, as discussed in the paper, there are currently several major interdisciplinary efforts under way to translate animal communication  [1, 2] involving interdisciplinary teams of linguists, marine biologists, and computer scientists, whose efforts are resting on the assumption that translation is possible. Our models formalize what assumptions are required for unsupervised translation. \n\n\n> There is no clear indication and suggestion of what to do with UMT after reading this theory. The paper does not make recommendations on how to design better UMT models, how to train them, which aspects of existing UMT models need to be fixed so that it can handle low-resource languages and more ambitiously human-animal translations. \n\nWhile we agree algorithms are important, theoretical ML results often provide insights rather than new algorithms, such as \"The no free-lunch theorem\". To quote another reviewer, *\"These findings may have implications for the quantity and type of communication data that is collected for deciphering animal communication and for UMT more generally.\"*\n\nIn particular, a fundamental question facing scientists working on translating animal communication is: **how much and what kinds of data need to be collected?** Our findings suggest that unsupervised data alone may suffice, at least from an information-theoretic/sample-complexity perspective. For example, [1] discusses that the project must decide how to allocate its data-collection investments between pure audio and other more expensive modalities such as video. Our work may shed light in this direction.\n\nAnd to quote another reviewer discussing their takeaways regarding how UMT works: *In my opinion, this paper’s assumption about the existence of a set of plausible translations is very realistic and insightful for understanding the mechanism of unsupervised translation. As far as I know, attributing the success of unsupervised translation to this characteristic is novel and I think it is convincing (though may not be a complete explanation).* They then go on to say,\n*\"The knowledge graph model is inspiring to me. I think it suggests that the success of unsupervised translation is because of the interaction between some high-level structure and some low-level structure of language. In this model, the high-level structure is the plausibility of the combination of nodes, while the low-level structure is the one-to-one mapping of the nodes.\"*\n\n\n> There are no experiments and related work sections.\n\nThank you for the suggestion. If our paper is accepted, we will be given an extra page and will add a related work section (currently in Appendix E) to the paper. As mentioned, we have added synthetic experiments to validate our theoretical results.\n\n## References\n[1] Jacob Andreas et al., Toward understanding the communication in sperm whales. iScience, 2022.\n\n[2] Emily Anthes. The animal translators. The New York Times, 2022."}, {"review_id": "3T1WjeAx7O", "reviewer": "Reviewer_FHLH", "summary": "This paper proposes a theoretical framework for understanding unsupervised translation and provides bounds for sample complexity. Specifically, the unsupervised machine translation setting they consider is that the translator $f_\\theta$ is the one that maximizes the plausibility $\\rho$ of the translation of examples $x_1, x_2, \\cdots, x_m$ in the source language:\n\n$$\\theta = \\mathrm{MLE}^{\\rho}(x_1, x_2, \\cdots, x_m) = \\arg \\max_{\\theta} \\sum_{i=1}^m \\log \\rho(f_\\theta(x_i))$$\n\nThe framework they propose has the following key components:\n\n- Prior $\\mu$: the distribution of the source language.\n- Prior $\\rho$: the plausibility of the translation in the target language.\n- Translator: $f_\\theta$ which they assume belongs to a finite-sized family.\n- Translation density $\\tau$: The distribution induced by the translator, i.e. $f_\\theta{x}$ where $x \\sim \\mu$.\n- A ground truth translator: $f_*$ that maps any input $x$ to a plausible translation almost surely.\n- Semantic loss: $L(\\theta)$ that evaluates how the translations by $f_\\theta$ is correct. They use exactly match (0-1 loss) as $L$ in the following analysis.\n\nAs instantiations of their framework, they propose two models of language:\n\n## Random knowledge graph model\n\nThis model makes the following assumptions:\n1. Text in this language represents an edge between a pair of nodes in a knowledge graph. \n2. The translator translates an edge by translating the two nodes respectively. \n3. The plausible edges in the source language largely agree with the plausible edges in the target language.\nBased on these assumptions the authors construct the distributions $\\rho, \\tau \\mu$, and then they provide the sample complexity bound for this model.\n\n\n## Common nonsense model\n\nThis model assumes no linguistic structure on the source text. They only assume that there is a set of translations that are implausible. They provide a sample complexity bound for this model. They also make connections to the complexity of the translator (description length).\n", "questions": "1. Please let me know if I misunderstood anything about the technical issues. I would be happy to adjust my score.\n2. Could you describe the meaning of the broader prior $\\rho$ and agreement $a$ in the context of real-world scenarios? e.g. what would we expect this $\\rho$ and $a$ to be in the real world?\n2. I wonder whether the back translation loss used in some unsupervised translation works is relevant to the one-to-one translator assumption in this work? Could it be helpful because the loss enforces the bijectivity of the model?\n3. I would also suggest the authors to include some experiments, perhaps with some toy data.\n", "limitations": "In my opinion, the authors should list their assumptions more explicitly and clearly, e.g. including them in a list or indexing them with numbers. Other than that, I think the discussion section addresses the limitations well.", "rating": 3, "confidence": 3, "soundness": 2, "presentation": 1, "contribution": 3, "strengths": "1. In my opinion, this paper’s assumption about the existence of a set of plausible translations is very realistic and insightful for understanding the mechanism of unsupervised translation. As far as I know, attributing the success of unsupervised translation to this characteristic is novel and I think it is convincing (though may not be a complete explanation).\n2. This paper also demonstrates how this assumption can be used to analyze unsupervised translation.\n3. I also like the consideration about having a plausible prior in addition to the ground truth translation distribution. It handles the mismatch between the domains of the text in the source and target language. I think this kind of domain mismatch is very common in practice and thus considering this helps us understand unsupervised translation better.\n4. The knowledge graph model is inspiring to me. I think it suggests that the success of unsupervised translation is because of the interaction between some high-level structure and some low-level structure of language. In this model, the high-level structure is the plausibility of the combination of nodes, while the low-level structure is the one-to-one mapping of the nodes (if I understood correctly).\n\nIn sum, I think I learned quite a few things from this paper. I think the community can benefit from these ideas.\n", "weaknesses": "## Clarity Issues\n\nThe first major issue to me is that this paper has a very unusual structure, i.e. having 5 pages of introduction. \n1. I would expect the introduction to talk more about the motivation and high-level intuition of the theory. However, the authors tried to elaborate many definitions in the introduction but at the same time mention a few things without clear definition. For example, I couldn’t understand “broader prior (line 69)” and “agreement (line 99)” when I was reading the introduction. \n2. Another problem of this long introduction is that there seems to be a lot of overlap between the introduction and the content in the following sections. Information in the later sections does not seem to be totally aligned with the description in the introduction section. For example, at line 101, the authors assume the compositional encoding of language, but this is not mentioned in Section 3.1.\n\nThe second  issue is that this paper never provides a high-level explanation for the proofs in the main text. It’s hard to assess the correctness of their results. I found the proofs in the appendix are not easy to follow either. \n\nThe third issues is that they rarely provide explanations for the symbols or the formulas either. For example, in Definition 3.1, they define many sets (e.g. $P, S$ etc) without describing their intuitive meanings. The usage of the symbols is also not very intuitive. For example, it seems that the $T, S$ and $P$ in Section 3.1 have different meanings than the ones in Section 3.2.\n\n## Technical Issues\n\nI have two main concerns:\n\n1. I doubt whether Theorem 3.4 is correct. Intuitively speaking, based on this model, there are many translators that never map any source text to an implausible target text. However, only one of them is correct. How can it be possible that the translator learned from MLE can be a good one without the access to other information? I also checked the proof in Appendix C.1.1. Line 714 seems to be saying it is suffice to prove that “large semantic error ($A$) implies many implausible translations ($B$)”, but the formula in Line 717 is more like saying “it’s impossible to have low error ($\\neg A$) while having many implausible translations ($B$)”. If the goal is to prove $A \\to B$, then I can’t see why we should prove $( \\neg A \\wedge B)$ is impossible.\n2. I think there needs to be more justification for how the instantiations are related to real world scenarios. One apparent example is the distributions of $\\rho$ and $\\nu$ constructed based on Definition 3.1, which is very complicated and is not intuitive. I would like to know whether this is also an abstraction of real-world scenarios.\n\nIn sum, I think this work is not ready for publication in this form, despite the interesting insights it has.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> **I doubt whether Theorem 3.4 is correct.** ...\n\nYou indeed found a typo in our proof overview intuition in section C.1.1. However, the theorem and proof are correct. We apologize for the mistake on line 717 and will correct it. Thank you for identifying it! Let us explain first the intuition and then the typo.\n\nYour intuition is correct when $\\Theta$ includes all mappings from $\\mathcal{X} \\hookrightarrow \\mathcal{Y}$, i.e., there is no structural assumption to the translation whatsoever. In this case, our bounds are vacuous. However, if the ideal translator is assumed to have a bounded number of parameters, then the error bounds are meaningful when the amount of source data exceeds the number of translator parameters $|\\Theta|$. For further intuition, consider any fixed translator with high error rate. Then a $1-\\alpha$ fraction of its mistranslations will be implausible. These implausible translations will rule out a constant fraction of translators. \n\nAs you noticed, the intuition in line 717 is incorrect, the $\\lesssim$ and $\\gtrsim$ have accidentally been swapped! So it should indeed be $A \\wedge \\neg B$ is unlikely. In the proof itself (line 747) we have them in the correct direction.\n\n> I would also suggest the authors to include some experiments...\n\nDone! See the pdf attached to our overall response.\n\n> I think there needs to be more justification for how the instantiations are related to real world scenarios...\n\nDefinition 3.1, the Knowledge Graph, corresponds to an abstraction of the natural phenomenon of language composition. Real-world constraints arise due to the laws of nature that are common to humans and fish. Consider the fact that certain translations such as \"The salmon ate the shark\" are implausible while \"The shark ate the salmon\" is plausible (here the nodes correspond to different fish). Definition 3.1 captures binary relations such as this, and it only requires that the two graphs are correlated rather than fully aggree.\n\n> list assumptions more explicitly and clearly...\n\nThe two assumptions underlying all our models, are:\n\n1. There exists a hypothetical translator from the animal to human language (a hypothetical \"mermaid\") that does not have a prohibitively large number of parameters.\n\nFor assumption 1, neural networks have proven useful for translation, e.g., between (human) languages, images and natural languages, speech and text, etc. It seems plausible that they could translate animal communication, or at least as well as a hypothetical mermaid could. As discussed in the submission, translators often require fewer parameters than the underlying LMs. Because human language is compositional, it is possible to translate the sentence \"The tuna ate the mackerel\" to French by knowing the meanings of tuna, mackerel and ate and their French equivalents (and grammar). In contrast, we have learned from GPTs that LMs can spit out encyclopedic articles about tuna and mackerel fish. Our knowledge graphs model this: e.g., for a “food web,” the nodes correspond to fish and the edges correspond to which fish eat which other fish. In some sense, the crux of the low-complexity translator assumption is that the source animal language is also compositional, deriving their meaning from the meaning of smaller units composed together.\n\n2. There is common ground between the languages, e.g., there are certain things that are implausible in both languages.\n\nFor assumption 2, LMs embed many properties of nature. If an animal language is sufficiently rich, it should also embed similar real-world knowledge. The common ground includes knowledge that \"the shark ate the salmon\" is more likely than \"the salmon ate the shark\". \n\n> Describe the meaning of the broader prior and agreement...\n\nThe broad prior is over reasonable translations that we might see. Of course, one wouldn't be surprised to see translations of whale utterances to be \"Let's dive and eat some squid.\" On the other hand, one would be shocked to learn that whales use smartphones, and many of their conversations are about these communications. See additional discussion in Appendix G.\n\nAgreement is easily illustrated in the food web example from before. Another way to think about it is, if we used a language model trained on animal communication to output detailed articles about all the fish, how many facts would be in common between that and the corresponding human-written (e.g., Wikipedia) articles.  That is what we refer to as agreement. Note that we do not require perfect agreement, as illustrated by the agreement parameter in our Knowledge Graph model and experiments.\n\n> they rarely provide explanations for the symbols or the formulas either... the symbols in Section 3.1 have different meanings than the ones in Section 3.2.\n\nOur two models are different but use related notation. We chose to use the similar symbols to capture the same concept in the two sections, but we understand that this can be confusing.  We will add tables of symbols to clarify their meanings.\n\n> In my opinion, this paper’s assumption about the existence of a set of plausible translations is very realistic and insightful for understanding the mechanism of unsupervised translation. As far as I know, attributing the success of unsupervised translation to this characteristic is novel and I think it is convincing (though may not be a complete explanation).\n\n> The knowledge graph model is inspiring to me. I think it suggests that the success of unsupervised translation is because of the interaction between some high-level structure and some low-level structure of language. In this model, the high-level structure is the plausibility of the combination of nodes, while the low-level structure is the one-to-one mapping of the nodes.\n\nThank you for these positive remarks. Considering that our rebuttal clarifies and fixes the main technical issue you (astutely) observed, and our additional experiments, we humbly ask that you consider increasing your score."}]

Author rebuttal:
# Overall Response

**BREAKING NEWS**: We have added experiments as requested by all reviewers. These synthetic experiments validate the theoretical findings and help illustrate the main message, that more complex languages can be translated with lower error. The focus of these experiments, like our paper, is on understanding how the error rate relates to the amount of data and language complexity, which may be useful for the scientists collecting data on animal communication. Additionally, we hope these experiments will help provide further intuition about our results.

Our experiments correspond to the two main theorems, 3.2 and 3.4. The results are in the attached pdf. We now describe in the experiments in detail, which are faithful brute-force implementations of the algorithms described in the paper.

**Common Nonsense model:** Since in this model the structure of sentences is arbitrary, we represent sentences by integer ids, $[10^5]=\{1,2,\ldots, 10^5\}$ and $[10^6]$ for the target language. We generate a prior $\rho$ from the common nonsense model by taking the target sentence ids $[10^6]$ and labeling a random $\alpha$-fraction of them as nonsense; the remaining sentences are called sensical $S$. Given a ground-truth translator $f_\star \colon [10^5] \to [10^6]$, the source language then distributes uniformly over the back-translation of sensical sentences, $f_\star^{-1}(S)$.

The translator family $\lbrace f_\theta | \theta \in \Theta\rbrace$ is taken to be a set of $10^5$ random one-to-one translators, of which one is secretely chosen to be ground-truth $f_\star$. We then train an MLE algorithm on random samples from the source language: Each sample $x\sim \mu$ rules-out a subset of translators, namely, all $\theta \in \Theta$ such that $f_\theta(x) \notin S$, i.e., is nonsensical.

Our experiments (Figure 1) show that as the number of samples increases, the average error over the plausible translators (that have not been ruled-out) decreases.

To show how language complexity / common ground affect translatability, we ablate the parameter $\alpha$ which determines the fraction of common nonsense. Our experiments validate the intuition that increased common nonsense results in lower translation error.

The error of a translator is computed as the fraction of disagreements with the ground-truth on a hold-out validation set of size 1000. The values with which the model is instantiated are:
| Name                        | Symbol   | Value(s)        |
|-----------------------------|----------|-----------------|
| Num source sentences        | $\|T\|$  | $10^5$          |
| Num target sentences        | $\|P\|$  | $10^6$          |
| Num training data           | $m$      | 1,...,100       |
| Num validation data         |          | 1000            |
| Fraction of common nonsense | $\alpha$ | 0,0.1,...,0.8   |

The experiments were run in parallel on an AWS r6i.4xlarge for a total of four CPU-hours.

**Knowledge Graph model:** Recall that in the knowledge graph model, text describes relations between nodes in a directed graph. Due to computational constraints, we consider ten nodes, each corresponding to a different word in the target language. To generate edges corresponding to the target language $P$, two nodes are connected with a directed edge independently, with probability $0.5$. We then consider source languages with $r \leq 10$ words. Given a ground-truth translator $f_\star \colon [r] \to [10]$, the source language graph $T$ is obtained by choosing a random subset of nodes $S$ of size $r$, taking the pre-image of graph induced on $S$ under $f_\star$, and (3) adding noise by redrawing each edge with probability $1-\alpha$ for a fixed _agreement coefficient_ $\alpha \in (0,1)$.

The prior $\rho$ is derived from the edges of $P$, and the source language $\mu$ is derived from the (noisy) permuted subgraph $T$. We consider the translator family $\lbrace f_\theta | \theta \in \Theta\rbrace$ of all node-to-node (word-to-word) injective translators, of which one is secretely chosen to be ground-truth. Similarly to the previous setting, we train an MLE algorithm on randomly chosen edges from $T$, which correspond to sentences in the source language. For each sampled edge $(x_1, x_2)$, we increase the "score" of each translator that agrees with the edge, that is, that $(f_\theta(x_1), f_\theta(x_2))$ is an edge in the graph $P$.

Our experiments (Figures 2 and 3) show that as the number of samples increases, the error of the top-scoring translator decreases.

To show how common ground affects translatability, we ablate the parameter $\alpha$ determines the fraction of edges on which the source language graph $T$ and the target language graph $P$ agree. Our experiments (Figure 2) validate the intuition that increased agreement results in lower translation error.

To show how language complexity affects translatability, we ablate $r$, which is the size of the subraph corresponding to the source language. Our experiments (Figure 3) validate the intuition that a larger subgraph results in lower translation error.

The error of a translator is computed as the fraction of edges whose labels are different than the ground-truth. The values with which the model is instantiated are:
| Name                        | Symbol   | Value(s)        |
|-----------------------------|----------|-----------------|
| Num source words        | r  | $1,4,7,10$          |
| Num target words        | $\|P\|$  | $10$          |
| Num training data           | $m$      | 1,2,..., up to all edges       |
| Edge density         |    p      | 0.5            |
| Agreement | $\alpha$ | $0, 0.33, 0.66, 1$ |

Note: We do not consider the product of all three ablations: Rather, for ablations on $r$ we take $\alpha=0.5$, and for ablations on $\alpha$ we take $r=9$.
The experiments were run in parallel on an AWS r6i.4xlarge for a total of three CPU-hours.

Meta-review: There has been a lot of debate about this paper in the reviewing process, and I believe the authors have defended relatively well the utility of their work as a formal model to show unsupervised translation is possible between pairs of languages under certain constraints and assumptions. While the excitement and reviews of the paper are somewhat mixed, it has some strong support.

I would be wary of making the connection to animal communication so explicit and visibly highlighted. As far as I can see, there is not much discussion in the paper of research about animal communication, and it serves as a highly informal (but perhaps catchy) inspiration.

I hope that the extra space, if the PCs eventually accept the paper, will be used for the synthetic experiments provided in the author's response, coupled with an intuition of how they support the formal model.

minor type in abstract: "sylized" should be "stylized?"
Decision: Accept (poster)