We describe a novel way of representing a symbolic knowledge base (KB) called a sparse-matrix reified KB.   This representation enables neural modules that are fully differentiable, faithful to the original semantics of the KB, expressive enough to model multi-hop inferences, and scalable enough to use with realistically large KBs. The sparse-matrix reified KB can be distributed across multiple GPUs, can scale to tens of millions of entities and facts, and is orders of magnitude faster than naive sparse-matrix implementations.   The reified KB enables very simple end-to-end architectures to obtain competitive performance on several benchmarks representing two families of tasks: KB completion, and learning semantic parsers from denotations. There has been much prior work on using neural networks to generalize the contents of a KB (e.g., (Xiong et al., 2017; Bordes et al., 2013; Dettmers et al., 2018) ), typically by constructing low-dimensional embeddings of the entities and relations in the KB, which are then used to score potential triples as plausible or implausible elements of the KB. We consider here the related but different problem of incorporating a symbolic KB into a neural system, so as to inject knowledge from an existing KB directly into a neural model. More precisely, we consider the problem of designing neural KB inference modules that are (1) fully differentiable, so that any loss based on their outputs can be backpropagated to their inputs; (2) accurate, in that they are faithful to the original semantics of the KB; (3) expressive, so they can perform non-trivial inferences; and (4) scalable, so that realistically large KBs can be incorporated into a neural model. To motivate the goal of incorporating a symbolic KB into a neural network, consider the task of learning neural semantic parsers from denotations. Many questions-e.g., what's the most recent movie that Quentin Tarantino directed? or which nearby restaurants have vegetarian entrees and take reservations?-are best answered by knowledge-based question-answering (KBQA) methods, where an answer is found by accessing a KB. Within KBQA, a common approach is neural semantic parsing-i.e., using neural methods to translate a natural-language question into a structured query against the KB (e.g., (Zhong et al., 2017; Finegan-Dollak et al., 2018; Shaw et al., 2019) ), which is subsequently executed with a symbolic KB query engine. While this approach can be effective, it requires training data pairing natural-language questions with structured queries, which is difficult to obtain. Hence researchers have also considered learning semantic parsers from denotations (e.g., (Berant et al., 2013; Yih et al., 2015) ), where training data consists of pairs (q, A), where q is a natural-language question and A is the desired answer. Typically A is a set of KB entities-e.g., if q is the first sample question above, A would be 1 the singleton set containing Once Upon a Time in Hollywood. Learning semantic parsers from denotations is difficult because the end-to-end process to be learned includes a non-differentiable operation-i.e., reasoning with the symbolic KB that contains the answers. To circumvent this difficulty, prior systems have used three different approaches. Some have used heuristic search to infer structured queries from denotations (e.g., (Pasupat & Liang, 2016; Dasigi et al., 2019) ): this works in some cases but often an answer could be associated with many possible structured queries, introducing noise. Others have supplemented gradient approaches 1 At the time of this writing. x: an entity X: weighted set of entities x: vector encoding X NE: # entities in KB r: an relation R: weighted set of relations r: vector encoding R NR: # relations in KB Mr: matrix for r MR: weighted sum of Mr's, see Eq 1 follow(x, r): see Eq 2 NT : # triples in KB M subj , M obj , M rel : the reified KB, encoded as matrices mapping triple id to subject, object, and relation ids Table 1 : Summary of notation used in the paper. (This excludes notation used in defining models for the KB completion and QA tasks of Section 3.) with reinforcement learning (e.g., (Misra et al., 2018) ). Some systems have also "neuralized" KB reasoning, but to date only over small KBs: this approach is natural when answers are naturally constrained to depend on a small set of facts (e.g., a single table (Zhong et al., 2017; Gupta & Lewis, 2018) ), but more generally requires coupling a learner with some (non-differentiable) mechanism to retrieve an appropriate small question-dependent subset of the KB (e.g., (Sun et al., 2018; ). In this paper, we introduce a novel scheme for incorporating reasoning on a large question-independent KB into a neural network, by representing a symbolic KB with an encoding called a sparse-matrix reified KB. A sparse-matrix reified KB is very compact, can be distributed across multiple GPUs if necessary, and is well-suited to modern GPU architecture. For KBs with many relations, a reified KB can be up to four orders of magnitude faster than alternative implementations (even alternatives based on sparse-matrix representations), and in our experiments we demonstrate scalability to a KB with over 13 million entities and nearly 44 million facts. This new architectural component leads to radically simpler architectures for neural semantic parsing from denotations-architectures based on a single end-to-end differentiable process, rather than cascades of retrieval and neural processes. We show that very simple instantiations of these architectures are still highly competitive with the state of the art for several benchmark tasks. To our knowledge these models are the first fully end-to-end neural parsers from denotations that have been applied to these benchmark tasks. We also demonstrate that these architectures scale to long chains of reasoning on synthetic tasks, and demonstrate similarly simple architectures for a second task, KB completion. 2 NEURAL REASONING WITH A SYMBOLIC KB 2.1 BACKGROUND KBs, entities, and relations. A KB consists of entities and relations. We use x to denote an entity and r to denote a relation. Each entity has an integer index between 1 and N E , where N E is the number of entities in the KB, and we write x i for the entity that has index i. A relation is a set of entity pairs, and represents a relationship between entities: for instance, if x i represents "Quentin Tarantino" and x j represents "Pulp Fiction" then (x i , x j ) would be an member of the relation director_of. A relation r is a subset of {1, . . . , N E } × {1, . . . , N E }. Finally a KB consists a set of relations and a set of entities. Weighted sets as "k-hot" vectors. Our differentiable operations are based on weighted sets, where each element x of weighted set X is associated with a non-negative real number. It is convenient to define this weight to be zero for all x ∈ X while for x ∈ X, a weight less than 1 is a confidence that the set contains x, and weights more than 1 make X a multiset. If all elements of X have weight 1, we say X is a hard set. A weighted set X can be encoded as an entity-set vector x ∈ R N E , where the i-th component of x is the weight of x i in X. If X is a hard entity set, then this will be a "k-hot" vector, for k = |X|. The set of indices of x with non-zero values is called the support of x. Sets of relations, and relations as matrices Often we would like to reason about sets of relations 2 , so we also assume every relation r in a KB is associated with an entity and hence an integer index. We write r k for the relation with index k, and we assume that relation entities are listed first in the index of entities, so the index k for r k is between 1 and N R , where N R is the number of relations in the KB. We use R for a set of relations, e.g., R = {writer_of, director_of} might be such a set, and use r for a vector encoding of a set. A relation r can be encoded as a relation matrix M r ∈ R N E ×N E , where the value for M r [i, j] is (in general) the weight of the assertion r(x i , x j ) in the KB. In the experiments of this paper, all KB relations are hard sets, so M r [i, j] ∈ {0, 1}. Sparse vs. dense matrices for relations. Scalably representing a large KB requires careful consideration of the implementation. One important issue is that for all but the smallest KBs, a relation matrix must be implemented using a sparse matrix data structure, as explicitly storing all N 2 E values is impractical. For instance, consider a KB containing 10,000 movie entities and 100,000 person entities. A relationship like writer_of would have only a few tens of thousands of facts, since most movies have only one or two writers, but a dense matrix would have more than 1 billion values. We thus model relations as sparse matrices. Let N r be the number of entity pairs in the relation r. A common sparse matrix data structure is a sparse coordinate pair (COO) encoding: with a COO encoding, each KB fact requires storing only two integers and one float. Our implementations are based on Tensorflow (Abadi et al., 2016) , which offers limited support for sparse matrices. In particular, driven by the limitations of GPU architecture, Tensorflow only supports matrix multiplication between a sparse matrix COO and a dense matrix, but not between two sparse matrices, or between sparse higher-rank tensors and dense tensors. Entity types. It is often possible to easily group entities into disjoint sets by some notion of "type": for example, in a movie domain, all entities might be either of the type "movie", "person", or "movie studio". It is straightforward to extend the formalism above to typed sets of entities, and doing this can lead to some useful optimizations. We use these optimizations below where appropriate: in particular, one can assume that relation-set vectors r are of dimension N R , not N E , in the sections below. The full formal extension of the definitions above to typed entities and relations is given in Appendix A. We introduced here a novel way of representing a symbolic knowledge base (KB) called a sparsematrix reified KB. This representation enables neural modules that are fully differentiable, faithful to the original semantics of the KB, expressive enough to model multi-hop inferences, and scalable enough to use with realistically large KBs. In a reified KB, all KB relations are represented with three sparse matrices, which can be distributed across multiple GPUs, and symbolic reasoning on realistic KBs with many relations is much faster than with naive implementations-more than four orders of magnitude faster on synthetic-data experiments compared to naive sparse-matrix implementations. This new architectural component leads to radically simpler architectures for neural semantic parsing from denotations and KB completion-in particular, they make it possible to learn neural KBQA models in a completely end-to-end way, mapping from text to KB entity sets, for KBs with tens of millions of triples and entities and hundreds of relations.
A scalable differentiable neural module that implements reasoning on symbolic KBs.
{"src": "scitldr-AIC_train", "paper_id": "BJlguT4YPr"}