Title: PROGRAM SYNTHESIS FOR CHARACTER LEVEL LANGUAGE MODELING

Abstract: We propose a statistical model applicable to character level language modeling and show that it is a good fit for both, program source code and English text. The model is parameterized by a program from a domain-specific language (DSL) that allows expressing non-trivial data dependencies. Learning is done in two phases: (i) we synthesize a program from the DSL, essentially learning a good representation for the data, and (ii) we learn parameters from the training datathe process is done via counting, as in simple language models such as n-gram. Our experiments show that the precision of our model is comparable to that of neural networks while sharing a number of advantages with n-gram models such as fast query time and the capability to quickly add and remove training data samples. Further, the model is parameterized by a program that can be manually inspected, understood and updated, addressing a major problem of neural networks.

1. INTRODUCTION:

Recent years have shown increased interest in learning from large datasets in order to make accurate predictions on important tasks. A significant catalyst for this movement has been the ground breaking precision improvements on a number of cognitive tasks achieved via deep neural networks. Deep neural networks have made substantial inroads in areas such as image recognition (Krizhevsky et al., 2012) and natural language processing (Józefowicz et al., 2016) thanks to large datasets, deeper networks (He et al., 2016) and substantial investments in computational power Oh & Jung (2004) .

While neural networks remain a practical choice for many applications, they have been less effective when used for more structured tasks such as those concerning predictions about programs (Allamanis et al., 2016; Raychev et al., 2014) . Initially targeting the programming languages domain, a new method for synthesizing probabilistic models proposed by Bielik et al. (2016) , without a neural network, has shown to be effective for modeling source code, and has gained traction.

In this work, we investigate the applicability of this new method to tasks which have so far been addressed with recurrent neural networks and n-gram language models. The probabilistic models we propose are defined by a program from a domain-specific language (DSL). A program in this DSL describes a probabilistic model such as n-gram language models or a variant of it -e.g. trained on subsets of the training data, queried only when certain conditions are met and specialized in making specific classes of predictions. These programs can also be combined to produce one large program that queries different specialized submodels depending on the context of the query.

For example, consider predicting the characters in an English text. Typically, the first character of a word is much more difficult to predict than other characters and thus we would like to predict it differently. Let f be a function that takes a prediction position t in a text x and returns a list of characters to make prediction on. For example, let f be defined as follows:

f (t, x) = if x t-1 is whitespace then x s else x t-1 x t-2

where x s is the first character of the word preceding the predicted word at position t. Now, consider a model that predicts a character by estimating each character x t from a distribution P (x t |f (t, x)). For positions that do not follow a whitespace, this distribution uses the two characters preceding x t and thus it simply encodes a trigram language model (in this example, without backoff, but we consider backoff separately). However, P (x t |f (t, x)) combines the trigram model with another interesting model for the samples in the beginning of the words where trigram models typically fail.

More generally, f is a function that describes a probabilistic model. By simply varying f , we can define trivial models such as n-gram models, or much deeper and interesting models and combinations. In this work, we draw f from a domain-specific language (DSL) that resembles a standard programming language: it includes if statements, limited use of variables and one iterator over the text, but overall that language can be further extended to handle specific tasks depending on the nature of the data. The learning process now includes finding f from the DSL such that the model P (x t |f (t, x)) performs best on a validation set and we show that we can effectively learn such functions using Markov chain Monte Carlo (MCMC) search techniques combined with decision tree learning.

Advantages An advantage of having a function f drawn from a DSL is that f becomes humanly readable, in contrast to neural networks that generally provide non-human readable matrices (Li et al., 2016) . Further, the training procedure is two-fold: first, we synthesize f from the DSL, and then for a given f , we estimate probabilities for P (x t |f (t, x)) by counting in the training data. This gives us additional advantages such as the ability to synthesize f and learn the probability distribution P on different datasets: e.g., we can easily add and remove samples from the dataset used for computing the probability estimate P . Finally, because the final model is based on counting, estimating probabilities P (x t |f (t, x)) is efficient: applying f and looking up in a hashtable to determine how frequently in the training data, x t appears in the resulting context of f (t, x).

Before we continue, we note an important point about DSL-based models. In contrast to deep neural networks that can theoretically encode all continuous functions (Hornik, 1991) , a DSL by definition targets a particular application domain, and thus comes with restricted expressiveness. Increasing the expressibility of the DSL (e.g., by adding new instructions) can in theory make the synthesis problem intractable or even undecidable. Overall, this means that a DSL should balance between expressibility and efficiency of synthesizing functions in it (Gulwani, 2010) .

Contributions This work makes two main contributions::

• We define a DSL which is useful in expressing (character level) language models. This DSL can express n-gram language models with backoff, with caching and can compose them using if statements in a decision-tree-like fashion. We also provide efficient synthesis procedures for functions in this DSL. • We experimentally compare our DSL-based probabilistic model with state-of-the-art neural network models on two popular datasets: the Linux Kernel dataset (Karpathy et al., 2015) and the Hutter Prize Wikipedia dataset (Hutter, 2012) .

2. A DSL FOR CHARACTER LEVEL LANGUAGE MODELING:

