A Lower Bound for Learning Distributions Generated by Probabilistic Automata

摘要

Known algorithms for learning PDFA can only be shown to run in time polynomial in the so-called distinguishability μ, of the target machine, besides the number of states and the usual accuracy and confidence parameters. We show that the dependence on μ, is necessary for every algorithm whose structure resembles existing ones. As a technical tool, a new variant of Statistical Queries termed Loo-queries is defined. We show how these queries can be simulated from samples and observe that known PAC algorithms for learning PDFA can be rewritten to access its target using Loo-queries and standard Statistical Queries. Finally, we show a lower bound: every algorithm to learn PDFA using queries with a resonable tolerance needs a number of queries larger than (1/μ)~c for every c < 1.