summaries: This paper proposes a modified bellman equation for reinforcement learning that optimizes the maximum expected single step reward along a trajectory, instead of the maximum cumulative reward. This formulation is applied to the generation of molecules with optimized properties of interest. A recently published molecule generation algorithm, that constructs molecules step wise via the (predicted) chemical reactions of building blocks, is modified with this new bellman formulation, and shows modest improvements in optimizing for some HIV activity targets.

summaries: Motivated by the de novo drug design, this submission proposed a new objective in reinforcement learning, i.e., to maximize the expected maximum rather than the accumulated reward along trajectories. The authors defined the corresponding Bellman operator, and then proved its theoretical properties, including monotonicity and contraction. In the experiments, the authors first showed on a simulated grid that when compared with Q-learning, the proposed Max-Q algorithm can achieve higher maximum rewards along trajectories. Finally, the authors tested on de novo drug design task, by modifying the TD target in the previous PGFS algorithm. The new variant achieved better performance across different metrics.

summaries: This paper proposes a max reward instead of cumulative reward objective for reinforcement learning. This objective is primarily motivated by applications like chemical synthesis where the goal is for the RL agent to generate the most desirable state possible. The paper then defines the corresponding varaint of the Bellman operator (the max-Bellman operator) and proves tabular convergence guarantees by a contraction argument. Some experiments in a gridworld and simulated chemical synthesis indicate that this objective modification can improve prior algorithms.

abstractText: Reinforcement learning (RL) algorithms typically deal with maximizing the expected cumulative return (discounted or undiscounted, finite or infinite horizon). However, several crucial applications in the real world, such as drug discovery, do not fit within this framework because an RL agent only needs to identify states (molecules) that achieve the highest reward within a trajectory and does not need to optimize for the expected cumulative return. In this work, we formulate an objective function to maximize the expected maximum reward along a trajectory, propose a novel functional form of the Bellman equation, introduce the corresponding Bellman operators, and provide a proof of convergence. Using this formulation, we achieve state-of-the-art results on the task of synthesizable molecule generation that mimics a real-world drug discovery pipeline.

authors:
Sungsoo Ahn
Junsu Kim
Hankook Lee
Jinwoo Shin

title: Guiding deep molecular optimization with genetic exploration, 2020

title: Some applications of the theory of dynamic programming - A review

venue: Oper. Res.,

authors:
G Richard Bickerton
Gaia V Paolini
Jérémy Besnard
Sorel Muresan
Andrew L Hopkins

title: Quantifying the chemical beauty of drugs

venue: Nature chemistry,

authors:
John Bradshaw
Brooks Paige
Matt J. Kusner
Marwin H.S. Segler
José Miguel

title: HernándezLobato. A model to search for synthesizable molecules

authors:
Nathan Brown
Ben McKay
François Gilardoni
Johann Gasteiger

title: A graph-based genetic algorithm and its application to the multiobjective evolution of median molecules

venue: Journal of chemical information and computer sciences,

authors:
Nathan Brown
Marco Fiscato
Marwin HS Segler
Alain C Vaucher

title: Guacamol: benchmarking models for de novo molecular design

venue: Journal of chemical information and modeling,

authors:
Alexander Button
Daniel Merk
Jan A Hiss
Gisbert Schneider

title: Automated de novo molecular design by hybrid machine intelligence and rule-driven chemical synthesis

venue: Nature machine intelligence,

authors:
Kai-Wei Chang
Akshay Krishnamurthy
Alekh Agarwal
Hal Daumé III
John Langford

title: Learning to search better than your teacher

authors:
Devendra Singh Chaplot
Emilio Parisotto
Ruslan Salakhutdinov

title: Active neural localization

venue: In International Conference on Learning Representations,

authors:
Xinyun Chen
Yuandong Tian

title: Learning to perform local rewriting for combinatorial optimization

venue: Advances in Neural Information Processing Systems,

authors:
Scott Fujimoto
Herke van Hoof
David Meger

title: Addressing function approximation error in actor-critic methods

authors:
Scott Fujimoto
Herke Van Hoof
David Meger

venue: arXiv preprint arXiv:1802.09477,

authors: Connor W. Coley. The synthesizability of molecules proposed by generative models. Journal of Chemical Information

title: ISSN 1549-960X

venue: doi:

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

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

venue: ACS central science,

authors:
Sai Krishna Gottipati
Boris Sattarov
Sufeng Niu
Yashaswi Pathak
Haoran Wei
Shengchao Liu
Karam M.J. Thomas
Simon Blackburn
Connor W. Coley
Jian Tang
Sarath Chandar
Yoshua Bengio

title: Learning to navigate the synthetically accessible chemical space using reinforcement learning

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

authors:
Ryan-Rhys Griffiths
José Miguel Hernández-Lobato

title: Constrained bayesian optimization for automatic chemical design using variational autoencoders

venue: Chem. Sci.,

authors:
Tuomas Haarnoja
Aurick Zhou
Pieter Abbeel
Sergey Levine

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

venue: arXiv preprint arXiv:1801.01290,

title: Dynamic Programming and Markov Processes

authors:
Tommi Jaakkola
Michael I. Jordan
Satinder P. Singh

title: Convergence of stochastic iterative dynamic programming algorithms

venue: In Proceedings of the 6th International Conference on Neural Information Processing Systems,

title: A graph-based genetic algorithm and generative model/monte carlo tree search for the exploration of chemical space

venue: Chemical science,

authors:
Wengong Jin
Regina Barzilay
Tommi Jaakkola

title: Junction tree variational autoencoder for molecular graph generation

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

authors:
Takashi Kamihigashi
Cuong Le Van

title: Necessary and sufficient conditions for a solution of the bellman equation to be the value function: A general principle

authors:
Mathilde Koch
Thomas Duigou
Jean-Loup Faulon

title: Reinforcement learning for bioretrosynthesis

venue: bioRxiv,

authors:
Ksenia Korovina
Sailun Xu
Kirthevasan Kandasamy
Willie Neiswanger
Barnabas Poczos
Jeff Schneider
Eric P. Xing

title: ChemBO: Bayesian Optimization of Small Organic Molecules with Synthesizable Recommendations

authors:
Volodymyr Mnih
Koray Kavukcuoglu
David Silver
Andrei A Rusu
Joel Veness
Marc G Bellemare
Alex Graves
Martin Riedmiller
Andreas K Fidjeland
Georg Ostrovski

title: Human-level control through deep reinforcement learning

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

title: Asynchronous methods for deep reinforcement learning

venue: In International conference on machine learning,

authors:
Marcus Olivecrona
Thomas Blaschke
Ola Engkvist
Hongming Chen

title: Molecular de-novo design through deep reinforcement learning

venue: Journal of cheminformatics,

authors:
Giseung Park
Whiyoung Jung
Sungho Choi
Youngchul Sung

title: Model ensemble-based intrinsic reward for sparse reward reinforcement learning, 2020

title: Deep symbolic regression: Recovering mathematical expressions from data via risk-seeking policy gradients, 2020

authors:
Mariya Popova
Olexandr Isayev
Alexander Tropsha

title: Deep reinforcement learning for de novo drug design

venue: Science advances,

authors:
K.H. Quah
Chai Quek

title: Maximum reward reinforcement learning: A non-cumulative reward criterion

venue: Expert Systems with Applications,

authors:
Martin Riedmiller
Roland Hafner
Thomas Lampe
Michael Neunert
Jonas Degrave
Tom van de Wiele
Vlad Mnih
Nicolas Heess
Jost Tobias Springenberg

title: Learning by playing solving sparse reward tasks from scratch

venue: Proceedings of Machine Learning Research,

title: Proximal policy optimization algorithms

authors:
Chence Shi
Minkai Xu
Zhaocheng Zhu
Weinan Zhang
Ming Zhang
Jian Tang

title: Graph{af}: a flow-based autoregressive model for molecular graph generation

authors:
Martin Simonovsky
Nikos Komodakis

title: Graphvae: Towards generation of small graphs using variational autoencoders

venue: In International Conference on Artificial Neural Networks,

authors:
Satinder Singh
Tommi Jaakkola
Michael L Littman
Csaba Szepesvári

title: Convergence results for single-step on-policy reinforcement-learning algorithms

venue: Machine learning,

title: The asymptotic convergence-rate of q-learning

venue: In NIPS, pp

title: Best practices for qsar model development, validation, and exploitation

venue: Molecular informatics,

authors:
Alexander Trott
Stephan Zheng
Caiming Xiong
Richard Socher

title: Keeping your distance: Solving sparse reward tasks using self-balancing shaped rewards

title: Asynchronous stochastic approximation and q-learning

authors:
Silviu-Marian Udrescu
Max Tegmark. Ai

title: feynman: A physics-inspired method for symbolic regression

venue: Science Advances,

authors:
Christopher J.C.H. Watkins
Peter Dayan

title: Technical note: q -learning

venue: Mach. Learn.,

title: Smiles, a chemical language and information system. 1. introduction to methodology and encoding rules

authors:
Robin Winter
Floriane Montanari
Andreas Steffen
Hans Briem
Frank Noé
Djork-Arné Clevert

title: Efficient multi-objective molecular optimization in a continuous latent space

authors:
Jiaxuan You
Bowen Liu
Rex Ying
Vijay S. Pande
Jure Leskovec

title: Graph convolutional policy network for goal-directed molecular graph generation

authors:
Jiaxuan You
Bowen Liu
Zhitao Ying
Vijay Pande
Jure Leskovec

venue: In Advances in neural information processing systems,

authors:
Zeyu Zheng
Junhyuk Oh
Satinder Singh

title: On learning intrinsic rewards for policy gradient methods

authors:
Zhenpeng Zhou
Steven M. Kearnes
Li Li
Richard N. Zare
Patrick Riley

title: Optimization of molecules via deep reinforcement learning

heading: 1 INTRODUCTION

text:
Reinforcement learning (RL) algorithms typically try to maximize the cumulative finite horizon undiscounted return, R(τ) = ∑T t=0 rt, or the infinite horizon discounted return, R(τ) = ∑∞ t=0 γ
trt. rt is the reward obtained at time step t, γ is the discount factor in the range [0, 1), and τ is the agent’s trajectory. τ consists of actions (a) sampled from the policy (π(· | s)) and states (s′) sampled from the probability transition function P (s′|s, a) of the underlying Markov Decision Process (MDP). The action-value function Qπ(s, a) for a policy π is given by
Qπ(s, a) = E τ∼π [R(τ)|(s0, a0) = (s, a)]
The corresponding Bellman equation for Qπ(s, a) with the expected return defined as R(τ) =∑∞ t=0 γ
trt is Qπ(st, at) = Est+1∼P (·|st,at)
at+1∼π(·|st+1) [r(st, at) + γQ
π (st+1, at+1)]
This Bellman equation has formed the foundation of RL. However, we argue that optimizing for only the maximum reward achieved in an episode is also an important goal. Reformulating the RL problem to achieve the largest reward in an episode is the focus of this paper, along with empirical demonstrations in one toy and one real-world domain.
In the de novo drug design pipeline, molecule generation tries to maximize a given reward function. Existing methods either optimize for the expected cumulative return, or for the reward at the end of the episode, and thus fail to optimize for the very high reward molecules that may be encountered in the middle of an episode. This limits the potential of several of these reinforcement learning based drug design algorithms. We overcome this limitation by proposing a novel functional formulation of the Bellman equation:
Qπmax(st, at) = Est+1∼P (·|st,at) at+1∼π(·|st+1) [max (r(st, at), γQ π max(st+1, at+1))] (1)
Other use cases of this formulation (i.e., situations where the single best reward found, rather than the total rewards, are important) are - symbolic regression (Petersen (2020), Udrescu & Tegmark (2020)) which is interested in finding the single best model, active localization (Chaplot et al. (2018)) must find the robot’s one most likely pose, green chemistry (Koch et al. (2019)) wants to identify the one best product formulation, and other domains that use RL for generative purposes.
This paper’s contributions are to:
• Derive a novel functional form of the Bellman equation, called max-Bellman, to optimize for the maximum reward in an episode.
• Introduce the corresponding evaluation and optimality operators, and prove the convergence of Q-learning with the max-Bellman formulation.
• Test on a toy environment and draw further insights with a comparison between Q-learning and Q-learning with our max-Bellman formulation.
• Use this max-Bellman formulation to generate synthesizable molecules in an environment that mimics the real drug discovery pipeline, and demonstrate significant improvements over the existing state-of-the-art methods.

