We propose the Neural Logic Machine (NLM), a neural-symbolic architecture for both inductive learning and logic reasoning. NLMs exploit the power of both neural networks---as function approximators, and logic programming---as a symbolic processor for objects with properties, relations, logic connectives, and quantifiers.   After being trained on small-scale tasks (such as sorting short arrays), NLMs can recover lifted rules, and generalize to large-scale tasks (such as sorting longer arrays). In our experiments, NLMs achieve perfect generalization in a number of tasks, from relational reasoning tasks on the family tree and general graphs, to decision making tasks including sorting arrays, finding shortest paths, and playing the blocks world. Most of these tasks are hard to accomplish for neural networks or inductive logic programming alone. Deep learning has achieved great success in various applications such as speech recognition (Hinton et al., 2012) , image classification (Krizhevsky et al., 2012; He et al., 2016) , machine translation BID21 Bahdanau et al., 2015; Wu et al., 2016; Vaswani et al., 2017) , and game playing (Mnih et al., 2015; BID17 . Starting from Fodor & Pylyshyn (1988) , however, there has been a debate over the problem of systematicity (such as understanding recursive systems) in connectionist models (Fodor & McLaughlin, 1990; Hadley, 1994; Jansen & Watter, 2012) .Logic systems can naturally process symbolic rules in language understanding and reasoning. Inductive logic programming (ILP) BID7 BID8 Friedman et al., 1999) has been developed for learning logic rules from examples. Roughly speaking , given a collection of positive and negative examples, ILP systems learn a set of rules (with uncertainty) that entails all of the positive examples but none of the negative examples. Combining both symbols and probabilities, many problems arose from high-level cognitive abilities, such as systematicity, can be naturally resolved. However, due to an exponentially large searching space of the compositional rules, it is difficult for ILP to scale beyond small-sized rule sets (Dantsin et al., 2001; Lin et al., 2014; Evans & Grefenstette, 2018) .To make the discussion concrete, let us consider the classic blocks world problem BID10 Gupta & Nau, 1992) . As shown in Figure 1 , we are given a set of blocks on the ground. We can move a block x and place it on the top of another block y or the ground, as long as x is moveable and y is placeable. We call this operation Move(x, y). A block is said to be moveable or placeable if there are no other blocks on it. The ground is always placeable, implying that we can place all blocks on the ground. Given an initial configuration of blocks world, our goal is to transform it into a target configuration by taking a sequence of Move operations.Although the blocks world problem may appear simple at first glance, four major challenges exist in building a learning system to automatically accomplish this task:1. The learning system should recover a set of lifted rules (i.e., rules that apply to objects uniformly instead of being tied with specific ones) and generalize to blocks worlds which contain more blocks than those encountered during training. To get an intuition on this, we refer the readers who are not familiar with the blocks world domain to the task of learning to sort arrays (e.g.,In this paper, we propose Neural Logic Machines (NLMs) to address the aforementioned challenges. In a nutshell, NLMs offer a neural-symbolic architecture which realizes Horn clauses (Horn, 1951) in first-order logic (FOL). The key intuition behind NLMs is that logic operations such as logical ANDs and ORs can be efficiently approximated by neural networks, and the wiring among neural modules can realize the logic quantifiers.The rest of the paper is organized as follows. We first revisit some useful definitions in symbolic logic systems and define our neural implementation of a rule induction system in Section 2. As a supplementary, we refer interested readers to Appendix A for implementation details. In Section 3 we evaluate the effectiveness of NLM on a broad set of tasks ranging from relational reasoning to decision making. We discuss related works in Section 4, and conclude the paper in Section 5. ILP and relational reasoning. Inductive logic programming (ILP) BID7 BID8 Friedman et al., 1999 ) is a paradigm for learning logic rules derived from a limited set of rule templates from examples. Being a powerful way of reasoning over discrete symbols, it is successfully applied to various language-related problems, and has been integrated into modern learning frameworks (Kersting et al., 2000; BID14 Kimmig et al., 2012) . Recently, Evans & Grefenstette (2018) introduces a differentiable implementation of ILP which works with connectionist models such as CNNs. Sharing a similar spirit, BID15 introduces an end-to-end differentiable logic proving system for knowledge base (KB) reasoning. A major challenge of these approaches is to scale up to a large number of complex rules. Searching a rule as complex as our ShouldMove example in Appendix E from scratch is beyond the scope of most systems that use weighted symbolic rules generated from templates.As shown in Section 2.4, both computational complexity and parameter size of the NLM grow polynomially w.r.t. the number of allowed predicates (in contrast to the exponential dependence in ∂ILP (Evans & Grefenstette, 2018)), but factorially w.r.t. the breadth (max arity, same as ∂ILP). Therefore, our method can deal with more complex tasks such as the blocks world which requires using a large number of intermediate predicates, while ∂ILP fails to search in such a large space.Our paper also differs from existing approaches on using neural networks to augment symbolic rule induction BID1 BID3 . Specifically, we have no rule designed by humans as the input or the knowledge base for the model. NLMs are general neural architectures for learning lifted rules from only input-output pairs.Our work is also related to symbolic relational reasoning, which has a wide application in processing discrete data structures such as knowledge graphs and social graphs (Zhu et al., 2014; Kipf & Welling, 2017; Zeng et al., 2017; Yang et al., 2017) . Most symbolic relational reasoning approaches (e.g., Yang et al., 2017; BID15 are developed for KB reasoning, in which the predicates on both sides of a rule is known in the KB. Otherwise, the complexity grows exponentially in the number of used rules for a conclusion, which is the case in the blocks world. Moreover, Yang et al. FORMULA2 considers rues of the form query(Y, X) ← R n (Y, Z n ) ∧ · · · ∧ R 1 (Z 1 , X), which is not for general reasoning. The key of BID15 and Campero et al. (2018) is to learn subsymbolic embeddings of entities and predicates for efficient KB completion, which differs from our focus. While NLMs can scale up to complex rules, the number of objects/entities or relations should be bounded as a small value (e.g., < 1000), since all predicates are represented as tensors. This is, to some extent, in contrast with the systems developed for knowledge base reasoning. We leave the scalability of NLMs to large entity sets as future works.Besides, modular networks BID0 BID4 are proposed for the reasoning over subsymbolic data such as images and natural language question answering. BID16 implements a visual reasoning system based on "virtual" objects brought by receptive fields in CNNs. Wu et al. (2017) tackles the problem of deriving structured representation from raw pixel-level inputs. Dai et al. (2018) combines structured visual representation and theorem proving.Graph neural networks and relational inductive bias. Graph convolution networks (GCNs) (Bruna et al., 2014; Li et al., 2016; Defferrard et al., 2016; Kipf & Welling, 2017 ) is a family of neural architectures working on graphs. As a representative, Gilmer et al. FORMULA2 proposes a message passing modeling for unifying various graph neural networks and graph convolution networks. GCNs achieved great success in tasks with intrinsic relational structures. However, most of the GCNs operate on pre-defined graphs with only nodes and binary connections. This restricts the expressive power of models in general-purpose reasoning tasks (Li et al., 2016) .In contrast, this work removes such restrictions and introduces a neural architecture to capture lifted rules defined on any set of objects. Quantitative results support the effectiveness of the proposed model in a broad set of tasks ranging from relational reasoning to modeling general algorithms (as decision-making process). Moreover, being fully differentiable, NLMs can be plugged into existing convolutional or recurrent neural architectures for logic reasoning.Relational decision making. Logic-driven decision making is also related to Relational RL (Van Otterlo, 2009 ), which models the environment as a collection of objects and their relations. State transition and policies are both defined over objects and their interactions. Examples include OO-MDP (Diuk et al., 2008; Kansky et al., 2017) , symbolic models for learning in interactive domains BID12 , structured task definition by object-oriented instructions (Denil et al., 2017) , and structured policy learning (Garnelo et al., 2016) . General planning methods solve these tasks via planning based on rules (Hu & De Giacomo, 2011; BID18 Jiménez et al., 2019) . The goal of our paper is to introduce a neural architecture which learns lifted rules and handle relational data with multiple orders. We leave its application in other RL and planning tasks as future work.Neural abstraction machines and program induction. Neural Turing Machine (NTM ) (Graves et al., 2014; enables general-purpose neural problem solving such as sorting by introducing an external memory that mimics the execution of Turing Machine. Neural program induction and synthesis BID9 BID13 Kaiser & Sutskever, 2016; BID11 Devlin et al., 2017; Bunel et al., 2018; BID20 are recently introduced to solve problems by synthesizing computer programs with neural augmentations. Some works tackle the issue of the systematical generalization by introducing extra supervision (Cai et al., 2017) . In Chen et al. (2018) , more complex programs such as language parsing are studied. However, the neural programming and program induction approaches are usually hard to optimize in an end-to-end manner, and often require strong supervisions (such as ground-truth programs). In this paper, we propose a novel neural-symbolic architecture called Neural Logic Machines (NLMs) which can conduct first-order logic deduction. Our model is fully differentiable, and can be trained in an end-to-end fashion. Empirical evaluations show that our method is able to learn the underlying logical rules from small-scale tasks, and generalize to large-scale tasks.The promising results open the door for several research directions. First, the maximum depth of the NLMs is a hyperparameter to be specified for individual problems. Future works may investigate how to extend the model, so that it can adaptively select the right depth for the problem at hand. Second, it is interesting to extend NLMs to handle vector inputs with real-valued components. Currently, NLM requires symbolic input that may not be easily available in applications like health care where many inputs (e.g., blood pressure) are real numbers. Third, training NLMs remains nontrivial, and techniques like curriculum learning have to be used. It is important to find an effective yet simpler alternative to optimize NLMs. Last but not least, unlike ILP methods that learn a set of rules in an explainable format, the learned rules of NLMs are implicitly encoded as weights of the neural networks. Extracting human-readable rules from NLMs would be a meaningful future direction. We cannot directly prove the accuracy of NLM by looking at the induced rules as in traditional ILP systems. Alternatively, we take an empirical way to estimate its accuracy by sampling testing examples. Throughout the experiments section, all accuracy statistics are reported in 1000 random generated data.To show the confidence of this result, we test a specific trained model of Blocks World task with 100,000 samples. We get no fail cases in the testing. According to the multiplicative form of Chernoff Bound 6 , We are 99.7% confident that the accuracy is at least 99.98%.
We propose the Neural Logic Machine (NLM), a neural-symbolic architecture for both inductive learning and logic reasoning.
{"src": "scitldr-AIC_train", "paper_id": "B1xY-hRctX"}