Title: LEARNING TO COMPOSE WORDS INTO SENTENCES WITH REINFORCEMENT LEARNING

Abstract: We use reinforcement learning to learn tree-structured neural networks for computing representations of natural language sentences. In contrast with prior work on tree-structured models, in which the trees are either provided as input or predicted using supervision from explicit treebank annotations, the tree structures in this work are optimized to improve performance on a downstream task. Experiments demonstrate the benefit of learning task-specific composition orders, outperforming both sequential encoders and recursive encoders based on treebank annotations. We analyze the induced trees and show that while they discover some linguistically intuitive structures (e.g., noun phrases, simple verb phrases), they are different than conventional English syntactic structures.

1. INTRODUCTION:

Languages encode meaning in terms of hierarchical, nested structures on sequences of words (Chomsky, 1957) . However, the degree to which neural network architectures that compute representations of the meaning of sentences for practical applications should explicitly reflect such structures is a matter for debate. In this work, we use reinforcement learning to learn to construct trees for computing sentence representations, guided by feedback from downstream tasks that depend on these representations. The space of structures that are considered by the learner includes both fully sequential structures (corresponding to traditional recurrent neural network "encoders"), as well as all projective binary trees. Thus, although we take seriously the notion that good compositional architectures might be tree-structured, we specify neither the form of the tree nor whether a tree is necessary at all, and instead leave those decisions up to the learner (and the data).

To place this work in context, there are three predominant approaches for constructing vector representations of sentences from a sequence of words. The first composes words sequentially using a recurrent neural network, treating the RNN's final hidden state as the representation of the sentence (Cho et al., 2014; Sutskever et al., 2014; Kiros et al., 2015) . In such models, there is no explicit hierarchical organization imposed on the words, and the RNN's dynamics must learn to simulate it. The second approach uses tree-structured networks to recursively compose representations of words and phrases to form representations of larger phrases and, finally, the complete sentence. In contrast to sequential models, these models' architectures are organized according to each sentence's syntactic structure, that is, the hierarchical organization of words into nested phrases that characterizes human intuitions about how words combine to form grammatical sentences. Prior work on tree-structured models has assumed that trees are either provided together with the input sentences (Clark et al., 2008; Grefenstette & Sadrzadeh, 2011; Socher et al., 2012; 2013; Tai et al., 2015) or that they are predicted based on explicit treebank annotations jointly with the downstream task (Bowman et al., 2016; Dyer et al., 2016) . The last approach for constructing sentence representations uses convolutional neural networks to produce the representation in a bottom up manner, either with syntactic information (Ma et al., 2015) or without (Kim, 2014; Kalchbrenner et al., 2014) .

Our work can be understood as a compromise between the first two approaches. Rather than using explicit supervision of tree structure, we use reinforcement learning to learn tree structures (and thus, sentence-specific compositional architectures), taking performance on a downstream task that uses the computed sentence representation as the reward signal. In contrast to sequential RNNs, which ignore tree structure, our model still generates a latent tree for each sentence and uses it to structure the composition. Our hypothesis is that encouraging the model to learn tree-structured compositions will bias the model toward better generalizations about how words compose to form sentence meanings, leading to better performance on downstream tasks. This work is related to unsupervised grammar induction (Klein & Manning, 2004; Blunsom & Cohn, 2010; Spitkovsky et al., 2011, inter alia) , which seeks to infer a generative grammar of an infinite language from a finite sample of strings from the language-but without any semantic feedback. Previous work on unsupervised grammar induction that incorporates semantic supervision involves designing complex models for Combinatory Categorial Grammars (Zettlemoyer & Collins, 2005) or marginalizing over latent syntactic structures (Naradowsky et al., 2012) . Since semantic feedback has been proposed as crucial for the acquisition of syntax (Pinker, 1984) , our model offers a simpler alternative.1 However, our primary focus is on improving performance on the downstream model, so the learner may settle on a different solution than conventional English syntax. We thus also explore what kind of syntactic structures are derivable from shallow semantics. Experiments on various tasks (i.e., sentiment analysis, semantic relatedness, natural language inference, and sentence generation) show that reinforcement learning is a promising direction to discover hierarchical structures of sentences. Notably, representations learned this way outperformed both conventional left-to-right models and tree-structured models based on linguistic syntax in downstream applications. This is in line with prior work showing the value of learning tree structures in statistical machine translation models (Chiang, 2007) . Although the induced tree structures manifested a number of linguistically intuitive structures (e.g., noun phrases, simple verb phrases), there are a number of marked differences to conventional analyses of English sentences (e.g., an overall left-branching structure).