heading: 2 RELATED WORK

text: This section briefly introduces fundamental RL concepts and the paper’s main application domain.

heading: 2.1 REINFORCEMENT LEARNING

text:
Bellman’s dynamic programming paper (Bellman, 1954) introduced the notions of optimality and convergence of functional equations. This has been applied in many domains, from control theory to economics. The concept of an MDP was proposed in the book Dynamic Programming and Markov Processes (Howard, 1960) (although some variants of this formulation already existed in the 1950s). These two concepts of Bellman equation and MDP are the foundations of modern RL. Q-learning was formally introduced in (Watkins & Dayan, 1992) and different convergence guarantees were further developed in (Jaakkola et al., 1993) and (Szepesvári, 1997). Q-learning convergence to the optimal Q-value (Q?) has been proved under several important assumptions. One fundamental assumption is that the environment has finite (and discrete) state and action spaces and each of the states and actions can be visited infinitely often. The learning rate assumption is the second important assumption, where the sum of learning rates over infinite episodes is assumed to go to infinity in the limit, whereas the sum of squares of the learning rates are assumed to be a finite value (Tsitsiklis, 1994; Kamihigashi & Le Van, 2015). Under similar sets of assumptions, the on-policy version of Q-learning, known as Sarsa, has also been proven to converge to the optimal Q-value in the limit (Singh et al., 2000).
Recently, RL algorithms have seen large empirical successes as neural networks started being used as function approximators (Mnih et al., 2016). Tabular methods cannot be applied to large state and action spaces as these methods are linear in the state space and polynomial in the action spaces in both time and memory. Deep reinforcement learning (DRL) methods on the other hand, can approximate the Q-function or the policy using neural networks, parameterized by the weights of the corresponding neural networks. In this case, RL algorithms easily generalize across states, which improves the learning speed (time complexity) and sample efficiency of the algorithm. Some popular Deep RL algorithms include DQN (Mnih et al., 2015), PPO (Schulman et al., 2017), A2C (Mnih et al., 2016), SAC (Haarnoja et al., 2018), TD3 (Fujimoto et al., 2018b), etc.

heading: 2.2 DE NOVO DRUG DESIGN

text:
De novo drug design is a well-studied problem and has been tackled by several methods, including evolutionary algorithms (Brown et al. (2004); Jensen (2019); Ahn et al. (2020)), generative models (Simonovsky & Komodakis (2018); Gómez-Bombarelli et al. (2018); Winter et al. (2019); Jin et al. (2018); Popova et al. (2018); Griffiths & Hernández-Lobato (2020); Olivecrona et al. (2017)), and reinforcement learning based approaches (You et al. (2018a); Zhou et al. (2018)). While the effectiveness of the generated molecules using these approaches has been demonstrated on standard benchmarks such as Guacamol (Brown et al. (2019)), the issue of synthesizability remains a problem. While all the above approaches generate molecules that optimize a given reward function, they do not account for whether the molecules can actually be effectively synthesized, an important practical consideration. Gao & Coley (2020) further highlighted this issue of synthesizability by using a synthesis planning program to quantify how often the molecules generated using these existing approaches can be readily synthesized. To attempt to solve this issue, Bradshaw et al. (2019) used a
variational auto-encoders based approach to optimize the reward function with single-step reactions. Korovina et al. (2019) employed a random selection of reactants and reaction conditions at every time step of a multi-step process. PGFS (policy gradient for forward synthesis) from Gottipati et al. (2020) generates molecules via multi-step chemical synthesis and simultaneously optimized for the given reward function. PGFS leveraged TD3 algorithm (Fujimoto et al. (2018a)), and like existing approaches, optimizes for the usual objective of total expected discounted return.

heading: 3 METHOD

text:
This section briefly describes the previous attempts at optimizing for the maximum reward in an episode, defines the Q-function and new functional form of the Bellman equation, defines the corresponding max-Bellman operators, and proves its convergence properties.
Quah & Quek (2006) also try to formulate a maximum reward objective function. They define the Q-function and derive the max-Bellman equation in the following way (rephrased according to this paper’s notation):
Qπmax(st, at) , E [ max t′≥t ( γt ′−tr(st′ , at′) ) | (st, at), π ] ,∀(st, at) ∈ S ×A (2)
Then, the corresponding functional form of Bellman equation (i.e., the max-Bellman formulation) was derived as follows:
Qπmax(st, at) = E [ max t′≥t ( γt ′−tr(st′ , at′) ) | (st, at), π ] = Est+1∼P (·|st,at)
at+1∼π(·|st′ ) max
( r(st, at),E [ max t′≥t+1 ( γt ′−tr(st′ , at′) ) | (st+1, at+1), π ]) = Est+1∼P (·|st,at)
at+1∼π(·|st+1) max (r(st, at), γQ
π max(st+1, at+1))
(3)
However, the second equality is incorrect, which can be shown with a counter example. Consider an MDP with four states and a zero-reward absorbing state. Assume a fixed deterministic policy and γ close to 1. Let s1 be the start state, with deterministic reward r(s1) = 1. With probability 1, s1 goes to s2. Let r(s2) = 0, and with equal probability 0.5 it transitions to either s3 or s4. The immediate reward r(s3) = 2 and r(s4) = 0, after that it always goes to the absorbing state with 0 rewards thereafter. Since there can be only 2 trajectories, one with a maximum reward of 2 and the other with a maximum reward of 1, we have Qπmax(s1) = 1.5, but Q π max(s2) = 1, and max(r(s1), Q π max(s2)) = 1 6= 1.5. This is because the expectation and max operators are not interchangeable.
While the counter example above is not applicable in the current setting of PGFS (as it has a deterministic environment and uses a deterministic policy gradient algorithm (TD3)), the definition of the Q-function given in equation-2 does not generalize to stochastic environments. Moreover, in order to be able to accommodate multiple possible products of a chemical reaction and to truly leverage a stochastic environment (and stochastic policy gradient algorithms), the Q-function should be able to recursively optimize for the expectation of maximum of reward at the current time step and future expectations. Therefore, we define the Q-function as:
Qπmax(st, at) = Est+1∼P (·|st,at) at+1∼π(·|st+1)
[ max ( r(st, at), γEst+2∼P (·|st+1,at+1)
at+2∼π(·|st+2) [max (r(st+1, at+1), ...)] )] (4)
Then, the corresponding functional form of Bellman equation (i.e., max-Bellman formulation) can be obtained as follows:
Qπmax(st, at) = Est+1∼P (·|st,at) at+1∼π(·|st+1) max (r(st, at), γQ π max(st+1, at+1)) (5)
While the work of Quah & Quek (2006) is focused on deriving the various forms of the max-Bellman equations, the major contributions of our paper are to 1) propose the max-Bellman equation with
a particular motivation towards drug discovery, 2) define the corresponding operators, 3) provide their convergence proofs, and 4) validate the performance on a toy domain and a real world domain (de-novo drug design). Other related ideas and formulations are described in Appendix section-B.
Based on Equation 5, we can now define the max-Bellman evaluation operator and the max-Bellman optimality operator. For any function Q : S ×A→ R and for any state-action pair (s, a),
(MπQ)(s, a) , max ( r(s, a), γEs′∼P (·|s,a)
a′∼π(·|s′) [Q(s′, a′)]
)
(M?Q)(s, a) , max ( r(s, a), γEs′∼P (·|s,a) [ max a′∈A Q(s′, a′) ]) M? and Mπ : (S ×A → R)→ (S ×A → R) are operators that takes in a Q function and returns another modified Q function by assigning the Q value of the state s, action a, to be the maximum of the reward obtained at the same state and action (s, a) and the discounted future expected Q value.
Proposition 1. The operators have the following properties.
• Monotonicity: let Q1, Q2 : S ×A → R such that Q1 ≥ Q2 element-wise. Then,
MπQ1 ≥MπQ2 and M?Q1 ≥M?Q2
• Contraction: both operators are γ-contraction in supremum norm i.e., for any Q1, Q2 : S ×A → R,
‖MπQ1 −MπQ2‖∞ ≤ γ‖Q1 −Q2‖∞ (6) ‖M?Q1 −M?Q2‖∞ ≤ γ‖Q1 −Q2‖∞ (7)
Proof. We will provide a proof only for M?. The proof of Mπ is similar and is provided in Section A of the Appendix.
Monotonicity: Let Q1 and Q2 be two functions such that Q1(s, a) ≥ Q2(s, a) for any state-action pair (s, a) ∈ S ×A. We then have:
max a′∈A
Q1(s, a ′) ≥ Q2(s, a),∀(s, a)
By the definition of max, we obtain:
max a′∈A
Q1(s, a ′) ≥ max
a′∈A Q2(s, a
′),∀s
and by linearity of expectation, we have: γEs′∼P (·|s,a) [ max a′∈A Q1(s ′, a′) ] ≥ γEs′∼P (·|s,a) [ max a′∈A Q2(s ′, a′) ] ,∀(s, a)
Since,
M?Q1(s, a) ≥ γEs′∼P (·|s,a) [ max a′∈A Q1(s ′, a′) ] we get:
M?Q1(s, a) ≥ γEs′∼P (·|s,a) [ max a′∈A Q2(s ′, a′) ] Moreover, because M?Q1(s, a) ≥ r(s, a), we obtain :
M?Q1(s, a) ≥ max ( r(s, a), γEs′∼P (·|s,a) [ max a′∈A Q2(s ′, a′) ]) = M?Q2(s, a)
which is the desired result.
Contraction: Denote fi(s, a) = γEs′∼P (·|s,a) [maxa′∈AQi(s′, a′)], the expected action-value function of the next state. By using the fact that max(x, y) = 0.5(x+ y + |x− y|),∀(x, y) ∈ R2, we obtain:
max(r, f1)−max(r, f2) = 0.5 (r + f1 + |r − f1|)− 0.5 (r + f2 + |r − f2|) = 0.5 (f1 − f2 + |r − f1| − |r − f2|) ≤ 0.5 (f1 − f2 + |r − f1 − (r − f2)|) = 0.5 (f1 − f2 + |f1 − f2|) ≤ |f1 − f2|
Therefore
‖M?Q1 −M?Q2‖∞ = ‖max(r, f1)−max(r, f2)‖∞ ≤ ‖f1 − f2‖∞ ≤ γ‖max
a′ Q1(·, a′)−max a′ Q2(·, a′)‖∞
≤ γ‖Q1 −Q2‖∞ (max is a non-expansion)
The left hand side of this equation represents the largest difference between the two Q-functions. Recall that γ lies in the range [0, 1) and hence all differences are guaranteed go to zero in the limit. The Banach fixed point theorem then lets us conclude that the operator M? admits a fixed point.
We denote the fixed point of M? by Q?max. Based on equation 5, we see that Qπmax is the fixed point of Mπ. In the next proposition, we will prove that Q?max corresponds to the optimal action-value function in the sense that Q?max = maxπ Q π max.
Proposition 2 (Optimal policy). The deterministic policy π? is defined as π?(s) = arg maxa∈AQ ? max(s, a). π
?, the greedy policy with respect to Q?max, is the optimal policy and for any stationary policy π, Qπ ?
max = Q ? max ≥ Qπmax.
Proof. By the definition of greediness and the fact that Q? is the fixed point of M?, we have: π?(s) = arg maxa∈AQ ? max(s, a) ⇒ Mπ ? Q? = M?Q?max = Q ? max. This proves that Q ? max is the fixed point of the evaluation operator Mπ ?
, which implies that Q?max is the action-value function of π?.
For any function Q : S × A → R and any policy π, we have M?Q ≥ MπQ. Using monotonicity, we have
(M?)2Q = M?(M?Q) ≥M?(MπQ) ≥Mπ(MπQ) = (Mπ)2Q. (8)
We then use induction to show that for any n ≥ 1, (M?)nQ ≥ (Mπ)nQ. As both operators are contractions, by the fixed-point theorem, (M?)nQ and (Mπ)nQ converge to Q?max and Q π max, respectively, when n goes to infinity. We conclude then that Q?max ≥ Qπmax.
Thus, we have shown that and optimality operator defined based on our novel formulation of Bellman equation converges to a fixed point (Proposition 1) and that fixed point is the optimal policy (Proposition 2).

