Abstract
Patterns provide a simple, yet powerful means of describing formal languages. However, for many applications, neither patterns nor their generalized versions of typed patterns are expressive enough. This paper extends the model of (typed) patterns by allowing relations between the variables in a pattern. The resulting formal languages are called Relational Pattern Languages (RPLs). We study the problem of learning RPLs from positive data (text) as well as the membership problem for RPLs. These problems are not solvable or not efficiently solvable in general, but we prove positive results for interesting subproblems.
We further introduce a new model of learning from a restricted pool of potential texts. Probabilistic assumptions on the process that generates words from patterns make the appearance of some words in the text more likely than that of other words. We prove that, in our new model, a large subclass of RPLs can be learned with high confidence, by effectively restricting the set of likely candidate patterns to a finite set after processing a single positive example.
This work was supported by the Natural Sciences and Engineering Research Council of Canada (NSERC).
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
Angluin, D.: Finding patterns common to a set of strings. J. Comput. Syst. Sci. 21, 46–62 (1980)
Angluin, D.: Inductive inference of formal languages from positive data. Inform. Control 45, 117–135 (1980)
Gold, E.M.: Language identification in the limit. Inform. Control 10, 447–474 (1967)
Jiang, T., Kinber, E., Salomaa, A., Salomaa, K., Yu, S.: Pattern languages with and without erasing. Int. J. Comput. Math. 50, 147–163 (1994)
Kearns, M., Pitt, L.: A polynomial-time algorithm for learning k-variable pattern languages from examples. In: COLT, pp. 57–71 (1989)
Koshiba, T.: Typed pattern languages and their learnability. In: Vitányi, P.M.B. (ed.) EuroCOLT 1995. LNCS, vol. 904, pp. 367–379. Springer, Heidelberg (1995)
Lange, S.: Algorithmic learning of recursive languages. Habilitationsschrift, University of Leipzig (2000)
Lange, S., Zeugmann, T.: Incremental learning from positive data. J. Comput. Syst. Sci. 53, 88–103 (1996)
Lange, S., Zeugmann, T., Zilles, S.: Learning indexed families of recursive languages from positive data: A survey. Theor. Comput. Sci. 397, 194–232 (2008)
Reidenbach, D.: Discontinuities in pattern inference. Theor. Comput. Sci. 397, 166–193 (2008)
Reischuk, R., Zeugmann, T.: An average-case optimal one-variable pattern language learner. J. Comput. Syst. Sci. 60, 302–335 (2000)
Rossmanith, P., Zeugmann, T.: Stochastic finite learning of the pattern languages. Mach. Learn. 44, 67–91 (2001)
Shinohara, T.: Polynomial time inference of extended regular pattern languages. In: Goto, E., Furukawa, K., Nakajima, R., Nakata, I., Yonezawa, A. (eds.) RIMS 1982. LNCS, vol. 147, pp. 115–127. Springer, Heidelberg (1983)
Wiehagen, R.: Limes-Erkennung rekursiver Funktionen durch spezielle Strategien. Elektronische Informationsverarbeitung und Kybernetik 12, 93–99 (1976)
Wright, K.: Identification of unions of languages drawn from an identifiable class. In: COLT, pp. 328–333 (1989)
Wright, K.: Inductive identification of pattern languages with restricted substitutions. In: COLT, pp. 111–121 (1990)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Geilke, M., Zilles, S. (2011). Learning Relational Patterns. In: Kivinen, J., Szepesvári, C., Ukkonen, E., Zeugmann, T. (eds) Algorithmic Learning Theory. ALT 2011. Lecture Notes in Computer Science(), vol 6925. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-24412-4_10
Download citation
DOI: https://doi.org/10.1007/978-3-642-24412-4_10
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-24411-7
Online ISBN: 978-3-642-24412-4
eBook Packages: Computer ScienceComputer Science (R0)