Search

The Shapley value is one of the most widely used measures of feature importance partly as it measures a feature's average effect on a model's prediction. We introduce joint Shapley values, which directly extend Shapley's axioms and intuitions: joint Shapley values measure a set of features' average contribution to a model's prediction. We prove the uniqueness of joint Shapley values, for any order of explanation. Results for games show that joint Shapley values present different insights from existing interaction indices, which assess the effect of a feature within a set of features. The joint Shapley values provide intuitive results in ML attribution problems. With binary features, we present a presence-adjusted global value that is more consistent with local intuitions than the usual approach., Source code available at https://github.com/harris-chris/joint-shapley-values

We introduce a natural extension of the exclusion process to hypergraphs and prove an upper bound for its mixing time. In particular we show the existence of a constant C such that for any connected, regular hypergraph G within some natural class, the ε-mixing time of the exclusion process on G with any feasible number of particles can be upper-bounded by C TEX(2,G) log(|V|/ε), where |V| is the number of vertices in G and TEX(2,G) is the 1/4-mixing time of the corresponding exclusion process with just two particles. Moreover we show this is optimal in the sense that there exist hypergraphs in the same class for which TEX(2,G) and the mixing time of just one particle are not comparable. The proofs involve an adaptation of the chameleon process, a technical tool invented by Morris (2006) and developed by Oliveira (2013) for studying the exclusion process on a graph.

Let $\sigma$ be a permutation of $\{0,\ldots,n\}$. We consider the Markov chain $X$ which jumps from $k\neq 0,n$ to $\sigma(k+1)$ or $\sigma(k-1)$, equally likely. When $X$ is at 0 it jumps to either $\sigma(0)$ or $\sigma(1)$ equally likely, and when $X$ is at $n$ it jumps to either $\sigma(n)$ or $\sigma(n-1)$, equally likely. We show that the identity permutation maximizes the expected hitting time of n, when the walk starts at 0. More generally, we prove that the hitting time of a random walk on a strongly connected $d$-directed graph is maximized when the graph is the line $[0,n]\cap\Z$ with $d-2$ self-loops at every vertex and $d-1$ self-loops at 0 and $n$.

It is well-known that both branching random walk models and trap models can exhibit intermittency and localisation phenomena; the prototypical examples being the parabolic Anderson and Bouchaud trap models respectively. Our aim is to investigate how these localisation phenomena interact. To do so, we study a hybrid model combining the dynamics of both the parabolic Anderson and the Bouchaud trap models; more precisely, we consider a variant of the parabolic Anderson model in which the underlying random walk driving the model is replaced with the Bouchaud trap model. In this initial study, we consider the model where the potential field distribution has Weibull tail decay and the trap distribution is bounded away from zero. In dimension one, we further assume that the trap distribution decays sufficiently fast. Under these conditions, we show that the localisation effects in the hybrid model are strongly dominated by the influence of the parabolic Anderson model; the Bouchaud trap model plays at most a minor role. Moreover, we distinguish regimes in which the Bouchaud trap model acts to strengthen or weaken the localisation effects due to the parabolic Anderson model, and also identify regimes in which the Bouchaud trap model has no influence at all on localisation in the hybrid model., Comment: Corrected typos, modified a coupling argument, updated references