Recognizing Entailment and Contradiction by Tree-based Convolution

Lili Mou, Rui Men, Ge Li, Yan Xu, Lu Zhang, Rui Yan, Zhi Jin

TL;DR

The paper introduces TBCNN-pair, a model for Natural Language Inference (NLI) that uses tree-based convolutional neural networks to capture the structural semantics of sentences. By combining these structural embeddings with a set of simple but effective matching heuristics, the model achieves state-of-the-art performance among sentence-encoding approaches while remaining computationally efficient enough for real-world retrieval systems.

What Problem Does This Paper Address?

Natural Language Inference (NLI) is the task of determining the logical relationship between two sentences: a premise and a hypothesis. The goal is to classify the pair as entailment (hypothesis is true given the premise), contradiction (hypothesis is false), or neutral (unrelated).

While neural networks have revitalized this field, most models treat sentences as simple sequences of words. This often misses the underlying grammatical structure that defines meaning. For example, "riding bicycles on the streets" involves specific dependency relations (like the object of the verb) that are more robust to word-order changes than a simple sliding window of words. The authors aim to bridge this gap by incorporating tree-based structures into a "Siamese" neural architecture that can compare two sentences efficiently.

Methods

The authors propose the TBCNN-pair model, which consists of two main stages:

  1. Sentence Modeling (TBCNN): Each sentence is first converted into a dependency parse tree. A Tree-Based Convolutional Neural Network (TBCNN) then slides a feature detector over subtrees (a parent and its children) rather than a linear sequence of words. This allows the model to capture structural features directly. A dynamic max-pooling layer then aggregates these features into a fixed-size vector representation ($h$).
  2. Heuristic Matching: To compare the premise ($h_1$) and hypothesis ($h_2$), the authors use three heuristics to create a combined vector ($m$):
  3. Concatenation: $[h_1; h_2]$ (the standard approach).
  4. Element-wise Product: $h_1 \cdot h_2$ (captures similarity).
  5. Element-wise Difference: $h_1 - h_2$ (captures the "offset" or relationship between concepts).
The TBCNN-pair architecture showing individual sentence modeling and heuristic matching.

Datasets

The model was evaluated on the Stanford Natural Language Inference (SNLI) dataset.

  • Scale: Contains 570k human-written sentence pairs, significantly larger than previous NLI resources.
  • Complexity: The authors provide statistics on the dependency trees generated from this dataset, noting an average of 8.59 nodes per tree and a mean depth of 3.93.
Statistics of the dependency trees in the SNLI dataset.

Key Insights and Ideas

  • Structure is Robust: Tree-based convolution is more resilient to "word order distortion" (caused by modifiers or determiners) than sequential convolution because it focuses on the core grammatical links between words.
  • Heuristics Matter for Optimization: Mathematically, element-wise difference is a special case of concatenation followed by a linear layer. However, the authors found that explicitly including the difference heuristic provided a 1–2% accuracy boost. This suggests that the explicit structure helps the optimization process, even if it doesn't strictly increase the model's theoretical capacity.
  • Efficiency vs. Complexity: Many high-performing models use "attention mechanisms" that compare every word in one sentence to every word in another, resulting in $O(n^2)$ complexity. TBCNN-pair uses a sentence-encoding approach with $O(1)$ matching complexity (after initial encoding), making it much faster for tasks like re-ranking thousands of search results.

Key Results

The TBCNN-pair model achieved a test accuracy of 82.1% on the SNLI dataset.

  • Comparison: It outperformed standard CNNs (77.0%), LSTMs (77.6%), and even a large GRU model using "skip-thought" pretraining (81.4%).
  • Ablation Study: The authors showed that combining all three heuristics (concatenation, product, and difference) was essential for the best performance. Using element-wise product alone was significantly worse than the other options.
Table 3: Accuracy of the TBCNN-pair model in comparison with previous results (bBowman et al., 2015; vVendrov et al., 2015; rRockt¨aschel et al., 2015). “cat” refers to concatenation; “-” and “◦” denote element-wise difference and product, resp.

Limitations and Future Work

  • Parser Dependency: The model's performance is inherently tied to the quality of the dependency parser used in the preprocessing step. Errors in parsing will propagate through the network.
  • Gap with Attention: While TBCNN-pair beats other sentence-encoding models, it still trails slightly behind the most complex $O(n^2)$ attention-based models (like the LSTM with word-by-word attention at 83.5%).
  • Implicit Inference: The authors note that while TBCNN is great for structural semantics, it remains to be seen how well it can be harnessed for more complex, implicit logical reasoning.

Summary updated

Abstract

In this paper, we propose the TBCNN-pair model to recognize entailment and contradiction between two sentences. In our model, a tree-based convolutional neural network (TBCNN) captures sentence-level semantics; then heuristic matching layers like concatenation, element-wise product/difference combine the information in individual sentences. Experimental results show that our model outperforms existing sentence encoding-based approaches by a large margin.
BibTeX
@inproceedings{mou2016recognizing,
  author = {Lili Mou and Rui Men and Ge Li and Yan Xu and Lu Zhang and Rui Yan and Zhi Jin},
  title = {{Recognizing Entailment and Contradiction by Tree-based Convolution}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {2016},
  doi = {10.18653/v1/p16-2022},
}
Figure