summaries: This paper proposes a novel approach to hierarchical reinforcement learning approach by first learning a graph decomposition of the state space through a recurrent VAE and then use the learned graph to efficiently explore the environment. The algorithm is separated into 2 stages where in the first stage random walk and goal conditioned policy is used to explore the environment and simultaneous use a recurrent binary VAE to compress the trajectory. The inference network is given the observation and action and the reconstruction is to, given the hidden state or hidden state+observation, reconstruct the action taken. The approximate posterior takes on the form of a hard Kumaraswamy distribution which can differentiably approximate a binary variable; when the approximate posterior is 0, the decoder must reconstruct the action using the hidden state alone. The nodes of the world graph are roughly states that are used to reconstruct the trajectories in the environment. After the graph is constructed, the agent can use a combination of high-level policy and classical planning to solve tasks with sparse reward.

summaries: This paper proposes an approach to identifying important waypoint states in RL domains in an unsupervised fashion, and then for using these states within a hierarchical RL approach.  Specifically, the authors propose to use a binary latent variable VAE to identify waypoint states, then an HRL algorithm uses these waypoints as intermediate goals to better decompose large RL domains. The authors show that on several grid world tasks, the resulting policies substantially outperform baseline approaches.

abstractText: Efficiently learning to solve tasks in complex environments is a key challenge for reinforcement learning (RL) agents. We propose to decompose a complex environment using a task-agnostic world graphs, an abstraction that accelerates learning by enabling agents to focus exploration on a subspace of the environment. The nodes of a world graph are important waypoint states and edges represent feasible traversals between them. Our framework has two learning phases: 1) identifying world graph nodes and edges by training a binary recurrent variational autoencoder (VAE) on trajectory data and 2) a hierarchical RL framework that leverages structural and connectivity knowledge from the learned world graph to bias exploration towards task-relevant waypoints and regions. We thoroughly evaluate our approach on a suite of challenging maze tasks and show that using world graphs significantly accelerates RL, achieving higher reward and faster learning.

authors:
Pieter Abbeel
Andrew Y Ng

title: Apprenticeship learning via inverse reinforcement learning

venue: In Proceedings of the twenty-first international conference on Machine learning,

authors:
Joshua Achiam
Shankar Sastry

title: Surprise-based intrinsic motivation for deep reinforcement learning

venue: arXiv preprint arXiv:1703.01732,

authors:
Adrien Angeli
David Filliat
Stéphane Doncieux
Jean-Arcady Meyer

title: A fast and incremental method for loop-closure detection using bags of visual words

venue: IEEE Transactions on Robotics,

authors:
Pierre-Luc Bacon
Jean Harb
Doina Precup

title: The option-critic architecture

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

authors:
André Barreto
Will Dabney
Rémi Munos
Jonathan J Hunt
Tom Schaul
Hado P van Hasselt
David Silver

title: Successor features for transfer in reinforcement learning

venue: In Advances in neural information processing systems,

authors:
Joost Bastings
Wilker Aziz
Ivan Titov

title: Interpretable neural predictions with differentiable binary variables. In Proceedings of the 2019 Conference of the Association for Computational Linguistics, Volume 1 (Long Papers)

venue: Association for Computational Linguistics,

authors:
Yuri Burda
Harri Edwards
Deepak Pathak
Amos Storkey
Trevor Darrell
Alexei A Efros

title: Large-scale study of curiosity-driven learning

venue: arXiv preprint arXiv:1808.04355,

authors:
Maria Chatzigiorgaki
Athanassios N Skodras

title: Real-time keyframe extraction towards video content identification

venue: In 2009 16th International conference on digital signal processing,

authors:
Fei Chen
Yang Gao
Shifu Chen
Zhenduo Ma

title: Connect-based subgoal discovery for options in hierarchical reinforcement learning

venue: In Third International Conference on Natural Computation (ICNC 2007),

authors:
Junyoung Chung
Kyle Kastner
Laurent Dinh
Kratarth Goel
Aaron C Courville
Yoshua Bengio

title: A recurrent latent variable model for sequential data

authors:
John D Co-Reyes
YuXuan Liu
Abhishek Gupta
Benjamin Eysenbach
Pieter Abbeel
Sergey Levine

title: Self-consistent trajectory autoencoder: Hierarchical reinforcement learning with trajectory embeddings

venue: arXiv preprint arXiv:1806.02813,

authors:
Christian Daniel
Herke Van Hoof
Jan Peters
Gerhard Neumann

title: Probabilistic inference for determining options in reinforcement learning

venue: Machine Learning,

authors:
Peter Dayan
Geoffrey E Hinton

title: Feudal reinforcement learning

authors:
Jacob Devlin
Ming-Wei Chang
Kenton Lee
Kristina Toutanova

title: Bert: Pre-training of deep bidirectional transformers for language understanding

title: Learning hierarchical control structures for multiple tasks and changing environments

authors:
Jeff Donahue
Yangqing Jia
Oriol Vinyals
Judy Hoffman
Ning Zhang
Eric Tzeng
Trevor Darrell

title: Decaf: A deep convolutional activation feature for generic visual recognition

venue: In International conference on machine learning,

authors:
Adrien Ecoffet
Joost Huizinga
Joel Lehman
Kenneth O Stanley
Jeff Clune

title: Go-explore: a new approach for hard-exploration problems

authors:
Negin Entezari
Mohammad Ebrahim Shiri
Parham Moradi

title: A local graph clustering algorithm for discovering subgoals in reinforcement learning

venue: In International Conference on Future Generation Communication and Networking,

authors:
Benjamin Eysenbach
Ruslan Salakhutdinov
Sergey Levine

title: Search on the replay buffer: Bridging planning and reinforcement learning

venue: arXiv preprint arXiv:1903.00606,

authors:
Zhengzhu Feng
Richard Dearden
Nicolas Meuleau
Richard Washington

title: Dynamic programming for structured continuous markov decision problems

venue: In Proceedings of the 20th conference on Uncertainty in artificial intelligence,

authors:
Dieter Fox
Wolfram Burgard
Sebastian Thrun

title: Active markov localization for mobile robots

venue: Robotics and Autonomous Systems,

authors:
Dibya Ghosh
Abhishek Gupta
Sergey Levine

title: Learning actionable representations with goalconditioned policies

venue: arXiv preprint arXiv:1811.07819,

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

title: Infobot: Transfer and exploration via the information

authors:
Karol Gregor
Frederic Besse

title: Temporal difference variational auto-encoder

venue: arXiv preprint arXiv:1806.03107,

authors:
Karol Gregor
Ivo Danihelka
Alex Graves
Danilo Jimenez Rezende
Daan Wierstra

title: Draw: A recurrent neural network for image generation

venue: In ICML,

authors:
Zhaohan Daniel Guo
Mohammad Gheshlaghi Azar
Bilal Piot
Bernardo A Pires
Toby Pohlen
Rémi Munos

title: Neural predictive belief representations

venue: arXiv preprint arXiv:1811.06407,

authors:
Tuomas Haarnoja
Kristian Hartikainen
Pieter Abbeel
Sergey Levine

title: Latent space policies for hierarchical reinforcement learning

venue: arXiv preprint arXiv:1804.02808,

authors:
Danijar Hafner
Timothy Lillicrap
Ian Fischer
Ruben Villegas
David Ha
Honglak Lee
James Davidson

title: Learning latent dynamics for planning from pixels

venue: arXiv preprint arXiv:1811.04551,

authors:
Peter Henderson
Riashat Islam
Philip Bachman
Joelle Pineau
Doina Precup
David Meger

title: Deep reinforcement learning that matters

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

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

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

venue: In ICLR),

authors:
Ahmed Hussein
Mohamed Medhat Gaber
Eyad Elyan
Chrisina Jayne

title: Imitation learning: A survey of learning methods

venue: ACM Computing Surveys (CSUR),

authors:
Dinesh Jayaraman
Frederik Ebert
Alexei A Efros
Sergey Levine

title: Time-agnostic prediction: Predicting predictable video frames

venue: arXiv preprint arXiv:1808.07784,

authors:
Lukasz Kaiser
Mohammad Babaeizadeh
Piotr Milos
Blazej Osinski
Roy H Campbell
Konrad Czechowski
Dumitru Erhan
Chelsea Finn
Piotr Kozakowski
Sergey Levine

title: Model-based reinforcement learning for atari

authors:
Diederik P Kingma
Jimmy Ba

title: Adam: A method for stochastic optimization

authors:
Diederik P Kingma
Max Welling

title: Auto-encoding variational bayes

venue: In ICLR,

authors:
Thomas Kipf
Yujia Li
Hanjun Dai
Vinicius Zambaldi
Edward Grefenstette
Pushmeet Kohli
Peter Battaglia

title: Compositional imitation learning: Explaining and executing one task at a time

venue: arXiv preprint arXiv:1812.01483,

