summaries: In this paper the authors present a Generative Adversarial Neural Networks with Xu et al.’s semantic loss applied to the generator. They call this GAN a Constrained Adversarial Network or (CAN) and identify it as a new class of GAN. The authors present three different problem domains for their experiments focused on the generation of constrained images, chunks of Super Mario Bros.-style levels, and molecules. For each domain they include particular constraints for the semantic loss, which biases the generator towards creating valid content according to these constraints.

summaries: This paper proposed Constrained Adversarial Networks (CAN), which incorporates structural constraints by augmenting a penalty term in the training object. The penalty term is formulated as the semantic loss proposed in [1] which can handle any logical constraints. Experiments are demonstrated to show the advantage of CAN over standard GAN in terms of whether the generated samples satisfy the hard constraints, and whether they are novel and unique.

summaries: The authors describe a method to improve the performance of generative adversarial networks in the task of generating structured objectives that have to satisfy complicated constraints. The proposed solution involves using an additional term in the GAN objective that penalizes the generation of invalid samples. This term, called the semantic loss, is given by a multiple of the log probability of the model generating valid samples.

abstractText: Despite their success, generative adversarial networks (GANs) cannot easily generate structured objects like molecules or game maps. The issue is that such objects must satisfy structural requirements (e.g., molecules must be chemically valid, game maps must guarantee reachability of the end goal) that are difficult to capture with examples alone. As a remedy, we propose constrained adversarial networks (CANs), which embed the constraints into the model during training by penalizing the generator whenever it outputs invalid structures. As in unconstrained GANs, new objects can be sampled straightforwardly from the generator, but in addition they satisfy the constraints with high probability. Our approach handles arbitrary logical constraints and leverages knowledge compilation techniques to efficiently evaluate the expected disagreement between the model and the constraints. This setup is further extended to hybrid logical-neural constraints for capturing complex requirements like graph reachability. An extensive empirical analysis on constrained images, molecules, and video game levels shows that CANs efficiently generate valid structures that are both high-quality and novel.

authors:
Martin Arjovsky
Soumith Chintala
Léon Bottou

title: Wasserstein generative adversarial networks

venue: In International conference on machine learning,

authors:
Supratik Chakraborty
Daniel J Fremont
Kuldeep S Meel
Sanjit A Seshia
Moshe Y Vardi

title: Distribution-aware sampling and weighted model counting for sat

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

authors:
Mark Chavira
Adnan Darwiche

title: On probabilistic inference by weighted model counting

venue: Artificial Intelligence,

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:
Hanjun Dai
Yingtao Tian
Bo Dai
Steven Skiena
Le Song

title: Syntax-directed variational autoencoder for molecule generation

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

title: Sdd: A new canonical representation of propositional knowledge bases

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

authors:
Nicola De Cao
Thomas Kipf

title: MolGAN: An implicit generative model for small molecular graphs

venue: arXiv preprint arXiv:1805.11973,

authors:
Laurent Dinh
David Krueger
Yoshua Bengio

title: Nice: Non-linear independent components estimation

venue: arXiv preprint arXiv:1410.8516,

authors:
I Donadello
L Serafini
AS d’Avila Garcez

title: Logic tensor networks for semantic image interpretation

authors:
Stefano Ermon
Carla P Gomes
Ashish Sabharwal
Bart Selman

title: Embed and project: Discrete sampling with universal hashing

venue: In Advances in Neural Information Processing Systems,

authors:
Rafael Gómez-Bombarelli
Jennifer N Wei
David Duvenaud
José Miguel Hernández-Lobato
Benjamı́n Sánchez-Lengeling
Dennis Sheberla
Jorge Aguilera-Iparraguirre
Timothy D Hirzel
Ryan P Adams
Alán Aspuru-Guzik

title: Automatic chemical design using a data-driven continuous representation of molecules

venue: ACS central science,

authors:
Ian Goodfellow
Jean Pouget-Abadie
Mehdi Mirza
Bing Xu
David Warde-Farley
Sherjil Ozair
Aaron Courville
Yoshua Bengio

title: Generative adversarial nets

authors:
Gabriel Lima Guimaraes
Benjamin Sanchez-Lengeling
Carlos Outeiral
Pedro Luis Cunha Farias
Alán Aspuru-Guzik

title: Objective-reinforced generative adversarial networks (ORGAN) for sequence generation models

venue: arXiv preprint arXiv:1705.10843,

authors:
Ishaan Gulrajani
Faruk Ahmed
Martin Arjovsky
Vincent Dumoulin
Aaron C Courville

title: Improved training of Wasserstein GANs

authors:
Matthew Guzdial
Mark Riedl

title: Game level generation from gameplay videos

venue: In Twelfth Artificial Intelligence and Interactive Digital Entertainment Conference,

authors:
Zhiting Hu
Xuezhe Ma
Zhengzhong Liu
Eduard H. Hovy
Eric P. Xing

title: Harnessing deep neural networks with logic rules

venue: The Association for Computer Linguistics,

authors:
Zhiting Hu
Zichao Yang
Ruslan R Salakhutdinov
LIANHUI Qin
Xiaodan Liang
Haoye Dong
Eric P Xing

title: Deep generative models with learnable knowledge constraints

authors:
Natasha Jaques
Shixiang Gu
Dzmitry Bahdanau
José Miguel Hernández-Lobato
Richard E Turner
Douglas Eck

title: Sequence tutor: Conservative fine-tuning of sequence generation models with kl-control

venue: In Proceedings of the 34th International Conference on Machine LearningVolume

authors:
Tero Karras
Timo Aila
Samuli Laine
Jaakko Lehtinen

title: Progressive growing of gans for improved quality, stability, and variation

authors:
Diederik Kingma
Max Welling

title: Auto-encoding variational Bayes

venue: In International Conference on Learning Representations,

authors:
Doga Kisa
Guy Van den Broeck
Arthur Choi
Adnan Darwiche

title: Probabilistic sentential decision diagrams

venue: In Fourteenth International Conference on the Principles of Knowledge Representation and Reasoning,

authors:
Daphne Koller
Nir Friedman

title: Probabilistic graphical models: principles and techniques

venue: MIT press,

authors:
Matt J Kusner
Brooks Paige
José Miguel Hernández-Lobato

title: Grammar variational autoencoder

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

authors:
Marco Lippi
Paolo Frasconi

title: Prediction of protein β-residue contacts by markov logic networks with grounding-specific

venue: weights. Bioinformatics,

authors:
Chris J Maddison
Andriy Mnih
Yee Whye Teh

title: The concrete distribution: A continuous relaxation of discrete random variables

venue: arXiv preprint arXiv:1611.00712,

authors:
Robin Manhaeve
Sebastijan Dumancic
Angelika Kimmig
Thomas Demeester
Luc De Raedt

title: DeepProbLog: Neural probabilistic logic programming

authors:
Giuseppe Marra
Francesco Giannini
Michelangelo Diligenti
Marco Gori

title: LYRICS: a General Interface Layer to Integrate AI and Deep Learning

authors:
Lars Mescheder
Sebastian Nowozin
Andreas Geiger

title: The numerics of gans

authors:
Lars Mescheder
Andreas Geiger
Sebastian Nowozin

title: Which training methods for gans do actually converge

venue: arXiv preprint arXiv:1801.04406,

authors:
Takeru Miyato
Toshiki Kataoka
Masanori Koyama
Yuichi Yoshida

title: Spectral normalization for generative adversarial networks

venue: arXiv preprint arXiv:1802.05957,

authors:
Sebastian Nowozin
Botond Cseke
Ryota Tomioka

title: f-GAN: Training generative neural samplers using variational divergence minimization

authors:
Alec Radford
Luke Metz
Soumith Chintala

title: Unsupervised representation learning with deep convolutional generative adversarial networks

venue: arXiv preprint arXiv:1511.06434,

authors:
Danilo Jimenez Rezende
Shakir Mohamed
Daan Wierstra

title: Stochastic backpropagation and approximate inference in deep generative models

venue: In International Conference on Machine Learning,

authors:
Tim Rocktäschel
Sebastian Riedel

title: End-to-end differentiable proving

authors:
Tim Salimans
Ian Goodfellow
Wojciech Zaremba
Vicki Cheung
Alec Radford
Xi Chen

title: Improved techniques for training gans

authors:
Bidisha Samanta
Abir De
Niloy Ganguly
Manuel Gomez-Rodriguez

title: Designing random graph models using variational autoencoders with applications to chemical design

venue: arXiv preprint arXiv:1802.05283,

authors:
Ari Seff
Wenda Zhou
Farhan Damani
Abigail Doyle
Ryan P Adams

title: Discrete object generation with reversible inductive construction

authors:
Sam Snodgrass
Santiago Ontanón

title: Controllable procedural content generation via constrained multi-dimensional markov chain sampling

venue: In IJCAI,

authors:
Gustav Sourek
Vojtech Aschenbrenner
Filip Zelezny
Steven Schockaert
Ondrej Kuzelka

