Correct and Optimal: the Regular Expression Inference Challenge

• URL: http://arxiv.org/abs/2308.07899v2
• Date: Fri, 10 May 2024 11:16:19 GMT
• Title: Correct and Optimal: the Regular Expression Inference Challenge
• Authors: Mojtaba Valizadeh, Philip John Gorinski, Ignacio Iacobacci, Martin Berger,
• Abstract summary: We propose regular expression inference (REI) as a challenge for code/language modelling. We generate and publish the first large-scale datasets for REI.
• Score: 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.

Related papers

• Is Reuse All You Need? A Systematic Comparison of Regular Expression Composition Strategies [5.503553586086489]
  Authors: Are composition tasks unique enough to merit dedicated machinery, or is reuse all we need? We collect a novel dataset of composition tasks mined from GitHub and RegExLib. Our evaluation uses multiple dimensions, including a novel metric, to compare reuse-by-example against two synthesis approaches.
  arXiv  Detail & Related papers  (2025-03-26T14:25:27Z)
• $\texttt{SEM-CTRL}$: Semantically Controlled Decoding [53.86639808659575]
  $texttSEM-CTRL$ is a unified approach that enforces rich context-sensitive constraints and task- and instance-specific semantics directly on an LLM decoder. texttSEM-CTRL$ allows small pre-trained LLMs to efficiently outperform larger variants and state-of-the-art reasoning models.
  arXiv  Detail & Related papers  (2025-03-03T18:33:46Z)
• Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
  We consider the problem of learning an $varepsilon$-optimal policy in a general class of continuous-space Markov decision processes (MDPs) having smooth Bellman operators. Key to our solution is a novel projection technique based on ideas from harmonic analysis. Our result bridges the gap between two popular but conflicting perspectives on continuous-space MDPs.
  arXiv  Detail & Related papers  (2024-05-10T09:58:47Z)
• Efficient Frameworks for Generalized Low-Rank Matrix Bandit Problems [61.85150061213987]
  We study the generalized low-rank matrix bandit problem, proposed in citelu2021low under the Generalized Linear Model (GLM) framework. To overcome the computational infeasibility and theoretical restrain of existing algorithms, we first propose the G-ESTT framework. We show that G-ESTT can achieve the $tildeO(sqrt(d_1+d_2)3/2Mr3/2T)$ bound of regret while G-ESTS can achineve the $tildeO
  arXiv  Detail & Related papers  (2024-01-14T14:14:19Z)
• Learning to Relax: Setting Solver Parameters Across a Sequence of Linear System Instances [42.16343861129583]
  We show that a bandit online learning algorithm can select parameters for a sequence of instances such that the overall cost approaches that of the best fixed $omega$ as the sequence length increases. Our work provides the first learning-theoretic treatment of high-precision linear system solvers and the first end-to-end guarantees for data-driven scientific computing.
  arXiv  Detail & Related papers  (2023-10-03T17:51:42Z)
• CORE: Common Random Reconstruction for Distributed Optimization with Provable Low Communication Complexity [110.50364486645852]
  Communication complexity has become a major bottleneck for speeding up training and scaling up machine numbers. We propose Common Om REOm, which can be used to compress information transmitted between machines.
  arXiv  Detail & Related papers  (2023-09-23T08:45:27Z)
• Robust Approximation Algorithms for Non-monotone $k$-Submodular Maximization under a Knapsack Constraint [0.0]
  Two deterministic approximation algorithms are presented for the problem of non-monotone $k$-submodular complexity under a knapsack constraint. Our algorithms provide constant approximation ratios within only $O(nk)$ query complexity for the non-monotone objective.
  arXiv  Detail & Related papers  (2023-09-21T12:42:52Z)
• Re-Reading Improves Reasoning in Large Language Models [87.46256176508376]
  We introduce a simple, yet general and effective prompting method, Re2, to enhance the reasoning capabilities of off-the-shelf Large Language Models (LLMs) Unlike most thought-eliciting prompting methods, such as Chain-of-Thought (CoT), Re2 shifts the focus to the input by processing questions twice, thereby enhancing the understanding process. We evaluate Re2 on extensive reasoning benchmarks across 14 datasets, spanning 112 experiments, to validate its effectiveness and generality.
  arXiv  Detail & Related papers  (2023-09-12T14:36:23Z)
• Reinforcement Learning with General Utilities: Simpler Variance Reduction and Large State-Action Space [17.366915676628867]
  We consider the reinforcement learning problem with general utilities. Our algorithm achieves $tildemathcalO(epsilon-3)$ and $tildemathcalO(epsilon-2)$ sample complexities.
  arXiv  Detail & Related papers  (2023-06-02T18:16:35Z)
• Search-Based Regular Expression Inference on a GPU [0.0]
  Regular expression inference (REI) is a supervised machine learning and program synthesis problem. It takes a cost metric for regular expressions, and positive and negative examples of strings as input. We present a novel algorithm for REI over arbitrary alphabets that is enumerative and trades off time for space.
  arXiv  Detail & Related papers  (2023-05-29T19:37:15Z)
• Mixability made efficient: Fast online multiclass logistic regression [68.8204255655161]
  We show that mixability can be a powerful tool to obtain algorithms with optimal regret. The resulting methods often suffer from high computational complexity which has reduced their practical applicability.
  arXiv  Detail & Related papers  (2021-10-08T08:22:05Z)
• Randomized Exploration for Reinforcement Learning with General Value Function Approximation [122.70803181751135]
  We propose a model-free reinforcement learning algorithm inspired by the popular randomized least squares value iteration (RLSVI) algorithm. Our algorithm drives exploration by simply perturbing the training data with judiciously chosen i.i.d. scalar noises. We complement the theory with an empirical evaluation across known difficult exploration tasks.
  arXiv  Detail & Related papers  (2021-06-15T02:23:07Z)
• Benchmarking Multimodal Regex Synthesis with Complex Structures [45.35689345004124]
  Existing datasets for regular expression (regex) generation from natural language are limited in complexity. We introduce StructuredRegex, a new synthesis dataset differing from prior ones in three aspects.
  arXiv  Detail & Related papers  (2020-05-02T00:16:09Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.