We now provide a definition of our domain specific language (DSL) called TChar for learning character level language models. At a high level, executing a program p ∈ TChar at a position t ∈ N in the input sequence of characters x ∈ X returns an LMProgram that specifies language model to be used at position t. That is, p ∈ TChar : N × X → LMProgram. The best model to use at position t is selected depending on the current program state (updated after processing each character) and conditioning on the dynamically computed context for position t of the input text x. This allows us to train specialized models suited for various types of prediction such as for comments vs. source code, newlines, indentation, opening/closing brackets, first character of a word and many more. Despite of the fact that the approach uses many specialized models, we still obtain a valid probability distribution as all of these models operate on disjoint data and are valid probability distributions. Subsequently, the selected program f ∈ LMProgram determines the language model that estimates the probability of character x t by building a probability distribution P (x t |f (t, x)). That is, the probability distribution is conditioned on the context obtained by executing the program f .

The syntax of TChar is shown in Fig. 1 and is designed such that it contains general purpose instructions and statements that operate over a sequence of characters. One of the advantages of our approach is that this language can be further refined by adding more instructions that are specialized for a given domain at hand (e.g., in future versions, we can easily include set of instructions specific to modeling C/C++ source code). We now informally describe the general TChar language of this work. We provide a formal definition and semantics of the TChar language in the appendix.

2.1. SIMPLEPROGRAMS:

The SimpleProgram is a basic building block of the TChar language. It describes a loop-free and branch-free program that accumulates context with values from the input by means of navigating within the input (using Move instructions) and writing the observed values (using Write instructions). The result of executing a SimpleProgram is the accumulated context which is used either to condition the prediction, to update the program state or to determine which program to execute next.

Move Instructions:

We define four basic types of Move instructions -LEFT and RIGHT that move to the previous and next character respectively, PREV CHAR that moves to the most recent position in the input with the same value as the current character x t and PREV POS which works as PREV CHAR but only considers positions in the input that are partitioned into the same language model. Additionally, for each character c in the input vocabulary we generate instruction PREV CHAR(c) that navigates to the most recent position of character c. We note that all Move instructions are allowed to navigate only to the left of the character x t that is to be predicted.

Write Instructions:

We define three Write instructions -WRITE CHAR that writes the value of the character at current position, WRITE HASH that writes a hash of all the values seen between the current position and the position of last Write instruction, and WRITE DIST that writes a distance (i.e., number of characters) between current position and the position of last Write instruction. Example We now briefly discuss some of the BranchProgram synthesized for the Linux Kernel dataset in our experiments described in Section 3. By inspecting the synthesized program we identified interesting SimplePrograms building blocks such as PREV CHAR( ) RIGHT WRITE CHAR that conditions on the first character of the current word, PREV CHAR(\n) WRITE DIST that conditions on the distance from the beginning of the line or PREV CHAR( ) LEFT WRITE CHAR that checks the preceding character of a previous underscore (useful for predicting variable names). These are examples of more specialized programs that are typically found in the branches of nested switches of a large TChar program. The top level switch of the synthesized program used the character before the predicted position (i.e. switch LEFT WRITE CHAR) and handles separately cases such as newline, tabs, special characters (e.g., !#@. * ), upper-case characters and the rest.

2.3. STATEPROGRAMS:

A common difficulty in building statistical language models is capturing long range dependencies in the given dataset. Our TChar language partially addresses this issue by using Move instructions that can jump to various positions in the data using PREV CHAR and PREV POS instructions. However, we can further improve by explicitly introducing a state to our programs using StateProgram. The StateProgram consists of two sequential operations -updating the current state and determining which program to execute next based on the value of the current state. For both we reuse the switch construct defined previously for SwitchProgram. In our work we consider integer valued state that can by either incremented, decremented or left unmodified after processing each input character. We note that other definitions of the state, such as stack based state, are possible.

Example As an example of a StateProgram consider the question of detecting whether the current character is inside a comment or is a source code. These denote very different types of data that we might want to model separately if it leads to improvement in our cost metric. This can be achieved by using a simple state program with condition LEFT WRITE CHAR LEFT WRITE CHAR that increments the state on '/*', decrements on '*/' and leaves the state unchanged otherwise.

2.4. LMPROGRAMS:

The LMProgram describes a probabilistic model trained and queried on a subset of the data as defined by the branches taken in the SwitchPrograms and StatePrograms. The LMProgram in TChar is instantiated with a language model described by a SimpleProgram plus backoff. That is, the prediction is conditioned on the sequence of values returned by executing the program, i.e. P (x t |f (t, x)).

Recall that given a position t in text x, executing a SimpleProgram returns context f (t, x). For example, executing LEFT WRITE CHAR LEFT WRITE CHAR returns the two characters x t-1 x t-2 preceding x t . In this example P (x t |f (t, x)) is a trigram model. To be effective in practice, however, such models should support smoothing or backoff to lower order models. We provide backoff in two ways. First, because the accumulated context by the SimpleProgram is a sequence we simply backoff to a model that uses a shorter sequences by using Witten-Bell backoff (Witten & Bell, 1991) . Second, in the LMProgram we explicitly allow to backoff to other models specified by a TChar pro-gram if the probability of the most likely character from vocabulary V according to the P (x t |f (t, x)) model is less than a constant d. Additionally, for some of our experiments we also consider backoff to a cache model (Kuhn & De Mori, 1990) .

Predicting Out-of-Vocabulary Labels Finally, we incorporate a feature of the language models as proposed by Raychev et al. (2016a) that enables us not only to predict characters directly but instead to predict a character which is equal to some other character in the text. This is achieved by synthesising a pair of (SimpleProgram, SimpleProgram). The first program is called equality program and it navigates over the text to return characters that may be equal to the character that we are trying to predict. Then, the second program f describes P (x t |f (t, x)) as described before, except that a possible output is equality to one of the characters returned by the equality program.

2.5. SYNTHESISING TChar PROGRAMS:

The goal of the synthesizer is given a set of training and validation samples D, to find a program:

p best = arg min p∈TChar cost(D, p)

where cost(D, p) = -logprob(D, p) + λ • Ω(p). Here logprob(D, p) is the log-probability of the trained models on the dataset D and Ω(p) is a regularization that penalizes complex functions to avoid over-fitting to the data. In our implementation, Ω(p) returns the number of instructions in p.

The language TChar essentially consists of two fragments: branches and straight-line SimplePrograms. To synthesize branches, we essentially need a decision tree learning algorithm that we instantiate with the ID3+ algorithm as described in Raychev et al. (2016a) . To synthesize SimplePrograms we use a combination of brute-force search for very short programs (up to 5 instructions), genetic programming-based search and Markov chain Monte Carlo-based search. These procedures are computationally feasible, because each SimpleProgram consists of only a small number of moves and writes. We provide more details about this procedure in Appendix B.1.

3. EXPERIMENTS:

Datasets For our experiments we use two diverse datasets: a natural language one and a structured text (source code) one. Both were previously used to evaluate character-level language models -the Linux Kernel dataset Karpathy et al. (2015) and Hutter Prize Wikipedia dataset Hutter (2012) . The Linux Kernel dataset contains header and source files in the C language shuffled randomly, and consists of 6, 206, 996 characters in total with vocabulary size 101. The Hutter Prize Wikipedia dataset contains the contents of Wikipedia articles annotated with meta-data using special mark-up (e.g., XML or hyperlinks) and consists of 100, 000, 000 characters and vocabulary size 205. For both datasets we use the first 80% for training, next 10% for validation and final 10% as a test set.

Evaluation Metrics To evaluate the performance of various probabilistic language models we use two metrics. Firstly, we use the bits-per-character (BPC) metric which corresponds to the negative log likelihood of a given prediction E[-log 2 p(x t | x <t )], where x t is character being predicted and x <t denotes characters preceding x t . Further, we use error rate which corresponds to the ratio of mistakes the model makes. This is a practical metric that directly quantifies how useful is the model in a concrete task (e.g., completion). As we will see, having two different evaluation metrics is beneficial as better (lower) BPC does not always correspond to better (lower) error rate.

3.1. LANGUAGE MODELS:

We compare the performance of our trained DSL model, instantiated with the TChar language described in Section 2, against two widely used language models -n-gram model and recurrent neural networks. For all models we consider character level modeling of the dataset at hand. That is, the models are trained by feeding the input data character by character, without any knowledge of higher level word boundaries and dataset structure. 

N-gram:

We use the n-gram model as a baseline model as it has been traditionally the most widely used language model due to it simplicity, efficient training and fast sampling. We note that ngram can be trivially expressed in the TChar language as a program containing a sequence of LEFT and WRITE instructions. To deal with data sparseness we have experimented with various smoothing techniques including Witten-Bell interpolation smoothing Witten & Bell (1991) and modified Kneser-Ney smoothing Kneser & Ney (1995) ; Chen & Goodman (1998) .

Recurrent Neural Networks To evaluate the effectiveness of the DSL model we compare to a recurrent network language model shown to produce state-of-the-art performance in various natural language processing tasks. In particular, for the Linux Kernel dataset we compare against a variant of recurrent neural networks with Long Short-Term Memory (LSTM) proposed by Hochreiter & Schmidhuber (1997) . To train our models we follow the experimental set-up and use the implementation of Karpathy et al. (2015) . We initialize all parameters uniformly in range [-0.08, 0.08], use mini-batch stochastic gradient descent with batch size 50 and RMSProp Dauphin et al. (2015) perparameter adaptive update with base learning rate 2 × 10 -3 and decay 0.95. Further, the network is unrolled 100 time steps and we do not use dropout. Finally, the network is trained for 50 epochs (with early stopping based on a validation set) and the learning rate is decayed after 10 epochs by multiplying it with a factor of 0.95 each additional epoch. For the Hutter Prize Wikipedia dataset we compared to various other, more sophisticated models as reported by Chung et al. (2017) .

DSL model To better understand various features of the TChar language we include experiments that disable some of the language features. Concretely, we evaluate the effect of including cache and backoff. In our experiments we backoff the learned program to a 7-gram and 3-gram models and we use cache size of 800 characters. 

3.2. MODEL PERFORMANCE:

We compare the performance of the DSL model, n-gram and neural networks for the tasks of learning character level language models by discussing a number of relevant metrics shown in Table 1 and Table 2 .

Precision In terms of model precision, we can see that as expected, the n-gram model performs worse in both BPC and error rate metrics. However, even though the best BPC is achieved for a 7-gram model, the error rate decreases up to 15-gram. This suggests that none of the smoothing techniques we tried can properly adjust to the data sparsity inherent in the higher order n-gram models. It is however possible that more advanced smoothing techniques such as one based on Pitman-Yor Processes (Teh, 2006) might address this issue. As the DSL model uses the same smoothing technique as n-grams, any improvement to smoothing is directly applicable to it.

As reported by Karpathy et al. (2015) , the LSTM model trained on the Linux Kernel dataset improves BPC over the n-gram. However, in our experiments this improvement did not translate to lower error rate. In contrast, our model is superior to n-gram and LSTM in all configurations, beating the best other model significantly in both evaluation metrics -decreasing BPC by over 0.5 and improving error rate by more than 12%.

For the Hutter Prize Wikipedia dataset, even though the dataset consists of natural language text and is much less structured than the Linux Kernel, our model is competitive with several neural network models. Similar to the results achieved on Linux Kernel, we expect the error rate of the DSL model for Hutter Prize Wikipedia dataset, which is 30.5%, to be comparable to the error rate achieved by other models. However, this experiment shows that our model is less suitable to unstructured text such as the one found on Wikipedia. Query (Sampling) Time Sampling the n-gram is extremely fast, answering ≈ 46, 000 queries per second, as each query corresponds to only a several hash look-ups. The query time for the DSL model is similarly fast, in fact can be even faster, by answering ≈ 62, 000 queries per second. This is because it consists of two steps: (i) executing the TChar program that selects a suitable language model (which is very fast once the program has been learned), and (ii) querying the language model. The reason why the model can be faster is that there are fewer hash lookups which are also faster due to the fact that the specialized language models are much smaller compared to the n-gram (e.g., ≈ 22% of the models simply compute unconditioned probabilities). Adding backoff and cache to the DSL model decreases sampling speed, which is partially because our implementation is currently not optimized for querying and fully evaluates all of the models even though that is not necessary.

Model Size Finally, we include the size of all the trained models measured by the size in MB of the model parameters. The models have roughly the same size except for the n-gram models with high order for which the size increases significantly. We note that the reason why both the n-gram and DSL models are relatively small is that we use hash-based implementation for storing the prediction context. That is, in a 7-gram model the previous 6 characters are hashed into a single number. This decreases the model size significantly at the expense of some hash collisions.

4. RELATED WORK:

Program Synthesis Program synthesis is a well studied research field in which the goal is to automatically discover a program that satisfies a given specification that can be expressed in various forms including input/output examples, logical formulas, set of constraints or even natural language description.In addition to the techniques that typically scale only for smaller programs and attempt to satisfy the specification completely (Alur et al., 2013; Solar-Lezama et al., 2006; Solar-Lezama, 2013; Jha et al., 2010) a recent line of work considers a different setting consisting of large (e.g., millions of examples) and noisy (i.e., no program can satisfy all examples perfectly) datasets. This is the setting that needs to be considered when synthesizing programs in our setting and in a language such as TChar. Here, the work of Raychev et al. (2016b) showed how to efficiently synthesize straight-line programs and how to handle noise, then Raychev et al. (2016a) showed how to synthesize branches, and thework of Heule et al. (2015) proposed a way to synthesize loops.

In our work we take advantage of these existing synthesis algorithms and use them to efficiently synthesize a program in TChar. We propose a simple extension that uses MCMC to sample from a large amount of instructions included in TChar (many more than prior work). Apart from this, no other modifications were required in order to use existing techniques for the setting of character level language modeling we consider here.

Recurrent Neural Networks Recent years have seen an emerging interest in building a neural language models over words (Bengio et al., 2003) , characters (Karpathy et al., 2015; Sutskever et al., 2011; Wu et al., 2016) as well as combination of both (Chung et al., 2017; Kim et al., 2015; Mikolov et al., 2012) . Such models have been shown to achieve state-of-the-art performance in several domains and there is a significant research effort aimed at improving such models further.

In contrast, we take a very different approach, one that aims to explain the data by means of synthesizing a program from a domain specific language. Synthesising such programs efficiently while achieving competitive performance to the carefully tuned neural networks creates a valuable resource that be used as a standalone model, combined with existing neural language models or even used for their training. For example, the context on which the predictions are conditioned is similar to the attention mechanism (Sukhbaatar et al., 2015; Bahdanau et al., 2014) and might be incorporated into that training in the future.

5. CONCLUSION:

In this paper we proposed and evaluated a new approach for building character level statistical language models based on a program that parameterizes the model. We design a language TChar for character level language modeling and synthesize a program in this language. We show that our model works especially well for structured data and is significantly more precise that prior work. We also demonstrate competitive results in the less structured task of modeling English text.

Expressing the language model as a program results in several advantages including easier interpretability, debugging and extensibility with deep semantic domain knowledge by simply incorporating a new instruction in the DSL. We believe that this development is an interesting result in bridging synthesis and machine learning with much potential for future research.

semantics of executing such programs are defined in Section C.1). This probability is obtained using a maximum likelihood estimation (counting):

