summaries: The paper proposes an imitation learning method that aims to align state distributions rather than state-action distributions to account for cases where the imitator dynamics differ from expert dynamics. They achieve this by two objectives: one local, the other global. The local objective aligns the next state to be close to the expert's next state in each transition by first training a VAE on the expert demonstrations, and using the trained VAE in conjunction with a pretrained inverse dynamics model to compute the action that the imitator needs to imitate. The global objective tries to do a global alignment of states encountered in the imitator and expert trajectories, by minimizing the Wasserstein distance between the two trajectory distributions. The paper claims that using these two objectives results in a method that outperforms existing inverse reinforcement learning and behavior cloning approaches in settings where the imitator and expert dynamics differ.

summaries: This paper seeks a solution to the problem of performing imitation learning when the dynamics of the demonstrator are different from the dynamics of the imitator. The authors present a novel approach that combines global alignment by minimizing the Wasserstein distance between state occupancies with local alignment via a state-predictive VAE and inverse dynamics model. The experimental results support the claims that the method works for different dynamics and the proposed approach usually outperforms existing imitation learning methods.

abstractText: Consider an imitation learning problem that the imitator and the expert have different dynamics models. Most of the current imitation learning methods fail because they focus on imitating actions. We propose a novel state alignment based imitation learning method to train the imitator to follow the state sequences in expert demonstrations as much as possible. The state alignment comes from both local and global perspectives and we combine them into a reinforcement learning framework by a regularized policy update objective. We show the superiority of our method on standard imitation learning settings and imitation learning settings where the expert and imitator have different dynamics models.

authors:
Martin Arjovsky
Soumith Chintala
Léon Bottou

title: Wasserstein gan

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

authors:
Yusuf Aytar
Tobias Pfaff
David Budden
Thomas Paine
Ziyu Wang
Nando de Freitas

title: Playing hard exploration games by watching youtube

venue: In Advances in Neural Information Processing Systems,

authors:
Michael Bain
Claude Sommut

title: A framework for behavioural cloning

venue: Machine intelligence,

authors:
Lionel Blondé
Alexandros Kalousis

title: Sample-efficient imitation learning via generative adversarial nets

venue: arXiv preprint arXiv:1809.02064,

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

title: Isolating sources of disentanglement in variational autoencoders

authors:
Bin Dai
Yu Wang
John Aston
Gang Hua
David Wipf

title: Connections with robust pca and the role of emergent sparsity in variational autoencoder models

venue: The Journal of Machine Learning Research,

authors:
Ashley D Edwards
Himanshu Sahni
Yannick Schroecker
Charles L Isbell

title: Imitating latent policies from observation

venue: arXiv preprint arXiv:1805.07914,

authors:
Justin Fu
Katie Luo
Sergey Levine

title: Learning robust rewards with adversarial inverse reinforcement learning

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

title: Generative adversarial nets

venue: In Advances in neural information processing systems,

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

title: Improved training of wasserstein gans

authors:
Tuomas Haarnoja
Aurick Zhou
Pieter Abbeel
Sergey Levine

title: Soft actor-critic: Offpolicy maximum entropy deep reinforcement learning with a stochastic actor

venue: arXiv preprint arXiv:1801.01290,

authors:
Todd Hester
Matej Vecerik
Olivier Pietquin
Marc Lanctot
Tom Schaul
Bilal Piot
Dan Horgan
John Quan
Andrew Sendonaris
Ian Osband

title: Deep q-learning from demonstrations

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

authors:
Jonathan Ho
Stefano Ermon

title: Generative adversarial imitation learning

authors:
Liyiming Ke
Matt Barnes
Wen Sun
Gilwoo Lee
Sanjiban Choudhury
Siddhartha Srinivasa

title: Imitation learning as f -divergence minimization

authors:
Diederik P Kingma
Max Welling

title: Auto-encoding variational bayes

venue: arXiv preprint arXiv:1312.6114,

authors:
Hoang M Le
Yisong Yue
Peter Carr
Patrick Lucey

title: Coordinated multi-agent imitation learning

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

authors:
Lisa Lee
Benjamin Eysenbach
Emilio Parisotto
Eric Xing
Sergey Levine
Ruslan Salakhutdinov

title: Efficient exploration via state marginal matching

authors:
YuXuan Liu
Abhishek Gupta
Pieter Abbeel
Sergey Levine

title: Imitation from observation: Learning to imitate behaviors from raw video via context translation

venue: IEEE International Conference on Robotics and Automation (ICRA),

authors:
Ofir Nachum
Shixiang Gu
Honglak Lee
Sergey Levine

title: Near-optimal representation learning for hierarchical reinforcement learning

venue: arXiv preprint arXiv:1810.01257,

authors:
Ofir Nachum
Shixiang Shane Gu
Honglak Lee
Sergey Levine

title: Data-efficient hierarchical reinforcement learning

authors:
Andrew Y Ng
Stuart J Russell

title: Algorithms for inverse reinforcement learning

venue: In Icml,

authors:
Sebastian Nowozin
Botond Cseke
Ryota Tomioka

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

authors:
Deepak Pathak
Parsa Mahmoudieh
Michael Luo
Pulkit Agrawal
Dian Chen
Fred Shentu
Evan Shelhamer
Jitendra Malik
Alexei A Efros
Trevor Darrell

title: Zero-shot visual imitation

venue: international conference on learning representations,

authors:
Xue Bin Peng
Angjoo Kanazawa
Jitendra Malik
Pieter Abbeel
Sergey Levine

title: Sfv: Reinforcement learning of physical skills from videos

venue: ACM Trans. Graph.,

authors:
Tobias Pohlen
Bilal Piot
Todd Hester
Mohammad Gheshlaghi Azar
Dan Horgan
David Budden
Gabriel Barth-Maron
Hado van Hasselt
John Quan
Mel Večerı́k

title: Observe and look further: Achieving consistent performance on atari

venue: arXiv preprint arXiv:1805.11593,

title: Alvinn: An autonomous land vehicle in a neural network

authors:
Ahmed H Qureshi
Byron Boots
Michael C Yip

title: Adversarial imitation via variational inverse reinforcement learning

venue: arXiv preprint arXiv:1809.06404,

authors:
Danilo Jimenez Rezende
Shakir Mohamed
Daan Wierstra

title: Stochastic backpropagation and approximate inference in deep generative models

venue: arXiv preprint arXiv:1401.4082,

authors:
Stéphane Ross
Drew Bagnell

title: Efficient reductions for imitation learning

venue: In Proceedings of the thirteenth international conference on artificial intelligence and statistics,

authors:
Stéphane Ross
Geoffrey Gordon
Drew Bagnell

title: A reduction of imitation learning and structured prediction to no-regret online learning

venue: In Proceedings of the fourteenth international conference on artificial intelligence and statistics,

title: Learning agents for uncertain environments

venue: In COLT,

authors:
Yannick Schroecker
Charles L Isbell

title: State aware imitation learning

authors:
John Schulman
Sergey Levine
Pieter Abbeel
Michael Jordan
Philipp Moritz

title: Trust region policy optimization

venue: In International Conference on Machine Learning,

authors:
John Schulman
Filip Wolski
Prafulla Dhariwal
Alec Radford
Oleg Klimov

title: Proximal policy optimization algorithms

venue: arXiv preprint arXiv:1707.06347,

title: Optimal transport on discrete domains

venue: AMS Short Course on Discrete Differential Geometry,

authors:
Wen Sun
Anirudh Vemula
Byron Boots
J Andrew Bagnell

title: Provably efficient imitation learning from observation alone

venue: arXiv preprint arXiv:1905.10948,

authors:
Emanuel Todorov
Tom Erez
Yuval Tassa

title: Mujoco: A physics engine for model-based control

venue: In 2012 IEEE/RSJ International Conference on Intelligent Robots and Systems,

authors:
Faraz Torabi
Garrett Warnell
Peter Stone

title: Generative adversarial imitation from observation

venue: arXiv preprint arXiv:1807.06158,

title: Behavioral cloning from observation

venue: arXiv preprint arXiv:1805.01954,

title: Optimal transport: old and new, volume 338

venue: Springer Science & Business Media,

authors:
Huang Xiao
Michael Herman
Joerg Wagner
Sebastian Ziesche
Jalal Etesami
Thai Hong Linh

title: Wasserstein adversarial imitation learning

authors:
Gu Ye
Ron Alterovitz

title: Guided motion planning

venue: In Robotics research,

authors:
Brian D Ziebart
Andrew Maas
J Andrew Bagnell
Anind K Dey

title: Maximum entropy inverse reinforcement learning

heading: 1 INTRODUCTION