authors:
Quoc V Le
Navdeep Jaitly
Geoffrey E Hinton

title: A simple way to initialize recurrent networks of rectified linear units

venue: arXiv preprint arXiv:1504.00941,

authors:
Alberto Quattrini Li
Marios Xanthidis
Jason M O’Kane
Ioannis Rekleitis

title: Active localization with dynamic obstacles

venue: In 2016 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS),

authors:
Christos Louizos
Max Welling
Diederik P Kingma

title: Learning sparse neural networks through l_0 regularization

venue: arXiv preprint arXiv:1712.01312,

authors:
Stephanie Lowry
Niko Sünderhauf
Paul Newman
John J Leonard
David Cox
Peter Corke
Michael J Milford

title: Visual place recognition: A survey

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:
Sridhar Mahadevan
Mauro Maggioni

title: Proto-value functions: A laplacian framework for learning representation and control in markov decision processes

venue: Journal of Machine Learning Research,

authors:
Shie Mannor
Ishai Menache
Amit Hoze
Uri Klein

title: Dynamic abstraction in reinforcement learning via clustering

authors:
Amy McGovern
Andrew G Barto

title: Automatic discovery of subgoals in reinforcement learning using diverse density

title: Learning graph-based representations for continuous reinforcement learning domains

venue: In Joint European Conference on Machine Learning and Knowledge Discovery in Databases,

authors:
Dmytro Mishkin
Jiri Matas

title: All you need is a good init

venue: arXiv preprint arXiv:1511.06422,

authors:
Volodymyr Mnih
John Agapiou
Simon Osindero
Alex Graves
Oriol Vinyals
Koray Kavukcuoglu

title: Strategic attentive writer for learning macro-actions

venue: arXiv preprint arXiv:1606.04695,

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

title: Asynchronous methods for deep reinforcement learning

venue: In International Conference on Machine Learning,

authors:
Ashvin V Nair
Vitchyr Pong
Murtaza Dalal
Shikhar Bahl
Steven Lin
Sergey Levine

title: Visual reinforcement learning with imagined goals

venue: In Advances in Neural Information Processing Systems,

authors:
Eric Nalisnick
Padhraic Smyth

title: Stick-breaking variational autoencoders

venue: arXiv preprint arXiv:1605.06197,

authors:
Georg Ostrovski
Marc G Bellemare
Aaron van den Oord
Rémi Munos

title: Count-based exploration with neural density models

authors:
Yudha P Pane
Subramanya P Nageshrao
Robert Babuška

title: Actor-critic reinforcement learning for tracking control in robotics

venue: In Decision and Control (CDC),

authors:
Deepak Pathak
Pulkit Agrawal
Alexei A Efros
Trevor Darrell

title: Curiosity-driven exploration by self-supervised prediction

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

authors:
Karl Pertsch
Oleh Rybkin
Jingyun Yang
Kost Derpanis
Joseph Lim
Kostas Daniilidis
Andrew Jeable. Keyin

title: Discovering subgoal structure with keyframe-based video prediction

authors:
Sébastien Racanière
Théophane Weber
David Reichert
Lars Buesing
Arthur Guez
Danilo Jimenez Rezende
Adria Puigdomenech Badia
Oriol Vinyals
Nicolas Heess
Yujia Li

title: Imaginationaugmented agents for deep reinforcement learning

authors:
Alec Radford
Jeff Wu
Rewon Child
David Luan
Dario Amodei
Ilya Sutskever

title: Language models are unsupervised multitask learners

authors:
Danilo Jimenez Rezende
Shakir Mohamed
Daan Wierstra

title: Stochastic backpropagation and approximate inference in deep generative models

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

title: Imagenet large scale visual recognition challenge

venue: International journal of computer vision,

authors:
Wenling Shang
Herk van Hoof
Max Welling

title: Stochastic activation actor-critic methods

venue: In ECML-PKDD,

authors:
Özgür Şimşek
Alicia P Wolfe
Andrew G Barto

title: Identifying useful subgoals in reinforcement learning by local graph partitioning

venue: In Proceedings of the 22nd international conference on Machine learning,

title: Introduction to reinforcement learning, volume 135

authors:
Matthew E Taylor
Peter Stone

title: Transfer learning for reinforcement learning domains: A survey

title: Learning metric-topological maps for indoor mobile robot navigation

venue: Artificial Intelligence,

authors:
Yuandong Tian
Qucheng Gong

title: Latent forward model for real-time strategy game planning with incomplete information

venue: In NIPS Symposium,

authors:
Alexander Sasha Vezhnevets
Simon Osindero
Tom Schaul
Nicolas Heess
Max Jaderberg
David Silver
Koray Kavukcuoglu

title: Feudal networks for hierarchical reinforcement learning

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

authors:
Yuhuai Wu
Elman Mansimov
Roger B Grosse
Shun Liao
Jimmy Ba

title: Scalable trust-region method for deep reinforcement learning using kronecker-factored approximation

authors:
Yuxin Wu
Yuandong Tian

title: Training agent for first-person shooter game with actor-critic curriculum

heading: 1 INTRODUCTION

text:
Many real-world applications, e.g., self-driving cars and in-home robotics, require an autonomous agent to execute different tasks within a single environment that features, e.g. high-dimensional state space, complex world dynamics or structured layouts. In these settings, model-free reinforcement learning (RL) agents often struggle to learn efficiently, requiring a large amount of experience collections to converge to optimal behaviors. Intuitively, an agent could learn more efficiently by focusing its exploration in task-relevant regions, if it has knowledge of the high-level structure of the environment.
We propose a method to 1) learn and 2) use an environment decomposition in the form of a world graph, a task-agnostic abstraction. World graph nodes are waypoint states, a set of salient states that can summarize agent trajectories and provide meaningful starting points for efficient exploration (Chatzigiorgaki & Skodras, 2009; Jayaraman et al., 2018; Ghosh et al., 2018). The directed and weighted world graph edges characterize feasible traversals among the waypoints. To leverage the world graph, we model hierarchical RL (HRL) agents where a high-level policy chooses a waypoint state as a goal to guide exploration towards task-relevant regions, and a low-level policy strives to reach the chosen goals.
Our framework consists of two phases. In the task-agnostic phase, we obtain world graphs by training a recurrent variational auto-encoder (VAE) (Chung et al., 2015; Gregor et al., 2015; Kingma & Welling, 2013) with binary latent variables (Nalisnick & Smyth, 2016) over trajectories collected using a random walk policy (Ha & Schmidhuber, 2018) and a curiosity-driven goal-conditioned policy (Ghosh et al., 2018; Nair et al., 2018). World graph nodes are states that are most frequently selected by the binary latent variables, while edges are inferred from empirical transition statistics between neighboring waypoints. In the task-specific phase, taking advantage of the learned world graph for structured exploration, we efficiently train an HRL model (Taylor & Stone, 2009).
In summary, our main contributions are:
• A task-agnostic unsupervised approach to learn world graphs, using a recurrent VAE with binary latent variables and a curiosity-driven goal-conditioned policy.
• An HRL scheme for the task-specific phase that features multi-goal selection (Wide-thenNarrow) and navigation via world graph traversal.
• Empirical evaluations on multiple tasks in complex 2D grid worlds to validate that our framework produces descriptive world graphs and significantly improves both sample efficiency and final performance on these tasks over baselines, especially thanks to transfer learning from the unsupervised phase and world graph traversal.

heading: 2 RELATED WORK

text:
An understanding of the environment and its dynamics is essential for effective planning and control in model-based RL. For example, a robotics agent often locates or navigates by interpreting a map (Lowry et al., 2015; Thrun, 1998; Angeli et al., 2008). Our exploration strategy draws inspiration from active localization, where robots are actively guided to investigate unfamiliar regions (Fox et al., 1998; Li et al., 2016). Besides mapping, recent works (Azar et al., 2019; Ha & Schmidhuber, 2018; Guo et al., 2018) learn to represent the world with generative latent states (Tian & Gong, 2017; Haarnoja et al., 2018; Racanière et al., 2017). If the latent dynamics are also extrapolated, the latent states can assist planning (Mnih et al., 2016a; Hafner et al., 2018) or model-based RL (Gregor & Besse, 2018; Kaiser et al., 2019).
While also aiming to model the world, we approach this as abstracting both the structure and dynamics of the environment in a graph representation, where nodes are states from the environment and edges encode actionable efficient transitions between nodes. Existing works (Metzen, 2013; Mannor et al., 2004; Eysenbach et al., 2019; Entezari et al., 2010) have shown benefits of such graph abstractions but typically select nodes only subject to a good coverage the observed state space. Instead, we identify a parsimonious subset of states that can summarize trajectories and provide more useful intermediate landmarks, i.e. waypoints, for navigating complex environments.
Our method for estimating waypoint states can be viewed as performing automatic (sub)goal discovery. Subgoal and subpolicy learning are two major approaches to identify a set of temporally-extended actions, “skills”, that allow agents to efficiently learn to solve complex tasks. Subpolicy learning identifies policies useful to solve RL tasks, such as option-based methods (Daniel et al., 2016; Bacon et al., 2017) and subtask segmentations (Pertsch et al., 2019; Kipf et al., 2018). Subgoal learning, on the other hand, identifies “important states” to reach (Şimşek et al., 2005).
Previous works consider various definitions of “important” states: frequently visited states during successful task completions (Digney, 1998; McGovern & Barto, 2001), states introducing the most novel information (Goyal et al., 2019), bottleneck states connecting densely-populated regions (Chen
et al., 2007; Şimşek et al., 2005), or environment-specific heuristics (Ecoffet et al., 2019). Our work draws intuition from unsupervised temporal segmentation (Chatzigiorgaki & Skodras, 2009; Jayaraman et al., 2018) and imitation learning (Abbeel & Ng, 2004; Hussein et al., 2017). We define “important” states (waypoints) as the most critical states in recovering action sequences generated by some agent, which indicates that these states contain the richest information about the executed policy (Azar et al., 2019).

