線形回数の所属性質問と１つの正例による正則パターン言語族に対する質問学習アルゴリズム

摘要

計算論的学習理論において，質問学習モデルは質問を用いた学習の数学モデルであり，巨大なデータベースから特徴的なパターンを抽出するデータマイニングのモデルとしてみることもできる．この質問学習モデルにおいて，正則パターン言語のクラスは，1 つの正例から多項式回数の所属性質問を用いて質問学習可能であることが論文で示されている．この結果を拡張し，本稿では，1 つの正例と線形回数の所属性質問を用いて正則パターン言語のクラスを同定する質問学習アルゴリズムを提案し，その正当性を示す．