-------------------------------------------------------------------------------------- 1) the complete title of one (or more) paper(s) published in the open literature describing the work that the author claims describes a human-competitive result; Inference of Regular Expressions for Text Extraction from Examples IEEE Transactions on Knowledge and Data Engineering, May 2016 Can A Machine Replace Humans In Building Regular Expressions? A Case Study IEEE Intelligent Systems (accepted for publication, to appear) -------------------------------------------------------------------------------------- 2) the name, complete physical mailing address, e-mail address, and phone number of EACH author of EACH paper(s); Alberto Bartoli, bartoli.alberto@univ.trieste.it, +393291899955 Andrea De Lorenzo, mimmuzk25@gmail.com, +393489105896 Eric Medvet, emedvet@units.it, +393283314160 Fabiano Tarlao, ftarlao@gmail.com, +393298479550 The physical mailing address of each author is: "Dipartimento di Ingegneria e Architettura, Università di Trieste - Via Valerio 10 - 34125, Trieste - Italy" -------------------------------------------------------------------------------------- 3) the name of the corresponding author (i.e., the author to whom notices will be sent concerning the competition); Alberto Bartoli -------------------------------------------------------------------------------------- 4) the abstract of the paper(s); (IEEE Transactions on Knowledge and Data Engineering) A large class of entity extraction tasks from text that is either semistructured or fully unstructured may be addressed by regular expressions, because in many practical cases the relevant entities follow an underlying syntactical pattern and this pattern may be described by a regular expression. In this work, we consider the long-standing problem of synthesizing such expressions automatically, based solely on examples of the desired behavior. We present the design and implementation of a system capable of addressing extraction tasks of realistic complexity. Our system is based on an evolutionary procedure carefully tailored to the specific needs of regular expression generation by examples. The procedure executes a search driven by a multiobjective optimization strategy aimed at simultaneously improving multiple performance indexes of candidate solutions while at the same time ensuring an adequate exploration of the huge solution space. We assess our proposal experimentally in great depth, on a number of challenging datasets. The accuracy of the obtained solutions seems to be adequate for practical usage and improves over earlier proposals significantly. Most importantly, our results are highly competitive even with respect to human operators. A prototype is available as a web application at http://regex.inginf.units.it. (IEEE Intelligent Systems) Regular expressions are routinely used in a variety of different application domains. Building a regular expression involves a considerable amount of skill, expertise and creativity. In this work we investigate whether a machine may surrogate these qualities and construct automatically regular expressions for tasks of realistic complexity. We discuss a large scale experiment involving more than 1700 users on 10 challenging tasks. We compared the solutions constructed by these users to those constructed by a tool based on Genetic Programming that we have recently developed and made publicly available. The quality of automatically-constructed solutions turned out to be similar to the quality of those constructed by the most skilled user group; and, the time for automatic construction was similar to the time required by human users. -------------------------------------------------------------------------------------- 5) a list containing one or more of the eight letters (A, B, C, D, E, F, G, or H) that correspond to the criteria (see above) that the author claims that the work satisfies; B, D, E, G, H -------------------------------------------------------------------------------------- 6) a statement stating why the result satisfies the criteria that the contestant claims (see examples of statements of human-competitiveness as a guide to aid in constructing this part of the submission); Our result consists of a method for constructing a regular expression from examples of the desired behavior. The method is based on genetic programming. ---------------------------------- B ("The result is equal to or better than a result that was accepted as a new scientific result at the time when it was published in a peer-reviewed scientific journal.") Our IEEE-TKDE paper includes a detailed experimental evaluation demonstrating that our method improves significantly over 3 baseline methods proposed earlier in the literature and over 73 human operators. Two of the baseline methods were published in peer-reviewed scientific journals: IEEE Transactions on Pattern Analysis and Machine Intelligence in July 2005 (citation #46); IEEE Computer in December 2014 (citation #15; this work was also authored by ours). The third baseline method was published in a primary scientific conference (ACM Programming Languages and Design 2014, citation #33). The baseline published in IEEE Computer, in its turn, improved significantly over two earlier baseline methods published in primary scientific conferences (Empirical Methods on Natural Language Processing EMNLP 2008, #10; ACM Conference on Information Knowledge and Management CIKM 2011, #13). ---------------------------------- D ("The result is publishable in its own right as a new scientific result independent of the fact that the result was mechanically created.") IEEE-TKDE advertises itself as "the most popular flagship journal in the broad, data related areas, including data science, big data, data engineering, data mining, databases and systems, information retrieval and many others" (State of the Journal Editorial, January 2016, https://www.computer.org/csdl/trans/tk/2016/01/07347536.pdf). IEEE-TKDE is concerned only with quality and novelty of the results; not with the nature of the methods used for achieving those results: the fact our method is based on genetic programming is irrelevant. ---------------------------------- E ("The result is equal to or better than the most recent human-created solution to a long-standing problem for which there has been a succession of increasingly better human-created solutions.") There have been in the literature many proposals for inferring regular expressions automatically from examples of the desired behavior (citations #1-#15 discussed in the intro of the IEEE-TKDE paper were proposed in years 1993, 1994, 1998, 2001 and 2005-2010). Only the most recent of those proposals could address non-trivial text extraction tasks. Despite all these attempts, we are not aware of any proposal which used human operators as baseline. Furthermore, our method improved over earlier methods significantly (see criterion B above). ---------------------------------- H (“The result holds its own or wins a regulated competition involving human contestants (in the form of either live human players or human-written computer programs).”) Our IEEE-IS paper describes a large-scale comparison between a tool implementing our method and 1700 (one thousand and seven hundred) users. We wrote a post on Reddit encouraging users to participate in a game consisting in the writing of a regular expression from examples of the desired behavior (http://play.inginf.units.it/). The game consisted of 10 levels, each corresponding to a challenging extraction task, and at the end the participating user was given a score and its percentile rank (e.g., http://play.inginf.units.it/#/end/1437495095612). Our tool delivered solutions with accuracy (F-measure) almost always greater than the accuracy obtained by each category of human users (users were grouped in three self-proclaimed categories: Novice, Intermediate, Expert). Furthermore, the time required by our tool was almost always smaller than the time required by each category of human users. We emphasize that both the users and the tool were given the very same information: examples of the desired behavior without any hint about the structure of the target expression. We also emphasize that we assessed accuracy on a hold-out testing set and on the examples themselves: our tool exhibited better results in both cases. Actual distributions of F-measure indicate that there is a fraction of humans which obtain better results than our tool. In other words, while our tool is not systematically better than humans, it does deliver F-measure that is comparable to humans and that, on average, is even better. Actual distributions of construction time indicate that our tool tends to be systematically faster than most humans on most tasks. We also remark that a preliminary experiment with 73 human operators on 9 tasks is reported in the IEEE-TKDE paper. The results are analogous to those of the large-scale experiment in the IEEE-IS paper. ---------------------------------- G ("The result solves a problem of indisputable difficulty in its field.") In May 2016 web site Stack Overflow, the most popular Question & Answer programming forum, features more than 144,000 questions on this topic with “regex” being the 26-th most popular question tag in a set including more than 44,000 tags. Nearly all of the question tags which are more popular than “regex” refer to a specific programming language or library—“arrays” is the only general tag more popular than “regex”, while “ajax” and “json” are only slightly more popular than “regex” (http://stackoverflow.com/tags). It is thus fair to claim that writing a regular expression tailored to a specific problem requires a considerable amount of skill, expertise and creativity by the programmer. ---------------------------------- 7) a full citation of the paper (that is, author names; publication date; name of journal, conference, technical report, thesis, book, or book chapter; name of editors, if applicable, of the journal or edited book; publisher name; publisher city; page numbers, if applicable); A. Bartoli, A. De Lorenzo, E. Medvet and F. Tarlao, "Inference of Regular Expressions for Text Extraction from Examples," in IEEE Transactions on Knowledge and Data Engineering, vol. 28, no. 5, pp. 1217-1230, May 1 2016. DOI: 10.1109/TKDE.2016.2515587 http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=7374717 A. Bartoli, A. De Lorenzo, E. Medvet and F. Tarlao, "Can A Machine Replace Humans In Building Regular Expressions? A Case Study" in IEEE Intelligent Systems, Accepted for publication, to appear. ---------------------------------- 8) a statement either that "any prize money, if any, is to be divided equally among the co-authors" OR a specific percentage breakdown as to how the prize money, if any, is to be divided among the co-authors; Any prize money, if any, is to be divided equally among the co-authors. ---------------------------------- 9) a statement stating why the judges should consider the entry as "best" in comparison to other entries that may also be "human-competitive;" We have faced a practically relevant problem. Regular expressions are routinely used in a variety of practical applications. Writing a regular expression requires a considerable amount of skill, expertise and creativity (the most popular Question & Answer programming forum features more than 144,000 questions on this topic, with “regex” being the 26-th most popular question tag in a set including more than 44,000 tags). We have faced a long-standing scientific problem. There have been in the literature many proposals for inferring regular expressions automatically, from year 1993 onward. We have provided the first solution capable of addressing practical tasks of realistic complexity. We have demonstrated human-competitiveness with a large-scale experiment involving more than 1700 (one thousand and seven hundred) human users on 10 different tasks. The accuracy of automatically-constructed solutions was similar or better than the accuracy of solutions constructed by the most skilled user group; and, the time for automatic construction was almost always smaller than the time required by human users. We have released a public prototype (http://regex.inginf.units.it) and full source code (https://github.com/MaLeLabTs/RegexGenerator). ---------------------------------- 10) An indication of the general type of genetic or evolutionary computation used, such as GA (genetic algorithms), GP (genetic programming), ES (evolution strategies), EP (evolutionary programming), LCS (learning classifier systems), GE (grammatical evolution), GEP (gene expression programming), DE (differential evolution), etc. GP (genetic programming)