Grammar-Based Grounded Lexicon Learning
Authors: Jiayuan Mao
Freda Shi
Jiajun Wu
Roger P. Levy
Joshua B. Tenenbaum
Venue: NeurIPS 2021 Poster (2021)
Keywords: Grounded Language Learning
Combinatory Categorial Grammar
Compositional Generalization

Abstract: We present Grammar-Based Grounded Language Learning (G2L2), a lexicalist approach toward learning a compositional and grounded meaning representation of language from grounded data, such as paired images and texts. At the core of G2L2 is a collection of lexicon entries, which map each word to a tuple of a syntactic type and a neuro-symbolic semantic program. For example, the word shiny has a syntactic type of adjective; its neuro-symbolic semantic program has the symbolic form $\lambda x.\textit{filter}(x, \textbf{SHINY})$, where the concept SHINY is associated with a neural network embedding, which will be used to classify shiny objects. Given an input sentence, G2L2 first looks up the lexicon entries associated with each token. It then derives the meaning of the sentence as an executable neuro-symbolic program by composing lexical meanings based on syntax. The recovered meaning programs can be executed on grounded inputs. To facilitate learning in an exponentially-growing compositional space, we introduce a joint parsing and expected execution algorithm, which does local marginalization over derivations to reduce the training time. We evaluate G2L2 on two domains: visual reasoning and language-driven navigation. Results show that G2L2 can generalize from small amounts of data to novel compositions of words.

Grammar-Based Grounded Lexicon Learning
Jiayuan Mao MIT
Haoyue Shi TTIC
Jiajun Wu Stanford University
Roger P. Levy MIT
Joshua B. Tenenbaum MIT
Abstract
We present Grammar-Ban Based Grounded Lexicon Learning (G2L2), a lexicalist approach toward learning compositional and grounded meaning representation of language from grounded data, such as paired images and texts. At the core G2L2 is collection of lexicon entries, which map each word to tuple of syntactic type and a ceuro-symbolic semantic program. For example, the word shiny has a syntactic type of adjective; its neuro-symbolic semantic program has the symbolic form Ax.filter(x: SHINY), where the concept SHINY is associated with a neural network embedding, which will be used to classify shiny objects. Given input sentence, G2L2 first looks the lexicon entries associated with each token. It then derives the meaning of the sentence an executable neuro-symbolic program by composing lexical meanings based on syntax. The recovered meaning programs can be executed on grounded inputs. To facilitate learning in an exponentially- growing compositional space, we introduce joint parsing and expected execution algorithm, which does local marginalization over derivations to reduce the training time. We evaluate G2L2 on two domains: visual reasoning and language driven navigation. Results show that G2L.2 can generalize from small amounts of data novel compositions of words.
1 Introduction
Human language learning suggests several desiderata for machines learning from language. Humans can learn grounded and compositional representations for novel words from few examples. These representations grounded on contexts, such visual perception. We also know how these words relate with each other in composing the meaning of a sentence. Syntax-the structured, order-sensitive relations among words in sentence-is crucial in humans' learning and compositional abilities for language. According to lexicalist linguistic theories [30, 37, 9], syntactic knowledge involves a small number of highly abstract and potentially universal combinatory rules, together with large amount of learned information in the lexicon: rich syntactic type and meaning representation for each word.
Fig. illustrates this idea in visually grounded language acquisition setup. The language learner looks at a few examples containing the novel word shiny (Fig. la). They also have built-in, compact but universal set of combinatory grammar rules (Fig. 1b) that describes how the semantic program of words can be combined based on their syntactic types. The learner can recover the syntactic type of the novel word and its semantic meaining. For example, shiny is adjective and its meaning can be grounded on visually shiny objects in images (Fig. lc). This representation supports the interpretation of novel sentences in novel visual context (Fig. 1d).
In this paper, we present Grammar- Basedd Grounded Lexicon Learning (G2L2), a ncuro-symbolic framework for grounded language acquisition. At the core of G2L2 is collection of grounded lexicon entries. Each lexicon entry maps a word to (i) a syntactic type, and (ii) a neuro-symbolic semantic program. For example, the lexicon entry for the English word shiny has syntactic type of objset/objset: it will compose with another constituent type objset on its right, and produces a new
Correspondence to Jiayuan Mao: jiayuanm @du. Project page: http://g212.csai.mmii mit.edu.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Q: What's the color of the shiny thing? Cyan.
Forward Application:
How many shiny cubes are there?
X
Y:a = X:f(a)
Backward Application:
Y:a
XY:f = X:f(a)
Q: Are there any shiny objects? Yes.
Coordination:
X.g cONE X:f X:2..bbf...Mg...)
comnl(iler(ileeCUUBB)). SHINY)
Training Examples
b. Universal Combinatory Rules (CCG)
Weight Word Syntax
Semanties
Concept Embedding
0.99
shiny setiset fiterre SHINY)
SHINY
Ex: shiny cube : fibetfiberCUUBE, SHINY)
0.85
right sefsetiset
Àx Ay.eevela y. RIGHT) RIGHT
Ex: cubes right of the green object GREEN,, CUBE) RIGHT
Answer:
c. Learned Grounded Lexicons
d. Novel Contexts
Figure I: G2L2 learns from grounded language data, for example, by looking at images and reading parallel question-answer pairs. It learns collection of grounded lexicon entries comprised of weights, syntax types, semantics forms, and optionally, grounded embeddings associated with semantic concepts. These lexicon entries can be used to parse questions into programs.
constituent of syntactic type objset. For example, in Fig. 1d, the word shiny composes with the word cube and yields new constituent of type objset. The ceuro-symbolic semantic program for shiny has the form Xr. Ar..filterrr, SHINY), where SHINY is a concept automatically discovered by G2L2 and associated with a learned vector embedding for classifying shiny objects. G2L2 parses sentences based on these grounded lexicon entries and small set of combinatory categorial grammar [CCG; 36] rules. Given input question, G2L2 will lookup lexicon entries associated with each token, and compose these lexical semantic programs based on their syntactic types.
G2L2 takes a lexicalist approach toward grounded language learning and focuses on data efficiency and compositional generalization to novel contexts. Inspired by lexicalist linguistic theories, but in contrast to neural wetwork-based end-to-end learning, G2L2 uses a compact symbolic grammar to constraint how semantic programs of individual words can be composed, and focuses on learning the lexical representation. This approach brings us strong data efficiency in learning new words, and strong generalization to new word compositions and sentences with more complex structures.
We are interested in jointly learning these neuro-symbolic grounded lexicon entries and the grounding of individual concepts from grounded language data, such as by simultaneously looking at images and reading parallel question-answer pairs. This particularly challenging because the number of candidate lexicon entry combinations of sentence grows exponentially with respect to the sentence length. For this reason, previous approaches lexicon learning have either assumed an expert- annotated set of lexical entries [46] or only attempted to learn at very small scales [15]. We address this combinatory explosion with novel joint parsing and expected execution mechanism, namely CK C-Y-22, which extends the classic CKY chart parsing algorithm. It performs local marginalization of distributions over uub-programs to make the search process tractable.
In sum, our paper makes three specific contributions. First, we present the neuro-symbolic G2L2 model that learns grounded lexical representations without requiring annotations for the concepts to be learned or partial word meanings; automatically recovers underlying concepts in the target domain from language and experience with their groundings. Second, we introduce a novel expected execution mechanism for parsing in model training, to facilitate search in the compositional grammar- based space of meanings. Third, through systematic evaluation on benchmarks, visual reasoning in CLEVR [21] and language-drive driven navigation in SCAN [25]. we show that the lexicalist design of G2L2 enables learning with strong data efficiency and compositional generalization to novel linguistic constructions and deeper linguistic structures.
2 Grammar-Based Grounded Lexicon Learning
Our framework, Grammar-Based Grounded Lexicon Learning (G2L2) learns grounded lexicons from cross-modal data, such as paired images and texts. Throughout this section, we will be using the visual reasoning task, specifically visual question answering (VQA) as the example, but the idea itself can be applied to other tasks and domains, such as image captioning and language-drive driven navigation.

