Closed Loop Neural-Symbolic Learning via Integrating Neural Perception, Grammar Parsing, and Symbolic Reasoning

REINFORCE as Rejection Sampling

Posterior Approximation

In Section 3.2.3, we formulate the $m$-step back search as a Metropolis-Hasting sampler to perform sampling from $p^{\prime}(z|x,y)$, which is a smoothing of the true posterior distribution $p(z|x,y)$ as shown in Equation 11. Intuitively, as $\epsilon$ gets smaller, the distance between two distribution $p^{\prime}(z|x,y)$ and $p(z|x,y)$ becomes smaller as well. Accordingly, we have the following lemma proved with Equation 9 and Equation 11:

Given an small $\epsilon$, the Kullback–Leibler divergence of $p^{\prime}(z|x,y)$ from $p(z|x,y)$ is $O(\epsilon)$.

From the definition of Kullback–Leibler divergence, we have:

where $C=\sum_{z^{\prime}}p(y|z^{\prime})p_{\theta}(z^{\prime}|x)=\sum_{z^{\prime}\in Q}p_{\theta}(z^{\prime}|x)$ is the normalizing constant. With Taylor expansion, we get:

Handwritten Formula Recognition

For the handwritten formula recognition task, we define the context-free grammar for the mathematical formulas, as shown in Table 1. This grammar considers only simple arithmetic operations over single-digit numbers. We compute the parsed results using a calculator, which is the symbolic reasoning module in this task.

To be noticed, the proposed method can be extended to more complex computations by designing more complicated grammar.

2 Data Generation

We generate the synthetic dataset based on CROHME 2019 Offline Handwritten Formula Recognition Taskhttps://www.cs.rit.edu/~crohme2019/task.html. First, we extract all the image patches of symbols from CROHME and only keep ten digits (0$\sim$9) and four basic operators ($+$,$-$,$\times$, $\div$). We split these images of symbols into a training symbol set (80%) and a testing symbol set (20%). Then we generate formulas by randomly sampling production rules from the predefined grammar. For the training set, we generate 1K formulas with length 1 (1 digit, 0 operator), 1K formulas with length 3 (2 digits, 1 operator), 2K formulas with length 5 (3 digits, 2 operators), and 6K formulas with length 7 (4 digits, 3 operators). For the test set, we generate 200 formulas with length 1, 200 formulas with length 3, 400 formulas with length 5, and 1,200 formulas with length 7. For each formula in the training/test set, we randomly select symbol images from the training/test symbol set. In this way, one symbol image can not exist in both the training set and the test set. Overall, our dataset contains 10K training formulas and 2K test formulas. The generated dataset is also submitted with the code.

3 Training Details

For the proposed Neural-Grammar-Symbolic models, we use LeNet as the neural perception module and train the models for 100K iterations using the Adam optimizer with a fixed learning rate of $5\times 10^{-4}$ and a batch size of 64. For the REINFORCE and reproduced MAPO baselines, we set the reward decay as $0.99$. For more details in the implementation and reproduction of the experiment results, please refer to the submitted code.

4 Qualitative Examples

Figure 1 shows an illustrative example of the $1$-BS process implemented with a priority queue. Figure 2 shows several examples of correcting the wrong predictions using the $m$-BS algorithms.

Neural-Symbolic VQA

The grammar model in the neural-symbolic VQA task ensures the generated sequence of function modules can form a valid program, which indicates the inputs and outputs of these modules can be strictly matched. Table 3 groups all function modules by the inputs and output types and Table 2 gives the context-free grammar for the CLEVR programs.

2 Implementation Details

The structure of the NGS model is shown in Figure 3. To get the structural scene representations, we train a scene parser following (yi2018neural). Specifically, Mask-RCNN (he2017mask) is used to generate segment proposals of all objects in each image. Along with the segmentation mask, the network also predicts the categorical labels of discrete intrinsic attributes such as color, material, size, and shape. The segment for each object is then paired with the original image and sent to a ResNet-34 to extract the spacial attributes such as pose and 3D coordinates. Both networks of the scene parser are trained on 4,000 generated CLEVR images with full annotations. Please refer to (yi2018neural) for more training details of the scene parser.

Instead of the attention-based seq2seq model used by (yi2018neural), we use a Pointer Network as the question parser. Considering the small vocabulary of the CLEVR questions, we can easily build a dictionary to map the keywords in the question to the corresponding modules. Therefore, for each question, we can extract a set of functional modules, and the ground-truth program is a permutation of this set of modules. In the Pointer Network, both the encoder and decoder are two-layer LSTMs with 256 hidden units. We set the dimensions of both the encoder and decoder word embedding to 300. The Pointer Network works as the neural perception module in the proposed NGS model. Unlike (yi2018neural), we do not need to pre-train the question parser on a small set of ground-truth question-program pairs.

The symbolic reasoning module in this task executes the generated program on the structural scene representations. The program executor is implemented as a collection of deterministic, generic functions in Python, designed to host all the functional modules in the CLEVR programs. Each function is in one-to-one correspondence with a module from the input program sequence, which has the same representation as in (johnson2017inferring; yi2018neural). The execution of a program tree starts from the leaf nodes with scene tokens and continues until the root node, which outputs the final answer to the question.

Since the set of the functional modules is given for each question, the 1-step back search algorithm works by switching two modules that belong to the same group according to Table 3.

All models are trained with 30K iterations using the Adam optimizer with a fixed learning rate of $1\times 10^{-5}$ and a batch size of 64. For the REINFORCE and MAPO baselines, we set the reward decay as $0.99$.

3 Qualitative Examples

Figure 4 shows several illustrative examples of correcting the wrong programs using the $1$-BS model.