# Constraint Inference in Control Tasks from Expert Demonstrations via Inverse
Optimization

Dimitris Papadimitriou and Jingqi Li The authors are with the University of
California, Berkeley. Correspondence to<EMAIL_ADDRESS>
###### Abstract

Inferring unknown constraints is a challenging and crucial problem in many
robotics applications. When only expert demonstrations are available, it
becomes essential to infer the unknown domain constraints to deploy additional
agents effectively. In this work, we propose an approach to infer affine
constraints in control tasks after observing expert demonstrations. We
formulate the constraint inference problem as an inverse optimization problem,
and we propose an alternating optimization scheme that infers the unknown
constraints by minimizing a KKT residual objective. We demonstrate the
effectiveness of our method in a number of simulations, and show that our
method can infer less conservative constraints than a recent baseline method
while maintaining comparable safety guarantees.

##  I Introduction

Specifying reward functions for Control and Reinforcement Learning (RL) tasks
is a nontrivial process. One approach to specify such reward functions is via
inverse Reinforcement Learning (IRL), in which expert demonstrations are used
to infer unknown reward functions [1, 2]. Once a reward function is obtained,
then a policy can be derived. Obtaining policies in constrained environments
via Control or RL is a fairly manageable task when those constraints are a
priori known. In many cases, specifying a reward function is intuitive. For
instance, a robot could use the inverse distance to its target destination as
a reward function. However, specifying the corresponding constraints for the
task at hand is not always straightforward.

One possible avenue to deal with learning policies under unknown constraints
is the use of Imitation Learning (IL) algorithms [3]. Simply imitating an
expert agent though, has a number of downsides. First, the inferred policy
applies only to the demonstrated task and may not be generalized to new ones.
Second, an inferred policy under a specific dynamics model is not guaranteed
to be applicable to an agent with different transition dynamics. On the other
hand, given the expert demonstrations, we could first infer the constraints
and then learn safe policies. The problem of constraint inference in RL is
mostly a new and active research area with a number of methods proposed so far
[4].

Constraint inference in control applications is an important problem that has
not been extensively studied [5]. Given the fact that most control tasks are
modeled as an optimization problem, elements from inverse optimization theory
can be utilized to infer constraints. In Inverse Optimization (IO), the
parameters of an optimization problem are inferred given access to its optimal
solution [6]. Although the majority of work revolves around inferring
parameters in the objective functions, a parallel to reward learning in RL,
research has recently focused on inferring constraint related parameters.

In this work, we propose a method for inferring constraints in control tasks,
based on expert demonstrations. Our contributions can be summarized as
follows: 1) We show that the unknown affine constraints can be recovered
exactly from the expert trajectory data, when we know the exact number of
unknown constraints and time instance of the constraint bindingness; 2) When
prior knowledge about the time instance of constraint binding is not
available, we develop a method to infer the unknown constraints, by minimizing
the KKT residual of the optimal control problem, which could be solved more
efficiently than prior works that rely on Mixed Integer Linear Programming
(MILP); 3) To deal with the challenge of not knowing the exact number of
unknown constraints, we develop a greedy algorithm which sequentially infers
an affine constraint such that the KKT residual is minimized. We empirically
demonstrated, that our method is robust to observation noise and suboptimal
demonstrations and it can infer less conservative constraints than a state-of-
the-art baseline method with same-level safety guarantees.

The rest of the paper is organized as follows. In Section II, we review the
relevant literature. In Section III, we formulate the constraint inference
problem. Our main results are presented in Section IV. In Section V, we
demonstrate the performance of our method in simulations.

##  II Related Work

This section outlines the existing work in constraint inference in RL and
Control. We also elaborate on relevant work from the IO literature as this is
particularly relevant to our framework.

Constraint Inverse Reinforcement Learning (CIRL): In the context of RL, [7]
proposed a greedy method to incrementally add constraints in discrete state
and actions spaces. This is done by assuming access to the reward function and
hence, the likelihood of each state or action being constrained can be
evaluated. At each iteration, the most likely state or action is classified as
a constraint following a maximum likelihood criterion. A continuous state
space framework is presented in [8] in which the authors propose a method to
learn a constraint classifier. Finally, in [9] the authors propose a Bayesian
approach to infer constraints. Estimating the full constraint posterior
distribution further allows for the quantification of estimation uncertainty.

Constraint Inference in Control: In the context of robotics, the authors in
[10] propose a method that infers constraints based on expert demonstrations
of a robot interacting with items. The inferred constraints are chosen from a
catalog of parametric constraint models so that under them, the robot
demonstrations are reproducible. In [11], cell occupancies of expert
demonstrations are calculated and later used in an integer programming
formulation, to provide estimates of the constraints. Constraints can also be
modeled in the form of control barrier functions. The authors in [12], use
expert demonstrations to learn control barrier functions that enjoy provable
safety guarantees.

Moreover, the authors in [13] infer parameters in the objective function
utilized to obtain control policies in constraint environments. However, it
should be noted that unknown parameters exist only in the objective function
and not in the constraints. The KKT optimality conditions of an optimization
problem can also be used to infer constraint sets. In [14], after candidate
constraint sets are constructed, the Lagrange multipliers of the IO problem
are used to infer constraints. The closest work to our framework is [5], in
which the authors use the KKT conditions to construct safe and unsafe areas of
the state-action space, and hence implicitly the constraints themselves.
Although this approach can also infer uncertainty in the objective function,
we choose to focus solely on the constraint recovery task.

Inverse Optimization: Inverse optimization, broadly refers to the problem of
inferring parameters of an optimization problem by observing the optimal
solution [6]. The majority of the work revolves around estimating parameters
in the objective function. For linear objective functions and constraints,
[15] formulate the inverse optimization problem also as a linear problem.
Regarding constraint inference, [16] infer the left-hand side of linear
constraints of a linear forward optimization problem. Finally, [17] provides a
convex formulation for inferring both the left and right-hand side of linear
constraints in linear optimization problems.

In our work, we base our constraint inference method, on minimizing the KKT
residual of the optimization problem.

KKT Residual and alternating optimization: In optimal control, the KKT
conditions are necessary conditions for the optimality of a sequence of states
and controls. Recent works [18, 19, 20, 21] proposed to minimize the residual
of the KKT conditions as a way to find the best cost function such that the
computed trajectory matches the expert demonstrations. The benefit of the KKT
residual formulation is that it could be convex if the cost function itself is
a convex function of the cost parameter [19, 22]. Moreover, the KKT residual
formulation can be extended to solve the inverse optimal control problem with
inequality constraints on states and controls [19].

##  III Problem Formulation

In this work, we are interested in providing a methodology to infer
constraints in constrained optimal control problems. We begin by formalizing
the classic forward control optimization problem as follows.

###### Definition 1

Consider a discrete-time dynamical system ${x}_{t+1}={f}({x_{t}},{u_{t}})$
where ${x_{t}}\in\mathbb{R}^{n}$ and ${u_{t}}\in\mathbb{R}^{m}$ represent the
state and control inputs at time $t\in\\{0,1,2,\dots\\}$, respectively. We
denote by $\mathbf{u}=\\{u_{0},\dots,u_{T-1}\\}$ and
$\mathbf{x}=\\{x_{0},x_{1},\dots,x_{T}\\}$ the control and state trajectories
from $t=0$ to $t=T$, respectively. For a control task with a quadratic cost
function $c({x},{u}):\mathbb{R}^{n}\times\mathbb{R}^{m}\to\mathbb{R}$,
terminal cost function $c_{T}({x}):\mathbb{R}^{n}\to\mathbb{R}$ and constraint
function $g_{\theta}(x):\mathbb{R}^{n}\to\mathbb{R}$, parameterized by a
vector $\theta\in\mathbb{R}^{d}$, we define the Forward Control Problem
FCP$({\theta})$ as follows,

$\displaystyle\text{{FCP}}(\theta):=\min_{\\{u_{t}\\}_{t=0}^{T-1}}$
$\displaystyle\sum_{t=0}^{T-1}c(x_{t},u_{t})+c_{T}(x_{T})$ (1) s.t.
$\displaystyle x_{t+1}=f(x_{t},u_{t}),t=0,\ldots,T-1$ $\displaystyle
g_{\theta}(x_{t})\leq 0,t=0,\ldots,T.$

In our work, we focus on state constraints, but our method can be easily
utilized for state-action constraints as well. Having access to the optimal
solution $\mathbf{u}^{*}:=\\{u_{t}^{*}\\}_{t=0}^{T-1}$ from the FCP we can
formulate the Inverse Control Problem (ICP) as an optimization problem that
provides an estimate of the unknown parameters, using a performance metric and
constraints that involve the optimal solution.

###### Definition 2

Given Definition 1, we define the Inverse Control Problem as
ICP($\mathbf{x}^{*},\mathbf{u}^{*}$)$\coloneqq\min_{{\theta}}$
$\\{\ell_{{\mathbf{x}^{*},\mathbf{u}^{*}}}(\theta)|{h}_{\mathbf{x}^{*},\mathbf{u}^{*}}(\theta)\leq{0}\\}$
that recovers the unknown constraint parameters ${\theta}$ via an
appropriately chosen loss function $\ell$ and constraints $h$, with
$\mathbf{x}^{*},\mathbf{u}^{*}$ denoting the optimal state and input solution
of FCP.

Given these definitions, we are interested in tackling the following problem.
Assume we are given a set of trajectories $\\{\tau_{i}\\}_{i=1}^{N}$, with
each $\tau_{i}=\\{x_{0},u_{0},x_{1},u_{1},$ $\dots,x_{T}\\}$. What objective
function $\ell$ and constraints $h$ should we use in an ICP formulation to
recover the unknown constraint parameters ${\theta}$ efficiently? The inferred
parameters $\hat{\theta}$ should be such that the induced optimal trajectories
are close to the expert demonstrations and feasible to the unknown
constraints.

###### Assumption 1

We assume that we have an expert data set composed by a number of expert state
and control input trajectories, which optimally solve the FCP$(\theta)$.

