#### AI

# Quantum-Inspired Logical Embedding for Knowledge Representation

December 10, 2019 | Written by: IBM Research Staff Members

Categorized: AI

Share this post:

*Authors: Dinesh Garg, Shajith Ikbal, Santosh K Srivastava, Harit Vishwakarma, Hima Karanam, L Venkata Subramaniam*

Knowledge representation is a field of AI that deals with representing knowledge in a form that machines can easily store, access, and use for solving complex reasoning tasks such as question answering, dialog in conversational systems, and computational argumentation. In our new paper, to be presented at NeurIPS 2019, we develop a new knowledge representation, which we call “quantum embedding”, that represents conceptual knowledge using a vector space representation that preserves its logical structure and allows reasoning tasks to be solved accurately and efficiently.

Until recently, predominant approaches for knowledge representation have largely been symbolic, where facts are represented by symbols, and logical reasoning is used to infer new facts and make deductions. Examples of symbolic and logical frameworks include First Order Logic (FOL), Web Ontology Language (OWL), and Frame Language. In practice, symbolic reasoning can be slow and brittle, despite being exact. On the other hand, continuous vector space representations, and their corresponding reasoning frameworks, are an alternative [1]. While they can be fast and robust, they are approximate. Continuous representation stems from the field of Statistical Relational Learning (SRL) [2, 3], where knowledge is embedded into a vector space using a distributional representation that captures statistical similarities among entities and predicates. While there are advantages in using such compact representations, they typically do not preserve underlying logical structure. This, in turn, limits the performance of logical reasoning tasks.

The challenge of developing an efficient continuous representation of knowledge that supports logical reasoning motivated our IBM Research team to develop a new way of representing knowledge using vector spaces.We call it Quantum Embedding because, while not applicable to the operation of quantum computers, the technique is inspired by the theory of Quantum Logic. Quantum Embedding preserves the “logical structure” of a given symbolic knowledge base (KB) in the vector space embedding. This also allows the application of Boolean logical operations directly, similar to how one would perform them on a purely symbolic representation of the KB.

Our initial results show that sub-symbolic (e.g. neural) reasoners can benefit immensely from using these Quantum Embeddings. We found significant accuracy improvements over popular SRL baselines on question answering tasks involving membership-based complex logical reasoning queries. The details of this work are available in our paper “Quantum Embedding of Knowledge for Reasoning.”

### The Core Idea Behind Quantum Embedding

Figure 1 illustrates the central idea behind Quantum Embedding. The example knowledge fragment on the left-hand side, in the form of unary predicate (concept) hierarchy, is embedded into a *d*-dimensional vector space on the right-hand side. Each red oval-shaped node corresponds to a concept (e.g., a medical profession) and each blue circular node corresponds to an entity (e.g., an individual). The Quantum Embedding maps the entity and concept nodes to a vector in *R ^{d}*, respectively. In Figure 1, uses a three-dimensional (

*d*=3) space for the sake of illustration. We generate this Quantum Embedding in a way that satisfies Quantum Logical Axioms, as we summarize next.

### Axioms of Quantum Logic

Quantum Logic (QL) was first proposed by Birkhoff and Von Neumann [4] to model the quantum behavior of subatomic particles. We exploit an analogy between quantum mechanics and knowledge for the purpose of producing an embedding that preserves logical structure. In this analogy, *subatomic particles* are analogous to *entities*, *classical quantum states* are analogous to *latent features*, and an *experimental hypothesis* is analogous to a *predicate*. Such an analogy suggests that:

- Each predicate (unary or binary) should be represented by a linear subspace of a (real or complex) vector space
*Σ*, where*Σ*=*R*(or^{d}*C*) for some integer^{d}*d*. - All the entities (or entity pairs) should be denoted by (complex) vectors in a way that they lie in each of the predicate subspaces to which they belong (Figure 1 illustrates this idea). The axes of the embedding space
*Σ*represent latent semantic attributes of the entities and entity pairs. - Each predicate should be mapped to a unique linear subspace of the embedding space
*Σ*the in such a way that its logical relationship with other predicates and entities remain intact.

#### Preserving Logical Implication (⇒)

Let’s consider the *physician* concept shown in the Figure 1. Note, both *pulmonologist* and *cardiologist* concepts are linked to the *physician* concept – each of them implies *physician*. This means that the subspace corresponding to *physician* concept must encompass (in theory) the subspace corresponding to each of *pulmonologist* and *cardiologist* concepts. In general, for any two concept *C*_{1} and *C*_{2}, where *C*_{1} ⇒ *C*_{2}, the diagram below depicts the condition that the geometry of their respective subspaces must satisfy in the embedding space to preserve such logical implication.

#### Preserving Logical AND

Suppose there are three concepts *C*_{1,} *C*_{2} and *C*_{3}. Assume that it is given in the KB that *C*_{3 }= (*C*_{1,} AND *C*_{2}). Then, the subspace corresponding to *C*_{3} must be given by the set theoretic intersection of the subspaces for *C*_{1} as well as *C*_{2}. This is illustrated below, where, given the subspaces of *C*_{1} and *C*_{2}, the subspace of *C*_{3} is automatically determined (shown by the red line).

#### Preserving Logical OR

If *C*_{3} = *C*_{1} OR *C*_{2}, the diagram below depicts the necessary condition to be satisfied by their corresponding subspaces.

#### Preserving Logical NOT

Finally, if *C*_{2} = ¬*C*_{1}, then the condition satisfied is given as follows.

