Identifying Best Interventions through Online Importance Sampling

Rajat Sen, Karthikeyan Shanmugam, Alexandros G. Dimakis, Sanjay Shakkottai
Proceedings of the 34th International Conference on Machine Learning, PMLR 70:3057-3066, 2017.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v70-sen17a, title = {Identifying Best Interventions through Online Importance Sampling}, author = {Rajat Sen and Karthikeyan Shanmugam and Alexandros G. Dimakis and Sanjay Shakkottai}, booktitle = {Proceedings of the 34th International Conference on Machine Learning}, pages = {3057--3066}, year = {2017}, editor = {Precup, Doina and Teh, Yee Whye}, volume = {70}, series = {Proceedings of Machine Learning Research}, month = {06--11 Aug}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v70/sen17a/sen17a.pdf}, url = {https://proceedings.mlr.press/v70/sen17a.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T Identifying Best Interventions through Online Importance Sampling %A Rajat Sen %A Karthikeyan Shanmugam %A Alexandros G. Dimakis %A Sanjay Shakkottai %B Proceedings of the 34th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2017 %E Doina Precup %E Yee Whye Teh %F pmlr-v70-sen17a %I PMLR %P 3057--3066 %U https://proceedings.mlr.press/v70/sen17a.html %V 70 %X 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.
APA
Sen, R., Shanmugam, K., Dimakis, A.G. & Shakkottai, S.. (2017). Identifying Best Interventions through Online Importance Sampling. Proceedings of the 34th International Conference on Machine Learning, in Proceedings of Machine Learning Research 70:3057-3066 Available from https://proceedings.mlr.press/v70/sen17a.html.

Related Material