heading: 3 LEARNING WORLD GRAPHS

text: We propose a method for learning a world graph Gw, a task-agnostic abstraction of an environment that captures its high-level structure and dynamics. In this work, the primary use of world graphs is to accelerate reinforcement learning of downstream tasks. The nodes of Gw, denoted by a set of waypoints states sp ∈ Vp, are generically “important” for accomplishing tasks within the environment, and therefore useful as starting points for exploration. Our method identifies such waypoint states from interactions with the environment. In addition, we embed feasible transitions between nearby waypoint states as the edges of Gw. In this work, we define important states in the context of learning Gw (see Section 2 for alternative definitions). That is, we wish to discover a small set of states that, when used as world graph nodes, concisely summarize the structure and dynamics of the environment. Below, we describe 1) how to collect state-action trajectories and an unsupervised learning objective to identify world graph nodes, and 2) how the graph’s edges (i.e., how to transition between nodes) are formed from trajectories.

heading: 3.1 WAYPOINT STATE IDENTIFICATION

text:
The structure and dynamics of an environment are implicit in the state-action trajectories observed during exploration. To identify world graph nodes from such data, we train a recurrent variational autoencoder (VAE) that, given a sequence of state-action pairs, identifies a subset of the states in the sequence from which the full action sequence can be reconstructed (Figure 2). In particular, the VAE infers binary latent variables that controls whether each state in the sequence is used by the generative decoder, i.e., whether a state is “important” or not.
Binary Latent VAE The VAE consists of an inference, a generative and a prior network. These are structured as follows: the input to the inference network qφ is a trajectory of state-action pairs observed from the environment τ={(st, at)}Tt=0, with s={st}Tt=0 and a={at}Tt=0 denoting the state and action sequences respectively. The output of the inference network is the approximated posterior over a sequence z={zt}Tt=0 of binary latent variables, denoted as qφ(z|a, s). The generative network pθ computes a distribution over the full action sequence a using the masked state sequence, where st is masked if zt=0 (we fix z0=zT=1 during training), denoted as pθ(a|s, z). Finally, a state-conditioned pψ(zt|st) given by the prior network pψ for each st encodes the empirical average probability that state st is activated for reconstruction. This choice encourages inference to select within a consistent subset of states for use in action reconstruction. In particular, the waypoint
Algorithm 1: Identifying waypoint states Vp and learning a goal-conditioned policy πg Result: Waypoint states Vp and a goal-conditioned policy πg Initialize network parameters for the recurrent variational inference model V Initialize network parameters for the goal-conditioned policy πg Initialize Vp with the initial position of the agent, i.e. Vp = {s0 = (1, 1)} while VAE reconstruction error has not converged do
for n← 1 to N do Sample random waypoint sp ∈ Vp Navigate agent to sp and perform T -step rollout using a randow walk policy: τ rn ← {(s0 = sp, a0), ..., (sT , aT )} gn ← sT Navigate agent to sp and perform T -step rollout using πg with goal gn: τπn ← {(s0 = sp, a0), ..., (sT , aT )}at∼πg(·|st,gn) Re-label πg rewards with action reconstruction error as curiosity bonus: rπn ← {1st+1=gn − λ · pθ(at|s, z)}Tt=0 end Perform policy gradient update of πg using τπ and rπ Update V using τ r and τπ Update Vp as set of states with largest prior mean αsαs+βs .
end
states Vp are chosen as the states with the largest prior means and during training, once every few iterations, Vp is updated based on the current prior network. Objective Formally, we optimize the VAE using the following evidence lower bound (ELBO):
ELBO = Eqφ(z|a,s) [log pθ(a|s, z)]−DKL (qφ(z|a, s)|pψ(z|s)) . (1) To ensure differentiablity, we apply a continuous relaxation over the discrete zt. We use the Beta distribution pψ(zt) = Beta(αt, βt) for the prior and the Hard Kumaraswamy distribution qψ(zt|a, z) = HardKuma(α̃t, β̃t) for the approximate posterior, which resembles the Beta distribution but is outside the exponential family (Bastings et al., 2019). This choice allows us to sample 0s and 1s without sacrificing differentiability, accomplished via the stretch-and-rectify procedure (Bastings et al., 2019; Louizos et al., 2017) and the reparametrization trick (Kingma & Welling, 2013). Lastly, to prevent the trivial solution of using all states for reconstruction, we use a secondary objective L0 to regularize the L0 norm of z at a targeted value µ0 (Louizos et al., 2017; Bastings et al., 2019), the desired number of selected states out of T steps, e.g. for when T = 25, we set µ0 = 5, meaning ideally 5 out of 25 states are activated for action reconstruction. Another term LT to encourage temporal separation between selected states by targeting the number of 0/1 switches among z at 2µ0:
L0 = ∥∥Eqφ(z|s,a)[‖z‖0]− µ0∥∥2 , LT = ∥∥∥∥∥Eqφ(z|s,a) [ T∑ t=0 1[zt 6= zt+1] ] − 2µ0 ∥∥∥∥∥ 2 . (2)
See Appendix A for details on training the VAE with binary zt, including integration of the Hard Kumaraswamy distribution and how to regularize the statistics of z.

heading: 3.2 EXPLORATION FOR WORLD GRAPH DISCOVERY

text:
Naturally, the latent structure learned by the VAE depends on the trajectories used to train it. Hence, collecting a rich set of trajectories is crucial. Here, we propose a strategy to bootstrap a useful set of trajectories by alternately exploring the environment based on the current iteration’s Vp and updating the VAE and Vp, repeating this cycle until the action reconstruction accuracy plateaus (Algorithm 1). During exploration, we use action replay to navigate the agent to a state drawn from the current iteration’s Vp. Although resetting via action replay assumes our underneath environment to be deterministic, in cases where this resetting strategy is infeasible, it may be modified so long as to allow the exploration starting points to expand as the agent discovers more of its environment. For
each such starting point, we collect two rollouts. In the first rollout, we perform a random walk to explore the nearby region. In the second rollout, we perform actions using a goal-conditioned policy πg (GCP), setting the final state reached by the random walk as the goal. Both rollouts are used for trianing the VAE and the latter is also used for training πg .
GCP provides a venue to integrate intrinsic motivation, such as curiosity (Burda et al., 2018; Achiam & Sastry, 2017; Pathak et al., 2017; Azar et al., 2019) to generate more diverse rollouts. Specifically, we use the action reconstruction error of the VAE as an intrinsic reward signal when training πg . This choice of curioisty also prevents the VAE from collapsing to the simple behaviors of a vanilla πg .

heading: 3.3 EDGE FORMATION

text: The final stage is to construct the edges of Gw, which should ideally capture the environment dynamics, i.e. how to transition between waypoint states. Once VAE training is complete and Vp is fixed, we collect random walk rollouts from each of the waypoints sp ∈ Vp to estimate the underlying adjacency matrix (Biggs, 1993). More precisely, we claim a directed edge sp → sq if there exists a random walk trajectory from sp to sq that does not intersect a third waypoint. We also consider paths taken by πg (starting at sp and setting sq as the goal) and keep the shortest observed path from sp to sq as a world graph edge transition. We use the action sequence length of the edge transition between adjacent waypoints as the weight of the edge. As shown experimentally, a key benefit of our approach is the ability to plan over Gw. To navigate from one waypoint to another, we can use dynamic programming (Sutton, 1998; Feng et al., 2004) to output the optimal traversal of the graph.

heading: 4 ACCELERATING REINFORCEMENT LEARNING WITH WORLD GRAPHS

text:
World graphs present a high-level, task-agnostic abstraction of the environment through waypoints and feasible transition routes between them. A key example of world graph applications for taskspecific RL is structured exploration: instead of exploring the entire environment, RL agents can use world graphs to quickly identify task-relevant regions and bias low-level exploration to these regions. Our framework to leverage world graphs for structured exploration consists of two parts:
1. Hierarchical RL wherein the high-level policy selects subgoals from Vp. 2. Traversals using world graph edges.

