論文の概要: Correct and Optimal: the Regular Expression Inference Challenge
- arxiv url: http://arxiv.org/abs/2308.07899v2
- Date: Fri, 10 May 2024 11:16:19 GMT
- ステータス: 処理完了
- システム内更新日: 2024-05-13 20:46:40.807002
- Title: Correct and Optimal: the Regular Expression Inference Challenge
- Title（参考訳）: 正当性と最適性:正規表現推論問題
- Authors: Mojtaba Valizadeh, Philip John Gorinski, Ignacio Iacobacci, Martin Berger,
- Abstract要約: コード/言語モデリングの課題として正規表現推論(REI)を提案する。
私たちはREIのための最初の大規模データセットを作成し、公開します。
- 参考スコア（独自算出の注目度）: 10.899596368151892
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We propose 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 optimisation 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 $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 $cost(r')<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, with its emphasis on optimisation, 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 regular 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 progress in code/language modelling.
- Abstract（参考訳）: コード/言語モデリングの課題として正規表現推論(REI)を提案する。
REIは教師付き機械学習(ML)およびプログラム最適化タスクであり、例から最小限の正規表現を見つける問題を引き起こす:$P$と$N$の文字列の有限セットとコスト関数$ Cost(\cdot)$が与えられたとき、そのタスクは$P$の全文字列を受け付け、$N$のすべての文字列を拒否する式$r$を生成する。
REIには、課題としてのアドバンテージがあります。
(i)正規表現は、よく知られ、広く使用され、コードの自然な理想化である。
(II)REIの漸近的最悪のケースの複雑さはよく理解されています。
(iii)REIには、容易に理解できるパラメータ(例えば$P$や$N$の濃度、例の文字列長、コスト関数)がいくつかあります。
(4)REIは、最適化に重点を置いており、ディープラーニングベースのMLでは未解決の問題である。
近年,プログラム合成技術を用いたREIソルバがGPU上に実装されている。
これにより、複雑なREIインスタンスに対して、最小限の正規表現を高速に生成できるようになった。
この進歩に基づいて、最初の大規模なREIデータセットを生成し、公開し、いくつかの初期ヒューリスティックおよび機械学習ベースラインを考案し、評価する。
私たちはコミュニティに、REI問題を解決するためのMLメソッドの参加と探索を依頼します。
私たちはREIの進歩が直接コード/言語モデリングの進歩に繋がると信じています。
関連論文リスト
- Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。
我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。
我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
論文 参考訳（メタデータ） (2024-05-10T09:58:47Z) - 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) - Learning to Relax: Setting Solver Parameters Across a Sequence of Linear System Instances [42.16343861129583]
オンライン学習アルゴリズムでは、シーケンス長が増加するにつれて、全体のコストが最高の$omega$に近づくように、一連のインスタンスに対してパラメータを選択できることが示される。
我々の研究は、高精度線形システム解法の最初の学習理論処理と、データ駆動型科学計算のエンドツーエンド保証を提供する。
論文 参考訳（メタデータ） (2023-10-03T17:51:42Z) - CORE: Common Random Reconstruction for Distributed Optimization with
Provable Low Communication Complexity [110.50364486645852]
コミュニケーションの複雑さは、トレーニングをスピードアップし、マシン番号をスケールアップする上で、大きなボトルネックになっています。
本稿では,機械間で送信される情報を圧縮するための共通Om REOmを提案する。
論文 参考訳（メタデータ） (2023-09-23T08:45:27Z) - 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) - Reinforcement Learning with General Utilities: Simpler Variance
Reduction and Large State-Action Space [17.366915676628867]
一般用途における強化学習の課題について考察する。
我々のアルゴリズムは、$tildemathcalO(epsilon-3)$と$tildemathcalO(epsilon-2)$サンプル複雑度を達成する。
論文 参考訳（メタデータ） (2023-06-02T18:16:35Z) - Search-Based Regular Expression Inference on a GPU [0.0]
正規表現推論(REI)は教師付き機械学習とプログラム合成の問題である。
正規表現のコストメトリックと、入力として文字列の正と負の例を取る。
本稿では,任意のアルファベットに対するREIの新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-05-29T19:37:15Z) - Mixability made efficient: Fast online multiclass logistic regression [68.8204255655161]
我々は、混合性は最適な後悔を伴うアルゴリズムを得るための強力なツールであることを示した。
結果として得られる手法は、しばしば計算の複雑さに悩まされ、実用性が低下した。
論文 参考訳（メタデータ） (2021-10-08T08:22:05Z) - Randomized Exploration for Reinforcement Learning with General Value
Function Approximation [122.70803181751135]
本稿では,ランダム化最小二乗値反復(RLSVI)アルゴリズムに着想を得たモデルレス強化学習アルゴリズムを提案する。
提案アルゴリズムは,スカラーノイズを用いたトレーニングデータを簡易に摂動させることにより,探索を促進する。
我々はこの理論を、既知の困難な探査課題にまたがる実証的な評価で補完する。
論文 参考訳（メタデータ） (2021-06-15T02:23:07Z) - Benchmarking Multimodal Regex Synthesis with Complex Structures [45.35689345004124]
自然言語から正規表現(regex)を生成する既存のデータセットは、複雑さに制限されている。
従来のものと異なる新しい合成データセットであるStructuredRegexを3つの側面で紹介する。
論文 参考訳（メタデータ） (2020-05-02T00:16:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。