Venue: ICLR 2017 workshop

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: This paper seeks to build a neural network component for subsampling data. The idea is to build a layer that takes as input a discrete sequence s_1, ..., s_T along with a probability e_t of keeping each element t of the sequence.  The layer is meant to independently choose whether or not to keep each element s_t based on the probability e_t, and then to assemble the kept inputs into a subsequence.  Rather than execute the layer by sampling, the paper proposes to instead compute a marginal distribution over the outputs under this model. It proposes a dynamic program that runs in O(T^3) time and evaluate the method on a simple toy problem.

While the big idea seems reasonable and the paper is written clearly, I don't think it's developed enough to warrant publication at the workshop at this point. The main issues are as follows:

- I'm not convinced the algorithm is optimal:
-- I'm not convinced the O(T^3) cost is necessary.  I would think that a matrix of $output position$ x $input symbol$ could be computed in O(T^2) time using dynamic programming, and then after having computed this, the expected output could be computed in O(T^2) time by summing over the $input symbol$ dimension. Am I missing something?
-- The algorithm should be implemented in a numerically stable way using log-sum-exps.

- The experiment is very simple and there are no baselines.

- One motivation for subsampling is to shorten a sequence. However, under the marginalization approach, the sequence doesn't actually get shortened. Please discuss this.


Typos:
"extented"

review_title: Reasonable start, but not there yet

final_score: rating: 6: Marginally above acceptance threshold
review_content: Subsampling In Expectation

Summary: 

This paper proposes a way to sample a shorter sequence y=(y_0, y_1, ..., y_t) from the input sequence x=(x_0, ..., x_k) according to the probabilities e=(e_0, ..., e_k). The authors propose a dynamic programming algorithm with the computational complexity of O(T^3) and provide some results on toy task.

A General Comment: The writing of the paper needs some work and the ideas need to be presented more clearly, though I understand that the space limitation makes it difficult to explain everything coherently. Especially, the notation is vague. However, the idea makes sense and it is correct in principal. Actually, we have tried a very similar idea for character-level neural machine translation a few years ago in order to learn hierarchical alignments, but we never managed to make it work. One main limitation we observed at the time for char-level NMT that, this kind of algorithm can only generate monotonic alignments, and for the language pairs such as, Ch-En or Tr-En where the alignments can be highly non-monotonic, we could not observe much improvements and also the vanishing gradients arising from the products and the sigmoids were crippling the training. Efficiency was also another issue for us. But authors of this paper shows that in principle this idea works in the toy cases, I guess the challenge remains to find the right architecture and a way to scale the algorithm to right tasks.

More detailed comments:

In the first page, you say “U \le T”, but neither U nor T has not defined anywhere in the document.
Please present a more precise probabilistic for e_t. You just say p(y_0=s_0) = e_0, but a more general formal definition would be useful.
A figure or the visualization of the automata/algorithm that generates the task would be useful(perhaps in the appendix).
This is more of a curious empirical question, but can this algorithm generalize to the sequences longer than the ones that it has been trained on?

Conclusion,
Pros: - A simple algorithm to subsample the sequences.
- Interesting results on a toy task.

Cons:
- The proposed algorithm is O(T^3) which is quite difficult to scale for the long sequences and realistic tasks.
- The experiments are not convincing enough.
- The writing is not clear enough and needs some more work(this is a minor cons).
review_title: Interesting and plausible idea but needs more work.

Decision: Accept