The ZULU Competition
https://labh-curien.univ-st-etienne.fr/zulu/
Supported by Pascal 2 Network of Excellence
Abstract:
Zulu is an active learning competition. Participants are to build algorithms that can learn deterministic finite automata (DFA) by making the smallest number of membership queries to the server/oracle.
Motivations:
When learning language models, techniques usually make use of huge corpora that are unavailable in many less resourced languages (such as the Zulu language). One possible way around this problem is to interrogate an expert with a number of chosen queries, in an interactive mode, until a satisfying language model is reached. In this case, an important indicator of success is the amount of energy the expert has spent in order for
learning to be successful. A nice learning paradigm covering this situation is that of Query Learning, introduced by Dana Angluin.
In the field of Grammatical Inference, Query Learning was thoroughly investigated to learn deterministic finite automata (DFA). As negative results, it was proved that DFA could not be learned from just a polynomial number of membership queries nor from just a polynomial number of strong equivalence queries. On the other hand, algorithm L* designed by Angluin, was proved to learn DFA from a polynomial number of both membership and equivalence queries. These results yield several successfull applications in Robotics, Games and Agents Technologies, Information Retrieval, Hardware and Software Verification.
However, what has not been hardly studied is how to optimise the learning task by trying to minimize the number of queries while making queries for which the Oracle's work and answers are simple. These are strong motivations for stemming research in the direction of developing new interactive learning strategies and algorithms, that is the aim of this competition.
The competition:
Zulu (https://labh-curien.univ-st-etienne.fr/zulu/) is both a web based platform simulating an Oracle in a DFA learning task and a competition.
As a web platform, Zulu allows users to generate tasks, to interact with the Oracle in learning sessions and to record the results of the users. It provides the users with a baseline algorithm written in JAVA, or the elements allowing to build from scratch a new learning algorithm capable of interacting with the server.
The server can be accessed by any user/learner who has opened an account. The server acts as an Oracle for membership queries. A player can log inand ask for a target DFA. The server then computes how many queries itneeds to learn a reasonable machine (reasonable means less than 30% classification errors), and invites the player to interact in a learning session in which he can ask up to that number of queries.
At the end of the learning process the server gives the learner a set of unlabelled strings (a test set). The labels the learner submits are used to compute his score.
As a starting point the baseline algorithm, which is a simple variation of L*, with some sampling done to simulate equivalence queries, is given to the user, who can therefore play with some simple JAVA code for a start.
The competition itself will be held in the spring of 2010 and the results will be presented during a special session at the International Colloquium on Grammatical Inference in Valencia, Spain, September 13-16, 2010(https://users.dsic.upv.es/workshops/icgi2010/)
Schedule:
- from now to March 1st, 2010: Zulu platform is open, anyone may
register and have fun
- March 1st: Official beginning of the competition
- May 15th: Deadline for scoring, submissions closed
- June 1st: Notifications of the results
- June 20th: Deadline for submission of abstracts explaining participants strategies
- September 13-16th: workshop at ICGI
Prizes and publications:
The winner of the Zulu competition will receive a prize, to be announced
on the Zulu webpage. Participants are encouraged to present their
innovations either as full papers to the ICGI 2010 conference, or as
extended abstracts to the Zulu workshop that will be organised during
ICGI. A journal special issue will also be considered.
Scientific committee:
* Dana Angluin, Yale University, USA
* Leo Becerra Bonache, Universidad de Tarragona, Spain
* François Coste, IRISA, Rennes, France
* Alex Clark, Royal Holloway University of London, UK
* Ricard Gavalda, Universidad Politecnica de Barcelona, Spain
* Colin de la Higuera, University of Nantes, France
* Jean-Christophe Janodet, University of Lyon, France
* Aurelien Lemay, University of Lille, France
* Laurent Miclet, ENSAT Lannion and IRISA, France
* Tim Oates, University of Maryland, USA
* Anssi Yli Jyra, University of Helsinki, Finland
* Menno van Zaanen, Tilburg University, The Netherlands
