知识编译地图
本文研究了知识编译中的相变现象,通过对随机 k-SAT 实例进行实验,发现编译结果存在易 - 难 - 易的规律,且大小峰值仅与子句数与变量数比例的固定值有关,大多数编译结果大小随变量数增加呈指数增长,但也存在一种相变现象,该相变由 DFA 的微结构决定,表现为大于 2 个变量的解可互换性随易 - 难 - 易规律的峰值有明显的相变现象,极大地影响 DFA 的大小。
Apr, 2011
研究随机 k-CNF 公式的规模和编译时间行为,以及使用知识编译进行的大小和运行时行为的严格实证研究和分析,类似于 SAT / CSP 社区对相变行为的早期研究,我们鉴定了不同参数方面的有趣行为:子句密度和解密度,并总结我们的经验研究。
Jul, 2020
讨论了 Pearlian 结构因果模型中用于限定部分可辨识查询(如反事实推断)边界的问题,并提出了一种迭代 EM 方案,通过对初始化参数进行抽样,得到这些边界的内部近似。该方法需要对共享相同结构方程和拓扑结构、但具有不同外生概率的模型进行多次(贝叶斯网络)查询,因此将底层模型编译成算术电路具有优势,从而实现了显著的推理加速。通过单一的符号知识编译,我们展示了如何获得具有符号参数的电路结构,以在计算不同查询时将其替换为实际值。此外,我们还讨论了进一步加速边界计算的并行化技术。与标准贝叶斯网络推断相比,实验证明了明显的计算优势,加速比可达一个数量级。
Oct, 2023
本文介绍了一种用于提高试探性推理效率的一阶知识编译技术,通过将关系概率模型编译成低级别程序,从而比数据结构提供更多的优化,为新式试探推理技术提供了现实基础,探讨了两个问题。
Jun, 2016
该论文提出了一种自适应神经编译框架来解决高效节目的学习问题,并展示了如何使用可微表示将程序编译为不同 iable 的表示,并通过考虑输入数据分布来优化这种表示,以实现为给定数据分布学习特定调整算法的目标。
May, 2016
本文提出一种新的表示语言 CCDD,并利用其支持的多项式算法在模型计数和一致采样上显著改进于目前最先进的 Decision-DNNF,SDD 和 OBDD [AND] 编译器,以及在 CNF 上开发模型计数器和一致采样器。
Feb, 2022
本文介绍了用于解决量化扩展逻辑编程中的第二级推理任务的算法框架 Second Level Algebraic Model Counting (2AMC),探讨了使用知识编译技术降低处理效率时的需要考虑变量阶数限制问题,进一步提出并实现了一种静态生成约束的策略,并在多个任务和基准测试上评估了有效性。
May, 2022
论文提出了关于大规模自然问题中精确概率推断效率的新极限,尤其是给出了关于知识编译到 SDD 和 DNNF 形式的新下限,并利用 SDD 大小与最佳划分通信复杂度的关系证明了一类大型问题的 SDD 大小的指数下限。
Jun, 2015
研究表明,通过嵌入知识图谱的向量空间,可以递归应用于回答路径查询来解决知识图谱中缺失事实的问题。引入新的 “组合性” 训练目标,大大提高了所有模型回答路径查询的能力,并在标准知识库完成任务上取得了新的最佳结果。
Jun, 2015