For the remainder of this work, we focus on the case of linear dynamics
functions and on finite horizon tasks. More specifically, we consider linear
dynamics of the form

$x_{t+1}=Ax_{t}+Bu_{t},$ (2)

where $x_{t}\in\mathbb{R}^{n}$ and $u_{t}\in\mathbb{R}^{m}$. Furthermore,
$A\in\mathbb{R}^{n\times n}$ and $B\in\mathbb{R}^{n\times m}$ are considered
known matrices. In what follows we elaborate on the formulation of the FCP and
ICP in the case of quadratic cost functions with linear constraints.

###  III-A Quadratic Objective and Linear Constraints

We consider control tasks of finite horizon $T$, with linear dynamics,
quadratic cost functions and $M$ distinct linear constraints of the following
form

$\displaystyle\min_{\\{u_{t}\\}_{t=0}^{t=T-1}}$
$\displaystyle\sum_{t=0}^{T-1}x_{t}^{\top}Qx_{t}+u_{t}^{\top}Ru_{t}+x_{T}^{\top}Qx_{T}$
s.t. $\displaystyle x_{t+1}=Ax_{t}+Bu_{t},\forall t\in\\{0,\dots,T-1\\}$ (3)
$\displaystyle c_{i}^{\top}x_{t}\leq d_{i},\forall
t\in\\{0,\dots,T\\},i\in\\{1,\ldots,M\\},$

where $Q$ and $R$ are cost matrices associated with states and control inputs,
respectively. Given that we are studying linear constraints, the unknown
parameters $\theta$ we are interested in inferring are the
$c_{i}\in\mathbb{R}^{n}$ and $d_{i}\in\mathbb{R}$ that parameterize the $i$-th
constraint, with $i\in\\{1,2,\dots,M\\}$. Let $x_{0}$ be the initial condition
and $U=[u_{0},u_{1}\dots,u_{T-1}]\in\mathbb{R}^{mT}$ be the compact
representation of the control input sequence. The problem can be rewritten in
a compact way as

$\displaystyle\min_{U\in\mathbb{R}^{mT}}$
$\displaystyle(GU+Hx_{0})^{\top}(I_{T}\otimes Q)(GU+Hx_{0})$
$\displaystyle+U^{\top}(I_{T}\otimes R)U$ s.t.
$\displaystyle\;C(GU+Hx_{0})\leq D,$ (4)

where $G\in\mathbb{R}^{nT\times mT}$, $H\in\mathbb{R}^{nT\times n}$,
$C\in\mathbb{R}^{MT\times nT}$ and $D\in\mathbb{R}^{MT}$ are defined as
follows

$\displaystyle G=\begin{bmatrix}B&0&0&\cdots&0\\\ AB&B&0&\cdots&0\\\
\vdots&\vdots&\vdots&\ddots&\vdots\\\
A^{T-1}B&A^{T-2}B&A^{T-3}B&\cdots&B\end{bmatrix},H=\begin{bmatrix}A\\\
A^{2}\\\ \vdots\\\ A^{T}\end{bmatrix},$ $\displaystyle
C=\begin{bmatrix}I_{T}\otimes c_{1}^{\top}\\\ \vdots\\\ I_{T}\otimes
c_{M}^{\top}\end{bmatrix},\ \ D=\begin{bmatrix}\mathbf{1}_{T}d_{1}\\\
\vdots\\\ \mathbf{1}_{T}d_{M}\end{bmatrix},$ (5)

with $I_{n}$ denoting the identify matrix and $\mathbf{1}_{n}$ a vector of
ones, both of size $n$. We use for simplicity $0$ in matrix definitions to
denote all zero matrices of appropriate dimensions.

##  IV Constraint Inference

This section introduces the constraint recovery approach using the inverse
problem formulation. Initially, we present conditions for exact constraint
recovery. Afterwards, we proceed to deriving a more general approach for
constraint inference based on the KKT optimality conditions.

###  IV-A Exact Constraint Recovery

Under certain assumptions, exact constraint inference is possible by solving a
linear system of equations. This is possible in the case where the exact
number of constraints and the states for which the constraints are binding are
known a priori. First, we present conditions under which constraint inference
can be exact in the case where the right-hand side of the constraints
$d_{i},i=1,\ldots,M$ is known. Afterwards, we extend these conditions to the
case where the right-hand side is also unknown, a setup that will be kept for
the remainder of the paper.

###### Proposition 1

Assume the existence of $M$ total linear unknown constraints with known right-
hand sides $d_{i},i=1,\ldots,M$ and that for each constraint $i=1,\ldots,M$
there are $n_{i}$, with $T>n_{i}\geq n$, states for which the constraint is
binding at time steps $\mathcal{T}_{i}$, where
$\mathcal{T}_{i}=\\{t|c_{i}^{\top}x_{t}=d_{i}\\}$. If, for each constraint,
$n$ of these state vectors are linearly independent, then the constraint
vector $c_{i}$ can be recovered exactly, for $i=1,\ldots,M$.

###### Proof:

For each of the constraints $i$ we select $n$ of the $n_{i}$ states for which
the constraint is binding. Then the following holds

$\displaystyle C_{\mathcal{T}_{i}}\cdot
X_{\mathcal{T}_{i}}=D_{\mathcal{T}_{i}},$ (6)

where

$\displaystyle C_{\mathcal{T}_{i}}=\begin{bmatrix}{I}_{n}\otimes
c^{\top}_{i}\end{bmatrix},X_{\mathcal{T}_{i}}=\begin{bmatrix}x_{t_{i,1}}\\\
\vdots\\\
x_{t_{i,n}}\end{bmatrix},t_{i,1},\ldots,t_{i,n}\in\mathcal{T}_{i}\text{ and }$
$\displaystyle
D_{\mathcal{T}_{i}}=\begin{bmatrix}\mathbf{1}_{n}d_{i}\end{bmatrix}.$ (7)

Rearranging (6) we obtain

$\displaystyle\tilde{X}_{\mathcal{T}_{i}}\cdot c_{i}=D_{\mathcal{T}_{i}},$ (8)

where

$\displaystyle\tilde{X}_{\mathcal{T}_{i}}=\begin{bmatrix}x_{t_{i,1}}^{\top}\\\
\vdots\\\ x^{\top}_{t_{i,n}}\end{bmatrix}.$ (9)

Since $\tilde{X}_{\mathcal{T}_{i}}$ is full row rank given the linear
independence of $x_{t_{i,j}},j=1,\ldots,n$, $c_{i}$ can be recovered exactly.
The non-binding states can be used to determine the sign of the constraint
inequality. ∎

For the remainder of the paper we will regard the right-hand side of the
constraints unknown as well. To deal with the unknown right-hand side
parameter $d_{i}$, $i\in\\{1,\dots,M\\}$, we expand the state dimension by one
element that corresponds to the right-hand side of the constraints to simplify
notation. More specifically, $x_{t}:=[x_{t},1]\in\mathbb{R}^{n+1}$ and

$\displaystyle A:=\begin{bmatrix}A&0\\\
0&1\end{bmatrix},B:=\begin{bmatrix}B\\\ 0\end{bmatrix}.$ (10)

Now each constraint can be compactly written as $c_{i}^{\top}x_{t}\leq 0$
where $c_{i}^{\top}:=[c_{i}^{\top},-d_{i}]\in\mathbb{R}^{n+1}$. Exact
constraint inference in this case can occur in a similar way to Proposition 1
and under the same assumptions. More specifically, the right-hand-side of the
constraints can be set equal to an arbitrary value and the inferred
constraints will be inferred up to scale. The above result suggests that, we
can infer the exact constraints under the strong assumptions that we know the
total number of constraints and the time instance of the bindingness. In this
work, we are primarily interested in providing a framework for constraint
inference in challenging scenaria in which the actual number of constraints
and the time steps at which the constraints are binding, if at all, are
unknown. To solve this challenging problem, we utilize the following KKT
residual objective formulation, which is a general framework that allows for
constraint inference in the most general settings.

###  IV-B General Constraint Inference via KKT Residual

In this section we focus on the case where the actual number of constraints
$M$ is known a priori. We will be extending our approach to the case where $M$
is unknown in section IV-D. The optimization problem in (III-A) admits the
following Lagrangian

$\displaystyle L(U,\lambda):=(GU+Hx_{0})^{\top}(I_{T}\otimes Q)(GU+Hx_{0})$
$\displaystyle+U^{\top}(I_{T}\otimes R)U+\lambda^{\top}C(GU+Hx_{0}),$ (11)

with $\lambda\in\mathbb{R}_{+}^{MT}$ denoting the vector of Lagrange
multipliers. The KKT conditions of stationarity, complementary slackness,
primal and dual feasibility are then

$\displaystyle\nabla_{U}L(U^{*},\lambda)=2G^{\top}(I_{T}\otimes
Q)(GU^{*}+Hx_{0})+$ $\displaystyle 2(I_{T}\otimes
R)U^{*}+G^{\top}C^{\top}\lambda=0$ (12)
$\displaystyle\lambda^{\top}C(GU^{*}+Hx_{0})=0$ (13) $\displaystyle
C(GU^{*}+Hx_{0})\leq 0$ (14) $\displaystyle\lambda\geq 0.$ (15)

The KKT residual formulation obtains estimates of the unknown parameters, in
our case $c_{i}$s, $i=1,\ldots,M$ and $\lambda$, by minimizing some metric of
the stationarity and complementary slackness conditions, while satisfying
primal and dual feasibility. More specifically,

$\displaystyle\min_{\\{c_{i}\\}_{i=1}^{i=M},\lambda}$
$\displaystyle\;\ell(\\{c_{i}\\}_{i=1}^{i=M},\lambda)$ (16) s.t.
$\displaystyle\;C_{\\{c_{i}\\}_{i=1}^{M}}A_{2}\leq 0$
$\displaystyle\lambda\geq 0,$

where for conciseness we define

