Causal Graph Identification: optimization, performance bounds and reward optimization
A Talk by Urbashi Mitra (Gordon S. Marshall Professor in Engineering, University of Southern California)
About this Talk
Describing the underlying causes of phenomena affected by multiple variables can often by done via the representation of causal graphs, which are often assumed to be directed and acyclic.
The identification of causal graphs – delineating the cause and effect between collection of variables has relevance in wireless networks, genetic networks, epidemiology, economics, and the social sciences to name just a few application areas. Graph identification is done via the collection of observations or realizations of the random variables which are the nodes in the graph.
A host of strategies have been proposed for causal graph identification from greedy methods to those based on sparse approximation. We consider two problems in graph identification, the first is the recovery of the full directed graph by first detecting individual links in the graph.
Unique to our approach, but relevant to many applications is directly considering unequal error protection for edge detection, that is false negatives versus false positives. We derive the optimal link detection rule and bound performance. These bounds can be used as benchmarks for current discovery algorithms.
A challenge with our approach (as is also true for many causal graph identification methods) is the attendant computational complexity. Motivated by this issue, the second problem we address is the development of a modest complexity strategy via the learning of sub-graphs.
A new edge detection method based on mutual information is derived and shown to offer superior performance to state-of-the-art methods. We apply our low complexity approach to the optimization of interventions in multi-armed bandits wherein the goal is to determine how to select choices (e.g. which slot-machine arm to pull) to maximize a reward.
Interventions could include allocation of resources or enforcing nodes in a graph to have certain values or links to have certain weights. We see that unequal error protection has a significant impact in reward optimization in causal multi-armed bandits.
Joint work with Joni Shaska and Chen Peng
About The Speakers
Gordon S. Marshall Professor in Engineering, University of Southern California
Urbashi Mitra received the B.S. and the M.S. degrees from the University of California at Berkeley and her Ph.D. from Princeton University. She is the Gordon S. Marshall Professor in Engineering at the University of Southern California with appointments in Electrical Engineering and Computer Science
We’re a cloud tech company that provides organisations around the world with computing infrastructure and software to help them innovate, unlock efficiencies and become more effective. We also created the world’s first – and only – autonomous database to help organise and secure our customers’ data.
