Abstract
Efficient learnability using the state merging algorithm is known for a subclass of probabilistic automata termed μ-distinguishable. In this paper, we prove that state merging algorithms can be extended to efficiently learn a larger class of automata. In particular, we show learnability of a subclass which we call μ 2-distinguishable. Using an analog of the Myhill-Nerode theorem for probabilistic automata, we analyze μ-distinguishability and generalize it to μ p -distinguishability. By combining new results from property testing with the state merging algorithm we obtain KL-PAC learnability of the new automata class.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Batu, T., Fortnow, L., Rubinfeld, R., Smith, W.D., White, P.: Testing that distributions are close. In: Proc. 41st Annu. IEEE Sympos. Found. Comput. Sci. (FOCS), pp. 259–269. IEEE Computer Society, Los Alamitos (2000)
Carrasco, R.C., Oncina, J.: Learning deterministic regular grammars from stochastic samples in polynomial time. Theoret. Inform. and Appl. 33(1), 1–20 (1999)
Clark, A., Thollard, F.: PAC-learnability of probabilistic deterministic finite state automata. Journal of Machine Learning Research 5, 473–497 (2004)
Cover, T., Thomas, J.: Elements of Information Theory. Wiley, Chichester (1991)
Hopcroft, J.E., Ullman, J.D.: Introduction to Automata Theory, Languages and Computation, 1st edn. Addison-Wesley, Reading (1979)
Kearns, M.: Efficient noise-tolerant learning from statistical queries. In: Proc. 25th Annu. ACM Sympos. Theory Comput (STOC), pp. 392–401. ACM Press, New York (1993)
Kearns, M., Mansour, Y., Ron, D., Rubinfeld, R., Schapire, R., Sellie, L.: On the learnability of discrete distributions. In: Proc. 26th Annu. ACM Sympos. Theory Comput (STOC), pp. 273–282 (1994)
Murphy, K.: Passively learning finite automata. Technical report, Santa Fe Institute (1996)
Ron, D.: Property testing. In: Rajasekaran, S., Pardalos, P., Reif, J., Rolim, J. (eds.) Handbook of Randomized Computing, vol. II, pp. 597–649. Kluwer Academic, Dordrecht (2001)
Ron, D., Singer, Y., Tishby, N.: On the learnability and usage of acyclic probabilistic finite automata. In: Proc. 8th Annu. Conf. on Comput. Learning Theory, pp. 31–40. ACM Press, New York (1995)
Vidal, E., Thollard, F., de la Higuera, C., Casacuberta, F., Carrasco, R.C.: Probabilistic finite-state machines – Part I. IEEE Trans. Pattern Anal. Mach. Intell. (2005a) (to appear)
Vidal, E., Thollard, F., de la Higuera, C., Casacuberta, F., Carrasco, R.C.: Probabilistic finite-state machines – Part II. IEEE Trans. Pattern Anal. Mach. Intell. (2005b) (to appear)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Guttman, O., Vishwanathan, S.V.N., Williamson, R.C. (2005). Learnability of Probabilistic Automata via Oracles. In: Jain, S., Simon, H.U., Tomita, E. (eds) Algorithmic Learning Theory. ALT 2005. Lecture Notes in Computer Science(), vol 3734. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11564089_15
Download citation
DOI: https://doi.org/10.1007/11564089_15
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-29242-5
Online ISBN: 978-3-540-31696-1
eBook Packages: Computer ScienceComputer Science (R0)