summaries: The paper proposes to use a multi-step prediction model in model-based RL. The proposed model maps from current state and a sequence of actions to the state after taking those actions. The paper demonstrates on 2 tasks that in a model-predictive control loop combined with planning by cross-entropy method, this can yield better asymptotic performance than using single-step models.

summaries: The authors learn a model that predicts the state R steps in the future, given the current state and intervening actions, instead of the predicting the next time step state. The model is then used for standard model predictive control. The authors find numerically that their method, termed Plan-Conditional Predictor (PCP), performs better over long horizon times (~100 time steps), than other recent model-based and model-free algorithms. This because for long horizon time scales, the model predicting the state for the next time step accumulates error when used recursively.

abstractText: In complex simulated environments, model-based reinforcement learning methods typically lag the asymptotic performance of model-free approaches. This paper uses two MuJoCo environments to understand this gap through a series of ablation experiments designed to separate the contributions of the dynamics model and planner. These reveal the importance of long planning horizons, beyond those typically used. A dynamics model that directly predicts distant states, based on current state and a long sequence of actions, is introduced. This avoids the need for many recursions during long-range planning, and thus is able to yield more accurate state estimates. These accurate predictions allow us to uncover the relationship between model accuracy and performance, and translate to higher task reward that matches or exceeds current state-of-the-art model-free approaches.

authors:
George A Bekey
Kenneth Y Goldberg

title: Neural Networks in robotics, volume 202

title: A Markovian decision process

venue: Journal of Mathematics and Mechanics,

title: The cross-entropy method for optimization

authors:
Kurtland Chua
Roberto Calandra
Rowan McAllister
Sergey Levine

title: Deep reinforcement learning in a handful of trials using probabilistic dynamics models

venue: arXiv preprint arXiv:1805.12114,

authors:
I. Clavera
A. Nagabandi
R.S. Fearing
P. Abbeel
S. Levine
C. Finn

title: Learning to adapt: Meta-learning for model-based control

authors:
M. Deisenroth
D. Fox
C.E. Rasmussen

title: Gaussian processes for data-efficient learning in robotics and control

venue: IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI),

authors:
Marc Peter Deisenroth
Carl E. Rasmussen

title: PILCO: A model-based and data-efficient approach to policy search

venue: In ICML,

authors:
Andreas Draeger
Sebastian Engell
Horst Ranke

title: Model predictive control using neural networks

venue: IEEE Control systems,

authors:
Chelsea Finn
Sergey Levine

title: Deep visual foresight for planning robot motion

authors:
Yarin Gal
Rowan McAllister
Carl Edward Rasmussen

title: Improving pilco with bayesian neural network dynamics models

venue: In Data-Efficient Machine Learning workshop,

authors:
A. Grancharova
J. Kocijan
T.A. Johansen

title: Explicit stochastic predictive control of combustion plants based on gaussian process models

authors:
Mikael Henaff
William F Whitney
Yann LeCun

title: Model-based planning with discrete and continuous actions

venue: arXiv preprint arXiv:1705.07177,

authors:
K Jetal Hunt
D Sbarbaro
R Żbikowski
Peter J Gawthrop

title: Neural networks for control systemsa survey

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

title: Self-normalizing neural networks

venue: In Advances in Neural Information Processing Systems,

authors:
J. Ko
D.J. Klein
D. Fox
D. Haehnel

title: Gaussian processes and reinforcement learning for identification and control of an autonomous blimp

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

authors:
J. Kocijan
R. Murray-Smith
C.E. Rasmussen
A. Girard

title: Gaussian process model based predictive control

venue: In IEEE American Control Conference,

title: Pytorch implementations of reinforcement learning algorithms

authors:
Ian Lenz
Ross A Knepper
Ashutosh Saxena

title: Deepmpc: Learning deep latent features for model predictive control

venue: In Robotics: Science and Systems,

authors:
Sergey Levine
Chelsea Finn
Trevor Darrell
Pieter Abbeel

title: End-to-end training of deep visuomotor policies

venue: The Journal of Machine Learning Research,

authors:
Timothy P. Lillicrap
Jonathan J. Hunt
Alexander Pritzel
Nicolas Heess
Tom Erez
Yuval Tassa
David Silver
Daan Wierstra

title: Continuous control with deep reinforcement learning

authors:
David Q Mayne
Hannah Michalska

title: Receding horizon control of nonlinear systems

venue: IEEE Transactions on automatic control,

authors:
W Thomas Miller
Robert P Hewes
Filson H Glanz
L Gordon Kraft

title: Real-time dynamic control of an industrial manipulator using a neural network-based learning controller

venue: IEEE Transactions on Robotics and Automation,

authors:
Anusha Nagabandi
Gregory Kahn
Ronald S Fearing
Sergey Levine

title: Neural network dynamics for model-based deep reinforcement learning with model-free fine-tuning

venue: arXiv preprint arXiv:1708.02596,

authors:
Vitchyr Pong
Shixiang Gu
Murtaza Dalal
Sergey Levine

title: Temporal difference models: Modelfree deep rl for model-based control

authors:
Sashank J Reddi
Satyen Kale
Sanjiv Kumar

title: On the convergence of adam and beyond

title: An on-line algorithm for dynamic reinforcement learning and planning in reactive environments

venue: In Proc. IEEE/INNS International Joint Conference on Neural Networks,

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

title: Proximal policy optimization algorithms

venue: arXiv preprint arXiv:1707.06347,

authors:
David Silver
Hado van Hasselt
Matteo Hessel
Tom Schaul
Arthur Guez
Tim Harley
Gabriel Dulac-Arnold
David Reichert
Neil Rabinowitz
Andre Barreto

title: The predictron: End-toend learning and planning

venue: arXiv preprint arXiv:1612.08810,

title: Integrated architectures for learning, planning, and reacting based on approximating dynamic programming

venue: In Machine Learning Proceedings

authors:
Emanuel Todorov
Weiwei Li

title: A generalized iterative lqg method for locally-optimal feedback control of constrained nonlinear stochastic systems

venue: In American Control Conference,

authors:
Emanuel Todorov
Tom Erez
Yuval Tassa

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

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

authors:
George E Uhlenbeck
Leonard S Ornstein

title: On the theory of the brownian motion

venue: Physical review,

authors:
Niklas Wahlström
Thomas B Schön
Marc Peter Deisenroth

title: From pixels to torques: Policy learning with deep dynamical models

venue: arXiv preprint arXiv:1502.02251,

authors:
Manuel Watter
Jost Tobias Springenberg
Joschka Boedecker
Martin A. Riedmiller

title: Embed to control: A locally linear latent dynamics model for control from raw images

venue: In NIPS,

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

title: Imagination-augmented agents for deep reinforcement learning

venue: arXiv preprint arXiv:1707.06203,

heading: 1 INTRODUCTION

text:
Model-based reinforcement learning (MBRL) has many potential benefits over model-free approaches. These include (i) the ability to generalize to new tasks in the environment, without having to retrain; (ii) learning from off-policy data and (iii) sample efficiency. However, in simulated environments where data is plentiful, model-based approaches struggle to approach the asymptotic performance of model-free methods Nagabandi et al. (2017); Pong et al. (2018); Chua et al. (2018). Several possible explanations present themselves: the planner used for selecting optimal actions under the model might be insufficiently powerful; the model might not be able to accurately model the dynamics; or the planning horizon might not be long enough.
This paper address these questions by teasing apart the different factors involved in an MBRL framework, applied to two deterministic MuJoCo environments (Todorov et al., 2012), with the aim of understanding the gap in asymptotic performance with respect to model-free approaches. In particular, we demonstrate that bias caused by short planning horizons and poor accuracy of long-term predictions is the cause of the poor performance of existing MBRL methods in the unlimited-sample regime. Our experiments show that, with a perfect dynamics model, the optimal planing horizon can be over 100 steps – much longer than typically considered in many MBRL approaches. Correspondingly, the performance is typically limited by the ability of the model to accurately predict over long-time scales, not just a few time-steps.
Existing approaches to MBRL rely on a single-step dynamics model that predict the next state, given the current state and an action. As can be see in Figure 5, over long time-horizons the errors compound due to recursive application of the model, yielding inaccurate state estimates which are not useful for planning. Instead, we propose an alternate form of dynamics model that takes as input a sequence of actions along with the current state and directly predicts many time-steps into the future. This approach provides accurate prediction over long time horizons, allowing us to uncover the relationship between model accuracy and performance. This reveals that MBRL with sufficiently good learned models matches or exceeds the performance of state-of-the-art model-free methods.

heading: 1.1 RELATED WORK

