Learning Symmetric Rules with SATNet
SATNet is a differentiable constraint solver with a custom backpropagation
algorithm, which can be used as a layer in a deep-learning system. It is a
promising proposal for bridging deep learning and logical reasoning. In fact,
SATNet has been successfully applied to learn, among others, the rules of a
complex logical puzzle, such as Sudoku, just from input and output pairs where
inputs are given as images. In this paper, we show how to improve the learning
of SATNet by exploiting symmetries in the target rules of a given but unknown
logical puzzle or more generally a logical formula. We present SymSATNet, a
variant of SATNet that translates the given symmetries of the target rules to a
condition on the parameters of SATNet and requires that the parameters should
have a particular parametric form that guarantees the condition. The
requirement dramatically reduces the number of parameters to learn for the
rules with enough symmetries, and makes the parameter learning of SymSATNet
much easier than that of SATNet. We also describe a technique for automatically
discovering symmetries of the target rules from examples. Our experiments with
Sudoku and Rubik's cube show the substantial improvement of SymSATNet over the
baseline SATNet.