Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
Authors: Daniel Keysers
Nathanael Schärli
Nathan Scales
Hylke Buisman
Daniel Furrer
Sergii Kashubin
Nikola Momchev
Danila Sinopalnikov
Lukasz Stafiniak
Tibor Tihon
Dmitry Tsarkov
Xiao Wang
Marc van Zee
Olivier Bousquet
Venue:  (2020)
Keywords: compositionality
generalization
natural language understanding
benchmark
compositional generalization
compositional modeling
semantic parsing
generalization measurement

Abstract: State-of-the-art machine learning methods exhibit limited compositional generalization. At the same time, there is a lack of realistic benchmarks that comprehensively measure this ability, which makes it challenging to find and evaluate improvements. We introduce a novel method to systematically construct such benchmarks by maximizing compound divergence while guaranteeing a small atom divergence between train and test sets, and we quantitatively compare this method to other approaches for creating compositional generalization benchmarks. We present a large and realistic natural language question answering dataset that is constructed according to this method, and we use it to analyze the compositional generalization ability of three machine learning architectures. We find that they fail to generalize compositionally and that there is a surprisingly strong negative correlation between compound divergence and accuracy. We also demonstrate how our method can be used to create new compositionality benchmarks on top of the existing SCAN dataset, which confirms these findings.