heading: 4.1 HIERARCHICAL RL OVER WORLD GRAPHS

text:
Formally, an RL agent learning to solve a task is formulated as a Markov Decision Process: at time t, the agent is in a state st, executes an action at via a policy π(at|st) and receives a rewards rt. The agent’s goal is to maximize its cumulative expected return R = E(st,at)∼π,p,p0 [∑ t≥0 γ trt ] , where p(st+1|st, at), p0(s0) are the transition and initial state distributions. To incorporate world graphs with RL, we use a hierarchical approach based on the Feudal Network (FN) (Dayan & Hinton, 1993; Vezhnevets et al., 2017), depicted in Figure 3. A standard FN
decomposes the policy of the agent into two separate policies that receive distinct streams of reward: a high-level policy (“Manager”) learns to propose subgoals; a low-level policy (“Worker”) receives subgoals from the Manager as inputs and is rewarded for taking actions in the environment that reach the subgoals. The Manager receives the environment reward defined by the task and therefore must learn to emit subgoals that lead to task completion. The Manager and Worker do not share weights and operate at different temporal resolutions: the Manager only outputs a new subgoal if either the Worker reaches the chosen one or a subgoal horizon c is exceeded.
For all our experiments, policies are trained using advantage actor-critic (A2C), an on-policy RL algorithm (Wu & Tian, 2016; Pane et al., 2016; Mnih et al., 2016b). To ease optimization, the feature extraction layers of the Manager and Worker that encode st are initialized with the corresponding layers from πg , the GCP learned during world graph discovery phase. More details are in Appendix B.

heading: 4.2 WIDE-THEN-NARROW GOALS AND WORLD GRAPHS

text: To incorporate the world graph, we introduce a Manager policy that factorizes subgoal selection as follows: a wide policy πw(gwt |st) selects a waypoint state as the wide goal gw ∈ Vp, and a narrow policy πn(gnt |st, gwt ) selects a state within a local neighborhood of gwt , i.e. its -net (Mahadevan & Maggioni, 2007), as the narrow goal gn ∈ {s : D(s, gwt ) ≤ }. The Worker policy πworker(at|st, gnt , gwt ) chooses the action taken by the agent given the current state and the wide and narrow goals from the Manager. A visual illustration is in Figure 4 and training details in Appendix C.2.

heading: 4.3 WORLD GRAPH TRAVERSAL

text:
The wide-then-narrow subgoal format simplifies the search space for the Manager policy. Using waypoints as wide goals also makes it possible to leverage the edges of the world graph for planning and executing the planned traversals. This process breaks down as follows:
1. When to Traverse: When the agent encounters a waypoint state st ∈ Vp, a “traversal” is initiated if st has a feasible connection in Gw to the active wide goal gwt . 2. Planning: Upon triggering a traversal, the optimal traversal route from the initiating state to gwt is estimated from the Gw edge weights using classic dynamic programming planning (Sutton, 1998; Feng et al., 2004). This yields a sequence of intermediate waypoint states.
3. Execution: Execution of graph traversals depends on the nature of the environment. If deterministic, the agent simply follows the action sequences given by the edges of the traversal. Otherwise, the agent uses the pretrained GCP πg to sequentially reach each of the intermediate waypoint states along the traversal (we fine-tune πg in parallel where applicable). If the agent fails to reach the next waypoint state within a certain time limit, it stops its current pursuit and a new (gw, gn) pair is received from the Manager.
World graph traversal allows the Manager to assign task-relevant wide goals gw that can be far away from the agent yet still reachable, which consequentially accelerates learning by focusing exploration around the task-relevant region near gw.

heading: 5 EXPERIMENTAL VALIDATION

text:
We now assess each component of our framework on a set of challenging 2D grid worlds. Our ablation studies demonstrate the following benefits of our framework:
Waypoint type MultiGoal MultiGoal-Sparse MultiGoal-Stochastic Door-Key Learned 2.72±0.59 0.26±0.11 0.60±0.12 0.26±0.19 Random 2.30±0.49 0.19±0.11 0.41±0.25 0.27±0.40
Implementation details, snippets of the tasks and mazes are in Appendix C-D.

heading: 5.1 ABLATION STUDIES ON 2D GRID WORLDS

text:
For our ablation studies, we construct 2D grid worlds of increasing sizes (small, medium and large) along with challenging tasks with different reward structures, levels of stochasticity and logic (summarized in Table 1). In all tasks, every action taken by the agent receives a negative reward penalty. We follow a rigorous evaluation protocol (Wu et al., 2017; Ostrovski et al., 2017; Henderson et al., 2018): each experiment is repeated with 3 training seeds. 10 additional validation seeds are used to pick the model with the best reward performance. This model is then tested on 100 testing seeds. We report mean reward and standard deviation.
We ablate each of the following components in our framework and compare against non-hierarchical (A2C) and hierarchical baselines (FN):
1. initializing the feature extraction layers of the Manager and Worker from πg , 2. applying Wide-then-Narrow Manager (WN) goal instruction, and 3. allowing the Worker to traverse along Gw.
Results are shown in Table 2. In sum, each component improves performance over the baselines.
Wide and narrow goals Using two goal types is a highly effective way to structure the Manager instructions and enables the Worker to differentiate the transition and local task-solving phases. We note that for small MultiGoal, agents do not benefit much from Gw traversal: it can rely solely on the guidance from WN goals to master both phases. However with increasing maze size, the Worker struggles to master traversals on its own and thus fails solving the tasks.
World Graph Traversal As conjectured in Section 4.3, the performance gain of our framework can be explained by the larger range and more targeted exploration strategy. In addition, the Worker
does not have to learn long distance transitions with the aid of Gw traversals. Figure 4 confirms that Gw traversal speeds up convergence and its effect becomes more evident with larger mazes. Note that the graph learning stage only need 2.4K iterations to converge. Even when taking these additional environment interactions into account, Gw traversal still exhibits superior sample efficiency, not to mention that the graph is shared among all tasks. Moreover, solving Door-Key involves a complex combination of sub-tasks: find and pick up the key, reach and open the door and finally exit. With limited reward feedback, this is particularly difficult to learn. The ability to traverse along Gw enables longer-horizon planning on top of the waypoints, thanks to which the agents boost the success rate on medium Door-Key from 0.56±0.02 to 0.75±0.06.
Benefits of Learned Waypoints To highlight the benefit of establishing the waypoints learned by the VAE as nodes for Gw, we compare against results using a Gw constructed around randomly selected states (Vrand). The edges of the random-node graph are formed in the same way as described in Section 3.3 and its feature extractor is also initialized from πg. Although granting knowledge acquired during the unsupervised phase to Vrand is unfair to Vp, deploying both initialization and traversal while only varying Vrand and Vp isolates the effect from the nodes to the best extent. The comparative results (in Table 3, learning curves for MultiGoal in Figure 4) suggest Vp generally outperforms Vrand. Door-Key is the only task in which the two matches. However, Vrand exhibits a large variance, implying that certain sets of random states can be suitable for this task, but using learned waypoints gives strong performance more consistently.
Initialization with GCP Initializing the weights of the Worker and Manager feature extractors from πg (learned during the task-agnostic phase) consistently benefits learning.In fact, we observe that models starting from scratch fail on almost all tasks within the maximal number of training iterations, unless coupled with Gw traversal, which is still inferior to using πg-initialization. Particularly, for the small MultiGoal-Stochastic environment, there is a high chance that a lava square blocks traversal; therefore, without the environment knowledge from πg transferred by weight initialization, the interference created by the episode-terminating lava prevents the agent from learning the task.

heading: 6 CONCLUSION

text: We have shown that world graphs are powerful environment abstractions, which, in particular, are capable of accelerating reinforcement learning. Future works may extend their applications to more challenging RL setups, such as real-world multi-task learning and navigation. It is also interesting to generalize the proposed framework to learn dynamic world graphs for evolving environments, and applying world graphs to multi-agent problems, where agents become part of the world graphs of other agents.

heading: A RECURRENT VAE WITH DIFFERENTIABLE BINARY LATENT VARIABLES

