 Many tasks in natural language processing involve comparing two sentences to compute some notion of relevance, entailment, or similarity. Typically this comparison is done either at the word level or at the sentence level, with no attempt to leverage the inherent structure of the sentence. When sentence structure is used for comparison, it is obtained during a non-differentiable pre-processing step, leading to propagation of errors. We introduce a model of structured alignments between sentences, showing how to compare two sentences by matching their latent structures. Using a structured attention mechanism, our model matches possible spans in the first sentence to possible spans in the second sentence, simultaneously discovering the tree structure of each sentence and performing a comparison, in a model that is fully differentiable and is trained only on the comparison objective. We evaluate this model on two sentence comparison tasks: the Stanford natural language inference dataset and the TREC-QA dataset. We find that comparing spans results in superior performance to comparing words individually, and that the learned trees are consistent with actual linguistic structures. There are many tasks in natural language processing that require comparing two sentences: natural language inference BID1 BID28 and paraphrase detection BID44 are classification tasks over sentence pairs, and question answering often requires an alignment between a question and a passage of text that may contain the answer BID39 BID31 BID17 .Neural models for these tasks almost always perform comparisons between the two sentences either at the word level BID29 ), or at the sentence level BID1 . Word-level comparisons ignore the inherent structure of the sentences being compared, at best relying on a recurrent neural network such as an LSTM BID15 to incorporate some amount of context from neighboring words into each word's representation. Sentence-level comparisons can incorporate the structure of each sentence individually BID2 BID36 , but cannot easily compare substructures between the sentences, as these are all squashed into a single vector. Some models do incorporate sentence structure by comparing subtrees between the two sentences BID46 BID4 , but require pipelined approaches where a parser is run in a non-differentiable preprocessing step, losing the benefits of end-to-end training.In this paper we propose a method, which we call structured alignment networks, to perform comparisons between substructures in two sentences, without relying on an external, non-differentiable parser. We use a structured attention mechanism BID18 BID25 to compute a structured alignment between the two sentences, jointly learning a latent tree structure for each sentence and aligning spans between the two sentences.Our method constructs a CKY chart for each sentence using the inside-outside algorithm BID27 , which is fully differentiable BID22 BID13 . This chart has a node for each possible span in the sentence, and a score for the likelihood of that span being a constituent in a parse of the sentence, marginalized over all possible parses. We take these two charts and find alignments between them, representing each span in each sentence with a structured attention over spans in the other sentence. These span representations , weighted by the span's likelihood, are then used to compare the two sentences. In this way we can perform comparisons between sentences that leverage the internal structure of each sentence in an end-to-end, fully differentiable model, trained only on one final objective. We evaluate this model on several sentence comparison datasets. In experiments on SNLI BID1 and TREC-QA (Voorhees & Tice, 2000) , we find that comparing sentences at the span level consistently outperforms comparing at the word level. Additionally, and in contrast to prior work , we find that learning sentence structure on the comparison objective results in well-formed trees that closely mimic syntax. Our results provide strong motivation for incorporating latent structure into models that implicitly or expliclty compare two sentences. We have considered the problem of comparing two sentences in natural language processing models. We have shown how to move beyond word-and sentence-level comparison to comparing spans between the two sentences, without the need for an external parser. Through experiments on several sentence comparison datasets, we have seen that span comparisons consistently outperform wordlevel comparisons, with no additional supervision. We additionally found our model was able to discover latent tree structures that closely mimic syntax, without any syntactic supervision.Our results have several implications for future work. First, the success of span comparisons over word-level comparisons suggests that it may be profitable to include such comparisons in more complex models, either for comparing two sentences directly, or as intermediate parts of models for more complex tasks, such as reading comprehension. Second, though we have not yet done a formal comparison with prior work on grammar induction, our model's ability to infer trees that look like syntax from a semantic objective is intriguing, and suggestive of future opportunities in grammar induction research. Also, the speed of the model remains a problem, with the insideoutside algorithm involved, the speed of the full model will be be 15-20 times slower than the decomposable attention model, mainly due the the fact this dynamic programming method can not be effectively accelerated on a GPU.
Matching sentences by learning the latent constituency tree structures with a variant of the inside-outside algorithm embedded as a neural network layer. This paper introduces a structured attention mechanisms to compute alignment scores among all possible spans in two given sentences This paper proposes a model of structured alignments between sentences as a means of comparing sentences by matching their latent structures.