P f (x t | f (t, x <t )) = Count(f (t, x <t ) • x t ) Count(f (t, x <t ))

where Count(f (t, x <t )•x t ) denotes the number of times label x t is seen in the training dataset after the context produced by f (t, x <t ). Similarly, f (t, x <t ) denotes the number of times the context was seen regardless of the subsequent label. To deal with data sparseness we additionally adjust the obtained probability by using Witten-Bell interpolation smoothing Witten & Bell (1991) . Now lets us consider the case when f consists of multiple SimplePrograms with backoff, i.e.,

f = f 1 backoff d; f 2 , where f 1 ∈ SimpleProgram and f 2 ∈ LMProgram.

Recall from Section 2 that we backoff to the next model if the probability of the most likely character according to the current model is less than a constant d. More formally:

P f (x t | f (t, x <t )) f =f1 backoff d; f2 = P f1 (x t | f 1 (t, x <t )) if d ≥ arg max y∈V P f1 (y | f 1 (t, x <t )) P f2 (x t | f 2 (t, x <t )) otherwise

This means that if f 1 produces a probability distribution that has confidence greater than d about its best prediction, then f 1 is used, otherwise a probability distribution based on f 2 is used. When backoff is used, both probabilities are estimated from the same set of training samples (the dataset that would be used if there was no backoff).

