Abbadingo One: DFA Learning Competition

The Abbadingo One competition is over. Plans are being made for Abbadingo 2, with new sorts of problems.

A test version of a follow-on to Abbadingo One (but not Abbadingo Two, which will be different) called Gowachin, is now available for your grammar learning pleasure.

Meanwhile, here is a forthcoming paper describing the outcome of the first competition, which will appear in the volume of Springer-Verlag's Lecture Notes in Computer Science containing the proceedings of ICGI-98. And here is an expanded version of the ICGI-98 paper, currently in review by a journal. And here is code for 4 DFA learning algorithms, including 3 versions of Rodney Price's EDSM idea. These 3 programs can solve Abbadingo problems 1, 2, 3, R, 4, 6, and S.

High-Level Executive Summary

This research competition is based on grammar induction, a difficult problem in machine learning. The winners will receive scientific admiration, one thousand twenty four dollars, guest of honor status at a formal award ceremony, and more.

Recent News

Nov 15

The competition is over. Congratulations to the winners Rod Price and Hugues Juille!

Jul 14

Hugues Juille solves problem 7, thereby proving that the rightmost column is not impossible!

Jun 8

Problem 6 has fallen.

May 16

Rod Price nails problem S!

May 15

Problem R has fallen.

May 6

Problem 3 has fallen.

Mar 31

Problem 5 has fallen.

Mar 19

Problem 2 has fallen.

Mar 18

We have adopted a 2-dimensional partial ordering for the benchmark problems that makes more sense given that the problems are layed out on a 2-dimensional grid. We can now not only measure, but also reward progress in both of the two directions that we care about, namely towards larger target concepts and towards sparser training data. This change has the side effect of allowing multiple winners if people produce algorithms that excel in different ways.

Mar 14

Problem 4 has fallen.

Mar 10

Problem 1 has fallen.

Mar 7

Abbadingo One competition begins.

Description

• There are 16 benchmark problems. Each problem consists of a secret randomly generated DFA which serves as a target concept, a set of training strings which have been labeled by that target concept, and a set of unlabeled testing strings.

• The task is to predict the labels that the target concept would assign to the testing strings. Each problem will be considered solved by the first person to demonstrate to us a test set error rate of 1% or less.

• The problems are ranked according to two factors that affect their difficulty: the size of the target concept and the sparsity of the training data. The winners of the competition will the first participants to solve problems that aren't easier than problems solved by other participants before the end of the competition, where ``easier'' is measured on a two-dimensional dominance lattice. Because some pairs of problems are of incomparable difficulty, the competition might end up with multiple winners. We will be happy to reward multiple algorithms that excel in different ways.

• We will not disclose any test set answers during the competition. Instead we provide the Abbadingo Oracle which can recognize sufficiently accurate submissions.

• The output of the oracle is either PASS or FAIL.

• When the Oracle declares a test set labeling to be a valid solution, the competitor must contact the Abbadingo administrators in order to receive official credit. Before awarding official credit the administrators will manually verify the correctness and priority of the labeling. Even though the automatic Oracle is not empowered to give official credit, participants are required to obtain its permission before submitting proposed solutions to the competition administrators.

• The competition ends on (7:00 pm GMT, Nov. 15, 1997)

• The 16 benchmark problems include 4 problems that we already know how to solve, and hence are for practice purposes only, and 12 official challenge problems.

So far nine of the twelve challenge problems have been solved. Solved problems are noted in the data sets page, which has pointers to the data sets along with a table of the problems, their current status, and some numbers relating to their difficulty.

This competition was inspired by a call for good benchmark tasks during the AAAI-96 Fall Symposium on Learning Complex Behaviors in Adaptive Intelligent Systems. It is being organized and administered by Kevin J. Lang and Barak A. Pearlmutter.

Details and Clarifications

Sponsors

• The Computer Science Department at the University of New Mexico, which provided the Abbadingo server.

• The prestigious Kluwer Academic journal Machine Learning, which promised to give priority treatment to a paper describing the award winning algorithm.

• The Santa Fe Institute.

• The Journal of Artificial Intelligence Research.

• Private individuals who have contributed to the award fund. Some of them may be listed here in the future.

The Fine Print

Intellectual Property: We make no claims on the intellectual property of competition participants.
Money: All donated funds will be used solely for awards and reimbursing the award ceremony travel expenses of award winners. If there is any prize money left over after the competition it will be returned to the sponsors, unless they'd prefer that it be rolled over into Abbadingo Two.
Void Where Prohibited: Participants must obey all laws and regulations that apply to them. If anyone's government or employer prohibits them from participating in this competition or from claiming an award, then they must not do so. Similarly, winners are responsible for paying any taxes that might be required.
General Disclaimer: The organizers and administrators of the Abbadingo competition (Kevin J. Lang and Barak A. Pearlmutter) reserve the right to change the competition in any way at any time at their sole discretion, without notice, including the right to change the rules, problems, and awards, and the right to terminate the competition. The Abbadingo administrators are the sole arbiters for this competition, and their judgment is final in all matters.
Eligibility: The administrators and their immediate relatives and immediate co-workers are not eligible for any award.