A GAuGE Approach to Learning DFA from Noisy Samples
Miguel Nicolau, Conor Ryan, Eoin Ryan · Arrow@dit (Dublin Institute of Technology) · 2004
Abstract. This paper describes the adaptation of the GAuGE system to classify binary sequences generated by random DFA. Experiments were conducted, which, although not highly successful, illustrate the potential of applying GAuGE like systems to this problem domain. 1 The Problem The problem was stated as follows. Given a training set of binary sequences, each with a binary class label, the system should generate a predictor that classifies unlabelled sequences in a given test set. The training and test sets consisted of random binary sequences, labelled by a randomly constructed Deterministic Finite Automata (DFA). Each system was allowed to run for 10 minutes. Although the training and test sets were generated by fairly small DFA (10 to 50 states), the training set had a high level of noise (10%): this noise was introduced by mutating each label in the training set with a probability of 0.1. The size of the training sample was also moderate: 1000 instances for data generated by a DFA with 10 states, 2000 for a DFA with 20 states, etc.