summaries: The authors propose to construct reinforcement learning policies with very few parameters. For this purpose, they force a feed-forward neural network to share most of its weights, reducing the total number of different weights to at most 23 and therefore compress the network. Instead of manually encoding which weights are shared, the authors propose to use a reinforcement learning method to learn this mapping. The values of all parameters are learned with a gradient-based method.

summaries: This paper focuses on neural architecture search for constructing compact RL policies. It combines ideas from the popular ENAS and ES methods for optimisation. Recent work defined a family of compact policies by imposing a fixed Toeplitz structure. This paper introduces the so-called “chromatic network” architecture, which partitions weights of the RL network into tied sub-groups. The partitioning is searched with ENAS and shared weights are updated via ES. Experiments on continuous control benchmarks show that good performance can be obtained using a very small number of parameters. Favourable reward-compression outcomes can be achieved compared to some baseline alternatives.

summaries: This paper compresses policy networks using approaches inspired by neural architecture search. The main idea is to have a fixed size weight matrix, but learn how to share weights, so that the resulting network can be compressed by storing only unique weights values. Both the partitioning and weights are trained simultaneously, inspired by ENAS. The partitioning is modeled by an autoregressive RNN and trained via REINFORCE. The weights are modeled by a single set of weights (as opposed to a distribution) which is then updated by using a gradient approximation based on ES. The experiments carried out include comparing to existing works on policy network compression, ablating against random partitioning, as well as a few experiments meant to increase understanding of the learned partitions.

abstractText: We present a neural architecture search algorithm to construct compact reinforcement learning (RL) policies, by combining ENAS (Vinyals et al., 2015; Pham et al., 2018; Zoph & Le, 2017) and ES (Salimans et al., 2017) in a highly scalable and intuitive way. By defining the combinatorial search space of NAS to be the set of different edge-partitionings (colorings) into same-weight classes, we represent compact architectures via efficient learned edge-partitionings. For several RL tasks, we manage to learn colorings translating to effective policies parameterized by as few as 17 weight parameters, providing > 90% compression over vanilla policies and 6x compression over state-of-the-art compact policies based on Toeplitz matrices (Choromanski et al., 2018), while still maintaining good reward. We believe that our work is one of the first attempts to propose a rigorous approach to training structured neural network architectures for RL problems that are of interest especially in mobile robotics (Gage, 2002) with limited storage and computational resources.

title: A back-propagation algorithm with optimal use of hidden units

venue: Advances in Neural Information Processing Systems

authors:
Wenlin Chen
James Wilson
Stephen Tyree
Kilian Weinberger
Yixin Chen

title: Compressing neural networks with the hashing trick

venue: In International Conference on Machine Learning,

authors:
Krzysztof Choromanski
Mark Rowland
Vikas Sindhwani
Richard E. Turner
Adrian Weller

title: Structured evolution with compact architectures for scalable policy optimization

venue: In Proceedings of the 35th International Conference on Machine Learning,

authors:
Giuseppe Cuccu
Julian Togelius
Philippe Cudré-Mauroux

title: Playing atari with six neurons

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

authors:
Yann Le Cun
John S. Denker
Sara A. Solla

title: Optimal brain damage

authors:
Thomas Elsken
Jan Hendrik Metzen
Frank Hutter

title: Neural architecture search: A survey

venue: Journal of Machine Learning Research,

authors:
Jonathan Frankle
Michael Carbin

title: The lottery ticket hypothesis: Finding sparse, trainable neural networks

title: Mobile Robots XVII, Philadelphia, PA

venue: USA, October

authors:
Aidan N. Gomez
Ivan Zhang
Kevin Swersky
Yarin Gal
Geoffrey E. Hinton

title: Learning sparse networks using targeted

venue: dropout. ArXiv,

authors:
Song Han
Jeff Pool
John Tran
William Dally

title: Learning both weights and connections for efficient neural network

authors:
Song Han
Huizi Mao
William J. Dally

title: Deep compression: Compressing deep neural network with pruning, trained quantization and Huffman coding

venue: In International Conference on Learning Representations,

authors:
Atil Iscen
Ken Caluwaerts
Jie Tan
Tingnan Zhang
Erwin Coumans
Vikas Sindhwani
Vincent Vanhoucke

title: Policies modulating trajectory generators

venue: In 2nd Annual Conference on Robot Learning, CoRL 2018, Zürich, Switzerland,

authors:
Karel Lenc
Erich Elsen
Tom Schaul
Karen Simonyan

title: Non-differentiable supervised learning with evolution strategies and hybrid methods

authors:
Edo Liberty
Steven W Zucker

title: The mailman algorithm: A note on matrix–vector multiplication

venue: Information Processing Letters,

authors:
Christos Louizos
Max Welling
Diederik P. Kingma

title: Learning sparse neural networks through l0 regularization

authors:
Horia Mania
Aurelia Guy
Benjamin Recht

title: Simple random search provides a competitive approach to reinforcement learning

title: Simple random search of static linear policies is competitive for reinforcement learning

venue: In Advances in Neural Information Processing Systems,

title: Comparing clusterings by the variation of information

venue: Learning Theory and Kernel Machines,

authors:
Michael C. Mozer
Paul Smolensky

title: Skeletonization: A technique for trimming the fat from a network via relevance assessment

authors:
Sharan Narang
Gregory Diamos
Shubho Sengupta
Erich Elsen

title: Exploring sparsity in recurrent neural networks

authors:
Hieu Pham
Melody Y. Guan
Barret Zoph
Quoc V. Le
Jeff Dean

title: Efficient neural architecture search via parameter sharing

title: Objective criteria for the evaluation of clustering methods

venue: Journal of the American Statistical Association,

authors:
Tim Salimans
Jonathan Ho
Xi Chen
Szymon Sidor
Ilya Sutskever

title: Evolution strategies as a scalable alternative to reinforcement

venue: learning. arXiv,

authors:
Abigail See
Minh-Thang Luong
Christopher D. Manning

title: Compression of neural machine translation models via pruning

venue: In Proceedings of The 20th SIGNLL Conference on Computational Natural Language Learning, Berlin,

authors:
Vikas Sindhwani
Tara N. Sainath
Sanjiv Kumar

title: Structured transforms for small-footprint deep learning

venue: In Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems

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

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

authors:
Kenneth O. Stanley
Risto Miikkulainen

title: Evolving neural network through augmenting topologies

venue: Evolutionary Computation,

authors:
Oriol Vinyals
Meire Fortunato
Navdeep Jaitly

title: Pointer networks. In Advances in Neural Information Processing Systems

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

venue: Machine Learning,

authors:
Saining Xie
Alexander Kirillov
Ross B. Girshick
Kaiming He

title: Exploring randomly wired neural networks for image recognition

authors:
Haonan Yu
Sergey Edunov
Yuandong Tian
Ari Morcos

title: Playing the lottery with rewards and multiple languages: lottery tickets in rl and nlp

authors:
Barret Zoph
Quoc V. Le

title: Neural architecture search with reinforcement learning

venue: In 5th International Conference on Learning Representations,

heading: 1 INTRODUCTION

