Finding dissimilar explanations in Bayesian networks: Complexity results
This addresses the need for diverse explanations in applications like search queries or decision support systems, but it is incremental as it focuses on complexity analysis rather than a practical solution.
The paper tackles the problem of finding a set of sufficiently dissimilar yet plausible explanations in Bayesian networks, showing that this task is at least as computationally hard as finding the single most probable explanation.
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.