Sign up ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Background :

I'm trying to learn aspects of information theory that might be relevant for neural decoding. I am a student and do not have a strong formal background in mathematics, statistics, or information theory.

I have run into one curiosity that I would like to understand better :

Say I have a set $X=x_1,x_2,\ldots,x_n$ of random variables, and would like to find a size $k\leq|X|$ subset that contains as much information as possible. This is complicated because the variables may contain redundant information.

It seems, intuitively, that "information" behaves like the size or volume of a set. In particular, I would like to know if some result similar to holds for selecting size $k$ subsets of $X$ that approximately maximize information. If all I can measure is the information content of an ensemble of variables, how good an approximation can I get by, starting from the empty set, always picking the variable that would maximize the information content of my subset ?

I have been told that I need to understand measure theory even to phrase this question correctly, and I apologize if my wording of the question is not rigorous.

share|cite|improve this question

1 Answer 1

up vote 2 down vote accepted

The prototypical way of measuring the "information content" of a set of random variables is by evaluating the Shannon entropy of their joint distribution. It is known that entropy is a submodular set function and that it is monotone: the joint distribution of a subset of the random variables cannot have more entropy than that of the set itself. Your question therefore becomes a special case of the following broader question: given the ability to evaluate a monotone, non-negative, submodular set function, how can I compute the $k$-element subset that maximizes this function? There is a greedy algorithm that generalizes the greedy algorithm for the maximum coverage problem: starting from the empty set, repeatedly enlarge your set by adding a single element that yields the greatest increase in the function value, until the number of elements chosen equals $k$. This algorithm, like the greedy algorithm for maximum coverage, achieves an approximation ratio of $e/(e-1)$. (Nemhauser, Wolsey, and Fisher, An analysis of approximations for maximizing submodular set functions, Math. Programming 14 (1978), 265-294.)

There are at least two senses in which this approximation ratio is the best possible under polynomial resource constraints. First, if the algorithm is only allowed to access the function by querying its value at specified sets, then any algorithm achieving an approximation ratio strictly less than $e/(e-1)$ must use an exponential (in $k$) number of queries. (Nemhauser and Wolsey, Best algorithms for approximating the maximum of a submodular set function, Math. Oper. Res. 3:3 (1978), 177-188.) Second, assuming the $P \neq NP$ conjecture, no polynomial-time algorithm can achieve a better approximation ratio, even for the special case of maximum coverage problems.

share|cite|improve this answer
Thanks, I really appreciate your help. This answer is clear and exactly addresses the question. –  MRule May 17 '11 at 14:02
Is it known whether entropy is a modular set function ? It seems like it is ? Since mutual information $MI=I(X;Y)$ and joint entropy $H(X,Y)$ obey the following relationship : $I(X;Y)+H(X,Y)=H(X)+H(Y)$ And, this would mean that all intuition about what happens when you take the union, intersection, and complement, with sets, should generalize to information for mutual information, joint entropy, and conditional entropy, respectively ? –  MRule May 19 '11 at 0:59

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.