text:
Consider a fixed Markov Decision Process (MDP) M and an agent aiming to maximize its total expected/discounted reward obtained in the environment E governed byM. An agent is looking for a sequence of actions a0, ..., aT−1 leading to a series of steps maximizing this reward. One of the approaches is to construct a policy πθ : S → A, parameterized by vector θ, which is a mapping from states to actions. Policy πθ determines actions chosen in states visited by an agent. Such a reinforcement learning (RL) policy is usually encoded as a neural network, in which scenario parameters θ correspond to weights and biases of a neural network. Reinforcement learning policies πθ often consist of thousands or millions of parameters (e.g. when they involve vision as part of the state vector) and therefore training them becomes a challenging high-dimensional optimization problem. Deploying such high-dimensional policies on hardware raises additional concerns in resource constrained settings (e.g. limited storage), emerging in particular in mobile robotics (Gage, 2002). The main question we tackle in this paper is the following:
Are high dimensional architectures necessary for encoding efficient policies and if not, how compact can they be in in practice?
We show that finding such compact representations is a nontrivial optimization problem despite recent observations that some hardcoded structured families (Choromanski et al., 2018) provide certain levels of compactification and good accuracy at the same time.
We model the problem of finding compact presentations by using a joint objective between the combinatorial nature of the network’s parameter sharing profile and the reward maximization of RL optimization. We leverage recent advances in the ENAS (Efficient Neural Architecture Search) literature and theory of pointer networks (Vinyals et al., 2015; Pham et al., 2018; Zoph & Le, 2017) to optimize over the combinatorial component of this objective and state of the art evolution strategies (ES) methods (Choromanski et al., 2018; Salimans et al., 2017; Mania et al., 2018a) to optimize over the RL objective. We propose to define the combinatorial search space to be the the set of different edge-partitioning (colorings) into same-weight classes and construct policies with learned weight-sharing mechanisms. We call networks encoding our policies: chromatic networks.
We are inspired by two recent papers: (Choromanski et al., 2018) and (Gaier & Ha, 2019). In the former one, policies based on Toeplitz matrices were shown to match their unstructured counterparts accuracy-wise, while leading to the substantial reduction of the number of parameters from
thousands (Salimans et al., 2017) to hundreds (Choromanski et al., 2018). Instead of quadratic (in sizes of hidden layers), those policies use only linear number of parameters. The Toeplitz structure can be thought of as a parameter sharing mechanism, where edge weights along each diagonal of the matrix are the same (see: Fig. 1). However, this is a rigid pattern that is not learned. We show in this paper that weight sharing patterns can be effectively learned, which further reduces the number of distinct parameters. For instance, using architectures of the same sizes as those in (Choromanski et al., 2018), we can train effective policies for OpenAI Gym tasks with as few as 17 distinct weights. The latter paper proposes an extremal approach, where weights are chosen randomly instead of being learned, but the topologies of connections are trained and thus are ultimately strongly biased towards RL tasks under consideration. It was shown in (Gaier & Ha, 2019) that such weight agnostic neural networks (WANNs) can encode effective policies for several nontrivial RL problems. WANNs replace conceptually simple feedforward networks with general graph topologies using NEAT algorithm (Stanley & Miikkulainen, 2002) providing topological operators to build the network.
Our approach is a middle ground, where the topology is still a feedforward neural network, but the weights are partitioned into groups that are being learned in a combinatorial fashion using reinforcement learning. While (Chen et al., 2015) shares weights randomly via hashing, we learn a good partitioning mechanisms for weight sharing.
Our key observation is that ENAS and ES can naturally be combined in a highly scalable but conceptually simple way. To give context, vanilla NAS (Zoph & Le, 2017) for classical supervised learning setting (SL) requires a large population of 450 GPU-workers (child models) all training one-by-one, which results in many GPU-hours of training. ENAS (Pham et al., 2018) uses weight sharing across multiple workers to reduce the time, although it can reduce computational resources at the cost of the variance of the controller’s gradient. Our method solves both issues (fast training time and low controller gradient variance) by leveraging a large population of much-cheaper CPU workers (300) increasing the effective batch-size of the controller, while also training the workers simultaneously via ES. This setup is not possible in SL, as single CPUs cannot train large image-based classifiers in practice. Furthermore, this magnitude of scaling by numerous workers can be difficult with policy gradient or Q-learning methods as they can be limited by GPU overhead due to exact-gradient computation.
We believe that our work is one of the first attempts to propose a flexible, rigorous approach to training compact neural network architectures for RL problems. Those may be of particular importance in mobile robotics (Gage, 2002) where computational and storage resources are very limited. We also believe that this paper opens several new research directions regarding structured policies for robotics.

heading: 1.1 BACKGROUND AND RELATED WORK

text:
Network Architecture Search: The subject of this paper can be put in the larger context of Neural Architecture Search (NAS) algorithms which recently became a prolific area of research with already voluminous literature (see: (Elsken et al., 2019) for an excellent survey). Interest in NAS algorithms started to grow rapidly when it was shown that they can design state-of-the-art architectures for image recognition and language modeling (Zoph & Le, 2017). More recently it was shown that NAS
network generators can be improved to sample more complicated connectivity patterns based on random graph theory models such as Erdos-Renyi, Barabasi-Albert or Watts-Strogatz to outperform human-designed networks, e.g. ResNet and ShuffleNet on image recognition tasks (Xie et al., 2019). However to the best of our knowledge, applying NAS to construct compact RL policy architectures has not been explored before. On a broader scope, there has been little work in applying NAS to general RL policies, partially because unlike SL, RL policies are quite small and thus do not require a search space involving hyperparameter primitives such as number of hidden layers, convolution sizes, etc. However, we show that the search space for RL policies can still be quite combinatorial, by examining partitionings of weights in our work.
Parameterizing Compact Architectures: Before NAS can be applied, a particular parameterization of a compact architecture defining combinatorial search space needs to be chosen. That leads to the vast literature on compact encodings of NN architectures. Some of the most popular and efficient techniques regard network sparsification. The sparsity can be often achieved by pruning already trained networks. These methods have been around since the 1980s, dating back to Rumelhart (Rumelhart, 1987; Chauvin, 1989; Mozer & Smolensky, 1989), followed shortly by Optimal Brain Damage (Cun et al., 1990), which used second order gradient information to remove connections. Since then, a variety of schemes have been proposed, with regularization (Louizos et al., 2018) and magnitude-based weight pruning methods (Han et al., 2015; See et al., 2016; Narang et al., 2017) increasingly popular. The impact of dropout (Srivastava et al., 2014) has added an additional perspective, with new works focusing on attempts to learn sparse networks (Gomez et al., 2019). Another recent work introduced the Lottery Ticket Hypothesis (Frankle & Carbin, 2019), which captivated the community by showing that there exist equivalently sparse networks which can be trained from scratch to achieve competitive results. Interestingly, these works consistently report similar levels of compression, often managing to match the performance of original networks with up to 90% fewer parameters. Those methods are however designed for constructing classification networks rather than those encoding RL policies.
Quantization: Weight sharing mechanism can be viewed from the quantization point of view, where pre-trained weights are quantized, thus effectively partitioned. Examples include (Han et al., 2016), who achieve 49x compression for networks applied for vision using both pruning and weight sharing (by quantization) followed by Huffman coding. However such partitions are not learned which is a main topic of this paper. Even more importantly, in RL applications, where policies are often very sensitive to parameters’ weights (Iscen et al., 2018), centroid-based quantization is too crude to preserve accuracy.
Compact RL Policies In recent times there has been increased interest in simplifying RL policies. In particular, (Mania et al., 2018b) demonstrated that linear policies are often sufficient for the benchmark MuJoCo locomotion tasks, while (Cuccu et al., 2019) found smaller policies could work for vision-based tasks by separating feature extraction and control. Finally, recent work found that small, sparse sub-networks can perform better than larger over-parameterized ones (Frankle & Carbin, 2019), inspiring applications in RL (Yu et al., 2019).
Our main contributions are:
1. We propose a highly scalable algorithm by combining ENAS and ES for learning compact representations that learns effective policies with over 92% reduction of the number of neural network parameters (Section 3). 2. To demonstrate the impact (and limitations) of pruning neural networks for RL, we adapt recent algorithms training both masks defining combinatorial structure as well as weights of a deep neural network concurrently (see: (Lenc et al., 2019)). Those achieve state-ofthe-art results on various supervised feedforward and recurrent models. We confirm these findings in the RL setting by showing that good rewards can be obtained up to a high level of pruning. However, at the 80-90% level we see a significant decrease in performance which does not occur for the proposed by us chromatic networks (Section 4.1, Section 4.2). 3. We demonstrate that finding efficient weight-partitioning mechanisms is a challenging problem and NAS helps to construct distributions producing good partitionings for more difficult RL environments (Section 4.3).

heading: 2 THE ARCHITECTURE OF NEURAL ARCHITECTURE SEARCH

text:
The foundation of our algorithm for learning structured compact policies is the class of ENAS methods (Pham et al., 2018). To present our algorithm, we thus need to first describe this class. ENAS algorithms are designed to construct neural network architectures thus they aim to solve combinatorial-flavored optimization problems with exponential-size domains. The problems are cast as MDPs, where a controller encoded by the LSTM-based policy πcont(θ), typically parameterized by few hundred hidden units, is trained to propose good-quality architectures, or to be more precise: good-quality distributions D(θ) over architectures. In standard applications the score of the particular distribution D(θ) is quantified by the average performance obtained by trained models leveraging architectures A ∼ D(θ) on the fixed-size validation set. That score determines the reward the controller obtains by proposing D(θ). LSTM-based controller constructs architectures using softmax classifiers via autoregressive strategy, where controller’s decision in step t is given to it as an input embedding at time t + 1. The initial embedding that the controller starts with is an empty one.
Weight Sharing Mechanism: ENAS introduces a powerful idea of a weight-sharing mechanism. The core concept is that different architectures can be embedded into combinatorial space, where they correspond to different subgraphs of the given acyclic directed base graph G (DAG). Weights of the edges of G represent the shared-poolWshared from which different architectures will inherit differently by activating weights of the corresponding induced directed subgraph. At first glance such a mechanism might be conceptually problematic since, a weight of the particular edge e belonging to different architectures Ai1 , ...Aik (see: next paragraph for details regarding weight training) will be updated based on evaluations of all of them and different Ais can utilize e in different ways. However it turns out that this is desirable in practice. As authors of (Pham et al., 2018) explain, the approach is motivated by recent work on transfer and multitask learning that provides theoretical grounds for transferring weights across models. Another way to justify the mechanism is to observe that ENAS tries in fact to optimize a distribution over architectures rather than a particular architecture and the corresponding shared-pool of weightsWshared should be thought of as corresponding to that distribution rather than its particular realizations. Therefore the weights of that pool should be updated based on signals from all different realizations.
Alternating Optimization: For a fixed parameterization θ defining policy π(θ) of the controller (and thus also proposed distribution over architecturesD(θ)), the algorithm optimizes the weights of the models usingM architectures: A1, ...,AM sampled fromD(θ), where the sampling is conducted by the controller’s policy πcont(θ). Models corresponding to A1, ...,AM are called child models. At iteration k of the weight optimization process, a worker assigned to the architectureAi computes the gradient of the loss function LAi,Bk corresponding to the particular batch Bk of the training data with respect to the weights of the inherited edges from the base DAG. Since the loss function LBk onWshared for a fixed distribution D(θ) and batch Bk at iteration k is defined as an expected loss EA∼π(θ)[LA,Bk(WAshared)], where WAshared stands for the projection of the set of shared-pool weights Wshared into edges defined by the induced subgraph determined by A, its gradient with respect toWshared can be estimated via Monte Carlo procedure as:
∇WsharedLBk(Wshared) ∼ 1
M M∑ i=1 ∇WAisharedLAi,Bk(W Ai shared) (1)
After weight optimization is completed, ENAS updates the parameters θ of the controller responsible for shaping the distribution used to sample architectures A. As mentioned before, this is done using reinforcement learning approach, where parameters θ are optimized to maximize the expected reward EA∼π(θ)[RWAshared(A)], where this time setWshared is frozen and RWAshared(A) is given as the accuracy obtained by the model using architectureA and weights fromWAshared on the validation set. Parameters θ are updated with the use of the REINFORCE algorithm (Williams, 1992).
Controller’s Architecture: The controller LSTM-based architecture uses pointer networks (Vinyals et al., 2015) that utilize LSTM-encoder/decoder approach, where the decoder can look back and forth over input. Thus these models are examples of architectures enriched with attention.

