Abstract Reasoning via Logic-guided Generation

Our problem setup is largely inspired by Bethell-Fox et al. (1984), who evaluated the constructive matching ability of humans to measure their generative reasoning ability. In this perspective, we express reasoning as a task of inferring the rule $r$ from a given problem $P$, where the problem $P$ is a pair of a context $\bm{x}$ and answer $y$ satisfying the rule $y=r(\bm{x})$. We especially focus on the generative strategy for solving this task; given a query context $\bm{x}$, we evaluate the ability of machines to infer a rule as $\hat{r}$ from contexts $\bm{x}$ to generate an answer image $\hat{y}=\hat{r}({\bm{x}})$ that matches the ground-truth image $y$.

For teaching models the ability of generative strategy in abstract reasoning, we train them on a dataset $\mathcal{D}$ consisting of $d$ problems, i.e., $\mathcal{D}=\{({\bm{x}}_{i},y_{i})\}_{i=1}^{d}$. To be specific, we consider a dataset where each context $\bm{x}$ in the dataset $\mathcal{D}$ is a tuple of $M$ images $(x_{1},\ldots,x_{M})$ and $y$ is an answer image. Images are specified by a collection of abstract features such as shapes, colors and size. For instance, we visualize the case of the generative strategy in Raven’s Progressive Matrices (RPM) structure in Figure 1(b): contexts are given as eight images i.e., $M=8$, and the goal is to generate an answer image for the remaining location, denoted by a question mark.

Our main idea is to connect abstract reasoning to the optimization problem in propositional logic to achieve the generative reasoning strategy into the framework. For instance, in RPM problems, one can define propositional variables $p(i,j,o)$ as “an image placed at $i$th row and $j$th column contains an attribute $o$” to represent contexts in the problem, as shown in Figure 1(c). Here, attributes are sets of features in each context image, e.g., set of shapes $\mathcal{A}$, color $\mathcal{C}$, and size $\mathcal{S}$. With those variables, underlying rules can be written as propositional logical formulas as in Figure 1(c). In this respect, one may interpret the answer generation procedure as the MAXSAT optimization problem in propositional logic: finding propositional variables representing the answer which satisfy the underlying logical formula in the given RPM problem as much as possible. We provide a more description of the MAXSAT problem in Appendix A.

As those propositional variables are not provided in dataset $\mathcal{D}$, LoGe learns a propositional embedding and rules in problems in self-supervised manner. In particular, we derive a three-step framework with an encoder network $f_{\theta}$, a decoder network $g_{\phi}$, a logical reasoning layer $S_{\psi}$ parametrized by $\theta$, $\phi$, $\psi$, respectively, and a latent codebook $\mathcal{E}=\{e_{1},\cdots,e_{K}\}$, where each element $e_{k}\in\mathcal{E}$ is a trainable $D$-dimensional real-valued vector:

• •

  (Abstraction.) The encoder network $f_{\theta}$ and the codebook $\mathcal{E}$ embeds contexts into propositional variables.

• •

  (Reasoning.) The reasoning layer $S_{\psi}$ predicts propositional variables of the answer image.

• •

  (Reconstruction.) The decoder network $g_{\phi}$ and the codebook $\mathcal{E}$ generates the answer image from inferred propositional variables.

We provide an illustration of our framework in Figure 2.

In the rest of this section, we describe each step of our framework in detail.

Abstraction. We first compute propositional logical variables of each context image $x_{i}\in\bm{x}$ from the encoder network $f_{\theta}$ and the latent codebook $\mathcal{E}$. To achieve this, we first pass through each image $x_{i}$ into the encoder network $f_{\theta}$ to have a corresponding output $z_{i}\coloneqq f_{\theta}(x_{i})\in\mathbb{R}^{H\times D}$, in which we denote $z_{i}=(z_{(i,1)},\ldots,z_{(i,H)})^{{\scriptscriptstyle\mathsf{T}}}$. We then quantize the output $z_{i}$ with the codebook $\mathcal{E}$, denoted by $q_{i}\coloneqq(e_{s(i,1)},\ldots,e_{s(i,H)})^{{\scriptscriptstyle\mathsf{T}}}$, where $s(i,h)\in[K]$ with $[K]\coloneqq\{1,\ldots,K\}$ is defined as follows:

where $[H]\coloneqq\{1,\ldots,H\}$. We finally consider an one-hot encoding of indices of $q_{i}$, namely $(s(i,1),\ldots,s(i,H))$. Specifically, we map each index $s(i,h)\in[K]$ into $K$-categorical one-hot vector $t_{(i,H)}$ in which the $s(i,h)$-th value is 1 for all $h\in[H]$. Consequently, we have an one-hot embedding $t_{i}\coloneqq(t_{(i,1)},\ldots,t_{(i,H)})^{{\scriptscriptstyle\mathsf{T}}}\in\{0,1\}^{H\times K}$ of each image $x_{i}$. This one-hot embedding $t_{i}$ is regarded and utilized as propositional variables of $x_{i}$ in further steps.

Reasoning. With propositional variables $(t_{1},\ldots,t_{M})$ of the context $\bm{x}$, we compute propositional variables $\hat{t}\in\{0,1\}^{H\times K}$ which corresponds to the predicted answer image. To be specific, we evaluate $\hat{t}$ from the reasoning layer $S_{\phi}$ and propositional variables of contexts $\bm{x}$, i.e., $\hat{t}=S_{\psi}(t_{1},\ldots,t_{M})$. For the reasoning layer $S_{\psi}$, we choose the SATNet layer (Wang et al., 2019), which is a differentiable version of the MAXSAT problem solver and learns propositional logical formulas from data as layer weights. We provide details of this reasoning layer in Appendix B.

Reconstruction. Finally, we infer the answer image $\hat{y}$ from predicted propositional variables $\hat{t}\in\{0,1\}^{H\times K}$. To achieve this, we first compute a latent vector $\hat{q}\in\mathbb{R}^{H\times D}$ of $\hat{y}$ from predicted $\hat{t}$ and the codebook $\mathcal{E}$:

We then return the output from the decoder $g_{\phi}(\hat{q})$ as the final answer image $\hat{y}$.

Training objective. To train LoGe, we propose three loss functions: $\mathcal{L}_{\mathtt{abst}}$, $\mathcal{L}_{\mathtt{reason}}$, and $\mathcal{L}_{\mathtt{recon}}$ for each $(\bm{x},y)\in\mathcal{D}$, which is for abstraction, reasoning, and reconstruction step, respectively. To formulate those objectives, we additionally consider $q^{\ast}$ and $t^{\ast}$, which indicates a quantized vector and propositional variables of the answer $y$ from the abstraction step.

We first formulate $\mathcal{L}_{\mathtt{abst}}$ and $\mathcal{L}_{\mathtt{recon}}$, which resemble the objective in vector-quantized variational autoencoder (Van Den Oord et al., 2017; Razavi et al., 2019):

where the term with the bar indicates the term with a stop-gradient operator. Moreover, we define $\mathcal{L}_{\mathtt{reason}}$ as follows:

Here, $\mathcal{L}_{\mathtt{BCE}}$ denotes the binary cross-entropy loss.

To sum up, we optimize the loss $\mathcal{L}_{\mathtt{total}}(\theta,\phi,\psi,\mathcal{E})$, which is a sum of above three loss functions:

Here, the total loss $\mathcal{L}_{\mathtt{total}}$ contains several discrete outputs, e.g., outputs of the reasoning layer in $\mathcal{L}_{\mathtt{reason}}$. We provide a detailed description of how to deal with such non-differentiability on the optimization in Appendix C.

Datasets. To verify the effectiveness of LoGe, we choose RAVEN (Zhang et al., 2019a) and i-RAVEN (Hu et al., 2021). For more details of these datasets, see Appendix D.

Baselines. We note that LoGe utilizes VQ-VAE (Van Den Oord et al., 2017) and SATNet (Wang et al., 2019) to leverage a propositional logic. To verify the effectiveness of this logical prior, we qualitatively compare the generated answers with ones from other black-box neural network frameworks, i.e., different encoders and reasoning networks other than VQ-VAE and SATNet, respectively. For quantitative results, we compare the performance with prior methods on discriminative abstract reasoning. We provide detailed descriptions of baselines for comparison in Appendix E.

Qualitative result. Figure 3 summarizes results of the generated answers from different configurations of RAVEN dataset. LoGe successfully generates the answer image at the various configuration of abstract reasoning problems, while other black-box architecture design choices fail. It indicates how propositional logic prior is beneficial to achieve the objective. We provide more illustrations in Appendix 7.

Quantitative result. Table 1 shows the comparison of our framework and prior approaches on discriminative tasks.¹¹1For Hu et al. (2021), we resized the image to 80$\times$80 for a fair comparison with other baselines. We select the answer by choosing the candidate which has the smallest mean-squared error from the generated answer image to employ our framework into discriminative tasks. Intriguingly, LoGe shows better performance to existing works; even our method has not been accessed to other candidates other than the answer while training.