summaries: Contributions: The paper proposes a novel Label Sensitive Gate (LSG) structure to enable the model to learn disentangled filters in a supervised manner. The novelty of the paper is to introduce the Label-Sensitive Gate path during the training, on top of the standard training path. This encourages the filters to extract class-sensitive features.

summaries: This paper proposed an interesting idea of using Label Sensitive Gate (LSG) structure to enforce models to learn disentangled filters for better interpretability of the DNN model. By periodically training with the sparse LSG structure, the model is forced to extract features from only a few classes. The model is trained efficiently in an alternate fashion (with respect to both the network parameters and the sparse gate matrix.) By disentangling the class-specific filters, the model becomes less redundant and more interpretable.

summaries: This paper proposes a method to improve the interpretability of a convolutional neural network (CNN). The main idea is to force the CNN filters to be class specific, i.e. to be associated to a specific class. This is accomplished by a gating function that enforces filters to be sparsely activated.  This would make the model more interpretable by allowing to check which filters/classes have been activated. Results are evaluated in terms of performance, sparsity of the filters and localization accuracy on CIFAR10.

abstractText: Convolutional neural networks (CNNs) have often been treated as “black-box” and successfully used in a range of tasks. However, CNNs still suffer from the problem of filter ambiguity – an intricate many-to-many correspondence relationship between filters and features, which undermines the models’ interpretability. To interpret CNNs, most existing works attempt to interpret a pre-trained model, while neglecting to reduce the filter ambiguity hidden behind. To this end, we propose a simple but effective strategy for training interpretable CNNs. Specifically, we propose a novel Label Sensitive Gate (LSG) structure to enable the model to learn disentangled filters in a supervised manner, in which redundant channels experience a periodical shutdown as flowing through a learnable gate varying with input labels. To reduce redundant filters during training, LSG is constrained with a sparsity regularization. In this way, such training strategy imposes each filter’s attention to just one or few classes, namely class-specific. Extensive experiments demonstrate the fabulous performance of our method in generating sparse and highly class-related representation of the input. Moreover, comparing to the standard training strategy, our model displays less redundancy and stronger interpretability.

authors:
David Bau
Bolei Zhou
Aditya Khosla
Aude Oliva
Antonio Torralba

title: Network dissection: Quantifying interpretability of deep visual representations

venue: In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition,

authors:
Mariusz Bojarski
Philip Yeres
Anna Choromanska
Krzysztof Choromanski
Bernhard Firner
Lawrence Jackel
Urs Muller

title: Explaining how a deep neural network trained with end-toend learning steers a car

venue: arXiv preprint arXiv:1704.07911,

authors:
Diane Bouchacourt
Ryota Tomioka
Sebastian Nowozin

title: Multi-level variational autoencoder: Learning disentangled representations from grouped observations

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

authors:
Christopher P Burgess
Irina Higgins
Arka Pal
Loic Matthey
Nick Watters
Guillaume Desjardins
Alexander Lerchner

title: Understanding disentangling in β-vae

venue: arXiv preprint arXiv:1804.03599,

authors:
Rich Caruana
Yin Lou
Johannes Gehrke
Paul Koch
Marc Sturm
Noemie Elhadad

title: Intelligible models for healthcare: Predicting pneumonia risk and hospital 30-day readmission

venue: In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,

authors:
Tian Qi Chen
Xuechen Li
Roger B Grosse
David K Duvenaud

title: Isolating sources of disentanglement in variational autoencoders

venue: In Advances in Neural Information Processing Systems,

authors:
Xi Chen
Yan Duan
Rein Houthooft
John Schulman
Ilya Sutskever
Pieter Abbeel

title: Infogan: Interpretable representation learning by information maximizing generative adversarial nets

venue: In Advances in neural information processing systems,

authors:
J. Deng
W. Dong
R. Socher
L.-J. Li
K. Li
L. Fei-Fei

title: ImageNet: A Large-Scale Hierarchical Image Database

venue: In CVPR09,

authors:
M. Everingham
L. Van Gool
C.K.I. Williams
J. Winn
A. Zisserman

title: The PASCAL Visual Object Classes Challenge 2010 (VOC2010) Results. http://www.pascalnetwork.org/challenges/VOC/voc2010/workshop/index.html

title: Fast r-cnn

venue: In Proceedings of the IEEE international conference on computer vision,

authors:
Song Han
Jeff Pool
Sharan Narang
Huizi Mao
Enhao Gong
Shijian Tang
Erich Elsen
Peter Vajda
Manohar Paluri
John Tran

title: Dsd: Dense-sparse-dense training for deep neural networks

venue: arXiv preprint arXiv:1607.04381,

authors:
Kaiming He
Xiangyu Zhang
Shaoqing Ren
Jian Sun

title: Deep residual learning for image recognition

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

authors:
Kaiming He
Georgia Gkioxari
Piotr Dollár
Ross Girshick

title: Mask r-cnn

authors:
Yihui He
Xiangyu Zhang
Jian Sun

title: Channel pruning for accelerating very deep neural networks

venue: In Proceedings of the IEEE International Conference on Computer Vision,

authors:
Irina Higgins
Loic Matthey
Arka Pal
Christopher Burgess
Xavier Glorot
Matthew Botvinick
Shakir Mohamed
Alexander Lerchner

title: beta-vae: Learning basic visual concepts with a constrained variational framework

venue: International Conference on Learning Representations,

authors:
Hyunjik Kim
Andriy Mnih

title: Disentangling by factorising

venue: arXiv preprint arXiv:1802.05983,

title: Adam: A method for stochastic optimization, 2014. URL http://arxiv.org/abs/1412.6980

authors:
Diederik P Kingma
Max Welling

title: Stochastic gradient vb and the variational auto-encoder

venue: In International Conference on Learning Representations,

authors:
Alex Krizhevsky
Ilya Sutskever
Geoffrey E Hinton

title: Imagenet classification with deep convolutional neural networks. In Advances in neural information processing

authors:
Abhishek Kumar
Prasanna Sattigeri
Avinash Balakrishnan

title: Variational inference of disentangled latent concepts from unlabeled observations

venue: arXiv preprint arXiv:1711.00848,

authors:
Zhuang Liu
Jianguo Li
Zhiqiang Shen
Gao Huang
Shoumeng Yan
Changshui Zhang

title: Learning efficient convolutional networks through network slimming

authors:
Francesco Locatello
Stefan Bauer
Mario Lucic
Sylvain Gelly
Bernhard Schölkopf
Olivier Bachem

title: Challenging common assumptions in the unsupervised learning of disentangled representations

venue: arXiv preprint arXiv:1811.12359,

authors:
Jian-Hao Luo
Jianxin Wu
Weiyao Lin

title: Thinet: A filter level pruning method for deep neural network compression

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:
Aravindh Mahendran
Andrea Vedaldi

title: Understanding deep image representations by inverting them

authors:
Pavlo Molchanov
Stephen Tyree
Tero Karras
Timo Aila
Jan Kautz

title: Pruning convolutional neural networks for resource efficient inference

venue: arXiv preprint arXiv:1611.06440,

authors:
Alexander Mordvintsev
Christopher Olah
Mike Tyka

title: URL https://research.googleblog.com/2015/06/ inceptionism-going-deeper-into-neural.html

venue: Inceptionism: Going deeper into neural networks,

authors:
Nina Narodytska
Shiva Prasad Kasiviswanathan

title: Simple black-box adversarial perturbations for deep networks

venue: arXiv preprint arXiv:1612.06299,

authors:
Chris Olah
Arvind Satyanarayan
Ian Johnson
Shan Carter
Ludwig Schubert
Katherine Ye
Alexander Mordvintsev

title: The building blocks of interpretability. Distill, 2018

authors:
Aaditya Prakash
James Storer
Dinei Florencio
Cha Zhang

title: Repr: Improved training of convolutional filters

authors:
Sara Sabour
Nicholas Frosst
Geoffrey E Hinton

title: Dynamic routing between capsules

authors:
Karen Simonyan
Andrea Vedaldi
Andrew Zisserman

title: Deep inside convolutional networks: Visualising image classification models and saliency maps

venue: arXiv preprint arXiv:1312.6034,

authors:
Jiawei Su
Danilo Vasconcellos Vargas
Kouichi Sakurai

title: One pixel attack for fooling deep neural networks

venue: IEEE Transactions on Evolutionary Computation,

authors:
Ilya Sutskever
James Martens
George Dahl
Geoffrey Hinton

title: On the importance of initialization and momentum in deep learning

venue: In International conference on machine learning,

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:
Valentin Thomas
Emmanuel Bengio
William Fedus
Jules Pondard
Philippe Beaudoin
Hugo Larochelle
Joelle Pineau
Doina Precup
Yoshua Bengio

title: Disentangling the independently controllable factors of variation by interacting with the world

venue: arXiv preprint arXiv:1802.09484,

authors:
Yulong Wang
Hang Su
Bo Zhang
Xiaolin Hu

title: Interpret neural networks by identifying critical data routing paths

authors:
Matthew D Zeiler
Rob Fergus

title: Visualizing and understanding convolutional networks

venue: In European conference on computer vision,

authors:
Quanshi Zhang
Ruiming Cao
Ying Nian Wu
Song-Chun Zhu

title: Mining object parts from cnns via active question-answering

title: Growing interpretable part graphs on convnets via multi-shot learning

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

authors:
Quanshi Zhang
Ruiming Cao
Shengming Zhang
Mark Redmonds
Ying Nian Wu
SongChun Zhu

title: Interactively transferring cnn patterns for part localization

venue: arXiv preprint arXiv:1708.01783,

authors:
Quanshi Zhang
Ruiming Cao
Feng Shi
Ying Nian Wu
Song-Chun Zhu

title: Interpreting cnn knowledge via an explanatory graph

authors:
Quanshi Zhang
Ying Nian Wu
Song-Chun Zhu

title: Interpretable convolutional neural networks

authors:
Quanshi Zhang
Yu Yang
Haotian Ma
Ying Nian Wu

title: Interpreting cnns via decision trees

authors:
Bolei Zhou
Aditya Khosla
Agata Lapedriza
Aude Oliva
Antonio Torralba

title: Learning deep features for discriminative localization

heading: 1 INTRODUCTION