heading: 4 EXPERIMENTS

text: This section shows the benefits of using max-Bellman in a simple grid world and in the real-world domain of drug discovery.

heading: 4.1 TOY EXAMPLE - GOLD MINING ENVIRONMENT

text:
Our first demonstration is on a toy domain with multiple goldmines in a 3 × 12 grid 1. The agent starts in the bottom left corner and at each time step, can choose from among the four cardinal actions: up, down, left and right. The environment is deterministic with respect to the action transitions and the agent cannot leave the grid. All states in the grid that are labeled with values other than -1 represent goldmines and each value represents the reward that the agent will collect upon reaching that particular state. Transitions into a non-goldmine state results in a reward of -1. A goldmine’s reward can be accessed only once and after it has been mined, its goldmine status is revoked, and the reward received upon further visitation is -1. The episode terminates after 11 time steps and the discount factor is γ = 0.99. The observation is a single integer denoting the state number of the agent. Thus, this is a non-Markovian setting since the environment observation does not communicate which goldmines have already been visited, and also because the time step information is not included in the state observation.
The environment is shown in Figure 1. If the agent goes up to the top row and continues to move right, it will only get a cumulative return of 26.8. If it instead traverses the bottom row to the right, it can receive a cumulative return of 27.5, which is the highest cumulative return possible in this environment.
We test both Q-learning and Max-Q (i.e. Q-learning based on our proposed max-Bellman formulation), on this environment. As usual, the one step TD update rule for Q-learning is:
Q(st, at) = Q(st, at) + α(rt + γmax a
Q(st+1, a)−Q(st, at))
The one step TD update rule for Max-Q is:
Q(st, at) = Q(st, at) + α(max(rt, γmax a
Q(st+1, a))−Q(st, at))
For both algorithms, we use learning rate α = 0.001, and decay epsilon from 0.2 to 0.0 linearly over 50000 episodes, after which remains fixed at 0. Figure 2 shows the learned Q-values and Figure 3 shows a difference in the final behavior learned by the two algorithms. Q-learning seems to prefer the path with highest cumulative return (along the bottom row) while Max-Q prefers the path with highest maximum reward (reward of +9 in the top row). The learned policies consistently reflect this behavior. Over 10 independent runs of each algorithm, Q-learning’s policy always converges to moving along the bottom row and achieves expected cumulative return of 27.5. On the other hand, Max-Q always prefers the top row and achieves expected cumulative return of 26.8, but accomplishes its goal of maximizing the expected maximum reward in an episode (i.e., reaching the highest rewarding state). Also, Max-Q has worse initial learning performance in terms of the cumulative return, which can be explained by the agent wanting to move from the bottom row to the top row, despite the -8 penalty. This desire to move upwards at any cost is because the agent is pulled towards the +9, and does not care about any intermediate negative rewards that it may encounter.
Figure 4 shows a quantitative comparison between Q-learning and Max-Q. Figure 4a shows a comparison in terms of the average episodic return. Q-learning achieved optimal performance in terms of cumulative return and therefore has no incentive to direct the agent towards the maximum
1The environment and algorithm code is submitted as supplementary material and will be open sourced after acceptance for replication purposes.
(a)
(b)
reward of +9. Max-Q on the other hand, converges to the path of following the top row to reach the highest reward of +9. This can be seen more clearly in Figure 4b, which shows a comparison of the maximum reward obtained in each episode. Each curve is averaged over 10 runs, and the shaded region represents 1 standard deviation. We also perform experiments in a fully Markovian setting for a similar environment. These results are shown in the Appendix section-C.

heading: 4.2 DRUG DISCOVERY

text:
We give a brief summary of PGFS (Gottipati et al. (2020)) for de novo drug design here and then incorporate the max-Bellman formulation derived above. PGFS operates in the realm of off-policy continuous action space algorithms. The actor module Π that consists of f and π networks predicts a continuous action a (that is in the space defined by the feature representations of all second reactants). Specifically, the f network takes in the current state s (reactant-1 R(1)) as input and outputs the best reaction template T . The π network takes in both R(1) and T as inputs and outputs the continuous action a. The environment then takes in a and computes k closest valid second reactants (R(2)). For each of these R(2)s, we compute the corresponding product of the chemical reaction between R(1) and R(2), compute the reward for the obtained produce and choose the product (next state, st+1) that corresponds to the highest reward. All these quantities are stored in the replay buffer. The authors leveraged TD3 (Fujimoto et al., 2018a) algorithm for updating actor (f , π) and critic (Q) networks. More specifically, the following steps are followed after sampling a random minibatch from the buffer (replay memory):
First, the actions for the next time step (Ti+1 and ai+1) are computed by passing the state input (R(1)i+1) through the target actor network (i.e., the parameters of the actor networks are not updated in this process). Then, the one step TD target is computed:
yi = ri + γ min j=1,2
Critic-target({R(1)i+1, Ti+1}, ai+1)
In the proposed approach “MB (max-Bellman) + PGFS", we compute the one-step TD target as
yi = max[ri, γ min j=1,2
Critic-target({R(1)i+1, Ti+1}, ai+1)]
The critic loss and the policy loss are defined as: Lcritic = ∑ i |yi −Q({R(1)i , Ti}, ai)| 2
Lpolicy = − ∑ i Critic(R(1)i ,Actor(R (1) i ))
Only a few reaction templates (about 8 percent) are valid for a given state (reactant-1). Thus, when the actor networks were randomly initialized, they choose an invalid template most of the time during initial phases of training. Thus, minimizing a cross entropy loss between the template predicted by the f-network and the actual valid template chosen enables faster training i.e., like the PGFS algorithm, we also minimize an auxiliary loss to enable stronger gradient updates during the initial phases of training.
Lauxil = − ∑ i (T (1) ic , log(f(R (1) ic )))
and, the total actor loss Lactor is a summation of the policy loss Lpolicy and auxiliary loss Lauxil.
Lactor = Lpolicy + Lauxil
The parameters θQ of the Q-network are updated by minimizing the critic loss Lcritic, and the parameters θf and θπ of the actor networks f and π are updated my minimizing the actor loss Lactor. A more detailed description of the algorithm, pseudo code and hyper parameters used in given in Section D of the Appendix.
We compared the performance of the proposed formulation “MB (max-Bellman) + PGFS” with PGFS, and random search (RS) where reaction templates and reactants are chosen randomly at every time step, starting from initial reactant randomly sampled from ENAMINE dataset (which contains a set of roughly 150,000 reactants). We evaluated the approach on five rewards: QED (that measures the drug like-ness: Bickerton et al. (2012)), clogP (that measures lipophilicity: You et al. (2018b)) and activity predictions against three targets (Gottipati et al. (2020)): HIV-RT, HIV-INT, HIV-CCR5. While PGFS demonstrated state-of-the-art performance on all these rewards across different metrics (maximum reward achieved, mean of top-100 rewards, performance on validation set, etc.) when compared to the existing de novo drug design approaches (including the ones that do not implicitly or explicitly account for synthesizability and just optimize directly for the given reward function), we show that the proposed approach (PGFS+MB) performed better than PGFS (i.e., better than the existing state-of-the-art methods) on all the five rewards across all the metrics. For a fairness in comparison, like PGFS, we only performed hyper parameter tuning over policy noise and noise clip and trained only for 400,000 time steps. However, in the proposed formulation, we noticed that the performance is sensitive to the discount factor γ and the optimal γ is different for each reward.
Table 3 compares the maximum reward achieved during the entire course of training of 400,000 time steps. We notice that the proposed approach PGFS+MB achieved highest reward compared to existing state-of-the-art approaches. Table 4 compares the mean (and standard deviation) of top 100 rewards (i.e., molecules) achieved by each of the methods over the entire course of training with and without applicability domain (AD) (Tropsha (2010), Gottipati et al. (2020)). We again note that the proposed formulation performed better than existing methods on all three rewards both with and without AD. In Figure 5, we compare the performance based on the rewards achieved starting from a fixed validation set of 2000 initial reactants. For all the three HIV reward functions, we notice that PGFS+MB performed better than existing reaction-based RL approaches (i.e., PGFS and RS) in terms of reward achieved at every time step of the episode (Figure 5a), and in terms of maximum reward achieved in each episode (Figure 5b). Further experimental details and results are provided in Section E of the Appendix.
Table 2: Statistics of the top-100 produced molecules with highest predicted HIV scores for every reaction-based method used and Enamine’s building blocks
NO AD AD
Scoring RT INT CCR5 RT INT CCR5
ENAMINEBB 6.87± 0.11 6.32± 0.12 7.10± 0.27 6.87± 0.11 6.32± 0.12 6.89± 0.32 RS 7.39± 0.10 6.87± 0.13 8.65± 0.06 7.31± 0.11 6.87± 0.13 8.56± 0.08
PGFS 7.81± 0.03 7.16± 0.09 8.96± 0.04 7.63± 0.09 7.15± 0.08 8.93± 0.05 PGFS+MB 7.81± 0.01 7.51± 0.02 9.06± 0.01 7.75± 0.04 7.51± 0.04 9.01± 0.05
(a)
(b)
Figure 5: Comparison of the three methods: RS (blue), PGFS (orange) and PGFS+MB (green) based on the rewards achieved starting with the 2000 initial reactants from a fixed validation set.