---

color
of
the
shiny
cube
Lexicon Entry Lookup
Visual Representation
Concept Embeddings
Ohj
SHINY
striabj
abjsetiobjser
objaet
Ohj
CUBE
Ixquerryss COLOR)
Axfiber(ys SHINY BlberCCURE)
Filter
Filter
Query
striobj
objset
Arqueryix, COLOR
CUBE)) SHINY)
Concept
CUBE
SHINY
COLOR
Outputs
querKflter(fleo CUBE), SHINY,, COLOR)
Selection: Obj1(0.9)
Selection: Ob)1(0.9)
Answer: GreentD
HI Chart Parsing
Ieuro Symbolly Prugram Execution
Figure 2: G21.2 parses the input sentence into executable neuro-symbolic program by first (I) lookup the lexicon entry associated with each word, followed by (II) computes the most probable parsing tree and the corresponding tree with chart parsing algorithm. The derived program be
grounded and executed on an image with a neuro-symbolic reasoning process [28] (III).
G2L.2 learns from a collection of VQA data tuples, containing an image, a question, and an answer to the question. In G2L2, each word type w is associated with one or multiple lexical entries, comprised of their syntactic types and semantic programs, Given the input question, G2L2 first looks up the lexicon entries associated with each individual token in the sentence (Fig. 2I). G2L2 then uses chart parsing algorithm to to derive the programmatic meaning representation of the entire sentence by recursively composing meanings based on syntax (Fig. 211). To answer the question, we execute the program on the image representation (Fig. 2III). During training, we compare the answer derived from the model with the groundtruth answer form the supervision for the entire system. No additional supervision, such as lexicon entries for certain words or concept labels, is needed.
2.1 Grounded Lexicon
At a high-level, G2L2 follows the combinatory cat- egorical grammar [CCG; 36] formalism to main- tain lexicon entries and parse sentences. Illustrated in Fig. 3, Each word (e.g., shiny) is associated e is a tuple comprised of syntax type syne (e.g.. ob- jset/objset), and a semantic meaning form sem! (e.g., A..Ax..fiiee(. SHINY)). sem!!) is a symbolic pro- gram represented in typed domain-specific language (DSL) and can be executed on the input image. Some programs contain concepts (in this case, SHINY) that can be visually grounded.
shiny
Syntax:
objsetiobjset
Example:
shiny
cube
objsettobjset
objset
with one or multiple entries. Each entry
Ax filtere,, SHINY)
filter(CUBE)
(t)
objset
fiterfiiterCUBB SHINYY
Semanties: Ax fifiterr( SHINY Example:
Concept Emb.
Typed domain specific language. G2L.2 uses DSL to represent word meanings. For the visual reasoning domain, we use the CLEVR DSL [21]. It contains object-level operations such as selecting all objects having particular attribute (e.g., the shiny objects) or select all objects having a specific relationship with certain object (e.g., the objects left of the cube). also supports functions that respond to user queries, such counting the number of objects or query a specific attribute (c.g., shape) of an object. The language is typed: most functions takes a set of objects or a single object as their inputs, and produce another set of objects. For example, the operation filter has the signature filter concept) >> objset and returns all objects that have concept (e.g., all shiny objects) in the input set.
Figure 3: Each word is associated with grounded lexicon, comprised of its syntactic type and neuro-symbolic semantic program.
Syntactic types. There two types of syntactic types in G2L2: primitive and complex." The primitive types are defined in the typed domain specific language (e.g., objset, int). A complex type, denoted as X/Y or X\Y, is functor type that takes argument of type Y and returns type X. The direction of the slash indicates word order: for X/Y, the argument Y must appear on the right, whereas in XYY, it must appear on the left. Note that X and Y can themselves be complex types,
object of
In some domains also conjunctions (CONJ) in the coordination rule.
3

---

which allows us to define functor types with multiple arguments, such as (XIY)/Z, or even functors with functor arguments (c.g. (ZIY)(ZZZ)).
In G2I.2, the semantic type of a word meaning (in the DSL.) together with a set of directional and ordering settings for its arguments (reflecting how the word and its arguments should be linearized in text) uniquely determines the word's syntactic type. For example, the syntactic type for word shiny is objset/objserr. It first states that shiny acts as function in meaning composition, which takes subprogram that outputs a set of objects (c.g...iteer (UUBE) as its argument, and produces anew program whose output is also set of objects, in this case, filter (fittr(CUBB)) SHINY) Second, states the direction of the argument, which should come from its right.
Neuro-symbolic programs. Some functions in the DSL involves concepts that will be grounded in other modalities, such as the visual appearance of an object and their spatial relationships. Taking the function filter an example, its secondary argument concept should be associated with the visual representation of objects. In G2L.2, the meaning of each lexicon entry may involve one more constants (called "concepts") that are grounded on other modalities, possibly via deep neural embeddings. In the case of shiny: Ax. Ax,ffittr(zz, SHINY). The concept SHINY is associated with a vector embedding in joint visual-semantic embedding space, following Kiros et al. [24]. During program execution, we will be comparing the embedding of concept SHINY with object embeddings extracted from the input image, to filter out all shiny objects.
Lexicon learning. G2L2 learns lexicon entries in the following three steps. (i) First, we enumerate all possible semantic meaning programs derived from the DSL.. For example, in the visual reasoning domain, a candidate program is Xr.ffiter(æ: ?). where ? denotes a concept argument. When we try to associate this lexicon entry the word shiny, the program is instantiated as Ax.ffllte( SH,Nl)))r,,NNNNY) SHINY), where SHINY is a new concept associated with a vector embedding. Typically, we set maximum number of arguments for each program and constrain its depth. We explain how we set these hyperparameters for different domains in the supplementary material. (ii) Next, for programs that have a primitive type, we use its semantic type as the syntactic type (e.g.. objset). For programs that are functions with arguments, we enumerate possible argument ordering of the arguments. For example, the program Äz. SHINY) SHINY) has two candidate syntactic types: objset/objser (the argument is on its right in language) and objseRobjser (the argument is on its left). (iii) Finally, we associate each candidate lexicon entry with learnable scalar weight T (.).. It is typical for a single word having tens or hundreds of candidate entries, and we optimize these lexicon entry weights in the training process. In practice, we assume no lexical ambiguity, i.e., each word type has only one lexical entry. Thus, the ambiguity of parsing only comes from different syntactic derivation orders for the same lexical entries. This also allows us to prune lexicon entries that do not lead to successful derivations during training.
2.2 Program Execution
Any fully grounded programs (i.e.. programs without unbound arguments) can be executed based on the image representation. We implement the Neuro-Symbolic Concept Learner INS-CL; 28] as our differentiable program executor, which consists of a collection of deterministic functional modules to realize the operations in the DSL. NS- (L-CL represents execution results in "soft" manner: in the visual reasoning domain, a set of objects is represented as a vector mask m of length N, where N is the number of objects in the scene. Each element, m, can be interpreted as the probability that object i is in the set. For example, the operation Xr.filter(x, SHINY) receives an input mask m and produces mask m' that selects all shiny objects in the input set. The computation has two steps: (i) compare the vector embedding of concept SHINY with all objects in the scene to obtain a mask m (SHInY), denoting the probability of each object being shiny; (ii) compute the glement-wise multiplication m' m O mESHINY which can be further used the input to other functions. In NS-CL, the execution result of any program is fully differentiable w.r.t. the input image representation and concept embeddings (e.g., SHINY).
2.3 Joint Chart Parsing and Expected Execution (CKY-E2)
G2L2 extends a standard dynamic programming algorithm for chart parsing (i.e., the CKY algo- rithm [22, 45, 10]) to compose sentence meaning from lexical meaning forms, based on syntax. Denote w; as the input word sequence. ei the j-th lexicon entry associated with word wi, and r(e)) the corresponding weight. Consider all possible derivation of the question {derivationg), k = 1,2,.... We define the following context-free probability distribution of derivations as:

