A Smoothing Formula Based on the Forgetting Hypothesis

基于遗忘假设的平滑公式 苏剑林 · 2017-01-07 · Mathematics statistics corpus smoothing

Statistics is the process of estimating a true distribution from a large number of samples, and a word that often accompanies statistics is "smoothing" — the process of discounting statistical results. The idea behind smoothing comes from the following observation: if the sample space is very large, the statistics will be sparse, and various chance factors make the small counts unreliable. For example, an item with a count of 1 might just be a fluke, and its frequency need not be close to $1/N$; likewise, an item with a count of 0 does not necessarily mean it will never occur. This is why we need to smooth the statistical results, to make our conclusions more reliable.

There are many smoothing methods. Here we introduce a smoothing formula based on a "forgetting hypothesis." Consider the following task: from a corpus, we want to estimate the frequency of each character. We model this on how the human brain forgets: assume that whenever a character occurs, our memory of it increases by 1, but if, over one period (never mind for now how large this period is), the character does not appear at all, then the memory decays to a fraction $\beta$ of its previous value. Assuming the character appears periodically, the memory amount $A_n$ then satisfies the following recurrence

$$A_{n+1} = \beta A_n + 1$$more

The general solution of this recurrence is

$$A_n = \frac{1-\beta^n}{1-\beta}$$

and its limit is

$$A = \frac{1}{1-\beta}$$

We take this limit to be the true statistical result we are after — that is, the smoothed result.

Suppose a corpus contains a total of $N$ characters, and a particular character occurs with count $F$. Assuming the character is uniformly distributed, its period of occurrence is then $N/F$. We may further assume that the law of forgetting decays exponentially (this is suggested by the Ebbinghaus forgetting curve; see: https://en.wikipedia.org/wiki/Forgetting_curve, though readers are welcome to guess at other forms of the forgetting law). Then there exists a constant $\alpha$ less than 1 such that

$$\beta = \alpha^{N/F}$$

This gives us the following data smoothing formula:

$$\hat{F} = \frac{1}{1-\alpha^{N/F}}$$

Let us examine this formula more closely. It's not hard to see that $\alpha$ should be very close to 1 — otherwise everything would be forgotten all at once. Second, we would expect that when $F$ is sufficiently large, the smoothed result $\hat{F}$ should be close to $F$, since the more data we have, the more trustworthy the statistics become. So we assume that as $F=N$, $\hat{F}=F$, in which case we should multiply by a factor

$$\hat{F} = \frac{N(1-\alpha)}{1-\alpha^{N/F}}$$

This, then, is the final smoothing formula.

If we adopt the result given by Han Shu, then we might consider using

$$\alpha = 0.99999962...$$

However, notice that when $F\to 0$, we have

$$\hat{F} = \lim_{F\to 0}\frac{N(1-\alpha)}{1-\alpha^{N/F}}=N(1-\alpha)$$

This means that this smoothing formula also assigns a frequency greater than 0, namely $N(1-\alpha)$, to characters with a count of 0. Clearly, fixing $\alpha$ in this way isn't quite appropriate here. Why not instead fix $N(1-\alpha)$? That is, assign every character that has never occurred a frequency of $\gamma$. Solving for this gives

$$\alpha = 1 - \frac{\gamma}{N}$$

and thus

$$\hat{F} = \frac{\gamma}{1-(1 - \gamma/N)^{N/F}}$$

At this point, starting from the forgetting hypothesis, we have arrived at a final smoothing formula containing only a single parameter with a clear meaning. Finally, note that when $N$ is sufficiently large, we have

$$(1 - \gamma/N)^N \approx e^{-\gamma}$$

and thus

$$\hat{F} \approx \frac{\gamma}{1-e^{-\gamma/F}}$$

This too is a usable smoothing formula. Let's finish by looking at its Taylor expansion:

$$\hat{F} \approx \frac{\gamma}{1-e^{-\gamma/F}} = F + \frac{\gamma}{2} + \frac{\gamma^2}{12F^2}+\dots$$

If we truncate after the first two terms, we see that this approach is, in effect, similar to add-one smoothing. So perhaps we could say that the forgetting hypothesis provides a more solid theoretical justification for add-one smoothing.