論文の概要: Scalable Anytime Algorithms for Learning Formulas in Linear Temporal Logic

• arxiv url: http://arxiv.org/abs/2110.06726v1
• Date: Wed, 13 Oct 2021 13:57:31 GMT
• ステータス: 処理完了
• システム内更新日: 2021-10-14 14:02:57.108089
• Title: Scalable Anytime Algorithms for Learning Formulas in Linear Temporal Logic
• Title（参考訳）: 線形時相論理における数式学習のためのスケーラブルな時間アルゴリズム
• Authors: Ritam Raha, Rajarshi Roy, Nathana\"el Fijalkow, Daniel Neider
• Abstract要約: トレースを分類する公式を学習する際の問題点を考察する。 既存の解には2つの制限がある: それらは小さな公式を超えてスケールせず、結果を返すことなく計算資源を消費する。 我々は,両問題に対処する新しいアルゴリズムを導入する。我々のアルゴリズムは,従来よりも桁違いに大きい式を構築でき,いつでも可能である。
• 参考スコア（独自算出の注目度）: 2.631744051718347
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Linear temporal logic (LTL) is a specification language for finite sequences (called traces) widely used in program verification, motion planning in robotics, process mining, and many other areas. We consider the problem of learning LTL formulas for classifying traces; despite a growing interest of the research community, existing solutions suffer from two limitations: they do not scale beyond small formulas, and they may exhaust computational resources without returning any result. We introduce a new algorithm addressing both issues: our algorithm is able to construct formulas an order of magnitude larger than previous methods, and it is anytime, meaning that it in most cases successfully outputs a formula, albeit possibly not of minimal size. We evaluate the performances of our algorithm using an open source implementation against publicly available benchmarks.
• Abstract（参考訳）: 線形時間論理(LTL)は、プログラム検証、ロボット工学における動作計画、プロセスマイニング、その他多くの分野で広く使われている有限列(トレースと呼ばれる)の仕様言語である。 研究コミュニティの関心が高まっているにもかかわらず、既存のソリューションには2つの制限がある: それらは小さな公式を超えてスケールせず、結果を返すことなく計算資源を消費する。 我々のアルゴリズムは、以前の方法よりも桁違いに大きい式を構築できるため、ほとんどの場合、最小限ではなく、式を出力できる。 公開ベンチマークに対するオープンソース実装を用いて,提案アルゴリズムの性能評価を行った。

関連論文リスト

• When can you trust feature selection? -- I: A condition-based analysis of LASSO and generalised hardness of approximation [49.1574468325115]
  近似入力を読み取る際に、LASSOのミニミサの正しいサポートセットを(確率$>1/2$で)決定できないことを示す。 不適切な入力の場合、アルゴリズムは永遠に動作するので、間違った答えを出すことはない。 無限条件数を持つ点を含む開集合上で定義される任意のアルゴリズムに対して、アルゴリズムが永久に実行されるか、間違った解を生成するような入力が存在する。
  論文  参考訳（メタデータ） (2023-12-18T18:29:01Z)
• Algorithm of Thoughts: Enhancing Exploration of Ideas in Large Language Models [17.059322033670124]
  本稿では,アルゴリズム的推論経路を通じて大規模言語モデルを促進する新しい手法を提案する。 この結果から,LLMをアルゴリズムを用いて指導すると,アルゴリズム自体よりも性能が向上する可能性が示唆された。
  論文  参考訳（メタデータ） (2023-08-20T22:36:23Z)
• Machine Learning for Online Algorithm Selection under Censored Feedback [71.6879432974126]
  オンラインアルゴリズム選択(OAS)では、アルゴリズム問題クラスのインスタンスがエージェントに次々に提示され、エージェントは、固定された候補アルゴリズムセットから、おそらく最高のアルゴリズムを迅速に選択する必要がある。 SAT(Satisfiability)のような決定問題に対して、品質は一般的にアルゴリズムのランタイムを指す。 本研究では,OASのマルチアームバンディットアルゴリズムを再検討し,この問題に対処する能力について議論する。 ランタイム指向の損失に適応し、時間的地平線に依存しない空間的・時間的複雑さを維持しながら、部分的に検閲されたデータを可能にする。
  論文  参考訳（メタデータ） (2021-09-13T18:10:52Z)