---

Algorithm 1 The CKY-E² algorithm.
Span: right of the green object
Candidute Ac Sereuatess,,eee((((e (leee RIGHT)
Input: wa: input sentence; sentence length; e/: the j-th lexicon
entry associated with word ws; r(e)) ): lexicon weights.
Output: ezeg execution result of the possible derivations and their weights (emre))
Relate
1: for i 4-400 0 to L 1 do
arg?
Filter
RIGHT
2:
Initialize dp(s, i I] with lexicon entries et and weights r(e,)
3: end for
GREEN
4: for length +- to do
Candidute
5:
for left +- 0) to I. length do
Av (elee (ibe(ORRJECT), GREEN), RIGHTT)
6:
right <- left + length
7:
for k <- left empty list
Leftt, right
Relate
8:
right do
Try to combine nodes in Ltete,,, k] and dp[k, right] Append successful combination to dp dt/left, right] 11: end for
9:
arg?
Relate
RIGHT
10:
Filter
Filter
GREEN
end for EXPECTEDEXEECUTION right))
13:
THE OBJECT
14:
end for
15:
procedure EXPEECTEDEXECCTTIONN list of derivations)
Figure 4: An illustrative exam- ple of two semantic programs that can be merged by comput- ing the expected execution results of two subtrees (highlighted in gray). Both subtrees outputs a vector of scores indicating the ob- jects being selected.
16: while y E are identical except for subtrees of the
type do
17:
Create from x and y by computing the expected execution results for non- non-identical subtrees
18:
7(2) r(x) + ((y)
19:
Replace and y with
while
21: end procedure
p(derivations) x exp
Σ
7
T(e)
eEderivation;
That is, the probability is exponentially proportional to the total weights r(e) of all lexicon entries e E derivation, used by the specific derivation.
A straightforward implementation to support joint learning of lexicon weights and neural modules (c.g..filtterzz. SHINY)), is to simply exccute all possible derivations on the input image, and compare the answer with the groundtruth. However, the number of possible derivations grows exponentially as the question length, making such computation intractable. For example, in SCAN [25], each word has 178 candidate lexicons, and the number of lexicon combination of sentence with 5 words will be 1785 se 10" To address this issue, we introduce the idea of expected execution, which essentially computes the "expected" execution result of all possible derivations. We further accelerate this process by taking local marginalization.
Our CKY-E2 algorithm is illustrated in Algorithm. 1. It processes all spans [left, right) sequentially ordered by their length. The composition for derivations of [left, right) has two stages. First, enumerates possible split point & and tries to combine the derivation of [left, k) and [K, right). This step identical to the standard CKY parsing algorithm. Next, if there are two derivations x and y of span j). whose program structures are identical except for subtrees that can be partially evaluated (i.e., does not contain any unbounded arguments), we will compress these two derivations into one, by marginalizing the execution result for that subtree.
See the example from Fig. Two programs have the identical structure, except for the second argument to the outer-most relate operation. However, these sub-trees, highlighted in gray, can be partially evaluated on the input image, and both of them output vector of scores indicating the objects being selected. Denote 71 and 72 as the weight associated with two derivations, and and d2 the partial evaluation results (vectors) for two subtrees. We will replace these two candidate meaning form with
== Xr.relate v', RIGHT), where v' = T1 + 72
T(2) == T1 T2
Ta 72
5

---

