C be a representation class which is polynomial time learnable using membership and equivalence queries. We show that if the equivalence-detecting 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 equivalence-detecting 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 equivalence-detecting 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." />


On the Role of Equivalence Queries in Learning via Queries

Seiichi TANI  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E75-D   No.4   pp.435-441
Publication Date: 1992/07/25
Online ISSN: 
Print ISSN: 0916-8532
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 equivalence-detecting problem". Let C be a representation class which is polynomial time learnable using membership and equivalence queries. We show that if the equivalence-detecting 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 equivalence-detecting 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 equivalence-detecting 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.