text:
Convolutional Neural Networks (CNNs) demonstrate extraordinary performance in various visual tasks (Krizhevsky et al., 2012; He et al., 2016; Girshick, 2015; He et al., 2017a). However, the strong expressive power of CNNs is still far from interpretable, which significantly limits its applications that require humans’ trust or interaction, e.g. self-driving and medical image analysis (Caruana et al., 2015; Bojarski et al., 2017). In this paper, we argue that filter ambiguity is one of the most critical reasons that hampers the interpretability of CNNs. As a matter of fact, previous studies has shown that 1) filters in CNNs generally extract features of a mixture of various semantic concepts, including objects, parts, scenes, textures, materials and colors (Zhang et al., 2018b; Bau et al., 2017); and that 2) there is also redundant overlap between features extracted by different filters (Prakash et al., 2019). The intricate many-to-many correspondence relationship between filters and features is so-called filter ambiguity as shown on the left of Figure 1.
Obviously, in high convolutional layers which might capture class-related feature, filter ambiguity contradicts our intention of an interpretable CNN, because it hinders humans from interpreting the concepts of a filter (Zhang et al., 2018b), which has been shown as an essential role in the visualization and analysis of networks (Olah et al., 2018) in human-machine collaborative systems (Zhang et al., 2017a;c). Moreover, the unnecessary overlap between features extracted by different filters leads to under-utilization of a model’s expressiveness (Prakash et al., 2019) Therefore, reducing filter ambiguity is critical to obtain better feature with better interpretability and less redundancy.
However, it is non-trivial to achieve such a goal barricaded by substantial challenges. First, most interpretability-related research simply focuses on post-hoc interpretation of filters (Szegedy et al., 2013; Bau et al., 2017), which manages to interpret the main semantic concepts captured by a filter but fails to alleviate the filter ambiguity prevalent in pretrained models. Second, many existing works such as VAEs’ variants (Higgins et al., 2017; Burgess et al., 2018; Kim & Mnih, 2018; Chen et al., 2018; Kumar et al., 2017) and InfoGAN (Chen et al., 2016) try to disentangle data representation and obtain better interpretability in an unsupervised way. However, it is proved that unsupervised
learning on disentangled features without inductive bias is impossible (Locatello et al., 2018), which challenges the works above.
Considering the aforementioned challenges, we shed light on enforcing the one-class for one-filter relationship during training (instead of post-hoc) in a supervised manner only with classification labels. To this end, we propose a novel training strategy that coerces each filter into extracting features from only one or few classes for classification tasks, namely disentangling filters towards classspecific. Specifically, we design a Label Sensitive Gate (LSG) structure on the top of convolutional filters, which limits each filter’s activation only to its specific input label(s). In our training process, we periodically insert LSG into the CNN and jointly minimize the classification cross-entropy and the sparsity of LSG, so as to keep the model’s performance on classification and meanwhile encourage class-specific filters.
Experiments proved the LGS filter yield better representation for images hence leading to promising applications. Our training method makes data representation sparse and highly correlated with the labeled class, which not only illustrates the alleviation of filter ambiguity but also enhances the interpretability of the network. The advantages of our method are concretely substantiated by sparser correlation between filters, sparser filter-class correlation, better explanation for misclassification and more precise localization of labeled objects.
Contributions The contributions of this work can be summarized as: (1) we propose a novel training strategy for CNNs which forces each filter to extract features mainly from only one or a few classes; (2) moreover, we propose a metric to evaluate filter ambiguity, which can also be used as a regularization in our training to encourage class-specific filters; (3) finally, our training enables filters to output sparse and class-related representation, which helps alleviate filter redundancy, improve interpretability of the model.

heading: 2 RELATED WORKS

text:
Existing works related to our work include post-hoc filter interpretation, learning disentangled representation and model pruning.
Post-hoc Interpretation for Filters is widely studied, which aims to interpret the patterns captured by filters in pretrained CNNs. Plenty of works visualize the pattern of a neuron as an image, which is the gradient (Zeiler & Fergus, 2014; Mahendran & Vedaldi, 2015; Simonyan et al., 2013) or accumulated gradient (Mordvintsev et al., 2015; Olah et al., 2018) of a certain score about the activation of the neuron. Bau et al. (2017) determine the main visual patterns extracted by a convolutional filter by treating it as a pattern detector. Some other works transfer the representation in CNN into an explanatory graph (Zhang et al., 2017b; 2018a) or a decision tree (Zhang et al., 2019), which aim to figure out the visual patterns of filters and the relationship between co-activated patterns. Posthoc filter interpretation helps to understand the main patterns of a filter but makes no change to the existing filter ambiguity of the pretrained models, while our work aims to train interpretable models.
Learning Disentangled Representation refers to learning data representation that encodes different semantic information into different dimensions. As a principle, it proves impossible to learn disentangled representation without inductive bias (Locatello et al., 2018). Unsupervised methods such as variants of VAEs (Kingma & Welling, 2014) and InfoGAN (Chen et al., 2016) rely on regularization. VAEs (Kingma & Welling, 2014) are modified into many variants (Higgins et al., 2017; Burgess et al., 2018; Kim & Mnih, 2018; Chen et al., 2018; Kumar et al., 2017), while their disentangling performance is sensitive to hyperparameters and random seeds. InfoGAN (Chen et al., 2016) learns disentangled hidden representations by maximizing the mutual information between input and generated images. Some other unsupervised methods rely on special network architectures including interpretable CNNs (Zhang et al., 2018b) and CapsNet (Sabour et al., 2017). As for supervised methods, Thomas et al. (2018) propose to disentangle with interaction with the environment; Bouchacourt et al. (2018) apply weak supervision from grouping information, while our work applies weak supervision from classification labels.
Model Pruning reduces structure redundancy and therefore is widely used for both model efficiency and better generalization, while our work uses it to alleviate filter ambiguity and improve interpretability. Many existing methods prune pretrained CNNs for better efficiency without significant deterioration in performance, including channel-wise pruning (He et al., 2017b; Molchanov et al., 2016; Liu et al., 2017) and filter-wise pruning (Luo et al., 2017). The methods mentioned imply that CNNs trained by standard training strategy tend to have redundant filters. Further research exploits redundant filters to improve generalization and suppress over-fitting by temporally pruning during training: Dense-Sparse-Dense (Han et al., 2016) encourages sparse weights by regularization and then recovers dense weights by removing the regularization; RePr (Prakash et al., 2019) repeatedly prunes and reinitializes redundant filters to reduce filter overlap.

heading: 3 METHOD

text: Learning disentangled filters in CNNs alleviates filter ambiguity and meanwhile narrows the gap between human’s perception and CNN’s representations. In this section, we first present an ideal case of class-specific filters, which is a direction for our training, and then we elaborate on our method about how to train an interpretable network.

heading: 3.1 CLASS-SPECIFIC FILTERS

text:
For CNNs in classification tasks, it is demonstrated that the filters in the last convolutional layer extract high-level features related to certain classes more or less (Zeiler & Fergus, 2014). We suppose the most ideal case, as shown in Figure 2, is that each filter extracts features mainly from only one class, i.e. each filter is mainly relevant to one class. We call such filters ideally class-specific. Obviously, given the labeled class of an input, the classification performance changes little if we shut down the channels from the filters irrelevant to the class. This is the direction for our training method elaborated later.
To have a rigorous definition of “ideally class-specific”, for a CNN, we use a matrixG ∈ {0, 1}C×K to measure the relevance between filters and classes, where K is the number of filters, C is the number of classes, and each element Gkc represents the relevance between the k-th filter and c-th class, as shown in Figure 3. The k-th filter extracts features mainly in the c-th class when and only when Gkc = 1. Given the label y ∈ {1, 2, ..., C} of an input, we can index a row Gy ∈ {0, 1}K from the matrixG, which can be used as a gate multiplied to the feature maps to shut down those irrelevant
channels. We call filters in a CNN as ideally class-specific filters, when the network’s prediction ỹG approaches that of original network ỹ after the feature maps from the last convolutional layer are multiplied by the gate Gy .

heading: 3.2 PROBLEM FORMULATION

text:
In order to train a CNN towards disentangling filters to class-specific and meanwhile keep the original classification performance, as opposed to the standard training scheme that entangles filters, we introduce a Label-Sensitive Gate (LSG) path in addition to the standard path of forward propagation. In such a LSG path, some channels are shut down by multiplication with a learnable gate. This path’s classification performance is regarded as a regularization for disentanglement training.
As shown in Figure 3, let us denote θ as the network parameters. The network forward propagates in two paths: 1) the standard (STD) path predicting ỹθ, and 2) the LSG path with gate matrix G predicting ỹGθ where the learnable gate Gy for the input labeled with y is multiplied to the feature map before the linear layer.
Initially, the elements in the gate matrix G for a CNN are unknown. Intuitively, we can search for them by exploring the binary space and find one solution that yields the best classification performance through LSG path, i.e., to solve Φ0(θ) = minG:Gkis one-hot CE(y||ỹGθ ), where the constraint on Gk applies to ∀k ∈ {1, 2, ...,K} and Φ0 evaluates the performance of the CNN with filters disentangled. Therefore, it is natural to add Φ0 into training loss as a regularization that forces filters to be class-specific. Thus, we get the following formulation of the original problem to train a CNN towards ideally class-specific filters as
min θ L0(θ) = CE(y||ỹθ) + λΦ0(θ). (1)
However, the problem is difficult to solve in practice. On the on hand, the assumption that each filter is ideally disentangled to extract only one class hardly holds, since it is usual for several classes to share one high-level feature in CNNs; on the other hand, binary vectors in a non-continuous space are difficult to optimize with gradient descent.
To address these two issues, we relax the constraints from two perspectives. First, we relax the one-hot vectorGk to sparse vector by L1 regularization ‖G‖1 where at least one element equals to 1 ( ∥∥Gk∥∥∞ = 1). Since ||Gk||∞ = 1 ensures ‖G‖1 to be larger than K, we actually apply ∣∣ ‖G‖1− s∣∣ as the sparsity regularization term in order to make the norm of gate matrix close to a constant target norm s ≥ K. Second, we relax the binary vectorGk ∈ {0, 1}C to a continuous vectorGk ∈ [0, 1]C . Therefore Φ0 now becomes
Φ(θ) = min G {CE(y||ỹGθ ) + a ∣∣ ‖G‖1 − s∣∣} s.t. ∥∥Gk∥∥∞ = 1 and Gkc ∈ [0, 1], (2)
where a is a coefficient to balance classification and sparsity. Φ can be regarded as a metric of filter ambiguity, which means a CNN with higher class-specificity of filters will have a lower Φ (contrary to common sense, here we expect Φ to be as small as possible).
Replacing Φ0 in Equation 1 with Φ, we get an intermediate problem minθ(CE(y||ỹθ) + λΦ(θ)). It is mathematically equivalent if we move minG within Φ to the left most (see Appendix A for proof). Thus, we formulate a relaxed problem as
min θ,G
L(θ,G) = CE(y||ỹθ) + λ(CE(y||ỹGθ ) + a ∣∣ ‖G‖1 − s∣∣), (3)
s.t. ∥∥Gk∥∥∞ = 1 and Gkc ∈ [0, 1].
The relaxed problem is easier to solve by jointly optimizing θ and G with gradient descent, compared to either the discrete optimization in the original problem, or the nested optimization in the intermediate problem. Solving the relaxed problem, we can obtain a CNN for classification with class-specific filters, where G precisely describes the correlation between filters and classes.

