----- Entry for the 2008 "Humies" Awards for Human-Competitive Results -----
----------------------------------------------------------------------------
(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:
"Genetic Programming for Finite Algebras"
----------------------------------------------------------------------------
(2) the name, complete physical mailing address, e-mail address, and phone number of EACH author of EACH paper:
Lee Spector
Cognitive Science
Hampshire College
Amherst, MA 01002
lspector@hampshire.edu
413-559-5352 or 413-584-8742
David M. Clark
Mathematics
SUNY New Paltz
New Paltz, NY 12561
clarkd@newpaltz.edu
845-257-3524
Ian Lindsay
Box 987
Hampshire College
Amherst, MA 01002
iml04@hampshire.edu
413-559-4528
Bradford Barr
Box 538
Hampshire College
Amherst, MA 01002
bradford.barr@gmail.com
413-559-4563
Jon Klein
Cognitive Science
Hampshire College
Amherst, MA 01002
jk@artificial.com
617-216-3890
----------------------------------------------------------------------------
(3) the name of the corresponding author (i.e., the author to whom notices will be sent concerning the competition):
Lee Spector
----------------------------------------------------------------------------
(4) the abstract of the paper(s):
We describe the application of genetic programming (GP) to a problem in pure mathematics, in the study of finite algebras. We document the production of human-competitive results in the discovery of particular algebraic terms, namely discriminator, Pixley, majority and Mal'cev terms, showing that GP can exceed the performance of every prior method of finding these terms in either time or size by several orders of magnitude. Our terms were produced using the ECJ and PushGP genetic programming systems in a variety of configurations. We compare the results of GP to those of exhaustive search, random search, and algebraic methods.
----------------------------------------------------------------------------
(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, F, G
----------------------------------------------------------------------------
(6) a statement stating why the result satisfies the criteria that the contestant claims:
Since the discoveries of the significance of Mal'cev functions in 1954, Pixley functions in 1963, the discriminator function in 1970, and majority functions in 1975, there has been a keen interest among algebraists to find terms that represent these functions on individual algebras. Two approaches embody the most effective methods previously developed for finding these terms. The first is uninformed search, of which we explored two variants: exhaustive search, in which terms are enumerated systematically from smallest to largest, and random search, in which terms within a range of sizes are generated in random order. Exhaustive search is guaranteed to produce a smallest term of the required type if such a term exists, but it has the disadvantage of requiring astronomical amounts of time, except for the very smallest algebras or the very simplest terms. Random search has the same abysmal performance but without any guarantees concerning size or success. The second approach is construction via the primality theorem, which gives the most time efficient method known to describe these terms that applies to any primal algebra. But it has the disadvantage that, except for the very smallest algebras, the terms it produces have astronomical length.
We have used GP to significantly expand the range of finite algebras for which we can produce, within a few hours, terms that can be written on a few lines. We have exhibited examples of such algebras for which these terms would require many orders of magnitude more time to find by exhaustive or random search and many orders of magnitude more space to write down the terms produced by the primality theorem. In this respect we have established that GP has surpassed, by a considerable margin, all known methods of generating practical terms for these algebras. Because there were no prior methods for generating practical terms in practical amounts of time, GP has provided the first solution to a previously open problem in the field.
The following five criteria for human-competitive performance are satisfied by our results:
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.
D: The result is publishable in its own right as a new scientific result independent of the fact that the result was mechanically created.
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.
F: The result is equal to or better than a result that was considered an achievement in its field at the time it was first discovered.
G: The result solves a problem of indisputable difficulty in its field.
----------------------------------------------------------------------------
(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);
Spector, Lee, Clark, David M., Lindsay, Ian, Barr, Bradford, and Klein, Jon. (2008). Genetic Programming for Finite Algebras. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO), edited by Maarten Keijzer et al. ACM Press. In press.
----------------------------------------------------------------------------
(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 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."
The results in this entry demonstrate not only that GP can be competitive with human experts, but also that it can outperform humans and all other known methods on significant problems. GP here provides benefits of several orders of magnitude with respect to the most relevant metrics (search speed and solution size). Furthermore, the presented results are in an area of pure mathematics with a long history and many outstanding problems that are linked to applications across the sciences. This entry may be "best," therefore, because it not only presents work that is both human-competitive and human-surpassing, but because it may also help to facilitate the use of evolutionary methods in a foundational area of mathematics that underlies research in many disciplines.