量化学习机器人：从Bengio演讲发散开来 探讨逻辑推理与机器学习

量化学习机器人：从Bengio演讲发散开来 探讨逻辑推理与机器学习初始化 SATNet 时，用户必须指定该层可以表示的最大子句数 m。通常希望将 m 的值设置的较低，因为低秩结构可以防止出现过拟合的问题，从而提高泛化能力。考虑到这种低秩结构，用户希望通过辅助变量在一定程度上提高层的表示能力。这里的高级直觉来自于布尔满足问题的合取范式（Conjunctive Normal Form，CNF）表示。向问题中添加额外的变量可以显著减少描述该问题所需的 CNF 子句的数量。【层初始化】使用 MAXSAT SDP 松弛和相关的坐标下降更新，作者创建了一个用于可满足性求解的深度网络层（SATNet）。令 I 表示已知赋值的 MAXSAT 变量的指数，O≡\I 对应于未知赋值的变量的指数。SATNet Layer 允许以概率或二进制的形式输入 z_l∈[0 1]，l∈I，然后输出未知变量 z_o∈[0 1]，o∈O 的赋值，这些未知变量具有类似的概率值或二进制值。令

（2）

这个问题是 MIN-UNSAT 的一个低秩（但非凸）公式，它等价于 MAXSAT。可以将这个公式重写为一个 SDP，并且已经由研究人员证明给定 k>sqrt(2n)的情况下，该式可以恢复最优 SDP 解。尽管它是非凸的，可以通过坐标下降来优化地解决公式（2）。特别是，依赖于 v_i 的客观条件表示为：

其中 s_i 是 S 的第 i 列向量。根据 ||v_i||=1 的约束条件，最小化 v_i 的值以得到坐标下降更新：

这些更新可证明能够收敛到 SDP(2)（即公式（2）对应的 SDP）的全局最优不动点。

使用 MAXSAT SDP 松弛和相关的坐标下降更新，作者创建了一个用于可满足性求解的深度网络层（SATNet）。令 I 表示已知赋值的 MAXSAT 变量的指数，O≡\I 对应于未知赋值的变量的指数。SATNet Layer 允许以概率或二进制的形式输入 z_l∈[0 1]，l∈I，然后输出未知变量 z_o∈[0 1]，o∈O 的赋值，这些未知变量具有类似的概率值或二进制值。令 Z_I 和 Z_O 分别表示全部的输入和输出任务。

通过 SDP(2)从输入 Z_I 生成输出 Z_O，SATNet Layer 的权重对应于 SDP 的低秩系数矩阵 S。完整的前向传递过程如图 1 所示，具体的层初始化和前向传递的步骤描述见算法 1。

图 1. MAXSAT 层的前向传递。该层将已知 MAXSAT 变量的离散或概率赋值作为输入，通过权重 S 的 MAXSAT SDP 松弛输出对未知变量赋值的猜测。

【层初始化】

初始化 SATNet 时，用户必须指定该层可以表示的最大子句数 m。通常希望将 m 的值设置的较低，因为低秩结构可以防止出现过拟合的问题，从而提高泛化能力。考虑到这种低秩结构，用户希望通过辅助变量在一定程度上提高层的表示能力。这里的高级直觉来自于布尔满足问题的合取范式（Conjunctive Normal Form，CNF）表示。向问题中添加额外的变量可以显著减少描述该问题所需的 CNF 子句的数量。

最后，令 k=sqrt(2n) 1，n 除了辅助变量外还捕获实际问题变量的数量。这也是本文的 MAXSAT 松弛公式（2）恢复其相关 SDP 的最优解所需的最小 k 值。

【放松层输入】

首先将其输入 Z_I 松弛成连续向量用于 SDP 公式（2）。也就是说，将每一层输入 z_l，l∈I 松弛到一个相关的随机单位向量 z_l，v_l∈R^k：

（4）

公式（4）满足：

（5）

其中，(v_l)^rand 为随机单位向量。

【通过 SDP 产生连续的输出松弛】

给定连续输入松弛 V_I，使用坐标下降更新公式（3）来计算连续输出松弛 v_o。值得注意的是，坐标下降更新只计算输出变量，也就是说，不计算其赋值作为层输入的变量。

前向传递的坐标下降算法详细说明在算法 2 中。该算法保留了计算 g_o 所需的Ω=VS^T 项，然后在每次内部迭代中通过秩 1 更新对其进行修改。因此，每次迭代的运行时间是 O(nmk)。