---
abstract: 'Compositional generalization is a basic mechanism in human language learning, but current neural networks lack such ability. In this paper, we conduct fundamental research for encoding compositionality in neural networks. Conventional methods use a single representation for the input sentence, making it hard to apply prior knowledge of compositionality. In contrast, our approach leverages such knowledge with two representations, one generating attention maps, and the other mapping attended input words to output symbols. We reduce the entropy in each representation to improve generalization. Our experiments demonstrate significant improvements over the conventional methods in five NLP tasks including instruction learning and machine translation. In the SCAN domain, it boosts accuracies from 14.0% to 98.8% in Jump task, and from 92.0% to 99.7% in TurnLeft task. It also beats human performance on a few-shot learning task. We hope the proposed approach can help ease future research towards human-level compositional language learning. Source code is available online[^1].'
author:
- |
    Yuanpeng Li, Liang Zhao, Jianyu Wang, Joel Hestness\
    Baidu Research\
    <span>{yuanpeng16,kristen11@example.com</span>\
    <span>{zhaoliang07,kristen11@example.com</span>
bibliography:
- 'emnlp-ijcnlp-2019.bib'
title: Compositional Generalization for Primitive Substitutions
---

Introduction
============

Humans learn language in a flexible and efficient way by leveraging *systematic compositionality*, the algebraic capacity to understand and produce large amount of novel combinations from known components @chomsky1957syntactic [@montague1970universal]. For example, if a person knows how to "step", "step twice" and "jump", then it is natural for the person to know how to "jump twice" (Figure \[fig:problem\]). This compositional generalization is critical in human cognition @minsky1986society [@lake2017building], and it helps humans learn language from a limited amount of data, and extend to unseen sentences.

![ Problem illustration. If a person knows how to "step", "step twice" and "jump", then the person should know how to "jump twice". Although this is straightforward for humans, it remains an open problem to equip machines with such ability.<span data-label="fig:problem"></span>](figs/problem3.png){width="35.00000%"}

In recent years, deep neural networks have made many breakthroughs in various problems @lecun2015deep [@krizhevsky2012imagenet; @yu2012asr; @he2016resnet; @wu2016google]. However, there have been critiques that neural networks do not have compositional generalization ability @fodor1988connectionism [@marcus1998rethinking; @fodor2002compositionality; @marcus2003algebraic; @calvo2014architecture].

\[t\]

  ------------------------------------------------ ----------------------------------
  **jump**                                         JUMP
  run after run left                               LTURN RUN RUN
  look left twice and look opposite right          LTURN LOOK LTURN LOOK RTURN
                                                   RTURN LOOK
  **jump** twice after look                        LOOK JUMP JUMP
  turn left after **jump** twice                   JUMP JUMP LTURN
  **jump** right twice after **jump** left twice   LTURN JUMP LTURN JUMP RTURN JUMP
                                                   RTURN JUMP
  ------------------------------------------------ ----------------------------------

  ----------------------------------------------------- ----------------------------
                                                        
  **turn left**                                         LTURN
  run thrice and jump right                             RUN RUN RUN RTURN JUMP
  look left thrice after run left twice                 LTURN RUN LTURN RUN LTURN
                                                        LOOK LTURN LOOK LTURN LOOK
  look twice and **turn left** twice                    LOOK LOOK LTURN LTURN
  **turn left** thrice and **turn left**                LTURN LTURN LTURN LTURN
  **turn left** twice after look opposite right twice   RTURN RTURN LOOK RTURN
                                                        RTURN LOOK LTURN LTURN
  ----------------------------------------------------- ----------------------------

Our observation is that conventional methods use a single representation for the input sentence, which makes it hard to apply prior knowledge of compositionality. In contrast, our approach leverages such knowledge with two representations, one generating attention maps, and the other mapping attended input words to output symbols. We reduce each of their entropies to improve generalization. This mechanism equips the proposed approach with the ability to understand and produce novel combinations of known words and to achieve compositional generalization.

In this paper, we focus on compositinal generalization for primitive substitutions. We use Primitive tasks in the SCAN @lake2018generalization dataset—a set of command-action pairs—for illustrating how the proposed algorithm works. In a Primitive task, training data include a single primitive command, and other training commands do not contain the primitive. In test data, the primitive appears together with other words. A primitive can be "jump" (Jump, see Table \[table:example\_jump\] for examples) or "turn left" (TurnLeft, see Table \[table:example\_left\] for examples). These tasks are difficult because "jump" (or "turn left") does not appear with other words in training. A model without compositionality handling will easily learn a wrong rule such as "any sentence with more than one word should not contain the 'jump' action". This rule fits the training data perfectly, and may reduce training loss quickly, but it does not work for test data. In contrast, our algorithm can process a sentence such as "jump twice after look" correctly by generating a sequence of three attention maps from function representation and then a sequence of actions "LOOK JUMP JUMP" by decoding the primitive representation from the attended command words (see the example in Figure \[fig:simple\_model\]). Besides Primitive tasks, we experiment on more tasks in SCAN and other datasets for instruction learning and machine translation. We also introduce an extension of SCAN dataset, dubbed as SCAN-ADJ, which covers additional compositional challenges. Our experiments demonstrate that the proposed method achieves significant improvements over the conventional methods. In the SCAN domain, it boosts accuracies from 14.0% to 98.8% in Jump task, and from 92.0% to 99.7% in TurnLeft task. It also beats human performance on a few-shot learning task.

Approach
========

\[t\] ![image](figs/intuition2.png){width="90.00000%"}

In compositional generalization tasks, we consider both input $X$ and output $Y$ have multiple components that are not labeled in data. Suppose input has two components $X_1$ and $X_2$, and output has two components $Y_1$ and $Y_2$, then we can define compositional generalization probabilistically as follows. In training, $$\begin{aligned}
    & P(X_1) > 0 \text{ and } P(X_2) > 0, \\
    & P(X_1, X_2) = 0, \\
    & P(Y_1 | X_1) \text{ and } P(Y_2 | X_2) \text{ are high.}\end{aligned}$$ In test, $$\begin{aligned}
    & P(X_1, X_2) > 0, \\
    & P(Y_1, Y_2 | X_1, X_2) \text{ is predicted high.}\end{aligned}$$ We expect this is possible when we have prior knowledge that $Y_1$ depends only on $X_1$ and $Y_2$ depends only on $X_2$. $$\begin{aligned}
    & P(Y_1 | X_1, X_2, Y_2) = P(Y_1 | X_1), \\
    & P(Y_2 | X_1, X_2, Y_1) = P(Y_2 | X_2).\end{aligned}$$ Therefore, with chain rule, $$\begin{aligned}
    & P(Y_1, Y_2 | X_1, X_2) = P(Y_1 | X_1)P(Y_2 | X_2).\end{aligned}$$ Since $P(Y_1 | X_1)$ and $P(Y_2 | X_2)$ are both high in training, if they generalize well, they should also be high in test, so that their product should be high in test. To make $P(Y_1 | X_1)$ and $P(Y_2 | X_2)$ generalize well at test time, we hope to remove unnecessary information from $X_1$ and $X_2$. In other words, we want $X_1$ ($X_2$) to be a *minimal sufficient statistic* for $Y_1$ ($Y_2$). In this task, input $X$ is a word sequence, and output $Y$ is an action sequence. We consider $X$ has two types of information: which actions are present ($X_1$), and how the actions should be ordered ($X_2$). $Y$ is constructed by the output action types ($Y_1$), and output action order ($Y_2$). $Y_1$ depends only on $X_1$, and $Y_2$ depends only on $X_2$. Based on these arguments, we design the algorithm with the following objectives:

1.  Learn two representations for input.

2.  Reduce entropy in each representation.

3.  Make output action type depend only on one representation, and output action order depend only on the other.

Figure \[fig:simple\_model\] shows an illustration of flowchart for the algorithm design (see Algorithm \[alg:algorithm\] for details). We describe it further here.

\[t\]

\[1\] $V$: output vocabulary size $\hspace{2em}\;$ $k_p, k_f$: embedding sizes $\hspace{2em}\;$ $\alpha$: 1 for training, 0 for inference $\hspace{2em}\;$ Seq2seq: seq2seq architecture $x$: sequence of one-hot representations $\hat{y}$: sequence of distributions $p_i = \text{Emb}_p(x_i) \in \mathbb{R}^{k_p}$ $f_i = \text{Emb}_f(x_i) \in \mathbb{R}^{k_f}$ $p' = p + \alpha\epsilon_p \in \mathbb{R}^{n \times k_p}, \epsilon_p \sim \mathcal{N}(0, I)$ $f' = f + \alpha\epsilon_f \in \mathbb{R}^{n \times k_f}, \epsilon_f \sim \mathcal{N}(0, I)$ $\text{decoder} = \text{Seq2seq}(f')$ $b_j = \text{decoder.next()} \in \mathbb{R}^{n}$ $a_j = \text{Softmax}(b_j) \in \mathbb{R}^{n}$ $v_j = a_jp' \in \mathbb{R}^{k_p}$ $l_j = f_\text{predict}(v_j) \in \mathbb{R}^V$ $\hat{y}_j = \text{Softmax}(l_j) \in (0, 1)^V$ **break if** $\operatorname*{\arg\!\max}{\hat{y}_j}$ is &lt;EOS&gt;

\[alg:algorithm\]

Input and Output
----------------

Input $x$ contains a sequence of $n$ words, where each input word is from an input vocabulary of size $U$. Output $y$ contains a sequence of $m$ action symbols, where each output symbol is from an output vocabulary of size $V$. Both vocabularies contain an end-of-sentence symbol which appears at the end of $x$ and $y$, respectively. The model output $\hat{y}$ is a prediction for $y$. Both input words and output symbols are in one-hot representation, i.e., $$\begin{split}
& x = [x_1, \dots, x_n] \in \{0, 1\}^{U \times n}, \\
& y = [y_1, \dots, y_m] \in \{0, 1\}^{V \times m}.
\end{split}$$

Primitive Representation and Function Representation
----------------------------------------------------

To achieve objective (i), we use two representations for an input sentence. For each word, we use two word embeddings for primitive and functional information. $$\begin{split}
& p_i = \text{Emb}_p(x_i) \in \mathbb{R}^{k_p}, \\
& f_i = \text{Emb}_f(x_i) \in \mathbb{R}^{k_f}.
\end{split}$$ We concatenate $p_i$ and $f_i$ to form the primitive representation and functional representation for the entire input sequence, i.e., $$\begin{split}
& p=[p_1,\dots,p_n] \in \mathbb{R}^{k_p \times n}, \\
& f=[f_1,\dots,f_n] \in \mathbb{R}^{k_f \times n}.
\end{split}$$

Entropy Regularization {#sec:noise_regularization}
----------------------

To achieve objective (ii), we reduce the amount of information, or entropy of the representations. We do this by regularizing the $L_2$ norm of the representations, and then adding noise to them. This reduces channel capacities, and thus entropy for the representations. $$\begin{split}
& p' = p + \alpha \epsilon_p \in \mathbb{R}^{k_p \times n}, \epsilon_p \sim \mathcal{N}(0, I), \\
& f' = f + \alpha \epsilon_f \in \mathbb{R}^{k_f \times n}, \epsilon_f \sim \mathcal{N}(0, I), \\
& \mathcal{L}_\text{regularize} = L_2(p) + L_2(f).
\end{split}$$ Here, $\alpha$ is the weight for noise. Noise is helpful in training, but is not necessary in inference. Therefore, we set $\alpha$ as a hyper-parameter for training and $\alpha=0$ for inference.

Combine Representations and Generate Output
-------------------------------------------

To achieve objective (iii), we want to make the output action types depend only on primitive representation, and the output action order depend only on function representation. Attention mechanism is a good fit for this purpose. We generate a sequence of attention maps from function representation, and use each attention map to get the weighted average of primitive representation to predict the corresponding action. We use attention mechanism with sequence-to-sequence architectures to aggregate representations in the following ways: (1) Instead of outputting a sequence of logits on vocabulary, we emit a sequence of logits for attention maps on input positions (see Figure \[fig:simple\_model\] for an example). (2) During decoding for autoregressive models, we do not use the previous output symbol as input for the next symbol prediction, because output symbols contain information for primitives. We still use the last decoder hidden state as input. Non-autoregressive models should not have this problem. (3) We end decoding when the last output is end-of-sentence symbol. More specifically, we feed the function representation, $f'$, to a sequence-to-sequence neural network for decoding. At each step $j$, we generate $b_j \in \mathbb{R}^n$ from the decoder, and use Softmax to obtain the attention map, $a_j$. With attention maps, we extract primitives and generate output symbols. To do that, we compute the weighted average, $v_j$, on noised primitive representations, $p'$, with attention, $a_j$. Then we feed it to a one-layer fully connected network, $f_\text{predict}$. We use Softmax to compute the output distribution, $\hat{y}_j$. The decoding ends when $\operatorname*{\arg\!\max}\hat{y}_j$ is end-of-sentence symbol. $$\begin{split}
        & a_j = \text{Softmax}(b_j) \in \mathbb{R}^{n}, \\
    & v_j = a_jp' \in \mathbb{R}^{k_p}, \\
    & l_j = f_\text{predict}(v_j) \in \mathbb{R}^V, \\
    & \hat{y}_j = \text{Softmax}(l_j) \in (0, 1)^V. \\
    \end{split}$$

Loss
----

We use the cross entropy of $y$ and $\hat{y}$ as the prediction loss, $\mathcal{L}_\text{prediction}$, and the final loss, $\mathcal{L}$, is the combination of prediction loss and entropy regularization loss (Section \[sec:noise\_regularization\]). $\lambda$ is the regularization weight. $$\begin{split}
    \mathcal{L}_\text{prediction} &= \sum^{m}_{j=1} \text{CrossEntropy}(y_j, \hat{y}_j), \\
    \mathcal{L} &= \mathcal{L}_\text{prediction} + \lambda \mathcal{L}_\text{regularize}.
\end{split}$$

Experiments
===========

We ran experiments on instruction learning and machine translation tasks. Following <span>@lake2018generalization ([-@lake2018generalization])</span>, we used sequence-level accuracy as the evaluation metric. A prediction is considered correct if and only if it perfectly matches the reference. We ran all experiments five times with different random seeds for the proposed approach, and report mean and standard deviation (note that their sum may exceed 100%). The Appendix contains details of models and experiments.

SCAN Primitive Tasks
--------------------

We used the SCAN dataset @lake2018generalization, and targeted the Jump and TurnLeft tasks. For the Jump and TurnLeft tasks, "jump" and "turn left" appear only as a single command in their respective training sets, but they appear with other words at test time (see Table \[table:example\_jump\] and Table \[table:example\_left\], respectively). We used multiple state-of-the-art or representative methods as baselines. L&B methods are from <span>@lake2018generalization ([-@lake2018generalization])</span>, RNN and GRU are best models for each task from <span>@bastings-etal-2018-jump ([-@bastings-etal-2018-jump])</span>. Ptr-Bahdanau and Ptr-Luong are best methods from <span>@kliegl2018more ([-@kliegl2018more])</span>.

We applied the same configuration for all tasks (see Appendix \[sec:configuration\] for details). The result in Table \[table:result\] shows that the proposed method boosts accuracies from 14.0% to 98.8% in Jump task, and from 92.0% to 99.7% in TurnLeft task.

<span> lrr </span> Method & &\
L&B

best overall

& 0.1

 

& 90.0

   

\
L&B

best

& 1.2

 

& 90.3

   

\
RNN

+Attn -Dep

& 2.7

$\pm$ 1.7

& 92.0

$\pm$   5.8

\
GRU

+Attn

& 12.5

$\pm$ 6.6

& 59.1

$\pm$ 16.8

\
Ptr-Bahdanau & 3.3

$\pm$ 0.7

& 91.7

$\pm$   3.6

\
Ptr-Loung & 14.0

$\pm$ 2.8

& 66.0

$\pm$   5.6

\
Proposed & **98.8**

**$\pm$ 1.4**

& **99.7**

**$\pm$   0.4**

\

SCAN Template-matching
----------------------

We also experimented with the SCAN template-matching task. The task and dataset descriptions can be found in <span>@lake2018rearrange ([-@lake2018rearrange])</span>. There are four tasks in this dataset: *jump around right*, *primitive right*, *primitive opposite right* and *primitive around right*. Each requires compositional generalization. Please see Appendix \[sec:template\] for more details.

Table \[table:template\_split\_result\] summarizes the results on SCAN template-matching tasks. The baseline methods are from <span>@lake2018rearrange ([-@lake2018rearrange])</span>. The proposed method achieves significantly higher performance than baselines in all tasks. This experiment demonstrates that the proposed method has better compositional generalization related to template matching.

<span> lrr </span> Condition & &\
Jump around & 98.4

$\pm$   0.5

& **100.0**

**$\pm$   0.0**

\
Prim. & 23.5

$\pm$   8.1

& **99.7**

**$\pm$   0.5**

\
Prim. opposite & 47.6

$\pm$ 17.7

& **89.3**

**$\pm$   5.5**

\
Prim. around & 2.5

$\pm$   2.7

& **83.2**

**$\pm$ 13.2**

Primitive and Functional Information Exist in One Word
------------------------------------------------------

One limitation of SCAN dataset is that each word contains either primitive or functional information, but not both. For example, "jump" contains only primitive information, but no functional information. On the other hand, "twice" contains only functional information, but no primitive information. However, in general cases, each word may contain both primitive and functional information. The functional information of a word usually appears as a word class, such as part of speech. For example, in translation, a sequence of part-of-speech tags determines the output sentence structure (functional), and primitive information of each input word determines the corresponding output word.

To explore whether the proposed method works when a word contains both primitive and functional information, we introduced an extension of SCAN dataset for this purpose. We designed a task SCAN-ADJ to identify adjectives in a sentence, and place them according to their word classes. The adjectives have three word classes: color, size, and material. The word classes appear in random order in input sentences, but they should be in a fixed order in the expected outputs. For example, an input sentence is "push blue metal small cube", and the expected output is "PUSH CUBE SMALL BLUE METAL". For another input "push small metal blue cube", the expected output is the same. Please see Table \[table:adjectives\_generation\] in Appendix for more details. To evaluate compositional generalization, similarly to the SCAN setting, the material, rubber, appears only with other fixed words in training "push small yellow rubber sphere". However, it appears with other combinations of words at test time. To solve this compositionality problem, a model needs to capture functional information of adjectives to determine their word classes, and primitive information to determine the specific value of the word in its class.

The experiment results are shown in Table \[table:scan-adj\]. The proposed method achieves 100.0% ($\pm$0.0%) accuracy, and as a comparison, a standard LSTM model can only achieves 2.1% ($\pm$2.2%) accuracy. Please refer to Appendix \[sec:both\_info\] for more details. This indicates that the proposed method can extend beyond simple structures in the SCAN dataset to flexibly adapt for words containing both primitive and functional information.

<span> lr </span> Method &\
Baseline & 2.1

$\pm$ 2.2

\
Proposed & **100.0**

**$\pm$ 0.0**

\

Few-shot Learning Task
----------------------

We also probed the few-shot learning ability of the proposed approach using the dataset from <span>@lake2019human ([-@lake2019human])</span>. The dataset is shown in Appendix Figure \[fig:fewshot\_primitive\_testset\]. In the few-shot learning task, human participants learned to produce abstract outputs (colored circles) from instructions in pseudowords. Some pseudowords are primitive corresponding to a single output symbol, while others are function words that process items. A primitive ("zup") is presented only in isolation during training and evaluated with other words during test. Participants are expected to learn each function from limited number of examples, and to generalize in a compositional way. We trained a model from all training samples and evaluate them on both Primitive test samples and all test samples. We used a similar configuration to SCAN task (Appendix \[sec:few\_shot\]) to train the model, and compared the results with baselines of human performance and conventional sequence to sequence model @lake2019human. In the Primitive task, we used the average over sample accuracies to estimate the accuracy of human participants, and the upper bound accuracy of the sequence-to-sequence model.

Table \[table:fewshot\_result\] shows the results that the proposed method achieves high accuracy on both test sets. In the Primitive task, the proposed method beats human performance. This indicates that the proposed method is able to learn compositionality from only a few samples. To our best knowledge, this is the first time machines beat humans in a few-shot learning task, and it breaks the common sense that humans are better than machines in learning from few samples.

<span> lrr </span> Method & &\
Human & 82.8

 

& 84.3

 

\
Baseline & $\le$ 3.1

 

& 2.5

 

\
Proposed & **95.0**

**$\pm$ 6.8**

& 76.0

$\pm$ 5.5

\

Compositionality in Machine Translation {#sec:nmt}
---------------------------------------

We also investigated whether the proposed approach is applicable to other sequence-to-sequence problems. As an example, we ran a proof-of-concept machine translation experiment. We consider the English-French translation task from <span>@lake2018generalization ([-@lake2018generalization])</span>. To evaluate compositional generalization, for a word "dax", the training data contains only one pattern of sentence pair ("I am daxy", "je suis daxiste"), but test data contains other patterns. Appendix \[sec:appendix\_mt\] provides more details on dataset and model configuration.

Compared to the baseline method, the proposed method increases sentence accuracy from 12.5% to 62.5% ($\pm$0.0%). Further, we find that other predicted outputs are even correct translations though they are different from references (Table \[table:translation\_examples\] in Appendix). If we count them as correct, the adjusted accuracy for the proposed approach is 100.0% ($\pm$0.0%). This experiment shows that the proposed approach has promise to be applied to real-world tasks.

  Method     
  ---------- ----------
  Baseline         12.5
  Proposed     **62.5**

  : Test accuracy (%) for machine translation task. The baseline method is from <span>@lake2018generalization ([-@lake2018generalization])</span>. <span data-label="table:translation_result"></span>

Discussion
==========

Our experiments show that the proposed approach results in significant improvements on many tasks. To better understand why the approach achieves these gains, we designed the experiments on SCAN domain to address the following questions: (1) Does the proposed model work in the expected way that humans do (i.e., visualization)? (2) What factors of the proposed model contribute to the high performance (i.e., ablation study)? (3) Does the proposed method influence other tasks?

Visualization of Attention Maps
-------------------------------

\[t\] ![image](figs/visualization3.png){width="70.00000%"}

To investigate whether the proposed method works in the expected way, we visualize the model's attention maps. These maps indicate whether the sequence-to-sequence model produces correct position sequences.

We visualized these activations for one sample from the Jump task and one from the TurnLeft task (Figure \[fig:visualization\]). In both figures, the horizontal dimension is the input sequence position, and the vertical dimension is the output position. Each figure is an $m \times n$ matrix, where $m$ and $n$ are output and input lengths, including end-of-sentence symbols. The rows correspond to $m$ attention maps, where the $i$th row corresponds to the attention map for the $i$th output ($i=1,...,m$). The values in each row sum to 1.

We expect that each attention map attends on the corresponding primitive input word. For the output end-of-sentence symbol, we expect that the attention is on the input end-of-sentence symbol. The visualization in both figures align with our expectation. When the model should replicate some input word multiple times, it correctly attends on that word in a manner similar to human understanding. In the Jump example, "jump" appears twice in the input. As expected, the generated attentions are on the second instance for the early part of the output, and on the first instance for the later part of the output. Similarly, the attentions are correct in the TurnLeft example with two words of "left".

These visualizations demonstrate that the models work in the way we expected, correctly parsing the organization of complex sentences. We have successfully encoded our prior knowledge to the network, and enabled compositional generalization.

Ablation Study
--------------

We conducted an ablation study to find out what factors of the proposed approach contribute to its high performance. The main idea of the proposed approach is to use two representations and corresponding entropy regularization. Also, for autoregressive decoders, the approach does not use the last output rather than feeding it as input for decoding. Based on that, we designed the following ablation experiments.

\(A) Use only one representation.

\(B) Do not use primitive entropy regularization.

\(C) Do not use function entropy regularization.

\(D) Both B and C.

\(E) Use the last output as input in decoding. The results are summarized in Table \[table:ablation\]. Experiment A shows that the accuracy drops in both tasks, indicating that two representations are important factor in the proposed approach. When there are two representations, we find the following from experiments B, C and D. For Jump task, the accuracy drops in these three experiments, indicating both primitive and function entropy regularization are necessary. For TurnLeft task, the accuracy drops only in D, but not in B or C, indicating at least one of entropy regularization is necessary. The difference between Jump and TurnLeft tasks may be because TurnLeft is relatively easier than the Jump task. Both "turn" and "left" individually appear with other words in training data, but "jump" does not. Experiment E shows that we should not use last output as next input during decoding.

<span> llrr </span> & Experiment & &\
A & one rep. & 63.4

$\pm$ 36.3

& 55.7

$\pm$ 31.5

\
B & no prim reg. & 79.8

$\pm$ 11.3

& 99.9

$\pm$   0.1

\
C & no func reg. & 29.5

$\pm$ 36.3

& 99.6

$\pm$   1.0

\
D & both B and C & 14.1

$\pm$ 23.2

& 64.0

$\pm$ 40.0

\
E & decoder input & 68.8

$\pm$ 15.0

& 50.3

$\pm$ 48.8

\
& Proposed & 98.8

$\pm$   1.4

& 99.7

$\pm$   0.4

\

Influence on Other Tasks {#section:other_tasks}
------------------------

To find whether the proposed method affects other tasks, we conducted experiments on Simple and Length tasks in SCAN dataset. In Simple task, test data follows the same distribution as the training data. In Length task, test commands have longer action sequences than training. Simple task does not require compositional generalization, and Length task requires syntactic generalization, so that they are beyond the scope of this paper. However, we still hope to avoid big performance drop from previous methods. We used the same configuration (Appendix \[sec:configuration\]) as SCAN Primitive tasks. The results in Table \[table:other\_result\] confirms that the approach does not significantly reduce performance in other tasks.

<span> lrr </span> Methods & &\
L&B

best overall

& 99.7

 

& 13.8

 

\
L&B

best

& 99.8

 

& 20.8

 

\
RNN

+Attn -Dep

& 100.0

$\pm$ 0.0

& 11.7

$\pm$ 3.2

\
GRU

+Attn

& 100.0

$\pm$ 0.0

& 18.1

$\pm$ 1.1

\
Ptr-Bahdanau & -

 

& 13.4

$\pm$ 0.8

\
Ptr-Loung & -

 

& 16.8

$\pm$ 0.9

\
Proposed & 99.9

$\pm$ 0.0

& 20.3

$\pm$ 1.1

\

Related Work
============

Human-level compositional learning has been an important open challenge @yang2019task, although there is a long history of studying compositionality in neural networks. Classic view @fodor1988connectionism [@marcus1998rethinking; @fodor2002compositionality] considers conventional neural networks lack systematic compositionality. With the breakthroughs in sequence to sequence neural networks for NLP and other tasks, such as RNN @sutskever2014sequence, Attention @xu2015show, Pointer Network @vinyals2015pointer, and Transformer @vaswani2017attention, there are more contemporary attempts to encode compositionality in sequence to sequence neural networks.

There has been exploration on compositionality in neural networks for systematic behaviour @wong2007generalisation [@brakel2009strong], counting ability @rodriguez1998recurrent [@weiss2018practical] and sensitivity to hierarchical structure @linzen2016assessing. Recently, many related tasks @lake2018generalization [@loula2018rearranging; @livska2018memorize; @bastings-etal-2018-jump; @lake2019human] and methods @bastings-etal-2018-jump [@loula2018rearranging; @kliegl2018more; @chang2018automatically] using a variety of RNN models and attention mechanism have been proposed. These methods make successful generalization when the difference between training and test commands are small.

Our research further enhances the capability of neural networks for compositional generalization with two representations of a sentence and entropy regularization. The proposed approach has shown promising results in various tasks of instruction learning and machine translation.

Compositionality is also important and applicable in multimodal problems, including AI complete tasks like Image Captioning @karpathy2015deep, Visual Question Answering @antol2015vqa, Embodied Question Answering @das2018embodied. These tasks requires compositional understanding of sequences (captions or questions), where our method could help. Compositional understanding could also help enable better transfer over time that could improve continual learning @zenke2017continual [@aljundi2018memory; @chaudhry2018efficient] ability of AI models.

Conclusions
===========

This work is a fundamental research for encoding compositionality in neural networks. Our approach leverages prior knowledge of compositionality by using two representations, and by reducing entropy in each representation. The experiments demonstrate significant improvements over the conventional methods in five NLP tasks including instruction learning and machine translation. In the SCAN domain, it boosts accuracies from 14.0% to 98.8% in Jump task, and from 92.0% to 99.7% in TurnLeft task. It also beats human performance on a few-shot learning task. To our best knowledge, this is the first time machines beat humans in a few-shot learning task. This breaks the common sense that humans have advantage over machines in learning from few samples. We hope this work opens a path to encourage machines learn quickly and generalize widely like humans do, and to make machines more helpful in various tasks.

Acknowledgments {#acknowledgments .unnumbered}
===============

We thank Kenneth Church, Mohamed Elhoseiny, Ka Yee Lun and others for helpful suggestions.

SCAN Tasks {#sec:configuration}
==========

For the sequence to sequence architecture, we use bidirectional LSTM as encoder, and unidirectional LSTM with attention as decoder. The first and last states of encoder are concatenated as initial state of decoder. The state size is $m=16$ for encoder, and $2m=32$ for decoder. For all SCAN tasks, the primitive embedding size $k_p$ and function embedding size $k_f$ are both 8. The weight for $L_2$ norm regularization $\lambda$ is 0.01, and noise weight $\alpha$ is 1. We use Adam @kingma2014adam for optimization. We ran 10,000 training steps. Each step has a mini-batch of 64 samples randomly and uniformly selected from training data with replacement. We clip gradient by global norm of 1. Initial learning rate is 0.01 and it exponentially decays by a factor of 0.96 every 100 steps. We use TensorFlow @abadi2016tensorflow for implementation.

SCAN dataset contains four sub datasets. Jump task contains 14,670 training and 7,706 test samples. TurnLeft task contains 21,890 training and 1,208 test samples. Simple task contains 16,728 training and 4,182 test samples. Length task contains 16,990 training and 3,920 test samples. We aim at Jump and TurnLeft tasks in the main experiments. Since Simple task does not require compositional generalization, and Length task requires syntactic generalization, they are beyond the scope of this paper. However, we still evaluate them to show that their performance is not significantly reduced.

SCAN Template-matching {#sec:template}
======================

We extend experiments to SCAN template-matching task @lake2018rearrange. There are four tasks in this dataset. In *jump around right* task, the test set includes all samples containing "jump around right" (1,173 samples), and training set consists of the remaining samples (18,528 samples). In *primitive right* task, the test set includes all samples containing "Primitive right" (4,476 samples), and the training set consists of the remaining templates (15,225 samples). In *primitive opposite right* task, the test set includes all samples containing templates in the form "Primitive opposite right" (4,476 samples), and the training set consists of remaining templates (including their conjunctions and quantifications) (15,225 samples). In *primitive around right* task, the test set includes all samples containing templates in the form "Primitive around right" (4,476 samples), and the training set consists of remaining templates (15,225 samples).

For *primitive around right* task, we set $m=8, k_p=k_f=128,\lambda=0.1$, and $\alpha=0.1$. For other tasks, we use the same model configurations as SCAN Jump task.

Primitive and Functional Information Exist in One Word {#sec:both_info}
======================================================

\[ht\]

<span>rcl</span>\
S & $\rightarrow$ & V A N\
A & $\rightarrow$ & C R M $\vert$ C M R $\vert$ R C M $\vert$ R M C $\vert$ M C R $\vert$ M R C\
V & $\rightarrow$ & push $\vert$ pull $\vert$ raise $\vert$ spin\
R & $\rightarrow$ & small $\vert$ large\
C & $\rightarrow$ & yellow $\vert$ purple $\vert$ brown $\vert$ blue $\vert$ red $\vert$ gray $\vert$ green $\vert$ cyan\
M & $\rightarrow$ & metal $\vert$ plastic $\vert$ rubber\
N & $\rightarrow$ & sphere $\vert$ cylinder $\vert$ cube\

We constructed a dataset with both primitive and functional information contained in one word using the grammar in Table \[table:adjectives\_generation\]. The training data contains 2,560 samples, and test data 1,151 samples. For the proposed approach, we set $m=32,\lambda=0.1,\alpha=0.3$, and we run 5,000 training steps. We keep other configurations the same as SCAN task. For comparison, we use standard LSTM with attention. The hyper parameters are the same as the proposed approach.

Few-shot Learning task {#sec:few_shot}
======================

\[ht\] ![image](figs/fewshot_data.png){width="100.00000%"}

For few-shot learning task, we set $k_p=k_f=16$ and $\lambda=0.1$. We keep other configurations the same as SCAN task.

The dataset @lake2019human is shown in Figure \[fig:fewshot\_primitive\_testset\]. It contains 14 training and 10 test samples. Among them, 8 test samples correspond to Primitive task. The other 2 test samples requires syntactic generalization which is beyond the scope of this paper.

Machine Translation {#sec:appendix_mt}
===================

The experimental setting of machine translation follows <span>@lake2018generalization ([-@lake2018generalization])</span>. The training data contains 10,000 English-French sentence pairs. The sentences are selected to be less than 10 words in length, and starting from English phrases such as "I am", "he is" and their contractions. The training data also contains 1,000 repetition of sentence pair ("I am daxy", "je suis daxiste"). Note that "dax" does not appear in the first set of training data. The two sets of training data are mixed and randomized. The test data contains 8 pairs of sentences that contain "daxy" in different patterns from training data, for example ("you are not daxy", "tu n'es pas daxiste").

The model configurations are similar to SCAN tasks, except that we set $m=32,k_p=k_f=32$, $\lambda=1$ and $\alpha=1$ in experiments. The result shows that some predicted outputs differ from the reference, but they are correct translations. Please see Table \[table:translation\_examples\] for details.

  Input                 Output
  --------------------- ---------------------------
  you are daxy .        tu es daxiste .
                        vous etes daxiste .
  you are not daxy .    tu n es pas daxiste .
                        vous n etes pas daxiste .
  you are very daxy .   tu es tres daxiste .
                        vous etes tres daxiste .

  : Test prediction mistakes in machine translation task (normalized). All mistakes are actually correct. Left part is input. Right part is output for reference (upper) and hypothesis (lower).<span data-label="table:translation_examples"></span>

[^1]: <https://github.com/yli1/CGPS>

{'source': 'arXiv_out/1910'}