text:
Non-Parametric Model-Based RL: Gaussian processes are popular approach to modeling nonlinear dynamics due to their low sample complexity and their ability to explicitly represent epistemic uncertainty. Consequently, numerous MBRL approaches use them, e.g. Kocijan et al. (2004); Ko
et al. (2007); Grancharova et al. (2008); Deisenroth & Rasmussen (2011); Deisenroth et al. (2014). However via the choice of kernel they impose potentially unrealistic smoothness constraints and do not scale to large data settings, limiting their asymptotic performance in practice.
Combining model-based and model-free methods: Due to the sample efficiency of model-based methods and superior asymptotic performance of model-free methods, several works have proposed to learn dynamics models using a few trajectory samples, then use those models to train or augment a model-free policy. The classic Dyna algorithm (Sutton, 1990) uses a model to extend Bellman updates multiple steps. Deisenroth & Rasmussen (2011) learns a Gaussian process model of the dynamics function and uses it to train an RBF network policy, and Gal et al. (2016) enables the model to scale to larger data by using Bayesian neural networks in place of GPs. Levine et al. (2016) fits a time-varying locally linear model around a trajectory, then trains a neural network policy to follow trajectories found by iLQR (Todorov & Li, 2005). Silver et al. (2016) learns an implicit model of the dynamics for implicit planning via value estimation; in an inversion of this technique, Pong et al. (2018) learn an explicit model of Q values for explicit planning via constrained optimization. Weber et al. (2017) learns a neural network dynamics model which is unrolled inside a policy to inform an actor-critic agent. Nagabandi et al. (2017) trains a neural network dynamics model on control tasks and uses it to take actions, then uses that model-based policy to speed the training of a model-free policy via imitation learning. These works largely seek to either (i) augment a modelfree method with a model for faster learning, or (ii) make up for the asymptotic deficiencies of a model-based method by transitioning to model-free. In this work we instead directly investigate the causes of MBRL’s poor asymptotic performance with the aim of making a transition to model-free unnecessary.
MBRL with neural network models: The idea of using neural networks to enable model-based control of nonlinear systems goes back decades (Miller et al., 1990; Schmidhuber, 1990; Hunt et al., 1992; Bekey & Goldberg, 2012; Draeger et al., 1995), but until recently has only seen significant success on systems with relatively simple dynamics. Several works have endeavored to use neural network generative models of images for model-based control (Wahlström et al., 2015; Watter et al., 2015; Finn & Levine, 2017); these policies have typically used short planning horizons and struggled to equal model-free performance on complex tasks. Lenz et al. (2015) learn recurrent neural network dynamics models, then use backpropagation through time to select actions and control a robotic arm, and Henaff et al. (2017) extend this concept to both discrete and continuous action spaces. Clavera et al. (2018) combine meta-learning with MBRL using neural network models to rapidly adapt to novel environments. Srinivas et al. (2018) uses imitation learning to train a model to plan by gradient descent, which relies on an existing expert rather than learning from scratch.
The closest work to ours is Chua et al. (2018). This follows a similar recipe, with similar planning and constructing a dataset online, but with different models and different goals. We use deterministic neural networks which predict many steps into the future to understand the impact of model- and horizon-bias on asymptotic performance of MBRL methods on long-horizon problems. Chua et al. (2018) uses a bootstrapped ensemble of probabilistic neural networks to improve the performance of MBRL in the few-sample regime. While that work achieves strong performance on short-horizon tasks, in our experiments we find it struggles to equal model-free methods on tasks with very long horizons.

heading: 2 APPROACH

text: In this section we describe the models used in our experiments, the action-conditional predictor (ACP) and the novel plan-conditional predictor (PCP), which predicts the outcome of a sequence of actions with a single model step. We then detail the framework we use for planning with and training these models.

heading: 2.1 NOTATION

text:
We denote states and actions at a time t by st and at. In the environments we consider, both st and at are continuous vectors. We use H to refer to the planning horizon of an MPC policy. We refer to a sequence of actions as a plan; a plan constructed with horizon H is thus p = {a1, ..., aH}. In a set of plans {p1, ..., pn}, aij refers to the jth action of the ith plan.
We consider models which predict a future state given the current state and one or more actions. We denote R to be the range of such a model, which is the number of steps this model predicts in a single application: fR(st, at, . . . , at+R−1; θ) = s̃t+R, for parameters θ.
We apply the model recursively using the notation FT (st, at, . . . , aT−1; θ) = fR(. . . fR(fR(st, at, . . . , at+R−1; θ), at+R, . . . , at+2R−1; θ) . . . , aT−R, . . . , aT−1; θ) = s̃T . That is, FT () applies fR() recursively T/R times.

heading: 2.2 PLAN-CONDITIONAL PREDICTORS

text:
To test our conjecture that compounding errors limit the asymptotic performance of existing models on long-horizon RL tasks, we propose plan-conditional predictors (PCPs). A PCP takes the form fR(st, at, . . . , at+R−1) = s̃t+R for some range R > 1. If R = 1, then it reduces to the standard approach (Deisenroth & Rasmussen, 2011; Gal et al., 2016; Henaff et al., 2017; Nagabandi et al., 2017; Chua et al., 2018) which predicts only a single time-step at a time, and which we call an action-conditional predictor (ACP). As shown in Figure 1, a PCP can predict H steps into the future using H/R recursive applications of the model instead of H applications required by an actionconditional predictor.
There are many possible parameterizations that could be used in a PCP. In this work we choose deep fully-connected neural networks. There are several reasons for this: (i) the space of inputs grows exponentially with the range R, thus models with high capacity are needed to minimize model bias; (ii) since the goal is to understand asymptotic performance, a large data regime is assumed and sample complexity is a secondary issue; (iii) by predicting R steps with a single network application, they are extremely fast at planning time. An obvious alternate parameterization is recurrent neural networks (RNNs), and we provide experimental comparisons between the two approaches in Section 3.
For both Swimmer and HalfCheetah, the ACP and PCP networks consist of fully-connected networks with 9 hidden layers with 1000 units each using the SELU activation function (Klambauer et al., 2017). The input state and action(s) are concatenated before being used as input to the network.
The same loss function is used for training PCPs and ACPs, namely ‖s̃t+R − st+R‖22, where s is the raw MuJoCo state. We assume that the environment forms a Markov decision process (MDP) (Bellman, 1957) with deterministic dynamics, properties shared by the tasks considered in this work. These assumptions allow us to focus exclusively on the significance of model fidelity and planning horizon to MBRL, but removing them is an interesting direction for future work.

heading: 2.2.1 INTERMEDIATE PREDICTIONS

text:
For visualization purposes, in some experiments we use a variant of a plan-conditional predictor which takes as input a state and a variable number of actions R′ where 1 ≤ R′ ≤ R, the remainder of action inputs being set to zero. This allows us to plot error or render video of the PCP’s predictions at each intermediate timestep instead of only at multiples of R.
Furthermore, this variant of the model allows for planning based on reward functions which operate at each timestep rather than just at the end of the episode (see Section 2.3.1). As such, this variant of the model is applicable to any environment.

heading: 2.3 SELECTING OPTIMAL ACTIONS

text:
In order to turn a predictor into a policy, we employ an off-the-shelf planning approach, namely the cross-entropy method (CEM) (Botev, 2011), to find a plan that is optimal up to some horizonH . We
take the first action from that plan and then replan, a technique known as model-predictive control (MPC) or receding-horizon control (Mayne & Michalska, 1990).

heading: 2.3.1 PLANNING WITH CROSS-ENTROPY METHOD

