Variational Information Maximization for Feature Selection
Feature selection is one of the most fundamental problems in machine learning. An extensive body of work on information-theoretic feature selection exists which is based on maximizing mutual information between subsets of features and class labels. Practical methods are forced to rely on approximations due to the difficulty of estimating mutual information. We demonstrate that approximations made by existing methods are based on unrealistic assumptions. We formulate a more flexible and general class of assumptions based on variational distributions and use them to tractably generate lower bounds for mutual information. These bounds define a novel information-theoretic framework for feature selection, which we prove to be optimal under tree graphical models with proper choice of variational distributions. Our experiments demonstrate that the proposed method strongly outperforms existing information-theoretic feature selection approaches.
The paper proposes an interesting algorithm for feature selection motivated by mutual information maximization. The authors attempt to show problems with current approaches that address the same problem (but I believe that their argument is flawed). The main idea behind their approach is to estimate a lower bound on the mutual information and use this estimate for a greedy feature selection. The paper describes a set of experiments showing clear advantage of the proposed method over other information maximization approaches to feature selection. 
There are several important issues that I believe must be addressed  A. The authors make the following argument against current approaches.    Current approaches are optimal under a pair of assumptions.    These assumptions are hardly ever satisfied simultaneously.    Therefore current approaches are flawed.    There is a clear flawed logic here. The only thing shown is that current    approaches are not optimal. But this is clear even from the greedy    perspective. Their algorithms is also clearly non optimal in the general    case. I don't think this is such a big deal, except that the    authors spend a lot of text with figures, etc., to make this argument.  B. I believe the strength of the paper is the new algorithm, and the    experimental evaluation which shows its superiority.    Still, I would like to point out the following problems with the experiments.    B1. They compare the method only to other approaches to information        maximization, and not to other feature selection schemes.         In particular I was missing comparison to the FS, as described, for        example, in the work of Das and Kempe referenced in the paper.    B2. The methodology used by the authors (apparently following other work        in the field) is to performs the comparison with 3 nearest neighbors        and linear SVM. As explained below my concern is mostly with the linear        SVM. I was expecting the following two experiments:        1. An estimate of the maximized information showing (hopefully)           that the proposed method gives larger values.        2. Nonlinear SVM. Here is why.              There is an implied assumption that information maximization is better       than correlation based techniques (cf line 24).       So One would expect the features selected using information maximization       to outperform those selected by, eg, FS.       But this would clearly not be the case if the classifier is linear.       Example: if both x and x^2 are features, linear classifiers can use       both. But information maximization would most likely not select both.        This raises the possibility that an algorithm more similar to FS       would perform better with linear SVM even though it would produce       smaller mutual information.   C. I was missing references and discussion of work related to "Markov Blanket".  D. Typo in Table 1 caption. What is listed as d should be T.     E. The authors state (line 55) that optimal feture selection that maximizes    the mutual information is NP-hard. Could you please provide a reference?     (I believe the problem is much more difficult.)