Higher-order logical inference with compositional semantics

Koji Mineshima, Pascual Martínez-Gómez, Yusuke Miyao, Daisuke BekkiEMNLP 2015 · OpenReview

Abstract: Koji Mineshima, Pascual Martínez-Gómez, Yusuke Miyao, Daisuke Bekki. Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing.

2015.

Introduction

In formal semantics, it is widely accepted that natural language requires higher-order logic (HOL) or type theory for full representation. However, the computational linguistics community has traditionally avoided HOL, fearing it is "hopelessly inefficient" for practical applications. Most systems instead rely on First-Order Logic (FOL) approximations or "natural logic" based on surface structures. These methods often struggle with complex linguistic phenomena such as generalized quantifiers (e.g., "most") and intensional operators (e.g., "believe").

This paper challenges the inefficiency myth by presenting an end-to-end inference system that combines a wide-coverage Combinatory Categorial Grammar (CCG) parser with the Coq proof assistant. The authors demonstrate that a well-engineered HOL system can be both more expressive and faster than state-of-the-art FOL systems.

Methodology

The authors developed a pipeline that transforms raw text into logical proofs through several stages:

  1. Parsing: The system uses the C&C parser to generate CCG derivations.
  2. Semantic Composition: Syntactic outputs are mapped to semantic representations using $\lambda$-calculus. A significant contribution is the refined handling of post-NP modifiers, such as relative clauses, to ensure logical consistency between syntax and semantics.
CCG derivation and semantic composition for the sentence "Every student who works comes".
  1. Inference Engine: Rather than a standard FOL solver, the system employs Coq, an interactive theorem prover. The authors automated Coq using its internal tactic language (Ltac) to handle first-order inferences automatically while applying targeted higher-order axioms for complex cases like monotonicity and veridicality.

Evaluation and Results

The system was evaluated using 181 problems from the FraCaS test suite, a benchmark for linguistic coverage in inference systems. The evaluation focused on six key sections: Quantifiers, Plurals, Adjectives, Comparatives, Verbs, and Attitudes.

The HOL system was compared against Nutcracker, a state-of-the-art system based on the FOL-driven Boxer. The results showed a clear advantage for the higher-order approach in both accuracy and computational efficiency.

Accuracy comparison across FraCaS sections for the proposed HOL system and Nutcracker.

Key findings include:

  • Accuracy: The HOL system achieved 69% total accuracy, significantly outperforming Nutcracker’s 50%.
  • Efficiency: The HOL system averaged 3.72 seconds per problem, nearly three times faster than Nutcracker's 11.23 seconds.
  • Robustness: While Nutcracker timed out on 57 of the 181 problems, the HOL system recorded zero time-outs.
  • Ablation Study: Removing higher-order rules caused accuracy to drop to 59%, confirming that HOL components are essential for handling complex linguistic features.

Discussion and Future Work

The study proves that HOL inference is not inherently slow when paired with a targeted set of axioms and a manageable semantic lexicon. The primary source of error was found to be the CCG parser, particularly with multi-word expressions.

Future research will focus on expanding lexical coverage and integrating treatments for anaphora, ellipsis, and temporal logic. While FraCaS provides a controlled environment for testing linguistic logic, applying this HOL framework to noisier, real-world datasets remains the next major challenge for the field.

Summary updated

BibTeX
@inproceedings{mineshima2015higher,
  author = {Koji Mineshima and Pascual Martínez-Gómez and Yusuke Miyao and Daisuke Bekki},
  title = {{Higher-order logical inference with compositional semantics}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2015},
  url = {https://openreview.net/forum?id=elHWt3kWuhE},
}
Figure