Abstract
We consider the polynomial time learnability of finite unions of ordered tree patterns with internal structured variables, in the query learning model of Angluin (1988). An ordered tree pattern with internal structured variables, called a term tree, is a rooted tree pattern which consists of tree structures with ordered children and internal structured variables. A term tree is suited for representing structural features in semistructured or tree structured data such as HTML/XML files. The language L(t) of a term tree t is the set of all trees which are obtained from t by substituting arbitrary trees for all variables in t. Moreover, for a finite set H of term trees, L(H) = ∪ t∈HL(t) . Let H *., which is a target of learning, be a finite set of term trees. An oracle for restricted subset queries answers “yes” for an input set H if L(H)= ⊆ L(H *), and answers “no”, otherwise. An oracle for equivalence queries returns “yes” for an input set H if L(H) = L(H *), and returns a counterexample in L(H)∪L(H *)-L(H)∩L(H *), otherwise. We show that any finite union of languages defined by m term trees is exactly identifiable in polynomial time using at most 2mn 2 restricted subset queries and at most m + 1 equivalence queries, where n is the maximum size of counterexamples.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
S. Abiteboul, P. Buneman, and D. Suciu. Data on the Web: From Relations to Semistructured Data and XML. Morgan Kaufmann, 2000.
T. R. Amoth, P. Cull, and P. Tadepalli. Exact learning of tree patterns from queries and counterexamples. Proc. COLT-98, ACM Press, pages 175–186, 1998.
T. R. Amoth, P. Cull, and P. Tadepalli. Exact learning of unordered tree patterns from queries. Proc. COLT-99, ACM Press, pages 323–332, 1999.
D. Angluin. Finding pattern common to a set of strings. Journal of Computer and System Sciences, 21:46–62, 1980.
D. Angluin. Queries and concept learning. Machine Learning, 2:319–342, 1988.
H. Arimura, H. Ishizaka, and T. Shinohara. Learning unions of tree patterns using queries. Proc. ALT-95, Springer-Verlag, LNAI 997, pages 66–79, 1995.
H. Arimura, H. Sakamoto, and S. Arikawa. Efficient learning of semi-structured data from queries. Proc. ALT-2001, Springer-Verlag, LNAI 2225, pages 315–331, 2001.
H. Arimura, T. Shinohara, and S. Otsuki. Polynomial time algorithm for finding finite unions of tree pattern languages. Proc. NIL-91, Springer-Verlag, LNAI 659, pages 118–131, 1993.
S. Matsumoto, Y. Hayashi, and T. Shoudai. Polynomial time inductive inference of regular term tree languages from positive data. Proc. ALT-97, Springer-Verlag, LNAI 1316, pages 212–227, 1997.
S. Matsumoto and A. Shinohara. Learning pattern languages using queries. Proc. EuroCOLT-97, Springer-Verlag, LNAI 1208, pages 185–197, 1997.
S. Matsumoto, A. Shinohara, H. Arimura, and T. Shinohara. Learning subsequence languages. In Information Modelling and Knowledge Bases VIII, pages 335–344. IOS Press, 1997.
S. Matsumoto, T. Shoudai, T. Miyahara, and T. Uchida. Learning unions of term tree languages using queries. Proceedings of LA Summer Symposium, July 2002, pages 21–1–21–10, 2002.
T. Miyahara, Y. Suzuki, T. Shoudai, T. Uchida, K. Takahashi, and H. Ueda. Discovery of frequent tag tree patterns in semistructured web documents. Proc. PAKDD-2002, Springer-Verlag, LNAI 2336, pages 341–355, 2002.
Y. Suzuki, R. Akanuma, T. Shoudai, T. Miyahara, and T. Uchida. Polynomial time inductive inference of ordered tree patterns with internal structured variables from positive data. Proc. COLT-2002, Springer-Verlag, LNAI 2375, pages 169–184, 2002.
Y. Suzuki, T. Shoudai, T. Miyahara, and T. Uchida. Ordered term tree languages which are polynomial time inductively inferable from positive data. Proc. ALT-2002, Springer-Verlag, LNAI (to appear), 2002.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Matsumoto, S., Shoudai, T., Miyahara, T., Uchida, T. (2002). Learning of Finite Unions of Tree Patterns with Internal Structured Variables from Queries. In: McKay, B., Slaney, J. (eds) AI 2002: Advances in Artificial Intelligence. AI 2002. Lecture Notes in Computer Science(), vol 2557. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-36187-1_46
Download citation
DOI: https://doi.org/10.1007/3-540-36187-1_46
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-00197-3
Online ISBN: 978-3-540-36187-9
eBook Packages: Springer Book Archive