text:
Given a predictor F , a horizon H , and a reward function r, we would like to find an optimal plan:
p∗t = argmax at,...,at+H−1 H−1∑ i=0 r(s̃t+i, at+i) | s̃t+i = FH(st, at, . . . , at+i−1)
For both MuJoCo environments, the reward function is dominated by the distance traveled in the xdimension at each timestep1. Thus for planning purposes we can replace the original reward function with a sparse one which provides reward equal to the x-distance traveled at the end of the episode:
r̂(st) = { st[x] if t == T 0 otherwise . We then substitute t +H for T and plan based on r̂(st+H); note this
is identical to using the sum of x-progress at each timestep t...t +H . This reduces the form of the optimal plan under a predictor F to
p∗t = argmax at,...,at+H−1 r̂(FH(st, at, . . . , at+H−1))
The cross-entropy method starts with a set of plans p drawn from a candidate distribution C. In continuous control tasks, sampling actions independently along a trajectory results in near-zero net motion. Therefore it is common to instead use correlated action noise for exploration or trajectory sampling, e.g. an Ornstein-Uhlenbeck process (Uhlenbeck & Ornstein, 1930) as in DDPG (Lillicrap et al., 2015). We define the candidate C(·) distribution by the following sampling process:
a0 ∼ U(−1, 1) at+1 = min(max(N (µ = at, σ = 0.2),−1), 1)
i.e. the sampled actions are clamped to be in the range ±1 which are the limits of the action space. The overall planning framework is shown in Figure 2. After drawing an initial set of N plans {p1, . . . , pN} ∼ C(·), these are passed through the predictor F to estimate rewards r1, . . . , rN , which are used to rank the plans. The top K are then passed to a 2nd round (red box). Additionally, their mean and variance are computed2 and used as parameters for a Gaussian distribution from which N −K new plans are sampled (green box). The combined set of plans are then passed to the PCP to rank them. The output from the planner is the first action from the top-ranked plan (yellow box) at the final planning round, which is executed by the agent in the environment.
The top K trajectories from the final round are used to seed the initial set of plans for replanning at the next timestep, after clipping the first action from each. In practice, we use 3 rounds of planning at each timestep, i.e. two rounds of resampling (the figure omits the 3rd round for clarity). In our experiments, we use N = 50 and K = 5.
1In all experiments we evaluate a policy using the original reward function from OpenAI Gym. This simplified reward function is exclusively used inside the policy. We found in experiments using the ground-truth dynamics as a model that planning with the true reward function instead made no significant difference on these tasks.
2Independently at each timestep and action dimension; µ(p1, . . . , pn) = {
1 n ∑ i a i j | j ∈ H } and
σ(p1, . . . , pn) = {√ 1 n ∑ i ( aij − µ(a1...nj ) )2 | j ∈ H}.
Ac#on   executed
p1   p2
pN
p1   p2
pN
C
Round  1
Round  2
F  pK
pK
N(μ,σ)
… ..
… ..
… ..
… ..
r1   r2
rN
rK  ~
~   F
r1   r2
rN
rK
Sort
Time     step  1
Sort
Seed  next     #mestep
Figure 2: Our off-the-shelf planner, based on the cross-entropy method (Botev, 2011). See text for details.
Algorithm 1 On-policy data aggregation and training Initialize dataset D with trajectories from random policy while not converged do
θ ← argminΘ E (fR(st, at...t+R−1)− st+R)2 st,at...t+R−1,st+R∼D for m = 0...M do for t = 0...T do
st ← Env.get observation() pt ← argmaxat...t+H−1 r̂(FH(st, at...t+H−1; θ)) at ← head(pt) Env.execute(at).
end for D← D ⋃ (s0...T , a0...T−1)
end for end while

heading: 2.4 ONLINE TRAINING

text:
The planning framework described above turns the PCP model into a policy which outputs an action at each time step. To train this policy, the underlying PCP model must be updated in an online fashion.
This requires a dataset of trajectories {s0...T , a0...T−1} that covers the environment’s state-action space. We follow Nagabandi et al. (2017); Chua et al. (2018) and others and collect this dataset by alternating between fitting the model to the existing data and using our planning procedure (2.3.1) to generate more trajectories from the environment. We collect trajectories from the environment for M = 100 episodes. These trajectories are added to the training set and the PCP model is updated with SGD for 10 epochs using AMSGrad (Reddi et al., 2018). The overall procedure is detailed in Algorithm 1 and is essentially the standard template for MBRL (Deisenroth & Rasmussen, 2011; Gal et al., 2016; Nagabandi et al., 2017; Chua et al., 2018).

heading: 3 EXPERIMENTS

heading: 3.1 EFFECT OF PLANNING HORIZON AND MODEL RANGE

text:
In this experiment we directly test our hypothesis that plan-conditional predictors are able to benefit from longer planning horizons than action-conditional predictors. Figure 3 shows that while an ACP model is competitive for planning horizons up to 20 timesteps, its performance falls substantially below the PCP models by 40 timesteps. The ACP model scores best at a horizon of 60 timesteps; beyond that its performance degrades as its predictions become unusably inaccurate.
By contrast the PCP models shown, which need only be recursively applied between 3 and 20 times, all show monotonically increasing rewards as the planning horizon is increased. This reveals two things: the Swimmer task has a minimum optimal planning horizon of at least 100 timesteps, and the PCP models are able to predict with sufficient accuracy to be useful even over that long horizon.
In the next experiments we tease apart the different factors of planning horizon, range, and accuracy that combine to produce these results.

heading: 3.2 PLANNING HORIZON VS REWARD

text:
Using a ground-truth model of the environment (that is, MuJoCo itself) in conjunction with our planner we can look at performance as a function of planning horizon for these tasks. That is, we define a new predictor MJC(st, at...t+T ) which can make predictions arbitrarily far into the future. This predictor works internally by creating a new copy env internal of the Gym environment. To make a prediction MJC(st, at...t+T ) = st+1, this predictor will call env internal.set state(st), then repeatedly call env internal.step(at+i) for i = 0...T . Its output is the observation after the final action has been executed. This ground-truth predictor can be used for planning like any other.
The results of this experiment, shown in Figure 4, show that the optimal planning horizons for Swimmer and HalfCheetah are at around 150 and 40 timesteps, respectively. These results provide additional clarity to those presented in the previous experiment. Policies that use the groundtruth dynamics as their predictor perform better as the horizon increases due to the decreased bias of the long-horizon reward estimate. The approximate dynamics model from PCPs show similar gains. However, beyond a certain planning horizon the quasi-random search in the planner becomes less effective due to variance caused by the huge size of the search space, causing the reward to dip for H > 150.
Previous work (Nagabandi et al., 2017; Chua et al., 2018) has demonstrated planning for 20 or 30 timesteps with a neural network dynamics model (and in particular, the recent Chua et al. (2018) achieves impressive scores on HalfCheetah). However, to our knowledge planning horizons above 50 timesteps remain untested. This leads us to investigate the accuracy at very long range prediction of traditional action-conditional predictors as well as our plan-conditional predictors.
3We found it necessary to handicap the ground-truth model on HalfCheetah by adding noise to its actions during planning to prevent the planner from breaking the simulation. Without this handicap the planner was able to find nonphysical strategies and achieves expected reward of up to 150,000.

heading: 3.3 MODEL RANGE VS ACCURACY

text:
With the evidence from Section 3.2 that some tasks require planning horizons up to 150 timesteps, we now evaluate action-conditional and plan-conditional predictors on their ability to make longrange predictions in MuJoCo. Additionally we compare to an RNN which predicts one step at a time, but which is trained with backpropagation through time (BPTT) to minimize prediction error across all timesteps. This RNN is trained with a curriculum of prediction lengths ranging from 1 (at the beginning of training) to 200 (at the end).
To enable direct comparisons, we employ a fixed dataset of trajectories from the environment. We generate this dataset by training a model-free PPO (Schulman et al., 2017) agent on Swimmer and recording the trajectories that it takes. This ensures that the dataset contains trajectories that involve interacting with the environment in nontrivial ways. We then split that data into a training set and a validation set and train each model to convergence on the training set.
Figure 5 shows the results of evaluating these models on the validation set. While the ACP is able to make extremely accurate predictions a few steps into the future, it suffers from accumulating error when it is recursively applied many times. This suggests an explanation for the inability of the ACP models to take advantage of planning horizons longer than 60 timesteps, as discussed in Section 3.1. As the horizon increases the predictions from an ACP diverge from reality, while simultaneously the bias from using a too-short planning horizon decreases. This produces an optimal planning horizon of intermediate length given a model with error that increases as a function of depth.
The RNN and the PCP are both optimized for long-term prediction accuracy and thus make much better predictions. The PCP model achieves slightly better accuracy, and does it in a fraction of the time; to predict 200 steps in the future requires 200 applications of the RNN network, but only 4 of the PCP. This performance gap is significant, as planning requires evaluating hundreds of thousands of trajectories per episode.

heading: 3.4 MODEL ACCURACY VS REWARD

text:
Figure 6 shows the reward vs prediction error for 10 models at various points during online training in the Swimmer environment. These results show a clear relationship between low prediction error of the model and high reward, reinforce the importance of having a highly accurate long-range model of the environment. Taken together with the high error for ACPs in Figure 5, this explains that the RL performance of action-conditional predictors is limited by their inability to make accurate predictions at long timescales.
The left panel of Figure 6 shows a very vertical trend at the far left of the plot. We hypothesize that this is due to the changing distribution of the training data as a function of the predictor’s accuracy; once a predictor is making accurate predictions, the trajectories that it follows change from being nearly random to more focused. This then means that most of the progress late in training is on refining the predictions on a very narrow distribution of trajectories. These refinements continue to improve the RL performance of the predictor but have little impact on its accuracy along trajectories coming from a different policy.

heading: 3.5 COMPARISON TO OTHER APPROACHES

text:
In this experiment we evaluate the performance of ACP and PCP models compared to previous reinforcement learning methods, both model-free and model-based, on Swimmer-v2 and HalfCheetah-v2 from OpenAI Gym (Brockman et al., 2016)4. We also show the performance of an RNN model, which is identical to ACP but trained via backpropagation through time (BPTT) to minimize prediction error across the entire planning horizon, i.e. 100 steps for Swimmer and 20 steps for HalfCheetah. Since the PCP models predict R timesteps per network application (versus one forward pass through the network per timestep for ACP and RNN models) the PCP models are a factor of R faster to plan with in wall-clock time.
Our main model-based baseline is PETS (Chua et al., 2018), a state of the art probabilistic neural network-based MBRL algorithm which has been shown to equal or exceed model-free performance on short-horizon tasks. Similar to this work, PETS uses MPC and CEM for model-based control and aggregates a dataset online. On HalfCheetah we also compare with the model-based results from Nagabandi et al. (2017), which follows the same basic formula as our work but uses random shooting to find optimal plans instead of CEM. Our model-free baseline is PPO (Schulman et al., 2017) as implemented by Kostrikov (2018), a high-performing actor-critic method.
For each method we run five seeds and allow the algorithm to run to convergence, as we are interested in evaluating asymptotic performance. We train PPO for 100,000 trajectories. On Swimmer and HalfCheetah we use planning horizons of 100 and 20 timesteps respectively for the ACP, PCP, RNN, and PETS results. For each of the baseline methods we plot a horizontal line indicating the best score achieved by that method at any point in training, after averaging over the random seeds and over several consecutive episodes. We also show lines for the score achieved by using the groundtruth dynamics with the same planner as we use for PCP. In the case of Nagabandi et al. (2017) the score shown is that reported in their work; while the version of the HalfCheetah environment that they use is slightly different from the Gym one, we believe the numbers to be roughly comparable.
4We selected Swimmer and HalfCheetah to follow the main experiments from Nagabandi et al. (2017).
Figure 7 shows the results of this experiment. On Swimmer, which has a very long planning horizon, PCP achieves rewards more than 50% higher than the next-best method, while on HalfCheetah it equals the performance of PPO. We speculate that the extremely high rewards achieved by Chua et al. (2018) on HalfCheetah are due in part to the difference in settings for CEM betweeen our two works; while we use 3 steps of CEM optimization with 50 candidates per step, Chua et al. (2018) use 5 steps of optimization on 500 candidates.

heading: 4 DISCUSSION

text:
In this work we considered the problem of model bias in model-based reinforcement learning. In the largely deterministic environments considered, we show that optimal planning horizons can be large, beyond 100 timesteps. Over these horizons, NN-based models trained to minimize single-step prediction accuracy do not perform well. We demonstrate that better performance is possible with NN models by changing the loss function and the form of the model. Further experiments confirm that model accuracy is crucial to end task performance.
Our experiments make several simplifying assumptions, most notably the availability of unlimited samples and deterministic environment dynamics. Sample complexity would undoubtedly be improved by replacing the current overparameterized MLP architecture with something more efficient, an interesting future direction. Another important area for future work is understanding the interaction of long-range planning with stochasticity in the environment, including the development of generative models capable of predictions over long horizons.

heading: APPENDIX A PLANNING WITH A GROUND TRUTH MODEL


summaries: This paper investigates the problem of neural network quantization. The main idea is to employ an end-to-end precision highway to reduce the accumulated quantization error and meanwhile enable ultra-low precision in deep neural networks.  The experimental results on the 3- and 2-bit quantizations of ResNet-18/50 and 2-bit quantization of an LSTM model demonstrate the effectiveness of the proposed method.

summaries: This paper studies methods to improve the performance of quantized neural networks.  The paper is largely centered around the idea of "precision highways" (full-precision residual connections) that run in parallel to fully-quantized convolutions.  However, the paper also throws in a toolbox of other methods like distillation from a teacher network, a quantization method based on the Laplace distribution, and a fine tuning scheme.

abstractText: Neural network quantization has an inherent problem called accumulated quantization error, which is the key obstacle towards ultra-low precision, e.g., 2or 3-bit precision. To resolve this problem, we propose precision highway, which forms an end-to-end high-precision information flow while performing the ultralow-precision computation. First, we describe how the precision highway reduce the accumulated quantization error in both convolutional and recurrent neural networks. We also provide the quantitative analysis of the benefit of precision highway and evaluate the overhead on the state-of-the-art hardware accelerator. In the experiments, our proposed method outperforms the best existing quantization methods while offering 3-bit weight/activation quantization with no accuracy loss and 2-bit quantization with a 2.45 % top-1 accuracy loss in ResNet-50. We also report that the proposed method significantly outperforms the existing method in the 2-bit quantization of an LSTM for language modeling.

title: Eyeriss: An energy-efficient reconfigurable accelerator for deep convolutional neural networks. Solid-State Circuits, 2017

title: Bridging the accuracy gap for 2-bit quantized neural networks

title: Pact: Parameterized clipping activation for quantized neural networks

authors:
Junyoung Chung
Çaglar Gülçehre
KyungHyun Cho
Yoshua Bengio

title: Empirical evaluation of gated recurrent neural networks on sequence modeling

authors:
Felix A. Gers
Jürgen Schmidhuber
Fred A. Cummins

title: Learning to forget: Continual prediction with LSTM

venue: Neural Computation,

authors:
Song Han
Huizi Mao
William J. Dally

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

authors:
Kaiming He
Xiangyu Zhang
Shaoqing Ren
Jian Sun

title: Identity mappings in deep residual networks

venue: European Conference on Computer Vision (ECCV),

title: Effective quantization methods for recurrent neural networks

authors:
Gao Huang
Zhuang Liu
Laurens van der Maaten
Kilian Q. Weinberger

title: Densely connected convolutional networks

venue: Computer Vision and Pattern Recognition(CVPR),

title: Quantized neural networks: Training neural networks with low precision weights and activations

authors:
Hakan Inan
Khashayar Khosravi
Richard Socher

title: Tying word vectors and word classifiers: A loss framework for language modeling

title: gemmlowp: a small self-contained low-precision gemm library

venue: https: //github.com/google/gemmlowp,

title: Quantization and training of neural networks for efficient integer-arithmetic-only inference

authors:
Dongyoung Kim
Junwhan Ahn
Sungjoo Yoo

title: Zena: Zero-aware neural network accelerator

venue: Design & Test,

title: Visualizing the loss landscape of neural nets

title: Bi-real net: Enhancing the performance of 1-bit cnns with improved representational capability and advanced training algorithm

title: NVIDIA 8-bit inference width TensorRT

venue: GPU Technology Conference,

authors:
Asit K. Mishra
Debbie Marr

title: Apprentice: Using knowledge distillation techniques to improve low-precision network accuracy

authors:
Eunhyeok Park
Dongyoung Kim
Sungjoo Yoo

title: Energy-efficient neural network accelerator based on outlier-aware low-precision computation

venue: International Symposium on Computer Architecture

authors:
Ofir Press
Lior Wolf

title: Using the output embedding to improve language models

title: Xnor-net: Imagenet classification using binary convolutional neural networks

title: Bit fusion: Bit-level dynamically composable architecture for accelerating deep neural networks

authors:
Andrew Tulloch
Yangqing Jia

title: High performance ultra-low-precision convolutions on mobile devices

authors:
Wojciech Zaremba
Ilya Sutskever
Oriol Vinyals

title: Recurrent neural network regularization

title: Dorefa-net: Training low bitwidth convolutional neural networks with low bitwidth gradients

title: Balanced quantization: An effective and efficient approach to quantized neural networks

venue: Journal of Computer Science and Technology,

title: Towards effective low-bitwidth convolutional neural networks

heading: 1 INTRODUCTION

text:
Energy-efficient inference of neural networks is becoming increasingly important in both servers and mobile devices (e.g., smartphones, AR/VR devices, and drones). Recently, there have been active studies on ultra-low-precision inference using 1 to 4 bits (Rastegari et al., 2016; Hubara et al., 2016; Zhu et al., 2016; Zhou et al., 2016; 2017; Zhuang et al., 2018; Choi et al., 2018b; Liu et al., 2018; Choi et al., 2018a) and their implementations on CPU and GPU (Tulloch & Jia, 2017), and dedicated hardware (Park et al., 2018; Sharma et al., 2017). However, as will be explained in section 5.2, the existing quantization methods suffer from a problem called accumulated quantization error where large quantization errors get accumulated across layers, making it difficult to enable ultra-low precision in deep neural networks.
In order to address this problem, we propose a novel concept called precision highway where an end-to-end path of high-precision information reduces the accumulated quantization error thereby enabling ultra-low-precision computation. Our proposed work is similar to recent studies (Liu et al., 2018; Choi et al., 2018b) which propose utilizing pre-activation residual networks, where skip connections are kept in full precision while the residual path performs low-precision computation. Compared with these works, our proposed method offers a generalized concept of high-precision information flow, namely, precision highway, which can be applied to not only the pre-activation convolutional networks but also both the post-activation convolutional and recurrent neural networks. Our contributions are as follows.
• We propose a novel idea of network-level approach to quantization, called precision highway and quantitatively analyze its benefits in terms of the propagation of quantization errors and the difficulty of convergence in training based on the shape of loss surface.
• We provide the detailed analysis of the energy and memory overhead of precision highway based on the state-of-the-art hardware accelerator model. According to our experiments, the overhead is negligible while offering significant improvements in accuracy.
• We apply precision highway to both convolution and recurrent networks. We report a 3-bit quantization of ResNet-50 without accuracy loss and a 2-bit quantization with a very small accuracy loss. We also provide the sub 4-bit quantization results of long short-term memory (LSTM) for language modeling.

heading: 2 RELATED WORK

text:
Migacz (2017) presented an int8 quantization method that selects an activation truncation threshold to minimize the Kullback-Leibler divergence between the distributions of the original and quantized data. Jacob et al. (2017) proposed a quantization scheme that enables integer-arithmetic only matrix multiplications (practically, 8-bit quantization for neural networks). These methods are implemented on existing CPUs or GPUs (Jacob et al., 2015; ACL).
Hubara et al. (2016) presented a binarization method and demonstrated the performance benefit on a GPU. Rastegari et al. (2016) proposed a binary network called XNOR-Net in which a weight-binarized AlexNet gives the same accuracy as a full-precision one. Zhou et al. (2016) presented DoReFa-Net, which applies tanh-based weight quantization and bounded activation. Zhou et al. (2017) proposed a balanced quantization that attempts to balance the population of values on quantization levels. He et al. (2016b) proposed utilizing full precision for internal cell states in the LSTM because of their wide value distributions. This work is similar to ours in that high-precision data are selectively utilized to improve the quantized network. Our difference is proposing a network-level end-to-end flow of high-precision activation. Recently, Zhuang et al. (2018) presented 4-bit quantization with ResNet-50. They adopt Dorefa-net style weight quantization with static bounded activation, and improve accuracy by adopting multi-step quantization and knowledge distillation during fine-tuning. Mishra et al. (2017) proposed a trade-off between the number of channels and precision. Clustering-based methods have the potential to further reduce the precision (Han et al., 2015). However, they require a lookup table and full-precision computation, which makes them less hardware-friendly.
Recently, Choi et al. (2018b;a) and Liu et al. (2018) proposed utilizing full-precision on the skip connections in pre-activation residual networks1. Compared with those works, our proposed idea has a salient difference in that it offers a network-level solution and demonstrates that the end-to-end flow of high-precision information is crucial. In addition, our method is not limited to pre-activation residual networks, but general enough to be applied to both post-activation convolutional and recurrent neural networks.

heading: 3 PROPOSED METHOD

text:
In precision highway, we build a path from the input to output of a network to enable the end-toend flow of high-precision activation, while performing low-precision computation. Our proposed method was motivated (1) by a residual network where the signal, i.e., the activation/gradient in a forward/backward pass, can be directly propagated from one block to another (He et al., 2016a) and (2) by the LSTM, which provides an uninterrupted gradient flow across time steps via the inter-cell state path (Gers et al., 2000). Our proposed method focuses instead on improving the accuracy of quantized network by providing an end-to-end high-precision information flow.
In this section, we first describe the precision highway in the cases of residual network (section 3.1) and recurrent neural network (section 3.2). Then, we discuss practical issues to be addressed before application to other networks in section 3.3.

heading: 3.1 PRECISION HIGHWAY ON RESIDUAL NETWORK

text:
In the case of a residual network, we can form a precision highway by making high-precision skip connections. In this subsection, we explain how high-precision skip connections can be constructed to reduce the accumulated quantization error.
1This work was conducted in parallel with Choi et al. (2018b;a); Liu et al. (2018)
In the conventional residual block shown in Figure 1 (a), quantization (denoted as Q[0,1]k , k-bit linear quantization in range from 0 to 1) is applied to all of the activations after the activation function. In the figure, thick (thin) arrows represent high-precision (low-precision) activations. As the figure shows, the input of a residual block is first quantized, and the quantized input (x+ e in the figure), which contains the quantization error e, enters both the skip connection and residual path. The output of a residual block, y, is calculated as follows:
y = F (x+ e) + x+ e = F (x) + x+ er + e, (1)
where F () represents a residual function (typically, 2 or 3 consecutive convolutional layers). For simplicity of explanation, we assume that F (x+ e) can be decomposed into F (x) + er, where er represents the resulting quantization error of the residual path incurred by the quantization operations on the residual path as well as the quantization error in the input, e. As the equation shows, output y has two quantization error terms, that of residual path, er, and that of the skip connection, e.
Figure 1 (b) shows our idea of high-precision skip connection. Compared with Figure 1 (a), the difference is the location of the first quantization operation in the residual block. In Figure 1 (b), quantization is applied only to the residual path after the bifurcation to the residual path and skip connection. As shown in the figure, the skip connection now becomes a thick arrow, i.e., a high-precision path. The proposed idea gives the output of the residual block as follows:
y = F (x+ e) + x = F (x) + x+ er. (2)
As Equation 2 shows, the proposed idea eliminates the quantization error of skip connection e. Thus, only the quantization error of the residual path er remains in the output of the residual block. Note that all of the input activations of the residual path are kept in low precision. It enables us to perform low-precision convolution operations in the residual path. We keep high-precision activation only on the skip connection and utilize it only for the element-wise addition. As will be shown in our experiments, the overhead of computation and memory access cost is small since the element-wise addition is much less expensive than the convolution on the residual path, and the low-precision activation is accessed for the computation on the residual path.
As will be shown later, our method gives a smaller quantization error, and the gap between the quantization error of the existing method and that of ours becomes wider across layers. Because of the reduction of the accumulated quantization error, the proposed method offers much better accuracy than the state-of-the-art methods with an ultra-low precision of 2 and 3 bits.
Note also that, as shown in figure 1 (c), our idea can be applied to other types of residual blocks, including the full pre-activation residual block (He et al., 2016a) as proposed in some recent works (Choi et al., 2018a; Liu et al., 2018). However, our idea is general in that it is applicable to recurrent networks as well as post-activation convolutional networks. Especially, our proposed idea is advantageous over the existing ones since hardware accelerators tend to be designed assuming as the input non-negative input activations enabled by ReLU activation functions (Park et al., 2018; Kim et al., 2018). Contrary to the existing works (Choi et al., 2018a; Liu et al., 2018), we provide a detailed analysis of the effect of precision highway.

heading: 3.2 PRECISION HIGHWAY ON RECURRENT NEURAL NETWORK

text:
Figure 2 illustrates how the precision highway can be constructed on the LSTM (Gers et al., 2000). In time step t, the LSTM cell takes, as an input, new input xt, along with the results of the previous time step, output ht−1 and cell state ct−1. First, it calculates four intermediate signals: i (input gate), f (forget gate), g (gate gate), and o (output gate). Then, it produces two results, ct and ht, as follows:
it = σ(Wiixt + bii +Whih(t−1) + bhi), (3a)
ft = σ(Wifxt + bif +Whfh(t−1) + bhf ), (3b)
gt = tanh(Wigxt + big +Whgh(t−1) + bhg), (3c)
ot = σ(Wioxt + bio +Whoh(t−1) + bho), (3d)
ct = ft c(t−1) + it gt, (3e) ht = ot tanh(ct), (3f)
where σ represents a sigmoid function, the element-wise multiplication, W the weight matrix, and b the bias.
In the conventional LSTM operation, as Figure 2 (a) shows, the quantization (gray box denoted by Qk with the output value range as the superscript) is applied to all of the activations before computation. The results of a time step, ct and ht, are calculated based on such inputs with quantization errors. More specifically, cell state ct is calculated with the quantized, i.e., low-precision, inputs of ct−1, f , i, and g. Thus, cell state ct accumulates the quantization errors of those inputs. In addition, output ht also accumulates the quantization errors from its inputs, ct and o. Then, they are propagated to the next time steps. Thus, we have the problem of accumulated quantization error across the time steps. Such an accumulation of quantization error will prevent us from achieving ultra-low precision.
Figure 2 (b) shows how we can build the precision highway in the LSTM cell. The figure shows that the quantization operation is applied only to the inputs of matrix multiplication (a circle denoted with × in the figure). Thus, all of the other operations and their input activations are in high precision. Specifically, when calculating ct, the inputs are not quantized, which reduces the accumulation of quantization error on ct. The computation of ht can also reduce the accumulation of quantization error by utilizing high-precision inputs. The construction of such a precision highway allows us to propagate high-precision information, i.e., cell states ct and outputs ht, across time steps.
Note that we benefit from low-precision computation by performing low-precision matrix multiplications (in Equations 3a-3d), which dominate the total computation cost. In our proposed method, all of the element-wise multiplications in Equations 3e and 3f are performed in high precision. However, the overhead of this high-precision element-wise multiplications is negligible compared with the matrix multiplication in Equations 3a-3d. In addition, this method can be applied to other types of recurrent neural networks. For instance, the GRU (Chung et al., 2014) can be equipped with a precision highway, in a way similar to that shown in Figure 2 (b), by keeping high-precision output ht while performing low-precision matrix multiplications and high-precision element-wise multiplications.

heading: 3.3 PRACTICAL ISSUES WITH PRECISION HIGHWAY

text: In order to generalize our proposed idea to other networks in real applications, we need to address the following issues. First, in the case of feed-forward networks with identity path, our precision highway idea is applicable regardless of pre-activation or post-activation structure. We can exploit the benefit of reduced precision by applying quantization in front of matrix multiplications, while maintain the accuracy by handing the identity path in high precision. Second, in the case of non-residual feed-forward networks, the precision highway can be constructed by equipping them with additional skip connections. In the case of networks with multiple candidates for the precision highway, e.g., DenseNet, which has multiple parallel skip connections (Huang et al., 2017), we need to address a new problem of selecting skip connections to form a precision highway, which is left for future work.

heading: 4 TRAINING

text: In this section, we describe weight quantization and fine-tuning for weight/activation quantization.

heading: 4.1 LINEAR WEIGHT QUANTIZATION BASED ON LAPLACE DISTRIBUTION MODEL

text:
Figure 3 illustrates that a Laplace distribution can well fit the distributions of weights in full-precision trained networks. Thus, we propose modeling the weight distribution with Laplace distribution and selecting quantization levels for weights based on a Laplace distribution.
Given a distribution of weights and a target precision of k bits, e.g., 2 bits, the quantization levels are determined as follows. First, the quantization levels for k bits are pre-computed for the normalized Laplace distribution. We determine quantization levels that minimize L2 error on the normalized Laplace distribution. For instance, in case of the 2-bit quantization, the error is minimized when four quantization levels are placed evenly with a spacing of 1.53 µ, where µ is the mean of the absolute value of weights. Given the distribution of weights and the pre-calculated quantization levels on the normalized Laplace distribution for the given k bits, we determine the real quantization levels by multiplying the pre-computed quantization levels and the mean of the absolute value of weights.
Our proposed weight quantization is similar to the one in Choi et al. (2018a). Compared to it, ours is simpler in that only Laplace distribution model is utilized, and our experiments show that the precision highway together with the proposed simple weight quantization gives outstanding results.

heading: 4.2 FINE-TUNING FOR WEIGHT/ACTIVATION QUANTIZATION

text: Our quantization is applied during fine-tuning after training a full-precision network. As the baseline, we adopt the fine-tuning procedure in (Zhuang et al., 2018), where we perform incremental/progressive quantization. In contrast to (Zhuang et al., 2018), we first quantize activations and then weights in an incremental quantization. In addition, for each precision configuration, we perform teacher-student training to improve the quantized network (Zhuang et al., 2018; Mishra & Marr, 2017). As the teacher network, we utilize a deeper full-precision network, e.g., ResNet-101, compared to the student network, e.g., quantized ResNet-50. Note that, during fine-tuning, we apply quantization in forward pass while updating full-precision weights during backward pass.

heading: 5 EXPERIMENTS

heading: 5.1 EXPERIMENTAL SETUP

text:
We implemented the proposed method in PyTorch and Caffe2. We use two types of trained neural networks, ResNet-18/50 for ImageNet and an LSTM for language modeling (Zaremba et al., 2014; Press & Wolf, 2016; Inan et al., 2016). We evaluate 4-, 3-, and 2-bit quantizations for the networks.
For ResNet, we did test with single center crop of 256x256 resized image. We compare our proposed method with the state-of-the-art methods (Zhou et al., 2016; Zhuang et al., 2018; Choi et al., 2018b;a; Liu et al., 2018). Note that, for the teacher-student training, we use the same teacher network for both the baseline method (our implementation) (Zhuang et al., 2018) and ours. We also evaluate the effects of increasing the number of channels (Mishra et al., 2017) to recover from accuracy loss due to quantization. As in the previous works (Hubara et al., 2016; Zhou et al., 2017; Zhuang et al., 2018; Choi et al., 2018b;a; Liu et al., 2018; Mishra et al., 2017), we do not apply quantization to the first and last layers.
The LSTM has 2 layers and 300 cells on each layer. We used the Penn Treebank dataset and evaluated the perplexity per word. We compared the state-of-the-art method in (He et al., 2016b) and our proposed method.

heading: 5.2 ANALYSIS OF ACCUMULATED QUANTIZATION ERROR

text:
Figure 4 shows the quantization errors across layers in ResNet-50 when applying the state-of-the-art 4- bit quantization to activations. We prepared, from the same initial condition, two activation-quantized networks (one with precision highway and the other with low precision skip connection) where weights are not modified and only activations are quantized to 4 bits. As the metric of the quantization error, we utilize a metric based on the cosine similarity between the activation tensor of corresponding layer in the full-precision and quantized networks, respectively.
As the figure shows, in the existing method, the quantization errors become larger for deeper layers. It is because the quantization error generated in each layer is propagated and accumulated across layers. We call this accumulated quantization error. The accumulated errors become larger with more aggressive quantization, e.g., 2 bits, and cause poor performance, i.e., 4.8 % drop (Zhuang et al., 2018) from the top-1 accuracy of the full-precision ResNet-50 for ImageNet classification.
The accumulation of quantization errors is an inherent characteristic of a quantized network in both feed-forward and feed-back networks. In the case of a recurrent neural network, the quantization errors are propagated across time steps. As shown in Figure 4, our proposed precision highway significantly reduces the accumulated quantization errors, which enables 3-bit quantization without accuracy drop and much better accuracy in 2-bit quantization than the existing methods.

heading: 5.3 LOSS SURFACE ANALYSIS OF QUANTIZED MODEL TRAINING

text: Figure 5 visualizes the complexity of loss surface depending on the existence of precision highway. We obtained the figures by applying the method proposed by Li et al. (Li et al., 2017). Each figure represents loss surface seen from the local minimum we obtained from the training, i.e., the weight vector of the final trained model. The origin of the figure at (0, 0) corresponds to the weight vector of the local minimum. As shown in the figure 5 (d), the precision highway gives better loss surface (having lower and smoother surface near the minimum point and steep and simple surface elsewhere) than the existing quantization method. This characteristic helps stochastic gradient descent (SGD) method to quickly converge to a good local minimum offering better accuracy than the existing method.

heading: 5.4 EVALUATING THE ACCURACY OF QUANTIZED MODEL

text:
Table 1 shows the accuracy of 2-bit quantization for ResNet-18/50. We evaluate each of our proposed methods, Laplace, teacher, and highway, as shown in the table. When the highway box is unchecked the skip connection is branched after the quantization and when the teacher box is unchecked, we use the conventional cross-entropy loss. Compared with the full-precision accuracy, our 2-bit quantization (when all the methods were applied) gives a top-1 accuracy of 73.55 %, which is within 2.45 % of the full-precision accuracy and much better than the state-of-the-art method (Zhuang’s 70.8 %) having a top-1 accuracy loss of 4.8 %. Note that Zhuang’s implemented all the methods, incremental/progressive quantization and teacher-student training, in Zhuang et al. (2018). We presents the accuracy results of our own implementations of Zhuang’s method under the same amount of training time. Zhuang’s (ours) implemented only incremental and progressive methods while Zhuang’s + Teacher utilized our teacher network.
Table 1 shows the effects of the precision highway. Compared with our solution supporting only Laplace and teacher, the highway provides an additional gain of 1.85 % (71.70 % to 73.55 %) in the top-1 accuracy of ResNet-50. The effects of the Laplace method can be evaluated by comparing the result of our implementation of Zhuang’s (69.04 % of top-1 accuracy in ResNet-50) and that of our solution adopting the Laplace model (70.50 %) because these are the same except for the weight quantization method, i.e., tanh vs. Laplace based model. The Laplace method gives 1.46 % better accuracy. The table indicates that ResNet-18 also benefits from our proposed methods like ResNet-50.
Table 2 compares the additional accuracy loss of quantization methods with respect to full-precision accuracy. The table shows that ours significantly outperform the methods without precision-highway (DoReFa, Zhuang’s, and PACT). PACT new and Bi-Real utilize high-precision skip connections on pre-activation resiudal networks. Thus, they show comparable results to ours2. Note that our results in the table are obtained from the conventional post-activation residual network, which demonstrates the generality of our proposed precision highway. As will be shown below for the LSTM, our proposed method is generally applied to recurrent networks as well as feed forward ones.
Table 3 shows the impact of the precision of the precision highway. We obtained the results by varying the highway precision (without retraining) after obtaining the results with the full-precision highway. The table shows that 2-bit quantization with the 8-bit highway gives only 0.09 % and 0.40 % drops in the top-1 accuracy for ResNet-18 and ResNet-50, respectively, from that of the 2-bit quantization with the full-precision highway. Most importantly, our 3-bit quantization (with the 8-bit highway) gives the same accuracy as the full-precision network, i.e., 76.08 % in ResNet-50, which means that our proposed method reduces the precision of the ResNet-50 from 4 bits with Zhuang et al. (2018) down to 3 bits even with the 8-bit highway.
Table 4 shows the effects of two times wider channel under 2-bit quantization. We first doubled the number of channels in ResNet-18 and ResNet-50, and then quantized them with our methods. As the table shows, the wide ResNets give better accuracy than the full-precision ones even for 2-bit quantization, i.e., 73.80 % (77.35 %) in Table 4 vs. 70.15 % (76.00 %) of the full precision in Table 1
2We performed 1-bit activation/weight quantization for the post-act style ResNet-18. For a fair comparison, we didnt apply the teacher-student and progressive quantization method and instead adopted BN-retraining proposed in Bi-Real Net. Our 1-bit activation/weight ResNet-18 gives 56.73 / 80.11 % of Top-1/Top-5 accuracy, which is by 0.33 / 0.61 % higher than the result of Bi-Real Net, respectively.
for ResNet-18 (ResNet-50). It would be worth investigating how to minimize the channel size while meeting the full-precision accuracy with ultra-low precision, which is left for future work.
Table 5 lists the quantization results for the LSTM. We varied the bit configuration (weight, activation) and obtained the perplexity results (the lower, the better). The table shows that our proposed method significantly reduces the perplexity. Compared with the perplexity of full-precision model (92.84), our 4-bit quantization gives a very small increase of 3.3 % (92.84 to 95.94). The precision highway provides more gain for a more aggressive quantization. Specifically, it reduces the perplexity by 14.1 % (from 133.25 to 114.44) in the 2-bit quantization, (2,2). Compared with the state-of-the-art quantization of a similar LSTM (He et al., 2016b)3, ours offers much better results, i.e., a much smaller increase in perplexity, e.g., a 23.3 % increase (92.84 to 114.44 in Table 5) vs. a 39.4 % increase (109 to 152 in (He et al., 2016b)) in perplexity for 2-bit quantization.

heading: 5.5 HARDWARE COST EVALUATION OF QUANTIZED MODEL

text:
Figure 6 shows the chip area cost and energy consumption of ResNet-18 at different levels of precision on the state-of-the-art hardware accelerator (Chen et al., 2017). The accelerator is synthesized at 65 nm, 250 MHz, and 1.0 V. Each processing element (PE) consists of a multiply-accumulate (MAC) unit and local buffers. The PEs share global on-chip 2 MB static random access memory (SRAM) at 16-bit precision and the size of which is adjusted proportional to the precision. As the figure shows, the reduced precision offers significant reduction in chip area, e.g., 82.3 % reduction from 16 to 3 bits and energy consumption, e.g., 73.1 % from 16 to 3 bits. In the 2-bit case where the overhead of precision highway is the largest, the precision highway incurs only 3.9 % additional energy consumption due to the high-precision data while offering 4.1 % better accuracy than the case that precision highway is not adopted. The accelerator is already equipped large internal buffer for partial sum accumulation. Thus, precision highway incurs additional energy consumption mainly on the accesses to on-chip SRAM and main memory (dynamic random access memory, DRAM).
Table 6 compares the number of operations in three neural networks used in our experiments. The table explains why the high-precision operations incur such a small overhead in energy consumption. As the table shows, it is because the frequency of high-precision operations is much smaller than that of low-precision operations. For instance, the 2-bit LSTM network has one high-precision (in 32 bits) element-wise multiplication for every 800 2-bit multiplications.

heading: 6 CONCLUSION

text:
In this paper, we proposed the concept of end-to-end precision highway which can be applied to both feedforward and feedback networks and enable ultra-low precision in deep neural networks. The proposed precision highway reduces quantization errors by keeping high-precision activation from the input to output of the network with small computation costs. We described how it reduces the accumulated quantization error and presented quantitative analyses in terms of accuracy and hardware cost as well as training characteristics. Our experiments showed that the proposed method outperforms the state-of-the-art methods in the 3- and 2-bit quantizations of ResNet-18/50 and 2-bit quantization of an LSTM model. We believe that our work will serve as a step toward mixed precision networks for computational efficiency.
3 Note that we compared their relative change from the full-precision perplexity because the full-precision perplexity of the state-of-the-art method (109) is different from that of ours (92.84).


summaries: This paper proposed a general method for image restoration based on GAN. In particular, the latent variable z is optimized based on the MAP framework. And the results are obtained by G(z). This method looks reasonable to achieve good results. However, the idea is very related to Yeh et al.’s work which has already published but not mentioned at all.

summaries: The authors propose a method for image restoration, where the restored image is the MAP estimate. A pretrained GAN is utilized to approximate the prior distribution of the noise-free images. Then, the likelihood induces a constraint which is based on the degradation function. In particular, the method tries to find the latent point for which the GAN generates the image, which if gets degraded will match the given degraded image. Also, an optimization algorithm is presented that solves the proposed constrained optimization problem.

abstractText: We propose a general method for various image restoration problems, such as denoising, deblurring, super-resolution and inpainting. The problem is formulated as a constrained optimization problem. Its objective is to maximize a posteriori probability of latent variables, and its constraint is that the image generated by these latent variables must be the same as the degraded image. We use a Generative Adversarial Network (GAN) as our density estimation model. Convincing results are obtained on MNIST dataset.

authors:
Konstantinos Bousmalis
Nathan Silberman
David Dohan
Dumitru Erhan
Dilip Krishnan

title: Unsupervised pixel-level domain adaptation with generative adversarial networks

venue: In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR),

