研究布尔函数的低树宽多项式阈值表示,提升模型可解释性。
Polynomial Threshold Functions of Bounded Tree-Width: Some Explainability and Complexity Aspects
- 用低树宽多项式表示布尔函数,简化复杂计算
- 在贝叶斯网络分类器中实现可解释性改进
- 揭示正系数与一般多项式阈值函数的表达能力差异
多元多项式的树宽定义为对应项的超图的树宽。Makowsky 和 Meer 将具有有界树宽的多元多项式作为新稀疏性条件,使得原本难解的问题在该条件下可多项式求解。本文研究布尔变量情形下的类似问题:将布尔函数表示为多项式符号的形式称为多项式阈值表示。我们分析了可由有界树宽多项式阈值表示的布尔函数,并在贝叶斯网络分类器(一种概率图模型)中提出两项应用,均属于可解释人工智能(XAI)领域,旨在应对当前机器学习模型的黑箱特性。此外,我们还给出了正系数多项式阈值函数与一般多项式阈值函数之间的表达能力分离结果。
原文摘要 · Abstract (English)
The tree-width of a multivariate polynomial is the tree-width of the hypergraph with hyperedges corresponding to its terms. Multivariate polynomials of bounded tree-width have been studied by Makowsky and Meer as a new sparsity condition that allows for polynomial solvability of problems which are intractable in general. We consider a variation on this theme for Boolean variables. A representation of a Boolean function as the sign of a polynomial is called a polynomial threshold representation. We discuss Boolean functions representable as polynomial threshold functions of bounded tree-width and present two applications to Bayesian network classifiers, a probabilistic graphical model. Both applications are in Explainable Artificial Intelligence (XAI), the research area dealing with the black-box nature of many recent machine learning models. We also give a separation result between the representational power of positive and general polynomial threshold functions.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。