SAT-Based PAC Learning of Description Logic Concepts
- URL: http://arxiv.org/abs/2305.08511v1
- Date: Mon, 15 May 2023 10:20:31 GMT
- Title: SAT-Based PAC Learning of Description Logic Concepts
- Authors: Balder ten Cate, Maurice Funk, Jean Christoph Jung, Carsten Lutz
- Abstract summary: 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.
- Score: 18.851061569487616
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We propose bounded fitting as a scheme for learning description logic
concepts in the presence of ontologies. A main advantage is that the resulting
learning algorithms come with theoretical guarantees regarding their
generalization to unseen examples in the sense of PAC learning. We prove that,
in contrast, several other natural learning algorithms fail to provide such
guarantees. As a further contribution, we present the system SPELL which
efficiently implements bounded fitting for the description logic
$\mathcal{ELH}^r$ based on a SAT solver, and compare its performance to a
state-of-the-art learner.
Related papers
- Learning-to-Optimize with PAC-Bayesian Guarantees: Theoretical Considerations and Practical Implementation [4.239829789304117]
We use the PAC-Bayesian theory for the setting of learning-to-optimize.
We present the first framework to learn optimization algorithms with provable generalization guarantees.
Our learned algorithms provably outperform related ones derived from a (deterministic) worst-case analysis.
arXiv Detail & Related papers (2024-04-04T08:24:57Z) - Multitask Kernel-based Learning with Logic Constraints [13.70920563542248]
This paper presents a framework to integrate prior knowledge in the form of logic constraints among a set of task functions into kernel machines.
We consider a multi-task learning scheme, where multiple unary predicates on the feature space are to be learned by kernel machines.
A general approach is presented to convert the logic clauses into a continuous implementation, that processes the outputs computed by the kernel-based predicates.
arXiv Detail & Related papers (2024-02-16T12:11:34Z) - Provable Representation with Efficient Planning for Partial Observable Reinforcement Learning [74.67655210734338]
In most real-world reinforcement learning applications, state information is only partially observable, which breaks the Markov decision process assumption.
We develop a representation-based perspective that leads to a coherent framework and tractable algorithmic approach for practical reinforcement learning from partial observations.
We empirically demonstrate the proposed algorithm can surpass state-of-the-art performance with partial observations across various benchmarks.
arXiv Detail & Related papers (2023-11-20T23:56:58Z) - A Theory of Unsupervised Speech Recognition [60.12287608968879]
Unsupervised speech recognition (ASR-U) is the problem of learning automatic speech recognition systems from unpaired speech-only and text-only corpora.
We propose a general theoretical framework to study the properties of ASR-U systems based on random matrix theory and the theory of neural tangent kernels.
arXiv Detail & Related papers (2023-06-09T08:12:27Z) - Multivariate Systemic Risk Measures and Computation by Deep Learning
Algorithms [63.03966552670014]
We discuss the key related theoretical aspects, with a particular focus on the fairness properties of primal optima and associated risk allocations.
The algorithms we provide allow for learning primals, optima for the dual representation and corresponding fair risk allocations.
arXiv Detail & Related papers (2023-02-02T22:16:49Z) - PAC-Bayesian Learning of Optimization Algorithms [6.624726878647541]
We apply the PAC-Bayes theory to the setting of learning-to-optimize.
We learn optimization algorithms with provable generalization guarantees (PAC-bounds) and explicit trade-off between a high probability of convergence and a high convergence speed.
Our results rely on PAC-Bayes bounds for general, unbounded loss-functions based on exponential families.
arXiv Detail & Related papers (2022-10-20T09:16:36Z) - Stabilizing Q-learning with Linear Architectures for Provably Efficient
Learning [53.17258888552998]
This work proposes an exploration variant of the basic $Q$-learning protocol with linear function approximation.
We show that the performance of the algorithm degrades very gracefully under a novel and more permissive notion of approximation error.
arXiv Detail & Related papers (2022-06-01T23:26:51Z) - Efficient Performance Bounds for Primal-Dual Reinforcement Learning from
Demonstrations [1.0609815608017066]
We consider large-scale Markov decision processes with an unknown cost function and address the problem of learning a policy from a finite set of expert demonstrations.
Existing inverse reinforcement learning methods come with strong theoretical guarantees, but are computationally expensive.
We introduce a novel bilinear saddle-point framework using Lagrangian duality to bridge the gap between theory and practice.
arXiv Detail & Related papers (2021-12-28T05:47:24Z) - Online Learning Probabilistic Event Calculus Theories in Answer Set
Programming [70.06301658267125]
Event Recognition (CER) systems detect occurrences in streaming time-stamped datasets using predefined event patterns.
We present a system based on Answer Set Programming (ASP), capable of probabilistic reasoning with complex event patterns in the form of rules weighted in the Event Calculus.
Our results demonstrate the superiority of our novel approach, both terms efficiency and predictive.
arXiv Detail & Related papers (2021-03-31T23:16:29Z) - Learning explanations that are hard to vary [75.30552491694066]
We show that averaging across examples can favor memorization and patchwork' solutions that sew together different strategies.
We then propose and experimentally validate a simple alternative algorithm based on a logical AND.
arXiv Detail & Related papers (2020-09-01T10:17:48Z)
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.