江苏龙网

  1. 首页 > 人文 > >

从Bengio演讲发散开来：探讨逻辑推理与机器学习( 八 )


从Bengio演讲发散开来：探讨逻辑推理与机器学习文章插图
图 1. MAXSAT 层的前向传递 。 该层将已知 MAXSAT 变量的离散或概率赋值作为输入 ， 通过权重 S 的 MAXSAT SDP 松弛输出对未知变量赋值的猜测 。
从Bengio演讲发散开来：探讨逻辑推理与机器学习文章插图
【层初始化】
初始化 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：
从Bengio演讲发散开来：探讨逻辑推理与机器学习文章插图
（4）
公式（4）满足：
（5）
其中 ， (v_l)^rand 为随机单位向量 。
【通过 SDP 产生连续的输出松弛】
给定连续输入松弛 V_I ， 使用坐标下降更新公式（3）来计算连续输出松弛 v_o 。 值得注意的是 ， 坐标下降更新只计算输出变量 ， 也就是说 ， 不计算其赋值作为层输入的变量 。
前向传递的坐标下降算法详细说明在算法 2 中 。 该算法保留了计算 g_o 所需的Ω=VS^T 项 ， 然后在每次内部迭代中通过秩 1 更新对其进行修改 。 因此 ， 每次迭代的运行时间是 O(nmk) 。
从Bengio演讲发散开来：探讨逻辑推理与机器学习文章插图
【生成离散或概率输出】
给定坐标下降的松弛输出 V_O ， 层通过阈值或随机取整将这些输出转换为离散或概率变量赋值 Z_O 。 随机化舍入的主要思想是 ， 对于每一个 v_o ， o∈O ， 可以从单位球面上取一个随机超平面 r 并赋值 。
从Bengio演讲发散开来：探讨逻辑推理与机器学习文章插图
（6）
给定正确的权值 ， 这种随机取整过程保证了某些 NP-hard 问题的最佳期望逼近比 。 在训练期间 ， 没有明确地执行随机取整 。 相反 ， v_o 和 v_T 在给定 r 的同一侧的概率是：
从Bengio演讲发散开来：探讨逻辑推理与机器学习文章插图
（7）
在测试过程中 ， 既可以以相同的方式输出概率输出 ， 也可以通过阈值分割或随机舍入输出离散赋值 。 如果使用随机化舍入 ， 则执行多次舍入后将 z_o 设为使公式（1）中 MAXSAT 目标最大化的布尔解 。
最后 ， 作者讨论了后向传递 ， 即 ， 通过 SATNet layer 获得反向传播更新 ， 使其能够集成到神经网络中 。 基于层输出给定网络损失 l 的梯度δl/δZ_O ， 根据层输入和每层权重δl/δS 计算梯度δl/δZ_I 。 由于显式展开前向传递计算并存储中间 Jacobians 在时间和内存方面效率低下 ， 因此作者采用了高效的坐标下降算法推导出直接计算期望梯度的解析表达式 。 算法 1 总结了计算这些梯度计算的步骤 。
【从概率输出到连续松弛】
给定 δl/δZ_O ， 可以通过概率分配机制推导出 δl/δV_O：
从Bengio演讲发散开来：探讨逻辑推理与机器学习文章插图


推荐阅读


上一篇：长虹经销商被薅羊毛破产！巨亏电热水壶20万单，恳求消费者撤单

下一篇：10月最新版 BR2020+ACR13.0 一键装完即用