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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Local Interpretable Model-agnostic Explanations of Bayesian Predictive Models via Kullback-Leibler Projections
We introduce a method, KL-LIME, for explaining predictions of Bayesian predictive models by projecting the information in the predictive distribution locally to a simpler, interpretable explanation model. The proposed ap…
Variable SelectionOn the Complexity of Finding Second-Best Abductive Explanations
While looking for abductive explanations of a given set of manifestations, an ordering between possible solutions is often assumed. The complexity of finding/verifying optimal solutions is already known. In this paper we…
On the Hardness of Computing Counterfactual and Semifactual Explanations in XAI
Providing clear explanations to the choices of machine learning models is essential for these models to be deployed in crucial applications. Counterfactual and semi-factual explanations have emerged as two mechanisms for…
Interpretable Measures of Conceptual Similarity by Complexity-Constrained Descriptive Auto-Encoding
Quantifying the degree of similarity between images is a key copyright issue for image-based machine learning. In legal doctrine however, determining the degree of similarity between works requires subjective analysis, a…
Descriptivetext similarityA new Initial Centroid finding Method based on Dissimilarity Tree for K-means Algorithm
Cluster analysis is one of the primary data analysis technique in data mining and K-means is one of the commonly used partitioning clustering algorithm. In K-means algorithm, resulting set of clusters depend on the choic…
Clustering