From Programs to Probabilistic Models: an Illustrative Example We illustrate how programs in TChar are executed and a probability distribution is built using a simple example shown in Fig. 2 . Consider the program p ∈ TChar containing two LMPrograms f 1 and f 2 that define two probability distributions P f1 and P f2 respectively.

The program p determines which one to use by inspecting the previous character in the input. Let the input sequence of characters be "a1a2b1b2" where each character corresponds to one training sample. Given the training samples, we now execute p to determine which LMProgram to use as shown in Fig. 2 (left). In our case this splits the dataset into two parts -one for predicting letters and one for numbers.

For numbers, the model based on f 1 = LEFT LEFT WRITE CHAR conditions the prediction on the second to left character in the input. For letters, the model based on f 2 = empty is simply an unconditional probability distribution since executing empty always produces empty context. As can be seen, the context obtained from f 1 already recognizes that the sequence of numbers is repeating. The context from f 2 can however be further improved, especially upon seeing more training samples.

B SYNTHESIZING TChar PROGRAMS:

In this section we describe how programs in our TChar language are synthesized.

B.1 LEARNING SIMPLEPROGRAMS:

We next describe the approach to synthesize good programs f ∈ SimpleProgram such that they minimize the objective function:

f best = arg min f ∈SimpleProgram 1 n n t=1 -log 2 P (x t | f (t, x t )) + λ • Ω(f )

We use a combination of three techniques to solve this optimization problem and find f ≈ best -an exact enumeration, approximate genetic programming search, and MCMC search. Enumerative Search We start with the simplest approach that enumerates all possible programs up to some instruction length. As the number of programs is exponential in the number of instructions, we enumerate only short programs with up to 5 instructions (not considering PREV CHAR(c)) that contain single Write instruction. The resulting programs serve as a starting population for a follow-up genetic programming search.

: "a1a2b1b2" t x<t xt p(t, x<t) 1 a f2 2 a 1 f1 3 a1 a f2 4 a1a 2 f1 5 a1a2 b f2 6 a1a2b 1 f1 7 a1a2b1 b f2 8 a1a2b1b 2 f1 t f1(t, x<t) P f 1 (xt | f1(t, x<t)) 2 unk Count(unk•1) Count(unk) = 1 1 = 1.0 4 1 Count(1•2) Count(1) = 2 2 = 1.0 6 2 Count(2•1) Count(2) = 1 1 = 1.0 8 1 Count(1•2) Count(1) = 2 2 = 1.0 t f2(t, x<t) P f 2 (xt | f2(t, x<t)) 1 ε Count(ε•a) Count(ε) = 2 4 = 0.5 3 ε Count(ε•a) Count(ε) = 2 4 = 0.5 5 ε Count(ε•b) Count(ε) = 2 4 = 0.5 7 ε Count(ε•b) Count(ε) = 2 4 = 0.5 p ::= switch LEFT WRITE CHAR case 'a' or 'b' then LEFT LEFT WRITE CHAR (f1) default empty (f2)

The reason we omit the PREV CHAR(c) instruction is that this instruction is parametrized by a character c that has a large range (of all possible characters in the training data). Considering all variations of this instruction would lead to a combinatorial explosion.

Genetic Programming Search:

The genetic programming search proceeds in several epochs, where each epoch generates a new set of candidate programs by randomly mutating the programs in the current generation. Each candidate program is generated using following procedure:

1. select a random program f from the current generation 2. select a random position i in f , and 3. apply mutation that either removes, inserts or replaces the instruction at position i with a randomly selected new instruction (not considering PREV CHAR(c)).

These candidate programs are then scored with the objective function (2) and after each epoch a subset of them is retained for the next generation white the rest is discarded. The policy we use to discard programs is to randomly select two programs and discard the one with worse score. We keep discarding programs until the generation has less than 25 candidate programs. Finally, we do not apply a cross-over operation in the genetic search procedure.

Markov Chain Monte Carlo Search (MCMC) Once a set of candidate programs is generated using a combination of enumerative search and genetic programming, we apply MCMC search to further improve the programs. This procedure is the only one that considers the PREV CHAR(c) instruction (which has 108 and 212 variations for the Linux Kernel and Hutter Prize Wikipedia datasets respectively).