heading: 5 CONCLUSION

text: In this paper, we introduced a novel functional form of the Bellman equation to optimize for the maximum reward achieved at any time step in an episode. We introduced the corresponding evaluation and optimality operators and proved the convergence ofQ-learning algorithm. We further showed that the proposed max-Bellman formulation can be applied to deep reinforcement learning algorithms by demonstrating state-of-the-results on the task of de novo drug design across several reward functions and metrics.

heading: B OTHER RELATED IDEAS

text:
While the discussion so far has been focused on formulating a novel functional form of the Bellman equation for optimizing for the expected maximum reward in an episode (and proving its convergence properties and applying it on a toy domain and a more complex de-novo drug design environment), there are potentially other possible ways to approach this problem, some of which were tried by us.
A possible alternate approach is to just try optimizing for reward at the final time step (You et al. (2018a), Shi* et al. (2020)). This leads to a sparse reward problem and the training becomes harder. It is still an active research area and several approaches were introduced to address this issue of sparse rewards. For example, shaping the rewards (Trott et al. (2019)), learning auxiliary tasks (Riedmiller et al. (2018)), learning intrinsic rewards (Zheng et al. (2018)), using ensemble of models to learn intrinsic rewards (Park et al. (2020)). However, these approaches optimize only for the reward at the end of the episode, whereas, the maximum reward can occur at any time step in the episode. Optimal stopping based approaches (Becker et al. (2020)) learns to stop the stream of rewards they receive but to the best of our knowledge, there isn’t any approach with a thorough theoretical proof that simultaneously learns to stop the episode and to optimize for the reward at the end of episode in a reinforcement learning framework. Nonetheless, we tried to have a policy network that can choose an additional ‘stop’ action. The rewards did not converge as the policy network got biased
towards choosing ‘stop’ action most of the time. We tried other tricks like shaping the reward in the range [0,1] (instead of [-1, 1]), using unshaped rewards (range [0,∞) ), using difference of rewards (Chen & Tian (2019)) and adding a penalty for choosing the stop action. Even though these ideas are interesting, they do not have a thorough theoretical foundation relating to the objective of maximum reward optimization and they performed worse than PGFS. An interesting future work would be to combine the optimal stopping framework with the actor-critic framework to solve the maximum objective problem. This is outside the scope of our current work. Chang et al. (2015) is potentially another way to search in the policy space on which our max-Bellman formulation could be tried.

heading: C MARKOVIAN GOLDMINING TOY EXAMPLE

text:
We also run a comparison between Q-learning and Max-Q on a fully Markovian setting on a similar goldmining environment. The Markovian property is enforced by not removing the rewards once the goldmines have been visited, and by also including the timestep information in the state observation. From the learning perspective, the latter is enforced simply by making the Q-value table 3 dimensional with the first dimension referencing the timestep.
The markovian setting is on a similar toy domain with multiple goldmines in a 3 × 6 grid. The agent starts in the bottom left corner and at each time step, can choose from among the four cardinal actions: up, down, left and right. The environment is deterministic with respect to the action transitions and the agent cannot leave the grid. All states in the grid that are labeled with values other than -1 represent goldmines and each value represents the reward that the agent will collect upon reaching that particular state. Transitions into a non-goldmine state results in a reward of -1. The episode terminates after 5 time steps and the discount factor is γ = 0.99. The observation is a tuple consisting of an integer denoting the state number of the agent and an integer denoting the current time step.
The environment is shown in Figure 6. If the agent goes up to the top row and continues to move right, it will only get a cumulative return of 6. If it instead traverses the bottom row to the right, it can receive a cumulative return of 9, which is the highest cumulative return possible in this environment.
A comparison of cumulative return and maximum reward is shown in Figure 8. Q-learning learns the optimal policy while Max-Q learning the policy to reach the highest rewarding state. Thus, consistent results are obtained for the Markovian setting as well. The exploration schedule and hyperparameters are the same as those used for the non-Markovian setting.
For the Markovian setting, the grid was made smaller and the number of goldmines were reduced. These changes were made only to make the task easier to solve. Since the rewards do not vanish in this setting, not applying these minor changes meant that it was a much harder exploration problem and it was observed that the agent simply oscillated between states and took much longer to converge to the optimal policy. The increased variance in the average return for Max-Q in Figure 8a is as expected, since there is no incentive for the Max-Q agent to avoid the -8 penalties. This high variance is not observed in the non-Markovian toy example only because the rewards guide the agent around the negative reward filled middle row.
It should be noted that in the Markovian setting, since the Q-value table has 3 dimensions, there is no straightforward way to visualize the learned policy. Figure 7 has been obtained by plotting the greedy action for each state after applying the mean across the time axis of the Q-value table.

heading: D PSEUDO CODE - PGFS+MB

text:
In this section, we explain the PGFS+MB algorithm in detail and provide the pseudo code.
The actor module Π consists of two networks f and π. The role of the actor module is to compute the action a for a given state s. In this case, the state is the reactant R(1), and the action outputs are reaction template T and a tensor a in the space defined by feature representation of all second reactants. We use ECFP feature representation (Morgan circular molecular fingerprint bit vector of size 1024 and radius 2) for state inputs (reactant-1) and RLV2 feature representation (a custom feature representation) for action outputs (reactant-2). We used the following features in RLV2: MaxEStateIndex, MinEStateIndex, MinAbsEStateIndex, QED, MolWt, FpDensityMorgan1, BalabanJ, PEOE-VSA10, PEOE-VSA11, PEOE-VSA6, PEOE-VSA7, PEOE-VSA8, PEOE-VSA9, SMR-VSA7, SlogP-VSA3, SlogP-VSA5, EState-VSA2, EState-VSA3, EState-VSA4, EState-VSA5, EState-VSA6, FractionCSP3, MolLogP, Kappa2, PEOE- VSA2, SMR-VSA5, SMR-VSA6, EStateVSA7, Chi4v, SMR-VSA10, SlogP-VSA4, SlogP-VSA6, EState-VSA8, EState-VSA9, VSA-EState9.
First, the reactantR(1) is passed through the f -network to compute the template tensor T that contains the probability of each of the reaction templates.
T = f(R(1))
For a given reactantR(1), only few reaction templates are eligible to participate in a reaction involving R(1). Thus, all the invalid reaction templates are masked off by multiplying element-wise with a template mask Tmask, which is a binary tensor with value 1 if its a valid template, 0 otherwise.
T = T Tmask Finally, the reaction template T in one-hot tensor format is obtained by applying Gumbel softmax operation to the masked off template T . It is parameterized by a temperature parameter τ that is slowly decayed from 1.0 to 0.1
T = GumbelSoftmax(T, τ)
The one-hot template along with the reactant R(1) is passed through the π network to obtain the action a in the space defined by feature representation of all second reactants.
a = π(R(1), T )
The critic module consists of the Q-network and computes the Q(s, a) values. In this case, it takes in the reactant R(1), reaction template T , action a and compute its Q value: Q(R(1), T, a).
For the fairness in comparison, we used the exact same network sizes as described in the PGFS paper i.e., The f -network has four fully connected layers with 256, 128, 128 neurons in the hidden layers. The π network has four fully connected layers with 256, 256, 167 neurons in the hidden layers. All the hidden layers use ReLU activation whereas the final layer uses tanh activation. The Q-network also has four fully connected layers with 256, 64, 16 neurons in the hidden layers, with ReLU activation for all the hidden layers and linear activation for the final layer.
The environment takes in the current state s and action a and computes the next state and reward. First, it computes the set of second reactants that are eligible to participate in a reaction involving chosen reaction template T
R(2) = GetValidReactants(T )
The k valid reactants closest to the action a are then obtained by passing the action a and set of valid second reactants R(2) through the k nearest neighbours module.
A = kNN(a,R(2))
For each of these k second reactants, we compute the corresponding productsR(1)t+1 obtained involving the reactant R(1) and reaction template T by passing them through a forward reaction predictor module, and then compute the corresponding rewards by passing the obtained products through a scoring function prediction module.
R (1) t+1 = ForwardReaction(R (1), T,A)
Rewards = ScoringFunction(R(1)t+1)
Then, the product and the reward corresponding to the maximum reward are chosen and returned by the environment. In all our experiments, we use k = 1.
During the optimization (“backward”) phase, we compute the actions for next time step Ti+1, ai+1 using target actor network on a randomly sampled mini-batch.
Ti+1, ai+1 = Actor-target(R (1) i+1)
We then compute one-step TD (temporal difference) target yi (using the proposed max-Bellman formulation) as the maximum of reward at the current time step and discounted Q value (computed by critic-target) for the next state, next action pair. To incorporate the clipped double Q-learning formulation used in TD3 (Fujimoto et al. (2018a)) to prevent over-estimation bias, we use two critics and only take the minimum of the two critics.
yi = max[ri, γ min j=1,2
Critic-target({R(1)i+1, Ti+1}, ai+1)]
Note that this is different from PGFS (Gottipati et al. (2020)) where the authors compute the TD target using the standard Bellman formulation: yi = ri + γminj=1,2 Critic-target({R(1)i+1, Ti+1}, ai+1). We then compute the critic loss Lcritic as the mean squared error between the one-step TD target yi and the Q-value (computed by critic) of the current state, action pair.
Lcritic = ∑ i |yi − CRITIC(R(1)i , Ti, ai)| 2
The policy loss Lpolicy is negative of the critic value of the state, action pair where the actions are computed by the current version of the actor network
Lpolicy = − ∑ i CRITIC(R(1)i ,ACTOR(R (1) i ))
Like in PGFS, to enable faster learning during initial phases of the training, we also minimize an auxiliary loss which is the cross entropy loss between the predicted template and the actual valid template
Lauxil = − ∑ i (T (1) i , log(f(R (1) i )))
Thus, the total actor loss is the sum of policy loss and the auxiliary loss
Lactor = Lpolicy + Lauxil
The parameters of all the actor and critic networks (f , π, Q) are updated by minimizing the actor and critic losses respectively.
minLactor,Lcritic
Algorithm 1 PGFS+MB
1: procedure ACTOR(R(1)) 2: T ← f(R(1)) 3: T ← T Tmask 4: T ← GumbelSoftmax(T, τ) 5: a← π(R(1), T ) 6: return T, a 7: procedure CRITIC(R(1), T , a) 8: return Q(R(1), T, a) 9: procedure ENV.STEP(R(1), T, a)
10: R(2) ← GetValidReactants(T ) 11: A← kNN(a,R(2)) 12: R(1)t+1 ← ForwardReaction(R(1), T,A) 13: Rewards← ScoringFunction(R(1)t+1) 14: rt, R (1) t+1, done← arg maxRewards 15: return R(1)t+1, rt, done 16: procedure BACKWARD(buffer minibatch) 17: Ti+1, ai+1 ← Actor-target(R(1)i+1) 18: yi ← max[ri, γminj=1,2 Critic-target({R(1)i+1, Ti+1}, ai+1)] 19: Lcritic ← ∑ i |yi − CRITIC(R (1) i , Ti, ai)|2
20: Lpolicy ← − ∑ i CRITIC(R (1) i ,ACTOR(R (1) i ))
21: Lauxil ← − ∑ i(T (1) i , log(f(R (1) i ))) 22: Lactor ← Lpolicy + Lauxil 23: minLactor,Lcritic 24: procedure MAIN(f , π, Q) 25: for episode = 1, M do 26: sample R(1)0 27: for t = 0, N do 28: Tt, at ← Actor(R(1)t ) 29: R(1)t+1, rt, done← env.step(R (1) t , Tt, at) 30: store (R(1)t , Tt, at, R (1) t+1, rt, done) in buffer 31: sample a random minibatch from buffer 32: Backward(minibatch)