text:
As illustrated in the main text, the main objective for the recurrent VAE is the following evidence lower bound with derivation:
log p(a|s) = log ∫ p(a|s, z)dz
= log ∫ p(a|s, z)p(z|s)q(z|a, s)
q(z|a, s) dz
= log ∫ p(a|s, z) p(z|s)
q(z|a, s) q(z|a, s)dz
≥ Eq(z|a,s)[log p(a|s, z)− log q(z|a, s) p(z|s) ]
= Eq(z|a,s)[log p(a|s, z)]−DKL(q(z|a, s)||p(z|s))
The inference network qψ takes in the trajectories of state-action pairs τ and at each time step approximates the posterior of the corresponding latent variable zt. The prior network pψ takes the state st at each time step and outputs the state-conditioned prior pψ(st). We choose Beta as the prior distribution and the Hard Kuma as the approximated posterior to relax the discrete latent variables to continuous surrogates.
The Kuma distribution Kuma(α, β) highly resembles the Beta Distribution in shape but does not come from the exponential family. Similar to Beta, the Kuma distribution also ranges from bimodal (when α ≈ β) to unimodal (α/β → 0 or α/β → ∞). Also, when α = 1 or β = 1, Kuma(α, β) = Beta(α, β). We observe empirically better performance when we fix β = 1 for the Kuma approximated posterior. One major advantage of the Kuma distribution is its simple Cumulative Distribution Function (CDF):
FKuma(x, α, β) = (1− (1− xα))β . (3)
It is therefore amendable to the reparametrization trick (Kingma & Welling, 2013; Rezende et al., 2014; Maddison et al., 2016) by sampling from uniform distribution u ∼ U(0, 1):
z = F−1Kuma(u;α, β) ∼ Kuma(α, β). (4)
Lastly, the KL-divergence between the Kuma and Beta distributions can be approximated in closed form (Nalisnick & Smyth, 2016):
DKL(Kuma(a, b)|Beta(α, β)) = a− α a
( −γ −Ψ(b)− 1
b ) + log(ab) + log Beta(α, β)− b− 1
b + (β − 1)b ∞∑ m=1
1
m+ ab Beta (m a , b ) , (5)
where Ψ is the Digamma function, γ the Euler constant, and the approximation uses the first few terms of the Taylor series expansion. We take the first 5 terms here.
Next, we make the Kuma distribution “hard” by following the steps in Bastings et al. (2019). First stretch the support to (r = 0− 1, l = 1 + 2), 1, 2 > 0, and the resulting CDF distribution takes the form:
FS(z) = FKuma ( z − l r − l ;α, β ) . (6)
Then, the non-eligible probabilities for 0’s and 1’s are attained by rectifying all samples below 0 to 0 and above 1 to 1, and other value as it is, that is
P (z = 0) = FKuma ( −l r − l ;α, β ) , P (z = 1) = 1− FKuma ( 1− l r − l ;α, β ) . (7)
Lastly, we impose two additional regularization terms L′ and LT on the approximated posteriors. As described in the main text, L′ prevents the model from selecting all states to reconstruct {at}T−10
by restraining the expected L0 norm of z = (z1 · · · zT−1) to approximately be at a targeted value µ0 (Louizos et al., 2017; Bastings et al., 2019). In other words, this objective adds the constraint that there should be µ0 of activated zt = 1 given a sequence of length T . The other term LT encourages temporally isolated activation of zt, meaning the number of transition between 0 and 1 among zt’s should roughly be 2µ0. Note that both expectations in Equation 2 have closed forms for HardKuma.
L0 = ∥∥Eq(z|s,a) [‖z‖0]− µ0∥∥2 , where (8)
Eq(z|s,a) [‖z‖0] = T∑ t=1 Eq(zt|s,a) [1zt 6=0]
= T∑ t=1 1− p (zt = 0) = T∑ t=1 1− FKuma ( −l r − l ;αt, βt ) , (9)
LT = ‖Eq(z|s,a) T−1∑ t=1 1zt 6=zt+1 − 2µ0‖2, where (10)
Eq(z|s,a)[ T−1∑ t=1 1zt 6=zt+1 ] = T−1∑ t=1 p (zt = 0) (1− p (zt+1 = 0)) + (1− p (zt = 0)) p (zt+1 = 0) .
(11)
Lagrangian Relaxation. The overall optimization objective consists of action sequence reconstruction, KL-divergence between the posterior and prior, L0 and LT (Equation 12). We tune the objective weights λi using Lagrangian relaxation (Higgins et al., 2017; Bastings et al., 2019; Bertsekas, 1999), treating λi’s as learnable parameters and performing alternative optimization between λi’s and the model parameters. We observe that as long as their initialization is within a reasonable range, λi’s converge to a local optimum:
max {λ1,2,3} min {θ,φ,ψ} −Eqψ(z|a,s) [log pθ(a|s, z)] +λ1DKL (qφ(z|a, s)|pψ(z|s)) +λ2L0+λ3LT . (12)
We observe this approach to produce efficient and stable mini-batch training.

heading: B GOAL-CONDITIONED POLICY INITIALIZATION FOR HRL

text:
Optimizing composite neural networks like HRL (Co-Reyes et al., 2018) is sensitive to weight initialization (Mishkin & Matas, 2015; Le et al., 2015), due to its complexity and lack of clear supervision at various levels. Therefore, taking inspiration from prevailing pre-training procedures in computer vision (Russakovsky et al., 2015; Donahue et al., 2014) and NLP (Devlin et al., 2018; Radford et al., 2019), we take advantage of the weights learned by πg during world graph discovery when initializing the Worker and Manager policies for downstream HRL, as πg has already implicitly embodied much environment dynamics information.
More specifically, we extract the weights of the feature extractor, i.e. the state encoder, and use them as the initial weights for the state encoders of the HRL policies. Our empirical results demonstrate that such weight initialization consistently improves performance and validates the value of skill/knowledge transfer from GCP (Taylor & Stone, 2009; Barreto et al., 2017).

heading: C ADDITIONAL IMPLEMENTATION DETAILS