heading: 3 TOWARDS CHROMATIC NETWORKS - ENAS FOR GRAPH PARTITIONINGS

text:
Preliminaries: Chromatic networks are feedforward NN architectures, where weights are shared across multiple edges and sharing mechanism is learned via a modified ENAS algorithm that we present below. Edges sharing a particular weight form the so-called chromatic class. An example of the learned partitioning is presented on Fig. 2. Learned weight-sharing mechanisms are more complicated than hardcoded ones from Fig. 1, but lead to smaller-size partitionings. For instance, Toeplitz sharing mechanism for architecture from Subfigure (b) of Fig. 2 requires 103 weightparameters, while ours: only 17.
Controller Architecture & Training: We use a standard ENAS reinforcement learning controller similar to (Pham et al., 2018), applying pointer networks. Our search space is the set of all possible mappings Φ : E → {0, 1, ...,M − 1}, where E stands for the set of all edges of the graph encoding an architecture and M is the number of partitions, which the user sets. Thus as opposed to standard ENAS approach, where the search space consists of different subgraphs, we instead deal with different colorings/partitionings of edges of a given base graph. The controller learns distributions D(θ) over these partitionings. The shared pool of weightsWshared is a latent vector in RM , where different entries correspond to weight values for different partitions enumerated from 0 to M − 1. As for standard ENAS, the controller π(θ) consists of a encoder RNN and decoder RNN, in which the encoder RNN is looped over the embedded input data, while the decoder is looped to repeatedly output smaller primitive components of the final output.
In our setting, we do not possess natural numerical data corresponding to an embedding of the inputs which are partition numbers and edges. Therefore we also train an embedding (as part of controller’s parameter vector θ) of both using tables: Vedge : e→ Rd and Vpartition : {0, 1, ...,M − 1} → Rd.
We denote by P a partitioning of edges and define the reward obtained by a controller for a fixed distribution D(θ) produced by its policy π(θ) as follows:
R(θ) = EP∼π(θ)[RmaxWshared(P )], (2)
where RmaxWshared(P ) stands for the maximal reward obtained during weight-optimization phase of the policy with partitioning P and with initial vector of distinct weightsWshared. As for the ENAS setup, in practice this reward is estimated by averaging over M workers evaluating independently different realizations P of D(θ). The updates of θ are conducted with the use of REINFORCE.

heading: 3.1 WEIGHT UPDATES VIA ES

text:
As opposed to standard ENAS, where weights for a fixed distribution D(θ) generating architectures were trained by backpropagation, we propose to apply recently introduced ES blackbox optimization techniques for RL (Choromanski et al., 2018). For a fixed partitioning P , we define the loss LP (Wshared) with respect to weights as the negated reward obtained by an agent applying partitioning P and with vector of distinct weights Wshared. That expression as a function of Wshared
is not necessarily differentiable, since it involves calls to the simulator. This also implies that explicit backpropagation is not possible. We propose to instead estimate the gradient of its Gaussian smoothing LσP (Wshared) defined as: LσP (Wshared) = Eg∈N (0,IM )[LP (Wshared + σg)] for a fixed smoothing parameter σ >. We approximate its gradient given by: ∇WsharedLσP (Wshared) = 1 σEg∈N (0,IM )[LP (Wshared + σg)g] with the following forward finite difference unbiased estimator introduced in (Choromanski et al., 2018):
∇̂WsharedLσP (Wshared) = 1
t t∑ i=1 gt [LP (Wshared + σgt)− EP∼π(θ) [LP (Wshared)] σ ] (3)
where g1, ...,gt are sampled independently at random fromN (0, IM ) and the pivot point is defined as an average loss for a given set of weightsWshared over partitionings sampled from π(θ). We note that a subtle key difference here from vanilla ES is by using the pivot point EP∼π(θ) [LP (Wshared)] as the expectation over a distribution of partitions P ∼ π(θ) rather than a static single-query objective L(W) used for e.g. a basic Mujoco task. From a broader perspective, this comes from the fact that ES can optimize any objective of the form EP∼P [f(W,P )] where P is any (possibly discrete) object with distribution P and W is a continuous weight vector, by assigning both a perturbed weight W + σg and a sampled P to a CPU worker for function evaluation on f(W + σg, P ).

heading: 4 EXPERIMENTAL RESULTS

text:
The experimental section is organized as follows:
• In Subsection 4.1 we show the limitations of the sparse network approach for compactifying RL policies on the example of state-of-the-art class of algorithms from (Lenc et al., 2019) that aim to simultaneously train weights and connections of neural network architectures. This approach is conceptually the most similar to ours. • In Subsection 4.2 we present exhaustive results on training our chromatic networks with ENAS on OpenAI Gym and quadruped locomotion tasks. We compare sizes and rewards obtained by our policies with those using masking procedure from (Lenc et al., 2019), applying low displacement rank matrices for compactification as well as unstructured baselines. • In Subsection 4.3 we analyze in detail the impact of ENAS steps responsible for learning partitions, in particular compare it with the performance of random partitionings.
We provide more experimental results in the Appendix.

heading: 4.1 LEARNED SPARSE NETWORKS VIA SIMULTANEOUS WEIGHT-TOPOLOGY TRAINING

text: The mask m, drawn from a multinomial distribution, is trained in (Lenc et al., 2019) using ES and element-wise multiplied by the weights before a forward pass. In (Lenc et al., 2019), the sparsity of the mask is fixed, however, to show the effect of pruning, we instead initialize the sparsity at 50% and increasingly reward smaller networks (measured by the size of the mask |m|) during optimization. Using this approach on several Open AI Gym tasks, we demonstrate that masking mechanism is capable of producing compact effective policies up to a high level of pruning. At the same time, we show significant decrease of performance at the 80-90% compression level, quantifying accurately its limits for RL tasks (see: Fig. 3).

heading: 4.2 RESULTS ON CHROMATIC NETWORKS

