Prasad Chalasani

ICML Conference 2020 Conference Paper

CAUSE: Learning Granger Causality from Event Sequences using Attribution Methods

• Wei Zhang 0058
• Thomas Kobber Panum
• Somesh Jha
• Prasad Chalasani
• David Page

We study the problem of learning Granger causality between event types from asynchronous, interdependent, multi-type event sequences. Existing work suffers from either limited model flexibility or poor model explainability and thus fails to uncover Granger causality across a wide variety of event sequences with diverse event interdependency. To address these weaknesses, we propose CAUSE (Causality from AttribUtions on Sequence of Events), a novel framework for the studied task. The key idea of CAUSE is to first implicitly capture the underlying event interdependency by fitting a neural point process, and then extract from the process a Granger causality statistic using an axiomatic attribution method. Across multiple datasets riddled with diverse event interdependency, we demonstrate that CAUSE achieves superior performance on correctly inferring the inter-type Granger causality over a range of state-of-the-art methods.

ICML Conference 2020 Conference Paper

Concise Explanations of Neural Networks using Adversarial Training

• Prasad Chalasani
• Jiefeng Chen 0001
• Amrita Roy Chowdhury 0001
• Xi Wu 0001
• Somesh Jha

We show new connections between adversarial learning and explainability for deep neural networks (DNNs). One form of explanation of the output of a neural network model in terms of its input features, is a vector of feature-attributions, which can be generated by various techniques such as Integrated Gradients (IG), DeepSHAP, LIME, and CXPlain. Two desirable characteristics of an attribution-based explanation are: (1) \emph{sparseness}: the attributions of irrelevant or weakly relevant features should be negligible, thus resulting in \emph{concise} explanations in terms of the significant features, and (2) \emph{stability}: it should not vary significantly within a small local neighborhood of the input. Our first contribution is a theoretical exploration of how these two properties (when using IG-based attributions) are related to adversarial training, for a class of 1-layer networks (which includes logistic regression models for binary and multi-class classification); for these networks we show that (a) adversarial training using an $\ell_\infty$-bounded adversary produces models with sparse attribution vectors, and (b) natural model-training while encouraging stable explanations (via an extra term in the loss function), is equivalent to adversarial training. Our second contribution is an empirical verification of phenomenon (a), which we show, somewhat surprisingly, occurs \emph{not only in 1-layer networks, but also DNNs trained on standard image datasets}, and extends beyond IG-based attributions, to those based on DeepSHAP: adversarial training with $\linf$-bounded perturbations yields significantly sparser attribution vectors, with little degradation in performance on natural test data, compared to natural training. Moreover, the sparseness of the attribution vectors is significantly better than that achievable via $\ell_1$-regularized natural training.

FOCS Conference 1996 Conference Paper

Approximate Option Pricing

• Prasad Chalasani
• Somesh Jha
• Isaac Saias

As increasingly large volumes of sophisticated options are traded in world financial markets, determining a "fair" price for these options has become an important and difficult computational problem. Many valuation codes use the binomial pricing model, in which the stock price is driven by a random walk. In this model, the value of an n-period option on a stock is the expected time-discounted value of the future cash flow on an n-period stock price path. Path-dependent options are particularly difficult to value since the future cash flow depends on the entire stock price path rather than on just the final stock price. Currently such options are approximately priced by Monte Carlo methods with error bounds that hold only with high probability and which are reduced by increasing the number of simulation runs. In this paper we show that pricing an arbitrary path-dependent option is #-P hard. We show that certain types of path-dependent options can be valued exactly in polynomial time. Asian options are path-dependent options that are particularly hard to price, and for these we design deterministic polynomial-time approximate algorithms. We show that the value of a perpetual American put option (which can be computed in constant time) is in many cases a good approximation to the value of an otherwise identical n-period American put option. In contrast to Monte Carlo methods, our algorithms have guaranteed error bounds that are polynomially small (and in some cases exponentially small) in the maturity n. For the error analysis we derive large-deviation results for random walks that may be of independent interest.

STOC Conference 1995 Conference Paper

A constant-factor approximation for the k -MST problem in the plane

• Avrim Blum
• Prasad Chalasani
• Santosh S. Vempala

STOC Conference 1994 Conference Paper

The minimum latency problem

• Avrim Blum
• Prasad Chalasani
• Don Coppersmith
• William R. Pulleyblank
• Prabhakar Raghavan
• Madhu Sudan 0001

FOCS Conference 1993 Conference Paper

An On-Line Algorithm for Improving Performance in Navigation

• Avrim Blum
• Prasad Chalasani

Recent papers have shown optimally-competitive on-line strategies for a robot traveling from a point s to a point t in certain unknown geometric environments. We consider the question: Having gained some partial information about the scene on its first trip from s to t, can the robot improve its performance on subsequent trips it might make? This is a type of on-line problem where a strategy must exploit partial information about the future (e. g. , about obstacles that lie ahead). For scenes with axis-parallel rectangular obstacles where the Euclidean distance between s and t is n, we present a deterministic algorithm whose average trip length after t trips, k/spl les/n, is O(/spl radic/n/k) times the length of the shortest s-t path in the scene. We also show that this is the best a deterministic strategy can do. This algorithm can be thought of as performing an optimal tradeoff between search effort and the goodness of the path found. We improve this algorithm so that for every i/spl les/n, the robot's ith trip length is O(/spl radic/n/t) times the shortest s-t path length. A key idea of the paper is that a tree structure can be defined in the scene, where the nodes are portions of certain obstacles and the edges are "short" paths from a node to its children. The core of our algorithms is an on-line strategy for traversing this tree optimally. >