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
Ixquerrys 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 (fiter(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,,NINNY) 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 Cereuatess,,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+t.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-snnthess 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": "HZs_SPKAEYT", "reviewer": "Reviewer_MH2M", "summary": "The paper presents a lexicon learning approach that learns to associate lexical items with \"neural embeddings\". \nIt does this by exploiting a given CCG grammar and learning the lexical itams\nResults are tested on a visual reasoning and a language-driven navigation task\nThe main contribution of the paper is a specific joint parsing and execution algorithm that helps with training times.\n", "questions": "", "limitations": "", "rating": 5, "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": "\nStrength\n\nCombining traditional parser with neural grounding is a very interesting research topic.\n\nThe approach is quite successful compared to baselines in the navigation domain and on some generalization tests in the visual reasoning domain.\n\n\nWeaknesses\n\nThe parser is given in this system. I don't think that is the case for baselines MAC, NS-VQA, NS-CL. That makes the comparison to prior work somewhat weak. As you essentially add very strong biases with the given parser.\nIt then is somewhat surprising that the performance of the system is not so convincing compared to baselines except for generalization in the visual reasoning domain\n\nIn the visual reasoning domain - authors demonstrate that the approach is superior to baselines primarily with respect to depth. However, I think that is almost obvious since the parser should be doing a lot of the work here and that is given as a prior.\n\nIt's not clear what is the impact of the curriculum\n\n\n\nComments\n\nL79 \"to to\"", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "YES", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "GnmSHO1J6k", "reviewer": "Reviewer_Wq9E", "summary": "This paper proposes a very interesting framework of grammar and lexicon learning where lexical entries are grounded with visual image question answering.  The experiments are conducted and show the comparative performance of the proposed method to the state-of-the-art baselines.", "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": "The overall idea looks to be quite interesting, and the experimental results show the effectiveness of the proposal.\nOn the other hand, there are a number of points that are difficult to understand.\n\n- How are the groundings between the image data and language expression provided?  Or, in what way the visual information is encoded and given?  Are the objects in the image represented by vectors as well?  How are their initial representations given?\n\n- What are the set of primitives in the domain-specific language?  It looks \"filter\", \"relate\", and \"query\" are some of them.  Are there any other semantic functions?  Is such a set of primitive functions define for each specific task or domain?\n\n- There are some lexical entries corresponding to the functional words such as prepositions and determiners.  How are they handled in the proposed framework?  While they do not have semantic information, they may have important syntactic information and are usually represented by complex category types.  It was a bit puzzling that such words are neglected in Figure 2 and still the derivation trees are constructed.\n\n- It is not clear how the initial values are assigned to the lexical entries.\n\n- Figure 4 is difficult to understand.  It is not clear if the gray parts in two candidates cover the same span in a given sentence.  More explanation is necessary.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Please start with defining the primitives or initial representations of words and images.  It is not clear what are initially defined and given.\n\nWhat about the scalability of the proposed method?  If it handles a small world with some objects, it will be fine.  However, there can be a number of different objects and regions and many properties and relations between them.  Is the proposed method feasible to such a more realistic situation?", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6 hours"}, "extra_text": {}}, {"review_id": "8kSSi1iZcr-", "reviewer": "Reviewer_45Px", "summary": "This paper introduces a new method, G^2L^2 (Grammar-Based Grounded Lexicon Learning).\n\nThe task is CLEVR: https://cs.stanford.edu/people/jcjohns/clevr/ (and SCAN)\n\nFor CLEVR, inputs are pictures + questions such as:\n\nQ: Are there an equal number of large things and metal spheres?\n\nQ: What size is the cylinder that is left of the brown metal thing that is left of the big sphere?\n\nQ: There is a sphere with the same size as the metal cube; is it made of the same material as the small red sphere?\n\nQ: How many objects are either small cylinders or red things?\n\nOutputs are simple answers that can be scored with simple mechanisms such as string matching.\n\nAccording to Table 1, the proposed method is about as good as some others in the literature (NS-VQA, NS-CL) on the standard task, but if we restrict ourselves to some interesting subcases such as the last two columns, the proposed method is considerably better.\n\nThe proposed method starts with NS-CL, but adds the lexicalist hypothesis, a linguistic framework that was popular a few decades ago (the HPSG reference is from 1994, and the Bresnan reference is even more recent, but Wikipedia traces the history back to the 1950s https://en.wikipedia.org/wiki/Lexicalist_hypothesis#History).   I suspect there is even more history than that, but nevertheless, for this audience, it may be more helpful to provide more tutorial background.  What is the lexical hypothesis, and how does it relate to this task?\n\n", "questions": "", "limitations": "", "rating": 5, "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": "This paper is hard to read.  It expects that the reader is familiar with quite a bit of difficult background.  The paper does not say much about CLEVR, or the baseline methods, or the main contribution (how the lexicalist hypothesis can improve over the baselines, at least in some interesting special cases such as the last two columns of Table 1).\n\nI think this paper would have more impact if it was more accessible to a larger audience.  It is unlikely that people that know about vision and deep nets will also know about the lexicalist hypothesis, and vice versa.  Can this paper be written in a way that could work with an audience that knows about some of this background, but not not all of it?\n\nI happen to be reasonably well-informed on much of the background, though I did spend some time chasing down references for some of these topics.  It is nice to see a connection between all these different interdisciplinary topics, but I would like to see more discussion on why the proposed method does as well as it does on the last two columns of Table 1?  \n\nIf I wanted to be nasty, I could suggest that there are so many ways to split the data that one could always find a few that would make almost any solution look good.  I suspect that count and depth are fundamentally different from purple and right-of.  Suppose we have k objects, and each one has just a single color.  Then we can address simple properties like purple (color), but treating each object one-at a time.  Relations like right-of are slightly more complicated.  That might involve looking at pairs of objects.  Thus the search space is perhaps choose(k,1) for colors, and choose(k,2) for properties of pairs of objects like right-of.  I suspect the search space for counting is fundamentally more difficult, especially if we need to understand the implicit argument which probably involves some notion of equivalence relations.  \n\nDepth seems to be even more abstract.  I have to admit that I have read L252-256 a few times, but I still do not understand the definition of \"hop number\".  \n\nI suspect the main point is not so much about the lexicalist hypothesis, but more a statement about standard benchmarks such as CLEVR and SCAN.  It appears that there are certain aspects of these tasks that make them too-easy or too-hard for currently popular methods.  The field would benefit from a deeper understanding of these benchmarks.  Can we identify aspects of the tasks that popular methods are doing too well on, or where there are opportunities for improvement?  In some cases, simple patches such as rules may improve results by quite a bit.  When that happens,  what should we conclude?  Should we ignore the result because rules are out of fashion?  Or should we take it as a challenge to find a way to generalize popular methods to do better on subcases such as count questions and 2+ hop questions? \n\nHow realistic are these benchmarks?  Should we care about count questions?  2+ hop questions?  I thought the SCAN benchmark was introduced to make a theoretical point about the ability of certain methods to address certain questions involving compositionality.   Now that many methods appear to have solved that task, should we move on? \n\nPerhaps the point is more about representation than the lexicalist hypothesis.  It makes sense to model words as predicates and arguments.  Categorical grammar can be viewed as a generalization of this.  These days, there is more interest in end-to-end training, and less interest in representation, but I could believe there are lots of opportunities for improvement involving representation.  But given the current popularity of end-to-end systems, the argument for representation needs to be much stronger than what was expected when there was more interest in representation, and less interest in end-to-end methods.\n\n\ntypo:\nCaption table 1: Our model achives a comparable results\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "NA", "review_text": "", "extra_scores": {"ethical_concerns": "NA", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "0W4Cv2srZZk", "reviewer": "Reviewer_JDyB", "summary": "This paper proposes a fusion of CCG-based approach and concept embedding modeling to introduce a neuro-symbolic approach for grounded lexicon learning. The experiments are done on closed-world and relatively closed-language datasets to empirically test the effectiveness of the proposed method, especially on compositional generalization. Based upon a lexicon of types and attributes described in a task specific DSL (Domain Specific Language), and using the training signal from downstream task (visual QA and instruction parsing), this approach learns concept embeddings and syntactic roles of types in surface form of text. The CCG parse is used to define ann executable program and the program itself requires concept embeddings for execution.\n\nA fairly straightforward modification to the standard CKY algorithm, based upon subtree merging of same types is proposed to compute the derivations and weights in a tractable manner. The results show improvements over relevant baselines in terms of length and syntactic depth generalization. ", "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": "Positives:\n-- The paper for the most part is clearly written with ample motivation and example (except the CKY section as mentioned below).\n\n-- The empirical results convincingly show the effectiveness of the proposed approach on the nested-structure and length generalization.\n\n-- The baselines are relevant and the two sufficiently dissimilar tasks strengthen the claims about generalizability of the proposed approach.\n\nNegatives:\n-- The method seems difficult to scale to free-form language in an open-world setting. Access to a DSL is assumed an the method does rely on types, attributes, and program definitions supported in the DSL. The approach is tested on limited vocabulary which is further pruned to eliminate lexical ambiguity and only preserve syntactic ambiguity. However, with such a closed-world/language setup, the challenges associated with processing free-form natural language are not addressed.\n\n-- The CKY section is difficult to read. Derivation_k is not explained anywhere. What is k here? Similarly, the first equation in the section does not seem correct--either it is a very strong assumption, or the equation is poorly written/explained. I checked the appendix and the equations in the appendix make more sense regarding \\exp and \\sum.\n\n-- I am still confused about the impact of expected execution. Don't we need the highest scoring derivation (or top-k derivations), both during learning (as described in the loss), and inference. The expected quantities involving marginalization do not appear in either the loss or decoding objectives. It appears that the method is a hybrid of enumeration of derivations and computing expected quantities (since this execution is limited to particular subtrees). The impact of this modeling choice should be discussed in more detail.\n\n-- In some settings, the proposed approach trails other baselines on the CLEVR dataset. Is there a systematic reason for this? Or can it just be attributed to unsuccessful grammar induction?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, they have sufficiently addressed broader societal impact of their work.", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presents a novel CCG-based neuro-symbolic framework for grounded language tasks like VQA. Experiments are conducted on both VQA (CLEVR) and navigation tasks. Results demonstrate marked improvements in generalization to particularly challenging question types (e.g. counting in CLEVR). Overall, reviewers are borderline -- half in favor of acceptance, half weakly against.    Several reviewers praised the paper's clarity and well-articulated motivations. Several also viewed the demonstrated improvements to generalization as impactful, and found the proposed training method (which helps address computational costs associated with latent derivations) to be a valuable contribution. However, reviewers also raised several important concerns. First, one reviewer raised concerns about the potential rigidity of the proposed formalism (e.g. that aspects of the grammar must be specified in advance) -- though authors have pointed out how simple and generalizable (e.g. between VQA and navigation tasks) the pre-specified component is. Second, one reviewer was concerned that the main hypothesis of the paper -- that taking a lexicalist approach to grounded language tasks may offer benefits -- could be better motivated, analyzed, and justified. The same reviewer raised a broader, but related point about the readability of the current draft. The draft, while clear, is quite dense and depends to some extent on both strong familiarity with deep learning and specific branches of linguistics, potentially limiting its audience and impact. Taking these points in balance, I lean towards acceptance. The paper does present a novel and well-motivated approach that may, apart from the this specific application, have influence on others working with models that combine discrete syntactic formalisms with neural representations. The paper does demonstrate strong improvements in generalization to unseen question types, matching the initial motivation of the general shape of approach. However, I strongly agree that final revisions should include a better survey and introduction to the relevant linguistic concepts and, perhaps even more importantly, more in depth discussion of how these specific results relate to the lexicalist hypothesis, around which the framework is centered. 
Decision: Accept (Poster)