heading: 3.3 OPTIMIZATION

text:
To solve the optimization problem formulated in Equation 3 with gradient descent, we alternately optimize G and θ to improve the classification performance of the model while ensuring the constraints of sparsity on G, as is shown in Algorithm 1 1. In this scheme, we run the LSG path to update both G and θ in some epochs of a period, and run the STD path to update θ in the other epochs. WhenG is updated with gradient,Gk will be normalized by
∥∥Gk∥∥∞ to ensure ∥∥Gk∥∥∞ = 1, and then clipped into range [0, 1].
After solving the relaxed problem, we can further tighten the constraint on LSG to G ∈ {0, 1}C×K for stronger sparsity ofG. In this work, we tighten into a simple and special case, where some filters are related to only one class (i.e. Gk is one-hot) for class-specific features, and the other filters are related to all classes (i.e. Gk is all-one) for class-sharing features. Specifically, if Gk has only one elementGkc ≥ h (threshold h ∈ (0, 1])Gk will be set to one-hot, otherwiseGk will be set to all-one.
Algorithm 1 LSG Training 1: for E in epochs do 2: for N in batches do 3: if E%3 == 1 then 4: ỹGθ ← prediction through the LSG path with G 5: Cost← λ(CE(y||ỹGθ ) + a ∣∣∥∥G∥∥ 1 − s ∣∣)
6: G is updated using the gradient decent as G← G− ∂Cost∂G ; 7: Each column of Gk is normalized as Gk ← G k
‖Gk‖∞ ;
8: G← clip(G, 0, 1) 9: else
10: ỹθ ← prediction through the STD path 11: Cost← CE(y||ỹθ) 12: end if 13: θ ← θ − ∂Cost∂θ 14: end for 15: end for

heading: 4 EXPERIMENT

text:
In this section, we conduct five experiments. We first delve into LSG training from three aspects, so as to respectively study the effectiveness of LSG training, the class-specificity of filters and the correlation between filters train with LSG. After that, we demonstrate LSG’s application on improving
1Another choice is a naive scheme: in all epochs we predict through both paths to directly calculate L(θ,G) defined in equation 3 and update θ and G with gradients of it. We choose the alternating scheme because in our preliminary exploration it shows better training stability and converging speed.
object localization and adversarial samples detection. In the following parts, we denote our training method Label-Sensitive Gate as LSG, the standard training as STD, and CNNs trained with them as LSG CNNs and STD CNNs, respectively.
Training setting We trained ResNet20s (He et al., 2016) on CIFAR20 and ResNet152s (He et al., 2016) on PASCAL VOC 2010 (Everingham et al.) on classification task with LSG/STD training. ResNet20s are evaluated in this 4.1, 4.2, 4.3 and 4.5, and ResNet152s are evaluated in 4.1 and 4.4. For fair comparison, all the code is implemented on the Pytorch framework and tested on GTX 1080Ti GPUs. We report the validation performance on last epoch following common practice.
For ResNet20s, the default settings include: batch size is 256; the optimizer is SGD with momentum of 0.9 (Sutskever et al., 2013); the initial learning rate is 0.1; and the total training epochs is 150. The ResNet152s are finetuned from model pretrained on ImageNet (Deng et al., 2009). Parameters are frozen except the top 2 bottleneck blocks, gate matrix and linear layers. The setting is: batch size is 32; the optimizer is Adam (Kingma & Ba, 2014); the initial learning rate is 1e-5 for STD path and 1e-3 for LSG path; the total training epochs is 150.
Beside, we preprocess PASCAL VOC to be a classification dataset for training ResNet152s: we crop out images for the objects in 6 classes (bird, cat, dog, cow, horse and sheep) and resize the image to 128x128; then randomly reassign 3644 objects for training and 1700 objects for testing. No segmentation label is used in training ResNet152s.

heading: 4.1 EFFECTIVENESS OF LSG TRAINING

text:
To begin with, we conduct experiments to demonstrate the effectiveness of our LSG training in learning a sparse gate matrix and yielding a low Φ that evaluates class-specificity of filters.
Basic Quantitative Evaluation To compare the performance on classification and filter disentanglement of the STD CNN and the LSG CNN, we calculate their test accuracy, cross entropy, L1 Norm ‖G‖1 and Φ as mentioned in Section 3.2. As shown in Table 1, LSG CNN’s even slightly outperforms STD CNN in test accuracy, and cross entropy of both is comparable, while LSG CNN has much lower L1 Norm and Φ. The L1 Norm and the Φ indicate LSG learns class-specific filters that hence reduce filter ambiguity. These metrics quantitatively demonstrate LSG’s capability of learning a sparse gate matrix and disentangling filters without any sacrifice on classification accuracy.
Visualization of Label-Sensitive Gate Matrix To illustrate the relevance between classes and the learned filters described in the gate matrix, we visualize gate matrices in Figue 4. Subfigure (a) indicates that the LSG training yields a sparse LSG matrix where each filter is only related to one or few classes. Subfigure (b) comes from a LSG training without the sparsity regularization to the gate matrix (L1 norm), from which we observe filter ambiguity where a filter would extract ambiguous features from multiple classes. Accordingly, LSG training effectively learn sparse gate matrix, and this characteristic originates from our sparsity regularization – the L1 norm on the gate matrix.
(a) Gate Matrix of LSG CNN using L1 Regularization
Filter ID
Class ID
(b) Gate Matrix of STD CNN w/o L1 Regularization 1.0
0.0
Filter ID
0 2 4 6 8
0 10 20 30 40 50 600 10 20 30 40 50 60
Figure 4: Visualization of the gate matrices from LSG training w/o the sparsity regularization on the gate matrix. The x-axis is the filter id from 1 to 64, the y-axis is the class id in CIFAR10 from 0 to 9, and the color represents how much a filter is related to a class.

heading: 4.2 CLASS-SPECIFIC FILTERS

text:
To substantiate that LSG training learns class-specific filters and reveal how it works, we explore the LSG CNN with filters masked for certain class(es) from which we observe the similarity between feature vectors and gates. The experiments are conducted on the ResNet20 trained in 4.1.
Masking Filters for Certain Class Although the sparse gate matrix implies filters are classspecific, to further verify the LSG training learns class-specific filters, we remove the filters highly related to certain class(es) referencing the gate matrix (i.e. Gkc greater than a threshold), and then visualize the classification confusion matrices. As shown in Figure 5, when filters highly related to “plane” are removed, to our surprise, the LSG CNN fails to recognize the first class ”plane”; nevertheless, the STD CNN still manages to recognize ”plane”. Analogously, when masking the filters highly related to the first and sixth classes, we observe similar phenomenon. This demonstrates that in the LSG CNN, the features from a certain class are almost extracted by the specific filters highly related to the class, while other filters extract little feature from the class. Therefore the filters are trained to be class-specific under the encouragement of the sparse gate matrix.
Similarity Between Features and Gates This experiment explains how the LSG matrix encourages class-specific filters by analyzing the similarity between feature from each class and each row in the LSG matrix. In our models there is a global average pooling (GAP) layer after the last convolutional layer, which yields a feature vector denoted as a. We use inner production to measure the similarity Scy between the feature vectors ay of images in the class y and the c-th row Gc in the LSG matrix (see Appendix B for details). We calculate Scy over all true positive (TP) and false negative (FN) images respectively and obtain similarity matrices STP , SFN ∈ RC×C , as shown in Figure 6. From the figure, we observe two phenomena and provide the following analysis. 1) TP similarity matrix is diagonally dominant significantly, which reveals how LSG works in disentangling filters to class-specific: LSG forces filters to yield feature vectors whose direction approaches that of the gate vector for its related class. 2) FN similarity matrix is far from diagonally dominant. Besides, two classes with shared features, such as car & truck and ship & plane, have high similarity in the FN similarity matrix, which enlightens us that hard samples with ambiguous feature across classes tends to be misclassified in LSG models. Thus, the mechanism of misclassification in the LSG CNN is probably the features across classes extracted by the shared filters .

heading: 4.3 CORRELATION BETWEEN FILTERS