2. MODEL:

Our model consists of two components: a sentence representation model and a reinforcement learning algorithm to learn the tree structure that is used by the sentence representation model.

2.1. TREE LSTM:

Our sentence representation model follows the Stack-augmented Parser-Interpreter Neural Network (SPINN; Bowman et al., 2016) , SPINN is a shift-reduce parser that uses Long Short-Term Memory (LSTM; Hochreiter and Schmidhuber, 1997) as its composition function. Given an input sentence of N words x = {x 1 , x 2 , . . . , x N }, we represent each word by its embedding vector x i ∈ R D . The parser maintains an index pointer p starting from the leftmost word (p = 1) and a stack. To parse the sentence, it performs a sequence of operations a = {a 1 , a 2 , . . . , a 2N -1 }, where a t ∈ {SHIFT, REDUCE}. A SHIFT operation pushes x p to the stack and moves the pointer to the next word (p ++ ); while a REDUCE operation pops two elements from the stack, composes them to a single element, and pushes it back to the stack. SPINN uses Tree LSTM (Tai et al., 2015; Zhu et al., 2015) as the REDUCE composition function, which we follow. In Tree LSTM, each element of the stack is represented by two vectors, a hidden state representation h and a memory representation c. Two elements of the stack (h i , c i ) and (h j , c j ) are composed as:

i = σ(W I [h i , h j ] + b I ) o = σ(W O [h i , h j ] + b I ) f L = σ(W F L [h i , h j ] + b F L ) f R = σ(W F R [h i , h j ] + b F R ) g = tanh(W G [h i , h j ] + b G ) c = f L c i + f R c j + i g h = o c (1)

where [h i , h j ] denotes concatenation of h i and h j , and σ is the sigmoid activation function.

A unique sequence of {SHIFT, REDUCE} operations corresponds to a unique binary parse tree of the sentence. A SHIFT operation introduces a new leaf node in the parse tree, while a REDUCE operation combines two nodes by merging them into a constituent. See Figure 1 for an example. We note that for a sentence of length N , there are exactly N SHIFT operations and N -1 REDUCE operations that are needed to produce a binary parse tree of the sentence. The final sentence representation produced by the Tree LSTM is the hidden state of the final element of the stack h N -1 (i.e., the topmost node of the tree).

Tracking LSTM. SPINN optionally augments Tree LSTM with another LSTM that incorporates contextual information in sequential order called tracking LSTM, which has been shown to improve performance for textual entailment. It is a standard recurrent LSTM network that takes as input the hidden states of the top two elements of the stack and the embedding vector of the word indexed by the pointer at timestep t. Every time a REDUCE operation is performed, the output of the tracking LSTM e is included as an additional input in Eq. 1 (i.e., the input to the REDUCE composition function is

[h i , h j , e] instead of [h i , h j ]).

2.2. REINFORCEMENT LEARNING:

In previous work (Tai et al., 2015; Bowman et al., 2016) , the tree structures that guided composition orders of Tree LSTM models are given directly as input (i.e., a is observed and provided as an input). Formally, each training data is a triplet {x, a, y}. Tai et al. ( 2015) consider models where a is also given at test time, whereas Bowman et al. ( 2016) explore models where a can be either observed or not at test time. When it is only observed during training, a policy is trained to predict a at test time.

Note that in this case the policy is trained to match explicit human annotations (i.e., Penn TreeBank annotations), so the model learns to optimize representations according to structures that follows human intuitions. They found that models that observe a at both training and test time are better than models that only observe a during training.

Our main idea is to use reinforcement learning (policy gradient methods) to discover the best tree structures for the task that we are interested in. We do not place any kind of restrictions when learning these structures other than that they have to be valid binary parse trees, so it may result in tree structures that match human linguistic intuition, heavily right or left branching, or other solutions if they improve performance on the downstream task.