heading: E EXPERIMENTAL SETUP AND RESULTS

text:
Our experimental setup is same as that of PGFS but we include it here for the sake of completeness. The set of 150,560 reactants used in this study were taken from the Enamine Building Block catalogue Global stock and are represented as Simplified molecular-input line-entry system(SMILES) Weininger (1988). The 97 reaction templates were taken from Button et al. (2019) and are represented as SMILES arbitrary target specification (SMARTS). For a given class of reaction the template contains the pattern of reactive centres and the product across unimolecular and bimolecular reactions.
We test the performance of our model on five different rewards which are estimated from the molecular structure of the compound. One of the most used measure for drug-likeliness is quantitative estimate of drug-likeliness (QED) Bickerton et al. (2012). Octanol-water partition coefficient (clogP) You et al. (2018b) measures the lipophilicity or the aliphatic nature of the molecule which determines the solubility of the molecule in aqueous phase and increases with the size of the molecule. The other three rewards are related specifically to the Human Immunodeficiency Virus (HIV), which extends the applicability of our method to biological targets, C-C chemokine receptor type 5 (CCR5), HIV Integrase (INT), HIV Reverse Transcriptase (RT).
Even though the main motivation of this work is to build on existing reaction-based methods (PGFS) to ensure that the molecules generated are synthesizable, we also include the comparison with other non-reaction based methods that were believed to achieve state-of-the-art results in the last few years. These methods include junction-tree variational auto encoder (JTVAE) (Jin et al. (2018)), Graph Convolutional Policy Network (GCPN) (You et al. (2018b)), Molecule Swarm Optimization (MSO) (Winter et al. (2019)).

title: MAXIMUM REWARD FORMULATION IN REINFORCE-


summaries: The paper proposes a few-shot meta-learning method for recommender system that uses a new feature's meta-information and observed samples for the features to predict the network weights for predicting the feature value from other features. The paper focuses on the cold-start problem where few samples with a new feature observed is available. The method outperforms a wide range of baselines on MovieLens-1M, a medical synthetic dataset, and a e-learning dataset.

summaries: The paper proposes Contextual HyperNetworks (CHNs) as an auxiliary model to generate parameters from existing data, and observations and other metadata associated with new feature to address cold start problem of new feature. Besides, it doesn’t need either re-train or fine-tune at prediction time. The CHN is applied to P-VAE and some experimental results are provided to demonstrate its effectiveness in some application, i.e., recommender system, e-learning and healthcare tasks.

summaries: This submission focuses on the cold start problem of new entities (new items in a recommender system, new treatments in a medical application, etc.). It combines the strengths of the *relations* between a new entity and the existing entities, and the *content* features of the new entity, by fusing the two kinds of information into a neural network that outputs the estimated representation of the new entity. The proposed method outperforms several intuitive naïve strategies as well as MAML.

abstractText: While deep learning has obtained state-of-the-art results in many applications, the adaptation of neural network architectures to incorporate new output features remains a challenge, as a neural networks are commonly trained to produce a fixed output dimension. This issue is particularly severe in online learning settings, where new output features, such as items in a recommender system, are added continually with few or no associated observations. As such, methods for adapting neural networks to novel features which are both time and data-efficient are desired. To address this, we propose the Contextual HyperNetwork (CHN), an auxiliary model which generates parameters for extending the base model to a new feature, by utilizing both existing data as well as any observations and/or metadata associated with the new feature. At prediction time, the CHN requires only a single forward pass through a neural network, yielding a significant speed-up when compared to re-training and fine-tuning approaches. To assess the performance of CHNs, we use a CHN to augment a partial variational autoencoder (P-VAE), a deep generative model which can impute the values of missing features in sparsely-observed data. We show that this system obtains improved few-shot learning performance for novel features over existing imputation and meta-learning baselines across recommender systems, e-learning, and healthcare tasks.

authors:
Marko Balabanović
Yoav Shoham

title: Fab: content-based, collaborative recommendation

venue: Communications of the ACM,

authors:
Luca Bertinetto
João F Henriques
Jack Valmadre
Philip Torr
Andrea Vedaldi

title: Learning feedforward one-shot learners

title: Meta-learning for user cold-start recommendation

venue: International Joint Conference on Neural Networks (IJCNN),

authors:
Chelsea Finn
Pieter Abbeel
Sergey Levine

title: Model-agnostic meta-learning for fast adaptation of deep networks

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

authors:
Marta Garnelo
Dan Rosenbaum
Chris J Maddison
Tiago Ramalho
David Saxton
Murray Shanahan
Yee Whye Teh
Danilo J Rezende
SM Eslami

title: Conditional neural processes

venue: arXiv preprint arXiv:1807.01613,

authors:
Spyros Gidaris
Nikos Komodakis

title: Dynamic few-shot visual learning without forgetting

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

authors:
Carlos A Gomez-Uribe
Neil Hunt

title: The netflix recommender system: Algorithms, business value, and innovation

venue: ACM Transactions on Management Information Systems (TMIS),

authors:
Wenbo Gong
Sebastian Tschiatschek
Sebastian Nowozin
Richard E Turner
José Miguel HernándezLobato
Cheng Zhang

title: Icebreaker: Element-wise efficient information acquisition with a bayesian deep latent gaussian model

venue: In Advances in Neural Information Processing Systems,

authors:
Jonathan Gordon
John Bronskill
Matthias Bauer
Sebastian Nowozin
Richard E Turner

title: Versa: Versatile and efficient few-shot learning

venue: In Third workshop on Bayesian Deep Learning,

authors:
Edward Grefenstette
Brandon Amos
Denis Yarats
Phu Mon Htut
Artem Molchanov
Franziska Meier
Douwe Kiela
Kyunghyun Cho
Soumith Chintala

title: Generalized inner loop meta-learning

authors:
Will Hamilton
Zhitao Ying
Jure Leskovec

title: Inductive representation learning on large graphs

authors:
F Maxwell Harper
Joseph A Konstan

title: The movielens datasets: History and context

venue: Acm transactions on interactive intelligent systems (tiis),

authors:
Xiangnan He
Lizi Liao
Hanwang Zhang
Liqiang Nie
Xia Hu
Tat-Seng Chua

title: Neural collaborative filtering

venue: In Proceedings of the 26th international conference on world wide web,

authors:
Diederik P Kingma
Jimmy Ba

title: Adam: A method for stochastic optimization

venue: arXiv preprint arXiv:1412.6980,

authors:
James Kirkpatrick
Razvan Pascanu
Neil Rabinowitz
Joel Veness
Guillaume Desjardins
Andrei A Rusu
Kieran Milan
John Quan
Tiago Ramalho
Agnieszka Grabska-Barwinska

title: Overcoming catastrophic forgetting in neural networks

venue: Proceedings of the national academy of sciences,

authors:
Xuan Nhat Lam
Thuc Vu
Trong Duc Le
Anh Duc Duong

title: Addressing cold-start problem in recommendation systems

venue: In Proceedings of the 2nd international conference on Ubiquitous information management and communication,

authors:
Dawen Liang
Rahul G Krishnan
Matthew D Hoffman
Tony Jebara

title: Variational autoencoders for collaborative filtering

venue: In Proceedings of the 2018 World Wide Web Conference,

authors:
Blerina Lika
Kostas Kolomvatsos
Stathes Hadjiefthymiades

title: Facing the cold start problem in recommender systems

authors:
Pasquale Lops
Marco De Gemmis
Giovanni Semeraro

title: Content-based recommender systems: State of the art and trends

venue: In Recommender systems handbook,

authors:
Chao Ma
Wenbo Gong
José Miguel Hernández-Lobato
Noam Koenigstein
Sebastian Nowozin
Cheng Zhang

title: Partial vae for hybrid recommender system

venue: In NIPS Workshop on Bayesian Deep Learning,

authors:
Chao Ma
Sebastian Tschiatschek
Konstantina Palla
José Miguel Hernández-Lobato
Sebastian Nowozin
Cheng Zhang

title: Eddi: Efficient dynamic discovery of high-value information with partial vae

venue: arXiv preprint arXiv:1809.11142,

authors:
Tsendsuren Munkhdalai
Xingdi Yuan
Soroush Mehri
Adam Trischler

title: Rapid adaptation with conditionally shifted neurons

venue: arXiv preprint arXiv:1712.09926,

authors:
Cuong V Nguyen
Yingzhen Li
Thang D Bui
Richard E Turner

title: Variational continual learning

venue: arXiv preprint arXiv:1710.10628,

authors:
Alex Nichol
John Schulman

title: Reptile: a scalable metalearning algorithm

venue: arXiv preprint arXiv:1803.02999,

authors:
Adam Paszke
Sam Gross
Soumith Chintala
Gregory Chanan
Edward Yang
Zachary DeVito
Zeming Lin
Alban Desmaison
Luca Antiga
Adam Lerer

title: Automatic differentiation in pytorch

authors:
Michael J Pazzani
Daniel Billsus

title: Content-based recommendation systems

venue: In The adaptive web,

authors:
Charles R Qi
Hao Su
Kaichun Mo
Leonidas J Guibas

title: Pointnet: Deep learning on point sets for 3d classification and segmentation

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

authors:
James Requeima
Jonathan Gordon
John Bronskill
Sebastian Nowozin
Richard E Turner

title: Fast and flexible multi-task classification using conditional neural adaptive processes

authors:
Badrul Sarwar
George Karypis
Joseph Konstan
John Riedl

title: Item-based collaborative filtering recommendation algorithms

venue: In Proceedings of the 10th international conference on World Wide Web,

authors:
J Ben Schafer
Dan Frankowski
Jon Herlocker
Shilad Sen

title: Collaborative filtering recommender systems

authors:
Andrew I Schein
Alexandrin Popescul
Lyle H Ungar
David M Pennock

title: Methods and metrics for cold-start recommendations

venue: In Proceedings of the 25th annual international ACM SIGIR conference on Research and development in information retrieval,

authors:
Michael Schlichtkrull
Thomas N Kipf
Peter Bloem
Rianne Van Den Berg
Ivan Titov
Max Welling

title: Modeling relational data with graph convolutional networks

venue: In European Semantic Web Conference,

authors:
Suvash Sedhain
Aditya Krishna Menon
Scott Sanner
Lexing Xie

title: Autorec: Autoencoders meet collaborative filtering

venue: In Proceedings of the 24th international conference on World Wide Web,

authors:
Jake Snell
Kevin Swersky
Richard Zemel

title: Prototypical networks for few-shot learning

authors:
David H Stern
Ralf Herbrich
Thore Graepel

title: Matchbox: large scale online bayesian recommendations

venue: In Proceedings of the 18th international conference on World wide web,

authors:
Ruibo Tu
Kun Zhang
Bo Bertilson
Hedvig Kjellstrom
Cheng Zhang

title: Neuropathic pain diagnosis simulator for causal discovery algorithm evaluation