title: Lifted relational neural networks: Efficient learning of latent relational structures

venue: Journal of Artificial Intelligence Research,

authors:
Adam Summerville
Michael Mateas

title: Super mario as a string: Platformer level generation via lstms

venue: arXiv preprint arXiv:1603.00930,

authors:
Adam Summerville
Sam Snodgrass
Matthew Guzdial
Christoffer Holmgård
Amy K Hoover
Aaron Isaksen
Andy Nealen
Julian Togelius

title: Procedural content generation via machine learning (pcgml)

venue: IEEE Transactions on Games,

authors:
Adam James Summerville
Sam Snodgrass
Michael Mateas
Santiago Ontanón

title: The vglc: The video game level corpus

venue: arXiv preprint arXiv:1606.07487,

authors:
Jerry Talton
Lingfeng Yang
Ranjitha Kumar
Maxine Lim
Noah Goodman
Radomı́r Měch

title: Learning design patterns with bayesian grammar induction

venue: In Proceedings of the 25th annual ACM symposium on User interface software and technology,

authors:
Ruben Rodriguez Torrado
Ahmed Khalifa
Michael Cerny Green
Niels Justesen
Sebastian Risi
Julian Togelius

title: Bootstrapping conditional gans for video game level generation

authors:
Aaron Van Oord
Nal Kalchbrenner
Koray Kavukcuoglu

title: Pixel recurrent neural networks

authors:
Vanessa Volz
Jacob Schrum
Jialin Liu
Simon M Lucas
Adam Smith
Sebastian Risi

title: Evolving mario levels in the latent space of a deep convolutional generative adversarial network

venue: In Proceedings of the Genetic and Evolutionary Computation Conference,

authors:
Po-Wei Wang
Priya Donti
Bryan Wilder
Zico Kolter

title: Satnet: Bridging deep learning and logical reasoning using a differentiable satisfiability solver

authors:
Jingyi Xu
Zilu Zhang
Tal Friedman
Yitao Liang
Guy Broeck

title: A semantic loss function for deep learning with symbolic knowledge

authors:
Yexiang Xue
Willem-Jan van Hoeve

title: Embedding decision diagrams into generative adversarial networks

venue: In International Conference on Integration of Constraint Programming, Artificial Intelligence, and Operations Research,

authors:
Han Zhang
Tao Xu
Hongsheng Li
Shaoting Zhang
Xiaogang Wang
Xiaolei Huang
Dimitris N Metaxas

title: Stackgan: Text to photo-realistic image synthesis with stacked generative adversarial networks

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

authors:
Jun-Yan Zhu
Taesung Park
Phillip Isola
Alexei A Efros

title: Unpaired image-to-image translation using cycle-consistent adversarial networks

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

heading: 1 INTRODUCTION

text:
Generative Adversarial Networks (GANs) (Goodfellow et al., 2014) have shown impressive performance on challenging tasks – like image generation (Karras et al., 2018), text-to-image (Zhang et al., 2017), and style transfer (Zhu et al., 2017) – where the goal is to produce believable configurations.
A number of important applications, however, require to generate objects that are both credible and feasible with respect to hard structural constraints. Examples include generating drug molecules, which must satisfy chemical validity requirements, and game levels, where the goal must be reachable from the starting position. Recent studies (Guimaraes et al., 2017; De Cao & Kipf, 2018; Xue & van Hoeve, 2019) observed that GANs struggle in these tasks. The main reason is that the training examples alone are insufficient to capture the feasibility constraints and thus to guide the model toward producing valid objects.
As a remedy, we propose Constrained Adversarial Networks (CANs), a class of generative models that extend GANs to structured domains. Given a set of examples drawn from a latent distribution and a set of structural constraints, CANs learn to output valid structured with high probability. This is achieved by augmenting the standard GAN loss with a penalty term that discourages the model from producing infeasible structures. Since CANs inject the constraints directly into the learned model, valid structures can be obtained with high probability by performing forward inference on the generator, avoiding the need for costly sampling or optimization steps (Volz et al., 2018).
The penalty term is implemented using the semantic loss (SL) (Xu et al., 2018). The SL leverages knowledge compilation (Darwiche, 2011) to represent arbitrary Boolean constraint as a circuit and uses the latter to measure the mass allocated by the generator to infeasible objects. The procedure is probabilistically sound, exact, and does not require sampling. Notably, the circuit, which can be quite large depending on the complexity of the constraints, can be thrown away after learning.
In addition, we show how to extend the SL complex constraints that would normally lead to intractably large circuits. This is accomplished by first using a neural network to map configurations to a different space in which the structural constraints can be compactly encoded, and then applying the SL to the latter. This enables us to deal with reachability on a graph, which is beyond the reach of
standard SL. Finally, we show how the validity constraints baked into the generator can be enabled or disabled during inference using ideas from InfoGANs Chen et al. (2016).
In summary, we contribute:
• Constrained Adversarial Networks (CANs), a generalization of GANs in which the generator is encouraged (at training time) to output valid structures with high probability via forward inference.
• An extensive empirical analysis on structured objects like constrained images, molecules, and video game levels showing that CANs generate structures that are stylistically coherent with the training data.
• A decomposition of intractably complex constraints into a neural and logical components, showcased on graph reachability for video game level synthesis.

heading: 2 UNCONSTRAINED GANS

text:
Let X be the object space and Z some latent space. GANs (Goodfellow et al., 2014) are composed of a generator g : Z → X and a discriminator d : X → [0, 1], both implemented as neural networks. The discriminator is trained to recognize “real” objects x taken from the data distribution Pr, while the generator is trained to map random latent vectors z ∈ Rm to “fake” objects that fool the discriminator. Learning amounts to solving the minimax game:
min g max d fGAN(g, d) fGAN(g, d) := Ex∼Pr [logPd(x)] + Ex∼Pg [log(1− Pd(x))] (1)
Here Pg(x) is the distribution induced by the generator and Pd(x) := Pd(real |x) by the discriminator. It is worth noting that the value of the game defines (a constrained form of) the Jensen-Shannon entropy and that Eq. 1 can be viewed as divergence minimization (Nowozin et al., 2016; Mescheder et al., 2017). After training, new objects can be generated by sampling random vectors z and mapping them to object space with the generator x = g(z).
Goodfellow et al. (2014) have shown that, under idealized assumptions, the learned generator g matches the data distribution, that is Pg = Pr. We report their theorem here for completeness:
Theorem 1. So long as (i) g and d are non-parametric, and (ii) the leftmost expectation in Eq. 1 is approximated arbitrarily well by the examples alone, any global equilibrium (g∗, d∗) of Eq. 1 satisfies Pd∗ ≡ 12 and Pg∗ ≡ Pr.
Finding Nash equilibria of non-convex games like Eq. 1 is notoriously hard, rendering GAN training very challenging. The most common optimization algorithm is alternating gradient descent, whereby d and g are optimized sequentially, or the more well-understood simultaneous gradient descent (Mescheder et al., 2017). A common failure state is mode collapse, whereby the generator outputs objects concentrated in a tiny portion of the object space. A plethora of theoretical and empirical remedies have been proposed, cf. (Salimans et al., 2016; Mescheder et al., 2018), including using alternative divergences (Nowozin et al., 2016; Arjovsky et al., 2017) and encouraging smoothness of the discriminator by, e.g., controlling the spectral norm of its parameters (Miyato et al., 2018). In our experiments, we apply some of these strategies to stabilize training.
In structured tasks, the objects of interest are usually discrete. GANs can be adapted to such settings by having the generator output a categorical distribution θ(z) overX and sampling objects from the latter. Below, we will focus on stochastic generators of this kind, although alternatives do exist (Gulrajani et al., 2017). In this setting Pg(x) = ∫ Pg(x|z)p(z)dz = ∫ θ(z)p(z)dz = Ez[θ(z)].

heading: 3 GENERATING STRUCTURES WITH CANS

