PaperlayerView exact revision on arXiv

Source-linked AI summary

Unbiasing Truncated Backpropagation Through Time

Corentin Tallec, Yann Ollivier

arXiv:1705.08209v1cs.NEcs.LG

TL;DR

Truncated BPTT reduces the cost of learning from long sequences, but its gradient estimates are biased. ARTBP randomizes truncation lengths and reweights backpropagation to obtain unbiased estimates; it converges reliably on a synthetic task and slightly outperforms truncated BPTT on Penn Treebank character-level modeling.

  • Problem

    Truncated BPTT reduces the need to backpropagate through entire long sequences, but its gradient estimates are biased.

    Source: §1 · p. 2, §2 · p. 4

  • Method

    ARTBP randomizes truncation points and reweights gradient flows in the backpropagation equation to produce an unbiased estimate.

    Source: §3 · pp. 5–6

  • Results

    ARTBP converges reliably where truncated BPTT diverges on the influence-balancing task and slightly outperforms it on Penn Treebank character-level modeling.

    Source: §6.1 · pp. 9–10

  • Takeaways & Limitations

    ARTBP is experimentally viable and provides proper balancing of effects across time scales when training recurrent models.

    Source: §7 · p. 11

    Stochastic truncation points introduce noise into ARTBP's gradient estimates.

    Source: §3 · p. 6

Abstract

from arXiv · show

Truncated Backpropagation Through Time (truncated BPTT) is a widespread method for learning recurrent computational graphs. Truncated BPTT keeps the computational benefits of Backpropagation Through Time (BPTT) while relieving the need for a complete backtrack through the whole data sequence at every step. However, truncation favors short-term dependencies: the gradient estimate of truncated BPTT is biased, so that it does not benefit from the convergence guarantees from stochastic gradient theory. We introduce Anticipated Reweighted Truncated Backpropagation (ARTBP), an algorithm that keeps the computational benefits of truncated BPTT, while providing unbiasedness. ARTBP works by using variable truncation lengths together with carefully chosen compensation factors in the backpropagation equation. We check the viability of ARTBP on two tasks. First, a simple synthetic task where careful balancing of temporal dependencies at different scales is needed: truncated BPTT displays unreliable performance, and in worst case scenarios, divergence, while ARTBP converges reliably. Second, on Penn Treebank character-level language modelling, ARTBP slightly outperforms truncated BPTT.

1 Related Work

BPTT is costly on long sequences, while fixed truncation reduces that cost at the expense of biased gradients. ARTBP instead compensates for truncation within backpropagation, unlike memoryless online alternatives that inject noise into gradient estimates.

1 Related Work

  • BPTT is impractical for very long sequences because storing and backpropagating through all timesteps consumes resources and slows learning.Storage remedies can increase computational cost.Source: §1 · p. 2
  • Fixed-length truncated BPTT retains hidden states between subsequences but biases gradients and removes theoretical convergence guarantees.Its learning of dependencies above the truncation range is difficult, although retained states may preserve information about the distant past.Source: §1 · p. 2
  • NoBackTrack and UORO provide scalable unbiased online learning but require memorylessness and inject noise through random rank-one reduction.Source: §1 · p. 2
  • ARTBP is not memoryless and avoids artificial gradient noise by compensating for truncations directly in the backpropagation equation.Source: §1 · p. 3

2 Background on recurrent models

Recurrent learning optimizes a dynamical system so its predictions approach target outputs. BPTT computes gradients across time, while truncation lowers sequence-processing demands but produces biased estimates.

2 Background on recurrent models

  • Recurrent learning seeks parameters that make a dynamical system's output sequence approximate known target outputs.A standard RNN state combines output-layer activations and hidden recurrent-layer activations.Source: §2 · p. 3
  • BPTT unfolds the system through time and sums each timestep's parameter effect on subsequent losses to compute the gradient.The backpropagation equations extend classical equations for a simple RNN.Source: §2 · pp. 3–4
  • Full-sequence BPTT requires storing and processing the entire history in both directions, slowing learning on long sequences.Source: §2 · p. 4
  • Truncated BPTT splits sequences into fixed-length subsequences, cuts gradient flow at their boundaries, and can be applied online.The recurrent hidden state is maintained, and an early subsequence's estimate does not depend on later timesteps.Source: §2 · p. 4
  • Truncated BPTT gives biased gradient estimates that can remain far from the true gradient even with large truncation lengths, sometimes leading to divergence.Source: §2 · p. 4

3 Anticipated Reweighted Backpropagation Through Time: unbiasedness through reweighted stochastic truncation lengths

ARTBP randomizes truncation points and reweights backpropagation to compensate for omitted gradient flows. Averaged over its truncations, its gradient estimate is unbiased, though stochastic cut points introduce noise.