text:
We perform experiments on the following OpenAI Gym tasks: Swimmer, Reacher, Hopper, HalfCheetah, Walker2d, Pusher, Striker, Thrower and Ant as well as quadruped locomotion task of forward walking from (Iscen et al., 2018). The performance of our algorithm constructing chromatic networks is summarized in Table 1. We tested three classes of feedforward architectures: linear from (Mania et al., 2018a), and nonlinear with one or two hidden layers and tanh nonlinearities.
We see a general trend that increasing hidden layers while keeping number of partitions fixed, improves performance as well as increasing the number of partitions while keeping the architecture fixed. The relation between the expressiveness of a linear, high-partition policy vs a hidden-layer, low-partition policy is however not well understood. As shown in Table 1, this depends on the environment’s complexity as well. For HalfCheetah, the linear 50-partition policy performs better than a hidden layer 17-partition policy, while this is reversed for for the Minitaur.
In Table 2 we directly compare chromatic networks with a masking approach as discussed in Section 4.1, as well as other structured policies (Toeplitz from (Choromanski et al., 2018) and circulant) and the unstructured baseline. In all cases we use the same hyper-parameters, and train until convergence for five random seeds. For masking, we report the best achieved reward with > 90% of the network pruned, making the final policy comparable in size to the chromatic network. For each class of policies, we compare the number of weight parameters used (“# of weight-params” field), since the compactification mechanism does not operate on bias vectors. We also record compression in respect to unstructured networks in terms of the total number of parameters (“# compression” field). This number determines the reduction of sampling complexity with respect to unstructured networks (which is a bottleneck of ES training), since the number of RL blackbox function F queries needed to train/up-train the policy is proportional to the total number of weights and biases of the corresponding network.
Finally, for a working policy we report total number of bits required to encode it assuming that real values are stored in the float format. Note that for chromatic and masking networks this includes bits required to encode a dictionary representing the partitioning. Further details are given in the Appendix (Section E). Top two performing networks for each environment are in bold. Chromatic networks are the only to provide big compression and quality at the same time across all tasks.
Inference Time: Similarly to Toeplitz, chromatic networks also provide computational gains. Using improved version of the mailman-algorithm (Liberty & Zucker, 2009), matrix-vector multiplication part of the inference can be run on the chromatic network using constant number of distinct weights and deployed on real hardware in time O( mnlog(max(m,n)) ), where (m,n) is the shape of the matrix.

heading: 4.3 FURTHER ANALYSIS: RANDOM PARTITIONINGS VERSUS ENAS

text:
A natural question to ask is whether ENAS machinery is required or maybe random partitioning is good enough to produce efficient policies. To answer it, we trained joint weights for fixed population of random partitionings without NAS, as well as with random NAS controller.
Our experiments show that these approaches fail by producing suboptimal policies for harder tasks (see: Fig. 4). Note also that if a partitioning distribution is fixed throughout the entire optimization, training policies for such tasks and restarting to fix another partitioning or distribution can cause substantial waste of computational resources, especially for the environments requiring long training time. However we also notice an intriguing fact that random partitionings still lead to nontrivial rewards. We find it similar to the conclusions in NAS for supervised learning (Pham et al., 2018) - while training a random child model sampled from a reasonable search space may produce ≥
80 % accuracy, the most gains from a controller will ultimately be at the tail end; i.e. at the 95% accuracies.
We observe that by training with ENAS, the entire optimization benefits in two ways by: (1) selecting partitionings leading to good rewards, (2) resampling good partitionings based on the controller replay buffer, and breaking through local minima inherently caused by the weight-sharing mechanism maximizing average reward. We see these benefits precisely when a new ENAS iteration abruptly increases the reward by a large amount, which we present on Fig. 5.

heading: 5 CONCLUSION & FUTURE WORK

text:
We presented a principled and flexible algorithm for learning structured neural network architectures for RL policies and encoded by compact sets of parameters. Our architectures, called chromatic networks, rely on partitionings of a small sets of weights learned via ENAS methods. Furthermore, we have also provided a scalable way of performing NAS techniques with RL policies which is not limited to weight-sharing, but can potentially also be used to construct several other combinatorial structures in a flexible fashion, such as node deletions and edge removals.
We showed that chromatic networks provide more aggressive compression than their state-of-the-art counterparts while preserving efficiency of the learned policies. We believe that our work opens new research directions, especially from using other combinatorial objects. Detailed analysis of obtained partitionings (see: Appendix C) also shows that learned structured matrices are very different from previously used state-of-the-art (in particular they are characterized by high displacement rank), yet it is not known what their properties are. It would be also important to understand how transferable those learned partitionings are across different RL tasks (see: Appendix D).

heading: APPENDIX

heading: A FULL PLOTS

heading: A.1 TRAINING CURVES

text: We plot black vertical bars in order to denote a NAS update iteration. Different curves correspond to different workers.

heading: A.2 MAXIMUM REWARD CURVES

text: In order to view the maximum rewards achieved during the training process, for each worker at every NAS iteration, we record the maximum reward within the interval [NAS iteration · T, (NAS iteration +1) · T ), where T stadns for the current number of conducted timestpes.

heading: B EXACT SETUP AND HYPERPARAMETERS

heading: B.1 CONTROLLER SETUP

text: We set LSTM hidden layer size to be 64, with 1 hidden layer. The learning rate was 0.001, and the entropy penalty strength was 0.3. We used a moving average weight of 0.99 for the critic, and used a temperature of 1.0 for softmax, with the training algorithm as REINFORCE.

heading: B.2 POLICY

text: We use tanh non-linearities. For all the environments, we used reward normalization, and state normalization from (Mania et al., 2018a) except for Swimmer. We further used action normalization for the Minitaur tasks.

heading: B.3 ES-ALGORITHM

text: For ES-optimization, we used algorithm from (Choromanski et al., 2018), where we applied Monte Carlo estimators of the Gaussian smoothings to conduct gradient steps using forward finitedifference expressions. Smoothing parameter σ and learning rate η were: σ = 0.1, η = 0.01.

heading: C PARTITIONINGS METRICS

text: We analyzed obtained partitionings to understand whether they admit simpler representations and how they relate to the partitionings corresponding to Toeplitz-like matrices that are used on a regular basis for the compactification of RL policies.

heading: C.1 SINGLE PARTITIONING METRICS

text:
Partitionings’ Entropies: We analyze the distribution of color assignments for network edges for a partitioning, by interpreting the number of edges assigned for each color as a count, and therefore a probability after normalizing by the total number of edges. We computed entropies of the corresponding probabilistic distributions encoding frequencies of particular colors. We noticed that entropies are large, in particular the representations will not substantially benefit from further compacification using Huffman coding (see: Fig. 12).
Displacement Rank: Recall that the displacement rank (Sindhwani et al., 2015; Demmel & Koev) of a matrix R with respect to two matrices: F,A is defined as the rank of the resulting matrix ∇F,A(R) = FR − RA. Toeplitz-type matrices are defined as those that have displacement rank 2 with respect to specific band matrices (Sindhwani et al., 2015; Demmel & Koev). We further analyze the displacement ranks of the weight matrices for our chromatic networks, and find that they are full displacement rank using band matrices (F,A) for both the Toeplitz- and the Toeplitz-Hankel-type matrices (see: Fig. 13).

heading: C.2 PAIRWISE PARTITIONINGS METRICS

text: We examine the partitionings produced by the controller throughout the optimization by defining different metrics in the space of the partitionings and analyzing convergence of the sequences of produced partitionings in these matrics. We view partitionings as clusterings in the space of all edges of the network. Thus we can use standard cluster similarity metrics such as RandIndex (Rand, 1971) and Variation of Information (Meilă, 2003). Distance metric counts the number of edges that reside in different clusters (indexed with the indices of the vector of distinct weights) in two compared partitionings/clusterings. We do not observe any convergence in the analyzed metrics (see: Fig.14). This suggests that the space of the partitionings found in training is more complex. We leave its analysis for future work.

heading: D TRANSFERABILITY

text: We tested transferability of partitionings across different RL tasks by using the top-5 partitionings (based on maximal reward) from HalfCheetah (one-hidden-layer network of size h = 41), and using them to train distinct weights (for the inherited partitionings) using vanilla-ES for Walker2d (both environments have state and action vectors of the same sizes). This is compared with the results when random partitionings were applied. Results are presented on Fig.15. We notice that transfered partitionings do not underperform. We leave understanding the scale in which these learned partitionings can be transfered across tasks to future work.

heading: E EXPERIMENT SETUP FOR BASELINES IN TABLE 2

text:
We compare the Chromatic network with other established frameworks for structrued neural network architectures. In particular, we consider Unstructured, Toeplitz, Circulant and a masking mechanism (Choromanski et al., 2018; Lenc et al., 2019). We introduce their details below.
Notice that all baseline networks share the same general architecture: 1-hidden layer with h = 41 units and tanh non-linear activation. To be concrete, we only have two weight matrices W1 ∈ R|S|×h,W2 ∈ Rh×|A| and two bias vectors b1 ∈ Rh, b2 ∈ R|A|, where |S|, |A| are dimensions of state/action spaces. These networks differ in how they parameterize the weight matrices.
Unstructured. A fully-connected layer with unstructured weight matrix W ∈ Ra×b has a total of ab independent parameters.
Toeplitz. A toeplitz weight matrixW ∈ Ra×b has a total of a+b−1 independent parameters. This architecture has been shown to be effective in generating good performance on benchmark tasks yet compressing parameters (Choromanski et al., 2018).
Circulant. A circulant weight matrix W ∈ Ra×b is defined for square matrices a = b. We generalize this definition by considering a square matrix of size n × n where n = max{a, b} and then do a proper truncation. This produces n independent parameters.
Masking. One additional technique for reducing the number of independent parameters in a weight matrix is to mask out redundant parameters (Lenc et al., 2019). This slightly differs from the other aforementioned architectures since these other architectures allow for parameter sharing while the masking mechanism carries out pruning. To be concrete, we consider a fully-connected matrix W ∈ Ra×b with ab independent parameters. We also setup another mask weight S ∈ Ra×b. Then the mask is generated via
M = softmax(M/α),
where softmax is applied elementwise and α is a constant. We set α = 0.01 so that the softmax is effectively a thresolding function wich outputs near binary masks. We then treat the entire concatenated parameter θ = [W,S] as trainable parameters and optimize both using ES methods. At
convergence, the effective number of parameter is ab ·η where η is the proportion of M components that are non-zero. During optimization, we implement a simple heuristics that encourage sparse network: while maximize the true environment return R = ∑ t rt, we also maximize the number of mask entries that are zero 1− η. The ultimate ES objective is: R′ = β ·R+ (1−β) · (1− η), where β ∈ [0, 1] is a combination coefficient which we anneal as training progresses. We also properly normalize R and (1− η) before the linear combination to ensure that the procedure is not sensitive to reward scaling.


summaries: The authors design a learnable time-series pre-processing, which they refer to as a learnable group transform (LGT). This is a generalization of the wavelet transform, which maps a time-series signal onto the affine group. In the wavelet transform, multiple scaled and shifted versions of a mother wavelet are "inner-producted" with a signal; the resulting coefficents are the output of the transform. In the LGT, a more flexible transform that just scaling and shifting is applied to the shape of the mother wavelet, which is piece-wise linearly stretched. This elegantly encompasses time-warping and many other wavelet-style transforms into one learnable preprocessing step.

summaries: This paper defines a set of learnable basis functions and a joint learning algorithm to estimate them. It is based on the premise that the common learning approach in time-series is to first represent them in some spectral domain; thus, the main problem is to define and estimate the basis functions. However, this premise is not accurate and many learning algorithms operate just in the actual time domain (even in speech).

summaries: A typical Wavelet Transform is built through the dilation and/or rotation of a mother wavelet, which can been viewed as a group action on a mother wavelet. This work proposes to extend this construction beyond the Euclidean group, and to supervisedly learn operators that will be applied on a mother wavelet. Competitive numerical performances are obtained.

abstractText: We undertake the problem of representation learning for time-series by considering a Group Transform approach. This framework allows us to, first, generalize classical time-frequency transformations such as the Wavelet Transform, and second, to enable the learnability of the representation. While the creation of the Wavelet Transform filter-bank relies on affine transformations of a mother filter, our approach allows for non-linear transformations. This is achieved by sampling a subset of invertible maps on R. The subset considered contains strictly increasing and continuous functions. The transformations induced by such maps enable us to span a larger class of signal representations, from wavelet to chirplet-like filters. We propose a parameterization of such a non-linear map such that its sampling can be optimized for a specific loss and signal. The Learnable Group Transform can thus be cast into a Deep Neural Network. The experiments on diverse time-series datasets demonstrate the expressivity of this framework, which competes with state-of-the-art performances.

authors:
G. Al-Naymat
S. Chawla
J. Taheri

title: Sparsedtw: A novel approach to speed up dynamic time warping

venue: In Proceedings of the Eighth Australasian Data Mining Conference-Volume

authors:
R. Arora
A. Basu
P. Mianjy
A. Mukherjee

title: Understanding deep neural networks with rectified linear units

venue: arXiv preprint arXiv:1611.01491,

authors:
A. Bagnall
J. Lines
J. Hills
A. Bostrom

title: Time-series classification with cote: the collective of transformation-based ensembles

venue: IEEE Transactions on Knowledge and Data Engineering,

authors:
R. Balestriero
R. Baraniuk

title: A spline theory of deep networks (extended version)

venue: arXiv preprint arXiv:1805.06576,

authors:
R. Balestriero
R. Cosentino
H. Glotin
R. Baraniuk

title: Spline filters for end-to-end deep learning

venue: In International Conference on Machine Learning,

title: Shear madness: signal-dependent and metaplectic time-frequency representations

authors:
R.G. Baraniuk
D. L Jones

title: Wigner-based formulation of the chirplet transform

venue: IEEE Transactions on signal processing,

title: Scattering representations for recognition

venue: PhD thesis,

authors:
E. Cakir
E. Can Ozan
T. Virtanen

title: Filterbank learning for deep neural network based polyphonic sound event detection

venue: In Neural Networks (IJCNN),

authors:
Y. Chen
E. Keogh
B. Hu
N. Begum
A. Bagnall
A. Mueen
G. Batista

title: The ucr time series classification archive

venue: Group equivariant convolutional networks. In International Conference on Machine Learning,

authors:
R.R. Coifman
M.V. Wickerhauser

title: Entropy-based algorithms for best basis selection

venue: Information Theory, IEEE Transactions on,

authors:
R. Cosentino
R. Balestriero
R.G. Baraniuk
A. Patel

title: Overcomplete frame thresholding for acoustic scene analysis

venue: arXiv preprint arXiv:1712.09117,

authors:
H.G. Feichtinger
W. Kozek
F. Luef

title: Gabor analysis over finite abelian groups

venue: Applied and Computational Harmonic Analysis,

title: Time frequency and chirps

venue: In Wavelet Applications VIII,

authors:
S. Goldenstein
J. Gomes

title: Time warping of audio signals

venue: In cgi, pp

authors:
R. Gribonval
E. Bacry

title: Harmonic decomposition of audio signals with matching pursuit

venue: IEEE Transactions on Signal Processing,

authors:
T. Grill
J. Schlüter

title: Two convolutional neural networks for bird detection in audio signals. In Proceedings of the 25th European Signal Processing Conference (EUSIPCO), Kos Island, Greece, August 2017

authors:
G. Kerkyacharian
D. Picard

title: Regression in random design and warped

venue: wavelets. Bernoulli,

authors:
H. Khan
B. Yener

title: Learning filter widths of spectral decompositions with wavelets

authors:
M. Korda
I. Mezić

title: Linear predictors for nonlinear dynamical systems: Koopman operator meets model predictive control

authors:
F. Lelandais
H. Glotin

title: Mallat’s matching pursuit of sperm whale clicks in real-time using daubechies 15 wavelets. In New Trends for Environmental Monitoring

venue: Using Passive Systems,

title: Group invariant scattering

venue: Communications on Pure and Applied Mathematics,

title: Understanding deep convolutional networks. Philosophical Transactions of the Royal Society A: Mathematical

venue: Physical and Engineering Sciences,

authors:
S. Mallat
Z. Zhang

title: Matching pursuits with time-frequency dictionaries

venue: Signal Processing, IEEE Transactions on,

authors:
E. Oyallon
S. Zagoruyko
G. Huang
N. Komodakis
S. Lacoste-Julien
M.B. Blaschko
E. Belilovsky

title: Scattering networks for hybrid representation learning

venue: IEEE transactions on pattern analysis and machine intelligence,

authors:
M. Ravanelli
Y. Bengio

title: Interpretable convolutional filters with sincnet

venue: arXiv preprint arXiv:1811.09725,

authors:
C. Saritha
V. Sukanya
Y.N. Murthy

title: Ecg signal analysis using wavelet transforms

venue: Bulg. J. Phys,

title: The boss is concerned with time series classification in the presence of noise

venue: Data Mining and Knowledge Discovery,

authors:
L. Seydoux
N.M. Shapiro
J. de Rosny
F. Brenguier
M. Landès

title: Detecting seismic activity with a covariance matrix analysis of data recorded on seismic arrays

venue: Geophysical Journal International,

authors:
D. Stowell
M.D. Plumbley

title: Framewise heterodyne chirp analysis of birdsong

venue: Proceedings of the 20th European Signal Processing Conference (EUSIPCO),

title: An open dataset for research on audio field recording archives: freefield1010

title: Wavelets associated with representations of the affine weyl–heisenberg group

venue: Journal of Mathematical Physics,

title: Special Functions and the Theory of Group Representations, volume 22

venue: American Mathematical Soc.,

authors:
Z. Wang
W. Yan
T. Oates

title: Time series classification from scratch with deep neural networks: A strong baseline

venue: In 2017 international joint conference on neural networks (IJCNN),

authors:
D.A. Winkler
T.C. Le

title: Performance of deep and shallow neural networks, the universal approximation theorem, activity cliffs, and qsar

venue: Molecular informatics,

authors:
N. Zeghidour
N. Usunier
I. Kokkinos
T. Schaiz
G. Synnaeve
E. Dupoux

title: Learning filterbanks from raw speech for phone recognition

venue: IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP),