text:
Our goal is to learn to generate structures x consistent with respect to some validity constraint ψ according to some unobserved distribution Pr. Throughout, we will make the following assumptions:
1. A single validity constraint ψ is provided as input. This is without loss of generality: if multiple constraints are necessary, then ψ can be taken to be their conjunction.
2. The constraint ψ is compatible with the data distribution, that is, the support of Pr falls entirely within the feasible region determined by ψ.
These assumptions hold in many tasks of interest, including all generative problems with known well-formedness requirements. For the sake of simplicity, we restrict our study to binary (i.e. 0– 1) variables and logical constraints (aka formulas) only. This is a very general setup: any discrete structured space can be encoded using binary variables and formulas, at the cost of a larger model.
Limitations of GANs Generators learned with the standard GAN training rule can output invalid structures, for two main reasons. First, for non-trivial constraints ψ, any finite set of examples that satisfy the constraint is insufficient to capture the full semantics of ψ. Second, in many cases of interest the examples are not even consistent with ψ. This more challenging case shows that regular GANs are easily lured into learning not to satisfy the constraint. More formally: Corollary 1. Under the assumptions of Theorem 1, given a target distribution Pr, a constraint ψ consistent with it, and a dataset of examples x sampled i.i.d. from a corrupted distribution P̃r 6= Pr inconsistent with ψ, GANs associate non-zero mass to infeasible objects.
Indeed, by Theorem 1, the optimal generator satisfies Pg ≡ P̃r, which is inconsistent with ψ. Ergo,∑ x 1 {x 6|= ψ}Pg(x) > 0. We stress that Theorem 1 captures the intent of GAN training, and thus this simple corollary shows that GANs are by design incapable of handling invalid examples.
Constrained adversarial networks In order to avoid these issues, constrained adversarial networks (CANs) take both the examples and the validity constraint into account during learning. More specifically, the CAN value function is designed so that the generator maximizes the probability of generating valid structures Pg(ψ) := Ex∼Pg [1 {x |= ψ}], that is:
fCAN(g, d) := fGAN(g, d)− λ logPg(ψ) (2) Here λ > 0 is a hyper-parameter controlling the importance of the constraint. Since the second term is always non-negative, the CAN value function upper bounds the GAN one (Eq. 1).
The second term is the so-called semantic loss (SL), proposed in (Xu et al., 2018) to inject knowledge into neural networks, and it is formally defined as SLψ (g) ∝ − logPg(ψ), where: Pg(ψ) = ∑ x′ 1 {x′ |= ψ}Pg(x′) = Ez[ ∑ x′∈X :x′|=ψ ∏ i : x′i=1 θi(z) ∏ i : x′i=0 (1− θi(z))] (3) Recall that θ(z) is the categorical distribution output by the generator g for z, while x′ |= ψ means that x′ satisfies constraint ψ. Hence the sum runs over all configurations x′ consistent with ψ. The SL can also be viewed as the negative log-likelihood of ψ w.r.t. the generator. This shows that, in Eq. 2, the SL rewards the generator g proportionally to the mass it allocates to valid structures. Since the SL is the negative logarithm of a polynomial in θ, it is fully differentiable (so long as Pψ(g) 6= 0, which is always the case in practice).
If the SL is given large enough weight, CANs are strongly encouraged to generate valid structures in expectation. Under the preconditions of Theorem 1, it can be shown that or λ→∞ CANs generate valid structures only: Proposition 1. Under the assumptions of Corollary 1, CANs associate zero mass to infeasible objects, irrespective of the discrepancy between Pr and P̃r.
Intuitively, this holds because with λ =∞ any global equilibrium (g∗, d∗) of mingmaxd fCAN(g, d) must minimize the second term. If g is non-parametric, then the minimum is attained with logPg∗(ψ) = 0, which is equivalent to Pg∗(ψ) = 1. This in turn implies that Pg∗(¬ψ) = 0, proving the claim. Of course, as with standard GANs, the prerequisites are often violated in practice. Regardless, Proposition 1 works as a sanity check, and shows that – in contrast to GANs – CANs are appropriate for constrained generative tasks.
Computing the semantic loss Naı̈ve evaluation of the SL (Eq. 3) involves summing over all (exponentially many) possible configurations x′, which is intractable. More generally, computing the SL amounts to weighted model counting, which is #P-complete (Chavira & Darwiche, 2008).
For many constraints of interest, however, the polynomial in Eq. 3 can be factorized into a much more compact form and evaluated very efficiently. Following Xu et al. (2018), we make use of
knowledge compilation to automatically factorize the polynomial by compiling it into an arithmetic circuit (more specifically, into a sentential decision diagram (SDD) (Darwiche, 2011)). When the resulting circuit is small enough, evaluation of the SL and of its gradient are extremely efficient, as shown in (Xu et al., 2018).
The main downside of knowledge compilation is that, depending on the complexity of the constraint ψ at hand, the compiled circuit may be very large. This is less of a problem during training, which is often performed on powerful machines, but it can be an issue for inference – especially on embedded devices. However, in CANs the circuit is not required for inference (as it consists of a simple forward pass over the generator), and thus it can be thrown away after training. This means that CANs incur no space penalty during inference when compared to GANs.
Dealing with intractable constraints When fed a particularly complex constraint, knowledge compilation may produce a circuit too large even for the training stage. In this case, we approximate the semantic loss by first mapping the objects from X to an application-specific space where ψ can be expressed in compact form, and then use the semantic loss on top of the transformed objects. We successfully employed this technique to synthesize mario levels where the goal tile is reachable from the starting tile; all details are provided below. The same technique can be exploited for dealing with very complex logical formulas beyond the reach of state-of-the-art knowledge compilation.

heading: 4 EXPERIMENTS

text:
We implemented CANs using Tensorflow and used PySDD1 to compile the constraint into a compact circuit for computing the Semantic Loss. We tested CANs using different generator architectures on one synthetic and two real-world structured generative tasks2. In all cases, we evaluated the objects generated by CANs and those of the baselines using three metrics (adopted from Samanta et al. (2018)):
• validity is the proportion of sampled objects that are valid; • novelty is the proportion of valid sampled objects that are not present in the training data; • uniqueness is the proportion of valid unique (non-repeated) sampled objects;
Our experimental evaluation aims at answering the following questions:
• Q1 Can CANs with tractable constraints achieve better results than GANs? • Q2 Can CANs with intractable constraints achieve better results than GANs? • Q3 Can constraints be combined with rewards to achieve better results than using rewards
only?

heading: 4.1 CONSTRAINED IMAGES

text:
In this synthetic experiment, we used CANs to generate small, strongly constrained bitmap images. The training set is composed of 23, 040 black-and-white 20 × 20 images, each with a black background and two randomly placed random polygons – either a triangle (30% of the cases), a square (30%), or a diamond (40%). The two polygons are always different from each other, fully contained in the canvas, and do not overlap. The leftmost and rightmost columns are special, in that they contain parity information about the image. More specifically, row r of the leftmost column encodes the parity bit for all pixels in the left half of row r, see Fig. 1 (left) for an illustration. The rightmost column does the same for the right half of the image. Fig. 1 (middle) shows a sample image. As a baseline GAN, we implemented the generator and discriminator as deconvolutional and convolutional networks, respectively, sampling from the concrete distribution (Maddison et al., 2016) and using the vanilla loss. The CAN uses the same architecture, except for the extra semantic loss term which encodes the parity constraints using XOR formulas.
1URL:https://pypi.org/project/PySDD/ 2Details can be found in the Appendix. Our code is publicly available at the URL:ANONYMIZED
Fig. 1 (right) shows the results in terms of validity, novelty and uniqueness computed over 300 objects generated using CANs (with λ = 1) and Vanilla GANs, where novelty and uniqueness are computed over the subset of valid objects. CANs generate more valid objects, improving at the same time both novelty and uniqueness. These results allow to answer Q1 affirmatively. Note that in this experiment, using CANs over Vanilla GANs results in a negligible training overhead. On average, training CANs takes 30 minutes against the 27 minutes taken by Vanilla GANs.

heading: 4.2 SUPER MARIO BROS LEVEL GENERATION