We parameterize each action a ∈ {SHIFT, REDUCE} by a policy network π(a | s; W R ), where s is a representation of the current state and W R is the parameter of the network. Specifically, we use a two-layer feedforward network that takes the hidden states of the top two elements of the stack h i and h j and the embedding vector of the word indexed by the pointer x p as its input:

s = ReLU(W 1 R [h i , h j , x p ] + b 1 R ) such that π(a | s; W R ) ∝ exp(w 2 R s + b 2 R ) where [h i , h j , x p ] denotes concatenation of vectors inside the brackets.

If a is given as part of the training data, the policy network can be trained-in a supervised training regime-to predict actions that result in trees that match human intuitions. Our training data, on the other hand, is a tuple {x, y}. We use REINFORCE (Williams, 1992) , which is an instance of a broader class of algorithms called policy gradient methods, to learn W R such that the sequence of actions a = {a 1 , . . . , a T } maximizes:

R(W) = E π(a,s;W R ) T t=1 r t a t ,

where r t is the reward at timestep t. We use performance on a downstream task as the reward function. For example, if we are interested in using the learned sentence representations in a classification task, our reward function is the probability of predicting the correct label using a sentence representation composed in the order given by the sequence of actions sampled from the policy network, so R(W) = log p(y | T-LSTM(x); W), where we use W to denote all model parameters (Tree LSTM, policy network, and classifier parameters), y is the correct label for input sentence x, and x is represented by the Tree LSTM structure in §2.1. For a natural language generation task where the goal is to predict the next sentence given the current sentence, we can use the probability of predicting words in the next sentence as the reward function, so R(W) = log p(x s+1 | T-LSTM(x s ); W).

Note that in our setup, we do not immediately receive a reward after performing an action at timestep t. The reward is only observed at the end after we finish creating a representation for the current sentence with Tree LSTM and use the resulting representation for the downstream task. At each timestep t, we sample a valid action according to π(a | s; W R ). We add two simple constraints to make the sequence of actions result in a valid tree: REDUCE is forbidden if there are fewer than two elements on the stack, and SHIFT is forbidden if there are no more words to read from the sentence. After reaching timestep 2N -1, we construct the final representation and receive a reward that is used to update our model parameters.

We experiment with two learning methods: unsupervised structures and semi-supervised structures. Suppose that we are interested in a classification task. In the unsupervised case, the objective function that we maximize is log p(y | T-LSTM(x); W). In the semi-supervised case, the objective function for the first E epochs also includes a reward term for predicting the correct SHIFT or RE-DUCE actions obtained from an external parser-in addition to performance on the downstream task, so we maximize log p(y | T-LSTM(x); W) + log π(a | s; W R ). The motivation behind this model is to first guide the model to discover tree structures that match human intuitions, before letting it explore other structures close to these ones. After epoch E, we remove the second term from our objective function and continue maximizing the first term. Note that unsupervised and semi-supervised here refer to the tree structures, not the nature of the downstream task.

3. EXPERIMENTS:



3.1. BASELINES:

The goal of our experiments is to evaluate our hypothesis that we can discover useful task-specific tree structures (composition orders) with reinforcement learning. We compare the following composition methods (the last two are unique to our work):

• Right to left: words are composed from right to left.2 • Left to right: words are composed from left to right. This is the standard recurrent neural network composition order. • Bidirectional: A bidirectional right to left and left to right models, where the final sentence embedding is an average of sentence embeddings produced by each of these models. • Balanced binary tree: words are composed according to a balanced binary parse tree of the sentence. • Supervised syntax: words are composed according to a predefined parse tree of the sentence. When parse tree information is not included in the dataset, we use Stanford parser (Klein & Manning, 2003) to parse the corpus. • Semi-supervised syntax: a variant of our reinforcement learning method, where for the first E epochs we include rewards for predicting predefined parse trees given in the supervised model, before letting the model explore other kind of tree structures at later epochs (i.e., semi-supervised structures in §2.2). • Latent syntax: another variant of our reinforcement learning method where there is no predefined structures given to the model at all (i.e., unsupervised structures in §2.2).

For learning, we use stochastic gradient descent with minibatches of size 1 and 2 regularization constant tune on development data from {10 -4 , 10 -5 , 10 -6 , 0}. We use performance on development data to choose the best model and decide when to stop training.

3.2. TASKS:

