論文の概要: The Regular Expression Inference Challenge
- arxiv url: http://arxiv.org/abs/2308.07899v1
- Date: Tue, 15 Aug 2023 17:40:10 GMT
- ステータス: 処理完了
- システム内更新日: 2023-08-16 11:53:32.771364
- Title: The Regular Expression Inference Challenge
- Title(参考訳): 正規表現推論チャレンジ
- Authors: Mojtaba Valizadeh, Philip John Gorinski, Ignacio Iacobacci, Martin
Berger
- Abstract要約: コード/言語モデリングの課題として,表現型推論(REI)を提案する。
REIは教師付き機械学習(ML)とプログラム合成タスクであり、例から最小限の正規表現を見つけるという問題を引き起こす。
- 参考スコア(独自算出の注目度): 11.907026010541674
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We propose \emph{regular expression inference (REI)} as a challenge for
code/language modelling, and the wider machine learning community. REI is a
supervised machine learning (ML) and program synthesis task, and poses the
problem of finding minimal regular expressions from examples: Given two finite
sets of strings $P$ and $N$ and a cost function $\text{cost}(\cdot)$, the task
is to generate an expression $r$ that accepts all strings in $P$ and rejects
all strings in $N$, while no other such expression $r'$ exists with
$\text{cost}(r')<\text{cost}(r)$.
REI has advantages as a challenge problem: (i) regular expressions are
well-known, widely used, and a natural idealisation of code; (ii) REI's
asymptotic worst-case complexity is well understood; (iii) REI has a small
number of easy to understand parameters (e.g.~$P$ or $N$ cardinality, string
lengths of examples, or the cost function); this lets us easily finetune
REI-hardness; (iv) REI is an unsolved problem for deep learning based ML.
Recently, an REI solver was implemented on GPUs, using program synthesis
techniques. This enabled, for the first time, fast generation of minimal
expressions for complex REI instances. Building on this advance, we generate
and publish the first large-scale datasets for REI, and devise and evaluate
several initial heuristic and machine learning baselines.
We invite the community to participate and explore ML methods that learn to
solve REI problems. We believe that progress in REI directly translates to
code/language modelling.
- Abstract(参考訳): 我々は、コード/言語モデリングの課題として、およびより広い機械学習コミュニティとして、 \emph{regular expression inference (rei)を提案する。
REIは教師付き機械学習(ML)とプログラム合成タスクであり、例から最小限の正規表現を見つける問題である: 2つの文字列の有限集合$P$と$N$とコスト関数$\text{cost}(\cdot)$が与えられたとき、そのタスクは、$P$のすべての文字列を受け入れて$N$のすべての文字列を拒否する式$r$を生成することであり、他のどの式$r'$も$\text{cost}(r')<\text{cost}(r)$と共に存在する。
reiには課題として利点があります
(i)正規表現は、よく知られ、広く使用され、コードの自然な理想化である。
(II)REIの漸近的最悪のケースの複雑さはよく理解されている。
(iii)reiは、簡単なパラメータ(例えば、$p$または$n$の基数、例の文字列長、コスト関数など)を少数持っているので、これにより、レイハードネスを簡単に微調整することができます。
(iv)REIはディープラーニングベースのMLの未解決問題である。
近年,プログラム合成技術を用いたREIソルバがGPU上に実装されている。
これにより、複雑なREIインスタンス用の最小限の式を、初めて高速に生成できるようになった。
この進歩に基づいて、最初の大規模なREIデータセットを生成し、公開し、いくつかの初期ヒューリスティックおよび機械学習ベースラインを考案し、評価する。
私たちはコミュニティに、REI問題を解決するためのMLメソッドの参加と探索を依頼します。
私たちはREIの進歩が直接コード/言語モデリングに翻訳されると考えている。
関連論文リスト
- Linear-time Minimum Bayes Risk Decoding with Reference Aggregation [61.63208012250885]
最小ベイズリスク(MBR、Minimum Bayes Risk)は、機械翻訳の品質向上を図ったテキスト生成技術である。
これは2次複雑性を持つ実用計量のペアワイズ計算を必要とする。
本稿では,集約された参照表現に対して計算したスコアを用いて,ペアワイズメトリックスコアを近似する。
論文 参考訳(メタデータ) (2024-02-06T18:59:30Z) - Efficient Frameworks for Generalized Low-Rank Matrix Bandit Problems [61.85150061213987]
一般化線形モデル (GLM) フレームワークを用いて, citelu2021low で提案した一般化低ランク行列帯域問題について検討する。
既存のアルゴリズムの計算不可能性と理論的制約を克服するため,まずG-ESTTフレームワークを提案する。
G-ESTT は $tildeO(sqrt(d_1+d_2)3/2Mr3/2T)$ bound of regret を達成でき、G-ESTS は $tildeO を達成できることを示す。
論文 参考訳(メタデータ) (2024-01-14T14:14:19Z) - Robust Approximation Algorithms for Non-monotone $k$-Submodular
Maximization under a Knapsack Constraint [0.0]
2つの決定論的近似アルゴリズムは、knapsack制約の下での非単調な$k$-部分モジュラー複雑性の問題に対して提案される。
提案アルゴリズムは,非単調な目的に対して,O(nk)$クエリの計算量内で一定の近似比を提供する。
論文 参考訳(メタデータ) (2023-09-21T12:42:52Z) - Re-Reading Improves Reasoning in Large Language Models [91.96027668854406]
既成のLarge Language Models (LLM) の推論能力を高めるため, 単純で汎用的で効果的なプロンプト手法であるRe2を導入する。
CoT (Chain-of-Thought) など、ほとんどの思考を刺激する手法とは異なり、Re2 は質問を2回処理することで入力に焦点を移し、理解プロセスを強化する。
提案手法の有効性と汎用性を検証するため,14のデータセットにまたがる広範囲な推論ベンチマークでRe2を評価した。
論文 参考訳(メタデータ) (2023-09-12T14:36:23Z) - 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) - Replicability in Reinforcement Learning [46.89386344741442]
生成モデルにアクセス可能なディスカウント型MDPの基本設定に焦点をあてる。
ImpagliazzoらにインスパイアされたRLアルゴリズムは、高い確率で2回の実行後に全く同じポリシーを出力した場合、複製可能である。
論文 参考訳(メタデータ) (2023-05-31T05:16:23Z) - Search-Based Regular Expression Inference on a GPU [0.0]
正規表現推論(REI)は教師付き機械学習とプログラム合成の問題である。
正規表現のコストメトリックと、入力として文字列の正と負の例を取る。
本稿では,任意のアルファベットに対するREIの新しいアルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-05-29T19:37:15Z) - Robust Empirical Risk Minimization with Tolerance [24.434720137937756]
我々は、(ロバストな)$textitempirical risk minimization$(RERM)の基本パラダイムについて研究する。
自然寛容なRERMは、$mathbbRd$を超える$gamma$-tolerantな学習VCクラスに十分であることを示す。
論文 参考訳(メタデータ) (2022-10-02T21:26:15Z) - RNNs can generate bounded hierarchical languages with optimal memory [113.73133308478612]
RNNは、自然言語構文の足場を反映した境界階層言語を効率的に生成できることを示す。
Dyck-($k$,$m$)は、よくネストされた括弧($k$型)と$m$バウンドされたネスト深さの言語である。
明示的な構成により,$O(m log k)$ hidden units の RNN がメモリの指数的削減に十分であることを示す。
論文 参考訳(メタデータ) (2020-10-15T04:42:29Z) - Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample
Complexity [59.34067736545355]
S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。
十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
論文 参考訳(メタデータ) (2020-06-06T13:34:41Z) - Benchmarking Multimodal Regex Synthesis with Complex Structures [45.35689345004124]
自然言語から正規表現(regex)を生成する既存のデータセットは、複雑さに制限されている。
従来のものと異なる新しい合成データセットであるStructuredRegexを3つの側面で紹介する。
論文 参考訳(メタデータ) (2020-05-02T00:16:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。