Evaluation of Analysis by Reduction Inference Algorithms

P. Hoffmann (Czech Republic)


machine learning, inductive inference, learning theory, restarting automata, evaluation, undecidability


Inference of an unknown target language based on given input samples plays an important role in artificial intelligence. Usually the input consists just of sample words and the goal is to guess a suitable model (e.g. an automaton or a grammar) that is consistent with the given data. To achieve better inference results, some researchers decided to supply additional information to the learner. Inspired by so-called analysis by reduction (ABR) they supply some hints on how to simplify input words in order to process them iteratively and then they try to infer a model of ABR. Several articles used a very limited approach to evaluating the proposed inference algorithms. Others used a quite advanced grammar-based method able to somehow supply input data enriched with the mentioned simplification hints. The goal of this article is to analyze that grammar-based method, show its drawbacks, prove some theoretical limits of similar methods and propose a new approach to evaluation of algorithms.

Important Links:

Go Back