{'fraction_non_alphanumeric': 0.037971228127644474, 'fraction_numerical': 0.004340348865776758, 'mean_word_length': 4.548924568312633, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 9, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 6, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Motivating explanations in Bayesian networks using MAP-independence

In decision support systems the motivation and justification of the system's diagnosis or classification is crucial for the acceptance of the system by the human user. In Bayesian networks a diagnosis or classification is typically formalized as the computation of the most probable joint value assignment to the hypothesis variables, given the observed values of the evidence variables (generally known as the MAP problem). While solving the MAP problem gives the most probable explanation of the evidence, the computation is a black box as far as the human user is concerned and it does not give additional insights that allow the user to appreciate and accept the decision. For example, a user might want to know to whether an unobserved variable could potentially (upon observation) impact the explanation, or whether it is irrelevant in this aspect. In this paper we introduce a new concept, MAP- independence, which tries to capture this notion of relevance, and explore its role towards a potential justification of an inference to the best explanation. We formalize several computational problems based on this concept and assess their computational complexity.


Introduction
With the availability of petabytes of data and the emergence of 'deep' learning as an AI technique to find statistical regularities in these large quantities of data, artificial intelligence in general and machine learning in particular has arguably entered a new phase since its emergence in the 1950s. Deep learning aims to build hierarchical models representing the data, with every new layer in the hierarchy representing ever more abstract information; for example, from individual pixels to lines and curves, to geometric patterns, to features, to categories. Superficially this might be related to how the human visual cortex interprets visual stimuli and seeks to classify a picture to be that of a cat, rather than of a dog.
When describing in what sense a cat is different from a dog, humans may use features and categories that we agreed upon to be defining features of cats and dogs, such as whiskers, location and form of the ears, the nose, etc. The deep learning method, however, does not adhere to features we humans find to be good descriptors; it bases its decisions where and how to 'carve nature's joints' solely on basis of the statistics of the data. Hence, it might very well be that the curvature of the spine (or some other apparently 'random' feature) happens to be the statistically most important factor to distinguish cats from dogs. This imposes huge challenges when the machine learning algorithm is asked to justify its classification to a human user. The sub-field of explainable AI has recently emerged to study how to align statistical machine learning with informative user-based motivations or explanations. Explainable AI, however, is not limited to deep neural network applications. Any AI application where trustworthiness is important benefits from justification and transparency of its internal process [12], and this includes decision support systems that are based on Bayesian networks [28], which is the focus of this paper. In these systems typically one is interested in the hypothesis that best explains the available evidence; for example in a medical case, the infection that is most probable given a set of health complaints and test findings [22].
Note that 'explainability' in explainable AI is in principle a triadic relationship between what needs to be explained, the explanation, and the user who seeks the explanation [31]. An explanation will be more satisfying ('lovelier', in Peter Lipton's [24] terms) if it allows the user to gain more understanding about the phenomenon to be explained. Lacave and Díez [23] review explanation in the context of a Bayesian network. In their work, three major categories of explanation has been identified. For example, the focus can be on explanation of the evidence or observed variables that need to be explained, where the most probable joint value assignment (or MAP explanation) serves as this explanation 1 . Alternatively, the focus can be on explanation of the model, i.e., the structure of the Bayesian network can be explained by providing conditional independence tests and justification in the form of expert assessment of probability distributions or training data sets. Finally, and for us most relevant, the focus can be on explaining the reasoning process. Here, the MAP explanation itself needs to be explained or motivated in terms of an explication of the reasoning process that needs further justification.
In this paper our aim is to improve the user's understanding of a specific MAP explanation by explicating the relevant information that contributed to said MAP explanation. That is, we seek to justify the MAP explanation by zooming in on the reasoning process. In some way, in the computation of the most probable joint value assignment to the hypothesis variables given the evidence, the process of marginalizing out the intermediate variables makes the decision more opaque. Some of these variables may have a bigger impact (i.e., are more influential) on the eventual decision than others, and this information is lost in the process. For example, the absence of a specific test result (i.e., a variable we marginalize out in the MAP computation) may lead to a different explanation of the available evidence compared to when a negative (or positive) test result were present. In this situation, this variable is more influential to the eventual explanation, and hence more relevant for the justification, than if the best explanation would be the same, irrespective of whether the test result was positive, negative, or missing. Our approach in this paper is to justify an explanation by showing which of these variables were influential towards arriving at this explanation. An intermediate variable is relevant in this justification if it has potential influence on the explanation.
This approach complements other approaches that focus on relevance of variables for justifying decisions. For MAP (i.e., where a Bayesian network is partitioned into hypothesis, evidence, and intermediate nodes) several authors focus on minimizing the set of hypothesis variables, pruning those variables that are deemed less relevant, thereby avoiding over-specification [34,39]; see [17] for an alternative proposal where over-specification is avoided by allowing the best explanation to be a set of joint value assignments rather than a singleton set. Others propose an assessment of the relevance of the evidence variables (rather than intermediate variables) for justifying an explanation [36,26,21]. Similarly, in Bayesian classifiers (without intermediate nodes) justification is often sought in terms of the impact an observable variable may have on the classification [1,32,25]. In contrast to these approaches, we assume that the partition between hypothesis variables, evidence variables, and intermediate variables is a given, and we focus on assessing the contribution of the intermediate variables towards a specific explanation.
Our perspective has roots in Pearl's early work on conditional independence [30]. Pearl suggests that human reasoning is in principle based on conditional independence: The organizational structure of human memory is such that it allows for easily retrieving context-dependent relevant information. For example (from [30, p.3]): The color of my friend's car is normally not related to the color of my neighbour's car. However, when my friend tells me she almost mistook my neighbour's car for her own, this information suddenly becomes relevant for me to understand, and for her to explain, this mistake. That is, the color of both cars is independent but becomes conditionally dependent on the evidence 2 .
In this paper we will argue that Pearl's proposal to model context-dependent (ir)relevance as conditional (in)dependence is in fact too strict. It generally leads to too many variables that are considered to be relevant: for some it is likely the case that, while they may not be conditionally independent on the hypothesized explanation given the evidence, they do not contribute to understanding why some explanation h is better than the alternatives. That means, for justification purposes their role is limited. In the remainder of this paper we will build on Pearl's work, yet provide a stronger notion of contextdependent relevance and irrelevance of variables relative to explanations of observations. Our goal is to advance explainable AI in the context of Bayesian 2 Graphically one can see this as a so-called common-effect structure, where C 1 and C 2 are variables that represent my car's, respectively my neighbour's car's, color; both variables have a directed edge towards the variable M that indicates whether my friend misidentified the cars or not. When M is unobserved, C 1 and C 2 are independent, but they become conditionally dependent on observation of M . networks by formalizing the problem of justification of an explanation (i.e., given an AI-generated explanation, advance the user's understanding why this explanation is preferred over others) into a computational problem that captures some aspects of this justification; in particular, by opening up the 'marginalization black box' and show which variables contributed to this decision. We show that this problem is intractable in the general case, but also give fixed-parameter tractability results that show what constraints are needed to render it tractable.
To summarize, we are interested in the potential applicability of this new concept for motivation and justification of MAP explanations, with a focus on its theoretical properties. The remainder of this paper is structured as follows. In the next section we offer some preliminary background on Bayesian networks and computational complexity and share our conventions with respect to notation with the reader. In section 3 we introduce so-called MAP-independence as an alternative to conditional independence, embed this concept in the literature, and elaborate on the potential of these computational problems for justifying explanations in Bayesian networks. In section 4 we introduce several formal computational problems based on this notion, and give complexity proofs and fixed-parameter tractability results for these problems. We conclude in section 5.

Preliminaries and notation
In this section we give some preliminaries and introduce the notational conventions we use throughout this paper. The reader is referred to textbooks like [4] for more background both on Bayesian networks and relevant aspects of computational complexity theory.
A Bayesian network B = (G B , Pr) is a probabilistic graphical model that succinctly represents a joint probability distribution Pr(V) = n i=1 Pr(V i | π(V i )) over a set of discrete random variables V. B is defined by a directed acyclic graph G B = (V, A), where V represents the stochastic variables and A models the conditional (in)dependencies between them, and a set of parameter probabilities Pr in the form of conditional probability tables (CPTs). In our notation π(V i ) denotes the set of parents of a node V i in G B . We use upper case to indicate variables, lower case to indicate a specific value of a variable, and boldface to indicate sets of variables respectively joint value assignments to such a set. Ω(V i ) denotes the set of value assignments to V i , with Ω(V a ) denoting the set of joint value assignment to the set V a .
One of the key computational problems in Bayesian networks is the problem to find the most probable explanation for a set of observations, i.e., a joint value assignment to a designated set of variables (the explanation set) that has maximum posterior probability given the observed variables (the joint value assignment to the evidence set) in the network. If the network includes variables that are neither observed nor to be explained (known as intermediate variables) this problem is typically referred to as MAP. We use the following formal definition: We assume that the reader is familiar with standard notions in computational complexity theory, notably the classes P and NP, NP-hardness, and polynomial time (many-one) reductions. The class PP is the class of decision problems that can be decided by a probabilistic Turing machine in polynomial time; that is, where yes-instances are accepted with probability strictly larger than 1 /2 and no-instances are accepted with probability no more than 1 /2. A problem in PP might be accepted with probability 1 /2 + where may depend exponentially on the input size n. Hence, it may take exponential time to increase the probability of acceptance (by repetition of the computation and taking a majority decision) close to 1; this in contrast to the related complexity class BPP that contains problems that can be solved in polynomial time by a randomized algorithm with probability arbitrarily close to 1. This makes PP a powerful class; we know for example that NP ⊆ PP and the inclusion is assumed to be strict. The canonical PP-complete decision problem is Majsat: given a Boolean formula φ, does the majority of truth assignments to its variables satisfy φ?
In computational complexity theory, so-called oracles are theoretical constructs that increase the power of a specific Turing machine. An oracle (e.g., an oracle for PP-complete problems) can be seen as a 'magic sub-routine' that answers class membership queries (e.g, in PP) in a single time step. In this paper we are specifically interested in classes defined by non-deterministic Turing machines with access to a PP-oracle. Such a machine is very powerful, and likewise problems that are complete for the corresponding complexity classes NP PP (such as MAP and Parameter Tuning) and co-NP PP (such as Monotonicity) are highly intractable [19,29,9]. Machines that can be characterized by such classes can themselves also be used as an oracle machine to, e.g., a non-deterministic Turing machine, leading to classes like NP NP PP with complete problems such as Maximin A Posteriori and Tunable Monotonicity [5,15].
Finally we wish to introduce the concept of fixed-parameter tractability to the reader. Oftentimes, NP-hard computational problems can be rendered tractable when the set of instances is constrained to instances where the value of some (set of) problem parameter(s) is bounded. Formally a parameterized problem k − Π is called fixed-parameter tractable for a parameter k if an instance i of Π can be decided in time O(p(|i|)f (k)) for a polynomial p and an arbitrary function f . Following the discussion in [16] we liberally mix integer and (monotone) rational parameters in our analyses.

MAP-independence
In the previous section we introduced the MAP problem as the problem to find the most probable explanation (viz., the joint value assignment to a set of hypothesis variables given observations in the network). In this paper we are not so much concerned with finding this explanation, but rather with motivating what information did or did not contribute to a given explanation. That is, rather than providing the 'trivial' justification "h * is the best explanation for e, since argmax h Pr(H = h | e) = argmax h i∈Ω(I) Pr(H = h, i | e) = h * " our goal is to partition the set I into variables I + that are relevant to establishing the best explanation and variables that are irrelevant. One straightforward approach, motivated by Pearl [30], would be to include variables in I + if they are conditionally dependent on H given e, and in I − when they are conditionally independent from H given e and to motivate the sets I + and I − in terms of a set of independence relations. This is particularly useful when inclusion in I + is triggered by the presence of an observation, such as in Pearl's example where 'color of my friend's car' and 'color of my neighbour's car' become dependent on each other once we learn that my friend confused both cars.
We argue that this way of partitioning intermediate variables into relevant and irrelevant ones, however useful, might not be the full story with respect to explanation. There is a sense in which a variable has an explanatory role in motivating a conclusion that goes beyond conditional (in)dependence. Take for example the small binary network in Figure 1(a). Assume that we want to motivate the best explanation for A given the evidence C = c, i.e., we want to motivate the outcome of argmax a Pr(A = a | C = c) = argmax a B,D Pr(A = a, B, D | C = c) in terms of variables that contribute to this explanation. Now, obviously D is not relevant, as it is d-separated from A given C. But the role of B is less obvious. This node is obviously not conditionally independent from A given C.
Whether This information is lost in the marginalization step but it helps motivate whyā is the best explanation of c.
Thus, the relevance of B for the explanation of A may need a different (and broader) notion of independence, as also suggested by [18]. Indeed, in this example, variable D is irrelevant for explaining A as D is conditionally independent from A given C; yet, we could also argue that B is irrelevant for explaining A if its value, were it observed, could not influence the explanation for A. We introduce the term MAP-independence for this (uni-directional) relationship; we say that A is MAP-independent from B given C = c when ∀ b∈Ω(B) argmax a * Pr(A = a * , B = b | C = c) = a for a specific value assignment a ∈ Ω(A). In general, for an unobserved variable I we have that the MAP explanation h * is MAP-independent from I given the evidence if the explanation would not have been different had I been observed to any value from its domain, and MAP-dependent if this is not the case.
In Figure 1  We call A weakly MAP-independent from the set {B, E}. Note that for singleton variable sets, weak and strong MAP-independence collapse. An explication of how I may impact or fail to impact the most probable explanation of the evidence will both help motivate the system's advice as well as offer guidance in further decisions, e.g., to decide when to gather additional evidence [10,8] to make the MAP explanation more robust. Typically, the number of intermediate variables that impact decisions (such that the explanation is weakly MAP-independent from these variables) is low [6]; however, when interactions between intermediate variables are taken into account, a challenge may be to find the smallest subset of intermediate variables from which the explanation is MAP-independent in the stronger sense. We will further extend upon this optimization problem in the next section.
Finally, we observe that there is a clear relation between the concept of MAP-independence and the so-called Same-decision probability defined by

Formal problem definition and results
The computational problem of interest is to decide upon the set I + , the relevant variables that contribute to establishing the best explanation given the evidence, in the sense as discussed above. We start with giving formal definitions for deciding whether weak or strong MAP-independence of a given set of variables relative to the evidence can be established and the optimization variant of this problem (i.e., to establish the smallest set of relevant variables). The latter problem is only interesting for strong MAP independence; in the weak case this is a trivial iteration over the variables in I. In subsequent sub-sections we elaborate on the computational complexity of these problems as well as consider fixed-parameter tractability results that indicate under which circumstances the problems are feasible.
We start with defining MAP-independence. For later simplification of the complexity proofs we look at the marginal definition of MAP; note that argmax H Pr(H | e) = argmax H Pr(H, e). Observe that the complement problem MAP-dependence is defined similarly with yes-and no-answers reversed.

MAP-independence
In this formal definition we allow for interaction in the set R. The related problem Weak MAP-independence, where we consider MAPindependence for each singleton variable on its own, is defined as follows: Weak MAP-independence Instance: As in MAP-independence. Question: Is ∀ R∈R ∀ r,r ∈Ω(R) argmax H Pr(H, R = r, E = e) = argmax H Pr(H, R = r , E = e)?
Observe, that while |Ω(R)| = O(c |R| ), where c = max W ∈V (G) Ω(W ), we have that in deciding Weak MAP-independence we test at most O(c|R|) assignments. Apart from assessing strong MAP-independence for specific sets R, we might be interested in the maximal subset R ⊆ I such that H is strongly MAPindependent from R given the evidence. We refer to this problem as Maximum MAP-independence, defined (as a decision problem) as follows: Observe that we allow in this problem definition for variables that are not part of the relevance assessment. These variables could, for example, be variables that are conditionally independent from the explanation given the evidence and therefore not relevant to be part of the formal assessment.

Computational complexity
We will show in this sub-section that an appropriate decision variant of MAP-independence is co-NP PP -complete and thus resides in the same complexity class as the Monotonicity problem [9]. For Weak MAPindependence it is easy to show membership of co-NP PP , by a similar argument, but hardness is unlikely given that the universal quantifier runs over a linear number of cases. For Maximum MAP-independence we show that the problem is in NP NP PP and is polynomial-time many-one reducible from the Partition-free A-Majsat problem which we conjecture (but were unable to prove) to be NP NP PP -complete. We first proceed with proving complexity of MAP-independence.
In order to establish the computational complexity of these problems, there are several caveats in the problem definitions above. The first one is that we wish to isolate the complexity of verifying that the MAP stays the same for all variables in the relevance assessment, and separate it from establishing MAP in the first place (an NP PP -hard problem). The second caveat is that, for complexity analyses, inference (and MAP) are defined as decision problems, rather than functional problems; the above definitions include functional aspects (such as maximization problems) that don't fit well with traditional complexity analyses of comparable problems.
To address the first caveat we require R to be non-empty and to include a joint value assignment h * to H in the input. We do not explicitly require in the formal definition of the decision problem that h * is in fact the MAP explanation, as this would effectively make MAP-independence a so-called promise problem [11], obfuscating the complexity analysis.
Prior to considering the second caveat let us first look at a common definition [16]  This captures the crucial sources of complexity (summation over the intermediate variables, maximization over the hypothesis set) of MAP. Note that MAP-D is NP PP -complete; further observe that both the summation and the maximization aspects of MAP are here formulated as decisions. Taking this into account we formulate MAP-independence-D as follows: Pr), where V(G) is partitioned into a set of evidence nodes E with a joint value assignment e, a non-empty explanation set H with a joint value assignment h * , a non-empty set of nodes R for which we want to decide MAP-independence relative to H, and a set of intermediate nodes I; rational number s.
Question: Is, for each joint value assignment r to R, Pr(h * , r, e) > s?
Note that as a decision variant of MAP-independence there is still a slight caveat, as the probability of Pr(h * , r, e) can be different for each joint value assignment r, implying that the 'generic' threshold s can either be too strict (h is still the MAP explanation although the test fails) or too loose (there is another explanation h which is the MAP explanation although the test passes). As the number of joint value assignments |Ω(R)| can be exponential in the size of the network (and thus we cannot include individual thresholds s i in the input of the decision problem without blowing up the input size), this nonetheless appears to be the closest decision problem variant that still captures the crucial aspects 3 of MAP-independence, particularly the universal quantification over all joint value assignments to R and the probabilistic inference and threshold test.
For the hardness proof we reduce from the canonical satisfiability co-NP PPcomplete variant A-Majsat [38] defined as follows:

