句子决策图的相对简洁性
本文介绍了一种名为 sentential decision diagrams (SDDs) 的表达语言,证明了在布尔函数的表示中 SDDs 比 ordered binary decision diagrams (OBDDs) 更简洁,该结论解决了知识编译中的一个开放性问题,并且在人工智能和知识编译等领域有广泛的应用。
Jan, 2016
本文研究了如何将一个二进制神经网络的决策函数编译成可行的表示形式,如有序二进制决策图和命题决策图,并讨论了使用这些表示形式来验证神经网络的鲁棒性和计算期望鲁棒性的方法。此外,本文还提出了一种基于伪多项式时间算法编译单个神经元的高效方法,并在手写数字数据集中展示了两个神经网络的高准确度但鲁棒性不同的案例研究。最后,实验证明使用命题决策图可以获得神经网络的紧凑表示形式。
Apr, 2020
通过语法特征,我们为 Sentential Decision Diagrams(SDDs)推导出具有一般性的修订算法,并呈现了一个特殊的程序,以便于修订任务的直接操作。
Jan, 2022
结构化 d-DNNF、SDD 和 OBDD 之间存在可处理性转换和简洁性差距的问题,我们通过实验证明结构化 d-DNNF 不支持多项式时间的取反、析取和存在量词操作,并且存在一些函数,其具有等价的多项式大小的结构化 d-DNNF,但没有等价的 SDD 表示。我们还通过对算术电路(AC)的研究,将这个结果推广到 PSDD 和结构化 d-DNNF 的单调 AC 类似物之间,从而展示了简洁性差距。
Feb, 2024
本文表明,CNF 无法被编译成由原始图树宽参数化的固定参数大小的有序二元决策图(OBDD)。因此,我们为 OBDD 和 SDD 提供了参数化分离,并证明了所提出的下界还可以产生 OBDD 和 SDD 的古典(非参数化)分离。此外,我们还展示了对于 OBDD 的现有的最佳参数化上界实际上适用于关联图树宽参数化。
Aug, 2013
论文提出了关于大规模自然问题中精确概率推断效率的新极限,尤其是给出了关于知识编译到 SDD 和 DNNF 形式的新下限,并利用 SDD 大小与最佳划分通信复杂度的关系证明了一类大型问题的 SDD 大小的指数下限。
Jun, 2015
提出了两种版本的布尔函数的标记句子决策图(TSDDs)—— 零抑制版本零抑制句子决策图(ZTSDDs)以及标准版本标准句子决策图(STSDDs),证明了 STSDDs 的规范性并提供了在 TSDDS 上进行二进制操作的算法。在实验评估中,证明了四个版本的 TSDDs 在尺寸上具有优势。
Nov, 2023
本文提出了基于 SAT 的方法学习最优二元决策图(BDD),以更好地实现可解释的机器学习模型,并给出了一种整合兼容子树的方法,该方法与现有方法相比在预测质量和可解释性方面具有明显的优势。
Mar, 2022
该研究论文主要研究了基于二元决策图的 Pseudo-Boolean 约束编码技术,提出了使用系数分解方法克服爆炸性增长问题,并给出了第一个多项式广义弧一致的 ROBDD 编码算法。
Jan, 2014