text:
To study the filter correlation in LSG CNNs, we train a CNN with the LSG under a tighter constraint, so as to conveniently analyze the correlation between filters for different classes.
Constraint Tightening Before tightening the constraint on gate matrix G ∈ {0, 1}C×K according to Section 3.3, we first conduct a statistic analysis on 20 different LSG models to figure out how many filters each class monopolizes. The result indicates that in CIFAR10, each class tends to monopolize 10% total filters (6 for ResNet20’s last convolutional layer), and 10% from all filters are shared by classes. Inspired by this phenomenon, we tighten the constraint accordingly by manually setting a fixed LSG matrix. In the fixed LSG matrix, for each row Gc there are 6 ones from 6 columns of one-hot Gk, and 4 extra columns Gk are all-one (see Appendix C for illustration). This provides a setup where each class monopolizes 6 filters and 4 extra filters are shared by all classes. Models trained with this constraint naturally inherits all features of previous LSG models, and moreover, has better disentangled filters.
Filter Orthogonality Analysis We evaluate the correlation between filters with the orthogonality of their weights. We train an AlexNet (Krizhevsky et al., 2012) and a ResNet20 with the fixed LSG matrix or with STD, and then calculate the correlation between filters in each models. The correlation between two filters is defined as the inner product of their normalized weights, visualized as matrices in Figure 7. In subfigures (a), (c) for STD models, the filters are randomly correlated with each other. On the contrary, subfigures (b), (d) for LSG models, the matrices are approximately block-diagonal, which means the correlation between the filters is limited into several filter groups corresponding to classes. This implies that filters for the same class are highly correlated (nonorthogonal) for the co-occurrence of features extracted by them, while filters for different classes are almost uncorrelated (orthogonal) for the lack of co-occurrence.
Through intuitive reasoning, we can explain why LSG training encourages filters for different classes to become orthogonal. Given a class c and a gate matrix, that assigns the filter k for class c and filter k′ for other class. During training, filter k′ is closed (i.e. its activation is masked) in the LSG path when class c’s images input. In order to ensure the STD path predict similar to LSG path, the filter k′ tends to be activated by class c as less as possible, which implies the weight of filter k′ is approximately perpendicular to Vc, the linear space spanned by class c’s features in a layer before. The filter k for class c, however, tends to be activated by class c as saliently as possible so as to enable the CNN to recognize this class. So the weight of filter k is approximately within Vc. Overall, the weights of filter k and filter k′ tends to be orthogonal.
Filter Redundancy With further analysis based on filter correlation, we discover that LSG reduce the redundancy of filters. For each element ai,j in the correlation matrix, we define that the i-th filter and j-th filter are correlated if ai,j > swhere s is a varying threshold. We count the ratio of elements in the correlation matrix satisfying the constrain and plot the results in subfigure (e). It shows that LSG significantly reduces the redundant weak (e.g. threshold= 0.3) correlation between most filter pairs, which are mostly for different classes. We explain the reduction of filter redundancy as a natural consequence of encouraging filters (for different classes) to be orthogonal. For a set of filter groups orthogonal to each other, a filter in any group can not be a linear representation with the filers from other groups. This directly avoids redundant filter across groups. Besides, experiments in (Prakash et al., 2019) also verify the opinion that filter orthogonality reduces filter redundancy.
Class-Related Representation Based on filter correlation, we can even show that filters trained with LSG can yield highly class-related representation, namely the representation for an image tends to exactly correspond to its labeled class rather than to other classes. That’s based on a reasoning that in the highly activated channel of a representation, filters are less activated by other classes and less correlated to the filters for other classes. To verify this reasoning, we analyze the correlation between the filters highly activated by each class. First we pick out each class c’s dominant m filters, denoted as group Ac (class c has highest average activation on them; m = 25 for AlexNet; m = 6 for RestNet20). We define Inter-Class filter correlation as the average correlation between
filters in different classes’ group: CIC = 1C(C−1)m2 ∑ c ∑ c6=c′ ∑ k∈Ac ∑ k′∈Ac′
Ck,k′ , where Ck,k′ is the row k column k′ of the filter correlation matrix in Figure 7. The results in Table 2 show that inter-class filter correlation in LSG is about half as much as that in STD, both on AlexNet and ResNet20. This demonstrates that different classes tend to activate uncorrelated filters in LSG CNNs. As a result, the representations for different classes have less overlap. Thus we finally confirm representation from LSG CNN is highly class-related.

heading: 4.4 APPLICATION - LOCALIZATION

text:
In this subsection, we exploit our class-specific filters to improve the localization of CNNs. LSG training encourages top convolutional each filter to focus on fewer classes, which obviously implies its feature map can localize a class better. We conducts experiments below to verify it.
Localization method Resizing feature maps to input size is a widely used method to determine the area of objects or visual concepts, which not only works in localization task without bounding box labels (Bau et al., 2017), but also take an important role in network visualization and understanding the function of filters (Zhou et al., 2016).
We study LSG CNNs’ performs on localizing object classes with the feature map from both single filter and all filters. For single filter, we bilinear interpolate its feature map and segment the region with values above the top 20% activation of the filter on the entire test dataset. For all filers, we sums up their feature maps with the weights of the linear connections between each channels and an output class2. By bilinear interpolating the sum feature map to input size, we get a classification activation map (CAM) (Bau et al., 2017). We segment the region with values above the top 20% activation in a CAM. Thus we can get segmentation map for a class from feature maps.
Quantitative evaluation We train ResNet152s to do classification on preprocessed PASCAL VOC and use Avg-IoU (average intersection over union) and AP15 (average precision 15%) to evaluate their localization for each class and all classes. Higher metrics shows better localization. Especially, for localization with one filter, we report Avg-IoU and AP15 averaged over all filters. See Appendix E for detailed definition of the metrics. The results for localization with one or all filters are shown in Table 3. For localization with one filter, most classes is localized better with LSG CNN. That’s because filters trained with LSG tends be activated by the labeled class rather than many other classes, which alleviates other classes’ interference on feature maps. Therefore, as a weighted sum of better one-filter feature maps, LSG CNN’s CAMs also outperform LSG CNN’s.
Visualiziation Besides the quantitative evaluation above, in Figure 8, we also visualize sample some images and their CAMs from the STD/LSG CNN. We observe that the CAMs of STD CNN often activate extra or other semantic areas unrelated to the labeled class. However, LSG training
2It only works for CNNs with global average pooling and one linear layer the last convolutional layer.
successfully helps the CNN find a more precise area of the labeled objects in an image. Such a phenomenon vividly demonstrates that LSG training improves the performance in localization.

heading: 4.5 APPLICATION - ADVERSARIAL SAMPLE DETECTION

text:
This subsection shows an application of the highly class-related representation from our classspecific filters. It is studied (Wang et al., 2018) that adversarial samples can be detected based on the anomalous behavior of their representation on each layers: in low layers of a neural network, the representation of an adversarial sample is similar to the original class, while on the high layers it is similar to the target class. With the highly class-related representation from our LSG training, it will be much easier to distinguish which class the high-layer representation is similar to. Therefore, we suppose this advantage will help in adversarial detection task.
To verify this judgment, we train a binary classifier with the features of normal samples and adversarial samples extracted by global average pooling after each convolution layers of ResNet20 trained in 4.1. As indicated in (Wang et al., 2018), the non-targeted adversarial samples result in semantic-closer class with the original class, which are hard to discriminate. In this regard, we generate targeted adversarial samples by commonly used PGD (Madry et al., 2017) attack with = 0.3 and iter = 40 and the adversarial target classes are from a random permutation of original classes besides each image’s true class. In our experiments, we adopt random forest (Breiman, 2001) as the binary classifier. We randomly select 100, 500 and 1000 images for each class in CIFAR-10 dataset to form different sizes of training datasets while the test data is collected by randomly selecting 100 images for each class. The experimental results are shown in Table 4. We repeat each experiments five times and report the mean AUC scores. The experimental results demonstrate that the class-related representation can better distinguish the abnormal behavior of adversarial samples which can help improve the robustness of the model.

heading: 5 CONCLUSION

text: In this work, we propose a simply yet effective structure – Label Sensitive Gate Matrix to disentangle the filters in CNNs. With reasonable assumptions about the behaviors of filters, we derive regularization terms to constrain the form of the gate matrix. As a result, the sparsity of the gate matrix encourages class-specific filters, and therefore yields sparse and highly class-related representations, which endows model with better interpretability. We believe LSG is a promising architecture to disentangle filters in CNNs. Referring to LSG’s successful utility and feasibility in classification problem, we expect that LSG also have the potential to interpret other tasks like detection, segmentation etc, and networks more than CNNs, which is the direction of our future work.

heading: A EQUIVALENCE PROOF

text:
This section is a supplementary proof for the equivalence (mentioned in 3.2) between
min θ
(CE(y||ỹθ) + λΦ(θ)),
Φ(θ) = min G
CE(y||ỹGθ ) + a |‖G‖1 − s| s.t. ∥∥Gk∥∥∞ = 1, Gkc ∈ [0, 1],
and
min θ,G
L(θ,G) = CE(y||ỹθ) + λ(CE(y||ỹGθ ) + a |‖G‖1 − s|) s.t. ∥∥Gk∥∥∞ = 1, Gkc ∈ [0, 1].
This equivalence is true referencing the Lemma below, if we set x ∈ X in the Lemma as θ ∈ RM , y ∈ Y as G ∈ {G ∈ [0, 1]C×K} , f(x) as CE(y||ỹθ), and g(x, y) as CE(y||ỹGθ ) + a |‖G‖1 − s|. Here, M is the number of parameters in a CNN, C is number of classes, K is the number of filters. y is the label of an input, ỹθ is the prediction of the CNN’s prediction through the STD path, and ỹGθ is the prediction of the CNN’s prediction through the LSG path with G.
Lemma Given sets X,Y , and functions f : X 7→ R , g : X × Y 7→ R. f . If f and g have lower bounds, then
min (x,y)∈X×Y [f(x) + g(x, y)] = min x∈X [f(x) + min y∈Y g(x, y)] (4)
Proof. Given ∀x ∈ X , f(x) is a constant if we take y as the only variable, so
f(x) + min y∈Y g(x, y) = min y∈Y [f(x) + g(x, y)]
Denote F (x, y) = f(x) + g(x, y), thus to prove equation 4 we only need to prove
min (x,y)∈X×Y F (x, y) = min x min y F (x, y)
This is obvious, because for ∀x ∈ X, y ∈ Y ,
min (x,y)∈X×Y
F (x, y) ≤ F (x, y),
so for ∀x ∈ X min
(x,y)∈X×Y F (x, y) ≤ min y∈Y F (x, y),
and then
min (x,y)∈X×Y F (x, y) ≤ min x∈X min y∈X F (x, y).
Reversely, for ∀x ∈ X, y ∈ Y , we have
min x∈X min y∈Y
F (x, y) ≤ F (x, y),
so
min x∈X min y∈Y F (x, y) ≤ min (x,y)∈X×Y F (x, y).

heading: B SIMILARITY BETWEEN FEATURE VECTORS AND GATES

text:
We design a similarity between the feature vector ay of a image in class y and the c-th row Gc in the LSG matrix. Noticing a,Gc ∈ RK , we use their inner production aTyGc as a similarity in direction. Thus, each pair of image in class y and class c will contribute an inner production aTyGc to S c y – the average similarity between the feature vectors for class y and the c-th gate row. Thus, we can further define the average similarity between the feature vectors for class y and the c-th gate row,
Scy(D) = DtestmeanaTyGc : (x, y) ∈ D.
Here, D is a dataset to calculate the average on, and (x, y) is a pair of image and label in the dataset. We can take D as all true positive or all false negative data, as conducted in 4.2.

heading: C MANUALLY FIXED GATE MATRIX

text:
In 4.3 we use a manually fixed gate matrix to train CNNs from scratch. The gate matrix is visualized in Figure 9.
Filter ID .
Class ID
1.0
0.0 0 10 20 30 40 50 60
0
2
4
6
8
Figure 9: Manual fixed gate matrix. Each class monopolizes 6 filters and 4 extra filters are shared by all classes.

heading: D CLUSTER CENTER EXPERIMENTS

text: Using the model with fixed LSG mentioned in 4.3, we run k-means clustering on the feature vectors after the global average pooling in the STD CNN and the LSG CNN. The dataset we used is CIFAR10. We find the LSG CNN yields better clustering centers, which is almost the same as the gate matrix we used (visualized in Figure 9), with filter groups reordered.

