Abstract
A linear graph pattern is a labeled graph such that its vertices have constant labels and its edges have either constant or mutually distinct variable labels. An edge having a variable label is called a variable and can be replaced with an arbitrary labeled graph. Let \({\mathcal GPC}\) be the set of all linear graph patterns having a structural feature \({\mathcal C}\) like “having a tree structure”, “having a two-terminal series parallel graph structure” and so on. The graph language GLc(g) of a linear graph pattern g in \({\cal GP}({\mathcal C})\) is the set of all labeled graphs obtained from g by substituting arbitrary labeled graphs having the structural feature \({\mathcal C}\) to all variables in g. In this paper, for any set \({\cal T_*}\) of m linear graph patterns in \({\cal GP}({\mathcal C})\), we present a query learning algorithm for finding a set S of linear graph patterns in \({\cal GP}({\mathcal C})\) with \(\bigcup_{g\in{\cal T_*}}GLc{(g)}=\bigcup_{f\in S}GLc{(f)}\) in polynomial time using at most m + 1 equivalence queries and O(m(n + n 2)) restricted subset queries, where n is the maximum number of edges of counterexamples, if the number of labels of edges is infinite. Next we show that finite sets of graph languages generated by linear graph patterns having tree structures or two-terminal series parallel graph structures are not learnable in polynomial time using restricted equivalence, membership and subset queries.
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
Amoth, T.R., Cull, P., Tadepalli, P.: On exact learning of unordered tree patterns. Machine Learning 44, 211–243 (2001)
Angluin, D.: Queries and concept learning. Machine Learning 2, 319–342 (1988)
Arimura, H., Sakamoto, H., Arikawa, S.: Efficient learning of semi-structured data from queries. In: Abe, N., Khardon, R., Zeugmann, T. (eds.) ALT 2001. LNCS (LNAI), vol. 2225, pp. 315–331. Springer, Heidelberg (2001)
Arimura, H., Shinohara, T., Otsuki, S.: Polynomial time algorithm for finding finite unions of tree pattern languages. In: Proc. NIL-91. LNCS (LNAI), vol. 659, pp. 118–131. Springer, Heidelberg (1993)
Duffin, R.J.: Topology of series parallel networks. J. Math. Anal. Appl. 10, 303–318 (1965)
Hirashima, H., Suzuki, Y., Matsumoto, S., Uchida, T., Nakamura, Y.: Polynomial time inductive inference of unions of two term tree languages. In: Proc. ILP 2006, pp. 92–94 (2006) (short papers)
Lloyd, J.W.: Foundations of Logic Programming, 2nd edn. Springer, Heidelberg (1987)
Lovász, L.: Combinatorial Problems and Exercises. ch. Two classical enumeration problems in graph theory. North-Holland Publishing Company (1979)
Matsumoto, S., Hayashi, Y., Shoudai, T.: Polynomial time inductive inference of regular term tree languages from positive data. In: ALT 1997. LNCS (LNAI), vol. 1316, pp. 212–227. Springer, Heidelberg (1997)
Matsumoto, S., Shoudai, T., Miyahara, T., Uchida, T.: Learning of finite unions of tree patterns with internal structured variables from queries. In: McKay, B., Slaney, J.K. (eds.) AI 2002: Advances in Artificial Intelligence. LNCS (LNAI), vol. 2557, pp. 523–534. Springer, Heidelberg (2002)
Matsumoto, S., Suzuki, Y., Shoudai, T., Miyahara, T., Uchida, T.: Learning of finite unions of tree patterns with repeated internal structured variables from queries. In: Gavaldá, R., Jantke, K.P., Takimoto, E. (eds.) ALT 2003. LNCS (LNAI), vol. 2842, pp. 144–158. Springer, Heidelberg (2003)
Miyahara, T., Suzuki, Y., Shoudai, T., Uchida, T., Takahashi, K., Ueda, H.: Discovery of frequent tag tree patterns in semistructured web documents. In: Chen, M.-S., Yu, P.S., Liu, B. (eds.) PAKDD 2002. LNCS (LNAI), vol. 2336, pp. 341–355. Springer, Heidelberg (2002)
Suzuki, Y., Akanuma, R., Shoudai, T., Miyahara, T., Uchida, T.: Polynomial time inductive inference of ordered tree patterns with internal structured variables from positive data. In: Kivinen, J., Sloan, R.H. (eds.) COLT 2002. LNCS (LNAI), vol. 2375, pp. 169–184. Springer, Heidelberg (2002)
Takami, R., Suzuki, Y., Uchida, T., Shoudai, T., Nakamura, Y.: Polynomial time inductive inference of TTSP graph languages from positive data. In: Kramer, S., Pfahringer, B. (eds.) ILP 2005. LNCS (LNAI), vol. 3625, pp. 366–383. Springer, Heidelberg (2005)
Uchida, T., Shoudai, T., Miyano, S.: Parallel algorithm for refutation tree problem on formal graph systems. IEICE Transactions on Information and Systems E78-D(2), 99–112 (1995)
Yamasaki, H., Shoudai, T.: A polynomial time algorithm for finding linear interval graph patterns. In: Proc. TAMC 2007. LNCS, vol. 4484, pp. 67–78. Springer, Heidelberg (2007)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Okada, R., Matsumoto, S., Uchida, T., Suzuki, Y., Shoudai, T. (2007). Exact Learning of Finite Unions of Graph Patterns from Queries. In: Hutter, M., Servedio, R.A., Takimoto, E. (eds) Algorithmic Learning Theory. ALT 2007. Lecture Notes in Computer Science(), vol 4754. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-75225-7_25
Download citation
DOI: https://doi.org/10.1007/978-3-540-75225-7_25
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-75224-0
Online ISBN: 978-3-540-75225-7
eBook Packages: Computer ScienceComputer Science (R0)