Constrained Optimization for SCMs

[JorgeLuizFranco]

Algorithm Recourse through Minimal Interventions optimization step can be defined as:

$$ A^* \in \arg\min_A \text{cost}(A; \mathbf{x}_F) $$

subject to:

$$ h(\mathbf{x}_{SCF}) \ne h(\mathbf{x}_F) $$

where:

$$ \mathbf{x}_{SCF} = F_A(F^{-1}(\mathbf{x}_F)) $$

and:

$$ \mathbf{x}_{SCF} \in \mathcal{P}, A \in \mathcal{F} $$

Here, $\mathbf{x}_F$ is the observed (factual) instance, $h(\mathbf{x})$ is the classifier's prediction function, and $\mathbf{x}_{SCF}$ is the structural counterfactual.

However, this is a constrained optimization problem and ideally CE.jl supports just GD-based optimization.

So, we will probably use projected gradient techniques:

https://www.cs.ubc.ca/~schmidtm/Courses/5XX-S20/S5.pdf

[JorgeLuizFranco]

Currently, we will base our grad descent optimization in the lagrangian form of the one provided by Karimi et al

$ L(x, \lambda) = \lambda cost(x; \mathbf{x}_F) + yloss(\mathbf{x}_{SCF},y^*) $

[JorgeLuizFranco]

So, just clarifying, we do not need to deal with the target variable y in the causal model, since it does not really appear in the optimization as we can see:

With no loss of generality, we take $x_{SCF}$ as just $x$:

$ \mathcal{L}(x) = \lambda \cdot \text{cost}(x; \mathbf{x}_F) + \text{yloss}(\mathbf{x}, y^*) $

It is clear in the paper that :

$ \text{yloss}(\mathbf{x}_{SCF}, y^*) = h \left(\left\{ x_{F_i} + \delta_i [i \in I] + \left(f_i(\text{pa}_{SCF_i}) - f_i(\text{pa}_{F_i}) \right) [i \notin I] \right\}_{i=1}^n \right) - h(\mathbf{x}_F) $

Then we can split the lagrangian derivative:

since $\frac{\partial \mathcal{L}}{\partial x_i} h(\mathbf{x}_F) = 0$

For $i \in I$ (intervened variables): $ \frac{\partial \mathcal{L}}{\partial x_i} = \lambda \cdot \frac{\partial \text{cost}}{\partial x_i} + \frac{\partial}{\partial x_i}\left(h(\left\{ x_{F_i} + \delta_i \right\}_{i=1}^n) \right) $

For $i \notin I$ (non-intervened variables): $ \frac{\partial \mathcal{L}}{\partial x_i} = \frac{\partial}{\partial x_i}\left(h(\left\{ x_{F_i} + \left(f_i(\text{pa}_{SCF_i}) - f_i(\text{pa}_{F_i}) \right) \right\}_{i=1}^n) \right) $

[pat-alt]

Thanks for adding this here @JorgeLuizFranco

[JorgeLuizFranco]

@pat-alt I am having some doubts in encondings.jl, since $x$ is an array equal to $x_F$ :

"""
    decode_array(dt::StatsBase.AbstractDataTransform, x::AbstractArray)

Helper function to decode an array `x` using a data transform `dt::StatsBase.AbstractDataTransform`.
"""
function decode_array(
    data::CounterfactualData, dt::StatsBase.AbstractDataTransform, x::AbstractArray
)
    idx = transformable_features(data)
    ignore_derivatives() do
        s = x[idx, :]
        s = StatsBase.reconstruct(dt, s)
        x[idx, :] = s
    end
    return x
end

here x should be a 1D array, right? But this does not make sense since we are doing x[idx, :]. Could you explain this to me?

since I am trying to create the run_causal_effects function this is not making too much sense because my initial thought was just do something like:

x[child_causal] = scm.coef[1]* x[parent_1] + scm.coef[2]* x[parent_2]  + scm.coef[3] # coef[3] -> bias

[pat-alt]

Hi @JorgeLuizFranco! x is just the encoded counterfactual (in our case just the feature vector). If only one counterfactual is being generated (i.e. kw argument num_counterfactuals in generate_counterfactual is set to 1), the x will be $d \times 1$ where $d$ is the number of features.

function decode_state(
    ce::CounterfactualExplanation, x::Union{AbstractArray,Nothing}=nothing
)

    # Unpack:
    s′ = isnothing(x) ? deepcopy(ce.s′) : x
    data = ce.data
    dt = data.input_encoder

    # Inverse-transform features:
    s′ = decode_array(data, dt, s′)

    # Categorical:
    s′ = DataPreprocessing.reconstruct_cat_encoding(data, s′)

    return s′
end

Does that clarify things?

[JorgeLuizFranco]

Understood, @pat-alt . It is like a parallelization, but in our case, I am unsure if generating more than one counterfactual should be possible, right?

Thank you!

[pat-alt]

I think it's possible, but let's not worry about that for now (happy to discuss on Thursday)

[pasq-cat]

So, just clarifying, we do not need to deal with the target variable y in the causal model, since it does not really appear in the optimization as we can see:

With no loss of generality, we take xSCF as just x:

L(x)=λ⋅cost(x;xF)+yloss(x,y∗)

It is clear in the paper that :

yloss(xSCF,y∗)=h({xFi+δi[i∈I]+(fi(paSCFi)−fi(paFi))[i∉I]}i=1n)−h(xF)

Then we can split the lagrangian derivative:

since ∂L∂xih(xF)=0

For i∈I (intervened variables): ∂L∂xi=λ⋅∂cost∂xi+∂∂xi(h({xFi+δi}i=1n))

For i∉I (non-intervened variables): ∂L∂xi=∂∂xi(h({xFi+(fi(paSCFi)−fi(paFi))}i=1n))

how did you write latex here on github?

[JorgeLuizFranco]

Hey, pasquale @Rockdeldiablo. Here is like a general markdown but for math I always use: " $ ` " and then close it with " ` $" like we do usually in Latex, but with " ` ". The editor don't let me but you should connect them without space

$\sqrt{tex} ^2$