ROCES: Robust Class Expression Synthesis in Description Logics via Iterative Sampling

N'Dah Jean Kouagou, Stefan Heindorf, Caglar Demir, Axel-Cyrille Ngonga NgomoIJCAI 2024

Abstract

Class Expression Learning (CEL) in Description Logics is vital for explainable AI, yet existing neural synthesizers often struggle with varying numbers of input examples. We present ROCES, a neural framework that achieves robustness through a Generalized Learning Problem and iterative sampling. ROCES demonstrates superior performance on small example sets and provides a 1,000x speedup over traditional search-based methods.

Introduction

ROCES (Robust Class Expression Synthesis) is a novel neural framework designed to learn human-readable rules, known as class expressions, from a limited number of examples. By reframing the learning task to focus on minimal data subsets and employing an iterative sampling strategy during training, ROCES achieves high accuracy and a significant speedup—up to 1,000x—over traditional search-based methods, particularly in data-scarce scenarios.

Problem Statement: The Generalization Gap in CEL

In Description Logics (DL), Class Expression Learning (CEL) involves finding a formal, readable rule that describes a set of objects. For instance, given a set of penguins, a CEL system might output: Bird ⊓ CanSwim ⊓ ¬CanFly. These "white-box" models are essential in domains like biomedicine and ontology engineering, where explainability is critical.

While recent deep learning approaches (synthesis-based methods) have improved CEL speed, they suffer from a "generalization gap." These models are typically trained on a fixed number of examples ($N$). If the number of examples provided at runtime deviates from $N$, performance often degrades. In practice, experts may only have a few labeled individuals, making existing neural synthesizers brittle and unreliable for practical use.

Methodology

ROCES introduces two primary innovations to address these robustness issues:

  1. Generalized Learning Problem (GLP): Instead of requiring a model to fit all provided examples, the GLP encourages finding a rule that fits the smallest possible subset. This forces the model to identify defining characteristics rather than overfitting to specific individuals.
  2. Iterative Sampling: During training, ROCES utilizes an algorithm that stochastically samples subsets of varying sizes. By skewing the probability distribution toward smaller sets, the neural network learns to synthesize accurate rules even with limited information.

The architecture utilizes Knowledge Graph Embeddings (ConEx) for data representation and a Set Transformer for example processing. The permutation-invariant nature of the Set Transformer ensures that the order of input examples does not affect the output rule.

Experimental Setup

The framework was evaluated on four benchmark datasets: Semantic Bible (New Testament concepts), Vicodi (European history), Carcinogenesis (chemical compounds), and Mutagenesis (molecular structures). These datasets involve complex relationships and require high precision for domain experts.

Results and Discussion

ROCES demonstrates significant improvements in both accuracy and efficiency compared to state-of-the-art baselines like CELOE, CLIP, and EvoLearner.

Performance on Small Example Sets

As shown in the $F_1$ score analysis, ROCES excels when data is scarce. On the Carcinogenesis and Vicodi datasets, it outperformed baselines by up to 10% in $F_1$ score when provided with only 16 or 64 examples. This robustness is a direct result of the iterative sampling strategy used during training, which acts as a powerful regularizer.

F1 score performance across different numbers of examples for various models.

Efficiency and Scalability

A standout feature of ROCES is its computational efficiency. While traditional search-based methods like CELOE or CLIP explore a vast space of possible rules—often taking minutes—ROCES synthesizes rules in a single forward pass. This results in a 1,000x speedup, with ROCES providing answers in approximately 0.01 seconds, regardless of the number of input examples.

Runtime comparison (in seconds) between ROCES and traditional search-based methods.

Even when provided with full example sets, ROCES remains highly competitive with specialized search-based learners, proving it doesn't sacrifice top-end accuracy for its newfound robustness.

Conclusion

ROCES represents a significant step forward in making neural CEL practical for real-world applications. By training on data subsets, the model becomes capable of handling "out-of-distribution" scenarios where the number of input examples varies. Future work will focus on extending the framework to handle even more expressive description logics beyond $\mathcal{ALCHIQ}(D)$.

Summary updated

BibTeX
@inproceedings{kouagou2024roces,
  author = {N'Dah Jean Kouagou and Stefan Heindorf and Caglar Demir and Axel-Cyrille Ngonga Ngomo},
  title = {{ROCES: Robust Class Expression Synthesis in Description Logics via Iterative Sampling}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2024},
}
Figure