title: L2(R) and κ ∈ R. It is in fact a Koopman operator Korda & Mezić (2018)

venue: PROOF THEOREM 1 Proof. Let τ ∈ R and g,

heading: 1 INTRODUCTION

text:
The selection of the time-frequency representation for analyzing, classifying, and predicting time-series has long been studied (Coifman & Wickerhauser, 1992; Mallat & Zhang, 1993; Gribonval & Bacry, 2003). To this day, the front-end processing of time-series remains a keystone toward the improvement of a wealth of applications such as health-care (Saritha et al., 2008)), environmental sound (Balestriero et al., 2018; Lelandais & Glotin, 2008), and seismic data analysis (Seydoux et al., 2016). The common denominator of the recorded signals in these fields is their undulatory behavior. While these signals share this common behavior, two significant factors imply the need of learning the representation: 1) time-series are intrinsically different because of their physical nature, 2) the machine learning task can be different even within the same type of data. Therefore, the representation should be induced by both the signal and the task at hand.
An all too common approach to performing inference on time-series consists of building a Deep Neural Network (DNN) that operates on a spectral decomposition of the time-series such as Wavelet Transform (WT) or Mel Frequency Spectral Coefficients (MFSC). The selection of the judicious transform is either performed by an expert in the signal at hand, or by considering the aforecited selection methods and their derivatives. However, an inherent drawback is that the selection of the time-frequency transform is often achieved with criteria that do not align with the task. For instance, a selection based on the sparsity of the representation while the task is the classification of the signals. Besides, these selection methods and transformations require substantial cross-validations of a large number of hyperparameters such as mother filter family, number of octaves, number of wavelets per octave, size of the window (Cosentino et al., 2017).
To alleviate these drawbacks, Ravanelli & Bengio (2018); Balestriero et al. (2018); Cakir et al. (2016); Zeghidour et al. (2018) investigated the learnability of a mother filter. This learnable mother filter is transformed by deterministic affine maps. These transformations constitute the filter-bank. The representation of the signal is obtained by convolving the filter-bank atoms with the signals. Recently, Khan & Yener (2018) investigated the learnability of the affine transformations, that is, the sampling of the dilation parameter of the affine group inducing the wavelet filter-bank. Optimized jointly with the DNN, their method allows an adaptive transformation of the mother filter. Another approach consists of building equivariant-invariant representations. In Mallat (2012); Bruna (2013) they propose a translation-invariant representation, the Scattering Transform, which is stable under
the action of small diffeomorphisms. In Oyallon et al. (2018); Cohen & Welling (2016), they focus on equivariant-invariant representations for images, which reduces the sample complexity and endow DNN’s layers with interpretability.
In this work, we focus on GT, which is achieved by taking the inner product between the filter-bank, which is built by taking the action of a transformation map on a mother filter, and the signal. Well-known GTs are the Short-Time Fourier Transform (STFT) and the Continuous Wavelet Transform (CWT). We propose to extend these GTs and improve their flexibility by introducing the Learnable Group Transform (LGT) by 1) generalizing the affine transformations of a mother filter leading to wavelet filter-bank by introducing non-linear transformations (Section 3.1), 2) proposing a parameterization of such non-linear map such that it can be learned efficiently and jointly with any DNN, (Sections 3.2, 3.3), 3) Replacing the affine transformations of CWT by non-linear maps allows for greater flexibility in the learnable spectral decomposition which displays different equivariance properties (Section 3.4). This flexibility improves the linearization capability of the representation as it eases the learning of a spectral decomposition that is able to discard intricate patterns in the time-series that are nuisances. This specific transformation of a filter induces a filter with a non-linear instantaneous phase, which in turn, allows to span filters a la chirplets, which are of interest in a variety of domains such as biology and medicine, mechanics and vibrations, and sonar systems (Flandrin, 2001). Also, this generalization implies that for fixed network topology, replacing the learnable affine group with the continuous group leads to a larger class of spannable functions, which improves the approximation property of the DNN at hand (Winkler & Le, 2017; Balestriero & Baraniuk, 2018). In order to show the generality of our approach, we apply our algorithm on two diverse time-series classification problems (Section 4).

