Fugu-MT 論文翻訳(概要): The Regular Expression Inference Challenge

論文の概要: 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の進歩が直接コード/言語モデリングに翻訳されると考えている。

関連論文リスト

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 [87.46256176508376]
既成の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)

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

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