Search

Counterfactual explanations inform ways to achieve a desired outcome from a machine learning model. However, such explanations are not robust to certain real-world changes in the underlying model (e.g., retraining the model, changing hyperparameters, etc.), questioning their reliability in several applications, e.g., credit lending. In this work, we propose a novel strategy -- that we call RobX -- to generate robust counterfactuals for tree-based ensembles, e.g., XGBoost. Tree-based ensembles pose additional challenges in robust counterfactual generation, e.g., they have a non-smooth and non-differentiable objective function, and they can change a lot in the parameter space under retraining on very similar data. We first introduce a novel metric -- that we call Counterfactual Stability -- that attempts to quantify how robust a counterfactual is going to be to model changes under retraining, and comes with desirable theoretical properties. Our proposed strategy RobX works with any counterfactual generation method (base method) and searches for robust counterfactuals by iteratively refining the counterfactual generated by the base method using our metric Counterfactual Stability. We compare the performance of RobX with popular counterfactual generation methods (for tree-based ensembles) across benchmark datasets. The results demonstrate that our strategy generates counterfactuals that are significantly more robust (nearly 100% validity after actual model changes) and also realistic (in terms of local outlier factor) over existing state-of-the-art methods., Comment: Accepted at ICML 2022

Solving general Markov decision processes (MDPs) is a computationally hard problem. Solving finite-horizon MDPs, on the other hand, is highly tractable with well known polynomial-time algorithms. What drives this extreme disparity, and do problems exist that lie between these diametrically opposed complexities? In this paper we identify and analyse a sub-class of stochastic shortest path problems (SSPs) for general state-action spaces whose dynamics satisfy a particular drift condition. This construction generalises the traditional, temporal notion of a horizon via decreasing reachability: a property called reductivity. It is shown that optimal policies can be recovered in polynomial-time for reductive SSPs -- via an extension of backwards induction -- with an efficient analogue in reductive MDPs. The practical considerations of the proposed approach are discussed, and numerical verification provided on a canonical optimal liquidation problem., Comment: 15 pages, 10 figures, 1 algorithm

We consider a novel queuing problem where the decision-maker must choose to accept or reject randomly arriving tasks into a no buffer queue which are processed by $N$ identical servers. Each task has a price, which is a positive real number, and a class. Each class of task has a different price distribution and service rate, and arrives according to an inhomogenous Poisson process. The objective is to decide which tasks to accept so that the total price of tasks processed is maximised over a finite horizon. We formulate the problem as a discrete time Markov Decision Process (MDP) with a hybrid state space. We show that the optimal value function has a specific structure, which enables us to solve the hybrid MDP exactly. Moreover, we prove that as the time step is reduced, the discrete time solution approaches the optimal solution to the original continuous time problem. To improve the scalability of our approach to a greater number of task classes, we present an approximation based on state abstraction. We validate our approach on synthetic data, as well as a real financial fraud data set, which is the motivating application for this work., Comment: 7+1 pages main text, 16 pages supplementary material, accepted to AAAI 2022

There exist several methods that aim to address the crucial task of understanding the behaviour of AI/ML models. Arguably, the most popular among them are local explanations that focus on investigating model behaviour for individual instances. Several methods have been proposed for local analysis, but relatively lesser effort has gone into understanding if the explanations are robust and accurately reflect the behaviour of underlying models. In this work, we present a survey of the works that analysed the robustness of two classes of local explanations (feature importance and counterfactual explanations) that are popularly used in analysing AI/ML models in finance. The survey aims to unify existing definitions of robustness, introduces a taxonomy to classify different robustness approaches, and discusses some interesting results. Finally, the survey introduces some pointers about extending current robustness analysis approaches so as to identify reliable explainability methods., Comment: 4 pages plus references. Accepted at the workshop on Explainable AI in Finance (XAI-FIN21). Camera-ready version. V2: Added more references and expanded robust explanations for counterfactuals

