Structural Results about Exact Learning with Unspecified Attribute Values

摘要

This paper deals with the UAV learning model of Goldman, Kwek, and Scott, where “UAV” is the acronym for “unspecified attribute values.” As they, we consider 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 per instance. For r=0, we obtain the standard model. For r=n (the total number of attributes), we obtain the (unrestricted) UAV model. Between these extremes, we find the hierarchies (UAV-MQr)0⩽r⩽n, (UAV-EQr)0⩽r⩽n, and (UAV-ARB-EQr)0⩽r⩽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 dimension of the concept class. We show, furthermore, that a natural extension of Angluin's Sunflower Lemma is still applicable in the exact UAV learning model. Our UAV Sunflower Lemma allows the establishment of exponentially large lower bounds on the necessary number of UAV-MQs for several popular concept classes. On the other hand, we can show that slight simplifications of these classes are efficiently learnable using only a few UAV-MQs. Finally, we investigate the inherent structure of the aforementioned three hierarchies and the relations between them. It turns out that query type UAV-EQr−1 is strictly stronger than UAV-EQr (for each constant r). The analogous result for UAV-ARB-EQ is valid. Furthermore, UAV-MQr+ω(log n) is strictly stronger than UAV-MQr. We also determine the relation between query types chosen from different hierarchies.