authors:
Patrizio Campisi
Karen Egiazarian

title: Blind image deconvolution: theory and applications

venue: CRC press,

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:
Christine Guillemot
Olivier Le Meur

title: Image inpainting: Overview and recent advances

venue: IEEE signal processing magazine,

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

title: Improved training of wasserstein gans

venue: In Advances in Neural Information Processing Systems,

authors:
Phillip Isola
Jun-Yan Zhu
Tinghui Zhou
Alexei A Efros

title: Image-to-image translation with conditional adversarial networks

venue: arXiv preprint,

authors:
Diederik P Kingma
Jimmy Ba

title: Adam: A method for stochastic optimization

venue: arXiv preprint arXiv:1412.6980,

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

title: Gradient-based learning applied to document recognition

venue: Proceedings of the IEEE,

authors:
Christian Ledig
Lucas Theis
Ferenc Huszár
Jose Caballero
Andrew Cunningham
Alejandro Acosta
Andrew P Aitken
Alykhan Tejani
Johannes Totz
Zehan Wang

title: Photo-realistic single image super-resolution using a generative adversarial network

venue: In CVPR,

authors:
Julien Mairal
Michael Elad
Guillermo Sapiro

title: Sparse representation for color image restoration

venue: IEEE Transactions on image processing,

authors:
Sung Cheol Park
Min Kyu Park
Moon Gi Kang