• Learning Linear Temporal Properties from Noisy Data: A MaxSAT Approach [22.46055650237819]
  雑音の存在下でも簡潔な公式を推測するための2つのアルゴリズムを考案する。 我々の第一のアルゴリズムは、推論問題を満足できる問題に還元することで最小の式を推論する。 第2の学習アルゴリズムは、決定木学習アルゴリズムに基づく公式上の決定木を導出する第1のアルゴリズムに依存している。
  論文  参考訳（メタデータ） (2021-04-30T16:06:03Z)
• Algorithmic Solution for Systems of Linear Equations, in $\mathcal{O}(mn)$ time [0.0]
  方程式の線形系の探索解を超高速に求める新しいアルゴリズムを提案する。 実行時間は最先端のメソッドと比較して非常に短い。 この論文はアルゴリズム収束の理論的証明も含んでいる。
  論文  参考訳（メタデータ） (2021-04-26T13:40:31Z)
• Evolving Reinforcement Learning Algorithms [186.62294652057062]
  メタラーニング強化学習アルゴリズムの手法を提案する。 学習アルゴリズムはドメインに依存しないため、トレーニング中に見えない新しい環境に一般化することができる。 従来の制御タスク、gridworld型タスク、atariゲームよりも優れた一般化性能を得る2つの学習アルゴリズムに注目した。
  論文  参考訳（メタデータ） (2021-01-08T18:55:07Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• Parallel Scheduling Self-attention Mechanism: Generalization and Optimization [0.76146285961466]
  本稿では,SAT(Satisfiability check)ソルバによって解決された小インスタンスの最適スケジューリングから導いた一般スケジューリングアルゴリズムを提案する。 余剰計算をスキップする際のさらなる最適化戦略も推進され、元の計算の約25%と50%の削減が達成される。 提案アルゴリズムは、入力ベクトルの数がアーキテクチャで利用可能な演算ユニットの数に割り切れる限り、問題のサイズにかかわらず適用可能である。
  論文  参考訳（メタデータ） (2020-12-02T12:04:16Z)
• Strong Generalization and Efficiency in Neural Programs [69.18742158883869]
  本稿では,ニューラルプログラム誘導の枠組みを強く一般化する効率的なアルゴリズムを学習する問題について検討する。 ニューラルネットワークの入力/出力インターフェースを慎重に設計し、模倣することで、任意の入力サイズに対して正しい結果を生成するモデルを学ぶことができる。
  論文  参考訳（メタデータ） (2020-07-07T17:03:02Z)
• Run2Survive: A Decision-theoretic Approach to Algorithm Selection based on Survival Analysis [75.64261155172856]
  生存分析(SA)は、自然に検閲されたデータをサポートし、アルゴリズムランタイムの分散モデルを学習するためにそのようなデータを使用する適切な方法を提供する。 我々は、アルゴリズム選択に対する洗練された決定論的アプローチの基礎として、そのようなモデルを活用し、Run2Surviveを疑う。 標準ベンチマークASlibによる広範な実験では、我々のアプローチは競争力が高く、多くの場合、最先端のASアプローチよりも優れていることが示されている。
  論文  参考訳（メタデータ） (2020-07-06T15:20:17Z)
• Learning Interpretable Models in the Property Specification Language [6.875312133832079]
  IEEE標準時相論理PSLにおける公式の学習アルゴリズムを開発した。 私たちの研究は、n番目の点ごとに起こる事象のような多くの自然の性質が、言葉で表現できないという事実に動機づけられている。
  論文  参考訳（メタデータ） (2020-02-10T11:42:50Z)

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

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