繰り返し内部構造変数を持つ木パターンの有限和の質問学習 Learning of Finite Unions of Tree Patterns with Repeated Internal Structured Variables from Queries

Search this Article

Author(s)

Abstract

Dana Angluinにより質問を用いた学習の数理モデル(質問学習モデル)が提案されている.これまでの研究の多くは文字列を要素とする言語を対象としており,パターン言語や正規言語などの言語族が多項式時間で学習可能であることが示されてきた.現在,Web上のHTML/XMLファイルなどのような木構造データが大量に存在する.我々は,木構造データに共通する構造を表現するパターンとして,項木という木構造パターンを提案している.本論文では,特徴的木構造を柔軟に表現するために,内部構造変数の繰り返しを許す項木で定義される言語の有限な和集合のクラスを考え,このクラスが質問学習モデルにおいて多項式時間で学習可能であることを示す.

A term tree is an ordered tree pattern, which have ordered tree structure and variables, and is suited for a representation of a tree structured pattern. 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 exact learning model of Angluin (1988), which is a mathematical model of learning via queries in computational learning theory. 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 exact learning model.

Journal

  • IPSJ SIG Notes

    IPSJ SIG Notes 73, 13-16, 2009-02-26

    Information Processing Society of Japan (IPSJ)

References:  6

Codes

  • NII Article ID (NAID)
    110007338672
  • NII NACSIS-CAT ID (NCID)
    AN10505667
  • Text Lang
    ENG
  • Article Type
    ART
  • ISSN
    09196072
  • NDL Article ID
    10200587
  • NDL Source Classification
    ZM13(科学技術--科学技術一般--データ処理・計算機)
  • NDL Call No.
    Z14-1121
  • Data Source
    CJP  NDL  NII-ELS 
Page Top