Quantifying Long Range Dependence in Language and User Behavior to improve RNNs

Francois Belletti, Minmin Chen, Ed H. Chi

Abstract

Standard Recurrent Neural Networks (RNNs) often treat all historical information with equal computational weight, leading to inefficiencies when processing sequences with Long Range Dependence (LRD). This paper introduces a model-independent framework to quantify LRD in discrete data like text and user interactions. By demonstrating that these sequences follow power-law decay patterns, the authors propose EvolutiveRNNs (EvoRNNs). These models dynamically adjust hidden state capacity based on temporal distance, achieving state-of-the-art performance with significantly reduced computational overhead.

Introduction

In sequential modeling, the fundamental assumption is that the past informs the future. However, the rate at which information relevance decays is rarely uniform. Most standard architectures, such as LSTMs or GRUs, allocate constant computational resources to every step in a sequence. This approach is inefficient for data exhibiting Long Range Dependence (LRD), where correlations persist over long durations and decay according to a power law rather than an exponential one.

Quantifying LRD in domains like natural language processing and recommendation systems has historically been challenging because these datasets consist of discrete symbols (words, item IDs) rather than continuous signals. Furthermore, production systems like YouTube require models that can maintain long-term memory while adhering to strict latency constraints (often <100ms).

Methodology: Estimating LRD and EvoRNNs

The authors bridge the gap between classical time-series analysis and deep learning with two primary innovations.

LRD Estimation for Discrete Sequences

To measure memory in discrete data, symbols are first mapped to high-dimensional, real-valued embeddings. The researchers then apply log-periodogram regression to the spectral density of these embedding sequences. By measuring the slope of the spectrum at low frequencies, they estimate the LRD coefficient ($d$), which quantifies the "memory" retained over time.

Process for estimating LRD coefficients from discrete symbol sequences using embeddings and FFT.

EvolutiveRNN (EvoRNN) Architecture

Finding that relevance decays via a power law, the authors designed the EvoRNN. In this architecture, the RNN cell size (number of hidden units $h$) is a function of the temporal distance from the prediction point:

  • Distant Past: Processed by small RNN cells with low capacity to minimize compute on noisier, less relevant signals.
  • Recent Past: Processed by large RNN cells with high capacity to capture fine-grained details.

Learned projection matrices are used to resize the hidden state as it transitions between cells of different sizes.

Experimental Setup

The framework was evaluated across three diverse datasets:

  • Wikipedia (2014): Measuring LRD in natural language using 300-dimensional GloVe embeddings.
  • Billion Word Benchmark (LM1B): A language modeling task modified to predict the final 4 words of a 128-word sequence, testing long-range predictive capabilities.
  • YouTube User Interaction Data: A massive dataset comprising over 200 million anonymized sequences, including item IDs, creator IDs, page types, and operating systems.

Insights into Sequence Memory

The study confirms that both natural language and user behavior exhibit significant LRD. A key finding was that different types of information retain memory differently. For instance, "software interface" interactions (OS/UI) demonstrated higher LRD coefficients than individual item clicks, suggesting that UI-related behavior is more stable over long periods.

Long memory coefficients (d) for different YouTube input components, showing higher LRD for software interface embeddings.

Processing the distant past with fewer hidden units acts as an effective architectural prior. Since signals from the distant past are often noisier relative to the current target, smaller cells provide a robust bottleneck that prevents the model from overfitting to irrelevant historical noise.

Key Results

  • Efficiency in Language Modeling: On the LM1B benchmark, the PowerLawEvoRNN outperformed LSTM baselines while requiring approximately 21x fewer floating-point operations (24.9M vs 536.8M). It achieved lower perplexity faster in wall-clock time.
  • Scalability in Recommendations: For YouTube sequential recommendation, EvoRNNs matched the Mean Average Precision (MAP@20) of constant-size GRU baselines while utilizing only 20% of the compute.
  • Necessity of Long-Term Memory: Models that entirely ignored the distant past (ExtrExpRNN) performed significantly worse, confirming that while the distant past requires less compute, its contribution remains vital for accuracy.

Limitations and Future Work

While promising, the current approach has limitations. The LRD estimation relies on Fast Fourier Transforms (FFT), which assume equally spaced events—a condition often violated by irregular user interaction timing. Future work may involve using point-process estimators. Additionally, while EvoRNNs reduce FLOPs, they currently increase the memory footprint by storing multiple sets of RNN parameters. The authors suggest exploring parameter sharing or randomized projections to mitigate this. Finally, the overhead of projection matrices between cells could be further reduced using structured linear operators.

Summary updated

BibTeX
@inproceedings{belletti2019quantifying,
  author = {Francois Belletti and Minmin Chen and Ed H. Chi},
  title = {{Quantifying Long Range Dependence in Language and User Behavior to improve RNNs}},
  booktitle = {ACM SIGKDD Conference on Knowledge Discovery and Data Mining},
  year = {2019},
  url = {https://openreview.net/forum?id=LPdyNcPySp-},
}

Loading related content...

Figure