Learning to Organize Knowledge with N-Gram Machines

Fan Yang, Jiazhong Nie, William W. Cohen, Ni Lao

Introduction

Deep neural networks (DNNs) have revolutionized NLP, but they struggle with "knowledge-intensive" tasks involving massive corpora. Existing end-to-end models, such as Memory Networks, typically have a computational complexity that is linear ($O(n)$) relative to the text size. To answer a single question, these models must essentially "re-read" or attend to every sentence in the story. This approach is prohibitive for real-world applications like querying Wikipedia or the entire Web.

N-Gram Machines (NGM) bridge the gap between deep learning and symbolic reasoning to solve this scalability bottleneck. By encoding text into an indexed symbolic "n-gram" store, NGM achieves constant-time question answering regardless of corpus size, overcoming the linear scaling limitations of traditional memory-augmented neural networks.

Methods

The N-Gram Machine consists of three learnable sequence-to-sequence (seq2seq) components and a deterministic executor:

  1. Knowledge Encoder: Converts input sentences into "knowledge tuples" (n-grams). For example, "Mary went to the kitchen" might become (mary, to, kitchen).
  2. Knowledge Store: A collection of these tuples. Crucially, because these are symbolic, they can be indexed using hash tables for near-instant retrieval.
  3. Programmer: Converts a question into a symbolic program (e.g., using functions like Hop or Argmax).
  4. Executor: Runs the generated program against the indexed knowledge store to produce an answer.
Detailed architecture of the N-Gram Machine showing the encoder, programmer, and training mechanisms.

Training Innovations

Training discrete latent variables (the n-grams and programs) is notoriously difficult due to high gradient variance. The authors use REINFORCE but introduce two key techniques to make it work:

  • Stabilized Auto-Encoding (AE): The model is tasked with decoding the n-grams back into the original sentences. This ensures the symbolic tuples actually preserve the meaning of the text.
  • Structure Tweaking (ST): If a program fails to find an answer because of a minor inconsistency (e.g., using a synonym), this procedure retrospectively "tweaks" the knowledge store to align with the programmer's expectations, refining the search space iteratively.

Datasets & Key Insights

The model was evaluated on the standard bAbI Tasks (a synthetic benchmark of 20 reasoning tasks) and a custom Life-long bAbI dataset, where stories are scaled up to 10 million sentences to test answering time against corpus size.

Key insights from the approach include:

  • The Symbolic Bottleneck is a Feature: By forcing the model to pass information through a symbolic "n-gram" bottleneck, the authors enable the use of classical computer science data structures (indices/hash maps) within a neural framework.
  • Latent Schema Induction: NGM learns its own internal n-gram "language" from weak supervision (just question-answer pairs), unlike traditional Information Extraction that requires fixed schemas.
  • Constant-Time Reasoning: Because the "reading" happens at encoding time and the "answering" happens via an index, the time it takes to answer a question is independent of the total number of facts stored.

Key Results

  • Accuracy: NGM outperformed the then-state-of-the-art Memory Networks (MemN2N) on several bAbI tasks, particularly those involving deduction and induction (Tasks 15 and 16).
  • Scalability: On the "Life-long bAbI" dataset, NGM's answering time remained constant as the story grew from 200 to 10 million sentences. In contrast, MemN2N's answering time grew linearly. The authors found that NGM becomes more efficient than standard neural memory models once a story exceeds roughly 1,000 sentences.
  • Ablation: Auto-Encoding is essential for bootstrapping the model; without it, the model fails to find any meaningful signal in the discrete search space. Structure Tweaking further refines performance to reach perfect accuracy on several tasks.
Ablation study demonstrating the necessity of Auto-Encoding (AE) and Structure Tweaking (ST) for task success.

Limitations and Future Work

  • Synthetic Data: The evaluation was primarily on bAbI, which uses a limited vocabulary and restricted grammar. The effectiveness of NGM on "wild" natural language remains to be proven.
  • N-Gram Expressiveness: The current model uses a fixed tuple length (tri-grams). While this has the same expressive power as RDF triples, it might be too rigid for more complex linguistic structures.
  • Search Space: Even with beam search and tweaking, the search space for discrete programs is massive. Future work could involve more sophisticated RL techniques or pre-training.
  • Expanded Functionality: Adding more complex functions to the programmer, such as counting, summation, or negation, could handle a broader range of semantic queries.

Summary updated

Abstract

Deep neural networks (DNNs) had great success on NLP tasks such as language modeling, machine translation and certain question answering (QA) tasks. However, the success is limited at more knowledge intensive tasks such as QA from a big corpus. Existing end-to-end deep QA models (Miller et al., 2016; Weston et al., 2014) need to read the entire text after observing the question, and therefore their complexity in responding a question is linear in the text size. This is prohibitive for practical tasks such as QA from Wikipedia, a novel, or the Web. We propose to solve this scalability issue by using symbolic meaning representations, which can be indexed and retrieved efficiently with complexity that is independent of the text size. More specifically, we use sequence-to-sequence models to encode knowledge symbolically and generate programs to answer questions from the encoded knowledge. We apply our approach, called the N-Gram Machine (NGM), to the bAbI tasks (Weston et al., 2015) and a special version of them (“life-long bAbI”) which has stories of up to 10 million sentences. Our experiments show that NGM can successfully solve both of these tasks accurately and efficiently. Unlike fully differentiable memory models, NGM’s time complexity and answering quality are not affected by the story length. The whole system of NGM is trained end-to-end with REINFORCE (Williams, 1992). To avoid high variance in gradient estimation, which is typical in discrete latent variable models, we use beam search instead of sampling. To tackle the exponentially large search space, we use a stabilized auto-encoding objective and a structure tweak procedure to iteratively reduce and refine the search space.
BibTeX
@inproceedings{yang2018learning,
  author = {Fan Yang and Jiazhong Nie and William W. Cohen and Ni Lao},
  title = {{Learning to Organize Knowledge with N-Gram Machines}},
  booktitle = {Workshops @ ICLR},
  year = {2018},
  url = {https://openreview.net/forum?id=5QZAruUm62m},
}
Figure