$\displaystyle\ell(\\{c_{i}\\}_{i=1}^{i=M},\lambda)=\|A_{1}+G^{\top}C_{\\{c_{i}\\}_{i=1}^{M}}^{\top}\lambda\|_{2}^{2}$
$\displaystyle+\|(C_{\\{c_{i}\\}_{i=1}^{M}}A_{2})^{\top}\lambda\|_{2}^{2}+\rho_{1}\sum_{i=1}^{M}\|c_{i}\|_{2}^{2}+\rho_{2}\|\lambda\|_{2}^{2}$
(17) $\displaystyle A_{1}=2G^{\top}(I_{T}\otimes
Q)(GU^{*}+Hx_{0})+2(I_{T}\otimes R)U^{*}$ (18) $\displaystyle
A_{2}=GU^{*}+Hx_{0}.$ (19)

Given that the constraints $c_{i}$ are now unknown, we use the notation
$C_{\\{c_{i}\\}_{i=1}^{M}}$ to denote the function that maps the $c_{i}$s as
follows

$\displaystyle C_{\\{c_{i}\\}_{i=1}^{M}}:=\begin{bmatrix}I_{T}\otimes
c_{1}^{\top}\\\ \vdots\\\ I_{T}\otimes c_{M}^{\top}\end{bmatrix}.$ (20)

It should be noted that this is a biconvex optimization problem in
$c_{i},{i=1,\ldots,M}$ and $\lambda$ [23]. The most common approach for
solving biconvex optimization problems, is via an alternating optimization
scheme, which we outline in the following section.

###  IV-C Alternating Optimization Formulation

Observing Problem (16), it is evident that by fixing one of the variables the
problem becomes a constrained least squares problem with respect to the other
variable. Without loss of generality, in this section, we focus on the case
where $M=1$ with the only constraint being $c$. More specifically, by fixing
$c$ Problem (16) becomes

$\displaystyle\min_{\lambda}\;\|\tilde{A}\lambda-\tilde{b}\|_{2}^{2}+\rho_{2}\|\lambda\|_{2}^{2}$
(21) $\displaystyle\textrm{s.t.}\;\lambda\geq{{0}},$

where

$\displaystyle\tilde{A}=\begin{bmatrix}G^{\top}C_{\\{c\\}}^{\top}\\\
(C_{\\{c\\}}A_{2})^{\top}\end{bmatrix},\tilde{b}=\begin{bmatrix}-A_{1}\\\
0\end{bmatrix}\text{ and }C_{\\{c\\}}=[I_{T}\otimes c].$

On the other hand, when minimizing over $c$, Problem (16) can be rewritten as

$\displaystyle\min_{c}\;\|\tilde{\tilde{A}}c-\tilde{\tilde{b}}\|_{2}^{2}+\rho_{1}||c||_{2}^{2}$
(22) $\displaystyle\textrm{s.t. }\;C_{\\{c\\}}A_{2}\leq{0},$

where

$\displaystyle\tilde{\tilde{A}}=\begin{bmatrix}G^{\top}\Lambda\\\
A_{2}^{\top}\Lambda\end{bmatrix},\tilde{\tilde{b}}=\begin{bmatrix}-A_{1}\\\
0\end{bmatrix},$

and ${\Lambda}$ is a constructed sparse matrix with elements the coordinates
of $\lambda$, such that $C_{\\{c\\}}^{\top}\lambda={\Lambda}c$. The
reformulation using matrix $\Lambda$ is solely done to show that Problem 22 is
indeed a least squares problem on $c$.

Problems (21) and (22) included in the objective function a regularization
term to ensure a unique solution. The detailed process of the alternating
optimization approach can be seen in Algorithm 1. For a number of $K$
iterations, we solve Problems (21) and (22) in an alternating way.

Algorithm 1 Alternating Minimization Algorithm

1:Initialize randomly: $c\in\mathbb{R}^{n+1}$

2:for $K=1,\ldots$ do

3: Solve Problem (21)

4: Update $\lambda$ value

5: Solve Problem (22)

6: Update $c$ value

7:end for

8:Output: $c,\lambda$

###### Theorem 1

Algorithm 1 converges to a stationary point of (16).

###### Proof:

For the theorem to hold, Problem (21) and Problem (22) must have unique
solutions [24]. Problem (21) is a regularized constrained least squares
problem in which the objective function is strictly convex. Thus, Problem (21)
admits an unique solution. Similarly, Problem (22) also admits a unique
solution due to strong convexity. Convergence then follows from Proposition
2.7.1 in [24]. The result is shown for the case when we infer only one
constraint because, as it will become clear is subsequent sections, we utilize
Algorithm 1 to infer one constraint at a time. ∎

###  IV-D Greedy Constraint Inference

The previous sections, have tackled the scenario of unknown constraints with
an a priori known number of constraints in the environment. However, in
realistic scenaria, such cases are rare and thus we need a heuristic approach
that infers constraints when their number is unknown. In that direction, we
propose using the KKT residual objective as an estimate of the quality of
constraint inference. In what follows, we propose a greedy constraint
inference algorithm, that incrementally adds constraints until a certain
criterion is met.

The Incremental Greedy Constraint Inference (IGCI) approach, shown in
Algorithm 2, utilizes at each iteration Algorithm 1 to incrementally add a
constraint in the set of inferred constraints. The method starts with an empty
set of constraints $\mathcal{C}$. After a constraint $c_{i}$ and the Lagrange
multiplier have been inferred following Algorithm 1, the constraint is
temporarily added to the constraint set $\mathcal{C}$. Then the KKT residual
objective $\ell(\\{c_{i}\\}_{c_{i}\in\mathcal{C}},\lambda)$ is evaluated. If
the difference between this value and the KKT residual in the previous
iteration, which is denoted with $E$ in Algorithm 2, is above a user-specified
threshold $\delta$, then the constraint $c_{i}$ remains in the constraint set.
The process is repeated until this difference drops below the predefined
threshold at which point the process terminates, without including the last
inferred constraint in $\mathcal{C}$.

Algorithm 2 IGCI

1:Parameters: Convergence threshold $\delta$, $E$$>\\!\\!>$$1$

2:Initialize: $\mathcal{C}^{\prime}=\\{\\}$

3:for $N_{c}=1,\ldots$ do

4: Obtain $c_{N_{c}}\in\mathbb{R}^{n+1}$ and $\lambda\in\mathbb{R}^{N_{c}T}$
from Algorithm 1

5: $\mathcal{C}^{\prime}\leftarrow\mathcal{C}^{\prime}\cup\\{c_{N_{c}}\\}$

6: $\lambda^{\prime}\leftarrow\lambda$

7: if
$|\ell(\\{c\\}_{c\in\mathcal{C}^{\prime}},\lambda^{\prime})-E|\leq\delta$ then

8: break

9: else

10:
$\mathcal{C}\leftarrow\mathcal{C}^{\prime},\;\lambda\leftarrow\lambda^{\prime}$

11: $E\leftarrow\ell(\\{c\\}_{c\in\mathcal{C}},\lambda)$

12: end if

13:end for

14:Output: $\mathcal{C},\lambda$

When the algorithm terminates, the set of $N_{c}$ inferred constraints
$\mathcal{C}=\\{\tilde{c}_{1},\ldots,\tilde{c}_{N_{c}}\\}$ is returned. It
should be noted that $N_{c}$ need not be equal to the original number of
constraints $M$. Furthermore, IGCI will add at least one constraint given that
the criterion in line $7$ will not be satisfied in the first iteration. This
can be modified if needed, by appropriately choosing a smaller initial value
for $E$.

At an arbitrary iteration $k$ of IGCI, in line $4$ we obtain the estimate for
an additional constraint and Lagrange multiplier. This is achieved by solving
(16) using Algorithm 1 with the unknowns being $c_{k}$ and the multiplier
$\lambda\in\mathbb{R}^{kT}$, while fixing the values of the already inferred
constraints, $\tilde{c}_{i},\;i=1,\ldots,k-1$. Although further fixing the
already inferred Lagrange multipliers and only inferring an additional
$\lambda\in\mathbb{R}^{T}$ at each iteration works well, our simulations
showed that inferring at iteration $k$ the Lagrange multipliers for all
constraints $i=1,\ldots,k$ gives slightly more accurate results.

Finally, the analysis so far has been based on a single optimal demonstration
$U^{*}$. In subsequent sections, we allow for inference from multiple
demonstrations by modifying $\tilde{A},\tilde{b},\tilde{\tilde{A}}$ and
$\tilde{\tilde{b}}$ in problems (21) and (22) appropriately. More
specifically, for $N$ demonstrations $U^{*}_{1},\ldots,U^{*}_{N}$ and by
denoting

$\displaystyle A_{1}^{(i)}=2G^{\top}(I_{T}\otimes
Q)(GU_{i}^{*}+Hx_{0})+2(I_{T}\otimes R)U_{i}^{*}$ (23) $\displaystyle
A_{2}^{(i)}=GU_{i}^{*}+Hx_{0},$ (24)

the new $\tilde{A}$ and $\tilde{b}$ for Problem 21 now become

$\displaystyle\tilde{A}=\begin{bmatrix}G^{\top}C_{\\{c\\}}^{\top}\\\
(C_{\\{c\\}}A^{(1)}_{2})^{\top}\\\ \vdots\\\ G^{\top}C_{\\{c\\}}^{\top}\\\
(C_{\\{c\\}}A^{(N)}_{2})^{\top}\end{bmatrix},\tilde{b}=\begin{bmatrix}-A_{1}^{(1)}\\\
0\\\ \vdots\\\ -A_{1}^{(N)}\\\ 0\end{bmatrix}.$

The definitions for $\tilde{\tilde{A}}$ and $\tilde{\tilde{b}}$ are analogous.

Although each additional demonstration should be associated with a distinct
Lagrange multiplier, in order to reduce the dimensionality of the problem, for
each constraint we associate a single Lagrange multiplier with all
trajectories. This allows our formulation to be implemented efficiently even
in the presence of a large number of demonstrations. This simplification was
shown in practice to not affect the results significantly.

##  V Simulations