text:
In the next experiment we show how CANs can help in the challenging task of learning to generate videogame levels from user-authored content. While procedural approaches to videogame level generation have successfully been used for decades, the application of machine learning techniques in the creation of (functional) content is a relatively new area of research (Summerville et al., 2018). On the one hand, modern video game levels are characterized by aesthetical features that cannot be formally encoded and thus are difficult to implement in a procedure, which motivates the use of ML techniques for task. On the other hand, the levels have often to satisfy a set of functional (hard) constraints that are easy to guarantee when the generator is hand-coded but pose challenges for current machine learning models.
In the following, we show how the semantic loss can be used to encode useful hard constraints in the context of videogame level generation. These constraints might be functional requirements that apply to every generated object or might be contextually used to steer the generation towards objects with certain properties. In our empirical analysis, we focus on Super Mario Bros (SMB), possibly one of the most studied video games in tile-based level generation. See Section 5 for related work in SMB level generation.
Recently, Volz et al. (2018) applied Wasserstein GANs (WGANs) (Arjovsky et al., 2017) to SMB level generation. The approach works by first training a generator in the usual way, then using an evolutionary algorithm called Covariance Matrix Adaptation Evolution Strategy (CMA-ES) to search for the best latent vectors according to a user-defined fitness function on the corresponding levels. We stress that this technique is orthogonal to CANs and the two can be combined together. Nonetheless, in the following we compare CANs with CMA-ES, as both techniques can be used to steer the network towards the generation of playable levels, i.e. having a feasible path3 from the left-most to the right-most column of the level. Pictures in 2 shows two SMB levels generated by our CAN using the semantic loss.
In CMA-ES, the fitness function doesn’t have to be differentiable and the playability can be computed on the output of an A* agent playing the level. Having the SL to steer the generation towards playable levels is not trivial, since it requires a differentiable definition of playability. Encoding the reachability of the right-most column with a propositional formula on the level variables x is unfeasible (consider the size of the formula resulting from unrolling and grounding a compact first-order encoding). For this reason, our CAN applies the semantic loss to a different probability distribution θ over binary variables r, with the intended meaning that ri is true if and only if the tile xi is
3According to the game’s physics.
reachable (in expectation) from the first column in the level x, with x sampled from the generator’s multinomial distribution γ over tiles. Encoding the playability of a level is straightforward in r, although the problem becomes finding a fully differentiable transformation PR : Γ→ Θ.
We approximate PR with a feedforward neural network P̂R. Our approach consists in pretraining P̂R with synthetic data {(γi, θ̂i)}, consisting of syntetic distributions labelled using the tile-based pathfinder provided in Summerville et al. (2016). Inputs γi are collected from previous runs of the generator, while θ̂i are computed by sampling 100 levels from γi and averaging the reachability of each tile using the pathfinder’s output. The data generation process is inexpensive, allowing to train P̂R to reasonable performance for the task.
We adopt the same experimental setting, WGAN architecture and training procedure of Volz et al. (2018). The structured objects are 14 × 28 tile-based representations of SMB levels (e.g. Fig. 2) and the training data is obtained by sliding a 28 tiles window over levels from the Video game level corpus (Summerville et al., 2016). In this experiment we train on individual levels, as in (Volz et al., 2018), to be consistent with MarioGAN, but we stress that CANs can be trained on multiple levels.
Our semantic loss, applied on the output of the approximated reachability map P̂R, encodes that at least 4 tiles of the right-most column are reachable. This choice is supported by two observations: if a tile is reachable, the same will probably be neighbours and the approximation given by P̂R may satisfy too easily a constraint asking for only 1 reachable tile in the rightmost column.
Table 1 shows the playability, novelty and uniqueness of a batch of 1000 levels generated respectively by the CAN with a forward pass (with λ = 0.01, which validation experiments showed to be a reasonable trade-off between SL and discriminator loss) and by CMA-ES using the default parameters for the search. Novelty and Uniqueness are notably higher compared to the syntetic case due to a much larger output space4. Results show that CANs achieve comparable results on the first level, and substantial improvements on the second. Moreover, no significant negative effects can be seen on the generated material with respect to the quality of the ones generated by the original GAN.
Moreover, at the cost of pretraining P̂R (1h35m on a 8-core machine with a GTX1080Ti), CANs avoid the execution of the A* agent during the generation, sampling high quality objects in milliseconds. On the other side, the training cost is slightly lower (∼ 20% less), but each run of CMA-ES, to find a single best individual, takes between 20 and 25 minutes on the previously described machine.
4The size of the output space is 13(14×28) solutions (with 13 being the number ofdifferent tiles)
Combining the two approaches and refining the constraints for the generation of state-of-the-art Super Mario levels is a promising research direction and is left for future work.
With these results, we can answer Q2 affirmatively.

heading: 4.3 MOLECULE GENERATION

text:
In the next experiment, we test how effective is SL in conjunction with different forms of supervision on the task of generating molecules with certain desirable chemical properties. Specifically, we consider MolGANs (De Cao & Kipf, 2018), a model that combines the adversarial loss with a reinforcement learning objective, used to maximize the druglikeness, sythesizability and solubility of the generated molecules. The reward is computed by a network that is trained to match the score provided by an external cheminformatics software. In contrast with our previous experimental settings, here the structured objects are undirected graphs of bounded maximum size, represented by discrete tensors that encode the atom/node type (padding atom (no atom), Carbon, Nitogren, Oxygen, Fluorine) and the bound/edge type (padding bond (no bond), single, double, triple and aromatic bond).
As confirmed by both the results reported by the authors of MolGANs and our previous experiments, providing an additional loss term might perturbate the already unstable adversarial game, possibly incurring in mode collapse. In the following, we explore the use of SL beyond the satisfaction of given constraints. Specifically, we observe that the formula can involve the latent variables too, and we show how this can be leveraged to increase the diversity of the generator’s output and to mitigate the mode collapse. This can be achieved by using a portion of the latent vector (whose values are in the [0, 1] domain) to trigger on and off SL terms that promote the presence of specific atoms in the molecule. Specifically, we apply the SL to MolGANs, making use of 4 latent dimensions to control the presence of one of the 4 types of atoms considered in the experiment. Each dimension represents the probability of having at least one atom of that type in the molecule, no matter the position. Assigning SL terms to specific subregion of the latent space is a general approach that can potentially be used to achieve some level of controllable constrained generation via the latent codes. We defer this research direction to future work.
In this experiment, we augment MolGAN with our constraints conditioned on the latent variables, starting from the first epoch. We consider two different variants of the reward network. In the first setting, the network implicitly rewards validity and the maximization of the three chemical properties at once: QED (druglikeness), SA (synthesizability) and logP (solubility). The experimental setting and evaluation metrics are identical to De Cao & Kipf (2018) except for the introduction of the SL, we thus report the same results for the baseline. In the second setting, the reward is proportional to the diversity of the generated batch, thus boosting the generator uniqueness. In this case, the training stops when the validity reaches 0.99.
The results, as shown in Table 2, indicate that the SL term is boosting the diversity of the generated molecules without negatively affecting the other metrics with both reward functions. This preliminary results seem to suggest that CANs can be successfully coupled with a reinforcement learning objective, answering Q3 affermatively. In this setting, using CANs produced a negligible overhead during the training with respect to the original model, providing further evidence that the technique doesn’t heavily impact on the training.

heading: 5 RELATED WORK

text:
Deep generative modeling has recently enjoyed substantial progress with the introduction of autoregressive models (Van Oord et al., 2016), variational autoencoders (VAEs) (Kingma & Welling, 2014; Rezende et al., 2014), flow-based approaches (Dinh et al., 2014), and GANs (Goodfellow et al., 2014). However, none of these approaches is designed to generate structures.
Traditional approaches to such tasks, like graphical models (Koller & Friedman, 2009; Richardson & Domingos, 2006) and probabilistic grammars (Talton et al., 2012), are ill-suited for complex tasks like image generation and do not support efficient inference under constraints. Tractable probabilistic circuits (e.g., probabilistic sentential decision diagrams (Kisa et al., 2014)) leverage knowledge compilation techniques – like CANs – and sport high capacity, efficient inference, and support for constraints, but they require the circuit even at inference time, meaning that inference can have large space requirements. Further, the runtime of inference depends on the size of the circuit. In contrast, inference in CANs boils down to a forward pass over the generator and does not rely on the circuit output by knowledge compilation. Finally, although solver-based approaches to constrained discrete sampling like (Ermon et al., 2013; Chakraborty et al., 2014) guarantee validity of the samples, they are also much slower than CANs and do not support learning the distribution from data.
Injecting knowledge into learned models, and neural networks in particular, is a long-standing aim of machine learning. Early approaches include grounding-specifica Markov Logic Networks (Lippi & Frasconi, 2009), which combine Markov logic with neural networks. More recent models include target-specific architectures (Rocktäschel & Riedel, 2017; Donadello et al., 2017), as well as frameworks based on probabilistic logics (Manhaeve et al., 2018) and T-norms (Marra et al., 2019). Other recent approaches include also constraint learning component (Wang et al., 2019; Sourek et al., 2018). However, none of these models is at the same time generative and probabilistic.
Posterior regularization (PR) has been used to introduce logic background knowledge into deep discriminative (Hu et al., 2016) and discriminative models (Hu et al., 2018). Like the Semantic Loss, PR can convert arbitrary discrete constraints into a loss. In addition, it does not require the target model to have an explicit density. The major downside of the PR is that it is not semantically consistent: rewriting a constraint (by applying e.g. De Morgan’s laws) can lead to different loss functions. This never happens with the SL. Further, unlike the approach of (Hu et al., 2018), CANs do not need to define and train an approximate variational distribution: the SL is computed directly on the generator.
A number of machine learning techniques were applied to Super Mario Bros level generation, e.g. LSTMs (Summerville & Mateas, 2016), probabilistic graphical models (Guzdial & Riedl, 2016) and multi-dimensional Markov Chain Monte Carlo (Snodgrass & Ontanón, 2016). Torrado et al. (2019) leverages GANs, but differs from our work in that they consider level generation only and they constrain the mixture of tiles appearing in the level5. This technique cannot be easily generalized to arbitrary constraints. Many approaches to molecule generation use VAEs (Gómez-Bombarelli et al., 2018; Kusner et al., 2017; Dai et al., 2018). Closest to MolGANs are ORGANs (Guimaraes et al., 2017) and Sequence Tutor (Jaques et al., 2017), both using a reinforcement learning objective (with SeqGANs and RNNs respectively) to generate molecules as sequences in SMILE encoding. Finally, the approach of Seff et al. (2019) use MCMC to sample graph representations of valid molecules. Compared to CANs, their approach requires an expensive inference procedure based on Gibbs sampling, which must be additionally bootstrapped by providing a valid configuration. When the space is constrained by an arbitrary logical formula, as in our case, this last step is NP-complete.