title: Super-resolution image reconstruction: a technical overview

title: Probabilities and statistics on riemannian manifolds: A geometric approach

venue: PhD thesis,

authors:
Alec Radford
Luke Metz
Soumith Chintala

title: Unsupervised representation learning with deep convolutional generative adversarial networks

venue: arXiv preprint arXiv:1511.06434,

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

title: Improved techniques for training gans

authors:
Casper Kaae Sønderby
Jose Caballero
Lucas Theis
Wenzhe Shi
Ferenc Huszár

title: Amortised map inference for image super-resolution

venue: arXiv preprint arXiv:1610.04490,

authors:
Dmitry Ulyanov
Andrea Vedaldi
Victor Lempitsky

title: Deep image prior

venue: arXiv preprint arXiv:1711.10925,

authors:
Zhou Wang
Eero P Simoncelli
Alan C Bovik

title: Multiscale structural similarity for image quality assessment

venue: In The Thrity-Seventh Asilomar Conference on Signals, Systems & Computers,

authors:
Raymond A Yeh
Chen Chen
Teck-Yian Lim
Alexander G Schwing
Mark Hasegawa-Johnson
Minh N Do

title: Semantic image inpainting with deep generative models

heading: 1 INTRODUCTION

text:
Image restoration has been researched for many years, but in a case-by-case way (Park et al., 2003; Mairal et al., 2008; Guillemot & Le Meur, 2014). Almost all image restoration algorithms are only designed for certain type of images or degradation. This research paradigm has some obvious disadvantages. It is exhausting to invent new algorithms or train new models for slightly different situations. Even if we can, those specialized solutions are not so elegant, because they are very unlike one another even though the problems they focus on are fundamentally so similar.
It is worth noting that any image degradation process can be abstracted as a many-to-one function. More specifically, for any given degradation process, one degraded image could be degraded from many possible original images. From that point of view, we propose a general method for various image restoration problems, such as denoising, deblurring, super-resolution and inpainting. Our algorithm chooses the most probable original image from all those possible original images, and uses it as the restoration of the given degraded image. To be more precise, the general image restoration is formulated as a constrained optimization problem. Its objective is to maximize a posteriori probability of latent variables, and its constraint is that the image generated by these latent variables must be the same as the degraded image.
Recent progress of density estimation techniques makes our algorithm possible. In the field of image generation, Generative Adversarial Networks (GANs) make a huge success in recent years (Goodfellow et al., 2014; Radford et al., 2015). As research continues, images generated by GANs become more and more realistic and clear, and training procedure of GANs become more and more stable (Salimans et al., 2016; Arjovsky et al., 2017). Besides being an image generation technique, GANs can also be used for density estimation. The generator part of a GAN is an implicit probability distribution model, and it will converge to a good estimator of the data distribution after training. In this work, we solve the inference problem with the probability density estimated by a GAN.
Figure 1 provides an illustration of how our image restoration method works. There are four dashed boxes from left to right in Figure 1, corresponding to four different phases of image capture and restoration process. Images in the first dashed box are original images, which are clear and undegraded. These images undergo a series of degradation in the second dashed box, and then are captured by our camera. In the image restoration process, we hope to estimate the original images with the degraded images we captured. As we pointed out before, every degraded image could be degraded from many possible original images. To be more precise, there is a particular subset of the original image manifold for any degraded image, and all image samples on the submanifold could be degraded to the given degraded image. Images in the third dashed box are those samples on the submanifold, and they are arranged in ascending order of log-likelihood from left to right. Images marked by yellow boxes are samples with the highest log-likelihood in their group, and they are placed in the last dashed box as restoration outputs.
Overall, the contributions of this work are mainly in two aspects:
1. We propose a general method for various image restoration problems. In the method, we explicitly use density information estimated by a GAN, an implicit model; and we directly solve the image restoration problem, an inference problem, with a GAN, a generative model. To the best of our knowledge, our work is the first to do those two things.
2. We propose a new algorithm to solve the optimization problem in our method. The new optimization algorithm is a first-order iterative algorithm for constrained problems, and it works well even for problems with highly nonlinear objective and constraints. These features make it especially suited to neural network related constrained optimization problems.