Feature attributions are a common paradigm for model explanations due to their simplicity in assigning a single numeric score for each input feature to a model. In the actionable recourse setting, wherein the goal of the explanations is to improve outcomes for model consumers, it is often unclear how feature attributions should be correctly used. With this work, we aim to strengthen and clarify the link between actionable recourse and feature attributions. Concretely, we propose a variant of SHAP, Counterfactual SHAP (CF-SHAP), that incorporates counterfactual information to produce a background dataset for use within the marginal (a.k.a. interventional) Shapley value framework. We motivate the need within the actionable recourse setting for careful consideration of background datasets when using Shapley values for feature attributions with numerous synthetic examples. Moreover, we demonstrate the efficacy of CF-SHAP by proposing and justifying a quantitative score for feature attributions, counterfactual-ability, showing that as measured by this metric, CF-SHAP is superior to existing methods when evaluated on public datasets using tree ensembles., Comment: Accepted at FAccT '22 (2022 ACM Conference on Fairness, Accountability, and Transparency)

We present a new method for counterfactual explanations (CFEs) based on Bayesian optimisation that applies to both classification and regression models. Our method is a globally convergent search algorithm with support for arbitrary regression models and constraints like feature sparsity and actionable recourse, and furthermore can answer multiple counterfactual questions in parallel while learning from previous queries. We formulate CFE search for regression models in a rigorous mathematical framework using differentiable potentials, which resolves robustness issues in threshold-based objectives. We prove that in this framework, (a) verifying the existence of counterfactuals is NP-complete; and (b) that finding instances using such potentials is CLS-complete. We describe a unified algorithm for CFEs using a specialised acquisition function that composes both expected improvement and an exponential-polynomial (EP) family with desirable properties. Our evaluation on real-world benchmark domains demonstrate high sample-efficiency and precision., Comment: 20 pages, 5 figures, 3 tables

We prove that a finite group $G$ has a normal Sylow $p$-subgroup $P$ if, and only if, every irreducible character of $G$ appearing in the permutation character $({\bf 1}_P)^G$ with multiplicity coprime to $p$ has degree coprime to $p$. This confirms a prediction by Malle and Navarro from 2012. Our proof of the above result depends on a reduction to simple groups and ultimately on a combinatorial analysis of the properties of Sylow branching coefficients for symmetric groups., Comment: 16 pages; we thank Gunter Malle for comments on a previous version

Our first main result is a uniform bound, in every dimension $k \in \mathbb N$, on the topological Tur\'an numbers of $k$-dimensional simplicial complexes: for each $k \in \mathbb N$, there is a $\lambda_k \ge k^{-2k^2}$ such that for any $k$-complex $\mathcal{S}$, every $k$-complex on $n \ge n_0(\mathcal{S})$ vertices with at least $n^{k+1 - \lambda_k}$ facets contains a homeomorphic copy of $\mathcal{S}$. This was previously known only in dimensions one and two, both by highly dimension-specific arguments: the existence of $\lambda_1$ is a result of Mader from 1967, and the existence of $\lambda_2$ was suggested by Linial in 2006 and recently proved by Keevash-Long-Narayanan-Scott. We deduce this geometric fact from a purely combinatorial result about trace-bounded hypergraphs, where an $r$-partite $r$-graph $H$ with partite classes $V_1, V_2, \dots, V_r$ is said to be $d$-trace-bounded if for each $2 \le i \le r$, all the vertices of $V_i$ have degree at most $d$ in the trace of $H$ on $V_1 \cup V_2 \cup \dots \cup V_i$. Our second main result is the following estimate for the Tur\'an numbers of degenerate trace-bounded hypergraphs: for all $r \ge 2$ and $d\in\mathbb N$, there is an $\alpha_{r,d} \ge (5rd)^{1-r}$ such that for any $d$-trace-bounded $r$-partite $r$-graph $H$, every $r$-graph on $n \ge n_0(H)$ vertices with at least $n^{r - \alpha_{r,d}}$ edges contains a copy of $H$. This strengthens a result of Conlon-Fox-Sudakov from 2009 who showed that such a bound holds for $r$-partite $r$-graphs $H$ satisfying the stronger hypothesis that the vertex-degrees in all but one of its partite classes are bounded (in $H$, as opposed to in its traces)., Comment: 12 pages