The synthesized program is a combination of several basic building blocks consisting of a few instructions. To discover a set of good building blocks, at the beginning of the synthesis we first build a probability distribution I that determines how likely a building block will be the one with the best cost metric, as follows:

• consider all building blocks that consist of up to three Move and one Write instruction, B : {empty, Move} 3 × Write.

• score each building block b ∈ B on the full dataset D by calculating the bits-per-character (BPC) b bpc as defined in (1) and the error rate b error rate (as usually defined) on dataset D.

• accept the building block with probability min(1.0, empty bpc /b bpc ) where empty bpc is the score for the unconditioned empty program. Note that for the BPC metric, lower is better. That is, if the program has better (lower) BPC than the empty program it is always accepted and accepted otherwise with probability empty bpc /b bpc .

• for an accepted building block b, set the score as I (b) = 1.0 -b error rate , that is, the score is proportional to the number of samples in the dataset D that are classified correctly using building block b.

• set the probability with which a building block b ∈ B will be sampled by normalizing the distribution I , that is,

I(b) = I (b)/ b ∈B I (b ).

Given the probability distribution I, we now perform random modifications of a candidate program p by appending/removing such blocks according to the distribution I in a MCMC procedure that does a random walk over the set of possible candidate programs. Backoff Programs The synthesis procedure described above can be adapted to synthesize SimplePrograms with backoff using a simple greedy technique that synthesizes the backoff programs one by one. In our implementation we however synthesize only a single SimpleProgram and then backoff to n-grams as described in Section 3. We optimize the backoff threshold d ∈ 0, 1 using a grid search with a step size 0.02 on a validation dataset.

B.2 LEARNING SWITCHPROGRAMS:

Recall from Fig. 1 that the SwitchPrograms have the following syntax:

SwitchProgram ::= switch SimpleProgram case v1 or • • • or v k then TChar • • • case vj or • • • or vn then TChar default TChar

To synthesize a SwitchProgram we need to learn the following components: (i) the predicate in the form of a SimpleProgram, (ii) the branch targets v 1 , v 2 , ..., v n that match the values obtained by executing the predicate, and (iii) a program for each target branch as well as a program that matches the default branch. This is a challenging task as the search space of possible predicates, branch targets and branch programs is huge (even infinite).

To efficiently learn SwitchProgram we use a decision tree learning algorithm that we instantiate with the ID3+ algorithm from Raychev et al. (2016a) . The main idea of the algorithm is to synthesize the program in smaller pieces, thus making the synthesis tractable in practice by using the same idea as in the ID3 decision tree learning algorithm. This synthesis procedure runs in two steps -a top-down pass that synthesizes branch predicates and branch targets, followed by a bottom-up pass that synthesizes branch programs and prunes unnecessary branches.

The top-down pass considers all branch programs to be an unconditioned probability distribution (which can be expressed as an empty SimpleProgram) and searches for best predicates and branch targets that minimize our objective function (i.e., regularized loss of the program on the training dataset). For a given predicate we consider the 32 most common values obtained by executing the predicate on the training data as possible branch targets. We further restrict the generated program to avoid over-fitting to the training data by requiring that each synthesized branch contains either more than 250 training data samples or 10% of the samples in the training dataset. Using this approach we search for a good predicate using the same techniques as described in Appendix B.1 and then apply the same procedure recursively for each program in the branch. The synthesis stops when no predicate is found that improves the loss over a program without branches. For more details and analysis of this procedure, we refer the reader to the work of Raychev et al. (2016a) .

The bottom-up pass then synthesizes approximately best programs for individual branches by invoking the synthesis as described in Appendix B.1. Additionally, we prune branches with higher loss compared to a single SimpleProgram trained on the same dataset.

C FORMAL SEMANTICS OF THE TChar LANGUAGE:

This section provides the formal semantics of TChar.

C.1 SMALL-STEP SEMANTICS OF TChar. • wr(WRITE CHAR, x, i) returns character at position i in the input string x. If i is not within the bounds of x (i.e., i < 1 or i ≥ len(x)) then a special unk character is returned. • wr(WRITE HASH, x, i) returns the hash of all characters seen between the current position i and the position of the latest Write instruction that was executed. More formally, let i prev be the position of the previous write. Then wr(WRITE HASH, x, i) = H(x, i, min(i + 16, i prev )), where H : char * × N × N → N is a hashing function that hashes characters in the string from the given range of positions. The hashing function used in our implementation is defined as follows:

We formally define:

H(x, i, j) =   

x i if i = j H(x, i, j -1) * 137 + x j if i < j ⊥ otherwise where we use ⊥ to denote that the hash function returns no value. This happens in case i > j (i.e., i > i prev ). • wr(WRITE DIST, x, i) returns a distance (i.e., the number of characters) between the current position and the position of latest Write instruction. In our implementation we limit the return value to be at most 16, i.e., wr(WRITE DIST, x, i) = min(16, |i -i prev |). • mv(LEFT, x, i) = max(1, i -1), that is, we move to the position of the previous character in the input.

• mv(RIGHT, x, i) = min(len(x) -1, i + 1), that is, we move to the position of the next character in the input. We use len(x) to denote the length of x.

• mv(PREV CHAR, x, i) = i , where i is the position of the most recent character with the same value as the character at position i, i.e., maximal i such that x i = x i and i < i. If no such character is found in x, a value -1 is returned.

