Spectra of Cardinality Queries over Description Logic Knowledge Bases

• URL: http://arxiv.org/abs/2412.12929v1
• Date: Tue, 17 Dec 2024 14:07:04 GMT
• Title: Spectra of Cardinality Queries over Description Logic Knowledge Bases
• Authors: Quentin Manière, Marcin Przybyłko,
• Abstract summary: We identify a class of counting queries whose spectra can be effectively represented. We refine constructions used for finite model reasoning and rely on a cycle-reversion technique for the Horn fragment.
• Score: 1.9336815376402723
• License:
• Abstract: Recent works have explored the use of counting queries coupled with Description Logic ontologies. The answer to such a query in a model of a knowledge base is either an integer or $\infty$, and its spectrum is the set of its answers over all models. While it is unclear how to compute and manipulate such a set in general, we identify a class of counting queries whose spectra can be effectively represented. Focusing on atomic counting queries, we pinpoint the possible shapes of a spectrum over $\mathcal{ALCIF}$ ontologies: they are essentially the subsets of $\mathbb{N} \cup \{ \infty \}$ closed under addition. For most sublogics of $\mathcal{ALCIF}$, we show that possible spectra enjoy simpler shapes, being $[ m, \infty ]$ or variations thereof. To obtain our results, we refine constructions used for finite model reasoning and notably rely on a cycle-reversion technique for the Horn fragment of $\mathcal{ALCIF}$. We also study the data complexity of computing the proposed effective representation and establish the $\mathsf{FP}^{\mathsf{NP}[\log]}$-completeness of this task under several settings.

Related papers

• Robust Learning of Multi-index Models via Iterative Subspace Approximation [36.138661719725626]
  We study the task of learning Multi-Index Models (MIMs) with label noise under the Gaussian distribution. We focus on well-behaved MIMs with finite ranges that satisfy certain regularity properties. We show that in the presence of random classification noise, the complexity of our algorithm scales agnosticly with $1/epsilon$.
  arXiv  Detail & Related papers  (2025-02-13T17:37:42Z)
• Optimal level set estimation for non-parametric tournament and crowdsourcing problems [49.75262185577198]
  Motivated by crowdsourcing, we consider a problem where we partially observe the correctness of the answers of $n$ experts on $d$ questions. In this paper, we assume that the matrix $M$ containing the probability that expert $i$ answers correctly to question $j$ is bi-isotonic up to a permutation of it rows and columns. We construct an efficient-time algorithm that turns out to be minimax optimal for this classification problem.
  arXiv  Detail & Related papers  (2024-08-27T18:28:31Z)
• CSPs with Few Alien Constraints [12.330326247154968]
  We consider CSP$(mathcalA cup mathcalB)$ where $mathcalA$ is a structure and $mathcalB$ is an alien structure. We establish connections and obtain transferable complexity results to several well-studied problems that previously escaped classification attempts.
  arXiv  Detail & Related papers  (2024-08-23T08:34:13Z)
• An in-depth study of the power function $x^{q+2}$ over the finite field $\mathbb{F}_{q^2}$: the differential, boomerang, and Walsh spectra, with an application to coding theory [28.489574654566677]
  We examine the finite field $mathbbF_q2$, which consists of $q2$ elements. We first present an alternative method to determine the differential spectrum of the power function $f(x) = xq+2$ on $mathbbF_q2$, incorporating several key simplifications.
  arXiv  Detail & Related papers  (2024-07-08T14:01:06Z)
• A Theory of Interpretable Approximations [61.90216959710842]
  We study the idea of approximating a target concept $c$ by a small aggregation of concepts from some base class $mathcalH$. For any given pair of $mathcalH$ and $c$, exactly one of these cases holds: (i) $c$ cannot be approximated by $mathcalH$ with arbitrary accuracy. We show that, in the case of interpretable approximations, even a slightly nontrivial a-priori guarantee on the complexity of approximations implies approximations with constant (distribution-free and accuracy-
  arXiv  Detail & Related papers  (2024-06-15T06:43:45Z)
• Agnostically Learning Multi-index Models with Queries [54.290489524576756]
  We study the power of query access for the task of agnostic learning under the Gaussian distribution. We show that query access gives significant runtime improvements over random examples for agnostically learning MIMs.
  arXiv  Detail & Related papers  (2023-12-27T15:50:47Z)
• Gapped Clique Homology on weighted graphs is $\text{QMA}_1$-hard and contained in $\text{QMA}$ [0.0]
  We study the complexity of a classic problem in computational topology, the homology problem. We find that the complexity is characterized by quantum complexity classes. Our results can be seen as an aspect of a connection between homology and supersymmetric quantum mechanics.
  arXiv  Detail & Related papers  (2023-11-28T21:15:30Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  We study the problem of PAC learning a linear combination of $k$ ReLU activations under the standard Gaussian distribution on $mathbbRd$ with respect to the square loss. Our main result is an efficient algorithm for this learning task with sample and computational complexity $(dk/epsilon)O(k)$, whereepsilon>0$ is the target accuracy.
  arXiv  Detail & Related papers  (2023-07-24T14:37:22Z)
• Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585]
  We study a function of the form $mathbfxmapstosigma(mathbfwcdotmathbfx)$ for monotone activations. The goal of the learner is to output a hypothesis vector $mathbfw$ that $F(mathbbw)=C, epsilon$ with high probability.
  arXiv  Detail & Related papers  (2022-06-17T17:55:43Z)
• Learning Finite Linear Temporal Logic Specifications with a Specialized Neural Operator [0.0]
  We address the problem of learning a compact $mathsfLTL_f$ formula from labeled traces of system behavior. Our approach includes a specialized recurrent filter, designed to subsume $mathsfLTL_f$ temporal operators. Experiments on randomly generated $mathsfLTL_f$ formulas show Neural$mathsfLTL_f$ scales to larger formula sizes than existing approaches.
  arXiv  Detail & Related papers  (2021-11-07T18:51:02Z)
• Average-case Complexity of Teaching Convex Polytopes via Halfspace Queries [55.28642461328172]
  We show that the average-case teaching complexity is $Theta(d)$, which is in sharp contrast to the worst-case teaching complexity of $Theta(n)$. Our insights allow us to establish a tight bound on the average-case complexity for $phi$-separable dichotomies.
  arXiv  Detail & Related papers  (2020-06-25T19:59: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.