Computing CQ lower-bounds over OWL 2 through approximation to RSA

• URL: http://arxiv.org/abs/2107.00369v1
• Date: Thu, 1 Jul 2021 11:13:00 GMT
• Title: Computing CQ lower-bounds over OWL 2 through approximation to RSA
• Authors: Federico Igne, Stefano Germano, Ian Horrocks
• Abstract summary: We present a novel algorithm to compute a closer (than PAGOd OWL) lower bound approximation using the RSA combined approach. We present a preliminary evaluation of our system that shows significant performance improvements.
• Score: 12.737436528656131
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Conjunctive query (CQ) answering over knowledge bases is an important reasoning task. However, with expressive ontology languages such as OWL, query answering is computationally very expensive. The PAGOdA system addresses this issue by using a tractable reasoner to compute lower and upper-bound approximations, falling back to a fully-fledged OWL reasoner only when these bounds don't coincide. The effectiveness of this approach critically depends on the quality of the approximations, and in this paper we explore a technique for computing closer approximations via RSA, an ontology language that subsumes all the OWL 2 profiles while still maintaining tractability. We present a novel approximation of OWL 2 ontologies into RSA, and an algorithm to compute a closer (than PAGOdA) lower bound approximation using the RSA combined approach. We have implemented these algorithms in a prototypical CQ answering system, and we present a preliminary evaluation of our system that shows significant performance improvements w.r.t. PAGOdA.

Related papers

• Fast MLE and MAPE-Based Device Activity Detection for Grant-Free Access via PSCA and PSCA-Net [13.076905065264091]
  Fast and accurate device activity is the critical challenge in grant-free access for supporting massive machine-type communications. We propose new maximum likelihood estimation (MLE) based device activity detection methods. We present a deep unrolling neural network implementation called PSCA-Net to further reduce the computation time.
  arXiv  Detail & Related papers  (2025-03-19T14:31:09Z)
• Do NOT Think That Much for 2+3=? On the Overthinking of o1-Like LLMs [76.43407125275202]
  o1-like models can emulate human-like long-time thinking during inference. This paper presents the first comprehensive study on the prevalent issue of overthinking in these models. We propose strategies to mitigate overthinking, streamlining reasoning processes without compromising accuracy.
  arXiv  Detail & Related papers  (2024-12-30T18:55:12Z)
• Simple and Provable Scaling Laws for the Test-Time Compute of Large Language Models [70.07661254213181]
  We propose two principled algorithms for the test-time compute of large language models. We prove theoretically that the failure probability of one algorithm decays to zero exponentially as its test-time compute grows.
  arXiv  Detail & Related papers  (2024-11-29T05:29:47Z)
• On additive error approximations to #BQP [0.34089646689382486]
  We study additive approximations to a quantum generalization of counting classes known as #BQP. First, we show that there exist efficient quantum algorithms that achieve additive approximations to #BQP problems to an error exponential in the number of witness qubits in the corresponding verifier circuit.
  arXiv  Detail & Related papers  (2024-11-04T20:51:20Z)
• Tractable Offline Learning of Regular Decision Processes [50.11277112628193]
  This work studies offline Reinforcement Learning (RL) in a class of non-Markovian environments called Regular Decision Processes (RDPs) Ins, the unknown dependency of future observations and rewards from the past interactions can be captured experimentally. Many algorithms first reconstruct this unknown dependency using automata learning techniques.
  arXiv  Detail & Related papers  (2024-09-04T14:26:58Z)
• When can you trust feature selection? -- I: A condition-based analysis of LASSO and generalised hardness of approximation [49.1574468325115]
  We show how no (randomised) algorithm can determine the correct support sets (with probability $> 1/2$) of minimisers of LASSO when reading approximate input. For ill-posed inputs, the algorithm runs forever, hence, it will never produce a wrong answer. For any algorithm defined on an open set containing a point with infinite condition number, there is an input for which the algorithm will either run forever or produce a wrong answer.
  arXiv  Detail & Related papers  (2023-12-18T18:29:01Z)
• Recursive Causal Structure Learning in the Presence of Latent Variables and Selection Bias [27.06618125828978]
  We consider the problem of learning the causal MAG of a system from observational data in the presence of latent variables and selection bias. We propose a novel computationally efficient constraint-based method that is sound and complete. We provide experimental results to compare the proposed approach with the state of the art on both synthetic and real-world structures.
  arXiv  Detail & Related papers  (2021-10-22T19:49:59Z)
• How to Approximate Ontology-Mediated Queries [22.99749220980996]
  We introduce and study several notions of approximation for ontology-mediated queries based on the description logics ALC and ALCI. Our approximations are of two kinds: we may (1) replace the ontology with one formulated in a tractable language such as ELI or certain TGDs and (2) replace the database with one from a tractable class such as the class of databases whose treewidth is bounded by a constant.
  arXiv  Detail & Related papers  (2021-07-12T12:29:50Z)
• Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
  We consider the task of minimizing the sum of smooth and strongly convex functions stored in a decentralized manner across the nodes of a communication network. We design two optimal algorithms that attain these lower bounds. We corroborate the theoretical efficiency of these algorithms by performing an experimental comparison with existing state-of-the-art methods.
  arXiv  Detail & Related papers  (2021-06-08T15:54:44Z)
• 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)
• Berrut Approximated Coded Computing: Straggler Resistance Beyond Polynomial Computing [34.69732430310801]
  We propose Berrut Approximated Coded Computing (BACC) as an alternative approach to deal with stragglers effect. BACC is proven to be numerically stable with low computational complexity. In particular, BACC is used to train a deep neural network on a cluster of servers.
  arXiv  Detail & Related papers  (2020-09-17T14:23:38Z)
• Approximation Algorithms for Sparse Principal Component Analysis [57.5357874512594]
  Principal component analysis (PCA) is a widely used dimension reduction technique in machine learning and statistics. Various approaches to obtain sparse principal direction loadings have been proposed, which are termed Sparse Principal Component Analysis. We present thresholding as a provably accurate, time, approximation algorithm for the SPCA problem.
  arXiv  Detail & Related papers  (2020-06-23T04:25:36Z)
• Refined bounds for algorithm configuration: The knife-edge of dual class approximability [94.83809668933021]
  We investigate how large should a training set be to ensure that a parameter's average metrics performance over the training set is close to its expected, future performance. We show that if this approximation holds under the L-infinity norm, we can provide strong sample complexity bounds. We empirically evaluate our bounds in the context of integer programming, one of the most powerful tools in computer science.
  arXiv  Detail & Related papers  (2020-06-21T15:32:21Z)

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.