<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
<meta content="text/html; charset=ISO-8859-1"
http-equiv="Content-Type">
</head>
<body text="#000000" bgcolor="#ffffff">
On 10/5/2011 10:54 AM, Rakesh Gopchandani wrote:
<blockquote
cite="mid:CACNk0dYYspAvzmDLVfgGJQ99ysjMC36HW2CT_-Z1kXbLXi8BcA@mail.gmail.com"
type="cite">
<div class="gmail_quote">Hi,<br>
<br>
<div class="gmail_quote">
<div class="im">
<blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt
0.8ex; border-left: 1px solid rgb(204, 204, 204);
padding-left: 1ex;">
<div><br>
</div>
This is well outside of my expertise, but your change is
in opposition to how ENT[1] does it.<br>
<br>
- ent += prob[i] * rt_log2(1 /
prob[i]);<br>
+ ent += prob[i] * rt_log2(prob[i]);<br>
<br>
I just went back and verified and it looks like the
original line is how it's done.<br>
<div><br>
</div>
</blockquote>
</div>
<div><br>
I checked it out. I think rt_log(prob[i]) is the correct way
to do this. It is the sum over entire alphabat, probability
multiplied by log of probablity: <a moz-do-not-send="true"
href="http://en.wikipedia.org/wiki/Entropy_%28information_theory%29#Definition"
target="_blank">http://en.wikipedia.org/wiki/Entropy_%28information_theory%29#Definition</a><br>
<br>
</div>
</div>
</div>
</blockquote>
<br>
Unfortunately, e-mail is not the best medium for arguing stuff like
this. Forgive the terrible formatting.<br>
<br>
Let SUM(i, f(i)) be the sum of f(i) for all values of i that exist
in some data set (in our case, the array prob).<br>
<br>
Base Definition: H(X) = -1 * SUM(i, prob[i] * rt_log2(prob[i]))<br>
<br>
What we want to prove:<br>
<br>
(1) H(X) = -1 * SUM(i, prob[i] * rt_log2(prob[i])) <br>
<br>
is equivalent to <br>
<br>
(2) H(X) = SUM(i, prob[i] * rt_log2(1 / prob[i]))<br>
<br>
Assuming I remember how to do math, I believe we can get from (2) to
(1) with a little bit of algebraic manipulation (as follows):<br>
<br>
SUM(i, prob[i] * rt_log2(1 / prob[i])) // we're starting at (2)<br>
<br>
SUM(i, prob[i] * (rt_log2(1) - rt_log2(prob[i])) ) // rule of
logarithms: log(1 / x) = log(1) - log(x)<br>
<br>
SUM(i, prob[i] * -rt_log2(prob[i]) ) // log(1) = 0<br>
<br>
SUM(i, -1 * prob[i] * rt_log2(prob[i]) ) //
pull the -1 to the front to make the next step more obvious<br>
<br>
-1 * SUM(i, prob[i] * rt_log2(prob[i]) ) // Pull
the constant -1 out of the SUM<br>
<br>
... and we should be good.<br>
<br>
--Gilbert<br>
<br>
</body>
</html>