heading: E METRICS FOR LOCALIZATION

text:
This section gives detailed definition of the metrics we used in our localization experiments.
E.1 LOCALIZATION WITH ONE FILTER
For an image x in class c (denoted as x ⊂ Dc ∈ D, D is the dataset), we denote the ground-truth segmentation map for x as Sx, and the segmentation map given by the resized feature map from filter k as Ŝkx . The filter k ∈ [1,K], where K is the number of filers in the top convolutional layer. The IoU (intersection over union) on this image is defined as
IoUkx = ∥∥∥Sk ∩ Ŝk∥∥∥∥∥∥Sk ∪ Ŝk∥∥∥ . The Avg-IoU (average intersection over union) for filter k to localize class c is defined as
IoUkc = meanx∈DcIoU k x.
The AP15 (average precision 15%) for filter k to localize class c is defined as
AP15kc = meanx∈DcI{IoU k x) > 0.15}.
When c = arg maxc′ AP15kc′ , we call filter k is for localizing class c, denoted as k ∈ Fc, where Fc is the set of filters for localizing class c. The performance for filter k is evaluated with IoUk = IoUkc∗ and AP15k = AP15kc∗ .
Thus we can define the Avg-IoU and AP15 for localizing class c as
IoUc = meank∈Fc∗ IoU k
and AP15c = meank∈Fc∗AP15 k.
Besides, the Avg-IoU and AP15 for localizing all classes is defined as
IoU = meank∈[1,K]IoU k
and AP15 = meank∈[1,K]AP15 k.
E.2 LOCALIZATION WITH ALL FILTERS
For an image x in class c (denoted as x ∈ Dc), we denote the ground-truth segmentation map for x as Sx, and the segmentation map given by the resized classification activation map (CAM) (Bau et al., 2017) as Ŝx.
The IoU (intersection over union) on this image is defined as
IoUx = ∥∥∥Sk ∩ Ŝ∥∥∥∥∥∥Sk ∪ Ŝ∥∥∥ . The Avg-IoU (average intersection over union) for localizing class c is defined as
IoUc = meanx∈DcIoUx.
The AP15 (average precision 15%) for localizing class c is defined as
AP15c = meanx∈DcI{IoUx) > 0.15}.
Besides, the Avg-IoU and AP15 for localizing all classes is defined as
IoU = meanx∈DIoUx
and AP15 = meanx∈DI{IoUx) > 0.15}.

heading: F DEFENDING ADVERSARIAL SAMPLES

text: In this experiments, inspired by the highly class-related representation, we further explore LSG CNNs’ potential in robustness for adversarial attacks. Two black box attacks are conducted, including one pixel attack (Su et al., 2019) and local search attack (Narodytska & Kasiviswanathan, 2016). They try to fool models according to the model’s predicted probability without access to the models’ parameters and architectures. From the results shown in Table 5, we find both the attacks gain attack success rates on STD CNN much higher than on LSG CNN. This demonstrates that LSG training also improves robustness to CNNs. We guess the robustness is caused by the increase of within-class distance and the decrease of between-class distance, which requires further verification. Robustness is another valuable characteristic of the highly class-related representation from the class-specific filters.


summaries: The authors propose a framework for combining value function factorization and communication learning in a multi-agent setting by introducing two regularizers, one for maximizing mutual information between decentralized Q functions and communication messages and the other for minimizing the entropy of messages between agents. The authors also discuss a method for dropping non-informative messages. They illustrate their approach on sensor and hallway tasks and evaluate their method on the decentralized StarCraft II benchmark. The paper addresses an interesting problem, and the authors show that their approach gives good performance compared to alternative approaches even when a large percentage of communication is cut off between the agents.

summaries: Authors propose a new method for multi-agent reinforcement learning by using nearly decomposable value functions. The main idea is to have local (agent specific) value function and one global value function (for all agents). They also try minimizing the required communication need for multi-agent setup. To this end they deploy variational inference tools and support their method with an experimental study.

summaries: The paper tackles the collaborative multi-agent RL problem as the problem of finding almost-decentralized value functions, where the loss tries to minimize communications between the agents. The core idea is around maximizing the mutual information between each massage and the existing knowledge of its receiver. This way, redundant messages are naturally removed. The authors then assert an entropy regularization to (almost) prevent the agents from *cheating*. The paper is in general well-written and motivated. There are however certain issues that should be addressed. [The second one is my main issue.]

abstractText: Reinforcement learning encounters major challenges in multi-agent settings, such as scalability and non-stationarity. Recently, value function factorization learning emerges as a promising way to address these challenges in collaborative multiagent systems. However, existing methods have been focusing on learning fully decentralized value functions, which are not efficient for tasks requiring communication. To address this limitation, this paper presents a novel framework for learning nearly decomposable Q-functions (NDQ) via communication minimization, with which agents act on their own most of the time but occasionally send messages to other agents in order for effective coordination. This framework hybridizes value function factorization learning and communication learning by introducing two information-theoretic regularizers. These regularizers are maximizing mutual information between agents’ action selection and communication messages while minimizing the entropy of messages between agents. We show how to optimize these regularizers in a way that is easily integrated with existing value function factorization methods such as QMIX. Finally, we demonstrate that, on the StarCraft unit micromanagement benchmark, our framework significantly outperforms baseline methods and allows us to cut off more than 80% of communication without sacrificing the performance. The videos of our experiments are available at https://sites.google.com/view/ndq.

authors:
Alexander A Alemi
Ian Fischer
Joshua V Dillon
Kevin Murphy

title: Deep variational information bottleneck

venue: In Proceedings of the International Conference on Learning Representations (ICLR),

authors:
Yongcan Cao
Wenwu Yu
Wei Ren
Guanrong Chen

title: An overview of recent progress in the study of distributed multi-agent coordination

venue: IEEE Transactions on Industrial informatics,

authors:
Abhishek Das
Satwik Kottur
José MF Moura
Stefan Lee
Dhruv Batra

title: Learning cooperative visual dialog agents with deep reinforcement learning

venue: In Proceedings of the IEEE International Conference on Computer Vision,

authors:
Abhishek Das
Théophile Gervet
Joshua Romoff
Dhruv Batra
Devi Parikh
Mike Rabbat
Joelle Pineau

title: Tarmac: Targeted multi-agent communication

venue: In International Conference on Machine Learning,

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

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

venue: In Advances in Neural Information Processing Systems,

authors:
Jakob Foerster
Nantas Nardelli
Gregory Farquhar
Triantafyllos Afouras
Philip HS Torr
Pushmeet Kohli
Shimon Whiteson

title: Stabilising experience replay for deep multi-agent reinforcement learning

venue: In Proceedings of the 34th International Conference on Machine Learning-Volume

authors:
Jakob N Foerster
Gregory Farquhar
Triantafyllos Afouras
Nantas Nardelli
Shimon Whiteson

title: Counterfactual multi-agent policy gradients

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

authors:
Anirudh Goyal
Riashat Islam
Daniel Strouse
Zafarali Ahmed
Matthew Botvinick
Hugo Larochelle
Sergey Levine
Yoshua Bengio

title: Infobot: Transfer and exploration via the information bottleneck

title: Vain: Attentional multi-agent predictive modeling

authors:
Natasha Jaques
Angeliki Lazaridou
Edward Hughes
Caglar Gulcehre
Pedro Ortega
Dj Strouse
Joel Z Leibo
Nando De Freitas

title: Social influence as intrinsic motivation for multi-agent deep reinforcement learning

authors:
Jiechuan Jiang
Zongqing Lu

title: Learning attentional communication for multi-agent cooperation

authors:
Daewoo Kim
Sangwoo Moon
David Hostallero
Wan Ju Kang
Taeyoung Lee
Kyunghwan Son
Yung Yi

title: Learning to schedule communication in multi-agent reinforcement learning

authors:
Akshat Kumar
Shlomo Zilberstein
Marc Toussaint

title: Scalable multiagent planning using probabilistic inference

venue: In Twenty-Second International Joint Conference on Artificial Intelligence,

authors:
Angeliki Lazaridou
Alexander Peysakhovich
Marco Baroni

title: Multi-agent cooperation and the emergence of (natural) language

authors:
Ryan Lowe
Yi Wu
Aviv Tamar
Jean Harb
OpenAI Pieter Abbeel
Igor Mordatch

title: Multi-agent actor-critic for mixed cooperative-competitive environments

authors:
Igor Mordatch
Pieter Abbeel

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

authors:
Ann Nowé
Peter Vrancx
Yann-Michaël De Hauwere

title: Game theory and multi-agent reinforcement learning

venue: In Reinforcement Learning,

authors:
Frans A Oliehoek
Christopher Amato

title: A concise introduction to decentralized POMDPs, volume

authors:
Peng Peng
Ying Wen
Yaodong Yang
Quan Yuan
Zhenkun Tang
Haitao Long
Jun Wang

title: Multiagent bidirectionally-coordinated nets: Emergence of human-level coordination in learning to play starcraft combat games

venue: arXiv preprint arXiv:1703.10069,

authors:
Tabish Rashid
Mikayel Samvelyan
Christian Schroeder Witt
Gregory Farquhar
Jakob Foerster
Shimon Whiteson

title: Qmix: Monotonic value function factorisation for deep multi-agent reinforcement learning

authors:
Mikayel Samvelyan
Tabish Rashid
Christian Schroeder de Witt
Gregory Farquhar
Nantas Nardelli
Tim GJ Rudner
Chia-Man Hung
Philip HS Torr
Jakob Foerster
Shimon Whiteson

title: The starcraft multi-agent challenge

authors:
Amanpreet Singh
Tushar Jain
Sainbayar Sukhbaatar

title: Learning when to communicate at scale in multiagent cooperative and competitive tasks

authors:
Kyunghwan Son
Daewoo Kim
Wan Ju Kang
David Earl Hostallero
Yung Yi

title: Qtran: Learning to factorize with transformation for cooperative multi-agent reinforcement learning

authors:
Sainbayar Sukhbaatar
Rob Fergus

title: Learning multiagent communication with backpropagation

authors:
Peter Sunehag
Guy Lever
Audrunas Gruslys
Wojciech Marian Czarnecki
Vinicius Zambaldi
Max Jaderberg
Marc Lanctot
Nicolas Sonnerat
Joel Z Leibo
Karl Tuyls

title: Value-decomposition networks for cooperative multi-agent learning based on team reward

venue: In Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems,

