summaries: Paper summary: This paper explores the problem of robustly transfer learning using only standard training (as opposed to adversarial training (AT)) on the target domain. The authors start by highlighting that intermediate representations learned by adversarially trained networks are themselves fairly robust. Then they propose two strategies for robust transfer from a robust model trained on the source domain: (1) naturally fine-tuning the final linear layer on the target domain and (2) naturally fine-tuning all the layers using lifelong learning strategies. They study transfer between CIFAR10 and CIFAR100, as well as, from ImageNet to CIFAR10/100.

summaries: The paper studies transfer learning from the point of view of adversarial robustness. The goal is, given a robust deep neural network classifier for a source domain, learn a robust classifier for a target domain as efficiently and with as few samples as possible. The authors empirically evaluate different strategies and compare with relevant baselines.

summaries: This paper addresses the problem of performing robust transfer learning. A first contribution of the paper is to robust and classic training with respect to usual validation accuracy and robustness to adversarial attacks on the CIFAR task. Then, the same comparison is made on a transfer learning task. The transfer learning setting is then completed by studying transfer from ImageNet-based models with a particular attention to low-data regime and training deeper networks on top of the feature extractor. An analysis of robust features is provided and finally the authors studies the interest of  Learning without Forgetting strategies to provide robust transfer. The tendency s to obtain the Best performance from robust-trained source models having a good validation accuracy.

abstractText: Transfer learning, in which a network is trained on one task and re-purposed on another, is often used to produce neural network classifiers when data is scarce or full-scale training is too costly. When the goal is to produce a model that is not only accurate but also adversarially robust, data scarcity and computational limitations become even more cumbersome. We consider robust transfer learning, in which we transfer not only performance but also robustness from a source model to a target domain. We start by observing that robust networks contain robust feature extractors. By training classifiers on top of these feature extractors, we produce new models that inherit the robustness of their parent networks. We then consider the case of “fine tuning” a network by re-training end-to-end in the target domain. When using lifelong learning strategies, this process preserves the robustness of the source network while achieving high accuracy. By using such strategies, it is possible to produce accurate and robust models with little data, and without the cost of adversarial training. Additionally, we can improve the generalization of adversarially trained models, while maintaining their robustness.

authors:
Anish Athalye
Nicholas Carlini
David Wagner

title: Obfuscated gradients give a false sense of security: Circumventing defenses to adversarial examples

venue: arXiv preprint arXiv:1802.00420,

authors:
Battista Biggio
Igino Corona
Davide Maiorca
Blaine Nelson
Nedim Šrndić
Pavel Laskov
Giorgio Giacinto
Fabio Roli

title: Evasion attacks against machine learning at test time

venue: In Joint European conference on machine learning and knowledge discovery in databases,

authors:
Nicholas Carlini
David Wagner

title: Towards evaluating the robustness of neural networks

venue: IEEE Symposium on Security and Privacy (SP),

authors:
Ian J Goodfellow
Jonathon Shlens
Christian Szegedy

title: Explaining and harnessing adversarial examples

venue: International Conference on Learning Representation,

authors:
Dan Hendrycks
Kimin Lee
Mantas Mazeika

title: Using pre-training can improve model robustness and uncertainty

venue: arXiv preprint arXiv:1901.09960,

authors:
Geoffrey Hinton
Oriol Vinyals
Jeff Dean

title: Distilling the knowledge in a neural network

venue: arXiv preprint arXiv:1503.02531,

authors:
Sergey Ioffe
Christian Szegedy

title: Batch normalization: Accelerating deep network training by reducing internal covariate shift

venue: arXiv preprint arXiv:1502.03167,

authors:
Alex Krizhevsky
Geoffrey Hinton

title: Learning multiple layers of features from tiny images

venue: Technical report, Citeseer,

authors:
Alexey Kurakin
Ian Goodfellow
Samy Bengio

title: Adversarial machine learning at scale

venue: arXiv preprint arXiv:1611.01236,

authors:
Yann LeCun
Léon Bottou
Yoshua Bengio
Patrick Haffner

title: Gradient-based learning applied to document recognition

venue: Proceedings of the IEEE,

authors:
Zhizhong Li
Derek Hoiem

title: Learning without forgetting

venue: IEEE transactions on pattern analysis and machine intelligence,

authors:
Aleksander Madry
Aleksandar Makelov
Ludwig Schmidt
Dimitris Tsipras
Adrian Vladu

title: Towards deep learning models resistant to adversarial attacks

venue: arXiv preprint arXiv:1706.06083,

authors:
Seyed-Mohsen Moosavi-Dezfooli
Alhussein Fawzi
Pascal Frossard

title: Deepfool: a simple and accurate method to fool deep neural networks

venue: In Proceedings of the IEEE conference on computer vision and pattern recognition,

authors:
Sinno Jialin Pan
Qiang Yang

title: A survey on transfer learning

venue: IEEE Transactions on knowledge and data engineering,

authors:
Olga Russakovsky
Jia Deng
Hao Su
Jonathan Krause
Sanjeev Satheesh
Sean Ma
Zhiheng Huang
Andrej Karpathy
Aditya Khosla
Michael Bernstein

title: Imagenet large scale visual recognition challenge

venue: International journal of computer vision,

authors:
Ludwig Schmidt
Shibani Santurkar
Dimitris Tsipras
Kunal Talwar
Aleksander Madry

title: Adversarially robust generalization requires more data

venue: In Advances in Neural Information Processing Systems,

authors:
Ali Shafahi
W Ronny Huang
Christoph Studer
Soheil Feizi
Tom Goldstein

title: Are adversarial examples inevitable? ICLR, 2019a

authors:
Ali Shafahi
Mahyar Najibi
Amin Ghiasi
Zheng Xu
John Dickerson
Christoph Studer
Larry S Davis
Gavin Taylor
Tom Goldstein

title: Adversarial training for free

venue: arXiv preprint arXiv:1904.12843,

authors:
Nitish Srivastava
Geoffrey Hinton
Alex Krizhevsky
Ilya Sutskever
Ruslan Salakhutdinov

title: Dropout: a simple way to prevent neural networks from overfitting

venue: The Journal of Machine Learning Research,

authors:
Dong Su
Huan Zhang
Hongge Chen
Jinfeng Yi
Pin-Yu Chen
Yupeng Gao

title: Is robustness the cost of accuracy?–a comprehensive study on the robustness of 18 deep image classification models

venue: In Proceedings of the European Conference on Computer Vision (ECCV),

authors:
Christian Szegedy
Wojciech Zaremba
Ilya Sutskever
Joan Bruna
Dumitru Erhan
Ian Goodfellow
Rob Fergus

title: Intriguing properties of neural networks

venue: arXiv preprint arXiv:1312.6199,

authors:
Florian Tramèr
Alexey Kurakin
Nicolas Papernot
Ian Goodfellow
Dan Boneh
Patrick McDaniel

title: Ensemble adversarial training: Attacks and defenses

venue: arXiv preprint arXiv:1705.07204,

authors:
Dimitris Tsipras
Shibani Santurkar
Logan Engstrom
Alexander Turner
Aleksander Madry

title: Robustness may be at odds with accuracy

authors:
Jason Yosinski
Jeff Clune
Yoshua Bengio
Hod Lipson

title: How transferable are features in deep neural networks

venue: In Advances in neural information processing systems,

authors:
Sergey Zagoruyko
Nikos Komodakis

title: Wide residual networks

venue: arXiv preprint arXiv:1605.07146,

authors:
Hongyang Zhang
Yaodong Yu
Jiantao Jiao
Eric P Xing
Laurent El Ghaoui
Michael I Jordan

title: Theoretically principled trade-off between robustness and accuracy

heading: 1 INTRODUCTION

text:
Deep neural networks achieve human-like accuracy on a range of tasks when sufficient training data and computing power is available. However, when large datasets are unavailable for training, or pracitioners require a low-cost training strategy, transfer learning methods are often used. This process starts with a source network (pre-trained on a task for which large datasets are available), which is then re-purposed to act on the target problem, usually with minimal re-training on a small dataset (Yosinski et al., 2014; Pan & Yang, 2009).
While transfer learning greatly accelerates the training pipeline and reduces data requirements in the target domain, it does not address the important issue of model robustness. It is well-known that naturally trained models often completely fail under adversarial inputs (Biggio et al., 2013; Szegedy et al., 2013). As a result, researchers and practitioners often resort to adversarial training, in which adversarial examples are crafted on-the-fly during network training and injected into the training set. This process greatly exacerbates the problems that transfer learning seeks to avoid. The high cost of creating adversarial examples increases training time (often by an order of magnitude or more). Furthermore, robustness is known to suffer when training on a small dataset (Schmidt et al., 2018). To make things worse, high-capacity models are often needed to achieve good robustness (Madry et al., 2017; Kurakin et al., 2016; Shafahi et al., 2019b), but these models may over-fit badly on small datasets.
CONTRIBUTIONS
The purpose of this paper is to study the adversarial robustness of models produced by transfer learning. We begin by observing that robust networks contain robust feature extractors, which are resistant to adversarial perturbations in different domains. Such robust features can be used
∗equal contribution †University of Maryland ‡Cornell University
as a basis for semi-supervised transfer learning, which only requires re-training the last layer of a network. To demonstrate the power of robust transfer learning, we transfer a robust ImageNet source model onto the CIFAR domain, achieving both high accuracy and robustness in the new domain without adversarial training. We use visualization methods to explore properties of robust feature extractors. Then, we consider the case of transfer of learning by “fine-tuning.” In this case, the source network is re-trained end-to-end using a small number of epochs on the target domain. Unfortunately, this end-to-end process does not always retain the robustness of the source domain; the network “forgets” the robust feature representations learned on the source task. To address this problem, we use recently proposed lifelong learning methods that prevent the network from forgetting the robustness it once learned. Using our proposed methods, we construct robust models that generalize well. In particular, we improve the generalization of a robust CIFAR-100 model by roughly 2% while preserving its robustness.

heading: 2 BACKGROUND

