Skip to yearly menu bar Skip to main content


Causal meets Submodular: Subset Selection with Directed Information

Yuxun Zhou · Costas J Spanos

Area 5+6+7+8 #82

Keywords: [ Causality ] [ Model Selection and Structure Learning ] [ (Other) Optimization ] [ Combinatorial Optimization ] [ Information Theory ]


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.

Live content is unavailable. Log in and register to view live content