text:
Learning from demonstrations (imitation learning, abbr. as IL) is a basic strategy to train agents for solving complicated tasks. Imitation learning methods can be generally divided into two categories: behavior cloning (BC) and inverse reinforcement learning (IRL). Behavior cloning (Ross et al., 2011b) formulates a supervised learning problem to learn a policy that maps states to actions using demonstration trajectories. Inverse reinforcement learning (Russell, 1998; Ng et al., 2000) tries to find a proper reward function that can induce the given demonstration trajectories. GAIL (Ho & Ermon, 2016) and its variants (Fu et al.; Qureshi et al., 2018; Xiao et al., 2019) are the recently proposed IRL-based methods, which uses a GAN-based reward to align the distribution of stateaction pairs between the expert and the imitator.
Although state-of-the-art BC and IRL methods have demonstrated compelling performance in standard imitation learning settings, e.g. control tasks (Ho & Ermon, 2016; Fu et al.; Qureshi et al., 2018; Xiao et al., 2019) and video games (Aytar et al., 2018b), these approaches are developed based on a strong assumption: the expert and the imitator share the same dynamics model; specifically, they have the same action space, and any feasible state-action pair leads to the same next state in probability for both agents. The assumption brings severe limitation in practical scenarios: Imagine that a robot with a low speed limit navigates through a maze by imitating another robot which moves fast, then, it is impossible for the slow robot to execute the exact actions as the fast robot. However, the demonstration from the fast robot should still be useful because it shows the path to go through the maze.
We are interested in the imitation learning problem under a relaxed assumption: Given an imitator that shares the same state space with the expert but their dynamics may be different, we train the imitator to follow the state sequence in expert demonstrations as much as possible. This is a more general formulation since it poses fewer requirements on the experts and makes demonstration collection easier. Due to the dynamics mismatch, the imitator becomes more likely to deviate from the demonstrations compared with the traditional imitation learning setting. Therefore, it is very important that the imitator should be able to resume to the demonstration trajectory by itself. Note that neither BC-based methods nor GAIL-based IRL methods have learned to handle dynamics misalignment and deviation correction.
To address the issues, we propose a novel approach with four main features: 1) State-based. Compared to the majority of literature in imitation learning, our approach is state-based rather than action-based. Not like BC and IRL that essentially match state-action pairs between the expert and the imitator, we only match states. An inverse model of the imitator dynamics is learned to recover the action; 2) Deviation Correction. A state-based β-VAE (Higgins et al., 2017) is learned as the prior for the next state to visit. Compared with ordinary behavior cloning, this VAE-based next state predictor can advise the imitator to return to the demonstration trajectory when it deviates. The
robustness benefits from VAE’s latent stochastic sampling; 3) Global State Alignment. While the VAE can help the agent to correct its trajectory to some extent, the agent may still occasionally enter states that are far away from demonstrations, where the VAE has no clue how to correct it. So we have to add a global constraint to align the states in demonstration and imitation. Inspired by GAIL that uses reward to align the distribution of state-action pairs, we also formulate an IRL problem whose maximal cumulative reward is the Wasserstein Distance between states of demonstration and imitation. Note that we choose not to involve state-action pairs as in GAIL(Ho & Ermon, 2016), or state-state pairs as in an observation-based GAIL (Torabi et al., 2018a), because our state-only formulation imposes weaker constraints than the two above options, thus providing more flexibility to handle different agent dynamics; 4) Regularized Policy Update. We combine the prior for next state learned from VAE and the Wasserstein distance-based global constraint from IRL in a unified framework, by imposing a Kullback-Leibler divergence based regularizer to the policy update in the Proximal Policy Optimization algorithm.
To empirically justify our ideas, we conduct experiments in two different settings. We first show that our approach can achieve similar or better results on the standard imitation learning setting, which assumes the same dynamics between the expert and the imitator. We then evaluate our approach in the more challenging setting that the dynamics of the expert and the imitator are different. In a number of control tasks, we either change the physics properties of the imitators or cripple them by changing their geometries. Existing approaches either fail or can only achieve very low rewards, but our approach can still exhibit decent performance. Finally, we show that even for imitation across agents of completely different actuators, it is still possible for the state-alignment based method to work. Surprisingly, a point mass and an ant in MuJoCo (Todorov et al., 2012) can imitate each other to navigate in a maze environment.
Our contributions can be summarized as follows: • Propose to use a state alignment based method in the imitation learning problems where
the expert’s and the imitator’s dynamics are different. • Propose a local state alignment method based on β-VAE and a global state alignment
method based on Wasserstein distance. • Combine the local alignment and global alignment components into a reinforcement learn-
ing framework by a regularized policy update objective.

heading: 2 RELATED WORK

text:
Imitation learning is widely used in solving complicated tasks where pure reinforcement learning might suffer from high sample complexity, like robotics control (Le et al., 2017; Ye & Alterovitz, 2017; Pathak et al., 2018), autonomous vehicle (Fu et al.; Pomerleau, 1989), and playing video game (Hester et al., 2018; Pohlen et al., 2018; Aytar et al., 2018a). Behavioral cloning (Bain & Sommut, 1999) is a straight-forward method to learn a policy in a supervised way. However, behavioral cloning suffers from the problem of compounding errors as shown by (Ross & Bagnell, 2010), and this can be somewhat alleviated by interactive learning, such as DAGGER (Ross et al., 2011b). Another important line in imitation learning is inverse reinforcement learning (Russell, 1998; Ng et al., 2000; Abbeel & Ng, 2004; Ziebart et al., 2008; Fu et al.), which finds a cost function under which the expert is uniquely optimal.
Since IRL can be connected to min-max formulations, works like GAIL, SAM (Ho & Ermon, 2016; Blondé & Kalousis, 2018) utilize this to directly recover policies. Its connections with GANs (Goodfellow et al., 2014) also lead to f -divergence minimization (Ke et al., 2019; Nowozin et al., 2016) and Wasserstein distance minimization (Xiao et al., 2019). One can also extend the framework from matching state-action pairs to state distribution matching, such as Torabi et al. (2018a); Sun et al. (2019); Schroecker & Isbell (2017). Other works (Aytar et al., 2018b; Liu et al., 2018; Peng et al., 2018) also learn from observation alone, by defining reward on state and using IRL to solve the tasks. Works like (Lee et al., 2019; Lee et al.) also use state-based reward for exploration. Torabi et al. (2018b); Edwards et al. (2018) will recover actions from observations by learning an inverse model or latent actions. However, our work aims to combine the advantage of global state distribution matching and local state transition alignment, which combines the advantage of BC and IRL through a novel framework.

heading: 3 BACKGROUNDS

text:
Variational Autoencoders Kingma & Welling (2013); Rezende et al. (2014) provides a framework to learn both a probabilistic generative model pθ(x|z) as well as an approximated posterior
distribution qφ(z|x). β-VAE is a variant VAE that introduces an adjustable hyperparameter β to the original objective:
L(θ, φ;x, z, β) = Eqφ(z|x) [log pθ(x|z)]− βDKL (qφ(z|x)‖p(z)) (1)
Larger β will penalize the total correlation (Chen et al., 2018) to encourage more disentangled latent representations, while smaller β often results in sharper and more precise reconstructions.
Wasserstein distance The Wasserstein distance between two density functions p(x) and q(x) with support on a compact metric space (M,d) has an alternative form due to Kantorovich-Rubenstein duality (Villani, 2008):
W(p, q) = sup φ∈L1 Ep(x)[φ(x)]− Eq(x)[φ(x)] (2)
Here, L1 is the set of all 1-Lipschitz functions from M to R. Compared with the prevalent KLdivergence and its extension, the f-divergence family, Wasserstein distance has a number of advantages theoretically and numerically. Please refer to Arjovsky et al. (2017) and Solomon (2018) for a detailed discussion.
4 SAIL: STATE ALIGNMENT BASED IMITATION LEARNING
4.1 OVERVIEW
Our imitation learning method is based on state alignment from both local and global perspectives. For local alignment, the goal is to follow the transition of the demonstration as much as possible, and allow the return to the demonstration trajectory whenever the imitation deviates. To achieve both goals, we use a βVAE (Higgins et al., 2017) to generate the next state (Figure 2 Left). For global alignment, we set up an objective to minimize the Wasserstein distance between the states in the current trajectory and the demonstrations (Figure 2 Right). There has to be a framework to naturally combine the local alignment and global alignment components. We resort to the reinforcement learning framework by encoding the local alignment as policy prior and encoding the global alignment as reward over states. Using Proximal Policy Optimization (PPO) by Schulman et al. (2017) as the backbone
RL solver, we derive a regularized policy update. To maximally exploit the knowledge from demonstrations and reduce interactions with the environment, we adopt a pre-training stage to produce a good initialization based on the same policy prior induced by the local alignment. Our method is summarized in Algorithm 1. In the rest parts of this section, we will introduce all the components of our method in details.

heading: 4.2 LOCAL ALIGNMENT BY STATE PREDICTIVE VAE

