Causal meets Submodular: Subset Selection with Directed Information
We study causal subset selection with Directed Information as the measure of prediction causality. Two typical tasks, causal sensor placement and covariate selection, are correspondingly formulated into cardinality constrained directed information maximizations. To attack the NP-hard problems, we show that the first problem is submodular while not necessarily monotonic. And the second one is "nearly" submodular. To substantiate the idea of approximate submodularity, we introduce a novel quantity, namely submodularity index (SmI), for general set functions. Moreover, we show that based on SmI, greedy algorithm has performance guarantee for the maximization of possibly non-monotonic and non-submodular functions, justifying its usage for a much broader class of problems. We evaluate the theoretical results with several case studies, and also illustrate the application of the subset selection to causal structure learning.
The authors study two related problems which they refer to as source detection (OPT1) and causal covariate selection (OPT2).  OPT1 is related to a body of work on sensor selection, but whereas past work typically use mutual information this work uses directed information.  Likewise problems like OPT2 have been studied for decades, though often with strong modeling assumptions.  The authors suggest using directed information for that too (it is a non-parametric method).  The authors show that OPT1 is submodular but not monotone (thus greedy search has performance guarantees), while OPT2 is monotone but generally not submodular.    The authors introduce a novel measure of how "submodular" a functions is (which they refer to as submodularity index SmI) and obtain performance bounds for maximization in OPT1 and OPT2 with cardinality constratints, where the bounds are a function of SmI.   They also analyze both simulated and real world data, showing performance of the algorithm and computing some empirically observed SmI values. 
 Overall, I find the work promising and it contains a number of results which will appeal to the NIPS community.  However, I think a significant revision for OPT2 is needed for it to appear at NIPS.  They are also missing citations for work closely related to their work on OPT2.  There are multiple minor issues that should also be addressed, listed further below.  Major comments (What I like):  -- Both problems are interesting and relevant to NIPS. Especially OPT2, broadly speaking, has been of great concern and generated decades of research in various domains.  To approach it with a non-parametric method is quite appealing because then one needs not worry as much about strong modeling assumptions.     -- SmI is an intriguing way of assessing submodularity, though it makes sense.  It is highly context dependent (function of A and k), but that seems necessary given your later work and data analysis.  I like how the results are not limited to specific functions but could potentially be applied to a broad range of combinatorial problems.    -- The performance bounds are good.    -- It was applied to both simulated and real world data.  Aside from empirical values for SmI, it does give credence at least to employing greedy methods (especially when exact is computationally prohibitive).    Major comments (What I think needs to be modified to improve the work):  (A) My major concern is with regards to the usefulness of the bounds for OPT2.  While results for OPT1 are clearly valid (since is submodular), the usefulness of the bounds for OPT2 is unknown.  They are useful only when OPT2 exhibits "quasi-submodularity," but when does that happen?  Statements such as       (line 44) "is “nearly” submodular in particular cases"   (line 216) "For quasi-submodular functions having negative SmI, although a degraded guarantee is produced, the bound is only slightly deteriorated when SmI is close to zero."   (line 227) "Similarly, for quasi-submodular functions, the guarantee is degraded but not too much if SmD is close to 0. Note that the objective function of OPT2 fits into this category." are made throughout the paper but not justified or made precise.    "quasi-submodular functions" is defined as (line 163) "We call a function quasi-submodular if it has a negative but close to zero SmI."  The authors never give a precise definition of what consistutes "close."  They also never give examples of when OPT2 is in fact quasi-submodular except in the extreme case of Proposition 2 (line 131) where you have independence *conditioned on Y_t*.  [Please give an example that satisfies Prop 2.  Even when causal covariates are marginally independent (which is already restrictive), say Y_{t+1} is a linear combination of marginally independent X_{it}'s,  then conditional independence (prop 2) won't hold.]    This is not to say that the formulas obtained are not useful for monotonic non-submodular functions (especially since they are applicable to potentially a wide range of combinatorial optimization problems), but some non-trivially "quasi-submodular" optimization problems need to be identified, and I don't think OPT2 is a good candidate.  Perhaps for some certain classes of distributions it could be shown to be (and if the authors can do this, I would be happy with them keeping OPT2 in), but in general not.  The graphical model literature on structure learning has examples where there is pairwise independence (similar to I(X-->Y)=0, I(Z-->Y)=0)) but the joint relationship (so I(X,Z-->Y) can be made arbitrarily large when the alphabet is not restricted (eg using the XOR function and converting vector valued binary variables (with Y(i) = X(i) XOR Z(i), then convert the vector to a larger-alphabet variable)).       Also, note that while I am happy to see they applied their work to data, and that the randomized greedy did well, the fact that randomized greedy did well does not imply quasi-submodularity holds.  [Greedy algorithms (though not randomized greedy) have been widely used in graphical model structure learning literature, for random variables and processes.]  The experiments do provide evidence for using randomized greedy, which is good.  I was furthermore happy that they included some empirical values of SmI index.  And for row 2 of Table 1, since all the values are larger than -0.6321 the bound in corollary 1 (line 224-225) would be nontrivial (approximation ratio bigger than 0).  This gives a little evidence of quasi-submodularity, and it is interesting that k=2 is the worst, whereas others have positive or "close" to 0 values.  In addressing this major concern, if proving when quasi-submodularity holds (maybe you can define "close" to be relative to E[f(S^g)], such that close means bound in 224-225 is nontrivial) is too difficult, empirical evidence is fine, though it would need to be more extensive than for a single stock in one dataset.   (B) The paper is missing a reference that appears to be closely related, especially for OPT2.  Searching "Submodularity directed information" on arxiv yielded two works     * [highly relevant] "Bounded Degree Approximations of Stochastic Networks" http://arxiv.org/abs/1506.04767 by authors Quinn et al (you cite some of their other works) which appears related for the OPT2 problem.  Especially Section 5 of the arxiv version, as they do cardinality constrained causal covariate selection (OPT2; it looks like they are doing "approximation", though the objective functions look similar) and propose a approximate submodularity measure and obtain bounds on the deterministic greedy search.  Their approximate submodularity measure is not the same as in this submission (SmI) and I can't tell whether the one in Quinn et al would be useful for studying OPT1.  Also, wrt my comment above about "quasi-submodularity" being unjustified, this work by Quinn et al also does not theoretically justify when their approximate submodularity is useful (when their alpha is close to 1).      They mention the arxiv version (I don't see it published yet) is based on a conference paper "Optimal bounded-degree approximations of joint distributions of networks of stochastic processes" ISIT 2013, which looks to have the same results (regarding approximate submodularity), though the causal covariate selection looks a little different.      * [less relevant] a very recent paper (just a few months out before the NIPS 2016 initial deadline) "Submodular Variational Inference for Network Reconstruction" http://arxiv.org/abs/1603.08616 that reconstructs the network, but does so assuming a diffusion model.           Minor comments   -- mentioned in Major comment (A), please provide examples when Prop 2 holds, esp if you cannot more generally identify when OPT2 is quasi-submodular.    -- Question: This work employs the CTW algorithm.  But the available code http://web.stanford.edu/~tsachy/DIcode/download.htm and the original paper [9] are for pairs of processes.  In the submission, you are dealing with sets.  Did you modify the code to handle DI for sets?  If so, are you sure the theoretical guarantees extend?  Or did you do a mapping, such as converting three binary processes into one process of alphabet 8? This might be straightforward but I wonder if there would be performance hit (for finite length data). I'm assuming you did not just find pairwise relations for the original processes and then combine individual parents, as that could lead to significant errors.      -- Can you provide any guidance to the reader on selecting $k$?  I think this is important given that not only there are computation tradeoffs but the approximation coefficient is sensitive to $k$ (especially for OPT2)    -- Line 185 with Algorithm 1.  You should provide a sentance or two explaining how this random greedy relates to deterministic.  It is not obvious at first glance of the notation, even though the idea is simple.  "At each step, instead of picking the best, we pick one of the top k best" or something like that.      -- line 131 "any" can have multiple meanings.  I assume you want it to mean "every pair" though it can also mean "at least one pair".  I'd suggest using "every" to avoid confusion.    -- Provide references for quantities in Section 2.  At first I thought you were introducing them but they are in some works you cite.    -- Double check your Reference section; right now it is a little sloppy (eg line 313 "gaussian" should be capitalized, journals in 340 and 346 should be capitalized, conference title in 358 should be capitalized, you use anacronyms for some conference proceedings but then write out names for others)    -- Lemma 2 line 197 please clarify the notation.    Are these lower case y's processes?  If so why lower case?  And is Y={y_1, .. y_M} or a strict subset or a strict superset?    -- in line 201 you make a comment about being able to lower bound SmI for order 2, yet wasn't that the worst case you found empirically? (thus suggesting it would be challenging to do so)    -- fix grammer line 205 "with each element appears in"    -- formula below line 201, what is "p_1"    -- line 238, in formula for \gamma, if S^{g_k} means |S^{g_k}|=k, then just use k in the formula, and you might consider putting a table or graph to show behavior    -- line 249 the data you use is old -- if it appeared in another paper you should cite the source.      -- Section 5  for the data, I'm sure the stock data is not binary, perhaps you designed the Bayesian network data to be so; but describe how your discretize the data (especially since to just binary, not even quantizing)    -- line 257 you should not say "is sufficient" for real world data unless you have ground truth knowledge you are basing that off of.  Even convergence is not sufficient (maybe for length 5 it converges to one value, for length 6 another)     -- line 261 include an equation reference; "the 1/e bound" is vague