論文の概要: Search-Based Regular Expression Inference on a GPU
- arxiv url: http://arxiv.org/abs/2305.18575v1
- Date: Mon, 29 May 2023 19:37:15 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-31 19:36:01.719935
- Title: Search-Based Regular Expression Inference on a GPU
- Title（参考訳）: gpuによる検索に基づく正規表現推論
- Authors: Mojtaba Valizadeh, Martin Berger
- Abstract要約: 正規表現推論(REI)は教師付き機械学習とプログラム合成の問題である。
正規表現のコストメトリックと、入力として文字列の正と負の例を取る。
本稿では,任意のアルファベットに対するREIの新しいアルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: Regular expression inference (REI) is a supervised machine learning and
program synthesis problem that takes a cost metric for regular expressions, and
positive and negative examples of strings as input. It outputs a regular
expression that is precise (i.e., accepts all positive and rejects all negative
examples), and minimal w.r.t. to the cost metric. We present a novel algorithm
for REI over arbitrary alphabets that is enumerative and trades off time for
space. Our main algorithmic idea is to implement the search space of regular
expressions succinctly as a contiguous matrix of bitvectors. Collectively, the
bitvectors represent, as characteristic sequences, all sub-languages of the
infix-closure of the union of positive and negative examples. Mathematically,
this is a semiring of (a variant of) formal power series. Infix-closure enables
bottom-up compositional construction of larger from smaller regular expressions
using the operations of our semiring. This minimises data movement and
data-dependent branching, hence maximises data-parallelism. In addition, the
infix-closure remains unchanged during the search, hence search can be staged:
first pre-compute various expensive operations, and then run the compute
intensive search process. We provide two C++ implementations, one for general
purpose CPUs and one for Nvidia GPUs (using CUDA). We benchmark both on Google
Colab Pro: the GPU implementation is on average over 1000x faster than the CPU
implementation on the hardest benchmarks.
- Abstract（参考訳）: 正規表現推論(Regular Expression Inference、REI)は、正規表現のコストメトリックと、入力として文字列の正と負の例を用いる教師付き機械学習およびプログラム合成問題である。
正確な正規表現(つまり、すべての正を受け入れ、すべての負の例を拒絶する)と最小の w.r.t. をコストメトリックに出力する。
本稿では,任意のアルファベットに対するREIの新しいアルゴリズムを提案する。
我々のアルゴリズムの主なアイデアは、ビットベクトルの連続行列として簡潔に正規表現の探索空間を実装することである。
集合的に、ビットベクターは特性列として、正および負の例の和の固定閉包のすべての部分言語を表す。
数学的には、これは(不変の)形式的パワー級数の半環である。
Infix-closureは、セミリングの操作を用いて、より小さな正規表現からより大きい構成のボトムアップ構築を可能にする。
これはデータ移動とデータ依存分岐を最小化し、データ並列性を最大化する。
さらに、infix-closureは検索中に変化しないため、検索は、まず様々な高価な操作をプリコンプリートし、計算集約的な検索プロセスを実行する。
汎用CPU用とNvidia GPU用(CUDAを使用)の2つのC++実装を提供する。
GPUの実装は、最も難しいベンチマークのCPU実装よりも平均1000倍以上高速です。
関連論文リスト
- Efficient Algorithms for Recognizing Weighted Tree-Adjoining Languages [104.90415092306219]
4つの形式は、ツリー随伴文法(TAG)、線形指数文法(LIG)、プッシュダウン随伴オートマトン(PAA)、組込みプッシュダウンオートマトン(EPDA)に相当する。
我々は,文字列の導出量(文字列のすべてのオートマトン重み)と全導出量(全ての導出量重み)を計算するための新しいアルゴリズムを設計する。
EPDA の場合、我々のアルゴリズムは、$mathcalO(|Gamma|2)$ および $ の因子による Alonso et al. (2001) のアルゴリズムよりも空間効率と時間効率が良い。
論文 参考訳（メタデータ） (2023-10-23T18:26:00Z) - High Performance Computing Applied to Logistic Regression: A CPU and GPU
Implementation Comparison [0.0]
汎用GPUによるロジスティック回帰(LR)の並列バージョンを提案する。
我々の実装は、X. Zouらによって提案された並列なグラディエントDescent Logistic Regressionアルゴリズムの直接変換である。
本手法は,画像認識,スパム検出,不正検出などのリアルタイム予測に特に有用である。
論文 参考訳（メタデータ） (2023-08-19T14:49:37Z) - Correct and Optimal: the Regular Expression Inference Challenge [10.899596368151892]
コード/言語モデリングの課題として正規表現推論(REI)を提案する。
私たちはREIのための最初の大規模データセットを作成し、公開します。
論文 参考訳（メタデータ） (2023-08-15T17:40:10Z) - Algorithms for Weighted Pushdown Automata [118.67634716230025]
重み付きプッシュダウンオートマトン(WPDA)は多くの自然言語処理タスクの中核にある。
WPDA上で直接動作する新しいアルゴリズムを開発した。
論文 参考訳（メタデータ） (2022-10-13T10:21:31Z) - Rapid Person Re-Identification via Sub-space Consistency Regularization [51.76876061721556]
Person Re-Identification (ReID) は、歩行者を分離したカメラで識別する。
実値特徴記述子を用いた既存のReID法は精度が高いが、ユークリッド距離計算が遅いため効率が低い。
本稿では,ReID 処理を 0.25 倍高速化するサブスペース一貫性規則化 (SCR) アルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-07-13T02:44:05Z) - Batch-efficient EigenDecomposition for Small and Medium Matrices [65.67315418971688]
EigenDecomposition (ED)は多くのコンピュータビジョンアルゴリズムとアプリケーションの中心にある。
本稿では,コンピュータビジョンの応用シナリオに特化したQRベースのED手法を提案する。
論文 参考訳（メタデータ） (2022-07-09T09:14:12Z) - Efficient GPU implementation of randomized SVD and its applications [17.71779625877989]
行列分解は、次元データの圧縮やディープラーニングアルゴリズムなど、機械学習においてユビキタスである。
行列分解の典型的な解は、計算コストと時間を大幅に増大させる複雑さを持つ。
我々は,計算行列分解の計算負担を軽減するために,現代のグラフィカル処理ユニット(GPU)で並列に動作する効率的な処理操作を利用する。
論文 参考訳（メタデータ） (2021-10-05T07:42:41Z) - Implementation of Parallel Simplified Swarm Optimization in CUDA [2.322689362836168]
最適化コンピューティングでは、インテリジェントなSwarmアルゴリズム(SIAs)が並列化に適している。
本稿では,計算能力と汎用性を考慮したGPUに基づくSimplified Swarm Algorithm Optimization (PSSO)を提案する。
結果から,Nの次数による時間複雑性の低減が達成され,資源プリエンプションの問題は完全に回避された。
論文 参考訳（メタデータ） (2021-10-01T00:15:45Z) - VersaGNN: a Versatile accelerator for Graph neural networks [81.1667080640009]
我々は,超効率的なサイストリックアレイベースの多用途ハードウェアアクセラレータである textitVersaGNN を提案する。
textitVersaGNNは平均3712$times$ speedup with 1301.25$times$ energy reduction on CPU、35.4$times$ speedup with 17.66$times$ energy reduction on GPUを達成している。
論文 参考訳（メタデータ） (2021-05-04T04:10:48Z) - Systolic Computing on GPUs for Productive Performance [2.8064596842326575]
我々は,GPU上で動作する高性能なシストリックアレイを生産的に構築する言語とコンパイラを提案する。
プログラマは、データフローのプロジェクションを線形シストリック配列に指定し、プロジェクションの詳細な実装はコンパイラに任せる。
コンパイラは指定されたプロジェクションを実装し、リニアシストリックアレイをGPUのSIMD実行ユニットとベクトルレジスタにマッピングする。
論文 参考訳（メタデータ） (2020-10-29T18:49:54Z) - Kernel methods through the roof: handling billions of points efficiently [94.31450736250918]
カーネル法は、非パラメトリック学習に対するエレガントで原則化されたアプローチを提供するが、今のところ大規模な問題ではほとんど利用できない。
最近の進歩は、最適化、数値線形代数、ランダム射影など、多くのアルゴリズム的アイデアの利点を示している。
ここでは、これらの取り組みをさらに進めて、GPUハードウェアを最大限に活用する解決器を開発し、テストする。
論文 参考訳（メタデータ） (2020-06-18T08:16:25Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。