text:
To align the transition of states locally, we need a predictive model to generate the next state which the agent should target at. And then we can train an inverse dynamics model to recover the cor-
Algorithm 1 SAIL: State Alignment based Imitation Learning Require: Expert trajectories τe : [s1, a1, s2, a2, ...] ∼ πe, initial policy π, inverse dynamics model
g, discriminator φ, total episode T , memory capacity S 1: if Imitator and Expert have the same dynamics model then 2: Pre-train g using τe and transitions collected by a random policy 3: else 4: Pre-train g using transitions collected by a random policy 5: end if 6: Pre-train VAE using τe, and obtain the policy prior . Pre-train VAE and obtain policy prior 7: Pretrain π using policy prior as described in Sec 4.5 8: while episode ≤ T do 9: while |τ | ≤ S do . τ is the collected trajectories 10: Collect trajectory {(s, a, s′, r, done)} using π 11: Update r using (4) 12: Add {(s, a, s′, r, done)} to τ 13: end while 14: Train φ using maxφ∈L1 Es∼τe [φ(s)]− Es∼τ [φ(s)] . Calculate Wasserstein Distance 15: Update inverse dynamics model g 16: Update policy using (5) 17: end while
responding action, so as to provide a direct supervision for policy. It is worth-noting that, while training an inverse dynamics model is generally challenging, it is not so hard if we only focus on the agent dynamics, especially when the low-dimensional control states are accessible as in many practical scenarios. The problem of how to learn high-quality inverse/forward dynamics models is an active research topic.
Instead of using an ordinary network to memorize the subsequent states, which will suffer from the same issue of compounding errors as behavioral cloning (Ross & Bagnell, 2010; Ross et al., 2011a), we propose to use VAE to generate the next state based on the following two reasons. First, as shown in (Dai et al., 2018), VAE is more robust to outliers and regularize itself to find the support set of a data manifold, so it will generalize better for unseen data. Second, because of the latent stochastic sampling, the local neighborhood of a data point will have almost the same prediction, which is self-correctable when combined with a precise inverse dynamics model as illustrated in Figure 1.
We can also use a VAE to generate action based on the current state. But if the agent deviated from the demonstration trajectory a little bit, this predicted action is not necessarily guide the agent back to the trajectory, as shown in Figure 1. And in Sec 5.3.2, we conduct experiments to compare the state predictive VAE and the action predictive VAE.
Instead of the vanilla VAE, we use β-VAE to balance the KL penalty and prediction error, with formulation shown in (1). In Sec 5, we discuss the effects of the hyper-parameter β in different experiment settings as one of the ablation studies.

heading: 4.3 GLOBAL ALIGNMENT BY WASSERSTEIN DISTANCE

text:
Due to the difference of dynamics between the expert and the imitator, the VAE-based local alignment cannot fully prevent the imitator from deviating from demonstrations. In such circumstances, we still need to assess whether the imitator is making progress in learning from the demonstrations. We, therefore, seek to control the difference between the state visitation distribution of the demonstration and imitator trajectories, which is a global constraint.
Note that using this global constraint alone will not induce policies that follow from the demonstration. Consider the simple case of learning an imitator from experts of the same dynamics. The expert takes cyclic actions. If the expert runs for 100 cycles with a high velocity and the imitator runs for only 10 cycles with a low velocity within the same time span, their state distribution would still roughly align. That is why existing work such as GAIL aligns state-action occupancy measure. However, as shown later, our state-based distribution matching will be combined with the local alignment component, which will naturally resolve this issue. The advantage of this state-based distribution matching over state-action pair matching as in GAIL or state-next-state pair matching in (Torabi et al., 2018a) is that the constraint becomes loosened.
We use IRL approach to achieve the state distribution matching by introducing a reinforcement learning problem. Our task is to design the reward to train an imitator that matches the state distribution of the expert.
Before introducing the reward design, we first explain the computation of the Wasserstein distance between the expert trajectories {τe} and imitator trajectory {τ} using the Kantorovich duality:
W(τe, τ) = sup φ∈L1 Es∼τe [φ(s)]− Es∼τ [φ(s)] (3)
where φ is the Kantorovich’s potential, and serves as the discriminator in WGAN (Arjovsky et al., 2017). φ is trained with a gradient penalty term as WGAN-GP introduced in (Gulrajani et al., 2017)
After the rollout of imitator policy is obtained, the potential φ will be updated by (3). Assume a transition among an imitation policy rollout of length T is (si, si+1). To provide a dense signal every timestep, we assign the reward as:
r(si, si+1) = 1
T [φ(si+1)− Es∼τeφ(s)] (4)
We now explain the intuition of the above reward. By solving (3), those states of higher probability in demonstration will have a larger φ value. The reward in (4) will thus encourage the imitator to visit such states.
Maximizing the curriculum reward will be equivalent to
J(π) = T∑ t=1 Est,st+1∼π[r(st, st+1)] = T∑ t=1 Est+1 [φ(st+1)− Es∼τe [φ(s)]] T = −W(τe, τ)
In other words, the optimal policy of this MDP best matches the state visitation distributions w.r.t Wasserstein distance.
Compared with AIRL (Fu et al.) that also defines rewards on states only, our approach indeed enjoys certain advantages in certain cases. We provide a theoretical justification in the Appendix D.

heading: 4.4 REGULARIZED PPO POLICY UPDATE OBJECTIVE

text:
As mentioned in the second paragraph of Sec 4.3, the global alignment has to be combined with local alignment. This is achieved by adding a prior to the original clipped PPO objective.
We maximize the following unified objective function:
J(πθ) = L CLIP (θ)− λDKL ( πθ(·|st) ∥∥∥ pa) (5) We will explain the two terms in detail. LCLIP (θ) denotes the clipped surrogate objective used in the original PPO algorithm:
LCLIP (θ) = Êt [ min ( πθ(a|s) πθold(a|s) Ât, clip ( πθ(a|s) πθold(a|s) , 1− , 1 + ) Ât )] , (6)
where Ât is an estimator of the advantage function at timestep t. The advantage function is calculated based on a reward function described in Sec 4.3.
TheDKL term in (5) serves as a regularizer to keep the policy close to a learned policy prior pa. This policy prior pa is derived from the state predictive VAE and an inverse dynamics model. Assume the β-VAE is f(st) = st+1 and the inverse dynamics model is ginv(st, st+1) = a. To solve the case when the agents have different dynamics, we learn a state prediction network and use a learned inverse dynamics to decode the action. We define the action prior as
pa(at|st) ∝ exp ( − ∥∥∥ginv(st, f(st))− at
σ ∥∥∥2) (7) where the RHS is a pre-defined policy prior, a Gaussian distribution centered at ginv(st, f(st)). σ controls how strong the action prior is when regularizing the policy update, which is a hyperparameter. Note that the inverse model can be further adjusted during interactions.
LCLIP is computed through the advantage Ât and reflects the global alignment. The policy prior is obtained from the inverse model and local β-VAE, which makes the DKL serve as a local alignment constraint. Furthermore, our method can be regard as a combination of BC and IRL because our KLdivergence based action prior encodes the BC policy and we update the policy leveraging reward.
We would note that our state-alignment method augments state distribution matching by taking relationships of two consecutive states into account with robustness concern.

heading: 4.5 PRE-TRAINING

text: We pretrain the state predictive VAE and the inverse dynamics model, and then obtain the policy prior in (7), which is a Gaussian distribution. For pre-training, we want to initialize PPO’s Gaussian policy π by this prior pa, by minimizing the KL-divergence between them. Practically, we use direct supervision from ginv(st, f(st)) and σ in (7) to directly train both the mean and variance of the policy network, which is more efficient during the pre-training stage. During the online interaction, the update rule of PPO’s policy is by optimizing (5), and the variance will be further adjusted for all the dimensions of the action space.

heading: 5 EXPERIMENTS

text: We conduct two different kinds of experiments to show the superiority of our method. In Sec 5.1, we compare our method with behavior cloning (Bain & Sommut, 1999), GAIL (Ho & Ermon, 2016), and AIRL (Fu et al.) in control setting where the expert and the imitator have different dynamics model, e.g., both of them are ant robots but the imitator has shorter legs. In Sec 5.1, we further evaluate in the traditional imitation learning setting. Finally, in Sec 5.3, we conduct ablation study to show the contribution of the components.

heading: 5.1 IMITATION LEARNING ACROSS AGENTS OF DIFFERENT ACTION DYNAMICS

heading: 5.1.1 ACTORS OF MODIFIED PHYSICS AND GEOMETRY PROPERTIES

text:
We create environments using MuJoCo (Todorov et al., 2012) by changing some properties of experts, such as density and geometry of the body. We choose 2 environments, Ant and Swimmer, and augment them to 6 different environments: Heavy/Light/Disabled Ant/Swimmer. The Heavy/Light agents have modified density, and the disabled agents have modified head/tail/leg lengths. The demonstrations are collected from the standard Ant-v2 and Swimmer-v2. More descriptions of the environments and the demonstration collection process can be founded in the Appendix.
We then evaluate our method on them.
Figure 3 demonstrates the superiority of our methods over all the baselines. Our approach is the most stable in all the 6 environments and shows the leading performance in each of them. GAIL seems to be the most sensitive to dynamics difference. AIRL, which is designed to solve imitation learning for actors of different dynamics, can perform on par with our method in two swimmerbased environments (DisabledSwimmer and HeavySwimmer) that have relatively lower dimensional action space (2D for swimmer versus 8D for ants).
Interestingly, the stability and performance of vanilla behavior cloning are quite reasonable in 4 of the environments, although it failed to move about in the DisabledAnt and HeavyAnt environments. For these two tasks, the agent will reach dangerous states by cloning actions, yet our method will not approach these states by using state-based imitation. In the other four games, BC agents do not die but just move less efficiently, so they have a sub-optimal yet still reasonable score. 1