:



Figures and Tables:

Figure 1: Syntax of TChar language for character level language modeling. Program semantics are given in the appendix.



Figure 2: Illustration of a probabilistic model built on an input sequence a1a2b1b2 using program p. (Left) The dataset of samples specified by the input and the result of executing program p on each sample. (Top Right) The result of executing program f 1 on a subset of samples selected by program p and the corresponding probability distribution P f1 . (Bottom Right) The result of executing empty program f 2 and it's corresponding unconditioned probability distribution P f2 . We use the notation ε to describe an empty sequence.

TChar programs to operate on a state σ = x, i, ctx, counts ∈ States where the domain States is defined as States = char * × N × Context × Counts, where x ∈ char * is an input sequence of characters, i ∈ N is a position in the input sequence, Context : (char ∪ N) * is a list of values accumulated by executing Write instructions and Counts : StateSwitch → N is mapping that contains a value denoting current count for each StateSwitch program. Initially, the execution of a program p ∈ lang starts with the empty context [] ∈ Context and counts initialized to value 0 for every StateSwitch program, i.e., counts 0 = ∀sp ∈ StateSwitch . 0. For a program p ∈ TChar, an input string x, and a position i in x, we say that p computes a program m ∈ LMProgram, denoted as p(i, x) = m, iff there exists a sequence of transitions from configuration p, x, i, [], counts i-1 to configuration m, x, i, [], counts i . As usual, a configuration is simply a program coupled with a state. The small-step semantics of executing a TChar program are shown in Fig. 3. These rules describe how to move from one configuration to another configuration by executing instructions from the program p. We next discuss these semantics in detail. C.1.1 SEMANTICS OF Write INSTRUCTIONS The semantics of the Write instructions are described by the [WRITE] rule in Fig. 3. Each write accumulates a value c to the context ctx according to the function wr: wr : Write × char * × N → char ∪ N defined as follows:

Figure 3: TChar language small-step semantics. Each rule is of the type: TChar × States → TChar × States.

.2 SEMANTICS OF Move INSTRUCTIONS The semantics of Move instructions are described by the [MOVE] rule in Fig. 3. Each Move instruction changes the current position in the input by using the following function mv: mv : Move × char * × N → N defined as follows:

In our implementation we truncate WRITE HASH and WRITE DIST to a maximum size of 16.Example With Write and Move instructions, we can express various programs that extract useful context for a given position t in text x. For example, we can encode the context used in trigram language model with a program LEFT WRITE CHAR LEFT WRITE CHAR. We can also express programs such as LEFT PREV CHAR RIGHT WRITE CHAR that finds the previous occurrence of the character on the left of the current position and records the character following it in the context. SimpleProgram is that the context it generates may not work well for the entire dataset, although combining several such programs can generate suitable contexts for the different types of predictions. To handle these cases, we introduce SwitchProgram with switch statements that can conditionally select appropriate subprograms to use depending on the context of the prediction. The checked conditions of switch are themselves program p guard ∈ SimpleProgram that accumulate values that are used to select the appropriate branch that should be executed next. During the learning the goal is then to synthesize best program p guard to be used as a guard, the values v 1 , • • • , v n used as branch conditions as well as the programs to be used in each branch. We note that we support disjunction of values within branch conditions. As a result, even if the same program is to be used for two different contexts v 1 and v 2 , the synthesis procedure can decide whether a single model should be trained for both (by synthesizing a single branch with a disjunction of v 1 and v 2 ) or a separate models should be trained for each (by synthesizing two branches).

Table content: <table><tr><td>2.2 SWITCHPROGRAMS</td></tr><tr><td>A problem of using only one</td></tr></table>

Detailed comparison of LSTM, n-gram and DSL models on Linux Kernel dataset.

Table content: <table><tr><td colspan="4">Linux Kernel Dataset (Karpathy et al., 2015)</td><td/><td/></tr><tr><td/><td>Bits per</td><td>Error</td><td>Training</td><td>Queries</td><td>Model</td></tr><tr><td>Model</td><td colspan="2">Character Rate</td><td>Time</td><td>per Second</td><td>Size</td></tr><tr><td>LSTM (Layers×Hidden Size)</td><td/><td/><td/><td/><td/></tr><tr><td>2×128</td><td>2.31</td><td>40.1%</td><td>≈28 hours</td><td>4 000</td><td>5 MB</td></tr><tr><td>2×256</td><td>2.15</td><td>37.9%</td><td>≈49 hours</td><td>1 100</td><td>15 MB</td></tr><tr><td>2×512</td><td>2.05</td><td>38.1%</td><td>≈80 hours</td><td>300</td><td>53 MB</td></tr><tr><td>n-gram</td><td/><td/><td/><td/><td/></tr><tr><td>4-gram</td><td>2.49</td><td>47.4%</td><td>1 sec</td><td>46 000</td><td>2 MB</td></tr><tr><td>7-gram</td><td>2.23</td><td>37.7%</td><td>4 sec</td><td>41 000</td><td>24 MB</td></tr><tr><td>10-gram</td><td>2.32</td><td>36.2%</td><td>11 sec</td><td>32 000</td><td>89 MB</td></tr><tr><td>15-gram</td><td>2.42</td><td>35.9%</td><td>23 sec</td><td>21 500</td><td>283 MB</td></tr><tr><td>DSL model (This Work)</td><td/><td/><td/><td/><td/></tr><tr><td>TChar w/o cache &amp; backoff</td><td>1.92</td><td>33.3%</td><td>≈8 hours</td><td>62 000</td><td>17 MB</td></tr><tr><td>TChar w/o backoff</td><td>1.84</td><td>31.4%</td><td>≈8 hours</td><td>28 000</td><td>19 MB</td></tr><tr><td>TChar w/o cache</td><td>1.75</td><td>28.0%</td><td>≈8.2 hours</td><td>24 000</td><td>43 MB</td></tr><tr><td>TChar</td><td>1.53</td><td>23.5%</td><td>≈8.2 hours</td><td>3 000</td><td>45 MB</td></tr></table>

