6
$\begingroup$

While discussing about decision trees in class, my teacher touched upon the topic of entropy. I have understood the purpose of entropy (have not understood how the formula $H(X)= -\sum_{i}{p(x_i) \log p(x_i)}$ comes from).

But anyways I was wondering if there is a simpler way to say that having (3 blue m&ms, 3 red m&ms, 3 orange m&ms, 3 yellow m&ms) is higher entropy than having (1 blue m&m, 2 red m&ms, 3 orange m&ms, 6 yellow m&ms).

Why can't we just compute the standard deviation? Higher the standard deviation, lesser the entropy.

If I were to do it here,

  • CASE1 : 1 blue m&m, 2 red m&ms, 3 orange m&ms, 6 yellow m&ms

    • $\bar{x} = (1+2+3+6)/4 = 3$
    • $s_x = (1-3)^2 + (2-3)^2 + (3-3)^2 + (3-6)^2 = 14$
  • CASE2 : 3 blue m&ms, 3 red m&ms, 3 orange m&ms, 3 yellow m&ms

    • $\bar{x} = (3+3+3+3)/4 == 3$
    • $s_x = (3-3)^2 + (3-3)^2 + (3-3)^2 + (3-3)^2 = 0$

Once again, lesser the SD, more the entropy, which holds true here.

$\endgroup$
  • 1
    $\begingroup$ Of course you can compute the SD--you did in your question. What we are missing is a purpose: what are you hoping to do with your calculation of entropy or SD? $\endgroup$ – whuber Jan 13 '15 at 23:23
  • $\begingroup$ I'm using entropy to help me decide on which attribute I should split when designing a decision tree. The lecture notes tell me that as we go down to lower levels of the tree, we want entropy to reduce at that level(which we calculate using Information gain, higher information gain means we would like to split on that attribute) I was thinking that instead of using entropy, we could use SD to tell how the split on that attribute is performing $\endgroup$ – IAMTubby Jan 14 '15 at 0:03
  • $\begingroup$ Just for the sake of more comprehensiveness, feel free to check my DS answer on a related topic, with references to other (non necessarily simpler) entropy measures. $\endgroup$ – Aleksandr Blekh Jan 14 '15 at 4:42
  • $\begingroup$ @AleksandrBlekh, I went through the link and saw some other entropy measures. But still curious to know whether SD gives an indication of whether the attribute in question is a good split or no. I feel that higher the SD, better the split. $\endgroup$ – IAMTubby Jan 14 '15 at 6:52
4
$\begingroup$

Why can't we just compute the standard deviation?

Here's why. Let's compare the formulas for entropy and variance:

  • $H(X) = - \sum\limits_x p(x) \, \log p(x) = - \mathbb E \, [ \log p(X) ]$
  • $\text{var} (X) = \mathbb E \, \Big[(X - \mathbb E[X])^2 \Big]$

So note that entropy does not care about values that $X$ may take, it cares only about the distribution itself, while variance does care about the values of $X$. Also, for variance the variable has to be numeric, and it's not the case for entropy. Both these properties make entropy a good candidate for calculating the information gain.

To get more insights into entropy and other information-theoretic measures, you may read this question on math.SE.

| cite | improve this answer | |
$\endgroup$
  • 3
    $\begingroup$ It might be worth pointing out that the entropy is the log-variance (plus a constant) in the special case of the normal distribution. $\endgroup$ – Neil G Jan 14 '15 at 20:09
3
$\begingroup$

When comparing standard deviation and entropy in context of statistics and related areas, I think that it is important to realize the difference between two notions of the entropy concept: entropy as a measure of variability, volatility, chaos (this meaning is usually implied in physics and similar domains) and entropy as a measure of an average information in a message (this meaning is usually implied in domains, based on Shannon's theory of information). However, despite obvious surface differences between the notions, the above-mentioned two dimensions reflect the close parallels between physics-based entropy and information theory-based entropy concepts. A discussion on this topic is beyond the scope of my answer, but this article is IMHO a good start.

The entropy formula, which you were confused about, comes from the theory of information (see this section) and is the basis for the use of entropy via the concept of information gain (notice the similarity in the formulas). If I understand correctly, all those types of entropy are particular (contextual) cases of a mathematics-based generalized concept of entropy in dynamic systems.

In terms of your particular question on potential use of standard deviation (SD) as a substitute measure for decision trees, I have to say the following:

  • yes, it is possible to use SD as a substitute for entropy (information gain, to be more accurate);
  • it seems that your statement about wanting higher SD as a criteria for attribute splitting is wrong - you need higher information gain, which can be substituted by standard deviation reduction, not SD itself. This nice page explains the idea and algorithm behind it rather well.

Finally, I would like to share two resources for reducing confusion and providing more details on the topic. First, this discussion is useful to see why your statements "higher the standard deviation, lesser the entropy" and "lesser the SD, more the entropy" [original style preserved] are incorrect. Second, this paper, despite its financial focus, presents potential reasons for preferring using entropy to standard deviation. Let me summarize them in the following list:

  • entropy is a more general measure and supports a wider range of data types;
  • entropy incorporates more information than SD (thus, making models more realistic);
  • entropy is distribution-free, that is not dependent on a particular distribution (less errors);
  • entropy satisfies the first order condition (used in optimization and econometric models);
  • entropy also serves as a measure of dispersion (hence, playing an SD's role).

Reasons for not preferring using entropy to SD also should be noted and include the former's complexity and potential statistical bias, related to considered degrees of freedom of a model.

| cite | improve this answer | |
$\endgroup$

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.