Structural results about exact learning with unspecified attribute values

This paper deals with the UAV learning model of Goldman, Kwek, and Scott, w here "UAV" is the acronym for "unspecified attribute values." As they, we c onsider exact earning within the UAV framework. A smooth transition between exact learning in the UAV setting and standard exact learning is obtained by putting a fixed bound r on the number of unspecified attribute values pe r instance. for r = 0, we obtain the standard model. For r = n (the total n umber of attributes), we obtain the (unrestricted) UAV model. Between these extremes, we find the hierarchies (UAV-MQ(r))(0 less than or equal to r le ss than or equal to n). (UAV-EQ(r))(0 less than or equal to r less than or equal to n). and (UAV-ARB-EQ(r))(0 less than or equal to r less than or equ al to n). Our main results are as follows. We present various lower bounds on the number of ARB-EQs and UAV-MQs in terms of the Vapnik-Chervonenkis di mension of the concept class. We show, furthermore, that a natural extensio n of Angluin's Sunflower Lemma is still applicable in the exact UAV learnin g model. Our UAV Sunflower Lemma allows the establishment of exponentially large lower bounds on the necessary number of UAV-MQs for several popular c oncept classes. On the other hand, we can show that slight simplifications of these classes are efficiently learnable using only a few UAV-MQs. Finall y, we investigate the inherent structure of the aforementioned three hierar chies and the relations between them. It turns out that query type UAV-EQ(r -1) is strictly stronger than UAV-EQ(r) (for each constant r). The analogou s result for UAV-ARB-EQ is valid. Furthermore, UAV-MQ(r + omega(log n)) is strictly stronger than UAV-MQ(r). We also determine the relation between qu ery types chosen from different hierarchies. (C) 2000 Academic Press.