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.

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.

We consider the following scenario. A point robot is placed at some start location s in a 2-dimensional scene containing oriented rectangular obstacles. The robot must repeatedly travel back and forth between s and a second location t in the scene. The robot knows the coordinates of s and t but initially knows nothing about the positions or sizes of the obstacles. It can only determine the obstacles' locations by bumping into them. We would like an intelligent strategy for the robot so that its trips between s and t both are relatively fast initially and improve as more trips are taken and more information is gathered. In this paper we describe an algorithm for this problem with the following guarantee: in the first $k \leq n$ trips, the average distance per trip is at most $O(\sqrt{n/k})$ times the length of the shortest s-t path in the scene, where n is the Euclidean distance between s and t. We also show a matching lower bound for deterministic strategies. These results generalize known bounds on the one-trip problem. Our algorithm is based on a novel method for making an optimal trade-off between search effort and the goodness of the path found. We improve this algorithm to a "smooth" variant having the property that for every $i \leq n,$ the robot's ith trip length is $O(\sqrt{n/i})$ times the shortest s-t path length. A key idea of this paper is a method for analyzing obstacle scenes using a tree structure that can be defined based on the positions of the obstacles.

We provide approximation algorithms for some capacitated vehicle routing and delivery problems. These problems can all be viewed as instances of the following k-delivery TSP: given n source points and n sink points in a metric space, with exactly one item at each source, find a minimum length tour by a vehicle of finite capacity k to pick up and deliver exactly one item to each sink. The only known approximation algorithm for this family of problems is the 2.5-approximation algorithm of Anily and Hassin [ Networks, 22 (1992), pp. 419--433] for the special case k=1. For this case, we use matroid intersection to obtain a 2-approximation algorithm. Based on this algorithm and some additional lower bound arguments, we devise a factor-approximation for k-delivery TSP with arbitrary finite k. We also present a 2-approximation algorithm for the case $k = \infty$. We then initiate the study of dynamic variants of k-delivery TSP that model problems in industrial robotics and other applications. Specifically, we consider the situation where a robot arm (with finite or infinite capacity) must collect n point-objects moving in the Euclidean plane, and deliver them to the origin. The point-objects are moving in the plane with known, identical velocities---they might, for instance, be on a moving conveyor belt. We derive several useful structural properties that lead to constant-factor approximations for problems of this type that are relevant to the robotics application. Along the way, we show that maximum latency TSP is implicit in the dynamic problems, and that the natural "farthest neighbor" heuristic produces a good approximation for several notions of latency.

We show that any rectilinear polygonal subdivision in the plane can be converted into a "guillotine" subdivision whose length is at most twice that of the original subdivision. "Guillotine" subdivisions have a simple recursive structure that allows one to search for "optimal" such subdivisions in polynomial time, using dynamic programming. In particular, a consequence of our main theorem is a very simple proof that the k-MST problem in the plane has a constant-factor polynomial-time approximation algorithm: we obtain a factor of 2 (resp., 3) for the L 1 metric, and a factor of $2\sqrt{2}$ (resp., 3.266) for the L 2 (Euclidean) metric in the case in which Steiner points are allowed (resp., not allowed).

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.

We introduce a new model for learning with membership queries in which queries near the boundary of a target concept may receive incorrect or "don't care" responses. In partial compensation, we assume the distribution of examples has zero probability mass on the boundary region. The motivation behind this model is that the reason for the incorrect (or "don't care") response is that these examples are extremely rare in practice. Thus, it does not matter how the learner classifies them. We present several positive results in this new model. We show how to learn the intersection of two halfspaces when membership queries near the boundary may be answered incorrectly. Our algorithm is an extension of an algorithmof Baum [6, 5] which learns intersections of two homogeneous halfspaces in the PAC-with-membership-queries model. We also describe algorithms for learning several subclasses of monotone DNF formulas. 1 Introduction In most of the theoretical work in concept learning it is assumed t...

We presentan algorithm that gives a constant factor approximation for the following problem.Given a set of n points in the plane with a Euclidean distance metric and an integer k < n, find the tree of least weight that spans k points.If desired, one may also specify in the problem a "root vertex" that must be in the tree.Our result improves on the previous best bound of O(log k) of Garg and Hochbaum [5], which in turn improved a previous 0(kl/4) bound of Ravi et al [9].

We are given a set of points p1;...;pn and a symmetric distance matrix (dij) givingthedistancebetweenpiandpj. Wewishtoconstruct atourthatminimizesPni=1`(i),where`(i)is thelatencyofpi,denedtobethedistance traveledbeforerstvisitingpi.Thisproblem isalsoknownintheliteratureasthedeliveryman problem orthetravelingrepairmanproblem. It arises in a number ofapplicationsincluding disk-head scheduling, and turnsouttobesurprisinglydierentfromthetravelingsalesman problem in character. We give exact and approximate solutions to a number of cases, including a constant-factor approximation algorithm whenever the distance matrix satisfies the triangle inequality.

Article On learning embedded symmetric concepts Share on Authors: Avrim Blum View Profile , Prasad Chalasani View Profile , Jeffrey Jackson View Profile Authors Info & Claims COLT '93: Proceedings of the sixth annual conference on Computational learning theoryAugust 1993 Pages 337–346https://doi.org/10.1145/168304.168367Online:01 August 1993Publication History 15citation146DownloadsMetricsTotal Citations15Total Downloads146Last 12 Months0Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

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.>

We consider learning in situations where the function used to classify examples may switch back and forth between a small number of different concepts during the course of learning. We examine several models for such situations: oblivious models in which switches are made independent of the selection of examples, and more adversarial models in which a single adversary controls both the concept switches and example selections.