Count-Based Frequency Estimation with Bounded Memory

1 Introduction

Undoubtedly, counting is the simplest way of estimating the relative frequency of symbols in a data sequence. In the sequential prediction setting, these estimates are used to assign to each symbol a probability proportionate to its frequency. When dealing with binary alphabets the counting approach gives rise to the Krichevsky-Trofimov estimator, known to be minmax optimal [Krichevsky and Trofimov, 1981]. Countbased approaches are also useful in dealing with large alphabets, and a number of methods coexist [Katz, 1987; Tjalkens et al., 1993; Friedman and Singer, 1999; Hutter, 2013], each with its own statistical assumptions and regret properties. While these simple estimators deal only with memoryless sources - whose output is context invariant - they play a critical role as building blocks for more complicated estimators [Cleary and Witten, 1984; Willems et al., 1995; Tziortziotis et al., 2014].

We are interested in the large alphabet setting as it naturally lends itself to the compression of language data, where symbols consist of letters, phonemes, words or even sentence fragments. This setting is also of practical interest in reinforcement learning, for example in learning dynamical models for planning [Farias et al., 2010; Bellemare et al., 2013]. In both contexts, the statistical efficiency of count-based estimators makes them excellent modelling candidates. However, the memory demands of such estimators typically increase linearly with the effective alphabet size M, which is problematic when M grows with the sequence length. Perhaps surprisingly, this issue is more than just a theoretical concern and often occurs in language data [Gale and Church, 1990].

Our work is also motivated by the desire to improve the Context Tree Weighting algorithm [CTW; Willems et al., 1995] to model k-Markov large alphabet sources. While CTW is a powerful modelling technique, its practical memory requirements (linear in the size of the sequence) often preclude its use in large problems. Here, even when the alphabet size is fixed and small, the number of observed k-order contexts typically grows with the sequence length. We are particularly interested in reducing the long term memory usage of such an estimator, for example when estimating attributes of internet packets going through a router or natural language models trained on nonstationary data.

Our solution takes its inspiration from the reservoir sampling algorithm [Knuth, 1981] and the work of Dekel et al. [2008] on budget perceptrons. We propose an online, randomized algorithm for sampling distinct symbols from a data stream; by choosing a sublinear reservoir size, we effectively force our statistical estimator to forget infrequent symbols. We show that this algorithm can easily be combined with a typical count-based estimator, the Sparse Adaptive Dirichlet estimator, to guarantee good statistical estimation while avoiding unbounded memory usage. As our results demonstrate, the resulting estimator is best suited to sources that emit a few frequent symbols while also producing a large pool of low-frequency "noise". We further describe a simple application of our sampling algorithm to branch pruning within the CTW algorithm.

The idea of sampling distinct symbols from a stream is well-studied in the literature. Perhaps most related to ours is the work of Gibbons and Matias [1998], who proposed the notion of a concise sample to more efficiently store a "hot list" of frequent elements. Their algorithm is also based on reservoir sampling, but relies on a user-defined threshold and probabilistic counting. By contrast, our algorithm maintains a reservoir based on a random permutation of the data stream, which avoids the need for a threshold. Gibbons [2001] proposed an algorithm called Distinct Sampling to estimate the number of distinct values within a data stream. Similar to the hot list algorithm, Distinct Sampling employs a growing threshold, which is used to determine when infrequent symbols should be discarded. Metwally et al. [2005] proposed to track frequent symbols using a linked list and a hash table. Their Space Saving algorithm aims to find all frequently occurring items (heavy hitters), rather than provide a frequencybiased sample; a similar scheme was also proposed by Demaine et al. [2002]. Manku and Motwani [2002] proposed a probabilistic counting and halving approach to find all items whose frequency is above a user-defined threshold. Charikar et al. [2004] showed how to use a probabilistic count sketch in order to find frequent items in a data stream. While count sketches may seem the natural fit for count-based estimators, their memory requirements grow quadratically with the accuracy parameter ϵ; by contrast, our algorithm has only a linear dependency on the implied ϵ.

2 Background

In the sequential prediction setting we consider, an algorithm must make probabilistic predictions over a sequence of symbols observed one at a time. These symbols belong to a finite alphabet X, with x1:n := x1 . . . xn ∈ X n denoting a string drawn from this alphabet. A probabilistic prediction consists in assigning a probability to a new symbol xn+1 given that x1:n has been observed.

