Name
Title | ||
|---|---|---|
Efficient Learning of Ordered and Unordered Tree Patterns with Contractible Variables |
Abstract | ||
|---|---|---|
Due to the rapid growth of tree structured data such as Web documents, efficient learning from tree structured data becomes more and more important. In order to represent structural features common to such tree structured data, we propose a term tree, which is a rooted tree pattern consisting of tree structures and labeled variables. A variable is a labeled hyperedge, which can be replaced with any tree. A contractible variable is an erasing variable which is adjacent to a leaf. A contractible variable may be replaced with a singleton vertex. A usual variable, called an uncontractible variable, is replaced with a tree of size at least 2. In this paper, we deal with ordered and unordered term trees with contractible and uncontractible variables such that all variables have mutually distinct variable labels. First we give a polynomial time algorithm for deciding whether or not a given term tree matches a given tree. Let Lambda be a set of edge labels. Second, when Lambda has more than one edge label, we give a polynomial time algorithm for finding a minimally generalized ordered term tree which explains all given tree data. Lastly, when Lambda has infinitely many edge labels, we give a polynomial time algorithm for finding a minimally generalized unordered term tree which explains all given tree data. These results imply that the classes of ordered and unordered term trees are polynomial time inductively inferable from positive data. |
Year | DOI | Venue |
|---|---|---|
2003 | 10.1007/978-3-540-39624-6_11 | ALGORITHMIC LEARNING THEORY, PROCEEDINGS |
Keywords | Field | DocType |
tree structure,inductive inference,polynomial time | Range tree,K-ary tree,Vantage-point tree,Artificial intelligence,Tree structure,Interval tree,Discrete mathematics,Combinatorics,Left-child right-sibling binary tree,Segment tree,Machine learning,Mathematics,Search tree | Conference |
Volume | ISSN | Citations |
2842 | 0302-9743 | 4 |
PageRank | References | Authors |
0.49 | 16 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yusuke Suzuki | 1 | 150 | 18.82 |
| Takayoshi Shoudai | 2 | 269 | 31.89 |
| Satoshi Matsumoto | 3 | 55 | 8.66 |
| Tomoyuki Uchida | 4 | 255 | 35.06 |
| Tetsuhiro Miyahara | 5 | 267 | 32.75 |