Concept Sketching for Description Logics

Jinghan Wu, Chang Lu, Renate Schmidt, Yizheng Zhao
Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence, PMLR 337:7468-7483, 2026.

Abstract

Domain experts often know *part* of a target description logic (DL) concept (a conjunction involving an existential restriction here, a structural pattern there), yet every existing concept learner ignores this knowledge and searches from scratch. We introduce *concept sketching* for the DL $\mathcal{ALC}$: the expert supplies a partial formula with typed holes (unknown subconcepts, unary or binary constructors), and any suitable back-end learner completes it from labeled examples. This *sketch fitting* problem turns out to have a sharp complexity landscape governed by a single dividing line: the signature size $|\Sigma|$. The problem is NP-complete even for a single hole; with $|\Sigma|$ as parameter it becomes fixed-parameter tractable; but without $|\Sigma|$ it is W[2]-hard, except for Type-2-only sketches which remain tractable. This dichotomy parallels recent results in first-order and decision tree learning. On the statistical side, we prove that each hole type contributes independently to {PAC} sample complexity, with a matching lower bound, so that a sketch capturing even part of the target structure requires provably fewer examples than unrestricted bounded fitting. Experiments on five standard DL benchmarks with two fundamentally different back-ends (SAT-based fitting and evolutionary concept learning) confirm improved accuracy, sample efficiency, and solver speed, demonstrating that sketching benefits are learner-agnostic.

Cite this Paper

BibTeX
@InProceedings{pmlr-v337-wu26d, title = {Concept Sketching for Description Logics}, author = {Wu, Jinghan and Lu, Chang and Schmidt, Renate and Zhao, Yizheng}, booktitle = {Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence}, pages = {7468--7483}, year = {2026}, editor = {Perković, Emilija and Malinsky, Daniel}, volume = {337}, series = {Proceedings of Machine Learning Research}, month = {17--21 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v337/main/assets/wu26d/wu26d.pdf}, url = {https://proceedings.mlr.press/v337/wu26d.html}, abstract = {Domain experts often know *part* of a target description logic (DL) concept (a conjunction involving an existential restriction here, a structural pattern there), yet every existing concept learner ignores this knowledge and searches from scratch. We introduce *concept sketching* for the DL $\mathcal{ALC}$: the expert supplies a partial formula with typed holes (unknown subconcepts, unary or binary constructors), and any suitable back-end learner completes it from labeled examples. This *sketch fitting* problem turns out to have a sharp complexity landscape governed by a single dividing line: the signature size $|\Sigma|$. The problem is NP-complete even for a single hole; with $|\Sigma|$ as parameter it becomes fixed-parameter tractable; but without $|\Sigma|$ it is W[2]-hard, except for Type-2-only sketches which remain tractable. This dichotomy parallels recent results in first-order and decision tree learning. On the statistical side, we prove that each hole type contributes independently to {PAC} sample complexity, with a matching lower bound, so that a sketch capturing even part of the target structure requires provably fewer examples than unrestricted bounded fitting. Experiments on five standard DL benchmarks with two fundamentally different back-ends (SAT-based fitting and evolutionary concept learning) confirm improved accuracy, sample efficiency, and solver speed, demonstrating that sketching benefits are learner-agnostic.} }
Endnote
%0 Conference Paper %T Concept Sketching for Description Logics %A Jinghan Wu %A Chang Lu %A Renate Schmidt %A Yizheng Zhao %B Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2026 %E Emilija Perković %E Daniel Malinsky %F pmlr-v337-wu26d %I PMLR %P 7468--7483 %U https://proceedings.mlr.press/v337/wu26d.html %V 337 %X Domain experts often know *part* of a target description logic (DL) concept (a conjunction involving an existential restriction here, a structural pattern there), yet every existing concept learner ignores this knowledge and searches from scratch. We introduce *concept sketching* for the DL $\mathcal{ALC}$: the expert supplies a partial formula with typed holes (unknown subconcepts, unary or binary constructors), and any suitable back-end learner completes it from labeled examples. This *sketch fitting* problem turns out to have a sharp complexity landscape governed by a single dividing line: the signature size $|\Sigma|$. The problem is NP-complete even for a single hole; with $|\Sigma|$ as parameter it becomes fixed-parameter tractable; but without $|\Sigma|$ it is W[2]-hard, except for Type-2-only sketches which remain tractable. This dichotomy parallels recent results in first-order and decision tree learning. On the statistical side, we prove that each hole type contributes independently to {PAC} sample complexity, with a matching lower bound, so that a sketch capturing even part of the target structure requires provably fewer examples than unrestricted bounded fitting. Experiments on five standard DL benchmarks with two fundamentally different back-ends (SAT-based fitting and evolutionary concept learning) confirm improved accuracy, sample efficiency, and solver speed, demonstrating that sketching benefits are learner-agnostic.
APA
Wu, J., Lu, C., Schmidt, R. & Zhao, Y.. (2026). Concept Sketching for Description Logics. Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research 337:7468-7483 Available from https://proceedings.mlr.press/v337/wu26d.html.

Related Material