authors:
Ardi Tampuu
Tambet Matiisen
Dorian Kodelja
Ilya Kuzovkin
Kristjan Korjus
Juhan Aru
Jaan Aru
Raul Vicente

title: Multiagent cooperation and competition with deep reinforcement learning

venue: PloS one,

title: Multi-agent reinforcement learning: Independent vs. cooperative agents

venue: In Proceedings of the tenth international conference on machine learning,

authors:
Nicolas Usunier
Gabriel Synnaeve
Zeming Lin
Soumith Chintala

title: Episodic exploration for deep deterministic policies: An application to starcraft micromanagement tasks

authors:
Ying Wen
Yaodong Yang
Rui Luo
Jun Wang
Wei Pan

title: Probabilistic recursive reasoning for multi-agent reinforcement learning

authors:
Chongjie Zhang
Victor Lesser

title: Coordinated multi-agent reinforcement learning in networked distributed pomdps

venue: In Twenty-Fifth AAAI Conference on Artificial Intelligence,

title: Coordinating multi-agent reinforcement learning with limited communication

venue: In Proceedings of the 2013 international conference on Autonomous agents and multi-agent systems,

heading: 1 INTRODUCTION

text:
Cooperative multi-agent reinforcement learning (MARL) are finding applications in many realworld domains, such as autonomous vehicle teams (Cao et al., 2012), intelligent warehouse systems (Nowé et al., 2012), and sensor networks (Zhang & Lesser, 2011). To help address these problems, recent years have made a great progress in MARL methods (Lowe et al., 2017; Foerster et al., 2018; Rashid et al., 2018; Jaques et al., 2019). Among these successes, the paradigm of centralized training with decentralized execution has attracted much attention for its scalability and ability to deal with non-stationarity.
Value function decomposition methods provide a promising way to exploit such paradigm. They learn a decentralized Q function for each agent and use a mixing network to combine these local Q values into a global action value. In previous works, VDN (Sunehag et al., 2018), QMIX (Rashid et al., 2018), and QTRAN (Son et al., 2019) have progressively enlarged the family of functions that can be represented by the mixing network. Despite their increasing ability in terms of value factorization representation, existing methods have been focusing on learning full decomposition, where each agent acts upon its local observations. However, many multi-agent tasks in the real world are not fully decomposable – agents sometimes require information from other agents in order to effectively coordinate their behaviors. This is because partial observability and stochasticity in a multi-agent environment can exacerbate an agent’s uncertainty of other agents’ states and actions during decentralized execution, which may result in catastrophic miscoordination.
∗Equal Contribution.
To address this limitation, this paper presents a scalable multi-agent learning framework for learning nearly decomposable Q-functions (NDQ) via communication minimization, with which agents act on their own most of the time but occasionally send messages to other agents in order for effective coordination. This framework hybridizes value function factorization learning and communication learning by introducing an information-theoretic regularizer for maximizing mutual information between agents’ action selection and communication messages. Messages are parameterized in a stochastic embedding space. To optimize communication, we introduce an additional informationtheoretic regularizer to minimize the entropy of messages between agents. With these two regularizers, our framework implicitly learn when, what, and with whom to communicate and also ensure communication to be both expressive (i.e., effectively reducing the uncertainty of agents’ actionvalue functions) and succinct (i.e., only sending useful and necessary information). To optimize these regularizers, we derive a variational lower bound objective, which is easily integrated with existing value function factorization methods such as QMIX.
We demonstrate the effectiveness of our learning framework on StarCraft II1 unit micromanagement benchmark used in Foerster et al. (2017; 2018); Rashid et al. (2018); Samvelyan et al. (2019). Empirical results show that NDQ significantly outperforms baseline methods and allows to cut off more than 80% communication without sacrificing the performance. We also observe that agents can effectively learn to coordinate their actions at the cost of sending one or two bits of messages even in complex StarCraft II tasks.

heading: 2 BACKGROUND

text:
In our work, we consider a fully cooperative multi-agent task that can be modelled by a DecPOMDP (Oliehoek et al., 2016) G = 〈I, S,A, P,R,Ω, O, n, γ〉, where I ≡ {1, 2, ..., n} is the finite set of agents. s ∈ S is the true state of the environment from which each agent i draws an individual partial observation oi ∈ Ω according to the observation function O(s, i). Each agent has an action-observation history τi ∈ T ≡ (Ω × A)∗. At each timestep, each agent i selects an action ai ∈ A, forming a joint action a ∈ An, resulting in a shared reward r = R(s,a) for each agent and the next state s′ according to the transition function P (s′|s, a). The joint policy π induces a joint action-value function: Qπtot(τ ,a) = Es0:∞,a0:∞ [ ∑∞ t=0 γ
trt|s0=s,a0=a,π], where τ is the joint action-observation history and γ ∈ [0, 1) is the discount factor. Learning the optimal action-value function encounters challenges in multi-agent settings. On the one hand, to properly coordinate actions of agents, learning a centralized action-value function Qtot seems a good choice. However, such a function is difficult to learn when the number of agents is large. On the other hand, directly learning decentralized action-value function Qi for each agent alleviates the scalability problem (Tan, 1993; Tampuu et al., 2017). Nevertheless, such independent learning method largely neglects interactions among agents, which often results in miscoordination and inferior performance.
In between, value function factorization method provides a promising way to attenuate such dilemma by representingQtot as a mixing of decentralizedQi conditioned on local information. Such method has shown their effectiveness on complex task (Samvelyan et al., 2019).
However, current value function factorization methods have been mainly focusing on full decomposition. Such decomposition reduces the complexity of learningQtot by first learning independentQi and putting the burden of coordinating actions on the mixing networks whose input is all Qi’s and output is Qtot. For many tasks with partial observability and stochastic dynamics, mixing networks are not sufficient to learn coordinated actions, regardless of how powerful its representation ability is. The reason is that full decomposition cuts off all dependencies among decentralized action-value functions and agents will be uncertain about states and actions of other agents. Such uncertainty will increase as time goes by and can result in severe miscoordination and arbitrarily worse performance during decentralized execution.
1StarCraft and StarCraft II are trademarks of Blizzard EntertainmentTM.

heading: 3 METHODOLOGY

text:
In this section, we propose to learn nearly decomposable Q-functions (NDQ) via communication minimization, a new framework to overcome the miscoordination issue of full factorization methods.
In our learning framework (Fig. 1), individual action-value functions condition on local actionobservation history and, at certain timesteps, messages received from a few other agents. Messages from agent i to agent j are drawn from a multivariate Gaussian distribution whose parameters are given by an encoder fm(τi, j;θc), where τi is the local observation-action history of agent i, and θc are parameters of the encoder fm. Formally, message mij ∼ N (fm(τi, j;θc), I), where I is an identity matrix. Here we use an identity covariance matrix and the reasons will be discussed in the next section. m(-i)j is used to denote the messages sent to j from agents other than i. We learn a nearly decomposable structure via learning minimized communication. We thus expect the communication to have the following properties:
i) Expressiveness: The message passed to one agent should effectively reduce the uncertainty in its action-value function.
ii) Succinctness: Agents are expected to send messages as short as possible to the agents who need it and only when necessary.
To learn such a communicating strategy, we draw inspiration from variational inference for its proven ability in learning structure from data and endow a stochastic latent message space, which we also refer to as ”message embedding”. We impose constraints, which will be discussed in detail in the next section, on the latent message embedding to enable an agent to decide locally which bits in a message should be sent according to their utility in terms of helping other agents make decisions. Agent j will receive an input message minj that has been selectively cut, on which it conditions the local action-value function Qj(τj , aj ,minj ). All the individual Q values are then fed into a mixing network such as that used by QMIX (Rashid et al., 2018).
Apart from the constraints on the message embedding, all the components (the individual actionvalue functions, the message encoder, and the mixing network) are trained in an end-to-end manner by minimizing the TD loss. Thus, our overall objective is to minimize
L(θ) = LTD(θ) + λLc(θc), (1)
where LTD(θ) = [r + γmaxa′ Qtot(τ ′,a′;θ−)−Qtot(τ ,a;θ)] 2 (θ− are the parameters of a periodically updated target network as in DQN) is the TD loss, θ are all parameters in the model,
and λ is a weighting term. We will discuss how to define and optimize Lc(θc) to regularize the message embedding in the next section.

heading: 3.1 MINIMIZED COMMUNICATION OBJECTIVE AND VARIATIONAL BOUND

text:
Introducing latent variables facilitates the representation of the message, but it does not mean that the messages can reduce uncertainty in the action-value functions of other agents. To make message expressive, we maximize the mutual information between message and agent’s action selection. Formally, we maximize Iθc(Aj ;Mij |Tj ,M(-i)j) where Aj is agent j’s action selection, Tj is the random variable of the local action-observation history of agent j, Mij and M(-i)j are random variables of mij and m(-i)j . However, if this is the only objective, the encoder can easily learn to cheat by giving messages under different histories representations in different regions in the latent space, rendering cutting off useless messages difficult. A natural constraint to avoid such representations is to minimize the entropy of the messages. Therefore, our objective for optimizing communication of agent i is to maximize:
Jc(θc) = n∑ j=1 [ Iθc(Aj ;Mij |Tj ,M(-i)j)− βHθc(Mij) ] , (2)
where β is a scaling factor trading expressiveness and succinctness.
This objective is appealing because it agrees exactly with the desiderata that we impose on the message embedding. However, optimizing this objective needs extra efforts because computation involving mutual information is intractable. By introducing a variational approximator, a popular technique from variational toolkit (Alemi et al., 2017), we can derive a lower bound for the mutual information term in Eq. 2 (a detailed derivation can be found in Appendix A):
Iθc(Aj ;Mij |Tj ,M(-i)j) ≥ ET∼D,Minj ∼fm(T,j;θc) [ −CE [ p(Aj |T)‖qξ(Aj |Tj ,M inj ) ]] ,
(3)
where T = 〈T1,T2, . . . ,Tn〉 is the joint local history sampled from the replay buffer D, qξ(Aj |Tj ,M inj ) is the variational posterior estimator with parameters ξ, and CE is the cross entropy operator. We share ξ among agents to accelerate learning.
Next we discuss how to minimize the term Hθc(Mij). Directly minimizing this can cause the variances of the Gaussian distributions to collapse to 0. To deal with this numeric issue, we use the unit covariance matrix and try to minimize H(Mij) − H(Mij |Ti) instead. This is equivalent to minimizing H(Mij) because H(Mij |Ti) is the entropy of a multivariate Gaussian random variable and thus is a constant log(det(2πeΣ))/2, where Σ is a unit matrix in our formulation). Then we have:
H(Mij)−H(Mij |Ti) = ∫ p(mij |τi)p(τi) log
p(mij |τi) p(mij) dmijdτi. (4)
We use a similar technique as for the mutual information term by introducing an distribution r(mij) to get a upper bound of Eq. 4:
H(Mij)−H(Mij |Ti) ≤ ∫ p(mij |τi)p(τi) log
p(mij |τi) r(mij) dmijdτi
= ETi∼D [DKL(p(Mij |Ti)‖r(Mij))] . (5)
This bound holds for any distribution r(Mij). To facilitate cutting off messages, we use unit Gaussian distribution N (0, I). Combining Eq. 3 and 5, we get a tractable variational lower bound of our objective in Eq. 2:
Jc(θc) ≥ ET∼D,Minj ∼fm(T,j;θc) [ −CE [ p(Aj |T)‖qξ(Aj |Tj ,M inj ) ] − βDKL(p(Mij |Ti)‖r(Mij)) ] . (6) We optimize this bound to generate an expressive and succinct message embedding. Specifically, we minimize:
Lc(θc) = ET∼D,Minj ∼fm(T,j;θc) [ CE [ p(Aj |T)‖qξ(Aj |Tj ,M inj ) ] + βDKL(p(Mij |Ti)‖r(Mij)) ] .
(7)
Intuitively, the first term, which we call the expressiveness loss, ensures that communication aims to reduce the uncertainty in action-value functions of other agents. The second term, called the succinctness loss, forces messages to get close to the unit Gaussian distribution. Since we set the covariances of the latent message variables to the unit matrix, this term actually pushes the means of the message distributions to the origin of the latent space. Using these two losses leads to an embedding space where useless messages distribute near the origin, while messages that contain important information for the decision-making processes of other agents occupy other spaces.
Note that the loss shown in Eq. 7 is used to update the parameters in the message encoder. In the meantime, all components (the individual action-value functions, the message encoder, and the mixing network) are trained in an end-to-end manner. Thus, the message encoder is updated by two gradients: the gradient induced by Lc(θc) and the gradient associated with the TD loss LTD(θ).

