Authors: Peter Rossmanith and Thomas Zeugmann
This main result is achieved by providing a new and improved average-case analysis of the Lange-Wiehagen (1991) algorithm learning the class of all pattern languages in the limit from positive data. The complexity measure chosen is the total learning time, i.e., the overall time taken by the algorithm until convergence. The expectation of the total learning time is carefully analyzed and exponentially shrinking tail bounds for it are established for a large class of probability distributions. For every pattern p containing k different variables it is shown that Lange and Wiehagen's algorithm possesses an expected total learning time of O(akE[L]log1/b(k)), where a and b are two easily computable parameters arising naturally from the underlying probability distributions, and E[L] is the expected example string length.
Finally, assuming a bit of domain knowledge concerning the underlying class of probability distributions, it is shown how to convert learning in the limit into stochastic finite learning.
©Copyright 2001 Kluwer Academic Publishers.