Providing deep models with access to structured knowledge - motivations, techniques, and challenges

I will give an overview of recent projects at Google involving the use of structured data sources, such as the knowledge graph, in the context of deep-learning models, motivated by the considerations of explainability, updatability, accountability, efficiency, and personalization. We will discuss motivations, techniques, and challenges.

Speaker Introduction

Balder joined Google in 2005, where he has made contributions to search and ads keyword matching using structured data and machine learning. Prior to that, Balder was an adjunct associate professor at UC Santa Cruz and a computer scientist at LogicBlox, doing research on the intersection of logic and computer science with applications in data management, knowledge representation, and computational learning theory.

Neural-Symbolic models for Knowledge Graph Extraction and Reasoning

A knowledge base/graph (KG) containing relevant entities and relationships should be the backbone of many applications including search, question-answering and situation awareness, both general and domain-specific. Leveraging the advancement in unstructured information extraction technology, such knowledge bases can be constructed automatically from text and other media. However, such automatically constructed knowledge graphs are usually error prone and highly incomplete. Link prediction and reasoning over KGs is crucial for both completing the KG and using them in applications. First, I will discuss our work on ontological path finding and differentiable rule mining to mine rules over KG more scalably and accurately for link prediction and the benefits of rules as an interpretable way of reasoning. Second, I will discuss our work on knowledge graph generation from multimedia sources, including text and images. The algorithms integrates neural models and symbolic rules. Lastly, I will talk about our on-going work on a transnational AI system based on representational learning.

Speaker Introduction

Daisy Zhe Wang is an Associate Professor in the CISE department at the University of Florida. She is the Director of the Data Science Research Lab at UF. She obtained her Ph.D. degree from the EECS Department at the University of California, Berkeley in 2011 and her Bachelor’s degree from the ECE Department at the University of Toronto in 2005. At Berkeley, she was a member of the Database Group and the AMP/RAD Lab. She is particularly interested in bridging scalable data management and processing systems with probabilistic models and statistical methods. She currently pursues research topics such as neuro-symbolic models, representational learning, model enabled databases, probabilistic knowledge graphs, interactive and interpretable machine learning. She received Google Faculty Award in 2014. She received a 2018 Very Large Databases (VLDB) 10-Year Test-of-Time Award. She received Arnold and Lisa Goldberg Rising Star Professorship in 2018. Her research has been funded by NSF, DARPA, NIH, NIST, Google, Pivotal, Harris, DTCC and Adobe.

Compositional Explanations of Deep Networks

Despite major efforts in recent years to improve explainability of deep neural networks, the tools we use for communicating explanations have largely remained the same: visualizations of representative inputs, salient input regions, and local model approximations. But when humans describe complex decision rules, we often use a different explanatory tool: natural language. I'll describe recent work on automatically constructing logical descriptions of representations and features inspired by the formal semantics of human language. These descriptions explain not just what a model is paying attention to, but why, and ground prediction in meaningful perceptual and linguistic abstractions. This talk will survey applications of language-based explanations to multi-agent reinforcement learning, language understanding, and image processing.

Speaker Introduction

Jacob Andreas is the X Consortium Assistant Professor at MIT. His research focuses on building intelligent systems that can communicate effectively using language and learn from human guidance. Jacob earned his Ph.D. from UC Berkeley, his M.Phil. from Cambridge (where he studied as a Churchill scholar) and his B.S. from Columbia. He has been the recipient of an NSF graduate fellowship, a Facebook fellowship, and paper awards at NAACL and ICML.

Neuro-Symbolic Visual Concept Learning

Humans are capable of learning visual concepts by jointly understanding vision and language. Imagine that someone with no prior knowledge of colors is presented with the images of the red and green objects, paired with descriptions. They can easily identify the difference in objects’ visual appearance (in this case, color), and align it to the corresponding words. This intuition motivates the use of image-text pairs to facilitate automated visual concept learning and language acquisition. In the talk, I will present recent progress on neuro-symbolic models for visual concept learning and reasoning. These models learn visual concepts and their association with symbolic representations of language, only by looking at images and reading paired natural language texts. I will also discuss their extensions to metaconcept reasoning, dynamics modeling, and action grounding.