Let $p$ be any prime. Let $P_n$ be a Sylow $p$-subgroup of the symmetric group $S_n$. Let $\phi$ and $\psi$ be linear characters of $P_n$ and let $N$ be the normaliser of $P_n$ in $S_n$. In this article we show that the inductions of $\phi$ and $\psi$ to $S_n$ are equal if, and only if, $\phi$ and $\psi$ are $N$--conjugate. This is an analogue for symmetric groups of a result of Navarro for $p$-solvable groups., Comment: 27 pages, reviewer comments and corrections incorporated

We prove the well-known Brown-Erd\H{o}s-S\'os Conjecture for hypergraphs of large uniformity in the following form: any dense linear $r$-graph $G$ has $k$ edges spanning at most $(r-2)k+3$ vertices, provided the uniformity $r$ of $G$ is large enough given the linear density of $G$, and the number of vertices of $G$ is large enough given $r$ and $k$., Comment: 9 pages

We prove a uniform bound on the topological Tur\'an number of an arbitrary two-dimensional simplicial complex $S$: any $n$-vertex two-dimensional complex with at least $C_S n^{3-1/5}$ facets contains a homeomorphic copy of $S$, where $C_S > 0$ is an absolute constant depending on $S$ alone. This result, a two-dimensional analogue of a classical result of Mader for one-dimensional complexes, sheds some light on an old problem of Linial from 2006., Comment: 9 pages, submitted

We show that there exists an absolute constant $C>0$ such that any family $\mathcal{F}\subset \{0,1\}^n$ of size at least $Cn^3$ has dual VC-dimension at least 3. Equivalently, every family of size at least $Cn^3$ contains three sets such that all eight regions of their Venn diagram are non-empty. This improves upon the $Cn^{3.75}$ bound of Gupta, Lee and Li and is sharp up to the value of the constant., Comment: 11 pages

In this note we study randomized voting trees, previously introduced by Fisher, Procaccia and Samorodnitsky. They speculate that a non-trivial performance guarantee may be achievable using randomized, balanced trees whose height is carefully chosen. We explore some connections to the so-called Volterra quadratic stochastic operators, and show that uniformly random voting trees cannot provide a performance guarantee that is linear in the number of individuals., Comment: 9 pages

Suppose that a binary operation $\circ$ on a finite set $X$ is injective in each variable separately and also associative. It is easy to prove that $(X,\circ)$ must be a group. In this paper we examine what happens if one knows only that a positive proportion of the triples $(x,y,z)\in X^3$ satisfy the equation $x\circ(y\circ z)=(x\circ y)\circ z$. Other results in additive combinatorics would lead one to expect that there must be an underlying "group-like" structure that is responsible for the large number of associative triples. We prove that this is indeed the case: there must be a proportional-sized subset of the multiplication table that approximately agrees with part of the multiplication table of a metric group. We also present an example that suggests that our result cannot be strengthened to yield a dense subset that agrees with part of the multiplication table of a group., Comment: Another substantial revision, following some very helpful comments from an anonymous referee

We show that a dense subset of a sufficiently large group multiplication table contains either a large part of the addition table of the integers modulo some $k$, or the entire multiplication table of a certain large abelian group, as a subgrid. As a consequence, we show that triples systems coming from a finite group contain configurations with $t$ triples spanning $\mathcal{O}(\sqrt{t})$ vertices, which is the best possible up to the implied constant. We confirm that for all $t$ we can find a collection of $t$ triples spanning at most $t+3$ vertices, resolving the Brown--Erd\H os--S\'os conjecture in this context. The proof applies well-known arithmetic results including the multidimensional versions of Szemer\'edi's theorem and the density Hales--Jewett theorem., Comment: Clarified a few points