authors:
Manasi Vartak
Arvind Thiagarajan
Conrado Miranda
Jeshua Bratman
Hugo Larochelle

title: A meta-learning perspective on cold-start recommendations for items

authors:
Oriol Vinyals
Charles Blundell
Timothy Lillicrap
Daan Wierstra

title: Matching networks for one shot learning

authors:
Johannes von Oswald
Christian Henning
João Sacramento
Benjamin F Grewe

title: Continual learning with hypernetworks

venue: arXiv preprint arXiv:1906.00695,

authors:
Xiang Wang
Xiangnan He
Meng Wang
Fuli Feng
Tat-Seng Chua

title: Neural graph collaborative filtering

venue: In Proceedings of the 42nd international ACM SIGIR conference on Research and development in Information Retrieval,

authors:
Zichao Wang
Angus Lamb
Evgeny Saveliev
Pashmina Cameron
Yordan Zaykov
José Miguel Hernández-Lobato
Richard E Turner
Richard G Baraniuk
Craig Barton
Simon Peyton Jones

title: Diagnostic questions: The neurips 2020 education challenge

venue: arXiv preprint arXiv:2007.12061,

authors:
Jiaxuan You
Xiaobai Ma
Yi Ding
Mykel J Kochenderfer
Jure Leskovec

title: Handling missing data with graph representation learning

venue: Advances in Neural Information Processing Systems,

venue: That is,

heading: 1 INTRODUCTION

text:
In many deep learning application domains, it is common to see the set of predictions made by a model grow over time: a new item may be introduced into a recommender system, a new question may be added to a survey, or a new disease may require diagnosis. In such settings, it is valuable to be able to accurately predict the values that this feature takes within data points for which it is unobserved: for example, predicting whether a user will enjoy a new movie in a recommender system, or predicting how a user will answer a new question in a questionnaire.
On the introduction of a new feature, there may be few or no labelled data points containing observed values for it; a newly added movie may have received very few or even no ratings. The typically poor performance of machine learning models in this low-data regime is often referred to as the cold-start problem (Schein et al., 2002; Lika et al., 2014; Lam et al., 2008), which is prevalent not only in recommender systems but also in applications where high quality data is sparse. This presents a key challenge: the adaptation of a deep learning model to accurately predict the new feature values in the low data regime. On one hand, it is often required to deploy the model in applications immediately upon the arrival of new features, so it is impractical for the adaptation to wait until much more data has been acquired. On the other hand, simply retraining the model every time a new feature is introduced is computationally costly, and may fall victim to severe over-fitting if there are only a small number of observations available for the new feature.
Few-shot learning (Snell et al., 2017; Requeima et al., 2019; Vinyals et al., 2016; Gordon et al., 2018) has seen great successes in recent years, particularly in image classification tasks; however, these approaches typically treat all tasks as independent of one another. We wish to extend these ideas to the challenge of extending deep learning models to new output features, using a method which captures how a new feature relates to the existing features in the model. Furthermore, we seek a method that is computationally efficient, ideally requiring no fine-tuning of the model, and that is resistant to over-fitting in the few-shot regime.
To address these needs simultaneously, our contributions are as follows:
• We propose an auxiliary neural network, called Contextual HyperNet (CHN), that can be used to initialize the model parameters associated with a new feature (see Section 2). CHNs are conditioned on both a context set made up of observations for the new feature, and any associated content information or metadata. CHNs amortize the process of performing gradient descent on the new parameters by mapping the newly observed data directly into high-performing new parameter values, with no additional fine-tuning of the model being required. This makes CHNs highly computationally efficient and scalable to large datasets. • We use a CHN to augment a partial variational autoencoder (P-VAE) and evaluate the
system’s performance across a range of applications (see Section 4). While CHNs are applicable to a wide range of deep learning models, in this work we choose a P-VAE as the evaluation framework. The result is a flexible deep learning model able to rapidly adapt to new features, even when the data is sparsely-observed, e.g. in recommender systems. We show that this model outperforms a range of baselines in both predictive accuracy and speed across recommender system, e-learning and healthcare tasks.

heading: 2 MODEL

heading: 2.1 PROBLEM SETTING

text:
Our goal is to enable fast adaptation of a machine learning model when new output features are added to augment the originally observed data. Specifically, we consider the original observations as a set of vector-valued data points D = {x(i)}mi=1, where each of the feature values in a given data point may be missing. We denote xj as the jth feature of a data point x ∈ D and group the observed and unobserved features within a data point as x = [xO,xU ]. In many scenarios, such as recommender systems, a machine learning model p(xU |xO) aims then at predicting the unobserved features xU given observed ones xO.
Now suppose a new output feature xn becomes available, so that each data vector x ∈ D is augmented to become x̃ = [x;xn]. This happens when e.g. a new item is added to a recommender system, or a new type of diagnostic test is added in a medical application. We note that not every data point x ∈ D receives an observed value for the new feature: a newly added movie may have received very few ratings, or a new diagnostic test may have yet to be performed on all of the patients. We refer to the set of data points where the new feature is observed as the context set for the new feature n, i.e.
Cn = {x̃ = [x;xn] | x ∈ D, xn is observed}. context set is shown in yellow in Figure 1 Its complement, the target set Tn, is the set of those data points for which there is no associated observation for the feature: Tn = {x̃ = [x;xn] | x ∈ D, xn is unobserved}.
One can also split the augmented data into observed and unobserved parts, i.e. x̃ = [x̃O, x̃U ]. Using this notation, it is clear that x̃O = [xO;xn], x̃U = xU for x̃ ∈ Cn, and x̃O = xO, x̃U = [xU ;xn] for x̃ ∈ Tn. In addition, we may also have access to some metadataMn describing the new feature. This could be categorical data such as the category of a product in a recommender system or the topic of a question in an e-learning system, or some richer data format such as images or text.
We wish to adapt the machine learning model pθ0(xU |xO) to pθ(x̃U |xO) so that it is able to accurately predict the value of the unobserved new features for data points x̃ ∈ Tn. A naive strategy would ignore the previous model pθ0(xU |xO) and instead seek the maximum likelihood estimates (MLE) of the parameters for the new model pθ(x̃U |xO). This is typically done by training the new model on the context set, by temporarily moving the observed new features xn to the prediction targets:
θ̂ = argmax θ [∑ x̃∈Cn log pθ (xn,xU |xO) ] .
However, in deep neural networks, the number of model parameters θ may be extremely large, so that maximising this log-likelihood is very expensive, particularly if new features are being introduced on a regular basis. Furthermore, optimising θ for one particular feature may lead to poor performance for another, as is the case in catastrophic forgetting (Kirkpatrick et al., 2017) in continual learning tasks. In order to address both of these concerns, we divide the model parameters into parameters θ0 inherent from the old model, and feature-specific parameters θn associated solely with the new feature. In other words, we use pθ0(xU |xO) as a base model and pose a factorisation assumption on the augmented model as pθ(x̃U |xO) = pθ0(xU |xO)pθ0(xn|xO;θn), which together yield a predictive model for the new feature. We then hold θ0 fixed and only seek MLEs for θn. While this greatly reduces the dimensionality of the parameter space over which we optimize for a new feature, and decouples the optimization of parameters for one new feature from another, several issues still exist. This factorization still requires a gradient descent procedure, which can be computationally costly and risks severe overfitting when there is little data for the new feature. Furthermore, it is not immediately clear how to make the estimation of θn depend on the feature metadataMn. To address these problems, we introduce a Contextual HyperNetwork (CHN) Hψ(Cn,Mn), an auxilliary neural network that amortizes the process of estimating θn. The goal is that when a new feature xn∗ is added at test time, the CHN will directly generate “good” parameters θ̃n∗ = Hψ(Cn∗ ,Mn∗) such that the new predictive model pθ0(xn∗ |xO;θn∗ = θ̃n∗) can predict the values of the new feature accurately.

heading: 2.2 CONTEXTUAL HYPERNETWORKS

text:
CHNs aim to map the context set Cn and metadataMn into an estimate of the new model parameters θ̃n. Since the size of Cn is variable for each feature, CHNs require an architecture that is able to adapt to a varying input dimension. This challenge is addressed through the use of a PointNet-style set encoder (Qi et al., 2017; Zaheer et al., 2017). For each context point x̃(i) ∈ Cn, we concatenate the new feature x(i)n with a fixed-length encoding z(i) (see below) of the other observed features x (i) O within the data point. Each of these concatenated vectors [z (i), x (i) n ] is then input to a shared neural network f(·), and the outputs f([z(i), x(i)n ]) are aggregated by a permutation-invariant function such as summation in order to produce a single, fixed-length vector. This output is passed through a second neural network g(·) to produce a fixed-length encoding of cn we term a “context vector". This architecture is displayed in Figure 2a.
The fixed length encoding z(i) of the observed features x(i)O for each context data point x̃ (i) ∈ Cn is obtained by inputting the observed features to the base model pθ0(xU |xO) and taking some intermediate representation from within the model: in an autoencoder model, this could be the encoded vector representing the data point at the information bottleneck, while in a feed-forward model it could be the output of an intermediate layer. By encoding the existing features in this way, we hope to enable the CHN to interpret the observed values for the new features in the context of the base model’s representation of remainder of the data point.
Additionally, any feature metadataMn is passed through a neural network h(·) to produce a fixed length metadata embedding vector mn. In the case of image or text metadata, specialized architectures
such as convolutional or sequence models can be used here. The concatenated vector [cn;mn] is then input into a final feed-forward neural network which outputs the new feature-specific parameters θ̃n. CHNs can be applied to any predictive model with dynamically added output features: Figure 2b shows the application of CHN to an predictive model. As an example, we illustrate how CHN is used with an autoencoder-style model in Figure 3.
Since it is possible to parallelize the encoding of the context set Cn both across each data point x(k) and across the observed features within each data point xi, the computational costs for parameter prediction with CHNs are able to scale efficiently with both the context set size and the number of observed values within each data point in the context set. When combined with the lack of any costly iterative gradientdescent procedure, this makes CHNs an extremely efficient choice for parameter initialization.

heading: 2.3 TRAINING CHNS WITH META-LEARNING