Speaker Introduction

Jiajun Wu is an Assistant Professor of Computer Science at Stanford University, working on computer vision, machine learning, and computational cognitive science. Before joining Stanford, he was a Visiting Faculty Researcher at Google Research. He received his PhD in Electrical Engineering and Computer Science at Massachusetts Institute of Technology. Wu's research has been recognized through the ACM Doctoral Dissertation Award Honorable Mention, the AAAI/ACM SIGAI Doctoral Dissertation Award, the MIT George M. Sprowls PhD Thesis Award in Artificial Intelligence and Decision-Making, the 2020 Samsung AI Researcher of the Year, the IROS Best Paper Award on Cognitive Robotics, and fellowships from Facebook, Nvidia, Samsung, and Adobe.

How to Augment Supervised Learning with Reasoning?

Supervised learning is a cognitive phenomenon that has proved amenable both to theoretical analysis and exploitation as a technology. However, not all of cognition can be accounted for directly by supervised learning. The question we ask here is whether one can build on the success of machine learning to address the broader goals of artificial intelligence. We regard reasoning as the major component of cognition that needs to be added. We suggest that the central challenge therefore is to unify the formulation of these two phenomena, learning and reasoning, into a single framework with a common semantics. In such a framework one would aim to learn rules with the same success that predicates can be learned by means of machine learning, and, at the same time, to reason with the rules with guarantees analogous to those of standard logic. We discuss how Robust Logic fulfils the role of such a theoretical framework. We also discuss the challenges of testing this experimentally on a significant scale, for tasks where one hopes to exceed the performance offered by learning alone.

Speaker Introduction

Leslie Valiant was educated at King's College, Cambridge; Imperial College, London; and at Warwick University where he received his Ph.D. in computer science in 1974. He is currently T. Jefferson Coolidge Professor of Computer Science and Applied Mathematics in the School of Engineering and Applied Sciences at Harvard University, where he has taught since 1982. Before coming to Harvard he had taught at Carnegie Mellon University, Leeds University, and the University of Edinburgh.

His work has ranged over several areas of theoretical computer science, particularly complexity theory, learning, and parallel computation. He also has interests in computational neuroscience, evolution and artificial intelligence and is the author of two books, Circuits of the Mind, and Probably Approximately Correct.

He received the Nevanlinna Prize at the International Congress of Mathematicians in 1986, the Knuth Award in 1997, the European Association for Theoretical Computer Science EATCS Award in 2008, and the 2010 A. M. Turing Award. He is a Fellow of the Royal Society (London) and a member of the National Academy of Sciences (USA).

Efficient Probabilistic Reasoning with Graph Neural Networks

Markov Logic Networks (MLNs), which elegantly combine logic rules and probabilistic graphical models, can be used to address many knowledge graph problems. However, inference in MLN is computationally intensive, making the industrial scale application of MLN very difficult. In recent years, graph neural networks (GNNs) have emerged as efficient and effective tools for large-scale graph problems. Nevertheless, GNNs do not explicitly incorporate prior logic rules into the models, and may require many labeled examples for a target task. In this paper, we explore the combination of MLNs and GNNs, and use graph neural networks for variational inference in MLN. We propose a GNN variant, named ExpressGNN, which strikes a nice balance between the representation power and the simplicity of the model. Our extensive experiments on several benchmark datasets demonstrate that ExpressGNN leads to effective and efficient probabilistic logic reasoning.

Speaker Introduction

Le Song is an Associate Professor in the Department of Computational Science and Engineering, College of Computing, an Associate Director of the Center for Machine Learning, Georgia Institute of Technology. His principal research direction is machine learning, especially kernel methods and deep learning, and probabilistic graphical models for large and complex problems, arising from artificial intelligence and interdisciplinary domains. He is the recipient of the NIPS'17 Materials Science Workshop Best Paper Award, the Recsys'16 Deep Learning Workshop Best Paper Award, AISTATS'16 Best Student Paper Award, IPDPS'15 Best Paper Award, NSF CAREER Award'14, NIPS'13 Outstanding Paper Award, and ICML'10 Best Paper Award. He has also served as the area chair or senior program committee for many leading machine learning and AI conferences such as ICML, NeurIPS, AISTATS, AAAI and IJCAI, and the action editor for JMLR and IEEE TPAMI.

