Apr, 2020

关于二元神经网络可计算性表示的研究

PDF
TL;DR本文研究了如何将一个二进制神经网络的决策函数编译成可行的表示形式，如有序二进制决策图和命题决策图，并讨论了使用这些表示形式来验证神经网络的鲁棒性和计算期望鲁棒性的方法。此外，本文还提出了一种基于伪多项式时间算法编译单个神经元的高效方法，并在手写数字数据集中展示了两个神经网络的高准确度但鲁棒性不同的案例研究。最后，实验证明使用命题决策图可以获得神经网络的紧凑表示形式。
发现论文，激发创造
  • 句子决策图的相对简洁性

    本文旨在确定哪些布尔函数可以由小型的 SDDs 表示，同时将多项式大小的布尔函数表示集合与来自 Darwiche 和 Marquis 经典知识编译地图的表示类型进行比较。最主要的结果是通过等效的不明确的非确定性 OBDDs 对 SDDs 进行准多项式仿真，回答了 SDDs 和超过 OBDDs 的 FBDDs 相对简洁性之间的一个开放问题。

    Feb, 2018

  • SDDs 比 OBDDs 更为简洁

    本文介绍了一种名为 sentential decision diagrams (SDDs) 的表达语言，证明了在布尔函数的表示中 SDDs 比 ordered binary decision diagrams (OBDDs) 更简洁，该结论解决了知识编译中的一个开放性问题，并且在人工智能和知识编译等领域有广泛的应用。

    Jan, 2016

  • 命题决策图中的信念修正

    通过语法特征，我们为 Sentential Decision Diagrams（SDDs）推导出具有一般性的修订算法，并呈现了一个特殊的程序，以便于修订任务的直接操作。

    Jan, 2022

  • 基于提升算法的线性阈值函数 BDDs 构建及其在神经网络验证中的应用

    该论文提出了一种将神经网络转化为特殊形式的二元决策图 (BDD) 的方法，并提出了结合该方法的新提升算法，以及用于计算最终布尔表达式的方法。

    Jun, 2023

  • 结构化的 d-DNNF 不封闭于否定

    结构化 d-DNNF、SDD 和 OBDD 之间存在可处理性转换和简洁性差距的问题，我们通过实验证明结构化 d-DNNF 不支持多项式时间的取反、析取和存在量词操作，并且存在一些函数，其具有等价的多项式大小的结构化 d-DNNF，但没有等价的 SDD 表示。我们还通过对算术电路（AC）的研究，将这个结果推广到 PSDD 和结构化 d-DNNF 的单调 AC 类似物之间，从而展示了简洁性差距。

    Feb, 2024

  • 贝叶斯网络分类器的推理

    本文介绍了一种基于 Ordered Decision Diagrams（ODDs）的贝叶斯网络分类器的推理方法，包括将任何朴素贝叶斯分类器转换成 ODDs 的算法，以及使用 ODDs 进行等价性测试和 CPT 更改范围的特性分析。

    Oct, 2012

  • 知识编译的新极限及其在精确模型计数中的应用

    论文提出了关于大规模自然问题中精确概率推断效率的新极限，尤其是给出了关于知识编译到 SDD 和 DNNF 形式的新下限，并利用 SDD 大小与最佳划分通信复杂度的关系证明了一类大型问题的 SDD 大小的指数下限。

    Jun, 2015

  • 使用 MaxSAT 优化二进制决策图以进行分类

    本文提出了基于 SAT 的方法学习最优二元决策图（BDD），以更好地实现可解释的机器学习模型，并给出了一种整合兼容子树的方法，该方法与现有方法相比在预测质量和可解释性方面具有明显的优势。

    Mar, 2022

  • 关于有界树宽的 CNFs 的 OBDDs

    本文表明，CNF 无法被编译成由原始图树宽参数化的固定参数大小的有序二元决策图（OBDD）。因此，我们为 OBDD 和 SDD 提供了参数化分离，并证明了所提出的下界还可以产生 OBDD 和 SDD 的古典（非参数化）分离。此外，我们还展示了对于 OBDD 的现有的最佳参数化上界实际上适用于关联图树宽参数化。

    Aug, 2013

  • 基于理论的规范决策图

    决策图是一种有效表达命题公式的强大工具，本文介绍了一种通用技术将决策图应用于 SMT 级别，并可产生理论规范的 T-DD，从而解决了现有技术的一些限制。

    Apr, 2024