3 October 2024 in ACM Computing Surveys
Machine learning plays a role in many deployed decision systems, often in ways that are difficult or impossible to understand by human stakeholders. Explaining, in a human-understandable way, the relationship between the input and output of machine learning models is essential to the development of trustworthy machine learning based systems. A burgeoning body of research seeks to define the goals and methods of explainability in machine learning. In this article, we seek to review and categorize research on counterfactual explanations , a specific class of explanation that provides a link between what could have happened had input to a model been changed in a particular way. Modern approaches to counterfactual explainability in machine learning draw connections to the established legal doctrine in many countries, making them appealing to fielded systems in high-impact areas such as finance and healthcare. Thus, we design a rubric with desirable properties of counterfactual explanation algorithms and comprehensively evaluate all currently proposed algorithms against that rubric. Our rubric provides easy comparison and comprehension of the advantages and disadvantages of different approaches and serves as an introduction to major research themes in this field. We also identify gaps and discuss promising research directions in the space of counterfactual explainability.
1 April 2019 in Management Science
Algorithmic matches in fielded kidney exchanges do not typically result in an actual transplant. We address the problem of cycles and chains in proposed matches failing after the matching algorithm has committed to them. We show that failure-aware kidney exchange can significantly increase the expected number of lives saved (i) in theory, on random graph models; (ii) on real data from kidney exchange match runs between 2010 and 2014; and (iii) on synthetic data generated via a model of dynamic kidney exchange. This gain is robust to uncertainty over the true underlying failure rate. We design a branch-and-price–based optimal clearing algorithm specifically for the probabilistic exchange clearing problem and show that this new solver scales well on large simulated data, unlike prior clearing algorithms. Finally, we show that failure-aware matching can increase overall system efficiency and simultaneously increase the expected number of transplants to highly sensitized patients, in both static and dynamic models. This paper was accepted by Yinyu Ye, optimization.
1 January 2020 in Operations Research
We study the stochastic matching problem with the goal of finding a maximum matching in a graph whose edges are unknown but can be accessed via queries. This is a special case of stochastic k-cycle packing, in which the problem is to find a maximum packing of cycles, each of which exists with some probability. We provide polynomial-time adaptive and nonadaptive algorithms that provably yield a near-optimal solution, using a number of edge queries that is linear in the number of vertices. We are especially interested in kidney exchange, with which pairs of patients with end-stage renal failure and their willing but incompatible donors participate in a mechanism that performs compatibility tests between patients and donors and swaps the donors of some patients so that a large number of patients receive compatible kidneys. Because of the significant cost of performing compatibility tests, currently, kidney exchange programs perform at most one compatibility test per patient. Our theoretical results applied to kidney exchange show that, by increasing the number of compatibility tests performed per patient from one to a larger constant, we effectively get the full benefit of exhaustive testing at a fraction of the cost. We show, on both generated and real data from the UNOS nationwide kidney exchange, that even a small number of nonadaptive edge queries per vertex results in large gains in expected successful matches.