Training a Subsampling Mechanism in Expectation

Colin Raffel, Dieterich Lawson

Introduction

In many sequence-to-sequence tasks, input data is often "oversampled." For example, in speech recognition, audio frames might be recorded every 10 milliseconds, but the actual phonemes change much more slowly. Standard methods for shortening these sequences, like pooling or striding, rely on fixed rules and cannot adapt dynamically to the underlying data.

Researchers at Google Brain have developed a method to make sequence subsampling—the process of picking specific, relevant elements from a stream of data—fully differentiable. By calculating the "expected" output of a stochastic sampling process using dynamic programming, they enable neural networks to learn exactly which parts of an input sequence are worth keeping using standard backpropagation.

The Sampling Bottleneck

The ideal solution to oversampled data is a learnable subsampling mechanism where the model decides which elements to keep. However, deciding to keep an element is a discrete, stochastic operation (akin to flipping a coin). This creates a "sampling bottleneck" that breaks backpropagation because gradients cannot be passed through a random choice. Traditionally, researchers resort to complex Reinforcement Learning techniques (like REINFORCE) to bypass this, but these methods can be unstable and slow to converge.

Methods: Training in Expectation

To overcome the sampling bottleneck, the authors propose a "Training in Expectation" approach. Instead of sampling a single discrete sequence during training, the model computes the probability distribution over all possible subsampled sequences.

Illustration of the subsampling mechanism where elements are kept based on predicted probabilities.
  1. The Mechanism: For every input vector $s_t$, the model predicts a probability $e_t \in [0, 1]$ of including that element in the final output.
  2. The Math: To make this process differentiable, the authors utilize a dynamic programming (DP) algorithm. They analytically compute $p(y_m = s_n)$—the probability that the $m$-th element of the output sequence is exactly the $n$-th element of the input.
  3. Complexity: This DP approach allows the model to compute the expected output in $O(T^2)$ time, where $T$ is the input sequence length.
  4. Integration: Because the output is an expectation (a weighted sum of inputs based on their probabilities), the entire operation is continuous and differentiable. This allows for standard end-to-end training without relying on high-variance gradient estimators.

Experimental Setup

The paper evaluates the method on a synthetic toy problem designed to test logic and memory:

  • Input: A sequence of symbols [0, 1, 2].
  • Rules: The model must maintain a "memory." For example, if it sees two 1s in a row, it should output a 0. If it sees a 1 followed by a 2, it should output a 2.
  • Goal: The model must learn to ignore 0s and only "emit" an output when specific conditions are met, effectively subsampling the input based on internal logic.

Key Insights

  • Differentiable Discrete Choices: The core innovation is realizing that you do not need to sample to train. By calculating the marginal probability of each input appearing at each output position, the model bypasses the need for RL-based estimators.
  • Implicit Alignment: This mechanism naturally produces a monotonic alignment between input and output. Unlike Connectionist Temporal Classification (CTC), which inserts "blank" symbols to match lengths, this mechanism actually shortens the sequence length.
  • Hierarchical Potential: The authors suggest this mechanism could be stacked. Multiple layers of subsampling could build a hierarchy where higher layers represent data at increasingly abstract time scales (e.g., frames $\rightarrow$ phonemes $\rightarrow$ words).

Key Results

On the toy problem with sequences up to length $T=500$, the model achieved >98% accuracy after roughly 10,000 minibatches.

Qualitatively, visualization of the probability matrix $p(y_m = s_n)$ showed that the model successfully learned to "wait" until it had seen enough relevant information before emitting an output symbol.

Probability matrix showing the model learning to emit outputs only when specific conditions are met.

Limitations and Future Work

While promising, the approach has a few notable limitations:

  • Computational Scaling: The $O(T^2)$ complexity is a significant hurdle. While fine for short sequences, it becomes prohibitively expensive for very long sequences like raw audio or long documents. The authors suggest greedy approximations or RL-based discrete latent variables as potential fixes.
  • Vanishing Gradients: The use of sigmoids and cumulative products in the DP formulation can lead to vanishing gradients, making it difficult for the model to learn long-range dependencies in the sampling probabilities.
  • Real-World Application: While highly successful on a synthetic task, applying this directly to complex real-world problems will require further optimization of gradient flow and computational efficiency.

Summary updated

Abstract

We describe a mechanism for subsampling sequences and show how to compute its expected output so that it can be trained with standard backpropagation. We test this approach on a simple toy problem and discuss its shortcomings.
BibTeX
@inproceedings{raffel2017training,
  author = {Colin Raffel and Dieterich Lawson},
  title = {{Training a Subsampling Mechanism in Expectation}},
  booktitle = {Workshops @ ICLR},
  year = {2017},
  url = {https://openreview.net/forum?id=ZVzlyO5cPCn},
}
Figure