Identifying Best Interventions through Online Importance Sampling
Identifying Best Interventions through Online Importance Sampling
复制标题
通过在线重要性抽样确定最佳干预措施
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
S. Shakkottai
中科院分区：
文献类型：
--
作者：
Rajat Sen;Karthikeyan Shanmugam;A. Dimakis;S. Shakkottai
受计算广告和系统生物学应用的启发，我们考虑在无循环因果有向图中识别源节点V的几个可能的软干预中的最佳问题，以最大化目标节点Y（位于V的下游）的期望值。我们的设置规定了在各种干预措施下取样的固定总预算，以及对不同类型干预措施的成本限制。我们将其视为具有K条手臂的最佳手臂识别强盗问题，其中每条手臂都是V处的软干预，并利用手臂之间的信息泄漏为该问题提供了第一个间隙相关误差和简单的后悔界限。我们的结果比传统的最佳手臂识别结果有了显著的改进。我们的经验表明，我们的算法在流式细胞术数据集中优于目前的技术水平，并且还将我们的算法应用于对图像分类的Inception-v3深度网络的模型解释。
Motivated by applications in computational advertising and systems biology, we consider the problem of identifying the best out of several possible soft interventions at a source node V in an acyclic causal directed graph, to maximize the expected value of a target node Y (located downstream of V). Our setting imposes a fixed total budget for sampling under various interventions, along with cost constraints on different types of interventions. We pose this as a best arm identification bandit problem with K arms where each arm is a soft intervention at V, and leverage the information leakage among the arms to provide the first gap dependent error and simple regret bounds for this problem. Our results are a significant improvement over the traditional best arm identification results. We empirically show that our algorithms outperform the state of the art in the Flow Cytometry data-set, and also apply our algorithm for model interpretation of the Inception-v3 deep net that classifies images.