heading: 6 CONCLUSION

text:
We presented Constrained Adversarial Networks (CANs), a generalization of GANs in which the generator is encouraged during training to output valid structures. CANs make use of the semantic loss (Xu et al., 2018) to measure the mass allocated by the generator to invalid structures and penalize the latter accordingly. As in GANs, generating (likely) valid structures then amounts to a simple forward pass of the generator. Importantly, the data structures used by the SL – which can be large if the structural constraints are very complex – can be discarded after training. Our framework
5This work is a pre-print and the code is not publicly available yet, so no comparison could be made.
was proven to be effective in different structured generative tasks, improving the validity of the generated structures (on average) while keeping the computational cost of training under control and substantially reducing inference runtimes. We also showed how the constraints to be turned on and off at inference time, suggesting different uses for the SL, namely promoting diversity of the generator’s outputs. Finally, our level generation experiment shows how to transform structures to a space in which the structural constraints are easier to encode and more compact.


summaries: This paper proposes a learnable piece-wise linear activation unit whose hinges are placed symmetrically. It gives a proof on the universality of the proposed unit on a certain condition. The superiority of the method is empirically shown. The change of the activation during training is analyzed and insight on the behavior is provided. The robustness to adversarial attacks is also empirically examined.

summaries: This paper proposes the S-APL (Symmetric Adaptive Piecewise Linear) activation function, based on the APL activation function proposed by (Agostinelli et al, 2014). This activation function is constructed as a piecewise linear function that is learned concurrently with training, and, in the case of S-APL, the activation function is forced to be symmetric. S-APL is claimed to help both with trainability and robustness of neural networks to adversarial examples.

summaries: In this paper, a new activation function, i.e. S-APL is proposed for deep neural networks. It is an extension of the APL activation, but is symmetric w.r.t. x-axis. It also has more linear pieces (actually S pieces, where S can be arbitrarily large) than the existing activation functions like ReLU. Experimental results show that S-APL can be on par with or slightly better than the existing activation functions on MNIST/CIFAR-10/CIFAR-100 datasets with various networks. The authors also show that neural networks with the proposed activation can be more robust to adversarial attacks.

abstractText: Deep neural networks with learnable activation functions have shown superior performance over deep neural networks with fixed activation functions for many different problems. The adaptability of learnable activation functions adds expressive power to the model which results in better performance. Here, we propose a new learnable activation function based on Adaptive Piecewise Linear units (APL), which 1) gives equal expressive power to both the positive and negative halves on the input space and 2) is able to approximate any zero-centered continuous non-linearity in a closed interval. We investigate how the shape of the SymmetricAPL function changes during training and perform ablation studies to gain insight into the reason behind these changes. We hypothesize that these activation functions go through two distinct stages: 1) adding gradient information and 2) adding expressive power. Finally, we show that the use of Symmetric-APL activations can significantly increase the robustness of deep neural networks to adversarial attacks. Our experiments on both black-box and open-box adversarial attacks show that commonly-used architectures, namely Lenet, Network-in-Network, and ResNet-18 can be up to 51% more resistant to adversarial fooling by only using the proposed activation functions instead of ReLUs.

authors:
Forest Agostinelli
Matthew Hoffman
Peter Sadowski
Pierre Baldi

title: Learning activation functions to improve deep neural networks

authors:
Nicholas Carlini
David Wagner

title: Towards evaluating the robustness of neural networks

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

authors:
Djork-Arné Clevert
Thomas Unterthiner
Sepp Hochreiter

title: Fast and accurate deep network learning by exponential linear units (elus)

authors:
Guneet S. Dhillon
Kamyar Azizzadenesheli
Zachary C. Lipton
Jeremy Bernstein
Jean Kossaifi
Aran Khanna
Anima Anandkumar

title: Stochastic activation pruning for robust adversarial defense, 2018

authors:
Ian J Goodfellow
Jonathon Shlens
Christian Szegedy

title: Explaining and harnessing adversarial examples

venue: arXiv preprint arXiv:1412.6572,

authors:
Kaiming He
Xiangyu Zhang
Shaoqing Ren
Jian Sun

title: Delving deep into rectifiers: Surpassing human-level performance on imagenet classification

venue: IEEE International Conference on Computer Vision (ICCV),

title: Deep residual learning for image recognition

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

authors:
Sergey Ioffe
Christian Szegedy

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

venue: arXiv preprint arXiv:1502.03167,

authors:
Xiaojie Jin
Chunyan Xu
Jiashi Feng
Yunchao Wei
Junjun Xiong
Shuicheng Yan

title: Deep learning with s-shaped rectified linear activation units

venue: In Thirtieth AAAI Conference on Artificial Intelligence,

authors:
Maryam Mahsal Khan
Arbab Masood Ahmad
Gul Muhammad Khan
Julian F Miller

title: Fast learning neural networks using cartesian genetic

venue: programming. Neurocomputing,

title: T test as a parametric statistic

venue: Korean journal of anesthesiology,

authors:
Günter Klambauer
Thomas Unterthiner
Andreas Mayr
Sepp Hochreiter

title: Self-normalizing neural networks

venue: In Advances in neural information processing systems,

authors:
Alex Krizhevsky
Vinod Nair
Geoffrey Hinton

title: Cifar-10 (canadian institute for advanced research). URL http://www.cs.toronto.edu/ ̃kriz/cifar.html

venue: Yann LeCun and Corinna Cortes. MNIST handwritten digit database

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

title: Gradient-based learning applied to document recognition

venue: Proceedings of the IEEE,

authors:
Hongyang Li
Wanli Ouyang
Xiaogang Wang

title: Multi-bias non-linear activation in deep neural networks

venue: In International conference on machine learning,

authors:
Andrew L. Maas
Raymond E. Daly
Peter T. Pham
Dan Huang
Andrew Y. Ng
Christopher Potts

title: Learning word vectors for sentiment analysis

venue: In Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies,

authors:
Andrew L Maas
Awni Y Hannun
Andrew Y Ng

title: Rectifier nonlinearities improve neural network acoustic models

venue: In Proc. icml,

authors:
Laurens van der Maaten
Geoffrey Hinton

title: Visualizing data using t-sne

venue: Journal of machine learning research,

authors:
Vinod Nair
Geoffrey E Hinton

title: Rectified linear units improve restricted boltzmann machines

venue: In Proceedings of the 27th international conference on machine learning

authors:
Paolo Napoletano
Flavio Piccoli
Raimondo Schettini

title: Anomaly detection in nanofibrous materials by cnn-based self-similarity

venue: Sensors (Basel, Switzerland),

title: Parallel distributed genetic programming

venue: University of Birmingham, Cognitive Science Research Centre,

authors:
Adnan Siraj Rakin
Jinfeng Yi
Boqing Gong
Deliang Fan

title: Defend deep neural networks against adversarial examples via fixed anddynamic quantized activation

authors:
Prajit Ramachandran
Barret Zoph
Quoc V Le

title: Searching for activation functions

venue: arXiv preprint arXiv:1710.05941,

authors:
Jonas Rauber
Wieland Brendel
Matthias Bethge

title: Foolbox: A python toolbox to benchmark the robustness of machine learning models

venue: arXiv preprint arXiv:1707.04131,

authors:
Sibo Song
Yueru Chen
Ngai-Man Cheung
C.C. Jay Kuo

title: Defense against adversarial attacks with saak transform, 2018

authors:
Jost Tobias Springenberg
Alexey Dosovitskiy
Thomas Brox
Martin Riedmiller

title: Striving for simplicity: The all convolutional net

venue: arXiv preprint arXiv:1412.6806,

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

title: Dropout: a simple way to prevent neural networks from overfitting. The journal of machine learning

authors:
Jiawei Su
Danilo Vasconcellos Vargas
Kouichi Sakurai

title: One pixel attack for fooling deep neural networks

venue: IEEE Transactions on Evolutionary Computation,

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:
Mingxing Tan
Quoc V Le

title: Efficientnet: Rethinking model scaling for convolutional neural networks

venue: arXiv preprint arXiv:1905.11946,

authors:
Bao Wang
Alex T. Lin
Zuoqiang Shi
Wei Zhu
Penghang Yin
Andrea L. Bertozzi
Stanley J. Osher

title: Adversarial defense via data dependent activation function and total variation minimization, 2018

authors:
Daniel Weingaertner
Victor K Tatai
Ricardo R Gudwin
Fernando J Von Zuben

title: Hierarchical evolution of heterogeneous neural networks

venue: In Proceedings of the 2002 Congress on Evolutionary Computation. CEC’02 (Cat. No. 02TH8600),

