Learning to Organize Knowledge with N-Gram Machines

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

TL;DR

Researchers from CMU and Google have introduced the N-Gram Machine (NGM), a question-answering system that bridges the gap between deep learning and symbolic logic. By encoding text into a searchable, symbolic "n-gram" database, the NGM achieves constant-time query complexity. This allows it to answer questions from stories containing 10 million sentences just as fast as from stories with only ten.

The Scalability Bottleneck in QA

Most state-of-the-art deep learning models for Question Answering (QA), such as Memory Networks (MemN2N), suffer from a major scalability bottleneck: they have to "read" the entire source text every time they are asked a question. This makes their computational complexity linear relative to the size of the corpus ($O(n)$).

While this works for short snippets, it is prohibitive for real-world applications like querying Wikipedia, a long novel, or the entire Web. Traditional Information Extraction (IE) systems solve this by building structured databases, but they usually require human experts to design the schema and annotate data. The authors seek a middle ground: a system that learns to build its own structured, symbolic memory from raw text without human-designed schemas.

Methods: The N-Gram Machine Architecture

The N-Gram Machine consists of three main neural components and a deterministic executor:

N-Gram Machine Architecture
  1. Knowledge Encoder: A sequence-to-sequence model that converts raw sentences into symbolic "knowledge tuples" (n-grams). Unlike standard n-grams, these can be any combination of words and special symbols that represent the sentence's meaning.
  2. Knowledge Decoder: This component attempts to reconstruct the original sentence from the generated tuples. This "auto-encoding" task helps the model learn meaningful representations even before it gets a "reward" for answering a question correctly.
  3. Programmer: This model translates a natural language question into a symbolic program (e.g., Argmax Daniel went).
  4. Executor: A non-learnable component that runs the generated program against the indexed knowledge store to retrieve the answer.

Training Innovations

Because the model involves discrete latent variables (the symbolic tuples and programs), it cannot be trained with simple backpropagation. The authors use REINFORCE (a reinforcement learning algorithm) but introduce two critical tweaks to handle the massive search space:

  • Stabilized Auto-Encoding (AE): They force the decoder to learn from noisy, partial observations of the text, preventing the encoder and decoder from drifting apart during training.
  • Structure Tweak (ST): If a program fails to find an answer, the system "retrospectively" suggests changes to the knowledge tuples to make them consistent with the question, effectively refining the search space iteratively.

Key Insights

  • Symbolic Indexing is the Secret Sauce: By converting text into symbols, the model can use hash tables or other classical data structures to index knowledge. This allows the "Programmer" to jump straight to the relevant information rather than scanning the whole text.
  • Consistency over Fluency: The model doesn't need to learn "fluent" English in its internal memory; it just needs to learn a consistent symbolic language that both the Encoder and Programmer agree on.
  • The "Aha" Moment of Structure Tweaking: The authors found that auto-encoding alone isn't enough. The "Structure Tweak" allows the model to learn from its failures by asking, "What should I have stored in memory to make this program work?"

Key Results

The authors evaluated the NGM on standard bAbI Tasks (20 synthetic reasoning tasks) and a custom Life-long bAbI dataset designed to test scalability up to 10 million sentences.

Scalability and Accuracy of NGM vs MemN2N
  • Constant-Time Scalability: In the "Life-long bAbI" experiment, the NGM maintained a flat response time (approx. 10ms) regardless of story length. In contrast, the baseline (MemN2N) saw its response time grow linearly, becoming 1,000x slower than NGM as the story reached 10 million lines.
  • Robustness at Scale: The NGM's answering quality remained perfect even at the 10-million-sentence scale, whereas the baseline's accuracy dropped sharply after the story length exceeded 400 sentences.
  • Accuracy: On the standard bAbI tasks, the NGM (with AE and ST) achieved 100% accuracy on several difficult tasks (Tasks 1, 11, 15, 16) where the baseline Memory Networks or a version of NGM without structure tweaking performed significantly worse.

Limitations and Future Work

While groundbreaking for scalability, the experiments were conducted on the bAbI dataset, which uses a limited vocabulary and simple grammar. Natural language is far more complex. Furthermore, the current representation (triplets/n-grams) might be too simple for highly nuanced language. The authors suggest that more complex representations, like Abstract Meaning Representations (AMR), and moving toward more sophisticated, weakly supervised learning for complex natural language remain open challenges.

Summary updated

BibTeX
@inproceedings{yang2018learning,
  author = {Fan Yang and William W. Cohen and Jiazhong Nie 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