StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>If you are only using entropy to determine which alternative is better, so that you only need the result of comparing two entropies and do not need their actual values, then you can eliminate some calculations.</p> <p>You have this function: Entropy(N1, N2, N) -> - N1/N*log2(N1/N) - N2/N*log2(N2/N).</p> <p>Supposing that N is a constant for the duration of your problem, let’s multiply the expression by N:</p> <blockquote> <ul> <li>N1*log2(N1/N)-N2*log2(N2/N)</li> </ul> </blockquote> <p>Next, separate the “/N” out of the logarithms:</p> <blockquote> <ul> <li>N1*(log2(N1)-log2(N)) - N2*(log2(N2)-log2(N))</li> </ul> </blockquote> <p>and expand:</p> <blockquote> <ul> <li>N1*log2(N1) - N2*log2(N2) - (N1+N2)*log2(N)</li> </ul> </blockquote> <p>and simplify:</p> <blockquote> <ul> <li>N1*log2(N1) - N2*log2(N2) - N*log2(N)</li> </ul> </blockquote> <p>Clearly N*log2(N) is a constant and does not affect whether one entropy is greater than another so we can discard it.</p> <p>Also, multiply by ln(2), which also does not change whether one entropy is greater than another. This has the effect of changing the log2 functions to ln functions, and ln may be calculated slightly more accurately by the math library (there is a reason it is the “natural” logarithm):</p> <blockquote> <p>E(N1, N2, N) -> - N1*ln(N1) - N2*ln(N2)</p> </blockquote> <p>This function has fewer operations, so it may be computed more accurately than the Entropy function, and it has the property that (when calculated exactly) E(N1, N2, N) < E(M1, M2, N) iff Entropy(N1, N2, N) < Entropy(M1, M2, N).</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload