AI

Quantum-Inspired Logical Embedding for Knowledge Representation

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: Illustration Quantum Embedding as a vector representation that preserves logical structure.

Figure 1: Illustration Quantum Embedding as a vector representation that preserves logical structure.

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 Rd, 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:

  1. Each predicate (unary or binary) should be represented by a linear subspace of a (real or complex) vector space Σ, where ΣRd (or Cd) for some integer d.
  2. 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.
  3. 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 C1 and C2, where C1 ⇒ C2, the diagram below depicts the condition that the geometry of their respective subspaces must satisfy in the embedding space to preserve such logical implication.

This diagram 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 C1, C2 and C3. Assume that it is given in the KB that C3 = (C1, AND C2). Then, the subspace corresponding to C3 must be given by the set theoretic intersection of the subspaces for C1 as well as C2. This is illustrated below, where, given the subspaces of C1 and C2, the subspace of C3 is automatically determined (shown by the red line).

This is illustrated, where, given the subspaces of C1 and C2, the subspace of C3 is automatically determined (shown by the red line).

Preserving Logical OR

If C3 = C1 OR C2, the diagram below depicts the necessary condition to be satisfied by their corresponding subspaces.

If C3 = C1 OR C2, the diagram depicts the necessary condition to be satisfied by their corresponding subspaces.

Preserving Logical NOT

Finally, if C2 = ¬C1, then the condition satisfied is given as follows.

If C2 = ¬C1, then the condition satisfied is given as shown in the diagram.

An Optimization Program for Generating Quantum Embedding

For any given KB, and a target embedding space Σ = Rd, 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).

Table 1: Datasets and Experimental Results. Acronyms used are E2R = Quantum Embedding, TE = TransE, CE = ComplEx.

Table 1: Datasets and Experimental Results. Acronyms used are E2R = Quantum Embedding, TE = TransE, CE = ComplEx.

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.

 

More AI stories

State-of-the-Art Results in Conversational Telephony Speech Recognition with a Single-Headed Attention-Based Sequence-to-Sequence Model

Powerful neural networks have enabled the use of “end-to-end” speech recognition models that directly map a sequence of acoustic features to a sequence of words. It is generally believed that direct sequence-to-sequence speech recognition models are competitive with traditional hybrid models only when a large amount of training data is used. However, in our recent […]

Continue reading

IBM Research at INTERSPEECH 2020

The 21st INTERSPEECH Conference will take place as a fully virtual conference from October 25 to October 29. INTERSPEECH is the world’s largest conference devoted to speech processing and applications, and is the premiere conference of the International Speech Communication Association. The current focus of speech technology research at IBM Research AI is around Spoken […]

Continue reading

You Have the Floor: IBM Watson AI Weighs In on Bloomberg’s “That’s Debatable”

IBM Research’s Project Debater team worked with the producers of “That’s Debatable” to integrate AI into the traditional debate format. With the help of a new natural language processing (NLP) feature called key point analysis, IBM Watson AI can synthesize thousands of submissions from the general public prior to each episode via ibm.com/debatable.

Continue reading