論文の概要: Learnability with PAC Semantics for Multi-agent Beliefs

• arxiv url: http://arxiv.org/abs/2306.05490v1
• Date: Thu, 8 Jun 2023 18:22:46 GMT
• ステータス: 処理完了
• システム内更新日: 2023-06-12 15:56:50.836329
• Title: Learnability with PAC Semantics for Multi-agent Beliefs
• Title（参考訳）: マルチエージェントにおけるPACセマンティクスの学習可能性
• Authors: Ionela G. Mocanu, Vaishak Belle and Brendan Juba
• Abstract要約: 推論と帰納の緊張は、おそらく哲学、認知、人工知能といった分野において最も根本的な問題である。 Valiant氏は、学習の課題は推論と統合されるべきである、と認識した。 古典的な包含よりも弱いが、クエリに応答する強力なモデル理論のフレームワークを可能にする。
• 参考スコア（独自算出の注目度）: 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.
• Abstract（参考訳）: 推論と帰納の緊張は、おそらく哲学、認知、人工知能といった分野において最も根本的な問題である。 影響力のある論文で、ヴァリアントは学習の課題は推論と統合されるべきだと認識した。 特に、論理式で定式化された場合、確率近似学習アルゴリズム(PAC)の出力が持つ品質を捉える意味論を提案した。 古典的な包含よりも弱いが、クエリに応答する強力なモデル理論のフレームワークを可能にする。 本稿では,マルチエージェント・エピステミック論理を用いたPAC学習の実証のための新しい技術基盤を提供する。 pacセマンティクスを用いたロバストな学習の難しさに関する文献の否定的な結果を回避するため,認識論的問合せの含意を決定する目的で背景理論に観察を組み込むことができるいわゆる暗黙的学習を考える。 学習手順の正しさを証明し,サンプル複雑性に関する結果について議論する。つまり,ユーザ指定のエラーバウンドを前提として,クエリが含んでいることを確実に主張する必要がある。 最後に,このアルゴリズムの効率性について検討する。 最後に、特にマルチエージェント・エピステミック論理における認識論理の推論がPSPACE完全であることを考えると、この問題には期待できないようである。 本稿では, 単エージェントおよび複数エージェントの認識論理に対して探索したRepresentation Theoremの最近の結果を利用する。

関連論文リスト

• The Computational Complexity of Circuit Discovery for Inner Interpretability [0.30723404270319693]
  我々は古典的およびパラメータ化された計算複雑性理論を用いて回路発見を研究する。 私たちの発見は、難しい複雑さの風景を明らかにします。 このフレームワークは、解釈可能性クエリの範囲と限界を理解するのに役立ちます。
  論文  参考訳（メタデータ） (2024-10-10T15:22:48Z)
• Counterfactual and Semifactual Explanations in Abstract Argumentation: Formal Foundations, Complexity and Computation [19.799266797193344]
  議論ベースのシステムは、意思決定プロセスをサポートしながら説明責任を欠くことが多い。 対実的・半実的な説明は解釈可能性のテクニックである。 本稿では,制約の弱いArgumentation Frameworkにおいて,逆ファクトおよび半ファクトのクエリを符号化可能であることを示す。
  論文  参考訳（メタデータ） (2024-05-07T07:27:27Z)
• Soft Reasoning on Uncertain Knowledge Graphs [85.1968214421899]
  本研究では,ソフト制約プログラミングの確立を動機とした,不確実な知識に対するソフトクエリの設定について検討する。 本稿では,大規模,不完全,不確実な知識グラフ上でのソフトクエリに応答する,前方推論と後方校正を併用したMLベースのアプローチを提案する。
  論文  参考訳（メタデータ） (2024-03-03T13:13:53Z)
• A Semantic Approach to Decidability in Epistemic Planning (Extended Version) [72.77805489645604]
  我々は決定可能性を達成するために新しい意味論的アプローチを用いる。 具体的には、知識の論理S5$_n$と(知識)可換性と呼ばれる相互作用公理を拡大する。 我々は,本フレームワークが,独立した知識である共通知識の有限的非固定点的特徴を認めていることを証明した。
  論文  参考訳（メタデータ） (2023-07-28T11:26:26Z)
• Modeling Hierarchical Reasoning Chains by Linking Discourse Units and Key Phrases for Reading Comprehension [80.99865844249106]
  本稿では,論理的推論の基盤として,対話レベルと単語レベルの両方の文脈を扱う総合グラフネットワーク(HGN)を提案する。 具体的には、ノードレベルの関係とタイプレベルの関係は、推論過程におけるブリッジと解釈できるが、階層的な相互作用機構によってモデル化される。
  論文  参考訳（メタデータ） (2023-06-21T07:34:27Z)
• A Parameterized Theory of PAC Learning [19.686465068713467]
  おそらく略正(PAC)学習は、サンプル複雑性理論の中核的な概念である。 我々は、パラメータ化複雑性の要素を組み込んだ最近のPAC学習結果に新たな光を当てることができるパラメータ化PAC学習の理論を開発した。
  論文  参考訳（メタデータ） (2023-04-27T09:39:30Z)
• Rethinking Complex Queries on Knowledge Graphs with Neural Link Predictors [58.340159346749964]
  本稿では,証明可能な推論能力を備えた複雑なクエリを用いたエンドツーエンド学習を支援するニューラルシンボリック手法を提案する。 これまでに検討されていない10種類の新しいクエリを含む新しいデータセットを開発する。 提案手法は,新しいデータセットにおいて先行手法を著しく上回り,既存データセットにおける先行手法を同時に上回っている。
  論文  参考訳（メタデータ） (2023-04-14T11:35:35Z)
• An Embedding-based Approach to Inconsistency-tolerant Reasoning with Inconsistent Ontologies [12.760301272393898]
  本稿では,公理の埋め込みに基づく一貫性のない意味論による推論手法を提案する。 組込みに基づく手法は、最大一貫した部分集合に基づく既存の矛盾耐性推論手法よりも優れていることを示す。
  論文  参考訳（メタデータ） (2023-04-04T09:38:02Z)
• Dual Box Embeddings for the Description Logic EL++ [16.70961576041243]
  知識グラフ(KG)と同様に、知識グラフはしばしば不完全であり、それらの維持と構築は困難であることが証明された。 KGsと同様に、有望なアプローチは、潜在ベクトル空間への埋め込みを学習し、基礎となるDLのセマンティクスに固執することである。 そこで本研究では,概念と役割をボックスとして表現した,DL EL++用のBox$2$ELという新しいオントロジー埋め込み手法を提案する。
  論文  参考訳（メタデータ） (2023-01-26T14:13:37Z)
• Towards Understanding Chain-of-Thought Prompting: An Empirical Study of What Matters [82.84696222087396]
  CoT(Chain-of-Thought)の促進により,大規模言語モデル(LLM)の多段階推論能力が劇的に向上する 無効な実演でもCoT推論が可能であることを示す。
  論文  参考訳（メタデータ） (2022-12-20T05:20:54Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。