text:
Model code folder including all architecture details is shared in comment.
C.1 HYPERPARAMETERS FOR VAE TRAINING
Our models are optimized with Adam (Kingma & Ba, 2014) using mini-batches of size 128, thus spawning 128 asynchronous agents to explore. We use an initial learning rate of 0.0001, with = 0.001, β1 = 0.9, β2 = 0.999; gradients are clipped to 40 for inference and generation nets. For HardKuma, we set l = −0.1 and r = 1.1. The maximum sequence length for BiLSTM is 25. The
total number of training iterations is 3600 and model usually converges around 2400 iterations. We train the prior, inference, and generation networks end-to-end.
We initialize λi’s (see Lagrangian Relaxation) to be λ1 = 0.01 (KL-divergence),λ2 = 0.06 (L0), λ3 = 0.02 (LT ). After each update of the latent model, we update λi’s, whose initial learning rate is 0.0005, by maximizing the original objective in a similar way as using Lagrangian Multiplier. At the end of optimization, λi’s converge to locally optimal values. For example, with the medium maze, λ1 = 0.067 for the KL-term, λ2 = 0.070 for the L0 and λ3 = 0.051 for the LT term. The total number of waypoints |Vp| is set to be 20% of the size of the full state space.
C.2 TRAINING HRL MODELS
The procedure of the Manager and the Worker in sending/receiving orders using either traversal paths among Vp from replay buffer for deterministic environments or with πg for stochastic ones follows:
1. The Manager gives a wide-narrow subgoal pair (gw, gn). 2. The agent takes action based on the Worker policy πω conditioned on (gw, gn) and reaches
a new state s′. If s′ ∈ Vp, gw has not yet met, and there exists a valid path basing on the edge paths from the world graph s′ → gw, agent then either follows replay actions or πg to reach gw. If πg still does not reach desired destination in a certain steps, then stop the agent wherever it stands; also πg can be finetuned here.
3. The Worker receives positive reward for reaching gw for the first time. 4. If agent reaches gn, the Worker also receives positive rewards and terminates this horizon. 5. The Worker receives negative for every action taken except for during traversal; the Manager
receives negative reward for every action taken including traversal. 6. When either gn is reached or the maximum time step for this horizon is met, the Manager
renews its subgoal pair.
The training of the Worker policy πω follows the same A2C algorithm as πg .
The training of the Manager policy πm also follows a similar procedure but as it operates at a lower temporal resolution, its value function regresses against the tm-step discounted reward where tm covers all actions and rewards generated from the Worker.
When using the Wide-then-Narrow instruction, the policy gradient for the Manager policy πm becomes:
E(st,at)∼π,p,p0 [Am,t∇ log (π ω (gw,t|st)πn (gn,t|st, gw,t, sw,t))] +∇ [H (πω) +H (πn(·|gw,t))] ,
where Am,t is the Manager’s advantage at time t. Also, for Manager, as the size of the action space scales linearly with |S|, the exact entropy for the πm can easily become intractable. Essentially there are O ( |V| × (N2) ) possible actions. To calculate the entropy exactly, all of them has to be summed, making it easily computationally intractable:
H = ∑ w∈V ∑ wn∈sw πn(wn|sw, st)πω(w|st) log∇πn(wn|sw, st)πω(w|st).
Thus in practice we resort to an effective alternativeH (πω) +H (πn(·|gw,t)). Psuedo-code for Manager training is in Algorithm 2.
C.3 HYPERPARAMETERS FOR HRL
For training the HRL policies, we inherit most hyperparameters from those used when training πg , as the Manager and the Worker both share similar architectures with πg . The hyperparameters used when training πg follow those from Shang et al. (2019). Because the tasks used in HRL experiments are more difficult than the generic goal-reaching task, we set the maximal number of training iterations to 100K abd training is stopped early if model performance reaches a plateau. The rollout steps for each iteration is 60. Hyperparameters specific to HRL are the horizon c = 20 and the size of the Manager’s local attention range (that is, the neighborhood around gw within which gn is selected), which are N = 5 for small and medium mazes, and N = 7 for the large maze.
Algorithm 2: Training of πm for HRL models Initialize network parameters θ for πm, here πm,t refers to the policy at time rollout time step t; Given a map of V , sV ; for iter = 0, 1, 2, · · · do
Clear gradients dθ ← 0; Reset the set of time steps where πm,t omits a new subgoal Sm = {} and tm = 0.; while t <= tmax or episode not terminated do
Simulate under current policy πm,t−1, πw,t−1; if the Worker has met the previous subgoal or exceeded the horizon c then
Sample a new subgoal gm,t from πm,t; zm,t = fLSTM(CNN(sm,t, sV), hm,tm), Vm,t = fv(zm,t), πt = fp(zm,t) ;
end Sm = Sm ∪ {tm} and tm = t;
end
R = { 0, if terminal Vtmax+1, otherwise ; for t = tmax, · · · 1 do R← rt + γR; if t ∈ Sm then
Am,t ← R− Vm,t; Accumulate gradients from value loss: dθ ← dθ + λ∂A 2 m,t
∂θ ; Accumulate policy gradients with entropy regularization: dθ ← dθ +∇ log πm,t(gm,t)Am,t + β∇H(πm,t);
end end
end
D 2D GRID WORLD VISUALIZATIONS


summaries: This paper investigates the question of identifying concise equations from data to understand the functional relations. In particular, a set of base functions are given in hand and the goal is to obtain the right composition of these functions which fits the target function. The main contribution of the paper is to introduce a selection layer, which enhances sparse connections in the network. Several experiments are conducted to show the effectiveness of the method.

summaries: This paper presents White Box Network (WBN), which allows for composing function blocks from a given set of functions to construct a target function. The main idea is to introduce a selection layer that only selects one element of the previous layer as an input to a function block. This allows for both introducing function priors as well as interpreting the learned function. The paper also presents a setting where each function block is a neural network that can be learned end-to-end using a PathNet style setting and shows positive transfer across MNIST and CIFAR classification tasks.

abstractText: Neural networks have significantly benefitted real-world tasks. The universality of a neural network enables the approximation of any type of continuous functions. However, a neural network is regarded as a non-interpretable black box model, and this is fatal to reverse engineering as the main goal of reverse engineering is to reveal the structure or design of a target function instead of approximating it. Therefore, we propose a new type of a function constructing network, called the white box network. This network arranges function blocks to construct a target function to reveal its design. The network uses discretized layers, thus rendering the model interpretable without disordering the function blocks. Additionally, we introduce an end-to-end PathNet structure through this discretization by considering the function blocks as neural networks

authors:
Magdy M. Abdelhameed
Houshang Darabi

title: Diagnosis and debugging of programmable logic controller control programs by neural networks

venue: In IEEE International Conference on Automation Science and Engineering,

title: Learning deep architectures for AI

venue: Foundations and Trends in Machine Learning,

authors:
Yoshua Bengio
Aaron C. Courville
Pascal Vincent

title: Representation learning: A review and new perspectives

venue: IEEE Trans. Pattern Anal. Mach. Intell.,

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 29: Annual Conference on Neural Information Processing Systems

authors:
Chrisantha Fernando
Dylan Banarse
Charles Blundell
Yori Zwols
David Ha
Andrei A. Rusu
Alexander Pritzel
Daan Wierstra

title: Pathnet: Evolution channels gradient descent in super neural networks

authors:
Diederik P. Kingma
Jimmy Ba

title: Adam: A method for stochastic optimization

venue: In 3rd International Conference on Learning Representations,

authors:
Diederik P. Kingma
Shakir Mohamed
Danilo Jimenez Rezende
Max Welling

title: Semisupervised learning with deep generative models

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

authors:
Zichao Long
Yiping Lu
Bin Dong

title: Pde-net 2.0: Learning pdes from data with A numericsymbolic hybrid deep network. CoRR, abs/1812.04426, 2018a. URL http://arxiv.org/ abs/1812.04426

authors:
Zichao Long
Yiping Lu
Xianzhong Ma
Bin Dong

title: Pde-net: Learning pdes from data

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

authors:
Georg Martius
Christoph H. Lampert

title: Extrapolation and learning equations

venue: In 5th International Conference on Learning Representations,

authors:
Jack W. Rae
Jonathan J. Hunt
Ivo Danihelka
Timothy Harley
Andrew W. Senior
Gregory Wayne
Alex Graves
Tim Lillicrap

title: Scaling memory-augmented neural networks with sparse reads and writes

authors:
Subham S. Sahoo
Christoph H. Lampert
Georg Martius

title: Learning equations for extrapolation and control

authors:
Alexander J. Smola
Bernhard Schölkopf

title: A tutorial on support vector regression

venue: Statistics and Computing,

title: Regression shrinkage and selection via the lasso

venue: Journal of the Royal Statistical Society (Series B),

authors:
Kelvin Xu
Jimmy Ba
Ryan Kiros
Kyunghyun Cho
Aaron C. Courville
Ruslan Salakhutdinov
Richard S. Zemel
Yoshua Bengio

title: Show, attend and tell: Neural image caption generation with visual attention

venue: In Proceedings of the 32nd International Conference on Machine Learning, ICML 2015,

heading: 1 INTRODUCTION

text:
Reverse engineering can be defined as the deconstruction of an object to reveal its design or architecture, or to extract knowledge from the object [Eldad, 2005]. Typically, in machine learning, obtaining the internal functions of a device only with its input and output values is a regression problem. Before machine learning was developed, devices were disassembled to analyze them. However, advances in deep learning have allowed us to approximate various functions in regression tasks; therefore, we can now solve this regression problem without actually looking inside the object. While this development in deep learning (Bengio, 2009; Bengio et al., 2013) has benefitted reverse engineering significantly, some limitations still exist. First, deep learning is a black box model; therefore, the results may not be interpreted. In this case, information regarding the object such as what it does and how it works may not be extracted. This causes field engineers to not entirely trust the results of deep learning even if the correct values were reflected. Next, deep learning approximates the target function and does not reveal the actual design and architecture of the device. An artificial neural network is a mathematical simulation of a neural network composed of human neurons and synapses that simulate the manner in which the human brain recognizes patterns. However, a device typically comprises an electronic circuit and block functions; therefore, it may not fit perfectly with the neural network structure, which can cause large errors when certain data are used. We herein propose a white box network (WBN) with a selection layer, specially designed for reverse engineering. This network continuously composites function blocks to create a target function. We assume that all types of function blocks that can constitute the target function are provided in advance. This differs from the normal neural network because the WBN reveals the exact functions with the correct inputs and their ordering to construct the target function, instead of merely approximating them. Our WBN is different from normal neural networks as the model architecture is discretized using a discretized matrix called the selection layer. Because discretization is interpretable (Chen et al., 2016), our WBN can reconstruct the target function. The WBN is motivated by the questions, Can we benefit from knowing the functions that are used in certain fields?. For example, in a programmable logic controller (PLC), a target function can be obtained through a ladder logic diagram comprising well-known function blocks. Therefore, we can obtain a target function by ordering those function blocks with the correct inputs. As such, in this study, we create a WBN that can automate reverse engineering. For the experiment, we imitated the PLC data and verified whether our model could obtain their ladder logic diagram. Additionally, we conducted other experiments to validate the selection layer. We assumed that we
may not know the functions used in a certain field. Therefore, we regarded the given function blocks as neural networks. Subsequently, the network was ordered and connected to the appropriate neural networks to obtain the target function that resembles PathNet (Fernando et al., 2017). Using this concept, we create an end-to-end PathNet structure and perform experiments to verify whether it functions like PathNet.

heading: 2 RELATED WORKS

text: In machine learning, regression is a task of obtaining a real-valued function y = f(x) from the hypothesis set (X,Y ). However, typically, actual data may contain noise or exhibit data loss owing to measurement limitations or other causes. Therefore, regression is often considered as a black box process and an exact function may not be obtained. For example, in Gaussian process regression [Williams and Ras-mussen, 2006] and support vector regression (SVR) (Smola & Schölkopf, 2004), we reproduced a kernel and obtained an approximated value instead of obtaining a function. Another typical regression method is using a multilayered neural network (Bengio, 2009; Bengio et al., 2013), which approximates a function by using the human neuron model. The aim of reverse engineering is to obtain the exact structure of a function rather than merely approximating it. In some fields, we may know the type of function forms that typically appear; hence, we can use that information to construct a function. An equation learner (EQL) (Martius & Lampert, 2017; Sahoo et al., 2018) is designed for regression task that can be described by analytical expressions of mechanical systems such as a pendulum or a robotic arm. An EQL has been shown more effective at solving dynamics than conventional neural nets; additionally, it reduces extrapolation errors. Furthermore, PDE-net (Long et al., 2018b;a) accurately predicts the dynamics of complex systems and uncovers the underlying hidden partial differential equation models using a convolution kernel filter. This type of model renders regression more effective if certain types of function blocks or processes that appear in a specific field are known. A discrete variable can be used variously, e.g., learning probabilistic latent representations (Kingma et al., 2014), image region (Xu et al., 2015), and memory access (Graves et al., 2014; 2016). Especially for the memory access, it resembles an attention mechanism that can help interpret the focus of the model. The end-to-end memory network (Kingma et al., 2014) uses softmax to access the memory in questions and answering task. This allows us to determine the sentence that the network refers to when it answers a specific question. The neural Turing machine (NTM) (Graves et al., 2014) and differentiable neural computer (Graves et al., 2016) use a sharpening method instead of merely using softmax. As such, those models select information from the memory without disordering information, thus rendering them more interpretable. Therefore, we can determine how the model functions. For example, we can reconstruct the Copy processes of the NTM and create a pseudocode by referring to the headers in the model. Therefore, discretization can be used such that the model is more interpretable (Chen et al., 2016), and it is sometimes more efficient for computing (Rae et al., 2016). PathNet (Fernando et al., 2017) is a modular deep neural network with pathways. It uses a genetic algorithm to obtain the best pathway for learning. The pathways are represented as integer-valued matrices; therefore, the modules can be selected by accessing those matrices. PathNet reuses the pathways for a different task as a transfer learning paradigm and shows the potential in selecting the appropriate modules to obtain the target results.

heading: 3 METHODS

heading: 3.1 WHITE BOX NETWORK ARCHITECTURE

text:
The WBN is a multilayered feed forward network. For each hidden layer, it consists of a selection layer followed by function block mappings. In this study, we assumed that all function blocks constituting the target function were known before we built the model. However, the exact order of the function blocks with the correct inputs must be obtained. Each function block can be multivalued with multiple inputs; however, for simplicity, we assume that the function blocks are unitary and binary operations. Suppose that the model is L-layered, and we have m(l) unitary functions and n(l) binary functions in the lth layer. In the selection layer, we select inputs to enter into each function block. The
selection layer can be written as z(l) = Ŵ (l)y(l−1)
Here, y(l−1) is the output of the previous layer and Ŵ (l) is the selection matrix. If each row of Ŵ (l) has only one 1 and the remaining 0s, then, it selects one element of the y(l−1) as an element of z(l). To make Ŵ (l) differentiable, we approximate Ŵ (l) by
Ŵ (l) = softmax(W (l)/τ, axis=-1)
Here, τ > 0 is a temperature parameter that renders Ŵ sharper as τ → 0. τ can be chosen as both a constant and a learnable parameter. After multiplying the selection matrix, z(l) goes through the function block mappings. Let f (l) 1 , . . . , f (l) m(l) and g (l) 1 , . . . , g (l) n(l) be the given unitary and binary function blocks on the lth layer. Then, our new output y(l) is
y(l) = ( f (l) 1 (z (l) 1 ), . . . , f (l) m(l)(z (l) m(l)), g (l) 1 (z (l) m(l)+1, z (l) m(l)+2), . . . , g (l) n(l)(z (l) m(l)+2n(l)−1, z (l) m(l)+2n(l)) ) As such, when we select the function blocks of each layer, the dimensions of the variables are fixed. For example, y(l) represents (m(l)+n(l))-dimensional vectors and z(l) represents (m(l)+2n(l))dimensional vectors. Finally, we convert the last layer’s output to fit the target output dimension. Therefore, we use the selection layer again to match with the output dimension.
o = Ŵ (L+1)y(L)
Here, the final output is a composition of function blocks from each layer with selective inputs.

heading: 3.2 END-TO-END PATHNET ARCHITECTURE

text:
Suppose we do not have any information regarding the target function. In that case, we can select our function blocks as a single-layered neural network followed by nonlinear activation. Then, our model becomes modular neural network that selects the right modules to find the best pathway to obtain the target value. This concept is the same as that of a previous study, i.e., PathNet (Fernando et al., 2017). To apply one key component of our WBN to existing PathNet architecture, we need to switch the order of the selection layer and the function block mapping for each hidden layer. Therefore, function block mapping is proceeded by the selection layer. In function block mapping, the function blocks are one-layered neural networks with learnable parameters. Each of them is assigned a single input and yields a single output, which is typically multidimensional. Now, suppose that our model is a modular deep neural network with L layers with each layer containing M neural network modules. Let N be the number of maximum distinct modules per layer
that can be selected in a pathway. Let φ(l)1 , , φ (l) M be neural network modules in the lth layer and let k
(l) be the dimension(number of channels) of hidden output variables. Then, the function mapping layer is written as
Z(l) = (φ (l) 1 (y (l−1)), φ (l) 2 (y (l−1)), . . . , φ (l) M (y (l−1)))
Here, Z(l) is M by k(l) matrix. Then, selection layer selects the neural network outputs
Ŷ (l) = Ŵ (l)Z(l)
The selection matrix Ŵ (l) is N ×M with each row of Ŵ (l) ) containing only one almost 1 and the remaining almost 0s; Ŵ (l) can be approximated in the manner described previously. Now, we add all rows of Ŷ (l) such that the hidden output y(l) follows the existing PathNet.
y(l) = reduce sum(Ŷ (l), axis=0)
Finally,there is a linear layer that can be used to convert the last hidden layer to the output value.
o = Wy(L) + b
This architecture is inspired by the PathNet in which a selection matrix instead of a genetic algorithm is used to select a pathway. It is differentiable, and hence we can easily train the network by gradient descent.