heading: 5.1.2 ACTORS OF HETEROGENEOUS ACTION DYNAMICS

text:
We consider an extremely challenging setting that the imitator and demonstrator are functionally different. One typical example of expert/imitator pair in practice would be a human and a humanoid robot. We consider a much simplified version but with similar nature – a Point and an Ant in MuJoCo. In this task, even if the state space cannot be exactly matched, there are still some shared dimensions across the state space of the imitator and the actor, e.g., the location of the center of mass, and the demonstration should still teach the imitator in these dimensions.
We use the same setting as many hierarchical RL papers, such as HIRO and Near-Optimal RL (Nachum et al., 2018a;b). The agent need to reach a goal position in a maze, which is represented by (x,y) coordinates. We also know that the first two dimensions of states are the position of the agent. The prior knowledge includes: (1) the goal space (or the common space that need to be matched) (2) the projection from the state space to the goal space (select the first two dimensions of the states).
The first task is that the Ant should reach the other side of the maze from several successful demonstrations of a Point robot. As shown in Figure 4(c) and Figure 4(d), the maze structure for the ant and point mass is exactly the same.
To solve this problem, we first pre-train an VAE on the demonstrations, and use this VAE to propose the next “subgoal” for the Ant. This VAE is trained on the goal space (i.e. the first two dimensions) of the Point robot’s trajectory. Then we train an inverse model for Ant, which will generate an action based on the Ant’s current state (high dimensional) and goal predicted by VAE (2 dimensional).
Our performance is shown in Figure 5(c). After 1M training steps, the agent has success rate of 0.8 to reach the other side of the maze.

heading: 5.2 ACTORS OF THE SAME DYNAMICS (STANDARD IMITATION LEARNING)

text:
We also evaluate our algorithm on 6 non-trivial control tasks in MuJoCo: Swimmer, Hopper, Walker, Ant, HalfCheetach, and Humanoid. We first collect demonstration trajectories with Soft ActorCritic, which can learn policies that achieve high scores in most of these environments2. For com-
1For LightSwimmer 3(e), AIRL meets MuJoCo numerical exception for several trials. 2We collect near-optimal demonstration on Swimmer using TRPO due to the limited performance of SAC.
parison, we evaluate our method against 3 baselines: behavior cloning, GAIL, and AIRL3. Also, to create even stronger baselines for the cumulative reward and imitator run-time sample complexity, we initialize GAIL with behavior cloning, which would obtain higher scores in Swimmer and Walker. Lastly, to evaluate how much each algorithm depends on the amount of demonstrations, we sampled demonstration trajectories of ten and fifty episodes.
Table 1 depicts representative results in Hopper and HalfCheetah4. The advantage of our methods over BC should be attributed to the inherent data augmentation by VAE. On Hopper-v2, we are significantly better with 10 demos but are just on par if the demos are increased to 50. On HalfCheetah-v2, the demo cheetah runs almost perfectly ( 12294 scores); in other words, the demo provides limited instruction when the imitator is even slightly off the demo states, thus the robustness from VAE becomes critical.

heading: 5.3 ABLATION STUDY

text:
5.3.1 COEFFICIENT β IN β-VAE
β-VAE introduces an additional parameter to the original VAE. It controls the variance of the randomly sampled latent variable sampling, which subsequently affects the reconstruction quality and robustness. Theoretically, a smaller β leads to better state prediction quality, with the cost of losing the deviation correction ability (Dai et al., 2018).
To empirically show the role of beta and check the sensitivity of our algorithm with respect to beta, we evaluate VAE in settings of both the imitator has the same dynamics and has different dynamics. We select HalfCheetah-v2 and HeavyAnt as an example. For HalfCheetah-v2, we pretrain the inverse dynamics and VAE using given demonstrations so that the initial performance will tell the quality of the VAE’s prediction. For DisabledAnt, we pretrain the dynamics with random trials, which results in forward/inverse dynamics estimation of less accuracy. In this case, we examine both its initialized performance and final performance. The results are shown in Table 2. We find out that for β in [0.01, 0.1], the performance is better. Specifically, when the imitator is different from the expert, a smaller β will result in poor performance as it overfits the demonstration data.
We also compare our method with an ordinary MLP trained by MSE loss. We find out that VAE outperforms MLP in all settings. Note that the MLP-based approach is very similar to the state-based behavior cloning work of (Torabi et al., 2018b).
5.3.2 ACTION PREDICTIVE β-VAE
In Figure 1, we mentioned that a VAE to predict the next action is less favorable. To justify the claim, we compare a VAE-based BC with a vanilla BC that both predict actions, as shown in Table 3. Experiments show that VAE-BC is even outperformed by a vanilla BC, especially when β is larger than 0.001. Compared with the last line in Table 2, we can conclude that VAE is more useful when predicting state, which consolidates that the advantage really comes from our state-based approach but not only the robustness of VAE.

heading: 5.3.3 EFFECT OF WASSERSTEIN DISTANCE AND KL REGULARIZATION

text:
In our policy update process, we use Wasserstein distance with KL regularization to update the policy. To analyze their effects on the performance, we use HalfCheetah-v2 and Humanoid-v2 with
3AIRL and EAIRL(Qureshi et al., 2018) have similar performance, and we only compare to AIRL. 4Results for other environments can be founded in the Appendix.
20 expert trajectories. For each environment, they use the same pretrained inverse model and VAE, thus they have the same behavior after pretraining.
As shown in Figure 5(a)(b), Wasserstein distance combined with KL regularization performs the best. Wasserstein objective is used in our inverse RL based mechanism that would significantly penalize the exploration when the agent deviates from the demonstration far away. However, using this objective alone lacks constraints over consecutive states, thus performing the worst. The KL objective adds constraints over consecutive states using a VAE prior; however, VAE is unable to extrapolate to states when the imitator deviates far from the demo (green line gradually fails as in Fig 5 (b)), but this is the scenario when the Wasserstein distance would not favor, thus the reward from the Wasserstein distance will push the imitator back to the demonstration states.

heading: 6 CONCLUSION

text: We proposed SAIL, a flexible and practical imitation learning algorithms that use state alignment from both local and global perspective. We demonstrate the superiority of our method using MuJoCo environments, especially when the action dynamics are different from the demonstrations.

heading: A LEARNING ACROSS DIFFERENT ENVIRONMENTS

text:
PointMaze & AntMaze As shown in Figure 4, a point mass or an ant is put in a 24 × 24 U-maze. The task is to make the agent reach the other side of U-maze with the demonstration from the point mass. The ant is trained to reach a random goal in the maze from a random location, and should reach the other side of the maze. The state space of ant is 30-dim, which contains the positions and velocities.
HeavyAnt Two times of original Ant’s density. Two times of original gear of the armature.
LightAnt One tenth of original Ant’s density.
DisabledAnt Two front legs are 3 quarters of original Ant’s legs.
HeavySwimmer 2.5 times of original Swimmer’s density.
LightSwimmer One twentieth of original Swimmer’s density.
DisabledSwimmer Make the last joint 1.2 times longer and the first joint 0.7 times of the original length
The exact results of these environments are listed in Table 4, 5. All the statistics are calculated from 20 trails.
B IMITATION BENCHMARK EXPERIMENTS SETTINGS AND RESULTS
We use six MuJoCo (Todorov et al., 2012) control tasks. The name and version of the environments are listed in Table 6, which also list the state and action dimension of the tasks with expert performance and reward threshold to indicate the minimum score to solve the task. All the experts are trained by using SAC (Haarnoja et al., 2018) except Swimmer-v2 where TRPO (Schulman et al., 2015) get higher performance.
The exact performance of all methods are list in Table 7, 8, 9, 10, 11, 12. We compare GAIL(Ho & Ermon, 2016), behavior cloning, GAIL with behavior cloning initilization and AIRL to our method containing. Means and standard deviations are calculated from 20 trajectories after the agents converge and the number total interactions with environments is less than one million environment steps.

heading: C HYPER-PARAMETER AND NETWORK ARCHITECTURE

text: When we pretrain the policy network with our methods, we choose β = 0.05 in β-VAE. We use Adam with learning rate 3e-4 as the basic optimization algorithms for all the experiments. The policy network and value network used in the algorithms all use a three-layer relu network with hidden size 256. We choose σ = 0.1 in the policy prior for all the environments.

heading: D COMPARISON WITH AIRL (FU ET AL.) FROM A THEORETICAL PERSPECTIVE

