Random DFA's can be approximately learned from sparse uniform examples

ABSTRACT

Approximate inference of finite state machines from sparse labeled examples has been proved NP-hard when an adversary chooses the target machine and the training set [Ang78, KV89, PW89]. We have, however, empirically found that DFA's are approximately learnable from sparse data when the target machine and training set are selected at random.

REFERENCES

• Ang78: D. Angluin. (1978) On the Complexity of Minimum Inference of Regular Sets. Information and Control, Vol. 39, pp. 337-350.
• KV89: M. Kearns , L. G. Valiant, Crytographic limitations on learning Boolean formulae and finite automata, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.433-444, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73049]
• PM88: S. K. Park , K. W. Miller, Random number generators: good ones are hard to find, Communications of the ACM, v.31 n.10, p.1192-1201, Oct. 1988 [doi>10.1145/63039.63042]
• PW89: L. Pitt , M. K. Warmuth, The minimum consistent DFA problem cannot be approximated within and polynomial, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.421-432, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73048]
• TB73: B. Trakhtenbrot and Ya. Barzdin'. (1973) Finite Automata: Behavior and Synthesis. North-Holland Publishing Company, Amsterdam.
• V78: L. Veelenturf. (1978) Inference of Sequential Machines from Sample Computations. IEEE Transactions on Computers, Vol. 27, pp. 167-170.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES

Additional Classification:
  G. Mathematics of Computing

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE

General Terms:
Algorithms, Measurement, Performance, Theory