We provide additional running examples of the algorithm in the supplementary material.
Complexity. Intuitively, once we have determined the semantics of constituents in the question, the actual concrete meaning form of the derivation does not matter for future program execution, if the meaning form can already be partially evaluated the input image. This joint parsing and expected execution procedure significantly reduces the exponential space of possible parsing to polynomial space w.r.t. the number of possible program layouts that can not be partially evaluated, which, in practice, is small. The complexity of CKY-E2 is polynomial with respect to the length L of the sentence, and M the number of candidate lexicon entries. More specifically, O(LMM), where O(L") comes from the chart parsing algorithm, and the number of derivations after the expected execution procedure is O(M). ). This result is obtained by viewing the maximum arity for functor types being a constant (e.g., 2). Intuitively, for each span, all possible derivations associated with this span can be grouped into 4 categories: derivations of a primitive type, derivations of a 1-ary functor type, derivations of a 2-ary functor type, and derivations of a 2-ary functor type, with one argument binded. All these numbers grow linearly w.r.t. M. For detailed analysis please refer to our supplementary material.
Correctness. One can theoretically prove that, all operations in the program layout are commutative with the expectation operator, i.e., if E (Lf (x)] f (E [x]]), our CKY-E2 produces exact computation of the expected execution result. These operations include, tensor addition, multiplication (if tensors are independent), and concatenation, which cover most of the computation we will do in neuro- symbolic program execution. For example, for filter, taking the expectation over different inputs before doing the filtering is the same taking the expectation over the filter results of different inputs. However, there are operations such as quantifiers whose semantics are not commutative with the expectation operator. In practice, it is possible to still use the expected expectation framework to approximate. We leave the application of other approximated inference techniques as future work. We provide proofs and its connections with other formalisms in the supplementary material.
2.4 Learning
Our model, G21.2, can be trained in an end-to-end manner, by looking at images and reading paired questions and answers. We denote as a loss function that compares the output of program execution (e.g..a probability distribution over possible answers) and the groundtruth. More precisely, given all possible derivations derivation,, the image representation L, the answer A, and the executor E(, I). we optimize all parameters by minimizing the loss L:
L = Σ (p(derivations) (Edderivattonn 1), A))
In practice, we use gradient- based optimization for both the neural network weights in concept grounding modules and the lexicon weights
3 Experiment
We evaluate G2I.2 on two domains: visual reasoning in CLEVR [21] and language-driven navigation in SCAN [25]. Beyond the grounding accuracy, also evaluate the compositional generalizability and data efficiency, comparing G2L.2 with end-to-end neural models and modular neural networks.
3.1 Visual Reasoning
We first evaluate G2L2 on the visual reasoning tasks in the CLEVR domain [21]. where the task is to reason and answer questions about images. In our study, we use subset of CLEVR dataset, which does not include sentences that involve coreference resolution, and words with multiple meanings in different contexts. We add additional information on how we filter the dataset in the supplementary.
Setup. Instead of using manually defined heuristics for curriculum learning or self-paced learning as in previous works [28, 26], we employ curriculum learning setup that is simply based on sentence length: we gradually add longer sentences into the training set. This helps the model to learn basic words from very short sentences (6 words), and use the acquired lexicon to facilitate learning longer sentences (20 words). Since CLEVR does not provide test set annotations, for all models, we held out 10% of the training data for model development and test them on the CLEVR validation split.
Baselines. We compare G2L.2 with 4 baselines. (1) MAC [19] an end-to-end approach based on attention. (2) TbD-Net [29] uses a pre-trained semantic parser parse the question into symbolic

---

Standard
Compositional Generalization Depth
Model
Prog? Concept?
10%
100%
purple
right of
count
MAC [19]
N/N
N/N
85.39
98.61
97.14
90.85
54.87
77.40
TbD-Net [29]
Y/Y
N/N
44.52
98.04
89.57
49.92
63.37
53.13
NS-VQA [44]
Y/Y
Y/Y
98.57
98.57
95.52
99.80
81.81
50.45
NS-CL [28]
Y/N
Y/N
98.51
98.91
98.02
99.01
18.88
81.60
G2L2 (ours)
Y/N
Y/N
98.11
98.25
97.82
98.59
96.76
98.49
Table I: Accuracy on the CLEVR dataset. Our model achieves a comparable results with state-of- the-art approaches the standard training-testing split. It significantly outperforms all baselines on generalization to novel word compositions and to sentences with deeper structures. The best number in each column is bolded. 'he second column indicates whether the model uses program-based representation of question meaning and whether it needs program annotation for training questions. The third column indicates whether the model explicitly models individual concepts and whether needs concept annotation for objects during training.
program, and executes the program with a neural module network [5]. (3) Similarly, NS- VS-VQA [44] also parses the question into a symbolic program. It also extracts an abstract scene representation with pre-trained neural recognition models [17]. It executes the program based on the abstract scene representation. Both of the approaches require additional supervision for training the semantic parser, and NSSVVQA requires additional annotation for training the visual recogmition model. (4) NS-CL [28] jointly learns neural semantic parser and concept embeddings by looking at images and reading paired questions and answers. It requires the annotation for all concepts in the domain (c.g., colors and shapes). In contrast, G2L2 can automatically discover visual concepts from texts.
Results. Table summarizes the results. We consider any model that performs in the 90- range have more or less solved the task. Small differences in numeric scores in this range, such as the fact that NS-CL outperforms our model on the "purple" generalization task by 0.2%, are less important than the fact that our model far outperforms all competitors "count" compositional generalization and the "depth" generalization task, both of which all competitor models are far from solving.
We first compare different models on the standard with either 10% or 100% of the training data and evaluate them on the validation set. Our model achieves a comparable performance in terms of its aceuracy and data efficiency.
-tatiigg-tsttnng split. We train different models
Next, we systematically build three compositional generalization test splits: purple, right of. and count. The detailed setups and examples for these splits are provided in the supplementary. Essentially, we remove 90% of the sentences containing the word purple, the phrase right, and counting operations, such as how many.... ...? and what number of ...? We only keep sentences up to a certain length (6 for purple, 11 for right, and 8 for count). We make sure that each use case of these words appear in training questions. After training, containing these words. Overall, our model G2L2 outperforms all baselines on all three generalization splits. In particular, it significantly outperforms other methods the count split. The count split is hard for other method because it requires model to generalize to sentences with deeper structures, for example, from "how many red objects Note that, during training, all models have seen example use of similar structures such as "what's 's the shape of the red object" and "what's 's the shape of the red object right of the cube?"
test these models on the validation set with questions
there?" ?" to "how many red objects are right of the cube?" ?
Finally, we test generalization to sentences with deeper structures (depth). Specifically, we define the "hop number" of a question as the number of intermediate objects being referred to in order to locate the target object. For example, the "hop number" of the question "how many red objects are right of the cube?" ?" is 1. We train different models on O-hop and I l-hop questions and test them 2-hop questions. Our model strongly outperforms all baselines.
The results on the compositional generalization and depth splits yield two conclusions. First, disentangling grounded concept learning (associating words onto visual appearances) and reasoning (e.g., filtering or counting subsets of objects in given scene) improves data efficiency and generaliza- tion. On CLEVR, neuro-symbolic approaches that separately identify concepts and perform explicit reasoning (NS-VQA, NS-CL and G2L.2) consistently generalize better than approaches that do not (MAC, TbD). The comparison between TbD and NS-VQA informative: TbD fails on the "right of" task even in the case where the semantic parser is providing correct programs, while NS-VQA,
7

---

