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  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.
This paper presents the n-gram machine, a model that encodes sentences into simple symbolic representations ("n-grams") which can be queried efficiently. The authors propose a variety of tricks (stabilized autoencoding, structured tweaking) to deal with the huge search space, and they evaluate NGMs on five of the 20 bAbI tasks. I am overall a fan of the general idea of this paper; scaling up to huge inputs is definitely a necessary research direction for QA. However, I have some concerns about the specific implementation and model discussed here. How much of the proposed approach is specific to getting good results on bAbI (e.g., conditioning the knowledge encoder on only the previous sentence, time stamps in the knowledge tuple, super small RNNs, four simple functions in the n-gram machine, structure tweaking) versus having a general-purpose QA model for natural language? Addressing some of these issues would likely prevent scaling to millions of (real) sentences, as the scalability is reliant on programs being efficiently executed (by simple string matching) against a knowledge storage. The paper is missing a clear analysis of NGM's limitations... the examples of knowledge storage from bAbI in the supplementary material are also underwhelming as the model essentially just has to learn to ignore stopwords since the sentences are so simple. In its current form, I am borderline but leaning towards rejecting this paper.
Other questions:
- is "n-gram" really the most appropriate term to use for the symbolic representation? N-grams are by definition contiguous sequences... The authors may want to consider alternatives.
- why focus only on extractive QA? The evaluations are only conducted on 5 of the 20 bAbI tasks, so  it is hard to draw any conclusions from the results as to the validity of this approach. Can the authors comment on how difficult it will be to add functions to the list in Table 2 to handle the other 15 tasks? Or is NGM strictly for extractive QA?
- beam search is performed on each sentence in the input story to obtain knowledge tuples... while the answering time may not change (as shown in Figure 4) as the input story grows, the time to encode the story into knowledge tuples certainly grows, which likely necessitates the tiny RNN sizes used in the paper. How long does the encoding time take with 10 million sentences?
- Need more detail on the programmer architecture, is it identical to the one used in Liang et al., 2017?