text:
Adversarial examples fall within the category of evasion attacks—test-time attacks in which a perturbation is added to a natural image before inference. Adversarial attacks are most often crafted using a differentiable loss function that measures the performance of a classifier on a chosen image. In the case of norm-constrained attacks (which form the basis of most standard benchmark problems), the adversary solves
max δ
l(x+ δ, y, θ) s.t. ‖δ‖p ≤ , (1)
where θ are the (already trained and frozen) parameters of classifier c(x, θ)→ ŷ that maps an image to a class, l is the proxy loss used for classification (often cross-entropy), δ is the image perturbation, (x, y) is the natural image and its true class, and ||.||p is some `p-norm1. The optimization problem in Eq. 1 aims to find a bounded perturbation that maximizes the cross-entropy loss given the correct label. There are many variants of this process, including DeepFool (Moosavi-Dezfooli et al., 2016), L-BFGS (Szegedy et al., 2013), and CW (Carlini & Wagner, 2017).
Many researchers have studied methods for building a robust network which have been later shown to be ineffective when attacked with stronger adversaries (Athalye et al., 2018). Adversarial training (Szegedy et al., 2013) is one of the defenses that was not broken by Athalye et al. (2018). While adversarial training using a weak adversary such as the FGSM attack (Goodfellow et al., 2015) can be broken even by single step attacks which add a simple random step prior to the FGSM step (Tramèr et al., 2017), adversarial training using a strong attack has successfully improved robustness. Madry et al. (2017) showed that a PGD attack (which is a BIM attack (Kurakin et al., 2016) with an initial random step and projection) is a strong enough attack to achieve promising adversarial training results. We will refer to this training method as PGD adversarial training. PGD adversarial training achieves good robustness on bounded attacks for MNIST (LeCun et al., 1998) and acceptable robustness on CIFAR-10 (Krizhevsky & Hinton, 2009) classifiers.
Tsipras et al. (2018) show that adversarial training with strong PGD adversaries has many benefits in addition to robustness. They also state that while adversarial training may improve generalization in regimes where training data is limited (especially on MNIST), it may be at odds with generalization in regimes where data is available. This trade-off was also recently studied by Zhang et al. (2019), Su et al. (2018), and Shafahi et al. (2019a).
While, to the best of our knowlegde, the transferability of robustness has not been studied in depth, Hendrycks et al. (2019) studied the case of adversarially training models that were pre-trained on different domains. Our work is fundamentally different in that we seek to transfer robustness without resorting to costly and data-hungry adversarial training. We train the target model on natural examples only, which allows us to directly study how well robustness transfers. Additionally, this allows us to have better generalization and achieve higher accuracy on validation examples. While as Hendrycks et al. (2019) state, fine-tuning on adversarial examples built for the target domain can improve robustness of relatively large datasets such as CIFAR-10 and CIFAR-100 compared to adversarial training from scratch on the target domain, we show that in the regimes of limited data (where transfer learning is more common), adversarially robust transfer learning can lead to better results measured in terms of both robustness and clean validation accuracy.
1By default we will use the `∞-norm in this paper.

heading: 3 THE ROBUSTNESS OF DEEP FEATURES

text:
In this section, we explore the robustness of different network layers, and demonstrate that robust networks rely on robust deep features. To do so, we start from robust classifiers (c(θr)) for the CIFAR-100 and CIFAR-10 datasets (Krizhevsky & Hinton, 2009), and update θ by training on natural examples. In each experiment, we re-initialize the last k layers/blocks of the network, and re-train just those layers. We start by re-initializing just the last layer, then the last two, and so on until we re-initialize all the layers.
We use the adversarially trained Wide-ResNet 32-10 (Zagoruyko & Komodakis, 2016) for CIFAR10 from Madry et al. (2017) as our robust model for CIFAR-10. We also adversarially train our own robust classifier for CIFAR-100 using the code from Madry et al. (2017). To keep things consistent, we use the same hyper-parameters used by Madry et al. (2017) for adversarially training CIFAR-10 to adversarially train the CIFAR-100 model.2 The performance of the CIFAR-10 and CIFAR-100 models on natural and adversarial examples are summarized in Table 1. To measure robustness, we evaluate the models on adversarial examples built using PGD attacks.
We break the WRN 32-10 model into 17 blocks, which are depicted in Fig. 2. In each experiment, we first re-initialize the k deepest blocks (blocks 1 through k) and then train the parameters of those blocks on natural images3. We train for 20,000 iterations using Momentum SGD and a learning rate of 0.001. We then incrementally unfreeze and train more blocks. For each experiment, we evaluate the newly trained model’s accuracy on validation adversarial examples built with a 20-step PGD `∞ attack with = 8.
Fig. 1 shows that robustness does not drop if only the final layers of the networks are re-trained on natural examples. In fact, there is a slight increase in robustness compared to the baseline PGD7 adversarially trained models when we just retrain the last batch-normalization block and fully connected block. As we unfreeze and train more blocks, the network’s robustness suddenly drops. This leads us to believe that a hardened network’s robustness is mainly due to robust deep feature representations and robustness is preserved if we re-train on top of deep features.
Now that we have identified feature extractors as a source of robustness, it is natural to investigate whether robustness is preserved when transfer learning using robust feature extractors. We will
2We adv. train the WRN 32-10 on CIFAR-100 using a 7-step `∞ PGD attack with step-size=2 and = 8. We train for 80,000 iterations with a batch-size of 128.
3In this experiment, we use standard data augmentation techniques.
study two different approaches for transferring robustness across datasets: one in which only the last layer is re-trained, and one with end-to-end re-training.

heading: 4 TRANSFER LEARNING: RECYCLING FEATURE EXTRACTORS

text:
We study how robustness transfers when the feature extractor layers of the source network are frozen, and we retrain only the last fully connected layer (i.e. the classification layer) for the new task. Formally, the transfer learning objective is:
min w
l(z(x, θ∗), y, w) (2)
where z is the deep feature extractor function with pre-trained and now “frozen” parameters θ∗, and w represents the trainable parameters of the last fully connected layer. To investigate how well robustness transfers, we use two source models: one that is hardened by adversarial training and another that is naturally trained.
We use models trained on CIFAR-100 as source models and perform transfer learning from CIFAR100 to CIFAR-10. The results are summarized in Table 2. Compared to adversarial/natural training the target model, transferring from a source model seems to result in a drop in natural accuracy (compare first row of Table 1 to the first row of Table 2). This difference is wider when the source and target data distributions are dissimilar (Yosinski et al., 2014).
To evaluate our method on two datasets with more similar attributes, we randomly partition CIFAR100 into two disjoint subsets where each subset contains images corresponding to 50 classes. Table 2 shows the accuracy of transferring from one of the disjoint sets to the other (second row) and to the same set (third row). We can compare results of transfer learning with adversarial training on CIFAR-100 by averaging the results in the second and third rows of Table 2 to get the accuracy across all 100 classes of CIFAR-100.4 By doing so, we see that the accuracy of the transferred classifier matches that of the adversarially trained one, even though no adversarial training took place in the target domain. For completeness, we have also included experiments where we use CIFAR-10 as the source and CIFAR-100 as the target domain.
We make the following observations from the transfer-learning results in Table 2. 1) robustness transfers: when the source model used for transfer learning is robust, the target model is also robust (although less so than the source), 2) robustness transfers between models that are more similar: If
4The robust CIFAR-100 classifier has 59.87% validation accuracy and 22.76% accuracy on PGD-20 adversarial examples. The average validation accuracy of the two half-CIFAR-100 classifiers on validation examples is 64.96%+58.48%
2 = 61.72% while the average robustness is 25.16%+15.86% 2 = 20.51%.
the source and target models are trained on datasets which have similar distributions (and number of classes), robustness transfers better, and 3) validation accuracy is worst if we use a robust model as the source compared to using a conventionally trained source model: if the source model is naturally trained, the natural validation accuracy is better, although the target model is then vulnerable to adversarial perturbations.

heading: 4.1 TRANSFER LEARNING WITH IMAGENET MODELS

text: Transfer learning using models trained on ImageNet (Russakovsky et al., 2015) as the source is a common practice in industry because ImageNet feature extractors are powerful and expressive. In this section we evaluate how well robustness transfers from these models.

heading: 4.1.1 TRANSFER LEARNING USING IMAGENET

text:
Starting from both a natural and robust ImageNet model, we perform the same set of experiments we did in section 4. Robust ImageNet models do not withstand untargeted `∞ attacks using as large an as those that can be used for simpler datasets like CIFAR. Following the method Shafahi et al. (2019b), we “free train” a robust ResNet-50 on ImageNet using replay hyper-parameter m = 4. The hardened ImageNet classifier withstands attacks bounded by = 5. Our robust ImageNet achieves 59.05% top-1 accuracy and roughly 27% accuracy against PGD-20 `∞ = 5 attacks on validation examples. We experiment with using this robust ImageNet model and a conventionally trained ResNet-50 ImageNet model as the source models.
Using the ImageNet source models, we train CIFAR classifiers by retraining the last layer on natural CIFAR examples. We up-sample the 32×32-dimensional CIFAR images to 224×224 before feeding them into the ResNet-50 source models that are trained on ImageNet. For evaluation purposes, we also train robust ResNet-50 models from scratch using (Shafahi et al., 2019b) for the CIFAR models. To ensure that the transfer learning models and the end-to-end trained robust models have the same capacity and dimensionality, we first upsample the CIFAR images before feeding them to the ResNet-50 model. To distinguish between the common case of training ResNet models on CIFAR images that are 32 × 32-dimensional, we call our models that are trained on the upsampled CIFAR datasets the upsample-first ResNets or “u-ResNets”.
Table 3 illustrates that using a robust ImageNet model as a source results in high validation accuracy for the transferred CIFAR target models. Also, given that the ImageNet classifier by itself is 27% robust, the CIFAR-10 model maintains the majority of that 27% robustness. When we compare the end-to-end hardened classifiers (robust u-ResNets) with the transferred classifier, we can see that
while the robustness is less for the transferred case, transferred models result in considerably better performance on clean validation examples.

heading: 4.2 LOW-DATA REGIME

text:
As touched on before, transfer learning is more common in situations where the number of training points in the target domain is limited. Up until now, as a proof of concept, we have illustrated the majority of our experiments on the CIFAR target domains where we have many training points perclass. Hendrycks et al. (2019) show that starting from a pre-trained robust ImageNet model and fine-tuning on adversarial examples of the CIFAR domain can improve robustness beyond that of simply adversarial training CIFAR. Here, we illustrate the effect of training data size on robustness and natural performance by running various experiments on subsets of CIFAR-100 where we vary the number of training points per-class (N ).
We compare three different hardening methods: (1) Free-training/adversarial training the target domain (Shafahi et al., 2019b); (2) fine-tuning using adversarial examples of the target task starting from the Free-4 robust ImageNet model similar to (Hendrycks et al., 2019); and (3) training a fully connected layer on top of the frozen feature extractors of the Free-4 robust ImageNet model using natural examples from the target task. For comparing the three different approaches, we look at three metrics: (a) clean validation accuracy; (b) robustness against PGD-20 validation adversarial examples; and (c) average of robustness and clean performance (((a)+(b))/2.) The results are summarized in Fig. 3. In the regimes where transfer learning is more common, adversarially robust transfer learning results in the best overall performance. Adversarially/Free training the target domain results in less robustness and validation accuracy compared to fine-tuning which highlights the importance of pre-training (Hendrycks et al., 2019). Note that in terms of computational resources required, the cost of fine-tuning on adversarial examples of the target domain is about k× our method since it requires generation of adversarial examples using k-step PGD attacks (we set k = 3).