Simple
Compositional Generalization
Length
Model
10%
100%
jump
around right
seq2seq [38]
0.93:10.05
0.9911.01
0.00:10.00'
0.00110.00t
0.15
Transformer [42]
0.711:0.24
0.78
0.00100.00
0. 0.1010.08
0.02:10.01
GECA [3]
0.991:0.00
0.001
0.87:10.05
0.82.10.11
0.15.10.02
WordDrop [16]*
0.56=0002
0.62=0.02
0.52+0.02
0,70+0.06
0,18+
SwitchOut [43]*
0.99=0.01
0.99=0.01
0.98+
0.97
0. 0.17+0.02
SeqMix [16]*
0
0.89*
recomb-2 [2]
0,88+0.077
0.82++0.08
G2L2 (ours)
1.00=0000
1.00=0.00
1.00= 00
1.00++.000
1.00+0.000
Table Accuracy on the SCAN dataset, averaged across 10 valid runs when applicable, denotes standard deviation. The best number in each column is bolded. f: results taken from [2]; f: results taken from [16]. Both paper have only presented results on the compositional generalization split. *: applied after GECA. The results for GECA are based on the released implementation by the authors. All the models are selected with respect to the accuracy on the training set.
which uses the same parser but explicitly represents compositional symbolic concepts for reason- ing, succeeds in this task. Crucially, of the three neuro-symbolic methods, G2L2 achieves strong performance with less domain-specift knowledge than other methods: NS-VQA needs groundtruth programs; NS-CL needs the concept vocabulary; G2L2 requires neither. Second, our model the only one to perform well on the hardest "out-of-sample generalization tests: holding out "count" and generalizing to deeper embeddings. The other, easier generalization tests all have close neighbors in the training set, differing by just one word. In contrast, the length, depth and "count" tests require generalizing to sentences that differ in multiple words from any training example. They appear to require or at least benefit especially well from G21.2 's lexical-grammatical approach capturing meaning of complex utterances, with explicit constituent-leeel (as opposed to simply word-level) composition. We also provide in-depth analysis for the behavior of different semantic parsing models in the supplementary material.
3.2
Language-driven Navigation
The second domain we consider is language-driven navigation. We evaluate models on the SCAN dataset [25]: a collection of sentence and navigational action sequence pairs. There are 6 primitive actions: jump. look, walk, run, Iturn, and rturn, where an instruction turn left twice and run will be translated to Iturn iturn run. All instructions are generated from finite context-free grammar, so that we can systematically construct train-test splits for different types of compositional generalizations.
Setup. We use a beiting domain-specific language (DSL) for modeling the meaning of words in the SCAN dataset, of which the details can be found in the supplementary material. At a high level, the model supports three primitive operations: constructing a new constant string (consisting of primitive operations), concatenating two strings, and repeating the input string for number of times.
For G2L2, we generate candidate lexicons by enumerating functions in the string-editing DSL with up to 2 arguments and the function body has maximum depth 3. We also allow at most one of the argument being functor-typed, for example, WV/WVV. To handle parsing ambiguities, we use two primitive syntax types S and V, while both of them are associated with the semantic type of string. In total, we have 178 candidate lexicon entries for each word.
Baselines. We compare G2L2 to seven baselines. (1) Seq2seq [38] trains an LSTM-based encoder- decoder model. We follow the hyperparameter setups of [25]. (2) Transformer [42] is a 4-head Transformer-baase autoregressive seq2seq model. We tuned the hidden size (i.e., the dimension of intermediate token representations) within { 1100, 200, 400), as well as the number of layers (for both the encoder and the decoder) from (2, 4, 8). Other methods are based on different data augmentation schemes for training a LSTM seq2seq model. Specifically, (3) GECA augments the original training splits using heuristic span recombination rules; (4) WordDrop [16] performs random dropout for input sequence (while keeping the same label); (5) similarly. SwitchOut [43] randomly replaces an input token with random token from the vocabulary; (6) SeqMix [16] uses soft augmentation techniques following [47], which composes an "weighted average" of different input sequences; (7) recomb-2 [2] learns recombination and resampling rules for augmentation.
Results. We compare different models on three train-test splits. In Simple, the training and test instructions are drawn from the same distribution. We compare the data efficiency of various models
8

---

by using either 10% or 100% of the training data, and test them on the same test split. While all models can achieve a nearly-perfect accuracy with 100% training data, our model G2L2 shows advantage with only small amount of data. Next, in Compositional, we have held out the sentences containing certain phrases, such as jump and around right. For these held-out phrases, only valid non-contextual examples containing them jump in isolation and no example for around right) are available during training. During test, algorithms need to make systematical generalization of these phrases in novel contexts. Finally, in Length, all training examples have the action length less than or equal to 22, while that of a test example is up to 48. Our model consistently reach perfect performance in all considered settings, even on the cross- cooss-lengh& generalization task where GECA does not help improve performance. These results are consistent with the conclusions we derived on the CLEVR dataset. Specifically, data- auta--uugeetttionn techniques for SCAN can solve simple generalization tests jump, where tests all have close neighbors in the training set, differing by just one word) but not the hard ones (e.g., length, where test sentences can different in multiple words from any training examples).
Cases study. G2L2 is expressive enough to achieve perfect accuracy on the SCAN dataset: there exists a set of lexicon entries which matches the groundtruth in SCAN. However, our learning algorithm does not always converge on the correct lexicon, but when it fails, the failure can be identified based on training-set accuracy. So, we perform model selection based on the training accuracy for G2L2: after sufficient number of epochs, if the model hasn't 't reached perfect accuracy (100%). we re-initialize the weights and train the model again. Our results show that, among 100 times of training, the model reaches 100% accuracy 74% of the time. For runs that don't 't have 100% accuracy, the average performance is 0.94.
Since G2L directly learns human- interrraatrr lexicon entries associated with each individual words, we can further inspect the failure cases made by it when the training accuracy does not converge to O. We find that the most significant failure mode is the word and (e.g.. jump and run) and after (e.g., jump after run). Both of them are treated as connectives in SCAN. Sometimes G2L2 fails to pick the syntax type SVV/V over the type WV/V. The entry WV/V will succeed in parsing most cases (e.g.. jump and run), except that it will introduce ambiguous parsing for sentences such as "jump and run twice": "rtice".juupp jump and run twice vs. jump and run twice. Based the definition of the SCAN, only the first derivation is valid. In contrast, using SV// resolves this ambiguity. Depending on the weight initialization and the example presentation order, G2L.2 sometimes get stuck at the local optima of WV/VV. However, we can easily identify this by the training accuracies- G21.2 is able to reach perfect performance all considered splits by simply retraining with another random seed, therefore, only select those with 100% training accuracy as valid models.
4 Related Work
The lexicalist theories of syntax [30, 37, 9] propose that 1) the key syntactic principles by which words and phrases combine are extremely simple and general, and 2) nearly all of the complexity in syntax can be attributed to rich and detailed lexical entries for the words in the language. For example, whereas the relationship between the active and passive voice, e.g., "Kim saw a balloon" versus "A balloon was seen by Kim", was treated in pre-lexicalist theories as a special syntactic rule converting between the sentences, in lexicalist theories this relationship derives simply from the knowledge that the passive participle for the verb "see" is "seen," which interacts with knowledge of other words to make both the active and passive forms of the sentence possible. In lexicalist theories, the problem for the language learner thus becomes a problem of learning the words in the language, not a problem of learning numerous abstract rule schemas. The combinatory categorial grammar [CCG; 36) framework we use is a well-established example of lexicalist theory: there is a universal inventory of just three combinatory rules (Fig. la), but those rules can only be applied once richly specified lexical entries are learned for the words in a sentence. We believe that this lexicalistttheory approach is a particularly good fit to the problem of grounded language learning: the visual context provides clues to the word's meaning, and the word's grammatical behavior is tied closely to this meaning, making learning efficient.
Lexicalist theories.
Compositional generalization in NLP. Improving the compositional generalization of natrual lan- gauge processing (NLP) systems have drawn great attention recent years [8]. Most of the recent approaches towards this goal are mostly built on deep learning-based models. There are two rep- resentative approaches: building structured neural networks with explicit phrase-based structures or segments [35, 49, 39, 32]; and using data augmentation techniques [3, 16, 2]. However, these