text:
We adopt a meta-learning approach to training the CHN, treating the prediction of the values of each new feature as an individual task, with the aim of producing a model that can “learn how to learn” from Cn andMn. First, a base model pθ0(xU |xO) is trained on the data observed before the adaptation stages; this model is then frozen during CHN training. To implement the training strategy, in the experiments we divide the dataset into three disjoint sets of features (see Figure 4): a ‘training’ set for base model training in the first stage, a ‘meta-training’ set for CHN meta-learning in the second stage, and a meta-test set for CHN evaluation in the third stage.
Meta-Training of the CHN During meta-training, the parameters θ0 of the base model are frozen, and we learn the parameters ψ of the CHN. We iterate the following training steps in mini-batches of features B sampled from the meta-training set for every step:
1. For each feature n in B, sample kn data points in which this feature is observed to form the context set Cn, and reveal the associated feature values to the model. In our experiments we sample kn ∼ Uniform[0, ..., 32] to ensure that a single CHN can perform well across a range of context set sizes.
2. For each feature n ∈ B, compute feature-specific parameter predictions using the CHN,
θ̃n = Hψ(Cn,Mn).
3. For each feature n ∈ B, estimate the log-likelihood of the CHN parameters ψ given the ground truths for the hidden values of the feature n in the data points in its target set Tn, using the augmented model pθ0(xn|xO, θ̃n):
l(ψ) = 1∑ n∈B |Tn| ∑ n∈B ∑ {i|x(i)∈Tn} log pθ0(x (i) n |x (i) O ; θ̃n).
4. Update the CHN parameters by taking a gradient ascent step in ψ for l(ψ).
Note that the log-likelihood is only computed for the hidden values of the new feature in the target set Tn, and not for the observed values in Cn – this is to ensure that the CHN produces parameters which generalize well, rather than overfitting to the context set. This approach is consistent with many meta-learning methods such as MAML (Finn et al., 2017), where the meta-learning model is updated based on its performance on a “test set" of previously unseen examples for each new task.
Evaluating the CHN At evaluation time, the parameters of both the base model and the CHN are now frozen. A fixed context set and metadata are provided for each feature in the meta-test set, and
these are used to initialize feature-specific parameters for the meta-test features using the trained CHN. These parameters are then used to make predictions for all of the target set values for the new features, from which evaluation metrics are computed.
3 RELATED WORK
CHNs aim to solve the problem of adapting to a new feature with very few available observations, and thus relate to few-shot learning and related fields such as meta-learning and continual learning. From a technical point of view, we use an auxiliary neural network to amortize the learning of parameters associated with the new feature, which falls under the domain of hypernetworks. Furthermore, in the context of recommender systems, a number of related methods have been proposed to address the cold-start problem. We thus discuss related work in these three areas.
Few-Shot Learning Few-shot learning is the problem of designing machine learning models that can adapt to new prediction tasks given a small number of training examples. A popular approach to this problem is gradientbased meta-learning, such as MAML (Finn et al., 2017) and Reptile (Nichol & Schulman, 2018), which seek a parameter initialisation θ that can rapidly adapt to tasks drawn from a task distribution p(T ).These methods do not directly condition the parameter initialisation for a
new task on any associated data or metadata, instead relying on fine-tuning,which can be both computationally expensive and lead to severe overfitting when little data is available. Another line of methods seek to adapt a classifier to a task based on a context set of class examples. For instance, by embedding class examples to provide a nearest neighbours classifier (Snell et al., 2017), learning an attention mechanism between class examples and a new example (Vinyals et al., 2016), or modulating activation functions (Munkhdalai et al., 2017) within a feature extractor conditioned on the context set. Conditional Neural Adaptive Processes (Requeima et al., 2019), which are based on Conditional Neural Processes (Garnelo et al., 2018), adapt both classifier and feature extractor parameters based on the context set for a task. Similarly, Gidaris & Komodakis (2018) generate classifier weights for a new image class based on features extracted using the base model. However, in all cases, each task or image class is treated as independent from all others, whereas CHNs explicitly utilize all previously-observed features in the base model when adapting to a new feature.
A closely related field is continual learning (Kirkpatrick et al., 2017; Nguyen et al., 2017), where a model seeks to adapt to new tasks or a shifting data distribution while avoiding catastrophic forgetting of old tasks. Continual learning does not necessarily address the few-shot scenario and is commonly applied in classification settings where the classifier/heads can be either shared or independent. CHNs can be seen as a means of addressing continual learning in the few-shot learning regime, by generating parameters for a new feature conditioned on all of the features already learned by the model.
Hypernetworks Hypernetworks (Ha et al., 2016) are auxiliary neural networks which generate the parameters of a neural network. They were introduced in Ha et al. (2016) as a form of model compression, with the hypernetwork taking as in input only structural information about the weight matrix they are currently predicting, such as its index in a sequence of layers. By contrast, CHNs are explicitly conditioned on data relevant to the weights currently being predicted. Bertinetto et al. (2016) train a hypernetwork to predict all of the parameters of a binary classifier for a class of images, conditioned on a single exemplar image for the class. It is found that the output dimension of the hypernetwork grows extremely large for even small classifiers—in order to mitigate this, the authors propose a factorisation of the parameters, whereas we instead choose to learn only a small number of feature-specific parameters θn. Task-conditioned hypernetworks (von Oswald et al., 2019) provide an application of hypernetworks to multi-task continual learning, where weights for the entire neural network for different tasks are predicted using a hypernetwork, based on a learned task embedding.
This setting differs from our work as the continual learning tasks are assumed to be independent, and the hypernetwork is not conditioned directly on data for the new task, instead requiring a gradient descent process to learn the associated task embedding.
Cold Starts in Recommender Systems Cold starts (Schein et al., 2002; Lika et al., 2014) occur when there is little or no data associated with a novel item or user in a recommender system. Collaborative filtering approaches to recommender systems have enjoyed great success for many years (Schafer et al., 2007; Sarwar et al., 2001; He et al., 2017), but can fail completely when there is very limited rating data associated with a new user or item (Lam et al., 2008). One potential solution to cold starts is given by content-based methods (Pazzani & Billsus, 2007; Lops et al., 2011), which use any available descriptive information about the new user or item. Hybrid approaches (Balabanović & Shoham, 1997; Stern et al., 2009; Gomez-Uribe & Hunt, 2015) seek to marry these two approaches, making use of both collaborative and content-based methods. Meta-learning approaches also show promise for solving cold starts, including MAML-like approaches (Bharadhwaj, 2019) for initialising new items. Vartak et al. (2017) takes a similar approach to CHNs by adapting the weights of a classifier, but the adaption is based on user rather than item history, and it relies on class-specific item embeddings and thus is not extensible to regression settings. In this work, when applied to recommender systems, CHNs combine the strengths of all of these approaches, using content information, ratings data and latent representations of the associated users to generate accurate parameters for novel items. Recently, graph neural network (GNN)-based approaches (You et al., 2020; Schlichtkrull et al., 2018; Wang et al., 2019; Hamilton et al., 2017) have shown promise when applied to recommender systems. These methods formulate each item and each user as a node, and incorporate new items by adding nodes to the graph, where the graph structure may be exploited for inductive reasoning about new features. In this work, we target more standard, vector-based neural networks which are currently deployed across a wide range of application domains where GNNs may not be suitable, but future work may explore the application of CHNs to GNNs and the relationships between the two.

heading: 4 EXPERIMENTS

text: We demonstrate the performance of the proposed CHN in three different real-world application scenarios, including recommender systems (Section 4.2), healthcare (Section 4.3) and e-learning (Section 4.4). Our method exhibits superior performance in terms of prediction accuracy across all these applications. We also demonstrate an advantage in terms of computational efficiency in a large scale real-life setting.

heading: 4.1 EXPERIMENT SETTINGS

text:
In all our experiments, we apply a CHN to a partial variational autoencoder (P-VAE) (Ma et al., 2018b;a) as an exemplar model. This is a flexible autoencoder model that is able to accurately work with and impute missing values in data points, allowing us to model sparsely-observed data such as that found in recommender systems. For each new feature n, we augment the P-VAE’s decoder with a new decoder head consisting of an additional column of decoder weights wn and an additional decoder bias term bn which extend the model’s output to the new feature, so that θn = {wn, bn}. Figure 3 illustrates how a CHN is used to extend a P-VAE to make predictions for a new feature xn.
For all experiments, we train the CHN to output accurate feature parameters based on a range of context set sizes k ∈ [0, ..., 32] by randomly sampling k on each occurrence of a meta-training set feature. We then evaluate the performance of the CHN and baselines on the meta-test set features for a fixed range of context set sizes, ensuring that the same context sets are revealed to the CHN and each baseline. Further experimental results can be found in Appendix C, and full details on the model architectures and hyperparameters can be found in Appendix D. All results are averaged across 5 random train/meta-train/meta-test feature splits, and ±1σ error bars are plotted across these splits. Hyperparameters and model architectures were tuned on different data splits to those used in the final experiments.
We consider the following baselines for generating the new feature parameters θn = {wn, bn}. All methods are applied to the same base trained P-VAE model to ensure a fair comparison.
• Random: Generate a random value for θn for each new decoder head using Xavier initialisation for weights and 0 for biases. • Mean Imputing: Set weights and biases to always predict the mean of the observed values for the new feature in the context set, i.e. wn = 0 and b = σ−1 ( 1 k ∑ i∈Cn x (i) n ) . • Mean Head Parameters: Generate the new head parameters θn as the mean of all of the head parameters learned on the training set features. • Mean Head Parameters (Matching Metadata): As above, but averaging only over parameters of heads whose associated feature has metadata categories matching those of the new feature. • k-Nearest Neighbour Head Parameters: Generate the new head parameters θn as the mean of the head parameters of the k-nearest neighbour features in terms of Euclidean distance, where column-wise mean imputing is used to fill in unobserved values. • Train from Random: Initialize the new feature head parameters randomly, and then fine-tune these parameters on the data in the context set Cn for a fixed number of epochs. • MAML: We meta-learn an initialisation of θn using Model-Agnostic Meta Learning (Finn et al., 2017), where we treat the prediction of each feature as a separate task and fine-tune these parameters on the context set. In all experiments, we compare with the MAML baseline which has the bestperforming number of fine-tuning epochs. For full details, see Appendix B.

heading: 4.2 RECOMMENDER SYSTEMS

text:
In real-life recommender systems, new users and new items are continuously added as new customers join and new products are launched. In deep learning based frameworks such as Sedhain et al. (2015); Liang et al. (2018); Gong et al. (2019); Ma et al. (2018a), the deep neural networks are commonly used in a user-based manner. In this approach, each new user is treated as a new data point, while each new item is treated as a new feature. To add a new item, one must extend the network architecture to incorporate the new feature, and we propose CHNs as an efficient way to predict the parameters associated with the new feature.
We evaluate the scenario above with MovieLens-1M dataset (Harper & Konstan, 2015). The dataset consists of 1 million ratings in the range 1 to 5 given by 8094 users to 5660 movies, and is thus 2.2% observed. For each movie, we have associated metadataMn giving a list of genres associated with the movie, such as Action or Comedy, which we encode in a binary format, alongside the year of release which we normalize to lie within [0, 1]. For each random data split, we sampled 60% of movies as training data to train the base P-VAE model, used 30% as a meta-training set for CHN training and used the remaining 10% as a meta-test set.
The plot in Figure 5 (left) shows the performance of our proposed CHN, comparing with all other baselines in terms of RMSE (lower is better). Our method shows an advantage over all considered
baselines other than MAML in the few-shot regime (k < 8), while achieving competitive performance with MAML without requiring costly fine-tuning.

heading: 4.3 HEALTHCARE

text:
In healthcare applications, a new question is often added to an existing health-assessment questionnaire, and in hospitals, new medical devices may be introduced to make physiological measurements. In this case it is desired for a model to quickly adapt to the newly added feature for health assessment, even when relatively few tests have been administered and so data is scarce.
We assess the utility of CHNs in a healthcare setting using synthetic data generated by the Neuropathic Pain Diagnosis Simulator (Tu et al., 2019). This simulator produces synthetic data using a generative model to simulate pathophysiologies, patterns and symptoms associated with different types of neuropathic pain. The data is binary, where a 0 represents the a diagnostic label that is not present in a patient’s record, and a 1 indicates a diagnostic label that is present. We simulated 1000 synthetic patients, and removed features with fewer than 50 positive diagnoses, resulting in 82 remaining features, with 17.3% of the values in the dataset being positive diagnoses. We used 50% of the features as training set; 30% of the features as the meta-test set and 20% of the features as the meta-test set.
The plot in Figure 5 (middle) shows the results in terms of AUROC (higher is better), as the dataset is highly imbalanced. Our method consistently outperforms all baselines across all values of k, while many methods including MAML suffer from severe overfitting when k is small. In contrast to the MovieLens-1M result, here the 10-nearest neighbour approach does not seem to leverage more datapoints in the context set. This shows that our method is desirable in the cost-sensitive healthcare environment, even for highly imbalanced medical tests where results are largely negative.