heading: 4.2.1 TRAINING DEEPER NETWORKS ON TOP OF ROBUST FEATURE EXTRACTORS

text:
The basic transfer learning setting of section 4.1.1 only re-trains one layer for the new task. In section 4.1.1, when we transferred from the robust ImageNet to CIFAR-100, the natural training accuracy was 88.84%. Given the small number of trainable parameters left for the network (≈ 2048 × 100) and the fixed feature extractor, the network was not capable of completely fitting the training data. This means that there is potential to improve natural accuracy by learning more complex non-linear features and increasing the number of trainable parameters.
To increase representation capacity and the number of trainable parameters, instead of training a 1- layer network on top of the feature extractor, we train a multi-layer perceptron (MLP) network on top of the robust feature extractor. To keep things simple and prevent bottle-necking, every hidden layer we add has 2048 neurons. We plot the training and validation accuracies on the natural examples and
the robustness (i.e. PGD-20 validation accuracy) in Fig. 4 for various numbers of hidden layers. As can be seen, adding one layer is enough to achieve 100% training accuracy. However, doing so does not result in an increase in validation accuracy. To the contrary, adding more layers can result in a slight drop in validation accuracy due to overfitting. As illustrated, we can improve generalization using simple but effective methods such as dropout (Srivastava et al., 2014) (with probability 0.25) and batch-normalization (Ioffe & Szegedy, 2015).
However, the most interesting behavior we observe in this experiment is that, as we increase the number of hidden layers, the robustness to PGD-20 attacks improves. Note, this seems to happen even when we transfer from a naturally trained ImageNet model. While for the case where we have no hidden layers, robustness is 0.00% on CIFAR100 when we use a naturally trained ImageNet model as source, if our MLP has 1, 2, 3, or 5 hidden layers, our robustness against PGD attacks would be 0.03%, 0.09%, 0.31% and 6.61%, respectively. This leads us to suspect that this behavior may be an artifact of vanishing gradients for adversary as the softmax loss saturates when the data is fit perfectly (Athalye et al., 2018). Therefore, for this case we change our robustness measure and use the CW attack (Carlini & Wagner, 2017) which will encounter fewer numerical issues because its loss function does not have a softmax component and does not saturate. Attacking the model from the natural source with CW-20 completely breaks the model and achieves 0.00% robustness. Most interestingly, attacking the model transferred from a robust source using the CW objective maintains robustness even when the number of hidden layers increases.

heading: 5 ANALYSIS: ROBUST FEATURE EXTRACTORS ARE FILTERS

text:
Our experiments suggest that the robustness of neural networks arises in large part from the presence of robust feature extractors. We have used this observation to transfer both robustness and accuracy between domains using transfer-learning. However, we have not yet fully delved into what it means to have a robust feature extractor. Through visualizations, Tsipras et al. (2018) studied how adversarial training causes the image gradients of neural networks to exhibit meaningful generative behavior. In other words, adversarial perturbations on hardened networks “look like” the class into which the image is perturbed. Given that optimization-based attacks build adversarial examples using the image gradient, we also visualize the image gradients of our transferred models to see if they exhibit the same generative behavior as adversarially trained nets.
Fig. 5 plots the gradient of the loss w.r.t. the input image for models obtained by re-training only the last layer, and also for the case where we train MLPs on top of a robust feature extractor. The gradients for the transfer-learned models with a robust source are interpretable and “look like” the adversarial object class, while the gradients of models transferred from a natural source do not. This interpretatbility comes despite the fact that the source model was hardened against attacks on one dataset, and the transferred model is being tested on object classes from another. Also, we see that adding more layers on top of the feature extractor, which often leads to over-fitting, does not make gradients less interpretable. This latter observation is consistent with our observation that added layers preserve robustness(Fig. 4).
These observations, together with the success of robust transfer learning, leads us to speculate that a robust model’s feature extractors act as a “filter” that ignores irrelevant parts of the image.
Figure 5: Gradients of the loss w.r.t to input images for the CIFAR-100 transfer learning experiments of sections 4.1.1 & 4.2.1. The top row contains sample CIFAR-100 images. Other rows contain image gradients of the model loss. The second row is for a model transferred from a naturally trained ImageNet source. Rows 3-5 are for models transferred from a robust ImageNet source. These rows correspond to an MLP with 0 (row 3), 1 (row 4), and 2 (row 5) hidden layers on top of the robust feature extractor. The gradients in the last three rows all show interpretable generative behavior.

heading: 6 END-TO-END TRAINING WITHOUT FORGETTING