Let [n] := {1, . . . , n}. We denote the set of finite strings by X ∗ := ⋃∞i=0 X i , denote the concatenation of strings s and r by sr, and use ϵ to represent the empty string. For a set B ⊆ X, we write x1:n \ B := (xi : i ∈ [n], xi /∈ B) to denote the substring produced by excising from x1:n the symbols in B. We denote by Nn(x) := N(x, x1:n) the number of occurrences of x ∈ X within x1:n, and write τn(x) := τ(x, x1:n) for the time of first occurrence of x in x1:n, with τ(x, x1:n) := n + 1 whenever x /∈ x1:n. We denote the set of permutations of x1:n by P(x1:n) and the discrete uniform distribution over X by UX(·). Finally, unless otherwise specified, we write log to mean the natural logarithm.

A coding distribution ρ is a sequence (ρt : t ∈ N) of probability distributions ρt : X t → [0, 1] each respecting

In what follows the subscript to ρt is always implied from its argument; we therefore omit it. A coding distribution assigns conditional probabilities according to

which after rearrangement yields the familiar chain rule ρ(x1:n) := ∏nt=1 ρ(xt | x1:t-1).

A source is a distinguished type of coding distribution which we assume generates sequences. When a coding distribution is not a source, we call it a model. A source (µt : t ∈ N) is said to be memoryless when µt(x | x1:t) = µt(x | ϵ) =: µt(x) for all t, all x ∈ X, and all sequences x1:t ∈ X t ; for B ⊆ X , we then write µt(B) := ∑x∈B µt(x). When µt(x) := µ1(x) for all t, we say it is stationary and omit its subscript.

Let x1:n ∈ X n and let µ be an unknown coding distribution, for example the source that generates x1:n. We define the redundancy of a model ρ with respect to µ as

The redundancy Fn(ρ, µ) can be interpreted as the excess bits (or nats) required to encode x1:n using ρ rather than µ. The expectation of this redundancy with respect to a random sequence x1:n is the Kullback-Leibler divergence KLn(µ ‖ ρ):

Typically, we are interested in how well ρ compares to a class of coding distributions M. The redundancy of ρ with respect to this class M is defined as

Intuitively, Fn(ρ,M) measures the cost of encoding x1:n with ρ rather than the best model inM.

2.1 The Sparse Adaptive Dirichlet Estimator

The Sparse Adaptive Dirichlet estimator [SAD; Hutter, 2013] is a count-based frequency estimator designed for largealphabet sources with sparse support. Informally, the SAD predicts according to empirical frequencies in x1:n, while reserving some escape probability γ for unseen symbols. Given At := ⋃ti=1{xi} the set of symbols seen up to time t and a probability distribution wt over X \ At, the SAD estimator predicts according to

Let MSAD be the class of memoryless sources generating symbols from a subalphabet A ⊆ X of size M. The redundancy of the SAD estimator with respect to this class is bounded as

making it particularly apt at dealing with sparse-support sources.

3 Budget Sequential Estimation

The SAD estimator requires counting the occurrence of all encountered symbols. This is usually undesirable when the observed alphabet grows with the sequence length. Here we propose a sampling solution to this problem; this solution, K-distinct reservoir sampling, lets us impose a memory constraint on our estimator. More broadly, our sampling scheme can be combined with any algorithm with a non-parametric component; as an illustration, in Section 5.2 we apply our solution to restrict the branching factor of the Context Tree Weighting algorithm.

Let µ be an unknown source. We are given a parameter K ∈ N and seek a count-based estimator that predicts x1:n ∼ µ sequentially without using more than O(K) memory. We call this problem the budget, sequential, count-based prediction setting. While similar settings have been studied extensively in the context of linear classifiers [Dekel et al., 2008; Cavallanti et al., 2007; Orabona et al., 2008] and in relation to the 0-1 loss [Lu and Lu, 2011], to the best of our knowledge the notion of a budget count-based frequency estimator is novel. From a practical perspective, we are interested in prediction problems for which the alphabet is large but the source skewed towards a few high-frequency symbols; it is for these problems that we expect meaningful prediction to be achievable.

