Venue: ICLR 2017 conference

Reviews:

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: This paper introduces a novel method for language modeling which is suitable for both modeling programming language as well as natural language. The approach uses a program synthesis algorithm to search over program space and uses count-based estimation of the weights of the program. This is a departure from neural network-based approaches which rely on gradient descent, and thus are extremely slow to estimate. Count-based method such as regular n-gram models suffer because of their simplicity, i.e. not being able to model large context, and scaling badly as context increases. The proposed approach synthesizes programs using MCMC which learn context-sensitive probabilities using count-based estimation, and thus is both fast and able to model long-range context.

Experiments on a programming language datasets, the linux kernel corpus, show that this method is vastly better than both LSTM and n-gram language models. Experiments on the Wikipedia corpus show that the method is competitive, but not better, to SOTA models. Both estimation and query time are significantly better than LSTM LMs, and competitive to n-gram LMs.

It's debatable whether this paper is suitable for ICLR, due to ICLR's focus on neural network-based approaches. However, in the interest of diversity and novelty, such "outside" papers should be accepted to ICLR. This paper is likely to inspire more research into fusion of program synthesis and machine learning methods, which was a popular theme at NIPS 2016.

*Pros*
1. Novel approach.
2. Good results.

*Cons*
1. Some significant algorithmic details are not included in the paper. They should at least be included in an appendix for comprehensiveness.

*Comments*
1. Please include n-gram results in the table for Wikipedia results.
review_title: Novel approach, good results

final_score: rating: null
review_content: 1. It would be helpful if the paper had an example of the program. An example would be much more helpful than the grammar specification. If I understand things correctly, after training is done, there is one program synthesized for the whole dataset? In that case, it would be good to include the synthesized program in the paper.
2. What is the synthesis algorithm used? I understand that it's MCMC, but it would be useful to allocate some space to the algorithm. In particular, I'm also interested in knowing how you estimate the value of a program. Are there any tricks to make the value estimation fast?
review_title: Questions

final_score: rating: 5: Marginally below acceptance threshold
review_content: This paper proposes an approach to character language modeling (CLMs) based on developing a domain specific language to represent CLMs. The experiments show mixed performance versus neural CLM approaches to modeling linux kernel data and wikipedia text, however the proposed DSL models are slightly more compact and fast to query as compared with neural CLMs. The proposed approach is difficult to understand overall and perhaps is aimed towards the sub-community already working on this sort of approach but lacks sufficient explanation for the ICLR audience. Critically the paper glosses over the major issues of demonstrating the proposed DSL is a valid probabilistic model and how training is performed to fit the model to data (there is clearly not a gradient-based training approach used). FInally the experiments feel incomplete without showing samples drawn from the generative model or analyzing the learned model to determine what it has learned. Overall I feel this paper does not describe the approach in enough depth for readers to understand or re-implement it.

Almost all of the model section is devoted to exposition of the DSL without specifying how probabilities are computed using this model and how training is performed. How are probabilities actually encoded? The DSL description seems to have only discrete decisions rather than probabilities.

Training is perhaps covered in previous papers but there needs to be some discussion of how it works here. Section 2.5 does not do enough to explain how training works or how any measure of optimality is achieved.

Given this model is quite a different hypothesis space from neural models or n-grams, looking and samples drawn from the model seems critical. The current experiments show it can score utterances relatively well but it would be very interesting if the model can sample more structured samples than neural approaches (for example long-range syntax constraints like brackets)
review_title: null

final_score: rating: null
review_content: 1. Could the authors provide and explain specific examples where this method yields interpretable behavior?
2. Are there experimental settings that differ from the experiments in Karpathy et al. 2015 for the Linux Kernel Dataset? The BPC corresponding to the CE loss that Karpathy et al. obtain seems significantly lower than in Table 1 in this paper.
3. What smoothing method was ultimately used for the n-gram benchmarks on the Linux Kernel Dataset?
review_title: Questions

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: The authors propose a method for language modeling by first generating a program from a DSL, then learning the count-based parameters of that program. Pros include: The proposed method is innovative and highly different from standard LSTM-based approaches of late. The model should also be much quicker to apply at query time. Strong empirical results are obtained on modeling code, though there is some gap between the synthesis method and neural methods on the Hutter task. A detailed description of the language syntax is provided.

Cons/suggestions:
- The synthesis procedure using MCMC is left very vague, even though being able to make this procedure efficient is one of the key questions.
- The work builds on work from the PL literature; surely the related work could also be expanded and this work better put in context.
- More compact/convincing examples of human interpretability would be helpful.

Other comments
- Training time evaluation in Table 1 should give basic information such as whether training was done on GPU/CPU, CPU specs, etc.

review_title: Novel approach to language modeling

Meta-review: This work was a very controversial submission, with two strong accepts and one initial strong reject. There was significant discussion about the replicability of the paper, although all reviewers seem interested in the methods. 
 
 Pro:
 - There is strong originality to this work. One of the few submissions in the area not just using RNNs for LM.
 - The paper shows strong empirical results on PL language modeling, comparative results in natural language modeling, fast lookup compared to neural models, and presents a significantly different approach then the currently accepted NN methods. 
 
 
 Cons:
 - The original draft has clarity issues. In particular the MCMC approach is very difficult to follow and lacks clear explanation for this community, the interpretability of the method is not demonstrated, and too much of the work is devoted to laying out the language itself. (Note The authors have gone out of their way to include an appendix which caused one reviewer to go from recommending strong rejection to weak rejection, but also requires a much larger submission size. While two reviewers do like the work, their reviews are mainly based on the empirical sucess at program language modeling.)
 
 Overall, the PCs have determined that this work deserves to appear at the conference.
Decision: Accept (Poster)