heading: 2 BACKGROUND AND NOTATIONS

text: We first highlight the properties of particular GTs by expressing their time-frequency tiling.

heading: 2.1 TIME-FREQUENCY TILING

text:
The spread of a filter and its Fourier transform are inversely proportional as per the Heisenberg uncertainty principle (Mallat, 1999). Following this principle, we can observe that in the case of STFT (respectively WT with a Gabor wavelet), at a given time τ , the signal is transformed by a window of constant bandwidth (respectively proportional bandwidth) modulated by complex exponential resulting in a uniform tiling (respectively proportional) on the frequency axis, Figure (1). In the case of a chirp-like filter, as proposed in Baraniuk & Jones (1996), each tile is a sheared rectangular, more generally, an affinely trans-
formed rectangular. In this case, as well, the lower bound area of the sheared rectangular is constrained by the uncertainty principle. As such, the understanding of the benefits of various time-frequency decompositions can be achieved by analyzing how they tile the time-frequency plane. For instance, in the case of WT, the precision in frequency degrades as the frequency increases while its precision in time increases (Mallat, 1999). In the case of STFT, the uniform tiling implies that the precision is constant along the frequency axis. In our proposed framework, the LGT allows for an adaptive tiling, as illustrated in Figure (1) such that the trade-off between time and frequency precision depends on the task and data.

heading: 3 LEARNABLE GROUP TRANSFORM

text: To extend the filter-bank derivation as proposed in a wavelet decomposition we introduce a learnable group transform. We now define a subset of invertible maps on R enabling the transformation of a mother filter . Then, we provide a parameterization of such functions and show how one can efficiently learn these parameters. Finally, we derive the equivariance properties of the induced group transform. The overall building block the LGT and its application on a signal is depicted in Figure (2).

heading: 3.1 STRICTLY INCREASING AND CONTINUOUS TRANSFORMATIONS

text:
In order to generalize the classical affine transformations used in WT, we propose the utilization of strictly increasing and continuous functions defined as
Cinc(R) = {g ∈ C(R)|g is strictly increasing} , (1)
where C(R) defines the space of continuous functions defined on R. This set of function is composed of invertible maps which is crucial in order to derive invariance properties as well as avoid artifacts in the transformed filters.
We define the linear operator ρinc(g) by [ρinc(g)ψ](t) = ψ ( g(t) ) , ∀ψ ∈ L2(R),∀g ∈ Cinc(R), (2)
where ψ denotes a mother filter. We can see that the increasing and continuous group representation operator ρinc induces a mapping which depends on the function g ∈ Cinc(R). If for instance g = e , i.e., the identity map, then we have ρinc(e)ψ = ψ, it is in fact the identity operator in the space of the mother filter. Given a mother filter ψ ∈ L2(R), ρinc(g)ψ, ∀g ∈ Cinc(R) induces a nonlinear transformation of the mother filter which can be visualized in Figure (3). Note that in signal processing, such a transformation is called warping (Goldenstein & Gomes, 1999; Kerkyacharian et al., 2004).
Among the possible transformations induced on a mother filter by the mapping g ∈ Cinc(R), some of them correspond to well-known filters (Table 1).

heading: 3.2 SAMPLING THE TRANSFORMATION MAPS

text:
In this work, we are specifically interested in the learnability of such an increasing and continuous map. As such, we provide a way to sample such a space via its parameterization. We propose to use piece-wise affine functions constrained such that they belong to the class of strictly increasing and continuous functions. This constrained piece-wise affine map is defined as
g(a,b)(t) = n∑ l=1 (alt+ bl)1Il(t), ∀t ∈ R, (3)
s.t.: al > 0, ∀l ∈ {1, . . . , n}, (4) bl+1 = (al − al+1)tl+1 + bl, ∀l ∈ {1, . . . , n− 1}, (5)
where a = (a1, . . . , an), b = (b1, . . . , bn), 1Il is the indicator function of the intervals Il = [tl, tl+1),∀l ∈ {2, . . . , n− 1} and I1 = (−∞, t1), In = [tn,+∞), and al and bl denote respectively the slope and offset of each piece of the function and n is the number of pieces. As such, for each (a,b) satisfying the constraints (4) and (5) the function g(a,b) is a sample from the set Cinc(R).
Notice that this mapping can be performed using a 1-layer ReLU Neural Network (Arora et al., 2016). This implementation implies a knot-free piece-wise affine mapping, providing more flexibility regarding the transformation map. The knot-free mapping is defined such that the uniform support, i.e., the intervals Il (3), is replaced with varying support for different l ∈ {1, . . . , n}. As such, this flexibility induces better approximation property (Jupp, 1978).

heading: 3.3 LEARNING THE PIECE-WISE AFFINE TRANSFORMATION MAPS