In the Boolean lattice, Sperner's, Erd\H{o}s's, Kleitman's and Samotij's theorems state that families that do not contain many chains must have a very specific layered structure. We show that if instead of $\mathbb{Z}_2^n$ we work in $\mathbb{Z}_{2^n}$, several analogous statements hold if one replaces the word $k$-chain by projective cube of dimension $2^{k-1}$. We say that $B_d$ is a projective cube of dimension $d$ if there are numbers $a_1, a_2, \ldots, a_d$ such that $$B_d = \left\{\sum_{i\in I} a_i \bigg\rvert \emptyset \neq I\subseteq [d]\right\}.$$ As an analog of Sperner's and Erd\H{o}s's theorems, we show that whenever $d=2^{\ell}$ is a power of two, the largest $d$-cube free set in $\mathbb{Z}_{2^n}$ is the union of the largest $\ell$ layers. As an analog of Kleitman's theorem, Samotij and Sudakov asked whether among subsets of $\mathbb{Z}_{2^n}$ of given size $M$, the sets that minimize the number of Schur triples (2-cubes) are those that are obtained by filling up the largest layers consecutively. We prove the first non-trivial case where $M=2^{n-1}+1$, and conjecture that the analog of Samotij's theorem also holds. Several open questions and conjectures are also given., Comment: 23 pages

Alon, Bohman, Holzman and Kleitman proved that any partition of a $d$-dimensional discrete box into proper sub-boxes must consist of at least $2^d$ sub-boxes. Recently, Leader, Mili\'{c}evi\'{c} and Tan considered the question of how many odd-sized proper boxes are needed to partition a $d$-dimensional box of odd size, and they asked whether the trivial construction consisting of $3^d$ boxes is best possible. We show that approximately $2.93^d$ boxes are enough, and consider some natural generalisations., Comment: 19 pages, 10 figures

We study a variant of the chip-firing game called \emph{diffusion}. In diffusion on a graph, each vertex of the graph is initially labelled with an integer interpreted as the number of chips at that vertex, and at each subsequent step, each vertex simultaneously fires one chip to each of its neighbours with fewer chips. Since this firing rule may result in negative labels, diffusion, unlike the parallel chip-firing game, is not obviously periodic. In 2016, Duffy, Lidbetter, Messinger and Nowakowski nevertheless conjectured that diffusion is always eventually periodic, and moreover, that the process eventually has period either 1 or 2. Here, we establish this conjecture., Comment: 7 pages, submitted

A method combining photogrammetry with ballistic analysis is demonstrated to identify flying debris in a rocket launch environment. Debris traveling near the STS-124 Space Shuttle was captured on cameras viewing the launch pad within the first few seconds after launch. One particular piece of debris caught the attention of investigators studying the release of flame trench fire bricks because its high trajectory could indicate a flight risk to the Space Shuttle. Digitized images from two pad perimeter high-speed 16-mm film cameras were processed using photogrammetry software based on a multi-parameter optimization technique. Reference points in the image were found from 3D CAD models of the launch pad and from surveyed points on the pad. The three-dimensional reference points were matched to the equivalent two-dimensional camera projections by optimizing the camera model parameters using a gradient search optimization technique. Using this method of solving the triangulation problem, the xyz position of the object's path relative to the reference point coordinate system was found for every set of synchronized images. This trajectory was then compared to a predicted trajectory while performing regression analysis on the ballistic coefficient and other parameters. This identified, with a high degree of confidence, the object's material density and thus its probable origin within the launch pad environment. Future extensions of this methodology may make it possible to diagnose the underlying causes of debris-releasing events in near-real time, thus improving flight safety., Comment: 26 pages, 11 figures, 3 tables

Within the first few seconds after launch of STS-124, debris traveling vertically near the vehicle was captured on two 16-mm film cameras surrounding the launch pad. One particular piece of debris caught the attention of engineers investigating the release of the flame trench fire bricks. The question to be answered was if the debris was a fire brick, and if it represented the first bricks that were ejected from the flame trench wall, or was the object one of the pieces of debris normally ejected from the vehicle during launch. If it was typical launch debris, such as SRB throat plug foam, why was it traveling vertically and parallel to the vehicle during launch, instead of following its normal trajectory, flying horizontally toward the north perimeter fence? By utilizing the Runge-Kutta integration method for velocity and the Verlet integration method for position, a method that suppresses trajectory computational instabilities due to noisy position data was obtained. This combination of integration methods provides a means to extract the best estimate of drag force and drag coefficient under the non-ideal conditions of limited position data. This integration strategy leads immediately to the best possible estimate of object density, within the constraints of unknown particle shape. These types of calculations do not exist in readily available off-the-shelf simulation software, especially where photogrammetry data is needed as an input.

