Fugu-MT 論文翻訳(概要): LTL learning on GPUs

論文の概要: LTL learning on GPUs

arxiv url: http://arxiv.org/abs/2402.12373v2
Date: Wed, 27 Mar 2024 20:00:00 GMT
ステータス: 処理完了
システム内更新日: 2024-03-29 20:52:50.482605
Title: LTL learning on GPUs
Title（参考訳）: GPUによるLTL学習
Authors: Mojtaba Valizadeh, Nathanaël Fijalkow, Martin Berger,
Abstract要約: 線形時間論理(LTL)は工業的検証公式で広く使われている。列挙型プログラムの新たな形式を用いて,GPUを用いた最初の学習者を実装した。
参考スコア（独自算出の注目度）: 1.3422713954544112
License: http://creativecommons.org/licenses/by-nc-nd/4.0/
Abstract: Linear temporal logic (LTL) is widely used in industrial verification. LTL formulae can be learned from traces. Scaling LTL formula learning is an open problem. We implement the first GPU-based LTL learner using a novel form of enumerative program synthesis. The learner is sound and complete. Our benchmarks indicate that it handles traces at least 2048 times more numerous, and on average at least 46 times faster than existing state-of-the-art learners. This is achieved with, among others, novel branch-free LTL semantics that has $O(\log n)$ time complexity, where $n$ is trace length, while previous implementations are $O(n^2)$ or worse (assuming bitwise boolean operations and shifts by powers of 2 have unit costs -- a realistic assumption on modern processors).
Abstract（参考訳）: 線形時間論理(LTL)は産業的検証に広く用いられている。 LTLの公式はトレースから学ぶことができる。 LTL公式学習のスケーリングはオープンな問題である。我々は,新しい列挙型プログラム合成形式を用いて,GPUベースのLTL学習器を実装した。学習者は健全で完ぺきです。我々のベンチマークでは、少なくとも2048倍のトレースを処理し、既存の最先端の学習者よりも平均46倍高速であることが示された。これは、例えば、$O(\log n)$時間複雑性を持つ新しいブランチフリーLTLセマンティクスで実現される。$n$はトレース長であり、以前の実装は$O(n^2)$以上である(ビットワイズなブール演算と2のパワーによるシフトは、現代のプロセッサにおける現実的な仮定である)。

関連論文リスト

TCNCA: Temporal Convolution Network with Chunked Attention for Scalable Sequence Processing [52.64837396100988]
MEGAは最近のトランスフォーマーベースのアーキテクチャで、線形リカレント演算子を使用し、並列計算はFFTに基づいて、$O(LlogL)$で、$L$はシーケンス長である。線形再帰を特別な時間的畳み込みネットワークに置き換えることで、より浅いネットワークでより大きい受容場を許容し、計算複雑性を$O(L)$に減らし、それらのアプローチを構築する。我々は,EnWik8言語モデリングにおけるTCNCA,LRA(Long-range-arena)シーケンス分類,および合成推論ベンチマーク連想リコールの評価を行った。
論文参考訳（メタデータ） (2023-12-09T16:12:25Z)
Longest Common Substring and Longest Palindromic Substring in $\tilde{\mathcal{O}}(\sqrt{n})$ Time [0.0]
LCS(Longest Common Substring)とLPS(Longest Palindromic Substring)は、コンピュータ科学における古典的な問題である。計算回路モデルにおいて, LCS と LPS の双方に対する量子アルゴリズムを提案する。
論文参考訳（メタデータ） (2023-09-03T19:27:57Z)
Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文参考訳（メタデータ） (2023-07-24T14:37:22Z)
Layered State Discovery for Incremental Autonomous Exploration [106.37656068276901]
Layered Autonomous Exploration (LAE) は、$tildemathcalO(LSrightarrow_LAln12(Srightarrow_LAln12(Srightarrow_LAln12(Srightarrow_LAln12(Srightar row_LAln12)Srightarrow_LAln12(Srightarrow_LAln12)Srightarrow_LAln12(Srightarrow_LAln12)のサンプル複雑性を達成するAXの新しいアルゴリズムである。
論文参考訳（メタデータ） (2023-02-07T22:58:12Z)
Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
論文参考訳（メタデータ） (2022-06-07T18:00:01Z)
A Push-Relabel Based Additive Approximation for Optimal Transport [5.111364864495785]
最適な輸送を計算するための厳密なアルゴリズムは遅くなる。我々は、OT距離の$varepsilon$approximationを求めるための、新しい非常に単純なアプローチを導入する。我々のアルゴリズムは、OT距離を計算するために、O(n2/varepsilon2)$のほぼ最適実行時間を達成する。
論文参考訳（メタデータ） (2022-03-07T21:40:14Z)
Learning Finite Linear Temporal Logic Specifications with a Specialized Neural Operator [0.0]
本稿では,システム動作のラベル付きトレースから,コンパクトな$mathsfLTL_f$式を学習する問題に対処する。提案手法は, 時間演算子$mathsfLTL_f$をサブスクライブする特殊リカレントフィルタを含む。ランダムに生成された$mathsfLTL_f$式の実験は、既存の手法よりも大きな公式サイズにスケールしたNeural$mathsfLTL_f$を示す。
論文参考訳（メタデータ） (2021-11-07T18:51:02Z)
Scalable Anytime Algorithms for Learning Formulas in Linear Temporal Logic [2.631744051718347]
トレースを分類する公式を学習する際の問題点を考察する。既存の解には2つの制限がある: それらは小さな公式を超えてスケールせず、結果を返すことなく計算資源を消費する。我々は,両問題に対処する新しいアルゴリズムを導入する。我々のアルゴリズムは,従来よりも桁違いに大きい式を構築でき,いつでも可能である。
論文参考訳（メタデータ） (2021-10-13T13:57:31Z)
Mixability made efficient: Fast online multiclass logistic regression [68.8204255655161]
我々は、混合性は最適な後悔を伴うアルゴリズムを得るための強力なツールであることを示した。結果として得られる手法は、しばしば計算の複雑さに悩まされ、実用性が低下した。
論文参考訳（メタデータ） (2021-10-08T08:22:05Z)
Higher-order Derivatives of Weighted Finite-state Machines [68.43084108204741]
本研究では、重み付き有限状態機械の正規化定数に関する高次微分の計算について検討する。文献に記載されていないすべての順序の導関数を評価するための一般アルゴリズムを提案する。我々のアルゴリズムは以前のアルゴリズムよりもはるかに高速である。
論文参考訳（メタデータ） (2021-06-01T19:51:55Z)
Sub-Linear Memory: How to Make Performers SLiM [38.068090269482425]
vanilla Transformerは、入力長$L$の関数としてシリアル時間とメモリで$O(L2)$を必要とする。最近の研究は、連続計算に$o(l)$でしかスケールしない様々な線形自己アテンション機構を提案している。計算の柔軟性は顕著であり, サブリニアメモリを用いた近似をすることなく, 前方および後方の伝播を行うことができる。
論文参考訳（メタデータ） (2020-12-21T13:56:04Z)

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