authors:
Valentina Zantedeschi
Maria-Irina Nicolae
Ambrish Rawat

title: Efficient defenses against adversarial attacks

venue: In Proceedings of the 10th ACM Workshop on Artificial Intelligence and Security,

authors:
Huan Zhang
Tsui-Wei Weng
Pin-Yu Chen
Cho-Jui Hsieh
Luca Daniel

title: Efficient neural network robustness certification with general activation

authors:
Qiyang Zhao
Lewis D Griffin

title: Suppressing the unusual: towards robust cnns using symmetric activation

heading: 1 INTRODUCTION

text:
Deep neural networks (DNNs) are a series of linear transformations followed by point-wise nonlinear functions. These non-linear functions are also referred to as activation functions. Activation functions directly influence the training dynamics and, therefore, affect the final performance of the DNN. For instance, activations such as Sigmoid and Tanh suffer from what is known as the “vanishing gradient” problem, when the inputs are in the saturation regions of these functions. This can adversely affect network performance and cause slow convergence. Rectified linear units (ReLU) (Nair & Hinton, 2010) have been shown to perform better than Sigmoid and Tanh in many scenarios. Instead of using a fixed activation function, one can learn a parameterized activation function to add expressive power to the model. Towards this goal, significant efforts have been made to introduce different learnable activation functions (Agostinelli et al., 2014; He et al., 2015; Ramachandran et al., 2017; Jin et al., 2016; Li et al., 2016). Although most of these adaptive activation functions outperform fixed activation functions in multiple tasks, there is very little insight into why.
In this paper, we propose the Symmetric Adaptive Piecewise Linear unit (Symmetric-APL; pronounced as Symmetric apple: "æp.@l) as a new adaptive activation function which builds upon the adaptive piecewise linear unit (APL) (Agostinelli et al., 2014). Similar to APL units, S-APL has multiple hinges which are connected by linear pieces. The S-APL activation is designed to give the same expressive power to both the positive and negative sides of the x-axis. We show that SAPL can approximate any continuous and zero-centered function, which encompasses many types of learned and fixed activations functions. Using this flexible learned activation function, we can then analyze how the shape changes during training and use ablation studies to investigate the role that these changes play in optimization. This helps us better understand learned activation functions and explain why they often provide increases in performance.
Finally, we evaluate the robustness of S-APL activated networks to adversarial attacks. Experiments are done using both black-box and open-box adversarial attacks where we observe S-APL equipped
networks are more robust to attacks than their ReLU counterparts. Experiments show that the robustness improves against differential evolution attacks (Su et al., 2019b) by (up to) 51% on Lenet , 47% on ResNet-18 (He et al., 2016), 43% on pure CNN, and 38% on Net in Net (Lin et al., 2013). For open-box adversarial attacks, the robustness also improves against FGSM and CW-L2 (Goodfellow et al., 2014) attack by (up to) 36%, 28%, and 25% for Lenet, pure CNN, and ResNet-18 architectures, respectively using CIFAR-10 dataset.

heading: 2 RELATED WORKS

text:
ReLU and its variants such as Leaky-ReLU (Maas et al., 2013), P-ReLU (He et al., 2015), exponential linear units (ELU) (Clevert et al., 2015), and scaled exponential linear units (SELU) (Klambauer et al., 2017) are believed to solve the vanishing gradient problem and some are shown to better normalize the network. By changing the negative side of x-axis, these variants push the mean activations of each unit closer to zero and accelerate learning.
Some of the pioneering attempts to learn activations in a neural network can be found in Poli (1996), Weingaertner et al. (2002), and Khan et al. (2013) where the authors proposed novel approaches to learning the best activation function per neuron among a pool of candidate activations by employing genetic and evolutionary algorithms. Maxout (Goodfellow et al., 2013) has been introduced as an activation function aimed at enhancing the model averaging properties of dropout (Srivastava et al., 2014). However, not only is it limited to approximating convex functions, but it also requires a significant increase in parameters. Neural architecture search (Ramachandran et al., 2017) uses a combination of exhaustive and reinforcement learning based search. Although the authors discovered multiple novel activation functions, of which f(x) = x ∗ sigmoid(βx) performed slightly better than ReLU, the search space of activation functions is limited. S-ReLU (Jin et al., 2016) was proposed as an adaptive activation function which can mimic both convex and non-convex functions.
It is worth mentioning that, in Lin et al. (2013), the authors proposed the network in network approach where they replace activation functions in convolutional layers with small multi-layer perceptrons. Theoretically, due to Universal Approximation Theorem, this is the most expressive activation; however, it requires many more parameters.

heading: 3 ADAPTIVE PIECEWISE ACTIVATION FUNCTION

heading: 3.1 ADAPTIVE PIECEWISE LINEAR UNITS

text:
Agostinelli et al. (2014) proposed an adaptive activation function which consists of multiple linear pieces. The formulation of this adaptive piecewise linear (APL) activation function is shown in Equation 1.
hi(x) = max(0, x) + S∑ s=1 asimax(0,−x+ bsi ) (1)
Where hi is the non-linear transformation for the hidden unit i and S is a hyperparameter that determines the number of hinges. ai is the slope of the linear piece and bi is the location of the hinge.
However, APL units are not zero-centered as they can have a non-zero output for a input of zero. This behavior provides no apparent beneficial purpose. Furthermore, APL units can only represent piecewise linear functions whose output hi(x) = x for x > u, for some scalar u. This significantly restricts the class of piecewise linear functions that APLs can express.
3.2 SYMMETRIC ADAPTIVE PIECEWISE LINEAR UNITS (APL: "æp.@l)
To overcome the shortcomings of APL activation function, we define a new adaptive piecewise linear activation function that is zero-centered and gives the same expressive power to the positive and negative half of the input space. Since S-APL shares the variables as+, b s +, a s −, and b s − among all
the neurons of a layer (e.i., hi(x, S) does not depend on i), it requires fewer parameters in compare to the plain APL. We formulate the activation hi of the hidden unit i as the summation of symmetric hinge-shaped pieces.
hi(x, S) = S∑ s=1 as+max(0, x− bs+) + S∑ s=1 as−max(0,−x− bs−) (2)
Similar to APL units, S is a hyperparameter which determines the number of hinges (on each side of the x-axis). as+ and a s − control the slope of linear pieces in both the positive and negative sides of the x-axis, while bs+, b s − ∈ [0,+∞) determine the location of hinge s. The total number of additional parameters is 4S for a single layer. Because our networks are trained with batch normalization (Ioffe & Szegedy, 2015) before each S-APL layer, the distribution of input to the S-APL function will follow that of a normal distribution. Therefore, we fix the hinges to be a pre-determined number of standard deviations away from the mean, decreasing the number of parameters to 2S.
Based on Equation 2, S-APL activation is zero-centered which leads to more stable statistical behavior during training. In case of using fixed hinges’ locations for APL, due to increasing the number of parameters, S-APL offers more flexibility than the normal APL. However, this increase is of O(constant) which is negligible. With the assumption of as+ = a s − and b s + = b s −, since hsi (x) = h s i (−x), S-APL allows neurons to activate symmetrically. As it is mentioned in Zhao & Griffin (2016), networks with symmetric activation functions are more robust to adversarial fooling. We will delve into this property in later sections.
S-APL can better handle the limits. It could be inferred from the definition that, in contrast to normal APL, increasing the absolute value of the input xwill also increase the number of terms affecting the hi(x). However, normal APL requires the rightmost linear section in all the component functions to have a unit slope and bias 0, which is not an appropriate constraint and undermines its representation ability.
The following theorem shows that S-APL can approximate any non-linear, zero-centered, and Lipschitz continuous function in a closed interval of real numbers. It is worth mentioning that APL was not flexible enough to do so.
Theorem 3.1 For any function f : [A,B]→ R and ∈ R, ∃S ∈ N, where |f(x)− S-APL(x)| ≤ , assuming:
• A and B are finite real numbers.
• f is M-Lipschitz continuous.
Proof: We start by dividing the interval [A,B] into S equal sub-intervals [Ai, Bi]. In other words, we put S equally distanced hinges in the interval [A,B]. So the length of each sub-interval will be B−AS . We start approximating f from the left most sub-interval which is [A,A + B−A S ]. The approximation of f in that sub-interval will be a line which connects f(A) to f(A+ B−AS ). Due to M-Lipschitz continuity of f , for any x ∈ [A,A+ B−AS ]:
|f(x)− S-APL(x)| ≤
{ |f(A)− f(A+ B−AS ) + M(B−A) S | f(A) ≤ f(A+ B−A S ),
|f(A+ B−AS )− f(A) + M(B−A) S | f(A) ≥ f(A+ B−A S ).
(3)
Again, due to M-Lipschitz continuity of f , we know that:
|f(A)− f(A+ B −A S )| ≤ M(B −A) S
(4)
Using Equation 4, we can re-write the inequality 3 as follows:
|f(x)− S-APL(x)| ≤ 2M(B −A) S
(5)
So, by choosing S ≥ 2M(B−A) , we satisfy that |f(x)− S-APL(x)| ≤ .
in order to complete the proof, we need to show that this approximation can be applied to other sub-intervals of [A,B] as well. We do so by induction as follows: Suppose that the approximation is done for sub-intervals [A1, B1], ..., [Ai, Bi], now we prove that for sub-interval [Ai+1, Bi+1] we can do the approximation which is connecting f(Ai+1) to f(Bi+1). The slope of S-APL in the subinterval [Ai, Bi] is ∑i 1 a i + or ∑i 1 a i − (depending on the sign of the sub-interval). However, the slope
of S-APL in the sub-interval [Ai+1, Bi+1] will be either ∑i+1 1 a i + or ∑i+1 1 a i −. In both cases, the extra term ai+1+ or a i+1 − is not fixed and can change the slop to any arbitrary value. This fact plus the assumption of continuity of S-APL guarantee that f(Ai+1) can be connected to f(Bi+1) which was our proposed approximation. As we showed the approximation for the left most sub-interval, the induction is complete.

heading: 4 COMPARISON TO COMMONLY USED ACTIVATION FUNCTIONS

text:
In order to show that S-APL unit is beneficial for deep neural networks, we compare it with wellknown activation functions in different architectures. We employed five different neural networks trained on three different datasets, MNIST, CIFAR-10, and CIFAR-100. We used S = 4 and set the hinges at positions x = −2.5,−2,−1, 0,+1,+2,+2.5 (0 considered as two hinges). Slope of as+1 is initialized to 1 and the remaining slopes are initiazlied to 0. With this initialization, the initialized S-APL mimics the shape of ReLU.
The results of the experiments are shown in Table 1. The table shows that S-APL leads to a better validation accuracy in almost all architectures.

heading: 5 HOW S-APL CHANGES DURING TRAINING AND POSSIBLE REASONS WHY

text:
Figures 1 and 2 show how the shape of S-APL changes for each layer during training. From these figures, we can see that during the early stages of training, the shape of S-APL looks similar to that of leaky ReLU: having a negative output for x < 0 and a positive output for x ≥ 0. During the later stages of training, the activation function has a positive output for both x < 0 and x ≥ 0. In addition, the slope of the output decreases as the magnitude of x increases.
We hypothesize that there are two distinct stages during the optimization of these learned activation functions. In the first stage, the function returns negative values for x < 0 and in the second stage,
the function returns positive values for x < 0. To investigate this hypothesis, we train S-APL under two different conditions where we: 1) force the output to only be negative for x < 0 (S-APLnegative) and 2) force the output to only be positive for x < 0 (S-APL-positive). We accomplish this by taking the absolute value of all as − and multiplying by +1 or −1.
Figure 2 shows that, although S-APL-positive has the ability to mimic the final learned shape of the S-APL function, it barely deviates from the ReLU initialization. This shows that the ability to give a negative output for negative inputs is crucial for S-APLs. Figure 2 shows that S-APL-negative does initially go negative in the 4th layer and then returns to the ReLU shape. To gain further insight, we compare the loss of these activation functions in Figure 3. We see that S-APL has a lower loss compared to S-APL-positive and S-APL-negative. Furthermore, S-APL-negative has a lower loss compared to S-APL-positive which has a lower loss than ReLU.
These results lead us to believe that it is possible that the first stage, S-APL-negative, adds gradient information by giving negative output for negative inputs. It is possible that S-APL-positive is not capable of doing so because giving positive outputs for negative inputs creates an identifiability issue. In other words, outputs for x < 0 and x ≥ 0 look the same. However, we can see that this property is useful for the S-APL function in the later stages of training. It is possible that this is because the DNN has adapted its parameters such that outputs on both the negative and positive sides capture a similar concept, adding expressive power to the model. Furthermore, one cannot achieve the final S-APL shape without the first stage of having negative outputs for negative inputs. To conclude, it appears that the S-APL units first go through two stages: 1) adding gradient information and 2) adding expressive power and that the second stage depends on the first stage. This information can be used to inform the design of learnable activation functions and even DNN optimization techniques.