3 Anticipated Reweighted Backpropagation Through Time: unbiasedness through reweighted stochastic truncation lengths

  • ARTBP usually maintains the internal state across subsequences and can process them sequentially, sampling each next truncation point as it proceeds.Figure 1 depicts forward and backward propagations and dots for internal-state or gradient resets.Source: §3 · p. 4, Figure 1 · p. 5
  • ARTBP uses variable-length subsequences and modifies the backpropagation equation with reweighting factors tied to truncation probabilities.Unbiasedness holds for any allowed choice of truncation probabilities, but those choices yield different gradient-estimate variances.Source: §3 · p. 5
  • Averaged over ARTBP truncations, the resulting gradient estimate is an unbiased estimate of the total-loss gradient.The method defines truncation through binary random variables and assumes each conditional truncation probability is below one.Source: §3 · pp. 5–6
  • When a gradient flow is cut with probability c_t, its contribution is omitted; when it is retained, a factor 1/(1-c_t) restores its average contribution.Thus the expected contribution matches standard, non-truncated BPTT.Source: §3 · p. 6
  • Stochastic truncation points add noise to ARTBP's gradient estimate, trading memory consumption associated with longer subsequences against variance.Source: §3 · p. 6

4 Choice of ct and memory/variance tradeoff

ARTBP's truncation-probability schedule balances subsequence length and compensation-factor growth. The proposed schedule controls average length and yields finite length variance when α > 3.

4 Choice of ct and memory/variance tradeoff

  • Larger truncation probabilities shorten subsequences but increase compensation factors and make estimates noisier; constant probabilities can make cumulative factors grow exponentially.A fixed-length truncated-BPTT range L and constant ARTBP probability c = 1/L are comparable in memory use.Source: §4 · p. 6
  • The proposed schedule sets truncation probability using time since the last cut, targeting average subsequence length L0 and finite standard deviation.The schedule makes the probability of a length-L subsequence decrease like L^-α; the length variance is finite when α > 3.Source: §4 · p. 7
  • The parameter α controls which moments of subsequence length are finite, while larger α makes long subsequences less frequent but increases compensation factors.With this schedule, cumulative factors within a length-L subsequence grow polynomially like L^(α-1).Source: §4 · p. 7
  • If the system's transition operator usually has geometrically decaying memory, the reweighted gradient remains controlled under the proposed schedule.Source: §4 · p. 7

5 Online implementation

ARTBP can be applied online by sampling truncation points as training proceeds, enabling unbiased gradient estimates for recurrent networks.

5 Online implementation

  • ARTBP can provide unbiased gradient estimates for recurrent networks in an online setting.Truncation points need not be drawn in advance.Source: §5 · p. 7
  • At each step, sample the next truncation point and perform forward and backward passes through that subsequence.The procedure can begin with the first sampled truncation point and continue to the next subsequence.Source: §5 · p. 7
  • After each subsequence, apply a partial gradient-descent update using its resulting gradient.Source: §5 · p. 7

6 Experimental validation

The experiments assess ARTBP’s theoretical properties and viability on real-world data. ARTBP converges reliably in the synthetic influence-balancing task and slightly improves Penn Treebank validation and test error, though not training error.

6.1 Influence balancing

  • The synthetic task pits short-term positive signals against delayed negative influences, with p=10 and n=13 agents and the leftmost agent as the optimization target.The setup uses a row of agents that diffuse part of their state to the agent on the left.Source: §6.1 · pp. 8–9
  • ARTBP converges reliably where truncated BPTT diverges, while on Penn Treebank it slightly improves validation and test error but trails on training error.Source: Figure 3 · p. 9, §6.1 · pp. 9–10, Figure 4 · p. 10
  • Penn Treebank runs trained an LSTM character predictor using fixed 50-step truncations or ARTBP sampled truncations with L0=50 and α=4.Adam updates used learning rate 10^-4, and six runs were plotted to test reliability; subsequences were not shuffled because the hidden state was retained.Source: §6.1 · p. 10
  • Test error was 1.43 bpc with truncated BPTT and 1.40 bpc with ARTBP, versus similar-LSTM reports of 1.38 bpc [CBLC16] to 1.26 bpc [Gra13].The authors suggest setup differences may explain the gap; their setup omitted subsequence shuffling and gradient clipping, both of which would break unbiasedness.Source: §6.1 · p. 11

7 Conclusion

The conclusion states that randomized truncation points and compensation factors can offset truncation bias. The resulting algorithm is experimentally viable and balances effects across timescales.

7 Conclusion

  • Randomized truncation points and compensation factors in the backpropagation equation can compensate for truncation bias.Source: §7 · p. 11
  • ARTBP is experimentally viable for training recurrent models.Source: §7 · p. 11
  • The algorithm provides proper balancing of effects at different timescales in recurrent-model training.Source: §7 · p. 11

8 Proof of Proposition 1

Backward induction establishes that the expected ARTBP gradient estimate matches the ordinary BPTT gradient at each timestep.

8 Proof of Proposition 1

  • Backward induction establishes that the expected ARTBP gradient estimate equals ordinary BPTT’s gradient at each timestep.The proof concludes by applying the induction hypothesis at the preceding timestep.Source: §8 · pp. 11–12
  • At t = T, the equality holds by definition, establishing the induction base.The proof then assumes the claim at time t + 1 to establish it at time t.Source: §8 · p. 11
  • For X_t = 0, substituting the recurrence into (20) yields an expression that the induction hypothesis at time t + 1 identifies as exactly ∂ℓ.Source: §8 · p. 12

Related papers

Loading 1705.08209v1…