In this section, we carry out simulations to quantify the performance of IGCI.
We utilize a two dimensional navigation task and a robotic arm environment and
consider scenaria of perfect and noisy state observations, as well as
suboptimal trajectories. To evaluate the quality of the inferred constraints,
we utilize a number of metrics. First, in a similar fashion to [5] we report
the coverage of the actual safe region and the overlap with the unsafe one.
More specifically, we define the constrained and unconstrained regions as

$\displaystyle\mathcal{A}$
$\displaystyle=\bigcup_{i=1,\ldots,M}\\{x|c_{i}^{\top}x>0\\}$ (25)
$\displaystyle\mathcal{A}^{c}$
$\displaystyle=\bigcap_{i=1,\ldots,M}\\{x|c_{i}^{\top}x\leq 0\\},$ (26)

respectively. The corresponding regions constructed using the estimated
parameters $\tilde{c}_{i},i=1,\ldots,N_{c}$ are designated with
$\tilde{\mathcal{A}}$ and $\tilde{\mathcal{A}}^{c}$, respectively. We now
define the coverage of the unconstrained set as
$\frac{Vol(\tilde{\mathcal{A}^{c}}\cap\mathcal{A}^{c})}{Vol(\mathcal{A}^{c})}$
and the overlap of the inferred unconstrained and the actual constrained sets
as
$\frac{Vol(\tilde{\mathcal{A}^{c}}\setminus\mathcal{A}^{c})}{Vol(\mathcal{A})}$.
These metrics can be seen as analogous to the True Positive (TP) and False
Positive (FP) classification rates, respectively.

###  V-A 2D Navigation Task

In this set of simulations we study a two dimensional linear system with
$x_{t}\in\mathbb{R}^{2},u_{t}\in\mathbb{R}$, dynamics matrices

$\displaystyle A=\begin{bmatrix}0.8&0.1\\\
0.1&0.8\end{bmatrix},B=\begin{bmatrix}0.1\\\ 0.5\end{bmatrix},$ (27)

and quadratic cost matrices $Q=100\cdot I_{2}$ and $R=0.1$. The goal of the
controller is to stay close to a predetermined trajectory $x_{track}$, listed
in Appendix -A, for the duration of the task. We evaluate Algorithm 1 in an
environment with two linear state constraints, shown in Figures 1,2. The
control task has a horizon $T=8$ and the starting states are normally
distributed around $[-5.5,-0.5]$ with $\sigma=0.05$. We consider two cases,
one with perfect and one with imperfect state observations. In all
simulations, we vary the number of expert demonstrations $N$, in order to
quantify its impact on inference. IGCI is terminated after $2$ iterations as
for subsequent iterations the KKT cost function, as seen in Figure 7(a), no
longer significantly decreases. For all simulations in this section, we
followed the elbow rule for the termination of the algorithm, without
explicitly choosing a threshold $\delta$. For each experiment, we carry out
$10$ independent simulations with newly obtained expert demonstrations. The
classification results and convergence rates are averaged over those
simulations.

We first investigate constraint inference under perfect state observations. In
Figure 1, we plot the expert demonstrations along with the actual and
estimated constraint regions, for $N=1$ and $N=10$. We denote with $OC$ and
$OCR$ the original affine constraint and corresponding region, respectively.
$EC$ and $ECR$ designate the estimated affine constraint and constraint
regions. For $N=1$, we showcase one of the $10$ simulations in which inference
for one of the constraints was inaccurate.

(a) $N=1.$

(b) $N=10.$

Figure 1: Examples of original and estimated constrained regions for $N=1$
(Fig. 1(a)) and $N=10$ (Fig. 1(b)) along with expert demonstrations under
perfect state observations.

In the case of noisy state observations, we assume that each demonstration $i$
is polluted with observation noise as follows

$\displaystyle\tau_{i}=\\{x_{0},u_{0},x_{1}+\epsilon,u_{1},x_{2}+\epsilon,\dots,u_{T-1},x_{T}+\epsilon\\},$
(28)

with $\epsilon\sim\mathcal{N}(0,0.005)$. In Figure 2 we plot the original
constraints along with an instance of the inferred ones for $N=1$ and $N=10$,
respectively. Clearly, for both perfect and noisy state observations, a larger
number of demonstrations leads to more accurate inference. Figure 3 contains
the TP and FP rates, as discussed in the next section.

(a) $N=1.$

(b) $N=10.$

Figure 2: Examples of original and estimated constrained regions for $N=1$
(Fig. 2(a)) and $N=10$ (Fig. 2(b)) along with expert demonstrations under
noisy state observations.

###  V-B Baseline Comparison

To emphasize the benefits of inferring constraint parameters and not just
safe/unsafe regions, we compare IGCI with the inference method presented in
[5]. The latter, infers regions of the state space that are deemed constrained
or unconstrained. We solve Problem 5 from [5] in order to obtain an estimate
of the unconstrained region for our two dimensional navigation task, in the
cases of perfect and imperfect state observations. We utilize $10$ different
query points to obtain the estimate of the unconstrained set.

Figure 3: Classification rates for IGCI and baseline under perfect and noisy
state observations. Results averaged over $10$ simulations. When $N=10$, our
method has significantly higher true positive rate than the baseline method
while maintaining same-level of false positive rates.

Evaluation of the algorithms is carried out using the TP and FP classification
rates.

The results for both the noiseless and noisy state observations are given in
Figure 3. Increasing the number of available trajectories naturally leads to
better estimation, which by itself allows for safer policies. The baseline
method, which we only implemented in the more favorable case of $N=10$
demonstrations, only manages to recognize rectangular areas around the
trajectories and hence fails to identify the majority of the unconstrained
regions “to the right” of the demonstrations. On the other hand, our approach
manages to infer the majority of the unconstrained region while having a false
positive rate similar to the more conservative baseline. It should be
stressed, that our method returns the full parameterization of the constraints
and hence a new forward optimization problem is still convex. On the other
hand, the baseline method infers rectangular regions, the union of which need
not be a convex set, hence, requiring more complex techniques for novel
forward problems in the inferred domain. Finally, the baseline method requires
the solution either of a nonlinear program or a MILP, which are significantly
more inefficient when compared to our alternating approach.

###  V-C 3D Manipulation Task with Suboptimal Demonstrations

In this section, we utilize the FetchReach robotic simulation [25] which is
designed to complete tasks, like pushing and grabbing objects, in three
dimensional environments. The control inputs are the desired displacement of
the robot gripper in the $x,y$ and $z$ coordinates,
$x_{t}\in\mathbb{R}^{3},u_{t}\in\mathbb{R}^{3}$. We assume that the nominal
dynamics matrices, the ones the robot theoretically adheres to, are
$A={I}_{3}$ and $B={I}_{3}$ and the quadratic cost matrices are
$Q=10\cdot{I}_{3}$ and $R=10\cdot{I}_{3}$.

It should be noted that the nominal dynamics are a simplification of the
actual dynamics, as the underlying physics engine is far more complicated and
for a particular control input the arm gripper will not land in the predicted
state by our nominal model but at a state in the proximity of the former. For
this reason, we study two cases, one with nominal trajectories and one with
the actual robot trajectories. To obtain the latter, after obtaining an
optimal trajectory by solving (III-A) using the nominal dynamics, we utilize a
closed loop controller between optimal waypoints to guide the gripper close to
the nominal states (robot states). The controller is run for $5$ iterations
for each waypoint and its action is determined by the difference between its
current state and the waypoint. Clearly, these trajectories, shown in Figure
4(b), are no longer optimal according to (III-A).

The control task is for the robotic gripper to stay close to a tracking
trajectory, which can be found in Appendix -A, over a horizon of $T=8$. The
ground truth underlying constraints, schematically pictured in Figure 4(a),
are $x\geq 0.9$ and $y\leq 1.1$, which can also be written as
$c_{i}^{\top}x\leq 0,\;i=1,2$ with $c_{1}=[0,1,0,-1.1]^{\top}$ and
$c_{2}=[-1,0,0,0.9]^{\top}$. The boundaries of the entire domain are
$x\in[0.4,1.4],y\in[0.4,1.4]$ and $z\in[0.4,1.4]$. We gather $N=1$ and $N=10$
expert trajectories with the starting states being normally distributed around
$[1,1,0.8]$ with $\sigma=0.05$.

(a) FetchReach robot.

(b) $N=10$ trajectories.

Figure 4: (4(a)) FetchReach robot along with constraints (red, green). (4(b))
Nominal and corresponding actual robot trajectories instance for $N=10$.

Figure 4(b) shows $N=10$ trajectories in which the green points correspond to
the nominal trajectories and the red ones are the actual robot states. We
infer the constraints by using both the nominal and the suboptimal
demonstrations, in order to quantify the performance of our method in view of
suboptimality. We run IGCI for $10$ independent simulations and we report the
average classification rates in Figure 5. Clearly, estimation is effective
even by utilizing a single expert demonstration.

Figure 5: Classification rates for nominal and robot trajectories. The robot
trajectories are considered to be suboptimal, because of the model discrepancy
between the nominal dynamics and the real robot dynamics in the FetchReach
simulation environment [25]. Results are averaged over $10$ independent
simulations. Our method is still effective even when the trajectories are
suboptimal.

In Figure 6 we plot the actual and the inferred constraints as obtained for
$N=10$ nominal trajectories. Figure 7(b) displays the convergence rate of the
KKT residual objective with respect to the number of iterations. As expected,
for optimal demonstrations the KKT cost function is lower than the
corresponding for noisy or suboptimal demonstrations.

Figure 6: Nominal trajectories ($N=5$) along with actual and inferred
constraints. The inferred constraints align well with the actual constraints.

(a)

(b)

Figure 7: KKT residual cost function, normalized by the number of
trajectories, with respect to iterations for the 2D navigation task (Fig.
7(a)) and 3D manipulation task (Fig. 7(b)). Results averaged over $10$
simulations. When the expert trajectories are optimal but subject to noise,
having more trajectories could lead to a lower KKT cost, as shown in Fig.
7(a). However, when the expert trajectories are suboptimal, having more
trajectory data may not necessarily lead to a lower KKT cost, as illustrated
in Fig. 7(b).

