论文标题
用多项式时间和延迟解释天真的贝叶斯和其他线性分类器
Explaining Naive Bayes and Other Linear Classifiers with Polynomial Time and Delay
论文作者
论文摘要
最近的工作提出了天真贝叶斯分类器（NBC）所谓的PI解释的计算。 PI解释是特征值对的子集最小值集，足以进行预测，并且已经使用最新的精确算法计算，这些算法是时间和空间上最差的指数。相比之下，我们表明，可以在对数线性时间内实现一个NBC的一个PI解释的计算，并且相同的结果也适用于更通用的线性分类器类别。此外，我们表明可以通过多项式延迟获得PI解释的枚举。实验结果证明了与早期工作相比，新算法的性能提高。实验结果还研究了衡量启发式解释质量的方法
Recent work proposed the computation of so-called PI-explanations of Naive Bayes Classifiers (NBCs). PI-explanations are subset-minimal sets of feature-value pairs that are sufficient for the prediction, and have been computed with state-of-the-art exact algorithms that are worst-case exponential in time and space. In contrast, we show that the computation of one PI-explanation for an NBC can be achieved in log-linear time, and that the same result also applies to the more general class of linear classifiers. Furthermore, we show that the enumeration of PI-explanations can be obtained with polynomial delay. Experimental results demonstrate the performance gains of the new algorithms when compared with earlier work. The experimental results also investigate ways to measure the quality of heuristic explanations
