2
$\begingroup$

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

$\endgroup$

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.