Fugu-MT 論文翻訳(概要): Learning temporal formulas from examples is hard

論文の概要: Learning temporal formulas from examples is hard

arxiv url: http://arxiv.org/abs/2312.16336v1
Date: Tue, 26 Dec 2023 21:16:19 GMT
ステータス: 処理完了
システム内更新日: 2023-12-29 20:06:04.496796
Title: Learning temporal formulas from examples is hard
Title（参考訳）: 例から時間式を学ぶことは難しい
Authors: Corto Mascle, Nathana\"el Fijalkow, Guillaume Lagarde
Abstract要約: 本稿では,線形時間論理式(LTL)を例から学習する問題について検討する。学習問題は完全論理とほぼすべてのフラグメントに対してNP完全であることを示す。
参考スコア（独自算出の注目度）: 2.8851756275902476
License: http://creativecommons.org/licenses/by/4.0/
Abstract: We study the problem of learning linear temporal logic (LTL) formulas from examples, as a first step towards expressing a property separating positive and negative instances in a way that is comprehensible for humans. In this paper we initiate the study of the computational complexity of the problem. Our main results are hardness results: we show that the LTL learning problem is NP-complete, both for the full logic and for almost all of its fragments. This motivates the search for efficient heuristics, and highlights the complexity of expressing separating properties in concise natural language.
Abstract（参考訳）: 線形時間論理式(LTL)の学習問題を,人間にとって理解しやすい方法で,正と負のインスタンスを分離する性質を表現するための第一歩として,例から考察する。本稿では,問題の計算複雑性の研究を開始する。 ltl学習問題は、全論理とほぼすべてのフラグメントの両方において、np完全であることを示している。これは効率的なヒューリスティックの探索を動機付け、簡潔な自然言語でプロパティを分離する複雑さを強調している。

関連論文リスト

Divide and Translate: Compositional First-Order Logic Translation and Verification for Complex Logical Reasoning [28.111458981621105]
複雑な論理的推論タスクは、長い推論を必要とするが、それは、チェーン・オブ・シークレットのプロンプトを持つ大きな言語モデル(LLM)が依然として不足している。本稿では,翻訳中に自然言語に隠された論理的意味を抽出する合成一階論理翻訳を提案する。提案手法は,CLOVERと呼ばれる7つの論理的推論ベンチマークを用いて評価し,従来のニューロシンボリックアプローチよりも優れていたことを示す。
論文参考訳（メタデータ） (2024-10-10T15:42:39Z)
Data Complexity in Expressive Description Logics With Path Expressions [7.832189413179361]
本稿では,表現的記述論理ZOIQ(ALCHb Self reg OIQ)の準フォレスト上でのデータ複雑性について検討する。これにより、ZOIQの決定可能なフラグメントに対するデータ複雑性の展望が完成し、OWL2(SRファミリー)の決定可能なフラグメントに関する既知の結果が改善される。
論文参考訳（メタデータ） (2024-06-11T09:37:51Z)
Do Language Models Exhibit the Same Cognitive Biases in Problem Solving as Human Learners? [140.9751389452011]
本研究では,大言語モデル(LLM)の偏りを,算術語問題を解く際に,子どもに知られているものと関連づけて検討する。我々は,これらの各テストに対して,問題特徴のきめ細かい制御を可能にするニューロシンボリックアプローチを用いて,新しい単語問題を生成する。
論文参考訳（メタデータ） (2024-01-31T18:48:20Z)
Language Models can be Logical Solvers [99.40649402395725]
論理解法の推論過程を直接エミュレートする新しい言語モデルであるLoGiPTを導入する。 LoGiPTは、導出的ソルバの見えない推論過程を明らかにして精錬することから導かれる、新しく構築された命令チューニングデータセットに基づいて微調整される。
論文参考訳（メタデータ） (2023-11-10T16:23:50Z)
When Do Program-of-Thoughts Work for Reasoning? [51.2699797837818]
本稿では,コードと推論能力の相関性を測定するために,複雑性に富んだ推論スコア(CIRS)を提案する。具体的には、抽象構文木を用いて構造情報をエンコードし、論理的複雑性を計算する。コードはhttps://github.com/zjunlp/EasyInstructのEasyInstructフレームワークに統合される。
論文参考訳（メタデータ） (2023-08-29T17:22:39Z)
Amortized Inference for Causal Structure Learning [72.84105256353801]
因果構造を学習することは、通常、スコアまたは独立テストを使用して構造を評価することを伴う探索問題を引き起こす。本研究では,観測・干渉データから因果構造を予測するため,変分推論モデルを訓練する。我々のモデルは、実質的な分布シフトの下で頑健な一般化能力を示す。
論文参考訳（メタデータ） (2022-05-25T17:37:08Z)
Generalization of Neural Combinatorial Solvers Through the Lens of Adversarial Robustness [68.97830259849086]
ほとんどのデータセットは単純なサブプロブレムのみをキャプチャし、おそらくは突発的な特徴に悩まされる。本研究では, 局所的な一般化特性である対向ロバスト性について検討し, 厳密でモデル固有な例と突発的な特徴を明らかにする。他のアプリケーションとは異なり、摂動モデルは知覚できないという主観的な概念に基づいて設計されているため、摂動モデルは効率的かつ健全である。驚くべきことに、そのような摂動によって、十分に表現力のあるニューラルソルバは、教師あり学習で共通する正確さと悪質さのトレードオフの限界に悩まされない。
論文参考訳（メタデータ） (2021-10-21T07:28:11Z)
The Complexity of Learning Linear Temporal Formulas from Examples [2.766648389933265]
我々は断片化のための近似アルゴリズムを構築し、硬度結果の証明を行う。特に、次の演算子と接続子のみを含むフラグメントの近似の厳密な境界を求め、多くのフラグメントに対してNP完全性を示す。
論文参考訳（メタデータ） (2021-02-01T14:34:46Z)
The Complexity of Adversarially Robust Proper Learning of Halfspaces with Agnostic Noise [67.27523616312428]
分布非依存型PACモデルにおけるハーフスペースの逆強正則学習の計算複雑性について検討する。この問題に対して,計算効率のよい学習アルゴリズムとほぼ一致する計算硬度結果を与える。
論文参考訳（メタデータ） (2020-07-30T04:18:51Z)
A tetrachotomy of ontology-mediated queries with a covering axiom [1.749935196721634]
我々の懸念は、標準的なデータベースクエリへの記述とそれらの最適な書き換えを介し、クエリに応答する際のデータ複雑さを効率的に決定することである。我々は、疎結合シロップ(d-シロップ)と呼ばれるブール共役型クエリに焦点を当てる。一部のd-シロップは指数的な大きさの分解能しか持たないが、そのうちのいくつかは二重指数サイズの正存在量書き換えと単帰的データログ書き換えのみである。
論文参考訳（メタデータ） (2020-06-07T14:47:07Z)
Learning Interpretable Models in the Property Specification Language [6.875312133832079]
IEEE標準時相論理PSLにおける公式の学習アルゴリズムを開発した。私たちの研究は、n番目の点ごとに起こる事象のような多くの自然の性質が、言葉で表現できないという事実に動機づけられている。
論文参考訳（メタデータ） (2020-02-10T11:42:50Z)

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