heading: 2 RELATED WORK

text:
The most similar work to ours is proposed in Yeh et al. (2017). They propose a semantic image inpainting method, which can generate missing content with a trained GAN. They search in the latent space of the trained GAN for the image which is closest to the corrupted image, and use the discriminator loss of the trained GAN as an indicator of how realistic their restoration is. Their motivation is similar to our work, but unfortunately, there is a major theoretical flaw in their method. Goodfellow et al. (2014) already prove that the discriminator is unable to identify how realistic an input is after several steps of training, if the GAN has enough capacity. During the training, the information of the data distribution gradually transfer from the discriminator to the generator. Ideally, the generator will have all the information of the data distribution while the discriminator will have none. That is why we use the generator of a trained GAN as an implicit probability density model in our method. Another difference between their work and ours is that they only focus on image inpainting problem, while our method applies to various image restoration problems.
The maximum a posteriori (MAP) has existed for a long time as a classic estimation method (Campisi & Egiazarian, 2016). But before GANs, people do not have a probability density model which is good enough to describe the distribution of images. After GANs make a huge success in image generation, researchers start to use them in image restoration tasks to get more realistic results (Isola et al., 2017; Bousmalis et al., 2017). Ledig et al. (2017) and Sønderby et al. (2016) try to use the MAP estimation on GANs to solve image super-resolution problem. However, they only use the MAP estimation implicitly and indirectly, while our method use it explicitly and directly. We suspect that all methods do implicit MAP estimation on GANs would require redesigning or retraining when the image restoration task changes, and this makes implicit methods not as general as our explicit method.
Ulyanov et al. (2017) is another work which is seemingly similar to ours, but they are actually quite different. Their work uses a randomly-initialized neural network as an image prior to solve various image restoration problems. The prior in their method is elaborate, neural network related but still handcrafted, while in our method the prior is learned from data. So our data-driven prior has better adaptability to specific image distribution.

