Modern neural networks obtain information about the problem and calculate the output solely from the input values. We argue that it is not always optimal, and the network's performance can be significantly improved by augmenting it with a query mechanism that allows the network to make several solution trials at run time and get feedback on the loss value on each trial. To demonstrate the capabilities of the query mechanism, we formulate an unsupervised (not dependant on labels) loss function for Boolean Satisfiability Problem (SAT) and theoretically show that it allows the network to extract rich information about the problem. We then propose a neural SAT solver with a query mechanism called QuerySAT and show that it outperforms the neural baseline on a wide range of SAT tasks and the classical baselines on SHA-1 preimage attack and 3-SAT task.
翻译:现代神经网络获取关于问题的信息,并仅从输入值中计算输出值。 我们争辩说,它并不总是最理想的,而且网络的性能可以通过一个查询机制得到显著改善,这个查询机制使网络能够在运行时进行数项解决方案试验,并获得关于每次试验损失价值的反馈。为了证明查询机制的能力,我们为Boolean可满足性问题(SAT)设计了一个不受监督(不依赖标签)的损失损失函数,并在理论上表明它允许网络提取关于该问题的丰富信息。 然后我们提议一个神经SAT解答器,其查询机制称为QuerySAT, 并显示它在一系列广泛的SAT任务上超过了神经基线以及SHA-1图像前攻击和3SAT任务上的典型基线。