heading: 3.2 CUTTING OFF MESSAGES

text:
Our objective pushes messages which can not reduce the uncertainties in action-value functions of other agents close to the origin of the latent message space. This naturally gives us a hint on how to drop meaningless messages – we can order the message distributions according to their means and drop accordingly. Note that since we use a unit covariance matrix for the latent message distribution, bits in a message are independent. Thus, we can make decisions in a bit-by-bit fashion and send messages with various lengths. In this way, our method learns not only when and who (agent i does not communicate with agent j when all bits of mij are dropped) to communicate, but also what to communicate (how many bits are sent and their values). More details are discussed in Appendix B.
Our framework adopts the centralized training with decentralized execution paradigm. During centralized training, we assume the learning algorithm has access to all agents’ individual observationaction histories and the global state s. During execution, agents communicate and act in a decentralized fashion based on the learned message encoder and action-value functions.

heading: 4 RELATED WORKS

text:
Deep multi-agent reinforcement learning has witnessed vigorous progress in recent years. COMA (Foerster et al., 2018), MADDPG (Lowe et al., 2017), and PR2 (Wen et al., 2019) explores multi-agent policy gradients and respectively address the problem of credit assignment, learning in mixed environments and recursive reasoning. Another line of research focuses on value-based multi-agent RL, among which value-function factorization is the most popular method. Three representative examples: VDN (Sunehag et al., 2018), QMIX (Rashid et al., 2018), and QTRAN (Son et al., 2019) gradually increase the representation ability of the mixing network. In particular, QMIX (Rashid et al., 2018) stands out as a scalable and robust algorithm and achieves state-ofthe-art results on StarCraft unit micromanagement benchmark (Samvelyan et al., 2019).
Communication is a hot topic in multi-agent reinforcement learning. End-to-end learning with differentiable communication channel is a popular approach now. Sukhbaatar et al. (2016); Hoshen (2017); Jiang & Lu (2018); Singh et al. (2019); Das et al. (2019) focus on learning decentralized communication protocol and address the problem of when and who to communicate. Foerster et al. (2016); Das et al. (2017); Lazaridou et al. (2017); Mordatch & Abbeel (2018) study the emergence of natural language in the context of multi-agent learning. IC3Net (Singh et al., 2019) learns gate to control the agents to only communicate with their teammates in mixed multi-agent environment. Zhang & Lesser (2013); Kim et al. (2019) study action coordination under limited communication channel and thus are related to our works. The difference lies in that they do not explicitly minimize communication. Social influence (Jaques et al., 2019) and InfoBot (Goyal et al., 2019) penalize message that has no influence on policies of other agents.
Work that is most related to this paper is TarMAC (Das et al., 2019), where attention mechanism is used to differentiate the importance of incoming messages. In comparison, we use variation inference to decide the content of messages and whether a message should be sent under the guidance of global reward signals. We compare our method with TarMAC and a baseline combining TarMAC and QMIX in our experiments. Related works on the task of StarCraft II unit micromanagement are discussed in Appendix C.2.

heading: 5 EXPERIMENTAL RESULTS

text:
In this section, we show our experiments to answer the following questions: (i) Is the miscoordination problem of full value function factorization methods widespread? (ii) Can our method learn the minimized communication protocol required by a task? (iii) Can the learned message distributions reduce uncertainties in value functions of other agents? (iv) How does our method differ from communication with attention mechanism? (v) How does β influence the communication protocol? We will first show three simple examples to clarify our idea from different perspectives and then provide performance analysis on StarCraftII unit micromanagement benchmark. For evaluation, all experiments are carried out with 5 random seeds and results are shown with a 95% confidence interval. Details of the NDQ network architecture are given in Appendix B.2. Videos of our experiments on StarCraft II are available online2.
2https://sites.google.com/view/ndq
We compare NDQ with the following baselines: (i) QMIX (Rashid et al., 2018); (ii) TarMAC (Das et al., 2019). QMIX and TarMAC are state-of-the-art full value function factorization and attentional communication methods, respectively. (iii) QMIX+TarMAC. We introduce the attentional communication mechanism into the value function factorization paradigm by integrating the communication component of TarMAC into QMIX.

heading: 5.1 DIDACTIC EXAMPLES

text:
We first demonstrate our idea on three didactic examples: sensor, hallway, and independent search.
Sensor network is a frequently used testbed in multi-agent learning field (Kumar et al., 2011; Zhang & Lesser, 2011). We use a 3-chain sensor configuration in the task sensor (Fig. 2(a)). Each sensor is controlled by one agent, and they are rewarded for successfully locating targets, which requires two sensors to scan the same area simultaneously when the target appears. At each timestep, target 1 appears in area 1 with possibility 1, and locating it induces a team reward of 20; target 2 appears with probability 0.5 in area 2, and agents are rewarded 30 for locating it. Agents can observe whether a target is present in nearby areas and need to choose one of the five actions: scanning north, east, south, west, and noop. Every scan induces a cost of -5.
In the optimal policy, when target 2 appears, sensor 1 should turn itself off while sensors 2 and 3 are expected to scan area 2 to get the reward. And when target 2 is absent, sensors 1 and 2 need to cooperatively scan area 1 while sensor 3 takes noop.
Sensor is representative of a class of tasks where the uncertainties about the true states cause policies learned by full value function factorization method to be sub-optimal – sensor 1 has to know whether the target is present in area 2 to make a decision. However, the mixing network of QMIX cannot provide such information. As a result, QMIX converges to a sub-optimal policy, which gets a team reward of 12.5 a step on average (see Fig. 2(b)).
We are particularly interested in whether our method can learn the minimized communication strategy. Fig. 3 shows the latent message space learned by NDQ. When β = 10−3, agent 3 learns to send a bit to tell agent 1 whether target 2 appears. In the meantime, the latent message distribution between any other pair of agents is close to the standard Gaussian distribution and thus is dropped. This result indicates that NDQ has discovered the minimized conditional graph and can explain why our method can still perform optimally when 80% of the messages are cut off (Fig. 2(c)). When β becomes too large (1.0), all the message bits are pushed below the cutting threshold (Fig. 3(a) and 3(d)). When β is too small (10−5), NDQ pays more attention on reducing uncertainties in Q-functions rather than compressing messages. Correspondingly, both agent 3 and agent 2 send a message to agent 1 (Fig. 3(c) and 3(f)), which is a redundant communication strategy.
The second example, hallway (Fig. 4(a)), is a Dec-POMDP with two agents randomly starting at states a1 to am and b1 to bn, respectively. Agents can observe their position and choose to move left, move right, or keep still at each timestep. Agents will win and get a reward of 10 if they arrive at state g simultaneously. Otherwise, if any agent arrives at g earlier than the other, the team will not be rewarded, and the next episode will begin. The horizon is set to max(m,n) + 10 to avoid an infinite loop.
Hallway aims to show that the miscoordination problem of full factorization methods can be severe in multi-step scenarios. We set m and n to 4 and show comparison of performance in Fig. 4(b). The miscoordination problem causes QMIX to lose about half of the games. We are again particularly interested in the message embedding representations learned by NDQ. We show an episode in Fig. 5. Two agents begin at a4 and b3, respectively. They first move left silently (t = 1 and t = 2) until agent B arrives at b1. On arriving b1, it sends a bit whose value is 5.24 to A. After sending this bit, B stays at b1 and sends this message repeatedly until it receives a bit from A indicating that A has arrived at a1. They then move left together and win. This is the minimized communication strategy. Taking advantage of this strategy, NDQ can still win in 100% of episodes when 80% of the communicating bits are dropped (Fig. 4(c)).
The third task, independent search, aims to demonstrate that NDQ can learn not to communicate in scenarios where agents are independent. Task description and results analysis are deferred to Appendix C.1.

heading: 5.2 MAXIMUM VALUE FUNCTION FACTORIZATION IN STARCRAFT II

text:
To demonstrate that the miscoordination problem of full decomposition methods is widespread in multi-agent learning, we apply our method and baselines to the StarCraft II micromanagement benchmark introduced by Samvelyan et al. (2019), which is described in detail in Appendix C.2. We further increase the difficulty of action coordination by i) reducing the sight range of agents from 9 to 2; ii) introducing challenging maps with complex terrain or highly random spawning po-
sitions for units. We test our method on the six maps shown in Fig. 6. Detailed descriptions of these scenarios are provided in Appendix C.2.
We use the same hyper-parameter setting for NDQ on all maps: β is set to 10−5, λ is set to 0.1, and the length of message mij is set to 3. For evaluation, we pause training every 100k environment steps and run 48 testing episodes. Other hyper-parameters for NDQ are described in Appendix B.2.

