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.
 Although there is a great deal of recent research on extracting structured knowledge from text BID13 BID31 and answering questions from structured knowledge stores BID12 BID19 , much less progress has been made on either the problem of unifying these approaches in an end-to-end model or the problem of removing the bottleneck of relying on human experts to design the schema and annotate examples for information extraction. In particular, traditional natural language processing and information extraction approaches are too labor-intensive and brittle for answering open domain questions from large corpus, and existing end-to-end deep QA models (e.g., BID29 BID47 ) lack scalability and the ability to integrate domain knowledge. This paper presents a new QA system that treats both the schema and the content of a structured storage as discrete hidden variables, and infers these structures automatically from weak supervisions (such as QA pair examples). The structured storage we consider is simply a set of "n-grams", which we show can represent a wide range of semantics, and can be indexed for efficient computations at scale. We present an end-to-end trainable system which combines an text auto-encoding component for encoding knowledge, and a memory enhanced sequence to sequence component for answering questions from the encoded knowledge. We show that the method scales well on artificially generated stories of up to 10 million lines long FIG2 ). The system we present here illustrates how end-to-end learning and scalability can be made possible through a symbolic knowledge storage. We present an end-to-end trainable system which combines an text auto-encoding component for encoding the meaning of text in symbolic representations, and a memory enhanced sequence-tosequence component for answering questions from the storage. We show that the method achieves good scaling properties and robust inference on artificially generated stories of up to 10 million sentences long. The system we present here illustrates how end-to-end learning and scalability can be made possible through a symbolic knowledge storage.To further improve the system, we are interested in investigating whether the proposed n-gram representation is sufficient for natural languages. More complex representations, such as Abstract Meaning Representations BID4 , are possible alternatives, but it remains unclear how to design effective weakly supervised learning techniques to induce such representations. John went to the bathroom. John went bathroom After that he went back to the hallway. John he hallway Sandra journeyed to the bedroom Sandra Sandra bedroom After that she moved to the garden Sandra she garden Question ProgramWhere is Sandra? Argmax Sandra she Berhard is a rhino. Bernhard a rhino Lily is a swan. Lily a swan Julius is a swan.Julius a swan Lily is white.Lily is white Greg is a rhino.Greg a rhino Julius is white.Julius is white Brian is a lion.Brian a lion Bernhard is gray.Bernhard is gray Brian is yellow.
We propose a framework that learns to encode knowledge symbolically and generate programs to reason about the encoded knowledge. 
The authors propose the N-Gram machine to answer questions over long documents. This paper presents the n-gram machine, a model that encodes sentences into simple symbolic representations which can be queried efficiently.