2
$\begingroup$

Suppose we have an $N \times 2$ array $A$ where the two entries $A(k,1)$ and $A(k,2)$ give the number of occurrences of each of two classes at position $k$. Given a sub-interval $I$ of indices between $1$ and $N$, the information gain associated with the interval is a constant plus

$$p_I(p_{in} \log p_{in} + (1 - p_{in})\log(1 - p_{in})) + (1 - p_I)(p_{out} \log p_{out} + (1 - p_{out})\log(1 - p_{out}))$$

where

$$p_I = (\sum_{k \in I} A(k,1) + A(k,2)) / (\sum_{k} A(k,1) + A(k,2))$$

i.e. $p_I$ is the fraction of points contained in the interval $I$, and

$$p_{in} = \sum_{k \in I} A(k,1) / (\sum_{k \in I} (A(k,1) + A(k,2)))$$

i.e. $p_{in}$ is the fraction of class 1 when restricting to interval $I$, and similarly $p_{out}$ is the fraction of class 1 when restricting to outside interval $I$. In the formulas it is understood that $0 \log 0 = 0$.

It is trivial to find the subinterval that maximizes information gain in $O(N^2)$ time just by brute force. However, finding the maximum sum subinterval can be done in $O(N)$ time using Kadane's dynamic programming algorithm. Can we similarly get some sort of speed up for information gain? I tried a recursion where you split the range in half and optimize the left half, then optimize the right half, and then find the optimal solution in the left half that reaches the middle of the array, and similarly find the optimal solution in the right half that reaches the middle of the array, and concatenate those two solutions, so that overall there are 3 candidates for the global optimal solution (either just in left half, or just in right half, or crossing the middle of the array). However experiments have shown that this fails when the global optimal solution crosses the middle of the array. Maybe some sort of non-linear transformation can make it work? Or another optimization strategy?

$\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.