A-Majsat
Instance: A Boolean formula φ with n variables {x 1 , . . . , x n }, partitioned into the sets A = {x 1 , . . . , x k } and M = {x k+1 , . . . , x n } for some 1 ≤ k ≤ n. Question: Does, for every truth instantiation x a to A, the majority of truth instantiations x m to M satisfy φ?
As a running example for our reduction we use the formula φ ex = ¬(x 1 ∧ x 2 ) ∨ (x 3 ∨ x 4 ), with A = {x 1 , x 2 } and M = {x 3 , x 4 }. This is a yes-instance 3 One of the reviewers of the conference version of this paper [20] asked whether a 'suitable' (neither too loose nor too strict) threshold s can (or is guaranteed) to exist. A trivial example with two unconnected binary nodes H (the MAP variable, with Pr(H = h) = 0.51 and h * = h) and uniformly distributed R (and either no evidence or another unconnected and arbitrarily instantiated evidence node), and a threshold s = 0.5 suffices to show that indeed there exists networks where a suitable s exists. On the other hand it is also easy to construct a small network where no suitable s exists; take a ternary node H instead, with binary and uniformly distributed R as parent (and again no or of A-Majsat: for each truth assignment to A, at least three out of four truth assignments to M satisfy φ. We construct a Bayesian network B φ from a given Boolean formula φ with n variables. For each propositional variable x i in φ, a binary stochastic variable X i is added to B φ , with possible values T and F and a uniform probability distribution. For each logical operator in φ, an additional binary variable in B φ is introduced, whose parents are the variables that correspond to the input of the operator, and whose conditional probability table is equal to the truth table of that operator. For example, the value T of a stochastic variable mimicking the and -operator would have a conditional probability of 1 if and only if both its parents have the value T , and 0 otherwise. The top-level operator in φ is denoted as V φ . In Figure 2   Proof. To prove membership in co-NP PP , we give a falsification algorithm for no-answers to MAP-independence-D instances, given access to an oracle for the PP-complete [3] Inference problem. Let (B, E, e, H, h * , R, I, s) be an instance of MAP-independence-D. We non-deterministically guess a joint value assignmentr, and use the Inference oracle to verify that Pr(h * ,r, e) ≤ s, which by definition implies that H is not MAP-independent from R given E = e, establishing a falsification.
To prove hardness, we reduce from A-Majsat. Let (φ, X A , X M ) be an instance of A-Majsat and let B φ be the Bayesian network created from φ as per the procedure described above. We set i.e., for every truth assignment to X A , the majority of truth assignments to X M satisfies φ. Then, by the construction of B φ , we have r Pr(V φ = T, r) > 1 /2 and so, as the variables in R are all uniformly distributed, Pr(V φ = T, r) > 2 −|R|−1 for every joint value assignment r to R, and so this is a yes-instance of MAP-independence-D. ⇐= Assume that (B, ∅, ∅, V φ , T, R, I, 2 −|R|−1 ) is a yes-instance of MAP-independence-D. Given the construction this implies that for all joint value assignments r it holds that Pr(V φ = T, r) > 2 −|R|−1 . But this implies that for all truth assignments to X A , the majority of truth assignments to X M satisfies φ, hence, this is a yes-instance of A-Majsat.
Observe that the construction of B φ takes time, polynomial in the size of φ, which concludes our proof. Furthermore, the result holds in the absence of evidence.
Further observe that the co-NP PP -membership proof of MAP-independence-D trivially extends to Weak MAP-independence-D by giving a suitable counterexample; however, this problem is unlikely to be complete for this class. We now turn to the complexity of Maximum MAP-independence-D. We will show that the following problem can be reduced in polynomial time to Maximum MAP-independence-D: Partition-free A-Majsat Instance: A Boolean formula φ with n variables {x 1 , . . . , x n }, positive integer k < n. Question: Is there a partition of {x 1 , . . . , x n } into the sets A and M, with |A| ≥ k, such that for every truth instantiation x a to A, the majority of truth instantiations x m to M satisfies (with x a ) φ?
It can be shown that Partition-free A-Majsat is in NP NP PP : nondeterministically guess the partition and use an oracle for A-Majsat to verify the desired property. However, despite substantial effort, we did not succeed in establishing hardness; while we can give a reduction from Partition-free A-Majsat to Maximum MAP-independence, implying that Maximum MAP-independence is as least as hard as Partitionfree A-Majsat, we therefore cannot show NP NP PP -hardness of Maximum MAP-independence 4 .
We start by defining the decision problem in a similar manner as for MAP-independence-D. Question: Is there a subset R ⊆ I P of size at least k, such that for each joint value assignment r to R, Pr(h * , r, e) > s?
Observe that Maximum MAP-independence-D is in NP NP PP , as we can non-deterministically guess R and invoke an oracle for MAP-independence-D. We now turn to the reduction.
Proof. Let (φ, k) be an instance of Partition-free A-Majsat, and let B φ be the Bayesian network created from φ as per the procedure described above, but without partitioning the variables X i into sets X A and X M ; we will refer to the set of variables X i as X. We set I P = X, H = {V φ }, E = ∅, 4 The canonical complete problems for classes in the counting hierarchy can be traced back to Wagner's [38] extension of early work by Meyer and Stockmeyer [27,35] which explicitly uses the given partitioning of the variables and oracle machines in their proof. The flexibility in the size of the sub-sets in the partition makes it difficult to force translation of a traditional EA-Majsat (the canonical complete satisfiability variant for NP NP PP ) instance into a Partition-free A-Majsat instance.
=⇒ Assume that (φ, k) is a yes-instance of Partition-free A-Majsat. Then there exists a partition of the variables X i of φ in the sets X A and X M , with |X A | ≥ k, such that for every truth assignment to X A , the majority of truth assignments to X M satisfies φ. Observe that if this property holds for X A with |X A | > k, it also holds for every subset X k A ⊂ X A with |X k A | = k, hence, we assume |X A | = k for ease of exposition. We set R = X A . By the construction of B φ , we have r Pr(V φ = T, r) > 1 /2 and so, as the variables in R are all uniformly distributed, Pr(V φ = T, r) > 2 −|R|−1 = 2 −k−1 for every joint value assignment r to R, and so this is a yes-instance of Maximum MAPindependence-D. ⇐= Assume that (B, ∅, ∅, V φ , T, I P , Given the construction this implies the existence of a subset R ⊆ I P with |X R | = k, such that for all joint value assignments r to R it holds that Pr(V φ = T, r) > 2 −k−1 . But this implies the existence of a partition of the variables X i of φ in the sets X A and X M , with |X A | = k, such that for all truth assignments to X A , the majority of truth assignments to X M satisfies φ. Hence, this is a yes-instance of Partition-free A-Majsat. Observe again that the construction of B φ takes time, polynomial in the size of φ, which concludes our proof. Furthermore, again the result holds in the absence of evidence.

Algorithm and algorithmic complexity
To decide whether a MAP explanation h * is MAP-independent from a set of variables R given evidence e, the straightforward algorithm below 5 shows that the run-time of this algorithm is O(Ω(R)) = O(2 |R| ) times the time needed for each MAP computation. This implies that the size of the set R for which we want to establish MAP independence is the crucial source of complexity assuming constraints that allow MAP to be computed [16], respectively approximated [29,18], feasibly. Given known results on fixed-parameter tractability of MAP, the following fixed-parameter tractability results can be derived: So, in general, for MAP-independence to be tractable we need to constrain the set R of variables to consider, and make sure that the MAP queries can be computed tractably by constraining the cardinality of the variables and size of the hypothesis set, and either the tree-width of the network or the size of the set of intermediate variables.
The following trivial modifications extend this algorithm to the weak case and to the maximization problem: We conclude that p-Weak MAP-independence is fixed-parameter tractable exactly when MAP is fixed-parameter tractable, and that p-Maximum MAPindependence is fixed-parameter tractable for p = {|H|, |I P |, tw, c}, p = {|H|, |I|, c}. Note that the latter results somewhat obfuscate the difference in complexity between MAP-independence and Maximum MAPindependence; in the third algorithm the additional foreach loop (looping over all subsets of I P of size k) collapses if |I P | is fixed.

Conclusion and future work
In this paper we introduced MAP-independence as a formal notion, relevant for decision support and justification of decisions. In a sense, MAPindependence is a relaxation of conditional independence, suggested by Pearl [30] to be a scaffold for human context-dependent reasoning. We suggest that MAP-independence may be a useful notion to further explicate the variables that are relevant for the establishment of a particular MAP explanation. Establishing whether the MAP explanation is MAP-independent from a set of variables given the evidence (and so, whether these variables are relevant for justifying the MAP explanation) is a computationally intractable problem; we expect that the problem of finding the maximal set for which the MAP explanation is MAP-independent is even harder, modulo commonly assumed separation properties of the counting hierarchy. However, for a specific variable of interest I (or a small set of these variables together) the problem is tractable whenever MAP can be computed tractably; in practice, this may suffice for usability in typical decision support systems.
There are many related problems of interest that one can identify, but which will be delegated to future work. For example, if the set of relevant variables is large, one might be interested in deciding whether observing one variable can bring down this set (by more than one, obviously). Initial work in this area has been proposed by [14] who looked at several heuristic approaches (e.g., Gini-index [33] and linear-value utility [10]) to decide which variable may best be observed.
Another related problem would be to decide upon the observations that are relevant for the MAP explanation (i.e., had we not observed E ∈ E or had we observed a different value, would that change the MAP explanation?). This would extend previous work [26] where the relevance of E for computing a posterior probability (conditioned on E) was established.
The notion of MAP-independence can, for practical purposes, be to strict; furthermore, when an explanation is MAP-dependent on a set of variables, the 'amount of impact' can be relevant. Various authors have proposed a form of quantification of MAP-independence, for example, based on the summed probability of joint value assignments to R for which the MAP explanation does not change [37], the proportion of such joint value assignments (ignoring their probability) [7], or the average structural impact (in terms of Hamming distance) on the best explanation [13]. A thorough overview of these and possibly other ways of quantifying MAP-independence would be welcome.
Finally, in order to test its practical usage, the formal concept introduced in this paper should be put to the empirical test in an actual decision support system to establish whether the justifications supported by the notion of MAP-independence actually help understand and appreciate the system's advise.