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.
Introduction
In many sequence-to-sequence learning tasks, such as speech recognition or video analysis, the input sequence is significantly longer than the target output sequence. For instance, a few seconds of audio may contain hundreds of frames but correspond to only a handful of phonemes or words. Standard Recurrent Neural Networks (RNNs) often struggle to capture long-term dependencies across such extended inputs.
A common solution is subsampling—reducing the sequence length by selecting a subset of frames. However, making this process learnable is challenging. If a model makes discrete decisions to "keep" or "skip" a frame based on a predicted probability, the sampling operation becomes non-differentiable, preventing the use of standard backpropagation. While Reinforcement Learning (RL) techniques like REINFORCE can address this, they are often unstable and difficult to tune. This paper proposes an alternative: computing the expected output of the sampling process analytically, allowing for end-to-end training using standard calculus.
The Subsampling Mechanism
The proposed mechanism processes an input sequence $S = (s_1, s_2, \dots, s_T)$. For each input vector $s_t$, a sub-network (typically an LSTM followed by a sigmoid layer) predicts a "keep" probability $e_t \in [0, 1]$. This probability represents the likelihood that the vector $s_t$ should be included in the final output sequence $Y = (y_1, y_2, \dots, y_M)$.
The core innovation lies in how the output sequence is constructed during training. Instead of performing a hard sampling step, the model computes a "soft" version of the subsampled sequence. This is achieved by treating the output at each position $m$ as a weighted sum of all possible input vectors, where the weights are derived from the joint probabilities of different sampling trajectories.
Differentiable Training via Dynamic Programming
To make the mechanism differentiable, the authors compute the expected output sequence. This requires calculating $p(y_m = s_n)$, the probability that the $m$-th element of the output sequence is the $n$-th element of the input sequence.
Because the subsampling must be monotonic (the model cannot pick $s_n$ for $y_m$ and then pick $s_{n-k}$ for $y_{m+1}$), the number of possible trajectories is constrained. The authors derive a recurrence relation that allows these probabilities to be computed efficiently using dynamic programming.
By calculating these marginal probabilities, the entire operation—from input processing to sequence shortening—becomes a series of differentiable multiplications and additions. This "Training in Expectation" approach allows the model to learn the optimal filtering strategy directly from the task loss.
Experimental Evaluation
The mechanism was evaluated on a complex logic-based toy problem designed to test its ability to maintain internal state and make precise emission decisions.
The Toy Task
The input consists of a sequence of symbols {0, 1, 2}. The model must maintain an internal "memory" and follow specific rules: depending on its current memory state and the incoming symbol, it must either update its memory and produce no output, or emit a specific symbol. This requires the model to learn a non-trivial state machine and decide exactly when to "emit" a value based on the accumulated context.
Results
The model demonstrated strong performance, achieving over 98% accuracy on sequences up to length $T=500$. Qualitative analysis of the learned $e_t$ values showed that the model successfully learned to "wait" until it had processed enough input symbols to satisfy the logic of the state machine before assigning a high probability to an emission. The model converged relatively quickly, reaching high accuracy within approximately 10,000 minibatches.
Discussion and Limitations
While the "expectation" approach provides a clean, differentiable way to learn subsampling, it faces several practical hurdles:
- Computational Complexity: The dynamic programming algorithm has a complexity of $O(T^2)$. For real-world applications like raw audio processing, where $T$ can be in the thousands, this quadratic scaling becomes a significant bottleneck.
- Vanishing Gradients: The method relies on cumulative products of probabilities. For very long sequences, this can lead to vanishing gradients, making it difficult for the model to learn to skip large sections of the input.
- Scaling: Although highly successful on toy problems, the authors noted that applying the method to large-scale, real-world datasets remains challenging. Future research may need to explore "greedy" approximations to the dynamic program or hybrid approaches that combine expectation-based training with reinforcement learning to improve scalability and stability.
In conclusion, training a subsampling mechanism in expectation offers a mathematically elegant alternative to discrete sampling, providing a path toward more efficient and learnable sequence compression in neural networks.
Summary updated