We evaluate our method on four sentence representation tasks: sentiment classification, semantic relatedness, natural language inference (entailment), and sentence generation. We show statistics of the datasets in Table 1 and describe each task in detail in this subsection. (Socher et al., 2013) . We use the binary classification task where the goal is to predict whether a sentence is a positive or a negative movie review.

We set the word embedding size to 100 and initialize them with Glove vectors (Pennington et al., 2014) 3 . For each sentence, we create a 100-dimensional sentence representation s ∈ R 100 with Tree LSTM, project it to a 200-dimensional vector and apply ReLU: q = ReLU(W p s + b p ), and compute p(ŷ = c | q; w q ) ∝ exp(w q,c q + b q ).

We run each model 3 times (corresponding to 3 different initialization points) and use the development data to pick the best model. We show the results in Table 2 . Our results agree with prior work that have shown the benefits of using syntactic parse tree information on this dataset (i.e., supervised recursive model is generally better than sequential models). The best model is the latent syntax model, which is also competitive with results from other work on this dataset. Both the latent and semi-supervised syntax models outperform models with predefined structures, demonstrating the benefit of learning task-specific composition orders. 1.2m RNTN (Socher et al., 2013) 85.4 -DCNN (Kalchbrenner et al., 2014) 86.8 -CNN-random (Kim, 2014) 82.7 -CNN-word2vec (Kim, 2014) 87.2 -CNN-multichannel (Kim, 2014) 88.1 -NSE (Munkhdalai & Yu, 2016a) 89.7 5.4m NTI-SLSTM (Munkhdalai & Yu, 2016b) 87.8 4.4m NTI-SLSTM-LSTM (Munkhdalai & Yu, 2016b) Semantic relatedness. The second task is to predict the degree of relatedness of two sentences from the Sentences Involving Compositional Knowledge corpus (SICK; Marelli et al., 2014) . In this dataset, each pair of sentences are given a relatedness score on a 5-point rating scale. For each sentence, we use Tree LSTM to create its representations. We denote the final representations by {s 1 , s 2 } ∈ R 100 . We construct our prediction by computing: and [u, v] denotes concatenation of vectors inside the brackets. We learn the model to minimize mean squared error.

u = (s 2 -s 1 ) 2 , v = s 1 s 2 , q = ReLU(W p [u, v] + b p ), and ŷ = w q q + b q , where W p ∈ R 200×200 , b p ∈ R 200 , w q ∈ R 200 , b q ∈ R 1 are model parameters,

We run each model 5 times and use the development data to pick the best model. Our results are shown in Table 3 . Similarly to the previous task, they clearly demonstrate that learning the tree structures yields better performance.

We also provide results from other work on this dataset for comparisons. Some of these models (Lai & Hockenmaier, 2014; Jimenez et al., 2014; Bjerva et al., 2014) rely on feature engineering and are designed specifically for this task. Our Tree LSTM implementation performs competitively with most models in terms of mean squared error. Our best model-semi-supervised syntax-is better than most models except LSTM models of Tai et al. ( 2015) which were trained with a different objective function. 4 Nonetheless, we observe the same trends with their results that show the benefit of using syntactic information on this dataset. Stanford Natural Language Inference. We next evaluate our model for natural language inference (i.e., recognizing textual entailment) using the Stanford Natural Language Inference corpus (SNLI; Bowman et al., 2015) . Natural language inference aims to predict whether two sentences are entailment, contradiction, or neutral, which can be formulated as a three-way classification problem. Given a pair of sentences, similar to the previous task, we use Tree LSTM to create sentence representations {s 1 , s 2 } ∈ R 100 for each of the sentences. Following Bowman et al. ( 2016), we construct our prediction by computing:

u = (s 2 -s 1 ) 2 , v = s 1 s 2 , q = ReLU(W p [u, v, s 1 , s 2 ]+b p ),

and p(ŷ = c | q; w q ) ∝ exp(w q,c q + b q ), where

W p ∈ R 200×400 , b p ∈ R 200 , w q ∈ R 200 , b q ∈ R 1 are model parameters.

The objective function that we maximize is the log likelihood of the correct label under the models.

