Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 8: Accept
review_content: RNA Secondary Structure Prediction by Learning Unrolled Algorithms

This paper proposes E2Efold, which is an RNA secondary structure prediction algorithm based on an unrolled algorithm. Previous methods rely on dynamic programming (which does not work for molecular configurations that do not factorize) or rely on energy-based models (which require a minimization step, e.g. by using MCMC to traverse the energy landscape and find minima). The former does not work for all molecules and the latter can be difficult to optimize. The method presented here is novel, shows strong SOTA performance, and would be of interest to the wider deep learning community.

The method is based on an unrolled algorithm, which is motivated by the inclusion of three inductive biases / constraints important underlying RNA folding. These constraints limit the wide RNA search space. The first component of the method is a “Deep Score Network” which uses a stack of Transformer encoders (with relative and exact positional embeddings) followed by 2D convolutional layers to output a L x L symmetric matrix describing the “scores” of base pairing. As these scores may not obey the rules of RNA folding, a second post-processing network is trained end-to-end together with the “Deep Score Network” to enforce constraints. This network starts with a transformation that symmetrizes the matrix and applies a constraint-enforcing mask. The problem is transformed into an unconstrained problem by using Lagrange multipliers; it is then solved using a proximal gradient. Finally, a recurrent cell is defined that implements this algorithm in a deep learning framework. This method is creative, could be applied to other tasks with constraints, and would be interesting to the wider deep learning community.

In addition to developing the deep score network and post-processing network, the authors also develop a differentiable F1 loss, so that the network can directly optimize for precision and recall on the task. The performance of this method significantly outperforms previous methods. There was a fruitful discussion on OpenReview regarding whether this was a result of overfitting on the task. Indeed, it is critical in deep learning applications to carefully construct train/test sets to avoid high performance by memorization alone. To address this, the authors train on RNAStralign and test on ArchiveII. As the original ArchiveII dataset contains subsequences of other RNA sequences, which can result in overfitting, the authors re-ran their experiment with that removed, and similar results were achieved. To support the hypothesis that ArchiveII and RNAStralign capture different distributions, they perform a permutation test on the unbiased empirical Maximum Mean Discrepancy estimator, finding that the distributions are different. I do wonder why they did not check if P(ArchiveII) = P(ArchiveII) as they do check if P(RNAStr_train) = P(RNAStr_train). On the specific task of pseudoknot prediction, the method also performs well (F1 is >0.23 over the baseline). On sequence length-weighted F1, the model does even better.

The paper is rich with ablations. The analysis of the number of unrolling iterations T helps support the use of an unrolled method and builds intuition for its importance - it would be useful to include this in the appendix of the paper. I also appreciated the visualizations, which are a good sanity check that the model correctly handles pseudoknots. The performance of the method is broken down by RNA family, which is also quite interesting -- the method outperforms LinearFold on all classes, besides 5S RNA, SRP, and Group I intron. Further analysis is required to better understand why the method is weaker on those datasets. Additionally, further work should explore training on one set of families and testing on a held-out set of families. This was pointed out by public comments on this paper. This is potentially a limitation of E2EFold (the authors do not seem to have tried this suggested experiment) and further exploration is required. Exploring this limitation (even if it is not overcome) would make this paper even more rich.

That said, I recommend acceptance of this paper due to the extensive experiments, polished writing, novel method, and strong results, which can inspire future research. 

review_title: Official Blind Review #4

final_score: rating: 8: Accept
review_content: This paper introduces an end-to-end method to predict the secondary structure of RNA, by mapping the nucleotide sequence to a binary affinity matrix. The authors decompose this problem into two part: (i) predicting an affinity score between each base pair in the input sequence, using a combination of a transformer sequence encoder network and a convolutional decoder, and (ii) a post-processing step that ensures that structural local and global constraints are enforced. An innovation is to express this post-processing as an unrolled sequence of proximal gradient descent steps, which are fully differentiable, and allow the full combination of (i)+(ii) to be trained end-to-end. A thorough set of experiments validate the approach.

Overall, the paper is well written and easy to follow. The approach of unrolling structural constraints as shown in the paper is interesting and applicable to much wider domains than secondary structure prediction. The proposed approach appears to provide a novel, convincing and non-obvious solution to RNA secondary structure prediction, and subject to suggestions below, would represent a valuable contribution to ICLR.

The principal area for improvement would be to include additional detail (perhaps in appendix) on the model hyperparameter configurations that were used in the experiments. Moreover, more details on the set of \psi functions, and the MLP details for P_i (e.g. number of hidden units, activation function, the use of dropout, batch normalization, etc) should be given, as well as more information on the specifics how how the “pairwise concatenation” is carried out in the output layer. What unrolling constant T is used? Finally, in the ablation study (p. 8) details on how U_\theta is trained by itself (without the post-processing step) should be given. 

Detailed comments:
* Overall, the whole paper should be thoroughly reviewed for English grammar and writing style; a subset of suggested changes follow.
* p. 1: structure a result ==> structure is a result
* p. 2: energy based methods ==> energy-based methods
* p. 2: energy function based approaches ==> energy function-based approaches
* p. 2: view point ==> viewpoint
* p. 2: E2Efold is flexible ==> E2Efold are flexible
* p. 2: nearly efficient ==> nearly efficiently
* p. 3: typically scale ==> typically scale as
* p. 3: few hundred. ==> few hundreds.
* p. 4: all binary matrix ==> all binary matrices
* p. 4: output space can help ==> output space could help
* p. 5: formulation are the ==> formulation are that the
* p. 6: eq. (7) should contain quantities indexed by $t$ in the RHS
* p. 8: pesudoknotted ==> pseudoknotted
* p. 9 ff: in the bibliography, all lowercase rna should be uppercase RNA. Use {RNA} in bibtex entries.