##  VI Conclusion and Future Extensions

In this work, we presented a method that infers constraints in control tasks
after observing expert demonstrations. We showed conditions under which exact
recovery is possible. We proposed to learn the unknown constraints by
minimizing the KKT residual objective function. We further introduced IGCI, an
algorithm that can be utilized to infer constraints in cases where no
information, except for their parametric representation, is available. We
evaluated the performance of IGCI in a number of simulations, in which we
showed that the inferred constraints can be accurate without jeopardizing
safety under perfect, noisy and suboptimal observations.

The alternating minimization procedure presented in this paper is flexible
enough to handle more complicated constraints that can be modeled as unions
and intersections of half-spaces. However, we believe that exploring specific
classes of constraint functions for which efficient solutions and safety
guarantees can be obtained, is an interesting future research direction.

## References

  * [1] A. Y. Ng, S. Russell _et al._ , “Algorithms for inverse reinforcement learning.” in _Icml_ , vol. 1, 2000, p. 2.
  * [2] D. Ramachandran and E. Amir, “Bayesian inverse reinforcement learning.” in _IJCAI_ , vol. 7, 2007, pp. 2586–2591.
  * [3] A. Hussein, M. M. Gaber, E. Elyan, and C. Jayne, “Imitation learning: A survey of learning methods,” _ACM Computing Surveys (CSUR)_ , vol. 50, no. 2, pp. 1–35, 2017.
  * [4] G. Liu, Y. Luo, A. Gaurav, K. Rezaee, and P. Poupart, “Benchmarking constraint inference in inverse reinforcement learning,” _arXiv preprint arXiv:2206.09670_ , 2022.
  * [5] G. Chou, N. Ozay, and D. Berenson, “Learning constraints from locally-optimal demonstrations under cost function uncertainty,” _IEEE Robotics and Automation Letters_ , vol. 5, no. 2, pp. 3682–3690, 2020.
  * [6] T. C. Chan, R. Mahmood, and I. Y. Zhu, “Inverse optimization: Theory and applications,” _arXiv preprint arXiv:2109.03920_ , 2021.
  * [7] D. R. Scobee and S. S. Sastry, “Maximum likelihood constraint inference for inverse reinforcement learning,” _arXiv preprint arXiv:1909.05477_ , 2019\.
  * [8] S. Malik, U. Anwar, A. Aghasi, and A. Ahmed, “Inverse constrained reinforcement learning,” in _International Conference on Machine Learning_. PMLR, 2021, pp. 7390–7399.
  * [9] D. Papadimitriou, U. Anwar, and D. S. Brown, “Bayesian methods for constraint inference in reinforcement learning,” _Transactions on Machine Learning Research_.
  * [10] C. Pérez-D’Arpino and J. A. Shah, “C-learn: Learning geometric constraints from demonstrations for multi-step manipulation in shared autonomy,” in _2017 IEEE International Conference on Robotics and Automation (ICRA)_. IEEE, 2017, pp. 4058–4065.
  * [11] G. Chou, D. Berenson, and N. Ozay, “Learning constraints from demonstrations,” in _International Workshop on the Algorithmic Foundations of Robotics_. Springer, 2018, pp. 228–245.
  * [12] A. Robey, H. Hu, L. Lindemann, H. Zhang, D. V. Dimarogonas, S. Tu, and N. Matni, “Learning control barrier functions from expert demonstrations,” in _2020 59th IEEE Conference on Decision and Control (CDC)_. IEEE, 2020, pp. 3717–3724.
  * [13] T. L. Molloy, J. J. Ford, and T. Perez, “Online inverse optimal control for control-constrained discrete-time systems on finite and infinite horizons,” _Automatica_ , vol. 120, p. 109109, 2020.
  * [14] M. Menner, P. Worsnop, and M. N. Zeilinger, “Constrained inverse optimal control with application to a human manipulation task,” _IEEE Transactions on Control Systems Technology_ , vol. 29, no. 2, pp. 826–834, 2019\.
  * [15] R. K. Ahuja and J. B. Orlin, “Inverse optimization,” _Operations Research_ , vol. 49, no. 5, pp. 771–783, 2001.
  * [16] T. C. Chan and N. Kaw, “Inverse optimization for the recovery of constraint parameters,” _European Journal of Operational Research_ , vol. 282, no. 2, pp. 415–427, 2020.
  * [17] K. Ghobadi and H. Mahmoudzadeh, “Inferring linear feasible regions using inverse optimization,” _European Journal of Operational Research_ , vol. 290, no. 3, pp. 829–843, 2021.
  * [18] S. Levine and V. Koltun, “Continuous inverse optimal control with locally optimal examples,” _arXiv preprint arXiv:1206.4617_ , 2012.
  * [19] P. Englert, N. A. Vien, and M. Toussaint, “Inverse kkt: Learning cost functions of manipulation tasks from demonstrations,” _The International Journal of Robotics Research_ , vol. 36, no. 13-14, pp. 1474–1488, 2017.
  * [20] C. Awasthi, “Forward and inverse methods in optimal control and dynamic game theory,” Ph.D. dissertation, University of Minnesota, 2019.
  * [21] M. Menner and M. N. Zeilinger, “Maximum likelihood methods for inverse learning of optimal controllers,” _IFAC-PapersOnLine_ , vol. 53, no. 2, pp. 5266–5272, 2020.
  * [22] A. Keshavarz, Y. Wang, and S. Boyd, “Imputing a convex objective function,” in _2011 IEEE international symposium on intelligent control_. IEEE, 2011, pp. 613–619.
  * [23] J. Gorski, F. Pfeuffer, and K. Klamroth, “Biconvex sets and optimization with biconvex functions: a survey and extensions,” _Mathematical methods of operations research_ , vol. 66, no. 3, pp. 373–407, 2007.
  * [24] D. P. Bertsekas, “Nonlinear programming,” _Journal of the Operational Research Society_ , vol. 48, no. 3, pp. 334–334, 1997.
  * [25] R. de Lazcano, K. Andreas, J. J. Tai, S. R. Lee, and J. Terry, “Gymnasium robotics,” 2023. [Online]. Available: http://github.com/Farama-Foundation/Gymnasium-Robotics

###  -A Simulation Details

Although IGCI is not very sensitive in the choice of $\rho_{1},\rho_{2}$, in
all simulations we use $\rho_{1}=10$ and $\rho_{2}=0$. 2D Navigation Task: The
starting states are normally centered around $x_{0}=[-0.5,-5.5]$ with variance
$\sigma=0.05$. The tracking trajectory is
$x_{track}=[0.,-5.5;-0.6,-4.5;-1.5,-3.8;-1.5,-3.5;-1.6,-2.5;\\\
-0.2,-2;0.5,-2;0.8,-1.5]$. Gym Environment: The starting states are normally
centered around $x_{0}=[1,1,0.8]$ with variance $\sigma=0.05$. The tracking
trajectory is
$x_{track}=[0.95,1,0.8;0.9,1,0.8;0.85,1,0.8;0.8,1.1,0.9;0.9,1.15,\\\
0.9;0.95,1.2,0.9;1,1.25,0.9;1.1,1.3,0.9]$.


# Analyzing the Influence of Training Samples on Explanations

André Artelt1,2&Barbara Hammer1
1Bielefeld University, Bielefeld, Germany
2University of Cyprus, Nicosia, Cyprus
<EMAIL_ADDRESS>
###### Abstract

EXplainable AI (XAI) constitutes a popular method to analyze the reasoning of
AI systems by explaining their decision-making, e.g. providing a
counterfactual explanation of how to achieve recourse. However, in cases such
as unexpected explanations, the user might be interested in learning about the
cause of this explanation – e.g. properties of the utilized training data that
are responsible for the observed explanation. Under the umbrella of data
valuation, first approaches have been proposed that estimate the influence of
data samples on a given model. In this work, we take a slightly different
stance, as we are interested in the influence of single samples on a model
explanation rather than the model itself. Hence, we propose the novel problem
of identifying training data samples that have a high influence on a given
explanation (or related quantity) and investigate the particular case of
differences in the cost of the recourse between protected groups. For this, we
propose an algorithm that identifies such influential training samples.

##  1 Introduction

Nowadays, many Artificial Intelligence (AI-) and Machine Learning (ML-) based
systems are deployed in the real world Zhao et al. (2023); Ho et al. (2022).
These systems show an impressive performance but are still not perfect – e.g.
failures, issues of fairness, and vulnerability to manipulations such as data
poisoning can cause harm when applied in the real world. Given the threat of
failures, transparency of such deployed AI- and ML-based systems becomes a
crucial aspect. Transparency is important not only to prevent failures but
also to create trust in such systems and understand where and how it is safe
to deploy them. The importance of transparency was also recognized by the
policymakers and therefore found its way into legal regulations such as the
EU’s GDPR Council of European Union (2016) or the more recent EU AI act
Commission et al. (21 04 2021). Explanations are a popular way of achieving
transparency and shaping the field of eXplainable AI (XAI) Dwivedi et al.
(2023). However, because of many different use cases and users, many different
explanation methods exist Dwivedi et al. (2023); Rawal et al. (2021). Popular
instances of XAI methods are LIME Ribeiro et al. (2016), SHAP Sundararajan and
Najmi (2020), and counterfactual explanations Wachter et al. (2017) that yield
computational recourse.

However, in cases of implausible or unexpected explanations such as unexpected
attention/focus of the AI to some input regions (e.g. ‘Clever Hans’ effect
Kauffmann et al. (2020); Anders et al. (2022)), the user might be interested
in an ”explanation of the explanation”. The need for methods to understand the
cause of explanations is also emphasized by recent findings that explanations
are vulnerable to manipulations and poisonings Baniecki et al. (2022);
Baniecki and Biecek (2024); Artelt et al. (2024), potentially harming the
users’ trust in the explanations. One possibility to analyze and understand
the cause of an explanation would be to trace it back to the training samples
– i.e. identifying training samples that have a strong influence on (i.e.
caused) the observed explanation. Those training samples could provide
additional insights into the system and can be then sanity checked and removed
or corrected in case of errors. To the best of our knowledge, no prior work
has looked into this aspect. Our contributions: We introduce and formalize the
novel problem of analyzing the influence of training samples on explanations,
and investigate the particular case of identifying training samples that have
a strong influence on the difference in the cost of recourse between two
protected groups, i.e. violation of group fairness of the given
counterfactual.