Our competitor class M is the set of budget multinomial distributions. More specifically, we consider models of the form ρ(x ; Z, θ, θ0) with Z := {xi1 , . . . , xiK } ⊆ X is a subalphabet of cardinality K; θ ∈ RK ; and θ0 ∈ R. Each such model predicts according to

with the usual requirement that ∑x∈X ρ(x ; Z, θ, θ0) = 1. Let µ be a memoryless stationary source and for B ⊆ X let

Finally, arrange X := {x1 , x2 , . . . , xm} in order of decreasing probability, i.e. such that for all i, µ(xi ) ≥ µ(xi+1 ).

Lemma 1. The model ρ∗µ ∈ Mwhich minimizes KL1(µ‖ ·) is

Proof (sketch). We first show that for a fixed Z, the optimal parameters correspond to those given above. We then use the convexity property of the KL divergence, namely that for λ ∈ [0, 1] and pairs of probability distributions (p1, q1), (p2, q2)

with equality when (p1, q1) and (p2, q2) have disjoint support. The result follows by setting p1 = q1 = µZ, and taking p2, q2 to be respectively µX\Z and ρ∗µ,X\Z = UX\Z.

The full proof is provided in the supplemental. The next result shows that the optimal Z ∗ is composed of a combination of the most and least frequent symbols according to µ.

Lemma 2. Let Z ∗ be the subalphabet associated with the model ρ∗µ . Then Z ∗ = H ∪ L, where H, L ⊆ X are disjoint sets such that

• for all x ∈ H, y ∈ X \ H, µ(x) ≥ µ(y), and
• for all x ∈ L, y ∈ X \ L, µ(x) ≤ µ(y).

Proof (sketch). The proof follows by using the identity

for a discrete random variable X distributed over X, with H(X) its entropy [Cover and Thomas, 1991]. We then show that, for Z = {xi}, the function µ(X \ Z)KL1(µX\Z ‖UX\Z) is concave in i. The result is then extended to the general case Z = {xi1 , . . . xiK }.

When µ is known, ρ∗µ can be constructed in time O(K) by considering the different choices of H and L. Furthermore, the set ˆ Z containing the K most frequent symbols achieves an expected redundancy at most 1e + K |X| logK greater than the expected redundancy of ρ∗µ (Lemma 3, supplemental), in our experiments and for large alphabets this redundancy is negligible. In the sequel we therefore assume that Z ∗ = ˆ Z.

However, we are interested in the setting where µ is unknown. In this case, our budget requirement poses a circular problem: we need good estimates of µ to find Z ∗ , and simultaneously need Z ∗ to estimate µ (with bounded memory). Our solution is to maintain a time-varying set Y which contains (with high probability) the K most frequent symbols.

We call our algorithmK-distinct reservoir sampling, in relation to the reservoir sampling algorithm [Knuth, 1981]. As we shall see in Section 3.2, we can leverage K-distinct reservoir sampling to approximate the SAD estimator by estimating the frequency of symbols in Y. We call the resulting approximation the Budget Sparse Adaptive Dirichlet estimator, or Budget SAD for short.

3.1 K-Distinct Reservoir Sampling

Let x1:n be a string of a priori unknown length and let K ∈ N. Reservoir sampling [Algorithm R; Knuth, 1981] is an algorithm for sampling y := y1 . . . yK ∈ X K from x1:n, without replacement and using O(K) memory. It proceeds as follows:

1. Randomly assign x1 . . . xK to y1 . . . yK.
2. For t = K + 1, . . . , n, draw r ∼ U ({1, . . . , t}). If
3. (b) otherwise do nothing.
4. (a) r ≤K, then assign xt to yr;

We would like to use reservoir sampling to sample an approximation to Z ∗ . However, Algorithm R is inadequate for our purposes: since y may contain duplicates, sampling K distinct items may require significant memory. Our solution is to modify Algorithm R to compactly represent duplicates. We begin with the following observation:

Observation 1. Let ˜x1:n be a random permutation of x1:n, that is ˜x1:n ∼ U (P(x1:n)). Then y := ˜x1 . . . ˜xK is a sample of size K sampled without replacement from x1:n.