We show the results in Table 4 . The latent syntax method performs the best. Interestingly, the sequential left to right model is better than the supervised recursive model in our experiments, which contradicts results from Bowman et al. ( 2016) that show 300D-LSTM is worse than 300D-SPINN. A possible explanation is that our left to right model has identical number of parameters with the supervised model due to the inclusion of the tracking LSTM even in the left to right model (the only difference is in the composition order), whereas the models in Bowman et al. ( 2016) have different number of parameters. Due to the poor performance of the supervised model relative to the unsupervised model, semi-supervised training can only mitigate the loss in accuracy, rather than improve over unsupervised learning. Our models underperform state-of-the-art models on this dataset that have almost four times the number of parameters. We only experiment with smaller models since tree-based models with dynamic structures (e.g., our semi-supervised and latent syntax models) take longer to train. See §4 for details and discussions about training time. (Vendrov et al., 2016) 81.4 15.0m 300D-CNN (Mou et al., 2016) 82.1 9m 300D-NTI (Munkhdalai & Yu, 2016b) 83.4 9.5m 300D-NSE (Munkhdalai & Yu, 2016a) 84.6 8.5m

Sentence generation. The last task that we consider is natural language generation. Given a sentence, the goal is to maximize the probability of generating words in the following sentence. This is a similar setup to the Skip Thought objective (Kiros et al., 2015) , except that we do not generate the previous sentence as well. Given a sentence, we encode it with Tree LSTM to obtain s ∈ R 100 . We use a bag-of-words model as our decoder, so p(w i | s; V) ∝ exp(v i s), where V ∈ R 100×29,209 and v i ∈ R 100 is the i-th column of V. Using a bag-of-words decoder as opposed to a recurrent neural network decoder increases the importance of producing a better representation of the current sentence, since the model cannot rely on a sophisticated decoder with a language model component to predict better. This also greatly speeds up our training time.

We use IMDB movie review corpus (Diao et al., 2014) 

4. DISCUSSION:

Learned Structures. Our results in §3 show that our proposed method outperforms competing methods with predefined composition order on all tasks. The right to left model tends to perform worse than the left to right model. This suggests that the left to right composition order, similar to how human reads in practice, is better for neural network models. Our latent syntax method is able to discover tree structures that work reasonably well on all tasks, regardless of whether the task is better suited for a left to right or supervised syntax composition order.

We inspect what kind of structures the latent syntax model learned and how closely they match human intuitions. We first compute unlabeled bracketing F 1 scores5 for the learned structures and parses given by Stanford parser on SNLI and Stanford Sentiment Treebank. In the SNLI dataset, there are 10,000 pairs of test sentences (20,000 sentences in total), while the Stanford Sentiment Treebank test set contains 1,821 test sentences. The F 1 scores for the two datasets are 41.73 and 40.51 respectively. For comparisons, F 1 scores of a right (left) branching tree are 19.94 (41.37) for SNLI and 12.96 (38.56) for SST.

We also manually inspect the learned structures. We observe that in SNLI, the trees exhibit overall left-branching structure, which explains why the F 1 scores are closer to a left branching tree structure. Note that in our experiments on this corpus, the supervised syntax model does not perform as well as the left-to-right model, which suggests why the latent syntax model tends to converge towards the left-to-right model. We handpicked two examples of trees learned by our model and show them in Figure 2 . We can see that in some cases the model is able to discover concepts such as noun phrases (e.g., a boy, his sleds) and simple verb phrases (e.g., wearing sunglasses, is frowning).

Of course, the model sometimes settles on structures that make little sense to humans. We show two such examples in Figure 3 , where the model chooses to compose playing frisbee in and outside a as phrases.

Training Time. A major limitation of our proposed model is that it takes much longer to train compared to models with predefined structures. We observe that our models only outperforms models with fixed structures after several training epochs; and on some datasets such as SNLI or IMDB, an epoch could take a 5-7 hours (we use batch size 1 since the computation graph needs to be reconstructed for every example at every iteration depending on the samples from the policy network). This is also the main reason that we could only use smaller 100-dimensional Tree LSTM models in all our experiments. While for smaller datasets such as SICK the overall training time is approximately 6 hours, for SNLI or IMDB it takes 3-4 days for the model to reach convergence. In general, the latent syntax model and semi-supervised syntax models take about two or three times longer to converge compared to models with predefined structures.

:

Our model only produces an interpretation grammar that parses language instead of a generative grammar.

