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
翻译:外部解释是确定一系列特征的任务,将样本与正常数据区别开来,这对下游(人)决策十分重要。现有方法基于对地物子集空间的光束搜索。它们很快变得计算成本高昂,因为每个特性子集都需要从头开始运行一个超前检测算法。为了缓解这一问题,我们提议了一个新的基于总产值网络(SPNs)的外部解释算法,这是一个概率性电路的类别。我们的方法利用了SPNs中边际推断的可移动性来计算特征子集的中分。通过使用SPNs,可以进行后向消除,而不是通常的远方波段搜索,因为通常的远方搜索不太容易在解释中遗漏相关特征,特别是在特征数量很大的情况下。我们的经验表明,我们的方法在外部解释方面达到了最先进的结果,超过了最近的搜索和深入的学习解释方法。