---

approaches either rely on additional annotation or pretrained models for phrase structure inference or require domain -ppaii- heuristics in data augmentation. In contrast to both approaches, we propose to use combinatory grammar rules to constrain the learning of word meanings and how they compose.
Neural latent trees. CK is in spirit related to recent work using CK C-Y-style modules for inducing latent trees. However, our model is fundamentally different from works on unsupervised constituency parsing [23, 34J which use the CKY algorithm for inference over scalar span scores and those compute span representation vectors with CKY-style algorithms [27, 11, inter alia]. Our key contribution to introduce the expected execution mechanism, where each span is associated with weighted, compressed programs. Beyond enumerating all possible parsing trees as in [27], G2L2 considers all possible programs associated with each span. Our expected execution procedure works for different types (object set, integer, etc.) and even functor types. This makes our approximation exact for linear cases and has polynomial complexity.
Grammar-based grounded language learning. There have also been approaches for learning grammatical structures from grounded texts [33, 48, 20, 7, 31, 41J. However, these approaches either rely on pre-defined lexicon entries [7], or only focus on inducing syntactic structures such as phrase-structure grammar [33]. Different from them, G2L2 jointly learns the syntactic types, semantic programs, and concept grounding, only based on a small set of combinatory grammar rules.
Grammar- based and grounded language learning have also been studied in linguistics, with related work to ours studying on how humans use grammar as constraints in learning meaning [37] and how learning syntactic rules and semantic meanings in language bootstrap each other[1, 40]. However, most previous computational models have focused only on explaining small-scale lab experiments and do not address grounding in visual perception [13, 15]. In contrast, G2L.2 is neuro-symbolic model that integrates the combinatory categorial grammar formalism [36] with joint perceptual learning and concept learning, directly learn meanings from images and texts.
Neuro-symbolic models for language grounding. Integrating symbolic structures such as programs and neural networks has shown success in modeling compositional queries in various domains, including image and video reasoning [18, 29], knowledge base query [4], and robotic planning [6]. symbolic Nomain-specifie languages with neural network embeddings for
In this paper, visual reasoning in images and navigation sequence generation, following NS-CL [28]. However, in contrasts to using neural network-based semantic parser in the aforementioned papers, model G2L focuses on learning grammar-basee -based lexicon for compositional generalization in linguistic structures, such novel word composition.
5 Conclusion and Discussion
In this paper, we have presented G2L.,, a lexicalist approach towards learning compositional and grounded meaning of words. G2L2 builts in a compact but potentially universal set of combinatory grammar rules and learns grounded lexicon entries from a collection of sentences and their grounded meaning, without any human annotated lexicon entries. The lexicon entries represent the semantic type of the word, the ordering settings for its arguments, as well as the grounding of concepts in its semantic program. To facilitate lexicon entry induction in exponentially-gron -gowiing space, introduced CKY-E2 for joint chart parsing and expected execution.
Through systematical evaluation on both visual reasoning and language- driven navigation domains, we demonstrate the data efficiency and compositional generalization capability G2L2, and its general applicability in different domains. The design of G2L2 suggests several research directions. First, in G2L we have made strong assumptions on the -oneextindeependence of the lexicon entry as well as the application of grammar rules, the handling of linguistic ambiguities and pragmatics needs further exploration [14]. Second, meta-learning models that can leverage learned words to bootstrap the learning of novel words, such syntactic bootstrapping [15], is a meaningful direction. Finally, future work may consider integrating G2L2 with mrogram-sntthess algorithms [12] for learning of more generic and complex semantic programs.
Broader impact. The ideas and techniques in this paper can be potentially used for building machine systems that can better understand the queries and instructions made by humans. We hope researchers and developers can build systems for social goods based on our paper. Meanwhile, we are aware of the ethical issues and concerns that may arise in the actual deployment of such systems, particularly biases in language and their grounding. The strong interpretability of the syntactic types and semantic programs learned by our model can be used in efforts to reduce such biases.
10

---

Acknowledgements. This work is in part supported by ONR MURI 100014-16-1-2000 the Center for Brain, Minds, and Machines (CBMM, funded by NSF STC award CCF-1231216) the MIT Quest for Intelligence, Stanford Institute for Human-Centered AI (HAT), Google, MIT-IBM AI Lab, Samsung GRO, and ADI. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of our sponsors.
References
[1] Omri Abend, Tom Kwiatkowski, Nathaniel J Smith, Sharon Goldwater, and Mark Steedman, Bootstrapping language acquisition. Cognition, 164:116 143, 2017. 10
Ekin Akyürek, Afra Feyza Akyürek, and Jacob Andreas. Learning recombine and resample data for compositional generalization. /CIR, 2021. 8, 9
[3] Jacob Andreas. Good-enough compositional data augmentation. In ACL, 2020. 8, 9
[4] Jacob Andreas, Marcus Rohrbach, Trevor Darrell, and Dan Klein. Learning to compose neural networks for question answering. In NAACL-HLT, 2016. 10
Jacob Andreas, Marcus Rohrbach, Trevor Darrell, and Dan Klein. Neural module networks. In CVPR, 2016.7
[6] Jacob Andreas, Dan Klein, and Sergey Levine. Modular multitask reinforcement learning with policy sketches. In ICML, 2017. 10
[7] Yoav Artzi and Luke Zettlemoyer. Weakly supervised learning of semantic parsers for mapping instructions to actions. TACI, 2013. 10
[8] Marco Baroni. Linguistic generalization and compositionality modern artificial neural networks. Philosophical Transactions of the Royal Society B, 3735(191)220190307, 2020.
[9] Joan Bresnan, Ash Asudeh, Ida Toivonen, and Stephen Wechsler. Lexical-functional syntax. John Wiley Sons, 2016. 1,9
[10] John Cocke. Programming languages and their compilers: Preliminary New York University, 1969.
[11] Andrew Drozdov, Pat Verga, Mohit Yadav, Mohit lyyer, and Andrew McCallum. Unsupervised latent tree induction with deep inside-outside recursive autoencoders. In NAACL-HLT, 2019. 10
[12] Kevin Ellis, Catherine Wong, Maxwell Nye, Mathias Sable-Meyer, Lue Cary, Lucas Morales, Luke Hewitt, Armando Lezar-Lezama, and Joshua Tenenbaum. Dreamcoder: Growing generalizable, interpretable knowledge with wake-sleep bayesian program learning. arXiv:2000.0838/ 2020. 10
[13] Afsanch Fazly, Afra Alishahi, and Suzanne Stevenson. A probabilistic computational model of cross- situational word lcarning, Cognitive Science, 34(6):1017-1063, 2010. 10
[14] Michael C Frank and Noah D Goodman. Predicting pragmatic reasoning in language games. Science, 336 (6084)9998 998, 2012. 10
[15] Jon Gauthier. Roger Levy, and Joshua Tenenbaum. Word learning and the acquisition of syntactic- semantic overhypotheses. In CogSci, 2018. 2,
[16] Demi Guo, Yoon Kim, and Alexander Rush. Sequence-level mixed sample data augmentation. In EMNLP, 2020. 8,9
[17] Kaiming He, Georgia Gkioxari, Piotr Dollár, and Ross Girshick. Mask R- CNN. In ICCV, 2017. 7
[18] Ronghang Hu, Jacob Andreas, Marcus Rohrbach, Trevor Darrell, and Kate Sacnko. Learning reason: End-to-end module networks for visual question answering. CVPR, 2017. 10
[19] Drew A Hudson and Christopher D Manning. Compositional attention networks for machine reasoning. In ICLR, 2018. 6.7
[20] Lifeng Jin and William Schuler. Grounded PCFG induction with images. In AACL, 2020. 10

---

[21] Justin Johnson, Bharath Hariharan, Laurens van der Maaten, Li Fei-Fei, C Lawrence Zitnick, and Ross Girshick. CLEVR: A diagnostic dataset for compositional language and elementary visual reasoning. In CVPR, 2017. 3,
[22] Tadao Kasami. An efficient recognition and syntax-anale analysis algorithm for context-free languages. Coordi- nated Science Laboratory Report no. R-257, 1966. 4
[23] Yoon Kim, Chris Dyer, and Alexander M Rush. Compound probabilistic context-free grammars for grammar induction. In ACI, 2019. 10
[24] Ryan Kiros. Ruslan Salakhutdinov, and Richard S Zemel. Unifying visual-semantic embeddings with multimodal neural language models. arXiv:1411.2533 2014.
[25] Brenden Lake and Marco Baroni, Generalization without systematicity: On the compositional skills of sequence-to-sequenee recurrent networks. In ICML, 2018 2. 6,
[26] Qing Li, Siyuan Huang. Yining Hong. and Song- Song-Chun Zhu. A competence-awee curriculum for visual concepts learning via question answering. In ECCV, 2020. 6
[27] Jean Maillard and Stephen Clark. Latent tree learning with diffcrentiable parsers: Shift-reduce parsing and chart parsing. In ACL Workshop, 2018. 10
[28] Jiayuan Mao, Chuang Gan, Pushmeet Kohli, Joshua B Tenenbaum, and Jiajun Wu. The SymbolSy Concept Learner: Interpreting Scenes, Words, and Sentences From Natural Supervision. In ICLR, 2019. 3,
4, 6, 10
[29] David Mascharka, Philip Tran, Ryan Soklaski, and Arjun Majumdar. Transparency by design: Closing the gap between performance and interpretabiliiy in visual reasoning. In CVPR, 2018. 6, 7, 10
[30] Carl Pollard and Ivan Sag. Head- -Diven Phrase Structure Grammar. Chicago: University of Chicago Press and Stanford: CSLI Publications., 1994. 1,9
[31] Candace Ross, Andrei Barbu, Yevgeni Berzak, Battushig Myanganbayar, and Boris Katz. Grounding language acquisition by training semantic parsers using captioned videos. In EMNLP. 2018. 10
[32] Racid Saqur and Karthik Narasimhan. Multimodal graph networks for compositional generalization in visual question answering. In NewrIPS, 2020.
[33] Haoyue Shi, Jiayuan Mao, Kevin Gimpel, and Karen Livescu. Visually grounded neural syntax acquisition. In ACL, 2019. 10
[34] Tianze Shi, Ozan Irsoy, Igor Malioutov, and Lillian Lec. Learning syntax from naturally-occurring bracketings. In NAACL-HLT, 2021. 10
[35] Richard Socher, Alex Perelygin, Jean Wu, Jason Chuang, Christopher D Manning, Andrew Y Ng. and Christopher Potts. Recursive deep models for semantic compositionality over a sentiment treebank. In EMNLP, 2013. 9
[36] Mark Steedman. Surface structure and interpretation. MIT press, 1996. 2, 3, 9, 10
[37] Mark Steedman, The Syntactic Process. Camhridge, MA: MIT Press, 2000. 1, 9, 10
[38] Ilya Sutskever, Oriol Vinyals, and Quoe V Le. Sequence sequence learning with neural networks. In NeurIPS, 2014.
[39] Kai Sheng Tai. Richard Socher, and Christopher D Manning. Improved semantic representations from tree-structured long short-term memory networks. In ACL-IJCNLP, 2015.
[40] Marjorie Taylor and Susan A Gelman. Adjectives and nouns: Children's 's strategies for learning new words. Child Development, pages 41 1-419, 1988. 10
[41] Stefanie Tellex, Thomas Kollar, Steven Dickerson, Matthew Walter, Ashis Banerjee, Seth Teller, and Nicholas Roy. Understanding natural language commands for robotic navigation and mobile manipulation. In AAAI, 2011. 10
[42] Ashish Vaswani, Noam Shazeer. Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention all you need. In NewrIPS, 2017. 8
[43] Xinyi Wang, Hieu Pham, Zihang Dai, and Graham Neubig. Switchout: an efficient data augmentation algorithm for neural machine translation. In EMNLP, 2018. 8
12

---

[44] Kexin Yi. Jiajun Wu, Chuang Gan, Antonio Torralba. Pushmeet Kohli, and Joshua B Tenenbaum. Neural- Symbolic VQA: Disentangling Reasoning from Vision and Language Understanding. In NeurlPSS, 2018.
[45] Daniel H Younger. Recognition and parsing of context-free languages in time n3. Information and control, 10(2):189-208, 1967.
[46] Luke Zettlemoyer and Michael Collins. Learning context-dependee mappings from sentences to logical form. In ACL, 2009.
[47] Hongyi Zhang, Moustapha Cisse, Yann N Dauphin, and David Lopez-Paz. mixup: Beyond empirical risk minimization. In ICLR, 2017. 8
[48] Yanpeng Zhao and Ivan Titov. Visually grounded compound PCFGs. In EMNLP, 2020. 10
[49] Xiaodan Zhu, Parinaz Sobihani, and Hongyu Guo. Long short-term memory over recursive structures. In ICML, 2015.
Checklist
For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Section 5.
(c) Did you discuss any potential negative societal impacts of your work? [Yes] See Section 5.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [N/A]
(b) Did you include complete proofs of all theoretical results? [N/A]
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] For the main settings, see Section 3. More detailed can be found in the supplementary material.
(c) Did you report error bars (e.g., with respect to the random seed after running exper- iments multiple times)? [Yes] See Section 3.2. For CLEVR experiments, we follow the existing approaches and report the best performance selected based on training accuracies.
(d) Did you include the total amount compute and the type of resources used (e.g.. type of GPUs, internal cluster, cloud provider)? [Yes] Details can be found in the supplementary material.
4. If you are using existing assets code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]]
(b) Did you mention the license of the assets? [Yes] Can be found in the supplementary
material.
(c) Did you include any new assets either in the supplemental material or as a URL? [Yes]
(d) Did you discuss whether and how consent was obtained from people whose data you't 're using/curating? [N/A] The consent is associated with BSD license. (e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
13

---

(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
14


Reviews:
[{"review_id": "aQrh8W_B-rn", "reviewer": "Reviewer_mHT4", "summary": "This paper presents an end-to-end trainable neuro-symbolic method for learning grounded compositional semantic representations.The proposed approach maintains a lexicon which maps each word to a syntactic type and a symbolic program. It then follows the Combinatory Categorial Grammar formalism for parsing input queries and deriving their meanings as executable symbolic programs. To get around the problem of the exponentially growing number of possible derivations, the authors propose to merge derivations by local marginalization.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "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": "* This paper was very easy to read. The language is clear, and the diagrams and various examples make it quite easy to follow what's going on. The structure is logical and the supplementary material, combined with the source code, should provide enough information to reproduce the experiments. My only minor gripe is that I would have liked to se the statistics for the additional splits of section 3.1.\n* This work seems technically sound. In particular, the claims of training efficiency and generalization ability are well supported by the experimental results, and baselines are adequate. I would have additionally liked to see a transformer-based architecture for the experiments of section 3.2 – this was not one of the architectures tested by Lake and Baroni (2018), but it cannot really be ignored these days.\n* While the basic components of the proposed work are generally well known, their combination is novel and the \"expected execution\" technique makes the algorithm practically applicable.\n* I would expect this work to be of interest to the community. While the results on the CLEVR dataset may not establish a new state of the art, they can be considered comparable, and the proposed model displays a much stronger ability to generalize on certain types of tasks. Moreover, the proposed model is more data efficient as it requires less annotation compared to other methods.\n\nSome additional questions for the authors:\n* What's the complexity of CKY-E$^2$?\n* Could you please provide statistics for the various splits you created in section 3.1?\n\nA handful of minor typos:\n* line 108: has > have\n* lines 126-127: more more\n* line 128: in the case of word\n* line 183: program structure are identical\n* line 274: scheme > schemes", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I don't see any strong potential for negative societal impact of this work beyond what is mentioned in the paper.\n\nThe authors adequately address the limitations of this work, in particular by studying the failure cases in section 3.2.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "IeCmas6Kov-", "reviewer": "Reviewer_kovo", "summary": "This paper presents an interesting and, apparently, innovative approach to learn combined linguistic and visula lexicon. The linguistic part is used to guide the learning of the visual embeddings for words. In fact, it seems that syntax is driving the learning process by generating programs to be executed by the neural network.", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "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": "The major problem of this paper is in the description of the results, which is not convincing. In fact, it does not clearly demonstrate that using syntax to drive learning is a real added value for the kind of tasks authors experimented with. The two discussions are not directly referring to the two result tables. \n\nTable 1 seems to contain a lot of information. The proposed model outperforms other models only in some specific cases. This fact should be carefully analyzed. Maybe, it is analyzed in the current discussion, but it is extremely unclear. Current results may be used to justify the fact that syntax-driven learning is important and adds value. This should be the most important innovation of the paper.\n\nTable 2 is instead astonishing as the proposed method seems to be perfect with respect to the second task. This is not commented. Why this is the case? Moreover, there is a paragraph entitled \"Failure cases\", which clashes with Table 2 where failure does not exist. If this is not the correct interpretation, this section should be really reorganized. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No societal impact were analyzed.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "FpHeHGLrN5k", "reviewer": "Reviewer_sQTY", "summary": "The authors present a model evaluated on two tasks: a) visual question answering (with CLEVR), and b) sequence-to-sequence generation for navigation commands in the SCAN domain. The model represents and parses input akin to CCG, and the parsing is fully unsupervised. Although the results for the two tasks appear strong, the paper is difficult to follow at times, and I can not say with confidence that I fully understand whether the claims are substantiated.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "Strengths\n\n- Strong results for generalization in CLEVR, and otherwise competitive w/ baselines.\n- Strong results for SCAN.\n\nWeaknesses\n\n- The details for the joint visual-semantic embedding space are glanced over. This seems critical to understand how to generalize performance for unseen words.\n- The details for the NS-CL are not sufficient. Why is this component needed? How does it work (more specifically)?\n- The token representation is incredibly limited. Most natural language tasks would involve sense or type ambiguity. Even if this is not innate to the tasks considered, it seems possible to emulate by modifying the input space.\n- It’s not clear whether the modifications for CKY are novel. Is it so different from algorithms such as those used for unsupervised constituency parsing? For example, Maillard and Clark 2018.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See comment about token representation in main review.", "review_text": "", "extra_scores": {"ethical_concerns": "n/a", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "1qo4170K-Aw", "reviewer": "Reviewer_wcV1", "summary": "The authors develop a method for learning a lexicon for lexically driven parsing, applied to cross modal tasks such as VQA and Language Driven Navigation. They rely on a CCG-style approach for jointly addressing syntax and semantics -- items can be primitives of a given type, left operators, right operators, or combinations thereof. The structure and parameters of these lexical items are learned based on the data for the given task. Together, this method performs on par for most operations, and better for some (e.g. Count and Depth for VQA)\n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "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": "The goal of jointly learning a lexicon and parser parameters from just the training data is interesting, and the approach seems effective. Mostly it's on par with existing approaches, but some targeted evaluations suggest it is better at complex compositional phenomena.\n\nIt is worth noting that the authors have to zoom in to these complex phenomena to see benefits against other approaches, though.\n\nPrimarily, the authors learn a set of potential program structures, parameters for filters, and weights for lexical entries. These are assembled together into executable programs using a CKY-style algorithm, ensuring syntactic compatibility as well as aggressively executing shared program structures -- the ExpectedExecution operation. Personally I think this was interesting but not defined particulary cleanly -- it feels like a joint lexical and program parsing approach (synchronous grammar) could provide a cleaner formalism for enabling the sharing / summation across similarly structured programs.\n\nThe restriction to linearity over expectation in the computation space makes life easy, but is that fair? Would quantifiers and other complex operators used in language violate this linearity?\n\nThe limitations of the program structure are worth discussion. Each lexical item can vary in its combinatorial methods but not its parameters; it would be interesing to explore impact of multiple embedding represntaitons of a word, as well as sharing across related words -- shouldn't \"shiny\" and \"glossy\" have something in common?\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Minimal societal impact on this dataset.\n", "review_text": "", "extra_scores": {"ethical_concerns": "Minimal ethical concerns.\n", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The submission introduces a novel neuro-symbolic approach to solving cross-modal tasks. The main contribution is to learn a lexicon in which words both have syntactic types and grounding in neural programs, and showing how to efficiently train by computing an "expected execution" over many possible parses. Results are promising on the SCAN and CLEVR datasets, particularly in terms of compositional generalization.

Three of the reviewers lean towards acceptance. Reviewer kovo raises two reasonable concerns about the presentation of the results, but I think that the authors have addressed these adequately in their response. I think the submission offers an innovated new approach, and lean towards acceptance.


Decision: Accept (Poster)