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:
- Knowledge Encoder: Converts input sentences into "knowledge tuples" (n-grams). For example, "Mary went to the kitchen" might become
(mary, to, kitchen). - Knowledge Store: A collection of these tuples. Crucially, because these are symbolic, they can be indexed using hash tables for near-instant retrieval.
- Programmer: Converts a question into a symbolic program (e.g., using functions like
HoporArgmax). - Executor: Runs the generated program against the indexed knowledge store to produce an answer.
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.
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