text:
Here we illustrate the theoretical advantage of our SAIL algorithm over AIRL in certain scenarios by an example.
The theory of AIRL shows that it is able to recover the groundtruth reward of an MDP up to a constant if the reward of this MDP is define on states only, when the adversarial learning reaches the equilibrium. Next we show a basic case that violates the theoretical assumption of AIRL but can be solved by our algorithm.
Figure 6 shows the states and transition of an MDP. The demonstration policy jumps back and forth between s1 and s2 periodically. Because our algorithm has the action prior (local alignment), it is clear that we can solve this problem. The dynamics of many periodic games, such as Walker and HalfCheetah in MuJoco, are extension of this two-ring graph.
It is easy to show that it is impossible for the adversarial game in AIRL to solve this problem at equilibrium. According to Sec 6 of Fu et al., the reward family of AIRL is parameterized as
fθ(s, s ′) = g(s) + γh(s′)− h(s) (8)
For simplicity of notation, let φ(s) = g(s)− h(s) and ψ(s) = γh(s), then fθ(s, s ′) = φ(s) + ψ(s′) (9)
In other words, the reward of AIRL is decomposible to the sum of two functions defined on states only.
Again, for simplicity, we omit the arguments of functions but use subscripts to represent states. For example, f12 = f(s1, s2) and φ1 = φ(s1). Then,
f12 = φ1 + ψ2, f11 = φ1 + ψ1 f21 = φ2 + ψ1, f22 = φ2 + ψ2
(10)
Assume that AIRL has reached the equilibrium and learned the optimal policy, then it must be true that f12 > f11 and f21 > f22 (otherwise, there exists other optimal policies). But f12 > f11 implies that ψ2 > ψ1, while f21 > f22 implies that ψ1 > ψ2, which is a contradiction.

title: STATE ALIGNMENT-BASED IMITATION LEARNING


summaries: This paper propose an extention method of SGD, deep gradient boosting (DGB), which views the back-propagation procedure as a pseudo-residual targets of a gradient boosting problem. To apply DGB to the real CNNs, DGB is simplified to a input normalization layer, conditioned on the assumption that the convolution kernels should be small. After applying the input normalization layer to CNNs, the model could achieve comparable performance to the model with BN on CIFAR-10 and ImageNet recognition.

summaries: The paper proposes an a new idea of treating the back propagated gradients using chain rule as pseudo residual targets of a gradient boosting problem. Then the weight update is done by solving the boosting problem using a linear base learner. Furthermore, to reduce computational cost incurred by solving the boosting problem, an idea proposed is only keep the diagonal terms of the matrix inversion involved.

abstractText: Stochastic gradient descent (SGD) has been the dominant optimization method for training deep neural networks due to its many desirable properties. One of the more remarkable and least understood quality of SGD is that it generalizes relatively well on unseen data even when the neural network has millions of parameters. We hypothesize that in certain cases it is desirable to relax its intrinsic generalization properties and introduce an extension of SGD called deep gradient boosting (DGB). The key idea of DGB is that back-propagated gradients inferred using the chain rule can be viewed as pseudo-residual targets of a gradient boosting problem. Thus at each layer of a neural network the weight update is calculated by solving the corresponding boosting problem using a linear base learner. The resulting weight update formula can also be viewed as a normalization procedure of the data that arrives at each layer during the forward pass. When implemented as a separate input normalization layer (INN) the new architecture shows improved performance on image recognition tasks when compared to the same architecture without normalization layers. As opposed to batch normalization (BN), INN has no learnable parameters however it matches its performance on CIFAR10 and ImageNet classification tasks.

authors:
Pierre Baldi
Peter Sadowski
Daniel Whiteson

title: Searching for exotic particles in high-energy physics with deep learning

venue: Nature communications,

authors:
Johan Bjorck
Carla Gomes
Bart Selman
Kilian Q. Weinberger

title: Understanding batch normalization, 2018

title: Arcing classifier (with discussion and a rejoinder by the author)

venue: The annals of statistics,

authors:
Gustavo Camps-Valls
Josee L Rojo-Alvarez
Martin Martiinez-Ramon

title: Kernel methods in bioengineering, signal and image processing

venue: Idea Group Pub.,

authors:
Saverio De Vito
Ettore Massera
M Piga
L Martinotto
G Di Francia

title: On field calibration of an electronic nose for benzene estimation in an urban pollution monitoring scenario

venue: Sensors and Actuators B: Chemical,

authors:
Laurent Dinh
Razvan Pascanu
Samy Bengio
Yoshua Bengio

title: Sharp minima can generalize for deep nets

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

authors:
John Duchi
Elad Hazan
Yoram Singer

title: Adaptive subgradient methods for online learning and stochastic optimization

venue: Journal of Machine Learning Research,

authors:
Yoav Freund
Robert E Schapire

title: A decision-theoretic generalization of on-line learning and an application to boosting

venue: Journal of computer and system sciences,

title: Greedy function approximation: a gradient boosting machine

venue: Annals of statistics,

title: Generating sequences with recurrent neural networks

venue: arXiv preprint arXiv:1308.0850,

authors:
Kaiming He
Xiangyu Zhang
Shaoqing Ren
Jian Sun

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

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

title: Deep residual learning for image recognition

venue: IEEE Conference on Computer Vision and Pattern Recognition (CVPR), Jun 2016a. doi: 10.1109/cvpr.2016.90. URL http://dx.doi.org/10.1109/CVPR.2016.90

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

authors:
Sergey Ioffe
Christian Szegedy

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

authors:
Diederik P Kingma
Jimmy Ba

title: Adam: A method for stochastic optimization

venue: The International Conference on Learning Representations (ICLR),,

authors:
Alex Krizhevsky
Geoffrey Hinton

title: Learning multiple layers of features from tiny images

venue: Technical report, Citeseer,

authors:
Yann LeCun
Ido Kanter
Sara A Solla

title: Second order properties of error surfaces: Learning time and generalization

venue: In Advances in neural information processing systems,

authors:
Yann LeCun
Corinna Cortes
Christopher J.C. Burges

title: The mnist database of handwritten digits

authors:
Llew Mason
Jonathan Baxter
Peter L Bartlett
Marcus R Frean

title: Boosting algorithms as gradient descent

authors:
Vinod Nair
Geoffrey E Hinton

title: Rectified linear units improve restricted boltzmann machines

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

authors:
Herbert Robbins
Sutton Monro

title: A stochastic approximation method

venue: The annals of mathematical statistics,

authors:
Samuel Rota Bulò
Lorenzo Porzi
Peter Kontschieder

title: In-place activated batchnorm for memory-optimized training of dnns

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

authors:
David E Rumelhart
Geoffrey E Hinton
Ronald J Williams

title: Learning representations by back-propagating errors

venue: Cognitive modeling,

authors:
Karen Simonyan
Andrew Zisserman

title: Very deep convolutional networks for large-scale image recognition

venue: arXiv preprint arXiv:1409.1556,

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

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

venue: The Journal of Machine Learning Research,

title: Online at https: //neuton.ai/assets/archives/hr.zip

venue: Hr employee attrition and performance

authors:
Dmitry Ulyanov
Andrea Vedaldi
Victor Lempitsky

title: Instance normalization: The missing ingredient for fast stylization, 2016

title: Beyond regression: New tools for prediction and analysis in the behavioral sciences

venue: Harvard University,

authors:
Ashia C Wilson
Rebecca Roelofs
Mitchell Stern
Nati Srebro
Benjamin Recht

title: The marginal value of adaptive gradient methods in machine learning

venue: In Advances in Neural Information Processing Systems,

heading: 1 INTRODUCTION

text:
Boosting, along side deep learning, has been a very successful machine learning technique that consistently outperforms other methods on numerous data science challenges. In a nutshell, the basic idea of boosting is to sequentially combine many simple predictors in such a way that their combined performance is better than each individual predictor. Frequently, these so called weak learners are implemented as simple decision trees and one of the first successful embodiment of this idea was AdaBoost proposed by Freund & Schapire (1997). No too long after this, Breiman et al. (1998) and Friedman (2001) made the important observation that AdaBoost performs in fact a gradient descent in functional space and re-derived it as such. Friedman (2001) went on to define a general statistical framework for training boosting-like classifiers and regressors using arbitrary loss functions. Together with Mason et al. (2000) they showed that boosting minimizes a loss function by iteratively choosing a weak learner that approximately points in the negative gradient direction of a functional space.
Neural networks, in particular deep neural nets with many layers, are also trained using a form of gradient descent. Stochastic gradient descent (SGD) (Robbins & Monro, 1951) has been the main optimization method for deep neural nets due to its many desirable properties like good generalization error and ability to scale well with large data sets. At a basic level, neural networks are composed of stacked linear layers with differentiable non-linearities in between. The output of the last layer is then compared to a target value using a differentiable loss function. Training such a model using SGD involves updating the network parameters in the direction of the negative gradient of the loss function. The crucial step of this algorithm is calculating the parameter gradients and this is efficiently done by the backpropagation algorithm (Rumelhart et al., 1988; Werbos, 1974).
Backpropagation has many variations that try to achieve either faster convergence or better generalization through some form of regularization. However, despite superior training outcomes, accelerated optimization methods such as Adam (Kingma & Ba, 2015), Adagrad (Duchi et al., 2011) or RMSprop (Graves, 2013) have been found to generalize poorly compared to stochastic gradient
descent (Wilson et al., 2017). Therefore even before using an explicit regularization method, like dropout (Srivastava et al., 2014) or batch normalization (Ioffe & Szegedy, 2015), SGD shows very good performance on validation data sets when compared to other methods. The prevalent explanation for this empirical observation has been that SGD prefers ”flat” over ”sharp” minima, which in turn makes these states robust to perturbations. Despite its intuitive appeal, recent work by (Dinh et al., 2017) cast doubt on this explanation.
This work introduces a simple extension of SGD by combining backpropagation with gradient boosting. We propose that each iteration of the backpropagation algorithm can be reinterpreted by solving, at each layer, a regularized linear regression problem where the independent variables are the layer inputs and the dependent variables are gradients at the output of each layer, before non-linearity is applied. We call this approach deep gradient boosting (DGB), since it is effectively a layer-wise boosting approach where the typical decision trees are replaced by linear regressors. Under this model, SGD naturally emerges as an extreme case where the network weights are highly regularized, in the L2 norm sense. We hypothesize that for some learning problems the regularization criteria doesn’t need to be too strict. These could be cases where the data domain is more restricted or the learning task is posed as a matrix decomposition or another coding problem. Based on this idea we further introduce INN, a novel layer normalization method free of learnable parameters and show that it achieves competitive results on benchmark image recognition problems when compared to batch normalization (BN).

