2018/05/22 by Long Ouyang, Ouyang, Long
Computer Science · #Artificial Intelligence (cs.AI) #FOS: Computer and information sciences #Machine Learning and Algorithms #Machine Learning and Data Classification #Topic Modeling #cs.AI
paper · pdf · doi:10.48550/arxiv.1805.08427
openalex publication_date 2018/05/22 · openalex created_date 2018/06/01 · arxiv created 2018/09/26 · arxiv updated 2018/09/28 · openalex updated_date 2026/07/28
In programming by example, users "write" programs by generating a small number of input-output examples and asking the computer to synthesize consistent programs. We consider a challenging problem in this domain: learning regular expressions (regexes) from positive and negative example strings. This problem is challenging, as (1) user-generated examples may not be informative enough to sufficiently constrain the hypothesis space, and (2) even if user-generated examples are in principle informative, there is still a massive search space to examine. We frame regex induction as the problem of inferring a probabilistic regular grammar and propose an efficient inference approach that uses a novel stochastic process recognition model. This model incrementally "grows" a grammar using positive examples as a scaffold. We show that this approach is competitive with human ability to learn regexes from examples.