IEICE Transactions on Information and Systems

IEICE Transactions on Information and Systems 2008 E91-D(2):222-230; doi:10.1093/ietisy/e91-d.2.222

This Article Abstract Full Text (PDF) Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Add to My Personal Archive Download to citation manager Request Permissions Google Scholar Articles by MATSUMOTO, S. Articles by SUZUKI, Y. Search for Related Content Social Bookmarking          What's this?

Copyright © 2008 The Institute of Electronics, Information and Communication Engineers

Special Section on Foundations of Computer Science -- Papers -- Algorithmic Learning Theory

Learning of Finite Unions of Tree Patterns with Internal Structured Variables from Queries

Satoshi MATSUMOTO¹, Takayoshi SHOUDAI², Tomoyuki UCHIDA³, Tetsuhiro MIYAHARA³ and Yusuke SUZUKI³

¹ The author is with the Department of Mathematical Sciences, Tokai University, Hiratsuka-shi, 259–1292 Japan. E-mail: matumoto{at}ss.u-tokai.ac.jp, ² The author is with the Department of Informatics, Kyushu University, Fukuoka-shi, 819–0395 Japan., ³ The authors are with the Graduate School of Information Sciences, Hiroshima City University, Hiroshima-shi, 731–3194 Japan.

A linear term tree is defined as an edge-labeled rooted tree pattern with ordered children and internal structured variables whose labels are mutually distinct. A variable can be replaced with arbitrary edge-labeled rooted ordered trees. We consider the polynomial time learnability of finite unions of linear term trees in the exact learning model formalized by Angluin. The language L(t) of a linear term tree t is the set of all trees obtained from t by substituting arbitrary edge-labeled rooted ordered trees for all variables in t. Moreover, for a finite set S of linear term trees, we define L(S) = _tSL(t). A target of learning, denoted by _*, is a finite set of linear term trees, where the number of edge labels is infinite. In this paper, for any set _* of m linear term trees (m 0), we present a query learning algorithm which exactly identifies _* in polynomial time using at most 2mn² Restricted Subset queries and at most m + 1 Equivalence queries, where n is the maximum size of counterexamples. Finally, we note that finite sets of linear term trees are not learnable in polynomial time using Restricted Equivalence, Membership and Subset queries.

Key Words: exact learning, computational learning theory, finite union of tree pattern languages

---

Manuscript received March 30, 2007. Manuscript revised June 30, 2007.

Reference

[1] T.R. Amoth, P. Cull, and P. Tadepalli, "Exact learning of tree patterns from queries and counterexamples," Proc. COLT-98, pp.175–186, ACM Press, 1998.

[2] T.R. Amoth, P. Cull, and P. Tadepalli, "On exact learning of unordered tree patterns," Mach. Learn., vol.44, pp.211–243, 2001.

[3] D. Angluin, "Finding pattern common to a set of strings," J. Comput. Syst. Sci., vol.21, pp.46–62, 1980.

[4] D. Angluin, "Queries and concept learning," Mach. Learn., vol.2, pp.319–342, 1988.

[5] H. Arimura, H. Ishizaka, and T. Shinohara, "Learning unions of tree patterns using queries," Theor. Comput. Sci., vol.185, pp.47–62, 1997.

[6] H. Arimura, H. Sakamoto, and S. Arikawa, "Efficient learning of semi-structured data from queries," Proc. ALT-2001, LNAI 2225, pp.315–331, Springer-Verlag, 2001.

[7] H. Arimura, T. Shinohara, and S. Otsuki, "Polynomial time algorithm for finding finite unions of tree pattern languages," Proc. NIL-91, LNAI 659, pp.118–131, Springer-Verlag, 1993.

[8] H. Hirashima, Y. Suzuki, S. Matsumoto, T. Uchida, and Y. Nakamura, "Polynomial time inductive inference of unions of two term tree languages," Proc. ILP-2006, (Short Papers) The University of Corunna, UDC Press service, 2006.

[9] L. Lovász, Combinatorial Problems and Exercises, chapter Two classical enumeration problems in graph theory, North-Holland Publishing Company, 1979.

[10] S. Matsumoto and A. Shinohara, "Learning pattern languages using queries," Proc. EuroCOLT-97, LNAI 1208, pp.185–197, Springer-Verlag, 1997.

[11] S. Matsumoto, A. Shinohara, H. Arimura, and T. Shinohara, "Learning subsequence languages," in Information Modelling and Knowledge Bases VIII, pp.335–344, IOS Press, 1997.

[12] S. Matsumoto, T. Shoudai, T. Miyahara, and T. Uchida, "Learning unions of term tree languages using queries," Proc. LA Summer Symposium, pp.21-1–21-10, July 2002.

[13] S. Matsumoto, Y. Suzuki, T. Shoudai, T. Miyahara, and T. Uchida, "Learning of finite unions of tree patterns with repeated internal structured variables from queries," Proc. ALT-2003, LNAI 2842, pp.144–158, Springer-Verlag, 2003.

[14] 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, LNAI 2336, pp.341–355, Springer-Verlag, 2002.

[15] 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, LNAI 2375, pp.169–184, Springer-Verlag, 2002.

[16] Y. Suzuki, Y. Inomae, T. Shoudai, T. Miyahara, and T. Uchida, "A polynomial time matching algorithm of structured ordered tree patterns for data mining from semistructured data," Proc. ILP-02, LNAI 2583, pp.270–284, Springer-Verlag, 2002.

[17] Y. Suzuki, T. Shoudai, S. Matsumoto, and T. Miyahara, "Polynomial time inductive inference of ordered tree languages with height-constrained variables from positive data," Proc. PRICAI-2004, LNAI 3157, pp.211–220, Springer-Verlag, 2004.

[18] Y. Suzuki, T. Shoudai, T. Uchida, and T. Miyahara, "Ordered term tree languages which are polynomial time inductively inferable from positive data," Theor. Comput. Sci., vol.350, pp.63–90, 2006.

CiteULike    Connotea    Del.icio.us    What's this?

This Article Abstract Full Text (PDF) Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Add to My Personal Archive Download to citation manager Request Permissions Google Scholar Articles by MATSUMOTO, S. Articles by SUZUKI, Y. Search for Related Content Social Bookmarking          What's this?