A previously developed mathematical model is amended to more accurately incorporate the effects of lift and drag on single dust particles in order to predict their behavior in the wake of high velocity gas flow. The model utilizes output from a CFD or DSMC simulation of exhaust from a rocket nozzle hot gas jet. An extension of the Saffman equation for lift based on the research of McLaughlin (1991) and Mei (1992) is used, while an equation for the Magnus force modeled after the work of Oesterle (1994) and Tsuji et al (1985) is applied. A relationship for drag utilizing a particle shape factor (phi = 0.8) is taken from the work of Haider and Levenspiel (1989) for application to non-spherical particle dynamics. The drag equation is further adjusted to account for rarefaction and compressibility effects in rarefied and high Mach number flows according to the work of Davies (1945) and Loth (2007) respectively. Simulations using a more accurate model with the correction factor (Epsilon = 0.8 in a 20% particle concentration gas flow) given by Richardson and Zaki (1954) and Rowe (1961) show that particles have lower ejection angles than those that were previously calculated. This is more prevalent in smaller particles, which are shown through velocity and trajectory comparison to be more influenced by the flow of the surrounding gas. It is shown that particles are more affected by minor changes to drag forces than larger adjustments to lift forces, demanding a closer analysis of the shape and behavior of lunar dust particles and the composition of the surrounding gas flow.

Parallelized versions of genetic algorithms (GAs) are popular primarily for three reasons: the GA is an inherently parallel algorithm, typical GA applications are very compute intensive, and powerful computing platforms, especially Beowulf-style computing clusters, are becoming more affordable and easier to implement. In addition, the low communication bandwidth required allows the use of inexpensive networking hardware such as standard office ethernet. In this paper we describe a parallel GA and its use in automated high-level circuit design. Genetic algorithms are a type of trial-and-error search technique that are guided by principles of Darwinian evolution. Just as the genetic material of two living organisms can intermix to produce offspring that are better adapted to their environment, GAs expose genetic material, frequently strings of 1s and Os, to the forces of artificial evolution: selection, mutation, recombination, etc. GAs start with a pool of randomly-generated candidate solutions which are then tested and scored with respect to their utility. Solutions are then bred by probabilistically selecting high quality parents and recombining their genetic representations to produce offspring solutions. Offspring are typically subjected to a small amount of random mutation. After a pool of offspring is produced, this process iterates until a satisfactory solution is found or an iteration limit is reached. Genetic algorithms have been applied to a wide variety of problems in many fields, including chemistry, biology, and many engineering disciplines. There are many styles of parallelism used in implementing parallel GAs. One such method is called the master-slave or processor farm approach. In this technique, slave nodes are used solely to compute fitness evaluations (the most time consuming part). The master processor collects fitness scores from the nodes and performs the genetic operators (selection, reproduction, variation, etc.). Because of dependency issues in the GA, it is possible to have idle processors. However, as long as the load at each processing node is similar, the processors are kept busy nearly all of the time. In applying GAs to circuit design, a suitable genetic representation 'is that of a circuit-construction program. We discuss one such circuit-construction programming language and show how evolution can generate useful analog circuit designs. This language has the desirable property that virtually all sets of combinations of primitives result in valid circuit graphs. Our system allows circuit size (number of devices), circuit topology, and device values to be evolved. Using a parallel genetic algorithm and circuit simulation software, we present experimental results as applied to three analog filter and two amplifier design tasks. For example, a figure shows an 85 dB amplifier design evolved by our system, and another figure shows the performance of that circuit (gain and frequency response). In all tasks, our system is able to generate circuits that achieve the target specifications.