論文の概要: Finding Good Proofs for Description Logic Entailments Using Recursive
Quality Measures (Extended Technical Report)
- arxiv url: http://arxiv.org/abs/2104.13138v1
- Date: Tue, 27 Apr 2021 12:34:13 GMT
- ステータス: 処理完了
- システム内更新日: 2021-04-28 13:23:16.966502
- Title: Finding Good Proofs for Description Logic Entailments Using Recursive
Quality Measures (Extended Technical Report)
- Title(参考訳): 再帰的品質対策による記述論理的内容の良質な証明(拡張技術報告)
- Authors: Christian Alrabbaa and Franz Baader and Stefan Borgwardt and Patrick
Koopmann and Alisa Kovtunova
- Abstract要約: 証明がいかに理解可能であるかは、使用する計算量だけでなく、特定の証明の性質にも依存する。
我々は、計算と測度の幅広いクラスを対象とする一般的な結果を目指す。
- 参考スコア(独自算出の注目度): 15.150938933215906
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Logic-based approaches to AI have the advantage that their behavior can in
principle be explained to a user. If, for instance, a Description Logic
reasoner derives a consequence that triggers some action of the overall system,
then one can explain such an entailment by presenting a proof of the
consequence in an appropriate calculus. How comprehensible such a proof is
depends not only on the employed calculus, but also on the properties of the
particular proof, such as its overall size, its depth, the complexity of the
employed sentences and proof steps, etc. For this reason, we want to determine
the complexity of generating proofs that are below a certain threshold w.r.t. a
given measure of proof quality. Rather than investigating this problem for a
fixed proof calculus and a fixed measure, we aim for general results that hold
for wide classes of calculi and measures. In previous work, we first restricted
the attention to a setting where proof size is used to measure the quality of a
proof. We then extended the approach to a more general setting, but important
measures such as proof depth were not covered. In the present paper, we provide
results for a class of measures called recursive, which yields lower
complexities and also encompasses proof depth. In addition, we close some gaps
left open in our previous work, thus providing a comprehensive picture of the
complexity landscape.
- Abstract(参考訳): 論理ベースのAIアプローチは、その振る舞いを原則としてユーザに説明できるという利点がある。
例えば、記述論理の推論器がシステム全体の何らかの作用を誘発する帰結を導出するならば、その帰結の証明を適切な計算で示すことで、そのような包含を説明することができる。
そのような証明がいかに理解可能であるかは、使用済みの計算量だけでなく、その全体の大きさ、深さ、使用済みの文の複雑さ、証明ステップなど、特定の証明の性質にも依存する。
このため、あるしきい値 w.r.t 未満の証明を生成する複雑さを判定したい。
与えられた証明品質の尺度。
固定証明計算や固定測度についてこの問題を研究するのではなく、計算量や測度の広いクラスを対象とする一般的な結果を求める。
先行研究では,まず,証明サイズを用いて証明の質を計測する設定に注意を限定した。
その後、より一般的な設定にアプローチを拡張したが、証明深さのような重要な尺度はカバーされなかった。
本稿では, 再帰的(recursive) と呼ばれる, より低い複雑性を生じ, 証明深度も含む尺度のクラスに対して, 結果を提供する。
さらに、前回の作業で開いたいくつかのギャップをクローズし、複雑さの状況の全体像を提供します。
関連論文リスト
- Next-Token Prediction Task Assumes Optimal Data Ordering for LLM Training in Proof Generation [27.60611509339328]
1つのトレーニングデータサンプルの最適順序は、特定の証明ステップの関連中間監督が、その証明ステップの左側に常に配置されているときに発生すると論じる。
証明が直感的に逐次順序にある場合、トレーニングが最も効果的であることを示す。
論文 参考訳(メタデータ) (2024-10-30T18:00:04Z) - MathGAP: Out-of-Distribution Evaluation on Problems with Arbitrarily Complex Proofs [80.96119560172224]
MathGAPは、それらの算術的証明構造に関する仕様に従って、問題文と連鎖推論トレースを生成する。
MathGAP を用いて, LLM はより深く, より広くなるにつれて, 性能が著しく低下することがわかった。
論文 参考訳(メタデータ) (2024-10-17T12:48:14Z) - Proving Theorems Recursively [80.42431358105482]
本稿では、定理をレベル・バイ・レベルで証明するPOETRYを提案する。
従来のステップバイステップメソッドとは異なり、POETRYは各レベルで証明のスケッチを検索する。
また,POETRYが検出した最大証明長は10~26。
論文 参考訳(メタデータ) (2024-05-23T10:35:08Z) - Efficient and Universal Merkle Tree Inclusion Proofs via OR Aggregation [27.541105686358378]
本稿では,メルクル木包摂証明のためのOR論理に基づく新しい証明集約手法を提案する。
木内の葉の数に依存しない証明サイズを実現し、有効な葉のハッシュ1つを用いて検証を行う。
提案手法は,ゼロ知識証明システムのスケーラビリティ,効率,柔軟性を著しく向上させる可能性がある。
論文 参考訳(メタデータ) (2024-05-13T17:15:38Z) - Testing the General Deductive Reasoning Capacity of Large Language
Models Using OOD Examples [36.63316546586304]
大型言語モデル(LLM)は、チェーン・オブ・シークレットのプロンプトを与えられた抽象的推論能力を持つ。
我々は、幅広い推論規則を検証し、より単純な実演からより複雑な証明に一般化する能力を測定する。
様々な大きさのLLMと訓練目的の4つの実験により、合成証明に一般化できることが示されている。
論文 参考訳(メタデータ) (2023-05-24T15:55:51Z) - ReCEval: Evaluating Reasoning Chains via Correctness and Informativeness [67.49087159888298]
ReCEvalは2つの重要な特性(正確性と情報性)を通じて推論チェーンを評価するフレームワークである。
本稿では、ReCEvalが様々なエラータイプを効果的に識別し、従来の手法と比較して顕著な改善をもたらすことを示す。
論文 参考訳(メタデータ) (2023-04-21T02:19:06Z) - Generating Natural Language Proofs with Verifier-Guided Search [74.9614610172561]
NLProofS (Natural Language Proof Search) を提案する。
NLProofSは仮説に基づいて関連するステップを生成することを学習する。
EntailmentBank と RuleTaker の最先端のパフォーマンスを実現している。
論文 参考訳(メタデータ) (2022-05-25T02:22:30Z) - The General Adversary Bound: A Survey [2.3986080077861787]
ベン・ライハルト(Ben Reichardt)は一連の結果において、関数の一般逆境界がその量子クエリの複雑さを特徴づけることを示した。
この調査は、証明を理解するのに必要な背景と定義をまとめたものだ。
論文 参考訳(メタデータ) (2021-04-13T17:35:16Z) - A simple geometric proof for the benefit of depth in ReLU networks [57.815699322370826]
本論文では, 多層フィードフォワードネットワークにおける深度の利点を, 整流活性化(深度分離)により証明する。
我々は、線形深さ($m$)と小さな定数幅($leq 4$)を持つ具体的なニューラルネットワークを示し、問題をゼロエラーで分類する。
論文 参考訳(メタデータ) (2021-01-18T15:40:27Z) - Causal Expectation-Maximisation [70.45873402967297]
ポリツリーグラフを特徴とするモデルにおいても因果推論はNPハードであることを示す。
我々は因果EMアルゴリズムを導入し、分類的表現変数のデータから潜伏変数の不確かさを再構築する。
我々は、反事実境界が構造方程式の知識なしにしばしば計算できるというトレンドのアイデアには、目立たずの制限があるように思える。
論文 参考訳(メタデータ) (2020-11-04T10:25:13Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。