The backoff thresholds d are selected by evaluating the model performance on the validation set. Finally, for the Linux Kernel dataset we manually include a StateProgram as a root that distinguishes between comments and code (illustrated in Bits-per-character metric for various neural language models (as reported byChung et al. (2017)) achieved on Hutter Prize Wikipedia dataset where the TChar model achieves competitive results. † State-of-the-art network combining character and word level models that are learned from the data.

Table content: <table><tr><td/><td/><td colspan="3">Hutter Prize Wikipedia Dataset (Hutter, 2012)</td><td/><td/></tr><tr><td colspan="4">Metric n-gram DSL model Stacked LSTM</td><td>MRNN</td><td colspan="2">MI-LSTM HM-LSTM  †</td></tr><tr><td/><td>n = 7</td><td>This Work</td><td>Graves (2013)</td><td colspan="2">Sutskever et al. (2011) Wu et al. (2016)</td><td>Chung et al. (2017)</td></tr><tr><td>BPC</td><td>1.94</td><td>1.62</td><td>1.67</td><td>1.60</td><td>1.44</td><td>1.34</td></tr></table>

Training Time Training time is dominated by the LSTM model that takes several days for the network with the highest number of parameters. On the other hand, training n-gram models is extremely fast since the model is trained simply by counting in a single pass over the training data. The DSL model sits between these two approaches and takes ≈ 8 hours to train. The majority of the DSL training time is spent in the synthesis of SwitchPrograms where one needs to consider a massive search space of possible programs from which the synthesis algorithm aims to find one that is approximately the best (e.g., for Linux Dataset the number of basic instructions is 108 which means that naive enumeration of programs up to size 3 already leads to 108 3 different candidate programs). All of our experiments were performed on a machine with Intel(R) Xeon(R) CPU E5-2690 with 14 cores. All training times are reported for parallel training on CPU. Using GPUs for training of the neural networks might provide additional improvement in training time.

Table content: <table/>

That is, at each step we are given a candidate program, and we sample a random piece from the distriution I to either randomly add it to the candidate program or remove it (if present) from the candidate program. Then, we keep the updated program either if the score (2) of the modified candidate program improves, or sometimes we randomly keep it even if the score did not improve (in order to avoid local optimums).

Table content: <table/>

i, n ∈ N ctx ∈ Context s ∈ TChar op ∈ {SwitchProgram, StateUpdate, StateSwitch} op.guard ∈ SimpleProgram op.cases ∈ Context → TChar op.def ault ∈ TChar counts : StateSwitch → N SwitchProgram op.guard, x, i, [] → , x, i , ctx guard ctx guard ∈ dom(op.cases) op, x, i, ctx, counts -→ op.cases(ctx guard ), x, i, [], counts [SWITCH] op ∈ SwitchProgram op.guard, x, i, [] → , x, i , ctx guard ctx guard / ∈ dom(op.cases) op, x, i, ctx, counts -→ op.def ault, x, i, [], counts [SWITCH-DEF] op ∈ StateUpdate op.guard, x, i, [] → , x, i , ctx guard ctx guard ∈ dom(op.cases) op :: s, x, i, ctx, counts -→ op.cases(ctx guard ) :: s, x, i, [], counts [STATEUPDATE] op ∈ StateUpdate op.guard, x, i, [] → , x, i , ctx guard ctx guard / ∈ dom(op.cases) op:: s, x, i, ctx, counts -→ s, x, i, [], counts [STATEUPDATE-DEF] op1 ∈ {Inc, Dec} n = update(op1, counts(op2)) counts = counts[op2 → n] op1 :: op2, x, i, ctx, counts -→ op2, x, i, [],counts [UPDATE] op ∈ StateSwitch counts[op] ∈ dom(op.cases) op, x, i, ctx, counts -→ op.cases(counts(op)), x, i, [], counts [STATESWITCH] op ∈ StateSwitch counts[op] / ∈ dom(op.cases) op, x, i, ctx, counts -→ op.def ault, x, i, [], counts [STATESWITCH-DEF]

Table content: <table><tr><td>w ∈ Write w :: s, x, i, ctx, counts -v = wr(w, x, i) → s, x, i, ctx • v, counts</td><td>[WRITE]</td></tr><tr><td>m ∈ Move m :: s, x, i, ctx, counts -i = mv(m, x, i) → s, x, i , ctx, counts</td><td>[MOVE]</td></tr><tr><td>op ∈</td><td/></tr></table>

Peer review (iclr2017):
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.