We choose to include right to left as a baseline since a right-branching tree structure-which is the output of a right to left composition order-has been shown to be a reliable baseline for unsupervised grammar induction(Klein & Manning, 2004).

http://nlp.stanford.edu/projects/glove/

Our experiments with the regularized KL-divergence objective function(Tai et al., 2015) do not result in significant improvements, so we choose to report results with the simpler mean squared error objective function.

We use evalb toolkit from http://nlp.cs.nyu.edu/evalb/.

Figures and Tables:

Figure1: Four examples of trees and their corresponding SHIFT (S) and REDUCE (R) sequences. In each of the examples, there are 4 input words (4 leaf nodes), so 7 operations (4 S, 3 R) are needed to construct a valid tree. The nodes are labeled with the timesteps in which they are introduced to the trees t ∈ {1, . . . , 7}. A SHIFT operation introduces a leaf node, whereas a REDUCE operation introduces a non-leaf node by combining two previously introduced nodes. We can see that different S-R sequences lead to different tree structures.

Figure 3: Examples of unconventional tree structures.

Descriptive statistics of datasets used in our experiments.

Table content: <table><tr><td colspan="5">Dataset # of train # of dev # of test Vocab size</td></tr><tr><td>SICK</td><td>4,500</td><td>500</td><td>4,927</td><td>2,172</td></tr><tr><td>SNLI</td><td>550,152</td><td>10,000</td><td>10,000</td><td>18,461</td></tr><tr><td>SST</td><td>98,794</td><td>872</td><td>1,821</td><td>8,201</td></tr><tr><td>IMDB</td><td colspan="3">441,617 223,235 223,236</td><td>29,209</td></tr><tr><td colspan="5">Stanford Sentiment Treebank. We evaluate our model on a sentiment classification task from the</td></tr><tr><td>Stanford Sentiment Treebank</td><td/><td/><td/><td/></tr></table>

Classification accuracy on Stanford Sentiment Treebank dataset. The number of parameters includes word embedding parameters and is our approximation when not reported in previous work.

Table content: <table><tr><td colspan="2">Model Acc. # params.</td></tr><tr><td>100D-Right to left 83.9</td><td>1.2m</td></tr><tr><td>100D-Left to right 84.7</td><td>1.2m</td></tr><tr><td>100D-Bidirectional 84.7</td><td>1.5m</td></tr><tr><td>100D-Balanced binary tree 85.1</td><td>1.2m</td></tr><tr><td>100D-Supervised syntax 85.3</td><td>1.2m</td></tr><tr><td>100D-Semi-supervised syntax 86.1</td><td>1.2m</td></tr><tr><td>100D-Latent syntax 86.5</td><td/></tr></table>

Mean squared error on SICK dataset.

Table content: <table><tr><td>Model</td><td colspan="2">MSE # params.</td></tr><tr><td colspan="2">100D-Right to left 0.461</td><td>1.0m</td></tr><tr><td colspan="2">100D-Left to right 0.394</td><td>1.0m</td></tr><tr><td colspan="2">100D-Bidirectional 0.373</td><td>1.3m</td></tr><tr><td colspan="2">100D-Balanced binary tree 0.455</td><td>1.0m</td></tr><tr><td colspan="2">100D-Supervised syntax 0.381</td><td>1.0m</td></tr><tr><td colspan="2">100D-Semi-supervised syntax 0.320</td><td>1.0m</td></tr><tr><td colspan="2">100D-Latent syntax 0.359</td><td>1.0m</td></tr><tr><td colspan="2">Illinois-LH (Lai &amp; Hockenmaier, 2014) 0.369</td><td>-</td></tr><tr><td colspan="2">UNAL-NLP(Jimenez et al., 2014) 0.356</td><td>-</td></tr><tr><td colspan="2">Meaning Factory (Bjerva et al., 2014) 0.322</td><td>-</td></tr><tr><td colspan="2">DT-RNN (Socher et al., 2014) 0.382</td><td>-</td></tr><tr><td colspan="2">Mean Vectors (Tai et al., 2015) 0.456</td><td>650k</td></tr><tr><td colspan="2">Left to Right LSTM (Tai et al., 2015) 0.283</td><td>1.0m</td></tr><tr><td colspan="2">Bidirectional LSTM (Tai et al., 2015) 0.274</td><td>1.0m</td></tr><tr><td colspan="2">Constituency Tree-LSTM (Tai et al., 2015) 0.273</td><td>1.0m</td></tr><tr><td colspan="2">Dependency Tree-LSTM (Tai et al., 2015) 0.253</td><td>1.0m</td></tr></table>