heading: 3 MAXIMUM A POSTERIORI ON A SUBMANIFOLD

heading: 3.1 FORMULATION

text:
Consider a general image degradation model as follows,
x̃ = F (x,Ω) (1)
where x, x̃, and Ω represent the original image, the degraded image, and the parameters of the degradation model, respectively. The image degradation function F is a deterministic function. That means, given an original image x and a particular set of parameters Ω, the image degradation model will always produce the same degraded image x̃.
Our goal is to get a reasonable estimate of x with given x̃ and F . In this paper, we use the maximum a posteriori probability (MAP) estimate of x as the restoration of x̃. Compared to MSE-based method, MAP estimate of x is perceptually more convincing. We can perform inference by maximizing the posterior p(x,Ω|x̃):
{x̂, Ω̂} =argmax x,Ω p(x,Ω|x̃)
= argmax x,Ω p(x̃|x,Ω)p(x|Ω)p(Ω) p(x̃)
(2)
where x̂ and Ω̂ represent MAP estimate of x andΩ. Note that p(x̃) is always positive and does not depend on x andΩ, and typically we assume that x andΩ are independent. Therefore,
{x̂, Ω̂} =argmax x,Ω p(x̃|x,Ω)p(x)p(Ω) (3)
Note that x̃ = F (x,Ω) is a deterministic function, i.e., p(x̃|x,Ω) = δ(x̃− F (x,Ω)). Therefore, the estimation is equivalent to
{x̂, Ω̂} = argmax x,Ω p(x)p(Ω)
s.t. ‖x̃− F (x,Ω)‖ = 0 (4)
Here we write p(x) more specifically as pr(x), which stand for the probability density of real data distribution. We can estimate pr(x) with the generator part of a trained GAN, which is an implicit probability distribution model with distribution pG(x). The trained generator G represents a mapping from latent space of z to data distribution of original image x, i.e., pr(x) = pG(x), and pG(x) is a probability density function implicitly defined by x = G(z), where z is typically sampled from some simple distribution, such as the uniform distribution or the normal distribution. Assuming G : Rn → Rm is an injective function, the estimation is equivalent to
{ẑ, Ω̂} = argmax z,Ω pG(G(z))p(Ω)
s.t. ‖x̃− F (G(z),Ω)‖ = 0 (5)
and x̂ = G(ẑ) (6)
Generally the dimension of vector space of z is far lower than the dimension of vector space of x. Note that pG(x) is nonnegative if and only if x is on the low dimensional manifoldM defined by x = G(z), we can replace the probability density on the original space pG(G(z)) in Eq. (5) by the probability density on the manifold pM(z), and end up with the same estimation result ẑ. According to Pennec (2004), the probability density on the manifold can be calculated by
pM(z) = p(z)√
detGram( ∂G∂z1 , . . . , ∂G ∂zn
) (7)
where Gram represents the Gram matrix, and √ detGram( ∂G∂z1 , . . . , ∂G ∂zn ) is the volume of the parallelotope spanned by the vectors ( ∂G∂z1 , . . . , ∂G ∂zn
), so the square root of the Gram determinant can serve as a local scale factor. It has an effect similar to the Jacobian determinant, but we can only
use the Gram determinant here because G is a function from Rn to Rm, and generally n is much less than m.
The Gram matrix can be simply calculated byGram( ∂G∂z1 , . . . , ∂G ∂zn ) = V TV , where V is anm×n matrix, whose entries are given by V ij = ∂xi∂zj . Therefore, Eq. (5) is equivalent to
{ẑ, Ω̂} = argmax z,Ω p(z)p(Ω)√ detV TV
s.t. ‖x̃− F (G(z),Ω)‖ = 0 (8)
To solve the estimation problem efficiently, we represent probabilities in Eq. (8) in logarithmic space, i.e.,
{ẑ, Ω̂} = argmax z,Ω − 1 2 log detV TV + log p(z) + log p(Ω)
s.t. ‖x̃− F (G(z),Ω)‖ = 0 (9)
Matrix V TV is a positive-definite matrix, so we can use Cholesky decomposition to calculate log detV TV efficiently, i.e.,
log detV TV = 2 tr(log(chol(V TV ))) (10)
Finally we deduce a set of expressions which can be calculated directly, and their final outcome x̂ is the restored image we want, i.e.,
{ẑ, Ω̂} = argmax z,Ω − tr(log(chol(V TV ))) + log p(z) + log p(Ω)
s.t. ‖x̃− F (G(z),Ω)‖ = 0 (11)
and x̂ = G(ẑ) (12)
Note that (G(z),Ω) form a low dimensional manifold which is embedded in the space of (x,Ω), and the feasible solutions of Eq. (11) is on a subset of the manifold, which is defined by ‖x̃ − F (G(z),Ω)‖ = 0. So our method basically makes a MAP estimate on a submanifold.
Figure 2 is a toy example to show how our method works in a very visible way. Suppose there is a grayscale original image x, which has only three pixels. Then it is downsampled to only one pixel during the image capture process, and our task is to estimate xwith the one pixel image we captured. Suppose we have trained a GAN as an implicit model of data distribution of x. More specifically, the generator of the trained GAN represents a mapping from its input noise z to data distribution of x. The left part of Figure 2 describes the two dimensional latent space of z. We use the saturation of orange color to represent probability density level, i.e., a thicker orange color means a higher
probability density. So the uniform orange color in the latent space means that the input noise z is sampled from a uniform distribution.
Then the two dimensional vector z is mapped to three dimensional space of image x by the generator of the trained GAN, and the big orange square in the latent space of z is transformed into a twisted torus in the three dimensional data space of x, which is described in the right part of Figure 2. Some areas in space of z expand during the transformation, while other areas shrink. We can find this out by comparing the red and blue quadrilateral between the latent and data space. Therefore, the probability density on the torus is no longer uniform. The orange colors of the expanded areas become lighter, and the colors of the shrunken areas become thicker. Quantitatively speaking, the square root of the Gram determinant in Eq. (7) is the local area scale factor of the mapping, and its inverse, of course, is the local density scale factor.
The pale yellow plane in the data space represents the constraint in the toy example. All points on the plane would exactly be downsampled to the one pixel image we captured. So the intersection curve of the plane and the torus is the submanifold we are looking for, and that white curve is the feasible set of the toy problem. In this problem, p(z) is a constant in the domain, and degradation parameters Ω does not exist at all. According to Eq. (8), what we need to do is to maximize the inverse of the square root of the Gram determinant on the submanifold. In other words, the point with the thickest orange color on the intersection curve is the restored image x̂, the MAP estimate on the submanifold. We can find out that the method is both intuitive and rational for this toy example.

