从均匀随机解中学习k-CNF公式，样本量大幅降低
Learning CNF formulas from uniform random solutions in the local lemma regime
- 基于洛瓦兹局部引理条件，用极少样本精确还原有界交集的k-CNF
- 在可满足性阈值附近，仅需约n^{exp(-√k)}样本即可学习
- 适用于需要高效布尔模型学习的研究者，如机器学习与理论计算机
我们研究从独立同分布的均匀随机解中学习n变量k-CNF公式Φ的问题，这等价于学习具有k元硬约束的布尔马尔可夫随机场（MRF）。重访Valiant算法（Commun. ACM'84），我们证明该算法可在洛瓦兹局部引理型条件下，仅用O(log n)样本精确学习具有有界子句交集的k-CNF；同时，在可满足性阈值附近，仅需˜O(n^{exp(-√k)})样本即可学习随机k-CNF。这些结果显著优于此前O(n^k)的样本复杂度。我们进一步建立了在独立同分布均匀随机解下，精确与近似学习的信息论下界。
原文摘要 · Abstract (English)
We study the problem of learning a $n$-variables $k$-CNF formula $Φ$ from its i.i.d. uniform random solutions, which is equivalent to learning a Boolean Markov random field (MRF) with $k$-wise hard constraints. Revisiting Valiant's algorithm (Commun. ACM'84), we show that it can exactly learn (1) $k$-CNFs with bounded clause intersection size under Lovász local lemma type conditions, from $O(\log n)$ samples; and (2) random $k$-CNFs near the satisfiability threshold, from $\widetilde{O}(n^{\exp(-\sqrt{k})})$ samples. These results significantly improve the previous $O(n^k)$ sample complexity. We further establish new information-theoretic lower bounds on sample complexity for both exact and approximate learning from i.i.d. uniform random solutions.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。