2
$\begingroup$

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 http://en.wikipedia.org/wiki/Maximum_coverage_problem 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.

$\endgroup$
0

1 Answer 1

4
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Thanks, I really appreciate your help. This answer is clear and exactly addresses the question. $\endgroup$
    – MRule
    May 17, 2011 at 14:02
  • $\begingroup$ 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 ? $\endgroup$
    – MRule
    May 19, 2011 at 0:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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