Learnability with PAC Semantics for Multi-agent Beliefs

• URL: http://arxiv.org/abs/2306.05490v1
• Date: Thu, 8 Jun 2023 18:22:46 GMT
• Title: Learnability with PAC Semantics for Multi-agent Beliefs
• Authors: Ionela G. Mocanu, Vaishak Belle and Brendan Juba
• Abstract summary: The tension between deduction and induction is perhaps the most fundamental issue in areas such as philosophy, cognition and artificial intelligence. Valiant recognised that the challenge of learning should be integrated with deduction. Although weaker than classical entailment, it allows for a powerful model-theoretic framework for answering queries.
• Score: 38.88111785113001
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The tension between deduction and induction is perhaps the most fundamental issue in areas such as philosophy, cognition and artificial intelligence. In an influential paper, Valiant recognised that the challenge of learning should be integrated with deduction. In particular, he proposed a semantics to capture the quality possessed by the output of Probably Approximately Correct (PAC) learning algorithms when formulated in a logic. Although weaker than classical entailment, it allows for a powerful model-theoretic framework for answering queries. In this paper, we provide a new technical foundation to demonstrate PAC learning with multi-agent epistemic logics. To circumvent the negative results in the literature on the difficulty of robust learning with the PAC semantics, we consider so-called implicit learning where we are able to incorporate observations to the background theory in service of deciding the entailment of an epistemic query. We prove correctness of the learning procedure and discuss results on the sample complexity, that is how many observations we will need to provably assert that the query is entailed given a user-specified error bound. Finally, we investigate under what circumstances this algorithm can be made efficient. On the last point, given that reasoning in epistemic logics especially in multi-agent epistemic logics is PSPACE-complete, it might seem like there is no hope for this problem. We leverage some recent results on the so-called Representation Theorem explored for single-agent and multi-agent epistemic logics with the only knowing operator to reduce modal reasoning to propositional reasoning.

Related papers

• The Computational Complexity of Circuit Discovery for Inner Interpretability [0.30723404270319693]
  We study circuit discovery with classical and parameterized computational complexity theory. Our findings reveal a challenging complexity landscape. This framework allows us to understand the scope and limits of interpretability queries.
  arXiv  Detail & Related papers  (2024-10-10T15:22:48Z)
• Counterfactual and Semifactual Explanations in Abstract Argumentation: Formal Foundations, Complexity and Computation [19.799266797193344]
  Argumentation-based systems often lack explainability while supporting decision-making processes. Counterfactual and semifactual explanations are interpretability techniques. We show that counterfactual and semifactual queries can be encoded in weak-constrained Argumentation Framework.
  arXiv  Detail & Related papers  (2024-05-07T07:27:27Z)
• Soft Reasoning on Uncertain Knowledge Graphs [85.1968214421899]
  We study the setting of soft queries on uncertain knowledge, which is motivated by the establishment of soft constraint programming. We propose an ML-based approach with both forward inference and backward calibration to answer soft queries on large-scale, incomplete, and uncertain knowledge graphs.
  arXiv  Detail & Related papers  (2024-03-03T13:13:53Z)
• A Semantic Approach to Decidability in Epistemic Planning (Extended Version) [72.77805489645604]
  We use a novel semantic approach to achieve decidability. Specifically, we augment the logic of knowledge S5$_n$ and with an interaction axiom called (knowledge) commutativity. We prove that our framework admits a finitary non-fixpoint characterization of common knowledge, which is of independent interest.
  arXiv  Detail & Related papers  (2023-07-28T11:26:26Z)
• Modeling Hierarchical Reasoning Chains by Linking Discourse Units and Key Phrases for Reading Comprehension [80.99865844249106]
  We propose a holistic graph network (HGN) which deals with context at both discourse level and word level, as the basis for logical reasoning. Specifically, node-level and type-level relations, which can be interpreted as bridges in the reasoning process, are modeled by a hierarchical interaction mechanism.
  arXiv  Detail & Related papers  (2023-06-21T07:34:27Z)
• A Parameterized Theory of PAC Learning [19.686465068713467]
  Probably Approximately Correct (i.e., PAC) learning is a core concept of sample complexity theory. We develop a theory of parameterized PAC learning which allows us to shed new light on several recent PAC learning results that incorporated elements of parameterized complexity.
  arXiv  Detail & Related papers  (2023-04-27T09:39:30Z)
• Rethinking Complex Queries on Knowledge Graphs with Neural Link Predictors [58.340159346749964]
  We propose a new neural-symbolic method to support end-to-end learning using complex queries with provable reasoning capability. We develop a new dataset containing ten new types of queries with features that have never been considered. Our method outperforms previous methods significantly in the new dataset and also surpasses previous methods in the existing dataset at the same time.
  arXiv  Detail & Related papers  (2023-04-14T11:35:35Z)
• An Embedding-based Approach to Inconsistency-tolerant Reasoning with Inconsistent Ontologies [12.760301272393898]
  We propose a novel approach to reasoning with inconsistent semantics based on the embeddings of axioms. We show that our embedding-based method can outperform existing inconsistency-tolerant reasoning methods based on maximal consistent subsets.
  arXiv  Detail & Related papers  (2023-04-04T09:38:02Z)
• Dual Box Embeddings for the Description Logic EL++ [16.70961576041243]
  Similar to Knowledge Graphs (KGs), Knowledge Graphs are often incomplete, and maintaining and constructing them has proved challenging. Similar to KGs, a promising approach is to learn embeddings in a latent vector space, while additionally ensuring they adhere to the semantics of the underlying DL. We propose a novel ontology embedding method named Box$2$EL for the DL EL++, which represents both concepts and roles as boxes.
  arXiv  Detail & Related papers  (2023-01-26T14:13:37Z)
• Towards Understanding Chain-of-Thought Prompting: An Empirical Study of What Matters [82.84696222087396]
  Chain-of-Thought (CoT) prompting can dramatically improve the multi-step reasoning abilities of large language models (LLMs) We show that CoT reasoning is possible even with invalid demonstrations.
  arXiv  Detail & Related papers  (2022-12-20T05:20:54Z)

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.