Learning & Reasoning / arXiv 2016

Put a Logical Rule Into a Vector Operation

This technical report derives tensor operations for storing facts, applying inference rules, and retrieving the answer to a query.

Basic Reasoning with Tensor Product Representations

Paul Smolensky, Moontae Lee, Xiaodong He, Wen-tau Yih, Jianfeng Gao, Li Deng

Overview

John picks up an apple, goes to an office, and walks to a kitchen. A reader can infer that the apple was in the office even though the story never says so. Moontae and his colleagues use this example to work out how a vector representation can carry a fact forward, combine it with another fact, and answer a question about what happened before.

Key Findings

A fact carries the roles of its parts

A stored fact has a relation, a first argument, a second argument, and a time. The tensor product puts each in a separate slot. The report writes the location relation as @@ and represents a collection of facts by adding their tensors. For a general predicate PP, the same construction is

B=∑kPk⊗ak⊗bk⊗ck.\mathbf B=\sum_k \mathbf P_k\otimes\mathbf a_k\otimes\mathbf b_k\otimes\mathbf c_k.

If the vectors for symbols are orthonormal, contracting the first three slots with the known predicate and arguments leaves the vector in the matching fourth slot. For linearly independent symbol vectors, the report gives the corresponding construction using dual vectors. The first example assumes that a semantic parser has already produced logical forms.

Two tensor operations follow the apple

The report applies two rules to the location relation, written below as at⁡\operatorname{at}:

at⁡(x,y,t)∧at⁡(y,z,t)⟹at⁡(x,z,t),at⁡(x,y,t)∧t≺t′⟹at⁡(x,y,t′).\begin{aligned} \operatorname{at}(x,y,t)\land\operatorname{at}(y,z,t) &\Longrightarrow\operatorname{at}(x,z,t),\\ \operatorname{at}(x,y,t)\land t\prec t' &\Longrightarrow\operatorname{at}(x,y,t'). \end{aligned}

The first rule joins two facts sharing the same middle entity and time. In the tensor diagram, the connecting wire indicates the shared index to be summed over. Contractions against the predicate and time vectors isolate the relevant facts.

The transitivity diagram connects the matching argument in two input fact tensors. The remaining wires carry the first argument, second argument, relation, and time into the output.
The transitivity diagram connects the matching argument in two input fact tensors. The remaining wires carry the first argument, second argument, relation, and time into the output.

The persistence operation copies a location fact from the preceding time into the current one. A time-shift operator links the time vectors. In the story, the fact that John has the apple is copied to the time when he enters the office. Applying transitivity places the apple in the office, and the same procedure places it in the kitchen one time step later.

The persistence operator combines its argument-preserving wires with a time shift.
The persistence operator combines its argument-preserving wires with a time shift.

A query joins facts about adjacent times

The question about the apple’s location before the kitchen uses two location facts and the immediate-precedence relation between their times. Known symbols and shared time indices are contracted; the location slot is left open. In the example, that remaining slot returns the office. Dropping the apple contributes a negative fact tensor that cancels the persisted carrying fact. The stored location of the apple in the kitchen can persist even as John moves on.

The query diagram wires together two location facts and a temporal-precedence fact. The free output wire carries the answer vector.
The query diagram wires together two location facts and a temporal-precedence fact. The free output wire carries the answer vector.

Some inference operations reduce to matrix multiplication

When the predicate is implicit and time is tracked in separate memory slots, the transitivity operation simplifies to a matrix product. In the report’s football and garden example, Mary’s unit vector m\mathbf m is the shared argument:

(fm⊤)(mg⊤)=f(m⊤m)g⊤=fg⊤.(\mathbf f\mathbf m^\top)(\mathbf m\mathbf g^\top) =\mathbf f(\mathbf m^\top\mathbf m)\mathbf g^\top =\mathbf f\mathbf g^\top.

The path-finding example needs several relations rather than one. It represents an individual direction by a matrix and a route by a product of such matrices. South and west are modeled by the inverses of north and east. In example (19), two north steps link the garden to the bedroom. The report notes that the bAbI path-finding tasks require testing routes of length at most two.

The bAbI scores describe a programmed system

bAbI question categoriesReported accuracy
Category 599.8%
Category 1699.5%
Every other category100%

Section 2.4 summarizes results from Lee et al. (2016) for the programmed simplification. The evaluation measures how well the supplied vector operations answer the benchmark questions under that setup. The report cautions against comparing its scores directly with systems that learn reasoning from training examples. Section 3 generalizes the construction to queries with multiple predicates, constants, equality constraints, and free answer variables.

Questions & Answers

Q: Why use a tensor product for a fact?

A: The tensor product retains both the symbol and its argument role. The same entities can participate in different relations, or in the same relation with their roles reversed, without collapsing into one representation.

Q: Does unbinding require one-hot vectors?

A: Orthonormal distributed vectors are sufficient in the worked examples. With linearly independent vectors, a dual representation can be used to isolate the requested slot.

Q: What could make the method unreliable on a new story?

A: The construction assumes that the relevant facts and rules are present and that the query has an appropriate logical form. If independently chosen symbol vectors are nearly collinear, computing dual vectors can also amplify representation errors. The reported bAbI scores do not test these parser and conditioning problems.

Future Ideas

Use a symbolic interpreter to check a tensor reasoning trace on stories about location and containment. Give both implementations identical logical forms. Add competing facts and controlled perturbations to the symbol vectors, then measure answer agreement and identify whether mistakes begin in fact retrieval, rule application, or the final query.

Sources

Original abstract

In this paper we present the initial development of a general theory for mapping inference in predicate logic to computation over Tensor Product Representations (TPRs; Smolensky (1990), Smolensky & Legendre (2006)). After an initial brief synopsis of TPRs (Section 0), we begin with particular examples of inference with TPRs in the 'bAbI' question-answering task of Weston et al. (2015) (Section 1). We then present a simplification of the general analysis that suffices for the bAbI task (Section 2). Finally, we lay out the general treatment of inference over TPRs (Section 3). We also show the simplification in Section 2 derives the inference methods described in Lee et al. (2016); this shows how the simple methods of Lee et al. (2016) can be formally extended to more general reasoning tasks.