text:
As discussed in section 4, transfer learning can preserve robustness of the robust source model. However, it comes at the cost of decreased validation accuracy on natural examples compared to the case where we use a naturally trained source model. Consequently, there seems to be a trade-off between generalization and robustness based on the choice of the source model. For any given classifer, the trade-off between generalization and robustness is the subject of recent research (Tsipras et al., 2018; Zhang et al., 2019; Shafahi et al., 2019a). In this section, we intend to improve the overall performance of classifiers transferred from a robust source model by improving their generalization on natural images. To do so, unlike previous sections where we froze the feature extractor mainly to preserve robustness, we fine tune the feature extractor parameters θ. Ideally, we should learn to perform well on the target dataset without catastrophically forgetting the robustness of the source model. To achieve this, we utilize lifelong learning methods.
Learning without Forgetting (LwF) (Li & Hoiem, 2018) is a method for overcoming catastrophic forgetting. The method is based on distillation. In this framework, we train the target model with a loss that includes a distillation term from the previous model.
min w,θ
l(z(x, θ), y, w) + λd · d(z(x, θ), z0(x, θ∗r)) (3)
where, in our method, λd is the feature representation similarity penalty, and d is some distance metric between the robust model’s feature representations z0(x, θ∗r) and the current model’s feature representations z(x, θ). Unlike the original LwF paper that used a distilled loss from Hinton et al. (2015) and applies distillation to the logits, we simply choose d to be the `2-norm and apply
distillation to the penultimate layer5. Our loss is designed to make the feature representations of the source and target network similar, thus preserving the robust feature representations (Fig. 6). Ideally, z(x, θ) ≈ z(x, θ∗r). To speed up training, given robust feature extractor parameters θ∗r , we store z0(x, θ∗r) for the images of the target task and load this from memory (i.e. offline) instead of performing a forward pass through the robust source network online. Therefore, in the experiments related to LwF, we do not train with data augmentation because we have not pre-computed z(xa, θ ∗ r), where xa is the augmented image. Empirically we verified that d(z(x, θ ∗ r), z(xa, θ ∗ r)) was not negligible6.
To improve performance, we follow a warm-start scheme and only train the fully connected parameters w early in training. We then cut the learning rate and continue fine tuning both feature extractors (θ) and w. In our experiments, we use a learning rate of 0.001, and the warm-start makes up half of the total training iterations. Starting from the pre-trained source model, we train for a total of 20,000 iterations with batch-size 128. The results with an adversarially trained CIFAR-100 model as source and CIFAR-10 as target are summarized in Table 4.7
As can be seen, having a LwF-type regularizer helps in maintaining robustness and also results in a considerable increase in validation accuracy. The trade-off between robustness and generalization can be controlled by the choice of λd. It seems that for some choices of λd such as 0.1, robustness also increases. However, in hindsight, the increase in accuracy on PGD-20 adversarial examples is not solely due to improvement in robustness. It is due to the fact that the validation accuracy has increased and we have a better classifier overall. For easier comparisons, we have provided the transfer results without LwF at the bottom of Table 4. Note that using LwF, we can keep the robustness of the source model and also achieve clean validation accuracy comparable to a model that uses naturally trained feature extractors. In the supplementary, we show that similar conclusions can be drawn for the split CIFAR-100 task.
We demonstrated in our transfer experiments that using our LwF-type loss, can help decrease the generalization gap while preserving robustness. In this section, we assume that the source domain is the adversarial example domain of a dataset and the target domain is the clean example domain of the same dataset. This experiment can be seen as applying transfer learning from the adversarial example domain to the natural example domain while preventing forgetting the adversarial domain.
In the case where the source and target datasets are the same (Transferring from a robust CIFAR-100 model to CIFAR-100), by applying our LwF-type loss, we can improve the generalization of robust models. Our results are summarized in Table 5.
5We do so since in section 3 we found the source of robustness to be the feature extractors and this observation was later reinforced due to the empirical results in section 4
6The analysis is in the supplementary. 7Source code for LwF-based experiments: https://github.com/ashafahi/RobustTransferLWF

heading: 7 CONCLUSION

text:
We identified the feature extractors of adversarially trained models as a source of robustness, and use this observation to transfer robustness to new problems domains without adversarial training. While transferring from a natural model can achieve higher validation accuracy in comparison to transferring from a robust model, we can close the gap and maintain the initial transferred robustness by borrowing ideas from the lifelong learning literature. The success of this methods suggests that a robust feature extractor is effectively a filter that sifts out relevant components of an image that are needed to assign class labels. We hope that the insights from this study enable practitioners to build robust models in situations with limited labeled training data, or when the cost and complexity of adversarial training from scratch is untenable.
Acknowledgements: Goldstein and his students were supported by the DARPA QED for RML program, the DARPA GARD program, and the National Science Foundation.

heading: A EXPERIMENT DETAILS

text:
A.1 LWF-BASED EXPERIMENTS
In our LWF-based experiments, we use a batch-size of 128, a fixed learning-rate of 1e-2m, and fine-tune for an additional 20,000 iterations. The first 10,000 iterations are used for warm-start; during which we only update the final fully connected layer’s weights. During the remaining 10,000 iterations, we update all of the weights but do not update the batch-normalization parameters.
A.2 IMAGENET TO CIFAR EXPERIMENTS
When freezing the feature extractor and fine-tuning on adversarial examples, we train the last fully connected layer’s weights for 50 epochs using batch-size=128. We start with an initial learning rate of 0.01 and drop the learning rate to 0.001 at epoch 30. In the case of fine-tuning on adversarial examples, we generate the adversarial examples using a 3 step PGD attack with step-size 3 and a perturbation bound = 5.
A.3 FREE TRAINING EXPERIMENTS
In all of our free-training experiments where we train the u-ResNet-50, we train for 90 epochs using a batch-size of 128. The initial learning rate used is 0.1 and we drop it by a factor of 10 at epochs 30 and 60. We use a replay parameter m = 4 and perturbation bound = 5.

heading: B THE DISTANCE BETWEEN FEATURE REPRESENTATIONS OF NATURAL IMAGES AND AUGMENTED IMAGES

text: To speed up the LwF experiments, we did not use data augmentation during training. Instead of computing the robust feature representations on the fly, before starting training on the new target task, we passed the entire training data of the target task through the robust network and stored the feature representation vector. If we were doing data augmentation, we would have to pass the entire augmented training data through the network, which would be slow and memory intensive. Alternatively, we could use the robust feature representation of the non-augmented images instead. The latter would have been feasible if the distance between the robust feature representations of the non-augmented and augmented images were very small. However, as shown in fig 7, this quantity is not often negligible.

heading: C LOW-DATA REGIME TRANSFER LEARNING FROM IMAGENET TO

text:
CIFAR-10
In section 4.2, we illustrated that robust transfer learning is most beneficial where we have limited data (i.e., limited number of training data per class). We used CIFAR-100 as an illustrative target dataset. However, the overall results are not data set dependent. When we have limited number of training data, robust transfer learning results in the highest overall performance (see Fig. 8 for transferring from a robust ImageNet model to smaller instances of CIFAR-10).

heading: D LWF-BASED ROBUST TRANSFER LEARNING FOR SIMILAR SOURCE AND TARGET DATASETS

text:
In Table 6 we conduct LwF experiments on the split CIFAR-100 task which is more suited for transfer learning due to the similarities between the source and target datasets. In these situations, the LwF regularizer on the feature representations still works and can improve generalization without becoming vulnerable to adversarial examples. If we take the average performance of the robust classifiers on the split tasks (average of robust half CIFAR-100 and the LwF setting model for λd = 0.01) we get (63.32 + 64.96)/2 = 64.14% average validation accuracy and 20.42% average robustness which is comparable with the case that we had adversarially trained the entire CIFAR-100 dataset (Table 1).
E IMPROVING GENERALIZATION OF THE CIFAR-10 ADVERSARIALLY TRAINED MODEL
Similar to the case of improving the generalization for CIFAR-100, we use our LwF-based loss function to transfer from the robust CIFAR-10 domain to the natural CIFAR-10 domain. We summarize the results in Table 7.

title: ADVERSARIALLY ROBUST TRANSFER LEARNING


summaries: This paper proposed a neural iterated learning algorithm to encourage the dominance of high compositional language in the multi-agent communication game. The author shows that the iterative training of two agents playing a referential game can incrementally increase the agent to use the language with high topological similarity. The authors also demonstrated that topological similarity is correlated with zero-shot performance. And Experiment results show the authors could propose alternative pre-training strategies for the neural agent can prefer high compositional language and achieve high task performance.

summaries: This paper studies the emergence of compositional language in neural agents. They propose an iterated learning method that consists of three phases: a supervised learning phase for a randomly-initialized speaker and listener, a self-play phase (where both agents are updated together), and a phase where a new dataset is created based on the current speaker’s language. This dataset is then passed on to the next ‘generation’ of speaker and listener. The paper finds that this procedure, with the right hyperparameters, leads to the emergence of more compositional languages in a simple symbolic referential game.

summaries: The paper "Compositional languages emerge in a neural iterated learning model" address the problem of language emergence in two-players games. In particular, the authors proposed a neural iterated learning model which seeks comopsitional languages. Authors claim that compositional languages are easier to be learned and that they allow listeners to more easily understand provided messages.

abstractText: The principle of compositionality, which enables natural language to represent complex concepts via a structured combination of simpler ones, allows us to convey an open-ended set of messages using a limited vocabulary. If compositionality is indeed a natural property of language, we may expect it to appear in communication protocols that are created by neural agents in language games. In this paper, we propose an effective neural iterated learning (NIL) algorithm that, when applied to interacting neural agents, facilitates the emergence of a more structured type of language. Indeed, these languages provide learning speed advantages to neural agents during training, which can be incrementally amplified via NIL. We provide a probabilistic model of NIL and an explanation of why the advantage of compositional language exist. Our experiments confirm our analysis, and also demonstrate that the emerged languages largely improve the generalizing power of the neural agent communication.

title: Measuring compositionality in representation learning

venue: arXiv preprint arXiv:1902.07181,

authors:
Laura Banarescu
Claire Bonial
Shu Cai
Madalina Georgescu
Kira Griffitt
Ulf Hermjakob
Kevin Knight
Philipp Koehn
Martha Palmer
Nathan Schneider

title: Abstract meaning representation for sembanking

venue: In Proceedings of the 7th Linguistic Annotation Workshop and Interoperability with Discourse,

title: Compositional syntax from cultural transmission

venue: Artificial life,

authors:
Henry Brighton
Simon Kirby

title: Understanding linguistic evolution by visualizing the emergence of topographic mappings

authors:
Jon W Carr
Kenny Smith
Hannah Cornish
Simon Kirby

title: The cultural evolution of structured languages in an open-ended, continuous world

venue: Cognitive science,

authors:
Edward Choi
Angeliki Lazaridou
Nando de Freitas

title: Compositional obverter communication learning from raw visual input

venue: In International Conference on Learning Representations,

authors:
Michael Cogswell
Jiasen Lu
Stefan Lee
Devi Parikh
Dhruv Batra

title: Emergence of compositional language with deep generational transmission

authors:
Jakob Foerster
Ioannis Alexandros Assael
Nando de Freitas
Shimon Whiteson

title: Learning to communicate with deep multi-agent reinforcement learning

authors:
Serhii Havrylov
Ivan Titov

title: Emergence of language with multi-agent games: Learning to communicate with sequences of symbols

authors:
Sepp Hochreiter
Jürgen Schmidhuber

title: Long short-term memory

venue: Neural computation,

authors:
Simon Kirby
James R Hurford

title: The emergence of linguistic structure: An overview of the iterated learning model

venue: In Simulating the evolution of language,

authors:
Simon Kirby
Tom Griffiths
Kenny Smith

title: Iterated learning and the evolution of language

venue: Current opinion in neurobiology,

authors:
Simon Kirby
Monica Tamariz
Hannah Cornish
Kenny Smith

title: Compression and communication in the cultural evolution of linguistic structure

authors:
Satwik Kottur
José Moura
Stefan Lee
Dhruv Batra

title: Natural language does not emerge naturallyin multi-agent dialog

venue: In Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing,

authors:
Angeliki Lazaridou
Karl Moritz Hermann
Karl Tuyls
Stephen Clark

title: Emergence of linguistic communication from referential games with symbolic and pixel input

title: Binary codes capable of correcting deletions, insertions, and reversals

venue: In Soviet physics doklady,

title: Convention: A philosophical study

authors:
Fushan Li
Michael Bowling

title: Ease-of-teaching and language structure from emergent communication

venue: arXiv preprint arXiv:1906.02403,

authors:
Christopher D Manning
Hinrich Schütze

title: Foundations of statistical natural language processing

venue: MIT press,

authors:
Volodymyr Mnih
Adria Puigdomenech Badia
Mehdi Mirza
Alex Graves
Timothy Lillicrap
Tim Harley
David Silver
Koray Kavukcuoglu

title: Asynchronous methods for deep reinforcement learning

venue: In International Conference on Machine Learning,

authors:
Igor Mordatch
Pieter Abbeel

title: Emergence of grounded compositional language in multi-agent populations

venue: In Thirty-Second AAAI Conference on Artificial Intelligence,

title: The nature of statistical learning theory

venue: Springer science & business media,

title: Simple statistical gradient-following algorithms for connectionist reinforcement learning

venue: Machine learning,

heading: 1 INTRODUCTION

text:
Natural language understanding (NLU), which is exemplified by challenging problems such as machine reading comprehension, question answering and machine translation, plays a crucial role in artificial intelligence systems. So far, most of the existing methods focus on building statistical associations between textual inputs and semantic representations, e.g. using first-order logic (Manning et al., 1999) or other types of representations such as abstract meaning representation (Banarescu et al., 2013). Recently, grounded language learning has gradually attracted attention in various domains, inspired by the hypothesis that early language learning was focused on problemsolving (Kirby & Hurford, 2002). While related to NLU, it focuses on the pragmatics (Clark, 1996) of learning natural language, as it implies learning language from scratch, grounded in experience. This research is often practiced through the development of neural agents which are made to communicate with each other to accomplish specific tasks (for example, playing a game). During this process, the agents build mappings between the concepts they wish to communicate about and the symbols used to represent them. These mappings are usually referred to as ‘emergent language’.
So far, an array of recent work (Havrylov & Titov, 2017; Mordatch & Abbeel, 2018; Kottur et al., 2017; Foerster et al., 2016) has shown that in many game settings, the neural agents can use their emergent language to exchange useful coordinating information. While the best way to design games to favour language emergence is still open to debate, there is a consensus on the fact that we should gear these emergent languages towards sharing similarities with natural language. Among the properties of natural language, compositionality is considered to be critical, because it enables representation of complex concepts through the combinination of several simple ones. While work on incorporating compositionality into emergent languages is still in its early stage, several experiments have already demonstrated that by properly choosing the maximum message length and vocabulary size, the agents can be brought together to develop a compositional language that shares similarities with natural language (Li & Bowling, 2019; Lazaridou et al., 2018; Cogswell et al., 2019).
In a different body of language research literature, evolutionary linguists have already studied the origins of compositionality for decades (Kirby & Hurford, 2002; Kirby et al., 2014; 2015). They
proposed a cultural evolutionary account of the origins of compositionality and designed a framework called iterated learning to simulate the language evolution process, based on the idea that the simulated language must be learned by new speakers at each generation, while also being used for communication. Their experiments show that highly compositional languages may indeed emerge through iterated learning. However, the models they introduced were mainly studied by means of experiments with human participants, in which the compositional languages is favored by the participants because human brain favors structure. Hence, directly applying this framework to ground language learning is not straightforward: we should first verify the existence of the preference of compositional language at the neural agent, and then design an effective training procedure for the neural agent to amplify such an advantage.
In this project, we analyze whether and how the learning speed advantage of the highly compositional languages exists in the context of communication between neural agents playing a game. Then we propose a three-phase neural iterated learning algorithm (NIL) and a probabilistic explanation of it. The experimental results demonstrate that our algorithm can significantly enhance the topological similarity (Brighton & Kirby, 2006) between the emergent language and the original meaning space in a simple referential game (Lewis, 1969). Such highly compositional languages also generalize better, because they perform well on a held-out validation set. We highlight our contribution as:
• We discover the learning speed advantages of languages with high topological similarity for neural agents communicating in order to play a referential game.
• We propose the NIL based on those advantages, which is quite robust compared to most of the related works.
• We propose a probabilistic framework to explain the mechanisms of NIL.

heading: 2 BACKGROUND

heading: 2.1 REFERENTIAL GAME

text:
We analyze a typical and straightforward object selection game, in which a speaking agent (Alice, or speaker) and a listening agent (Bob, or listener) must cooperate to accomplish a task. In each round of the game, we show Alice a target object x selected from an object space X and let her send a discrete-sequence message m to Bob. We then show Bob c different objects (x must be one of them) and use c1, ..., cc ∈ X to represent these candidates. Bob must use the message received from Alice to select the object that Alice refers among the c candidates. If Bob’s selection c̄ is correct, both Alice and Bob are rewarded. The objects are shuffled and candidates are randomly selected in each round to avoid the agents recognizing the objects using their order of presentation.
In our game, each object in X has Na attributes (color and shape are often used in the literature), and each attribute has Nv possible values. To represent objects, similarly to the settings chosen in (Kottur et al., 2017), we encode each attribute as a one-hot vector and concatenate the Na one-hot vectors to represent one object. The message delivered by Alice is a fixed-length discrete sequence m = (m1, ...,mNL), in which each mi is selected from a fixed size meaningless vocabulary V .

heading: 2.2 NEURAL AGENT STRUCTURES

text:
Neural agents usually have separate modules for speaking and listening, which we name Alice and Bob. Their architectures, shown in Figure 1, are similar to those studied in (Havrylov & Titov, 2017) and (Lazaridou et al., 2018). Alice first applies a multi-layer perceptron (MLP) to encode x into an embedding, then feeds it to an encoding LSTM (Hochreiter & Schmidhuber, 1997). Its output will go through a softmax layer, which we use to generate the message m1,m2, · · · . Bob uses a decoding LSTM to read the message and uses a MLP to encode c1, ..., cc into embeddings. Bob then takes the dot product between the hidden states of the decoding LSTM and the embeddings to generate scores sc for each object. These scores are then used to calculate the cross-entropy loss when training Bob. When Alice and Bob are trained using reinforcement learning, we can use pA(m|x; θA) and pB(c̄|m, c1, ..., cc; θB) to represent their respective policies, where θA and θB contain the parameters of each of the neural agents. When the agents are trained to play the game together, we use the REINFORCE algorithm (Williams, 1992) to maximize the expected reward under their policies, and add the entropy regularization term to encourage exploration during training, as explained in (Mnih et al., 2016). The gradients of the objective function J(θA, θB) are:
∇θAJ = E [R(c̄, x)∇ log pA(m|x)] + λA∇H[pA(m|x)] (1) ∇θBJ = E [R(c̄, x)∇ log pB(c̄|m, c1, ..., cc)] + λB∇H[pB(c̄|m, c1, ..., cc)], (2)
where R(c̄, x) = 1(c̄, x) is the reward function, H is the standard entropy function, and λA, λB > 0 are hyperparameters. A formal definition of the agents can be found in Appendix C.

heading: 2.3 MEASURING COMPOSITIONALITY

text:
Compositionality is a crucial feature of natural languages, allowing us to use small building blocks (e.g., words, phrases) to generate more complex structures (e.g., sentences), with the meaning of the larger structure being determined by the meaning of its parts (Clark, 1996). However, there is no consensus on how to quantitatively assess it. Besides a subjective human evaluation, topological similarity has been proposed as a possible quantitative measure (Brighton & Kirby, 2006).
To define topological similarity, we first define the language studied in this work as L(·) : X 7→ M. Then we need to measure the distances between pairs of objects: ∆ijX = dX (xi, xj), where dX (·) is a distance in X . Similarly, we compute the corresponding quantity for the associated messages mi = L(xi) in the message space M with ∆ijM = dM (mi,mj), where dM(·) is a distance in M. Then the topological similarity (i.e., ρ) is defined as the correlation between these quantities across X . Following the setup of (Lazaridou et al., 2018) and (Li & Bowling, 2019), we use the negative cosine similarity in the object space and Levenshtein distances (Levenshtein, 1966) in the message space. We provide an example in Appendix B to give a better intuition about this metric.

heading: 3 NEURAL ITERATED LEARNING MODEL

text: The idea of iterated learning requires the agent in current generation be partially exposed to the language used in the previous generation. Even this idea is proven to be effective when experimenting with human participants, directly applying it to games played by neural agents is not trivial: for example, we are not sure where to find the preference for high-ρ languages for the neural agents. Besides, we must carefully design an algorithm that can simulate the “partially exposed” procedure, which is essential for the success of iterated learning.

heading: 3.1 LEARNING SPEED ADVANTAGE FOR THE NEURAL AGENTS

text:
As mentioned before, the preference of high-ρ language by the learning agents is essential for the success of iterated learning. In language evolution, highly compositional languages are favored because they are structurally simple and hence are easier to learn (Carr et al., 2017). We believe that a similar phenomenon applies to communication between neural agents:
Hypothesis 1: High topological similarity improves the learning speed of the speaking neural agent.
We speculate that high-ρ languages are easier to emulate for a neural agent than low-ρ languages. Concretely, that means that Alice, when pre-trained with object-message pairs describing a high-
ρ language at a given generation, will be faster to successfully output the right message for each object. Intuitively, this is because the structured mapping described by a language with high ρ is smoother, and hence has a lower sample complexity, which makes resulting examples easier to learn for the speaker agent (Vapnik, 2013).
Hypothesis 2: High topological similarity allows the listening agent to successfully recognize more concepts, using less samples.
We speculate that high-ρ languages are easier for a neural agent to recognize. That means that Bob, when pre-trained with message-object pairs corresponding to a high-ρ language, will be faster to successfully choose the right object. Intuitively, the lower topological similarity is, the more difficult it will be to infer unseen object-message pairs from seen examples. The more complex mapping of a low-ρ language implies that more object-message pairs need to be provided to describe it. This translates as an inability for the listening agent to generalize the information it obtained from one object-message associated to a low-ρ language to other examples. Thus, the general performance of Bob on any example will improve much faster when trained with pairs corresponding to a high-ρ language than with a low-ρ language. We provide experimental results in section 4.1 to verify our hypotheses. We also provide a detailed example in Appendix D to illustrate our reasoning.

heading: 3.2 NEURAL ITERATED LEARNING AND PROBABILISTIC ANALYSIS

text:
We design the NIL algorithm to exploit these advantages in a robust manner, as detailed in Algorithm 1. The algorithm runs for I generations: at the beginning of each generation i, both the agents are reinitialized. As Alice and Bob have different structures, they are then pre-trained differently (see line 5-7 for Alice and line 8-12 for Bob): this is the learning phase. Alice is pre-trained via categorical cross-entropy, using the data generated at the previous generation, which we denote Di. Bob is pretrained with REINFORCE, learning from the pre-trained Alice. We note Ia and Ib their respective number of pre-training iterations. With hypothesis 1, the expected ρ of the language spoken by Alice should be higher than that of Di. Meanwhile, Bob shold be more “familiar with” the language with a higher ρ than Di, as stated by hypothesis 2. Alice and Bob then play the game together for Ig rounds in the interacting phase, in which both agents are updated via REINFORCE. In this phase, the languages used by them are filtered to be more unambiguous — their language must deliver information accurately to accomplish the task. Finally, in the transmitting phase, we feed all objects to Alice and let it output the corresponding messages to be stored in Di+1 for the learning phase of the next generation.
To better understand how NIL enhances the expected ρ of the languages generation by generation, we propose a probabilistic model for NIL in Appendix C, as well as a probabilistic analysis of the role played by Alice and Bob in every phase. Intuitively, at the beginning of each generation, the expected ρ of language used by Alice (denoted by EL[ρ(L)]) is quite low because of the random initialization. Then during the learning phase, Alice learns from Di and expected to have the same EL[ρ(L)] with Di if it perfectly learns that data set. However, as the high-ρ language is favored by neural agent during training, the EL[ρ(L)] of the weakly pre-trained Alice should be higher than that of Di. A similar thing may happen when pre-training Bob. Then in the interacting phase, as the game performance has no preference for language with different ρ, EL[ρ(L)] will not change in this phase.1 Finally, in the transmitting phase, Di+1 is sampled based on the language with current EL[ρ(L)], which is expected to be higher than that of Di. In other words, EL[ρ(L)] would increase generation by generation (the details for derivations are provided in Appendix C):
EL∼Di+1 [ρ(L)] ≥ EL∼Di [ρ(L)]. (3)

heading: 4 EXPERIMENTS AND DISCUSSIONS

text:
In this section, we first verify hypotheses 1 and 2 by directly feeding languages with different ρ to Alice and Bob. Then we examine the behavior and performance of the neural agents, as well as the expected ρ of languages, at each generation. We conduct an ablation study, to examine the effect of pre-training Alice and Bob separately. We then investigate more thoroughly the advantages
1The role of interacting phase is to filter out those ambiguous language. This may change EL[ρ(L)], but without a preference for language with specific ρ.
Randomly initialize D1 for i = 1, 2, ..., I do
Re-initialize Alice and Bob, get Alicei and Bobi // ======= Learning Phase ======= for ia = 1, 2, ..., Ia do
Randomly sample an example pair from Di and use it to update Alicei with cross-entropy training
end for for ib = 1, 2, ..., Ib do
Alicei generates message based on input objects Bobi receives message and selects the target Bobi updates its parameters if rewarded
end for // ======= Interacting Phase ======= for ig = 1, 2, ..., Ig do
Alicei generates message based on input objects Bobi receives message and selects the target BOTH Alicei and Bobi update parameters if rewarded
end for // ======= Transmitting Phase ======= for is = 1, 2, ..., Is do
Generate object-message pairs by feeding objects to Alicei and save them to data set Di+1 end for end for Algorithm 1: The NIL algorithm. Ia, Ib and Ig are the number of iterations used to pre-train Alice, Bob, and to play the game at each generation.
brought by high-ρ languages, and highlight the ‘interval of advantage’ in pre-training rounds, which could help in selecting reasonable Ia and Ib. Finally, we conduct a series of experiments on a held-out validation set to highlight the positive effect of high-ρ languages on the neural agents generalization ability — which shows the potential of iterated learning for NLU tasks. Details about our experimental setup and our choice of hyper-parameters can be found in Appendix A. More experiments about the robustness of NIL are presented in Appendix E.

heading: 4.1 LEARNING SPEED ADVANTAGES

text:
We first use the experimental results in Figure 2 to verify hypotheses 1 and 2. In these experiments, we randomly initialize one Alice and feed languages with different expected ρ for it to learn (and repeat the same procedure for Bob). We generate a perfect high-ρ language (ρ = 1) using the method proposed in (Kirby et al., 2015), and randomly permute the messages to generate a low-ρ language with ρ = 0.21. The other languages are intermediate languages generated during NIL. Note that there is no interacting nor transmitting phase in the experiment in this subsection: we only test the learning behavior of a randomly initialized Alice (or Bob) separately.
From the result in Figure 2-(a) and (b), we see that the high-ρ languages indeed has the learning speed advantage at both the speaker and the listener side. One important finding is in Figure 2-(c), which record the expected ρ, i.e., EL[ρ(L)], during Alice’s learning. From this figure, we find that when learning a language with low expected ρ, the value of EL[ρ(L)] will first increase, and finally converge to the ρ of D. This phenomenon, caused by the learning speed advantage, makes the weak pre-train the essential design for the success of NIL: if Ia is correctly chosen, we may expect a higher EL[ρ(L)] than that of the data set it learns from.

heading: 4.2 PERFORMANCE OF NIL

text:
In this part, we record the game performance (i.e., the rate of successful object selections) and mean ρ of the object-message pairs exchanged by the neural agents every 20 rounds. We run the simulation 10 times, with a different random number seed each time. Although the results are different, they
all follow the same trend. In this first series of experiments, we compare the following 4 different methods:
• Iterated learning, with resetting both Alice and Bob at the beginning of each generation. • Iterated learning, only resetting Alice at the beginning of each generation; • Iterated learning, only resetting Bob at the beginning of each generation; • No iterated learning: neither Alice nor Bob are reset during training.
From Figure 3-(a), we can see that for the 3 displayed variants of the procedure, neural agents can play the game almost perfectly after a few generations. The curve of the no-reset method will directly converge while the curves of the other two iterated learning procedures will show a loss of accuracy at the beginning of each generation. That is because one or both agents are reset, and are not able to completely re-learn from the data kept from the previous generation during the pre-training phase. However, at the end of each generation, all these algorithms can ensure a perfect game performance.
While the use of NIL has little effect on the game performance, given a sufficient number of rounds, these procedures have a clear positive effect on topological similarity. In Figure 3-(b), we can see that the no-reset case has the lowest average ρ while the iterated learning cases all have higher means (and increasing). We provide extra experiments in Appendix E, which demonstrate the robustness of NIL under different scenarios. The discussion on the specific impact of each agent and why the reset-Alice and reset-Bob behave differently is in Section 5.

heading: 4.3 HIGH TOPOLOGICAL SIMILARITY AND INTERVAL OF ADVANTAGE

text:
In this section, we explore further the phenomenon caused by the learning speed advantage on NIL. From the discussion in section 3.1 and the experimental results in section 4.1, we know that Ia and Ib play an important role in NIL: they should not be too large nor too small. Intuitively, if Ia is too small, Alice will learn nothing from the previous generation, hence the NIL amounts to playing
only one interacting phase. If Ia is too large, from the trend in Figure 2-(c), we may expect that the increase of expected ρ should be small in each generation, because Alice will perfectly learn Di, and hence have a ρ similar to its predecessor. Hence we speculate that the value of Ia should have a “bottleneck” effect, i.e., a too large one or a too small one will both harm the performance of NIL. A similar argument can also applied in the selection of Ib.
To verify our argument, we run NIL with different values of Ia and Ib, examining the behavior of the following 3 different quantitive metrics:
• E[r71:80]: The average reward of the last ten generations (game performance); • E[ρ1:10]: The average value of ρ for the first ten generations (converging speed); • E[ρ71:80]: The average value of ρ for the last ten generations (converged ρ).
From the results presented in Table 1, we can see the importance of the number of pre-training rounds not being too large nor too small. The suitable Ia and Ib are shown in bold. Furthermore, combining Figure 2 and Table 1, the interval of suitable Ia lies between 1000 to 2000 while it lies between 100 to 200 for Ib, which provides us an effective way to choosing hyper-parameters.

heading: 4.4 TOPOLOGICAL SIMILARITY AND VALIDATION PERFORMANCE

text: In this last series of experiments, we aim to explore the relationship between topological similarity and the generalisation ability of our neural agents, which can also indirectly reflect the expressivity of a language. We measure this ability by looking at their validation game performance: we restrict the training examples to a limited numbers of objects (i.e., the training set), and look at how good are the agents at playing the game on the others (i.e., the validation set). Figure 4-(a) demonstrates the strength of the iterated learning procedure in a validation setting. To illustrate the relationship between ρ and validation performance, we randomly choose Ia ∈ [60, 4000] and Ib ∈ [5, 200] and conduct a series of experiments. Those for which Ia and Ib are not in their optimal range will yield a worse performance on both validation test and topological similarity. In Figure 4-(b), we record the results from different experimental settings and draw the zero-shot performance given the topological similarity of the emergent language. This shows the linear correlation between these two metrics, and a significance test confirms it: the correlation coefficient is 0.928, and the associated p-value is 3.8 ∗ 10−104. Hence, under various experimental settings, the validation performance and the topological similarity are strongly correlated. Table 2 shows that when the size of validation set increases, using iterated learning can always improve the validation performance: in all the cases, both-reset algorithm always yields the best performance. The fact that the Alice-reset setting performs better than the Bob-reset setting also matches our analysis well.

heading: 5 DISCUSSION: A PARALLEL WITH LANGUAGE EVOLUTION

text:
We can observe an interesting phenomenon in Figure 3-(b):2 the topological similarity of the emergent language always increases at first, whether we use iterated learning or not. This is akin to the effect apparent for ρ in Figure 2-(c): continuing training will imply fine-tuning to examples that
2This can be viewed in more details when looking at the probabilistic analysis presented in Appendix D.
are not necessarily of good quality. However, through the generational resets and limited number of pre-training examples, iterated learning allows small generational improvements: this is because constraining the agent to learn with smaller amounts of data at each generation — through a ‘bottleneck’ (Kirby & Hurford, 2002) — forces the emergence of a more structured language. This limitation on the amounts of data available corresponds in our algorithm to limiting the number of pre-training rounds of the agents, to a number in what we denoted as the ‘interval of advantage’. In NIL, we use the weak pre-training to simulate this bottleneck, and achieve a good result: the values of Ia and Ib have an effect similar to the bottleneck studied in (Kirby et al., 2015) (more details are provided in Appendix D). Extending this parallel with the evolution of natural language, we can relate the learning speed advantage provided by high-ρ languages to the speaking agent to the compressibility pressure (Kirby et al., 2015), and the better ability to generalize provided by high-ρ languages to the listening agent to the expressivity pressure (Kirby et al., 2015).
This comparison allows us to address one important difference between our neural iterated learning algorithm and the original version: our speaking and listening agents are not identical. Actually, the speaking module and listening module of human are also not identical, but the works on traditional iterated learning do not pay much attention to such differences. From Figure 3-(b) and Figure 4-(a), it is clear that Alice and Bob are affected differently by the generational resets, and thus do not offer the same contribution to the final performance.3 From this parallel, we retain that iterated learning is also linked to the emergence of a certain form of compositionality when applied to neural agents. Besides, we believe that the correlation between topological similarity and validation performance that we highlight in Section 4.4 is another argument in favor of a relationship between compositionality and generalization, which has recently been explored (Kottur et al., 2017; Choi et al., 2018; Andreas, 2019).
3However, this parallel may not explain how differently they contribute to gains in topological similarity, since we must factor in the differences between their pre-training procedures, and especially the fact that Alice is pre-trained by minimizing cross-entropy.

heading: 6 CONCLUSION

text: In this paper, we find and articulate the existence of the learning speed advantages offered by high topological similarity, with which, we propose the NIL algorithm to encourage the dominance of high compositional language in a multi-agent communication game. We show that our procedure, consisting in resetting neural agents playing a referential game and pre-training them on data generated by their predecessors, can incrementally advantage emergent languages with high topological similarity. We demonstrate its interest by obtaining large performance improvements in a validation setting, linking compositionality and ability to generalize to new examples. The robustness of the algorithm is also verified in various experimental settings. Finally, we hope the proposed probabilistic model of NIL could inspire the application of NIL in more complex neural-agents-based systems.

heading: ACKNOWLEDGEMENT

text:
We show our sincere gratitude to Kenny Smith, Ivan Titov, Stella Frank and Serhii Havrylov for their helpful discussion and comments that greatly improved the manuscript.
We would also like to thank the members from Prof. Jun Zhao’s team at Institute of Automation, Chinese Academy of Sciences, e.g. Dr. Kang Liu, Xiang Zhang and Xinyu Zuo, for sharing computing resources to run some experiments as well as sharing their pearls of wisdom with us during the course of this research, and we thank 3 anonymous reviewers for their insights and comments.

heading: APPENDIX A: PARAMETER SETTINGS

text: Unless specifically stated, the experiments mentioned in this paper use the hyper-parameters given in Table 3. The code is available at https://github.com/Joshua-Ren/Neural_ Iterated_Learning.

heading: APPENDIX B: DIFFERENT TYPES OF LANGUAGES: A TOY EXAMPLE

text:
To better understand how topological similarity can measure the compositionality of one language, and to give some intuitions on how languages having different ρ would like, we provide and illustrate a toy example in this appendix. In this example, the object space is X = {blue box, blue circle, red box, red circle} and the message space is M = {aa, ab, ba, bb}. Any
set of mappings from four distinct objects to four messages (not necessarily distinct, i.e. same message could correspond to different objects) forms a language. Hence, there exist 44 = 256 possible languages in this toy example. Following the principles provided in (Kirby et al., 2015), we define the following concepts for describing a language:
• Unambiguous language. A type of language that can unambiguously describe all objects in X . In other words, the mappings between X and M are bijectional. In this example, there exist 4× 3× 2× 1 = 24 such languages.
• Compositional language. A type of unambiguous language that exhibits systematic compositional structure when forming messages. Such languages can use different symbols to represent different attributes of meaning and combine these symbols in a systematic way to form a message such that the meaning of the whole message is formed from a simple combination of the meaning of its parts. For example, following the rules of S → XY , and X : blue → b;X : red :→ b;Y : box → a;X : circle :→ b, we can derive a compositional language like the example in Table 4. In this example, we have 4 + 4 = 8 such languages.
• Holistic language. A type of unambiguous language but does not exhibits full systematic structures. In other words, holistic languages are those unambiguous language who are not compositional languages. In this example, we have 24− 8 = 16 such languages.
• Degenerate language. A type of ambiguous language that maps all objects to the same message. In this example, we have 4 such languages.
• Degenerate component. Any ambiguous language having degenerate component, i.e., there may be more than one objects mapping to the same message. The existence of degenerate component makes the language ambiguous.
Note that the number of unambiguous languages is usually much smaller than that of ambiguous languages, and the number of compositional languages is usually smaller than that of holistic languages. Using permutation and combination, we can calculate the numbers of all possible languages, unambiguous language, compositional language and holistic language as:
# all possible languages = ( |V |NL )(NNav ) (4) # unambiguous languages =
(|V |NL)! (|V |NL −NNav )!
(5)
# compositional languages = NL! (NL −Na)! · ( |V |! (|V | −Nv)! )Na (6)
# holistic languages = # unambiguous languages −# compositional languages (7)
From the above equation, it is easy to see that the gap between the number of compositional languages and holistic languages would become larger when Nv , Na, NL and |V | increase. Further, this means that it becomes even harder to pick a compositional language when randomly sample a language. That could explain why the expected topological similarity of the emergent language may increase when smaller NL and |V | are applied, as illustrated in (Lazaridou et al., 2018; Cogswell et al., 2019).
Besides the numbers of different languages, another key difference among these languages is the topological similarity (i.e., ρ), as illustrated in section 2.3. As the language studied in this paper is defined as a mapping function from a meaning (i.e., an object) to a message, a compositional language must ensure that the meaning of a symbol is a function of the meaning of its parts. In other words, compositional languages are neighborhood related: nearby meanings tend to be mapped to nearby signals. Or to say, nearby meanings that share similar attributes are likely to share similar message symbols (Brighton & Kirby, 2006). Thus, as the difference between messages are measured by edit distance, the compositional languages will have a higher ρ than the holistic ones. However, the existence of degenerate component also change the value of ρ: the ρ of a degenerate language might be higher than that of a holistic language.
From the above discussions, we find that making the highly compositional languages dominate is a challenging task: it occupies a really small portion among all possible languages, and only using
topological similarity also cannot tell them apart from those who are highly degenerate. However, the proposed algorithm can solve this problem almost perfectly: it uses the learning speed advantage caused by high topological similarity to increase the posterior probability of high-ρ languages, and uses the interacting phase to rule out the degenerate components. The details of how the probability of languages changes in different phase of our algorithm are illustrated in Appendix C.

heading: APPENDIX C: PROBABILISTIC MODEL OF THE SYSTEM

text:
Probabilistic Model of Emergent Languages:
In section 2.3, we define a language as a mapping function from object space X to the message space M, i.e., L(·) : X 7→ M. Here we discuss how to describe the probability of a specific language, i.e., P (L). Suppose that we have N possible different objects (x1, x2, ..., xN ), where N = NNav , and the messages are conditionally independent given an object xn (where n ∈ [1, 2, . . . , N ]), i.e.:
P (L) = P (m1, ...,mN|x1, ..., xN ) = N∏
n=1
P (mn|x1, ..., xN ) = N∏
n=1
P (mn|xn). (8)
Assume that messages are uniformly sampled from M whose size is M = |V |NL , we could have P (mn|xn) = 1M ,∀n ∈ {1, 2, ..., N}. Hence the initial probability (or prior probability) of any possible language is ( 1 M )N . We define the posterior distribution of languages as the distribution after our neural iterated learning algorithm (NIL), i.e. P (L|NIL). Then, our goal is to enhance the posterior probability of the high-ρ languages, which is equivelant to enhance the expectation of ρ, i.e.:
EL∼P (L|NIL)[ρ(L)] = ∑ i ρ(Li)P (Li|NIL). (9)
It is obvious that EL[ρ(L)], the expected topological similarity of languages following the prior probability, is quite low, as the high-ρ languages only occupy an extremely small fraction.
Definition of the Agents:
Following the structure provided in Figure 1, we define the speaking agent (Alice) and listening agent (Bob) formally here.
Alice is a bunch of neural networks that can map any input object x to a discrete message m. So we define it as m = h(x), h : X 7→ M. As Alice generate discrete messages with softmax layers, the probabilistic distribution of different words in mn can be obtained. In the example provided in Figure 1, we can have P (m1|x) and P (m2|x,m1) by reading the distribution from softmax layers. In more general cases, we could obtain P (ml|x,ml−1,ml−2, . . . ) following the same method. Thus, we can directly calculate the probability of specific m given x for Alice as follow:
P (m|x) = P (m1|x) NL∏ l=2 P (ml|x,ml−1,ml−2, . . . ). (10)
If we feed all possible x to Alice and calculate the corresponding P (m|x), we then could calculate the probability distribution of all languages after training Alice, following equation (8) and (9). Then, we can state our goal as to obtain a high EL∼P (L|NIL)[ρ(L)] by using NIL to update the parameters of the neural network.
In our setting, the posterior probability of languages is decided by Alice with its softmax layers. Bob plays a role of assistant to ensure the robustness of NIL, which will be further illustrated in Appendix D and E. From Figure 1, we could see that the inputs of Bob are a discrete message m and c different objects. As Bob will calculate a score sc for each object cc, we can denote its function as s = f(m, x), f : M×X 7→ R1.
Probabilistic Description of Language Evolution in NIL:
To avoid confusion, we specify all the probabilities involved in NIL in the left corner of Figure 6. In the figure, the shadow regions with different colors represent the three phases of NIL in ONE generation. Thus, one generation of NIL could be described as:
1. Initialization: At the beginning of generation t, the initial probability of Alice[i] is P0(L), which is same as the prior probability of P (L) mentioned before, as Alice[i] is always randomly initialized. The initial function of Bob[i] is represented as f0(m, x).
2. Learning Phase: Then following Algorithm 1, Alice[i] will be pre-trained using the data sampled from the previous generation, i.e. Di. The pre-trained probability of languages is defined as Pi(L|Di). Bob[i] will then be pre-trained using the sample generated by Pi(L|Di), using REINFORCE procedure, after which, its function becomes fi(m, x).
3. Interacting Phase: The pre-trained Alice[i] and Bob[i] then interact and update their parameters together following the REINFORCE procedure described in section 3.2. In each round of the game, Alice[i] would first use argmax to select m with the highest probability given a randomly selected object x, both agents would then update their parameters if R = 1, i.e. the data pair ⟨m, x⟩ could assist them to accomplish the referential game successfully. We argure that this process has the same effect as the following procedure: we first sample a data set D∗ ∼ Pi(L|Di), and then delete the data pairs that cannot unambiguously deliver information to form a refined data set Ri. Then, the interacted probability of Alice[i] can be represented by Pi(L|Di, Ri). As Bob also update its parameters in this phase, we define its interacted function as fi∗(m, x).
4. Transmitting Phase: Finally, in the transmitting phase, we sample Di+1 ∼ Pi(L|Di, Ri) by: i)randomly feeding xn to Alice[i]; ii) sample a message mn ∼ Pi(m|xn, Di, Ri). Note that Bob[i] is not involved in this phase.
From all sections above, we argue that Alice plays an important role in all the phases in NIL while Bob only helps to make the languages effective during interaction phases. As we will discuss the role of Alice and Bob in further details in Appendix E, we only provide an intuition of how the language changes in NIL in the following paragraphs.
Overall, the objective of our NIL design is to ensure the expected topological similarity of emergent languages would increase over generations, as expressed by equation (3). As the languages with higher ρ would be learned faster, which is stated as Hypothesis 1, we can expect those high-ρ languages to have a higher pre-trained probability in P (L|Di) than in Di, i.e.:4
EL∼P (L|Di)[ρ(L)] ≥ EL∼Di [ρ(L)]. (11)
Note that this inequality is not a strict corollary, but it is very likely to hold as long as we have an appropriate Ia. In the worst case, we can chose an extremely large Ia to make Alice learn Di perfectly. However, we could verify it by the experimental results as well as the explanation in Appendix D that the weak pre-training can indeed help us to achieve a higher expected ρ. Then, in the interacting phase, we may expect:
EL∼P (L|Di,Ri)[ρ(L)] = EL∼P (L|Di)[ρ(L)], (12)
as the compositional languages and holistic languages are both unambiguous and the game performance cannot tell them apart. Finally, during the transmitting phase, we have Di+1 ∼ Pi(L|Di, Ri). Assuming that we sampled enough Di+1 to ensure it has a very similar distribution to Pi(L|Di, Ri), it is reasonable to have:
EL∼Di+1 [ρ(L)] = EL∼P (L|Di,Ri)[ρ(L)]. (13)
Sum up from the above, equation (3) can be obtained by combining equation (11-13).

heading: APPENDIX D: MORE ON THE LEARNING SPEED ADVANTAGE

text:
Amplifying mechanism and learning speed advantage are the two main elements for the success of NIL. The former on is elaborated in section 3.2 and Appendix C, under the assumption that the learning speed advantage of high-ρ language indeed exist. In this section, we will explain why such an advantage exist by experimental results and a toy example.
Example for Supporting Hypothesis 1:
This hypothesis claims that a high-ρ language would be leared faster than a low-ρ one on the speaker side. As we can directly represent the posterior probability of any language from Alice’s perspective, the assertion of “learned faster” can be converted to “the posterior probability increases faster”. We use a toy example, i.e. two languages in Table 4, to demonstrate how such an advantage emerges and how it works. To make the notation concise, we use “BB, RB, BC, RC” to represent “blue box, red box, blue circle, red circle” respectively. The probability of the compositional language and the holistic language in Table 4 can be represented as:
4Figure 2-(c) might be a good example
P (Lcmp)=P (m1=a|BB) · P (m2=a|BB,m1=a) · P (m1=b|RB) · P (m2=a|RB,m1=b) · C (14) P (Lhol)=P (m1=b|BB)︸ ︷︷ ︸
1
·P (m2=a|BB,m1=b)︸ ︷︷ ︸ 2 ·P (m1=a|RB)︸ ︷︷ ︸ 3 ·P (m2=a|RB,m1=a)︸ ︷︷ ︸ 4 ·C (15)
C=P (m1=a|BC)︸ ︷︷ ︸ 5 ·P (m2=b|BC,m1=a)︸ ︷︷ ︸ 6 ·P (m1=b|RC)︸ ︷︷ ︸ 7 ·P (m2=b|RC,m1=b)︸ ︷︷ ︸ 8
(16)
where C is the common part for both languages.
As we are using stochastic gradient descent algorithm to update the parameters of Alice, it straightforward to see that the update of gradient from one point will ’pull up’ the neighbourhood region of function h, which is shown in the left panel of Figure 7. Then, we can speculate that if one data sample belonging to both the two language comes, e.g. ⟨ab,BC⟩, the following probabilities would increase at the same time:
P (m1=a|BC); P (m1=a|BB); P (m1=a|RC), (17) as the input of them are similar with BC (only one attribute changes). As the conditional probabilities must sum to 1, the following probabilities would decrease:
P (m1=b|BC); P (m1=b|BB); P (m1=b|RC). (18)
Thus, when Alice learns the data sample ⟨ab,BC⟩, P (Lcmp) may have two terms increased, i.e., terms 5 and 1 . For P (Lhol), however, the decrease of term 1 will harm the increase of term
5 , hence P (Lhol) increases slower than P (Lcmp) (The fact that term 7 decreases on both sides would not change our deduction).
Example for Supporting Hypothesis 2:
We can use a similar explanation for the advantage at Bob. Recall that Bob is defined as a mapping function f from M×X to R1. Following the principle mentioned above, if Bob learns ⟨ab,BB⟩, a bunch of function values would increase, i.e. f(ab,BB), f(aa,BB), f(bb,BB), f(ab,BC), and f(ab, CB), as they are all close to each other in the input space. Then it is easy to find that two terms in the compositional language in Table 4 are increased while only one term increases in the holistic language. That is, the score of high-ρ language would increases faster.
We can also think hypothesis 2 in the following way. With the intuition that a language with higher ρ tends to be smoother and to have fewer inflection points than one with lower ρ, the learning speed advantage given by highly compositional languages can be illustrated by the example provided in Figure 7. In the example, language is considered to be a one-dimensional mapping function, which is represented by the dotted lines in Figure 7. The object-message pairs, which are represented by the cross marks, are the points that satisfy the mapping function. The solid line represents the mapping function of the learning agent. Suppose the target output (i.e. the third cross mark in each figure) is larger than the predicting output (i.e. the circle mark), the optimizer will update the parameters of the neural network following the direction of the gradient, as illustrated by the bold arrows in the figure. Such an update will also pull the neighbouring parts of the function up, as illustrated by the smaller arrows on the solid curve.
The smoothness of high-ρ languages implies that the MSE of neighbouring positions will also be reduced by this update, while the MSE of neighbors would be increased in the case of a low-ρ language. Such a trend is represented by the blue arrows and red crossed-arrows in Figure 7: the blue one means a decrease of the MSE at the specific position while the red one means increases of MSE. In other words, for a high-ρ languages, an update corresponding to one data sample is likely to have a larger positive effect on other data samples, and hence ensure a higher learning speed. Meanwhile, for a low-ρ language, one data sample would have both positive and negative effects on its neighbors and thus lead to a lower learning speed.

heading: APPENDIX E: ROBUSTNESS OF NIL

text:
In this section, we will provide experimental results to demonstrate the robustness of the proposed method. The influence of hyperparameters (e.g. vocabulary size, message length) as well as the role played by Alice and Bob are both elaborated.
Robustness for Hyperparameters on Message Space:
The message space are decided by the vocabulary size |V | and the message length NL. Thus, we first make experiments to see the effects of different |V | and NL on EL∼P (L|NIL)[ρ(L)].
From the discussion in Appendix B, we know that when |V | and NL are large, making high-ρ language dominate in the posterior probability is very hard, as the compositional languages only occupy an extremely small portion. Such a trend could also be found in Table 5, as the finally converged expectation of topological similarity becomes lower with larger |V | or NL. Our algorithm, however, is very robust to different values of |V | and NL. By comparing different columns in Table 5, EL∼P (L|NIL)[ρ(L)] decreases very slow with the increasement of |V | and NL. An extreme example is that, the converged ρ can still be roughly 0.8 with |V | = 72. The performance of validation accuracy seems more robust when |V | and NL changes: the NIL can always obtain more than 80% accuracy compared to the none reset case (roughly 15%).
Furthermore, compared with |V |, NL has a stronger impact on the performance in terms of all metrics but the validation performance, as it is shown in Table 5 that the performance with NL = 3 is significantly lower than its counterpart when NL = 2. One possible explanation is that the increasing of NL brings an exponential change to the message space. However, no matter how |V | and NL change, EL∼P (L|NIL)[ρ(L)] is always significantly higher that the compositionality of emergent languages given by baseline model, i.e. 0.3.
Robustness on Degenerate Components:
From the discussions in Appendix B, we know that the ρ of a language who has many degenerate components will also be high, and hence can be learned faster by Alice in the learning phase. Thus, it is necessary to check whether our algorithm can avoid the mode collapse caused by the degenerate components. Intuitively, the degenerate components can be filtered out during the interacting phase, as the REINFORCE algorithm ensure that the parameters of the agent will only be updated with respect to R = 1, i.e. the language is effective and thus unambiguous.
To verify our hypothesis, we first observe how the number of message types, i.e. the number of different messages used to describe all 64 objects, changes during NIL. It is straightforward to see that a language without any degenerate component would have 64 different message types. As shown in Figure 8, all methods could achieve high numbers if message types, which indicates that the REINFORCE algorithm could always filter out the degenerate components efficiently.
Furthermore, we design two challenging tasks for NIL:
1. Degenerate initialized: We let Alice learn from a pure degenerate language at the beginning of each generation, before it learns from Di.
2. Degenerate mixed: We mix the data pair generated by a pure degenerate language to Di and ensures the proportion of the degenerate pairs is more than 50%, which makes Alice easier to collapse to a degenerate language during learning phase.
We then compare the performance, i.e. the expected ρ and validation accuracy, of agents in different tasks. The results shown in Figure 9 demonstrate that our NIL is very robust to the influence of degenerate component, as both EL∼P (L|NIL)[ρ(L)] and the validation score are much higher than the none reset baseline’s performance.
The Role of Bob’s Pre-training
From the discussions above, it is easy to understand why EL∼P (L|NIL)[ρ(L)] would gradually increase in NIL and how the REINFORCE applied in interacting phase can filter the degenerate component. However, the role played by Bob, especially in the learning phase where Bob only update its own parameters, is not straightforward. In short, the pre-training of Bob makes the algorithm more robust, especially at the beginning of the interacting phase. We record the value of EL∼P (L|NIL)[ρ(L)] every 20 iterations among learning phase and interacting phase, and plot the results of two generations in Figure 10.
In this figure, the x-axis is the index of iterations. With Ia=1000, Ib=400, and Ig=1600, we split (by dotted lines) each generation to three parts: Alice pre-training, Bob pre-training, and interacting phase. The blue lines are generated by NIL with the pre-training of Bob while the red lines are generated when Bob is not pre-trained (here Ig=2000 to make a fair comparison). For the blue lines, EL∼P (L|NIL)[ρ(L)] will not change when Bob is pre-training (begins at the 1000th iteration), because Alice do not update parameters at that time. However, for the red lines, EL∼P (L|NIL)[ρ(L)] begin to decrease at the 1000th iteration. That is because when Bob is not pre-trained, the language learned by Alice may be impacted by playing with a fresh new Bob at the beginning of interacting phase! That is why the pre-training of Bob can make the NIL more efficient and robust. If Bob are pre-trained by the data generated by Alice in the current generation, Bob would be more “familiar” with Alice’s language, and hence ensures a more stable interacting phase.
Looking at the Emergent Languages
From the discussions above, we know that NIL can ensure a high expected ρ of the emergent language, and a high validation performance. Here we show the evolution of the distributions of emergent languages to provide a better intuition on how NIL works.
We first provide two examples of converged language (i.e., the language generated by Alice in the last generation) using the none-reset method and the resetting-both method in Table 6 and 7, respectively. In these examples, both languages can almost unambiguously represent all 64 different types of objects in X , and hence they can help Alice and Bob to play the game successfully. However, the language generated using iterated learning has a clear compositional structure: the first position of the message represents different colors, and the second position represents the shape. Such a structure is quite similar to what humans do, e.g., combine an adjective and a noun to represent a complex concept.
To better illustrate the posterior probability of emergent languages as a function of the corresponding value of ρ and the generation, we provide the 3D views of P (ρ(L)|Di, Ri) in 80 generations in Figure 12 and 13. The heat-map provided in Figure 11 can be considered as the top views of these 3D illustrations. In these two figures, the x-axis and y-axis represent the index of generation and the topological similarity, and the z-axis represents the probability of languages with a specific value of ρ, in a specific generation. To make the figures easier to read, we smooth the distribution of ρ in each generation using linear interpolation (Boyd & Vandenberghe, 2004).
Figure 14-(a) and (b) compare the posterior distributions at some typical generations, which can also be considered as the side views of the 3D illustration from the direction of x-axis. In these figures, we find that the initial distribution of ρ is not flat. That is because even the prior probability for each language is uniform, the amounts of languages with extremely high ρ and low ρ only occupy a small portion among all possible languages, as stated in (Brighton, 2002). Hence the initial probability of ρ(L) is no longer uniform and has a bell shape which is similar to the Gaussian distribution. One new trend provided by these figures is that, in the none-reset case, the width of the curves in different generations do not change much, while in the resetting-both case, the width of the curves
will gradually decrease (i.e., becomes more peaky). Such a trends means when iterated learning is applied, language tend to converge to some high-ρ types.
Figure 15-(a) and (b) track the ratio of languages with different values of ρ, which can also be considered as the side views of the 3D illustration from the direction of y-axis. In these figures, we divide all possible languages into five groups based on their topological similarity, i.e., languages with ρ ≤ 0.2, 0.2 < ρ ≤ 0.4, 0.4 < ρ ≤ 0.6, 0.6 < ρ ≤ 0.8, and 0.8 < ρ. We plot the ratio of these five different groups of languages at the end of each generation. From Figure 15-(a), we can see that the high-ρ language, which is represented by the bold curve, always occupy a small portion. The topological similarity of the dominant languages are ρ < 0.4. However, in the resetting-both case, as illustrated in Figure 15-(b), the portion of high-ρ language will increase significantly, which further verifies that the iterated learning can gradually make the high-ρ language dominate in posterior.

title: COMPOSITIONAL LANGUAGES EMERGE IN A NEURAL ITERATED LEARNING MODEL