Published as a conference paper at ICLR 2020
MEASURING COMPOSITIONAL GENERALIZATION: A COMPREHENSIVE METHOD ON REALISTIC DATA
Daniel Keysers, Nathanael Schärli, Nathan Scales, Hylke Buisman, Daniel Furrer, Sergii Kashubin, Nikola Momchev, Danila Sinopalnikov, Lukasz Stafiniak, Tibor Tihon, Dmitry Tsarkov, Xiao Wang, Mare van Zee & Olivier Bousquet Google Research, Brain Team
(keysers, schaerli, nkscales, hylke, daniel furrer, sergik, nikola, s lukstafi, ttihont tsar, wangx ao, ma marcvanzes, obousquet) 8googl e. com
ABSTRACT
State-of-the-art machine learning methods exhibit limited compositional general- ization. At the same time, there is a lack of realistic benchmarks that comprehen- sively measure this ability, which makes it challenging to find and evaluate im- provements. We introduce novel method to systematically construct such bench- marks by maximizing compound divergence while guaranteeing a small atom di- vergence between train and test sets, and we quantitatively compare this method to other approaches for creating compositional generalization benchmarks. We present a large and realistic natural language question answering dataset that is constructed according to this method, and we use it to analyze the compositional generalization ability of three machine learning architectures. We find that they fail to generalize compositionally and that there is a surprisingly strong nega- tive correlation between compound divergence and accuracy. We also demonstrate how our method can be used to create new compositionality benchmarks on top of the existing SCAN dataset, which confirms these findings.
INTRODUCTION
Human intelligence exhibits systematic compositionality (Fodor & Pylyshyn, 1988), the capacity to understand and produce a potentially infinite number of novel combinations of known components, i.e, to make "infinite use of finite means" (Chomsky) 1965). In the context of learning from a set of training examples, we can observe compositionality as compositional generalization, which we take to mean the ability to systematically generalize to composed test examples of a certain distribution after being exposed to the necessary components during training on a different distribution.
Humans demonstrate this ability in many different domains, such as natural language understanding (NLU) and visual scene understanding. For example, we can learn the meaning of new word and then apply it to other language contexts. As Lake & Baroni (018) put it: "Once a person learns the meaning of new verb 'dax', he or she can immediately understand the meaning of 'dax twice' and "sing and dax'." "" Similarly, we can learn new object shape and then understand its compositions with previously learned colors or materials (Johnson et al. 2017 Higgins et al. 2018).
In contrast, state-of-the-art machine learning (ML) methods often fail to capture the compositional structure that is underlying the problem domain and thus fail to generalize compositionally (Lake & Baroni 2018 Bastings et al. 2018; Loula et al. 2018 Russin et al. 2019 Johnson al., 2017). We believe that part of the reason for this shortcoming is a lack of realistic benchmarks that comprehen- sively measure this aspect of learning in realistic scenarios.
As others have proposed, compositional generalization can be assessed using a train-test split based on observable properties of the examples that intuitively correlate with their underlying composi- tional structure. Finegan-Dollaa Doolak et al. (2018), for example, propose to test on different output pat- terns than are in the train set, while Lake & Baroni (2018) propose, among others, to split examples by output length or to test on examples containing primitives that are rarely shown during training. In this paper, we formalize and generalize this intuition and make these contributions:
We introduce distribution-bar based compositionality assessment (DBCA), which is a novel method to quantitatively assess the adequacy of particular dataset split for measuring compositional generalization and to construct splits that are ideally suited for this purpose (Section 2

---

Published as a conference paper at ICLR 2020
We present the Compositional Freebase Questions (CFQ simple yet realistic and large NLU dataset that is specifically designed to measure compositional generalization using the DBCA method, and we describe how to construct such a dataset (Section B)
We the DBCA method to construct series of experiments for measuring composi- tionality on CFQ and SCAN Laaee & Baroni 2018) and to quantitatively compare these experiments to other compositionality experiments (Section
We analyze the performance of three baseline MI. architectures on these experiments and show that these architectures fail to generalize compositionally, and perhaps more surpris- ingly, that compound divergence between train and test sets is a good predictor of the test accuracy (Section
2 DISTRIBUTION DIRRBBUTION-BAEED COMPOSITIONALITY ASSESSMENT (DBCA)
Like other authors, we propose to measure a learner's ability to generalize compositionally by using setup where the train and test sets come from different distributions. More specifically, we propose a setup where each example is obtained by composing primitive elements (atoms), and where these atoms are similarly represented in the train and test sets while the test set contains novel compounds, i.e., new ways of composing the atoms of the train set.
As a simple illustrative scenario, consider the task of answering simple questions such as "Who directed Inception?" and "Did Christopher Nolan produce Goldfinger?". In this scenario, the atoms intuitively correspond to the primitive elements that are used compose those questions. such as the predicates "direct(ed)" and "produce(d)), the question patterns "Who [predicate] [entity]" and "Did [entity1] [predicate] [entity2]", and the entities "Inception". "Christopher Nolan", etc. The compounds on the other hand correspond to the combinations of these atoms that appear in the various examples: "Who directed [entity]?", "Did Christopher Nolan [predicate] Inception?", etc.
To measure compositional generalization on such task, one might therefore use the questions "Who directed Inception?" and "Did Christopher Nolan produce Goldfinger?" as training examples while testing questions such "Did Christopher Nolan direct Goldfinger?" and "Who produced Incep- tion?" because the atoms are identically represented in the train and test sets while the compounds differ.
To make this intuition more precise, we focus on datasets such as CFQ (introduced in Section 3) and SCAN (Lake & Baroni 2018), where each example be created from formal set of rules by successively applying a number of these rules. In this case, the atoms are the individual rules, while the compounds are the subgraphs of the directed acyclic graphs (DAGs) that correspond the rule applications. (See Sections 3 and for more details.)
2.1 PRINCIPLES FOR MEASURING COMPOSITIONALITY
We use the term compositionality experiment to mean a particular way of splitting the data into train and test sets with the goal of measuring compositional generalization. Based on the notions of atoms and compounds described above, we say that an ideal compositionality experiment should adhere to the following two principles:
1. Similar atom distribution: All atoms present in the test set are also present in the train set, and the distribution of atoms in the train set is as similar as possible their distribution in the test set.
2. Different compound distribution: The distribution of compounds in the train set is as differ- ent as possible from the distribution in the test set.
The second principle guarantees that the experiment is compositionally challenging in the sense that it tests the leamner on compounds that are as different as possible from the compounds used during training. The first principle aims to guarantee that the experiment is exclusively measuring the effect of the difference in the way atoms are composed to form compounds (rather than some related but different property such as domain adaptation on the distribution of the atoms).
To determine to which degree a certain experiment adheres to these principles, formalization. For a sample set T, we use Fx(T) to denote the frequency distribution of atoms
the following
Available at http:///wmccoooooooeoeeeeooeoeee
2

---

Published as a conference paper at ICLR 2020
in T and (T) for the weighted frequency distribution of compounds in T, which correspond to the subgraphs of the rule application DAGs. For practicality, we do not consider all subgraphs of rule application DAGs when computing the compound divergence. Instead, we first generate large subset G of subgraphs, then weight them in context of their occurrence, and keep only the ones with highest sum of weights. The purpose of the weighting is avoid double-counting compounds that are highly correlated with some of their super-compounds. We achieve this by calculating the weight of G G in a sample as w(G)
maXgewee(G) (1 maXG'sg =aX "g"Exc<("")) P(G'(G)), where (Cc(G) is the of all occurrences of G in the sample, denotes the strict subgraph relation, and P(G'IG) is the empirical probability of G' occurring as a supergraph of G over the full sample set. See Appendix I..4 for example subgraphs and more details on the weighting.
We measure divergence (or similarity) of the weighted distributions using the Chernoff coefficient [0. 1] (Chung al. 1989). For the atom divergence, we use a 0.5, which corresponds to the Bhattacharyya coefficient and reflects the desire of making the atom distributions in train and test as similar as possible. For the compound divergence, we use a 0.1, which reflects the intuition that it is more important whether certain compound occurs in P (train) and Q (test) match exactly. This allows us to formally define as follows the notions of compound divergence Dc and atom divergence DA of compositionality experiment consisting of a train set V and a test set W:
C, (PII)) Ex PI 9s
P (train) than whether the probabilities
Dc(V][W) = C..1 || (W)) DA(VIWW) = (F.((Fa(V) FA(W))
Based on these principles, we suggest use as preferred compositionality benchmark for given dataset the accuracy obtained by learner on splits with maximum compound divergence and low atom divergence (we use D S 0.02). See Section forr details about how to construct such splits.
THE CFQ DATASET
We present the Compositional Freebase Questions (CFQ) example of how to construct da- taset that is specifically designed to measure compositional generalization using the DBCA method introduced above. CFQ is simple yet realistic, large dataset of natural language questions and answers that also provides for each question a corresponding SPARQL query against the Freebase knowledge base (Bollacker et al.] 2008). This means that CFQ can be used for semantic parsing (Be-
rant et al. 2013 Yao & Van Durme 2014), which is the task that we focus on in this paper.
3.1 AUTOMATIC, RULE-BASED GENERATION
Saxton al. 2019) describe number of benefits for automated rule-based dataset generation, in- cluding scalability, control of scope, and avoidance of human errors. Beyond these benefits, however, such an approach is particularly attractive in the context of measuring compositional generalization using the DBCA method, as it allows us to precisely track the atoms (rules) and compounds (rule applications) of each example by recording the sequence of rule applications used to generate it.
Since the way we measure compositionality depends on how the examples can be broken down into atoms and compounds, we design the generation rules so as to have few and meaningful atoms. More precisely, aim to have few rules as possible so that the richness of the examples comes from composing them, which yields a large variety of compounds (enabling a large range of different compound divergences) while making it easy to obtain similar distributions of atoms. Also, we aim to make our rules truly "atomic" in the sense that the behavior of any rule is independent of the context where it is applied (e.g., rules may not contain "if-then-else" constructs).
In order to minimize the number of rules, we use an intermediate logical form that serves as a uniform semantic representation with relatively direct mappings natural language and SPAROL. Our rules thus fall into the following four categories (a selection of rules is provided in Appendix M):
1. Grammar rules that generate natural language constructs and corresponding logical forms.
2. Inference rules that describe transformations on logical forms, allowing to factor out transformations that are independent of specific linguistic and SPARQL constructs.
3. Resolution ruley that map constructs of the logical form to SPARQI constructs.
3

---

Published as a conference paper at ICLR 2020
Natural Language: 10h: dt-eected Elystum
Person Stolefair(uareete Parectew)) Elyssum)
Resokaton
SPAROL: SELECT DISTIMET 7x0 WHRE
Mineooo Ralls
7e8 nerrile: dinector file 9.0gmmy
Figure 1: Generating a natural language question together with its SPARQL query using four types of rules. One (of potentially many) intermediate logical forms is also shown.
4. Knowledge rules that supply logical form expressions that are universally applicable. Other rules can be kept more generic by parameterizing them on knowledge.
These rules define language of triples of the form (question, logical form, SPAROL query). Our generation algorithm produces such triples in a mixed top-down and bottom-up fashion. We first ap- ply grammar rules and inference rules to produce the natural language questions and their semantics in our logical form. Then we apply resolution rules to obtain the SPARQL query. See Figure [ for an illustration. addition, the generator produces a normalized, directed acyclic graph (DAG) of rule applications that corresponds to the normalized program that generated the triple. (Appendix D shows an example.) Edges this DAG represent dependencies among the rule applications, and the normalization ensures that a certain rule combination is represented using the same DAG across all the examples where it occurs.
The described approach can generate potentially infinite set of questions, from which we first sample randomly and then subsample (to maximize the overall diversity of rule combinations while keeping uniform distribution over complexity). We measure the diversity of rule combinations using the empirical entropy of a weighted subset of the rule application DAGs, and we use the num- ber of rule upplications example complexity such that the questions remain relatively natural. Table I shows examples of generated questions at varying levels of complexity. An example of complete data item is shown in Appendix A a more detailed data quality analysis is presented in Appendix B. and the generation algorithm is discussed in more detail in Appendix K
measure of the complexity of example. We also limit the maximum
3.2 DATASET DETAILS AND STATISTICS
Input and output. While the primary focus of the dataset is semantic parsing (natural language question to SPARQL query), we also provide natural language answers for each question. This allows the dataset to be used in a text-in-text-out scenario as well (see Appendix A).
Ambiguity. We largely avoid ambiguity in the questions. In particular, we make sure each name is used refer to exactly one entity, and we avoid different possible parse trees, different interpreta- tions of plurals, and the need for disambiguation that requires semantic knowledge.
Scope. We select the following language features as compositional building blocks: open ques- tions and closed questions; subordinate clauses; active and passive voice; conjunctions of verb phrases and of noun phrases; possessives with roles ("X's parent"); adjectives: and type restrictions. For knowledge base features, we select roles, verbs, types, and adjectives from domains that are well-represented in Freebase and that can be combined easily. We start from the popular movie do-
Table I: Examples of generated questions at varying levels (L) of complexity.
Question + Answer
What did [Commerzbank] acquire? >> Eurohypo: Dresdner Bank
15 Did [Dianna Rhodes]'s spouse produce [Soldier Blue]? + No
20 Which costume designer of [E. married [Mannequin]'s cinematographer? + Deborah Lynn Scott
30 Who was inffuenced by and influeneed [Steve Vail, [Marx Brothers), (Woody Allen), and [Steve Martin] |? Brendon Small
40 Was [Weekend Cowgirls] produced, directed, and written by film editor that [The Evergreen State Col- lege] and [Fairway Pictures] employed? r> No
50 Were [It's Not About the Shawerma], [The Fifth Wall], [Rick's Canoe], [White Stork Is Coming]. and [Blues for the Avatar] executive produced, edited, directed, and written screenwriter's parent? Yes
4

---

Published as a conference paper at ICLR 2020
Table 2: (a) CFQ dataset statistics. (b) CFQ complexity statistics in comparison to other semantic parsing datasets. Datasets in the first section map text to SQL for various DBs, with numbers as reported by Finegan-Dollak et al. (2018). Datasets in the second section map text SPARQL for Freebase. The number of query patterns is determined by anonymizing entities and properties.
(a)
(b)
Query
CFQ Dataset Statistics
Value
Dataset
Questions
Queries
patterns
Unique questions
239.357
Academic
196
185
92
Question putterns (mod entities)
239.357
Advising
4,570
211
174
Question patterns (mod entities, verbs, etc.)
49,320
AMDB
131
89
52
Unique queries
228,149
ATIS
5,280
947
751
Query patterns (mod entities)
123,262
GeoQuery
877
246
98
Query patterns (mod entities and properties)
34,921
Restaurants
378
2.3
17
Open questions
108,786
Scholar
817
193
146
Clused questions (with answer "yess")
65,092
WikiSQL
80,654
77,840
488
Clused questions (with answer "no")
65,479
Yelp
128
110
89
WebQuestionsSP
4,737
3,750
240
Complex WebQuesinns
34,689
27.875
2,474
CFQ (this work)
239,357
228,149
34,921
main (e.g., directing, producing, editor, sequel) and extend this with personal relations (e.g.. parent, spouse, sibling), companies (c.g., founding, employer), and adjectives (e.g., gender, nationality).
Logical form and grammar. For the internal logical form, adopt a variation of the description logic EL (Baader et al., 2003 2005), augmented with additional constructors (see Appendix M to more easily map to certain linguistic structures. For the grammar rules,
unification- based grammar syntax similar to that used in the Prolog extension GULP 3.1 (Covington) 1994), with addition of support for disjunction, negation, absence, and default inheritance of features for compactness of representation.
Grounding in Freebase. Once example is generated by the CFQ rules, still contains entity placeholders instead of Freebase machine ids (MIDs). For the task of semantic parsing, the examples could theoretically be used as-is, as our avoidance of semantic ambiguity means that learner should not need knowledge of the specific entity in order to parse the question. To make the questions natural, however, we apply an additional step of replacing the placeholders with appropriate specific entities. To do this we first execute the generated SPARQL. query against Freebase. This returns set of candidate MID combinations that satisfy the query and can be used as substitutes. If the set is empty, we abandon the generated question candidate as unnatural. Otherwise, we pick one combination at random to yield a question with positive answer. the case of a closed question, we also generate variation that yields the answer "No", which we do by mixing in MIDs from another substitution (or a more generic replacement if that fails) to keep the question as Mausible-soundde possible. We then randomly choose either the question with positive with negative answer, to avoid spurious correlations between question structure and yes/no answer.
Semantic and structural filtering. Even among the questions that be satisfied in Freebase, there are some that are meaningful but somewhat unnatural, such as "Was Strange Days directed by female person whose gender is female?". We automatically filter such unnatural questions using semantic and structural rules. Note that since we do not require a learner to identify such questions, we do not track these filtering rules.
Release and statistics. CFQ contains 239,357 English question-answer pairs that are answerable using the public Freebase data. (The data URL is not yet provided for anonymous review.) We include list of MIDs such that their English names map unambiguously to a MID. Table sum- marizes the overall statistics of CFQ. Table ( uses numbers from (Finegan-Dolle et al., 2018) and from an analysis of WebQuestionsSP (Yih et al. (016) and Complex WebQuestions (Talmor & Berant 2018) to compare three key statisties of CFQ to other semantic parsing datasets (none of which provide annotations of their compositional structure). CFQ contains the most query patterns by an order magnitude and also contains significantly more queries and questions than the other datasets. Note that it would be easy to boost the number of questions in CFQ almost arbitrarily by repeating the same question pattern with varying entities, but we use at most one entity substitu- tion per question pattern. Appendix Centtains more detailed analyses of the data distribution.
5

---

Published as a conference paper at ICLR 2020
Table 3: Comparison of relevant measurements for different split methods CFQ SCAN.
D
De
Output
Input
Oulpul
Input
Atom
Compound Divergence
Pattern Coverage
Pattern Coverage
Length
Length
Split Method
Divergence
Ratio
Ratio
Random
0.000
0.000
0.726
0.705
1.007
1.003
Output Length
0.033
0.176
0,000
0.004
0,486
0,648
CFQ
Input Length
0.047
0.062
0.285
0.047
0.584
0.578
Output Pattern
0.000
0.008
0,000
0.516
0.977
0.984
Input Pattern
0.000
0.005
0.636
0.000
1.028
1.017
MCD1
0.020
0.694
0.079
0.032
0.732
0.871
MCD2
0.020
0.713
0.023
0.007
0.838
0.958
MCD,
0.020
0.704
0,034
0.027
0.807
0.896
Random
0.000
0.047
1.000
1.000
0.998
0.994
Output Length
0.034
0.437
0.000
1.000
0,367
0.856
SCAN
Input Length
0.106
0.380
0.278
0.000
0.501
0.771
Output Pattern
0.003
0.221
0,000
0.967
1.081
0.989
Input Pattern
0.005
0,240
0,951
0.000
0.993
0.967
MCD1
0.015
0.736
0.260
0.357
0.698
0.926
MCD
0.020
0.734
0.259
0.010
0.757
0.837
MCD,
0.014
0.735
0.318
0.009
0.632
0.938
4 COMPOSITIONALITY EXPERIMENTS FOR CFQ AND SCAN
The DBCA principles described in Section 2.1 enable a generic and task-independent method for constructing compositionality experiments. To construct such an experiment for dataset U and desired combination of atom and compound divergences, we use an iterative greedy algorithm that starts with empty sets V (train) and W (test), and then alternates between adding an example u E U to V or W (while maintaining the desired train/test ratio). At each iteration, the element is selected such that WV) and D PA(E ([W) are kept as closely as possible the desired values. To reduce the risk of being stuck in a local optimum, we also allow removing examples at certain iterations.
In general, there are many different splits that satisfy a desired compound and atom divergence. This reflects the fact that a certain compound may either occur exclusively in the train set or the test set, or may occur in both of them because the split may have achieved the desired compound divergence by separating other (possibly orthogonal) compounds. Our greedy algorithm addresses this by making random choices along the way, starting with picking the first example randomly.
For the goal of measuring compositional generalization as accurately as possible, it is particularly interesting to construct maximum compound divergence (MCD) splits, which aim for a maximum compound divergence at a low atom divergence (we D < 0.02). Table 3 compares the com- pound divergence Dc and atom divergence D of three MCD splits to a random split baseline as well as several previously suggested compositionality experiments for both CFQ and the existing SCAN dataset (cf. Section 5.3). The split methods (beyond random split) are the following:
Output length: Variation of the setup described by Lake & Baroni (2018) where the train set consists of examples with output (SPARQL query or action sequence) length <,,, while the test set consists of examples with output length >. For CFQ, we use N constraints. For SCAN, we use N = 22 actions.
Input length: Variation the above setup, which the train set consists of examples with input (question or command) length < N, while test set consists of examples with input length > N. For CFQ, we use N 19 grammar leaves. For SCAN, we use N = tokens.
Output pattern: Variation of setup described by Finegan-Dollak et al. (0018). in which the split is based on randomly assigning clusters of examples sharing the same output (query or action sequence) pattern. Query patterns are determined by anonymizing entities and properties; action sequence patterns collapse primitive actions and directions.
Input pattern: Variation of the previous setup in which the split is based on randomly as- signing clusters of examples sharing the same input (question command) pattern. Ques- tion patterns are determined by anonymizing entity and property names; command patterns collapse verbs and the interchangeable pairs left/right, around/opposite, twice/thrice.

---

Published as a conference paper at ICLR 2020
All of these experiments based the same train and validation/test sizes of 40% and 10% of the whole set, respectively. For CFQ, this corresponds to about 96k train and 12k validation and test examples, whereas for SCAN, it corresponds to about 8k train and Ik validation and test examples. We chose to use half of the full dataset for the train-test splits, as it led to an appropriate balance between high compound divergence and high train set size in informal experiments.
The MCD splits achieve a significantly higher compound divergence at a similar atom divergence when compared to the other experiments. The reason for this is that, instead of focusing on only one intuitive but rather arbitrary aspect of compositional generalization, the MCD splits aim to optimize divergence across all compounds directly.
Interestingly, the MCD splits still correlate with the aspects of compositional generalization that are targeted by the other experiments in this table. As shown in the four right columns of Table for each MCD split, the train set V contains on average shorter examples than the test set W (measured by the ratio of average lengths), and V also contains only a small fraction of the input and output patterns used in W (measured by the fraction of patterns covered). However, these correlations are less pronounced than for the experiments that specifically target these aspects, and they vary significantly across the different MCD splits.
This illustrates that MCD splits are comprehensive the sense that they cover many different aspects of compositional generalization, especially when looking at multiple of them. It also means that whether a certain example ends up in train or test is not determined solely by a single criterion that is immediately observable when looking at the input and output (such as length). As we show in Appendix D.I this generally makes the examples in train and test look fairly similar.
5
EXPERIMENTAL RESULTS AND ANALYSIS
5.1 EXPERIMENT SETUP
We use three encoder-decoder neural architectures as baselines: (1) LSTM as an LSTM (Hochreiter & Schmidhuber 1997) with attention mechanism (Bahdanau et al., 2015); (2) Trans- former (Vaswani et al. (017) and (3) Universal Transformer (Dehghani et al. 2018).
We tune the hyperparameters using a CFQ random split, and we keep the hyperparameters fixed for both CFQ and SCAN (listed in Appendix Eb. In particular the number of training steps is kept constant to remove this factor of variation. We train a fresh model for each experiment, and we replicate each experiment times and report the resulting mean accuracy with 95% confidence intervals.
Note that while we construct test and validation sets from the same distribution, we suggest that hyperparameter tuning should be done on random split (or random subset of the train set) if one wants to measure compositional generalization of a model with respect to an unknown test distribu- tion opposed to architecture with respect set that has the same distribution as the test set would amount to optimizing for a particular type of compound divergence and thus measure the ability for a particular architecture to yield models that can be made to generalize in one particular way (through leaking information about the test set in the hyperparameters).
known test distribution. Tuning
a validation
Similarly to Finegan-Doilak et al. (2018), we anonymize the Freebase names and MIDs in the textual input and the SPARQL output, respectively, by replacing them with a placeholder (e.g., "MO" for the first MID). This removes the need for two learning sub-tasks that are orthogonal to our focus: named entity recognition and learning that the MIDs are patterns that need to be copied. An example onput-output (question-query) pair then looks like the following: 'Was MO a screenwriter' + 'select count(*) where (MO a fi:film. ns:film.writerr..
The main relation we are interested in is the one between compound divergence of the data split and accuracy, Specifically, we compute the accuracy of each model configuration on a series of divergence- splits that we produce with target compound divergences that span the range be- tween zero and the maximum achievable in 0.1 increments (while ensuring that atom divergence does not exceed the value of 0.02). For each target divergence, produce at least 3 different splits with different randomization parameters (compare Section 4p. For comparison, we also compute accuracies on the other splits shown in Table
7

---

Published as a conference paper at ICLR 2020
1.0
Ra idom
1,0
Imput Partern
Turakret
Randont
0.8
Input length
Qutput patters
lspur pattern
Actuary
0.4
3.4
Inpur length
guh
0.2
222
00
30
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
(a)
Compondd
(b)
compound direngence
Figure 2: Accuracies of the three baseline systems on (a) CFQ and (b) SCAN vs. compound diver- gence for different split methods and for different target compound divergences.
Table 4: Mean accuracies of the three bascline systems CFQ and SCAN (in %).
Dataset
CFQ
SCAN
Split Method
Random
MCD
Random
MCD
LSTMtattnntion
97.4 +0.3
14.9 +1.1
99.9 +2.7
6.1 #2.2
Transformer
98.5 =0.2
17.9 +0,9
100.0 +0.0
1.1 +0.5
Universal Transformer
10.3
18.9 11.4
99.9 10.2
1.2 10.7
5.2 RESULTS AND ANALYSIS FOR CFQ
The mean accuracies of the three architectures on CFQ are shown in Figure 2[a) and Table We make three main observations:
All models achieve an accuracy larger than 95% on random split, and this is true even if they are trained on 10 times fewer training instances (see Appendix H for a more detailed analysis on the performance with varying training size).
The mean accuracy on the MCD splits is below 20% for all architectures, which means that even large train set (about 96k instances) with similar distribution of atoms between train and test is not sufficient for these architectures to perform well on the test distribution.
For all architectures, there is a strong negative correlation between the compound diver- gence and the mean accuracy.
This suggests that the baseline models able to capture the superficial structure of the dataset, but fail to capture the compositional structure. We find it surprising that varying the compound divergence gives direct control of the (mean) accuracy, even though the examples in train and test look similar (see Appendix D.I. This means that compound divergence seems to capture the core difficulty for these ML architectures to generalize compositionally.
Note that the experiment based on output-length exhibits a worse accuracy than what we would expect based on its compositional divergence. One explanation for this is that the distribution varies from the training distribution in other ways than compound divergence (namely in output length and a slightly higher atom divergence), which seems make this split particularly difficult for the baseline architectures. To analyze the influence of the length ratio further, we compute the correlation between length ratios and accuracy of the baseline systems and compare to the corre- lation between compound divergence and accuracy. We observe R² correlation coefficients between 0.11 and 0.22 for the input and output length ratios and between 0.81 and 0.88 for the compound divergence. This shows that despite the known phenomenon that the baseline systems struggle to generalize to longer lengths, the compound divergence seems to be a stronger explanation for the accuracy different splits than the lengths ratios.
Error analysis. We perform an analysis of the errors for the split MCD, (the first MCD split that constructed, with more details provided in Appendix F.. We observe accuracies between 29%
8

---

Published as a conference paper at ICLR 2020
and 37% on the test set of this particular split. Qualitatively, all three systems seem make similar errors at this point (68% of errors are on the same samples). They make more errors for longer sequences and predict about 20% too short output when they make error. The most common category of error is the omission of a clause in the output (present in 43%-49% of the test samples), e-g.: (1) Omitted conjunctions: for the input "What spouse of a film producer executive produced and spous edited M0, MI, and M2?" the best system ignores "executive produced" in the output. (2) Omitted adjectives: for the input "Which female Spanish film producer was M3' spouse?" the best system ignores the adjective "female".
5.3 RESULTS AND ANALYSIS FOR SCAN
To demonstrate the use of our analysis method on another dataset, we re-create the SCAN data- set (Lake & Baroni 2018), which consists of compositional navigation commands (e.g, 'turn left twice and jump') ) mapped to corresponding action sequences (e.g., 'LTURN LTURN JUMP"). We use the original grammar while tracking the rule applications used for the construction of each input- output pair. This enables us to compare the compositional generalization abilities of the baseline systems on this dataset in novel way.
Figure bb) shows the graphs for the SCAN data set in the same setup as Figureaja) does for CFQ- We observe that the compound divergence again is good predictor for the mean accuracy for all three architectures. One difference is that for SCAN the systems are able to attain accuracies close to 100% for compound divergences up to around 0.2, which is not the case for CFQ. This seems to be in line with the fact that overall CFQ is more complex task than SCAN: the total number of rules used generating SCAN is only 38 in comparison to 443 rules in the construction of CFQ.
Appendix G provides a comparison to other experiments presented in previous work, including ex- periments that have significantly different atom distributions. We observe that this generally causes lower accuracies but does not break the correlation between accuracy and compound divergence.
6 RELATED WORK
To measure compositional generalization for semantic parsing to SQL., Finegan-Dollate et al. (2018) propose to ensure that no SQL query pattern occurs in both the train and the test set ("query split"), and they provide such splits for several data sets. By evaluating several ML architectures the authors confirm that this guery-pattern split is harder to learn than a conventional split.
Lake & Baroni (0188) introduce the SCAN dataset, and several publications provide interesting anal- yses of compositional generalization using it (Bastings et al.] [2018] Loula et al. 2018). J Russin et al. (2019) discuss particular extension of seq2seq model that is effective in handling difficult SCAN sub-tasks by separating semantic and syntactic information during learning. Our contributions ex- tend the analyses on the SCAN data in several ways: CFQ provides richer annotations and covers broader subset of English than the SCAN dataset, and we propose a comprehensive score for assess- ing aggregate compositionality of system on given task.
The mathematics dataset (Saxton et al. 2019) is a large, automatically generated set of 112M sam- ples in 56 separated sub-tasks. The authors present data and experiments that share common goals with our approach, but focus on mathematical reasoning instead of natural language. Our breakdown of generation rules per train sample more fine- -raineddddd which allows more precise compositional generalization analysis. Being automatically generated also links our approach to datasets such as the bAbl tasks (Weston et al., 2016), which however do not focus on compositional generalization.
A dataset related to CFQ is ComplexWebuuenee WebQuestions (Talmor & Berant, 2018), which consists of complex questions that are automatically generated from simpler sub-questions in WebQuestionsSP (Yih et al. 2016) and then reworded manually. While these datasets can be used for semantic parsing, we did not find them suitable for a thorough compositionality analysis because consistent annota- tion with the compositional structure would be hard to obtain. Other approaches semi-automatic dataset creation also use paraphrasing (Wang et al.) 2015 Su et al. 2016).
Johnson et al. (201)) introduce the generated CLEVR dataset, which shares common goals with our work applied in the area of visual reasoning. The dataset's functional programs capture some of the structural information of the questions and are linked one-to-many to the 423 question patterns

---

Published as a conference paper at ICLR 2020
used. The authors specifically investigate generalization to new combinations of visual attributes in one experiment which uses a particular train-tess split based on the colors used. [Ma et al. (2019)
propose a neural-symbolic architecture and discuss promising results additional specific splits of the CLEVR data, e.g. based on object counts and program depth. Hudson & Manning (2018) describe how the application of compositional attention networks to the CLEVR data leads to structured and data-efficient learning. Hudson & Manning (2019a) present a large, compositional, generated visual question answering data set with functional programs, on which neural state machines achieve good performance (Hudson & Manning, (019b)) The use of specific splits between train and test data also occurs in the context of visual data. E.g. Agrawal al. 2018) propose a greedy split algorithm to pairs dis-
maximize the coverage of test concepts in the train set while keeping question question-type/answw joint and observe performance degradation existing approaches. [Bahdanau et al. (2019) introduce a synthetic visual question answering dataset called SQOOP, which is used to test whether a learner can answer questions about all possible object pairs after being trained on a subset.
While these datasets are very interesting, the additional annotation that provide in CFQ indicating the exact rule trees needed to link input and output makes additional analyses regarding composi- tionality possible. Our analyses go beyond many of the presented discussions (that mostly focus on accuracy regarding particular holdouts) in formalizing an approach that uses the atom and compound divergences measure compositionality.
A number of MI. approaches have been developed for semantic parsing. Miller et al. (2016) propose Key- Key-Value Memory Networks neural network-based architectures that internalize knowledge base into the network - and introduce the WikiMovies dataset. Zhang et al. (2018) develop an end- to-end architecture that can handle noise in questions and learn multi-hop reasoning simultaneously. They introduce the MetaQA benchmark that is based on WikiMovies but uses a set of only 511 question patterns (mod entities) shared between train and test.
With regards to studying compositionality in ML. Battaglia et al. (2018) argue that combinatorial generalization should be top priority achieve human-like abilities. Andreas (2019) discusses measuring the compositionality of a trained representation, e.g. of learned embedding. The author suggests to use a tree reconstruction error that is based on how well the oracle derivation of the input matches the structure that can be derived on the representations. |Higinn et al. (2018) discuss an architecture that enables the learning of compositional concept operators on top of learned visual abstractions. Chang et al. (2019) introduce the compositional recursive learner that "can generalize to more complex problems than the learner has previously encountered".
CONCLUSION AND OUTLOOK
In this paper we presented what is (to the best of our knowledge) the largest and most compre- hensive benchmark for compositional generalization dataset generated via a principled rule-based approach and a new method of splitting the dataset by optimizing the divergence of atom and compound distributions between train and test sets. The performance of three baselines indicates that in a simple but realistic NLU scenario, state-of-the learning systems fail to generalize compositionally even if they are provided with large amounts of training data and that the mean accuracy is strongly correlated with the compound divergence.
realistic NLU task. It is based on new
We hope our work will inspire others use this benchmark as a yardstick to advance the composi- tional generalization capabilities of learning systems and achieve high accuracy at high compound divergence. Some specific directions that we consider promising include applying unsupervised pre- training on the input language output queries and the use of more diverse or more targeted learning architectures, such as syntactic attention (Russin et al., 2019). We also believe would be interest- ing to apply the DBCA approach to other domains such as visual reasoning, e.g. based CLEVR JJohnson et al. 2017).
In the area of compositionality benchmarks, we are interested in determining the performance of current architectures on the end-to-end task that expects a natural language answer given a natural language question in CFQ. We would like also to extend our approach to broader subsets of language understanding, including use of ambiguous constructs, negations, quantification, comparatives, ad- ditional languages, and other vertical domains.
10

---

Published as a conference paper at ICLR 2020
REFERENCES
Aishwarya Agrawal, Dhruv Batra, Devi Parikh, and Aniruddha Kembhavi. Don't just assume: look and answer: Overcoming priors for visual question answering. In CVPR, 2018. URL https:
//rxi..rr//o///112.0377....
Jacob Andreas. Measuring compositionality in representation learning. In ICLR, 2019. URL. https: //ppacrtwew..uuolddllii-llobbbbd
Franz Baader, Diego Calvanese, Deborah McGuinness, Peter Patel-Schneider, and Daniele Nardi.
The description logic handbook: Theory, implementation and applications. Cambridge University Press, 2003.
Franz Baader, Sebastian Brandt, and Carsten Lutz. Pushing the EL envelope. In IJCAI, 2005. URL wwt.://wwwggccaaaoooocdoddd--//a
Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. Neural machine translation by jointly learning to align and translate. In ICLR, 2015. URL http://anxiv.orrabb///44....
Dzmitry Bahdanau, Shikhar Murty, Michael Noukhovitch, Thien Huu Nguyen, Harm de Vries, and Aaron Courville. Systematic generalization: What is required and can it be learned? In ICLR, 2019. URL http://arxiv.orr//////81111..
Joost Bastings, Marco Baroni, Jason Weston, Kyunghyun Cho, and Douwe Kiela. Jump to better conclusions: SCAN both left and right. In BluckboxNLP@EMNN 2018. URL https://www.
aalweb.org/anthology/WW 11-es///885550000 18-5407
Peter Battaglla, Jessica Blake Chandler Hamrick, Victor Bapst, Alvaro Sanchez, Vinicius 7am- baldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, Caglar Gulcehre, Francis Song. Andy Ballard, Justin Gilmer, George E. Dahl, Ashish Vaswani, Kelsey Allen, Charles Nash, Victoria Jayne Langston, Chris Dyer, Nicolas Heess, Daan Wier- stra, Pushmeet Kohli, Matt Botvinick, Oriol Vinyals, Yujia Li, and Razvan Pascanu. Rela- tional inductive biases, deep learning, and graph networks. CoRR, abs/1800.00221,, 2018. URL hutps://rxxiv.org/dtle 806.01 21w.0.12611.. 261..dff
Jonathan Berant, Andrew Chou, Roy Frostig, and Percy Liang, Semantic parsing on Freebase from question-answe pairs. In EMNLP, 2013. URL https//www...wwwwooooo/ttbooosss 1160
Kurt Bollacker, Colin Evans, Praveen Paritosh, Tim Sturge, and Jamie Taylor. Freebase: a collabo- ratively created graph database for structuring human knowledge. In ACM SIGMOD, 2008. URL
Michael Chang, Abhishek Gupta, Sergey Levine, and Thomas L. Griffiths. Automatically com- posing representation transformations means for generalization. In ICLR, 2019. URL.
https://oppuneeiieee////dllleded IfQQnReXX
Noam Chomsky. Aspects of the Theory of Syntax. The MIT Press, Cambridge, 1965.
JK Chung, PL Kannappan, CT Ng, and PK Sahoo. Measures of distance between probability distri- butions. JMAA, 138(1):280-22) 1989. URL http:///ccc.cccuooooooooaa//s/ss
Michael A. Covington. Gulp 3.1: An extension of prolog for unification--based grammar. Research Report A1-1994-06, University of Georgia, 1994. URL httphh/g///ddd.aaaaeeee/////2222
Mostafa Dehghani, Stephan Gouws, Oriol Vinyals, Jakob Uszkoreit, and Lukasz Kaiser. Universal transformers. CoRR, abs//807 000 19, 2018. URL https://arxiiv.rr//////////
Catherine Finegan-Dollak, Jonathan K. Kummerfeld, Li Zhang, Karthik Ramanathan, Sesh Sadasi- vam, Rui Zhang, and Dragomir Radev. Improving text-to-SQL. evaluation methodology. ACI., 2018.
Jerry A Fodor and Zenon W Pylyshyn. Connectionism and cognitive architecture: A crit- ical analysis. Cognition, 28 28(1-2):3-71 1988. URL https://pi..smmmtttsssaarrrrroge fa014bbaahaaayy//6600a0007775515

---

Published as a conference paper at ICLR 2020
Irina Higgins, Nicolas Sonnerat, Loic Matthey, Arka Pal, Christopher P Burgess, Matko Bosnjak, Murray Shanahan, Matthew Botvinick, Demis Hassabis, and Alexander Lerchner. Scan: Learning hierarchical compositional visual concepts. In ICLR, 2018. URL httphtss//ppeeeeeeeee.ehhhhddddd
RK
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 9(8): 1735-1780, 1997.
Drew A. Hudson and Christopher D. Manning. Compositional attention networks for machine rea- soning. In ICLR, 2018. URL httpss//ppeeneeieeev.e/////////" Huww-
Drew A. Hudson and Christopher D. Manning. GQA: A new dataset for real-world visual reasoning and compositional question answering. In CVPR, 2019a. URL https://ari..orrg///////22222399 pdf
Drew A. Hudson and Christopher D. Manning. Learning by abstraction: The neural state machine.
CoRR, abs/1907 1900009993, 2019b. URL hhtpp::/aaaiii.rrgga//a/////
Justin Johnson, Bharath Hariharan, Laurens van der Maaten, Fei-Fei Li, Lawrence C. Zitnick, and Ross Girshick. CLEVR: A diagnostic dataset for compositional language and elementary visual reasoning. In CVPR, 2017. URL
Lauri Karttunen. Features and values. In ACL, 1984. URL httpp:///o..oog110031155///10110
Brenden M. Lake and Marco Baroni. Generalization without systematicity: On the compositional skills of sequence-to-sequene recurrent networks. In ICML, 2018. URL hntps:/aarxi.orr/pdli 1711.00350.pdf
João Loula, Marco Baroni, and Brenden Lake. Rearranging the familiar: Testing compositional gen- cralization in recurrent networks. In BlackboxNLP@ EMNLP, 2018. URL https:/wwww.a/wwch
org/anthology/WII8-55 WI--//118
Jiayuan Mao, Chuang Gan, Pushmeet Kohli, Joshua B Tenenbaum, and Jiajun Wu. The neuro- symbolic concept learner: Interpreting scenes, words, and sentences from natural supervision. In ICLR, 2019. URL http::/aaxi..og//ab//994122222
Alexander Miller, Adam Fisch, Jesse Dodge, Amir-Hossein Karimi, Antoine Bordes, and Jason Weston. Key-value memory networks for directly reading documents. EMNLP, 2016. doi: 10.18653/v1/d11-1144 147. URL http://///d/dddoo.rrr////// http://dkddooooog/////////////11 18653/
Jake Russin, Jason Jo, Randall C. O' O'Reilly, and Yoshua Bengio. Compositional generalization in deep seq2seq model by separating syntax and semantics. CoRR, htts//994409700, 2019. URL http://axxiv.ogg/bbb///00...009
David Saxton, Edward Grefenstette, Felix Hill, and Pushmeet Kohli. Analysing mathematical reasoning abilities of neural models. In ICLR, 2019. URL https://ppenneevie.ne///d////// H|gR5iR5FX
Stuart M Shieber. An introduction to unification-based approaches to grammar. Microtome Publish- ing, Brookline, Massachusetts, 2003. Reissue of Stuart M. Shieber. An introduction to unification- based approaches grammar. CSLI Publications, Stanford, California, 1986.
Yu Su, Huan Sun, Brian Sadler, Mudhakar Srivatsa, Izzeddin Gur, Zenghui Yan, and Xifeng Yan.
On generating characteristic-richt question sets for QA evaluation. In EMNLP, 2016. URL https: www..cllwe.org/mmloooo//////////
Alon Talmor and Jonathan Berant. The web as knowledge-base for answering complex questions. In NAACL, 2018. URL http::/wwww..llwee..gggaallggg//
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. NIPS, 2017. URL https: Vaaxiv.org//d///770600777772
12

---

Published as a conference paper at ICLR 2020
Ashish Vaswani, Samy Bengio, Eugene Brevdo, Francois Chollet, Aidan N. Gomez, Stephan Gouws, Llion Jones, Lukasz Kaiser, Nal Kalchbrenner, Niki Parmar, Ryan Sepassi, Noam Shazeer. and Jakob Uszkoreit. Tensor2tensor for neural machine translation. CoRR, abs/1803.07416 2018. URL http://awwv..rrr/b//////0101..1
Yushi Wang, Jomathan Berant, and Percy Liang. Building a semantic parser overnight. In ACL, 2015.
Jason Weston, Antoine Bordes, Sumit Chopra, Alexander Rush, Bart van Merriënboer, Armand Joulin, and Tomas Mikolov, Towards Al-complete question answering: A set of prerequisite toy tasks. ICLR, 2016. URL httpss///aaxwxwor/////////////// 50t.:p/ddd...20..8.8....8..1 pdf
Xuchen Yao and Benjamin Van Durme. Information extraction over structured data: Question an- swering with freebase. In ACL, 2014.
Scott Wen-tau Yih, Matthew Richardson, Chris Meek, Ming-Wei Chang, and Jina Suh. The value of semantic parse labeling for knowledge base question answering, In ACL, 2016. URL https: //ww./cwwwoor///tbooo///------
Yuyu Zhang, Hanjun Dai, Zornitsa Kozareva, Alexander Smola, and Le Song. Variational rea- soning for question answering with knowledge graph. In AAAI, 2018. URL https://arxxiv.rr//dd/ 1709.0407l.pdf.
13

---

Published as a conference paper at ICLR 2020
APPENDIX
A EXAMPLE DATASET ITEM
The following shows example data item including the question text in various forms, the answer, the SPARQL query in various forms, some tracked statistics, and the set of used rules (atoms) and the applied rule tree (compound). Some details are omitted, indicated by ellipses ("...").
"question"; "bid Agustin Almodovar executive produce Weadfall", AueeatooWiichBraake. *bid [Agustin Almodovar] executive produce (Beacfall)", "questionNiin LonKichMi "bid m.341ha01 executive produce m, m.x0pppt"", "question wwwreetioonaaaeeeaee.. wew.aeeeeeooddiieeeeeeee.
"Did executive produce M1*, "questioneempatte.. "bid [entity] [Ve_SIMPLE] [entity]",
"expecteddRepoosa"" "No",
"spargi" "; "SELECT ccunti*) WHERE (Amns:m.0fhhh01 seifilm.produse siinssexecutiie_ppoooo. m. (..0xxppfkmi
"sparq' FattarnModonnt
wtw_eeeccttiee_eeeeeeeee "SEIECT count WHERE ('nMD na:filmn mm..flmprouoerr MI3n)",
"spergiPettern" "SELECT count (x) WERRE (Naxo BIAn)",
"ccmplexityxeezzuree"""
"parsetrnoeiessCooonn""""
"arrseTreeRueeCount"" 12
*pporglMMoxtmmnchhttnaannggt 2,
apaa "aparg|lMxxxmmmnerreee 1,
#ppe:glRuuConsttaiinnl""""" 1,
"sparglNumVarisable"""
"aggregatedRuleTn""""
"ruleId":
"Lype"; "SPAROL GENERATION", "stringValue": "ENTITY_XID"
"type": "SPAROT, GENERATTON", "stringValue": SET__GET_RRUTH
"sype": "KNCNLEDGE",
"stringvalue": *
(Executive produces, Executiva produces), na: prpootoorr.. #1 ims_xxecutive, (opoouuttoo_prrdooedddd))) "
"type": GGAMMAR RULE", "stringValue": "YNQ-DID SON-DDIDDDP_P__IADIRECE
"cype": *GRAMARR "GRAMMAR_RULE""
"stringWalue": VACIIVE_VE-VP_BEE 3
"ruleTree":
"ruleIa":
"Eype"; "SPAROL_GENERATTE" GENERATIOO",
"stringvalue"; PCONCSPi_TO_SPAN 5,
"subTree":
"ruletd": "Lype": "GRAWBAR_RULE"
"stringValue"; "S-YNe"
"subTree":
"ruletd":
"Lype": "GRAMMAR RULB",
"stringVelue": "YNQ-DID_DP_W DE
14

---

Published as a conference paper at ICLR 2020
B DATA QUALITY ANALYSIS
During the development of our data generation pipeline, we manually checked the generated exam- ples for quality. Below is random selection of examples of the final CFQ dataset (no cherry- picking was used). Brackets around [entity names] are provided just for ease of human reading. Man- ual checking also indicated that all questions are associated with the semantically correct SPARQL queries. However, because we rely on the data present in Freebase, there are three debatable ques- tions which sound somewhat unnatural
21 and 29 see further discussion below the list).
1. Who was writer, star, and cinematographer of [Tetsuo: The Bullet Man], [Nightmare Detective], and [Bullet Ballet]?
2. Which male person was sibling of [Andrew Klavan]?
3. Did [Wallace Stevens] influence [Levi Seeley]'s spouse and parent?
4. Did producer, writer, and director of [Thelma & Luis] produce, direct, and write [Light Girls]?
5. Were [Hangover Square), [Zack and Miri Make Porno], and [Clerks II] edited by founder and employee of film producer?
6. What American parent [Charlie Sistovaris] was a British screenwriter's sibling?
7. Did [Anne Williams Rubinstein] marry a person that influenced a screenwriter and influ- enced [John Most]?
8. Was [Cachún cachún ra ra!]'s director film director's American child?
9. Did IMaisy's GardenJ's executive producer write, edit, and executive produce [Pakalp- pooram], [It's Not About the Shawerma), [Rick's Canoe], and [The Fifth Wall]?
10. Was [Holly Ellenson]'s 's child [Wally Ellenson]?
11. Did [Emerald Cities]'s cinematographer, writer, and editor edit, executive produce, and direct [Blues for the Avatar] and [White Stork Is Coming]?
12. Was film producer [Lilies of the Ghetto]'s distributor and producer?
13. Which child of [Mimi Iger] did film producer employ and [The Walt Disney Company] employ?
14. What Japanese spouse of [Hong Kong ParadiseJ's 's star did [Ineko Arima] and [Nishiki Koj marry?
15. Who influenced and was influenced by [Black Dynamite]'s 's star?
16. What was written by, edited by, directed by, produced by, and executive produced by [Pauline Collins]'s child's sibling?
17. Which Swedish film director that [Théo Van Horn]'s actor influenced did [Egen ingång] star?
18. Who was influenced by [Golden Yeggs]'s s star, was influenced by [Richard Pryor], was influenced by [Bill Murray], and married [Elaine Chappelle]?
19. What did [his Is My Show]'s director, cinematographer, and star direct, edit, produce, and executive produce?
20. Who was a male costume designer and director of [Ene... due... like... fake...] and [The Windmill Bar]?
21. Was [Kumudu Munasinghe] a Dutch film producer's country of nationality's 's employee?
22. Did art director, editor, director, writer, cinematographeer and star of [Tetsuo II: Body Hammer] produce [Nightmare Detective], [Tetsuo: The Iron Man], and [A Snake of June]?
23. Was [Alexandra Naoum] [Monsieur Verdoux]'s producer, writer, and star?
24. What film director founded [THX], was employed by [American Zoetrope], [LucasArts], [Skywalker Sound], and [Lucasfilm] and founded [Industrial Light & Magic]?
25. What male employee of [Weta Workshop) [Bad Taste]'s editor?
15

---

Published as a conference paper at ICLR 2020
26. Were [Weta Digital] and [Weta Workshop] founded by cinematographer and founded by a film editor?
27. What director influenced [Dream Works AnimationJ's founder?
28. Did [Daisies] star [Fruit of Paradisel's costume designer and writer, star [Jaromír Vomácka], and star [Jirina Myskova]?
29. What character was influenced by costume designer, influenced by [Pedro Calderón de la Barca], influenced by [William Shakespeare] and [Luis Buñuel], and influenced by [Miguel de Unamuno]?
30. What British costume designer of [The Love Letter] and [The Chamber] was a screen- writer's child?
31. Was [Eric Massa] cinematographer's parent's sibling's American sibling?
32. What art director of [Stepping Sisters 1932] was a parent of [Imre Sándorházij?
33. What was executive produced by, written by, produced by, and edited by director of [V/H/S/2]'s sequel?
34. What did an editor and cinematographer of [Tongue Twister Variations] direct?
35. Who Canadian screenwriter that produced [Her Painted Hero] and [The Nick of Time Baby]?
36. Which American parent of [Janet Friedman] did [Rose Friedman] influence and marry?
37. Did [George Carlin] influence [Louis C.K.: Shameless]'s executive producer and influence [Joan Rivers]?
38. Who male writer, star, director, and costume designer of [The Wizard of Speed and Time]?
39. Who was [Lost Boys: The Thirst]'s prequel's sequel's art director?
40. Did cinematographer's female parent executive produce, direct, and write [Hit Dat Shit 5]?
41. Who married [Siri Essen], influenced [A Lesson in LoveJ's 's director and art director, influenced [Tennessee Williams], and influenced [Maxim Gorky]?
42. What Italian film director directed [Children of Hannibal]?
43. What film producer directed, wrote, edited, and produced [la estrella], [la ardilla], and [el valiente]?
44. Were [Flames: The Movie] and [Soltera] directed by male person and executive produced by [Hilda Russoff]'s 's spouse?
45. Was a sibling of [Fawwaz bin Abdulaziz Al Saud] [Badr bin Abdulaziz SaudJ's sibling?
46. What did sibling of [Louise Rohr] executive produce, produce, and edit?
47. Did French cinematographer of [Le Volcan interdit] edit [The Last Bolshevik] and direct [..K.] and [Statues Also Die]?
48. Was [Mannai Thottu Kumbidanum] directed by and written by Dutch male cinematogra- pher?
49. Was director, art director, executive producer, and costume designer of [But I'm Gen- derqueer] [Lauren Soldanoj?
50. Was [When We Were Kings] produced by film editor whose spouse was employed by [Royal Academy of Dramatic Art] and distributed by [PolyGram Filmed Entertainment]?
Further discussion of the debatable questions:
3 Did |Wallace Stevens] influence (Levi Seeleyl's spouse and parent?
The occurrence of the seemingly implausible combination of roles "spouse and parent" is due incorrect data in Freebase, in which there are 502 entities asserted to be both the spouse and parent of other entities. For instance, "Anne Dacre" is both the spouse and parent of "Christopher Conyers". We can also find occasional occurrences in CFQ of other implausible role combinations, such as "parent and child", "spouse and sibling" etc., triggered by similar Freebase data issues.
16

---

Published as a conference paper at ICLR 2020
Table 5: Most frequent answers in CFQ.
Frequency
Answer
Frequency
Answer
65479
No
594
David Lynch
65092
Yes
572
Richard Branson
1581
Promises Written in Water
551
Paris, je t'aime
1037
Shinya Tsukamoto
547
Visions of Europe
907
Vincent Gallo
484
Woody Allen
893
Metro- Goldwyn- Mayee
476
Charlie Chaplin
885
Agnès Varda
409
New York, I Love You
858
George Lucas
396
Universal Studios
800
Jacques Demy
392
Robert Santos
742
The ABCs of Death
386
Andy Warhol
709
Rick Schmidt
385
Georges Méliès
666
Ingmar Bergman
370
Chris Rock
649
Garret Schuelke
369
Steven Spielberg
622
Walt Disney
361
Jackie Chan
603
Darren Aronofsky
356
Orson Welles
Figure 3: Number of questions by complexity before (blue) and after (red) subsampling.
21 Was (Kumudu Munasinghe] a Dutch film producer's country of nationality's 's employee?
The somewhat unnatural phrasing of "country's s employee" occurs due to a modeling choice in Freehase, in which the same entity is used to represent both country and the government of that country. This makes it possible for a country to employ a person.
29
What character was inftuenced by a costume designer, influenced by [Pedro Calderón de la Barca], influenced by [William Shakespeare) ] and [Luis Buñuel), and influenced by [Miguel de Unamuno]?
The somewhat unnatural phrasing of "a character was influenced by" occurs due to mod- eling choice Freebase, which when film character based on a real person, Freebase commonly uses the same entity to represent both. This makes "person" and "character" ex- changeable in the questions where the person is also a film character.
C DATA DISTRIBUTION ANALYSIS
C.I ANSWER FREQUENCIES
Table shows the most frequently occurring answers in CFQ. Not surprisingly, after the answers "Yes" and "No",, entities related Freebase to the domain of movies have highest frequency.
C.2 IMPACT OF SUBSAMPLING ON THE DISTRIBUTION OF COMPLEXITY LEVELS
Figure illustrates how subsampling changes the distribution of questions in CFQ with different levels of complexity to become more even.
C.3 IMPACT OF SUBSAMPLING ON THE FREQUENCY OF RULES AND RULE COMBINATIONS
Subsampling increases the frequency of rarely used rules and rule combinations and decreases the frequency of commonly used ones. For rules, this is illustrated by Figure which shows the ratio of
17

---

Published as a conference paper at ICLR 2020
10.0%%
1.00%
0.1%
indix frequancy
Figure 4: Ratio of examples in which a given rule appears, before (blue) and after (red) subsampling.
100.00%
50.00%
10.00%
5.00%
1.00%
0.50%
5000
10000
15000
20000
25000
30000
combination order frequency
Figure 5: Ratio of examples in which given rule combination appears, before (blue) and after (red) subsampling.
examples each rule appears in, before and after subsampling, in the order of their frequency. Figure 5 shows the same comparison for rule combinations.
D DIVERGENCE-BASER SPLIT ANALYSIS
D.1 QUALITATIVE ANALYSIS OF MCD,
Traditional compositionality experiments often use train-test splits based on observable properties of the input and output (c.g., input/output complexity, input/output patterns, and input/output feature holdouts). One consequence of this is that the difference between train and test examples relatively easily observable "with the naked eye". The lists below illustrate that this is not usually the case for divergence-basse splits. Similar to the random sample of the general data in Appendix B we provide random sample of size 20 from both the train and test set here. Indeed, with a high divergence of 0.694, the 20 random samples of train and test questions shown below cannot easily be distinguished they both contain the same kind of questions of different sizes.
for the MCD, split
Train samples from MCDI:
What was founded by a costume designer, founded by [Forgotten Silver]'s 's star, and founded by [Jamie Selkirk]?
2. Which male person influenced and was influenced by [William Dean Howells]?
18

---

Published as a conference paper at ICLR 2020
3. Did [Marco Bellocchio] produce, write, and direct [Greek Pete]?
4. What did [Rick Schmidt] edit, [Philip Rashkovetsky] edit, and cinematographer edit?
5. Were [The Living Playing Cards] and [The Haunted Castle] edited by, directed by, and produced by French writer of [Le cauchemar Méliès]?
6. What did spouse of [Shorts]'s producer's spouse executive produce and direct?
7. Did IP. G. Wodehouse], [Raymond Chandler], [Edward Bunker], [Pauline Kael], and [Michael Cimino] influence [Grindhouse]'s 's cinematographer and star?
8. What Mexican person did a film producer employ?
9. Did [The Midnight After]'s Chinese executive producer edit [Perfect Life] and
[Dumplings]?
10. Who did [For the Secret ServiceJ's director's female spouse influence?
11. Who married, was influenced by, and influenced company's founder?
12. Was [MAN SEJ's French male German employee's is employer [Sulzer]?
13. Who influenced an actor that [Robin Santana] was influenced by and [K. J. Stevens] was influenced by and was influenced by [Virgil]?
14. Did [Pirates of Malaysia] star [Giuseppe Addobbati] and star a Spanish screenwriter?
15. Was [The Silence of the Sea] written by, produced by, executive produced by, directed by, and edited by [The Red Circle]'s Is French editor?
16. Did [Chanel] employ a German costume designer, employ [Gaspard Ulliel] and [Maureen Chiquet], and employ [Jacques Polge]?
17. Who was influenced by [Adam Sandler] and married film producer?
18. Did Spanish screenwriter's child direct and edit [Bakuchi-uchi: Nagaremono]?
19. Was a founder of [IG Port] employed by film producer?
20. Was [Orizzonti Orizzonti!] executive produced by and written by an art director's sibling?
Test samples from MCD₁:
1. What sequel of [Paranormal Activity 2] was edited by and written by film director?
2. What spouse a film producer founded [Grand Hustle Records] and was employed by [40/40 Club), [Roc-A-Fella Records], and [Def Jam Recordings]?
3. Did [Pixar] employ art director and employ [Susham Bedi]?
4. Was a sibling of [David Lindbland] [Dynamit NobelJ's Swedish founder?
5. What prequel of [Charlie the Unicorn 2] starred, was edited by, produced by, was written by, and was directed by [Jason Steele]?
6. Did [Rick Schmidt] direct, produce, executive produce, and edit [Blues for the Avatar), [White Stork Is Coming], [TThe Fifth Wall], and [It's Not About the Shawerma]?
7. Was [Luke Larkin Music] an art director's employer?
8. What prequel of [Goat Story 2] was executive produced, written, directed, edited, and pro- duced by [Jan Tománek]?
9. Was [Bullet Ballet]'s editor, star, director, and cinematographer [Promises Written in Wa- ter]'s 's star, director. writer, executive producer, and art director?
10. What was edited by, produced by, directed by, and written by [Ellis Kaan Ozen], [Thaw Bwe], [Jeffrey Baikkofsk--Bergett and [Leslie Berkley]?
11. Was a person's female sibling [Reggae in Babylon]'s producer?
12. Who director, cinematographer, executive producer, director, producer, star, and writer of [The Man Who Killed God]?
13. Was [My Sweet Home]'s director, editor, writer, art director, producer, cinematographer, and costume designer person?
19

---

Published as a conference paper at ICLR 2020
Frequency of atoms
test
10"1
10-2
10-3
10
50
100
150
200
250
300
350
400
Frequency compounds
10-1
10a
10-1
10
Figure 6: Frequency of atoms resp. compounds in the train test set
Which art director, star, and editor of [The Brown Bunny] and [Promises Written Water] did [Cord] star?
15. Did an employee and founder of [Virgin Mobile Australia], [Virgin Mobile USA], and [Virgin Mobile France] found [Virgin America] and found [V2 Records]?
16. Was a Chinese executive producer and of [Happy Ghost II] and [All's Well, Ends Well 2010] a film director?
17. Was [The VoyeurJ's executive producer an actor's parent?
18. Did [Erasable Cities]'s writer, producer, editor, art director, cinematographer, and director produce and executive produce [Promises Written in Water]?
19. Who was editor, star, and cinematographer of [Tetsuo: The Iron Man], [A Snake of June], and [Bullet Ballet]?
20. Was a costume designer's 's employer [Philips High School]?
D.2 QUANTITATIVE ANALYSIS OF MCD,
Figure 6 shows the frequency of atoms (upper graph) and compounds (lower graph) in the train and test sets of the maximum compound divergence split for the CFQ data. As the frequency of an atom resp. compound we use the fraction of examples appears in. Both atoms and compounds are indexed primarily by their frequency in the train secondarily by their frequency in the test set, in decreasing order. For practical reasons we only look at a small subset compounds here but we believe the analysis is representative.
We can see that the frequency of atoms in the two sets is very aligned and that all atoms from the test appear in the train set. The frequency of compounds however is wildly different: While some invariably occur in both sets, the frequencies are often not aligned and most compounds appear only in either the train the test set.
20

---

Published as a conference paper at ICLR 2020
Table 6: Summary of hyperparameters that deviate from the defaults. Default hyperparameter
sets are: lstm tively.
lattaanmaaaauuaaaaaaaaaaaaa bawdanauuattenn aattnnatinnnttiinnnnoo multi, transformer base, and universal transformer_ tiny, respec-
LST "MMttttettonn
Transtormer
Universal Transformer
train steps
35,000
35,000
35,000
batch size
2,048
4,096
2,048
hidden size
512
128
256
num hidden layers
2
num heads
16
learning rate schedule learning (.constant]
constant"lnnear
www.wwwwrmppagaomm rsqgr_decay
0.03
0.08
0.14
learning rate warmup steps dropout
4,000
8,000
0.4
Table 7: Examples with given enror (in %) of total test set size. See text for details.
Error type
Clause error
Filter error
Malformed output
sub node
System
sum
ins
del
prop
both
ins
del
sub
LST Atttentin
71.7
9.0
49.2
23.3
33.1
27.6
8.6
2.1
3.2
4.1
0.2
Transformer
63.9
8.0
49.2
13.3
28.2
15.4
7.0
2.1
1.7
4.2
3.0
Universal Transformer
59.9
9.8
43.1
12.1
22.9
14.5
5.0
1.7
1.1
2.7
0.8
E HYPERPARAMETERS
The experiments were run using the tensor2tensor framework (Vaswani et al. 2018) with some of the hyperparameters tuned using a random split of previous, smaller version of the data set during development. We use the default hyperparameter sets publicly available in the tensor2tensor implementation (obtained from https//ggillbbccoomeeeeerr////// hyperparameters. The hyperparameters used are summarized in Table
and override the tuned
F DETAILED ERROR ANALYSIS
F.1 BREAKDOWN OF ERROR TYPES
Table shows a more detailed analysis of the errors that the baseline models make on CFQ for MCD, (compare Section 5.2). The reported errors are bucketized into three main types: SPARQL property clause error, SPARQL filter clause егror and malformed SPARQL query in the model's output. The total number of test set examples exhibiting any clause filter eгror is reported (sum column), as well as the number of insertions (ins), deletions (del), and substitutions (sub) in the model's output with respect to the correct query. Property clause substitution errors are further subdivided into those where only the property itself is wrong while subject and object are correct (prop), those where the property correct but either subject or object wrong (node) and those where both the property and the subject or the object wrong (both).
The accuracy metric requires the model response and the golden (correct) answer to be exactly equal to each other. Thus, SPARQL query with the same clauses as the golden answer but in different order or with some of the clauses appearing multiple times is also considered to be an error despite being equivalent to the golden answer in its meaning. The amount of such errors is relatively small Transformer
though, accounting for 1.8% 0.6% and 1. 1.5% of total test set size for and Universal Transformer respectively.
F.2 QUALITATIVE ERROR ANALYSIS
Below qualitatively analyze number of instances the models fail on. We anonymize the MIDs in the same way as the data is provided to the models (see Section We first select queries on which all machine learning systems fail in all replicated runs (about 5k instances out of a total of about
21

---

Published as a conference paper at ICLR 2020
Subquery
Count
What...?
23,695
...sibling of Mx
2,331
MM'' parent....
1,222
What [entity] was...?
1,066
What sibling ...?
0
[DetNP]'s [NP]...
51,600
[NP] of [NP]...
20,038
What [NP] was [DetNP]?
416
What [NP] was [DetNPJ's [NP]?
0
Table 8: Subqueries of "What sibling of MO was MI's parent?" and their occurrences in training.
12k), and then randomly select queries from this list. In the following we discuss a few cases in more detail. Note that, for readability, the following abbreviations for the SPARQL properties in Query 1:
ns oppppppe..cccccccciaaaaaoooooooe ns aet.aabbbi__tttteeaaaa..aaaaaaaa ns oag.ghaiiaaiii....gno.r.aa...... mac.gaaiittio..rggaaaaaaaaaaaaaa
ns: oa
nafficttioni__uiveeraa
Query 1: "What sibling of MO was MI parent?"
Golden (correct) SPARQL query:
SELECT DISTINCT ?x0 WHERE ?x0 as:people www.on..cooseeoeeeeoeee M1 ?x0 ns:people wwr.on..ssliiin....... MO
FILTER ( ?x0 != MO
Inferred (system) SPARQI. query:
SELECT DISTINCT ?x0 WHERE
?x0 pespeopleeperron..ooo sibling ?xl
?x0 esspeople..erson.siil.
MO
?x1
child M1
FILTER ( ?x0 != ?x1
Analysis. The meaning of the SPARQL query generated by the system "What sibling of MO was sibling of MI's parent?", which is incorrect. We analyze the train set, in order show that we believe enough information has been provided in the train set for the question to be answered correctly.
Some subqueries of the query and their occurrences are shown in Table g While the exact sub- query "What sibling" does occur training, the words have been shown separately in many instances: the subqueries "sibling of Mx", " and "Mx's parent" occur 2,331 and 1,222 times, respectively. We can analyze this example in more detail by comparing parts of the rule tree of this example with those shown at training. As can be read from the table, similar sentences have been shown during training. Some examples are:
What executive produced by and written by sibling of M0?
22

---

Published as a conference paper at ICLR 2020
Subquery
Count
...dreet....
40,616
...edit...
31,776
Did..?
17,464
film director
5,603
male film director
121
edit and direct...
93
Did [DetNP] [VP] [DeINP]?
17,464
Did [DetNP] [VP] and [VP] [DeNNP]?
1,432
Did [DetNP] [VP] [DetNP] and [DetNP]?
909
Did [DetNP] [VP] and [VP] [DetNP] and [DeNNP]?
0
Table 9: Subqueries of "Did a male film director edit and direct MO and M1?" and their occurrences in training.
What costume designer did MI's parent employ?
What cinematographer was film editor that M2 and M3 married?
What film director was a character influenced by M2?
Query 2: "Did a male film director edit and direct MO and MI?"
Golden (correct) SPARQI query:
SELECT count ( * WHERE {
7x0
na:film. w...lmm.dirett.om film MO
?x0
film M1
?x0 na:film.editor.ff
MO
?x0 ns: ma:filmmeddioorffll M1
7x0 ns asspeople..ersso.gerco m_ 05
Inferred (system) SPARQL query:
SELECT count ( WHERE {
2x0 as:film.directon film Ma
?x0
M1
2x0 na:film.editor.ff MO
?x0
m_05zpp2
Analysis. The meaning of the inferred SPARQL query is "Did male film director edit MO and direct MO and M1?". thus seems the model 'forget'' to include the relation between the director and movie MI.
Looking at subqueries and their occurrence count (Table 9. we see again that various subqueries occur often during training. However, "edit and direct" have not been shown often together. When looking at the rule trees, we see that both conjunctions in the query occur often at training sepa- rately: "Did [DeNNP] [VP] and [VP] [DetNP]" occurs 1,432 times, and "Did [DeNNP] [VP] [Entity] and [Entity]" occurs 909 times. However, they never occur together: "Did [DetNP] [VP] and [VP] [DetNP] and [DetNP]" does not occur training. This may be the reason why all systems fail on this example, but at the same time we believe compositional learner should be able to generalize correctly given the training instances. Some examples are:
Did male film director that M3's parent married influence art director?
Did film producer that played M2 edit and direct M1?
Did screenwriter edit and direct sequel of M1
Did Chinese male film director edit M1 and M2?
23

---

Published as a conference paper at ICLR 2020
1.0
simple (79%, 0.00]
(ewshot@ [94%, 0.04]
template<jump
right> [94%, 0.04]
fillen@11 [94%, 0.04]
0.8
complex<jump-@535 T/U (63%, 0.07]
template<<nght> (78)g 0.055
primitive-ttrm left> T/U [94%s, 0.07]
template<opposite right> (78%.. 0.06]
complex<jump>-16 T/UT 663%, 0.07)
complex<jump----22
[6.3% 0.07]
Accuracy
complex<jump-@9
0.07]
complexcjupp2@110
0.07]
LSTM (34%.
(63%,
0.4
complex<|ump2ee
[63%, 0.08]
complex<jupp-@- UT (63%, 0.05]
complex<jump>-@e LSTM (6.3%, 0.08]
complex<jump-@2 [6.3%, 0.08]
complex<jmpp@@2 UT (63%, 0.08]
0.2
length LSTM (81%, 0.03]
complex<qump--22 (63%, 0.08)
complex<jump>-02 -1 [63%, 0.08]
complexejump=@1
complex<jump>@@
[63%, 0.08]
[6.3%
0.1
0.2
length T/UT [81%, 0.03]
Compound divergence
Figure 7: Accuracy and divergence measurements for splits of SCAN used in other work (see text for details). The numbers in brackets show the train / full data-set ratio, and the atom divergence.
G ADDITIONAL EXPERIMENTAL RESULTS ON SCAN
Figure shows scatter plot of accuracy vs. compound divergence for the three baseline archi- tectures (see Section (5) on existing splits of the SCAN data. These splits are discussed in (Lake & Baroni 2018) and (Loula et al., 2018), and the exact split data is available. (Data splits obtained We map these splits onto the re-created SCAN data, which enables us to measure the atom and compound divergences. The authors present a total of six split experiments (some with several sub-experiments):
from httpss//github..c weatttuu.combbreddeee wommbbrendenlake/SCAA..
Lake & Baroni 2018):
simple (random)
by action sequence length
adding a primitive and adding primitive along with complex combinations
Loula et al. 2018):
adding template
adding template,filee
adding more training examples of fillers (fewshot)
In the plot, we omit some data points that are too close to be distinguished easily. The point la- bels have the form '(abbreviated experiment (amee)<(arametr) (number of samples) (baseline system abbreviation) [(train set size fraction), (split atom divergence)]'. The train set size fraction is given as a percentage of the overall data size. The baseline system abbreviations are LSTM, T for Transformer, UT for Universal Transformer, T/UT where both transformer models are indistin- guishable, and empty where all three systems perform indistinguishably. The abbreviated experiment name one of the names in italics above.
We can observe strong dependency of the accuracies on the compound divergence of the data split. Again, this seems to indicate that the compound divergence is correlated with accuracy for these baseline architectures. One difference to the data shown Figure 2 is that for this set of experiments the accuracy drops faster with increasing compound divergence. One explanation for this effect that the experiments are directly aimed at highlighting one specific potentially prob- lematic scenario for learning. E.g. in the experiment 'primitive<jump>' (with very low accuracies for all three systems) the jump command is shown exactly in one combination (namely alone) in the training data while it occurs in all test examples in arbitrary combinations.
24

---

Published as a conference paper at ICLR 2020
This is reflected in the higher atom divergence value of 0.08 for this split, as well in all other splits that exhibit a low accuracy at a low compound divergence in Figure [ Note that Lake & Baroni (2018) already compare the experiment "primitivejjun>>' to the experiment prrimitve<ttrnn lefts' for which all three systems achieve a much higher accuracy. In their interpretation of this phenomenon, they mainly focus the fact that in contrast to 'jump', the action 'turn left' is also generated by other inputs. We additionally observe that the latter experiment also has slightly lower atom divergence of 0.07, lower compound divergence, and it covers much larger part of the data in the train set (94% vs. 63%).
While the accuracies we observe for the 'primitive' experiments are very much in line with the results reported by Lake & Baroni (2018), we noticed few interesting differences for other exper- iments: All three systems go 100% accuracy on the fewshot task even for one example (while Loula et al. (2018) report slowly increasing accuracy for the architecture they evaluate). On the other hand, both transformer models only reach 0% accuracy on the length split, while the LSTM obtains around 14% (which is in line with what previous work reports).
H ANALYSIS OF RELATIONS BETWEEN ACCURACY, COMPOUND DIVERGENCE, AND TRAINING SIZE
Figure shows for all baseline systems strong correlation between accuracy and compound di- vergence for the chosen training sizes (96k for CFQ and 8k for SCAN). One interesting question whether and how this correlation is changed for different training sizes. Figures g and show that this correlation holds also for smaller training sizes but that the accuracy is generally somewhat lower for smaller training sizes.
At the same time, we observe that the difference between accuracies of various training sizes gets smaller as the training size increases. This can be seen more clearly in Figures an [1] which plot the training size rather than the compound divergence on the x-axis. These figures show that the increase in accuracy flattens significantly we reach training size of about 80k for CFQ and about 6k for SCAN. This indicates that further increasing train set size may not be sufficient to do well on these compositionality experiments.
I LOGICAL FORM
To represent our logical form we use syntax of the description logic EL (Baader et al. 2003 2005) with additional concept and role constructors. These constructors not have description logic se- mantics; instead, their meaning is completely determined by the set of generation rules of the CFQ dataset.
Let A be a concept name. C, C1, C2 be concepts, R, R1, R2 be roles, and be raw string. Then the following would be concepts:
C::=
T
A
C nC2
3R.C'
And (Ci, C2) DropDependency (C)
Entity (v)
Predi catewi www.eittooooooooooeoooiioo Preeeettttttttiieiooooeeeeeeeeee (Rı, R2) ProjectedRol (Ci, C2)
TypeInstance (C, v)
and the following would be roles:
=
RolePair (C1, C2)
Note that our logical form does not have roles other than those in a form of RolePair (C1, C2).
25

---

Published as a conference paper at ICLR 2020
Transfrmeer
Ua verual Trersfommr
116
1.0
0.4
PX
0.2
02-
02-
00
02
0.4
06
0.3
00
C44
C4
0.
04
Figure 8: Accuracies of the three baseline systems on CFQ as a function of compound divergence at different training sizes.
LSTMeatttoriin
Transformer
Transfomer
1.0
33
1.0
0.4
Figure 9: Accuracies of the three baseline systems SCAN function of compound divergence at different training sizes.
0.-
0.6
11800ng 341 655
Tratting S47 106
Figure 10: Accuracies of the three baseline systems on CFQ at different divergence levels as function of training size.
1STWe-sttorron
Transformer
Trancfomerr
0.-
3.6
0.2
0.6
11202ig
realiing
Figure 11: Accuracies of the three baseline systems on SCAN at different divergence levels as a function of training size.
26

---

Published as a conference paper at ICLR 2020
New strings are generated by using special function new var ($8). This function generates unique string of the form ?x<N>, where is unique number, and assigns that string to variable $S. This string can later be used as variable in SPARQL constraint.
J
RULE FORMAT
This section describes the format of each of the rule types use for generating the CFQ dataset, in the form which they appear in the rules index in Appendix(M)
General formatting conventions shared across all rule types:
Variable names prefixed by 'S'. Example: $X.
(Exception: In grammar rules, while variables standing for constants are prefixed by 'S', variables standing for logical forms prefixed by '_' Example: _actionn
Concept names written in camel case. Example: F 1iIProducer.
Names of functions that output logical forms (concepts, roles, or knowledge) are also writ- ten in camel case. Examples: DropDependency, BoundRolePair RolePair.
Names of functions that output string literals which are used for converting logical forms to SPARQL are written in lowercase with underscores. Examples: def2sparql, get_specializate satiiiiiiiiiiiiss..... new new_var. var.
String literals enclosed in single quotes. Example: ' 'ns: mas:film:drretor..
J.1 GRAMMAR RULE FORMAT
The CFQ grammar is a unification-basee grammar of recursive rewriting rules used to generate pairs of strings and their corresponding logical form. For an introductory overview of unification-baa based grammars including several popular variations, see SShieber (2003). The rules in the CFQ grammar follow similar syntax particular to that used the Prolog extension GULP 3.1 [Covington] 1994), with the addition of support for disjunction, negation, absence, and default inheritance of features, and with minor differences in formatting described below.
Properties shared between the CFQ grammar syntax and that of (Covington 1994) include the fol- lowing:
Grammar rules are notated as variations of context- free phrase- rules of the form To Ti ... Tn, where each of the syntactie non-terminals and terminals To ... Tn augmented with feature lists parentheses.
Each grammar rule can be interpreted as specifying how a feature structure (with logical form) that is unifiable with the lefthand side can be re-written to the sequence of features structures (with logical form) indicated on the righthand side.
Features are represented as attribute-value pairs separated by a colon (i.e.,
attributevvalue.
Shared values in feature structures are represented through the use variables.
Specifically, in the rules index, CFQ grammar rules are described in the format
To(F))(H/ +
where:
Each T; is syntactic category (syntactic nonterminal) or string literal (syntactic termi- nal).
Each L, for i E [1,n] is either a variable representing a logical form or an empty string. In the case when L, is an empty string, we allow dropping the trailing slash from the Tx(F))/ expression, resulting in just (F.)..
Log logical form expressed in terms of T.....
27

---

Published as a conference paper at ICLR 2020
Each F; is comma-separated feature list of the form dattribute::valu ierrrbbuteyvauueee In the case where F; is empty, we allow dropping the parentheses from the (F)) expression, resulting in just T,
is either an empty string or one of the variables L; for E [I, indicating that Fo default inherits the features of F; (the syntactic "head"). In the case where H is empty string, we allow dropping the brackets from the (F)F))(H] expression, resulting in just (Fo).
Note that while the above notation adopts the convention of splitting the syntactic category and logical form from the feature list for visual prominence and to highlight the relationship to its context-free phrase-structure rule core, behaviorally it is identical to adding two more features to the feature list (we can call them, for example, cat and sem) to represent the syntactic category and logical form.
This means that, for example, the rule
ACTIVE_ hell_head//_aae + VP SIMPIIIMIEEEEEE (form: wnw.nitiiet/ieiiiii..iiiiiie /_he
can be considered a notational shorthand for the following rule expressed purely using feature lists:
(cat: :ACTIVE_V,, sem:_heade [_head] + (cat:ve_SIMPLE, sem: sem:_head, form:infinitive
Disjunction of features. Similarly to (Krrtunnen 1984). we allow disjunctive feature specifica- tions, which we denote by separating the alternative values with a pipe (*I'). The feature spec- ification (frud in iffiniiiie would thus unify with either (form:gerund) or (form: infinitive), but not with (Form:past_particcipp
Absence of features. We use a special atomic value _ to indicate that given fea- ture must either be absent or else explicitly set the value _non__. The feature specifica- tion srubject:_nonee (subject : __none_, object : yes), but not with (subject yes, object : yes).
ioject:yes: would thus unify with either (object :yss) or
Negation of features. Similarly to (Karttunen) 1984), we allow negated feature specifications, which we denote by prefixing the attribute with a minus sign ('-). The feature specification e-form:gerrunee iinfinitiin (form: __n___), but not with (form: gerund) or (form: infinitivel In general, a fea- ture specification of the form (-attribute:we ... V2) can be considered notational short- hand for aattribute:e
would thus unify with form::patt_partccpppp
or
vv __none_), where Vi+1 I... Vv is an enumeration of all possible values of the feature attribute other than v1 .... V-j-
Default inheritance of features. the lefthand side term is notated as To (H),,, with H equal to one of the variables for i [1, ri). then this is interpreted notational shorthand for augmenting both Fo and F. with an additional list of attribute-value pairs (a ::81, ..., (u:Sux), where aj... are all of the attributes listed in F. that were not originally listed in Fo.
Unification of logical forms. As described in Appendix D we represent logical forms us- ing a variation of description logic, rather than using feature structures. In the context of unification, we consider logical forms to unify if and only they achieve structural concept equality after variable replacement (using the same variable replacements applied during unification of the corresponding feature lists), while taking into account the commutativ- ity and associativity of T. For example, under this criterion, the logical form GenderRel n IRolePair (Predicate, Gender) h_ad would unify with either GenderRel ERolePair (Predicate, Gender) .Male or with (ERolePair (Predicate, Gender) .Male) n GenderRel under variable replacement mapping head to Male, but would not unify with GenderRel n BRolePair (Predicate, Gender) Male NI GRo iPeeeeaa (Predicate, GenderHaver) FFilm 1mP roducer.
28

---

Published as a conference paper at ICLR 2020
J.2 KNOWLEDGE RULE FORMAT
CFQ knowledge rules output expressions representing facts that are known to be true. They have no direct effect on text, logical forms, or SPARQI, but the generated knowledge can be used as preconditions to other rules. In the rules index, they are described in the following format:
+ where K knowledge that is output.
By convention, we define the rule name a knowledge rule to be simply the string representing the knowledge that the rule outputs, and omit the rule name in the rules index for brevity.
The union of those rules defines a knowledge base which we denote with K BCFQ.
All knowledge in CFQ is represented in the form P(X,, Xn), where P is predicate from the list below, and X X,, variable-based expressions.
Xn are either logical forms or else raw strings. Knowledge rules do not use
Supported knowledge predicates:
BoundRolePairrs
ExclusiveRolePaii
Freebas@EnnttttMappiing
FreebaseProopert/Mppppiig
PreebaseTYpeeMappingg
NondxclusiveRolleFa..
Role
J.3
INFERENCE RULE FORMAT
CFQ inference rules transform logical forms and may be conditioned on knowledge. the rules index, they are described in the following format:
K: Lo L1
where K represents a comma-separated list of knowledge preconditions, and Lo and L1 represent the input and output logical forms, all expressed in terms of shared set of variables Vi...." Um.
These rules are interpreted as stating that if there exists variable replacement r() replacing ...... Um with some logical forms lm. respectively, such that r(K) S K BBFF then can apply the inference rule by rewriting r r(Lo) to r(L1).
RESOLUTION RULE FORMAT
CFQ resolution rules transform SPARQL expressions and may be conditioned knowledge. They do not affect text or logical forms.
In the rules index, they are described in the following format:
K S. + S S.
where K represents comma-separated list of knowledge preconditions, So is variable-based expression and S S, are either raw SPARQL strings or else expressions described in terms of the same variables used in Sg and K.
These rules are interpreted as stating that if there exists a variable replacement r() replacing U1..... Um with some logical forms, strings, expressions l,,..., Im respectively, such that r r(K) S K KBCFQ then we can apply the resolution rule by rewriting r(S)) to the sequence terms r(Si): ... r(S.).
29

---

Published as a conference paper at ICLR 2020
K GENERATION ALGORITHM
Our generation algorithm produces triples of the form (question, logical form, SPARQL query) in mixed top-down and bottom-up fashion, with the final program of rule applications output alongside each triple in the form of a rule application DAG. The top-down portion of generation is responsible for efficiently searching for rules that can applied to produce a meaningful example, while the bottom-up u portion is responsible for actually applying the rules (i.e., performing the composition) and for producing the DAG.
The generation process proceeds in two phases, each involving top-down as well bottom-up aspect. In the first phase, we apply grammar rules interleaved with inference rules to produce a pair of (question, logical form). Specifically, we apply recursive top-down algorithm which starts with the S nonterminal and at every step performs a random search over the rules in the grammar which could produce the target nonterminal with accompanying feature structure. This top-down process proceeds until a candidate syntactic parse tree is attained whose leaves consist purely of syntactic terminals (i.e., string literals or entity placeholders). The grammar rules from this candidate parse tree are then applied in bottom-up fashion beginning with the syntactic terminals to yield a tree of (text, logical form) pairs. After each such bottom-up grammar rule application, we then greedily apply all possible inference rules on the resulting logical forms, applying an arbitrary deterministic ordering to the inference rules in cases where rules could be applied in multiple valid orderings. This ensures that inference rules and grammar rules are executed in an interleaved manner and each inference rule is applied at the earliest possible occasion.
When (question, logical form) pair is generated for the S nonterminal, we proceed to the sec- ond phase of the algorithm, in which resolution rules are applied to generate a corresponding SPARQL query to make up the third element of the desired (question, logical form, SPARQL query) triple. In practice, the bulk of the work in this phase is performed in a top-down fashion, in which resolution rules are recursively applied to transform starting expression of the form get_specia 1 i zztt ions ($L) (where L represents the logical form output from the grammar phase) into sequence of text literals representing the SPARQL query. This is followed nominally by bottom-up process to construct the rule application DAG, yielding tree of resolution rule applications of similar form to the tree of interleaved grammar and inference rules output from the grammar phase. Note that while the grammar phase involves large degree of random choice, the resolution phase proceeds much more deterministically, as the CFQ resolution rules have been designed such that any given question can yield only one possible SPARQI query, modulo commu- tativity and associativity of F. In cases where resolution rules could be applied in multiple valid orderings, we again apply an arbitrary deterministic ordering to the resolution rules as to yield as consistent as possible a rule application DAG and (question, logical form, SPARQL query) triple for any given question.
Finally, to ease the task of tracking unique query patterns and to minimize the impact on the learn- ing task of implementation details regarding choice of variable names or ordering of clauses, normalize the final SPARQI. query by alphabetically sorting the query clauses and re-numbering the variables to follow a standard increasing order.
The resulting (question, logical form, SPARQL query) triple is then appended to the CFQ dataset.
K.1 JOIN BY LOGICAL FORM
In general, we do not explicitly track rules to represent the saample-indepencee behaviors of the generation algorithm, as the universal applicability of these rules mean that the complete behavior of the generator should be observable on any reasonably-sizee train set. The same applies to certain core behaviors of the description logic &C, such as commutativity and associativity of n, which we omit tracking as explicit rules due to their similar ubiquity of application.
One example-independent rule, however, that we do explicitly track is the rule that describes the handover process between the grammar phase and the resolution phase or in terms of the rule application DAG, the rule that joins the tree of interleaved grammar and inference rule applications with the tree of resolution rule applications. We call this rule JOIN BY LOGICAL FORM. It is included in the rules list for every example in CFQ and appears as the head of the rule application tree for each example.
30

---

Published as a conference paper at ICLR 2020
K.2 RELATIONSHIP BETWEEN GENERATION AND PARSING
Note that conceptually a similar approach for combining the different rule types could be applied to the semantic parsing task. The main difference would he that, instead of performing random search the grammar, the semantic parsing task would need to find the set of rules which produce the desired input text.
K.3 SELECTING AN APPROPRIATE SAMPLE SET
For many domains, the set of examples generated by exhaustively combining rules is infinite or prohibitively large. For example, the CFQ grammar generates an infinite set of questions, and even when restricted to reasonable complexity, the set is still too large for practical use. This means that we need to choose which subset of examples we want to include in our dataset. Given our goal of comprehensively measuring compositional generalization, we do this by:
1. maximizing the overall diversity of rule combinations (allowing to test many rule combinations as possible)
2. while using a uniform distribution from simple examples to increasingly more complex examples.
We measure the diversity of rule combinations of a dataset using the empirical entropy over the fre- quency distribution of the subgraphs of the rule application DAGs, and we measure the complexity of an example using the number of rule applications used to generate it.
For CFQ, we choose the following practical trade-off between these two criteria. We first generate sufficiently large sample set by performing random rule applications. We then subsample from it select a subset that maximizes the entropy of the subgraph distribution (while only taking into account subgraphs with limited number of nodes for practicality). We use greedy algorithm that incrementally assigns elements to the subsampled set while maximizing entropy each step.
The subsampling is initially limited to examples with the smallest complexity level and continues with increasingly larger complexity levels. We cap the maximum number of examples per level to achieve uniform distribution across levels, and we limit the maximum complexity level such that the questions remain relatively natural. Table shows examples of generated questions at varying levels of complexity.
L EXAMPLE OF A RULE APPLICATION DAG
Figures 12 through show the rule application DAG that was produced when generating the ques- tion "Who directed [entity]?". They illustrate how grammar, inference, and knowledge rules are combined to generate a pair of text and logical form, and how resolution rules are used to generate the SPARQL query for the resulting logical form.
L. DAG NORMALIZATION
As discussed in Section nodes of this DAG represent rule applications while edges represent de- pendencies among the rules; i.e., an edge - B means that rule B strictly depends on rule A in the sense that the generator cannot apply rule B before applying rule A. The DAG is normalized to ensure that a certain rule combination is represented using the same DAG across all the exam- ples where it occurs. This is important for meaningfully comparing measures such entropy and divergence across subgraphs of different examples.
Specifically, together with adopting the measures described above to ensure that rules are applied in a deterministic order, we achieve the normalization the DAG by only producing edges that represent "minimal dependencies". This means that if rule A can be applied after rule B, but it could also be applied after rule with B + B' (i.c., depends on B), we don't produce the edge B' A.
31

---

Published as a conference paper at ICLR 2020
MP INODECT COOLRECTOOOCC conject Sype BIt. 100 Rojject type Sa-1l bond) hedd Sunject Sinjectigenteer onjectunce gor werr ACTEPA PPLAMITI Lype Set, unter EOR Typ (0177_00 Jes
WERE
1t. HNCIEEET (ol Leciin)) Stolefair (Cb recheee de
33 W SNOTECT CoJjCtt Ront sujject: rete J. actiin T9/ 200000es
SELECT DESTEMT Dt. D0L20P OX 1eN JUP (00) (1))))
65ee soarate rigure
(Cont1yy)
7x0 fo...... dirctrr wot..r..ii. .fle 21
Le (RL)
SELECT OISTUNG 70 INdI
3hi7ePiir (bjecttove (bje0..8
goe Type
Directang Sabjectiqumtteet
WP Conncct id 21 octting)
had w.diiitoor reterr filn 121
SELECT DISTINCT 750 MILEE
"Girecter" bireccung
"ci -ecteet" Bireerin
"SI rocted" Directing
cirected (entsty]
(5ee aiirevttted inference rules.
happppappppiiiigg streel decacppdeene doulatuu (sakyee 3.0 17catt sam
"Hirected (ontity) Biree Su. derppeeeeeeeeee 3h0 ar www.errrrrrdiiie Crwddicate srreett two E1
Di rintting S1pp" Sippe-igeeete rigentver n 3totehat OP Linder grer) E1
Sh Sireciee .13
To Peaire 4 n ItcleiesrEs T):
n worrter
s. stolehirss 31.A B. Snolshaitts Fl-A
Rolefarrss.
Gesperttoor)
0 thoi Iholittc (CC for pua., numbe Sn, dbjal 38., aábject Jane LLaction
Eaun JDL E. MITIL VITIL PROIOOT SELJCT:
Du reciini Susjecilennteer Bholdrar ciliitt (irette))..e ..13
Willeooo SUBJECT.
(ww.errrreeeeeaaee sereedicen Ueder
WAy
TONPEE 2400 30.5 PAIRS
"Elrectad rentity)
(cosity)
Prodica www.cct
Eurezing
Songuaan
EeT Iet Phent case LnneeT penderrgon gorr)
2013
"tt direcced pertisp"
Text" Logical 10r8
Woo" Pe- 500
Inference Baie
Seve La Lan Rv..P SPAROL
Legond
Figure 12: The normalized rule application DAG that was produced for "Who directed [entity]?"
(grammar/inference rules portion, continued Figures 13 and 14
32

---

Published as a conference paper at ICLR 2020
www.aaterrppeee.. phupstegee SF1
WEER
TE $Y
raletsperii (91 St
tril entzoporat (X))
SELEE SISTINCT R0C.00 E2. noe (0r(E)0)))
RELATIO MADTNN Jehion IICLSSE
"en" ti director fain
1981 7v0 ez: film director
ded ref2sparaless TEX n ST. 9913 drtspprgl 5913
SELECT OESTRCI WENE 7O 3 AS 207330
7x0 ne peop par.o 7 mE: L.L. dir restor
Sagaarrlla rellzsorgii
" bipelppr (pettporai(s3) (X)
SOLECT DISTINCT bad WEEE
3 AS 2009 201500
Jno directed (entaty)
di
(ts goopl woople.errse
FIFE MAFF INC.
paop 3007
www.lilllyyyllpppp..oo Horsen,
"Bo dirari pantiss
Lnffen cree.)
591
VIIEE ST. (N1 vertonl SerEaN get werde (9))..
M.S o WAy
GET SAE RELATION
get Loer
$:3:
Tmcc" oggical Gam
TEXC" Logical rom
SET VIL TIPE MOCHEMM
Lagent
Figure 13: The normalized rule application DAG that produced for "Who directed [entity]?" (resolution rules portion, continued from Figure 12).
33

---

Published as a conference paper at ICLR 2020
Legend
Granzor
57 MHz
"Text";
directed [entity]";
BRolefarr(Director Directee).Ef)
Inference Rule
"Text"; Logical form
PREDICATE UNREIFICATION:
Resolution Rule
Role(Q, Role(R, P):
SPARQL
3RolePair Predicate). HeleeoLr(Prediccte,, R).A)
3tolePair(O. R).A
Knowledge Rule
"Wo directed [entity]"; Person Booiefatr(Dirrecor (trectee)
(Direete,,,eee Directing)
ROUND PREDTCATF DRJECT:
BoundRolePairs(A.
RolePair(T, S)>
(Darrettr,,,or, Darecting)
3RolePair(O, R)-(A)3) ERolePair(S, (AnB)
"Who directed [entity]"; Person 3RolePair (Director Predicate). Directing (Preecsir Direccee))).)r
(Dt.eeoeeeaarssrrrreeeeeeteeeeee (PrePair Agent), RolePair(Predicate (
LGNORE HOUND ROLE FAIRS: reeelicttetttBeudccleea...
diracted [entity]":
Person (Agent,,
Directing n PRolePar (PredLictteDDirectee)) Directee)
ROUND RolePair(R, RolePair(T,
BoundRoleFairst
#RoleFair(O. ().(AΠB] #RcloPair(S, (A7(8)8)
"Who directed [entity]";
Person i (AggeeParrAgget..... (Tedicaate),.
SubjecttgentvVer) n BholaPaar(Preaicateeerre Direttee)
->BoundRolePair jerrAgenWerb (Subject, Subjectraver), (Ageet, Predicate))
IGNORE DEPENDENCY
Dropdependency((R
"whn diracced [ontity]":
Person 3Ro1ePair Subjectteerrr (Directtin
SubjectAgentVerb @oolePairPreedicate
Directee), Direeeeeeeeeeereeeeeeeee..e.
WHOT subject (aaojject/DDgggpeeeneeee Drrggeegendencc((Lius )(abbeeeddenc((__ujett))) 1o sabjeeeeeeeetttteeettttteeeerrr
INDIRINDDETTTC (1s _noattttttt___.. Bn) Sny_ssbjjct
WP_INDIRECT(farE past, nunber:$n, object-yes, subject:_nom
"Who diracted fentityl";
DropDapencency(PPr
DropDependencyy BatpeeccyyBBoeeaarraaaaaaaa Subp:/bbbbeetttSuetteebteeee Sibjetttere)))
Directing Subjee Legeentrrrr (eele
Figure 14: The normalized rule application DAG that was produced for "Who directed [entity]?" (inference rules portion, continued from Figure 12
L.2 CONCEPT ABBREVIATIONS
For brevity, in the rule application DAG figures we have applied the following abbreviations for several lengthy concept names:
Directingg
SubjectAgent = PredicateMiLlBBondRddePeedi (RolePairz SubjectHaver, Subject), RolePair (Predi cate, Agent))
34

---

Published as a conference paper at ICLR 2020
Ob Undergeeeeee PredicaceittlbbudkRllee...s (RolePair
ob Hace,, Object), RolePair (Predicate, Undergoer)
B1 Entity (E1')
L.3
ENTITY PLACEHOLDERS
As described in Section 3.2 during generation we initially generate (question, logical form, SPARQL query) triple containing entity placeholders, and then re- place those placeholders with specific entities as a post-processing step. Conceptually, could construct rule application DAG describing either the process by which the original (question, logical form, SPARQL query) triple with entity placcholders was generated, alternatively the rules that would need to be applied if constructing the (question, logical form, SPARQL query) triple containing the final entity MIDs directly. Struc- turally, these two DAGs are identical, differing only the definition of two entity-related rules described below. The rule application DAG shown in the accompanying figures is the version using entity placeholders.
Versions of entity rules applicable when using entity placeholders:
ENTITY=LENTITY HSz7QrdGdsX:
ENTITY (number: singular) / /Entity (new var (V1)
'lentityl'
ENTITY_MID.
ent (Entity (SX)) 9x
Versions of entity rules applicable when using actual entity MIDs:
ENTITY:EENTITV] S HSZ7QrdGdsX:
ENTITY (number: : singular) /' //m." sx
+ 'm.' SX
ENTITY MID:
2nt2sparql (mm. $X) /nsmm.
L.4 SUBGRAPHS AND THEIR WEIGHTS
shows an example of subgraphs in order to provide more details on the sampling and weighting of compounds. An example non-linear subgraph is highlighted by the red area, and two linear subgraphs highlighted by the blue and the yellow areas, respectively.
Figure 15
given a large subset G of subgraphs from the sample set as a whole, we calculate for each sample the weight of each subgraph G G that occurs in that sample as:
As described in Section 2.1
w(G)
(1 (Eoo)(
G' Eoso(G') P(G"|G)),
where occ(G)) is the all occurrences of G in the sample, - denotes the strict subgraph relation, and PG)' is the empirical probability of G" occurring as supergraph of G over the full sample set.
Intuitively, we are trying to estimate how interesting the subgraph G is in the sample. First, for every occurrence g of a subgraph G, we look for the supergraph G' of g that co-occurs most often with G in the full sample set. The empirical probability of having G' as supergraph of G determines how interesting the occurrence g is the higher this probability, the less interesting the occurrence. Thus compute the weight of the occurrence as the complement of this maximum empirical probability. Then we take the weight of to be the weight of the most interesting occurrence of in the sample.
E.g. in the extreme case that G only occurs within the context G'. the weight G will be 0 in all sam- ples. Conversely, if G occurs in many different contexts, such that there is single other subgraph G' that subsumes it in many cases, then wGG) will be high in samples in which occurs. This ensures that when calculating compound divergence based weighted subset of compounds, the
35

---

Published as a conference paper at ICLR 2020
Teat Lntre
EIERET MOR Erecte S1
Plant:
Proariis
conprtient sattec www.eeeeeeeeeennnn AutacPioetii 2CA2 Metern
atremay Lagerigem are Solderr Atreeee
saperperoo exprrs vergerees
and laynikge liek Sogec
RoPting SUNNOSS THE
Suaneer Benstay Lagenigenou htgeiiinsnnnooooooooooor Gparierrgeros
Sentiog Begmsppedes Bride theaintt Eimdors
new AU
Aude la Praaan paial
Shvernie Jn Seectoe Tor BuCoREnnna stnoe!
Figure 15: Examples subgraphs in the grammar/inference rules portion for "Who directed [entity]?" (from Figure[I2] non-linear subgraph (red area), and two linear subgraphs (yellow and blue areas), of which one (yellow area) is subgraph of the other (blue area).
most representative compounds are taken into account, while avoiding double-counting compounds whose frequency occurrence already largely explainable by the frequency of occurrence of one of its super-compounds.
suppose that represents the smallest linear subgraph (yel- low area), and suppose that the weight of G in this sample is 0.4. Then this means that there exists some other subgraph G" (for instance, the linear subgraph highlighted by the blue area) that is a supergraph of G in 60% of the occurrences of G across the sample set.
Returning to our example Figure 15,
M RULES INDEX
Below is selection of the rules used in the generation of CFQ. Specifically, this includes all rules involved in generating the question "Who directed [entity]?" (the same example illustrated in the rule application DAG in Appendix [.) The format of the rules is discussed in Appendix [
M.1 GRAMMAR RULES
WHQ F6E9egkQqxj:
$/_x
WHQ/_x
WHQ=NPQ INDIRECT INDIRECT_
[HQ__subeect] /ttppppppppeeenccyyccccccpp (_subjectt)
DropDependency (RRolePaiz (Subject, [aojjectHave))__ccttt
+ NPQ INDIRECT (is_what: L_t___aaa________ none_, number: /_sbjjccttttt
VP INIIIIIIICTTTOCCC (form:past, number: object:yes, subject:_ none ) action
NPQ INDIRECT=WHO SBIBECCT-WWOO.SppPXXXLLZZZ 5ptbPXXbuLZ:
[O__INDRECTT (number: (numberr singular) /Person who
VP INDIRECT= INDIRECT DP ETT Byyy
36

---

Published as a conference paper at ICLR 2020
VP INDIRECT (object: :es)) Lacticn//_action RRleeair (0b
jbjett __ob
+ VP VP_IND (object:_none__ /
DF/_object
VP BAC.://TAAAAIIILLLLRRSSTSm//
subject_type: [_head] /_head n. VP "F_INDIRECT (cbject_ Sut, Sut,
predicatteiithBBonlllllPPPi (RolePair ( (SubjectHaver, Subject), RolePair )gent)) n
PresiccassstttBBuudoollllaasssss (RolePair (Oaeaaatt Object),
RoleFair Undergoer)
+ ACTIVE_ (ageettttteeeeeeeaeaeeee
ACTIVE
hJ
ACTIVE_ VP (number: :nugber:sinuular)) [_head/ /ead
singular)
VP VP_SIMPLE (form: head
VP SIMPLE=VP GHWBBRVRZe
VP SIMPLE (agent, type person, undergoer httprggorrrtyyemooiieee. [_head] bead
VP=DIRECTED JKY2NOOWW:::
VP caannnet_id:iirrettiiii
+ 'dirtdted'
OP-ENTITY_MGSPSGYREE
DP (is_proper_noun:ye) number:singular) [_head] /_ae
ENTITY/_head
ENTIY-ENNIYYLHH777dGGaY
ENTITY (number: nuumber:singulary /Entity (new_var (V1))
[[entit]]'
(211 grammar rules total)
M.2 INFERENCE RULES
BOUND ROLES WITH PREDICATE OBJECT:
BoundkolePairse ($A, Rolepair (SR, $Q), Rolepair ) RkolePair ($Q, SR) (SA $8) 3kolePair ($S, $T). (SA n $8)
BOUND ROLES
BOIS_IITT_PPPPP PREDICATE
PREDICATT_SURJECTT. SUBJECT:
NoundKolePairse ($H, RolePair (9Q, $8), (Sle ST)):
$B #eclePair ($Q, SR) SA + $B Iklerair $T).85 SSA
IGNORE (GNORE_BOUND HOUND_ROLE, PAIRS: $A credicate wtt.tewwwchhoonnolleeeaaa.. ($x, $Y) + SA
SENORE_DEPENDENCE COSOIDENNCYDDPPPNGGG.G DROPPING:
DropDeppeddnnc (6X) + Sx
MREDICATE__NNEIFTCC
Role ($Q, $P), Role SP)
ERolePair ($Q, Predicate) (se 7 #koleFair (Predicaat,, SB).SA +
RolePair ($C, $R) .A
(17 inference rulcs total)
M.3 RESOLUTION RULES
CONJUNCTION WITHOUT ENTITY:
def2sparq1 ($x n $Y, $V1) de defaapa ($X, SV1) def2sparg) (SY, $v1)
37

---

Published as a conference paper at ICLR 2020
ENTITY MID:
ent2sparql (Entity (6X))
GET_SPECI SEECSPPCCIAIISIOONNSS
set_specializationn (9X) 'SELECT DISTINCT ' get_ (6x, new_var (8V0))
WHERE (Sf, get_var $VO)) "
GET VAR CONJUNCTION.
ger_var ($X $Y, $V1) + shared verreed_vrrieeee var (get_var (SX, get_var (V1)),
var (SY, get_var ($X, (V1)))
GET VAR RELATION:
get_var (X, SVL) - SV1
GET VAR TYPE:
TresbaseTypeMappiing (5X, SF) get_var (SX, $V1) + $V1
PROPERTY MAPPING:
wtwpoasserrppetttttppppp (SR, $F) role2sparql ($R)
$F
RELATION MAPPPING WITHOUT WITHOUT_EXCLUSS EXCLUSION.
MentxeelusveRRoeePirr re12sparq1 (sx, $R, $Y) sx role2sparql (SR) SY
RELATION ENTNTY:: def2sparq1 (ESR.SX, SV1) re12sparg1 (SVI, SR, ent2sparg] (8X)
SHARED :AR: shared_var (5x, $X)
SPECIALIZATION_OOM TYPE:
def2sparq1 (5x, $V1) sV1 type?sparg] (9X)
TYPE_MAPPING
yrrebbaselyyeaaappingg.. (SX, SF): type2sparql ($X)
$F
(21 resolution rules total)
M.4 KNOWLEDGE RULES
BoundRolePairs (DirectingFinm, RolePair (Predicate,, Agent),
RoleFair FilmDirector)
RolePair (Predicate, Undergoer), RoleFair DirecteaFilm)
+ (Drrraooeeeeaaasieirtretitiaeee
tound catew wat.wa thsoondRoleePard (RolePair (objectHaver, htwp
(ObjectHaver, Object), Releeair,,redicate,, Undergcer)), RolePair (0bePair Object), (Preicatt,,e Undergoer))
(Rolepair (Bubject,, jubjectHaver), RolePair (Agent, Predicate)), RolePair (Subject, (Agent, Predicate))
+
SubjectHaver), RolePair (Agent,
(Roleea + Freebbseerroperttkkppp.ngg (RolePair /FimmDirecoor, SirectedFilnt
ns: mas:fimm.ddrrccorffffl..
FrecbaseTyypoKappiing (Person, 'ns:people. pecople.person')
NonExxlussiveRolcearr (FiinDirector, DirectedFiim)
Role (Directtted:, pictiigg:1 igFilm)
Role (ollmiiiirrert,.r, Di Direct prectingPimm)
(194 knowledge nules total)
38


Reviews:
[{"review_id": "Skgd0wo0tS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper introduces a method for generating training/test data for measuring the model's ability of \"compositional generalization\" in complex compositional tasks/domains such as natural language understanding, visual understanding and other domains. \nThe idea of the proposed method is to essentially keep the \"atom\" distribution unchanged between the training and test data, but maximize the divergence between the \"compound\" distributions between them. \nThe authors have conducted a thorough and systematic experimentation, comparing the proposed approach with a number of other heuristic approaches for train test splits (such as random and input/output length, etc.) and using both a new large data set they generated (CFQ) and existing data set (SCAN). \nThe experimental results verify that using their method they can obtain train test data sets with uniform atom distributions with large divergence in compound distributions, and they find that there is a surprisingly large negative correlation between the accuracy of existing state-of-the-art learning methods and the compound divergence. \nThe data generation mechanism is systematic and involved, consisting of different categories of rules (logical form, grammar, rule application DAG's, etc.) and it would seem that the generation method/system and the generated data would be useful as benchmark data for the community. \nThe paper lacks technical novelty other than the training and test data generation approach, but having one available to the community with these apparently desirable characteristics as benchmark data for measuring complex, compositional generalization capabilities, and that could be invaluable to the research community. ", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A"}, "extra_text": {}}, {"review_id": "H1lWSY0fKH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary\n\nStrength:\n1. This topic studied in this paper is interesting and is helping to promote the following developing of algorithms with compositional generalization ability.\n2. The experimental results show the effectiveness of the proposed metric for measuring compositional diversity.\n\n\ncomments:\n1. How to control the trade-off between the atom and compositional divergence? It's interesting to show how different\ncompositional divergence can affect the performance of different models.\n2. Many previous works are proposed for improving the generalization ability of the seq2seq models[1]. More experiments need to\nbe conducted using these previous methods.\n\n[1]Compositional generalization in a deep seq2seq model by separating syntax and semantics\n", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "BJgDGC9RFB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper first introduces a method for quantifying to what extent a dataset split exhibits compound (or, alternatively, atom) divergence, where in particular atoms refer to basic structures used by examples in the datasets, and compounds result from compositional rule application to these atoms. The paper then proposes to evaluate learners on datasets with maximal compound divergence (but minimal atom divergence) between the train and test portions, as a way of testing whether a model exhibits compositional generalization, and suggests a greedy algorithm for forming datasets with this property. In particular, the authors introduce a large automatically generated semantic parsing dataset, which allows for the construction of datasets with these train/test split divergence properties. Finally, the authors evaluate three sequence-to-sequence style semantic parsers on the constructed datasets, and they find that they all generalize very poorly on datasets with maximal compound divergence, and that furthermore the compound divergence appears to be anticorrelated with accuracy.\n\nThis is an interesting and ambitious paper tackling an important problem. It is worth noting that the claim that it is the compound divergence that controls the difficulty of generalization (rather than something else, like length) is a substantive one, and the authors do provide evidence of this. At the same time, I think the authors could possibly do more to show that the trend in the plots in Figure 2 can't be explained by something else: for example, the authors could show that the length ratios remain constant as the compound divergence is varied.  I think it is also not necessarily clear how easily the notion of differing compound distributions generalizes to other types of tasks.\n\nPresentation-wise, much of the paper is clear and well written, though I think the discussion of weighted frequency distributions of compounds (top of page 3) could be clarified further, and in particular an example subgraph of a rule application DAG should be highlighted here. ", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: Main content:

Blind review #1 summarizes it well:

This paper first introduces a method for quantifying to what extent a dataset split exhibits compound (or, alternatively, atom) divergence, where in particular atoms refer to basic structures used by examples in the datasets, and compounds result from compositional rule application to these atoms. The paper then proposes to evaluate learners on datasets with maximal compound divergence (but minimal atom divergence) between the train and test portions, as a way of testing whether a model exhibits compositional generalization, and suggests a greedy algorithm for forming datasets with this property. In particular, the authors introduce a large automatically generated semantic parsing dataset, which allows for the construction of datasets with these train/test split divergence properties. Finally, the authors evaluate three sequence-to-sequence style semantic parsers on the constructed datasets, and they find that they all generalize very poorly on datasets with maximal compound divergence, and that furthermore the compound divergence appears to be anticorrelated with accuracy.

--

Discussion:

Blind review #1 is the most knowledgeable in this area and wrote "This is an interesting and ambitious paper tackling an important problem. It is worth noting that the claim that it is the compound divergence that controls the difficulty of generalization (rather than something else, like length) is a substantive one, and the authors do provide evidence of this."

--

Recommendation and justification:

This paper deserves to be accepted because it tackles an important problem that is overlooked in current work that is evaluated on datasets of questionable meaningfulness. It adds insight by focusing on the qualities of datasets that enable testing how well learning algorithms do on compositional generalization, which is crucial to intelligence.
Decision: Accept (Poster)