heading: 3.3 TRAINING DETAILS

text:
We used the stochastic gradient descent algorithm with mini-batches and Adam (Kingma & Ba, 2015) to update the parameters. The free parameter of the WBN is θ = {W (1), . . . ,W (L)} or possibly θ = {W (1), . . . ,W (L), τ (1), . . . , τ (L)}. Furthermore, we used the mean square error as a loss function for the regression task and an L1 regularization term for W (l)’s
Loss(D) = 1
|D| |D|∑ i=1 ||φ(xi)− yi||2 + α L∑ i=1 |W (l)|1
which is a Lasso-like (Tibshirani, 1996). For the WBN, L1 regularization is highly important in optimization. Without the regularization term, the absolute value of elements of W (l) can become extremely large. This causes Ŵ (l) to be extremely sparse and sharp, and it can be an obstacle for shifting the function blocks from one ordering to another. As expected, the model typically fails to obtain the exact ordering of function blocks when we set α = 0. Hence, the regularization parameter α should be set to more than 0. Typically, we set α ∈ (0, 5] at the beginning of training to prevent the problem.
However, another problem occurs with the scale of α. We typically set α to be more than 0 at the beginning; however, after the model has discovered the exact ordering, Ŵ (l) cannot be sharpened enough because of the large regularization restriction. Therefore, we change the regularization parameter α during training time; we set α = 0 after enough learning time. Two methods exist for selecting when to set α = 0: one is by a threshold and the other is by an iteration number. For the former, if the MSE is smaller than a certain threshold (typically 0.001), we set α = 0. For the latter, if the iteration reaches a certain number (typically t = T/2, where T is the total number of iterations), we set α = 0. Occasionally, we used the temperature learning strategy such that the temperature of each layer can be learned during the optimization. We used τ(> 0) because we wished to sharpen our selection matrix Ŵ (l); however if τ is extremely small at the early stage of training, the model may be prevented from selecting the exact order of function blocks. Because we want our τ to approach zero as learning progresses, we use
τ̂ (l) = 1
τ0 + softplus(τ (l)) or τ̂ (l) =
1
exp(τ0 + softplus(τ (l)))
Ŵ (l) = softmax(W (l)/τ̂ (l), axis=-1) where τ0 is a constant determining upper bound of τ̂ .

heading: 4 EXPRIMENTS

heading: 4.1 LADDER LOGIC DIAGRAM

