1

I recently came across the following summation in the definition of the Gini impurity in a machine learning lecture on decision trees:

$$\sum_{i \ne j}{P(\omega_i)P(\omega_j)} \space\space\space i,j \in c$$

Based on the formulas used in the lecture, the above summation involves only combinations. In other words, if $(i,j)=(1,2)$ is included then $(2,1)$ is not. This is intuitively how I would interpret the notation, and how my professor did as well.

However, based on the formulas in Wikipedia, the above summation should be over all permutations. Indeed, if I were to write it more explicitly as shown below, then this way makes sense too:

$$\sum_i\sum_j{P(\omega_i)P(\omega_j)} \space\mid\space i \ne j$$

So is either of these correct or accepted? And regardless, how would one explicitly write the double summation over all combinations as I did for permutations?

Community
  • 1
TheSchwa
  • 135
  • Just a hint $\sum_{i} \sum_{j} P(\omega_{i})P(\omega_{j})=\sum_{i} P(\omega_{i}) ( \sum_{j} P(\omega_{j}))$ you can do the same with the first sum. – rtybase Nov 10 '15 at 22:48

1 Answers1

0

I have seen, and used, the notation $$\sum_{i \ne j}{P(\omega_i)P(\omega_j)}$$ many times before, and it never once occurred to me that somehow if $i = 2$ and $j = 1$ is included, then you should exclude $i = 1$ and $j = 2$. If you want to do that, then you should use a notation that explicitly says so, such as $$\sum_{i > j}{P(\omega_i)P(\omega_j)}.$$

Just because this particular sum treats $i$ and $j$ symmetrically does not mean all such sums do. If you are summing some $F(i, j)$ where in general $F(i, j) \ne F(j, i)$, then how would you decide which of $(1,2)$ and $(2,1)$ to include in the sum?.

It is possible that the lecture made some use of the fact that $$\sum_{i \ne j}{P(\omega_i)P(\omega_j)} = 2\sum_{i > j}{P(\omega_i)P(\omega_j)},$$ instead of interpreting it in in what I have to call an inappropriate fashion.

Paul Sinclair
  • 43,643