Goal-Driven Query Answering over First- and Second-Order Dependencies with Equality

• URL: http://arxiv.org/abs/2412.09125v1
• Date: Thu, 12 Dec 2024 10:02:16 GMT
• Title: Goal-Driven Query Answering over First- and Second-Order Dependencies with Equality
• Authors: Efthymia Tsamoura, Boris Motik,
• Abstract summary: We present what we believe to be the first technique for goal-driven query answering over first- and second-order dependencies with equality reasoning.<n>Our technique transforms the input dependencies so that applying the chase to the output avoids many inferences that are irrelevant to the query.<n>We also present the results of an extensive empirical evaluation, which show that goal-driven query answering can be orders of magnitude faster than computing the full universal model.
• Score: 9.880191856609581
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Query answering over data with dependencies plays a central role in most applications of dependencies. The problem is commonly solved by using a suitable variant of the chase algorithm to compute a universal model of the dependencies and the data and thus explicate all knowledge implicit in the dependencies. After this preprocessing step, an arbitrary conjunctive query over the dependencies and the data can be answered by evaluating it the computed universal model. If, however, the query to be answered is fixed and known in advance, computing the universal model is often inefficient as many inferences made during this process can be irrelevant to a given query. In such cases, a goal-driven approach, which avoids drawing unnecessary inferences, promises to be more efficient and thus preferable in practice. In this paper we present what we believe to be the first technique for goal-driven query answering over first- and second-order dependencies with equality reasoning. Our technique transforms the input dependencies so that applying the chase to the output avoids many inferences that are irrelevant to the query. The transformation proceeds in several steps, which comprise the following three novel techniques. First, we present a variant of the singularisation technique by Marnette [60] that is applicable to second-order dependencies and that corrects an incompleteness of a related formulation by ten Cate et al. [74]. Second, we present a relevance analysis technique that can eliminate from the input dependencies that provably do not contribute to query answers. Third, we present a variant of the magic sets algorithm [19] that can handle second-order dependencies with equality reasoning. We also present the results of an extensive empirical evaluation, which show that goal-driven query answering can be orders of magnitude faster than computing the full universal model.

Related papers

• Attention with Dependency Parsing Augmentation for Fine-Grained Attribution [26.603281615221505]
  We develop a fine-grained attribution mechanism that provides supporting evidence from retrieved documents for every answer span. Existing attribution methods rely on model-internal similarity metrics between responses and documents, such as saliency scores and hidden state similarity. We propose two techniques applicable to all model-internals-based methods. First, we aggregate token-wise evidence through set union operations, preserving the granularity of representations. Second, we enhance the attributor by integrating dependency parsing to enrich the semantic completeness of target spans.
  arXiv  Detail & Related papers  (2024-12-16T03:12:13Z)
• Towards Fast Algorithms for the Preference Consistency Problem Based on Hierarchical Models [4.007697401483925]
  We construct and compare algorithmic approaches to solve the Consistency Problem for preference statements based on hierarchical models. An instance is consistent if there exists an hierarchical model on the evaluation functions that induces an order relation on the alternatives. We develop three approaches to solve this decision problem.
  arXiv  Detail & Related papers  (2024-10-31T13:48:46Z)
• Konstruktor: A Strong Baseline for Simple Knowledge Graph Question Answering [60.6042489577575]
  We introduce Konstruktor - an efficient and robust approach that breaks down the problem into three steps. Our approach integrates language models and knowledge graphs, exploiting the power of the former and the interpretability of the latter. We show that for relation detection, the most challenging step of the workflow, a combination of relation classification/generation and ranking outperforms other methods.
  arXiv  Detail & Related papers  (2024-09-24T09:19:11Z)
• Learning to Learn in Interactive Constraint Acquisition [7.741303298648302]
  In Constraint Acquisition (CA), the goal is to assist the user by automatically learning the model. In (inter)active CA, this is done by interactively posting queries to the user. We propose to use probabilistic classification models to guide interactive CA to generate more promising queries.
  arXiv  Detail & Related papers  (2023-12-17T19:12:33Z)
• Adversarial Imitation Learning On Aggregated Data [0.0]
  Inverse Reinforcement Learning (IRL) learns an optimal policy, given some expert demonstrations, thus avoiding the need for the tedious process of specifying a suitable reward function. We propose an approach which removes these requirements through a dynamic, adaptive method called Adversarial Imitation Learning on Aggregated Data (AILAD) It learns conjointly both a non linear reward function and the associated optimal policy using an adversarial framework.
  arXiv  Detail & Related papers  (2023-11-14T22:13:38Z)
• Answering Ambiguous Questions via Iterative Prompting [84.3426020642704]
  In open-domain question answering, due to the ambiguity of questions, multiple plausible answers may exist. One approach is to directly predict all valid answers, but this can struggle with balancing relevance and diversity. We present AmbigPrompt to address the imperfections of existing approaches to answering ambiguous questions.
  arXiv  Detail & Related papers  (2023-07-08T04:32:17Z)
• Successive Prompting for Decomposing Complex Questions [50.00659445976735]
  Recent works leverage the capabilities of large language models (LMs) to perform complex question answering in a few-shot setting. We introduce Successive Prompting'', where we iteratively break down a complex task into a simple task, solve it, and then repeat the process until we get the final solution. Our best model (with successive prompting) achieves an improvement of 5% absolute F1 on a few-shot version of the DROP dataset.
  arXiv  Detail & Related papers  (2022-12-08T06:03:38Z)
• Partial Order in Chaos: Consensus on Feature Attributions in the Rashomon Set [50.67431815647126]
  Post-hoc global/local feature attribution methods are being progressively employed to understand machine learning models. We show that partial orders of local/global feature importance arise from this methodology. We show that every relation among features present in these partial orders also holds in the rankings provided by existing approaches.
  arXiv  Detail & Related papers  (2021-10-26T02:53:14Z)
• Adaptive Information Seeking for Open-Domain Question Answering [61.39330982757494]
  We propose a novel adaptive information-seeking strategy for open-domain question answering, namely AISO. According to the learned policy, AISO could adaptively select a proper retrieval action to seek the missing evidence at each step. AISO outperforms all baseline methods with predefined strategies in terms of both retrieval and answer evaluations.
  arXiv  Detail & Related papers  (2021-09-14T15:08:13Z)
• Logically Consistent Loss for Visual Question Answering [66.83963844316561]
  The current advancement in neural-network based Visual Question Answering (VQA) cannot ensure such consistency due to identically distribution (i.i.d.) assumption. We propose a new model-agnostic logic constraint to tackle this issue by formulating a logically consistent loss in the multi-task learning framework. Experiments confirm that the proposed loss formulae and introduction of hybrid-batch leads to more consistency as well as better performance.
  arXiv  Detail & Related papers  (2020-11-19T20:31:05Z)
• An Advance on Variable Elimination with Applications to Tensor-Based Computation [11.358487655918676]
  We present new results on the classical algorithm of variable elimination, which underlies many algorithms including for probabilistic inference. The results relate to exploiting functional dependencies, allowing one to perform inference and learning efficiently on models that have very large treewidth.
  arXiv  Detail & Related papers  (2020-02-21T14:17:44Z)
• Polynomial-Time Exact MAP Inference on Discrete Models with Global Dependencies [83.05591911173332]
  junction tree algorithm is the most general solution for exact MAP inference with run-time guarantees. We propose a new graph transformation technique via node cloning which ensures a run-time for solving our target problem independently of the form of a corresponding clique tree.
  arXiv  Detail & Related papers  (2019-12-27T13:30:29Z)

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.