### An Optimization Program for Generating Quantum Embedding

For any given KB, and a target embedding space *Σ* = *R ^{d}*, we can express each of the above Quantum Logical constraints in the form of an appropriate loss function. Combining these losses results in a combinatorial optimization program whose solution yields the desired Quantum Embedding. The details of this program can be found in our paper. We call this whole program as

*Embed-to-Reason (E2R)*method.

### How to Answer Queries using Quantum Embedding

Suppose you have computed Quantum Embedding of a given symbolic KB. The immediate question is: *“How do I work with it?”* While applicability of quantum embeddings is quite broad, we highlight a simple membership query-based reasoning task that we think is important and sufficient enough to understand the use of Quantum Embeddings. A typical membership query over KB is: *“Find all the entities belonging the concept ** where ** could be a given complex logical formula.”*

To answer such a query, we convert the formula into an appropriate subspace of the Quantum Embedding space *Σ*. Next, we find all entity vectors with the length of orthogonal projection onto subspace *S* more than some threshold τ. The projection length is used to assign the confidence score/probability (again drawing analogy from Quantum Logic theory) of the entity being a member of the correct answer set of the query.

### Performance of Quantum Embedding

We evaluate the performance of E2R program on two different kinds of tasks – (i) *link prediction*, and (ii) *reasoning*. For link prediction, we evaluate on the *FB15K* and *WN18* datasets using the standard train and test partitions [5,6, 7]. To evaluate the reasoning capabilities, we use the LUBM (Lehigh University Benchmark) dataset, which consists of a university domain ontology, customizable and repeatable synthetic data. We generated one university (LUBM1U) data as our training set and it contained 69,628 triples along with ontology in triple form (unary and binary predicates). We custom-designed eight test queries that comprise higher level predicates in the LUBM1U hierarchy, such that answering such queries would explicitly require deductive reasoning.

We used TransE [5] and ComplEx [7] as baselines to compare the effectiveness of our method. Table 1 shows the experimental results, where we have highlighted the numbers reflecting higher performance of Quantum Embedding (denoted in the table as E2R for Embed-to-Reason).

It is evident from Table 1 that Quantum Embedding-based E2R method outperforms both TransE and ComplEx on *MRR* and *HITS@1* metrics for all the tasks and datasets, except for WN18. Interestingly, Quantum Embedding improves accuracy over the baselines for link prediction on the FB15k dataset as well as on the LUBM1U dataset for the reasoning task. WN18 is a collection of binary relation instances, where most of these relations satisfy transitivity property (e.g. hypernym) and have inverse relations (e.g. hypernym/hyponym). The baseline methods, which are primarily distance-based, seem to capture transitivity/inversion properties better than Quantum Embedding, which is not distance-based. This gives future directions to explore in our work.

### Concluding Remarks

Quantum Embedding is a new way of representing knowledge in classical (not quantum) computers. It represents symbolic knowledge in a vector space that preserves the structure of logical propositions. The idea is inspired by Quantum Logic axioms. The key advantage is answering complex reasoning queries accurately (both deductive and predictive) using a distributional representation of the knowledge base (KB). Experimental results show higher effectiveness relative to baseline methods. Future directions include extending to more expressive logical operations as well as to natural language-based KBs. More details are available in our paper.

### References

[1] Dominic Widdows and Trevor Cohen, Reasoning with Vectors: A Continuous Model for Fast Robust Inference, *Logic Journal of the IGPL,* 23(2), 141–173, 2015.

[2] Lise Getoor and Ben Taskar. *Introduction to Statistical Relational Learning.* Adaptive Computation and Machine Learning. MIT Press, 2007.

[3] Maximilian Nickel, Kevin Murphy, Volker Tresp, and Evgeniy Gabrilovich. A Review of Relational Machine Learning for Knowledge Graphs. *IEEE,* 104(1):11–33, 2016.

[4] Garrett Birkhoff and John Von Neumann. The logic of quantum mechanics. *The Annals of Mathematics,* 37(4):823–843, 1936.

[5] Antoine Bordes, Nicolas Usunier, Alberto García-Durán, JasonWeston, and Oksana Yakhnenko. *Translating embeddings for modeling multi-relational data*. In NIPS, pages 2787–2795, 2013.

[6] Zhen Wang, Jianwen Zhang, Jianlin Feng, and Zheng Chen. *Knowledge graph embedding by translating on hyperplanes*. In AAAI, pages 1112–1119, 2014.

[7] Théo Trouillon, Johannes Welbl, Sebastian Riedel, Eric Gaussier, and Guillaume Bouchard. *Complex embeddings for simple link prediction*. In ICML, pages 2071–2080, 2016.

### AI Year in Review: Highlights of Papers from IBM Research in 2019

IBM’s leadership in AI continued in earnest in 2019, which was notable for a growing focus on critical topics such as making trustworthy AI work in practice, creating new AI engineering paradigms to scale AI for a broader use, and continuing to advance core AI capabilities.

### Optimal Transport for Label Switching: Using Geometry to Solve Problems in AI

A new paper from the MIT-IBM Watson AI Lab and MIT CSAIL considers how the optimal transport can efficiently “summarize” this uncertainty for a class of popular decision making problems.

### 2020 AI Predictions from IBM Research

In 2020, three themes will shape the advancement of AI: automation, natural language processing, and trust. From this lens, IBM Research is unveiling its annual five predictions for AI in 2020.