{'fraction_non_alphanumeric': 0.035541310541310545, 'fraction_numerical': 0.00405982905982906, 'mean_word_length': 4.587345801830481, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Finding dissimilar explanations in Bayesian networks: Complexity results

Finding the most probable explanation for observed variables in a Bayesian network is a notoriously intractable problem, particularly if there are hidden variables in the network. In this paper we examine the complexity of a related problem, that is, the problem of finding a set of sufficiently dissimilar, yet all plausible, explanations. Applications of this problem are, e.g., in search query results (you won't want 10 results that all link to the same website) or in decision support systems. We show that the problem of finding a 'good enough' explanation that differs in structure from the best explanation is at least as hard as finding the best explanation itself.


Introduction
A vital computational problem within probabilistic graphical models such as Bayesian networks is the problem of finding the mode or most probable explanation of a set of variables given observed values for other variables in the network. When the network includes latent or hidden variables (i.e., variables that have neither been observed nor are of interest for the explanation) this problem is known as Partial MAP; the explanation sought is the MAP explanation, i.e., the joint value assignment to the explanation variables that has maximum posterior probability. In this paper we are interested in the problem of finding not specifically the MAP explanation, but other explanations that have desirable properties. There are two distinct reasons why we may be interested in alternative explanations: 1. As a means of approximating the MAP explanation. Partial MAP is a highly intractable problem [1,6] and we may find an acceptable approximation thereof (to be further explicated later) 'good enough'; 2. To obtain 'alternative good' explanations in addition to the MAP explanation, to allow us to explore several alternatives (e.g. search results) or to cover for a set of likely explanations (e.g. medical conditions).
'Good enough' and 'alternative good' explanations are conceptually different when we look at the structure of the explanation as compared to the MAP explanation; that is, how similar or dissimilar the joint value assignments (of the MAP explanation and the alternative explanation) are. In the first case we are more than happy to obtain an explanation that is almost identical to the MAP explanation; in fact, in some problem domains this might even be a prerequisite. For example, in computational cognitive modeling an explanation that does not resemble the MAP explanation would not be acceptable as a valid approximation of the MAP explanation, even if it has a comparable probability. In the second case, our goal is to find alternative explanations that are structurally different yet are still plausible. For example, in response to a search query we don't want to end up with ten results that refer to minor variations of essentially the same web-page, even if they happen to be the most probable given the query.
Note that structure approximation (where we seek an explanation with Hamming distance at most d of the MAP explanation) is really different from value approximation (where we seek an explanation with almost-as-high probability, e.g. within ratio r of the MAP explanation) and from rank approximation (where we seek an explanation that is within the m best explanations) [7]. These notions are really orthogonal, as Figure 1 will reveal. Current algorithms that seek to find alternative explanations by exploring local maxima (e.g. [2,3,5]) may fare well if the explanatory landscape is as in the "local maxima" panel of Figure 1. They might not find good explanations, or take a lot of time, if the landscape is in either of the other panels of Figure  1. However, the computational complexity of this problem has not yet been investigated. In this paper we are specifically interested in explanations that rank well (are within the best m explanations) and that are either structurally similar or dissimilar; that is, we complement the results of [7]. In this paper we will further explicate both problems and explore the computational complexity of both of them. We will start with offering some necessary preliminaries and sharing our notational conventions. In Section 3 we will formalize both problems (in several variants) and show that both of them are at least as hard as Partial MAP itself. We will also further elaborate on the exact complexity of decision versions of both problems which turns out to be non-trivial. We conclude in Section 4.

Preliminaries
In this section we introduce our notational conventions. Specifically we will cover Bayesian networks, the complexity classes PP and NP PP , one-Turing reductions, and formal definitions of the approximation notions we will use in the paper. The reader is referred to textbooks like [4] (specifically complexity in Bayesian networks) and to [7] (for a formal treatment of MAP approximations) for more background.
A Bayesian network B = (G B , Pr) is a probabilistic graphical model that succinctly represents a joint probability distribution Pr Graphical depiction of possible relationships between similarity and probability of explanations, with on the X-axis defines an order of the explanations according to their similarity to the best explanation. In "linear decrease" the structure and the probability correlate almost completely; in "random noise" almost not at all. There can be a sole peak of probability mass ("lonely mountain") with all other explanations having almost zero probability. Alternatively, there can be several structurally distinct "local maxima" of probability mass. Particularly in the latter case it might be interesting to look at dissimilar explanations that have a relatively high probability. 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)dependences 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.
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 (referred to as intermediate variables) this problem is typically referred to as Partial MAP. We use the following formal definition: is partitioned into a set of evidence nodes E with a joint value assignment e, a set of intermediate nodes I, and an explanation set H. Output: A joint value assignment h to H such that for all joint value assignments h to H, Pr(h | e) ≥ Pr(h | e).
The following notation is taken from [7]. For an arbitrary Partial MAP instance {B, H, E, I, e}, let cansol B refer to the set of candidate solutions, with optsol B ∈ cansol B denoting the optimal solution (or, in case of multiple solutions with the same posterior probability, one of the optimal solutions) to the Partial MAP instance; we will informally refer to this solution as the MAP explanation. When cansol B is ordered according to the probability of the candidate solutions (breaking ties between candidate solutions with the same probability arbitrarily), then optsol 1...m B refers to the set of the first m elements in cansol B , viz. the m most probable solutions to the Partial MAP instance.
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 is consistent with the sampling variant of the Chernoff bound: The number of samples M needed to increase the probability of acceptance of Yes-instances to 1 − δ is at least ln( 1 / √ δ) 2 ; when = 1 /2 n then M is exponential in the input size. PP hence is 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 class NP PP are highly intractable.
A decision variant of Partial MAP is known to be NP PP -complete, even for binary variables, indegree at most 2, and under the assumption that there exists at least one joint value assignment h such that Pr(h, e) > 0 [8,9]. In the intractability proofs in Section 3 we will assume, without loss of generality, that these constraints hold for all Bayesian networks B under consideration. As we use reductions from function problems, not decision problems, our reductions are formally polynomial-time one-Turing reductions. A function f one-Turing reduces to g (notation f ≤ FP 1−T g) if there are functions t 1 and t 2 such that for all x, f (x) = t 1 (x, g(x, t 2 (x))) [10, p.5].
We finish this section be repeating the following formal definition of rankapproximation of Partial MAP from [7]; we will build on this definition in the next section.

Main results
Let d H be the Hamming distance between two joint value assignments. We define the following two problem variants to Partial MAP, where m and d are arbitrary constants: (m, d)-Similar Partial MAP Instance: As in Partial MAP. Output: An explanation approxsol B ∈ cansol B that m-rank-approximates optsol B and where d H (approxsol B , optsol B ) ≤ d, or special symbol ∅ if no such explanation exists.
(m, d)-Dissimilar Partial MAP Instance: As in Partial MAP. Output: An explanation approxsol B ∈ cansol B that m-rank-approximates optsol B and where d H (approxsol B , optsol B ) ≥ d, or special symbol ∅ if no such explanation exists.
We will prove that both problems are NP PP -hard by reduction from Partial MAP, even for binary variables with indegree at most 2. We will start with the construction for (m, d)-Similar Partial MAP without the latter constraints and prove NP PP -hardness ( Figure 2, panel a), and then adapt it to contain only binary variables and indegree at most 2 (panel b). Then we show how this construction can be extended to prove NP PP -hardness of (m, d)-Dissimilar Partial MAP (panel c).  Note that m and d are constants and not part of the input. If we would make them part of the input, then unary notation would be necessary as the number of nodes added would otherwise be exponential in the binary representation of m and d. However, since m ≤ 2 n (where n denotes the number of variables in B) the reduction would then not be polynomial in the Partial MAP instance any more. Hence, we require m (and d) to be a constant.

On membership in NP PP
As explicated before, Partial MAP has an NP PP -complete decision variant [9]. Is it likely that appropriate decision variants of Similar Partial MAP and Dissimilar Partial MAP are also in NP PP ? We can check in polynomial time, using the MAP explanation optsol B and the approximation approxsol B ∈ cansol B , that the Hamming distance d H (approxsol B , optsol B ) is as promised. However, a verification algorithm for (m, d)-Similar Partial MAP and (m, d)-Dissimilar Partial MAP should also verify that approxsol B actually is within the m best explanations, and finding the m-th best explanation is known to be FP PP PP -complete [8]. Hence, it is unlikely that (m, d)-Similar Partial MAP and (m, d)-Dissimilar Partial MAP have an NP PP -complete decision variant.

Conclusion
In this short paper we elaborated on the computational complexity of finding MAP explanations that are almost-as-good as the most probable one (where 'almost-as-good' was defined by rank) and that are sufficiently similar or dissimilar to the most probable explanation. We found that these problems are NP PP -hard, that is, not easier than the Partial MAP problem itself. An attempt to extend this proof construct to include value-approximation did not succeed, as the proof constructs really require that all explanations in approxsol B ∈ optsol 1...m B have the same probability. In an extreme case it might be that we have just two explanations for a given Partial MAP problem, where Pr(h | e) = 1 /2 + and Pr(¬h | e) = 1 /2 − , and any non-uniform probability assignment to the additional variables in the explanation set will destroy the proof.
In future work we'd like to extend our results to value-approximation as well as rank-approximation. It might be relevant to investigate the complexity of these problems in constrained structures, such as polytrees, where the Partial MAP problem nonetheless remains NP-hard.