review_title: Official Blind Review #2

final_score: rating: 8: Accept
review_content: The authors proposed an end-to-end method (E2Efold) to predict RNA secondary structure. The method consists of a Deep Score Network and a Post-Process Network (PPN). The two networks are trained jointly. The score network is a deep learning model with transformer and convolution layers, and the post-process network is solving a constrained optimization problem with an T-step unrolled algorithm. Experimental results demonstrate that the proposed approach outperforms other RNA secondary structure estimation approaches.

Overall I found the paper interesting. Although the writing can be improved and some important details are missing.

Major comments
As the authors point out, several existing approaches for unrolling optimization problems have been proposed. It would be helpful to clarify the methodological novelty of the proposed algorithm compared to those.


Training details and implementation details are missing; these hinder the reproducibility of the proposed approach. The author stated pre-training of the score network, how is the PPN and score network updated during the joint training? Does the model always converge? The authors vaguely mentioned add additional logistic regression loss to Eq9 for regularization. What is a typical number of T? How does varying T affect the performance, both in terms of training time (and convergence) and in terms of accuracy/F1?

Minor comments
The 29.7% improvement of F1 score overstates the improvements compared to non-learning approaches.. This performance was computed on the dataset (RNAStralign) on which E2Efold was trained. A fair comparison, as the authors also stated, is on the independent ArchiveII data. On this data, E2Efold has F1 score 0.686 versus 0.638 for CONTRAfold. The author should report performance improvement under this line.


It would be helpful to report performance per RNA category, both for RNAstralign data and ArchiveII data, while the ArchiveII data should still remain independent. Different models may have their strengths and weaknesses on different RNA types.


It is not obvious to me how the proximal gradient was derived to (3)-(5). It would be helpful if the authors show some details in the supplements.


Why is there a need to introduce an l_1 penalty term to make A sparse?


On which data is Table 6?

Typos, etc.
The references are not consistently formatted
“structure a result” -> “structure is a result”
“a few hundred.” -> “a few hundred base pairs.”
“objective measure the” -> “objective measures the”
“section 5” -> “Section 5” (in several places)
In the equation above Equation 2, should it be -\rho||\hat{A}||_{1} instead of plus? Otherwise, the “max” could be made arbitrarily large.

review_title: Official Blind Review #1

final_score: rating: 6: Weak Accept
review_content: *Summary*
The authors perform RNA secondary prediction using deep learning. The outputs are subject to hard constraints on which nucleotides can be in contact with others. They unroll a sophisticated optimization algorithm for a relaxation of the task of finding the optimal contact map subject to these constraints. This work is in a long line of work demonstrating that end-to-end training of models that incorporate application-specific optimization routines as sub-modules is very useful. In particular, it outperforms an approach where the inputs to this optimization problem come from a network that was trained using a simple loss that ignores the fact that it will feed into this structured optimizer. The paper also considers an application domain that will be unfamiliar to many ICLR readers interested in deep structured prediction, and may serve as a call to arms for the community engaging with additional problems in this field.   

*Overall Assessment*
The paper is well written, well executed, and part of a general research thread that ICLR readers care about. There are a number of technical details, such as the loss function in (8) that will be of general interest. I advocate for acceptance.

*Comments*
The actual specification of the output constraints doesn't occur until late in the paper. Before then, the discussion of them is very abstract. Given that the constraints are easy to describe, the exposition would be improved notably if you described the specific constraints earlier on. This would help me understand the problem domain better.

Fyi, the idea of nested structures vs. non-nested structures appears in NLP in terms of projective parsing vs. non-projective parsing. There may be some relevant reading for you to do there. Your specific work (minus the unrolled constraint enforcement) is similar to "Dozat et al. 2017. Deep biaffine attention for neural dependency parsing."

The idea of backpropping through some constraint-enforcing process is reminiscent of backpropping through belief propagation. See, for example, Domke's "Learning Graphical Model Parameters with Approximate Marginals Inference." Or Hershey et al. "Deep Unfolding: Model-Based Inspiration of Novel Deep Architectures." You should also cite work using unrolled ISTA to learn sparse coding dictionaries. They have terms similar to (5). 

What exactly was your motivation for the setup in "Test On ArchiveII Without Re-training?"

How sensitive is performance to the number of optimizer iterations? Does it work to train with a fixed number of unrolled iters, but at test time run the optimizer until convergence?

(8) is cool!

review_title: Official Blind Review #3

Meta-review: This paper proposes a RNA structure prediction algorithm based on an unrolled inference algorithm. The proposed approach overcomes limitations of previous methods, such as dynamic programming (which does not work for molecular configurations that do not factorize), or energy-based models (which require a minimization step, e.g. by using MCMC to traverse the energy landscape and find minima).

Reviewers agreed that the method presented here is novel on this application domain, has excellent empirical evaluation setup with strong numerical results, and has the potential to be of interest to the wider deep learning community. The AC shares these views and recommends an enthusiastic acceptance. 
Decision: Accept (Talk)