heading: 2 DEEP GRADIENT BOOSTING

text:
Consider a learning problem where training examples (x, y) are generated from a probability distribution P (x, y) where x ∈ RN is the space of measurements and y ∈ R is the space of labels. The goal of gradient boosting is to find an approximation F̂ (x) to a function F (x) that minimizes a specified loss function L(F (x), y):
F̂ = arg min F L(F (x), y) (1)
Gradient boosting solves Eq. 1 by seeking functions ht(x), so called weak learners, from a differentiable class H such that F̂ = ∑ t ht(x). Starting from a constant function F0 and applying steepest descent we can find F̂ by iteratively updating with learning rate γ:
Ft(x) = Ft−1(x)− γ∇Ft−1L(Ft−1(x), y) (2)
The weak learners ht are thus found by fitting the training data to the pseudo-residuals rt = ∇Ft−1L(Ft−1(x), y) hence in practice:
Ft(x) = Ft−1(x)− γht(x) (3)
Next, consider a neural network F (x) with parameters w[l] comprised of L successive dense linear layers F [l](x) = xTw[l] with non-linearities ψ: F (x) = F [0](ψ(F [1](...ψ(F [L](x))))). Similarly, starting from parameter w0 and following steepest descent the network weights are updated at iteration t:
wt = wt−1 − γ∇wt−1L(F (xt), yt) (4)
At each iteration, for a fixed layer l the gradient of the parameter w[l]ij can be calculated using the chain rule:
∂Lt
∂w [l] ij
= ∂Lt
∂F [l] t
∂F [l] t ∂w [l] ij = ∂Lt ∂F [l] t ψ(F [l−1] t )i = ∂Lt ∂F [l] t o [l] ti (5)
where o[l]i is the output of the layer l − 1 at iteration t and position i and the gradients ∂Lt ∂F
[l] t
are
calculated using the backpropagation algorithm.
Alternatively, using the gradient boosting formula from Eq. 3 and plugging in Ft = F [l](xt) = xTt w [l] for input xt = o [l] t we obtain, after dropping the layer indexes [l] for simplicity:
oTt wt = o T t wt−1 + γh(ot) (6)
We choose the weak learner h(ot) in this case to be a linear transformation as well h(ot) = oTt vt and fit it to the pseudo-residuals rt = ∂Lt
∂F [l] t
by solving the associated regularized linear regression:
v̂t = arg min v
(‖rt − oTt v‖22 + α‖v‖22), α > 0 (7)
The primal form solution of Eq. 7 is v̂t = (oTt ot + αI) −1otrt and plugging it into Eq. 6 yields the following update rule: wt = wt−1 − γ(oTt ot + αI)−1otrt where I ∈ RN×N is the identity matrix. For a given input batch of size B, the update rule becomes:
Wt = Wt−1 − γ(OTt Ot + αI)−1OTt Rt (8)
where Wt ∈ Rn×m is the weight matrix for a given layer, Ot ∈ RB×n is the input matrix at the same layer while Rt ∈ RB×m is the pseudo-residual matrix ∇FtLt. In practice, the inverse of matrix OTt Ot can be hard to calculate for neural networks with large number of neurons per layer. In consequence, it is often more convenient to use the dual form formulation of the ridge regression solution of Eq. 7 that involves calculating the inverse of OtOTt instead. This is a well known formulation (e.g. see Chapter 1 of (Camps-Valls et al., 2006)) and leads to the analogous weight update rule:
Wt = Wt−1 − γOTt (OtOTt + αI)−1Rt (9)
The weight update formulas from Eq. 8 and 9 have the drawback that they change in magnitude with either the number of neurons in the neural network layer or batch size. This is an undesirable behavior that can lead to differences in scale between weights from layers of different sizes. In consequence, the terms OTt Ot and OtO T t are scaled accordingly.
For large values of α the terms OTt Ot + αI and OtO T t + αI can be approximated by a constant diagonal matrix which leads to the classic SGD solution Wt ≈ Wt−1 − γOTt Rt. This shows that back-propagation with SGD is an extreme case of DGB that implicitly minimizes the magnitude of weight updates.

heading: 2.1 EXPERIMENTS

text:
In the following we will compare the performance of DGB and SGD on a variety of reference data sets and explore the effect of the α parameter using simple dense layer neural networks. A summary of the data sets used is given in Table 1:
The first data set is the MNIST database of handwritten digits (LeCun et al., 1999) comprised of 60,000 28x28 grayscale images for training and 10,000 for testing. In the case of the Higgs data set (Baldi et al., 2014) we used a randomly chosen subset with 1 million samples out of 10 million for training, and 500 thousands samples for testing. This data comes from the field of high energy physics and was generated by Monte Carlo simulations. The third data set (Reuters-21578) is comprised of 11,228 english language news articles from Reuters international news agency, labeled over 46 topics. The forth data set is the Human Resource (HR) data set (Stacker IV, 2015) which was put together by IBM Inc. to predict employee attrition based on 47 features and was randomly split into 1,029 training samples and 441 test samples. The fifth data set is a regression problem for predicting a measure of air quality based on the outputs from an array of chemical sensors together with air temperature and humidity (De Vito et al., 2008).
All experiments were performed until test set convergence using a gradient update momentum of 0.9 and no decay. For simplicity, network architecture was fixed for each data set and all activation
functions were rectified linear units (ReLU) (Nair & Hinton, 2010). The network weights were initialized using a uniform distribution according to (He et al., 2015). The loss functions used were cross-entropy loss for classification problems and mean squared loss for regression problems. The performance metrics used were accuracy for classification tasks and root mean squared error (RMSE) for regression tasks. In addition, standard deviations were calculated and reported for all performance measures by repeating each experiment 10 times with different random seeds.

heading: 2.1.1 MNIST

text:
For this experiment we found that results were relatively invariant to network architecture passed a certain complexity, in consequence we chose a dense neural network with three hidden layers each with 500 ReLU nodes. All models were trained using 100 sample batch size for 25 epochs using a fixed 0.1 learning rate and achieved 100% accuracy on the training set. The two DGB variants were labeled DGB(l) if it used the left pseudo-inverse from Eq. 8 and DGB(r) corresponding to the right pseudo-inverse from Eq. 9.
Both left and right variants achieve increasingly better test set performance with larger α values culminating with 98.59% average accuracy for the DGB(r) model with α = 1.0. This is marginally better than 98.41% average accuracy for SGD but more importantly this result shows how increasing the regularization parameter alpha successfully improves test set performance for an image classification problem prone to over-fitting.
Overall DGB(l) and DGB(r) show similar performance with the drawback that for relatively small batch sizes DGB(l) is considerably slower. This is because it needs to calculate the inverse of 500x500 matrix as opposed to calculating the inverse of 100x100 matrix, as is the case for DGB(r). When training on a single V-100 Nvidia GPU one SGD iteration took on average 0.0166 sec, one DGB(r) iteration took 0.0188 sec while in contrast DGB(l) took 0.1390 sec. In consequence, for the rest of experiments we will just use DGB(r) and simply label it DGB.

heading: 2.1.2 HIGGS

text: Higgs data set was created using Monte Carlo simulations of particle collisions and has 11 mil samples with 28 features. This is a binary classification problem designed to distinguish between a signal process which produces Higgs bosons and a background process which does not. For this exercise we kept only 1 mil samples for training and 500k for testing. All 28 features were normalized to be between 0 and 1. We used an architecture composed of two hidden linear layers with 500 ReLU activations each that was trained using a small batch size of 30 samples over 50 epochs. The learning rate was kept constant at 0.01 for SGD and DGB for high α values and was reduced to 0.001 for α ≤ 0.1. This data set poses a considerable challenge with its relatively few features and large sample size. Performance on the training set is relatively poor and doesn’t approach 100% accuracy like in the other experiments. The best test set accuracy is obtained for a smaller α value (Table A1).

heading: 2.1.3 REUTERS