heading: 3.2 OPTIMIZATION ALGORITHM

text:
We propose a new optimization algorithm to solve Eq. (11). Note that the objective function and the equality constraint in Eq. (11) are both highly nonlinear, so gradient-based method seems a natural choice for the problem. Our algorithm is inspired by Projected Gradient Descent Method.
To solve a unconstrained problem with ordinary Gradient Descent Method, we take small steps in the direction of the negative gradient. To solve an constrained problem, we can try to use Projected Gradient Descent Method, take small step as usual and then project variables back onto the feasible set. But unfortunately, Projected Gradient Descent Method is only valid for problems with very simple feasible set, such as solution set of linear equations, some simple polyhedra and simple cone, etc. If constraints of a problem is too complex, like the constraint in Eq. (11), it is very hard to project variables back onto the feasible set.
To overcome this shortage, we propose a new optimization algorithm called Quasi Projected Gradient Descent Method. In our algorithm, the gradient information is not only used to improve the objective function, but helps to satisfy the constraints as well. Consider the standard form of continuous optimization problem,
minimize u f(u)
s.t. hi(u) = 0, i = 1, . . . ,m hj(u) ≤ 0, j = m+ 1, . . . ,m+ p
(13)
where f, hi, hj : Rn → R, and they are all highly nonlinear. Algorithm 1 is the proposed algorithm for the problem.
To solve Eq. (11) using the proposed algorithm, we only need to set u = {ẑ, Ω̂}, objective function f(u) = −(− tr(log(chol(V TV )))+log p(z)+log p(Ω)), and the only equality constraint function h1(u) = ‖x̃− F (G(z),Ω)‖. In the proposed algorithm, we first define an overall constraint function h(u) : Rn → R≥0, and the feasible set of the optimization problem is the region where h(u) = 0. In each iteration of the algorithm, we calculate the gradients of f(u) and h(u) at ui−1. If we take a small step in the direction of the negative gf , the value of f(u) will decrease a little bit, but it may have a unwanted impact on the value of h(u). In order to avoid this problem, we calculate g‖, the tangential component of gf on the isocontour of h(ui−1), which can be calculated by vector rejection of gf on gh. In each iteration, we actually take a small step in the direction of the negative g‖, the value of f(u) will still decrease, while it has almost no impact on the value of h(u). We also take a small step in the direction of the negative g⊥, i.e., gh itself, which is perpendicular to the isocontour of
Algorithm 1 Quasi Projected Gradient Descent Method Require: step size η‖ and η⊥, positive factors ci and cj , number of iterations n, small positive constant for numerical stability, initial guess u0
Define h(u) = m∑ i=1 ci · ‖hi(u)‖2 + m+p∑ j=m+1 cj · H(hj(u)) · ‖hj(u)‖2, where H represents the Heaviside step function for i = 1 to n do gf = ∇f(ui−1) gh = ∇h(ui−1) g‖ = gf − gf ·gh gh·gh+
· gh g⊥ = gh ui = ui−1 − η‖ · g‖ (or do with an advanced gradient descent optimizer) ui = ui − η⊥ · g⊥ (or do with another advanced gradient descent optimizer)
end for return un and f(un)
h(ui−1). Repeat these steps, and the sequence u will hopefully converge to the desired optimal solution.
Behaviors of our Quasi Projected Gradient Descent Method is similar to behaviors of the original Projected Gradient Descent Method. Consider a point u which is very close to the feasible region. The summation of two moves against g‖ and g⊥ is actually an inaccurate Projected Gradient Descent. That is why we name our method as “Quasi Projected Gradient Descent Method”.
Here we use the same toy example we used in Section 3.1, to show how our Quasi Projected Gradient Descent Method works. In Figure 3, solid curves in black and white are isocontour of constraint function h. The whiter the curve, the lower value of h it corresponds; Dashed lines in color are isocontour of objective function f . The redder the line, the lower value of f it corresponds. Note that the white solid curve is the feasible set of the toy problem, so intersection points of the white solid curve and the red dashed line in the latent space is ẑ in Eq. (11), while the intersection points in the data space is x̂ in Eq. (12).
Our iterative optimization algorithm starts from the bottom left corner of the latent space. The red vector is a gradient step of h. It is pointing towards the direction of the negative gh, and is perpendicular to the black solid curve, an isocontour of h. The green vector is a gradient step of f . It is pointing towards the direction of the negative gf , and is perpendicular to the yellow dashed
line, an isocontour of f . The blue vector is a projected gradient step. It is pointing towards the direction of the negative g‖, and is the tangential component of the green vector on the black solid curve, which can be calculated by vector rejection of the green vector on the red vector. We only plot green, red and blue vector for the first iteration to keep Figure 3 clean and easy to understand. Black vectors are combined gradient steps, which are vector sums of red and blue vectors. We move along these black vectors and we can find out that our optimization algorithm reaches a desired solution quickly.

heading: 4 EXPERIMENTS

text:
In this Section, we use MNIST dataset (LeCun et al., 1998) to test our image restoration method. The dataset is divided in 50k for the training set, 10k for each of the validation and test set. We use a WGAN-GP (Gulrajani et al., 2017) trained on the training set as the density estimation model. The architecture of the WGAN-GP we used is shown in Table 1 and Table 2, and we add a L2 weight decay term with decay parameter of 0.001 on the generator loss to prevent over-fitting. The network we used is very simple, but it is enough to prove the effectiveness of our method.
Table 1: Architecture of the generator
Kernel size Output shape
z - 16 Linear, tanh - 64× 4× 4 Deconv, tanh 5× 5 32× 7× 7 Deconv, tanh 5× 5 16× 14× 14 Deconv, sigmoid 5× 5 1× 28× 28
Table 2: Architecture of the discriminator
Kernel size Output shape
G(z) - 1× 28× 28 Conv, LeakyReLU 5× 5 16× 14× 14 Conv, LeakyReLU 5× 5 32× 7× 7 Conv, LeakyReLU 5× 5 64× 4× 4 Linear - 1
We use four different kinds of degradation to test the generality of our method. The first three kinds of degradation are relatively simple. They are 7× downsampling, making a 14×14 square hole in the center of the image, and adding Gaussian white noise with a standard deviation of 1.0, respectively. The last kind of degradation is a composition of a series of degradation in order, which are (a) adding linear motion blur by at most 14 pixels in any direction, (b) 4× downsampling, (c) adding uniform noise between -0.05 and 0.05, (d) randomly removing 10% of the pixels.
We use two independent ADAM optimizer (Kingma & Ba, 2014) with g‖ and g⊥ respectively in the Quasi Projected Gradient Descent Method. For all four kinds of degradation, we run the algorithm with the same settings. Settings for both ADAM optimizer are learning rate α = 0.01 (decayed linearly to 0), β1 = 0.9, β2 = 0.99, and number of iterations n = 500.
To the best of our knowledge, there is only one other general image restoration algorithm which can cope with various kinds of degradation like ours does. And that is the nearest neighbor algorithm. It searches in the training set for an image, whose degradation is the nearest to the given degraded image x̃. More specifically, if there are m points x(1), . . . ,x(m) in the training set, then
{x̂NN , Ω̂NN} =argmin x(i),Ω ‖x̃− F (x(i),Ω)‖ (14)
where x̂NN represents the restored image by the nearest neighbor algorithm. In case of multiple occurrences of the minimum objective values, we choose the one with the largest p(Ω̂NN ). Note that the empirical distribution of the training set is
pe(x) = 1
m m∑ i=1 δ(x− x(i)) (15)
If we replace p(x) with pe(x) rather than pG(x) in Eq. (4), or in other words, if the generative model in our method is extremely over-fitting, our method will degenerate to the nearest neighbor algorithm. So our method can be treated as a generalized method of the nearest neighbor algorithm. In the experiments, we use the nearest neighbor algorithm as a baseline, and compare its results with the proposed method.
Experimental results are shown in Table 3 and Table 4. MSE(x̃, F (x̂, Ω̂)) is a measure of how accurately a restored image can be degraded back to its input, and MSE(x, x̂) and MSSSIM(x, x̂) (Wang et al., 2003) are measures of the difference between the restoration and the ground truth. We can find out that our general image restoration method is better than the baseline method. The nearest neighbor algorithm cannot use the information of the probability density of images well, and that is the major disadvantage compared to our method.

heading: 5 CONCLUSIONS AND FUTURE WORK

text:
We propose a general image restoration method in this work. Compared with traditional image restoration algorithms, our method is much more powerful. Image restoration is an inherently illposed problem, so additional prior knowledge is needed. In our method, we use all prior knowledge of original images, i.e., the probability distribution of original images; and we use all prior knowledge of degradation, i.e., the degradation model itself. Traditional image restoration, by contrast, just uses a small part of the prior, typically some statistical properties. Besides, unlike our method, there is usually no guarantee that an output restoration from a traditional method can be degraded back accurately to its input. This makes restorations from a traditional method less plausible than restorations from our method.
For future work, We think our method can be straightforwardly extended to other domains which GANs are gifted in, such as video, audio and language. We will try to solve restoration problems and other inference problems in these domains with our paradigm. The convergence and other properties of the Quasi Projected Gradient Descent Method would be interesting as well.