We can therefore interpret Algorithm R as maintaining the first K elements of a random permutation of x1:n. By analogy, we define the K-distinct operator, which describes the first K distinct elements of a string:

Definition 1. Let w1:m ∈ X m. The K-distinct operator φK : X ∗ → ⋃Ki=0 X i is recursively defined as

The next step is to use this operator to define a K-distinct sample of x1:n. From here onwards, we assume without loss of generality that sequences contain at least K distinct symbols.

Definition 2. Let Yn := Y (x1:n) be a random variable taking values in X K , and let ˜x1:n ∼ U (P(x1:n)). Then Yn is a K-distinct sample of x1:n if

In our algorithm, the simple reservoir is replaced by a Kconcise summary which keeps track of these K first distinct symbols and their times τ(·, w1:m) of first occurence:

Definition 3. Let w1:m ∈ X m with y1 . . . yK+1 := φK+1(w1:m). The K-concise summary of w1:m is a vector of K pairs S := 〈(yi, di) ∈ X × N〉 such that, for all i ≤ K,

Each pair (yi, di) in the K-concise summary of a string thus describes this string's ith distinct symbol and the gap di between this distinct symbol and the next (Figure 1, bottom row).

In the spirit of Algorithm R, K-distinct reservoir sampling incrementally generates a random permutation ˜x1:n through a sequence of insertions, and maintains the K-concise summary of this permutation. Effectively, this summary allows us to describe the beginning of ˜x1:n compactly (using O(K) memory), while preserving the information needed for later updates.

For x ∈ X, r ∈ [DK+1], and S := 〈(yi, di) : i ∈ [K]〉, define the vector and set of stored symbols

as well as the indices I : Y(S) → [K] and J : [DK+1] → [K]:

In K-distinct reservoir sampling (Algorithm 1), I(x) and J(r) are used to indicate, respectively, the index of x in S and the index in S at which a new symbol should be inserted. For example, in Figure 1 (left) I('B′ ) = 2 and J(3) = 3.

Algorithm 1 K-Distinct Reservoir Sampling.

Initially: S = 〈〉 SAMPLE(K, x1:n) for t = 1 . . . n do Observe xt Draw r ∼ U ({0, . . . , t - 1}) if r > DK+1 then do nothing else if xt /∈ Y(S) then INSERT(S, xt, r) else if I(xt) < J(r) then dJ(r)-1 ← dJ(r)-1 + 1 else MERGE(S, xt) and INSERT(S, xt, r) Output y(S) INSERT(S, xt, r) Insert (xt, DJ(r) - r + 1) at position J(r) in S if J(r) > 1 then dJ(r)-1 ← r - DJ(r)-1 if |S| > K then remove item K + 1 from S MERGE(S, xt) dI(xt)-1 ← dI(xt)-1 + dI(xt) Remove item I(xt) from S

Theorem 1. When Algorithm 1 terminates, its summary S is the K-concise summary of a permutation ˜x1:n sampled uniformly at random from P(x1:n).

Proof (sketch). Let r1:n be the string of random integers generated by Algorithm 1. These induce a sequence (˜xt1:t : t ∈ N) of permutations of x1:n. To show the correctness of Algorithm 1, we simply show that its operations mirror this sequence of permutations and incrementally generate the sequence of K-concise summaries of ˜xt1:t . The different cases handled by Algorithm 1 then arise from different kinds of insertions.

Corollary 1. Algorithm 1 outputs a K-distinct sample of x1:n.

Note here the significance of Theorem 1: we can simulate, in a fully online fashion and in O(K) memory and running time, the sampling of a permutation ˜x1:n ∼ U (P(x1:n)) and the subsequent selection of its first K distinct symbols. Interestingly enough, the use of random insertions, rather than swaps (as is done in Algorithm R), seems necessary to guarantee the correct distribution on y(S).

3.2 The Budget SAD Estimator

Naturally, we wish to use K-distinct reservoir sampling to approximate the set Z ∗ of frequently occurring symbols in x1:n.

However, the di variables do not estimate the frequencies of their respective symbols. To estimate these frequencies, our Budget Sparse Adaptive Dirichlet estimator augments a Kconcise summary with count information. The new summary is a vector of tuples

where ci represents the number of occurrences of yi since its last entering the summary.

Algorithm 2 Budget SAD.

Initially: U = 〈〉, z = 0 for t = 1 . . . n do Predict xt according to Equation 2 Observe xt Update U as per Algorithm 1 if xt is new in U then cI(xt) ← 1

else if xt ∈ Y(U) then cI(xt) ← cI(xt) + 1 else z ← z +1 // discard xt

New symbols are added to U with c = 1; then, whenever a symbol already present in U is observed, its count is incremented. Recall that the SAD prediction depends on Nt(x), the number of occurrences of x in x1:t, as well as the subalphabet At (Section 2.1). Our process yields Yt := Y(Ut) as an approximation to At, as well as an approximate count function ˆNt : X → R, with ˆNt(x) = 0 for x /∈ Yt. The algorithm also tracks zt, the number of discarded symbols, and approximates the SAD prediction rule as

where ct,· denote the stored counts at time t, and ∑x∈X ρB (x‖ ·) = 1. Our Budget SAD is designed to overestimate the probability of frequent symbols (via the (t - zt) renormalization); the definition of ˜Nt(x) ensures that symbols in Yt are never deemed less likely than unseen symbols. The process is summarized in Algorithm 2.

The zt term keeps track of discarded counts; this is to correct for two types of counting errors. First, the counter ct,I(x) for a symbol x ∈ Yt only equals Nt(x) if 1) it was never discarded and 2) never removed from the reservoir; in general, ct,I(x) is an underestimate for Nt(x). We also need to compensate for our lack of knowledge of |At| in computing ˆ γt , the probability mass associated with unseen symbols. Effectively, zt mitigates both issues by rectifying the stored counts so as to approximate the SAD denominator. In particular, when ˜N(x) = ˆN(x) for all x ∈ Y, we have