text:
The ladder logic diagram (LLD) is a programming language that represents a program by a graphical diagram based on the circuit diagrams of a relay logic hardware. It is especially used in developing software for PLCs. Typically, a PLC device is black boxed before it is released as that is the core part of the technology. In fact, an attempt to model a PLC using recurrent neural networks has been reported (Abdelhameed & Darabi, 2005). However, the tracking and analysis of the learning process were inadequate; therefore, the internal structure of the controller could not be determined. Our white box model is designed to reveal this internal structure, and our goal in this experiment is to restore the logic diagram through reverse engineering using the input and output signals of a PLC device.
Three LLDs were used in our experiment, as shown in Figure 3. These LLDs range from simple to complex. The first one is a single output problem and the last two are multiple output problems. Furthermore, in the last two diagrams, the output signals become input signals that create other outputs; therefore, the outputs are highly related to each other. The maximum number of inputs required was six, but we set the input signals as eight dimensional to validate whether the network could find the LLDs even if nonmeaningful input values existed. The inputs and outputs are Boolean numbers, which are either 0 or 1. Therefore, the function
Table 1: Mean squared errors for ladder logic diagrams
LLD1 LLD2 LLD3 WBN (7.404± 0.166)× 10−7 (2.425± 0.160)× 10−6 (3.312± 0.108)× 10−6 ANN (2.729± 0.287)× 10−6 (7.422± 0.280)× 10−5 (9.619± 0.216)× 10−5 SVR 1.181× 10−2 1.861× 10−2 7.123× 10−1
Figure 4: Sample structures for three LLDs suggested by WBN. (a) LLD1 sample #1 constructed by WBN (b) LLD1 sample #2 constructed by WBN (c) LLD2 sample #1 constructed by WBN
blocks used in LLDs are nondifferentiable Boolean discrete functions. To solve this problem, we continuously extended the function blocks such that gradient descent could be applied. The four function blocks used in this experiment are as follows.
IDENTITY(x) = x NOT(x) = 1− x
AND(x, y) = x× y OR(x, y) = x+ y − x× y
The first two are unitary operations and the last two are binary. Therefore, the number of unitary functions m = 2 and the number of binary functions n = 2. We used these functions multiple times by duplicating them. Hence, the number of functions was set to m + n ∈ {12, 16, 20} and the number of layers L ∈ {3, 4, 5, 6} was selected in our experiment. The initial L1 regularization parameter α was set to α ∈ {0.1, 0.5, 1, 5}. We prepared a multilayered artificial neural network (ANN) and support vector regression (SVR) to compare with our model. For the ANN, the number of layers were set as that of our model and the number of hidden units k ∈ {5, 10, 20} per layer. For SVR, we used a radial basis function kernel of width γ ∈ {0.05, 0.1, 0.5, 1.0} and set two hyperparameters C ∈ {0.01, 0.1, 1, 10, 100} and ∈ {0.01, 0.1, 1}. Although comparing losses is not meaningful as our model not only reduces the error, but also obtains the actual structure of the target function, it clearly shows how our model effectively reduces the loss after obtaining the structure of the target function.
Three samples of LLDs suggested by our model are shown in Figure 4. (a) is a sample from LLD1, which is equivalent to LLD1. Two equivalent LLDs imply that, for every possible input signal, the corresponding output signals from two LLDs are the same. Therefore, we verified that the WBN may not suggest the exact diagram but an equivalent diagram (it sometimes produces the exact LLD). (b) is another sample of LLD1 that is also equivalent to LLD1. We discovered that if we set the number of layers larger than the required number, the WBN will likely generate an inefficient LLD. (b) is a sample of LLD2; it is equivalent to LLD2. Both y1 and y2 cannot be obtained efficiently using this diagram. However, it is clear that y3 is of a simpler form than the original LLD2; additionally, it is equivalent to real y3 in LLD2 because NOT(y2) and x1 cannot occur simultaneously. We included more samples of LLDs including samples from LLD3 in the Appendix. See Figure 7

heading: 4.2 BINARY MNIST CLASSIFICATION

text:
We performed experiments to verify the end-to-end PathNet structure. We used the selection matrix instead of the genetic algorithm, which is different from the original PathNet. Experiments were conducted to determine whether the selection matrix could select the appropriate path. We performed the experiments using the transfer learning paradigm suggested in the original PathNet and observed a positive transfer by using our network. A binary MNIST classification is a task distinguishing two classes of MNIST digits from each other. In our experiment, we conducted two tasks for the transfer learning paradigm. First, we trained binary classification task A until we obtained a 0.998 training accuracy. After we achieved the accuracy, we set the best-fit pathway, that is, the parameters within the pathway were no longer allowed to change. Subsequently, we initialized the remaining parameters including the last linear layer and trained another binary classification task B until we obtained a 0.998 training accuracy. In this experiment, we adopted the original PathNet structure to construct our model. The end-toend PathNet structure comprises L = 3 layers; each layer contains M = 10 linear units with 20 neurons each followed by rectified linear units. We set N = 3 as the maximum number of distinct modules permissible in a pathway for each layer. We created two different datasets for transfer learning. One is for transferring from classifying 1 and 3 to classifying 7 and 8 (1vs3 to 7vs8). The other is for transferring from classifying 4 and 7 to classifying 2 and 5 (4vs7 to 2vs5). We created these datasets because, in our opinion, transferring 1vs3 to 7vs8 is more reasonable than transferring 4vs7 to 2vs5 because 1, 4, 7 are numbers with only straight lines, whereas 2, 5 , 8 are numbers with curved lines. We expect that the model that is learned to classify 1 and 3 can classify 7 and 8 easily after a transfer. The experiment was performed 500 times for each dataset to analyze the statistics.
Figure 5 shows the results of a positive transfer. For classifying 7 and 8, the number of generations to obtain a 0.998 training accuracy was 49.728 and 42.112 on average before and after transfer, respectively. The speed-up ratio was 1.18 for this dataset. For classifying 2 and 5, the number of generations to obtain a 0.998 training accuracy was 55.324 and 48.808 on average before and after transfer, respectively. The speed-up ratio was 1.13 for this dataset. We discovered that the learning speed of the task enhanced for both datasets. Furthermore, it is clear that the transfer from 1vs3 to 7vs8 is better than that of the other by comparing the speed-up ratios. This implies that the selection matrix successfully discovered the best way pathway to transfer. The loss decreases quickly at the early stage of the training for the post-transferred task compared with the nontransferred task. See Figure 9 in appendix.

heading: 4.3 CIFAR CLASSIFICATION

text:
The CIFAR10 dataset contains images from 10 different classes. We performed an experiment using this dataset to determine whether our network could be used for classification problems. In the original PathNet study, a similar experiment was performed, in which information was transferred between CIFAR and SVHN datasets. One is for the classification of 10 different objects and the other that of 10 different digits. In our opinion, using two dataset are not suitable for transfer learning as
they need to focus on different items when classifying them. Therefore, we divided the CIFAR dataset into two classes: class 1, which comprises data from airplanes, automobiles, birds, cats, and deer; and class 2, which comprises data from dogs, frogs, horses, ships, and trucks. In our experiment, we used a transfer paradigm similar to that of the previous experiment. However, we trained the task according to a fixed iteration number instead of obtaining a certain accuracy. We trained one class 5000 times and then fixed the best-fit pathway. Subsequently, we initialized the remaining parameters and trained the other class 5000 times to verify the accuracy with their test sets. The end-to-end PathNet structure we used comprises L = 3 layers; each layer contains M = 16 linear units with 20 neurons each followed by rectified linear units. We set N = 4 as the maximum number of distinct modules permissible in a pathway for each layer.
Figure 6 shows the results of a positive transfer in the experiment. We conducted the experiment 500 times for each task and obtained the test accuracy. The test accuracy enhanced after a transfer was performed for both classes. For the first class, the total accuracy increased from 51.28% to 52.42% on average; for the second class, the total accuracy increased from 58.50% to 59.73% on average. Furthermore, we verified that the task was learned quickly at the early stage of the training for the post-transferred task compared with the nontransferred task. See Figure 10-(a), (b) in appendix.

heading: 5 CONCLUSION

text: We presented a new model called the WBN, which obtains the exact order and correct inputs of function blocks to compose them for constructing target functions. It is especially suitable for reverse engineering, e.g., for revealing PLC devices. It is different from other neural networks as it not only approximates a target function, but also constructs and reveals its structure. The WBN is differentiable with a discretized variable-named selection matrix; therefore, gradient descent can be used for its training. We used the L1 regularization with a variable parameter in temperature learning during training to optimize our network. Using this network, we discovered that it could reveal LLDs in devices, e.g., logic devices such as PLCs. This network provides the target logic, which may be helpful in auto-reverse engineering for reconstructing PLC-like devices. A WBN provides an equivalent logic rather than an exact one. Furthermore, we discovered that if the layer was set too large, then a WBN may yield an inefficient logic. This will be investigated in future studies. Additionally, we created another structure to verify the efficacy of the selection layer. Assuming that the function blocks were not known, we created an end-to-end PathNet structure using the selection layers. We performed a few experiments using this network and the transfer learning paradigm; consequently, positive transfer results were shown. This demonstrated that the selection layer could successfully select networks or functions during training. However, the hyperparameters and their scales must be investigated. The efficient initial regularization parameter and temperature based on the data scale remain unclear. This will be investigated in future studies as it is an important topic.

heading: A APPENDIX

title: WHITE BOX NETWORK: OBTAINING A RIGHT COMPOSITION ORDERING OF FUNCTIONS