ML Anthology

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

Satoshi Matsumoto, Yusuke Suzuki, Takayoshi Shoudai, Tetsuhiro Miyahara, Tomoyuki Uchida
ALT 2003 pp. 144-158
doi:10.1007/978-3-540-39624-6_13 /alt/2003/matsumoto2003alt-learning/

Abstract

In the field of Web mining, a Web page can be represented by a rooted tree T such that every internal vertex of T has ordered children and string data such as tags or texts are assigned to edges of T . A term tree is an ordered tree pattern, which has ordered tree structures and variables, and is suited for a representation of a tree structured pattern in Web pages. A term tree t is allowed to have a repeated variable which occurs in t more than once. In this paper, we consider the learnability of finite unions of term trees with repeated variables in the query learning model of Angluin (1988). We present polynomial time learning algorithms for finite unions of term trees with repeated variables by using superset and restricted equivalence queries. Moreover we show that there exists no polynomial time learning algorithm for finite unions of term trees by using restricted equivalence, membership and subset queries. This result indicates the hardness of learning finite unions of term trees in the query learning model.

PDF ALT Semantic Scholar

Cite

Text

Matsumoto et al. "Learning of Finite Unions of Tree Patterns with Repeated Internal Structured Variables from Queries." International Conference on Algorithmic Learning Theory, 2003. doi:10.1007/978-3-540-39624-6_13

Markdown

[Matsumoto et al. "Learning of Finite Unions of Tree Patterns with Repeated Internal Structured Variables from Queries." International Conference on Algorithmic Learning Theory, 2003.](https://mlanthology.org/alt/2003/matsumoto2003alt-learning/) doi:10.1007/978-3-540-39624-6_13

BibTeX

@inproceedings{matsumoto2003alt-learning,
  title     = {{Learning of Finite Unions of Tree Patterns with Repeated Internal Structured Variables from Queries}},
  author    = {Matsumoto, Satoshi and Suzuki, Yusuke and Shoudai, Takayoshi and Miyahara, Tetsuhiro and Uchida, Tomoyuki},
  booktitle = {International Conference on Algorithmic Learning Theory},
  year      = {2003},
  pages     = {144-158},
  doi       = {10.1007/978-3-540-39624-6_13},
  url       = {https://mlanthology.org/alt/2003/matsumoto2003alt-learning/}
}