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

 MATSUMOTO Satoshi
 the Department of Mathematical Sciences, Tokai University

 SHOUDAI Takayoshi
 the Department of Informatics, Kyushu University

 UCHIDA Tomoyuki
 the Graduate School of Information Sciences, Hiroshima City University

 MIYAHARA Tetsuhiro
 the Graduate School of Information Sciences, Hiroshima City University

 SUZUKI Yusuke
 the Graduate School of Information Sciences, Hiroshima City University
Access this Article
Search this Article
Author(s)

 MATSUMOTO Satoshi
 the Department of Mathematical Sciences, Tokai University

 SHOUDAI Takayoshi
 the Department of Informatics, Kyushu University

 UCHIDA Tomoyuki
 the Graduate School of Information Sciences, Hiroshima City University

 MIYAHARA Tetsuhiro
 the Graduate School of Information Sciences, Hiroshima City University

 SUZUKI Yusuke
 the Graduate School of Information Sciences, Hiroshima City University
Abstract
A linear term tree is defined as an edgelabeled rooted tree pattern with ordered children and internal structured variables whose labels are mutually distinct. A variable can be replaced with arbitrary edgelabeled 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 <i>L</i>(<i>t</i>) of a linear term tree <i>t</i> is the set of all trees obtained from <i>t</i> by substituting arbitrary edgelabeled rooted ordered trees for all variables in <i>t</i>. Moreover, for a finite set <i>S</i> of linear term trees, we define <i>L</i>(<i>S</i>)=∪<sub><i>t</i>∈<i>S</i></sub><i>L</i>(<i>t</i>). A target of learning, denoted by <i>T</i>*, is a finite set of linear term trees, where the number of edge labels is infinite. In this paper, for any set <i>T</i>* of <i>m</i> linear term trees (<i>m</i>≥0), we present a query learning algorithm which exactly identifies <i>T</i>* in polynomial time using at most 2<i>mn</i><sup>2</sup> <i>Restricted Subset</i> queries and at most <i>m</i>+1 <i>Equivalence</i> queries, where <i>n</i> is the maximum size of counterexamples. Finally, we note that finite sets of linear term trees are not learnable in polynomial time using <i>Restricted Equivalence, Membership</i> and <i>Subset</i> queries.
Journal

 IEICE Transactions on Information and Systems

IEICE Transactions on Information and Systems 91(2), 222230, 20080201
The Institute of Electronics, Information and Communication Engineers
References: 18

1
 Exact learning of tree patterns from queries and counterexamples

AMOTH T. R.
Proc. COLT98, 175186, 1998
Cited by (1)

2
 Polynomial time algorithm for finding finite unions of tree pattern languages

ARIMURA H.
Proc. NIL91, 118131, 1993
Cited by (1)

3
 Polynomial time inductive inference of unions of two term tree languages

HIRASHIMA H.
Proc.ILP2006, The University of Corunna, 2006
Cited by (1)

4
 chapter Two classical enumeration problems in graph theory

LOVASZ L.
Combinatorial Problems and Exercises, 1979
Cited by (1)

5
 Learning pattern languages using queries

MATSUMOTO S.
Proc. EuroCOLT97, 185197, 1997
Cited by (1)

6
 Learning subsequence languages

MATSUMOTO S.
Information Modelling and Knowledge Bases VIII, 335344, 1997
Cited by (1)

7
 Learning unions of term tree languages using queries

MATSUMOTO S.
Proc. LA Summer Symposium, July 2002 "211""2110", 2002
Cited by (1)

8
 Learning of finite unions of tree patterns with repeated internal structured variables from queries

MATSUMOTO S.
Proc. ALT2003, 144158, 2003
Cited by (1)

9
 A polynomial time matching algorithm of structured ordered tree patterns for data mining from semistructured data

SUZUKI Y.
Proc. ILP02, 270284, 2002
Cited by (1)

10
 Polynomial time inductive inference of ordered tree languages with heightconstrained variables from positive data

SUZUKI Y.
Proc. PRICAI2004, 211220, 2004
Cited by (1)

11
 Ordered term tree languages which are polynomial time inductively inferable from positive data

SUZUKI Y.
Theor. Comput. Sci. 350, 6390, 2006
Cited by (1)

12
 On exact learning of unordered tree patterns

AMOTH T. R.
Machine Learning 44, 211243, 2001
DOI Cited by (2)

13
 Finding patterns common to a set of strings

ANGLUIN D.
Journal of Computer and System Sciences 21, 4662, 1980
DOI Cited by (22)

14
 Querise and concept learning

ANGLUIN D.
Machine Learning 2, 319342, 1988
DOI Cited by (21)

15
 Learning unions of tree patterns using queries

ARIMURA H.
Theoretical Computer Science 85, 4762, 1997
DOI Cited by (4)

16
 Efficient learning of semistructured data from queries

ARIMURA H.
Proc. ALT2001, 315331, 2001
Cited by (4)

17
 Discovery of Frequent Tag Tree Patterns in Semistructured Web Documents

MIYAHARA T.
Proc. PAKDD2002, 341355, 2002
Cited by (8)

18
 Polynomial time inductive inference of ordered tree patterns with internal structured variables from positive data

SUZUKI Y.
Proc. COLT2002, 169184, 2002
Cited by (5)
Cited by: 3

1
 A Polynomial Time Algorithm for Finding a Minimally Generalized Linear Interval Graph Pattern

YAMASAKI Hitoshi , SHOUDAI Takayoshi
IEICE Transactions on Information and Systems 92(2), 120129, 20090201
JSTAGE References (14)

2
 Polynomial Time Inductive Inference of TTSP Graph Languages from Positive Data

TAKAMI Ryoji , SUZUKI Yusuke , UCHIDA Tomoyuki , SHOUDAI Takayoshi
IEICE Transactions on Information and Systems 92(2), 181190, 20090201
JSTAGE References (13)

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

MATSUMOTO Satoshi , SUZUKI Yusuke , SHOUDAI Takayoshi , MIYAHARA Tetsuhiro , UCHIDA Tomoyuki
IPSJ SIG Notes 73, 1316, 20090226
References (6)