4

Heaps' Law basically is an empirical function that says the number of distinct words you'll find in a document grows as a function to the length of the document. The equation given in the Wikipedia link is

enter image description here

where $V_R$ is the number of distinct words in a document of size $n$, and $K$ and $\beta$ are free parameters that are chosen empirically (usually $0 \le K \le 100$ and $0.4 \le \beta \le 0.6$).

I'm currently following a course on Youtube called Deep Learning for NLP by Oxford University and DeepMind. There is a slide in a lecture that demonstrates Heaps' Law in a rather different way:

enter image description here

The equation given with the logarithms apparently is also Heaps' Law. The fastest growing curve is a corpus for Twitter data and the slowest is for the Wall Street Journal. Tweets usually have less structure and more spelling errors, etc. compared to the WSJ which would explain the faster-growing curve.

The main question that I had is how Heaps' Law seems to have taken on the form that the author has given? It's a bit of a reach but the author didn't specify what any of these parameters are and I was wondering if anybody might be familiar with Heaps' Law to give me some advise on how to solve my question.

5

A straightforward rewriting of the Wikipedia formula gives

log V_R(n) = log K*n^beta
           = log K + log n^beta
           = log K + beta*log n

This allows us to identify K=C and beta=-alpha (probably the WSJ uses a different formulation of Heaps' law

V_R (n) = \frac{K}{n^\alpha}

). The remaining b is a strange additional parameter not present in the original formulation of the law (and irrelevant, too, because the law is about large numbers where n-b is approximately equal to n).

| improve this answer | |
  • Thanks for the answer. I tried to apply logarithms to each side but it didn't come to mind that K = C and β = -α. This may also sound like a bit of an out-of-placed question, but would you happen to know what a "singleton" in this context is? My knowledge of set theory tells me that it means a single perceptual unit, or a word in this context. – Seankala Apr 9 '19 at 15:34
  • From the small context given, I can only guess what a singleton could be here. My guess is that it refers to a hapax legomenon, i.e., a word form that occurs exactly once in the corpus (or sample). – jk - Reinstate Monica Apr 9 '19 at 16:07
  • alpha in the chart is notably not in the same range as implied for beta in the question. I'm not sure whether that makes a huge difference. I guess it does. – vectory Apr 9 '19 at 17:59
  • singleton 34.3%, 70% must mean hapax legomenon percentage of new words. However, that still seems quite high. Edit: that wouldn't even make sense, if every word is new at some point, unless they don't count a seizable number of basic vocabulary as new, like, compact OED sized. – vectory Apr 9 '19 at 18:02
-2

The question is interesting from a (my) novice math perspective.

From a basic linguistic perspective, there is little to no difference between either form. All you need is a slowly decreasing count. Both forms describe standard distributions, a concept that's naturally observed in nature. The specific formula of any such distribution depends on an accurate model. It doesn't hold much explanatory power, if the model isn't empiricly grounded, but it's a heuristic--we might speak of so called fudge factors. For the specifics you should check out datascience.se, or whatever it's called where statistics are treated (compression of text is also rather important in signal processing).

The first formular is akin to the area of a circle

V = k * n ^ beta

A = pi * r ^ 2

but inverted, i.e. taking the square root (beta=1/2) instead of the square; also, it has a random factor k instead of pi (=3.14...). This can be pictured various ways, for example as light cone projected onto a surface, or a stream of words onto a lexicon: Where the radious of a light cone increases linearly with distance, it's area increases squarely; if this area illuminated a text, the number of new words would increase linearly with distance from the lamp.

This only explains the inversion of the exponantial function, but the fudge factor is another matter, depending on the model. While the factor pi relates the circumference of a circle to its radius, a different factor implies first of all a different shape, either of the light cone, or alternatively of the surface (left as exercise to the reader to the reader), but it still grows linearly with distance. So it doesn't even make a difference in my simplistical model.

In other words, if counting text length in number of words n, so the text grows linearly with each word, it should grow squarely if counting each newly introduced word.

V ~ n ^ beta

Or vice-versa as the formular has it: The number of new words grows proportional to the square root of the number of total words.

The second formular is essentially the same. I too have no idea what the extra variables are. Removing the logarithm and transposing, we see

  1. f(w) = C * (r(w)-b)^(-alpha).

  2. 1/C * (r(w)-b)^a = 1 / f(w).

This is in principle the same polynomial form as V=K*n^b in either case, with several new parameters. It's not apparent why to choose the transposed form, which works as well, iff it were that V = 1 / f(w), k = 1/C, n = (r(w) - b), beta = alpha.

There are a few notable differences. What's with those parameters? I'd assume the following:

  • b is likely a threshold under which the distribution is useless, because if r(w)<b, then the logarithm of the difference (r(w) - b) is undefined. Perhaps that's the Basic vocabulary.

that's the major difference in any case.

Another difference would be to focus on the transposed form.

  • If C is a constant as usual notation practice has it, then writing log(C) would be constant as well. This might just be a courtesy to ease solving for (w). It's inversely proportional to k, but that shouldn't trouble us now. I'm keen to assume that it means Corpus, but that gives me troubles. [todo]

  • That leaves alpha to be explained, which seems to be a variable nudge factor determined per corpus by a specific statistical procedure for error correction.

The last one is crucial. Raising to a negative power of alpha (=reciproke of the power of alpha) is not quite the same as taking the square root (power of 0.5). But it is similar in effect because the ranges of the exponents are also different than in the first formular; here we have b < 1 < alpha. The very important difference is that the number of new words will tend to zero as the number of typed words tends to infinity. In contrast, the old formula would require ever new words to grow the text.

Somehow I'm trying to see 1/f as a derivative, compared to mechanical accelleration. But I'll rather leave the rest of the exercise to the reader. Please add a link to the video to your question. thx bye

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.