1use crate::{
2 coalition, evaluation::CoalitionEvaluator, Background, EvaluationConfig, Explainer,
3 Explanation, IndependentMasker, Link, Masker, Predict, Result, ShapError,
4};
5use ndarray::{Array2, Array3, ArrayView2, Axis};
6pub struct ExactExplainer<M, K = IndependentMasker> {
8 model: M,
9 masker: K,
10 max_features: usize,
11 evaluation: EvaluationConfig,
12 link: Link,
13}
14impl<M> ExactExplainer<M, IndependentMasker> {
15 pub fn new(model: M, background: Background) -> Self {
16 Self::from_masker(model, IndependentMasker::new(background))
17 }
18}
19impl<M, K> ExactExplainer<M, K> {
20 pub fn from_masker(model: M, masker: K) -> Self {
21 Self {
22 model,
23 masker,
24 max_features: 20,
25 evaluation: EvaluationConfig {
26 coalition_batch_size: 64,
27 cache_capacity: 1 << 20,
28 max_model_rows: None,
29 },
30 link: Link::Identity,
31 }
32 }
33 pub fn with_max_features(mut self, n: usize) -> Self {
34 self.max_features = n;
35 self
36 }
37 pub fn with_evaluation_config(mut self, config: EvaluationConfig) -> Self {
38 self.evaluation = config;
39 self
40 }
41 pub fn with_link(mut self, link: Link) -> Self {
42 self.link = link;
43 self
44 }
45}
46pub(crate) fn checked_predict<M: Predict>(
47 model: &M,
48 x: ArrayView2<'_, f64>,
49) -> Result<Array2<f64>> {
50 let y = model.predict(x)?;
51 if y.nrows() != x.nrows() || y.ncols() == 0 {
52 return Err(ShapError::DimensionMismatch {
53 expected: format!("({}, outputs>0)", x.nrows()),
54 found: format!("{:?}", y.dim()),
55 });
56 }
57 if y.iter().any(|v| !v.is_finite()) {
58 return Err(ShapError::ModelError(
59 "prediction contains a non-finite value".into(),
60 ));
61 }
62 Ok(y)
63}
64pub(crate) fn coalition_value<M: Predict, K: Masker>(
65 model: &M,
66 masker: &K,
67 s: ndarray::ArrayView1<'_, f64>,
68 mask: &[bool],
69) -> Result<Vec<f64>> {
70 let y = checked_predict(model, masker.mask(s, mask)?.view())?;
71 Ok(y.mean_axis(Axis(0)).unwrap().to_vec())
72}
73impl<M: Predict, K: Masker> Explainer for ExactExplainer<M, K> {
74 fn explain(&self, x: ArrayView2<'_, f64>) -> Result<Explanation> {
75 let m = self.masker.n_features();
76 if x.nrows() == 0 {
77 return Err(ShapError::EmptyData);
78 }
79 if x.ncols() != self.masker.n_input_features() {
80 return Err(ShapError::DimensionMismatch {
81 expected: format!("{} input features", self.masker.n_input_features()),
82 found: format!("{} features", x.ncols()),
83 });
84 }
85 if m > self.max_features || m >= 63 {
86 return Err(ShapError::InvalidConfiguration(format!(
87 "exact SHAP supports at most {} features",
88 self.max_features
89 )));
90 }
91 let base = coalition_value(&self.model, &self.masker, x.row(0), &vec![false; m])?;
92 let o = base.len();
93 crate::error::checked_f64_shape(&[x.nrows(), m, o], "exact explanation")?;
94 let mut values = Array3::zeros((x.nrows(), m, o));
95 let mut bases = Array2::zeros((x.nrows(), o));
96 let factorial = (0..=m)
97 .scan(1.0, |a, k| {
98 if k > 0 {
99 *a *= k as f64
100 }
101 Some(*a)
102 })
103 .collect::<Vec<_>>();
104 for i in 0..x.nrows() {
105 let masks = coalition::all(m).collect::<Vec<_>>();
106 let mut evaluator =
107 CoalitionEvaluator::new(&self.model, &self.masker, self.evaluation)?;
108 let cache = evaluator
109 .evaluate(x.row(i), &masks)?
110 .into_iter()
111 .map(|row| {
112 row.into_iter()
113 .map(|value| self.link.forward(value))
114 .collect::<Result<Vec<_>>>()
115 })
116 .collect::<Result<Vec<_>>>()?;
117 for out in 0..o {
118 bases[[i, out]] = cache[0][out]
119 }
120 for j in 0..m {
121 for mask in coalition::all(m).filter(|z| z & (1 << j) == 0) {
122 let k = mask.count_ones() as usize;
123 let w = factorial[k] * factorial[m - k - 1] / factorial[m];
124 for out in 0..o {
125 values[[i, j, out]] += w
126 * (cache[(mask | (1 << j)) as usize][out] - cache[mask as usize][out]);
127 }
128 }
129 }
130 }
131 Explanation::new(values, bases, self.masker.attribution_data(x)?)
132 }
133}
134
135#[cfg(test)]
136mod tests {
137 use super::*;
138 use crate::{metrics::check_additivity, FixedMasker, FnModel, GroupedMasker};
139 use ndarray::{array, ArrayView2};
140
141 #[test]
142 fn exact_values_satisfy_local_accuracy_for_an_interaction() {
143 let model = FnModel::new(|x: ArrayView2<'_, f64>| {
144 Ok(x.map_axis(Axis(1), |r| r[0] * r[1] + 2.0 * r[0])
145 .insert_axis(Axis(1)))
146 });
147 let background = Background::new(array![[0.0, 0.0], [1.0, 1.0]]).unwrap();
148 let x = array![[2.0, 3.0]];
149 let explanation = ExactExplainer::new(model, background)
150 .explain(x.view())
151 .unwrap();
152
153 check_additivity(&explanation, array![[10.0]].view(), 1e-10).unwrap();
154 assert_eq!(explanation.values().dim(), (1, 2, 1));
155 }
156 #[test]
157 fn exact_logit_link_explains_log_odds() {
158 let model =
159 FnModel::new(|x: ArrayView2<'_, f64>| Ok(x.column(0).to_owned().insert_axis(Axis(1))));
160 let explanation = ExactExplainer::new(model, Background::new(array![[0.5]]).unwrap())
161 .with_link(Link::Logit)
162 .explain(array![[0.8]].view())
163 .unwrap();
164 assert!(explanation.base_values()[[0, 0]].abs() < 1e-12);
165 assert!((explanation.values()[[0, 0, 0]] - 4f64.ln()).abs() < 1e-12);
166 }
167 #[test]
168 fn grouped_features_are_explained_as_single_coalition_players() {
169 let model =
170 FnModel::new(|x: ArrayView2<'_, f64>| Ok(x.sum_axis(Axis(1)).insert_axis(Axis(1))));
171 let masker = GroupedMasker::new(
172 FixedMasker::new(array![0., 0., 0.]).unwrap(),
173 vec![vec![0, 2], vec![1]],
174 )
175 .unwrap();
176 let explanation = ExactExplainer::from_masker(model, masker)
177 .explain(array![[2., 4., 8.]].view())
178 .unwrap();
179 assert_eq!(explanation.values().dim(), (1, 2, 1));
180 assert_eq!(explanation.values(), &array![[[10.], [4.]]]);
181 assert_eq!(explanation.data(), array![[5., 4.]].view());
182 }
183}