SAT-Based Bounded Fitting for the Description Logic ALC

• URL: http://arxiv.org/abs/2507.21752v1
• Date: Tue, 29 Jul 2025 12:32:16 GMT
• Title: SAT-Based Bounded Fitting for the Description Logic ALC
• Abstract summary: We investigate bounded fitting for the description logic ALC and its syntactic fragments.<n>We show that the underlying size-restricted fitting problem is NP-complete for all studied fragments.<n>We present an implementation of bounded fitting in ALC and its fragments based on a SAT solver.
• Score: 7.193373053157516
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Bounded fitting is a general paradigm for learning logical formulas from positive and negative data examples, that has received considerable interest recently. We investigate bounded fitting for the description logic ALC and its syntactic fragments. We show that the underlying size-restricted fitting problem is NP-complete for all studied fragments, even in the special case of a single positive and a single negative example. By design, bounded fitting comes with probabilistic guarantees in Valiant's PAC learning framework. In contrast, we show that other classes of algorithms for learning ALC concepts do not provide such guarantees. Finally, we present an implementation of bounded fitting in ALC and its fragments based on a SAT solver. We discuss optimizations and compare our implementation to other concept learning tools.

Related papers

• Bounded Fitting for Expressive Description Logics [6.136487946258519]
  Bounded fitting is an attractive paradigm for learning logical formulas from labeled data examples.<n>We study bounded fitting for learning concepts in expressive description logics that extend ALC with inverse roles, qualified number restrictions, and feature comparisons.
  arXiv  Detail & Related papers  (2026-05-08T08:59:52Z)
• Supervised Learning as Lossy Compression: Characterizing Generalization and Sample Complexity via Finite Blocklength Analysis [0.08594140167290097]
  This paper presents a novel information-theoretic perspective on generalization in machine learning.<n>We derive lower bounds on sample complexity and generalization error for a fixed randomized learning algorithm.<n>We decompose the overfitting term to show its theoretical connection to existing metrics found in information-theoretic bounds and stability theory.
  arXiv  Detail & Related papers  (2026-02-04T00:45:01Z)
• Closing the Approximation Gap of Partial AUC Optimization: A Tale of Two Formulations [121.39938773554523]
  The Area Under the ROC Curve (AUC) is a pivotal evaluation metric in real-world scenarios with both class imbalance and decision constraints.<n>We present two simple instance-wise minimax reformulations to close the approximation gap of PAUC optimization.<n>The resulting algorithms enjoy a linear per-iteration computational complexity w.r.t. the sample size and a convergence rate of $O(-2/3)$ for typical one-way and two-way PAUCs.
  arXiv  Detail & Related papers  (2025-12-01T02:52:33Z)
• Curved Boolean Logic: A Contextual Generalization of Propositional Logic with Algorithmic Consequences [0.0]
  CBL generalizes propositional logic by allowing local truth assignments that do not extend to a single global valuation.<n>We give equivalent sheaf and exclusivity-graph semantics and a context-aware proof calculus that is conservative in the flat limit.<n>We model noise with iid, AR(1)-correlated, and adversarial bounded perturbations and provide permutation-based significance with Benjamini-Hochberg FDR control.
  arXiv  Detail & Related papers  (2025-10-06T11:34:08Z)
• Nearly Optimal Sample Complexity for Learning with Label Proportions [54.67830198790247]
  We investigate Learning from Label Proportions (LLP), a partial information setting where examples in a training set are grouped into bags.<n>Despite the partial observability, the goal is still to achieve small regret at the level of individual examples.<n>We give results on the sample complexity of LLP under square loss, showing that our sample complexity is essentially optimal.
  arXiv  Detail & Related papers  (2025-05-08T15:45:23Z)
• Minimum Description Length and Generalization Guarantees for Representation Learning [16.2444595840653]
  This paper presents a framework that allows us to derive upper bounds on the generalization error of a representation learning algorithm. Rather than the mutual information between the encoder's input and the representation, our new bounds involve the "multi-letter" relative entropy. To the best knowledge of the authors, the established generalization bounds are the first of their kind for Information Bottleneck (IB) type encoders and representation learning.
  arXiv  Detail & Related papers  (2024-02-05T18:12:28Z)
• Nonparametric active learning for cost-sensitive classification [2.1756081703276]
  We design a generic nonparametric active learning algorithm for cost-sensitive classification. We prove the near-optimality of obtained upper bounds by providing matching (up to logarithmic factor) lower bounds.
  arXiv  Detail & Related papers  (2023-09-30T22:19:21Z)
• SAT-Based PAC Learning of Description Logic Concepts [18.851061569487616]
  We propose bounded fitting as a scheme for learning logic concepts in the presence of description. We present the system SPELL which implements bounded fitting for the description logic $mathcalELHr$ based on a SAT solver, and compare its performance to a state-of-the-art learner.
  arXiv  Detail & Related papers  (2023-05-15T10:20:31Z)
• Asymptotically Unbiased Instance-wise Regularized Partial AUC Optimization: Theory and Algorithm [101.44676036551537]
  One-way Partial AUC (OPAUC) and Two-way Partial AUC (TPAUC) measures the average performance of a binary classifier. Most of the existing methods could only optimize PAUC approximately, leading to inevitable biases that are not controllable. We present a simpler reformulation of the PAUC problem via distributional robust optimization AUC.
  arXiv  Detail & Related papers  (2022-10-08T08:26:22Z)
• Deep Probabilistic Graph Matching [72.6690550634166]
  We propose a deep learning-based graph matching framework that works for the original QAP without compromising on the matching constraints. The proposed method is evaluated on three popularly tested benchmarks (Pascal VOC, Willow Object and SPair-71k) and it outperforms all previous state-of-the-arts on all benchmarks.
  arXiv  Detail & Related papers  (2022-01-05T13:37:27Z)
• On Guaranteed Optimal Robust Explanations for NLP Models [16.358394218953833]
  We build on abduction-based explanations for ma-chine learning and develop a method for computing local explanations for neural network models. We present two solution algorithms, respectively based on implicit hitting sets and maximum universal subsets. We evaluate our framework on three widely used sentiment analysis tasks and texts of up to100words from SST, Twitter and IMDB datasets.
  arXiv  Detail & Related papers  (2021-05-08T08:44:48Z)
• Reducing Confusion in Active Learning for Part-Of-Speech Tagging [100.08742107682264]
  Active learning (AL) uses a data selection algorithm to select useful training samples to minimize annotation cost. We study the problem of selecting instances which maximally reduce the confusion between particular pairs of output tags. Our proposed AL strategy outperforms other AL strategies by a significant margin.
  arXiv  Detail & Related papers  (2020-11-02T06:24:58Z)
• Joint Contrastive Learning with Infinite Possibilities [114.45811348666898]
  This paper explores useful modifications of the recent development in contrastive learning via novel probabilistic modeling. We derive a particular form of contrastive loss named Joint Contrastive Learning (JCL)
  arXiv  Detail & Related papers  (2020-09-30T16:24:21Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  We investigate the problem of best-policy identification in discounted Markov Decision (MDPs) when the learner has access to a generative model. The advantages of state-of-the-art algorithms are discussed and illustrated.
  arXiv  Detail & Related papers  (2020-09-28T15:22:24Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.