基于理论的规范决策图
通过语法特征,我们为 Sentential Decision Diagrams(SDDs)推导出具有一般性的修订算法,并呈现了一个特殊的程序,以便于修订任务的直接操作。
Jan, 2022
本文旨在确定哪些布尔函数可以由小型的 SDDs 表示,同时将多项式大小的布尔函数表示集合与来自 Darwiche 和 Marquis 经典知识编译地图的表示类型进行比较。最主要的结果是通过等效的不明确的非确定性 OBDDs 对 SDDs 进行准多项式仿真,回答了 SDDs 和超过 OBDDs 的 FBDDs 相对简洁性之间的一个开放问题。
Feb, 2018
本文介绍了一种名为 sentential decision diagrams (SDDs) 的表达语言,证明了在布尔函数的表示中 SDDs 比 ordered binary decision diagrams (OBDDs) 更简洁,该结论解决了知识编译中的一个开放性问题,并且在人工智能和知识编译等领域有广泛的应用。
Jan, 2016
提出了两种版本的布尔函数的标记句子决策图(TSDDs)—— 零抑制版本零抑制句子决策图(ZTSDDs)以及标准版本标准句子决策图(STSDDs),证明了 STSDDs 的规范性并提供了在 TSDDS 上进行二进制操作的算法。在实验评估中,证明了四个版本的 TSDDs 在尺寸上具有优势。
Nov, 2023
本文研究了如何将一个二进制神经网络的决策函数编译成可行的表示形式,如有序二进制决策图和命题决策图,并讨论了使用这些表示形式来验证神经网络的鲁棒性和计算期望鲁棒性的方法。此外,本文还提出了一种基于伪多项式时间算法编译单个神经元的高效方法,并在手写数字数据集中展示了两个神经网络的高准确度但鲁棒性不同的案例研究。最后,实验证明使用命题决策图可以获得神经网络的紧凑表示形式。
Apr, 2020
本文提出一种新的表示语言 CCDD,并利用其支持的多项式算法在模型计数和一致采样上显著改进于目前最先进的 Decision-DNNF,SDD 和 OBDD [AND] 编译器,以及在 CNF 上开发模型计数器和一致采样器。
Feb, 2022
本研究比较了不同 Zero-suppressed Decision Diagrams 变体在多智能体系统的符号编码中的记忆使用情况,结果表明使用合适的 ZDDs 可以显著减少 BDDs 的记忆使用量。
Jul, 2023
该研究论文主要研究了基于二元决策图的 Pseudo-Boolean 约束编码技术,提出了使用系数分解方法克服爆炸性增长问题,并给出了第一个多项式广义弧一致的 ROBDD 编码算法。
Jan, 2014
本文提出了基于 SAT 的方法学习最优二元决策图(BDD),以更好地实现可解释的机器学习模型,并给出了一种整合兼容子树的方法,该方法与现有方法相比在预测质量和可解释性方面具有明显的优势。
Mar, 2022
本文介绍了可分解否定范式(DNNF)作为可行的命题理论形式,并提供了一些在多项式时间内可以执行的强大逻辑操作。在此基础上,本文提出了将任何合取范式(CNF)转化为 DNNF 的算法,并提供其空间和时间复杂度上的结构保证。同时它也介绍了将有序二叉决策图(OBDD)表示的命题理论转换为等价的 DNNF 的线性时间算法。接着,介绍了采用新的操作在 d-DNNF 上遍历之后实现线性时间、完整的信念修正系统。
Mar, 2000