text:
Reuters is a text categorization data set comprised or articles organized into 46 news topics. It was randomly divided into 8982 training and 2246 test samples that were processed using a binary tokenizer for the top 1,000 most common words. This data was then fed into a dense neural network with two hidden layers each with 500 ReLU nodes and trained for 100 epochs with learning rate fixed at 0.01.
Table A2 shows the results for experiments run using the SGD optimizer and DGB with α values 1.0, 0.1 and 0.01. This is a relatively small data set with a large number of features that is usually more successfully addressed using more advanced approaches like recurrent neural networks or convolutional neural nets. In this case, the results are close for all experiments and only marginally better at 78.05% mean accuracy for DGB with α = 0.1.

heading: 2.1.4 HR

text:
Similar to the other data sets, min-max normalization was used on all 47 features of the Human resource attrition data (HR). This is a binary classification task designed to predict employee attrition. To this end we employed a dense neural network with one hidden layer composed of 100 ReLU nodes. As before, we used a batch size of 30 samples for speed. All models were trained for 500 epochs with a fixed learning rate of 0.001.
With only 1029 training samples and 441 test samples the error bars (i.e. standard deviation) are too big to make a claim that DGB outperforms SGD in this case (see Table A3).

heading: 2.1.5 AIR

text:
The Air quality data set contains 9358 instances of hourly averaged reads from chemical sensors designed to measure air quality. After removing samples with missing values we divided the remaining data equally into 3788 training and 3788 test samples, and all the features were min-max normalized to be between 0 and 1. Unlike the previous experiments this was a regression problem with the goal of predicting concentrations of benzene, a common pollutant associated with road traffic. For this we employed a neural network with two hidden layers with 100 ReLU activations each, trained for 1000 epochs using a fixed learning rate of 0.1 and a batch size of 30 samples.
Just as the previous experiments, DGB with larger α values were closer in performance to SGD (Table A4). In this case, relaxing the regularization parameter led to a gradual increase in test set performance with almost half the root mean squared error for DGB with α = 0.001 when compared to SGD.

heading: 3 FAST APPROXIMATION OF DGB

text:
We showed in the previous section that deep gradient boosting outperforms regular stochastic gradient descent in some cases. However, this comes at a cost because DGB gradient updates involve calculating the inverse of a matrix at each step and for each layer. The computational cost for matrix inversion is roughly O(n3) and this can be significant even for small batch sizes as the ones used in the previous experiments. A straight forward way of speeding matrix inversion is to keep just the diagonal terms. This is equivalent of making the simplified assumption that for a layer input matrix O ∈ RB×n the rows are independent (i.e. ∑ k oikojk for i 6= j) in the case of DGB(r) or the
columns are independent (i.e. ∑ k okiokj for i 6= j) in the case of DGB(l).
For a layer with n input dimensions and a sample batch of size B, plugging in the diagonal approximations of matrices OtOTt and O T t Ot into Eq. 8 & 9 the gradient updates become:
Wt = Wt−1 − γÔTt Rt (10)
where
ôi,j = oij
1 n ∑n j=1 o 2 ij + α
(11)
in the case of DGB(r) and ôi,j =
oij 1 B ∑B i=1 o 2 ij + α
(12)
in the case of DGB(l).
In the above notation Ôt is the normalized version of layer input matrix Ot with elements ôij . In the following paragraphs, FDGB(r) will refer to fast DGB(r) from Eq. 11 and FDGB(l) will refer to fast DGB(l) from Eq. 12.

heading: 3.1 CONVOLUTIONAL NEURAL NETWORKS

text:
Convolutional neural networks (CNN) are a class of neural networks particularly suited to analyzing visual imagery. Typically the input at each CNN layer is a tensor of size (B × c× w × h) where B is the batch size, c is the number of feature maps while w and h are the width and height of the map. Instead of using a dense network with different weight connecting each point in the (c×w×h) map, CNNs work by dividing the feature map into usually overlapping sections by scanning the input with a kernel of a size much smaller than (w×h), usually (3×3). In this way CNNs effectively increase the number of input samples and simultaneously decrease the number of weights that need to be learned. This process can be viewed as a form of regularization and it has proven to greatly outperform regular dense networks that are usually prone to over-fitting on image recognition problems.
For a given CNN layer, assume we have an input of size (B × c0 × w0 × h0) and an output of size (B×c1×w1×h1) that was generated with a kernel of size (p×q). In this case, the equivalent DGB formulation based on Eq. 8 & 9 would have an input matrix Ot of size (B×w1×h1, c0× p× q). It would be extremely costly to first unfold the input as described and then calculate the matrix inverse of either OTt Ot or OtO T t . In consequence, it is advisable to use the fast versions of DGB however, one would still have to unfold the input matrix which is still a costly operation.
The key observation for extending FDGB(l) to convolutional neural networks is that for small kernels with a small step size each position in the kernel matrix will ”visit” roughly the same pixels in a feature map. Hence, calculating the raw second moment of each feature needs to be done only once per map. After resizing the input tensor Ot to (B × w0 × h0, c0) the new normalized input Ôt becomes:
ôi,j = oij
1 B×w0×h0 ∑B×w0×h0 i=1 o 2 ij + α
(13)
It is not unreasonable to assume a small kernel size given that most modern convolutional network architectures use kernels of size (3,3) for image recognition.

heading: 4 INPUT NORMALIZATION

text:
It is clear from Eq. 10 and previous paragraphs that DGB’s gradient update formulation can also be viewed as input normalization defined as N(X) := X(XTX + αI)−1 or N(X) := (XXT + αI)−1X followed by a regular SGD update. Hence this process can also be implemented as a separate normalization layer, similar to how other layer normalization work like batch norm (BN) (Ioffe & Szegedy, 2015), layer norm (LN) (Ba et al., 2016), instance norm (IN) (Ulyanov et al., 2016) and others.
The advantages of these normalization methods are well documented: they accelerate descent by enabling higher learning rates without the risk of divergence which in turn may help avoid local sharp minima (Bjorck et al., 2018), make training more resilient to parameter or input data scale (Ba et al., 2016), and they stabilize layer output variance which prevents gradient exposition in very deep networks (He et al., 2016a). Interestingly, for formulations that operate across samples like batch norm they also have a regularization effect and virtually eliminate the need for other regularization methods like dropout (Srivastava et al., 2014). This is because training examples are seen in conjunction with other examples in the mini-batch, hence the layer outputs are no longer deterministic. This added noise was found to be beneficial to the generalization of the network.
Batch norm, layer norm and instance norm perform a z-score standardization of features/inputs by subtracting the mean and dividing by standard deviation which is typically applied to the output
of a layer, before the activation function. This procedure runs the risk of keeping the output of a layer inside the linear regime of activation functions that are symmetric around zero. In order to recover the expressive power of the network, after normalization is performed two new parameters are introduced that scale and shift the output. These parameters are in turn learned during training like the rest of the network weights. Interestingly, the scale and shift parameters help convergence even for neural networks with non-symmetric activation functions (e.g. ReLU).
In contrast to these methods, the normalization procedure described here is applied to the layer input, it is not scale invariant and has only one parameter α which is predefined before training, not learned. In addition, ”normalization” in our case doesn’t refer to the process of making the data look more like a standard normal distribution but instead refers to an algebraic transformation of the data that improves its condition number.

heading: 4.1 INPUT NORMALIZATION OF MULTIPLE LINEAR REGRESSION

text:
In the following we will study the effect of input normalization as defined in the previous paragraph to the simple problem of ordinary least squares solved by gradient descent. Consider a multiple linear regression model arg minw(y − Xw)T (y − Xw) where X ∈ RB×n is an input matrix, y ∈ RB is the output vector and w ∈ Rn is the vector of parameters. It is well known that the rate of convergence of gradient descent in this case depends on the condition number of the Hessian H = XTX where high values lead to slow convergence. If X = UΣV T is the singular value decomposition of input matrix X , where U and V are orthogonal matrices and Σ is a diagonal matrix, then the condition number of H = XTX = V Σ2V T is:
κ(H) = σ2max σ2min
(14)
where σmax and σmin are the largest and respectively smallest singular values of X .
Let N(X) := X(XTX + αI)−1 and arg minw(y − N(X)w)T (y − N(X)w) be the resulting linear regression problem after applying input normalization. The new Hessian matrix is H∗ = (XTX + αI)−1XTX(XTX + αI)−1. After plugging in X = UΣV T and some linear algebra manipulation the new condition number becomes:
κ(H∗) = σ2max
(σ2max + α) 2
(σ2min + α) 2
σ2min = κ(H)
( σ2min + α
σ2max + α
)2 < κ(H) (15)
This result shows that input normalization leads to a smaller condition number of the Hessian matrix in the case of multiple linear regression. The same result can be obtained when using the alternative input normalization N(X) := (XXT + αI)−1X (see Prop. A.1 & A.2 in the appendix).

heading: 4.2 FORMULATION