One may also increment zt to keep tracks of counts that are discarded when a symbol leaves the reservoir; however, this does not affect our redundancy bound.

In addition to these counting errors, the Budget SAD suffers a redundancy cost from forgetting symbols. Clearly, this problem arises only when symbols are removed from the reservoir. As we now show, the Budget SAD achieves low redundancy with respect to the optimal memory-bounded model (Section 3) whenever the source's tail distribution is close to uniform.

4 Analysis

Let µ be a memoryless stationary source and let x1:n ∼ µ. We compare our Budget SAD estimator ρB to the optimal memory-bounded model ρ∗µ ∈ M described in Section 3. In our analysis we consider the associated optimal set Z ∗ of size K∗ , and derive a redundancy bound which depends on the probability mass µ(Z ∗ ) as well as the reservoir size K > K∗ . For clarity, we take the SAD probability distribution wt(·) to be uniform over the alphabet X, noting that our result extends to the more general case.

We take a conservative approach and bound the expected redundancy E [Fn(ρB , ρ∗µ )] according to the probability of a best-case scenario. In this best-case scenario, the symbols in Z ∗ are never ejected from the reservoir. We define a good event Gn(x) := {cn,In(x) = Nn(x)} which occurs when the stored count for x matches the total number of occurrences of x in x1:n; this implies that ct,It(x) = Nt(x) for all t ∈ [n]. The instantaneous redundancy of our algorithm at time t then depends on the probability of Gn(xt). Critically, we set K so that Gn(x) must occur with probability 1 - δ for all x ∈ Z ∗ . For B ⊆ X and a memoryless stationary source µ, define

We first provide a lemma stating the conditions under which Gn(B) := ⋂x∈B Gn(x) occurs with high probability.

Proof (sketch). The event Gn(x) occurs if x never leaves the K-concise summary after entering it. Because K-distinct reservoir sampling induces a permutation of x1:n, we can view the corresponding K-distinct sample as generated from independent draws without replacement from µ. Computing the probability that a symbol x ∈ B is not drawn in K tries and taking union bounds yields the result.

Our main theoretical result follows from this lemma:

Theorem 2. Let δ = o (log |X| +n logn) and K ≥ υ(Z ∗ , µ)-1 log(|Z ∗ |nδ-1 ). Let ZAUG ⊆ X of size K maximizing µ(·), and let κ := K(1 - µ(ZAUG))-1 . The expected redundancy of ρB with respect to ρ∗µ is bounded as

