3
$\begingroup$

I'm trying to use feature hashing (or hashing trick) on a set of files that are composed mostly in English and code (in English).

I'm trying to see if Zipf's law applies to the set of files before I try to use feature hashing.

Looking at 3 different websites:

  1. https://en.wikipedia.org/wiki/Zipf's_law
  2. How to calculate Zipf's law coefficient from a set of top frequencies?
  3. How to verify if data follows Zipf's law without looking at the graph

It seems that I would need to:

  1. Plot a rank vs Occurrences graph
  2. Apply log_10 to rank and occurences, and see if there is some sort of linear line
  3. Use Linear Regression to construct a line, and look at the residuals.
  4. Use Chi-Squared Test to see how the fit is doing.

So here I go:

  1. Plot a rank vs Occurrences graph

enter image description here

Okay, so it looks a bit like power distribution.

  1. Apply log_10 to rank and occurences, and see if there is some sort of linear line

enter image description here

Hmm... It doesn't really fit the graph found on wikipedia, but the middle part looks okay.

  1. Use Linear Regression to construct a line

enter image description here

  1. Chi Squared Value:

Using scipy, I was able to get some sort of numbers:

statistic=-5231551.8602747163, pvalue=1.0

I see that from graph 1, 2, and 3, it looks like Zipf's law might not hold. And looking at 4, I'm not too sure what it means.

Then I'm stuck, because I get all these graphs and numbers, but I'm not sure how to programmatically determine if I can use feature hashing?

If we compare it to something like skewness, we can compute some sort of number for skewness, if > 0, then it means it's skewed to the left, and vice versa.

| cite | improve this question | | | | |
$\endgroup$
4
$\begingroup$

This answer from one of your linked questions is on the technical side, but it does seem like it has everything you need.

Specifically, it links to this blog post by Cosma Shalizi that makes several clear points on the topic. I'll condense and paraphrase those points here:

  1. Lots of distributions give you straight-ish lines on a log-log plot. This means that even if you can look at the plot every time, you can't determine that Zipf's law applies. You can only determine that it doesn't apply.
  2. Don't fit a linear regression to your log-log plot. It's a hack at best.
  3. Use maximum likelihood to fit a power law model, and use a goodness-of-fit test to check its goodness of fit. Use the Kolmogorov-Smirnov test to compare your data to the theoretical Zipf's law distribution. Use bootstrapping (instead of the standard KS test p-value tables) to determine statistical significance; there's an example R implementation of this procedure in Help with understanding the ks.boot test results.
  4. Use Vuong's test to check against other alternatives. Try to rule out other long-tailed distributions, like the log-normal and Weibull. If you can't rule these out, you can't conclude that you have a power-law distribution.

Points 1 and 2 are just advice. Points 3 and 4 represent an automate-able procedure:

  1. Estimate the parameters of a power law distribution using your data
  2. Use the KS test to test the goodness of fit of the estimated distribution
  3. Use the Vuong test to rule out a "short list" of reasonable alternatives

If the tests in step 2 and 3 pass, you have a Zipf distribution.

That said, Shalizi makes another point in his post that I omitted above:

Ask yourself whether you really care.

I'm not sure if you should or shouldn't. Ben Gimpert suggests that you should.

I don't have an opinion on this because I haven't personally worked through the math underlying the text hashing trick. Is an actual power law distribution really necessary? If so, is Zipf's law specifically necessary? I don't know the answer, so hopefully another user can clarify this point.

Finally, I imagine that the presence of code blocks in your text could be distorting the expected power-law relationship. Consider whether you need to do additional text processing before doing whatever else it is you intend to do with your data.

| cite | improve this answer | | | | |
$\endgroup$
  • $\begingroup$ Thanks for your extremely detailed post. I thought power law distribution = long tail? $\endgroup$ – user1157751 Feb 28 '17 at 5:30
  • $\begingroup$ Maybe I don't need exactly to be Zipf's law to hold, but when you try to use text hashing trick, you would sometimes get collision. If Zipf's law holds, then when two words get a collision, then they are probably rare words. If they are rare words, they contribute little to variance. If the text and code portions have even distribution of words, then it's not a good idea to use hashing trick. $\endgroup$ – user1157751 Feb 28 '17 at 5:33
  • $\begingroup$ I'll try to work out the math, but using method 3, what tends to be a good, average, or bad goodness of fit value is my main question. But I'll post another question about that when I'm stuck. Thanks for your help!! $\endgroup$ – user1157751 Feb 28 '17 at 5:35
  • $\begingroup$ @user1157751 it's a hypothesis test like any other. You set the cutoff based on your tolerance for falsely rejecting the null hypothesis, weighed against your tolerance for missing true opportunities to reject the null hypothesis. $\endgroup$ – shadowtalker Feb 28 '17 at 15:09
  • $\begingroup$ @user1157751 you're right about the definition of a "long tail." But Zipf's distribution is only one of several power law distributions. $\endgroup$ – shadowtalker Apr 25 '17 at 14:57

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.