The Logic of Graph Neural Networks

Graph neural networks (GNNs) compute functions on graphs or nodes of graphs that, by design, are isomorphism (and hence representation) invariant. The question is which functions can be expressed. A basic observation (Morris et al., AAAI 2019; Xu et al., ICLR 2019) is that GNNs can distinguish two nodes exactly if the 1-dimensional Weisfeiler-Leman (1-WL) algorithm can distinguish them. 1-WL is a simple combinatorial graph isomorphism heuristic that has been used for decades as a basic building block of graph isomorphism tools. The equivalence can be lifted to higher order GNNs and higher-dimensional versions of the WL algorithm. There is a tight connection between the WL algorithm and definability in certain finite variable fragments of first-order logic. Building on this connection and the equivalence between GNNs and 1-WL, Barcelo et al. (ICLR 2020) gave a precise logical characterisation of the expressiveness of GNNs.

The equivalence shows that in their basic form, GNNs can be too weak to express simple graph properties such as the existence of a triangle. It has been known for a while by both practitioners and theoreticians that GNNs can be strengthened by randomly initialising the states of nodes. Indeed, it can be shown that GNNs with random node initialisation are universal: they can approximately express all invariant functions on graphs (Abboud et al., 2020).

My talk will be a survey of these results linking the expressivity of GNNs to logical expressivity. I will cover both theoretical results and experimental findings supporting them.

Speaker Introduction

Martin Grohe is a Professor for Theoretical Computer Science at the RWTH Aachen. He received his PhD in Mathematics at Freiburg University in 1994 and then spent a year as a visiting scholar at Stanford and the University of California at Santa Cruz. Before joining the Department of Computer Science of RWTH Aachen in 2012, he held positions at the University of Illinois at Chicago, the University of Edinburgh, and the Humboldt University at Berlin. His research interest are in theoretical computer science interpreted broadly, including logic, algorithms and complexity, graph theory, theoretical aspects of machine learning, and database theory.

Exploring Combinations of Neural and Logic Learning

Human intelligence clearly hinges on (at least) two kinds of thinking--- fast thinking that allows us to reach instinctive conclusions (like making out objects in a picture) and slow thinking, which allows more robust, symbolic, and communicable thinking (such as arithmetic and logic). Deep neural nets have discovered at least some aspects of fast thinking, leveraging learning from lots of examples/data. We believe that discovering synergistic coordination of these fast and slow thinking processes is an important direction in AI and will lead to new kinds of intelligence that neither slow or fast thinking can alone achieve.

In this talk, I will talk about some new results on robust learning of logical concepts (including learning FOL, recursion, and programs) and new hierarchical models that combine neural networks for vision and learning logical formulas for few-shot robust learning, with applications to solving visual discrimination puzzles.

Speaker Introduction

Madhusudan Parthasarathy is a professor of computer science at the University of Illinois at Urbana-Champaign. He works in formal software verification using automated deduction, automata and logic, learning logics with applications to theorem proving and program verification, program synthesis, and interpretable machine learning.

Neural=Symbolic: A New Paradigm of Logical Neural Networks

Neuro-symbolic AI has recently gained significant interest amid growing industrial requirements for high-performance models that are nonetheless interpretable, verifiable, and adaptable to new problem domains with a minimum of reconfiguration. Numerous distinct categories of such methods have emerged, often characterized either as neural nets somehow informed by symbolic logic or as symbolic logic somehow extracted from neural nets. In contrast, we introduce a new paradigm to the mix, Neural=Symbolic, in which the underlying neural model exactly corresponds to a system of logical formulae in any of various real-valued logics (with classical logic as a special case). Evaluation of such a Logical Neural Network (LNN) performs deductive inference in the associated logical system and can answer complex, zero-shot queries rather than focusing exclusively on predefined outputs. LNNs can easily incorporate existing domain knowledge, but can also learn weights on (sub)formulae so as to minimize logical contradiction, thereby yielding resilience to inconsistency. Additionally, LNNs are careful to distinguish true, false, intermediate, and unknown truth values according to the open-world assumption by working in terms of bounds rather than individual values, thereby yielding resilience to incomplete knowledge. Lastly, LNNs are beginning to generate state-of-the-art results with respect to both theory and application.

