A Compact Forest for Scalable Inference over Entailment and Paraphrase Rules

Roy Bar-Haim, Jonathan Berant, Ido DaganEMNLP 2009 · OpenReview

Abstract: A large body of recent research has been investigating the acquisition and application of applied inference knowledge. Such knowledge may be typically captured as entailment rules, applied over syntactic representations. Efficient inference with such knowledge then becomes a fundamental problem. Starting out from a formalism for entailment-rule application we present a novel packed data-structure and a corresponding algorithm for its scalable implementation. We proved the validity of the new algorithm and established its efficiency analytically and empirically.

Introduction: The Challenge of Combinatorial Explosion

In the field of Textual Entailment (TE), the goal is to determine if a "hypothesis" sentence can be logically inferred from a "source" text. A common approach involves applying semantic entailment rules—transformations like "X is fond of Y $\to$ X likes Y"—to the syntactic parse tree of the source text.

However, this approach faces a severe scalability bottleneck. When multiple independent rules can be applied to different parts of a sentence, the number of possible derived trees grows exponentially. For instance, if a sentence has $k$ independent sites where rules can apply, an explicit generation system must produce $2^k$ variations. In real-world scenarios with long sentences and massive rule bases containing millions of entries, this "exponential explosion" leads to memory exhaustion and prohibitive processing times.

The Compact Forest Framework

To address this, the authors introduce the Compact Forest, a packed data structure that represents a massive set of derived sentences within a single directed acyclic graph (cDAG).

Example of a passive-to-active substitution rule applied to a dependency tree.

The core innovation is the use of Disjunction Edges (d-edges). Unlike a standard dependency tree where a node points to a single child, a d-edge allows a node to point to a set of alternative target nodes. This enables the system to "pack" multiple versions of a sentence into one structure, where all variations share the same unchanged subtrees.

Inference Algorithm and Variable Sharing

The associated Compact Inference Algorithm operates through two main phases:

  1. L-matching: The algorithm searches for the left-hand side (LHS) of a rule within the forest. Because the forest is packed, a single match can represent many matches across different potential sentence variations.
  2. R-instantiation: When a rule is applied, the algorithm avoids copying the entire tree. Instead, it adds only the new nodes from the rule's right-hand side (RHS) and links them back into the forest using d-edges.
The resulting Compact Forest (cDAG) where multiple sentence variations share common subtrees via disjunction edges.

This method maximizes "sharing." For example, if a rule changes a verb but leaves the subject and object intact, the new representation simply points to the existing subject and object subtrees. The authors also utilize "Dual Leaf Variables" to share variables that appear on both sides of a rule without modifiers, further reducing node creation.

Evaluation and Scalability

The system was evaluated using the RTE-3 and RTE-4 benchmarks, utilizing massive rule bases including Wikipedia lexical rules, WordNet, DIRT (automatically learned paraphrase rules), and AmWN.

The results demonstrated a dramatic shift in performance:

  • Efficiency: The compact forest achieved a nearly 400-fold speedup over explicit generation (61ms vs. 24,184ms per pair).
  • Memory: While explicit generation failed on complex examples by exceeding 100,000 nodes, the compact forest handled the same cases with a maximum of only 268 nodes.
  • Accuracy: By enabling the use of large-scale rule bases that were previously computationally too expensive, the authors achieved a statistically significant 3.1% accuracy gain on the RTE-4 dataset.

Conclusion

The Compact Forest transforms the complexity of semantic inference from exponential $\Omega(2^k)$ to linear $O(|T| + k)$. While challenges remain regarding search heuristics and noise in automatically learned rules, this packed representation provides a scalable foundation for deep semantic reasoning and potential applications in natural language generation and paraphrasing.

Summary updated

Abstract

A large body of recent research has been investigating the acquisition and application of applied inference knowledge. Such knowledge may be typically captured as entailment rules, applied over syntactic representations. Efficient inference with such knowledge then becomes a fundamental problem. Starting out from a formalism for entailment-rule application we present a novel packed data-structure and a corresponding algorithm for its scalable implementation. We proved the validity of the new algorithm and established its efficiency analytically and empirically.
BibTeX
@inproceedings{barhaim2009compact,
  author = {Roy Bar-Haim and Jonathan Berant and Ido Dagan},
  title = {{A Compact Forest for Scalable Inference over Entailment and Paraphrase Rules}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2009},
  url = {https://openreview.net/forum?id=HJZNuzMdWr},
}
Figure