Implement Entropy UDF

[king821221]

Implement Entropy UDF

[matthayes]

Good suggestion, this seems like it could be useful.

[king821221]

Thanks Matthayes.

I am working on this feature and will submit a patch soon.

Could you please help me do the code review?

I am following the guideline of git: https://help.github.com/articles/fork-a-repo, https://help.github.com/articles/using-pull-requests

Anything I need to follow, please inform me.

[matthayes]

Great, and sure I can help with the code review. Will yours support conditional entropy too so mutual information can be computed?

Regarding guidelines to follow, first of all you'll need to fork the code as discussed in that article. For the code itself, a few points to start:

• Make sure the UDF is well documented. Please include example usage in the javadoc.
• Be sure to write unit tests for the UDF. Follow the pattern used for the other UDFs. You can run the tests in eclipse or at the command line. The README has info on running individual tests.
• datafu.pig.stats is probably the right home for this.

Once you're happy with your implementation you can send a pull request and we'll take a look at it.

[king821221]

Sure, I will follow the guideline.

Yes, conditional entropy is something to be supported. Its definition is at http://en.wikipedia.org/wiki/Conditional_entropy. I am just wondering if we need a separate UDF to support it, cos

H(Y|X) = H(X, Y) - H(X), according to the chain rule.

H(X, Y) may could be handled by the above UDF, and the input to the UDF may need to be a bag, each tuple in the bag is a pair <x, y>.

so we shall calculate H(X, Y) = - sum(p(xi, yj) * log(p(xi, yj))), is this correct?

[matthayes]

Yes it seems like conditional entropy could be computed using the same UDF, where the UDF would be used to compute H(X,Y) and H(X). If we wanted mutual information we could compute H(X) + H(Y) - H(X,Y).

It's not clear that AccumulatorEvalFunc works for this case though. To estimate the probability you need to know the total number of events right? Usually we use the accumulator interface where the total count is not needed, as this allows the tuples from the bag to be streamed in.

[matthayes]

By the way, it looks like all the Entropy code that was added in MAHOUT-747 was later removed in MAHOUT-1296.

[king821221]

Yes, my original thought is that entropy is very similar to datafu.pig.sessions.Sessionize as it reads a stream of data, accumulate and output the final result. But when we count p(x), the total number of events are unknown. To work around this problem, I apply the following formula:

Our target T = SUM(p(x) * log(p(x)))
= SUM(c(x) / N * log(c(x) / N)) // p(x) = c(x) / N, c(x) is the number of events of x, N is the total number of events, which I think could be SUM(c(x))

                 = 1 / N * SUM( c(x) * [ log(c(x)) - log(N) ] ) // log(a/b) = log(a) - log(b)
                 = 1 / N * SUM(  c(x) * log(c(x)) - c(x) * log(N) )
                 = 1 / N * SUM( c(x) * log(c(x)) ) - 1 / N  * log(N) * SUM(c(x))
                 = 1 / N * SUM(c(x) * log(c(x)) ) - log(N)

What we need is M = SUM(c(x) * log(c(x)) ) and N = SUM(c(x)) and T = M / N - log(N) and M and N could be accumulated, I think.

Please correct me if my chain of thought is incorrect.

By the way, the entropy code removal is bad news for the original guy, I do not want this to happen

R also has entropy implementation: http://cran.r-project.org/web/packages/entropy/

[matthayes]

Yes I think you're right. I tried working out the math myself too and got the same solution as you (with a sign flip):

 H(X) = log(N) - 1 / N * SUM(c(x) * log(c(x)) )

So I think AccumulatorEvalFunc does in fact work for computing entropy. If the values are sorted then as you accumulate you can count the number of instances and pass them into a function computing c(x) * log(c(x)), accumulating the total as you go. Then once you are finished you can compute the final result given that you now know N.

[king821221]

Pull request in #78

[king821221]

Close this and track all follow up actions on pull request #78