where the expectation is with respect to both x1:n ∼ µ and r1:n, the random integers chosen by Algorithm 1.

Proof (sketch). We consider a partition of the event space at each time step:

1. xt ∈ Z ∗ and Gn(Z ∗ ),
2. xt /∈ Z ∗ .
3. xt ∈ Z ∗ and ¬Gn(Z ∗ ), or

In the first case, the Budget SAD correctly estimates the probability of xt, and exhibits similar regret guarantees to the SAD. The second case contributes negligible expected redundancy, since Pr{¬Gn(Z ∗ )} is small. The final case gives rise to most of the expected redundancy, which we bound by providing bounds on zt (which lets us estimate the probability of symbols not in the K-concise summary), which itself depends on a bound on Dt,K+1, the expected gap between the first and K + 1th symbols in our summary. Let r1:n be the random draws of r within K-distinct reservoir sampling. We show that

which provides the last two terms of our bound.

Remark 1. The expected redundancy of ρB with respect to ρ∗µ is also bounded as

and in particular the bound of Theorem 2 is meaningful whenever κ log n = o(n).

The three terms in Theorem 2 correspond respectively to 1) the cost of learning µ over Z ∗ , 2) estimating the quantity 1µ(Z ∗ ), and 3) the redundancy for symbols which enter, but do not remain in our reservoir. In the presence of a favourable distribution (i.e., when (1 - µ(Z ∗ )/(1 - µ(ZAUG)) is small), our algorithm is asymptotically optimal, in the sense that its per-step redundancy goes to 0 as n → ∞. This is the case, for example, when the source is in the class M of memorybounded models (Equation 1) and |X | ≫ n.

As a final note, Lu and Lu [2011] recently provided a Ω(n) lower bound on the regret suffered by a bounded-memory, sequential prediction algorithm in the 0-1 loss setting. We point out that our analysis does not contradict their bound since, in the worst case, the second term may grow superlinearly (see Remark 1 and Section 6 below). In this case, one may (trivially) construct a Bayesian mixture between ρB and a uniform estimator to achieve O(n log |X |) regret.

5 Empirical Evaluation

The Budget SAD is especially motivated by the desire to minimize memory usage in the presence of infrequent symbols. Here we present two experiments showing the practical value of our approach.

5.1 Synthetic Image Domain

We first consider a synthetic image domain to demonstrate the effectiveness of our algorithm in the presence of symbol noise. In this domain, the source first selects one of m images uniformly at random, then corrupts this image with probability p and otherwise leaves it unchanged. Here we consider 50 × 60, 8-bit images and a uniform noise corruption model

(Figure 2; images from Wikipedia, 2015). Thus, while the source emits symbols from an alphabet X of size 25650×60 , only m of these symbols occur with non-negligible frequency.

We implemented the Budget SAD with a time-dependent reservoir size K to match the regret bound of Theorem 2: from a parameter R ∈ R+, we set Kt = ⌈R⌈log(t+1)⌉⌉. We trained both SAD and Budget SAD on one million symbols generated with m = 4 and p ∈ {0.1, 0.9}. We performed experiments with R ∈ [1.0, 2.0] (when p = 0.1) and R ∈ [0.5, 10.0] (when p = 0.9), with the results of each Budget SAD experiment averaged across 100 trials.

To study the behaviour of our algorithm, we map each value of R to its corresponding end-of-sequence reservoir size and report the algorithm's redundancy as a function of this value. Results for both values of p are shown in Figure 3. The Budget SAD achieves equal or lower redundancy using a small fraction of the SAD's memory budget (0.01% for both p = 0.1 and p = 0.9). Note that the Budget SAD even performs slightly better than the SAD in this instance, as it assigns a higher probability mass to unseen symbols. We conclude that the Budget SAD has the ability to significantly reduce memory usage.

5.2 Branch Pruning in Context TreeWeighting

Our analysis so far has focused on memoryless sources and their models. A common method of augmenting memoryless models is to embed them into a tree structure in order to guarantee low redundancy with respect to the class of k-Markov sources. One such method, Context Tree Weighting [Willems et al., 1995], uses the generalized distributive law [Aji and McEliece, 2000] to efficiently perform Bayesian model averaging over tree structures.

At the core of CTW is a growing |X|-ary context tree; each new symbol creates up to D new nodes, where D is a depth parameter. Each node corresponds to a context (a subsequence of x1:n) and maintains a statistical estimator (here, the SAD). Here we consider a modified CTW in which each node uses a K-distinct reservoir to store its children: removing an item from the reservoir prunes a whole subtree.

To understand the need for branch pruning, consider the Wikipedia Clean Text data set [Mahoney, 2011], which we use as our sequential prediction task here. This data set is composed of 713M lowercase characters (a-z and whitespace; |X| = 27). Within are 105M unique contexts of length at most D = 9. This number grows linearly over time, making a memory-bounded solution highly desirable. However, each context sees, on average, two or fewer symbols; as a result, using the Budget SAD at each node cannot significantly reduce memory usage. Branch pruning, on the other hand, is relatively effective.

For our experiment we used the more efficient CTW relative, Context Tree Switching [CTS; Veness et al., 2012] and derived our parameters from its authors' open-source implementation. As with the synthetic experiment, we considered values in the range R ∈ [1.0, 3.0]. For each node u, its reservoir size was increased as R log(tu + 1), with tu the number of visits to this node. We set the depth parameter to D = 9 as larger values of D did not affect redundancy, and averaged each experiment across 10 trials.

As illustrated in Figure 4, our algorithm, through the R parameter, can smoothly trade off memory usage and redundancy (with respect to an unpruned CTS). For example, for a small redundancy (≤ 5%) we observed a 44.6% average reduction in memory usage (R ≈ 1.76, not illustrated). Furthermore, there was minimal variance between trials. While memory usage still remains linear in n, we believe this result is particularly significant given the Zipfian behaviour of natural language data, which in our analysis corresponds to a large κ term.

6 Discussion

In our setting, the optimal model ρ∗µ assigns a uniform probability over the set X \ Z ∗ . Interestingly enough, the main source of redundancy in the Budget SAD is the κ log2 n cost for approximating this uniform probability. In particular for some distributions (e.g. µ(·) ∝ 2-i for i ∈ N) our analysis suggests an unpleasant O(n logn) redundancy - possibly worse-than-random performance. This cost stems from our overestimation of symbols in Z ∗ ; it seems probable that an alternative approach, which instead overestimates 1-µ(Z ∗ ), exists.

On the other hand, with well-behaved data the Budget SAD provides significant memory savings. This is the case, for example, when the tail of µ is approximately uniform. Most count-based frequency estimators [Friedman and Singer, 1999; Teh, 2006; Veness and Hutter, 2012; Hutter, 2013] model this behaviour by setting aside a lump probability mass ε for all unobserved symbols; our zt term serves a similar purpose.

Surprisingly, K-distinct reservoir sampling is unnecessary if the source µ is truly memoryless and stationary. In fact, in this case the first K distinct symbols in x1:n are just as good an approximation to Z ∗ ! The benefit of our approach is to (partially) inoculate the budget estimator against adversarial empirical sources; a similar role is played by the Dirichletmultinomial prior in estimating counts.

Orlitsky et al. [2003] proposed two methods for achieving o(n) per-symbol redundancy on open alphabets, where new symbols appear at a O(n) rate. As an alternative to the zt term, in this setting it may be sufficient to accurately estimate |At|, the size of the alphabet at time t; work on distinct value queries suggests this is possible [Gibbons, 2001]. However, Orlitsky et al.'s method requires that we instead estimate the prevalence, or frequency distribution, of symbols. Whether this can be done with bounded memory is not known to us.

7 Conclusion

In this paper we presented a novel algorithm, K-distinct reservoir sampling, which incrementally maintains a sample of frequently occurring symbols within a data stream. We described how to combine K-distinct reservoir sampling with a simple count-based estimator and derived a corresponding redundancy bound. As our empirical results show, our algorithm can significantly reduce the memory requirements of both memoryless and tree-based estimators when dealing with long data sequences.

8 Acknowledgements

The author wish to thank Joel Veness for uncountably many discussions on the topic of count-based estimation, Laurent Orseau for providing thorough editorial comments, Alvin Chua and Michael Bowling for helpful discussion, and finally the anonymous reviewers for their superb feedback.