heading: 4.4 E-LEARNING

text:
We foresee CHNs being valuable in online education settings, potentially allowing teachers to quickly assess the diagnostic power of a new question given a small number of answers, or to gauge whether a new question’s difficulty is appropriate for a particular student.
We assess the performance of the CHN in an e-learning setting using a real-life dataset provided by the e-learning provider Eedi for the NeurIPS 2020 Education Challenge (Wang et al., 2020). In particular, we use the dataset for the first 2 tasks, filtered so that all students and questions have at least 250 associated responses. This results in a dataset of for 6797 students across 4792 questions, detailing whether or not a student answered a particular question correctly. The dataset contains approximately 2.7 million responses, making it 8.2% observed. We treat each student as a data point and each question as a feature, and use a binary encoding of each question’s associated subjects as metadata. We used 60% of the questions as training set; 30% of the questions as the meta-test set and 10% of the questions as the meta-test set.
The right panel in Figure 5 illustrates the performance on prediction on the unseen meta-test set in terms of AUROC. Our method shows a significant improvement over all of the considered baselines over the entire range of k, suggesting promise for applying CHNs in educational settings.
4.5 TIMING EXPERIMENTS
We used the E-learning dataset to compare the time taken to generate new feature parameters at meta-test time for a number of methods considered in our experiments. The results are shown in Table 1. We see that the CHN offers nearly a 4-fold speedup compared to the nearestneighbours based approach. We see a similar difference in performance when compared to training the new heads on a single observation for just 10 epochs. Moreover,
while this training time grows rapidly with the number of observations in the context set, the time taken for a CHN remains nearly constant since it can efficiently parallelize along these observations, making CHNs an extremely efficient initialisation choice for larger context set sizes. The experimental settings are specified in Appendix D where the total computation time for training and evaluating a CHN was approximately 3 minutes on the Neuropathic Pain dataset, 1.5 hours on the E-learning dataset, and 8 hours on MovieLens-1M.

heading: 5 CONCLUSION

text: We introduce Contextual HyperNetworks (CHNs), providing an efficient way to initialize parameters for a new feature in a model given a context set of points containing the new feature and feature metadata. Our experiments demonstrate that CHNs outperform a range of baselines in terms of predictive performance across a range of datasets, in both regression and classification settings, and are able to perform well across a range of context set sizes, while remaining computationally efficient. In the future work, we will evaluate CHNs in streaming setting with large-scale real-world applications.

heading: A APPENDIX: PARTIAL VARIATIONAL AUTOENCODERS

heading: A.1 PARTIAL VARIATIONAL AUTOENCODERS

text:
For our experiments, we base our model on the Partial Variational Autoencoder (P-VAE) (Ma et al., 2018a) - this model combines a traditional variational autoencoder (VAE) model with a PointNet-style set encoder (Qi et al., 2017), allowing it to efficiently encode and reconstruct partially observed data points. The P-VAE is based on the observation that typically the features in a VAE are assumed to be conditionally independent when conditioned on the latent variable z. That is,
p(x|z) = ∏ j p(xj |z)
Then, given a data point x with observed features xO and unobserved features xU , we have that
p(xU |xO, z) = p(xU |z)
Hence, if we can infer a posterior distribution over z from the observed features, we can use this to estimate p(xU |xO). The P-VAE infers a variational posterior distribution over z using an amortized inference network (or encoder network) qθ(z|xO) and approximates the conditional data distribution given a value of z using a decoder network pφ(xO,xU |z). In our model, we extend the decoder to decode the value of a new feature xn by initialising an additional subnetwork in the decoder which we term a decoder head, with parameters φn, to extend its output dimension by one. In principal this head could be of any architecture which takes as input the output of the shared layers of the decoder, but in practice we found that simply extending the final layer of weights and biases to accommodate a new output dimension yielded good results while remaining parameter-efficient as the number of output features grows.

heading: A.2 TRAINING P-VAES

text:
The P-VAE is trained to reconstruct observed features in the partially-observed data point, and in the process learn to infer a variational posterior qθ(z|xO) over the latent variable z. The P-VAE is given batches of data points where features from both the meta-train and meta-test sets are hidden from the model. Additionally, each time a particular data point is input, some additional features are also randomly hidden from the model using a Bernoulli mask, in order to ensure the model is robust to different sparsity patterns in the data. The P-VAE is then trained by maximising the Evidence Lower-Bound (ELBO) (Ma et al., 2018b):
log p(xO) ≥ log p(xO)−DKL(q(z|xO)||p(z|xO)) = Ez∼q(z|xO) [log p(xO,xU |z)]−DKL [q(z|xO)||p(z)] = Lpartial(xO)

heading: B APPENDIX: BASELINES

text: Here we provide additional details and results for the baselines used in our experiments.

heading: B.1 MAML

text:
We adapt the Model-Agnostic Meta Learning (Finn et al., 2017) technique as a baseline. The decoder head parameters θn are adapted using the MAML algorithm in the ‘meta-training’ stage. Each new feature X is viewed as a separate MAML task, with some observed and unobserved values. We sample the tasks in batches of size M and train the inner (a.k.a. fast) model over N steps. The inner model training loss is the ELBO of the PVAE on the observations LXO . The meta-model (a.k.a. the slow or outer model) is trained by being given the context set observations, and computing a reconstruction loss on the target set, L̂T ,C(fθ′ ,X ). The gradient for the meta-model update is taken over the batch reconstruction losses mean. The full algorithm is detailed in Algorithm 1.
Algorithm 1 Feature-wise Model-Agnostic Meta-Learning with PVAE Input: p(X ): distribution over features. α, β: learning rate hyperparameters. M : meta-batch size, N : number inner iterations.
Initialize θ while not done do
Sample M features Xi ∼ p(X ). for all Xi do θi,0 ← θ for j ← 0, N do
Evaluate ELBO gradient ∇θi,jLXO (fθi,j ,Xi) w.r.t. observations in K examples Optimize inner model parameters: θi,j+1 ← θi,j −∇θi,jLXO (fθi,j ,Xi)
end for θ′i ← θi,N
end for Evaluate gradient of mean reconstruction error∇θ 1M ∑ Xi∼p(X ) L̂Ti,Ci(fθ′i ,Xi)
Optimize meta-model parameters: θ ← θ −∇θ 1M ∑ Xi∼p(X ) L̂Ti,Ci(fθ′i ,Xi)
end while Output: θ
Notably, since MAML aims to fit parameters that adapt quickly to new tasks, it allows for fine-tuning at evaluation time, that is, training the model for several iterations from the MAML parameter initialization. Here, we evaluate the model with and without fine-tuning.
In the MAML baseline experiments we use M = 4, N = 10, ADAM (Kingma & Ba, 2014) with learning rate α = β = 10−2 for inner and outer model optimization. The model fine-tuned performance is evaluated over {1, 3, 5, 10} epochs and beset results are used. We make use of the higher order optimization facilitated by the higher library (Grefenstette et al., 2019) in the implementation of this baseline.

heading: C APPENDIX: ADDITIONAL RESULTS

text: Here we provide additional results not included in the main text.

heading: C.1 MAML

text: Figure 6 shows the performance of the MAML baseline for different numbers of fine-tuning epochs and with no fine-tuning. As expected, the baseline with no fine-tuning is outperformed by those where fine-tuning is employed. For the Neuropathic Pain and E-learning datasets, the increase in the number of fine-tuning epochs corresponds to improvement in performance (greater AUROC), whereas in case of MovieLens-1M, performance drops (RMSE increases) with longer fine-tuning, particularly for the smaller context set sizes.

heading: C.2 K-NEAREST NEIGHBOUR HEAD PARAMETERS

text: We consider k-Nearest Neighbour Head Parameters baselines for the values k ∈ {1, 5, 10}. Figure 7 shows the performance of this baseline for the different values of k across a range of context set sizes. We expect that as k is increased further, and the number of head parameters averaged over grows, the behaviour will approach that of the mean head parameter baselines. In the main text, 10-Nearest Neighbours is used throughout, as it yields good performance in both the low and high-data regimes.

heading: C.3 FINE-TUNING

text:
In the main text, we show the performance of training the new decoder heads on their context sets from randomly initialized parameters for 10 epochs (see results for “Train from Random (10 epochs)”), in order to provide a trade-off between predictive accuracy and computational cost. This section aims to elaborate further on this trade-off. In Figure 8a, we show the predictive performance of the P-VAE on the meta-test set after training randomly initialized head parameters for an increasing number of epochs, for a range of context set sizes k. We see that the performance improves with training in all cases, with better performance achieved as the context set size k increases, and thus the effect of over-fitting is lessened.
Furthermore, in Figure 8b, we perform the same experiment but instead initialising the heads with the CHN parameters. We see that in all cases except k = 0 and k = 32, training by gradient descent leads to a decrease in performance due to over-fitting, suggesting that the CHN has an implicit regularising effect on the parameter initialisation. We note also that in all cases, the untrained CHN parameters substantially outperform those trained from the random initialisation for all values of k, even after 25 training epochs, with many of the training curves appearing to approach convergence.

heading: C.4 RMSE VALUES FOR BINARY DATASETS

text: In Figure 9 we provide the RMSE values (lower is better) for the main paper experiments run on the Neuropathic Pain and E-learning datasets. We see that the relative performance ordering of methods in terms of RMSE is largely identical to the performance ordering obtained from the AUC results, suggesting that the proposed CHN approach is indeed better than other baselines.

heading: C.5 METADATA ABLATION STUDY

text: It is possible to obtain an ablation for removing the usage of the context set Cn as an input to the CHN by looking at the performance for k = 0 in any of the preceding performance plots. In order to further investigate the effect of metadata on the CHN’s performance, we additionally perform an ablation on MovieLens-1M by removing the use of metadata (movie genre and year) as an input to the CHN. We also compare the performance of averaging all trained head parameters, vs. averaging all trained head parameters whose features are a subset of those of the new feature under consideration. The results of these ablations can be found in Figure 10. We see that in both cases, in absolute terms the difference in performance due to the metadata is slight, with a small improvement made to the mean head parameter performance, and a very slight improvement to the CHN performance when k = 0. This is likely due to the metadata carrying very little information for this dataset relative to the data points themselves, so that when k ≥ 1 the CHN is able to effectively disregard the metadata in favour of the observed data points. Future work could investigate the performance of CHNs on datasets with richer and more information feature metadata.

heading: D APPENDIX: EXPERIMENT DETAILS

text:
All models were implemented in PyTorch (Paszke et al., 2017). All experiments were performed on a single Nvidia Tesla K80 GPU. For training both the P-VAE and the CHN’s parameters, the ADAM (Kingma & Ba, 2014) optimizer was used with β1 = 0.9, β2 = 0.999 and ε = 10−8
Details of hyperparameters and model architectures used for each dataset can be found in Table 2.