按年被提到
20192020 · 2 次2026
数学、逻辑与理论›AI 数学与定理证明·arXiv:1905.12149 · cs.LG

SATNet: Bridging deep learning and logical reasoning using a differentiable satisfiability solver

SATNet:用可微分可满足性求解器连接深度学习与逻辑推理
Po-Wei Wang, Priya L. Donti, Bryan Wilder, Zico Kolter · 2019

把可微分 MAXSAT 求解器做成网络层,用样例学会数独

开始阅读 ↗PDFalphaXiv 讨论
被推荐 · 4 人首次 2019-06-03 · 最近 2022-12-23
4不同的人
4活跃月份
4讨论串
85被引(OpenAlex)

提出一个可微分(平滑化)的最大可满足性(MAXSAT)求解器层,可嵌入更大的深度学习系统。它基于求解对应半定规划(SDP)的快速坐标下降,并推导出通过 SDP 解的解析求导与高效反向传播。实验中仅用单比特监督就学会了奇偶函数,只靠样例学会了 9x9 数独,并与卷积网络结合解决了从图像到解的“视觉数独”。

HN 为什么提它

有人问神经网络能否做逻辑或约束求解时,评论者把它当作“可微分松弛的形式化求解器”这一方向的代表,也有人提到它学到的权重缺乏逻辑含义。

方法难度 4 / 5约 60 分钟经得起时间
读之前最好知道
1布尔可满足性(SAT/MAXSAT)
2半定规划(semidefinite programming)
3反向传播与可微分层
4坐标下降法

学习路径

读这篇之前,按顺序读书架上的 3 篇 · 参考文献来自 OpenAlex,顺序和要点由 Claude Code 排出

先看三条“让神经网络学会逻辑推理”的路线(可微分规则学习、SAT 求解学习、关系推理),再读 SATNet 如何把 MAXSAT 做成可微分层。

  1. 1
    Learning Explanatory Rules from Noisy Data从噪声数据中学习可解释的规则 · 2017

    可微分归纳逻辑编程,是把符号规则学习放进反向传播的代表,SATNet 要超越这类做法。

    读抓住用反向传播从样例学规则的思路,以及它对噪声数据的鲁棒性;不必深究实现细节。

  2. 2

    NeuroSAT 用单比特监督让网络学会判定可满足性,是 SATNet 最直接的对照物。

    读看它如何把 CNF 公式表示成图并做消息传递,以及只给可满足与否的单比特监督。

  3. 3
    Recurrent Relational Networks循环关系网络 · 2017

    循环关系网络能解数独,是 SATNet 数独实验的主要基线。

    读理解在对象图上做多步关系推理的思路,以及它在数独上的设置与效果。

  4. 4
    SATNet: Bridging deep learning and logical reasoning using a differentiable satisfiability solverSATNet:用可微分可满足性求解器连接深度学习与逻辑推理 · 2019 · 就是这篇

    把 MAXSAT 的 SDP 松弛做成可微分层,可从样例中同时学出约束。

    读抓住 SDP 松弛与坐标下降求解、解析求梯度的反向传播;数独实验看它如何学出规则。

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
推荐bglazer · 2020-05

“You might be interested in the line of work around differentiable relaxations of formal solvers”

推荐关注形式化求解器的可微松弛,SATNet 的可微 Max-SAT 层配合 ConvNet 可解数独
Symbolic mathematics finally yields to neural networks原评论 ↗
推荐AlexCoventry · 2020-06

“SATnet is an interesting paper, in this regard.”

称 SATNet 有意思,它从二值反馈学会数独,但学到的权重没有逻辑含义
Deep Learning – The “Why” Question (2018)原评论 ↗
引用bmc7505 · 2022-12

“There are architectures with layers which can approximate MAXSAT [1] (or rather, an SDP relaxation thereof), but I doubt this is what OP was referring to.”

指出有的层可通过 SDP 松弛近似 MAXSAT,但怀疑原帖说的不是它
Do Simpler Machine Learning Models Exist and How Can We Find Them?原评论 ↗
被提交为 story · 1 次