##  2 Foundations

###  2.1 Data-Valuation

The young field of data-valuation Sim et al. (2022) is concerned with
assessing the value/importance of individual training samples – i.e.
quantifying the importance of each sample to the final trained model. Such
knowledge could for instance be used to pay users for utilizing their data,
sanity check (the labeling of) highly relevant training samples, or to acquire
more data samples that are similar to the most relevant ones. The Data-Shapley
method Ghorbani and Zou (2019) carries the concept of Shapley-Values
Sundararajan and Najmi (2020) over to data valuation by computing the
influence $\phi_{i}\in\mathbb{R}$ of each training sample
$(\vec{x}_{i},y_{i})\in\mathcal{S}$ on a value function
$V:\mathcal{S}\mapsto\mathbb{R}$. This value function $V(\cdot)$ states the
property of interest of a predictive function $h:\mathcal{X}\to\mathcal{Y}$
derived from the given training data $\mathcal{S}$. In data valuation, the
property of interest is usually the predictive performance of $h(\cdot)$, e.g.
the accuracy. Requiring some equitable properties, it can be shown Ghorbani
and Zou (2019) that the solution of $\phi_{i}$ is given as:

$\phi_{i}=C\sum_{\mathcal{S}\subseteq\mathcal{D}-\\{i\\}}\frac{V(\mathcal{S}\cup\\{i\\})-V(\mathcal{S})}{\binom{|\mathcal{D}|-1}{|\mathcal{S}|}}$
(1)

where $C$ is a constant, and $\\{i\\}$ refers to the $i$-th sample in a given
set $\mathcal{D}$. Like Shapley-Values, the computation of Eq. (1) is
computationally infeasible. Therefore, in Ghorbani and Zou (2019) a Monte-
Carlo approximation of Eq. (1) is proposed:

$\phi_{i}=\mathbb{E}_{\pi\sim\Pi}[V(\mathcal{S}^{i}_{\pi}\cup\\{i\\})-V(\mathcal{S}^{i}_{\pi})]$
(2)

where $S^{i}_{\pi}$ denotes the first $i-1$ samples in the training data set
$\mathcal{S}$ under the permutation $\pi$. Furthermore,
$\mathcal{S}^{i}_{\pi}\cup\\{i\\}$ denotes the addition of the $i$-th training
data sample to the $S^{i}_{\pi}$. In order to completely avoid the
computationally expensive refitting of $h(\cdot)$ in Eq. (2), the same authors
Ghorbani and Zou (2019) propose to only perform a single gradient descent step
instead of completely refitting $h(\cdot)$ in Eq. (2).

###  2.2 Counterfactuals for Computational Recourse

A counterfactual explanation (often just called counterfactual) states
(actionable) changes to the features of a given input such that the system’s
output changes. Usually, an explanation is requested in the case of an
unfavorable outcome Riveiro and Thill (2022) – in the latter case, a
counterfactual is also referred to as (computational) recourse Karimi et al.
(2021), i.e. recommendations on how to change the unfavorable into a favorable
outcome. Because counterfactuals can mimic ways in which humans explain Byrne
(2019), they constitute among one of the most popular explanation methods in
literature and in practice Verma et al. (2020). When computing a
counterfactual $\vec{\delta}_{\text{cf}}$ Wachter et al. (2017), it must be
ensured that 1) it indeed changes the output of the system; and 2) the cost of
$\vec{\delta}_{\text{cf}}$ – i.e. the cost and effort it takes to execute the
counterfactual in the real world should be kept to a minimum. We phrase the
computation of a counterfactual $\vec{\delta}_{\text{cf}}\in\mathbb{R}^{d}$
for a given instance $\vec{x}_{\text{orig}}\in\mathbb{R}^{d}$ as the following
optimization problem:

$\underset{\vec{\delta}_{\text{cf}}\,\in\,\mathbb{R}^{d}}{\arg\min}\;\operatorname*{{\ell}}\big{(}h(\vec{x}_{\text{orig}}+\vec{\delta}_{\text{cf}}),y_{\text{cf}}\big{)}+C\cdot\operatorname*{{\theta}}(\vec{\delta}_{\text{cf}})$
(3)

where $\operatorname*{{\ell}}(\cdot)$ penalizes deviation of the prediction
$h(\vec{x}_{\text{cf}}:=\vec{x}_{\text{orig}}+\vec{\delta}_{\text{cf}})$ from
the requested outcome $y_{\text{cf}}$, $\operatorname*{{\theta}}(\cdot)$
states the cost of the explanation (e.g. cost of recourse) which should be
minimized, and $C>0$ denotes the regularization strength balancing the two
properties. The short-hand notation $\text{CF}(\vec{x},h)$ denotes the
counterfactual $\vec{\delta}_{\text{cf}}$ of an instance $\vec{x}$ under a
classifier $h(\cdot)$ iff the target outcome $y_{\text{cf}}$ is uniquely
determined. Note that the cost $\operatorname*{{\theta}}(\cdot)$ is highly
domain and use-case specific. However, in many implementations and toolboxes
Guidotti (2022), the $p$-norm is used as a default.

######  Remark 1.

In the case of recourse – i.e. a counterfactual $\vec{\delta}_{\text{cf}}$ for
turning an unfavorable into a favorable outcome –, we refer to the cost
$\operatorname*{{\theta}}(\vec{\delta}_{\text{cf}})$, as the _cost of
recourse_.

In this work, w.l.o.g., we refer to $y=0$ as the unfavorable, and $y=1$ as the
favorable outcome. Besides those two essential properties in Eq. (3), there
exist additional relevant aspects such as plausibility Looveren and Klaise
(2021); Poyiadzi et al. (2020), diversity Mothilal et al. (2020), robustness
Artelt et al. (2021), etc. which have been addressed in literature Guidotti
(2022). There exist numerous methods and implementations/toolboxes for
computing counterfactual explanations in practice Guidotti (2022) – most
include some additional aspects such as plausibility, diversity, etc. :
Counterfactuals Guided by Prototypes Looveren and Klaise (2021) focuses on
plausibility. Here a set of plausible instances (so-called prototypes) are
used to pull the final counterfactual instance (i.e.
$\vec{x}_{\text{orig}}+\vec{\delta}_{\text{cf}}$) closer to these plausible
instances and by this make them more plausible. The simple instantiation
Nearest Training Sample method is a straightforward baseline method for
computing plausible counterfactuals by picking the closest sample, with the
requested output $y_{\text{cf}}$, from a given set (e.g. training set) as the
counterfactual instance $\vec{x}_{\text{cf}}$.

A critical and still unsolved fairness issue in computational recourse is the
difference in the cost of recourse
$\operatorname*{{\theta}}(\vec{\delta}_{\text{cf}})$ between protected groups
Artelt and Hammer (2023); Von Kügelgen et al. (2022); Sharma et al. (2021) –
i.e. individuals from one protected group (e.g. gender) get more costly
recommendations on how to achieve recourse. It was shown that such cases could
be created intentionally by targeted attacks Artelt et al. (2024); Slack et
al. (2021).

##  3 Influence of Training Data on Explanations

We consider settings, where we have a predictive model
$h:\mathcal{X}\to\mathcal{Y}$, derived from a training data set
$\mathcal{D}_{\text{train}}$, together with an explanation $z\in\mathcal{E}$
of $h(\cdot)$ – we use the shorthand notation $Z(h)\mapsto z\in\mathcal{E}$ to
denote the explanation generation method. The explanation $z$ could be any
type of explanation, e.g. a counterfactual explanation, or some kind or
property of an explanation such as the cost of recourse in the case of a
counterfactual. We are interested in identifying training samples that have a
high influence on the explanation $z$ – i.e. outlier or malicious training
samples that ”caused” the observed explanation $z$. To be able to compute the
influence (a scalar) of a single sample on an explanation, we introduce a
function $\Psi:\mathcal{E}\times\mathcal{E}\to\mathbb{R}$ that computes the
similarity of two given explanations $z_{1},z_{2}\in\mathcal{E}$ of the same
type, whereby larger absolute numbers correspond to a larger dissimilarity. In
the case of explanations that are stated as real-valued vectors (i.e.
$\mathcal{E}=\mathbb{R}^{m}$), $\Psi(\cdot)$ could be implemented by a
$p$-norm: $\Psi(z_{1},z_{2})=\lVert{z_{1}-z_{2}}\rVert_{p}$.

Next, we can formally define and characterize training samples that have a
strong influence on an explanation.

######  Definition 1 (Influential Training Samples).

For a given training set $\mathcal{D}_{\text{train}}$, we say that
$\mathcal{D}_{\text{infl}}\subset\mathcal{D}_{\text{train}}$ has a strong
influence on the explanation $z$ iff the absence of
$\mathcal{D}_{\text{infl}}$ changes the explanation $z$ significantly:

$|\Psi(z_{\mathcal{D}_{\text{train}}},z_{\mathcal{D}_{\text{train}}\setminus\mathcal{D}_{\text{infl}}})|>>0$
(4)

where $z_{\mathcal{D}_{\text{train}}}$ refers the explanation of $h(\cdot)$
trained on $\mathcal{D}$.

In this work, we propose to find such influential training samples (Definition
1) by utilizing the Data-Shapley method Ghorbani and Zou (2019) from the data
valuation literature as described in Section 2.1. We aim to identify training
instances that have a strong influence on the explanation $z$ of a given
$h(\cdot)$. We substitute the difference of the two value functions in Eq. (2)
with Eq. (4) from Definition 1:

$V(\mathcal{D}\cup\\{i\\})-V(\mathcal{D}):=\Psi(z_{\mathcal{D}\cup\\{i\\}},z_{\mathcal{D}})$
(5)

This allows us to use Eq. (2) to compute the influence score $\phi_{i}$ of
each training sample in $\mathcal{D}$. The complete gradient-based Monte-Carlo
algorithm for computing the influence score $\phi_{i}$ of each training sample
is described in Algorithm 1.

Finally, we select the training samples with the largest absolute influence
score as the set of most influential training samples
$\mathcal{D}_{\text{infl}}$ (Definition 1):

$\mathcal{D}_{\text{infl}}=\\{(\vec{x}_{i_{0}},y_{i_{0}}),(\vec{x}_{i_{1}},y_{i_{1}}),\dots\\}\quad\text{s.t.
}|\phi_{i_{0}}|\geq|\phi_{i_{1}}|\geq\dots$ (6)

where the number of influential training samples could either be given by the
user or determined automatically by applying a minimum threshold to
$|\phi_{i}|$.

Algorithm 1 Finding Influential Training Samples

Input: Labeled training samples $\mathcal{D}$; $K$ number of training
iterations
Output: Influence score $\phi_{i}$ of each training sample.

1:for $j=1,...,N$ or until convergence do

2: Random initialization of $h(\cdot)$ weights $\vec{w}$

3: for $t=1,...,K$ do $\triangleright$ Training loop

4: $z_{\mathcal{D}}=Z(h)$ $\triangleright$ Current explanation

5: $\pi=\text{random\\_permutation}$

6: for idx $\in\pi$ do

7: $(\vec{x}_{i},y_{i})=\mathcal{D}\text{[idx]}$ $\triangleright$ Get current
sample

8:
$\vec{w}-=\lambda\nabla_{\vec{w}}\operatorname*{{\ell}}(\vec{x}_{i},y_{i}\mid\vec{w})$
$\triangleright$ Gradient descent

9: $z_{\mathcal{D}\cup\\{i\\}}=Z(h)$ $\triangleright$ Compute new explanation

10:
$\phi_{\text{[idx]}}^{j,t}=\Psi(z_{\mathcal{D}\cup\\{i\\}},z_{\mathcal{D}})$
$\triangleright$ Compute influence of $(\vec{x}_{i},y_{i})$

11: $z_{\mathcal{D}}=z_{\mathcal{D}\cup\\{i\\}}$ $\triangleright$ Update
current explanation

12: end for

13: end for

14:end for

15:$\phi_{i}=\frac{1}{N\cdot K}\sum_{j,t}\phi_{i}^{j,t}$ $\triangleright$
Final influence scores

###  3.1 Tracing back the Difference in the Cost of Recourse

As a particular instantiation of our proposed method for identifying
influential training samples (see Algorithm 1), we consider the emerging
problem of analyzing the reason for the difference in the cost of recourse
between two protected groups Artelt and Hammer (2023); Sharma et al. (2020)
(see Section 2.2). We formalize the difference in the worst-case cost of
recourse between two protected groups as follows:

$\left|\underset{i}{\max}(\operatorname*{{\theta}}\circ\text{CF}(\vec{x}_{i}\mid
s=0,h_{\mathcal{D}})-\underset{i}{\max}(\operatorname*{{\theta}}\circ\text{CF}(\vec{x}_{i}\mid
s=1,h_{\mathcal{D}})))\right|$ (7)

where $s=?$ denotes the protected attribute. Consequently, we define the value
function $V(\cdot)$ to be equal to Eq. (7).

However, the evaluation of Eq. (7) is computationally expensive because it
requires computing a counterfactual $\text{CF}(\vec{x}_{i}\mid
s=?,h_{\mathcal{D}})$ for every sample in $\mathcal{D}$. In order to make the
computation of the influence scores $\phi_{i}$ feasible, we assume that the
cost of recourse $\operatorname*{{\theta}}(\cdot)$ is related to the distance
to the decision boundary and propose an approximation based on the difference
in the logits Sharma et al. (2021):

$\operatorname*{{\theta}}\circ\text{CF}(\vec{x}_{i}\mid
s=?,h_{\mathcal{D}}))\approx|g_{0}(\vec{x}_{i})-g_{1}(\vec{x}_{i})|$ (8)

where $g_{1},g_{2}$ denote the logits of the neural network $h(\cdot)$ The
authors of Sharma et al. (2021) show that Eq. (8) constitutes a good
approximation of the distance to the decision boundary. The final value
function $V(\cdot)$ denoted as $c_{\mathcal{S}}$ is given as:

$c_{\mathcal{S}}=\left|\underset{\vec{x}_{i}\in\mathcal{S}\mid
s=0}{\max}(|g_{0}(\vec{x}_{i})-g_{1}(\vec{x}_{i})|)-\underset{\vec{x}_{i}\in\mathcal{S}\mid
s=1}{\max}(|g_{0}(\vec{x}_{i})-g_{1}(\vec{x}_{i})|)\right|$ (9)

In order to apply our proposed Algorithm 1 from Section 3, we define the
difference $\Psi(\cdot)$ between two explanations (here the cost of recourse)
as follows:

$\Psi(z_{\mathcal{D}\cup\\{i\\}},z_{\mathcal{D}}):=c_{\mathcal{D}\cup\\{i\\}}-c_{\mathcal{D}}$
(10)

The training samples of interest to us are those with a large positive
influence score, i.e. $\phi_{i}>>0$, since those are likely to increase the
difference in the cost of recourse Eq. (7). In the empirical evaluation
(Section 4), we investigate the effect of removing those training samples from
the training data.

##  4 Experiments

We empirically evaluate our proposed Algorithm 1 for identifying influential
training samples (see Section 3.1) and evaluate how the deletion of those
samples influences the difference in the cost of recourse between protected
groups, as well as the predictive performance of the classifier.

Figure 1: Evaluation of the Proto CF method for plausible counterfactuals on the Diabetes data set – we report mean and standard deviation. CF Method | Data set |  Difference in Cost of Recourse Eq. (7) $\downarrow$ |  F1-score $\uparrow$
---|---|---|---
|  | Ours | Data-Shapley | Random removal | Ours | Data-Shapley | Random removal
Proto | Credit | $61.17\pm 14.15$ | $62.35\pm 24.71$ | $80.22\pm 16.03$ | $5.94\pm 0.28$ | $5.43\pm 0.23$ | $6.10\pm 0.35$
Diabetes | $17.26\pm 9.30$ | $18.45\pm 10.73$ | $21.80\pm 15.25$ | $7.62\pm 0.42$ | $7.23\pm 0.29$ | $7.91\pm 0.42$
Nearest | Credit | $60.71\pm 24.55$ | $48.69\pm 31.48$ | $66.59\pm 36.58$ | $6.01\pm 0.24$ | $5.43\pm 0.27$ | $6.20\pm 0.36$
Diabetes | $17.76\pm 6.96$ | $18.03\pm 9.50$ | $24.37\pm 14.22$ | $7.83\pm 0.54$ | $7.39\pm 0.44$ | $8.05\pm 0.49$
Wachter | Credit | $26.27\pm 3.28$ | $26.72\pm 1.00$ | $27.10\pm 2.37$ | $5.97\pm 0.27$ | $5.39\pm 0.29$ | $6.08\pm 0.38$
Diabetes | $15.57\pm 7.81$ | $12.16\pm 5.18$ | $15.79\pm 10.60$ | $7.60\pm 0.44$ | $7.26\pm 0.28$ | $7.85\pm 0.45$
Table 1: Areas under each curve – we report mean and standard deviation over
each curve (i.e. fold), and round all numbers to two decimal places. Smaller
numbers are better for the difference in the cost of recourse, whereas larger
numbers are better for the F1-score.

#### Data

We consider the following two benchmark data sets from the fairness literature
Friedler et al. (2019):

The “Diabetes” data set Efron et al. (2004) (denoted as Diabetes) contains
data from $442$ diabetes patients, each described by $9$ numeric attributes
together with the sensitive binary attribute “sex”. The target is a binarized
quantitative measure of disease progression one year after baseline.

The “German Credit Data set” Ger (1994) (denoted as Credit) is a data set for
loan approval and contains $1000$ samples each annotated with $7$ numerical
and $13$ categorical attributes, including the sensitive binary attribute
“sex”, with a binary target value. We only use the seven numerical features.

#### Setup

We use the $\ell_{1}$ norm as a popular implementation Guidotti (2022) of the
cost of recourse – i.e.
$\operatorname*{{\theta}}(\cdot)=\lVert{\cdot}\rVert_{1}$. For all data sets,
we utilize a Deep Neural Network as the classifier $h(\cdot)$. We conduct the
experiments in a $5$-fold cross-validation: After fitting the classifier, we
compute the most influential training samples on the difference in the cost of
recourse by our proposed method from Section 3.1, whereby all negative
classified samples (i.e. $h(\cdot)=0$) from the test set are considered in Eq.
(10). To evaluate the results, we increasingly remove (1% - 30%) of the most
influential training samples from the training set, retrain the classifier,
and evaluate the difference in the cost of recourse between the two protected
groups – we report the mean as well as the standard deviation of Eq. (7)
(difference in the cost of recourse) and of the F1-score of $h(\cdot)$. We
compute the computational recourse (i.e. counterfactuals) using different
popular recourse methods: Nearest Training Sample (denoted as Nearest), as
simple baseline for plausible counterfactuals; Counterfactuals guided by
Prototypes Looveren and Klaise (2021) (denoted as Proto) as an advanced method
for computing plausible counterfactuals; Classic counterfactuals Wachter et
al. (2017) (denotes as Wachter) by solving Eq. (3).

#### Baseline

We compare our method (i.e. Algorithm 1) to two baselines: 1) Removal of
random training samples; 2) Removal of the most influential training samples
on the predictive performance as returned by the original Data-Shapley method
Ghorbani and Zou (2019).

#### Results

