文献

J-GLOBAL ID：202002287558482559   整理番号：20A1394798

1つのポジティブ例とメンバシップ問合せの線形数を用いた正規パターン言語のための効率的学習アルゴリズム

An Efficient Learning Algorithm for Regular Pattern Languages Using One Positive Example and a Linear Number of Membership Queries

著者 (5件)： MATSUMOTO Satoshi (School of Science, Tokai University) ,  UCHIDA Tomoyuki (Graduate School of Information Sciences, Hiroshima City University) ,  SHOUDAI Takayoshi (Faculty of Contemporary Business, Kyushu International University) ,  SUZUKI Yusuke (Graduate School of Information Sciences, Hiroshima City University) ,  MIYAHARA Tetsuhiro (Graduate School of Information Sciences, Hiroshima City University)
資料名： IEICE Transactions on Information and Systems (Web)  (IEICE Transactions on Information and Systems (Web))
巻： E103.D  号： 3  ページ： 526-539(J-STAGE)  発行年： 2020年 
JST資料番号： U0469A  ISSN： 1745-1361  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 英語 (EN)

抄録/ポイント： 正規パターンは,定数記号と明確な変数記号から成る文字列である。正規パターンの言語は,非空の文字列で正規パターンにおける全ての変数記号を置き換えることによって得られる全ての定数文字列の集合である。本論文は,計算学習理論における問合せによる学習の確立された数学モデルである,Angluinの問合せ学習モデル内の正規パターンの言語の学習問題を扱った。正規パターンの言語のクラスは,問合せ学習モデルにおいて,メンバシップ問合せの多項式数を用いて,1つのポジティブ例から同定できることが知られている。本論文で筆者らは,正規パターンの言語のクラスが,ポジティブ例の長さに関して,メンバシップ問合せの線形数を用いて,1つのポジティブ例から同定可能であることを示した。(翻訳著者抄録)

シソーラス用語： *質問 ,  言語 ,  *学習アルゴリズム ,  定数 ,  記号 ,  変数 ,  文字列 ,  理論 ,  数学モデル ,  学習 ,  学習モデル ,  *ソフトウェア設計 ,  *パターンランゲージ
準シソーラス用語： *パターン言語 ,  計算学習理論 ,  *問合せ

著者キーワード (4件)： パターン言語 ,  メンバーシップ質問 ,  質問学習 ,  計算学習理論

分類 (2件)： 計算機システム開発  (JD02010R) ,  人工知能  (JE08000Z)

引用文献 (28件)：

• [1] D. Angluin, “Queries and concept learning,” Machine Learning, vol.2, no.4, pp.319-342, 1988. 10.1007/bf00116828
• [2] H. Mamitsuka and N. Abe, “Efficient mining from large databases by query learning,” Proc. 7th International Conference on Machine Learning (ICML'00), pp.575-582, 2000.
• [3] D. Angluin, “Finding patterns common to a set of strings,” Journal of Computer and System Sciences, vol.21, no.1, pp.46-62, 1980. 10.1016/0022-0000(80)90041-0
• [4] A. Marron, “Learning pattern languages from a single initial example and from queries,” Proc. Workshop on Computational Learning Theory (COLT'88), pp.345-358, 1988.
• [5] S. Matsumoto and A. Shinohara, “Learning pattern languages using queries,” Proc. European Conf. on Computational Learning Theory (EuroCOLT'97), LNAI, vol.1208, pp.185-197, Springer, Berlin, 1997. 10.1007/3-540-62685-9_16

タイトルに関連する用語 (6件)： メンバ ,  シップ ,  問合せ ,  線形 ,  パターン言語 ,  学習アルゴリズム