Fugu-MT 論文翻訳(概要): The Complexity of Learning Linear Temporal Formulas from Examples

論文の概要: The Complexity of Learning Linear Temporal Formulas from Examples

arxiv url: http://arxiv.org/abs/2102.00876v1
Date: Mon, 1 Feb 2021 14:34:46 GMT
ステータス: 処理完了
システム内更新日: 2021-02-04 09:53:42.817283
Title: The Complexity of Learning Linear Temporal Formulas from Examples
Title（参考訳）: 実例からの線形時間公式の学習の複雑さ
Authors: Nathana\"el Fijalkow and Guillaume Lagarde
Abstract要約: 我々は断片化のための近似アルゴリズムを構築し、硬度結果の証明を行う。特に、次の演算子と接続子のみを含むフラグメントの近似の厳密な境界を求め、多くのフラグメントに対してNP完全性を示す。
参考スコア（独自算出の注目度）: 2.766648389933265
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: In this paper we initiate the study of the computational complexity of learning linear temporal logic (LTL) formulas from examples. We construct approximation algorithms for fragments of LTL and prove hardness results; in particular we obtain tight bounds for approximation of the fragment containing only the next operator and conjunctions, and prove NP-completeness results for many fragments.
Abstract（参考訳）: 本稿では、例から線形時間論理(LTL)式を学習する計算の複雑さの研究を開始する。我々はLTLのフラグメントに対する近似アルゴリズムを構築し、硬さを証明し、特に、次の演算子と接続子のみを含むフラグメントの近似の厳密な境界を求め、多くのフラグメントに対するNP完全性の結果を証明する。

関連論文リスト

Timeline-based Sentence Decomposition with In-Context Learning for Temporal Fact Extraction [19.96263282146533]
本稿では,自然言語テキストから時間的事実を抽出する方法について述べる。本稿では,大規模言語モデル(LLM)と文脈内学習を用いたタイムラインに基づく文分解手法を提案する。実験の結果, TSDRE は HyperRED-Temporal データセットと ComplexTRED データセットの両方で最先端の結果が得られることがわかった。
論文参考訳（メタデータ） (2024-05-16T17:48:21Z)
Learning temporal formulas from examples is hard [2.8851756275902476]
本稿では,線形時間論理式(LTL)を例から学習する問題について検討する。学習問題は完全論理とほぼすべてのフラグメントに対してNP完全であることを示す。
論文参考訳（メタデータ） (2023-12-26T21:16:19Z)
Tractable Bounding of Counterfactual Queries by Knowledge Compilation [51.47174989680976]
本稿では, パール構造因果モデルにおいて, 因果関係などの部分的特定可能なクエリのバウンダリングの問題について議論する。最近提案された反復EMスキームは初期化パラメータをサンプリングしてそれらの境界を内部近似する。シンボルパラメータを実際の値に置き換えた回路構造を,単一のシンボル知識コンパイルによって得られることを示す。
論文参考訳（メタデータ） (2023-10-05T07:10:40Z)
An Optimal Algorithm for the Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit [65.268245109828]
多武装バンディット(R-CPE-MAB)の真価純探査問題について検討する。既存のR-CPE-MABの手法は、いわゆるトランスダクティブ線形帯域の特殊な場合と見なすことができる。本稿では,差分探索アルゴリズム (CombGapE) を提案する。
論文参考訳（メタデータ） (2023-06-15T15:37:31Z)
Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
本稿では,完全合成最適化問題を凸コンパクト集合で解くための一階アルゴリズムについて検討する。微分可能および非微分可能を別々に扱い、滑らかな部分のみを線形化することで目的の構造を利用する。
論文参考訳（メタデータ） (2023-02-24T18:41:48Z)
Reinforcement Learning from Partial Observation: Linear Function Approximation with Provable Sample Efficiency [111.83670279016599]
部分観察決定過程(POMDP)の無限観測および状態空間を用いた強化学習について検討した。線形構造をもつPOMDPのクラスに対する部分可観測性と関数近似の最初の試みを行う。
論文参考訳（メタデータ） (2022-04-20T21:15:38Z)
Sublinear Least-Squares Value Iteration via Locality Sensitive Hashing [49.73889315176884]
本稿では、実行時の複雑さをアクション数にサブリニアに持つ最初の証明可能なLeast-Squares Value Iteration(LSVI)アルゴリズムを提示する。我々は, 近似最大内積探索理論と強化学習の後悔分析との関係を構築する。
論文参考訳（メタデータ） (2021-05-18T05:23:53Z)
Fast and Complete: Enabling Complete Neural Network Verification with Rapid and Massively Parallel Incomplete Verifiers [112.23981192818721]
BaB プロセス中に線形計画法 (LP) を置き換えるために, 逆モード線形緩和に基づく解析法 (LiRPA) を提案する。 LPとは異なり、LiRPAを適用すると、より弱い境界が得られ、分割時にサブドメインのコンフリクトをチェックすることもできない。既存のLPベースのアプローチと比較して、桁違いのスピードアップを示す。
論文参考訳（メタデータ） (2020-11-27T16:42:12Z)
Explaining Multi-stage Tasks by Learning Temporal Logic Formulas from Suboptimal Demonstrations [6.950510860295866]
本稿では,一貫した線形時間論理式(LTL)の論理構造と原子命題を学習し,実演から多段階タスクを学習する手法を提案する。学習者は、その式を満足しながらコスト関数を最適化し、学習者にはコスト関数が不確実な場合において、成功しているが潜在的に最適でないデモンストレーションが与えられる。提案アルゴリズムでは,デモのKKT(Karush-Kuhn-Tucker)最適条件と反例誘導ファルシフィケーション戦略を用いて,原子命題パラメータを学習する。
論文参考訳（メタデータ） (2020-06-03T17:40:14Z)
Learning Interpretable Models in the Property Specification Language [6.875312133832079]
IEEE標準時相論理PSLにおける公式の学習アルゴリズムを開発した。私たちの研究は、n番目の点ごとに起こる事象のような多くの自然の性質が、言葉で表現できないという事実に動機づけられている。
論文参考訳（メタデータ） (2020-02-10T11:42:50Z)

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