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.
- 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.
- 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.
- Complexity: This DP approach allows the model to compute the expected output in $O(T^2)$ time, where $T$ is the input sequence length.
- 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 a0. If it sees a1followed by a2, it should output a2. - 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.
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