text:
In practice, we will define Input Normalization (INN) using the faster diagonal approximations from Eq. 11 & 12. In addition, similar to other normalization layers we will also mean center the input data. For a single layer network, centering further improves conditioning of the Hessian of the loss (LeCun et al., 1991), it brings the input data near the critical point of most activation functions thus removing the bias towards certain neurons and, it has a regularization effect by shifting the data in a nondeterministic way during training based on the content of the mini-batch.
For an input matrix X ∈ RB,n with elements xij left input normalization is labeled INN(l) and defined as
N(xij) := xij − 1B
∑B i=1 xij
1 B ∑B i=1 x 2 ij + α
(16)
while right input normalization is labeled INN(r) and defined as
N(xij) := xij − 1n
∑n j=1 xij
1 n ∑n j=1 x 2 ij + α
(17)
In the case of INN(l) formulation the batch statistics m1 = 1B ∑B i=1 xij and m2 = 1 B ∑B i=1 x 2 ij can cause non-deterministic predictions at test time. Instead, running exponential averages are calculated during training for both m1 and m2. These new values are then used at test time.

heading: 4.3 EXPERIMENTS

text: We tested the implicit (i.e. FDGB) and explicit (i.e. INN) input normalization models on the CIFAR10 data set (Krizhevsky et al., 2009) and compared them to Batch Normalization (BN). We then validated the best performing models on the ImageNet object recognition data set (ILSVRC2015) (Russakovsky et al., 2015). In both cases we used versions of the VGG architecture first introduced by Simonyan & Zisserman (2014) and then modified them to accommodate the different models as described in Appendix A.

heading: 4.3.1 CIFAR10

text: The CIFAR10 data set consists of 60000 images organized into 10 classes. There are 50000 training and 10000 test images. According to Table 3 the original VGG11 model achieves a baseline performance of 89.50% accuracy on this problem. Adding batch normalization layers to this architecture significantly improves the performance to 91.18% accuracy. The INN(l) model outperforms both FDGB(l) and VGG11 while matching the performance of batch normalized VGG11 architecture (VGG11 BN). In the next section we validate the performance of INN(l) on a larger image classification data set using a deeper convolutional network.

heading: 4.3.2 IMAGENET

text:
The ImageNet data set is part of the Large Scale Image Recognition Challenge 2015 (Russakovsky et al., 2015) and consists of 1,281,167 training and 50,000 validation images organized into 1,000 categories. For this experiment we compared the performance of VGG19 and ResNet101 with batch normalization (VGG19 BN(a) and respectively ResNet101 BN) to the equivalent architecture with input normalization layers (VGG19 INN(l) and respectively ResNet101 INN(l)) (See Appendix A for more details). In addition, for VGG19 BN(b) we disabled the learnable affine parameters which reduces BN to a basic standardization operation.
Similar to CIFAR10 the performance of VGG INN(l) is very close to that of VGG19 BN(a) although during early epochs VGG INN(l) shows better convergence (Figure 1). For the BN model without affine parameters (VGG19 BN(b)) performance drops dramatically when trained using the same learning rate schedule showing that extra parameters are essential for the performance of VGG19 with batch normalization (Table 4). When employing an architecture with residual connections ResNet101, replacing batch normalization layers with INN operations leads to a slight decrease in performance.

heading: 5 CONCLUSIONS

text: This work introduces Deep Gradient Boosting (DGB), a simple extension of Stochastic Gradient Descent (SGD) that allows for finer control over the intrinsic generalization properties of SGD. We empirically show how DGB can outperform SGD in certain cases among a variety of classification and regression tasks. We then propose a faster approximation of DGB and extend it to convolutional layers (FDGB). Finally, we reinterpret DGB as a layer-wise algebraic manipulation of the input data and implement it as a separate normalization layer (INN). We then test INN on image classification tasks where its performance proves to be on par with batch normalization without the need for additional parameters.

heading: A APPENDIX

text:
Model α Learning rate Performance
SGD 0.01[0-50] 74.10%± 0.12 DGB 1.0 0.01[0-50] 73.53%± 0.42 DGB 0.1 0.001[0-50] 74.60%± 0.19 DGB 0.01 0.001[0-50] 74.99%± 0.09 DGB 0.001 0.001[0-50] 73.98%± 1.22
Table A1: Performance on the Higgs data set measured as accuracy.
Model α Learning rate Performance
SGD 0.01[0-100] 77.54%± 0.29 DGB 1.0 0.01[0-100] 77.31%± 0.27 DGB 0.1 0.01[0-100] 78.05%± 0.23 DGB 0.01 0.01[0-100] 77.39%± 0.24
Table A2: Performance on the Reuters data set measured as accuracy.
Model α Learning rate Performance
SGD 0.001[0-500] 86.51%± 0.44 DGB 1.0 0.001[0-500] 86.87%± 0.21 DGB 0.1 0.001[0-500] 86.92%± 0.48 DGB 0.01 0.001[0-500] 85.24%± 0.59
Table A3: Performance on the HR data set measured as accuracy.
Model α Learning rate Performance
SGD 0.1[0-1000] 0.0020± 0.00017 DGB 1.0 0.1[0-1000] 0.0020± 0.00020 DGB 0.1 0.1[0-1000] 0.0013± 0.00007 DGB 0.01 0.1[0-1000] 0.0012± 0.00028 DGB 0.001 0.1[0-1000] 0.0010± 0.00015
Table A4: Performance on the Air data set measured as root mean squared error.
Proposition A.1. If σ is a singular value of matrix X then (XTX + αI)−1XTX(XTX + αI)−1 has singular values of the form σ 2
(σ2+α)2 .
Let X = UΣV T be the singular value decomposition of X then:
(XTX + αI)−1XTX(XTX + αI)−1 = (V Σ2V T + αI)−1V Σ2V T (V Σ2V T + αI)−1
= (V Σ2V T + αV V T )−1V Σ2V T (V Σ2V T + αV V T )−1
= V (Σ2 + αI)−1V TV Σ2V TV (Σ2 + αI)−1V T
= V (Σ2 + αI)−1Σ2(Σ2 + αI)−1V T
Proposition A.2. If σ is a singular value of matrix X then XT (XXT + αI)−2X has singular values of the form σ 2
(σ2+α)2 .
Let X = UΣV T be the singular value decomposition of X then:
XT (XXT + αI)−2X = V ΣUT (UΣ2UT + αI)−2UΣV T
= V ΣUT (UΣ2UT + αUUT )−2UΣV T
= V ΣUTU(Σ2 + αI)−2UTUΣV T
= V Σ(Σ2 + αI)−2ΣV T
A.1 CIFAR10
For this experiment we used a version of the VGG11 network introduced by Simonyan & Zisserman (2014) that has 8 convolutional layers followed by a linear layer with 512 ReLU nodes, a dropout layer with probability 0.5 and then a final softmax layer for assigning the classification probabilities. A second version of this architecture (VGG11 BN) has batch normalization applied at the output of each convolutional layer, before the ReLU activation as recommended by Ioffe & Szegedy (2015) We modified this architecture by first removing all the batch normalization and dropout layers. We then either replaced all convolutional and linear layers with ones that implement the fast version of DGB for the FDGB(l) architecture or added INN(l) layers in front of each of the original convolutional and linear layers. Both FDGB(l) and INN(l) models implement input normalization based on the left pseudo-inverse (see Eq. 12 & 16) in order to take advantage of its regularization effect. All weights were initialized according to Simonyan & Zisserman (2014) and were trained using stochastic gradient descent with momentum 0.9 and batch size 128. For the FDGB(l) model the gradients were calculated according to Eq. 12 for linear and 13 for convolutional layers. Training was started with learning rate 0.1 and reduced to 0.01 after 250 epochs and continued for 350 epochs. All experiments were repeated 10 times with different random seeds and performance was reported on the validation set as mean accuracy ± standard deviation.
A.2 IMAGENET
Similar to the CIFAR10 data set we based these experiments on the larger VGG19 architecture of Simonyan & Zisserman (2014). The VGG19 network has 16 convolutional layers interspersed with max-pool operations, followed by two linear layers with 4096 ReLU nodes and a final softmax layer with 1000 outputs. The original VGG19 model uses dropout regularization after each rectified linear
layer. A second version of this architecture (VGG19 BN) has batch normalization applied at the output of each convolutional layer, before the ReLU activation. We tested VGG19 BN with and without affine parameters (VGG19 BN(a) and respectively VGG19 BN(b)). After removing all the dropout and batch normalization layers we created the INN(l) version by adding input normalizations in front of each remaining layer.
In order to explore the performance of INN on network architectures with residual connections we employed ResNet101 proposed by He et al. (2016b). The original network uses batch normalization between convolutional layers by default (ResNet101 BN). The INN version of this network (ResNet101 INN(l)) was created by first removing all BN layers, then adding INN operations in front of each convolutional and dense layers, with the exception of down-sample convolutions.
Stochastic gradient descent was used to minimize the cross entropy loss of each network over 120 epochs, using an initial learning rate of 0.05, 0.9 momentum, a batch size of 128 images, and 0.0001 weight decay. Every 30 epochs the learning rate was decreased by a factor of 10. All networks were evaluated by computing the top-1 and top-5 validation errors on a held out data set using 10 crops per image.