5
$\begingroup$

From wikipedia: https://en.wikipedia.org/wiki/Decision_tree_learning

enter image description here

I am unable to get my head around two of the steps:

  1. The first equation: $f_i(1 - f_i)$. This does not immediately become apparent as the "probability of being chosen times the probability of miscategorization". Instead it looks to me like "probability of being chosen times the probability of others being chosen" (but not necessarily incorrectly)

  2. The arithmetic of the last simplification eludes me: how to get from $1 - \sum(f_i^2)$ to $\sum(f_if_k)$

Tips appreciated.

$\endgroup$
5
$\begingroup$

I don't know about the algebra, but you can prove the identity with a probabilistic argument. If I roll two dice with $m$ sides and the probability of side $i$ is $f_i$, then the probability of a double is $\sum f_i^2$. Thus $1-\sum f_i^2$ is the probability that I roll distinct values. But arguing differently, the probability, say, that I get $i$ followed by $j$ is $f_if_j$. Summing over all possibilities, with $i \neq j$, I get the probability of rolling distinct outcomes: $\sum f_if_j$, and the identity is proven.

As for the first point, If you role the $m$ sided die, there is a probability $f_i$ that side $i$ comes up. Suppose I have to guess the value, and I do this by rolling a die of my own with the same weights. The probability that I guess wrong, conditional on value $i$ being true, is $1-f_i$. The probability that I get it wrong, summing over the possible values, is $\sum f_i(1-f_i)$.

$\endgroup$
  • $\begingroup$ nice explanations. I feel closer to an understanding. $\endgroup$ – javadba Oct 1 '15 at 22:05
5
$\begingroup$

I think it's best to answer your question in reverse order as we'll back into your first question by answering your second.

Question 2

Imagine you have a probability distribution function ($f_i$) that distributes its probabilities as such:

enter image description here

I can then square the probabilities ($f_i^2$) and get:

enter image description here

Another way of looking at it is putting each probability distribution along the axis of a grid. Each cell now represents the product of the function along the respective axes.

enter image description here

The grid itself sums to 1, just like you'd see in a two dice roll probability table. It should be clear that 1 minus the sum of the diagonal probabilities is the same as the non-highlighted squares below.

enter image description here

If we call one of the axis k to differentiate it, but still have it render the same function, we can then make the statement.

enter image description here

$1-\sum f_i^2$ = $\sum_{i \neq k} f_if_k$

Question 1

We can now use some of the intuition from answering question 2 to drive the intuition for question 1.

Let's take our same table from question 2, but change what the two axes mean. Across one axis we'll have labels for objects, while on the other we'll have the actual object.

For a concrete example, let's assume we have a bowl of fruit: apples, oranges and pears. In another bowl we'll have labels corresponding to apples, oranges and pears in the same proportion as the actual objects.

enter image description here

If we then look at the probability of choosing each at random we get the following distribution.

enter image description here

Now we want to look at the joint distribution. The Geni impurity tells us the probability that we select an object at random and a label at random and it is an incorrect match. The Geni impurity is the sum of the probabilities in the black shaded areas. These are where the label does not match the object, thus the impurity.

enter image description here

This should look very familiar to the answer to question 2. If the explanation for question 2 convinced you that $1-\sum f_i^2$, you should be able to work backwards through the algebra you provided to see that also equals $\sum f_i(1-f_i)$

$\endgroup$
1
$\begingroup$

1) Remember that the classification is done randomly proportional to the frequency of the value. $i$ is then miscategorized with probability $(1-f_i)$.

2) The $f_i$ sum to 1. So if I sum all $f_if_j$ this equals 1*1. So if I sum just the ones where $i\neq j$ this equals $1- \sum f_if_i$.

Sorry for the brevity, answering from my phone. Comment with questions.

$\endgroup$
  • $\begingroup$ Reasonable explanation. The other one with a bit more verbosity served me a bit better (given I needed bit more handholding). I upvoted here in any case. $\endgroup$ – javadba Oct 1 '15 at 22:06

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.