内部変数付き木パターン言語の有限和の質問学習 Learning of finite unions of tree patterns with internal structured variables from queries

Search this Article

Author(s)

Abstract

順序項木とは複数の順序木に含まれる共通構造を表現することができる木構造パターンである.順序項木は順序木の連結な部分構造を変数に置きかえることにより得られる.逆に,この変数を任意の順序木に置きかえることにより多くの順序木を表現する.順序項木tから得られる全ての順序木の集合L(t)を,順序項木tから得られる順序項木言語という.順序項木の有限集合Hから得られる順序項木言語の和集合をL(H)=U_<t∈H>L(t)と定める.我々は順序項木言語の和集合のクラスの多項式時間学習可能性をAngluin(1988)により提案された質問学習モデルに基づいて考察した.本論文では,m個の順序項木からなる集合H_*から得られる言語L(H_*)を高々2mn^2回の制限された部分性質問と高々m+1回の等価性質問によって同定し,L(H)=L(H_*)となるような高々m個の順序項木からなる集合Hを出力する学習アルゴリズムを提案した.ここでnは等価性質問をすることで得られる反例の順序木の最大頂点数である.

We consider the polynomial time learnability of finite unions of ordered tree patterns with internal structured variables in the query learning model proposed by Angluin (1988). An ordered tree pattern with internal structured variables, called a term tree, is a rooted tree pattern which consists of tree structures with ordered children and internal structured variables. A term tree is suited for representing structural features in semistructured or tree structured data such as HTML/XML files. The language L (t) of a term tree t is the set of all trees which are obtained from t by substituting arbitrary trees for all variables in t. Moreover, for a finite set H of term trees, L (H) = ?t⋴HL (t). Our target of learning is a finite set H of term trees. We show that any finite union of languages defined by m term trees is exactly identifiable in polynomial time using at most 2mn^2 restricted subset queries and at most m + 1 equivalence queries, where n is the maximum size of counterexamples.

Journal

  • IEICE technical report. Theoretical foundations of Computing

    IEICE technical report. Theoretical foundations of Computing 102(593), 29-36, 2003-01-17

    The Institute of Electronics, Information and Communication Engineers

References:  15

Codes

  • NII Article ID (NAID)
    110003178732
  • NII NACSIS-CAT ID (NCID)
    AN10013152
  • Text Lang
    ENG
  • Article Type
    ART
  • ISSN
    09135685
  • NDL Article ID
    6467922
  • NDL Source Classification
    ZN33(科学技術--電気工学・電気機械工業--電子工学・電気通信)
  • NDL Call No.
    Z16-940
  • Data Source
    CJP  NDL  NII-ELS 
Page Top