The results for the Proto method and the Diabetes data set are shown in Figure
1. All other results are summarized in Table 1 by computing the area under
each curve (see Figure 1) – smaller numbers are better for the difference in
the cost of recourse, whereas larger numbers are better for the F1-score. For
decreasing the difference in the cost of recourse Eq. (7), we observe that our
method almost always achieves a bit better or at least competitive performance
with the Data-Shapley method. However, our method consistently maintains a
much better predictive performance of the classifier than the Data-Shapley
method which often leads to a drastic drop in predictive performance. Random
removal of training samples does not affect the F1-score much, however, it
also does not significantly decrease the difference in the recourse cost.
Together, these results demonstrate that our proposed method is able to
identify influential training samples (1) that decrease the difference in the
cost of recourse and that those samples do not affect the classifier
$h(\cdot)$ as strong as those determined by the Data-Shapley method.

##  5 Summary & Conclusion

In this work, we introduced the novel problem of identifying training samples
that have a strong influence on an explanation. We investigated the particular
case of differences in the cost of recourse between two protected groups, and
proposed an algorithm to identify training samples that contribute
significantly to the observed difference. We empirically tested that removing
those identified training samples, indeed reduces the difference significantly
without hurting the predictive performance too much. In this work, we mainly
focused on the cost of recourse as the quantity of interest, however, the
proposed methodology and Algorithm 1 are more general and can be applied to
many other explanations as well. Because groups of samples might have a strong
influence only together, it would be interesting to extend Algorithm 1 to
consider groups of training samples instead of individual samples. Here the
challenge of finding such groups arises.

## Acknowledgments

This research was supported by the Ministry of Culture and Science NRW
(Germany) as part of the Lamarr Fellow Network. This publication reflects the
views of the authors only.

## References

  * Anders et al. [2022] Christopher J Anders, Leander Weber, David Neumann, Wojciech Samek, Klaus-Robert Müller, and Sebastian Lapuschkin.  Finding and removing clever hans: Using explanation methods to debug and improve deep models.  Information Fusion, 77:261–295, 2022.
  * Artelt and Hammer [2023] André Artelt and Barbara Hammer.  ”Explain it in the Same Way!” – Model-Agnostic Group Fairness of Counterfactual Explanations.  In Amir Ofra, Tim Miller, and Hendrik Baier, editors, Workshop on XAI, 2023.
  * Artelt et al. [2021] André Artelt, Valerie Vaquet, Riza Velioglu, Fabian Hinder, Johannes Brinkrolf, Malte Schilling, and Barbara Hammer.  Evaluating robustness of counterfactual explanations.  In 2021 IEEE Symposium Series on Computational Intelligence, pages 01–09. IEEE, 2021.
  * Artelt et al. [2024] André Artelt, Shubham Sharma, Freddy Lecué, and Barbara Hammer.  The effect of data poisoning on counterfactual explanations.  arXiv preprint arXiv:2402.08290, 2024.
  * Baniecki and Biecek [2024] Hubert Baniecki and Przemyslaw Biecek.  Adversarial attacks and defenses in explainable artificial intelligence: A survey.  Information Fusion, page 102303, 2024.
  * Baniecki et al. [2022] Hubert Baniecki, Wojciech Kretowicz, and Przemyslaw Biecek.  Fooling partial dependence via data poisoning.  In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 121–136. Springer, 2022.
  * Byrne [2019] Ruth M. J. Byrne.  Counterfactuals in explainable artificial intelligence (xai): Evidence from human reasoning.  In IJCAI-19, 2019.
  * Commission et al. [21 04 2021] European Commission, Directorate-General for Communications Networks, Content, and Technology.  Proposal for a Regulation laying down harmonised rules on Artificial Intelligence (Artificial Intelligence Act) and amending certain Union legislative acts.  Policy and Legistlation, 21-04-2021.
  * Council of European Union [2016] Council of European Union.  Regulation (EU) 2016/679 of the European Parliament and of the Council of 27 April 2016 on the protection of natural persons with regard to the processing of personal data and on the free movement of such data, and repealing Directive 95/46/EC.  Official Journal of the European Union, L 119:4.5, 2016.
  * Dwivedi et al. [2023] Rudresh Dwivedi, Devam Dave, Het Naik, Smiti Singhal, Rana Omer, Pankesh Patel, Bin Qian, Zhenyu Wen, Tejal Shah, Graham Morgan, et al.  Explainable AI (XAI): Core ideas, techniques, and solutions.  ACM Computing Surveys, 55(9):1–33, 2023.
  * Efron et al. [2004] Bradley Efron, Trevor Hastie, Iain Johnstone, and Robert Tibshirani.  Least angle regression.  2004\.
  * Friedler et al. [2019] Sorelle A Friedler, Carlos Scheidegger, Suresh Venkatasubramanian, Sonam Choudhary, Evan P Hamilton, and Derek Roth.  A comparative study of fairness-enhancing interventions in machine learning.  In Proceedings of the conference on fairness, accountability, and transparency, pages 329–338, 2019.
  * Ger [1994] Statlog (german credit data) data set, 1994.
  * Ghorbani and Zou [2019] Amirata Ghorbani and James Zou.  Data shapley: Equitable valuation of data for machine learning.  In International conference on machine learning, pages 2242–2251. PMLR, 2019.
  * Guidotti [2022] Riccardo Guidotti.  Counterfactual explanations and how to find them: literature review and benchmarking.  Data Mining and Knowledge Discovery, pages 1–55, 2022.
  * Ho et al. [2022] Jonathan Ho, Chitwan Saharia, William Chan, David J Fleet, Mohammad Norouzi, and Tim Salimans.  Cascaded diffusion models for high fidelity image generation.  The Journal of Machine Learning Research, 23(1):2249–2281, 2022\.
  * Karimi et al. [2021] Amir-Hossein Karimi, Gilles Barthe, Bernhard Schölkopf, and Isabel Valera.  A survey of algorithmic recourse: contrastive explanations and consequential recommendations.  ACM Computing Surveys, 2021.
  * Kauffmann et al. [2020] Jacob Kauffmann, Lukas Ruff, Grégoire Montavon, and Klaus-Robert Müller.  The clever hans effect in anomaly detection.  arXiv preprint arXiv:2006.10609, 2020.
  * Looveren and Klaise [2021] Arnaud Van Looveren and Janis Klaise.  Interpretable counterfactual explanations guided by prototypes.  pages 650–665, 2021.
  * Mothilal et al. [2020] Ramaravind K Mothilal, Amit Sharma, and Chenhao Tan.  Explaining machine learning classifiers through diverse counterfactual explanations.  In Proceedings of the 2020 conference on fairness, accountability, and transparency, pages 607–617, 2020.
  * Poyiadzi et al. [2020] Rafael Poyiadzi, Kacper Sokol, Raul Santos-Rodriguez, Tijl De Bie, and Peter Flach.  Face: feasible and actionable counterfactual explanations.  In Proceedings of the AAAI/ACM Conference on AI, Ethics, and Society, pages 344–350, 2020.
  * Rawal et al. [2021] Atul Rawal, James Mccoy, Danda B Rawat, Brian Sadler, and Robert Amant.  Recent advances in trustworthy explainable artificial intelligence: Status, challenges and perspectives.  IEEE Transactions on Artificial Intelligence, 1(01):1–1, 2021.
  * Ribeiro et al. [2016] Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin.  ”why should i trust you?”: Explaining the predictions of any classifier.  In 22Nd ACM SIGKDD, pages 1135–1144, New York, NY, USA, 2016. ACM.
  * Riveiro and Thill [2022] Maria Riveiro and Serge Thill.  The challenges of providing explanations of ai systems when they do not behave like users expect.  In Proceedings of the 30th ACM Conference on User Modeling, Adaptation and Personalization, pages 110–120, 2022.
  * Sharma et al. [2020] Shubham Sharma, Jette Henderson, and Joydeep Ghosh.  Certifai: A common framework to provide explanations and analyse the fairness and robustness of black-box models.  In Proceedings of the AAAI/ACM Conference on AI, Ethics, and Society, pages 166–172, 2020.
  * Sharma et al. [2021] Shubham Sharma, Alan H Gee, David Paydarfar, and Joydeep Ghosh.  Fair-n: Fair and robust neural networks for structured data.  In Proceedings of the 2021 AAAI/ACM Conference on AI, Ethics, and Society, pages 946–955, 2021.
  * Sim et al. [2022] Rachael Hwee Ling Sim, Xinyi Xu, and Bryan Kian Hsiang Low.  Data valuation in machine learning:” ingredients”, strategies, and open challenges.  In IJCAI, pages 5607–5614, 2022.
  * Slack et al. [2021] Dylan Slack, Anna Hilgard, Himabindu Lakkaraju, and Sameer Singh.  Counterfactual explanations can be manipulated.  Advances in Neural Information Processing Systems, 34:62–75, 2021\.
  * Sundararajan and Najmi [2020] Mukund Sundararajan and Amir Najmi.  The many shapley values for model explanation.  In International conference on machine learning, pages 9269–9278. PMLR, 2020.
  * Verma et al. [2020] Sahil Verma, John Dickerson, and Keegan Hines.  Counterfactual explanations for machine learning: A review, 2020.
  * Von Kügelgen et al. [2022] Julius Von Kügelgen, Amir-Hossein Karimi, Umang Bhatt, Isabel Valera, Adrian Weller, and Bernhard Schölkopf.  On the fairness of causal algorithmic recourse.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 9584–9594, 2022.
  * Wachter et al. [2017] Sandra Wachter, Brent Mittelstadt, and Chris Russell.  Counterfactual explanations without opening the black box: Automated decisions and the gdpr.  Harv. JL & Tech., 31:841, 2017.
  * Zhao et al. [2023] Wayne Xin Zhao, Kun Zhou, Junyi Li, Tianyi Tang, Xiaolei Wang, Yupeng Hou, Yingqian Min, Beichen Zhang, Junjie Zhang, Zican Dong, et al.  A survey of large language models.  arXiv preprint arXiv:2303.18223, 2023.