論文の概要: Learning Linear Temporal Properties from Noisy Data: A MaxSAT Approach

• arxiv url: http://arxiv.org/abs/2104.15083v1
• Date: Fri, 30 Apr 2021 16:06:03 GMT
• ステータス: 処理完了
• システム内更新日: 2021-05-03 13:46:59.442233
• Title: Learning Linear Temporal Properties from Noisy Data: A MaxSAT Approach
• Title（参考訳）: 雑音データから線形時間特性を学習する: MaxSAT アプローチ
• Authors: Jean-Rapha\"el Gaglione, Daniel Neider, Rajarshi Roy, Ufuk Topcu and Zhe Xu
• Abstract要約: 雑音の存在下でも簡潔な公式を推測するための2つのアルゴリズムを考案する。 我々の第一のアルゴリズムは、推論問題を満足できる問題に還元することで最小の式を推論する。 第2の学習アルゴリズムは、決定木学習アルゴリズムに基づく公式上の決定木を導出する第1のアルゴリズムに依存している。
• 参考スコア（独自算出の注目度）: 22.46055650237819
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We address the problem of inferring descriptions of system behavior using Linear Temporal Logic (LTL) from a finite set of positive and negative examples. Most of the existing approaches for solving such a task rely on predefined templates for guiding the structure of the inferred formula. The approaches that can infer arbitrary LTL formulas, on the other hand, are not robust to noise in the data. To alleviate such limitations, we devise two algorithms for inferring concise LTL formulas even in the presence of noise. Our first algorithm infers minimal LTL formulas by reducing the inference problem to a problem in maximum satisfiability and then using off-the-shelf MaxSAT solvers to find a solution. To the best of our knowledge, we are the first to incorporate the usage of MaxSAT solvers for inferring formulas in LTL. Our second learning algorithm relies on the first algorithm to derive a decision tree over LTL formulas based on a decision tree learning algorithm. We have implemented both our algorithms and verified that our algorithms are efficient in extracting concise LTL descriptions even in the presence of noise.
• Abstract（参考訳）: 本稿では, 線形時間論理(LTL)を用いたシステム動作の記述を, 有限の正と負の例から推定する問題に対処する。 そのようなタスクを解決する既存のアプローチのほとんどは、推論された式の構造を導くための事前定義されたテンプレートに依存している。 一方、任意の ltl 公式を推論できるアプローチは、データのノイズに対して堅牢ではない。 このような制約を緩和するため,ノイズの存在下でも簡潔LTL式を推定する2つのアルゴリズムを考案した。 第1のアルゴリズムは,最大充足性の問題に推論問題を還元し,既定のmaxsatソルバを用いて解を求めることで,最小のltl公式を推定する。 我々の知識を最大限に活用するため、我々は ltl の式を推論するために maxsat ソルバを最初に組み込んだ。 我々の第2の学習アルゴリズムは、決定木学習アルゴリズムに基づいてLTL式よりも決定木を導出する最初のアルゴリズムに依存している。 我々は,2つのアルゴリズムを実装し,ノイズがあっても簡潔なLTL記述の抽出に有効であることを検証した。

関連論文リスト

• Learning Optimal Signal Temporal Logic Decision Trees for Classification: A Max-Flow MILP Formulation [5.924780594614676]
  本稿では,データから時間的時間的論理特性を推定するための新しい枠組みを提案する。 混合整数線形プログラミング最適化問題として推論過程を定式化する。 結果木に最大フローアルゴリズムを適用すると、この問題はグローバルな最適化問題に変換される。 我々は,2クラス,複数クラス,複雑な式分類シナリオを含む3つのケーススタディを実施している。
  論文  参考訳（メタデータ） (2024-07-30T16:56:21Z)
• Efficiently Explaining CSPs with Unsatisfiable Subset Optimization (extended algorithms and examples) [14.163888405810635]
  我々は,制約満足度問題の解法を段階的に説明する手法を最近提案した。 ここでは、コスト関数を用いて単純さを定量化する単純な推論ステップの列を説明する。
  論文  参考訳（メタデータ） (2023-03-21T10:03:36Z)
• Learning Temporal Logic Properties: an Overview of Two Recent Methods [27.929058359327186]
  正あるいは負とラベル付けされた例から線形時間論理(LTL)公式を学習することで、システムの振る舞いの記述を推測することが可能になる。 2つの異なる問題設定における例から公式を学習する2つの方法を提案する。
  論文  参考訳（メタデータ） (2022-12-02T00:32:09Z)
• Scalable Anytime Algorithms for Learning Formulas in Linear Temporal Logic [2.631744051718347]
  トレースを分類する公式を学習する際の問題点を考察する。 既存の解には2つの制限がある: それらは小さな公式を超えてスケールせず、結果を返すことなく計算資源を消費する。 我々は,両問題に対処する新しいアルゴリズムを導入する。我々のアルゴリズムは,従来よりも桁違いに大きい式を構築でき,いつでも可能である。
  論文  参考訳（メタデータ） (2021-10-13T13:57:31Z)
• Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
  バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。 両レベル最適化のための2つの新しいアルゴリズムを提案する。 両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
  論文  参考訳（メタデータ） (2021-06-08T21:05:30Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。 本研究の結果は, 同時一次および二重側収束の形で表される。
  論文  参考訳（メタデータ） (2020-08-23T20:36:49Z)
• Lagrangian Decomposition for Neural Network Verification [148.0448557991349]
  ニューラルネットワーク検証の基本的なコンポーネントは、出力が取ることのできる値のバウンダリの計算である。 ラグランジアン分解に基づく新しい手法を提案する。 ランニングタイムのごく一部で、既成の解法に匹敵するバウンダリが得られることを示す。
  論文  参考訳（メタデータ） (2020-02-24T17:55:10Z)
• Second-order Conditional Gradient Sliding [79.66739383117232]
  本稿では,emphSecond-Order Conditional Gradient Sliding (SOCGS)アルゴリズムを提案する。 SOCGSアルゴリズムは、有限個の線形収束反復の後、原始ギャップに二次的に収束する。 実現可能な領域が線形最適化オラクルを通してのみ効率的にアクセスできる場合に有用である。
  論文  参考訳（メタデータ） (2020-02-20T17:52:18Z)
• Learning Interpretable Models in the Property Specification Language [6.875312133832079]
  IEEE標準時相論理PSLにおける公式の学習アルゴリズムを開発した。 私たちの研究は、n番目の点ごとに起こる事象のような多くの自然の性質が、言葉で表現できないという事実に動機づけられている。
  論文  参考訳（メタデータ） (2020-02-10T11:42:50Z)

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

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