Classification accuracy on SNLI dataset.

Table content: <table><tr><td colspan="2">Model Acc. # params.</td></tr><tr><td>100D-Right to left 79.1</td><td>2.3m</td></tr><tr><td>100D-Left to right 80.2</td><td>2.3m</td></tr><tr><td>100D-Bidirectional 80.2</td><td>2.6m</td></tr><tr><td>100D-Balanced binary tree 77.4</td><td>2.3m</td></tr><tr><td>100D-Supervised syntax 78.5</td><td>2.3m</td></tr><tr><td>100D-Semi-supervised syntax 80.2</td><td>2.3m</td></tr><tr><td>100D-Latent syntax 80.5</td><td>2.3m</td></tr><tr><td>100D-LSTM (Bowman et al., 2015) 77.6</td><td>5.7m</td></tr><tr><td>300D-LSTM (Bowman et al., 2016) 80.6</td><td>8.5m</td></tr><tr><td>300D-SPINN (Bowman et al., 2016) 83.2</td><td>9.2m</td></tr><tr><td>1024D-GRU</td><td/></tr></table>

for this experiment, The corpus consists of280,593, 33,793, and 34,029  reviews in training, development, and test sets respectively. We construct our data using the development and test sets of this corpus. For training, we process 33,793 reviews from the original development set to get 441,617 pairs of sentences. For testing, we use 34,029 reviews in the test set (446,471 pairs of sentences). Half of these pairs is used as our development set to tune hyperparamaters, and the remaining half is used as our final test set. Our results in Table5further demonstrate that methods that learn tree structures perform better than methods that have fixed structures.

Table content: <table/>

Word perplexity on the sentence generation task. We also show perplexity of the model that does not condition on the previous sentence (unconditional) when generating bags of words for comparison.

Table content: <table><tr><td colspan="3">Model Perplexity # params.</td></tr><tr><td>100D-Unconditional</td><td>105.6</td><td>30k</td></tr><tr><td>100D-Right to left</td><td>101.4</td><td>6m</td></tr><tr><td>100D-Left to right</td><td>101.1</td><td>6m</td></tr><tr><td>100D-Bidirectional</td><td>100.2</td><td>6.2m</td></tr><tr><td>100D-Balanced binary tree</td><td>103.3</td><td>6.2m</td></tr><tr><td>100D-Supervised syntax</td><td>100.8</td><td>6m</td></tr><tr><td>100D-Semi-supervised syntax</td><td>98.4</td><td>6m</td></tr><tr><td>100D-Latent syntax</td><td>99.0</td><td>6m</td></tr></table>

Peer review (iclr2017):
The paper proposes to use reinforcement learning to learn how to compose the words in a sentence, i.e. parse tree, that can be helpful for the downstream tasks. To do that, the shift-reduce framework is employed and RL is used to learn the policy of the two actions SHIFT and REDUCE. The experiments on four datasets (SST, SICK, IMDB, and SNLI) show that the proposed approach outperformed the approach using predefined tree structures (e.g. left-to-right, right-to-left). The paper is well written and has two good points. Firstly, the idea of using RL to learn parse trees using downstream tasks is very interesting and novel. And employing the shift-reduce framework is a very smart choice because the set of actions is minimal (shift and reduce). Secondly, what shown in the paper somewhat confirms the need of parse trees. This is indeed interesting because of the current debate on whether syntax is helpful. I have the following comments: - it seems that the authors weren*t aware of some recent work using RL to learn structures for composition, e.g. Andreas et al (2016). - because different composition functions (e.g. LSTM, GRU, or classical recursive neural net) have different inductive biases, I was wondering if the tree structures found by the model would be independent from the composition function choice. - because RNNs in theory are equivalent to Turing machines, I was wondering if restricting the expressiveness of the model (e.g. reducing the dimension) can help the model focus on discovering more helpful tree structures. Ref: Andreas et al. Learning to Compose Neural Networks for Question Answering. NAACL 2016