Abstract
Count-based estimators are a fundamental building block of a number of powerful sequential prediction algorithms, including Context Tree Weighting and Prediction by Partial Matching. Keeping exact counts, however, typically results in a high memory overhead. In particular, when dealing with large alphabets the memory requirements of count-based estimators often become prohibitive. In this paper we propose three novel ideas for approximating count-based estimators using bounded memory. Our first contribution, of independent interest, is an extension of reservoir sampling for sampling distinct symbols from a stream of unknown length, which we call K-distinct reservoir sampling. We combine this sampling scheme with a state-of-the-art count-based estimator for memoryless sources, the Sparse Adaptive Dirichlet (SAD) estimator. The resulting algorithm, the Budget SAD, naturally guarantees a limit on its memory usage. We finally demonstrate the broader use of K-distinct reservoir sampling in nonparametric estimation by using it to restrict the branching factor of the Context Tree Weighting algorithm. We demonstrate the usefulness of our algorithms with empirical results on two sequential, large-alphabet prediction problems.
Introduction
In machine learning tasks such as natural language processing and reinforcement learning, estimating the probability of future symbols based on historical frequency is a core requirement. While standard count-based estimators are effective, their memory footprint grows linearly with the number of unique symbols observed. This becomes a critical bottleneck when dealing with massive alphabets, such as high-resolution images or extensive text corpora. This paper addresses the challenge of "budget sequential prediction," proposing methods to maintain accurate frequency estimates within a fixed memory budget $O(K)$, even as the data stream grows indefinitely.
Methods
The authors introduce three primary innovations to achieve memory-efficient estimation:
- $K$-distinct Reservoir Sampling: Unlike standard reservoir sampling, which may fill with duplicates of frequent items, this algorithm maintains the first $K$ unique symbols from a random permutation of the stream. It uses a concise summary to track symbols and the gaps between them in a virtual permutation.
- Budget SAD: This integrates the sampling scheme with the Sparse Adaptive Dirichlet (SAD) estimator. Budget SAD tracks the most significant symbols in the reservoir and utilizes a "discard counter" ($z_t$) to adjust probability estimates for symbols evicted from memory, ensuring the sum of probabilities remains normalized.
- Branch Pruning in CTW: The $K$-distinct sampling is applied to the Context Tree Weighting (CTW) algorithm to limit the branching factor at each node. This allows the model to prune less useful subtrees, preventing the memory explosion typically associated with tree-based context models.
Experimental Evaluation
The proposed algorithms were evaluated on two distinct large-alphabet tasks:
- Synthetic Image Domain: A stream of 50x60 pixel, 8-bit images. With a total possible alphabet size of $256^{3000}$, traditional counting is impossible. The source emits base images corrupted by varying noise levels.
- Wikipedia Clean Text: A dataset comprising 713 million characters. This was used to evaluate branch pruning in the Context Tree Switching (CTS) algorithm, a CTW variant.
Key Results
The experiments demonstrated that limiting memory can act as a form of regularization. By forcing the estimator to "forget" infrequent symbols, the model avoids wasting resources on noise.
- Memory Efficiency: In the synthetic image task, Budget SAD achieved prediction redundancy comparable to the full SAD estimator while using only 0.01% of the memory.
- Scalable Language Modeling: On the Wikipedia dataset, branch pruning reduced memory usage by 44.6% with a negligible increase in prediction error (less than 5%).
Discussion and Future Work
While the algorithm performs well in practice on non-stationary data like Wikipedia, the current theoretical analysis assumes a stationary source. Future research may focus on establishing theoretical bounds for non-stationary cases and refining the "unseen" symbol estimation. Additionally, the authors noted that heavy-tailed distributions—where many rare symbols collectively appear frequently—pose a challenge for $O(n \log n)$ redundancy, suggesting a need for more sophisticated prevalence estimation for symbols outside the reservoir.
Summary updated