# Complexity of / best algorithm for finding the dichotomy that maximizes information gain?

Suppose that $X$ is a finite set with a probability measure $P$. I want to find the subset $A \subset X$ so that the information gain of conditioning on ${A, A^c}$ is maximal. That is, I want to find $A$ that maximizes

$$H(X) -H(X|\{A,A^c\}) = H(X) - (P(A)H(A) + P(A^c) H(A^c)),$$

where $H(A)$ refers to the entropy of the conditional probability distribution so $\mu(B) = P(B \cap A) / P(A)$. (If $P(A) = 0$, then set $P(A) H(A) = 0$. In any case, it won't be a maximizer.)

Since this splits $X$ into two sets, I am calling this a dichotomy, and the question is of finding the dichotomy that produces the largest information gain.

Question: What is the complexity of this problem? (As D.W. points out below, a reasonable corresponding decision problem is - for $t \geq 0$, is there an $A$ so that information gain is $\geq t$? This decision problem is in NP, and we can ask if it is NP-hard, etc.) Is there a good heuristic algorithm for making this choice? What if I ask for an approximately, probably correct algorithm?

I am asking this question since I'm studying decision trees in machine learning and also coding theory, and this seems like a basic question in both settings.

• Information gain in decision trees is usually defined differently, see wikipedia, for instance. Is your definition the same as the usual one? – Discrete lizard Apr 10 '17 at 21:37
• @Discretelizard The differences from my definition and that on the wikipedia page are: 1) they consider only splitting around features, wheras I want all subsets 2) they use empirical entropy and probabilities. My problem is a subset of theirs if enough features are given. Otherwise, you could imagine that you impose the additional constraint on my original question of having some set of functions that you can use to describe the allowable subsets. – Lorenzo Najt Apr 10 '17 at 21:47
• Fascinating question! It seems reasonable to ask whether the problem is NP-hard. (It's an optimization problem, so it's not in NP, but the corresponding decision problem is. The natural decision associated with it is: given $p$, $t$, determine whether there exists a set $A$ with information gain $\ge t$. Any efficient algorithm the decision problem can likely be turned into an efficient algorithm for the optimization problem by binary search. The decision problem is in NP, so it seems reasonable to ask whether the decision problem is NP-complete.) – D.W. Apr 10 '17 at 22:40
• @D.W. Thanks for the clarification ! I'll edit my question to reflect your comment. – Lorenzo Najt Apr 10 '17 at 22:51
• @D.W. I want to make sure I understand the decision problem is in NP (I haven't studied complexity formally yet.) I think the point is that you can run the algorithm C(A) = { print A if information gain is $\geq t$ } for each of the subsets $A \subset X$.$C(A)$ runs in polynomial time in $|A| \leq |X|$ (we can compute logs efficiently presumably) for a fixed A, and we "non-deterministically" choose all subsets A at the outset of the program. Is this roughly correct? – Lorenzo Najt Apr 10 '17 at 22:59

The information gain in that case depends only on the mass of $A$, and is maximized when $P(A)=\frac{1}{2}$. This probably shows why this definition of information gain is not very interesting.

Suppose $X=\left\{x_1,...,x_n\right\}$ and $P=\left(p_1,...,p_n\right)$.

The information gain is defined as

$IG(A)=H(X)-\left(P(A)H(A)+\left(1-P(A)\right)H\left(X\setminus A\right)\right)$

Where $H(A)$ is the entropy of the random variable which takes values in $A$ with probabilities $q_x = \mathbb{1}_{x\in A}\frac{p_x}{p(A)}$.

Now lets write explicitly what is $IG(A)$:

\begin{align*} IG(A)&= H(X)+P(A)\sum\limits_{x\in A} \frac{p_x}{P(A)}\log \frac{p_x}{P(A)}+ \left(1-P(A)\right)\sum\limits_{x\in X\setminus A} \frac{p_x}{1-P(A)}\log\frac{p_x}{1-P(A)} \\ &= H(x)+\sum\limits_{x\in A} p_x\log \frac{p_x}{P(A)}+ \sum\limits_{x\in X\setminus A} p_x\log\frac{p_x}{1-P(A)} \\ &= H(A)+\sum\limits_{x\in A} p_x\log p_x -\sum\limits_{x\in A} p_x \log P(A) + \sum\limits_{x\in X\setminus A}p_x\log p_x - \sum\limits_{x\in X\setminus A}p_x\log \left(1-P(A)\right) \\ &= -P(A)\log P(A) - \left(1- P(A)\right)\log(1-P(A)). \end{align*}

So setting $y=P(A)$, you seek to maximize $f(y)=-y\log y-(1-y)\log(1-y)$ in $y\in[0,1]$. Maximum is achieved at $y=\frac{1}{2}$.

The optimization problem (or corresponding decision problem) is NP-hard, meaning that unless $P=NP$, you can't find a subset $A$ which minimizes $\left| P(A)-\frac{1}{2}\right|$ in polynomial time. This problem is called the partition problem (special case of subset sum), only that now you have the constraint that the elements sum to 1. See this question for some information about the hardness of partition problem.

• Okay, I think I understand your point about this not being an interesting notion of information gain (for decision tree classifiers). The point is that we have some random variable C defined on X, which we think of as the class of an instance, and we want to maximize the difference between the entropy of C and the expectation of the entropy of C conditioned on the partition $\{A, A^c\}$. $H(C) - P(A) H(C | A) - P(A^c) H(C | A^c) = H(C) - \Sigma_{\epsilon} \Sigma_{i= \pm} P(C^i \cap A^{\epsilon}) log P(C^i \cap A^{\epsilon}) + \Sigma_e P(A^e) log P(A^e)$. – Lorenzo Najt Apr 11 '17 at 4:35
• $(A^e$ is A or $A^c$). This formula exhibits the previous cancellation if C is the identity classifier, but otherwise doesn't exhibit the same cancellation. In particular, the minimization is not the same as maximizing $\Sigma_e P(A^e) log P(A^e)$. I think I'll ask about this optimization problem as a separate question. (Still curious about the connection of the subset sum problem to the original formulation though.) – Lorenzo Najt Apr 11 '17 at 4:37
• I asked a new question here : cs.stackexchange.com/questions/73778/… – Lorenzo Najt Apr 11 '17 at 4:56