The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
질의어와 선험적 지식을 바탕으로 단순 결정론적 언어에 대한 학습 알고리즘을 제안합니다. 학습자에게는 대표 샘플이라고 불리는 목표 언어의 특수한 유한 하위 집합이 처음에 제공되며, 동등 쿼리와 멤버십 쿼리의 두 가지 유형의 쿼리가 가능합니다. 이 학습 알고리즘은 Ishizaka(1990)의 아이디어를 기반으로 가설 문법의 비단말을 구성합니다. Ishizaka(1990)의 알고리즘에서 학습자는 긍정적인 반례를 통해 가능한 한 많은 규칙을 만들고, 부정적인 반례를 통해 잘못된 규칙을 진단합니다. 이에 비해 우리의 알고리즘은 Angluin(1987)의 알고리즘을 기반으로 간단한 결정론적 문법을 추측하고 이를 긍정 및 부정 반례를 사용하여 진단합니다.
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
부
Yasuhiro TAJIMA, Etsuji TOMITA, Mitsuo WAKATSUKI, "Polynomial Time Learnability of Simple Deterministic Languages from MAT and a Representative Sample" in IEICE TRANSACTIONS on Information,
vol. E83-D, no. 4, pp. 757-765, April 2000, doi: .
Abstract: We propose a learning algorithm for simple deterministic languages from queries and a priori knowledge. To the learner, a special finite subset of the target language, called a representative sample, is provided at the beginning and two types of queries, equivalence queries and membership queries, are available. This learning algorithm constructs nonterminals of a hypothesis grammar based on Ishizaka(1990)'s idea. In Ishizaka(1990)'s algorithm, the learner makes rules as many as possible from positive counterexamples, and diagnoses wrong rules from negative counterexamples. In contrast, our algorithm guesses a simple deterministic grammar and diagnoses them using positive and negative counterexamples based on Angluin(1987)'s algorithm.
URL: https://global.ieice.org/en_transactions/information/10.1587/e83-d_4_757/_p
부
@ARTICLE{e83-d_4_757,
author={Yasuhiro TAJIMA, Etsuji TOMITA, Mitsuo WAKATSUKI, },
journal={IEICE TRANSACTIONS on Information},
title={Polynomial Time Learnability of Simple Deterministic Languages from MAT and a Representative Sample},
year={2000},
volume={E83-D},
number={4},
pages={757-765},
abstract={We propose a learning algorithm for simple deterministic languages from queries and a priori knowledge. To the learner, a special finite subset of the target language, called a representative sample, is provided at the beginning and two types of queries, equivalence queries and membership queries, are available. This learning algorithm constructs nonterminals of a hypothesis grammar based on Ishizaka(1990)'s idea. In Ishizaka(1990)'s algorithm, the learner makes rules as many as possible from positive counterexamples, and diagnoses wrong rules from negative counterexamples. In contrast, our algorithm guesses a simple deterministic grammar and diagnoses them using positive and negative counterexamples based on Angluin(1987)'s algorithm.},
keywords={},
doi={},
ISSN={},
month={April},}
부
TY - JOUR
TI - Polynomial Time Learnability of Simple Deterministic Languages from MAT and a Representative Sample
T2 - IEICE TRANSACTIONS on Information
SP - 757
EP - 765
AU - Yasuhiro TAJIMA
AU - Etsuji TOMITA
AU - Mitsuo WAKATSUKI
PY - 2000
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E83-D
IS - 4
JA - IEICE TRANSACTIONS on Information
Y1 - April 2000
AB - We propose a learning algorithm for simple deterministic languages from queries and a priori knowledge. To the learner, a special finite subset of the target language, called a representative sample, is provided at the beginning and two types of queries, equivalence queries and membership queries, are available. This learning algorithm constructs nonterminals of a hypothesis grammar based on Ishizaka(1990)'s idea. In Ishizaka(1990)'s algorithm, the learner makes rules as many as possible from positive counterexamples, and diagnoses wrong rules from negative counterexamples. In contrast, our algorithm guesses a simple deterministic grammar and diagnoses them using positive and negative counterexamples based on Angluin(1987)'s algorithm.
ER -