Let me introduce my problem with a simple example.

Let's say that we have two different classes $C_0$ and $C_1$ and we have one node $S$ that has the following elements of each class:

$S = \{1000,400\}$

We want to split this node into 4 different child nodes. We pick a random threshold $\theta$ in a decision tree fashion and we obtain the following split:

$S_1 = \{600,200\}$ $S_2 = \{50,0\}$ $S_3 = \{75,10\}$ $S_4 = \{275,190\}$

And we can assign a probability function to each node:

$p_1 = (0.66,0.33)$ $p_2 = (1,0.33)$ $p_3 = (0.88,0.12)$ $p_4 = (0.59,0.41)$

We define a good split as the one that generates the "purest" distributions at child nodes. One option is to pick the $\theta$ that minimizes the following energy function:

$argmin_\theta (|S_1|H(S_1)+|S_2|H(S_2)+|S_2|H(S_2)+|S_3|H(S_3))$

Where $|S_i|H(S_i)$ is the weighted Shannon entropy that we can compute from $p_i$.

Until here there's no mystery. Let's add a constraint:

After splitting, we construct a matrix for each class in the following way:

$M'_{C_0} = \begin{bmatrix} 600 & 50 \\ 75 & 275 \\ \end{bmatrix}$

$M'_{C_1} = \begin{bmatrix} 200 & 0 \\ 10 & 190 \\ \end{bmatrix} $

And we normalize row-wise:

$M_{C_0} = \begin{bmatrix} 0.923 & 0.08 \\ 0.22 & 0.78 \\ \end{bmatrix}$

$M_{C_1} = \begin{bmatrix} 1 & 0 \\ 0.05 & 0.95 \\ \end{bmatrix} $

Our objective now is to have the matrices $M_{C_0}$ and $M_{C_1}$ the most different possible. So one ideal split would be:

$M_{C_0} = \begin{bmatrix} 1 & 0 \\ 0 & 1 \\ \end{bmatrix}$

$M_{C_1} = \begin{bmatrix} 0 & 1 \\ 1 & 0 \\ \end{bmatrix} $

From the example matrices we see that a quite good split like the one obtained in $S_1$ having $p_1 = (0.66,0.33)$ it becomes not as good if we have a look at the matrices: $M_{C_0}(1,1) = 0.923$ and $M_{C_0}(1,1) = 1.0$.

Once introduced my problem, here are my questions:

  1. How can I modify the energy function to obtain splits that maximize the difference between matrices? Direct entropy calculation doesn't seem to give good splits. How can I encode this post-normalization?
  2. How can I quantify this difference between matrices? In my real problem I have hundreds of nodes so I need to have a measure on how good is the matrix separation. I came up is using a divergence measure (KL, Jensen-Shannon, etc.) between matrices as they are row-wise probability measures, however, as number of samples can be very different at each row, I need to ponder this somehow.

Any help/comment/suggestion would be appreciated


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.