Outlier Explanation via Sum-Product Networks
This addresses the problem of identifying distinguishing features for outliers in data analysis, with potential applications in human decision-making, though it is incremental as it builds on existing outlier explanation frameworks.
The paper tackles the computational expense of existing outlier explanation methods by proposing a novel algorithm based on Sum-Product Networks (SPNs), which uses backwards elimination to efficiently compute outlier scores in feature subsets, achieving state-of-the-art results.
Outlier explanation is the task of identifying a set of features that distinguish a sample from normal data, which is important for downstream (human) decision-making. Existing methods are based on beam search in the space of feature subsets. They quickly becomes computationally expensive, as they require to run an outlier detection algorithm from scratch for each feature subset. To alleviate this problem, we propose a novel outlier explanation algorithm based on Sum-Product Networks (SPNs), a class of probabilistic circuits. Our approach leverages the tractability of marginal inference in SPNs to compute outlier scores in feature subsets. By using SPNs, it becomes feasible to perform backwards elimination instead of the usual forward beam search, which is less susceptible to missing relevant features in an explanation, especially when the number of features is large. We empirically show that our approach achieves state-of-the-art results for outlier explanation, outperforming recent search-based as well as deep learning-based explanation methods