Efficient Algorithms for Generating Provably Near-Optimal Cluster Descriptors for Explainability
Efficient Algorithms for Generating Provably Near-Optimal Cluster Descriptors for Explainability
复制标题
DOI：
10.1609/aaai.v34i02.5525
复制
发表时间：
2020-02
期刊：
影响因子：
--
通讯作者：
Prathyush Sambaturu;Aparna Gupta;I. Davidson;S. Ravi;A. Vullikanti;A. Warren
中科院分区：
文献类型：
--
作者：
Prathyush Sambaturu;Aparna Gupta;I. Davidson;S. Ravi;A. Vullikanti;A. Warren
提高机器学习方法结果的可解释性已成为一个重要的研究目标。在这里，我们研究了通过扩展[Davidson等人，NeurIPS 2018]最近的一种方法来构建簇的简洁表示来使簇更易于解释的问题。给定对象集合S、S的分割π(分成簇)和标签宇宙T，使得S中的每个元素与标签的子集相关联，目标是为每个簇找到标签的代表性集合，使得这些集合是成对不相交的，并且所有代表的总大小被最小化。由于该问题一般是NP难的，因此我们提出了具有可证明性能保证的近似算法。我们还展示了解释来自数据集的集群的应用程序，包括代表不同威胁级别的基因组序列集群。
Improving the explainability of the results from machine learning methods has become an important research goal. Here, we study the problem of making clusters more interpretable by extending a recent approach of [Davidson et al., NeurIPS 2018] for constructing succinct representations for clusters. Given a set of objects S, a partition π of S (into clusters), and a universe T of tags such that each element in S is associated with a subset of tags, the goal is to find a representative set of tags for each cluster such that those sets are pairwise-disjoint and the total size of all the representatives is minimized. Since this problem is NP-hard in general, we develop approximation algorithms with provable performance guarantees for the problem. We also show applications to explain clusters from datasets, including clusters of genomic sequences that represent different threat levels.