Sparse Attentive Backtracking: Temporal CreditAssignment Through Reminding

By Nan Rosemary Ke, Anirudh Goyal, Olexa Bilaniuk, Jonathan Binas, Michael C. Mozer, C. Pal, Yoshua Bengio. 2018

94 citations recorded by the source corpus.

Learning long-term dependencies in extended temporal sequences requires credit assignment to events far back in the past. The most common method for training recurrent neural networks, back-propagation through time (BPTT), requires credit information to be propagated backwards through every single step of the forward computation, potentially over thousands or millions of time steps. This becomes computationally expensive or even infeasible when used with long sequences. Importantly, biological brains are unlikely to perform such detailed reverse replay over very long sequences of internal states (consider days, months, or years.) However, humans are often reminded of past memories or mental states which are associated with the current mental state. We consider the hypothesis that such memory associations between past and present could be used for credit assignment through arbitrarily long sequences, propagating the credit assigned to the current state to the associated past state. Based on this principle, we study a novel algorithm which only back-propagates through a few of these temporal skip connections, realized by a learned attention mechanism that associates current states with relevant past states. We demonstrate in experiments that our method matches or outperforms regular BPTT and truncated BPTT in tasks involving particularly long-term dependencies, but without requiring the biologically implausible backward replay through the whole history of states. Additionally, we demonstrate that the proposed method transfers to longer sequences significantly better than LSTMs trained with BPTT and LSTMs trained with full self-attention.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Reinforcement Learning

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

In Reinforcement Learning

Citations in the corpus

Transformer-XL: Attentive Language Models beyond a Fixed-Length Context (2019, background): “, 2018), augmented memory structure (Ke et al., 2018) and others that modify the internal architecture of RNNs to ease the optimiza-”
RUDDER: Return Decomposition for Delayed Rewards (2018, background): “EQerZV. 1 Introduction Assigning credit for a received reward to past actions is central to reinforcement learning [128]. A great challenge is to learn long-term credit assignment for delayed rewards [65, 59, 46, 106]. Delayed rewards are often episodic or sparse and common in real-world problems [9”
Recurrent Independent Mechanisms (2019, background): “, 2014b) 3 3 7 7 SAB(Ke et al., 2018) 7 3 7 7 IndRNN(Li et al.”
Coordination Among Neural Modules Through a Shared Global Workspace (2021, methodology): “One can also use a top-k softmax (Ke et al., 2018) to select a ﬁxed number of specialists allowed to write in the shared workspace: based on the pre-softmax values, a ﬁxed number of k specialists which have the highest values are selected, and get access to write in the shared workspace.”
Inductive biases for deep learning of higher-level cognition (2020, background): “What we showed earlier (Ke et al., 2018; Kerg et al., 2020) is that this prior assumption is the strongest ingredient to bound the degree of vanishing of gradients.”
Towards mental time travel: a hierarchical memory for reinforcement learning agents (2021, background): “[25] Nan Rosemary Ke, Anirudh Goyal, Olexa Bilaniuk, Jonathan Binas, Michael C Mozer, Chris Pal, and Yoshua Bengio.”
Self-Attentional Credit Assignment for Transfer in Reinforcement Learning (2019, unknown): “SAB [Ke et al. , 2018 ] is a sparse attention mechanism used to derive a mod-iﬁed backpropagation algorithm.”
COVI White Paper (2020, methodology): “Note that the number of inputs of the predictor is variable as it depends on the number of contacts, so we have used a Transformer deep learning architecture [91], which can also capture dependencies across the whole history of the user (14 days and the list of all contacts) without suffering from t”
BasicVSR++: Improving Video Super-Resolution with Enhanced Propagation and Alignment (2021, methodology): “These methods demonstrate improvements in different tasks including classification [16] and language modeling [25].”
Fast and Slow Learning of Recurrent Independent Mechanisms (2021, methodology): “Then a soft key-value based attention mechanism (Bahdanau et al., 2014; Vaswani et al., 2017; Santoro et al., 2018) is used to select the top-k modules that pay most attention to input x t in a differentiable way using a sparse softmax (Ke et al., 2018; Goyal et al., 2019).”
Sequence Modeling of Temporal Credit Assignment for Episodic Reinforcement Learning (2019, background): “Sparse Attentive Backtracking[19] applies the attentive mechanism for network straining, while ours focuses on learning the decomposition of the reward signal.”
Calibration, Entropy Rates, and Memory in Language Models (2019, background): “…& Zweig, 2012; Ji et al., 2015; Wang & Cho, 2016) or document-level topics (Wang et al., 2017) to using LSTM recurrent neural networks with careful initialization (Le et al., 2015), auxiliary loss signals (Trinh et al., 2018) or augmented memory structures (Grave et al., 2016; Ke et al., 2018).”
Generalization of Reinforcement Learners with Working and Episodic Memory (2019, methodology): “This approach is similar to Sparse Attentive Backtracking (Ke et al., 2018, SAB) which uses sparse replay by passing gradients only through memories selected as relevant at each step.”
Generative Pretraining From Pixels (2020, methodology): “Ke et al. (2018) introduced the pixel-by-pixel CIFAR10 task and ﬁrst benchmarked the performance of a 1D sequence transformer on a competitive image classiﬁcation dataset.”