heading: 6 ROBUSTNESS TO ADVERSARIAL ATTACKS

text:
DNNs have been shown to be vulnerable to many types of adversarial attacks (Szegedy et al., 2013; Goodfellow et al., 2014). Research suggests that activation functions are a major cause of this vulnerability (Zantedeschi et al., 2017). Zhang et al. (2018) bounds a given activation function with a few linear and quadratic functions and allows it to tackle general activation functions. This adds up with applying a different activation for each neuron so the resulting network shows efficiency and robustness to adversarial foolings. Wang et al. (2018) proposed a data-dependent activation function and empirically shows its robustness to both black-box and gradient-based adversarial attacks. Other
studies such as Rakin et al. (2018), Dhillon et al. (2018), and Song et al. (2018) focused on other additional properties of activation such as quantization and pruning and showed they can improve the robustness of DNNs against adversarial examples.
Recently, Zhao & Griffin (2016) theoretically showed that DNNs with symmetric activations are less likely to get fooled. The authors proved that “symmetric units suppress unusual signals of exceptional magnitude which result in robustness to adversarial fooling and higher expressibility.” Due to the symmetric convergence of S-APL units and also their hinges’ locations (b+i = b − i ) which result in h(x) = h(−x), S-APL units are capable of increasing the robustness of DNNs against adversarial attacks.
In this section, relying on the properties of S-APL such as data dependency, piecewise linearity, noninjective behavior, better handling of extreme values, and most importantly, symmetric shape, we show that adding S-APL to a DNNs greatly improves the robustness against adversarial attacks. This claim is verified through a wide range of experiments with the CIFAR-10 dataset under both blackbox and open-box methods, including one-pixel-attack and Fast Gradient Sign Method.
Figure 4 provides an intuition for the robustness of S-APL activated network in comparison to ReLU activated ones. For each of the two networks, we take 100 random samples of frog and ship images and visualize the pre-softmax representations using tSNE visualization (Maaten & Hinton, 2008) in
Figure 4. As it is depicted, for S-APL activated networks, the two classes are better separated. We suspect that red samples such as those that are lying on the outer circle in the left plot of Figure 4 might be somewhere on the manifold of the data where the network is more susceptible. As one can see, there is no red point on the outer circle of the right plot which might be showing the robustness of S-APL networks. For other samples on the inner circle and the cloud next to circles, we can see better separation by the S-APL network.

heading: 6.1 BLACK-BOX ADVERSARIAL ATTACK

text:
For black-box attacks against a DNN, we assume the adversary has no information about the structure or parameters of the DNN and does not have access to any large training dataset. The adversary’s only capability is to observe labels assigned by the DNN for chosen inputs in a manner analog to a cryptographic oracle. A successful attacking technique of this type is Su et al. (2019a) which is based on differential evolution. We can iteratively generate adversarial images to try to minimize the confidence (probability) of the network’s classification.
The process starts with random modifications of a few pixels to generate adversarial examples. At each step, one feeds several adversarial images to the DNN and only observes the output as the probability of different classes. Examples that lowered the confidence of the true class will be kept to generate the next generation of adversaries. The next generation modifications are then evolved through a certain mutation scheme to generate new adversarial images. By repeating these steps for a few iterations, the adversarial modifications generate more and more misleading images. The last step returns an adversarial modification that reduces the confidence of the true class the most. This means that the confidence of the true class would be reduced so much that a new incorrect category now has the highest classification confidence. This technique is called untargeted attack since we don’t specify the labels of the modified images.
In the following experiment, we modify one, three, and five pixels of images to generate adversarial examples. The mutation scheme we used for this experiment is as follows:
xl+1i = x l r1 + 0.5(x l r2 + x l r3) (6)
Where r1, r2, and r3 are three non-equal random indices of the modifications at level l. xl+1i will be an element of a new candidate modification.
To evaluate the effect of S-APL activation on the robustness of DNNs, we employ commonlyused architectures, namely, Lenet5, Network-in-Network (Lin et al., 2013), pure CNN (ours), and ResNet-18 (He et al., 2016). Each architecture is trained with ReLU, APL, and Swish activation functions and once with S-APL activation functions. The results in Table 2 show that Lenet5 and ResNet-18 architectures are 51% and 47.8% more resistant to back-box adversarial attacks. As authors in Zhao & Griffin (2016) theoretically proved, that one can be robust to adversarial examples with symmetric behavior.
After observing adversarial samples which are deceiving to both networks, we found that S-APL activated network still assigns high confidence to the true labels of the perturbed images. In other words, the difference between the confidence of the true label and the confidence of adversarially
wrong label is much smaller in S-APL network than networks that are activated with ReLU, APL, or Swish. More precisely, we measure the average of |Z(x′)true label − Z(x′)adversarial label| over all adversarial samples where each network is fooled. Z(.) is the post-softmax output and x′ is the adversarial sample. The avg(|Z(x′)true label − Z(x′)adversarial label|) for each model is also included in Table 2. Due to the reported averages, we can conclude that S-APL is much more robust against being adversarially deceived.

