Sensor Selection in High-Dimensional Gaussian Trees with Nuisances
We consider the sensor selection problem on multivariate Gaussian distributions where only a subset of latent variables is of inferential interest. For pairs of vertices connected by a unique path in the graph, we show that there exist decompositions of nonlocal mutual information into local information measures that can be computed efficiently from the output of message passing algorithms. We integrate these decompositions into a computationally efficient greedy selector where the computational expense of quantification can be distributed across nodes in the network. Experimental results demonstrate the comparative efficiency of our algorithms for sensor selection in high-dimensional distributions. We additionally derive an online-computable performance bound based on augmentations of the relevant latent variable set that, when such a valid augmentation exists, is applicable for any distribution with nuisances.
The paper introduces a method to select incrementally 
      a subset of features that are informative about a specific relevant 
      set of variables. The issue at hand is about being able to be better 
      than a generic detector with respect to target variables when these 
      are specified, and nuisance nodes exist. A core assumption is 
      Gaussianity which allows much of the procedure to work. Finally, an 
      enhanced relevance set is introduced to "lift" the original, 
      non-submodular process towards a sub-modular one which exhibits 
      performance guarantees for greedy sensor selection. Though a 
      quite technical paper, I enjoyed reading it. There are lots of 
      interesting and - to me - novel ideas combined in the work, the 
      construction of the composable warped MI measure, the relation to 
      distributed computing, and making the model sub-modular were all 
      attractive properties of the work. It is a contentful paper, which I 
      found worth the time reading. One potential aspect that the 
      reviewer is not sure about is whether the Gaussian scenario is really 
      relevant in practice for the type of networks considered here. In 
      particular in large networks with, possibly, very simple sensors where 
      this approach would be most interesting, Gaussianity is not really a 
      default, and the question is how much one would lose when that 
      happens. The authors indicate that treatment of non-Gaussianity is 
      future work, but a short discussion on the relevance of the results in 
      case of non-Gaussian variables (perhaps, as an extreme guiding 
      example, one could consider binary variables as thought model) may be 
      in place here; it's clear that a full computation is out of the place 
      here, but some comments as to what can be expected to change. 
      Generally clear, notwithstanding its technicality, there are a 
      number of issues that might be improved in the presentation, I will 
      list them below: - line 62: Gaussian belief propagation is 
      introduced as (BP), but later referred to as GaBP. Please make it 
      consistent. - line 181: the use of the indicator function seems to 
      miss an argument - the right side of the inequality is a scalar, the 
      left side is a function. - lines 262-264: I read and reread 
      the argument, but it was to compact. Please rephrase the argument of 
      Remark 6 (first three lines of the remark). - line 269: what 
      is a pair of *unique* vertices? - line 272: the explanation for 
      \zeta is unclear here. How do you compute it? Where does this term 
      arise from? - line 289: I did not follow the reasoning why in the 
      term W(i;j|A) + \zeta(r,j; G), the \zeta contains the r,j pair? In 
      (9), \zeta is computed for the boundary nodes u and v, but here, j 
      replaces the boundary node on the opposite side of the path 
      emanating from r. What if there is a node, say q, further down the 
      path? Surely \zeta will not be unchanged if we replace j by q? So, 
      why then, are we allowed to use j? Perhaps it's a simple argument, but 
      I didn't see it. - line 322: I did not immediately see the 
      operation suggested in footnote 2 - I do not see how the setting to 
      -\inf works; what causes the blocking in the chain following 
      procedure? - line 399: "running on a fictitious problem" - this 
      formulation is unfortunate. Do you mean that you generate a surrogate 
      problem ^R (i.e. \hat R) by making S conditionally independent and 
      then run your algorithm? This is what I understood. But it may mean 
      something different. Please clarify. ** Supplementary Material 
      Comments - line 22: "joint potential over the chain" - please define 
      the term "joint potential". You do not use jargon in the paper (which 
      is good), please keep that style in the Supplementary Material. 
      - line 66: "subchain" -> "subchains" - line 67: font of 
      I(x_1;x_k) - lines 69-77: The argument is a bit tight and 
      difficult to follow. Please reformulate. You have space here.