heading: 5.2.1 PERFORMANCE COMPARISON

text:
We show the performance of our method and baselines when no message is cut in Fig. 7. The superior performance of NDQ against QMIX demonstrates that the miscoordination problem of full factorization methods is widespread, especially in scenarios with high stochasticity, such as 1o2r vs 4r, 3b vs 1h1m, and 1o10b vs 1r. Notably, our method also outperforms the attentional
communication mechanism (QMIX+TarMAC) by a large margin. Since agents communicate in both of these two methods and the same TD error is used, these results highlight the role of the constraints that we impose on our message embedding. TarMAC struggles in all the scenarios. We believe that this is because it does not deal with the issue of reward assignment.

heading: 5.2.2 MESSAGE CUT OFF

text:
To demonstrate that our method can learn nearly decomposable Q-functions in complex tasks, we cut off 80% of messages according to the means of distributions when testing and show the results in Fig. 8. The results indicate that we can omit more than 80% of communication without significantly affecting performance. For comparison, we cut off messages in QMIX+TarMAC whose weights are 80% smallest and find that its performance drops significantly (Fig. 8). These results indicate that our method is more robust in terms of message cutting off compared to the attentional communication methods.
We further drop all the messages and show the developments of testing performance in Fig. 9. As expected, the win rates of NDQ decrease dramatically, proving that the superiority of our method when 80% of messages are dropped comes from expressive and succinct communication protocols.

heading: 6 CLOSING REMARKS

text: In this paper, we presented a novel multi-agent learning framework within the paradigm of centralized training with decentralized execution. This framework fuses value function factorization learning and communication learning and efficiently learns nearly decomposable value functions for agents to act most of the time independently and communicate when it is necessary for coordination. We introduce two information-theoretical regularizers to minimize overall communication while maximizing the message information for coordination. Empirical results in challenging StarCraft II tasks show that our method significantly outperforms baseline methods and allows us to reduce communication by more than 80% without sacrificing the performance. We also observe that nearly minimal messages (e.g., with one or two bits) are learned to communicate between agents in order to ensure effective coordination.

heading: APPENDIX

text:
A VARIATIONAL BOUND ON MUTUAL INFORMATION
In order to enable messages to effectively reduce the uncertainties in action-value functions of other agents, we propose to maximize the mutual information betweenAj andMij . We borrow ideas from the variational inference literature and derive a lower bound of this mutual information regularizer. Theorem 1. A lower bound of mutual information Iθc(Aj ;Mij |Tj ,M(-i)j) is
ET∼D,Minj ∼fm(T,j;θc) [ −CE [ p(Aj |T)‖qξ(Aj |Tj ,M inj ) ]] , (8)
where Tj is the local action-observation history of agent j, and T = 〈T1,T2, . . . ,Tn〉 is the joint local history sampled from the replay buffer D, qξ(Aj |Tj ,M inj ) is the variational posterior estimator with parameters ξ.

heading: Proof.

text:
Iθc(Aj ;Mij |Tj ,M(-i)j) (9)
= ∫ p(aj , τj ,m in j ) log
p(aj ,mij |τj ,m(-i)j) p(aj |τj ,m(-i)j)p(mij |τj ,m(-i)j) dajdτjdm in j (10)
= ∫ p(aj , τj ,m in j ) log
p(aj |τj ,minj ) p(aj |τj ,m(-i)j) dajdτjdm in j , (11)
where p(aj |τj ,minj ) is determined by the message encoder fm and Markov Chain:
p(aj |τj ,minj ) (12)
= ∫ p(τ−j , aj |τj ,minj )dτ−j (13)
= ∫ p(τ−j |τj ,minj )p(aj |τ )dτ−j ( According to [ aj ⊥ minj |τ ]) (14)
=
∫ p(τ )p(minj |τ )p(aj |τ )
p(τj ,minj ) dτ−j . (15)
We introduce qξ(aj |τj ,minj ) as a variational approximation to p(aj |τj ,minj ). Since
DKL(p(aj |τj ,minj )‖qξ(aj |τj ,minj ) ≥ 0, (16)
we have ∫ p(aj |τj ,minj ) log p(aj |τj ,minj )daj (17)
≥ ∫ p(aj |τj ,minj ) log qξ(aj |τj ,minj )daj . (18)
Thus, for the mutual information term:
Iθc(Aj ;Mij |Tj ,M(-i)j) (19) ≥ ∫ p(aj , τj ,m in j ) log
qξ(aj |τj ,minj ) p(aj |τj ,m(-i)j) dajdτjdm in j (20)
= ∫ p(aj , τj ,m in j ) log qξ(aj |τj ,minj )dajdτjdminj (21)
− ∫ p(aj , τj ,m in j ) log p(aj |τj ,m(-i)j)dajdτjdminj (22)
= ∫ p(τ )p(minj |τ )p(aj |τ ,minj ) log qξ(aj |τj ,minj )dajdτdminj (23)
− ∫ p(aj , τj ,m(-i)j) log p(aj |τj ,m(-i)j)dajdτjdm(-i)j (24)
= ∫ p(τ )p(minj |τ )p(aj |τ ) log qξ(aj |τj ,minj )dajdτdminj ( According to [ aj ⊥ minj |τ ]) (25)
+Hθc(Aj |Tj ,M(-i)j) (26) = ET∼D,Minj ∼fm(T,j;θc) [∫ p(aj |T) log qξ(aj |Tj ,M inj )daj ] (27)
+Hθc(Aj |Tj ,M(-i)j) (28) = ET∼D,Minj ∼fm(T,j;θc) [ −CE [ p(Aj |T)‖qξ(Aj |Tj ,M inj ) ]] (29)
+Hθc(Aj |Tj ,M(-i)j). (30)
Because Hθc(Aj |Tj ,M(-i)j) ≥ 0, we get the lower bound in Theorem 1.
B IMPLEMENTATION DETAILS

heading: B.1 DETAILS OF MESSAGE DROPPING

text: In our methods, not only the number of messages but also the length of messages are minimized. In other words, we send messages with varying lengths. However, messages are feed into an actionvalue function approximator at the recipient side, which requires inputs to have the same length. To solve this problem, we send masks indicating which bits are dropped along with the messages. To save channel bandwidth, masks are regarded as binary numbers, so each of them only consumes a negligible log-scale space compared to the length of messages. For the unsent bits, we fill in 0s before feeding the messages into the local utility functions.

heading: B.2 NETWORK ARCHITECTURE, HYPERPARAMETERS, AND INFRASTRUCTURE

text: We base our implementation on the PyMARL framework (Samvelyan et al., 2019) and use its default network structure and hyper-parameter setting for QMIX. For the message encoder, we use a fully connected network with one 64-dimensional hidden layer and ReLU activation. For the posterior estimator qξ, we adopt a fully connected network with two 20-dimensional hidden layers with ReLU activation. We train our models on NVIDIA RTX 2080Ti GPUs using experience sampled from 16 parallel environments. To benchmark NDQ, we train all algorithms for 20 million time steps on each StarCraft II unit micromanagement task and use the default hyper-parameter settings for baselines.

heading: C EXPERIMENTAL RESULTS

heading: C.1 DIDACTIC EXAMPLE: INDEPENDENT SEARCH

text:
In independent search, two agents are finding landmarks in two independent 5 × 5 rooms for 100 time steps (see Fig. 10). An agent is rewarded 1 when it is on the landmark in its room.
Independent search is an example where agents are totally independent. This task aims to demonstrate that our method can learn not to communicate in independent scenarios. We show team performance in Table 1. NDQ can achieve the optimal performance when agents do not communicate with each other.

heading: C.2 STARCRAFT II

text:
StarCraft unit micromanagement has attracted lots of research interests for its high degree of control complexity and environmental stochasticity. Usunier et al. (2017) and Peng et al. (2017) study this problem from a centralized perspective. In order to facilitate decentralized control, we use the setup introduced by Samvelyan et al. (2019).
We first describe the scenarios that we consider in detail. We consider combat scenarios where the enemy units are controlled by StarCraft II built-in AI (difficulty level is set to medium), and each of the ally units is controlled by a learning agent. The units of the two groups can be asymmetric, and the initial placement is random. At each time step, each agent chooses one action from the discrete action space consisting of the following actions: noop, move[direction], attack[enemy id], and stop. Under the control of these actions, agents move and attack in a continuous map. A global reward that is equal to the total damage dealt on the enemy units is given at each timestep. Killing each enemy unit and winning a combat induce extra bonuses of 10 and 200, respectively.
3b vs 1h1m: 3 Banelings try to kill a Hydralisk assisted by a Medivac. 3 Banelings together can just blow up the Hydralisk. Therefore, they should not give the Hydralisk rest time during which the Medivac can restore its health. Banelings have to attack at the same time to get the winning reward. This scenario is designed to test whether our method can learn a communication protocol to coordinate actions.
3s vs 5z: 3 Stalkers encounter 5 Zealots on a map. Zealots can cause high damage but are much slower so that Stalkers have to take advantage of a technique called kiting – Stalkers should alternatively attack the Zealots and flee for a distance.
1o2r vs 4r: An Overseer has found 4 Reapers. Its ally units, 2 Roaches, need to get there and kill the Reapers to win. At the beginning of an episode, the Overseer and Reapers spawn at a random point on the map while the Roaches are initialized at another random point. Given that only the Overseer knows the position of the enemy, a learning algorithm has to learn to deliver this message to the Roaches to effectively win the combat.
5z vs 1ul: 5 Zealots try to kill a powerful Ultralisk. A sophisticated micro-trick demanding right positioning and attack timing has to be learned to win.
MMM: Symmetric teams consisting of 7 Marines, 2 Marauders, and 1 Medivac spawn at two fixed points, and the enemy team is tasked to attack the ally team. To win the battle, agents have to learn to communicate their health to the Medivac.
1o10b vs 1r: In a map full of cliffs, an Overseer detects a Roach. The teammates of the Overseer, 10 Banelings, need to kill this Roach to get the winning reward. The Overseer and the Roach spawn at a random point while the Banelings spawn randomly on the map. In the minimized communication strategy, the Banelings can keep silent, and the Overseer needs to encode its position and send it to the Banelings. We use this task to test the performance of our method in complex scenarios.

title: LEARNING NEARLY DECOMPOSABLE VALUE FUNC- TIONS VIA COMMUNICATION MINIMIZATION