
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

On the Role of Equivalence Queries in Learning via Queries
Seiichi TANI
Publication
IEICE TRANSACTIONS on Information and Systems
Vol.E75D
No.4
pp.435441 Publication Date: 1992/07/25
Online ISSN:
DOI:
Print ISSN: 09168532 Type of Manuscript: Special Section PAPER (Special Issue on Algorithmic Learning Theory) Category: Keyword: Query learning, equivalence queries, exact learning,
Full Text: PDF(645.7KB) >>Buy this Article
Summary:
We consider the role of equivalence queries in learning unknown concepts using membership and equivalence queries. Equivalence queries have the following two roles: (R1) indicating whether a learning algorithm has succeeded to learn the unknown concept and (R2) providing counterexamples. In this paper, we consider the learning using membership and equivalence queries but using only the (R2) part of equivalence queries. In order to gain an insight into the learning membership and equivalence queries but using only the (R2) part of equivalence queries, we define equivalencedetecting problem". Let C be a representation class which is polynomial time learnable using membership and equivalence queries. We show that if the equivalencedetecting problem for C is polynomial time solvable then C is polynomial time learnable using membership and equivalence queries without using (R1). Moreover, we show that under certain conditions, the two notions, polynomial time solvability of equivalencedetecting problem" and polynomial time learnability using membership and equivalence queries without using (R1)", are equivalent. For concrete examples, we prove that dfas are polynomial time learnable using membership and equivalence queries without using (R1) in the learning situation where the algorithm is informed the number of states of the minimum states dfa accepting the target set in advance. On the other hand, we show that the equivalencedetecting problem for dfas are not solvable in the learning situation where the algorithm can use no additional information. This result together with our main result shows that, in this learning situation, the (R1) part of equivalence queries are necessary to learn dfas using membership and equivalence queries.