text:
The parameters (ak,bk),∀k ∈ {1, . . . ,K} are differentiable with respect to the filter and thus any deep learning pipeline using those filters can be used and optimized jointly with the other DNN parameters by stochastic gradient descend methods. Given a set of signals {si ∈ L2(R)}Ni=1 and given a task specific loss function L, we aim at solving the following optimization problem
min (a1,b1)∈Ω1,...,(aK ,bK)∈ΩK N∑ i=1 L ( F (W[si, ψ](g, .) ) , (6)
where N denotes the number of signals, K the number of filters, F represents a DNN, Ωk = {ak ∈ Rn+,bk ∈ Rn|b(k,l+1) = (a(k,l)−a(k,l+1))t(l+1,k) + b(k,l)}∀k ∈ {1, . . . ,K}, and W[si, ψ](g, .) = [W[si, ψ](g(a1,b1), .), . . . ,W[si, ψ](g(aK ,bK), .)] T , and
W[si, ψ](g(ak,bk), .) = (si ? ρinc(g(ak,bk))ψ̄)(.), g(ak,bk) ∈ Cinc(R), ∀k ∈ {1, . . . ,K} , (7)
where ψ̄(t) = ψ(−t) and (.) corresponds to the time axis. We propose different settings that will impact the type of filter-bank our method can reach.
First, We propose a normalization of the frequency of the transform filter (denoted in the result tables by nLGT). This normalization helps to reduce the aliasing induced by the filters. We propose to use f̂ , the normalized frequency f with respect to the maximum slope of the piece-wise affine mapping. For instance, in the case of a Morlet wavelet, the normalization is as follows
[ρinc(g(a,b))ψ](t) = π − 14 exp ( 2πjf̂g(a,b)(t) ) exp ( −1
2 (g(a,b)(t)/σ)
2 ) ,
where f̂ = f/maxl∈{1,...,n} al, j is the imaginary unit, and σ is the width parameter defining the localization of the wavelet in time and frequency. This normalization will be performed for each sample of the group, and thus for each generated filter k ∈ {1, . . . ,K} of the filter-bank. Second, we constrain the domain of the piece-wise affine map, as derived in (3) (denoted in the result tables by cLGT). In the following experiments, we propose a dyadic constraint of the domain as in the WT. The support of the filter is close to the support of a wavelet filter-bank. However, the envelope of the filter and the instantaneous frequency still vary as in the Chirplet Transform (Baraniuk & Jones, 1996).

heading: 3.4 EQUIVARIANCE PROPERTIES

text:
The equivariance-invariance properties of signal representations play a crucial role in the efficiency of the algorithm at hand (Mallat, 2016). By considering the mapping ρinc as a group action on the space of the mother filter, i.e., L2(R), or more precisely, a representation of a group on L2(R) we can develop the equivariance properties of the LGT. More details regarding the background of this group theoretical approach are given in Appendix A. We can consider the set Cinc(R) with the operation consisting of the composition of function to form the group of strictly increasing and continuous maps denoted by Ginc. This formulation eases the derivation of the equivariance properties of group transforms which can be defined for a group G by
W[ρ(g′)si, ψ](g, .) = W[si, ψ]((g ′)−1 g, .),∀g, g′ ∈ G. (8)
That is, transforming the signal with respect to the group G and computing its representation is equal to computing the representation of the signal and then transforming the representation. If G corresponds to the affine group, the associated group transform is the WT the transformation which is equivariant to scalings and translations. One can already notice that since W(., .) employs convolution, for any group G, the LGT is translation equivariant. We now focus on more specific equivariance properties of the LGT by defining the local equivariance by
∃τ ∈ R,W[ρ(g′)si, ψ](g, τ) = W[si, ψ]((g′)−1 g, τ),∀g, g′ ∈ G.
That is, the representation of a local transformation of a signal in a window centred at τ is equals to the transformation of the representation at τ . The size of the window depends on the support of the filter. As a matter of fact, assuming that the representation of Ginc is unitary, we have the following proposition. Proposition 1. The LGT is locally equivariant with respect to the action of the group Ginc.
Refer to Appendix E for the proof.

heading: 4 EXPERIMENTS

text: For all the experiments and all the settings, i.e., LGT, nLGT, cLGT, cnLGT, the increasing and continuous piece-wise affine map is initialized randomly, and the optimization is performed with Adam Optimizer, and the number of knots of each piece-wise affine map is 256. The mother filter used for our setting is a Morlet wavelet filter. The code of the LGT framework will be provided on the Github page of the first author.

heading: 4.1 ARTIFICIAL DATA: CLASSIFICATION OF CHIRP SIGNALS

text:
We present an artificial dataset that demonstrates how a specific time-frequency tiling might not be adapted or would require cross-validations for a given task and data. To build the dataset, we
generate one high frequency ascending chirp and one descending high-frequency chirp of size 8192 following the chirplet formula provided in (Baraniuk & Jones (1996)). Then for both chirp signals, we add Gaussian noise samples (100 times for each class), see Figures in Appendix (C.1). The task aims at being able to detect whether the chirp is ascending or descending. Both the training and test sets are composed of 50 instances of each class. For all models, set the batch size to 10, the number of epochs to 50. Each experiment was repeated 5 times with randomly sampled train and test set, and the accuracy was the result of the average over these 5 runs. Each GT is composed with a non-linearity, and the inference is performed by a linear classifier. For the case of WT and LGT, the size of the filters is 512. As we can observe in Table (2), the WT, as well as the STFT with few numbers of filters, perform poorly on this dataset. The chirp signals to be analyzed are localized close to the Nyquist frequency, and in the case of WT, as illustrated in Figure 1, the wavelet filter-bank has a poor frequency resolution in high frequency while benefiting from a high time resolution. In this experiment, we can see that this characteristic the WT time-frequency tiling implies that through time, the small frequency variations of the chirp are not efficiently captured.
In the case of STFT, as the number of filter decreases, the frequency resolution gets altered. Thus, this frequency variation is not captured. Using a large window for the STFT increases the frequency resolution of the tiling and thus enables to capture the difference between the two classes. In the LGT setting, the tiling has adapted to the task and produces good performances except for the cLGT model. In fact,
the domain of the piece-wise linear map is constrained to be dyadic, and thus the adaptivity of the filter bank is reduced, which is not suitable for this specific task. For all settings, the visualization of the filters, as well as the representations of the signals, can be found in Appendix (C.1.2,C.1.3). This experiment shows an example of signals that are not easily classified by neither the proportionalbandwidth nor the constant-bandwidth without considering cross-validation of hyperparameters.

heading: 4.2 SUPERVISED BIRD DETECTION

text:
We now propose a large scale dataset to validate the suitability of our model in a noisy and realistic setting. The dataset is extracted from the Freesound audio archive Stowell & Plumbley (2013). This dataset contains about 7, 000 field recording signals of 10 seconds sampled at 44 kHz, representing slightly less than 20 hours of audio signals. The content of these recordings varies from water sounds to city noises. Among these signals, some contain bird songs that are mixed with different background sounds having more energy than the bird song, see Appendix (C.2.1). The given task is a binary classification where one should predict the presence or absence of a bird song. As the dataset is unbalanced, we use the Area Under Curve (AUC) metric. The results we propose for both the benchmarks and our models are evaluated on a test set consisting of 33% of the total dataset. In order
to compare with previously used methods, we use the same seeds to sample the train and test set, the batch size, i.e., 10, and the learning rate cross-validation grid as in Balestriero et al. (2018). For each model, the best hyperparameters are selected, and we train and evaluated randomly 10-times the models with early stopping, the results are shown in Table (3). While the first layer of the architecture has a model-dependent representation (i.e., MFSC, LGT, Conv. filters,...), we use the state-of-the-art architecture (Grill & Schlüter (2017)) for the DNN architecture, described in Appendix (B.2). Notice that this specific DNN architecture has been designed and optimized for MFSC representation. As we can see in Table 3, the case without constraints (LGT) reaches better accuracy than the domain expert benchmark (MFSC), showing the ability of such transformation to tile the time-frequency plane according to the task and data at hand. Besides, including more constraints on the model (cnLGT) reduces overfitting and further improve results to outperform the other benchmarks.
One can notice that all the learned filters in Figure 5 contain either an increasing chirp or a decreasing chirp, corresponding respectively to the convexity or concavity of the instantaneous phase of the filter and thus of the piece-wise linear map. Such a feature is being used and is crucial in the detection and analysis of bird song (Stowell & Plumbley, 2012).

heading: 4.3 HAPTICS DATASET CLASSIFICATION

text:
The Haptics dataset is a classification problem with five classes and 155 training and 308 testing samples from the UCR Time Series Repository Chen et al. (2015), where each time-series has 1092 time samples. As opposed to the bird dataset where features of interests are known, and competitive methods have been established, there is no expert knowledge regarding the specific signal features (see Table 4).
One can see that our method outperforms other approaches in the cLGT setting while performing the classification with a linear classifier as opposed to other methods using DNN algorithms. This demonstrates the capability of our method to transform the data efficiently while not requiring a further change of basis. Besides, even in a small dataset setting, our approach is capable of learning an efficient transformation of the data. We provide in
Figure 6 the visualization of some sampled filters for each setting of the LGT model. As opposed to the supervised bird dataset, we can see that the filters do not coincide with well-known filters that are commonly used in signal processing. This is an example of an application where the features of interest in the signals are unknown, and one requires a learnable representation.

heading: 5 CONCLUSION

text: We proposed to extend the WT by introducing a GT based on non-linear transformations of the mother filter. We restrain the transformation to be in the space of strictly increasing and continuous functions enabling its connection with well known time-frequency filters as well as the derivation of equivariance properties. We also shown a tractable way to learn to sample these transformations. From bird detection to haptics classification, our approach competes with state-of-the-art methods without a priori knowledge on the signal power spectrum and outperform classical hand-crafted time-frequency representations. Interestingly, in the bird detection experiment, we recover chirplet filters that are known to be crucial to their detection, while in the case of the haptic dataset where important features to be captured to perform the classification of the signals accurately are unknown, the filters learned are very dissimilar to classical time-frequency filters.

heading: A GROUP TRANSFORM: A GROUP REPRESENTATION APPROACH

heading: A.1 BACKGROUND

text:
For further details on the group theoretical aspects described in this section, the reader should refer to Vilenkin (1978). Definition 1. A group is a set G with a multiplicative operation that respects enclosure, identity element, inverse element, and associativity.
The representation of the group determines its action on a function space and bridges the gap between group theory and linear algebra, allowing to compute the transformation of a function following the rules induced by the specific group at hand. The representation of a group can be thought as a farreaching generalization of the exponential function property, exp(x+ y) = exp(x) exp(y),∀x, y ∈ R (Baraniuk, 1993). In fact, it is defined as, Definition 2. A linear continuous representation ρ of a group G on the linear space H is defined as
ρ : G→ GL(H), (9)
where GL(H) is the the group of linear map in H such that ∀g, g′ ∈ G ρ(g g′) = ρ(g)ρ(g′). (10)
For instance, let H be a vector space such as R3, the representation of the group is induced by 3× 3 matrices. In this case, the operation on the right of (10) is a matrix multiplication, where each matrix depends on the group elements g and g′. This concept extends to linear operators acting on functional spaces.
As such, multiple transformations of a function by different elements of the group is equal to the representation of the combination of the group elements applied to the function.
This structure-preserving map defines the action of a group on elements of function spaces. Group transforms such as STFT and CWT can be expressed in such a way by selecting a mother filter space and a group. The representation of the group in the mother filter space provides an operator that takes as input an element of the group and acts on the filter to transform it. A filter-bank can thus be created by iterating this process with different group elements. Therefore, the selected group carries the characteristics of the filter-bank and consequently, the group transform and its time-frequency tiling. The building blocks of the WT through representation theory is provided in Appendix A.2. Notice that further properties such as the invariant measure of the group and the resolution of the identity can be develop using the representation of the group.

heading: A.2 EXAMPLE: THE WAVELET TRANSFORM

text:
As an introductory example, we consider the creation of a wavelet filter-bank utilizing transformation group. Let’s denote by Gaff the affine group, the so called ”ax + b” group, where the elements (λ, τ) ∈ R?+×R, where R?+ = (0,+∞), where the multiplicative operation of the group is defined by (λ, τ) (λ′, τ ′) = (λλ′, τ + λτ ′) (11) Let’s define by ρaff the representation of the affine group in L2(R), i.e., ρaff : Gaff → GL(L2(R)), such that ρaff is a homomorphism as per Definition 2. Its action on square integrable function ψ is defined as
[ρaff(g)ψ] (t) = 1√ λ ψ( t− τ λ ), t ∈ R, (12)
where (a, b) are respectively the dilation and translation parameters. The wavelet filter-bank is built by transforming a mother filter, ψ by the representation ρaff for specific elements of the group. A visualization of this approach for a Morlet wavelet filter can be seen in Figure (3). The wavelet transform of a signal si ∈ L2(R) is achieved by
W(si, ψ)(g(λ,τ)) = 〈 si, ρaff(g(λ,τ))ψ 〉 ,∀g(λ,τ) ∈ Gaff, (13)
= (si ? ρaff(g(λ,0))ψ̄),∀g(λ,0) ∈ Gaff, (14)
where ψ̄(t) = ψ(−t), 〈., .〉 denotes the inner product, ? the convolution, and ρaff(g(λ,τ))ψ the action of the operator ρaff, evaluated at the group element g(λ,τ), on the mother filter ψ as per (12). In practice, the filter-bank is generated by sampling a few elements of the group. For instance, in the case of the dyadic wavelet transform, the dilation parameters follow a geometric progression of common ratio equals to 2. In general, the translation parameter is sampled according to the scaling one (Daubechies, 1992). Notice that in the convolution expression (14), the translation parameter τ = 0, in fact the convolution operator ? acts as the translation one. In the case where the translation parameter depends on the scaling one, a specific stride is used to perform the discrete convolution.
Note that the STFT can be constructed similarly utilizing the Weyl-Heisenberg group (Feichtinger et al., 2009), whose representation on L2(R) consists of frequency modulations and translations. More intricated group representations can be built as in Torrésani (1991) where the combination of the affine group and Weyl-Heisenberg group is considered.

heading: B ARCHITECTURE DETAILS

heading: B.1 ARTIFICIAL DATA

text:
Group Transform + Complex Modulus + Log Dense Layer (1 sigmoid)
After the Group Transform, a batch-normalization is applied.

heading: B.2 SUPERVISED BIRD DETECTION

text:
Group Transform + Complex Modulus + Log + Average-Pooling (stride:(1, 512) size:(1, 1024)) Conv2D. layer (16 filters 3× 3) and Max-Pooling (3× 3) and ReLU Conv2D. layer (16 filters 3× 3) and Max-Pooling (3× 3) and ReLU Conv2D. layer (16 filters 3× 1) and Max-Pooling (3× 1) and ReLU Conv2D. layer (16 filters 3× 1) and Max-Pooling (3× 1) and ReLU
Dense layer (256) and ReLU Dense layer (32) and ReLU
Dense layer (1 sigmoid)
At each layer a batch-normalization is applied and for the last three layers a 50% dropout is applied as in (Grill & Schlüter (2017)). The dimension of the input of the DNN presented is the same for the different benchmarks.

heading: B.3 HAPTICS DATA

text:
Group Transform + Complex Modulus + Log + Average-Pooling (stride:(1, 64) size:(1, 128)) Dense Layer (5 softmax)
After the Group Transform, a batch-normalization is applied.

heading: C ADDITIONAL FIGURES

heading: C.1 ARTIFICIAL DATA

text: C.1.1 DATA

heading: C.1.2 FILTERS

heading: C.1.3 GROUP TRANSFORM

heading: C.2 SUPERVISED BIRD DETECTION

text:
C.2.1 DATA
Each data sample, normalized, centered and subsampled by two before experiment.

heading: C.2.3 GROUP TRANSFORM

heading: C.2.2 FILTERS

heading: C.3 HAPTICS DATA

text:
C.3.1 DATA
Each data is centered and normalized. For the experiments, the number of epochs is set to 1000 and we perform early-stopping and obtain the testing accuracy at this specific epoch as in Khan & Yener (2018), the batch size was set to 64. In order to avoid overfitting, we perform different asymmetric zeros-paddings on the training samples. For the testing samples, we perform a symmetric zeros-padding (512 zeros on each side of the signals).

heading: C.3.2 FILTERS

heading: C.3.3 GROUP TRANSFORM

heading: D GROUP PARAMETER OPTIMIZATION

text:
In order to learn the group transform module, we can use the back-propagation algorithm and a gradient-based optimization technique such that the parameters of the group transform module, denoted by g, can be learned jointly with the parameters of the DNN, or any other differentiable algorithm taking as input the learnable time-frequency representation. Using the notations of Section 3.3 where L denotes a loss function and F a DNN, the learnability of the optimal group transform leading to the most suitable time-frequency representation is performed by the chain rule,
∂L ∂gk =
∂L ∂[F (Wψ(gk, si))] × ∂[F (Wψ(gk, si))] ∂gk ,∀i ∈ {1, . . . , N} , ∀k ∈ {1, . . . ,K} , gk ∈ Ginc,
where [Wψ(gk, si)] is the convolution of the signals si with the transformed filter ρinc(gk)ψ as defined in (14).

heading: E PROOFS

text: Proposition 2. ρinc is a group representation of Ginc on L2(R).

heading: E.1 PROOF THEOREM 2

text:
Proof. Let g, g′ ∈ Ginc, then
[ρinc(g ′ ~ g)ψ](t) = ψ((g′ ~ g)(t))
= ψ(g′(g(t)))
and,
[ρinc(g ′)ρinc(g)ψ](t) = [ρinc(g ′)ψ](g(t))
= ψ(g′(g(t)))
which verifies the homogeneity property. The linearity is implied by,
[ρinc(g)(κψ1 + ψ2)](t) = (κψ1 + ψ2)(g(t)) = κψ1(g(t)) + ψ2(g(t)),∀t ∈ R.
where ψ1, ψ2 ∈ L2(R) and κ ∈ R. It is in fact a Koopman operator Korda & Mezić (2018).

heading: E.2 PROOF THEOREM 1

text:
Proof. Let τ ∈ R and g, g′ ∈ Ginc,
W[ρinc(g ′)si, ψ](g, τ) = 〈ρinc(g′)si, ρinc(g)ψτ 〉 = 〈 si, ρinc(g ′)−1ρinc(g)ψτ 〉
= 〈 si, ρinc(g ′−1)ρinc(g)ψτ 〉
= 〈 si, ρinc(g ′−1 g)ψτ 〉
= W[si, ψ](g ′−1 g, τ),
where ψτ denotes the filter ψ centered at position τ . Then, there is not guarantee that this can be extrapolated to all τ ∈ R, i.e., in the convolution case, except in the affine case where the global transformation matches the iteration of a local one.

title: LEARNABLE GROUP TRANSFORM FOR TIME-SERIES