Asymmetric Causal Shapley values

In this PR, we add support for computing asymmetric and/or causal Shapley values. The asymmetric version can use all approaches, while the causal version is limited to the Monte Carlo-based approaches. The implementation is an extension of #273 (but this PR was restricted to the gaussian approach and the old version of shapr), which was adapted from the package CauSHAPley.

Asymmetric Shapley values were proposed by Frye et al. (2020) as a way to incorporate causal knowledge in the real world by restricting the possible permutations of the features when computing the Shapley values to those consistent with a (partial) causal ordering.

Causal Shapley values were proposed by Heskes et al. (2020) as a way to explain the total effect of features on the prediction, taking into account their causal relationships, by adapting the sampling procedure in shapr.

The two ideas can be combined to obtain asymmetric causal Shapley values. For more details, see Heskes et al. (2020).

Usage: (Assume N_features = 7) (Symmetric) Conditional Shapley values: asymmetric = FALSE (default), causal_ordering = list(1:7) (default), and confounding = FALSE (default)

Marginal Shapley values: either 1) the same as above, but set approach = independence, or 2) asymmetric = FALSE (default), causal_ordering = list(1:7) (default), and confounding = TRUE.

Asymmetric conditional Shapley values with respect to a specific ordering: asymmetric = TRUE, causal_ordering = list(1, c(2, 3), 4:7), and confounding = FALSE (default).

Causal Shapley values (compute all coalitions, but chains of sampling steps): asymmetric = FALSE (default), causal_ordering = list(1, c(2, 3), 4:7), andconfounding = c(FALSE, TRUE, FALSE).

Asymmetric Causal Shapley values (compute only coalitions respecting the ordering and chains of sampling steps): asymmetric = TRUE, causal_ordering = list(1, c(2, 3), 4:7), and confounding = c(FALSE, TRUE, FALSE).

Main differences: The user now has the option to specify asymmetric, causal_ordering, and confounding in the explain function. The first argument, asymmetric, specifies if we are to consider all feature combinations/coalitions, or only the combinations that respect the (partial) causal ordering given by causal_ordering. The second argument, causal_ordering is a list specifying the (partial) causal ordering of the features (groups), i.e., causal_ordering = list(1:3, 4:5), which implies that features one to three are the ancestors of four and five. The third argument, confounding specifies if the user assumes that each component is subject to confounding or not, e.g., causal_confounding = c(FALSE, TRUE). Note that practitioners are responsible for correctly identifying the causal structures.

When the causal_ordering is not list(1:N_features), then we have a causal structure that implies that some coalitions/feature combinations will not respect the order. For example, we cannot have a combination that conditions/includes feature four and not all of the features one to three in the setting above, as they are feature four's ancestors. If asymmetric = TRUE, then we only use the combinations that respect the order. If asymmetric = FALSE, then we use all combinations. Furthermore, generating the MC samples for each valid coalition will introduce a chain of sampling steps, which will be influenced by the confounding argument.

That is, if S = {2}, we would in the first step (assuming confounding = c(FALSE, TRUE)) sample X1, X3 | X2, and in the second step, we would sample X4, X5 | X1, X2, X3. The confounding changes whether to include the features in the same component as conditional features or not, as Heskes et al. (2020) explained. Also, see examples in get_S_causal() for demonstrations of how changing the confounding assumption changes the data generation steps.

To reuse most of the shapr code, we iteratively call prepare_data() with different values of S to generate the data. This introduces a lot of redundant computations, as we then generate X1, X3, X4, X5 | X2 in the first step, but throw away X4 and X5. To only generate MC samples for the relevant features, we would have to rewrite all prepare_data.approach functions to also take in a Sbar argument as they currently assume that Sbar is all features not in S.

The independence, empirical, and ctree approaches can not necessarily generate n_samples but rather weigh the samples. It is not obvious how to combine these weights in an interactive sampling process. We solve it by sampling the samples n_samples time using the weights. This means that we will have duplicates, which introduces extra computations.

TODO:

[ ] Implement exact asymmetric causal feature Shapley values for all Monte Carlo-based approaches.
[ ] Implement support for non-exact. Need to figure out how to sample the allowed combinations and what weights to give them. I have a function that can create all valid combinations but still grows at O(2^C), where C is the number of features in the largest component in the causal ordering.
[ ] Implement support for groups. Restrict feature groups to be in the same component in the causal ordering.
[ ] Ctree is not very fast due to many inputs/MC samples. Can we somehow use the weights to speed it up?
[ ] Create a small vignette.
[ ] FUTURE: Generate only the features in Sbar and not all features not in S (Since Sbar union S is not all features). To do this, all prepare_data.approach functions must be rewritten.
[ ] FUTURE: Be more clever in choosing the combinations to go into the different batches. Combinations that condition on features in the same components have similar chains of sampling steps. Often, only the first step is different. See ?get_S_causal for some examples of chains. E.g., we can have c("2|", "3,4|1,2", "5|1,2,3,4") and c("1|", "3,4|1,2", "5|1,2,3,4"). Could then ideally save some time by computing the rest together to minimize the number of times we have to recompute/model the same conditional distributions (the last step is often identical for all combinations).
[ ] The causal versions of Gaussian and copula can be written faster in C++ by sending the whole chain of sampling steps for each coalition, but then we would no longer have the same structure for all sampling methods.

References:

Heskes, T., Sijben, E., Bucur, I. G., & Claassen, T. (2020). Causal Shapley Values: Exploiting Causal Knowledge to Explain Individual Predictions of Complex Models. Advances in Neural Information Processing Systems, 33.
Frye, C., Rowat, C., & Feige, I. (2020). Asymmetric Shapley values: incorporating causal knowledge into model-agnostic explainability. Advances in Neural Information Processing Systems, 33.

NorskRegnesentral / shapr

Asymmetric Causal Shapley values #395