heading: 6.2 OPEN-BOX ADVERSARIAL ATTACK

text: To further explore the robustness of S-APL activated networks, in this section, we consider two of the popular benchmarks of open-box adversarial attacks: Fast Gradient Sign Method (FGSM) (Goodfellow et al., 2014) and CW attack (Carlini & Wagner, 2017). For both attacking strategy, we consider three different architectures and compare the rate of successful attacks for each of the networks with ReLU, APL, or Swich activations versus S-APL activation functions. The dataset and architectures are same as those were used for black-box adversarial attacks.

heading: 6.2.1 FGSM

text:
Fast Gradient Sign Method generates an adversarial image x′ from the original image x by maximizing the loss L(x′, y), where y is the true label of the image x. This maximization problem is subjected to ||x − x′||∞ ≤ where is considered as the attack strength. Approximating with the first term of Taylor expansion, we have:
L(x′, y) = L(x, y) +∇xL(x, y)T .(x− x′) (7) So the adversarial image x′ would be:
x′ = x+ .sign(∇xL(x, θ)) (8)
Where the is considered as the power of the attack. This form of FGSM is considered to be an untargeted attack where there is no pre-specified label t that x′ should be classified as. This method only yields an adversary x′ which will not be classified as y.
To see how S-APL increases the robustness against FGSM attack, we employ three architectures all trained to classify CIFAR-10 dataset. For different range of the results are summarized in Table 3.
In the best case, for Lenet architecture and = 0.02, S-APL activated network is 36% more robust than the ReLU activated one. The robustness also improves by 28% and 25% for pure CNN and ResNet-18 respectively. We can see the overall increase in the robustness over all networks and values. However, one can conclude that for smaller values of the robustness of S-APL activated network is higher in comparison to ReLU activated networks. As we increase the attack strength ( ), the robustness of S-APL networks gets closer to the robustness of ReLU activated networks.

heading: 6.2.2 CW-L2

text:
We showed that replacing ReLU with S-APL activation units can greatly improve the robustness of DNNs against FGSM attack. To further investigate the robustness that S-APL is adding to the network, we are using a more powerful open-box adversarial attack.
Another open-box adversarial attack which is generally more powerful than FGSM was introduced in Carlini & Wagner (2017). For a given pair of image x and label y, this technique is trying to find the minimum perturbation δ, so that the perturbed image x′ is classified as t 6= y. Considering L2 norm as the goal of minimization, this perturbation minimization problem can be formulated as
follows: ∀t 6= y,min||δ||22 subject to f(x+ δ) = t, x+ δ ∈ [0, 1]n (9)
Or equally, to ease the satisfaction of equality, Equation 9 can be rephrased asmin||δ||22+c.g(x+δ) where g(x) = max(maxt 6=y(logit(x)t− logit(x)y)), c is Lagrange multipliyer, and logit(x) is the pre-softmax vector for the input x.
Here, we examine the robustness of S-APL activated networks against CW-L2 attack. As it is shown in the table 4, CW-L2 attack is more powerful than FGSM. Although the S-APL activated network is less robust to CW-L2 attack than to FGSM attack, it is still showing more robustness in comparison to ReLU, APL, and Swish activated networks. Similar to black-box attack, the metric avg|Ztrue − Zadv| is calculated for successfully attacked images. The smaller values of avg|Ztrue − Zadv| for S-APL activated networks in both open-box attacks shows that S-APL activated networks are more resistant to being fooled.

heading: 7 CONCLUSION AND FUTURE WORKS

text: We extend the idea of piecewise linear activation functions by introducing S-APL as a learnable and potentially symmetric activation function. We investigate the properties of S-APL and their evolution during training to understand how these functions accelerate learning and increase expressive power in DNNs. Finally, we show that S-APL networks show more robustness to adversarial attacks than ReLU networks. One can potentially design a hybrid defense method that combines other defense techniques and S-APL units.

heading: 8 APPENDIX

heading: 8.1 NUMBER OF HINGES AND THE SYMMETRY OF S-APL

text:
In this section, we perform a variety of experiments to find the best setting for S-APL activation in terms of complexity and expressibility.
Before going to experiments, it is necessary to mention that we used batch normalization layer before every S-APL layer in our experiments. This means that the input of the S-APL activation is unit Gaussian. Relying on this fact and the experiments done in Agostinelli et al. (2014) we chose a fixed and symmetric set of hinges on±σ,±2σ,±2.5σ,±3σ, and ... . This will reduce the number of S-APL’s parameters by a factor of 2 which makes it much less computationally expensive.
First, we assess the effect of S on the performance of S-APL. Due to Theorem 3.1, greater S values increase the expressive power of the S-APL which results in better fitting the training data. We tried S ∈ [2, 3, 4, 5, 6], (which means 4, 6, 8, 10, and 12 hinges) with fixed hinges’ locations on MNIST (LeCun & Cortes, 2010), CIFAR-10 (Krizhevsky et al.) and binary classification of IMDB review dataset (Maas et al., 2011) to cover MLP, convolution, and recurrent architectures respectively. Each network is trained with two types of S-APL activation; 1) A shared S-APL: a shared unit among all neurons of a layer and 2) An independent S-APL unit for each neuron of a layer. As it is summarized in Table 5, in all cases for S ≥ 4 the performance is not decreasing significantly.
On the other hand, due to the increase in the number of parameters of S-APL, the unit becomes more computationally expensive. In Table 6 we compare the per-epoch training run-time for different number of hinges of a shared S-APL.
For small values of S, we can see that S-APL is comparable to an exponential activation unit such as Tanh, and much faster than heavier activation such as Maxout.
As one can conclude from both Table 5 and 6, there is a trade-off between the complexity and expressibility. We believe that S = 4, or equally 8 hinges, is the best choice for the number of hinges where the hinges’ locations are symmetrically fixed.

heading: 8.2 EXPERIMENTS’ DETAILS AND STATISTICAL SIGNIFICANCE

text:
In this section, we explain the experimental conditions and all the parameters used for each experiment. Also, in order to make the results of Table 1 more interpretable, we perform a t-test (Kim, 2015) on all the error rates achieved in that experiment.
In section 4, the experiment corresponding to Table 1 are performed using six different architectures. Lenet 5 is used as it was introduced in LeCun et al. (1998). It has two convolution layers followed by two MLPs that are connected to a softmax layer.
The MLP architecture which is only used for classifying MNIST dataset has three fully connected feed-forward layers with 258, 128, and 10 hidden units. A dropout of rate 0.3 is added in between each layer. We use the batch size of 32 and we train the MLP network for 50 epochs.
Pure CNN architecture which is only taking advantage of convolutional layers, was introduced in Springenberg et al. (2014). All the specifications, including kernel size, stride, learning rate, batch size, and the number of epochs are taken from the main article.
ResNet18 architecture as a variant of residual networks (He et al., 2016) is taken from Napoletano et al. (2018) which has five residual convolution blocks, one MLP, and a softmax layer. The size of the convolution kernels, strides, padding, pooling size, pooling operation, learning rate, batch size, and epochs are taken as the defaults mentioned in Napoletano et al. (2018).
EffectiveNets was introduced in Tan & Le (2019) and is used in our experiments exactly the way in was originally introduced. It is necessary to mention that we useB0 variant of EffectiveNets.
Lastly, Net in Net architecture which is using an MLP instead of a fixed nonlinear transformation is taken from Agostinelli et al. (2014).
It is worth mentioning that in section 4, all the experiments were performed five times. To reduced the effect of noise and randomness, the average of the five times is reported. In Tabel 7, we show the statistical significance of the experiments performed in section 4. Since each number is the average of five experiments, we are able to perform a t-test and provide p-values and statistical significance for each individual experiment. As one can see in Table 7, most of the numbers of Table 1 are statistically significant.
In section 5, we use two architectures to visualize S-APL shapes at different stages of the training process. For Figure 1 and Figure 2 we use the same MLP and Lenet 5 architectures as described above.
In section 6, we start by a tSNE visualization of 100 random samples of frogs and ships from the cifar10 test set. The tSNE mapping is performed using a learning rate of 30 and a perplexity of 40.
For the black-box adversarial attack experiments, each network is attacked five times and the reported number is the average of successful modifications in five different attacks. Attacks are done using the maximum number of iteration to be 40 and the pop size to be 400.
As for the open-box attacks, for both FGSM and CW-L2 attack, we employ the implementation and default hyper-parameters in Rauber et al. (2017).
Lastly, for activation function of networks in section 6, ReLU (y = x for x > 0, 0 otherwise ), APL (S = 5, with fixed hinges on 0,±1, and ± 2), Swish (y = x.sigmoid(βx) with β = 0.2), and S-APL (with the configurations mentioned in the previous section) are used.