Apr, 2011

知识编译中的相变：实验研究

PDF
TL;DR本文研究了知识编译中的相变现象，通过对随机 k-SAT 实例进行实验，发现编译结果存在易 - 难 - 易的规律，且大小峰值仅与子句数与变量数比例的固定值有关，大多数编译结果大小随变量数增加呈指数增长，但也存在一种相变现象，该相变由 DFA 的微结构决定，表现为大于 2 个变量的解可互换性随易 - 难 - 易规律的峰值有明显的相变现象，极大地影响 DFA 的大小。
发现论文，激发创造
  • 知识编译中的相变行为

    研究随机 k-CNF 公式的规模和编译时间行为，以及使用知识编译进行的大小和运行时行为的严格实证研究和分析，类似于 SAT / CSP 社区对相变行为的早期研究，我们鉴定了不同参数方面的有趣行为：子句密度和解密度，并总结我们的经验研究。

    Jul, 2020

  • 知识编译地图

    本文提供了一种知识编译的角度，分析了不同的编译方法（依据目标编译语言的简洁性与语言在多项式时间内支持的查询和转换的类别），并提供了一张知识编译图使新的编译方法能在已有方法的背景下进行分析。

    Jun, 2011

  • 2+p-SAT：典型情况复杂性与相变性质的关系

    这篇研究报告讨论了如何解决 NP-Complete 决策问题中的 “相位边界” 问题，介绍了在 K-SAT 中发生的相变的解析解和实验研究。其中，在计算代价随问题规模呈指数级增长的情况下，首次发现了 “随机一阶相变” 的本质，并提出了可能的搜索启发式算法改进方案来应对决策问题中的 “脊骨”。

    Oct, 1999

  • SAT 相变

    本文探讨了在随机 k-SAT 模型下，随着变量与子句的比例 r 的增加，满足问题的可满足性呈现相变现象，并在阈值点出现真值分配的突变，从而使得满足真值分配的相似度由之前开始相对差异变为非常相似的过程。

    May, 2000

  • 自顶向下计数模理论知识编译

    该研究讨论了 #SMT 的编译策略，提出了一种基于穷尽 DPLL (T) 搜索的自上而下的编译器。

    Jun, 2023

  • 高维几何相变的普适性观察，及其对现代数据分析与信号处理的影响

    本文研究高维组合几何中的相变与现代高维数据分析和信号处理中的相变之间的联系，并探讨了阈值的重要性和在不同问题中的应用。作者进行了广泛的计算实验和形式推断分析，证明了这些相变在一定条件下是普适的，但有限样本上的普适性则被拒绝。

    Jun, 2009

  • 结合 $k$-CNF 和 XOR 相变

    本文首次研究了随机 $k$-CNF-XOR 公式的可满足性，并证明了 $k$-CNF-XOR 公式以及 $k = 2$ 时的相变存在性，发现了服从 $k$-CNF 和 XOR 约束之间线性权衡的惊人相变现象，并且提供了 SAT 求解器在此相变中的性能实证结果。

    Feb, 2017

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

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

    Jun, 2015

  • 大型语言模型输出分布的相变

    通过统计距离量化输出生成中的分布变化，本研究利用物理学界提出的自动检测相变的统计方法，成功地将其应用于大型语言模型中，以发现新的行为状态和未探索的转变。

    May, 2024

  • 贝叶斯推断问题中的相变类型学

    本文通过对稀疏图上的推理问题的描述和分析，研究了随机块模型的相变以及在信息论上最优化问题变得容易但是在计算上仍具挑战性的的混合硬相位，并阐明了消息传递算法的贝叶斯最优性及其在这些问题中的作用，并通过数值模拟验证了该方法的有效性。

    Jun, 2018