Speaker Introduction

Ryan Riegel is a researcher in the AI Reasoning group at IBM Research. He works on neuro-symbolic reasoning methods and their related technologies, including sound and complete real-valued logic, logically constrained neural network learning, extensions of said to temporal and modal logic, and applications including natural language question answering. In the past, he has worked on fast algorithms for a family of nonparametric machine learning methods dubbed generalized N-Body problems, which includes all-nearest-neighbors and kernel density estimation. He also co-founded an AI startup where he oversaw and contributed to the development of enterprise-grade machine learning software for Big Data. He received a Joint BS in Mathematics and Computer Science from Harvey Mudd College and a PhD in Computer Science from the Georgia Institute of Technology.

Language, Brain, and Computation

How does the brain beget the mind? How do molecules, cells and synapses effect reasoning, intelligence, language? Despite dazzling progress in experimental neuroscience, as well as in cognitive science at the other extreme of scale, we do not seem to be making progress in the overarching question -- the gap is huge and a completely new approach seems to be required. As Richard Axel recently put it: "We don't have a logic for the transformation of neural activity into thought [...]."

What kind of formal system would qualify as this "logic"?

I will introduce the Assembly Calculus, a computational system whose basic data structure is the assembly -- assemblies are large populations of neurons representing concepts, words, thoughts, etc. --, and which is informed by recent progress in understanding how language happens in the brain.

Speaker Introduction

Christos Harilaos Papadimitriou is the Donovan Family Professor of Computer Science at Columbia University. Before joining Columbia in 2017, he was a professor at UC Berkeley for the previous 22 years, and before that he taught at Harvard, MIT, NTU Athens, Stanford, and UCSD. He has written five textbooks and many articles on algorithms and complexity, and their applications to optimization, databases, control, AI, robotics, economics and game theory, the Internet, evolution, and the brain. He holds a PhD from Princeton (1976), and eight honorary doctorates, including from ETH, University of Athens, EPFL, and Univ. de Paris Dauphine. He is a member of the National Academy of Sciences of the US, the American Academy of Arts and Sciences, and the National Academy of Engineering, and he has received the Knuth prize, the Goedel prize, the von Neumann medal, as well as the 2018 Harvey Prize by Technion. In 2015 the president of the Hellenic republic named him commander of the order of the Phoenix. He has also written three novels: “Turing”, “Logicomix” and his latest “Independence.”

Neural-Symbolic Integration: A Compositional Perspective

Despite significant progress in the development of neural-symbolic frameworks, the question of how to integrate a neural and a symbolic system in a compositional manner remains open. Our work seeks to fill this gap by treating these two systems as black boxes to be integrated as modules into a single architecture, without making assumptions on their internal structure and semantics. Instead, we expect only that each module exposes certain methods for accessing the functions that the module implements: the symbolic module exposes a deduction method for computing the function's output on a given input, and an abduction method for computing the function's inputs for a given output; the neural module exposes a deduction method for computing the function's output on a given input, and an induction method for updating the function given input-output training instances. We are, then, able to show that a symbolic module --- with any choice for syntax and semantics, as long as the deduction and abduction methods are exposed --- can be cleanly integrated with a neural module, and facilitate the latter's efficient training, achieving empirical performance that exceeds that of previous work.

Speaker Introduction

Efi Tsamoura is a Researcher in Samsung AI, Cambridge. On 2016 she was awarded an early career fellowship from the Alan Turing Institute, UK, and prior to that she was a Researcher in the Department of Computer Science of the University of Oxford. She received her PhD in computer science from the Aristotle University of Thessaloniki, Greece. Her main research interests lie in the areas of logic, KRR and neural-symbolic integration.